DEPENDENCIAS DE CONTROL
Ejemplo:
En ambos casos no sabemos cual será la próxima instrucción a ser ejecutada después del test.
Pero, en el primer caso no hay dependencia de control, y en el segundo caso sí la hay. ¿Por qué?
for (i=0;i< 0)
a[i] = 1;
}
for (i=1;i< 0)
a[i] = 1;
}
11
DEPENDENCIAS DE RECURSOS
Tenemos dependencias de recursos cuando recursos compartidos del procesador (ej. ALU, UF coma flotante, buses, etc.) son demandados por instrucciones diferentes al mismo tiempo.
Ejemplo:
Dependencias por ALU
Dependencias de almacenamiento
S3
S4
Ejemplo:
S1: load R1, A
S2: load R2, B
S3: add R3,R1,R2
S4: sub R4,R1,R2
12
La transformación de código secuencial en paralelo puede realizarse:
Manualmente por el programador (paralelismo explícito).
Automáticamente por el compilador (paralelismo implícito).
En ambos casos, el “particionamiento” del código (decomposition) es un paso clave.
El particionamiento o división del código determina sí (y cómo) un segmento de código puede ser ejecutado en paralelo o en un orden en particular.
La detección de segmentos paralelos requiere la verificación de las relaciones de dependencia.
CONDICIONES PARA EL PARALELISMO
13
Conjunto de condiciones formales que determinan si dos procesos (segmentos de programa) pueden ser ejecutados en paralelo.
Ii : Conjunto de variables de entrada al proceso Pi (read set).
Oi : Conjunto de variables de salida del proceso Pi (write set).
“Variables”: operandos a ser loaded/stored en registros o posiciones de memoria.
CONDICIONES DE BERNSTEIN
14
CONDICIONES DE BERNSTEIN
Consideremos los procesos P1 y P2 y sus conjuntos de entrada (I1, I2) y salida (O1, O2)
Condiciones de Bernstein (dependencias de datos)
I1 n O2 = 0 (antidependencia)
I2 n O1 = 0 (flujo)
O1 n O2 = 0 (salida)
Si se verifican las tres condiciones, P1 y P2 pueden ejecutarse en paralelo, esto lo denotamos como :
P1 || P2
15
CONDICIONES DE BERNSTEIN
En resumen, si P1 || P2 el orden de ejecución de dos procesos es irrelevante, en tanto que:
La salida de uno no es usada como entrada por el otro
No escriben sobre las mismas variables de salida
Propiedades de la relación de paralelismo || :
Conmutativa: Pi || Pj <=> Pj || Pi
NO transitiva: Pi || Pj and Pj || Pk =/> Pi || Pk
Asociativa: (Pi || Pj) || Pk => Pi || (Pj || Pk)
Por tanto, no es una relación de equivalencia.
16
CONDICIONES DE BERNSTEIN: Ejemplo
Detectar que instrucciones del siguiente código pueden ejecutarse concurrentemente
Instrucción 1 x:=y+1
Instrucción 2 y:=x-2
Instrucción 3 z=a+b-7
17
CONDICIONES DE BERNSTEIN: Ejemplo
Detectar que instrucciones del siguiente código pueden ejecutarse concurrentemente
Lo primero es establecer qué variables se acceden en modo lectura. En las instrucciones vemos que son:
Para la instrucción 1 es la variable "y”.
Para la instrucción 2 es la variable "x”.
Para la instrucción 3 son las variables "a", "b”.
También necesitaremos saber qué variables se acceden en modo escritura. Son las siguientes:
Para la instrucción 1 es la variable "x”.
Para la instrucción 2 es la variable "y”.
Para la instrucción 3 es la variable "z".
18
I1 x:=y+1
I2 y:=x-2
I3 z=a+b-7
CONDICIONES DE BERNSTEIN: Ejemplo
Ahora aplicamos las tres condiciones:
Condición 1: La intersección entre las variables de lectura de un conjunto de instrucciones C1 y las variables de escritura de un conjunto C2 debe ser vacía.
Instrucciones 1 y 2 ? No cumple la condición
Instrucciones 1 y 3 ? Cumple la condición
Instrucciones 2 y 3 ? Cumple la condiciónte
19
I1 x:=y+1
I2 y:=x-2
I3 z=a+b-7
CONDICIONES DE BERNSTEIN: Ejemplo
Condición 2: La intersección entre las variables de escritura de un conjunto de instrucciones C1 y las variables de lectura de un conjunto C2 debe ser vacía.
Instrucciones 1 y 2 ? No cumple la condición
Instrucciones 1 y 3 ? Cumple la condición
Instrucciones 2 y 3 ? Cumple la condición
20
I1 x:=y+1
I2 y:=x-2
I3 z=a+b-7
CONDICIONES DE BERNSTEIN: Ejemplo
Condición 3: La intersección entre las variables de escritura de un conjunto de instrucciones C1 y las variables de escritura de un conjunto C2 debe ser vacía.
Instrucciones 1 y 2 ? Cumple la condición
Instrucciones 1 y 3 ? Cumple la condición
Instrucciones 2 y 3 ? Cumple la condición
21
I1 x:=y+1
I2 y:=x-2
I3 z=a+b-7
CONDICIONES DE BERNSTEIN: Ejemplo
Ahora podemos saber qué instrucciones pueden ejecutarse concurrentemente
22
I1 x:=y+1
I2 y:=x-2
I3 z=a+b-7
CONDICIONES DE BERNSTEIN
Observar que la condición Ii n Ij != 0 no impide el paralelismo.
Si tenemos n procesos, la violación de alguna de las condiciones impide total o parcialmente la ejecución en paralelo de P1…Pn
3*n*(n-1)/2
Qué ocurre con las otras dependencias?
Cualquier instrucción que dependa de condiciones de tiempo de ejecución no puede ponerse en forma paralela (subscripts, tests, Branches cond. …).
Los ficheros pueden tratarse e introducirse en los conjuntos de entrada I y salida O.
23
CONDICIONES DE BERNSTEIN
Ejemplo:
Detectar el paralelismo del siguiente código.
Suponiendo que cada instrucción requiere 1 paso (no pipeline).
Suponiendo que tenemos dos sumadores disponibles (pipeline).
P1: C = D*E
P2: M = G+C
P3: A = B+C
P4: C = L+M
P5: F = G/E
24
CONDICIONES DE BERNSTEIN
25
CONDICIONES DE BERNSTEIN
26
CONDICIONES DE BERNSTEIN
Generalización:
Las condiciones de Bernstein a nivel de instrucción pueden extenderse a niveles superiores, como segmentos de código, subrutinas, procesos, programas.
Las dependencias a niveles altos se infieren de las dependencias a niveles inferiores.
27
 Página anterior | Volver al principio del trabajo | Página siguiente  |