Separation constraint partitioning: a new algorithm for partitioning non-strict programs into sequential threads

ABSTRACT

In this paper we present substantially improved thread partitioning algorithms for modern implicitly parallel languages. We present a new block partitioning algorithm, separation constraint partitioning, which is both more powerful and more flexible than previous algorithms. Our algorithm is guaranteed to derive maximal threads. We present a theoretical framework for proving the correctness of our partitioning approach, and we show how separation constraint partitioning makes interprocedural partitioning viable.We have implemented the partitioning algorithms in an Id90 compiler for workstations and parallel machines. Using this experimental platform, we quantify the effectiveness of different partitioning schemes on whole applications.

REFERENCES

• AA89: Zena Ariola , Arvind, P-TAC: a parallel intermediate language, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.230-242, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99388]
• ACI+83: Arvind, D. E. Culler, R. A. Iannucci, V. Kathail, K. Pingali, and R. E. Thomas. The Tagged Token Dataflow Architecture. Technical report, MIT Lab for Comp. Sci., August 1983.
• AN90: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• BH87: Adrienne Bloss , Paul Hudak, Path Semantics, Proceedings of the 3rd Workshop on Mathematical Foundations of Programming Language Semantics, p.476-489, April 08-10, 1987
• CGSvE93: 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]
• Coo94: S.R. Coorg. Partitioning Non-strict Languages for Multi-threaded Code Generation. Master's thesis, Dept. of EECS, MIT, Cambridge, MA, May 1994.
• CPJ85: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• Cul90: D.E. Culler. Managing Parallelism and Resources in Scientific Data/tow Programs. Technical Report 446, MIT Lab for Comp. Sci., March 1990. (PhD Thesis, Dept. of EECS, MIT).
• FOW87: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• GKW85: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• Gol88: Benjamin F. Goldberg, Multiprocessor execution of functional programs, 1988
• Gol94: Seth C Goldstein, The Implementation of a Threaded Abstract Machine, University of California at Berkeley, Berkeley, CA, 1999
• HDGS91: J.E. Hoch, D. M. Davenport, V. G. Grafe, and K. M. Steele. Compile-time Partitioning of a Non-strict Language into Sequential Threads. In Proc. Syrup. on Parallel and Distributed Processing, Dec. 1991.
• Ian88: R.A. Iannucci. A DatMtow/von Neumann Hybrid Architecture. Technical Report TR-418, MIT Lab for Comp. Sci., May 1988. (PhD Thesis, Dept. of EECS, MIT).
• Jor83: Harry F. Jordan, Performance measurements on HEP - a pipelined MIMD computer, Proceedings of the 10th annual international symposium on Computer architecture, p.207-212, June 13-17, 1983, Stockholm, Sweden
• Kie87: Richard B. Kieburtz, A RISC architecture for symbolic computation, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.146-155, October 1987, Palo Alto, California, United States
• Myc80: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• Nik90: R.S. Nikhil. Id (Version 90.0) Reference Manual. Technical Report CSG Memo, to appear, MIT Lab for Comp. Sci., 1990.
• Nik93: Rishiyur S. Nikhil, A Multithreaded Implementation of Id using P-RISC Graphs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.390-405, August 12-14, 1993
• NPA92: R. S. Nikhil , G. M. Papadopoulos , Arvind, T: a multithreaded massively parallel architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.156-167, May 19-21, 1992, Queensland, Australia
• NRB93: Walid A. Najjar , Lucas Roh , A. P. Wim Böhm, The Initial Performance of a Bottom-Up Clustering Algorithm for Dataflow Graphs, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.91-100, January 20-22, 1993
• PC90: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• PCSH87: Simon L. Peyton Jones , Chris Clack , John Salkild , Mark Hardie, GRIP—A high-performance architecture for parallel graph reduction, Proc. of a conference on Functional programming languages and computer architecture, p.98-112, October 1987, Portland, Oregon, United States
• Pey92: S.L. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine. J. Functional Programming, April 1992.
• Sch94: Klaus Erik Schauser, Compiling lenient languages for parallel asynchronous execution, University of California at Berkeley, Berkeley, CA, 1994
• SCvE91: Klaus Erik Schauser , David E. Culler , Thorsten von Eicken, Compiler-controlled multithreading for lenient parallel languages, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.50-72, June 1991, Cambridge, Massachusetts, United States
• SGS+93: Ellen Spertus , Seth Copen Goldstein , Klaus Erik Schauser , Thorsten von Eicken , David E. Culler , William J. Dally, Evaluation of mechanisms for fine-grained parallel programs in the J-machine and the CM-5, Proceedings of the 20th annual international symposium on Computer architecture, p.302-313, May 16-19, 1993, San Diego, California, United States
• SH86: Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.17-26, June 25-27, 1986, Palo Alto, California, United States
• SNvGP91: Sjaak Smetsers , Eric Nöcker , John van Groningen , Rinu Plasmeijer, Generating efficient code for lazy functional languages, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.592-617, June 1991, Cambridge, Massachusetts, United States
• SYH+89: S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
• TCS92: Kenneth R. Traub , David E. Culler , Klaus E. Schauser, Global analysis for partitioning non-strict programs into sequential threads, Proceedings of the 1992 ACM conference on LISP and functional programming, p.324-334, June 22-24, 1992, San Francisco, California, United States
• Tra86: K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
• Tra91: Kenneth R. Traub, Implementation of non-strict functional programming languages, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Parallel C

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Experimentation, Languages, Theory, Verification