Synthesis of reconfigurable high-performance multicore systems

ABSTRACT

Reconfigurable high-performance computing systems (RHPC) have been attracting more and more attention over the past few years. RHPC systems are a promising solution for accelerating system performance, lowering power consumption and minimizing operation cost. In order to achieve high performance on this hybrid system, it is important to effectively explore the design space, which includes accelerator synthesis, resource allocation and job scheduling. In this paper we propose novel algorithms for reconfigurable resource allocation and job scheduling to optimize performance of multicore RHPC systems. Specifically, we first propose an interesting approximation algorithm to assign jobs to processors with consideration of coprocessors at the global optimization step. Then we present an optimal solution for coprocessor selection in the local optimization step. In this paper we also demonstrate that designers can quickly explore a large number of accelerator design choices with the help of high-level synthesis tools. Experiments show that our proposed techniques provide efficient solutions for real-life benchmarks and generate higher quality of results. When compared to other heuristic algorithms, our results can achieve up to 47% performance improvement.

REFERENCES

• 1: S.G. Abraham, B.R. Rau and R. Schreiber, "Fast Design Space Exploration Through Validity and Quality Filtering of Subsystem Designs", HP Labs Technical Reports, HPL-2000-98.
• 2: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 3: Samit Chaudhuri , Stephen A. Blythe , Robert A. Walker, A solution methodology for exact design space exploration in a three-dimensional design space, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.69-81, March 1997 [doi>10.1109/92.555988]
• 4: 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]
• 5: Jason Cong , Karthik Gururaj , Guoling Han , Adam Kaplan , Mishali Naik , Glenn Reinman, MC-Sim: an efficient simulation tool for MPSoC designs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
• 6: Jason Cong , Yi Zou, Lithographic aerial image simulation with FPGA-based hardwareacceleration, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344683]
• 7: P. Dubey, "Recognition, Mining and Synthesis Moves Computers to the Era of Tera," Technology@Intel Magazine, Feb. 2005.
• 8: M. R. Garey , D. S. Johnson, `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM (JACM), v.25 n.3, p.499-508, July 1978 [doi>10.1145/322077.322090]
• 9: Seth Copen Goldstein , Herman Schmit , Mihai Budiu , Srihari Cadambi , Matt Moe , R. Reed Taylor, PipeRench: A Reconfigurable Architecture and Compiler, Computer, v.33 n.4, p.70-77, April 2000 [doi>10.1109/2.839324]
• 10: 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
• 11: R.L. Graham, "Bounds for Certain Multiprocessing Anomalies," Bell System Tech. J. 45, pp. 1563--1581, 1966.
• 12: S. Hauk, A. Dehon, Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation, Morgan Kaufmann, 2007.
• 13: Klaus Jansen , Monaldo Mastrolilli, Approximation schemes for parallel machine scheduling problems with controllable processing times, Computers and Operations Research, v.31 n.10, p.1565-1581, September 2004 [doi>10.1016/S0305-0548(03)00101-1]
• 14: Vinod Kathail , Shail Aditya , Robert Schreiber , B. Ramakrishna Rau , Darren C. Cronquist , Mukund Sivaraman, PICO: Automatically Designing Custom Computers, Computer, v.35 n.9, p.39-47, September 2002 [doi>10.1109/MC.2002.1033026]
• 15: M. Gokhale and Paul S. Graham, Reconfigurable Computing: Accelerating Computation with Field-Programmable Gate Arrays, Springer, 2005.
• 16: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 17: Maurizio Palesi , Tony Givargis, Multi-objective design space exploration using genetic algorithms, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774804]
• 18: Andrew R. Putnam , Dave Bennett , Eric Dellinger , Jeff Mason , Prasanna Sundararajan, CHiMPS: a high-level compilation flow for hybrid CPU-FPGA architectures, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344720]
• 19: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 20: Byoungro So , Pedro C. Diniz , Mary W. Hall, Using estimates from behavioral synthesis tools in compiler-directed design space exploration, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775963]
• 21: Byoungro So , Mary W. Hall , Pedro C. Diniz, A compiler approach to fast hardware design space exploration in FPGA-based systems, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 22: R. Vickson, "Two Single Machine Sequencing Problems Involving Controllable Job Processing Times," AIIE Transactions, vol. 12, pp. 258--262, 1980.
• 23: Gang Wang , Wenrui Gong , Brian DeRenzi , Ryan Kastner, Design space exploration using time and resource duality with the ant colony optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147028]
• 24: AutoPilot, http://www.autoesl.com
• 25: Altera Corp., http://www.altera.com.
• 26: Cray Inc., http://www.cray.com
• 27: Catapult, http:://www.mentor.com
• 28: Impulse C, http://www.impulsec.com
• 29: Finance Numerical Recipes, http://finance.bi.no/~bernt/gcc_prog/recipes/recipes/
• 30: LPsolve, http://www.cs.sunysb.edu/~algorith/implement/ lpsolve/implement.shtml
• 31: Xilinx Inc., http://www.xilinx.com.
• 32: SESC simulator, http://sesc.sourceforge.net
• 33: SGI, http://www.sgi.com
• 34: SRC Inc., http://www.srccomp.com
• 35: XtremeData, Inc., http://www.xtremedata.com

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications

General Terms:
Algorithms

Keywords:
coprocessor synthesis, design space exploration, reconfigurable high-performance computing