DEPENDENCIAS
Para poder ejecutar diferentes segmentos de código en paralelo, tenemos que asegurarnos de que son independientes, es decir, el orden de ejecución no importa (no afecta al resultado).
En general nos referimos a segmentos de código (grupos de instrucciones).
Por simplicidad, consideraremos instrucciones simples.
Las dependencias entre (grupos de) instrucciones pueden describirse por medio del grafo de dependencias.
El análisis de dependencias es estático, es decir, no se realiza en run-time.
1
GRAFO DE DEPENDENCIAS
Consideremos dos secuencias de instrucciones S1 y S2, para las que existe un camino de ejecución entre ellas (S1 primero, y después S2).
Nodos: (grupo de) instrucciones que se van a ejecutar en paralelo.
Arcos: indican dependencia.
Ejemplo:
(Gp:) S1
(Gp:) S2
2
DEPENDENCIAS
Existen tres tipos de dependencias:
Dependencias de datos
Dependencias de control
Dependencias de recursos
3
DEPENDENCIAS DE DATOS
Puede plantearse un conflicto cuando dos instrucciones hacen uso del mismo dato: el orden de ejecución es importante.
Dependencias de flujo
Antidependencias
Dependencias de salida
Dependencias de E/S ( a fichero)
Desconocidas
4
DEPENDENCIAS DE DATOS
1.Dependencia de flujo: la salida de S1 alimenta la entrada de S2.
2. Antidependencia: la salida de S2 se solapa con la entrada de S1.
S1
S2
(Gp:) S1
(Gp:) S2
(Gp:) S1
(Gp:) S2
(Gp:) S1
(Gp:) S2
A = 1
…
B = A+C
B = A
…
A = C+D
5
3. Dependencia de salida: S1 y S2 escriben en la misma salida.
4. Dependencia de I/O: S1 y S2 acceden al mismo fichero.
S1
S2
S1
S2
R
(Gp:) S1
(Gp:) S2
(Gp:) I/O
S1
S2
(Gp:) F
R1 = 1
…
R1 = A+C
read R1,F
…
write F,R2
DEPENDENCIAS DE DATOS
6
5. Dependencias desconocidas: ciertas dependencias no pueden ser determinadas.
Direccionamientos indirectos –> no es posible saber a que posición se esta accediendo.
Variables índices en bucles:
Las variable aparecen más de una vez en un bucle con diferentes índices.
índices no lineales.
índices que no contienen la variable del bucle.
DEPENDENCIAS DE DATOS
7
Los casos (4) y (5) presuponen el peor caso posible: en el que no es posible determinar que esta ocurriendo, por lo que se asume que existe una dependencia para evitar posibles errores.
Ejemplo:
S1: load R1,A /* R1 <- mem(A) */
S2: add R2,R1 /* R2 <- R2+R1 */
S3: move R1,R3 /* R1 <- R3 */
S4: store B,R1 /* mem(B) <- R1 */
DEPENDENCIAS DE DATOS
S1
S2
S4
S3
8
Ejemplo 2:
S1: read 4,A /* A <- tape 4 */
S2: rewind 4 /* rewind tape 4 */
S3: write 4, B /* tape 4 <- B */
S4: rewind 4 /* rewind tape 4 */
S5: add R1,A,B /* R1 <- A + B */
S1
S3
(Gp:) I/O
S5
S2
S4
DEPENDENCIAS DE DATOS
9
DEPENDENCIAS DE CONTROL
Tenemos dependencias de control cuando el orden de ejecución no puede ser determinado estáticamente, sino sólo en tiempo de ejecución.
Ejemplo: sentencias tipo “IF” o instrucciones tipo branch/jump.
También aparecen en bucles (ver ejemplo).
Dado que el orden no es conocido anticipadamente, las dependencias reales no pueden ser determinadas.
10
Página siguiente  |