SecBCache: Evaluating Banked Interleaved Word-Granularity Sector Cache for gather/scatter Operations on Sparse Data

Moderne Computer werden oft nicht durch die Geschwindigkeit begrenzt, mit der sie rechnen können, sondern durch die Geschwindigkeit, mit der sie Daten bewegen können. In der Welt des Hochleistungsrechnens, in der Maschinen komplexe Probleme wie die Kartierung der Ausbreitung von Krankheiten, die Analyse sozialer Netzwerke oder die Simulation des Klimawandels bewältigen, ist die häufigste Aufgabe nicht das Zerlegen von Zahlen, sondern das Abrufen derselben aus dem Speicher. Dies gilt insbesondere beim Umgang mit „spärlichen“ (sparse) Daten, einem Begriff, der Informationen beschreibt, bei denen der Großteil des potenziellen Raums leer ist. Stellen Sie sich eine riesige Tabelle vor, in der nur einige verstreute Zellen Zahlen enthalten, während der Rest leer ist. Wenn ein Computer versucht, diese verstreuten Zahlen zu lesen, muss er oft auf unvorhersehbare Weise im Speichersystem umherspringen, ein Prozess, der als indirekter Zugriff bekannt ist. Da diese Sprünge zufällig sind, kann der Computer nicht leicht vorhersagen, welche Daten als Nächstes benötigt werden, was die Aufgabe, Informationen vom Speicher zum Prozessor zu bewegen, zu einem Hauptengpass macht, der das gesamte System verlangsamt und Energie verschwendet.

Um zu verstehen, warum dies schwierig ist, muss man betrachten, wie Computer Daten derzeit speichern. Der Standard-Computerspeicher ist in Blöcken fester Größe organisiert, vergleichbar mit einer Bibliothek, die immer nur ganze Bücher verleiht, selbst wenn ein Leser nur eine einzige Seite benötigt. Wenn ein Computer ein bestimmtes Stück Daten anfordert, ruft das Speichersystem einen ganzen Block ab, der als Cache-Zeile bekannt ist und typischerweise sechzigundvier Byte groß ist. Wenn der Computer nur ein oder zwei Zahlen aus diesem Block benötigt, werden der Rest der Daten unnötigerweise abgerufen und gespeichert, was Energie verbraucht und die Datenwege verstopft. Diese Ineffizienz wird zu einem schweren Problem für „spärliche“ Arbeitslasten, bei denen der Computer möglicherweise Dutzende unzusammenhängender Zahlen aus verschiedenen Teilen des Speichers sammeln muss, um eine einzige Berechnung durchzuführen. In diesen Szenarien verbringt der Computer mehr Zeit mit der Bewegung nutzloser Daten, als er mit der eigentlichen Arbeit verbringt.

Ein Team von Forschern der New Mexico State University, des Lawrence Berkeley National Laboratory und der Florida International University hat einen neuen Weg vorgeschlagen, um dieses Problem zu lösen, genannt SecBCache. Ihre Arbeit konzentriert sich auf eine spezifische Art von Computerarchitektur, die in wissenschaftlichen Simulationen und maschinellem Lernen eingesetzt wird, wo Daten oft in einem verstreuten, unregelmäßigen Muster abgerufen werden. Die Forscher entwarfen eine spezialisierte Speicherkomponente, die die Regeln dafür ändert, wie Daten abgerufen und gespeichert werden. Anstatt jedes Mal einen großen, festen Datenblock zu greifen, ermöglicht ihr Design dem Computer, nur die winzigen, spezifischen Informationsstücke abzurufen und zu speichern, die er tatsächlich benötigt. Sie testeten diese Idee mithilfe einer detaillierten Computersimulation eines modernen Prozessors, die gegen reale Datensätze aus der Graphanalyse und der Matrixmultiplikation lief. Die Ergebnisse zeigten, dass dieser neue Ansatz die Menge der Daten, die der Computer in seinen Speicher schreibt, erheblich reduzieren, die für diese Aufgaben erforderliche Energie senken und potenziell die Zeit verkürzen kann, die für den Informationszugriff benötigt wird – und das, ohne Änderungen an den Programmiersprachen oder den grundlegenden Befehlen des Computers zu erfordern.

Der Kern der Innovation der Forscher liegt darin, wie sie die Speicherorganisation neu strukturiert haben. Sie brachen die standardmäßigen großen Speicherblöcke in kleinere, acht-Byte-große Stücke auf, die sie Subsektoren nennen. In einem traditionellen System muss ein Computer einen ganzen Block laden, wenn er eine Zahl aus einem Block benötigt. Im neuen SecBCache-System wird der Speicher in acht separate Sektionen oder Banken unterteilt, die gleichzeitig angesprochen werden können. Wenn der Computer eine Liste verstreuter Zahlen sammeln muss, kann er Anfragen an diese verschiedenen Banken gleichzeitig senden und dabei nur die spezifischen Acht-Byte-Stücke abrufen, die benötigt werden. Dies ist vergleichbar mit einer Bibliothek, die, anstatt Ihnen ein ganzes Buch zu geben, acht verschiedene Mitarbeiter hat, die im exakt gleichen Moment jeweils eine einzelne Seite, die Sie benötigen, aus verschiedenen Büchern ziehen können. Dieses Design ermöglicht es dem Computer, die Verschwendung durch das Abrufen nicht genutzter Daten zu vermeiden und dennoch die Geschwindigkeit und Organisation eines Standard-Speichersystems beizubehalten.

Um zu sehen, ob diese Idee in der Praxis funktionieren würde, bauten die Forscher eine virtuelle Version eines Computerprozessors mit einem Werkzeug namens gem5, das simuliert, wie Hardware auf einer sehr detaillierten Ebene reagiert. Sie programmierten diesen virtuellen Computer so, dass er zwei gängige Arten wissenschaftlicher Aufgaben ausführt: eine Breitensuche (breadth-first search), eine Methode zur Erkundung von Netzwerken wie sozialen Medienverbindungen oder Straßenkarten, und eine dünnbesetzte Matrixmultiplikation (sparse matrix multiplication), eine Berechnung, die in der Physik und den Ingenieurwissenschaften verwendet wird und große Zahlenraster beinhaltet, bei denen die meisten Einträge Null sind. Sie testeten diese Aufgaben mit sechzehn verschiedenen realen Datensätzen, die von E-Mail-Netzwerken bis hin zu Stromnetzmodellen reichten. Für jede Aufgabe verglichen sie die Leistung ihres neuen SecBCache-Designs mit einem standardmäßigen, konventionellen Speicher-Cache, der die traditionellen großen Blöcke verwendet.

Die Simulationen zeigten einen markanten Unterschied in der Effizienz. In einem Standardsystem rief der Computer oft einen vollen Datenblock ab, nutzte davon aber weniger als die Hälfte, in einigen Fällen sogar nur achtzehn Prozent. Das bedeutet, dass das System für jedes Stück nützlicher Daten Energie und Bandbreite verschwendete, indem es mehrere Stücke nutzloser Daten bewegte. Das SecBCache-Design eliminierte diese Verschwendung, indem es nur die benötigten Acht-Byte-Stücke abrief. Bei den Graph-Suchaufgaben reduzierte das neue Design die Menge der an den Speicher geschriebenen Daten um einen Median von dreiundsechzig Prozent. Bei den Matrixmultiplikationsaufgaben war die Reduktion mit einem Medianrückgang von achtzig Prozent sogar noch dramatischer. Das bedeutet, dass das neue System für viele der getesteten Datensätze nur einen Bruchteil der Daten schrieb, die das alte System schrieb, was den internen Datenverkehr, der Computer verlangsamt, drastisch reduzierte.

Über die bloße Platzersparnis hinaus untersuchten die Forscher auch, wie sich dieses Design auf die Geschwindigkeit des Speicherzugriffs auswirkt. Da das neue System in der Lage ist, mehrere Banken gleichzeitig zu nutzen, hat es das Potenzial, viele Anfragen parallel zu bedienen. Die Forscher merkten jedoch an, dass der tatsächliche Geschwindigkeitsgewinn davon abhängt, wie die Daten verteilt sind. Sie erstellten ein mathematisches Modell, um die Zeit für den Speicherzugriff zu schätzen, wobei sie sowohl ein Best-Case-Szenario berechneten, in dem alles perfekt läuft, als auch ein Worst-Case-Szenario, in dem Anfragen in ders der gleichen Bank stecken bleiben. Unter den konservativen Worst-Case-Annahmen sagte das Modell voraus, dass das neue System die Speicherzugriffsverzögerungen bei den Graph-Suchaufgaben um sechsundzwanzig Prozent und bei der Matrixmultiplikation um fünfzig Prozent reduzieren würde. Diese Zahlen stellen die Zeit dar, die das Speichersystem selbst benötigt, nicht die Gesamtzeit, die der Computer benötigt, um das gesamte Programm abzuschließen, aber sie deuten auf eine signifikante Verbesserung darin hin, wie schnell der Prozessor die Daten erhält, die er benötigt.

Die Forscher untersuchten auch die physischen Kosten für den Bau eines solchen Systems. Sie verwendeten ein Standard-Industriewerkzeug, um die Größe und den Stromverbrauch des neuen Speicherdesigns zu schätzen. Sie fanden heraus, dass die zusätzliche Hardware, die zur Verwaltung dieser kleineren, gebankten Datenstücke erforderlich ist, höchstens 2,46 Prozent der Gesamtfläche der Speicherhierarchie des Computers einnehmen würde. Dies ist ein sehr geringer Fußabdruck, was darauf hindeutet, dass das Design zu modernen Prozessoren hinzugefügt werden kann, ohne viel Platz einzunehmen. Darüber hinaus verbraucht das neue System, da es so viel weniger Daten in die Speicher-Arrays schreibt, auch weniger Energie. Die Simulationen zeigten, dass die dynamische Energie, die das Speichersystem verbraucht, für jeden getesteten Datensatz sank, mit Reduktionen, die je nach Spärlichkeit der Daten von wenigen Prozent bis zu über achtzig Prozent reichten.

Einer der wichtigsten Aspekte dieser Arbeit ist, dass Programmierer ihren Code nicht umschreiben oder neue Wege lernen müssen, wie sie dem Computer Befehle geben sollen. Die Forscher entwarfen SecBCache so, dass es mit bestehenden Befehlen funktioniert, die Computer bereits zum Sammeln (gather) und Verstreuen (scatter) von Daten verwenden. In modernen Prozessoren gibt es spezifische Befehle, die es ermöglichen, dass eine einzige Anweisung mehrere nicht zusammenhängende Datenstücke lädt. Das neue Speichersystem macht diese bestehenden Befehle einfach effizienter, indem es sicherstellt, dass nur die notwendigen Daten bewegt werden. Die einzige erforderliche Änderung wäre ein einfacher Software-Marker, der dem Computer mitteilt, welche Teile des Speichers diese Art von verstreuten Daten enthalten, wodurch die Hardware diese Anfragen automatisch an das neue System routen kann. Dieser Ansatz vermeidet die Notwendigkeit komplexer neuer Programmiermodelle oder spezialisierter Hardware-Beschleuniger, die oft scheitern, eine breite Akzeptanz in der Industrie zu finden.

Die Studie hob auch hervor, wo dieser Ansatz nicht so effektiv sein könnte. In Fällen, in denen die aufgerufenen Daten sehr dicht und vorhersehbar sind, etwa wenn ein Computer eine lange Liste von Zahlen liest, die direkt nebeneinander liegen, funktioniert das traditionelle System des Abrufens großer Blöcke sehr gut. In diesen spezifischen Szenarien schnitt das neue System manchmal etwas schlechter ab, da es jedes Stück einzeln abrufen musste und somit den Vorteil der „kostenlosen“ Daten, die mit einem großen Block einhergehen, verlor. Die Forscher betonten jedoch, dass ihr Design speziell auf die wachsende Klasse von Problemen ausgerichtet ist, die spärliche, unregelmäßige Datenzugriffe beinhalten, welche in Bereichen wie künstlicher Intelligenz und Big-Data-Analysen immer häufiger vorkommen. Für diese Anwendungen überwiegt die Fähigkeit, nur das abzurufen, was benötigt wird, den Vorteil, alles auf einmal abzurufen.

Die Forscher waren sorgfältig darin, zwischen dem, was sie direkt gemessen haben, und dem, was sie geschätzt haben, zu unterscheiden. Die Reduktionen der geschriebenen Daten und die Energieeinsparungen wurden direkt aus der Simulation des Speichersystems gemessen. Die Verbesserungen der Zugriffsgeschwindigkeit wurden jedoch durch ein mathematisches Modell abgeleitet, das schätzte, wie das System reagieren würde, wenn es mehrere Anfragen gleichzeitig bearbeiten könnte. Während die Simulation zeigte, dass die Hardware die Anfragen bewältigen kann, lieferte das Modell eine Spanne möglicher Verzögerungen, basierend darauf, wie oft verschiedene Teile des Speichers gleichzeitig angefragt werden. Die Forscher merkten an, dass dies modellierte Verzögerungen sind und keine garantierten Beschleunigungen für die endgültige Anwendung, aber sie sind ein starker Indikator dafür, dass das Speichersubsystem weniger ein Engpass sein wird.

Im breiteren Kontext der Informatik adressiert diese Arbeit einen grundlegenden Wandel in der Art und Weise, wie sich das Computing entwickelt. Während sich Maschinen von einfachen, linearen Berechnungen hin zu komplexen, datengesteuerten Aufgaben bewegen, werden die alten Annahmen darüber, wie der Speicher funktionieren sollte, immer weniger relevant. Die Vorstellung, dass ein Computer immer einen großen Block an Daten abrufen sollte, ist ein Erbe einer Ära, in der Daten dicht und vorhersehbar waren. Das SecBCache-Design bietet einen Ausblick auf eine Zukunft, in der Speichersysteme flexibler sind und in der Lage sind, sich an die unregelmäßigen Bedürfnisse moderner Algorithmen anzupassen. Durch den Beweis, dass es möglich ist, ein Speichersystem zu bauen, das sowohl hocheffizient als auch kompatibel mit bestehender Software ist, haben die Forscher einen praktischen Weg aufgezeigt, um die Leistung der nächsten Generation wissenschaftlicher und analytischer Werkzeuge zu verbessern.

Die Studie kommt zu dem Schluss, dass zwar keine einzelne Lösung für jedes Computerproblem passt, die spezifische Herausforderung des Umgangs mit spärlichen, indirekten Datenzugriffen jedoch mit einer gezielten architektonischen Änderung gelöst werden kann. Die Forscher haben demonstriert, dass es durch die Aufteilung des Speichers in kleinere, unabhängig zugängliche Stücke und die Organisation in einer Weise, die den parallelen Zugriff ermöglicht, möglich ist, die Verschwendung von Energie und Bandbreite, die aktuelle Systeme plagt, drastisch zu reduzieren. Dieser Ansatz erfordert keine Revolution in der Art und Weise, wie wir Computer programmieren, sondern vielmehr eine Evolution in der Art und Weise, wie die Hardware die Daten handhabt, die wir bereits an sie zu verarbeiten anweisen. Da die Nachfrage nach der Verarbeitung großer, komplexer Datensätze weiter wächst, könnten Designs wie SecBCache unerlässlich werden, um Computer schnell und energieeffizient zu halten und sicherzustellen, dass der Engpass beim Bewegen von Daten nicht das Potenzial der Berechnungen selbst bremst.