Intelligent data storage and processing using FPGA devices

• US 8,620,881 B2
• Filed: 06/21/2011
• Issued: 12/31/2013
• Est. Priority Date: 05/23/2003
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Chamberlain, Roger D., Brink, Benjamin M., White, Jason R., Franklin, Mark A., Cytron, Ron K.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Bullock, Joshua
• Application Number:
  US13/165,155
• Publication Number:
  US 20110252008A1
• Time in Patent Office: 924 Days
• Field of Search: 707/693
• US Class Current: 707/693
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 21/85 interconnection devices, e.g. bus-connected or in-line devices
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/44505 Configuring for program initiating, e.g. using registry, configuration files
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis

Abstract

Methods and apparatuses for processing data are disclosed, including methods and apparatuses that leverage a reconfigurable logic device to offload decompression and search operations from a processor to thereby enable high speed data searches within data that has been stored in a compressed format.

Claims

1. A data processing apparatus comprising:

a processor for communicating with a data storage device to store data in and retrieve data from the data storage device; and

a reconfigurable logic device for offloading a plurality of processing operations from the processor, the reconfigurable logic device comprising a hardware logic template configured as a data processing pipeline, the data processing pipeline comprising a decompression engine and a downstream search engine;

wherein the decompression engine is configured to (1) receive a stream of compressed data retrieved from the data storage device, and (2) perform a decompression operation on the compressed data stream to thereby create a stream of decompressed data;

wherein the search engine is configured to (1) store a data key, the data key being representative of data of interest, (2) receive the stream of decompressed data created by the decompression engine, and (3) perform a search operation by matching the received decompressed data against the data key;

wherein the decompression engine and the search engine are configured to operate in a pipelined manner by performing their respective decompression and search operations simultaneously at hardware processing speeds such that the decompression engine performs the decompression operation on compressed data while at the same time the search engine performs the search operation on decompressed data that was previously decompressed by the decompression engine; and

wherein the processor is configured to send a search request to the reconfigurable logic device, the search request pertaining to the search operation with respect to compressed data that is stored in the data storage device and to be offloaded from the processor to the reconfigurable logic device, the search request comprising a plurality of parameters for controlling the search operation, at least one of the parameters comprising the data key.

2. The apparatus of claim 1 further comprising:

the data storage device, the data storage device configured to store data in a compressed format.

3. The apparatus of claim 1 wherein the data storage device comprises a hard disk drive.

4. The apparatus of claim 1 wherein the search engine is configured to perform an approximate match operation between the streaming decompressed data and the data key.

5. The apparatus of claim 1 wherein the search engine is further configured to (1) generate a signal indicative a similarity between the data key and a portion of the streaming decompressed data, and (2) compare the generated signal with a threshold value to thereby determine whether the streaming decompressed data portion is deemed a match to the data key, wherein the threshold value is adjustable to control whether the search engine performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

6. The apparatus of claim 5 wherein the data key comprises a digital data key, and wherein the search engine is further configured to process portions of the streaming decompressed data against the data key on a frame-by-frame basis to generate the similarity signal.

7. The apparatus of claim 6 wherein the parameters further comprise a specification of the threshold value.

8. The apparatus of claim 7 wherein the parameters further comprise a starting location for the streaming decompressed data with respect to the search operation and a final location for the streaming decompressed data with respect to the search operation for terminating the search operation if no match is found.

9. The apparatus of claim 7 wherein the parameters further comprise data representative of information to be returned by the reconfigurable logic device when a match is found.

10. The apparatus of claim 9 further comprising a cache memory, wherein the reconfigurable logic device is further in communication with the cache memory, and wherein the parameters further comprise data representative of whether the reconfigurable logic device is to return the information to the system bus or the cache memory.

11. The apparatus of claim 1 wherein the reconfigurable logic device includes internal memory that is not accessible to the processor, and wherein the reconfigurable logic device is further configured to store the decompressed data only in its internal memory.

12. The apparatus of claim 1 further comprising a processing board on which the reconfigurable logic device is deployed, the processing board in communication with the processor and the data storage device via a system bus, the processing board further comprising a memory device that is not accessible to the processor, wherein the reconfigurable logic device is further configured to store the decompressed data only in the memory device.

13. The apparatus of claim 1 further comprising a processing board on which the reconfigurable logic device is deployed, wherein the reconfigurable logic device includes internal memory that is not accessible to the processor, the processing board in communication with the processor and the data storage device via a system bus, the processing board further comprising a memory device that is not accessible to the processor, and wherein the reconfigurable logic device is further configured to store a portion of the decompressed data in its internal memory and store another portion of the decompressed data in the memory device.

14. The apparatus of claim 1 wherein the compressed data comprises compressed data that was compressed using LZ compression, and wherein the decompression engine is configured to perform LZ decompression.

15. The apparatus of claim 1 wherein the compressed data comprises compressed data that was compressed using lossless compression, wherein the decompression engine is configured to perform lossless decompression.

16. The apparatus of claim 1 wherein the compressed data comprises compressed data that was compressed using lossy compression, wherein the decompression engine is configured to perform lossy decompression.

17. An apparatus for processing data received from a mass storage medium, the apparatus comprising:

a reconfigurable logic device configured to receive a stream of compressed data from a mass storage medium, wherein the reconfigurable logic device comprises a hardware logic template configured as a data processing pipeline, the data processing pipeline comprising a decompression engine and a downstream search engine;

the decompression engine configured to perform a decompression operation on the received compressed data stream to create a stream of decompressed data;

the search engine configured to (1) store a data key, the data key being representative of the data of interest, (2) receive streaming decompressed data created by the decompression engine, and (3) perform a search operation within the stream of decompressed data to find data of interest within the stream of decompressed data by matching the received decompressed data against the data key; and

wherein the decompression engine and the search engine are configured to operate in a pipelined manner by operating simultaneously such that the decompression engine operates to perform the decompression operation on compressed data while at the same time the search engine operates to perform the search operation on decompressed data that was previously decompressed by the decompression engine.

18. The apparatus of claim 17 wherein the data processing pipeline comprises at least another data processing engine, the another data processing engine configured to perform a data processing operation other than a decompression operation and a search operation.

19. The apparatus of claim 17 wherein the search operation is configured to determine whether a pattern match exists between the data key and a data signal that is representative of a decompressed data stream.

20. The apparatus of claim 17 further comprising the mass storage medium, wherein the mass storage medium comprises a magnetic storage device.

21. The apparatus of claim 17 wherein the search engine is further configured to perform the search operation on a frame-by-frame basis.

22. The apparatus of claim 17 wherein the search engine is further configured to perform the search operation on a frameless basis.

23. The apparatus of claim 17 wherein the reconfigurable logic device comprises a programmable logic device.

24. The apparatus of claim 17 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

25. A method for processing data received from a mass storage medium, the method comprising:

receiving, by a reconfigurable logic device, a stream of compressed data from a mass storage medium, wherein the reconfigurable logic device comprises a hardware logic template configured as a data processing pipeline, the data processing pipeline comprising a decompression engine and a downstream search engine;

the decompression engine performing a decompression operation on the received compressed data stream to create a stream of decompressed data; and

the search engine (1) storing a data key, the data key being representative of the data of interest, (2) receiving streaming decompressed data created by the decompression engine, and (3) performing a search operation within the stream of decompressed data to find data of interest within the stream of decompressed data by matching the received decompressed data against the data key; and

the decompression engine and the search engine operating in a pipelined manner by operating simultaneously such that the decompression engine performs the decompression operation on compressed data while at the same time the search engine performs the search operation on decompressed data that was previously decompressed by the decompression engine.

26. The method of claim 25 further comprising:

a processor sending a search request to the reconfigurable logic device, the search request pertaining to a search operation to be offloaded from the processor to the reconfigurable logic device with respect to data that is stored in the mass storage medium in compressed form, the search request comprising a plurality of parameters for controlling the search operation, at least one of the parameters comprising the data key; and

the decompression engine and the search engine performing their respective decompression and search operations in a pipelined manner at hardware processing speeds.

27. The method of claim 25 wherein the data processing pipeline comprises at least another data processing engine, the method further comprising the another data processing engine performing a data processing operation other than a decompression operation and a search operation.

28. The method of claim 26 wherein the search operation performing step comprises the search engine performing an approximate match operation between the streaming decompressed data and the data key.

29. The method of claim 26 wherein the search operation performing step further comprises:

the search engine (1) generating a signal indicative a similarity between the data key and a portion of the streaming decompressed data, and (2) comparing the generated signal with a threshold value to thereby determine whether the streaming decompressed data portion is deemed a match to the data key, wherein the threshold value is adjustable to control whether the search engine performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

30. The method of claim 29 wherein the data key comprises a digital data key, and wherein the search operation performing step further comprises the search engine processing portions of the streaming decompressed data against the data key on a frame-by-frame basis to generate the similarity signal.

31. The method of claim 30 wherein the parameters further comprise a specification of the threshold value.

32. The method of claim 31 wherein the parameters further comprise a starting location for the streaming decompressed data with respect to the search operation and a final location for the streaming decompressed data with respect to the search operation for terminating the search operation if no match is found.

33. The method of claim 31 wherein the parameters further comprise data representative of information to be returned by the reconfigurable logic device when a match is found.

34. The method of claim 33 wherein the parameters further comprise data representative of whether the reconfigurable logic device is to return the information to a system bus or a cache memory.

35. The method of claim 26 wherein the reconfigurable logic device includes internal memory that is not accessible to the processor, the method further comprising the reconfigurable logic device storing the decompressed data only in its internal memory.

36. The method of claim 26 wherein the reconfigurable logic device is deployed on a processing board, the processing board in communication with the processor and the mass storage medium via a system bus, the processing board further comprising a memory device that is not accessible to the processor, the method further comprising the reconfigurable logic device storing the decompressed data only in the memory device.

37. The method of claim 26 wherein the reconfigurable logic device is deployed on a processing board, wherein the reconfigurable logic device includes internal memory that is not accessible to the processor, the processing board in communication with the processor and the mass storage medium via a system bus, the processing board further comprising a memory device that is not accessible to the processor, the method further comprising the reconfigurable logic device storing a portion of the decompressed data in its internal memory and storing another portion of the decompressed data in the memory device.

38. The method of claim 26 wherein the compressed data comprises compressed data that was compressed using LZ compression, and wherein the decompression operation performing step comprises the decompression engine performing LZ decompression.

39. The method of claim 26 wherein the compressed data comprises compressed data that was compressed using lossless compression, and wherein the decompression operation performing step comprises the decompression engine performing lossless decompression.

40. The method of claim 26 wherein the compressed data comprises compressed data that was compressed using lossy compression, and wherein the decompression operation performing step comprises the decompression engine performing lossy decompression.

41. The method of claim 25 wherein the search operation performing step comprises the search engine determining whether a pattern match exists between the data key and a data signal that is representative of a decompressed data stream.

42. The method of claim 25 wherein the mass storage medium comprises a magnetic storage device.

43. The method of claim 25 wherein the search operation performing step comprises the search engine performing the search operation on a frame-by-frame basis.

44. The method of claim 25 wherein the search operation performing step comprises the search engine performing the search operation on a frameless basis.

45. The method of claim 25 wherein the reconfigurable logic device comprises a programmable logic device.

46. The method of claim 25 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).