Paralelización del procesamiento a nivel de instrucción 1
sábado, 8 de octubre de 2022 17:26
Paralelismo
Def. Técnica de programación e implementación en la que se pretende realizar operaciones simultáneamente,
con el fin de reducir tiempos de ejecución, en un procesador.
Bit Datos
Tipos de paralelismo Tareas
(a nivel de)
Instrucciones
Hilos
Paralelismo a nivel de instrucciones (ILP)
Por hardware - ejecución -Segmentación pipeline
Enfoque: -Ejecución fuera de orden
Por software - compilación Tipos de ILP:
-VLIW
- CPU's superescalares
Bloque básico: Es una sección de código secuencial que no presenta ramificaciones (branches) hasta el final
del mismo.
Worse Case Execution Time - WCET
Corresponde al tiempo máximo que tarda en ejecutar un código
en un hardware específico.
Dado un programa con N bloques básicos, donde cada bloque Bi,
que posee un tiempo de ejecución máximo ci, se ejecuta un
número de veces xi, el WCET es:
Pipelining
Técnica utilizada en el diseño de CPUs para aumentar el rendimiento, mediante la separación de las etapas en
el proceso de ejecución de una instrucción.
Premisas: -Todas las instrucciones pasan por todas las etapas
-Etapas no comparten recursos de hardware entre sí.
-Tiempo de propagación entre etapas es el mismo.
-Instrucciones independientes entre sí.
-Las etapas se pueden aislar temporalmente
Resumen IIP página 1
Paralelización del procesamiento a nivel de instrucción 1
sábado, 8 de octubre de 2022 17:26
Etapas de un pipeline: -Búsqueda de instrucción (IF)
-Decodificación de instrucción (ID)
-Ejecución /Dir efectiva (Ex): operaciones en ALU
-Accesos a memoria (MEM)
-Escritura a registros (WB)
Uso en Hardware
Pipeline ideal
Performance improvement
La ganancia en el desempeño debido al pipeline
Ventajas
-Aumenta el rendimiento del CPU.
-Brinda determinismo en ejecución de instrucciones.
Desventajas
-Etapas e instrucciones lentas afectan el rendimiento general
-Mayor complejidad, más hardware.
-Latencia es ligeramente mayor.
Riesgos
Riesgos estructurales: conflictos de hardware entre instrucciones.
Riesgos de datos: Dependencias reales entre datos de instrucciones
Riesgos de control: saltos y branches.
Stall
Un detenimiento de la siguiente instrucción debido a un riesgo.
Se deben tomar en cuenta el detenimiento por instrucción :
Riesgo estructural
Problema: Cuando no hay recursos necesarios para evitar conflictos en uso de hardware
se tiene un riesgo estructural.
Solución: Se requieren unidades funcionales duplicadas para alojar recursos en todas las
posibles combinaciones de instrucciones o uso de stall que es la solución más simple
Unidad funcional: ALU, fpALU, Multiplicadores, Comparadores, MAC, etc.
Resumen IIP página 2
Paralelización del procesamiento a nivel de instrucción 1
sábado, 8 de octubre de 2022 17:26
Riegos de datos
Problema: Ocurren cuando el pipeline se cambia el orden de acceso a lectura/escritura de operando, de
forma que el orden difiere de la ejecución secuencia en un procesador sin pipeline. Es decir se necesita un
dato que aún no ha sido creado.
Soluciones: Uso de stalls o adelantamiento, nop, calendarización
Adelantamiento: Consiste en mover el resultado de un registro
directamente hacia la siguiente etapa donde se necesita,
sin esperar al WB.
Stalls
Situaciones en las que pueden ocurrir riesgos de datos:
-RAW: Lectura después de escritura
-WAR: Escritura después de lectura
-WAW: Escritura después de escritura
Riesgo de control
Problema: Ocurren cuando al tener la ejecución de una instrucción branch se puede modificar o no el
valor del PC, alterando el flujo de ejecución del programa. Dependiendo de si el salto se toma o no
(etapa ID), la siguiente instrucción sería o no la correcta.
Solución: Stall de un ciclo, predicción de salto estrategia basada en métodos estadísticos
Resumen IIP página 3
Ejemplos diap 12-1
sábado, 8 de octubre de 2022 17:26
Performance improvement
---------------------------------------------------------------------------------------------------------------------
Ventajas y desventajas
Resumen IIP página 4
Ejemplos diap 12-2
sábado, 8 de octubre de 2022 17:26
Riesgo de datos
Resumen IIP página 5
Paralelización del procesamiento a nivel de instrucción 2
sábado, 8 de octubre de 2022 17:26
Procesadores escalares: Son procesadores canalizados que están diseñados para obtener y emitir como
máximo una instrucción en cada ciclo de máquina.
Procesadores super escalares: Son aquellas que están diseñadas para buscar y emitir múltiples
instrucciones en cada ciclo de máquina.
El rendimiento aumenta si IPC aumenta.
IPC vs CPI
• El CPI es de gran importancia con los procesadores escalares con pipeline, el objetivo final de
rendimiento era reducir el CPI promedio = 1.
• El IPC es más importante en los procesadores super escalares, el nuevo objetivo de rendimiento es
lograr un IPC promedio > 1.
Ley de Amdahl
La aceleración general debida al procesamiento paralelo está fuertemente dictada por la parte
secuencial del programa a medida que aumenta el paralelismo de la máquina.
Donde:
f= mejora en paralelización
N= Numero de cores o mejoramiento general
(notar gráfico de abajo)
Pipeline ideal Pipelined real (stalls)
Problema del pipeline real
• Rendimiento disminuye debido a los stalls
• A mayor grado de pipelining (N), se penalizan más los stall en tiempo debido al proceso de llenado
• Los ciclos de stall constituyen el cuello de botella.
Ley de amdahl con super escalar
Resumen IIP página 6
Paralelización del procesamiento a nivel de instrucción 2
sábado, 8 de octubre de 2022 17:26
Superpipelined
Pipeline
Los procesadores superpipilined explotan el hecho de que la mayoría de implementaciones de
etapas tardan menos de medio ciclo de reloj en ejecutarse.
Procesador super escalar
-Unidades funcionales replicadas.
-Profundidad: Número de pipelines independientes para cada instrucción.
IPC > 1. Depende de la profundidad. Mayor desempeño.
Más complejo. Mayor consumo de potencia.
Segmentación paralela
-Paralelismo temporal
-Paralelismo espacial
-Segmentación paralela
Segmentación diversificada
Un pipeline diversificado utiliza hardware idéntico para algunas etapas, mientras que se diversifica
en otras, permitiendo la ejecución paralela de una mayor cantidad de instrucciones diferentes.
Resumen IIP página 7
Paralelización del procesamiento a nivel de instrucción 2
sábado, 8 de octubre de 2022 17:26
Segmentación dinámica
-En pipelines escalares se agregaba un registro (buffer) entre etapas, para mantener aislada una de la otra y
conservar señales de control y datos entre las mismas.
-En pipelines paralelos se deben tener buffers multientrada.
-Buffers multientrada tienen la capacidad de hacer reordenamiento de las instrucciones, permitiendo la
ejecución fuera de orden (OoOE).
Calendarización de instrucciones
Hardware especializado se encarga de determinar el orden, así como de evitar y solucionar riesgos.
Políticas de calendarización
-búsqueda in order, terminación in order
-búsqueda in order, terminación ouf-of-order
-búsqueda out-of-order, terminación ouf-of-order
Resumen IIP página 8
Ejemplo dip 13-1
sábado, 8 de octubre de 2022 17:26
Superpipelined
Resumen IIP página 9
Algoritmos de calendarización dinámica
sábado, 8 de octubre de 2022 17:26
Arquitecturas tipo pipeline:
Paralelismo a nivel de instrucciones (ILP)
Busca explotar el potencial de que instrucciones no relacionadas puedan traslaparse.
Traslape posible si:
-No hay riesgo estructural.
-No hay riego RAW, WAR y WAW.
-No hay riesgo de control.
Dependencias: Si dos instrucciones son dependientes, no pueden ser ejecutadas en paralelo: deben ser
ejecutadas en orden.
Tipos de dependencias:
-Dependencia de datos
-Dependencia de nombre
-Dependencia de control
Dependencia de nombre: Ocurre cuando dos instrucciones utilizan el mismo registro o posición
de memoria (llamado nombre), pero no hay flujo de datos entre las instrucciones asociadas con el mismo
nombre.
Tipos de dependencia de nombre:
-Antidependencia (WAR): j escribe en un registro o posición de memoria leída por la instrucción i. El orden de las
instrucciones debe preservarse para asegurar que i lee el valor correcto. Solución: cambiar el nombre de registro
destino.
-Dependencia de salida (WAW): i e j escriben el mismo registro o posición de memoria. El orden de las
instrucciones debe preservarse para asegurar que el valor final corresponde a j. Solución: Utilizar un registro
diferente resuelve el problema.
Solución de la dependencia de nombre
Renombramiento de registros: -Estáticamente (compilador) -Dinámicamente (Hardware)
Dependencia de datos vs los riegos de datos
Las dependencias son parte del programa, mientras que los riesgos son parte del pipeline.
Dependencia de Control
Propiedades:
-Ejecución de las instrucciones en el orden del programa para asegurar que una instrucción que ocurre antes de
un salto es ejecutada antes del salto.
-Detección de riesgos de control para asegurar que una instrucción no es ejecutada hasta que la dirección del
salto es conocida.
Resumen IIP página 10
Algoritmos de calendarización dinámica
sábado, 8 de octubre de 2022 17:26
Propiedades de ejecución correcta
-Flujo de datos: el flujo real de datos entre las instrucciones que produce y utiliza los resultados correctos.
-Comportamiento de excepciones: preservar el comportamiento de excepciones significa que cualquier cambio
en el orden de la ejecución de instrucciones no debe modificar la forma en que las excepciones son realizadas
en el programa.
Estrategias de ILP
Calendarización dinámica: el hardware es el encargado de explotar el paralelismo.
Calendarización estática: depende del software para identificar potencial paralelismo.
Calendarización estatica
Los compiladores utilizan algoritmos sofisticados para calendarizar el código y explotar el ILP.
Las dependencias son soluciones por el compilador por medio de reordenamiento del código.
Calendarización dinámica
El hardware reordena la ejecución de instrucciones para reducir pipeline stalls mientras se mantiene el flujo de
datos y el comportamiento de excepciones.
Ventajas
Permite manejar algunos casos de dependencias que no son conocidas en tiempo de compilación.
Simplifica la complejidad del compilador,
Permite que el código compilado sea ejecutado eficientemente en un pipeline diferente
Desventajas
Aumento de la complejidad de hardware.
Consumo de potencia.
Puede generar excepciones imprecisas.
Problema: dependencias de datos que no pueden ser resueltas con anticipo de datos causas hardware stalls en
el pipeline.
Solución: permitir que instrucciones posteriores al stall continúen su ejecución. Habilita ejecución fuera de
orden.
Algoritmo de marcador (Scoreboard)
Características:
-Reemplaza las etapas ID, EX, WB con 4 etapas.
-La ejecución fuera de orden divide la etapa de ID:
Issue: decodificación de instrucciones, búsqueda de riesgos estructurales.
Lectura de operandos: esperar hasta que no haya riesgos de datos, después leer los operandos.
-Las instrucciones son ejecutadas cuando no dependen de instrucciones previas y no hay riesgos.
-El algoritmo de marcador permite que las instrucciones se ejecuten cuando se mantengan 1 y 2.
- Issue en orden pero lectura de operandos fuera de orden. Ejecución y finalización de la instrucción fuera de
orden.
Resumen IIP página 11
Algoritmos de calendarización dinámica
sábado, 8 de octubre de 2022 17:26
Finalización de las instrucciones fuera de orden: riesgos WAR y WAW pueden ocurrir.
Soluciones para WAR:
-Detener el WB hasta que los registros hayan sido leídos.
-Leer registros solamente durante la etapa de lectura de operandos.
Soluciones para WAW:
-Detectar el riesgo y detener el lanzamiento de una nueva instrucción hasta que la otra instrucción sea
completada.
-No hay renombramiento de registros.
-Debe tener múltiples instrucciones en la etapa de ejecución.
-Mantiene información de dependencias y el estado de las operaciones.
Problema con finalización fuera de orden: Debe preservar el comportamiento de las excepciones como si
fuera en orden.
Solución: asegurar que ninguna instrucción puede generar una excepción hasta que el procesador sepa que
la instrucción que generó la excepción va a ser ejecutada.
Etapas de control del algoritmo
Issue: Decodificar la instrucción y revisar riesgos estructurales y riesgos WAW. Las instrucciones son lanzadas
en el orden del programa.
Lectura de operandos: Esperar a que no existan riesgos de datos, después leer los operandos. Un operando
fuente está disponible si.
Ejecución: La unidad funcional comienza la ejecución cuando los operandos están
disponibles. Cuando el resultado está disponible, notifica al marcador que ha finalizado
su ejecución.
Escribir el resultado: Revisar si existen riesgos WAR y finalizar la ejecución. Una vez que el marcador sabe
que la unidad funcional completó su ejecución, revisa si existen riesgos WAR. Si no hay riesgos, escribe el
resultado. Si hay riesgos WAR, detiene la finalización de la instrucción.
Nota: Latencia - Tiempo efectivo para completar una operación.
Estructura
-Estado de la instrucción.
-Estado de la unidad funcional.
-Estado de registro de resultado.
Nota: Ejemplo de algoritmo de marcador (Diap 42-69)
Resumen de ejemplo:
Idea básica del algoritmo de marcador: permitir instrucciones detrás de
un stall ser ejecutadas por medio de:
*Dividir la etapa de decodificación en lanzamiento y lectura de
operandos.
*Finalización y ejecución fuera de orden.
Resumen IIP página 12
Ejemplo diap-14-1
sábado, 8 de octubre de 2022 17:26
Dependencia de nombre:
Antidependencia (WAR)
Dependencia de salida (WAW)
Calendarización dinamica
Resumen IIP página 13
Ejemplo diap-14-2
sábado, 8 de octubre de 2022 17:26
Calendarización dinamica
Resumen IIP página 14
Out-of-Order execution
sábado, 8 de octubre de 2022 17:26
Arquitectura pipeline en orden con buffer de reordenamiento
Decode (D) -> Execute (E) -> completion (C) -> Retirement/commit (W)
Las dependencias de datos se ven como:
no son verdaderas
dependencies
(Un mismo registro se refiere a
valores que no tienen nada que ver
entre sí)
Solución
-El ID del registro cambia de nombre a la entrada del búfer de reorden que contendrá el valor del registro.
-Esto elimina las dependencias anti y de salida.
Ejecución fuera de orden
Despacho: Acto de enviar una instrucción a una unidad funcional.
Problema: una verdadera dependencia de datos detiene el envío de instrucciones más jóvenes a unidades
funcionales (de ejecución).
Prevención de paradas de envió: problema -ejecución en orden. Solución: ejecución fuera de orden.
Formas de evitar los stalls de envió:
1. Programación/reordenación de instrucciones en tiempo de compilación
2. Predicción de valor
3. Subprocesos múltiples de grano fino
Calendarización dinámica (OoO)
Idea: Mueva las instrucciones dependientes fuera del camino de las independientes (las independientes
pueden ejecutarse).
Beneficio: Tolerancia de latencia: permite que se ejecuten y completen instrucciones independientes en
presencia de una operación de latencia prolongada.
Resumen IIP página 15
Out-of-Order execution
sábado, 8 de octubre de 2022 17:26
Habilitación de la ejecución fuera de orden:
1. Renombrar registro: asociar una “etiqueta” a cada valor de dato.
2. Necesidad de almacenar en búfer las instrucciones hasta que estén listas para ejecutarse.
3. Las instrucciones deben realizar un seguimiento de la preparación de los valores de origen.
4. Cuando todos los valores fuente de una instrucción están listos, es necesario enviar la instrucción a su
unidad funcional (FU).
Algoritmo tomasulu
Un algoritmo eficiente para explotar múltiples unidades aritméticas.
Los Humps en el pipeline moderno:
1-Reservation station.
2-Reordering.
Pasos
• Si la estación de reserva está disponible antes de cambiar el nombre
-Instrucción + operandos renombrados (valor de origen/etiqueta) insertados en la estación de
reserva
-Solo cambie el nombre si la estación de reserva está disponible
• De lo contrario, Stall
• Mientras está en la estación de reserva, cada instrucción:
-Observa el bus de datos común (CDB) para la etiqueta de sus fuentes
-Cuando vea la etiqueta, tome el valor de la fuente y guárdelo en la estación de reserva
-Cuando ambos operandos están disponibles, la instrucción está lista para ser enviada
• Envía instrucciones a la unidad funcional cuando la instrucción está lista
• Después de que termine la instrucción en la Unidad Funcional
-Arbitraje para CDB
-Ponga el valor etiquetado en CDB (difusión de etiquetas)
-El archivo de registro está conectado al CDB
+El registro contiene una etiqueta que indica el último escritor del registro
+Si la etiqueta en el archivo de registro coincide con la etiqueta de transmisión, escriba el
valor de transmisión en el registro (y establezca un bit válido)
-Reclamar etiqueta de cambio de nombre
+¡no hay una copia válida de la etiqueta en el sistema!
Resumen IIP página 16
sábado, 8 de octubre de 2022 17:26
Resumen IIP página 17
