Abstract:
A device for queuing information combines the speed of SRAM with the low cost and low power consumption of DRAM, affording substantial expansion of high-speed data storage in queues without corresponding increases in costs. The queues have a variable size, and provide fast, flexible and efficient data storage via an SRAM interface and a DRAM body. The queues may hold pointers to buffer addresses or other data that allow manipulation of information in the buffers via manipulation of the queues. Particular utility for this mechanism exists in situations for which high-speed access to queues is beneficial, flexible queue size is advantageous, and/or the smaller size and lower cost of DRAM compared to SRAM is of value.

Description:
MICROFICHE APPENDIX 
     A Microfiche Appendix comprising one sheet, totaling twenty-seven frames is included herewith. 
     COPYRIGHT NOTICE 
     A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of the patent document or the patent disclosure in exactly the form it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. 
     TECHNICAL FIELD 
     The present invention relates to memory circuits for microprocessors. 
     BACKGROUND OF THE INVENTION 
     The operation of processors frequently involves temporary storage of information for later manipulation. As is well known, data may be stored for random access, or may be stored for access in an ordered fashion such as in a stack or queue. A queue stores data entries in sequential fashion, so that the oldest entry in the queue is retrieved first. The entry and removal of data in queues may be handled by a central processing unit (CPU) processing software instructions. 
     Such a queue system can be a bottleneck in the efficient operation of the processor. For example, a first item of information obtained from one process may need to be queued to wait for the processing of another item of information, so that both items may then be manipulated together by the processor. The queuing and dequeuing of the first item of information may require additional work of the processor, slowing the eventual processing of both items of information further. More complicated situations involving multiple operands and operations cause the queuing and dequeuing complications to multiply, requiring various locks that absorb further processing power and time. The size and complexity of a microprocessor can lead to correspondingly large and complex arrangements for storing queues. 
     The allocation of memory space for these queues is also challenging, as the queues can vary in length depending upon the type of operations being processed. For example, a queuing scheme for a communication system is described by Delp et al. in U.S. Pat. No. 5,629,933, in which a number of data packets are stored in first-in, first out (FIFO) order in queues that are segregated by session identity. Depending upon activity of a particular session, the number of entries in such queues could be very large or zero. In U.S. Pat. No. 5,097,442, Ward et al. teach programming a variable number into a register to store that number of data words in a FIFO memory array, up to the limited size of that array. 
     To distribute memory for queuing different connections, U.S. Pat. No. 5,812,775 to Van Seters et al. teaches a device for a router having a number of network connections that dedicates specific buffers to each network connection as well as providing a pool of buffers for servicing any network connection. A number of static random access memory (SRAM) queues are maintained for tracking buffer usage and allocating buffers for storage. While SRAM provides relatively quick access compared to dynamic random access memory (DRAM), SRAM memory cells are much larger than DRAM, making SRAM relatively expensive in terms of chip real estate. 
     SUMMARY OF THE INVENTION 
     The present invention provides a mechanism for queuing information that is fast, flexible and efficient. The mechanism combines the speed of SRAM with the low cost and low power consumption of DRAM, to enable significant expansion of high-speed data storage in queues without corresponding increases in costs. The queues may be manipulated by hardware or software, and may provide processing events for an event-driven processor. While the queuing mechanism of the present invention can be employed in many systems in place of conventional queues, particular utility is found where high speed access to queues is beneficial, as well for situations in which flexible queue size may be an advantage, and/or for cases where the smaller size and lower cost of DRAM compared to SRAM is of value. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram of a plurality of queues of the present invention. 
     FIG. 2 is a diagram of the enqueuing and dequeuing of entries in a queue of FIG.  1 . 
     FIG. 3 is a diagram of a network computer implementation of the queue system of the present invention. 
     FIG. 4 is a diagram of a plurality of status registers for the queues of FIG.  3 . 
     FIG. 5 is a diagram of a queue manager that manages movement of queue entries between various queues in the queue system of FIG.  3 . 
     FIG. 6 is a diagram of a queue system that may be provided on a card that plugs into a computer or other device. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 illustrates a plurality of hardware queues of the present invention, which may contain other such hardware queues as well. A first queue  20  is formed of a combination of SRAM  22  and DRAM  25  storage units. A second queue  27  is similarly formed as a combination of SRAM  30  and DRAM  25  storage units. The queues  20  and  27  each have an SRAM head and tail which can be used as an SRAM FIFO, and the ability to queue information in a DRAM body as well, allowing expansion and individual configuration of each queue. Connection between SRAM FIFOS  22  and  30  and DRAM  25  allows those queues  20  and  27  to handle situations in which the SRAM head and tail are fall. DRAM  25  may be formed on the same integrated circuit chip as SRAM FIFOS  22  and  30 , or may be separately formed and then connected. The portion of DRAM  25  that is allocated to specific queues such as  20  and  27  may be determined during initialization of the system containing the queues. SRAM FIFOS  22  and  30  afford rapid access to the queues for enqueuing and dequeuing information, while DRAM  25  affords storage for a large number of entries in each queue at minimal cost. 
     SRAM FIFO  22  has individual SRAM storage units,  33 ,  35 ,  37  and  39 , each containing eight bytes for a total of thirty-two bytes, although the number and capacity of these units may vary in other embodiments. Similarly, SRAM FIFO  30  has SRAM storage units  42 ,  44 ,  46  and  48 . SRAM units  33  and  35  form a head  50  of FIFO  22  and units  37  and  39  form a tail  52  of that FIFO, while units  42  and  44  form a head  55  of FIFO  30  and units  46  and  48  form a tail  57  of that FIFO. Information for FIFO  22  may be written into head units  33  or  35 , as shown by arrow  60 , and read from tail units  37  or  39 , as shown by arrow  62 . A particular entry, however, may be both written to and read from head units  33  or  35 , or may be both written to and read from tail units  37  or  39 , minimizing data movement and latency. Similarly, information for FIFO  30  is typically written into head units  42  or  44 , as shown by arrow  64 , and read from tail units  46  or  48 , as shown by arrow  66 , but may instead be read from the same head or tail unit to which it was written. While a queue of the present invention may include only one SRAM unit, the availability of plural SRAM units can improve access to SRAM without observable latency from data movement between SRAM and DRAM. 
     Queue  20  may enqueue an entry in DRAM  25 , as shown by arrow  70 , by direct memory access (DMA) units acting under direction of a queue manager, not shown in this figure, instead of being queued in the head or tail of FIFO  22 . Entries stored in DRAM  25  return to SRAM unit  37 , as shown by arrow  73 , extending the length and fall-through time of that FIFO. Diversion of information from SRAM to DRAM is typically reserved for when the SRAM is full, since DRAM is slower and DMA movement causes additional latency. Thus queue  20  may comprise the entries stored by the queue manager in both the FIFO  22  and the DRAM  25 . Likewise, information bound for FIFO  30  can be moved by DMA into DRAM  25 , as shown by arrow  75 . The capacity for queuing in cost-effective albeit slower DRAM  25  is user-definable during initialization, allowing the queues to change in size as desired. Information queued in DRAM  25  can be returned to SRAM unit  46 , as shown by arrow  77 . Movement of information between DRAM and SRAM can be coordinated so that devices utilizing the queue experience SRAM speed although the bulk of queued information may be stored in DRAM. 
     The queue system of the present invention may vary in size and may be used with various devices. Such a queue system may be particularly advantageous for devices that benefit from rapid processing of large amounts of data with plural processors. A preferred embodiment described in detail below and in Verilog code in the microfiche appendix includes a queue manager, SRAM and DRAM controllers and a number of queues that may be used with a network communication device. 
     FIG. 2 depicts the enqueuing and dequeuing of entries in queue  20  for a device  10  such as a processor. When device  10  wants to store data in a queue, information regarding that data is sent to a queue manager  12 , which manages entries in multiple queues such as queue  20 . Queue manager  12  includes a queue controller  14  and DMA units Q 2 D  16  and D 2 Q  18 , which may be part of a number of DMA units acting under the direction of queue controller  14 . DMA units Q 2 D  16  and D 2 Q  18  may be specialized circuitry or dedicated sequencers that transfer data from SRAM to DRAM and vice-versa without using the device  10 . The queue controller  14  enters the data from device  10  in the head  50  of queue  20 , which is composed of SRAM. Should the information be needed again shortly by device  10 , the queue controller can read the entry from head  50  and send it back to device  10 . Otherwise, in order to provide room for another entry in head  50 , DMA unit Q 2 D  16  moves the entry from the SRAM head  50  to DRAM body  25 . Entries are dequeued to device  10  from queue  20  in a similar fashion, with device  10  requesting controller  14  for the next entry from queue  20 , and receiving that entry from tail  52  via controller  14 . DMA unit D 2 Q  18 , operating as a slave to controller  14 , moves entries sequentially from body  25  to SRAM tail  52 , so that entries are immediately available for dequeuing to device  10 . 
     FIG. 3 focuses on a queuing system integrated within a network communication device  160  for a host  170  having a memory  202  and a CPU  205 . The device  160  is coupled to a network  164  via a media access controller  166  and a conventional physical layer interface unit (PHY), not shown, and coupled to the host  170  via a PCI bus  168 . The device  160  maybe provided on the host  170  motherboard or as an add-on network interface card for the host. Although a single network connection is shown in this figure for brevity, the device  160  may offer full-duplex communication for several network connections, partly due to the speed and flexibility of the queuing system. Processing of communications received from and transmitted to the network  164  is primarily handled by receive sequencer  212  and transmit sequencer  215 , respectively. A queue array  200 , which may include thirty-two queues in this embodiment, contains both DRAM  203  and SRAM  206 , where the amount of DRAM  203  earmarked for the queue system can vary in size. The DRAM  203  and SRAM  206  are used for other functions besides the queue array  200 , and may be formed as part of the device or may be separately formed and attached to the device. The device  160  includes a communications microprocessor  208  that interacts with the CPU  205  and host memory  202  across PCI bus  168  via a bus interface unit  210 . A queue manager  220  helps to manage the queue array  200 , via DRAM controller  211  and SRAM controller  214 . 
     Status for each of the hardware queues of the queue array  200  is conveniently maintained by and accessed from a set  80  of four registers, as shown in FIG. 4, in which a specific bit in each register corresponds to a specific queue. The registers are labeled Q-Out_Ready  82 , Q-In_Ready  84 , Q-Empty  86  and Q-Full  88 , and for the thirty-two queue embodiment the registers each have thirty-two bits. If a particular bit is set in the Q-Out_Ready register  82 , the queue corresponding to that bit contains information that is ready to be read, while the setting of the same bit in the Q-In_Ready register  84  means that the queue is ready to be written. Similarly, a positive setting of a specific bit in the Q-Empty register  86  means that the queue corresponding to that bit is empty, while a positive setting of a particular bit in the Q-Full register  88  means that the queue corresponding to that bit is full. Q-Out_Ready  82  contains bits zero  90  through thirty-one  99  in the thirty-two queue embodiment, including bits twenty-seven  95 , twenty-eight  96 , twenty-nine  97  and thirty  98 . Q-In_Ready  84  contains bits zero  100  through thirty-one  109 , including bits twenty-seven  105 , twenty-eight  106 , twenty-nine  107  and thirty  108 . Q-Empty  86  contains bits zero  110  through thirty-one  119 , including bits twenty-seven  115 , twenty-eight  116 , twenty-nine  117  and thirty  118 , and Q-full  88  contains bits zero  120  through thirty-one  129 , including bits twenty-seven  125 , twenty-eight  126 , twenty-nine  127  and thirty  128 . 
     Operation of the queue manager  220 , which manages movement of queue entries between SRAM and the microprocessor, the transmit and receive sequencers, and also between SRAM and DRAM, is shown in more detail in FIG.  5 . Requests, which utilize the queues, include Processor Request  222 , Transmit Sequencer Request  224 , and Receive Sequencer Request  226 . Other requests for the queues are DRAM to SRAM Request (D 2 Q Seq Req)  228  and SRAM to DRAM Request (Q 2 D Seq Req)  230 , which operate on behalf of the queue manager in moving data back and forth between the DRAM and the SRAM head or tail of the queues. Determining which of these various requests will get to use the queue manager in the next cycle is handled by priority logic Arbiter  235 . To enable high frequency operation the queue manager is pipelined, with Register-A  238  and Register-B  240  providing temporary storage, while Status Registers Q_Out_Ready  265 , Q_In_Ready  270 , Q_Empty  275 , and Q_Full  280  maintain status until the next update. The queue manager reserves even cycles for SRAM to DRAM, DRAM to SRAM, receive and transmit sequencer requests and odd cycles for processor requests. Dual ported QRAM  245  stores variables regarding each of the queues, the variables for each queue including a Head Write Pointer, Head Read Pointer, Tail Write Pointer and Tail Read Pointer corresponding to the queue&#39;s SRAM condition, and a Body Write Pointer, a Body Read Pointer and a Queue Size Variable corresponding to the queue&#39;s DRAM condition and the queue&#39;s size. 
     After Arbiter  235  has selected the next operation to be performed, the variables of QRAM  245  are fetched and modified according to the selected operation by a QALU  248 , and an SRAM Read Request  250  or an SRAM Write Request  255  may be generated. The four queue manager registers Q_Out_Ready  265 , Q_In_Ready  270 , Q_Empty  275 , and Q_Full  280  are updated to reflect the new status of the queue that was accessed. The status is also fed to Arbiter  235  to signal that the operation previously requested has been fulfilled, inhibiting duplication of requests. Also updated are SRAM Addresses  283 , Body Write Request  285  and Body Read Requests  288  which are used by DMA CONTROLLER  214  while moving data between SRAM head and DRAM body as well as SRAM tail and DRAM body. If the requested operation was a write to a queue, data as shown by Q Write Data  264 , are selected by multiplexor  266 , and pipelined to SRAM Write Data register  260 . The SRAM controller services the read and write requests by reading the tail or writing the head of the accessed queue and returning an acknowledge. In this manner the various queues can be utilized and their status updated. 
     The array of queues  200  contained within the communication device  160  may include thirty-two queues, for example. At the beginning of operation the device memory is divided into a number of large (2 kilobyte) and small (256 byte) buffers, and pointers denoting the addresses of those buffers are created. These pointers are placed in a large free buffer queue and a small free buffer queue, respectively. Over time, as various operations are executed, these free buffer queues offer a list of addresses for buffers that are available to the communication device  160  or other devices. Due to the potential number of free buffer addresses, these free buffer queues commonly include appreciable DRAM  203  in order to provide sufficient room for listing the buffers available to any device in need of a usable buffer. Note that the queue entries need not be pointers but may, for example, comprise thirty-two bits of control information that is used for communicating with or controlling a device. Another example of a variable capacity queue that may contain a significant amount of DRAM  203  is a trace element queue, which can be used to trace various events that have occurred and provide a history of those events, which may for instance be useful for debugging. 
     FIG. 6 shows a queue system  300  that may be provided on a card that can plug into a computer or similar device. The queue system contains an array of queues that may include both SRAM  303  and DRAM  305 . The queue system may be formed as a single ASIC chip  308 , with the exception of DRAM  305 . The DRAM  305  may be provided on the card as shown or may exist as part of the computer or other device and be connected to the card by a bus. The system  300  may connect to a microprocessor  310  via a microprocessor bus  313 , with a microprocessor bus interface unit  316  translating signals between the microprocessor bus and a queue manager  320 . The queue manager  320  controls DMA units  323  and an SRAM controller  325  that can also control the DMA units  323 . SRAM controller  325  and DMA units  323  can also interact with a DRAM controller  330 , manages and maintains information in DRAM  305 . 
     While the above-described embodiments illustrate several implementations for the queue system of the present invention, it will be apparent to those of ordinary skill in the art that the present invention may be implemented in a number of other ways encompassed by the scope of the following claims. Examples of such implementations include employment for network routers and switches, controllers of peripheral storage devices such as disk drives, controllers for audio or video devices such as monitors or printers, network appliance controllers and multiprocessor computers.