Home Computer Hardware Site Map counter

Warum braucht ein Computer einen Cache?

Wer heute einen neuen Rechner kauft, wird mit Begriffen bombardiert. Einige sind noch leicht verständlich. So die Anzahl der Kerne, die für unabhängige Prozessoren stehen, oder die Taktfrequenz – je höher sie ist desto mehr Befehle kann der Prozessor ausführen. Doch was hat es mit einer Angabe wie „L3 Cache: 2 MB“ auf sich?

Dazu ein kleiner Ausflug in die Technologie von Speicherbausteinen. Als man die integrierte Schaltung entdeckte, nutzte man sie vor allem für den Ersatz von logischen Schaltungen, also Gattern oder bei größeren Integrationsdichten Subeinheiten von Prozessoren wie Addierwerke. Erst relativ spät, Ende der sechziger Jahre, ging man daran auch den Speicher mit integrierten Schaltungen herzustellen.

Die ersten verfügbaren Speicherbausteine waren statische Speicherbausteine, sogenannte SRAM (Static Random Acess Memory). Der Begriff verwirrt etwas, weil er suggeriert, das der Speicher sich nicht verändert, also z.B. beim Abschalten noch seinen Inhalt behält. Das war bei den vorher eingesetzten Ringkernspeichern der Fall, aber statische Speicher verlieren ihren Inhalt ohne Stromversorgung.

Ein statischer Speicher besteht aus einem Flop-Flop, einer Schaltung aus mindestens vier Transistoren, die zwischen zwei Zuständen umkippen kann. Dazu braucht man noch zwei Widerstände um sie von der Lese- und Schreibleitung abzukoppeln, wenn die Daten nicht ausgelesen oder geschrieben werden.

Der Statische Speicher hat einige Vorzüge. So kann man sehr schnell ein Bit in die Schaltung schreiben oder ein Bit auslesen. Wenn auf eine Speicherzelle nicht gelesen oder geschrieben wird, so benötigt sie auch wenig Strom. Das ist bei Arbeitsspeicher allerdings oft nicht so relevant, da hier oft der Inhalt verändert oder gelesen wird. Wenn dies selten erfolgt, z.B. bei dem Speicher für die Einstellungen des BIOS, dann ist dies aber von Vorteil, weil dann eine handelsübliche Knopfzelle genügend Strom für einige Jahre Betrieb liefert.

SRAM hat aber einen fundamentalen Nachteil: Bedingt durch die Verschaltung der Transistoren benötigt er viel Platz. Im Mittel 16-mal mehr als der DRAM Speicher.

Der DRAM Speicher erschien erst einige Jahre nach dem SRAM-Speicher und die ersten PC‘s der Welt wie der Altair 8800 setzten daher SRAM Speicher ein. Ein DRAM Speicher hat einen viel einfacheren Aufbau. Im Silizium ist eine Zone, anders als bei Transistoren üblich nicht nur gering, sondern sehr stark dotiert. Sie kann daher sehr viele Elektronen aufnehmen und wirkt als Kondensator. Unter dem Dotieren versteht man das gezielte einbringen von Fremdatomen, die dann aus dem Halbleitermetall Silizium ein leitfähigeres Element machen.

Neben dieser, oder heute auch über dieser, ist ein Transistor angebracht. Er ist mit Datenleitungen gekoppelt, die an Basis und Emitter angebracht sind. Der Kollektor ist mit einer Leseleitung verbunden. Ein DRAM Baustein besteht aus Tausenden, Millionen, heute Milliarden dieser Transistoren in einem Array. Meist wird das Gesamtarray noch in kleinere Felder unterteilt, doch das Prinzip ist das gleiche.

Durch diesen einfachen Aufbau braucht ein DRAM-Bit viel weniger Platz und die Herstellung ist einfacher, bei einem Flip-Flop für ein SRAM müssen vier Transistoren und zwei Widerstände (heute gängiger: 6 Transistoren wobei zwei als Widerstände fungieren) miteinander verschaltet werden. Das ist bei einem DRAM nicht notwendig.

Den Namen DRAM bekam der Speicher durch einen Nachteil: Da Silizium ein Halbleiter ist, bleiben die Ladungen nicht in der dotierten Zone, sondern wandern langsam in die Umgebung ab. Der Speicher verliert also die Information, was er enthält. Nach einer Millisekunde wären alle Bits Nullen. Um dies zu verhindern, muss er „aufgefrischt“ werden. Dazu liest man zeilenweise nacheinander die Transistoren einer Spalte aus, verstärkt den Inhalt und schreibt ihn zurück. Während dieser Zeit kann auf diese Zeile nicht zugegriffen werden. Dafür gibt es eine eigene Schaltung pro Zeile, den Schreib/Leseverstärker.

Dieses Wiederauffrischen war anfangs ein Nachteil in der Anwendung, weil die Mikroprozessoren nicht darauf ausgerichtet waren. Sie taten dies nicht automatisch. Beim Apple programmierte Steve Wozniak eigens eine Routine, die dies erledigte und die periodisch aufgerufen wurde. Doch da der dynamische Speicher schon bei seiner Einführung durch den einfacheren Aufbau viermal preiswerter als statischer Speicher war, setzte er sich bald durch und Mikroprozessoren erhielten eine Logik, die einen vom Takt abgeleiteten Refreshimpuls abgab. Dieser musste nur noch durch eine Logik an die Speicherbausteine übergeben und mit den Adresssignalen gekoppelt werden. Heute werden DRAM Bausteine nicht mehr einzeln verkauft, sondern als Riegel mit 4,8 oder 16 dieser Bausteine und dort ist die nötige Logik für den Refresh schon enthalten.

Als der DRAM Anfang der siebziger Jahre aufkam, verdrängte er sehr rasch den SRAM vom Markt. Doch schon zehn Jahre später wurde ein Nachteil des Konzeptes offenbar. Dadurch, dass die Ladung in einem Kondensator gespeichert ist und Tausende von Zellen jeweils einen Schreib/Leseverstärker haben, ist der Speicher recht langsam. In einem Flip-Flop, dem Speicherelement eines SRAM wechselt die Ladung eines Transistors dauernd. Im Prinzip ist das Flip-Flop ein Ring aus Leitungen mit Transistoren als kurze Verzögerungsstrecken, durch die ein Impuls jagt. Ein Flip-Flop kann daher sehr schnell ausgelesen werden.

In einem DRAM ist der Kondensator wie eine kleine Batterie: eine Batterie ist weder sofort vollgeladen noch kann man den ganzen Inhalt auf einmal abholen. Bei einem Kondensator im Miniaturformat dauert es zwar nur einige Nanosekunden die Ladung zu schreiben und den größten Teil wieder auszulesen, doch das ist bei modernen Prozessoren eine Ewigkeit. Daneben teilen sich viele Transistoren eine Leitung und daran angeschlossen einen Schreib-/Leseverstärker, der die Ladung schreibt oder ausliest. Bis die Ladung diese lange Leitung um ein gewisses Potenzial (üblich 0,1 V) erhöht, vergeht ebenso Zeit. Nach dem Auslesen kann zudem nicht sofort die Ladung wieder geschrieben werden (sie muss aber in die Speicherzelle zurückgeschrieben werden, sonst ist sie verloren). Das alles braucht Zeit.

Ein Speicherzyklus, also das Lesen eines Bits, das Rückschreiben des Bits durch den Schreibleseverstärker und dazwischen kurze Zeiten der Erholung dauert bei einem DRAM Speicher daher lange. Selbst heute sind noch Werte von 60 bis 70 ns üblich. Erst danach kann der Prozessor auf das gleiche Bit erneut zugreifen. Wenn, was sehr oft vorkommt, der Prozessor nur die Daten auslesen muss, aber nicht verändert zurückschreibt, weil die nächsten Daten aus einer anderen Speicherzelle kommen, dann gilt eine andere Größe, die mittlere Zugriffszeit.

Diese beiden Parameter Speicherzyklus (Memory Cycle) und Zugriffszeit (Random Access Time) sind daher zwei Geschwindigkeitsparameter, die bei Speicherbausteinen angeben werden.

Anfangs lag der Speicherzyklus bei 2000 ns, er sank dann in den Siebzigern schnell ab, aber ab den Achtziger Jahren dann kaum noch. 1980 betrug er noch 500 ns, bei einer Zugriffszeit von 150 ns. Heute liegt er bei 30 bis 40 ns bei einer Zugriffszeit von 7,5 bis 12,5 ns.

Voll assoziativer CacheDas ergab ein Problem. Der Kehrwert von 40 ns ist 25 MHz. Ein Prozessor könnte also 25 Millionen Mal pro Sekunde dieselbe Speicherstelle abrufen. Nun tut er dies selten, aber selbst wenn man sich auf den Zugriff auf verschiedene Speicherzellen beschränkt, kommt man nur auf eine Frequenz von maximal 100 MHz. Das ist weitaus niedriger als die 2-4 GHz, mit denen ein Rechner heute getaktet ist. In 11 Jahren hat sich die Zugriffszeit nur verdoppelt, während die Taktrate der Prozessoren von 200 auf 3800 MHz anstieg.

Als das Problem zuerst auftauchte, führte man den „Wait State“ ein. Anstatt nach einem Zugriff die nächsten Daten abzurufen, wartete der Prozessor einen oder zwei Taktzyklen lang. Da viele Befehle nur auf die internen Speicherplätze im Prozessor zugriffen oder mehr als einen Zyklus zum Abarbeiten brauchte, machte dies den Rechner nur wenig langsamer. Das war bei den Rechnern der 80286-Generation mit 8-12v MHz Taktfrequenz noch eine Lösung des Problems. Wenn man sich es leisten konnte, konnte man den Speicher auch mit sehr schnellen Speicherbausteinen ohne Waitstate bestücken.

Doch als die nächste Generation, der 80386 mit 16 MHz auf den Markt kam, war der Speicher noch nicht schneller geworden. Wartezyklen einzubauen war auch keine Lösung, denn der 80386 führte auch die meisten Befehle schneller als sein Vorgänger aus. Dazu stieg die Taktfrequenz von 8-10 auf 16, später 20-40 MHz. Mit Wartezyklen hätte man einen Großteil der Leistung verschenkt.

Die Lösung war die Einführung des Caches. Caches waren nichts Neues. Man hatte sie bei den Großrechnern schon vorher eingeführt. Diese waren schon früher so schnell gewesen, dass sie auf dasselbe Problem stießen. Die Lösung war ein Zwischenspeicher aus dem schnellen, aber teuren SRAM. Er wird in kleine Einheiten, Cachelines genannt unterteilt. Jede Cacheline hat nun eine Kopie eines kleinen RAM-Bereichs. Wenn der Prozessor Daten braucht, die er nicht im Cache findet so werden die Daten vom Speicher angefordert und an den Prozessor übermittelt, aber auch in eine freie Cacheline eingelesen. Das dauert nun lange, denn der Arbeitsspeicher bestimmt die Geschwindigkeit. Während der Prozessor weiter arbeitet, liest eine Elektronik weiter Daten vom Arbeitsspeicher und füllt damit die Cacheline auf. Sie greift dazu auf die Adressen zu, die direkt den Daten folgen die gerade angefordert wurden. Wenn nun der Prozessor die nächsten Daten braucht, schaut die Elektronik zuerst nach, ob die Daten nicht in einer Cacheline sind und wenn das der Fall ist, dann kann der Prozessor nun auf den schnellen SRAM-Speicher zugreifen. Zu jedem Cache gehört ein Cachecontroller, der neben dem Lesen und Schreiben (auch die Ergebnisse landen zuerst im Cache) auch Buch führt, welche Cachelines am längsten nicht benutzt wurden, weil der Cache sie verwerfen muss, wenn neue Daten benötigt werden. Die ersten Cachelines waren beim 386 16 Byte lang, bis zum Pentium III waren sie auf 32 Bytes angewachsen und seit dem Pentium 4 sind sie 64 Byte lang, dass passt sehr gut zum Burstmodus von DDR-RAM, der einen 64 Bit Datenbus hat und 8 Transfers nacheinander durchführt, also 64 x 8 Bit = 64 Byte transfereirt.

Es gibt verschiedene Bauformen für Caches. Sie resultieren daraus, dass ein Cache wenn er effektiv sein soll ein Problem hat: wie stelle ich schnell fest ob die Daten die der Prozessor braucht im Cache sind oder nicht? Jeder Cache besteht aus einer Indextabelle welche die Adresse (oder den Teil der Adresse den man braucht) und pro Eintrag in dieser Tabelle einer Cacheline, die eine feste Anzahl von Bytes beginnend an dieser Adresse enthalten. Damit der Prozessor nicht warten muss, sollte man nun schnell feststellen ob die Adresse sich in der Tabelle befindet.

Man unterscheidet im Prinzip drei verschiedene Auslegungen um dieses Problem zu lösen:

Anfangs war der Cache noch ein eigener Speicherbereich. Es gab neben dem Arbeitsspeicher noch acht Speicherchips für den Cache auf dem Motherboard direkt neben dem Prozessor. Mit dem 486-Prozessor wanderte dann der Cache in den Prozessor und ein Zweiter war außerhalb angebracht – es etablierte sich ein mehrstufiges System. Der im Prozessor untergebrachte war der schnellste. Dafür bestand er aus Flip-Flops mit mehr als 6 Transistoren (bis zu 12), die schneller ausgelesen werden konnten. Der Cache war dafür klein (beim 486er: 16 Kbyte). Der Außen angebrachte war aus normalen SRAM Bausteinen aufgebaut, deutlich größer (64 oder 256 KByte), aber langsamer, beim Zugriff auf ihn mussten wieder Wartezyklen eingeschoben werden. Der interne bekam die Bezeichnung „Level 1 Cache“ oder „L1-Cache“ und der äußere entsprechend L2-Cache / Level 2 Cache. Zuerst sucht der Prozessor im L1-Cache. Findet er dort die Daten so ist das okay, wenn nicht so sucht der Cache Controller im L2-Cache, der viel größer ist. Das ist langsamer als der L1-Cache, aber noch erheblich schneller als das DRAM. Analog landen Daten zuerst im L1-Cache und werden dann in den L2-Cache geschrieben und von dort erst in den Arbeitsspeicher. Je größer der Cache ist, desto größer die Wahrscheinlichkeit die Daten vorrätig zu haben. Sehr oft hat der L1-Cahce auch viel mehr Datenleitungen als der L2-Cache. Dadurch kann er auch mehr Daten auf einmal übertragen.

Dafür ist er auch langsamer. Das hängt zum einen mit der Technologie zusammen - langsamere Caches sind billiger und brauchen auch weniger Strom, weil die Transistoren bei jedem Takt schalten und dabei ein Verluststrom entsteht. Bedeutender ist aber das zum Cache ein Controller gehört der die Tabellen verwaltet welche Adressen gecacht werden. Das Durchsuchen der Tabellen braucht auch Zeit und diese Verzögerung nennt man Latenz. Je größer der Cache ist, desto größer die Tabellen und desto mehr Zeit braucht man zum Durchsuchen. Bei Pentium III hatte der L1-Cache eine Latenz von 3 Takten und der L2-Cache eine von 10 Takten. Beim Pentium 4 hatte man diese Latenzen gesenkt auf 2/7 Takte. Auch wenn 10 Takte Latenz beim L2-Cache beim Pentium III schon fast auf dem Niveau des damals üblichen SD-RAM (das mit 100 MHz getakt war, also mit 10 Takten Latenz eine Taktfrequenz von 1 GHz erlaubte, nahe der maximalen Taktfrequenz von 1,4 GHZ bei einem Pentium III, so wurde dies durch den größeren Datenbus ausgeglichen, denn es wurde gleich eine ganze Cacheline von 32 Bytes in den L1-Cache übertragen. Auf die folgenden Bytes konnte also dann mit 3 Takten Latenz zugegriffen werden.

Direct mapped CacheDas System funktioniert deswegen, weil Programme aus dem Aufruf vieler kleiner Routinen bestehen und Programmierer Variablen, die zusammengehören auch zusammen deklarieren. Dadurch ist die Wahrscheinlichkeit sehr groß, wenn man einen Wert vom Speicher braucht, dass man die nächsten auf den darauffolgenden Adressen folgenden Daten (Befehle oder Variablen) auch bald benötigt und wenn man diese vorab in den Cache lädt, hat man sie, wenn man sie braucht in diesem schnellen Speicher.

Auf dieser Überlegung funktioniert auch der DDR-Speicher, der nichts mit einer kommunistischen Republik zu tun hat, sondern die Abkürzung für Double Date Rate ist. Ende der Neunziger Jahre ging man, weil die Prozessoren nun schon erheblich schneller als der Speicher waren, über zu synchronem Speicher. (SDRAM) Da wie erläutert der Cache immer die darauffolgenden Daten lädt, baute man diesen Mechanismus in die Elektronik der Speicherchips ein. Beim ersten Speicherzyklus fingen die Chips, schon während dieser lief, an mit jedem Takt an eine neue Speicherzelle nach der angeforderten zu lesen. Jeweils einen Takt nach dem Ende des ersten Speicherzyklus stand das nächste Bit oder Datenwort, je nach Organisation des Speichers an den Ausgängen zum Lesen an, wo der Cachecontroller es abholte. Das war ein Burstbetrieb, bei dem so 16 Datenworte hintereinander abgeliefert wurden. Allerdings konnte der Speicherbaustein nun nicht mehr mit einem beliebigen Takt betrieben werden, sondern nur einem festgelegten Basistakt, der anfangs bei 100 MHz lag, heute bei etwa 1333 MHz. DDR-Speicher unterscheidet sich von dem synchronen Speicher dahin gehend, dass er pro Takt zwei Worte überträgt, je eines an der ansteigenden und abfallenden Flanke eines Taktimpulses. Intern nutzt DDR-Speicher auch mehrere Speicherbänke (bis zu 8) und Prefetch um die Daten nach der Anlaufzeit schnell zu liefern. Diese ist nach wie vor langsam, so beträgt sie bei DDR3 RAM etwa 10-13,75 ns für den Erstzugriff, die folgenden Bits folgen dagegen in 1,25 bis 1,75 ns Abstand. Die Zahl der Worte ist auf die Größe heutiger Cachelines ausgelegt, da es zum einen kaum Prozessoren ohne Cache gibt und zum andern diese sonst zum Füllen der Cacheline einen zweiten Zugriff starten müssten.

DDR Speicher hat daher sehr hohe Datenübertragungsraten, auch weil immer 64 Bit auf einmal übertragen werden. Dazu kommt, dass man heute Speicher in Modulen anordnet, die nacheinander angesprochen werden. Damit hat das erste Modul eine Ruhepause, wenn der nächste Speicherzugriff erfolgt. Auch das ist nichts Neues. Als Seymour Cray die Cray 2 mit DRAM entwickelte, kompensierte er dessen Langsamkeit nicht nur mit Caches, sondern setzte 256 Module ein – erst nach 256 Speicherzugriffen wäre also das erste wieder dran gewesen. Dagegen sind die 2-8 Module, die im PC heute üblich sind, Kleinvieh.

Wer programmieren kann, kann selbst herausfinden, wie langsam der Speicher ist. Man muss dazu nur auf einen großen Speicherbereich (einige Hundert Megabyte, jedenfalls deutlich größer als der Cache) zufällig irgendwelche Daten auslesen. Man wird bald feststellen, dass dieses Programm um den Faktor 10 langsamer läuft, als wenn man den gleichen Speicherbereich sequenziell von vorne bis hinten abarbeitete, wo die Strategie des vorausschauenden Lesens „Prefetch“ genannt, dann wirkt.

Folgendes Pascal-Programm greift z.B. auf 100 Millionen Speicherstellen einmal linear zu und einmal zufällig verteilt. Beim nicht mehr ganz taufrischen Rechner (Baujahr 2009) braucht der erste Zugriff 2,3 s, der Zweite dagegen 20,2 s.

program TestSpeicher;
           
uses
  Classes,SysUtils;

const
  max = 1000 * 1000 * 100;

var
  feld: array [1..max] of Integer;
  startzeit, endzeit: Ttime;
  i: integer;
  adresse: integer;
  wert: int64;

begin
  // Linearer Zugriff
  Startzeit := Now;
  for i := 1 to max do
  begin
    adresse := random(max);
    // zusätzlich damit Laufzeit der Randomroutine die Messung nicht verfälscht
    wert := feld[i];
    feld[i] := 10 * wert;
  end;
  Endzeit := now - Startzeit;
  Writeln('Linearer Zugriff: ', FormatDateTime('ss.zzzz', Endzeit));
  // Zufälliger Zugriff
  Startzeit := Now;
  for i := 1 to max do
  begin
    adresse := random(max);
    wert := feld[adresse];
    feld[adresse] := 10 * wert;
  end;
  Endzeit := now - Startzeit;
  Writeln('Zufälliger Zugriff: ', FormatDateTime('ss.zzzz', Endzeit));
  readln;
end.

Prozessoren haben heute intern bis zu 3 Cacheebenen, wobei diese Caches mehrere Megabyte groß sein können. Für Großrechner sind Prozessoren auf dem Markt, die einen L4 Cache eingeführt haben. Die Caches stellen einen großen Teil der Transistoren auf einem Prozessor. Der Intel Core i7-3960X Prozessor hat z.B. 2,27 Milliarden Transistoren und sechs Prozessorkerne. Jeder Kern hat einen 32 KByte großen L1-Cache, einen 256 großen L2-Cache und alle zusammen teilen sich einen 12 MByte großen L3-Cache. Nimmt man nur 6 Transistoren pro Bit an (im Regelfall haben die schnelleren Caches mehr Transistoren) so braucht man alleine 919 Millionen Transistoren für die Caches auf diesem Prozessor.

Referenzen:

Andreas Stiller, ct 12/2014 S.174: Matrix reloaded Von Matrizen und magischen Compiler-Fähigkeiten.

Intel: 80386 Hardware Reference Manual

Harvey G. Cragon: Memory Systems and Pipelined Processors

 

Veröffentlichungsdatum des Artikels: 5.10.2013
Letzte Überarbeitung´: 20.9.2014

Zum Thema Computer ist auch von mir ein Buch erschienen. "Computergeschichte(n)" beinhaltet, das was der Titel aussagt: einzelne Episoden aus der Frühzeit des PC. Es sind Episoden aus den Lebensläufen von Ed Roberts, Bill Gates, Steve Jobs, Stephen Wozniak, Gary Kildall, Adam Osborne, Jack Tramiel und Chuck Peddle und wie sie den PC schufen.

Das Buch wird abgerundet durch eine kurze Erklärung der Computertechnik vor dem PC, sowie einer Zusammenfassung was danach geschah, als die Claims abgesteckt waren. Ich habe versucht ein Buch zu schreiben, dass sie dahingehend von anderen Büchern abhebt, dass es nicht nur Geschichte erzählt sondern auch erklärt warum bestimmte Produkte erfolgreich waren, also auf die Technik eingeht.

Die 2014 erschienene zweite Auflage wurde aktualisiert und leicht erweitert. Die umfangreichste Änderung ist ein 60 Seiten starkes Kapitel über Seymour Cray und die von ihm entworfenen Supercomputer. Bedingt durch Preissenkungen bei Neuauflagen ist es mit 19,90 Euro trotz gestiegenem Umfang um 5 Euro billiger als die erste Auflage. Es ist auch als e-Book für 10,99 Euro erschienen.

Mehr über das Buch auf dieser eigenen Seite.

Hier geht's zur Gesamtübersicht meiner Bücher mit direkten Links zum BOD-Buchshop. Die Bücher sind aber auch direkt im Buchhandel bestellbar (da ich über sehr spezielle Themen schreibe, wird man sie wohl kaum in der Auslage finden) und sie sind natürlich in den gängigen Online-Plattformen wie Amazon, Libri, Buecher.de erhältlich.


© des Textes: Bernd Leitenberger. Jede Veröffentlichung dieses Textes im Ganzen oder in Auszügen darf nur mit Zustimmung des Urhebers erfolgen.
Sitemap Kontakt Impressum / Datenschutz Neues Hier werben / advertisment here Buchshop Bücher vom Autor Top 99