Particionadores personalizados para PLINQ e TPL

Para paralelizar uma operação em uma fonte de dados, uma das etapas essenciais é particionar a fonte em várias seções que podem ser acessadas simultaneamente por vários threads. O PLINQ e a TPL (Task Parallel Library) fornecem particionadores padrão que funcionam de forma transparente quando você escreve uma consulta paralela ou ForEach loop. Para cenários mais avançados, você pode conectar seu próprio particionador.

Tipos de particionamento

Há muitas maneiras de particionar uma fonte de dados. Nas abordagens mais eficientes, vários threads cooperam para processar a sequência de origem original, em vez de separar fisicamente a fonte em várias subsequências. Para matrizes e outras fontes indexadas, como IList coleções em que o comprimento é conhecido antecipadamente, o particionamento de intervalo é o tipo mais simples de particionamento. Cada thread recebe índices iniciais e finais exclusivos, para que possa processar seu intervalo da fonte sem substituir ou ser substituído por qualquer outro thread. A única sobrecarga envolvida no particionamento de intervalos é o trabalho inicial de criação dos intervalos; nenhuma sincronização adicional é necessária depois disso. Portanto, ele pode fornecer um bom desempenho, desde que a carga de trabalho seja dividida uniformemente. Uma desvantagem do particionamento de intervalo é que, se um thread terminar cedo, ele não pode ajudar os outros threads a terminar seu trabalho.

Para listas vinculadas ou outras coleções cujo comprimento não é conhecido, você pode usar o particionamento de blocos. No particionamento de blocos, cada thread ou tarefa em um loop paralelo ou consulta consome algum número de elementos de origem em um bloco, processa-os e, em seguida, volta para recuperar elementos adicionais. O particionador garante que todos os elementos sejam distribuídos e que não haja duplicatas. Um pedaço pode ser de qualquer tamanho. Por exemplo, o particionador demonstrado em Como: Implementar partições dinâmicas cria blocos que contêm apenas um elemento. Contanto que os blocos não sejam muito grandes, esse tipo de particionamento é inerentemente balanceamento de carga porque a atribuição de elementos a threads não é pré-determinada. No entanto, o particionador incorre na sobrecarga de sincronização cada vez que o thread precisa obter outro bloco. A quantidade de sincronização incorrida nesses casos é inversamente proporcional ao tamanho dos blocos.

Em geral, o particionamento de intervalo só é mais rápido quando o tempo de execução do delegado é pequeno a moderado, e a fonte tem um grande número de elementos, e o trabalho total de cada partição é aproximadamente equivalente. O particionamento de blocos é, portanto, geralmente mais rápido na maioria dos casos. Em fontes com um pequeno número de elementos ou tempos de execução mais longos para o delegado, o desempenho do particionamento de partes e intervalos é praticamente igual.

Os particionadores TPL também suportam um número dinâmico de partições. Isso significa que eles podem criar partições on-the-fly, por exemplo, quando o ForEach loop gera uma nova tarefa. Esse recurso permite que o particionador seja dimensionado junto com o próprio loop. Os particionadores dinâmicos também são inerentemente balanceadores de carga. Ao criar um particionador personalizado, você deve oferecer suporte ao particionamento dinâmico para ser consumível a partir de um ForEach loop.

Configurando particionadores de balanceamento de carga para PLINQ

Algumas sobrecargas do método permitem criar um particionador para uma matriz ou IList fonte e especificar se ele deve tentar equilibrar a carga de Partitioner.Create trabalho entre os threads. Quando o particionador é configurado para balancear a carga, o particionamento de partes é usado e os elementos são entregues a cada partição em pequenos blocos conforme são solicitados. Essa abordagem ajuda a garantir que todas as partições tenham elementos para processar até que todo o loop ou consulta seja concluído. Uma sobrecarga adicional pode ser usada para fornecer particionamento de balanceamento de carga de qualquer IEnumerable fonte.

Em geral, o balanceamento de carga requer que as partições solicitem elementos com relativa frequência do particionador. Por outro lado, um particionador que faz particionamento estático pode atribuir os elementos a cada particionador de uma só vez usando o particionamento de intervalo ou bloco. Isso requer menos sobrecarga do que o balanceamento de carga, mas pode levar mais tempo para ser executado se um thread acabar com significativamente mais trabalho do que os outros. Por padrão, quando é passado um IList ou uma matriz, o PLINQ sempre usa particionamento de intervalo sem balanceamento de carga. Para habilitar o balanceamento de carga para PLINQ, use o Partitioner.Create método, conforme mostrado no exemplo a seguir.

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

A melhor maneira de determinar se o balanceamento de carga deve ser usado em um determinado cenário é experimentar e medir quanto tempo as operações levam para serem concluídas sob cargas representativas e configurações de computador. Por exemplo, o particionamento estático pode fornecer uma aceleração significativa em um computador multi-core que tem apenas alguns núcleos, mas pode resultar em lentidão em computadores que têm relativamente muitos núcleos.

A tabela a seguir lista as sobrecargas disponíveis do Create método. Estes particionadores não estão limitados a usar apenas com PLINQ ou Task. Eles também podem ser usados com qualquer construção paralela personalizada.

Configurando particionadores de intervalo estático para Parallel.ForEach

Em um For loop, o corpo do loop é fornecido ao método como um delegado. O custo de invocar esse delegado é aproximadamente o mesmo que uma chamada de método virtual. Em alguns cenários, o corpo de um loop paralelo pode ser pequeno o suficiente para que o custo da invocação do delegado em cada iteração de loop se torne significativo. Em tais situações, você pode usar uma das Create sobrecargas para criar uma IEnumerable<T> das partições de intervalo sobre os elementos de origem. Em seguida, você pode passar essa coleção de intervalos para um ForEach método cujo corpo consiste em um loop regular for . O benefício dessa abordagem é que o custo de invocação do delegado é incorrido apenas uma vez por intervalo, em vez de uma vez por elemento. O exemplo a seguir demonstra o padrão básico.

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

Cada thread no loop recebe seu próprio Tuple<T1,T2> que contém os valores de índice inicial e final no subintervalo especificado. O loop interno for usa os fromInclusive valores e toExclusive para fazer loop sobre a matriz ou o IList diretamente.

Uma das Create sobrecargas permite especificar o tamanho das partições e o número de partições. Essa sobrecarga pode ser usada em cenários onde o trabalho por elemento é tão baixo que até mesmo uma chamada de método virtual por elemento tem um impacto notável no desempenho.

Particionadores personalizados

Em alguns cenários, pode valer a pena ou até mesmo ser necessário implementar seu próprio particionador. Por exemplo, você pode ter uma classe de coleção personalizada que você pode particionar com mais eficiência do que os particionadores padrão, com base em seu conhecimento da estrutura interna da classe. Ou, você pode querer criar partições de intervalo de tamanhos variados com base em seu conhecimento de quanto tempo levará para processar elementos em locais diferentes na coleção de origem.

Para criar um particionador personalizado básico, derive uma classe e System.Collections.Concurrent.Partitioner<TSource> substitua os métodos virtuais, conforme descrito na tabela a seguir.

Se os resultados precisarem ser classificáveis ou se você precisar de System.Collections.Concurrent.OrderablePartitioner<TSource> acesso indexado aos elementos, derive e substitua seus métodos virtuais, conforme descrito na tabela a seguir.

A tabela a seguir fornece detalhes adicionais sobre como os três tipos de particionadores de balanceamento de carga implementam a OrderablePartitioner<TSource> classe.

Partições dinâmicas

Se você pretende que o particionador seja usado em um ForEach método, você deve ser capaz de retornar um número dinâmico de partições. Isso significa que o particionador pode fornecer um enumerador para uma nova partição sob demanda a qualquer momento durante a execução do loop. Basicamente, sempre que o loop adiciona uma nova tarefa paralela, ele solicita uma nova partição para essa tarefa. Se você precisar que os dados sejam ordenáveis, derive de System.Collections.Concurrent.OrderablePartitioner<TSource> modo que cada item em cada partição receba um índice exclusivo.

Para obter mais informações e um exemplo, consulte Como implementar partições dinâmicas.

Contrato para particionadores

Ao implementar um particionador personalizado, siga estas diretrizes para ajudar a garantir a interação correta com o PLINQ e ForEach no TPL:

• Se GetPartitions for chamado com um argumento de zero ou menos para partitionsCount, lance ArgumentOutOfRangeException. Embora PLINQ e TPL nunca passem em um partitionCount igual a 0, no entanto, recomendamos que você se previna contra a possibilidade.

• GetPartitions e GetOrderablePartitions deve sempre retornar partitionsCount o número de partições. Se o particionador ficar sem dados e não puder criar tantas partições quanto solicitado, o método deve retornar um enumerador vazio para cada uma das partições restantes. Caso contrário, tanto o PLINQ como o TPL lançarão um InvalidOperationExceptionficheiro .

• GetPartitions, GetOrderablePartitions, GetDynamicPartitions, e GetOrderableDynamicPartitions nunca deve retornar null (Nothing no Visual Basic). Se o fizerem, PLINQ / TPL lançará um InvalidOperationException.

• Os métodos que retornam partições devem sempre retornar partições que podem enumerar completa e exclusivamente a fonte de dados. Não deve haver duplicação na fonte de dados ou itens ignorados, a menos que especificamente exigido pelo design do particionador. Se esta regra não for seguida, a ordem de saída pode ser embaralhada.

• Os seguintes getters booleanos devem sempre retornar com precisão os seguintes valores para que a ordem de saída não seja embaralhada:

  • KeysOrderedInEachPartition: Cada partição retorna elementos com índices de chave crescentes.

  • KeysOrderedAcrossPartitions: Para todas as partições que são retornadas, os índices de chave na partição i são maiores do que os índices de chave na partição i-1.

  • KeysNormalized: Todos os índices-chave estão a aumentar monotonicamente sem diferenças, começando de zero.

• Todos os índices devem ser únicos. Não pode haver índices duplicados. Se esta regra não for seguida, a ordem de saída pode ser embaralhada.

• Todos os índices devem ser não negativos. Se esta regra não for seguida, então PLINQ/TPL pode lançar exceções.

Consulte também

• Programação paralela
• Como: Implementar partições dinâmicas
• Como: Implementar um particionador para particionamento estático