Abstract:
A bandwidth conserving queue manager for a FIFO buffer is provided, preferably on an ASIC chip and preferably including separate DRAM storage that maintains a FIFO queue which can extend beyond the data storage space of the FIFO buffer to provide additional data storage space as needed. FIFO buffers are used on the ASIC chip to store and retrieve multiple queue entries. As long as the total size of the queue does not exceed the storage available in the buffers, no additional data storage is needed. However, when some predetermined amount of the buffer storage space in the FIFO buffers is exceeded, data are written to and read from the additional data storage, and preferably in packets which are of optimum size for maintaining peak performance of the data storage device and which are written to the data storage device in such a way that they are queued in a first-in, first-out (FIFO) sequence of addresses. Preferably, the data are written to and are read from the DRAM in burst mode.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to management of queues of data being received from an outside source and inputted into a device for further processing. In more particular aspects, this invention relates to an improved DRAM used in conjunction with a FIFO buffer for controlling the queue of received data. 
     BACKGROUND OF THE INVENTION 
     There are many applications in which data is received at a higher rate than it can be utilized by a particular device for short periods of time, thus necessitating queuing data for orderly input into the device on which it is to be used. A common type of queue is first-in, first-out (FIFO) buffers which temporarily store the data being received from some outside source for input into the receiving device at a rate the receiving device can accommodate. One of the problems encountered is that the FIFO buffers may exceed their capacity to store data inputted faster than it can be outputted. Thus, there is a need for a technique for managing data in an orderly way with minimum overhead for periods of time when such data being inputted is greater than the storage capacity of the FIFO buffer or buffers. 
     SUMMARY OF THE INVENTION 
     According to the present invention, a bandwidth conserving queue manager for a FIFO buffer is provided, preferably on an ASIC chip and preferably including a separate DRAM that maintains a FIFO queue which can extend beyond the data storage space of the FIFO buffer to provide additional data storage space as needed. FIFO buffers are used on the ASIC chip to store and retrieve multiple queue entries. As long as the total size of the queue does not exceed the storage available in the buffers, no additional data storage is needed. However, when the buffer storage space in the FIFO buffers is exceeded, data are written to and read from the additional data storage preferably a DRAM and preferably in packets which are of optimum size for maintaining peak performance of the data storage device and which are written to the data storage device in such a way that they are queued in a first-in, first-out (FIFO) sequence of addresses. The DRAM can be a separate chip, or it can be formed on the ASIC. In either case, its memory is separate from the FIFO buffer or buffers. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a high level diagrammatic view of the structure of the managed DRAM queue manager of the present invention; 
     FIG. 2 is a detailed view, somewhat diagrammatic, of the input FIFO buffer; and 
     FIG. 3 is a detailed view, somewhat diagrammatic, of the output FIFO buffer. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring now to the drawings and, for the present, to FIG. 1, an overview of the structure and operation of the bandwidth conserving DRAM queue manager according to the present invention is shown. The queue manager is formed on an ASIC chip  10 . The queue manager receives data input  12  from an outside source which is inputted to an input FIFO (first-in, first-out) buffer  14  in which the data is arranged in a queue. Data  16  is outputted from the input FIFO buffer  14  to a memory interface  18  and to a multiplexor (Mux)  20 . The memory interface  18  connects to a DRAM chip  22  which is a separate chip. (However, the DRAM could be formed on the ASIC  10 .) The multiplexor  20  is controlled by multiplexor control logic  24  to output data  16  from FIFO buffer  14  selectively to the DRAM chip  22  or to an output FIFO buffer  32 . The FIFO buffer  32  outputs data  34  to the device (not shown) to which data is being supplied. 
     In general, the queue manager shown in FIG. 1 operates in the following manner: Data  12  to be written into the queue is inputted to the input FIFO buffer  14 . Data  16  leaving the FIFO may go either to the output FIFO  32  or to the external memory interface  18  and then to the DRAM chip  22  as controlled by the mux  20  and by mux control logic  24  depending on whether or not there is enough room in the input FIFO buffer  14  and the output FIFO buffer  32  for the data being read from an external source. The mux  20  is controlled based on this condition, i.e., whether the input FIFO buffer  14  and output FIFO buffer  32  are full or at least have a predetermined percentage of capacity filled. When there is more data to be stored in the input FIFO buffer  14  and output FIFO buffer  32  than the maximum permitted, the mux  20  selects data to be written to the external memory interface  18  and the data is then stored in the DRAM chip  22 . As the output FIFO buffer  32  is read out, the data is read from the DRAM chip  22  through the memory interface, to the output FIFO buffer  32  under the control of the mux control logic  24 . Thus, as long as the amount of input data  12  being read from an external source does not exceed a preselected capacity of the input FIFO buffer  14  and output FIFO buffer  32 , the data is passed from the input FIFO buffer  14  directly to the output FIFO buffer  32 . 
     However, when the amount of data  12  being inputted exceeds the capacity or predetermined percentage of capacity of the input FIFO buffer  14  and the output FIFO buffer  32 , then the data is written by the input FIFO buffer  14  to the DRAM chip  22  through the memory interface  18 . The DRAM chip  22  is structured to be written and read on a first-in, first-out basis at contiguous addresses so that address mapping is not required as in a conventional cache memory. The data is written to the input FIFO buffer  14  from the external source and to the output FIFO buffer  32  from the input FIFO buffer  14  one data item at a time. However, preferably the data is written to the memory interface  18  and thence to the DRAM chip  22 , and read from the DRAM chip  22  by output FIFO  32  in bursts of multiple data items to utilize the optimum transfer rate of the DRAM chip  22 . Moreover, because the DRAM is arranged so that it is ordered on a first-in, first-out basis, the burst capabilities can be used and no address tags need be applied to the data written thereto. Thus, for example, the data can be written to and read from the DRAM chip  22  in data packets of three items, rather than have to read each data item individually by address. It is also preferred that the DRAM be a DDR (double data rate) DRAM. Double data rate DRAM allows twice the data bandwidth for a given number of I/O pins on the ASIC package as does standard synchronous DRAM This is accomplished by launching and capturing data on both the rising and falling edge of the clock signal. RAMBUS is another scheme of increasing the bandwidth per in which may be beneficial in some applications. 
     Referring now to FIG. 2, a more detailed depiction of the input FIFO buffer  14  is shown. The input FIFO buffer  14  includes latches at storage locations  40   a ,  40   b ,  40   c ,  40   d ,  40   e  and  40   f  for six different data items. The data items are read one data item at a time from an external source and are written in the FIFO buffer  14 , one data item at a time, under control selectors  42   a ,  42   b  and  42   c . A write pointer  44  and read pointer  46  are both provided which provide outputs to a comparator  48 . The output of the comparator  48  goes to the mux control logic  24 . As indicated above, the data is written in bursts, e.g. three data items from the FIFO buffer  14  to the DRAM  20  or one data item at a time to the output FIFO buffer  32  responsive to the control of the mux  20 . A detailed view of the output FIFO buffer  32  is shown in FIG.  3 . 
     Shown in FIG. 3 are data item latches at storage locations  50   a ,  50   b ,  50   c ,  50   d ,  50   e  and  50   f  and selectors  52   a ,  52   b ,  52   c ,  52   d ,  52   e  and  52   f  which control the inputs  54   a ,  54   b ,  54   c ,  54   d ,  54   e  and  54   f  to storage locations  50   a - 50   f . Data outputs  56   a ,  56   b ,  56   c ,  56   d ,  56   e  and  56   f  from the data item storage  50   a - 50   f  are provided which go to a selector  58  to provide the data output  34 , the data being outputted one data item at a time. A write pointer  62  and a read pointer  64  are provided which output signals to a comparator  66 . Comparator  66  outputs its difference to the mux control logic  24 . 
     Also, the DRAM  20  has a write pointer, a read pointer and a comparator (all not shown), the output of which DRAM comparator is also provided to the mux control logic  24  As indicated above, the data is written to the output FIFO  32  from the DRAM in multiple data items to utilize the optimum data rate transfer of the DRAM. The memory interface is responsible for maintaining pointers to the head and tail portions of the queue which is stored in the DRAM chip  22 . By having contiguous addresses and head and tail pointers, the need for individual addresses is eliminated, and the DRAM chip  22  acts in a FIFO mode. 
     The multiplexor  20  is controlled by the multiplexor control logic  24  in the following way: Initially, data  12  is inputted to the input FIFO queue in the FIFO buffer  14  one data item at a time, and, assuming the output FIFO buffer  32  is empty, the data is passed from the input FIFO buffer  14  directly to the output FIFO buffer  32  by the action of the mux  20 . When the output FIFO buffer  32  is completely full and the input FIFO buffer  14  is half full, the mux  20  is switched by the control logic  24  responsive to the comparators  48  and  66  to pass data through the memory interface  18  to the DRAM chip  22  on the write cycle in multiple data items and for the output FIFO  32  to read data from the DRAM chip  22  through the memory interface  18  on the read cycle in multiple data items. When the comparator in the DRAM indicates that there are no more data items stored in the DRAM chip  22 , the mux  20  is switched back to pass the data from the input FIFO buffer  14  to the output FIFO buffer  32 . 
     The control of the memory interface, as indicated above, is accomplished by a write pointer to keep track of where the next group of data items will be written and a read pointer to keep track of from where the next group of data items will be read. The comparator determines if these two pointers are the same, which indicates the buffer is either full or empty. The read and write pointers work in the following way: When the read and write pointers are at the same data location on a read cycle, it means the storage locations are empty, and when the read and write pointers are at the same location on a write cycle, it means that the storage locations are full. 
     Thus, the read and write pointers and comparators  44 ,  46  and  48  and read and write pointers and comparators  62 ,  64  and  66 , operate to indicate whether the data storage in the input FIFO buffer  14  is full or empty and the data storage in output FIFO buffer  32  is full or empty and to control the operation of the mux  20  accordingly. The read and write and comparator in the DRAM operate in the same way. (It should be noted that in some applications a linked list of data items can be used rather than read and write pointers). 
     The bus width of the interfaces to the input data  12  and output data  34  can be the same as the bus width at the memory bus interface. However, different bus widths may be desirable, especially if a DDR DRAM is used. The trade-off which must be made based on the particular application is the amount of on-chip buffering which will be provided (silicon area) versus the efficiency of the data transfer (bandwidth). In most cases, the bandwidth is more important. The maximum bandwidth is determined by the width of the DRAM interface and the rate at which it can accept commands and data. These rates are a property of the DRAM and the width is selectable, although the number of I/Os on an ASIC is usually a limiting factor. When these issues are weighed, there will be a particular minimum packet size required to maintain this maximum bandwidth. The input data  12  and output data  34  widths will usually be dictated by the particular application so the variable is on the on-chip buffer size which would be the minimum DRAM packet size divided by the data item size times four. (The input and output FIFOs each need to be able to store two memory packets worth of data.) 
     To summarize the operation of the device of this invention, data is read into the input FIFO buffer  14  from an outside source and is written from the input FIFO buffer  14  to the output FIFO buffer  32  as long as the output FIFO buffer  32  is not full. When the output FIFO buffer  32  becomes full and the input FIFO buffer  14  becomes half full, the mux  20  shifts and allows the input FIFO buffer  14  to write data to the DRAM chip  22  and allows the output FIFO buffer  32  to read data from the DRAM chip  22 . The output from the output FIFO buffer  32  is outputted as output  34 . When the output FIFO buffer  32  and the DRAM chip  22  are empty, the mux  20  then allows the input FIFO buffer  14  to write directly to the output FIFO buffer  32 . Thus, the DRAM chip  22  acts as an additional buffer space when the data input  12  is greater than input FIFO buffer  14  and output FIFO buffer  32  can handle.