Nothing Special   »   [go: up one dir, main page]

Skip to main content

The data-parallel categorical abstract machine

  • Paper Sessions
  • Conference paper
  • First Online:
PARLE '93 Parallel Architectures and Languages Europe (PARLE 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 694))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

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

    Google Scholar 

  2. Z. Ariola and Arvind, P-TAC: A parallel intermediate language, in FPCA Functional Programming Languages and Computer Architecture, ACM Press, 1989, pp. 230–242.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  5. G. E. Blelloch, Vector Models for Data-Parallel Computing, MIT Press, 1990.

    Google Scholar 

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

    Google Scholar 

  7. M. Chen, Transformations of parallel programs in Crystal, Tech. Rep. YALEU/DCS/RR-469, Yale University, April 1986.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  10. P.-L. Curien, Categorical Combinators, Sequential Algorithms and Functional Programming, Research Notes in Theoretical Computer Science, Pitman, 1986.

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  14. G. Hains and L. M. R. Mullin, Parallel functional programming with arrays, The Computer Journal, (1993).

    Google Scholar 

  15. K. Hammond, Parallel SML: A Functional Language and its Implementation in Dactl, Pitman-MIT Press, 1991.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  18. M. Mauny, Functional programming using CAML, Rapport Technique 129, INRIA, Institut National de Recherche en Informatique et Automatique, 1991.

    Google Scholar 

  19. M. Mauny and A. Suárez, Implementing functional languages in the categorical abstract machine, in Conference on Lisp and Functional Programming, ACM, 1986.

    Google Scholar 

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

    Google Scholar 

  21. R. Milner and M. Tofte, Commentary on Standard ML, MIT Press, 1991.

    Google Scholar 

  22. N. Paris, Definition of POMPC (version 1.99), Publication 92-5-bis, Laboratoire d'Informatique de l'École Normale Supérieure, Paris, March 1991.

    Google Scholar 

  23. P. Quinton and Y. Robert, Algorithmes et architectures systoliques, Masson, 1989.

    Google Scholar 

  24. J. H. Reppy, CML: A higher-order concurrent language, in SIGPLAN'91 Conference on Programming Language Design and Implementation, ACM, June 1991.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Arndt Bode Mike Reeve Gottfried Wolf

Rights and permissions

Reprints 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

Publish with us

Policies and ethics