Automatic Parallelization of Canonical Loops

Autores: Leonardo Luiz Padovani da Mata

This paper presents a compilation technique that performs automatic parallelization of canonical loops. Canonical loops are a recurring pattern observed in many well known algorithms, such as frequent itemset, K-means and K nearest neighbors. Automatic parallelization allows application developers to focus on the algorithmic details of the problem they are solving, leaving for the compiler the task of generating correct and efficient parallel code. Our method splits tasks and data among stream processing elements and uses a novel technique based on labeled-streams to minimize the communication between filters. Experiments performed on a cluster of 36 computers indicate that, for the three algorithms mentioned above, our method produces code that scales linearly on the number of available processors. These experiments also show that the automatically generated code is competitive when compared to hand tuned programs.

Published Paper in SBLP2009

This work compiles code using a compiler based in Cetus Compiler Infrastructure. The parallel code generated runs in the Anthill Framework

Algorithms used in this project:

Sml version.

Original C code version.

Compiled for anthill version.

Hand-crafted version.