Memory die with on-chip binary vector database search
A data storage device is configured to store a database of objects in an NVM die as binary vectors and to then search the database based on binary key vectors. The binary vectors may be received from a host for storage in the NVM die. In other examples, a data storage controller converts floating-point vectors received from the host into binary vectors for storage in the NVM die. Various procedures are described for converting the floating-point vectors into binary vectors. Exemplary procedures are also described for comparing a binary key vector received from the host with the binary vectors stored in the NVM die to detect matches. For example, a sequence of commands is described for applying by the data storage controller to the NVM die to control the die to identify and count matching bits using the latches of the NVM die. Volatile memory implementations are also described.
1. A data storage device, comprising:
a die comprising non-volatile memory (NVM); and
a data storage controller coupled to the die, the data storage controller comprising one or more processors configured to:
store objects within the NVM of the die as binary vectors;
obtain a binary key vector representative of a particular object to search for within the binary vectors stored on the NVM of the die; and
search for the particular object within the binary vectors stored in the NVM by sending one or more instructions or commands to the die that are configured to:
determine whether bits within the binary key vector match corresponding bits within a binary vector stored in the NVM;
control a counter of the die to count a number of bits within the binary vector that match corresponding bits in the binary key vector; and
notify the data storage controller in response to the counter exceeding a threshold count representative of a match between the binary key vector and the binary vector of the NVM.
2. The data storage device of claim 1 , wherein the one or more instructions or commands are configured to cause the die to perform one or more exclusive NOR (XNOR) operations.
3. The data storage device of claim 1 , wherein the one or more processors are further configured to receive the objects as binary vectors from a host for storing in the NVM of the die.
4. The data storage device of claim 1 , wherein the one or more processors are further configured to store the binary vectors along bitlines of the NVM.
5. The data storage device of claim 1 , wherein counter comprises a latch-based counter or a per-bit counter circuit.
6. The data storage device of claim 1 , wherein the counter is one of a plurality of counters of the die, and wherein the one or more processors are further configured to:
count a number of the counters that overflow;
compare the count of the number of counters that overflow to a counter overflow threshold; and
generate an indicator in response to the count exceeding the counter overflow threshold.
7. A method for use by a data storage controller of a data storage device having a die with non-volatile memory (NVM), the method comprising:
storing objects within the NVM of the die as binary vectors;
obtaining a binary key vector representative of a particular object to search for within the binary vectors stored in the NVM of the die; and
searching for the particular object within the binary vectors stored in the NVM of the die by sending one or more instructions or commands to the die that control the die to:
determine whether bits within the binary key vector match corresponding bits within a binary vector stored in the NVM;
control a counter of the die to count a number of bits within the binary vector that match corresponding bits in the binary key vector; and
notify the data storage controller in response to the counter exceeding a threshold count representative of a match between the binary key vector and the binary vector of the NVM.
8. The method of claim 7 , wherein the one or more instructions or commands causes the die to perform one or more exclusive NOR (XNOR) operations.
9. The method of claim 7 , wherein the one or more instructions or commands are configured to control the die to:
sense all bits of a bitline of the NVM that stores one of the binary vectors; and
compare all bits of the sensed bitline to corresponding bits of the binary key vector.
10. The method of claim 7 , wherein the one or more instructions or commands are configured to control the die to:
sense only a portion of the bits of a bitline of the NVM that stores one of the binary vectors; and
compare the portion of bits to corresponding bits of the binary key vector.
11. The method of claim 10 , wherein the data storage controller randomly selects the portion of bits to be sensed.
12. The method of claim 10 , wherein the data storage controller selects the portion of bits to be sensed based on bit values of the binary key vector.
13. The method of claim 7 , further comprising receiving the objects as binary vectors from a host for storing in the NVM of the die.
14. The method of claim 7 , wherein storing objects within the NVM of the die as binary vectors comprises storing the binary vectors along bitlines of the NVM.
15. The method of claim 7 , wherein counter comprises a latch-based counter or a per-bit counter circuit.
16. The method of claim 7 , wherein the counter is one of a plurality of counters of the die, and wherein the method further comprises:
counting a number of the counters that overflow;
comparing the count of the number of counters that overflow to a counter overflow threshold; and
generating an indicator in response to the count exceeding the counter overflow threshold.
17. A device, comprising:
a die comprising non-volatile memory (NVM); and
one or more processors formed on the die and configured to:
store objects within the NVM as binary vectors;
receive signals from a data storage controller representative of a particular object to search for within the binary vectors including receiving one or more instructions or commands configured to control the one or more processors of the die to determine whether bits within a binary key vector corresponding to the particular object match corresponding bits within a binary vector stored in the NVM;
search for the particular object within the binary vectors stored in the NVM by executing the one or more instructions or commands while incrementing a counter of the die to count a number of bits within the binary vector that match corresponding bits in the binary key vector; and
notify the data storage controller in response to the counter exceeding a threshold count representative of a match between the binary key vector and the binary vector in the NVM.
18. The device of claim 17 , wherein the one or more processors are further configured to store the binary vectors along bitlines of the NVM.
19. The device of claim 18 , wherein the one or more processors are further configured to store an individual binary vector of a plurality of the binary vectors using an entire bitline or only a portion of a bitline.
20. The device of claim 17 , wherein the NVM comprises multiple blocks and wherein the one or more processors are further configured to store an individual binary vector of a plurality of the binary vectors using an entire block, only a fraction of a block, or multiple blocks.
21. The device of claim 17 , wherein the NVM comprises single-level cell (SLC) memory and wherein the binary vectors are stored in the SLC memory.
22. The device of claim 17 , wherein the NVM comprises multi-level cell (MLC) memory and wherein the binary vectors are stored in the MLC memory.
23. The device of claim 17 , wherein the counter comprises a latch-based counter or a per-bit counter circuit.
24. The device of claim 17 , wherein the counter is one of a plurality of counters on the die, and wherein the one or more processors are further configured to:
count a number of the counters that overflow;
compare the count of the number of counters that overflow to a counter overflow threshold; and
generate an indicator in response to the count exceeding the counter overflow threshold.
25. A method for use by a die having non-volatile memory (NVM), the method comprising:
storing objects within the NVM as binary vectors;
receiving signals from a data storage controller representative of a particular object to search for within the binary vectors including receiving one or more instructions or commands configured to control the die to determine whether bits within a binary key vector corresponding to the particular object match corresponding bits within a binary vector stored in the NVM;
searching for the particular object within the binary vectors stored in the NVM by executing the one or more instructions or commands while incrementing a counter of the die to count a number of bits within the binary vector that match corresponding bits in the binary key vector; and
notifying the data storage controller in response to the counter exceeding a threshold count representative of a match between the binary key vector and the binary vector in the NVM.
26. The method of claim 25 , wherein the binary vectors are stored along bitlines of the NVM.
27. The method of claim 25 , wherein storing objects within the NVM of the die as binary vectors comprises storing the binary vectors along bitlines of the NVM.
28. The method of claim 25 , wherein counter comprises a latch-based counter or a per-bit counter circuit.
29. The method of claim 25 , wherein the counter is one of a plurality of counters of the die, and wherein counting the number of bits within the binary vector that match corresponding bits in the binary key vector further comprises:
counting a number of the counters that overflow;
comparing the count of the number of counters that overflow to a counter overflow threshold; and
generating an indicator in response to the count exceeding the counter overflow threshold.
30. An apparatus for use with a die having non-volatile memory (NVM), the apparatus comprising:
means for storing objects within the NVM of the die as binary vectors;
means for obtaining a binary key vector representative of a particular object to search for within the binary vectors stored in the NVM of the die; and
means for searching for the particular object within the binary vectors stored in the NVM of the die by sending one or more instructions or commands to the die that are configured to control the die to:
determine whether bits within the binary key vector match corresponding bits within a binary vector stored in the NVM;
control a counter of the die to count a number of bits within the binary vector that match corresponding bits in the binary key vector; and
notify a data storage controller of the apparatus in response to the counter exceeding a threshold count representative of a match between the binary key vector and the binary vector of the NVM.
31. The apparatus of claim 30 , wherein the means for storing objects within the NVM as binary vectors comprises means for storing binary vectors along bitlines of the NVM.