DRAM access command queuing structure

[0001] This invention relates to the field of computer memory access, with particular reference to command queuing methods and structures for DRAM memory access.

[0002] A number of functional units are utilized by a network processor to manage the flow of data. Among these are memory interfaces to provide memory arbitration; state machines to provide functionality of processing command messages; and receive, transmit and dispatch controllers, just to name a few. A memory interface attempts to provide buffer management and data movement at media speed. To eliminate the memory access bandwidth bottleneck, the main function of the memory interface is to provide an efficient memory access scheme while meeting the requirements of sustained data throughput at the required data rate at the memory controller interface to the memory device.

[0003] Network traffic management requires hardware implementation for scheduling the delivery of network packets, and for traffic shaping. For this, a computer employs a scheduler which is a computer program designed to perform advanced scheduling algorithms to control functions, such as network packet scheduling, traffic shaping, and initiation and termination of specified tasks. Hardware schedulers contain a plurality of network interface and switch ports, an internal memory for DRAM write access command queues as well as buffers for received packets, an internal memory for DRAM read access command queues and finite state machines for memory management. The system utilizes external SRAM and DRAM memory devices to store control blocks of scheduling elements. It is necessary to be able to quickly and accurately execute searches for programs with complex flow patterns.

[0004] A number of features are found in related art devices, but none of these devices embody the combination of features that are found in the present invention. For example, some conventional DRAM access arbiters consider only one access request across several memory banks at a time, thereby leading to low memory bandwidth utilization. Other DRAM access arbiters employ schemes to increase the memory access bandwidth, but access command queues are global queuing structures which contain access requests to all the memory banks of the memory device.

[0005] Neither of these schemes imposes any limitation on how many access requests for the same memory bank can be presented in the command queues. The command queues can be populated with access requests to the same memory bank. Command queues are limited resources, such that new access requests for different memory banks cannot be inserted into the command queues while these queues are full. This problem results in low memory bandwidth utilization for a period of time.

[0006] In some applications where a “cut-and-paste” processing model is used, the “paste” of a packet header also contributes to the write accesses traffic to the memory. In this case, flow control on the regular write access traffic is required in order to guarantee that the “paste” operation of packet data is given the highest priority to access the memory devices.

[0007] One of the objects of the present invention is to solve the problems associated with the above schemes. This is achieved by use of one or more arbiters to maximize the memory bandwidth available for the read and the write operations by avoiding consecutive accesses to the same memory bank and associated dead cycles.

[0008] This objective is accomplished by the use of a system and a method for (1) dividing the access requests across several memory banks into access requests per memory bank. Each memory access to a certain memory bank is independent from accesses to other memory banks; thus, memory access bandwidth can be optimized; (2) Providing queuing structure for access requests per memory bank; (3) Preventing accesses to a certain memory bank from occupying the whole command queue by imposing a threshold per memory bank access request queue such that memory access bandwidth will not be degraded; (4) Using bank rotation for writing receive packet to memory based on the write queue status; (5) Providing a best fit for systems where multiple “users” access independently in different memory locations; and (6) Using the status of write queue per memory bank for flow control of the system.

[0009] The invention relates to a system and a method of maximizing DRAM memory access utilization wherein the DRAM memory consists of a plurality of memory banks. The method comprises first dividing DRAM accesses into write accesses and read accesses. The read and write access requests are further divided into accesses per memory bank. A configurable threshold limit is imposed on the number of accesses to each memory bank. The writing receive packets are rotated among the banks based on the write queue status. The status of the write queue for each memory bank may also be used for system flow control. The method also typically includes the additional steps of determining access windows based on the status of the command queues, and performing arbitration on each access window.

[0010] The invention also relates to an article of manufacture comprising a computer usable medium having a computer readable program embodied in said medium. The program when executed on a computer causes the computer to maximize access to DRAM memory using an arbiter that maximizes the memory bandwidth available for the read and the write operations by avoiding consecutive accesses to the same memory bank and associated dead cycles. The program causes the arbiter to divide DRAM accesses into write accesses and read accesses, to divide the access request into accesses per memory bank, to impose a threshold limit on the number of accesses to each memory bank, and to rotate the write receive packets among the banks, wherein the write packets are rotated among the banks based on the write queue status. The program can cause the arbiter to use the status of the write queue for each memory bank for system flow control. It can cause the arbiter to determine access windows based on the status of the command queues, and perform arbitration on each access window. In one embodiment, the memory banks are embedded in fast cycle random access memory devices.

[0011] These, as well as other objects and advantages, will become apparent upon a full reading and understanding of the present invention.

[0018] A network processor scheduler is typically provided with sufficient memory access bandwidth to avoid bottlenecks and conflicts caused by different functional entities attempting to simultaneously access the same memory. This is done by using a combination of static random access memory (SRAM) and dynamic random access memory (DRAM) devices. The present invention is specifically concerned with the controlled access to DRAM memory useful for supporting high (e.g. 10 Gbps) data rates. For these high rates, a particularly useful memory device is a fast cycle dynamic random access memory (FCRAM chip), a double data speed fast cycle dynamic random access memory. (DDS FCRAM), or a reduced latency dynamic random access memory (RLDRAM). An FCRAM device is capable of delivering a random cycle time of 20 nanoseconds (ns) which is about 4 times faster than the speed of a conventional DRAM device. Another feature of the FCRAM is that it combines non-multiplexed addressing and complete address decoding and pipelining, thereby enabling both row and column address to be designated simultaneously, whereas with a conventional DRAM, there is a time lapse between these two activities.

[0019] In one embodiment, there are two FCRAM memory devices with one being the logical high part and the other the logical low part, with the two parts being generally transparent to the system software. Each FCRAM memory device contains four internal banks. A bank can be organized as a 4M×16-bits or 8M×8 bits format. The read and write access to each bank share the same bus. Each data chunk in the memory of the bank comprises 64 bytes, with 32 bytes in the high part and 32 bytes in the low part to achieve a wide bus. Typically, there is no need to read or to write both a high and a low in a given bank at the same time because the address buses of the high and low parts can be implemented independently.

[0020] As previously noted, the memory interface provides buffer management and data movement at media speed. To eliminate the memory access bandwidth bottleneck, the main function of the memory interface is to provide an efficient memory access scheme while meeting the requirements of sustained data throughput at the required data rate at the memory controller interface to the FCRAM memory device. This requires that a memory arbiter collect read requests from transmit FIFOs and write requests from receive FIFOs, and schedule efficient accesses to the memories. Because of hardware limitations, the access to FCRAM devices has the following timing constraints:

[0021] 1. Consecutive accesses (read or write) to the same memory bank shall be spaced out by three dead memory cycles.

[0022] 2. A write access following a read access shall be spaced out by two dead memory cycles to allow data bus turnaround. If the write operation is accessing the same memory bank as the previous read operation, one additional dead memory cycle is needed for a total of three dead cycles.

[0023] In order to provide a better understanding of the invention, reference is made to the drawings, and particularly with respect to FIG. 1, wherein the queuing structure 100 is shown for handling multiple access requests 102 comprising read access requests 104 and write access requests 106. The requests are labeled read A, B, C and D and write A, B, C and D, and are specified for one of four memory banks 110 marked as banks A 112, B 114, C 116 and D 118. A predetermined threshold 120 is imposed on each of the read queues 122 and each of the write queues 124 by the software or hardware package. This threshold limit can be configured to the predetermined value at system initialization by means of software or hardware or a combination thereof. Each read request passes through the queue to multiplexer 126, and each write request passes through the queue to multiplexer 128. In turn, one read request 130 and one write request 132 are selected and are passed to the multiplexer 134, and either a write or a read request is selected by the arbiter circuit 136. The address of the selected request is then forwarded at 138 to one of the memory banks 110. The queue status is checked at 140 to determine the actual queue count or number of requests in each queue compared to the threshold limit of each queue. A queue count equal to zero represents an empty queue. A queue count greater than the predetermined threshold limit represents overflow status.

[0024] According to one feature of the present invention, a decision flow chart 200 is shown in FIG. 2 for determining the sizes of access windows. The window access procedure starts at 202 when a queue status inquiry is received at 204. The first step in the decision process involves the determination at 218 as to whether any of the queues 122 or 124 in FIG. 1 is empty. If the answer is ‘yes’, the next question at 206 is whether any queue is overflowed. A ‘no’ response then results in the calculation of window size at 208 and, in turn, starts access window at 210. A ‘yes’ answer at 206 then triggers the next inquiry at 212 as to whether the overflow is in a read queue. If the response is ‘yes’, the read window is extended at 214. If the answer is ‘no’, then the size of the write window is extended at 216 to accommodate the overflow.

[0025] Returning to the queue status inquiry at 204, if the answer is ‘no’, thereby indicating that no queues are empty, the same question is asked at 220 as at 218, namely if any queue is overflowed. A ‘no’ answer then fixes the size of the access window at 18 memory cycles at 222 and the access window 210 is started. If, however, any queue is overflowed in response to the inquiry at 220, the ‘read overflow’ question at 224 is either answered ‘yes’ whereupon the read window is extended at 226 or ‘no’ whereupon the write queue is overflowed and the write window is extended at 228. Either way, the extended read or write window goes to the start access window at 210.

[0026] As can be readily seen from FIG. 2, there are a number of options that are available depending on the paths that are followed. FIGS. 3-9 show just a few of these possibilities.

[0027] Referring first to FIG. 3, the reading of packet data starts from memory bank A, and then successively from banks B, C and D. Then, the memory bus is turned around for the write access, starting from memory bank A, followed by banks B, C and D. The read and write accesses are completed in the access window of 18 memory cycles. For example, assume a required data rate of 10 Gbps in both receive (corresponding to memory write) and send or transmit (corresponding to memory read) directions. The available memory bandwidth for read and write access to eight DDR-FCRAM devices is based on an assumption of 51.2 Gbps at a clock cycle of five nanoseconds. At five ns per cycle, using 18 memory cycles, the bandwidth for the read operation is sustained at 51.2 Gbps while the corresponding bandwidth for the write operation is sustained at 22.75 Gbps, based on an assumption that each access contains 32 bytes of valid data. Two dead cycles between read and write are also shown in both the high and the low parts of the banks. In this example, banks A-D are read simultaneously in the high and low parts, and are written simultaneously in the high and low parts.

[0028] FIG. 4 shows that the access sequence to the memory banks of the high and low parts of the arbiter memory can be completely independent of one another. In this figure, there are two non-empty read request queues in the high part and two non-empty read request queues in the low part. As shown, write access is available in banks C and D in the low part, simultaneously with read access to banks A and B of the high part. Also, the high part of banks C and D can be read at the same time that the low part of banks A and B are being read. Also, it should be observed that the dead cycles in the low part do not necessarily occur simultaneously with those of the high part. It should also be noted that there is a dead time for a turn around when going from read to write, but that such a turn around time is not necessarily required when switching from write to read.

[0029] FIGS. 5-7 are samples of access windows where none of the queues has overflowed. It will be noted that both upper and lower parts of banks A-D are read or are written simultaneously.

[0030] Turning first to FIG. 5, a first data store analysis is shown in which the high part has two non-empty read request queues and four non-empty write request queues. The low part likewise has two non-empty read queues and four non-empty write queues. None of the queues as shown have exceeded the predetermined threshold.

[0031] FIG. 6 represents a second data store analysis similar to that of FIG. 5 but in which one of the non-empty read request queues in the high part and one of the non-empty read request queues in the low part have a significantly higher number of requests than the other two non-empty read request queues. In this scenario, the total memory cycles required to complete eight read and eight write accesses are 22 cycles, resulting in a decrease in the data throughput of both the read and the write accesses.

[0032] A third example of a data store access analysis is shown in FIG. 7. In this case, there is only one non-empty read request queue in the high part, one non-empty read request in the low part, eight non-empty write request queues in the high and the low parts, and none of the request queues have exceeded the predetermined threshold. In this scenario, the access windows contain 32 memory cycles to complete eight read and eight write accesses. This requires a total of 27 cycles to complete the accesses.

[0033] By its very nature, network traffic tends to be bursty. To accommodate the peak bandwidth requirement, it is desirable to extend either the read or the write access window as shown in FIGS. 8 and 9. The present invention embraces that capability.

[0034] FIG. 8 allows for additional write accesses by extending the window. If the number of write requests has exceeded the predetermined threshold, while all of the non-empty read request queues are below the threshold, the arbiter will extend the access window by another eight memory cycles to accommodate the demand for more accesses.

[0035] If the number of read requests exceeds the predetermined threshold, while all of the non-empty write request queues are below the threshold, the arbiter will extend the access window by another eight memory cycles to accommodate the increased number of read requests. This is shown in FIG. 9.

[0036] The net result of the present invention is that the arbiter maximizes the memory bandwidth available for the read and the write operations by avoiding consecutive accesses to the same memory bank and associated dead cycles.

[0037] FIG. 10 shows a computer-readable medium in the form of a floppy disc 1000 for containing the software implementation of the program to carry out the various steps of project management according to the present invention. Other machine readable storage mediums are fixed hard drives, optical discs, magnetic tapes, semiconductor memories, such as read-only memories (ROMs), programmable read-only memories (PROMs), etc. The article containing this computer readable code is utilized by executing the code directly from the storage device, or by copying the code from one storage device to another storage device, or by transmitting the code on a network for remote execution. The computer program may be loaded into the memory to configure and to run the program herein described and claimed for execution. The computer program comprises instructions which, when read and executed by the system, perform the steps necessary to execute the steps or elements of the present invention.

[0038] The present invention can be realized in hardware, software, or a combination of the two. Any kind of computer system or other apparatus adapted for carrying out the methods described herein is suited. A typical combination of hardware and software could be a general purpose computer system that, when loaded and executed, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which, when loaded in a computer system, is able to carry out these methods.

[0039] Computer program instructions or a computer program in the present context mean any expression, in any language, code (i.e., picocode instructions) or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following occur: (a) conversion to another language, code or notation; (b) reproduction in a different material form.

[0040] While the invention has been described in combination with specific embodiments thereof, there are many alternatives, modifications, and variations that are likewise deemed to be within the scope thereof. Accordingly, the invention is intended to embrace all such alternatives, modifications and variations as fall within the spirit and scope of the appended claims.