advertisement

Pipelining

50 %
50 %
advertisement
Information about Pipelining

Published on August 5, 2007

Author: stefanosalvatori

Source: slideshare.net

advertisement

Pipelining o Segmentación Cecilia Hernández

Pipelining o Segmentación Idea viene de línea de ensamblaje Dividir un trabajo en n partes secuenciales del mismo tamaño (p1, p2, p3, …, pn), donde cada parte p se realiza en aproximadamente en el mismo tiempo Cada parte p, se procesa en una estación distinta (usando distintos recursos) o equivalentemente pasa a través de una serie de etapas Distintas etapas de distintos trabajos pueden ejecutarse simultáneamente dado que los recursos que ellas utilizan son distintos Ejemplo Trabajo A: compuesto por etapas A1, A2, A3 en donde cada una requiere de recursos R1, R2, R3 respectivamente Trabajo B: compuesto por etapas B1, B2, B3 en donde cada una requiere de recursos R1, R2, R3 respectivamente Luego, A2 y B1, A3 y B2 pueden ejecutarse simultáneamente

Idea viene de línea de ensamblaje

Dividir un trabajo en n partes secuenciales del mismo tamaño (p1, p2, p3, …, pn), donde cada parte p se realiza en aproximadamente en el mismo tiempo

Cada parte p, se procesa en una estación distinta (usando distintos recursos) o equivalentemente pasa a través de una serie de etapas

Distintas etapas de distintos trabajos pueden ejecutarse simultáneamente dado que los recursos que ellas utilizan son distintos

Ejemplo

Trabajo A: compuesto por etapas A1, A2, A3 en donde cada una requiere de recursos R1, R2, R3 respectivamente

Trabajo B: compuesto por etapas B1, B2, B3 en donde cada una requiere de recursos R1, R2, R3 respectivamente

Luego, A2 y B1, A3 y B2 pueden ejecutarse simultáneamente

Analogía: lavado de ropa Ana, Berta, Claudio y Darío tienen una carga de ropa cada uno, las que deben lavar, secar y doblar Lavado dura 30 minutos Secado dura 40 minutos Doblado dura 20 minutos A B C D

Ana, Berta, Claudio y Darío tienen una carga de ropa cada uno, las que deben lavar, secar y doblar

Lavado dura 30 minutos

Secado dura 40 minutos

Doblado dura 20 minutos

Lavado secuencial O R D E N E J E C U C I Ó N Cada persona demora 1.5 horas en estar lista. Lavado secuencial toma 6 horas para 4 cargas. Esto es equivalente a procesador multiciclo. ¿Cómo acelerar la cosa? A B C D 30 40 20 30 40 20 30 40 20 30 40 20 6 PM 7 8 9 10 11 Medianoche Tiempo

Lavado segmentado (pipelined) Cada persona todavía demora 1.5 horas en estar lista. Pero ahora las 4 cargas están listas en sólo 3.5 horas. Aceleración = 1.7 En general, 1 carga de ropa lista cada 40 minutos. Aceleración = 1.5hrs/40min. = 2.25 ¿Cuál sería la aceleración si lavar = secar = doblar? A B C D 6 PM 7 8 9 10 11 Medianoche Tiempo 30 40 40 40 40 20 O R D E N E J E C U C I Ó N

Problemas con reutilizar esquema de multiciclo Problema es que hay conflictos con el uso de recursos. Cuáles? Solución?, se separan Memorias para I y D, se agregan sumadores

Problema es que hay conflictos con el uso de recursos. Cuáles?

Solución?, se separan Memorias para I y D, se agregan sumadores

Pasando de multiciclo a pipeline Si podemos agregar recursos a nuestro esquema multiciclo podemos usarlos en forma más eficiente Paralelismo a nivel de instrucciones Cómo lo hacemos? Tomamos como base las mismas etapas del multiciclo de la ejecución de una instrucción Busqueda Inst, Decodificación, Ejecución, Acceso a Memoria de datos, escritura en registros A medida que vamos desocupando recursos en cada ciclo en la ejecución de una instrucción, los vamos ocupando para la ejecución de la siguiente instrucción

Si podemos agregar recursos a nuestro esquema multiciclo podemos usarlos en forma más eficiente

Paralelismo a nivel de instrucciones

Cómo lo hacemos?

Tomamos como base las mismas etapas del multiciclo de la ejecución de una instrucción

Busqueda Inst, Decodificación, Ejecución, Acceso a Memoria de datos, escritura en registros

A medida que vamos desocupando recursos en cada ciclo en la ejecución de una instrucción, los vamos ocupando para la ejecución de la siguiente instrucción

Ejecutando instrucciones en pipeling Implementación multiciclo In pipeline mode IF ID EX MEM WB IF ID EXE MEM WB Instr. i Instr. i+1 Tiempo ocioso IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB Instr. i Instr. i+1 Instr. i+2

Implementación multiciclo

In pipeline mode

Desempeño de pipelining CPU Uniciclo : CPI = 1 largo ciclo de reloj CPU Multiciclo : CPI > 1, ciclo reloj más corto Pipeline : CPI Ideal = 1 con ciclo reloj corto Latencia , de una sola instrucción puede ser mayor Cada etapa se demora tanto como la más lenta Todas las instrucciones deben pasar a través de todas las etapas incluso si instrucción no la requiere Productividad (throughput) es mejor Cantidad de instrucciones por unidad de tiempo Idealmente la tasa de ejecución de instrucciones es de 1 por tiempo ocupada por etapa, asumiendo que el pipeline esta lleno todo el tiempo En el caso ideal la productividad es n veces mejor si hay n etapas Sin embargo, una instrucción podría requerir menos etapas para completarse

CPU Uniciclo : CPI = 1 largo ciclo de reloj

CPU Multiciclo : CPI > 1, ciclo reloj más corto

Pipeline : CPI Ideal = 1 con ciclo reloj corto

Latencia , de una sola instrucción puede ser mayor

Cada etapa se demora tanto como la más lenta

Todas las instrucciones deben pasar a través de todas las etapas incluso si instrucción no la requiere

Productividad (throughput) es mejor

Cantidad de instrucciones por unidad de tiempo

Idealmente la tasa de ejecución de instrucciones es de 1 por tiempo ocupada por etapa, asumiendo que el pipeline esta lleno todo el tiempo

En el caso ideal la productividad es n veces mejor si hay n etapas

Sin embargo, una instrucción podría requerir menos etapas para completarse

Uniciclo, Multiciclo, Pipelining Clk Ciclo 1 Multiciclo: IF DEC EX MEM WB Ciclo 2 Ciclo 3 Ciclo 4 Ciclo 5 Ciclo 6 Ciclo 7 Ciclo 8 Ciclo 9 Ciclo 10 Load IF DEC EX MEM WB IF DEC EX MEM Load Store Segmentación (pipeline): IF DEC EX MEM WB Store Clk Uniciclo: Load Store Ocio IF R-type IF DEC EX MEM WB R-type Ciclo 1 Ciclo 2

Paralelismo en Pipeline Note que una vez que pipeline está lleno hay 5 instrucciones en ejecución, aunque cada instrucción por separado tiene una mayor latencia IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB IF ID EXE MEM WB 5 instrucciones en ejecución simulatneamente t t+1 t +2 t+3 t+4 t+5 t +6 t+7 t+8 t+9 Instr. i Instr. i+1 Instr. i+2 Instr. i+3 Instr. i+4 Instr. i+5

Note que una vez que pipeline está lleno hay 5 instrucciones en ejecución, aunque cada instrucción por separado tiene una mayor latencia

Requerimientos de implementación 5 etapas para la ejecución de instrucciones A partir de instrucción más larga en multiciclo (load) Etapas correspondientes a las definidas en load Todas las etapas son independientes y aisladas entre sí. Esto significa que la información reunida en la etapa i+1, i+2 deben guardarse para pasarse a la siguiente Para ello se necesitan recursos adicionales los que se implementan en los denominados “ registros pipeline ” ubicados entre las distintas etapas

5 etapas para la ejecución de instrucciones

A partir de instrucción más larga en multiciclo (load)

Etapas correspondientes a las definidas en load

Todas las etapas son independientes y aisladas entre sí. Esto significa que la información reunida en la etapa i+1, i+2 deben guardarse para pasarse a la siguiente

Para ello se necesitan recursos adicionales los que se implementan en los denominados “ registros pipeline ” ubicados entre las distintas etapas

Qué se almacena en los “registros del pipeline” Número de registro donde se almacenará resultado Se sabe en etapa ID (2) y se utiliza en etapa WB (5) Número de registro que contiene dato a ser almacenado en memoria en store Se conoce en etapa ID (2) y se ocupa en MEM(4) Valores inmediatos para instrucciones aritméticas y lógicas y para instrucciones de acceso a memoria (cálculo de direcciones de memoria) load/store y direcciones de branchs Se conocen en etapa ID y se usan en etapa ALU (3)

Número de registro donde se almacenará resultado

Se sabe en etapa ID (2) y se utiliza en etapa WB (5)

Número de registro que contiene dato a ser almacenado en memoria en store

Se conoce en etapa ID (2) y se ocupa en MEM(4)

Valores inmediatos para instrucciones aritméticas y lógicas y para instrucciones de acceso a memoria (cálculo de direcciones de memoria) load/store y direcciones de branchs

Se conocen en etapa ID y se usan en etapa ALU (3)

Sección de datos en Pipeline IF ID EXE MEM WB IF/ID ID/EXE EXE/MEM MEM/WB

Visión alternativa, usando recursos MI Reg MD MI Reg MD MI Reg MD MI Reg MD tiempo Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4 Ciclo 5 Ciclo 6 Ciclo 7 Instrucciones instr1 instr2 instr3 instr4

Usando como base uniciclo Donde debería ir los registros pipeline

Donde debería ir los registros pipeline

Notación Registros pipeline nombrado con los nombres de etapas Información fluye de izquierda a derecha excepto en Cuando se escribe en registros Modificando PC

Registros pipeline nombrado con los nombres de etapas

Información fluye de izquierda a derecha excepto en

Cuando se escribe en registros

Modificando PC

Qué información se almacena en registros pipeline Datos Instrucción, registros A y B, ALUout, MDR, PC + 4, Inmediato, Con traspaso de datos entre etapas cuando se requiera Control Señales de control RegDst, Branch, MemRead, MemtoReg, ALUop, MemWrite, ALUSrc, RegWrite Se van consumiendo en etapas a medida que se requieran

Datos

Instrucción, registros A y B, ALUout, MDR, PC + 4, Inmediato,

Con traspaso de datos entre etapas cuando se requiera

Control

Señales de control

RegDst, Branch, MemRead, MemtoReg, ALUop, MemWrite, ALUSrc, RegWrite

Se van consumiendo en etapas a medida que se requieran

Conflictos Evitan que sea ideal 3 tipos Estructurales donde dos instrucciones en diferentes etapas quieren usar el mismo recurso. Resuelto usando más recursos Separación de memoria de instrucciones de la de datos, y agregar ALUs Haciendo que todas las instrucciones se ejecuten en el mismo número de etapas, aunque se desperdicien ciclos Datos cuando una instrucción en el pipeline es dependiente de otra instrucción todavía en el pipeline Control cuando un branch exitoso o procedimiento

Evitan que sea ideal

3 tipos

Estructurales donde dos instrucciones en diferentes etapas quieren usar el mismo recurso. Resuelto usando más recursos

Separación de memoria de instrucciones de la de datos, y agregar ALUs

Haciendo que todas las instrucciones se ejecuten en el mismo número de etapas, aunque se desperdicien ciclos

Datos cuando una instrucción en el pipeline es dependiente de otra instrucción todavía en el pipeline

Control cuando un branch exitoso o procedimiento

Conflicto estructural: una sola memoria Tiempo (ciclos de reloj) Soluciones: - detener el pipeline (stall) - replicar la memoria (memoria de datos separada de memoria de instrucciones) Mem Sec. Instr. Load Instr 1 Instr 2 Instr 3 Instr 4 ALU Mem Reg Mem Reg ALU Mem Reg Mem Reg ALU Mem Reg Mem Reg ALU Reg Mem Reg ALU Mem Reg Mem Reg

Solución 1: Detención del pipeline (stalling) Tiempo (ciclos reloj) Mem Sec. Instr Load Instr 1 Instr 2 Instr 3 Instr 4 Reg Mem Reg Reg Mem Reg Si 1 de cada 4 instrucciones es un load: CPI = 1.25  100% utilización de puerta de lectura de la memoria  CPI no puede ser menor que 1.25 a menos que tengamos memoria de datos e instrucciones separadas ALU Mem ALU Mem Reg Mem Reg ALU Mem Reg Mem Reg ALU ALU Mem Reg Mem Reg

Solución 2: Replicar hardware Memoria de datos separada de memoria de instrucciones Conocida como “Arquitectura de Harvard” Procesadores reales implementan esta solución a nivel de memoria cache de primer nivel (cache de instrucciones y cache de datos) Cache de nivel 2, 3 y DRAM son unificadas IMem F L U J O D E P R O G R A M A Tiempo (ciclos de reloj) LW ADD SUB LW LW Reg DMem Reg Reg DMem Reg ALU IMem ALU IMem Reg DMem Reg ALU IMem Reg DMem Reg ALU ALU IMem Reg DMem Reg

Memoria de datos separada de memoria de instrucciones

Conocida como “Arquitectura de Harvard”

Procesadores reales implementan esta solución a nivel de memoria cache de primer nivel (cache de instrucciones y cache de datos)

Cache de nivel 2, 3 y DRAM son unificadas

Conflictos estructurales: Acceso banco de registros Sec. Instr Load Instr 1 Reg Mem Reg Reg Reg Tiempo (ciclos de reloj) ALU Mem ALU Mem

Solución 1: Detener el pipeline (stalling) F L U J O D E P R O G R Tiempo (ciclos de reloj) LW ADD SUB LW LW Soluciona el conflicto, pero introduce una “burbuja”(ciclo ocioso) en el pipeline  CPI > 1 Ej. Si el conflicto se produce en una de cada 4 instrucciones, CPI = 1.25 ALU Mem Reg Mem ALU Mem Reg Mem Reg Mem Reg ALU Reg ALU Reg Reg Mem ALU Mem Reg Mem Reg Reg burbuja

Solución 2: Regularizar el pipeline Todas las instrucciones pasan por todas las etapas Como cada etapa usa diferentes recursos hardware, no hay conflictos estructurales F L U J O D E P R O G R A M A Tiempo (ciclos de reloj) LW ADD SUB LW LW Latencia de instrucciones ALU aumenta de 4 a 5, pero CPI = 1 ALU Mem Reg Mem Reg Mem ALU Mem Reg Mem Mem ALU Reg Reg Mem Reg Mem Reg ALU Mem Reg Reg Mem Reg ALU

Todas las instrucciones pasan por todas las etapas

Como cada etapa usa diferentes recursos hardware, no hay conflictos estructurales

Siguiendo la ejecución de una instrucción en las 5 etapas (1) Etapa 1: Búsqueda de instrucción e incremento de PC ( lo mismo para todas las instrucciones) Instrucción es extraída de memoria de instrucciones desde la dirección apuntada por PC. Como la instrucción se necesita para las siguientes etapas se almacena en registro pipeline IF/ID PC = PC + 4 Necesitado para la siguiente instrucción o cálculo de branch, tambien se almacena en registro pipeline IF/ID Recursos usados: Memoria Instrucciones y ALU Registro pipeline: contiene instrucción y PC incrementado

Etapa 1: Búsqueda de instrucción e incremento de PC ( lo mismo para todas las instrucciones)

Instrucción es extraída de memoria de instrucciones desde la dirección apuntada por PC. Como la instrucción se necesita para las siguientes etapas se almacena en registro pipeline IF/ID

PC = PC + 4

Necesitado para la siguiente instrucción o cálculo de branch, tambien se almacena en registro pipeline IF/ID

Recursos usados: Memoria Instrucciones y ALU

Registro pipeline: contiene instrucción y PC incrementado

Etapa 1: IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] Instrucción [15-11] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo lw IF

Siguiendo la ejecución de una instrucción en las 5 etapas (2) Etapa 2: Se decodifica instrucción y se leen los registros (lo mismo para todas las instrucciones) Tenemos en IF/ID todo lo que se necesita en las siguientes etapas: La instrucción y el PC incrementado Se usan los identificadores de registros para extraer los datos que contienen Se obtiene campo inmediato si instrucción lo posee y se extiende en signo o no según instrucción Se utiliza instrucción para definir señales de control Recursos utilizados: Banco de registros y unidad de control ID/EX contiene PC, instrucción, contenido de rs y rt, inmediato extendido,señales de control generadas por unidad de control

Etapa 2: Se decodifica instrucción y se leen los registros (lo mismo para todas las instrucciones)

Tenemos en IF/ID todo lo que se necesita en las siguientes etapas:

La instrucción y el PC incrementado

Se usan los identificadores de registros para extraer los datos que contienen

Se obtiene campo inmediato si instrucción lo posee y se extiende en signo o no según instrucción

Se utiliza instrucción para definir señales de control

Recursos utilizados: Banco de registros y unidad de control

ID/EX contiene PC, instrucción, contenido de rs y rt, inmediato extendido,señales de control generadas por unidad de control

Etapa 2 : ID Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] Instrucción [15-11] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo lw ID

Siguiendo la ejecución de una instrucción en las 5 etapas (3) Etapa 3: Depende del tipo de instrucción que se está ejecutando. Por ejemplo load. Entonces en esta etapa se calcula dirección de memoria Los operandos fuentes a ALU vienen de ID/EX (rs e Inmmediato extendido en signo) Resultado de ALU se almacena en EX/MEM Contenidos de rs e Inmediato ya no se necesitarán más PC se continúa almacenando por posibles exepciones ( caso que se deba interrumpir la ejecución de la instrucción, por ejemplo, la dirección de memoria este incorrecta) Se necesita mantener la información respecto al identificador de rt Recursos necesitados: ALU para cálculo de dirección de memoria en caso de load,store. Se necesitan 2 ALUs para caso de branch (uno para cálculo de condición y otro para cálculo dirección de salto) EX/MEM almacena Resultado de ALU (loads/stores y aritméticas/lógicas) Identificación rt (addi, load) y rd (aritméticas/lógicas), contenido rs (stores) PC para caso excepcional

Etapa 3: Depende del tipo de instrucción que se está ejecutando. Por ejemplo load. Entonces en esta etapa se calcula dirección de memoria

Los operandos fuentes a ALU vienen de ID/EX (rs e Inmmediato extendido en signo)

Resultado de ALU se almacena en EX/MEM

Contenidos de rs e Inmediato ya no se necesitarán más

PC se continúa almacenando por posibles exepciones ( caso que se deba interrumpir la ejecución de la instrucción, por ejemplo, la dirección de memoria este incorrecta)

Se necesita mantener la información respecto al identificador de rt

Recursos necesitados: ALU para cálculo de dirección de memoria en caso de load,store. Se necesitan 2 ALUs para caso de branch (uno para cálculo de condición y otro para cálculo dirección de salto)

EX/MEM almacena

Resultado de ALU (loads/stores y aritméticas/lógicas)

Identificación rt (addi, load) y rd (aritméticas/lógicas), contenido rs (stores)

PC para caso excepcional

Etapa 3: EX Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] Instrucción [15-11] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo lw EX

Siguiendo la ejecución de una instrucción en las 5 etapas (4) Etapa 4: Acceso a memoria de datos. Accesar memoria con dirección calculada en etapa anterior y almacenada en EX/MEM Almacenar resultado de load en MEM/WB Recursos usados: Memoria de datos MEM/WB almacena Dato leído de memoria (loads) Resultado de ALU (instr aritméticas/lógicas) almacenados en EX/MEM Identificador de registro a escribir (rt para loads, rd para aritméticas/lógicas) No se necesita almacenar PC por más tiempo

Etapa 4: Acceso a memoria de datos.

Accesar memoria con dirección calculada en etapa anterior y almacenada en EX/MEM

Almacenar resultado de load en MEM/WB

Recursos usados: Memoria de datos

MEM/WB almacena

Dato leído de memoria (loads)

Resultado de ALU (instr aritméticas/lógicas) almacenados en EX/MEM

Identificador de registro a escribir (rt para loads, rd para aritméticas/lógicas)

No se necesita almacenar PC por más tiempo

Etapa 4: MEM Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] Instrucción [15-11] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo lw MEM

Siguiendo la ejecución de una instrucción en las 5 etapas (5) Etapa 5: WB (Write back a registro) usado en loads y aritméticas/lógicas Identificador de registro de escritura (rt o rd) y dato a escribir vienen en MEM/WB No se necesita guardar nada porque es el último paso en la ejecución de la instrucción Recurso usado: Banco de registros Conflicto estructural por uso de banco de registros eliminado con la normalización en que cada instrucción se ejecuta en 5 etapas (independiente si la requiere o no)

Etapa 5: WB (Write back a registro) usado en loads y aritméticas/lógicas

Identificador de registro de escritura (rt o rd) y dato a escribir vienen en MEM/WB

No se necesita guardar nada porque es el último paso en la ejecución de la instrucción

Recurso usado: Banco de registros

Conflicto estructural por uso de banco de registros eliminado con la normalización en que cada instrucción se ejecuta en 5 etapas (independiente si la requiere o no)

Etapa 5: WB Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] Instrucción [15-11] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo lw WB

Varias instrucciones en pipeline Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Instrucción [20-16] Instrucción [15-11]

Varias instrucciones en pipeline Ciclo 1 lw $1, 4($3) #IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 Instrucción [20-16] Instrucción [15-11]

Varias instrucciones en pipeline Ciclo 2 lw $1, 4($3) #ID add $3, $4, $5 #IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21]RS Instrucción [20-16]RT 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 2 Instrucción [20-16]RT Instrucción [15-11]RD 0 M U X 1

Varias instrucciones en pipeline Ciclo 3 lw $1, 4($3) #EX sw $4, 8($5) #IF add $3, $4, $5 #ID Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21]RS Instrucción [20-16]RT 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 2 3 Instrucción [20-16]RT Instrucción [15-11]RD 0 M U X 1 RT

Varias instrucciones en pipeline Ciclo 4 lw $1, 4($3) #MEM sw $4, 8($5) #ID add $3, $4, $5 #EX and $1, $2, $3 #IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21]RS Instrucción [20-16]RT 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 2 3 4 Instrucción [20-16]RT Instrucción [15-11]RD 0 M U X 1 RD RT

Varias instrucciones en pipeline Ciclo 5 lw $1, 4($3) #WB sw $4, 8($5) #EX add $3, $4, $5 # MEM and $1, $2, $3 #ID beq $2, $3, L1 #IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21]RS Instrucción [20-16]RT 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 2 3 4 5 Instrucción [20-16]RT Instrucción [15-11]RD 0 M U X 1 RT RD RT

Tipos de conflictos de datos Conflicto de Datos ocurre cuando una instrucción en el pipeline es dependiente de otra instrucción todavía en el pipeline I1: add r1, r2, r3 I2: sub r4, r1, r5 I3: or r2, r6, r7 I4: and r1, r8, r9

Conflicto de Datos ocurre cuando una instrucción en el pipeline es dependiente de otra instrucción todavía en el pipeline

Tipos de conflictos de datos RAW (read after write) Instrucción I1 genera un dato que instrucción I2 usa I1 debe ejecutarse antes que I2 I1: add r1, r2, r3 I2: sub r4, r1, r5 I3: or r2, r6, r7 I4: and r1, r8, r9

RAW (read after write)

Instrucción I1 genera un dato que instrucción I2 usa

I1 debe ejecutarse antes que I2

Tipos de conflictos de datos WAW (write after write) Instrucciones I1 e I4 escriben en el mismo registro I1 debe ejecutarse antes que I4 ¿Por qué no puede producirse en MIPS segmentado? I1: add r1, r2, r3 I2: sub r4, r1, r5 I3: or r2, r6, r7 I4: and r1, r8, r9

WAW (write after write)

Instrucciones I1 e I4 escriben en el mismo registro

I1 debe ejecutarse antes que I4

¿Por qué no puede producirse en MIPS segmentado?

Tipos de conflictos de datos WAR (write after read) Instrucción I1 lee un registro que instrucción I3 escribe I1 debe ejecutarse antes que I3 ¿Por qué no puede producirse en MIPS segmentado? I1: add r1, r2, r3 I2: sub r4, r1, r5 I3: or r2, r6, r7 I4: and r1, r8, r9

WAR (write after read)

Instrucción I1 lee un registro que instrucción I3 escribe

I1 debe ejecutarse antes que I3

¿Por qué no puede producirse en MIPS segmentado?

Conflicto de datos (RAW) Flechas hacia atrás representan conflictos: no se puede usar un dato hasta que se haya generado Sec. Instr Tiempo (ciclos reloj) add r1 ,r2,r3 sub r4, r1 ,r3 and r6, r1 ,r7 or r8, r1 ,r9 xor r10, r1 ,r11 ALU Im Reg Dm Reg Reg Dm Reg Reg Dm Reg Im ALU Reg Dm Reg ALU Im ALU Im ALU Im Reg Dm Reg

Flechas hacia atrás representan conflictos: no se puede usar un dato hasta que se haya generado

Solución: forwarding (redireccionamiento) Tiempo (ciclos reloj) Pasar dato directamente de la etapa en que se genera a la etapa en que se usa Instrucción “or r9, r1, r9” no necesita forwarding si se define orden lectura-escritura en el banco de registros Sec Instr add r1 ,r2,r3 sub r4, r1 ,r3 and r6, r1 ,r7 or r8, r1 ,r9 xor r10, r1 ,r11 ALU Im Reg Dm Reg ALU Im Reg Dm Reg ALU Im Reg Dm Reg Im ALU Reg Dm Reg ALU Im Dm Reg Reg

Límites de forwarding Forwarding elimina conflicto de datos cuando dato se genera en la misma etapa en que se utiliza, o antes ALU – ALU (EX - EX) ALU – SW (EX – MEM) LW – SW (MEM – MEM) ¿Qué pasa cuando dato se genera en etapa posterior a etapa de uso? Reg Tiempo (ciclos de reloj) lw $1 , 0($2) sub $4, $1 , $3 IF ID/RF EX MEM WB ALU Im Dm Reg Dm Reg Reg or $10, $11, $12 Reg Dm Reg ALU Im Im ALU

Forwarding elimina conflicto de datos cuando dato se genera en la misma etapa en que se utiliza, o antes

ALU – ALU (EX - EX)

ALU – SW (EX – MEM)

LW – SW (MEM – MEM)

¿Qué pasa cuando dato se genera en etapa posterior a etapa de uso?

Soluciones a conflicto de datos LW – ALU Load retrasado Similar a salto retrasado, intrucción en el “delay slot” no puede utilizar resultado del load Visible en ISA Stall Hardware detecta si instrucción siguiente a load utiliza resultado, y retrasa su ejecución hasta que el dato esté disponible Introduce burbuja en el pipeline Mismo impacto en desempeño que load retrasado, pero compilador no necesita insertar NOP Técnica conocida como “pipeline interlock” Reg Tiempo (ciclos de reloj) lw $1 , 0($2) sub $4, $1 , $3 IF ID/RF EX MEM WB ALU Im Dm Reg Dm Reg Reg or $10, $11, $12 Reg Dm Reg burbuja ALU Im Im ALU

Load retrasado

Similar a salto retrasado, intrucción en el “delay slot” no puede utilizar resultado del load

Visible en ISA

Stall

Hardware detecta si instrucción siguiente a load utiliza resultado, y retrasa su ejecución hasta que el dato esté disponible

Introduce burbuja en el pipeline

Mismo impacto en desempeño que load retrasado, pero compilador no necesita insertar NOP

Técnica conocida como “pipeline interlock”

Optimización por software Compilador puede insertar instrucción independiente después del load para reducir CPI Funciona para load retrasados e interlocks Original (lw retrasado) Original (interlock) Optimizado I1: lw $1, 0($2) I2: nop I3: sub $4, $1, $3 I4: or $10, $11, $12 I1: lw $1, 0($2) I2: sub $4, $1, $3 I3: or $10, $11, $12 burbuja I1: lw $1, 0($2) I3: or $10, $11, $12 I2: sub $4, $1, $3 Reg Tiempo (ciclos de reloj) lw $1 , 0($2) sub $4, $1 , $3 IF ID/RF EX MEM WB ALU Im Dm Reg Dm Reg Reg or $10, $11, $12 Reg Dm Reg ALU Im Im ALU

Compilador puede insertar instrucción independiente después del load para reducir CPI

Funciona para load retrasados e interlocks

Original (lw retrasado) Original (interlock) Optimizado

Conflicto de datos en load-add lw $1 , 4($3) #WB and $2, $1 , $3 #ID beq $2, $3, L1 #IF Leer dirección Instrucción [31-0] Memoria de Instrucciones Leer registro 1 Lect. dato 1 Lect. dato 2 Escribir dato Escribir registro Leer registro 2 Registros ALU Zero result Add 1 M U X 0 0 M U X 1 P C Leer dirección Escribir dirección Escribir dato Lect. dato Memoria de Datos 4 Instrucción [25-21] Instrucción [20-16] 16 32 Instrucción [15-0] Desp. Izq. Add IF/ID ID/EX EX/MEM MEM/WB 1 M U X 0 Ext Signo Reloj: 1 2 3 Conflicto Load debe escribir en $1 y add debe leer $1. Lectura debe ocurrir despues de escritura 0 M X 1 RT Instrucción [20-16]RT Instrucción [15-11]RD

Ejecución en pipeline con forwarding y detección de conflicto

Conflicto de datos en load-and

Conflicto de datos en load-and

Conflicto de datos en load-add (agregando burbuja)

Conflicto de datos con load-and

Conflicto de datos en load-and

Conflicto de datos en load-and

Conflictos de control Producidos por instrucciones branch No se puede leer próxima instrucción hasta saber cuál es el siguiente PC Qué hacer Esperar Saltos retrasados Predecir

Producidos por instrucciones branch

No se puede leer próxima instrucción hasta saber cuál es el siguiente PC

Qué hacer

Esperar

Saltos retrasados

Predecir

Solución #1: Esperar: bloquear el pipeline Sec. Instr Tiempo (ciclos reloj) Add Beq Load Reg Mem Reg Reg Mem Reg Reg Mem Reg Mem potencial perdido Instrucción branch se ejecuta en tres ciclos Dos ciclos perdidos esperando por siguiente PC Solución parcial: Mover cálculo de siguiente PC al final de la etapa de decodificación Aún se pierde un ciclo ALU Mem ALU Mem ALU

Instrucción branch se ejecuta en tres ciclos

Dos ciclos perdidos esperando por siguiente PC

Solución parcial: Mover cálculo de siguiente PC al final de la etapa de decodificación

Aún se pierde un ciclo

Solución #2: saltos retrasados Sec. Inst Tiempo (ciclos reloj) Add Beq Misc Reg Mem Reg Reg Mem Reg Mem Reg Mem Reg Load Mem Reg Mem Reg Salto retrasado: instrucción que sigue al salto se ejecuta de todas formas Afecta ISA Costo 0 ciclos si compilador encuentra instrucción que se ejecute de todas formas, 1 ciclo si hay que llenar el delay slot con un NOP Mayor paralelismo a nivel de instrucciones  más delay slots por salto  salto retrasado es menos útil ALU Mem ALU Mem ALU ALU

Salto retrasado: instrucción que sigue al salto se ejecuta de todas formas

Afecta ISA

Costo

0 ciclos si compilador encuentra instrucción que se ejecute de todas formas, 1 ciclo si hay que llenar el delay slot con un NOP

Mayor paralelismo a nivel de instrucciones  más delay slots por salto  salto retrasado es menos útil

Compilador puede llenar el slot Programa original Programa optimizado Eficiencia Ej. 15% de saltos, y compilador puede llenar el slot en un 80% de los casos CPI = 1 + 0.15*0.2*1 = 1.03 (3% degradación) Mayor paralelismo a nivel de instrucciones (ej. pipeline más profundo)  más slots por salto  más difícil llenar slots  menor eficiencia Ej. 2 slots por salto, 15% de saltos, compilador puede llenar primer slot en el 80% de los casos, pero segundo slot en sólo el 25% de los casos CPI = 1 + 0.15*(0.2*1 + 0.75*1) = 1.14 (14% degradación) ¿Por qué no podemos mover instrucciones I2 – I5 al slot? I1: xor $23, $7, $1 I2: and $3, $12, $10 I3: or $5, $2, $8 I4: add $3, $5, $7 I5: add $2, $6, $7 I6: beq $3, $2, ROTULO I7: nop I8: lw $5, $6, $17 I2: and $3, $12, $10 I3: or $5, $2, $8 I4 add $3, $5, $7 I5: add $2, $6, $7 I6: beq $3, $2, ROTULO I1: xor $23, $7, $1 I8: lw $5, $6, $17

Programa original Programa optimizado

Eficiencia

Ej. 15% de saltos, y compilador puede llenar el slot en un 80% de los casos

CPI = 1 + 0.15*0.2*1 = 1.03 (3% degradación)

Mayor paralelismo a nivel de instrucciones (ej. pipeline más profundo)  más slots por salto  más difícil llenar slots  menor eficiencia

Ej. 2 slots por salto, 15% de saltos, compilador puede llenar primer slot en el 80% de los casos, pero segundo slot en sólo el 25% de los casos

CPI = 1 + 0.15*(0.2*1 + 0.75*1) = 1.14 (14% degradación)

I1: xor $23, $7, $1

I2: and $3, $12, $10

I3: or $5, $2, $8

I4: add $3, $5, $7

I5: add $2, $6, $7

I6: beq $3, $2, ROTULO

I7: nop

I8: lw $5, $6, $17

I2: and $3, $12, $10

I3: or $5, $2, $8

I4 add $3, $5, $7

I5: add $2, $6, $7

I6: beq $3, $2, ROTULO

I1: xor $23, $7, $1

I8: lw $5, $6, $17

Solución #3: predecir el salto Predicción de saltos Adivinar resultado y continuar con siguiente instrucción Verificar resultado y corregir si predicción fue incorrecta Implica eliminar instrucción incorrecta del pipeline Costo 0 ciclos predicción correcta, 1 ciclo predicción incorrecta Ej. Correcta 50%: CPIbranch = (1*0.5 + 2*0.5) = 1.5 30% branch: CPItotal = (1*0.7 + 1.5*0.3) = 1.15 Mejorar predicción: utilizar historia del salto (~90% correcto) Sec Inst Tiempo (ciclos reloj) Add Beq Load Reg Mem Reg Reg Mem Reg Mem Reg Mem Reg ALU Mem ALU Mem ALU

Predicción de saltos

Adivinar resultado y continuar con siguiente instrucción

Verificar resultado y corregir si predicción fue incorrecta

Implica eliminar instrucción incorrecta del pipeline

Costo

0 ciclos predicción correcta, 1 ciclo predicción incorrecta

Ej. Correcta 50%: CPIbranch = (1*0.5 + 2*0.5) = 1.5

30% branch: CPItotal = (1*0.7 + 1.5*0.3) = 1.15

Mejorar predicción: utilizar historia del salto (~90% correcto)

Organización de CPU segmentada Examinar sección de datos y control Asociar recursos con estados Detectar y resolver conflictos entre instrucciones Activar señales de control en las etapas apropiadas del pipeline

Examinar sección de datos y control

Asociar recursos con estados

Detectar y resolver conflictos entre instrucciones

Activar señales de control en las etapas apropiadas del pipeline

Control en pipeline Control se genera en etapa Reg/Dec Control para Exec (ExtOp, AluSrc,…) se utilizan 1 ciclo después Control para Mem (MemWr) se utiliza 2 ciclos después Control para WB (MemToReg, RegWr,…) se utiliza 3 ciclos después) Control estacionario: señales de control viajan junto con los datos IF/ID Register ID/Ex Register Ex/Mem Register Mem/Wr Register Reg/Dec Exec Mem ExtOp ALUOp RegDst ALUSrc MemWr MemtoReg RegWr Main Control ExtOp ALUOp RegDst ALUSrc MemtoReg RegWr MemtoReg RegWr MemtoReg RegWr MemWr MemWr Wr RegDst RegDst

Control se genera en etapa Reg/Dec

Control para Exec (ExtOp, AluSrc,…) se utilizan 1 ciclo después

Control para Mem (MemWr) se utiliza 2 ciclos después

Control para WB (MemToReg, RegWr,…) se utiliza 3 ciclos después)

Control estacionario: señales de control viajan junto con los datos

Resumen Pipelining es forma natural de paralelismo Maximizar uso de recursos ejecutando múltiples instrucciones en diferentes etapas Conflictos Estructurales: competencia por uso de hardware Control: dirección de siguiente instrucción depende de resultado de instrucción en ejecución Datos: secuencia de ejecución limitada por dependencias de datos Pipeline simple (MIPS) Conflictos eliminados por diseño (estructurales, WAW, WAR) Conflictos de control manejados como saltos retrasados Conflictos RAW manejados por forwarding (ALU), stalling (loads) Excepciones aumentan complejidad del control Aún peor con formas más agresivas de paralelismo (superscalar, VLIW)

Pipelining es forma natural de paralelismo

Maximizar uso de recursos ejecutando múltiples instrucciones en diferentes etapas

Conflictos

Estructurales: competencia por uso de hardware

Control: dirección de siguiente instrucción depende de resultado de instrucción en ejecución

Datos: secuencia de ejecución limitada por dependencias de datos

Pipeline simple (MIPS)

Conflictos eliminados por diseño (estructurales, WAW, WAR)

Conflictos de control manejados como saltos retrasados

Conflictos RAW manejados por forwarding (ALU), stalling (loads)

Excepciones aumentan complejidad del control

Aún peor con formas más agresivas de paralelismo (superscalar, VLIW)

Material adicional Existen simuladores que permiten clarificar el funcionamiento del pipeline MIPSim32, accesible en website del curso WinMIPS64, Simulador de MIPS de 64 bits, también accesible en website del curso Otro sitio web con simulador de pipeline : http://bellerofonte.dii.unisi.it/WEBMIPS/

Existen simuladores que permiten clarificar el funcionamiento del pipeline

MIPSim32, accesible en website del curso

WinMIPS64, Simulador de MIPS de 64 bits, también accesible en website del curso

Otro sitio web con simulador de pipeline : http://bellerofonte.dii.unisi.it/WEBMIPS/

Add a comment

Related pages

Pipeline (Prozessor) – Wikipedia

Durch das Pipelining wird der Gesamtdurchsatz gegenüber Befehlsabarbeitung ohne Pipelining erhöht. Die Gesamtzeit für die Pipeline-Verarbeitung mit ...
Read more

Pipelining – Wikipedia

Pipelining steht für. Pipelining als Mikroarchitektur in Prozessoren: Pipeline (Prozessor) HTTP-Pipelining, Technik, bei der mehrere HTTP-Anfragen einem ...
Read more

Pipelining - Elektronik-Kompendium.de

Pipelining. Die Befehlsausführung in einem Prozessor erfolgt wie an einem Fließband (Pipeline). Eine Pipeline ist eine Abfolge von Verarbeitungseinheiten ...
Read more

Instruction pipelining - Wikipedia, the free encyclopedia

Instruction pipelining is a technique that implements a form of parallelism called instruction-level parallelism within a single processor. It therefore ...
Read more

Pipelining - technet.microsoft.com

Pipelining in der Exchange-Verwaltungsshell bezeichnet den Vorgang, bei dem ein Cmdlet beim Ausführen einer Operation die Ausgabe eines anderen Cmdlets ...
Read more

What is Pipelining? Webopedia Definition

Pipelining is also called pipeline processing. (2) A similar technique used in DRAM, in which the memory loads the requested memory contents into a small ...
Read more

Pipelining – Wikipedie

Pipelining neboli zřetězené zpracování, či překrývání strojových instrukcí. Základní myšlenkou je rozdělení zpracování jedné instrukce ...
Read more

What is pipelining? - Definition from WhatIs.com

Continue Reading About pipelining. Tep Dobry's Computer Architecture course at the University of Hawaii provides some illustrated explanations of pipelining .
Read more

Pipelining Funktion in Firefox aktivieren - winfaq.de

Diese Funktion ist Standardmäßig ausgeschaltet, da einige Webserver Pipelining nicht unterstützen und es dadurch zu Fehlern bei laden der Webseite ...
Read more

Browser schneller durch Pipelining - PC-WELT

In Firefox lässt sich Pipelining mit nur wenigen Schritten aktivieren. Hier sollten Sie allerdings beachten, dass dafür einige Schritte in den ...
Read more