Automatic compiler techniques for thread coarsening for multithreaded architectures

ABSTRACT

Multithreaded architectures are emerging as an important class of parallel machines. By allowing fast context switching between threads on the same processor, these systems hide communication and synchronization latencies and allow scalable parallelism for dynamic and irregular applications. Thread partitioning is the most important task in compiling high-level languages for multithreaded architectures. Non-preemptive multithreaded architectures, which can be built from off-the-shelf components, require that if a thread issues a potentially remote memory request, then any statement that is dependent upon this request must be in a separate thread.When performing thread partitioning on codes that use pointer-based recursive data structures, it is often difficult to extract accurate dependence information. As a result, threads of unnecessarily small granularity get generated, which, because of thread switching costs, leads to increased execution time. In this paper, we present three techniques that lead to improved extraction and representation of dependence information in the presence of structured control flow, references through fields of structures, and pointer-based data structures. The benefit of these techniques is the generation of coarser-grained threads and, therefore, decreased execution time. Our experiments were performed using the EARTH-C compiler and the EARTH multithreaded architecture model emulated on both a cluster of Pentium PCs and a distributed memory multiprocessor. On our set of 6 pointer-based programs, these techniques reduced the static number of threads by 38%. Reductions in execution times ranged from 16% to 45% on the four programs we measured runtime performance.

REFERENCES

• 1: Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
• 2: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 3: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 4: U. Bruening , Wolfgang K. Giloi , Wolfgang Schroeder-Preikschat, Latency Hiding in Message-Passing Architectures, Proceedings of the 8th International Symposium on Parallel Processing, p.704-709, April 01, 1994
• 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: David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser , Thorsten von Eicken, TAM—a compiler controlled threaded abstract machine, Journal of Parallel and Distributed Computing, v.18 n.3, p.347-370, July 1993 [doi>10.1006/jpdc.1993.1070 ]
• 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: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 9: Rakesh Ghiya , Laurie J. Hendren , Yingchun Zhu, Detecting Parallelism in C Programs with Recursive Darta Structures, Proceedings of the 7th International Conference on Compiler Construction, p.159-173, March 28-April 04, 1998
• 10: L. J. Hendren , Xinan Tang , Yingchun Zhu , G. R. Gao , Xun Xue , Haiying Cai , P. Ouellet, Compiling C for the EARTH Multithreaded Architecture, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.12, October 20-23, 1996
• 11: Laurie J. Hendren , Xinan Tang , Yingchun Zhu , Shereen Ghobrial , Guang R. Gao , Xun Xue , Haiying Cai , Pierre Ouellet, Compiling C for the EARTH multithreaded architecture, International Journal of Parallel Programming, v.25 n.4, p.305-338, Aug. 1997 [doi>10.1007/BF02699905]
• 12: Herbert H. J. Hum , Olivier Maquelin , Kevin B. Theobald , Xinmin Tian , Xinan Tang , Guang R. Gao , Phil Cupryk , Nasser Elmasri , Laurie J. Hendren , Alberto Jimenez , Shoba Krishnan , Andres Marquez , Shamir Merali , Shashank S. Nemawarkar , Prakash Panangaden , Xun Xue , Yingchun Zhu, A design study of the EARTH multiprocessor, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.59-68, June 27-29, 1995, Limassol, Cyprus
• 13: Robert A. Iannucci. A datafiow/von Neumann hybrid architecture. MIT/LCS/TR-418, MIT for ACM Computing Surveys, Cambridge, July 1988. PhD thesis, May 1988.
• 14: 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
• 15: Jack L. Lo , Susan J. Eggers , Henry M. Levy , Sujay S. Parekh , Dean M. Tullsen, Tuning compiler optimizations for simultaneous multithreading, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.114-124, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Rishiyur Nikhil. Cid: A parallel C for distributed memory machines. Technical report, Cambridge Research Laboratory, Digital Equipment Corporation, 1994.
• 17: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 18: Lucas Roh , Walid A. Najjar , Bhanu Shankar , A. P. Wim Böhm, An Evaluation of Optimized Threaded Code Generation, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.37-46, August 24-26, 1994
• 19: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Mitsuhisa Sato , Yuetsu Kodama , Shuichi Sakai , Yoshinori Yamaguchi, EM-C: Programming with Explicit Parallelism and Locality for EM-4 Multiprocessor, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.3-14, August 24-26, 1994
• 21: Klaus Eric Schauser, David E. Culler, and Thorsten yon Eiken. Compiler-controlled multithreading for lenient parallel languages. No. UCB/CSD 91/640, ACM Computing Surveys, at Berkeley, 1991.
• 22: Xinan Tang , Guang R. Gao, Compiling for multithreaded architectures, 2000
• 23: Xinan Tang , Guang R. Gao, Automatically partitioning threads for multithreaded architectures, Journal of Parallel and Distributed Computing, v.58 n.2, p.159-189, Aug. 1999 [doi>10.1006/jpdc.1999.1551 ]
• 24: Xinan Tang , R. Ghiya , L. J. Hendren , G. R. Gao, Heap Analysis And Optimizations For Threaded Programs, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.14, November 11-15, 1997
• 25: J.-Y. Tsai , Z. Jiang , E. Ness , P.-C. Yew, Performance Study of a Concurrent Multithreaded Processor, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.24, January 31-February 04, 1998
• 26: 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
• 27: Suan Hsi Yong , Susan Horwitz , Thomas Reps, Pointer analysis for programs with structures and casting, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.91-103, May 01-04, 1999, Atlanta, Georgia, United States
• 28: Xingbin Zhang , Andrew A. Chien, Dynamic pointer alignment: tiling and communication optimizations for parallel pointer-based computations, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.37-47, June 18-21, 1997, Las Vegas, Nevada, United States
• 29: Yingchun Zhu , Laurie J. Hendren, Communication optimizations for parallel C programs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.199-211, June 17-19, 1998, Montreal, Quebec, Canada
• 30: Yingchun Zhu , L. J. Hendren, Locality Analysis For Parallel C Programs, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.2, November 11-15, 1997

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory