A formal model for divide-and-conquer and its parallel realization
Zhijing G. Mou · 1990
Divide-and-conquer (DC) has long been known to be an effective programming paradigm in sequential computing. More recently, its significance to parallel computation has also been noted; many efficient parallel DC algorithms have emerged. However, the notion of divide-and-conquer has not yet received the formal treatment it deserves. This has precluded recognition of the common structure and intrinsic constituents of many DC algorithms, as well as the definition of a parallel programming environment that supports the development of DC algorithms. This dissertation contains the results of a research effort aimed at solving the problems above. I present (1) an algebraic model for divide-and-conquer called pseudomorphism, which permits DC algorithms to be designed by studying the algebraic properties of the problems; (2) a programming notation called Divacon which allows DC algorithms to be specified by a small set of primitives and functional forms in a way that is concise, hierarchical, and highly modular; (3) a collection of applications programs based on the formal DC model; (4) a tool developed for the analysis for Divacon programs; and (5) a prototype implementation of the model on the Connection Machine. The DC model leads to the definition of two parallel programming constructs called PDC and SDC. Their expressiveness is demonstrated by several examples, including polynomial evaluation, matrix multiplication, sort, Gaussian elimination, and the solution of triangular systems. Furthermore, these two parallel programming constructs are powerful enough to subsume many other well-known parallel constructs such as broadcast, reduction, and scan.