Electrical computers and digital data processing systems: input/ – Input/output data processing – Direct memory accessing
Reexamination Certificate
2000-12-14
2004-11-16
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Direct memory accessing
C710S023000, C710S028000
Reexamination Certificate
active
06820142
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the field of Direct Memory Access (DMA) transactions, and more particularly to a deterministic schedule for DMA accesses via tokens.
BACKGROUND INFORMATION
One widely accepted system architecture for computing systems has been the Symmetric Multi-Processing (SMP) architecture. Symmetric Multi-Processing (SMP) computer architectures are known in the art as overcoming the limitations of single or uniprocessors in terms of processing speed and transaction throughput, among other things. Typically, commercially available SMP systems are generally “shared memory” systems, characterized in that multiple processing elements on a bus, or a plurality of busses, share a single global memory. In an SMP system, all memory is uniformly accessible to each processing element, which simplifies the task of dynamic load distribution. Processing of complex tasks can be distributed among various processing elements in the multiprocessing element system while data used in the processing is substantially equally available to each of the processing elements undertaking any portion of the complex task. Similarly, programmers writing code for typical shared memory SMP systems do not need to be concerned with issues of data partitioning, as each of the processing elements has access to and shares the same, consistent global memory.
Each processing element in the SMP computer architecture may comprise a Direct Memory Access (DMA) controller. The DMA controller handles DMA transactions between the shared system memory and the corresponding processing element in the multiprocessing element system. That is, the DMA controller allows blocks of information to be exchanged between the corresponding processing element in the multiprocessing element system and the shared system memory. Typically, the processing elements in the multiprocessing element system may initiate a DMA transfer by having the respective DMA controller issue a DMA request to the shared system memory. The shared system memory typically comprises an arbitration mechanism to arbitrate among the DMA requests issued by the processing elements in the multiprocessing element system. Once the arbitration mechanism determines which DMA channel, i.e., channel coupling the DMA controller and the shared system memory, is to be serviced, the particular processing element associated with that DMA channel gains access, commonly referred to as a DMA access, to the system memory to initiate the DMA transfer.
Unfortunately, an arbitration mechanism is required to arbitrate among the DMA requests issued by the DMA controllers of the processing elements in the multiprocessing element system.
It would therefore be desirable to develop an SMP architecture that eliminates the necessity of an arbitration mechanism to arbitrate among the DMA requests issued by the DMA controllers of the processing elements in the SMP system. It would further be desirable to develop a deterministic schedule for DMA accesses via the issuance of tokens and hence improve utilization of the data transfer bus.
SUMMARY
The problems outlined above may at least in part be solved in some embodiments by a master controller in a shared memory configured to issue and receive tokens that grant the right to access the shared memory at a particular deterministic point in time for a selected duration of time, e.g., clock cycle. Master controller may be configured to issue tokens to Direct Memory Access (DMA) controllers of processing elements and a system I/O controller in a Symmetric Multi-Processing (SMP) system. Each token may be unique by granting the processing element or system I/O controller whose DMA controller possesses the respective token the right to access the shared memory at a unique designated time and lasting a designated duration of time. By master controller allocating unique tokens among DMA controllers, a deterministic schedule to access the shared memory may be achieved without the arbitration mechanism of the prior art.
In one embodiment, a system for accessing shared memory comprises a plurality of processing elements where each processing element comprises a DMA controller. The system further comprises a shared memory coupled to each of the plurality of processing elements where the shared memory comprises a master controller. The master controller may then issue tokens to DMA controllers to grant the right for the associated processing elements to access the shared memory at deterministic points in time. Each token issued by the master controller grants access to the shared memory for a particular duration of time at a unique deterministic point in time. A processing element may access the shared memory upon the associated DMA controller relinquishing to the master controller the token that grants the right to access the shared memory at that particular time. The master controller may then reissue the relinquished token back to the DMA controller associated with the processing element that accessed the shared memory if at the future designated time, e.g., 128 ns from the completion of the access to the shared memory, there does not exist a higher prioritized request, e.g., refresh the shared memory, to access the shared memory at that future designated time. The reissued token grants the right to the processing element associated with the DMA controller to access the shared memory at the future designated time, e.g., 128 ns from the completion of the access to the shared memory by the processing element. However, if there exists a higher prioritized request at the future designated time, then the master controller may not reissue the relinquished token back to the DMA controller associated with the processing element that accessed the shared memory.
In another embodiment of the present invention, the shared memory may comprise a plurality of memory banks resulting in the possibility of a bank conflict. A bank conflict may occur when the DMA controller requests to read from or write to a particular memory bank more than once during the designated period of time of the access to the shared memory. DMA controllers may comprise a queue comprising a plurality of memory line addresses to be accessed by the associated processing element during the designated period of time. A portion of the memory line addresses may comprise one or more bits that indicate a particular memory bank that includes a line of a page associated with the memory line address. DMA controllers may further comprise a detector to detect a bank conflict by examining the memory bank indicator portion of the memory line addresses to determine if there exists a bank conflict. A bank conflict may be detected by the detector by detecting two or more memory addresses with the same memory bank indicator. The detector of the DMA controllers may be configured to resolve the bank conflicts by not issuing two or more requests to read from or write to the same memory bank during the designated period of access.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.
REFERENCES:
patent: 4658247 (1987-04-01), Gharachorloo
patent: 5068849 (1991-11-01), Tanaka
patent: 5734926 (1998-03-01), Feeley et al.
patent: 6011798 (2000-01-01), McAlpine
patent: 6026443 (2000-02-01), Oskouy et al.
patent: 6029225 (2000-02-01), McGehearty et al.
patent: 6070194 (2000-05-01), Yu et al.
patent: 6275877 (2001-08-01), Duda
patent: 6393512 (2002-05-01), Chen et al.
Hofstee Harm Peter
Nair Ravi
Wellman John-David
Gaffin Jeffrey
International Business Machines - Corporation
Salys Casimer K.
Schneider Joshua D
Voigt, Jr. Robert A.
LandOfFree
Token based DMA does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Token based DMA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Token based DMA will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292898