PatentDe  


Dokumentenidentifikation DE10015675B4 14.07.2005
Titel Spekulative Auswahl von heißen Spuren in einem dynamischen CACHE-Übersetzer mit geringem Aufwand
Anmelder Hewlett-Packard Co. (n.d.Ges.d.Staates Delaware), Palo Alto, Calif., US
Erfinder Bala, Vasanth, Sudbury, Ma., US;
Duesterwald, Evelyn, Boston, Ma., US
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Anmeldedatum 29.03.2000
DE-Aktenzeichen 10015675
Offenlegungstag 23.11.2000
Veröffentlichungstag der Patenterteilung 14.07.2005
Veröffentlichungstag im Patentblatt 14.07.2005
IPC-Hauptklasse G06F 9/45
IPC-Nebenklasse G06F 12/08   

Beschreibung[de]

Die vorliegende Erfindung bezieht sich auf Techniken zum Identifizieren von Computerprogrammabschnitten, die besonders häufig ausgeführt werden. Die vorliegende Erfindung ist insbesondere bei dynamischen Übersetzern nützlich, die Kandidatenabschnitte eines Codes für eine Cache-Speicherung und/oder Optimierung identifizieren müssen.

Dynamische Übersetzer übersetzen eine Sequenz von Befehlen in eine weitere Sequenz von Befehlen, die ausgeführt wird. Die zweite Sequenz von Befehlen sind "native" Befehle – sie können von der Maschine, auf der der Übersetzer läuft, direkt ausgeführt werden (diese "Maschine" kann eine Hardware sein oder diese Maschine kann durch Software definiert sein, die auf einer weiteren Maschine mit ihrer eigenen Architektur läuft). Ein dynamischer Übersetzer kann entworfen sein, um Befehle für eine Maschinenarchitektur (d. h. einen Befehlssatz) auf einer Maschine einer unterschiedlichen Architektur (d. h. mit einem unterschiedlichen Befehlssatz) auszuführen. Alternativ kann ein dynamischer Übersetzer Befehle nehmen, die für die Maschine, auf der der dynamische Übersetzer läuft, nativ sind, und an diesem Befehlsstrom wirken, um einen optimierten Befehlsstrom zu erzeugen. Ein dynamischer Übersetzer kann ferner beide dieser Funktionen aufweisen (eine Übersetzung von einer Architektur in eine andere und eine Optimierung).

Dynamische Cache-Übersetzer versuchen, Programm-Hot-Spots (häufig ausgeführte Abschnitte des Programms, wie z. B. bestimmte Schleifen) in Laufzeit zu identifizieren, und verwenden einen Code-Cache-Speicher, um Übersetzungen dieser häufig ausgeführten Abschnitte zu speichern. Eine anschließende Ausführung dieser Abschnitte kann die Cache-mäßig gespeicherten Übersetzungen verwenden, wodurch der Aufwand zum Ausführen dieser Abschnitte des Programms reduziert wird.

Ein dynamischer Übersetzer kann Befehle in einem Befehlssatz nehmen und Befehle in einem unterschiedlichen Befehlssatz erzeugen. Oder ein dynamischer Übersetzer kann eine Optimierung durchführen: Erzeugen von Befehlen in demselben Befehlssatz wie demjenigen des ursprünglichen Befehlsstromes; folglich ist die dynamische Optimierung ein spezieller Nativ-zu-Nativ-Fall einer dynamischen Übersetzung. Oder ein dynamischer Übersetzer kann beides durchführen – Umwandeln zwischen Befehlssätzen sowie Durchführen einer Optimierung.

Im allgemeinen gilt, daß, je komplizierter das Ausführungsprofilbildungsschema ist, desto präziser die Hot-Spot-Identifizierung sein kann, und folglich (i) desto kleiner der übersetzte Code-Cache-Speicher-Platz sein kann, der erforderlich ist, um den kompakteren Satz von identifizierten Hot-Spots des Arbeitssatzes des laufenden Programms zu halten, und (ii) desto weniger Zeit auf gewendet wird, um Hot-Spots in einen nativen Code (oder in einen optimierten nativen Code) zu übersetzen. Falls keine spezielle Hardwareunterstützung für die Profilbildung vorgesehen ist, liegt allgemein der Fall vor, daß ein komplexeres Profilbildungsschema einen größeren Aufwand nach sich zieht. Folglich müssen dynamische Übersetzer typischerweise einen Ausgleich zwischen dem Minimieren der Verwaltung auf der einen Seite und dem sehr sorgfältigen Auswählen von Hot-Spots auf der anderen Seite finden.

Abhängig von der verwendeten Profilbildungstechnik kann die Granularität der ausgewählten Hot-Spots variieren. Eine Feinkörnungstechnik kann beispielsweise einzelne Blöcke identifizieren (eine schleifenfreie Codesequenz ohne jegliche dazwischen angeordnete Verzweigungen), wohingegen ein gröberer Lösungsansatz für eine Profilbildung vollständige Prozeduren identifizieren kann. Da es typischerweise verglichen zu Prozeduren viel mehr Blöcke gibt, die ausgeführt werden, erfordern die Prozeduren viel mehr Profilbildungsaufwand (sowohl Speicherplatz für die Ausführungshäufigkeitszähler als auch Zeit, die zum Aktualisieren dieser Zähler aufgewendet wird) als die Blöcke. Bei Systemen, die eine Programmoptimierung vornehmen, besteht ein weiterer, zu berücksichtigender Faktor in der Wahrscheinlichkeit einer nützlichen Optimierung und/oder dem Grad der Optimierungsmöglichkeit, die bei dem ausgewählten Hot-Spot verfügbar ist. Ein Block bietet einen viel geringeren Optimierungswirkungsbereich als eine Prozedur (und folglich können weniger Typen von Optimierungstechniken angewendet werden), obwohl ein Block einfacher zu optimieren ist, da demselben jeglicher Steuerungsfluß fehlt (Verzweigungen und Verbindungen).

Spuren bieten noch einen unterschiedlichen Satz von Abwägungen. Spuren (ferner bekannt als Pfade) sind dynamische Einzel-Eingang-Mehr-Ausgang-Sequenzen von Blöcken. Obwohl Spuren häufig einen Optimierungswirkungsbereich aufweisen, der zwischen demjenigen für Blöcke und demjenigen für Prozeduren liegt, können Spuren mehrere Prozedurkörper durchlaufen, und können sogar vollständige Prozedurkörper enthalten. Spuren bieten einen ziemlich großen Optimierungswirkungsbereich, während dieselben immer noch einen einfachen Steuerungsfluß aufweisen, was das Optimieren derselben viel einfacher macht als das Optimieren einer Prozedur. Der einfache Steuerungsfluß ermöglicht ferner eine schnellere Optimiererimplementierung. Eine dynamische Spur kann sich sogar über mehrere Prozeduraufrufe und -Rücksprünge einschließlich dynamisch verbundener Bibliotheken (DLLs) erstrecken. Dies ermöglicht einem Optimierer, ein "Inlining" durchzuführen, was eine Optimierung ist, die redundante Aufruf- und Rücksprung-Verzweigungen entfernt, was die Leistungsfähigkeit wesentlich verbessern kann.

Ungünstigerweise ist der erforderliche Aufwand, um ein Profil von heißen Spuren unter Verwendung existierender Verfahren (wie z. B. demjenigen, das in "Efficient Path Profiling", Proceedings of the 29th Symposium on Micro Architecture (MICRO-29), Dezember 1996, von T. Ball und J. Larus beschrieben wird) zu bilden, ohne eine Hardwareunterstützung unakzeptabel hoch. Solche Verfahren erfordern das Instrumentieren der Programm-Binär-Struktur (das Einfügen von Befehlen, um die Profilbildung zu unterstützen), was die Profilbildung undurchsichtig macht, und eine Aufblähung des Binärcodes ergeben kann. Die Ausführung der eingefügten Instrumentierungsbefehle verlangsamt außerdem die gesamte Programmausführung, und sobald die Instrumentierung eingefügt worden ist, ist es schwierig, dieselbe in Laufzeit zu entfernen. Zusätzlich erfordert ein solches Verfahren eine ausreichend komplexe Analyse der Zählerwerte, um die heißen Pfade in dem Programm aufzudecken, so daß ein solches Verfahren, während das Programm ausgeführt wird, schwierig während der Ausführung wirksam zu verwenden ist. All dies macht herkömmliche Schemata für eine Verwendung bei einem dynamischen Cache-Übersetzer uneffizient.

Heiße Spuren können ferner indirekt unter Verwendung einer Verzweigungs- oder Grundblock-Profilbildung aufgebaut werden (im Gegensatz zu einer Spurprofilbildung, bei der das Profil Spurinformationen direkt liefert). Bei diesem Schema wird einem Zähler das genommene Ziel jeder Verzweigung zugeordnet (es gibt andere Variationen hierfür, aber der Aufwand ist ähnlich). Wenn der dynamische Cache-Übersetzer den Programmcode interpretiert, inkrementiert derselbe einen solchen Zähler jedesmal, wenn eine angenommene Verzweigung interpretiert wird. Wenn ein Zähler einen voreingestellten Schwellenwert überschreitet, wird sein entsprechender Block als heiß markiert. Diese heißen Blöcke können aneinandergereiht werden, um eine heiße Spur zu erzeugen. Eine solche Profilbildungstechnik weist die folgenden Nachteile auf:

  • 1. Es ist eine große Zählertabelle erforderlich, da die Anzahl von getrennten Blöcken, die von einem Programm ausgeführt werden, sehr groß sein kann.
  • 2. Der Aufwand für eine Spurauswahl ist hoch. Der Grund kann intuitiv erklärt werden: falls eine Spur aus N Blöcken besteht, wird das Schema so lange warten müssen, bis alle N Zähler ihre Schwellenwerte überschritten haben, bevor dieselben in eine Spur eingereiht werden können. Dasselbe schlägt keinen Vorteil aus der Tatsache, daß, nachdem der erste Zähler heiß geworden ist, die nächsten N-1 Zähler sehr wahrscheinlich in einer schnellen Aufeinanderfolge heiß werden, wodurch es unnötig wird, mit dem Inkrementieren derselben und der Buchführung bezüglich der durchlaufenen Blöcke, die gerade ausgeführt worden sind, fortzufahren.

Aus der US 5,751,982 A ist ein Verfahren bekannt, bei dem jedem Codeblock eines Programms ein Zähler zugeordnet wird, der bei jeder Ausführung des Codeblocks inkrementiert wird. Abhängig von dem Zähler für jeden einzelnen Block wird bestimmt, ob der Block häufig ausgeführt wird, d.h. ein heißer Block ist, um zu beurteilen, ob eine dynamische Übersetzung des Blocks gerechtfertigt ist.

Die Aufgabe der vorliegenden Erfindung besteht darin, ein Verfahren zum Auswählen von heißen Spuren für eine dynamische Übersetzung zu schaffen, so daß eine Profilbildung mit weniger Aufwand durchgeführt werden kann.

Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1 gelöst.

Gemäß der vorliegenden Erfindung werden Spuren auf einer spekulativen Basis als heiß identifiziert und nicht basierend auf vollständigen Spurprofildaten. Die Reihe von Blöcken, die an einer heißen Spuranfangbedingung beginnt und sich bis zu einer Spurendebedingung erstreckt, wird als eine heiße Spur identifiziert. Eine solche Spur wird ohne die Notwendigkeit, den Aufwand des tatsächlichen Messens, ob aufeinanderfolgende Blöcke eine ausreichende Anzahl von Malen ausgeführt worden sind, zu erfordern, um als heiß betrachtet zu werden, als heiß identifiziert.

Die Identifizierung dessen, aus was sich die Spur zusammensetzt, wird durchgeführt, während die Spur ausgeführt wird. Eine Übersetzung der Spur wird ausgegeben, wenn die Spur ausgeführt wird, ist für eine Optimierung bei einem System, das eine Optimierung durchführt, verfügbar und wird in dem Code-Cache-Speicher erfaßt.

Eine besonders nützliche Spuranfangbedingung liegt vor, wenn die letzte interpretierte Verzweigung rückwärts genommen wurde. Eine nützliche Spurendebedingung liegt vor, wenn eine der folgenden drei Bedingungen erfüllt ist: (1) die letzte interpretierte Verzweigung wurde rückwärts genommen, (2) die Anzahl von interpretierten Verzweigungen überschritt einen Schwellenwert, oder (3) die Anzahl von nativen Befehlen, die für die Spur ausgegeben wurden, überschritt einen weiteren Schwellenwert.

Folglich muß gemäß der vorliegenden Erfindung eine Profilbildung lediglich an bestimmten wohldefinierten Programmadressen, wie z. B. den Zielen von rückwärts genommenen Verzweigungen, durchgeführt werden, und es müssen nicht komplizierte Profilbildungstechniken mit einem höheren Aufwand zum Identifizieren von Programm-Hot-Spots in Laufzeit verwendet werden. wenn eine solche Adresse heiß wird (d. h. ihr zugeordneter Zähler einen Schwellenwert überschreitet), wird die anschließende Sequenz von ausgeführten Blöcken (oder die Spur) spekulativ als ein heißer Pfad ausgewählt.

Dieses Schema wählt spekulativ die anschließende Sequenz von interpretierten Blöcken, die bestimmten heißen Verzweigungszielen – insbesondere bestimmten Verzweigungszielen, die wahrscheinlich Schleifenanfangsblöcke sind – folgen, als eine heiße Spur aus. Sogar obwohl dieses Schema keine mühsame Profilbildung umfaßt, kann die Qualität der Spuren, die durch diese Technik ausgewählt werden, exzellent sein. Wieso dieses Schema effektiv ist, kann man folgendermaßen verstehen: Sequenzen von heißen Blöcken sind häufig korreliert; bei einem laufenden Programm tendieren vollständige Pfade und nicht ein unverbundener Satz von Blöcken dazu, heiß zu werden.

Die vorliegende Erfindung liefert eine Vorrichtung für eine Spurauswahl mit einem reduzierten Profilbildungsaufwand.

Ein weiterer Vorteil der vorliegenden Erfindung besteht darin, daß eine Spur sogar dann aufgebaut werden kann, wenn dieselbe ungerichtete Verzweigungen enthält (Verzweigungen, deren Ergebnisse lediglich dann bekannt sind, wenn die Verzweigung ausgeführt wird, und die nicht durch einfaches Decodieren des Verzweigungsbefehls bestimmt werden können). Im Gegensatz dazu ist es für Spuraufbauschemata, die auf Verzweigungsvorhersageinformationen beruhen, ungünstig, ungerichtete Verzweigungen zu handhaben, da es keinen einfachen Weg gibt, um das Ergebnis solcher Verzweigungen vorherzusagen.

Ein weiterer Vorteil der Erfindung besteht darin, daß der Speicher, der für die Speicherung von Zählern erforderlich ist, verglichen zu herkömmlichen Profilbildungsschemata, die auf einer Verzweigungs- oder Grundblockzählung basieren, kleiner ist, da es bei der vorliegenden Erfindung nicht erforderlich ist, den Zählwert für jeden Block oder für jede Verzweigung zu überwachen.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend bezugnehmend auf die beiliegenden Zeichnungen näher erläutert. Es zeigen:

1 die Komponenten eines dynamischen Übersetzers, wie z. B. eines Übersetzers, bei dem die vorliegende Erfindung verwendet werden kann;

2 einen Fluß von Operationen bei einer Implementierung eines dynamischen Übersetzers, der die vorliegende Erfindung verwendet; und

3 einen Programmfluß über vier Blöcke eines Programmes hinweg, der veranschaulicht, daß es mehrere unterschiedliche Spuren geben kann, die mit einem, gemeinsamen Block beginnen.

Unter Bezugnahme auf 1 weist ein dynamischer Übersetzer einen Interpretierer 110 auf, der einen Eingangsbefehlsstrom 160 empfängt. Dieser "Interpretierer" stellt die Befehlsauswertungsmaschine dar; er kann auf mehrere Weisen implementiert sein (z. B. als eine Software-Hol-Decodier-Auswerte-Schleife, ein Just-In-Time-Compiler (Zur-rechten-Zeit-Compiler) oder sogar eine Hardware-CPU).

Bei einer Implementierung liegen die Befehle des Eingangsbefehlsstroms 60 in demselben Befehlssatz wie demjenigen der Maschine vor, auf der der Übersetzer läuft (Nativ-zu-Nativ-Übersetzung). In dem Nativ-zu-Nativ-Fall ergibt sich der Hauptvorteil, der durch den Übersetzer erhalten wird, aus der dynamischen Optimierung 150, die der Übersetzer durchführen kann. Bei einer anderen Implementierung liegen die Eingangsbefehle in einem anderen Befehlssatz als demjenigen der nativen Befehle vor.

Der Spurauswähler 120 identifiziert Befehlsspuren, die in dem Code-Cache-Speicher 130 gespeichert werden sollen. Der Spurauswähler ist die Komponente, die für das Zuordnen von Zählern zu interpretierten Programmadressen, zum Bestimmen, wann der Interpretiererzustand hin- und her-geschaltet werden soll (zwischen einem normalen Modus und einem Spuraufbaumodus), und zum Bestimmen, wann eine "heiße Spur" erfaßt worden ist, verantwortlich ist.

Ein Großteil der Arbeit des dynamischen Übersetzers findet in einer Interpretierer-Spurauswähler-Schleife statt. Nachdem der Interpretierer 110 einen Block von Befehlen interpretiert hat (d. h. bis zu einer Verzweigung), wird die Steuerung an den Spurauswähler 120 weitergegeben, um die Beobachtungen des Programmverhaltens durchzuführen, so daß derselbe Spuren für eine spezielle Verarbeitung und eine Plazierung in dem Cache-Speicher auswählen kann. Die Interpretierer-Spurauswähler-Schleife wird so lange ausgeführt, bis eine der folgenden Bedingungen erfüllt ist: (a) ein Cache-Treffer tritt auf, wobei in diesem Fall die Steuerung in den Code-Cache-Speicher springt, oder (b) ein heißes Start-Einer-Spur bzw. ein heißer Spuranfang wird erreicht.

Wenn ein heißes Start-Einer-Spur vorgefunden wird, schaltet der Spurauswähler 120 den Zustand des Interpretierers 110 um, so daß der Interpretierer die Spurbefehle ausgibt, bis die entsprechende Spurendebedingung (Bedingung (b)) erfüllt ist. An diesem Punkt ruft der Spurauswähler den Spuroptimierer 150 auf. Der Spuroptimierer ist verantwortlich für das Optimieren der Spurbefehle für eine bessere Leistungsfähigkeit auf dem zugrundeliegenden Prozessor. Nachdem die Optimierung durchgeführt ist, gibt der Codegenerator 140 den Spurcode tatsächlich in den Code-Cache-Speicher 130 aus und springt zu dem Spurauswähler 120 zurück, um die Interpretierer-Spurauswähler-Schleife fortzusetzen.

2 stellt den Betrieb einer Implementierung eines dynamischen Übersetzers dar, der die vorliegende Erfindung verwendet. Die durchgezogenen Pfeile stellen einen Steuerungsfluß dar, während der gestrichelte Pfeil die Erzeugung von Daten darstellt. In diesem Fall sind die erzeugten "Daten" tatsächlich ausführbare Sequenzen von Befehlen (Spuren), die in dem Cache-Speicher 130 von übersetztem Code gespeichert werden.

Das Wirken des Interpretierers 110, 210, 245 in dem dynamischen Übersetzer gemäß dem dargestellten Ausführungsbeispiel ist erweitert worden, so daß derselbe einen neuen Betriebszustand aufweist (im folgenden als "Spuraufbaumodus" bezeichnet): wenn sich derselbe in diesem neuen Zustand befindet, wird als ein Nebeneffekt der Interpretierung ein nativer Code für eine Spur ausgegeben. Für eine Nativ-zu-Nativ-Übersetzung beläuft sich dieser Prozeß des Ausgebens von Befehlen lediglich auf das Weiterleiten der relevanten Befehle von dem Eingangsbefehlsstrom 160. Für andere Übersetzungen werden die Eingangsbefehle in native Befehle übersetzt, wobei diese nativen Befehle in einem Puffer aufgezeichnet werden. Die übersetzten nativen Befehle werden daraufhin ausgeführt und dann ausgegeben – der Puffer von übersetzten Befehlen wird für eine weitere Verarbeitung (d. h. eine Optimierung 255 und Plazierung in den Cache-Speicher 260) verfügbar gemacht. Obwohl ein Block eine nützliche Einheit zum Übersetzen, Ausführen und Ausgeben ist, kann der Interpretierer übersetzte Befehle in anderen Einheiten ausgeben, und der Interpretierer kann die Übersetzungs-Ausführ-Schleife bezüglich einer Größe, wie z. B. einem Befehl oder einem Block) durchführen und übersetzte Befehle für eine weitere Verarbeitung in unterschiedlichen Einheiten (wie z. B. einem Block oder einer Spur) weiterleiten. Es sind ferner verschiedene alternative Implementierungen eines Interpretierers möglich, der übersetzte Befehle ausgibt.

Der native Code, der von dem Interpretierer 245 ausgegeben wird, ist bei dem nächsten Mal, wenn dieser Abschnitt des Programms ausgeführt wird, für eine Ausführung ohne die Notwendigkeit für eine Interpretation in dem Cache-Speicher 130 von übersetztem Code gespeichert (falls nicht Störfaktoren ergeben haben, daß dieser Code aus dem Cache-Speicher abgeräumt worden ist). In 2 ist der "Normal-Modus"-Betrieb des Interpretierers 110 bei 210 gezeigt, wobei der "Spuraufbaumodus"-Betrieb des Interpretierers bei 245 gezeigt ist.

Der Spuraufbaumodus 245 des Interpretierers 110 wird bei der vorliegenden Erfindung als ein Mechanismus zum Identifizieren der Erstreckung einer Spur ausgenutzt; der Spuraufbaumodus erzeugt nicht nur Daten (Befehle), die in dem Cache-Speicher gespeichert werden sollen, sondern derselbe spielt ferner bei dem Spurauswahlprozeß selbst eine Rolle. Wie es im vorhergehenden beschrieben wurde, leitet die vorliegende Erfindung eine Spurauswahl basierend auf einer begrenzten Profilbildung ein: bestimmte Adressen, die Spuranfangbedingungen erfüllen, werden überwacht, ohne daß die Notwendigkeit besteht, Profildaten für vollständige Spuren beizubehalten. Eine Spur wird basierend auf einer heißen Spuranfangbedingung ausgewählt. Diese Auswahl ist spekulativ, da die tatsächliche Spur, die ausgewählt wird, (und die bestimmt werden wird, während der Interpretierer in dem Spuraufbaumodus seinen Weg durch die Spur abarbeitet) nicht eine häufig ausgeführte sein muß, sogar obwohl dieselbe an einer häufig ausgeführten Startadresse beginnt. Zu dem Zeitpunkt, da eine Spur als heiß identifiziert wird (basierend darauf, daß der Ausführungszähler einen Schwellenwert überschreitet), ist die Erstreckung der Befehle, die die Spur bilden, nicht bekannt. Der Prozeß, daß der Interpretierer Befehle ausgibt, ist es, was die Erstreckung der Spur festlegt; der Spuraufbaumodus wird verwendet, um die Spur während der Ausführung zu entwirren.

Bezugnehmend auf 3 sind beispielsweise vier Blöcke eines Programmes gezeigt, um zu veranschaulichen, wie eine Identifizierung eines Spuranfangspunktes nicht an sich eine Spur vollständig identifiziert. Ein Block A erfüllt die Spuranfangbedingung (derselbe ist das Ziel einer Rückwärtsverzweigung von D). Bei vier Blöcken mit der Verzweigungsbeziehung, die in 3 gezeigt ist, verwenden die folgenden Spuren gemeinschaftlich denselben Anfangspunkt (A): ABCD, ABD, ACD. Die Spur, der das Programm zu dem Zeitpunkt folgt, zu dem der Zähler für A heiß wird, ist die Spur, die für eine Speicherung in dem Cache-Speicher ansprechend darauf, daß der Zähler heiß wird, ausgewählt wird – es könnte jede dieser drei Spuren sein (in Wirklichkeit kann es mehr als drei mögliche Spuren geben, falls sich die Spuren über D hinaus erstrecken).

Bezugnehmend auf 2 beginnt der dynamische Übersetzer mit dem Interpretieren von Befehlen, bis eine genommene Verzweigung interpretiert wird 210. An diesem Punkt wird eine Überprüfung durchgeführt, um zu erkennen, ob eine Spur, die an dem Ziel der genommenen Verzweigung beginnt, in dem Code-Cache-Speicher 215 existiert. Falls es eine solche Spur gibt (d. h. einen Cache-"Treffer"), wird die Steuerung an das vordere Ende dieser Version der Spur, die in dem Cache-Speicher 130 gespeichert ist, übergeben.

Wenn die Steuerung nach dem Ausführen der Befehle, die in dem Cache-Speicher 130 gespeichert sind, den Cache-Speicher über eine Ausgangverzweigung verläßt, wird ein Zähler, der dem Ausgangverzweigungsziel zugeordnet ist, als Teil der "Trampolin"-Befehlssequenz, die ausgeführt wird, um die Steuerung an den dynamischen Übersetzer zurückzugeben, inkrementiert 235. Wenn die Spur für eine Speicherung in dem Cache-Speicher 130 gebildet wird, wird in der Spur für jede Ausgangverzweigung in der Spur ein Satz von Trampolinbefehlen einbezogen. Diese Befehle (ferner bekannt als ein Übersetzungs-"Epilog") übergeben die Steuerung von den Befehlen in dem Cache-Speicher zurück an die Interpretierer-Spurauswähler-Schleife. Dem Trampolin, das jeder Ausgangverzweigung entspricht, ist ein Ausgangverzweigungszähler zugeordnet. Entsprechend der Speicherung für die Trampolinbefehle für eine Cache-mäßig gespeicherte Spur wird die Speicherung für die Spurausgangzähler ebenfalls automatisch zugewiesen, wenn der native Code für die Spur in den Cache-Speicher von übersetztem Code ausgegeben wird. Bei dem dargestellten Ausführungsbeispiel werden aus Übersichtlichkeitsgründen die Ausgangzähler mit den Trampolinbefehlen gespeichert; der Zähler könnte jedoch auch anderswo gespeichert werden, wie z. B. in einem Array von Zählern.

Wiederum bezugnehmend auf 215 in 2 wird, falls, wenn der Cache-Speicher auf eine Spur hin, die an dem Ziel der genommenen Verzweigung beginnt, untersucht wird, keine solche Spur in dem Cache-Speicher existiert, eine Bestimmung durchgeführt, ob eine "Spuranfang"-Bedingung existiert 230. Bei dem dargestellten Ausführungsbeispiel liegt eine Spuranfangbedingung dann vor, wenn die soeben interpretierte Verzweigung eine rückwärts genommene Verzweigung war. Alternativ könnte ein System unterschiedliche Spuranfangbedingungen verwenden, die mit rückwärts genommenen Verzweigungen kombiniert sind oder dieselben nicht umfassen: Prozeduraufruf-Befehle, Ausgänge aus dem Code-Cache-Speicher, Systemaufruf-Befehle oder Maschinenbefehl-Cache-Fehlgriffe (falls die Hardware eine solche Einrichtung zum Nachverfolgen solcher Dinge aufweist).

Eine rückwärts genommene Verzweigung ist eine nützliche Spuranfangbedingung, da dieselbe die Beobachtung ausnutzt, daß das Ziel einer rückwärts genommenen Verzweigung sehr wahrscheinlich (obwohl nicht notwendigerweise) der Start einer Schleife ist. Da die meisten Programme eine erhebliche Zeitdauer in Schleifen verbringen, sind Schleifenanfangsblöcke gute Kandidaten für mögliche Hot-Spot-Eintritte. Da es ferner üblicherweise weitaus weniger Schleifenanfangsblöcke in einem Programm als Ziele von genommenen Verzweigungen gibt, wird die Anzahl von Zählern und die Zeitdauer, die zum Aktualisieren der Zähler verwendet wird, erheblich reduziert, wenn man sich auf die Ziele von rückwärts genommenen Verzweigungen (die wahrscheinlich Schleifenanfangsblöcke sind) und nicht auf alle Verzweigungsziele konzentriert.

Falls die Spuranfangbedingung nicht erfüllt ist, tritt die Steuerung neu in den Grundinterpretiererzustand ein, wobei die Interpretation fortschreitet. In diesem Fall besteht keine Notwendigkeit dafür, einen Zähler beizubehalten; eine Zählerinkrementierung findet lediglich dann statt, falls eine Spuranfangbedingung erfüllt ist. Dies steht im Gegensatz zu herkömmlichen dynamischen Übersetzerimplementierungen, die Zähler für jedes Verzweigungsziel beibehalten. Bei dem dargestellten Ausführungsbeispiel werden lediglich den Adressen der Ziele der rückwärts genommenen Verzweigungen und der Ziele von Verzweigungen, die den Cache-Speicher von übersetztem Code verlassen, Zähler zugeordnet; folglich ermöglicht die vorliegende Erfindung einem System, weniger Zählerspeicherung zu verwenden, und weniger Zählerinkrementierungsaufwand zu erfordern.

Falls die Bestimmung, ob eine "Spuranfang"-Bedingung vorliegt 230, ergibt, daß die Spuranfangbedingung erfüllt ist, wird, falls kein Zähler für das Ziel existiert, ein Zähler erzeugt, oder, falls ein Zähler für das Ziel existiert, dieser Zähler inkrementiert.

Falls der Zählerwert für das Verzweigungsziel den Heiß-Schwellenwert 240 nicht überschreitet, tritt die Steuerung in den Grundinterpretiererzustand neu ein, wobei die Interpretation fortschreitet 210.

Falls der Zählerwert einen Heiß-Schwellenwert 240 überschreitet, ist dieses Verzweigungsziel der Beginn dessen, was als eine heiße Spur erachtet wird. An diesem Punkt wird der Zählerwert nicht länger benötigt, wobei dieser Zähler wieder verwendet werden kann (alternativ könnte der Zählerspeicher für eine Verwendung für andere Zwecke neu beansprucht werden). Dies stellt einen Vorteil über Profilbildungsschemata dar, die das Instrumentieren der Binär-Struktur umfassen.

Da die Profildaten, die durch die Spuranfangzähler gesammelt werden, während der Ausführung verwendet werden (während das Programm ausgeführt wird), können diese Zähler neu verwendet werden, wenn ihre Informationen nicht mehr erforderlich sind; insbesondere kann, sobald ein Spuranfangzähler heiß geworden ist, und verwendet worden ist, um eine Spur für eine Speicherung in dem Cache-Speicher auszuwählen, dieser Zähler neu verwendet werden. Das dargestellte Ausführungsbeispiel weist eine Tabelle von Spuranfangzählern mit einer festen Größe auf. Die Tabelle ist assoziativ – auf jeden Zähler kann mittels der Spuranfangadresse zugegriffen werden, für die der Zähler zählt. Wenn ein Zähler für eine spezielles Start-Einer-Spur neu verwendet werden soll, wird dieser Eintrag in der Tabelle einer Frei-Liste hinzugefügt, oder auf andere Weise als frei markiert.

Je niedriger der Schwellenwert ist, desto weniger Zeit wird bei dem Interpretierer aufgewendet, und desto größer ist die Anzahl von Start-von-Spuren, die möglicherweise heiß werden. Dies ergibt eine größere Anzahl von Spuren, die in den Code-Cache-Speicher erzeugt werden (und desto spekulativer ist die Auswahl von heißen Spuren), und die wiederum den Druck auf die Code-Cache-Ressourcen und folglich den Aufwand zum Verwalten des Code-Cache-Speichers erhöhen können. Andererseits gilt, je höher der Schwellenwert ist, desto größer der Interpretationsaufwand (z. B. das Zuweisen und das Inkrementieren von Zählern, die den Start-von-Spuren zugeordnet sind). Folglich muß die Auswahl des Schwellenwertes diese zwei Kräfte ausgleichen. Sie hängt ferner von dem tatsächlichen Interpretations- und Code-Cache-Verwaltungs-Aufwand bei der speziellen Implementierung ab. Bei unserer spezifischen Implementierung, bei der der Interpretierer als eine Software-Hol-Decodier-Evaluier-Schleife in C geschrieben worden ist, wurde ein Schwellenwert von 50 als der beste Kompromiß ausgewählt.

Falls der Zählerwert einen Heiß-Schwellenwert 240 überschreitet, wird, wie es im vorhergehenden angezeigt wurde, die Adresse, die diesem Zähler entspricht, als der Start einer heißen Spur erachtet. Zu dem Zeitpunkt, da die Spur als heiß identifiziert ist, bleibt immer noch die Erstreckung der Spur zu bestimmen (durch die Spurendebedingung, die im folgenden beschrieben wird). Es wird ferner darauf hingewiesen, daß die Auswahl der Spur als "heiß" ebenfalls spekulativ ist, nämlich darin, daß lediglich der Anfangsblock der Spur tatsächlich bemessen worden ist, heiß zu sein.

An dieser Stelle wechselt der Interpretierer von dem Normal-Modus 210 zu dem Spuraufbaumodus 245 über. In diesem Modus fährt die Interpretation, wie es im vorhergehenden beschrieben wurde, fort, ausgenommen darin, daß, während die Befehle interpretiert werden, die native Übersetzung der Befehle ebenfalls ausgegeben wird, so daß dieselben in dem Code-Cache-Speicher 130 gespeichert werden können. Der Interpretierer speichert die nativen Befehle in einen Puffer.

Wenn eine Spurendebedingung erreicht ist 250, wird der Puffer mit der vollständigen Spur einem Optimierer 255 ausgehändigt. Nach einer Optimierung werden die optimierten nativen Befehle in den Cache-Speicher plaziert, wobei der Zählerspeicher, der der Anfangsadresse der Spur zugeordnet ist, wiederverwendet wird 260. (Alternativ könnte der Zählerspeicher sogleich benutzt werden, wenn bestimmt worden ist, daß der Zähler den Heiß-Schwellenwert überschreitet). Ferner wechselt der Interpretierer 110, ausgelöst durch die Spurendebedingung, zu dem normalen Interpretiererzustand zurück.

Eine Spurendebedingung ist einfach eine heuristische Aussage, die aussagt, wann das Aufbauen der gegenwärtigen Spur gestoppt werden soll. Folgende Bedingungen sind Beispiele für einige mögliche Spurendebedingungen: das Beenden einer Spur, wenn eine rückwärts genommene Verzweigung erreicht wird, vermeidet ein unnötiges Entfalten von Zyklen und erfaßt ferner Schleifen; eine "Rückkehr"-Verzweigung kann eine nützliche Spurendebedingung sein, da dieselbe das Ende eines Prozedurkörpers anzeigen kann; im allgemeinen ist es wünschenswert ein Ende-Einer-Spur auszulösen, falls ein neues Start-Einer-Spur aufgetritt.

Bei dem dargestellten Ausführungsbeispiel ist die Spurendebedingung erfüllt, wenn (a) eine rückwärts genommene Verzweigung interpretiert wird, oder (b) wenn seit dem Eintreten in den Spuraufbaumodus eine bestimmte Anzahl von Verzweigungsbefehlen interpretiert worden ist (bei dem dargestellten Ausführungsbeispiel beträgt diese Anzahl 20) (das Beschränken der Anzahl von Verzweigungen an der Spur nach oben hin begrenzt die Anzahl von Stellen, an denen die Steuerung die Spur verlassen kann – je größer die Anzahl von Verzweigungen ist, die die Spur verlassen können, desto geringer ist die Wahrscheinlichkeit, daß die gesamte Spur verwendet werden wird, und desto größer ist die Wahrscheinlichkeit eines frühzeitigen Verlassens der Spur) oder (c) eine bestimmte Anzahl von nativen übersetzten Befehlen für die gegenwärtige Spur in den Code-Cache-Speicher ausgegeben worden ist. Die Grenze für die Anzahl von Befehlen in einer Spur ist ausgewählt, um übermäßig lange Spuren zu vermeiden. Bei dem dargestellten Ausführungsbeispiel sind dies 1024 Befehle, was es einer bedingten Verzweigung an der Spur ermöglicht, ihre Enden zu erreichen (dies folgt aus der Anzahl von Versetzungsbits in dem Befehl der bedingten Verzweigung auf dem PA-RISC-Prozessor, auf dem das dargestellte Ausführungsbeispiel implementiert ist).

Obwohl der Cache-Speicher groß genug proportioniert werden kann, so daß eine Ersetzung von Einträgen nicht erforderlich ist, wird typischerweise ein Ersetzungsschema verwendet. Ein Lösungsansatz besteht darin, den Cache-Speicher zu räumen, wenn derselbe voll ist und Platz für einen neuen Eintrag erforderlich ist. Ein weiterer Lösungsansatz, der Vorteile bietet, besteht jedoch darin, den Cache-Speicher basierend auf einem gewissen Anzeichen, daß sich der Arbeitssatz des Programms ändert, preemtiv zu räumen. Ein solcher preemtiver Lösungsansatz wird in der von der gleichen Anmelderin und am selben Tag eingereichten Patentanmeldung mit dem Titel "Eine preemtive Ersetzungsstrategie für einen dynamischen Cache-Speicher" beschrieben.

Wenn eine Spur aus dem Code-Cache-Speicher entfernt wird, wird der Speicher, der für die Zählerspeicherung für jede der Austrittsverzweigungen der Spur verwendet wird, automatisch wiederverwendet. Folglich ist die Speicherung für diese Austrittsverzweigungzielzähler in diesem Sinne "frei", da dieselben nicht unabhängig zugewiesen werden müssen, und nicht wie die anderen Zähler, die den Zielen interpretierter Verzweigungen zugeordnet sind, verwaltet werden müssen (diejenigen Ziele, die Spuranfangbedingungen erfüllt haben, aber für die der zugeordnete Zähler den "Heiß"-Schwellenwert noch nicht überschritten hat); wie es im vorhergehenden erörtert wurde, werden die Austrittsverzweigungzielzähler als ein Teil des Erzeugens des Trampolins für die Austrittsverzweigung zugewiesen.

Bei dem dargestellten Ausführungsbeispiel sind 1 und 2 wie folgt miteinander verwandt; einem Fachmann auf diesem Gebiet wird klar sein, daß diese Funktionen bei anderen Implementierungen auf andere Weisen organisiert werden können. Der Interpretierer 210 implementiert 210 und 245. Der Codegeneratoreinrichtung 140 implementiert 260. Der Spuroptimierer 150 implementiert 255. Der Spurauswähler 120 implementiert 215, 220, 230, 235, 240 und 250.

Das dargestellte Ausführungsbeispiel der vorliegenden Erfindung ist als eine Software implementiert, die auf einem Allzweckcomputer läuft, und die vorliegende Erfindung ist insbesondere für eine Softwareimplementierung geeignet. Bezüglich der Erfindung kann ferner eine Spezialzweckhardware nützlich sein (beispielsweise ein Hardware-"Interpretierer", eine Hardware, die das Sammeln von Profilbildungsdaten vereinfacht, oder eine Cache-Hardware).

Im vorhergehenden ist ein spezifisches Ausführungsbeispiel der Erfindung beschrieben worden. Zusätzliche Variationen werden Fachleuten auf diesem Gebiet offensichtlich sein. Obwohl beispielsweise die Erfindung in dem Kontext eines dynamischen Übersetzers beschrieben worden ist, kann dieselbe ferner bei anderen Systemen verwendet werden, die Interpretierer oder Just-In-Time-Compilierer (JITs) verwenden. Die Erfindung könnte ferner bei anderen Systemen verwendet werden, die jedes Nicht-native-System emulieren, wie z. B. bei einem Simulator. Folglich ist die Erfindung nicht auf die spezifischen Details und das dargestellte Ausführungsbeispiel, das in dieser Beschreibung gezeigt und beschrieben wurde, beschränkt. Vielmehr ist es die Aufgabe der anhängigen Ansprüche, alle solche Variationen und Modifikationen abzudecken, die in den Schutzbereich der Erfindung fallen.


Anspruch[de]
  1. Verfahren zum spekulativen Auswählen von Sequenzen von Programmblöcken eines Programms als eine heiße Spur für eine dynamische Übersetzung, mit folgenden Schritten:

    Interpretieren eines Eingangsbefehlsstroms (160);

    Bestimmen, ob ein spezieller Befehl in dem Eingangsbefehlsstrom (160) einer Spuranfangsbedingung (230) genügt;

    wenn dies so ist, Inkrementieren (235) eines Zählers, der dem Befehl zugeordnet ist;

    Bestimmen (240), ob der Wert des Zählers einen Schwellenwert übersteigt;

    wenn dies der Fall ist, Interpretieren (245) einer Sequenz von Programmblöcken des Eingangsbefehlsstroms, die dem speziellen Befehl folgt, zum Ausgeben nativer Befehle basierend darauf und Speichern der nativen Befehle in einem Puffer, zum Identifizieren der Sequenz als eine heiße Spur, ungeachtet dessen, ob die Sequenz von Programmblöcken tatsächlich eine häufig ausgeführte Spur ist; und

    bei Erreichen einer Spurendebedingung, Aushändigen der Sequenz an einen Optimierer (255).
  2. Verfahren gemäß Anspruch 1, bei dem der Interpretierer zwischen einem Normalmodus und einem Spuraufbaumodus, bei dem der Interpretierer als ein Nebeneffekt der Interpretation die nativen Befehle ausgibt, hin- und hergeschaltet werden kann, wobei, wenn der Zähler den Schwellenwert überschreitet, der Interpretierer in den Spuraufbaumodus (245) umgeschaltet wird, und, wenn sich der Interpretierer in dem Spuraufbaumodus befindet, und die Spurendebedingung erfüllt ist (250), der Interpretierer in den Normalmodus umgeschaltet wird.
  3. Verfahren gemäß Anspruch 1 oder 2, bei dem ansprechend auf das Identifizieren einer Spur als eine heiße Spur der entsprechende Zähler zur Verwendung für eine andere Adresse, die eine Spuranfangsbedingung erfüllt, wiederverwendet wird.
  4. Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem die Spuranfangbedingung erfüllt ist, wenn die zuletzt interpretierte Verzweigung rückwärts genommen wurde.
  5. Verfahren gemäß einem der Ansprüche 1 bis 4, bei dem die Spuranfangsbedingung eine Rückwärts-Verzweigung ist, und bei dem eine Übersetzung der heißen Spur in einem Cache-Speicher abgelegt wird.
  6. Verfahren gemäß Anspruch 5, bei dem, wenn eine Übersetzung in dem Cache-Speicher gespeichert wird, der entsprechende Zähler zur Verwendung für eine andere Adresse, die eine Spuranfangsbedingung erfüllt, wiederverwendet wird.
  7. Programm, das auf einem Computer läuft und dabei ein Verfahren nach einem der Ansprüche 1 bis 6 ausführt.
Es folgen 3 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com