Trace Alignment Algorithm Implementation Using Parallel Programming Techniques
DOI:
https://doi.org/10.21501/21454086.1722Keywords:
CUDA, OpenCL, OpenMP, Process Mining, Trace AlignmentAbstract
The article refers to an algorithm in the field of mining processes, Trace Alignment, aimed at detecting anomalies in a sequence of patterns and identify common patterns. The analysis of the traces generated by the business process may take considerable time, given that a large part of the process, today, are computerized. The algorithm in question is parallelized using the shared memory paradigm, specifically OpenMP, CUDA and OpenCL. The parallel proposed design has two stages: a first construction where the similarity matrix and a second where pairs or sets of traces at the same time is aligned. The results indicate that, with the proposed design, the best times are obtained using OpenMPDownloads
References
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
Downloads
Published
How to Cite
Issue
Section
License
In accordance with national and international copyrights, as well as publishing policies of "Fundación Universitaria Luis Amigó" and its Journal "Lámpsakos" (indexed with ISSN : 2145-4086), I (we ) hereby manifest:1. The desire to participate as writers and submit to the rules established by the magazine publishers.
2. The commitment not to withdraw the manuscript until the journal finishes the editing process of the ongoing issue.
3. That article is original and unpublished and has not been nominated or submitted together in another magazine; therefore, the rights of the article in evaluation have not been assigned in advance and they do not weigh any lien or limitation for use.
4. The absence of conflict of interest with commercial institution or association of any kind
5. The incorporation of the quotes and references from other authors, tending to avoid plagiarism. Accordingly, the author affirms that the paper being published do not violate copyright, intellectual property or privacy rights of third parties. Morover, if necessary there is a way of demonstrating the respective permits original copyright to the aspects or elements taken from other documents such as texts of more than 500 words, tables, graphs, among others. In the event of any claim or action by a third party regarding copyright on the article, the author (s) will assume full responsibility and come out in defense of the rights herein assigned. Therefore, for all purposes, the Journal "Lámpsakos" of the "Fundación Universitaria Luis Amigó" acts as a third party in good faith.
6. In the event of the publication of the article, the authors free of charge and on an exclusive basis the integrity of the economic rights and the right to print, reprint and reproduction in any form and medium, without any limitation as to territory is concerned, in favor of the Journal "Lámpsakos" of the "Fundación Universitaria Luis Amigó".
