FiberTaskingLib
v2.0.4
Dies ist eine Bibliothek zur Ermöglichung von aufgabenbasiertem Multithreading. Es ermöglicht die Ausführung von Aufgabendiagrammen mit beliebigen Abhängigkeiten. Abhängigkeiten werden als atomare Zähler dargestellt.
Unter der Decke wird der Aufgabengraph mithilfe von Fasern ausgeführt, die wiederum auf einem Pool von Arbeitsthreads (ein Thread pro CPU-Kern) ausgeführt werden. Dadurch kann der Scheduler auf Abhängigkeiten warten, ohne dass Aufgaben verkettet oder Kontextwechsel vorgenommen werden müssen.
Diese Bibliothek wurde ursprünglich als Proof of Concept der Ideen erstellt, die Christian Gyrling in seinem GDC-Vortrag 2015 „Parallelizing the Naughty Dog Engine Using Fibers“ vorgestellt hat.
Kostenlose aufgezeichnete GDC Vault-Präsentation
Folien
# include " ftl/task_scheduler.h "
# include " ftl/wait_group.h "
# include < assert.h >
# include < stdint.h >
struct NumberSubset {
uint64_t start;
uint64_t end;
uint64_t total;
};
void AddNumberSubset (ftl::TaskScheduler *taskScheduler, void *arg) {
( void )taskScheduler;
NumberSubset *subset = reinterpret_cast <NumberSubset *>(arg);
subset-> total = 0 ;
while (subset-> start != subset-> end ) {
subset-> total += subset-> start ;
++subset-> start ;
}
subset-> total += subset-> end ;
}
/* *
* Calculates the value of a triangle number by dividing the additions up into tasks
*
* A triangle number is defined as:
* Tn = 1 + 2 + 3 + ... + n
*
* The code is checked against the numerical solution which is:
* Tn = n * (n + 1) / 2
*/
int main () {
// Create the task scheduler and bind the main thread to it
ftl::TaskScheduler taskScheduler;
taskScheduler. Init ();
// Define the constants to test
constexpr uint64_t triangleNum = 47593243ULL ;
constexpr uint64_t numAdditionsPerTask = 10000ULL ;
constexpr uint64_t numTasks = (triangleNum + numAdditionsPerTask - 1ULL ) / numAdditionsPerTask;
// Create the tasks
// FTL allows you to create Tasks on the stack.
// However, in this case, that would cause a stack overflow
ftl::Task *tasks = new ftl::Task[numTasks];
NumberSubset *subsets = new NumberSubset[numTasks];
uint64_t nextNumber = 1ULL ;
for ( uint64_t i = 0ULL ; i < numTasks; ++i) {
NumberSubset *subset = &subsets[i];
subset-> start = nextNumber;
subset-> end = nextNumber + numAdditionsPerTask - 1ULL ;
if (subset-> end > triangleNum) {
subset-> end = triangleNum;
}
tasks[i] = { AddNumberSubset, subset };
nextNumber = subset-> end + 1 ;
}
// Schedule the tasks
ftl::WaitGroup wg (&taskScheduler);
taskScheduler. AddTasks (numTasks, tasks, ftl::TaskPriority::Normal, &wg);
// FTL creates its own copies of the tasks, so we can safely delete the memory
delete[] tasks;
// Wait for the tasks to complete
wg. Wait ();
// Add the results
uint64_t result = 0ULL ;
for ( uint64_t i = 0 ; i < numTasks; ++i) {
result += subsets[i]. total ;
}
// Test
assert (triangleNum * (triangleNum + 1ULL ) / 2ULL == result);
( void )result;
// Cleanup
delete[] subsets;
// The destructor of TaskScheduler will shut down all the worker threads
// and unbind the main thread
return 0 ;
}Für eine gute Einführung in das Thema Glasfaser und die allgemeine Idee würde ich vorschlagen, sich den Vortrag von Christian Gyrling anzusehen. Es ist (zum Zeitpunkt des Verfassens dieses Artikels) kostenlos aus dem GDC-Tresor anzusehen. Dennoch werde ich im Folgenden einen Überblick über die Funktionsweise dieser Bibliothek geben:
Eine Faser besteht aus einem Stapel und einem kleinen Speicherraum für Register. Es handelt sich um einen sehr einfachen Ausführungskontext, der innerhalb eines Threads ausgeführt wird. Sie können es sich als eine Hülle eines tatsächlichen Threads vorstellen.
Das Schöne an Fasern ist, dass man extrem schnell zwischen ihnen wechseln kann. Letztendlich besteht ein Wechsel darin, Register zu speichern und dann den Ausführungszeiger und den Stapelzeiger zu tauschen. Dies ist viel schneller als ein vollständiger Thread-Kontextwechsel.
Um diese Frage zu beantworten, vergleichen wir sie mit einer anderen aufgabenbasierten Multithreading-Bibliothek: den Threading Building Blocks von Intel. TBB ist eine äußerst ausgefeilte und erfolgreiche Tasking-Bibliothek. Es kann wirklich komplexe Aufgabendiagramme verarbeiten und verfügt über einen hervorragenden Planer. Stellen wir uns jedoch ein Szenario vor:
Aufgabe A erstellt die Aufgaben B, C und D und sendet sie an den Planer
Aufgabe A führt andere Arbeiten aus, trifft dann aber auf die Abhängigkeit: B, C und D müssen abgeschlossen sein.
Wenn sie noch nicht fertig sind, können wir zwei Dinge tun:
Spin-warten / Schlafen
Bitten Sie den Planer um eine neue Aufgabe und beginnen Sie mit deren Ausführung
Nehmen wir den zweiten Weg
Der Planer gibt uns also Aufgabe G und wir beginnen mit der Ausführung
Aber auch Aufgabe G benötigt letztendlich eine Abhängigkeit, also bitten wir den Planer um eine weitere neue Aufgabe
Und noch einer und noch einer
Inzwischen sind die Aufgaben B, C und D abgeschlossen
Aufgabe A könnte theoretisch fortgesetzt werden, sie liegt jedoch im Stapel unter den Aufgaben vergraben, die wir während des Wartens erhalten haben
Die einzige Möglichkeit, A fortzusetzen, besteht darin, darauf zu warten, dass sich die gesamte Kette wieder auflöst, oder einen Kontextwechsel zu erleiden.
Offensichtlich ist dies ein erfundenes Beispiel. Und wie ich oben sagte, verfügt TBB über einen großartigen Planer, der hart daran arbeitet, dieses Problem zu lindern. Allerdings können Glasfasern dazu beitragen, das Problem vollständig zu beseitigen, indem sie einen kostengünstigen Wechsel zwischen Aufgaben ermöglichen. Dadurch können wir die Ausführung einer Aufgabe von einer anderen isolieren und so den oben beschriebenen „Verkettungseffekt“ verhindern.
Aufgabenwarteschlange – Eine „normale“ Warteschlange zum Speichern der Aufgaben, die auf ihre Ausführung warten. Im aktuellen Code gibt es eine Warteschlange mit „hoher Priorität“ und eine Warteschlange mit „niedriger Priorität“.
Fiber-Pool – Ein Fiber-Pool, der für den Wechsel zu neuen Aufgaben verwendet wird, während die aktuelle Aufgabe auf eine Abhängigkeit wartet. Fasern führen die Aufgaben aus
Worker-Threads – 1 pro logischem CPU-Kern. Diese verlaufen durch die Fasern.
Wartende Aufgaben – Alle Fasern/Aufgaben, die darauf warten, dass eine Abhängigkeit erfüllt wird. Abhängigkeiten werden mit WaitGroups dargestellt
Auf dem Stapel können Aufgaben erstellt werden. Es handelt sich lediglich um eine einfache Struktur mit einem Funktionszeiger und einem optionalen void *arg, das an die Funktion übergeben wird:
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}Sie planen die Ausführung einer Aufgabe, indem Sie TaskScheduler::AddTasks() aufrufen.
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);Die Aufgaben werden zur Warteschlange hinzugefügt und andere Threads (oder der aktuelle, wenn er mit der aktuellen Aufgabe fertig ist) können mit der Ausführung beginnen, wenn sie aus der Warteschlange entfernt werden.
AddTasks kann optional einen Zeiger auf eine WaitGroup annehmen. Wenn Sie dies tun, wird der Wert der WaitGroup um die Anzahl der in der Warteschlange befindlichen Aufgaben erhöht. Jedes Mal, wenn eine Aufgabe abgeschlossen ist, wird die WaitGroup atomar dekrementiert. Mit dieser Funktionalität können Sie Abhängigkeiten zwischen Aufgaben erstellen. Das machen Sie mit der Funktion
void WaitGroup::Wait ();Hier kommen Fasern ins Spiel. Wenn der Wert von WaitGroup == 0 ist, kehrt die Funktion trivialerweise zurück. Wenn nicht, verschiebt der Scheduler die aktuelle Faser in eine Liste wartender Fasern in der WaitGroup und holt sich eine neue Faser aus dem Fiber Pool . Die neue Fiber entfernt eine Aufgabe aus der Aufgabenwarteschlange und beginnt damit mit der Ausführung.
Aber was ist mit der Aufgabe/Faser, die wir in der WaitGroup gespeichert haben? Wann wird die Ausführung abgeschlossen sein?
Wenn der WaitGroup-Wert durch Dekrementieren Null erreicht, fügen wir alle wartenden Fibers wieder in die Warteschlange im TaskScheduler ein. Wenn ein Thread das nächste Mal Fasern wechselt (entweder weil die aktuelle Faser fertig ist oder weil sie WaitGroup::Wait() aufgerufen hat), wird die fertige Aufgabe übernommen und dort fortgesetzt, wo sie aufgehört hat.
Im Allgemeinen sollten Sie aus zwei Gründen keine Mutexe im Fiber-Code verwenden:
Wenn Sie einen Mutex nehmen und WaitGroup::Wait() aufrufen, könnte sich Ihr Code beim Fortsetzen von Wait() in einem anderen Thread befinden. Das Entsperren des Mutex ist ein undefiniertes Verhalten und führt wahrscheinlich zu einem Deadlock
Mutex-Konflikte blockieren die Arbeitsthreads. Und da wir die Threads der Kerne im Allgemeinen nicht überbelegen, bleiben die Kerne im Leerlauf.
Um dieses Problem zu lösen, haben wir Fibtex erstellt. Es implementiert die std-sperrbare Schnittstelle, sodass Sie sie mit allen Ihren bevorzugten Wrappern (std::lock_guard, std::unique_lock usw.) verwenden können. Es wird hinter den Kulissen mit Fiber-Wartezeiten implementiert, sodass ein Kellner dies tun kann, wenn ein Fibtex gesperrt ist Wechseln Sie zu einer anderen Aufgabe und leisten Sie wertvolle Arbeit
Wenn eine Fiber nach einem WaitGroup::Wait() oder einem Fibtex::lock() wieder aufgenommen wird, gibt es keine Garantie dafür, dass sie in demselben Thread fortgesetzt wird, in dem sie ausgeführt wurde, als sie angehalten wurde. Für den meisten Code ist das in Ordnung. Bestimmte Bibliotheken haben jedoch starke Annahmen. Beispielsweise müssen Sie in DirectX die endgültige Frame-Übermittlung über denselben Thread durchführen, der die Swap-Kette erstellt hat. Daher muss ein gewisser Code garantieren, dass Fasern in demselben Thread wieder aufgenommen werden, in dem sie ausgeführt wurden, als sie angehalten wurden. Dazu können Sie das Argument pinToCurrentThread verwenden. Wenn der Scheduler auf true gesetzt ist, garantiert er, dass die wiederaufgenommene Fiber im selben Thread ausgeführt wird. Dieses Argument ist für WaitGroup::Wait() und Fibtext::lock() verfügbar. HINWEIS: Das Anheften von Threads ist teurer als das Standardverhalten und kann möglicherweise zu einer viel langsameren Wiederaufnahme der betreffenden Aufgabe führen (da der angeheftete Thread die Aufgabe beenden muss, die er gerade ausführt). Daher sollte es nur verwendet werden, wenn es wirklich notwendig ist.
C++11-Compiler
CMake 3.2 oder höher
Bogen | Windows | Linux | OS X | iOS | Android |
Arm | Muss getestet werden | Vollständig unterstützt | Theoretisch | Theoretisch | Theoretisch |
arm_64 | Muss getestet werden | Vollständig unterstützt | Muss getestet werden | Theoretisch | Theoretisch |
x86 | Vollständig unterstützt | Muss getestet werden | Muss getestet werden | ||
x86_64 | Vollständig unterstützt | Vollständig unterstützt | Vollständig unterstützt |
FiberTaskingLib ist ein Standard-CMake-Build. Detaillierte Anweisungen zum Erstellen und Einbinden der Bibliothek in Ihr eigenes Projekt finden Sie jedoch auf der Dokumentationsseite.
Die Bibliothek ist unter der Apache 2.0-Lizenz lizenziert. FiberTaskingLib vertreibt und verwendet jedoch Code aus anderen Open-Source-Projekten, die über eigene Lizenzen verfügen:
Boost Context Fork: Boost-Lizenz v1.0
Catch2: Boost-Lizenz v1.0
Beiträge sind herzlich willkommen. Weitere Einzelheiten finden Sie auf der Beitragsseite.
Diese Implementierung habe ich erstellt, weil ich Christians Präsentation wirklich interessant fand und sie selbst erkunden wollte. Der Code ist noch in Arbeit und ich würde gerne Ihre Kritik hören, wie ich ihn verbessern könnte. Ich werde weiter an diesem Projekt arbeiten und es so gut wie möglich verbessern.
