Uma Implementação MPI Tolerante a Falhas do Algoritmo Bitonic Sort
Resumo
O Bitonic Sort executa a ordenação através de operações de divisão e mesclagem de sequências bitônicas. Uma sequência é dita bitônica se seus elementos crescem e decrescem a partir de algum ponto. Apesar de muitas variantes do algoritmo encontradas na literatura, não se conhece uma implementação paralela capaz de tolerar falhas de processos em tempo de execução. Este trabalho apresenta uma implementação MPI do Bitonic Sort capaz de suportar até n-1 falhas de processos, onde n é o total de processos. A mais recente especificação de tolerância a falhas proposta pelo MP-Fórum é empregada no desenvolvimento da solução. Resultados experimentais mostram a eficiência da implementação na ordenação de até 1 bilhão de números inteiros.
Palavras-chave:
Tolerância a Falhas, Algoritmos de ordenamento, MPI, Bitonic Sort
Referências
Al-Hashimi, M. A., Abulnaja, O. A., Saleh, M. E., and Ikram, M. J. (2017). Evaluating power and energy efficiency of bitonic mergesort on graphics processing unit. IEEE Access, 5:16429-16440.
Batcher, K. E. (1968). Sorting networks and their applications. In Proceedings of the April 30-May 2, 1968, Spring Joint Computer Conference, AFIPS '68 (Spring), pages 307-314, New York, NY, USA. ACM.
Bland, W., Bouteiller, A., Hérault, T., Bosilca, G., and Dongarra, J. (2013). Post-failure recovery of MPI communication capability: Design and rationale. International Jour-nal of HPC Applications, 27(3):244-254.
Camargo, E. T. and Duarte, Jr., E. (2016). Uma implementação mpi tolerante a falhas do algoritmo hyperquicksort. In SBRC 2016 -WTF.
Camargo, E. T. d. and Duarte, Jr., E. P. (2017). Minicurso v: Técnicas para a construção de sistemas mpi tolerantes a falhas. In Minicurso do WSCAD 2017, page 30.
Camargo, E. T. d. and Duarte, Jr., E. P. (2018). Running resilient mpi applications on a dynamic group of recommended processes. Journal of the Brazilian Computer Society, 24(1):5.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267.
Chen, R., Siriyal, S., and Prasanna, V. (2015). Energy and memory efficient mapping of bitonic sorting on fpga. In Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA '15, pages 240-249, New York, NY, USA. ACM.
Duarte, Jr., E. P. and Nanya, T. (1998). A hierarchical adaptive distributed system-level diagnosis algorithm. IEEE Transactions on Computers, 47(1):34-45.
Durad, M. H., Akhtar, M. N., and ul Haq, I. (2014). Performance analysis of parallel sorting algorithms using mpi. In 2014 12th International Conference on Frontiers of Information Technology, pages 202-207.
Elnozahy, Alvisi, Wang, and Johnson (2002). A survey of rollback-recovery protocols in message-passing systems. ACM Comput. Surveys, 34.
Fagg, G. E. and Dongarra, J. (2000). FT-MPI: Fault tolerant MPI, supporting dynamic applications in a dynamic world. In Recent advances in PVM and MPI, LNCS. Sprin-ger.
Forum, M. (2019a). Mpi forum website. http://mpi-forum.org/. Acessado em 26/01/2019.
Forum, M. (2019b). User-level failure mitigation. http://fault-tolerance. org/ulfm/ulfm-specification/. Acessado em 26/02/2019.
Freiling, F. C., Guerraoui, R., and Kuznetsov, P. (2011). The failure detector abstraction. ACM Comput. Surv., 43(2):9:1-9:40.
Gabriel, E., Fagg, G. E., Bosilca, G., Angskun, T., Dongarra, J. J., Squyres, J. M., Sahay, V., Kambadur, P., Barrett, B., Lumsdaine, A., Castain, R. H., Daniel, D. J., Graham, R. L., and Woodall, T. S. (2004). Open MPI: Goals, concept, and design of a next generation MPI implementation. In Proceedings, 11th European PVM/MPI Users' Group Meeting, pages 97-104, Budapest, Hungary.
Gropp, W., Lusk, E., Doss, N., and Skjellum, A. (1996). A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing, 22(6):789-828.
Johnson, S. L. (1984). Combining parallel and sequential sorting on a boolean n-cube. In Proceedings of the 1984 International Conference on Parallel Processing, pages 444-448.
Kumar, V. (2002). Introduction to Parallel Computing. Addison-Wesley Longman Pu-blishing Co., Inc., Boston, MA, USA, 2nd edition.
Lan, Y. and Mohamed, M. A. (1992). Parallel quicksort in hypercubes. In Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing: Technological Challenges of the 1990's, SAC '92, pages 740-746, New York, NY, USA. ACM.
Lee, D. and Batcher, K. E. (1994). On sorting multiple bitonic sequences. In 1994 International Conference on Parallel Processing Vol. 1, volume 1, pages 121-125.
MPI Forum (2015). Document for a standard message-passing interface 3.1. Technical report, University of Tennessee, http://www.mpi-forum.org/docs/mpi-3.1.
MPI-Forum (2019). User-level failure mitigation. https://bitbucket.org/ icldistcomp/ulfm/. Acessado em 26/02/2019.
Nassimi, D. and Sahni, S. (1979). Bitonic sort on a mesh-connected parallel computer. IEEE Transactions on Computers, C-28(1):2-7.
Pacheco, P. S. (1997). Parallel programming with MPI. Morgan Kaufmann.
Quinn, M. J. M. J. (2003). Parallel programming in C with MPI and OpenMP. McGraw-Hill, pub-MCGRAW-HILL:adr.
Sheu, J.-P., Chen, Y.-S., and Chang, C.-Y. (1992). Fault-tolerant sorting algorithm on hypercube multicomputers. J. Parallel Distrib. Comput., 16:185-198.
Velusamy, K., Rolinger, T. B., McMahon, J., and Simon, T. A. (2018). Exploring paral-lel bitonic sort on a migratory thread architecture. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1-7.
Batcher, K. E. (1968). Sorting networks and their applications. In Proceedings of the April 30-May 2, 1968, Spring Joint Computer Conference, AFIPS '68 (Spring), pages 307-314, New York, NY, USA. ACM.
Bland, W., Bouteiller, A., Hérault, T., Bosilca, G., and Dongarra, J. (2013). Post-failure recovery of MPI communication capability: Design and rationale. International Jour-nal of HPC Applications, 27(3):244-254.
Camargo, E. T. and Duarte, Jr., E. (2016). Uma implementação mpi tolerante a falhas do algoritmo hyperquicksort. In SBRC 2016 -WTF.
Camargo, E. T. d. and Duarte, Jr., E. P. (2017). Minicurso v: Técnicas para a construção de sistemas mpi tolerantes a falhas. In Minicurso do WSCAD 2017, page 30.
Camargo, E. T. d. and Duarte, Jr., E. P. (2018). Running resilient mpi applications on a dynamic group of recommended processes. Journal of the Brazilian Computer Society, 24(1):5.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267.
Chen, R., Siriyal, S., and Prasanna, V. (2015). Energy and memory efficient mapping of bitonic sorting on fpga. In Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA '15, pages 240-249, New York, NY, USA. ACM.
Duarte, Jr., E. P. and Nanya, T. (1998). A hierarchical adaptive distributed system-level diagnosis algorithm. IEEE Transactions on Computers, 47(1):34-45.
Durad, M. H., Akhtar, M. N., and ul Haq, I. (2014). Performance analysis of parallel sorting algorithms using mpi. In 2014 12th International Conference on Frontiers of Information Technology, pages 202-207.
Elnozahy, Alvisi, Wang, and Johnson (2002). A survey of rollback-recovery protocols in message-passing systems. ACM Comput. Surveys, 34.
Fagg, G. E. and Dongarra, J. (2000). FT-MPI: Fault tolerant MPI, supporting dynamic applications in a dynamic world. In Recent advances in PVM and MPI, LNCS. Sprin-ger.
Forum, M. (2019a). Mpi forum website. http://mpi-forum.org/. Acessado em 26/01/2019.
Forum, M. (2019b). User-level failure mitigation. http://fault-tolerance. org/ulfm/ulfm-specification/. Acessado em 26/02/2019.
Freiling, F. C., Guerraoui, R., and Kuznetsov, P. (2011). The failure detector abstraction. ACM Comput. Surv., 43(2):9:1-9:40.
Gabriel, E., Fagg, G. E., Bosilca, G., Angskun, T., Dongarra, J. J., Squyres, J. M., Sahay, V., Kambadur, P., Barrett, B., Lumsdaine, A., Castain, R. H., Daniel, D. J., Graham, R. L., and Woodall, T. S. (2004). Open MPI: Goals, concept, and design of a next generation MPI implementation. In Proceedings, 11th European PVM/MPI Users' Group Meeting, pages 97-104, Budapest, Hungary.
Gropp, W., Lusk, E., Doss, N., and Skjellum, A. (1996). A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing, 22(6):789-828.
Johnson, S. L. (1984). Combining parallel and sequential sorting on a boolean n-cube. In Proceedings of the 1984 International Conference on Parallel Processing, pages 444-448.
Kumar, V. (2002). Introduction to Parallel Computing. Addison-Wesley Longman Pu-blishing Co., Inc., Boston, MA, USA, 2nd edition.
Lan, Y. and Mohamed, M. A. (1992). Parallel quicksort in hypercubes. In Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing: Technological Challenges of the 1990's, SAC '92, pages 740-746, New York, NY, USA. ACM.
Lee, D. and Batcher, K. E. (1994). On sorting multiple bitonic sequences. In 1994 International Conference on Parallel Processing Vol. 1, volume 1, pages 121-125.
MPI Forum (2015). Document for a standard message-passing interface 3.1. Technical report, University of Tennessee, http://www.mpi-forum.org/docs/mpi-3.1.
MPI-Forum (2019). User-level failure mitigation. https://bitbucket.org/ icldistcomp/ulfm/. Acessado em 26/02/2019.
Nassimi, D. and Sahni, S. (1979). Bitonic sort on a mesh-connected parallel computer. IEEE Transactions on Computers, C-28(1):2-7.
Pacheco, P. S. (1997). Parallel programming with MPI. Morgan Kaufmann.
Quinn, M. J. M. J. (2003). Parallel programming in C with MPI and OpenMP. McGraw-Hill, pub-MCGRAW-HILL:adr.
Sheu, J.-P., Chen, Y.-S., and Chang, C.-Y. (1992). Fault-tolerant sorting algorithm on hypercube multicomputers. J. Parallel Distrib. Comput., 16:185-198.
Velusamy, K., Rolinger, T. B., McMahon, J., and Simon, T. A. (2018). Exploring paral-lel bitonic sort on a migratory thread architecture. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1-7.
Publicado
24/09/2019
Como Citar
DOS SANTOS, Lucca ; TAVARES DE CAMARGO, Edson ; DUARTE JR., Elias P..
Uma Implementação MPI Tolerante a Falhas do Algoritmo Bitonic Sort. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 20. , 2019, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 48-61.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2019.7714.
