SORT OPERATION IN MEMORY

• US 20160188250A1
• Filed: 10/22/2015
• Published: 06/30/2016
• Est. Priority Date: 10/24/2014
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Wheeler, Kyle B.
• Granted Patent: US 10,147,480 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 19/287 Organisation of a multiplicity of shift registers
• 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

Examples of the present disclosure provide apparatuses and methods related to performing a sort operation in a memory. An example apparatus might include a a first group of memory cells coupled to a first sense line, a second group of memory cells coupled to a second sense line, and a controller configured to control sensing circuitry to sort a first element stored in the first group of memory cells and a second element stored in the second group of memory cells by performing an operation without transferring data via an input/output (I/O) line.

Claims

1. An apparatus comprising:

a first group of memory cells coupled to a first sense line;

a second group of memory cells coupled to a second sense line; and

a controller configured to control sensing circuitry to sort a first element stored in the first group of memory cells and a second element stored in the second group of memory cells by performing an operation without transferring data via an input/output (I/O) line.

2. The apparatus of claim 1, wherein performing the operation comprises performing at least one of:

an AND operation;

an OR operation, an INVERT operation, and a SHIFT operation without performing a sense line address access.

3. The apparatus of claim 2, wherein the sensing circuitry comprises a first compute component coupled to the first sense line and formed on pitch with the first group of memory cells and a second compute component coupled to the second sense line and formed on pitch with the second group of memory cells.

4. The apparatus of claim 3, wherein:

the sensing circuitry comprises a first sense amplifier coupled to the first compute component and a second sense amplifier coupled to the second compute component; and

the I/O line is coupled, via respective access devices, to the first and second compute components and to a secondary sense amplifier.

5. The apparatus of claim 4, wherein each of the first and the second sense amplifier comprise a primary latch and each of the first and the second compute component comprises a secondary latch.

6. A method comprising:

performing a sort operation, comprising;

swapping a first element stored in a first group of memory cells coupled to a first sense line and to a number of access lines of an array of memory cells with a second element stored in a second group of memory cells coupled to a second sense line and to the number of access lines if the first element is greater than the second element, such that subsequent to the swapping, the first element is stored in the second group of memory cells and the second element is stored in the first group of memory cells; and

wherein the swapping is performed without transferring data corresponding to the first and second elements via an input/output (I/O) line.

7. The method of claim 6, wherein, prior to the swapping, the first element is stored as a first bit-vector in the first group of memory cells, with each memory cell in the first group of memory cells storing a respective bit of the first bit-vector.

8. The method of claim 7, wherein, prior to swapping, the second element is stored as a second bit-vector in the second group of memory cells, with each memory cell in the second group of memory cells storing a respective bit of the second bit-vector.

9. The method of claim 8, wherein, subsequent to the swapping, the first bit-vector is stored in the second group of memory cells and the second bit-vector in the first group of memory cells.

10. The method of claim 6, wherein, prior to the swapping:

the first element is stored, as a first bit-vector comprising a number of bits, in a respective number of memory cells of the first group; and

the second element is stored, as a second bit-vector comprising a same number of bits as the first bit-vector, in a respective number of memory cells of the second group; and

wherein bits of the first bit-vector having a same bit position as bits of the second bit-vector are stored in memory cells coupled to a same access line of the number of access lines; and

wherein swapping the first element with the second element comprises swapping bit pairs of the first and second bit-vectors having a same bit position and stored in memory cells coupled to a same access line such that subsequent to the swapping, the first element is stored, as the first bit-vector, in the respective number of memory cells of the second group, and the second element is stored, as the second bit-vector, in the respective number of memory cells of the first group.

11. The method of claim 6, wherein the first element is a first value and the second element is a second value and wherein performing the swap operation results in storing the first value in the second group of memory cells and storing the second value in the first group of memory cells.

12. An apparatus comprising:

a plurality of groups of memory cells configured to store a plurality of elements, wherein each group from the plurality of groups of memory cells is coupled to a different sense line from a plurality of sense lines and to a plurality of access lines;

a controller configured to control sensing circuitry to, without transferring data via an input/output (I/O) line;

perform a comparison operation on the plurality of elements; and

swap a first portion of the plurality of elements with a second portion of the plurality of elements, wherein the first portion of the plurality of elements and the second portion of the plurality of elements are selected based on a result of the comparison operation.

13. The apparatus of claim 12, wherein the controller is further configured to control sensing circuitry to compare each of the plurality of elements with a different element from the plurality of elements that is stored in an adjacent sense line from the plurality of sense lines.

14. The apparatus of claim 13, wherein the comparison operation compares each of the plurality of elements with the different elements from the plurality of elements based on a numeric value that is associated with each of the plurality of elements.

15. The apparatus of claim 15, wherein the controller is further configured to control sensing circuitry to swap elements that have a higher numerical value with elements that have a lower numerical value.

16. A method for performing a sort operation comprising:

performing, in parallel and without performing a sense line address access, a sort operation in memory on;

elements stored in a plurality of groups of memory cells, wherein each group of memory cells from the plurality of groups is coupled to a different sense line from a plurality of sense lines and to a plurality of access lines; and

wherein performing the sort operation results in sorting the elements based on values associated with the elements by performing a plurality of compare operations and a plurality of swap operations.

17. The method of claim 16, wherein each of the elements comprises a plurality of bits.

18. The method of claim 17, wherein each of the plurality of bits in each of the elements are associated with a respective one of a plurality of indices corresponding to bit positions of the plurality of bits, and wherein bits from corresponding elements having a same associated index are stored in memory cells that are coupled to a same access line from the plurality of access lines.

19. The method of claim 18, wherein each of the plurality of access lines is associated with a different one of the plurality of indices.

20. The method of claim 16, wherein performing each of the plurality of compare operations includes:

determining whether each of the elements that are stored in a first group of memory cells is greater than a different element from the elements stored in a second group of memory cells that is adjacent to the first group of memory cells.

21. The method of claim 20, wherein determining whether each of the elements is greater than a different element includes:

determining whether a difference exists between each of the elements stored in the first group of memory cells and the different element from the elements that are stored in the second group of memory cells.

22. The method of claim 21, wherein determining whether the difference exists between each of the elements and the different element includes:

determining whether a difference exists between a first bit with a specific index from each of the elements and a second bit with the specific index from each of the respective different elements.

23. The method of claim 22, wherein determining whether the difference exists between the first bit and the second bit includes:

performing a SHIFT operation to shift the second bit that is stored in a second compute component to a first compute component;

wherein the second compute component and a memory cell that stores the second bit are coupled to a second sense line from the plurality of sense lines and the first compute component and a memory cell that stored the first bit are coupled to a first sense line.

24. The method of claim 20, wherein performing each of the plurality of compare operations includes creating a mask to identify which of the elements are to be swapped.

25. The method of claim 24, wherein the method includes modifying the mask to alternate between identifying elements that are stored in memory cells that are coupled to even sense lines and odd sense lines after each of the plurality of compare operations.

26. The method of claim 25, wherein the method further includes swapping elements that are identified in the mask.

27. The method of claim 26, wherein the method includes concluding the sort operation when no elements are identified in the mask.