universidad tecnica federico santa maria...

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA

ELO311 Estructuras de Computadores

Prof. Leopoldo Silva Bijit. 22-10-2004 309

14. Segmentación. El procesador tiene registros de segmentación entre etapas, todas las instrucciones pasan por las mismas etapas, y a medida en que se avanza por la cañería se va propagando el control de las transferencias asociado a cada instrucción. Se ejecutan varias instrucciones, que usan recursos diferentes, en forma simultánea. Se comienza la próxima instrucción mientras se trabaja aún en otra. La velocidad de avance está limitada por la etapa más lenta. Si las etapas no están balanceadas en tiempo, se reduce la velocidad. Durante el llenado y vaciado la velocidad de ejecución de instrucciones es más lenta. La velocidad puede degradarse si existen dependencias.

14.1 Etapas: • Búsqueda de Instrucción. (BI) • Decodificación. Lectura Registros. (Dec) • Ejecución. (Eje) • Operación con memoria de datos. (Mem) • Post-escritura en arreglo de registros. (WR) La ejecución de instrucciones puede representarse por el siguiente diagrama, donde cada renglón representa una instrucción y hacia la derecha se muestra la evolución de la ejecución individual: La siguiente figura ilustra las diferencias en las ejecuciones de las instrucciones en procesadores monociclo, multiciclo y segmentado:

tiempo

flujo de ejecución

BI Dec Eje Me WR BI Dec Eje Me WR

BI Dec Eje Me WR




En la ejecución monociclo, el período del reloj lo establece la instrucción que más demora en ejecutarse. A la vez este período es la suma de los tiempos asociados a cada etapa. En el diagrama los tiempos de acceso a memoria de instrucciones y de datos se asumen iguales y levemente mayores que la operación de la unidad aritmético lógica; la lectura y escritura de registros, se asumen iguales y menores que el tiempo de propagación en la alu. En la ejecución multiciclo, el período del reloj lo establece la etapa que más demora en realizarse(acceso a memoria). En el diagrama se aprecia que la instrucción load word demora más en ejecutarse en la máquina multiciclo. Sin embargo la instrucción store word demora menos, y también es más rápida la ejecución de la secuencia lw, sw, en el procesador multiciclo(el marcador uno ilustra esta diferencia). En la ejecución segmentada o en cañería(pipeline), asumiendo que cada instrucción ocupa las cinco etapas, la realización individual de una de ellas demora lo mismo que la más lenta en la ejecución multiciclo. Se aprecia que es más rápida la ejecución de la secuencia lw, sw, en el procesador segmentado que en el multiciclo(el marcador dos ilustra esta diferencia).

Load Store Add

BI Dec Eje Me BI Dec BI Dec Eje Me W

BI Dec Eje Me WR

BI Dec Eje Me WR

BI Dec Eje Me WR

1

2

Monociclo

Multiciclo

Pipeline

Reloj Monociclo

Reloj Multiciclo y pipeline




Ejemplo: Suponer que se ejecutan 100 instrucciones: ° Procesador monociclo • 45 ns/ciclo x 1 CPI x 100 inst = 4500 ns ° Procesador Multiciclo • 10 ns/ciclo x 4.6 CPI (debido a la mezcla) x 100 inst =4600 ns ° Segmentada ideal • 10 ns/ciclo x (1 CPI x 100 inst + 4 ciclos llenado) = 1040 ns Si T es la duración de la etapa más lenta.

Con n etapas: I instrucciones demoran: T* ( I + (n-1) )

En el diseño de un procesador segmentado se desea mejorar la velocidad de ejecución de una gran cantidad de instrucciones, en lugar de optimizar la ejecución individual de las instrucciones.

llena




La segmentación ocupa los recursos que ya están en el procesador, sólo agrega algunos registros para efectuar la segmentación y propagar el control.

El siguiente diagrama ilustra la ejecución

de instrucciones: Multiciclo versus segmentación. En un procesador multiciclo interesa que el número de etapas o microciclos sea mínimo para cada una de las instrucciones. Esto disminuye el CPI promedio. En un procesador segmentado interesa disminuir las detenciones debidas a conflictos. En un camino segmentado las cinco unidades funcionales independientes son: • Memoria de instrucciones para la etapa de búsqueda.

BI (fetch). • Puertas A y B de lectura del arreglo de registros para la etapa de Decodificación y

Lectura de Registros. Reg/Dec.

• Unidad aritmético-lógica para la etapa de Ejecución. Ejec.

• Memoria de Datos para la etapa de acceso a memoria. Mem. • Puerta de escritura del arreglo de Registros para la etapa de postescritura.

Wr.

tiempo (ciclos de reloj)

orden de ejecución

Instrucción 1

Instrucción 2

Instrucción 3

Instrucción 4

Instrucción 5

todas las etapas están ejecutando una instrucción diferente en un mismo ciclo.

Cuando la instrucción 1 está en escritura de registros WR, la 2 está en Memoria de datos; la 3 está en Ejecución en Operaciones; la 4 está en decodificación y lectura de registros; la 5 está en la etapa de búsqueda de instrucción.




14.2. Análisis de las etapas requeridas por las diferentes instrucciones.

14.2.1. Load. La instrucción Load requiere pasar por las cinco etapas:

No hay conflictos de escritura, ya que el arreglo de registros se emplea para escritura en ciclos diferentes. Tampoco de lectura ya que las instrucciones leen registros que permanencen con sus contenidos sin cambios. Sin embargo la secuencia : lw $t1, 0($t2) lw $t4, 0($t1) requiere usar $t1, que aún no ha sido escrito.

14.2.2. Instrucciones de tipo R. En un procesador multiciclo las instrucciones de tipo R requieren cuatro etapas. Si se introducen en la cañería secuencias de lw y de tipo R (con cuatro etapas), se produce un riesgo estructural. Dos instrucciones intentan escribir en la única puerta de escritura del arreglo de registros en el mismo tiempo. Una solución es insertar una operación nop entre un lw y una de tipo R. Se producen cinco etapas nulas. Lo que degrada la velocidad de ejecución de instrucciones.

lw $t1, 0($t2)

lw $t4, 0($t5)

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L

M I

M D

R L

lw $t3, 0($t3)

add $t1, $t2, $t3

lw $t4, 0($t5)

tiempo

Orden de ejecución

M I

R L

M I

M D

R L

M I

R L

add $t3, $t3, $t2




Otra solución es detener la ejecución (stall) de la ejecución de una instrucción de tipo R siguiente a un lw, insertando una burbuja. Esta solución requiere una lógica de control que resulta compleja. Se prefiere escoger la solución de insertar un ciclo de memoria nulo en las instrucciones de tipo R. Esto implica que las instrucciones de tipo R durarán 5 ciclos.

14.2.3. Instrucción sw Para la ejecución de la instrucción store word, en un procesador multiciclo, se requieren cuatro etapas. En la ejecución en la cañería no es necesario agregar un ciclo nulo de postescritura, para la instrucción store, ya que en este caso se libera el recurso(escritura en el arreglo de registros).

add $t1, $t2, $t3

lw $t4, 0($t5)

tiempo

Orden de ejecución

M I

R L

M I

M D

R L

M I

R L

add $t3, $t3, $t2

Orden de ejecución

add $t1, $t2, $t3

lw $t4, 0($t5)

tiempo M I

R L

M I

M D

R L

M I

R L

add $t3, $t3, $t2

M D

M D

M D

M D

sw $t1, $t2, $t3

lw $t4, $t1, $t2

tiempo

Orden de ejecución

M I

R L

M I

M D

R L

M I

R L

sw $t3, $t3, $t2




14.2.4. Bifurcación. La bifurcación requiere cuatro etapas, si se determina la igualdad empleando la condición cero generada por la ALU, durante la etapa de memoria de datos(nula obviamente) se actualiza el valor de PC si debe efectuarse la bifurcación. Nuevamente no se requiere la etapa de postescritura ya que no se usa el recurso; también la etapa nula de memoria no ocasiona riesgos con la ejecución de otras instrucciones. Para disminuir los riesgos de control es mejor solución detectar la igualdad en la etapa de decodificación y lectura del arreglo de registros y actualizar el valor de PC, en caso de que se efectúe la bifurcación, en la misma etapa. En este caso el beq libera el recurso ALU y memoria. Se elige esta opción, en la cual la bifurcación requiere dos ciclos para completarse. Un razonamiento análogo se emplea para el salto incondicional(jump). Se actualizará PC en la etapa de decodificación y lectura de registros. En este caso se libera el arreglo de registros, ya que no se emplea.

14.3. Problemas de la segmentación. Riesgos de segmentación.

14.3.1. Clasificación de riesgos de datos. ° Sea i una instrucción que entrará ha ser procesada y j una instrucción anterior que está en la cañería, con Rregs( i ) el conjunto de registros que son empleados en lectura y Wregs( i ) el conjunto(en el repertorio MIPS, es un solo registro) de registros en que se escribe en la instrucción i, entonces:

M D

beq $t1, $t2, rótulo tiempo

Orden de ejecución

M I

R L

Orden de ejecución

beq $t1, $t2, rótulo tiempo M I

R L

j rótulo tiempo M I

R L

Orden de ejecución




° Existe un riesgo Read after Write en el registro r si: r ∈ Rregs( i ) ∩ Wregs( j )

° Existe un riesgo Write after Write en el registro r si: r ∈ Wregs( i ) ∩ Wregs( j )

° Existe un riesgo Write after Read en el registro r si: r ∈ Wregs( i ) ∩ Rregs( j )

El siguiente diagrama ilustra los tipos de riesgos: El riesgo de tipo RAW(read after write) consiste en leer después de escribir, produce conflicto de datos, ya que se lee el valor anterior de un registro. El riesgo WAW(write after write) consiste en es escribir después de escribir. Se ilustra con un tiempo largo de acceso a la memoria de datos. Produce la sobre escritura de un registro con un valor anterior El riesgo WAR(write after Read) escribe después lee, se ilustra con una etapa larga de decodificación, y produce el leer el valor futuro de un registro, no usando el valor presente.

14.3.2. Tipos de riesgos(hazards) • Estructurales: Se intenta usar el mismo recurso de dos maneras diferentes, en el mismo tiempo. • Conflicto de datos: Se intenta usar un dato antes de que sea válido. Ocurre cuando una instrucción depende de un dato que escribe una instrucción previa que también está en la cañería. • Conflicto de Control: Se intenta efectuar una decisión antes de que la condición o flag sea válida. Todos los riesgos pueden resolverse esperando. Es decir, impidiendo que se ejecuten las etapas de las siguientes instrucciones, hasta que se resuelva el conflicto. La unidad de control del procesador segmentado debe detectar los riesgos, y tomar acciones para solucionar los conflictos.

BI Dec Eje Me WR

BI Dec Eje Me WR

BI Dec Eje Me WR

tiempo

flujo de ejecución

RAW

WAW

BI Dec Eje Me WR

BI Dec Eje Me WR WAR




Ejemplo de riesgo estructural. Usar, en forma compartida, una memoria para datos e instrucciones provoca un riesgo estructural. Por ejemplo, la instrucción load, en su etapa de lectura de memoria, y el fetch de la instrucción 4, intentan leer al mismo tiempo la única memoria. La siguiente secuencia de ejecución de instrucciones ilustra un conflicto estructural: En las unidades de memoria y registros, se sombrea la parte derecha para indicar que se está leyendo el recurso; y se sombrea a la izquierda para indicar que se está escribiendo en el recurso.

Ejemplo de Riesgo de Control. En el siguiente camino multiciclo, y con registros de segmentación:

La bifurcación se resuelve después de la etapa de ejecución; es decir se escribe en PC la dirección de salto en la etapa de memoria, si es que se cumple la condición para realizar el salto.

Load word

Instrucción 2

Instrucción 3

Instrucción 4

Instrucción 5

tiempo

Orden de ejecución

M I

M I

M I

M I

M I

M D

M D

M D

M D

M D

R L

R L

R L

R L

R L




La bifurcación puede realizarse o no. En caso de tomar la bifurcación ya habrán ingresado a la cañería las dos instrucciones siguientes a la bifurcación y comenzado a ejecutarse; si no se efectúa la bifurcación, ya se tendrá adelantada la ejecución de las instrucciones siguientes a la bifurcación. Se puede solucionar este riesgo de control, deteniendo el procesamiento de las próximas instrucciones hasta que la decisión pueda efectuarse. Esto implica tres ciclos de reloj de detención (stall) por cada branch. No puede efectuarse fetch: durante la etapa de decodificación, durante la etapa de cálculo del flag de cero a la salida de la alu de la instrucción beq, y durante la escritura de PC de la instrucción beq que se efectúa en la etapa mem; sólo en la etapa WR de la instrucción beq puede efectuarse confiablemente el fetch de la instrucción siguiente. La detención puede lograrse evitando leer la memoria de instrucciones, mediante la deshabilitación de WEIR y desactivando las señales de control que modifican el estado del procesador(WrReg, MemWr); o bien, limpiando el registro IR en la etapa de decodificación del beq. Esto intercala burbujas en la cañería. Lo cual se ilustra en el siguiente diagrama:

beq $t1, $t2, loop

burbuja

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L

este fetch es seguro

burbuja

burbuja

beq $t1, $t2, loop

add $t3, $t4, $t5

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L

M I

M D

R L

M I

M D

R L

M I

M D

R L


add $t3, $t6, $t3

add $t3, $t8, $t7




Ésta es una solución por hardware; también puede delegarse la tarea de detención al compilador, que debe intercalar tres instrucciones nop (no operación) despues de cada beq; el diagrama que representa esta situación es similar al visto antes, pero se está ejecutando la instrucción nop. El texto assembler, modificado por el compilador, para asegurar la ejecución sin riesgos de control en la cañería es el siguiente:

beq $t1, $t2, loop nop nop nop add $t3, $t4, $t5 #este fetch es seguro. add $t3, $t6, $t3 add $t3, $t8, $t7

14.3.3. Solución de riesgo de control anticipando la comparación. Puede mejorarse el diseño de la cañería, anticipando la comparación, para esto es preciso agregar hardware, que permita generar la condición "equal" en la etapa de decodificación y a la vez escribir el valor de PC. En este caso: Existen varias soluciones para este riesgo de control:

14.3.3.1. Detención. La solución por hardware consiste en detener por un ciclo el fetch de la instrucción siguiente a un branch. La solución por software consiste en intercalar un nop, después de cada branch.

14.3.3.2. Bifurcaciones retardadas.

No se detiene la ejecución después de una bifurcación; es decir la instrucción siguiente a una bifurcación comienza a ejecutarse siempre.

Orden de ejecución

beq $t1, $t2, loop

add $t3, $t4, $t5

tiempo M I

M D

R L

M I

M D

R L

M I

M D

R L





Esta solución (delayed branch) agrega un ciclo por cada branch, si el compilador no puede encontrar una instrucción que sea útil, y que pueda realizarse después del branch.

14.3.3.3. Vaciamiento. (flush) La tercera solución es efectuar el fetch, después del branch. Si el salto no se realiza, se continúa la ejecución. Si el salto se realiza, se debe descartar la instrucción leída y volver a efectuar el fetch.

14.3.3.4. Predicción de las bifurcaciones. Basado en la observación que en muchos lazos repetitivos, las bifurcaciones ocurren normalmente en el fondo de un bloque, y saltan hacia el inicio del bloque; puede predecirse que las bifurcaciones hacia atrás tienen mayor probabilidad de ser realizadas(ésta es una predicción estática). Un esquema más refinado es el de las predicciones dinámicas: se mantiene una máquina secuencial que recuerda si las bifurcaciones anteriores(una, dos o más) se han o no realizado; en caso de haberse efectuado las anteriores se asume que la próxima también se efectuará; en caso contrario se asume que no efectuará la bifurcación. En caso de que la suposición de no efectuarla sea incorrecta, el control debe modificar las instrucciones siguientes a la de la bifurcación o salto para no afectar la integridad de los datos. Si el número de etapas de la cañería es muy largo se tiende a emplear la predicción dinámica del flujo de ejecución. El primer procesador MIPS empleó la solución por software, de intercalar nops después de los saltos y bifurcaciones. La siguiente versión empleó el diseño de efectuar siempre la siguiente instrucción después de un salto o bifurcación (así está implementado el simulador SPIM, en modo raw, realiza bifurcaciones retardadas en una instrucción).

14.3.4. Más sobre bifurcaciones retardadas (Delayed Branches). En un procesador MIPS la instrucción después de un branch se ejecuta siempre, aún cuando se efectúe la bifurcación. En el simulador esto se logra en modo "raw". La máquina virtual MIPS (modo no raw) no ejecuta la instrucción siguiente a la bifurcación. Esta interpretación de las bifurcaciones permiten al compilador generar código para usar más eficientemente la segmentación. Por ejemplo, en el siguiente texto, el addi después del beq se ejecuta aún cuando se efectúe la bifurcación:

.text .globl main main: addi $t2, $zero,0 beqz $t1, rótulo addi $t2, $t0, 1 ;se ejecuta siempre




...... rótulo: slt $t1, $t0, $t3 Al finalizar la etapa de decodificación del branch, se conoce si el salto tendrá o no lugar. Sin embargo, ya se habrá realizado el fetch de la instrucción siguiente no importando si se realiza o no el salto. La mitad de las veces un compilador puede encontrar una instrucción útil para colocar después de un branch, esto en promedio. Si no puede encontrar una instrucción debe intercalar una instrucción que no haga nada (nop). Una técnica para rellenar los huecos en la cañería es que el compilador intercale un nop después de cada branch, y luego intente reemplazar el nop por una instrucción que pueda adelantarse. Para esto existen diversas opciones: a) Para encontrar una instrucción que se pueda ejecutar después del branch, se mueve

hacia el rótulo y se observa si la instrucción puede moverse en forma segura (que no haya riesgos), si es posible ésta reemplaza al nop. El segmento siguiente ilustra el procedimiento, con una bifurcación hacia adelante.

addi $t2, $zero,0

beqz $t1, rótulo NOP ...

rótulo: addi $t2, $t0, 1 slt $t1, $t0, $t3 El addi puede moverse ya que no tiene conflictos. El texto quedaría igual al que se mostró antes. Esto es en caso de bifurcaciones hacia adelante; existe un procedimiento similar cuando la bifurcación es hacia atrás. b) Otra opción es rellenar el nop(intercalado en una primera etapa por el compilador), con

una instrucción que se encuentre antes de la bifurcación. En el ejemplo, el addi que está antes de la bifurcación, no tiene riesgos y puede moverse, quedando:

beqz $t1, rótulo

addi $t2, $zero,0 ; una que está antes rellena el hueco. ...

rótulo: addi $t2, $t0, 1 slt $t1, $t0, $t3




No es tan difícil encontrar instrucciones para rellenar el hueco si existen instrucciones de punto flotante, ya que éstas emplean registros separados del procesador central. Otra técnica empleada, por los compiladores, para mejorar el tratamiento de las detenciones por riesgos de control, es aumentar el tamaño de los bloques de instrucciones que se repiten. Una iteración puede desenrollarse; es decir efectuar el paso i y el i+1(o más pasos, si es posible) dentro del bloque, lo cual disminuye el número de bifurcaciones promedio realizadas para ejecutar el lazo.

14.3.5. Conflicto de datos en operaciones de tipo R o inmediatas. Estudiemos la ejecución de cinco instrucciones de tipo R. El primer add escribe en $t1 en la etapa WR. Las tres instrucciones siguientes tienen conflictos de dependencia de datos, ya que usan un valor que aún no ha sido escrito. Esto puede detectarse en los diagramas, observando las líneas hacia atrás en el tiempo. El and, que es la cuarta instrucción después del add, no tiene riesgos en $t1(puede detectarse por una línea hacia delante en la cañería). Si el arreglo de registros se implementa con latchs transparentes el or (la tercera después del add) no tendría conflicto en $t1. Ya que se puede leer y escribir en el mismo registro, en el mismo ciclo del reloj. En este tipo de registros la salida se modifica cuando cambia la entrada(modo transparente), entonces lo que se escriba es lo que comienza a salir. La solución de los conflictos de datos, puede realizarse mediante la anticipación de los datos. Esto considerando que el dato que será escrito en un registro por una instrucción de tipo R o de tipo inmediata, ya está disponible en la cañería después de terminada la etapa de operaciones. También dicho valor está disponible al terminar el ciclo de memoria(nulo en este caso, ya que la instrucción de tipo R o inmediata no emplea la memoria).

add $t1, $t2, $t3

add $t4, $t1, $t2

sub $t2, $t3, $t1

or $t6, $t1, $t3

and $t2, $t1, $t1

tiempo

Orden de ejecución

M I

M I

M I

M I

M I

M D

M D

M D

M D

M D

R L

R L

R L

R L

R L




Esto implica modificar la ruta de datos, para que la alu pueda adquirir sus datos de entrada desde la salida de la alu, o desde la salida de la memoria. Se detecta el conflicto de datos de las instrucciones siguientes que lean registros con una que escriba en registros(de tipo R o inmediata pero no de tipo load word), estando la instrucción que escribe en registros en operaciones y la que le sigue en decodificación, si el registro destino(se denomina RD más adelante) de la que está en operaciones es igual al campo rs o rt de la que está en decodificación. En este caso, mediante muxes, debe escribirse la salida de la alu en el registro A(en lugar del busA) si el conflicto es con rs; o en el registro B(en lugar del busB) si el conflicto es con rt. Puede detectarse que la que está en operaciones es de tipo R o inmediata, ya que debe tener MemRd y MemWr iguales a cero y RegWr igual a uno. Si se tiene en la etapa nula de memoria una operación de tipo R o inmediata que escribirá en un registro(que se denomina RD1 más adelante), y en decodificación una operación de tipo R cuyo campo rs o rt sean iguales a RD1, deberá anticiparse la salida de la etapa memoria hacia el registro A o B, dependiendo de si el conflicto es con rs o rt, respectivamente. Puede detectarse que la que está en memoria es de tipo R o inmediata, ya que debe tener MemRd1 y MemWR1 iguales a cero y RegWr1 igual a uno. Si en la etapa de operación y de memoria existen instrucciones que escriban en un registro que deba ser leído por la instrucción que está en decodificación, debe adelantarse el dato que está a la salida de la alu, por ser el más reciente. En el diagrama, que se mostró anteriormente, se ilustran las anticipaciones desde la salida de la alu(del valor de $t1) y de la salida de la memoria(con el valor de $t1) hacia la entrada de la alu de las instrucciones siguientes. También se muestra, el efecto anticipatorio, del uso de registros en base a latchs transparentes.

add $t1, $t2, $t3

add $t4, $t1, $t2

sub $t2, $t3, $t1

or $t6, $t1, $t3

and $t2, $t1, $t1

tiempo

Orden de ejecución

M I

M I

M I

M I

M I

M D

M D

M D

M D

M D

R L

R L

R L

R L

R L




14.3.6. Conflicto de datos en transferencias. La anticipación de datos hacia la unidad de operaciones resuelve los riesgos para instrucciones de tipo R o inmediatas, pero los conflictos de datos en las transferencias no pueden anticiparse, como se ilustra a continuación. En una instrucción de carga el valor que será escrito en el registro destino está disponible en la cañería al terminar la etapa de memoria. Sin embargo, la instrucción siguiente al lw requiere leer el registro con riesgo de datos en el ciclo anterior. La solución de este riesgo de datos es detener el ingreso de nuevas instrucciones(detención por hardware), o introducir nop(si se delega la detención al compilador), hasta resolver el conflicto. Si se anticipa la salida de la memoria como entrada a la alu (como se muestra en el diagrama anterior), es preciso detener en un ciclo; sin esta anticipación la detención es de dos ciclos.

Detención por hardware. El siguiente diagrama ilustra la detención por hardware(stall) de la instrucción siguiente a un load word, pudiendo ser ésta una de tipo R, bifurcación o store word, pero que lea el registro en el que escribe la instrucción load word. Nótese que cuando el load word está en operaciones y la siguiente en decodificación se puede detectar el riesgo, y detener(en ese ciclo) la actualización del registro IR y del

lw $t1, 0($t2)

add $t3, $t1, $t5

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L

Orden de ejecución

lw $t1, 0($t2)

add $t3, $t1, $t5

tiempo

M I

R L

M I

M D

R L

inicio fetch siguiente M I

M D

R L

M I

M D

R L

repite fetch siguiente




registro PC. De esta forma cuando lw está en memoria: se anula la etapa de operación(se indica con una burbuja, la cual debe deshabilitar los controles que modifican el estado del procesador: MemWr y RegWr); como IR no cambió sigue estando la operación add en decodificación, y como PC no cambió, vuelve a realizarse el fetch de la instrucción siguiente al add. El diagrama anterior ilustra el uso de las etapas en el tiempo por cada instrucción en ejecución(en cada ciclo del reloj deben estar presentes todas las etapas). Existe una forma alternativa de emplear el diagrama, mostrando la ejecución individual de las instrucciones en el tiempo, en este caso cada línea horizontal muestra la ejecución individual en las etapas. Esto se muestra a continuación. En el diagrama anterior se muestra que al final del ciclo de operación del load word, se detiene el procesamiento del add(no se actualiza IR) y la instrucción siguiente(no se cambia PC). Cuando el load word entra a su ciclo de memoria, se repite la decodificación del add y el fetch de la siguiente al add. El esquema no muestra la etapa de operación nula en el ciclo en que se procesa en memoria el load word.

Solución por software. El siguiente diagrama ilustra la solución por software, en la cual el compilador intercala una operación nop, después de cada load word.

lw $t1, 0($t2)

add $t3, $t1, $t5

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L

M I

M D

R L

nop

Orden de ejecución

lw $t1, 0($t2)

add $t3, $t1, $t5

tiempo M I

M D

R L

proceso siguiente inst.

M I

R L

M D

R L

M I

M I

M D

R L




Después del load word, el compilador inserta una operación nop, y ésta se ejecuta en la cañería. La decodificación de la operación nop, debe deshabilitar los controles de escritura en registro y en memoria. Si la siguiente instrucción al nop, lee un registro que aún no se ha escrito, puede anticiparse el valor del contenido del registro en conflicto, que ya está a la salida de la memoria y escribirlo en el registro A(en el caso del ejemplo); en lugar de lo leído en la etapa de decodificación por la instrucción(ubicada dos líneas más abajo que el load word). Esto explica que sólo sea necesario perder un ciclo del reloj, después de instrucciones load word que tengan conflictos de datos.

Secuencia lw seguida de sw. Una excepción a lo anterior es la secuencia lw seguida de un sw que puede resolverse, en caso que el registro en que escribe lw sea usado para escribir en la memoria en la instrucción store word. Esto se ilustra a continuación: Igual situación sucede en secuencias de instrucciones que escriban en un registro(tipo R o inmediatas) seguidas de un store word que emplea el contenido de ese registro para escribir en la memoria. Para resolver este riesgo se requiere anticipar desde la salida de la memoria hacia el registro D (en el diagrama que se verá más adelante) con el valor que será escrito en la siguiente etapa de memoria. Para esto debe poderse ingresar al bus de escritura de la memoria(mediante un mux) el contenido del busB y también la salida de la memoria(Mout), cuando se tenga en la etapa de operaciones un sw y en la etapa de memoria: una instrucción lw o de tipo R o inmediata, y se tenga conflicto en el registro que se escribe, con el que graba sw.

Cargas retardadas. (Delayed Loads) Una forma de evitar las detenciones, en el caso de conflicto de datos de cargas (load) seguidas de operaciones de tipo R o bifurcaciones, es optimizar el orden de las instrucciones mediante el compilador. Se muestran las detenciones, debidas a cargas, para tres programas (un compilador C (gcc), un analizador de circuitos (spice), y un procesador de textos (tex) ) con y sin optimización.

lw $t1, 0($t2)

sw $t1, 0($t3)

tiempo

Orden de ejecución

M I

M D

R L

M I

M D

R L




En este caso el compilador intercala un nop después de cada load word que tenga conflictos con la instrucción siguiente. Y luego trata de reemplazarlo por una instrucción que no tenga conflictos, ubicada antes o después del load word. Las frecuencias de detención disminuyen apreciablemente, como puede observarse en el diagrama anterior.

14.4. Camino de datos y control. A continuación se muestra el camino de datos y el control para un procesador segmentado en cinco etapas. Se asume la detección de la igualdad en la etapa de lectura de registros, esto puede hacerse si el número de etapas de segmentación es reducido. Las señales de control se generan en la etapa de lectura de Registros y Decodificación, ciclo en el cual se sabe cuál instrucción debe ejecutarse. Las señales de control para la etapa de ejecución (ExtOpt, AluSrc, AluCtr) se emplean un ciclo después y son pasadas a dicha etapa a través del registro de segmentación, que separa las etapas. Las señales de control para la etapa de memoria (MemWr, MemRd, MemtoReg) son usadas dos ciclos más tarde. Las señales de control para la etapa de postescritura (RD, RegWr) se emplean tres ciclos después. RD es el número del registro en el que debe escribirse. El diagrama muestra el control y los datos fluyendo en la cañería. El camino no muestra los recursos necesarios para lograr detenciones, anticipaciones y descartes, para solucionar los riesgos, los que se verán más adelante.

0 10 20 30 40 50 60 70

% detención

Sin optimizar Con optimización

gcc spice text




Camino de datos y control del procesador segmentado(pipeline).

AluCtrAluSrcExtOp

RDRegWr

MemRdMemWr

MemtoReg

Inm16a

A

B

PC

S

D

RD1RegWr1

MemRd1 MemWr1

MemtoReg1

M

Reg

add26 inm16

rs

COp funct

rt rd

rt

inm16

MRD2

RegWr2

RD2RegWr2

IR

equal

NextPC

Mem. Inst.

PC+4

Mem. Dat.

Decodificador

Operaciones

PCsel

nPC

br j

MDout

br j

En un ciclo de reloj se activan simultáneamente las siguientes transferencias de control: RD1 = RD; RegWr1 = RegWr; MemtoReg1 = MemtoReg; MemWr1 = MemWr; MemRd1 = MemRd; RD2 = RD1; RegWr2 = RegWr1; A la vez se activan simultáneamente las siguientes transferencias en el camino de datos: /* etapa de búsqueda de instrucción */ IR = MI[PC]; nPC = PC + 4; if (PCsel==0) PC = PC+4; else PC = NextPC; /* riesgo control*/ /* etapa de decodificación */ if (Op == add) { AluCtr=”add” (010); AluSrc=”B”(0); ExtOp=φ; MemRd = 0; MemWr=0; Memtoreg = “S” (0); RD= rd; RegWr =1; PCsel =”+4” (0) }




if (Op == sub) { AluCtr=”sub” (110); AluSrc=”B” (0); ExtOp=φ; MemRd = 0; MemWr=0; Memtoreg = “S” (0); RD= rd; RegWr =1; PCsel ="+4" (0) } if (Op == slt) { AluCtr=”slt” (111); AluSrc="B" (0); ExtOp= φ; MemRd = 0; MemWr=0; Memtoreg = “S” (0); RD= rd; RegWr =1 ; PCsel = "+4" (0) } if (Op == ori) { AluCtr=”or” (001); AluSrc="Op32" (1); ExtOp=”zero” (0); MemRd = 0; MemWr=0; Memtoreg = “S” (0); RD= rt; RegWr =1 ;PCsel = "+4" (0) } if (Op == lw) { AluCtr="add" (010); AluSrc="OP32) (1); ExtOp="sign" (1); MemRd = 1; MemWr=0; Memtoreg = "MDout" (1); RD= rt; RegWr =1; PCsel ="+4" (0) } if (Op == sw) { AluCtr="add" (010); AluSrc="Op32" (1); ExtOp="sign" (1); MemRd = 0; MemWr=1; Memtoreg = φ; RD= rt; RegWr =0; PCsel ="+4" (0) } if (Op == beq) {br =1; j=0; /*Señal de control br */

AluCtr="nop" (φφφ); AluSrc=φ; ExtOp=φ; MemRd = φ; MemWr=0; Memtoreg = φ; RD= 0; RegWr =0 ; if(Equal) PCsel =1; else PCsel =0; } if (Op == j ) { br =0; j=1 ; /* Señal de control j */

AluCtr="nop" (φφφ); AluSrc=φ; ExtOp=φ; MemRd = φ; MemWr=0; Memtoreg = φ; RD= 0; RegWr =0; PCsel =1 } /* lectura de registros */ A = R[rs]; B = R[rt]; inm16a = inm16; /*escritura de registros */ if (RegWr2 ==1) R[RD2] = M; /* riesgo de datos*/ /* cálculo de direcciones de bifurcación y salto /* equal = (R[rs] == R[rt]); if ( (Op == beq) & equal ) NextPC = nPC + SignExt(inm16)*4; if ( Op == j) NextPC = nPC&F0000000 | (add26<<2); /* segmento de operaciones */ if (AluCtr="add" (010) & AluSrc="B" (0) ) S = A + B; /* add */ if (AluCtr="sub" (110) & AluSrc="B" (0) ) S = A - B; /* sub */ if (AluCtr="slt" (111) & AluSrc="B" (0) ) if (A<B) S = 1;else S = 0; /* slt */ if (AluCtr="or" (001) & AluSrc="OP32" (1) & ExtOp="cero" (0) ) S = A or CeroExt(Inm16a); /* ori */ if (AluCtr="add" (010) & AluSrc="Op32" (1) & ExtOp="sign" (1) ) S = A + SignExt(Inm16a); /* lw y sw */ D = B; /* dato a escribir en memoria en sw */




/* segmento memoria de datos */ if (MemRd1 ==1) M = MD[S]; if (MemWr1 ==1) MD[S] = D; if (Memtoreg1=="S" (0 ) ) M = S; if (Memtoreg1=="Mdout" (1 ) ) M = MDout;

14.5. Solución de riesgos.

14.5.1. Unidad de anticipación de datos hacia la unidad de operaciones. El riesgo se detecta cuando en operaciones se tiene una instrucción de tipo R o inmediata que escriba en un registro(RD), y en decodificación una instrucción que lea el registro rs(add, sub, ori, beq, lw) o que lea el registro rt(add, sub, beq). Nótese que no se considera en ningún grupo a la instrucción store word que también lee rs y rt, ya que este riesgo se trata aparte. También existe riesgo cuando en etapa de memoria se tiene una de tipo R o inmediata y en decodificación una instrucción que lee rs o rt, con igual valor al del registro en que se escribirá(RD1). Para solucionar por anticipación de datos hacia la unidad de operaciones se requiere agregar muxes a las entradas de la alu, que permitan ingresar las salidas de la alu y de la memoria, además de los contenidos de los buses de salida del arreglo de registros(busA y busB). Para detectar que la operación que está en la etapa de operaciones sea de tipo R o inmediata se tiene la siguiente condición:

TipoRI = (MemWr==0) & (MemRd==0) & (RegWR==1) Para detectar que la operación que está en la etapa de memoria sea de tipo R o inmediata se tiene la siguiente condición:

TipoRI1 = (MemWr1==0) & (MemRd1==0) & (RegWR1==1) Las instrucciones que leen el registro con campo rs son: add, sub, ori, lw y beq. Exceptuando la instrucción sw que se trata aparte. Las instrucciones que leen el registro con campo rt son: add, sub y beq. Exceptuando la instrucción sw que se trata aparte. Notar que las inmediatas escriben en el registro indicado por el campo rt, también lw escribe en R[rt]. Los controles de los muxes se diseñan según: if (TipoRI ) & (lee_rs) & (rs == RD ) A = Aluout; /*AntA = 1 */ if (TipoRI1) & (lee_rs) & (rs == RD1) A = Mout; /*AntA = 2 */ if (MemRd1==1) && (Cop==”sw”) &&(rs == RD1) A = Mout;




en el resto de los casos A = R[rs]; /*AntA = 0 */ if (TipoRI ) & (lee_rt) & (rt == RD ) B = Aluout; /* AntB = 1 */ if (TipoRI1) & (lee_rt) & (rt == RD1) B = Mout; /* AntB = 2 */ en el resto de los casos B = R[rt]; /* AntB = 0 */

14.5.2. Anticipación de escritura en memoria. Las instrucciones que escriben en un registro, seguidas de un store word que escriba el contenido del registro que aún no se ha grabado, no requieren detener la ejecución de la escritura en memoria si se adelanta la salida de la etapa de memoria(Mout) en el registro de segmentación que almacena el valor que será escrito en la memoria(D). El riesgo se detecta cuando la instrucción que escribe en registro está en la etapa de memoria y el store word en operaciones; y si el número del registro cuyo contenido debe escribirse en memoria(RD) es igual al número del registro en que escribirá la instrucción que está en etapa de memoria(RD1). La señal que controla el mux que anticipa datos, para escritura en memoria, se diseña según: if ( (MemWr == 1) & (RegWr1==1) & (RD==RD1 ) ) D = Mout; /* AntM = 1 */ en el resto de los casos D = B /* AntM = 0 */ Esto considerando que en la decodificación de sw se almacena en el registro destino(RD) el valor del campo rt.

14.5.3. Detención de un ciclo en secuencias: lw-alu Esta solución impide la optimización a nivel del compilador de intercalar un nop e intentar sustituirlo por una instrucción que no genere conflicto con el load word. Se detecta el riesgo cuando el lw está en operaciones(MemRd en 1) y la instrucción que le sigue(que lea el registro en el cual el lw escribe) en decodificación. La condición para la detención está separada en dos partes: Primero las secuencias lw seguidas por instrucciones que leen el registro rs(tipo R, transferencias, inmediatas y beq); que se detectan por:

(MemRd == 1) & ( OP != j) & ( rs ==RD) En segundo lugar las secuencias lw seguidas de instrucciones que leen el registro rt(tipo R y beq) que se detectan según:

(MemRd == 1) & (Op==tipoR | Op==beq ) & ( rt ==RD)




Si la instrucción siguiente es otro load word no produce riesgos, ya que escribe en rt después del anterior(lo sobreescribe). Si la siguiente instrucción es store word, emplea el contenido de rt para escribir en la memoria y puede solucionarse. Las instrucciones inmediatas no leen en registro rt; lo usan para escribir el resultado. Juntando las dos condiciones, se tiene: if ( ( MemRd == 1) & ( Op != j) & ( rs ==RD) | ( MemRd== 1)& ( Op==tipoR | Op==beq) & (rt ==RD) ) { burbuja = 1; válido = 0;} en el resto de los casos burbuja = 0; válido =1; La señal burbuja debe detener el reloj en PC e IR o inhabilitar los write enable de esos registros( WEPC =0; WEIR = 0), esta última es mejor solución electrónica. También debe escribir en la señal de control válido un 0, para propagar una acción nula(o burbuja) en la cañería. Entonces: válido = (∼burbuja)

14.5.4. Descarte(flush) en caso de saltos incondicionales. En caso de no ejecutar la instrucción siguiente a un jump, que ya pasó por etapa de fetch deben eliminarse los efectos de la instrucción siguiente, para esto basta que la instrucción que completó su fetch no modifique un registro o escriba en la memoria. Se detecta mediante: if ( PCsel==1)&(Op==j) flush =1; La señal flush implica limpiar el registro IR, para que cuando se decodifique, en el siguiente ciclo, se generen RegWr=0, MemWr=0 con lo cual se propagan acciones nulas. Esto equivale a reemplazar la instrucción leída por un nop, en forma electrónica.

14.5.5. Descarte(flush) en caso de bifurcaciones. En caso de no ejecutar la instrucción siguiente a un beq, que ya pasó por la etapa de fetch deben eliminarse los efectos de la instrucción siguiente, para esto basta que la instrucción que completó su fetch no modifique un registro o escriba en la memoria. Se detecta mediante: if ( PCsel==1)&(Op==beq) flush =1; También puede diseñarse, según: if ( Equal==1)&(Op==beq) flush =1;

14.5.6. Instrucción No operación. Esta instrucción tiene los 32 bits iguales a cero. Es de tipo R, con el campo funct = 0. Se indica a continuación la decodificación de la instrucción nop, en caso de que el compilador los intercale.




if (Op == nop) { AluCtr=φφφ; AluSrc=φ; ExtOp=φ; MemRd = φ; MemWr=0; Memtoreg = φ; RD= 0; RegWr =0; PCsel =0; válido = 0} además si es nop: rs=0, rt=0, rd =0.

14.6. Camino de datos con solución de riesgos. Las ecuaciones anteriores implican modificaciones a la ruta de datos y el control, las que se ilustran a continuación.

AluCtr

AluSrc

ExtOp

RD

RegWr

MemRd

MemWr

MemtoReg

Inm16a

A

B

S

D

RD1

RegWr1

MemRd1

MemWr1

MemtoReg1

M

RD2

RegWr2

equal

Mem. Dat.

Operaciones

PC

add26

inm16

rs

COp funct

rt rd

rt

inm16

M

RD2

RegWr2

IR

Next PC

Mem. Inst.

PC+4

Decodi ficador

burbuja

reloj

Mout

AluOut

valido

AntM

AntAAntB

PCsel

flush

nPC

MDout

b j

No se muestran las unidades combinacionales que generan las señales: burbuja, AntA, AntB, AntM. El tratamiento de excepciones también requiere efectuar modificaciones al control y a la ruta de datos, que no se discuten en estos apuntes.

universidad tecnica federico santa maria...

Documents