Age matrix for queue dispatch order

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.

1 . An apparatus for queue allocation, the apparatus comprising:
 a dispatch order data structure corresponding to a queue, the dispatch order data structure to store 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;   a bit vector to store a plurality of mask values corresponding to the dispatch indicators of the dispatch order data structure; and   a queue controller to interface with the queue and the dispatch order data structure, the queue controller to exclude at least some of the entries from a queue operation based on the mask values of the bit vector.   
     
     
         2 . The apparatus according to  claim 1 , wherein the queue operation comprises a dispatch operation to write a new entry in the queue. 
     
     
         3 . The apparatus according to  claim 1 , wherein the mask values of the bit vector comprise a replay mask to mask a dispatch indictor for an entry of the queue associated with a replay operation. 
     
     
         4 . The apparatus according to  claim 1 , wherein the mask values of the bit vector comprise an atomic flush mask to mask a dispatch indicator for an entry of the queue associated with an atomic flush operation. 
     
     
         5 . The apparatus according to  claim 1 , wherein the mask values of the bit vector comprise a hazard mask to mask a dispatch indicator for an entry of the queue associated with prevention of a hazard event. 
     
     
         6 . The apparatus according to  claim 5 , wherein the hazard event comprises a structural hazard event. 
     
     
         7 . The apparatus according to  claim 5 , wherein the hazard event comprises a data hazard event. 
     
     
         8 . The apparatus according to  claim 5 , wherein the hazard event comprises a control hazard event. 
     
     
         9 . The apparatus according to  claim 1 , wherein the mask values of the bit vector comprise a thread mask to mask a subset of dispatch indicators for corresponding entries of the queue associated with a thread of a plurality of threads in a multi-threaded processing system. 
     
     
         10 . The apparatus according to  claim 1 , further comprising a flop bank with a plurality of flip-flops, each flip-flop to store a bit value indicative of the dispatch order of the entries of a corresponding pair of entries. 
     
     
         11 . The apparatus according to  claim 10 , the queue controller further comprising dispatch logic to interface with the dispatch order data structure, the dispatch logic to flip the bit value for at least one of the dispatch indicators in response to the queue operation to write the new entry in the queue. 
     
     
         12 . The apparatus according to  claim 11 , further comprising a random access memory (RAM) device to store the queue and the dispatch order data structure, wherein the queue comprises a fully associative RAM structure and the dispatch order data structure comprises a control structure separate from the fully associative RAM structure. 
     
     
         13 . The apparatus according to  claim 1 , further comprising a mapper coupled to the queue, the mapper to dispatch the queue operation to insert a new entry in the queue. 
     
     
         14 . The apparatus according to  claim 1 , the queue controller further comprising least recently used (LRU) logic, the LRU logic to implement a queue entry replacement strategy for the queue based on the dispatch order data structure, wherein the queue entry replacement strategy comprises a true LRU replacement strategy or a pseudo LRU replacement strategy. 
     
     
         15 . A method for managing a dispatch order of entries in a queue, the method comprising:
 storing a plurality of dispatch indicators corresponding to pairs of entries in a queue, each dispatch indicator indicative of the dispatch order of the corresponding pair of entries;   storing a bit vector comprising a plurality of mask values corresponding to the dispatch indicators of the dispatch order data structure; and   performing a queue operation on a subset of the entries in the queue, wherein the subset excludes at least some of the entries of the queue based on the mask values of the bit vector.   
     
     
         16 . The method according to  claim 15 , wherein performing the queue operation comprises dispatching a new entry into the queue. 
     
     
         17 . The method according to  claim 16 , further comprising masking a replay instruction stored in an entry of the queue to avoid dispatching the new entry in the location of the replay instruction. 
     
     
         18 . The method according to  claim 16 , further comprising masking an instruction stored in an entry of the queue from an atomic flush operation to flush a plurality of instructions from the queue. 
     
     
         19 . The method according to  claim 16 , further comprising masking an instruction stored in an entry of the queue to prevent a hazard event. 
     
     
         20 . The method according to  claim 19 , wherein the hazard event comprises a structural hazard, a data hazard, or a control hazard. 
     
     
         21 . The method according to  claim 16 , further comprising masking a plurality of instructions associated with a first thread to give priority to instructions associated with a second thread. 
     
     
         22 . The method according to  claim 15 , further comprising storing the dispatch indicators in a dispatch order data structure corresponding to a representation of at least a partial matrix with intersecting rows and columns, each row corresponding to one of the entries of the queue and each column corresponding to one of the entries of the queue, the intersections of the rows and columns corresponding to the pairs of entries in the queue. 
     
     
         23 . The method according to  claim 15 , further comprising storing the dispatch indicators in a plurality of flip-flops of a flop bank, each flip-flop comprising a bit value indicative of the dispatch order of the corresponding pair of entries. 
     
     
         24 . The method according to  claim 15 , further comprising implementing a least recently used (LRU) replacement strategy for the queue based on at least some of the dispatch indicators. 
     
     
         25 . A computer readable storage medium embodying a program of machine-readable instructions, executable by a digital processor, to perform operations to facilitate queue allocation, the operations comprising:
 store a plurality of dispatch indicators corresponding to pairs of entries in a queue, each dispatch indicator indicative of the dispatch order of the corresponding pair of entries;   store a bit vector comprising a plurality of mask values corresponding to the dispatch indicators of the dispatch order data structure; and   perform a queue operation on a subset of the entries in the queue, wherein the subset excludes at least some of the entries of the queue based on the mask values of the bit vector.   
     
     
         26 . The computer readable storage medium according to  claim 25 , the operations further comprising an operation to dispatch a new entry into the queue. 
     
     
         27 . The computer readable storage medium according to  claim 25 , the operations further comprising an operation to mask a replay instruction stored in an entry of the queue to avoid dispatching the new entry in the location of the replay instruction. 
     
     
         28 . The computer readable storage medium according to  claim 25 , the operations further comprising an operation to mask an instruction stored in an entry of the queue from an atomic flush operation to flush a plurality of instructions from the queue. 
     
     
         29 . The computer readable storage medium according to  claim 25 , the operations further comprising an operation to mask an instruction stored in an entry of the queue to prevent a hazard event. 
     
     
         30 . The computer readable storage medium according to  claim 29 , the operations further comprising an operation to mask a plurality of instructions associated with a first thread to give priority to instructions associated with a second thread.