info.info-dc
Pedro H Penna 
email: pedro.penna@sga.pucminas.br
  
Márcio Castro 
email: marcio.castro@ufsc.br
  
Henrique C Freitas 
  
Franc ¸ois Broquedis 
email: francois.broquedis@imag.fr
  
Jean-Franc ¸ois Méhaut 
email: jean-francois.mehaut@imag.fr
  
Uma Metodologia Baseada em Simulac ¸ão e Algoritmo Genético para Explorac ¸ão de Estratégias de Escalonamento de Lac ¸os

In High Performance Computing, the application's workload must be well balanced among the threads to achieve better performance. In this work, we propose a methodology that enables the design and exploration of new loop scheduling strategies. In this methodology, a simulator is used to evaluate the most relevant existing scheduling strategies, and a genetic algorithm is employed to explore the solution space of the problem itself. The proposed methodology allowed us to design a new loop scheduling strategy, which showed to be up to 32.3x better than the existing policies in terms of load balance.

Resumo. Na Computac ¸ão de Alto Desempenho, a carga de trabalho de aplicac ¸ões paralelas deve ser balanceada entre as threads para obtenc ¸ão de um melhor desempenho. Nesse trabalho é proposta uma metodologia que possibilita o projeto e a explorac ¸ão de novas políticas de escalonamento de lac ¸os. Essa metodologia emprega a técnica de simulac ¸ão para estudar as principais estratégias existentes e um algoritmo genético para explorar o espac ¸o de soluc ¸ões do problema. A metodologia proposta auxiliou no projeto de uma nova estratégia de escalonamento de lac ¸os que se mostrou ser até 32.3x melhor em ternos de balanceamento de carga que as políticas existentes.

Introduc ¸ão

De maneira geral, aplicac ¸ões podem ser classificadas em dois grupos: regulares, que se caracterizam pela homogeneidade no tamanho de suas tarefas; e irregulares, que se destacam pela sua heterogeneidade. A multiplicac ¸ão de matrizes é um exemplo de aplicac ¸ão regular, onde as tarefas possuem cargas similares e consistem na multiplicac ¸ão de uma linha de uma matriz pela coluna de outra. Em contrapartida, uma aplicac ¸ão de ordenac ¸ão de inteiros exemplifica a classe de aplicac ¸ões irregulares, com o número de operac ¸ões necessárias para se ordenar um número variando em func ¸ão dos demais.

A diferenc ¸a existente entre essas duas classes é fundamental para o projeto de aplicac ¸ões paralelas eficientes. Nesse contexto, aplicac ¸ões regulares são fortemente apreciadas, pois uma simples divisão de uma carga de trabalho total n entre t threads é suficiente para se obter uma distribuic ¸ão de tarefas homogênea. Infelizmente, essa estratégia não é válida para aplicac ¸ões irregulares, uma vez que as tarefas são heterogêneas em tamanho. Logo, um determinado conjunto de threads poderá apresentar um forte desbalanceamento de carga, fazendo com que o desempenho da aplicac ¸ão fique dominado pela thread mais sobrecarregada.

O problema de balanceamento de carga pode ser estudado em diferentes granularidades [Patni et al. 2011, Tantawi and[START_REF] Tantawi | Optimal static load balancing in distributed computer systems[END_REF]. Porém, esse problema é estudado no presente trabalho no contexto de escalonamento de lac ¸os (loop scheduling), onde as iterac ¸ões são consideradas como tarefas que devem ser atribuídas às threads. Nessa linha, diferentes estratégias são conhecidas para se enderec ¸ar esse problema [START_REF] Srivastava | Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems[END_REF]. O objetivo do presente trabalho, no entanto, é apresentar uma metodologia que possibilite o projeto e a explorac ¸ão de novas estratégias de escalonamento de lac ¸os, em especial aquelas que levem em considerac ¸ão a característica da carga de trabalho da aplicac ¸ão. A metodologia proposta utiliza a técnica de simulac ¸ão para estudar as principais políticas de escalonamento existentes e um algoritmo genético para explorar o espac ¸o de soluc ¸ões do problema. Por fim, uma nova estratégia, projetada com base nos resultados obtidos com a aplicac ¸ão da metodologia, é proposta para fins de validac ¸ão. Essa estratégia, nomeada Smart Round-Robin (SRR), considera características da carga de trabalho e, então, acaba por se destacar das estratégias existentes. As principais contribuic ¸ões desse trabalho em relac ¸ão ao estado da arte se concentram em: (i) uma proposta da metodologia para estudo de novas estratégias de escalonamento de lac ¸os; (ii) no uso de um algoritmo genético aplicado ao contexto; e (iii) uma proposta de uma nova estratégia de escalonamento de lac ¸os.

O restante do artigo está organizado da seguinte forma. Na Sec ¸ão 2 os principais trabalhos relacionados ao problema de escalonamento de lac ¸os são apresentados. Na Sec ¸ão 3 o problema em questão é discutido formalmente. Na Sec ¸ão 4 a metodologia proposta é apresentada em detalhes. Na Sec ¸ão 5 os resultados obtidos são apresentados e discutidos. Por fim, na Sec ¸ão 6, as conclusões e trabalhos futuros são apresentados.

Trabalhos Relacionados

O escalonamento de lac ¸os é um tema recorrente na área de Computac ¸ão Paralela e de Alto Desempenho. Nesta sec ¸ão são discutidos os principais esforc ¸os em pesquisa nesse assunto que são relevantes para o presente trabalho.

Diversas estratégias para realizar o escalonamento de lac ¸os foram propostas para satisfazer as mais variadas restric ¸ões [START_REF] Hajieskandar | Parallel loop scheduling using an evolutionary algorithm[END_REF][START_REF] Olivier | Openmp task scheduling strategies for multicore numa systems[END_REF][START_REF] Ding | Locality-aware mapping and scheduling for multicores[END_REF][START_REF] Chen | A static scheduling scheme of multicore compiler for loop load imbalance in openmp[END_REF]. No entanto, selecionar estratégias de escalonamento mais adequadas para aplicac ¸ões específicas ainda é um desafio. Objetivando solucionar esse problema, Sukhija et al. propuseram uma abordagem que utiliza técnicas de aprendizado de máquina supervisionado para predizer e escolher a estratégia de escalonamento de lac ¸os mais robusta para uma aplicac ¸ão e plataforma específicos [START_REF] Sukhija | Portfoliobased selection of robust dynamic loop scheduling algorithms using machine learning[END_REF]. Os resultados mostraram que: (i) a abordagem proposta é capaz de selecionar a estratégia de escalonamento mais robusta, que satisfac ¸a uma tolerância especificada pelo usuário; e (ii) a estratégia selecionada usualmente oferece maior robustez do que outra selecionada empiricamente para a mesma aplicac ¸ão.

Seguindo uma linha de pesquisa semelhante, Srivastava et al. propuseram e avaliaram uma rede neural artificial capaz de predizer a flexibilidade de estratégias dinâmicas para o escalonamento de lac ¸os em sistemas heterogêneos [START_REF] Srivastava | Predicting the flexibility of dynamic loop scheduling using an artificial neural network[END_REF]. O modelo proposto utiliza como parâmetros de entrada a quantidade de processadores e suas respectivas disponibilidades, o número de iterac ¸ões no lac ¸o e a func ¸ão de probabilidade dos tempos de execuc ¸ão dessas iterac ¸ões. Três func ¸ões de distribuic ¸ão probabilísticas foram consideradas (gaussiana, gamma e exponencial) e tiveram seus parâmetros variados, totalizando 1.152 exemplos. Os resultados mostraram que o modelo proposto é efetivo na selec ¸ão da estratégia de balanceamento mais robusta, garantindo uma acurácia de 94,9 %.

No que diz respeito à avaliac ¸ão das estratégias de escalonamento existentes, Srivastava et al. propuseram uma metodologia para analisar a robustez de estratégias de escalonamento dinâmico de lac ¸os [START_REF] Srivastava | Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems[END_REF]. Para tanto, os autores implementaram oito estratégias em um simulador e utilizaram uma aplicac ¸ão sintética para avaliá-las. Essa aplicac ¸ão possui n lac ¸os independentes e o tempo de execuc ¸ão de cada iterac ¸ão de um lac ¸o é representado por uma distribuic ¸ão gaussiana. Ao final do estudo, os autores concluíram que a metodologia baseada em simulac ¸ão pode ser aplicada para realizar uma análise das estratégias de balanceamento existentes. Outro trabalho que segue uma metodologia de simulac ¸ão similar é discutido em [START_REF] Balasubramaniam | Towards the scalability of dynamic loop scheduling techniques via discrete event simulation[END_REF].

O presente trabalho se difere dos trabalhos discutidos anteriormente em diferentes aspectos. Em primeiro lugar, ele se concentra em apresentar uma metodologia que possibilite o projeto e a explorac ¸ão de estratégias de escalonamento de lac ¸os, levando em considerac ¸ão a carga de trabalho da aplicac ¸ão. Nessa metodologia, a técnica de simulac ¸ão é empregada para avaliar as principais estratégias de escalonamento existentes e uma técnica de busca é usada para se explorar o espac ¸o de soluc ¸ões do problema. Em segundo lugar, esse trabalho amplia o estudo de aplicac ¸ões sintéticas para 5 diferentes distribuic ¸ões de carga. Finalmente, em terceiro lugar, uma nova estratégia de escalonamento, que se baseia nos resultados da aplicac ¸ão da técnica de explorac ¸ão, é apresentada e comparada com as estratégias existentes, validando assim a metodologia proposta.

O Problema de Escalonamento de Lac ¸os

O problema de escalonamento de lac ¸os é uma instância particular do problema de balanceamento de carga de trabalho e consiste em um problema NP-Completo de minimizac ¸ão que é definido formalmente a seguir [START_REF] Skiena | The Algorithm Design Manual[END_REF]]. Considere um conjunto de n iterac ¸ões T = {t 1 , t 2 , . . . , t n }, em que cada iterac ¸ão t i está associada a um tamanho s i , com

s i ∈ N. Assim, dado um inteiro k ≥ 1, o problema consiste em particionar T em k subconjuntos disjuntos {C 1 , C 2 , . . . , C k } de forma a minimizar a máxima soma s C i = { s i | s i ∈ C i }
dentre os conjuntos e, então, reduzir o grau de desbalanceamento entre partic ¸ões (Equac ¸ão 1):

f (s C i ) = min (max (s C i )), ∀ 1 ≤ i ≤ k (1) 
O número de iterac ¸ões e partic ¸ões constituem variáveis intrínsecas ao problema de escalonamento de lac ¸os e, portanto, não podem ser ignoradas em sua análise. No entanto, quando o objetivo é estudar o problema no contexto de uma aplicac ¸ão real, outras variáveis também devem ser consideradas, o que torna a func ¸ão de minimizac ¸ão apresen-tada multiobjetiva. Nesse segundo cenário, algumas das variáveis que podem ser destacadas são: a carga associada às iterac ¸ões, a frequência em que o escalonamento é realizado e a afinidade de memória existente entre as iterac ¸ões.

A carga associada a cada iterac ¸ão está relacionada à natureza da carga de trabalho da aplicac ¸ão e exerce influência direta na qualidade da soluc ¸ão para o problema. Por exemplo, se a carga das iterac ¸ões seguir uma distribuic ¸ão uniforme, isto é, se a probabilidade de ocorrência de iterac ¸ões com carga muito pequena e muito grande é a mesma, o grau de desbalanceamento (Equac ¸ão 1) observado tende a ser menor. No entanto, para uma distribuic ¸ão não tão regular, esse grau tende a ser mais elevado. A frequência com que o escalonamento de iterac ¸ões é realizado, por sua vez, é importante para algoritmos de escalonamento dinâmico que realizam a atribuic ¸ão de iterac ¸ões em tempo de execuc ¸ão. Nesse contexto, ela dita quantas vezes a estratégia de escalonamento será invocada durante a execuc ¸ão da aplicac ¸ão e, então, impacta diretamente em seu desempenho final. Por fim, a afinidade de memória se relaciona com o nível de localidade espacial e/ou temporal existente entre as iterac ¸ões atribuídas a uma mesma partic ¸ão. Quando as localidades espacial e temporal são altas, há uma melhora significativa na eficiência do sistema de memória como um todo, minimizando contenc ¸ões em barramentos e outras estruturas de interconexão, impactando positivamente no desempenho da aplicac ¸ão.

Metodologia

O presente trabalho tem como principal objetivo apresentar uma metodologia que possibilite o projeto e a explorac ¸ão de novas estratégias de escalonamento de lac ¸os. Nessa metodologia, a técnica de simulac ¸ão é empregada para estudar as principais políticas de escalonamento existentes e um algoritmo genético é usado para se explorar o espac ¸o de soluc ¸ões do problema. Nessa sec ¸ão, essa metodologia é apresentada em detalhes. Inicialmente é feita uma discussão sobre as variáveis consideradas no problema. Em seguida, o ambiente de simulac ¸ão utilizado é apresentado. Por fim, é apresentado o algoritmo genético empregado nesse trabalho.

Variáveis Consideradas

Na Sec ¸ão 3 discutiu-se o problema de escalonamento de lac ¸os e as principais variáveis a ele relacionadas. Algumas dessas variáveis são inerentes ao problema, enquanto outras estão relacionadas às características da aplicac ¸ão ou da plataforma de execuc ¸ão, como a carga associada às iterac ¸ões e a afinidade de memória, respectivamente. Nesse estudo, as seguintes variáveis foram consideradas: (i) número de iterac ¸ões; (ii) número de threads (partic ¸ões); e (iii) a func ¸ão de distribuic ¸ão de carga das iterac ¸ões.

As duas primeiras variáveis (número de iterac ¸ões e threads) constituem a natureza do problema de escalonamento de lac ¸os, sendo portanto consideradas no estudo. A terceira variável está relacionada à característica da aplicac ¸ão e dita qual é a carga associada às iterac ¸ões. Essa variável é também considerada no presente trabalho devido à sua influência no grau de desbalanceamento existente entre as threads e ao seu impacto na qualidade da soluc ¸ão proporcionada pela estratégia de escalonamento adotada.

As demais variáveis discutidas na Sec ¸ão 3 não são consideradas devido a dois motivos principais: (i) ou estão relacionadas a alguma das variáveis já consideradas, como por exemplo a máxima diferenc ¸a entre a carga de duas iterac ¸ões quaisquer, que se correlaciona com a func ¸ão de distribuic ¸ão de carga das iterac ¸ões; ou (ii) são dependentes de plataforma e, portanto, podem ser estudadas em uma etapa posterior, como por exemplo a afinidade de memória existente entre as iterac ¸ões atribuídas a uma mesma thread e sua relac ¸ão com a hierarquia de memória da plataforma considerada.

Simulador

Uma vez definidas as variáveis a serem estudadas, um ambiente para estudo das políticas de escalonamento de lac ¸os existentes se faz necessário. Para tanto, duas alternativas são possíveis: (i) usar uma plataforma real; ou (ii) usar um ambiente simulado. A primeira alternativa possui como principal vantagem possibilitar uma análise de todas as variáveis envolvidas no problema. No entanto, conforme discutido na Sec ¸ão 4.1, algumas dessas variáveis são dependentes de plataforma e de aplicac ¸ão e, uma vez que o presente trabalho se concentra em uma análise teórica do problema, elas podem ser abstraídas. Em contrapartida, o uso de um ambiente simulado possibilita que as variáveis de interesse não só sejam isoladas, como também controladas minuciosamente. Por esse motivo, um simulador foi projetado, desenvolvido e utilizado no presente trabalho. Vale ressaltar que simuladores já existentes reportados em trabalhos relacionados [START_REF] Srivastava | Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems[END_REF][START_REF] Balasubramaniam | Towards the scalability of dynamic loop scheduling techniques via discrete event simulation[END_REF]] não foram utilizados por não estarem disponíveis em domínio público e limitarem a análise de cargas sintéticas a apenas 3 distribuic ¸ões de carga.

A Figura 1 apresenta a arquitetura interna desse simulador, com os seus três módulos principais na parte superior e aplicac ¸ão sintética representada na parte inferior. O módulo gerador de carga sintética recebe como parâmetros o número de iterac ¸ões e a func ¸ão de distribuic ¸ão da carga associada a essas iterac ¸ões, e gera como saída um conjunto de iterac ¸ões com as características especificadas. A carga de uma iterac ¸ão representa o tempo necessário para que ela seja concluída, de forma que conjunto de iterac ¸ões corresponde à carga de trabalho da aplicac ¸ão sintética.

O módulo gerenciador de threads, por sua vez, é responsável por criar e escalonar as threads da aplicac ¸ão sintética. O número de threads criadas depende do parâmetro especificado e o escalonamento de threads é feito segundo uma política round-robin. Para gerenciar as threads, esse módulo mantém duas estruturas: uma fila de prioridades das threads em execuc ¸ão, ordenada pelo tempo de processamento remanescente de cada thread; e uma lista das threads prontas para execuc ¸ão. Por fim, o módulo escalonador de iterac ¸ões realiza, segundo a política de escalonamento especificada, o escalonamento das iterac ¸ões criadas pelo gerador de carga sintética. O escalonador exporta uma interface que possibilita o estudo tanto de estratégias estáticas quanto dinâmicas. Nessa arquitetura, a aplicac ¸ão sintética é responsável por processar linearmente o conjunto de iterac ¸ões gerado, considerando os parâmetros especificados.

Esse simulador está disponível online 1 , o que permite que novas funcionalidades sejam adicionadas para atender a contextos específicos de trabalhos futuros. No entanto, os seguintes recursos já estão disponíveis. Quanto à configurac ¸ão dos parâmetros de entrada, o simulador é capaz de gerar um número arbitrário de iterac ¸ões segundo as distribuic ¸ões beta, gamma, normal, poisson e uniforme. Com relac ¸ão às políticas de escalonamento de iterac ¸ões, o simulador permite a escolha de duas políticas: estática (Static) e dinâmica (Dynamic), ambas presentes no modelo de programac ¸ão OpenMP [START_REF] Dagum | Openmp: An industry standard api for shared-memory programming[END_REF]]. Na primeira estratégia, as iterac ¸ões de um lac ¸o são particionadas estaticamente antes da execuc ¸ão e são atribuídas às threads seguindo uma política round-robin. Já na estratégia Dynamic (também conhecida por Fixed Size Chunk), as iterac ¸ões são particionadas em tempo de execuc ¸ão e são atribuídas sob demanda às threads. Em ambas as estratégias, o tamanho da partic ¸ão (chunk size) é definido de antemão.

Por fim, o simulador desenvolvido é capaz de gerar um trac ¸o detalhado que contém as seguintes informac ¸ões: (i) número de threads simuladas; (ii) quantidade de iterac ¸ões sintéticas geradas; (iii) tamanho de cada iterac ¸ão; (iv) iterac ¸ões atribuídas a cada thread; e (v) carga de trabalho total atribuída a cada thread. Essas informac ¸ões são salvas em um arquivo e podem ser utilizadas posteriormente para se realizar um estudo detalhado da simulac ¸ão, como o apresentado na Sec ¸ão 5.

Algoritmo Genético

O simulador desenvolvido permite que as diferentes políticas de balanceamento de cargas existentes sejam estudadas. No entanto, utilizá-lo de maneira isolada dificulta a identificac ¸ão de políticas alternativas ainda mais eficientes. Uma estratégia adicional, que pode ser adotada em conjunto com a técnica de simulac ¸ão, é a técnica de explorac ¸ão do espac ¸o de soluc ¸ões do problema. Nesse caso, o problema de escalonamento de lac ¸os é encarado como um problema de minimizac ¸ão e um algoritmo de busca heurística é a ele aplicado. Esse algoritmo utiliza a func ¸ão-objetivo de minimizac ¸ão para orientar sua busca e, ao final do processo, encontrar um escalonamento de iterac ¸ões às threads que minimize o valor dessa func ¸ão.

Diferentes algoritmos de buscas heurísticas são conhecidos. Eles consistem em uma ferramenta básica da Inteligência Artificial e são frequentemente aplicados em diferentes domínios da computac ¸ão [START_REF] Coello | A comprehensive survey of evolutionary-based multiobjective optimization techniques[END_REF]]. Nesse trabalho, um algoritmo genético foi utilizado para explorar o universo de soluc ¸ões do problema de escalonamento de lac ¸os. Esse algoritmo foi selecionado por dois principais motivos: (i) tem se mostrado promissor em diferentes outros contextos [START_REF] Konfrst | Parallel genetic algorithms: Advances, computing trends, applications and perspectives[END_REF]]; e (ii) não exige qualquer conhecimento de como novos estados são gerados a partir de um dado estado. A seguir é feita uma apresentac ¸ão do funcionamento desse algoritmo e, então, é apresentada uma discussão de como ele foi adaptado para o contexto estudado.

O Algoritmo 1 apresenta o funcionamento, em linhas gerais, de um algoritmo genético. Esse algoritmo recebe dois parâmetros, o tamanho da populac ¸ão (tampop) e a quantidade de iterac ¸ões (n), e retorna o estado encontrado que possuir o menor valor avaliado pela func ¸ão-objetivo. A ideia básica é evoluir uma populac ¸ão de estados ao longo do tempo segundo a teoria da evoluc ¸ão de Darwin. Para tanto, um conjunto de estados iniciais (pop) é gerado (linha 2). Nesse conjunto, cada estado (organismo) possui duas 1 https://github.com/cart-pucminas/scheduler Algoritmo 1 Descric ¸ão genérica de um algoritmo genético. propriedades: a descric ¸ão do estado (cromossomo), e o valor da func ¸ão-objetivo para aquele estado (fitness). Em seguida, alguns organismos são selecionados para o cruzamento, considerando seu valor de fitness (linhas 6 e 7). Organismos com valor de fitness mais altos possuem uma maior probabilidade de serem selecionados, possuindo assim uma maior chance de que seus genes perpetuem e a qualidade da populac ¸ão aumente com o passar das gerac ¸ões. Organismos selecionados para o cruzamento são, em seguida, escolhidos aleatoriamente para formarem pares, cruzarem, com uma alta probabilidade α, e gerarem novos organismos filhos (linha 9 a 11). Nesse processo, o cromossomo de um novo organismo é criado trocando-se o material genético entre o par de organismos-pai. Assim que um novo organismo é gerado, ele pode sofrer alguma mutac ¸ão em seu cromossomo, usualmente com uma pequena probabilidade β (linha 14). Finalmente, para compor a nova populac ¸ão, alguns organismos da populac ¸ão antiga são escolhidos aleatoriamente para serem substituídos pelos novos organismos gerados (linha 16), e então uma nova gerac ¸ão comec ¸a. Esse processo termina quando um critério de parada é alcanc ¸ado (linha 17).

Para o problema de escalonamento de lac ¸os, o Algoritmo 1 foi adaptado da seguinte forma: cada cromossomo é um vetor que indica o mapeamento das iterac ¸ões às threads e a fitness de cada cromossomo é dada pela func ¸ão-objetivo definida na Sec ¸ão 3. Para criar a populac ¸ão inicial, POPULAC ¸ÃO-INICIAL() gera, aleatoriamente, o cromossomo de cada organismo. Os operadores genéticos foram definidos da seguinte forma:

• SELEC ¸ÃO(): seleciona indivíduos de acordo com o Algoritmo da Roleta [START_REF] Goldberg | A comparative analysis of selection schemes used in genetic algorithms[END_REF]]; • CRUZAMENTO(): gera dois indivíduos e utiliza somente um ponto de corte;

• MUTAC ¸ÃO(): altera, aleatoriamente, o valor de um gene de um cromossomo;

• SUBSTITUIC ¸ÃO(): aplica a técnica de elitismo [START_REF] Bhandari | Genetic algorithm with elitist model and its convergence[END_REF] na populac ¸ão antiga e escolhe aleatoriamente os demais organismos que irão compor a nova populac ¸ão, considerando tanto a populac ¸ão antiga remanescente quanto os novos organismos gerados no processo de cruzamento. 

Discussão de Resultados

Nessa sec ¸ão, são discutidos os resultados obtidos quando a metodologia proposta foi aplicada. Inicialmente, são discutidas as cargas de trabalho, as estratégias de escalonamento consideradas e os parâmetros do algoritmo genético. Em seguida, resultados da convergência do algoritmo genético proposto são apresentados, seguidos pelos resultados de estudo das políticas existentes.

Parâmetros da Metodologia

As cargas de trabalho foram geradas com base em cinco diferentes func ¸ões de distribuic ¸ão probabilística: beta, gamma, normal, poisson e uniforme. A Figura 2 apresenta as distribuic ¸ões e os parâmetros utilizados em cada caso. Para cada uma das cinco cargas de trabalho sintéticas, foram considerados lac ¸os de 128, 256 e 512 iterac ¸ões, totalizando 15 cenários.

Dentre as estratégias de escalonamento existentes, foram utilizadas as estratégias estática (Static) e dinâmica (Dynamic) do OpenMP. Outras estratégias de escalonamento mais robustas são conhecidas [START_REF] Srivastava | Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems[END_REF], no entanto, elas não foram consideradas uma vez que a estratégia Dynamic se equipara a essas técnicas quando utilizada com blocos (chunks) de iterac ¸ões de tamanho fixo ótimo [START_REF] Balasubramaniam | Towards the scalability of dynamic loop scheduling techniques via discrete event simulation[END_REF].

No presente trabalho, ambas as estratégias foram estudadas considerando-se chunks de tamanho 1, 4, 8, 16 e 32. Em todos os cenários o número de threads foi fixado em 32.

Por fim, os seguintes valores para os parâmetros genéticos foram aplicados: 80 % de taxa de cruzamento, 10 % de taxa de mutac ¸ão, 90 % de taxa de substituic ¸ão e 1 % de taxa de elitismo. Além disso, adotou-se como critério de parada do algoritmo genético quando a melhor soluc ¸ão encontrada se estagna por 1.000 iterac ¸ões sucessivas. Esses valores interferem no tempo de convergência do algoritmo e foram estabelecidos de maneira empírica. A Sec ¸ão 5.2 discute o quão adequada foi a escolha desses parâmetros.

Convergência do Algoritmo Genético

Como dito anteriormente, o algoritmo genético proposto explora o espac ¸o de soluc ¸ões do problema buscando minimizar o desbalanceamento de carga existente entre um conjunto de threads (Equac ¸ão 1). A Figura 3 apresenta um exemplo da evoluc ¸ão do algoritmo genético (AG) quando uma carga de 512 iterac ¸ões que seguem a distribuic ¸ão beta é considerada. Partindo de uma soluc ¸ão com um grau de desbalanceamento crítico, o algoritmo gradualmente combina as diferentes soluc ¸ões de sua populac ¸ão até convergir para uma soluc ¸ão que é 9,5 x e 57,6 x melhor que as soluc ¸ões encontradas pelas estratégias Dynamic e Static, respectivamente. Um comportamento similar foi observado para os demais cenários. A convergência do algoritmo genético para os demais cenários pode ser concluída a partir das informac ¸ões compiladas na Tabela 1. Considerando a ¸ão 1, a soluc ¸ão ótima (teórica) para o problema de escalonamento corresponde a atribuir a cada thread uma carga de trabalho igual a carga de trabalho total dividida pelo número de threads. Nesse caso, a carga de trabalho atribuída a cada thread será a mesma e o desvio padrão relativo observado na carga média de trabalho atribuída será igual a zero. Nos experimentos realizados, o algoritmo genético encontrou, em todos os cenários considerados, uma soluc ¸ão em que a carga de trabalho média atribuída às threads coincide com a carga média da soluc ¸ão ótima. No entanto, o desvio padrão relativo observado variou de 0,22 % a 12,53 %, ficando sempre abaixo de 5 % em 12 de 15 casos. Esses resultados apontam dois fatos. Em primeiro lugar, o algoritmo genético proposto converge para uma soluc ¸ão próxima da ótima, validando então seu uso no estudo do problema de escalonamento de lac ¸os. Em segundo lugar, estratégias de escalonamento podem fazer uso dessas informac ¸ões para alcanc ¸ar soluc ¸ões ainda mais eficientes.

Avaliac ¸ão das Estratégias de Escalonamento

Na Sec ¸ão 5.2 foram apresentados resultados que indicam uma convergência do algoritmo genético proposto em direc ¸ão à soluc ¸ão ótima para o problema estudado. A Figura 4 compara o grau de desbalanceamento da soluc ¸ão encontrada pelo algoritmo genético (AG) com as soluc ¸ões encontradas pelas estratégias Static e Dynamic. As estratégias Static e Dynamic foram executadas com chunks de tamanho 1, 4, 8, 16 e 32. Porém, a Figura 4 apresenta somente os melhores resultados em cada caso.

O resultado para a estratégia SRR também é apresentado. Essa estratégia foi projetada a partir de uma análise das soluc ¸ões encontradas pelo algoritmo genético, que considerou a carga média de trabalho atribuída às threads e o desvio padrão observado nos diferentes cenários. Em termos gerais, a ideia dessa estratégia é atribuir em pares as iterac ¸ões de um lac ¸o às threads seguindo um esquema round-robin, de forma que ao final do processo cada thread receba uma carga de trabalho próxima à carga de trabalho média estimada. Para tanto, cada par é composto pelas iterac ¸ões de maior e menor cargas ainda não atribuídas.

Número de Tarefas Grau de Desbalanceamento

Beta Gamma Normal

Poisson Uniforme Figura 4. Avaliac ¸ão das estrat égias de escalonamento de lac ¸os.

Com base nos resultados é possível verificar que em 14 dos 15 cenários estudados a soluc ¸ão encontrada pelo AG supera às encontradas pelas estratégias existentes (Static e Dynamic), sendo no mínimo 1,2 x melhor (distribuic ¸ão normal, 512 iterac ¸ões) e no máximo 40,2 x melhor (distribuic ¸ão gamma, 512 iterac ¸ões). A soluc ¸ão encontrada pelo AG foi superada na distribuic ¸ão normal com 256 iterac ¸ões pela estratégia Static em 1,2 x. Essa situac ¸ão é melhor detalhada na Sec ¸ão 5.4. Diferente das estratégias Static e Dynamic, a estratégia SRR leva em considerac ¸ão a carga de trabalho e, então, obtém uma soluc ¸ão superior às encontradas por essas duas estratégias em todos os cenários estudados. Esse ganho observado varia de 1,1 x (distribuic ¸ão gamma, 512 iterac ¸ões) a 32,3 x (distribuic ¸ão uniforme, 512 iterac ¸ões), sendo expressivo em todas as distribuic ¸ões, exceto para a distribuic ¸ão gamma. Esse fato é explicado pela natureza da distribuic ¸ão e relac ¸ão com a estratégia de escalonamento e será discutido em maiores detalhes a seguir.

Análise da Distribuic ¸ão de Cargas

Avaliando as estratégias de escalonamento a partir da Figura 4, três casos típicos podem ser identificados: (i) o algoritmo genético apresenta a melhor soluc ¸ão, seguido pelas estratégia SRR, Dynamic e Static; (ii) o algoritmo genético apresenta a melhor soluc ¸ão, com as estratégias SRR e Dynamic equiparadas, e a estratégia Static em seguida; e (iii) a estratégia SRR se destaca com a melhor soluc ¸ão. Esses três casos podem ser observados para as distribuic ¸ões beta, gamma e normal quando 512 iterac ¸ões são consideradas.

A Figura 5 apresenta uma visão detalhada do desempenho do algoritmo genético e das três estratégias de balanceamento nesses cenários, com a linha vermelha horizontal indicando a soluc ¸ão ótima (teórica) para o problema. Para a distribuic ¸ão beta é possível perceber um claro desbalanceamento nas soluc ¸ões encontradas pelas estratégias Static e Dynamic. Já para as estratégias SRR e AG, observa-se que as soluc ¸ões encontradas aproximam-se substancialmente da ótima, com a diferenc ¸a entre as duas soluc ¸ões explicada pela magnitude do eixo vertical do gráfico.

Para a distribuic ¸ão gamma, é possível constatar o forte desbalanceamento provocado pela estratégia Static e uma soluc ¸ão próxima da ótima encontrada pelo algoritmo genético. No entanto, as estratégias SRR e Dynamic encontram-se equiparadas em um meio termo. No caso da estratégia SRR, o motivo deve-se à própria distribuic ¸ão e estratégia: como existem poucas iterac ¸ões grandes, essas iterac ¸ões são atribuídas às thre- ads inicialmente consideradas no escalonamento, causando um desbalanceamento entre o conjunto de threads posteriormente considerado. Esse fato é evidenciado pelos degraus presentes no gráfico. Portanto, a estratégia SRR é mais adequada para distribuic ¸ões que possuam um número balanceado de iterac ¸ões com carga grande e pequena.

Por fim, para a distribuic ¸ão normal observa-se que a estratégia SRR se aproxima consideravelmente da soluc ¸ão ótima enquanto as demais estratégias apresentam resultados desbalanceados com valores similares. Nessa situac ¸ão, observou-se que o algoritmo genético ficou estagnado em um máximo local e, portanto, não convergiu para uma soluc ¸ão ótima. Além disso, a uniformidade existente na quantidade de iterac ¸ões com carga pequena e grande na distribuic ¸ão favorece a estratégia SRR. Um comportamento similar foi observado na distribuic ¸ão uniforme.

Conclusões

Esse trabalho apresentou uma metodologia que possibilita o projeto e explorac ¸ão de novas estratégias de escalonamento de lac ¸os. Nessa metodologia, a técnica de simulac ¸ão foi empregada para se estudar as principais políticas de escalonamento existentes e um algoritmo genético foi usado para se explorar o espac ¸o de soluc ¸ões do problema. Baseado nos resultados obtidos quando essa metodologia foi aplicada, uma nova estratégia, denominada SRR, foi proposta. Os resultados revelaram que as políticas clássicas apontadas na literatura, Static e Dynamic, são de 1,2 x a 40,2 x piores que as soluc ¸ões ótimas estimadas pelo algoritmo genético em 14 dos 15 cenários estudados. Já a estratégia SRR se mostrou de 1,1 x a 32,3 x melhor que as políticas existentes, em todos os casos considerados. Essa observac ¸ão valida a metodologia proposta, possibilitando seu uso no projeto de novas estratégias de escalonamento de lac ¸os. Como trabalhos futuros, pretende-se empregar a metodologia para guiar o projeto de novas estratégias, aprimorar a política SRR para considerar aspectos relacionados à plataforma e estender a metodologia, acrescentando uma fase adicional que valide as estratégias no ambiente OpenMP.

Agradecimentos

Os autores agradecem o CNPq, a FAPEMIG e o INRIA pelo suporte parcial ao trabalho.

Figura 1 .

 1 Figura 1. Arquitetura interna do simulador desenvolvido.

Figura 2 .

 2 Figura 2. Distribuic ¸ões e par âmetros considerados.

Figura 3 .

 3 Figura 3. Evoluc ¸ão do AG para uma distribuic ¸ão beta com 512 iterac ¸ões.

Figura 5 .

 5 Figura 5. Cargas atribuídas à cada thread em execuc ¸ões com 32 threads.

Tabela 1. Desvio padr ão relativo observado na carga de trabalho m édia.

  

	N úmero de iterac ¸ões	Beta Gamma Normal Poisson Uniforme
	128	6,05 % 12,53 %	1,37 %	7,76 %	3,22 %
	256	1,34 %	1,41 %	1,16 %	2,53 %	1,52 %
	512	0,26 %	0,22 %	0,73 %	1,68 %	0,68 %