Uma Metodologia Baseada em Simulação e Algoritmo Genético para Exploração de Estratégias de Escalonamento de Laços
Resumo
Na Computação de Alto Desempenho, a carga de trabalho de aplicações paralelas deve ser balanceada entre as threads para obtenção de um melhor desempenho. Nesse trabalho é proposta uma metodologia que possibilita o projeto e a exploração de novas políticas de escalonamento de laços. Essa metodologia emprega a técnica de simulação para estudar as principais estratégias existentes e um algoritmo genético para explorar o espaço de soluções do problema. A metodologia proposta auxiliou no projeto de uma nova estratégia de escalonamento de laços que se mostrou ser até 32.3x melhor em ternos de balanceamento de carga que as políticas existentes.Referências
Balasubramaniam, M., Sukhija, N., Ciorba, F., Banicescu, I., and Srivastava, S. (2012). Towards the scalability of dynamic loop scheduling techniques via discrete event siIn IEEE International Parallel and Distributed Processing Symposium mulation. Workshops (IPDPSW), pages 1343–1351, Shanghai, China.
Bhandari, D., Murthy, C. A., and Pal, S. K. (1996). Genetic algorithm with elitist model and its convergence. International Journal of Pattern Recognition and Articial Intelligence, 10(06):731–747.
Chen, B. and Guo, D. (2014). A static scheduling scheme of multicore compiler for loop load imbalance in openmp. In International Conference on Anti-counterfeiting, Security, and Identication (ASID), pages 1–4, Fujian, China.
Coello, C. A. C. (1999). A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge and Information Systems, 1(3):269–308.
Dagum, L. and Menon, R. (1998). Openmp: An industry standard api for shared-memory programming. IEEE Computational Science Engineering, 5(1):46–55.
Ding, W., Zhang, Y., Kandemir, M., Srinivas, J., and Yedlapalli, P. (2013). Locality-aware mapping and scheduling for multicores. In IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 1–12, Shenzhen, China.
Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69–93. Morgan Kaufmann.
Hajieskandar, A. and Lot, S. (2010). Parallel loop scheduling using an evolutionary algorithm. In International Conference on Advanced Computer Theory and Engineering (ICACTE), volume 1, pages 314–319, Chengdu, China.
Konfrst, Z. (2004). Parallel genetic algorithms: Advances, computing trends, applications and perspectives. In IEEE International Parallel Distributed Processing Symposium (IPDPS), pages 162–, Santa Fe, New Mexico.
Olivier, S. L., Portereld, A. K., Wheeler, K. B., Spiegel, M., and Prins, J. F. (2012). Openmp task scheduling strategies for multicore numa systems. Int. J. High Perform. Comput. Appl., 26:110–124.
Patni, J., Aswal, M., Pal, O., and Gupta, A. (2011). Load balancing strategies for In International Conference on Electronics Computer Technology grid computing. (ICECT), volume 3, pages 239–243, Kanyakumari, India.
Skiena, S. S. (2008). The Algorithm Design Manual. Springer, 2nd edition. Srivastava, S., Malone, B., Sukhija, N., Banicescu, I., and Ciorba, F. (2013). Predicting the exibility of dynamic loop scheduling using an articial neural network. In IEEE International Symposium on Parallel and Distributed Computing (ISPDC), pages 3– 10, Bucharest, Romania.
Srivastava, S., Sukhija, N., Banicescu, I., and Ciorba, F. (2012). Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems. In International Symposium on Parallel and Distributed Computing (ISPDC), pages 156–163, Munich, Germany.
Sukhija, N., Malone, B., Srivastava, S., Banicescu, I., and Ciorba, F. (2014). Portfoliobased selection of robust dynamic loop scheduling algorithms using machine learning. In IEEE International Parallel Distributed Processing Symposium Workshops (IPDPSW), pages 1638–1647, Phoenix, USA.
Tantawi, A. N. and Towsley, D. (1985). Optimal static load balancing in distributed computer systems. J. ACM, 32(2):445–465.
Bhandari, D., Murthy, C. A., and Pal, S. K. (1996). Genetic algorithm with elitist model and its convergence. International Journal of Pattern Recognition and Articial Intelligence, 10(06):731–747.
Chen, B. and Guo, D. (2014). A static scheduling scheme of multicore compiler for loop load imbalance in openmp. In International Conference on Anti-counterfeiting, Security, and Identication (ASID), pages 1–4, Fujian, China.
Coello, C. A. C. (1999). A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge and Information Systems, 1(3):269–308.
Dagum, L. and Menon, R. (1998). Openmp: An industry standard api for shared-memory programming. IEEE Computational Science Engineering, 5(1):46–55.
Ding, W., Zhang, Y., Kandemir, M., Srinivas, J., and Yedlapalli, P. (2013). Locality-aware mapping and scheduling for multicores. In IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 1–12, Shenzhen, China.
Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69–93. Morgan Kaufmann.
Hajieskandar, A. and Lot, S. (2010). Parallel loop scheduling using an evolutionary algorithm. In International Conference on Advanced Computer Theory and Engineering (ICACTE), volume 1, pages 314–319, Chengdu, China.
Konfrst, Z. (2004). Parallel genetic algorithms: Advances, computing trends, applications and perspectives. In IEEE International Parallel Distributed Processing Symposium (IPDPS), pages 162–, Santa Fe, New Mexico.
Olivier, S. L., Portereld, A. K., Wheeler, K. B., Spiegel, M., and Prins, J. F. (2012). Openmp task scheduling strategies for multicore numa systems. Int. J. High Perform. Comput. Appl., 26:110–124.
Patni, J., Aswal, M., Pal, O., and Gupta, A. (2011). Load balancing strategies for In International Conference on Electronics Computer Technology grid computing. (ICECT), volume 3, pages 239–243, Kanyakumari, India.
Skiena, S. S. (2008). The Algorithm Design Manual. Springer, 2nd edition. Srivastava, S., Malone, B., Sukhija, N., Banicescu, I., and Ciorba, F. (2013). Predicting the exibility of dynamic loop scheduling using an articial neural network. In IEEE International Symposium on Parallel and Distributed Computing (ISPDC), pages 3– 10, Bucharest, Romania.
Srivastava, S., Sukhija, N., Banicescu, I., and Ciorba, F. (2012). Analyzing the robustness of dynamic loop scheduling for heterogeneous computing systems. In International Symposium on Parallel and Distributed Computing (ISPDC), pages 156–163, Munich, Germany.
Sukhija, N., Malone, B., Srivastava, S., Banicescu, I., and Ciorba, F. (2014). Portfoliobased selection of robust dynamic loop scheduling algorithms using machine learning. In IEEE International Parallel Distributed Processing Symposium Workshops (IPDPSW), pages 1638–1647, Phoenix, USA.
Tantawi, A. N. and Towsley, D. (1985). Optimal static load balancing in distributed computer systems. J. ACM, 32(2):445–465.
Publicado
18/10/2015
Como Citar
PENNA, Pedro; CASTRO, Márcio; FREITAS, Henrique; BROQUEDIS, François; MÉHAUT, Jean-François.
Uma Metodologia Baseada em Simulação e Algoritmo Genético para Exploração de Estratégias de Escalonamento de Laços. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 16. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 156-167.
DOI: https://doi.org/10.5753/wscad.2015.14280.
