Method and apparatus for compacting a queue

Abstract

A method of compacting an instruction queue in an out of order processor includes determining the number of invalid instructions below and including each row in the queue, by counting invalid bits or validity indicators associated with rows below and up to the current row. For each row, multiplexor select signals are generated from the flat vector counts for the N rows above and including the present row, and from the validity indicators associated with the N rows, where N is a predetermined value. A multiplexor associated with a particular row selects one of the N rows according to the select value, and moves or passes the instruction held in the selected row to the present row. A row's select value is determined by forming a diagonal from the N count vectors corresponding to the N rows above and including the present row, and logically ANDing, each diagonal bit with the valid bit associated with the same row. Each row's count vector is determined in two stages. In the first stage, a local count is determined for each row in a local group of rows, and a global count is determined for the entire local group. Each local count is determined by counting the validity indicators associated with rows in the local group. In the second stage, a final count is determined for each row in the queue, by combining the local and global counts generated for the local group in the first stage, with global counts generated in local groups below the local group. The N rows can extend to the queue's input pipeline.

What is claimed is:  
     
         1 . A method of compacting an instruction queue in a processor, the queue comprising a plurality of rows for holding instructions and associated validity indicators, in which instructions may be removed from the queue out of sequence, the method comprising: 
 (a) for each row in the queue, responsive to validity indicators associated with rows below and including said row, determining a flat vector count of the number of invalid instructions below and including said row; and    (b) for each row, 
 (i) determining a select value, by 
 forming a diagonal from N counts corresponding to N rows above and including the present row, for a predetermined value N, and  
 logically ANDing each diagonal bit with a set of validity indicators to form the present row's select value, each ANDed diagonal bit and corresponding validity indicator being associated with a common row,  
 
 (ii) selecting one of the N rows responsive to the select value, and  
 (iii) moving an instruction held in the selected row to the present row.  
   
     
     
         2 . The method of  claim 1 , wherein N is a maximum of new instructions which can enter the queue during any given cycle, further comprising: 
 limiting each count to N.    
     
     
         3 . The method of  claim 1  wherein only valid queue instructions are moved.  
     
     
         4 . The method of  claim 1  wherein the N rows can extend to the queue's input pipeline.  
     
     
         5 . An apparatus for compacting an instruction queue having a plurality of rows for holding instructions, comprising; 
 for each row, 
 a validity indicator storage location for holding a validity indicator for the row,  
 a flat vector counter for holding a count of invalid instructions below and including said row, which is responsive to validity indicators associated with rows below and including said row, and  
 a multiplexor having an output for inserting an instruction into the row, and having a N inputs connected to N rows above and including the present row respectively, and having a select signal which selects one of the N rows, such that an instruction held in the selected row is moved to the present row, for a predetermined value N; and  
 update logic for generating multiplexor select signals for each row, responsive to the counters and validity indicators associated with the N rows above and including each row, wherein the update logic generates the select signals from diagonals formed across the counters.  
   
     
     
         6 . The apparatus of  claim 5  wherein each counter is limited to a maximum value of N.  
     
     
         7 . The apparatus of  claim 5 , wherein each counter comprises a barrel shifter.  
     
     
         8 . The apparatus of  claim 5 , wherein the update logic groups queue rows into local groups, the update logic further comprising for each local group: 
 plurality of first stage local adders and a local global adder which count invalid instructions in the queue for the local group; and    second stage adders which add global counts from groups below to local and global counts generated from the first stage adders of the local group, the output of each second stage adder forming the flat vector counters associated respectively with the rows in the local group.    
     
     
         9 . The apparatus of  claim 5  wherein only valid queue instructions are moved.  
     
     
         10 . The apparatus of  claim 5  wherein the N rows can extend to the queue's input pipeline.  
     
     
         11 . An instruction queue compaction circuit, the queue comprising a plurality of rows for holding instructions and associated validity indicators, in which instructions may be removed from the queue out of sequence, comprising: 
 (a) an update logic circuit, further comprising: 
 for each row in the queue, a counting circuit which, responsive to validity indicators associated with rows below and including said row, determines a count of the number of invalid instructions below and including said row; and  
 for each row, a multiplexor select circuit which determines a select value responsive to a diagonal formed across the counting circuits associated with the N rows above and including the instant row, and responsive to the validity indicators associated with the N rows, for a predetermined value N; and  
   (b) for each row, a multiplexor circuit which, responsive to the multiplexor select circuit, moves an instruction to the instant row.    
     
     
         12 . A system board comprising an integrated circuit, which includes an instruction queue compaction circuit for compacting an instruction queue in an out-of-order processor, the instruction queue compaction circuit comprising: 
 (a) an update logic circuit which generates, for each row in the queue, multiplexor select signals, the update logic circuit further comprising: 
 for each row, a counter circuit which generates a flat vector count, responsive to validity indicators associated with rows below and including the row, the count indicating the number of invalid instructions below and including said row; and  
 for each row, a multiplexor select circuit which determines a select value responsive to a diagonal formed across the counting circuits associated with the N rows above and including the instant row, and responsive to the validity indicators associated with the N rows, for a predetermined value N; and  
   (b) for each row, a multiplexor circuit which, responsive to the multiplexor select signals, moves an instruction to the present row.