Algorisme de Tomasulo

L'algorisme Tomasulo és un algorisme de maquinari desenvolupat el 1967 per Robert Tomasulo d'IBM. Permet que instruccions seqüencials que normalment es quedarien retingudes per certes dependències s'executin no seqüencialement (execució fora d'ordre). Va ser implementat per primer cop per la unitat de coma flotant del computador IBM System/360 model 91.

Aquest algorisme es diferencia de l'algorisme marcador en el fet que fa servir reanomenament de registres. On el marcador resol riscos Write-after-Write (WAW) i Write-after-Read (WAR) retenint, el reanomenament de registres permet continuar el processament d'instruccions. L'algorisme Tomasulo també fa servir un bus de dades comú (CDB), en el que els valors calculats són emesos a totes les estacions reserva que poden necessitar-los. Això també permet executar paral·lelament instruccions que amb marcador podrien ser retingudes.

Robert Tomasulo va rebre el Premi Eckert-Mauchly en 1997 pel seu algorisme.

Conceptes d'implementació

Els conceptes necessaris per a la implementació de l'algorisme Tomasulo són els següents.

• Les instruccions són llançades seqüencialment perquè els efectes d'una seqüència d'instruccions com ara excepcions provocades per aquestes instruccions tinguin lloc en el mateix ordre que en el cas d'un processador no segmentat, a pesar del fet que van a ser executades no seqüencialment.

• Tots els registres de propòsit general i les estacions de reserva guarden valors reals o virtuals. Si un valor real no és disponible per a un registre de destí durant la fase de llançament, inicialment es fa servir un valor virtual. La unitat funcional que està calculant el valor real és assignada com a valor virtual. Els valors de registre virtual són convertits a valors reals tan aviat com la unitat funcional designada completa el seu càlcul.

• Les unitats funcionals fan servir estacions de reserva amb múltiples slots. Cada slot guarda informació necessària per a executar una sola instrucció, incloent-hi l'operació i els operands. La unitat funcional comença el processament quan és lliure i quan tots els operands font necessaris per a la instruccions són reals.

Cicle de vida d'una instrucció

Les tres fases llistades a sota són les fases a través de les quals cada instrucció passa del moment en què és llançada al moment en què és acomplerta.

Fase 1: Llançament

A la fase de llançament, les instruccions són llançades per a ser executades si tots els operands i les estacions de reserva estan preparades; altrament són retingudes. Els registres són reanomenats en aquest pas, eliminant els riscos WAR i WAW.

• Si els operands de la instruccions estan als registres: agafar la següent instrucció del cap de la cua d'instruccions.
  • Si existeix una estació de reserva lliure: llançar la instrucció.
  • Si no: retenir la instrucció fins que una estació o un buffer sigui lliure.
• Si no: fer servir valors virtuals; anotant les unitats funcionals que produiran els operands.

Fase 2: Execució

A la fase d'execució, les operacions de la instrucció són portades a terme. Les instruccions són retardades en aquest pas fins que tots els seus operands són disponibles, eliminant riscos RAW. La correctesa del programa és mantinguda a través del càlcul d'adreces efectives per a prevenir riscos de memòria.

1. Si un o més dels operands no és encara disponible: s'espera que l'operand sigui disponible al CDB.
2. Si la instrucció és un load o un store: Calcula l'adreça efectiva quan el registre base sigui disponible, i posa'l al buffer del load/store
   1. Si la instrucció és un load: executa tan aviat com la unitat de memòria sigui disponible.
   2. Si la instrucció és un store: espera al valor a guardar abans d'enviar-la a la unitat de memòria.
   3. Si la instrucció és aritmètica: executa la instrucció a la unitat funcional corresponent.

Fase 3: Escriptura del resultat

En la fase d'escriptura del resultat, les operacions aritmètiques escriuen als registres i les operacions de store escriuen a la memòria.

• Si l'operació era aritmètica
  • Si el resultat és disponible: escriu-lo al CDB i d'allí als registres i qualsevol estació de reserva esperant aquest resultat.
• Si l'operació era un store: escriure les dades a memòria.

Enllaços externs

• Dynamic Scheduling - Tomasulo's Algorithm Arxivat 2014-03-10 a Wayback Machine.

• An Efficient Algorithm for Exploiting Multiple Arithmetic Units Arxivat 2013-07-19 a Wayback Machine., IBM Journal of Research and Development, 11(1):25-33, January 1967.
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm Arxivat 2013-09-11 a Wayback Machine., Institute for Computing Systems Architecture, Edinburgh University.
• TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson