Paralelización del Algoritmo Expectación–Maximización Utilizando OpenCL
DOI:
https://doi.org/10.21501/21454086.1361Palabras clave:
Arquitecturas híbridas, Computación Paralela y Distribuida, Expectación-Maximización, ejecución paralela, OpenCL.Resumen
Actualmente, las organizaciones y empresas almacenan grandes volúmenes de datos para lograr sus propósitos. Una de las variantes para obtener información valiosa consiste en el empleo de la Minería de datos. Dentro de esta, existen diferentes tareas, una de ellas es el agrupamiento. En esta tarea los datos se agrupan según sus semejanzas entre si y diferencias con elementos de otros grupos. Dentro de los algoritmos que realizan estos agrupamientos se encuentra Expectación-Maximización, el cual presenta elevados tiempos de ejecución en la medida que aumenta el tamaño de los datos. En el presente artículo se discute acerca de la paralelización del algoritmo, utilizando técnicas de programación paralela. El diseño del algoritmo propuesto se basa en el uso de las tarjetas de procesamiento gráfico, GPU. OpenCL, lenguaje empleado para la programación en arquitecturas híbridas, permite aprovechar las arquitecturas de hardware disponibles, con lo que se logra disminuir el tiempo de ejecución de la implementación realizada. La razón principal por lo cual es posible mejorar este tiempo se debe a la cantidad de procesos paralelos que se pueden lanzar en hilos de procesamientos independientes. Para el logro de los resultados descritos se integran conocimientos del campo de la Minería de datos y la Computación Paralela y Distribuida. Como parte de esta investigación, se realizó una implementación del algoritmo utilizando las bibliotecas de OpenCL, para disminuir su tiempo de ejecución. La implementación logra disminuir en un 82% la implementación secuencial. Esto significa que el algoritmo paralelo se ejecuta 5,5 veces más rápido que su correspondiente implementación secuencial.Descargas
Referencias
J. Hernández-Orallo, J. Ramírez-Quintana, "Introduccíon A La Minería De Datos". Primera edición, 2004, Madrid, Pearson Prentice Hall S.A. 680p.
A. P. Dempster, D. B. Rubin,"Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society, 1977. pp. 39-45.
Collins, M. "The EM Algorithm", 1997, 28p. Disponible en: http://faculty.washington.edu/fxia/courses/LING572/EM_collins97.pdf
S.Purcell. "Maximum Likelihood Estimation (MLE)", 2007, Disponible en: http://statgen.iop.kcl.ac.uk/bgim/mle/sslike_1.html
I. Foster, "Designing and Building Parallel Programs", 1995: Addison-Wesley. Disponible en: http://www.mcs.anl.gov/~itf/dbpp
OpenMP.org. "The OpenMP API Specification For Parallel Programming". 2014; Disponible en: http://www.openmp.org
R. Pas, "An Overview of OpenMP 3.0", IWOMP 2009, TU Dresden (Alemania), Disponible en: https://iwomp.zih.tu-dresden.de/downloads/2.Overview_OpenMP.pdf
H. Hoeger, "Introducción a la Computación Paralela", Centro Nacional de Cálculo Científico Universidad de Los Andes, Mérida (Venezuela) - CeCalCULA, 2011, 48p
Tosini, M. "Introducción a las Arquitecturas Paralelas", 2011, 51p, Disponible en: http://bit.ly/1H9pylQ
NVIDIA, "High Performance Computing with CUDA", Users Group Conference", San Diego, CA (EEUU), 2009.
J.A. Raya-Vaquera, E.X. Martín-Rull, "Aceleración con CUDA de Procesos 3D". 2009.
Wang, P., "OpenCL Optimization", GPU Technology Conference, San José, CA (EEUU), 2009.
A. Munshi, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Boston, MA (EEUU), Pearson Education, 2012
A. Barak, E. Levy, A. Shiloh, "A Package for OpenCL Based Heterogeneous Computing on Clusters with Many GPU Devices", IEEE International Conference on Cluster Computing Workshops and Posters, Heraklion, Isla de Creta, 2010.
B. R. Gaster, L. Howes, D. R. Kaeli, P. Mistry, D. Schaa, "Chapter 13 - OpenCL Profiling and Debugging", En: Heterogeneous Computing with Opencl, Editado por B. R. Gaster, L. Howes, D R. KaeliPerhaad, M.D. Schaa, M. Kaufmann, Boston, 2013, pp. 243-261, ISBN 9780124058941,
NVIDIA, "NVIDIA CUDA Compute Unified Device Architecture", 2014. Disponible en: http://www.nvidia.com/object/cuda_home_new.html
E.W. Weisstein, "K-Means Clustering Algorithm". 2014. Disponible en: http://mathworld.wolfram.com/K-MeansClusteringAlgorithm.html
M.I. Ángeles-Larrieta, A.M. Santillán-Gómez "Minería de datos: Concepto, características, estructura y aplicaciones", Contaduría y Administración, N° 190, 2004. p. 79-84.
Vallejos, S.J. "Minería de Datos. Argentina: Universidad Nacional del Nordeste" Facultad de Ciencias Exactas, Naturales y Agrimensura, 2006.
P. Graham, "Parallel Computation Notes", 1996. Disponible en: http://www.cs.umanitoba.ca/~comp4510/notesDIR/COMP4510Models_2up.pdf.
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.
