Abstract
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.
Keywords
MSC
68-N19
Cite this article
@article{cai-3377,
author = {Tamás Kozsik and Melinda Tóth and István Bozó and Zoltán Horváth},
title = {Static Analysis for Divide-and-Conquer Pattern Discovery},
journal = {Computing and Informatics},
volume = {35},
number = {4},
pages = {764--791},
year = {2016},
issn = {1335-9150},
url = {https://cai.type.sk/content/2016/4/static-analysis-for-divide-and-conquer-pattern-discovery/}
}
TY - JOUR AU - Tamás Kozsik AU - Melinda Tóth AU - István Bozó AU - Zoltán Horváth TI - Static Analysis for Divide-and-Conquer Pattern Discovery JO - Computing and Informatics VL - 35 IS - 4 SP - 764 EP - 791 PY - 2016 SN - 1335-9150 UR - https://cai.type.sk/content/2016/4/static-analysis-for-divide-and-conquer-pattern-discovery/ KW - Erlang KW - divide-and-conquer KW - pattern KW - parallelization ER -
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. https://cai.type.sk/content/2016/4/static-analysis-for-divide-and-conquer-pattern-discovery/