Thread warping: a framework for dynamic synthesis of thread accelerators

ABSTRACT

We present a dynamic optimization technique, thread warping, that uses a single processor on a multiprocessor system to dynamically synthesize threads into custom accelerator circuits on FPGAs (field-programmable gate arrays). Building on dynamic synthesis for single-processor single-thread systems, known as warp processing, thread warping improves performances of multiprocessor systems by speeding up individual threads and by allowing more threads to execute concurrently. Furthermore, thread warping maintains the important separation of function from architecture, enabling portability of applications to architectures with different quantities of microprocessors and FPGA.an advantage not shared by static compilation/synthesis approaches. We introduce a framework of architecture, CAD tools, and operating system that together support thread warping. We summarize experiments on an extensive architectural simulation framework we developed, showing application speedups of 4x to 502x, averaging 130x compared to a multiprocessor system having four ARM11 microprocessors, for eight benchmark applications. Even compared to a 64-processor system, thread warping achieves 11x speedup.

REFERENCES

• 1: R. Amerson , R. Carter , W. Culbertson , P. Kuekes , G. Snider , Lyle Albertson, Plasma: an FPGA for million gate systems, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.10-16, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228372]
• 2: David Andrews , Douglas Niehaus , Peter Ashenden, Programming Models for Hybrid CPU/FPGA Chips, Computer, v.37 n.1, p.118-120, January 2004 [doi>10.1109/MC.2004.1260732]
• 3: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 4: Cifuentes, C. Reverse Compilation Techniques. PhD Thesis, Queensland University of Technology, 1994.
• 5: Cray XD1. http://www.cray.com/products/xd1, 2005.
• 6: Dellson, A., Sandberg, G., and Möhl, S. Turning FPGAs into Supercomputers. Cray User Group, 2006.
• 7: Eles, P., Peng, Z., Kuchchinski, K., and Doboli, A. System level hardware/software partitioning based on simulated annealing and tabu search. Journal on Design Automation for Embedded Systems (DAES), Springer, 2, 1 (1997), 5--32.
• 8: Alessandro Fin , Franco Fummi , Maurizio Martignano , Mirko Signoretto, SystemC: a homogenous environment to test embedded systems, Proceedings of the ninth international symposium on Hardware/software codesign, p.17-22, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371657]
• 9: Eike Grimpe , Frank Oppenheimer, Extending the SystemC synthesis subset by object-oriented features, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944652]
• 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: Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, SPARK: A High-Lev l Synthesis Framework For Applying Parallelizing Compiler Transformations, Proceedings of the 16th International Conference on VLSI Design, p.461, January 04-08, 2003
• 12: Mark D. Hill , James R. Larus , Alvin R. Lebeck , Madhusudhan Talluri , David A. Wood, Wisconsin Architectural Research Tool Set, ACM SIGARCH Computer Architecture News, v.21 n.4, p.8-10, Sept. 1993 [doi>10.1145/165496.165500]
• 13: IBM. The Cell Architecture. http://domino.research.ibm.com, 2006.
• 14: Schleupen, K., Lekuch, S., Mannion, R., Guo, Z., Najjar, W., and Vahid, F. Dynamic partial FPGA reconfiguration in a prototype microprocessor system. In Proceedings of Int. Conf. on Field Programmable Logic And Applications, 2007.
• 15: Intel Quad-Core Xeon. http://www.intel.com, 2007.
• 16: Hyunuk Jung , Soonhoi Ha, Hardware synthesis from coarse-grained dataflow specification for fast HW/SW cosynthesis, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016730]
• 17: Dirk Koch , Christian Haubelt , Jürgen Teich, Efficient hardware checkpointing: concepts, overhead analysis, and implementation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216950]
• 18: M. LaPedus. Intel Tips Teraflops Programmable Processor. EE Times, September 2006.
• 19: Lu, J., Chen, H., Yew, P., and Hsu, W. Design and implementation of a lightweight dynamic optimization system. Journal of Instruction-Level Parallelism, 6 (Jun 2004), 1--24.
• 20: Ludwig, S. Fast Hardware Synthesis Tools and a Reconfigurable Coprocessor. Ph.D. Thesis, ETH Zurich, 2005.
• 21: Roman Lysecky , Greg Stitt , Frank Vahid, Warp Processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.659-681, July 2006
• 22: Roman Lysecky , Frank Vahid , Sheldon X. -D. Tan, A Study of the Scalability of On-Chip Routing for Just-in-Time FPGA Compilation, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.57-62, April 18-20, 2005 [doi>10.1109/FCCM.2005.12]
• 23: Gaurav Mittal , David C. Zaretsky , Xiaoyong Tang , P. Banerjee, Automatic translation of software binaries onto FPGAs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996678]
• 24: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 25: Daler N. Rakhmatov , Sarma B. K. Vrudhula, Hardware-software bipartitioning for dynamically reconfigurable systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774819]
• 26: SGI Altix. http://www.sgi.com/products/servers/altix/
• 27: G. Stiff , F. Vahid, New decompilation techniques for binary-level co-processor generation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.547-554, November 06-10, 2005, San Jose, CA
• 28: VxWorks RTOS. http://www.windriver.com/vxworks/, 2007.
• 29: Xilinx Virtex II Pro, http://www.xilinx.com, 2006.
• 30: Xilinx Virtex IV, http://www.xilinx.com, 2006.
• 31: Weifeng Zhang , Brad Calder , Dean M. Tullsen, An Event-Driven Multithreaded Dynamic Optimization Framework, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.87-98, September 17-21, 2005 [doi>10.1109/PACT.2005.7]

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:
FPGA, dynamic synthesis, just-in-time compilation, multi-core, synthesis, thread warping, threads, warp processing