A FRAMEWORK FOR GENERATING DISTRIBUTED-MEMORY PARALLEL PROGRAMS FOR BLOCK RECURSIVE ALGORITHMS

A framework for synthesizing communication-efficient distributed-memor y parallel programs for block recursive algorithms such as the fast Fo urier transform (FFT) and Strassen's matrix multiplication is presente d, This framework is based on an algebraic representation of the algor ithms, which involves the tensor (Kronecker) product and other matrix operations, This representation is useful in analyzing the communicati on implications of computation partitioning and data distributions, Th e programs are synthesized under two different target program models. These two models are based on different ways of managing the distribut ion of data for optimizing communication, The first model uses point-t o-point interprocessor communication primitives, whereas the second mo del uses data redistribution primitives involving collective all-to-ma ny communication. These two program models are shown to be suitable fo r different ranges of problem size, The methodology is illustrated by synthesizing communication-efficient programs for the FFT, This framew ork has been incorporated into the EXTENT system for automatic generat ion of parallel/vector programs for block recursive algorithms. (C) 19 96 Academic Press, Inc.