Storage device and memory system

Patent metadata

Field	Value
Publication number	US-12443368-B2
Application number	US-202217696586-A
Country	US
Kind code	B2
Filing date	Mar 16, 2022
Priority date	Sep 9, 2021
Publication date	Oct 14, 2025
Grant date	Oct 14, 2025

Abstract

A storage device is provided. The storage device includes a controller which receives a command from a host for instructing performance of a first computation, a non-volatile memory which stores a plurality of datasets, a buffer memory to which a first dataset among the plurality of datasets stored in the non-volatile memory is provided in response to the command, and an accelerator which performs the first computation corresponding to the command, using the first dataset provided to the buffer memory. The accelerator includes a memory access module which receives a first input query for instructing the first computation and the first dataset from the buffer memory, and a first computing module which is connected to the memory access module and determines first final candidate data corresponding to the first input query, using the first dataset.

First claim

What is claimed is:

1. A storage device comprising:
a controller which receives a command from a host for instructing performance of a first computation;
a non-volatile memory which stores a plurality of datasets;
a buffer memory, wherein a first dataset among the plurality of datasets stored in the non-volatile memory is provided to the buffer memory in response to the command; and
an accelerator which performs the first computation corresponding to the command, using the first dataset provided to the buffer memory,
wherein the accelerator comprises:
a memory access module which receives a first input query and a second input query for instructing the first computation and the first dataset from the buffer memory, wherein the first input query is different from the second input query;
a first computing module which is connected to the memory access module and determines first final candidate data corresponding to the first input query, using the first dataset received from the memory access module, wherein the first computing module calculates first vector distances between the first input query and entry points of the first dataset and retains the first vector distances that are shorter than a minimum distance as the first final candidate data; and
a second computing module which is connected to the memory access module and determines second final candidate data corresponding to the second input query, using the same first dataset received from the memory access module, wherein the second computing module calculates second other vector distances between the second input query and the entry points and retains the second vector distances that are shorter than a minimum distance as the second final candidate data,
wherein at least one of the computing modules:
maintains a visit list that tracks previously evaluated data points within the corresponding dataset, wherein a data point from the corresponding dataset is added to the visit list after its vector distance to the corresponding input query has been calculated;
maintains a candidate list comprising unvisited data points within the corresponding dataset, wherein a data point from the corresponding dataset is added to the candidate list when its vector distance to the corresponding input query is within a predefined distance threshold and has not been previously evaluated; and

selects the corresponding final candidate data based on data points in the candidate list that meet a predefined threshold,
wherein a block random-access memory (RAM) of the storage device includes a first block RAM storing an activated visit list and a second block RAM storing an initialized visit list.

2. The storage device of claim 1 , wherein the accelerator includes a Field Programmable Gate Array (FPGA).

3. The storage device of claim 1 , wherein the accelerator performs the first computation, using a hierarchical navigable small world (HNSW) search algorithm.

4. The storage device of claim 1 , wherein the memory access module includes a final calculator,
the first computing module includes a first calculator and a first comparator,
the first calculator performs a calculation based on the first input query, using the first dataset,
the first comparator determines the first final candidate data, using a result calculated by the first calculator, and
the final calculator determines a first final result data, using the first final candidate data determined by the first comparator.

5. The storage device of claim 4 , wherein the second computing module includes a second comparator and a second calculator,
the second calculator performs the calculation based on the second input query,
the second comparator determines the second final candidate data, using the result calculated by the second calculator, and
the final calculator determines a second final result data, using the second final candidate data determined by the second comparator.

6. The storage device of claim 5 , wherein the accelerator provides the host with first and second final result data.

7. The storage device of claim 1 , wherein the memory access module and the first computing module are connected by a first-in-first-out (FIFO) interface.

8. The storage device of claim 1 , wherein the non-volatile memory provides the first dataset to the buffer memory in a peer-to-peer communication, using Peripheral Component Interconnect express (PCle).

9. A memory system comprising:
a host which provides a command for instructing performance of a first computation; and
a first storage device to which the command is provided from the host,
wherein the first storage device comprises:
a first controller which controls the first storage device in response to the command;
a first non-volatile memory which stores a first dataset;
a first buffer memory which receives the first dataset from the first non-volatile memory in response to the command; and
a first accelerator which performs the first computation corresponding to the command, using the first dataset provided to the first buffer memory,

wherein the first accelerator comprises:
a first memory access module which receives a first input query and a second input query for instructing the first computation and the first dataset from the first buffer memory, wherein the first input query is different from the second input query;
a first computing module which is connected to the first memory access module and determines first final candidate data corresponding to the first input query, using the first dataset received from the first memory access module, wherein the first computing module calculates first vector distances between the first input query and entry points of the first dataset and retains the first vector distances that are shorter than a minimum distance as the first final candidate data; and
a second computing module which is connected to the first memory access module and determines second final candidate data corresponding to the second input query, using the same first dataset received from the memory access module, wherein the second computing module calculates second other vector distances between the second input query and the entry points and retains the second vector distances that are shorter than a minimum distance as the second final candidate data, and

wherein the first accelerator provides the host with the first final candidate data and the second final candidate data,
wherein at least one of the computing modules:
maintains a visit list that tracks previously evaluated data points within the corresponding dataset, wherein a data point from the corresponding dataset is added to the visit list after its vector distance to the corresponding input query has been calculated;
maintains a candidate list comprising unvisited data points within the corresponding dataset, wherein a data point from the corresponding dataset is added to the candidate list when its vector distance to the corresponding input query is within a predefined distance threshold and has not been previously evaluated; and

selects the corresponding final candidate data based on data points in the candidate list that meet a predefined threshold,
wherein a block random-access memory (RAM) of the memory system includes a first block RAM storing an activated visit list and a second block RAM storing an initialized visit list.

10. The memory system of claim 9 , further comprising:
a second storage device to which the command is provided from the host,
wherein the second storage device includes
a second controller which controls the second storage device in response to the command,
a second non-volatile memory which stores a second dataset different fro

Assignees

• Samsung Electronics Co Ltd

Inventors

• Ji Soo Young
• Kim Joo Young
• Kim Ji Hoon
• Do Jae Young
• Park Yeo Reum

Classifications

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F3/0679 Primary

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F3/0658

  Controller construction arrangements · CPC title

• G06F3/0664

  at device level, e.g. emulation of a storage device or system · CPC title

• G06F3/0659 Primary

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title