Computer implemented method of electing K extreme entries from a list using separate section comparisons

Abstract

A computer implemented method selects K extreme elements of a list of N elements by partitioning each of the N elements into a plurality of sections. For each section the method selects a threshold selection determining at least K extreme entries from the list. This iteratively compares a corresponding section to a section threshold, counts a number of sections which are more extreme than the section threshold, increasing (or decreasing) the section threshold if the count is greater than K and decreasing (or increasing) the section threshold if the count is less than K. The method forms a combined threshold by concatenation of said section thresholds in order, compares each of the N elements to the combined threshold, and selects at least K elements from the set of N elements more extreme than the combined threshold.

What is claimed is: 
     
       1. A computer implemented method of selecting K greatest elements of a list of N elements comprising the steps of:
 partitioning each of the N elements into a plurality of sections; 
 for each section of the N elements from a most significant section to a least significant section iteratively
 comparing a corresponding section of each of the N elements to a section threshold, 
 counting a number of sections of the N elements which are not less than the section threshold, 
 increasing the section threshold if the count of sections of the N elements is not less than the section threshold is greater than K, 
 decreasing the section threshold if the count of sections of the N elements is not less than the section threshold is less than K, 
 until a section threshold having at least K elements not less than said section threshold is determined for the corresponding section; 
 
 forming a combined threshold by concatenation of said section thresholds in order from a most significant section to a least significant section; 
 comparing each of the N elements to the combined threshold; and 
 selecting K elements from the set of N elements not less than the combined threshold. 
 
     
     
       2. The computer implemented method of  claim 1 , wherein said step of iteratively for each section of the N elements from a most significant section to a least significant section further includes:
 setting an initial section threshold to a number one half of a maximum number expressible by the number of bits of the corresponding section. 
 
     
     
       3. The computer implemented method of  claim 2 , wherein:
 said step of iteratively for each section of the N elements from a most significant section to a least significant section wherein:
 said step of increasing the section threshold increases the section threshold by adding an adjustment factor to a prior section threshold and setting a next adjustment factor to half a current adjustment factor, an initial adjustment equal to half the initial section threshold; and 
 said step of decreasing the section threshold decreases the section threshold by subtracting an adjustment factor from a prior section threshold and setting a next adjustment factor to half a current adjustment factor. 
 
 
     
     
       4. The computer implemented method of  claim 1 , wherein:
 the computer implements a multiple compare instruction operable to compare plural sections of two source data registers and pack a result of each section comparison in a corresponding bit of a destination data register; and 
 said step of comparing a corresponding section of each of the N elements to a section threshold includes
 packing corresponding sections of list entries into plural data words, and 
 performing the multiple compare instruction on one of the plural packed data words as first data register and a second data register having the corresponding section threshold repeated in each corresponding section; and 
 
 said step of counting a number of sections of the N elements which are not less than the section threshold includes counting bits within at least one destination register of the multiple compare instruction. 
 
     
     
       5. The computer implemented method of  claim 4 , wherein:
 said step of performing the multiple compare instruction on one of the plural packed data words produces a single bit result for each said comparison which is stored in a destination data register; 
 the method further comprising
 shifting the destination data register following each multiple compare instruction to present a set of bits equal to a number of sections of the multiple compare instruction for a subsequent multiple compare instruction until the destination data register is full of the single bit results, and 
 thereafter selecting a new destination data register. 
 
 
     
     
       6. The computer implemented method of  claim 4 , wherein:
 the computer implements a bit count instruction by counting a number of bits having a 1 state in a source register and storing this count in a destination register; and 
 said step of counting a number of sections of the N elements includes performing said bit count instruction on each destination register of a multiple compare instruction. 
 
     
     
       7. The computer implemented method of  claim 4 , wherein:
 the computer implements a multiple addition instruction by adding corresponding sections of two source data registers and storing a sum in a corresponding section of a destination register; 
 the computer implements a section bit count instruction by counting a number of bits having a 1 state in each section of a source register and storing this count in a corresponding section of a destination register; and 
 said step of counting a number of sections of the N elements includes
 performing said bit count instruction on each destination register of a multiple compare instruction, 
 performing said multiple addition instruction of each destination register of each section bit count instruction destination register, and 
 adding counts of each section of a destination register of a final multiple addition instruction. 
 
 
     
     
       8. The computer implemented method of  claim 4 , wherein:
 for each section of the N elements following determination of said section threshold having at least K elements not less than said section threshold setting to zero a next less significant section of elements not said at least K elements. 
 
     
     
       9. The computer implemented method of  claim 4 , wherein:
 said computer implements a mask instruction by copying each of a predetermined number of bits of a source data register into a corresponding section of a destination register, repeating said source register bit to fill said destination register section; 
 said step of setting to zero a next less significant section of elements not said at least K elements includes
 performing a multiple compare instruction for each section with said section threshold; 
 performing a mask instruction upon each destination register of the multiple compare instruction; 
 ANDing the destination register of the mask instruction with each packing corresponding sections of list entries and storing results to replace the packing corresponding sections of list entries. 
 
 
     
     
       10. The computer implemented method of  claim 1 , wherein:
 each entry consists of 32 bits; and 
 each section of each entry consists of 8 bits. 
 
     
     
       11. The computer implemented method of  claim 1 , wherein:
 said step of iteratively for each section of the N elements from a most significant section to a least significant section further includes setting a maximum number of iterations for section threshold adjustment to the largest integer not greater than the base-2 logarithm of M, where M is the maximum number expressible by the number of bits of the corresponding section. 
 
     
     
       12. The computer implemented method of  claim 4 , wherein:
 said step of comparing a corresponding section of each of the N elements to a section threshold further includes following said packing step and before performing said multiple compare instruction
 adding 1 to each section of the N elements through a multiple saturation-add instruction which saturates to a maximum number expressible by the number of bits of the corresponding section. 
 
 
     
     
       13. The computer implemented method of  claim 12 , wherein:
 said step of forming a combined threshold further includes following said concatenation step
 subtracting 1 from each section of said concatenation of said section thresholds through a multiple subtraction instruction. 
 
 
     
     
       14. A computer implemented method of selecting K least elements of a list of N elements comprising the steps of:
 partitioning each of the N elements into a plurality of sections; 
 for each section of the N elements from a most significant section to a least significant section iteratively
 comparing a corresponding section of each of the N elements to a section threshold, 
 counting a number of sections of the N elements which are not greater than the section threshold, 
 decreasing the section threshold if the count of sections of the N elements is not greater than the section threshold is greater than K, 
 increasing the section threshold if the count of sections of the N elements is not greater than the section threshold is less than K, 
 until a section threshold having at least K elements not greater than said section threshold is determined for the corresponding section; 
 
 forming a combined threshold by concatenation of said section thresholds in order from a most significant section to a least significant section; 
 comparing each of the N elements to the combined threshold; and 
 selecting K elements from the set of N elements not greater than the combined threshold. 
 
     
     
       15. The computer implemented method of  claim 14 , wherein:
 said step of iteratively for each section of the N elements from a most significant section to a least significant section further includes setting an initial section threshold to a number one half of a maximum number expressible by the number of bits of the corresponding section. 
 
     
     
       16. The computer implemented method of  claim 15 , wherein:
 said step of iteratively for each section of the N elements from a most significant section to a least significant section wherein:
 said step of increasing the section threshold increases the section threshold by adding an adjustment factor to a prior section threshold and setting a next adjustment factor to half a current adjustment factor, an initial adjustment equal to half the initial section threshold; and 
 said step of decreasing the section threshold decreases the section threshold by subtracting an adjustment factor from a prior section threshold and setting a next adjustment factor to half a current adjustment factor. 
 
 
     
     
       17. The computer implemented method of  claim 14 , wherein:
 the computer implements a multiple compare instruction operable to compare plural sections of two source data registers and pack a result of each section comparison in a corresponding bit of a destination data register; and 
 said step of comparing a corresponding section of each of the N elements to a section threshold includes
 packing corresponding sections of list entries into plural data words, and 
 performing the multiple compare instruction on one of the plural packed data words as first data register and a second data register having the corresponding section threshold repeated in each corresponding section; and 
 
 said step of counting a number of sections of the N elements which are not greater than the section threshold includes counting bits within at least one destination register of the multiple compare instruction. 
 
     
     
       18. The computer implemented method of  claim 17 , wherein:
 said step of performing the multiple compare instruction on one of the plural packed data words produces a single bit result for each said comparison which is stored in a destination data register; 
 the method further comprising
 shifting the destination data register following each multiple compare instruction to present a set of bits equal to a number of sections of the multiple compare instruction for a subsequent multiple compare instruction until the destination data register is full of the single bit results, and 
 thereafter selecting a new destination data register. 
 
 
     
     
       19. The computer implemented method of  claim 17 , wherein:
 the computer implements a bit count instruction by counting a number of bits having a 1 state in a source register and storing this count in a destination register; and 
 said step of counting a number of sections of the N elements includes performing said bit count instruction on each destination register of a multiple compare instruction. 
 
     
     
       20. The computer implemented method of  claim 17 , wherein:
 the computer implements a multiple addition instruction by adding corresponding sections of two source data registers and storing a sum in a corresponding section of a destination register; 
 the computer implements a section bit count instruction by counting a number of bits having a 1 state in each section of a source register and storing this count in a corresponding section of a destination register; and 
 said step of counting a number of sections of the N elements includes
 performing said bit count instruction on each destination register of a multiple compare instruction, 
 performing said multiple addition instruction of each destination register of each section bit count instruction destination register, and 
 adding counts of each section of a destination register of a final multiple addition instruction. 
 
 
     
     
       21. The computer implemented method of  claim 17 , wherein:
 for each section of the N elements following determination of said section threshold having at least K elements not greater than said section threshold setting to zero a next less significant section of elements not said at least K elements. 
 
     
     
       22. The computer implemented method of  claim 21 , wherein:
 said computer implements a mask instruction by copying each of a predetermined number of bits of a source data register into a corresponding section of a destination register, repeating said source register bit to fill said destination register section; 
 said step of setting to zero a next less significant section of elements not said at least K elements includes
 performing a multiple compare instruction for each section with said section threshold; 
 performing a mask instruction upon each destination register of the multiple compare instruction; 
 ANDing the destination register of the mask instruction with each packing corresponding sections of list entries and storing results to replace the packing corresponding sections of list entries. 
 
 
     
     
       23. The computer implemented method of  claim 17 , wherein:
 said step of comparing a corresponding section of each of the N elements to a section threshold further includes following said packing step and before performing said multiple compare instruction
 subtracting 1 from each section of the N elements through a multiple saturation-subtract instruction which saturates to a minimum number expressible by the number of bits of the corresponding section. 
 
 
     
     
       24. The computer implemented method of  claim 23 , wherein:
 said step of forming a combined threshold further includes following said concatenation step
 adding 1 to each section of said concatenation of said section thresholds through a multiple addition instruction. 
 
 
     
     
       25. The computer implemented method of  claim 14 , wherein:
 each entry consists of 32 bits; and 
 each section of each entry consists of 8 bits. 
 
     
     
       26. The computer implemented method of  claim 14 , wherein:
 said step of iteratively for each section of the N elements from a most significant section to a least significant section further includes setting a maximum number of iterations for section threshold adjustment to the largest integer not greater than the base-2 logarithm of M, where M is the maximum number expressible by the number of bits of the corresponding section.