A calculus for parallel computations over multidimensional dense arrays

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cl.2006.07.005 Byline: Roberto Di Cosmo (a)(b), Zheng Li (a)(b), Susanna Pelagatti (c) Abstract: We present a calculus to formalize and give costs to parallel computations over multidimensional dense arrays. The calculus extends a simple distribution calculus (proposed in some previous work) with computation and data collection. We consider an SPMD programming model in which process interaction can take place using point-to-point as well as collective operations, much in the style of MPI. We want to give a rigorous description of all stages of data parallel applications working over dense arrays: initial distribution (i.e., partition and replication) of arrays over a set of processors, parallel computation over distributed data, exchange of intermediate results and final data gather. In the paper, beside defining the calculus, we give it a formal semantics, prove equations between different combinations of operations, and show how to associate a cost to operation combinations. This last feature makes possible to make quantitative cost-driven choices between semantically equivalent implementation strategies. Author Affiliation: (a) PPS, Universite Paris VII - Denis Diderot, Case 7014, 2 place Jussieu, F-75251 Paris Cedex 05, France (b) Project Cristal, INRIA Rocquencourt, France (c) Dipartimento di Informatica, Universita di Pisa, Largo Pontecorvo 3, I-56127 Pisa, Italy Article History: Received 5 October 2005; Accepted 24 July 2006