Share Email Print
cover

Proceedings Paper

FPGA implementation of sparse matrix algorithm for information retrieval
Author(s): Slobodan Bojanic; Ruzica Jevtic; Octavio Nieto-Taladriz
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 30 June 2005
PDF: 10 pages
Proc. SPIE 5837, VLSI Circuits and Systems II, (30 June 2005); doi: 10.1117/12.608390
Show Author Affiliations
Slobodan Bojanic, Univ. Politecnica de Madrid, ETSIT Cuidad Univ. (Spain)
Ruzica Jevtic, Univ. Politecnica de Madrid, ETSIT Cuidad Univ. (Spain)
Octavio Nieto-Taladriz, Univ. Politecnica de Madrid, ETSIT Cuidad Univ. (Spain)


Published in SPIE Proceedings Vol. 5837:
VLSI Circuits and Systems II
Jose Fco. Lopez; Francisco V. Fernandez; Jose Maria Lopez-Villegas; Jose M. de la Rosa, Editor(s)

© SPIE. Terms of Use
Back to Top