Task- und Datenparallelität mit Rust
Wer mit Rust einfach und komfortabel effiziente parallele wie auch nebenläufige Anwendungen entwickeln möchte, dem bieten sich Rayon, packed_simd oder Tokio an.
- Dr. Stefan Lankes
- Dr. Jens Breitbart
Um moderne Mehrkernrechner auszulasten, ist die Entwicklung von parallelem oder nebenläufigen Code zwingend erforderlich. Rust bietet als Teil der Standardbibliothek verschiedene Low-Level-Konzepte, die auch aus anderen Sprachen bekannt sind, wie Threads, atomare Operationen oder unterschiedliche Arten von Locks. Diese Konzepte sind bereits detaillierter im Artikel "Rust als sichere Programmiersprache für systemnahe und parallele Software" beschrieben.
Rust unterstützt Entwickler bei der Benutzung dieser Konstrukte, indem sich bereits zur Compile-Zeit viele Fehler erkennen lassen und daher nicht mehr zeitaufwendig mit Debuggern gefunden werden müssen. Die Low-Level-Konstrukte ermöglichen zwar feingranulare Kontrolle über die Art und Weise, wie der Code ausgeführt wird, allerdings erhöhen sie typischerweise auch die Entwicklungszeit von Anwendungen im Vergleich zur Verwendung von High-Level-Konzepten auf Basis paralleler Schleifen beziehungsweise Iteratoren.
Die Autoren gehen im Folgenden exemplarisch auf die Bibliotheken Rayon, packed_simd und Tokio ein. Die verwendeten Beispiele sind auch auf GitHub zu finden.
Datenparallelisierung mit Rayon
Rayon ist eine Bibliothek, die das Entwickeln paralleler Anwendungen deutlich vereinfacht. Als englisches Synonym für Kunstseide ist Rayon nicht nur namentlich eine Hommage an die auf Intel zurückgehende C/C++-Erweiterung Cilk, die dem englischen Wort für Seide nachempfunden ist. Entwickler, die Erfahrung mit Threading Building Blocks (TBB) , OpenMP oder Cilk Plus haben, dürften viele Konstrukte in Rayon wiedererkennen. TBB, OpenMP und Cilk Plus und sind Laufzeit-/Spracherweiterungen für C, C++ oder Fortran, die Daten- und Task-Parallelisierung unterstützen sollen. Wie alle diese Erweiterungen verfolgt auch Rayon das Ziel, besonders ressourcenschonend und effizient zu sein.
Um zu veranschaulich, wie sich mit Rayon parallele Anwendungen erstellen lassen, dient hier die Mehrkörpersimulation (N-body simulation) als Beispiel. Dabei handelt es sich um eine Methode der numerischen Simulation, mit der sich die Kräfte und damit die Geschwindigkeit von Körpern innerhalb eines Raums bestimmen lassen. Um die Prinzipien möglichst einfach erläutern zu können, beschränken sich die Autoren auf eine vereinfachte Variante der Mehrkörpersimulation – und verzichten darauf, die bestmögliche Lösung zu entwickeln.
In Heft 12/2013 der c’t findet sich eine ausführliche Beschreibung des N-Body-Problems – parallelisiert und vektorisiert in C. Die verwendete einfache Mehrkörpersimulation hält für einen kurzen Zeitraum alle Körper fest und summiert für jeden Körper die nach den Newtonschen Gesetzen von allen anderen Körpern ausgehende Kraft auf. Die wirkende Kraft verändert die Geschwindigkeit und anschließend die Position der Körper im Raum. Die Bestimmung der Position ist dabei vernachlässigbar, da sie kaum Rechenzeit benötigt. Die Lösung wird aber online veröffentlicht, sodass die Lösung vollständig nachvollziehbar ist.
Die N-Body-Simulation benötigt eine Datenstruktur, um die Körper und Kräfte darzustellen. Zur Anwendung kommt eine Datenstruktur, die Position oder Geschwindigkeit im dreidimensionalen Raum darstellen kann. Im vorliegenden Fall wird ein Platzhalter für den Datentyp verwendet, der die drei Komponenten beschreibt. So lässt sich die Genauigkeit beim Erzeugen auf einfach- oder doppelgenaue Fließkommazahlen festlegen. Solche generalisierten Datentypen heißen in Rust (wie auch in anderen Sprachen) Generics. Ein Vektor zur Darstellung der Position und der Geschwindigkeit im dreidimensionalen Raum gestaltet sich folgendermaßen:
pub struct Vector<T> {
pub x: T,
pub y: T,
pub z: T
}
Um mit diesen Vektoren direkt rechnen zu können, ist die Definition von Standardoperationen auf diese Vektoren erforderlich. Rust bietet die Möglichkeit, sogenannte Traits zu definieren, die eine wiederverwendbare Sammlung von Methoden und Attributen darstellen. In der folgenden Definition des Traits wird die Operation += für die Datenstruktur Vektor definiert. Rust ermöglicht bei Generics, Anforderungen für den generalisierten Datentyp zu definieren. In diesem Fall muss die Addition für den Datentyp T existieren und diese wieder T als Ergebnis zurückgeben (T: Add<Output=T>). Zudem muss auch die Operation += für den Datentyp T existieren.
impl<T: Add<Output=T> + AddAssign> AddAssign for Vector<T> {
fn add_assign(&mut self, other: Vector<T>) {
self.x += other.x;
self.y += other.y;
self.z += other.z;
}
}
Da solche Vektoren häufig zum Einsatz kommen, liegen in Rust bereits Implementierungen vor. Eine der häufig verwendeten Implementierungen ist cgmath. Das Beispiel in diesem Artikel soll allerdings die Vorgehens- und Entwicklungsweise von Rust verdeutlichen und verzichtet daher auf cgmath.
Nachdem nun die Möglichkeit besteht, die Geschwindigkeit und die Position eines Köpers mit Hilfe von Vector<T> darzustellen, lässt sich das N-Body-Problem beschreiben. Grundsätzlich benötigen sowohl die Position als auch die Geschwindigkeit jeweils ein dynamisches Feld (häufig als Vektor bezeichnet – aufgrund der Verwechselungsgefahr mit Vector wird in diesem Artikel aber der Begriff dynamisches Feld benutzt), in dem für jeden Körper je ein Eintrag existiert. Solche dynamische Felder besitzen in Rust den Typ Vec. In der folgenden Darstellung eines N-Body-Systems beherbergen die Felder die zuvor definierten Vektoren, die Fließkommazahlen mit einfacher Genauigkeit (f32) für die Elemente verwenden.
pub struct NBody {
pub position: Vec<Vector<f32>>,
pub velocity: Vec<Vector<f32>>
}
Für die N-Body-Simulation muss für jeden Körper zuerst der Abstand zu allen anderen Körpern bestimmt werden und anschließend die daraus resultierende Kraft auf den ursprünglichen Körper. Anschließend lassen sich die Auswirkungen auf die Geschwindigkeit des Körpers berechnen.
Rust bietet ein Iterator-Konzept, mit dem sich einfach eine Schleife über dynamischen Felder erzeugen lässt. Im Beispiel wird sowohl über die Position als auch über die Geschwindigkeit der Körper iteriert. Die zip-Methode von Rust bietet zudem die Möglichkeit, zwei Iteratoren zu einem zusammenfassen. Danach kann mit for_each über die einzelnen Einträge iteriert werden. In Rust sind alle Variablen standardmäßig nicht-veränderbar. Soll eine Variable veränderbar sein, ist dies mit mut zu kennzeichnen. In der folgenden sequenziellen Lösung des N-Body-Systems sind die temporäre Variable für die Geschwindigkeitsveränderung sowie der Iterator über die Geschwindigkeit veränderbar, da dieser aktualisiert wird.
position.iter().zip(velocity.iter_mut())
.for_each(|(item_pi, item_vi)| {
let mut f: Vector<Precision> = Vector::new(0.0, 0.0, 0.0);
position.iter().for_each(|item_pj| {
// Newton’s law of universal gravity calculation.
let diff = *item_pj - *item_pi;
let n2 = diff * diff;
let power = 1.0 / (n2.sqrt() * n2);
f += diff*power;
});
*item_vi += f*DELTA_T;
});
Die Lösung ist rein sequenziell und basiert komplett auf Bestandteilen der Standard-Laufzeitumgebung von Rust. Rayon bietet die Möglichkeit, solchen Code einfach zu parallelisieren. Im Prinzip definiert es neue, parallele Iteratoren für alle Komponenten der Standard-Laufzeitumgebung. Dadurch ist die Parallelisierung besonders einfach zu erreichen. Nur die Iteratoren sind durch parallele Rayon-Iteratoren zu ersetzen. Die folgende parallele Lösung des N-Body-Systems benutzt standardmäßig alle auf dem System vorhandene CPU-Kerne und skaliert auf den von den Autoren verwendeten Testsystemen bis zur Anzahl der physischen Kernen.
position.par_iter().zip(velocity.par_iter_mut())
.for_each(|(item_pi, item_vi)| {
let mut f: Vector<Precision> = Vector::new(0.0, 0.0, 0.0);
position.iter().for_each(|item_pj| {
// Newton’s law of universal gravity calculation.
let diff = *item_pj - *item_pi;
let n2 = diff.square();
let power = 1.0 / (n2.sqrt() * n2);
f += diff*power;
});
*item_vi += f*DELTA_T;
});
Durch das Ownership-Prinzip von Rust, also die Garantie, dass es nur einen Besitzer des Objekts gibt, kann der Rust-Compiler mögliche Wettlaufsituationen schon zur Compile-Zeit erkennen. Hierdurch lassen sich Fehler vermeiden und somit das Entwickeln nebenläufiger Anwendungen vereinfachen.
