Paralelismo de dados - Data parallelism

Execução de job sequencial vs. paralela de dados

O paralelismo de dados é a paralelização entre vários processadores em ambientes de computação paralela . Ele se concentra na distribuição dos dados em diferentes nós, que operam nos dados em paralelo. Ele pode ser aplicado em estruturas de dados regulares, como arrays e matrizes, trabalhando em cada elemento em paralelo. Contrasta com o paralelismo de tarefas como outra forma de paralelismo.

Um trabalho paralelo de dados em uma matriz de n elementos pode ser dividido igualmente entre todos os processadores. Vamos supor que queremos somar todos os elementos de uma determinada matriz e o tempo para uma única operação de adição é unidades de tempo Ta. No caso de execução sequencial, o tempo gasto pelo processo será n × Ta unidades de tempo, pois soma todos os elementos de uma matriz. Por outro lado, se executarmos este trabalho como um trabalho paralelo de dados em 4 processadores, o tempo gasto seria reduzido para ( n / 4) × Ta + unidades de tempo indireto de fusão. A execução paralela resulta em uma aceleração de 4 em relação à execução sequencial. Uma coisa importante a notar é que a localidade das referências de dados desempenha um papel importante na avaliação do desempenho de um modelo de programação paralela de dados. A localização dos dados depende dos acessos à memória realizados pelo programa, bem como do tamanho do cache.

História

A exploração do conceito de paralelismo de dados começou na década de 1960 com o desenvolvimento da máquina Solomon. A máquina Solomon, também chamada de processador vetorial , foi desenvolvida para agilizar o desempenho de operações matemáticas, trabalhando em uma grande matriz de dados (operando em vários dados em intervalos de tempo consecutivos). A simultaneidade de operações de dados também foi explorada operando em vários dados ao mesmo tempo, usando uma única instrução. Esses processadores eram chamados de 'processadores de matriz'. Na década de 1980, o termo foi introduzido para descrever esse estilo de programação, que era amplamente usado para programar Connection Machines em linguagens paralelas de dados como C * . Hoje, o paralelismo de dados é melhor exemplificado em unidades de processamento gráfico (GPUs), que usam ambas as técnicas de operação em vários dados no espaço e no tempo usando uma única instrução.

Descrição

Em um sistema multiprocessador executando um único conjunto de instruções ( SIMD ), o paralelismo de dados é obtido quando cada processador executa a mesma tarefa em diferentes dados distribuídos. Em algumas situações, um único thread de execução controla as operações em todos os dados. Em outros, diferentes threads controlam a operação, mas executam o mesmo código.

Por exemplo, considere a multiplicação e adição de matrizes de maneira sequencial, conforme discutido no exemplo.

Exemplo

A seguir é a pseudo-código sequencial para a multiplicação e adição de duas matrizes, onde o resultado é armazenado na matriz C . O pseudo-código para a multiplicação calcula o produto escalar dos dois matrizes A , B e armazena o resultado na matriz de saída C .

Se os programas a seguir fossem executados sequencialmente, o tempo necessário para calcular o resultado seria de (assumindo que os comprimentos de linha e de coluna de ambas as matrizes são n) e para multiplicação e adição, respectivamente. ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle O (n)}$

// Matrix multiplication
for (i = 0; i < row_length_A; i++)
{		
    for (k = 0; k < column_length_B; k++)
    {
        sum = 0;
        for (j = 0; j < column_length_A; j++)
        {
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

// Array addition
for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

Podemos explorar o paralelismo de dados no código anterior para executá-lo mais rápido, pois a aritmética é independente do loop. A paralelização do código de multiplicação da matriz é obtida usando OpenMP . Uma diretiva OpenMP, "omp parallel for" instrui o compilador a executar o código no loop for em paralelo. Para multiplicação, podemos dividir a matriz A e B em blocos ao longo de linhas e colunas, respectivamente. Isso nos permite calcular cada elemento da matriz C individualmente, tornando a tarefa paralela. Por exemplo: A [mxn] ponto B [nxk] pode ser finalizado em vez de quando executado em paralelo usando processadores m * k . ${\ displaystyle O (n)}$ ${\ displaystyle O (m * n * k)}$

Paralelismo de dados na multiplicação de matrizes

// Matrix multiplication in parallel
#pragma omp parallel for schedule(dynamic,1) collapse(2)
for (i = 0; i < row_length_A; i++){
    for (k = 0; k < column_length_B; k++){
        sum = 0;
        for (j = 0; j < column_length_A; j++){
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

Pode-se observar a partir do exemplo que muitos processadores serão necessários conforme os tamanhos das matrizes continuam aumentando. Manter o tempo de execução baixo é a prioridade, mas conforme o tamanho da matriz aumenta, nos deparamos com outras restrições, como a complexidade de tal sistema e seus custos associados. Portanto, restringindo o número de processadores no sistema, podemos ainda aplicar o mesmo princípio e dividir os dados em blocos maiores para calcular o produto de duas matrizes.

Para adição de matrizes em uma implementação paralela de dados, vamos supor um sistema mais modesto com duas unidades de processamento central (CPU) A e B, a CPU A pode adicionar todos os elementos da metade superior das matrizes, enquanto a CPU B pode adicionar todos os elementos de a metade inferior das matrizes. Como os dois processadores funcionam em paralelo, a tarefa de realizar a adição do array levaria metade do tempo de realizar a mesma operação em série usando apenas uma CPU.

O programa expresso em pseudocódigo abaixo - que aplica alguma operação arbitrária,, foo em cada elemento da matriz - d ilustra o paralelismo de dados:

if CPU = "a" then
    lower_limit := 1
    upper_limit := round(d.length / 2)
else if CPU = "b" then
    lower_limit := round(d.length / 2) + 1
    upper_limit := d.length

for i from lower_limit to upper_limit by 1 do
    foo(d[i])

Em um sistema SPMD executado em um sistema de 2 processadores, ambas as CPUs executarão o código.

O paralelismo de dados enfatiza a natureza distribuída (paralela) dos dados, em oposição ao processamento (paralelismo de tarefas). A maioria dos programas reais fica em algum lugar entre o paralelismo de tarefas e o paralelismo de dados.

Etapas para paralelização

O processo de paralelizar um programa sequencial pode ser dividido em quatro etapas distintas.

Modelo	Descrição
Decomposição	O programa é dividido em tarefas, a menor unidade de concorrência explorável.
Tarefa	As tarefas são atribuídas a processos.
Orquestração	Acesso a dados, comunicação e sincronização de processos.
Mapeamento	Os processos estão vinculados aos processadores.

Paralelismo de dados vs. paralelismo de tarefas

Paralelismo de dados	Paralelismo de tarefas
As mesmas operações são realizadas em diferentes subconjuntos dos mesmos dados.	Diferentes operações são realizadas nos mesmos dados ou em dados diferentes.
Computação síncrona	Computação assíncrona
A aceleração é maior, pois há apenas um thread de execução operando em todos os conjuntos de dados.	A aceleração é menor, pois cada processador executará uma thread ou processo diferente no mesmo conjunto de dados ou em conjuntos diferentes.
A quantidade de paralelização é proporcional ao tamanho dos dados de entrada.	A quantidade de paralelização é proporcional ao número de tarefas independentes a serem executadas.
Projetado para um equilíbrio de carga ideal em sistema multiprocessador.	O balanceamento de carga depende da disponibilidade do hardware e algoritmos de agendamento, como agendamento estático e dinâmico.

Paralelismo de dados vs. paralelismo de modelo

Paralelismo de dados	Paralelismo de modelo
O mesmo modelo é usado para cada thread, mas os dados fornecidos a cada um deles são divididos e compartilhados.	Os mesmos dados são usados para cada encadeamento e o modelo é dividido entre os encadeamentos.
É rápido para redes pequenas, mas muito lento para redes grandes, uma vez que grandes quantidades de dados precisam ser transferidas entre os processadores de uma só vez.	É lento para redes pequenas e rápido para redes grandes.
O paralelismo de dados é idealmente usado em cálculos de matriz e matriz e redes neurais convolucionais	O paralelismo de modelos encontra suas aplicações no aprendizado profundo

Dados mistos e paralelismo de tarefas

O paralelismo de dados e tarefas pode ser implementado simultaneamente combinando-os no mesmo aplicativo. Isso é chamado de dados mistos e paralelismo de tarefas. O paralelismo misto requer algoritmos de programação sofisticados e suporte de software. É o melhor tipo de paralelismo quando a comunicação é lenta e o número de processadores é grande.

Dados mistos e paralelismo de tarefas têm muitas aplicações. É particularmente usado nas seguintes aplicações:

Dados mistos e paralelismo de tarefas encontram aplicações na modelagem climática global. Grandes cálculos paralelos de dados são realizados criando grades de dados que representam a atmosfera terrestre e os oceanos e o paralelismo de tarefas é empregado para simular a função e o modelo dos processos físicos.
Em simulação de circuito baseada em temporização . Os dados são divididos entre diferentes sub-circuitos e o paralelismo é obtido com a orquestração das tarefas.

Ambientes de programação paralela de dados

Uma variedade de ambientes de programação paralela de dados estão disponíveis hoje, os mais amplamente usados são:

Interface de passagem de mensagem : é uma interface de programação de passagem de mensagem de plataforma cruzada para computadores paralelos. Ele define a semântica das funções da biblioteca para permitir aos usuários escrever programas portáteis de passagem de mensagens em C, C ++ e Fortran.
Open Multi Processing (Open MP): É uma interface de programação de aplicativo (API) que oferece suporte a modelos de programação de memória compartilhada em várias plataformas de sistemas multiprocessadores.
CUDA e OpenACC : CUDA e OpenACC (respectivamente) são plataformas de API de computação paralela projetadas para permitir que um engenheiro de software utilize unidades computacionais da GPU para processamento de propósito geral.
Threading Building Blocks e RaftLib : Ambos os ambientes de programação de código aberto que permitem o paralelismo de dados / tarefas combinados em ambientes C / C ++ em recursos heterogêneos.

Formulários

O paralelismo de dados encontra suas aplicações em uma variedade de campos, desde física, química, biologia, ciências de materiais até processamento de sinais. Ciências implicam paralelismo de dados para simular modelos como dinâmica molecular, análise de sequência de dados do genoma e outros fenômenos físicos. As forças motrizes no processamento de sinais para paralelismo de dados são a codificação de vídeo, processamento de imagens e gráficos, comunicações sem fio, para citar alguns.

Veja também

Notas

^ Alguns dados de entrada (por exemplo, quando d.length avaliado para 1 e round arredondado para zero [este é apenas um exemplo, não há requisitos sobre o tipo de arredondamento usado]) levará a lower_limit ser maior do que upper_limit , presume-se que o loop sairá imediatamente ( isto é, zero iterações ocorrerão) quando isso acontecer.

Referências

Hillis, W. Daniel e Steele, Guy L. , Data Parallel Algorithms Communications of the ACM dezembro 1986
Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X

[5] Alguns dados de entrada (por exemplo, quando d.length avaliado para 1 e round arredondado para zero [este é apenas um exemplo, não há requisitos sobre o tipo de arredondamento usado]) levará a lower_limit ser maior do que upper_limit , presume-se que o loop sairá imediatamente ( isto é, zero iterações ocorrerão) quando isso acontecer.

Languages

In other projects