APPARATUSES AND METHODS FOR DETERMINING POPULATION COUNT

• US 20160062692A1
• Filed: 08/24/2015
• Published: 03/03/2016
• Est. Priority Date: 09/03/2014
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Finkbeiner, Timothy P., Hush, Glen E., Murphy, Richard C.
• Granted Patent: US 10,068,652 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G11C 16/26 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 7/06 Sense amplifiers; Associated circuits , e.g. timing or triggering circuits
• CPC Class Codes: G11C 7/065 Differential amplifiers of latching type
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor
• CPC Class Codes: G11C 7/1009 Data masking during input/output
• CPC Class Codes: G11C 7/12 Bit line control circuits, e.g. drivers, boosters, pull-up circuits, pull-down circuits, precharging circuits, equalising circuits, for bit lines

Abstract

The present disclosure includes apparatuses and methods related to determining population count. An example apparatus comprises an array of memory cells coupled to sensing circuitry. The apparatus can include a controller configured to cause: summing, in parallel, of data values corresponding to respective ones of a plurality of first vectors stored in memory cells of the array as a data value sum representing a population count thereof, wherein a second vector is stored as the plurality of first vectors, and wherein each first vector of the plurality of first vectors is stored in respective memory cells of the array that are coupled to a respective sense line of a plurality of sense lines; and iteratively summing, in parallel, of data value sums corresponding to the plurality of first vectors to provide a single data value sum corresponding to the second vector.

Claims

1. An apparatus, comprising:

an array of memory cells coupled to sensing circuitry; and

a controller configured to cause;

summing, in parallel, of data values corresponding to respective ones of a plurality of first vectors stored in memory cells of the array as a data value sum representing a population count thereof, wherein a second vector is stored as the plurality of first vectors, and wherein each first vector of the plurality of first vectors is stored in respective memory cells of the array that are coupled to a respective sense line of a plurality of sense lines; and

iteratively summing, in parallel, of data value sums corresponding to the plurality of first vectors to provide a single data value sum corresponding to the second vector.

2. The apparatus of claim 1, wherein the apparatus is configured to sum data values corresponding to respective ones of the plurality of first vectors without transferring data values via an input/output (I/O) line outside the array and sensing circuitry.

3. The apparatus of claim 1, wherein the apparatus is configured to iteratively sum the data value sums in parallel without transferring data values via an input/output (I/O) line outside the array and sensing circuitry.

4. The apparatus of claim 1, wherein the apparatus is configured to perform the summing acts without transferring data values to a control component external to the array and sensing circuitry.

5. The apparatus of claim 4, wherein the sensing circuitry comprises transistors formed on pitch with transistors of the array.

6. The apparatus of claim 1, wherein the controller is configured to cause the data value sums to be stored in the array.

7. An apparatus, comprising:

an array of memory cells coupled to sensing circuitry; and

a controller configured to cause;

summing, in parallel, of data values stored in memory cells coupled to a number of a plurality of sense lines and to a number of access lines of the array to determine a data value sum corresponding to each respective one of the number of sense lines;

storing of a respective data value sum of the data value sums in memory cells coupled to the respective sense line to which the respective data value sum corresponds; and

summing of the stored data value sums to determine a resultant sum representing a population count corresponding to the data values stored in the memory cells coupled to the number of the plurality of sense lines and to the number of access lines.

8. The apparatus of claim 7, wherein the controller is configured to cause storing of the data value sums in memory cells coupled to access lines other than the number of access lines to which memory cells storing the data values are coupled.

9. The apparatus of claim 7, wherein the controller is configured to cause storing of the data value sums as vertical bit vectors.

10. The apparatus of claim 7, wherein the controller being configured to cause summing of the data value sums to determine a resultant sum comprises the controller being configured to cause:

summing, in parallel, of a number of pairs of the stored data value sums to determine a number of updated data value sums; and

storing of the number of updated data value sums in memory cells coupled to respective ones of the number of sense lines to which the data value sums correspond; and

responsive to the number of updated data value sums being greater than one, subsequently summing, in parallel, of a number of pairs of the updated data value sums to determine a number of updated updated data value sums; and

storing of the number of updated updated data value sums in memory cells coupled to respective ones of the number of sense lines to which the updated data value sums correspond.

11. The apparatus of claim 7, wherein the controller being configured to cause the storing of the data value sums comprises the controller being configured to cause the data value sums to be stored as:

M-bit vertical bit vectors, and wherein the controller being configured to cause summing of the stored data value sums comprises the controller being configured to cause;

summing respective pairs of the M-bit vertical bit vectors; and

storing the sums of the respective pairs of the M-bit vertical bit vectors in log₂ (M) memory cells of the array.

12. The apparatus of claim 7, wherein the controller is configured to cause storing of the data values as a plurality of vertical bit vectors.

13. The apparatus of claim 7, wherein the controller is configured to cause storing of the data values in the array of memory cells using a same number of memory cells coupled to each of the plurality of sense lines.

14. The apparatus of claim 7, wherein the controller is configured to cause storing the data values in the array as a plurality of vertical bit vectors, each of the plurality of vertical bit vectors being arranged such that the elements of a respective one of the plurality of vertical bit vectors is stored in memory cells coupled to a respective one of the plurality of sense lines.

15. The apparatus of claim 7, wherein the apparatus is configured to perform logical operations without transferring data out of the memory array and sensing circuitry.

16. The apparatus of claim 7, wherein each sense line of the plurality of sense lines corresponds to a different column of the array.

17. A method for determining population count, comprising:

storing a vector in memory cells coupled to a number (R) of access lines and a number (C) of sense lines of an array;

performing, in parallel, a first summation operation on data values stored in memory cells coupled to respective ones of the C sense lines to determine C sense line population count sums corresponding to the respective sense lines;

storing each respective one of the C sense line population count sums in memory cells coupled to a corresponding one of the C sense lines;

subsequently performing a second summation operation, comprising;

summing, in parallel, at least two particular sense line population count sums of the C sense line population count sums to provide a first number of updated population count sums; and

storing each respective one of the first number of updated population count sums in memory cells coupled to a respective one of the C sense lines; and

responsive to the first number of updated population count sums being greater than one, subsequently performing a number of summation operation iterations, wherein each one of the number of summation operation iterations comprises;

summing, in parallel, at least two particular population count sums of the number of updated population count sums determined in an immediate prior summation operation iteration to provide an updated number of updated population count sums;

storing each respective one of the updated number of updated population count sums in memory cells coupled to a respective one of the C sense lines; and

wherein the number of summation operation iterations are performed until the number of updated population count sums is equal to one.

18. The method of claim 17, wherein each of the C sense line population count sums corresponds to a respective population count of a particular data value stored in the memory cells coupled to a respective one of the C sense lines.

19. The method of claim 17, wherein storing each respective one of the C sense line population count sums in memory cells coupled to a corresponding one of the C sense lines includes storing the each respective one of the C sense line population count sums in memory cells coupled to access lines of the array other than the R access lines to which memory cells storing the vector are coupled.

20. The method of claim 17, wherein performing the number of summation operation iterations until the number of updated population count sums is equal to one includes performing log₂ (C)−

1 summation operations; and

wherein the updated population count sum when the number of updated population counts sums is one indicates the population count for the vector.

21. The method of claim 17, wherein the vector comprises a number (M) of digits with M/R digits of the vector being stored in memory cells coupled to each of the R access lines and M/C of the digits of the vector being stored in memory cells coupled to each of the C sense lines.

22. The method of claim 17, wherein:

performing the second summation operation includes summing, in parallel, a number of pairs of the C sense line population count sums such that the first number of updated population count sums is C/2 population count sums; and

performing a first summation operation iteration of the number of summation operation iterations includes summing, in parallel, pairs of the C/2 updated population count sums such that the updated number of updated population count sums is C/4.

23. The method of claim 17, wherein performing the second summation operation and subsequently performing the number of summation operation iterations includes performing log₂ (C) summation operations.

24. A method for determining population count, comprising:

storing a vector in a memory array as a plurality of bit vectors;

determining, in parallel, population counts of the plurality of bit vectors; and

successively adding the population counts of the plurality of bit vectors together to provide a population count for the vector.

25. The method of claim 24, wherein successively adding the population counts of the plurality of bit vectors together includes:

adding a first pair of the population counts of the plurality of bit vectors together in parallel with adding a second pair of the population counts of the plurality of bit vectors together; and

adding a sum of the first pair of the population counts to a sum of the second pair of the population counts.

26. The method of claim 24, wherein successively adding the population counts of the plurality of bit vectors together includes at most log₂ (C) iterations of addition operations where C is a quantity of the bit vectors.

27. The method of claim 26, wherein determining population counts of the plurality of bit vectors includes at most R−

1+log₂ (C) addition operations where R is a quantity access lines coupled to cells in which the vector is stored.