Conceitos de Programação Paralela

MO801/MC972

3 origens para threads

• Task– Diferentes atividades atribuidas à diferentes

threads

• Data– Muitas threads executando a mesma

operação sobre dados diferentes

• Data flow– Uma thread opera com o dado fornecido pela

outra (produtor-consumidor)

Task decomposition

• Geralmente a forma mais fácil de paralelizar• Implica em detectar tarefas que podem ser

executadas separadamente pelos programas• Normalmente requer pouca modificação no

código– Preparo do código para evitar conflito entre duas

tarefas

• Muito comum para interface com o usuário

Data decomposition

• O dado a ser processado é dividido em pedações e o mesmo código é utilizado para processá-lo

• Comum em processamento de áudio, imagens e programas científicos

• Com o aumento no número de processadores, é possível aumentar o tamanho do problema

• Modifica pouco o código– Geralmente o início e o final da tarefa apenas

Data-flow decomposition

• Foca no problema da transferência de dados entre várias threads– Modelo produtor/consumidor– O produtor gera os dados que o consumidor utiliza– O consumidor só pode iniciar após o produtor– Múltiplos produtores/consumidores podem ser

encadeados

• Cuidado com as latências de início e finalização do processo

Problemas (Data-flow)

• As dependências criadas podem causar grande atraso– Exige maior conhecimento das tarefas para melhor distribuir a

carga– Deve-se evitar situações onde os consumidores ficam

esperando os dados

• As dependências de contexto podem implicar em mais dados a serem transferidos– A interação entre o produtor e o consumidor pode gerar um

overhead grande

• Balancear a carga de processamento entre as threads– Evitar que threads consumidoras fiquem Idle– Por causa da relação de dependência, nem sempre é fácil fazer

esse balanceamento de carga

Níveis de dificuldade

• Thread decomposition– Quando possível, é o mais simples de implementar

• Data decomposition– Nível intermediário, principalmente por causa da

divisão dos dados e sincronismos no início e final

• Data-flow decomposition– Mais complicado em relação ao código seqüencial– Alternativa geralmente ditada pelo tipo de programa a

paralelizar

Exemplo

• Considere o processamento de um vídeo sem dependência entre os quadros sucessivos– Task decomposition

• Uma thread para decodificar um quadro, outra para processar um quadro, etc

– Data decomposition• Cada thread processa um quadro

– Data-flow decomposition• Similar ao Task decomposition nesse caso

• Qual o tamanho de um quadro de vídeo?– Quantos podem ser processados simultaneamente?

Desafios

• Threads permitem que mais de uma atividade ocorra ao mesmo tempo

• Gerenciar atividades diferentes pode gerar problemas de sincronização, comunicação, balanceamento de carga e escalabilidade– Como medir esses problemas?– Como decidir antecipadamente quais

enfrentar?

Desafios

• Sincronização– Como coordenar a atividade de duas ou mais

threads?• Comunicação

– Quanto de transferência de dados (banda e latência) é necessário?

• Balanceamento de carga– Como distribuir o trabalho entre as threads de forma

a não deixar threads ociosas?• Escalabilidade

– Como fazer bom uso das threads quando o sistema computacional aumentar?

Padrões de Programação

• Task-level parallelism– Task decomposition

• Divide and Conquer– Task/Data decompsition

• Geometric Decomposition– Data decomposition

• Pipeline– Data-flow decomposition

• Wavefront– Data-flow decomposition

Task-level Parallelism Pattern

• Focar diretamente nas atividades a serem realizadas

• Problemas são decompostos em tarefas que operam independentemente– Pode ser necessário remover as

dependências entre essas tarefas (replicação?)

• Exemplos: embarrassingly parallel problems e replicated data problems

Divide and Conquer Pattern

• O problema é dividido em um número de sub-problemas menores

• Quando o problema é resolvido, o resultado é agrupado para formar a solução final

• Como cada sub-problema é independente, eles podem ser executados em paralelo

• Em geral faz uma boa distribuição de carga• Exemplo: Merge sort

Geometric Decomposition Pattern

• Baseado na paralelização de estruturas de dados usadas no problema– O foco é na estrutura de dados

• Cada thread é responsável por operar em parte dos dados

• Exemplo: Propagação de ondas e calor

Pipeline Pattern

• Quebrar o problema em várias fases subseqüentes

• Encontrar essa concorrência geralmente é mais difícil– Balancear a concorrência é mais difícil ainda

• Cada estágio deve ser capaz de executar uma determinada tarefa e todos devem trabalhar simultaneamente

Wavefront Pattern

• Processamento dos elementos de uma matriz através de uma diagonal– Como se fosse uma onda passando pela

matriz

• Em geral, é utilizado quando há dependências entre os elementos de uma matriz 1 2 3

2 3 4

3 4 5

Exemplo: Error Diffusion

• É um algoritmo para converter imagens com grande quantidade de bits por pixel em imagens em preto e branco– Usado para imprimir as imagens

• Havendo um grande número de pontos pequenos, é difícil notar a piora da imagem

• Exemplo: conversão de 8 bits para 1 bit

Passos para cada ponto

1. Determinar o valor a ser associado ao ponto atual

• Valores em [0, 127] são mapeados em 0• Valores em [128, 255], são mapeados em 1

2. A partir do valor do resultado, o erro é calculado

• Ex.: 168 é mapeado em 1 com erro de -87 (= 255 – 168)

3. O erro é distribuido entre os pontos vizinhos conforme uma matriz de pesos

• Exemplo 7/16

3/16 5/16 1/16

Pseudo-códigovoid error_diffusion(unsigned int width, unsigned int heigh,

unsigned short **InputImage, unsigned short **OutputImage){

for (unsigned int i = 0; i < height; i ++) { for (unsigned int j = 0; j < width; j ++) {

/* 1 */if (InputImage[i][j] < 128)

OutputImage[i][j] = 0;else

OutputImage[i][j] = 1;/* 2 */int err = InputImage[i][j] – 255 * OutputImage[i][j];/* 3 */InputImage[i][j+1] += 7/16;InputImage[i+1][j-1] += 3/16;InputImage[i+1][j] += 5/16;InputImage[i+1][j+1] += 1/16;

} } }

Análise

• Como dividir o código anterior?

• Que tipo de tarefas quebrar?

• Como quebrar os dados?

Alternativa

• O problema dos pesos também pode ser visto como

1/16 5/16 3/16

7/16

Alternativas

• Processar uma linha por thread, atrasando cada linha em duas colunas

• Processar uma página por thread, sem quebrar os dados

• Processar pedaços de páginas por thread, passando para a próxima página ao final de cada bloco

• etc