Tomasulo algoritme - Tomasulo algorithm

Tomasulos algoritme er en hardware- algoritme til computerarkitektur til dynamisk planlægning af instruktioner, der muliggør udførelse uden for ordren og muliggør mere effektiv brug af flere eksekveringsenheder. Det blev udviklet af Robert Tomasulo hos IBM i 1967 og blev først implementeret i IBM System/360 Model 91 ’s floating point -enhed .

De store nyskabelser i Tomasulos algoritme omfatter omdøbning af registre i hardware, reservationsstationer til alle udførelsesenheder og en fælles databus (CDB), hvor beregningsværdier udsendes til alle reservationsstationer, der kan have brug for dem. Disse udviklinger muliggør forbedret parallel udførelse af instruktioner, der ellers ville stoppe ved brug af scoreboarding eller andre tidligere algoritmer.

Robert Tomasulo modtog Eckert – Mauchly -prisen i 1997 for sit arbejde med algoritmen.

Implementeringskoncepter

Tomasulos flydepunktsenhed

Følgende er de begreber, der er nødvendige for implementeringen af ​​Tomasulos algoritme:

Fælles databus

Common Data Bus (CDB) forbinder reservationsstationer direkte med funktionelle enheder. Ifølge Tomasulo "bevarer den forrang, samtidig med at den tilskynder til samtidighed". Dette har to vigtige effekter:

1. Funktionelle enheder kan få adgang til resultatet af enhver handling uden at involvere et floating-point-register, så flere enheder, der venter på et resultat, kan fortsætte uden at vente på at løse konflikter om adgang til at registrere fillæseporte.
2. Hazard Detection og kontroludførelse distribueres. Reservationsstationerne kontrollerer, hvornår en instruktion kan udføres i stedet for en enkelt dedikeret fareenhed.

Instruktion rækkefølge

Instruktioner udstedes i rækkefølge, således at virkningerne af en instrukserække, f.eks. Undtagelser fra disse instruktioner, forekommer i samme rækkefølge som på en in-order processor, uanset at de udføres uden for rækkefølge (dvs. ikke-sekventielt).

Registrer omdøbning

Tomasulos algoritme bruger omdøbning af register til korrekt udførelse uden for ordre. Alle registre til generelle formål og reservationsstationer har enten en reel værdi eller en pladsholderværdi. Hvis en reel værdi ikke er tilgængelig for et destinationsregister i udstedelsesfasen, bruges en pladsholderværdi i første omgang. Pladsholderværdien er et mærke, der angiver, hvilken reservationsstation der vil producere den reelle værdi. Når enheden er færdig og sender resultatet på CDB, vil pladsholderen blive erstattet med den reelle værdi.

Hver funktionel enhed har en enkelt reservationsstation. Reservationsstationer indeholder de oplysninger, der er nødvendige for at udføre en enkelt instruktion, herunder operationen og operanderne. Den funktionelle enhed begynder at behandle, når den er gratis, og når alle kildeoperander, der er nødvendige for en instruktion, er ægte.

Undtagelser

Rent praktisk kan der være undtagelser, for hvilke der ikke er tilstrækkelig statusinformation om en undtagelse tilgængelig, i hvilket tilfælde processoren kan rejse en særlig undtagelse, kaldet en "upræcis" undtagelse. Præcise undtagelser kan ikke forekomme i implementeringer i rækkefølge , da processorstatus kun ændres i programrækkefølge (se RISC Pipeline Exceptions ).

Programmer, der oplever "præcise" undtagelser, hvor den specifikke instruktion, der tog undtagelsen, kan bestemmes, kan genstarte eller genudføre på tidspunktet for undtagelsen. Imidlertid kan dem, der oplever "upræcise" undtagelser generelt ikke genstarte eller genudføre, da systemet ikke kan bestemme den specifikke instruktion, der tog undtagelsen.

Instruktionens livscyklus

De tre trin, der er anført nedenfor, er de stadier, gennem hvilke hver instruktion går fra det er udstedt til det er gennemført.

Registrer legende

• Op - repræsenterer den operation, der udføres på operander
• Qj, Qk - reservationsstationen, der vil producere den relevante kildeoperand (0 angiver, at værdien er i Vj, Vk)
• Vj, Vk - værdien af ​​kildeoperanderne
• A - bruges til at gemme hukommelsesadresseoplysningerne for en belastning eller butik
• Optaget - 1 hvis optaget, 0 hvis ikke optaget
• Qi - (Kun registerenhed) reservationsstationen, hvis resultat skal lagres i dette register (hvis det er tomt eller 0, er der ikke bestemt nogen værdier for dette register)

Fase 1: problem

I udstedelsesfasen udstedes instruktioner til udførelse, hvis alle operander og reservationsstationer er klar, eller de ellers er gået i stå. Registre omdøbes i dette trin, hvilket eliminerer WAR- og WAW -farer.

• Hent den næste instruktion fra lederen af ​​instruktionskøen. Hvis instruktionsoperanderne i øjeblikket er i registre, så
  • Hvis der findes en matchende funktionel enhed, skal du udstede instruktionen.
  • Ellers, da der ikke er nogen tilgængelig funktionel enhed, standser instruktionen, indtil en station eller buffer er fri.
• Ellers kan vi antage, at operanderne ikke er i registre, og derfor bruger virtuelle værdier. Den funktionelle enhed skal beregne den reelle værdi for at holde styr på de funktionelle enheder, der producerer operanden.

if (RegisterStat[rs].Qi¦0) {
	RS[r].Qj ← RegisterStat[rs].Qi
}
else {
	RS[r].Vj ← Regs[rs];
	RS[r].Qj ← 0;
}
if (RegisterStat[rt].Qi¦0) { 
	RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
	RS[r].Vk ← Regs[rt]; 
	RS[r].Qk ← 0;
}
RS[r].Busy ← yes;
RegisterStat[rd].Qi ← r;

if (RegisterStat[rs].Qi¦0) {
	RS[r].Qj ← RegisterStat[rs].Qi;
}
else {
	RS[r].Vj ← Regs[rs];
	RS[r].Qj ← 0;
}
RS[r].A ← imm;
RS[r].Busy ← yes;

RegisterStat[rt].Qi ← r;

if (RegisterStat[rt].Qi¦0) {
	RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
	RS[r].Vk ← Regs[rt];
	RS[r].Qk ← 0
};

Eksempel på Tomasulos algoritme

Trin 2: udfør

I udførelsesfasen udføres instruktionsoperationer. Instruktioner forsinkes i dette trin, indtil alle deres operander er tilgængelige, hvilket eliminerer RAW -farer. Programmets korrekthed opretholdes gennem effektiv adresseberegning for at forhindre farer gennem hukommelse.

• Hvis en eller flere af operanderne endnu ikke er tilgængelige: Vent på, at operand bliver tilgængelig på CDB.
• Når alle operander er tilgængelige, så: hvis instruktionen er en last eller butik
  • Beregn den effektive adresse, når basisregistret er tilgængeligt, og anbring det i load/store -bufferen
    • Hvis instruktionen er en belastning: Udfør, så snart hukommelsesenheden er tilgængelig
    • Ellers, hvis instruktionen er en butik, så vent på værdien, der skal gemmes, før du sender den til hukommelsesenheden
• Ellers er instruktionen en aritmetisk logisk enhed (ALU) operation: udfør instruktionen på den tilsvarende funktionelle enhed

(RS[r].Qj = 0) and (RS[r].Qk = 0)

RS[r].A ← RS[r].Vj + RS[r].A;

Trin 3: skriv resultat

I skriveresultatfasen skrives ALU -operationsresultater tilbage til registre, og lageroperationer skrives tilbage til hukommelsen.

• Hvis instruktionen var en ALU -operation
  • Hvis resultatet er tilgængeligt, så: skriv det på CDB og derfra ind i registre og eventuelle reservationsstationer, der venter på dette resultat
• Ellers, hvis instruktionen var en butik, så skriv dataene til hukommelsen under dette trin

	∀x(if (RegisterStat[x].Qi = r) {
		regs[x] ← result;
		RegisterStat[x].Qi = 0
	});
	∀x(if (RS[x].Qj = r) {
		RS[x].Vj ← result;
		RS[x].Qj ← 0; 
	});
	∀x(if (RS[x].Qk = r) {
		RS[x].Vk ← result;
		RS[x].Qk ← 0;
	});
	RS[r].Busy ← no;

	Mem[RS[r].A] ← RS[r].Vk;
	RS[r].Busy ← no;

Forbedringer af algoritme

Begreberne reservationsstationer, omdøbning af register og den fælles databus i Tomasulos algoritme viser betydelige fremskridt inden for design af højtydende computere.

Reservationsstationer påtager sig ansvaret for at vente på operander i nærvær af dataafhængigheder og andre uoverensstemmelser såsom varierende lagringstilgangstid og kredsløbshastigheder og frigør dermed de funktionelle enheder. Denne forbedring overvinder lange flydende forsinkelser og hukommelsesadgang. Især algoritmen er mere tolerant over for cachemishandlinger. Derudover er programmerere befriet for at implementere optimeret kode. Dette er et resultat af, at den fælles databus og reservationsstation arbejder sammen for at bevare afhængigheder samt opmuntre til samtidighed.

Ved at spore operander til instruktioner i reservationsstationerne og registrere omdøbning i hardware minimerer algoritmen læse-efter-skrivning (RAW) og eliminerer farer efter skrive-efter-skrivning (WAW) og Skriv-efter- læsning (WAR) ved computerarkitektur . Dette forbedrer ydeevnen ved at reducere spildtid, der ellers ville være nødvendig for boder.

En lige så vigtig forbedring i algoritmen er, at designet ikke er begrænset til en specifik pipeline -struktur. Denne forbedring gør det muligt for algoritmen at blive bredere vedtaget af processorer med flere spørgsmål. Derudover udvides algoritmen let for at muliggøre filialspekulation.

Ansøgninger og arv

Tomasulos algoritme uden for IBM var ubrugt i flere år efter implementeringen i System/360 Model 91 -arkitekturen. Imidlertid oplevede det en enorm stigning i brugen i løbet af 1990'erne af tre grunde:

1. Når først cacher blev almindelige, blev Tomasulo -algoritmens evne til at opretholde samtidighed under uforudsigelige belastningstider forårsaget af cachemisser værdifuld i processorer.
2. Dynamisk planlægning og filialspekulation om, at algoritmen muliggør hjælp til ydeevne, da processorer udsendte flere og flere instruktioner.
3. Spredning af massemarkedssoftware betød, at programmører ikke ville kompilere til en specifik pipelinestruktur. Algoritmen kan fungere med enhver pipeline-arkitektur, og derfor kræver software få arkitekturspecifikke ændringer.

Mange moderne processorer implementerer dynamiske planlægningsordninger, der er afledt af Tomasulos originale algoritme, herunder populære Intel x86-64 chips.

Se også

• Ombestil buffer (ROB)
• Instruktion-niveau parallelisme (ILP)

Referencer

Yderligere læsning

• Savard, John JG (2018) [2014]. "Pipelined and Out-of-Order Execution" . quadibloc . Arkiveret fra originalen 2018-07-03 . Hentet 2018-07-16 .

eksterne links

• Dynamisk planlægning - Tomasulos algoritme på Wayback -maskinen (arkiveret 25. december 2017)
• HASE Java -appletsimulering af Tomasulos algoritme