BinLPT: a workload-aware parallel loop scheduler for large-scale multicore platforms

Abstract

A comunidade de Computação de Alto Desempenho investiga soluções eficientes e escaláveis, visando suprir as demandas computacionais de aplicações larga-escala. Para tanto, particularidades da aplicação e plataforma alvos são exploradas, de forma que técnicas específicas possam ser aplicadas. Nesse contexto, a irregularidade da aplicação é uma importante característica que deve ser considerada, por exemplo, no escalonamento de iterações de laços. Nesse cenário, estratégias cientes da carga de trabalho destacam-se como a abordagem mais promissora, no entanto elas apresentam algumas fraquezas que devem ser superadas. Primeiro, elas baseiam-se em técnicas de profiling e regressão estatística, sendo portanto inerentemente projetadas para cargas de trabalho com padrão bem definido. Segundo, essas estratégias falham em aplicar seu conhecimento para escalonar os chunks de iterações do laço paralelo alvo. Terceiro, estratégias existentes não foram avaliadas de maneira compreensiva quanto a variações na carga de trabalho. Finalmente, apesar de existirem diversas estratégias cientes da carga de trabalho, nenhuma delas está integrada a uma biblioteca de programação paralela, tornando assim ainda mais desafiador que aplicações beneficiem-se das mesmas. Com o objetivo de endereçar esses problemas, nesse trabalho propõe-se uma nova estratégia de escalonamento de laços ciente da carga de trabalho batizada de BinLPT. Para possibilitar desempenho e flexibilidade superiores, essa estratégia é baseada em algumas características como estimativas da carga de trabalho fornecidas pelo usuário e o uso de uma heurística de escalonamento adaptativa baseada na regra lpt. Além disso, o BinLPT foi integrado no OpenMP e disponibilizado publicamente para download. Essa nova estratégia foi concebida com base em dois pontos, ambos desenvolvidos durante a elaboração dessa dissertação: uma metodologia de projeto para novas estratégias de escalonamento de laços baseado em simulação; e uma estratégia prova de conceito, nomeada SRR. Uma avaliação compreensiva do BinLPT foi efetuada, utilizando simulações, benchmarks sintéticos e kernels de aplicações, com diversas cargas de trabalho. Os experimentos foram executadas em uma plataforma NUMA e os resultados com os kernels de aplicações relevaram que BinLPT conduz a um desempenho de até 64.92% superior que estratégias do OpenMP consideradas.

Abstract : The High Performance Computing community seeks for efficient and scalable solutions to meet the ever-increasing performance demands in large-scale applications. To achieve this goal, intricacies of the target application and platform are often exploited, so that specific techniques can be applied. In this context, the irregularity of the application is an important characteristic that should be considered. For instance, when scheduling loop iterations of a shared-memory-based applications, workload-aware scheduling strategies stands out as the most promising approach. Unfortunately, existing strategies that are based on this finding present several drawbacks that should be overcome. First, these strategies rely on profiling and statistical regression techniques, and thus are inherently designed to well-behaved workloads. Second, workload-aware strategies fail to apply their knowledge about the underlying workload of the target irregular loop when scheduling chunks of iterations. Third, existing strategies were not so far comprehensively evaluated in what concerns variations in the workload. Finally, despite the existence of several workload-aware strategies, none of them is integrated in a publicly available library for parallel programming, hence making it harder for applications to effectively get benefit from them. To address these challenges, in this work we propose a novel workload-aware loop scheduling strategy called BinLPT. To enable superior performance and flexibility, our strategy is based on some features as user-supplied estimation about the workload of the target irregular loop and the use of an adaptive scheduling heuristic based on the LPT rule. We integrated BinLPT into OpenMP, and we made our implementation publicly available. To conceive BinLPT, we relied on two cornerstones, both devised during the preparation of this master thesis: a simulation-guided design methodology and on a proof-of-concept workload-aware loop scheduler, named SRR. We carried out a throughout assessment of BinLPT using simulations, synthetic kernels and application kernels. We ran experiments on a large-scale NUMA machine and we studied the different workloads. In the application kernels, our experimental results uncovered up to 64.91% of performance improvement when using BinLPT, in contrast to OpenMP strategies.