El algoritmo de Tomasulo

El algoritmo de Tomasulo es un algoritmo de hardware de arquitectura informática para la planificación dinámica de instrucciones que permite la ejecución fuera de orden y posibilita un uso más eficiente de múltiples unidades de ejecución. Fue desarrollado por Robert Tomasulo en IBM en 1967 y se implementó por primera vez en la unidad de punto flotante del IBM System/360 Modelo 91. ^{[ 1 ]}

Las principales innovaciones del algoritmo de Tomasulo incluyen el cambio de nombre de los registros en el hardware, estaciones de reserva para todas las unidades de ejecución y un bus de datos común (CDB) por el cual se transmiten los valores calculados a todas las estaciones de reserva que puedan necesitarlos. Estos avances permiten una mejor ejecución paralela de instrucciones que, de otro modo, se bloquearían con el uso de marcadores u otros algoritmos anteriores.

Robert Tomasulo recibió el Premio Eckert-Mauchly en 1997 por su trabajo en el algoritmo. ^{[ 2 ]}

Los siguientes son los conceptos necesarios para la implementación del algoritmo de Tomasulo:

El Bus de Datos Comunes (CDB) conecta las estaciones de reserva directamente con las unidades funcionales. Según Tomasulo, "conserva la precedencia al tiempo que fomenta la concurrencia". ^{[ 1 ] : 33} Esto tiene dos efectos importantes:

1. Las unidades funcionales pueden acceder al resultado de cualquier operación sin necesidad de utilizar un registro de punto flotante, lo que permite que varias unidades que esperan un resultado continúen sin tener que esperar a resolver la contención por el acceso a los puertos de lectura del archivo de registros.
2. La detección de riesgos y la ejecución del control están distribuidas. Las estaciones de reserva controlan cuándo se puede ejecutar una instrucción, en lugar de una única unidad dedicada a la detección de riesgos.

Las instrucciones se emiten de forma secuencial, de modo que los efectos de una secuencia de instrucciones, como las excepciones que generan, se producen en el mismo orden que en un procesador que se ejecuta en orden, independientemente de que se estén ejecutando fuera de orden (es decir, de forma no secuencial).

El algoritmo de Tomasulo utiliza el cambio de nombre de registros para ejecutar correctamente incluso en orden inverso. Todos los registros de las estaciones de reserva y de propósito general contienen un valor real o un valor de marcador de posición. Si un registro de destino no dispone de un valor real durante la fase de emisión, se utiliza inicialmente un valor de marcador de posición. Este valor de marcador de posición indica qué estación de reserva generará el valor real. Cuando la unidad finaliza y difunde el resultado en la base de datos de control (CDB), el marcador de posición se reemplaza por el valor real.

Cada unidad funcional dispone de una única estación de reserva. Estas estaciones almacenan la información necesaria para ejecutar una instrucción, incluyendo la operación y los operandos. La unidad funcional comienza a procesar cuando está libre y cuando todos los operandos fuente necesarios para la instrucción son reales.

En la práctica, puede haber excepciones para las que no se dispone de suficiente información de estado sobre una excepción, en cuyo caso el procesador puede generar una excepción especial, denominada excepción imprecisa . Las excepciones imprecisas no pueden ocurrir en implementaciones en orden , ya que el estado del procesador cambia solo en el orden del programa (véase la sección Excepciones de la tubería RISC clásica ).

Los programas que experimentan excepciones precisas , donde se puede determinar la instrucción específica que generó la excepción, pueden reiniciarse o volver a ejecutarse en el punto donde ocurrió la excepción. Sin embargo, aquellos que experimentan excepciones imprecisas generalmente no pueden reiniciarse ni volver a ejecutarse, ya que el sistema no puede determinar la instrucción específica que generó la excepción.

Las tres etapas que se enumeran a continuación son las etapas por las que pasa cada instrucción desde el momento en que se emite hasta que se completa su ejecución.

• RS - Estado de la reserva
• RegisterStat - Estado del registro; contiene información sobre los registros.
• regs[x] - Valor del registro x
• Mem[A] - Valor de la memoria en la dirección A

• rd - número de registro de destino
• rs, rt - números de registro fuente
• imm - signo extendido campo inmediato
• r - estación de reserva o búfer al que se asigna la instrucción

• Op - representa la operación que se realiza sobre los operandos.
• Qj, Qk: la estación de reserva que producirá el operando fuente correspondiente (0 indica que el valor está en Vj, Vk).
• Vj, Vk: el valor de los operandos fuente.
• A - se utiliza para almacenar la información de la dirección de memoria para una carga o almacenamiento.
• Ocupado: 1 si está ocupado, 0 si no está ocupado.

• Qi: la estación de reservas cuyo resultado debe almacenarse en este registro (si está en blanco o es 0, no se destinan valores a este registro).

En la fase de emisión, se dan instrucciones para su ejecución si todos los operandos y estaciones de reserva están listos; de lo contrario, se bloquean. En este paso, se renombran los registros, eliminando los riesgos WAR y WAW.

• Recuperar la siguiente instrucción del inicio de la cola de instrucciones. Si los operandos de la instrucción se encuentran actualmente en los registros, entonces
  • Si hay disponible una unidad funcional compatible, emita la instrucción.
  • De lo contrario, como no hay ninguna unidad funcional disponible, se retrasará la instrucción hasta que una estación o un búfer esté libre.
• De lo contrario, podemos asumir que los operandos no están en los registros y, por lo tanto, usar valores virtuales. La unidad funcional debe calcular el valor real para llevar un registro de las unidades funcionales que generan el operando.

En la fase de ejecución, se llevan a cabo las operaciones de las instrucciones. Estas se retrasan hasta que todos sus operandos estén disponibles, eliminando así los riesgos de acceso no autorizado. La corrección del programa se mantiene mediante el cálculo efectivo de direcciones para prevenir riesgos relacionados con la memoria.

• Si uno o más de los operandos aún no están disponibles, entonces: espere a que el operando esté disponible en la CDB.
• Cuando todos los operandos estén disponibles, entonces: si la instrucción es de carga o almacenamiento
  • Calcula la dirección efectiva cuando el registro base esté disponible y colócala en el búfer de carga/almacenamiento.
    • Si la instrucción es de carga, entonces: ejecutar tan pronto como la unidad de memoria esté disponible.
    • De lo contrario, si la instrucción es de almacenamiento, entonces: esperar a que el valor se almacene antes de enviarlo a la unidad de memoria.
• De lo contrario, si la instrucción es una operación de la unidad aritmético-lógica (ALU), entonces: ejecute la instrucción en la unidad funcional correspondiente.

En la etapa de escritura de resultados, los resultados de las operaciones de la ALU se escriben de nuevo en los registros y las operaciones de almacenamiento se escriben de nuevo en la memoria.

• Si la instrucción era una operación de la ALU
  • Si el resultado está disponible, entonces: escríbalo en el CDB y desde allí en los registros y en cualquier estación de reserva que esté esperando este resultado.
• De lo contrario, si la instrucción era de almacenamiento, entonces: escribir los datos en la memoria durante este paso.

Los conceptos de estaciones de reserva, cambio de nombre de registros y bus de datos común en el algoritmo de Tomasulo representan avances significativos en el diseño de computadoras de alto rendimiento.

Las estaciones de reserva asumen la responsabilidad de esperar los operandos en presencia de dependencias de datos y otras inconsistencias, como tiempos de acceso al almacenamiento variables y velocidades de circuito, liberando así las unidades funcionales. Esta mejora supera las largas demoras de punto flotante y los accesos a memoria. En particular, el algoritmo es más tolerante a los fallos de caché. Además, los programadores no necesitan implementar código optimizado. Esto se debe a que el bus de datos común y la estación de reserva trabajan juntos para preservar las dependencias y fomentar la concurrencia. ^{[ 1 ] : 33}

Al rastrear los operandos para las instrucciones en las estaciones de reserva y renombrar los registros en el hardware, el algoritmo minimiza la lectura después de la escritura (RAW) y elimina los riesgos de la arquitectura de computadora de escritura después de la escritura (WAW) y escritura después de la lectura (WAR) . Esto mejora el rendimiento al reducir el tiempo perdido que de otro modo se requeriría para los bloqueos. ^{[ 1 ] : 33}

Una mejora igualmente importante en el algoritmo es que su diseño no se limita a una estructura de tubería específica. Esta mejora permite que el algoritmo sea adoptado más ampliamente por procesadores de múltiples emisiones . Además, el algoritmo se puede extender fácilmente para permitir la especulación de bifurcaciones. ^{[ 3 ] : 182}

El algoritmo de Tomasulo se implementó en la arquitectura System/360 Modelo 91. Fuera de IBM, permaneció sin utilizarse durante varios años. Sin embargo, experimentó un enorme aumento en su uso durante la década de 1990 por tres razones:

1. Una vez que las cachés se generalizaron, la capacidad del algoritmo para mantener la concurrencia durante los tiempos de carga impredecibles causados ​​por fallos de caché se volvió valiosa en los procesadores.
2. La planificación dinámica y la especulación de bifurcaciones del algoritmo permiten un rendimiento mejorado a medida que los procesadores emiten más y más instrucciones.
3. La proliferación de software de consumo masivo significó que los programadores no quisieran compilar para una estructura de canalización específica. El algoritmo puede funcionar con cualquier arquitectura de canalización y, por lo tanto, el software requiere pocas modificaciones específicas de la arquitectura. ^{[ 3 ] : 183}

Muchos procesadores modernos implementan esquemas de planificación dinámica que son variantes del algoritmo original de Tomasulo, incluidos los populares chips Intel x86-64 . ^{[ 5 ] [ 6 ]}

• Búfer de reordenamiento (ROB)
• Paralelismo a nivel de instrucción (ILP)

• Savard, John JG (2018) [2014]. "Ejecución en paralelo y fuera de orden" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .

• Planificación dinámica: el algoritmo de Tomasulo en Wayback Machine (archivado el 25 de diciembre de 2017)
• Simulación del algoritmo de Tomasulo mediante un applet de Java en HASE.