Dynamic coprocessor management for FPGA-enhanced compute platforms

ABSTRACT

Various commercial programmable compute platforms have their processor architecture enhanced with field-programmable gate arrays (FPGAs). In a common usage scenario, an application loads custom processors into the FPGA to speed up application execution compared to processor-only execution. Transient applications, changing application workloads, and limited FPGA capacity have led to a new problem of operating-system-controlled dynamic management of the loading of coprocessors into the FPGAs for best overall performance or energy. We define the Dynamic Coprocessor Management problem and provide a mapping to an online optimization problem known as Metrical Task Systems. We introduce a robust heuristic, called the fading cumulative benefit (FCBenefit) heuristic, that outperforms other heuristics, including a previously developed one for MTS. For two distinct application sets, we generate numerous workloads and show that the FCBenefit heuristic provides best results across all considered workloads. In our simulations, the heuristic's results were within 9% of the offline optimal for performance, and within 3% for energy. The heuristic may be applicable to a wide variety of dynamic architecture management problems.

REFERENCES

• 1: Altera Excalibur FPGAs, http://www.altera.com.
• 2: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• 3: Felice Balarin , Luciano Lavagno , Praveen Murthy , Alberto Sangiovanni-vincentelli, Scheduling for Embedded Real-Time Systems, IEEE Design & Test, v.15 n.1, p.71-82, January 1998 [doi>10.1109/54.655185]
• 4: Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258667]
• 5: Domingo Benitez, Performance of Remote FPGA-Based Coprocessors for Image-Processing Applications, Proceedings of the Euromicro Symposium on Digital Systems Design, p.268, September 04-06, 2002
• 6: Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000 [doi>10.1023/A:1007621832648]
• 7: Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
• 8: Celoxica, http://www.celoxica.com.
• 9: Katherine Compton , Zhiyuan Li , James Cooley , Stephen Knol , Scott Hauck, Configuration relocation and defragmentation for run-time reconfigurable computing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.209-220, June 2002 [doi>10.1109/TVLSI.2002.1043324]
• 10: DRC Coprocessors for AMD Opteron Platforms, www.drccomputer.com, 2008.
• 11: Jan Frigo , Maya Gokhale , Dominique Lavenier, Evaluation of the streams-C C-to-FPGA compiler: an applications perspective, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.134-140, February 2001, Monterey, California, United States [doi>10.1145/360276.360326]
• 12: Hiroshi Fujiwara , Kazuo Iwama, Average-Case Competitive Analyses for Ski-Rental Problems, Proceedings of the 13th International Symposium on Algorithms and Computation, p.476-488, November 21-23, 2002
• 13: Scott Hauck , Thomas W. Fry , Matthew M. Hosler , Jeffrey P. Kao, The chimaera reconfigurable functional unit, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.2, p.206-217, February 2004 [doi>10.1109/TVLSI.2003.821545]
• 14: Scott Hauck, Configuration prefetch for single context reconfigurable coprocessors, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.65-74, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275121]
• 15: 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
• 16: Edson L. Horta , John W. Lockwood , David E. Taylor , David Parlour, Dynamic hardware plugins in an FPGA with partial run-time reconfiguration, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514007]
• 17: Intel QuickAssist Technology, http://www.intel.com/technology/platforms/quickassist/, 2008.
• 18: D. Isaacs, E. Trexel and B. Karsten. Accelerate System Performance with hybrid multiprocessing and FPGAs. Embedded Systems Design, 8/15/2007.
• 19: Yung-Hsiang Lu , Luca Benini , Giovanni De Micheli, Low-power task scheduling for multiple devices, Proceedings of the eighth international workshop on Hardware/software codesign, p.39-43, May 2000, San Diego, California, United States [doi>10.1145/334012.334020]
• 20: Mitrionics, http://www.mitrionics.com.
• 21: Juanjo Noguera , Rosa M. Badia, Dynamic run-time HW/SW scheduling techniques for reconfigurable architectures, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774831]
• 22: SGI Altix, http://www.sgi.com/products/servers/altix/.
• 23: Greg Stitt , Frank Vahid, Energy Advantages of Microprocessor Platforms with On-Chip Configurable Logic, IEEE Design & Test, v.19 n.6, p.36-43, November 2002 [doi>10.1109/MDT.2002.1047742]
• 24: Frank Vahid , Greg Stitt , Roman Lysecky, Warp Processing: Dynamic Translation of Binaries to FPGA Circuits, Computer, v.41 n.7, p.40-46, July 2008 [doi>10.1109/MC.2008.240]
• 25: Xilinx Virtex-4 FPGAs, http://www.xilinx.com.

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.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

General Terms:
Algorithms, Design, Performance

Keywords:
FPGAs, acceleration, coprocessing, dynamic optimization, online algorithms., runtime configuration