Abstract
In this paper, we present a new approach to partitioning, the problem of generating sequential threads for programs written in a non-strict functional language. The goal of partitioning is to generate threads as large as possible, while retaining the non-strict semantics of the program. We define partitioning as a program transformation and design algorithms for basic block partitioning and interprocedural partitioning. The inter-procedural algorithm presented here is more powerful than the ones previously known and is based on abstract interpretation, enabling the algorithm to handle recursion in a straightforward manner. We prove the correctness of these algorithms in a denotational semantic framework.
The research described in this paper was funded in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-92-J-1310.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Z. Ariola and Z. Arvind. P-TAC: A Parallel Intermediate Language. In Proceedings of the ACM Conference on Functional Programming Languages and Computer Architecture, London, UK, pages 230–242. ACM, September 1989.
A. Bloss. Path Analysis and the Optimization of Non-strict Functional Languages. PhD thesis, Dept. of Computer Science, Yale University, May 1989.
A. Bloss and P. Hudak. Path Semantics. In Mathematical Foundations of Programming Language Semantics (LNCS 298). Springer-Verlag, April 1987.
J. Burn, C. Hankin, and S. Abramsky. Strictness Analysis for Higher-order Functions. Science of Computer Programming, 9, 1986.
S. R. Coorg. Partitioning Non-strict Languages for Multi-threaded Code Generation. Masters Thesis, EECS, MIT, May 1994.
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(4):347–370, July 1993.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA, 1979.
J. E. Hoch, D. M. Davenprot, V. G. Grafe, and K. M. Steele. Compile-time Partitioning of a Non-strict Language into Sequential Threads. In Proc. Symp. on Parallel and Distributed Processing, Dec 1991.
P. Hudak and J. Young. Higher-order Strictness Analysis of the Untyped Lambda-Calculus. In Proc. 12th ACM Symposium on Principles of Programming Languages, pages 97–109. ACM, Jan 1986.
Paul Hudak, Simon L. Peyton Jones, and Philip Wadler (editors). Report on the programming language haskell, a non-strict purely functional language (version 1.2). SIGPLAN Notices, Mar, 1992.
A. Mycroft. The Theory and Practice of Transforming Call-by-need into Call-by-value. In International Symposium on Programming (LNCS 83). Springer-Verlag, April 1980.
R. S. Nikhil. Id Language Reference Manual Version 90.1. Technical Report CSG Memo 284-2, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, July 15 1991.
R.S. Nikhil, G.M. Papadopoulos, and Arvind. *T: A Multithreaded Massively Parallel Architecture. In Proc. 19th Annual Intl. Symp. on Computer Architecture, May 1992.
G. Papadopoulos and D. Culler. Monsoon: an Explicit Token-Store Architecture. In Proc. of the 17th Intl. Symp. on Computer Architecture, May 1990.
K. E. Schauser. Compiling Lenient Languages for Parallel Asynchronous Execution. PhD thesis, Computer Science Div., Univ. of California at Berkeley., May 1994.
K. E. Schauser, D. Culler, and S. C. Goldstein. Separation Constraint Partitioning — A New Algorithm for Partitioning Non-strict Programs into Sequential Threads. In Proc. ACM Conference on Principles of Programming Languages (POPL), January 1995.
K. E. Schauser, D. Culler, and von Eicken T. Compiler-controlled Multithreading for Lenient Parallel Languages. In Proc. Conf. on Functional Programming Languages and Computer Architecture, August 1991.
K. R. Traub. A Compiler for the MIT Tagged-Token Dataflow Architecture. Technical Report TR-370, MIT Lab. for Computer Science, August 1986. (MS Thesis, Dept. of EECS, MIT).
K. R. Traub. Implementation of Non-strict Functional Programming Languages. MIT Press, Cambridge, MA, 1991.
K. R. Traub, D. E. Culler, and K. E. Schauser. Global Analysis for Partitioning Non-strict Programs into Sequential Threads. In Proc. of the ACM Conf. on LISP and Functional Programming, June 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coorg, S.R. (1995). Partitioning non-strict functional languages for multi-threaded code generation. In: Mycroft, A. (eds) Static Analysis. SAS 1995. Lecture Notes in Computer Science, vol 983. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60360-3_34
Download citation
DOI: https://doi.org/10.1007/3-540-60360-3_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60360-3
Online ISBN: 978-3-540-45050-4
eBook Packages: Springer Book Archive