Field-programmable gate array based accelerator system

• US 8,117,137 B2
• Filed: 04/19/2007
• Issued: 02/14/2012
• Est. Priority Date: 04/19/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Ning-yi, Hsu, Feng-Hsiung, Cai, Xiong-Fei
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US11/737,605
• Publication Number:
  US 20080262984A1
• Time in Patent Office: 1,762 Days
• Field of Search: 706/12, 716/16
• US Class Current: 706/12
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

Accelerator systems and methods are disclosed that utilize FPGA technology to achieve better parallelism and flexibility. The accelerator system may be used to implement a relevance-ranking algorithm, such as RankBoost, for a training process. The algorithm and related data structures may be organized to enable streaming data access and, thus, increase the training speed. The data may be compressed to enable the system and method to be operable with larger data sets. At least a portion of the approximated RankBoost algorithm may be implemented as a single instruction multiple data streams (SIMD) architecture with multiple processing engines (PEs) in the FPGA. Thus, large data sets can be loaded on memories associated with an FPGA to increase the speed of the relevance ranking algorithm.

Claims

1. A system comprising:

a Field Programmable Gate Array (FPGA) to perform a machine learning algorithm using training data;

a Peripheral Component Interface (PCI) controller to communicate with a Central Processing Unit (CPU) of a host computing device, and

a memory hierarchy composed of Static Random Access Memory (SRAM) and Synchronous Dynamic Random Access Memory (SDRAM) associated with the FPGA and embedded Random Access Memory (RAM) within the FPGA, the training data being loaded onto at least a portion of the memory hierarchy and organized according to a streaming memory access order for streaming memory access by logic associated with the FPGA; and

a control unit within the FPGA to direct the FPGA to;

build a histogram based in part on at least a subset of the training data;

build an integral histogram based in part on the histogram; and

send a result of the machine learning algorithm to a First In First Out (FIFO) queue for presentation to the host computing device, the result being based at least in part on the integral histogram.

2. A system according to claim 1, wherein the machine learning algorithm comprises a document-based relevance-ranking algorithm implemented at least in part as a single instruction multiple data stream (SIMD) architecture with multiple processing engines (PEs) in the FPGA.

3. A system according to claim 1, wherein:

randomly used large-scale data structures are loaded onto the SRAM to be used as a large low latency cache; and

temporary data structures are stored in the embedded RAM to act as high bandwidth, low latency cache.

4. A system according to claim 1, wherein multiple FPGAs are provided for connection to a computer.

5. A system according to claim 4, wherein multiple computers are connected together through a network.

6. A system according to claim 1, the training data being stored in the memory hierarchy in a compressed format, the FPGA configured to decompress the training data prior to the using the training data.

7. A system according to claim 1, the streaming memory access order enabling the streaming memory access by the logic without interaction with software or drivers.

8. A system as recited in claim 1, wherein the FPGA has at least one processing engine, and the at least one processing engine is controlled by a control unit.

9. A system as recited in claim 1, wherein the machine learning algorithm comprises a relevance ranking algorithm.

10. A system as recited in claim 9, wherein the relevance ranking algorithm incorporates a RankBoost algorithm.

11. A system as recited in claim 9, wherein the relevance ranking algorithm is document based.

12. A system as recited in claim 1, wherein the FPGA is a first FPGA associated with a first computing device, the system further comprising a network connecting the first FPGA associated with the first computing device to a second FPGA associated with a second computing device.

13. A system as recited in claim 12, wherein the first and second computing devices are each associated with multiple FPGA devices.

14. A system as recited in claim 1, the training data comprises feature values of documents classified into bins defining the streaming memory access order.

15. A system as recited in claim 14, the FPGA builds the histogram based in part on feature values of at least one of the documents classified into the bins associated with the subset of the training data.

16. A system as recited in claim 1, wherein the FPGA comprises multiple processing engines (PEs), and the training data is arranged in a First In First Out (FIFO) buffer to map the training data onto each of the multiple PEs using the streaming memory access order, the streaming memory access order enabling the streaming memory access by each of the PEs without interaction with software or drivers.

17. A system comprising:

a Field Programmable Gate Array (FPGA) to perform a machine learning algorithm using training data, the FPGA comprising multiple processing engines (PEs);

a Peripheral Component Interface (PCI) controller to communicate with a Central Processing Unit (CPU) of a host computing device; and

a memory hierarchy composed of Static Random Access Memory (SRAM) and Synchronous Dynamic Random Access Memory (SDRAM) associated with the FPGA and embedded Random Access Memory (RAM) within the FPGA, the training data being loaded onto the memory hierarchy and organized according to a streaming memory access order for streaming memory access by each of the PEs, the streaming memory access order enabling the streaming memory access by each of the PEs without interaction with software or drivers, the training data being stored in the memory hierarchy in a compressed format, the FPGA being configured to decompress the training data prior to the using the training data; and

a control unit within the FPGA to direct one or more components of the FPGA to;

build a histogram based in part on at least a subset of the training data;

build an integral histogram based in part on the histogram; and

provide a result of the machine learning algorithm for presentation to the host computing device, the result being based at least in part on the integral histogram.

18. A system according to claim 17, wherein multiple FPGAs are provided for connection to a computer.

19. A system as recited in claim 17, wherein the machine learning algorithm comprises a relevance ranking algorithm that incorporates a RankBoost algorithm that is document based.

20. A system as recited in claim 17, the training data comprises feature values of documents classified into bins defining the streaming memory access order.

21. A system as recited in claim 20, the FPGA builds the histogram based in part on the feature values of at least one of the documents classified into the bins associated with the subset of the training data.

22. A system comprising:

a Field Programmable Gate Array (FPGA) to perform a machine learning algorithm using training data, the machine learning algorithm comprising a document-based relevance-ranking algorithm implemented at least in part as a single instruction multiple data streams (SIMD) architecture using processing engines (PEs) in the FPGA;

a memory hierarchy composed of Double Data Rate (DDR) memory associated with the FPGA and embedded Random Access Memory (RAM) within the FPGA, the training data being loaded onto the memory hierarchy and organized according to a streaming memory access order for streaming memory access by each of the PEs, the training data includes feature values of documents classified into bins that define at least in part the streaming memory access order; and

a control unit within the FPGA to direct the PEs to;

build histograms based in part on the feature values of the documents as classified into the bins; and

build multiple integral histograms based in part on at least a subset of the histograms, the multiple integral histograms being built at the same time.