Minimum processor instruction for implementing weighted fair queuing and other priority queuing

Abstract

The present invention provides techniques for efficiently determining a minimum or maximum of a plurality of values and the index of the minimum using registers of a processor. The present invention also provides for various processor instructions for determining the minimum/maximum and index of two or more values. The present invention finds particular benefit in implementing heaps and in systems utilizing Weighted Fair Queuing (WFQ).

1 . A processor for determining a minimum value of a plurality of values stored in source registers and determining an index value of source register having the minimum value, the processor comprising: 
 means for determining a first minimum value of a first value and a second value;    means for determining a second minimum value of a third value and a fourth value;    means for storing the first minimum value in a first portion of a first destination register and the second minimum value in a second portion of the first destination register; and    means for storing a first index value associated with the first minimum value in a first portion of a second destination register and a second index value associated with the second minimum value in a second portion of the second destination register;    wherein the means for determining the first minimum value and the means for determining the second minimum value are adapted to execute in parallel.    
     
     
         2 . The processor of  claim 1 , wherein the means for determining and the means for storing are adapted to execute sequentially within one processor cycle.  
     
     
         3 . The processor of  claim 1 , wherein each of the first, second, third, and fourth values includes an active status bit to indicate a status, and wherein a value having an active status is less than a value having an inactive status.  
     
     
         4 . The processor of  claim 1 , wherein a value having “11” as its two most significant bits is less than a value having “00” as its two most significant bits.  
     
     
         5 . The processor of  claim 1 , wherein the first source register and the destination register comprise a same register.  
     
     
         6 . The processor of  claim 1 , wherein the second source register and the destination register comprise a same register.  
     
     
         7 . A processor for determining a maximum value of a plurality of values stored in source registers and determining an index value of source register having the maximum value, the processor comprising: 
 means for determining a first maximum value of a first value and a second value;    means for determining a second maximum value of a third value and a fourth value;    means for storing the first maximum value in a first portion of a first destination register and the second maximum value in a second portion of the first destination register; and    means for storing a first index value associated with the first maximum value in a first portion of a second destination register and a second index value associated with the second maximum value in a second portion of the second destination register;    wherein the means for determining the first maximum value and the means for determining the second maximum value are adapted to execute in parallel.    
     
     
         8 . The processor of  claim 7 , wherein the means for determining and the means for storing are adapted to execute sequentially within one processor cycle.  
     
     
         9 . The processor of  claim 7 , wherein each of the first, second, third, and fourth values includes an active status bit to indicate a status, and wherein a value having an active status is greater than a value having an inactive status.  
     
     
         10 . The processor of  claim 7 , wherein a value having “11” as its two most significant bits is greater than a value having “00” as its two most significant bits.  
     
     
         11 . The processor of  claim 7 , wherein the first source register and the destination register comprise a same register.  
     
     
         12 . The processor of  claim 7 , wherein the second source register and the destination register comprise a same register.