Computational storage device, computational storage system and operation method for DiskANN search
A computational storage device for executing DiskANN search is provided by an aspect of the present disclosure. The computational storage device comprises a NAND memory array configured to storage node chunks corresponding to nodes in the DiskANN. The computational storage device also comprises a non-volatile memory array configured to store multiple product quantization (PQ) vectors corresponding to the nodes of the node chunks. The computational store device also comprises a processing unit coupled to the NAND memory array and the non-volatile memory array. The processing unit configured to execute DiskANN search (DiskANNs) among the node chunks in the NAND memory array and the multiple PQ vectors in the non-volatile memory array according to a received search instruction, and output a search result.
1 . A computational storage device for disk approximate nearest neighbor (DiskANN) search, comprising:
a NAND memory array, configured to store a plurality of node chunks corresponding to a plurality of nodes of the DiskANN;
a non-volatile memory array, configured to store a plurality of product quantization (PQ) vectors corresponding to the plurality of nodes in the plurality of node chunks; and
a processor unit, coupled to the NAND memory array and the non-volatile memory array,
wherein the processor unit is configured to:
execute DiskANN search among the plurality of node chunks in the NAND memory array and the plurality of PQ vectors in the non-volatile memory array according to a received search instruction, and output a search result,
wherein the non-volatile memory array is a phase change memory (PCM) array, a NOR memory array, a 3D NOR memory array, a magnetoresistive random access memory (MRAM) array or a resistive random access memory (RRAM) array,
wherein each of the plurality of node chunks comprises a node vector data, a number of neighboring nodes, and a plurality of identifiers of neighboring nodes, of each of the plurality of nodes.
2 . The computational storage device according to claim 1 , wherein the processor unit executing DiskANN search while receiving the search instruction comprises:
comparing a graph index corresponding to the plurality of node chunks, with a query condition of the search instruction, to obtain a near node of the plurality of nodes, in the plurality of node chunks, corresponding to comparison of the graph index;
based on respective identifiers of neighboring nodes of the near node, in the plurality of node chunks stored in the NAND memory array, obtaining a plurality of respective PQ vectors of neighboring nodes corresponding to the respective identifiers of neighboring nodes of the near node, from the plurality of PQ vectors stored in the non-volatile memory array;
comparing the plurality of respective PQ vectors of the neighboring nodes of the near node for obtaining a nearest node nearest to the query condition, from the neighboring nodes; and
using the nearest node as the near node and repeating the above steps until k nodes nearest to the query condition are obtained, which search result includes the k nodes as a Top-K search result,
wherein k is an integer greater than or equal to one.
3 . The computational storage device according to claim 2 , wherein the graph index stores in the non-volatile memory array.
4 . The computational storage device according to claim 2 , further comprising a dynamic memory array coupled to the processing unit and configured to store the graph index.
5 . The computational storage device according to claim 2 ,
wherein the dynamic memory array is a dynamic random-access memory (DRAM) array.
6 . A computational storage system for DiskANN search, comprising:
a computational storage device, comprising:
a NAND memory array, configured to store a plurality of node chunks corresponding to a plurality of nodes of the DiskANN; and
a processor unit, coupled to the NAND memory array; and
a non-volatile memory device including a non-volatile memory array configured to store a plurality of PQ vectors corresponding to the plurality of nodes in the plurality of node chunks; and
wherein the non-volatile memory device is coupled to the processor unit, and the processor unit is configured to:
execute DiskANN search among the plurality of node chunks in the NAND memory array of the computational storage device and the plurality of PQ vectors in the non-volatile memory array of the non-volatile memory device according to a received search instruction, and output a search result,
wherein the non-volatile memory array is a PCM array, a NOR memory array, a 3D NOR memory array, a MRAM array or a RRAM array,
wherein each of the plurality of node chunks comprises a node vector data, a number of neighboring nodes, and a plurality of identifiers of neighboring nodes, of each of the plurality of nodes.
7 . The computational storage system according to claim 6 , wherein the processor unit executing DiskANN search while receiving the search instruction comprises:
comparing a graph index corresponding to the plurality of node chunks, with a query condition of the search instruction, to obtain a near node of the plurality of nodes, in the plurality of node chunks, corresponding to comparison of the graph index;
based on respective identifiers of neighboring nodes of the near node, in the plurality of node chunks stored in the NAND memory array, obtaining a plurality of respective PQ vectors of neighboring nodes corresponding to the respective identifiers of neighboring nodes of the near node, from the plurality of PQ vectors stored in the non-volatile memory array;
comparing the plurality of respective PQ vectors of the neighboring nodes of the near node for obtaining a nearest node nearest to the query condition, from the neighboring nodes; and
using the nearest node as the near node and repeating the above steps until k nodes nearest to the query condition are obtained, which search result includes the k nodes as a Top-K search result,
wherein k is an integer greater than or equal to one.
8 . The computational storage system according to claim 7 , wherein the graph index stores in the non-volatile memory array.
9 . The computational storage system according to claim 7 , wherein the computational storage device further comprises a dynamic memory array coupled to the processing unit and configured to store the graph index.
10 . The computational storage system according to claim 9 ,
wherein the dynamic memory array is a DRAM array.
11 . An operation method for a memory device, comprising:
storing a plurality of node chunks of a plurality of nodes generated by a DiskANN regarding a database, in a NAND memory array of the memory device;
storing a plurality of PQ vectors corresponding to the plurality of nodes in the plurality of node chunks, in a non-volatile memory array of the memory device; and
executing, by a processing unit of the memory device, a DiskANN search among the plurality of node chunks in the NAND memory array and the plurality of PQ vectors in the non-volatile memory array according to a received search instruction, and outputting a search result,
wherein the non-volatile memory array is a PCM array, a NOR memory array, a 3D NOR memory array, a MRAM array or a RRAM array,
wherein each of the plurality of node chunks comprises a node vector data, a number of neighboring nodes, and a plurality of identifiers of neighboring nodes, of each of the plurality of nodes.
12 . The operation method according to claim 11 , wherein executing, by a processing unit of the memory device, the DiskANN search comprises:
comparing a graph index corresponding to the plurality of node chunks, with a query condition of the search instruction, to obtain a near node of the plurality of nodes, in the plurality of node chunks, corresponding to comparison of the graph index;
based on respective identifiers of neighboring nodes of the near node, in the plurality of node chunks stored in the NAND memory array, obtaining a plurality of respective PQ vectors of neighboring nodes corresponding to the respective identifiers of neighboring nodes of the near node, from the plurality of PQ vectors stored in the non-volatile memory array;
comparing the plurality of respective PQ vectors of the neighboring nodes of the near node for obtaining a nearest node nearest to the query condition, from the neighboring nodes; and
using the nearest node as the near node and repeating the above steps until k nodes nearest to the query condition are obtained, which search result includes the k nodes as a Top-K search result,
wherein k is an integer greater than or equal to one.
13 . The operation method according to claim 12 , wherein the graph index stores in the non-volatile memory array.
14 . The operation method according to claim 12 , wherein the graph index is stored in a dynamic memory array of the computational storage device, and the dynamic memory array is coupled to the processing unit.
15 . The operation method according to claim 14 ,
wherein the dynamic memory array is a DRAM array.