This paper addresses the problem of mapping divide-and-conquer programs to mesh-connected multicomputers with wormhole or store-and-forward routing. We propose the binomial tree as an efficient model of parallel divide-and-conquer computations. We develop mappings which exploit the regular communication structure of this paradigm, including both the communication topology and the phases of message passing over time.

We develop several new performance metrics to evaluate the communication overhead of a mapped divide-and-conquer computation. These metrics are natural extensions of the standard contention and dilation metrics used in the literature, with refinements that take into account the underlying flow control scheme (worm­hole vs. store and forward).

We present two mappings of the binomial tree divide-and-conquer computation to the 2-D mesh and evaluate their performance using our new metrics. Our first mapping, the Reflecting Mapping has optimal communication slowdown on a target machine with wormhole routing, independent of the message volumes. We also present a second mapping called the Growing Mapping which outperforms the Reflecting Mapping for a wide range of message volumes on a target machine with store and forward routing. We conclude that significant performance gains can be realized when the mapping of the divide and conquer computation to the 2-D mesh is sensitive to the flow control scheme of the target architecture.