Dynamic scheduling in application level aware of architecture and data dependencies between tasks.

Modern architectures have multiple processors, each of which contains multiple cores, connected to dedicated memory blocks, featuring NUMA (Non-Uniform Memory Access) architectures. NUMA have different latencies in accessing different blocks of distributed memory. A major challenge is to develop an efficient scheduling to the tasks produced by parallel applications among the available processors by considering the heterogeneity of these memory access times. For this, the scheduler must make decisions influenced by several factors. One of these factors is related to issues of data locality, the decision of allocate a task on a specific processor is an assessment of the costs associated to the access to its data on the asymmetric memory structure. Another factor to be considered is related to the data dependences used by tasks, where heuristics based on list algorithms can be used to scheduling these tasks, in application level, in dynamic execution environments. In this work, we designed a dynamic scheduling strategy for parallel applications on NUMA architectures. This strategy was validated by a series of experiments, where it was possible to assess its performance by comparing it against other tools that employ scheduling on application level. The aim of the strategy was reduced the impact, when executing parallel aplications, of the different latencies arising from the physical distribution of memory modules in NUMA architectures. This work resulted in an extension of the Anahy execution core, which now comprise the proposed strategy, considering, at the time of scheduling, the heterogeneous characteristics of the architecture where the application is running. The results show that the proposed strategy improved the quality of Anahy scheduling on NUMA architectures, contributing to the increased performance of this environment. Compared to other tools, the proposed strategy proved compatible.Sem bolsaAs arquiteturas modernas apresentam múltiplos processadores, compostos por vários núcleos e blocos de memória dedicados, caracterizando as arquiteturas NUMA (Non-Uniform Memory Access). NUMA têm como característica as diferentes latências no acesso aos diferentes blocos de memória. Um dos grandes desafios é o desenvolvimento de técnicas eficientes para o escalonamento das tarefas produzidas pelas aplicações paralelas entre os processadores disponíveis, considerando a heterogeneidade desses tempos de acesso à memória. Para tal, o escalonador deve tomar decisões influenciadas por diversos fatores. Um destes fatores diz respeito à questões de localidade dos dados, a decisão de alocar uma tarefa sobre um processador específico passa pela análise dos custos associados ao acesso aos seus dados na estrutura assimétrica de memória. Um outro fator está relacionado às dependências de dados utilizados pelas tarefas, onde heurísticas baseadas em algoritmos de lista podem ser utilizadas para realizar o escalonamento, em nível aplicativo, em ambientes de execução dinâmicos. Neste trabalho, foi concebida uma estratégia de escalonamento dinâmico para aplicações paralelas em arquiteturas NUMA. Esta estratégia foi validada com a realização de uma série de experimentos, onde foi possível aferir o seu desempenho comparando-a com outras ferramentas que empregam escalonamento em nível aplicativo. O objetivo da estratégia desenvolvida foi buscar reduzir o impacto, na execução de aplicações paralelas, das diferentes latências oriundas da distribuição física dos módulos de memória das arquiteturas NUMA. Este trabalho resultou em uma extensão do núcleo de execução do ambiente Anahy, o qual passou a comportar a estratégia proposta, considerando, no momento do escalonamento, as características heterogêneas da arquitetura onde a aplicação está executando. Os resultados obtidos comprovam que a qualidade do escalonamento de Anahy em arquiteturas NUMA melhorou, contribuindo com o aumento de desempenho do ambiente. A estratégia desenvolvida apresentou resultados de desempenho compatíveis com as demais ferramentas