Algoritme de Tomasulo

El algoritme de Tomasulo és un algoritme de planificació dinàmica desenrollat per Robert Tomasulo, d'IBM. Es va dissenyar per a permetre a un processador eixecutar instruccions fòra d'orde. Este algoritme diferix del algoritme de marcador (Scoreboard) que este últim no dispon de renombrado de registres. En el seu lloc, l'algoritme de Scoreboard (scoreboarding) resol els riscs Escritura Despuix d'Escritura (EDE o WAW) i Escritura Despuix de Llectura (EDL o WAR) detenint l'eixecució, mentres que l'algoritme de Tomasulo permet el llançament de dites instruccions. Ademés, l'algoritme de Tomasulo utilisa un bus de senyes comuna en el que els valors calculats són enviats a totes les estacions de reserva que els necessiten. Açò permet millorar l'eixecució paralela d'instruccions en situacions en les que el scoreboarding fallaria i provocaria la parada.

Es va implementar per primera volta en l'unitat de punt flotant del processador IBM360/91.

En l'actualitat, gran part dels processadors fan us de variacions d'este algoritme per a la planificació dinàmica d'instruccions.

Conceptes per a l'implementació

Els següents són els conceptes necessaris per a l'implementació de l'algoritme de Tomasulo:

Bus comú de senyes (CDB, de l'anglés "Common data bus")

El Bus Comú de Senyes, o CDB, conecta a les estacions de reserva directament en les unitats funcionals (UF). D'acort a la definició de l'Algoritme de Tomasulo, el CDB "preserva la precedència, mentres que garantisa el soport per a la concurrència" Açò té dos conseqüències importants:

1. Les unitats funcionals (UF) poden accedir al resultat de qualsevol operació que tinga relació en el "registre de punt flotant", permetent que múltiples unitats esperen el resultat.
2. L'unitat de Detecció d'errors (Hazard Detection) i l'unitat de Control d'eixecució (Control Execution) es troben distribuïdes. Les estacions de reserva controlen quan una instrucció pot ser eixecutada, en lloc d'haver una única unitat de Detecció d'errors dedicada.

Orde d'instruccions

Les instruccions són emeses de forma seqüencial, per tant les excepcions disparades per estes ocorren en el mateix orde en que ingressen al processador, sense importar que estiguen sent eixecutades en un atre orde (no seqüencial)

Unitat de Punt flotant de Tomasulo

Renombrado de registres

L'algoritme de Tomasulo utilisa el renombrado de registres per a eixecutar de forma correcta les instruccions que no tenen orde. Tots els registres, els de us general i els de l'estació de reserva, guarden o un valor real o una etiqueta (placeholder). Si durant l'etapa d'Emissió, no es troba disponible un valor real per a ser enviat a un atre registre, s'utilisa com a valor una etiqueta (placeholder) indicant l'estació de reserva que produirà el valor real. Quan l'unitat termina de transmetre el resultat en el Bus Comú de Senyes, l'etiqueta és reemplaça en el valor real.

Cada Unitat Funcional (UF) té una única Estació de Reserva, estes guarden l'informació necessària per a eixecutar una única instrucció, incloent l'operació i els operants. Les UF comencen a processar quan estan lliures i tots els operants necessaris per a eixecutar l'instrucció contenen un valor real.

Excepcions

Podrien ocórrer excepcions per a les que no existix suficient informació de l'estat, en el cas del qual el processador pot llançar una excepció "imprecisa". Este tipo d'excepcions no poden ocórrer en implementacions que no siguen OoOE, ya que l'estat del processador només varia en l'orde del programa.

Els programes que experimenten excepcions precises, en les que l'instrucció que va provocar l'excepció pot ser determinada poden reiniciar o reejecutar en el moment de l'excepció. No obstant si s'experimenta una excepció imprecisa no es pot en general reiniciar o rejecutar, ya que el sistema no pot determinar l'instrucció que va provocar l'excepció.