Parallelization of divide-and-conquer by translation to nested loops

摘要: We present a hierarchical classification of specializations the divide-and-conquer paradigm. The aim is to identify subclass algorithms with an efficient parallel implementation which can be viewed as static space-time mapping. impose balanced call tree, fixed degree problem division, and elementwise operations. correctness our compile-time transformations proved by equational reasoning in Haskell; recursion iteration are handled induction. demonstrate practicality skeleton some examples, one Strassen's matrix multiplication.