Data Search and Reorganization using FPGAs: Application to Spatial Pointer-based Data Structures

Pedro Diniz and Joonseok Park
University of Southern California / Information Sciences Institute
4676 Admiralty Way, Suite 1001
Marina del Rey, California 90292
{pedro,joonseok}@isi.edu

Abstract

FPGAs have appealing features such as customizable internal and external bandwidth and the ability to exploit vast amounts of fine-grain instruction-level parallelism. In this paper we explore the applicability of these features in using FPGAs as smart memory engines for performing search and reorganization computations over spatial pointer-based data structures for which traditional computing platforms perform poorly. This experience suggests that reconfigurable logic when combined with data reorganization can lead to dramatic performance improvements of up to 20x for a wide range of data input sets sizes over traditional computer architectures for pointer-based computations, traditionally not viewed as a good match for reconfigurable technologies.

Keywords:

Custom Computing; Data search and Data Reorganization Engines; Hardware support for Pointer Operations; Field-Programmable-Gate-Arrays (FPGAs).

PDF Document