Partitionneurs personnalisés pour PLINQ et la bibliothèque parallèle de tâches (TPL)

Pour paralléliser une opération sur une source de données, l’une des étapes essentielles consiste à partitionner la source en plusieurs sections accessibles simultanément par plusieurs threads. PLINQ et la bibliothèque parallèle de tâches (TPL) fournissent des partitionneurs par défaut qui fonctionnent de façon transparente lorsque vous écrivez une requête parallèle ou une boucle ForEach. Pour des scénarios plus élaborés, vous pouvez incorporer votre propre partitionneur.

Types de partitionnement

Il existe de nombreuses façons de partitionner une source de données. Dans les approches les plus efficaces, plusieurs threads coopèrent pour traiter la séquence source d’origine, au lieu de séparer physiquement la source en plusieurs sous-séquences. Pour des tableaux et d’autres sources indexées telles que des collections IList où la longueur est connue à l’avance, le partitionnement par plage de valeurs est le type de partitionnement le plus simple. Chaque thread reçoit des index de début et de fin uniques pour pouvoir traiter sa plage de la source, sans remplacer ni être remplacé par un autre thread. La seule surcharge impliquée dans le partitionnement par plage de valeurs est le travail initial consistant à créer les plages : aucune synchronisation supplémentaire n’est requise par la suite. Par conséquent, cette méthode offre de bonnes performances tant que la charge de travail est répartie uniformément. L’inconvénient du partitionnement par plage de valeurs réside dans le fait que si un thread se termine plus tôt, il ne peut pas aider les autres threads à terminer leur travail.

Pour les listes liées ou d’autres collections dont la longueur n’est pas connue, vous pouvez utiliser le partitionnement par segments. Dans le partitionnement par segments, chaque thread ou tâche d’une boucle parallèle ou d’une requête consomme un certain nombre d’éléments de la source dans un segment, les traite, puis revient pour extraire des éléments supplémentaires. Le partitionneur s’assure que tous les éléments sont distribués et qu’il n’y a pas de doublons. Un segment peut être de n’importe quelle taille. Par exemple, le partitionneur présenté dans la section Guide pratique pour implémenter des partitions dynamiques crée des segments qui ne contiennent qu’un seul élément. Tant que les segments ne sont pas trop volumineux, ce type de partitionnement effectue, par nature, un équilibrage de charge car l’affectation des éléments aux threads n’est pas prédéfinie. Cependant, le partitionneur déclenche la surcharge de synchronisation chaque fois que le thread a besoin d’un autre segment. Le niveau de synchronisation effectué dans ce cas est inversement proportionnel à la taille des segments.

En règle générale, le partitionnement par plage de valeurs n’est plus rapide que lorsque la durée d’exécution du délégué est faible à modérée, que la source comporte un grand nombre d’éléments, et que le travail total de chaque partition est à peu près équivalent. Le partitionnement par segments est donc généralement plus rapide dans la plupart des cas. Sur les sources comportant un petit nombre d’éléments ou avec des durées d’exécution plus longues pour le délégué, les performances du partitionnement par plage de valeurs et du partitionnement par segments sont équivalentes.

Les partitionneurs TPL prennent également en charge un nombre dynamique de partitions. Cela signifie qu’ils peuvent créer des partitions à la volée, par exemple lorsque la boucle ForEach génère une nouvelle tâche. Cette fonctionnalité permet la mise à l’échelle du partitionneur par rapport à la boucle elle-même. Par nature, les partitionneurs dynamiques effectuent également un équilibrage de charge. Lorsque vous créez un partitionneur personnalisé, vous devez faire en sortie que le partitionnement dynamique soit utilisable par une boucle ForEach.

Configuration des partitionneurs d’équilibrage de charge pour PLINQ

Certaines surcharges de la méthode Partitioner.Create vous permettent de créer un partitionneur pour un tableau ou une source IList et de spécifier s’il doit tenter d’équilibrer la charge de travail entre les threads. Lorsque le partitionneur est configuré pour l’équilibrage de charge, le partitionnement par segments est utilisé, et les éléments sont transmis, à la demande, par petits segments à chaque partition. Cette approche garantit que toutes les partitions disposent d’éléments à traiter jusqu'à ce que la boucle ou la requête soit terminée. Une surcharge supplémentaire peut être utilisée pour fournir le partitionnement d’équilibrage de charge de n’importe quelle source IEnumerable.

En général, l’équilibrage de charge requiert que les partitions sollicitent fréquemment le partitionneur pour obtenir des éléments. En revanche, un partitionneur qui effectue un partitionnement statique peut affecter les éléments à chaque partitionneur en même temps à l’aide d’un partitionnement par plage de valeurs ou par segments. Cette méthode nécessite moins de surcharge que l’équilibrage de charge, mais elle peut prendre plus de temps à s’exécuter si un thread se retrouve avec beaucoup plus de travail que les autres. Par défaut, lorsqu’il reçoit un objet IList ou un tableau, PLINQ utilise toujours le partitionnement par plage de valeurs sans équilibrage de charge. Pour activer l’équilibrage de charge pour PLINQ, utilisez la méthode Partitioner.Create, comme indiqué dans l’exemple suivant.

// Static partitioning requires indexable source. Load balancing
// can use any IEnumerable.
var nums = Enumerable.Range(0, 100000000).ToArray();

// Create a load-balancing partitioner. Or specify false for static partitioning.
Partitioner<int> customPartitioner = Partitioner.Create(nums, true);

// The partitioner is the query's data source.
var q = from x in customPartitioner.AsParallel()
        select x * Math.PI;

q.ForAll((x) =>
{
    ProcessData(x);
});

' Static number of partitions requires indexable source.
Dim nums = Enumerable.Range(0, 100000000).ToArray()

' Create a load-balancing partitioner. Or specify false For  Shared partitioning.
Dim customPartitioner = Partitioner.Create(nums, True)

' The partitioner is the query's data source.
Dim q = From x In customPartitioner.AsParallel()
        Select x * Math.PI

q.ForAll(Sub(x) ProcessData(x))

La meilleure méthode pour déterminer si vous devez utiliser l’équilibrage de charge dans un scénario donné consiste à faire des essais et à mesurer la durée des opérations avec des charges et des configurations d’ordinateur représentatives. Par exemple, le partitionnement statique peut accélérer considérablement les opérations sur un ordinateur multicœur doté de quelques cœurs, mais il peut entraîner des ralentissements sur les ordinateurs qui disposent de nombreux cœurs.

Le tableau ci-dessous répertorie les surcharges disponibles avec la méthode Create. L’utilisation de ces partitionneurs ne se limite pas à PLINQ ou à Task. Ils peuvent également être utilisés avec n’importe quelle construction parallèle personnalisée.

Configuration de partitionneurs de plages statiques pour Parallel.ForEach

Dans une boucle For, le corps de la boucle est transmis à la méthode en tant que délégué. Le coût d’un appel à ce délégué est équivalent à celui d’un appel à une méthode virtuelle. Dans certains scénarios, le corps d’une boucle parallèle peut être suffisamment petit de sorte que le coût d’un appel au délégué sur chaque itération de la boucle devient important. Dans ce cas, vous pouvez utiliser une des surcharges Create pour créer un objet IEnumerable<T> de partitions par plages de valeurs sur les éléments sources. Vous pouvez ensuite transmettre cette collection de plages de valeurs à une méthode ForEach dont le corps se compose d’une boucle for standard. L’avantage de cette approche est que le coût d’un appel au délégué n’est généré qu’une seule fois par plage au lieu d’une seule fois par élément. L'exemple suivant illustre le modèle de base.

using System;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {

        // Source must be array or IList.
        var source = Enumerable.Range(0, 100000).ToArray();

        // Partition the entire source array.
        var rangePartitioner = Partitioner.Create(0, source.Length);

        double[] results = new double[source.Length];

        // Loop over the partitions in parallel.
        Parallel.ForEach(rangePartitioner, (range, loopState) =>
        {
            // Loop over each range element without a delegate invocation.
            for (int i = range.Item1; i < range.Item2; i++)
            {
                results[i] = source[i] * Math.PI;
            }
        });

        Console.WriteLine("Operation complete. Print results? y/n");
        char input = Console.ReadKey().KeyChar;
        if (input == 'y' || input == 'Y')
        {
            foreach(double d in results)
            {
                Console.Write("{0} ", d);
            }
        }
    }
}

Imports System.Threading.Tasks
Imports System.Collections.Concurrent

Module PartitionDemo

    Sub Main()
        ' Source must be array or IList.
        Dim source = Enumerable.Range(0, 100000).ToArray()

        ' Partition the entire source array. 
        ' Let the partitioner size the ranges.
        Dim rangePartitioner = Partitioner.Create(0, source.Length)

        Dim results(source.Length - 1) As Double

        ' Loop over the partitions in parallel. The Sub is invoked
        ' once per partition.
        Parallel.ForEach(rangePartitioner, Sub(range, loopState)

                                               ' Loop over each range element without a delegate invocation.
                                               For i As Integer = range.Item1 To range.Item2 - 1
                                                   results(i) = source(i) * Math.PI
                                               Next
                                           End Sub)
        Console.WriteLine("Operation complete. Print results? y/n")
        Dim input As Char = Console.ReadKey().KeyChar
        If input = "y"c Or input = "Y"c Then
            For Each d As Double In results
                Console.Write("{0} ", d)
            Next
        End If

    End Sub
End Module

Chaque thread de la boucle reçoit son propre objet Tuple<T1,T2>, qui contient les valeurs d’index de début et de fin dans la sous-plage spécifiée. La boucle for interne utilise les valeurs fromInclusive et toExclusive pour parcourir le tableau ou IList directement.

Une des surcharges Create vous permet de spécifier la taille des partitions ainsi que leur nombre. Cette surcharge peut être utilisée dans des scénarios où le travail par élément est si faible que même un appel à une méthode virtuelle par élément a un impact perceptible sur les performances.

Partitionneurs personnalisés

Dans certains scénarios, il peut être utile ou même obligatoire d’implémenter votre propre partitionneur. Par exemple, vous pouvez partionner une classe de collection personnalisée plus efficacement qu’avec les partitionneurs par défaut, selon votre connaissance de la structure interne de la classe. Ou vous pouvez créer des partitions de plages de valeurs de tailles différentes en fonction du temps nécessaire pour traiter les éléments situés en différents emplacements de la collection source.

Pour créer un partitionneur personnalisé de base, dérivez une classe de System.Collections.Concurrent.Partitioner<TSource> puis remplacez les méthodes virtuelles, comme décrit dans le tableau suivant.

Si les résultats doivent pouvoir être triés ou que vous avez besoin d’un accès indexé aux éléments, dérivez System.Collections.Concurrent.OrderablePartitioner<TSource> et remplacez ses méthodes virtuelles, comme décrit dans le tableau suivant.

Le tableau suivant fournit des détails supplémentaires sur la façon dont les trois types de partitionneurs d’équilibrage de charge implémentent la classe OrderablePartitioner<TSource>.

Partitions dynamiques

Si vous envisagez d’utiliser le partitionneur dans une méthode ForEach, vous devez être en mesure de retourner un nombre dynamique de partitions. Cela signifie que le partitionneur peut fournir un énumérateur pour une nouvelle partition, à la demande et à tout moment pendant l’exécution de la boucle. En fait, chaque fois que la boucle ajoute une nouvelle tâche parallèle, elle demande une nouvelle partition pour cette tâche. Si vous avez besoin de pouvoir classer les données, effectuez une dérivation System.Collections.Concurrent.OrderablePartitioner<TSource> afin d’affecter un index unique à chaque élément de chaque partition.

Pour plus d’informations et consulter un exemple, voir Guide pratique pour implémenter des partitions dynamiques.

Contrat pour les partitionneurs

Lorsque vous implémentez un partitionneur personnalisé, suivez ces instructions pour garantir une interaction correcte avec PLINQ et ForEach dans la bibliothèque parallèle de tâches (TPL) :

• Si GetPartitions est appelé avec un argument de zéro ou moins pour partitionsCount, levez ArgumentOutOfRangeException. Bien que PLINQ et TPL ne fourniront jamais une valeur partitionCount égale à 0, nous vous recommandons néanmoins de vous prémunir contre ce risque.

• GetPartitions et GetOrderablePartitions devraient toujours renvoyer un nombre de partitions équivalant à partitionsCount. Si le partitionneur manque de données et ne peut pas créer autant de partitions que demandé, la méthode devrait retourner un énumérateur vide pour chacune des partitions restantes. Sinon, PLINQ et TPL lèveront une InvalidOperationException.

• GetPartitions, GetOrderablePartitions, GetDynamicPartitions, et GetOrderableDynamicPartitions ne devraient jamais retourner null (Nothing en Visual Basic). Si tel est le cas, PLINQ/TPL lèveront une InvalidOperationException.

• Les méthodes qui retournent des partitions devraient toujours renvoyer des partitions capables d’énumérer totalement et de manière unique la source de données. Il ne devrait y avoir aucune duplication dans la source de données ou les éléments ignorés, sauf si cela est spécifiquement requis par la conception du partitionneur. Si cette règle n’est pas suivie, l’ordre de sortie peut être brouillé.

• Les accesseurs booléens suivants doivent toujours retourner correctement les valeurs ci-dessous afin que l’ordre de sortie ne soit pas brouillé :

  • KeysOrderedInEachPartition : chaque partition retourne des éléments en augmentant les index clés.

  • KeysOrderedAcrossPartitions : pour toutes les partitions retournées, les index clés dans la partition i sont plus élevés que les index clés de la partition i-1.

  • KeysNormalized: tous les index clés augmentent de monotone, sans écarts, à partir de zéro.

• Tous les index doivent être uniques. Il ne doit pas y avoir de doublons. Si cette règle n’est pas suivie, l’ordre de sortie peut être brouillé.

• Tous les index doivent être non négatifs. Si cette règle n’est pas suivie, PLINQ/TPL peuvent lever des exceptions.

Voir aussi

• Programmation parallèle
• Procédure : implémenter des partitions dynamiques
• Procédure : implémenter un partitionneur pour un partitionnement statique