Maschinelles Lernen und neuronale Netze - Seite 29

[MetaQuotes]

Vorlesung 2. Bentley-Regeln zur Arbeitsoptimierung

2. Bentley-Regeln zur Arbeitsoptimierung

Dieses YouTube-Video behandelt verschiedene Optimierungstechniken für Computerprogramme. Die Bentley-Regeln zur Optimierung der Arbeit werden eingeführt und die Optimierungen in Datenstrukturen, Schleifen, Logik und Funktionen gruppiert. Verschiedene Techniken wie Kodierung von Werten, Datenstrukturerweiterung, Vorberechnung, Caching und Verwendung von Matrizen mit geringer Dichte werden diskutiert. Der Referent geht auch auf die Vorteile der Verwendung einer spärlichen Matrixdarstellung für Graphen, Logikoptimierung und Kollisionserkennungsoptimierung in Grafikprogrammen ein. Die Implementierung dieser Optimierungstechniken trägt dazu bei, die Laufzeit von Programmen zu reduzieren und sie effizienter zu machen.

Der zweite Teil des Videos behandelt mehrere Kategorien von Optimierungstechniken, darunter das Heben von Schleifen, die Verwendung von Sentinels in Schleifen, das Abrollen und Verschmelzen von Schleifen sowie das Inlining von Funktionen. Der Referent rät von voreiliger Optimierung ab und betont die Wichtigkeit der Einhaltung der Korrektheit und der Anwendung von Regressionstests. Das Video umreißt auch die Bentley-Regeln zur Arbeitsoptimierung, eine Anleitung in sechs Schritten zur Steigerung der Produktivität und zum effizienten Erreichen von Zielen. Zu diesen Regeln gehören das Setzen klarer Ziele, das Aufteilen von Aufgaben, das Planen und Organisieren, das Priorisieren von Aufgaben, das Minimieren von Ablenkungen und das regelmäßige Überprüfen und Anpassen des eigenen Vorgehens.

• 00:00:00 In diesem Abschnitt stellt der Dozent das Konzept der Optimierung der Arbeit in Computerprogrammen vor und erklärt, wie die Reduzierung der Arbeit eines Programms seine Leistung verbessern kann. Er spricht auch über die Bentley-Regeln zur Optimierung der Arbeit, benannt nach John Lewis Bentley, der ein Buch über das Schreiben effizienter Programme geschrieben hat. Die Optimierungen sind in vier Kategorien eingeteilt: Datenstrukturen, Schleifen, Logik und Funktionen, und der Dozent plant, alle 22 Regeln in einer Reihe von Minivorträgen während des gesamten Kurses abzudecken. Während die Reduzierung der Arbeit eines Programms eine gute Heuristik zur Verbesserung seiner Laufzeit ist, bedeutet die komplexe Natur von Computerhardware, dass dies nicht immer zu einer Reduzierung der Laufzeit führt, sodass der Dozent später in der Vorlesung auch architekturspezifische Optimierungen behandeln wird Kurs.
  
  
• 00:05:00 In diesem Abschnitt des Videos erläutert der Sprecher das Konzept des Packens und Codierens von Datenstrukturen, um mehr als einen Datenwert in einem Maschinenwort zu speichern und Datenwerte in eine Darstellung umzuwandeln, die weniger Bits erfordert. Indem die Anzahl der Dinge reduziert wird, die im Speicher verschoben werden müssen, wird es zu einer guten Heuristik, um die Laufzeit eines Programms zu verkürzen. Der Sprecher bietet ein Beispiel für die Codierung von Daten, um sie mit weniger Bits zu speichern, um das Abrufen des Monats, Jahres oder Tages für ein bestimmtes Datum zu erleichtern. Der Redner schlägt vor, Bitfelder in C zu verwenden, um die strukturierten Daten zu speichern und sie leichter zugänglich zu machen. Diese Darstellung erfordert etwas mehr Bits, ist aber viel effizienter beim Zugriff auf bestimmte Datenwerte innerhalb der Struktur.
  
  
• 00:10:00 In diesem Abschnitt behandelt das Video drei Optimierungstechniken. Die erste Technik besteht darin, zu entscheiden, ob Werte als aufeinanderfolgende Ganzzahlen codiert oder für einen schnelleren Zugriff entpackt werden sollen. Die zweite Technik ist die Datenstrukturerweiterung, bei der das Hinzufügen von Informationen zu einer Datenstruktur allgemeine Operationen optimieren kann. Ein Beispiel ist das Hinzufügen eines Endzeigers zu einer einfach verknüpften Liste, um das Anhängen von zwei Listen effizienter zu gestalten. Die dritte Technik ist die Vorberechnung, die darin besteht, Berechnungen im Voraus durchzuführen, um zu vermeiden, dass die Berechnungen zu missionskritischen Zeiten durchgeführt werden. Ein Beispiel ist die Verwendung des Pascal-Dreiecks zur Vorberechnung von Binomialkoeffizienten, um das Programm zu beschleunigen, das sie verwendet.
  
  
• 00:15:00 In diesem Abschnitt erläutert der Referent, wie man das Pascalsche Dreieck mit einer rekursiven Formel und C-Code vorberechnen kann. Sie erklären, dass die rekursive Formel den Aufruf der Funktion choose beinhaltet und wie die Tabelle zur Laufzeit mit einer Schleife vorberechnet wird. Außerdem erläutern sie, wie die Tabelle zur Kompilierzeit initialisiert wird, indem die Tabellenwerte in den Quellcode eingefügt werden, was Zeit bei der Programmausführung spart. Schließlich stellen sie eine Beispieltabelle mit Binomialkoeffizienten bis 10 bereit, auf die während der Programmausführung zugegriffen werden kann.
  
  
• 00:20:00 In diesem Abschnitt stellt der Sprecher das Konzept der Metaprogrammierung vor, um zu vermeiden, dass große Tabellen mit konstanten Werten manuell in ein Programm eingegeben werden müssen. Durch das Schreiben eines Programms, das den erforderlichen Code generiert, kann die mühsame Aufgabe automatisch erledigt werden. Der Referent stellt als Beispiel ein Python-Code-Snippet zur Verfügung. Das Thema Caching wird ebenfalls eingeführt, als eine Technik, um die Wiederholung kostspieliger Berechnungen zu vermeiden, indem Ergebnisse, auf die kürzlich zugegriffen wurde, in einem Cache gespeichert werden. Das gegebene Beispiel ist die Berechnung der Hypotenuse eines rechtwinkligen Dreiecks unter Verwendung des Quadratwurzeloperators, wobei der Cache vorherige Hypotenusen zusammen mit den Werten von a und b vorspeichert. Die Hypotenuse-Funktion prüft zuerst, ob die Eingabewerte mit denen im Cache übereinstimmen, und gibt in diesem Fall den zwischengespeicherten Wert zurück, ohne die Quadratwurzel neu berechnen zu müssen.
  
  
• 00:25:00 In diesem Abschnitt erörtert der Referent das Konzept des Cachings zur Optimierung der Arbeit in einem Programm. Durch das Speichern häufig berechneter Werte in einem Cache können Programme Zeit sparen, da dieselben Werte nicht wiederholt berechnet werden müssen. Während die Hardware auch Caching durchführt, kann dies auch die Software tun, wobei ein Cache der Größe 1.000 die 1.000 zuletzt berechneten Werte speichert, um ein Beispiel zu sein. Die Optimierung kann ein Programm um etwa 30 % beschleunigen, wenn dieselben Werte wiederholt berechnet werden. Der Sprecher führt dann die Idee ein, Sparsity in einer Eingabe auszunutzen, um eine Berechnung auf null Elementen dieser Eingabe zu vermeiden, wodurch Rechenzeit eingespart wird. Sie demonstrieren dies anhand eines Beispiels der Matrix-Vektor-Multiplikation und stellen die Datenstruktur Compressed Sparse Row (CSR) vor, die die Multiplikation von Matrizen beschleunigen kann.
  
  
• 00:30:00 In diesem Abschnitt erläutert der Referent, wie die Speicher- und Recheneffizienz von Matrizen mit geringer Dichte mithilfe des Formats Compressed Sparse Row (CSR) optimiert werden kann. Das CSR-Format speichert die Nicht-Null-Elemente einer Matrix in drei Arrays: dem Werte-Array, dem Spalten-Array und dem Zeilen-Array. Der Referent erklärt, wie man die Länge einer Zeile berechnet und wie man eine Matrix-Vektor-Multiplikation mit dem CSR-Format durchführt. Das CSR-Format kann platzsparender sein als die dichte Matrixdarstellung, wenn die Anzahl der Nicht-Null-Elemente deutlich kleiner als N^2 ist. Bei relativ dichten Matrizen kann die dichte Matrixdarstellung jedoch weniger Platz beanspruchen. Der Sprecher liefert ein Codebeispiel zum Durchführen einer Matrix-Vektor-Multiplikation unter Verwendung des CSR-Formats.
  
  
• 00:35:00 In diesem Abschnitt erörtert der Kursleiter die Vorteile der Verwendung einer dünnbesetzten Matrix zur Darstellung eines Diagramms und wie sie verwendet werden kann, um klassische Diagrammalgorithmen wie Breitensuche und PageRank effizienter auszuführen. Die spärliche Graphendarstellung besteht aus zwei Arrays: Offsets und Kanten, wobei die Grade jedes Scheitelpunkts erhalten werden können, indem die Differenz zwischen aufeinanderfolgenden Offsets genommen wird. Das Gewicht der Kanten kann auch entweder in einem separaten Array gespeichert oder mit den Kanten verschachtelt werden, um die Cache-Lokalität zu verbessern. Der Abschnitt endet mit einer kurzen Einführung in Logikoptimierungen, insbesondere Constant Folding und Propagation, die konstante Ausdrücke während der Kompilierung auswerten, um die Laufzeit zu reduzieren.
  
  
• 00:40:00 In diesem Abschnitt des Videos erörtert der Sprecher verschiedene Optimierungstechniken für Code, einschließlich konstanter Faltung und Ausbreitung, Eliminierung gemeinsamer Unterausdrücke und Nutzung algebraischer Identitäten. Durch die Definition von Konstanten zur Kompilierzeit kann der Compiler diese auswerten und zur Laufzeit Zeit sparen. Durch die Eliminierung gemeinsamer Unterausdrücke kann vermieden werden, dass derselbe Ausdruck mehrmals berechnet wird, indem das Ergebnis für die zukünftige Verwendung gespeichert wird. Die Nutzung algebraischer Identitäten beinhaltet das Ersetzen teurerer Ausdrücke durch billigere Alternativen. Der Referent betont, dass der Compiler zwar normalerweise gut darin ist, diese Optimierungen zu implementieren, es aber dennoch wichtig ist, sie für Situationen zu kennen, in denen der Compiler dies nicht automatisch tut.
  
  
• 00:45:00 In diesem Abschnitt des Videos erläutert der Sprecher zwei Optimierungstechniken. Die erste besteht darin, die Verwendung des Quadratwurzeloperators zu reduzieren, der rechenintensiv ist, indem algebraische Identitäten verwendet werden, um Quadratwurzeln zu vermeiden. Die zweite Optimierungstechnik ist das Kurzschließen, bei dem eine Reihe von Tests abgebrochen werden, sobald das Ergebnis bekannt ist, falls ein Array nicht negative ganze Zahlen enthält und die Summe der Werte im Array mit a verglichen werden muss Grenze. Die Optimierung kann die Notwendigkeit eliminieren, alle Elemente im Array zu betrachten, und kann die Programmausführung beschleunigen, sollte jedoch basierend auf der Häufigkeit, mit der der Test kurzgeschlossen werden kann, mit Bedacht verwendet werden.
  
  
• 00:50:00 In diesem Abschnitt behandelt das Video das Konzept des Kurzschließens logischer Operatoren und ihre Nützlichkeit bei der Optimierung von Code. Das doppelte kaufmännische Und und der doppelte senkrechte Strich sind kurzschließende logische Operatoren, die Zeit und Ressourcen sparen können, indem sie nur eine Seite des Arguments auswerten. Darüber hinaus schlägt das Video vor, Tests basierend auf ihrer Erfolgshäufigkeit und den Ausführungskosten zu bestellen. Dieser Ansatz kann das Kurzschließen nutzen, um teure Tests zu überspringen, wenn kostengünstigere bereits fehlschlagen. Abschließend stellt das Video die Idee vor, einen schnellen Pfad zu erstellen, indem Prüfungen verwendet werden, um ein Programm vorzeitig zu beenden, wenn ein Ergebnis bereits bekannt ist. Ein Beispiel dafür ist das Prüfen, ob sich die Begrenzungsboxen zweier Kugeln schneiden, bevor andere Kollisionsbedingungen geprüft werden.
  
  
• 00:55:00 In diesem Abschnitt erörtert Bentley Möglichkeiten zur Optimierung von Tests zur Kollisionserkennung in Grafikprogrammen. Er schlägt einen schnellen Pfadtest vor, um festzustellen, ob sich Begrenzungsrahmen schneiden, bevor der teurere Kollisionstest durchgeführt wird. Bei diesem Test wird der Absolutwert der Differenz an jeder Koordinate überprüft und überprüft, ob er größer als die Summe der beiden Radien ist. Bentley weist auch darauf hin, dass das Kombinieren von Tests durch eine einzelne Switch-Anweisung oder sogar Tabellensuchen die Leistung erheblich verbessern kann. Insgesamt können diese Optimierungen für viele Anwendungen und Grafikprogramme von Vorteil sein.
  
  
• 01:00:00 In diesem Abschnitt behandelt das Video die dritte Kategorie von Optimierungen, die sich auf Schleifen bezieht. Die erste besprochene Schleifenoptimierung ist das Heben, bei dem vermieden wird, dass der schleifeninvariante Code jedes Mal durch den Körper einer Schleife neu berechnet wird. Indem ein Ausdruck einmal berechnet und in einer Variablen gespeichert wird, anstatt ihn bei jeder Iteration neu zu berechnen, kann er Laufzeit sparen. Die Optimierung der zweiten Schleife ist die Verwendung von Wächtern, speziellen Dummy-Werten, die in Datenstrukturen platziert werden, um die Handhabung von Randbedingungen und die Logik der Handhabung von Schleifenaustrittstests zu vereinfachen. Indem das Programm so modifiziert wird, dass es zwei zusätzliche Einträge im Array verwendet, kann ein Sentinel verwendet werden, um nur eine Prüfung in jeder Iteration der Schleife durchführen zu müssen.
  
  
• 01:05:00 In diesem Abschnitt erläutert der Referent zwei Techniken zur Optimierung von Code: Randbedingungen und Loop-Unrolling. Für Randbedingungen zeigt er, wie eine Schleife modifiziert werden kann, um den Sonderfall effizient zu handhaben, wenn alle Elemente des Eingabearrays Null sind. Durch Hinzufügen eines Dummy-Elements am Ende des Arrays und Prüfen auf einen Überlauf kann der Code erkennen, wann er aufhören sollte. Für das Abrollen von Schleifen erklärt er zwei Arten: vollständig und teilweise. Während das Abwickeln einer vollständigen Schleife aufgrund größerer Schleifengrößen selten ist, reduziert das Abwickeln einer teilweisen Schleife die Anzahl der Iterationen einer Schleife, indem mehrere zu einer kombiniert werden, was die Leistung verbessern kann, indem die Anzahl der ausgeführten Steuerflussbefehle verringert wird.
  
  
• 01:10:00 In diesem Abschnitt erörtert der Kursleiter Schleifenentrollung und Schleifenfusionsoptimierungen. Das Abrollen von Schleifen beinhaltet das Kombinieren mehrerer Iterationen einer Schleife zu einer einzigen Iteration, wodurch der Overhead der Schleifensteuerung reduziert und mehr Compiler-Optimierungen ermöglicht werden. Ein zu starkes Entrollen kann sich jedoch negativ auf die Leistung auswirken, indem der Anweisungs-Cache verschmutzt wird. Die Schleifenfusion hingegen kombiniert mehrere Schleifen über denselben Indexbereich zu einer einzigen Schleife, wodurch der Overhead der Schleifensteuerung reduziert und die Cache-Lokalität verbessert wird. Der Kursleiter bespricht auch das Eliminieren verschwendeter Iterationen durch Modifizieren von Schleifengrenzen, um das Ausführen von Schleifeniterationen über leere Schleifenkörper zu vermeiden.
  
  
• 01:15:00 In diesem Abschnitt erörtert Bentley Funktionsoptimierungen, insbesondere das Konzept des Inlinings, um den Overhead eines Funktionsaufrufs zu vermeiden. Indem eine Funktion als statisch inline deklariert wird, versucht der Compiler, einen Aufruf der Funktion durch den Hauptteil der Funktion selbst zu ersetzen, wodurch die Notwendigkeit eines separaten Funktionsaufrufs entfällt. Während Makros dies auch tun könnten, sind Inline-Funktionen strukturierter und werten alle ihre Argumente aus, wodurch das Risiko vermieden wird, dass ein Makro einen teuren Ausdruck mehrmals in den Code einfügt. Bentley rät von vorzeitiger Optimierung ab und ermutigt Entwickler, zunächst sicherzustellen, dass ihr Programm korrekt ist, und Regressionstests durchzuführen, um die Korrektheit aufrechtzuerhalten. Abschließend weist er darauf hin, dass viele Optimierungsebenen vom Compiler automatisiert werden können und eine Überprüfung des Assemblercodes solche Optimierungen aufdecken kann.
  
  
• 01:20:00 In diesem Abschnitt werden die Bentley-Regeln zur Arbeitsoptimierung in sechs Schritten beschrieben. Diese Regeln bestehen darin, klare Ziele zu setzen, Aufgaben in kleinere Teile zu unterteilen, sich Zeit für die Planung und Organisation zu nehmen, Aufgaben zu priorisieren, Ablenkungen zu minimieren und Ihren Ansatz regelmäßig zu überprüfen und anzupassen. Indem Sie diese Richtlinien befolgen, können Sie Ihre Produktivität steigern und Ihre Ziele effizienter erreichen. Darüber hinaus kann Ihnen die Einbeziehung dieser Strategien in Ihre tägliche Routine dabei helfen, eine starke Arbeitsmoral aufrechtzuerhalten und sich auf Ihre Ziele zu konzentrieren.

[MetaQuotes]

Vorlesung 3. Bit-Hacks

3. Bit-Hacks

Dieses YouTube-Video behandelt eine Vielzahl von Themen zur Bit-Manipulation, einschließlich Binärdarstellung, Zweierkomplement, bitweise Operatoren, Austauschen von Variablen ohne temporäre Variable und Code-Optimierung. Das Video demonstriert verschiedene Bit-Tricks, wie z. B. das Finden des Minimums von zwei Ganzzahlen ohne if-else-Anweisungen und wie man zwei Ganzzahlen vertauscht, ohne eine temporäre Variable zu verwenden. Der Redner diskutiert unvorhersehbare Verzweigungen und stellt einen No-Branch-Minimum-Bit-Trick vor, wenn vorhersehbare Verzweigungen nicht verfügbar sind, und zeigt, wie Bit-Hacks Code optimieren können, indem kostspielige Operationen wie Division durch einfache bitweise Operationen ersetzt werden. Das Video diskutiert auch die de Bruijn-Folge und ihre Anwendung bei der Lösung von Problemen wie dem N-Queens-Problem.

Der zweite Teil behandelt die Lösung des N-Queens-Problems unter Verwendung von Bitvektoren und das effiziente Zählen der Anzahl von 1-Bits in einem Binärwort. Backtracking wird verwendet, um das N-Damen-Problem zu implementieren, und Bitvektoren werden verwendet, um die Platine effizient darzustellen. Es werden drei Überprüfungen beschrieben, um eine Dame im N-Damen-Problem sicher zu platzieren, und es wird ein Verfahren zum Zählen der Anzahl von 1-Bits in einem Wort durch rekursives Eliminieren des niedrigstwertigen 1-Bits vorgestellt. Zusätzlich wird die Verwendung von Tabellennachschlagen und Registermanipulation zum Zählen der Anzahl von 1-Bits diskutiert. Das Video endet mit einer Demonstration eines Teile-und-Herrsche-Ansatzes zum Zählen von 1-Bits, dessen Leistung proportional zur logarithmischen Basis zwei der Wortlänge ist. Es werden auch Ressourcen für weiterführendes Lernen bereitgestellt.

• 00:00:00 In diesem Abschnitt lernen wir etwas über die binäre Darstellung von Wörtern und wie man daraus ganzzahlige Werte berechnet. Wir lernen auch die Darstellung des Zweierkomplements für vorzeichenbehaftete ganze Zahlen und die Sonderfälle des Worts aus Nullen und Einsen kennen. Darüber hinaus sehen wir eine wichtige Identität für das Einerkomplement von X und seine Beziehung zum Negativen von X in der Zweierkomplementdarstellung.
  
  
• 00:05:00 In diesem Abschnitt erklärt der Moderator das Einerkomplement und wie man das Negative einer Zahl erhält, indem man 1 zum Einerkomplement addiert. Er geht auch auf die Verwendung von Hex-Zahlen zur Darstellung großer binärer Konstanten ein und gibt eine Tabelle für die Konvertierung zwischen Hex und Binär. Das Video geht dann auf die bitweisen Operatoren in C++ ein und zeigt Beispiele, wie man sie für logisches und, logisches oder, exklusives oder und linke und rechte Verschiebungsoperationen verwendet.
  
  
• 00:10:00 In diesem Abschnitt behandelt das Video verschiedene gängige Redewendungen, die mit bitweisen Operatoren in C implementiert werden können. Ein Beispiel ist das Setzen oder Löschen des Groß-/Kleinschreibungsbits in einem Wort X durch Verwendung einer Verschiebung, gefolgt von einem ODER oder NICHT und einem UND bzw. Ein weiteres Beispiel ist das Extrahieren eines Bitfelds aus einem Wort X, indem eine Maske mit Einsen an den Positionen der gewünschten Bits und Nullen an anderer Stelle erzeugt wird, dann die Maske mit X UND-verknüpft wird und die extrahierten Bits nach rechts verschoben werden. Das Video erwähnt auch, dass die Verwendung dieser Tricks besonders nützlich sein kann, wenn Sie mit komprimierten oder codierten Daten arbeiten.
  
  
• 00:15:00 In diesem Abschnitt erläutert das Video, wie man zwei Ganzzahlen vertauscht, ohne eine temporäre Variable zu verwenden, indem man einige Bit-Tricks anwendet. Der Code beinhaltet das Setzen von X gleich X XOR Y, dann Y gleich X XOR Y und schließlich X gleich X XOR Y. Dies funktioniert, weil XOR seine eigene Umkehrung ist und die erste Zeile eine Maske mit Einsen generiert, bei denen die Bits in X und Y unterscheiden sich, was dann verwendet wird, um die Bits in Y umzukehren, die sich von X unterscheiden. Dies ermöglicht den Austausch ohne die Verwendung einer temporären Variablen. Das Video betont auch die Bedeutung der Maskierung, um die Sicherheit bei der Arbeit mit diesen Tricks zu gewährleisten.
  
  
• 00:20:00 In diesem Abschnitt diskutiert der Sprecher zwei Bit-Hacks. Der erste Hack ist eine Methode, um zwei Variablen auszutauschen, ohne eine temporäre Variable zu verwenden. Der Hack beinhaltet die Verwendung von XOR und einer Maske, um die Bits umzukehren, die sich zwischen den beiden Variablen unterscheiden. Obwohl dieser Hack cool ist, ist er aufgrund der schlechten Parallelität auf Befehlsebene nicht die effizienteste Methode zum Austauschen von Variablen. Der zweite Hack ist eine Möglichkeit, das Minimum von zwei Ganzzahlen zu finden, ohne if-else-Anweisungen zu verwenden, die aufgrund von Verzweigungsfehlvorhersagen zu Leistungsproblemen führen können. Stattdessen zeigt der Referent, wie man bitweise Operationen verwendet, um die ganzen Zahlen zu vergleichen und das Minimum ohne Verzweigung zu berechnen.
  
  
• 00:25:00 In diesem Abschnitt erörtert der Referent die Codeoptimierung und die Verwendung des Schlüsselworts „restrict“ in einer Unterroutine, die zwei sortierte Arrays zusammenführt. Der Vorgang wird anhand eines Beispiels erläutert, bei dem zwei grüne Arrays zu einem blauen Array zusammengeführt werden. Die Vorhersagbarkeit jeder Verzweigung im Code wird ebenfalls diskutiert, wobei die erste Verzweigung vorhersehbar ist, während die zweite unvorhersehbar ist.
  
  
• 00:30:00 In diesem Abschnitt behandelt das Video vorhersagbare und unvorhersehbare Verzweigungen in der Programmierung und stellt einen No-Branch-Minimum-Bit-Trick als Lösung für das Problem der unvorhersehbaren Verzweigungen vor. Der Trick besteht darin, eine Variable namens "comp" zu verwenden, um das Vergleichsergebnis zwischen dem ersten Element von a und b zu speichern und das Minimum von a und b mit einem Bittrick zu erhalten. Dann wird der Minimalwert in C platziert, und der Wert von A oder B wird basierend auf dem Wert von "comp" inkrementiert oder dekrementiert. Das Video weist darauf hin, dass der Trick zwar in einigen Fällen nicht funktioniert, es aber hilfreich ist, zu verstehen, was der Compiler tut, und dass viele Bit-Hacks für Wörter zu Bit- und Wort-Hacks für Vektoren führen können, sodass es nützlich ist, diese Tricks zu kennen.
  
  
• 00:35:00 In diesem Abschnitt behandelt das Video Bit-Hacks und ihre Nützlichkeit beim Programmieren. Das angegebene Beispiel ist ein kleiner Trick für die modulare Addition, der schnellere Operationen ohne Division ermöglicht. Indem Z auf die Summe von X und Y gesetzt und dann überprüft wird, ob es kleiner oder größer als N ist, kann das Programm Z zurückgeben, wenn es innerhalb des Bereichs liegt, oder das Ergebnis von Z minus N, um es wieder in den Bereich zu bringen. Das Programm verwendet eine ähnliche Logik wie Minimum und hat eine unvorhersehbare Verzweigung, die zu einer falschen Vorhersage der Verzweigung führen kann. Ein weiteres gegebenes Beispiel ist eine Möglichkeit, einen Wert auf die nächste Zweierpotenz aufzurunden, indem Bitmanipulation verwendet wird, indem N dekrementiert wird, bitweise oder Operationen durchgeführt werden, wobei N um unterschiedliche Werte nach rechts verschoben wird, und dann am Ende erhöht wird.
  
  
• 00:40:00 In diesem Abschnitt des Videos diskutiert der Sprecher zwei Bit-Manipulationsprobleme. Das erste Problem besteht darin, die kleinste Zweierpotenz zu finden, die größer als ein gegebener Wert n ist. Der Referent erklärt, wie man dies erreicht, indem man Bitmanipulation verwendet und n dekrementiert, wenn es bereits eine Zweierpotenz ist, um sicherzustellen, dass der Logarithmus von n minus einem Bit gesetzt ist. Das zweite Problem besteht darin, die Maske des niederwertigsten in einem Wort X zu berechnen, und der Sprecher erklärt, wie man dies erreicht, indem er das Ergebnis auf X setzt und die bitweise und Operation mit negativem X verwendet. Der Sprecher präsentiert auch Code, um den Index zu finden des Bits, indem Sie X mit einer Konstanten multiplizieren und das Ergebnis in einer Tabelle nachschlagen. Der Abschnitt endet damit, dass der Sprecher einen mathematischen Zaubertrick vorführt, der eine Bitmanipulation beinhaltet.
  
  
• 00:45:00 In diesem Abschnitt zeigt ein YouTube-Video eine Gruppe, die einen Zaubertrick mit Karten und einer Glocke vorführt. Der Darsteller behauptet, die Gedanken des Publikums zu lesen und bittet sie, das Kartenspiel zu zerschneiden, bevor sie es verteilen. Der Darsteller sagt die Farbe und Nummer der Karte jeder Person voraus und ist scheinbar erfolgreich. Sie schreiben ihre Fähigkeiten dem Tragen eines „fantastischen Stramplers“ und eines magischen Hutes sowie dem Reinigen der Luft mit einer Glocke zu.
  
  
• 00:50:00 In diesem Abschnitt lernen wir die de Bruyne-Folge und ihren Zusammenhang mit der Berechnung der logarithmischen Basis 2 einer Potenz von 2 kennen. Die de Bruyne-Folge ist eine zyklische Bitfolge, in der jede mögliche Bitfolge der Länge K genau vorkommt einmal als Teilstring in der Sequenz. Unter Verwendung einer Umwandlungstabelle können wir die De-Bruyne-Folgenkonstante mit einer Potenz von 2 multiplizieren und den Teilstring extrahieren, der am Anfang der Folge erscheint, um die logarithmische Basis 2 der Potenz von 2 zu berechnen. Indem wir die Folge nach links verschieben und dann suchen Wenn wir die Startposition des Teilstrings in der Konvertierungstabelle erhöhen, können wir die logarithmische Basis 2 der Ganzzahl bestimmen, mit der wir begonnen haben, was den zuvor demonstrierten Kartentrick löst.
  
  
• 00:55:00 In diesem Abschnitt diskutiert der Sprecher die de Bruijn-Folge, die eine zyklische Folge eines binären Alphabets ist, die jede mögliche n-Bit-Kette genau einmal enthält. Die Folge kann verwendet werden, um Probleme wie das N-Damen-Problem zu lösen, und kann durch einen Zaubertrick erzeugt werden. Der Referent erklärt auch, wie der Bit-Trick funktioniert, um die Position eines Teilstrings einer de Bruijn-Folge nach einer Linksverschiebung zu bestimmen. Die Leistung dieses Bittricks ist durch die Leistung der Multiplikation und der Tabellensuche begrenzt, aber es gibt jetzt einen Hardwarebefehl, um ihn zu berechnen.
  
  
• 01:00:00 In diesem Abschnitt diskutiert der Sprecher das N-Damen-Problem, bei dem es darum geht, N Schachköniginnen auf einem NxN-Schachbrett so zu platzieren, dass sich keine zwei Damen gegenseitig bedrohen. Das Problem wird oft durch Backtracking implementiert, bei dem Damen Reihe für Reihe platziert werden und das Programm zurückverfolgt, wenn keine gültige Position gefunden werden kann. Es werden auch verschiedene Darstellungen des Boards diskutiert, wobei die kompakteste ein Satz von drei Bit-Vektoren ist. Der Abwärtsvektor speichert das Vorhandensein von Damen in jeder Spalte, der Linksdiagonalvektor speichert das Vorhandensein von Damen auf jeder linken Diagonale und der Rechtsdiagonalvektor speichert das Vorhandensein von Damen auf jeder rechten Diagonale. Die Verwendung von Bitvektoren ermöglicht eine effizientere Implementierung des Algorithmus.
  
  
• 01:05:00 In diesem Abschnitt wird der Prozess der Überprüfung, ob eine Stellung sicher ist, um eine Dame in einem n-Damen-Problem unter Verwendung von Bitvektoren zu platzieren, beschrieben. Bei den drei Prüfungen wird überprüft, ob sich bereits eine Dame in derselben Reihe, derselben Spalte und derselben Diagonale wie die Position befindet. Diese Methode ist effizient und garantiert, dass eine Königin sicher platziert werden kann, wenn sie alle drei Prüfungen besteht. Ein weiteres diskutiertes Problem ist die Populationszählung, bei der die Anzahl der 1-Bits in einem Wort X gezählt wird. Das vorgestellte Verfahren eliminiert wiederholt das niedrigstwertige 1-Bit in X, bis es Null wird, und die Anzahl der erforderlichen Iterationen ist proportional zur Anzahl von 1 Bit in X.
  
  
• 01:10:00 In diesem Abschnitt erörtert der Sprecher die Verwendung der Tabellensuche zum effizienten Zählen der Anzahl von 1-Bits in einem Binärwort. Das Tabellensuchverfahren umfasst das Erstellen einer Tabelle der Größe 256, die die Anzahl der Einsen in jedem 8-Bit-Wort speichert, und das anschließende Nachschlagen der Zählung für jede 8-Bit-Teilzeichenfolge in dem Binärwort. Der Sprecher merkt an, dass die Leistung dieses Verfahrens durch die zum Zugriff auf die Tabelle erforderlichen Speicheroperationen beeinträchtigt wird. Der Redner stellt eine dritte Möglichkeit vor, die Anzahl der 1-Bits mithilfe von Registern zu zählen, bei denen sie Masken erstellen und spezifische Anweisungen ausführen, die es ihnen ermöglichen, die Anzahl der Einsen in einem Binärwort zu zählen, ohne auf den Speicher zuzugreifen. Der Moderator erklärt anhand eines Beispiels, wie diese Methode funktioniert.
  
  
• 01:15:00 In diesem Abschnitt demonstriert der Sprecher, wie man die Anzahl der Einsen in einem Eingabewort mit einer parallelen Teile-und-Herrsche-Methode zählt, bei der die Leistung proportional zur logarithmischen Basis zwei der Wortlänge W ist. It's wies darauf hin, dass die meisten modernen Maschinen eine intrinsische Pop-Count-Anweisung haben, die schneller ist als alles, was codiert werden kann und über Compiler-Intrinsics zugänglich ist. Dies kann jedoch dazu führen, dass Code weniger über verschiedene Computer portierbar ist. Der Redner stellt einige Ressourcen bereit, um mehr über Bittricks zu erfahren, darunter eine Website, ein Lehrbuch, eine Schachprogrammierungs-Website und ein Buch namens Hacker's Delight.

[MetaQuotes]

Vorlesung 4. Assemblersprache & Computerarchitektur

Vorlesung 4. Assemblersprache & Computerarchitektur

Dieses Video bietet einen umfassenden Überblick über Assemblersprache und Computerarchitektur. Die Assemblersprache ist eine wichtige Schnittstelle zur Optimierung der Codeleistung, und das Verständnis der Computerarchitektur ist für die Beherrschung der Assemblersprache unerlässlich. Der Referent erläutert die Geschichte der x86 64-Architektur und ihre Entwicklung, ihre Schlüsselregister, Datentypen, Speicheradressierungsmodi und die Befehlssatzarchitektur, einschließlich Stacks, ganzzahliger und binärer Logik, boolescher Logik und Subroutinen. Sie diskutieren auch Erweiterungen wie Null- und Vorzeichenerweiterung und verschiedene Adressierungsmodi in Assemblersprache. Darüber hinaus behandelt das Video Gleitkommatypen, Vektoren und Vektoreinheiten, herkömmliche und SSE-Anweisungen sowie Designfunktionen für Computerarchitekturen wie superskalare Verarbeitung, Out-of-Order-Ausführung und Verzweigungsvorhersage.

Das Video behandelt auch mehrere Themen im Zusammenhang mit Assemblersprache und Computerarchitektur. Eines der zentralen Themen ist Parallelität auf Befehlsebene (ILP) und Pipeline-Stalls, die durch Gefahren wie Datenabhängigkeiten verursacht werden. Der Redner erörtert wahre, Anti- und Ausgangsdatenabhängigkeiten und wie superskalare Prozessoren mehr Parallelität in der Hardware nutzen können, um mehrere Befehle gleichzeitig auszuführen. Um Gefahren zu vermeiden, haben Architekten jedoch Strategien wie Umbenennen und Neuordnen sowie spekulative Ausführung implementiert, um das Ergebnis einer Verzweigung zu erraten und im Voraus auszuführen. Der Referent ermutigt das Publikum, diese Methoden zu verstehen, um Softwareoptimierungen besser zu verstehen.

• 00:00:00 In diesem Abschnitt spricht der Kursleiter über Assemblersprache und Computerarchitektur, die in modernen Softwarekursen oft nicht behandelt werden. Das Verständnis dieser Konzepte ist notwendig, um die Codeleistung zu optimieren, und die Assemblersprache ist die beste Schnittstelle dafür. Der Prozess des Kompilierens von Code umfasst mehrere Phasen, darunter Vorverarbeitung, Kompilierung, Assemblierung und Verknüpfung. Die Assemblersprache ist eine mnemonische Struktur des Maschinencodes, die ihn für Menschen lesbarer macht, und die endgültige ausführbare Datei wird durch eine Verknüpfungsphase mit dem LD-Befehl erzeugt.
  
  
• 00:05:00 In diesem Abschnitt erklärt der Referent, dass Assembler- und Maschinencode in ihrer Struktur sehr ähnlich sind, wobei OP-Codes in Assembler bestimmten Bitmustern im Maschinencode entsprechen. Der Referent stellt das Programm ABS vor, das eine Zerlegung von Maschinencode erzeugen kann und den mnemotechnischen, für Menschen lesbaren Assemblercode freigibt. Der Redner erörtert dann mehrere Gründe, warum jemand sich Assemblercode ansehen möchte, darunter das Aufdecken, was der Compiler getan und was nicht getan hat, das Debuggen von Compilerfehlern und das Reverse Engineering eines Programms ohne Zugriff auf seine Quelle.
  
  
• 00:10:00 In diesem Abschnitt erläutert der Referent die Erwartungen an die Klasse, darunter das Verständnis, wie ein Compiler linguistische Konstrukte mit x86-Anweisungen implementiert, die Fähigkeit, die x86-Assemblersprache zu lesen, und das Verständnis der Leistungsauswirkungen gängiger Assemblermuster. Die Schüler sollten auch in der Lage sein, Code bei Bedarf von Grund auf neu zu schreiben und so weit zu beherrschen, dass dies möglich ist. Der Redner taucht dann in die x86-64-Befehlssatzarchitektur ein, einschließlich Register, Befehle, Datentypen und Speicheradressierungsmodi. Zu den Schlüsselregistern gehören Allzweckregister und das Flags-Register, das arithmetische Operationen und Überträge verfolgt. Der Befehlszeiger führt die Hardware durch die Folge von Befehlen in einem Programm in Assemblersprache.
  
  
• 00:15:00 In diesem Abschnitt erörtert der Redner die Geschichte der x86-64-Architektur und ihre Entwicklung von 16-Bit-Wortmaschinen mit begrenztem Speicher zu breiteren Wörtern für die Indizierung, als mehr Speicher verfügbar wurde. Der Referent erklärt auch das Hinzufügen von Vektorregistern wie den xmm- und AVX-Registern zur Vektorisierung und wie sie verwendet werden. Sie berühren auch das Thema Allzweckregister und wie sich ihre funktionalen Zwecke im Laufe der Zeit erheblich verändert haben, aber ihre Namen aus historischen Gründen geblieben sind. Darüber hinaus erklärt der Sprecher, wie bestimmte Register für die untere und die obere Hälfte des Kurzworts, der 32-Bit- oder der 64-Bit-Wörter auf dasselbe Alias gesetzt werden.
  
  
• 00:20:00 In diesem Abschnitt erklärt der Referent die Grundlagen der x86 64-Assemblersprache und wie sie funktioniert. Register haben unterschiedliche Namen, je nachdem, auf welchen Teil des Registers zugegriffen wird, und einige haben bestimmte Zwecke, wie z. B. die Verwendung von RSP als Stapelzeiger. Das Format eines x86 64-Befehlscodes besteht darin, einen Opcode und eine Operandenliste zu haben, normalerweise mit 0-3 Operanden, die Quellen oder Ziele sein können. Der Referent erklärt den Unterschied zwischen der AT&T-Syntax und der Intel-Syntax für die Bezugnahme auf Operationen und liefert eine Liste gängiger Op-Codes wie „move“ und „conditional move“. Außerdem erklärt der Referent, wie wichtig es ist, das Vorzeichen zu erweitern, wenn man von einem 32-Bit-Wertregister in ein 64-Bit-Register wechselt.
  
  
• 00:25:00 In diesem Abschnitt erörtert der Sprecher die verschiedenen Arten von Anweisungen in Assemblersprache, einschließlich Anweisungen für Stapel, ganzzahlige Arithmetik, binäre Logik, boolesche Logik, Sprünge und Subroutinen. Die Opcodes können mit einem Suffix erweitert werden, das den Datentyp der Operation oder einen Bedingungscode beschreibt. Zum Beispiel zeigt eine Bewegung mit einem „Cue“, dass die Daten, die verschoben werden, ein Quad-Wort sind, das aus 8 Bytes oder 64 Bits besteht. Die x86 64-Datentypen und ihre Assembly-Suffixe werden ebenfalls besprochen, und es werden Beispiele gegeben, um zu veranschaulichen, wie die Zeichenerweiterung funktioniert. Das Vorhandensein oder Fehlen bestimmter Opcodes und Mnemoniken in der Assemblersprache kann verwirrend sein, aber der Compiler muss diese Anweisungen verstehen, um das Programm korrekt auszuführen.
  
  
• 00:30:00 In diesem Abschnitt erörtert der Redner die Erweiterungen wie Nullerweiterung und Vorzeichenerweiterung, die auftreten, wenn 32-Bit-Operationen in 64-Bit-Operationen verschoben werden. Sie erwähnen auch, wie der Intel-Befehlssatz durch das Hinzufügen neuer Befehle komplizierter werden kann. Der Sprecher fährt fort, die verschiedenen Bedingungscodes zu erläutern, die in bedingten Sprüngen und bedingten Bewegungen verwendet werden, und die Flags, die mit ihnen verwendet werden, wie etwa das Null-Flag und das Überlauf-Flag. Der Grund für bestimmte Bedingungscodes, die das Null-Flag prüfen, wird ebenfalls diskutiert.
  
  
• 00:35:00 In diesem Abschnitt erörtert der Sprecher die verschiedenen direkten und indirekten Adressierungsmodi in Assemblersprache. Zu den direkten Adressierungsmodi gehören der unmittelbare, der direkte Speicher und die Verwendung eines Registers. Registerindirekte und registerindizierte Adressierungsmodi ermöglichen den Zugriff auf den Speicher, indem die Adresse in einem Register bereitgestellt oder die Adresse versetzt wird. Der Redner weist darauf hin, dass der Zugriff auf den Speicher langsam und teuer sein kann, daher ist es wichtig, Werte wann immer möglich in Registern zu speichern, um den Prozess zu beschleunigen. Sie erwähnen auch die Bedeutung des Cachings bei der Optimierung des Speicherzugriffs.
  
  
• 00:40:00 In diesem Abschnitt behandelt das Video die Verwendung der zeigerrelativen Indizierung, bei der der Anweisungszeiger zum Indizieren von Daten anstelle eines Allzweckregisters verwendet wird. Das Adressierungsverfahren für die Basisindex-Skalenverschiebung wird ebenfalls eingeführt, was eine komplizierte Anweisung ist, die ein sanftes Indizieren von einem Basiszeiger unterstützt. Das Video bietet einen Überblick über einige Redewendungen der Assemblersprache, einschließlich des XOR-Opcodes, der zum Nullen von Registern verwendet wird, und des Test-Opcodes, der das bitweise und von zwei Werten berechnet und die Register-Flags beibehält. Schließlich berührt das Video Sprunganweisungen und Beschriftungen, die einen Kontrollfluss im Code ermöglichen.
  
  
• 00:45:00 In diesem Abschnitt behandelt das Video Assemblersprache und Computerarchitektur, einschließlich verschiedener Befehlssätze und der Geschichte von Fließkommazahlen. Die x86-Befehlssätze, einschließlich x87 und SSE, unterstützen skalare Gleitkommaarithmetik mit einfacher und doppelter Genauigkeit sowie Vektorbefehle. Die SSE-Anweisungen werden im Allgemeinen von Compilern gegenüber x87 aufgrund ihrer Einfachheit bei der Kompilierung und Optimierung bevorzugt. Der Zweck der Verwendung von no operation (nop)-Anweisungen beim Zusammenbau, wie z. B. Ausrichtungsoptimierung, wird ebenfalls erläutert.
  
  
• 00:50:00 In diesem Abschnitt erörtert der Referent Gleitkommatypen, Vektoren und Vektoreinheiten, die in der Computerarchitektur verwendet werden. Der Sprecher erklärt, dass Vektoreinheiten so funktionieren, dass der Prozessor Anweisungen an alle Vektoreinheiten ausgibt, von denen jede als Lane bezeichnet wird. Die Bahnen enthalten die Integer- oder Fließkomma-Arithmetik und arbeiten alle im Gleichschritt, was bedeutet, dass sie alle dasselbe tun. Sie können mehrere Operationen gleichzeitig ausführen, und das alles mit einer einzigen Anweisung. Der Referent erklärt, dass einige Architekturen erfordern, dass Vektoroperanden ausgerichtet werden, während andere Vektoren im Speicher verschieben können, was zu einem Leistungsunterschied zwischen den beiden führt. Darüber hinaus gibt es Architekturen, die bahnübergreifende Operationen unterstützen, wie z. B. Permutieren, Mischen und Scatter-Gather.
  
  
• 00:55:00 In diesem Abschnitt erörtert der Sprecher die Unterschiede zwischen traditionellen und SSE-Anweisungen und wie sie verwendet werden können. Sie erwähnen auch den Aliasing-Trick, bei dem ymm Alias xmm-Register registriert und sie mit avx-512 auf 512 Bit erweitert. Anschließend befassen sie sich mit der Computerarchitektur, insbesondere mit dem Unterschied zwischen einer fünfstufigen Pipeline und einem modernen Prozessor mit 14 bis 19 Pipelinestufen. Zu den von ihnen diskutierten Designmerkmalen gehören Vektor- oder Hardware I, superskalare Verarbeitung, Out-of-Order-Ausführung und Verzweigungsvorhersage, aber sie erwähnen, dass sie sich aus Zeitgründen nicht tief in die Out-of-Order-Ausführung vertiefen werden.
  
  
• 01:00:00 In diesem Abschnitt des Videos erläutert der Kursleiter Parallelität auf Befehlsebene (ILP) und Pipeline-Stalls. ILP beinhaltet das Finden von Möglichkeiten, mehrere Anweisungen gleichzeitig auszuführen, um den Durchsatz zu verbessern. Pipeline-Stalls können jedoch auftreten, wenn eine Anweisung aufgrund einer Gefahr nicht ausgeführt werden kann, wie z. B. einer strukturellen Gefahr, einer Datengefahr oder einer Steuerungsgefahr, wobei Datenrisiken am häufigsten vorkommen. Eine echte Abhängigkeit tritt auf, wenn ein Befehl nach einer Schreibabhängigkeit liest, während eine Anti-Abhängigkeit auftritt, wenn ein Befehl in eine Stelle schreiben möchte, aber warten muss, bis der vorherige Befehl den Wert gelesen hat. Der Compiler versucht, Verzögerungen in der Pipeline zu reduzieren, indem er den Code optimiert, um Gefahren zu vermeiden.
  
  
• 01:05:00 In diesem Abschnitt wird das Konzept der Datenabhängigkeiten in der Assemblersprache besprochen. Es gibt drei Arten von Datenabhängigkeiten: true, anti und output. Arithmetische Operationen, insbesondere komplexe wie Gleitkommaarithmetik, haben eine längere Latenzzeit und erfordern separate Funktionseinheiten im Prozessor, manchmal mit separaten Registern. Um die Parallelität auf Befehlsebene zu erhöhen, haben Architekten Techniken wie das Ausgeben mehrerer Befehle pro Zyklus implementiert, um mehr Parallelität in der Hardware auszunutzen.
  
  
• 01:10:00 In diesem Abschnitt erklärt das Video, wie superskalare Prozessoren mehrere Befehle gleichzeitig ausführen können, am Beispiel von Haswell, der Befehle in einfachere Operationen, sogenannte Micro-Ops, zerlegt und bis zu vier Micro-Ops pro Zyklus ausgibt. Das Video beschreibt dann Strategien, um Prozessoren von der Ausführung von Anweisungen in der richtigen Reihenfolge zu befreien, einschließlich Umgehung und Registerumbenennung, die es ermöglichen, dass nicht abhängige Anweisungen außerhalb der Reihenfolge ausgeführt werden, was zu schnelleren Verarbeitungszeiten führt. Diese Strategien erfordern es, Abhängigkeiten im Auge zu behalten und Code so auszuführen, dass Gefahren wie Datenabhängigkeiten vermieden werden.
  
  
• 01:15:00 In diesem Abschnitt erörtert der Redner das Umbenennen und Neuordnen, zwei wichtige Methoden, die in modernen Prozessoren verwendet werden, um Datenrisiken zu vermeiden. Der Sprecher spricht auch über die spekulative Ausführung, die bei der Verzweigungsvorhersage verwendet wird, um das Ergebnis einer Verzweigung zu erraten und im Voraus auszuführen, um ein Abwürgen zu vermeiden. Wenn die Schätzung jedoch falsch ist, kostet es etwa 15 bis 20 Zyklen, um die Berechnung rückgängig zu machen. Der Redner erwähnt kurz, wie Verzweigungsprädiktoren funktionieren, weist jedoch darauf hin, dass dies kompliziert ist und weiterer Studien bedarf. Trotz des hastigen Endes ermutigt der Referent das Publikum, die verschiedenen Methoden zu verstehen, was helfen wird, zu verstehen, warum bestimmte Softwareoptimierungen funktionieren und nicht funktionieren.

[MetaQuotes]

Vortrag 5. C zur Versammlung

Vortrag 5. C zur Versammlung

In diesem Teil des Videos wird erläutert, wie wichtig es ist, C für die Assemblersprache zu verstehen, und wie C-Code mithilfe eines Compilers in Assemblersprache implementiert wird. Der Schwerpunkt liegt speziell darauf, wie LLVM IR in der Linux x86 64-Aufrufkonvention in Assembly übersetzt wird. Der Referent erklärt die grundlegenden Komponenten von LLVM IR und wie Konstrukte in der Programmiersprache C in LLVM IR übersetzt werden. Das Video behandelt auch das Layout des virtuellen Speichers, das Problem der Koordinierung von Funktionsaufrufen zwischen mehreren Funktionen und die Verwendung von zwei Zeigern – BP und SP – in der Linux x86 64-Aufrufkonvention zur Verwaltung aller Stack-Frames.

Das Video erklärt auch die Strategien zum Beibehalten von Registerzuständen in der C-to-Assembly-Programmierung, wie z. B. das Speichern von Registern entweder als caller-save oder callee-save, und wie die x86-Aufrufkonvention Arbeitsverschwendung vermeidet. Es behandelt, wie Funktionsaufrufe in C und Assembler funktionieren, diskutiert den Vorgang des Speicherns von Argumenten und lokalen Variablen auf dem Stapel sowie die allgemeine Optimierung der Verwendung des Stapelzeigers anstelle des Basiszeigers. Das Video zeigt auch den Prozess der Kompilierung von LV miR in Assembler-Code, die Erörterung des Funktionsprologs, das Speichern von Registern, die Handhabung von Bedingungen und das Konvertieren von C-Code in Assembler-Code mithilfe eines Kontrollflussdiagramms. Schließlich spricht es über den Funktionsepilog, der verwendet wird, um Register wiederherzustellen, bevor Ergebnisse zurückgegeben werden.

• 00:00:00 In diesem Abschnitt des Videos erläutert TB Shuttle, wie wichtig es ist, C für die Assemblersprache zu verstehen. Er stellt fest, dass die Assemblersprache eine größere Genauigkeit als C-Code bietet und Details über ein Programm offenbaren kann, die aus dem C-Code nicht ersichtlich sind. Ein Blick auf die Assemblierung kann es Entwicklern auch ermöglichen, festzustellen, was der Compiler bei der Optimierung eines Programms getan oder nicht getan hat. Darüber hinaus können Fehler auftreten, die nur bei der Optimierung von Code auf bestimmten Ebenen zu unerwartetem Verhalten führen würden, was es schwierig macht, diese Fehler zu erkennen. Schließlich kann das Verständnis von Assembler Entwicklern ermöglichen, den Assemblercode von Hand zu ändern oder Code zurückzuentwickeln.
  
  
• 00:05:00 In diesem Abschnitt erläutert das Video, wie C-Code in Assemblersprache mithilfe eines Compilers implementiert wird, der komplexe Entscheidungen darüber treffen muss, welche Assembleranweisungen verwendet werden sollen, wie C-Bedingungen und -Schleifen implementiert werden und wie Funktionsaufrufe koordinieren. Um den Übersetzungsprozess zu verstehen, stellt das Video die LVM IR vor, eine vereinfachte Baugruppe, die der Compiler verwendet, um über das Programm nachzudenken. Das Video erklärt dann, wie Konstrukte in der Programmiersprache C, wie Funktionen, Bedingungen und Schleifen, in LVM IR übersetzt werden. Der Abschnitt endet mit einer kurzen Erwähnung der LVM-IR-Attribute.
  
  
• 00:10:00 In diesem Abschnitt liegt der Schwerpunkt auf dem Prozess, wie LLVM ir in Assembly übersetzt wird, insbesondere in der Linux x86 64-Aufrufkonvention. Der Referent bietet eine kurze Einführung in LLVM ir und erklärt seine grundlegenden Komponenten von Funktionen, Anweisungen und Registern, die einer einfacheren Version der Assemblierung ähneln. LLVM-IR-Register ähneln c-Variablen und unterscheiden sich durch ihre Namen, und jede Funktion hat ihre eigenen lokalen Registernamen. Der Moderator hebt die Register in einem beispielhaften Codeausschnitt hervor und stellt fest, dass die Syntax für Register gekapert wird, wenn auf verschiedene Basisblöcke in LLVM verwiesen wird. Der Vortrag schließt mit einer Fallstudie darüber, wie dieser Prozess für einen einfachen Code zur Berechnung von Fibonacci-Zahlen funktioniert.
  
  
• 00:15:00 In diesem Abschnitt erläutert der Sprecher die Syntax von LV Mir-Anweisungen, die einen Registernamen, ein Gleichheitszeichen, einen Opcode und eine Operandenliste umfasst. Während einige Anweisungen einen Wert zurückgeben, der in einem lokalen Register gespeichert wird, tun andere dies nicht. Der LV Mir-Befehlssatz ist kleiner als der von x86, da er nur wenige Befehle für Datenbewegungen, arithmetische und logische Operationen und Kontrollfluss enthält. In LV Mir wird alles als Typen bereitgestellt, einschließlich Ganzzahlen (mit einer definierten Anzahl von Bits), Gleitkommatypen, Zeigertypen, Vektortypen und Labeltypen für Basisblöcke. Der Redner erwähnt auch, dass LV Mir-Vektoroperationen nicht wie SSE oder AVX aussehen, sondern eher wie gewöhnliche Operationen, die auf einem Vektortyp arbeiten.
  
  
• 00:20:00 In diesem Abschnitt erläutert das Video, wie Sequenzen von Operationen in C-Code in LLVM-IR übersetzt werden, sowie die Faustregeln für die Interpretation des Codes in IR. Der Auszug erklärt auch, wie LLVM IR mit primitiven und aggregierten Typen wie Arrays und Strukturen umgeht, und zeigt Beispiele dafür, wie der Zugriff auf Elemente in einem Array die Berechnung von Adressen im Speicher beinhaltet. Darüber hinaus erklärt das Video, wie C-Funktionen in LLVM IR übersetzt werden, mit den entsprechenden Rückgabeanweisungen in beiden Sprachen.
  
  
• 00:25:00 In diesem Abschnitt erklärt das Video, wie Funktionen und Parameter in C in LV Mir übersetzt werden. Funktionen in LV Mir ähneln Funktionen in C, aber C-Parameter werden in LV Mir zu Parameterlisten. Das Lesen von LV Mir kann jedoch eine Herausforderung sein, da die Register nicht gut benannt sind, was die Entzifferung erschwert. Das Video behandelt auch grundlegende Blöcke in LV Mir, bei denen es sich um Codeblöcke handelt, die basierend auf Kontrollflussanweisungen partitioniert sind. Die Verbindungen zwischen Basisblöcken basieren auf Kanten, die durch Verzweigungsbefehle induziert werden. Schließlich berührt das Video Bedingungen in LV Mir, wo if-then-else-Anweisungen zu bedingten Verzweigungsanweisungen werden, die grundlegende Blöcke induzieren und Flusskanten steuern.
  
  
• 00:30:00 In diesem Abschnitt erklärt das Video, wie bedingte Operationen und Verzweigungen in LLVM IR funktionieren. Der Prozess beginnt mit einem Vergleich zwischen einem Literalwert und einem in einem Register gespeicherten Wert, der eine Ein-Bit-Ganzzahl oder ein boolesches Ergebnis erzeugt. Dieses Ergebnis wird dann an eine bedingte Verzweigungsaktion weitergegeben, zusammen mit zwei Markierungen von Basisblöcken, die angeben, wohin zu gehen ist, wenn das Prädikat wahr oder falsch ist. Bei einer unbedingten Verzweigung mit einem Operanden erfolgt ein direkter Sprung zu einem bestimmten Basisblock. Das Video zeigt auch, wie man eine Rautenform im Kontrollflussgraphen erstellt, wenn eine bedingte Anweisung vorhanden ist, und bietet ein Beispiel für eine in C-Code geschriebene Schleife.
  
  
• 00:35:00 In diesem Abschnitt behandelt das Video die Komponenten einer C-Schleife, zu denen der Schleifenkörper und die Schleifensteuerung gehören. Der Schleifenkörper wird bei jeder Iteration ausgeführt, während die Schleifensteuerung alle Iterationen der Schleife verwaltet. Die AC-Schleife erzeugt ein Schleifenmuster im Kontrollflussdiagramm, das wiederum eine Schleifenstruktur im LLVM-IR erzeugt. Das Video analysiert dann den LLVM-IR-Code für die Schleifensteuerung, wo es eine seltsame Dateianweisung gibt, die häufig beim Umgang mit Schleifen auftritt. Die fie-Anweisung versucht, ein Problem mit der LLVM-Darstellung des Codes zu lösen, bei der I durch eine ganze Reihe verschiedener Register dargestellt wird, wodurch unklar wird, wohin ich tatsächlich gegangen bin.
  
  
• 00:40:00 In diesem Abschnitt erläutert das Video die Zuordnung der Induktionsvariablen in einer Schleife zu verschiedenen Stellen in LLVM, was aufgrund der sich ändernden Werte der Variablen über die Iterationen der Schleife hinweg geschieht. Dies führt bei LLVM zu der „Static Single Assignment“-Invariante, dass jede Anweisung den Wert eines Registers nur einmal definiert, was bei Induktionsvariablen ein Problem darstellt. Der „phi“-Befehl löst dieses Problem, indem er einen Registerwert definiert, der davon abhängt, wie der Kontrollfluss am Eintrittspunkt einer Schleife zusammengeführt wird. Das Video erörtert auch Attribute in LLVM und wie sie zusätzliche Informationen für LLVM-Konstrukte bereitstellen können, wie z. B. das NSW-Attribut, das an die „add“-Anweisung angehängt ist.
  
  
• 00:45:00 In diesem Abschnitt des Videos liegt der Schwerpunkt auf LLVM IR, das der Assemblierung ähnelt, aber in vielerlei Hinsicht einfacher ist, da alle berechneten Werte in Registern gespeichert werden, die wie gewöhnliche C-Variablen sind. LLVM IR verwendet das Paradigma der statischen Einzelzuweisung, bei dem jede Variable von höchstens einer Anweisung geschrieben wird. Das Video beschreibt, wie C-Code in LLVM IR und dann in die Assemblierung übersetzt wird, mit einigen zusätzlichen Komplexitäten im Prozess. Der Compiler wählt die eigentlichen Assembleranweisungen aus, die für die LLVM-IR-Operationen benötigt werden, entscheidet, welche Allzweckregister verwendet werden, und koordiniert Funktionsaufrufe zwischen verschiedenen Quelldateien und Binärbibliotheken. Die Diskussion wendet sich dann der Linux x86 64-Aufrufkonvention zu.
  
  
• 00:50:00 In diesem Abschnitt wird das Layout des virtuellen Speichers für ein Programm besprochen. Der virtuelle Speicher ist in Segmente unterteilt, wie z. B. die Stack- und Heap-Segmente, die unter Verwendung von Assembler-Direktiven im Assembler-Code organisiert sind. Darüber hinaus werden verschiedene Arten von Speicherdirektiven diskutiert, wie die Space-Direktive und das lange Segment, die Speicher zuweisen und Werte speichern. Die Aufmerksamkeit wird dann dem Stack-Segment zugewandt, wo Daten gespeichert werden, um Funktionsaufrufe und Rückgaben zu verwalten, was das Speichern lokaler Variablen, Funktionsargumente, der Rückgabeadresse und möglicherweise Zwischenergebnisse umfasst.
  
  
• 00:55:00 In diesem Abschnitt des Videos erörtert der Moderator das Problem der Koordinierung von Funktionsaufrufen über mehrere Funktionen hinweg, von denen einige möglicherweise aus verschiedenen Dateien oder Bibliotheken stammen. Um sicherzustellen, dass alle Funktionen gut zusammenspielen, wurde eine Aufrufkonvention festgelegt, der alle Funktionen gehorchen müssen. Die Linux x86 64-Aufrufkonvention verwendet zwei Zeiger – den BP und den SP – um alle Stack-Frames für jede Funktionsinstanziierung zu verwalten. Wenn eine Aufrufanweisung ausgeführt wird, wird der aktuelle Wert des IP als Rücksprungadresse auf den Stapel geschoben, und die Aufrufanweisung springt zu der Adresse einer Funktion im Programmspeicher. Die Rückkehranweisung macht die Operationen der Aufrufanweisung rückgängig und nimmt die Rückkehradresse aus dem Stapel, um zur Ausführung des Aufrufers zurückzukehren. Um das Problem zu lösen, dass mehrere Funktionen dasselbe verwenden möchten
  Register, die Aufrufkonvention beschreibt Regeln, welche Register jede Funktion verwenden kann und wie sie diese Register durch Funktionsaufrufe erhalten müssen.
  
  
• 01:00:00 In diesem Abschnitt behandelt das Video die Strategien zum Aufrechterhalten von Registerzuständen beim Arbeiten mit verschiedenen Funktionen in der C-to-Assembly-Programmierung. Es erwähnt die zwei Methoden, die verwendet werden können, eine, bei der der Aufrufer den Registerzustand speichert, bevor er einen Anruf aufruft, und die andere, bei der der Angerufene den gesamten Registerzustand speichert. Die x86-Aufrufkonvention umfasst beides, wobei einige Register als Callee-Save und andere als Caller-Save angegeben werden, um Arbeitsverschwendung zu vermeiden. Das Video untersucht auch, wie der Stapelspeicher organisiert ist und wie der Stapel verkleinert wird. Schließlich wird die Koordinierung erörtert, wie Funktionen überlappende Teile des Stapelspeichers verwenden werden.
  
  
• 01:05:00 In diesem Abschnitt erläutert das Video, wie ein Funktionsaufruf in C und Assembly funktioniert. Vor dem Aufrufen der Funktion C platziert die Funktion B Nicht-Register-Argumente für die Funktion C auf einem reservierten Verknüpfungsblock in ihrem eigenen Stapelspeicher unterhalb ihrer lokalen Variablen. Es greift auf diese Argumente mit negativen Offsets zu. Wenn die Funktion C startet, führt sie einen Funktionsprolog aus, der den Basiszeiger für den Stapelrahmen von B speichert und BP gleich SP setzt, weil sie in einen neuen Rahmen eintritt. Dann weist es Platz auf dem Stack für seine eigenen lokalen Variablen sowie Platz zu, den B für alle Verknüpfungsblöcke verwendet, die es für seine Aufrufer oder für die Dinge, die es aufruft, erstellt. Das Video erwähnt auch eine allgemeine Optimierung, bei der der Compiler BP loswerden und die gesamte Indizierung basierend auf dem Stapelzeiger RSP durchführen könnte, um ein weiteres Allzweckregister zu erhalten.
  
  
• 01:10:00 In diesem Abschnitt führt der Kursleiter das Publikum durch den Prozess der Kompilierung von LV miR bis hin zum Assemblercode. Der erste Schritt besteht darin, die Funktion "fib" als global zugängliche Funktion zu definieren, indem einige Assembler-Direktiven wie die globale fib-Direktive und die Ausrichtung verwendet werden. Dann wird der Funktionsprolog mit einer Push-Warteschlange von var BP und einer Mob-Warteschlange von RSP rbp gespeichert. Der Assembler-Code schiebt auch ein paar Register auf den Stack, die Kali-Save-Register sind, bevor er das Argument in die Funktion RTI verschiebt und es in das RBX-Register verschiebt. Schließlich wird eine Vergleichsanweisung ausgewertet, um zu prüfen, ob der Wert von N kleiner als zwei ist, und wenn dies der Fall ist, gibt sie den Eingangswert zurück. Andernfalls durchläuft es einen geradlinigen Code, um fib von n minus eins und fib von n minus zwei zu berechnen, sie zu addieren und das Ergebnis zurückzugeben.
  
  
• 01:15:00 In diesem Abschnitt erläutert das Video bedingte Sprünge und die unterschiedlichen Verhaltensweisen, die als nächstes im Code in Abhängigkeit von den Vergleichsergebnissen auftreten. Der JGE-Befehl springt zum Label für die falsche Seite der LLVM-Verzweigungsoperation, wenn n größer oder gleich 2 ist, während die Operationen der wahren Seite der Operation entsprechen, wenn n kleiner als 2 ist. Der LEA-Befehl wird für verwendet Adressberechnung, während die Move-Operation das Ergebnis des Funktionsaufrufs in R14 speichert. Der nächste Befehlssatz berechnet den Wert von n-2, speichert ihn in RDI und ruft dann fib auf n-2 auf und gibt das Ergebnis an unser AX zurück. Schließlich fügt die Operation R14 zu unserem AX hinzu.
  
  
• 01:20:00 In diesem Abschnitt behandelt das Video die Umwandlung von C-Code in Assembler-Code. Der Sprecher erklärt, dass der Prozess einen Kontrollflussgraphen verwendet, der aus Grundblöcken besteht, die durch Kontrollflusskanten verbunden sind, um den Code darzustellen. Sie erwähnen auch die Komplexität des Umgangs mit Aufrufkonventionen im Assemblercode. Der Funktionsepilog wird verwendet, um Register vor irgendetwas im Stapelrahmen wiederherzustellen, bevor das Ergebnis zurückgegeben wird. Das Video schließt mit einer Zusammenfassung der Hauptthemen, die im gesamten Abschnitt behandelt werden.

[MetaQuotes]

Vorlesung 6. Multicore-Programmierung

Vorlesung 6. Multicore-Programmierung

Dieser Videovortrag behandelt die Multicore-Programmierung und die Entstehung von Multicore-Prozessoren aufgrund des Mooreschen Gesetzes und das Ende der Skalierung von Taktfrequenzen. Der Redner erklärt das Problem der Leistungsdichte, mit dem Prozessoren konfrontiert sind, und wie es dazu führte, dass Chips um mehrere Kerne erweitert wurden, um mit dem Moore'schen Gesetz Schritt zu halten. Die Vorlesung behandelt auch die Grundlagen von Cache-Kohärenzprotokollen in Shared-Memory-Hardware und Parallelitätsplattformen wie Pthreads, TBB, OpenMP und Silk, die Abstraktionen für die parallele Programmierung bereitstellen. Die Vor- und Nachteile jeder Plattform werden diskutiert und anhand von Beispielen für die Implementierung von Fibonacci-Programmen demonstriert. Das Video bietet einen umfassenden Überblick über die Multi-Core-Programmierung und die Herausforderungen und Lösungen, denen Programmierer gegenüberstehen.

Das Video behandelt auch verschiedene Aspekte von Silk, einem Abstraktionstool zur Handhabung der Parallelverarbeitung. Der Referent bespricht Themen wie verschachtelte Silk-for-Loops, Generieren von Assembler-Code, Reduktion mit Reducern, Scheduler und Leistungsoptimierung. Sie bieten auch einen Überblick über das Silk-Ökosystem und verwandte Tools wie Silk Sanitizer und Silk Scale zum Debuggen bzw. Analysieren der Skalierbarkeit. Die wichtigste Erkenntnis ist, dass das Schreiben paralleler Programme für Multicore-Prozessoren eine Herausforderung sein kann, aber Silk vereinfacht den Prozess, indem es komplexe Aufgaben effizient handhabt und Programmierern mehr Kontrolle über die Ausführung ihres Codes gibt.

• 00:00:00 In diesem Abschnitt erörtert der Kursleiter die Multicore-Programmierung und die Gründe für das Aufkommen von Multicore-Prozessoren. Mit dem Aufkommen des Mooreschen Gesetzes, das besagt, dass sich die Anzahl der Transistoren, die auf einen Chip passen, alle zwei Jahre verdoppelt, und dem Ende der Skalierung der Taktfrequenzen um 2004 bis 2005 begannen Halbleiterhersteller mit der Produktion von Chips mit mehreren Prozessorkernen darauf. Dies lag daran, dass es nicht mehr möglich war, die Frequenz einzelner Kerne auf einem Chip zu erhöhen, was die Umstellung auf ein Designmodell erforderlich machte, das eine parallele Verarbeitung ermöglichte. Der Dozent verdeutlicht auch den Zusammenhang zwischen der Anzahl der Transistoren auf einem Chip und der maximalen Taktfrequenz des Prozessors.
  
  
• 00:05:00 In diesem Abschnitt erörtert der Redner das Problem der Leistungsdichte, mit dem Prozessoren konfrontiert sind, bei denen eine zunehmende Taktfrequenz zu einem exponentiellen Anstieg der Leistungsdichte führt. Dies führte dazu, dass den Chips mehrere Kerne hinzugefügt wurden, um mit dem Mooreschen Gesetz Schritt zu halten und die Leistungsdichtegrenzen nicht zu überschreiten. Anschließend stellt der Referent die abstrakte Multicore-Architektur, bekannt als Chip-Multiprozessor, vor und umreißt die Vorlesungen zu Hardware-Herausforderungen und Softwarelösungen zur Programmierung paralleler Programme auf Multicore-Rechnern unter Verwendung verschiedener Parallelitätsplattformen wie P-Threads, winAPI-Threads, Intel-Threading Bausteine, openmp und so weiter.
  
  
• 00:10:00 In diesem Abschnitt erklärt der Referent, wie Caches in der Multicore-Programmierung funktionieren. Wenn ein Prozessor einen Wert aus dem Hauptspeicher in seinen Cache lädt, behält er diesen Wert im Cache, falls er in Zukunft erneut darauf zugreifen muss. Wenn ein anderer Prozessor den gleichen Wert laden möchte, kann er ihn auch durch den Cache des ersten Prozessors bekommen, anstatt den ganzen Weg zum Hauptspeicher zu gehen. Es entsteht jedoch ein Problem, wenn ein Prozessor den Wert in seinem eigenen Cache aktualisiert, wodurch der Wert im Cache eines anderen Prozessors veraltet wird. Das MSI-Protokoll ist eine grundlegende Lösung für dieses Problem, das Cache-Zeilen mit drei möglichen Zuständen (M, S und I) kennzeichnet, um die Kohärenz zwischen den Caches sicherzustellen.
  
  
• 00:15:00 In diesem Abschnitt behandelt die Vorlesung die Grundlagen von Cache-Kohärenzprotokollen in Shared-Memory-Hardware, insbesondere wie Änderungen an einer Cache-Zeile im Cache eines Prozessors die Kopien derselben Zeile in anderen Caches ungültig machen können. Die Vorlesung stellt ein einfaches Protokoll vor und erklärt, wie andere komplexere Protokolle in der Praxis existieren. Die Hardware ist für die Verwaltung von Konflikten verantwortlich, wenn mehrere Prozessoren dieselbe Cache-Zeile ändern, aber dies kann zu einem „Invalidierungssturm“ führen und die Leistung verlangsamen. Der Vortrag weist auch darauf hin, dass Parallelitätsplattformen diese Komplexitäten abstrahieren und bei der Synchronisation und Kommunikation in der parallelen Programmierung helfen können.
  
  
• 00:20:00 In diesem Abschnitt erörtert der Referent verschiedene Parallelitätsplattformen am Beispiel der Fibonacci-Zahlen. Das Fibonacci-Programm wird mit einem rekursiven Algorithmus implementiert, der Fibonacci-Zahlen mehrmals berechnet, was es zu einem schlechten Algorithmus macht. Die beiden rekursiven Aufrufe können parallelisiert werden, da es sich um völlig unabhängige Berechnungen handelt. Pthreads, eine Standard-API für Threading, kann verwendet werden, um diese Parallelisierung zu implementieren.
  
  
• 00:25:00 In diesem Abschnitt erörtert der Redner Pthreads, eine Bibliothek von Funktionen, die Parallelität bei der Programmierung ermöglichen. Pthreads bietet eine Do-it-yourself-Parallelitätsplattform, da Sie die Parallelität in Ihrem Code mithilfe einer Bibliothek von Funktionen mit spezieller Semantik angeben können. Jeder Thread in Pthreads implementiert eine Abstraktion eines Prozessors und wird auf die tatsächlichen Maschinenressourcen gemultiplext. Pthreads stellt auch Masken bereit, die die an der inneren Thread-Koordination beteiligten Protokolle vereinfachen. Die Pthreads-Bibliothek hat Schlüsselfunktionen wie pthread_create, die den neuen Thread speichert und identifiziert, den pthread erstellt, und pthread_join, das wartet, bis der Thread beendet ist, bevor er im Code fortfährt. Der Referent demonstriert die Implementierung einer Fibonacci-Reihe mit Pthreads.
  
  
• 00:30:00 In diesem Abschnitt erörtert der Moderator die Implementierung von Pthreads-Code zur parallelen Ausführung der Fibonacci-Folge. Sie erklären, dass es aufgrund der Kosten für die parallele Erstellung von Threads besser ist, das Programm sequenziell auszuführen, wenn die Eingabegröße klein genug ist. Der Code marshallt das Eingabeargument für den Thread und speichert es in der Argumentstruktur. Der Moderator erläutert Pthread create, Pthread join und einige seiner Nachteile, z. B. dass es viel komplizierter wird, wenn der Code rekursiv Threads erstellen muss. Sie erwähnen auch, dass dieser Code nur einen Thread erstellt, sodass die maximal mögliche Beschleunigung zwei beträgt, wenn er auf vier Prozessoren ausgeführt wird.
  
  
• 00:35:00 In diesem Abschnitt des Videos werden die Probleme mit Pthreads und dem Code für die Fibonacci-Folge besprochen. Der hohe Aufwand zum Erstellen eines Threads führt zu einer grobkörnigen Parallelität, und das Problem der Skalierbarkeit besteht darin, dass die beiden Kerne nicht die gleiche Menge an Arbeit leisten. Dem Code mangelt es auch an Modularität, da die Fibonacci-Logik nicht gut in einer Funktion gekapselt ist, was die Wartung und Änderung erschwert. Der Code wird auch durch das Marshalling von Argumenten kompliziert, was dem Schreiben von Code in Assembler ähnelt. Das Video stellt dann Threading Building Blocks (TBB) vor, eine Bibliothek, die von Intel entwickelt wurde, um eine Lösung für diese Probleme bereitzustellen.
  
  
• 00:40:00 In diesem Abschnitt behandelt das Video die Verwendung der Intel Thread Building Blocks (TBB)-Bibliothek, einer C++-Bibliothek, die es Programmierern ermöglicht, native Threads und einen arbeitsraubenden Algorithmus zu verwenden, ohne sich direkt mit Threads befassen zu müssen. Durch die Angabe von Tasks verteilt TBB die Last auf Threads, wodurch Code einfacher zu schreiben ist und eine bessere Leistung als bei der Verwendung von POSIX-Threads erzielt wird. Das Video zeigt ein Beispiel für die Implementierung eines Fibonacci-Programms mit TBB und demonstriert, wie es rekursiv untergeordnete Aufgaben erstellt, was mehr Parallelität und Skalierbarkeit über mehrere Prozessoren hinweg ermöglicht. TBB bietet auch Vorlagen für Schleifenparallelität, Datenaggregation und Software-Pipelining sowie gleichzeitige Containerklassen für den sicheren gleichzeitigen Zugriff auf gemeinsam genutzte Daten.
  
  
• 00:45:00 In diesem Abschnitt stellt der Referent zwei linguistische Lösungen für das Nebenläufigkeitsproblem vor: OpenMP und Silk. OpenMP ist eine Spezifikation, die linguistische Erweiterungen für C und C++ sowie Fortran bereitstellt und mithilfe von Compiler-Pragmas angibt, welche Codeteile parallel ausgeführt werden sollen. Es unterstützt Schleifenparallelität, Aufgabenparallelität und Pipelineparallelität und verfügt über viele Planungs- und Datenteilungsanweisungen sowie Synchronisationskonstrukte. Der Referent liefert ein Beispiel für die Implementierung von Fibonacci in OpenMP, das einfacher und performanter ist als die Verwendung von Pthreads oder TBB. OpenMP ist eine beliebte Lösung zum Schreiben paralleler Programme, da es viele Funktionen bietet und den Code vereinfacht.
  
  
• 00:50:00 In diesem Abschnitt erörtert der Redner die Silk-Programmierplattform, die Joint- und Vektorparallelität unterstützt und einen nachweislich effizienten Work-Stealing-Scheduler enthält. Das Programm verfügt außerdem über eine Hyperobjektbibliothek zum Parallelisieren von Code mit globalen Variablen und enthält Programmiertools wie einen Seidenbildschirm-Race-Detektor und einen Skalierbarkeitsanalysator namens Silk View. Der Referent merkt auch an, dass sie zwar kein Silk Plus in der Klasse verwenden werden, aber einen besseren Compiler namens Taper LLVM verwenden werden, der im Vergleich zu seinem Basiscompiler besseren Code produziert als alle anderen Implementierungen von Silk da draußen.
  
  
• 00:55:00 In diesem Abschnitt wird die Verwendung von Silk-Spawn- und Silk-Sync-Anweisungen zum Aktivieren der parallelen Ausführung anhand von Beispielen erläutert. Das erste Beispiel ist der Salt Coat für Fibonacci, der Silk-Spawn- und Silk-Sync-Anweisungen enthält, die darauf hindeuten, dass fib von n-1 parallel zu der aufrufenden Funktion ausgeführt werden kann, während fib von n-2 ausgeführt wird. Das Laufzeitsystem entscheidet jedoch, ob diese Tasks parallel ausgeführt werden oder nicht. Ein weiteres diskutiertes Beispiel ist die Schleifenparallelität, bei der die Silk for-Anweisung verwendet wird, um eine for-Schleife parallel auszuführen, wobei der Compiler den Iterationsraum rekursiv in zwei Hälften teilt und Silk Spawn- und Silk Sync-Anweisungen verwendet, bis der Bereich zu klein wird, um parallel ausgeführt zu werden. Es ist wichtig sicherzustellen, dass die Iterationen unabhängig sind, um korrekte Ergebnisse zu erzielen, und die Verwendung von Silk für fügt einige zusätzliche Overheads hinzu.
  
  
• 01:00:00 In diesem Abschnitt behandelt das Video die Verwendung von verschachtelten Seiden-for-Schleifen und die Details zum Generieren von Assembler-Code mithilfe eines Flags im Clang-Compiler. Der Beispielcode für eine Summierung von Werten unter Verwendung einer Seiden-for-Schleife wirft das Problem des Bestimmungswettlaufs auf, wenn mehrere Prozessoren in dieselbe Speicherstelle schreiben. Silk geht dieses Problem durch die Verwendung von Reducern an, bei denen es sich um Hyperobjekte handelt, die die Additionsfunktion für eine bestimmte Variable handhaben, während sie die Reducer-Makros registrieren und deren Registrierung aufheben. Dies ist eine Möglichkeit, das Reduktionsproblem zu lösen, das bei der Multicore-Programmierung auftreten kann, wobei viele andere Reduktionsoperatoren ebenfalls zur Verfügung stehen.
  
  
• 01:05:00 In diesem Abschnitt erörtert der Redner Reduzierer in Silk – algebraische Strukturen, die eine assoziative binäre Operation und ein Identitätselement haben. Silk verfügt über mehrere vordefinierte Reduzierer, darunter Addition, Multiplikation, Min, Max und XOR, und Sie können Ihren eigenen Reduzierer definieren. Einer der Vorteile von Silk ist, dass es immer eine gültige serielle Interpretation des Programms gibt, was das Debuggen erleichtert, und dass es über einen Laufzeitplaner verfügt, der das Programm überwacht und auf verfügbare Prozessorkerne abbildet, wobei ein arbeitsraubender Planungsalgorithmus verwendet wird, um Aufgaben auszugleichen gleichmäßig. Im Gegensatz zu anderen Parallelplattformen ist der Planer von Silk theoretisch effizient.
  
  
• 01:10:00 In diesem Abschnitt bietet der Referent einen allgemeinen Überblick über das Silk-Ökosystem für die Multicore-Programmierung, einschließlich der Kompilierung des Silk-Quellcodes, des Benchmarks für parallele und serielle Leistung und der Fehlerbehebung mit Tools wie Silk Sanitizer und Silk Skala. Sie betonen auch, wie wichtig es ist, das serielle Programm für die Leistung zu optimieren, und wie der Scheduler von Silk verschiedene Aufgaben während der Programmausführung handhaben kann. Darüber hinaus erklärt der Referent, wie Silk Scale die maximale Anzahl von Prozessoren bestimmen kann, die ein Code nutzen kann, was es zu einem nützlichen Werkzeug zur Analyse der Skalierbarkeit macht.
  
  
• 01:15:00 In diesem Abschnitt fasst der Referent die wichtigsten Erkenntnisse aus der Vorlesung über Multicore-Programmierung zusammen. Sie erklären, dass die meisten modernen Prozessoren mehrere Kerne haben, was es notwendig macht, parallele Programme für eine hohe Leistung zu schreiben. Das Schreiben solcher Programme kann jedoch schwierig sein, und hier kommt Silk ins Spiel. Dieses Tool abstrahiert Prozessorkerne vom Programmierer und übernimmt die Synchronisation, Kommunikationsprotokolle und den Lastausgleich. Der Referent erwähnt auch ein zukünftiges Projekt, bei dem Studenten ihren eigenen parallelen Bildschirmschoner mit Silk implementieren werden.

[MetaQuotes]

Vorlesung 7. Rassen und Parallelität

Vorlesung 7. Rassen und Parallelismus

Das Video behandelt eine Reihe von Themen im Zusammenhang mit Rassen, Parallelität und Berechnungs-Dags in der Silk-Programmierung. Zu den wichtigsten behandelten Konzepten gehören die Spawn- und Sync-Anweisungen für die gleichzeitige Ausführung, die Bedeutung der Vermeidung von Race-Conditions und die Verwendung des Race-Detektors von Silk zu ihrer Identifizierung. Das Video behandelt auch das Amdahlsche Gesetz, das Arbeitsgesetz und das Span-Gesetz als Möglichkeiten zur Quantifizierung des Umfangs der Parallelität in einem Programm sowie Möglichkeiten zur Analyse der Arbeit und der Spanne von Berechnungen. Die potenzielle Beschleunigung und Parallelität paralleler Sortieralgorithmen und das Konzept der Scheduling-Theorie werden ebenfalls diskutiert, wobei der Schwerpunkt auf dem Theorem des Greedy-Schedulers liegt. Insgesamt bietet das Video wertvolle Einblicke in das Verständnis und die Optimierung der Programmleistung in der Silk-Programmierung.

Das Video erklärt die Folgeerscheinungen der Greedy-Scheduler-Grenze, die im Wesentlichen besagt, dass jeder Greedy-Scheduler eine nahezu perfekte lineare Beschleunigung erreicht, solange T1/Tinfinity größer oder gleich P^2 ist. Der Silk-Scheduler, der einen arbeitsraubenden Scheduler verwendet, kann eine nahezu perfekte lineare Beschleunigung erreichen, solange die Anzahl der Prozessoren viel geringer ist als bei T1/Tinfinity. Das Silk-Laufzeitsystem funktioniert, indem es ein Arbeitsdeck mit fertigen Strängen verwaltet und den Boden des Decks wie einen Stapel manipuliert. Das Video behandelt auch den Cactus Stack, der mehrere Ansichten von Stacks parallel ermöglicht und parallele Funktionsaufrufe ermöglicht. Die Obergrenze des für die P-Prozessorausführung erforderlichen Stapelspeicherplatzes ist oft viel lockerer als die tatsächlich benötigte Menge, da nicht jeder Prozessor jedes Mal, wenn er Arbeit stiehlt, den Berechnungsgraphen ganz nach unten gehen muss.

• 00:00:00 In diesem Abschnitt führt der Ausbilder in das Thema Rassen und Parallelität in Silk ein, das für die bevorstehende Hausaufgabe und das Projekt wichtig sein wird. Die Grundlagen der Spawn- und Sync-Anweisungen von Silk werden wiederholt, die eine gleichzeitige Ausführung von übergeordneten und untergeordneten Funktionen ermöglichen. Der Ausbilder betont auch, wie wichtig es ist, sich mit Mitgliedern der MIT-Politik zu treffen und Race Conditions im Code zu vermeiden, die zu katastrophalen Folgen führen können, wie bei früheren Beispielen zu sehen ist. Die am schwierigsten zu findenden Rennfehler sind diejenigen, die katastrophale Ereignisse verursacht haben, und herkömmliche Tests sind oft nicht effektiv. Silk bietet ein Tool, mit dem potenzielle Race-Bugs im Code identifiziert werden können.
  
  
• 00:05:00 In diesem Abschnitt erklärt das Video, dass Races einer der am schwierigsten zu findenden Fehler für Entwickler sind, da sie nur in seltenen Fällen auftreten können, wenn logisch parallele Codes auf denselben Speicherort zugreifen und mindestens einer einen Schreibvorgang registriert dazu. Als Beispiel zeigt das Video einen einfachen Code, der ein Abhängigkeitsdiagramm verwendet, um zu zeigen, dass der Race-Bug, der zwischen zwei parallelen Pfaden geteilt wird, nicht immer auftritt. Das Rennen findet statt, wenn beide Speicher an denselben Speicherort schreiben, was zu unterschiedlichen Ausgaben führen kann, je nachdem, welcher Ausführungspfad zuerst vollständig ausgeführt wird.
  
  
• 00:10:00 In diesem Abschnitt erläutert der Referent das Konzept der Determinationsrennen, die auftreten, wenn zwei Befehle auf denselben Speicherplatz zugreifen und mindestens einer der Befehle ein Schreibvorgang ist, was zu einem nicht deterministischen Verhalten im Programm führt. Der Referent gibt Tipps zur Vermeidung von Races, z. B. um sicherzustellen, dass Iterationen einer Silk for-Schleife unabhängig sind, und um sicherzustellen, dass der Code zwischen einer Silk spawn-Anweisung und der entsprechenden Silk sync-Anweisung ebenfalls unabhängig ist. Der Sprecher weist auch darauf hin, dass die Wortgröße der Maschine eine Rolle spielt und dass beim Lesen und Schreiben in gepackte Datenstrukturen, die nicht standardmäßige Typen verwenden, Vorsicht geboten ist.
  
  
• 00:15:00 In diesem Abschnitt behandelt das Video den „Race Detector“ der Silk-Plattform, der dabei helfen kann, potentielle Race Conditions in einem Programm zu identifizieren. Durch die Verwendung des Flags „-f sanitized equal to silk“, um ein instrumentiertes Programm zu generieren, kann Silk anstößige Rassen melden und lokalisieren, was beim Debuggen von Code hilft. Das Video erklärt auch das Konzept der Parallelität und wie das Silk-Ausführungsmodell Berechnungsdiagramme verwendet, um die Entfaltung der Berechnung während der Ausführung zu veranschaulichen. Es ist wichtig, diese Konzepte zu verstehen, wenn Sie versuchen, die Programmleistung zu optimieren und zu verbessern.
  
  
• 00:20:00 Arten von Scheitelpunkten im Berechnungs-Tag: der Anfangsstrang, Fortsetzungsstränge, Funktionsaufrufstränge und Endstränge. Der Anfangsstrang enthält die erste auszuführende Anweisung, und der Endstrang enthält die letzte im Programm ausgeführte Anweisung. Fortsetzungsstränge stellen die Fortsetzung einer Spawn-Operation dar, während Funktionsaufrufstränge die Ausführung eines Funktionsaufrufs darstellen. Es ist wichtig zu beachten, dass sich der Berechnungs-DAG während der Ausführung dynamisch entfaltet und den Prozessor nicht kennt, was bedeutet, dass das Laufzeitsystem herausfindet, wie Tasks zur Laufzeit Prozessoren zugeordnet werden. Zusammenfassend lässt sich sagen, dass der Berechnungs-Dag ein mächtiges Werkzeug ist, um die Parallelität und Nebenläufigkeit eines Programms zu verstehen.
  
  
• 00:25:00 In diesem Abschnitt lernen wir Berechnungsdaten kennen und wie sie zur Analyse der Parallelität in einem Programm verwendet werden können. Der Berechnungs-dag stellt die Abhängigkeiten zwischen verschiedenen Teilen des Programms dar und hat verschiedene Arten von Kanten, einschließlich Spawn-Kanten, Aufrufkanten, Rückgabekanten und Fortsetzungskanten. Es ist möglich, Rechendaten zu verwenden, um zu analysieren, wie viel Parallelität in einem Programm vorhanden ist, und wir verwenden das Gesetz von Amdahl, um die Menge an Parallelität zu quantifizieren. In dem bereitgestellten Beispiel gibt es weniger als sieben Knoten, die nacheinander ausgeführt werden müssen, was darauf hinweist, dass es einen gewissen Grad an Parallelität in der Berechnung gibt.
  
  
• 00:30:00 In diesem Abschnitt wird das Konzept des Amdahlschen Gesetzes eingeführt, um die maximal mögliche Beschleunigung bei der parallelen Verarbeitung zu bestimmen. Es wird festgestellt, dass der serielle Bruchteil des Programms 3/18 ist, was zu einer maximalen Beschleunigung von 6 führt. Während das Gesetz von Amdahl eine Obergrenze für die Parallelität bereitstellt, ist es in praktischen Fällen oft zu locker. Das Arbeitsgesetz und das Span-Gesetz werden als alternative Definitionen der Parallelität eingeführt, wobei das Arbeitsgesetz besagt, dass die Ausführungszeit auf P Prozessoren größer oder gleich der Arbeit des Programms geteilt durch P ist, und das Span-Gesetz besagt, dass die Ausführungszeit auf P Prozessoren ist mindestens die Ausführungszeit auf unendlich vielen Prozessoren. Diese Gesetze bieten in vielen Fällen bessere Obergrenzen für die maximale Beschleunigung als das Gesetz von Amdahl.
  
  
• 00:35:00 In diesem Abschnitt erläutert der Sprecher, wie die Arbeit zusammengestellt und die Mengen verschiedener Berechnungen überspannt werden. Sie erklären, dass beim Ausführen von zwei parallelen Berechnungen die Arbeit immer noch die Summe der Arbeit der einzelnen Berechnungen ist und die Spanne das Maximum der Spanne der einzelnen Berechnungen ist. Der Redner definiert auch die Beschleunigung auf P-Prozessoren und erörtert die sublineare, lineare und superlineare Beschleunigung. Sie stellen fest, dass die maximal mögliche Beschleunigung gleich der Parallelität der Berechnung ist, die dem durchschnittlichen Arbeitsaufwand pro Schritt entlang der Berechnung entspricht. Insgesamt bietet dieser Abschnitt einen Einblick in die Zusammensetzung von Berechnungen und wie man ihre Parallelität misst.
  
  
• 00:40:00 In diesem Abschnitt erläutert der Referent, wie die Arbeit und Spannweite von Berechnungen analysiert werden, um die maximale Parallelität zu berechnen, wobei Beispiele wie ein Berechnungs-DAG und ein paralleler Quicksort-Algorithmus verwendet werden. Der Referent stellt den Skalierbarkeitsanalysator Silk Scale vor, der Compilerinstrumente verwendet, um die serielle Ausführung eines Programms zu analysieren und Obergrenzen für die parallele Beschleunigung des Programms abzuleiten. Der Referent erwähnt auch, dass es mühsam sein kann, die Parallelität großer Berechnungen von Hand zu analysieren, aber Silk Scale kann dabei helfen.
  
  
• 00:45:00 In diesem Abschnitt erörtert das Video die Ergebnisse einer parallelen Berechnung und der Erstellung eines Diagramms, das die beobachtete Beschleunigung sowie die Grenzen der Spannweite und der Arbeitsgesetze zeigt. Das Diagramm zeigt, dass die maximale Beschleunigung etwa 5 beträgt, was darauf hinweist, dass die Parallelität im Programm gering ist. Die Analyse zeigt, dass der Engpass für die Parallelität die sequentielle Ausführung der Partitionsfunktion ist und die erwartete Arbeit und Spanne der parallelen Version von Quicksort in der Größenordnung von n log n liegt. Die maximal erreichbare Parallelität liegt in der Größenordnung von log log n, was nicht sehr hoch ist. Um die Parallelität zu erhöhen, muss die Partitionsfunktion parallelisiert werden.
  
  
• 00:50:00 In diesem Abschnitt erörtert der Referent die Bedeutung der Implementierung von Parallelität in Partitions- und Merge-Sortier-Algorithmen, um eine signifikante Beschleunigung zu erzielen. Parallele Versionen dieser Algorithmen haben eine Gesamtspanne, die mit log zum Quadrat n und eine hohe Parallelität von n über log n begrenzt ist. Darüber hinaus gibt es viele andere praktische parallele Algorithmen, die eine hohe Parallelität und eine Arbeitsgrenze aufweisen, die asymptotisch gleich der des entsprechenden sequentiellen Algorithmus ist. Der Referent stellt auch das Konzept der Scheduling-Theorie vor und erklärt, dass ein zentralisierter Scheduler Berechnungs-DAGs zur Laufzeit auf verfügbare Prozessoren abbilden kann, während bei der Silk-Programmierung ein verteilter Scheduler verwendet wird. Als Beispiel dient ein Greedy Scheduler, der bei jedem Schritt der Berechnung so viel wie möglich macht.
  
  
• 00:55:00 In diesem Abschnitt wird das Konzept eines Greedy Scheduler vorgestellt, der so viel Arbeit wie möglich im aktuellen Zeitschritt verrichtet, ohne an die Zukunft zu denken. Ein vollständiger Schritt, bei dem mindestens P Stränge fertig sind, und ein unvollständiger Schritt, bei dem weniger als P Stränge fertig sind, werden definiert. Das berühmte Theorem, das erstmals 1968 von Ron Graham gezeigt wurde, besagt, dass die von einem gierigen Planer erreichte Zeitgrenze kleiner oder gleich T1/P + T unendlich ist, wobei T1 die Arbeit und T unendlich die Spanne ist. Der Beweis für dieses Theorem wird erbracht, und es wird gezeigt, dass jeder Greedy-Scheduler innerhalb eines Faktors von zwei die optimale Laufzeit erreicht.
  
  
• 01:00:00 In diesem Abschnitt erklärt das Video die Folgeerscheinungen des Greedy Scheduler Bound, der innerhalb eines Faktors von zwei des optimalen Schedulers erreicht. Die Folgerung besagt, dass jeder Greedy-Scheduler eine nahezu perfekte lineare Beschleunigung erreicht, wenn T1/Tinfinity größer oder gleich P^2 ist, wobei T1/P mal Tinfinity das Maß an Parallelität in der Berechnung im Vergleich zur Anzahl der Prozessoren misst verfügbar. Der Seiden-Scheduler verwendet einen Arbeitsdiebstahl-Scheduler, der eine erwartete Laufzeit von TP gleich T1/P plus der Ordnung T unendlich hat, mit einem großen O vor dem T unendlich, um den Overhead der Planung zu berücksichtigen, und kann nahezu perfekte lineare Beschleunigung, solange die Anzahl der Prozessoren viel geringer ist als bei T1/Tinfinity. Das Silk-Laufzeitsystem funktioniert, indem es ein Arbeitsdeck mit fertigen Strängen verwaltet und den Boden des Decks wie einen Stapel manipuliert. Die Instrumentierung in der Silk Scale ermöglicht das Messen von Arbeits- und Spannentermen, um die Parallelität im Programm zu bestimmen.
  
  
• 01:05:00 In diesem Abschnitt erörtert der Referent das Konzept von Spawning und Parallelität in Prozessoren. Sie erklären, dass ein Prozessor, wenn er eine Funktion aufruft, den Frame dieser Funktion an das untere Ende seines Stapels legt und Frames an das untere Ende des Stapels erzeugen kann. Mehrere Prozesse können parallel ablaufen, und Rückgaben können von Spawns und Calls erfolgen. Wenn den Arbeitern die Arbeit ausgeht, stehlen sie von der Oberseite des Decks eines anderen Prozessors. Das berühmte Theorem besagt, dass Arbeiter sehr selten stehlen, was zu einer nahezu linearen Beschleunigung führt. Der Redner merkt auch an, dass Silk die Regeln von C für Zeiger unterstützt, bei denen ein Zeiger auf einen Stapelplatz von einem Elternteil an ein Kind weitergegeben werden kann, aber nicht von einem Kind an einen Elternteil.
  
  
• 01:10:00 In diesem Abschnitt des Videos bespricht der Sprecher den Cactus Stack, den Stack, der von einer Aufgabe im Ancestor-Berechnungsgraphen eines Silk-Programms gesehen werden kann. Dieser Stapel ermöglicht mehrere parallele Ansichten von Stapeln, was parallele Funktionsaufrufe ermöglicht. Der Referent erklärt, dass der von einem Silk-Programm benötigte Stack-Speicherplatz ermittelt werden kann, indem der für eine serielle Ausführung des Programms erforderliche Stack-Speicherplatz (S sub 1) mit der Anzahl der verwendeten Prozessoren (P) multipliziert wird (S Teil P ≤ P x S Teil 1). Der Referent liefert einen Beweis dieses Konzepts auf hoher Ebene und stellt fest, dass die Obergrenze des für die Ausführung von P-Prozessoren erforderlichen Stapelspeicherplatzes oft viel lockerer ist als die tatsächlich benötigte Menge, da nicht jeder Prozessor den Berechnungsgraphen ganz nach unten gehen muss Mal stiehlt es Arbeit.

[MetaQuotes]

Vorlesung 8. Analyse von Multithread-Algorithmen

Vorlesung 8. Analyse von Multithread-Algorithmen

In diesem Video wird die Hauptmethode zum Analysieren von Teile-und-Herrsche-Wiederholungen erörtert und auf Multithread-Algorithmen angewendet, indem die logarithmische Basis B von n mit der logarithmischen Basis B von A mit F von N verglichen wird, um ihr Wachstum in n und die erforderliche Arbeit zu bestimmen. Das Video präsentiert einen Spickzettel mit Lösungen für grundlegende Multithread-Algorithmen und behandelt Themen wie Arbeits- und Span-Analyse, Arbeitseffizienz und Überwindung von Gemeinkosten durch Optimierung der Korngröße. Die Bedeutung von Empathie bei der Kommunikation technischer Themen wird betont, und das Konzept einer DAG wird als Mittel zum Ausgleich von Arbeit und Spannweite eingeführt, um die Parallelität zu erhöhen und die Laufzeit zu verringern.

Das Video behandelt auch die Analyse von Multithread-Algorithmen, wobei der Schwerpunkt auf Arbeit und Spanne liegt, und wie man die Parallelität maximiert und gleichzeitig die Spanne minimiert, um eine nahezu perfekte lineare Beschleunigung zu erreichen. Der Redner schlägt einen Teile-und-Herrsche-Ansatz für Multithread-Algorithmen vor, bei dem die Anzahl der Aufgaben, die den Threads zugewiesen werden, ausreichend groß ist, und warnt davor, zahlreiche kleine Aufgaben aufgrund von Planungs-Overheads hervorzubringen. Der vorgestellte Beispielcode enthält einen effizienten und einen miesen. Der Redner erörtert auch, wie Untermatrizen in der zweidimensionalen Codierung und Indizierung dargestellt werden, und betont die Verwendung von „Einschränken“ im Multiplikationscode „Teile und Herrsche“ der Matrix, um die Leistung zu verbessern.

• 00:00:00 In diesem Abschnitt erinnert der Kursleiter die Schüler zunächst an „Teile und Herrsche“-Wiederholungen und die allgemeine Methode zu deren Lösung, die Master-Methode genannt wird. Die Methode befasst sich mit Wiederholungen und ihrer Form T(n) = a*T(n/B) + F(n), wobei a eine Konstante, B der Aufteilungsfaktor und F(n) der Gesamtarbeitsaufwand ist um das Problem in Teilprobleme der Größe n/B zu zerlegen. Die Schüler werden an den Rekursionsbaum erinnert und wie sich jede Ebene in Teilprobleme der Größe n/B aufteilt, sie addieren die Laufzeit über die Zeilen hinweg, berechnen die Höhe des Baums und multiplizieren sie mit der Anzahl der Teilprobleme auf jeder Ebene (a ^k). Schließlich berechnen die Schüler, dass n^log Basis B von A die Gesamtlaufzeit des Algorithmus ist.
  
  
• 00:05:00 In diesem Abschnitt erklärt der Referent, wie man das Wachstum von n und den erforderlichen Arbeitsaufwand bei der Bewertung von Multithread-Algorithmen bestimmt. Der Schlüssel besteht darin, die logarithmische Basis B von n mit der logarithmischen Basis B von A mit F von N zu vergleichen. Der Sprecher behandelt drei mögliche Fälle, wobei der erste der Fall ist, wenn die logarithmische Basis B n viel größer als F von n ist. In diesem Fall befindet sich der konstante Bruchteil des Gewichts in den Blättern, was dazu führt, dass die Antwort n zur logarithmischen Basis B von A ist. Der zweite Fall liegt vor, wenn die logarithmische Basis B n ungefähr gleich F von n ist. Dazu heften Sie einen zusätzlichen Baumstamm an, und die Antwort ist n hoch logarithmisch Basis B eines logarithmisch hoch k plus 1 von n. Der dritte Fall schließlich ist, wenn an zum Loggen der Basis B viel kleiner als F von N ist, was bedeutet, dass F eine Regelmäßigkeitsbedingung erfüllen muss, die von allen Funktionen erfüllt wird, die sie betrachten werden, wie Polynome und Logarithmen.
  
  
• 00:10:00 In diesem Abschnitt stellt der Referent einen Spickzettel mit grundlegenden Lösungen für Multithread-Algorithmen vor, die üblicherweise in der Informatik verwendet werden. Der erste Algorithmus, T(n) = T(n/2) + n, hat eine Lösung von Θ(n^2), da er unter Fall eins fällt. Der zweite Algorithmus, T(n) = T(n/2) + n^2logn, hat eine Lösung von Θ(n^2logn), da er unter Fall zwei mit k = 0 fällt. Für den dritten Algorithmus, T(n) = T(n/2) + n^2, die Lösung ist Θ(n^2), da sie unter Fall eins fällt. Der vierte Algorithmus, T(n) = 2T(n/2) - n, ist knifflig, da er nicht unter die Master-Methode fällt und eine Lösung von Θ(n^2loglogn) hat.
  
  
• 00:15:00 In diesem Abschnitt erörtert der Referent die Aqua Bazi-Methode und wie sie komplizierter ist als die Master-Methode, die für die Analyse der meisten Programme ausreicht. Sie liefern dann ein Beispiel für eine parallele Schleife mit direktem Matrix-Transponierungscode, bei der die äußere Schleife parallelisiert ist. Der Referent betont die Bedeutung der korrekten Definition des Iterationsraums und des Lastausgleichs für eine effiziente Parallelverarbeitung. Sie erklären auch, wie Schleifen vom Open-Silk-Compiler und -Laufzeitsystem implementiert werden.
  
  
• 00:20:00 In diesem Abschnitt beschreibt der Sprecher ein rekursives Programm für eine Schleife, das „Divide and Conquer“ verwendet, um die Schleife in zwei Teile aufzuteilen und sich auf jeder Seite rekursiv selbst aufzurufen, bis eine Iteration mit einem Element erreicht wird. Die Arbeit dieser Berechnung wird in Bezug auf Arbeit und Spannweite analysiert, wobei die Blattarbeit die Ordnung n zum Quadrat und der obere Teil Thetan n ist, da jede Ebene von den Blättern bis zur Wurzel nur n Knoten hat. Das offene Silk-Laufzeitsystem hat kein Schleifenprimitiv, daher werden Schleifen effektiv parallel in diesen Teile-und-Herrsche-Ansatz übersetzt.
  
  
• 00:25:00 In diesem Abschnitt erörtert der Referent die Arbeits- und Span-Analyse eines Multithread-Algorithmus. Er erklärt, dass die Gesamtarbeit Θ(n²) ist, weil für jedes der n Blätter des vollständigen Binärbaums konstante Arbeit geleistet wird. Die Spanne der Schleifensteuerung ist log(n), was bedeutet, dass eine unendliche Anzahl von Prozessoren die Aufgabe in logarithmischer Zeit erledigen könnte. Da jedoch die Berechnung (n) eine lineare Komponente enthält, ist die Gesamtspanne Θ(n). Daher ist die Parallelität Θ(n), was für die meisten praktischen Systeme eine gute Größe ist. Der Referent untersucht dann das Szenario, in dem auch die innere Schleife parallelisiert wird, und diskutiert den daraus resultierenden Arbeitsaufwand.
  
  
• 00:30:00 In diesem Abschnitt des Videos diskutiert der Professor das Konzept der Arbeitseffizienz in parallelen Algorithmen. Das Parallelisieren von Algorithmen ändert nichts an der Arbeit, sollte aber hoffentlich die Spannweite der Berechnung verringern, um eine große Parallelität zu erreichen. Manchmal kann die Parallelisierung jedoch dazu führen, dass mehr Arbeit hinzugefügt wird, was problematisch sein kann, da es das Programm im Vergleich zum ursprünglichen Algorithmus verlangsamt. Arbeitseffiziente parallele Algorithmen sind das, was der Professor lehren möchte, da sie in der Lage sind, die Spanne zu reduzieren, um eine große Parallelität zu erreichen, ohne mehr Arbeit hinzuzufügen. Der Professor betont, wie wichtig es ist, im Lernprozess Fragen zu stellen und Fehler zu machen, da dies anderen helfen kann, die möglicherweise dieselben Fragen haben, aber Angst haben, sie zu stellen. Er ermutigt die Schüler, sich am Lernprozess zu beteiligen und sich daran zu beteiligen, auch wenn sie nicht zu den besten 10 % gehören.
  
  
• 00:35:00 In diesem Abschnitt wird die Bedeutung von Empathie in der Kommunikation bei technischen Themen betont. Der Professor ermutigt die Studenten, geduldig mit anderen in der Klasse zu sein, die möglicherweise nicht mit dem behandelten Material vertraut sind. Weiter zur Analyse von Multithread-Algorithmen wird ein Teile-und-Herrsche-Algorithmus für die Vektoraddition vorgestellt, und es wird festgestellt, dass die Parallelität n über log n ist. Die Beziehung zwischen Parallelität und der Anzahl der Prozessoren wird diskutiert, wobei der Professor betont, dass mehr Parallelität zwar besser erscheinen mag, aber nur bis zu einer bestimmten Schwelle von Vorteil ist.
  
  
• 00:40:00 In diesem Abschnitt erörtert der Sprecher die Optimierung eines Teils des Overheads in einem Multithread-Algorithmus, insbesondere des Overheads für Unterroutinenaufrufe. Sie führen das Konzept der „Korngröße“ ein, das dem Compiler suggeriert, dass es bis zu G Elemente pro Chunk an den Blättern des Teile-und-Herrsche-Prozesses gibt. Dies ermöglicht, dass der Unterroutinen-Overhead über G-Iterationen statt nur über eine amortisiert wird, was zu einer besseren Leistung führt. Wenn die Korngröße nicht angegeben ist, macht das System seine beste Schätzung, um den Overhead zu minimieren. Der Sprecher zerlegt die Variablen I, G und s, um die Arbeit in diesem Zusammenhang zu analysieren, und vergleicht sie mit der Arbeit im Originalcode ohne das parallele Kontrollzeug.
  
  
• 00:45:00 In diesem Abschnitt spricht der Sprecher über die Analyse von Multithread-Algorithmen und darüber, wie günstig die Schleifensteuerung auf einem modernen Out-of-Order-Prozessor ist. Sie betrachten die Spanne, d. h. die Zeit, die benötigt wird, um den Algorithmus mit einer unendlichen Anzahl von Prozessoren auszuführen, und diskutieren die Overhead-Kosten im Vergleich zu den Kosten der Iterationen. Der Sprecher zerlegt die Spannweite in Bezug auf die Anzahl der Blätter und die farbigen Operationen, die als „s“ bezeichnet werden und die an jedem von ihnen durchgeführt werden müssen. Sie beantworten auch Fragen zur Anzahl der internen Knoten in einem vollständigen Binärbaum und zu den Pfaden, die zur Berechnung der Spannweite verwendet werden.
  
  
• 00:50:00 In diesem Abschnitt erörtert der Referent die Analyse von Multithread-Algorithmen, insbesondere das Konzept eines DAG (gerichteter azyklischer Graph) und wie es den Pfad des Algorithmus beeinflusst. Sie betonen die Notwendigkeit der Unabhängigkeit zwischen verschiedenen Teilbäumen der DAG, um eine parallele Verarbeitung zu ermöglichen. Das Ziel ist es, die Arbeit und Spannweite des Algorithmus auszugleichen, da diese beiden Faktoren in entgegengesetzte Richtungen wirken. Der Schlüssel liegt darin, dass G (das Maß an Parallelität) viel größer ist als s über I (der sequentielle Teil des Algorithmus), was einen geringeren Overhead und eine schnellere Verarbeitung ermöglicht. Der Referent erwähnt auch eine Umsetzung dieses Konzepts, weist jedoch darauf hin, dass dies später in der Vortragsreihe diskutiert wird.
  
  
• 00:55:00 In diesem Abschnitt stellt der Sprecher eine Implementierung von Multithread-Algorithmen vor, die eine for-Schleife verwenden, um zwei Vektoren zu addieren. Die Schleife verwendet einen Operator namens V add , um eine serielle Vektoraddition durchzuführen, und die Schleife erzeugt Additionen in Gruppen von G unter Verwendung eines Vektors der Größe G. Unter der Annahme, dass G gleich eins ist, ist die Arbeit der Schleifen die Ordnung n, und die Spanne ist es auch Bestellung n. Die Parallelität wird gemessen, indem das Verhältnis von Arbeit zu Spanne genommen wird, das n dividiert durch n ist, was zu 1 vereinfacht. Der Referent betont, dass das Ziel der Analyse von Multithreading-Algorithmen darin besteht, die Parallelität zu erhöhen und die Spanne zu verringern, um die Laufzeit zu minimieren, und hebt die Technik hervor Strip Mining genannt, bei dem eine Schleife der Länge N durch eine doppelt verschachtelte Schleife ersetzt wird, um Berechnungen zu parallelisieren, als eine Möglichkeit, Multithread-Algorithmen zu verbessern.
  
  
• 01:00:00 In diesem Abschnitt analysiert der Referent die Leistung von Multithread-Algorithmen in Bezug auf Arbeit und Spannweite. Sie besprechen, wie die Spanne minimiert werden kann, um die Parallelität zu maximieren, da die Spanne im Nenner steht. Der Schlüssel liegt darin, zehnmal mehr Parallelität als Prozessoren zu erzeugen, wenn man eine nahezu perfekte lineare Beschleunigung erreichen möchte. Der Redner schlägt auch vor, etwas Parallelität einzutauschen, um den Arbeitsaufwand bei Bedarf zu reduzieren. Sie regen dazu an, mit der Korngröße herumzuspielen, solange eine ausreichende Parallelität erhalten bleibt.
  
  
• 01:05:00 In diesem Abschnitt diskutiert der Redner die Verwendung von Teile-und-Herrsche-Strategien in Multithread-Algorithmen und rät davon ab, zahlreiche kleine Aufgaben nacheinander zu erzeugen, es sei denn, sie sind auf wenige Aufgaben aufgeteilt, in welchem Fall der Overhead ist gut. Im Allgemeinen sollte es einen Teile-und-Herrsche-Ansatz geben, bei dem die Anzahl der Aufgaben, die den Threads zugewiesen werden, ausreichend groß ist. Der Referent mahnt, auf Scheduling-Overheads zu achten und schlägt vor, statt der inneren Loops, die mehr Overhead haben, die äußere Schleife zu parallelisieren. Die hier vorgestellten Beispielcodes zeigen einen effizienten, bei dem die Planung nur einmal erfolgt, und einen miesen, bei dem der Overhead n-mal auftritt. Die Matrixmultiplikation wird als Beispiel für einen Multithread-Algorithmus verwendet, der eine Teile-und-Herrsche-Strategie verwendet, um n-mal-n-Matrizen zu multiplizieren, indem 8-Multiplikationen von n über 2-mal n-über-2-Matrizen durchgeführt werden und dann zwei n-mal-n-Matrizen addiert werden.
  
  
• 01:10:00 In diesem Abschnitt erörtert der Referent, wie Untermatrizen bei der zweidimensionalen Codierung und Indizierung dargestellt werden, insbesondere in Zeilen-Dur- und Spalten-Dur-Reihenfolge für Sprachen wie C und Fortran. Die Idee ist, dass jede zweidimensionale Matrix als eindimensionale Matrix indiziert werden kann, und beim Umgang mit Untermatrizen muss man die Anzahl der Zeilen und die Länge der langen Matrix hinzufügen, um zu wissen, wo sich das IJ-Element befindet. Darüber hinaus ist es bei der Implementierung von Teile und herrsche entscheidend, die Startecken jeder der vier Untermatrizen zu kennen. Letztendlich betont der Redner die Verwendung von „restrict“ im Division-and-Conquer-Matrix-Multiplikationscode, um dem Compiler mitzuteilen, für welche Elemente ein Alias verwendet werden kann oder nicht.
  
  
• 01:15:00 In diesem Abschnitt erörtert der Referent einen Multithread-Algorithmus für die Matrixmultiplikation. Der Algorithmus basiert auf einer rekursiven Unterteilung der Matrizen in kleinere Untermatrizen, wobei jede Untermatrix rekursiv multipliziert wird, um das Endergebnis zu erhalten. Der Referent hebt einen kleinen Trick hervor, um schnell festzustellen, ob n eine Zweierpotenz ist, und verwendet ein Makro, um die Indizierung der Matrizen zu vereinfachen. Der Algorithmus weist eine hohe Parallelität auf, die reduziert werden kann, um die Leistung zu verbessern. Andere ähnliche Algorithmen werden ebenfalls erwähnt.

[MetaQuotes]

Vorlesung 9. Was Compiler können und was nicht

Vorlesung 9. Was Compiler können und was nicht

In diesem Video wird anhand verschiedener Beispiele erläutert, wie Compiler Code optimieren können. Es erklärt, wie Compiler unnötige Speicher- und Speicherreferenzen eliminieren und Schleifen optimieren können, um die Leistung zu verbessern.

Dieses Video erklärt auch das Konzept der Compiler-Optimierungsdurchläufe und wie sie zur Verbesserung der Codeleistung verwendet werden können. Außerdem werden die Einschränkungen von Compilern erörtert, insbesondere in Bezug auf die Vektorisierung. Compiler können Code nur vektorisieren, wenn sie feststellen können, dass die Zeiger im Code keinen Alias verwenden. Wenn die Zeiger einen Alias verwenden, kann der Compiler den Code nicht vektorisieren. Als Programmierer können Sie dem Compiler helfen, indem Sie Ihre Zeiger mit Anmerkungen versehen, um mehr Informationen über ihre Verwendung bereitzustellen.

• 00:00:00 In diesem Vortrag diskutiert Tao Schardl, was Compiler können und was nicht. Er erklärt, dass das Studium der Compiler-Optimierung Entwicklern helfen kann, zu verstehen, wie man Code schreibt, der Optimierungen nutzt, und wie man die manuelle Optimierung von Code vermeidet, den der Compiler bereits optimieren kann.
  
  
• 00:05:00 Der Compiler ist ein großes Stück Software und kann beim Debuggen absolut hilfreich sein, wenn der Compiler selbst Fehler aufweist. Es hilft zu verstehen, wo der Compiler möglicherweise einen Fehler gemacht hat oder wo der Compiler einfach nicht das getan hat, was Sie für möglich hielten.
  
  
• 00:10:00 Der Compiler kann viele Optimierungen vornehmen, aber es gibt einige Dinge, die er nicht kann. Beispielsweise kann es nicht immer einen schnellen Pfad erstellen oder Schleifen optimieren.
  
  
• 00:15:00 Der Compiler kann viel tun, um Code zu optimieren, aber es gibt einige Dinge, die er nicht gut kann. Ein Beispiel sind Datenstrukturen – der Compiler kennt sie nicht so gut wie Funktionen. Eine andere sind Schleifen - der Compiler kann einige Optimierungen an ihnen vornehmen, aber es gibt Einschränkungen.
  
  
• 00:20:00 Dieses YouTube-Video erklärt, wie Compiler durch einfache Operationen komplexere ersetzen können. Um beispielsweise eine Divisionsoperation zu ersetzen, kann ein Compiler mit einer magischen Zahl multiplizieren und das Ergebnis dann verschieben. In diesem Video wird auch erklärt, wie der Adressrechner funktioniert.
  
  
• 00:25:00 Das Video erläutert, wie Compiler Code optimieren können, am Beispiel einer einfachen „Vex-Scale“-Funktion. Der Code wird zuerst ohne Optimierungen und dann mit verschiedenen angewendeten Optimierungen angezeigt. Die gezeigten Optimierungen umfassen die Reduzierung der Anzahl von Anweisungen, die Verwendung von Vektoranweisungen und die Verwendung von magischen Zahlen.
  
  
• 00:30:00 In diesem Video wird erläutert, wie Compiler Code optimieren können, indem sie unnötige Speicheroperationen eliminieren. Insbesondere zeigt es, wie ein Compiler eine Funktion optimieren kann, die zwei Skalarwerte multipliziert, indem die Notwendigkeit entfällt, die Werte im Speicher zu speichern. Schließlich zeigt es, wie ein Compiler eine Funktion optimieren kann, die auf einer Struktur arbeitet, indem er die Notwendigkeit beseitigt, die Struktur im Speicher zu speichern.
  
  
• 00:35:00 In diesem YouTube-Video erklärt der Referent, wie Compiler Code optimieren können, indem sie unnötige Speicher- und Speicherreferenzen eliminieren. Er verwendet das Beispiel einer Struktur mit mehreren Feldern und demonstriert, wie der Compiler den Code optimieren kann, indem er die Mathematik der Adressberechnungen sorgfältig analysiert. Indem er versteht, was jede Anweisung tut, kann der Compiler den Code optimieren und unnötige Operationen entfernen.
  
  
• 00:40:00 Der Compiler arbeitet hart daran, Datenstrukturen und Skalarwerte zu transformieren, um so viel wie möglich nur innerhalb von Registern zu speichern und möglichst keine lokale Speicherung zu verwenden. Bei Funktionsaufrufen sieht der Compiler die Aufrufanweisung und den Code für die aufgerufene Funktion. Es versucht dann, die Funktion im obigen Code noch schneller zu machen.
  
  
• 00:45:00 Der Compiler kann Code einbetten, um Overhead für Funktionsaufrufe zu vermeiden, und er kann Code auch optimieren, indem unnötige Operationen entfernt werden.
  
  
• 00:50:00 In diesem YouTube-Video erklärt der Sprecher, dass es drei Hauptgründe gibt, warum ein Compiler eine Funktion möglicherweise nicht einbettet: wenn die Funktion rekursiv ist, wenn sich die Funktion in einer anderen Kompilierungseinheit befindet oder wenn die Funktion erweitert werden könnte Codegröße und beeinträchtigte Leistung. Der Referent gibt auch einige Tipps zur Steuerung des Funktions-Inlinings in eigenen Programmen.
  
  
• 00:55:00 Dieses Video zeigt, wie Compiler Schleifen optimieren können, um Programme schneller laufen zu lassen. Code-Heben oder schleifeninvariante Codebewegung ist eine Optimierung, die verwendet werden kann, um die Leistung zu verbessern.
  
  
• 01:00:00 Der Compiler kann Code optimieren, indem er eine Folge von Transformationsdurchläufen durchführt. Diese Durchgänge sollen Eigenschaften wie identische Adressberechnungen finden und durch effizienteren Code ersetzen.
  
  
• 01:05:00 Der Compiler kann diese Schleife vektorisieren, obwohl er nicht weiß, ob sich die Adressen von „x“ und „y“ überschneiden. Dies liegt daran, dass die Struktur des kompilierten Codes komplizierter ist als die zweizeilige Funktion, die als Eingabe angegeben wurde.
  
  
• 01:10:00 Dieses YouTube-Video erklärt, was Compiler können und was nicht. Compiler können Code vektorisieren, wenn der Code keine Schleifen enthält. Wenn der Code jedoch Schleifen enthält, kann der Compiler den Code nur vektorisieren, wenn die Schleife voller Vektoroperationen ist. Wenn die Schleife nicht voll von Vektoroperationen ist, kann der Compiler den Code nicht vektorisieren.
  
  
• 01:15:00 Die Frage, ob ein Compiler Code vektorisieren kann oder nicht, ist schwierig, da dies von einer Reihe von Faktoren abhängt. Insbesondere muss der Compiler in der Lage sein, zu bestimmen, ob zwei Zeiger Alias werden oder nicht, was eine schwierige Aufgabe sein kann. Als Programmierer können Sie dem Compiler helfen, indem Sie Ihre Zeiger mit Anmerkungen versehen, um mehr Informationen über ihre Verwendung bereitzustellen.

[MetaQuotes]

Vorlesung 10. Messung und Zeitmessung

Vorlesung 10. Messung und Zeitmessung

In diesem Video erörtern die Referenten verschiedene Aspekte der Messung und des Timings in der Datenverarbeitung, einschließlich externer Faktoren, die die Genauigkeit beeinträchtigen können. Sie betonen die Notwendigkeit von Modellen und einem klaren Verständnis der Daten, die Verringerung der Varianz zur Kompensation von Fehlern und die Verwendung geeigneter Timing-Aufrufe zur Gewährleistung der Zuverlässigkeit. Sie diskutieren auch Herausforderungen bei der genauen Messung der Softwareleistung, wie z. B. das Potenzgesetz und nicht deterministische Faktoren, und heben Tools wie Leistungsmodellierung, Timing-Aufrufe, Hardwarezähler und Simulatoren hervor. Schließlich warnen sie davor, sich auf ein einzelnes Tool zu verlassen, und empfehlen Triangulation und Anpassung als Techniken, um genaue Ergebnisse zu gewährleisten.

Der Referent erläutert die Bedeutung einer zuverlässigen Leistungsmessung im Performance Software Engineering. Er empfiehlt die Verwendung von Statistiken, um die Leistung genau zu messen, und erörtert verschiedene Arten von zusammenfassenden Statistiken wie den Mittelwert, die in verschiedenen Kontexten nützliche Leistungsmaße liefern können. Er weist darauf hin, dass das Verwenden des arithmetischen Mittels von Verhältnissen kein gültiger Ansatz ist, und schlägt vor, stattdessen das geometrische Mittel zu verwenden. Der Redner betont, wie wichtig es ist, beim Vergleichen von Programmen die richtige Methode zum Aggregieren von Daten zu wählen, und schlägt vor, die Statistik niedriger Ordnung, z. B. das Minimum oder 10 %, aus mehreren Läufen zu verwenden, um die Leistung genauer zu vergleichen. Der Redner erörtert auch verschiedene Methoden zum Messen und Vergleichen der Leistung, einschließlich Kopf-an-Kopf-Vergleich und Anpassung eines Modells zur Ableitung von Statistiken, warnt jedoch vor dem Problem der Überanpassung bei der Modellierung. Insgesamt betont das Video die Bedeutung einer zuverlässigen Leistungsmessung zur Verbesserung der Programmleistung.

• 00:00:00 In diesem Abschnitt diskutiert der Redner eine Studie zum Sortieren von Codes, die von einem seiner ehemaligen Studenten durchgeführt wurde. Der Code verwendet die Header-Datei time.h, um Zugriff auf die Clock Get Time-Routine für Timing-Messungen zu erhalten. Eine Sortierroutine wird zeitgesteuert, und die verstrichene Zeit wird berechnet und ausgedruckt. Die Grafik der gemessenen Laufzeiten zeigt, dass die Sortierroutine meist einem N log N-Wachstum folgt, aber die gemessenen Zeiten selbst für die größten Arrays langsam sind.
  
  
• 00:05:00 In diesem Abschnitt erörtert ein Professor die Bedeutung eines Modells für die beobachteten Daten. Er stellt ein Beispiel vor, bei dem die gemessenen Daten erheblich von den Erwartungen abweichen, und bittet die Schüler, mögliche Hypothesen für diese Abweichung vorzuschlagen. Während einige dachten, es könnte ein Problem mit dem Cache oder der Genauigkeit des Timings sein, weist der Professor darauf hin, dass auf dem Computer nicht zusammenhängende Prozesse ausgeführt werden könnten, die die Abweichung verursachen. In diesem Fall liegt das Problem bei der Mandantenfähigkeit, bei der die Maschine von mehr als einem Prozess gleichzeitig verwendet wird. Der Professor betont die Notwendigkeit von Qualitätsmessungen und ein klares Verständnis davon, was die Daten bedeuten.
  
  
• 00:10:00 In diesem Abschnitt erörtern die Referenten Messungen und Timing in der Computertechnik und wie externe Faktoren die Genauigkeit von Messungen beeinflussen können. Sie konzentrieren sich insbesondere darauf, wie Taktfrequenzänderungen aufgrund der Systemtemperatur und Energiespartechniken auftreten können, die die Messergebnisse erheblich beeinflussen können. Die Referenten stellen das Konzept der dynamischen Frequenz- und Spannungsskalierung vor, eine Technik zur Leistungsreduzierung durch Anpassung der Taktfrequenz und Spannung an Transistoren. Sie betonen, dass es entscheidend ist, externe Faktoren bei der Durchführung von Messungen zu berücksichtigen, um ungenaue Ergebnisse zu vermeiden.
  
  
• 00:15:00 In diesem Abschnitt erörtert der Referent die Herausforderungen bei der Messung der Softwareleistung aufgrund des von Elektroingenieuren verwendeten Potenzgesetzes. Das Potenzgesetz besagt, dass die Leistung gleich CV zum Quadrat F ist, wobei C die dynamische Kapazität, V die Versorgungsspannung und F die Taktfrequenz ist. Um Strom und Wärme zu reduzieren, kann man die Frequenz und Spannung reduzieren, was zu einer kubischen Reduzierung der Leistung führt. Dies stellt eine Herausforderung für die zuverlässige Messung der Softwareleistung dar, und der Redner schlägt vor, Systeme stillzulegen, indem ein Teil des Rauschens beseitigt wird, um genaue Messungen durchzuführen. Sie diskutieren auch Tools zur Messung der Softwareleistung, wie z. B. Leistungsmodellierung.
  
  
• 00:20:00 In diesem Abschnitt erörtert der Referent die Bedeutung der Reduzierung von Varianzen bei Messung und Timing, insbesondere im Zusammenhang mit Performance Engineering. Durch die Reduzierung der Variabilität ist es möglich, systematische und zufällige Messfehler zu kompensieren und weniger Versuche zum Vergleichen von Programmen zu erfordern. Der Redner weist auch auf verschiedene Ursachen für Schwankungen in Computersystemen hin, darunter unter anderem Hintergrundjobs, Interrupts und Thread-Platzierung. Schließlich betont er, wie wichtig es ist, sich zuerst auf die Verringerung der Varianz zu konzentrieren, bevor versucht wird, Änderungen am System vorzunehmen, da die Messung bei hoher Varianz zu unzuverlässigen Ergebnissen führen kann.
  
  
• 00:25:00 In diesem Abschnitt spricht der Referent über das Konzept des Hyper-Threading in Prozessoren und wie es zu ungenauen Messungen in Cloud-Systemen führen kann. Hyper-Threading führt zwei Befehlsströme durch eine Funktionseinheit aus, die wie zwei Prozessoren erscheinen, aber tatsächlich nur eine 20-prozentige Beschleunigung anstelle von zwei separaten Prozessoren bietet. Der Referent erörtert auch andere Techniken wie Turbo Boost und Stillsetzen eines Systems, die die Messergebnisse erheblich beeinflussen können. Durch das Abschalten von Hyper-Threading und Turbo Boost und das Stilllegen aller Dämonen konnten der Sprecher und seine Gruppe bemerkenswert zuverlässige Messungen erzielen, die weniger als 1 % langsamer als die Mindestlaufzeit waren.
  
  
• 00:30:00 In diesem Abschnitt spricht der Referent über verschiedene Faktoren, die den Determinismus eines Programms beeinflussen können, das auf moderner Hardware läuft. Es gibt zwar bestimmte Maßnahmen, die man ergreifen kann, um das Programm deterministischer zu machen, aber es ist unmöglich, die nicht-deterministischen Faktoren vollständig zu eliminieren. Die meisten nicht deterministischen Faktoren, die während der Programmausführung auftreten können, wie z. B. Caching, Interrupts, Threading und Verzweigungsvorhersage, sind deterministische Prozesse. Die Zufälligkeit in der Hardware liegt jedoch außerhalb der Kontrolle des Benutzers und kann zu einem Speicherfehler führen. Der Sprecher schlägt vor, dass die Codeausrichtung einen Unterschied im Programmdeterminismus bewirken kann und dass jede am Code vorgenommene Änderung eine Verschiebung der Cacheausrichtung bewirken kann, was den Determinismus des Programms beeinflusst.
  
  
• 00:35:00 In diesem Abschnitt erläutert der Referent, wie kleine Änderungen große Auswirkungen auf die Leistung eines Programms haben können. Beispielsweise kann das Einfügen eines Bytes dazu führen, dass alles danach linear beeinflusst wird, und das Ändern der Reihenfolge, in der dot o-Dateien in der Linker-Befehlszeile erscheinen, kann eine größere Wirkung haben, als zwischen -OH- und -O3 zu wechseln. Um diese Probleme anzugehen, erkennen Compiler das Problem und nehmen mehr Alignment vor. LLVM verfügt über Schalter, die alle Funktionen und Blöcke in einer Funktion ausrichten können, aber die Ausrichtung kann das Programm verlangsamen. Darüber hinaus kann der Name des Programms seine Geschwindigkeit beeinträchtigen, da der Name der ausführbaren Datei in einer Umgebungsvariablen landet, die auf dem Aufrufstapel landet.
  
  
• 00:40:00 In diesem Abschnitt erläutert der Referent verschiedene Tools und Methoden zum Messen der Softwareleistung, einschließlich externes Messen des Programms mit dem Befehl time, Einfügen von Timing-Aufrufen in das Programm mit clock get time oder anderen Methoden, Unterbrechen des Programms mit gdb um festzustellen, welche Routine die meiste Zeit in Anspruch nimmt, indem Hardware- und Betriebssystemunterstützung genutzt werden, wie sie im Perf-Toolset verwendet werden, oder um das Programm zu simulieren, um ein tieferes Verständnis zu erlangen, jedoch mit einer langsameren Geschwindigkeit. Der Referent erklärt den Unterschied zwischen verstrichener Zeit, Benutzerzeit und Systemzeit bei Verwendung des time-Befehls und wie sie aufgrund der Prozessorzuweisung möglicherweise nicht zur Gesamtzeit addiert werden.
  
  
• 00:45:00 In diesem Abschnitt erörtert der Redner die verschiedenen Arten von Timing und Messung, einschließlich Wanduhrzeit, im Benutzermodus verbrachte Prozessorzeit und im Kernel verbrachte Zeit. Der zur Verwendung empfohlene Timing-Aufruf ist Clock Get Time mit der Clock Monotonic-Option, die garantiert, niemals rückwärts zu laufen. Die Ausführung kann zwar eine nicht deterministische Zeitdauer in Anspruch nehmen, ist jedoch zuverlässiger als andere Timer wie RTIDTSC, die auf verschiedenen Kernen unterschiedliche Antworten geben und rückwärts laufen können. Der Sprecher warnt vor der Verwendung von get time of day.
  
  
• 00:50:00 In diesem Abschnitt erörtert der Referent verschiedene Möglichkeiten, Ereignisse in der Programmierung zu messen und zu timen, einschließlich der Verwendung von clock_gettime und der Messung mit dem Befehl time. Sie weisen darauf hin, dass sich Techniken im Laufe der Zeit ändern können und Ingenieure sich möglicherweise anpassen müssen. Der Referent schlägt auch vor, Code zu zufälligen Zeitpunkten als einfache Profilierungstechnik zu unterbrechen, und erwähnt, dass große Unternehmen wie Facebook diese Methode verwenden. Darüber hinaus stellt der Referent die Idee von Hardwarezählern und der Bibliothek livepFM4 vor, die den Zugriff auf diese Zähler pro Prozess ermöglicht. Sie betonen, dass ein Ingenieur nicht immer chirurgisch präzise Werkzeuge benötigt und dass manchmal ein einfaches Werkzeug für die Arbeit ausreichen kann.
  
  
• 00:55:00 In diesem Abschnitt erörtert der Referent die verschiedenen Methoden zum Sammeln von Messungen, einschließlich Hardwarezähler und Simulatoren. Sie weisen darauf hin, dass viele Hardwarezähler schlecht dokumentiert sind und dass einige Tools die Bandbreite time-sharen, wenn mehr als vier oder fünf Zähler verwendet werden. Simulatoren werden für ihre Wiederholbarkeit gelobt, modellieren jedoch möglicherweise nicht alles im Cache. Der Referent empfiehlt die Triangulation und die Verwendung von mindestens zwei Messungen, um die Genauigkeit sicherzustellen. Sie betonen auch die Bedeutung eines Leistungsmodells zur Führung der Dateninterpretation.
  
  
• 01:00:00 In diesem Abschnitt erläutert der Referent den Prozess des Performance-Software-Engineering, bei dem ein Programm genommen, Änderungen daran vorgenommen und seine Leistung gemessen wird, um ein schnelleres Programm zu erstellen. Eine zuverlässige Leistungsmessung ist jedoch unerlässlich, um kleine Änderungen vorzunehmen, die sich summieren, und genaue Schlussfolgerungen zu ziehen. Der Referent empfiehlt daher, mit Hilfe von Statistiken ein genaues Bild davon zu bekommen, was vor sich geht. Er bietet auch ein Rätsel an, bei dem es darum geht, die Rohleistung eines deterministischen Programms zu messen, und kommt zu dem Schluss, dass die Verwendung des Minimums der beste Weg ist, Rauschen zu unterdrücken und die zugrunde liegende Hardwareleistung des Programms zu bestimmen.
  
  
• 01:05:00 In diesem Abschnitt werden verschiedene Arten von zusammenfassenden Statistiken erörtert, einschließlich des Mittelwerts, der nützliche Leistungsmaße in verschiedenen Kontexten liefern kann. Bei der Bewertung von Webservern können die CPU-Auslastung und die Gesamtzeit für die Ausführung von Aufgaben mithilfe des arithmetischen Mittels gemessen werden, während die Uhrzeit und das Perzentilverhalten für die Optimierung der Anforderungserfüllung relevanter sein können. Bei der Zusammenfassung von Verhältnissen, z. B. beim Vergleich der Leistung von Programm A und B, ist die Verwendung des arithmetischen Mittels jedoch kein gültiger Ansatz, auch wenn dies häufig missbraucht wird. Dies liegt daran, dass der Mittelwert der Verhältnisse nicht mit dem Verhältnis selbst identisch ist, wie im Beispiel im Video gezeigt.
  
  
• 01:10:00 In diesem Abschnitt erörtert der Referent die Probleme beim Vergleich von Verhältnissen und Mittelwerten bei der Leistungsmessung. Sie zeigen, dass das Bilden des arithmetischen Mittels der Verhältnisse zu verdächtigen Ergebnissen führen kann und es besser ist, das geometrische Mittel zu verwenden. Darüber hinaus stellen sie fest, dass beim Vergleich von Raten das harmonische Mittel oft nützlich ist. Es wird betont, wie wichtig es ist, beim Vergleichen von Programmen die richtige Methode zum Aggregieren von Daten zu wählen, und der Redner schlägt vor, die Statistik niedriger Ordnung, wie z. B. das Minimum oder 10 %, aus mehreren Läufen zu verwenden, um die Leistung genauer zu vergleichen.
  
  
• 01:15:00 In diesem Abschnitt erörtert der Referent verschiedene Methoden zum Messen und Vergleichen von Leistung. Ein Ansatz besteht darin, die 10 % billigsten Optionen zu vergleichen und eine Rauschunterdrückung durchzuführen, um die Mittel zu vergleichen, obwohl dies möglicherweise keine schlüssigen Beweise liefert. Alternativ kann ein Kopf-an-Kopf-Vergleich zwischen A und B durchgeführt werden, um zu sehen, wer häufiger gewinnt. Dadurch kann die Nullhypothese getestet und der p-Wert berechnet werden, um festzustellen, ob die Abweichung signifikant ist. Diese Methode wird häufig in den Sozialwissenschaften verwendet und kann in lauten Umgebungen nützlich sein. Abschließend geht der Redner kurz auf die Idee ein, ein Modell anzupassen, um Statistiken abzuleiten, und diskutiert die Verwendung der Näherung der kleinsten Quadrate.
  
  
• 01:20:00 In diesem Abschnitt erörtert der Referent das Problem der Überanpassung bei der Modellierung und wie das Hinzufügen weiterer Basisfunktionen die Datenanpassung verbessern, aber auch zu einer Überanpassung führen kann. Die Lösung besteht darin, eine Basisfunktion zu entfernen und zu prüfen, ob sie die Qualität des Modells beeinträchtigt. Der Redner erwähnt auch Lord Kelvin, bekannt als der Guru des Messens, der erklärte, dass Messen Wissen bedeutet, und wenn man nicht messen kann, kann man sich nicht verbessern. Das Video endet damit, dass der Sprecher am Dienstag bei einem Quiz Glück wünscht.

[MetaQuotes]

Vorlesung 11. Speicherzuordnung

Vorlesung 11. Speicherzuordnung

Der Dozent erörtert in diesem Video die Speicherzuweisung, wobei sowohl die Speicherzuweisung als auch die Freigabe behandelt werden. Es werden unterschiedliche Arten der Speicherung angesprochen, darunter Stack und Heap sowie Zuweisungsschemata mit fester und variabler Größe. Externe Fragmentierung durch verteilte Speicherblöcke wird ebenfalls diskutiert, mit Lösungen wie freien Listen oder Bitmaps pro Plattenseite. Das Konzept der Garbage Collection wird ebenfalls eingeführt, einschließlich der Referenzzählung und der Einschränkungen dieses Algorithmus. Die Garbage-Collection-Prozeduren „markieren und fegen“ und „stoppen und kopieren“ werden ebenfalls erläutert, wobei der Schwerpunkt darauf liegt, wie letztere die Fragmentierung und das mögliche Korrektheitsproblem angeht, das durch Zeigeraktualisierungen verursacht wird. Das Video schließt mit Anmerkungen zur zeitlichen und räumlichen Komplexität des Stop-and-Copy-Algorithmus und seiner Eliminierung externer Fragmentierung.

Dieses Video behandelt verschiedene Themen im Zusammenhang mit der dynamischen Speicherzuweisung, darunter das Buddy-System, Mark-and-Sweep-Verfahren, Optimierungen, Garbage Collection für Generationen und Echtzeit, Multithread-Speicherzuweisung und parallele Garbage Collection. Der Dozent erklärt, dass die Generational Garbage Collection auf der Idee basiert, dass jüngere Objekte häufiger gescannt werden, während die Echtzeit-Garbage Collection während der Programmausführung im Hintergrund läuft, aber zu Korrektheitsproblemen führen kann, wenn sich das Objekt und der Zeigergraph ständig ändern. Abschließend fasst die Vorlesung verschiedene Arten der Speicherzuordnung zusammen, einschließlich Stack und Heap, und verschiedene Methoden der Speicherbereinigung, wie Referenzzählung, Mark-and-Sweep und Stop-and-Copy. Der Dozent erwähnt, dass die Studierenden einige dieser Methoden in ihrer bevorstehenden Hausaufgabe ausprobieren können.

• 00:00:00 In diesem Abschnitt erörtert der Dozent die Speicherzuweisung, die sowohl die Speicherzuweisung als auch die Freigabe umfasst. Die einfachste Form der Speicherung ist ein Stack, bei dem Speicher durch Inkrementieren des Stack-Zeigers zugewiesen und durch Dekrementieren des Stack-Zeigers freigegeben wird. Der Stack hat jedoch eine begrenzte Anwendbarkeit, da er nur das letzte Element freigeben kann, das zugewiesen wurde, und nichts in der Mitte des verwendeten Bereichs freigeben kann. Der Dozent weist auch darauf hin, dass der Stapelüberlauf aus Effizienzgründen normalerweise nicht von Compilern überprüft wird.
  
  
• 00:05:00 In diesem Abschnitt spricht der Dozent über zwei Speicherarten: den Stapel und den Haufen. Der Stack ist ein Speicher mit fester Größe, der effizient ist, aber nicht für alles verwendet werden kann, während der Heap allgemeiner, aber schwierig zu organisieren und effizient zu verwenden ist. Für die Heap-Zuweisung können malloc- und freie C-Funktionen verwendet werden, aber da C und C++ keinen Garbage Collector bereitstellen, müssen Programmierer den Speicher selbst verwalten, was zu Speicherlecks, hängenden Zeigern und doppelter Freigabe führen kann. Der Dozent schlägt vor, Speicherprüfer wie Address Sanitizer und Valgrind zu verwenden, um die Anzahl der Speicherfehler im Programm zu reduzieren.
  
  
• 00:10:00 In diesem Abschnitt erörtert der Referent verschiedene Möglichkeiten der Speicherzuweisung, beginnend mit der Zuweisung fester Größe, bei der jeder Speicher die gleiche Größe hat und einige Blöcke verwendet werden, während andere ungenutzt bleiben. Die unbenutzten Blöcke werden in einer Liste gehalten, die Freiliste genannt wird, und jeder Block in der Freiliste hat einen Zeiger auf den nächsten Block in der Liste. Um ein Objekt aus der freien Liste zuzuweisen, setzt das Programm den Zeiger auf frei und setzt dann den freien Zeiger so, dass er auf das nächste Ding in der freien Liste zeigt, wobei es den Zeiger auf das erste Objekt in der freien Liste zurückgibt. Um die Zuordnung aufzuheben, setzt man einfach den nächsten Zeiger des Objekts auf frei und setzt frei gleich dem freizugebenden Objekt. Bei der freien Liste dauert das Zuweisen und Freigeben konstant, und man erhält auch eine gute zeitliche Lokalität.
  
  
• 00:15:00 In diesem Abschnitt wird das Konzept der externen Fragmentierung eingeführt, die auftritt, wenn belegte Speicherblöcke über den gesamten Speicher verteilt sind. Dies kann zu einer größeren Seitentabelle führen, was zu Festplatten-Thrashing führen und das Nachschlagen von Übersetzungen weniger effizient machen kann. Um die externe Fragmentierung abzumildern, kann eine freie Liste oder Bitmap pro Plattenseite verwendet werden, und es kann eine Zuweisung von der vollsten Seite, das Freigeben von Story-Blöcken und das Auslagern leerer Seiten erfolgen. Heap-Zuordnung mit fester Größe kann auch nützlich sein, um die externe Fragmentierung zu reduzieren. Schließlich kann eine Heap-Zuordnung mit variabler Größe mit binfreien Listen verwendet werden, die die Effizienz freier Listen für unterschiedliche Größen von zugewiesenem Speicher nutzen.
  
  
• 00:20:00 In diesem Abschnitt wird ein Schema zum Speichern von Speicherblöcken unterschiedlicher Größe in einem Speicherzuweisungssystem vorgestellt. Das Schema umfasst das Unterteilen der Blöcke in Behälter basierend auf ihrer Größe, wobei jeder Behälter Blöcke einer bestimmten Größe enthält, die Zweierpotenzen sind. Beim Zuweisen von Speicher wird der geeignete Behälter basierend auf der angeforderten Größe ausgewählt, und wenn er leer ist, wird ein größerer, nicht leerer Behälter in kleinere Blöcke aufgeteilt, um die gewünschte Größe zu erhalten. Dieses Schema kann jedoch zu einer internen Fragmentierung des Speichers führen, was verschwenderisch ist, sodass die Anzahl der verwendeten Bins begrenzt ist und kleine Blöcke in Seiten gruppiert werden, um den Overhead zu reduzieren. Das Betriebssystem kann verwendet werden, um bei Bedarf mehr Speicher bereitzustellen, und es stehen Systemaufrufe für diesen Zweck zur Verfügung.
  
  
• 00:25:00 In diesem Abschnitt erläutert das Video, wie die Speicherzuweisung funktioniert, und stellt fest, dass Standardimplementierungen von „malloc“ auf Befehlen wie „break“ beruhen, um Speicher vom Betriebssystem zu erhalten. Das Betriebssystem stellt einen großen Teil des Arbeitsspeichers zur Verfügung, und es liegt am Speicherzuweisungssystem, ihn in kleinere Blöcke aufzuteilen. Dieser Abschnitt behandelt auch Varianten des Speicherzuordners, einschließlich unterschiedlicher Schemata zum Speichern von Blockgrößen und wie der Adressraum des virtuellen Speichers in einem Programm angeordnet ist. Es stellt fest, dass der Stapel und der Haufen aufeinander zuwachsen, sich aber niemals schneiden. Schließlich wird erwähnt, dass das Vorberechnen großer Konstantentabellen in einem Programm die Ladezeit erhöhen kann, da es das Lesen aus dem Datensegment erfordert.
  
  
• 00:30:00 In diesem Abschnitt wird das Problem der Fragmentierung mit virtuellem Speicher erörtert, das zu externer Fragmentierung, verminderter Leistung der Seitentabelle, Festplatten-Thrashing und niedrigen TLB-Trefferraten führen kann, wenn der Speicher verteilt ist. Das Ziel der Speicherzuweisung besteht darin, so wenig virtuellen Speicher wie möglich zu verwenden und gleichzeitig verwendete Speicherbereiche kompakt zu halten. Das Zuweisungsschema der freien Bin-Liste wird mit einem Theorem analysiert, das besagt, dass die Menge des vom Heap-Speicher verbrauchten virtuellen Speichers durch M log M nach oben begrenzt ist. Das Zusammenfügen kleinerer Blöcke zu größeren kann das Schema der freien Bin-Liste verbessern, aber den Overhead von Diese Methode kann laut einem Artikel von Charles Leiserson im Vergleich zum Standard-Bin-Free-List-Algorithmus hoch sein, der nur um einen konstanten Faktor schlechter ist als der optimale Zuordner.
  
  
• 00:35:00 In diesem Abschnitt erläutert der Referent das Konzept der Speicherzuweisung und wie es die Fragmentierung beim Umgang mit Heap-Speicher verringern kann. Er erörtert auch die Idee der Garbage Collection, die den Programmierer davon befreit, Objekte manuell freigeben zu müssen. Der Referent erklärt die drei Arten von Speicherobjekten – Roots, Live Objects und Dead Objects – und wie die Garbage Collection letztere recyceln kann. Schließlich beschreibt er das Zählen von Referenzen, eine einfache Form der Garbage Collection, die die Anzahl der Zeiger zählt, die auf ein Objekt verweisen, um festzustellen, ob es freigegeben werden kann.
  
  
• 00:40:00 In diesem Abschnitt stellt der Referent das Konzept der Referenzzählung als Garbage-Collection-Schema vor und erklärt, wie der Referenzzählalgorithmus funktioniert. Es wird jedoch auf eine Einschränkung des Algorithmus hingewiesen, wo Zyklen im Referenzgraphen nicht gesammelt werden können. Der Sprecher erörtert dann die Verwendung von starken und schwachen Zeigern in einigen Programmiersprachen, um diese Einschränkung zu vermeiden. Schließlich gibt der Sprecher eine Vorschau auf zwei weitere Garbage-Collection-Schemata, "Mark-and-Sweep" und "Stop and Copy", die die Beschränkung der Referenzzählung vermeiden, wenn sie sich mit Zyklen im Referenzgraphen befassen.
  
  
• 00:45:00 In diesem Abschnitt erörtert der Sprecher die Verwendung eines Breitensuchalgorithmus zum Auffinden aller lebenden Objekte im Speicher. Ein Array mit zwei Zeigern wird verwendet, um eine FIFO-Warteschlange für die Suche darzustellen, und der Algorithmus markiert jedes Live-Objekt, das von den Wurzeln aus erreichbar ist. Nachdem die Suche abgeschlossen ist, stehen die nicht markierten Objekte für die Garbage-Collection zur Verfügung. Das Mark-and-Sweep-Verfahren umfasst zwei Phasen: die markierte Phase, die den Breitensuchalgorithmus umfasst, und die Sweep-Phase, die das Scannen des Speichers umfasst, um nicht markierte Objekte freizugeben. Es gibt jedoch Einschränkungen bei diesem Schema, wie z. B. die Notwendigkeit, den gesamten Speicher zu scannen, und den Overhead, der mit dem Betrachten von nicht referenzierten Objekten verbunden ist.
  
  
• 00:50:00 In diesem Abschnitt stellt das Video das Garbage-Collection-Verfahren "Stop and Copy" vor, das sich mit der Fragmentierung befasst. Dieses Verfahren ähnelt dem Mark-and-Sweep-Algorithmus, verfolgt jedoch einen anderen Ansatz, um sicherzustellen, dass Live-Objekte zusammenhängend im Speicher sind. Die Prozedur verwendet zwei getrennte Speicherbereiche – den From-Bereich und den To-Bereich – und weist Objekte zu und befreit den From-Bereich, bis dieser voll ist. Dann wird der Garbage-Collection-Algorithmus ausgeführt, und der Zwei-Raum wird als Warteschlange für die Breitensuche verwendet, um Live-Objekte zu identifizieren, die zusammenhängend im Speicher in den Zwei-Raum platziert werden. Die Verwendung dieses Algorithmus kann jedoch zu einem möglichen Korrektheitsproblem führen, bei dem Zeiger, die auf Objekte im From-Raum zeigen, möglicherweise nicht mehr korrekt sind. Um dies anzugehen, speichert die Prozedur einen Weiterleitungszeiger in dem entsprechenden Objekt im From-Raum und aktualisiert alle Zeiger, indem sie diesen Weiterleitungszeigern folgt, wenn ein Objekt aus der Warteschlange in der Breitensuche entfernt wird.
  
  
• 00:55:00 In diesem Abschnitt bespricht der Redner den Stop-and-Copy-Garbage-Collection-Algorithmus, seine zeitliche Komplexität und wie er mit externer Fragmentierung umgeht. Der Stop-and-Copy-Algorithmus umfasst das Kopieren von Objekten aus dem from-Raum in den to-Raum und das anschließende Aktualisieren der Zeiger dieser Objekte im to-Raum. Dieser Algorithmus ist zeitlich und räumlich linear, was ihn zu einer effizienteren und effektiveren Methode der Garbage Collection macht. Wenn der From-Space voll ist, kann der Benutzer einen neuen Heap-Space anfordern und die Größe des From-Space verdoppeln. Der von diesem Schema benötigte virtuelle Speicherplatz ist konstant optimal, und dieser Algorithmus eliminiert externe Fragmentierung.
  
  
• 01:00:00 In diesem Abschnitt erörtert der Referent weitere Themen im Zusammenhang mit dynamischer Speicherzuweisung, wie das Buddy-System für die Koaleszenz, Varianten des Mark-and-Sweep-Verfahrens, Optimierungen zur Verbesserung der Leistung, Generationen-Garbage-Collection, Echtzeit-Garbage-Collection , Multithread-Speicherzuweisung und parallele Garbage Collection. Generational Garbage Collection basiert auf der Idee, dass viele Objekte kurzlebig sind und daher meistens nur jüngere Objekte gescannt werden. Die Garbage Collection in Echtzeit arbeitet im Hintergrund, während das Programm läuft, aber es könnte zu Korrektheitsproblemen führen, wenn sich der Graph von Objekten und Zeigern ändert. Bei der Multithread-Speicherzuweisung und der parallelen Garbage Collection werden mehrere Threads ausgeführt, wodurch die Algorithmen schwieriger mit Races und anderen Korrektheitsproblemen umgehen können. Der Referent fasst auch die verschiedenen Arten der Speicherzuweisung zusammen, einschließlich Stack und Heap, und verschiedene Möglichkeiten der Garbage Collection, wie z. B. Referenzzählung, Mark-and-Sweep und Stop-and-Copy.
  
  
• 01:05:00 In diesem Abschnitt erwähnte der Kursleiter, dass sie sich weiter mit Speicherzuweisungsschemata befassen werden und dass die Schüler die Möglichkeit haben werden, einige davon in ihrer bevorstehenden Hausaufgabe auszuprobieren. Der Dozent beendete dann den Vortrag und eröffnete das Wort für weitere Fragen.