Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2000-08-30
2004-08-03
Vital, Pierre M. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S005000, C711S151000, C711S159000
Reexamination Certificate
active
06772300
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems; more particularly, the present invention relates to executing memory transactions using a linked list.
BACKGROUND
The efficiency of accessing large arrays of a memory device can be improved by enabling out of order accesses of the memory. Typically, larger memory arrays are divided into banks. A bank is a section of memory wherein an access is completed before another access to the same bank can be started. In particular, whenever two transactions access the same bank, the second transaction must wait the full memory access time of the first transaction before it can begin. However, an access to one bank does not delay access to other banks within the memory device. As a result, if two transactions are accessing different banks, a second transaction may begin as soon as it has been received at the memory device. This hides some of the memory access time.
Therefore, in order to further improve access efficiency, transactions to different banks should be done out of order. For example, if three memory transaction are received, the first two to the same bank and the third to a different bank. The first transaction is started but the second is held up because it is to the same bank. Thus, if the transactions were executed in order, the third transaction would also be held up. However, if the transactions are enabled to execute out of order, the third transaction could be started as soon as it was received.
To allow out of order executions, control logic must store the transactions that are stalled and keep track of these stalled transactions until they can be executed. A simple approach is to use a set of first-in-first-out (FIFO) buffers. Each FIFO within the controller may hold the transactions for one bank. Subsequently, an arbiter may select which transaction in a non-empty FIFO will next be executed.
The problem with the above memory mapping method is the number and size of the FIFOs. For a very large memory array, there is typically a large number of banks. Thus, for maximum performance, a FIFO for each bank is required. For instance, a typical memory may be divided into 32 read banks and 4 write banks, resulting in 36 FIFOs. The size of each of the 36 FIFOs is dependent on the number of transactions that may be received. In some applications, the maximum number of transaction that can be handled is 64. Since it is possible for all 64 transactions to go to the same bank, each bank must be capable of storing 64 transactions at one time. As a result, 36 FIFOs requiring 64 storage locations are often required. Providing this amount of storage space for the execution of out of order transactions results in an inefficient use of resources within a computer system. Therefore, a more efficient method and apparatus handling out of order memory transactions is desired.
REFERENCES:
patent: 4794526 (1988-12-01), May et al.
patent: 5179685 (1993-01-01), Nojiri
patent: 5251303 (1993-10-01), Fogg et al.
patent: 5995967 (1999-11-01), Iacobovici et al.
patent: 6137807 (2000-10-01), Rusu et al.
patent: 6247107 (2001-06-01), Christie
patent: 6317803 (2001-11-01), Rasmussen et al.
patent: 6434641 (2002-08-01), Haupt et al.
Blakely , Sokoloff, Taylor & Zafman LLP
Vital Pierre M.
LandOfFree
Method and apparatus for managing out of order memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for managing out of order memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing out of order memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269948