Massive und Hardware-Parallelität sind heiße Themen des 21. Jahrhunderts. Dafür gibt es mehrere gute und einen eher traurigen Gründe.
Zwei gute Gründe: eine Kombination aus exzellenter GPU-Leistung in Spielen und gleichzeitig deren unerwarteter Nebenwirkung beim vertieften Erlernen der KI, da dort auf Hardwareebene massive Parallelität implementiert wird. Der traurige Grund ist, dass die Geschwindigkeit von Einprozessorsystemen seit 2006 gegen die Gesetze der Physik gerichtet ist. Aktuelle Probleme mit Leckage und thermischem Durchschlag begrenzen den Anstieg der Taktfrequenz stark, und der klassische Spannungsabfall stößt jetzt auf ernsthafte Probleme mit Quantenrauschen.
Im Wettbewerb um die Aufmerksamkeit der Öffentlichkeit versuchen die Prozessorhersteller, immer mehr Prozessorkerne in jeden Chip zu schieben, um die theoretische Gesamtleistung zu bewerben. Die Förderbemühungen und spekulativen Ausführungsmethoden, die Multithreading unter der Haube verwenden, nehmen ebenfalls rasch zu, sodass ein einzelner Prozessor, der für den Programmierer sichtbar ist, Anweisungen schneller verarbeiten kann.
Die unbequeme Wahrheit ist, dass viele unserer weniger glamourösen Computeraufgaben sichtbares Multithreading einfach nicht sehr gut nutzen können. Dafür gibt es verschiedene Gründe, die unterschiedliche Konsequenzen für den Programmierer haben, und es gibt viel Verwirrung. In diesem Artikel möchte ich die Situation etwas klären.
Zunächst müssen Sie klar verstehen, wo und warum Hardware-Parallelität am besten funktioniert. Schauen wir uns die Berechnungen für Grafiken, neuronale Netze, Signalverarbeitung und Bitcoin-Mining an. Es gibt ein Muster: Parallelisierungsalgorithmen funktionieren am besten auf Geräten, die (a) speziell für deren Ausführung entwickelt wurden; (b) kann nichts anderes tun!
Wir sehen auch, dass die Eingaben für die erfolgreichsten parallelen Algorithmen (Sortieren, String-Matching, schnelle Fourier-Transformation, Matrixoperationen, inverse Quantisierung von Bildern usw.) ziemlich ähnlich aussehen. In der Regel haben sie eine metrische Struktur und der Unterschied zwischen „nahen“ und „entfernten“ Daten ist impliziert, sodass wir sie in Teile schneiden können, da die Verbindung zwischen den entfernten Elementen unbedeutend ist.
In Bezug auf den letzten Artikel zur semantischen Lokalität können wir sagen, dass parallele Methoden hauptsächlich dann anwendbar sind, wenn die Daten eine gute Lokalität aufweisen. Und sie eignen sich am besten für Geräte, die nur Verbindungen mit kurzer Reichweite unterstützen, wie die systolische Matrix im Herzen der GPU.
Andererseits ist es sehr schwierig, Software zu schreiben, die effektiv einen solchen Abschnitt für Eingabedaten mit schlechter Lokalität auf Allzweckcomputern (von Neumann-Architektur) erzeugt.
Infolgedessen können wir eine einfache Heuristik formulieren: Die
Chancen, paralleles Rechnen zu verwenden, sind umgekehrt proportional zum Grad der irreduziblen semantischen Nichtlokalität in den Eingabedaten.Eine weitere Einschränkung des parallelen Rechnens besteht darin, dass einige wichtige Algorithmen - auch theoretisch - überhaupt nicht parallelisiert werden können. Als ich dieses Thema zum ersten Mal in meinem Blog diskutierte, kam ich auf den Begriff „kranker Algorithmus“, bei dem SICK für „Serial, Intrinscally - Cope, Kiddo!“ Steht. Wichtige Beispiele sind: Dijkstras Algorithmus zum Finden des kürzesten Weges; Erkennung von Zyklen in gerichteten Graphen (unter Verwendung von 3-SAT in Lösern); tiefe Suche; Berechnen des n-ten Mitglieds in der kryptografischen Hash-Kette; Netzwerk-Stream-Optimierung ... und dies ist keine vollständige Liste.
Auch hier spielt die schlechte Lokalität der Eingabedaten eine Rolle, insbesondere im Kontext der Grafik- und Baumstruktur. Kryptografische Hash-Ketten können nicht parallelisiert werden, da Datensätze in strenger Reihenfolge berechnet werden - dies ist wirklich eine wichtige Regel, um die Kette vor Fälschungen zu schützen.
Und hier kommt die Sperre ins Spiel: Sie können nichts parallelisieren, während der SICK-Algorithmus funktioniert.
Wir sind noch nicht fertig. Es gibt mindestens zwei Klassen von Hindernissen und sehr häufige.
Erstens gibt es keine notwendigen Werkzeuge. Die meisten Sprachen unterstützen nur einen Mutex und Semaphoren. Dies ist praktisch, Grundelemente sind leicht zu implementieren, aber diese Situation führt zu schrecklichen Explosionen von Komplexität im Kopf: Es ist fast unmöglich, den Maßstab von mehr als vier interagierenden Sperren zu erfassen.
Wenn Sie Glück haben, erhalten Sie eine entgegenkommendere Reihe von Grundelementen, z. B. Go-Kanäle (auch bekannt als Communicating Sequential Processes) oder das Rust-Besitz- / Sende- / Synchronisationssystem. Tatsächlich wissen wir jedoch nicht, was die „richtige“ Sprache der Grundelemente für die Implementierung der Parallelität in der von Neumann-Architektur ist. Vielleicht gibt es nicht einmal einen richtigen Satz von Grundelementen. Vielleicht sind zwei oder drei verschiedene Sätze für verschiedene Problembereiche geeignet, aber sie sind als Einheit und Quadratwurzel von zwei nicht vergleichbar. Bis heute weiß es 2018 niemand wirklich.
Und die letzte, aber nicht weniger wichtige Einschränkung ist das menschliche Gehirn. Selbst bei einem klaren Algorithmus mit guter Datenlokalität und effizienten Tools ist die parallele Programmierung für Menschen einfach
schwierig , selbst wenn der Algorithmus ganz einfach angewendet wird. Unser Gehirn modelliert die einfachsten Zustandsräume rein sequentieller und insbesondere paralleler Programme nicht sehr gut.
Wir wissen das, weil es viele echte Beweise dafür gibt, dass das Debuggen von parallelem Code mehr als schwierig ist. Dies wird durch Rennbedingungen, Deadlocks, selbstzerstörende Sperren und heimtückische Datenbeschädigung aufgrund einer etwas unsicheren Reihenfolge der Anweisungen behindert.
Ich denke, dass das Verständnis dieser Einschränkungen nach dem Zusammenbruch
des Skalierungsgesetzes von Dennard wichtiger wird. Aufgrund all dieser Engpässe bei der Programmierung wird in einem Teil von Mehrkernsystemen immer Software ausgeführt, die Geräte nicht mit 100% der Rechenleistung laden kann. Wenn Sie von der anderen Seite schauen, haben wir überschüssiges Eisen für aktuelle Aufgaben. Wie viel Geld und Mühe verschwenden wir?
Prozessorhersteller möchten, dass Sie die funktionalen Vorteile intelligenter neuer Chips mit noch mehr Kernen überschätzen. Wie sonst können sie Geld sammeln, um gigantische Produktionskosten zu decken und gleichzeitig profitabel zu bleiben? Marketing gibt sein Bestes, damit Sie sich nie fragen, welche Aufgaben ein solches Multithreading wirklich vorteilhaft ist.
Ehrlich gesagt gibt es solche Aufgaben. Server in Rechenzentren, die Hunderttausende gleichzeitiger Transaktionen pro Sekunde verarbeiten, verteilen die Last wahrscheinlich ziemlich gut auf die Kerne. Auch Smartphones oder eingebettete Systeme - in beiden Fällen werden erhebliche Anstrengungen unternommen, um Kosten und Energieverbrauch zu minimieren, was es schwierig macht, überschüssigen Strom in Betrieb zu nehmen.
Aber für normale Desktop- und Laptop-Benutzer? Vage Zweifel quälen mich. Die Situation ist hier schwer zu verstehen, da die tatsächliche Produktivitätssteigerung auf andere Faktoren zurückzuführen ist, beispielsweise auf den Übergang von der Festplatte zur SSD. Solche Erfolge werden leicht mit dem Effekt der Beschleunigung der CPU verwechselt, wenn Sie keine gründliche Profilerstellung durchführen.
Hier sind die Gründe für solche Verdächtigungen:
- Seriöses paralleles Rechnen auf Desktop- / Laptop-Computern tritt nur auf der GPU auf.
- Mehr als zwei Kerne in einem Prozessor sind normalerweise unbrauchbar. Betriebssysteme können Anwendungsflüsse verteilen, aber typische Software kann keine Parallelität verwenden, und die meisten Benutzer schaffen es selten, gleichzeitig eine große Anzahl verschiedener Anwendungen zu starten, die viel CPU-Ressourcen verbrauchen, um ihre Geräte vollständig zu laden.
- Folglich tun die meisten Quad-Core-Systeme die meiste Zeit nur Wärme zu erzeugen.
Unter meinen Lesern gibt es viele Leute, die diese Hypothese wahrscheinlich vernünftigerweise kommentieren können. Es ist interessant zu sehen, was sie sagen.
UPDATE Der Kommentator zu G + wies auf einen interessanten Vorteil von Multi-Core-Prozessoren hin: Sie kompilieren Code sehr schnell. Der Quellcode von Sprachen wie C hat eine gute Lokalität: Hier werden gut getrennte Einheiten (Quelldateien) zu Objektdateien kompiliert, die der Linker dann kombiniert.