La mise en œuvre d'un travail de voler de la file d'attente en C/C++?

Pas de repas gratuit.

Veuillez jeter un oeil l'œuvre originale de voler papier. Ce papier est difficile à comprendre. Je sais que le papier contient théorique de la preuve plutôt que de pseudo-code. Cependant, il n'est tout simplement pas beaucoup plus version simple que TBB. Le cas échéant, il ne sera pas fournir une performance optimale. Le travail de voler lui-même subit une certaine quantité de frais généraux, de sorte optimisations et des astuces sont tout à fait important. En particulier, retire sont doit être thread-safe. La mise en œuvre de très extensible et très peu de frais généraux synchronisations sont difficiles.

Je suis vraiment vous demandez-vous pourquoi vous en avez besoin. Je pense que la bonne mise en œuvre signifie quelque chose comme TBB et Cilk. Encore une fois, le travail de voler est difficile à mettre en œuvre.

À mettre en œuvre "le travail de voler" n'est pas difficile, en théorie. Vous avez besoin d'un ensemble de files d'attente contenant des tâches qui ne travail en faisant une combinaison de l'informatique et de générer d'autres tâches à faire plus de travail. Et vous avez besoin atomique de l'accès aux files d'attente à la place nouvellement créées, les tâches dans les files d'attente. Enfin, vous avez besoin d'une procédure qui chaque tâche appels à la fin, pour trouver plus de travail pour le thread qui a exécuté la tâche; cette procédure doit regarder dans les files d'attente de travail pour trouver du travail.

La plupart de ces de vol de travail, des systèmes de faire l'hypothèse qu'il existe un petit nombre de threads (sauvegardé généralement par de vrais cœurs de processeur), et qu'il y a exactement une file d'attente de travail par thread. Ensuite, vous essayez d'abord de voler le travail à partir de votre propre file d'attente, et si elle est vide, essayez de voler les autres. Ce qui est difficile, c'est de savoir qui les files d'attente à regarder dans; de procéder à la numérisation en série pour le travail est assez cher et peut créer une énorme quantité de discorde entre les threads à la recherche de travail.

La mesure où cela est assez générique des choses avec l'un deux exceptions majeures: 1) la commutation de contextes (e.g, réglage contexte processeur registres comme une "pile") ne peut pas être déclaré en pur C ou C++. Vous pouvez résoudre ce problème en acceptant d'écrire une partie de votre forfait dans la cible de la plateforme de code machine. 2) Atomique de l'accès aux files d'attente pour un multiprocesseur ne peuvent être faites qu'en C ou C++ (en ignorant l'algorithme de Dekker), et donc vous aurez besoin de code ceux qui utilisent la langue assemblage de primitives de synchronisation comme le X86 VERROUILLAGE XCH ou de Comparer et d'Échanger. Maintenant, le code impliqués dans la mise à jour de la queuse une fois que vous avez un accès sécuritaire n'est pas très complexe, et vous pouvez facilement écrire en quelques lignes de C.

Cependant, je pense que vous trouverez, c'est que la tentative de code d'un de ces paquets en C et C++ avec un mélange assembleur est encore assez inefficace et vous finirez par la suite jusqu'le codage de l'ensemble de la chose en assembleur de toute façon. Tous de gauche qui sont en C/C++ compatible avec les points d'entrée :- }

Je l'ai fait pour notre PARLANSE parallèle langage de programmation, qui propose l'idée d'un nombre arbitrairement grand de calculs en parallèle de vivre et d'interagir (synchonizing) à tout instant. Il est mis en œuvre en coulisses sur un système X86 exactement avec un thread par CPU, et la mise en œuvre est entièrement en assembleur. Le vol de travail code est probablement 1000 lignes de total, et son délicat code parce que vous voulez qu'il soit très rapidement dans la non-cas de contestation.

Le réel à la mouche dans la pommade pour le C et le C++ est, lorsque vous créez une tâche de la représentation du travail, de combien d'espace de pile attribuez-vous? Série de programmes C/C++ éviter cette question simplement overallocating d'énormes quantités (e.g, 10 mo) de un linéaire de la pile, et personne ne s'en soucie quelle quantité d'espace de pile est gaspillée. Mais si vous pouvez créer des milliers de tâches et de les avoir tous en direct à un instant particulier, vous ne pouvez pas raisonnablement attribuer 10 mo chacun. Alors maintenant, vous avez besoin soit de déterminer statiquement combien d'espace de pile une tâche devra (Turing-dur), ou vous aurez besoin d'allouer de la pile des blocs (par exemple, par appel de fonction), qui ont largement disponibles compilateurs C/C++ ne pas faire e.g, celui que vous utilisez probablement). La dernière solution est de limiter la création de la tâche de la limiter à quelques centaines de, à tout instant, et multiplex, à quelques centaines de vraiment énormes piles parmi les tâches qui sont vivants. Vous ne pouvez pas faire la dernière si les tâches peuvent verrouillage/suspension de l'état, parce que vous allez courir dans votre seuil. Si vous ne pouvez le faire que si les tâches seulement faire le calcul. Qui semble être une très contrainte sévère.

Pour PARLANSE, nous avons construit un compilateur alloue activation des enregistrements sur le tas pour chaque appel de fonction.

Si vous êtes à la recherche d'un autonome workstealing classe de file d'attente de la mise en œuvre en C++ construit sur pthread ou boost::thread, bonne chance, à ma connaissance, il n'en est pas une.

Cependant, comme d'autres l'ont dit Cilk, TBB et Microsoft PPL ont tous workstealing la mise en œuvre sous le capot.

La question est voulez-vous utiliser un workstealing file d'attente ou de mettre en œuvre un? Si vous souhaitez les utiliser à un, puis le choix ci-dessus sont de bons points de départ tout simplement de la planification d'une "tâche" dans l'un d'eux suffit.

Comme BlueRaja dit le task_group & structured_task_group dans PPL sera ce faire, notez également que ces classes sont disponibles dans la dernière version de Intel TBB ainsi. Les boucles parallèles (parallel_for, parallel_for_each) sont également mis en œuvre avec workstealing.

Si vous devez regarder à la source plutôt que d'utiliser une mise en œuvre, le TBB est open source et Microsoft navires sources pour ses CRT, de sorte que vous pouvez faire de la spéléologie.

Vous pouvez aussi regarder Joe Duffy blog pour le C# de mise en œuvre (mais c'est du C# et le modèle de mémoire est différent).

-Rick

Le plus proche de la mise en œuvre de ce travail de voler de l'algorithme que j'ai trouvé est quelque chose qui s'appelle Laine par Karl-Filip Faxén. src /rapport /comparaison

Cette bibliothèque open source https://github.com/cpp-taskflow/cpp-taskflow prend en charge les travaux de voler des pools de threads depuis Décembre 2018.

Prendre un coup d'oeil à la WorkStealingQueue classe qui implémente le travail de voler de la file d'attente, comme décrit dans le document "Dynamique Circulaire de vol de Travail Deque," l'ISPA, 2015.

J'ai porté ce projet C C++.

L'original Steal peut l'expérience d'une lecture sale lorsque le tableau est élargi. J'ai essayé de corriger le bug, mais fini par céder parce que je n'ai pas réellement besoin d'une croissance dynamique de la pile. Au lieu d'essayer d'allouer de l'espace, la Push méthode retourne simplement false. L'appelant peut alors effectuer un spin-attendez, c'est à dire while(!stack->Push(value)){}.

#pragma once
#include <atomic>
//A lock-free stack.
//Push = single producer
//Pop = single consumer (same thread as push)
//Steal = multiple consumer
//All methods, including Push, may fail. Re-issue the request
//if that occurs (spinwait).
template<class T, size_t capacity = 131072>
class WorkStealingStack {
public:
inline WorkStealingStack() {
_top = 1;
_bottom = 1;
}
WorkStealingStack(const WorkStealingStack&) = delete;
inline ~WorkStealingStack()
{
}
//Single producer
inline bool Push(const T& item) {
auto oldtop = _top.load(std::memory_order_relaxed);
auto oldbottom = _bottom.load(std::memory_order_relaxed);
auto numtasks = oldbottom - oldtop;
if (
oldbottom > oldtop && //size_t is unsigned, validate the result is positive
numtasks >= capacity - 1) {
//The caller can decide what to do, they will probably spinwait.
return false;
}
_values[oldbottom % capacity].store(item, std::memory_order_relaxed);
_bottom.fetch_add(1, std::memory_order_release);
return true;
}
//Single consumer
inline bool Pop(T& result) {
size_t oldtop, oldbottom, newtop, newbottom, ot;
oldbottom = _bottom.fetch_sub(1, std::memory_order_release);
ot = oldtop = _top.load(std::memory_order_acquire);
newtop = oldtop + 1;
newbottom = oldbottom - 1;
//Bottom has wrapped around.
if (oldbottom < oldtop) {
_bottom.store(oldtop, std::memory_order_relaxed);
return false;
}
//The queue is empty.
if (oldbottom == oldtop) {
_bottom.fetch_add(1, std::memory_order_release);
return false;
}
//Make sure that we are not contending for the item.
if (newbottom == oldtop) {
auto ret = _values[newbottom % capacity].load(std::memory_order_relaxed);
if (!_top.compare_exchange_strong(oldtop, newtop, std::memory_order_acquire)) {
_bottom.fetch_add(1, std::memory_order_release);
return false;
}
else {
result = ret;
_bottom.store(newtop, std::memory_order_release);
return true;
}
}
//It's uncontended.
result = _values[newbottom % capacity].load(std::memory_order_acquire);
return true;
}
//Multiple consumer.
inline bool Steal(T& result) {
size_t oldtop, newtop, oldbottom;
oldtop = _top.load(std::memory_order_acquire);
oldbottom = _bottom.load(std::memory_order_relaxed);
newtop = oldtop + 1;
if (oldbottom <= oldtop)
return false;
//Make sure that we are not contending for the item.
if (!_top.compare_exchange_strong(oldtop, newtop, std::memory_order_acquire)) {
return false;
}
result = _values[oldtop % capacity].load(std::memory_order_relaxed);
return true;
}
private:
//Circular array
std::atomic<T> _values[capacity];
std::atomic<size_t> _top; //queue
std::atomic<size_t> _bottom; //stack
};

Plein de Gist (y compris les tests). J'ai seulement exécuter les tests sur une solide architecture (x86/64), pour autant que la faiblesse des architectures aller votre kilométrage peut varier si vous essayez d'utiliser cette sur, par exemple, Néon/PPC.

ne sais pas si ce serait d'aucune aide pour vous, mais jetez un oeil à cette article sur AMD développeur de réseau, c'est simple, mais devrait vous donner quelque chose d'utile