JPH05508497A - Method and apparatus for non-sequential source access - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention] Methods and device techniques for non-sequential resource access Field The present invention provides storage systems and recording for computers and electronic logic systems. Regarding storage management. More specifically, the present invention provides Requests to shared resources, especially main memory, that can result in out-of-order responses METHODS AND APPARATUS FOR NON-SEQUENTIAL MEMORY ACCESS Ru.

Forward technique Multiple requesters for accessing shared hardware resources, especially main memory Conventional methods and apparatus in a system are to prevent overwriting or inaccurate access to the shared resources. requirements that maintain a chronological or ordered relationship with each other. ing. In fact, the possibility of out-of-order access to shared resources is typically or considered as an incorrect access to an instruction, and in the prior art, the memory access hazard It is called a code.

In the prior art, access to shared resources in multiprocessor systems is restricted. One technique used to control the demand for shared resources is to use a global decision algorithm to The goal is to maintain a central control mechanism that is handled by algorithms. Its multiple processes If the server system is physically small and has a small number of clusters and a small number of shared resources, This method is effective if you only have a source. Many Nori Questa and many In larger multiprocessor systems with shared resources of A central method using algorithms can be cumbersome and the decision time can be It begins to affect the overall processing performance of heavy processors.

Another prior art technique is to make a given decision only if the previous decision has been cleared. Interlocking various decisions with time tags as they occur. this The problem with this method is that signals travel through the system that update those time tags. The transient time of That's true.

Essentially, the problem of resource lockout and shared resource access is In a computer, each resource is scheduled sequentially across its multiprocessor system. is managed by utilizing a central #i1 mechanism that processes This method effectively avoids the memory access hazard problem at the expense of system performance. Ru.

A novel method and system for accessing shared resources in multiprocessor systems There are four issues to consider when designing a stem. The first problem is that The question is how to maximize the throughput of shared resources.

The second problem is how to maximize the bandwidth between the processor and the shared resources. It's up to you. The third problem is the access time between processors and shared resources. The question is how to minimize it. The final issue is that there are predictable outcomes for resource requirements. The problem is how to avoid access hazards so that access can be achieved. computer If the data processing system does not provide optimal solutions to all of these problems, The performance of that system is effectively limited.

For example, consider the problem of a processor making three requests to main memory. . Each request results in a message being processed by three separate logical mechanisms. shall be directed to different partitions of in-memory. With conventional technology, these requirements Each of the must be consecutive, with subsequent requests completing the preceding request. cannot be started until In this example of three requests, the requirements for sequential access are The requirement is that the logic 273 related to the main memory is in an idle state. bring about results. This restriction is designed to be done as a vibrating operation. Processing requirements are reduced by providing a steady flow of work to processing elements and shared resources. A high-performance system whose purpose is to keep primary and shared resources continuously busy. This is especially hard on the stem.

Such high-performance computer processing systems, often referred to as supercomputers, In an effort to improve the processing speed and flexibility of 'C1uster Architecture for a Highly Parallel 5 calar/Vector Mul tipr.

PCT Application No. PCT/US9010 entitled “cessor System” The 7665 has multiple processors and external interfaces, main memory, large multiple and Provides an architecture for supercomputers that can perform simultaneous requests. ing. schedule each resource sequentially across its multiprocessor system This prior art technique, which utilizes a central control mechanism for This is unacceptable for cluster architectures for processors. Therefore, all Guarantees equal and democratic access to all access points across shared resources simultaneously so that each shared resource has independent speed and avoids access hazards. multiprocessor systems by allowing data to be processed atomically. New methods and devices for memory access are needed to improve memory access performance. Summary of the Invention The present invention provides non-sequential access to shared resources in multiple requester systems. provides a method and apparatus for

To achieve this, the present invention provides a method for effectively reordering data at its destination. Use various tags for this purpose. In its simplest form, this tag concerns directional information. to a location in the buffer to position another tag, or related to that tag. switch to a location in a buffer or processor (register) to issue a response. Orient the changing logic. For example, to load data from memory, its Requires requester to provide request signal, address and request tag . The request signal checks the validity of its address and request tag. The address is Specifies the location in memory of the requested data. The request tag indicates that the data Specifies where to put the data when it is returned to the processor.

The device for non-sequential shared resource access according to the invention also comprises a multi-processor system. Multiple processors and multiple inputs that can access the system's shared resources Used in multiprocessor systems with output interfaces. suitable Shared resources in some embodiments include main memory, global registers, and interrupt facilities. including. For non-sequential access within a cluster of tightly coupled processors, the present invention is a request generation resource for generating multiple resource requests from that processor, and its is operably connected to the request-generating resources of the resource when those resource requests are generated. A switch for receiving resource requests in inter-order order and routing the resource requests to shared resources. and servicing the resource request when the requested resource becomes available. shared resource means for Each resource request includes the address of the requested shared resource, and a request tag that specifies the storage location within the requester where the resource request should be returned. Including.

The switching logic associated with the switching means is related to its resource requirements. A tag queue for storing requested request tags and individual requests from that tag queue. A logical means for relating request tags to resource responses, and how those resource responses and individual requests can be and means for returning the requested tag to the processor. Switching involving shared resources The switching logic provides the switching means to route requests to and from shared resources and Control logic for correctly routing requests and logic for handling multiple decision requests. the logic for storing or retrieving the final data entity requested. including.

In other embodiments, the present invention also provides for It also allows non-sequential access to shared resources. In this example, the cluster tag Attach additional routing information to the request tag to generate a new tag called A remote cluster adapter is provided in the logical means to enable the clustering. This cluster tag is passed to the target cluster's remote cluster adapter, where it is removed from its request. and stored in the tag buffer. new to be used internally in the target cluster A request tag is generated. The response is sent back to the target cluster's remote cluster adapter. , the returned request tag will have its associated corresponding class in the tag buffer. Used to position tags. That response and cluster tag is then Returned to the requesting cluster. The requesting cluster's remote cluster adapter The raster tag is broken down into additional return routing information and request tag parts.

The additional return routing section passes the response and request tag sections to the requesting switching Used to return to the stage.

A special consequence of this system is that control is handled locally and access to shared resources is to ensure that access decisions are made quickly and that resources are fully utilized. This means that it is done only when necessary. Extremely high system bandwidth and By maintaining the highest possible system throughput combined, the present invention achieves , the requester is provided with a steady supply of data to process with minimal access time. system bandwidth and throughput parameters. improve the overall performance of a multiprocessor system for a given set.

It is an object of the invention that the responses may be returned out of order with respect to the chronological order in which the requests were issued. methods and methods for non-sequential storage access that can issue requests to shared resources. and equipment.

A second object of the present invention is to enable each component of the shared resource system to simultaneously and Interleave by ensuring that it can operate at potentially different speeds. For memory access that can improve performance in shared resource systems An object of the present invention is to provide a method and apparatus for the invention.

A third object of the present invention is that the multiprocessor system High bandwidth, high throughput when configured with many shared resources A storage access system for multiprocessor systems that provides high performance and low latency. The object of the present invention is to provide a method and apparatus for the system.

The foregoing and other objects of the invention will be further appreciated from the drawings, detailed description of the preferred embodiments, and the accompanying drawings. This will become clear from the following claims.

Drawing description Figures 1a, lb, lc and 1d show the conventional technology and the viblining requirements of the present invention. FIG. 2 is an explanatory diagram of a /response storage access technique.

FIG. 2 is a block diagram of a single multiprocessor cluster of a preferred embodiment of the present invention. be.

38 and 3b are block diagrams of a four-cluster implementation of the preferred embodiment of the present invention. be.

FIG. 4 shows a single multi-processor illustrating the arbitration node implementation of the preferred embodiment. FIG. 2 is a block diagram of a processor cluster.

Figures 5a and 5b show details of the human output interface in a preferred embodiment of the invention. It is a detailed block diagram.

Figures 6a and 6b illustrate the ports involved in the input/output interface within the processor. FIG. 3 is a detailed block diagram.

7a, 7b, 7c, 7d and 7e are illustrations of various request tags of the present invention. .

FIG. 8 is a block diagram of the external interface boat.

FIG. 9 shows the correspondence between request tags and command block words.

FIG. 1O is a detailed block diagram of the NRCA means in a preferred embodiment of the invention. .

Figures 11g and 11b show detailed blocks of the MRCA means in a preferred embodiment of the invention. It is a lock diagram.

DESCRIPTION OF THE PREFERRED EMBODIMENT First, FIGS. 1a to 1d show that the present invention's vibrating disorder is compared with the prior art. The sequential access mechanism will be explained. These diagrams illustrate the memory/shared resource architecture. It is applicable to request/response operations at each level of the architecture. Multilayer Questa System It should be understood that memory is a commonly accessed shared resource in Therefore, the preferred embodiment of the present invention will also be described in terms of access to memory. However, the present invention does not require that access be made to any form of shared hardware resource. It is assumed that this will occur. In this sense, shared hardware resources include memory, In addition to global registers and interrupt mechanisms, boats, routes, functional units, registers, and wait lines Including columns, banks, etc.

Figure 18 shows how a series of requests and responses flow in a conventional system. It shows that it is treated like a sea urchin. Random access or streaming functionality is now available. each successive request waits until the next request can start. must wait for the related responses to complete. Regarding Figure 1b, Some prior art vector processors do not have to wait for each response to be returned. , the ability to issue successive requests to load or write vector registers. We are supporting. Such a limited vibelining technique, shown in Figure 1b, applied to vector processors that access memory, but other system resources is not applied.

In contrast, Figure 1c shows that all requests and their related responses are in time order. but response 1 can be returned before request n is issued, in an interleaved system. Showing column requests and responses. In Fig. 1d, the entire random order access mechanism of the present invention is shown. The ability to ensure that requests and their associated responses do not have any special relationship to temporal order. This is exemplified by the fact that it occurs unaccompanied. The storage access shown in this diagram In a process system, response 2 may be returned before response 1. Illustrated in Figure 1d The Vibrine technique has not been applied in the prior art.

In describing the preferred embodiment, the following describes a preferred implementation of a multiprocessor system. Start with an explanation of the example, then a description of the various requesters and their related boats. Starting with the shared resources of the multiprocessor system, we discuss A method and apparatus for this purpose are described.

[Multiprocessor system]

FIG. 2 shows a preferred implementation of a multiprocessor system for use with the present invention. An example single multiprocessor cluster architecture is described. Altitude level This preferred cluster architecture for column cluster/multiprocessor systems A architecture is a large set of shared resources 12 (main memory 14, global registers 16 , interrupt mechanism 18, etc.). Can be done. The processor 10 is capable of both vector and scalar parallel processing, It is connected to the shared resource 12 via arbitration node means 20. Ma In addition, a plurality of external interface points are connected via the arbitration node means 20. 22 and an input/output concentrator (IOC) 24 are connected to it. These are further connected to various external data transmitting devices 26. These external data The data transmitter 26 is connected to the input/output concentrator 24 by a high speed channel 30. A secondary storage system (SMS) 28 may be included.

External data transmitter 26 also provides input/output control via one or more standard channels 34. various other peripheral devices and interfaces 32 connected to the center 24. can be included. These peripherals and interfaces 32 storage devices, tape storage devices, printers, external processors, and communication networks. can be included. Processor 10, shared resource 12, arbitration node 20 and external interface port 22 together form a preferred implementation of the present invention. Single multiprocessor cluster for highly parallel multiprocessor systems according to example 40.

A preferred embodiment of multi-processor cluster 40 includes processors 10, shared resources 12 , one or more arbitration nodes 20 and external interface ports 22. By physically organizing into clusters 40 on Overcoming problems with computer direct connect interfaces. Shown in Figures 3a and 3b In the preferred embodiment there are four clusters: J40a, 40b, 40c and 40d. Exists. These clusters 40a, 40b.

40c and 40d each have their own cluster associated with that cluster. Processor 10” + 10b.

10c and 10d, shared resources 12a, 12b, 12c and 12d1, and Collection of external interface ports 22a, 22b, 22c and 22d have a physical presence. Clusters 40a, 40b, 40c and 40d are each arbitration node means 20a, 20b.

20c and 20d are interconnected by remote cluster adapter 42, which is a logical part of 20c and 20d. It is continued. Cluster 40a.

Although 40b, 40c and 40d are physically separated, the The logical organization and physical interconnection by remote cluster adapters 42 40a.

Shared resources 12g, 12b, 12c and 40b, 40c and 40d and 12d.

Referring now to FIG. 4, the arbitration node means 20 of a single cluster 40 A preferred embodiment will be described. At a conceptual level, arbitration no The code means 20 connects the processor 10 and the external interface port 22 to the same to shared resources 12 within cluster 40 and through remote cluster adapter 42 A plurality of cross-connections symmetrically interconnecting shared resources 12 in other clusters 40. Including bar switch. Normally, a full crossbar switch allows each requester to should allow you to connect to. In the present invention, the arbitration no. The code means 20 performs a full cross operation in a situation where there are more number questers than resources. It makes it possible to obtain similar results with a bar switch. In the preferred embodiment, the arbitrator The arbitration node means 20 includes 16 arbitration nodes 44 and Includes remote cluster adapter means 42. The remote cluster adapter means 42 memory remote cluster adapter (NRCA) means 46 and memory remote cluster adapter (NRCA) means 46; (MRCA) means 48.

The NRCA means 46 allows the arbitration node 44 to The remote cluster adapter means 42 of the server cluster 40 can be accessed.

Similarly, the MRCA means 48 controls the remote clocks of all other multiprocessor clusters 40. Access to the shared resources 12 of that cluster 40 from the raster adapter means 42 control the

In this example, the 16 arbitration nodes 44 have 32 arbitration nodes. The processor 10 and 32 external interface ports 22 are connected to the main memory 14, Interconnect with global register 16 and interrupt mechanism 18 and NRCA means 46 I'm letting you do it. Each arbitration node 44 has eight bidirectional parallel paths 50. Therefore, it is connected to the main memory 14. A single parallel bidirectional path 52 connects each The arbitration node 44 is connected to NRCA means 46. good practice In the example, the same route 52 from each arbitration node 44 is also connection node 44 to global register 16 and interrupt mechanism 18; is used in the It will be understood that

As with each arbitration node 44, the MRCA means 48 has eight bidirectional It is connected to the main memory 14 by a parallel path 54 . Similarly, a single parallel Bidirectional path 56 connects MRCA means 48 to global register 16 and interrupt mechanism 1. It is connected to 8. In the preferred embodiment, a total of six parallel bidirectional paths 58 are connected to the clock. It is used to interconnect rasters 40. For example, cluster 40g is It has two paths 58 connecting each cluster 40b, 40c and 40d. child In this way, the MRCA means 48 detects whether another cluster 40 of that cluster 40 Allows direct access to shared resources 12.

As shown in Figures 58 and 5b, each of the memory ports 310 ports 312, and processor ports 314.31.5, 316 and 317. Arbitration networks 303 and 306 for each A bitration node 44 is included. In addition, the arbitration node 44 has the following information: Input boat queue 301, crossbars 302 and 307, tag queue 30 4 and a data queue 305.

Arbitration networks 303 and 3, as described in detail herein. 06 uses a first-come, first-served service to ensure that the oldest references are processed first. You are using the requester toggle method. In the case of multiple old references with the same age, the public The Taira algorithm applies to its arbitration network 303 or 306. Therefore, the ports 310 and 312 and 315, 316 and 316 controlled respectively and 317.

In other supercomputers, memory returns are the same as the order in which the requests were sent. Return in order. Therefore, there are no issues as to where to put the data when it returns. Since there is no ambiguity, the processor's memory return logic is simple.

However, restricting memory returns in order is Rather, the shared resource is forced to wait until it explicitly learns of the breaking of either order. , which also means sacrificing performance and therefore reducing the amount of concurrent activity. become. The early return is due to the heterogeneous latencies of that storage system, A return that returns with a shorter latency than the requested return. Li If the turn is not constrained to return in the same order that the requests were sent, then To guarantee this, the storage subsystem must provide a sorting mechanism. do not have. This allows multiple ports to request data and multiple ports to return that data. If a memory department exists, it will be a considerable burden.

In the present invention, memory data returns are returned out of order with respect to the order of the request. I can do it. Whenever a request accumulates in the queue, the response is The fact that the matrix can be returned in random order with respect to the relative time initially entered is that is a feature of heavy processor-wide queuing and arbitration networks. Ru. This means that data from earlier requests may return later than data from later requests. It means to be. However, due to ordering limitations in processors, Therefore, it may not be possible to use data that arrives early.

For example, data associated with arithmetic operations may be Must be used in the same order as specified in the gram. Therefore, in the present invention , the memory returns data regardless of whether it is already actually available or not. first, its final destination (vector register, space register, L register, instruction cache) output buffer or human output buffer). that data can be used The decision is based on the response status of previously issued requests.

The present invention provides that all system resources are Method and apparatus for shared resource access that can be accessed using the full scope of the law It is to provide. To achieve this, the invention records requests and responses. tags and queues to effectively reorder that data at its destination. use.

In its simplest form, a tag uses its base to position another tag for directional information. buffer or location in which to place responses related to that tag. tells its logic its location in the processor (register).

For example, to request data from memory, the requester uses a request signal, an address request tags. The request signal indicates the address and request Check the validity of tags. The address is the location of the response data in main memory. Specify. Request tags include data when it is returned to the processor. Specify the location. A description of the preferred embodiment for accessing shared resources. A multiprocessor system with each processor in a system with multiple ports Although we have discussed this in the context of a system, the present invention allows each processor to access memory. have only a single port for accessing memory, or multiple ports for accessing memory. Equally applicable to uniprocessor systems with ports It should be obvious.

[Processor]

In the following sections, the processor 10 of the preferred embodiment will be described as follows: Describe in detail how requests will be managed. 4 vector load ports There is one Skashi load port and one instruction load port. Each port The ports have different mechanisms for issuing random responses.

6a and 6b, vector load ports 724, 726, 728 and 730 are vector registers for request signals, addresses, and their data. A storage access request tag directed to register 718 is attached. four vectors load ports exist, and each load port has two load ports at any given time. Support pending vector loads. A vector load port is a vector load port that Makes a variable size request for memory return to register 718. Each request group is It can consist of 1 to 64 individual requests. those two to each port Only one of the possible pending vector loads can issue a request at a time. Ru. However, due to the non-sequential nature of memory returns, the return on the second load It is also possible that all of the loads arrive before any of the returns of the first load. Can be determined. The vector load port control mechanism 732 ensures that the data is in the correct register. until all published data in that register is used. It must be ensured that it is not used.

As shown in Figure 7a, each memory return from the vector port and address The request tag is large enough to indicate the destination of the memory return.

i.e. put the data into which of two possible vector registers and which storage location of that vector register to use. request is Once issued, the vector load port control mechanism determines that the correct tag is Guaranteed to follow the address. The first component of that vector tag is the destination register identifier bits. The preferred embodiment includes the destination register as part of its tag. Instead of sending the register number, the processor simply registers one of two registers. Send a single pit to direct. That particular register number is established and can be different each time a load instruction is issued to a port. on the tag contains only a single destination register identifier, so at any given time can have only two loads pending. Tag collision within one port (same destination (register bit reuse) This is prevented by waiting for all responses. In addition, communication from each port Subsequent loads always use different destination register tag pits. each vector Multiple loafs for registers (but at different vector load ports) This can be avoided by waiting for the register load to complete.

The second part of the vector tag is the vector register element number. This is simply , which word of a given register should be updated by its stored data Specify.

The third and last part of the vector registers relates to the processor 10. A "cancel" indicator that effectively discards the load request. However, the memory system For example, a canceled request is, with very few exceptions, a canceled request. It is treated exactly the same as a new request. This exception is a canceled out-of-cluster request. is transferred within the cluster for performance reasons. request was submitted This ability to later cancel the request is provided by the processor 1 handling the request. 0 and a processor that handles parts and addresses of the arbitration node 44. 10 and part of the arbitration node 44, the time is critical. It also effectively reduces memory latency as it removes some handshaking. Tarasu. In this example, the cancellation bit is used for address validation and request Arbitration can overlap, processor 10 and arbitrator and are executed in parallel within the application node 44. That is, for example, The arbitration node 44 proceeds with the arbitration of storage requests and, at the same time, The address control logic within processor 10 indicates that the address of the storage request is a valid request. Determine whether it exists, that is, whether it is within the correct address range. process If the processor 10 determines that the address is out of range, the cancellation bit is set. and directs the request to the intra-cluster address.

In some operations, this undo function can be used to This is beneficial because it allows for With this software technique, when waiting for memory The interaction between Avoided by touching.

On preferred multiprocessor systems, programs should turn off mapping exceptions. and notes with no problem with random addresses (even addresses outside of that data space) The program can access prohibited data and its cancellation mechanism to ensure that it cannot be accessed.

Therefore, a program must access memory before examining the addresses it uses. The load instruction can be placed at the bottom of the loop instead of the top. (“bottom loading”).

Returning again to Figures 68 and 6b, the scalar request tag will be described. to memory A single scalar board 722 writes to S register 714 and L register 716. Provide a route for stored data. To ensure correct data ordering, the scara point Similar to vector ports, ports attach request tags to each storage request and address. do.

As shown in Figure 7b, this scalar request tag includes the destination register format and register Indicate the number. The first part of the scalar tag is in register format. This is L Identify register and S register responses. The second part of the scalar tag is a register It's a number. This indicates which register number (L or S) the return data should be placed in. Instruct whether to enter. Tag collisions result in only one outstanding reference per register, or Or, in the case of L registers, allow only one pending reference per register group. This is prevented by The third and final part of the scalar tag is programs to access data outside their permitted address spaces. It is a "cancelled" sign that prevents This mechanism is explained in various parts of this application. has been done.

As shown in FIGS. 6a and 6b, the scalar load boat 722 is connected to the L register 716. or receive a return directed to either S register 714. That Rita The L/S bit in the element tag indicates which destination level the data will be sent to when it returns from memory. Decide whether to write in register format.

When an S register is written, its request tag performs two functions. first, causes that register to be unreserved, thereby making the write address of the S register file form a space. When the L register is written, the tag performs the same two functions. Ru. However, L registers are reserved in blocks rather than individual registers. or be ignored.

The request tagging scheme outlined for the scalar boat response means that the L register load is Allows to be interrupted by high priority loads such as register loads. How to get out No ordering is imposed on the addresses, and no ordering is imposed on the input data stream. Since one set of register loads (e.g., L registers) is Treated as a background activity, giving high priority to the other set (S register) It can be treated as a ranked foreground activity. after that, With proper software assistance, the L registers can be used for block loads and stores. Can be treated as a software managed cache accessed by Ru.

Returning again to FIGS. 6a and 6b, the instruction request tag will be described. command and input The output port 20 outputs the command character 10 and the input/output buffer 7 from the memory. Give a route to 12. This instruction box is used to ensure correct instruction ordering. A boat is given a request tag along with its request and address, just like any other boat. do. The instruction request tag contains the buffer number for the response of that instruction, as shown in Figure 7c. and the element number within that buffer.

Similar to the vector boat register number, this instruction boat buffer number indicator is simply Encoded with one tag bit. This limits the number of pending buffer requests to two However, it simplifies the control and data paths involved in instruction loading. command tag The buffer waits for the oldest buffer fill to complete before allowing a new fill to begin. This can be avoided by Multiple pending loads to the same buffer are cached Prohibited by replacement policy. The tag encoding is specified when the return destination is an instruction cache. buffer 712 or input/output response buffer 710. Ru.

Each vector load boat 724, 726, 728 and 730 has a "back" boat. It maintains two sets of boats, one for each possible pending vector for that boat. This is for the torque register. When a return is returned from memory, its registers and and the back bit of the element number is set to 1, and the data is stored in that vector register. will be written to. However, the control mechanism 732 controls all of the previous elements, including the previous elements. Prevents the data from being used until the element in is returned from memory. this uses all elements of the vector register in order, even if the response returns out of order. I guarantee that.

When all elements of a vector register are returned from memory, the back bit on that side is marked as ``not-backed'' and its set of back bits is another load instruction. It becomes available for use. a vector whose tag indicates that the request was canceled And scalar load data is a non-signal NaN (Not a Number: ``r non-numeric'') is discarded and replaced. This is a preferred embodiment of the invention is accessed by a program that does not enable operand mapping exceptions? This is a method of protecting stored data. When the instruction data is returned from memory 14, Processor 10 uses the return tag to determine where to put it. use. Unlike data return, instruction return is different from data return, even in Matsubuto mode. For example, instruction mapping exceptions are always available, so do not use the cancel function.

To avoid the hazards associated with non-coherent storage systems, processors 10 and external interface boat 22, arbitration node 44 It is recommended to add information other than the tag.

This information is used to determine the ordering of requests and how they are handled by specific shared resources. Relevant when committed to be processed. In a preferred embodiment, the coffee This technique used to ensure currency is called a “data mark mechanism.” Ru. This data mark mechanism is disclosed in more detail in the original patent application.

[External interface port]

In addition to the requests issued by processor 10, the present invention It can also service resource requests from peripheral devices issued through port 22. can. External interface port 22 connects main memory 14 or global memory. Data fetched from register 16 is in a different order than it was requested. You can return with To achieve this non-sequential access of the present invention, external 10C 24 and SMS 28 related to interface port 22 are A request tag is attached to a resource request made through the face port 22.

FIG. 8 provides a detailed description of the external interface port 22 of the preferred embodiment. cormorant. The external interface port 22 is a cluster channel interface (CC I) A memory boat cable (not shown) that physically connects the packets of command and data words from the online memory 14; command The word is placed in the command buffer 350 and the data is placed in the data FIFO buffer. 360. If a command exists in the command buffer 350, The control logic 370 of the external interface port 22 is an arbitration node. 44 to request access to the memory 14. command word Data from the code count, command, address and mtag fields are each request in preparation for delivery to the arbitration node 44 upon recognition of the request. It is loaded into its own registers 382, 384, 386 and 388. It was done A new request tag and address must be computed for every word request. No.

For fetch requests, no data is sent, but the address and request tag are The command will be sent for a number of requests equal to the contents of its command word count field. be believed. The request tag starts with the lower 6 bits set to 0 and the correct number of tags. is calculated by incrementing the contents of that field until the field is sent. Similarly, request The addresses of each request are accepted starting with the address present in that command word. It is calculated by incrementing it each time it is recognized.

For store requests, the next word in data FIFO 360 contains the address, tag and and command information. The word count value is decremented after each request. Ru.

Once the word count value reaches 0, no further requests will be made. FIFO 350 and 360 terminate arbitration nodes 44 whenever possible. commands and commands on external interface port 22 to keep it busy. commands and data to ensure they are always available. used to hold

Fetched data returns from the shared resource via transfer registers 390. the The request tag issued when the request was made is returned with the data. transfer The output of register 390 is connected to main memory 14 . external interface The control line related to the data line of the cable connecting the baseboard 22 is a valid data line. It is inserted to indicate that the word is on the CC 1120 bus.

The I/O request tag precedes the data packet as it travels through the IOC 24. is sent with the command word. The tag sends its data to rOc 24. A 4-bit field that indicates which buffer receives the data, and the data Contains a 6-bit field that indicates the location within that buffer where the data is stored. . The 4-bit buffer selection field is decoded as shown in FIG. Ko The board 1011 directs data to one of two SMTC command buffers. Attach. The remaining six tag pits have their response data words assigned to either buffer. and the storage location in which it is stored. Code 1111 is l Not used by 0C24. It is the processor's instruction cache Reserved for touch operation. The IOC 24 uses the memory boat as its instruction cache. Sharing.

A 6-bit field is used for each individual data word request when the request is made. Generated by external interface boat. Requests are made in order starting with the lowest address. It will be done. According to FIG. 7d, the input/output request tag, i.e. the 6-bit word identifier and the 4-bit destination identifier are placed in the 10-bit tag field. This type The storage system carries the request along with each word of data. Returned to OC24. The request tag then sends that data word to the appropriate buffer. and is used by the IOC 24 to direct to the memory location of its buffer. Ru.

Tags are generated in sequential order when requests are made, so the memory location of the destination buffer Using tags to address data, in any arbitrary order This ensures that the buffers are loaded in the correct order, even if you return in the same order. follow Therefore, reading data from the buffer in consecutive order ensures that the data is delivered in the correct order. Guarantee that it will be returned to you.

[Arbitration node]

Returning again to Figures 5a and 5b, from a shared resource perspective (in this case path 5 0 and 52), each input request is sent to the request arbitration network 303. Therefore, arbitration is performed. A similar response arbitration network ports 306 - 315, 316 or 317 of their respective processor ports. Arbitrates response data back to . For input requests, waiting for input matrix 301 is passed by its request arbitration network 303. Holds up to 16 requests waiting to be completed. For responses returned, the data queue 305 whose response arbitration network 306 up to 64 responses waiting to return data to destination boat 315.316 or 317. Hold. Each of these queues 301 and 305 is to keep any control latency within the range when data flows between resources. It is strategically sized. Also, once the data is returned from storage, its The relevant tag is retrieved from the tag queue 304 and the data and tag are It is attached again before being loaded into matrix 305. Response via NRCA pathway 52 , the data and its related tags are already paired and the NRCA and and MRCA means handle related data and tags.

The request arbitration network 303 determines whether the request being input is usable. is requesting resources, has the highest priority, and is directed to storage. If it is determined that the address and data components of the request are and is routed to its correct storage. request arbitration network 303 indicates that the incoming request requires available resources and has the highest priority. and if it is determined that the request is directed to NRCA 46. address, data and tag components are placed on path 52 and its correct shared resources are source 12. The arbitration network 303 Note that this effectively controls access to interconnect traces 50 and 52. Must be. Subsequent arbitration networks along that request path controls access to other shared resources. Data is in a different order than requested may be returned to request boats 315, 316, and 317 in the order specified.

Arbitration node 44 receives a set of tags with each load address. and queue them for later reference. data returned from main memory Once the tags are attached to the corresponding data word, the data and Both tags are returned to the requesting boat. Processor 10 corrects the data. Use these tags to enter the new destination and make sure they are used in the correct order. We guarantee that.

[Main memory]

Returning again to Figures 5a and 5b, with respect to memory references, the switching of each memory Logic 400 determines whether that particular storage subordinate from a given arbitration node 44 Wait for subdivision catch on each storage subdivision to collect all input requests for the partition Contains matrix 401. Each arbitration node 44 stores its own information in each storage unit 14. has its own set of catch queues. Bank request arbitration network Bank 405 is a subdivision that has outstanding requests to that bank 403 each cycle. Arbitration occurs between that group of catch queues 401. request selected Then, the selected request is issued to its destination bank 403. The request is If it is a bank, addresses and data are issued to that bank. request is low If the bank is a bank, only that address will be issued to that bank. request is unloaded If flagged, the address and data are issued to that bank. B for the load and flags, their response data from bank 403. The response arbitration network 407 outputs the output response from its storage section. It is held in a hold queue 406 before being granted.

[Remote cluster adapter]

Next, FIG. 10 will be explained. In the case of NRCA means 46, input queue 610 or or 630 collects input requests. Input queue 610 is an external interface Holds a reference directed to. Arbitration network 612 Among that group of input queues 610 that have pending requests for external resources at a cycle Perform arbitration. Once a request is selected, the selected request is response, data, and its request tag and additional information placed on path 58 ( (see Figure 70), along with a new tag called a cluster tag consisting of Issued to the previous resource. Input queue 630 may include an interrupt mechanism, global registers or holds a reference directed to the 5ETN register. arbitration net 7 - resource 634 requests pending requests to that resource 620, 632 or 633 each cycle. Arbitration is performed between that group of input queues 630 that have requests. So If a request for is granted, it is issued to its destination resource. data is in the global register from the SETN register 633 or S ETN register 632 to the arbitration node 44 If returned, the high priority request is sent to its output arbitration network 6 15, thereby returning the output route to that arbitration node. It will be rearranged.

Data and tags returning from MRCA means 48 via boat 58 are sent to queue 6 Received on 14th. Data from global register 633 or 5ETN register 632 The data is pre-arbitrated and immediately sent along with the associated tags. placed on the return path 52. At each clock cycle, the response arbitration The communication network 615 provides an architecture for the return data path of the boat 52 or 56. Perform bitration. Data queue 614, global register 633 or 5E The appropriate data is selected from the TN register 632 and placed in the appropriate boat 52 or 56. will be returned to.

Referring now to FIGS. 11g and 11b, the MRCA means 48 6 boats 5 through which store and load operations from other clusters are received There are 20. Each of these boats has a receive queue 500 . tag bag response queue 504 and boat control logic 501 and 503 It consists of Each boat operates independently from all other boats. another group All operations arriving at a boat from a raster are returned to that cluster. this is, Includes store and load. MRCA means 48 queuing and arbitration (506, 507, 508, 509, 510, 511 and 512) are essentially In addition, the queue of arbitration node 44 and the arbitration 301, 302, 303, 304, 305, 306 and 307), respectively. works.

When an operation arrives at MRCA port 520 from an external cluster, the data, Address and tag information is in a receive queue 500 that is 64 locations deep. will be written to. After a valid operation is written to this receive queue 500, the board The control logic 501 determines whether the operation can be passed to the MRCA means 48. Perform resource checks to There are three resources that are examined.

The first resource checked concerns the availability of tags. The operation is passed to MRCA means 48 When the request is received, the original cluster tag that arrived with the request is written to the tag buffer 502. A new 8-bit request tag is generated by tag generator 501. Ru. The address of the memory location in tag buffer 502 where the original tag is written is: That becomes the new request tag. This request tag must be unique, so new Once a new cluster tag is generated and passed to the MRCA means 48, it MRCA means 48'b1 may not be reused until returned to its boat. stomach. Implementation of this logic requires that request tags must be generated in order. . If the next request tag to be generated is still pending in the MRCA means 48, then The boat cannot issue its next operation from the receive queue 500. . Tag buffer 502 is 256 locations deep.

A second resource that must be checked before an operation can be issued to the MRCA means 48 relates to the availability of storage locations in return queue 504. MRCA means 48 completely implements a mechanism for causing arbitration node 44 to maintain return operation. Since the arbitration node 44 does not have many There is always a memory location in the return queue 504 to store any operations that return from must be guaranteed to exist.

This return queue 504 is 128 locations deep. Waiting for return Once all of the storage locations in matrix 504 have been allocated, the storage locations are ready for use. , no other action can be issued to the MRCA means 48.

The boat queue 506 within the MRCA means 48 receives operations from the receive queue 500. This is the third resource that must be examined before it can be issued. boat control logic 501 maintains the current total number of operations in a boat queue 506. waiting for boat Once column 506 is full, port control logic 501 indicates that a storage location is available. Issuance must be suppressed until then.

When the operation returns from the MRCA means 48, the data, if present, is Stored directly in turn queue 504. The request tag returned with that action is , to access its tag buffer and recover the original cluster tag 503. used. This original cluster tag is extracted from the tag buffer 502 and its It is stored in return queue 504 along with the data. Then the port control logic 501 performs a resource check on the cluster at the far end of its intercluster path 520. . if the far-end cluster has storage available for its receive queue , return queue 504 is not loaded. If there is no storage space, the queue Data is retained until a storage location becomes available.

Although a description of a preferred embodiment has been presented, various modifications may be made without departing from the spirit of the invention. It is assumed that changes may be made. Accordingly, the scope of the invention is limited to the description of the preferred embodiment. It is intended that the scope of the invention, rather than the scope of the invention, be defined by the claims appended hereto.

Fig, 2 Fig, 3a Pole 3b Fig, 5 Fig, Ila Summary book For non-sequential access to shared resources (12) in multiple requester systems The method and apparatus for Use tags. In its simplest form, this tag contains another tag for directional information. to a location in the buffer to locate the tag, or emit a response related to that tag. Switching logic to a location in a buffer or processor (register) to direct the principles. For example, to load data from memory (14), It will be necessary for the questa to provide the request signal, address and request tag.

The request signal checks the validity of its address and request tag. The address is Specifies the storage location in memory (14) of the requested data. The request tag is specifies the location to put the data when it is returned to its processor . The requester's switching logic (44) determines whether the requestor's switching logic (44) A tag queue for storing tags and individual request tags from that tag queue A logical means for relating a resource response to a resource response and its individual request tags. and means for returning the information to the requester. Switches related to memory (14) The routing logic (400) includes control logic for routing requests to and from shared resources. , the logic for handling multiple decision requests and the final data entity being requested. and logic for storing or retrieving the information.

international search report

Claims (20)

[Claims] 1. Non-sequential shared resource access in multiprocessors with multiple processors , wherein the shared resources include main memory, global registers, and the device is operable with each of the processors; a request for generating multiple resource requests from said processor; generating means, each of said resource requests having an address and address of the requested shared resource; , a request tag that specifies the storage location within the processor to which the resource request should be returned; the request generation means, which operably connected to the request generating means, the time at which the resource request was generated; for in turn receiving the resource request and routing the resource request to the shared resource; switching means, wherein said switching means a tag queue for storing the requested tag; logic means for associating each request tag from the tag queue with a resource response; and means for returning the resource request and each request tag to the processor. the switching means, operatively connected to the switching means and the shared resource; service the resource request when the requested resource becomes available; means for returning said resource responses to said switching means in the order in which they are serviced; It includes Thereby, the resource responses are out of order with respect to the time order in which the resource requests were issued. A device characterized in that it can be returned at 2. 2. The apparatus of claim 1, wherein the switching means further comprises: before being routed to said shared resource in a given clock cycle of the processor system. Arbitration node means for arbitrating between storage resource requests A device comprising: 3. 3. The apparatus of claim 2, further comprising logical means for associating each of said request tags. further receives a cancellation instruction from the request generation means, and responds to the cancellation instruction. in response to the resource request prior to the time the resource request was routed to the shared resource. Apparatus characterized in that it includes cancellation logic means for canceling the request. 4. 4. The apparatus of claim 3, wherein said cancellation logic means responds to said resource request. to indicate that the resource request has been canceled by returning a non-numeric value in response to the request. Featured device. 5. 2. The apparatus of claim 1, wherein the switching means further comprises: characterized in that it includes an address verification means for verifying the validity of the requested address. equipment. 6. 6. The apparatus of claim 5, further comprising logical means for associating each of said request tags. further receives a cancellation instruction from the request generation means, and responds to the cancellation instruction. in response to the resource request prior to the time the resource request was routed to the shared resource. Apparatus characterized in that it includes cancellation logic means for canceling the request. 7. Non-sequential shared resource access in multiprocessors with multiple requesters , wherein the requester includes a processor and an external interface. The shared resources include main memory, global registers, and and an interrupt mechanism, the device comprising: operably connected to each requester and receiving multiple resource requests from said requester; a request generation means for generating a resource request, each of the resource requests being requested; address of the shared resource, a request tag that specifies the storage location within the requester where the resource request should be returned; the request generation means, which operably connected to the request generating means, the time at which the resource request was generated; for in turn receiving the resource request and routing the resource request to the shared resource; switching means, wherein said switching means a tag queue for storing the requested tag; logical means for associating each request tag from said tag queue with a resource response; for returning the resource request and each request tag to the requester, including: said switching means, said switching means comprising: operatively connected to the switching means and the shared resource; service the resource request when the requested resource becomes available; means for returning said resource responses to said switching means in the order in which they are serviced; It includes Thereby, the resource responses are out of order with respect to the time order in which the resource requests were issued. A device characterized in that it can be returned at 8. 8. The apparatus of claim 7, wherein the switching means further comprises: before being routed to said shared resource in a given clock cycle of the processor system. Arbitration node means for arbitrating between storage resource requests , and address verification means for verifying the validity of the address of the resource request. A device comprising: 9. 9. The apparatus of claim 8, further comprising logical means for associating each of said request tags. further receives a cancellation instruction from the request generation means, and responds to the cancellation instruction. in response to the resource request prior to the time the resource request was routed to the shared resource. Apparatus characterized in that it includes cancellation logic means for canceling the request. 10. 8. The apparatus of claim 7, wherein the requester and the shared resource are multiple requests. raster-organized, and said switching means further comprises a remote cluster. receives a resource request from a requester in that cluster directed to a shared resource in that cluster, and forwarding these requests to remote cluster adapter means of said remote cluster; receives a resource response from a cluster and is directed to a shared resource of said cluster; receiving a resource request from a remote cluster adapter means of said remote cluster; a remote cluster associated with each cluster for returning the resource response to the remote cluster; Apparatus characterized in that it includes star adapter means. 11. A multiprocessor system in which queuing and queuing occur between one or more requesters. and means for establishing a pipeline; a means for making requests to resources; such that the requests may be serviced in a different order than the time order in which the requests were made; and one or more resource means for responding to said request. processor system. 12. Accessing shared resources in multiprocessor systems with multiple processors A method for accessing a shared resource such as main memory, global registers, etc. and an interrupt mechanism, wherein the method includes a generating resource requests, each of said resource requests comprising: the address of the requested shared resource, and a request tag specifying a storage location within the processor to which the resource request is to be returned; the step of generating the request; to a switching mechanism related to the shared resource in the time order in which the resource request was issued. presenting the resource request; placing said request tag related to said resource request in a tag queue of said switching means; storing and making the requested resource available to generate a resource response; servicing the resource requests when the resource requests are serviced; and the order in which the resource requests are serviced. returning the resource response to the switching means at associating each of the request tags from the tag queue with the resource response; returning the resource request and each request tag to the processor; Thereby, the resource responses are out of order with respect to the time order in which the resource requests were issued. A method characterized in that the method can be returned by: 13. 13. The method of claim 12, wherein servicing the resource request comprises: routing to the shared resource at a predetermined clock cycle of the multiprocessor system; arbitrating between the resource requests determined; and verifying the validity of the address of the resource request. . 14. 14. The method of claim 13, wherein the step of servicing the resource request further comprises: , inspecting a cancellation instruction associated with the resource request and responding to the cancellation instruction. the resource request prior to the time the resource request was routed to the shared resource. A method characterized in that it includes a step of erasing. 15. 15. The method of claim 14, wherein the step of canceling the resource request includes the step of canceling the resource request. that the resource request has been canceled by returning a non-numeric value in response to a cancellation instruction; A method characterized by instructing. 16. Accessing shared resources in a multi-requester system with multiple requesters A method for accessing a processor and an external interface, the requester comprising: The shared resources include main memory, global memory, and register and an interrupt mechanism, the method comprising: generating a resource request from one of said requestors; Each is the address of the requested shared resource, and a request tag specifying a storage location within the requester to which the resource request is to be returned; the step of generating the request; to a switching mechanism related to the shared resource in the time order in which the resource request was issued. presenting the resource request; placing said request tag related to said resource request in a tag queue of said switching means; storing and making the requested resource available to generate a resource response; servicing the resource requests when the resource requests are serviced; and the order in which the resource requests are serviced. returning the resource response to the switching means at associating each of the request tags from the tag queue with the resource response; returning the resource request and each request tag to the processor; Thereby, the resource responses are out of order with respect to the time order in which the resource requests were issued. A method characterized in that the method can be returned by: 17. 17. The method of claim 16, wherein servicing the resource request comprises: routing to the shared resource at a predetermined clock cycle of the multiprocessor system; arbitrating between the resource requests determined; and verifying the validity of the address of the resource request. . 18. 18. The method of claim 17, wherein the step of servicing the resource request further comprises: , inspecting a cancellation instruction associated with the resource request and responding to the cancellation instruction. the resource request prior to the time the resource request was routed to the shared resource. A method characterized in that it includes a step of erasing. 19. 17. The method of claim 16, wherein the requester and the shared resource being organized into a cluster and servicing the resource requests further comprising: A remote resource request from a requester of said cluster directed to a shared resource of a remote cluster. and forwarding the remote resource request to a remote cluster and transmitting the remote resource request to the remote cluster. 12. A method comprising: receiving a resource response from a host. 20. 20. The method of claim 19, wherein the step of servicing the resource request further comprises: To, receiving a remote resource request from the remote cluster directed to a shared resource of the cluster; and returning the resource response to the remote cluster for the remote request. A method characterized by comprising: