DE19721685A1 - Bestimmung von Engpässen bei Pufferspeichern - Google Patents

Description

Technisches Gebiet

Die Erfindung betrifft ein Verfahren zur Bestimmung von Engpässen, wie sie bei Pufferspeichern in Computersyste­ men, insbesondere solche mit mehreren Prozessoren und ge­ meinsamem Speicher, auftreten.

Stand der Technik

Bei Hochleistungs-Rechnersystemen wird vor jeder Zen­ traleinheit ein Pufferspeicher (CACHE) vorgesehen, um den Zugriff auf den relativ langsamen Hauptspeicher scheinbar zu beschleunigen. Dabei wird benutzt, daß mit Zugriff auf eine Speicherstelle mit hoher Wahrscheinlichkeit auf die­ se oder eine benachbarte recht bald noch mehrere erfol­ gen. Dieser Effekt wird Lokalität des Zugriffs genannt.

Dabei besteht der Cache aus einer Anzahl von Einträgen, die als Cache-Zeilen (cache line) bezeichnet werden und mehreren, aufeinanderfolgende Speicherworten entsprechen. Zu jedem gepuffertem Speicherwort wird auch dessen Adres­ se gespeichert, so daß bei jedem Zugriff entschieden wer­ den kann, ob die gespeicherten Daten gültig sind. Übli­ cherweise erhalten die Cache-Zeilen einen Alterungs-Zähler, so daß eine neue Cache-Zeile diejenige ersetzt, die am längsten nicht benutzt wurde.

Besonders wirksam ist ein Cache, wenn mehrere Prozesse gemeinsame Datenbereiche verwenden, weil diese dann so häufig referiert werden, daß sie im Cache verbleiben. Dies trifft insbesondere für das Betriebssystem zu, des­ sen Teile natürlichweise einer gemeinsamen Benutzung durch die Anwendungsprogramme unterliegen.

Andererseits wird die Leistung eines solchen Systems we­ sentlich reduziert, wenn der als Verdrängung bezeichnete Prozeß des Auslagerns einer Cache-Zeile zugunsten einer neuen überwiegt. Dieses unerwünschte Verhalten wird, wenn es gehäuft auftritt, auch als "thrashing" bezeichnet. Der dabei auftretende Effekt, daß das gewünschte Datenelement nicht im Cache vorhanden ist, sondern aus dem Hauptspei­ cher geholt werden muß, wird üblicherweise als "cache miss" bezeichnet.

Es sind Programme bekannt, die absichtlich "thrashing" herbeiführen, um über die dadurch bewirkte signifikant verlängerte Laufzeit die Cache-Größe per Software zu be­ stimmen. Umfaßt beispielsweise ein Cache 128 Zeilen à 64 Bytes, so wird das Programm eine Tabelle von mehr als 128 Zeilen à 64 Bytes anlegen, aber immer nur das erste Byte einer Zeile benutzen, da die üblichen Cache-Speicher im­ mer nur ganze Cache-Zeilen verwalten. Solange das Pro­ gramm in einer Schleife weniger als 128 Zeilen dieser Ta­ belle zyklisch benutzt, werden alle diese in den Cache-Spei­ cher geladen und bleiben dort erhalten. Werden jedoch mehr als 128 Zeilen zyklisch benutzt, so verdrängt jede Benutzung eine Cache-Zeile, so daß die Leistung um bei­ spielsweise den Faktor fünf reduziert wird.

Es ist jedoch umgekehrt erstrebenswert, die Effekte von "thrashing" möglichst zu vermeiden. Zu diesem Zweck wer­ den Einrichtungen verwendet, die die Verdrängungen verur­ sachenden Adressen aufzeichnen und für eine Auswertung zur Verfügung stellen.

Für die in neueren Prozessoren integrierten Caches sind Diagnoseeinrichtungen vorgesehen, die die Anzahl der "cache misses" pro Prozeß aufgezeichnen können. Damit kann dann zumindest der verursachende Prozeß identifi­ ziert werden und dieser dann durch weitere, meist gedank­ liche, Analyse diagnostiziert und ggf. verbessert werden. Ein Hilfsmittel hierzu wird auch als "profiling" bezeich­ net, bei dem über einen Zeitgeber das zu untersuchende Programm regelmäßig unterbrochen wird und der Stand des Befehlszählers notiert wird, um herauszufinden, an wel­ chen Stellen das Programm am häufigsten verweilt, weil diese Stellen häufig mit den Stellen koinzidieren, bei denen "thrashing" verursacht wird. Diese Methoden liefern jedoch lediglich Hinweise, an Hand derer das Programm ge­ danklich analysiert werden kann und durch probeweise Ver­ änderung eine Verbesserung versucht werden kann, die je­ doch immer nur auf das zu analysierende Programm allein bezogen sind.

Es sind ferner Hardware-Einrichtungen bekannt, die die Hardware-Vorgänge in einem System zu erfassen erlauben und im Folgenden als "Logger" bezeichnet werden. Hierzu sind insbesondere die als Logik-Analysatoren bekannten Einrichtungen verwendbar; es können aber auch spezielle Geräte hierzu eingerichtet werden, deren Eigenschaften sich aus der Beschreibung ergeben. Mit diesen könnten auch die Adressen ermittelt werden, die zu einem "cache miss" führen. Da es sich allerdings um Speicher-Adressen handelt und die Zentraleinheit heute überwiegend über Adressumsetzung verfügt, die einer virtuellen Program­ madresse auch während der Laufzeit andere absolute Spei­ cheraddressen zuordnen kann, erscheint es aussichtslos, mittels eines Logik-Ahalysators hier verwertbare Informa­ tion bereitstellen zu können. Dies gilt umso mehr, wenn mehrere Cache-Speiche über ein Bussystem mit einem ge­ meinsamen Speicher verbunden sind, weil die Adressüber­ setzungstabellen in jeder Zentraleinheit unterschiedlich sind und zu unterschiedlichen Zeiten verändert werden.

In der Patentschrift US 5,630,097 wird ein Verfahren be­ schrieben, mit dem eine Ursache von Leistungsverlusten, die durch ungünstige Verwendung des Cache entstehen, ver­ mieden werden können. Hierzu wird zunächst der Cache der­ art erweitert, daß eine Anzahl von Adressen von dem Cache-Mechanismus ausgeschlossen wird. Diese Adressen werden bestimmt, indem ein permanent vorhandener Zusatz die einen "cache miss" verursachenden Adressen durch "sampling" aufzeichnet und dem Betriebssystem zur Verfü­ gung stellt. Diese Einrichtung dient dabei dazu, einen speziellen Fall zu kompensieren, der insbesondere bei "direct mapped" Caches gehäuft auftritt und durch dynami­ sche Neuzuordnung von virtuellen zu absoluten Adressen entschärft werden kann. Da die Einrichtung permanent vor­ handen ist und vom Betriebssystem bedient wird, kann die­ ses auch mitführen, wie lange welche Zuordnung von virtu­ ellen zu absoluten Adressen und umgekehrt gültig ist und die Einträge der Diagnoseeinrichtung entsprechend bewer­ ten. Allerdings werden hierdurch nur die Folgen einer speziellen Variante von Engpässen in ihrer Wirkung redu­ ziert.

Im Verlaufe der Erprobung der nachfolgend beschriebenen Erfindung wurde ein Effekt diagnostiziert, der abstrakt bereits als "false sharing bekannt ist, dessen Diagnose als Ursache von Leistungseinbußen bei Cache-Speichern je­ doch bislang so nicht bekannt war.

Wie oben bereits dargestellt, ist die gemeinsame Benutzung von Speicherbereichen durch mehrere Prozesse auf dersel­ ben CPU anzustreben, da der Cache hierbei seine volle Wirkung entfaltet. Dies gilt auch, wenn zwei verschiedene Prozesse zwar dieselbe Cache-Zeile benutzen, aber völlig getrennte Daten, z. B. ausschließlich das erste und das letzte Byte einer solchen Zeile, solange beide Prozesse auf derselben Zentraleinheit ablaufen bzw. auf Zen­ traleinheiten, die denselben Cache verwenden.

Anders jedoch liegt der Fall, wenn zwei Prozesse diesel­ ben Daten verwenden, aber auf getrennten Zentraleinheiten ablaufen, die auch getrennte Caches verwenden. Dann muß bei jeder Alteration des Zugriffs die Cache-Zeile in den jeweils anderen Cache geladen werden. Aus diesem Grunde sind die Betriebssysteme so ausgelegt, daß Prozesse mit gemeinsamem Speicher möglichst auf derselben Zentralein­ heit ablaufen.

Anders liegt der Fall, wie mit Hilfe der Erfindung dia­ gnostiziert wurde, beim "false sharing". Dadurch, daß die Prozesse getrennte Speicherbereiche umfassen, wird das Betriebssystem diese durchaus verschiedenen Prozessoren zuordnen und die Leistung des Systems beeinträchtigen. Weitere Erläuterungen sind weiter unten in der Beschrei­ bung dargestellt.

Aufgabe der Erfindung ist es daher, ein Verfahren anzuge­ ben, mit dem Engpässe bei der Cache-Benutzung in Mehrpro­ zessorsystemen mit mehreren Cache-Speichern aufgedeckt werden können.

Beschreibung der Erfindung

Entgegen der prinzipiell richtigen Annahme, daß ein Rück­ schluß von absoluten Adressen auf die zugehörigen Pro­ gramme im nachhinein nicht zuverlässig ist, verwendet die Erfindung einen Logger, der an das Bussystem angeschlos­ sen ist, das die Cache-Speicher mit dem Hauptspeicher koppelt. Dieser Logger registriert die Adressen, die zu einem Datentransfer von dem Hauptspeicher oder einem an­ deren Cache führen. Sinnvollerweise wird auch mit aufge­ zeichnet, welcher Cache Auslöser für diesen Transfer war. Zu Beginn und am Ende der Aufzeichnung werden die Adress­ umsetzungs-Tabellen des Betriebssystems abgespeichert und nur diejenigen Adressen verwendet, die in beiden Tabellen gleiche Zuordnung haben.

Er ergibt sich dabei, daß eine große Anzahl von häufig zu "cache misses" führenden Adressen in beiden Adressum­ setzungs-Tabellen dieselbe Zuordnung haben und daher zu identifizierbaren Programmteilen führen.

Es handelt sich also um ein Verfahren zur Bestimmung von Engpässen bei Pufferspeichern in Rechnern mit mehreren Zentraleinheiten und gemeinsamem Speicher, wobei eine Adressübersetzung von virtuellen in absolute Adressen in den Zentraleinheiten stattfindet, vor Beginn und nach En­ de einer Meßperiode die Adressumsetzungstabellen ausge­ lesen werden, während einer Meßperiode die Zugriffe auf den gemeinsamen Speicher mit absoluten Adressen aufge­ zeichnet und nach Ende der Meßperiode lediglich die ab­ soluten Adressen in virtuelle Adressen umgesetzt werden, die in beiden Adressumsetzungstabellen gleich sind.

Kurzbeschreibung der Zeichnungen

Es zeigt

Fig. 1 ein Blockschaltbild eines Rechnersystems, auf dem die Erfindung durchgeführt werden kann.

Ausführungsbeispiel der Erfindung

In Fig. 1 ist ein Rechnersystem dargestellt, bei dem zwei Zentraleinheiten 11a, 11b über ein Bussystem 10 mit zwei Speichermoduln 20a, 20b gekoppelt sind. Die Anzahl der Zentraleinheiten und Speichermoduln kann dabei nach den Einsatzanforderungen gewählt werden; es ist auch möglich, nur lediglich einen Speichermodul zu verwenden. Die An­ zahl der Zentraleinheiten beträgt mindestens zwei.

Jede Zentraleinheit 11a, 11b besteht aus mindestens einem Prozessor 12a, 12b, einer Adressumsetzungseinrichtung 13a, 13b und einem Pufferspeicher 14a, 14b, üblicherweise als "Cache" bezeichnet. Es ist ohne weiteres möglich, daß die Adressumsetzung 13a, 13b in den jeweiligen Prozessor integriert ist, und daß mehr als ein Prozessor auf einen gemeinsamen Cache arbeiten. Ein Cache speichert mehr als ein Byte oder Wort, sondern immer eine ganze Reihe, Cache-Line genannt, von z. B. 64 Byte, und umfaßt z. B. 128 Cache-Zeilen.

Die Cache-Speicher verwenden ein Verfahren zur Daten-Kohärenz, mit dem sichergestellt ist, daß die Cache-Spei­ cher transparent sind, d. h. daß sich das Gesamtsy­ stem, abgesehen von der schnelleren Ausführung, so ver­ hält, als ob die Cache-Speicher nicht vorhanden seien. Beispielsweise wird bei Anforderung eines Bytes oder Da­ tenwortes eine gesamte Cache-Zeile aus einem der beiden Speicher 20a, 20b angefordert und im jeweiligen Cache 14a, 14b abgelegt. Fordert danach ein Prozeß auf einer der anderen Prozessoren ein Byte derselben Adresse an, so wird die Speicheranforderung meist von dem Cache befrie­ digt, der dieses Byte gepuffert hat.

Wie oben dargelegt, bewirkt ein häufigeres Nachladen eines Cache aus einem anderen oder dem Speicher eine wesentli­ che Leistungseinbuße. Um diesen Effekten auf die Spur zu kommen, wird wie folgt vorgegangen:
An den Bus 10 wird ein Logger 30 angeschlossen. Dieser ist mit den Daten-, Adress- und Steuerleitungend des Bus­ systems 10 verbunden. Durch Programmierung des Loggers wird festgelegt, welche Signalzustände auf den Steuerlei­ tungen eine Speicherung von Eingangssignalen, hier denen auf den Adressleitungen, bewirken soll. Indem diese Pro­ grammierung so eingerichtet wird, daß Speicheranforderun­ gen seitens eines Cache selektiert werden, werden alle Anfragen von Cache-Lines protokolliert. Dabei werden aus­ gewählt Steuerleitungszustände mit aufgezeichnet, aus de­ nen beispielsweise ermittelt werden kann, welche Zen­ traleinheit 11a, 11b die Anforderung gestellt hat, und ob es sich um einen Lese- oder Schreibzugriff handelt. Je nach verwendetem Bussystem kann diese Information auch auf den Datenleitungen erscheinen, oder es können keine getrennten Daten- und Adressleitungen vorhanden sein. Durch den Logger, der einen größeren, nicht gezeigten Speicher, enthält, werden also die ausgewählten Adress­ worte zusammen mit der weiteren Information in eben die­ sem Speicher abgelegt. Dieser Speicher ist in der Lage, die anfallenden Daten mit der maximalen, auf dem Bus auf­ laufenden Geschwindigkeit abzulegen. Weniger günstig, aber auch möglich, wenn der Speicher nicht ausreicht, ist eine Aufzeichnung in Stichproben, bei beispielsweise nur jeder sechzehnte auslösende Transfer tatsächlich gespei­ chert wird.

Die Speicherung kann von einem Programm, welches in einer der Zentraleinheiten 11a, 11b abläuft, ausgelöst werden. Dies kann entweder über eine speziell hierzu eingerichte­ te Signalleitung oder, bevorzugt, durch ein Auslöse-Muster, beispielsweise den Zugriff auf eine bestimmte, sonst nicht verwendete absolute Adresse, erreicht werden.

Bevor das Programm die Speicherung auslöst, stellt es ei­ ne Kopie der Adressumsetzungstabellen aller Prozessoren, die bei der Analyse berücksichtigt werden sollen, auf ei­ nem (nicht gezeigten) Massenspeicher sicher. Diese Opera­ tion ist von System zu System unterschiedlich und hängt davon ab, ob diese Tabellen in der Adressumsetzung selbst abgelegt sind, ob das Betriebssystem für Verwaltungszwec­ ke eine Kopie führt, die auch verwendbar ist, oder in dem Speicher, der dann meist mit über den Cache geführt ist, ablegt. Auf jeden Fall besteht diese Tabelle aus minde­ stens drei Spalten; der absoluten Adresse, wie sie dem Cache präsentiert wird, der virtuellen Adresse im Adress­ raum eines Prozesses und eine Angabe über den Prozeß selbst. In der Regel, insbesondere in Betriebssystemen, deren Namen auf -ix endet, wird jedem Prozeß eine fort­ laufende Nummer zugeordnet, welche erst nach etlichen Stunden Betriebszeit wiederverwendet wird. Zusätzlich werden die Informationen über die bezogenen Prozesse si­ chergestellt, die beispielsweise Diagnoseinformation wie Symboltabellen u.ä. enthalten.

Danach wird die Aufzeichnung mit dem Logger 30 gestartet; entweder manuell oder per Signal. Ist die Aufzeichnung beendet, werden erneut die Addressumsetzungstabellen in der gleichen Art wie vor Beginn der Aufzeichnung abgespei­ chert. Sodann kann die Information aus dem Logger 30 auf einen Rechner, bevorzugt den Rechner, auf dem die Adres­ sumsetzungstabellen abgelegt sind, übertragen. Diese Ope­ ration ist zeitunkritisch, da die Adressumsetzungstabelle und sonstige Verwaltungsinformation bereits sicherge­ stellt ist. Alle diese Daten können sicherlich auch auf einen anderen Rechner übertragen und dort ausgewertet werden, wenn dies zweckmäßig ist, um beispielsweise wei­ tere Messungen durchführen zu können.

In einem nächsten Schritt werden die abgespeicherten Adressumsetzungstabellen zusammengeführt. Hierbei werden zunächst die vor Beginn der Messung ermittelten zu einer zusammengeführt, indem die Nummer des Prozessors hinzuge­ fügt und aus den vielen per-Prozessor-Tabellen eine ein­ zige mit jetzt (mindestens) vier Spalten, nämlich Abso­ lutadress, virtuelle Adresse, Prozeßnummer und Prozes­ sornummer, erzeugt wird, die bevorzugt nach Absolutadres­ se sortiert ist.

Die dadurch entstehenden beiden Adresstabellen von vor und nach der Aufzeichnung werden nun derart gemischt, daß nur in beiden identische Zeilen verwendet werden. Damit bleibt zwar nur Information über solche Prozesse übrig, die während der Messung weder erzeugt noch beendet noch im Speicher verschoben wurden. Dies sind jedoch, wie die Erprobung der Erfindung gezeigt hat, überwiegend die im folgenden Schritt benötigten Zeilen.

Der folgende Schritt besteht darin, die Aufzeichnung des Loggers 30 nach Absolutadressen zu sortieren und eine Ta­ belle zu erzeugen, in der zu jeder Absolutadresse die Häufigkeit des Auftretens und die weiteren Angaben, ins­ besondere die Unterscheidung in Schreib- und Leseopratio­ nen sowie die verursachende Zentraleineheit, notiert sind. Dies kann im übrigen möglicherweise bereit vom Log­ ger durchgeführt werden, damit dieser eine große Menge aufzeichnen kann, und hängt von dessen Ausstattung ab.

Die von dem Logger bereitgestellte Tabelle und die ge­ mischte Tabelle der Adressübersetzung werden nunmehr zu einer Ergebnistabelle gemischt, indem für gleiche Abso­ lutadressen die jeweiligen Spalteneinträge zusammenge­ führt werden; die Absolutadresse könnte entfallen und wird lediglich zum besseren Verständnis durch den die Ta­ belle auswertenden Fachmann mitgeführt. Diese Tabelle kann nunmehr ausgewertet werden, indem sie beispielsweise primär nach Häufigkeit und sekundär nach Prozeßnummer sortiert wird. Damit werden diejenigen Prozesse mit ihrer virtuellen Adresse aufgeführt, die besonders häufig zu einer das System ausbremsenden Speicheranforderung ge­ führt haben. Im übrigen kann mittels gegebenenfalls vor­ handenen Diagnoseinformation das betroffene Unterprogramm und die darin relative Adresse ermittelt und mit aufge­ führt werden.

Es ergab sich, daß eine große Anzahl von signifikanten Hinweisen zu analysieren war. Unter anderem wurde ein Fall gefunden, in dem mehrere Prozesse die gleiche Cache-Line benutzten, um, durch Unterbrechungen im Millisekunden-Takt gesteuert, einen Zeitzähler mitzuführen. Das "false sharing" war nicht beabsichtigt und sollte durch Auffül­ len der verwendeten Datenstruktur auf die Größe einer Cache-Line vermieden werden. Seitdem wurde jedoch die Größe der Cache-Line verdoppelt, ohne die Software anzu­ passen. Dieser Effekt konnte durch das angegebene Verfah­ ren in relativ kurzer Zeit gefunden und damit auch vor­ beugend beseitigt werden. Vorbeugend insofern, als die betroffene Komponente in dem System gar nicht aktiv be­ nutzt wurde, sondern lediglich das System unnötig ver­ langsamte. Bei aktueller Benutzung wären wiederum neue Engpässe aufgetreten, die den eigentlich erwarteten Lei­ stungsgewinn der neuen Generation von Rechnern mit der doppelt so langen Cache-Line nicht in voller Höhe hätten wirksam werden lassen.

Claims (2)

1. Verfahren zur Bestimmung von Engpässen bei Puffer­ speichern in Rechenanlagen mit mehreren Prozessoren, die mit einer Adressübersetzung mittels einer Adress­ übersetzungstabelle von virtuellen in absolute Adres­ sen arbeiten und die jeweils mit einem Pufferspei­ cher, absolute Adressen benutzend, verbunden sind, welche Pufferspeicher über ein Bussystem auf einen gemeinsamen Speicher zugreifen, mit den Merkmalen:

• - ein Logger, welcher die Adressen auf dem Bussystem zusammen mit Steuerinformation, ausgelöst durch vorbestimmte Kombinationen von Steuersignalen, auf­ zuzeichnen vermag, ist mit dem Bussystem verbunden,
• - zu Beginn eines Analysevorgangs werden die Adress­ übersetzungstabellen der betroffenen Prozessoren abgelegt,
• - danach werden mittels des Loggers zumindest die ab­ soluten Adressen der Zugriffe der Pufferspeicher aufgezeichnet,
• - zum Ende der Aufzeichnung werden die Adressüberset­ zungstabellen der betroffenen Prozessoren in glei­ cher Art wie zu Beginn abgelegt,
• - sodann werden die von dem Logger aufgezeichneten absoluten Adressen dahingehend bearbeitet, daß für lediglich diejenigen die absolute Adresse in virtu­ elle Adressen umgesetzt wird, deren Einträge in den abgelegten Adressübersetzungstabellen gleich sind.

2. Verfahren nach Anspruch 1, wobei zu den absoluten Adressen auch ein den anfordernden Pufferspeicher be­ zeichnendes Kennzeichen und die Art des Zugriffs auf­ gezeichnet werden.