Orientadores: Guido Costa Souza de Araújo, Alexandro José Baldassin e José Nelson AmaralDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: A correta alocação de threads e páginas de memória em nós de computadores de uma arquitetura NUMA (Non-Uniform Memory Access), visando igualar a demanda por acessos remotos com a disponibilidade de banda de comunicação entre os nós, pode ter um impacto significativo no tempo de execução de programas. Tipicamente, esta alocação deve atender quatro objetivos simultaneamente: (a) manter threads próximas às páginas que elas acessam; (b) distribuir a carga de trabalho de maneira uniforme entre todos os nós; (c) manter a demanda à memória abaixo da banda suportada pelo controlador de memória de cada nó; e (d) realocar threads e páginas de memória de acordo com alterações nos padrões de acesso do programa. A maioria das soluções existentes para o problema de distribuição de threads e páginas em máquinas NUMA concentra-se somente em um subconjunto destas metas, principalmente devido à complexidade das soluções requeridas e à sobrecarga resultante da implementação. Este trabalho propõe o algoritmo PTB, uma heurística que busca simultaneamente alocar (P)áginas, (T)hreads e (B)anda por todos os nós de uma arquitetura NUMA. Ao contrário de abordagens alternativas, a solução integrada PTB procura, ao mesmo tempo, distribuir o trabalho de maneira uniforme entre todos os nós e limitar a demanda aos controladores de memória de cada nó. Além disso, o algoritmo aborda questões de assimetria presentes na infraestrutura de comunicação de máquinas NUMA modernas. Resultados experimentais utilizando benchmarks das suítes Parsec, NAS e Metis revelam que PTB produz média geométrica de speedup 1.16x em relação ao escalonador padrão do Linux. Além disso, para um grande conjunto de programas, PTB produz speedups entre 1.6x e 2.0x, enquanto a solução para balanceamento NUMA do Linux mantém-se abaixo de 1.2x ou até mesmo os desaceleraAbstract: In a NUMA machine, a program¿s execution time can be significantly impacted by how data and tasks are distributed between nodes. Thus, correctly assigning threads and memory pages is paramount. The correct assignment should match the demand for remote data transfers with the available communication bandwidth and memory controller capacity. Such assignment typically requires dealing with four simultaneous goals: (a) keep threads close to the memory pages they access; (b) evenly distribute the workload among nodes; (c) maintain memory demand below memory controllers¿ bandwidth; and (d) reassign threads and pages to follow changes in the memory access pattern of the program. However, most solutions to this problem address only a subset of these goals, mainly because they seek to avoid complex solutions or expensive implementation overheads. This work proposes PTB, a heuristic-based algorithm that simultaneously allocates (P)ages, (T)hreads and (B)andwidth to each node of a NUMA architecture. In contrast to alternative approaches, PTB integrated solution seeks both to uniformly distribute workload and to limit memory demand to the controllers¿ bandwidth while also addressing asymmetry issues found in the communication paths of modern NUMA architectures. Experimental results using Parsec, NAS and Metis benchmarks reveal that PTB produces geometric mean speedups of 1.16x when compared to Linux¿s default scheduler. In particular, for a number of programs, PTB speedups ranged from 1.6x to 2x while Linux¿s automatic NUMA balancing either stayed below 1.2x. or resulted in slowdownsMestradoCiência da ComputaçãoMestre em Ciência da Computação2014/15523-1, 2015/12187-3FAPESPCAPES