Spekulation zur Simulation. Innovation in der Verifizierung

Neuauflage von Plato

Verfolger: 0

Dies ist eine interessante Idee, die hardwaregestützte spekulative Parallelität verwendet, um die Simulation zu beschleunigen, mit einer Wendung, die benutzerdefinierte Hardware erfordert. Paul Cunningham (Senior VP/GM, Verification bei Cadence), Raúl Camposano (Silicon Catalyst, Unternehmer, ehemaliger CTO von Synopsys und jetzt CTO von Silvaco) und ich setzen unsere Reihe zu Forschungsideen fort. Feedback wie immer erwünscht.

Spekulation für Simulation

Die Innovation

Die Auswahl dieses Monats ist Chronos: Effiziente spekulative Parallelität für Beschleuniger. Die Autoren präsentierten das Papier auf der 2020 Conference on Architectural Support for Programming Languages and Operating Systems und stammen vom MIT.

Die Ausnutzung der Parallelität mit Multicore-Prozessoren ist eine Option für Anwendungen, bei denen Parallelität selbstverständlich ist. Andere Algorithmen lassen sich möglicherweise nicht so einfach partitionieren, profitieren jedoch möglicherweise von der spekulativen Ausführung unter Ausnutzung der intrinsischen Parallelität. Normalerweise hängt die spekulative Ausführung von der Cache-Kohärenz ab, was insbesondere für die Simulation ein hoher Overhead ist. Diese Methode umgeht die Notwendigkeit der Kohärenz, indem sie die Aufgabenausführung physisch lokalisiert, um Kacheln nach dem Ziel-Lese-Schreib-Objekt zu berechnen, und stellt sicher, dass die Konflikterkennung lokal erkannt werden kann, ohne dass eine globale Kohärenzverwaltung erforderlich ist. Tasks können spekulativ parallel ausgeführt werden; Jeder erkannte Konflikt kann von einer Aufgabe durch ihre untergeordneten Aufgaben abgewickelt und dann erneut ausgeführt werden, ohne dass andere Threads angehalten werden müssen.

Hier noch ein weiterer Hinweis. Dieses Verfahren unterstützt im Gegensatz zu den meisten Hardwarebeschleunigungstechniken eine verzögerungsbasierte Simulation.

Pauls Ansicht

Wow, was für ein wunderbares Papier mit hoher Oktanzahl von MIT! Wenn ich nach paralleler Berechnung gefragt werde, denke ich sofort an Threads, Mutexe und Speicherkohärenz. So sind natürlich moderne Mehrkern-CPUs aufgebaut. Aber es ist nicht die einzige Möglichkeit, die Parallelisierung in der Hardware zu unterstützen.

Dieses Papier schlägt eine alternative Architektur für die Parallelisierung namens Chronos vor, die auf einer geordneten Warteschlange von Aufgaben basiert. Zur Laufzeit werden Aufgaben in Zeitstempelreihenfolge ausgeführt und jede Aufgabe kann neue Unteraufgaben erstellen, die der Warteschlange dynamisch hinzugefügt werden. Die Ausführung beginnt damit, dass einige anfängliche Aufgaben in die Warteschlange gestellt werden, und endet, wenn sich keine weiteren Aufgaben in der Warteschlange befinden.

Aufgaben in der Warteschlange werden parallel an mehrere Verarbeitungselemente (PEs) ausgelagert – was bedeutet, dass Chronos zukünftige Aufgaben spekulativ ausführt, bevor die aktuelle Aufgabe abgeschlossen ist. Wenn die aktuelle Aufgabe alle spekulativ ausgeführten zukünftigen Aufgaben ungültig macht, werden die Aktionen dieser zukünftigen Aufgaben "rückgängig gemacht" und sie werden erneut in die Warteschlange gestellt. Die korrekte Implementierung dieses Konzepts in Hardware ist nicht einfach, aber für den externen Benutzer ist es schön: Sie codieren Ihren Algorithmus einfach so, als ob die Aufgabenwarteschlange seriell auf einem einzelnen PE ausgeführt wird. Sie müssen keine Mutexe codieren oder sich Gedanken über Deadlocks machen.

Die Autoren implementieren Chronos in SystemVerilog und kompilieren es zu einem FPGA. Ein Großteil des Papiers widmet sich der Erklärung, wie sie die Aufgabenwarteschlange und alle notwendigen Entrollungen in der Hardware für maximale Effizienz implementiert haben. Chronos wird anhand von vier Algorithmen bewertet, die sich gut für eine auf Aufgabenwarteschlangen basierende Architektur eignen. Jeder Algorithmus wird auf zwei Arten implementiert: erstens mit einem dedizierten algorithmenspezifischen PE und zweitens mit einer handelsüblichen Open-Source-32-Bit-eingebetteten RISC-V-CPU als PE. Die Leistung von Chronos wird dann mit Multithread-Softwareimplementierungen der Algorithmen verglichen, die auf einem Intel Xeon-Server mit einem ähnlichen Preisschild wie das für Chronos verwendete FPGA ausgeführt werden. Die Ergebnisse sind beeindruckend – Chronos skaliert 3- bis 15-mal besser als die Verwendung des Xeon-Servers. Der Vergleich von Tabelle 3 mit Abbildung 14 macht mir jedoch etwas Sorgen, dass die meisten dieser Gewinne eher von den algorithmenspezifischen PEs als von der Chronos-Architektur selbst stammen.

Da dies ein Verifizierungsblog ist, habe ich natürlich auf den Simulationsbenchmark auf Gate-Ebene gezoomt. Die EDA-Branche hat viel investiert, um zu versuchen, die Logiksimulation zu parallelisieren, und es hat sich als schwierig erwiesen, große Gewinne über einige wenige spezifische Anwendungsfälle hinaus zu sehen. Dies ist hauptsächlich darauf zurückzuführen, dass die Leistung der meisten realen Simulationen von Lade-/Speicheranweisungen dominiert wird, die im L3-Cache fehlen und in den DRAM gehen. In diesem Dokument gibt es nur einen Testfall, bei dem es sich um einen winzigen 32-Bit-Carry-Save-Addierer handelt. Wenn Sie diesen Blog lesen und daran interessiert sind, ein gründlicheres Benchmarking durchzuführen, lassen Sie es mich bitte wissen – wenn Chronos wirklich gut auf Simulationen in der realen Welt skalieren kann, hätte es einen enormen kommerziellen Wert!

Raúls Ansicht

Der Hauptbeitrag dieser Arbeit ist die Ausführungsmodell für räumlich lokalisierte geordnete Aufgaben (SLOT). Dies ist effizient für Hardwarebeschleuniger, die Parallelität und Spekulation ausnutzen, und für Anwendungen, die Aufgaben dynamisch zur Laufzeit generieren. Die Unterstützung dynamischer Parallelität ist für die Simulation unvermeidlich, und die spekulative Synchronisation ist eine ansprechende Option, aber der Kohärenz-Overhead ist zu hoch.

SLOT vermeidet die Notwendigkeit von Kohärenz, indem es jede Aufgabe darauf beschränkt, auf einem einzelnen Objekt zu arbeiten (zu schreiben) und unterstützt geordnete Aufgaben, um eine Multi-Objekt-Atomizität zu ermöglichen. SLOT-Anwendungen sind geordnete, dynamisch erstellte Aufgaben, die durch einen Zeitstempel und eine Objekt-ID gekennzeichnet sind. Zeitstempel geben Reihenfolgebeschränkungen an; Objekt-IDs spezifizieren die Datenabhängigkeiten, dh Tasks sind genau dann datenabhängig, wenn sie dieselbe Objekt-ID haben. (bei Leseabhängigkeit kann die Aufgabe spekulativ ausgeführt werden). Die Konflikterkennung wird lokal (ohne komplexe Verfolgungsstrukturen), indem Objekt-IDs auf Kerne oder Kacheln abgebildet werden und jede Aufgabe dorthin gesendet wird, wo ihre Objekt-ID abgebildet ist.

Das Chronos Das System wurde im AWS FPGA-Framework als System mit 16 Kacheln mit jeweils 4 anwendungsspezifischen Verarbeitungselementen (PE) implementiert, die mit 125 MHz laufen. Dieses System wird mit einer Baseline verglichen, die aus Intel Xeon E20-40v2.4 mit 5 Kernen/2676 Threads und 3 GHz besteht, das speziell ausgewählt wurde, weil sein Preis mit dem FPGA vergleichbar ist (ca. 2 $/Stunde). Wenn eine einzelne Aufgabe auf einem PE ausgeführt wird, ist Chronos 2.45-mal schneller als die Basislinie. Wenn die Anzahl gleichzeitiger Aufgaben zunimmt, skaliert die Chronos-Implementierung auf eine selbstrelative Beschleunigung von 44.9-fach auf 8 Kacheln, was einer 15.3-fachen Beschleunigung gegenüber der CPU-Implementierung entspricht. Sie verglichen auch eine Implementierung, die auf Allzweck-RISC-V statt auf anwendungsspezifischen PEs basiert; PEs waren 5x schneller als RISC-V.

Ich fand das Papier beeindruckend, weil es alles von einem Konzept über die Definition des SLOT-Ausführungsmodells bis hin zur Implementierung von Hardware und dem detaillierten Vergleich mit einer traditionellen Xeon-CPU für 4-Anwendungen abdeckt. Der Aufwand ist beträchtlich, Chronos umfasst über 20,000 Zeilen SystemVerilog. Das Ergebnis ist eine durchschnittlich 5.4-fache Beschleunigung (der 4 Anwendungen) gegenüber Software-Parallelversionen aufgrund von mehr Parallelität und mehr Verwendung von spekulativer Ausführung. Das Papier ist auch für die Anwendung auf Nicht-Simulationsaufgaben lesenswert; Das Papier enthält drei Beispiele.

Teile diesen Beitrag über: