Data Centers

Traversal Caches: A Framework for FPGA Acceleration of Pointer Data Structures

Date Added: Dec 2010
Format: PDF

Field-Programmable Gate Arrays (FPGAs) and other Reconfigurable Computing (RC) devices have been widely shown to have numerous advantages including order of magnitude performance and power improvements compared to microprocessors for some applications. Unfortunately, FPGA usage has largely been limited to applications exhibiting sequential memory access patterns, thereby prohibiting acceleration of important applications with irregular patterns (e.g., pointer-based data structures). In this paper, the authors present a design pattern for RC application development that serializes irregular data structure traversals online into a traversal cache, which allows the corresponding data to be efficiently streamed to the FPGA.