OpenMP

Brevísimo tutorial de OpenMP
MSc Miguel Vargas-Félix
miguelvargas@cimat.mx
http://www.cimat.mx/~miguelvargas
17/08/11

1/37

Contenido

Contenido
Cómputo en paralelo
Operaciones matemáticas en paralelo
Evolución de los procesadores de propósito general
El cache
El esquema OpenMP
Pérdida de eficiencia con el aumento de procesadores
Post data: Optimizar el código compilado¿Preguntas?
Para saber más...

17/08/11

2/37

Número de instrucciones por segundo
2E+10

1E+10

1970

3E+10

1975
1985
1990

17/08/11

1995

6E+10

5E+10

4E+10

2000

8E+10

2005

Intel Core i7
AMD Phenom II X4 (76G ips)
(43G ips)

Intel Core 2
(49G ips)

7E+10

PlayStation 3 Cell
(10G ips)

AMD Athlon XP (5.9G ips)
Intel Pentium IV (9.7G ips)

IntelPentium III
(1.4G ips)

Motorola 68040
(44M ips)
Intel 80x486
(54M ips)
Motorola 68060
(88M ips)
Intel Pentium Pro
(541M ips)

0E+0
Intel 80x386
(11M ips)

1980
Intel 80x286
(4M ips)

Motorola 68000
(1M ips)

Intel 8080
(500K ips)

Intel 4004
(92K ips)

Cómputo en paralelo

Cómputo en paralelo

La evolución de la velocidad de los procesadores

2010procesadores
multi-core
3/37

Cómputo en paralelo

Tenemos ahora que desarrollar nuevos esquemas para diseñar algoritmos

Algoritmo
en
paralelo
Algoritmo
en
serie

La meta es reducir tiempo necesario para realizar una secuencia de instrucciones.
La buena noticia: Hacer programas en paralelo con OpenMP es muy sencillo.
La mala noticia: Hacer programas en paralelo eficientes requiere unesfuerzo extra.
17/08/11

4/37

Operaciones matemáticas en paralelo

Operaciones matemáticas en paralelo
Fácilmente paralelizables
Esto significa que pueden separarse en varias sub-operaciones que puede realizarse de forma
independiente. Por ejemplo, el la suma de dos vectores x, y para producir otro vector c,
ci = x i  y i, i=1, , N.
En este caso las N sumas pueden realizarsesimultáneamente, asignando una a cada procesador.
Lo que hay que resaltar es que no hay dependencia entre los diferentes pares de datos, tenemos
entonces el paralelismo más eficiente.

No tan fáciles de paralelizar
Por ejemplo el producto punto 〈 x , y 〉
N

a= ∑ x i y i,
i=1

donde a es un escalar, una primera aproximación sería verlo como una secuencia de sumas de
productos que requieren irseacumulando, al verlo así no es una operación paralelizable.

17/08/11

5/37

Operaciones matemáticas en paralelo

Sin embargo, podemos reorganizar el proceso como se muestra en la figura:
x1 y1

x2 y2

x3 y3

+

N

a=∑ x i y i

x4 y4

x5 y 5

+

x6 y6

x7 y7

+

+

x8 y8

x9 y9

...

+

xn yn

...

+

i=1

+

...
+
a

En este caso se tieneuna paralelización eficiente de la multiplicación de las entradas de los
vectores, después se va reduciendo la eficiencia. Muchos algoritmos seriales requieren, para ser
paralelizados, de re-ordenar las operaciones con una estrategia de “divide y vencerás”, como en
el caso del producto punto.

17/08/11

6/37

Operaciones matemáticas en paralelo

Usualmente se tendrán memos procesadoresque el tamaño del vector, por lo que se asignan
varias operaciones de un grupo a cada procesador, las cuales se ejecutarán en secuencia, lo que
limita la eficiencia del paralelismo.
x1 y1
N

a=∑ x i y i

x2 y 2

x3 y3

x4 y4

x5 y5

x6 y6

+

x7 y7
+

x 8 y8

x9 y9

...

xn yn

...

i=1

+
a

17/08/11

7/37

Evolución de los procesadores de propósitogeneral

Evolución de los procesadores de propósito general
Hace unos 30+ años
Single-core computer

Running program
Heap

Processor

Bus
Bus

RAM

Stack

Code

Data
Desde un punto de vista físico muy simplificado, la computadora contiene un procesador (CPU)
que accesa a la memoria (RAM) a través de un bus de datos/direcciones.
La velocidad de los procesadores y la memoria...