Mach dem Speicher Beine

Als Ergänzung zu meiner kleinen Zusammenfassung der Schritte wie man einen Prozessor beschleunigt möchte ich heute ergänzen, wie man den Speicher beschleunigt. Wie bei meinem ersten Aufsatz geht es dabei um Computerentwicklung allgemein und nicht nur um Mikroprozessoren, die meisten Technologien wurden sogar entwickelt, bevor es überhaupt Mikroprozessoren gab.

Das Problem

Das grundlegende Problem war schon immer, und daran hat sich bis heute nichts geändert, das Speicher langsamer als die Logik war. Das muss nicht so sein. Jeder Prozessor, selbst der einfachste benötigt etwas lokalen Speicher zumindest für die Arbeitsregister, heute auch Caches (dazu später) auf dem Chip. Man kann also Speicher aus denselben Elementen aufbauen, wie Logik die in Prozessoren vorherrscht. Nur macht man dies aus wirtschaftlichen Gründen nicht. Dazu ein Beispiel. Gerade auf den Markt gekommen ist der Ryzen 4750G Prozessor. Er hat 9,8 Milliarden Transistoren und kostet 275 Euro. In etwa genauso viel kosten heute 64 GB DDR4 RAM also Speicher.

Man kann aus vier Transistoren ein Element konstruieren, das ein Bit speichert, ein Flip-Flop. Mit 9,8 Milliarden Transistoren könnte man also rund 2,5 Milliarden Bits speichern oder rund 300 MByte. Das sind aber nur ein Zwanzigstel der Speichermenge, die der Arbeitsspeicher für denselben Preis speichert. Arbeitsspeicher in der Technologie aufzubauen, die man für die Logik verwendet geht, ist also sehr teuer. Die Technologie für RAM ist dagegen billiger, aber sie ist langsamer und dieses Problem muss man lösen.

Das war übrigens schon immer so, auch wenn die Technologien wechselten. Die ersten Speicher speicherten die Information akustisch, als Wellen in einer Röhre gefüllt mit Quecksilber, dann kamen magnetisch-mechanische Speicher in Mode (Trommelspeicher, die nach dem Prinzip einer Festplatte arbeiteten, nur war es keine Platte, sondern eine Zylinderoberfläche) und dann die rein magnetische Speicherung auf Ringkernspeichern. Nach einer kurzen Episode, in der tatsächlich für den Speicher dieselbe Technologie wie für die Logik eingesetzt wurde, (heute als SRAM bezeichnet) kam dann der bis heute übliche DRAM auf, bei dem die Information in dotiertem Silizium gespeichert wird, das sich wie ein Kondensator verhält.

Alle Technologien für Speicher haben das Problem, das sie langsamer als die Logik ihrer Zeit waren. Man kann dies an einer Größe festmachen, die früher gängig war, bei aktuellem DDR-RAM aber durch eine Liste von Timings ersetzt wurde, die Zugriffszeit und Zykluszeit.

Jeder Prozessor arbeitet mit einem Takt und bei jedem Takt macht er nur eine Aufgabe. Spricht er den Speicher an, so legt er bei einem Takt die Informationen auf den Bus und verständigt den Speicher das er Daten holen oder schrieben möchte und beim nächsten Takt will er diese Information holen oder schreiben (es können auch mehrere Takte sein, im Folgenden gehe ich aber mal von einem Takt aus, was bei allen modernen Prozessoren auch so ist). Jeder Speicher hat eine Zugriffszeit, das ist die Zeit, die vergeht, zwischen der Anforderung des Prozessors als Signal auf dem Bus und dem Anliegen der Daten auf dem Bus die vom Speicher kommen. Bei den meisten Speichertypen gibt es noch eine zweite Zeit, die Zykluszeit. Sie entsteht dadurch, dass das Auslesen von Daten meistens den Inhalt zerstört und er neu geschrieben werden muss und auch Schreib-/Lesepuffer Zeit brauchen bis ihre Ladung abgebaut ist. Das obige Flip Flop ist eine Ausnahme von der Regel es hat keine Zykluszeit, bzw. diese ist genauso lange wie die Zugriffszeit. Die Zykluszeit gibt an, wie lange man nach einer Anforderung warten muss, bis man erneut eine Anfrage an den Speicher stellen muss.

Wer wie ich seine ersten Versuche Anfang der Achtziger mit einem C64, CPC 464, Sinclair Spectrum oder ähnlichem Computer machte, der hatte in diesem DRAM Bausteine mit einer Zugriffszeit von 150 bis 200 ns und einer Zykluszeit von 260 bis 350 ns. Prozessoren dieser Zeit (in 8 Bit Rechnern) hatten Taktfrequenzen von 1 bis 4 MHz), der Kehrwert davon waren dann 250 bis 1000 ns, das heißt, die Prozessoren konnten verzögerungsfrei lesen. Das galt, aber nur weil es die langsamsten Prozessoren ihrer Zeit war. Großcomputer arbeiteten dagegen damals schon mit bis zu 250 MHz und für diese waren dann diese Zugriffszeiten viel zu langsam.

Das Dumme nur: Seitdem ist die Taktfrequenz eines PC um etwa das Tausendfache auf 2 bis 5 GHz gestiegen, die Zugriffzeit von DRAM aber nur auf 7 bis 10 ns gesunken, also den Faktor 30. Speicher ist im Vergleich zum Prozessor noch langsamer geworden und unsere Computer wären unerträglich langsam, wenn man diesen Nachteil nicht kaschieren würde. Löst man es nicht, so muss der Prozessor warten, bis der Speicher bereit ist, das kam auch vor, als die Prozessoren nur etwas schnellerals das RAM ihrer Zeit  waren. Rechner der AT-Ära gab es mit 0, 1 oder 2 Wartezyklen zu kaufen – je nach Taktfrequenz und verbautem Speicher.

Taktiken das Problem zu lösen

Es gibt im Prinzip folgende Methoden die Langsamkeit des Speichers zu kaschieren:

• Zwischenspeichern
• Vorausschauendes Lesen
• Verteilter Zugriff
• Lesen größerer Datenmengen als eigentlich benötigt

Alle Techniken basieren im Wesentlichen auf einer Eigenschaft, sowohl von Code wie Daten: die Linearität. Daten werden nach Deklaration nacheinander im Speicher abgelegt, größere Strukturen wie Felder sind von sich aus linear organisiert. Code wird meist linear abgewickelt – die Ausnahme sind Sprünge in Unterprogramme und bei Schleifen. Das bedeutet, mit einer großen Wahrscheinlichkeit benötigt man im nächsten Taktzyklus die Daten, die an der nächsten Adresse im Speicher sitzen. Alle Techniken beruhen darauf, diese bereitzustellen, bevor überhaupt eine Anforderung kommt und dann fällt die Zugriffszeit weg oder ist verkürzt. Wechselt die abgerufene Region, dann ist der Vorteil weg. Das ist besonders bei Code ein Problem, weshalb heute Prozessoren sich große Mühe geben Sprünge vorherzusagen und die Daten schon vorab vom Speicher abzuholen.

Zwischenspeichern

Für das Zwischenspeichern baut man einen kleinen Speicher in einer schnellen Technologie wie den obigen Flip-Flops. Er nimmt Daten, auf die man eventuell nochmals braucht oder bald braucht. Die Technologie kommt in verschiedensten Techniken vor.

Seymour Crays Supercomputer hatten einen Instruktionsbuffer. Er nahm die letzten Anweisungen auf, gab es einen Sprung, der meist bei einer Schleife am Schleifenende ist, so wurden die Instruktionen nochmals abgearbeitet und befanden sich im Instruktionsbuffer, mussten also nicht aus dem Speicher geholt werden.

Speicherbänke (Erklärung folgt noch) speicherten ebenfalls die nächsten Informationen aus der Adresse die der aktuellen folgt, in einem kleinen Buffer, den sie automatisch füllten und auf den so verzögerungsfrei zugegriffen werden konnte.

Die gängigste Umsetzung des Prinzips ist aber der Cache, der zuerst bei der IBM System 360 eingeführt wurde. Das Prinzip ist recht einfach. Immer wenn Daten oder Code geholt wird, landet eine Koppe in einem schnellen Zwischenspeicher dem Cache. Der Prozessor sieht bei jedem Transfer zuerst nach, ob sich die Daten im Cache befinden und nutzt diese und erst dann zum Speichern. In der Praxis kann die Verwaltung eines Caches durchaus komplex sein, doch dafür verweise ich auf meinen Artikel auf der Webseite. Heutige Prozessoren haben mehrere Caches, die unterschiedlich groß und schnell sind und oft auch aufgeteilt nach Daten oder Code. Sie machen heute von der Chipfläche und Transistorenzahl sogar das Groß des Die aus.

Vorausschauendes Lesen

Wegen der Lokalität und Linearität macht es Sinn Daten zu lesen, bevor der Prozessor sie überhaupt anfordert, auch wenn man sie später verwerfen muss. Praktisch alle Techniken setzen dies, da es wenig Aufwand macht, zusätzlich ein. In der Intel x86 Serie hatte der 80386 zuerst Unterstützung für einen externen Cache, beim Nachfolger 80486 war dann der erste Cache intern verbaut, es gab aber noch einen externen Cache.

Die einfachste Form ist der Prefetch, den z. B. Der 8086 hatte. Da nach jedem Lesen eines Befehls (Speicherzugriff) dieser immer erst dekodiert und ausgeführt werden musste hatte die I/O Einheit die mit dem Speicher kommuniziert, einige Takte lang nichts zu tun und sie nutzte dies, um ein Byte einzulesen. Das kostet wenig Aufwand ist uns weit verbreitet.

Caches sind in Cachelines organisiert, die länger als ein Befehlswort sind, bei aktuellen Prozessoren sind sie z.B. 8 Bytes lang. Auch hier liegt es nahe das man die nächsten Bytes einer Cacheline bald benötigt und es wird immer eine komplette Cacheline aus dem Speicher geholt.

Speicherbänke, die bei Großcomputern verbreitet waren (heute noch in Form von Speicherkanälen auf dem Mainboard) lasen auch meist das nächste Befehlswort aus und speicherten es in einem schnellen Speicher zwischen.

Vorausschauendes Lesen ist aber die Basis für die Performance von DDR-Speicher. Nach dem ersten langsamen Zugriff, der mit der Zugriffszeit eines DRAM erfolgt, liest der Speicher intern nicht die angeforderten Daten aus, sondern 8 weitere Blöcke zu jeweils 64 Bit und überträgt sie bei jedem Flankenwechsel, also zwei Transfers pro Takt. Die Größe ist abgestimmt auf die Cachelines, da es wie bei einer Cacheline genau 64 Bit pro Anforderung sind.

Verteilter Zugriff

Die bei Großcomputern gängigste Taktik ist es, den Speicher in einzelne Sektionen genannt Speicherbänke zu unterteilen. Ein Großcomputer konnte durchaus 256 Speicherbänke haben. Sie waren im Adressbereich so angeordnet, dass ein sequenzieller Zugriff jeweils auf eine andere Speicherbank ging und so im Idealfall bei n Speicherbänken erst nach n Taktzyklen die gleiche Bank wieder zum Zug kam. So kann man die Zykluszeit auf die Zugriffszeit reduzieren. Um auch diese zu umgehen, setzen die Bänke die Technik des Prefetch ein und haben so die Daten der nächsten Adresse schon bereit, wenn der nächste Zugriff kommt. Bei Crays Supercomputern funktionierte das so gut, das diese Computer ohne Caches auskamen und trotzdem es keine Wartezyklen bei linear ausgeführtem Code gab. Dabei war die CPU schon bei der Cray 1 viermal schneller als der Speicher. Ein PC hat meist 2 oder 4 Speicherkanäle, die technisch je eine Bank sind und meist einem Modulsteckplatz entsprechen. Server haben meist mehr Speicherbänke üblich sind 8 oder 16 Kanäle, die jeweils mit einem Modul bestückt werden. Durch Caches ist der Vorteil bei einem PC allerdings relativ klein und liegt bei einer Verdopplung von einem auf zwei Kanäle unter 10 % Geschwindigkeitszuwachs.

Lesen größerer Datenmengen

Auch diese Technik findet man häufig. Angesprochen wurde, das Cachelines länger als ein Befehl sind. Das hat allerdings vor allem organisatorische Gründe. Das Lesen großer Datenmengen hat im eigentlichen Sinn die Aufgabe, gleichzeitig mehrere Befehle oder große Datenblöcke in die Kern-CPU zu transferieren. Der Intel Itanium Prozessor fasste immer drei Instruktionen zu einem Block zusammen der bei einem Transfer übermittelt wurde. Im Allgemeinen heißt die Technik VLIW (Very Long Instruction Word) wenn mehrere Befehle zu einem Block zusammengefasst werden oder SIMD (Single Instruction, Multiple Data) wenn eine Instruktion mehrere Daten bearbeitet und dies ebenfalls einen Block ergibt.

Bei Großrechnern baute man Bussysteme, die relativ breit waren, 256, 512 oder 1024 Bit auf einmal lasen oder schreiben und dabei auch mehrere Speicherbänke parallel ansprachen. Damit waren die Daten für mehrere Instruktionen in Prozessor, selbst wenn der Speicher nur einen Bruchteil dessen Taktfrequenz hatte, man gleich also dessen Langsamkeit damit aus, das das Bussystem viel mehr Daten transferierte, als der Prozessor auf einmal verarbeiten konnte, so hatte der Speicher Zeit, bis diese verarbeitet, waren neue Daten bereitzustellen-

Beim heutigen PC findet man die Technik bei Grafikkarten, wo die CPU festverlötet ist. Dann ist es leichter die vielen Leitungen die man benötigt. zum Speicher zu ziehen, als wenn die CPU getrennt ist und jeder Pin eine bestimmte Mindestgröße haben muss, damit er sich nicht zu leicht bei der Montage verbiegt. Dagegen sind Kupferleitungen auf einer Platine viel dünner und enger platzierbar.

Testen des Effekts der Maßnahmen

Das folgende C-Programm ist eine einfache Matrizenmultiplikation. Sei wird dreimal durchgeführt, wobei jedoch die Schleifenreihenfolge variiert. Wer das Programm übersetzt, wird feststellen, dass die Ausführungsgeschwindigkeit variiert, weil nur in einer Reihenfolge die Caches voll ausgenützt werden. Je nach Größe der Caches (Variieren der Konstante DIM) kann eine Schleifenreihefolge, die zum regelmäßigen Cache-Miss führt, die Geschwindigkeit des Programms um den Faktor 100 heruntersetzen.

#pragma hdrstop

#pragma argsused

#include <tchar.h>

#include <stdio.h>

#include <time.h>

#define DIM 1000

typedef double mat[DIM][DIM];

mat a, b, c;

void clear()

{

for (int i = 0; i < DIM; i++)

for (int j = 0; j < DIM; j++) {

c[i][j] = 0.0;

b[i][j] = i * 1.2;

a[i][j] = j * 1.1;

}

}

int _tmain(int argc, _TCHAR* argv[]) {

time_t zeit1, zeit2;

clear();

zeit1 = time(NULL);

for (int k = 0; k < DIM; k++)

for (int j = 0; j < DIM; j++)

for (int i = 0; i < DIM; i++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„kji: %f\n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000);

clear();

zeit1 = time(NULL);

for (int k = 0; k < DIM; k++)

for (int i = 0; i < DIM; i++)

for (int j = 0; j < DIM; j++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„kij: %f \n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000.0);

clear();

zeit1 = time(NULL);

for (int i = 0; i < DIM; i++)

for (int j = 0; j < DIM; j++)

for (int k = 0; k < DIM; k++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„ijk: %f\n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000.0);

clear();

zeit1 = time(NULL);

for (int j = 0; j < DIM; j++)

for (int i = 0; i < DIM; i++)

for (int k = 0; k < DIM; k++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„jik: %f\n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000.0);

clear();

zeit1 = time(NULL);

for (int i = 0; i < DIM; i++)

for (int k = 0; k < DIM; k++)

for (int j = 0; j < DIM; j++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„ikj: %f\n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000.0);

clear();

zeit1 = time(NULL);

for (int j = 0; j < DIM; j++)

for (int k = 0; k < DIM; k++)

for (int i = 0; i < DIM; i++) {

c[i][j] += a[i][k] * b[k][j];

}

zeit2 = time(NULL);

printf(„jki: %f\n“, difftime(zeit2, zeit1));

printf(„%.0f\n“, 2.0*DIM*DIM*DIM / difftime(zeit2, zeit1) / 1000000.0);

printf(„Ende“);

getchar();

return 0;

}