Abstract
Data-parallel ML is proposed for compilation to a distributed version (DPCAM) of Cousineau, Curien and Mauny's Categorical Abstract Machine. The DPCAM is a static network of CAMs which dynamically restrict the MIMD execution mode: nodes execute the same program and communicate only while executing the same function body. Programs violating this restriction or exhibiting unbounded spatial recursion abort or deadlock. The execution model thus defines a class of SPMD programs.
With respect to syntax and types, DPML is Mini-ML enriched with localization and remote evaluation functions. Its values are arrays of size matching the DPCAM network and containing ML values. Pointwise functions, data-parallel primitives and systolic algorithms are easily programmed. To improve the language's portability there is no automatic virtualization mechanism. Hence DPML is an intermediate target for more elaborate data-parallel languages, bridging the gap between direct source-language processor allocation and fully automatic allocation.
Work supported by FCAR and NSERC.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Amamiya and R. Taniguchi, Datarol: A massively parallel architecture for functional languages, in 2nd IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, Dec. 1990, IEEE Computer Society.
Z. Ariola and Arvind, P-TAC: A parallel intermediate language, in FPCA Functional Programming Languages and Computer Architecture, ACM Press, 1989, pp. 230–242.
P. Bailey and M. Newey, Implementing ML on distributed memory multiprocessors, in Boulder Workshop on Languages, Compilers and Run Time Environments for Distributed Memory Multiprocessors, Boulder, CO, October 1992, ACM. Appears in SIGPLAN Newsletter.
G. Blelloch and S. Chatterjee, VCODE: a data-parallel intermediate language, in Third IEEE Symposium on the Frontiers of Massively Parallel Computation, J. JaJa, ed., 1990.
G. E. Blelloch, Vector Models for Data-Parallel Computing, MIT Press, 1990.
L. Bougé, On the semantics of languages for massively parallel SIMD architectures, in PARLE-91, E. H. L. Aarts and J. van Leeuwen, eds., no. 505 and 506 in Lecture Notes in Computer Science, Eindhoven, The Netherlands, June 1991, Springer.
M. Chen, Transformations of parallel programs in Crystal, Tech. Rep. YALEU/DCS/RR-469, Yale University, April 1986.
D. Clément, J. Despeyroux, T. Despeyroux, and G. Kahn, A simple applicative language: Mini-ML, Rapport Technique 529, INRIA, Institut National de Recherche en Informatique et Automatique, 1991.
G. Cousineau, P.-L. Curien, and M. Mauny, The categorical abstract machine, in Functional Programming Languages and Computer Architectures, J.-P. Jouannaud, ed., no. 201 in Lecture Notes in Computer Science, Springer, 1985.
P.-L. Curien, Categorical Combinators, Sequential Algorithms and Functional Programming, Research Notes in Theoretical Computer Science, Pitman, 1986.
Damas and Milner, Principal type-schemes for functional programs, in Principles of Programming Languages. Annual ACM SIGACT-SIGPLAN Symposium, Association for Computing Machinery, New York, NY, 1982, pp. 207–212.
A. Giacalone, P. Mishra, and S. Prasad, Facile: a symmetric integration of concurrent and functional programming, International Journal of Parallel Programming, 18 (1989), pp. 121–160.
J.-L. Giavitto, Un langage data-flow synchrone pour la simulation massivement parallèle, in Secondes Journées Francophones des Langages Applicatifs, JFLA-92, C. Queinnec, ed., Tréguier, France, Février 1992, pp. 40–62. Revue Bigre no. 76–77.
G. Hains and L. M. R. Mullin, Parallel functional programming with arrays, The Computer Journal, (1993).
K. Hammond, Parallel SML: A Functional Language and its Implementation in Dactl, Pitman-MIT Press, 1991.
P. Hoogvorst, R. Keryell, P. Matherat, and N. Paris, POMP or how to design a massively parallel machine with small developments, in PARLE-91, E. H. L. Aarts, J. van Leeuwen, and M. Rem, eds., no. 505 in LNCS, Springer, 1991, pp. 83–100.
G. K. Jouret, Compiling functional languages for SIMD architectures, in Workshop on Abstract Machine Models for Highly Parallel Computers, P. M. Dew, T. Lake, and J. Davy, eds., University of Leeds, March 1991, British Computer Society. Two volumes.
M. Mauny, Functional programming using CAML, Rapport Technique 129, INRIA, Institut National de Recherche en Informatique et Automatique, 1991.
M. Mauny and A. Suárez, Implementing functional languages in the categorical abstract machine, in Conference on Lisp and Functional Programming, ACM, 1986.
C. Mauras, P. Gachet, P. Quinton, and Y. Saouter, ALPHA du CENTAUR: an environment for the design of regular algorithms, tech. rep., IRISA-Rennes France, 1988.
R. Milner and M. Tofte, Commentary on Standard ML, MIT Press, 1991.
N. Paris, Definition of POMPC (version 1.99), Publication 92-5-bis, Laboratoire d'Informatique de l'École Normale Supérieure, Paris, March 1991.
P. Quinton and Y. Robert, Algorithmes et architectures systoliques, Masson, 1989.
J. H. Reppy, CML: A higher-order concurrent language, in SIGPLAN'91 Conference on Programming Language Design and Implementation, ACM, June 1991.
G. Steele and W. Hillis, Connection Machine Lisp: A Fine Grained Parallel Symbolic Processing, in ACM Conf. on Lisp and Funct. Progr., Cambridge MA, 1986, pp. 276–297.
C. Walinsky and D. Banerjee, A functional programming language compiler for massively parallel computers, in Conference on Lisp and Functional Programming, Nice, France, June 1990, ACM.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hains, G., Foisy, C. (1993). The data-parallel categorical abstract machine. In: Bode, A., Reeve, M., Wolf, G. (eds) PARLE '93 Parallel Architectures and Languages Europe. PARLE 1993. Lecture Notes in Computer Science, vol 694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56891-3_5
Download citation
DOI: https://doi.org/10.1007/3-540-56891-3_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56891-9
Online ISBN: 978-3-540-47779-2
eBook Packages: Springer Book Archive