Implementação e Avaliação de Algoritmos de Ordenação Paralela em MapReduce
Resumo
Quantidades cada vez maiores de dados, conhecidas como Big Data, são um fato do mundo real e um desafio em termos de processamento de dados. Ordenação é uma das tarefas mais comuns em computação e ordenar grandes massas de dados é uma necessidade em vários processos. O modelo de programação paralela MapReduce tem sido amplamente adotado para processar dados em larga escala em agrupamentos de computadores. Apresentamos neste artigo a implementação de dois algoritmos paralelos de ordenação, o Quicksort Paralelo e o Ordenação por Amostragem. Ambos foram implementados no ambiente de programação MapReduce/Hadoop e testados quanto ao seu desempenho para ordenar dados distribuídos em várias máquinas. Uma variedade de experimentos revela o comportamento de ambos os algoritmos e indica que o algoritmo Ordenação por Amostragem apresenta melhor desempenho.
Palavras-chave:
Ordenação paralela, computação paralela, MapReduce
Referências
J. Gantz, “The 2011 Digital Universe Study: Extracting Value from Chaos,” 2011. [Online]. Available: http://www.emc.com/collateral/demos/microsites/emc-digital-universe-2011/index.htm
K. Asanovic, R. Bodik, J. Demmel, T. Keaveny, K. Keutzer, J. Kubiatowicz, N. Morgan, D. Patterson, K. Sen, J. Wawrzynek, D. Wessel, and K. Yelick, “A View of the Parallel Computing Landscape,” Commun. ACM, vol. 52, no. 10, pp. 56–67, Oct. 2009.
J. Lin and C. Dyer, Data-Intensive Text Processing with MapReduce. Morgan & Claypool Publishers, 2010.
J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008.
T. White, Hadoop: The Definitive Guide, 1st ed. Sebastopol, CA, USA: O’Reilly, June 2009.
Hadoop, “ Welcome to Apache Hadoop!” Website, 2012. [Online]. Available: http://hadoop.apache.org
C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis, “Evaluating MapReduce for Multi-core and Multiprocessor Systems,” in Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture. Washington, DC, USA: IEEE Computer Society, 2007, pp. 13–24.
V. Kale and E. Solomonik, “Parallel Sorting Pattern,” in Proceedings of the 2010 Workshop on Parallel Programming Patterns, ser. ParaPLoP ’10. New York, NY, USA: ACM, 2010, pp. 10:1–10:12.
N. M. Amato, R. Iyer, S. Sundaresan, and Y. Wu, “A Comparison of Parallel Sorting Algorithms on Different Architectures,” Texas A & M University, College Station, TX, USA, Tech. Rep., 1998.
L. Cherkasova, “Performance Modeling in MapReduce Environments: Challenges and Opportunities,” in Proceedings of the Second Joint WOSP/SIPEW International Conference on Performance Engineering, ser. ICPE ’11. New York, NY, USA: ACM, 2011, pp. 5–6.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT Press, 2009.
T. Rauber and G. Rünger, Parallel Programming for Multicore and Cluster Systems. Berlin, Heidelberg: Springer Verlag, 2010.
K. Asanovic, R. Bodik, J. Demmel, T. Keaveny, K. Keutzer, J. Kubiatowicz, N. Morgan, D. Patterson, K. Sen, J. Wawrzynek, D. Wessel, and K. Yelick, “A View of the Parallel Computing Landscape,” Commun. ACM, vol. 52, no. 10, pp. 56–67, Oct. 2009.
J. Lin and C. Dyer, Data-Intensive Text Processing with MapReduce. Morgan & Claypool Publishers, 2010.
J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008.
T. White, Hadoop: The Definitive Guide, 1st ed. Sebastopol, CA, USA: O’Reilly, June 2009.
Hadoop, “ Welcome to Apache Hadoop!” Website, 2012. [Online]. Available: http://hadoop.apache.org
C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis, “Evaluating MapReduce for Multi-core and Multiprocessor Systems,” in Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture. Washington, DC, USA: IEEE Computer Society, 2007, pp. 13–24.
V. Kale and E. Solomonik, “Parallel Sorting Pattern,” in Proceedings of the 2010 Workshop on Parallel Programming Patterns, ser. ParaPLoP ’10. New York, NY, USA: ACM, 2010, pp. 10:1–10:12.
N. M. Amato, R. Iyer, S. Sundaresan, and Y. Wu, “A Comparison of Parallel Sorting Algorithms on Different Architectures,” Texas A & M University, College Station, TX, USA, Tech. Rep., 1998.
L. Cherkasova, “Performance Modeling in MapReduce Environments: Challenges and Opportunities,” in Proceedings of the Second Joint WOSP/SIPEW International Conference on Performance Engineering, ser. ICPE ’11. New York, NY, USA: ACM, 2011, pp. 5–6.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT Press, 2009.
T. Rauber and G. Rünger, Parallel Programming for Multicore and Cluster Systems. Berlin, Heidelberg: Springer Verlag, 2010.
Publicado
23/10/2013
Como Citar
MURTA, Cristina Duarte; GONÇALVES, Mariane Raquel Silva; PINHÃO, Paula de Morais.
Implementação e Avaliação de Algoritmos de Ordenação Paralela em MapReduce. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 14. , 2013, Porto de Galinhas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 11-18.
DOI: https://doi.org/10.5753/wscad.2013.16768.
