análisis de algoritmos cb-102cb.mty.itesm.mx/tc4001/tc4001-algoritmos-en-paralelo.pdf · ejemplo 1...

Algoritmos en Paralelo TC-4001 - p. 1/22

Análisis de AlgoritmosCB-102

Algoritmos en ParaleloCentro de Manufactura / Centro de Sistema Inteligentes

ITESM

ParalelismoPRAMConflictos deEscrituraComplejidadMedidasComentariosEjemplo 1Tarea parte IEjemplo 2Tarea parte IIOr BooleanoMaxMezcla de listasTarea Parte III


Paralelismo

■ Hasta este punto, nuestro modelo decomputación ha sido el de una computadora depropósito general, determinística, acceso amemoria aleatorio, que realiza una solaoperación a la vez.

■ Usaremos el término algoritmo secuencial paralos algoritmos de un paso a la vez que hemosestudiado hasta ahora.



■ Hay situaciones donde algunos cálculos de unatarea son relativamente independientes entre si;dichos cálculos podrían realizarsesimultáneamente, es decir, en paralelo.

■ El propósito de este capítulo es introduciralgunos de los conceptos, modelos formales, ytécnicas para el análisis de algoritmos donde esposible ejecutar varias operaciones en paralelo,es decir, algoritmos para máquinas que tienenmás de un procesador trabajando en un mismoproblema a la vez. Algoritmos Paralelos



■ Los algoritmos paralelos son naturales enmuchas aplicaciones:◆ Procesamiento de imágenes◆ Sistema de búsqueda◆ Evaluaciones de soluciones factibles en

problemas de optimización■ Al disminuir el precio de los microprocesadores y

al mejorar la tecnología para interconectarlos seha vuelto posible y práctico construircomputadoras con un gran número deprocesadores. Para ver la tendencia delparalelismo en las supercomputadoras actualesvisitar el sitio:◆ http://www.top500.org/



Modelo utópico: PRAM

Parallel Random Access Machine■ p procesadores■ P1, P1,. . . , Pp, conectados a una memoria

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

lleva a cabo vía la memoria compartida.■ El input se encuentra en las primeras n celdas

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



■ Cada paso tiene tres fases:1. Lectura2. Cálculo3. Escritura

■ Todos los procesadores ejecutan el mismoprograma y saben cual es su índice (identificadorde procesador o pid).

■ Procesadores PRAM están sincronizados:Empiezan cada paso al mismo tiempo; y todoslos que tiene que escribir lo hacen al mismotiempo.

■ Los procesadores pueden leer la misma posiciónde memoria concurrentemente.



Conflictos de Escritura: Modelos

■ CREW (Concurrent Read, Exclusive Write): Sóloun procesador puede escribir en una celdaparticular en un paso dado.

■ CRCW (Concurrent Read, Common Write):Varios procesadores pueden escribir en unacelda particular en un paso dado, siempre ycuando escriban el mismo valor.

■ CRPW (Concurrent Read, Priority Write): Sivarios procesadores tratan de escribir en unacelda al mismo tiempo, gana el de menor índice.



Complejidad

La Clase de Nick (Nicholas Pippenger): NC

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

p(n) ∈ O(nk)

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



Medidas

■ T (n): tiempo requerido por el mejor algoritmosecuencial conocido

■ Tp(n): tiempo que toma un algoritmo paralelousando p procesadores

■ Sp: speed-up ratio con respecto al mejoralgoritmo secuencial:

Sp =Tp(n)

T (n)

■ Ep: Eficiencia

Ep =Sp

p



Comentarios

Ley de Amdahl (versión texto interpretada):

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

El problema de ponerse los zapatos:

Si tuviera 4 brazos podría reducirse el tiempoa la mitad poniendo dos brazos a cadazapato; pero teniendo mas de 4 brazos nodisminuye el tiempo.



Obtención del máximo de un arreglo

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

eliminatoria hasta llegar a las finales donde seelige al ganador.

■ Tiempo de ejecución ⌈log2(n)⌉ competencias enparalelo



Código para cada procesador:

torneoMaxParalelo(M,n)1. read M [pid] into big;2. incr = 1;3. write −∞ into M [n+ pid];4. for step = 1 to ⌈log n⌉5. read M [pid+ incr] into temp;6. big = max(big, temp);7. incr = 2 ∗ incr ;8. write big into M [pid];9. end

Este algoritmo emplea CREW de manera que nohay conflictos de escritura.



Afirmación:

Al término de la iteración t en el ciclo del for :■ incr = 2t

■ Para cualquier 0 ≤ pid < 2⌈n⌉:M [pid] contiene el máximo de loscontenidos iniciales de

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

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

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

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



Tarea (Parte I)

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



Multiplicación de Matrices

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

C = AB

entonces

cij =n∑

k=1

aik bkj

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



Tarea (Parte II)

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

Tarea

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



Potenciando el Manejo de Escritura

Utilizando el esquema anterior (Abanico deEntrada Binario) el problema se resuelve entiempo Θ(log n). Este método funciona en todoslos modelos por que no hay conflicto de escritura.Pero puede rerolverse más rápido con otroesquema de manejo de conflictos de escritura: Orbooleano de n bits en tiempo constante.



Potenciando el Manejo de Escritura

Utilizando el esquema anterior (Abanico deEntrada Binario) el problema se resuelve entiempo Θ(log n). Este método funciona en todoslos modelos por que no hay conflicto de escritura.Pero puede rerolverse más rápido con otroesquema de manejo de conflictos de escritura: Orbooleano 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]

OrConsEscrituraComun(M,n)1. Pi lee xi en M[i];2. Si xi = 1, entonces Pi escribe 1 en M[1].3. end;



Un algoritmo rápido para encontrar Max

■ Utilizando CRCW o CRPW podemos acelerar eltiempo de cálculo del máximo de un arreglo(Max), aumentando el número de procesadores.

■ Se usan n(n− 1) procesadores.■ Estrategia: comparar todos los pares de valores

en paralelo, y comunicar los resultados vía lamemoria compartida:



Un algoritmo rápido para encontrar Max

■ Utilizando CRCW o CRPW podemos acelerar eltiempo de cálculo del máximo de un arreglo(Max), aumentando el número de procesadores.

■ Se usan n(n− 1) procesadores.■ Estrategia: comparar todos los pares de valores

en paralelo, y comunicar los resultados vía lamemoria compartida: Se usa un arreglo loserque ocupa las celdas de memoriaM[n+1],. . . .,M[2n]. Inicialmente todas las celdasde este arreglo tienen el valor 0. Si xi pierde unacomparación, entonces loser [i] recibe un 1.



MaxCW1(M,n)1. i = ⌊pid/n⌋;2. Escribe un 0 en loser[i];

MaxCW2(M,n)1. i = ⌊pid/n⌋; j = pid− n · i;2. Si i ≥ j, el procesador no ejecuta trabajo;3. xi←M [i];4. xj ←M [j];5. k ← i;6. Si xj > xi, entonces k ← j;7. Escribe 1 en loser[k];

MaxCW3(M,n)

1. i = ⌊pid/n⌋;

2. Si loser[i] = 0, entonces escribe M [i] en M [0];



Mezcla de listas en paralelo

■ Dos listas◆ X = (x1, x2, . . . , xn/2)◆ Y = (y1, y2, . . . , yn/2)

■ n procesadores:Cada procesador se asigna a un elementode la lista, su misión es localizar la posiciónde ese elemento en la lista mezclada.

■ Un procesador asociado con el elemento xi enX, realiza una búsqueda binaria en la lista Y ylocaliza la menor j tal que xi < yj. Con esto sedetermina que: xi es mayor que i− 1 elementosen X y mayor que j − 1 elementos en Y suposición en la lista mezclada es i+ j − 1.



Input: lista de n elementos en M [1], . . . ,M [n]

Output: los n elementos ordenados en ordennodecreciente en M [1], . . . ,M [n]

1. for i = 1 to ⌈log n⌉ do2. k = 2i − 1;3. Pi, . . . , Pi+2k−1 mezclan las dos listas

ordenadas de tamaño k empezando en M [i];4. end



Tarea Parte III

■ Escriba un algoritmo para PRAM con modeloCREW que calcule la suma de n númerosenteros en tiempo O(log n).

■ Modifique el programa de or booleano paracalcular el and booleano de n bits en tiempoconstante.

■ Indique un algoritmo que determine el productobooleano de dos matrices booleanas n× n entiempo constante en una PRAM con modeloCRCW.

análisis de algoritmos cb-102cb.mty.itesm.mx/tc4001/tc4001-algoritmos-en-paralelo.pdf · ejemplo 1...

Documents