PDF de programación - Programación Paralela

Programación Paralela

Jesús Manuel Mager Hois

8 de marzo de 2013

1

Índice

1. Introducción

2. Características

2.1. Equipos multicore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Memoria compartida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Consideraciones sobre C

3.1. API de OpenMP para C . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Directivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2. Biblioteca de rutinas de tiempo de ejecución . . . . . . . . . . . . . .
3.2. Sistema de producción multiplataforma (Autoconf y OpenMP) . . . . . . . .

4. Manos a la obra

4.1. Primer programa en OpenMP (directiva parallel)
. . . . . . . . . . . . . . .
4.2. Directiva for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Directiva section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Directiva single . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Directiva barrier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Directiva critical
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7. Directiva atomic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Implementación

5.1.

Implementación de búsqueda secuencial . . . . . . . . . . . . . . . . . . . . .

3

3
3
4
4

5
5
5
10
14

17
17
18
21
22
23
24
25

26
26

2

1.

Introducción

La programación paralela es una forma de computación donde varios cálculos son efec-
tuados de manera simultánea, bajo el principio de que cada problema puede ser separado
en partes para su tratamiento. Este tiempo de programación es válido para equipos que
tienen procesadores con varios núcleos (multicore) y computadoras con varios procesadores
de memoria compartida. Sin embargo, se ha agregado un nuevo nivel de dificultad a la
programación, donde las sincronización entre las subtareas y las condiciones de carreras in-
troducen nuevos tipos de errores en los programas y nuevos retos para realmente obtener
buenos resultados en ciertos problemas. También es importante considerar la llamada ley
de Amdahl donde se plantea que los programas paralelos tienen un límite de mejoramiento
marcado por las partes del mismo que no pueden ser paralelizados.

Para implementar este tipo de programación se ha implementado librerías que facilitan el
trabajo paralelo, como son POSIX Threads, OpenMP y MPI (Message Passing Interface). Sin
embargo también existen lenguajes de programación que implementan de manera automática
la paralelización, pero con resultados limitados. Ejemplos de estos lenguajes de paralelizado
implícito es Parallel Haskell.

En este breve texto, trataremos el lenguaje de programación C con la librería de Open-
MP. Presentaremos el API de OpenMP, así como ejemplos sencillos para que el lector pueda
acercase a la programación paralela. Con ejemplos dos ejemplos más complejos presenta-
mos también aplicaciones reales de la programación en paralelo para el mejoramiento de
algoritmos conocidos.

2. Características

2.1. Equipos multicore

Un equipo multicore es un procesador en un único componente con dos o más unidades
centrales de procesamiento llamados cores o núcleos, que son procesadores que ejecutan in-
strucciones. Estas instrucciones son instrucciones típicas de cada procesador, como puede
ver add, mov, etc... que pueden ser ejecutadas simultáneamente por sus diferentes núcleos.
Al llegar la computación a un nivel límite de ciclos por segundo en sus procesadores, las
grandes compañías productoras de procesadores han optado por incrementar el número de
núcleos de sus procesadores. Los primeros procesadores con estas características fueron el
AMD Phenom II X2 y Intel Core Duo. Sin embargo para poder ganar realmente sacar
provecho de las tecnologías es necesario que los algoritmos computacionales utilicen estas
características. Tenemos una serie de algoritmos conocidos como embarazosamente paralelos
que pueden ganar mayor provecho de esta situación. Independientemente de esto, el presente
texto tratará de generar una primer acercamiento a la programación multicore y multiproce-
sador utilizando la librería OpenMP.

3

2.2. Memoria compartida

El término Computadoras Paralelas de Memoria Compartida(en inglés Shared-Memory
Parallel Computers SMPs) fue originalmente creado para designar sistemas multiproce-
sadores simétricos, computadoras paralelas de memoria compartida donde los procesadores
individuales comparten la entrada y salida de la memoria de tal manera que cada uno de
ellos puede acceder a la memoria en cualquier locación con la misma velocidad, esto significa
que tienen acceso uniforme a memoria(en inglés uniform memory access UMA). Muchas
computadoras de memoria compartida menores son en este sentido simétricas. Sin embargo,
computadoras más grandes, usualmente no satisfacen esta definición;incluso si la diferencia
de tiempo de acceso es relativamente pequeña, ya que alguna memoria puede encontrarse mas
¸cerca”de uno o más procesadores, y estos logran acceder más rápido a esta memoria. A estas
computadoras se le dice que tienen un acceso a memoria no uniforme coherente-cache(en
inglés cache-coherent non-uniform-memory access cc-NUMA).

En la actualidad todos los grandes fabricantes de hardware ofertan algún tiempo de
computadoras de memoria compartida, desde dos procesadores, hasta cientos o incluso miles.

2.3. OpenMP

OpenMP es API multiplataforma para multiprocesos de memoria compartida. Está es-
crito para usarse de manera nativa desde C, C++ y Fortran. Se encuentra disponible para
una gran variedad de arquitecturas y sistemas operativos, entre los que podemos destacar
Windows, Mac OS X y la familia de sistemas operativos Unix. OpenMP es una estándar y
está bajo la administración de un consorcio no lucrativo impulsado por los mayores produc-
tores de hardware.

Entre los miembros de la Mesa de Revisión de Arquitectura, que es el consorcio del
estándar se encuentran miembros permanentes: AMD, CAPS-Entreprise, Convey Comput-
er, Cray, Fujitsu, HP, IBM, Intel, Microsoft, NEC, NVIDIA, Oracle Corporation, The Port-
land Group, Inc. y Texas Instruments. Además se tiene ta bién miembros auxiliares: ANL,
ASC/LLNL, cOMPunity, EPCC, LANL, NASA, ORNL, RWTH Aachen University, Texas
Advanced Computing Center.

Se implementa el multihilo partiendo de un hilo maestro, que con una serie de instrucción
son partidas creando hilos esclavos, donde las tareas son distribuidas a estos hilos. Los hilos
son ejecutados entonces y ejecutados en tiempo de ejecución a diferentes procesadores. Una
vez los hilos hallan terminado sus tareas paralelizadas, los hilos vuelven a unirse otra vez en
el hilo maestro.

4

3. Consideraciones sobre C

3.1. API de OpenMP para C

3.1.1. Directivas

Una directiva ejecutable de OpenMP aplica al bloque de construcción OpenMP. Un
bloque estructurado es una declaración simple o una declaratoria compuesta con una sola
entrada al principio y una sola salida al final.

1. Parallel

La construcción parallel crea un equipo de hilos y comienza con la ejecución paralela.

#pragma omp p a r a l l e l

[ c l a u s u l a [ [ , ] c l a u s u l a ] . . . ]

b l o q u e e s t r u c t u r a d o

c l a u s u l a s :

i f ( e x p r e s i o n e s c a l a r )
num threads ( e x p r e s i o n de e n t e r o s )
d e f a u l t ( s h a r e d | none )
p r i v a t e ( l i s t a )
s h a r e d ( l i s t a )
c o p y i n ( l i s t a )
r e d u c t i o n ( o p e r a d o r : l i s t a )

2. Loop

La construcción loop especifica que las iteraciones de los ciclos serán distribuidas y
ejecutadas entre el equipo de hilos.

#pragma omp f o r

[ c l a u s u l a [ [ , ] c l a u s u l a ] . . . ]

c i c l o s −f o r

c l a u s u l a :

p r i v a t e ( l i s t a )
f i r s t p r i v a t e ( l i s t a )
l a s t p r o v a t e ( l i s t a )
r e d u c t i o n ( o p e r a d o r :
s c h e d u l e ( t i p o [ , e x t e n c i o n d e l
c o l l a p s e ( n )
o r d e r e d
nowait

l i s t a )

t r a b a j o ] )

Tipo:

static: Las iteraciones son divididas en partes de un tamaño definido. Las partes
son asignadas a los hilos del equipo en una forma de round-robin según el número
de hilos.

dynamic: Cada hilo ejecuta una cantidad de iteraciones, y posteriormente pide
otra cierta cantidad hasta que no quede ninguna parte del ciclo.

5

guided: Cada hilo ejecuta una parte de iteraciones, después pide otra parte,
hasta que no quede ninguna parte sin asignar. El tamaño de las partes del siclo
comienzan grandes, y posteriormente se irán reduciendo hasta llegar al indicado
chunk size.

auto: La decisión de como delegar las tareas se relega al compilador o al sistema
de tiempo de ejecución.

runtime: El trabajo y el tamaño de las partes a procesar será decidido en tiempo
de ejecución.

for ( var = l b ; var

r e l a t i o n a l −op b ; var+=i n c r )

3. Sections

La construcción de secciones contiene una serie de bloques estructurados que serán
distribuidos y ejecutados entre un equipo de hilos.

#pragma omp s e c t i o n s

[ c l a u s u l a [ [ , ] c l a u s u l a ] . . . ]

{
[#pragma omp s e c t i o n ]

b l o q u e e s t r u c t u r a d o

[#pragma omp s e c t i o n ]

b l o q u e e s t r u c t u r a d o

. . .}

c l a u s u l a s :

p r i v a t e ( l i s t a )
f i r s t p r i v a t e ( l i s t a )
l a s t p r o v a t e ( l i s t a )
r e d u c t i o n ( o p e r a d o r :
nowait

l i s t a )

4. Single

La construcción single especifica que el bloque estructurado asociado es ejecutado
únicamente por uno de los hilos que componen el equipo de hilos(no necesariamente el
hilo maestro), en el contexto de una tarea implícita.

#pragma omp s i n g l e

[ c l a u s u l a [ [ , ] c l a u s u l a ] . . . ]

b l o q u e e