FiberTaskingLib
v2.0.4
Il s'agit d'une bibliothèque permettant le multithreading basé sur des tâches. Il permet l'exécution de graphiques de tâches avec des dépendances arbitraires. Les dépendances sont représentées sous forme de compteurs atomiques.
Sous les couvertures, le graphe de tâches est exécuté à l'aide de fibres, qui à leur tour sont exécutées sur un pool de threads de travail (un thread par cœur de processeur). Cela permet au planificateur d'attendre les dépendances sans chaînage de tâches ni changements de contexte.
Cette bibliothèque a été créée pour la première fois comme preuve de concept des idées présentées par Christian Gyrling dans son discours GDC 2015 « Parallelizing the Naughty Dog Engine Using Fibers ».
Présentation enregistrée gratuite de GDC Vault
Diapositives
# 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 ;
}Pour une excellente introduction à la fibre et à l'idée générale, je suggère de regarder l'exposé de Christian Gyrling. Il est gratuit de regarder (au moment de la rédaction) depuis le coffre-fort GDC. Cela dit, je vais donner un aperçu du fonctionnement de cette bibliothèque ci-dessous :
Une fibre est constituée d'une pile et d'un petit espace de stockage pour les registres. Il s'agit d'un contexte d'exécution très léger qui s'exécute dans un thread. Vous pouvez le considérer comme la coquille d’un véritable fil de discussion.
La beauté des fibres est que vous pouvez passer de l’une à l’autre extrêmement rapidement. Au final, un switch consiste à sauvegarder les registres, puis à échanger le pointeur d'exécution et le pointeur de pile. C'est beaucoup plus rapide qu'un changement de contexte de thread complet.
Pour répondre à cette question, comparons-le à une autre bibliothèque multithreading basée sur des tâches : les Threading Building Blocks d'Intel. TBB est une bibliothèque de tâches extrêmement soignée et réussie. Il peut gérer des graphiques de tâches très complexes et dispose d’un excellent planificateur. Cependant, imaginons un scénario :
La tâche A crée les tâches B, C et D et les envoie au planificateur
La tâche A effectue un autre travail, mais elle atteint ensuite la dépendance : B, C et D doivent être terminés.
S'ils ne sont pas terminés, nous pouvons faire 2 choses :
Spin-wait / Sommeil
Demandez au planificateur une nouvelle tâche et commencez à l'exécuter
Prenons le deuxième chemin
Le planificateur nous donne donc la tâche G et nous commençons à l'exécuter
Mais la tâche G finit par avoir également besoin d'une dépendance, nous demandons donc au planificateur une autre nouvelle tâche.
Et un autre, et un autre
Entre-temps, les tâches B, C et D sont terminées
La tâche A pourrait théoriquement être poursuivie, mais elle est enfouie dans la pile sous les tâches que nous avons reçues en attendant.
La seule façon de reprendre A est d'attendre que toute la chaîne y revienne, ou de subir un changement de contexte.
Évidemment, il s’agit d’un exemple artificiel. Et comme je l'ai dit ci-dessus, TBB dispose d'un superbe planificateur qui travaille dur pour atténuer ce problème. Cela dit, les fibres peuvent contribuer à éliminer complètement le problème en permettant une commutation peu coûteuse entre les tâches. Cela nous permet d'isoler l'exécution d'une tâche d'une autre, évitant ainsi l'effet « d'enchaînement » décrit ci-dessus.
File d'attente des tâches - Une file d'attente « ordinaire » pour contenir les tâches en attente d'exécution. Dans le code actuel, il existe une file d'attente « haute priorité » et une file d'attente « basse priorité ».
Pool de fibres : un pool de fibres utilisé pour passer à de nouvelles tâches pendant que la tâche en cours attend une dépendance. Les fibres exécutent les tâches
Threads de travail : 1 par cœur de processeur logique. Ceux-ci font circuler les fibres.
Tâches en attente - Toutes les fibres/tâches qui attendent qu'une dépendance soit remplie. Les dépendances sont représentées avec WaitGroups
Des tâches peuvent être créées sur la pile. Il s'agit simplement d'une simple structure avec un pointeur de fonction et un void *arg facultatif à transmettre à la fonction :
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}Vous planifiez l'exécution d'une tâche en appelant TaskScheduler::AddTasks()
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);Les tâches sont ajoutées à la file d'attente et d'autres threads (ou celui en cours, lorsqu'il a terminé la tâche en cours) peuvent commencer à les exécuter lorsqu'ils sont retirés de la file d'attente.
AddTasks peut éventuellement prendre un pointeur vers un WaitGroup. Si vous le faites, la valeur de WaitGroup sera incrémentée du nombre de tâches mises en file d'attente. Chaque fois qu'une tâche se termine, le WaitGroup sera décrémenté de manière atomique. Vous pouvez utiliser cette fonctionnalité pour créer des dépendances entre les tâches. Vous faites cela avec la fonction
void WaitGroup::Wait ();C'est là que les fibres entrent en jeu. Si la valeur de WaitGroup == 0, la fonction renvoie trivialement. Dans le cas contraire, le planificateur déplacera la fibre actuelle dans une liste de fibres en attente dans le WaitGroup et récupérera une nouvelle fibre dans le Fiber Pool . La nouvelle fibre extrait une tâche de la file d'attente des tâches et commence l'exécution avec celle-ci.
Mais qu’en est-il de la tâche/fibre que nous avons stockée dans le WaitGroup ? Quand finira-t-il d’être exécuté ?
Lorsque la valeur WaitGroup atteint zéro après décrémentation, nous rajoutons toutes les fibres en attente dans la file d'attente du TaskScheduler. La prochaine fois qu'un thread changera de fibre (soit parce que la fibre actuelle est terminée, soit parce qu'elle a appelé WaitGroup::Wait() ), la tâche prête sera reprise et reprise là où elle s'était arrêtée.
Généralement, vous ne devriez pas utiliser de Mutex dans le code fibre, pour deux raisons :
Si vous prenez un mutex et appelez WaitGroup::Wait(), lorsque Wait() reprend, votre code pourrait se trouver sur un autre thread. Le déverrouillage du mutex aura un comportement indéfini et conduira probablement à une impasse
Les conflits de mutex bloqueront les threads de travail. Et comme nous ne souscrivons généralement pas trop de threads aux cœurs, cela laisse les cœurs inactifs.
Pour résoudre ce problème, nous avons créé Fibtex. Il implémente l'interface verrouillable std, vous pouvez donc l'utiliser avec tous vos wrappers préférés (std::lock_guard, std::unique_lock, etc.). Il est implémenté en coulisses avec des attentes de fibre, donc si un Fibtex est verrouillé, un serveur peut passer à une autre tâche et effectuer un travail précieux
Lorsqu'une fibre est reprise après un WaitGroup::Wait() ou un Fibtex::lock(), il n'y a aucune garantie qu'elle reprendra sur le même thread sur lequel elle s'exécutait lorsqu'elle a été suspendue. Pour la plupart du code, c'est très bien. Cependant, certaines bibliothèques ont des hypothèses fortes. Par exemple, dans DirectX, vous devez soumettre la trame finale à partir du même thread qui a créé la chaîne d'échange. Ainsi, certains codes devront garantir que les fibres reprennent sur le même thread où elles s'exécutaient lorsqu'elles étaient suspendues. Pour ce faire, vous pouvez utiliser l'argument pinToCurrentThread . Lorsqu'il est défini sur true , le planificateur garantira que la fibre reprise s'exécutera sur le même thread. Cet argument est disponible pour WaitGroup::Wait() et Fibtext::lock(). REMARQUE : l'épinglage de thread est plus coûteux que le comportement par défaut et peut potentiellement entraîner une reprise beaucoup plus lente de la tâche en question (puisqu'il nécessite que le thread épinglé termine la tâche qu'il est en cours d'exécution). Par conséquent, il ne doit être utilisé qu’en cas de véritable nécessité.
Compilateur C++11
CMake 3.2 ou supérieur
Cambre | Fenêtres | Linux | OS X | IOS | Androïde |
bras | Besoin de tests | Entièrement pris en charge | Théoriquement | Théoriquement | Théoriquement |
bras_64 | Besoin de tests | Entièrement pris en charge | Besoin de tests | Théoriquement | Théoriquement |
x86 | Entièrement pris en charge | Besoin de tests | Besoin de tests | ||
x86_64 | Entièrement pris en charge | Entièrement pris en charge | Entièrement pris en charge |
FiberTaskingLib est une version CMake standard. Cependant, pour des instructions détaillées sur la façon de créer et d'inclure la bibliothèque dans votre propre projet, consultez la page de documentation.
La bibliothèque est sous licence Apache 2.0. Cependant, FiberTaskingLib distribue et utilise le code d'autres projets Open Source qui disposent de leurs propres licences :
Fourche de contexte Boost : licence Boost v1.0
Catch2 : Licence Boost v1.0
Les contributions sont les bienvenues. Voir la page de contribution pour plus de détails.
Cette implémentation a été quelque chose que j'ai créé parce que je pensais que la présentation de Christian était vraiment intéressante et que je voulais l'explorer moi-même. Le code est toujours en chantier et j'aimerais entendre vos critiques sur la façon dont je pourrais l'améliorer. Je vais continuer à travailler sur ce projet et l'améliorer du mieux possible.
