Static Analysis for Divide-and-Conquer Pattern Discovery

Year, pages: 2016, 764 - 791

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.

Kozsik, T., Tóth, M., Bozó, I., Horváth, Z. 2016. Static Analysis for Divide-and-Conquer Pattern Discovery. In Computing and Informatics, vol. 35, no.4, pp. 764-791. 1335-9150.

Kozsik, T., Tóth, M., Bozó, I., Horváth, Z. (2016). Static Analysis for Divide-and-Conquer Pattern Discovery. Computing and Informatics, 35(4), 764-791. 1335-9150.