Fast sparse list walker

• US 7,743,231 B2
• Filed: 02/27/2007
• Issued: 06/22/2010
• Est. Priority Date: 02/27/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rider, Scot H., Strader, Todd A.
• Primary Examiner(s): Li; Aimee J
• Application Number:
  US11/679,282
• Publication Number:
  US 20080209183A1
• Time in Patent Office: 1,211 Days
• Field of Search: 712/2, 712 4- 6, 712224-225, 712/300
• US Class Current: 712/6
• CPC Class Codes: G06F 7/74 Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders with shifting G06F5/01

Abstract

Provided are a method, information processing system, and computer readable medium for identifying active bits in a vector. The method comprises receiving a pointer associated with a vector of bits. The pointer is associated with a current bit within the vector of bits. The vector of bits if grouped into groups of a mathematical power of two, which is any non-negative integer powers of two. One or more current groups are determined which are the groups of the mathematical power of two comprising the current bit. The one or more current groups of the power of two are analyzed. A largest group of the power of two is identified in the one or more current groups comprising all empty bits. The pointer is set to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.

Claims

1. A computer implemented method for identifying active bits in a vector, the computer implemented method comprising:

executing on an information processing system the following;

receiving a pointer associated with a vector of bits, wherein the pointer is associated with a current bit within the vector of bits;

grouping the vector of bits into groups of a mathematical power of two, which is any non-negative integer powers of two;

determining one or more current groups which are the groups of the mathematical power of two comprising the current bit;

analyzing, in response to receiving the pointer, the one or more current groups of the power of two;

identifying, in response to the analyzing, a largest group of the power of two in the one or more current groups comprising all empty bits; and

setting the pointer to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.

2. The computer implemented method of claim 1, wherein the pointer which was received is a pointer set to the bit following the last bit in the identified largest group of the power of two comprising all empty bits.

3. The computer implemented method of claim 1, further comprising:

receiving the vector of bits from a data source.

4. The computer implemented method of claim 1, wherein the grouping further comprises:

dividing the vector of bits into at least a first group of bits and a second group of bits.

5. The computer implemented method of claim 4, wherein the analyzing further comprises:

determining a group from the first group of bits and the second group of bits that includes the current bit associated with the pointer.

6. The computer implemented method of claim 5, wherein the setting the pointer further comprises:

determining that the group comprises all empty bits; and

setting, in response to the determining that the group comprises all empty bits, the pointer to a first bit in a group from the first group of bits and the second group of bits that does not include the current bit associated with the pointer.

7. The computer implemented method of claim 5, wherein the analyzing further comprises:

determining that the group comprises at least one active bit;

dividing the group into a set of subsequent power of two groups; and

identifying a subsequent power of two group in the set of subsequent power of two groups including the current bit associated with the pointer.

8. The computer implemented method of claim 7, wherein the setting the pointer further comprises:

analyzing the subsequent power of two group;

determining, based on the analyzing, that a current power of two group including the current bit associated with the pointer comprises at least one active bit; and

setting, in response to the determining, the pointer to a bit subsequent to the current bit associated with the pointer.

9. The computer implemented method of claim 1, further comprising:

setting the pointer to point to a bit in another group of the power of two;

masking the current bit associated with the pointer;

identifying a largest current group of the power of two that comprises all empty bits; and

setting, in response to identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.

10. The computer implemented method of claim 1, further comprising:

setting the pointer to point to a bit in another group of the power of two;

masking the current bit associated with the pointer and all bits preceding the current bit in a current half of the vector of bits;

identifying a largest current group of the power of two that comprises all empty bits; and

setting, in response to the identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.

11. A computer readable medium for identifying active bits in a vector, the computer readable medium comprising instructions for:

receiving a pointer associated with a vector of bits, wherein the pointer is associated with a current bit within the vector of bits;

grouping the vector of bits into groups of a mathematical power of two, which is any non-negative integer powers of two;

determining one or more current groups which are the groups of the mathematical power of two comprising the current bit;

analyzing, in response to receiving the pointer, the one or more current groups of the power of two;

identifying, in response to the analyzing, a largest group of the power of two in the one or more current groups comprising all empty bits; and

setting the pointer to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.

12. The computer readable medium of claim 11, wherein the instructions for the grouping further comprise instructions for:

dividing the vector of bits into at least a first group of bits and a second group of bits.

13. The computer readable medium of claim 11, further comprising instructions for:

setting the pointer to point to a bit in another group of the power of two;

masking the current bit associated with the pointer;

identifying a largest current group of the power of two that comprises all empty bits; and

setting, in response to identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.

14. The computer readable medium of claim 11, further comprising instructions for:

setting the pointer to point to a bit in another group of the power of two;

masking the current bit associated with the pointer and all bits preceding the current bit in a current half of the vector of bits;

identifying a largest current group of the power of two that comprises all empty bits; and

setting, in response to the identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.

15. An information processing system for identifying active bits in a vector, the information processing system comprising:

a memory;

a processor communicatively coupled to the memory; and

a circuit communicatively coupled to the memory and the processor, wherein the circuit is adapted to;

receive a pointer associated with a vector of bits, wherein the pointer is associated with a current bit within the vector of bits;

group the vector of bits into groups of a mathematical power of two, which is any non-negative integer powers of two;

determine one or more current groups which are the groups of the mathematical power of two comprising the current bit;

analyze, in response to receiving the pointer, the one or more current groups of the power of two;

identify, in response to the analyzing, a largest group of the power of two in the one or more current groups comprising all empty bits; and

setting the pointer to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.

16. The information processing system of claim 15, wherein the circuit is further adapted to:

analyze the vector of bits in groups of mathematical powers of two; and

identify at least one active bit within the vector of bits based on the vector of bits being analyzed in groups of mathematical powers of two.

17. The information processing system of claim 16, wherein the circuit is further adapted to group by:

dividing the vector of bits into at least a first group of bits and a second group of bits.

18. The information processing system of claim 15, wherein the pointer which was received is a pointer set to the bit following the last bit in the identified largest group of the power of two comprising all empty bits.

19. The information processing system of claim 15 wherein the circuit is further adapted to:

set, the pointer to point to a bit in another group of the power of two;

mask, the current bit associated with the pointer;

identify, a largest current group of the power of two that comprises all empty bits; and

set, in response to identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.

20. The information processing system of claim 15, wherein the circuit is further adapted to:

set the pointer to point to a bit in another group of the power of two;

mask the current bit associated with the pointer and all bits preceding the current bit in a current half of the vector of bits;

identify, a largest current group of the power of two that comprises all empty bits; and

set, in response to the identifying the largest current group of the power of two that comprises all empty bits, the pointer to point to a next bit after a last bit in the largest current group of the power of two that comprises all empty bits.