PDF de programación - Optimización en Paralelo Basada en Poblaciones Usando GPGPU

Conciencia Tecnológica No. 43, Enero-Junio 2012

Optimización en Paralelo Basada en Poblaciones Usando GPGPU

Investigación

MSC. Iliana Castro Liera1, Dr. Marco Antonio Castro Liera2 , M.C. Jesús Antonio Castro2
1Depto. de Sistemas y Computación, 2 División de Estudios de Posgrado e Investigación

Instituto Tecnológico de La Paz, México, Blvd. Forjadores de B.C.S., #4720 Col 8 de Octubre

La Paz, B.C.S., CP 23080, Tel: 01(612)1210424 ext 116, Fax: 01(612)1211295

[email protected], [email protected], [email protected].

Resumen

En este artículo se muestran dos estrategias para
aprovechar el poderío computacional de las unidades
de procesamiento gráfico de propósito general GPGPU
(General-Purpose computation on Graphics Processing
Unit) con arquitectura CUDA (Compute Unified
Device Architecture) para la solución de problemas de
optimización utilizando algoritmos genéticos (AG) y
optimización por enjambre de partículas (PSO, Particle
Swarm Optimization).

Se muestra que esta implementación en una sola
GPU consigue resultados de buena calidad en tiempos
menores que los de un cluster de 16 computadoras con
32 núcleos.

Palabras clave: GPGPU, AG, PSO, CUDA.

videojuegos, tienen una tarjeta gráfica poderosa que la
mayor parte del tiempo es desaprovechada.

En el apartado de Fundamentos Teóricos se
explican las bases de los Algoritmos Genéticos y la
Optimización por Enjambres de Partículas.

En la sección de Materiales y Métodos, se describen
los fundamentos de la arquitectura CUDA, y la manera
en que se implementaron los algoritmos en ella. Se
describen también la batería de funciones utilizadas
para medir la eficacia y eficiencia de la implementación.
En las secciones de Resultados y Discusión y
Conclusiones se muestra que utilizando una sola GPU
se obtienen soluciones de buena calidad en tiempos
menores que los requeridos por un cluster de 16
computadoras.

Fundamentos Teóricos

Abstract

Optimización por Enjambres de Partículas

This paper describes two successful strategies for using
the computing power of a General Purpose Graphics
Processing Unit (GPGPU) with CUDA (Compute
Unified Device Architecture) to solve hard numerical
optimization problems using genetic algorithms (GA)
and particle swarm optimization (PSO).

The proposed algorithm executed on a single GPU

outperforms a cluster of 16 computers and 32 cores.

Key words: GPGPU, GA, PSO, CUDA.

Introducción

El presente trabajo está siendo desarrollado en el I.T.
de La Paz con apoyo de la DGEST con el proyecto
de investigación PAZ-MSC-2009-201 y el periodo
sabático AS-1-200/2011, cuyos resultados parciales
fueron publicados en [1] [2].

Las nuevas herramientas computacionales nos han
permitido disminuir el tiempo necesario para encontrar
la solución a los problemas de optimización y han
hecho posible que abordemos nuevos problemas, tan
complejos, que sin ellas simplemente no podríamos
resolver. Actualmente, muchas computadoras están
equipadas con procesadores que incluyen más de un
núcleo y en muchos casos, gracias al interés por los

Los métodos de optimización por enjambres de
partículas, propuestos en 1995 por Russ C. Eberhart y
James Kennedy [5] están basados en el comportamiento
de las bandadas de aves y los cardúmenes de peces
en los que su movimiento se guía por la búsqueda de
alimento o para escapar de los predadores y en los que
el grueso de la población sigue al miembro que posee
mayor conocimiento del entorno.

Cada partícula en el enjambre recuerda su posición
(xi), su velocidad (vi) y aptitud (fi), así como su mejor
posición y aptitud históricas.

El algoritmo inicia generando aleatoriamente un
conjunto de partículas, denominado enjambre. Cada
partícula calcula su velocidad usando (1) y su nueva
posición usando (2) para cada dimensión d; esto se
realiza una cantidad preestablecida de generaciones o
hasta alcanzar una condición de parada.

donde xh representa la mejor posición histórica de la
partícula, w un peso inercial, c1 la confianza en su
propia información y c2 la confianza en la información
social; r1 y r2 son valores generados aleatoriamente con
una distribución uniforme en el intervalo de [0,1].

24

OPTIMIZACIÓN EN PARALELO BASADA EN POBLACIONES USANDO GPGPU

MSC. Iliana Castro Liera, Dr. Marco Antonio Castro Liera, M.C. Jesús Antonio Castro

Si se utiliza la estrategia global (gbest), xg
representa la mejor posición del enjambre; si se
utiliza la estrategia local (lbest), xg representa la mejor
posición del vecindario. En general la estrategia gbest
tiende a converger más rápido que lbest, pero es más
probable quedar atrapado en un óptimo local. Podemos
también decir que gbest es un caso especial de lbest, en
donde el tamaño del vecindario es igual al de todo el
enjambre [6].

Algoritmos Genéticos

Fueron propuestos por Holland [7] en su versión
original y basan su comportamiento en la evolución de
las especies, en donde sobreviven los más adaptados al
entorno.

El concepto central de los algoritmos genéticos es
el de población, que se define como un conjunto de
individuos Ci donde i=1,…, μ.

Los algoritmos genéticos inician con una población
Pg generada de forma aleatoria. Posteriormente, de
manera iterativa, se calcula la aptitud de sus individuos
y se aplican los operadores genéticos (selección,
cruce y mutación) para determinar a los individuos
que formarán la siguiente población Pg+1, donde g es
el número de generaciones ó iteraciones que se han
ejecutado. Generalmente, el criterio de parada es el
arribo a una generación gmax, fijada antes de iniciar el
algoritmo.

Materiales y métodos

CUDA

CUDA es una tecnología de GPGPU desarrollada
por NVIDIA en 2006 cuando liberaron el lenguaje
CUDA C que permite el desarrollo de aplicaciones de
propósito general en paralelo utilizando los múltiples
procesadores de la tarjeta gráfica [3]. La arquitectura
CUDA se muestra en la figura 1.

Los elementos de la arquitectura CUDA son
[4]: los hilos en donde se ejecutan las funciones
simultáneamente y tienen su propio espacio de
memoria; bloques, formados por un conjunto de hilos
e incluyen un espacio de memoria compartida para su
comunicación; una malla, que incluye los bloques que
se ejecutan en un dispositivo, con distintas zonas de
memoria comunes a todos los bloques (figura 1).

Una función que se ejecuta en la tarjeta gráfica
(GPU) se denomina kernel. Cuando se lanza un kernel,
es necesario informar a la GPU cuantos bloques (BLK)
e hilos (THR) se ejecutarán, utilizando la siguiente
sintaxis:

nombre_kernel<<<BLK,THR>>>(parámetros);

Figura 1. Arquitectura CUDA.

La GPU organiza el trabajo en sus multiprocesado-

res como se muestra en la figura 2 [4].

Para aprovechar al máximo la capacidad de
procesamiento y evitar tener recursos desperdiciados,
es importante que la cantidad de bloques sea un
múltiplo de la cantidad de núcleos disponibles.

Figura 2. Distribución de bloques

En virtud de que las unidades de proceso son
homogéneas, la asignación de carga se efectúa de
manera estática y simétrica. Aunque la asignación de
carga dinámica en estructuras de cómputo heterogéneas
brinda la ventaja de una mayor eficiencia en el
aprovechamiento del poder computacional, en el caso
que nos compete, significaría agregar complejidad al
algoritmo sin obtener beneficios de desempeño.

Implementación de PSO con CUDA

En cada bloque se procesó un enjambre de t partículas
y cada hilo procesó una partícula, Figura 3.

Cada PDB iteraciones ocurre un proceso de dispersión
de la información, que consiste en que cada bloque
comunica la información de su mejor posición con una
topología de anillo; como se muestra en la figura 4.

Conciencia Tecnológica No. 43, Enero-Junio 2012

25

OPTIMIZACIÓN EN PARALELO BASADA EN POBLACIONES USANDO GPGPU

MSC. Iliana Castro Liera, Dr. Marco Antonio Castro Liera, M.C. Jesús Antonio Castro

La migración se llevó a cabo con un periodo del
10% del total de generaciones y una tasa de migración
(MR) aproximada al 3% de la población.

En el siguiente pseudocódigo se muestra la
asignación de tareas y se ilustra qué parte se ejecuta en
el CPU y cuál se ejecuta en el GPU:

CPU:
Lanza el kernel para Crear BLK poblaciones
para i = 1 hasta GMAX/PMB
Lanza kernel AG
Lanza kernel Migración
Recibe la major posición de las BLK
poblaciones
Despliega la mejor posición global como la
solución del problema de optimización.
GPU:
KERNEL Crear
para i=1 hasta MU
inicializa Xi y Fi
KERNEL Pso
G = 0;
Mientras que (G<PMB)
G = G+1
ejecuta selección
para i = 1 hasta tamaño_enjambre
ejecuta cruce por torneo
ejecuta mutación
KERNEL Ordenar
para i=1 hasta MU
para j=2 hasta MU-1
si Xj mejor que Xi
intercambia(Xi,Xj)
KERNEL Migración
Para i=0 hasta MR-1
Xi = XMR-i
Fi = FMR-i

Primeramente se ordenó la población, para poder
migrar los MR mejores del bloque siguiente en los MR
peores individuos del bloque actual (ubicados al final
del bloque), figura 5.

Figura 5. Migración. Se sustituyen los MU peores
individuos con los mejores del bloque siguiente.

Funciones de prueba

Se optimizaron las funciones de Rastrigin, Ackley,
Schwefel y Weierstrass, en 30 dimensiones propuestas,
en
la Competencia de Computación Evolutiva
(CEC’05) [5].

La función de Rastrigin (5) es una función escalable,
separable, multimodal con un óptimo global en el

Figura 3. Asignación de enjambres en el GPU.

Figura 4. Dispersión.

En el siguiente