Method and circuits for early detection of a full queue

Abstract

In a pipelined computer architecture in which instructions may be removed from the instruction queue out of sequence, instruction queue status at a cycle K is determined by adding together the number of invalid instructions or free rows in the queue during cycle K- 2 , the number of instructions issued for cycle K- 1 and the number of instructions speculatively issued in cycle K- 1 that have produced a cache hit, and subtracting from the sum the number of instructions enqueued for cycle K- 1 . The result indicates the number of invalid instructions in the queue cycle K. The number of invalid entries instructions, the number of issued instructions, and the number of enqueued instructions are preferably represented as flat vectors, so that adding is performed by shifting in one direction, while subtracting is performed by shifting in the opposite direction. The result is compared with either the number of instructions to be enqueued in the present cycle, which number is encoded, or with a predetermined value. A stall signal is generated if the indicative value is less than the encoded number or the predetermined value.

1 . In a pipelined computer architecture, a method for detecting instruction queue status at a cycle K, wherein instructions are capable of being removed from the queue out of sequence, the method comprising: 
 determining a number of invalid instructions in the queue in cycle K- 2 ;    determining a number of instructions issued from the queue in cycle K- 1 ;    determining a number of instructions enqueued in the queue in cycle K- 1 ; and    responsive to the number of invalid instructions, the number of instructions issued, and the number of enqueued instructions, determining a value indicative of a number of free rows in the queue at cycle K.    
   
   
       2 - 3 . (Cancelled).  
   
   
       4 . The method of  claim 1 , further comprising: 
 determining a count of instructions speculatively issued in cycle K- 1 , that have produced a cache hit, wherein determining the indicative value is further based on the count of speculatively issued instructions.    
   
   
       5 . The method of  claim 4 , wherein the indicative value is equal to the sum of the number of invalid instructions, the number of issued instructions, and the count of speculatively issued instructions, less the number of enqueued instructions.  
   
   
       6 . The method of  claim 1 , further comprising: 
 stalling an instruction pipeline responsive to the indicative value.    
   
   
       7 . The method of  claim 1 , further comprising 
 stalling an instruction pipeline if the indicative value is less than a predetermined value.    
   
   
       8 . The method of  claim 7 , wherein the predetermined value is related to a maximum number of instructions that can be enqueued in one cycle.  
   
   
       9 . The method of  claim 1 , further comprising 
 stalling an instruction pipeline if the indicative value is less than a count of instructions to be enqueued.    
   
   
       10 . The method of  claim 9 , further comprising encoding the count of instructions to be enqueued.  
   
   
       11 . An apparatus, in a pipelined computer architecture, for detecting instruction queue status at a cycle K, wherein instructions are capable of being removed from the queue out of sequence, comprising: 
 means for determining a number of invalid instructions in the queue in cycle K- 2 ;    means for determining a number of instructions issued from the queue in cycle K- 1 ;    means for determining a number of instructions enqueued in the queue in cycle K- 1 ; and    an adder/subtracter, responsive to the number of invalid instructions, the number of instructions issued, and the number of enqueued instructions, to determine a value indicative of the number of free rows in the queue at cycle K.    
   
   
       12 - 13 . (Cancelled).  
   
   
       14 . The apparatus of  claim 11 , further comprising: 
 an adder, responsive to a count of instructions speculatively issued in cycle K- 1  that have produced a cache hit, to for use in further determining the indicative value.    
   
   
       15 . The apparatus of  claim 14 , wherein the indicative value is equal to the sum of the number of invalid instructions, the number of issued instructions, and the count of speculatively issued instructions, less the number of enqueued instructions.  
   
   
       16 . The apparatus of  claim 11 , further comprising: 
 an instruction pipeline stalling in response to the indicative value.    
   
   
       17 . The apparatus of  claim 11 , further comprising an instruction pipeline stalling  16 , if the indicative value is less than a predetermined value.  
   
   
       18 . The apparatus of  claim 17 , wherein the predetermined value is related to a maximum number of instructions that can be enqueued in one cycle.  
   
   
       19 . The apparatus of  claim 11 , further comprising an instruction pipeline stalling if the indicative value is less than the count of instructions to be enqueued.  
   
   
       20 . The apparatus of  claim 19 , further comprising: 
 an encoder which encodes the count of instructions to be enqueued.    
   
   
       21 . In a pipelined computer, a queue status detection circuit for detecting instruction queue status at a cycle K, comprising: 
 a counter circuit for determining a number of free entries in the queue in cycle K- 2 ;    a counter circuit for determining a number of instructions issued cycle K- 1 ;    a counter circuit for determining a number of instructions enqueued in the queue in cycle K- 1 ; and    an adder/subtracter circuit, responsive to the number of free entries, the number of instructions issued, and the number of enqueued instructions, to determine a value indicative of the number of free entries in the queue at cycle K.    
   
   
       22 - 23 . (Cancelled).  
   
   
       24 . The queue status detection circuit of  claim 21 , further comprising: 
 an adder circuit, responsive to a count of instructions speculatively issued in cycle K- 1  that have produced a cache hit, for use in further determining the indicative value.    
   
   
       25 .- 33 . (Cancelled)