Algoritmos de Otimização para Simulação Distribuída de Arquiteturas Complexas
Resumo
O projeto de arquiteturas de computadores complexas envolve diversas etapas e pode levar vários anos de desenvolvimento. Desse modo, é comum usar simulação com a finalidade de estudar os efeitos de novos mecanismos e das diversas modificações e atualizações na arquitetura, já que a implementação direta é proibitiva em função do tempo, custo e complexidade. Mesmo usando simulação, a busca pela melhor configuração pode ser onerosa em decorrência da diversidade de parâmetros que podem mudar e afetar o comportamento da arquitetura. Este trabalho utiliza uma implementação de um algoritmo genético para a otimização e automatização da busca de configurações em simulação de arquiteturas de computadores. Os resultados mostram que, dentro do espaço de busca apresentado no artigo, o tempo de execução das simulações reduz em até 91%, se comparado à busca exaustiva. Além disso, os resultados encontrados pelo algoritmo genético representam valores com precisão acima de 97% com relação à solução ótima. Para diminuir ainda mais o tempo na obtenção dos resultados, o processamento das simulações executadas pelo algoritmo genético foi distribuído em um agregado e uma grade. Essa versão distribuída reduziu em mais de 80% o tempo de execução, quando comparado à execução seqüencial do mesmo algoritmo genético.
Referências
N. Andrade, L. Costa, G. Germóglio, andW. Cirne. Peer-topeer grid computing with the ourgrid community. In Proceedings of the SBRC 2005 – IV Special Tools Session, 2005.
D. C. Burger and T. M. Austin. The simplescalar tool set, version 2.0. Technical Report CS-TR-1997-1342, 1997.
R. Buyya and C. Szyperski. Cluster Computing. Nova Science Publishers, 2001.
E. Cant’u-Paz. A summary of research on parallel genetic algorithms. Technical Report IlliGAL report 95007, University of Illinois at Urbana-Champaign, 1995.
W. Cirne and et. al. Computing for bag of tasks applications. In Proceedings of the 3rd IFIP Conference on E-Commerce, E-Business and E-Goverment, 2003.
J. R. Filho, C. Alippi, and P. Treleaven. Genetic algorithm programming environments. In J. Stender, editor, Parallel Genetic Algorithms: Theory and Applications, pages 65–83. IOS Press, Amsterdam, 1993.
G. Hamerly, E. Perelman, J. Lau, and B. Calder. Simpoint 3.0: Faster and more flexible program analysis. Journal on Instruction-Level Parallelism (JILP), (7), Sept. 2005.
J. L. Henning. SPEC CPU200: Measuring CPU performance in the new millenium. IEEE Computer, 33(7):28–35, July 2000.
J. H. Holland. Adaptation in natural and artificial systems. Technical Report Report of the Systems Analysis Research Group SYS–1/92, University of Dortmund, Department of Computer Science. Ann Arbor, MI: The University of Michigan Press, 1975.
M. Olivieri. A genetic approach to the design space exploration of superscalar microprocessor architectures. In ISCAS (5), pages 69–72. IEEE, 2001.
C. B. Pettey, M. R. Leuze, and J. J. Grefenstette. A parallel genetic algorithm. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 155–161, Mahwah, NJ, USA, 1987. Lawrence Erlbaum Associates, Inc.
A. Thompson. Artificial evolution in the physical world. In T. Gomi, editor, Evolutionary Robotics: From intelligent robots to artificial life (ER’97), pages 101–125. AAI Books, 1997.
G. V. R. Viana. Meta-heurísticas e programação paralela em otimizaçãoo combinatória. UFC Edições, Fortaleza, 1998.
