Introducción
Algoritmos secuenciales: secuencia de pasos. El orden de la ejecución se puede conocer de antemano (a menos que haya aleatoriedad en el algoritmo)
Algoritmos paralelos: hay el detalle extra de la concurrencia (que pasos se pueden hacer en paralelo) y el no determinismo del orden de ejecución.
Un algoritmo paralelo no trivial necesita:
Definir que porciones del algoritmo se pueden hacer en paralelo
Mapear esas porciones en los CPUs correspondientes
Distribuir la data (input, output y variables intermedias) entre CPUs y/o memorias.
Administrar el acceso a la data compartida entre varios CPUs.
Sincronizar los procesos cuando convenga.
Qué se puede y qué no se puede paralelizar?
La suma de dos matrices es fácilmente paralelizable
Pero se puede paralelizar esto?
A=B+C
D=A+E
+
A=B+C
D=A+E
A=B+C
D=A+E
Dependencia de data y de flujo
Relación de bloqueo: write after read
F=G+D
G=H+I
Si i>j, el output de la oper.j es el input de la oper.i
Se puede solucionar usando variables auxiliares:
AUX=G
F=AUX+D
G=H+I
Dependencia de flujo: if A>B then C=D+E. Primero hay que hacer la comparación antes de tocar C. Si antes alguna operación modificaba A ó B, debe ser antes tocar C.
SI NO hay ninguna de estas dependencias, se puede paralelizar “a lo bestia” y funcionará bien. Por que entonces no hay carreras por la data ?localidad
Descomposición de y=Ab
Ejemplo: descomponer un query
MODEL="Civic" AND YEAR="2001" AND (COLOR="Green" OR COLOR="White")
Grafo de Dependencia 1
Grafo de dependencia 2
Página siguiente  |