Scoreboarding

Scoreboarding o algorisme marcador, és un mètode centralitzat fet servir al CDC 6600, per a planificar dinàmicament un pipeline i així disposar d'execució fora d'ordre quan no hi hagi conflictes i el hardware sigui disponible. Les dependències de dades de cada instrucció són enregistrades a un marcador. Les instruccions són llançades només quan el marcador determina que no hi ha conflictes amb instruccions prèviament llançades però encara incompletes. Si una instrucció és retinguda perquè no és segur que continuï, el marcador monitora el flux d'execució d'instruccions fins que totes les dependències han estat resoltes. Després, la instrucció retinguda és llançada.

Fases

Les instruccions són decodificades en ordre i passen per les següents quatre fases:

Llançament

El sistema comprova quins registres seran llegits i escrits per aquesta instrucció. Aquesta informació és recordada, ja que serà necessària en les següents fases.

Per a evitar riscos Write-after-Write (WAW) la instrucció és retinguda fins que les instruccions que volen escriure al mateix registre són acomplertes.

La instrucció també és retinguda mentre les unitats funcionals estan ocupades.

Lectura d'operands

Després que una instrucció ha estat llançada i correctament ubicada al mòdul de hardware requerit, la instrucció espera fins que tots els operands són disponibles.

Aquest procediment resol dependències reals Read-after-Write (RAW) perquè els registres que seran escrits per altres instruccions són considerats no disponibles fins que són realment escrits.

Execució

Quan tots els operands han estat agafats, la unitat funcional comença la seva execució.

Quan el resultat està preparat, el marcador és notificat.

Escriptura del resultat

Durant aquesta fase el resultat serà escrit al seu registre de destí. Això no obstant, aquesta operació és retardada fins que instruccions anteriors que volen llegir els mateixos registres han finalitzat la seva fase de lectura d'operands. Així, les dependències de dades Write-after-Read (WAR) poden ser solucionades.

Estructura de dades

Per a controlar l'execució de les instruccions, el marcador manté tres taules d'estat:

  • Estat d'instrucció: Indica, per a cada instrucció que s'està executant, en quina de les 4 fases es troba.
  • Estat d'unitat funcional: Indica, per a cada unitat funcional, 9 atributs:
    • Busy: Indica si la unitat s'està fent servir o no.
    • Op: Operació a executar a la unitat (ex: MUL, DIV o MOD)
    • Fi: Registre a escriure
    • Fj,Fk: Registres a llegir (F de File)
    • Qj,Qk: Unitats funcionals que produiran els registres a llegir Fj, Fk
    • Rj,Rk: Flags que indiquen quan Fj i Fk estan preparats (R de Ready)
  • Registre d'estat: Indica, per a cada registre, quina unitat funcional hi escriurà els resultats.

L'algorisme

L'algorisme detallat per al control del marcador és descrit a continuació. 

function llança(op, dst, src1, src2)
wait until (!Busy[FU] AND !Result[dst]); // FU pot ser qualsevol unitat funcional que pugui executar l'operació op
Busy[FU] ← Yes; 
Op[FU] ← op;
Fi[FU] ← dst;
Fj[FU] ← src1;
Fk[FU] ← src2;
Qj[FU] ← Result[src1];
Qk[FU] ← Result[src2]; 
Rj[FU] ← not Qj;
Rk[FU] ← not Qk;
Result[dst] ← FU;

function llegeix_operands(FU)
wait until (Rj[FU] AND Rk[FU]);
Rj[FU] ← No;
Rk[FU] ← No;

function executa(FU)
// Executa el que FU hagi de fer

function escriu(FU)
wait until (
  
    
      
        ∀
      
    
    {\displaystyle \forall }
  
f {(Fj[f]≠Fi[FU] OR Rj[f]=No) AND (Fk[f]≠Fi[FU] OR Rk[f]=No)})
foreach f do
if Qj[f]=FU then Rj[f] ← Yes;
if Qk[f]=FU then Rk[f] ← Yes;
Result[Fi''FU'' ← 0;
Busy[FU] ← No;

Limitacions

El mètode marcador ha de retenir la fase de llançament quan no hi hagi unitat funcional disponible. En aquest cas, les instruccions següents hauran d'esperar fins que aquesta unitat funcional estigui disponible. Altres tècniques com l'algorisme Tomasulo poden evitar aquest risc estructural i també resoldre dependències WAR i WAW amb reanomenament de registres.

Enllaços externs

  • Dynamic Scheduling - Scoreboard Arxivat 2013-08-20 a Wayback Machine.
  • Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson
  • EECS 252 Graduate Computer Architecture Lec XX - TOPIC, Electrical Engineering and Computer Sciences, Berkeley, University of California.