Static Analysis for Divide-and-Conquer Pattern Discovery

Authors

  • 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

Keywords:

Erlang, divide-and-conquer, pattern, parallelization

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.

Downloads

Download data is not yet available.

Downloads

Published

2017-02-07

How to Cite

Kozsik, T., Tóth, M., Bozó, I., & Horváth, Z. (2017). Static Analysis for Divide-and-Conquer Pattern Discovery. COMPUTING AND INFORMATICS, 35(4), 764–791. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/3377

Issue

Section

Special Section Articles