Balanceamento de Carga ciente da topologia de máquina para a portabilidade de desempenho em plataformas de alto desempenho paralelas

This thesis presents our research to provide performance portability and scalability to complex scientific applications running over hierarchical multicore parallel platforms. Performance portability is said to be attained when a low core idleness is achieved while mapping a given application to different platforms, and can be affected by performance problems such as load imbalance and costly communications, and overheads coming from the task mapping algorithm. Load imbalance is a result of irregular and dynamic load behaviors, where the amount of work to be processed varies depending on the task and the step of the simulation. Meanwhile, costly communications are caused by a task distribution that does not take into account the different communication times present in a hierarchical platform. This includes nonuniform and asymmetric communication costs at memory and network levels. Lastly, task mapping overheads come from the execution time of the task mapping algorithm trying to mitigate load imbalance and costly communications, and from the migration of tasks. Our approach to achieve the goal of performance portability is based on the hypothesis that precise machine topology information can help task mapping algorithms in their decisions. In this context, we proposed a generic machine topology model of parallel platforms composed of one or more multicore compute nodes. It includes profiled latencies and bandwidths at memory and network levels, and highlights asymmetries and nonuniformity at both levels. This information is employed by our three proposed topology-aware load balancing algorithms, named NUCOLB, HWTOPOLB, and HIERARCHICALLB. Besides topology information, these algorithms also employ application information gathered during runtime. NUCOLB focuses on the nonuniform aspects of parallel platforms, while HWTOPOLB considers the whole hierarchy in its decisions, and HIERARCHICALLB combines these algorithms hierarchically to reduce its task mapping overhead. These algorithms seek to mitigate load imbalance and costly communications while averting task migration overheads. Experimental results with the proposed load balancers over different platform composed of one or more multicore compute nodes showed performance improvements over state of the art load balancing algorithms: NUCOLB presented improvements of up to 19% on one compute node; HWTOPOLB experienced performance improvements of 19% on average; and HIERARCHICALLB outperformed HWTOPOLB by 22% on average on parallel platforms with ten or more compute nodes. These results were achieved by equalizing work among the available resources, reducing the communication costs experienced by applications, and by keeping load balancing overheads low. In this sense, our load balancing algorithms provide performance portability to scientific applications while being independent from application and system architecture.Esta tese apresenta nossa pesquisa para prover portabilidade de desempenho e escalabilidade para aplicações científicas complexas executadas em plataformas multicore paralelas e hierárquicas. A portabilidade de desempenho é dita como alcançada quando uma pequena ociosidade nas unidades de processamento é obtida para o mapeamento de uma aplicação em diferentes plataformas. A portabilidade de desempenho pode ser afetada por problemas como o desbalanceamento de carga, comunicações custosas e sobrecustos vindos do algoritmo de mapeamento de tarefas. O desbalanceamento de carga é um resultado de comportamentos de cargas de tarefas irregulares e dinâmicas, onde a quantidade de trabalho a ser processado varia dependendo da tarefa e da etapa da simulação. Enquanto isso, comunicações custosas são causadas por uma distribuição de tarefas que não leva em conta os diferentes tempos de comunicações presentes em uma plataforma hierárquica. Isto inclui custos de comunicações não uniformes e assimétricos em níveis de memória e rede. Por fim, os sobrecustos de mapeamento de tarefas vêm do tempo de execução do algoritmo de mapeamento de tarefas tentando mitigar o desbalanceamento de carga e comunicações custosas, além do tempo ligado à migração de tarefas. Nossa abordagem para atingir o objetivo de portabilidade de desempenho é baseada na hipótese de que informações precisas da topologia de máquina podem auxiliar algoritmos de mapeamento em suas decisões. Neste contexto, nós propomos um modelo de topologia de máquina genérico para plataformas paralelas compostas de um ou mais nós de processamento multicore. Ele inclui latências e larguras de banda perfiladas nos níveis de memória e rede, além de salientar assimetrias e não uniformidade em ambos níveis. Estas informações são empregadas pelos nossos três algoritmos de balanceamento de carga cientes da topologia de máquina propostos, chamados NUCOLB, HWTOPOLB e HIERARCHICALLB. Além das informações da topologia, estes algoritmos também utilizam informações da aplicação capturadas durante o tempo de execução. NUCOLB foca nos aspectos não uniformes de plataformas paralelas, enquanto HWTOPOLB considera toda a hierarquia da máquina em suas decisões. HIERARCHICALLB combina estes algoritmos hierarquicamente para reduzir seu sobrecusto de mapeamento de tarefas. Estes algoritmos buscam mitigar o desbalanceamento de carga e comunicações custosas enquanto evitam sobrecustos de migração de tarefas. Resultados experimentais com os balanceadores de carga propostos em diferentes plataformas compostas de um ou mais nós de processamento multicore apresentaram desempenhos superiores a outros algoritmos de balanceamento de carga do estado da arte: NUCOLB apresentou melhorias de até 19% em média; HWTOPOLB demonstrou melhorias de desempenho de 19% em média; e HIERARCHICALLB superou HWTOPOLB em 22% em média em plataformas paralelas com dez ou mais nós de processamento. Estes resultados foram obtidos através da equalização da carga de trabalho entre os recursos disponíveis, redução dos custos de comunicação sentidos pelas aplicações e manutenção de sobrecustos de balanceamento de carga pequenos. Dessa forma, nossos algoritmos de balanceamento de carga proveem portabilidade de desempenho para aplicações científicas enquanto se mantendo independentes de uma aplicação ou arquitetura de sistema específica