A formal model for divide-and-conquer and its parallel realization

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