COMPUTING REDUCTION AND PREFIX SUM OPERATIONS IN MEMORY

• US 20160098208A1
• Filed: 10/02/2015
• Published: 04/07/2016
• Est. Priority Date: 10/03/2014
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Willcock, Jeremiah J.
• Granted Patent: US 9,836,218 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor

Abstract

The present disclosure includes apparatuses and methods for computing reduction and prefix sum operations in memory. A number of embodiments include processing circuitry configured to compute a reduction operation on data stored in a group of memory cells by splitting the data into a plurality of elements, copying each of the plurality of elements into elements that are wider than before being copied, and performing a logical operation associated with the reduction operation on each of the copied elements.

Claims

1. An apparatus, comprising:

processing circuitry configured to compute a reduction operation on data stored in a group of memory cells by;

splitting the data into a plurality of elements;

copying each of the plurality of elements into elements that are wider than before being copied; and

performing a logical operation associated with the reduction operation on each of the copied elements.

2. The apparatus of claim 1, wherein:

splitting the data into the plurality of elements includes splitting the data into even and odd indexed elements; and

copying each of the plurality of elements includes;

copying the even indexed elements into elements twice as wide and half as tall as before being copied; and

copying the odd indexed elements into elements twice as wide and half as tall as before being copied.

3. The apparatus of claim 1, wherein the group of memory cells is coupled to a single sense line.

4. The apparatus of claim 1, wherein the group of memory cells is coupled to a plurality of sense lines.

5. The apparatus of claim 1, wherein the group of memory cells is coupled to a plurality of access lines.

6. The apparatus of claim 1, wherein the processing circuitry is configured to compute the reduction operation without transferring the data via an input/output (I/O) line.

7. An apparatus, comprising:

processing circuitry configured to compute a prefix sum operation on data stored in a group of memory cells by;

splitting the data into a plurality of elements;

copying each of the plurality of elements into elements that are wider than before being copied; and

performing a logical operation associated with the prefix sum operation on each of the copied elements.

8. The apparatus of claim 7, wherein the processing circuitry is configured to:

shift an output of the logical operation by one element;

perform another logical operation on the shifted output and one of the copied elements, wherein the one of the copied elements is an even indexed element; and

pack an output of the another logical operation into elements half as wide as before the another logical operation.

9. The apparatus of claim 7, wherein the processing circuitry is configured to:

shift an output of the logical operation by one element;

perform another logical operation on the shifted output and one of the copied elements, wherein the one of the copied elements is an odd indexed element; and

pack an output of the another logical operation into elements half as wide as before the another logical operation.

10. The apparatus of claim 7, wherein the prefix sum operation is computed using an identity element.

11. The apparatus of claim 7, wherein the prefix sum operation is computed without using an identity element.

12. The apparatus of claim 7, wherein the processing circuitry comprises sensing circuitry on pitch with the memory cells.

13. A method of operating processing circuitry, comprising:

computing a reduction operation on data stored in a group of memory cells in an array of memory cells by;

splitting the data into a plurality of elements;

copying each of the plurality of elements into elements that are wider than before being copied; and

performing a logical operation associated with the reduction operation on each of the copied elements.

14. The method of claim 13, wherein the reduction operation and the logical operation are addition operations.

15. The method of claim 13, wherein the reduction operation and the logical operation are multiplication operations.

16. The method of claim 13, wherein copying each of the plurality of elements includes copying each of the plurality of elements into elements twice as wide as before being copied.

17. The method of claim 13, wherein the method includes sensing the data stored in the group of memory cells.

18. The method of claim 13, wherein the reduction operation is computed without performing a sense line address access.

19. A method of operating processing circuitry, comprising:

computing a prefix sum operation on data stored in a group of memory cells in an array of memory cells by;

splitting the data into a plurality of elements;

copying each of the plurality of elements into elements that are wider than before being copied; and

performing a logical operation associated with the prefix sum operation on each of the copied elements.

20. The method of claim 19, wherein performing the logical operation combines the each of the copied elements.

21. The method of claim 19, wherein each of the copied elements are copied to the group of memory cells.

22. The method of claim 19, wherein each of the copied elements are copied to an additional group of memory cells in the array.

23. The method of claim 19, wherein the logical operation is performed using an algorithm based on a structure of a Kogge-Stone adder.

24. The method of claim 19, wherein the logical operation is performed using an algorithm based on a structure of a Brent-Kung adder.

25. The method of claim 19, wherein the prefix sum operation is computed without transferring the data via a bus.

26. An apparatus, comprising:

processing circuitry configured to compute a reduction operation on data stored in a group of memory cells by;

splitting the data into a plurality of elements;

copying each of the plurality of elements into elements twice as wide and half as tall as before being copied; and

performing an addition operation on each of the copied elements to combine the copied elements.

27. The apparatus of claim 26, wherein the group of memory cells is coupled to a plurality of sense lines and a plurality of access lines.

28. The apparatus of claim 26, wherein the processing circuitry is configured to output a result of the reduction operation to external hardware.

29. The apparatus of claim 26, wherein the apparatus includes shift circuitry coupled to the group of memory cells.

30. The apparatus of claim 29, wherein the processing circuitry is configured to:

split the data via the shift circuitry; and

copy each of the plurality of elements via the shift circuitry.

31. The apparatus of claim 26, wherein the processing circuitry comprises a sense amplifier and a compute component.

32. A method of operating processing circuitry, comprising:

computing a prefix sum operation on data stored in a group of memory cells by;

splitting the data into even and odd indexed elements;

copying the even indexed elements into elements twice as wide and half as tall as before being copied, and copying the odd indexed elements into elements twice as wide and half as tall as before being copied;

performing an addition operation on the copied even indexed elements and the copied odd indexed elements to combine the copied even and odd indexed elements;

shifting an output of the addition operation by one element;

performing another addition operation on the shifted output and the copied even indexed elements to combine the shifted output and the copied even indexed elements; and

packing the combined shifted output and copied even indexed elements into elements half as wide and twice as tall as before the another addition operation.

33. The method of claim 32, wherein a direction the output of the addition operation is shifted is based on a direction of the prefix sum operation.

34. The method of claim 32, wherein:

the prefix sum operation is a forward prefix sum operation; and

the method includes shifting the output of the addition operation right by one element.

35. The method of claim 32, wherein:

the prefix sum operation is a backward prefix sum operation; and

the method includes shifting the output of the addition operation left by one element.

36. The method of claim 32, wherein shifting the output of the addition operation by one element includes filling an identity element in an element of the output of the addition operation.

37. The method of claim 32, wherein shifting the output of the addition operation by one element includes filling an arbitrary element in an element of the output of the addition operation.

38. The method of claim 32, wherein the method includes replacing an element of the combined shifted output and copied even indexed elements with an element of the copied even indexed elements before packing the combined shifted output and copied even indexed elements.