Pipelinining

La Segmentación (pipelining) es un método por el cual se consigue aumentar el rendimiento de algunos sistemas electrónicos digitales. Es aplicado, sobre todo, en microprocesadores. El nombre viene de que para impulsar el gas en un oleoducto a la máxima velocidad es necesario dividir el oleoducto en tramos y colocar una bomba que de un nuevo impulso al gas. El símilar con la programación existe en que los cálculos deben ser registrados o sincronizados con el reloj cada cierto tiempo para que la ruta crítica (tramo con más carga o retardo computacional entre dos registros de reloj) se reduzca.


La ruta crítica es en realidad la frecuencia máxima de trabajo alcanzada por el conjunto. A mayor ruta crítica (tiempo o retraso entre registros) menor es la frecuencia máxima de trabajo y a menor ruta crítica mayor frecuencia de trabajo. La una es la inversa de la otra. Repartir o segmentar equitativamente el cálculo hace que esa frecuencia sea la óptima a costa de más área para el almacenamiento o registro de los datos intervinientes y de un retraso o latencia (en ciclos de reloj/tiempo) en la salida del resultado equivalente al número de segmentaciones o registros realizados. La ventaja primordial de este sistema es que, tal y como se muestra en la imagen, una vez el pipe está lleno, es decir, después de una latencia de cuatro en la imagen, los resultados de cada comando vienen uno tras otro cada flanco de reloj y sin latencia extra por estar encadenados dentro del mismo pipe. Todo esto habiendo maximizado la frecuencia máxima de trabajo.

Detalle de la segmentación de instrucciones.

El alto rendimiento y la velocidad elevada de los modernos procesadores, se debe, principalmente a la conjunción de tres técnicas:
Arquitectura Harvard (arquitectura que propicia el paralelismo).
Procesador tipo RISC.
Segmentación.
Consiste en descomponer la ejecución de cada instrucción en varias etapas para poder empezar a procesar una instrucción diferente en cada una de ellas y trabajar con varias a la vez.



En el caso del procesador DLX podemos encontrar las siguientes etapas en una instrucción:

IF: búsqueda
ID: decodificación
EX: ejecución de unidad aritmético lógica
MEM: memoria
WB: escritura

Cada una de estas etapas de la instrucción usa en exclusiva un hardware determinado del procesador, de tal forma que la ejecución de cada una de las etapas en principio no interfiere en la ejecución del resto.
En el caso de que el procesador no pudiese ejecutar las instrucciones en etapas segmentadas, la ejecución de la siguiente instrucción sólo se podría llevar a cabo tras la finalización de la primera. En cambio en un procesador segmentado, salvo excepciones de dependencias de datos o uso de unidades funcionales, la siguiente instrucción podría iniciar su ejecución tras acabar la primera etapa de la instrucción actual.
Otro ejemplo de lo anterior, en el caso del PIC, consiste en que el procesador realice al mismo tiempo la ejecución de una instrucción y la búsqueda del código de la siguiente.

Superpipeline

La reducción del período de reloj τ sin reducir el tiempo total de cada etapa, y permitiendo que se emita una instrucción por ciclo, se denomina. Un procesador superpipeline posee sus etapas supersegmentadas, cada una de las cuales duran varios ciclos


Superescalar

Es el término utilizado para designar un tipo de microarquitectura de procesador capaz de ejecutar más de una instrucción por ciclo de reloj. El término se emplea por oposición a la microarquitectura escalar que sólo es capaz de ejecutar una instrucción por ciclo de reloj. En la clasificación de Flynn, un procesador superescalar es un procesador de tipo MIMD (multiple instruction multiple data). La microarquitectura superescalar utiliza el paralelismo de instrucciones además del paralelismo de flujo, éste último gracias a la estructura en pipeline. La estructura típica de un procesador superescalar consta de un pipeline con las siguientes etapas:

lectura (fetch)
decodificación (decode)
lanzamiento (dispatch)
ejecución (execute)
escritura (writeback)
finalización (retirement)

En un procesador superescalar, el procesador maneja más de una instrucción en cada etapa. El número máximo de instrucciones en una etapa concreta del pipeline se denomina grado, así un procesador superescalar de grado 4 en lectura (fetch) es capaz de leer como máximo cuatro instrucciones por ciclo. El grado de la etapa de ejecución depende del número y del tipo de las unidades funcionales.

Un procesador superescalar suele tener unidades funcionales independientes de los tipos siguientes :

Unidad aritmético lógica (ALU)
Unidad de lectura / escritura en memoria (Load/Store Unit)
Unidad de coma flotante (Floating Point Unit)
Unidad de salto (Branch unit)

Un procesador superescalar es capaz de ejecutar más de una instrucción simultáneamente únicamente si las instrucciones no presentan algún tipo de dependencia (hazard). Los tipos de dependencia entre instrucciones son :

Dependencia estructural, esta ocurre cuando dos instrucciones requieren el mismo tipo unidad funcional y su número no es suficiente.

Dependencia de datos, esta ocurre cuando una instrucción necesita del resultado de otra instrucción para ejecutarse, por ejemplo R1<=R2+R3 y R4<=R1+5.

Dependencia de escritura o falsa dependencia , esta ocurre cuando dos instrucciones necesitan escribir en la misma memoria, por ejemplo R1<=R2+R3 y R1<=R1+5.

La detección y resolución de las dependencias entre instrucciones puede ser estática (durante la compilación) o dinámica, es decir, a medida que se ejecuta un programa, generalmente durante la etapas de codificación y lanzamiento de las instrucciones.

La detección y resolución dinámica de las dependencias entre instrucciones suele realizarse mediante alguna variante del algoritmo de Tomasulo que permite la ejecución de instrucciones en un orden distinto al del programa también llamada ejecución en desorden .

La eficacia de un procesador superescalar viene limitada por un lado por la dificultad en suministrar al procesador suficientes instrucciones que puedan ser ejecutadas en paralelo y por otro lado por las prestaciones de la jerarquía de memorias.

Si las instrucciones de salto son un problema para los procesadores con pipeline en general, en el caso de los procesadores superescalares, el problema se multiplica ya que un parón en el pipeline tiene consecuencias en un número mayor de instrucciones.

Por esta razón, los fabricantes de procesadores recurren a técnicas de ejecución especulativa y diseñan algoritmos de predicción de saltos cada vez más sofisticados así como sistemas de almacenamiento de instrucciones por trazas (trace caches).

Las arquitecturas superescalares adolecen de una estructura compleja y de un mal aprovechamiento de sus recursos debido en parte a la dificultad en encontrar suficientes instrucciones paralelizables. Una forma de obtener un mayor número de instrucciones paralelizables es aumentar la ventana de instrucciones, es decir el conjunto de instrucciones que la unidad de lanzamiento considera como candidatas a ser lanzadas en un momento dado.

Desafortunadamente la complejidad del procesador superescalar aumenta desproporcionadamente con respecto al tamaño de dicha ventana lo que se traduce por un ralentizamiento general del circuito. Otra forma de obtener más instrucciones paralelizables es manipulando instrucciones de más de un programa a la vez, lo que se conoce bajo el nombre de multitarea simultánea o multithreading simultáneo.

Mientras las primeras CPUs superescalares disponían de dos ALUs y una sola FPU, un procesador moderno como el PowerPC 970 incluye cuatro ALUs y dos FPUs, además de dos unidades SIMD. Si el despachador no es eficiente haciendo trabajar lo máximo posible a estas unidades, el rendimiento global del procesador se verá mermado.

La CDC 6600 de Seymour Cray, construida en 1965, es la primera arquitectura superescalar, siendo llevado el concepto a las microcomputadoras en las CPUs RISC. Esta posibilidad venía dada por la simpleza de los núcleos RISC, permitiendo meter más unidades de ejecución en un mismo chip.


Esta fue una de las razones de la rapidez de los sistemas RISC frente a los más antiguos CISC durante las décadas de los 80 y los 90, pero a medida que los procesos de fabricación mejoraron y se pudieron meter más y más transistores en el mismo chip, hasta diseños complejos como el IA-32 pudieron ser superescalares.

La inmensa mayoría de las CPUs desarrolladas desde 1998 son superescalares.

Llegados a un punto en que la mejora sustancial de la unidad de control y despachamiento parece imposible, ya no parece que los diseños superescalares puedan dar más de sí. Una de las posibles soluciones es trasladar la lógica de despachamiento desde el chip hasta el compilador, que puede invertir mucho más tiempo en tomar las mejores decisiones posibles, ya que no tiene que operar en tiempo real como tenía que hacer el hardware de despachamiento.

Este es el principio básico de los procesadores VLIW (Very Long Instruction Word), donde el paralelismo es explicitado por el formato de instrucción, también conocidos como superescalares estáticos

Riesgos de salto o de control

Los riesgos de salto o de control ocurren cuando el procesador se ve obligado a saltar a una instrucción que no tiene por qué ser necesariamente la inmediatamente siguiente en el código. En ese caso, el procesador no puede saber por adelantado si debería ejecutar la siguiente instrucción u otra situada más lejos en el código.

Esto puede resultar en acciones no deseadas por parte de la CPU.

Eliminación de riesgos de salto

Ejecución especulativa

En ciencias de la computación, la ejecución especulativa es la ejecución de código por parte del procesador que no tiene por qué ser necesaria a priori. En la programación funcional, suele usarse el término "evaluación especulativa".


La ejecución especulativa no es más que una optimización. Obviamente, sólo es útil cuando la ejecución previa requiere menos tiempo y espacio que el que requeriría la ejecución posterior, siendo este ahorro lo suficientemente importante como para compensar el esfuerzo gastado en caso de que el resultado de la operación nunca llegue a usarse.

Los procesadores modernos que hacen uso de un pipeline usan la ejecución especulativa para, entre otras cosas, reducir el coste computacional de las instrucciones de salto condicional. Cuando el procesador se encuentra con una instrucción de salto condicional, el procesador intenta adivinar donde es más probable que se salte (a esto se le llama predicción de saltos) e inmediatamente comienza a ejecutar el código que empieza en ese área. Si a posteriori se demuestra que la predicción fue errónea, todo lo ejecutado después del salto se descarta. Esta ejecución prematura sale realmente rentable en términos de uso de recursos puesto que si no el pipeline se pararía hasta conocer cual sería la próxima instrucción.

Hay un tipo de ejecución 'vaga' que no realiza este tipo de predicciones. La incorporación de la ejecución especulativa en lenguajes de programación es un tema de investigación actualmente, probándose en diversas implementaciones de Haskell. Las versiones recientes del GHC permiten un tipo de ejecución especulativa llamada "ejecución optimista".

Hueco de retardo

En arquitectura de computadores, un hueco de retardo contiene una instrucción que es ejecutada sin tener en cuenta los efectos de la instrucción precedente. La forma más común consiste en una instrucción arbitraria sencilla colocada inmediatamente después de una instrucción de salto en las arquitecturas RISC o DSP; esta instrucción se ejecutará incluso si el salto precedente es efectivo. De este modo las instrucciones parecen ejecutarse de un modo ilógico o incorrecto. Es típico de los lenguajes ensambladores reordenar automáticamente las instrucciones, cubriendo de este modo las carencias de algunos compiladores.

Huecos de retardo de salto

Los huecos de retardo en que se ven involucradas las instrucciones de salto son conocidos como huecos de retardo de salto. Se encuentran principalmente en las arquitecturas DSP y RISC más antiguas. Las arquitecturas MIPS, PA-RISC, ETRAX CRIS, SuperH y SPARC son arquitecturas RISC que tienen un único huecos de retardo de salto; las arquitecturas PowerPC, ARM y la recientemente diseñada DEC Alpha carecen de él. Las arquitecturas de los DSP pueden ser de hueco único o doble (ejecutan dos instrucciones entre el inicio de la instrucción de salto y su resolución).

El objetivo de la segmentación RISC clásica es mantener los registros de segmentación ocupados en todo momento. El hueco de retardo de salto es un efecto colateral de las arquitecturas segmentadas debido a los riesgos. Un diseño sencillo insertaría burbujas en la segmentación después del salto hasta que la dirección de destino sea computada y cargada en el contador de programa. Cada ciclo en que se inserta una burbuja es considerado un hueco de retardo de salto. Un diseño más sofisticado ejecutaría las instrucciones del programa no dependientes del resultado de la instrucción de salto. Esta optimización puede ser realizada mediante software en tiempo de compilación moviendo instrucciones desde memoria al hueco de retardo de salto, siempre y cuando el hardware soporte esta operación. Otro efecto colateral es el especial cuidado que hay que tener con los puntos de ruptura y las ejecuciones línea a línea durante el proceso de depuración de programas.


El número ideal de huecos de retardo de salto en una determinada implementación segmentada viene dado por el número de etapas de segmentación, la presencia de unidades anticipadoras, la etapa en que se computen las condiciones de salto, si se utiliza o no un buffer de destino de salto, etc. Los requisitos de compatibilidad de software marcan que una arquitectura no puede cambiar el número de huecos de retardo de una generación a la siguiente. Esto requiere inevitablemente que las nuevas implementaciones del hardware contengan componentes a mayores para asegurar que el comportamiento de la arquitectura se mantiene a pesar de no ser ya relevante.

Hueco de retardo de carga

Un hueco de retardo de carga es una instrucción que se ejecuta inmediatamente después de una carga (copia de memoria a registro) pero que no ve el resultado de dicha carga. Estos huecos de retardo son poco comunes porque los retardos por cargas son altamente impredecibles en el hardware actual. Una carga puede ser satisfecha por la RAM por la caché, y puede ser ralentizada por la distribución de recursos. Los retardos por cargas eran propios de los diseños más primitivos de procesadores RISC. El repertorio de instrucciones MIPS1 (utilizado en los procesadores R3000 y anteriores) sufre este problema.

El siguiente código de ejemplo está escrito en ensamblador MIPS1, mostrando tanto un hueco de retardo de carga como de salto.

lw v0,4(v1) # carga de la palabra almacenada en la dirección v1+4 en el registro v0
nop # hueco de retardo de carga
jr v0 # salto incondicional a la dirección especificada por el registro v0
nop # hueco de retardo de salto

Un salto es una interrupción del flujo normal de las instrucciones, haciendo que el procesador continúe en otro punto del programa ("salta" a otra parte del programa). Un salto condicional es una instrucción (más bien una familia de instrucciones) que realiza el salto si se cumple una condición determinada con anterioridad. El problema es que el procesador no sabe si se realizará el salto o no hasta que se evalúa la condición y si esto ocurre en la mitad del pipeline, es posible que tenga que borrar el pipeline y comenzar de nuevo en el nuevo punto de ejecución, perdiendo tiempo y trabajo.

Para evitar interrumpir el pipeline, el procesador trata de adivinar si se tomará el salto o no, y seguir leyendo/decodificando/ejecutando las instrucciones de acuerdo a su escogencia. Claro que no toma la decisión al azar, sino que utiliza circuitos adicionales que guardan la historia de estos saltos y un algoritmo (no revelado) que lo ayuda a elegir. Además, los programadores que construyen los compiladores tienen que seguir unas reglas que Intel ha especificado para ayudar al procesador a realizar una decisión inteligente. trata de adivinar si se tomará el salto o no, y seguir leyendo/decodificando/ejecutando las instrucciones de acuerdo a su escogencia. Claro que no toma la decisión al azar, sino que utiliza circuitos adicionales que guardan la historia de estos saltos y un algoritmo (no revelado) que lo ayuda a elegir. Además, los programadores que construyen los compiladores tienen que seguir unas reglas que Intel ha especificado para ayudar al procesador a realizar una decisión inteligente.

Videos de pipeline.