VECTOR POPULATION COUNT DETERMINATION IN MEMORY

• US 20160266899A1
• Filed: 03/09/2016
• Published: 09/15/2016
• Est. Priority Date: 03/13/2015
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Tiwari, Sanjay
• Granted Patent: US 10,146,537 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 15/7821 Tightly coupled to memory, e.g. computational memory, smart memory, processor in memory
• CPC Class Codes: G06F 15/7839 with memory
• CPC Class Codes: G06F 7/607 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 Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30038 using a mask
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G11C 11/4091 Sense or sense/refresh amplifiers, or associated sense circuitry, e.g. for coupled bit-line precharging, equalising or isolating
• CPC Class Codes: G11C 11/4096 Input/output [I/O] data management or control circuits, e.g. reading or writing circuits, I/O drivers or bit-line switches
• CPC Class Codes: G11C 2207/002 Isolation gates, i.e. gates coupling bit lines to the sense amplifier
• CPC Class Codes: G11C 2207/005 Transfer gates, i.e. gates coupling the sense amplifier output to data lines, I/O lines or global bit lines
• CPC Class Codes: G11C 2207/104 Embedded memory devices, e.g. memories with a processing device on the same die or ASIC memory designs
• 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/1012 Data reordering during input/output, e.g. crossbars, layers of multiplexers, shifting or rotating
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Examples of the present disclosure provide apparatuses and methods for determining a vector population count in a memory. An example method comprises determining, using sensing circuitry, a vector population count of a number of fixed length elements of a vector stored in a memory array.

Claims

1. A method, comprising:

determining, using sensing circuitry, a vector population count of a number of fixed length elements of a vector stored in a memory array.

2. The method of claim 1, wherein the determining of the vector population count is performed in the memory array.

3. The method of claim 1, wherein determining the vector population count includes performing a number of AND, OR, and shift operations, wherein the number of AND and shift operations is based on a length of the number of fixed length elements.

4. The method of claim 2, wherein the number of AND, OR, and shift operations are performed using sensing circuitry coupled to each of a number of columns of complementary sense lines.

5. The method of claim 1, wherein the determining of the vector population count includes determining how many bits of each of the number of fixed length elements have a particular value.

6. The method of claim 5, wherein the particular value includes a bit value of 1.

7. The method of claim 5, wherein the particular value includes a bit value of 0.

8. The method of claim 1, wherein the vector is stored in a group of memory cells coupled to a particular access line.

9. The method of claim 8, including determining the vector population count and storing a result of the determination of the vector population count in a group of memory cells coupled to a different particular access line of the memory array without performing a sense line address access.

10. The method of claim 1, wherein determining the vector population count includes creating an elemental mask that indicates a most significant bit of each of the number of fixed length elements.

11. The method of claim 1, wherein determining the vector population count includes determining a number of comparison iterations to perform by calculating log 2 of a number of bits in the number of fixed length elements.

12. An apparatus, comprising:

a group of memory cells coupled to a first access line of a memory array and configured to store a vector comprising a number of elements; and

a controller configured to;

perform at least one of an AND operation, an OR operation, and a SHIFT operation using sensing circuitry to determine a vector population count of the number of elements.

13. The apparatus of claim 12, wherein each of the sensing circuitry comprises a sense amplifier and a compute component.

14. The apparatus of claim 13, wherein each of the corresponding sense amplifiers comprises a primary latch and each of the corresponding compute components comprise a secondary latch.

15. The apparatus of claim 12, wherein the sensing circuitry is configured to determine a most significant bit of each of the number of elements.

16. The apparatus of claim 15, wherein the sensing circuitry is configured to store elements representing a most significant bit of each of the number of elements as an elemental mask.

17. The apparatus of claim 12, wherein the sensing circuitry is configured to determine a number of comparison iterations to perform by calculating log 2 of a number of bits in the number of elements.

18. The apparatus of claim 17, wherein the sensing circuitry is configured to determine a reduction vector bit vector for each of the number of comparison iterations.

19. The apparatus of claim 17, wherein the sensing circuitry is configured to determine a pattern mask for each of the number of comparison iterations.

20. The apparatus of claim 19, wherein each of the pattern masks include a first portion of the pattern mask and a second portion of the pattern mask.

21. The apparatus of claim 20, wherein the sensing circuitry is configured to perform a half add operation on the first portion of the pattern mask and the second portion of the pattern mask.

22. A method, comprising:

determining, using sensing circuitry, a vector population of a number of elements of a vector stored in a memory array by;

determining a number of elements that represent a most significant bit of each of the number of elements;

performing a number of comparison iterations, wherein performing the number of comparison iterations comprises;

determining a reduction vector for each of the number of comparison iterations; and

determining a pattern mask for each of the number of comparison iterations.

23. The method of claim 22, comprising determining a quantity of comparison iterations to perform by calculating log 2 of a number of bits in each of the number of elements.

24. The method of claim 22, comprising determining an elemental mask for the vector, wherein the elemental mask represents a most significant bit of each of the number of elements.

25. The method of claim 22, wherein performing the number of comparison iterations includes comparing 2ⁿ bits during each respective comparison iteration.

26. The method of claim 24, wherein determining the reduction vector for each of the number of comparison iterations includes performing a first loop in which a shifted elemental mask is formed by shifting bits of the elemental mask to the right by one bit and an OR operation is performed with the shifted elemental mask and the elemental mask.

27. The method of claim 26, wherein determining the reduction vector for each of the number of comparison iterations includes performing a second loop, wherein a result of the first loop is shifted to the right by an amount equal to 2*I, where I is a count of the iteration that is being performed, and an OR operation is performed with the shifted result of the first loop and the result of the first loop.

28. The method of claim 22, wherein determining the pattern mask for each of the number of comparison iterations includes determining a first portion of the pattern mask by performing an AND operation with the reduction vector and a destination vector and shifting a result of the AND operation to the right by 2^I−

1, where I is a count of the iteration that is being performed.

29. The method of claim 28, wherein determining the pattern mask for each of the number of comparison iterations includes determining a second portion of the pattern mask by performing an AND operation with an inverse of the reduction vector and the destination vector.

30. The method of claim 29, wherein performing the number of comparison iterations includes performing a half add operation of the first portion and second portion of the pattern mask for each of the number of comparison iterations.

31. The method of claim 30, wherein performing the number of comparison iterations includes performing a loop that includes shifting a carry of the half add operation to left one place, and checking for carry values using a BlockOR operation, and performing another half add operation with the shift carry values and a sum of the half add operation.

32. An apparatus comprising:

a group of memory cells coupled to a first access line of a memory array and configured to store a number of elements; and

a controller configured to;

determine an elemental mask;

perform a number of comparison iterations, wherein each of the number of comparison iterations includes determining a reduction vector for each of the number of comparison iterations and determining a pattern mask for each of the number of comparison iterations; and

output a vector population count that indicates how many bits of each of the number of elements have a particular data value.

33. The apparatus of claim 32, wherein the sensing circuitry is configured to determine the number of comparison iterations to perform by calculating log 2 of a number of bits in the number of elements.

34. The apparatus of claim 32, wherein the sensing circuitry is configured to calculate an output for each of the number of comparison iterations that is used by a subsequent comparison iteration to determine the vector population count.