Modelo de Algoritmo Genético para o Escalonamento de Tarefasem uma Arquitetura Multiprocessadora

Autor: Adilmar Coelho Dantas1,Orientador: Márcia Aparecida Fernandes1

1Programa de Pós-Graduação em Ciência da ComputaçãoUniversidade Federal do Uberlândia (UFU)

Uberlândia – MG – Brasil

adilmar@mestrado.ufu.br

Nível: Mestrado

Resumo. Este artigo apresenta um algoritmo genético baseado na teoria da evoluçãopara resolver o problema de escalonamento de tarefas em máquinas paralelas idên-ticas. O problema consiste em determinar a ordem de processamento das tarefas nasmáquinas, minimizando o tempo máximo de finalização do processamento (makes-pan). O objetivo do algoritmo genético é determinar uma aproximação do conjuntode soluções eficientes. As técnicas de crossover, mutação e torneio foram utilizadoscom diferentes índices com o objetivo de avaliar o algoritmo.

Palavras-Chave. Escalonamento de Tarefas, Algoritmo Genético, Inteligência Com-putacional.

1. Introdução e MotivaçãoO problema de escalonamento de tarefas consiste em determinar a ordem de processamentodas tarefas nas máquinas, minimizando o tempo máximo de finalização do processamento (ma-kespan). É um problema de otimização combinatória bem conhecido pertencente à classe deproblemas intratáveis (NP completo).

Este Artigo tem como o objetivo o desenvolvimento de um algoritmo e a realização detestes a fim de verificar seu desempenho e assertividade em situações diversas com o objetivo dechegar a uma melhor configuração para o algoritmo genético proposto e compará-lo a resultadosde outros trabalhos com essa mesma proposta.

2. Fundamentação TeóricaAlgoritmos genéticos usam modelos computacionais dos processos naturais de evolução comouma ferramenta para resolver problemas. Apesar de haver uma grande variedade de modeloscomputacionais propostos (CAMPELLO e MACULAN 1994), todos eles têm em comum oconceito de simulação da evolução das espécies através de seleção, mutação e reprodução, pro-cessos estes que dependem do desempenho dos indivíduos desta espécie dentro do ambiente.

Os algoritmos evolucionários funcionam mantendo uma população de estruturas queevoluem de forma semelhante à evolução das espécies. A estas estruturas são aplicados oschamados operadores genéticos, como recombinação e mutação, entre outros (LINDEN 2012).

Cada indivíduo recebe uma aptidão ou avaliação que é uma quantificação da sua quali-dade como solução do problema em questão. Baseado nesta avaliação é que serão aplicados osoperadores genéticos de forma a simular a sobrevivência do mais apto assim como na natureza(LUKE 2011).

Os operadores genéticos consistem em aproximações computacionais de fenômenos vis-tos na natureza, como a reprodução sexuada, a mutação genética, entre outros (WOODWARDe SWAN 2011).

Algoritmos genéticos podem ser definidos como uma técnica de busca baseada nos pro-cessos biológicos e de evolução natural encontrados na natureza. Nos algoritmos genéticospopulações de indivíduos são criadas e submetidas aos operadores genéticos conhecidos porseleção, crossover e mutação.

Estes operadores avaliam a qualidade de cada indivíduo como critério para encontrar asolução do problema. É gerado um processo de evolução natural destes indivíduos, que eventu-almente gerará um indivíduo que caracterizará uma boa solução (talvez até a melhor possível)para o problema (LUKE 2011).

Assim como na seleção natural que não para de procurar outros indivíduos ainda melho-res, mesmo que estes se destaquem no grupo, os algoritmos genéticos não ficarão estagnadossimplesmente por terem encontrado um melhor indivíduo.

A reprodução e a mutação são aplicadas em indivíduos selecionados dentro da popu-lação (LINDEN 2012). A seleção deve ser feita de modo que os indivíduos mais aptos sejamselecionados mais frequentemente do que aqueles menos aptos, de forma que as boas caracte-rísticas daqueles passem a predominar dentro da população da solução.

Um agendamento, ou escalonamento (Scheduling), pode ser entendido como uma formade escalonar um conjunto de operações (processos) as quais envolvem planejamento, pois obe-decem a múltiplas restrições. Para resolvê-lo é necessário obter as informações sobre as tarefasa serem executadas no sistema como a quantidade de processos, processadores dentre outrosuma forma de representar essas informações de escalonamento entre dois processadores de es-trutura paralela é o chamado Gauss 18 que pode ser observado na figura 1, que é um grafodirecionado composto de 18 tarefas.

Figura 1. Grafo Gauss 18

Onde os círculos (nós) representam as tarefas, ao lado esquerdo de cada círculo pode seobservar o tempo total de execução da tarefa. Os links entre esses nós representam a precedên-cia. Não somente o grafo de Gauss foi utilizado neste artigo mas outros semelhantes para medirseu desempenho.

3. Contribuição do TrabalhoO presente trabalho tem como objetivo validar é comparar os resultados obtidos com trabalhossemelhantes e além disso propor possíveis soluções utilizando algoritmos genéticos, para oproblema de escalonamento de processos, um problema aplicado a diversas situações da vidareal, como o escalonamento de processos da CPU, e na indústria em geral com a finalidade dereduzir custos, minimizar gastos dentre outros.

4. Estado atual do TrabalhoPara a construção desse algoritmo a população inicial e gerada de forma aleatória para garantirque todos estes indivíduos sejam válidos, onde um indivíduo não válido se caracteriza pelofato de estar alocado antes de outra da qual é uma dependente no mesmo processador. Muitasdas vezes os indivíduos gerados podem não ser válidos, necessitando assim de uma funçãode correção para melhores resultados, a qual foi implementada com a finalidade de manter aaleatoriedade e diversidade da população.

O método de avaliação de indivíduos em algoritmos genéticos tem como objetivo veri-ficar o seu percentual positivo de cada indivíduo da população. Para o problema de escalona-mento, o algoritmo contabiliza as unidades de tempo necessárias para que todas as tarefas sejamrealizadas, seguindo a alocação de precedência de cada uma delas. Então, o melhor indivíduoserá aquele que levar menos tempo de execução dentre os demais na população.

Após essa avaliação da população corrente, passa-se para a etapa de seleção, para estealgoritmo foi implementado o método de seleção denominado torneio simples para determinarquais indivíduos passaram seus materiais genéticos para as próximas gerações. Nesta etapasorteia-se dois indivíduos de forma aleatória é feita então a verificação de quais dos dois possuimelhor aptidão, neste caso o menor tempo, formando assim pares de indivíduos pais que darãoorigem a novas gerações para a população.

Uma dupla vencedora de cada torneio dará origem a dois filhos através do crossover,onde se escolhe um ponto no qual é feito a troca de material genético entre esses indivíduos.Após o crossover alguns destes filhos são submetidos a mutação assim como pode ocorrer nanatureza, para isso se utilizou da permutação simples que evita que tarefas repetidas façamparte do cromossomo. É sorteado dois pontos e feita a troca dessas tarefas sem interferir nosprocessadores, a figura 2 ilustra esse processo.

Figura 2. Processo de Mutação

Na etapa final, os melhores indivíduos de cada iteração são selecionados para formaremuma nova população para nova interação, e novamente para o processo de seleção, crossovere mutação. Cada uma dessas iterações é chamada de geração tendo como critério de paradaquando se alcança o número máximo (Nger) especificado na implementação.

A figura 3 demostra todo o processamento decorrente do algoritmo genético, desde suaexecução até a sua convergência final ilustrando todas as etapas citadas acima. Os AG possuem

natureza probabilística, sendo necessário diversas execuções do mesmo para garantir maiorconfiabilidade dos resultados.

Figura 3. Ciclo de um AG

5. Análise de Resultados

Foi implementado em Scala um ambiente baseado no algoritmo genético como descrito anteri-ormente para encontrar uma melhor configuração para o grafo Gauss 18, estes testes realizadoslevaram em consideração as seguintes combinações das configurações Tpop = Tamanho da po-pulação, Nger = Número de gerações e Tour = Tamanho do método de seleção do torneio, paratodas as combinações foi utilizado taxa de mutação de 30%, e dois processadores em paralelo.

As combinações foram executadas 20 vezes cada uma delas, totalizando assim 540 exe-cuções para se encontrar uma melhor combinação, para este trabalho foi levado em consideraçãoo tempo de execução também para cada combinação.

Uma das dificuldades de reproduzir os trabalhos relacionados foi primeiramente no sor-teio de indivíduos, onde testes que descartaram os considerados não aptos. Foi perceptível oaumento no tempo de execução do algoritmo uma vez que ele deveria sortear um novo indíviduotoda vez que encontrasse um não válido. Para resolver este impasse, fizemos o sorteio cíclico,que varre a estrutura e a reoganiza de modo que ela se torne compatível.

A função de avaliação outra grande dificuldade encontrada, pois se não for realizadacorretamente pode provocar uma convergência prematura e em algumas execuções iniciais pro-vocou elitismo no algoritmo isso é, quando os melhores pontos encontrados são preservados napopulação por todas as gerações ou na maioria delas.

Sanada essas dificuldades foi alcançado resultados próximos dos obtidos nos artigos etambém a mesma configuração proposta. Estes resultados podem ser observados na tabela 1,a configuração 10 com Tpop = 100, Nger= 200 e Tour = 2 está selecionada como melhorconfiguração pois estamos levando em consideração o tempo de execução.

Essas configurações foram testadas para outros grafos gerados aleatoriamente de 15atividades com a finalidade de testar e verificar quais as possíveis melhores configurações, emespecifico para o grafo de Gauss 18 foi realizado testes com maior número de execuções evariações na população e mutação baseada na melhor configuração encontrada e analisar qual oseu comportamento.

Após a geração da tabela de resultados fizemos uma comparação com os artigos e foiverificado o mesmo resultado na combinação nos demais campos houve variações mas sãoaceitavéis pelo fato das particularidades do AG e por sua natureza estatística.

Combinação Tpop Nger Tour Convergência Média1 50 200 2 2 52,352 50 200 3 2 58,823 50 200 4 2 62,944 50 300 2 6 52,355 50 300 3 3 58,826 50 300 4 2 62,647 50 500 2 7 52,358 50 500 3 2 60,009 50 500 4 3 63,82

10 100 200 2 11 44,1111 100 200 3 5 57,0512 100 200 4 4 62,0513 100 300 2 7 49,1114 100 300 3 2 58,5215 100 300 4 3 59,9916 100 500 2 10 51,4717 100 500 3 3 57,9418 100 500 4 4 60,2929 200 200 2 9 57,9420 200 200 3 5 54,9921 200 200 4 3 59,4122 200 300 2 13 51,9423 200 300 3 2 55,0024 200 300 4 2 59,1125 200 500 2 12 57,6426 200 500 3 2 54,1127 200 500 4 16 59,99

Tabela 1. Resultados AG: Gauss 18

Ambas combinações foram executadas 20 vezes, somando um total de 540 execuçõesde 27 combinações para o grafo Gauss 18.

Pela tabela pode-se observar que a combinação 22 poderia ser uma boa opção, masela requer o dobro de população e muito mais tempo de execução, o que não nos levou à es-colhermos como a melhor combinação para este algoritmo proposto. As combinações foramexecutadas em um computador com processador Quad Core 3.33 GHZ e 4 GB de memóriaRAM. Abaixo na figura 4 temos os resultados de convergência agrupados para o Gauss 18.

Para avaliar o AG, esse mesmo teste foi refeito, porém com taxa de crossover de 20%e 10% de mutação. Os testes demostraram que com baixas populações ocorrem poucas con-vergências ou nenhuma, e novamente a combinação 10 a mesma proposta para o Gauss 18 foiescolhida como a melhor.

Outra observação é que o tempo de execução do AG cresce de forma linear geralmente,conforme as alterações em populações e convergências. Dentre os testes realizados, uma boaopção observada seria aumentar em 50 o tamanho da população mantendo as mesmas confi-gurações para convergência e torneio, obtendo assim, uma taxa de convergência de 15 em 47unidades de tempo.

Figura 4. Resultados agrapados para o Gauss 18

O mesmo algoritmo foi executado para um grafo de 11 tarefas que chamamos de G11cujas os (V) vertices e arestas (E) dos grafos estão representados na tabela 2, os resultados domesmo foi comparado com o artigo, onde obtivemos 19 de convergência para o mesmo e médiade 39,50 ambos bem próximo com os obtidos nos artigos o qual obteve 20 para convergência e40,00 de média.

Grafo V EG11 (0,8),(1,4),(2,4), (0,1,8),(0,2,12),(1,3,12),(1,4,12)

(3,4),(4,4),(5,4), (2,5,8),(2,6,12),(3,7,8),(4,7,8),(6,6),(7,3),(8,3), (4,8,8),(5,8,8),(5,9,8),(6,9,8),

(9,3),(10,3) (7,10,12),(8,10,8),(9,10,12)

Tabela 2. Grafo de 11 tarefas utilizado

6. Trabalhos Relacionados

Existem diversos trabalhos com a mesma temática proposta neste trabalho, pelo fato do pro-blema ser NP completo a busca por algoritmos mais eficientes é grande além das técnicas aquiproposta de algoritmos genéticos esses trabalhos apresentam também, autômatos celulares, al-goritmos aproximados, algoritmos gulosos dentre outras técnicas.

O desenvolvimento deste trabalho utilizou como base dois trabalhos sobre o mesmoassunto, são eles (HELDER & JAQUELINA & PAULO & GINA) e (JAQUELINE & HELDER& GINA ). O primeiro faz uma comparação entre algoritmos genéticos e outros algoritmosenquanto o segundo usado para comparação de resultados principalmente, tem como objetivoencontrar e propor uma melhor configuração para o AG proposto.

Os resultados foram diretamente comparados com o trabalho citado com objetivo de ob-ter os resultados mais próximos possíveis, apesar dos trabalhos serem mais abrangentes fazendocomparações com outras técnicas para a solução de escalonamento de tarefas, o artigo propostotem as mesmas finalidades e bons resultados.

7. ReferênciasCampello, R. E. and Maculan, N. (1994). Algorítmo e Heurísticas, EDUFF - EditoraUniversitária.

Linden, R. (2012). Algoritmos Genéticos (2a edição), BRASPORT.

Luke, S. (2011). Essentials of Metaheuristics. Department of Computer Science, Ge-orge Mason University, Lulu.

Woodward, J. R. and Swan, J. (2011). Automatically designing selection heuristics.Proceedings of the 13th annual conference companion on Genetic and evolutionary computa-tion. Dublin, Ireland, ACM: 583-590.

Jaqueline A. J. Papine, Helder R. G. Linhares, Gina M. B. De Oliveira. Escalonamentode Tarefas em Multiprocessadores Baseado em Algoritmos Genéticos .

Jaqueline A. J. Papine, Helder R. G. Linhares, Paulo M. Vidica, Gina M. B. De Oliveira.Algoritmos genéticos e Branch and Bound aplicados ao escalonamento de tarefas emmultiprocessadores.