Boost­ing

Boost­ing

Alexan­der Lei­dinger
Alexander@Leidinger.net

Zwei Artikel von Michael D. Smith, Mark Horowitz, Mon­i­ca S. Lam
Com­put­er Sys­tems Lab­o­ra­to­ry
Stan­ford Uni­ver­si­ty
©1990 IEEE, ©1992 ASPLOS

 

Zusam­men­fas­sung:

Es wird ein super­skalar­er Prozes­sor beschrieben, der die pos­i­tiv­en Eigen­schaften von sta­tis­chem und dynamis­chem Sched­ul­ing vere­int, um die Leis­tung nicht numerisch­er Pro­gramme zu erhöhen. Um die Fähigkeit des Com­pil­ers, effek­tiv Befehle über viele Basic-Blocks hin­aus zu sched­ulen, zu nutzen, wird bei dieser Architek­tur sta­tis­ches Sched­ul­ing benutzt. Da bed­ingte Sprünge in nicht numerischem Code stark daten­ab­hängig sind, wird hier das Konzept geboost­eter Befehle einge­führt, deren Ergeb­nisse abhängig von später auszuführen­den Sprung­be­fehlen akzep­tiert wer­den. Boost­ing ent­fer­nt effek­tiv die Abhängigkeit­en von Sprün­gen und macht das Sched­ul­ing von Befehlen mit Neben­ef­fek­ten so ein­fach wie das von Befehlen ohne Neben­ef­fek­te. Zur Effizien­zsteigerung wird Boost­ing von der Hard­ware durch Schat­ten­struk­turen unter­stützt, welche vorüberge­hend die Neben­ef­fek­te geboost­eter Befehle puffern, bis die bed­ingten Sprünge von denen die geboost­eten Befehle abhän­gen aus­ge­führt wur­den. Dann wer­den die gepuffer­ten Neben­ef­fek­te entwed­er ver­wor­fen oder akzep­tiert. Die erzielte Leis­tung durch diese Art von sta­tis­chem Sched­ul­ing ist ver­gle­ich­bar mit der von dynamis­chem Sched­ul­ing.

Herun­ter­laden dieser Sem­i­na­rausar­beitung als kom­prim­ierte Post­script Datei.


Inhalt

  • Inhalt
  • Abbil­dungsverze­ich­nis
  • Tabel­len­verze­ich­nis
  • 1. Ein­führung
  • 2. Speku­la­tive Aus­führung von Befehlen
    • 2.1 Sichere Aus­führung speku­la­tiv­er Befehle
    • 2.2 Boost­ing
  • 3. Notwendi­ge Hard­ware für Boost­ing
    • 3.1 Kom­plette Unter­stützung von Boost­ing
    • 3.2 Par­tielle Unter­stützung von Boost­ing
  • 4. TORCH
    • 4.1 Hard­ware
  • 5. MATCH
    • 5.1 Hard­ware
  • 6. Mes­sun­gen
    • 6.1 Ergeb­nisse
    • 6.2 Berech­ti­gung von Boost­ing
    • 6.3 Ver­gle­ich von TORCH und MATCH
    • 6.4 Ver­gle­ich ver­schieden­er Boost­in­gop­tio­nen
    • 6.5 Ver­gle­ich von MinBoost3 mit einem dynamis­chen Sched­uler

Abbil­dungsverze­ich­nis

    • Typen speku­la­tiv­er Aus­führung
    • Beispiel geboost­eter Befehle
    • Ver­schiedene Reg­is­ter­filekon­fig­u­ra­tio­nen
    • Hard­ware der Option 2
    • Block Dia­gramm der TORCH Hard­ware
    • Block Dia­gramm der MATCH Hard­ware
    • Effek­tiv­itätsver­gle­ich mit einem dynamis­chen Sched­uler

Tabel­len­verze­ich­nis

    • Ausführungs- und Ergeb­nis­latenz
    • Benutzte Pro­gramme
    • Max­i­male the­o­retis­che Geschwindigkeitssteigerung basierend auf Load/Store Häu­figkeit
    • Geschwindigkeitssteigerung (TORCH) nur durch Basic Block Sched­ul­ing
    • Geschwindigkeitssteigerung bei kor­rekt vorherge­sagten Sprün­gen (MATCH+ mit Load/Store Reor­gan­i­sa­tion)
    • Geschwindigkeitssteigerung unter reeller Vorher­sage von Sprün­gen (MATCH+ mit Load/Store Reor­gan­i­sa­tion)
    • Sprungvorher­sage Genauigkeit (%)
    • Bench­markpro­gramme und ihre Sim­u­la­tion­sin­for­ma­tio­nen
    • Effek­tiv­itätssteigerun­gen geg­nüber sta­tis­chem Sched­ul­ing

1. Ein­führung

Da die Anzahl der par­al­lel aus­führbaren Befehle in einem Basic-Block (Befehle zwis­chen zwei Sprün­gen) klein ist, müssen super­skalare Prozes­soren über diese Block­gren­zen hin­auss­chauen, um die Leis­tung zu erhöhen. In numerischem Code kön­nen Schleifen, welche eine große Prozentzahl aller aus­ge­führten Sprünge aus­machen, früh erkan­nt und die Par­al­lelität erhöht wer­den. Da jedoch viele der Sprünge in nicht numerischem Code daten­ab­hängig sind, kön­nen diese nicht frühzeit­ig vorherge­sagt wer­den. Deshalb ist speku­la­tive Aus­führung von Befehlen eine wichtige Quelle von Par­al­lelität in dieser Art von Code.

Befehlspar­al­lelität erre­icht man sta­tisch (zur Com­pilezeit) oder dynamisch (zur Laufzeit). Sta­tis­ches Sched­ul­ing erre­icht man mit einem gerin­gen Hard­wareaufwand durch Berück­sich­ti­gung der Par­al­lelität im Befehlssatz. Für numerische Pro­gramme benutzt der Com­pil­er Tech­niken wie z.B. Soft­warepipelin­ing um effizien­ten Code zu erzeu­gen, was bei nicht numerischen Pro­gram­men nicht zum gewün­scht­en Ergeb­nis führt. Dynamisch geschedulte super­skalare Prozes­soren hinge­gen benöti­gen einen großen (und damit teuren) Hard­wareaufwand um effek­tiv zu arbeit­en.

Um die Leis­tung nicht numerisch­er Pro­gramme mit vernün­fti­gen Hard­warekosten zu erhöhen, wird eine super­skalare Architek­tur vorgestellt (TORCH genan­nt), die die Vorteile sta­tis­chen und dynamis­chen Sched­ul­ings vere­int. Der Vorteil sta­tis­chen Sched­ul­ings liegt in der Fähigkeit des Com­pil­ers Befehle über viele Basic-Blocks hin­weg zu Sched­ulen. Deshalb wird das Befehlss­ched­ul­ing bei TORCH vom Com­pil­er aus­ge­führt. Der Vorteil von dynamis­chem Sched­ul­ing ist die Fähigkeit der speku­la­tiv­en Aus­führung von Befehlen. Darum hat TORCH Hard­ware, die die Aus­führung von Befehlen vor dem Sprung erlaubt, die erst nach dem Sprung aus­ge­führt wür­den, eine Oper­a­tion die hier Boost­ing genan­nt wird. Boost­ing macht agres­sives Sched­ul­ing im Com­pil­er ein­fach, da Neben­ef­fek­te, die von den bed­ingten Sprün­gen abhän­gen, umgan­gen wer­den.

Um effizient zu boost­en, enthält die TORCH Hard­ware zwei Schat­ten­struk­turen: das shad­ow Reg­is­ter­file und den shad­ow Store­buffer. Diese Struk­turen puffern die Neben­ef­fek­te geboost­eter Befehle bis die zuge­höri­gen Sprünge abgear­beit­et sind. Bei einem kor­rekt vorherge­sagten Sprung akzep­tiert die Hard­ware die entsprechen­den Ergeb­nisse in den Schat­ten­struk­turen. Bei inko­r­rekt vorherge­sagten Sprün­gen garantiert die Hard­ware kor­rek­te Ergeb­nisse durch ver­w­er­fen der nicht benötigten Ergeb­nisse geboost­eter Befehle.


2. Speku­la­tive Aus­führung von Befehlen

Speku­la­tive Aus­führung ist notwendig, da bed­ingte Sprünge eine Aus­führungsab­hängigkeit der nach­fol­gen­den Befehle aufzwin­gen. Zum Beispiel sind die Befehle in den THEN und ELSE Teilen eines IF Befehles abhängig von der IF Bedin­gung, da wir nicht her­aus­find­en kön­nen, ob der THEN oder ELSE Befehl aus­ge­führt wer­den soll, bis die Bedin­gung der IF Anweisung getestet wurde. Speku­la­tive Aus­führung erlaubt die Aus­führung des THEN und/oder ELSE Befehles vor der Über­prü­fung der Bedin­gung der IF Anweisung.

2.1 Sichere Aus­führung speku­la­tiv­er Befehle

Speku­la­tive Aus­führung erhält jedoch lei­der nicht immer die Kor­rek­theit eines Pro­grammes, so daß man 4 Arten von speku­la­tiv­er Aus­führung unter­schei­den muß.

  
Abbil­dung: Typen speku­la­tiv­er Aus­führung
Typen

Für einen speku­la­tiv­en Befehl kann ein Sprung entwed­er kor­rekt oder falsch vorherge­sagt wer­den. Einen Sprung nen­nt man für einen speku­la­tiv­en Befehl kor­rekt vorherge­sagt, wenn der Block von der der speku­la­tive Befehl geboost­et wurde, nach dem Sprung aus­ge­führt wird. Andern­falls nen­nt man den Sprung falsch vorherge­sagt. Einen speku­la­tiv­en Befehl nen­nt man ille­gal, wenn diese Oper­a­tion einen Wert über­schreibt, der benötigt wird, wenn der Sprung falsch vorherge­sagt ist (Bild 1b). Unsich­er nen­nt man einen speku­la­tiv­en Befehl, wenn dieser eine Excep­tion verur­sachen kann. Diese Excep­tion sollte nur auftreten, wenn der Sprung kor­rekt vorherge­sagt ist (Bild  1c [address-exception]). Offen­sichtlich kann ein speku­la­tiv­er Befehl unsich­er und ille­gal sein (Bild  1d). Zur kor­rek­ten Pro­gram­maus­führung soll­ten nur sichere und legale speku­la­tive Befehle aus­ge­führt wer­den, was durch sta­tis­ches Sched­ul­ing erre­icht wird. Ein Com­pil­er kann zwar manche ille­gale speku­la­tive Befehle, durch Ver­wen­dung ander­er Reg­is­ter, die nicht zu Kon­flik­ten führen, in legale speku­la­tive Befehle umwan­deln, jedoch nicht unsichere in sichere. Deshalb wird Hard­ware­un­ter­stützung benötigt. Die Basis der momen­tan ver­wen­de­ten Tech­niken beruht auf der Hard­ware­puffer­ung der Effek­te speku­la­tiv­er Befehle.

Der sequen­zielle Sta­tus der Mas­chine ist definiert als der Maschi­nen­sta­tus, der nicht ein Ergeb­nis eines speku­la­tiv­en Befehles ist. Der speku­la­tive Sta­tus demzu­folge der Maschi­nen­sta­tus, der das Ergeb­nis eines speku­la­tiv­en Befehles ist. Die Puffer­ung tren­nt den sequen­ziellen und speku­la­tiv­en Sta­tus und gewährt einen Auf­schub der speku­la­tiv­en Neben­ef­fek­te bis der Sprung/die Sprünge aus­ge­führt wurde(n). Wenn alle Sprünge von denen ein speku­la­tiv­er Befehl abhängt aus­ge­führt wur­den, müssen Hard­ware­mech­a­nis­men den sequen­ziellen Sta­tus der Mas­chine mit den speku­la­tiv­en Effek­ten dieses Befehles aktu­al­isieren, andern­falls ver­wirft die Mas­chine ein­fach den speku­la­tiv­en Sta­tus und Neben­ef­fek­te des Befehles.

   
2.2 Boost­ing

Eine Boost­ing Architek­tur enthält Hard­ware­puffer, die unsichere und ille­gale speku­la­tive Befehle in sichere und legale umwan­delt. Weit­er­hin behan­delt Boost­ing alle Aspek­te von Excep­tion­han­dling durch die Bere­it­stel­lung eines Excep­tion­mech­a­nis­muss­es für alle Oper­a­tio­nen.

Nur die Hard­ware kann effek­tiv alle Effek­te ein­er speku­la­tiv­en Oper­a­tion puffern. Damit die Boost­ing­hard­ware sich­er­stellen kann, daß die Seman­tik des Pro­grammes nicht verän­dert wird, muß der Com­pil­er seine Annah­men der Hard­ware mit­teilen. Deshalb betitelt der Com­pil­er jeden speku­la­tiv­en Befehl als geboost­eten Befehl. Diese Betitelung kodiert die benötigten Infor­ma­tio­nen, so daß die Hard­ware unter­schei­den kann, wann die Effek­te eines geboost­eten Befehles nicht länger speku­la­tiv sind. Die Betitelung zeigt von welchem Sprung der geboost­ete Befehl abhängt und welch­es die vorherge­sagte Sprun­grich­tung ist. Im Beispiel in Bild  2 zeigt ein “.B” an, daß es sich um einen geboost­eten Befehl han­delt, wobei ein ange­hängtes “R” oder “L” die Sprun­grich­tung angibt, von der der geboost­ete Befehl abhängt.

  
Abbil­dung 2: Beispiel geboost­eter Befehle
bsp_Boosting

Die all­ge­me­in­ste Art von Boost­ing benötigt Hard­ware expo­nen­tiell zum Bosst­in­glev­el, da für jeden Sprung­weg der speku­la­tive Sta­tus der Mas­chine benötigt wird. Um die Hard­ware auf einem vernün­fti­gen Niveau zu hal­ten, boost­et man nur Befehle der meist genutzten Rich­tung eines Sprunges (z.B. durch Pro­fil­ing, wird im fol­gen­den voraus­ge­set­zt). Dadurch kön­nen die Sprung­be­fehle die Vorher­sage­in­for­ma­tion (Sprung wird aus­ge­führt oder nicht) kodieren, und jed­er geboost­ete Befehl kann ein­fach anzeigen, daß er von den näch­sten n bed­ingten Sprün­gen abhängt (z.B. der 2. speku­la­tive Befehl in Bild  2 vere­in­facht sich von “.BRR” zu “.B2”). Um das ganze weit­er zu vere­in­fachen geht man davon aus, daß der geboost­ete Befehl kon­trol­lab­hängig von allen Sprün­gen ist, über die er geboost­et wurde. Durch Kodierung des Boost­in­glevels als Anzahl der kon­trol­lab­hängi­gen Sprünge kann die Hard­ware die Kon­trol­lab­hängigkeitsin­for­ma­tion rekon­stru­ieren. D.H. ein geboost­eter Befehl des Lev­els n is kon­trol­lab­hängig von der Aus­führung der näch­sten n bed­ingten Sprünge, und das Ergeb­niss des geboost­eten Befehles wird nur akzep­tiert, wenn alle n bed­ingten Sprünge kor­rekt vorherge­sagt wur­den. Diese Bedin­gung macht es ein­fach­er, die Boost­ing­in­for­ma­tio­nen zu kodieren und die Hard­ware zu bauen.

Speku­la­tive Excep­tions wer­den gepuffert bis fest­ste­ht, ob der Sprung kor­rekt vorherge­sagt wurde oder nicht. Je nach­dem wird dann der Befehl, der die Excep­tion verur­sachte, erneut aus­ge­führt und dadurch eine sequen­zielle Excep­tion aus­gelöst. Eine genauere Beschrei­bung speku­la­tiv­er Excep­tions befind­et sich in der Dok­torar­beit von M. D. Smith, Stan­ford Uni­ver­sität.


3. Notwendi­ge Hard­ware für Boost­ing

   
3.1 Kom­plette Unter­stützung von Boost­ing

In der MIPS Architek­tur, auf der hier Boost­ing auf­baut, sind 3 mögliche Neben­ef­fek­te zu beacht­en: ein Reg­is­ter wird beschrieben, ein Spe­icher­bere­ich wird beschrieben, oder eine Aus­nahme wird sig­nal­isiert. Deshalb wer­den Schat­ten­struk­turen für das Reg­is­ter­file und den Store­buffer benötigt (Aus­nah­me­be­hand­lung siehe Abschnitt 2.2).

Im ein­fach­sten Fall kann man sich die speku­la­tiv­en Teile der Schat­ten­struk­turen als Kopi­en der sequen­ziellen Teile vorstellen. In diesem Fall benötigt man jedoch für jeden Boost­in­glev­el einen eige­nen speku­la­tiv­en Hard­wa­reein­trag (Bild 3b). Obwohl diese Art des Boost­ings viel Hard­ware benötigt, ist sie ein­fach zu imple­men­tieren.

  
Abbil­dung 3: Ver­schiedene Reg­is­ter­filekon­fig­u­ra­tio­nen
divRegfileConfig

Da es aus­re­icht, die Dat­en lediglich logisch in den sequen­ziellen Zus­tand zu kopieren, kann man eine Tech­nik anwen­den, die ähn­lich zum Reg­is­ter­re­nam­ing ist. Für jedes sequen­zielle Reg­is­ter erzeugt man eine Liste beste­hend aus Reg­is­ter, Zäh­ler und einem Belegt-Bit, wobei der Zäh­ler­w­ert den Boost­in­glev­el angibt. Ein Boost­in­glev­el von 0 ist hier­bei der sequen­zielle Sta­tus. Bei einem geboost­eten Befehl wird ein freier Ein­trag als Belegt gekennze­ich­net und in den Zäh­ler wird der Boost­in­glev­el einge­tra­gen. In das Reg­is­ter kommt nach Abar­beitung des Befehles das Ergeb­nis. Nach einem Sprung wird jed­er Zäh­ler dekre­men­tiert, wobei darauf geachtet wer­den muß, daß der Zäh­ler des sequen­ziellen Reg­is­ters nur herun­tergezählt wird, wenn der Boost­in­glev­el 1 Dat­en enthält (Belegt-Bit geset­zt). Enthält er diese nicht, bleibt der Zäh­ler des sequen­ziellen Reg­is­ters auf 0 und das Belegt-Bit des Boost­in­glevels 1 wird gelöscht.

   
3.2 Par­tielle Unter­stützung von Boost­ing

Da die kom­plette Unter­stützung von Boost­ing einen nicht uner­he­blichen (und damit teuren) Hard­wareaufwand mit sich bringt, lohnt es sich mehrere Optio­nen der par­tiellen Unter­stützung von Boost­ing anzuse­hen.

In Option 1 wird der speku­la­tive Store­buffer ent­fer­nt. Somit kann der Sched­uler keine Spe­icher­be­fehle boost­en, was auch Berech­nun­gen bein­hal­tet, welche ein Ergeb­nis aus dem Spe­ich­er laden, welch­es vorher durch einen anderen Befehl dort gespe­ichert wird. Unter der Annahme, daß genug Reg­is­ter vorhan­den sind und der Com­pil­er einen effek­tiv­en Reg­is­ter­al­lo­ca­tor hat, soll­ten solche Abläufe sel­ten auftreten, weswe­gen die Ein­bußen dieser Ein­schränkung min­i­mal sein soll­ten.

In Option 2 wer­den die ver­schiede­nen speku­la­tiv­en Reg­is­ter­files in einem einzel­nen speku­la­tiv­en Reg­is­ter­file zusam­men­gelegt, welch­es in der Lage ist mehrere Bosst­in­glev­el zu hand­haben. Ohne einen unter­schiedlichen Spe­icher­platz für jeden möglichen Boost­in­glev­el beziehen sich r3.B1 und r3.B2 in Bild 3b auf den sel­ben physikalis­chen Spe­icher­platz. Der Com­pil­er muß deshalb Code für Bild 3c gener­ieren. Wenn diese Art der Abhängigkeit sel­ten auftritt, bzw. die geringe Über­lap­pung wie in Bild 3c aus­re­icht, dann soll­ten die Ein­bußen dieser Ein­schränkung eben­falls min­i­mal sein.

Option 2 reduziert sig­nifikant den Hard­wareaufwand, den man für mehrere Boost­in­glev­el benötigt. Sie braucht lediglich zwei Reg­is­ter, einen Zäh­ler und ein Valid-Bit für jedes sequen­zielle Reg­is­ter. Bild 4 zeigt wie die dafür benötigte Hard­ware ver­schal­tet ist.

  
Abbil­dung 4: Hard­ware der Option 2
hardwO2

Der Zäh­ler hand­habt den aktuellen Boost­in­glev­el des Wertes im speku­la­tiv­en Reg­is­ter. Dieser Zäh­ler wird jedes­mal dekre­men­tiert, wenn ein kor­rekt vorherge­sagter Sprung aus­ge­führt wird. Ste­ht der Zäh­ler auf eins und das Reg­is­ter enthällt kor­rek­te Dat­en wird beim näch­sten kor­rekt vorherge­sagten Sprung aus dem sequen­ziellen das speku­la­tive Reg­is­ter und umgekehrt. Diese Hard­ware imple­men­tiert den speku­la­tiv­en Sta­tus und fügt lediglich ein einzelnes Gat­ter dem Reg­is­terzu­griff­sp­fad hinzu.

In Option 3 wird das kom­plette speku­la­tive Reg­is­ter­file ent­fer­nt. Um trotz­dem Befehle boost­en zu kön­nen, wird die Pipelinekon­trolle erweit­ert, so daß der Sched­uler in den “Schat­ten” des bed­ingten Sprunges hinein boost­en kann. Dieses ist eigentlich eine Erweiterung von “squash­ing branch­es” bei denen Befehle in den dem Sprung nach­fol­gen­den Zyklen ver­wor­fen wer­den, wenn der Sprung falsch vorherge­sagt wurde. Hier wer­den in solchen Fällen jedoch lediglich geboost­ete Befehle ver­wor­fen. Dieses erfordert den ger­ing­sten Hard­wareaufwand, hat jedoch die größten Restrik­tio­nen.


4. TORCH

TORCH basiert auf der MIPS R2000 RISC Architek­tur. Wie der R2000 benutzt TORCH verzögerte Sprünge um die Latenz zwis­chen der Aus­führung des Sprunges und dem Fetchen des ersten Befehles des Sprungzieles zu min­imieren. Weit­er­hin codiert TORCH die sta­tis­che Sprungvorher­sagen­for­ma­tion in jeden bed­ingten Sprung. Die Sprungvorher­sage in TORCH basiert auf Sprung-Profile-Statistiken, weil die Genauigkeit der Sprungvorher­sage direk­ten Ein­fluß auf die Leis­tung hat. Pro­fil­ing zeigt den meist genutzten Sprungp­fad, dessen Befehle von TORCH um lediglich einen Lev­el geboost­et wer­den. Außer­dem min­imiert bei TORCH der Com­pil­er die Effek­te unsicher­er Befehle durch Reg­is­ter­bele­gung während dem Befehlss­ched­ul­ing.

4.1 Hard­ware

TORCH beste­ht aus zwei Ein­heit­en, eine für Integer- und Logik­op­er­a­tio­nen und eine für Fließkom­ma­berech­nun­gen. Bei­de enthal­ten jew­eils eine Schat­ten­struk­tur, welche aus dem sequen­ziellen und dem speku­la­tiv­en Reg­is­ter­file beste­ht, wobei jedes Reg­is­ter­file den entsprechende Sta­tus der Mas­chine enthält. Befind­et sich ein Befehl ger­ade in der Pipeline wenn die Bedin­gung des dazuge­höri­gen Sprunges fest­ste­ht, so wird, wenn der Sprung kor­rekt vorherge­sagt wurde, das Ziel des geboost­eten Befehles das sequen­zielle Reg­is­ter, oder wenn es falsch vorherge­sagt wurde wird der Befehl ver­wor­fen. Desweit­eren existiert ein shad­ow Store­buffer, welch­er einen sequen­ziellen und einen speku­la­tiv­en Teil enthält. Dieser ist für die speku­la­tive Aus­führung von Schreibzu­grif­f­en auf den Spe­ich­er zuständig

  
Abbil­dung 5: Block Dia­gramm der TORCH Hard­ware
TORCH

5. MATCH

MATCH basiert auf ein­er Studie von M. John­son.

5.1 Hard­ware

MATCH ist sehr ähn­lich zu TORCH. Da MATCH jedoch das Befehlss­ched­ul­ing mit sein­er Hard­ware erledigt, ist der kom­plex­este Teil von MATCH seine Kon­trol­logik, welche in Bild 6 nicht zu sehen ist.

Vor jed­er Funk­tion­sein­heit gibt es eine Reservation-Station, welche zusam­men mit ihrer Kon­trol­logik die Out-of-Order Aus­führung ermöglicht. Außer­dem enthält MATCH noch einen Reorder-Buffer für die In-Order-Completion. Desweit­eren wird noch ein Banch-Tar­get-Buffer einge­set­zt, um bed­ingte Sprünge zu beschle­u­ni­gen, wobei hier Verzögerun­gen durch Befehls-misalignment nicht ver­hin­dert wer­den kön­nen.

  
Abbil­dung 6: Block Dia­gramm der MATCH Hard­ware
MATCH

6. Mes­sun­gen

Im weit­eren wird davon aus­ge­gan­gen, daß ide­ale Caches und effek­tive Reg­is­terum­be­nen­nung bei­de Prozes­soren in gle­ich­er Weise bee­in­flussen. Deshalb gehen wir hier der Ein­fach­heit hal­ber von diesen ide­alen Bedin­gun­gen aus. Desweit­eren wird davon aus­ge­gan­gen, daß die Fetch­ef­fek­tiv­ität und nicht die Anzahl der Funk­tion­sein­heit­en auss­chlaggebend für die ILP in nicht numerischen Pro­gram­men ist.

Bei­de super­skalare Prozes­soren haben zwei ALU’s und jew­eils eine Funk­tion­sein­heit nach Tabelle 1, deren Charak­ter­is­ti­ka eben­falls in Tabelle 1 beschrieben ist.

 
Tabelle: Ausführungs- und Ergeb­nis­latenz
Funk­tion­sein­heitAus­führungs­latenzErgeb­nis­latenz
 (Zyklen)(Zyklen)
Inte­ger ALU11
Bar­rel Shifter11
Load Pipe12
Store Pipe1-
Branch Unit12
FP Addier­er12
FP Mul­ti­plizier­er15
FP Divi­dier­er119
FP Kon­vert­er12

 

Tabelle 2 beschreibt die für den Bench­mark ver­wen­de­ten Pro­gramme, welche alle durch den Com­pil­er hochop­ti­miert wur­den, und nicht FPU-intensiv sind.

 
Tabelle 2: Benutzte Pro­gramme
Pro­gramm­nameSta­tis­cheDynamis­cheBeschrei­bung
 BefehleBefehle 
awk26,9K60,7Mpat­tern scanning/processing
ccom58,1K19,4Mfront-end of a C com­pil­er
espres­so43,6K340,5Mlog­ic miniza­tion
irsim89,4K54,3Msim­u­la­tor for VLSI lay­outs
latex53,2K100,6Mdoc­u­ment prepa­ra­tion sys­tem

 

6.1 Ergeb­nisse

Alle Ergeb­nisse zeigen die Geschwindigkeitssteigerung gegenüber einem skalaren Prozes­sor. Um eine Ref­erenz zu haben, zeigt Tabelle 3 die max­i­male the­o­retis­che Geschwindigkeitssteigerung die erre­icht wer­den kann, wenn Load/Store Befehle der einzige Flaschen­hals des Befehlss­ched­ul­ings ist. Berech­net wurde dies durch:

ser_clock/dyn_load_store

D.h. das Fetchen von 2 – 4 Befehlen pro Takt reicht aus, um das the­o­retis­che Max­i­mum an Geschwindigkeitssteigerung zu erre­ichen. Deshalb wer­den bei TORCH und MATCH lediglich zwei oder vier Befehle pro Zyk­lus gefetcht.

 
Tabelle: Max­i­male the­o­retis­che Geschwindigkeitssteigerung basierend auf Load/Store Häu­figkeit
awkccomespres­soirsimlatex$phi$
3,913,034,192,842,883,28

 

6.2 Berech­ti­gung von Boost­ing

Um Boost­ing richtig ein­schätzen zu kön­nen, zeigt Tabelle 4 die Geschwindigkeitssteigerung die durch herköm­lich­es sta­tis­ches Sched­ul­ing erre­icht wird.

 
Tabelle 4: Geschwindigkeitssteigerung (TORCH) nur durch Basic Block Sched­ul­ing
 awkccomespres­soirsimlatex$phi$
Fetch 21,171,111,221,111,191,16
Fetch 41,171,111,221,121,211,16
1 IPC1,191,231,081,271,131,18
unbe­gren­zt1,241,321,351,241,411,31

 

Die Dat­en der Zeilen Fetch 2 und Fetch 4 (welche die Anzahl der gefetcht­en Befehle pro Takt angeben) zeigen, daß diese nicht-numerischen Pro­gramme keine großen Abhängigkeit­en inner­halb der Basic-Blöcke (BB) haben. Außer­dem zeigten sie, daß in den Pro­gram­men die ILP inner­halb der BB sehr ger­ing ist, und so schon das Fetchen von nur zwei Befehlen aus­re­icht. Zeile 3 zeigt, daß BB-Scheduling in etwa mit der Aus­führung von einem Befehl pro Zyk­lus kor­re­spondiert.

Die let­zte Zeile in Tabelle 4 zeigt die max­i­mal mögliche Geschwindigkeitssteigerung der Pro­gramme, wenn der Prozes­sor unendliche viele Funk­tion­sein­heit­en hätte und man unendlich viele Befehle gle­ichzeit­ig Fetchen kön­nte.

6.3 Ver­gle­ich von TORCH und MATCH

Um bei­de super­skalaren Prozes­soren ver­gle­ichen zu kön­nen, wird davon aus­ge­gan­gen, daß sie die Sprungvorher­sage gle­ich hand­haben. Weit­er­hin wird in Tabelle 5 davon aus­ge­gan­gen, daß alle bed­ingten Sprünge genom­men wer­den (d.h. es wird gesprun­gen).

 
Tabelle: Geschwindigkeitssteigerung bei kor­rekt vorherge­sagten Sprün­gen (MATCH+ mit Load/Store Reor­gan­i­sa­tion)
 awkccomespres­soirsimlatex$phi$
Fetch 2      
TORCH1,421,371,611,451,441,45
MATCH1,341,281,451,311,341,34
MATCH +1,541,461,581,511,481,51
Fetch 4      
TORCH1,451,411,691,531,491,51
MATCH1,401,371,581,431,401,43
MATCH +1,731,711,881,731,701,75

 

Wie man in Tabelle 5 sieht, ist sta­tis­ches Sched­ul­ing mit Boost­ing effek­tiv­er als dynamis­ches Sched­ul­ing. Wenn zwei Instruk­tio­nen pro Takt gefetcht wer­den kommt dieser Effek­tiv­itätsvorteil daher, daß der Com­pil­er in der Lage ist, Befehle im Spe­ich­er auszuricht­en und somit Befehlsmisalign­ment ver­hin­dert wird. Außer­dem lim­i­tiert ein klein­er Fetch­block in MATCH auch das Befehls­fen­ster und somit das dynamis­che Sched­ul­ing. Obwohl ein größer­er Fetch­block diese Effek­te reduziert, ist TORCH trotz­dem schneller.

Da der Sched­uler in TORCH lediglich einen einzi­gen Boost­in­glev­el zuläßt und der Com­pil­er noch verbessert wer­den kann, läßt sich die Effek­tiv­itätssteigerun­gen von TORCH gegenüber dem skalaren Prozes­sor noch erhöhen, außer­dem wurde in TORCH noch keine Load/Store Reor­gan­i­sa­tion (Pri­or­isierung von Load Befehlen zur effek­tiv­eren Aus­las­tung von Funk­tion­sein­heit­en) imple­men­tiert.

 
Tabelle: Geschwindigkeitssteigerung unter reeller Vorher­sage von Sprün­gen (MATCH+ mit Load/Store Reor­gan­i­sa­tion)
 awkccomespres­soirsimlatex$phi$
Fetch 2      
TORCH1,491,521,701,551,551,56
MATCH1,411,411,511,401,421,43
MATCH +1,631,591,621,631,611,62
Fetch 4      
TORCH1,521,571,791,641,631,63
MATCH1,481,501,661,531,491,53
MATCH +1,861,971,971,941,951,94

 

Wenn man real­is­tis­che Sprungvorher­sagetech­niken zuläßt, kommt man zu Ergeb­nis­sen wie in Tabelle 6, wobei in Tabelle 7 die Genauigkeit der Sprungvorher­sage abge­le­sen wer­den kann. Hier­bei ist der Branch-Target-Buffer in MATCH ein assozia­tiv­er 4‑Wege Puffer mit 2048 Ein­trä­gen.

 
Tabelle 7: Sprungvorher­sage Genauigkeit (%)
 awkccomespres­soirsimlatex$phi$
Pre­dict Take79,368,577,675,666,873,2
BTB87,180,880,088,181,583,4
Pro­fil­ing91,092,686,992,190,690,6

 

6.4 Ver­gle­ich ver­schieden­er Boost­in­gop­tio­nen

Im fol­gen­den wer­den die Pro­gramme und Sim­u­la­tion­sin­for­ma­tio­nen aus Tabelle 8 ver­wen­det. Die Geschwindigkeitssteigerung gegenüber einem MIPS R2000 wird durch

r2000/super


definiert.

 
Tabelle 8: Bench­markpro­gramme und ihre Sim­u­la­tion­sin­for­ma­tio­nen
 Total R2000Avg. R2000Branch
 CyclesIPCPre­dic­tion Accu­ra­cy
awk47,2M0,8982,0%
com­press29,3M0,8782,7%
eqn­tott0,7M0,9572,1%
espres­so97,8M0,8975,7%
grep28,6M0,8197,9%
nroff66,4M0,8296,7%
xlisp1,0M0,8983,5%

 

Tabelle 9 zeigt Effek­tiv­itätssteigerun­gen ver­schieden­er Boost­in­gop­tio­nen in Prozent, nor­mal­isiert zu dem ein­fachen super­skalaren Prozes­sor ohne Boost­ing jedoch mit sta­tis­chem Befehlss­ched­ul­ing.

 
Tabelle: Effek­tiv­itätssteigerun­gen geg­nüber sta­tis­chem Sched­ul­ing
 Squash­ingBoost1MinBoost3Boost7
awk11,2%16,4%17,2%18,1%
com­press9,1%10,6%10,6%10,6%
eqn­tott8,0%14,4%16,0%16,0%
espres­so9,8%18,0%21,3%23,0%
grep15,4%27,7%40,8%40,8%
nroff11,4%24,4%31,7%36,6%
xlisp6,7%13,3%12,5%14,2%
G.M9,9%17,0%19,3%20,5%

 

Squash­ing ist hier­bei die unter Abschnitt 3.2 beschriebene Option 3, welche keine Schat­ten­struk­turen enthält und somit die kaum Zusatzhard­ware enthält.

Boost1 entspricht der Boost­ing­hard­ware in TORCH.

MinBoost3 erlaubt in einem Reg­is­ter­file Boost­ing über 3 Sprünge hin­weg und entspricht Option 2 in Abschnitt 3.2.

Boost7 erlaubt einen unlim­i­tierten Boost­in­glev­el von 7 und entspricht der Hard­ware von Abschnitt 3.1. Da Boost7 lediglich eine ver­nach­läs­sig­bare Geschwindigkeitssteigerung gegenüber Boost1 und MinBoost3 bringt und dazu noch einen großen Hard­wareaufwand erfordert, hat diese Imple­men­ta­tion ein schlecht­es Preis/Leistungsverhältnis.

Der Dekoder ein­er Boost1 Mas­chine mit 32 sequen­tiellen Reg­is­tern enthält nur 33% mehr Tran­si­s­toren als ein nor­maler Dekoder für 64 Reg­is­ter (50% mehr Tran­si­s­toren für eine MinBoost3).

6.5 Ver­gle­ich von MinBoost3 mit einem dynamis­chen Sched­uler

  
Abbil­dung: Effek­tiv­itätsver­gle­ich mit einem dynamis­chen Sched­uler
vgDyn

Bild 7 ver­gle­icht MinBoost3 mit einem dynamis­chen Sched­uler, da MinBoost3 das beste Preis/Leistungsverhältnis der ver­schiede­nen Imple­men­tierungsmöglichkeit­en hat. Der dynamis­che Sched­uler fetcht und dekodiert zwei Befehle pro Zyk­lus, hat ins­ge­samt 30 Plätze in den Reservation-Stations und 16 Ein­träge im Reorder­buffer um speku­la­tive Out-of-Order Aus­führung zu ermöglichen. Desweit­eren benutzt er einen assozia­tiv­en 4‑Wege Branch-Target-Buffer mit 2048 Ein­trä­gen.

Die untere Hälfte des Balkens bei MinBoost3 zeigt die Geschwindigkeitssteigerung wenn Reg­is­ter vor dem Befehlss­ched­ul­ing alloziert wer­den. Die obere Hälfte repräsen­tiert ein Mod­el mit unendlich vie­len Reg­is­tern. Bei dem dynamis­chen Sched­uler zeigt die untere Hälfte die Effek­tiv­ität ohne, die obere Hälfte mit Reg­is­terum­be­nen­nung.

Wie man sieht, erre­icht man schon mit gerin­gen Kosten eine hohe Effek­tiv­ität.

Send to Kin­dle