Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1998-12-22
2001-07-10
Etienne, Ario (Department: 2155)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S036000, C710S039000, C710S112000, C710S120000
Reexamination Certificate
active
06260099
ABSTRACT:
CROSS-REFERENCE TO OTHER PATENT APPLICATIONS
The following co-pending patent application of common assignee contains some common disclosure:
“Queueing Architecture and Control System For Data Processing System Having Independently-Operative Data and Address Interfaces”, Ser. No. 09/096,822, filed on Jun. 12, 1998, which is incorporated herein by reference in its entirety.
“Transfer Request Selection Method And Apparatus For Symmetrical Multiprocessor Systems”, Ser. No. 09/218,210, filed Dec. 22, 1998, concurrently herewith, which is incorporated herein by reference in its entirety.
FIELD OF THE INVENTION
This invention relates generally to transfer request priority management in multiprocessor data processing systems, and more particularly to a system and method for managing the flow of data transfer requests from requesting devices to associated data transfer interconnection circuitry.
BACKGROUND OF THE INVENTION
Large-scale data processing systems typically utilize a tremendous amount of memory. This is particularly true in multiprocessing systems where multiple processing units are implemented. There are several memory methodologies known in the art that provide for efficient use of memory in such multiprocessing environments. One such memory methodology is a distributed memory where each processor has access to its own dedicated memory, and access to another processor's memory involves sending messages via an inter-processor network. While distributed memory structures avoid problems of contention for memory and can be implemented relatively inexpensively, it is usually slower than other memory methodologies, such as shared memory systems.
Shared memory is used in a parallel or multiprocessing system, and can be accessed by more than one processor. The shared memory is connected to the multiple processing units—typically accomplished using a shared bus or network. Large-scale shared memories may be designed to cooperate with local cache memories associated with each processor in the system. Cache coherency protocols ensure that one processor's cached copy of a shared memory location is invalidated when another processor writes to that location.
In order to initiate and establish transfers of data in such a system, a device desiring a data transfer issues a data transfer request. For example, a data transfer request may be issued by a processor to the main memory to fetch a data segment from the main memory, which is thereafter supplied by the main memory to the processor's local memory or cache memory. It is possible that any of the processors, input/output devices and memory devices may be the source or the destination of a data transfer. Managing the data transfer requests in a system where there may be multiple request sources and multiple request destinations therefore becomes very important. Conservatively managing the transfer of these requests may lead to a reduction in system throughput, while mismanagement to obtain greater throughput may lead to memory access conflicts.
For example, where the number of request sources is unequal to the number of request destinations, it is possible that each of the request sources has issued an active data transfer request. Where the number of destinations is less than the number of active data transfer requests, this implies that some of the destinations are being targeted by multiple data transfer requests. A manner of fairly distributing these data transfer requests is required.
Further, because such a system may include multiple destinations for the data transfer requests, such as multiple memory blocks or other local memories, it is possible that a particular request source may issue multiple data transfer requests each identifying a different destination for the request. If these data transfer requests are allowed to be issued simultaneously to the request destination, such as a single-port memory device, indeterminate results can occur. It is therefore important to properly manage the flow of the data transfer requests, taking into account the manner in which the data targeted by the data transfer request is to be routed from the data source to the data destination.
Finally, while managing the flow of data transfer requests, it is also important to maximize system data throughput. To do so requires maximizing the throughput of the data transfer requests. To allow only one data transfer request to be issued at a time would severely limit the system's throughput where data transfer requests between multiple sources and destinations are pending.
Therefore, it would be desirable to provide a system and method that maximizes data throughput, while properly and fairly managing concurrently-pending data transfer requests. The present invention provides a multi-level queuing architecture to manage the data transfer requests, while allowing data transfers to occur in parallel in accordance with rules established by the multi-level queuing architecture. The present invention offers these and other advantages over the prior art, and provides a solution to the shortcomings of the prior art.
SUMMARY OF THE INVENTION
The present invention relates to a system and method for managing the flow of data transfer requests from requesting devices to associated data transfer interconnection circuitry in a data processing system.
In accordance with one embodiment of the invention, a method is provided for controlling transfers of data between devices in a data processing system. Each of the devices includes both a designated data input queue to temporarily store data being transferred from the device, and a designated data output queue to temporarily store data that is output from other devices for receipt by the device. The transfer of data is initiated via data transfer requests that identify the data input queue and data output queue for which the data is to be transferred. The method includes issuing data transfer requests from one or more of the devices, and queuing each of the data transfer requests issued from the one or more devices. The data transfer requests that identify like data input queues are commonly queued in first distinct queues. Each of the data transfer requests from each of the first distinct queues are transferred to second distinct queues, where each of the second distinct queues receives and queues only those data transfer requests identifying like data output queues. A control signal set is generated for each of the data transfer requests that are output from each of the second distinct queues, and each control signal set identifies the data input queue and the data output queue between which the data is to be transferred. The data from the identified data input queues is transferred to the identified data output queues in response to the corresponding control signal sets.
In accordance with another embodiment of the invention, a multi-level priority control system for managing data transfer requests in a data processing system is provided. The data processing system includes a plurality of data request sources to generate the data transfer requests, and a data interconnect module to establish data transfer connections between identified ones of a plurality of data input queues and a plurality of data output queues. Each of the data transfer requests includes an identification of one of the data input queues and one of the data output queues to which the data transfer is to be effected. The control system includes a first request queue stage having a plurality of input request queues coupled to respective ones of the data request sources. Each of the input request queues receives and temporarily stores corresponding data transfer requests. A second request queue stage is provided, which has a plurality of output request queues, each of which is coupled to each one of the input request queues to receive and temporarily store those of the data transfer requests that identify a particular one of the data output queues as a destination for the data transfer. The control system further includes a contro
DePenning James L.
Gilbertson Roger L.
Altera Law Group
Etienne Ario
Johnson Charles A.
Starr Mark T.
Unisys Corporation
LandOfFree
Multi-level priority control system and method for managing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-level priority control system and method for managing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-level priority control system and method for managing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448241