Static Analysis for Divide-and-Conquer Pattern Discovery

keywords: Erlang, divide-and-conquer, pattern, parallelization
Routines implementing divide-and-conquer algorithms are good candidates for parallelization. Their identifying property is that such a routine divides its input into ``smaller'' chunks, calls itself recursively on these smaller chunks, and combines the outputs into one. We set up conditions which characterize a wide range of d & c routine definitions. These conditions can be verified by static program analysis. This way d & c routines can be found automatically in existing program texts, and their parallelization based on semi-automatic refactoring can be facilitated. We work out the details in the context of the Erlang programming language.
mathematics subject classification 2000: 68-N19
reference: Vol. 35, 2016, No. 4, pp. 764–791