Maschinelles Lernen und neuronale Netze - Seite 30

Neuer Kommentar
 

Vorlesung 12. Parallele Speicherzuordnung



Vorlesung 12. Parallele Speicherzuordnung

Das Video diskutiert verschiedene Speicherzuweisungsstrategien und ihre Kompromisse. Die Verwendung von malloc und ausgerichteter Zuweisung sowie die Bedeutung einer ordnungsgemäßen Speicherfreigabe mit free werden erläutert. Die Verwendung von Mmap für die Zuweisung von virtuellem Speicher wird ebenfalls behandelt, zusammen mit den Problemen der externen Fragmentierung und langsamen Leistung. Das Konzept von Stacks in der C- und C++-Programmierung wird untersucht, wobei der Schwerpunkt auf einem Heap-basierten Cactus-Stack-Ansatz zur Zuweisung von Stack-Frames liegt, der zu besseren raumgebundenen Beweisen und Obergrenzen führen kann. Die Verwendung eines Pools von linearen Stapeln wird ebenfalls diskutiert, zusammen mit der Bedeutung der Optimierung für kleine Blöcke, um die Fragmentierung zu minimieren. Das Video schließt mit einer Diskussion globaler und lokaler Heap-Ansätze und ihrer potenziellen Probleme, zusammen mit Ansätzen wie Bin-Free-Listen und regelmäßigem Speicherausgleich, um diese Probleme anzugehen.

Das Video diskutiert auch Lösungen für die parallele Speicherzuweisung und stellt den Hoard-Allocator als Lösung vor. Der Hoard-Zuordner verwendet eine Kombination aus lokalen und globalen Heaps und großen Superblöcken, die zwischen Heaps verschoben werden können, um falsches Teilen zu reduzieren, die Skalierbarkeit zu verbessern und externe Fragmentierung zu reduzieren. Der im globalen Heap zugewiesene maximale Speicher ist höchstens der in den lokalen Heaps zugewiesene maximale Speicher, und der Footprint ist nach oben durch den Benutzer-Footprint plus zugewiesenen, aber ungenutzten Speicher in den lokalen Heaps begrenzt. Das Video diskutiert auch kurz andere Allokatoren wie Je malloc und Super malloc, wobei Benchmark-Ergebnisse darauf hindeuten, dass Super malloc besser abschneidet als Je malloc und Hoard. Die Diskussion endet mit einem Verweis auf Online-Folien für Details zur Garbage Collection.

  • 00:00:00 In diesem Abschnitt geht der Dozent auf Grundelemente der Speicherzuweisung einschliesslich malloc und ausgerichteter Zuweisung ein. Die ausgerichtete Zuweisung kann verwendet werden, um Speicher auf Cache-Zeilen auszurichten, so dass der Zugriff auf ein Objekt innerhalb einer Cache-Zeile nur einen Cache-Zugriff erfordert, wodurch die Anzahl von Cache-Fehlschlägen reduziert wird. Der Dozent erörtert auch die Bedeutung der ordnungsgemäßen Freigabe von Speicher mit der free-Funktion und der Vermeidung von Speicherlecks und doppelter Freigabe. Abschließend stellt der Dozent den Systemaufruf Mmap vor, mit dem virtueller Speicher ohne Backing-Datei allokiert werden kann.

  • 00:05:00 In diesem Abschnitt erklärt der Referent den Prozess der Speicherzuweisung mit M map, einem Systemaufruf, der einen zusammenhängenden unbenutzten Bereich im Adressraum der Anwendung findet, der groß genug ist, um die angeforderte Speichergröße aufzunehmen, und den aktualisiert Seitentabelle einen Eintrag für die zugewiesenen Seiten enthalten. Im Gegensatz zu malloc, das ein Bibliotheksaufruf und Teil des Heap-Verwaltungscodes der C-Bibliothek ist, weist M map nicht sofort physischen Speicher für den angeforderten Speicher zu, sondern füllt die Seitentabelle mit Einträgen, die auf eine spezielle Nullseite verweisen, die geändert wird und nur dann in den physischen Speicher übersetzt, wenn der Benutzer zum ersten Mal darauf schreibt. Darüber hinaus ist M map dafür verantwortlich, Speicher vom Betriebssystem zu erhalten, während malloc dafür verantwortlich ist, zuvor zugewiesenen Speicher wiederzuverwenden, um die Fragmentierung zu reduzieren und die zeitliche Lokalität zu verbessern.

  • 00:10:00 In diesem Abschnitt erörtert das Video die Unterschiede zwischen der Verwendung von MMAP und MALLOC für die Speicherzuweisung und betont, dass MMAP relativ schwergewichtig ist und selbst bei kleinen Zuweisungen ganze Seiten zuweist, was zu externer Fragmentierung und langsamer Leistung führt. Das Video zeigt auch den Prozess der Adressübersetzung, bei der die virtuelle Adresse für den Zugriff auf den Speicher verwendet wird und die Hardware die entsprechende physische Adresse in der Seitentabelle nachschlägt. Das Video erklärt, wie TLBs funktionieren, indem die letzten Seitentabellensuchen zwischengespeichert werden, und weist darauf hin, dass Programme mit räumlicher oder zeitlicher Lokalität viele kürzliche Zugriffe im TLB gespeichert haben, was zu einer schnelleren Leistung führt.

  • 00:15:00 In diesem Abschnitt erörtert der Referent, wie die Adressübersetzung in modernen Maschinen funktioniert, und vertieft sich auch in das Konzept von Stacks in der C- und C++-Programmierung. Stapel werden verwendet, um Funktionsaufrufe und lokale Variablen zu verfolgen und einer linearen Reihenfolge zu folgen. Der Sprecher betont eine Zeigerregel in herkömmlichen linearen Stapeln: Ein Elternteil kann Zeiger auf seine Stapelvariablen an seine Kinder weitergeben, aber nicht umgekehrt, um ein Überschreiben von Variablen zu vermeiden. Der Sprecher schlägt auch Optionen vor, wie etwa das Zuordnen von Speicher auf der Halde oder auf dem Stack des Elternteils, um Speicher von einer Kindfunktion zurück an den Elternteil zu übergeben.

  • 00:20:00 Wenn die parallele Heap-Zuweisung korrekt ist, ist das potenzielle Problem bei der Verwendung eines heapbasierten Cactus-Stacks die Speicherfragmentierung, bei der möglicherweise nicht genügend zusammenhängender Speicher für zukünftige Zuweisungen übrig bleibt, was zu Speicherplatzverschwendung und möglicherweise zu einem knappen Speicherplatz führt Arbeitsspeicher oder Absturz des Programms. Während frühe Systeme für die parallele Programmierung diese Strategie verwendeten, ist es wichtig, den Code zu optimieren, um die Auswirkungen auf die Leistung zu minimieren und die Folgen der Speicherfragmentierung zu berücksichtigen.

  • 00:25:00 In diesem Abschnitt erläutert das Video die Verwendung eines Heap-basierten Cactus-Stack-Ansatzes für die Zuweisung von Stack-Frames ohne Festlegung einer Obergrenze für die maximale Tiefe. Die Interoperabilität ist jedoch ein Problem, wenn versucht wird, traditionellen linearen Stack-Code mit diesem heapbasierten Cactus-Stack zu verwenden. Dies kann mit einem Ansatz behoben werden, der als Thread-lokale Speicherzuordnung bezeichnet wird, aber dieser Ansatz erfordert Änderungen am Betriebssystem. Trotzdem ist der Heap-basierte Cactus-Stack-Ansatz in der Praxis immer noch gut und kann verwendet werden, um eine Leerzeichenbindung eines Silk-Programms zu beweisen, das ihn verwendet. Diese Leerraumbegrenzung zeigt, dass der Stackspeicherplatz einer P Worker-Ausführung mit einem heapbasierten Cactus-Stack nach oben durch P mal s1 begrenzt ist, wobei s1 der Stackspeicherplatz ist, der für eine serielle Ausführung des Silk-Programms erforderlich ist. Dies ist ein nettes Feature des Heap-basierten Cactus-Stack-Ansatzes.

  • 00:30:00 In diesem Abschnitt wird der Multiplikationscode der Teile-und-Herrsche-Matrix analysiert, um zu verstehen, wie er auf das Space-Time Tradeoff Theorem angewendet werden kann. Der Code führt acht rekursive Aufrufe mit jeweils der Größe N/2 durch, und vor jedem Aufruf führt er einen Malloc aus, um temporären Speicherplatz der Größe N zum Quadrat zu erhalten, der dann freigegeben wird, bevor die Funktion zurückkehrt. Da die Zuweisungen einer Stack-Disziplin folgen, kann der von der vorherigen Folie gebundene Speicherplatz verwendet werden, um den P-Worker-Speicherplatz nach oben zu begrenzen, selbst wenn die Zuweisung von der Halde erfolgt. Die Arbeit ist die Kubikzahl N und die Spanne ist die Ordnung Log zum Quadrat N. Die Wiederholung für den Raum ist s von N/2 + Theta von N zum Quadrat, was zu N zum Quadrat auflöst. Daher zeigen die Busy Leaves-Eigenschaft und das Theorem für den begrenzten Speicherplatz, dass der Speicherplatz auf P Prozessoren durch P mal N zum Quadrat begrenzt ist.

  • 00:35:00 In diesem Abschnitt führt der Sprecher das Publikum durch, wie eine stärkere Raumbegrenzung für den im vorherigen Abschnitt besprochenen Algorithmus nachgewiesen werden kann. Durch Analysieren der Struktur des Algorithmus und Fokussieren auf möglichst viele Verzweigungen in der Nähe der Spitze des Rekursionsbaums kann der Sprecher eine Raumgrenze von P auf ein Drittel mal N zum Quadrat demonstrieren, was besser ist als frühere Obergrenzen . Der Referent merkt an, dass die Analyse der Struktur eines Algorithmus zu stärkeren raumgebundenen Beweisen führen kann als die einfache Anwendung eines allgemeinen Theorems. Der Abschnitt schließt mit der Erörterung, wie parallele Funktionen nicht mit älteren und seriellen Binärdateien von Drittanbietern zusammenarbeiten können.

  • 00:40:00 In diesem Abschnitt erörtert der Referent die Verwendung eines Pools von linearen Stacks bei der Speicherzuweisung, die verwendet werden können, um einen Pool von Stacks für Legacy-Code zu verwalten. Die Anzahl der Stacks im Pool sollte konstant multipliziert mit der Anzahl der Prozessoren sein, damit der gebundene Speicherplatz erhalten bleibt. Diese Strategie kann sich jedoch auf die Zeitbindung des Arbeitsdiebstahlalgorithmus auswirken, da der Arbeiter möglicherweise nicht in der Lage ist, zu stehlen, wenn keine Stapel mehr verfügbar sind. Der Redner spricht dann über grundlegende Eigenschaften von Heap-Storage-Allokatoren, einschließlich Allokator-Geschwindigkeit und Benutzer-Footprint, und betont die Bedeutung der Optimierung für kleine Blöcke aufgrund des Potenzials für Fragmentierung und Overhead bei der Zuweisung. Fragmentierung ist definiert als der Allokator-Fußabdruck geteilt durch den Benutzer-Fußabdruck.

  • 00:45:00 In diesem Abschnitt des Videos erläutert der Sprecher, wie der zugewiesene Fußabdruck so nah wie möglich am Benutzer-Fußabdruck gehalten werden kann, um das Verhältnis der beiden zu minimieren. Eine Lösung besteht darin, etwas namens M-Advice zu verwenden, das dem Betriebssystem mitteilt, dass eine bestimmte Speicherseite nicht mehr benötigt wird, sondern im virtuellen Speicher gehalten werden sollte. Der Referent erwähnt auch das Theorem aus dem vorherigen Vortrag, dass die Fragmentierung für Bin-Free-Listen das Ordnungsprotokoll zur Basis zwei von U ist, wobei U die Gesamtmenge des zugewiesenen Speichers ist, und erklärt die Unterschiede zwischen Speicherplatz-Overhead, interner Fragmentierung und externer Fragmentierung. Abschließend stellt der Redner fest, dass moderne 64-Bit-Prozessoren etwa 2 bis 48 Byte virtuellen Adressraum bieten, was für die meisten Programme ausreicht, aber immer noch mehr als der physische Speicher einer typischen Maschine.

  • 00:50:00 In diesem Abschnitt untersucht das Video eine parallele Heap-Zuweisungsstrategie unter Verwendung eines globalen Heaps mit Mutex-Schutz, wie der standardmäßige C++-Allocator funktioniert. Das Besondere an dieser Strategie ist, dass sie im Vergleich zu einer seriellen Zuweisung keinen zusätzlichen Platz benötigt. Das potenzielle Problem bei diesem Ansatz ist jedoch die Leistungseinbuße, da das Abrufen der Sperre für jede Zuweisung und Freigabe langsam ist und mit zunehmender Prozessorleistung schlechter wird. Sperrkonflikte sind der Hauptgrund für schlechte Skalierbarkeit, die für kleine Zuweisungen aufgrund höherer Anforderungsraten problematischer ist, und große Blockzuweisungen erfordern mehr Arbeit.

  • 00:55:00 In diesem Abschnitt erörtert das Video das potenzielle Problem bei der Verwendung eines lokalen Heap-Ansatzes, das zu Speicherdrift und unbegrenztem Blow-up führen kann. Wenn Sie Ihren gesamten Speicher in einem Thread zuweisen, ihn aber in einem anderen freigeben, kann es im Wesentlichen ungenutzten Speicher im System geben, für dessen Wiederverwendung der Zuordner nicht intelligent genug ist. Infolgedessen könnte Ihrem Programm, das auf mehreren Prozessoren ausgeführt wird, irgendwann der Arbeitsspeicher ausgehen, aber das passiert nicht, wenn es nur auf einem einzelnen Kern ausgeführt wird. Das Video schlägt vor, dieses Problem mit einer Bin-Free-Liste zu lösen, bei der Zeiger in der Datenstruktur der Bin-Free-Liste gesetzt werden, sodass der freigegebene Block in einer der verknüpften Listen erscheinen kann. Eine andere Strategie besteht darin, den Speicher regelmäßig neu auszugleichen, aber es wird auch ein einfacherer Ansatz diskutiert.

  • 01:00:00 In diesem Abschnitt erläutert das Video, wie der Speicherzuordner geändert wird, um das gewünschte Verhalten zu erreichen, dass jeder Thread auf seinen eigenen Heap zugreift, ohne dass ein globaler Heap erforderlich ist. Ein Ansatz besteht darin, jedes Objekt mit einem Eigentümer zu kennzeichnen und es an den Heap des Eigentümers zurückzugeben, wenn es freigegeben wird. Auf diese Weise werden lokale Objekte schnell zugewiesen und freigegeben, während entfernte Objekte eine gewisse Synchronisierung erfordern, jedoch nicht so viel wie bei einem globalen Heap. Die maximale Speichermenge, die zugewiesen werden kann, ist durch X begrenzt, die Menge, die von dem sequentiellen Programm verwendet wird, und das Blow-Up-Verhältnis ist nach oben begrenzt durch P, die Anzahl der Heaps. Dieser Ansatz ist auch widerstandsfähig gegenüber falschem Teilen, was auftritt, wenn mehrere Prozessoren auf unterschiedliche Speicherstellen, aber auf derselben Cache-Zeile zugreifen.

  • 01:05:00 In diesem Abschnitt erörtert der Referent, wie die parallele Heap-Zuweisung zu falschem Teilen führen kann, und stellt den Hoard-Allocator als Lösung vor. Der Hortzuordner verwendet eine Kombination aus lokalen und globalen Heaps und organisiert den Speicher in großen Superblöcken, die zwischen Heaps verschoben werden können. Dieser Ansatz ist schnell, skalierbar und widerstandsfähig gegen falsches Teilen. Wenn eine Zuweisung vorgenommen wird, sucht der Zuordner nach einem freien Objekt im lokalen Heap und ruft es ab, falls eines vorhanden ist. Wenn nicht, geht es zum globalen Heap, um mehr Speicher zu bekommen.

  • 01:10:00 In diesem Abschnitt erklärt der Sprecher, wie der Horde-Allokator die externe Fragmentierung reduziert, indem er ein freies Objekt aus dem vollsten nicht vollen Superblock zuweist, um die Bewegung der Superblöcke zu verdichten. Wenn das Objekt nicht im lokalen Heap gefunden wird, überprüft es den globalen Heap, und wenn der globale Heap leer ist, ruft es einen neuen Superblock vom Betriebssystem auf. Der Horde-Zuordner behält eine Invariante bei, bei der der Heap höchstens halb ausgelastet ist, und wenn er feststellt, dass der Heap nicht ausgelastet ist, verschiebt er einen halb leeren Superblock auf den globalen Heap. Der Sprecher präsentiert dann ein Lemma, das besagt, dass der maximale Speicher, der in der globalen Halde zugewiesen ist, höchstens der maximale Speicher ist, der in den lokalen Halden zugewiesen ist. Schließlich beweist der Sprecher das Theorem, dass der Fußabdruck des Horde-Zuordners nach oben durch die Ordnung u plus SP begrenzt ist, wobei u der Benutzer-Fußabdruck für das Programm und SP der zugewiesene, aber ungenutzte Speicher in den lokalen Heaps ist. Die Vergrößerung wird dann als eins plus Ordnung SP geteilt durch u berechnet.

  • 01:15:00 In diesem Abschnitt erörtert der Sprecher verschiedene Allokatoren, darunter Je malloc und Super malloc. Je malloc verfügt über separate globale Sperren für unterschiedliche Zuordnungsgrößen und gibt leere Seiten mithilfe von em-Ratschlägen frei, wodurch es robust gegenüber unterschiedlichen Zuordnungsablaufverfolgungen wird. Andererseits hat Super malloc nur sehr wenige Codezeilen und entwickelt sich sehr schnell. Der Lautsprecher teilt Benchmark-Ergebnisse, bei denen Super malloc besser abschneidet als J malloc, das besser abschneidet als Horde, während der Standardzuordner eine schlechte Leistung aufweist. Die Diskussion erstreckt sich auch auf die Garbage-Collection, die Details dazu verschiebt der Referent jedoch auf die Online-Folien.
 

Vorlesung 13. Das Cilk-Laufzeitsystem



Vorlesung 13. Das Cilk-Laufzeitsystem

Das Cilk-Laufzeitsystem ist für das Scheduling und den Lastausgleich von Berechnungen auf parallelen Prozessoren verantwortlich, wobei ein randomisierter Arbeitsdiebstahl-Scheduler verwendet wird, um Berechnungen zur Laufzeit auf Prozessoren abzubilden. Das System ist darauf ausgelegt, die serielle Ausführung des Programms zu optimieren, selbst auf Kosten zusätzlicher Kosten für Diebstähle. Der Worker verwaltet eine separate Deckdatenstruktur, die Zeiger auf die Stapelrahmen enthält und Kopf- und Endzeiger verwendet. Die Rahmen, die gestohlen werden können, haben eine zusätzliche lokale Struktur, die notwendige Informationen enthält, damit ein Diebstahl stattfindet, während sich das Deck außerhalb des Aufrufstapels befindet. Der Abschnitt erläutert, wie das System es Prozessoren ermöglicht, mitten in einer laufenden Funktion mit der Ausführung zu beginnen, und wie die Synchronisierung zwischen Prozessoren kompliziert wird, wenn eine Sync-Anweisung erreicht wird, die nicht über den Punkt hinaus ausgeführt werden kann, weil bestimmte Prozessoren noch auf den Abschluss von Berechnungen warten. Darüber hinaus spricht der Referent die Leistung des Systems, Designüberlegungen und Datenstrukturen an und wie das System die Ausführung unter Verwendung des THC-Protokolls optimiert, wobei zwei Sätze von Protokollen verwendet werden, einer für den Arbeiter, der die Arbeit ausführt, und einer für den Dieb.

Das Cilk-Laufzeitsystem verwendet ein Set-Jump- und ein Long-Jump-Protokoll, um den Diebstahl von Berechnungen aus den Ausführungsdecks von Opferprozessen zu handhaben. Die Cactus-Stack-Abstraktion ermöglicht es dem Diebesprozess, einen eigenen Call-Stack zu haben, um eine Beschädigung der Stacks des Opfers zu verhindern. Das Synchronisationsprotokoll des Systems verwendet einen Berechnungsbaum und einen Cactus Stack, um sicherzustellen, dass die Synchronisation nur zwischen verschachtelten Berechnungen innerhalb einer Funktion erfolgt. Der Full Frame Tree hält Eltern-Kind-Beziehungen zwischen Berechnungen mit ausstehenden Unterberechnungen aufrecht, um den Synchronisationsprozess zu vereinfachen. Zusätzlich optimiert das Laufzeitsystem den allgemeinen Fall, in dem die aktuelle Funktion keine ausstehenden Kindberechnungen hat und alle Worker beschäftigt sind. Zu den weiteren unterstützten Funktionen gehören C++-Ausnahmen, Reducer-Hyperobjekte und Stammbäume.

  • 00:00:00 In diesem Abschnitt erklärt Tibi das Cilk-Laufzeitsystem, das für die Planung und Lastverteilung von Berechnungen auf parallelen Prozessoren verantwortlich ist. Das Laufzeitsystem verwendet einen randomisierten Workstealing-Scheduler, um Berechnungen zur Laufzeit auf Prozessoren abzubilden und so eine effiziente Ausführung sicherzustellen. Tibi merkt an, dass das Cilk-Laufzeitsystem ein komplexes Stück Software ist, aber die zugrunde liegende Magie wird durch die Zusammenarbeit des Cilk-Compilers und der Laufzeitbibliothek implementiert. Außerdem zeigt er den Pseudocode für ein einfaches Cilk-Programm nach dem Kompilieren, was den komplexen Prozess hervorhebt, der dem Laufzeitsystem von Cilk zugrunde liegt.

  • 00:05:00 In diesem Abschnitt erläutert der Referent die für das Cilk-Laufzeitsystem erforderlichen Funktionen sowie Überlegungen zur Leistung. Er verwendet ein Beispiel einer parallelisierten Fibonacci-Routine, um zu veranschaulichen, wie das Cilk-Programm einen Berechnungs-Dag ausführt, der sich dynamisch entfaltet, wenn das Programm auf einem Prozessor läuft. Wenn jedoch die Silk-Spawn-Anweisung angetroffen wird, wird ein neuer Frame für Fib von 3 erstellt, und ein weiterer Strang steht zur parallelen Ausführung zur Verfügung. Der Prozessor beginnt dann mit der Ausführung von fib von 3, als wäre es ein gewöhnlicher Funktionsaufruf. Der Prozess wiederholt sich selbst, wenn der Befehlszeiger zum Beginn der fib-Routine zurückkehrt.

  • 00:10:00 In diesem Abschnitt sehen wir, wie mehrere Prozessoren mit Hilfe des Laufzeitsystems Cilk eine Fib-Routine parallel ausführen. Jeder Prozessor springt in die Mitte einer ausgeführten Funktion und beginnt mit der Ausführung, obwohl er über unabhängige Register verfügt, was die Frage aufwirft, wie das Silk-System Prozessoren ermöglicht, mit der Ausführung mitten in einer laufenden Funktion zu beginnen. Darüber hinaus wird die Synchronisierung zwischen Prozessoren kompliziert, wenn eine Sync-Anweisung erreicht wird, die nicht über den Punkt hinaus ausgeführt werden kann, da bestimmte Prozessoren immer noch auf den Abschluss von Berechnungen warten, was eine feinkörnige Synchronisierung innerhalb des verschachtelten Musters erfordert.

  • 00:15:00 In diesem Abschnitt erörtert der Referent die Implementierungsüberlegungen für das Cilk-Laufzeitsystem. Sie erwähnen drei Hauptüberlegungen: ein einzelner Worker, der in der Lage ist, das Programm auszuführen, die Fähigkeit, mitten in der Ausführung von Funktionen zu springen und dort weiterzumachen, wo andere Prozessoren aufgehört haben, und Synchronisation. Darüber hinaus hat Silk eine Vorstellung von einem Cactus-Stack, der korrekt implementiert werden muss, um alle Ansichten des Stacks verfügbar und konsistent zu machen. Schließlich muss das System Work-Stealing ermöglichen, indem es Prozessoren erlaubt, Frames voneinander zu stehlen.

  • 00:20:00 In diesem Abschnitt erörtert der Redner die für das Cilk-Laufzeitsystem erforderlichen Funktionen, darunter serielle Ausführung, Diebe, die in die Mitte laufender Funktionen springen, Synchronisierungen zur Synchronisierung auf verschachtelte, feinkörnige Weise, einen Cactus-Stack für alle Worker zu sehen, und der Umgang mit Mischungen aus Spawn-Frames und aufgerufenen Frames, die verfügbar sein können, wenn sie Berechnungen stehlen. Der Abschnitt befasst sich dann mit der Leistung des Systems, wo wir reichlich Parallelität benötigen, T1 über T unendlich viel größer als P sein sollte und wir eine lineare Beschleunigung wünschen, wenn wir die Anzahl der Prozessoren zum Ausführen des Programms erhöhen. Der Abschnitt behandelt auch die erwartete Laufzeit von TCP auf P Prozessoren, die proportional zur Berechnungsarbeit dividiert durch die Anzahl der Prozessoren plus etwas in der Größenordnung der Berechnungsspanne ist.

  • 00:25:00 In diesem Abschnitt lernen wir das Cilk-Laufzeitsystem und sein Ziel kennen, eine hohe Arbeitseffizienz in Programmen mit ausreichender Parallelität aufrechtzuerhalten. Das Silk-Laufzeitsystem hält sich an das Work-First-Prinzip, indem es die serielle Ausführung des Programms optimiert, selbst auf Kosten einiger zusätzlicher Kosten für Stähle. Die Laufzeitsystembibliothek behandelt Probleme mit paralleler Ausführung und behandelt langsamere Ausführungspfade, wenn Stähle auftreten. Der Worker verwaltet eine separate Deckdatenstruktur, die Zeiger auf die Stapelrahmen enthält und Kopf- und Endzeiger verwendet. Die Rahmen, die gestohlen werden können, haben eine zusätzliche lokale Struktur, die notwendige Informationen enthält, damit ein Diebstahl stattfindet, während sich das Deck außerhalb des Aufrufstapels befindet.

  • 00:30:00 In diesem Abschnitt lernen wir das Design des Cilk-Laufzeitsystems und seine grundlegenden Datenstrukturen kennen. Das System erzeugt eine Spawn-Helferfunktion für jede Berechnung, die eine Worker-Struktur und eine Silk-Stack-Frame-Struktur für jede Instantiierung einer Spawn-Funktion bzw. eines Spawn-Helfers aufrechterhält. Der Silk-RTS-Stapelrahmen enthält Felder wie einen Puffer und eine ganze Zahl von Flags, um den Status des Silk-Stapelrahmens zusammenzufassen, sowie einen Zeiger auf einen übergeordneten Silk-Stapelrahmen im Aufrufstapel. Die Worker-Struktur verwaltet ein Deck und einen Zeiger auf den aktuellen Silk RTS-Stack-Frame. Diese Datenstrukturen sind die wesentlichen Bestandteile des Cilk-Laufzeitsystems, das das Intel so+-Laufzeitsystem ausarbeitet.

  • 00:35:00 In diesem Abschnitt untersucht das Video den Code für die Spawn-Funktion „foo“ und die Spawn-Hilfsfunktion. Der Code für „foo“ enthält einen Aufruf zum Initialisieren des Stapelrahmens, der für einen Spawn mit der Set-Jump-Routine eingerichtet wird, einen Aufruf der Spawn-Hilfsfunktion „spawn bar“, einen bedingten Codeblock für eine Senke im Silk RTS, und Aufrufe zum Platzieren und Blättern von Frames zur Bereinigung. Der Code für den Spawn-Helfer enthält einen Aufruf zum Initialisieren des Stapelrahmens und einen Aufruf zum Trennen des Silk RTS mit zusätzlichen Bereinigungsfunktionen für die Stapelstruktur. Die Setup-Routine wird als eine Funktion beschrieben, die es Dieben ermöglicht, die Fortsetzung der Funktion zu stehlen, indem sie als Argument einen Puffer nimmt, um notwendige Informationen zum Wiederaufnehmen des Funktionsorts zu speichern.

  • 00:40:00 In diesem Abschnitt erläutert der Sprecher, wie der Registersatz eingeschränkt und in einem vorgegebenen Satz für einen Funktionsaufruf gespeichert werden kann. Die Verantwortung für das Speichern der Register liegt bei der Funktion, aber der Befehlszeiger und die Stapelzeiger werden im Puffer gespeichert. Der Abschnitt fährt fort, eine Spawn-Hilfsfunktion zu diskutieren und wie sie Worker-Strukturen und aktuelle Stack-Frames aktualisiert. Abschließend erklärt der Abschnitt, wie die schnelle Rahmeneintrittsroutine einen übergeordneten Zeiger in der Aufrufliste erstellt und den aktuellen Stapelrahmen des Arbeiters aktualisiert, so dass er auf das untere Ende zeigt.

  • 00:45:00 In diesem Abschnitt erklärt das Transkript des YouTube-Videos mit dem Titel „The Cilk Runtime System“, wie die Trennfunktion von Silk RTS den Diebstahl von Berechnungen ermöglicht, wobei ein Dieb kommen und stehlen könnte, sobald die Ausführung von Silk Art abgeschlossen ist die Fortsetzung der Seidenbrut. Der Pop-Frame ist dafür verantwortlich, die Stack-Frame-Struktur zu bereinigen und den aktuellen Stack-Frame so zu aktualisieren, dass er auf den übergeordneten Frame zeigt. Dieser Funktionsaufruf kann zurückkehren oder nicht, und welcher dieser beiden Fälle für das Laufzeitsystem wichtiger zu optimieren ist, ist der Erfolgsfall, basierend auf dem Prinzip der beiden, die zuerst funktionieren.

  • 00:50:00 In diesem Abschnitt erörtert der Referent die Optimierung des Cilk-Laufzeitsystems für die Worker-Ausführung im ersten Fall, bei dem angenommen wird, dass Worker eine regelmäßige serielle Ausführung durchführen. Sie erklären auch, wie das Stehlen von Arbeitern funktioniert, wobei der Dieb auf die Oberseite des Decks des Opfers zielt, den Gegenstand aus der Warteschlange entfernt und den Kopf des Decks und den aktuellen Stapelrahmenzeiger aktualisiert. Das Ergebnis der erzeugten Funktion wird im ursprünglichen SIL-Code an den übergeordneten Stapelrahmen zurückgegeben.

  • 00:55:00 In diesem Abschnitt erläutert der Referent den Ansatz des Cilk-Laufzeitsystems bei der Handhabung gleichzeitiger Zugriffe mit mehreren Prozessoren unter Verwendung eines Protokolls namens THC-Protokoll. Das Protokoll umfasst zwei Sätze von Protokollen, einen für den Arbeiter, der die Arbeit ausführt, und einen für den Dieb. Das Protokoll des Arbeiters wird optimiert, indem versucht wird, etwas von der Unterseite des Decks zu knallen, und nur wenn es fehlschlägt, erhält es ein Schloss auf dem Deck, während der Dieb immer ein Schloss ergreift, bevor er irgendwelche Deckoperationen durchführt. Der Dieb nimmt dann auf magische Weise eine gestohlene Fortsetzung wieder auf, indem er die Weitsprungfunktion aufruft, den von der Set-Jump-Funktion abgerufenen Stapelrahmenpuffer weiterleitet und seinen Registerzustand auf den der gestohlenen Fortsetzung setzt.

  • 01:00:00 In diesem Abschnitt erläutert der Referent die Interaktion zwischen Set-Jump- und Long-Jump-Aufrufen innerhalb des Cilk-Laufzeitsystems. Sie erklären, wie eine Weitsprungroutine beim Aufruf effektiv ein zweites Mal vom Satzsprung zurückkehrt, diesmal mit einem anderen Wert, der im zweiten Argument angegeben ist. Unter Verwendung des geeigneten Puffers und des zweiten Arguments kann der Dieb einen langen Sprung ausführen, um eine bestimmte Berechnung im Code des Opfers zu überspringen. Der Redner merkt an, dass es möglich ist, die zum Überspringen eines Anrufs erforderliche Entfernung statisch zu berechnen und einen anderen Ansatz zu verwenden, aber das Set-Jump- und Long-Jump-Protokoll dient als flexiblere Methode für das Cilk-Laufzeitsystem. Insgesamt hebt der Redner die verschiedenen Techniken hervor, die dem Dieb zur Verfügung stehen, um mit Cilk Berechnungen aus dem Deck des Opfers zu stehlen.

  • 01:05:00 In diesem Abschnitt wird die Notwendigkeit einer Cactus-Stack-Abstraktion für das Cilk-Laufzeitsystem erörtert. Es wird erklärt, dass die Verwendung des Stacks des Opfers zu einer Beschädigung des Stacks des Opfers führen und Probleme bei der Aufrechterhaltung der Konsistenz über alle Worker hinweg verursachen kann. Daher wird ein separater Aufrufstapel für den Dieb benötigt. Die Implementierung des Cactus-Stacks beinhaltet, dass der Dieb die Fortsetzung stiehlt und seinen Stack-Zeiger auf seinen eigenen Stack setzt, während er immer noch in der Lage ist, durch Offsets von RB p auf den Zustand der Funktion auf dem Stack des Opfers zuzugreifen.

  • 01:10:00 In diesem Abschnitt erläutert der Referent, wie das SIL-Laufzeitsystem die Synchronisation der Berechnung auf verschiedenen Prozessoren handhabt. Das System verwendet den Cactus-Stack und einen Berechnungsbaum, um sicherzustellen, dass die Synchronisierung nur zwischen verschachtelten Unterberechnungen unter einer Funktion und nicht dem Programm im Allgemeinen erfolgt. Wenn ein Worker eine Silk-Sync-Anweisung erreicht, bevor alle Unterberechnungen zurückkehren, wird er zu einem Dieb und arbeitet weiter am Stack-Frame einer gestohlenen Berechnung. Dadurch kann das System die Verschwendung von Arbeitskräften vermeiden und sicherstellen, dass die verschachtelten Berechnungen richtig synchronisiert sind. Das System weist den Compiler ausdrücklich an, keine Optimierung zu verwenden, die mit diesem Ansatz in Konflikt geraten könnte.

  • 01:15:00 In diesem Abschnitt wird das Cilk-Laufzeitsystem so beschrieben, dass es einen Zustandsbaum verwaltet, der als Vollbilder bezeichnet wird und verfolgt, welche Berechnungen darauf warten, welche anderen Berechnungen abgeschlossen werden. Dieses System verwendet einen vollständigen Frame-Baum, um eine Vielzahl von Informationen für die parallele Ausführung zu verfolgen, einschließlich Zeigern auf übergeordnete Frames, möglicherweise auf untergeordnete Frames und wie sich ausstehende Unterberechnungen zueinander verhalten. Wenn ein Worker auf eine Synchronisierung stößt und eine ausstehende untergeordnete Berechnung hat, kann er nicht synchronisieren und muss seinen gesamten Frame aussetzen, bis er zum Dieb werden kann, um mehr Arbeit zu stehlen. Dieses System ermöglicht einem Programm eine ausreichende Parallelität und vereinfacht Synchronisationsprotokolle.

  • 01:20:00 In diesem Abschnitt erläutert der Referent, wie das Cilk-Laufzeitsystem den allgemeinen Fall optimiert, in dem die ausführende Funktion keine ausstehenden Kinder hat und alle Worker im System mit ihren eigenen Aufgaben beschäftigt sind. Das Laufzeitsystem verwendet Bits aus dem Flag-Feld eines zugeordneten Stack-Frames, um auszuwerten, ob eine Synchronisation für eine Seidensynchronisation erforderlich ist. Der Redner erwähnt auch mehrere andere Features, die vom Laufzeitsystem unterstützt werden, darunter C++-Ausnahmen, Reducer-Hyper-Objekte und Stammbäume.
 

Vorlesung 14. Caching und Cache-effiziente Algorithmen



Vorlesung 14. Caching und Cache-effiziente Algorithmen

Im Video zu Caching und Cache-effizienten Algorithmen erklärt der Dozent die Cache-Hierarchie moderner Maschinen, die Unterschiede zwischen vollassoziativen und direkt abgebildeten Caches sowie die Vor- und Nachteile von satzassoziativen Caches. Das Video stellt auch das ideale Cache-Modell und das Konzept Cache-effizienter Algorithmen vor. Der Sprecher erörtert das Cache-Fehlschlag-Lemma, die Tall-Cache-Annahme und das Sub-Matrix-Caching-Lemma. Sie analysieren auch Cache-Fehlschläge, die beim Lesen einer Teilmatrix und während der Matrixmultiplikation auftreten. Das Video schließt mit einer Einführung in das Konzept der gekachelten Matrixmultiplikation und wie sie die Leistung erheblich verbessern kann, weist aber auch darauf hin, dass sie nicht portabel ist und die Optimierung für mehrere Cache-Ebenen teuer sein kann.

Die Vorlesung behandelt Caching und Cache-effiziente Algorithmen am Beispiel der rekursiven Matrixmultiplikation. Der Referent betont, wie wichtig es ist, sowohl Work- als auch Cache-Mißerfolge separat zu analysieren, und weist darauf hin, dass Cache-fähige Algorithmen aufgrund unterschiedlicher Cache-Größen möglicherweise nicht für alle Computer optimal sind. Der Redner erörtert auch Cache-vergessene Algorithmen, die sich automatisch auf jede Cache-Größe einstellen, und erwähnt Entwicklungen bei parallelem Cache-vergessenem Code. Schließlich ist das Ziel, Algorithmen zu entwerfen, die entweder Cache-bewusst oder Cache-oblivious sind, und die Diskussion über das Design von Cache-oblivious Algorithmen wird in der folgenden Vorlesung fortgesetzt.

  • 00:00:00 In diesem Abschnitt über Caching und Cache-effiziente Algorithmen erörtert der Kursleiter die Cache-Hierarchie moderner Maschinen, die private L1-Daten- und Befehls-Caches für jeden Prozessor, einen privaten L2-Cache und einen Last-Level-Cache umfasst von allen Prozessoren geteilt. Die Größe dieser Caches nimmt zu, wenn man sich in der Speicherhierarchie nach oben bewegt, wobei DRAM am langsamsten und größten ist. Die Assoziativität des Caches und die Latenz nehmen ebenfalls zu, wenn man sich in der Speicherhierarchie nach oben bewegt, wobei der L1-Cache der schnellste und assoziativste ist. Der Kursleiter erwähnt auch die Bedeutung von Cache-Kohärenzprotokollen, um Konsistenz bei Speicheradressenzugriffen für parallele Verarbeitung sicherzustellen. Wenn Sie verstehen, wie Sie die Lokalität in Programmen nutzen, können Sie die schnelleren Speicher-Caches effizienter nutzen.

  • 00:05:00 In diesem Abschnitt werden die Unterschiede zwischen vollständig assoziativen und direkt abgebildeten Caches diskutiert. Ein vollständig assoziativer Cache erfordert das Durchsuchen des gesamten Cache, um einen Block zu finden, was langsam und ineffizient sein kann, da das Finden eines Blocks den Zugriff auf mehrere Zeilen erfordern kann. Der direkt abgebildete Cache hingegen hat nur einen möglichen Speicherort für jeden Block, was den Zugriff auf Blöcke viel schneller und mit weniger Konflikten macht. Die drei Komponenten des Adressraums, der Offset, der Satz und das Tag werden auch erläutert, wenn die virtuelle Speicheradresse aufgeteilt wird, um die Position des Cache-Blocks zu bestimmen. Das Tag identifiziert, welchem Speicherblock der Cache-Block entspricht, und der Satz bestimmt, an welche Position im Cache der Block gelangt, mit einem Gesamtadressraum von W Bits.

  • 00:10:00 In diesem Abschnitt diskutiert das Video die Vor- und Nachteile von direkt zugeordneten Caches, die schnell sind, weil nur eine Stelle im Cache durchsucht werden muss, aber anfällig für Konfliktfehler sind, bei denen Cache-Blöcke sich gegenseitig räumen. Leistung reduzieren. Das Video stellt dann satzassoziative Caches vor, eine Hybridlösung, bei der jeder Satz mehrere Zeilen enthält, wodurch mehr als eine mögliche Position im Cache für jeden Cache-Block möglich ist. Das Video erwähnt auch eine Taxonomie verschiedener Arten von Cache-Fehlern, einschließlich Cold Misses, die beim ersten Zugriff auf einen Cache-Block auftreten und nicht vermieden werden können.

  • 00:15:00 In diesem Abschnitt behandelt das Video verschiedene Arten von Cache-Fehlern, einschließlich Kapazitätsfehler, Konfliktfehler und Freigabefehler. Kapazitätsfehler treten auf, wenn der Cache voll ist und nicht alle Cache-Blöcke aufnehmen kann, auf die zugegriffen werden muss, während Konfliktfehler in satzassoziativen Caches auftreten, wenn zu viele Blöcke aus demselben Satz auf den Cache abgebildet werden. Schließlich treten Fehler bei der gemeinsamen Nutzung in einem parallelen Kontext auf, wenn mehrere Prozessoren auf dieselbe Cache-Zeile zugreifen und mindestens einer von ihnen darauf schreibt. Das Video liefert auch ein Beispiel für einen schlimmen Fall für Konfliktfehler, wenn auf eine Untermatrix innerhalb einer größeren Matrix zugegriffen wird, die in Zeilen-Major-Reihenfolge gespeichert ist.

  • 00:20:00 In diesem Abschnitt erörtert der Referent Caching und Cache-effiziente Algorithmen. Sie verwenden ein Beispiel für den Zugriff auf eine Untermatrix innerhalb einer größeren Matrix und wie Konfliktfehler auftreten können, wenn der Cache nur 4-Wege-assoziativ ist. Der Sprecher schlägt vor, am Ende jeder Zeile in der Matrix eine konstante Menge an Platz hinzuzufügen, sodass jede Zeile länger als 2 ^ 15 Bytes ist, was dazu beitragen kann, die Konfliktfehler zu reduzieren.

  • 00:25:00 In diesem Abschnitt diskutiert der Redner das ideale Cache-Modell, das ein Modell ist, das verwendet wird, um die Cache-Leistung von Algorithmen zu analysieren. Dieses Modell geht von einer zweistufigen Cache-Hierarchie, einem vollständig assoziativen Cache und einer optimalen Nishant-Ersetzungsrichtlinie aus. Der Redner erklärt, dass die beiden entscheidenden Leistungsmaße die Ordnung N und die Anzahl der Cache-Fehler sind, wobei das ideale Szenario darin besteht, eine geringe Anzahl von Cache-Fehlern zu haben, ohne die Arbeit des herkömmlichen Standardalgorithmus zu erhöhen. Das 1985 bewiesene LRU-Lemma wird ebenfalls erwähnt, das besagt, dass ein Algorithmus, der Q-Cache-Fehler bei einem idealen Cache der Größe M verursacht, 2Q-Cache-Fehler bei einem vollständig assoziativen Cache der Größe 2M verursacht, der die LRU-Richtlinie verwendet.

  • 00:30:00 In diesem Abschnitt stellt der Referent das Konzept von Cache-effizienten Algorithmen vor und wie sie die Programmleistung verbessern können, indem sie die Anzahl von Cache-Fehlschlägen minimieren. Er erläutert die LRU-Ersetzungsrichtlinie (Least Recently Used), die besagt, dass ein vollständig assoziativer Cache, der doppelt so groß ist wie der ideale Cache, der LRU verwendet, nicht mehr als die doppelte Anzahl von Cache-Fehlschlägen verursacht. Dies ermöglicht eine einfachere Analyse von Cache-Fehlschlägen, wenn eine asymptotische Analyse durchgeführt wird. Der Sprecher präsentiert auch ein Cache-Miss-Lemma, das besagt, dass, wenn ein Programm einen Satz von Datensegmenten liest, deren Größe weniger als ein Drittel der Cache-Größe beträgt und deren durchschnittliche Größe mindestens der Größe einer Cache-Zeile entspricht, dann die Anzahl von Cache-Fehlschläge, um sie alle zu lesen, ist höchstens das Dreifache der Gesamtgröße der Segmente dividiert durch die Größe einer Cache-Zeile.

  • 00:35:00 In diesem Abschnitt diskutiert das Video zwei Annahmen im Zusammenhang mit dem Caching – das Cache-Miss-Lemma und die Tall-Cache-Annahme. Das Cache-Fehlschlag-Lemma besagt, dass, wenn die durchschnittliche Länge von Datensegmenten größer als eine Cache-Blockgröße ist, die Anzahl von Cache-Fehltreffern nur um einen konstanten Faktor erhöht wird. Die Annahme eines großen Cache geht davon aus, dass der Cache höher als breit ist, und ist in der Praxis normalerweise erfüllt. Das Video erklärt auch das Sub-Matrix-Caching-Lemma, das das Problem mit kurzen Caches beim Einpassen von Sub-Matrizen in Cache-Zeilen erörtert und warum die Annahme eines großen Caches zur Lösung dieses Problems nützlich ist.

  • 00:40:00 In diesem Abschnitt erörtert der Referent Caching und Cache-effiziente Algorithmen. Sie analysieren die Anzahl der Cache-Fehler, die beim Lesen einer quadratischen Untermatrix in den Cache auftreten, und verwenden das Cache-Fehler-Lemma, um zu zeigen, dass die Anzahl der Cache-Fehler, die zum Lesen aller Elemente der Matrix in den Cache erforderlich sind, höchstens 3n^2/B beträgt . Sie analysieren dann die Anzahl von Cache-Fehlschlägen, die in dem standardmäßigen kubischen Arbeitsmatrix-Multiplikationsalgorithmus auftreten, unter der Annahme, dass die Matrix in Zeilen-Major-Ordnung ist und sie die Annahme eines großen Caches erfüllen. Sie betrachten drei Fälle und nehmen LRU für den zweiten und dritten Fall an, was letztendlich die Bedeutung der Cache-Optimierung beim Algorithmusdesign zeigt.

  • 00:45:00 In diesem Abschnitt erörtert der Redner Caching und Cache-effiziente Algorithmen. Sie analysieren zwei Fälle für die Matrixmultiplikation, in denen n größer als M über B ist und wenn n kleiner als C mal M über B ist. Sie verwenden eine LRU-Ersetzungsrichtlinie und berechnen die Anzahl der Cache-Fehler, die beim Zugriff auf Matrix B auftreten. Im ersten Fall In diesem Fall stellen sie fest, dass sie Theta von n gewürfelten Cache-Fehlschlägen benötigen, was zu keinem Gewinn führt, wenn der Algorithmus über Lokalität verfügt. Im zweiten Fall können sie die räumliche Lokalität ausnutzen und die Anzahl von Cache-Fehlschlägen um einen Faktor B reduzieren, was zu Theta von n hoch drei über B Cache-Fehlschlägen führt, was effizienter ist.

  • 00:50:00 In diesem Abschnitt des Videos erörtert der Sprecher Caching und Cache-effiziente Algorithmen. Sie analysieren zuerst den Fall, in dem die gesamte Matrix in den Cache passt, was zu einer Gesamtzahl von Cache-Fehlschlägen von Theta von n zum Quadrat über B führt. Dann diskutieren sie eine Optimierung durch Vertauschen der Reihenfolge der inneren beiden Schleifen, um von räumlicher Lokalität und zu profitieren Reduzieren Sie die Gesamtzahl der Cache-Fehler auf Theta von n hoch drei über B. Sie stellen jedoch fest, dass es möglich ist, es besser zu machen, indem eine Optimierung namens Tiling verwendet wird, bei der sechs for-Schleifen verwendet werden, um Kacheln zu durchlaufen, und die Berechnung für jedes Sub durchgeführt wird -Matrix, bevor Sie mit der nächsten fortfahren. Die Arbeit für eine Teilmatrix der Größe s mal s wird dann in s hoch drei geteilt.

  • 00:55:00 In diesem Abschnitt wird das Konzept der gekachelten Matrixmultiplikation eingeführt und ausführlich besprochen. Das Ziel dieses Algorithmus besteht darin, die Teilmatrizen in den Cache einzupassen, sodass alle Berechnungen im Cache ohne weitere Cache-Fehlschläge durchgeführt werden können. Die Anzahl von Cache-Fehlschlägen wird analysiert und es wird festgestellt, dass die Anzahl von Cache-Fehlschlägen n/s^3 mal s^2/B ist, für insgesamt n^3/B * sqrt(M) Cache-Fehlschläge. Diese Zahl ist sehr bedeutsam für die Verbesserung der Leistung des Matrixmultiplikationscodes. Bei dem Algorithmus tritt jedoch ein Problem auf: Er ist nicht portierbar, da er stark von der Cache-Größe der Maschine abhängt, auf der er ausgeführt wird. Darüber hinaus wird die mehrdimensionale Tuning-Optimierung viel teurer und der Code wird chaotischer, wenn für mehrere Cache-Ebenen optimiert wird.

  • 01:00:00 In diesem Abschnitt befasst sich die Vorlesung mit Caching und Cache-effizienten Algorithmen. Der Referent erörtert die Herausforderungen bei der Abstimmung der Parameter für einen Cache-effizienten Algorithmus und dessen Optimierung für eine bestimmte Maschine. Sie führen einen rekursiven Matrixmultiplikationsalgorithmus ein, bei dem die Eingabematrizen in vier Untermatrizen oder Quadranten unterteilt werden. Für jeden Quadranten der Ausgangsmatrix tritt rekursiv eine Summe von zwei Matrixmultiplikationen auf. Schließlich analysiert der Sprecher die Arbeit dieses Algorithmus und kommt zu dem Schluss, dass es sich um ein einfacheres Design handelt, das immer noch eine gute Cache-Leistung beibehält.

  • 01:05:00 In diesem Abschnitt erörtert der Referent Caching und Cache-effiziente Algorithmen und verwendet das Beispiel der Matrixmultiplikation, um den Unterschied zwischen der Analyse von Arbeit und Cache-Fehlschlägen zu erläutern. Der Sprecher zeichnet einen Rekursionsbaum, um das Problem der Größe und der verzweigten Teilprobleme zu visualisieren, und stellt fest, dass die Anzahl der Ebenen bis zu den Blättern logarithmisch zur Basis 2 von n ist. Die Anzahl der Blätter wird als acht zur logarithmischen Basis 2 von n berechnet, was dasselbe ist wie n hoch drei. Die Arbeitsmenge ist einfach Theta n hoch drei, und die Cache-Fehlschläge werden mit einem anderen Basisfall analysiert, bei dem die Untermatrix in den Cache passt, und das Theta von N zum Quadrat über Cache-Fehlschläge verwendet wird. Der Referent betont, dass die Anzahl der Ebenen nicht nur logarithmisch zur Basis 2 von n ist, sondern auch von der Größe des Caches abhängt, was zu einer unterschiedlichen Anzahl von Blättern führt, Theta von n gewürfelt über m zu den drei Hälften.

  • 01:10:00 In diesem Abschnitt erklärt der Referent am Beispiel eines rekursiven Matrixmultiplikationscodes, wie man die Anzahl der Cache-Misses in einem Cache-effizienten Algorithmus analysiert. Der Code vergisst den Cache, was bedeutet, dass er keine explizite Kenntnis der Caches hat und sich passiv automatisch an die jeweilige Cache-Größe des Computers anpasst, auf dem er ausgeführt wird. Der Redner erwähnt auch, dass die besten Codes, die den Cache vergessen, heute mit beliebigen rechteckigen Matrizen arbeiten und eine binäre Teilung anstelle einer Acht-Wege-Teilung durchführen. Der Referent erörtert den parallelen Kontext und erklärt, wie die Anzahl der Cache-Fehler in einer deterministischen Zellberechnung analysiert wird, die auf mehreren Prozessoren mit privaten Caches ausgeführt wird.

  • 01:15:00 In diesem Abschnitt diskutiert der Referent Caching und Cache-effiziente Algorithmen. Durch die Minimierung von Cache-Fehlschlägen in der seriellen Illusion können wir sie im Wesentlichen bei der parallelen Ausführung für Low-Span-Algorithmen minimieren. Der Lautsprecher stellt eine Cache-Fehlschlaggrenze für einen parallelen rekursiven Matrixmultiplikationsalgorithmus bereit, der derselbe wie die serielle Ausführung ist. Das Ziel besteht darin, Algorithmen zu entwerfen, die den Cache explizit kennen oder Cache-vergessen sind. Der Referent liefert Beispiele für beides und erwähnt, dass es in der folgenden Vorlesung weitere Diskussionen zum Entwurf von Cache-vergessenen Algorithmen geben wird.
 

Vorlesung 15. Cache-oblivious Algorithmen



Vorlesung 15. Cache-oblivious Algorithmen

Das Video diskutiert Cache-vergessene Algorithmen, die automatisch die Cache-Größe auf einer Maschine optimieren können, eine gute Cache-Effizienz erzielen und keine Kenntnis der Cache-Parameter der Maschine erfordern. Das Video zeigt, wie man Code zur Simulation der Wärmediffusion durch Differentialgleichungen mit der Stencil-Methode auf einer 2D-Matrix schreibt. Der Code hat sowohl Schleifen- als auch Trapezversionen, wobei letztere Cache-effizienter, aber aufgrund der Vorhersagbarkeit des Zugriffsmusters des Schleifencodes in einer 2D-Simulation nicht wesentlich schneller ist. Das Video diskutiert auch das Zusammenspiel zwischen Caching und Parallelität und die Diagnose möglicher Engpässe bei der parallelen Beschleunigung. Abschließend erläutert der Referent Schablonenberechnungen und wie jeder Punkt in einem Array mithilfe eines festen Musters namens Schablone aktualisiert wird, das unter Cache-Fehlern leiden kann und Speicheranforderungen hat, die mithilfe effizienter Algorithmen reduziert werden können, die zeitliche und räumliche Lokalität ausnutzen.

Der zweite Teil des Videos behandelt Cache-vergessene Algorithmen zum Sortieren und Zusammenführen. Insbesondere behandelt das Video die Cache-Komplexität des Merge-Sortierens, stellt das Konzept des Multi-Way-Merging vor und erklärt die Cache-Komplexität des Multi-Way-Merge-Algorithmus. Das Video behandelt auch den Trichtersortieralgorithmus, einen Cache-vergessenen Sortieralgorithmus, der K quadratische Elemente und K sortierte Listen zusammenführen kann. Der Trichtersortieralgorithmus ist optimal und rekursiv mit der Quadratwurzel von K Trichtern konstruiert. Das Video erklärt, dass es viele andere Cache-vergessene Algorithmen und Datenstrukturen gibt, wie z. B. B-Trees, geordnete Dateiverwaltung und Prioritätswarteschlangen. Insgesamt bietet das Video eine Einführung in Cache-vergessene Algorithmen für diejenigen, die mehr über das Thema erfahren möchten.

  • 00:00:00 In diesem Abschnitt behandelt das Video Cache-vergessene Algorithmen, d. h. einen Algorithmus, der automatisch die Cache-Größe auf einem Computer anpasst und eine gute Cache-Effizienz erreicht, ohne dass der Code Kenntnis von den Cache-Parametern haben muss Die Maschine. Das Video verwendet das Beispiel der Simulation von Wärmediffusion durch Differentialgleichungen, um zu zeigen, wie sich wissenschaftliches Rechnen oft auf Differentialgleichungen stützt, um physikalische Prozesse zu beschreiben, und dann einen effizienten Code schreiben muss, um den Prozess zu simulieren. Das Video zeigt, wie Code basierend auf der Finite-Differenzen-Approximationsmethode zur Simulation der 1D-Wärmegleichung geschrieben wird.

  • 00:05:00 In diesem Abschnitt behandelt der Referent, wie Code für eine Simulationsgleichung geschrieben wird, die eine Finite-Differenzen-Näherung unter Verwendung der Schablonenmethode ermöglicht. Die Gleichung verwendet partielle Ableitungen von U nach T und X, und der Referent zeigt, wie man diese partiellen Ableitungen mit Näherungsverfahren erhält. Der 2D-Raum wird unter Verwendung einer Matrix dargestellt, wobei die X- und T-Werte horizontal bzw. vertikal dargestellt werden. Der Sprecher erklärt die Grenzen der Matrix und berechnet U anhand der Gleichung.

  • 00:10:00 In diesem Abschnitt erklärt der Moderator Schablonenberechnungen, eine Methode, die im wissenschaftlichen Rechnen für verschiedene Zwecke weit verbreitet ist. Bei dieser Methode wird jeder Punkt in einem Array unter Verwendung eines festen Musters, das als Schablone bezeichnet wird, aktualisiert. Die Berechnung hängt von drei anderen Werten ab, und dies wird als Drei-Punkte-Haltung bezeichnet. Obwohl Stencil-Berechnungen für große X-Werte verwendet werden können, kann die Leistung beim Caching leiden, was zu Cache-Fehlschlägen führt. Darüber hinaus kann der zum Speichern der Daten erforderliche Speicherplatz reduziert werden, indem nur zwei Zeilen gespeichert werden, die aktuelle und die vorherige, um die Punktwerte zu aktualisieren.

  • 00:15:00 funktioniert: In jedem Zeitschritt aktualisieren wir nur die Werte von X für eine bestimmte Zeile mit den Werten aus der vorherigen Zeile. Wir können also abwechseln, welche Zeile wir aktualisieren und welche Zeile wir als vorherige Zeile verwenden, und müssen nur etwa eine zusätzliche Zeile mit Werten behalten. Dieser Code ist jedoch nicht sehr Cache-effizient, und wir können ihn mithilfe von Kachel- oder Cache-vergessenen Algorithmen noch effizienter machen. Das ideale Cache-Modell geht von einem vollständig assoziativen Cache mit einer optimalen oder LRU-Ersetzungsrichtlinie aus und erfasst Kapazitätsfehler, aber keine Konfliktfehler in einer seriellen Ausführung. Nichtsdestotrotz ist es immer noch nützlich, um effiziente Algorithmen zu entwerfen, die zeitliche und räumliche Lokalität ausnutzen.

  • 00:20:00 In diesem Abschnitt erklärt der Referent, wie ein Cache-vergessener Algorithmus verwendet werden kann, um Punkte innerhalb eines trapezförmigen Raums in einer 2D-Matrix zu berechnen, ohne außerhalb davon zu suchen. Die Berechnung umfasst eine Kernfunktion, die einen Zeiger auf UT mod auf X nimmt und W von 0 plus Alpha mal W von minus 1 minus 2 mal W von 0 plus W von 1 zurückgibt Die Anzahl der Cache-Fehler ist Theta von NT über B für jede Zeile. Der Sprecher merkt jedoch an, dass mit Kacheln eine bessere Leistung erzielt werden kann, aber er fährt mit der Diskussion der Cache-vergessenen Version fort. Das Trapez hat eine obere Basis bei T1 und eine untere Basis bei T0. Der Algorithmus berechnet alle Punkte innerhalb des Trapezes unter Verwendung von Ungleichungsbedingungen, die T, t0, t1, X, x0, x1, DX0, DX1 umfassen, wobei DX0 und DX1 entweder -1, 0 oder 1 sind und Steigungen darstellen.

  • 00:25:00 In diesem Abschnitt beschreibt der Sprecher einen Teile-und-Herrsche-Ansatz für den Trapezregelalgorithmus. Der Ansatz hat einen Basisfall, bei dem die Höhe des Trapezes 1 ist und eine Schleife alle Werte basierend auf der Reihenfolge der Berechnung berechnet. Der Algorithmus hat zwei rekursive Fälle, nämlich den Raumschnitt und den Zeitschnitt, die von der Breite bzw. Höhe des Trapezes abhängen. Wenn das Trapez zu breit ist, wird ein Abstandsschnitt angewendet, bei dem das Trapez vertikal geschnitten wird, wobei eine Linie mit einer negativen Steigung durch die Mitte des Trapezes verläuft. Im Gegensatz dazu wird ein Zeitschnitt angewendet, wenn das Trapez zu hoch ist, und es wird mit einer horizontalen Linie durch die Mitte geschnitten. Der rekursive Algorithmus führt zwei Aufrufe durch, die die linke und rechte Seite sowie die Unterseite und Oberseite des Trapezes in einer bestimmten Reihenfolge durchlaufen, um eine gegenseitige Abhängigkeit zwischen den Punkten zu verhindern.

  • 00:30:00 In diesem Abschnitt erörtert der Sprecher die Cache-Komplexität der Cache-vergessenen Algorithmen. Sie analysieren den Rekursionsbaumansatz und stellen fest, dass sich der Algorithmus auf jeder Ebene in zwei Teilprobleme aufteilt, bis er den Basisfall erreicht, der das Theta von HW-Punkten darstellt, wobei H Theta von W ist. Die Anzahl der Cache-Fehler pro Blatt ist Theta W über B, und die Anzahl der Blätter ist Theta von NT über HW. Die internen Knoten tragen nicht wesentlich zur Cache-Komplexität bei. Die Cache-Komplexität verallgemeinert sich auf mehr als eine Dimension, und wenn d eins ist, führt dies zu NT über MB.

  • 00:35:00 In diesem Abschnitt erklärt der Sprecher den Unterschied zwischen dem Schleifencode und dem trapezförmigen Code, der eine viel bessere Cache-Komplexität aufweist, indem er einen Faktor von M einspart, wobei M die Anzahl der Cache-Zeilen ist. Die Simulation zeigt, dass der trapezförmige Code im Vergleich zum Schleifencode weniger Cache-Fehler verursacht, wodurch die Berechnung viel schneller abgeschlossen wird. Der Sprecher merkt jedoch an, dass diese Simulation nur für eine Dimension gedacht war, und fährt fort, eine Demo zu zeigen, was in zwei Dimensionen passiert.

  • 00:40:00 In diesem Abschnitt demonstriert der Moderator eine Echtzeitsimulation der Wärmeverteilung in einem 2D-Raum, in dem die Farben auf dem Bildschirm den Temperaturen entsprechen. Der Moderator vergleicht die Leistung des Schleifencodes und des Trapezcodes und zeigt, dass der Trapezcode zwar weitaus weniger Cache-Fehler verursacht, aber nur geringfügig schneller ist als der Schleifencode. Es wird vermutet, dass dies darauf zurückzuführen sein könnte, dass das Hardware-Prefetching den Schleifencode unterstützt, da sein Zugriffsmuster regelmäßig und leicht vorhersehbar ist.

  • 00:45:00 In diesem Abschnitt geht der Referent auf das Zusammenspiel von Caching und Parallelität ein. Sie erläutern ein Theorem, das besagt, dass das Minimieren von Cache-Fehlschlägen in der seriellen Ausführung sie im Wesentlichen in der parallelen Ausführung minimieren kann, wenn ein Algorithmus mit niedriger Spanne angenommen wird. Anschließend demonstrieren sie, wie der trapezförmige Algorithmus mithilfe eines V-Schnitts parallel arbeiten kann, wobei zwei unabhängige Trapeze parallel ausgeführt werden und das graue Trapez anschließend ausgeführt wird. Sie erwähnen auch den umgedrehten V-Schnitt, der für umgekehrte Trapeze verwendet wird.

  • 00:50:00 In diesem Abschnitt erörtert der Referent die Leistung von parallelem Schleifencode und parallelem Trapezcode im Vergleich zu ihren seriellen Gegenstücken. Der Code mit paralleler Schleife erreicht weniger als die Hälfte der potenziellen Beschleunigung, obwohl er mehr potenzielle Parallelität als der trapezförmige Code hat. Dies liegt daran, dass es im parallelen Fall einen Engpass bei der Speicherbandbreite gibt, der verhindert, dass das Vorabrufen dem parallel durchlaufenden Code hilft, im Vergleich zum seriellen Fall, wo viel Speicherbandbreite vorhanden ist. Im Gegensatz dazu erreicht der trapezförmige Code eine nahezu lineare Beschleunigung, was mit der Tatsache übereinstimmt, dass die Cache-Effizienz bei größeren Eingabegrößen, bei denen der Cache im Vergleich zur Eingabegröße so klein ist, eine viel größere Rolle spielt.

  • 00:55:00 In diesem Abschnitt erläutert der Referent, wie ein Engpass bei der parallelen Beschleunigung diagnostiziert wird, und identifiziert mehrere Ursachen, die ihn verursachen könnten, z. B. unzureichende Parallelität, Scheduling-Overhead, fehlende Speicherbandbreite und Konflikte. Sie schlagen mehrere Möglichkeiten vor, diese Probleme zu diagnostizieren, einschließlich der Verwendung von Silk Scale zur Messung der Parallelität im Code und der Durchführung von Hardwarezählern zur Messung der Speicherbandbreite. Die Diagnose von Konflikten ist jedoch besonders schwierig, und der Referent empfiehlt, sich die ersten drei möglichen Ursachen anzusehen, bevor er beurteilt, ob es sich um Konflikte handelt. Abschließend geht der Sprecher zur Erörterung der Schablonenberechnung über.

  • 01:00:00 In diesem Abschnitt erörtert der Referent die Analyse der Cache-Komplexität von Merge-Sortierung, indem er zunächst die Komplexität der Zusammenführung von zwei sortierten Eingabearrays analysiert. Die Zeit dafür ist proportional zur Summe der Größen der Eingabearrays. Die Anzahl der beim Zusammenführen von n Elementen auftretenden Cache-Fehltreffer ist Theta n über B, wobei B die Anzahl der Bytes in einer Cache-Zeile ist. Mergesort hat zwei rekursive Aufrufe für Eingaben, die halb so groß sind, und führt die sortierten Ausgaben seiner rekursiven Aufrufe zusammen. Die Gesamtarbeit der Zusammenführungssortierung ist Theta von n log n, was unter Verwendung der Rekursionsbaummethode analysiert wird. Die Cache-Komplexität von Mergesort wird ebenfalls diskutiert, und es wird gezeigt, dass die Anzahl der Cache-Misses proportional zur Anzahl der Cache-Blöcke ist, die zum Speichern der Daten benötigt werden, was Theta n über B log M ist, wobei M die maximale Größe a ist Unterblock haben kann.

  • 01:05:00 In diesem Abschnitt erläutert der Referent die Wiederholung für die Cache-Komplexität von Mergesort. Der Basisfall tritt auf, wenn die Problemgröße in den Cache passt, was zu Θ(n/B) Cache-Fehlschlägen führt. Andernfalls hat der Algorithmus zwei rekursive Aufrufe der Größe n/2 und Θ(n/B) Cache-Fehlschläge, um die Ergebnisse zusammenzuführen. Die Analyse umfasst die Anzahl der Ebenen eines Rekursionsbaums, der logarithmisch zur Basis 2 von n/CM ist, wobei CM eine Konstante ist. Die Anzahl von Cache-Fehltreffern pro Blatt ist Θ(M/B * n/CM), was eine Gesamtzahl von Cache-Fehltreffern von Θ(n/B * log (n/CM)) ergibt, was einen Faktor von B im ersten Term einspart . Allerdings sparen wir bei größeren Problemgrößen nur einen Faktor B gegenüber der Arbeit ein, während wir bei kleinen Problemgrößen einen Faktor B log n einsparen. Der Sprecher fragt, ob es eine bessere Lösung gibt, und die Antwort ist immer ja.

  • 01:10:00 In diesem Abschnitt erklärt der Referent, wie man Multi-Way-Merging verwendet, um sortierte Sub-Arrays zusammenzuführen, und stellt die Idee eines Turnierbaums vor, um die minimalen Elemente der Sub-Arrays zu bestimmen. Sie erklären auch die Arbeits- und Cache-Komplexität dieses Ansatzes, der in Cache-vergessenen Algorithmen zum Sortieren verwendet wird. Die Arbeitskomplexität der Multi-Way-Merge ist die gleiche wie bei der binären Merge-Sortierung, während die Cache-Komplexität durch die Anzahl der Cache-Misses bestimmt wird, die erforderlich sind, um den Turnierbaum zu füllen und auf die Eingabearrays zuzugreifen, die optimiert werden kann, wenn R kleiner als ist C*M/B für eine kleine Konstante C.

  • 01:15:00 In diesem Abschnitt erörtert der Referent die Cache-Komplexität des Multiway-Merge-Sortieralgorithmus und vergleicht ihn mit dem binären Merge-Sortieralgorithmus. Der Multi-Way-Merge-Sortieralgorithmus beinhaltet das Unterteilen des Problems in Unterprobleme der Größe n/R und das Bezahlen von n/B Cache-Fehlschlägen, um sie zusammenzuführen. Die Anzahl der Ebenen des Rekursionsbaums ist logarithmisch Basis R von n/cm, und die Blattgröße ist cm. Der Sprecher setzt R gleich Theta von M/B, macht es so groß wie möglich, und analysiert die Cache-Komplexität, die sich als Thetan n log n geteilt durch B log M herausstellt. Im Vergleich zum binären Merge-Sort-Algorithmus ist der Multi -way-Merge-Sortieralgorithmus spart einen Faktor von log M bei Cache-Fehlschlägen. Allerdings vergisst der Algorithmus den Cache nicht, und der Wert von R muss für eine bestimmte Maschine angepasst werden, was ein Problem sein kann, wenn andere Jobs ausgeführt werden, die um den Cache konkurrieren.

  • 01:20:00 In diesem Abschnitt erörtert der Redner den Funnel-Sortieralgorithmus, einen Cache-vergessenen Sortieralgorithmus, der K quadratische Elemente und K sortierte Listen zusammenführen kann. Es wird gezeigt, dass die Kosten dieser Zusammenführung die gleichen sind wie die des Mehrfach-Zusammenführungs-Sortieralgorithmus, aber der Trichter-Sortieralgorithmus ist Cache-vergessen und seine Grenze ist optimal. Der Referent präsentiert ein Bild davon, wie ein K-Trichter aussieht, und erklärt, dass der Algorithmus rekursiv mit Quadratwurzeln aus K-Trichtern konstruiert ist, die Elemente in Puffer einspeisen, die wiederum Elemente in die endgültige Ausgabe-Quadratwurzel von K-Trichtern einspeisen und produzieren die Ausgabe für den K-Trichter. Der Redner erwähnt auch, dass es viele andere Cache-vergessene Algorithmen und Datenstrukturen gibt, wie z. B. B-Trees, geordnete Dateiverwaltung und Prioritätswarteschlangen, und lädt die Zuschauer ein, online mehr darüber zu erfahren.
 

Vorlesung 16. Nichtdeterministische parallele Programmierung



Vorlesung 16. Nichtdeterministische parallele Programmierung

In diesem Video werden verschiedene Konzepte im Zusammenhang mit deterministischer und nicht deterministischer paralleler Programmierung erörtert. Der Referent betont, wie wichtig es ist, Nichtdeterminismus zu vermeiden, da er zu anomalen Verhaltensweisen und schwieriger Fehlersuche führen kann. Zu den Strategien zum Umgang mit Nicht-Determinismus gehören die Verwendung fester Werte, die Wiedergabe von Aufzeichnungen, Analysetools, Kapselung und Komponententests. Die Verwendung von Mutexes wird im Detail untersucht, einschließlich Spinning vs. Yielding, Reentrant vs. Non-Reentrant und Fair vs. Unfair. Der Referent geht auch auf das Konzept des Kontextwechsels und das „Skiverleihproblem“ im Zusammenhang mit paralleler Programmierung ein. Das Segment schließt mit der Erörterung der Grundprinzipien des Performance Engineering in Multi-Core-Prozessoren.

Der zweite Teil des Videos behandelt das Problem des Deadlocks bei der parallelen Programmierung und bietet Lösungen zu seiner Vermeidung an, wie z. B. die lineare Reihenfolge von Mutexes, die garantiert, dass es keinen Wartezyklus gibt. Darüber hinaus stellt der Referent das Konzept des Transaktionsspeichers vor, das Atomarität gewährleistet, indem es einen kritischen Bereich als eine Transaktion darstellt, die alle Aktualisierungen auf einmal festschreibt. Das Video stellt dann einen Algorithmus vor, der einen sperrenbasierten Ansatz mit einem endlichen Besitzarray und einer Release-Sortierung-Require-Methode verwendet, um Deadlocks und Hunger zu verhindern, ohne dass eine globale Sperre erforderlich ist. Abschließend wird der Algorithmus Release Sort and Reacquire erläutert, der verhindert, dass mehrere Sperren gleichzeitig versuchen, eine Sperre zu erwerben, wodurch Leistungsprobleme vermieden werden.

  • 00:00:00 In diesem Abschnitt stellt der Dozent das Konzept des Determinismus in der Programmierung vor und wie es sich auf paralleles Rechnen bezieht. Ein Programm ist deterministisch, wenn jeder Speicherplatz bei jeder Ausführung mit der gleichen Folge von Werten aktualisiert wird und sich das Programm immer gleich verhält. Deterministische Programme haben den Vorteil, dass sie wiederholbar sind, wodurch sie leichter zu debuggen sind. Der Dozent betont, wie wichtig es ist, niemals nicht-deterministische Parallelprogramme zu schreiben, da diese ein anomales Verhalten aufweisen können, das schwer zu debuggen ist. In der Praxis kann es jedoch schwierig sein, Nichtdeterminismus beim parallelen Rechnen zu vermeiden.

  • 00:05:00 In diesem Abschnitt erörtert der Redner die nicht-deterministische parallele Programmierung und die Tatsache, dass sie manchmal zu einer besseren Leistung führen kann, aber dennoch vermieden werden sollte, sofern dies nicht erforderlich ist. Der Redner empfiehlt, eine Teststrategie zu entwickeln, um den Nichtdeterminismus zu handhaben, wenn Sie ein Programm auf diese Weise schreiben müssen. Beispiele für Strategien sind das Ausschalten des Nicht-Determinismus, die Verwendung desselben Seeds für Zufallszahlen oder die Bereitstellung fester Werte für Programmeingaben, die sich ansonsten zufällig ändern könnten. Der Redner betont, wie wichtig es ist, Fehler im Programm zu handhaben, die durch Nicht-Determinismus verursacht werden.

  • 00:10:00 In diesem Abschnitt spricht der Referent über Strategien für den Umgang mit nicht-deterministischer Programmierung, wie z. B. die Wiedergabe von Aufzeichnungen, die Kapselung von Nicht-Determinismus, das Ersetzen einer deterministischen Alternative, die Verwendung von Analysewerkzeugen und Komponententests. Der Redner betont, wie wichtig es ist, den Nichtdeterminismus zu kontrollieren, um die Chancen zu verbessern, Fehler im Code zu finden. Der Referent liefert auch ein Beispiel für die Verwendung von gegenseitigem Ausschluss und Atomarität in einer Hash-Tabelle, um zu veranschaulichen, wie nicht deterministische Programmierung gehandhabt wird.

  • 00:15:00 In diesem Abschnitt erörtert der Sprecher, wie parallele Befehle, die auf denselben Ort zugreifen, zu Rennfehlern führen und die Integrität des Systems zerstören können. Die Standardlösung besteht darin, einige Anweisungen atomar zu machen, was bedeutet, dass sie vom Rest des Systems entweder als vollständig ausgeführt oder überhaupt nicht ausgeführt angesehen werden. Um dies zu erreichen, wird eine gegenseitige Ausschlusssperre oder Mutex-Sperre verwendet, bei der es sich um ein Objekt mit Sperr- und Entsperrelementfunktionen handelt. Jeder Slot wird zu einer Struktur mit einer Mutex-Sperre und einem Zeigerkopf zum Slot-Kontext gemacht, wodurch die Verwendung der Sperr- und Entsperrfunktionen vor dem Zugriff auf die Liste ermöglicht wird, wodurch die Korrektheit des Systems sichergestellt wird.

  • 00:20:00 In diesem Abschnitt untersucht das Video die Verwendung von Mutexes zur Implementierung von Atomarität und wie sie sich auf Determinationsrennen bezieht. Mutex-Sperren können sicherstellen, dass kritische Abschnitte atomar sind, aber der resultierende Code ist aufgrund eines Bestimmtheitswettlaufs nicht deterministisch, was in einigen Fällen erwünscht sein kann. Das Video betont, wie wichtig es ist, den Unterschied zwischen Data Races und Determinacy Races zu verstehen, und stellt fest, dass das einfache Eliminieren von Data Races nicht unbedingt bedeutet, dass keine Fehler im Code vorhanden sind. Es ist wichtig, eine Möglichkeit zu haben, Nichtdeterminismus zu erkennen, um Fehlalarme oder fehlende Race-Bugs im Code zu vermeiden.

  • 00:25:00 In diesem Abschnitt erklärt der Sprecher, dass das Fehlen von Datenrennen nicht unbedingt bedeutet, dass der Code keine Fehler enthält. Während keine Datenrennen positive Aspekte des Codes sind, kann das Beispiel des Sperrens zum Bereitstellen von Atomizität zu einer Verletzung der Atomizität führen. Darüber hinaus können harmlose Races auftreten, z. B. wenn zwei parallele Prozesse auf denselben Wert zugreifen, was zu demselben Ergebnis führen kann, aber auf einigen Architekturen auch zu falschen Werten führen kann. Der Referent argumentiert, dass, obwohl einige Menschen gutartige Rassen als harmlos betrachten, es dennoch wichtig ist, sie zu erkennen und zu vermeiden.

  • 00:30:00 In diesem Abschnitt erläutert der Referent die Gefahren der nicht deterministischen Programmierung, insbesondere aufgrund von Race Conditions, die auftreten können, wenn mehrere Prozesse versuchen, Werte an derselben Stelle festzulegen. Der Referent stellt das Konzept der „Silks“ vor, das absichtliche Rennen zulässt, aber gefährlich sein kann, wenn es nicht richtig verwendet wird. Die Komplexität von Rennen kann auch das Debuggen erschweren und Tools verwirren, die helfen sollen, korrekten Code zu erkennen. Der Referent erörtert auch, wie die Implementierung von Mutexe und ihre Parameter ihr Verhalten beeinflussen können, z. B. ob sie nachgeben oder sich drehen.

  • 00:35:00 In diesem Abschnitt erklärt das Video drei grundlegende Eigenschaften von Mutexe in der parallelen Programmierung: Spinning vs. Yield, Reentrant vs. Non-Reentrant und Fair vs. Unfair. Das Konzept von Spinning vs. Yielding ist die Idee, dass ein Thread nicht im Leerlauf bleibt und kontinuierlich nach Zugriff auf eine Sperre sucht, sondern die Kontrolle an das Betriebssystem für eine effizientere Ausführung abgibt. Wiedereintretender Mutex ermöglicht es einem Thread, der bereits eine Sperre hält, diese erneut zu erwerben, während nicht wiedereintrittsfähige Sperren zu einem Deadlock führen, wenn der Thread versucht, einen bereits vorhandenen Mutex erneut zu erwerben. Schließlich stellt Fair Mutex sicher, dass der Thread, der am längsten gewartet hat, zuerst die Sperre erhält, um die Möglichkeit eines Hungerproblems zu verhindern. Das Video bietet auch eine Implementierung eines einfachen Spinning-Mutex in Assemblersprache.

  • 00:40:00 In diesem Abschnitt erläutert das Video die Verwendung von Mutex in der parallelen Programmierung und warum die Austauschanweisung verwendet wird, anstatt nur den Mutex zu erhalten. Es wird erklärt, dass die Umtauschoperation einem Recht ähnlich ist, und um ein Recht auszuüben, muss die Bargeldlinie, auf der es sich befindet, auf den anderen ungültig gemacht und in einem modifizierten oder exklusiven Zustand gehalten werden. Dies erzeugt Datenverkehr im Speichernetzwerk und verlangsamt den Prozess. Andererseits werden durch die Verwendung des Austauschbefehls die Cache-Zeilen in einen gemeinsam genutzten Zustand versetzt, wodurch der Prozess schneller gehalten und weniger Verkehr erzeugt wird.

  • 00:45:00 In diesem Abschnitt erläutert der Sprecher den Unterschied zwischen einem Spinning-Mutex und einem Yield-Mutex. Bei einem Spinning-Mutex prüft das Programm ständig, ob der Mutex entsperrt werden soll, während das Programm bei einem Yielding-Mutex die Kontrolle an das Betriebssystem abgibt, wodurch es etwas anderes planen kann. Der Sprecher merkt an, dass es auch eine andere Art von Mutex gibt, die als kompetitiver Mutex bezeichnet wird und beide Ziele eines sich drehenden Mutex und eines nachgiebigen Mutex erreicht. Der Redner untersucht auch die Verwendung von Message-Passing oder Interrupts, um wartende Threads zu informieren, stellt jedoch fest, dass die einfachere Lösung darin bestünde, einen gegenseitigen Ausschlussmechanismus zu verwenden.

  • 00:50:00 In diesem Abschnitt erläutert der Referent das Konzept der Kontextumschaltung, dh wie oft das Betriebssystem zwischen Threads auf verfügbaren Prozessoren umschaltet. Typischerweise wechselt das System etwa 100 Mal pro Sekunde den Kontext, was bedeutet, dass jeder Wechsel etwa 10 Millisekunden dauert. Dies ist jedoch mehr als eine Größenordnung länger als die Ausführungszeit einer einfachen Anweisung, was bedeutet, dass viele Anweisungen ausgeführt werden können, bevor der Thread die Chance hat, zurückzukommen und eine Sperre zu ergreifen. Dieses Problem kann durch eine Kombination aus Spinnen und Nachgeben gelöst werden. Der Referent nennt dies in der Theorieliteratur das „Skiverleihproblem“.

  • 00:55:00 In diesem Abschnitt erläutert das Video den Prozess der Entscheidung, ob Ausrüstung für eine bestimmte Aufgabe gekauft oder gemietet werden soll, am Beispiel des Kaufs oder der Miete von Sportausrüstung. Der Redner ermutigt die Zuschauer, die Kosten für Miete und Kauf zu berücksichtigen, und schlägt vor, zu mieten, bis die Kosten denen des Kaufs entsprechen, und dann den Kauf zu tätigen. Das Video untersucht auch das Konzept der Kontextwechselzeit, der Festplattenzugriffszeit und das Problem des Deadlocks, wenn mehrere Sperren gleichzeitig gehalten werden. Insgesamt deckt dieses Segment grundlegende Prinzipien des Performance Engineering in Mehrkernprozessoren ab.

  • 01:00:00 In diesem Abschnitt erläutert der Referent einen Deadlock, bei dem zwei Threads Ressourcen enthalten, die beide vom anderen Thread benötigt werden, was zu einem Leistungsverlust führt. Es gibt drei Grundbedingungen für Deadlocks: gegenseitiger Ausschluss (exklusive Kontrolle über Ressourcen), Nicht-Präemption (Ressourcen werden gehalten, bis sie fertig sind) und zirkuläres Warten (ein Zyklus von Threads, die auf Ressourcen warten, die vom nächsten gehalten werden). Das Entfernen einer dieser Einschränkungen kann das Deadlock-Problem lösen. Der Redner verwendet „Dining Philosophers“, eine Geschichte, die von Tony Hoare auf der Grundlage einer Prüfungsfrage von Edsger Dijkstra erzählt wird, um das Problem mit Deadlocks zu veranschaulichen. Die Geschichte handelt von Philosophen, die um einen Tisch sitzen und Nudeln mit Essstäbchen essen, wobei sich jeder Nudelteller zwischen zwei Essstäbchen befindet, und sie benötigen zwei Essstäbchen, um die Nudeln zu essen. Die Philosophen greifen links und rechts nach den Essstäbchen, um ihre Nudeln zu essen. Wenn sie jedoch alle das linke Essstäbchen zu ihrer Linken aufheben, werden sie am Ende verhungern.

  • 01:05:00 In diesem Abschnitt erörtert der Referent das Problem des Deadlocks bei der parallelen Programmierung und bietet eine Lösung an, die eine Nicht-Präemption sicherstellt und gleichzeitig Deadlocks vermeidet: lineare Anordnung von Mutexes. Indem jeder Mutex nummeriert und basierend auf seiner numerischen Reihenfolge strategisch gesperrt wird, können Programmierer garantieren, dass kein Wartezyklus (die notwendige Bedingung für Deadlocks) auftreten kann. Er warnt Programmierer jedoch davor, sich der Kapselung von Sperren durch das Laufzeitsystem in Silk bewusst zu sein, da die Einführung von zusätzlichem Nicht-Determinismus durch diese Sperren zu Problemen führen kann. Er nennt ein Beispiel, bei dem Deadlocks mit nur einer Sperre auftreten können, und betont, wie wichtig sorgfältige Überlegungen beim Entwerfen paralleler Programme sind.

  • 01:10:00 In diesem Abschnitt befasst sich der Referent mit dem Thema des Transaktionsspeichers, einer neueren Technik auf Forschungsniveau, die Datenbanktransaktionen beinhaltet, bei denen die Atomarität implizit erfolgt, ohne dass Sperren angegeben werden müssen. Der Sprecher gibt ein Beispiel dafür, wie Transaktionsspeicher bei der gleichzeitigen Berechnung von Graphen nützlich sind, nämlich die Gauss'sche Eliminierung, bei der die gleichzeitige Eliminierung von zwei Knoten Unteilbarkeitsverletzungen verursacht. Die Idee hinter dem Transaktionsspeicher besteht darin, den kritischen Bereich als Transaktion darzustellen, und beim Festschreiben erscheinen alle Speicheraktualisierungen im kritischen Bereich so, als ob sie gleichzeitig erfolgten.

  • 01:15:00 In diesem Abschnitt erörtert der Sprecher Konfliktlösung, Konfliktlösung, Vorwärtsfortschritt und Durchsatz im Transaktionsspeicher. Sie führen einen Algorithmus ein, der einen lock-basierten Ansatz mit einem endlichen Ownership-Array und einer Release-Sortierung-Require-Methode verwendet, um Deadlocks und Hunger zu verhindern, ohne dass eine globale Sperre erforderlich ist. Der Algorithmus protokolliert Lese- und Schreibvorgänge, um ein Rollback oder einen atomaren Commit zu ermöglichen, wenn eine Transaktion abgebrochen wird. Das Lock-Array wird verwendet, um einen Ort zu sperren, auf den eine Hash-Funktion abgebildet wird, was einen fairen Erwerb von Sperren ermöglicht. Dieser Algorithmus ermöglicht gleichzeitige Transaktionen ohne Leistungseinbußen oder Deadlocks.

  • 01:20:00 In diesem Abschnitt diskutiert der Sprecher einen Algorithmus namens Release Sort and Reacquire. Der Algorithmus arbeitet, indem er gierig versucht, eine Speicherstelle zu sperren, und wenn ein Konflikt auftritt, wird die Transaktion zurückgesetzt, ohne die von ihr gehaltenen Sperren freizugeben. Danach gibt der Algorithmus alle Sperren mit Indizes frei, die größer sind als der Index des Speicherorts, auf den er zuzugreifen versucht. Es erwirbt dann die gewünschte Sperre und erwirbt schließlich die freigegebenen Sperren in sortierter Reihenfolge. Dieser Vorgang wird wiederholt, bis die Transaktion erfolgreich ist. Der Algorithmus soll verhindern, dass mehrere Sperren gleichzeitig versuchen, eine Sperre zu erwerben, was zu Leistungsproblemen führen kann.
 

Vorlesung 17. Synchronisation ohne Sperren



Vorlesung 17. Synchronisation ohne Sperren

Charles Leiserson untersucht das Konzept der Synchronisierung ohne Sperren in einem YouTube-Video. Er liefert ein Beispiel, das die Notwendigkeit einer globalen linearen Reihenfolge von Anweisungen demonstriert, um eine sequentielle Ausführung sicherzustellen, und erörtert, wie ein gegenseitiger Ausschluss durch sequentielle Konsistenz erreicht werden kann, wodurch die Schwierigkeiten und potenziellen Probleme der Verwendung von Sperren vermieden werden. Leiserson präsentiert Petersons Algorithmus als eine Lösung, die nur Lade- und Speicheroperationen verwendet, um auf kritische Abschnitte zuzugreifen, ohne von gleichzeitigen Prozessen gestört zu werden. Das Video behandelt auch die Herausforderungen der Synchronisierung durch Speicher aufgrund von Hardware-Neuordnungen und das Konzept von Speicherzäunen, um die relative Reihenfolge mit anderen Anweisungen aufrechtzuerhalten. Leiserson argumentiert, dass die Unterstützung sequentieller Konsistenz für parallele Maschinen zwar vorteilhaft, aber für Hardwaredesigner schwer zu erreichen ist.

Der zweite Teil des Videos behandelt die Verwendung von Speicherzäunen und Synchronisationsanweisungen zur Vermeidung von Fehlern in parallelen Programmen. Der Referent untersucht verschiedene Arten der Implementierung von Speicherzäunen, implizit oder explizit, und die Bedeutung einer sorgfältigen Konstruktion und Koordination zwischen verschiedenen Teams, die an verschiedenen Aspekten eines Prozessors arbeiten. Darüber hinaus diskutiert der Dozent die Verwendung von CAS-Anweisungen als Teil des Lock-Free-Algorithmus im C11-Sprachstandard, um Mutexe von n-Thread-Deadlock-freien Mutual-Exclusion-Algorithmen zu implementieren, die nur konstanten Speicherplatz verwenden. Charles Leiserson erläutert das Problem der Verwendung von Sperren in einem Multithread-System und die Lösung, stattdessen CAS zu verwenden, da ein Thread, der die Sperre für lange Zeit aufrechterhält, möglicherweise andere Threads blockieren kann, die darauf warten, auf dieselbe Ressource zuzugreifen. Darüber hinaus hebt das Video das potenzielle Problem des ABA-Problems mit Compare-and-Swap hervor und ermutigt diejenigen, die sich für das Thema interessieren, mehr über lock-freie Algorithmen zu erfahren.

  • 00:00:00 und ihre Anweisungen werden verschachtelt, um eine globale lineare Reihenfolge aller Anweisungen zu erzeugen. Das ist die Idee hinter dem Gedächtnismodell der sequentiellen Konsistenz, das aus theoretischer Sicht das wichtigste Gedächtnismodell ist. Es ist wichtig, Speichermodelle zu verstehen, da das Verhalten paralleler Programme ohne Sperren vom Speichermodell abhängt. Ein in der Vorlesung vorgestelltes Beispiel verdeutlicht diesen Punkt, indem es fragt, ob es möglich ist, dass zwei Prozessoren beide den Wert 0 haben, nachdem sie ihren Code parallel ausgeführt haben, was vom verwendeten Speichermodell abhängt.

  • 00:05:00 In diesem Abschnitt erörtert Charles Leiserson das Konzept der Synchronisierung ohne Sperren, bei der Lade- und Speichervorgänge anscheinend einer globalen linearen Reihenfolge gehorchen müssen, damit die Ausführung sequentiell erfolgt. Am Beispiel der Verschachtelung verschiedener Werte demonstriert er unterschiedliche Ausführungspfade, die auftreten können und wie die Hardware machen kann, was sie will. Er erklärt auch, dass es zwar viele verschiedene Möglichkeiten zum Verschachteln von Werten geben kann, es aber so aussehen muss, als ob die Lade- und Speichervorgänge einer linearen Reihenfolge folgen, damit die Ausführung konsistent ist. Letztendlich kommt Leiserson zu dem Schluss, dass es keine Ausführung gibt, die damit endet, dass beide Werte Null sind, und es ist interessant festzustellen, dass keiner von modernen Computern sequentielle Konsistenz bietet.

  • 00:10:00 In diesem Abschnitt wird das Konzept der sequentiellen Konsistenz erörtert, was das Verständnis der Beziehung zwischen Befehlen und ihrer Reihenfolge, der linearen Beziehung zwischen der Rechtspfeilverbindung, der Prozessorreihenfolge und der Sequenzierung von Befehlen beinhaltet. Außerdem kann ein gegenseitiger Ausschluss erreicht werden, ohne dass Hochleistungsbefehle oder Sperren verwendet werden, indem man über sequentielle Konsistenz nachdenkt und die gemeinsame Datenstruktur durch die Verwendung von Lade- und Speichervorgängen implementiert. Die Vorlesungsunterlagen beschreiben Methoden, die spezialisierte Operationen wie Testen und Setzen oder Vergleichen und Austauschen verwenden, aber die vorgestellte Lösung vermeidet das Entstehen von Deadlocks oder anderen schlechten Dingen, die bei der Verwendung von Sperren auftreten.

  • 00:15:00 In diesem Abschnitt erläutert Charles Leiserson Petersons Algorithmus zum Erzielen gegenseitigen Ausschlusses in einem gleichzeitigen Programm, das nur Lade- und Speicheroperationen verwendet. Der Algorithmus ermöglicht es zwei gleichzeitigen Prozessen, Alice und Bob, Code auszuführen, ohne sich gegenseitig zu stören, indem er einen Satz von Variablen und einen Turn-Taking-Mechanismus verwendet. Der Code stellt sicher, dass jeweils nur ein Prozess in einen kritischen Abschnitt eintreten und eine gemeinsam genutzte Ressource ändern kann. Im Gegensatz zu Sperren ist der Algorithmus von Peterson nicht darauf angewiesen, eine Sperre zu erwerben oder freizugeben, sondern verwendet stattdessen Ladevorgänge und Speichervorgänge, um einen gegenseitigen Ausschluss zu erreichen.

  • 00:20:00 In diesem Abschnitt diskutiert der Sprecher Petersons Algorithmus zum Erzielen eines gegenseitigen Ausschlusses im kritischen Abschnitt ohne Verwendung von Sperren. Er erklärt, dass jeweils nur eine Person den kritischen Abschnitt betreten kann, und der Algorithmus stellt sicher, dass jemand, der den kritischen Abschnitt betreten möchte, dies tun kann, wenn er der einzige ist, der gehen möchte. Der Sprecher präsentiert dann einen Beweis des Algorithmus, bei dem angenommen wird, dass sich sowohl Alice als auch Bob gemeinsam im kritischen Abschnitt befinden und einen Widerspruch herleiten. Der Beweis beruht auf der "passiert vorher"-Beziehung und der Programmreihenfolge der ausgeführten Befehle.

  • 00:25:00 In diesem Abschnitt erklärt der Sprecher den Vorgang der Synchronisierung ohne Sperren. Sie erstellen Befehlsketten und stellen sicher, dass sie in der richtigen Reihenfolge ausgeführt werden, um Synchronisationsfehler zu vermeiden. Sie verwenden das Beispiel von Bob und Alice, die als Demonstration auf eine gemeinsam genutzte Ressource zugreifen möchten. Sie erklären, dass Ingenieure beim Synchronisieren vorsichtig sein und die „Vorherigen Ereignisse“ überprüfen müssen, um sicherzustellen, dass sie in der richtigen Reihenfolge auftreten.

  • 00:30:00 In diesem Abschnitt erörtert Charles Leiserson das Konzept der Modellprüfung und seine Verwendung bei der Analyse von Netzwerk-, Sicherheits- und Cache-Protokollen. Anschließend erläutert er die Eigenschaften von Petersons Algorithmus, der Hungerfreiheit garantiert, aber nicht mit mehr als zwei Prozessen arbeitet. Leiserson untersucht auch die Herausforderungen der Synchronisierung über den Speicher und den Mangel an sequentieller Konsistenz in modernen Prozessoren, was zu einer entspannten Speicherkonsistenz und Schwierigkeiten bei der korrekten Synchronisierung führt.

  • 00:35:00 ist es sicher, Anweisungen neu zu ordnen, ohne Probleme mit der Ladelatenz zu verursachen? Die zweite Einschränkung besteht, wenn keine Datenabhängigkeit zwischen Befehlen besteht, was bedeutet, dass die Befehle keine Daten gemeinsam nutzen oder denselben Ort im Speicher verwenden. Das Neuordnen von Anweisungen kann in diesem Fall die Leistung verbessern und eine Überladelatenz abdecken, da das Laden früher erfolgen kann und andere Arbeiten ausgeführt werden können, während auf das Ergebnis gewartet wird. Das Verständnis dieser Konzepte auf Hardwareebene kann dabei helfen, über Software nachzudenken und die Leistung zu optimieren.

  • 00:40:00 In diesem Abschnitt erläutert Charles Leiserson das Konzept der synchronen Neuordnung ohne Sperren. Er stellt klar, dass die Neuordnung sicher durchgeführt werden kann, solange keine Parallelität besteht, insbesondere wenn der Prozessor in Betrieb ist oder es Blasen im Befehlsstrom gibt. Dies liegt daran, dass die Hardware in modernen Prozessoren Daten in einem Puffer speichert und Lasten umgeht, indem sie direkt zum Speichersystem geht. Dieses Umgehen kann jedoch zu Problemen mit der Korrektheit führen, wenn einer der Speicher das geladene Ding ist.

  • 00:45:00 In diesem Abschnitt erklärt Charles Leiserson, wie die Hardware-Neuordnung abläuft und warum sie die sequentielle Konsistenz nicht erfüllt und dass x86 ein Speicherkonsistenzmodell namens Total Store Order hat, das schwächer ist als die sequentielle Konsistenz. Die Regeln für die Gesamtspeicherreihenfolge beinhalten niemals das Umordnen von Ladungen mit Ladungen, Ladungen, die von externen Prozessoren in derselben Reihenfolge gesehen werden, Speichern, die nie mit Speichern neu geordnet werden, und Ladungen, die nur mit vorherigen Speichern an einem anderen Ort neu geordnet werden, aber nicht mit vorherigen Ladungen an der gleiche Ort. Die Verriegelungsbefehle und die Speicherordnung respektieren eine Gesamtordnung.

  • 00:50:00 In diesem Abschnitt erläutert der Sprecher, wie die Neuordnung von Anweisungen die sequentielle Konsistenz verletzen und zu falschen Werten führen kann. Eine Neuordnung kann sowohl in der Hardware als auch im Compiler erfolgen, und es ist wichtig zu wissen, dass Sperrbefehle nicht vor andere Befehle verschoben werden. Der Sprecher weist auch darauf hin, dass Lasten vor Geschäften gehen können, wenn sie an eine andere Adresse gehen. Die Gefahr des Umordnens zeigt sich in Petersons Algorithmus, der bei bestimmten Umordnungen völlig vermasselt werden könnte. Daher ist es wichtig, deterministischen Code zu schreiben, um diese Probleme bei der Synchronisierung über den Arbeitsspeicher zu vermeiden.

  • 00:55:00 In diesem Abschnitt erörtert Charles Leiserson das Problem der Neuordnung beim Schreiben von parallelem und nebenläufigem Code, bei dem es wichtig ist, zu vermeiden, dass eine bestimmte Last vor einem Speichern auftritt. Um solche Szenarien zu handhaben, führen Ingenieure Speicherzäune ein, die die relative Reihenfolge mit anderen Anweisungen aufrechterhalten, aber sie gehen auf Kosten einer erhöhten Komplexität und potenzieller Fehler. Leiserson argumentiert auch, dass es für parallele Maschinen vorteilhaft ist, sequentielle Konsistenz zu unterstützen, aber es eine Herausforderung für Hardware-Designer ist, dies zu erreichen.

  • 01:00:00 In diesem Abschnitt erörtert der Referent die Bedeutung von Speicherzäunen und Synchronisationsanweisungen, um zu verhindern, dass parallele Programme auf Fehler stoßen. Der Referent beschreibt verschiedene Möglichkeiten, wie Speicherzäune implementiert werden können, etwa explizit als Befehl oder implizit durch andere Synchronisationsbefehle wie Sperren und Austauschen. Es gibt jedoch Fälle, in denen ein Speicherzaun ein Programm tatsächlich verlangsamen kann, was zeigt, wie wichtig sorgfältiges Engineering und Koordination zwischen verschiedenen Teams sind, die an verschiedenen Aspekten eines Prozessors arbeiten. Darüber hinaus rät der Referent, flüchtige Variablen und Compiler-Fences zu verwenden, um zu verhindern, dass der Compiler Variablen wegoptimiert und Fehler im parallelen Code verursacht.

  • 01:05:00 In diesem Abschnitt behandelt der Dozent die Synchronisation ohne Sperren im Sprachstandard C11. Der Standard definiert ein schwaches Speichermodell, das es ermöglicht, Dinge als atomar zu deklarieren, was die Verwendung teurer Operationen wie Memory Fence oder eines atomaren Vergleichens und Austauschens für einen Deadlock-freien gegenseitigen Ausschlussalgorithmus erfordert. Hier wird der CAS-Befehl (Compare-and-Swap) als Teil des Lock-Free-Algorithmus untersucht. Die Anweisung prüft, ob der Wert im Speicher derselbe ist wie der alte Wert, bevor er auf den neuen Wert umgestellt wird, was alles atomar erfolgt. Die Verwendung von CAS ermöglicht die Implementierung von Mutexes von Deadlock-freien gegenseitigen Ausschlussalgorithmen mit n-Threads, die nur konstanten Speicherplatz verwenden. Eine Sperranweisung, die sich dreht, bis sie den Wert wahr erhält, wird verwendet, um wahr zu tauschen, um anzugeben, dass jemand die Sperre hält.

  • 01:10:00 In diesem Abschnitt erklärt Professor Charles Leiserson, wie man mit Compare-and-Swap (CAS) Synchronisationsprobleme löst. Er demonstriert, wie CAS als Sperre verwendet wird, und behebt einen Fehler in dem von einem Studenten präsentierten Code. Dann zeigt er einen falschen Code an, der verwendet wird, um die Summe der Werte in einem Array zu berechnen, was zu einer Race-Bedingung führt. Er stellt Mutex-Sperren als typische Lösung vor und erklärt das potenzielle Problem, dass ein Thread nach dem Erwerb der Sperre ausgelagert wird, was dazu führt, dass andere Threads auf die Sperre warten und somit den Fortschritt behindern.

  • 01:15:00 In diesem Abschnitt erläutert Charles Leiserson das Problem der Verwendung von Sperren in einem Multithread-System und die Lösung, stattdessen CAS zu verwenden. Mit Sperren kann ein Thread die Sperre möglicherweise lange Zeit aufrechterhalten und andere Threads blockieren, die darauf warten, auf dieselbe Ressource zuzugreifen. Bei CAS folgt jedoch auf ein Laden von x ein Speichern von x nach dem Berechnen einer Temperatur, während auch die Variablen alt und neu vorhanden sind, um das alte Ergebnis zu speichern und das temporäre Ergebnis zu diesem alten Wert hinzuzufügen, um einen neuen Wert zu erzeugen, der sein kann eingelagert, wenn sich der alte Wert nicht geändert hat. Charles erwähnt auch das ABA-Problem mit Compare-and-Swap und ermutigt diejenigen, die sich für das Thema interessieren, mehr über lock-freie Algorithmen zu erfahren.
 

Vorlesung 18. Domänenspezifische Sprachen und Autotuning



Vorlesung 18. Domänenspezifische Sprachen und Autotuning

In diesem Video erläutert Professor Saman Amarasignhe von der EECS-Abteilung des MIT die Vorteile der Verwendung von domänenspezifischen Sprachen (DSLs) und Autotuning im Performance Engineering. Er betont die Bedeutung von DSLs, die bereichsspezifische Domänen erfassen, die in Allzwecksprachen schwer zu beschreiben sind, und es Programmierern ermöglichen, das Wissen von Domänenexperten für eine bessere Leistung zu nutzen. Singh erörtert die Optimierung von Graphprozessen unter Verwendung von DSLs, einschließlich der Graphpartitionierung und der Bedeutung der Form des Graphen bei der Berechnung. Er stellt das DSL Halide für die Bildverarbeitung vor, das eine schnelle Codeoptimierung und Portierbarkeit über Maschinen hinweg ermöglicht. Er diskutiert den Einsatz von Halogenid in verschiedenen Branchen wie Google und Adobe. Letztendlich hebt er die Bedeutung des Experimentierens mit verschiedenen Ansätzen bei der Optimierung von Code hervor, während er sich auf Parallelität, Lokalität und redundante Arbeit konzentriert.

Das Video spricht auch über die Herausforderungen des Performance Engineering und das Finden der optimalen Parameter für einen effizienten Programmablauf. Der Redner schlägt vor, dass Auto-Tuning dieses Problem angehen kann, indem es den großen Parameterraum automatisch durchsucht, um die optimalen Werte zu finden. Er stellt fest, dass eine erschöpfende Suche unpraktisch sein kann und heuristische Lösungen möglicherweise nicht optimal sind. Autotuning, das einen Bereich akzeptabler Werte definiert und basierend auf Leistungsergebnissen iteriert, kann den Prozess der Suche nach optimalen Lösungen beschleunigen. Der Referent erörtert auch die Anwendung von Autotuning bei der Generierung von Zeitplänen für Try, mit dem Zeitpläne effizienter und effektiver erstellt werden konnten als mit einer erschöpfenden Suche.

  • 00:00:00 In diesem Abschnitt spricht Professor Saman Amarasignhe, Professor in der EECS-Abteilung am MIT, über domänenspezifische Sprachen und Autotuning. Er erklärt, dass diese Sprachen technische Vorteile haben, weil sie bestimmte bereichsspezifische Domänen erfassen, die in einer Allzwecksprache schwer zu beschreiben sind. Domänenspezifische Sprachen sind viel einfacher zu verstehen und zu warten, und sie ermöglichen es dem Programmierer, das Wissen der Domänenexperten zu nutzen, um eine wirklich gute Leistung zu erzielen. Darüber hinaus kann eine domänenspezifische Sprache, wenn sie korrekt erstellt wurde, die Entscheidung auf niedrigerer Ebene dem Compiler überlassen, wodurch der Optimierungsprozess viel einfacher wird.

  • 00:05:00 In diesem Abschnitt erörtert der Referent die Verwendung von domänenspezifischen Sprachen (DSLs) im Performance Engineering. Sie ermutigen dazu, die Leistung wann immer möglich dem Compiler zu überlassen, und führen drei verschiedene Programmiersprachen/Frameworks für die Graphverarbeitung ein: Graffiti, Halide und OpenTuner. Sie weisen darauf hin, dass Grafiken überall zu finden sind, von der Google-Suche bis hin zu Empfehlungsmaschinen, und tauchen tiefer in den PageRank-Algorithmus ein, der von Google zum Ranking von Webseiten verwendet wird. Der PageRank-Algorithmus sieht sich die Nachbarn einer Webseite an und berechnet basierend auf ihrem Einfluss einen neuen Rang, was die Bedeutung der Diagrammverarbeitung beim Performance Engineering zeigt.

  • 00:10:00 In diesem Abschnitt erörtert der Redner Graphalgorithmen, die die Verarbeitung großer Datenmengen und iterative Berechnungen für den gesamten Graphen beinhalten können. Um den Code auf Leistung zu optimieren, kann eine DSL verwendet werden. Die Art von Algorithmen, die für die Graphenverarbeitung verwendet werden, umfasst topologiegesteuerte Algorithmen, bei denen der gesamte Graph an der Berechnung teilnimmt, und datengesteuerte Algorithmen, bei denen die Verarbeitung in einem kleinen Bereich oder Teil des Graphen erfolgt. Es gibt auch mehrere Möglichkeiten, Graphumkehrungen durchzuführen, und jede Methode hat unterschiedliche Ergebnisse.

  • 00:15:00 In diesem Abschnitt wird das Thema der Graphpartitionierung behandelt, bei der ein großer Graph in kleinere Teile unterteilt wird. Der Vorteil der Partitionierung eines Diagramms besteht darin, dass es Parallelität ermöglicht und auch eine gute Lokalität bietet, was bedeutet, dass die Knoten, an denen gearbeitet wird, klein genug sind, um in den Cache zu passen. Die Graphpartitionierung wirkt sich auch auf Graphen sozialer Netzwerke aus, da sie eine Potenzgesetzbeziehung haben. Das bedeutet, dass bestimmte Knoten mehr Verbindungen oder einen größeren Einfluss haben als andere, und bei der Verarbeitung dieser Diagramme müssen bestimmte Verbindungen und Knoten aufgrund ihrer Bedeutung mehr Aufmerksamkeit erhalten.

  • 00:20:00 In diesem Abschnitt erörtert der Redner die Bedeutung der Form eines Graphen bei der Berechnung, insbesondere wie die Größe und Lokalität eines Graphen die Effizienz von Parallelitätsalgorithmen beeinflussen können. Faktoren wie Parallelität, Lokalität und erforderliche zusätzliche Arbeit müssen sorgfältig abgewogen werden, um die beste Leistung für einen bestimmten Algorithmus zu erzielen, und die richtige Methode muss basierend auf der Art des Graphen, der Art des Algorithmus und der verwendeten Hardware ausgewählt werden. Eine domänenspezifische Sprache wurde entwickelt, um den konstanten Algorithmus von den Verarbeitungsmethoden zu trennen und diese Faktoren besser zu optimieren.

  • 00:25:00 In diesem Abschnitt erörtert der Referent, wie domänenspezifische Sprachen (DSLs) verwendet werden können, um Code auf einer höheren Ebene zu schreiben, was ihn einfacher und eleganter macht. Sie geben Beispiele für verschiedene Algorithmen und wie DSLs eine einfache Möglichkeit bieten, sie zu berechnen. Darüber hinaus erklärt der Referent, wie das Scheduling von DSLs optimiert werden kann, um die bestmögliche Geschwindigkeit zu erreichen, sogar unter Berücksichtigung der Parallelverarbeitung. Der Code kann basierend auf Änderungen im Graphen oder der Maschine variiert werden, aber der Algorithmus bleibt derselbe. Der Redner betont die Bedeutung von DSLs, die eine einfache Programmierung bieten und gleichzeitig leistungsstark genug sind, um optimierte Zeitpläne zu erstellen.

  • 00:30:00 In diesem Abschnitt diskutiert der Sprecher eine andere domänenspezifische Sprache, Halide, die sich auf die Bildverarbeitung mit dichten, regelmäßigen Strukturen konzentriert. Halide trägt dazu bei, den Programmieraufwand zu reduzieren, der zum Erzielen einer optimierten Leistung erforderlich ist, und erhöht die Übertragbarkeit des Programms auf verschiedene Computer. Der Redner liefert ein Drei-mal-drei-Unschärfebeispiel, um zu demonstrieren, wie Halide funktioniert. Halide hat ein ähnliches Muster wie die zuvor besprochene Graphensprache in Bezug auf die Optimierung der Leistung durch verschiedene Kombinationen verschiedener Techniken.

  • 00:35:00 In diesem Abschnitt erörtert der Referent die Verwendung von domänenspezifischen Sprachen (DSLs) und Autotuning zur Optimierung der Codeleistung. Er liefert ein Beispiel für einen Bildfilter, der mit einer DSL namens Halide schneller läuft als mit gültigem C-Code. Halide ermöglicht die Entkopplung des Algorithmus vom Zeitplan, was eine einfache Optimierung der Pipeline der ausgeführten reinen Funktionen ermöglicht. Schließlich betont der Redner die Notwendigkeit eines Kompromisses zwischen Lokalität, Parallelität und redundanter Arbeit, um die beste Leistung aus den verfügbaren Rechenressourcen zu erzielen.

  • 00:40:00 In diesem Abschnitt geht der Referent auf die Bedeutung der Lokalität bei der Bildverarbeitung ein. Bei der Verarbeitung eines großen Bildes ist es nicht effizient, Filter anzuwenden, die auf das gesamte Bild auf einmal wirken, da es nicht in den Cache passt. Stattdessen schlägt der Sprecher vor, das Bild in kleinere Abschnitte zu zerlegen und Filter auf jeden Abschnitt anzuwenden, wobei der Schwerpunkt auf Lokalität und Parallelität liegt. Dies kann durch die Verwendung eines Scheduling-Frameworks und die Optimierung der Berechnungsbandbreite und Speichergranularität erreicht werden. Es kann auch einige redundante Arbeit erfordern, um eine bessere Lokalität und Parallelität zu erreichen.

  • 00:45:00 In diesem Abschnitt erörtert der Redner domänenspezifische Sprachen und Autotuning, wobei der Schwerpunkt auf der Verwendung von Halide liegt. Halide kann Bibliotheksfunktionen miteinander verschmelzen, was schneller ist als das Aufrufen von Bibliotheken, da mehr Lokalität vorhanden ist. Der Referent zeigt, wie Halide Rechenprozesse wie bilaterale Filterberechnung und Segmentierungsalgorithmen optimieren kann. In einem Beispiel war ein in MATLAB geschriebener Segmentierungsalgorithmus, der manuell optimierte Bibliotheken aufgerufen hatte, 70-mal schneller, wenn er in Halide geschrieben wurde. Halogenid ist ein wichtiger Bestandteil von Google und wurde in Android-Telefone integriert und in Google Glass verwendet.

  • 00:50:00 In diesem Abschnitt erörtert der Redner die Effektivität der Verwendung von Halide für die Front-End-Verarbeitung und wie es in verschiedenen Branchen weit verbreitet ist. Halide weist im Vergleich zu früheren Versionen eine Geschwindigkeitssteigerung von 4-5 % auf, was für Google angesichts der Anzahl der heruntergeladenen Videos von Bedeutung ist. Adobe hat außerdem angekündigt, dass ganze Photoshop-Filter in Halide geschrieben sind. Auch der Snapdragon-Bildprozessor und Intel fangen an, Halide zu verwenden. Der Redner erörtert auch, wie Halide und Graph Ähnlichkeiten in Bezug auf die Fähigkeit zur Automatisierung der Optimierung haben, was die Arbeit des Performance-Ingenieurs erleichtert. Bei der algorithmischen Optimierung handelt es sich jedoch um eine übergeordnete Änderung, die spezifisches Kontextwissen erfordert und daher schwer zu automatisieren ist. Nichtsdestotrotz geben Tools wie geplante Sprachen den Benutzern die Möglichkeit, verschiedene Ansätze auszuprobieren und eine bessere Leistung zu erzielen.

  • 00:55:00 In diesem Abschnitt erörtert der Referent die Komplexität moderner Computersysteme und erklärt, dass es nicht den einen richtigen Weg zur Codeoptimierung gibt. Sie betonen die Bedeutung des Ausprobierens unterschiedlicher Ansätze und die Bedeutung von Caches, Lokalität und Parallelität. Sie diskutieren auch, wie Menschen in verschiedenen Bereichen wie Biologie und Physik viel Zeit damit verbringen, Code zu optimieren, anstatt Forschung zu betreiben, weil sie aufgrund der Codekomplexität nicht in der Lage sind, Programme schnell genug zu schreiben. Der Redner schlägt vor, dass das Auffinden von Domänen, in denen Menschen die meiste Zeit mit Hacken und Abstraktion verbringen, ein interessantes Forschungsgebiet sein kann. Insgesamt umfasst der Bereich, in dem Programme optimiert werden können, Parallelität, Lokalität und redundante Arbeit, und das Spielen in diesem Bereich ist für Leistungsingenieure von entscheidender Bedeutung.

  • 01:00:00 In diesem Abschnitt geht der Referent auf die Herausforderungen des Performance Engineering ein, bei dem es darum geht, die richtigen Parameter für einen optimalen Programmablauf zu finden. Er erklärt, dass es zahlreiche Parameter gibt, die angepasst werden können, wie z. B. die Speicherzuweisung und die Blockgröße, aber dass es schwierig sein kann, die richtigen Werte für jeden Parameter für jedes Programm zu bestimmen. Der Sprecher schlägt jedoch vor, dass Auto-Tuning dieses Problem lösen kann, indem der große Parameterraum automatisch durchsucht wird, um die optimalen Werte zu finden. Er erklärt, dass heuristische Lösungen, die fest codierte Regeln für bestimmte Situationen beinhalten, die meiste Zeit funktionieren können, aber möglicherweise nicht immer optimal sind. Der Referent weist auch darauf hin, dass das Erstellen von Modellen des Systems problematisch sein kann, da das Modell nicht alle wichtigen Faktoren berücksichtigt, was zu suboptimalen Ergebnissen führen kann.

  • 01:05:00 In diesem Abschnitt erörtert der Referent die Herausforderungen, angesichts sich ändernder Technologien oder sich ändernder Anforderungen optimale Lösungen zu finden. Er stellt fest, dass es eine Vielzahl von „Heuristiken“ gibt, die Programmierer verwenden, um ihre Lösungen zu steuern, oft basierend auf Richtlinien oder Faustregeln, die möglicherweise nicht mehr anwendbar sind. Eine Option ist die erschöpfende Suche, die jedoch angesichts der schieren Anzahl möglicher Permutationen unpraktisch sein kann. Um dem entgegenzuwirken, empfiehlt der Referent die Verwendung von Autotuning, um den Suchraum zu beschneiden und optimale Lösungen schneller zu finden. Autotuning umfasst das Definieren eines Bereichs akzeptabler Werte, das zufällige Auswählen eines zu testenden Werts und das anschließende Iterieren basierend auf den Leistungsergebnissen. OpenTuner ist ein Beispiel für ein Framework, das eine Reihe von Techniken wie Bergsteiger und Zufallssuche verwendet, um diesen iterativen Prozess zu beschleunigen.

  • 01:10:00 In diesem Abschnitt erörtert der Referent das Konzept der automatischen Abstimmung und wie es bei der Generierung von Zeitplänen für Try angewendet werden kann. Durch das Verständnis der beteiligten Graphen und Rhythmen kann die automatische Abstimmung verwendet werden, um einen Zeitplan effizienter und effektiver zu erstellen als eine erschöpfende Suche. Diese Methode war in der Lage, Zeitpläne in weniger als zwei Stunden zu erstellen, und in einigen Fällen sogar besser als das, was ursprünglich als der bestmögliche Zeitplan angesehen wurde.
 

Vorlesung 19. Leiserchess Codewalk



Vorlesung 19. Leiserchess Codewalk

In diesem YouTube-Video mit dem Titel „19. Leiserchess Codewalk“ erklärt Helen Xu die Regeln von Lesierchess, einem Spiel, das von zwei Teams gespielt wird, mit dem Ziel, den König des gegnerischen Teams zu erschießen oder Ihren König erschießen zu lassen. Das Spiel hat zwei Arten von Zügen, Grund- und Schlagzüge, und eine Ko-Regel, die einen Zug illegal macht, wenn er den letzten Zug des Gegners rückgängig macht. Xu taucht in verschiedene Aspekte des Spiels ein, darunter die Fisher-Zeitsteuerungsmethode, Forsythe-Edwards-Notation, Cloud-Autotester und Projektorganisation, Bewertung und Vergleich von Bots anhand von Elo-Bewertungen, Generierung von Zügen, statische Bewertung und Suchalgorithmen wie Alpha-Beta, Prinzipvariation, Subtree Pruning und Transpositionstabellen. Sie erörtert auch die Bedeutung der Testinfrastruktur für die Optimierung des Programms und der Datei eval.c, die Heuristiken enthält, die jedes Feld auf dem Brett basierend auf der Art der Figur und ihrer Farbe bewerten.

Der Redner geht auch auf den Laserabdeckungsaspekt des Spiels ein und erklärt das komplizierte System der Generierung aller möglichen Züge für eine Position basierend auf der Farbe des Spielers unter Verwendung einer while-true-Anweisung. Sie erklären auch die Bedeutung der Korrektheit im Code und wie man darauf testet, und schlagen die Konvertierung der Darstellung vor, um die Korrektheit vor der Leistungsoptimierung sicherzustellen. Der Redner erörtert auch die große Flexibilität, die die Leiserchess UCI-Schnittstelle bietet, die es Benutzern ermöglicht, Tabellen und Befehle nach ihren Wünschen zu bearbeiten, und versichert den Zuschauern, dass der tote Code bereinigt wird und alle anderen Fehler zur Behebung gemeldet werden sollten.

  • 00:00:00 In diesem Abschnitt geht Helen durch die Regeln des Lesierchess-Spiels und wie man es spielt. Das Spiel wird von zwei Teams gespielt, Orange und Lavendel, wobei jedes Team sieben Bauern und einen König hat. Das Ziel des Spiels ist es, den König des gegnerischen Teams zu erschießen oder Ihren König erschießen zu lassen. Das Spiel hat zwei Arten von Moves, Basic- und Swat-Moves. Das Spiel hat außerdem eine Ko-Regel, die einen Zug illegal macht, wenn er den letzten Zug des Gegners rückgängig macht, indem er einfach dorthin zurückkehrt, wo das gegnerische Team war. Ein Unentschieden liegt vor, wenn jedes Team 50 Züge gemacht hat, ohne dass ein Bauer gezapped wurde, dieselbe Stellung sich wiederholt oder die beiden Teams dem Remis zustimmen.

  • 00:05:00 In diesem Abschnitt erklärt der Sprecher die Fisher-Zeitsteuerungsmethode, die im Leiserschach verwendet wird. Jeder Spieler beginnt mit einem anfänglichen Zeitbudget und einem Zeitinkrement. In dem verwendeten Beispiel beginnt jeder Spieler mit 60 Sekunden, und wenn er seinen Zug beendet, erhält er 0,5 zusätzliche Sekunden. Aber das tatsächliche Zeitlimit kann alles sein. Der Sprecher demonstriert dann, wie man leiserchess spielt, indem er das Publikum auffordert, Züge für Tangerine vorzuschlagen, um den Bauern in F5 zu zappen, während er Gegenangriffe vermeidet. Der Sprecher warnt jedoch vor den Feinheiten des Spiels, wie dem naiven Töten aller Figuren, da dies den Gegner öffnen könnte.

  • 00:10:00 In diesem Abschnitt bespricht Helen Xu die Forsythe-Edwards-Notation als ein Werkzeug zur Darstellung einer Schachstellung mithilfe einer Zeichenfolge, was für Debugging-Zwecke nützlich ist und es einem ermöglicht, leicht zu einer bestimmten Stellung zurückzukehren. Sie erklärt auch, wie man Protokolle von Schachpartien liest, wo sie jeden Zug und die entsprechenden Anmerkungen aufschlüsselt. Außerdem demonstriert sie, wie man den Scrimmage-Server nutzt, um Bots mit anderen Teams in der Klasse zu testen, wie man andere Teams herausfordert und sich die gespielten Spiele ansieht.

  • 00:15:00 In diesem Abschnitt erläutert Helen Xu den Cloud-Autotester und die Projektorganisation für Lesierchess. Während der Scrimmage-Server jeweils nur ein Spiel zulässt, kann der Cloud-Autotester mehrere Spiele und Binärdateien mit einer Zeitsteuerung ausführen, die an die Vorlieben jedes Benutzers angepasst werden kann. Die Projektorganisation im Repo umfasst die Verzeichnisse doc, auto tester, pgnstates, tests, player und webgui. Der Autotester ist ein lokaler Java-Autotester, der verwendet wird, um Änderungen lokal zu testen, während im Verzeichnis tests Konfigurationen für Autotests angegeben werden können. Helen Xu stellt auch das Universal Chest Interface (UCI) vor, ein Kommunikationsprotokoll, das von Lesierchess als Schnittstelle zum Autotester verwendet wird.

  • 00:20:00 In diesem Abschnitt erläutert der Redner, wie die Bots anhand von Elo-Bewertungen gemessen und verglichen werden, einem Bewertungssystem, das auf dem relativen Fähigkeitsniveau in Nullsummenspielen basiert. Die Elo-Wertung basiert nicht nur auf der Zeit, sondern auch auf den mit der UCI gesuchten Knoten pro Sekunde. Der Sprecher geht dann detaillierter auf das Spielen des Spiels ein, z. B. das Generieren von Zügen, die Brettdarstellung und die Struktur, die zum Speichern der Position verwendet wird. Zusätzlich wird der Zug mit 28 Bits dargestellt, was den Figurentyp, die Ausrichtung, das Ausgangsfeld, das Zwischenfeld und die beiden Felder umfasst. Die Referenzimplantation generiert alle Züge in Abhängigkeit davon, wer an der Reihe ist, indem sie durch das Brett iteriert und alle Züge aus dieser bestimmten Figur generiert. Der Sprecher erwähnt die Verwendung der Debugging-Funktion perft, um sicherzustellen, dass die modifizierte Zuggenerierung die gleichen Züge aus jeder Position zurückgibt.

  • 00:25:00 In diesem Abschnitt erläutert der Redner, wie man durch statische Bewertung bestimmt, ob ein Zug gut ist, wodurch mithilfe von Heuristiken eine Punktzahl basierend auf einer Position generiert wird. Die Heuristik umfasst solche, die sich auf König, Bauern und Distanz konzentrieren, und kann dabei helfen, festzustellen, ob eine Stellung gut ist oder nicht. Der Redner spricht auch darüber, wie Spielprogramme Suchbäume verwenden, um das Spiel zu spielen und den besten Zug basierend auf der Bewertung auszuwählen. Um die Anzahl der Knoten zu reduzieren, geht der Referent auf die Ruhesuche und die Min-Max-Suche ein, die die Anzahl der ausgewerteten Knoten verbessern und zu einer besseren Leistung führen können.

  • 00:30:00 In diesem Abschnitt erörtert der Redner den Alpha-Beta-Algorithmus, der während einer Suche von einem Knoten mit einem Alpha-Beta-Fenster verwendet wird. Wenn der Wert der Suche unter Alpha fällt, ist der Zug nicht gut genug und Sie suchen weiter. Beta bedeutet im Wesentlichen, dass eine Seite versucht zu maximieren und eine Seite versucht zu minimieren. Wenn der Wert also über Beta fällt, generieren Sie einen Beta-Cut-Off, weil der Gegner Sie diesen Zug nicht machen lassen würde, da er zu gut wäre. Der Sprecher erklärt dann das Prinzip der Variantensuche, bei der davon ausgegangen wird, dass der erste Zug der beste ist, und Sie führen bei den verbleibenden Zügen eine Scout-Suche durch, die auch als Nullfenstersuche bezeichnet wird, um zu überprüfen, ob sie schlechter sind. Diese Art der Suche ist eine Variation des Alpha-Beta-Algorithmus.

  • 00:35:00 In diesem Abschnitt wird das Konzept des Subtree Pruning in Minimax-Suchalgorithmen diskutiert. Die Idee hinter dem Beschneiden von Teilbäumen besteht darin, Teilbäume zu entfernen, deren Punktzahlen niedriger sind als die bisher gefundene beste Punktzahl. Dadurch wird die Anzahl der ausgewerteten Knoten reduziert und der Suchvorgang beschleunigt. Der Gegner sucht auch nach dem besten Zug und versucht, die Punktzahl des Spielers zu minimieren. Das Gleichgewicht zwischen der Maximierung der Punktzahl des Spielers und der Minimierung der Punktzahl des Gegners ist entscheidend, und das Ziel ist es, einen Zug zu finden, der gut für den Spieler ist und auch etwas, das der Gegner zulassen würde.

  • 00:40:00 In diesem Abschnitt erläutert Helen Xu das Konzept der Beschneidung von Hauptvariationen, bei der die Annahme getroffen wird, dass der Teilbaum ganz links der beste Pfad ist, und frühe Ausstiege vorgenommen werden, wenn die Annahme zutrifft. Wenn die Annahme falsch ist, muss der gesamte Teilbaum durchsucht werden. Die Scout-Suche wird verwendet, um dies rekursiv auf niedrigere Teilbäume anzuwenden, mit anfänglichen Durchläufen, um Annahmen zu verifizieren. Diese Methode verbessert das Pruning und verarbeitet den größten Teil des Spielbaums ohne Fenstersuchen.

  • 00:45:00 In diesem Abschnitt lernen wir Suchoptimierungen für das Leiserchess-Programm kennen. Eine der wichtigsten Optimierungen ist die Verwendung einer Transpositionstabelle zum Speichern zuvor gefundener Positionen, was Zeit spart, indem unnötiges Suchen vermieden wird. Weitere Optimierungen umfassen die Verwendung von Zobrist-Hashing, um eindeutige Hashes für jede Position zu generieren, die Killer-Move-Tabelle, um gute Züge zu speichern, damit sie nicht neu berechnet werden müssen, und Vergeblichkeitsbeschneidung, um Erkundungszüge zu überspringen, die den Alpha-Score nicht erhöhen würden. Auch die Implementierung eines besseren Eröffnungsbuches empfiehlt sich, um vorberechnete Stellungen zu Beginn des Spiels zu speichern und Zeit bei der Suche zu sparen.

  • 00:50:00 In diesem Abschnitt bespricht der Redner einige nützliche Tools zur Optimierung eines Schachprogramms, darunter Eröffnungsbücher und Datenbanken für Endpartien, die vorberechnet werden können. Es ist wichtig zu testen und über eine gute Infrastruktur zum Testen zu verfügen, um innovativ zu sein und Fortschritte zu erzielen, ohne Probleme zu debuggen. Die Verwendung von Transpositionstabellen bei der parallelen Programmierung macht es wichtig, sie zu Testzwecken ausschalten zu können, und es wird empfohlen, beim Testen Suchen mit fester Tiefe durchzuführen. Insgesamt ist eine gute Testinfrastruktur entscheidend, um Fortschritte zu erzielen und erhebliche Debugging-Probleme zu vermeiden.

  • 00:55:00 In diesem Abschnitt geht der Referent auf die eval.c-Datei im Leiserchess-Projekt ein und wie sie aufgrund ihrer Größe und Komplexität auf den ersten Blick überwältigend wirken kann. Wenn die Benutzer jedoch damit vertrauter werden, werden sie Vertrauen in den Umgang mit einem anständigen Codestück gewinnen. Die Datei eval.c enthält Heuristiken wie p between, p central, k face und k aggressive, die jedes Feld auf dem Brett basierend auf der Art der Figur und ihrer Farbe bewerten. Die p between-Heuristik bestimmt, ob sich ein Bauer zwischen den beiden Königen befindet, während p central einen Bonus gibt, der darauf basiert, wie nahe der Bauer an der Mitte des Bretts ist. Die k-Face- und k-Aggressive-Heuristiken geben Boni basierend auf der Ausrichtung des Königs und seiner Entfernung vom Gegner und den Bretträndern.

  • 01:00:00 In diesem Abschnitt erklärt der Sprecher die Laserabdeckung, die ein komplizierter Aspekt des Spiels ist. Die Laserabdeckung generiert alle möglichen Bewegungen einer bestimmten Position in Abhängigkeit von der Farbe des Spielers. Dann liefert es eine Liste von Zügen, und der Sprecher erklärt, wie diese Karte ihre Funktion mit einer while-true-Anweisung ausführt. Der Laserpfad prallt beim Zeichnen des Pfads von einigen Bauern ab und erhöht die Entfernung für jedes Feld. Nach dem Erstellen der Karte wird der Vorgang wiederholt und die Entfernung durch die tatsächliche Entfernung vom Laser dividiert. Dieses komplizierte System optimiert die Iterationen, die in der Bewertungsmethode erforderlich sind, um jedes Stück auf dem Brett zu finden, was den Prozess verlangsamt, und der Sprecher fügt hinzu, dass es eine gute Möglichkeit ist, das Brett anders darzustellen und zu behaupten, dass beide Konvertierungsfunktionen dasselbe Ergebnis liefern Optimierungsentscheidungen.

  • 01:05:00 In diesem Abschnitt des Videos diskutieren die Redner, wie wichtig es ist, die Korrektheit des Codes beizubehalten und wie man darauf testet. Sie erklären, dass das Konvertieren von einer Darstellung in eine andere den Prozess verlangsamen kann, aber notwendig ist, um die Korrektheit sicherzustellen, bevor die Leistung optimiert wird. Eine Möglichkeit, die Korrektheit zu testen, besteht darin, die Anzahl der Knoten zu verfolgen und sicherzustellen, dass sie nach Änderungen gleich bleiben. Sie demonstrieren auch, wie der Code ausgeführt wird, und zeigen die UCI-Schnittstelle in Lesierchess.c, mit der Sie Werte für verschiedene Dinge festlegen können, ohne die Binärdatei jedes Mal neu kompilieren zu müssen. Schließlich gehen sie eine Tabelle mit Heuristiken durch und erklären, wie Werte für den Autotester angegeben werden.

  • 01:10:00 In diesem Abschnitt erläutert der Referent die große Flexibilität, die das Spiel Leiserchess für die Bearbeitung von Tabellen und Befehlen über die UCI-Schnittstelle bietet. Dies ermöglicht Benutzern den Zugriff auf und die Implementierung aller gewünschten Befehle, einschließlich neuer Heuristiken, und die Kontrolle über das Parsen und die Implementierung. Obwohl toter Code vorhanden ist, versichert der Professor den Zuschauern, dass er bereinigt wird und alle anderen Fehler zur Behebung gemeldet werden sollten. Abschließend stellt er fest, dass das Projekt zwar nicht jede Minute Spaß macht, aber insgesamt viel Spaß macht.
 

Vorlesung 20. Spekulativer Parallelismus & Leiserschach



20. Spekulativer Parallelismus & Leiserschach

In diesem YouTube-Video mit dem Titel „20. Speculative Parallelism & Leiserchess“ stellt der Kursleiter das Konzept der spekulativen Parallelität vor, bei der im Wesentlichen vorausschauend vermutet wird, dass bestimmte Aufgaben parallel ausgeführt werden können und zu schnellerem Code führen können. Der Sprecher warnt jedoch davor, dass dieser Code nicht deterministisch ist und nur bei Bedarf verwendet werden sollte, während er auch davor warnt, ihn in Fällen zu verwenden, in denen ein besserer serieller Code verwendet werden könnte. Ein wesentlicher Teil des Videos dreht sich um die Erörterung paralleler Alpha-Beta-Suchen, bei denen der Spielbaum zur Optimierung der Suchzeit beschnitten wird, und spricht auch über verschiedene Datenstrukturen und Heuristiken, die im Bewertungsprozess von Suchalgorithmen verwendet werden, insbesondere zur Vermeidung von Zyklen und Ruhe suchen. Das Video geht auch auf die Vorteile der iterativen Vertiefung ein und wie sie zu einer besseren Zugreihenfolge bei der Suche führt, und diskutiert auch das Zobrist-Hashing, eine Optimierungstechnik, die in Suchalgorithmen verwendet wird und einen eindeutigen Hash-Wert für jede Position auf dem Schachbrett mit denselben Figuren verwendet.

In diesem Video werden auch verschiedene Optimierungstechniken für Schachengines wie Transpositionstabellen, späte Zugreduktionen und die Verwendung von Bitboards zur Zuggenerierung besprochen. Der Referent spricht auch über das Thema "spekulative Parallelität und Leiserschach", wo er Programmierern rät, zu prüfen, ob eine Bewegung den Pfad des Lasers beeinflusst, und nach "Laserabdeckung" zu suchen. Der Referent schlägt vor, alte Darstellungen im Code zu belassen und Änderungen mit Programmen zu testen. Sie entwickelten auch eine Heuristik, um zu messen, wie nah ein Laser beim Leiserschach am König ist. Weitere Optimierungsvorschläge umfassen die Suche nach einem besseren Weg, um die Nähe des Gegners zum Laser des Spielers zu bewerten, und die Optimierung der Sortierung von Zügen. Abschließend wird die Bedeutung des ordnungsgemäßen Refactorings und Testens von Code diskutiert.

  • 00:00:00 In diesem Abschnitt stellt der Kursleiter das Konzept der spekulativen Parallelität vor, um Code zu optimieren und schneller auszuführen. Dies beinhaltet das Erraten, dass bestimmte Aufgaben parallel ausgeführt werden können, selbst wenn sie von Natur aus seriell sind, was zu einer gewissen Zeitverschwendung führen kann, wenn sich die Vermutung als falsch herausstellt. Der Kursleiter liefert ein Beispiel für die Schwellenwertbildung einer Summe und zeigt eine einfache Optimierung durch vorzeitiges Beenden, wenn die Teilsumme jemals einen Schwellenwert überschreitet, obwohl dies eine vorhersehbare Verzweigung einführt, die den Code immer noch verlangsamen könnte.

  • 00:05:00 In diesem Abschnitt erläutert der Redner, wie das Problem des Hinzufügens von zu viel in die innere Schleife beim parallelen Betrieb gemildert werden kann. Sie erklären, dass Strip Mining verwendet werden kann, um die Schleife von n Iterationen durch eine Schleife von n über vier Iterationen durch eine innere Schleife von vier Iterationen zu ersetzen und gleichzeitig zu prüfen, ob der Schwellenwert bei jeder vierten Iteration überschritten wurde, um die Kosten zu minimieren die Prüfung. Um eine kurzgeschlossene Schleife zu parallelisieren, fügt der Sprecher dem Code ein Abbruch-Flag hinzu und verwendet es rekursiv, um zu prüfen, ob die Summe größer als eine Grenze ist und nicht abgebrochen wurde, bevor er das Flag auf wahr setzt. Indem sie die Flagge überprüfen, bevor sie sie setzen, vermeiden sie einen Bestimmungswettlauf und verhindern echte Wettkämpfe.

  • 00:10:00 In diesem Abschnitt behandelt das Video die spekulative Parallelität, d. h. wenn ein Programm vorhersagt, dass es parallel arbeiten muss, und präventiv arbeitet. Dieser Code ist nicht deterministisch und sollte nur bei Bedarf zu Leistungszwecken verwendet werden. Es ist wichtig, das Abort-Flag zurückzusetzen und keine spekulative Arbeit hervorzubringen, es sei denn, es gibt wenig andere Möglichkeiten für Parallelität und eine gute Chance, dass sie benötigt wird. Das Video warnt vor der Verwendung von spekulativer Parallelität in Fällen, in denen ein besserer serieller Code verwendet werden könnte, da dieser Ansatz häufig zu mehr Arbeit ohne Beschleunigung führt. Schließlich wird auf ein Theorem verwiesen, das umreißt, dass für Parallelität die Wahrscheinlichkeit, dass die Arbeit unnötig ist, geringer sein muss als die Anzahl der verwendeten Prozessoren.

  • 00:15:00 In diesem Abschnitt dreht sich die Diskussion um parallele Alpha-Beta-Suchen, bei denen der Spielbaum beschnitten wird, um die Suchzeit zu optimieren. Burkhardt Manin und seine Studenten beobachteten, dass in einem bestgeordneten Baum der Grad jedes Knotens entweder 1 oder maximal ist. Ihre Idee war zu spekulieren, dass der beste Zug ausgewählt wurde, nachdem das erste Kind keinen Beta-Cutoff generiert hatte. Dadurch können die verbleibenden Kinder ohne Arbeitsaufwand parallel durchsucht werden. Heuristiken im Code helfen dabei, sicherzustellen, dass die Dinge in der richtigen Reihenfolge ausgeführt werden, wie z. B. die Verwendung des Gewichtsalgorithmus für junge Geschwister, um den besten Zug auszuwählen, selbst wenn es sich um eine geringere Tiefe handelt. Der Algorithmus bricht auch Unterberechnungen ab, wenn sie sich als unnötig erweisen.

  • 00:20:00 In diesem Abschnitt des Videos erläutert der Sprecher den Mechanismus des regelmäßigen Hochkletterns des Baums, um nach Vorfahren zu suchen, die bei der Parallelisierung abgebrochen wurden, und um Arbeitsverschwendung zu vermeiden. Sie schlagen vor, einen Zähler oder Voodoo-Parameter zu haben, um zu bestimmen, wie oft überprüft werden soll, da das Hochziehen des Baums mit Kosten verbunden ist. Der Referent spricht auch über die bei der Suche verwendeten Datenstrukturen wie die Transpositionstabelle, die zu Parallelisierungsrennen führen können. Sie schlagen vor, es für jeden Worker zu replizieren oder zu sperren, um Datenrennen zu vermeiden. Schließlich empfiehlt der Redner, Spekulationen und andere nicht deterministische Teile des Codes auszuschalten, um das Debuggen zu erleichtern.

  • 00:25:00 In diesem Abschnitt spricht der Sprecher über ein Programm, das 1999 beinahe die Computerschach-Weltmeisterschaft gewonnen hätte. Sie schlugen eine Regeländerung vor, der alle zustimmten, aber dann verloren sie gegen den berühmten IBM-Computer Deep Blue. Sie liefen auf einem Supercomputer mit 1824 Knoten in den Sandia National Labs, und ihr einziger Verlust war Deep Blue. Sie beschlossen, in ihrem Programm ein Rennen in der Transpositionstabelle zuzulassen, ohne Sperren für den Zugriff auf die Tabelle einzuschließen, da dies das Programm verlangsamen würde. Sie berechneten, dass die Quoten eines Rennens, die den von ihnen gewählten Wert und schließlich das Ergebnis des Turniers beeinflussten, gering waren.

  • 00:30:00 In diesem Abschnitt des Videos diskutiert der Sprecher drei Datenstrukturen, die für die Entscheidungsfindung in der Schach-KI wichtig sind. Die erste ist die „Killer“-Heuristik, die die besten Schritte bei einer bestimmten Codetiefe verfolgt und dazu neigt, sich zu wiederholen. Die zweite ist die "Best Move"-Tabelle, die alle Züge mit niedrigerer Rangfolge basierend auf statistischen Daten ordnet. Beide Datenstrukturen werden gemeinsam genutzt und müssen beim Parallelisieren des Codes ordnungsgemäß verwaltet werden. Die endgültige Datenstruktur ist das Eröffnungsbuch, das die besten Züge zu Beginn des Spiels vorberechnet. Der Sprecher weist jedoch darauf hin, dass es weniger hängende Früchte als das Eröffnungsbuch gibt und dass die meisten Spiele statistisch gesehen nicht lange genug dauern, als dass ein Eröffnungsbuch von Vorteil wäre.

  • 00:35:00 In diesem Abschnitt erörtert der Redner die Strategie zum Erstellen von Eröffnungsbüchern in Leiserchess, einem Spiel, bei dem Teams versuchen, die stärksten schachspielenden Bots zu erstellen. Der Sprecher stellt fest, dass einige Teams Erfolg hatten, indem sie ein starkes Eröffnungsbuch erstellten, das es ihnen ermöglichte, durch einen fantastischen Start zu gewinnen. Sie schlagen auch vor, dass es effektiver ist, separate Eröffnungsbücher für jede Seite zu führen, anstatt eines für beide zu verwenden. Darüber hinaus empfiehlt der Sprecher, dem Code eine leichte Zufälligkeit hinzuzufügen, um Vorhersagbarkeit zu vermeiden, warnt jedoch davor, dass es nicht notwendig ist, dies während der ersten Betaphase zu optimieren. Schließlich schlagen sie die Strategie der iterativen Vertiefung vor, bei der Suchen in verschiedenen Tiefen durchgeführt werden, bis die Zeitkontrolle abläuft. Der Sprecher merkt an, dass dies eine gute Strategie ist, da der Arbeitsaufwand mit jeder Tiefe exponentiell zunimmt, aber die wichtigen Informationen werden während der ersten paar Tiefen angesammelt.

  • 00:40:00 In diesem Abschnitt befasst sich das Video mit den Vorteilen der iterativen Vertiefung und wie sie zu einer besseren Zugreihenfolge für Suchen führt. Durch iteratives Vertiefen kann die Transpositionstabelle die besten Zugreihenfolgeinformationen für alle Zwischenpositionen speichern, wodurch das Beschneiden in einer größeren Tiefe effektiver wird. Darüber hinaus bietet es durch die iterative Vertiefung auch einen guten Mechanismus zur Zeitsteuerung. Das Video geht auch auf die Partiedatenbank ein und erklärt, warum das Erstellen einer Endspieldatenbank vorteilhaft ist, während es auch erörtert, wie man das Radfahren in einer Endspieldatenbank vermeidet, indem man die Distanz zum Matt anstelle eines einfachen booleschen Werts speichert.

  • 00:45:00 In diesem Abschnitt erörtert der Referent verschiedene Heuristiken, die im Bewertungsprozess von Suchalgorithmen verwendet werden, insbesondere zur Vermeidung von zyklischer und Ruhesuche. Der Redner erwähnt, wie wichtig es ist, den Abstand zum Sieg beizubehalten und das Radfahren zu vermeiden, indem er nach einem Abstand zum Sieg sucht, der um eins kleiner ist als der aktuelle Abstand. Eine weitere verwendete Heuristik ist das Beschneiden von Zügen, bei dem Stillsitzen normalerweise nicht so gut ist wie das Ausführen eines Zuges, und das Beschneiden von Zügen ohne Bewegung, bei dem der Nullzug angewendet wird, um die Suche zu vereinfachen, wenn eine Position so gut ist, dass sogar Nichtstun zu einem Gewinn führen würde . Der Redner erörtert auch Zoogs Wang im Schach und wie Zugerweiterungen bei der Lügensuche im Schach verwendet werden, wenn es nur einen erzwungenen Zug gibt.

  • 00:50:00 In diesem Abschnitt spricht der Sprecher über die Verwendung einer Transpositionstabelle in einem Suchalgorithmus, der eigentlich ein Dag (gerichteter azyklischer Graph) ist, da dieselbe Position durch transponierte Züge erreicht werden kann. Die Transpositionstabelle speichert Qualitätsbewertungen, die durch die Suchtiefe bestimmt werden, um den Wert einer Bewegung festzulegen, um ein erneutes Suchen derselben Position zu vermeiden. Es ist wichtig, keine Bewegungen von zu geringer Qualität zu verwenden, da dies keine vollständige Suche ermöglicht und der gespeicherte Wert möglicherweise weniger genau ist. Zusätzlich wird ein spezieller Code verwendet, um Paarungspositionen zu speichern, die berechnet werden, indem eine sehr große Zahl von der Tiefe subtrahiert wird, um zur Paarung zu gelangen. Zobrist-Hashing, eine Optimierungstechnik, die in Suchalgorithmen verwendet wird, wird ebenfalls diskutiert, wobei für jede Position auf dem Brett mit denselben Steinen ein eindeutiger Hash-Wert verwendet wird.

  • 00:55:00 In diesem Abschnitt erläutert Professor Leiserson das Konzept des Zobrist-Hashing, das verwendet wird, um eine Hash-Funktion, die die Position verschiedener Figuren auf einem Schachbrett darstellt, effizient zu aktualisieren. Die Hash-Funktion umfasst das Erzeugen einer Tabelle mit Zufallszahlen, die verschiedenen Kombinationen von Stücktyp, Reihe, Spalte und Ausrichtung entsprechen. Die Hash-Funktion verwendet XOR-Operationen, um den Hash zu berechnen, indem sie das XOR der Werte aller Teile und ihrer Ausrichtungen nimmt. Zobrist-Hashing nutzt die XOR-Eigenschaft, um Teile aus der Hash-Funktion zu entfernen, indem der Wert des entfernten Teils XOR-verknüpft wird, um den Hash für die verbleibenden Teile zu erhalten. Dies ermöglicht eine kostengünstige und effiziente Aktualisierung der Hash-Funktion mit nur zwei XOR-Operationen für jede durchgeführte Bewegung.

  • 01:00:00 In diesem Abschnitt erörtert der Referent verschiedene Optimierungstechniken für Schachengines. Er spricht über die Transpositionstabelle, die Aufzeichnungen über die Zobrist-Tonart, die Punktzahl, die Qualität und den gebundenen Typ eines Zuges speichert und ältere Züge altert. Darüber hinaus erwähnt er das Konzept der Late-Move-Reduktion, bei dem weniger vielversprechende Züge weniger gründlich gesucht werden, um Zeit zu sparen. Der Redner spricht auch über die Darstellung des Bretts und wie die Verwendung von Bitboards die Zuggenerierung und andere Schachkonzepte beschleunigen kann, indem Bittricks verwendet werden, um Operationen wie das Verschieben und Zählen von Bits effizient auszuführen.

  • 01:05:00 In dieser Sektion geht der Referent auf das Thema „Spekulativer Parallelismus und Leiserschach“ ein. Er erklärt, dass eine der wichtigsten Optimierungen im Umgang mit einem Laser darin besteht, zu bewerten, ob eine Bewegung den Weg des Lasers beeinflusst oder nicht. Außerdem schlägt der Redner vor, nach einer „Laserabdeckung“ zu suchen, da diese sehr teuer ist. Er rät Programmierern auch, die alte Darstellung im Code zu belassen und Behauptungen einzubauen, die besagen, dass die Dinge gleichwertig sind, und Programme wie Perfectiy zu verwenden, um festzustellen, ob sie Änderungen vorgenommen haben. Abschließend erläutert er, wie das Programm funktionieren soll, um den Laser in die Nähe des Königs zu bringen, und wie wichtig die Position im Spiel ist.

  • 01:10:00 In diesem Abschnitt diskutiert der Sprecher eine neue Heuristik, die sie entwickelt haben, um zu messen, wie nahe ein Laser beim Leiserschach an den König eines Gegners herankommt. Sie bewerten jeden Zug, indem sie die Entfernung des Lasers vom König berechnen, einen Wert für jede Position zählen, von der er sich entfernt, und einen zusätzlichen Wert, wenn er von einem Gegner abprallt. Sie nehmen die minimale Anzahl, die sie für jedes Feld erreichen können, und verwenden einen Multiplikator, um zu gewichten, wie gut es ist, in der Nähe des Königs zu sein. Sie addieren alles und multiplizieren es mit einem magischen konstanten Multiplikator, um den Wert als Bruchteil eines Bauern darzustellen. Die resultierende Zahl reicht im Durchschnitt bis zu etwa vier.

  • 01:15:00 In diesem Abschnitt geht der Referent auf verschiedene Möglichkeiten ein, wie die Effizienz der Schachengine verbessert werden könnte. Ein Vorschlag ist, einen besseren Weg zu finden, um die Nähe des Gegners zum Laser des Spielers zu bewerten, da die aktuelle Methode rechenintensiv ist. Ein weiterer Bereich der Optimierung ist das Sortieren der Züge, was ebenfalls teuer sein kann, insbesondere wenn viele Züge durchgesehen werden müssen. Der Referent schlägt vor, das Sortieren so zu optimieren, dass nur relevante Züge sortiert und unnötiges Sortieren vermieden wird. Der Redner erwähnt auch, dass das Ändern von Darstellungen für das Board ein schmerzhafter Prozess sein kann, aber es gibt Alternativen zur Bitboard-Darstellung, die möglicherweise effizienter sind.

  • 01:20:00 In diesem Abschnitt erläutert das Video, wie wichtig es ist, Code umzugestalten und richtig zu testen, um sicherzustellen, dass Änderungen korrekt vorgenommen werden, ohne den Code zu beschädigen. Der Redner schlägt vor, Board-Zugriffe auf einen Funktionsaufruf zu refaktorisieren, bevor er modifiziert wird, um es einfacher zu machen, die Board-Darstellung ohne umfangreiches Refactoring zu ändern. Korrektes Testen ist auch wichtig, um sicherzustellen, dass Änderungen korrekt sind und den Code nicht beschädigen, und es ist wichtig, den Code deterministisch zu gestalten, um Unvorhersehbarkeiten zu vermeiden. Der Redner erwähnt auch einen bevorstehenden Vortrag von John Bentley als wertvolle Gelegenheit, eine Berühmtheit zu treffen und mehr über das Gebiet zu erfahren.
 

Vorlesung 21. Tuning eines TSP-Algorithmus



Vorlesung 21. Tuning eines TSP-Algorithmus

Dieses YouTube-Video konzentriert sich auf das Traveling Salesperson Problem (TSP), ein NP-schweres Problem, das es seit vielen Jahren gibt. Der Sprecher geht verschiedene Algorithmen und Ansätze durch, um den Suchraum zu optimieren und die Suche zu beschneiden, um den TSP-Algorithmus schneller zu machen, wie z. B. das Implementieren eines besseren Minimum-Spanning-Tree-Algorithmus, das Aktivieren der Compiler-Optimierung und das Modifizieren der Entfernungsberechnung, um einen Tabellensuchalgorithmus zu verwenden. Die Notwendigkeit, den Suchbereich einzuschränken und kreativ zu denken, um Programme hinsichtlich Geschwindigkeit und Leistung zu optimieren, wird im gesamten Video betont, das wertvolle Einblicke in die Lösung von TSP- und anderen verwandten Problemen bietet.

In diesem Video diskutiert der Referent verschiedene Techniken zur Optimierung des TSP-Algorithmus, wie z. B. Caching, verzögerte Auswertung und das Speichern von Daten in einer Hash-Tabelle, und betont die Bedeutung empirischer Daten gegenüber der Intuition. Er teilt auch seine Erfahrungen mit der Lösung des TSP-Problems und die Bedeutung von Performance Engineering in seinem Beruf. Der Referent gibt Einblicke in den Codeoptimierungsprozess, einschließlich inkrementeller Entwicklung und rekursiver Generierung, und ermutigt das Publikum, diese Techniken zu verwenden, da sie einfach zu implementieren sind. Abschließend drückt der Redner seine Dankbarkeit für das Betreiben von Performance Engineering und die Entwicklung von Algorithmen aus, die verschiedene Google-Dienste verbessern, sowie für die Freundschaften, die er im Laufe seiner Karriere geschlossen hat.

  • 00:00:00 In diesem Abschnitt stellt John Bentley das Traveling Salesperson Problem (TSP) vor, ein NP-schweres Problem, das es seit vielen Jahren gibt. Er beschreibt seine Erfahrungen mit dem Problem und wie er vor über 40 Jahren davon abhängig wurde. Anschließend diskutiert er eine rekursive Lösung zum Aufzählen aller Teilmengen einer Menge und erklärt den Vorgang des Zählens der ganzen Zahlen in einer Menge. Er stellt fest, dass diese Methode nicht gut verallgemeinert werden kann, aber Prinzipien liefert, die dabei helfen, immer schnellere Algorithmen für TSP zu entwickeln.

  • 00:05:00 In diesem Abschnitt erklärt der Referent, wie alle Mengen der Größe M rekursiv generiert werden. Der Ansatz besteht darin, mit einem Satz der Größe n-1 zu beginnen und alle Sätze der Größe M aufzuzählen, wobei am Ende eine Null hinzugefügt wird. Die Anzahl der Sätze mit einer Null am Ende wird berechnet, indem 2 hoch M minus eins genommen wird. Die rekursive Skizze wird mit einem Beispiel veranschaulicht, bei dem jede Teilmenge von Null rückwärts gezählt und am Ende mit einer Eins ergänzt wird. Der Code für diesen Algorithmus ist einfach und kann in den meisten Programmiersprachen implementiert werden. Der Redner ermutigt das Publikum, Fragen zu stellen und sich zu äußern, und sagt, dass ihre Kreativität möglicherweise durch das Bildungssystem aus ihnen herausgeschlagen wurde. Der Rest des Videos befasst sich mit dem Problem des Handlungsreisenden und der Entwicklung eines effizienten Algorithmus dafür.

  • 00:10:00 In diesem Abschnitt spricht der Referent über das Traveling Salesman Problem (TSP) und seine Bedeutung als prototypisches Problem in der Informatik, das eines der ersten Probleme war, das sich als NP-schwer erwiesen hat. Der Referent erzählt eine persönliche Anekdote darüber, wie sein Interesse an dem Problem geweckt wurde, als sein Kollege ihre Probleme mit der Lösung eines 16-Punkte-TSP in ihrer Doktorarbeit besprach. Der Redner erörtert dann, wie er 20 Jahre später ein Programm zur Lösung desselben Problems schrieb, das zu einem beliebten Thema in einem Algorithmuskurs an der Lehigh University wurde, was zu weiteren Untersuchungen darüber führte, wie sich Performance Engineering in 40 Jahren verändert hat.

  • 00:15:00 In diesem Abschnitt erläutert der Referent einen rekursiven Algorithmus in einem einfachen C-Programm zur Generierung aller faktoriellen Permutationen von n Städten, um die beste Tour zu finden. Der Verzweigungsfaktor des Baums beträgt an jedem Knoten 9, was zu einem großen Baum für n = 10 mit 10 Fakultäten möglicher Kombinationen führt. Das Programm prüft für jede Permutation die Summe der Entfernungen zwischen den Städten und speichert die bisher gefundene Mindestsumme. Das Programm arbeitet korrekt, aber seine Geschwindigkeit für n=10 ist unklar.

  • 00:20:00 In diesem Abschnitt erörtert der Sprecher die Zeit, die zum Ausführen von Permutationen benötigt wird, und schlägt verschiedene Möglichkeiten vor, das Programm schneller zu machen. Er erklärt, wie schnell es dauert, vier Permutationen auf einem schnellen Laptop auszuführen, und wie die Zeit dramatisch ansteigt, wenn die Permutationen größer werden. Er erwägt auch Möglichkeiten, das Programm zu beschleunigen, wie z. B. die Auswahl eines Starts und das Ignorieren aller anderen oder die Verwendung von Parallelisierung. Außerdem erwähnt er die Möglichkeit, das Programm mit Compilern zu optimieren, insbesondere mit GCC und -o3. Abschließend erläutert er die Vorteile von schnelleren Maschinen und schnellerer CPU-Zeit.

  • 00:25:00 In diesem Abschnitt geht der Referent darauf ein, wie viel schneller der TSP-Algorithmus durch verschiedene Optimierungen werden kann. Beispielsweise kann das einfache Aktivieren von Compiler-Optimierungen zu einer Leistungssteigerung von bis zu Faktor 25 führen. Da sich die Hardware im Laufe der Jahre verbessert hat, kann die Kernel-Optimierung außerdem zu einer schnelleren Taktrate, breiteren Datenpfaden und tieferen Pipelines führen eine Beschleunigung um den Faktor 150. Darüber hinaus kann die Modifizierung der Entfernungsberechnung zur Verwendung eines Tabellensuchalgorithmus zu einem Beschleunigungsfaktor von 2,5 bis 3 führen. Insgesamt, auch wenn die alte Intuition über die Leistung möglicherweise nicht mehr zutrifft, seien Sie vorsichtig Die Modellierung kann die Auswirkungen verschiedener Optimierungen auf den TSP-Algorithmus bestimmen.

  • 00:30:00 In diesem Abschnitt erläutert der Referent verschiedene Möglichkeiten zur Optimierung eines induktiven Algorithmus zur mehrfachen Berechnung derselben Summe, um zu vermeiden, dass dieselben Teile wiederholt berechnet werden. Der Referent zeigt auch die Laufzeiten für die vier Algorithmen und erklärt, wie man schneller vorgehen kann, wie z. B. die Verwendung einer besseren Maschine und die Nutzung jedes Faktors von en, um das Problem in der gleichen Zeit um eins zu vergrößern. Sie erklären auch, wie man ein Problem des Handlungsreisenden löst, und zeigen, dass die optimale Tour auf verschiedenen Seiten des Problems anders aussieht. Der Redner schließt mit der Aufforderung, das Problem trotz seiner langen Laufzeit zu lösen.

  • 00:35:00 In diesem Abschnitt erörtert der Sprecher die Größenordnung von 52 Fakultäten und erklärt, warum sie schneller ist als jede Exponentialfunktion. Er erklärt, dass es ungefähr 2 hoch 225 oder 10 hoch 67 ist, was eine riesige Zahl ist. Um es alltagssprachlich auszudrücken, nennt er das Beispiel, wie man 52 faktorielle Nanosekunden herunterzählt und alle eine Million Jahre einen Schritt vorwärts macht, um schließlich den Äquator zu umrunden und einen Wassertropfen aus dem Pazifischen Ozean zu nehmen. Er betont dann die Notwendigkeit, den Suchraum einzuschränken und die Suche zu beschneiden, um diese Probleme effizient zu lösen.

  • 00:40:00 In diesem Abschnitt stellt der Sprecher ein Problem vor, das ihm seine Tochter zur Lösung gegeben hat. Das Problem besteht darin, alle Permutationen der 9 ganzen Zahlen 1 bis 9 so zu finden, dass jeder anfängliche Teilstring der Länge m durch M teilbar ist, sodass das Ganze durch 9 teilbar ist. Der Sprecher schlägt vor, dass Sie nachdenken, bevor Sie ein Programm schreiben, um das Problem zu lösen . Anschließend bespricht er ein Programm in der Programmiersprache AWK, das Strings und rekursive Prozeduren verwendet, um alle möglichen Permutationen zu generieren. Das Ausführen dieses Programms würde ungefähr 49 dauern! zeitliche Komplexität.

  • 00:45:00 In diesem Abschnitt erläutert der Referent, wie der Suchraum optimiert werden kann, wenn mit einem Programm nach einer bestimmten Zeichenfolge gesucht wird. Er demonstriert dies anhand eines Beispiels, bei dem eine Zeichenfolge mit bestimmten Eigenschaften gefunden wird, z. B. durch bestimmte Zahlen teilbar ist und bestimmte Zahlen an bestimmten Positionen enthält. Durch die Definition der Eigenschaften, die in der Gewinnzeichenfolge vorhanden sein müssen, kann der Suchraum erheblich von einer Drittelmillion auf ein halbes Tausend Auswahlmöglichkeiten reduziert werden. Dies unterstreicht, wie wichtig es ist, die Suche zu beschneiden, um den Prozess zu beschleunigen. Der Referent betont die Notwendigkeit, darüber nachzudenken, wie Programme auf Geschwindigkeit und Leistung optimiert werden können.

  • 00:50:00 In diesem Abschnitt erörtert der Redner Möglichkeiten, die Suche zu beschneiden, um den TSP-Algorithmus schneller zu machen. Eine Möglichkeit, die Suche zu beschneiden, besteht darin, nicht weiter zu tun, was nicht funktioniert, dh wenn sich herausstellt, dass die Summe größer als die Mindestsumme ist, indem mehr hinzugefügt wird, dann die Suche stoppen. Diese Methode kann den Algorithmus auf derselben Maschine schneller machen, indem sie weniger Zeit in Anspruch nimmt. Der Referent stellt jedoch auch andere Ideen vor, um die Suche zu beschneiden und eine untere Schranke zu erhalten, wie die Berechnung eines TSP-Pfads oder eines minimalen Spannbaums, die leistungsfähiger, aber auch teurer sind.

  • 00:55:00 In diesem Abschnitt erörtert der Sprecher, wie die Untergrenze für TSP verbessert werden kann, indem ein besserer minimaler Spanning-Tree-Algorithmus implementiert wird, da hier die meiste Rechenzeit aufgewendet wird. Er verwendet Parallelität mit einer Bitmaskendarstellung der Teilmenge von Städten, um die MST schnell und effizient zu berechnen. Obwohl die Berechnung des MST n Quadratzeit dauert, ist diese Methode ein leistungsfähiger Bereinigungsmechanismus, der zu einer höheren Programmgeschwindigkeit führt. Nach mehreren Versuchen und der Bewältigung von Herausforderungen dauert das Programm von 17 Sekunden auf 0 Sekunden, sodass größere Datensätze problemlos verarbeitet werden können.

  • 01:00:00 In diesem Abschnitt beschreibt der Referent sein Experiment zur Optimierung des TSP-Algorithmus durch Implementieren von Lazy Evaluation, Speichern von Daten in einer Hash-Tabelle und Verwenden einer besseren Starttour mit einer intelligenteren Suche. Er erörtert die Vorteile des Cachings und wie die Leistung des Algorithmus durch Experimentieren und Testen verschiedener Ansätze optimiert werden kann. Der Referent betont, dass sich Performance Engineering auf empirische Daten stützen sollte und dass die Intuition oft falsch liegt. Er erwähnt auch die Besteigung des Mount Monadnock und den Unterschied zwischen vorhersehbaren und unvorhersehbaren Algorithmen.

  • 01:05:00 In diesem Abschnitt des Videos erklärt der Sprecher, wie die Suche des TSP-Algorithmus intelligenter gestaltet werden kann, indem er schneller zur anfänglichen Startstadt geführt wird, anstatt nur eine zufällige Tour zu verwenden. Durch die Verwendung einer einfachen Einfügungssortierung und den Besuch der nächstgelegenen 30 Städte kann der Suchraum beschnitten werden, was einen großen Unterschied macht. Der Sprecher teilt mit, dass sie 1997 froh waren, 230 herauszuholen, aber in 20 weiteren Jahren, wenn sie allein das Mooresche Gesetz verwenden, könnten sie einen Faktor von 1.000 erhalten. Durch die Kombination von Moores Gesetz und Compiler-Technologie mit allen Algorithmen konnten sie jedoch bis zu 52 erreichen. Der Sprecher betont, dass alles, was sie teilten, mit 160 Codezeilen erreicht werden könnte, und all diese Dinge sind durchaus im Rahmen der Praxis von jemandem, der diesen Kurs abgeschlossen hat.

  • 01:10:00 In diesem Abschnitt erörtert der Referent mehrere Techniken zur Codeoptimierung, wie z. B. Caching, Vorausberechnung und Speichern von Ergebnissen, um unnötige Arbeit zu vermeiden. Er betont auch die Bedeutung der inkrementellen Softwareentwicklung und die Leistungsfähigkeit der rekursiven Generierung. Der Redner erwähnt, dass einige der Techniken, die er bespricht, in einem alten Buch behandelt werden, das er über Code-Tuning geschrieben hat, aber einige der Ideen gelten noch heute. Er erwähnt auch, dass er viele Tools hinter den Kulissen verwendet hat, wie z. B. Profiler und Kostenmodelle, um Experimente durchzuführen und Kosten zu schätzen. Schließlich ermutigt er das Publikum, diese Techniken zu erforschen und anzuwenden, da sie in der Praxis einfach umzusetzen sind.

  • 01:15:00 In diesem Abschnitt diskutiert der Referent verschiedene Themen, die von Alpha-Beta-Pruning bis zum Problem der Hashing-Kollisionen reichen. Der Referent teilt mit seinem Kollegen auch seine Erfahrungen bei der Lösung des Traveling-Salesman-Problems Anfang der 1990er Jahre. Sie konnten das Problem von 48 Landeshauptstädten lösen und waren begeistert. Der Redner betont auch die Bedeutung von Performance Engineering in seinem Beruf und erwähnt seine Beteiligung an verschiedenen Computersystemen, darunter automatisiertes Gerrymandering und Telefonanrufcodierung. Insgesamt bietet der Abschnitt Einblicke in die umfangreiche Erfahrung des Referenten in der Computerprogrammierung und seine Perspektiven auf verschiedene Techniken und Probleme.

  • 01:20:00 In diesem Abschnitt drückt der Redner seine Dankbarkeit dafür aus, Performance Engineering als Lebensweise zu verfolgen. Er erwähnt, dass es ihm ermöglicht hat, Algorithmen zu entwickeln, die verschiedene Google-Dienste verbessern, was für ihn immens befriedigend und erfüllend war. Der Redner drückt auch seine Dankbarkeit für die Freundschaften aus, die er im Laufe seiner Karriere geschlossen hat, und hofft, dass Performance Engineering für andere genauso gut sein kann wie für ihn.
1...232425262728293031323334353637...74
Neuer Kommentar