PARALLEL DIVIDE-AND-CONQUER ON MESHES

We address the problem of mapping divide-and-conquer programs to mesh connected multicomputers with wormhole or store-and-forward routing, W e propose the binomial tree as an efficient model of parallel divide-a nd-conquer and present two mappings of the binomial tree to the 2D mes h. Our mappings exploit regularity in the communication structure of t he divide-and-conquer computation and are also sensitive to the underl ying flow control scheme of the target architecture. We evaluate these mappings using new metrics which are extensions of the classical noti ons of dilation and contention. We introduce the notion of communicati on slowdown as a measure of the total communication overhead incurred by a parallel computation. We conclude that significant performance ga ins can be realized when the mapping is sensitive to the flow control scheme of the target architecture.