2DT-FP - A PARALLEL FUNCTIONAL PROGRAMMING LANGUAGE ON 2-DIMENSIONAL DATA

We propose a new paradigm fdr 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 ca n be expressed in a functional or imperative base language; a typed va riant 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-dimensio nal representations. A set of examples tries to prove this claim. An i nterleaving semantics for 2DT-FP is given, exposing the potential for parallel execution of 2DT-FP programs. The claim is proved that any se quential and thus any parallel execution will deliver the same result. The implementation realized on the Intel Hypercube is described.