Minimum processor instruction for implementing weighted fair queuing and other priority queuing
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.