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 |