Sort operation in memory
View Patent ↗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.
1. 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 of a memory array;
a controller configured to control sensing circuitry to:
perform a comparison operation on the plurality of elements by comparing 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, based on a numeric value that is associated with each of the plurality of elements; and
swap a first portion of the plurality of elements with a second portion of the plurality of elements, without transferring data out of the memory array and the sensing circuitry via an input/output (I/O) line, 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 stored in the memory array.
2. The apparatus of claim 1 , wherein the controller is further configured to control the sensing circuitry to swap elements that have a higher numerical value with elements that have a lower numerical value.
3. A method for performing a sort operation comprising:
performing, in parallel, 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;
storing a result of the compare operation as a mask in the memory array; and
performing a plurality of swap operations using the mask, wherein the plurality of swap operations are performed without transferring data out of a memory array and sensing circuitry using a sense line address access.
4. The method of claim 3 , wherein each of the elements comprises a plurality of bits.
5. The method of claim 4 , 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.
6. The method of claim 5 , wherein each of the plurality of access lines is associated with a different one of the plurality of indices.
7. The method of claim 3 , 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.
8. The method of claim 7 , 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.
9. The method of claim 8 , 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.
10. The method of claim 9 , 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.
11. The method of claim 7 , wherein performing each of the plurality of compare operations includes creating the mask to identify which of the elements are to be swapped.
12. The method of claim 11 , 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.
13. The method of claim 12 , wherein the method further includes swapping elements that are identified in the mask.
14. The method of claim 13 , wherein the method includes concluding the sort operation when no elements are identified in the mask.