Deriving efficient parallel programs for complex recurrences

Abstract

We propose a method to synthesize parallel divide-and-conquer programs from non-trivial sequential recurrences. Traditionally, such derivation methods are based on schematic rules which attempt to match each given sequential program to a prescribed set of program schemes that have parallel counterparts. Instead of relying on specialized program schemes, we propose a new approach to parallelization based on techniques built using elementary transformation rules. Our approach requires an induction to recover parallelism from sequential programs. To achieve this, we apply a second-order generalization step to selected instances of sequential equations, before an inductive derivation procedure. The new approach is systematic enough to be semi-automated, and shall be shown to be widely applicable using a range of examples.