ON THE SPACE-TIME MAPPING OF A CLASS OF DIVIDE-AND-CONQUER RECURSIONS
Christoph A. Herrmann, Christian Lengauer · Parallel Processing Letters · 1996
We propose a functional program skeleton for balanced fixed-degree divide-and-conquer and a method for its parallel implementation on message-passing multiprocessors. In the method, the operations of the skeleton are first mapped to a geometric computational model which is then mapped to space-time in order to expose the inherent parallelism. This approach is inspired by the method of parallelizing nested loops in the polytope model.