Associative database scanning and information retrieval using FPGA devices

• US 20030018630A1
• Filed: 05/21/2002
• Published: 01/23/2003
• Est. Priority Date: 04/07/2000
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Chamberlain, Roger D., Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron Kaplan
• Granted Patent: US 7,139,743 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A data storage and retrieval device and method is disclosed. The device includes at least one magnetic storage medium configured to store target data and at least one re-configurable logic device comprising an FPGA coupled to the at least one magnetic storage medium and configured to read a continuous stream of target data therefrom, having been configured with a template or as otherwise desired to fit the type of search and data being searched. The re-configurable logic device is configured to receive at least one search inquiry in the form of a data key and to determine a match between the data key and the target data as it is being read from the at least one magnetic storage medium. This device and method can perform a variety of searches on the target data including without limitation exact and approximate match searches, sequence match searches, image match searches and data reduction searches. This device and method may be provided as part of a stand-alone computer system, embodied in a network attached storage device, or can otherwise be provided as part of a computer LAN or WAN.

Claims

1. A data searching device for connection between a magnetic data storage device and a CPU, said data searching device comprising a FPGA, said FPGA being re-configurable to perform a search on data stored in said data storage device.

2. The data searching device of claim 1 wherein said CPU is configured to transmit a template to said FPGA to thereby reconfigure it.

3. The data searching device of claim 2 wherein said CPU is configured to transmit a key to said FPGA for matching to data read from the data storage device in performing the search.

4. The data searching device of claim 3 further comprising a data shift register connected between the data storage device and the FPGA, the data storage device being configured to store target data as it is read from the data storage device.

5. The data searching device of claim 1 wherein said device further comprises a dedicated CPU connected between the FPGA and the other CPU, said dedicated CPU being configured to transmit a template to said FPGA to thereby reconfigure it.

6. The data searching device of claim 5 wherein said dedicated CPU is configured to transmit a key to said FPGA for matching to data read from the data storage device in performing the search.

7. The data searching device of claim 6 further comprising a data shift register connected between the data storage device and the FPGA, the data storage device being configured to store target data as it is read from the data storage device.

8. The data searching device of claim 1 wherein said FPGA comprises a dedicated CPU and a re-configurable logic device.

9. The data searching device of claim 8 wherein said FPGA further comprises a data shift register.

12. The hard disk drive accelerator of claim 9 further comprising a pc board, and wherein said hard disk drive accelerator is mounted thereto.

13. The hard disk drive accelerator of claim 9 wherein said FPGA comprises a data processor, a re-configurable logic device, and a data shift register.

10. A hard disk drive accelerator for connection between a hard disk drive and a processor, said accelerator comprising an FPGA having processing capability and arranged so that data read from the hard disk drive flows to the FPGA for processing prior to being passed on to the processor.

11. The hard disk drive accelerator of claim 10 further comprising a shift register connected to the FPGA and configured to receive data as it is read from the hard disk.

15. The data storage and retrieval device of claim 14 wherein the mass data storage device is a hard disk.

16. The data storage and retrieval device of claim 15 wherein the re-configurable logic device is configured to receive at least one search inquiry in the form of a data key, and to determine a match between the data key and the target data as it is read from the at least one mass data storage device.

17. The data storage and retrieval device of claim 16 wherein the re-configurable logic device is configured to search for matches between an analog data key and an analog target data.

18. The data storage and retrieval device of claim 16 wherein the re-configurable logic device is configured to search for matches between a digital data key and a digital target data.

19. The data storage and retrieval device of claim 14 further comprising a plurality of magnetic storage media, each of said magnetic storage media having an associated re-configurable logic device.

20. The data storage and retrieval device of claim 14 wherein the data key is a sequence having a plurality of elements, and the re-configurable logic device comprises:

a table generator configured to generate a table having a plurality of table entries based on the elements of the sequence and

the target data read from the at least one magnetic storage medium; and

a comparator configured to compare each table entry to a predetermined threshold and determine the match based on the comparison therebetween.

21. The data storage and retrieval device of claim 14 wherein the data key is an image having a plurality of pixels, and the re-configurable logic device comprises an array generator configured to generate at least one array having a plurality of cells, each cell being configured to determine a match between one pixel of the data key and one pixel of the target data as it is read from the at least one magnetic storage medium.

22. The data storage and retrieval device of claim 21 wherein each cell of the array comprises:

a data key pixel register configured to store the data key pixels;

a target data pixel register configured to load the target data pixels; and

a comparator configured to compare the data key pixels stored in the data key pixel register with the target data pixels stored in the target data pixel register to determine whether there is a match therebetween.

23. The data storage and retrieval device of claim 22 wherein the comparator is further configured to communicate with other neighboring cells of the array to determine a match between each cell and its other neighboring cells.

24. The data storage and retrieval device of claim 22 further comprising a copy register configured to store a copy of the target data pixel register once an entire target image has been loaded therein and wherein the comparator is configured to compare in parallel the last image loaded in the target data pixel register with the current image being loaded in the target data pixel register.

25. The data storage and retrieval device of claim 22 further comprising a load data key pixel register configured to load the data key pixels of the array concurrently with the loading of the target data pixels in the target data pixel register.

26. The data storage and retrieval device of claim 14 wherein the re-configurable logic device is configured to compute aggregate data reductions on any matches determined thereby.

27. The data storage and retrieval device of claim 26 further comprising a plurality of re-configurable logic devices, and a plurality of data shift registers configured to store target data as it is read from the at least one magnetic storage medium, each data shift register connected between the at least one magnetic storage medium and each re-configurable logic device.

29. The device of claim 28 wherein the computer network includes at least one computer, and wherein that one computer is configured to reconfigure the FPGA for different types of search protocols.

30. The device of claim 28 wherein the FPGA further comprises processor capability for reconfiguring the FPGA for different types of search protocols.

31. The device of claim 28 further comprising a data processor for reconfiguring the FPGA for different types of search protocols.

14. A data storage and retrieval device comprising at least one mass data storage device configured to at least temporarily store target data and at least one re-configurable logic device comprising an FPGA coupled to the at least one mass data storage device, said re-configurable logic device being configurable to read a continuous stream of target data therefrom.

28. A device for retrieving data from at least one magnetic storage medium, the device being coupled to said at least one magnetic storage medium and interfacing the at least one magnetic storage medium with a computer network desiring the retrieved data for processing thereof, the device comprising a re-configurable logic device comprising an FPGA configured to compare a data key representative of the data sought to be retrieved with a target data representative of data read from the at least one magnetic storage medium.

32. A network attached storage device, comprising:

at least one magnetic storage medium; and

at least one re-configurable logic device coupled to the at least one magnetic storage medium, the network attached device having a network addressable input/output port configured to receive search inquiries and respond thereto.

33. A method of retrieving data from at least one magnetic storage medium, comprising:

receiving a search inquiry in the form of a data key from a processor in communication with the at least one magnetic storage medium;

receiving target data from the at least one magnetic storage medium;

comparing the data key with the target data as it is read from the at least one magnetic storage medium with a re-configurable logic device comprising an FPGA; and

determining a match based on the comparison therebetween.

34. The method of claim 33 wherein the data key is a sequence having a plurality of elements and wherein the method further comprises the steps of:

generating a table having a plurality of table entries based on the elements of the sequence and the target data read from the at least one magnetic storage device;

comparing each table entry to a predetermined threshold; and

determining a match based on the comparisons therebetween.

35. The method of claim 34 wherein the data key is an image having a plurality of data key pixels, the target data are images having a plurality of target data pixels, and wherein the method further comprises the steps of:

storing the data key pixels in a data key register;

loading the target data pixels into a target data pixel register;

comparing the data key pixels and the target data pixels; and

determining a match based on the comparisons therebetween.

36. The method of claim 35 further comprising generating at least one array having a plurality of cells, each cell configured to perform the storing, loading and comparing steps of claim 33.

37. The method of claim 35 further comprising:

storing a copy of the target data pixel register once an entire target image has been loaded therein; and

comparing in parallel the last image loaded in the target data pixel register with the current image being loaded in the target data pixel register.

38. The method of claim 37 further comprising loading the data key pixels concurrently with the loading of the target data pixels in the target data pixel register.

39. The method of claim 38 further comprising computing aggregate data reductions on any determined matches.