Erstellen Sie ausdrucksstarke intelligente Zeiger für den Remotespeicher in C ++

Hallo Habr!

Heute veröffentlichen wir eine Übersetzung einer interessanten Studie zur Arbeit mit Speicher und Zeigern in C ++. Das Material ist ein wenig akademisch, aber es wird offensichtlich für die Leser der Bücher von Galowitz und Williams von Interesse sein.

Folgen Sie der Werbung!

In der Graduiertenschule beschäftige ich mich mit dem Aufbau verteilter Datenstrukturen. Daher ist die Abstraktion, die den Remote-Zeiger darstellt, in meiner Arbeit äußerst wichtig, um sauberen und aufgeräumten Code zu erstellen. In diesem Artikel werde ich erklären, warum intelligente Zeiger benötigt werden, erläutern, wie ich Remote-Zeigerobjekte für meine Bibliothek in C ++ geschrieben habe, und sicherstellen, dass sie genau wie normale C ++ - Zeiger funktionieren. Dies erfolgt über Remote-Link-Objekte. Außerdem werde ich erklären, in welchen Fällen diese Abstraktion aus dem einfachen Grund fehlschlägt, dass mein eigener Zeiger (bisher) die Aufgaben, die gewöhnliche Zeiger ausführen können, nicht bewältigt. Ich hoffe, dieser Artikel wird Leser interessieren, die an der Entwicklung von Abstraktionen auf hoher Ebene beteiligt sind.

Low Level APIs

Wenn Sie mit verteilten Computern oder mit Netzwerkhardware arbeiten, haben Sie häufig Lese- und Schreibzugriff auf einen Speicher über die C-API. Ein Beispiel dieser Art ist die MPI- API für die Einwegkommunikation . Diese API verwendet Funktionen, die den direkten Zugriff auf das Lesen und Schreiben aus dem Speicher anderer Knoten in einem verteilten Cluster ermöglichen. So sieht es etwas vereinfacht aus.

void remote_read(void* dst, int target_node, int offset, int size); void remote_write(void* src, int target_node, int offset, int size); 

Bei dem angegebenen Versatz in das gemeinsam genutzte Speichersegment des remote_read eine bestimmte Anzahl von Bytes daraus und remote_write schreibt eine bestimmte Anzahl von Bytes.

Diese APIs sind großartig, weil sie uns Zugriff auf wichtige Grundelemente ermöglichen, die für die Implementierung von Programmen, die auf einem Computercluster ausgeführt werden, nützlich sind. Sie sind auch sehr gut, weil sie sehr schnell arbeiten und die auf Hardwareebene angebotenen Funktionen genau widerspiegeln: Remote Direct Memory Access (RDMA). Moderne Supercomputernetzwerke wie Cray Aries und Mellanox EDR ermöglichen es uns zu berechnen, dass die Verzögerung beim Lesen / Schreiben 1-2 μs nicht überschreitet. Diese Anzeige wird durch die Tatsache erreicht, dass die Netzwerkkarte (NIC) direkt in den RAM lesen und schreiben kann, ohne darauf zu warten, dass die Remote-CPU aufwacht und auf Ihre Netzwerkanforderung reagiert.

Solche APIs sind jedoch in Bezug auf die Anwendungsprogrammierung nicht so gut. Selbst bei solchen einfachen APIs wie oben beschrieben kostet das versehentliche Löschen von Daten nichts, da für jedes im Speicher gespeicherte Objekt kein separater Name vorhanden ist, sondern nur ein großer zusammenhängender Puffer. Darüber hinaus ist die Schnittstelle untypisiert, dh Sie haben keine weitere konkrete Hilfe mehr: Wenn der Compiler schwört, wenn Sie den Wert des falschen Typs an der falschen Stelle notieren. Ihr Code wird sich einfach als falsch herausstellen, und Fehler werden mysteriöser und katastrophaler Natur sein. Die Situation ist noch komplizierter, da diese APIs in Wirklichkeit etwas komplizierter sind und es bei der Arbeit mit ihnen durchaus möglich ist, zwei oder mehr Parameter fälschlicherweise neu anzuordnen.

Gelöschte Zeiger

Zeiger sind eine wichtige und notwendige Abstraktionsebene, die beim Erstellen von Programmierwerkzeugen auf hoher Ebene benötigt wird. Die direkte Verwendung von Zeigern ist manchmal schwierig, und Sie können viele Fehler machen, aber Zeiger sind die Grundbausteine ​​des Codes. Datenstrukturen und sogar C ++ - Links verwenden häufig Zeiger unter der Haube.

Angenommen, wir haben eine API ähnlich der oben beschriebenen, wird eine eindeutige Position im Speicher durch zwei „Koordinaten“ angezeigt: (1) den Rang oder die Prozess-ID und (2) den Versatz zu dem gemeinsam genutzten Teil des Remote-Speichers, der vom Prozess mit diesem Rang belegt wird . Sie können dort nicht anhalten und eine vollwertige Struktur erstellen.

  template <typename T> struct remote_ptr { size_t rank_; size_t offset_; }; 

Zu diesem Zeitpunkt ist es bereits möglich, eine API zum Lesen und Schreiben in Remote-Zeiger zu entwerfen. Diese API ist sicherer als die ursprünglich verwendete.

  template <typename T> T rget(const remote_ptr<T> src) { T rv; remote_read(&rv, src.rank_, src.offset_, sizeof(T)); return rv; } template <typename T> void rput(remote_ptr<T> dst, const T& src) { remote_write(&src, dst.rank_, dst.offset_, sizeof(T)); } 

Blocktransfers sehen sehr ähnlich aus, und hier lasse ich sie der Kürze halber weg. Zum Lesen und Schreiben von Werten können Sie nun den folgenden Code schreiben:

  remote_ptr<int> ptr = ...; int rval = rget(ptr); rval++; rput(ptr, rval); 

Es ist bereits besser als die ursprüngliche API, da wir hier mit typisierten Objekten arbeiten. Jetzt ist es nicht so einfach, einen Wert vom falschen Typ zu schreiben oder zu lesen oder nur einen Teil eines Objekts zu schreiben.

Zeigerarithmetik

Zeigerarithmetik ist die wichtigste Technik, mit der ein Programmierer Wertesammlungen im Speicher verwalten kann. Wenn wir ein Programm für verteilte Arbeit im Speicher schreiben, werden wir vermutlich mit großen Wertesammlungen arbeiten.
Was bedeutet das Erhöhen oder Verringern eines gelöschten Zeigers um eins? Die einfachste Möglichkeit besteht darin, die Arithmetik der gelöschten Zeiger als die Arithmetik gewöhnlicher Zeiger zu betrachten: p + 1 zeigt einfach auf die nächste sizeof(T) -ausgerichteten Speichers nach p im gemeinsam genutzten Segment des ursprünglichen Ranges.

Obwohl dies nicht die einzig mögliche Definition der Arithmetik von Remote-Zeigern ist, wurde sie kürzlich am aktivsten übernommen, und die auf diese Weise verwendeten Remote-Zeiger sind in Bibliotheken wie UPC ++ , DASH und BCL enthalten. Die UPC-Sprache ( Unified Parallel C ), die in der Community der HPC-Spezialisten (High Performance Computing) ein reiches Erbe hinterlassen hat, enthält jedoch eine ausführlichere Definition der Zeigerarithmetik [1].

Das Implementieren der Zeigerarithmetik auf diese Weise ist einfach und beinhaltet nur das Ändern des Zeigerversatzes.

  template <typename T> remote_ptr<T> remote_ptr<T>::operator+(std::ptrdiff_t diff) { size_t new_offset = offset_ + sizeof(T)*diff; return remote_ptr<T>{rank_, new_offset}; } 

In diesem Fall haben wir die Möglichkeit, auf Datenarrays im verteilten Speicher zuzugreifen. Wir konnten also erreichen, dass jeder Prozess im SPMD-Programm eine Schreib- oder Leseoperation für seine Variable in dem Array ausführt, auf das der Remote-Zeiger gerichtet ist [2].

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { rput(ptr + my_rank(), my_rank()); } } 

Es ist auch einfach, andere Operatoren zu implementieren, die den gesamten Satz von arithmetischen Operationen unterstützen, die in gewöhnlicher Zeigerarithmetik ausgeführt werden.

Wählen Sie nullptr

Bei regulären Zeigern ist der Wert nullptr NULL , was normalerweise bedeutet, dass #define auf 0x0 reduziert wird, da dieser Abschnitt im Speicher wahrscheinlich nicht verwendet wird. In unserem Schema mit Remote-Zeigern können wir entweder einen bestimmten Zeigerwert als nullptr , wodurch dieser Speicherort im Speicher nicht verwendet wird, oder ein spezielles boolesches nullptr , das angibt, ob der Zeiger null ist. Trotz der Tatsache, dass es nicht der beste Ausweg ist, einen bestimmten Speicherort nicht zu verwenden, berücksichtigen wir auch, dass sich die Größe des Remote-Zeigers beim Hinzufügen nur eines Booleschen Werts aus Sicht der meisten Compiler verdoppelt und von 128 auf 256 Bit wächst, um die Ausrichtung aufrechtzuerhalten. Dies ist besonders unerwünscht. In meiner Bibliothek habe ich {0, 0} , nullptr einen Offset von 0 mit einem Rang von 0 als Wert nullptr .

Es kann möglich sein, andere Optionen für nullptr zu nullptr , die genauso gut funktionieren. Darüber hinaus sind in einigen Programmierumgebungen wie UPC schmale Zeiger implementiert, die jeweils in 64 Bit passen. Somit können sie in Atomvergleichsoperationen mit Austausch verwendet werden. Wenn Sie mit einem schmalen Zeiger arbeiten, müssen Sie Kompromisse eingehen: Entweder der Versatzbezeichner oder der Rangbezeichner sollten in 32 Bit oder weniger passen, was die Skalierbarkeit einschränkt.

Gelöschte Links

In Sprachen wie Python dient die Klammeranweisung als syntaktischer Zucker zum Aufrufen der __getitem__ __setitem__ und __getitem__ , je nachdem, ob Sie das Objekt lesen oder darauf schreiben. In C ++ unterscheidet operator[] nicht, zu welcher der Wertkategorien ein Objekt gehört und ob der zurückgegebene Wert sofort unter Lesen oder Schreiben fällt. Um dieses Problem zu lösen, geben C ++ - Datenstrukturen Links zurück, die auf den im Container enthaltenen Speicher verweisen und geschrieben oder gelesen werden können. Die operator[] -Implementierung für std::vector könnte ungefähr so ​​aussehen.

  T& operator[](size_t idx) { return data_[idx]; } 

Die wichtigste Tatsache hierbei ist, dass wir eine Entität vom Typ T& , bei der es sich um eine rohe C ++ - Verknüpfung handelt, über die Sie schreiben können, und keine Entität vom Typ T , die lediglich den Wert der Quelldaten darstellt.

In unserem Fall können wir keine rohe C ++ - Verknüpfung zurückgeben, da wir uns auf Speicher beziehen, der sich auf einem anderen Knoten befindet und nicht in unserem virtuellen Adressraum dargestellt ist. Natürlich können wir unsere eigenen benutzerdefinierten Referenzobjekte erstellen.
Ein Link ist ein Objekt, das als Wrapper um einen Zeiger dient und zwei wichtige Funktionen ausführt: Er kann in einen Wert vom Typ T konvertiert werden und Sie können ihn auch einem Wert vom Typ T zuweisen T Im Fall einer Remote-Referenz müssen wir nur einen impliziten Konvertierungsoperator implementieren, der den Wert liest, und einen Zuweisungsoperator erstellen, der in den Wert schreibt.

 template <typename T> struct remote_ref { remote_ptr<T> ptr_; operator T() const { return rget(ptr_); } remote_ref& operator=(const T& value) { rput(ptr_, value); return *this; } }; 

Auf diese Weise können wir unseren Remote-Zeiger mit neuen leistungsstarken Funktionen anreichern, bei deren Vorhandensein er genau wie gewöhnliche Zeiger dereferenziert werden kann.

 template <typename T> remote_ref<T> remote_ptr<T>::operator*() { return remote_ref<T>{*this}; } template <typename T> remote_ref<T> remote_ptr<T>::operator[](ptrdiff_t idx) { return remote_ref<T>{*this + idx}; } 

Jetzt haben wir das gesamte Bild wiederhergestellt und gezeigt, wie Sie Remote-Zeiger wie gewohnt verwenden können. Wir können das einfache Programm oben umschreiben.

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { ptr[my_rank()] = my_rank(); } } 

Natürlich können wir mit unserer neuen Zeiger-API komplexere Programme schreiben, beispielsweise eine Funktion zum Durchführen einer parallelen Reduktion basierend auf einem Baum [3]. Implementierungen, die unsere Remote-Zeigerklasse verwenden, sind sicherer und sauberer als diejenigen, die normalerweise mit der oben beschriebenen C-API erhalten werden.

Kosten, die zur Laufzeit anfallen (oder fehlen!)

Was würde es uns jedoch kosten, eine solche Abstraktion auf hoher Ebene zu verwenden? Jedes Mal, wenn wir auf den Speicher zugreifen, rufen wir die Dereferenzierungsmethode auf, geben das Zwischenobjekt zurück, das den Zeiger umschließt, und rufen dann den Konvertierungsoperator oder den Zuweisungsoperator auf, der das Zwischenobjekt beeinflusst. Was kostet es uns zur Laufzeit?

Es stellt sich heraus, dass bei sorgfältiger Festlegung der Zeiger- und Referenzklassen zur Laufzeit kein Aufwand für diese Abstraktion entsteht - moderne C ++ - Compiler verarbeiten diese Zwischenobjekte und Methodenaufrufe durch aggressive Einbettung. Um zu bewerten, was uns eine solche Abstraktion kostet, können wir ein einfaches Beispielprogramm kompilieren und überprüfen, wie die Assembly abläuft, um festzustellen, welche Objekte und Methoden zur Laufzeit vorhanden sind. In dem hier beschriebenen Beispiel mit baumbasierter Reduktion, die mit Klassen von Remote-Zeigern und remote_read kompiliert wurde, reduzieren moderne Compiler die baumbasierte Reduktion auf mehrere remote_read und remote_write [4]. Zur Laufzeit werden keine Klassenmethoden aufgerufen, keine Referenzobjekte vorhanden.

Interaktion mit Datenstrukturbibliotheken

Erfahrene C ++ - Programmierer denken daran, dass in der Standard-C ++ - Vorlagenbibliothek Folgendes angegeben ist: STL-Container müssen benutzerdefinierte C ++ - Allokatoren unterstützen . Mit Allokatoren können Sie Speicher zuweisen, und dann kann auf diesen Speicher mithilfe der von uns erstellten Zeigertypen verwiesen werden. Bedeutet dies, dass Sie einfach einen "Remote-Allokator" erstellen und ihn verbinden können, um Daten mithilfe von STL-Containern im Remote-Speicher zu speichern?

Leider gibt es keine. Vermutlich erfordert der C ++ - Standard aus Leistungsgründen keine Unterstützung mehr für benutzerdefinierte Referenztypen, und in den meisten Implementierungen der C ++ - Standardbibliothek werden sie wirklich nicht unterstützt. Wenn Sie beispielsweise libstdc ++ von GCC verwenden, können Sie auf benutzerdefinierte Zeiger zurückgreifen, es stehen Ihnen jedoch nur normale C ++ - Links zur Verfügung, sodass Sie keine STL-Container im Remotespeicher verwenden können. Einige übergeordnete C ++ - Vorlagenbibliotheken, z. B. Agency , die benutzerdefinierte Zeigertypen und Referenztypen verwenden, enthalten eigene Implementierungen einiger Datenstrukturen aus STL, mit denen Sie wirklich mit Remote-Referenztypen arbeiten können. In diesem Fall erhält der Programmierer mehr Freiheit bei der kreativen Erstellung von Zuordnertypen, Zeigern und Verknüpfungen sowie eine Sammlung von Datenstrukturen, die automatisch mit ihnen verwendet werden können.

Breiter Kontext

In diesem Artikel haben wir eine Reihe allgemeinerer und noch nicht gelöster Probleme angesprochen.

• Speicherzuordnung . Wie können wir nun, da wir Objekte im Remote-Speicher referenzieren können, einen solchen Remote-Speicher reservieren oder zuweisen?
• Unterstützung für Objekte . Was ist mit der Speicherung solcher Objekte im Remote-Speicher, deren Typ komplizierter ist als int? Ist eine ordentliche Unterstützung für komplexe Typen möglich? Können einfache Typen gleichzeitig unterstützt werden, ohne Ressourcen für die Serialisierung zu verschwenden?
• Entwerfen verteilter Datenstrukturen . Welche Datenstrukturen und Anwendungen können Sie mit diesen Abstraktionen erstellen? Welche Abstraktionen sollten für die Datenverteilung verwendet werden?

Anmerkungen

[1] In UPC haben Zeiger eine Phase, die bestimmt, auf welchen Rang der Zeiger gerichtet wird, nachdem er um eins erhöht wurde. Aufgrund der Phasen können verteilte Arrays in Zeigern eingekapselt werden, und die Verteilungsmuster in ihnen können sehr unterschiedlich sein. Diese Funktionen sind sehr leistungsfähig, aber für Anfänger mögen sie magisch erscheinen. Obwohl einige UPC-Asse diesen Ansatz wirklich bevorzugen, besteht ein vernünftigerer objektorientierter Ansatz darin, zuerst eine einfache Remote-Zeigerklasse zu schreiben und dann sicherzustellen, dass die Daten basierend auf speziell dafür entwickelten Datenstrukturen zugewiesen werden.

[2] Die meisten Anwendungen in HPC sind im Stil von SPMD geschrieben . Dieser Name bedeutet "ein Programm, verschiedene Daten". Die SPMD-API bietet eine Funktion oder Variable my_rank() , die dem Prozess, der das Programm ausführt, einen eindeutigen Rang oder eine eindeutige ID mitteilt, anhand derer er dann vom Hauptprogramm verzweigen kann.

[3] Hier ist eine einfache Baumreduktion, die im SPMD-Stil unter Verwendung der Remote-Zeigerklasse geschrieben wurde. Der Code basiert auf einem Programm, das ursprünglich von meinem Kollegen Andrew Belt geschrieben wurde .

  template <typename T> T parallel_sum(remote_ptr<T> a, size_t len) { size_t k = len; do { k = (k + 1) / 2; if (my_rank() < k && my_rank() + k < len) { a[my_rank()] += a[my_rank() + k]; } len = k; barrier(); } while (k > 1); return a[0]; } 

[4] Das kompilierte Ergebnis des obigen Codes finden Sie hier .