Descargar

Dependencias para el paralelismo en un Computador

Enviado por Pablo Turmero

Partes: 1, 2

    edu.red 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

    edu.red 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

    edu.red DEPENDENCIAS

    Existen tres tipos de dependencias:

    Dependencias de datos Dependencias de control Dependencias de recursos 3

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    Partes: 1, 2
    Página siguiente