| ™ |
Divacon: Parallel Divide and Conquer
Tutorial and Homework
My friend and hero, George Mou, has given mathematical form and intellectual rigor to the optimal decomposition, understanding, design, and implementation of parallel computer algorithms. Parallel Divide-and-Conquer using Divacon offers a simple, concretely achieveable, analytic and expressive methodology for design of such algorithms: the PDC() function generator. I call it an opinionated approach because there are guiderails all around, in the form of extremely limited options for expressing extremely few elements, but he considers it truth: see, he writes mathematics. And he has found and expressed the simple truths at the bottom, better yet, he teaches us to do the simple math with him. You will find his writing to be comprehensive, practical, and correct, in a style which is clear and mathematical. Strunk and White inform his style, and he follows his own maxim: To write clearly about something, it is best to fully understand it.The reader can sense magisterial understanding, and I find myself awestruck by the power conveyed to the comprehending reader by the simple combination of simple parts. See the Bit. Parallel algorithms are notoriously inconceiveable, so that it took Tukey and Gauss to come up with the good one (FFT, of course). (If only one had read the other, it wouldn't have taken 150 years.) Mou is in that stratosphere, despite lack of appreciation and uptake by history, perhaps because it does require careful study. I have done careful and thorough note-taking, and it requires sufficient and thoughtful practice, in order to fully understand it before then being able to practically use it. But the rewards are great for those who can create optimal parallel programs, and the path is clear and open, if you have the courage to take it.
Zhijing George Mou, A Formal Model for Divide-and-Conquer and Its Parallel Realization, May 1990, Research Report YALEU/DCS/RR-795.Let's move forward. For a couple of months I've been studying this pathbreaking dissertation and his patents and other papers. To support others to also understand and use it, the following are my homework and notes-in-progress, only somewhat organized, as follows:
|