Traversal caches: a first step towards FPGA acceleration of pointer-based data structures

ABSTRACT

Field-programmable gate arrays (FPGAs) often achieve order of magnitude speedups compared to microprocessors, but typically have been unable to improve the performance of applications with irregular memory access patterns, such as traversals of pointer-based data structures. Due to the common use of these data structures, the applicability and widespread success of FPGAs has been limited. In this paper, we introduce the traversal cache framework - a first step towards improving the performance of FPGA applications that utilize pointer-based data structures. The traversal cache is a local FPGA memory that stores repeated traversals of pointer-based data structures, allowing for these traversals to be efficiently streamed into the FPGA. Although the cache is generally limited to improving applications that exhibit repeated traversals, we show that many applications in fact have this characteristic. Furthermore, we show that few repetitions are needed to achieve performance improvements. We present experimental results showing that FPGA implementations using the traversal cache framework achieve speedups ranging from 7x to 29x compared to pointer-based software on a 3.2 GHz Xeon.

REFERENCES

• 1: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 2: J. Carter , W. Hsieh , L. Stoller , M. Swanson , L. Zhang , E. Brunvand , A. Davis , C.-C. Kuo , R. Kuramkote , M. Parker , L. Schaelicke , T. Tateyama, Impulse: Building a Smarter Memory Controller, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.70, January 09-12, 1999
• 3: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Making Pointer-Based Data Structures Cache Conscious, Computer, v.33 n.12, p.67-74, December 2000 [doi>10.1109/2.889095]
• 4: Jamison Collins , Suleyman Sair , Brad Calder , Dean M. Tullsen, Pointer cache assisted prefetching, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 5: André DeHon, The Density Advantage of Configurable Computing, Computer, v.33 n.4, p.41-49, April 2000 [doi>10.1109/2.839320]
• 6: Pedro C. Diniz , Joonseok Park, Data Search and Reorganization Using FPGAs: Application to Spatial Pointer-based Data Structures, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.207, April 09-11, 2003
• 7: GiDEL. GiDEL PROC Boards, 2008. http://www.gidel.com/PROCBoards.htm.
• 8: P. Grun , N. Dutt , A. Nicolau, Access pattern based local memory customization for low power embedded systems, Proceedings of the conference on Design, automation and test in Europe, p.778-784, March 2001, Munich, Germany
• 9: Peter Grun , Nikil Dutt , Alex Nicolau, Memory aware compilation through accurate timing extraction, Proceedings of the 37th conference on Design automation, p.316-321, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337428]
• 10: Zhi Guo , Betul Buyukkurt , Walid Najjar, Input data reuse in compiling window operations onto reconfigurable hardware, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 11: Zhi Guo , Walid Najjar , Frank Vahid , Kees Vissers, A quantitative analysis of the speedup factors of FPGAs over processors, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968304]
• 12: Brian Holland , Karthik Nagarajan , Chris Conger , Adam Jacobs , Alan D. George, RAT: a methodology for predicting performance in application design migration to FPGAs, Proceedings of the 1st international workshop on High-performance reconfigurable computing technology and applications: held in conjunction with SC07, November 11-11, 2007, Reno, Nevada [doi>10.1145/1328554.1328560]
• 13: Zhigang Hu , Stefanos Kaxiras , Margaret Martonosi, Timekeeping in the memory system: predicting and optimizing memory behavior, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 14: Jeffrey A. Jacob , Paul Chow, Memory interfacing and instruction specification for reconfigurable processors, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.145-154, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296446]
• 15: Nallatech Inc. DIMEtalk 3, 2008. http://www.nallatech.com/?node_id=1.2.2&id=19.
• 16: Nallatech Inc. Nallatech PCIXM FPGA accelerator card, 2008. http://www.nallatech.com/?node_id=1.2.2&id=41.
• 17: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 18: Luc Séméria , Giovanni De Micheli, SpC: synthesis of pointers in C: application of pointer analysis to the behavioral synthesis from C, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.340-346, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289051]
• 19: Luc Séméria , Koichi Sato , Giovanni De Micheli, Synthesis of hardware models in C with pointers and complex data structures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.743-756, 12/1/2001 [doi>10.1109/92.974889]
• 20: Nitzan Weinberg , David Nagle, Dynamic Elimination of Pointer-Expressions, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.142, October 12-18, 1998
• 21: Xilinx Inc. MicroBlaze, 2008. http://www.xilinx.com/products/design_resources/proc_central/microblaze.htm.
• 22: Xilinx Inc. Virtex IV FX devices, 2008. http://www.xilinx.com/products/silicon_solutions/fpgas/virtex/virtex4/index.htm.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Performance

Keywords:
cad, fpga, hardware/software partitioning, pointers, synthesis, traversal cache