Compresión BZIP2 optimizada usando colas libres de bloqueo
DOI:
https://doi.org/10.15359/ru.31-2.3Palabras clave:
Programación informática, Procesamiento de datos, Lenguaje de programación.Resumen
Debido a que la tendencia actual es tener más y más procesadores (cores) disponibles en cada computadora, la escalabilidad de las estructuras de datos usadas en programación paralela debe ser considerada cuidadosamente, para así garantizar que ellas saquen ventaja de los procesadores disponibles. Debido al aumento en la contención, usualmente las estructuras de datos basadas en bloqueos no mejoran su rendimiento proporcionalmente al incrementar el número de procesadores. El uso de estructuras de datos libres de bloqueos bien diseñadas, tales como las colas first in-first out, puede mejorar el rendimiento de un programa paralelo, cuando hay varios procesadores disponibles. En este trabajo se diseña e implementa una versión paralela de bzip2, un programa para compresión y descompresión de datos muy popular, usando colas libres de bloqueos en lugar de las basadas en bloqueos, y aplicando una estrategia de dos buffers de salida. Se compara el rendimiento de la implementación libre de bloqueos contra implementaciones basadas en bloqueos. Se midió el tiempo de compresión usando diferente número de procesadores y diferentes tamaños de bloques. Coincidiendo con la hipótesis de trabajo, los resultados muestran que la implementación paralela libre de bloqueos supera las otras implementaciones.
Referencias
Boost C++ Library (n.d.). (2013). Retrieved from https://svn.boost.org/trac/boost/
Burrows, M., & Wheeler, D. J. (1994). A block-sorting lossless data compression algorithm. (SRC Research Report 124). California: Digital systems research center. http://www.hpl.hp.com/techreports.
Feldman, S. & Dechev, D. (2015). A wait-free multi-producer multi-consumer ring buffer. ACM SIGAPP Applied Computing Review, 15(3), 59-71. http://dx.doi.org/10.1145/2835260.2835264
Gilchrist, J. (2004). Parallel data compression with bzip2. Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems(PDCS). http://gilchrist.ca/jeff/comp5704/Final_Paper.pdf
Huffman, D.A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the I.R.E. http://dx.doi.org/10.1109/jrproc.1952.273898
Isakov, K. (2005). Bzip2smp. Retrieved from http://bzip2smp.sourceforge.net
Jannesari, A., Pankratius, V. & Tichy, W. (1990). Parallelizing bzip2-a case study in multicore software engineering. IEEE Software, 26(6). Recovered from https://www.semanticscholar.org
Ladan-mozes, E. and Shavit, N. (2004). An optimistic approach to lock-free fifo queues. Proceedings of the 18th International Symposium on Distributed Computing, Springer, Berlin, Germany. http://dx.doi.org/10.1007/978-3-540-30186-8_9
Marcais, G. & Kingsford, C. (2011). A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics, 27, 764–770. http://dx.doi.org/10.1093/bioinformatics/btr011
Michael, M., & Scott, M. (1996). Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing. http://dx.doi.org/10.1145/248052.248106
Neal, R., Witten, I. & Cleary, J. (1987). Arithmetic coding for data compression. Communications of the ACM, 30(6), 520-540. http://dx.doi.org/10.1145/214762.214771
Seward, J. (2010). bzip2. Retrieved from http://www.bzip.org/
Valois, D. (1994). Implementing lock-free queues. Proceeding of the Seventh International Conference On Parallel and Distributed Computing Systems, 1994.
Welch, T. (1984). A technique for high-performance data compression. IEEE Computer, 17(6). http://dx.doi.org/10.1109/MC.1984.1659158
Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics Bulletin. 1 (6). http://dx.doi.org/10.2307/3001968
Zhang, D. & Dechev, D. (2016). A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists. IEEE Trans. Parallel Distrib. Syst. 27(3) 613-626. http://dx.doi.org/10.1109/tpds.2015.2419651
Ziv, J., & Lempel, A. (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5). 530-536. http://dx.doi.org/10.1109/tit.1978.1055934
Descargas
Publicado
Número
Sección
Licencia
Los autores que publican en esta revista están de acuerdo con los siguientes términos:
1. Los autores garantizan a la revista el derecho de ser la primera publicación del trabajo al igual que licenciado bajo una Creative Commons Attribution License que permite a otros compartir el trabajo con un reconocimiento de la autoría del trabajo y la publicación inicial en esta revista.
2. Los autores pueden establecer por separado acuerdos adicionales para la distribución no exclusiva de la versión de la obra publicada en la revista (por ejemplo, situarlo en un repositorio institucional o publicarlo en un libro), con un reconocimiento de su publicación inicial en esta revista.
3. Los autores han afirmado poseer todos los permisos para usar los recursos que utilizaron en el artículo (imágenes, tablas, entre otros) y asumen la responsabilidad total por daños a terceros.
4. Las opiniones expresadas en el artículo son responsabilidad de los autores y no necesariamente representan la opinión de los editores ni de la Universidad Nacional.
Revista Uniciencia y todas sus producciones se encuentran bajo una Licencia Creative Commons Atribución-NoComercial-SinDerivadas 4.0 Unported.
No existe costo por acceso, revisión de propuestas ni publicación para autores y lectores.
