Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-02-25
2001-11-27
Lee, Thomas (Department: 2782)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S052000, C710S113000, C711S110000, C711S147000, C712S245000, C370S474000, C370S235000, C370S400000, C370S362000, C370S395430
Reexamination Certificate
active
06324601
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to first in, first out memory systems. More particularly, the present invention relates to a method and apparatus for managing multiple ordered sets in a single memory system.
BACKGROUND OF THE INVENTION
A first in, first out memory system (FIFO) is a memory system from which data items are retrieved in the same sequence in which the data items were stored in the memory system. That is, the first data item stored in a FIFO is the first data item that is retrieved from the FIFO.
FIFO's are commonly used as data rate buffers between systems that transfer data at widely different rates. For example, multiple systems which process and transfer data at widely different rates can be interconnected through an interconnect such as a crossbar. A FIFO can be used to buffer data transferred from a fast device to a slow device, for example, from a computer to a printer. The computer can send character data to a FIFO at a relatively high rate. The printer can then read the data from the FIFO at a much slower rate and in the same order that the data was sent by the computer. Similarly, a FIFO can be used to buffer data transferred from a slow device to a fast device, e.g., from a keyboard to a computer. Here, the keyboard can send character data to a FIFO at a relatively low rate. The computer can then read the data from the FIFO at a much higher rate and in the order that the data was sent by the keyboard. Therefore, the computer may perform other tasks while the FIFO is slowly being filled with data and later retrieve the data from the FIFO in order.
A FIFO implemented in hardware, e.g., in an integrated computer, typically includes a finite number of memory positions into which data items can be stored. Each memory position can be, for example, a register. In general, each memory position of the FIFO can store a single data item. Each data item typically has a fixed length, but some FIFOs store data items of variable length.
Many applications require buffering of multiple ordered sets, or multiple sets of data items. In such applications, sequential ordering of data items are generally only important among data items of the same set. One such example is a scheduler that spools task sets for multiple processors. The scheduler can compile an ordered set of packets for each processor and each processor can sequentially execute a task set which includes the ordered set of packets specific to the processor. Therefore, it is important to maintain sequential ordering of packets within each ordered set for each processor. But, it is not necessary to maintain sequential ordering of packets among the plurality of ordered sets.
One method of buffering data entries of multiple ordered sets is to sort the data entries into multiple, separate FIFO's, i.e., one for each ordered set. In some applications, e.g., when multiple FIFO's are implemented in hardware, it is necessary to pre-allocate memory space for such FIFO's and therefore to fix a maximum number of FIFO's and a maximum number of memory positions for each such FIFO. In systems which use multiple FIFO's, the number of FIFO's and the maximum requisite length of each FIFO can be particularly difficult to predict and can depend upon the manner in which such systems are used. Fixing the maximum number of FIFO's too low increases the likelihood that such a system finds insufficient FIFO's to operate properly. Fixing the maximum number of FIFO's too high allocates more memory, and therefor more circuitry, than is necessary for implementation of the multiple FIFO's. In addition, one of a number of FIFO's of fixed length can exhaust available memory positions while other FIFO's have a surplus of memory positions. Accordingly, fixing the number of FIFO's and the number of memory positions for each FIFO can result in a memory position shortage in one FIFO and a simultaneous memory position surplus in other FIFO's.
Some attempts have been made to implement multiple ordered sets in a single FIFO. However, such can result in a problem known as blocking. Blocking refers to the unavailability of data items of one ordered set stored in a FIFO as a result of storage of a data item of another ordered set in a preceding memory in the order of the FIFO. The following example is illustrative. Suppose a scheduler collects packets into respective ordered sets representing respective tasks to be performed by respective processors. Suppose further that the packets are spooled through a single FIFO regardless of the particular processor which is to receive each packet. If packets intended for a first processor follow packets intended for a second processor in the sequence of the single FIFO, the packets intended for the first processor cannot be sent to the first processor until the preceding packets for the second processor are sent. If the second processor is busy and cannot receive the packets from the FIFO, the packets intended for the first processor are blocked. Even if the first processor is ready to receive packets from the FIFO, the packets are blocked pending receipt of the preceding packets by the second processor. Accordingly, the first processor is idle and wasted as long as the second processor is busy. Thus, blocking leads to unnecessarily wasted resources and time.
What is needed is a method and apparatus for buffering data entries of multiple ordered sets without a need to allocate an excess of FIFO's or slots per FIFO and in a manner such that blocking of an oldest data entry which is a member of one set does not cause excessive delay in release of oldest data entries of other sets from the FIFO.
SUMMARY OF THE INVENTION
In accordance with the present invention, a method and apparatus for managing multiple ordered sets of data entries in a circular memory structure is provided. A circular memory structure according to the present invention is sometimes referred to as a turnstile FIFO. Multiple ordered sets of data packets are stored in the turnstile FIFO. The turnstile FIFO is managed such that blocking of an oldest packet which is a member of one set does not cause excessive delay in dequeuing oldest packets which are members of other sets. Processing multiple ordered sets according to the present invention safely preserve sequential order among packets which are members of a same set.
Each packet includes a set identifier which specifies one of the multiple ordered sets stored in the turnstile FIFO. Accordingly, the turnstile FIFO can include as few as one ordered set or as many distinct and separate ordered sets as can be uniquely identified by the range of values of the set identifier. Conventional FIFO systems require pre-allocating a number of FIFO's, each of which is pre-allocated at a maximum size. However, storing all packets at a single turnstile FIFO allows a moderately sized turnstile FIFO to store a few long ordered sets, many short ordered sets, or a combination of both.
Operations performed on the turnstile FIFO include enqueue, dequeue, and rotate. The enqueue operation adds a new packet to the turnstile FIFO in such a way that preserves the sequential order of the packets of the selected set within the turnstile FIFO. The dequeue operation retrieves an oldest packet of a set stored in the turnstile FIFO which is not currently blocked from being dequeued.
Specifically, a data packet is dequeued from a position within the turnstile FIFO only if the data packet is the oldest data packet stored in the turnstile FIFO of the particular ordered set to which the data packet belongs. Turnstile logic determines whether the data packet is the oldest of its particular ordered set by determining the ordered set to which each older data packets of the turnstile FIFO belongs. Since the data packets of the turnstile FIFO are stored in the same sequence in which the data packets are added to the turnstile FIFO, all data packets which are older than the selected data packet are stored at preceding positions within
Webber Thomas P.
Wilcox Paul A.
Conley Rose & Tayon PC
Kivlin B. Noëel
Lee Thomas
Schuster Katharina
Sun Microsystems Inc.
LandOfFree
Data structure and method for managing multiple ordered sets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure and method for managing multiple ordered sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure and method for managing multiple ordered sets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598908