System and method for hierarchical sort acceleration near storage

Patent metadata

Field	Value
Publication number	US-11249651-B2
Application number	US-202016821811-A
Country	US
Kind code	B2
Filing date	Mar 17, 2020
Priority date	Oct 29, 2019
Publication date	Feb 15, 2022
Grant date	Feb 15, 2022

Abstract

A storage system includes: a storage device to store an array of data elements associated with a sort operation; a storage interface to facilitate communications between the storage device and a host computer; and a reconfigurable processing device communicably connected to the storage device, the reconfigurable processing device including: memory to store input data read from the storage device, the input data corresponding to the array of data elements stored in the storage device; and a kernel including one or more compute components to execute the sort operation on the input data stored in the memory according to a SORT command received from the host computer. The reconfigurable processing device is to dynamically instantiate the one or more compute components to accelerate the sort operation.

First claim

What is claimed is:

1. A storage system comprising:
a storage device configured to store an array of data elements associated with a sort operation;
a storage interface configured to facilitate communications between the storage device and a host computer; and
a reconfigurable processing device communicably connected to the storage device, the reconfigurable processing device comprising:
memory configured to store input data read from the storage device, the input data corresponding to the array of data elements stored in the storage device; and
a kernel comprising one or more compute components configured to execute the sort operation on the input data stored in the memory according to a SORT command received from the host computer,

wherein the reconfigurable processing device is configured to dynamically instantiate the one or more compute components according to a comparison of a size of the input data with one or more threshold sizes to accelerate the sort operation.

2. The storage system of claim 1 , wherein the reconfigurable processing device comprises a field programmable gate array (FPGA), and the storage device comprises a solid state drive (SSD).

3. The storage system of claim 2 , wherein the input data is read from the SSD by the host computer and loaded into primary memory of the host computer, and the memory of the FPGA is configured to receive the input data from the primary memory of the host computer.

4. The storage system of claim 2 , further comprising a direct interconnect between the memory and the SSD, and the FPGA is configured to directly access the SSD to read the input data from the SSD to the memory via the direct interconnect.

5. The storage system of claim 4 , wherein the FPGA and the SSD are implemented on the same circuit board.

6. The storage system of claim 4 , wherein the FPGA is configured to access the SSD via the direct interconnect using point-to-point (P2P) communications to bypass the host computer when reading data from the SSD.

7. The storage system of claim 4 , wherein the memory comprises dynamic random-access memory (DRAM).

8. The storage system of claim 1 , wherein the one or more compute components comprises a plurality of processing elements, and each of the plurality of processing elements is configured to sort a segment of the array of data elements corresponding to the input data according to a sorting algorithm.

9. A storage system comprising:
a storage device configured to store an array of data elements associated with a sort operation;
a storage interface configured to facilitate communications between the storage device and a host computer; and
a reconfigurable processing device communicably connected to the storage device, the reconfigurable processing device comprising:
memory configured to store input data read from the storage device, the input data corresponding to the array of data elements stored in the storage device; and
a kernel comprising one or more compute components configured to execute the sort operation on the input data stored in the memory according to a SORT command received from the host computer,

wherein the reconfigurable processing device is configured to dynamically instantiate the one or more compute components to accelerate the sort operation,
wherein the one or more compute components comprises a plurality of processing elements, and each of the plurality of processing elements is configured to sort a segment of the array of data elements corresponding to the input data according to a sorting algorithm, and
wherein each of the processing elements comprises a local comparator and a local merger, and the local comparator and the local merger are configured to generate a partially sorted array from the segment using the sorting algorithm.

10. The storage system of claim 9 , wherein the one or more compute components further comprises a processing unit connected to an output of each of the processing elements, and the processing unit is configured to sort the outputs of the processing elements according to the sorting algorithm.

11. The storage system of claim 10 , wherein the processing unit comprises a global comparator and a global merger, and the global comparator and the global merger are configured to generate a fully sorted array of the input data from the partially sorted arrays output by the processing elements using the sorting algorithm.

12. The storage system of claim 11 , wherein the sorting algorithm is a Bitonic sorting algorithm.

13. The storage system of claim 11 , wherein the reconfigurable processing device is configured to dynamically instantiate a number of the processing elements and the processing unit at run-time according to a size of the array of data elements.

14. The storage system of claim 13 , wherein the reconfigurable processing device is configured to:
identify a size of the array of data elements;
compare the size of the array of data elements with one or more threshold sizes; and
instantiate the number of processing elements and the processing unit according to the comparison.

15. A method for dynamically scaling a sort operation for a storage system comprising a storage device to store an array of data elements associated with a sort operation, a storage interface to facilitate communications between the storage device and a host computer, and a reconfigurable processing device communicably connected to the storage device, the method comprising:
identifying, by the reconfigurable processing device, a size of the array of data elements associated with a sort command from the host computer;
comparing, by the reconfigurable processing device, the size with one or more threshold sizes; and
instantiating, by the reconfigurable processing device, one or more compute components according to the comparison to accelerate the sort operation.

16. The method of claim 15 , wherein the reconfigurable processing device comprises a field programmable gate array (FPGA), and the storage device comprises a solid state drive (SSD).

17. The method of claim 16 , wherein the instantiating of the one or more compute components comprises reconfiguring one or more logic blocks and one or more interconnects of a kernel of the FPGA.

18. The method of claim 16 , wherein the instantiating of the one or more compute components comprises instantiating, by the reconfigurable processing device, at least one local sort compute component, and
wherein the method further comprises:
sorting, by the at least one local sort compute component, at least a segment of the array of data elements; and
generating, by the at least one local sort compute component, a sorted array of the at least the segment.

19. The method of claim 16 , wherein the instantiating of the one or more compute components comprises instantiating, by the reconfigurable processing device, a plurality of local sort compute components, and
wherein the method further comprises:
sorting, by each of the local sort compute components, a different segment of the array of data elements; and
generating, by each of the local sort compute components, a partially sorted array of the corresponding segment.

20. The method of claim 19 , wherein the instantiating of the one or more compute components further comprises instantiating, by the reconfigurable processing device, a global sort compute component connected to outputs of each of the local sort compute components, and
wherein the method further comprises:
sorting, by the global sort compute component,

Assignees

• Samsung Electronics Co Ltd

Inventors

• Salamat Sahand
• Zhang Hui
• Lee Joo Hwan
• Ki Yang Seok

Classifications

• G06F3/0658

  Controller construction arrangements · CPC title

• G06F3/0679

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

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/061

  Improving I/O performance · CPC title