Automatic Optimization of Granularity Control Algorithms for Parallel Programs

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 difficult and error prone. Two of the main problems in parallelization are the identification of which sections of the code can be safely parallelized and efficient work partitioning. Automatic parallelization can save programmers time in the identification of 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. However, current techniques focus solely on loop and recursive parallelization, neglecting possible fine-grained task-level parallelism. 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. This search has been done manually through guided empirical evaluation of several alternatives.

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 both in terms of memory accesses (reads and writes) and control-flow. Access permissions are used to identify as many tasks as possible while preserving the program semantics. Parallelism at the AST node level is very fine grained and it may generate more tasks than the processor can execute simultaneously, resulting in scheduling overheads. In order to reduce these overheads, tasks may be merged in coarser tasks, thus reducing parallelism. Task aggregation can be performed statically or dynamically. Static aggregation is performed by the compiler and consists in merging tasks that have are considered too small with respect to a custom threshold. Dynamic aggregation may occur during program execution immediately before the execution of each task, thus having the advantage of using runtime data to make a more informed decision.

In order to improve the performance of automatic and manually parallelized programs, new dynamic granularity algorithms are proposed for runtime aggregation of tasks. The proposed algorithms are based on the usage of the number of stack frames, machine occupation or on a cost-model-based prediction of the task execution time. Proposed and existing algorithms are evaluated in both time and energy consumed, as well as number of programs completed within reasonable time. Considering both time and energy, proposed algorithms outperformed existing ones, but no algorithm performed better than any other in all benchmark programs. Thus, it is important to choose the right algorithm for each individual program.

To avoid an exhaustive search for the best granularity algorithm for each program, this thesis proposes a simple ruleset based on the program characteristics. The ruleset can be used by compilers or programmers to choose the ideal granularity algorithm for each program. This ruleset was obtained from the empirical evidence of a selected benchmark set. In a larger benchmark set, the usage of the ruleset was shown to have a lower penalty than always selecting the global best algorithm or than using machine-learning classifiers on the same characteristics.

Additionally, 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 find a reasonable good granularity algorithm within 10 to 20 generations.

Given their massive parallelism capabilities, GPUs are a suitable target for fine grained parallelism. The machine-learning techniques developed for granularity algorithm selection have been applied and extended to the decision between scheduling a task to the CPU or to subdivide it for the GPU. This model performed program classification with a 92\% accuracy and a low misclassification cost.

----------------------------------------------------------

Nas duas últimas décadas, os processadores têm mudado de um design com um núcleo único para multi-núcleo, devido a restrições físicas no processo de fabrico. Esta decisão a nível de hardware teve grande impacto no desenvolvimento de software, resultando num crescente investimento em programação paralela e ferramentas para paralelização.

Escrever programas paralelos é difícil e os dois dos principais problemas são a identificação de paralelismo e a divisão de trabalho. Apesar dos avanços em paralelização automática, a identificação de partes do programa que possam ser executadas ao mesmo tempo que outras ainda é feito manualmente pelo programador. O principal motivo é que a paralelização automática não consegue alcançar os mesmos resultados que a manual, porque não usa todas as estratégias possíveis e não considera a granularidade das tarefas. Tarefas são representações abstractas de sequências de instruções que podem executar em paralelo com outras sequências. A granularidade de tarefas refere-se a quantas tarefas são criadas para executar um certo trabalho, e tem um grande impacto na performance do programa. Se a granularidade for muito fina, o programa tem muito overhead em tarefas de escalonamento. Se a granularidade for muito grossa, o programa não vai usar todos os recursos que tem para fazer o programa mais rápido. A granularidade ideal depende do programa. Um programa que demore segundos com a granularidade certa pode demorar dias com uma granularidade não ideal. Encontrar esta granularidade certa não é trivial, especialmente no caso da paralelização automática em que o humano não está presente, precisando de uma avaliação empírica de várias possibilidades.

Esta tese aborda a problemática de uma paralelização automática e eficiente, propondo um modelo baseado na inferência de permissões de acesso. Permissões de acesso descrevem como é que um nó da árvore de sintaxe abstracta (AST) interage com outros nós tanto em termos de leitura e escrita de memória, como em fluxo de controlo. Permissões de acesso são usadas para isolar o máximo de tarefas que possam ser executadas em paralelo, mantendo a semântica do programa. Ao contrário de abordagens existentes que se focam em paralelismo em ciclos, este modelo conseguem extrair paralelismo em qualquer nó da AST. Após a identificação de tarefas com a maior granularidade possível, é necessário adaptar o paralelismo ao hardware, reduzindo os custos acrescidos e melhorando a performance do programa final. Para reduzir a granularidade é usado um método híbrido que consiste de agregação de tarefas tanto ao nível estático como dinâmico. A agregação estática é feita durante a compilação e junta tarefas que seja demasiado pequenas, de acordo com um valor pré-definido, e que iriam prejudicar o desempenho do programa. A agregação dinâmica atrasa a decisão de juntar tarefas até ao momento em que precise de ser feita, permitindo que informação do estado do sistema seja usada.

Existem várias alternativas para algoritmos de controlo de granularidade dinâmicos, tanto baseados na profundidade da recursividade como no número de tarefas alocadas a cada núcleo. Estes algoritmos foram avaliados juntamente com novos algoritmos que tinham em conta o número de pilhas de recursividade, a ocupação da máquina ou uma previsão do custo da tarefas, baseado em análise estática. Esta avaliação foi feita em termos de tempo e energia consumida, bem como programas completados em tempo razoável. Nenhum algoritmo foi superior a todos os outros em todos os programas. Tendo conta este facto, foi desenhada uma regra de escolha de algoritmo baseada nestes dados, que foi comparada com classificadores baseados em aprendizagem computacional. Outra abordagem seguida foi o uso de um algoritmo evolucionário para testar a hipótese de que seria possível evoluir um algoritmo de granularidade artificial que consiga uma boa performance global a qualquer programa, e evoluir um algoritmo que seja o melhor num programa apenas. Finalmente, as técnicas de aprendizagem computacional usadas na previsão de algoritmos foram modificadas para escolher entre dois níveis de granularidade: uma granularidade grossa no CPU ou granularidade fina na GPU.

O modelo de paralelização automática proposto conseguiu obter melhor performance que a alternativa do estado da arte. A agregação de tarefas estática foi capaz de melhorar a performance comparado com não agregar. A agregação dinâmica melhorou ainda mais os resultados da estática. O algoritmo de controlo de granularidade baseado num modelo de custo conseguiu, em alguns casos, melhorar a performance escolhida por um especialista. Em termos de energia, a conclusão é que a eficiência energética dos algoritmos de controlo de granularidade não é constante, e que o algoritmo mais rápido pode não ser o mais eficiente. A regra para escolha de algoritmo de granularidade foi capaz de produzir programas mais rápidos do que usar sempre o algoritmo mais rápido e do que classificadores de aprendizagem computacional. O algoritmo evolucionário não foi capaz de encontrar um algoritmo melhor em qualquer programa, mas foi capaz de evoluir um algoritmo em concreto para cada programa individualmente entre 10 a 20 gerações. Finalmente, o modelo de aprendizagem computacional para escolha entre CPU e GPU teve 92\% de eficácia, com um baixo custo de classificação errada.

Durante as últimas duas décadas, o design dos processadores mudou de um único núcleo para multicore, devido a limitações físicas no processo de fabrico. Para além disso, GPUs têm também sido usadas para programas generalistas e não só de aplicações gráficas. Esta mudança em design de hardware tem tido um impacto grande no desenvolvimento de software, resultando num investimento crescente em programação paralela e ferramentas para tal. Escrever programas paralelos é difícil e sujeitável a erros. Dois dos principais problemas em paralelização são a identificação de secções de código que podem ser executas em paralelo sem causar erros, e como dividir o trabalho eficientemente. Técnicas de paralelização automática podem poupar tempo aos programadores na identificação de paralelismo. Em paralelização, cada secção que corre em paralelo é chamada de tarefa, e um programa é composto por diferentes tarefas com dependências entre elas. Partição de trabalho consiste em decidir quantas tarefas vão ser criadas para um determinado trabalho, definindo a granularidade de tarefas. As técnicas actuais focam-se em paralelização automática de ciclos e recursividade, ignorando paralelismo fino ao nível da tarefa. No entanto, com uma granularidade demasiado fina, existem custos no escalonamento de tarefas. Mas se a granularidade for demasiado grossa, pode não existir paralelismo para ocupar todos os nú- cleos do processador. A granularidade ideal para um programa é influenciada pela sua natureza e pelos recursos disponíveis. Nas nossas experiências, um programa que termine em segundos com a granularidade certa, pode demorar dias com uma granularidade menos própria. Encontrar a granularidade ideal não é trivial, especialmente em casos de paralelização automática, em que não existe conhecimento do domínio do programa. A abordagem actual consiste em empiricamente avaliar diferentes alternativas. Esta tese propõe um modelo de paralelização automática mais eficiente, em que o paralelismo é identificado ao nível dos nós da Árvore de Sintaxe Abstracta (AST). Análise estática é usada para obter access permissions, representações de como os nós interagem com outros em termos de acessos de memória e fluxo de controlo. Paralelismo a este nível é muito fino e pode executar mais tarefas do que as que podem ser executadas eficientemente em paralelo. Para reduzir os overheads causados, tarefas podem ser agregadas em tarefas maiores, reduzindo o paralelismo. Um modelo de custo é proposto para ajustar dinamicamente a granularidade de acordo com a complexidade das tarefas, resultando em programas mais eficientes do que com as alternativas actuais. Como este modelo pode gerar programas que podem executar na GPU ou no CPU, é importante tomar a decisão em que plataforma correr. Um programa com uma granularidade mais grossa deve executar na CPU, enquanto um programa com a granularidade mais fina pode executar na GPU. Para fazer esta decisão, é proposta uma abordagem de Machine Learning, baseado em análise estática e em features obtidas pelo Runtime. Este modelo conseguiu uma precisão de 95% e um baixo custo de classificação errada. Para melhorar a performance de programas paralelos, tanto manuais como automáticos, são propostos novos algoritmos de controlo de granularidade para agregação de tarefas pelo Runtime. Os algoritmos propostos estendem o estado da arte tendo em conta o uso de stack frames e ocupação da máquina. Os algoritmos existentes e propostos foram todos avaliados tanto a nível de tempo de execução, como de energia consumida, bem como número de programas terminados num determinado tempo. Considerado tempo e energia, os algoritmos propostos conseguiram ser melhores que os existentes, mas nenhum algoritmos conseguiu ser melhor que todos os outros em todos os programas testados. Estes resultados demostram como é importante escolher o algoritmo ideal para cada programa. Um algoritmo evolucionário é também proposto para gerar um melhor algoritmo de granularidade para um conjunto de programas alvo. Apesar das melhorias não serem generalizáveis para um conjunto maior de programas, o algoritmo evolucionário pode ser usado para melhorar o tempo de execução entre 10 a 20 gerações. Para evitar uma pesquisa exaustiva pelo melhor algoritmo de granularidade para cada programa, são propostos um conjunto de regras e classificadores de MachineLearning. O conjunto de regras foi obtido através da análise empírica de diferentes algoritmos num conjunto de programas. Ambas as abordagens podem ser usadas por compiladores ou programadores para escolher o algoritmo de granularidade para cada programa. Num conjunto de programas reais, o conjunto de regras mostrou melhores resultados que os classificadores. Em novos programas criados sinteticamente, um classificador Random Forest, usando pesos baseados no custo de classificação errada, obteve resultados melhores que o ruleset. Resumindo, esta tese propõe novas abordagens para paralelização automática e controlo de granularidade que podem melhorar a performance de programas.