Traversal Caches : A Framework for FPGA Acceleration of Pointer Data Structures
Joint Authors
Source
International Journal of Reconfigurable Computing
Issue
Vol. 2010, Issue 2010 (31 Dec. 2010), pp.1-16, 16 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-03-07
Country of Publication
Egypt
No. of Pages
16
Main Subjects
Information Technology and Computer Science
Abstract EN
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, we 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.
The paper presents a generalized framework that benefits applications with repeated traversals, which we show can achieve between 7x and 29x speedup over pointer-based software.
For applications without strictly repeated traversals, we present application-specialized extensions that benefit applications with highly similar traversals by exploiting similarity to improve memory bandwidth and execute multiple traversals in parallel.
We show that these extensions can achieve a speedup between 11x and 70x on a Virtex4 LX100 for Barnes-Hut n-body simulation.
American Psychological Association (APA)
Coole, James& Stitt, Greg. 2011. Traversal Caches : A Framework for FPGA Acceleration of Pointer Data Structures. International Journal of Reconfigurable Computing،Vol. 2010, no. 2010, pp.1-16.
https://search.emarefa.net/detail/BIM-488451
Modern Language Association (MLA)
Coole, James& Stitt, Greg. Traversal Caches : A Framework for FPGA Acceleration of Pointer Data Structures. International Journal of Reconfigurable Computing No. 2010 (2010), pp.1-16.
https://search.emarefa.net/detail/BIM-488451
American Medical Association (AMA)
Coole, James& Stitt, Greg. Traversal Caches : A Framework for FPGA Acceleration of Pointer Data Structures. International Journal of Reconfigurable Computing. 2011. Vol. 2010, no. 2010, pp.1-16.
https://search.emarefa.net/detail/BIM-488451
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-488451