S14 - myTeachingURJC/Arq-computadores-01 GitHub Wiki

Sesión de Teoría 14: Segmentación y rendimiento

  • Tiempo: 2h
  • Dispositivas sobre segmentación: PDF
  • Objetivos de la sesión:
    • Estudiar el comportamiento de las tareas subdivididas en subtareas
    • Comprender porqué la segmentación mejora el rendimiento de estas tareas
    • Aplicarlo a los procesadores

Contenido

Introducción

Ya entendemos el funcionamiento del procesador NanoRiscv Monociclo. Y sabemos calcular su frecuencia de funcionamiento: Está determinada por la instrucción más lenta (load). Esta instrucción es la que tiene el camino crítico: el camino con mayor retardo. Garantizando que los datos son capaces de recorrer este camino y ser capturados de forma estable, el procesador funcionará correctamente a esa frecuencia

La pregunta ahora es ¿cómo podemos aumentar el rendimiento del procesador? ¿Cómo podemos hacer para que el procesador ejecute más instrucciones en el mismo tiempo?

Ejemplo: Fabricación de automóviles

El problema del aumento del rendimiento no es exclusivo de los procesadores, sino que se remonta a principios del siglo XX (1900-1910) cuando aparecieron los primeros fabricantes de automóviles. El más importante, y el que puso en práctica la producción en masa fue Henry Ford, con la fabricación del modelo Ford T

El problema a resolver es: ¿Cómo producir más cantidad de coches al día? Para entender mejor este problema y comprender su solución, vamos a utilizar un modelo simplificado de fabricación

Modelo simplificado de fabricación

Supondremos que fabricar el coche y tenerlo listo para vender hay que realizar cuatro fases. Cada fase requiere de unas herramientas y una maquinaria especializada. También, por simplificidad, supondremos que las 4 fases tardan más o menos lo mismo: 2 horas

Supondremos también que siempre tendremos suficiente material para fabricar los coches. En la primera fase se monta el chasis del coche. Es la estructura básica de soporte donde se alojarán el resto de componentes. A continuación se coloca el motor y todos los componentes mecánicos necesarios. Luego se termina la carrocería y se colocan el resto de elementos. Por último, hay que comprobar que el vehículo funciona correctamente, pasando una revisión técnica

La fábrica es una nave donde está situada la línea de montaje. En cada zona de la línea están las herramientas y maquinaria necesaria para realizar cada fase

Los operarios se han formado para saber cómo montar el coche desde cero. Se van desplazando de una zona a otra de la línea hasta completar la fabricación del coche. Una vez han terminado con uno, empiezan con la fabricación del siguiente

Modelo secuencial

El modelo anterior de fabricación es secuencial. Se fabrica un coche. Cuando se termina se empieza con el siguiente. Y luego con el siguiente. Supondremos que se tarda en fabricarlo 8h, empleándose 2h aproximadamente en cada fase

Lo representamos gráficamente mediante un diagrama en el que ponemos el tiempo en el eje horizontal y la cantidad de coches fabricados en el vertical. En él colocamos las fases de la fabricación (2 de horas de tiempo cada una)

La productividad de la fábrica es de 1 coche cada 8h, o lo que es lo mismo, 3 coches al día

¿Cómo podríamos mejorar esa productividad?

Paralelismo

Como se anunció en la sesión 2, el rendimiento se incrementa mediante paralelismo

Si replicamos la línea de producción de la fábrica, de manera ahora tengamos dos líneas, el resultado es que se duplica la productividad. El diagrama es el siguiente:

Ahora la fábrica produce 6 coches al día. El precio a pagar es que tenemos hemos replicado totalmente la línea, así como todas las herramientas y la maquinaria necesaria para la fabricación. La productividad ha aumentado, pero... ¿E es la manera más eficiente?

Problemas del modelo secuencial

Si analizamos el modelo secuencial, vemos que en cada momento sólo hay una fase activa. Esto significa que sólo se están usando las herramientas y maquinaría de cada fase una cuarta parte del tiempo. Los 3/4 restantes no se están usando. Hay mucho tiempo desperdiciado, en el que no hay producción. Las máquinas están infrautilizadas

La solución es utilizar estas máquinas mientras no se están usando. ¿Cómo lo hacemos?

Frabricación en cadena

La fabricación en cadena se aplicó por primera vez en el modelo T de Ford en 1908. El proceso de fabricación hay que dividirlo en N etapas que tarden tiempos similares. En cada estapa se sitúan unos operaciones, que se especialian en realizar exclusivamente esa etapa

Así, como en nuestro ejemplo de fabricación hay 4 Fases, necesitamos 4 grupos de operarios, un grupo por fase, para completar el ensamblaje de esa fase. PERO NO necesitamos maquinaria ni herramientas adicionales. Se usan las que ya había antes

El funcionamiento de la línea es ahora así. Se comienza la fabricación del primer coche. Empiezan a trabajar los operarios de la etapa 1. El resto de operarios están a la espera. Para distinguir los diferentes coches utilizaremos colores. El coche 1 es el gris

Al cabo de 2 horas, el chásis del coche 1 está listo y pasa a la segunda etapa. En ese momento, los operarios de la primera etapa empiezan a construir el chásis del coche 2 (amarillo). Ahora hay dos etapas que funcionan en paralelo: la construcción del chásis del coche 2, y el ensamblaje del motor del coche 1

Tras otras 2 horas se comienza la construcción del coche 3 y los coches 1 y 2 pasan a las siguientes etapas. Ahora sólo los operarios de la etapa 4 están inactivos. El resto están trabajando

Al cabo de otras 2 horas, el coche 1 llega a su última etapa de construcción (la revisión) y el coche 4 entra en la línea de producción

En este momento TODOS los operarios de la cadena están trabajando: Las 4 etapas están funcionando en paralelo. ¡Estamos a todo rendimiento!. Decimos la línea de producción está llena (o que el pipeline está lleno). Inicialmente, a las 0 horas, la línea estaba vacía (pipeline vacío)

Tras la revisión del coche 1, que dura 2 horas, ya tenemos su fabricación finalizada y este coche sale de la línea de producción (sale del pipeline)

Transcurridas otras 2 horas, el coche 2 (amarillo) está también terminado, y sale de la línea. Así sucesivamente con el resto de coches

Análisis de la fabricación en cadena

Para entender el funcionamiento dibujamos el diagrama de tiempos correspondiente a un día completo (24 horas). Así veremos gráficamente, también, cuál es la producción de ese día

Si miramos horizontalmente vemos el estado de un coche concreto: En qué momento empieza a fabricarse, y cuándo se termina. Todos los coches tardan 8h en fabricarse. Igual que en el caso secuencial (no se ha mejorado el tiempo de fabricación de cada coche individual)

Si miramos verticalmente vemos el estado de la línea de producción. Así, en la línea marcada en el dibujo, vemos que en la primera etapa está el coche magenta (coche 5), en la segunda etapa el coche verde (coche 4), en la tercera el cyan (coche 3) y en la cuarta el amarillo (coche 2)

Vemos que el primer coche lo tenemos fabricado a las 8 horas. Desde que entra en la línea de producción hasta que sale fabricado pasan 8 horas. Esto lo denominamos el tiempo de latencia

PERO dos horas después de tener el coche 1, se termina de fabricar el coche 2. Otras dos horas después, aparece el coche 3. Es decir, que una vez que la línea está llena, ¡se fabrica un coche cada 2 horas!

Así, el primer día, la producción total es de 9 coches. Como la línea se ha arrancado ese día, debido a la latencia, el primer coche tarda más y luego el resto menos.... PERO si miramos la producción del día 2 y sucesivos, y suponiendo que la línea no se ha parado en ningún momento, vemos que la producción es de ¡¡¡12 coches al día!!! (1 cada 2 horas)

Resumen y comparación

En esta tabla se han recopilado todos los datos para comparalos mejor. Se ha añadido un modelo de 4 líneas de producción en paralelo

La conclusión final es que, al usar el modelo de fabricación en cadena (segmentación, pipelining), tenemos un rendimiento IGUAL al de 4 líneas en paralelo, SIN NECESIDAD de replicar la maquinaria ni las herramientas. Sólo necesitamos 4 grupos de operarios, para que las 4 etapas funcionen en paralelo

La fórmula general es:

Productividad fabricación en cadena = (Productividad modelo secuencial) x Número de etapas

Es válida a partir de que la línea se llene (una vez pasado el tiempo de latencia). Como en nuestro ejemplo hemos usado 4 etapas, la productividad se multiplica por 4: 3 * 4 = 12 coches/día

Aplicación a procesadores

Todas estas ideas que hemos visto en el campo de la fabricación las aplicaremos a los procesadores para lograr que mejoren su rendimiento, y que por tanto puedan ejecutar la mayor cantidad posible de instrucciones en el menor tiempo

Modelo simplificado de ejecución

Como ya vismos en las sesiones anteriores, la ejecución completa de una instrucción la dividimos en 5 fases. El tiempo de cada fase está determinado por los retardos de sus elementos

En cada fase hay un componente principal cuyo retardo es el que determina su tiempo

  • Fetch: Memoria de instrucciones
  • Decodificacion: Lectura del banco de registros
  • Ejecución: ALU
  • Memoria: Lectura de la memoria de datos
  • Write-back: Escritura en registros/memoria. PERO, en nuestro procesador moniciclo, como al escritura se hace al llegar el flanco de reloj, en realidad el tiempo de escritura se hace en paralelo con la lectura de la siguiente intrucción (y por eso no lo hemos tenido en cuenta). Sin embargo, en otros modelos sí que habrá que tenerlo en cuenta

Modelo secuencial: Procesador Monociclo

El modelo de fabricación secuencial es el equivalente al procesador Monociclo. La instrucción finaliza una vez que se han terminado todas las etapas. La frecuencia máxima viene determinado por la instrucción más lenta, que es load. Las instrucciones se ejecutan secuencialmente. Hasta que no termina una no empieza la otra

Si tenemos un programa de 3 instrucciones, lo representamos en nuestro diagrama de la siguiente forma:

El rendimiento de nuestro procesador (productividad) es de una instrucción por ciclo. Cada ciclo equivale al tiempo de la instrucción más lenta

Nos gustaría mejorar ese rendimiento

Paralelismo en procesadores

Para ejecutar más instrucciones ponemos los procesadores en paralelo. Cada uno de ellos es lo que llamamos un core. ¡OJO! Ejecutan instrucciones, pero de diferentes programas. No hacen que los programas se ejecuten más rápido, sino que se ejecutan instrucciones de diferentes programas en paralelo. La cantidad de instrucciones ejecutadas se multiplica por N, donde N es el número de cores

Así, si tenemos un computador con 2 cores, lo representamos gráficamente así:

Este computador ejecuta el doble de instrucciones. El precio a pagar es que se han REPLICADO todos sus recursos (memoria, ALU, registros....)

Problemas del procesador monociclo

Al igual que ocurría con el modelo de fabricación secuencial, el hardware se está utilizando muy poco. Cada elemento sólo está usado una quinta parte del tiempo. El resto del tiempo está sin usarse (sin hacer trabajo útil). Esto es muy poco eficiente

La solución es utilizar este hardware para realizar trabajo útil cuando NO se está usando en la instrucción actual

Segmentación

La segmentación es el equivalente a la producción en cadena, pero aplicado a los procesadores. Es exactamente la misma idea: ejecutar varias etapas en paralelo, cada una correspondiente a una instrucción diferente, pero SIN REPLICAR los recursos

Lo primero que se debe hacer es separar la ejecución total en etapas del mismo tiempo (o similar). Ahora, cada etapa se ejecutará en un ciclo de reloj. El tiempo del ciclo se elije como el mayor de todas las etapas

Supongamos que tenemos los siguientes retardos para estos componentes. Supondremos que el retardo para el resto de elementos es 0 (despreciable)

Componente Etapa Retardo (ps)
Memoria de código (lectura) Fetch 200
Banco registros (lectura) Decodificación 100
ALU Ejecución 180
Memoria de datos (lectura) Acceso memoria 200
Banco de registros (escritura) Write-back 80
Memoria da datos (escritura) Write-back 120

Las etapas tienen diferentes duraciones, porque usan componentes distintos. Hay que seleccionar el retardo de la peor etapa. En este ejemplo serán las etapas de Fetch y acceso a memoria, con un retardo de 200ps. Ese será el periodo de nuestro reloj. Por lo que la frecuencia máxima será de (1/200ps = 5GHz)

Todas las etapas de nuestra segmentación serán de 200ps de duración entonces. Al arrancar el procesador no tenemos ninguna instrucción en nuestra tubería (pipeline). Se comienza con la etapa 1: Obtener la instrucción 1 (color gris)

La memoria de código empieza a funcionar. PERO el resto de elementos hardware están sin usar: inactivos (y por tanto se está perdiendo tiempo. No está a su máximo rendimiento)

Al cabo de 200ps la etapa 1 se completa, y se comienza la decodificación de la instrucción 1. Pero ahora la etapa 1 comienza con la lectura de la instrucción 2 (amarilla). En vez de quedar inactiva hasta que se complete la ejecución de la instrucción 1, se comienza a trabajar en la instrucción 2. Esta es la clave de la segmentación

Transcurridos otros 200ps, la instrucción 1 (gris) pasa a la etapa de ejecución, la instrucción 2 (amarilla) a la de decodificación y se comienza con la lectura de la instrucción 3 (cyan). Tenemos 3 instrucciones ejecutándose en paralelo, aunque ninguna de ellas se ha completado todavía. Pero aún así, hay dos etapas que están inactivas. Nuestro sistema todavía NO ha alcanzado el máximo rendimiento

En el siguiente ciclo se comienza con la ejecución de la instrucción 4 (verde) y todas las anteriores pasan a sus siguientes etapas

En el siguiente ciclo, al cabo de 800ps desde el comienzo, todas las etapas están FUNCIONANDO. Por tanto, se ha alcanzado el máximo rendimiento. Hay un total de 5 instrucciones ejecutándose en paralelo, aunque todavía no se ha completado ninguna. En este estado, decimos que el pipeline está lleno

Transcurridos otros 200ps, lo que hace un total de 1ns (1000ps), se ha completado la ejecución de la instrucción 1, y se ha comenzado con la lectura de la instrucción 6 (magenta). La instrucción 1 ha tardado un total de 1ns en completarse

La magia de la segmentación comienza ahora. Al cabo de sólo 0.2ns (200ps) tras la finalización de la instrucción 1, ¡se ha completado la instrucción 2!. Y entra otra nueva en el pipeline (azul). A partir de ahora, dado que el pipeline está lleno y está a su máximo rendimiento, cada 200ps se ejecuta una instrucción nueva

Todo esto lo vemos resumido en el siguiente diagrama de tiempos

La instrucción 1 tarda 1ns en ejecutarse. La instrucción 2 tarda 1ns en ejecutarse. TODAS las instrucciones, vistas individualmente, han tardado 1ns en ejecutarse. PERO, como se están ejecutando etapas en paralelo, una vez que se ha terminado de ejecutar la primera instrucción, ¡se completa la ejecución de una nueva cada 0.2ns! Es como si tuviésemos un procesador secuencial (ejecutando una instrucción tras otra) pero a una frecuencia 5 veces superior!!!!

Resumen y comparación

En esta tabla se han recopilado todos los datos para entenderlos mejor. Como ejemplo usamos estos tiempos para los componentes del procesador:

Componente Etapa Retardo (ps)
Memoria de codigo (Lectura) Fetch 200
Banco registros (Lectura) Decodificación 100
ALU Ejecución 180
Memoria de datos (Lectura) Acceso memoria 200
Banco de registros (Escritura) Write-back 80
Memoria da datos (Escritura) Write-back 120

Para el procesador monociclo se utiliza como periodo el retardo de la instrucción más lenta, que normalmente es load (porque tiene una etapa adicional). En la implementación que hemos visto del monociclo, la escritura en memoria y en los registros se prepara en la etapa de Write-Back, pero se ejecuta en paralelo con el Fetch de la siguiente instrucción. Por eso no lo tenemos en cuenta al calcular la frecuencia máxima

Sin embargo, muchas veces se hace el cálculo sin tener en cuenta esta optimización, y el tiempo de escritura se añade en la fase de Write-Back

Cuando tenemos varios cores (procesadores en paralelo), el rendimiento se multiplica por el número de cores. PERO es a costa de replicar los recursos

Sin embargo, con el modelo segmentando tenemos un rendimiento que es casi 5 veces el del monociclo, pero sin replicar recursos.

El rendimiento del segmentando siempre será menor que el del monociclo x 5, ya que las etapas NO están balanceadas (no ocupan lo mismo)

Conclusiones

Mediante la segmentación logramos aumentar el rendimiento de los procesadores sin apenas coste adicional en hardware, ya que no hay que replicar recursos hardware. Un procesador segmentando en N etapas tiene un rendimiento equivalente a N procesadores en paralelo, pero usándose mucho menos hardware

Todos los procesadores modernos están segmentados

Lecturas del libro de referencia

Libro de referencia: "Computer Organization and Design. Hardware/Software interface. Risc-V"

  • Apartado 4.5: An Overview of Pipelining (Pag 262-266)

Ejercicios

Ejercicios para practicar y asimilar los conceptos más importantes

Ejercicio 1

Se tiene un procesador NanoRisc-V implentado con los siguientes componentes:

Componente Retardo (ps)
Memoria de codigo (Lectura) 220
Banco registros (Lectura) 100
ALU 80
Memoria de datos (Lectura) 400

Tanto la escritura en el Banco de registros como en la memoria de datos las consideraremos muy rápidas por los que sus retardos serán despreciables (= 0 ps)

Se pide:

  • a) Calcular la frecuencia máxima de funcionamiento si este procesador tiene una implementación Monociclo
  • b) Calcular la frecuencia máxima de funcionamiento si se utiliza una implementación segmentada
  • c) Se tiene un programa de prueba que ejecuta 1000 instrucciones y termina. Calcular el CPI del procesador segmentando
  • d) ¿Cual es la mejora del rendimiento al pasar de la implementación monociclo a la segmentada?

Autores

Licencia

Créditos

TODO

Enlaces