A fast approximate interprocedural analysis for speculative multithreading compilers

ABSTRACT

Speculative multithreading (SpMT) promises to be very effective for parallelizing non-numeric programs. Data dependences are perhaps the most important factor in the crucial step of deciding the thread boundaries, and SpMT compilers need to estimate data dependences as precisely as possible. Interprocedural points-to and side-effects information is essential to accurately determine data dependences. Determining this information has been an Achilles' heel in SpMT compilation. Existing interprocedural analyses are unsuitable for large programs, as they have high complexity or generate imprecise (very conservative) information that is not useful for aggressive speculative parallelization.This paper presents a novel interprocedural analysis scheme that is highly effective for use in SpMT compilers. It has running time and memory requirement almost linear in the number of procedures in the input program. The information it generates is comparable in accuracy with those generated by highly accurate context-sensitive interprocedural analyses, although it does not guarantee safe information (which is not a requirement for SpMT compilers any way). We implemented this interprocedural analysis in our SpMT compiler, and parallelized large non-numeric programs from the SPEC 2000 suite. Parallel execution of these threads in an SpMT simulator demonstrate good speedups for these non-numeric programs.

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: Anasua Bhowmik , Manoj Franklin, A general compiler framework for speculative multithreading, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564885]
• 3: Anasua Bhowmik , Manoj Franklin, A general compiler framework for speculative multithreaded processors, 2003
• 4: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 5: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 6: M. Emami. "A Practical Interprocedural Alias Analysis For an Optimizing/Parallelizing C Compiler," Masters Thesis, School of Computer Science, McGill University, 1993.
• 7: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 8: Manoj Franklin, Multiscalar Processors, Kluwer Academic Publishers, Norwell, MA, 2002
• 9: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 10: Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.97-105, June 17-19, 1998, Montreal, Quebec, Canada
• 11: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 12: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
• 13: Pedro Marcuello , Antonio González, Clustered speculative multithreaded processors, Proceedings of the 13th international conference on Supercomputing, p.365-372, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305214]
• 14: Kunle Olukotun , Lance Hammond , Mark Willey, Improving the performance of speculatively parallel applications on the Hydra CMP, Proceedings of the 13th international conference on Supercomputing, p.21-30, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305155]
• 15: Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
• 16: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 17: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 18: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 19: 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
• 20: J.-Y. Tsai, Z. Jiang, Z. Li, D. J. Lilja, X. Wang, P.-C. Yew, B. Zheng, and S. Schwinn. "Integrating Compilation Technology and Processor Architecture for Cost-Effective Concurrent Multithreading," in Journal of Information Science and Engineering, March 1998.
• 21: T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
• 22: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 23: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Algorithms, Languages

Keywords:
interprocedural analysis, pointer analysis, speculative multithreading (SpMT), thread-level parallelism (TLP)