Parallelization by semantic detection of reductions. (English) Zbl 0587.68021

Programming, Proc. Eur. Symp., Saarbr├╝cken/FRG 1986, Lect. Notes Comput. Sci. 213, 223-236 (1986).
[For the entire collection see Zbl 0578.00005.]
One of the best known techniques to compile sequential programs for multiprocessors is to detect the so called reduction operations. An example of such an operation is the sum of vector elements which can be evaluated under a pyramidal scheme using the associativity property of addition. A method to detect such operations in a PASCAL or FORTRAN-like programming language is presented. This detection and the corresponding modifications to the source programs are considered as non-standard denotational interpretations of the abstract syntax tree of the object programs. A by-product of this paper is to show how a denotational specification of a nontrivial application can directly lead to a running prototype, using here the ML programming language as an ”executable specification language”.


68N25 Theory of operating systems


Zbl 0578.00005