El 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.

• 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

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.

In the execute stage, the instruction operations are carried out. Instructions are delayed in this step until all of their operands are available, eliminating RAW hazards. Program correctness is maintained through effective address calculation to prevent hazards through memory.

• If one or more of the operands is not yet available then: wait for operand to become available on the CDB.
• When all operands are available, then: if the instruction is a load or store
  • Compute the effective address when the base register is available, and place it in the load/store buffer
    • If the instruction is a load then: execute as soon as the memory unit is available
    • Else, if the instruction is a store then: wait for the value to be stored before sending it to the memory unit
• Else, the instruction is an arithmetic logic unit (ALU) operation then: execute the instruction at the corresponding functional unit

In the write Result stage, ALU operations results are written back to registers and store operations are written back to memory.

• If the instruction was an ALU operation
  • If the result is available, then: write it on the CDB and from there into the registers and any reservation stations waiting for this result
• Else, if the instruction was a store then: write the data to memory during this step