Towards automatic program partitioning

ABSTRACT

There is a trend towards using accelerators to increase performance and energy efficiency of general-purpose processors. Adoption of accelerators, however, depends on the availability of tools to facilitate programming these devices.

In this paper, we present techniques for automatically partitioning programs for execution on accelerators. We call the off-loaded code regions sub-algorithms, which are parts of the program that are loosely connected to the remainder of the program. We present three heuristics for automatically identifying sub-algorithms based on control flow and data flow properties. Analysis of SPECint and MiBench benchmarks shows that

on average 12 sub-algorithms are identified (up to 54), covering the full execution time for 27 out of 30 benchmarks. We show that these sub-algorithms are suitable for off-loading them to accelerators by manually implementing sub-algorithms for 2 SPECint benchmarks on the Cell processor.

REFERENCES

• 1: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.
• 2: R. H. Bell. Automatic workload synthesis for early design studies and performance model validation. lib.utexas.edu, page 169, 2005.
• 3: Pieter Bellens , Josep M. Perez , Rosa M. Badia , Jesus Labarta, CellSs: a programming model for the cell BE architecture, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188546]
• 4: A. Cantle and R. Bruce. An Introduction to the Nallatech Slipstream FSB-FPGA Accelerator Module for Intel Platforms. White paper, http://www.nallatech.com, Sept. 2007.
• 5: Marc Eaddy , Alfred V. Aho , Giuliano Antoniol , Yann-Gaël Guéhéneuc, CERBERUS: Tracing Requirements to Source Code Using Information Retrieval, Dynamic Analysis, and Program Analysis, Proceedings of the 2008 The 16th IEEE International Conference on Program Comprehension, p.53-62, June 10-13, 2008 [doi>10.1109/ICPC.2008.39]
• 6: Alexandre E. Eichenberger , Kathryn O'Brien , Kevin O'Brien , Peng Wu , Tong Chen , Peter H. Oden , Daniel A. Prener , Janice C. Shepherd , Byoungro So , Zehra Sura , Amy Wang , Tao Zhang , Peng Zhao , Michael Gschwind, Optimizing Compiler for the CELL Processor, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.161-172, September 17-21, 2005 [doi>10.1109/PACT.2005.33]
• 7: Andrew David Eisenberg , Kris De Volder, Dynamic Feature Traces: Finding Features in Unfamiliar Code, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.337-346, September 25-30, 2005 [doi>10.1109/ICSM.2005.42]
• 8: P. Elias, A. Feinstein, and C. Shannon. A note on the maximum flow through a network. Information Theory, IEEE Transactions on, 2(4):117--119, 1956.
• 9: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 10: Gabriel Falcão , Leonel Sousa , Vitor Silva, Massive parallel LDPC decoding on GPU, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345221]
• 11: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 12: T. R. Halfhill. Floating point buoys ClearSpeed. Microprocessor Report, page 7, Nov. 2003.
• 13: IBM. Performance Analysis with the IBM Full-System Simulator. Documentation, http://www.ibm.com/developerworks/power/cell/, Sept. 2007.
• 14: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
• 15: John H. Kelm , Isaac Gelado , Mark J. Murphy , Nacho Navarro , Steve Lumetta , Wen-mei Hwu, CIGAR: Application Partitioning for a CPU/Coprocessor Architecture, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.317-326, September 15-19, 2007 [doi>10.1109/PACT.2007.21]
• 16: Adrian Lienhard , Orla Greevy , Oscar Nierstrasz, Tracking Objects to Detect Feature Dependencies, Proceedings of the 15th IEEE International Conference on Program Comprehension, p.59-68, June 26-29, 2007 [doi>10.1109/ICPC.2007.38]
• 17: D. J. Lilja. Measuring Computer Performance. Cambridge University Press, 2000.
• 18: Erik Lindholm , John Nickolls , Stuart Oberman , John Montrym, NVIDIA Tesla: A Unified Graphics and Computing Architecture, IEEE Micro, v.28 n.2, p.39-55, March 2008 [doi>10.1109/MM.2008.31]
• 19: Tim Mattson, Introduction to OpenMP, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188673]
• 20: D. Pham, S. Asano, M. Bolliger, M. N. Day, H. P. Hofstee, C. Johns, J. Kahle, A. Kameyama, J. Keaty, Y. Masubuchi, M. Riley, D. Shippy, D. Stasiak, M. Suzuoki, M. Wang, J. Warnock, S. Weitzel, D. Wendel, T. Yamazaki, and K. Yazawa. The design and implementation of a first-generation Cell processor. In ISSCC 2005, IEEE International Solid-State Circuits Conference, pages 184--592, 2005.
• 21: S. Rul, H. Vandierendonck, and K. De Bosschere. Detecting the existence of coarse-grain parallelism in general-purpose programs. In Proceedings of the First Workshop on Programmability Issues for Multi-Core Computers, MULTIPROG-1, page 12, 1 2008.
• 22: Scott Schneider , Jae-Seung Yeom , Benjamin Rose , John C. Linford , Adrian Sandu , Dimitrios S. Nikolopoulos, A comparison of programming models for multiprocessors with explicitly managed memory hierarchies, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 23: Robert C. seacord , Daniel Plakosh , Grace A. Lewis, Modernizing Legacy Systems: Software Technologies, Engineering Process and Business Practices, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 24: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: 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
• 26: H. Vandierendonck, S. Rul, M. Questier, and K. De Bosschere. Experiences with parallelizing a bio-informatics program on the Cell BE. In HiPEAC 2008, volume 4917, pages 161--175. Springer, 1 2008.
• 27: Oreste Villa , Daniele Paolo Scarpazza , Fabrizio Petrini, Accelerating Real-Time String Searching with Multicore Processors, Computer, v.41 n.4, p.42-50, April 2008 [doi>10.1109/MC.2008.105]
• 28: Dong Hyuk Woo , Hsien-Hsin S. Lee , Joshua B. Fryman , Allan D. Knies , Marsha Eng, POD: A 3D-Integrated Broad-Purpose Acceleration Layer, IEEE Micro, v.28 n.4, p.28-40, July 2008 [doi>10.1109/MM.2008.58]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Design, Performance

Keywords:
accelerators, off-loading, partitioning, sub-algorithms