Dynamic parallelization and mapping of binary executables on hierarchical platforms

ABSTRACT

As performance improvements are being increasingly sought via coarse-grained parallelism, established expectations of continued sequential performance increases are not being met. Current trends in computing point towards platforms seeking performance improvements through various degrees of parallelism, with coarse-grained parallelism features becoming commonplace in even entry-level systems.Yet the broad variety of multiprocessor configurations that will be available that differ in the number of processing elements will make it difficult to statically create a single parallel version of a program that performs well on the whole range of such hardware. As a result, there will soon be a vast number of multiprocessor systems that are significantly under-utilized for lack of software that harnesses their power effectively. This problem is exacerbated by the growing inventory of legacy programs in binary executable form with possibly unreachable source code.We present a system that improves the performance of optimized sequential binaries through dynamic recompilation. Leveraging observations made at runtime, a thin software layer recompiles executing code compiled for a uniprocessor and generates parallelized and/or vectorized code segments that exploit available parallel resources. Among the techniques employed are control speculation, loop distribution across several threads, and automatic parallelization of recursive routines.Our solution is entirely software-based and can be ported to existing hardware platforms that have parallel processing capabilities. Our performance results are obtained on real hardware without using simulation.In preliminary benchmarks on only modestly parallel (2-way) hardware, our system already provides speedups of upto 40% on SpecCPU benchmarks, and near-optimal speedups on more obviously parallelizable benchmarks.

REFERENCES

• 1: 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
• 2: Leonid Baraz , Tevi Devor , Orna Etzion , Shalom Goldenberg , Alex Skaletsky , Yun Wang , Yigel Zemach, IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium®-based systems, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.191, December 03-05, 2003
• 3: Bryan Buck , Jeffrey K. Hollingsworth, An API for Runtime Code Patching, International Journal of High Performance Computing Applications, v.14 n.4, p.317-329, November 2000 [doi>10.1177/109434200001400404]
• 4: Marcelo Cintra , Diego R. Llanos, Toward efficient and robust software speculative parallelization on multiprocessors, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 5: M. de Alba and D. Kaeli. Runtime predictability of loops, 2001.
• 6: Kemal Ebcioğlu , Erik R. Altman, DAISY: dynamic compilation for 100% architectural compatibility, Proceedings of the 24th annual international symposium on Computer architecture, p.26-37, June 01-04, 1997, Denver, Colorado, United States
• 7: An Eight Issue Tree-VLIW Processor for Dynamic Binary Translation, Proceedings of the International Conference on Computer Design, p.488, October 05-05, 1998
• 8: J. A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 30(7):478--490, July 1981.
• 9: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 10: Lance Hammond , Kunle Olukotun, Considerations in the Design of Hydra: A Multiprocessor-on-a-Chip Microarchitecture, Stanford University, Stanford, CA, 1998
• 11: Peter Hofstee , Michael Day, Hardware and software architectures for the CELL processor, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, p.1-1, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084837]
• 12: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 13: Thomas Peter Kistler , Michael Franz, Continuous program optimization, 1999
• 14: A. Klaiber. The technology behind Crusoetexttrademark processors. Transmeta Technical Brief, Jan. 2000.
• 15: Manohar K. Prabhu , Kunle Olukotun, Using thread-level speculation to simplify manual parallelization, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 16: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.218-232, June 18-21, 1995, La Jolla, California, United States
• 17: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 18: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, 25 years of the international symposia on Computer architecture (selected papers), p.521-532, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.286010]
• 19: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989446]
• 20: Jenn-Yaun Tsai , Jian Huang , Christoffer Amlo , David J. Lilja , Pen-Chung Yew, The Superthreaded Processor Architecture, IEEE Transactions on Computers, v.48 n.9, p.881-902, September 1999 [doi>10.1109/12.795219]
• 21: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, ACM SIGPLAN Notices, v.36 n.7, p.93-102, July 2001
• 22: E. Yardimci, C. Fensch, N. Dalton, and M. Franz. Azure: A virtual machine for improving execution of sequential programs on throughput-oriented explicitly parallel processors. In 11th International Workshop on Compilers for Parallel Computers, July 2004.
• 23: Craig B. Zilles , Gurindar S. Sohi, A Programmable Co-processor for Profiling, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.241, January 20-24, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
continuous optimization, dynamic parallelization