More Web Proxy on the site http://driver.im/

Article

Free access

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

Authors:

Klaus E. Schauser,

David E. Culler,

Seth C. GoldsteinAuthors Info & Claims

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 259 - 271

https://doi.org/10.1145/199448.199511

Published: 25 January 1995 Publication History

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

[1]

Z. Ariola and Arvind. P-TAC: A parallel intermediate language. In Proceedings of the 1989 Conference on Functional Programming Languages and Computer Architecture, pages 230-242, September 1989.

Digital Library

[2]

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.

[3]

Arvind and R. S. Nikhil. Executing a Program on the MIT Tagged-Token Dataflow Architecture. IEEE Transactions on Computers, 39(3):300-318, March 1990.

Digital Library

[4]

A. Bloss and P. Hudak. Path Semantics. In Mathematical Foundations of Programming Language Semantics (LNCS 298). Springer-Ver}ag, April 1987.

Digital Library

[5]

D. E. Culler, S. C. Goldstein, K. E. Schauser, and T. von Eicken. TAM -- A Compiler Controlled Threaded Abstract Machine. Journal of Parallel and Distributed Computing, 18:347-370, July 1993.

Digital Library

[6]

S.R. Coorg. Partitioning Non-strict Languages for Multi-threaded Code Generation. Master's thesis, Dept. of EECS, MIT, Cambridge, MA, May 1994.

[7]

C. Clack and S. L. Peyton-Jones. Strictness Analysis - A Practical Approach. In Proc. Functional Programming Languages and Computer Architecture, Sept. 1985. Springer-Verlag LNCS 201.

Digital Library

[8]

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).

[9]

J. Ferrante, K. Ottenstein, and J. Warren. The Program Dependence Graph and its Use in Optimization A CM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

Digital Library

[10]

J. Gurd, C.C. Kirkham, and I. Watson. The Manchester Prototype Dataflow Computer. Communicatzons of the Association for Computing Machinery, 28(1):34-52, January 1985.

Digital Library

[11]

B. Goldberg. Multiproeessor Execution of Functional Programs. PhD thesis, Department of Computer Science, Yale University, 1988.

Digital Library

[12]

S.C. Goldstein. Implementation of a Threaded Abstract Machine on Sequential and Multiprocessors. Master's thesis, Computer Science Division-- EECS, U.C. Berkeley, 1994. (UCB/CSD 94-818).

Digital Library

[13]

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.

Digital Library

[14]

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).

[15]

H.F. Jordan. Performance Measurement on HEP A Pipelined MIMD Computer. In Proc. of the l Oth Annual Int. Syrup. on Comp. Arch, Stockholm, Sweden, June 1983.

Digital Library

[16]

R.B. Kieburtz. A RISC architecture for symbolic computation. In Proc. of 2nd Int. Cony. on Architectural Support }or Programmzng Languages and Operatzng Systems, October 1987.

[17]

A. Mycroft. The theory and practice of transforming call-by-need into call-by-value. In Inte#'natlonal Symposium on Programmang (LNCS 83). Springer- Verlag, April 1980.

Digital Library

[18]

R.S. Nikhil. Id (Version 90.0) Reference Manual. Technical Report CSG Memo, to appear, MIT Lab for Comp. Sci., 1990.

[19]

R.S. Nikhil. A Multithreaded Implementation of Id using P-RISC Graphs. In Proc. Sixth Ann. Workshop on Languages and Compilers for Parallel Computing, Portland, Oregon, August 1993.

Digital Library

[20]

R.S. Nikhil, G. M. Papadopoulos, and Arvind. *T: A Multithreaded Massively Parallel Architecture. In Proc. igth. Annual Intl. Symp. on Computer Architecture, May 1992.

Digital Library

[21]

W.A. Najjar, L. Roh, and W. A. P. BShm. Initial Performance of a Bottom-Up Clustering Algorithm for Data/tow Graphs. In Proc. IFIP Conf. on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism. North-Holland, January 1993.

Digital Library

[22]

G.M. Papadopoulos and D. E. Culler. Monsoon: an Explicit Token-Store Architecture. In Proc. of the 17th Annual Int. Symp. on Comp. Arch., Seattle, Washington, May 1990.

Digital Library

[23]

S. L. Peyton Jones, C. Clack, J. Salkild, and M. Hardie. GRIP - A High Performance Architecture for Parallel Graph Reduction. In Proc. Intl Conf. on Functional Programming and Comp. Arch., Sept. 1987.

Digital Library

[24]

S.L. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine. J. Functional Programming, April 1992.

[25]

K.E. Schauser. Compiling Lenient Languages .for Parallel Asynchronous Execution. PhD thesis, Computer Science Div., University of California at Berkeley, May 1994.

Digital Library

[26]

K. E. Schauser, D. Culler, and T. von Eicken. Compiler-controlled Multithreading for Lenient ParaUel Languages. In Proc. Conf. on FunctzonaI Programming Languages and Comp. Arch., Aug. 1991.

Digital Library

[27]

E. Spertus, S. C. Goldstein, K. E. Schauser, T. yon Eicken, D. E. Culler, and W. J. Dally. Evaluation of Mechanisms for Fine-Grained Parallel Programs in the J-Machine and the CM-5. In Proc. of the 20th Int'l Symposium on Computer Architecture, San Diego, CA, May 1993.

Digital Library

[28]

V. Sarkar and J. Hennessy. Compile-time Partitioning and Scheduling of Parallel Programs. In Proceedings o} the SIGPLAN 86 Symposium on Compiler Construction, June 1986.

Digital Library

[29]

S. Smetsers, E. Ngcker, J. van Groningen, and R. Plasmeijer. Generating Efficient Code for Lazy Functional Languages. In Proc. Functional Programming Languages and Comp. Arch., Aug. 1991.

Digital Library

[30]

S. Sakai, Y. Yamaguchi, K. Hiraki, Y. Kodama, and T. Yuba. An Architecture of a Data/tow Single Chip Processor. In Proc. of the 16th Annual Int. Symp. on Comp. Arch., June 1989.

Digital Library

[31]

K.R. Traub, D. E. Culler, and K. E. Schauser. Global Analysis for Partitioning Non-Strict Programs into Sequential Threads. In Proc. of the A CM Conf. on LISP and Functional Programming, June 1992.

Digital Library

[32]

K.R. Traub. A Compiler for the MIT Tagged-Token Dataflow Architecture. Technical Report TR-370, MIT Lab for Comp. Sci., August 1986. (MS Thesis, Dept. of EECS, MIT).

Digital Library

[33]

K.R. Traub. Implementation of Non-street Functional Programming Languages. MIT Press, 1991.

Digital Library

Cited By

Jo SChung K(2014)An efficient thread partition policy for secure functional languageJournal of Computer Virology and Hacking Techniques10.1007/s11416-014-0234-711:3(165-171)Online publication date: 30-Dec-2014
https://doi.org/10.1007/s11416-014-0234-7
Kusakabe SInenaga KAmamiya MTang XMarquez AGao G(2006)Implementing a non-strict functional programming language on a threaded architectureParallel and Distributed Processing10.1007/BFb0097894(138-152)Online publication date: 28-Oct-2006
https://doi.org/10.1007/BFb0097894
Ryan SAmaral JGao GRuiz ZMarquez ATheobald K(2006)Coping with very high latencies in petaflop computer systemsHigh Performance Computing10.1007/BFb0094912(71-82)Online publication date: 19-Oct-2006
https://doi.org/10.1007/BFb0094912
Show More Cited By

Index Terms

Separation constraint partitioning: a new algorithm for partitioning non-strict programs into sequential threads
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Randomness, geometry and discrete structures
  2. Semantics and reasoning
    1. Program constructs

Recommendations

Separation Constraint Partitioning - A New Algorithm for Partitioning Non-strict Programs into Sequential Threads
Multilevel algorithms for multi-constraint graph partitioning
SC '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing

Traditional graph partitioning algorithms compute a k-way partitioning of a graph such that the number of edges that are cut by the partitioning is minimized and each partition has an equal number of vertices. The task of minimizing the edge-cut can be ...
Constraint-driven system partitioning

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1995

415 pages

ISBN:0897916921

DOI:10.1145/199448

Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Peter Lee
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 January 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL95

Sponsor:

POPL95: 22nd ACM Symposium on Principles of Programming Languages

January 23 - 25, 1995

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 800 of 4,009 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jo SChung K(2014)An efficient thread partition policy for secure functional languageJournal of Computer Virology and Hacking Techniques10.1007/s11416-014-0234-711:3(165-171)Online publication date: 30-Dec-2014
https://doi.org/10.1007/s11416-014-0234-7
Kusakabe SInenaga KAmamiya MTang XMarquez AGao G(2006)Implementing a non-strict functional programming language on a threaded architectureParallel and Distributed Processing10.1007/BFb0097894(138-152)Online publication date: 28-Oct-2006
https://doi.org/10.1007/BFb0097894
Ryan SAmaral JGao GRuiz ZMarquez ATheobald K(2006)Coping with very high latencies in petaflop computer systemsHigh Performance Computing10.1007/BFb0094912(71-82)Online publication date: 19-Oct-2006
https://doi.org/10.1007/BFb0094912
Inenaga KKusakabe SMorimoto TAmamiya M(2005)Hybrid approach for non-strict dataflow program on commodity machineHigh Performance Computing10.1007/BFb0024220(243-254)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0024220
Araki TTanaka H(2005)Static granularity optimization of a committed-choice language FlengEuro-Par'97 Parallel Processing10.1007/BFb0002872(1191-1200)Online publication date: 26-Sep-2005
https://doi.org/10.1007/BFb0002872
Oyama YTaura KYonezawa A(2005)An efficient compilation framework for languages based on a concurrent process calculusEuro-Par'97 Parallel Processing10.1007/BFb0002781(546-553)Online publication date: 26-Sep-2005
https://doi.org/10.1007/BFb0002781
Ohno KIkawa MGoshimai MMori SNakashima HTomita S(2005)Efficient goal scheduling in a concurrent logic language using type-based dependency analysisAdvances in Computing Science — ASIAN'9710.1007/3-540-63875-X_58(268-282)Online publication date: 1-Aug-2005
https://doi.org/10.1007/3-540-63875-X_58
Coorg S(2005)Partitioning non-strict functional languages for multi-threaded code generationStatic Analysis10.1007/3-540-60360-3_34(82-99)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-60360-3_34
Ennals RJones S(2003)Optimistic evaluationACM SIGPLAN Notices10.1145/944746.94473138:9(287-298)Online publication date: 25-Aug-2003
https://dl.acm.org/doi/10.1145/944746.944731
Ennals RJones SRunciman CShivers O(2003)Optimistic evaluationProceedings of the eighth ACM SIGPLAN international conference on Functional programming10.1145/944705.944731(287-298)Online publication date: 25-Aug-2003
https://dl.acm.org/doi/10.1145/944705.944731
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents