Quelles sont les contraintes pour l'utilisateur qui utilise les algorithmes parallèles de STL?

Question

À Jacksonville réunion de la proposition P0024r2 efficacement en adoptant les spécifications du Parallélisme TS a été accepté dans le C++17 (projet). Cette proposition ajoute surcharges pour un grand nombre d'algorithmes prenant une politique d'exécution des argument pour indiquer quel type de parallélisme doit être envisagée. Il y a trois stratégies d'exécution déjà défini en <execution> (20.19.2 [exécution]):

• std::execution::sequenced_policy (20.19.4 [execpol.seq]) avec un constexpr objet std::execution::seq (20.19.7 [parallèles.execpol.objets]) pour indiquer l'exécution séquentielle similaire à l'appel les algorithmes sans une politique d'exécution.
• std::execution::parallel_policy (20.19.5 [execpol.par]) avec un constexpr objet std::execution::par (20.19.7 [parallèles.execpol.objets]) pour indiquer l'exécution d'algorithmes potentiellement l'utilisation de plusieurs threads.
• std::execution::parallel_unsequenced_policy (20.19.6 [execpol.vec]) avec un constexpr objet std::execution::par_unseq (20.19.7 [parallèles.execpol.objets])pour indiquer l'exécution des algorithmes en utilisant éventuellement vecteur d'exécution et/ou de plusieurs threads.

La STL algorithmes prennent généralement des objets définis par l'utilisateur (itérateurs, les objets de fonction) comme arguments. Quelles sont les contraintes sur les objets définis par l'utilisateur afin de les rendre utilisables avec les algorithmes parallèles à l'aide de la norme de l'exécution des politiques?

Par exemple, lors de l'utilisation d'un algorithme comme dans l'exemple ci-dessous, quelles sont les implications pour l' FwdIt et Predicate?

template <typename FwdIt, typename Predicate>
FwdIt call_remove_if(FwdIt begin, FwdIt end, Predicate predicate) {
    return std::remove_if(std::execution::par, begin, end, predicate);
}

Answer 1

La réponse courte est que l' accès à l'élément de fonctions (essentiellement les opérations requises par les algorithmes sur les différents arguments; voir ci-dessous pour plus de détails) utilisé avec des algorithmes à l'aide de la politique d'exécution std::execution::parallel ne sont pas autorisés à cause de données des courses ou morts-les verrous. L'accès à l'élément de fonctions utilisées avec des algorithmes à l'aide de la politique d'exécution std::execution::parallel_unsequenced_policy de plus ne pouvez pas utiliser le blocage de la synchronisation.

Les Détails

La description est basée sur le bulletin de vote document N4604. Je n'ai pas vérifié si certaines clauses ont été modifiés en réponse à l'organisme national des commentaires (d'une vérification sommaire semble impliquer qu'il n'y avait pas de modifications jusqu'à présent).

L'article 25.2 [algorithmes.en parallèle] spécifie la sémantique des algorithmes parallèles. Il y a des contraintes multiples qui ne s'appliquent pas aux algorithmes de ne pas prendre une stratégie d'exécution, décomposé en plusieurs sections:

1. Dans 25.2.2 [algorithmes.en parallèle.utilisateur] limite de ce prédicat fonctions peuvent faire pour leurs arguments:

   La fonction des objets transmis en parallèle des algorithmes comme des objets de type Predicate, BinaryPredicate, Compare, et BinaryOperation ne doit pas, directement ou indirectement, de modifier des objets par l'intermédiaire de leurs arguments.

   La façon dont la clause est écrit, il semble que les objets eux-mêmes peuvent être modifiées tant que les autres contraintes (voir ci-dessous) sont respectées. Notez que cette contrainte est indépendant de la politique d'exécution et, par conséquent, s'applique même lorsque l'utilisation de std::execution::sequenced_policy. La réponse est plus compliquée que cela et il semble que le cahier des charges est actuellement involontairement sur-contraintes (voir le dernier paragraphe ci-dessous).

2. Dans 25.2.3 [algorithmes.en parallèle.exec] ajoute des contraintes sur l' accès à l'élément de fonctions (voir ci-dessous) qui sont spécifiques aux différentes politiques d'exécution:

   • Lors de l'utilisation d' std::execution::sequenced_policy l'accès à l'élément de fonctions sont toutes appelées à partir de la même thread, c'est à dire, de l'exécution n'est entrelacé dans n'importe quelle forme.
   • Lors de l'utilisation d' std::execution::parallel_policy différents threads peut invoquer l'accès à l'élément de fonctions simultanément à partir de différents threads. Invoquant l'accès à l'élément de fonctions de différents threads n'est pas autorisé à cause de données à des courses ou à cause de mort-écluses. Cependant, les invocations de l'accès à l'élément à partir du même thread sont [pour une période indéterminée] de la séquence, c'est à dire, il n'y a pas d'entrelacement des invocations de l'accès à l'élément de la fonction de la même thread. Par exemple, si un Predicate utilisé avec std::execution::par compte comment il est souvent appelé, le comte devra être correctement synchronisées.

   • Lors de l'utilisation d' std::execution::parallel_unsequenced_policy de l'invocation de l'accès à l'élément de fonctions peuvent être entrelacées à la fois entre les différents thread ainsi que dans un thread d'exécution. Qui est, l'utilisation d'un blocage des primitives de synchronisation (comme un std::mutex) peut causer des morts-lock le même thread peut essayer de synchroniser plusieurs fois (et, par exemple, essayer de verrouiller la même mutex plusieurs fois). Lors de l'utilisation de fonctions de bibliothèque standard pour l'accès à l'élément de fonctions de la contrainte de la norme (25.2.3 [algorithmes.en parallèle.exec] paragraphe 4):

     Une fonction de la bibliothèque standard est la vectorisation-dangereuse si elle est spécifiée pour se synchroniser avec un autre invocation de la fonction, ou d'une autre, l'invocation de la fonction est spécifiée pour se synchroniser avec elle, et si elle n'est pas une allocation de la mémoire ou de la fonction de libération. La vectorisation-dangereux fonctions de bibliothèque standard ne peut être invoquée par le code de l'utilisateur appelé à partir d' execution::parallel_unsequenced_policy algorithmes.

   • Ce qui se passe lors de l'utilisation de la mise en œuvre définies les stratégies d'exécution est, sans surprise, la mise en œuvre définies.

3. Dans 25.2.4 [algorithme.en parallèle.exception] l'utilisation d'exceptions générées à partir de l'accès à l'élément de fonctions est une sorte de contrainte: lorsqu'un accès à l'élément de la fonction lève une exception, std::terminate() est appelé. C'est, il est possible de lever une exception, mais il est peu probable que l'issue est souhaitable. Notez que std::terminate() sera même appelé lors de l'utilisation d' std::execution::sequenced_policy.

Accès À L'Élément De Fonctions

Les contraintes ci-dessus utilisent le terme d' accès à l'élément de fonction. Ce terme est défini dans 25.2.1 [algorithme.en parallèle.defns] le paragraphe 2 de l'. Il existe quatre groupes de fonctions classés comme des accès à l'élément de fonctions:

• Toutes les opérations des catégories d'itérateurs que l'algorithme est instancié avec.
• Opérations sur les éléments de la séquence qui sont requis par son cahier des charges.
• Fourni par l'utilisateur de la fonction des objets à appliquer lors de l'exécution de l'algorithme, si requis par le cahier des charges.
• Des opérations sur ces objets de fonction, conformément à la spécification.

Essentiellement, l'accès à l'élément fonctions sont toutes les opérations qui sont la norme se réfère explicitement à la définition des algorithmes ou les concepts utilisés avec ces algorithmes. Les fonctions ne sont pas mentionnés et, par exemple, détecté à être présents (par exemple, à l'aide de SFINAE) ne sont pas limitées et, effectivement, ne peut pas être appelée à partir de la algorithmes parallèles imposant des contraintes de synchronisation sur leur utilisation.

Le Problème

C'est un peu le concernant qu'il semble y avoir aucune garantie que les objets de la [mutation] accès à l'élément de fonctions sont appliquées sont différentes entre les différents threads. En particulier, je ne vois aucune garantie que l'itérateur opérations appliquées à un itérateur objet ne peut pas être appliquée de la même itérateur objet de deux threads différents! L'implication est que, par exemple, operator++() sur un itérateur objet devra en quelque sorte la synchronisation de son état. Je ne vois pas comment, par exemple, operator==() pourrait faire quelque chose d'utile si l'objet est modifié dans un thread différent. Il semble involontaire que les opérations sur le même objet doivent être synchronisé comme il n'a pas de sens d'appliquer [mutation] accès à l'élément de fonctions simultanément à un objet. Cependant, je ne peux pas voir tout le texte indiquant que des objets différents sont utilisés (je suppose, j'ai besoin de lever un défaut pour cette).