Condividi tramite


Partitioner personalizzati per PLINQ e TPL

Per parallelizzare un'operazione su un'origine dati, uno dei passaggi essenziali consiste nel partizionare l'origine in più sezioni a cui è possibile accedere simultaneamente da più thread. PLINQ e Task Parallel Library (TPL) forniscono partizionatori predefiniti che funzionano in modo trasparente quando si scrive una query parallela o un ForEach ciclo. Per scenari più avanzati, è possibile collegare il proprio partitioner.

Tipi di partizionamento

Esistono molti modi per partizionare un'origine dati. Negli approcci più efficienti, più thread cooperano per elaborare la sequenza originale, anziché separare fisicamente l'origine in più sottosequenze. Per le matrici e altre origini indicizzate, ad IList esempio le raccolte in cui la lunghezza è nota in anticipo, il partizionamento di intervalli è il tipo più semplice di partizionamento. Ogni thread riceve indici iniziali e finali univoci, in modo che possa elaborare l'intervallo dell'origine senza sovrascrivere o essere sovrascritto da qualsiasi altro thread. L'unico sovraccarico dovuto al partizionamento di intervalli è il lavoro iniziale di creazione degli intervalli; non è necessaria alcuna sincronizzazione aggiuntiva. Pertanto, può offrire buone prestazioni purché il carico di lavoro venga diviso uniformemente. Uno svantaggio del partizionamento di intervalli è che se un thread termina in anticipo, non può aiutare gli altri thread a completare il loro lavoro.

Per gli elenchi collegati o altre raccolte la cui lunghezza non è nota, è possibile usare il partizionamento blocchi. Nel partizionamento in blocchi, ogni thread o attività in un ciclo parallelo o una query utilizza un certo numero di elementi di origine in un blocco, li elabora e quindi torna a recuperare elementi aggiuntivi. Il partitioner garantisce che tutti gli elementi siano distribuiti e che non siano presenti duplicati. Un blocco può essere di qualsiasi dimensione. Ad esempio, il partitioner illustrato in Procedura: Implementare partizioni dinamiche crea blocchi che contengono solo un elemento. Se i blocchi non sono troppo grandi, questo tipo di partizionamento è intrinsecamente bilanciamento del carico perché l'assegnazione di elementi ai thread non è determinata in modo preliminare. Tuttavia, il partitioner comporta il sovraccarico di sincronizzazione ogni volta che il thread deve ottenere un altro blocco. La quantità di sincronizzazione in questi casi è inversamente proporzionale alle dimensioni dei blocchi.

In generale, il partizionamento dell'intervallo è solo più veloce quando il tempo di esecuzione del delegato è ridotto a moderato e l'origine ha un numero elevato di elementi e il lavoro totale di ogni partizione è approssimativamente equivalente. Il partizionamento dei blocchi è quindi generalmente più veloce nella maggior parte dei casi. Nei casi di sorgenti con un numero ridotto di elementi o tempi di esecuzione più lunghi per il delegato, le prestazioni del partizionamento a blocchi e a intervallo sono all'incirca uguali.

I partitioner TPL supportano anche un numero dinamico di partizioni. Ciò significa che possono creare partizioni in tempo reale, ad esempio quando il ForEach ciclo genera una nuova attività. Questa funzionalità consente al partitioner di ridimensionarsi insieme al ciclo stesso. I partitioner dinamici sono anche intrinsecamente capaci di bilanciare il carico. Quando si crea un partitioner personalizzato, è necessario supportare il partizionamento dinamico per poter essere consumato da un ciclo ForEach.

Configurazione dei partizionatori di bilanciamento del carico per PLINQ

Alcuni sovraccarichi del metodo Partitioner.Create permettono di creare un partizionatore per un array o una sorgente IList e di specificare se deve tentare di bilanciare il carico di lavoro tra i thread. Quando il partitioner è configurato per il bilanciamento del carico, viene usato il partizionamento dei blocchi e gli elementi vengono passati a ogni partizione in piccoli blocchi quando vengono richiesti. Questo approccio consente di garantire che tutte le partizioni dispongano di elementi da elaborare fino al completamento dell'intero ciclo o della query. È possibile usare un overload aggiuntivo per fornire il bilanciamento del carico tramite partizionamento di qualsiasi IEnumerable origine.

In generale, il bilanciamento del carico richiede che le partizioni richiedano elementi relativamente frequentemente dal partitioner. Al contrario, un partitioner che esegue il partizionamento statico può assegnare gli elementi a ogni partitioner contemporaneamente usando il partizionamento di intervalli o blocchi. Questo richiede meno sovraccarico rispetto al bilanciamento del carico, ma potrebbe richiedere più tempo per l'esecuzione se un thread termina con un lavoro significativamente maggiore rispetto agli altri. Per impostazione predefinita, quando viene passato un IList o una matrice, PLINQ usa sempre il partizionamento di intervalli senza bilanciamento del carico. Per abilitare il bilanciamento del carico per PLINQ, usare il Partitioner.Create metodo , come illustrato nell'esempio seguente.

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

Il modo migliore per determinare se usare il bilanciamento del carico in uno scenario specifico consiste nell'sperimentare e misurare il tempo necessario per il completamento delle operazioni in carichi rappresentativi e configurazioni del computer. Ad esempio, il partizionamento statico potrebbe offrire una velocità significativa in un computer multicore con solo pochi core, ma potrebbe comportare rallentamenti nei computer con un numero relativamente elevato di core.

Nella tabella seguente sono elencati i sovraccarichi disponibili del metodo Create. Questi partitioner non sono limitati all'uso solo con PLINQ o Task. Possono essere usati anche con qualsiasi costrutto parallelo personalizzato.

Sovraccarico Usa il bilanciamento del carico
Create<TSource>(IEnumerable<TSource>) Sempre
Create<TSource>(TSource[], Boolean) Quando l'argomento booleano viene specificato come vero
Create<TSource>(IList<TSource>, Boolean) Quando l'argomento booleano viene specificato come vero
Create(Int32, Int32) Mai
Create(Int32, Int32, Int32) Mai
Create(Int64, Int64) Mai
Create(Int64, Int64, Int64) Mai

Configurazione dei partitioner di intervalli statici per Parallel.ForEach

In un For ciclo il corpo del ciclo viene fornito al metodo come delegato. Il costo dell'invocazione di quel delegato è circa lo stesso di una chiamata a metodo virtuale. In alcuni scenari, il corpo di un ciclo parallelo potrebbe essere sufficientemente piccolo che il costo della chiamata del delegato in ogni iterazione del ciclo diventa significativo. In tali situazioni, è possibile usare uno degli Create overload per creare una IEnumerable<T> delle partizioni di intervallo sugli elementi di origine. È quindi possibile passare questa raccolta di intervalli a un ForEach metodo il cui corpo è costituito da un ciclo regolare for . Il vantaggio di questo approccio è che il costo di chiamata del delegato viene addebitato una sola volta per intervallo, anziché una volta per elemento. Nell'esempio seguente viene illustrato il modello di 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

Ogni thread nel ciclo riceve il proprio Tuple<T1,T2> che contiene i valori di indice iniziale e finale nell'intervallo secondario specificato. Il ciclo interno for usa i valori fromInclusive e toExclusive per eseguire il ciclo sull'array o direttamente su IList.

Uno degli Create overload consente di specificare le dimensioni delle partizioni e il numero di partizioni. Questo overload può essere usato negli scenari in cui il lavoro per elemento è così basso che perfino una chiamata di metodo virtuale per elemento ha un impatto notevole sulle prestazioni.

Partitioner personalizzati

In alcuni scenari, potrebbe essere utile o anche necessario implementare il proprio partitioner. Ad esempio, è possibile avere una classe di raccolta personalizzata che è possibile partizionare in modo più efficiente rispetto ai partitioner predefiniti, in base alla conoscenza della struttura interna della classe. In alternativa, è possibile creare partizioni di intervalli di dimensioni diverse in base alla conoscenza del tempo necessario per elaborare gli elementi in posizioni diverse nella raccolta 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.

Metodo Descrizione
GetPartitions Questo metodo viene chiamato una volta dal thread principale e restituisce un IList(IEnumerator(TSource)). Ogni thread di lavoro nel ciclo o nella query può chiamare GetEnumerator nell'elenco per recuperare un IEnumerator<T> su una partizione distinta.
SupportsDynamicPartitions Restituisce true se si implementa GetDynamicPartitions, in caso contrario, false.
GetDynamicPartitions Se SupportsDynamicPartitions è true, questo metodo può essere chiamato facoltativamente anziché GetPartitions.

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

Metodo Descrizione
GetPartitions Questo metodo viene chiamato una volta dal thread principale e restituisce un oggetto IList(IEnumerator(TSource)). Ogni thread di lavoro nel ciclo o nella query può chiamare GetEnumerator nell'elenco per recuperare un IEnumerator<T> su una partizione distinta.
SupportsDynamicPartitions Restituisce true se si implementa GetDynamicPartitions; in caso contrario, false.
GetDynamicPartitions In genere, questo chiama semplicemente GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions Se SupportsDynamicPartitions è true, questo metodo può essere chiamato facoltativamente anziché GetPartitions.

Nella tabella seguente vengono forniti dettagli aggiuntivi sul modo in cui i tre tipi di partitioner di bilanciamento del carico implementano la OrderablePartitioner<TSource> classe .

Metodo/Proprietà IList/Array senza bilanciamento del carico IList/Array con bilanciamento del carico IEnumerable (interfaccia per implementare una raccolta iterabile)
GetOrderablePartitions Usa il partizionamento di intervalli Utilizza il partizionamento dei blocchi ottimizzato per gli elenchi per il partitionCount specificato. Usa il partizionamento dei blocchi creando un numero statico di partizioni.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions Genera un'eccezione non supportata Usa il partizionamento dei blocchi ottimizzato per elenchi e partizioni dinamiche Usa il partizionamento dei blocchi creando un numero dinamico di partizioni.
KeysOrderedInEachPartition Restituisce true. Restituisce true. Restituisce true.
KeysOrderedAcrossPartitions Restituisce true. Restituisce false. Restituisce false.
KeysNormalized Restituisce true. Restituisce true. Restituisce true.
SupportsDynamicPartitions Restituisce false. Restituisce true. Restituisce true.

Partizioni dinamiche

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

Per altre informazioni e un esempio, vedere Procedura: Implementare partizioni dinamiche.

Contratto per i ripartitori

Quando si implementa un partitioner personalizzato, seguire queste linee guida per garantire una corretta interazione con PLINQ e ForEach nel TPL:

  • Se GetPartitions viene chiamato con un argomento pari a zero o inferiore per partitionsCount, lancia ArgumentOutOfRangeException. Anche se PLINQ e TPL non passeranno mai un valore partitionCount uguale a 0, è tuttavia consigliabile proteggersi dalla possibilità.

  • GetPartitions e GetOrderablePartitions deve restituire partitionsCount sempre il numero di partizioni. Se il partitioner esaurisce i dati e non può creare tutte le partizioni richieste, il metodo deve restituire un enumeratore vuoto per ognuna delle partizioni rimanenti. In caso contrario, sia PLINQ che TPL genereranno un'eccezione InvalidOperationException.

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

  • I metodi che restituiscono partizioni devono restituire sempre partizioni in grado di enumerare completamente ed in modo univoco l'origine dati. Non ci dovrebbero essere duplicazioni nella fonte dati o elementi saltati, a meno che non sia specificatamente richiesto dalla progettazione del partitioner. Se questa regola non viene seguita, l'ordine di output potrebbe essere confuso.

  • I metodi getter booleani seguenti devono sempre restituire con precisione i valori indicati affinché l'ordine di output non sia confuso.

    • KeysOrderedInEachPartition: ogni partizione restituisce elementi con indici chiave crescenti.

    • KeysOrderedAcrossPartitions: per tutte le partizioni restituite, gli indici chiave nella partizione i sono superiori agli indici chiave nella partizione i-1.

    • KeysNormalized: tutti gli indici chiave aumentano in modo monotonico senza lacune, a partire da zero.

  • Tutti gli indici devono essere univoci. Potrebbero non essere presenti indici duplicati. Se questa regola non viene seguita, l'ordine di output potrebbe essere confuso.

  • Tutti gli indici devono essere non negativo. Se questa regola non viene seguita, PLINQ/TPL potrebbe generare eccezioni.

Vedere anche