Abstract
We propose a new paradigm for programming multiprocessor systems, 2DT (two-dimensional transformations). 2DT programs are composed of local computations on linear data (columns) and global transformations on 2-dimensional combinations of columns (2D-arrays). Local computations can be expressed in a functional or imperative base language; a typed variant of Backus' FP is chosen for 2DT-FP. The level of abstraction of 2DT makes it suitable for programming a relevant set of algorithms, in general any algorithms, whose data can be easily mapped to 2-dimensional representations. A set of examples tries to prove this claim. An interleaving semantics for 2DT-FP is given, exposing the potential for parallel execution of 2DT-FP programs. The claim is proved that any sequential and thus any parallel execution will deliver the same result. The implementation realized on the Intel Hypercube is described.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Backus, Can programming be liberated from the von Neumann style? A functional style and its algebra of programs.Comm. of the ACM,21(8):613–641 (1978).
K. R. Apt and E. R. Olderog,Verification of Sequential and Concurrent Programs. Springer-Verlag (1991).
D. Banerjee and C. Walinsky, An optimizing compiler forFP *—a data-parallel dialect ofFP. Parallel and Distributed Processing, p. 70–78 (1991).
J. Hill. Vectorizing a non-strict Functional Language for a data-parallel “Spineless (not so) Tagless G-machine”. In M. van Eekelen R. Plasmeijer (ed.),Implementation of Functional Languages, pp. 87–100 (September 1993).
G. K. Jouret, Compiling functional languages for SIMD architectures.Parallel and Distributed Processing, pp. 79–86 (1991).
G. Hains and L. M. R. Mullin, Parallel functional programming with arrays.The Computer Journal (1993).
D. Cann, Retire Fortran? A Debate Rekindled.Comm. of the ACM,35(8):81–89, (August 1992).
T. Rauber and G. Rünger, Hypercube implementation and performance analysis for extrapolation methods. InProc. of the CONPAR '94, Linz, AustriaLecture Notes in Computer Science,854:265–276 (September 1994) Springer-Verlag.
Y. Ben-Asher, D. Egozi, and A. Schuster, 2-D SIMD algorithms for perfect shuffle networks.J. Parallel and Distributed Computing,16:250–257 (1992).
Y. Ben-Asher, H. Seidl, and R. Wilhelm, The TRANSPOSE machine: A global implementation of a parallel graph reducer. InProc. of IEEE Tencon '89, Bombay (1989).
Y. Ben-Asher, G. Rünger, A. Schuster, and R. Wilhelm, Implementing 2DT-FP on a multiprocessor. InProc. of 5th Int. Conf. on Compiler Construction, CC'94, Edinburgh,Lecture Notes in Computer Science,786:113–127 (1994) Springer-Verlag.
G. D. Plotkin, A structural approach to operational semantics. Technical Report DAIMI-FN 19, Department of Computer Science, Aarhus University (1981).
Y. Ben-Asher, G. Rünger, A. Schuster, and R. Wilhelm, 2DT-FP: An FP based programming language for efficient parallel programming of multi processor networks. InProc. of PARLE'93, München,Lecture Notes in Computer Science,694:42–55 (1993) Springer-Verlag.
Author information
Authors and Affiliations
Additional information
Supported by the Deutsche Forschungsgemeinschaft, DFG
Rights and permissions
About this article
Cite this article
Ben-Asher, Y., Rünger, G., Schuster, A. et al. 2DT-FP: A parallel functional programming language on two-dimensional data. Int J Parallel Prog 23, 389–422 (1995). https://doi.org/10.1007/BF02577772
Received:
Issue date:
DOI: https://doi.org/10.1007/BF02577772