Implementación del Algoritmo Trace Alignment Empleando Técnicas de Programación Paralela

Marlis Fulgueira-Camilo, Ernesto Insúa-Suárez, Humberto Díaz-Pando

Resumen


En este artículo se refiere un algoritmo del campo de la minería de procesos, Trace Alignment, cuyo objetivo es detectar anomalías en una secuencia de patrones e identificar patrones comunes. El análisis de las trazas generadas por los procesos de negocios puede tardar un tiempo considerable, teniendo en cuenta que una gran parte de los procesos, hoy en día, se encuentran informatizados. El algoritmo en cuestión es paralelizado empleando el paradigma de memoria compartida, específicamente OpenMP, CUDA y OpenCL. El diseño paralelo propuesto cuenta de dos etapas: una primera donde se paraleliza la construcción de la matriz de similitud y una segunda donde se alinean pares o conjuntos de trazas a la misma vez. Los resultados obtenidos indican que, con el diseño propuesto, los mejores tiempos se obtienen empleando OpenMP para todos los juego de datos propuestos.

Palabras clave


CUDA; Minería de Procesos; OpenCL; OpenMP; Trace Alignment

Texto completo:

PDF

Referencias


W. Van Der Aalst, Process mining: discovery, conformance and enhancement of business processes: Springer Science & Business Media, 2011. ISBN: 978-3-642-19344-6

A. Weijters, W. M. van Der Aalst, and A. A. De Medeiros, "Process mining with the heuristics miner-algorithm," Technische Universiteit Eindhoven, Tech. Rep. WP, vol. 166, pp. 1-34, 2006. DOI: 10.1.1.118.8288

R. J. C. Bose and W. M. van der Aalst, "Process diagnostics using trace alignment: opportunities, issues, and challenges," Information Systems, vol. 37, pp. 117-141, 2011. DOI: 0.1016/j.is.2011.08.003

N. Carriero and D. Gelernter, How to Write Parallel Programs: A First Course 1st ed.: MIT Press, 1992. ISBN: 0-262-03171-X

Z. Du, Z. Yin, and D. Bader, "A tile-based parallel Viterbi algorithm for biological sequence alignment on GPU with CUDA," presented at the Proc. of the IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum (IPDPSW), Atlanta, GA, 2010. DOI: 10.1109/IPDPSW.2010.5470903

T. Siriwardena and D. Ranasinghe, "Accelerating global sequence alignment using CUDA compatible multi-core GPU," in Information and Automation for Sustainability (ICIAFs), 2010 5th International Conference on, Colombo, 2010, pp. 201-206. DOI: 10.1109/ICIAFS.2010.5715660

L. Hasan, M. Kentie, and Z. Al-Ars, "GPU-accelerated protein sequence alignment," in Engineering in Medicine and Biology Society, EMBC, 2011 Annual International Conference of the IEEE, 2011, pp. 2442-2446. ISBN: 978-1-4244-4121-1

M. R. Babu, "Parallelized hierarchical expected matching probability for multiple sequence alignment," Journal of Theoretical & Applied Information Technology, vol. 64, 2014. URL: http://www.jatit.org/volumes/Vol64No2/10Vol64No2.pdf

A. E. C. González, "La métrica de Levenshtein," Revista de Ciencias Básicas UJAT, vol. 7, pp. 35-43, 2008. URL: www.publicaciones.ujat.mx/publicaciones/revista_dacb/Acervo/v7n2OL/v7n2.pdf#page=37

D. Shrimankar and S. Sathe, "Performance Analysis of OpenMP and MPI for NW algorithm on multicore architecture," International Journal of Advanced Studies in Computers, Science and Engineering, vol. 3, p. 23, 2014. URL: http://www.ijascse.org/volume-3-issue-6/OpenMp.pdf

Sharma C and V. A.K. (2014, Parallel Approaches in Multiple Sequence Alignments. International Journal of Advanced Research in Computer Science and Software Engineering 4(2). URL: http://www.ijarcsse.com/docs/papers/Special_Issue/icadet2014/Lord_35.pdf

A. Y. Zomaya, Parallel computing for bioinformatics and computational biology: models, enabling technologies, and case studies vol. 55: John Wiley & Sons, 2006. ISBN: 978-0-471-71848-2 ISBN: 978-1-4613-6601-0

D. E. Lenoski and W.-D. Weber, Scalable shared-memory multiprocessing: Elsevier, 2014. ISBN: 978-1-4613-6601-0

N. Matloff, Programming on Parallel Machines University of California: Davis, 2012.URL: http://heather.cs.ucdavis.edu/~matloff/158/PLN/ParProcBook.pdf

A. OpenMP, "The OpenMP API specification for parallel programming," http://openmp.org, 2010., 2010.

B. Chapman, G. Jost, and R. Van Der Pas, Using OpenMP: portable shared memory parallel programming vol. 10: MIT press, 2008. ISBN: 978-0-262-53302-7

OpenMP and A. R. Board, "OpenMP Application Program Interface", 3.0 ed., 2008. URL: http://www.openmp.org/mp-cuments/spec30.pdf

M. Sato, "OpenMP: parallel programming API for shared memory multiprocessors and on-chip multiprocessors," in Proceedings of the 15th international symposium on System Synthesis, 2002, pp. 109-111. ISBN: 1-58113-576-9

S. Cook, CUDA programming: a developer's guide to parallel computing with GPUs: Newnes, 2012. ISBN: 978-0124159334

R. Farber, CUDA application design and development: Elsevier, 2011. ISBN: 978-0-12-388426-8

J. Sanders and E. Kandrot. (2010). CUDA by example: an introduction to general-purpose GPU programming. ISBN: 978-0131387683

AMD, Accelerated Parallel Processing OpenCL Programming Guide: AMD, 2012.URL: http://developer.amd.com/wordpress/media/2013/07/AMD_Accelerated_Parallel_Processing_OpenCL_Programming_Guide-rev-2.7.pdf

B. e. R. Gaster, L. Howes, D. R. Kaeli, P. Mistry, and D. Schaa, Heterogeneous Computing with OpenCL, 2nd ed.: Morgan Kaufmann, 2013. ISBN: 970-0-12-405894-1

M. Scarpino, "Opencl in Action: How to Accelerate Graphics and Computation. NY," ed: USA: Manning, 2012. ISBN: 9781617290176

P. S. Pacheco, An Introduction to Parallel Programming, 1st ed.: Morgan Kaufmann, 2011. ISBN: 0080921442

M. Abd-El-Barr and H. El-Rewini, Fundamentals of Computer Organization and Architecture 1st ed. New Jersey, USA: Wiley-Interscience, 2004. ISBN: 0-471-4674-1-3

F. Gebali, Algorithms and Parallel Computing, 1st ed.: Wiley, 2011. ISBN: 978-0-470-90210-3

A. Grama, A. Gupta, G. Karyspis, and V. Kumar, Introduction to Parallel Computing, 2nd ed.: Addison Wesley, 2003. ISBN: 978-0201648652




DOI: https://doi.org/10.21501/21454086.1722

Enlaces refback

  • No hay ningún enlace refback.




Copyright (c) 2016

 
Directora/Editora - Ingrid Durley Torres Pardo

Correo: lampsakos@amigo.edu.co

ISSN (En línea): 2145-4086

DOI de la revista: https://doi.org/10.21501/issn.2145-4086

Universidad Católica Luis Amigó - Transversal 51A #67B 90. Medellín - Colombia.

 


 © 2019 Universidad Católica Luis Amigó

    

La revista y los textos individuales que en esta se divulgan están protegidos por las leyes de copyright y por los términos y condiciones de la Licencia Creative Commons Atribución-No Comercial-Sin Derivar 4.0 Internacional. Permisos que vayan más allá de lo cubierto por esta licencia pueden encontrarse en http://www.funlam.edu.co/modules/fondoeditorial/

Derechos de autor. El autor o autores pueden tener derechos adicionales en sus artículos según lo establecido en la cesión por ellos firmada.

 

Se recomienda visualizar este contenido con los navegadores: Mozilla Firefox, Google Chrome, Safari.