Age matrix for queue entries dispatch order
AssigneeNetLogic Microsystems, Inc.
InventorsGaurav Singh, Srivatsan Srinivasan, Lintsung Wong
Life of this patent
Estimating the term…
Abstract
An apparatus for queue allocation. An embodiment of the apparatus includes a dispatch order data structure, a bit vector, and a queue controller. The dispatch order data structure corresponds to a queue. The dispatch order data structure stores a plurality of dispatch indicators associated with a plurality of pairs of entries of the queue to indicate a write order of the entries in the queue. The bit vector stores a plurality of mask values corresponding to the dispatch indicators of the dispatch order data structure. The queue controller interfaces with the queue and the dispatch order data structure. The queue controller excludes at least some of the entries from a queue operation based on the mask values of the bit vector.
Claims33
An apparatus comprising:
- a queue to store a plurality of entries;
- a dispatch order structure corresponding to the queue, the dispatch order structure comprising indicator entries to store a plurality of indicators associated with a plurality of different pairs of entries of the queue to indicate a dispatch order of the entries, wherein at least one of the indicators indicates the relative age for the corresponding different pairs of entries in the queue such that respective indicators of the plurality of indicators of the dispatch order structure have either a first value or a second value, the first value indicating an entry is older than another entry and the second value indicating the entry is younger than the another entry, wherein the dispatch order structure comprises a representation of a partial matrix and masked duplicate entries, the partial matrix to store a portion of a matrix of rows and columns and to mask duplicate entries of the matrix;
- and
- a controller to interface with the queue and the dispatch order structure, the controller to update the dispatch order structure in response to an operation to insert a new entry in the queue.
A method comprising:
- storing a plurality of entries in a queue;
- identifying different pairs of entries in the queue;
- storing a plurality of indicators corresponding to the different pairs of entries in a dispatch order structure, in which the dispatch order structure comprises a partial matrix and masked duplicate entries such that the partial matrix stores a portion of a matrix of rows and columns and duplicate entries are masked, at least one of the plurality of indicators indicative of a dispatch order of the corresponding different pairs of entries, wherein an indicator indicates the relative age for the corresponding different pairs of entries in the queue such that respective indicators of the plurality of indicators have either a first value or a second value, the first value indicating an entry is older than another entry and the second value indicating the entry is younger than the another entry;
- and
- dispatching an entry from the queue according to at least one of the plurality of indicators associated with the entry.
A non-transitory computer readable storage medium embodying a program of machine-readable instructions, executable by a digital processor, to perform operations, the operations comprising:
- storing a plurality of entries in a queue;
- identifying different pairs of entries in the queue;
- storing a plurality of indicators corresponding to the different pairs of entries in a dispatch order structure, in which the dispatch order structure comprises a partial matrix and masked duplicate entries such that the partial matrix stores a portion of a matrix of rows and columns and duplicate entries are masked, at least one of the plurality of indicators indicative of a dispatch order of the corresponding different pairs of entries, wherein an indicator indicates the relative age for the corresponding different pairs of entries in the queue such that respective indicators of the plurality of have either a first value or a second value, the first value indicating an entry is older than another entry and the second value indicating the entry is younger than the another entry;
- and
- dispatching an entry from the queue according to at least one of the plurality of indicators associated with the entry.
A non-transitory computer readable storage medium embodying a program of machine-readable instructions, executable by a digital processor, to perform operations to manage a dispatch order of a plurality of entries of a queue, the operations comprising:
- writing an entry in the queue;
- assigning a line of a matrix to the entry, the line intersecting with another line of the matrix associated with another entry in the queue;
- and
- assigning a bit value to an indicator at the intersection of the lines of the matrix to indicate a relative age of a corresponding pair of entries in the queue such that respective indicators of the plurality of indicators have either a first value or a second value, the first value indicating an entry is older than another entry and the second value indicating the entry is younger than the another entry, wherein the matrix comprises a partial matrix and masked duplicate entries, the partial matrix stores a portion of the matrix and duplicate entries of the matrix are masked.
Dependencies are inferred from the claim text.