Paralelización del Algoritmo Expectación–Maximización Utilizando OpenCL

Ernesto Insua-Suárez, Marlis Fulgueira-Camilo, Venus Henry-Fuenteseca

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.

Palabras clave


Arquitecturas híbridas, Computación Paralela y Distribuida, Expectación-Maximización, ejecución paralela, OpenCL.

Texto completo:

PDF

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.




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

Enlaces refback

  • No hay ningún enlace refback.




Copyright (c)

 
Directora/Editora - Ingrid Durley Torres Pardo

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.