Scoreboarding

Scoreboarding je centralizovani metod koji se koristi u računaru CDC 6600 za dinamičko planiranje protočne obrade tako da se instrukcije mogu izvršavati van reda kada nema konfilkta i kada je hardver dostupan. U scoreboard-u zavisnost podataka svake instrukcije se zapisuje. Instrukcije se puštaju tek kada scoreboard odredi da nema konflikta između prethodne i trenutne instrukcije. Ako je instrukcija stopirana zbog toga što nije bezbedno nastaviti, scoreboard nadgleda protok izvršavanja instrukcije dok sve zavisnosti ne budu sređene, pre sprovođenja stopiranja.

Faze

Instrukcije se dekodiraju redom i idu kroz sledeće četiri faze:

1. Izdavanje: Sistem proverava koji registri će biti čitani i na koje će biti pisano ovom instrukcijom. Ova informacija se pamti jer će biti potrebna u sledećim fazama. Kako bi izbegli izlazne zavisnosti, instrukcija se zaustavlja dok se ne završe instrukcije koje žele da pišu u isti registar. Instrukcija se takođe zaustavlja ako su zahtevane instrukcione jedinice zauzete.
2. Operandi čitanja: Nakon što su instrukcije izdate i pravilno raspoređene hardverskim modulima, instrukcija čeka dok svi operandi ne postanu dostupni. Ova procedura rešava zavisnosti pri čitanju jer registri na koje druga instrukcija želi da piše se ne smatraju dostupnim dok po njima nije pisano.
3. Izvršavanje: Kada su učitani svi operandi, funkcionalna jedinica počinje njegovo izvršenje. Nakon rezultat je spreman, scoreboard je obavešten.
4. Pisanje rezultata : U ovoj fazi rezultat treba da bude napisan na oređeni registar. Međutim, ova operacija je odložena dok ranija instrukcija (koja namerava da pročita ovaj registar) ne završi čitanje operanada. Na ovaj način, tzv. zavisnosti podataka se mogu rešiti.

Struktura podataka

Za kontrolu izvršenja uputstva, scoreboard održava tri statusne tabele:

• Status instrukcije: pokazuje u kojoj je instrukcija fazi.
• Status funkcionalne jedinice:
  • Zauzeto: pokazuje da li se jedinica koristi.
  • Op: Operacija koja se koristi u jedinici.
  • Fi: Registar destinacije.
  • Fj, Fk: Source-register brojevi.
  • Qj,Qk: Funkcionalne jedinice koje će proizvoditi izvorne registre Fj, Fk.
  • Rj, Rk: Zastave koje pokazuju kada su Fj, Fk spremni.
• 'Status registra: Pokazuje koja funkcijska jedinica će pisati rezultat u isti.

Algoritmi

Detaljan algoritam za scoreboard je niže:

 function issue(op, dst, src1, src2)
    wait until (!Busy[FU] AND !Result[dst]); // FU can be any functional unit that can execute operation 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 read_operands(FU)
    wait until (Rj[FU] AND Rk[FU]);
    Rj[FU] ← No;
    Rk[FU] ← No;

 function execute(FU)
    // Execute whatever FU must do

 function write_back(FU)
    wait until ($\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;

Napomene

Metod scoreboarding mora zaustaviti fazu kada funkcionalna jedinica nije na raspolaganju. U ovom slučaju, buduće instrukcije koje se potencijalno mogu izvršiti će sačekati dok se ne reši strukturna opasnost. Neke druge tehnike kao što Tomasulo algoritam može da izbegne strukturnu opasnost i reši zavisnosti sa preimenovanjem registra.

Reference

• Glenford Myers, "Register scoreboarding on a microprocessor chip", United States Patent 4891753

Spoljašnje veze

• Dynamic Scheduling - Scoreboard Arhivirano na sajtu Wayback Machine (20. avgust 2013)
• 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.