Computing reduction and prefix sum operations in memory

Patent metadata

Field	Value
Publication number	US-9836218-B2
Application number	US-201514874068-A
Country	US
Kind code	B2
Filing date	Oct 2, 2015
Priority date	Oct 3, 2014
Publication date	Dec 5, 2017
Grant date	Dec 5, 2017

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.

First claim

What is claimed is:

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; and

wherein the processing circuitry is configured to compute the reduction operation without transferring the data via an input/output (I/O) line external to the group of memory cells.

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. 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; and

wherein the processing circuitry is on layout pitch with sense lines of the group of memory cells.

7. The apparatus of claim 6 , 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.

8. The apparatus of claim 6 , 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.

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

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

11. The apparatus of claim 6 , wherein the processing circuitry comprises sensing circuitry on layout pitch with the sense lines of the group of memory cells.

12. 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; and

wherein the reduction operation is computed without transferring the data via an input/output (I/O) line external to the array of memory cells.

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

14. The method of claim 12 , wherein the reduction operation and the logical operation are multiplication operations.

15. The method of claim 12 , 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.

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

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

18. 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; and

wherein the prefix sum operation is computed without transferring the data via a bus external to the array of memory cells.

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

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

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

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

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

24. 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; and

wherein the processing circuitry is on layout pitch with sense lines of the group of memory cells.

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

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

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

28. The apparatus of claim 27 , 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.

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

30. 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 t

Assignees

• Micron Technology Inc

Inventors

• Willcock Jeremiah J

Classifications

• G11C7/1006 Primary

  Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F3/065

  Replication mechanisms · CPC title