PDF de programación - Algoritmos en paralelo

Análisis de Algoritmos

CB-102

Algoritmos en Paralelo

Centro de Manufactura / Centro de Sistema Inteligentes

ITESM

Algoritmos en Paralelo

TC-4001 - p. 1/22

Paralelismo

n Hasta este punto, nuestro modelo de

computación ha sido el de una computadora de
propósito general, determinística, acceso a
memoria aleatorio, que realiza una sola
operación a la vez.

n Usaremos el término algoritmo secuencial para

los algoritmos de un paso a la vez que hemos
estudiado hasta ahora.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 2/22

n Hay situaciones donde algunos cálculos de una
tarea son relativamente independientes entre si;
dichos cálculos podrían realizarse
simultáneamente, es decir, en paralelo.

n El propósito de este capítulo es introducir

algunos de los conceptos, modelos formales, y
técnicas para el análisis de algoritmos donde es
posible ejecutar varias operaciones en paralelo,
es decir, algoritmos para máquinas que tienen
más de un procesador trabajando en un mismo
problema a la vez. Algoritmos Paralelos

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 3/22

n Los algoritmos paralelos son naturales en

muchas aplicaciones:
u Procesamiento de imágenes
u Sistema de búsqueda
u Evaluaciones de soluciones factibles en

problemas de optimización

n Al disminuir el precio de los microprocesadores y
al mejorar la tecnología para interconectarlos se
ha vuelto posible y práctico construir
computadoras con un gran número de
procesadores. Para ver la tendencia del
paralelismo en las supercomputadoras actuales
visitar el sitio:
u http://www.top500.org/

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 4/22

Modelo utópico: PRAM

Parallel Random Access Machine

n p procesadores
n P1, P1,. . . , Pp, conectados a una memoria

compartida M.

n Cada procesador tiene una memoria local.
n Toda la comunicación entre los procesadores se

lleva a cabo vía la memoria compartida.

n El input se encuentra en las primeras n celdas

de la memoria.

n El output se escribe apartir de la primera celda.
n Todas las celdas de memoria sin input tienen un

0.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 5/22

n Cada paso tiene tres fases:

1. Lectura
2. Cálculo
3. Escritura

n Todos los procesadores ejecutan el mismo

programa y saben cual es su índice (identificador
de procesador o pid).

n Procesadores PRAM están sincronizados:

Empiezan cada paso al mismo tiempo; y todos
los que tiene que escribir lo hacen al mismo
tiempo.

n Los procesadores pueden leer la misma posición

de memoria concurrentemente.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 6/22

Conflictos de Escritura: Modelos

n CREW (Concurrent Read, Exclusive Write): Sólo

un procesador puede escribir en una celda
particular en un paso dado.

n CRCW (Concurrent Read, Common Write):
Varios procesadores pueden escribir en una
celda particular en un paso dado, siempre y
cuando escriban el mismo valor.

n CRPW (Concurrent Read, Priority Write): Si

varios procesadores tratan de escribir en una
celda al mismo tiempo, gana el de menor índice.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 7/22

Complejidad

La Clase de Nick (Nicholas Pippenger): N C

Clase de problemas que pueden ser resueltos por
un algoritmo en paralelo donde el número de
procesadores p está acotado por un polinomio en
el tamaño del input y el número de pasos F está
acotado por un polinomio en el logaritmo del
tamaño del input.

p(n) ∈ O(nk)

F (n) ∈ O((log (n))m)

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 8/22

Medidas

n T (n): tiempo requerido por el mejor algoritmo

secuencial conocido

n Tp(n): tiempo que toma un algoritmo paralelo

usando p procesadores

n Sp: speed-up ratio con respecto al mejor

algoritmo secuencial:

n Ep: Eficiencia

Sp =

Tp(n)
T (n)

Ep =

Sp
p

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 9/22

Comentarios

Ley de Amdahl (versión texto interpretada):

Finalmente, es el algoritmo el que decide el
factor de aceleración y no el número de
procesadores.

El problema de ponerse los zapatos:

Si tuviera 4 brazos podría reducirse el tiempo
a la mitad poniendo dos brazos a cada
zapato; pero teniendo mas de 4 brazos no
disminuye el tiempo.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 10/22

Obtención del máximo de un arreglo

n Idea: Torneo en paralelo.
n Forma de ejecución: Competir por pares:

eliminatoria hasta llegar a las finales donde se
elige al ganador.

n Tiempo de ejecución ⌈log2(n)⌉ competencias en

paralelo

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 11/22

Código para cada procesador:

read M [pid] into big;
incr = 1;
write −∞ into M [n + pid];
for step = 1 to ⌈log n⌉

torneoMaxParalelo(M,n)
1.
2.
3.
4.
5.
6.
7.
8.
9.

read M [pid + incr] into temp;
big = max(big, temp);
incr = 2 ∗ incr ;
write big into M [pid];

end

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Este algoritmo emplea CREW de manera que no
hay conflictos de escritura.

Algoritmos en Paralelo

TC-4001 - p. 12/22

Afirmación:

Al término de la iteración t en el ciclo del for:
n incr = 2t
n Para cualquier 0 ≤ pid < 2⌈n⌉:

M [pid] contiene el máximo de los
contenidos iniciales de

M [pid], M [pid + 1], . . . , M [pid + incr − 1]

Por tanto, para t = ⌈log n⌉ y para pid = 0 se
tendría que M [0] contendría el máximo de
los contenidos iniciales de

M [0], M [1], . . . , M [n − 1]

Por tanto: El problema de encontrar el máximo de
n números está en N C.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 13/22

Tarea (Parte I)

Modifique el algoritmo previo para
n encontrar el mínimo de n números
n calcular el or y and de n bits
n calcular la suma de n números

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 14/22

Multiplicación de Matrices

Consideremos el problema de multiplicación de
dos matrices A y B (n × n). Recordemos que si

entonces

C = A B

cij =

n

X

k=1

aik bkj

Idea del algoritmo:
Asignar un procesador a cada elemento del
producto, usando n2 procesadores. Cada
procesador Pij calcula su cij en 2n pasos (n
productos y n − 1 sumas).

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 15/22

Tarea (Parte II)

Note que el algoritmo anterior para el cálculo del
producto de matrices no prueba que el problema
está en la clase de Nick: 2 n (tiempo de ejecución)
no es poli-log en 2 n2 (tamaño de la entrada).
Para probar que efectivamente está en N C, habrá
que proveer de otro algoritmo que aunque quizá
use más procesadores reduzca el tiempo de
ejecución.

Tarea

Indique un algoritmo para hacer el cálculo de
dos matrices n × n que use Θ(n3)
procesadores y que ejecute en tiempo
O(log(n)).

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 16/22

Potenciando el Manejo de Escritura

Utilizando el esquema anterior (Abanico de
Entrada Binario) el problema se resuelve en
tiempo Θ(log n). Este método funciona en todos
los modelos por que no hay conflicto de escritura.
Pero puede rerolverse más rápido con otro
esquema de manejo de conflictos de escritura: Or
booleano de n bits en tiempo constante.

Paralelismo
PRAM
Conflictos de
Escritura
Complejidad
Medidas
Comentarios
Ejemplo 1
Tarea parte I
Ejemplo 2
Tarea parte II
Or Booleano
Max
Mezcla de listas
Tarea Parte III

Algoritmos en Paralelo

TC-4001 - p. 17/22

Potenciando el Manejo de Escritura

Utilizando el esquema anterior (Abanico de
Entrada Binario) el problema se resuelve en
tiempo Θ(log n). Este método funciona en todos
los modelos por que no hay conflicto de escritura.
Pero puede rerolverse más rápido con otro
esquema de manejo de conflictos de escritura: Or
booleano de n bits en tiempo constante.

Input: Bits x1, x2, . . . , xn, en M[1], M[2],. . . , M[n]
Output x1 ∨ x2 ∨ . . . xn en M[1]

Paralelismo
PRAM
Conflictos de