Field-programmable gate array based accelerator system

• US 8,583,569 B2
• Filed: 12/22/2011
• Issued: 11/12/2013
• 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, Cai, Xiong-Fei, Hsu, Feng-Hsiung
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US13/335,333
• Publication Number:
  US 20120092040A1
• Time in Patent Office: 691 Days
• Field of Search: 706/12, 706/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) provided on a substrate;

a memory connected to the substrate and the FPGA;

an interface for connecting the FPGA to a computing device; and

a relevance-ranking algorithm for documents implemented at least in part by the FPGA, the FPGA configured to generate a result of the relevance-ranking algorithm based at least in part on the FPGA building an integral histogram based at least in part on feature values corresponding to one or more terms in one or more of the documents included in training data associated with the relevance-ranking algorithm.

2. A system as recited in claim 1, wherein the substrate comprises a Peripheral Component Interface (PCI) board, PCI-X board, PCI-Express board, HyperTransport board, Universal Serial Bus (USB) board or Front-Side Bus (FSB) board.

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

4. A system as recited in claim 3, wherein the memory comprises Double Data Rate (DDR) memory.

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

6. A system as recited in claim 1, wherein the FPGA comprises a number of processing engine (PE) unit, and wherein data is arranged in a First In First Out (FIFO) buffer to map the data onto the PE unit.

7. A system as recited in claim 1, wherein the FPGA associated with a computing device 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 the second computing device.

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

9. A method comprising:

mapping data in one or more data structures to one or more memories associated with a Field Programmable Gate Array (FPGA), wherein at least a portion of the data includes training data associated with a relevance-ranking algorithm for documents; and

learning the relevance ranking-algorithm based at least in part on logic of the FPGA building one or more integral histograms based at least in part on feature values associated with the training data corresponding to one or more terms of at least one of the documents.

10. A method as recited in claim 9, wherein the relevance-ranking algorithm comprises at least a portion of a RankBoost algorithm.

11. A method as recited in claim 9, further comprising loading the training data into at least one of the one or more memories associated with the FPGA, wherein the training data is organized according to a streaming memory access order for streaming memory access by processing engines (PEs) of the FPGA for the building of the one or more integral histograms, wherein the training data includes the feature values classified into bins that define at least in part the streaming memory access order.

12. A method as recited in claim 9, further comprising utilizing memory within the FPGA as a cache memory.

13. The method of claim 9, further comprising compressing data in the one or more data structures prior to mapping the one or more data structures in the one or more memories.

14. The method of claim 9, wherein the relevance-ranking algorithm is document based.

15. The method of claim 9, further comprising organizing the data according to input data structure of processing units in the FPGA and according to the order by which the FPGA will access the data.

16. A system comprising:

a memory; and

a Field Programmable Gate Array (FPGA) connected to the memory, the FPGA configured to learn a relevance-ranking algorithm for documents by processing engines (PEs) of the FPGA building integral histograms using training data associated with term-based feature values of the documents, wherein the term-based feature values are organized into bins that define at least in part a streaming memory access order for storing at least a portion of the training data in the memory for streaming memory access by each of the PEs for the building of the integral histograms.

17. A system of claim 16, wherein the memory includes at least a portion of the training data.

18. A system of claim 16, wherein the FPGA uses the processing engines (PEs) of the FPGA to build the integral histograms.

19. A system of claim 16, wherein the FPGA is configured to build the integral histograms in parallel using the training data associated with the relevance-ranking algorithm.

20. A system of claim 16, wherein the training data is associated with the relevance-ranking algorithm;

and

building the integral histograms comprises summing elements of the integral histograms.