Identificação de Paralelismo

Aleardo Manacero Jr.

Paralelização de programas

Já vimos como identificar pontos em que não se pode paralelizar tarefas

Falta agora examinar como identificar pontos passíveis de paralelização e como implementar o paralelismo em um programa (sabendo de antemão que não existe receita pronta para isso)

Paralelização de programas

Um programa pode ser paralelizado, sempre que for conveniente, por dois agentes distintos:

Pelo compilador

Pelo programador

Paralelismo pelo compilador

Usualmente é chamado de ILP (Instruction Level Parallelism)

Deve identificar dependências e fazer a paralelização quando, comprovadamente, tivermos códigos independentes

Mais factível para máquinas de memória compartilhada (multiprocessadores), pela ausência de código para troca de mensagens

Paralelismo pelo compilador

O compilador atua se receber parâmetros específicos de paralelização

O usuário pode (e deve) interferir no processo, dirigindo (ou auxiliando) o compilador na identificação dos pontos para paralelização

Exemplos

DO I = 1,N

A(I) = A(I+K) * B(I)

ENDDO

É paralelizável se K>-1

DO I = 1,N

A(K(I)) = A(K(J)) + B(I) * C

ENDDOÉ paralelizável se K(I)K(J) p/ I,J:1,N e IJ

Exemplos

DO I = 1,N

CALL BIGSTUFF(A,B,C,I,J,K)

ENDDO

É paralelizável se a função é independente

DO I = L,N

A(I) = B(I) + C(I)

ENDDO

É paralelizável se N-L for grande

Paralelismo pelo programador

Realizado normalmente para ambientes de memória distribuída (multicomputadores)

Neles é o usuário (programador) quem deve identificar e implementar o paralelismo

A forma em que o paralelismo ocorrerá depende, fundamentalmente, da estrutura de conexão entre processadores

Paralelismo pelo programador

A dependência da estrutura de conexão faz com que o tempo gasto com comunicação limite:

o tamanho do grão de processamento

o grau de paralelismo da máquina

Comunicação X tamanho do grão

Se entre cada grão for necessário trocar valores (existir intersecção entre os conjuntos de saída do primeiro grão e de entrada do segundo), então os grãos devem ser suficientemente grandes para compensar o tempo gasto com comunicação

Grau de paralelismo

Se a velocidade em que se recebe novos dados for menor do que a capacidade de processamento, então não se deve aumentar o grau de paralelismo (aumentaria a ociosidade dos elementos de processamento)

Paralelismo pelo programador

A paralelização de um programa deve sempre levar as restrições de grau de paralelismo e tamanho de grão em consideração

Com isso, a identificação do paralelismo possível passa a ser uma tarefa de dimensionamento do ponto ótimo de particionamento do problema

Contraexemplos

Sistemas com dominação de E/S:

Aqui temos a restrição do tamanho do grão

Quando existe dominação de E/S (pouco processamento, muita E/S) fica impossível paralelizar o sistema, exceto na hipótese remota de E/S em altíssima velocidade

Contraexemplos

Sistemas iterativos de corpo curto:

Aqui temos a restrição de grau de paralelismo

Nos casos em que o corpo de um processo iterativo é muito curto (poucas operações, levando a ociosidade entre iterações), então é também impossível a paralelização

(isso tem mudado com GPUs)

Modelos de particionamento

Quando a paralelização de um programa é

feita pelo programador é necessário definir

qual o modelo de particionamento a ser

utilizado

Modelos de particionamento

Modelos de particionamento são modelos que

definem como o processamento paralelo

ocorrerá e de que forma os programas

paralelos irão interagir

Modelos de particionamento

A decisão sobre qual modelo deve ser utilizado depende de:

características do problema

características da máquina

O que significa depender de qual é o melhor tipo de casamento entre software e hardware

Modelos de particionamento

Um caso clássico desse casamento surge na

multiplicação de matrizes, em que o caminho

entre linhas e colunas não é feito sempre da

mesma forma, como visto na próxima figura

Multiplicação de matrizes

Multiplicação de matrizes

Nesse caso o particionamento do problema deve minimizar a necessidade de se percorrer muitas linhas ou colunas em ordem inversa

Ou ainda minimizar as trocas de cache

Uma forma de se fazer isso é multiplicar a matriz através de blocos

Multiplicação em blocos

Multiplicação em blocos

Para os casos em que as matrizes se tornam grandes demais deve-se considerar a possibilidade de outras formas de divisão em blocos

Multiplicação em blocos

Multiplicação em blocos

Para os casos em que as matrizes se tornam grandes demais deve-se considerar a possibilidade de outras formas de divisão em blocos

Essas formas devem, sempre, levar em consideração o tamanho dos blocos de cache

Outros métodos, como Strassen, são usados...

Paradigmas para interação

Pode-se considerar a existência de três paradigmas básicos de interação entre processos paralelos, que são:

Saco de Tarefas (Bag-of-Tasks)

Batimento (Heartbeat)

Linha de Produção (Pipeline)

Modelo “bag of tasks”

Implementado através de algoritmos centralizados, em que um processo assume o controle e os demais fazem o processamento de fato

A idéia de saco de tarefas vem de sua forma de operação, em que os trabalhadores buscam novas tarefas com o coordenador (que tem o saco com as tarefas)

Modelo “bag of tasks”

As tarefas são usualmente novos dados a serem processados pelo trabalhador

Após a manipulação desses dados, o trabalhador devolve os resultados ao coordenador

O sincronismo entre coordenador e trabalhadores é feito por requisições dos trabalhadores

Modelo “bag of tasks”

A interação entre trabalhadores deve ser evitada, diminuindo assim a necessidade de comunicação entre esses processos

Uma consequência desse modelo é o balanceamento da carga entre trabalhadores, pois novas tarefas apenas são recebidas após a conclusão do trabalho atual

Funcionamento do modelo

Funcionamento do modelo

Funcionamento do modelo

Funcionamento do modelo

Modelo “heartbeat”

Nesse modelo o gerenciamento é normalmente descentralizado

Isso exige um volume maior de comunicação e de interação entre os programas paralelos

Modelo “heartbeat”

O nome do modelo vem de sua estrutura de funcionamento que imita, de certo modo, os batimentos cardíacos

Cada processador trabalha em três fases (expansão, contração e processamento), que se repetem iterativamente até se chegar à solução

Modelo “heartbeat”

Durante a fase expansão ocorre o envio de dados por todos os processos

Funcionamento do modelo

Modelo “heartbeat”

Durante a fase expansão ocorre o envio de dados por todos os processos

Na contração cada processo recebe os dados enviados pelos demais processos

Funcionamento do modelo

Modelo “heartbeat”

Durante a fase expansão ocorre o envio de dados por todos os processos

Na contração cada processo recebe os dados enviados pelos demais processos

Na fase de processamento ocorre, obviamente, o processamento dos dados recém-recebidas

Funcionamento do modelo

Modelo “pipeline”

Nesse modelo simula-se, em software, a operação de um pipeline de hardware, numa estrutura de paralelismo de tarefa

Cada elemento de processamento executa ações sobre os dados de um problema, de forma que os resultados sejam a entrada para o próximo elemento de processamento

Modelo “pipeline”

Sistemas pipeline se prestam bem para problemas como filtros de ordenação, em que cada processador faz o merge (intercalação) da operação realizada em outros dois processadores

Outra aplicação interessante é a implementação de redes neurais paralelas

Modelo “pipeline”

Pipelines podem ser de três tipos:

Aberto

Fechado sem coordenador

Fechado com coordenador

Funcionamento do modelo

Funcionamento do modelo

Funcionamento do modelo

Programando em paralelo

Além da forma de atribuição de atividades aos elementos de processamento podemos pensar em como as atividades se relacionam

Nesse sentido temos:

Tarefas independentes

Tarefas em workflow

Tarefas independentes

Qualquer dos modelos anteriores pode ser usado

Bag of Tasks se encaixa perfeitamente para essas tarefas

Normalmente resulta no que se chama “embarrasingly parallel system”

Tarefas em workflow

Qualquer dos modelos anteriores pode ser usado

O problema aqui é determinar quando uma tarefa se torna apta a ser executada

Demanda cuidados com sincronismo

Programando em paralelo

Além dos modelos de particionamento podemos definir estratégias na forma de programar

Nesse sentido podemos pensar em:

Paralelismo por dados

Paralelismo por eventos/tarefas

Paralelismo por tarefas

Aparece tipicamente quando se programa em sistemas MIMD, com cada elemento de processamento executando tarefas diferentes para dados iguais ou diferentes

Enfatiza a natureza distribuída de processamento

Paralelismo por dados

Aqui o programa paralelo é construído considerando que em todos os elementos de processamento se executa o mesmo código, sobre dados diferentes

É a estratégia básica para SIMD/SPMD

É também a estratégia em MapReduce

Hadoop MapReduce

Projetado para tarefas independentes, executadas em batch

Grandes quantidades de dados, contidos em um DFS

Framework faz a distribuição dos dados e agrupamento das “respostas”

Hadoop MapReduce

Sua ideia básica é dividir o problema em duas fases:

Uma embaraçosamente paralela, que é a função map

Outra de composição, dada pela função reduce

Estrutura básica de dados formada por pares chave-valor

Hadoop MapReduce

Hadoop MapReduce – exemplo

class Mapper

method Map(doc_id a, doc d)

for all term t in doc d do

Emit (term t, count 1)

class Reducer

method Reduce(term t, counts[c1, c2, …])

sum = 0

for all count c in counts[c1,c2,…] do

sum = sum + c

Emit (term t, count sum)

Transactional Memory

Busca aplicar a ideia de transações (de bancos de dados) na paralelização

Conceito proposto na década de 80, mas recebendo mais atenção recentemente

Tarefas em paralelo são executadas como se fossem independentes e sua validade é verificada no final (commit)

Transactional Memory

A principal vantagem é a abordagem otimista em relação aos conflitos em regiões críticas

Desvantagens aparecem quando esse otimismo não se confirma

Transactional Memory

Primeiros usos vieram com implementações em software (STM), nos anos 90

Linguagens como Haskell, Scala, Clojure, C/C++ (gcc 4.7) apresentam construções para a programação de STM

Transactional Memory

Implementações em hardware surgiram em 2007

Sun sparc v9, mas era ineficiente e com alto consumo de energia

PowerPC A2 (2011), com HTM operando na cache L2

Transactional Memory

Maiores avanços nesta década

Power 8 (2013), também operando em cache, com tratamento de exceções por software

Intel Haswell (2013), com HTM operando na cache L1, usando HLE (hardware lock ellision) e RTM (restricted TM),

Transactional Memory

Lock ellision é uma técnica em que se executa a região crítica como uma transação e, caso não ocorra o commit dela, então bloqueia a thread que a executava

Próximo slide ilustra uma possível implementação de lock ellision

Transactional Memory

void elided_lock_wrapper(lock) {if (_xbegin() == _XBEGIN_STARTED) { /* Start transaction */ if (lock is free) /* Check lock and put into read-set */

return; /* Execute lock region in transaction */

_xabort(0xff); /* Abort transaction as lock is busy */} /* Abort comes here */take fallback lock

}

void elided_unlock_wrapper(lock) {if (lock is free) _xend(); /* Commit transaction */else unlock lock;

}

Considerações finais

O paralelismo existente em cada problema varia bastante, exigindo sempre uma análise cuidadosa de como tal problema pode ser resolvido

A solução desse problema depende, na prática, da identificação da melhor forma de particionamento do problema

Considerações finais

Felizmente existem poucas formas básicas de particionamento, que são “facilmente” mapeáveis aos problemas típicos de computação de alto desempenho

A escolha pelo modelo correto implica em bons ganhos de eficiência e desempenho