Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-07-21
2003-11-04
Peikari, B. James (Department: 2186)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S052000, C710S054000, C365S189050
Reexamination Certificate
active
06643718
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the design of a FIFO queue and more particularly to the design of the control of order dependency between items of a multiple FIFO queue structure.
BACKGROUND OF THE INVENTION
In a highly integrated system, a memory subsystem may be accessed by multiple devices and working in a multitasking mode. Under this circumstance, how to gain maximum data bandwidth to enhance system performance and meet latency requirement becomes an important issue. In the field of memory controller design, some apparatus that optimizes the utilization of a DRAM bus has been developed and implemented. At the time when a memory controller receives a memory access request, correct memory commands must be generated based on current SDRAM internal status.
In a memory controller circuit, there are typically two separate queues for storing different memory commands. One is pre-charge/activate command queue and the other is read/write command queue. Memory commands are divided into pre-charge/activate commands and read/write commands that are pushed into the pre-charge/active command queue or the read/write command queue respectively. In general, read/write commands include memory read and memory write commands that are concerned with data transfer. Pre-charge/activate commands are the other SDRAM commands for the preliminary operations before the actual read/write preliminaries. When a pointed command in the queues satisfies all the required conditions, this command will be issued onto DRAM bus at the earliest allowable time.
Because pre-charge/active commands are not related to data transfer, they can be issued during the interval that the data bus is busy but the command bus is free. In other words, pre-charge/activate commands can be overlapped with read/write commands. Therefore, both pre-charge/activate command and read/write command queues are used to issue pipelined memory commands to gain maximum bus utilization. However, because pre-charge/active commands and read/write commands are popped from different queues, pre-charge/activate commands of a corresponding read/write command may be issued too early to prevent the read/write command from working correctly if the two queues are not controlled properly to ensure the order dependency between commands.
For example,
FIG. 3
shows the operation of three cycles of accessing a memory bank A. Cycle
1
is a hit write cycle on bank A, cycle
2
is a hit read cycle on bank A and cycle
3
is a miss write cycle on bank A. After a command is generated, the read/write queue (foreground queue FQ) and the pre-charge/activate queue (background queue BQ) are formed as shown in FIG.
3
. The cycle
3
which is a miss write cycle is decoded into pre-charge (PRE) bank A command, activate (ACT) bank A command and write (WTT) bank A command. PRE bank A and ACT bank A commands are pushed into BQ level
1
while the corresponding WTT bank A command is pushed into FQ level
3
because the write bank A command of cycle
1
and the read bank A command of cycle
2
are already in the levels
1
and
2
of FQ. In this case, obviously, the PRE band A and ACT bank A commands of BQ level
1
can not be issued before the read bank A command in FQ level
2
(cycle
2
) is finished. Otherwise, the read command of cycle
2
will read data from an undesired page which is associated with the write bank A command of cycle
3
.
In the above example, if the order dependency is not considered carefully in designing the queues, PRE A and ACT A may be issued right after the completion of FQ level
1
because all the conditions for BQ level
1
within its own queue are satisfied at that moment. Therefore, before issuing a background command, order dependency checking for read/write commands is required to ensure that memory access can function properly at the desired memory location.
The command queue discussed above is usually implemented by a first-in-first-out (FIFO) queue structure as shown in FIG.
1
. The basic operations for a FIFO are push and pop operations that insert incoming items into the FIFO and consume outgoing items from the FIFO respectively. In general, a 2-way FIFO queue structure is composed of two FIFOs and the operations of each FIFO queue work independently and concurrently with respect to the other FIFO queue. Although a 2-way FIFO structure as shown in
FIG. 2
provides higher performance because of the concurrent operations, it is difficult to maintain the order dependency between items in the two different FIFOs.
SUMMARY OF THE INVENTION
This invention has been made to overcome the above-mentioned difficulty in optimizing the performance and controlling the order dependency of items in a multiple FIFO queue structure. The primary object of the invention is to provide a barrier control scheme for controlling the order dependency of items between two FIFO queues with optimal parallelism. Accordingly, the barrier control scheme comprises a cycle ID generator, a barrier bit/barrier ID generator and a cycle ID and barrier ID comparator.
The cycle ID generator generates a sequential number as the cycle ID for each incoming item of the multiple FIFOs. For an incoming item to be inserted into a first FIFO, the item is also given a barrier bit and a barrier ID. The barrier bit/barrier ID generator determines the barrier bit and the barrier ID of the incoming item inserted into the first FIFO. If the incoming item is dependent on items of a second FIFO, the barrier bit is set to 1 and the barrier ID is generated according to the order dependency. The cycle ID and barrier ID comparator compares the barrier ID of an outgoing item of the first FIFO with the cycle ID of the outgoing item of the second FIFO to determine if the outgoing item of the first FIFO should be blocked or not.
It is also an object of the invention to provide a method of generating the barrier bit and the barrier ID of an incoming item of the first FIFO based on order dependency of the incoming item with respect to items in the second FIFO. According to the invention, the barrier bit is set to 0 and the barrier ID is in a don't care condition if there is no dependency. Otherwise, the barrier bit is set to 1 and the barrier ID is generated according to how the incoming item is dependent on the items in the second FIFO. In the present invention, each FIFO has a PUSH pointer. In the second FIFO, the latest item on which the incoming item of the first FIFO is dependent is the one nearest to the PUSH pointer. Based on the location of the PUSH pointer and the order dependency, the invention provides a method which can be implemented by a combinational logic circuit to generate the barrier ID.
It is yet another object of the invention to provide a top-down decision tree for the cycle ID and barrier ID comparator to compare a cycle ID and a barrier ID. To avoid ambiguity in comparison, the cycle ID of this invention is given one bit more than the number of bits required in representing the maximum number of items in the multiple FIFOs. The top-down decision tree is formed by comparing a cycle ID with a barrier ID bit by bit from the highest bit to the lowest bit.
According to the order of the cycle ID and the barrier ID, the decision tree comprises a plurality of leaf nodes and non-leaf nodes. A non-leaf node indicates a comparison condition and a leaf node indicates a comparison result. If the cycle ID is greater (or later) than the barrier ID, a leaf node shows a true result. Otherwise, a leaf node shows a false result. By traveling through the top-down decision tree, the cycle ID and barrier ID comparator can determine if an outgoing item in the first FIFO should be blocked or not based on whether the leaf node is false or true.
REFERENCES:
patent: 4852127 (1989-07-01), Fraser et al.
Chang Hui-Neng
Chen Chao-Yu
Chu Sui-His
Peikari B. James
Silicon Integrated Systems Corporation
LandOfFree
Method and apparatus for controlling order dependency of... 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 controlling order dependency of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling order dependency of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3184614