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.
@article{cai3377,
author = {Tam\'as Kozsik; E\"otv\"os Lor\'and University, Budapest and Melinda T\'oth; ELTE-Soft Nonprofit Ltd., Budapest and Istv\'an Boz\'o; ELTE-Soft Nonprofit Ltd., Budapest and Zolt\'an Horv\'ath; ELTE-Soft Nonprofit Ltd., Budapest},
title = {Static Analysis for Divide-and-Conquer Pattern Discovery},
journal = {Computing and Informatics},
volume = {35},
number = {4},
year = {2017},
language = {en},
url = {http://dml.mathdoc.fr/item/cai3377}
}
Tamás Kozsik; Eötvös Loránd University, Budapest; Melinda Tóth; ELTE-Soft Nonprofit Ltd., Budapest; István Bozó; ELTE-Soft Nonprofit Ltd., Budapest; Zoltán Horváth; ELTE-Soft Nonprofit Ltd., Budapest. Static Analysis for Divide-and-Conquer Pattern Discovery. Computing and Informatics, Tome 35 (2017) no. 4, . http://gdmltest.u-ga.fr/item/cai3377/