Automatic Optimization of Granularity Control Algorithms for Parallel Programs
Authors
Abstract
In the last two decades, processors have changed from a single-core to a multi-core design, due to physical constrains in chip manufacturing. Furthermore, GPUs have become suitable targets for general purpose programming. This change in hardware design has had an impact on software development, resulting in a growing investment in parallel programming and parallelization tools.Writing parallel programs is di cult and error prone. Two of the main problems in parallelization are the identi cation of which sections of the code can be safely parallelized and how to efficiently partition work. Automatic parallelization techniques can save programmers time identifying parallelism. In parallelization, each parallelizable section is denoted as a task, and a program is comprised of sev- eral tasks with dependencies among them. Work partition consists in deciding how many tasks will be created for a given parallel workload, thus de ning the task granularity. Current techniques focus solely on loop and recursive parallelization, neglecting possible fine-grained task-level parallelism. However, if the granularity is too fine, penalizing scheduling overheads may be incurred. On the other hand, if the granularity is too coarse, there may not be enough parallelism in the program to occupy all processor cores. The ideal granularity of a program is in uenced by its nature and the available resources. Our experiments have shown that a program that terminates within seconds with the correct granularity may execute for days with an unsuitable granularity. Finding the best granularity is not trivial, more so in the case of automatic parallelization, in which there is no knowledge of the program domain. The current approach consists in empirically evaluating several alternatives to find the optimal granularity.
This thesis proposes a more e cient model for automatic parallelization, in which parallelism is identi ed at the Abstract Syntax Tree (AST) node level. Static analysis is used to obtain access permissions, representations of how an AST node interacts with others in terms of memory accesses and control-flow. Parallelism at the AST node level is very ne grained and may generate more tasks than those that can be executed simultaneously, resulting in scheduling overheads. In order to reduce these overheads, tasks may be merged in coarser tasks, thus reducing par- allelism. A cost-model is proposed to dynamically adjust granularity according to the complexity of tasks, resulting in programs more e cient than the best existing alternative.
Because the automatic parallelization model can generate programs that can execute either on the CPU or the GPU, it is important to automatically decide if a program should execute on the CPU with a coarse granularity, or on the GPU with a finer granularity. To perform this decision, a Machine Learning approach was built, based on static compiler-obtained and runtime features. This model performed program classification with over 95% of accuracy and a low misclassi cation cost. In order to improve the performance of automatic and manually parallelized programs, new dynamic granularity algorithms are proposed for runtime aggrega- tion of tasks. The proposed algorithms extend the state of the art by taking into consideration the usage of the number of stack frames and machine occupation, as well as using a cost-model-based prediction of the task execution time. The existing and proposed algorithms have been evaluated in both time and energy consumed, as well as number of programs completed within reasonable time. Considering both time and energy, the proposed algorithms outperformed existing ones, but no algorithm performed better than any other in all benchmark programs. These results demonstrate the importance of using the right algorithm for an individual program. An evolutionary algorithm was used to generate a global best granularity algorithm for a set of target programs. While improvements were not generalized to a larger set of programs, the evolutionary algorithm can be used to improve the execution time within 10 to 20 generations.
To avoid an exhaustive search for the best granularity algorithm for each program, this thesis proposes both a ruleset and the usage of machine-learning classi ers over program features. The ruleset was obtained from the empirical evaluation of different alternatives on a selected benchmark suite. Both approaches can be used by compilers or programmers to select the granularity algorithm for each program. In a real-world benchmark suite, the ruleset has shown to outperform classifiers, but on an unseen larger synthetic benchmark suite, a misclassification-weighted Random Forest was able to achieve better results than the ruleset.
Overall, this thesis proposes new approaches for automatic parallelization and granularity control that improve the performance of programs.