Two-level microprocessor-accelerator partitioning

ABSTRACT

The integration of microprocessors and field-programmable gate array (FPGA) fabric on a single chip increases both the utility and necessity of tools that automatically move software functions from the microprocessor to accelerators on the FPGA to improve performance or energy. Such hardware/software partitioning for modern FPGAs involves the problem of partitioning functions among two levels of accelerator groups -- tightly-coupled accelerators that have fast single-clock-cycle memory access to the microprocessor's memory, and loosely-coupled accelerators that access memory through a bridge to avoid slowing the main clock period with their longer critical paths. We introduce this new two-level accelerator-partitioning problem, and we describe a novel optimal dynamic programming algorithm to solve the problem. By making use of the size constraint imposed by FPGAs, the algorithm has what is effectively quadratic runtime complexity, running in just a few seconds for examples with up to 25 accelerators, obtaining an average performance improvement of 35% compared to a traditional single-level bus architecture.

REFERENCES

• 1: Chattopadhyay, A. and Z. Zilic. GALDS: A Complete Framework for Designing Multiclock ASICs and SoCs. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, Vol. 13, No. 6, June 2005
• 2: Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002 [doi>10.1145/508352.508353]
• 3: CriticalBlue. http://www.criticalblue.com
• 4: Eles, P., Z. Peng, K. Kuchcinsky, and A. Doboli. System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search. Design Automation for Embedded Systems, vol2, no 1, 5--32 January 1997.
• 5: Excalibur. Altera Corp., http://www.altera.com
• 6: M. D. Galanis , A. Milidonis , G. Theodoridis , D. Soudris , C. E. Goutis, A Partitioning Methodology for Accelerating Applications in Hybrid Reconfigurable Platforms, Proceedings of the conference on Design, Automation and Test in Europe, p.247-252, March 07-11, 2005 [doi>10.1109/DATE.2005.29]
• 7: 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]
• 8: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 9: 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
• 10: Jörg Henkel, A low power hardware/software partitioning approach for core-based embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.122-127, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309896]
• 11: Asawaree Kalavade , P. A. Subrahmanyam, Hardware/software partitioning for multi-function systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.516-521, November 09-13, 1997, San Jose, California, United States
• 12: Ronald Laufer , R. Reed Taylor , Herman Schmit, PCI-PipeRench and the SWORDAPI: A System for Stream-Based Reconfigurable Computing, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.200, April 21-23, 1999
• 13: 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
• 14: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 15: Takashi Miyamori , Kunle Olukotun, A Quantitative Analysis of Reconfigurable Coprocessors for Multimedia Applications, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.2, April 15-17, 1998
• 16: Poseidon Triton System. http://www.poseidon-systems.com
• 17: C. R. Rupp , M. Landguth , T. Garverick , E. Gomersall , H. Holt , J. M. Arnold , M. Gokhale, The NAPA Adaptive Processing Architecture, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.28, April 15-17, 1998
• 18: Greg Stitt , Frank Vahid , Shawn Nematbakhsh, Energy savings and speedups from partitioning critical software loops to hardware in embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.218-232, February 2004 [doi>10.1145/972627.972637]
• 19: Dinesh C. Suresh , Walid A. Najjar , Frank Vahid , Jason R. Villarreal , Greg Stitt, Profiling tools for hardware/software partitioning of embedded applications, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 20: Wildfire Reference Manual, Annapolis, Maryland: Annapolis Microsystems, Inc., 1998
• 21: Peter Yiannacouras , J. Gregory Steffan , Jonathan Rose, Application-specific customization of soft processor microarchitecture, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117231]