Dynamic FPGA routing for just-in-time FPGA compilation

ABSTRACT

Just-in-time (JIT) compilation has previously been used in many applications to enable standard software binaries to execute on different underlying processor architectures. However, embedded systems increasingly incorporate Field Programmable Gate Arrays (FPGAs), for which the concept of a standard hardware binary did not previously exist, requiring designers to implement a hardware circuit for a single specific FPGA. We introduce the concept of a standard hardware binary, using a just-in-time compiler to compile the hardware binary to an FPGA. A JIT compiler for FPGAs requires the development of lean versions of technology mapping, placement, and routing algorithms, of which routing is the most computationally and memory expensive step. We present the Riverside On-Chip Router (ROCR) designed to efficiently route a hardware circuit for a simple configurable logic fabric that we have developed. Through experiments with MCNC benchmark hardware circuits, we show that ROCR works well for JIT FPGA compilation, producing good hardware circuits using an order of magnitude less memory resources and execution time compared with the well known Versatile Place and Route (VPR) tool suite. ROCR produces good hardware circuits using 13X less memory and executing 10X faster than VPR's fastest routing algorithm. Furthermore, our results show ROCR requires only 10% additional routing resources, and results in circuit speeds only 32% slower than VPR's timing-driven router, and speeds that are actually 10% faster than VPR's routability-driven router.

REFERENCES

• 1: Altera Corp. http://www.altera.com, 2003.
• 2: 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]
• 3: Atmel Corp. http://www.atmel.com, 2003.
• 4: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 5: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 6: 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
• 7: Betz, V., J. Rose, A. Marquardt. VPR and T-VPack: Versatile Packing, Placement and Routing for FPGAs. http:// www.eecg.toronto.edu/~vaughn/vpr/vpr.html, 2003.
• 8: 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]
• 9: Cypress Semiconductor. http://www.cypress.com, 2004.
• 10: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 11: Gschwind, M., E. Altman, S. Sathaye, P. Ledak, D. Appenzeller. Dynamic and Transparent Binary Translation. IEEE Computer, Vol. 3, pp.70--77, 2000.
• 12: Klaiber, A. The Technology Behind Crusoe Processors. Transmeta Corporation White Paper, 2000.
• 13: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 14: Lee, C. Y. An Algorithm for Path Connection and its Applications. IRE Transaction on Electronic Computing, Vol. EC=10, pp. 346--365, 1961.
• 15: 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
• 16: Roman Lysecky , Frank Vahid, A codesigned on-chip logic minimizer, 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.944677]
• 17: 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]
• 18: 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]
• 19: Singh, S., J. Rose, P. Chow, D. Lewis. The Effect of Logic Block Architecture on FPGA Performance. IEEE Journal of Solid-State Circuits, Vol. 27, No. 3, 1992.
• 20: 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]
• 21: 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]
• 22: Transmeta Corporation. http://www.transmeta.com, 2004.
• 23: Xilinx, Inc. http://www.xilinx.com, 2004.
• 24: Yang, S. Logic Synthesis and Optimization Benchmarks, Version 3.0. Technical Report, Microelectronics Center of North Carolina, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, codesign, configurable logic, dynamic optimization, hardware/software partitioning, just-in-time compilation, place and route, platforms, system-on-a-chip, warp processors