FPGA implementation of sparse matrix algorithm for information retrieval

Slobodan Bojanic; Ruzica Jevtic; Octavio Nieto-Taladriz

doi:10.1117/12.608390

30 June 2005 FPGA implementation of sparse matrix algorithm for information retrieval

Slobodan Bojanic, Ruzica Jevtic, Octavio Nieto-Taladriz

Proceedings Volume 5837, VLSI Circuits and Systems II; (2005) https://doi.org/10.1117/12.608390
Event: Microtechnologies for the New Millennium 2005, 2005, Sevilla, Spain

Abstract

Information text data retrieval requires a tremendous amount of processing time because of the size of the data and the complexity of information retrieval algorithms. In this paper the solution to this problem is proposed via hardware supported information retrieval algorithms. Reconfigurable computing may adopt frequent hardware modifications through its tailorable hardware and exploits parallelism for a given application through reconfigurable and flexible hardware units. The degree of the parallelism can be tuned for data. In this work we implemented standard BLAS (basic linear algebra subprogram) sparse matrix algorithm named Compressed Sparse Row (CSR) that is showed to be more efficient in terms of storage space requirement and query-processing timing over the other sparse matrix algorithms for information retrieval application. Although inverted index algorithm is treated as the de facto standard for information retrieval for years, an alternative approach to store the index of text collection in a sparse matrix structure gains more attention. This approach performs query processing using sparse matrix-vector multiplication and due to parallelization achieves a substantial efficiency over the sequential inverted index. The parallel implementations of information retrieval kernel are presented in this work targeting the Virtex II Field Programmable Gate Arrays (FPGAs) board from Xilinx. A recent development in scientific applications is the use of FPGA to achieve high performance results. Computational results are compared to implementations on other platforms. The design achieves a high level of parallelism for the overall function while retaining highly optimised hardware within processing unit.

Citation Download Citation

Slobodan Bojanic, Ruzica Jevtic, and Octavio Nieto-Taladriz "FPGA implementation of sparse matrix algorithm for information retrieval", Proc. SPIE 5837, VLSI Circuits and Systems II, (30 June 2005); https://doi.org/10.1117/12.608390

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available