Scoreboard - Scoreboarding

Scoreboarding är en central metod, som först användes i CDC 6600- datorn, för dynamisk schemaläggning av instruktioner så att de kan köras i ordning när det inte finns några konflikter och hårdvaran är tillgänglig.

På resultattavlan loggas, spåras och följs strikt datainvänligheten för varje instruktion hela tiden. Instruktioner släpps endast när resultattavlan fastställer att det inte finns några konflikter med tidigare utfärdade ("under flygning") instruktioner. Om en instruktion stannar eftersom den är osäker att utfärda (eller det finns otillräckliga resurser) övervakar resultattavlan flödet av exekveringsinstruktioner tills alla beroenden har lösts innan den stoppade instruktionen utfärdas. I huvudsak: läs fortsätt frånvaron av skrivrisker och skriv fortsätt i frånvaro av läsrisker.

Scoreboarding är i huvudsak en hårdvaruimplementering av samma underliggande algoritm som ses i dataflödesspråk , vilket skapar en Directed Acyclic Graph , där samma logik används i programmeringsspråkets körtid.

Stadier

Instruktioner avkodas i ordning och går igenom följande fyra steg.

  1. Problem : Systemet kontrollerar vilka register som kommer att läsas och skrivas av denna instruktion och där konflikter WAR och RAW och WAW upptäcks. RAW- och WAR-faror registreras med hjälp av en beroende matris (konstruerad av SR NOR-spärrar i original 6600-designen) eftersom det kommer att behövas i följande steg. Samtidigt registreras en post i en andra matris som registrerar instruktionsordningen som en Directed Acyclic Graph . För att undvika utgångsberoenden ( WAW - Skriv efter skrivning) stannar instruktionen tills instruktioner som avser att skriva till samma register har slutförts. Instruktionen stoppas också när nödvändiga funktionella enheter för närvarande är upptagen. * Ingen instruktion utfärdas någonsin om den inte är 100% spårbar från start till slut *.
  2. Läs operander : Efter att en instruktion har utfärdats och tilldelats korrekt till den nödvändiga hårdvarumodulen (kallad en beräkningsenhet i Thorntons bok) väntar enheten tills alla operander blir tillgängliga. Läs- bara fortsätter när skriv beroenden ( RAW - Läs efter Write) har sjunkit från alla andra enheter. För att undvika påståenden om registerfilport väljer en prioritetsväljare en beräkningsenhet (om flera enheter är fria från risker).
  3. Utförande : När alla operander har hämtats startar beräkningsenheten sin körning. När resultatet är klart meddelas resultattavlan.
  4. Skriv resultat : I detta skede är resultatet klart men har ännu inte skrivits till sitt destinationsregister. Skrivningen kanske inte fortsätter förrän enheten är fri från alla ( WAR - Skriv efter avläsning) risker. De enda extra förseningarna här är baserade på tillgängligheten av registerfilportar: i 6600 användes en Priority Picker för att välja ett resultat per skrivport. När enheten är skriven markeras den inte längre upptagen och alla faror och tillstånd tappas. Observera att endast i avancerade (utökade, exakta) resultattavlor med "Shadow" -funktion kan skrivresultatfasen förhindras (fördröjs). Originalet på 6600 hade inte denna funktion.

Det är viktigt att notera över som läser endast fortgå i frånvaro av skriv risker och som skriver vidare i frånvaro av Läs faror. Detta är logiskt men kontraindikativt för förväntningarna. Observera särskilt att Writes måste vänta med att skriva efter läsning för att ge andra enheter möjlighet att läsa det aktuella värdet i ett register innan de skrivs över med det nya. Därför måste skrivningar vänta tills avsaknaden av WaR-risker.

Datastruktur

För att kontrollera genomförandet av instruktionerna har resultattavlan tre statustabeller:

  • Instruktionsstatus : Indikerar för varje instruktion som utförs vilken av de fyra stegen den befinner sig i.
  • Funktionsenhetsstatus : Indikerar tillståndet för varje funktionsenhet. Varje funktionsenhet har 9 fält i tabellen:
    • Upptagen: Anger om enheten används eller inte
    • Op: Funktion för att utföra i enheten (t.ex. MUL, DIV eller MOD)
    • F i : Destinationsregister
    • F j , F k : Källregisternummer
    • Q j , Q k : Funktionsenheter som producerar källregistren F j , F k
    • R j , R k : Flaggor som indikerar när F j , F k är redo för och ännu inte läst.
  • Registerstatus : Indikerar för varje register vilken funktionsenhet som skriver resultat i det.

Den ursprungliga 6600-algoritmen

Den detaljerade algoritmen för resultattavlan, beskriven i det ursprungliga patentet, beskrivs nedan: 

 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] ← Qj[FU] == 0;
    Rk[FU] ← Qk[FU] == 0;
    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 (∀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; // 0 means no FU generates the register's result
    RegFile[Fi[FU]] ← computed value;
    Busy[FU] ← No;

Anmärkningar

Thorntons bok daterar modern datorterminologi.

  • Funktionsenheter (rörledningar) kallades "Beräkningsenheter".
  • "First Order Conflict" täckte både stall på grund av att alla enheter var upptagen och också täckte WAW-konflikter .
  • "Andra ordningskonflikt" var den term som användes för RAW-konflikt .
  • "Tredje ordningskonflikten" täckte WAR-konflikt .

Stoppning inträffade bara vid utgivningsstadiet när konflikter med "First Order" upptäcktes. Några andra tekniker som Tomasulo-algoritm löser dessutom WAW-beroenden med registerbyte . Den ursprungliga CDC 6600 hade sannolikt inte WAW-fartspårning bara för att dess designers var tvungna att leverera produkt och sedan gick vidare till 7600: stalling istället var det mest lämpliga alternativet. Det finns ingen teknisk anledning till att Registerbyte inte ska läggas till i resultattavlorna.

En analys av båda algoritmerna utfördes av Luke Leighton och en transformationsprocess skisseras som visar ekvivalens mellan Tomasulo-algoritmen och 6600 resultattavlealgoritmen. WAW-riskupplösning saknas verkligen i den ursprungliga algoritmen: 6600 skulle stanna vid den första förekomsten av en skrivrisk.

Se även

Referenser

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

externa länkar