Implementación del Algoritmo Trace Alignment Empleando Técnicas de Programación Paralela
DOI:
https://doi.org/10.21501/21454086.1722Palabras clave:
CUDA, Minería de Procesos, OpenCL, OpenMP, Trace AlignmentResumen
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.Descargas
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
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
De conformidad con las normas nacionales e internacionales sobre derechos de autor, las políticas de publicación de la Universidad Católica Luis Amigó y de la revista Lámpsakos (indexada con ISSN: 2145-4086), yo(nosotros), manifiesto(amos):
1. El deseo de participar como articulista(s) y someter a las normas editoriales establecidas por la revista (nombre la revista) el artículo titulado (nombre del artículo),
2. El compromiso de no retirar el artículo hasta no terminar el proceso de edición del número de la revista en curso.
3. Que el artículo es original e inédito y no ha sido postulado o presentado conjuntamente en otra(s) revista(s); por tanto, los derechos del artículo en cuestión no han sido cedidos con antelación y sobre ellos no pesa ningún gravamen ni limitación en su uso o utilización.
4. La inexistencia de conflicto de interés con institución o asociación comercial de cualquier índole.
5. Haber incorporado las citas y referencias de otros autores, tendientes a evitar el plagio. En consecuencia, afirmo que de ser publicado el artículo, no se violarán derechos de autor, de propiedad intelectual o de privacidad de terceros. Así mismo, de ser necesario, existe forma de evidenciar los permisos respectivos sobre derechos de autor originales para los aspectos o elementos extraídos de otros documentos como textos de más de 500 palabras, tablas, gráficas, entre otros. En caso de presentarse cualquier tipo de reclamación o acción por parte de un tercero en cuanto a los derechos de autor sobre el artículo, el(los) autor(es) asumirán toda la responsabilidad, y saldrán en defensa de los derechos aquí cedidos. Por tanto, para todos los efectos, la revista Lámpsakos de la Fundación Universitaria Luis Amigó actúa como un tercero de buena fe.
6. Que en el evento de publicarse el artículo, cedo(emos) a título gratuito y con carácter de exclusividad la integridad de los derechos patrimoniales así como los derechos de impresión, reimpresión y de reproducción por cualquier forma y medio, sin ninguna limitación en cuanto a territorio se refiere, en favor de la revista Lámpsakos de la Universidad Católica Luis Amigó.
7. Reconocer como coautores y/o colaboradores, a todos quienes participaron en ese rol y no se ha omitido a ninguno.
