- author = "Alcides Miguel Cachulo Aguiar Fonseca",
- title = "Automatic Optimization of Granularity Control Algorithms for Parallel Programs",
- school = "Department of Informatics Engineering, University of Coimbra",
- year = "2016",
- address = "Portugal",
- month = sep,
- keywords = "genetic algorithms, genetic programming, automatic parallelisation, compilers, concurrency, work-stealing, optimisation, parallel programming, granularity, machine learning",
-
URL = "
https://old.cisuc.uc.pt/publication/show/5104",
-
URL = "
https://estudogeral.uc.pt/bitstream/10316/32304/3/Automatic%20Optimization%20of%20Granularity%20Control%20Algorithms%20for%20Parallel%20Programs.pdf",
- size = "156 pages",
-
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 parallelisation
tools.
Writing parallel programs is difficult and error prone. Two of the main problems in parallelization are the identification of which sections of the code can be safely parallelised 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 several tasks with dependencies among them. Work partition consists in deciding how many tasks will be created for a given parallel workload, thus defining 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 influenced 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 efficient model for automatic parallelization, in which parallelism is identified 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 fine 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 parallelism. A cost-model is proposed to dynamically adjust granularity according to the complexity of tasks, resulting in programs more efficient 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 95percent of accuracy and a low misclassification cost.
In order to improve the performance of automatic and manually parallelised programs, new dynamic granularity algorithms are proposed for runtime aggregation 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 classifiers 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.",
-
notes = "Brief mention of GP.
SFRH/BD/84448/2012
Supervisor: Bruno Cabral",
