Paralelismo en las instrucciones

En inglés es Instruction-Level Parallelism (ILP), y se refiere a ejecutar más de una instrucción a la vez, en paralelo. Veremos aquí un breve resumen de lo cubierto en la bibliografía específica al final del documento.

Ya vimos que el pipelining permite ejecutar múltiples instrucciones en paralelo. El mejor CPI que podemos obtener es 1, un ciclo por instrucción. En definitiva, queremos mejorar el rendimiento del procesador, que medimos con el tiempo de respuesta, entonces ¿qué más se puede hacer para aumentar el ILP?

Si bien hay varias técnicas, nos centraremos en 2:

• Pipelines más profundos
  • más etapas en la segmentación → más instrucciones en el datapath a la vez
  • menos trabajo por etapa → ciclo de reloj más corto
  • disminuye el tiempo de respuesta, manteniendo el CPI ideal en 1
• Emisión múltiple (multiple issue)
  • replicando el hardware de la pipeline → múltiples pipelines
  • comienzo de múltiples instrucciones por ciclo
  • CPI (ideal) < 1 → se usa IPC
    • Por ejemplo: 4 GHz 4-way multiple-issue
      • 16 BIPS, mejor CPI = 0.25, mejor IPC = 4
    • pero dependencias terminan reduciendo estos valores en la práctica

Índice

• Emisión múltiple
• Especulación
• Emisión múltiple estática
  • Ejemplo: emisión dual estática
  • Ejemplo: emisión múltiple + loop unrolling
• Emisión múltiple dinámica
• Planificación dinámica del pipeline
• Eficiencia energética
• Bibliografía específica

Emisión múltiple

Con las técnicas que vimos hasta ahora, usando lo mejor que tengamos a disposición en una implementación segmentada, el CPI ideal que podemos esperar es 1. El valor 1 significa que por cada ciclo de reloj finalizamos una instrucción, que tampoco está mal ¿no? Sin embargo, si queremos reducir todavía más el CPI, necesitamos que por cada ciclo de reloj se termine más de una instrucción, y los procesadores que lo logran se llaman de emisión múltiple (multiple issue). Por ejemplo, si se emiten y completan dos instrucciones por ciclo de reloj, el CPI que se logra es 0.5. Supongamos que la cantidad máxima de instrucciones que se pueden emitir en un ciclo de reloj es m, entonces se dice que el procesador es de m-vías, o en inglés, m-issue wide.

Hay dos categorías de procesadores de emisión múltiple, que si bien difieren mucho en el hardware, y vamos a ver varias diferencias, parten de una idea fundamental en la división del trabajo. Esta división, entre el compilador y el hardware, está dada por cómo se toma la decisión para la emisión de las instrucciones y define las categorías de emisión múltiple. Si la decisión se hace en tiempo de compilación, es estática, y el procesador es de emisión múltiple estática (static multiple issue). Si la decisión se hace mientras se ejecuta el programa, es dinámica (la está tomando el hardware), y el procesador es de emisión múltiple dinámica (dynamic multiple issue).

• Emisión estática:
  • El compilador organiza las instrucciones para ser emitidas juntas
  • Se agrupan las instrucciones en espacios de emisión (issue slots)
  • Es el compilador quien detecta y evita los riesgos del pipeline
    • Todo lo que puede
• Emisión dinámica:
  • La CPU examina el flujo de instrucciones y decide qué instrucciones se emiten en cada ciclo
    • El compilador puede haber ayudado organizando las instrucciones de manera propicia
  • La CPU resuelve los riesgos usando técnicas más avanzadas en tiempo de ejecución

Especulación

Basado en la idea de la predicción, la especulación (speculation) les permite al procesador o al compilador “adivinar” sobre las propiedades de una instrucción. Esta especulación permite que comiencen instrucciones que en caso contrario tendrían que esperar los resultados, certeros, de instrucciones previas. La idea básica detrás del mecanismo es comenzar con la siguiente instrucción lo antes posible. Una vez que se realiza la especulación, es necesario considerar que la misma puede no ser correcta. Si fue correcta, se completa la operación. Si fue incorrecta, se debe deshacer o descartar lo procesado y hacer lo correcto. Por ejemplo, se puede especular sobre un resultado aritmético para emitir un salto por adelantado (especulativamente), y en caso de error ese salto se debe deshacer, e ir por el camino correcto. También se puede intentar adivinar el resultado de una carga de datos, y deshacer los cambios si la ubicación fue actualizada.

Tanto los procesadores de emisión múltiple dinámica como los de emisión múltiple estática pueden hacer uso de la especulación, y nuevamente la diferencia está en dónde se hace (y cómo se resuelve). Por ejemplo, el compilador puede usar la especulación para reordenar instrucciones, moviendo una instrucción antes de un salto, en una especulación estática. En tiempo de ejecución, el hardware puede hacer lo mismo usando técnicas, claramente, más complejas.

Sin embargo, ambas estrategias (estática y dinámica) pueden fallar y estos errores se salvan de distintos modos. Durante el proceso de compilación, se agregan instrucciones adicionales para corroborar los resultados y para generar una rutina que repare el error producido. En el hardware, el procesador usualmente almacena los resultados de la especulación hasta que no sean más especulativos, hasta que haya una resolución y se tenga información de los registros, o estados, que intervienen. Si la especulación fue correcta, se usan los resultados almacenados, si no lo fuera, descarta los resultados y ejecuta la secuencia de instrucciones correcta. Típicamente, los errores dinámicos requieren que se vacíe el pipeline, o al menos que se paren algunas etapas, reduciendo el desempeño del procesador. Si los errores son debidos a especulación estática, también se degrada el rendimiento, ya que se ejecutan instrucciones innecesarias y, posiblemente, instrucciones adicionales para deshacer las anteriores.

Además de fallar en una especulación y tener que deshacerla, la ejecución de una instrucción errónea puede generar excepciones. Por ejemplo, intentar acceder a una posición de memoria con un puntero nulo, siendo que la instrucción de carga se reordenó y se ejecuta antes de la comprobación. Para salvar estos problemas, en procesadores de emisión estática, se agrega soporte en la ISA para diferir excepciones. En un procesador de emisión múltiple dinámica, la excepción se puede almacenar en un buffer hasta que se complete la instrucción.

Emisión múltiple estática

Como se mencionó anteriormente, estos procesadores trasladan el trabajo al compilador. Es este último quien se encarga de empaquetar las instrucciones y analizar los riesgos, en función de los recursos disponibles en el pipeline. Se puede pensar que las instrucciones de estos procesadores, para un determinado ciclo de reloj, forman una única gran instrucción —no olvidemos que sigue siendo un procesador de emisión múltiple. Este conjunto de instrucciones empaquetadas se llama paquete de emisión (issue packet). Además, el conjunto de instrucciones que se pueden empaquetar juntas es limitado, por lo que se puede analizar pensando en una única instrucción con varios campos para las distintas operaciones que se enviarán al pipeline. Esta analogía dio lugar al nombre palabra de instrucción muy larga, o con el nombre que devino en siglas: Very Long Instruction Word (VLIW). También se los conoce como procesadores de instrucciones de paralelismo explícito (EPIC, Explicitly Parallel Instruction Computing), a pesar de no ser iguales.

Además, el compilador es responsable de los riesgos y debe eliminarlos (tal vez no completamente). Como se mencionó, el compilador reordena las instrucciones y las agrupa en paquetes. Este proceso se denomina planificación (scheduling). Los paquetes no pueden tener dependencias internas, es decir, se las debe haber eliminado por reordenamiento y/o la inserción de uno o más nop. Sin embargo, el procesador puede tener capacidad para detectar riesgos y retener paquetes, pero lo hace entre paquetes. Así como existe la posibilidad de que el procesador puede salvar riesgos entre paquetes, existen procesadores que no lo implementan y la responsabilidad recae completamente en el compilador. El compilador debe saber para quién compila.

Ejemplo: emisión dual estática

• Se generan paquetes de emisión con dos operaciones
  • Una instrucción para la ALU o para saltos (ALU/salto)
  • Una instrucción para operaciones de carga/almacenamiento (LD/SD)
• El paquete debe estar alineado a 64 bits
  • Primero la instrucción ALU/salto, luego la instrucción LD/SD
  • Si una instrucción no se usa, se reemplaza por nop

Este procesador puede mejorar el rendimiento en un factor de dos, pero hay que recordar que hay dependencias en la arquitectura que estamos viendo que no se pueden evitar y se deben retener instrucciones, tal es el caso de las dependencias Load/Store. La solución en esos casos era esperar un ciclo para poder hacer uso del reenvío de datos, y el reordenamiento podía aprovechar ese ciclo con otra instrucción, cosa que ahora es más compleja de hacer. Por otro lado, si antes no había problemas en usar Load o Store después de una instrucción que usa la ALU, ahora sí puede aparecer, porque se ejecuta en el mismo momento. Es el compilador quien debe trabajar en resolver esos problemas y aprovechar la capacidad del procesador.

En definitiva:

• Hay más instrucciones ejecutándose en paralelo (en este caso puede haber hasta 20)
• Riesgo por dependencia de datos en etapa EX
  • En el pipeline común, forwarding evitaba los stalls
  • En emisión dual no se pueden usar los resultados de la ALU en una instrucción LD/SD en el mismo paquete

  • Por ejemplo, la secuencia:

    x86-64	RISC-V
    addq %r9, %r8	add x8, x8, x9
    movq (%r8), %rax	ld a0, 0(x8)

    debe separarse en 2 paquetes, lo que genera un stall en la práctica.

• Riesgo Load/Use
  • Mismo problema: en el siguiente ciclo no está disponible el dato de la instrucción load, pero ahora son dos las instrucciones del siguiente ciclo (en vez de una)
• Se requiere de una mejor y más agresiva planificación (debe inspeccionar más datos y considerar más casos)

Ejemplo de planificación (x86-64)

1
2
3
4
5
6
loop: movq  0(%rdi), %rax  // %rax = elemento de un arreglo
      addq  %rdx, %rax     // le suma el valor guardado en %rdx
      movq  %rax, 0(%rdi)  // guardar resultado
      subq  $8, %rdi       // decrementar puntero
      cmpq  %rdi, %rsi     //
      jb    loop           // saltar si %rsi < %rdi

• IPC = 6/5 = 1.2 (el máximo sería IPC = 2)

Nótese la suma de 8 en la instrucción movq del ciclo 4, debido a que la instrucción subq se reordenó y se puso antes.

Ejemplo de planificación (RISC-V)

1
2
3
4
5
loop: ld    x31, 0(x20)    // x31 = elemento de un arreglo
      add   x31, x31, x21  // le suma el valor guardado en x21
      sd    x31, 0(x20)    // guardar resultado
      addi  x20, x20, -8   // decrementar puntero
      blt   x22, x20, loop // saltar si x22 < x20

• IPC = 5/a = 1.25 (el máximo sería IPC = 2)

Nótese la suma de 8 en la instrucción sd del ciclo 4, debido a que la instrucción addi se reordenó y se puso antes.

Ejemplo: emisión múltiple + loop unrolling

Ejemplo unrolling el ciclo anterior en 4-stride, usando emisión dual.

• Antidependencia o dependencia por nombres: se da cuando se fuerza el código a tener cierto orden debido a la reutilización de algún nombre, típicamente, un registro.

• Renombrado de registros (register renaming): es el uso de registros adicionales para evitar las antidependencias

Emisión múltiple dinámica

Los procesadores de emisión múltiple dinámica también son llamados (procesadores) superescalares. En cada ciclo de reloj es el procesador quien decide cuántas instrucciones se emiten, entre cero, una o más. Al hacerlo, puede evitar riesgos estructurales o por dependencias de datos. Para que esto funcione correctamente en un procesador superescalar simple, es necesaria una buena planificación estática de las instrucciones. Sin embargo, a diferencia de los procesadores VLIW, el hardware garantiza que el código se ejecuta correctamente (no siempre es el caso en los procesadores VLIW, donde se puede necesitar recompilar el código al cambiar de procesador dentro de una misma familia). Es por esto que estos procesadores no requieren de planificación estática, a pesar de poder beneficiarse en gran medida por esta técnica.

En muchos casos se extiende la toma de decisiones a lo que se llama planificación dinámica del pipeline (dynamic pipeline scheduling). Usando esta técnica no sólo se decide cuántas instrucciones emitir, sino cuáles.

Por ejemplo, en la secuencia

a pesar de que la instrucción sub (o subq) puede ejecutarse, debe esperar a que finalicen las anteriores, con acceso a memoria incluido. La planificación dinámica del pipeline permite evitar estos problemas.

Planificación dinámica del pipeline

La gran diferencia en esta técnica es la capacidad de elegir no cuántas instrucciones emitir, sino cuáles, posiblemente reordenando su emisión mientras el código se ejecuta. El pipeline, en este caso, se divide en 3 grandes unidades:

• una unidad para hacer el fetch y la emisión de instrucciones,
• una grupo de múltiples unidades funcionales (más de una docena en procesadores de 2015), y
• una unidad de commit (commit unit).

Este esquema se muestra en la siguiente figura.

La primera unidad lee, decodifica y emite las instrucciones a las distintas unidades funcionales. Cada unidad funcional posee una cola o buffer, llamada estación de reserva (reservation station), que almacena la operación a realizar y los operandos. En cuanto la unidad funcional está lista y se tienen todos los operandos, se ejecuta la operación. Una vez que se obtiene el resultado, el mismo se envía a todas las unidades funcionales que lo necesitan y a la unidad de commits, que lo almacena en un buffer hasta que es seguro guardarlo, ya sea en el banco de registros o en la memoria. Este buffer se llama de reordenamiento (reorder buffer), y se usa también para enviar resultados previamente calculados a las unidades funcionales que los necesiten, del mismo modo que se haría con la lógica de reenvío de datos en el pipeline que conocemos.

Este conjunto de colas de operandos y resultados funciona como un renombrado de registros. Conceptualmente, lo que se hace es lo siguiente:

1. Al emitir una instrucción, esta se copia a la estación de reserva, junto con los operandos disponibles en el banco de registros o el buffer de reordenamiento. Si no están disponibles todos los operandos o la unidad funcional no está lista, se encola hasta que esté todo disponible. Una vez encolados los operandos, la instrucción ya los tiene disponibles y los mismos pueden ser modificados en el banco de registros, otras unidades o el buffer de reordenamiento.
2. Si un operando no está en el banco de registros ni el buffer de reordenamiento, es el resultado de una unidad funcional, cuyo nombre se registra. Cuando la unidad funcional genera el resultado, se copia inmediatamente a quienes lo necesitan.

Se puede pensar que la planificación dinámica analiza el flujo de datos de un programa y el procesador ejecuta las instrucciones de forma tal que este flujo se mantenga. La ejecución de las instrucciones de este modo se llama ejecución fuera de orden (out-of-order execution). El contrario se llama ejecución en orden (in-order execution). Para simplificar la detección y rastreo de dependencias, es necesario que la unidad de lectura y emisión emita las instrucciones en orden. Además, la unidad de commits actualiza los registros y graba a memoria en el orden de lectura de las instrucciones; esto se conoce como commit en orden (in-order commit). En el caso de una excepción, se puede ver cuál fue la última instrucción ejecutada y hacer los commits correspondientes a las instrucciones anteriores a esa. A pesar de que las unidades de lectura y de actualización procesan en orden, las unidades funcionales operan en el orden que sea más conveniente, que es cuando los datos están disponibles.

Una extensión que se hace a esta técnica es la ejecución especulativa, junto con la predicción de saltos. La predicción permite continuar con la lectura y ejecución de instrucciones, mientras que el commit en orden garantiza que no se escribirán datos erróneos. Un pipeline especulativo con planificación dinámica puede especular incluso con el resultado de las operaciones de carga de datos y cálculo de direcciones, basándose en que la unidad de commits no permitirá actualizar los datos si se especuló de manera incorrecta.

Eficiencia energética

A medida que las técnicas se vuelven más complejas, se requieren más transistores, ya que todo se implementa en hardware (porque el software es lento). Más transistores significa un mayor consumo de energía, y las soluciones complejas son ineficientes energéticamente hablando. Es por esto que hubo un cambio de paradigma donde se pasó de un procesador extremadamente complejo, a implementar múltiples procesadores por chip, con éstos últimos implementando pipelines más chatos y con especulaciones menos agresivas. La idea es que estos procesadores tienen un mejor rendimiento por Joule, siendo preferidos cuando hay restricciones energéticas.

La siguiente tabla muestra cómo cae la profundidad del pipeline, cae el consumo, y aumenta el cantidad de procesadores por chip. Además, están ordenados en orden creciente de rendimiento (cuanto más abajo en la tabla, mejor el procesador). Aunque también se puede pensar que sólo están ordenados por fecha.

Bibliografía específica

Patterson, David A., and John L. Hennessy. Computer Organization and Design: The Hardware/Software Interface. RISC-V edition. Cambridge, Massachusetts: Morgan Kaufmann Publishers, an imprint of Elsevier, 2018. Sec. 4.10.