Warp Processors

ABSTRACT

We describe a new processing architecture, known as a warp processor, that utilizes a field-programmable gate array (FPGA) to improve the speed and energy consumption of a software binary executing on a microprocessor. Unlike previous approaches that also improve software using an FPGA but do so using a special compiler, a warp processor achieves these improvements completely transparently and operates from a standard binary. A warp processor dynamically detects the binary's critical regions, reimplements those regions as a custom hardware circuit in the FPGA, and replaces the software region by a call to the new hardware implementation of that region. While not all benchmarks can be improved using warp processing, many can, and the improvements are dramatically better than those achievable by more traditional architecture improvements. The hardest part of warp processing is that of dynamically reimplementing code regions on an FPGA, requiring partitioning, decompilation, synthesis, placement, and routing tools, all having to execute with minimal computation time and data memory so as to coexist on chip with the main processor. We describe the results of developing our warp processor. We developed a custom FPGA fabric specifically designed to enable lean place and route tools, and we developed extremely fast and efficient versions of partitioning, decompilation, synthesis, technology mapping, placement, and routing. Warp processors achieve overall application speedups of 6.3X with energy savings of 66&percent; across a set of embedded benchmark applications. We further show that our tools utilize acceptably small amounts of computation and memory which are far less than traditional tools. Our work illustrates the feasibility and potential of warp processing, and we can foresee the possibility of warp processing becoming a feature in a variety of computing domains, including desktop, server, and embedded applications.

REFERENCES

• 1: Altera Corp. 2006. Customer showcase. http://www.altera.com/corporate/cust_successes/ customer_showcase/view_product/csh-vproduct-nios.jsp.
• 2: Altera Corp. 2005. Excalibur embedded processor solutions. http://www.altera.com/products/ devices/excalibur/exc-index.html.
• 3: Atmel Corp. 2005. FPSLIC (AVR with FPGA), http://www.atmel.com/products/FPSLIC/.
• 4: A. Balboni , W. Fornaciari , D. Sciuto, Partitioning and Exploration Strategies in the TOSCA Co-Design Flow, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.62, March 18-20, 1996
• 5: Banerjee, P., Mittal, G., Zaretsky, D., and Tang, X. 2004. BINACHIP-FPGA: A tool to map DSP software binaries and assembly programs onto FPGAs. In Proceedings of the Embedded Signal Processing Conference (GSPx).
• 6: Berkeley Design Technology, Inc. 2004. http://www.bdti.com/articles/info_eet0207fpga.htm# DSPEnhanced&percent;20FPGAs.
• 7: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 8: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 9: W. Böhm , J. Hammes , B. Draper , M. Chawathe , C. Ross , R. Rinker , W. Najjar, Mapping a Single Assignment Programming Language to Reconfigurable Systems, The Journal of Supercomputing, v.21 n.2, p.117-130, February 2002 [doi>10.1023/A:1013623303037 ]
• 10: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 11: 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]
• 12: Wang Chen , Panos Kosmas , Miriam Leeser , Carey Rappaport, An FPGA implementation of the two-dimensional finite-difference time-domain (FDTD) algorithm, 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.968311]
• 13: Christensen, F. 2004. A scalable software-defined radio development system. Xcell J., Winter.
• 14: Paul Chow , Jonathan Rose , Soon Ong Seo , Kevin Chung , Gerard Páez-Monzón , Immanuel Rahardja, The design of an SRAM-based field-programmable gate array—part I: architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.2, p.191-197, June 1999 [doi>10.1109/92.766746 ]
• 15: Cristina Cifuentes, Structuring Decompiled Graphs, Proceedings of the 6th International Conference on Compiler Construction, p.91-105, April 24-26, 1996
• 16: Cifuentes, C., Simon, D., and Fraboulet, A. 1998. Assembly to high-level language translation. Department of Computer Science and Electrical Engineering, University of Queensland. Tech. Rep. 439.
• 17: Cifuentes, C., Van Emmerik, M., Ung, D., Simon, D., and Waddington, T. 1999. Preliminary experiences with the use of the UQBT binary translation framework. In Proceedings of the Workshop on Binary Translation, 12--22.
• 18: Critical Blue. 2005. http://www.criticalblue.com.
• 19: D.H. Brown Associates. 2004. Cray XD1 brings high-bandwidth supercomputing to the mid-market. White Paper prepared for Cray, Inc., http://www.cray.com/downloads/dhbrown_crayxd1_ oct2004.pdf.
• 20: EEMBC. 2005. The Embedded Microprocessor Benchmark Consortium. http://www.eembc.org.
• 21: Eles, P., Peng, Z., Kuchchinski, K., and Doboli, A. 1997. System level hardware/software partitioning based on simulated annealing and Tabu search. Kluwer's Design Automation for Embedded Systems 2, 1, 5--32.
• 22: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964 ]
• 23: Gajski, D., Vahid, F., Narayan, S., and Gong, J. 1998. SpecSyn: An environment supporting the specify-explore-refine paradigm for hardware/software system design. IEEE Trans. Very Large Scale Integration Syst. (TVLSI) 6, 1, 84--100.
• 24: Maya B. Gokhale , Janice M. Stone, NAPA C: Compiling for a Hybrid RISC/FPGA Architecture, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.126, April 15-17, 1998
• 25: Ann Gordon-Ross , Frank Vahid, Frequent loop detection using efficient non-intrusive on-chip hardware, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951728]
• 26: Zhi Guo , Betul Buyukkurt , Walid Najjar , Kees Vissers, Optimized Generation of Data-Path from C Codes for FPGAs, Proceedings of the conference on Design, Automation and Test in Europe, p.112-117, March 07-11, 2005 [doi>10.1109/DATE.2005.234]
• 27: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 28: Jörg Henkel , Rolf Ernst, A hardware/software partitioner using a dynamically determined granularity, Proceedings of the 34th annual conference on Design automation, p.691-696, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266323]
• 29: John F. Keane , Christopher Bradley , Carl Ebeling, A compiled accelerator for biological cell signaling simulations, 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.968313]
• 30: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 31: Roman Lysecky , Susan Cotterell , Frank Vahid, A fast on-chip profiler memory using a pipelined binary tree, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.120-122, January 2004 [doi>10.1109/TVLSI.2003.820522]
• 32: Roman Lysecky , Frank Vahid, A Configurable Logic Architecture for Dynamic Hardware/Software Partitioning, Proceedings of the conference on Design, automation and test in Europe, p.10480, February 16-20, 2004
• 33: Roman Lysecky , Frank Vahid, On-chip logic minimization, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775918]
• 34: 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 (FCCM'05), p.57-62, April 18-20, 2005 [doi>10.1109/FCCM.2005.12]
• 35: Roman Lysecky , Frank Vahid , Sheldon X.-D. Tan, Dynamic FPGA routing for just-in-time FPGA compilation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996819]
• 36: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 37: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Speed and area tradeoffs in cluster-based FPGA architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.1, p.84-93, Feb. 2000 [doi>10.1109/92.820764 ]
• 38: Matsumoto, C. 2000. Triscend adds 32-bit configurable SoC line. EE Times, http://www. eet.com/story/OEG20000828S0015.
• 39: Gokhan Memik , William H. Mangione-Smith , Wendong Hu, NetBench: a benchmarking suite for network processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 40: 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]
• 41: Morris, K. 2005. Cray goes FPGA. FPGA and Programmable Logic J., April.
• 42: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 43: Singh, S., Rose, J., Chow, P., and Lewis, D. 1992. The effect of logic block architecture on FPGA performance. IEEE J. Solid-State Circuits. 27, 3, 3--12.
• 44: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 45: 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
• 46: Greg Stitt , Frank Vahid, Hardware/software partitioning of software binaries, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.164-170, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774596]
• 47: Greg Stitt , Frank Vahid , Gordon McGregor , Brian Einloth, Hardware/software partitioning of software binaries: a case study of H.264 decode, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, p.285-290, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084905]
• 48: Tensilica, Inc. 2006. XPRES compiler, automatically generate processors from standard C code. http://www.tensilica.com/products/xpres.htm.
• 49: Triscend Corp. 2003. http://www.triscend.com.
• 50: Girish Venkataramani , Walid Najjar , Fadi Kurdahi , Nader Bagherzadeh , Wim Bohm, A compiler framework for mapping applications to a coarse-grained reconfigurable computer architecture, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502235]
• 51: Kees Vissers, Programming models and architectures for FPGA platforms, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, p.1-1, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023834]
• 52: Xilinx, Inc. 2006. http://www.xilinx.com.
• 53: Xilinx, Inc. 2005a. Customer success stories, http://www.xilinx.com/company/success/csprod. htm#embedded.
• 54: Xilinx, Inc. 2005b. Virtex-4 FPGAs, http://www.xilinx.com/products/silicon_solutions/fpgas/ virtex/virtex4/index.htm.
• 55: Xilinx, Inc. 2004a. Partnering for success, Xilinx and photonic bridges. http://www.xilinx.com/ ipcenter/processor_central/embedded/success_PB.pdf.
• 56: Xilinx, Inc. 2004b. Virtex-II Pro/ProX FPGAs, http://www.xilinx.com/products/silicon_solutions/ fpgas/virtex/virtex_ii_pro_fpgas/.
• 57: Xilinx, Inc. 2000a. Xilinx introduces high level language compiler for Virtex FPGAs. Xilinx Press Release. http://www.xilinx.com/prs_rls/00119_forge.htm.
• 58: Xilinx, Inc. 2000b. Xilinx Version 3.3i software doubles clock frequencies. Xilinx Press Release. http://www.xilinx.com/prs_rls/00118_3_3i.htm.
• 59: Marco Zagha , Brond Larson , Steve Turner , Marty Itzkowitz, Performance analysis using the MIPS R10000 performance counters, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369059]
• 60: Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.15-26, October 05-08, 1997, Saint Malo, France
• 61: Craig B. Zilles , Gurindar S. Sohi, A Programmable Co-processor for Profiling, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.241, January 20-24, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

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

General Terms:
Design, Experimentation, Performance

Keywords:
FPGA, Warp processors, configurable logic, dynamic optimization, hardware/software codesign, hardware/software partitioning, just-in-time (JIT) compilation