Trace Cache - Vor- und Nachteile?

[CrazyIvan]

Na dann lasst mal was hören ^^

[GloomY]

Ein Trace Cache (http://www-ti.informatik.uni-tuebingen.de/~heim/lehre/seminar_ws0001/martin/tc_html/node3.html) speichert Folgen von bereits dekodierten Instruktionen, die bei der Programmabarbeitung zusammenhängen. Dabei werden die einzelnen Einträge des Caches (auch Traces genannt) aus Blöcken gebildet, in denen selbst keinerlei Programmverzweigung vorkommt. Diese Blöcke können also ohne weiteres sofort nacheinander abgearbeitet werden. Die Befehle müssen also nur innerhalb eines Blockes nacheinander im Speicher liegen. Die Blocks selbst können beliebige Anfangsadressen beinhalten. Damit lassen sich eben Programmabarbeitungsfolgen speichern, also soetwas wie

Stück1 - Sprungs an Adresse x - Stück2 - kein Sprung - Stück3 - kein Sprung - Stück 4 - Sprung an Adresse y - Stück5 usw.

Ein weiterer Trace kann dann z.B. als ersten Block die Befehle enthalten, die nach Stück 1 kommen, so dass wenn der erste Sprung nicht genommen werden sollte, die Befehle aus diesem Trace genommen werden können.

http://www.realworldtech.com/includes/images/articles/Willamette-pt2-fig1.gif http://www.realworldtech.com/includes/images/articles/Willamette-pt2-fig2.gif

Der Vorteil liegt darin, dass häufig durchlaufene Programmabfolgen im Trace Cache liegen, während seltene oder gar nicht durchlaufene entweder gar nicht drin sind oder mit der Zeit entfernt werden. Dadurch dass die Intruktionen schon in dekodierter Form vorliegen, spart man sich teilweise mehrere Pipelinestufen der Dekodierung, wenn der Cache trifft. Besonders bei langen Pipelines, die bei einem falsch vorhergesagten Sprung eine große Anzahl an Stufen löschen müssen und damit auch eine große Anzahl an Takten verlieren, hilft das besonders viel.


Der Nachteil stellt natürlich die erhebliche Platznutzung durch die schon dekodierten Befehle da, die in ISA-Form natürlich weitaus weniger Platz einnehmen (besonders bei x86). Die Frage stellt sich daher, in wie weit es sinnvoll ist, einen Trace Cache als Ersatz für einen normalen Instruktion-Cache herzunehmen. Als Zusatz zu einem bereits bestehenden I-Cache ist ein Trace Cache aber sicherlich eine feine Sache. :)

[saaya]

wenn ein Mod in ROT etwas editiert, dann hat das einen Grund. Der Grund hier war, solche Postings wie dieses als SPAM aufgefasst werden. Wenn du einen solchen Hinweis dann wieder wegeditierst und durch den selben Spam ersetzt kann man das als Missachtung der Moderation auffassen. Ich bitte daher darum, solche Hinweise ernst zu nehmen, da es sonst Konsequenzen hat

[CrazyIvan]

@ GloomY
Der Trace Cache ist also dem Instruction Cache nachgelagert und sitzt somit irgendwo zwischen dem L1 und den Registern?

Irgendwie klingt das für mich nur nach einer alternativen Herangehensweise an das Problem der Verzweigungen zu Predication, oder ist dem nicht so? Könnte man vielleicht beides kombinieren?

[StefanV]

die Kurzversion:

Der Vorteil vom Trace Cache ist, daß die gespeicherten Befehle dadrin nicht mehr durch den Decoder müssen.

Der Nachteil hingegen ist, daß da nicht wirklich viel reinpasst und das der Durchsatz begrenzt ist (beim P4).

Ich denke nicht, daß es wirklich Sinn macht, den I-Cache durch einen Trace Cache zu ersetzen, da man in einem normalen I-Cache, bei gleicher Spechermenge/gleichem Platz auf dem DIE, deutlich mehr reinbekommt...

[zeckensack]

Der Vorteil liegt darin, dass häufig durchlaufene Programmabfolgen im Trace Cache liegen, während seltene oder gar nicht durchlaufene entweder gar nicht drin sind oder mit der Zeit entfernt werden.Das ist bei einem konventionellen L1-I-Cache auch der Fall. Dadurch dass die Intruktionen schon in dekodierter Form vorliegen, spart man sich teilweise mehrere Pipelinestufen der Dekodierung, wenn der Cache trifft.Auch wahr. Allerdings spart man eben nur Stufen, man spart aber keine Logik. Die Decoder-Logik kann nicht eingespart werden, weil man sonst den Trace Cache nicht füttern könnte.Besonders bei langen Pipelines, die bei einem falsch vorhergesagten Sprung eine große Anzahl an Stufen löschen müssen und damit auch eine große Anzahl an Takten verlieren, hilft das besonders viel.Mein Reden. Der einzige greifbare Vorteil eines Trace Caches liegt darin, dass er bei ohnehin dubiosen Pipeline-Längen ein paar Takte spart, wenn ein Branch nicht getroffen werden konnte. Btw, je länger der Teil der Pipeline nach dem Trace Cache ist, desto weniger nützt (relativ gesehen) der Trace Cache ...

Ansatzpunkt #1 sollte sein, die Branch prediction zu verbessern. #2 ist die möglichst sinnvolle Wahl der Pipeline-Länge. Wenn man das gemacht hat, braucht man keinen Trace Cache mehr.

Auch in konventionellen L1-Caches kann man nebenher Predecode-Bits uä speichern, dies wurde bereits im K7 so implementiert. Dabei profitiert man allerdings nach wie vor von der hohen Code-Dichte der x86-ISA, und braucht keine 100kiB SRAM, um 24 kiB Code zu speichern ...

Der Nachteil stellt natürlich die erhebliche Platznutzung durch die schon dekodierten Befehle da, die in ISA-Form natürlich weitaus weniger Platz einnehmen (besonders bei x86). Die Frage stellt sich daher, in wie weit es sinnvoll ist, einen Trace Cache als Ersatz für einen normalen Instruktion-Cache herzunehmen. Als Zusatz zu einem bereits bestehenden I-Cache ist ein Trace Cache aber sicherlich eine feine Sache. :)Auch das sehe ich natürlich ein wenig anders ...
Als Zusatz zu einem konventionellen L1-I-Cache ist ein Trace Cache völlig redundant. Mein Vorschlag wäre den Trace Cache gleich wieder rauszuschmeissen, und stattdessen stärkere Dekoderlogik zu implementieren. Das bringt mehr, und für mehr Code.

[BlackBirdSR]

Ich greife die Sache TraceCache hier mal gezielt in Verbindung zum P4 auf.
Denn sonst machen die folgenden Punkte ja wenig Sinn.

Wie schon gesagt wurde, spart man sich durch den TraceCache in vielen Fällen ca 8 Pipelinestufen. Je nachdem wie lang die gesamte Pipeline bis zum rausschmeissen der Befehle aus der Pipeline ist. Das kann einer CPU wie dem P4 schon helfen, wenn man statt 28 nur noch 20 kritische Stufen hat.
Intel lässt die Stufen vom Decoder zum TraceCache ja gerne weg.
(Wenn man bedenkt, dass Prescott somit bei ca 40 Stufen liegen könnte, wird einem mulmig)

Zeckensack&Gloomy, ihr sprecht die Sache mit dem Decoder und eventuell eingesparter Logik an.
Meines Wissens, verlangt ein TraceCache ebenso Logik als eine komplexe Decodereinheit. Die genauen Relationen sind mir nicht bekannt, aber eine einfache Schaltung ist es auf keinen Fall.
Was allerdings eingespart werden kann, ist wohl einer der HotSpots in den CPUs.
Während Ausführungseinheiten auch mal nichts tun, sind Decoder nahezu ständig am Ackern. Es entsteht nicht nur ordentlich Verlustleistung, Decoder sind höchtwahrscheinlich auch eine der Stellen wo man ordentlich Taktfrequenz liegen lassen kann. Beweise hab ich keine. Das wird halt hier und dort so allgemein angenommen.
Áuf das P4 Konzept angewandt, passt das natürlich perfekt.

Dann die Sache mit den Programmabfolgen. Es stimmt schon, dass oftmals benötigte Befehle in einem traditionellen L1 Cache ebenfalls enthalten sind. Allerdings gilt hier weiterhin die zeitl/räumliche Lokalität. Im TraceCache sind die Befehle zu Segmenten verbunden, welche genau so ablufen. Quasi ein Befehlsstrom der genau so und nicht anders ausgeführt wird. Ich denke da z.B an die Fast-ALUs die ja genau sowas brauchen.
Natürlich muss man Befehle abseits dieser Reihenfolge durchreichen. Funktioniert meistens auch ganz gut.

Den Trace Cache rauszuschmeissen halte ich beim P4 für falsch. Die CPU scheint einfach darauf angewiesen zu sein. Natürlich würde es ein normaler L1 Cache auch tun, bei so niedrigen Taktraten. Dann aber mit ein paar Modifikationen am Core, welche aus der MegaGHZ Maschine eher wieder eine CPU im Bereich der AMDs machen könnte. Und das wollte Intel ja nicht.
Was am Ende dabei rausgekommen ist, ist mir dabei gar nicht so wichtig.

[GloomY]

Das ist bei einem konventionellen L1-I-Cache auch der Fall.Ich habe fast schon erwartet, dass das jetzt kommt ;)

Es ist insofern etwas anderes, dass ein konventioneller L1 I-Cache komplette Speicherbereiche - eben ganze Cachelines - enthält, also auch Befehle, die nie oder nur ganz selten ausgeführt werden. Wenn bei den 64 Byte einer Cache Line eben fast immer nach z.B. den ersten 11 Byte woanders hingesprungen wird, sind die restlichen 53 Byte nicht wirklich sinnvoll gespeichert. Ähnlich verhält es sich, wenn der Speicherbereich, der durch die Cache Line abgedeckt wird, nur ein Einsprungziel "mitten drin" ist und der Rest davor (im Sinne von kleineren Adressen) nicht genutzt wird.

Ein Trace Cache speichert eben wirklich nur die Pfade, die auch wirklich benutzt werden/wurden. Eine räumliche Lokalität ist dort nicht vorhanden, ein weiterer Grund, warum ein Trace Cache alleine nicht wirklich sinnvoll ist. Man braucht eben ab und zu auch die "Umgebung", aber oft ist diese auch komplett unnütz.
Sicherlich nehmen die dekodierten Befehle mehr Platz weg, aber immerhin werden eben nicht eine Menge weiterer Befehle auf gut Glück gespeichert, nur weil diese eben auch in der "Umgebung" bereits genutzter Befehle liegen.
Auch wahr. Allerdings spart man eben nur Stufen, man spart aber keine Logik. Die Decoder-Logik kann nicht eingespart werden, weil man sonst den Trace Cache nicht füttern könnte.Man kann sie vielleicht reduzieren, weil man davon ausgehen kann, dass man recht häufig den TC trifft und nur selten direkt aus den Dekodern die Instruktionen erhalten muss. Wie BlackbirdSR richtig sagte, sind Dekoder ständig am Ackern (s.u.) und verbrauchen neben Strom auch noch eine ganze Menge Platz.

Natürlich muss man an dem Punkt auch vorsichtg sein und nicht zu viel wegrationalisieren.
Mein Reden. Der einzige greifbare Vorteil eines Trace Caches liegt darin, dass er bei ohnehin dubiosen Pipeline-Längen ein paar Takte spart, wenn ein Branch nicht getroffen werden konnte. Btw, je länger der Teil der Pipeline nach dem Trace Cache ist, desto weniger nützt (relativ gesehen) der Trace Cache ...

Ansatzpunkt #1 sollte sein, die Branch prediction zu verbessern. #2 ist die möglichst sinnvolle Wahl der Pipeline-Länge. Wenn man das gemacht hat, braucht man keinen Trace Cache mehr.Selbst bei moderaten Pipelinelängen wie der des A64/Opterons braucht man immerhin 10 Stufen, bis das Ergebnis durch die ALU berechnet wurde. D.h. die Branch Miss Penalty beträgt mindestens eben diese 10 Takte. Wenn man dann 2 oder vielleicht sogar drei Takte durch einen TC einsparen kann, dann ist das ein nicht zu verachtender Anteil (20 bzw. 30%). Eine Größenordnung, bei der es sich imho lohnt über solche Maßnahmen nachzudenken.

Sicherlich ist Branch Prediction eine ganz wichtige Sache, aber beides schließt sich ja nicht aus. :)
Auch in konventionellen L1-Caches kann man nebenher Predecode-Bits uä speichern, dies wurde bereits im K7 so implementiert. Dabei profitiert man allerdings nach wie vor von der hohen Code-Dichte der x86-ISA, und braucht keine 100kiB SRAM, um 24 kiB Code zu speichern ...Sind die 100 kiB eine offizielle Zahl?

edit: Naja, dürfte wohl etwa hinkommen. Btw: Der Athlon braucht für seine 64 kiB L1 I-Cache auch 102kiB realen Speicherplatz (predecoded Bits, Parity, Branch Selector).
Auch das sehe ich natürlich ein wenig anders ...
Als Zusatz zu einem konventionellen L1-I-Cache ist ein Trace Cache völlig redundant. Mein Vorschlag wäre den Trace Cache gleich wieder rauszuschmeissen, und stattdessen stärkere Dekoderlogik zu implementieren. Das bringt mehr, und für mehr Code.Noch stärker? Imho ist der Athlon64/Opteron (um den geht's doch?!) mit seinem riesigen Dekoder, der bis zu drei µOps/Takt liefer kann, wirklich gut ausgestattet. Laut Hans de Vries (http://www.chip-architect.com/news/2003_09_21_Detailed_Architecture_of_AMDs_64bit_Core.html#4.4) ist das schon ein ziemlicher Brute Force Ansatz, indem man in den 16 Bytes Code, die pro Takt untersucht werden, 16 verschiedene Anfangspunkte für die Dekodierung eines Befehls wählt. Für jeden Anfangspunkt tut man dann so, als ob das der Beginn eines neuen Befehls wäre (obwohl das beim Großteil natürlich falsch ist), dekodiert diese 16 Befehle alle parallel und sucht sich dann am Ende nur die richtigen raus.

Hans de Vries spricht (http://www.chip-architect.com/news/2002_06_24_Hammers_Two_Extra_PipelineStages.html) auch davon, dass der Durchsatz der Ausführungseinheiten im Schnitt deutlich weniger als 3 µOps / Takt ist, weil Abhängigkeiten, Cache Misses usw. dieses verhindern. Ich glaube nicht, dass es sinnvoll ist, hier noch mehr in die Dekoder zu investieren.

Der P4 (ja, ich weiss, der muss immer als schlechtes Beispiel dienen...) ist mit seinem Dekoder, der 1 µOp/Takt liefert, recht spärlich ausgestattet. Ich frage mich sowieso, wie das auf lange Zeit gutgehen soll, wenn das superskalare Back-End > 1 IPC ausführen möchte, aber der Dekoder nur einen Befehl pro Takt liefern kann. Da muss der TC ja mehrmals das Gleiche liefern. Bei Code, der wenig Schleifen enthält, kann das zu einem echten Engpass werden. Das Füllen des TCs geht mit einem µOp/Takt wohl auch sehr schleichend vorran...

[CrazyIvan]

Die Frage ist doch, was ein Trace Cache bei einer K8(ähnlichen) Architektur brächte. Wenn man von 10 - 15 Stufen ausginge und der Trace Cache irgendwo zwischen Stufe 1 und 6 hinge, dann könnte man also im besten Falle 5 Takte einsparen. Bezieht man aber eine geschätzte mittlere Richtigkeit der Sprungvorhersage von 95% (IMHO realistisch) ein, so mindert sich dieser Gewinn doch drastisch. Bleibt die Frage, ob man die Die Fläche nicht nützlicher für andere Sachen verwenden könnte. Demzufolge müsste ein Trace Cache umso überflüssiger sein, je besser die Branch Prediction ist?!

[zeckensack]

GloomY,
natürlich ist der K8 ein wichtiger Referenzpunkt, aber das ist nur die halbe Wahrheit.
Ich gehe davon aus, dass die Komplexität der Logik eben ausgewogen sein muß. Wenn man sich einen Trace Cache im Design leisten kann, dann hat man auf jeden Fall eine erhebliche Menge an Die-Fläche "übrig" (sonst könnte man sich den TC eben nicht leisten ...). Und dann stelle ich folgende Fragen auf:
1)wurden an anderer Stelle Kompromisse geschlossen, um den TC noch ins Budget zu bekommen? Waren das sinnvolle Kompromisse?
2)könnte man mit der Fläche/der Menge an Transistoren, die der TC verbraucht, nicht etwas besseres tun?

Zu 1) ist am Beispiel "Netburst" die vergleichsweise schwache Dekoderlogik zu erwähnen. Das ist glasklar ein Kompromiss der Trace Cache-Implementierung. Es stellt sich die Frage, ob der Trace Cache diesen Einschnitt exakt ausgleichen, oder mehr als ausgleichen kann. Die Argumentation ist natürlich, dass man, wenn man einen TC hat, keine stärkeren Decoder "braucht".

2)wie teuer wäre anstatt des Trace Caches 32kiB an konventionellem L1-I-Cache plus meinetwegen verdoppelter Dekoder-Logik wirklich gewesen? Hätte es nicht evtl gar zu einer vervierfachten "Overkill"-Dekoder-Logik gereicht? Oder, alternativ zum Overkill, zu einem letztlich kleineren Die?

So weit ich informiert bin, braucht der K8 für seine "Monster"-Decoder drei Pipeline-Stufen. Das ist lächerlich wenig. Darüber würde ich mir wirklich nicht den Kopf zerbrechen. Gute Branch-Prediction-Logik erreicht Trefferquoten von 95% oder mehr. Bei den restilchen 5% aller Branches (ergo ~0,75% von typischem Integer-Code) 25% an Waitstates einzusparen, bedeutet nach meiner Rechnung dass das Investitionsgrab "Trace Cache" einen Performancegewinn in der Größenordnung von 0,57% erwarten lässt.

Die Implementierung in "Netburst" mag durchaus eine grössere Wirkung zeigen, aber das beruht eben zu großen Teilen auf dem Gesamtdesign, mit unglaublich langen Pipelines, mit dem schwachen x86-Dekoder, und dem nicht vorhandenen L1-I-Cache.

Der Northwood, mit seinen 30 Stufen, durch und durch auf Takt getrimmt, und dafür mit einer enormen Die-Size "gesegnet", stößt bei ~3,5GHz bereits auf nahezu unüberwindbare thermische Hürden. Anhand einer so dermaßen unausgewogenen Fehlkonstruktion (<= dafür kriege ich bestimmt gleich auf die Fresse) möchte ich nicht über die universelle Sinnhaftigkeit von Architekturmerkmalen sinnieren. Sprich: wenn es beim Northwood viel bringt, bedeutet das nicht automatisch, dass es auch bei ausgewogenen Designs viel bringt.

Northwood, und Presscot erst recht, haben so enorme Transistor-Counts, dass die Einsparung des Trace Cache, bzw die äquivalente Ersetzung durch bewährte Architekturmerkmale vergleichsweise wenig Einfluß auf die Gesamtkosten pro Die gehabt hätten. Deswegen wird ein Trace Cache als Teil einer vernünftig dimensionierten Pipeline aber weder billiger, noch erstrebenswerter.

[BlackBirdSR]

GloomY,
Anhand einer so dermaßen unausgewogenen Fehlkonstruktion (<= dafür kriege ich bestimmt gleich auf die Fresse) m.

Ich kann nicht für Andere sprechen, aber zumindest von mir bekommst du dafür keine auf die Fresse.
Ultimativ ist der P4 nunmal eine Fehlkonstruktion in dem Sinne, dass es nicht annähernd das erreicht hat was er sollte.
Vielleicht wusste Intel nicht, dass die thermischen Grenzen so schnell erreicht werden (will und kann ich nicht glauben).
Vielleicht hat man bei Intel einfach gehofft ein Gegenmittel zu finden.
Am Ende zeigt sich jedoch, dass die Konstruktion nicht in der Lage ist, ohne extremen Aufwand, die Leistung noch zu steigern.

Prescott ist ein extremer Aufwand, und er hat die Leistung nicht wirklich gesteigert. Wenn NW noch halbwegs erfolgreich war, so ist Prescott sicherlich der Versuch mit dem Kopf gegen die Mauer zu rennen.

Selbst Intel gibt ja mehr oder weniger zu, dass man versagt hat.

[Lokadamus]

mmm...

Wenn ich mich richtig erinnere, hiess es damals in der ct, die Daten liegen als CISC vor und werden im Tracecache als RISC abgelegt => sie sind fertig und brauchen nur noch abgearbeitet werden, die Umwandlung entfällt.
Einen Nachteil sehe ich selber in der relativ geringen Grösse und dem niedrigen Output.
Wegen dem Design des P4, ich hab mir lange keine Pläne dazu angesehen, meine aber, das einige Sachen nicht dumm waren. Allerdings gibt es durch den schlechten Output des Tracecache einen fetten Flaschenhals, wodurch die restliche Technik stümperhaft wirkt ...

[BlackBirdSR]

mmm...

Wenn ich mich richtig erinnere, hiess es damals in der ct, die Daten liegen als CISC vor und werden im Tracecache als RISC abgelegt => sie sind fertig und brauchen nur noch abgearbeitet werden, die Umwandlung entfällt.

Allerdings gibt es durch den schlechten Output des Tracecache einen fetten Flaschenhals, wodurch die restliche Technik stümperhaft wirkt ...

Die Befehle liegen im Cache immer im x86 Format vor. Das war nunmal CISC.
Intern läuft es dann immer in den jeweiligen µOps weiter. Das läuft seit dem PentiumPro einfach so.
Der TraceCache ist allerdings quasi ein Sammelbehälter für eben jene µOps.
Normalerweise werden diese am Ende der Pipeline wieder rausgeschmissen und müssten den ganzen Weg nochmal nehmen.

Der Output des Trace-Cache ist allerdings kein so großes Problem wie viele gerne meinen. Klar klingen 3µOps/Takt (eigentlich 6µOps alle 2 Talkte) wenig vergleichen mit einem K7/8.
Allerdings muss man bedenken, dass selbst moderne x86 CPUs eigentlich nur ca 1.5-2µOps/Takt auch wirklich verarbeiten können.
Nur weil die CPU 7 oder gar 9 Ausführungseinheiten hat, muss das nicht heissen, dass diese auch versorgt werden können.
Ein Anhaltspunkt wären z.B die Ports, welche die Einheiten mit den Befehlen versorgen. Sie wären gar nicht in der Lage alle auf einmal zu versorgen.
Dann ist der TraceCache ja auch nicht direkt vor den Einführungseinheiten. Die Befehle müssen zuerst in den "Verteiler". Der kann 6µOps/Takt abschicken. Befehle werden auch nicht alle in einem Takt bearbeitet. Macnhmal ist eine Einheit nur in der Lage Befehle alle 2 Takte auszuführen. Dann sammeln sich µOps auch an.
Als weiter Punkt kommt hinzu, dass die dicken Brocken unter den Befehlen gar nicht erst in den TraceCache kommen. Sie würden diesen nur zumüllen und werden selten gebraucht. Sie werden also vom Microcode erzeugt.
Der TraceCache enthält also oft genutzt, eher simple Befehle.. man könnte denken ideal für die ALUs des P4.

Die große Frage ist, und das bleibt wohl den Simulationen von Intel vorbehalten: wie viel Nutzen bringt der TraceCache gegenüber einem L1 Cache?
Was mich persönlich interessieren würde:
Der TraceCache baut sich die Segmente selbst auf, (ein Grund warum ein Trace-Cache eine menge Logik benötigt) während ein Segment gebildet wird, kann auf dieses ja nicht zugegriffen werden. Der TC ist also in der Lage einen Befehl der gerade benutzt wurde und schon wieder gebraucht wird, einfach durchzuschleusen. Wie viel Gewinn würde ich erzielen, würde ich nur auf dieses Konzept setzen? Kein TC, nur eine Logik, die solche Befehle abfängt und erneut zur Verarbeitung weitergibt?

[CrazyIvan]

Der TraceCache baut sich die Segmente selbst auf, (ein Grund warum ein Trace-Cache eine menge Logik benötigt) während ein Segment gebildet wird, kann auf dieses ja nicht zugegriffen werden. Der TC ist also in der Lage einen Befehl der gerade benutzt wurde und schon wieder gebraucht wird, einfach durchzuschleusen. Wie viel Gewinn würde ich erzielen, würde ich nur auf dieses Konzept setzen? Kein TC, nur eine Logik, die solche Befehle abfängt und erneut zur Verarbeitung weitergibt?

Was genau meinst Du mit Durchschleusen? Für mich klingt das nur so, als würde man den Zugriff solange Loopen, bis auf das Segment wieder zugegriffen werden kann. Und wenn Du meinst, dass für dieses Segment bei sofortiger Benutzung keine Takte verschwendet werden, dann gäbe es doch auch keinen Unterschied zu einem "nicht vorhandenen" Trace-Cache. Damit wäre bewiesen, dass der Trace Cache zumindest keine Nachteile hätte. Allerdings bliebe dann immer noch die Frage nach den Vorteilen ob des hohen Transisistor Counts...

[micki]

Ich hab mal irgendwo gelesen, dass die absicht hinter dem einen decoder im p4 die war, dass man dafür sorgen wollte, dass manche einheiten nicht übermässig oft mit befehlen versorgt werden würden, weil sie probleme mit hotspots dort hatten und das eine einfache un billige lösung war.

MfG
micki

[GloomY]

Zeckensack, du hast mich fast überzeugt, auch wenn es da noch ein paar Sachen gibt, die man bedenken muß.
GloomY,
natürlich ist der K8 ein wichtiger Referenzpunkt, aber das ist nur die halbe Wahrheit.
Ich gehe davon aus, dass die Komplexität der Logik eben ausgewogen sein muß. Wenn man sich einen Trace Cache im Design leisten kann, dann hat man auf jeden Fall eine erhebliche Menge an Die-Fläche "übrig" (sonst könnte man sich den TC eben nicht leisten ...). Und dann stelle ich folgende Fragen auf:
1)wurden an anderer Stelle Kompromisse geschlossen, um den TC noch ins Budget zu bekommen? Waren das sinnvolle Kompromisse?
2)könnte man mit der Fläche/der Menge an Transistoren, die der TC verbraucht, nicht etwas besseres tun?

Zu 1) ist am Beispiel "Netburst" die vergleichsweise schwache Dekoderlogik zu erwähnen. Das ist glasklar ein Kompromiss der Trace Cache-Implementierung. Es stellt sich die Frage, ob der Trace Cache diesen Einschnitt exakt ausgleichen, oder mehr als ausgleichen kann. Die Argumentation ist natürlich, dass man, wenn man einen TC hat, keine stärkeren Decoder "braucht".

2)wie teuer wäre anstatt des Trace Caches 32kiB an konventionellem L1-I-Cache plus meinetwegen verdoppelter Dekoder-Logik wirklich gewesen? Hätte es nicht evtl gar zu einer vervierfachten "Overkill"-Dekoder-Logik gereicht? Oder, alternativ zum Overkill, zu einem letztlich kleineren Die?Vollkommen richtig. Man muss sich bei jeder Designentscheidung fragen, wie effizient das ganze ist und ob bessere Alternativen exisiteren, die die durchschnittliche Leistung erhöhen.
Wie BlackbirdSR richtig festgestellt hat, ist der TC wohl auch besonders gut für die Fast-ALU - also für spezielle Fälle - zu gebrauchen. Für den Rest und damit der allgemeinen Verwendung ist dieser eventuell schlechter geeignet als ein klassischer I-Cache, den man mit gleicher Die-Fläche realisieren könnte. Insofern ist diese Designentscheidung natürlich äußerst fraglich.
So weit ich informiert bin, braucht der K8 für seine "Monster"-Decoder drei Pipeline-Stufen. Das ist lächerlich wenig. Darüber würde ich mir wirklich nicht den Kopf zerbrechen. Gute Branch-Prediction-Logik erreicht Trefferquoten von 95% oder mehr. Bei den restlichen 5% aller Branches (ergo ~0,75% von typischem Integer-Code) 25% an Waitstates einzusparen, bedeutet nach meiner Rechnung dass das Investitionsgrab "Trace Cache" einen Performancegewinn in der Größenordnung von 0,57% erwarten lässt.An dieser Stelle gibt es von mir Zustimmung, aber auch Ablehnung.

Deine Folgerung ist sicherlich richtig. Wenn man eins aus Amdahl's Law folgern kann, dann dass man die häufigen Fälle optimieren muss und nicht die seltenen. Wer mal ein paar Übungsbeispiele dazu durchgerechnet hat, dem ist klar, dass selbst sehr krasse Optimierungen im Bereich von +500% kaum etwas an der Ausführungszeit ändern, wenn der Anteil an selbiger zu gering ist. Da bringen allgemeine Optimierungen mit wesentlich geringeren Speedups aber z.B. verdoppeltem Anteil an der Ausführungszeit deutlich mehr. Insofern ist die Folgerung absolut richtig.

Woran ich jedoch Kritik übe, sind deine - soweit ich das beurteilen kann - optimistischen Zahlen. ;)
Ich halte deine "Trefferquote von 95% und mehr" für zu hoch geschätzt. Ich kann zwar leider nur recht alten Zahlen von SPEC89 liefern, aber die Spanne ist dort weitaus größer. Bis zu 18% Missprediction bei einem 2-Bit Counter sind schon ein bisschen mehr als du geschrieben hast, auch wenn der Durchschnitt trotzdem bei 7% liegt (Quelle: Hennessy & Patterson, Computer Architecture, 3rd Edition, Seite 200): 4096 entries, unlimited entries,
2 bits/entry 2 bits/entry
nasa7 1% 0%
matrix300 0% 0%
tomcatv 1% 0%
doduc 5% 5%
spice 9% 9%
fpppp 9% 9%
gcc 12% 11%
espresso 5% 5%
eqntott 18% 18%
li 10% 10%Imho nutzt der K7 nutzt genau diese Konstellation, nämlich 4096 Einträger dieser 2 Bit Counter, während der K8 16384 davon besitzt.

Und auch den Branch-Anteil an durchschnittlichem Code würde ich auf mehr als die von dir angenommenen 15% schätzen. Zumindest liegen die Werte für SPEC92 im Bereich von 18 bis 24%. (Klick, Seite 3 (http://citeseer.ist.psu.edu/44354.html)). Das soll keine Rechthaberei sein, sondern nur mal als Anschauung dienen, damit man konkrete Zahlen hat. Andere (aktuellere) Quellen sind natürlich immer willkommen =)
Diese Zahlen ändern natürlich nichts an deiner obigen Feststellung, dass der TC hier nicht viel nützt. Daher habe ich auch gleich zu Anfang meine Zustimmung dazu geäußert :)


Eine Sache, die jetzt noch nicht angesprochen wurde und die ich in obigem Paper gefunden habe, ist die Frage nach der Fetch Bandbreite bei Sprüngen. Dort heraus folgende Tabelle (SPEC92):Benchmark taken % avg basic # instr between
block size taken branches
eqntott 86.2% 4.20 4.87
espresso 63.8% 4.24 6.65
xlisp 64.7% 4.34 6.70
gcc 67.6% 4.65 6.88
sc 70.2% 4.71 6.71
compress 60.9% 5.39 8.85Ein klassischer I-Cache in Kombination mit Dekodern untersucht immer eine im Speicher zusammenhängende Folge von Bytes. Wenn darin ein Sprung auftaucht und dieser von der Branch-Prediction als "genommen" identifiziert wird, muss man das Fetchen an einer anderen Speicherstelle fortführen. Das kann dazu führen, dass man ausser dem Sprung nichts weiteres in diesem einen Takt dekodieren kann (bin mir nicht ganz sicher, wie das beim K8 geregelt ist). Für Befehle, die in den Ausführungseinheiten landen sollen, kann dieser Takt sogar eine Nullnummer bedeuten.

Natürlich gibt es zwischen Dekoder und Ausführungseinheiten noch einige Puffer, die erstmal leer laufen müssen. Aber wenn sich innerhalb eines größeren Stückes nun viele als genommen vorhergesagte Sprünge häufen, dann könnte das zu einem echten Engpass durch nicht genügend dekodierte Befehle führen.

"Enqtott" hat im Schnitt weniger als 5 Befehle zwischen zwei als "genommen" vorrausgesagten Sprüngen. Das halte ich für schon recht bedenklich. Zwar ist im Schnitt wie in meinem letzten Posting verlinkt der durchschnittliche Durchsatz des Back-Ends wohl deutlich geringer als 3 µOps/Takt, aber das heisst ja nicht, dass es in Peak-Situationen nicht durchaus mehr sein kann. Wenn bei sprungintensivem Code nicht genügend dekodierte Befehle vorhanden sind weil die Dekoder nicht nachkommen, wäre an dieser Stelle ein TC sicher von Vorteil. :)

edit: Ja, es ist mir klar, dass dies das Gegenteil von dem ist, was ich in meinem vorhiergen Post geschrieben habe, also dass der Dekoder des K8 genügend dimensioniert sei. Da war mir die Fragestellung der Fetch-Bandbreite auch noch nicht präsent...

[zeckensack]

<...>

Ich halte deine "Trefferquote von 95% und mehr" für zu hoch geschätzt. Ich kann zwar leider nur recht alten Zahlen von SPEC89 liefern, aber die Spanne ist dort weitaus größer. Bis zu 18% Missprediction bei einem 2-Bit Counter sind schon ein bisschen mehr als du geschrieben hast, auch wenn der Durchschnitt trotzdem bei 7% liegt <...>

Imho nutzt der K7 nutzt genau diese Konstellation, nämlich 4096 Einträger dieser 2 Bit Counter, während der K8 16384 davon besitzt.Die K7-BP ist auch nicht mehr sonderlich aktuell. IMO hat der P4 wesentlich fortschrittlichere Prediktoren (IIRC 3 Bits; zwei verschiedene Algos mit jeweils 2 Bit History, und das dritte Bit wählt den momentan erfolgreicheren aus), und erreicht damit auch höhere durchschnittliche Trefferquoten (immer noch höher als beim K8).
Und auch den Branch-Anteil an durchschnittlichem Code würde ich auf mehr als die von dir angenommenen 15% schätzen. Zumindest liegen die Werte für SPEC92 im Bereich von 18 bis 24%. (Klick, Seite 3 (http://citeseer.ist.psu.edu/44354.html)). Das soll keine Rechthaberei sein, sondern nur mal als Anschauung dienen, damit man konkrete Zahlen hat. Andere (aktuellere) Quellen sind natürlich immer willkommen =)Meine "Quelle" war auch nur eine Schätzung.

Je nach Projekt kann diese Zahl auch höher ausfallen, die Frage ist nur, ob die Zählweise denn sinnvoll ist.

Ich schätze zB mein privates Hauptprojekt auf deutlich über 50% Branch-Anteil. Das ist bei "state machines" auch normal. Das ist aber nur eine Erhebung des Anteils der Branches am gesamten Code ... das ist IMO nicht zwangsläufig sinnvoll.
1)verbringe ich (gemessene) 80% der Ausführungszeit in externen Libs. Dazu kann ich schonmal garnichts sagen.
2)verbringe ich von der restlichen Ausführungszeit >90% in "stream kernel"-artigen Funktionen. Diese enthalten auch jeweils mindestens zwei branches (Schleifenkonstrukt + RETN), allerdings sind sie mit geschätzten mittleren 100 Maschineninstruktionen schon recht umfangreich.

Der Mittelwert "Branches im Programm/alle Instruktionen im Programm" ist davon nicht wirklich betroffen.
Der Mittelwert "begegnete Branches (Merhfachzählung möglich)/ausgeführte Instruktionen (Mehrfachzählung möglich)" dagegen wird dadurch IMO sehr stark gedrückt.

Deswegen ist es wichtig zu wissen, wie solche Statistiken aufgestellt wurden. Ich vermute aufgrund der Zahlen, dass deine der ersten Zählweise folgt. Das wäre technisch betrachtet natürlich iO, aber ist sowas auch praktisch relevant?
Eine Sache, die jetzt noch nicht angesprochen wurde und die ich in obigem Paper gefunden habe, ist die Frage nach der Fetch Bandbreite bei Sprüngen. Dort heraus folgende Tabelle (SPEC92):Benchmark taken % avg basic # instr between
block size taken branches
eqntott 86.2% 4.20 4.87
espresso 63.8% 4.24 6.65
xlisp 64.7% 4.34 6.70
gcc 67.6% 4.65 6.88
sc 70.2% 4.71 6.71
compress 60.9% 5.39 8.85Ein klassischer I-Cache in Kombination mit Dekodern untersucht immer eine im Speicher zusammenhängende Folge von Bytes. Wenn darin ein Sprung auftaucht und dieser von der Branch-Prediction als "genommen" identifiziert wird, muss man das Fetchen an einer anderen Speicherstelle fortführen. Das kann dazu führen, dass man ausser dem Sprung nichts weiteres in diesem einen Takt dekodieren kann (bin mir nicht ganz sicher, wie das beim K8 geregelt ist). Für Befehle, die in den Ausführungseinheiten landen sollen, kann dieser Takt sogar eine Nullnummer bedeuten.Du überinterpretierst diese Zahlen. Ich weiss nicht wie du darauf kommst, dass ein klassischer I-Cache damit überfordert wäre, denn dazu fehlen dir ganz entscheidende Parameter:
1)Dort steht nichts davon, wie weit das Branchziel im Mittel entfernt ist.
2)Dort steht nichts davon, wie hoch die Anzahl an "Wiederholungstätern" ist.

1)Sind viele Branches ganz einfach Schleifen. Dort ist es egal, ob Trace Cache oder I-Cache. Das Ansprungziel ist mit extrem hoher Wahrscheinlichkeit bereits im Cache, denn es ist der Schleifenkörper, und der wurde unmittelbar zuvor bereits ausgeführt.

Und auch branches außerhalb von Schleifen können trotzdem eine hohe effektive räumliche Lokalität aufweisen. ZB:
if (NULL==this->memory)
{
this->memory=malloc(mem_required);
}
...

<=>
.if_statement:
MOV EAX,[ESI+xxx]
TEST EAX,EAX
JNZ .alloc_ok

.if_body:
PUSH [mem_required]
CALL near "malloc"
MOV [ESI+xxx],EAX

.alloc_ok:Der "weit entfernte" Aufruf von malloc ist in diesem Fall eine Ausnahmebehandlung. Der normale Fluß durch den Code ist ein kurzer Sprung. Im Mittel der Ausführungszeit ist dort kein langer Sprung, sondern ein sehr kurzer Sprung.

Sektionen mit hoher Branch-Dichte sind nicht zwangsläufig wildes Umherhüpfen zwischen tausenden weit voneinander entfernter Funktionen mit 4,2 Instruktionen Länge.

Es können auch ganz einfach nahe Sprünge innerhalb eines großen Funktionskörpers sein.

Denk mal an Switch-Statements, Parametervalidierung, adaptive Speicherzuweisung, Polymorphie, etc, und wie diese Konzepte in Maschinencode übersetzt werden. Alles im Prinzip das gleiche.

2)Jetzt solltest du entgegnen, dass die drei Instruktionen der "Ausnahmebehandlung" nur sehr selten genommen werden, und trotzdem Platz im Cache verschwenden. Korrekt. Deswegen ist die hohe Code-Dichte von x86 so günstig für konventionelle I-Caches. Es tut einfach kaum weh. Der Code ist so stark komprimiert, dass man sich sowas leisten kann, denn man kriegt so viele Instruktionen in so wenig Cache, dass die Einsparungen an Instruktionen durch einen TC fast zwangsläufig durch das weniger kompakte Speicherformat wieder gekillt werden.

Mit klassischen RISC-ISAs (feste und enorme Instruktionsgrößen) ist ein Trace Cache möglicherweise effektiver, wenn er mit allen Schikanen implementiert wurde. Daran hatte ich noch garnicht gedacht :)

Der Sprung in das weit entfernte malloc dagegen ist unkritisch. Wird der dort liegende Code wirklich nur sehr selten benötigt, wird er aus dem Cache verdrängt (er ist ja nicht im Funktionsfluß eingebettet). Wird er immer mal wieder aufgerufen (natürlich auch von an anderen Stellen aus), dann bleibt er eben drin.

<...>
edit: Ja, es ist mir klar, dass dies das Gegenteil von dem ist, was ich in meinem vorhiergen Post geschrieben habe, also dass der Dekoder des K8 genügend dimensioniert sei. Da war mir die Fragestellung der Fetch-Bandbreite auch noch nicht präsent...Dazu kann ich nur am Rande etwas sagen, da ich das nicht mehr 100%ig im Kopf habe.

K7 und K8 dekodieren immer 16 Bytes Code am Stück. In den Predecode-Bits (ein Anhang zum I-Cache, das natürlich auch Platz braucht) wird gespeichert, wo Instruktionen anfangen, wo sie enden, und was bekannte branch targets sind.

AMD empfiehlt für maximale Performance in hot spots, dass nur ein branch (oder ein branch target) pro 8 Byte Code stehen soll.

Das ist alles. Den Rest wirst du nachlesen (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF) müssen.
Quelle (http://www.amd.com/us-en/Processors/TechnicalResources/0,,30_182_739_9003,00.html)
Noch mehr Quellen (http://www.amd.com/us-en/Processors/TechnicalResources/0,,30_182_739_7044,00.html)

[GloomY]

Die K7-BP ist auch nicht mehr sonderlich aktuell. IMO hat der P4 wesentlich fortschrittlichere Prediktoren (IIRC 3 Bits; zwei verschiedene Algos mit jeweils 2 Bit History, und das dritte Bit wählt den momentan erfolgreicheren aus), und erreicht damit auch höhere durchschnittliche Trefferquoten (immer noch höher als beim K8).Das stimmt natürlich.

Meine "Quelle" war auch nur eine Schätzung.

Je nach Projekt kann diese Zahl auch höher ausfallen, die Frage ist nur, ob die Zählweise denn sinnvoll ist.

Ich schätze zB mein privates Hauptprojekt auf deutlich über 50% Branch-Anteil. Das ist bei "state machines" auch normal. Das ist aber nur eine Erhebung des Anteils der Branches am gesamten Code ... das ist IMO nicht zwangsläufig sinnvoll.
1)verbringe ich (gemessene) 80% der Ausführungszeit in externen Libs. Dazu kann ich schonmal garnichts sagen.
2)verbringe ich von der restlichen Ausführungszeit >90% in "stream kernel"-artigen Funktionen. Diese enthalten auch jeweils mindestens zwei branches (Schleifenkonstrukt + RETN), allerdings sind sie mit geschätzten mittleren 100 Maschineninstruktionen schon recht umfangreich.

Der Mittelwert "Branches im Programm/alle Instruktionen im Programm" ist davon nicht wirklich betroffen.
Der Mittelwert "begegnete Branches (Merhfachzählung möglich)/ausgeführte Instruktionen (Mehrfachzählung möglich)" dagegen wird dadurch IMO sehr stark gedrückt.

Deswegen ist es wichtig zu wissen, wie solche Statistiken aufgestellt wurden. Ich vermute aufgrund der Zahlen, dass deine der ersten Zählweise folgt. Das wäre technisch betrachtet natürlich iO, aber ist sowas auch praktisch relevant?Zur Zählweise kann ich nichts sagen, auch deswegen weil meine verlinkte Quelle gerade down ist und ich diese nicht auf meinem Rechner habe.

Ansonsten ist natürlich die zweite Zählung sinnvoll, denn es geht ja gerade darum wie viel Prozent der ausgeführten Befehle Sprungbefehle sind, also wie oft diese durch den Decoder müssen.
Du überinterpretierst diese Zahlen. Ich weiss nicht wie du darauf kommst, dass ein klassischer I-Cache damit überfordert wäre, denn dazu fehlen dir ganz entscheidende Parameter:
1)Dort steht nichts davon, wie weit das Branchziel im Mittel entfernt ist.Das ist egal, es geht mir bezüglich des Dekodierens darum, ob ein Sprung genommen wird oder nicht. Wohin ist erstmal (fast) egal (s.u.)

2)Dort steht nichts davon, wie hoch die Anzahl an "Wiederholungstätern" ist.

1)Sind viele Branches ganz einfach Schleifen. Dort ist es egal, ob Trace Cache oder I-Cache. Das Ansprungziel ist mit extrem hoher Wahrscheinlichkeit bereits im Cache, denn es ist der Schleifenkörper, und der wurde unmittelbar zuvor bereits ausgeführt.

Und auch branches außerhalb von Schleifen können trotzdem eine hohe effektive räumliche Lokalität aufweisen. ZB:
if (NULL==this->memory)
{
this->memory=malloc(mem_required);
}
...

<=>
.if_statement:
MOV EAX,[ESI+xxx]
TEST EAX,EAX
JNZ .alloc_ok

.if_body:
PUSH [mem_required]
CALL near "malloc"
MOV [ESI+xxx],EAX

.alloc_ok:Der "weit entfernte" Aufruf von malloc ist in diesem Fall eine Ausnahmebehandlung. Der normale Fluß durch den Code ist ein kurzer Sprung. Im Mittel der Ausführungszeit ist dort kein langer Sprung, sondern ein sehr kurzer Sprung.

Sektionen mit hoher Branch-Dichte sind nicht zwangsläufig wildes Umherhüpfen zwischen tausenden weit voneinander entfernter Funktionen mit 4,2 Instruktionen Länge.

Es können auch ganz einfach nahe Sprünge innerhalb eines großen Funktionskörpers sein.Ist ja alles richtig, die Sprünge müssen nicht umbedingt weit sein. Aber eigentlich wollte ich auf etwas anderes hinaus ;) Vielleicht habe ich mich ja auch nicht genau genug ausgedrückt:

Der Athlon bekommt 16 Bytes/Takt an seinen Decoder. Diese können aus mehreren Cachlines stammen, d.h. es ist nicht am Ende einer Cache Line Schluss sondern es sind immer 16 im Speicher zusammenhängende Bytes, also ab einer bestimmten Adresse 16 Bytes "aufwärts". Ich sag' das so deutlich, weil es für das, worauf ich hinaus will, wichtig ist.

Wenn unter diesen 16 Bytes ein Sprung ist und dieser von der Branch Prediction als "genommen" vorrausgesagt wird, dann ist der nächste Befehl in der Programmabarbeitung nicht einer aus diesem 16 Bytes Block sondern aus einem vollkommen anderen Speicherbereich (eben von dort wohin der Sprung geht). D.h. dass für diesen Takt die Dekodierung nach dem genommenen Sprung beendet werden muss, weil die restlichen Bytes nicht die Befehle enthalten, die als nächstes dran sind. Diese können erst wieder im nächsten Takt dekodiert werden, wenn der I-Cache die ersten 16 Bytes ab dem vorrausgesagten Sprungziel liefert.

Je nachdem, wo innerhalb des 16 Bytes Blocks der Sprung auftaucht, können noch mehr oder weniger Instruktionen davor dekodiert werden. Der Punkt ist, dass für diesen Takt die Anzahl der dekodierten Instruktionen durch die Position des Sprungs innerhalb der 16 Bytes bzw. dessen Ende begrenzt ist und nicht durch den Dekoder (3µOps/Takt in maximal 16 Bytes). In jedem Takt, in dem ein genommener Sprung dekodiert wird, endet die Dekodierung der Befehle hinter dem Sprung. Vielleicht wird in diesem Takt nur der Sprung selbst dekodiert oder vielleicht ein Befehl davor und dann der Sprung, wahrscheinlich aber nicht so viel wie normalerweise aus den gesamten 16 Bytes möglich wäre (3µOps/Takt). Ein genommener Sprung limitiert also den Decoder in diesem Takt, darauf wollte ich hinaus :)

Meine Frage war jetzt, ob Code mit vielen Sprüngen bzw. mit vielen als genommen vorhergesagten Sprüngen nicht zu einem Engpass bei der Decodierung führen kann. Immerhin kann das Back-End theoretisch 9 µOps/Takt ausführen, wenn natürlich auch nicht im Durchschnitt.
Die Häufigkeit von genommenen Sprüngen ist da natürlich ein entscheidender Faktor. Da ich mir jetzt nicht sicher bin, nach welcher Zählweise meine Quelle die Daten erhoben hat, müssen wir erstmal abwarten, bis diese wieder online ist.

Wenn aber eine echte Dskodierungslimitierung vorläge, dann hätte ein Trace Cache wirklich Vorteile, weil dieser eben die Instruktionen enthält wie sie wirklich in der Programmabfolge vorkommen, d.h. auch über eventuell genommene Sprünge hinaus. Ein TC kann auch bei Sprüngen weit mehr dekodierte Befehle/Takt liefern als ein klassischer I-Cache mit "dreifach"-Dekoder.
Dazu kann ich nur am Rande etwas sagen, da ich das nicht mehr 100%ig im Kopf habe.

K7 und K8 dekodieren immer 16 Bytes Code am Stück. In den Predecode-Bits (ein Anhang zum I-Cache, das natürlich auch Platz braucht) wird gespeichert, wo Instruktionen anfangen, wo sie enden, und was bekannte branch targets sind.

AMD empfiehlt für maximale Performance in hot spots, dass nur ein branch (oder ein branch target) pro 8 Byte Code stehen soll.Haha, warum wohl? ;)
Das ist alles. Den Rest wirst du nachlesen (http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF) müssen.
Quelle (http://www.amd.com/us-en/Processors/TechnicalResources/0,,30_182_739_9003,00.html)
Noch mehr Quellen (http://www.amd.com/us-en/Processors/TechnicalResources/0,,30_182_739_7044,00.html)Danke für die Infos, ich kann aber nicht versprechen, dass ich mir das alles durchlese...

Ich guck' aber trotzdem mal rein :)

[Muh-sagt-die-Kuh]

Das stimmt natürlich.
Je nachdem, wo innerhalb des 16 Bytes Blocks der Sprung auftaucht, können noch mehr oder weniger Instruktionen davor dekodiert werden. Der Punkt ist, dass für diesen Takt die Anzahl der dekodierten Instruktionen durch die Position des Sprungs innerhalb der 16 Bytes bzw. dessen Ende begrenzt ist und nicht durch den Dekoder (3µOps/Takt in maximal 16 Bytes). In jedem Takt, in dem ein genommener Sprung dekodiert wird, endet die Dekodierung der Befehle hinter dem Sprung. Vielleicht wird in diesem Takt nur der Sprung selbst dekodiert oder vielleicht ein Befehl davor und dann der Sprung, wahrscheinlich aber nicht so viel wie normalerweise aus den gesamten 16 Bytes möglich wäre (3µOps/Takt). Ein genommener Sprung limitiert also den Decoder in diesem Takt, darauf wollte ich hinaus :)Sollte sich diese Situation nicht durch geschickte Anordnung der Befehle durch den Compiler (sprich der Branch-Befehl ist möglichst immer der letzte in einem 16 Byte-Block, die einem Branch-Target folgenden 16 Bytes befinden sich möglichst immer in einer einzelnen Cache-Line) entschärfen lassen?

Um zu beurteilen, ob sowas sinnvoll wäre bräuchte man aber erst genauere Zahlen inwiefern der Decoder überhaupt limitierend wirkt.

[GloomY]

Sollte sich diese Situation nicht durch geschickte Anordnung der Befehle durch den Compiler (sprich der Branch-Befehl ist möglichst immer der letzte in einem 16 Byte-Block, die einem Branch-Target folgenden 16 Bytes befinden sich möglichst immer in einer einzelnen Cache-Line) entschärfen lassen?

Um zu beurteilen, ob sowas sinnvoll wäre bräuchte man aber erst genauere Zahlen inwiefern der Decoder überhaupt limitierend wirkt.Der I-Cache liefert ja immer 16 Byte ab dem Programm Counter, also nicht immer einen 16 Byte-Block, welcher auch 16 Byte-aligned im Speicher liegt. Der Anfangspunkt kann also prinzipiell eine beliebige Adresse sein, daher ist das Anordnen der Sprung-Befehle in die letzten Bytes eines 16Byte-aligned Blocks nicht wirklich sinnvoll. Wenn der I-Cache bei einer Adresse zu fetchen beginnt, die modulo 14 = 0 ist, dann kann es genauso passieren, dass der erste zu dekodierende Befehl ein Sprung ist (Leg' mich jetzt nicht auf die 14 fest, kA wie viel Bytes ein Sprung für die Codierung braucht).

Was man natürlich machen kann/sollte ist nicht zu viele Branches in kurzem Abstand zu haben. Deshalb gibt AMD ja auch an, dass nur höchstens alle 8 Byte Code ein Branch vorkommen sollte. :)

[Muh-sagt-die-Kuh]

Der I-Cache liefert ja immer 16 Byte ab dem Programm Counter, also nicht immer einen 16 Byte-Block, welcher auch 16 Byte-aligned im Speicher liegt.Der Anfangspunkt kann also prinzipiell eine beliebige Adresse sein, daher ist das Anordnen der Sprung-Befehle in die letzten Bytes eines 16Byte-aligned Blocks nicht wirklich sinnvoll. Wenn der I-Cache bei einer Adresse zu fetchen beginnt, die modulo 14 = 0 ist, dann kann es genauso passieren, dass der erste zu dekodierende Befehl ein Sprung ist (Leg' mich jetzt nicht auf die 14 fest, kA wie viel Bytes ein Sprung für die Codierung braucht).

Was man natürlich machen kann/sollte ist nicht zu viele Branches in kurzem Abstand zu haben. Deshalb gibt AMD ja auch an, dass nur höchstens alle 8 Byte Code ein Branch vorkommen sollte. :)Hmmmm, das die Blöcke nicht aligned sind muss ich wohl überlesen haben....das macht das ganze auf jeden Fall noch ekelhafter, als es sowieso schon ist. Die Branch-Befehle unter dieses Prämissen optimal anzuordnen sollte eigentlich ein NP-schweres Problem darstellen.

[zeckensack]

<schnipp>
Das ist egal, es geht mir bezüglich des Dekodierens darum, ob ein Sprung genommen wird oder nicht. Wohin ist erstmal (fast) egal (s.u.)Aber nur fast ;)
Wenn ich von der aktuellen Adresse aus x Bytes vorwärts springe, und mein I-Cache Lines von >=2*x Bytes Länge hat ...
Ein kurzer Vorwärtssprung wird mit extrem hoher Wahrscheinlichkeit auf Code verweisen, der bereits im I-Cache liegt und dekodiert ist. Stichwort "Prefetch". Das ist ein Nebeneffekt jeglicher Cache-Architekturen mit Lines, also unter Ausnahme von Haarmanns Idee allen ;)

Ist ja alles richtig, die Sprünge müssen nicht umbedingt weit sein. Aber eigentlich wollte ich auf etwas anderes hinaus ;) Vielleicht habe ich mich ja auch nicht genau genug ausgedrückt:

Der Athlon bekommt 16 Bytes/Takt an seinen Decoder. Diese können aus mehreren Cachlines stammen, d.h. es ist nicht am Ende einer Cache Line Schluss sondern es sind immer 16 im Speicher zusammenhängende Bytes, also ab einer bestimmten Adresse 16 Bytes "aufwärts". Ich sag' das so deutlich, weil es für das, worauf ich hinaus will, wichtig ist.Das ist in der Tat starker Tobak, und das höre ich hier auch zum ersten Mal. Wo kann ich das nachlesen? Du weißt, wie üblich, ich habe großes Vertrauen, dass deine Aussagen richtig sind, nur überrascht mich das doch sehr. IMO verkompliziert das die Cache-Architektur erheblich, und bringt im statistischen Mittel eigentlich garnichts ...
Ich würde gerne mal selbst nachforschen :)

Deswegen vertage ich mal meine Antwort auf die Passagen, die das als gegeben voraussetzen.

Haha, warum wohl? ;)Ich denke nicht dass es an den Dekodern oder dem I-Cache selbst liegt. Ich vermute viel eher, dass die Branch-History mit verkürzten Addressen arbeitet, und nur einen Eintrag pro 8 Byte Code haben kann.
Danke für die Infos, ich kann aber nicht versprechen, dass ich mir das alles durchlese...

Ich guck' aber trotzdem mal rein :)Es lohnt sich. AMD-Dokumentation ist erstaunlich klar und offenherzig, man erhält tiefe Einblicke in die Architektur. Ein sehr angenehmer Kontrast zu Intel.

[Haarmann]

OT /on

zeckensack

Hatte der Cyrix 486DLC Lines?

OT /off

[zeckensack]

OT /on

zeckensack

Hatte der Cyrix 486DLC Lines?

OT /offIch weiß es nicht. Ich vermute mal, dass du es weißt, und wenn du auf meinem Seitenhieb oben reagiest, dann lautet die Antwort höchstwahrscheinlich "nein" :)

Ich kann mich aber erinnern, dass dieses Gerät unglaublich langsam war. Mein Vater hatte mal sowas. Hatte einen "eingebauten" grünen Kühlkörper auf dem was von "FasCache" (kein Schreibfehler) stand. 2kiB (Intel's 486er hatten 8kiB), und -- damals noch branchenüblich -- keine Trennung zwischen Daten und Code.

Oder ist das ein anderes Modell?

[GloomY]

Aber nur fast ;)
Wenn ich von der aktuellen Adresse aus x Bytes vorwärts springe, und mein I-Cache Lines von >=2*x Bytes Länge hat ......dann habe ich höchstwahrscheinlich einen I-Cache Hit :) , es sei denn die aktuelle Adresse ist ziemlich "nah" am Ende der aktuellen Cache Line und die folgenden Befehle liegen nicht in einer weiteren Line (was wie du unten schreibst eher unwahrscheinlich wegen Prefetch ist).
Ein kurzer Vorwärtssprung wird mit extrem hoher Wahrscheinlichkeit auf Code verweisen, der bereits im I-Cache liegt und dekodiert ist. Stichwort "Prefetch". Das ist ein Nebeneffekt jeglicher Cache-Architekturen mit Lines, also unter Ausnahme von Haarmanns Idee allen ;)Natürlich ist es für die Performance nicht egal, wo man hinspringt. Für das Dekodieren allein betrachtet ist es das aber schon. Mir ging es ja - nachdem ich die Ineffektivität der Reduzierung der Branch Missprediction Penalty durch TC eingesehen hatte - nur noch um die Frage, in wieweit ein TC beim Dekodieren von sprunganfälligem Code Vorteile gegenüber einem normalem I-Cache plus Dekoder hat.
Meine Betrachtung bezog sich deswegen erstmal allein auf den Dekodiervorgang und hat die Hitrate des I-Caches erstmal nicht betrachtet.
Und ich bleibe dabei, dass es für das Dekodieren alleine betrachtet egal ist, wohin man springt, es ist lediglich wichtig, ob man springt oder nicht.
Das ist in der Tat starker Tobak, und das höre ich hier auch zum ersten Mal. Wo kann ich das nachlesen? Du weißt, wie üblich, ich habe großes Vertrauen, dass deine Aussagen richtig sind, nur überrascht mich das doch sehr. IMO verkompliziert das die Cache-Architektur erheblich, und bringt im statistischen Mittel eigentlich garnichts ...
Ich würde gerne mal selbst nachforschen :)Tja, ich dachte, ich hätte es bei Hans de Vries gelesen, aber ich jetzt wo ich es nachschauen wollte, kann ich es nicht mehr finden. Das ist peinlich für mich, erst etwas zu behaupten und es dann nicht belegen zu können :|

Asche auf mein Haupt... ;(
Ich denke nicht dass es an den Dekodern oder dem I-Cache selbst liegt. Ich vermute viel eher, dass die Branch-History mit verkürzten Addressen arbeitet, und nur einen Eintrag pro 8 Byte Code haben kann.Mangels Wissen kann ich dazu (erstmal) nichts sagen :|


leicht OT: Ein TC hat noch einen weiteren Nachteil, wenn man Code und Daten in einer "Section" (sind damit Segmente gemeint?) mischt (kA wie oft das vorkommt):

http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&selm=8d5ji09jpcrdkpal3d4gqjhcp7vkmr7rm1%404ax.com

Ein gescheiter Compiler sollte das bei allen neueren Architekturen mit split I/D Cache verhindern, denn sonst wird mal eben der komplette TC geflushed :rolleyes:

[zeckensack]

Natürlich ist es für die Performance nicht egal, wo man hinspringt. Für das Dekodieren allein betrachtet ist es das aber schon. Mir ging es ja - nachdem ich die Ineffektivität der Reduzierung der Branch Missprediction Penalty durch TC eingesehen hatte - nur noch um die Frage, in wieweit ein TC beim Dekodieren von sprunganfälligem Code Vorteile gegenüber einem normalem I-Cache plus Dekoder hat.Ist architekturspezifisch. Es gibt IMO auch beim Trace Cache viele Variablen und Tweaks, die die Antwort auf diese Frage beeinflussen. Generell würde ich aber sagen, dass da ein TC im Vorteil ist. Alleine schon weil man sich mehr Zeit zum gründlichen Dekodieren nehmen kann. Der Trace Cache puffert die dadurch entstehenden Latenzen ja weitgehend vom Rest der Pipeline ab.

Evtl ist das auch ein Grund für die 10 Pipeline-Stufen vor dem Trace Cache in "NetBurst"? :conf2:
Meine Betrachtung bezog sich deswegen erstmal allein auf den Dekodiervorgang und hat die Hitrate des I-Caches erstmal nicht betrachtet.
Und ich bleibe dabei, dass es für das Dekodieren alleine betrachtet egal ist, wohin man springt, es ist lediglich wichtig, ob man springt oder nicht.Und du hast Recht ;)
Tja, ich dachte, ich hätte es bei Hans de Vries gelesen, aber ich jetzt wo ich es nachschauen wollte, kann ich es nicht mehr finden. Das ist peinlich für mich, erst etwas zu behaupten und es dann nicht belegen zu können :|

Asche auf mein Haupt... ;(
Mangels Wissen kann ich dazu (erstmal) nichts sagen :|Hans de Vries' K8-Übersicht habe ich mir auch gründlich reingezogen, als sie damals neu war. Ich seh's mir vielleicht nochmal durch. IMO steht da einiges, was für uns hier relevant ist.
1)die "Predecoder" arbeiten mit 16 Byte-Paketen. An beliebige Startadressen kann ich mich nicht erinnern, vielleicht steht's aber doch irgendwo ...
2)Der L1-I-Cache speichert neben den 64kiB ISA-Code auch einen ganzen Haufen Zusatzdaten (48kiB). Unter anderem pro I-Cache-Line zwei "lokale" Branch History-Einträge ...
leicht OT: Ein TC hat noch einen weiteren Nachteil, wenn man Code und Daten in einer "Section" (sind damit Segmente gemeint?) mischt (kA wie oft das vorkommt):

http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&selm=8d5ji09jpcrdkpal3d4gqjhcp7vkmr7rm1%404ax.com

Ein gescheiter Compiler sollte das bei allen neueren Architekturen mit split I/D Cache verhindern, denn sonst wird mal eben der komplette TC geflushed :rolleyes:Richtig. Code und Daten zu nah aneinander in den Speicher zu legen ist für alle modernen Architekturen shice. Egal ob TC oder konventionell.

[Haarmann]

zeckensack

Ich weiss es eben auch nicht auf Sicher. Was ich aber weiss, ist, dass es auf dem i386er Sockel sass und ne ideale Spiele CPU war (imul war schneller als beim i486 war glaubs der Grund). Daher schliesse ich die Option nicht aus, dass es keine Lines gab. Er hatte doch auch nur 1KB Cache drinnen und die FPU war noch extern - ich hatte ne ULSI Math oder wie die hiess. Mein Board hatte nen OPTI Chipset und nen altes AMI BIOS nebst den obligaten 8 SIMM Slots für 30 Pinner. Ich werde also mal nachsehen, wie der Cache wohl aufgebaut ist. Das Buch ist allerdings bei meinen eltern geblieben - es ist etwas alt...

http://cpu-museum.de/?m=Cyrix&f=486DLC

Nen solchen Chip hätte ich auch noch ;).

[StefanV]

Wenn jemand ein Testproggie für DOS hinbekommt, dann könnte ich das mal testen.

In meinem HW Sortiment befindet sich atm sogar ein 486DLC, allerdings von Texas Instruments...

Win95 möchte ich nicht unbedingt installieren, da das Board ein ISA Board ist und ich keine 500er Platte hab (nur 1,6GB und 250MB), dazu hat das Board nur 4 SIMM Sockel und ich keine 2 oder 4MB (30pin) SIMMs...

[zeckensack]

zeckensack

Ich weiss es eben auch nicht auf Sicher. Was ich aber weiss, ist, dass es auf dem i386er Sockel sass und ne ideale Spiele CPU war (imul war schneller als beim i486 war glaubs der Grund). Daher schliesse ich die Option nicht aus, dass es keine Lines gab. Er hatte doch auch nur 1KB Cache drinnen und die FPU war noch extern - ich hatte ne ULSI Math oder wie die hiess. Mein Board hatte nen OPTI Chipset und nen altes AMI BIOS nebst den obligaten 8 SIMM Slots für 30 Pinner. Ich werde also mal nachsehen, wie der Cache wohl aufgebaut ist. Das Buch ist allerdings bei meinen eltern geblieben - es ist etwas alt...

http://cpu-museum.de/?m=Cyrix&f=486DLC

Nen solchen Chip hätte ich auch noch ;).Dann haben wir aneinander vorbei geredet :)
Mein Vater hatte diesen (http://cpu-museum.de/?m=Cyrix&f=Cx486#cpu0054), und der passte schon auf den 486er Sockel. Im Vergleich zu einem richtigen 486er (i486DX-33 zB, oder gar AMD's damals noch zu Intel baugleichen AM486DX-40) fand ich ihn allerdings kaum "ideal".

[Haarmann]

zeckensack

Der sieht irgendwie schlecht aus... vor allem für sein Erscheinungsdatum. Aber dann isses klar, dass wir nicht zum gleichen Ergebnis kommen könnten ;).