Browse Prior Art Database

Indirect Translation of Sequence Counts to Indices of Arbitrary Depth Queues Disclosure Number: IPCOM000099360D
Original Publication Date: 2005-Mar-14
Included in the Prior Art Database: 2005-Mar-14
Document File: 3 page(s) / 60K

Publishing Venue



In a system with a bus that uses sequence counts, this method provides an efficient means to process queue entries when the number of sequence counts available is not a multiple of the queue size.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 3

Indirect Translation of Sequence Counts to Indices of Arbitrary Depth Queues

Disclosed is a method for bus systems using sequence counts that provides an efficient means to process queue entries when the number of sequence counts is nota multiple of the queue size.This method builds on an existing circular First-In, First-Out (FIFO) queue design, and adds a series of pointers that allow sequence counts of interest to be indirectly translated to the index values of queue entries. Since only a few pointers need to be added, this design avoids the area and timing problems of other possible solutions.

    Currently, simple methods exist for handling queue depths that divide evenly into the number of sequence counts. Most designs use powers of two for the size of the FIFO to simplify the controls. Usually, for each FIFO entry a large amount of data must be stored, either in latches or in an array. When restricted to powers of two, designers sometimes must choose between a smaller FIFO, at a sacrifice to performance, or a FIFO that is too large, at the great expense of chip area. Being able to choose any depth of FIFO allows the designer to use less area to optimize performance. Background - Link Layer Circular FIFO
Many bus protocols assign a sequence count to each packet sent across the bus link. The link layer logic retains pertinent command information until it receives an acknowledge for that packet's sequence count. This design uses one or more circular buffers to maintain this information. A given command always has the same index in the queue. Pointers into the FIFO wrap around as they reach the top.

    The circular FIFO maintains pointers that index important locations in the FIFO. The write pointer (WritePtr) points to the next queue entry to write into. SendPtr points to the next command to send. StartPtr marks the beginning of outstanding commands. These are commands that have been sent but have not received an acknowledge. FreeNxtPtr points to the head of the queue. This contains the earliest command that has not been freed in the transaction layer. When FreeNxtPtr does not equal StartPtr, this means commands have been acknowledged but have not been freed yet.

New FIFO Control Implementation When the number of sequence counts is a multiple of the number of FIFO entries, a given sequence count always corresponds to the same entry. When this is not the case, a new method must be used to match entries with sequence counts. The disclosed method uses a set of virtual pointers to track which commands need to be sent and which ones can be freed. These virtual pointers work in parallel to the pointers described earlier.

    The following example contains a FIFO that is 12 entries deep and a system with 32 sequence counts. The first time a command is sent from Index 0, it has sequence count 0x00, but the next command in Index 0 would have sequence count 0x0C. The third time, sequence count 0x18 would correspond to Index 0. The same sequence c...