Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

ABSTRACT

This article presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generted code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.

REFERENCES

• 1: Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, ACM SIGPLAN Notices, v.28 n.6, p.126-138, June 1993
• 2: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 4: Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, ACM SIGPLAN Notices, v.31 n.5, p.149-159, May 1996
• 5: BARNES, J. AND HUT, P. 1986. A hierarchical O(NlogN) force calculation algorithm. Nature 324, 4, 446-449.
• 6: Eric A. Brewer, High-level optimization via automated statistical modeling, ACM SIGPLAN Notices, v.30 n.8, p.80-91, Aug. 1995
• 7: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• 8: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 9: William Y. Chen , Scott A. Mahlke , Nancy J. Warter , Sadun Anik , Wen-mei W. Hwu, Profile-assisted instruction scheduling, International Journal of Parallel Programming, v.22 n.2, p.151-181, April 1994 [doi>10.1007/BF02577873]
• 10: CHILIMBI, T. AND LARUS, J. 1994. Cachier: A tool for automatically inserting cico annotations. In Proceedings of the 1994 International Conference on Parallel Processing. CRC Press, Inc., Boca Raton, FL, 89-98.
• 11: Alan L. Cox , Robert J. Fowler, Adaptive cache coherency for detecting migratory shared data, Proceedings of the 20th annual international symposium on Computer architecture, p.98-108, May 16-19, 1993, San Diego, California, United States
• 12: Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
• 13: Pedro C. Diniz , Martin C. Rinard, Lock coarsening: eliminating lock overhead in automatically parallelized object-based programs, Journal of Parallel and Distributed Computing, v.49 n.2, p.218-244, March 15, 1998 [doi>10.1006/jpdc.1998.1441 ]
• 14: Czarek Dubnicki , Thomas J. LeBlanc, Adjustable block size coherent caches, ACM SIGARCH Computer Architecture News, v.20 n.2, p.170-180, May 1992
• 15: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, ACM SIGPLAN Notices, v.31 n.5, p.160-170, May 1996
• 16: Babak Falsafi , David A. Wood, Reactive NUMA: a design for unifying S-COMA and CC-NUMA, Proceedings of the 24th annual international symposium on Computer architecture, p.229-240, June 01-04, 1997, Denver, Colorado, United States
• 17: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 18: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
• 19: FISHER, J. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July), 478-490.
• 20: Armando Fox , Steven D. Gribble , Eric A. Brewer , Elan Amir, Adapting to network and client variability via on-demand dynamic distillation, ACM SIGOPS Operating Systems Review, v.30 n.5, p.160-170, Dec. 1996
• 21: Stefan M. Freudenberger , Jacob T. Schwartz , Micha Sharir, Experience with the SETL Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.26-45, Jan. 1983 [doi>10.1145/357195.357197]
• 22: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 23: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, ACM SIGPLAN Notices, v.30 n.10, p.108-123, Oct. 17, 1995
• 24: M. Gupta , P. Banerjee, Demonstration of Automatic Data Partitioning Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.179-193, March 1992 [doi>10.1109/71.127259 ]
• 25: HARRIS, J., LAZARATOS, S., AND MICHELENA, R. 1990. Tomographic string inversion. In Proceedings of the 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts. 82-85.
• 26: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 27: CORPORATE Institute of Electrical and Electronics Engineers, Inc. Staff, IEEE Standard for Scalable Coherent Interface, Science: IEEE Std. 1596-1992, IEEE Standards Office, New York, NY, 1993
• 28: KEMMERER, R. AND ECKMANN, S. 1985. UNISEX: A UNix-based symbolic EXecutor for Pascal. Softw. Pract. Exper. 15, 5 (May), 439-458.
• 29: Ken Kennedy , Ulrich Kremer, Automatic data layout for high performance Fortran, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.76-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224495]
• 30: Gregor Kiczales, Beyond the Black Box: Open Implementation, IEEE Software, v.13 n.1, p.8-11, January 1996
• 31: Jai-Hoon Kim , Nitin H. Vaidya, A cost-comparison approach for adaptive distributed shared memory, Proceedings of the 10th international conference on Supercomputing, p.44-51, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237584]
• 32: KNUTH, D. E. 1971. An empirical study of FORTRAN programs. Softw. Pract. Exper. 1, 105-133.
• 33: Peter Lee , Mark Leone, Optimizing ML with run-time code generation, ACM SIGPLAN Notices, v.31 n.5, p.137-148, May 1996
• 34: Daniel Edward Lenoski, The design and analysis of DASH: a scalable directory-based multiprocessor, Stanford University, Stanford, CA, 1992
• 35: Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, ACM SIGPLAN Notices, v.28 n.7, p.83-91, July 1993
• 36: Beng-Hong Lim , Anant Agarwal, Reactive synchronization algorithms for multiprocessors, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.25-35, October 05-07, 1994, San Jose, California, United States
• 37: Sungdo Moon , Mary W. Hall , Brian R. Murphy, Predicated array data-flow analysis for run-time parallelization, Proceedings of the 12th international conference on Supercomputing, p.204-211, July 1998, Melbourne, Australia [doi>10.1145/277830.277874]
• 38: W. G. Morris, CCG: a prototype coagulating code generator, ACM SIGPLAN Notices, v.26 n.6, p.45-58, June 1991
• 39: Karl Pettis , Robert C. Hansen, Profile guided code positioning, ACM SIGPLAN Notices, v.25 n.6, p.16-27, Jun. 1990
• 40: John Plevyak , Xingbin Zhang , Andrew A. Chien, Obtaining sequential efficiency for concurrent object-oriented languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-321, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199524]
• 41: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987
• 42: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, ACM SIGPLAN Notices, v.30 n.6, p.218-232, June 1995
• 43: Martin C. Rinard , Pedro C. Diniz, Commutativity analysis: a new analysis technique for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.942-991, Nov. 1997 [doi>10.1145/267959.269969]
• 44: M. C. Rinard , D. J. Scales , M. S. Lam, Heterogeneous parallel programming in Jade, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.245-256, November 16-20, 1992, Minneapolis, Minnesota, United States
• 45: ROMER, T., LEE, D., BERSHAD, B., AND CHEN, g. 1994. Dynamic page mapping policies for cache conflict resolution on standard hardware. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (Monterey, CA, May). USENIX Assoc., Berkeley, CA, 255-266.
• 46: Rafael H. Saavedra , Daeyeon Park, Improving the Effectiveness of Software Prefetching with Adaptive Execution, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.68, October 20-23, 1996
• 47: SALTZ, J., BERRYMAN, H., AND WU, J. 1991. Multiprocessors and run-time compilation. In Proceedings of the Conference on Practical Parallel Computing: Achievements, Problems and Prospects (Capri, Italy, June 3-7, 1990), P. MessinG and A. Murli, Eds. John Wiley & Sons, Inc., New York, NY, 573-592.
• 48: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 49: SMITH, M. 1991. Tracing with Pixie. Tech. Rep. CSL-TR-91-497. Stanford University, Stanford, CA.
• 50: David W. Wall, Global register allocation at link time, ACM SIGPLAN Notices, v.21 n.7, p.264-275, July 1986
• 51: Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, ACM SIGOPS Operating Systems Review, v.31 n.5, p.15-26, Dec. 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

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

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization; Run-time environments; Compilers

General Terms:
Measurement, Performance

Keywords:
parallel computing, parallelizing compilers