Carry-less population count

Patent metadata

Field	Value
Publication number	US-2018062664-A1
Application number	US-201615247192-A
Country	US
Kind code	A1
Filing date	Aug 25, 2016
Priority date	Aug 25, 2016
Publication date	Mar 1, 2018
Grant date	—

Abstract

Technical solutions are described for determining a population count of an input bit-string. In an example, a population count circuit receives a single n-bit input data word including of bits A[n−1:0]. The population count circuit isolates a pair of 4-bit nibbles. The population count circuit includes a carryless counter circuit that determines a pair of counts of 1s, one for each 4-bit nibble. The population circuit further includes an adder circuit that determines the population count by summing the pair of counts of 1s from the carryless counter circuit, where the adder circuit determines the most significant bit (MSB) of the sum based on the MSBs of the counts of 1s only, without depending on carry propagation.

First claim

What is claimed is:

1 . A population count circuit that determines a population count of an input bit-string, wherein:
the population count circuit is configured to output the population count, wherein the population count is a number of is in the input bit-string; and the population count circuit comprises:
input interface configured to receive a single n-bit input data word comprising of bits A[n−1:0],
a logic device configured to isolate a pair of 4-bit nibbles of an n-bit input bit-string;
a carryless counter circuit configured to determine a pair of counts of 1s, one for each 4-bit nibble from the pair of 4-bit nibbles; and
an adder circuit configured to determine the population count by summing the pair of counts of 1s from the carryless counter circuit corresponding to each 4-bit nibble, wherein the adder circuit determines the most significant bit (MSB) of the sum based on the MSBs of the counts of 1s only, without depending on carry propagation.

2 . The population count circuit of claim 1 , wherein the carryless counter circuit comprises logic gates configured to receive a 4-bit nibble from the n-bit input bit-string and output a corresponding 3-bit population count value.

3 . The population count circuit of claim 2 , wherein the adder circuit is a 4-bit adder that receives the pair of counts of 1s as 3-bit count values from the carryless counter circuit and outputs the sum as a 4-bit value.

4 . The population count circuit of claim 1 , wherein the adder circuit computes the MSB of the sum by computing a bitwise AND operation on the MSBs of the counts of 1s.

5 . The population count circuit of claim 4 , wherein the adder circuit computes a first carry bit by computing a bitwise AND operation on the least significant bits of the counts of 1s.

6 . The population count circuit of claim 1 , further comprising a tree of log 2 (n/4) levels of adders for the n-bit input bit-string, wherein output of a first level of adders is input to a second level of adders, the second level being successive to the first level.

7 . The population count circuit of claim 6 , wherein a number of bits output by adders in each successive level of the tree increases by 1 bit.

8 . The population count circuit of claim 7 , wherein a maximum value of an output of adders at n th level is limited to 2 (n+2) .

9 . The population count circuit of claim 7 , wherein population count values for each byte of the n-bit input bit-string are generated at level 1 of the tree of adders.

10 . The population count circuit of claim 7 , wherein population count values for each half word of the n-bit input bit-string are generated at level 2 of the tree of adders.

11 . The population count circuit of claim 7 , wherein population count values for each word of the n-bit input bit-string are generated at level 3 of the tree of adders.

12 . The population count circuit of claim 7 , wherein population count values for each double word of the n-bit input bit-string are generated at level 4 of the tree of adders.

13 . A system for facilitating determination of population count of a bit-string, the system comprising:
a register file; and a processor coupled with the register file, the processor configured to:
receive a command to determine the population count of the bit-string;
determine a pair of counts of 1s, one for each 4-bit nibble from a pair of 4-bit nibbles from the bit-string; and
add the pair of counts of 1s corresponding to each 4-bit nibble, by determining the most significant bit (MSB) of the sum based on the MSBs of the counts of 1s only, without depending on carry propagation.

14 . The system of claim 13 , further comprising a population count circuit that comprises a 4:3 carryless counter circuit configured to receive a 4-bit nibble and output a corresponding 3-bit population count value.

15 . The system of claim 14 , further comprising a tree of adders, the tree comprising log 2 (n/4) levels, where n is a number of bits in the bit-string, and wherein each adder in the tree adds two population counts.

16 . The system of claim 13 , wherein the command specifies a register as an operand, wherein the register contains the bit-string for which the population count is to be determined.

17 . The system of claim 13 , wherein the command specifies a register as an operand, wherein the register contains a memory address of a memory location that contains the bit-string for which the population count is to be determined.

18 . A computer program product for determining a population count for a bit-string, the computer program product comprising a computer readable storage medium, the computer readable storage medium comprising computer executable instructions, wherein the computer readable storage medium comprises instructions to:
divide an input bit-string into 4-bit nibbles;
determine 3-bit population count values corresponding to the 4-bit nibbles respectively;
propagate the 3-bit population count values through a sequential tree of additions, where the tree comprises log 2 (n/4) levels, wherein n is a number of bits in the input bit-string, and wherein:
at level k of the tree, population count results from a level k−1 of the tree in consecutive pairs are used to determine the most significant bit (MSB) of the sum based on the MSBs of the count values only, without depending on carry propagation; and
at level k of the tree, results from a level k−1 of the tree are added for sum bits other than the MSB; and
output result of additions at level log 2 (n/4) of the tree as the population count of the input bit-string.

19 . The computer program product of claim 18 , wherein at the level 1, the MSB of the sum is determined by computing a bitwise AND operation on the MSBs of the 3-bit counts values.

20 . The computer program product of claim 18 , wherein a number of bits output by additions in each successive level of the tree increases by 1 bit.

Assignees

• IBM

Inventors

• Singh Deepak K
• Denneau Monty M
• Rogers Brian M

Classifications

• G06F7/607 Primary

  number-of-ones counters, i.e. devices for counting the number of input lines set to ONE among a plurality of input lines, also called bit counters or parallel counters (for applications thereof, see the relevant places, e.g. G06F7/49, G06F7/5013, G06F7/509, H03M1/00, H03M7/20) · CPC title

• H03M7/46 Primary

  Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind · CPC title

• G06F7/00

  Methods or arrangements for processing data by operating upon the order or content of the data handled (logic circuits H03K19/00) · CPC title