Partitioner personalizzati per PLINQ e TPL

Uno dei passaggi basilari per la parallelizzazione di un'operazione su un'origine dati consiste nel suddividere l'origine in più sezioni, cui è possibile accedere contemporaneamente da più thread. PLINQ e TPL (Task Parallel Library) forniscono partitioner predefiniti che funzionano in maniera trasparente quando si scrive una query parallela o un ciclo ForEach. Per gli scenari più avanzati, è possibile collegare il proprio partitioner.

Tipi di partizionamento

Esistono molti modi per suddividere in partizioni un'origine dati. Quelli più efficaci prevedono la cooperazione di più thread nell'elaborazione della sequenza di origine originale senza separazione fisica dell'origine in più sottosequenze. Per le matrici e le altre origini indicizzate, quali insiemi IList in cui la lunghezza è nota in anticipo, il tipo più semplice di partizionamento è il partizionamento per intervalli. Ogni thread riceve indici iniziali e finali univoci, in modo che possa elaborare l'intervallo dell'origine senza sovrascrivere un altro thread o essere sovrascritto. L'unico sovraccarico coinvolto nel partizionamento per intervalli è il lavoro iniziale di creazione degli intervalli. Non è richiesta alcuna sincronizzazione aggiuntiva successiva. Questo tipo di partizionamento può pertanto garantire buone prestazioni, a condizione che il carico di lavoro sia suddiviso in modo uniforme. Uno svantaggio del partizionamento per intervalli è che un thread che completa il proprio lavoro prima degli altri non può contribuire al completamento del lavoro degli altri thread.

Per gli elenchi collegati o altri insiemi la cui lunghezza non è nota, è possibile utilizzare il partizionamento a blocchi. Nel partizionamento a blocchi ogni thread o attività in una query o un ciclo parallelo utilizza un determinato numero di elementi di origine in un unico blocco, li elabora, quindi torna a recuperare altri elementi. Il partitioner si assicura che tutti gli elementi vengano distribuiti e che non ci siano duplicati. Un blocco può avere qualsiasi dimensione. Il partitioner illustrato in Procedura: implementare partizioni dinamiche, ad esempio, determina la creazione di blocchi che contengono un solo elemento. Fintantoché i blocchi non sono troppo grandi, in questo tipo di partizionamento è implicita la funzionalità di bilanciamento del carico, in quanto l'assegnazione di elementi ai thread non è predeterminata. Il partitioner deve tuttavia affrontare il sovraccarico della sincronizzazione ogni volta che il thread ottiene un altro blocco da elaborare. La quantità di lavoro richiesta per la sincronizzazione in questi casi è inversamente proporzionale alla dimensione dei blocchi.

In generale, il partizionamento per intervalli è più veloce solo quando il tempo di esecuzione del delegato è da ridotto a moderato, nell'origine è presente un numero elevato di elementi e il lavoro totale di ogni partizione è pressoché equivalente. Il partizionamento a blocchi è pertanto generalmente più veloce nella maggior parte dei casi. Nelle origini con un numero ridotto di elementi o con tempi di esecuzione più lunghi per il delegato, le prestazioni del partizionamento a blocchi e quelle del partizionamento per intervalli sono quasi equivalenti.

I partitioner TPL supportano inoltre un numero dinamico di partizioni. Ciò significa che possono creare partizioni in qualsiasi momento, ad esempio, quando il ciclo ForEach genera una nuova attività. Questa funzionalità consente il ridimensionamento del partitioner insieme al ciclo stesso. Anche nei partitioner dinamici è implicita la funzionalità del bilanciamento del carico. Quando si crea un partitioner personalizzato, è necessario che l'utilizzo del partizionamento dinamico sia supportato in un ciclo ForEach.

Configurazione di partitioner con bilanciamento del carico per PLINQ

Alcuni overload del metodo Partitioner.Create consentono di creare un partitioner per una matrice o un'origine IList, nonché di specificare se deve essere effettuato il tentativo di bilanciare il carico di lavoro tra i thread. Quando il partitioner viene configurato per il bilanciamento del carico, viene utilizzato il partizionamento a blocchi e gli elementi vengono passati a ogni partizione in piccoli blocchi man mano che vengono richiesti. Questo approccio consente di assicurarsi che in tutte le partizioni siano presenti elementi da elaborare fino a che non è stato completato l'intero ciclo o l'intera query. È possibile utilizzare un overload aggiuntivo per rendere possibile il partizionamento del bilanciamento del carico di qualsiasi origine IEnumerable.

In generale, per la corretta esecuzione del bilanciamento del carico è necessario che le partizioni richiedano elementi al partitioner con una certa frequenza. Al contrario, un partitioner che esegue il partizionamento statico può assegnare contemporaneamente gli elementi a ogni partitioner mediante il partizionamento per intervalli o a blocchi. Ciò comporta un sovraccarico minore rispetto al bilanciamento del carico, ma potrebbe richiedere più tempo per l'esecuzione se un thread viene completato con un volume di lavoro significativamente superiore rispetto agli altri. Per impostazione predefinita, quando viene passato un IList o una matrice, PLINQ utilizza sempre il partizionamento per intervalli senza bilanciamento del carico. Per abilitare il bilanciamento del carico per PLINQ, utilizzare il metodo Partitioner.Create, come mostrato nell'esempio seguente.

        ' 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))

            // 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);
            });

Il modo migliore per stabilire se è opportuno utilizzare il bilanciamento del carico in qualsiasi scenario specificato consiste nello sperimentare e misurare il tempo necessario per il completamento delle operazioni con carichi e configurazioni di computer rappresentativi. Il partizionamento statico potrebbe ad esempio garantire un aumento di velocità significativo in un computer con processore multi-core che presenta un numero limitato di core, ma potrebbe comportare rallentamenti in computer che presentano un numero di core relativamente elevato.

Nella tabella riportata di seguito sono elencati i sovraccarichi disponibili del metodo Create. L'utilizzo di tali partitioner non è limitato a PLINQ o ForEach. Possono infatti essere utilizzati anche con qualsiasi costrutto parallelo personalizzato.

Configurazione di partitioner a intervalli statici per Parallel.ForEach

In un ciclo For il corpo del ciclo viene fornito al metodo come delegato. Il costo della chiamata al delegato è quasi equivalente a quello di una chiamata al metodo virtuale. In alcuni scenari il corpo di un ciclo parallelo può arrivare a essere sufficientemente ridotto da rendere significativo quello della chiamata al delegato su ogni iterazione del ciclo. In situazioni di questo tipo è possibile utilizzare uno degli overload Create per creare un IEnumerable<T> di partizioni a intervalli sugli elementi di origine. È quindi possibile passare questo insieme di intervalli a un metodo ForEach il cui corpo è costituito da un ciclo for normale. Il vantaggio di questo approccio è che il costo della chiamata al delegato viene sostenuto una sola volta per intervallo anziché una volta per elemento. Nell'esempio seguente viene illustrato il modello di base.

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

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);
            }           
        }
    }
}

Ogni thread del ciclo riceve il proprio Tuple<T1, T2>, che contiene i valori di indice iniziale e finale nel sottointervallo specificato. Il ciclo for interno utilizza i valori fromInclusive e toExclusive per eseguire il ciclo sulla matrice o direttamente su IList.

Uno degli overload di Create consente di specificare la dimensione e il numero delle partizioni. Tale overload può essere utilizzato negli scenari in cui il volume di lavoro per elemento è così ridotto che anche una sola chiamata del metodo virtuale per elemento ha un impatto notevole sulle prestazioni.

Partitioner personalizzati

In alcuni scenari potrebbe valere la pena o potrebbe addirittura essere necessario implementare un partitioner personalizzato. È ad esempio possibile suddividere una classe di insiemi personalizzata in modo più efficace di come sarebbe possibile utilizzando i partitioner predefiniti basandosi sulla conoscenza della struttura interna della classe. In alternativa, è possibile creare partizioni a intervalli di varie dimensioni basandosi sulla conoscenza del tempo necessario per l'elaborazione degli elementi in posizioni diverse nell'insieme di origine.

Per creare un partitioner personalizzato di base, derivare una classe da System.Collections.Concurrent.Partitioner<TSource> ed eseguire l'override dei metodi virtuali, come descritto nella tabella seguente.

Se i risultati devono essere ordinabili o si richiede l'accesso indicizzato agli elementi, derivare da System.Collections.Concurrent.OrderablePartitioner<TSource> ed eseguire l'override dei metodi virtuali, come descritto nella tabella seguente.

Nella tabella seguente vengono forniti dettagli aggiuntivi sulle modalità con cui i tre tipi di partitioner con bilanciamento del carico implementano la classe OrderablePartitioner<TSource>.

Partizioni dinamiche

Se si prevede che il partitioner verrà utilizzato in un metodo ForEach, è necessario riuscire a restituire un numero dinamico di partizioni. Ciò significa che il partitioner può fornire su richiesta in qualsiasi momento un enumeratore per una nuova partizione durante l'esecuzione del ciclo. Fondamentalmente ogni volta che il ciclo aggiunge una nuova attività parallela, richiede una nuova partizione per l'attività. Se si ha necessità che i dati siano ordinabili, derivare da System.Collections.Concurrent.OrderablePartitioner<TSource> in modo che a ogni elemento di ogni partizione venga assegnato un indice univoco.

Per ulteriori informazioni e un esempio, vedere Procedura: implementare partizioni dinamiche.

Contratto per i partitioner

Quando si implementa un partitioner personalizzato, seguire le linee guida indicate di seguito per consentire la corretta interazione con PLINQ e ForEach in TPL:

• Se GetPartitions viene chiamato con un argomento con valore zero o un valore inferiore per partitionsCount, viene generata l'eccezione ArgumentOutOfRangeException. Anche se PLINQ e TPL non passeranno mai in un partitionCount uguale a 0, si consiglia comunque di evitare che ciò accada.

• GetPartitions e GetOrderablePartitions devono restituire sempre un numero di partizioni pari a partitionsCount. Se il partitioner perde dati e non può creare il numero di partizioni richiesto, il metodo deve restituire un enumeratore vuoto per ognuna delle partizioni rimanenti. In caso contrario, sia PLINQ sia TPL genereranno un'eccezione InvalidOperationException.

• GetPartitions, GetOrderablePartitions, GetDynamicPartitions e GetOrderableDynamicPartitions non devono mai restituire null (Nothing in Visual Basic). In caso contrario, PLINQ / TPL genererà un'eccezione InvalidOperationException.

• I metodi che restituiscono partizioni devono sempre restituire partizioni che possono enumerare in modo completo e univoco l'origine dati. Nell'origine dati non devono essere presenti duplicati né elementi ignorati, a meno che non sia richiesto in maniera specifica dalla progettazione del partitioner. Se questa regola non viene rispettata, è possibile che l'ordine di output venga alterato.

• Le funzioni Get booleane indicate di seguito devono sempre restituire esattamente i valori seguenti in modo che l'ordine di output non venga alterato:

  • KeysOrderedInEachPartition: ogni partizione restituisce elementi con indici di chiave incrementali.

  • KeysOrderedAcrossPartitions: per tutte le partizioni restituite, gli indici di chiave della partizione i hanno un valore superiore degli indici di chiave della partizione i-1.

  • KeysNormalized: tutti gli indici di chiave subiscono incrementi progressivi costanti senza interruzioni, a partire da zero.

• Tutti gli indici devono essere univoci. Non possono esistere indici duplicati. Se questa regola non viene rispettata, è possibile che l'ordine di output venga alterato.

• Tutti gli indici devono essere non negativi. Se questa regola non viene rispettata, è possibile che PLINQ/TPL generi eccezioni.

Vedere anche

Attività

Procedura: implementare partizioni dinamiche

Procedura: implementare un partitioner con un numero statico di partizioni

Concetti

Programmazione parallela in .NET Framework