Mostly static program partitioning of binary executables

ABSTRACT

We have built a runtime compilation system that takes unmodified sequential binaries and improves their performance on off-the-shelf multiprocessors using dynamic vectorization and loop-level parallelization techniques. Our system, Azure, is purely software based and requires no specific hardware support for speculative thread execution, yet it is able to break even in most cases; that is, the achieved speedup exceeds the cost of runtime monitoring and compilation, often by significant amounts.

Key to this remarkable performance is an offline preprocessing step that extracts a mostly correct control flow graph (CFG) from the binary program ahead of time. This statically obtained CFG is incomplete in that it may be missing some edges corresponding to computed branches. We describe how such additional control flow edges are discovered and handled at runtime, so that an incomplete static analysis never leads to an incorrect optimization result.

The availability of a mostly correct CFG enables us to statically partition a binary executable into single-entry multiple-exit regions and to identify potential parallelization candidates ahead of execution. Program regions that are not candidates for parallelization can thereby be excluded completely from runtime monitoring and dynamic recompilation. Azure's extremely low overhead is a direct consequence of this design.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: 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
• 3: Balakrishnan, G. and Reps, T. 2004. Analyzing memory accesses in x86 executables. In Proceedings of the Conference on Compiler Construction. Lecture Notes in Computer Science, vol. 2985, Springer Verlag, 5--23.
• 4: 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
• 5: 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]
• 6: Gregory T. Byrd , Mark A. Holliday, Multithreaded processor architectures, IEEE Spectrum, v.32 n.8, p.38-46, Aug. 1995 [doi>10.1109/6.402166]
• 7: Martin C. Carlisle , Anne Rogers , John H. Reppy , Laurie J. Hendren, Early Experiences with Olden, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.1-20, August 12-14, 1993
• 8: Craig Chambers, Staged compilation, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, January 14-15, 2002, Portland, Oregon
• 9: Anton Chernoff , Mark Herdeg , Ray Hookway , Chris Reeve , Norman Rubin , Tony Tye , S. Bharadwaj Yadavalli , John Yates, FX!32: A Profile-Directed Binary Translator, IEEE Micro, v.18 n.2, p.56-64, March 1998 [doi>10.1109/40.671403]
• 10: Cristina Cifuentes , K. John Gough, Decompilation of binary programs, Software—Practice & Experience, v.25 n.7, p.811-829, July 1995 [doi>10.1002/spe.4380250706]
• 11: 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
• 12: M. R. de Alba , D. R. Kaeli, Runtime predictability of loops, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.91-98, December 02-02, 2001 [doi>10.1109/WWC.2001.20]
• 13: 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
• 14: An Eight Issue Tree-VLIW Processor for Dynamic Binary Translation, Proceedings of the International Conference on Computer Design, p.488, October 05-05, 1998
• 15: J. A. Fisher, Trace Scheduling: A Technique for Global Microcode Compaction, IEEE Transactions on Computers, v.30 n.7, p.478-490, July 1981 [doi>10.1109/TC.1981.1675827]
• 16: 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
• 17: Lance Hammond , Benedict A. Hubbert , Michael Siu , Manohar K. Prabhu , Michael Chen , Kunle Olukotun, The Stanford Hydra CMP, IEEE Micro, v.20 n.2, p.71-84, March 2000 [doi>10.1109/40.848474]
• 18: 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]
• 19: Kagan, M., Gochman, S., Orenstien, D., and Lin, D. 1997. MMX micro-architecture of Pentium processors with MMX technology and Pentium II micro-processors. Intel Techn. J. 8.
• 20: Thomas Kistler , Michael Franz, Continuous Program Optimization: Design and Evaluation, IEEE Transactions on Computers, v.50 n.6, p.549-566, June 2001 [doi>10.1109/12.931893]
• 21: Thomas Kistler , Michael Franz, Continuous program optimization: A case study, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.500-548, July 2003 [doi>10.1145/778559.778562]
• 22: Klaiber, A. 2000. The technology behind Crusoe processors. White Paper, Transmeta Corp.
• 23: Venkata Krishnan , Josep Torrellas, Hardware and software support for speculative execution of sequential binaries on a chip-multiprocessor, Proceedings of the 12th international conference on Supercomputing, p.85-92, July 1998, Melbourne, Australia [doi>10.1145/277830.277852]
• 24: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 25: Krishnan, V. S. 1998. Speculative multithreading architectures. Tech. rep. UIUCDCS-R-98-2048, UIUC.
• 26: James R. Larus , Thomas Ball, Rewriting executable files to measure program behavior, Software—Practice & Experience, v.24 n.2, p.197-218, Feb. 1994 [doi>10.1002/spe.4380240204]
• 27: Allen Leung , Lal George, Static single assignment form for machine code, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.204-214, May 01-04, 1999, Atlanta, Georgia, United States
• 28: Jack Lee-Jay Lo , Susan J. Eggers , Henry M. Levy, Exploiting thread-level parallelism on simultaneous multithreaded processors, University of Washington, 1998
• 29: Huy Nguyen , Lizy Kurian John, Exploiting SIMD parallelism in DSP and multimedia algorithms using the AltiVec technology, Proceedings of the 13th international conference on Supercomputing, p.11-20, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305150]
• 30: Stuart Oberman , Greg Favor , Fred Weber, AMD 3DNow! Technology: Architecture and Implementations, IEEE Micro, v.19 n.2, p.37-48, March 1999 [doi>10.1109/40.755466]
• 31: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 32: Carlos García Quiñones , Carlos Madriles , Jesús Sánchez , Pedro Marcuello , Antonio González , Dean M. Tullsen, Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 33: Lawrence Rauchwerger , David A. Padua, The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.160-180, February 1999 [doi>10.1109/71.752782]
• 34: 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
• 35: Skoglund, J. and Felsberg, M. 2005. Fast image processing using SSE2. In Proceedings of the SSBA Symposium on Image Analysis.
• 36: 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]
• 37: 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]
• 38: Thakkar, S. T. and Huff, T. 1999. The Internet Streaming SIMD Extensions. Intel Tech. J., 8.
• 39: 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]
• 40: Jenn-Yuan Tsai , Pen-Chung Yew, The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.35, October 20-23, 1996
• 41: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 42: Michael J. Voss , Rudolf Eigenmann, ADAPT: Automated De-Coupled Adaptive Program Transformation, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.163, August 21-24, 2000
• 43: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, ACM SIGPLAN Notices, v.36 n.7, p.93-102, July 2001
• 44: Efe Yardimci , Michael Franz, Exploiting parallelism to improve the performance of sequential binary executables, California State University at Long Beach, Long Beach, CA, 2006
• 45: Efe Yardimci , Michael Franz, Dynamic parallelization and mapping of binary executables on hierarchical platforms, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128040]
• 46: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Incremental compilers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Optimization

General Terms:
Design, Experimentation, Performance

Keywords:
Continuous compilation and optimization, binary translation, dynamic parallelization