Plataformas de Computação Paralela

Prévia do material em texto

2
PLATAFORMAS PARA COMPUTAÇÃO
PARALELA
As limitações de desempenho de um sistema computacional estão relacionadas prin-
cipalmente à velocidade do processador e à capacidade de acesso e armazenamento em
memória. Baseado nestes elementos, as plataformas computacionais foram classificadas.
Este capítulo visa apresentar as principais plataformas de computação paralela e distribuída
existentes e quais as limitações dos recursos computacionais para se obter alto desem-
penho. As informações apresentadas estão baseadas em [Quinn (2004), Grama (2003),
Jaja (1992), Pitanga (2002)].
2.1 PARALELISMO IMPLÍCITO
A velocidade de clock dos microprocessadores tem apresentado um aumento expres-
sivo - duas ou três ordens de magnitude - em relação a 20 anos atrás. Entretanto, este
aumento na velocidade do clock é diluído pelas limitações da tecnologia de memória. Ao
mesmo tempo, níveis mais altos de integração de dispositivos têm também resultado em
bom desempenho. Conseqüentemente, técnicas que permitem a execução de múltiplas
instruções em um único ciclo de clock têm se tornado populares.
Processadores podem explorar o paralelismo em nível de instrução ou ILP (Instruction-
level parallelism) para tentar melhorar o desempenho do processador por ter múltiplos
componentes de processamento ou unidades funcionais executando instruções simulta-
neamente. Há duas técnicas principais de ILP: pipeline, onde unidades funcionais são
arranjadas em estágios e múltiplas execuções, onde múltiplas instruções podem ser simul-
taneamente iniciadas.
Na técnica de pipeline, a sobreposição de vários estágios de execução de instruções
(busca, escalonamento, decodificação, busca de operando, execução, armazenamento, en-
tre outros), em pipelines, permite uma execução mais rápida. Fazendo analogia com uma
linha de produção de um carro, se a produção de um carro levar 100 unidades de tempo,
esta produção pode ser quebrada em 10 estágios de pipeline com 10 unidades cada. As-
sim, uma única linha de produção pode produzir um carro a cada 10 unidades de tempo.
18 DCC/UFLA - Programação Paralela e Distribuída
Isto representa uma aceleração (speedup) de 10 vezes na produção de um carro totalmente
seqüencial, um após o outro. Desta forma, o aumento do desempenho para um único pi-
peline é obtido através da divisão das tarefas em unidades menores (estágios), formando
o pipeline e aumentando a sobreposição na execução da tarefa. Considere a Figura 2.1
que apresenta um pipeline de 5 estágios, onde cada instrução é representada como tarefa.
Pode-se observar que cada tarefa foi dividida em busca, decodificação, execução, acesso
a memória e resultado. No tempo 1, a Tarefa 1 executa a busca da instrução. No tempo 2
começa sua decodificação, enquanto a Tarefa 2 inicia a busca da instrução. No tempo 3, a
Tarefa 1 realiza a execução, a Tarefa 2 a decodificação e a Tarefa 3 a busca da instrução.
Estes passos são realizados até se obter o resultado. Se cada tarefa fosse executada de
forma sequencial, ou seja, se fossem realizados todos os estágios da Tarefa 1 e somente
depois da Tarefa 2 e assim por diante, seriam necessárias 20 unidades de tempo para exe-
cutar as 4 tarefas. Utilizando o pipeline são necessários apenas 8 unidades de tempo, pois
há estágios das tarefas que são realizados de forma concorrente.
Figura 2.1: Pipeline de 5 estágios
No contexto de processadores isto permite taxas de clock mais rápidas já que as tare-
fas são agora menores. Por exemplo, a arquitetura Core tem um pipeline de 14 estágios. A
velocidade de um único pipeline é limitado pela maior tarefa atômica no pipeline. Entretanto,
em instruções típicas, toda quinta ou sexta instrução é uma instrução de desvio. Pipelines
de instruções longas precisam de técnicas eficientes para prever destino de desvios tal que
pipelines possam ser preenchidos especulativamente. A penalidade de uma previsão incor-
reta aumenta quando os pipelines tornam-se mais profundos já que um grande número de
instruções precisam ser desfeitas. Estes fatores colocam limitações na profundidade de um
pipeline de processador.
Uma forma de melhorar a taxa de execução de instrução além deste nível é usar
múltiplos pipelines. Durante cada ciclo de clock, múltiplas instruções são colocadas em um
pipe no processador em paralelo. Estas instruções são executadas em múltiplas unidades
funcionais.
Plataformas para Computação Paralela 19
Por exemplo, se há dois somadores de ponto flutuante, a execução gastará aproxima-
damente a metade do tempo para executar o loop
for (1 = 0; i < 1000; i++) z[i] = x[i] + y[i];
Enquanto o primeiro somador está computando z[0], o segundo pode computar z[1].
Enquanto o primeiro está computando z[2], o segundo pode computar z[3] e assim por di-
ante.
Considere, por exemplo, um processador com 2 pipelines e a habilidade de simultane-
amente executar duas instruções. Este tipo de processador recebe o nome de processador
super-pipelined. A habilidade de um processador tratar múltiplas instruções no mesmo ci-
clo é referida como execução superescalar. Em um programa as instruções podem estar
relacionadas. Então, os resultados de uma instrução podem ser requeridos por instruções
subseqüentes (dependência de dados verdadeira). Outro tipo de dependência ocorre, por
exemplo, quando duas instruções utilizam a mesma unidade de ponto de flutuante (depen-
dência de recursos). Na execução de um desvio condicional, o destino do desvio somente
é conhecido no momento da execução e o escalonamento de instruções, a priori, através
de desvios pode gerar erros (dependência de desvio ou dependência procedural).
A habilidade de um processador detectar e escalonar instruções concorrentes é crí-
tica para o desempenho superescalar. Para isso é necessário que as instruções sejam
escalonadas fora de ordem. Neste caso, o paralelismo é explorado em nível de instrução.
O desempenho de arquiteturas superescalares é limitado pela disponibilidade de pa-
ralelismo em nível de instrução.
O paralelismo em nível de thread ou TLP (Thread-level parallelism) tenta prover para-
lelismo através de execuções simultâneas de diferentes threads. As unidades do programa
que estão sendo executadas simultaneamente (threads) são maiores do que as instruções
individuais.
2.2 LIMITAÇÕES DE DESEMPENHO DO SISTEMA DE MEMÓRIA
O desempenho de um programa em um computador depende da velocidade do pro-
cessador e também da habilidade do sistema de memória para fornecer dados ao proces-
sador. Em nível lógico, um sistema de memória, possivelmente consistindo de múltiplos
níveis de cache, realiza uma requisição por uma palavra de memória e retorna um bloco de
dados de tamanho b contendo a palavra requisitada após l nanossegundos, onde l é a la-
tência da memória. A taxa em que o dado pode ser copiado da memória para o processador
determina a banda do sistema de memória.
Considere um processador operando a 1GHz (1ns de clock) conectado a uma DRAM
com uma latência de 100ns (sem cache). Assuma que o processador tenha 2 unidades
multiplicação-adição e seja capaz de executar quatro instruções em cada ciclo de 1ns. O
20 DCC/UFLA - Programação Paralela e Distribuída
processamento máximo é de 4 GFLOPS (Giga FLoating point Operations per Second). Já
que a latência de memória é igual a 100 ciclos e o tamanho de bloco é de uma palavra, toda
vez que uma requisição de memória é realizada, o processador deve esperar 100 ciclos
antes que ele possa processar o dado. Considere o problema de computar o produto de dois
vetores em tal plataforma. Uma computação de produto realiza uma multiplicação-adição
de um único par de elementos do vetor, isto é, cada operação de ponto flutuante requer
uma busca de dado. É fácil verificar que a velocidade de pico destacomputação é limitada
a uma operação de ponto flutuante a todo 100ns, ou à velocidade de 10MFLOPS, uma fração
muito pequena da taxa máxima do processador. Este exemplo destaca a necessidade de
desempenho do sistema de memória em alcançar altas taxas de computação.
A presença de caches pode melhorar o desempenho baseado na hipótese de que há
repetidas referências a um mesmo item de dados. Esta noção de referência repetida a um
item de dados em uma janela de tempo pequena é chamada de localidade temporal. A
reutilização de dados é crítica para o desempenho de caches porque se cada item de dado
é usado somente uma vez, ele teria de ser buscado uma vez por uso para a DRAM e a
latência da DRAM ocorreria para cada operação.
A banda de memória refere-se à taxa em que os dados podem ser movidos entre o
processador e a memória. É determinada pela largura de banda do barramento da memória
bem como pela unidade de memória. Uma técnica muito usada para melhorar a largura
de banda da memória é aumentar o tamanho dos blocos de memória. Para exemplificar,
assuma que uma única requisição de memória retorna um bloco contíguo de 4 palavras. A
única unidade de 4 palavras neste caso é referida como uma linha de cache. Computadores
convencionais tipicamente buscam dois a oito palavras juntas na cache.
Considere um sistema de memória com um único ciclo de cache e 100 ciclos de
latência DRAM com o processador operando a 1 GHz. Se o tamanho de bloco é de uma
palavra, o processador leva 100 ciclos para buscar cada palavra. Para cada par de palavras,
o produto de vetores realiza uma multiplicação-adição, isto é, 2 FLOPs. Além disso, o
algoritmo realiza um FLOP a todo 100 ciclos para uma velocidade de pico de 10 MFLOPS.
Considere que o tamanho do bloco é aumentado para 4 palavras, isto é, se o proces-
sador puder buscar uma linha de cache de 4 palavras a cada 100 ciclos. Assuma que os
vetores são colocados de forma linear em memória, 8 FLOPs (4 operações multiplicação-
adição) podem ser realizadas em 200 ciclos. Isto é porque um único acesso de memória
busca 4 palavras consecutivas no vetor. Além disso, 2 acessos podem buscar 4 elementos
de cada um dos vetores. Isto corresponde a um FLOP a cada 25 ns, para uma velocidade
de pico de 40 MFLOPS. Note que o aumento no tamanho do bloco de um para 4 palavras
não mudou a latência do sistema de memória. Entretanto, aumenta a banda de memória
em 4 vezes. Neste caso, o aumento da banda do sistema de memória permite-nos acelerar
o algoritmo do produto de vetores que não tem dados para serem reutilizados.
Plataformas para Computação Paralela 21
O cenário ilustrado anteriormente corresponde a um barramento de dados largo (4
palavras ou 128 bits) conectado a múltiplos bancos de memória. Na prática, tal largura de
barramento é cara para se construir. Em um sistema mais prático, palavras consecutivas
são enviadas ao barramento de memória em ciclos de barramento subseqüentes após a
primeira palavra ser recuperada. Por exemplo, com um barramento de dados de 32 bits,
a primeira palavra é colocada no barramento depois de 100ns (latência associada) e uma
palavra é coloca em cada ciclo de barramento subseqüente.
Quando os dados consecutivos em memória são usados por instruções sucessivas
há uma localidade espacial de acesso à memória. Se a computação não tem localidade
espacial, então a banda pode ser muito menor do que a banda máxima.
Um exemplo de tal padrão de acesso é ler uma matriz densa por coluna quando a ma-
triz seria armazenada em memória por linha. Compiladores podem ser programados para
fazer um bom trabalho reestruturando a computação para aproveitar a localidade espacial.
Considere o fragmento de código:
1 for (i = 0; i < 1000; i++){
2 column_sum[i] = 0.0;
3 for (j = 0; j < 1000; j++)
4 column_sum[i] += b[j][i];
}
O fragmento de código soma as colunas da matriz b em um vetor column_sum. Duas
observações importantes podem ser feitas: (i) o vetor column_sum é pequeno e pode
facilmente caber na cache e (ii) a matriz b é acessada na ordem das colunas. Para uma
matriz de tamanho 1000 x 1000, armazenada na ordem das colunas, isto corresponde a
acessar todas as 1000 entradas, como ilustra a Figura 2.2(a).
Pode ocorrer que somente uma palavra de cada linha de cache buscada na memória
seja usada. Conseqüentemente, o fragmento de código produzirá um desempenho ruim.
A falta de localidade espacial em computação causa um desempenho ruim do sistema de
memória. Mas freqüentemente é possível reestruturar a computação para remover acesso
freqüente. Desta forma, o fragmento de código pode ser reescrito para que a matriz seja
varrida por linhas e não por colunas. O código reestruturado fica como segue:
1 for (i=0; i < 1000; i++)
2 column_sum[i] = 0.0;
3 for (j=0; j < 1000; j++){
4 for (i=0; i<1000; i++)
5 column_sum[i] += b[j][i];
}
22 DCC/UFLA - Programação Paralela e Distribuída
Figura 2.2: Multiplicação de uma matriz por um vetor: (a) multiplicação de coluna por coluna; (b)
multiplicação de linha por coluna
Neste caso, a matriz é varrida na ordem das linhas, como ilustrado na Figura 2.2(b).
Pode-se notar que o vetor column_sum pode ser mantido em cache durante a execução
do loop.
Este exemplo mostrou que os seguintes conceitos são importantes:
• Explorar localidade espacial e temporal em aplicações é crítico para amortizar a
latência de memória e aumentar o uso efetivo de banda de memória.
• Certas aplicações têm localidade temporal maior do que outras e têm maior tole-
rância à baixa banda de memória. A taxa entre o número de operações e o número
de acessos à memória é um bom indicador de tolerância antecipada para banda de
memória.
• A organização da memória e a organização da computação de forma apropriada
podem gerar um impacto significativo na localidade espacial e temporal.
2.2.1 Estratégias alternativas para esconder latência de memória
Suponha que um usuário esteja sentado em frente seu computador navegando pela
web durante um período de alto tráfego de rede. O desenvolvedor de um navegador pode
implementá-lo de forma que o tempo de resposta seja reduzido. Para isso, existem 3 estra-
tégias simples:
1. prefetching: antecipar quais páginas serão acessadas informando quais as requi-
sições que serão realizadas;
Plataformas para Computação Paralela 23
2. multithreading: abrir múltiplos navegadores e acessar diferentes páginas em cada
navegador. Enquanto espera-se que uma página seja carregada pode-se ler outras
páginas ou
3. localidade espacial: acessar um conjunto de páginas de uma vez só - amortizando
a latência de vários acessos.
Multithreading para esconder latência: Uma thread é um fluxo de execução de um
programa. Considere o exemplo de multiplicação de matriz por vetor para ilustrar threads.
Considere o seguinte código para multiplicar uma matriz a, n x n, por um vetor b, obtendo
um vetor c.
1 for (i=0; i < n; i++)
2 c[i] = dot_product(get_row(a,i),b);
Este código computa cada elemento de c como produto escalar da linha correspon-
dente de a pelo vetor b. Note que cada produto escalar é independente do outro e repre-
senta uma unidade de execução concorrente. Este segmento de código pode ser reescrito
como segue:
1 for (i=0; i < n; i++)
2 c[i] = create_thread(dot_product, get_row(a,i),b);
A única diferença entre os dois segmentos de código é que temos explicitamente es-
pecificada cada instância da computação do produto escalar como sendo uma thread. Con-
sidere a execução de cada instância da função dot_product. A primeira instância desta
função acessa um par de elementos do vetor e espera por eles. Enquanto isso, a segunda
instância desta função pode acessar dois outros elementos do vetor no próximo ciclo e as-
sim por diante. Apósl unidades de tempo, onde l é a latência do sistema de memória, a
primeira instância da função obtém o dado requisitado da memória e pode realizar a com-
putação requisitada. No próximo ciclo, os itens de dado para a próxima instância da função
são retornados e assim por diante. Desta forma, em todo ciclo de clock, pode-se realizar
uma computação.
A maneira como é realizada a execução deste exemplo pode ser analisada sob dois
aspectos: o sistema de memória é capaz de servir múltiplas requisições pendentes e o
processador é capaz de escalonar uma thread diferente a cada ciclo. Além disso, ele tam-
bém requer que o programa tenha uma especificação explícita de concorrência na forma de
threads.
Prefetching para reduzir latência: Em programa, um dado é carregado e usado por
um processador em uma pequena janela de tempo. Se o carregamento (load) do dado
resultar em um cache miss (dado não está em memória), então a execução é interrom-
pida para buscar o dado em disco. Uma solução simples para este problema é antecipar
a operação de carregamento (load) do dado tal que mesmo que haja um cache miss, o
dado chegue normalmente no tempo de ser usado. Entretanto, se o dado já tiver sido so-
24 DCC/UFLA - Programação Paralela e Distribuída
brescrito entre o carregamento e a utilização, uma atualização torna-se necessária. Note
que isso não é pior do que a situação em que o carregamento não tenha sido antecipado.
Uma análise cuidadosa desta técnica revela que prefetching funciona pela mesma razão
de multithreading. Antecipando o carregamento, estamos tentando identificar threads inde-
pendentes de execução que não tenham dependência de recursos entre si (isto é, usam os
mesmos registradores).
Considere o problema de adicionar dois vetores a e b usando um único loop for.
Na primeira iteração do loop, o processador requisita a[0] e b[0]. Como estes valores
não estão em cache, o processador deve esperar, havendo latência de memória. Enquanto
estas requisições estão sendo atendidas, o processador também requisita a[1] e b[1].
Assumindo que cada requisição é gerada em um ciclo de (1 ns) e as requisições de me-
mória são satisfeitas em 100 ns, após 100 requisições o primeiro conjunto de dados é
retornado pelo sistema de memória. Subseqüentemente, um par de componentes do vetor
será retornado a cada ciclo. Desta forma, em cada ciclo subseqüente, uma adição pode ser
realizada e ciclos de processador não são desperdiçados.
Uma desvantagem da utilização de prefetching e multithreading é que há necessidade
de mais memória. As requisições de memória em um sistema multithreaded podem aumen-
tar significativamente porque a cache residente de cada thread é pequena. Por exemplo,
considere que uma máquina tenha 32KB de memória cache e há a execução multithreaded
com 32 threads. Então, cada thread terá uma cache residente de 1KB, pois cada thread
terá maior necessidade de buscar dados em memória.
Em computadores paralelos a memória pode estar distribuída em diferentes computa-
dores, como é o caso dos clusters, ou compartilhada pelos processadores, em uma mesma
máquina. No caso da memória distribuída, somente o processador do computador que
possui o dispositivo de memória terá acesso aos dados. Os demais processadores locali-
zados em outros computadores deverão solicitar os dados através da troca de mensagens.
No caso da memória compartilhada, todos os processadores terão acesso a esta memó-
ria para leitura e escrita. Para não haver inconsistência de dados deverão ser adotadas
políticas de consistência de memória.
2.3 CLASSIFICAÇÃO DAS PLATAFORMAS PARALELAS
As plataformas paralelas podem ser classificadas de acordo com as características de
hardware ou com o fluxo de instruções e dados.
Considerando a perspectiva de memória, tem-se os modelos de memória distribuída
(distributed), memória compartilha (shared) e memória compartilhada-distribuída (distributed-
shared).
Plataformas para Computação Paralela 25
2.3.1 Modelo de memória distribuída
No modelo de memória distribuída, encontram-se os cluster de computadores pes-
soais ou estações de trabalho (workstations) que são também conhecidos como NOW
(Network of Workstations) ou cluster Beowulf.
Um cluster Beowulf é uma coleção de computadores e switches, localizados no mesmo
recinto, dedicados para execução de jobs paralelos. Os computadores tipicamente não pos-
suem teclado nem monitores, sendo acessados somente via rede. Todos os computadores
executam a mesma versão de sistema operacional e possuem imagens de disco local idên-
ticas. O cluster inteiro é administrado como uma entidade. A rede pode ser fast Ethernet
(100Mbit/sec), gigabit Ethernet (1000Mbit/sec) e Myrinet (1920Mbit/sec).
A Figura apresenta um exemplo de um cluster com 8 nós de processamento e um
servidor que realiza acesso externo. Todos os nós de processamento podem ser acessados
somente pelo servidor, que deverá ter firewall configurado, evitando ataques externos. Cada
nó de processamento não necessita ter mouse, teclado e vídeo, pois o acesso é realizado a
partir do servidor. Há softwares apropriados para cluster que realizam o escalonamento dos
programas para serem executados nos nós de processamento: Condor, PBS, LSF, SGE,
entre outros. Além disso, os softwares para monitoramento dos nós têm conhecimento de
quais nós estão ativos e poderão receber um programa para ser executado.
Figura 2.3: Cluster Beowulf
Uma rede de estações de trabalho é uma coleção de computadores distantes uns dos
outros e switches, tipicamente localizados na mesa do usuário. São tipicamente conec-
tados via Ethernet (10Mbit/sec) ou fast Ethernet (100 Mbit/sec). O objetivo de uma rede
de estações de trabalho é servir às necessidades da pessoa que a utiliza; a execução de
um job paralelo é simplesmente uma maneira para consumir ciclos de CPU desperdiçados.
Estações de trabalho individuais podem ter diferentes sistemas operacionais e programas
26 DCC/UFLA - Programação Paralela e Distribuída
executáveis. Um usuário pode desligar sua estação de trabalho, então há necessidade de
suporte para realizar checkpoint e reiniciar jobs.
Os clusters podem ser classificados, de acordo com sua finalidade, em: cluster de alta
disponibilidade, de alto desempenho e de balanceamento de carga.
Cluster de alta disponibilidade O cluster de alta disponibilidade tem a finalidade de man-
ter um determinado serviço de forma segura o maior tempo possível. A demanda deste tipo
de cluster ocorre em bancos, empresas financeiras e de seguros, serviço público, empresas
de comércio eletrônico, indústrias, entre outros. Os computadores possuem algum recurso
para detectar, recuperar e ocultar eventuais falhas. Os recursos computacionais pertencen-
tes a essa classe possuem uma disponibilidade entre 99,99% a 99,999%, ou seja, em um
ano de operação poderá existir indisponibilidade por um período de pouco mais de cinco
minutos. A Figura 2.4 ilustra este tipo de cluster, onde há dois servidores: um primário e um
secundário. Estes dois servidores são cópias idênticas um do outro. Caso o primário apre-
sente algum problema e o programa HeartBeat (verifica se o servidor está on-line) identifica
que o servidor primário está offline, o servidor secundário torna-se o primário e continua a
execução. O sistema de armazenamento de dados é compartilhado entre entres.
Figura 2.4: Cluster de Alta Disponibilidade.
Cluster de alto desempenho O cluster de alto desempenho é voltado para prover grande
poder computacional. Neste tipo de cluster são estudados algoritmos de processamento
paralelo e construção de aplicações paralelas distribuídas. O objetivo é diminuir o tempo
para a resolução de problemas computacionais. O primeiro cluster Beowulf construído tinha
este objetivo.Plataformas para Computação Paralela 27
Cluster de balanceamento de carga O cluster de balanceamento de carga tem como
finalidade distribuir carga entre servidores de modo que um único servidor não fique so-
brecarregado e outros sem carga. A Figura 2.5 ilustra este tipo de cluster onde há dois
computadores balanceadores que recebem as requisições e distribui entre os 3 servidores
que irão atender as requisições.
Figura 2.5: Cluster de Balanceamento de Carga
2.3.2 Modelo de memória compartilhada
O modelo de memória compartilhada possui a visão do espaço de endereçamento
compartilhado com todos os processadores. Os processadores interagem modificando da-
dos armazenados no espaço de endereçamento compartilhado. As plataformas de memória
compartilhada que suportam programação SPMD Single Program Multiple Data, operam
sobre múltiplas instâncias do mesmo programa executando sobre dados diferentes. Tais
plataformas são também conhecidas como multiprocessadas. A memória em uma plata-
forma de espaço de endereçamento compartilhado pode ser local (exclusiva a um proces-
sador) ou global (comum a todos os processadores). Se o tempo gasto por um processador
acessar qualquer palavra da memória no sistema (global ou local) é idêntico, a plataforma
é classificada como um multicomputador de acesso uniforme à memória - UMA (Uniform
Memory Access). Por outro lado, se o tempo gasto para acessar certas palavras na me-
28 DCC/UFLA - Programação Paralela e Distribuída
mória for maior do que outras, a plataforma é chamada de multicomputador de acesso
não-uniforme à memória - NUMA (Non-Uniform Memory Access).
Um multiprocessador UMA pode também ser denominado multiprocessador centrali-
zado ou multiprocessador simétrico (SMP - Symmetric Multiprocessor).
Um multiprocessador NUMA pode ser também denominado multiprocessador distri-
buído.
Em um multiprocessador UMA, os dados privados são os dados usados somente por
um único processador, enquanto os dados compartilhados são os dados usados por múlti-
plos processadores. Os processadores comunicam com os demais através de variáveis de
dados compartilhados e variáveis de controle para sincronização entre os processadores.
Semáforos e monitores que foram originalmente projetados para uniprocessadores e multi-
processadores são exemplos de como a sincronização pode ser alcançada em sistemas de
memória compartilhada.
A Figura 2.6 apresenta uma visão esquemática deste tipo de multiprocessador com
memória cache e sem memória cache.
(a)
(b)
Figura 2.6: Multiprocessador UMA (a) com cache e (b) sem cache
As desvantagens de um multiprocessador UMA são que (i) o barramento de memória
compartilhada limita o número de CPUs e (ii) podem surgir problemas associados a dados
compartilhados como coerência de cache e sincronização.
Plataformas para Computação Paralela 29
UMA - Coerência de cache
Coerência de cache é o problema existente para manter consistência entre as có-
pias do dado na memória global e as caches locais dos processadores. Esta consistência
pode ser realizada através da replicação de dados entre as múltiplas caches, reduzindo a
contenção entre processadores para valores de dados compartilhados. Mas quando cada
processador tem uma visão da memória em sua cache, é necessário que seja garantido
que processadores diferentes não tenham valores diferentes para a mesma locação de me-
mória.
A Figura 2.7 ilustra o problema de coerência de cache. Pode-se observar que em (a)
a locação de memória x contém o valor 7. Em (b) a CPU A lê o valor x e uma cópia de x
é armazenada na cache da CPU A. Em (c) a CPU B lê o valor de x e uma cópia de x é
armazenada na cache da CPU B. Até este ponto, as CPUs A e B possuem o mesmo valor,
7. Em (d) a CPU B armazena 2 em x. A locação de memória x (global) recebe um novo
valor. O valor é também atualizado na cache da CPU B. Entretanto, a CPU A tem um valor
antigo de x em sua cache.
Figura 2.7: UMA: problema de coerência de cache
Para resolver o problema de coerência de cache, pode-se adotar as políticas write-
through ou write-back.
Write-through: os dados escritos em cache são atualizados imediatamente na memó-
ria global.
Write-back: os dados escritos em cache só são escritos na memória global em caso
de troca do bloco da cache.
Os protocolos snooping são usados para manter coerência de cache em multipro-
cessadores UMA. Cada controlador de cache da CPU monitora (snoops) o barramento
para identificar que blocos de cache estão sendo requisitados por outras CPUs. A solu-
ção mais comum para o problema de coerência de cache é garantir que um processador
tenha acesso exclusivo a um item de dado antes de escrever seu valor. Antes de realizar
30 DCC/UFLA - Programação Paralela e Distribuída
a escrita, todas as cópias de itens de dados armazenados em cache de outras CPUs são
invalidados. Neste ponto, o processador realiza a escrita, atualizando o valor neste bloco
de cache e na locação de memória apropriada. Quando qualquer outra CPU tenta ler uma
locação de memória daquele bloco de cache, ocorrerá um cache miss, forçando-o a re-
cuperar o valor atualizado da memória. Isto é chamado de protocolo write invalidate. Se
dois processadores tentarem, simultaneamente, escrever na mesma locação de memória,
somente um deles vence a disputa. O bloco de cache do processador que perde a disputa
é invalidado. O processador que perde deve obter uma nova cópia do dado (com o valor
atualizado) antes que ele possa fazer sua escrita.
UMA - Sincronização
Vários tipos de sincronização podem ser necessários pelos processos cooperantes
para realizar uma computação:
• Exclusão mútua: situação em que no máximo um processo pode realizar uma ati-
vidade específica em qualquer momento.
• Barreira: muito utilizado em programas para memória compartilhada. Uma sincro-
nização por barreira garante que nenhum processo continuará a execução, num
ponto específico do programa, (chamado barreira) até que todos os processadores
tenham alcançado este ponto.
NUMA
Em um multiprocessador NUMA, cada processador possui uma memória próxima a
ele e o espaço de endereçamento é distribuído. Isto permite a existência de um número
maior de processadores. Desta forma, o acesso à memória local é muito mais rápido do
que o acesso à memória não local. A Figura 2.8 (a) ilustra a arquitetura do multiprocessador
NUMA. Esta figura não considera que cada CPU possui uma memória cache. A Figura 2.8
(b) ilustra a situação onde cada CPU tem uma memória cache, além da memória local.
Uma desvantagem deste tipo de multiprocessador é o tempo de acesso a um bloco
de memória, pois depende de onde ele está: em uma memória próxima ou distante do
processador.
Na Figura 2.8(b)um dado que está em cache pode estar incoerente com o dado que
está na memória local, que é compartilhada. Para realizar a consistência de cache, o
multiprocessador NUMA utiliza um protocolo baseado em diretório. Neste protocolo há
um único diretório que contém a informação de compartilhamento de todos os blocos de
memória que podem estar em cache. Para cada bloco de cache, a entrada no diretório
indica um dos seguintes estados do bloco:
Plataformas para Computação Paralela 31
(a)
(b)
Figura 2.8: Multiprocessador NUMA: (a) sem cache e (b) com cache
• uncached - não está atualmente na cache de nenhum dos processadores;
• shared - está na cache de um ou mais processadores e a cópia em memória global
é a mais atual;
• exclusive - está em cache de exatamente um processador que escreveu no bloco,
mas a cópia na memória global está obsoleta.
É necessário manter o acompanhamento de que processador tem cópias de qual-
quer bloco de cache, tal que estas cópias possam ser invalidadas quando um processador
escreverum valor para aquele bloco.
Para prevenir que o acesso ao diretório de cache torne-se um gargalo de desempenho,
o diretório deve ser distribuído entre as memórias locais do computador. Entretanto, os
conteúdos não são replicados: a informação sobre um bloco de memória particular está
exatamente em uma locação de memória.
32 DCC/UFLA - Programação Paralela e Distribuída
Considere o exemplo do protocolo baseado em diretório de um multiprocessador de
memória distribuída simples mostrado na Figura 2.9. (a) x tem o valor 7. Bloco contendo x
não está em cache. (b) Estado após CPU 0 ler x. (c) Estado após CPU 2 ler x. (d) Estado
após CPU 0 escrever valor 6 em x. (e) Estado após CPU 1 ler x. (f)Estado após CPU 2
escrever 5 em x. (g) Estado após CPU 0 escrever 4 em x. (h) Estado após CPU 0 apagar o
bloco de cache contendo x.
Na Figura 2.9 (a), o computador tem 3 CPUs: CPU 0, CPU 1 e CPU 2. Com cada
processador há associada uma memória cache, uma memória local e um diretório. No mo-
delo NUMA, as memórias locais dos processadores formam um espaço de endereçamento
único e qualquer CPU pode se referir a qualquer um destes endereços. A variável X está
armazenada na memória controlada pela CPU 2. Ela contém o valor 7. CPU 2 tem uma
entrada no diretório correspondente ao bloco de cache contendo X: "U000". Esta entrada
mostra que atualmente o bloco não está em cache (uncached).
Suponha que CPU 0 tente ler o valor de X. O bloco de cache contendo X não está na
cache da CPU 0. Uma mensagem read miss é enviada de CPU 0 para CPU 2. O status do
bloco de cache contendo X em CPU 2 é trocado para shared, o vetor de bits é atualizado
para mostrar que CPU 0 tem uma cópia do bloco de cache ("S100") e o bloco é enviado
para CPU 0 (Figura 2.9 b).
Em seguida, CPU 2 tenta ler o valor de X. O valor de X não está na cache da CPU 2.
Como resultado do read miss, o valor de X é copiado para a cache de CPU 2 (Figura 2.9 c).
Suponha que CPU 0 escreva 6 na variável X. Uma mensagem write miss é enviada de
CPU 0 para CPU 2. O controlador de diretório invalida a cópia do bloco de cache atualmente
na cache da CPU 2, atualiza o vetor de bits para mostrar que CPU 2 não tem mais uma
cópia do bloco e troca o estado do bloco de cache para exclusive ("E000"). A Figura 2.9 d
mostra o novo estado do sistema. Note que o valor de X em memória local de CPU 2 está
desatualizado.
Se CPU 1 tentar ler X, gerando um read miss, o controlador de diretório para CPU
2 envia uma mensagem switch to shared para CPU 0, que envia uma cópia do bloco de
cache de volta para CPU 2, de forma que fique uma cópia atualizada em memória local.
Então o bloco atualizado é enviado para CPU 1 (Figura 2.9 e).
Suponha que a próxima ação envolvendo o bloco de cache que está na CPU 2 escre-
vendo 5 a X. Já que o bloco não está mais em cache, ele gera uma mensagem de cache
miss de volta para o controlador de diretório. O controlador de diretório envia uma mensa-
gem de invalidação para CPU 0 e CPU 1, que removem os blocos de suas caches. Agora
um status do bloco é trocado para exclusive com owner CPU 2. Uma cópia do bloco é
enviada para cache da CPU 2 e CPU 2 atualiza o valor de X (2.9 f).
Em seguida, CPU 0 tenta escrever o valor 4 a X. Já que o bloco apropriado não está
em sua cache, CPU 0 gera uma mensagem write miss para o diretório de CPU 2, que
Plataformas para Computação Paralela 33
(a) (b)
(c) (d)
(e) (f)
(g) (h)
Figura 2.9: Ilustração do protocolo baseado em diretório para implementar coerência de cache em
um multiprocessador distribuído.
envia uma mensagem take away para controlador de cache de CPU 2. O bloco de cache é
copiado de volta para a memória. O estado do bloco permanece exclusive, mas o vetor de
34 DCC/UFLA - Programação Paralela e Distribuída
bits é atualizado para mostrar que o owner agora é CPU 0. Uma cópia do bloco é enviada
para cache de CPU 0 e o valor de X é atualizado (Figura 2.9 g).
Finalmente, suponha que CPU 0 decida limpar o bloco de cache contendo X. Já que
ele tem acesso exclusivo ao bloco, deve copiar o conteúdo do bloco de volta à memória de
CPU 2. O estado final é ilustrado na Figura 2.9 h.
A presença de um espaço de memória global torna a programação de computadores
com espaço de endereçamento de memória compartilhada muito mais fácil. Todas as in-
terações realizadas somente para leitura são invisíveis ao programador, quando elas são
codificadas igual a um programa seqüencial. Isto facilita a escrita de programas paralelos.
Interações de leitura e escrita são mais complicadas para programar do que interações so-
mente leitura, pois estas operações requerem exclusão mútua para acesso concorrente. Os
paradigmas de programação para espaço de endereçamento compartilhado tais como thre-
ads (POSIX, NT) e diretivas (OpenMP) suportam sincronização usando locks e mecanismos
relacionados.
É importante notar a diferença entre dois termos que são muito usados: computadores
de espaço de endereçamento compartilhado-distribuído e computadores de memória com-
partilhada. O termo computador de memória compartilhada é historicamente usado para
arquiteturas em que a memória está fisicamente compartilhada entre vários processadores,
isto é, cada processador tem acesso a qualquer segmento de memória. Isto é idêntico ao
modelo UMA. Isto é o contrário de computador com memória compartilhada-distribuída, em
que diferentes segmentos de memória são fisicamente associados a diferentes elementos
de processamento. Um computador com espaço de endereçamento compartilhado com
memória distribuída é idêntico a uma máquina NUMA.
2.3.3 Sistema de memória compartilhada multicore
Em um sistema de memória compartilhada com múltiplos processadores multicore a
interconexão pode conectar todos os processadores diretamente à memória principal ou
cada processador pode ter uma conexão direta ao bloco de memória principal e os proces-
sadores podem acessar os blocos de memória principal dos outros através de hardware
especial construído nos processadores. As figuras 2.10 e 2.11 ilustram um sistema multi-
core UMA e um NUMA, respectivamente. No primeiro tipo de sistema, o tempo de acesso
a todas as locações de memória será o mesmo para todos os cores. No segundo tipo, o
acesso a uma locação de memória para um core diretamente conectado à memória é mais
rápido do que o acesso de um core localizado em outro chip.
Plataformas para Computação Paralela 35
Figura 2.10: Um sistema multicore UMA [Pacheco (2011)]
Figura 2.11: Um sistema multicore NUMA [Pacheco (2011)]
36 DCC/UFLA - Programação Paralela e Distribuída
2.3.4 Comparação entre espaço de endereçamento compartilhado, distribuído e com-
partilhado-distribuído
A classificação das plataformas computacionais em plataforma de espaço de endere-
çamento compartilhado, espaço de endereçamento compartilhado distribuído e passagem
de mensagens refere-se à forma como o programa visualiza o acesso à memória da má-
quina paralela.
Na plataforma de espaço de endereçamento compartilhado, todos os processadores
acessam umamemória comum a eles. Na Figura 2.12 pode-se observar que há umamemó-
ria compartilhada que pode ser acessada por qualquer processador através do barramento.
Na Figura 2.13 pode-se observar que a memória que é local a cada processador é visuali-
zada pelo programador como uma memória compartilhada, representada por um retângulo
com linha mais grossa. O acesso a posições de memória necessita de uma camada de
software que deixe transparente para o desenvolvedor a troca de mensagens entre os pro-
cessadores para atualização das posições de memória. Na Figura 2.14, pode-se observar
que cada processador está em uma máquina diferente e a memória é local a esta máquina.
O programador somente consegue compartilhardados entre os processadores fazendo a
troca de mensagens de forma explícita. Não há a noção de memória compartilhada.
Figura 2.12: Multiprocessador UMA
Vantagens e desvantagens
Espaço de endereçamento compartilhado
Plataformas para Computação Paralela 37
Figura 2.13: Multiprocessador NUMA
Figura 2.14: Cluster
38 DCC/UFLA - Programação Paralela e Distribuída
As vantagens da programação para esta plataforma é que o tempo gasto para um
processador acessar uma palavra da memória no sistema é idêntico, de forma que a latên-
cia de acesso é igual para todos os processadores. Além disso, nesta arquitetura é fácil
programar, pois não é necessário realizar troca de mensagens de forma explícita para ter
acesso a um dado.
Entre as desvantagens podemos citar que o barramento de acesso à memória com-
partilhada limita o número de CPUs que podem ser colocadas em uma mesma máquina.
Podem surgir problemas associados a dados compartilhados como coerência de cache e
sincronização.
Espaço de endereçamento compartilhado distribuído
As vantagens desta plataforma é que permite a utilização de maior número de pro-
cessadores, aproveitando recursos computacionais já existentes. O programador tem uma
camada de software que deixa a troca de mensagens entre os processadores transparente
para ele. Desta forma, o programador pode programar da mesma forma que no espaço de
endereçamento compartilhado.
Como desvantagens pode-se citar o fato de haver uma grande quantidade de troca
de mensagens para o compartilhamento dos dados entre os processadores; o tempo de
acesso a um bloco de memória que não está local pode ser alto e o protocolo de coerência
de cache é mais complexo.
Espaço de endereçamento distribuído
As vantagens desta plataforma é que podem ser utilizadas máquinas conectadas em
rede para obter alto desempenho, como ocorre com os clusters de estações de trabalho. O
número de máquinas que podem ser utilizadas é ilimitado.
Como desvantagem, o programador precisa realizar a troca de mensagens de forma
explícita para obter os dados, usando uma biblioteca de passagem de mensagens.
Emulando passagem de mensagens em um sistema de memória compartilhada
O espaço de endereçamento compartilhado pode ser particionado em partes disjun-
tas, uma parte sendo atribuída a cada processador. Operações "send"e "receive"podem
ser implementadas pela escrita e leitura no espaço de endereçamento dos processadores
receptor e emissor. Especificamente, uma locação separada pode ser reservada como uma
caixa de mensagens para cada par ordenado de processos. Uma passagem de mensagens
Pi−Pj pode ser emulada por uma escrita de Pi na caixa de mensagens e uma leitura de Pj
da caixa de mensagens. O caso mais simples de uma caixa de mensagens assume que o
tamanho é ilimitado. Operações de leitura e escrita precisam ser controladas usando primi-
tivas de sincronização para informar ao receptor/emissor que o dado foi enviado/recebido.
Plataformas para Computação Paralela 39
Emulando memória compartilhada em um sistema de passagem de mensagens
Envolve o uso de operações "send"e "receive"para operações de escrita e leitura.
Cada locação compartilhada pode ser modelada como um processo separado; escrever
para uma locação compartilhada é emulada pelo enviado de uma mensagem de atualiza-
ção para o processo owner correspondente; uma leitura de uma locação compartilhada é
emulada pelo envio de uma mensagem de consulta do processo owner. Como acessar a
memória de outro processador requer operações de envio e recebimento, esta emulação
é cara. Portanto, esta emulação em um sistema distribuído envolve altas latências nas
operações de escrita e leitura.
Uma aplicação pode usar uma combinação de memória compartilhada e passagem
de mensagens. Em sistemas multiprocessadores, os processadores comunicam-se via
memória compartilhada. Entre dois computadores, a comunicação é feita por passagem de
mensagens.
2.3.5 Taxonomia de Flynn
A taxonomia de Flynn é uma classificação que depende do paralelismo exibido no seu
fluxo de instrução e no seu fluxo de dados. Os processadores podem executar o mesmo ou
diferentes fluxos de instrução ao mesmo tempo e processar ou não os mesmos (idênticos)
dados ao mesmo tempo. Assim, um processo pode ser visto como a execução de uma
seqüência de instruções (fluxo de instruções) que manipulam uma seqüência de operandos
(fluxo de dados). O foco é na multiplicidade de hardware usado para manipular o fluxo de
instruções e de dados. Desta forma, Flynn classificou os computadores em 4 categorias:
• SISD (Single Instruction Stream, Single Data Stream);
• SIMD (Single Instruction Stream, Multiple Data Stream);
• MISD (Multiple Instruction Stream, Single Data Stream) e
• MIMD (Multiple Instruction Stream, Multiple Data Stream).
A Figura 2.15 ilustra o fluxo de dados e de instruções destas categorias.
2.3.6 SISD
A arquitetura SISD refere-se aos computadores com um único fluxo de instrução e um
único fluxo de dados. Um sistema clássico de von Neumann é um sistema SISD. Corres-
ponde a computadores com uma única CPU e uma única unidade de memória conectada
por um sistema de barramento. Apesar de ter somente uma única CPU (Central Processing
Unit) executando um único fluxo de instruções, um uniprocessador pode ainda exibir alguma
concorrência de execução. Por exemplo, arquiteturas superescalares suportam identifica-
ção dinâmica e seleção de múltiplas operações independentes que podem ser executadas
40 DCC/UFLA - Programação Paralela e Distribuída
Figura 2.15: Fluxo de instruções e fluxo de dados na 4 categorias definidas por Flynn.
simultaneamente. Instrução de prefetching e execução pipeline de instruções são outros
exemplos de concorrência tipicamente encontrados em computadores modernos do tipo
SISD.
2.3.7 SIMD
A categoria SIMD refere-se a múltiplos processadores homogêneos que executam
sobre diferentes dados. Uma única unidade de controle despacha instruções para cada
unidade de processamento. Em um computador paralelo SIMD, a mesma instrução é exe-
cutada sincronamente por todas as unidades de processamento. A execução do Exemplo
1 neste modelo, ocorreria com o despacho da instrução add para todos os processadores
seguido de sua execução concorrente por eles.
Estas arquiteturas são ideais para trabalhar com estruturas de dados regulares como
vetores e matriz, aumentando o desempenho de aplicações que envolvem sistemas de
equações, análise de imagem e reconhecimento de padrões. Como exemplo de aplicações,
pode-se citar: aerodinâmica, sismologia, meteorologia, física nuclear, química molecular e
dinâmica dos fluidos. Tais aplicações necessitam de alta precisão, operam com grandes
matrizes e/ou vetores, realizam repetitivas operações com dados representados em ponto
Plataformas para Computação Paralela 41
flutuante e geralmente consistem em problemas envolvendo modelagem 3D. Neste tipo de
modelagem, as superfícies são aproximadas por uma malha de pontos e uma série de
equações define o comportamento de cada ponto. Geralmente, as mesmas equações são
utilizadas para operar sobre o conjunto completo de pontos. Este tipo de característica pode
ser explorada pelas arquiteturas SIMD, uma vez que esta permite a operação da mesma
instrução sobre um grande conjunto de dados.
Propriedades importantes de instruções vetoriais:
• o cálculo de cada resultado é independente do cálculo dos demais, permitindo a
utilização de pipelines profundos;
• uma única instrução vetorial é responsável por uma grande fatia de trabalho;
• o atraso no acesso à memória não causa maiores problemas devido à possibilidade
de operação com dados em endereços contíguos. A organização da memória pode
tirar proveito da estrutura dos dados;
• as dependênciasde controle que ocorreriam em uma estrutura do tipo laço, não
existem, uma vez que o comportamento da instrução vetorial é pré-determinado.
Os elementos principais da arquitetura são apresentados a seguir.
• Registradores vetoriais: cada registrador vetorial é um banco de tamanho fixo con-
tendo apenas um vetor. Por exemplo, considere uma arquitetura com 8 registrado-
res de 64 elementos cada;
• Unidades funcionais vetoriais: cada unidade é totalmente pipeline e pode iniciar
uma nova operação a cada ciclo de clock. Na arquitetura exemplo, existem 5 uni-
dades funcionais, capazes de operar valores escalares.
• Unidade load-store vetorial: totalmente pipeline, é capaz de acessar 1 dado a cada
ciclo de clock, após a latência inicial.
• Registradores escalares: são os registradores de uso geral, utilizados para o cál-
culo de endereço e operações comuns.
Os primeiros computadores que pertenciam a esta categoria compreendiammáquinas
vetoriais e processadores matriciais.
• Máquinas vetoriais (Vector Processors): a mesma operação é executada em para-
lelo sobre todos os elementos de um vector (em células de memória ou em regis-
tadores) (Exemplo: CRAY).
• Processadores matriciais (Array Processors): a execução das instruções, por um
conjunto de processadores, é controlada por uma unidade de controle única, mas
cada processador tem as suas células de memória/registadores privados (Exem-
plos: ILLIAC IV, 64 processadores, 1970; Connection Machine (CM-1), 64.000 pro-
cessadores, 1985).
42 DCC/UFLA - Programação Paralela e Distribuída
Recentemente, arquiteturas SIMD incluem unidades de co-processamento tais como
as unidades MM em processadores Intel (por exemplo, Pentium com as opções SSE (Stre-
aming SIMD Extensions)) e chips DSP como o Sharc.
A Figura 2.16 apresenta uma arquitetura SIMD típica. Nesta figura, pode-se obser-
var que há uma única unidade de controle para todos os processadores; há também uma
interconexão de rede entre os processadores. Cada processador possui sua memória local.
Figura 2.16: Arquitetura SIMD
Recentemente, as unidades de processamento gráfico ou GPUs (Graphics Proces-
sing Units) possuem característica de computação SIMD, mas não são puramente SIMD.
Embora as ALUs de um dado core use paralelismo SIMD, a geração atual de GPUs pod ter
dezenas de cores, que são capazes de executar fluxos de instruções independentes.
2.3.8 MISD
A categoria MISD é para computadores com múltiplos fluxos de instrução e um único
fluxo de dados.Um computador MISD é "um pipeline de múltiplas unidades funcionais exe-
cutando independentemente operandos sobre um único fluxo de dados, passando resulta-
dos de uma unidade funcional para a seguinte".
Um vetor systolic encaixa-se nesta categoria. A palavra systole refere-se à contração
do coração. Um vetor systolic é uma rede de elementos de processamento primitivos que
bombeia (pump) dados.
Plataformas para Computação Paralela 43
Por exemplo, considere uma ordenação primitiva de elementos, onde o ordenador tra-
balha em duas fases. Na primeira fase ele entra com 3 valores de dados (a, b, c). Na
segunda fase saem os valores mínimo (min(a,b,c)), médio (med(a,b,c)) e máximo (max(a,b,c)).
Pode-se criar uma fila de prioridade em hardware relacionada a um vetor linear destes ele-
mentos ordenados. A fila de prioridade suporta duas operações: inserir uma chave e extrair
a chave com o valor mínimo. Cada operação leva dois ciclos, isto é, tempo constante.
Para inserir a chave x, o processador host insere x e -∞ à esquerda da fila de priori-
dade durante o primeiro ciclo. No segundo ciclo a fila sai -∞ no seu lado esquerdo. O host
descarta este valor.
Par extrair a chave mínima, o host insere duas cópias da chave ∞ durante o primeiro
ciclo e extrai a chave mínima durante o segundo ciclo. Para todas as operações a chave ∞ é
inserida do lado direito do vetor systolic durante o primeiro ciclo de clock. No segundo ciclo
de clock, as cópias de ∞ devem sair do lado direito do vetor systolic. Se uma das chaves
não é ∞, a fila de prioridade tem overflow.
Neste caso, todos os elemento do vetor systolic são idênticos. Entretanto, um vetor
systolic pode conter uma variedade de elementos e desempenhar diferentes funções.
Os sistemas paralelos baseados em princípios MISD foram desenvolvidos para apli-
cações particulares, tais como processamento de sinais digitais.
2.3.9 MIMD
Computadores com múltiplos fluxos de instrução e múltiplos fluxos de dados. Multi-
processadores e multicomputadores entram nesta categoria. Diferentes CPUs podem si-
multaneamente executar diferentes fluxos de instruções manipulando diferentes fluxos de
dados.
A Figura 2.17 apresenta uma arquitetura MIMD típica.
Uma variante deste modelo, chamada de SPMD (Single Program Multiple Data, opera
sobre múltiplas instâncias do mesmo programa executando sobre dados diferentes. O mo-
delo SPMD tem a mesma expressividade pois múltiplos programas podem ser inseridos
em um bloco i f − else grande com condições especificadas pelos identificadores da tarefa.
Exemplos de tais plataformas incluem Servidores Sun Ultra, PCs multiprocessados, clusters
de estações de trabalho e o IBM SP.
Os computadores SIMD requerem menos hardware do que os computadores MIMD
porque eles têm somente uma unidade de controle global. Além disso, computadores SIMD
requerem menos memória porque somente uma cópia do programa precisa ser armaze-
nada. Em computadores MIMD é necessário armazenar o programa e o sistema operacio-
nal em cada processador. Plataformas suportando o paradigma SPMD podem ser construí-
das de componentes mais baratos com esforço relativamente pequeno em um curto tempo.
Computadores SIMD requerem esforço de projeto extenso resultando em tempo de desen-
44 DCC/UFLA - Programação Paralela e Distribuída
Figura 2.17: Arquitetura MIMD
volvimento de produto mais longo. A rápida mudança de processadores seriais e a natureza
irregular de muitas aplicações faz com que as arquiteturas SIMD não sejam apropriadas.
2.4 PROGRAMAÇÃO EM COMPUTADORES PARALELOS
Atualmente, computadores paralelos estão mais disponíveis do que nunca, mas para
aproveitar bem os múltiplos processadores, programadores e/ou compiladores devem ser
capazes de identificar operações que podem ser realizadas em paralelo. Para isso, o pro-
gramador deve identificar a dependência entre dados e entre tarefas. Além disso, é preciso
saber como agrupar as tarefas de forma a explorar o máximo de paralelismo.
Após a identificação de paralelismo em um problema, o próximo passo é desenvolver
um algoritmo implementado em uma linguagem de programação.
Em 1988, McGraw e Axelrod identificaram quatro formas distintas para o desenvolvi-
mento de aplicações de software para computadores paralelos:
1. Estender um compilador existente para traduzir programas seqüenciais em progra-
mas paralelos;
2. Estender uma linguagem existente com novas operações que permitem aos usuá-
rios expressar paralelismo;
Plataformas para Computação Paralela 45
3. Adicionar uma nova camada de linguagem paralela no topo de uma linguagem
seqüencial existente;
4. Definir uma nova linguagem paralela e um sistema compilador totalmente novos.
Estender um compilador existente: Uma forma de resolver o problema da pro-
gramação paralela de computadores é o desenvolvimento de compiladores paralelos que
possam detectar e explorar o paralelismo em programas existentes escritos em uma lin-
guagem seqüencial. Dependendo da forma como o programador implementa o código, o
compilador pode ter dificuldades em identificar o paralelismo de um segmento de código.
Para não ocorrer esta situação, uma solução é permitir ao programador anotar o programa
seqüencial com diretivas de compilador para fornecerao compilador informações de forma
que ele possa paralelizar corretamente os segmentos do programa. Foram realizadas vá-
rias pesquisas nesta área e um exemplo é um compilador, desenvolvido pela empresa Pa-
rallel Software Products, que traduz o código do Fortran 77 em programas paralelos para
arquiteturas tanto de passagem de mensagens quanto de memória compartilhada.
Estender uma linguagem de programação seqüencial: Um forma mais conser-
vative para desenvolver um ambiente de programação paralela é estender uma linguagem
de programação seqüencial com funções que permitam ao programador criar e terminar
processos paralelos, sincronizá-los e permitir que eles se comuniquem. Deve também ha-
ver uma maneira de distinguir entre dados públicos (compartilhados entre os processos) e
dados privados (para que cada processo tenha uma cópia).
Estender uma linguagem de programação seqüencial é a forma mais fácil, rápida, ba-
rata e mais popular de programação paralela, porque simplesmente requer que seja desen-
volvida uma biblioteca de subrotinas. A linguagem existente e seu compilador podem ser
usados sem alteração. A facilidade relativa com que as bibliotecas podem ser desenvolvi-
das permite que elas sejam construídas rapidadmente para novos computadores paralelos.
Por exemplo, bibliotecas com o padrão MPI existem para virtualmente todo tipo de computa-
dor paralelo. Além disso, programas escritos com chamadas de funções MPI são altamente
portáveis (podem ser usados em muitos computadores com pequena ou nenhuma modifi-
cação).
Como o compilador não está envolvido na geração do código paralelo, ele não pode
mostrar onde estão os erros. Por isso, é fácil escrever um programa paralelo que seja difícil
de depurar.
Adicionar uma camada de programação paralela: Um programa paralelo pode ser
pensado como tendo duas camadas. A camada mais baixa contém o core da computação,
onde um processo manipula sua porção de dados para produzir sua porção de resultados.
Uma linguagem de programação seqüencial existente poderia ser alterada para expressar
esta porção de atividade. A camada superior controla a criação e sincronização de proces-
sos e o particionamento dos dados entre os processos. Estas ações poderiaam ser pro-
46 DCC/UFLA - Programação Paralela e Distribuída
gramadas usando uma linguagem paralela (talvez uma linguagem de programação visual).
Um compilador deveria ser responsável por traduzir este programa paralelo da segunda
camada em código apropriado para execução em um computador paralelo.
Criar uma linguagem paralela:
A criação de uma linguagem paralela envolve a habilidade de expressar operações pa-
ralelas explicitamente. A linguagem de programação Occam é um exemplo. Com uma sin-
taxe diferente das linguagens imperativas tradicionais, ela suporta tanto execução seqüen-
cial quanto paralela de processos e comunicação automática de processos e sincronização.
Outra forma de suportar paralelismo explícito é adicionar construtores paralelos a uma
linguagem existente. Fortran 90, High Performance Fortran (extensão do Fortran 90) e C*
são exemplos destas estratégias. O High Performance Fortran possui diretivas de compi-
lador que permite ao programador especificar como os dados devem ser mapeados aos
processadores. O C* é uma extensão da linguagem de programação C com a noção de um
shape, que especifica a maneira em que os dados paralelos são organizados. Um shape
é um objeto como um vetor, mas enquanto os elementos do vetor devem ser manipulados
um de cada vez, os elementos de um shape podem ser manipulados simultaneamente.
Adicionar construtores paralelos a uma linguagem de programação existente ou criar
uma nova linguagem de programação paralela requer o desenvolvimento de novos compi-
ladores. Mesmo após uma linguagem padrão ser adotada, ela tipicamente leva anos para
as empresas desenvolverem compiladores de alta qualidade para seus sistemas paralelos.
Algumas linguagens paralelas, como o C*, não foram adotadas como um padrão.
Nesta situação muitas empresas competidoras podem decidir não prover compiladores para
a linguagem em suas máquinas. Quando isto acontece, a portabilidade dos códigos é se-
veramente comprometida.
Outra barreira na adoção de novas linguagens de programação é a resistência do
usuário. Quando novos construtores paralelos são adicionados a uma linguagem de pro-
gramação, os programadores devem aprender como usar estes novos contrutores. Muitos
programadores são relutantes a fazer a transição.
2.5 ESTRUTURA DE CONTROLE DE PLATAFORMAS PARALELAS
Tarefas paralelas podem ser especificadas em vários níveis de granulosidade (ou gra-
nularidade). Em uma visão macro, cada programa em um conjunto de programas pode
ser visto como uma tarefa paralela. Em uma visão mais detalhada, instruções individuais
dentro de um programa podem ser vistas como tarefas paralelas. Entre estes dois extre-
mos existem vários modelos para especificação de estruturas de controle de programas e
o suporte arquitetural correspondente para eles.
Plataformas para Computação Paralela 47
Exemplo 1: Considere o seguinte fragmento de código que adiciona dois vetores, a e
b, e armazena o resultado no vetor c:
1 for (i=0; i<1000; i++)
2 c[i] = a[i] + b[i];
Neste exemplo, várias interações do loop são independentes. Isto significa que
c[0] = a[0]+ b[0]; c[1] = a[1] + b[1], etc., podem ser executadas independen-
temente. Conseqüentemente, se há um mecanismo para executar a mesma instrução
(neste exemplo a instrução add) em todos os processadores com dados apropriados, po-
deríamos executar este loop mais rapidamente.
As unidades de processamento em computadores paralelos podem operar sob o con-
trole centralizado de uma única unidade de controle ou trabalhar independentemente.
2.6 CONTROLE DE ESTRUTURA DE PLATAFORMAS PARALELAS
Há duas formas principais de troca de dados entre tarefas paralelas - acessando um
espaço de dados compartilhado e trocando mensagens.
2.6.1 Plataformas de passagem de mensagens
A visão lógica de uma máquina em uma plataforma de passagem de mensagens con-
siste de p nós de processamento, cada um cada um com seu espaço de endereçamento
exclusivo. Cada um dos nós de processamento podem ser processadores únicos ou um
multiprocessador com espaço de endereçamento compartilhado. Exemplos de tal visão
são os cluster de estações de trabalho (workstations e os multicomputadores de espaço
de endereçamento não-compartilhado. Em tais plataformas, interações entre processos
executando em diferentes nós devem ser realizadas usando mensagens, por isso surgiu o
termo passagem de mensagens. Esta troca de mensagens é usada para transferir dados,
trabalho e para sincronizar ações entre os processos. De uma forma geral, os paradigmas
de passagem de mensagens suportam a execução entre diferentes programas em cada p
nós.
As interações são realizadas enviando e recebendo mensagens. Assim, as operações
básicas neste paradigma de programação são enviar (send) e receber receive (as chama-
das correspondentes podem diferir entre as APIs, mas as semânticas são idênticas). Além
disso, já que nas operações de envio e recebimento os endereços destino devem especifi-
car os endereços destinos, deve haver um mecanismo para atribuir um identificador único
ou ID a cada um dos múltiplos processos que estão executando um programa paralelo. Este
identificador é utilizado em programas paralelos. Para obtê-lo existem funções específicas,
de acordo com a API utilizada. Existe também uma função para descobrir o número de pro-
48 DCC/UFLA - Programação Paralela e Distribuída
cessos que participando da computação. Com estas 4 funções básicas (send, receive, para
obter o identificador de processo e o número de processos) é possível escreverqualquer
programa de passagem de mensagens. Diferentes APIs de passagem de mensagens, tais
como MPI e PVM, suportam estas operações básicas e uma variedade de funcionalidades
de mais alto nível sob diferentes nomes de funções. Cluster de estações de trabalho é um
exemplo de uma plataforma paralela que suporta o paradigma de passagem de mensagens.
É fácil emular um arquitetura de passagem de mensagens contendo p nós em um
computador de espaço de endereçamento compartilhado com um número idêntico de nós.
Assumindo nós uniprocessados isto pode ser feito particionando o espaço de endereça-
mento compartilhado em p partes disjuntas e atribuindo uma partição exclusiva para cada
processador. Um processador pode então "enviar"ou "receber"mensagens escrevendo ou
lendo de outra partição do processador usando primitivas de sincronização apropriadas
para informar seu padrão de comunicação quando ele tiver terminado de ler ou escrever o
dado. Entretanto, emular uma arquitetura de espaço de endereçamento compartilhado em
um computador de passagem de mensagens é custoso, já que acessar memória de outro
nó requer enviar e receber mensagens.
Plataformas para Computação Paralela 49
2.7 MODELOS PARALELOS
A modelagem na computação paralela é desafiadora devido à presença de muitos pro-
cessadores interconectados. Os modelos algorítmicos podem ser usados como frameworks
para descrever e analisar algoritmos paralelos. Porém, nenhum algoritmo paralelo provou
ser aceitável para a maioria dos pesquisadores em processamento paralelo. As seções
seguintes apresentam dois modelos paralelos: DAG e PRAM.
2.7.1 Grafos acíclicos orientados (DAGs)
Muitas computações podem naturalmente ser representadas por grafos acíclicos ori-
entados (directed acyclic graphs - DAGs). Cada entrada é representada por um nó que não
tem arcos incidentes. Cada operação é representada por um nó que tem arcos incidentes
de nós que representam os operandos. O grau máximo devido às arestas incidentes de um
nó interno é no máximo 2. Um nó cujo grau devido às arestas com origem no nó é igual a
zero, representa uma saída. Será assumido o critério de custo unitário, onde cada um dos
nós representa uma operação que gasta uma unidade de tempo.
Um DAG com n nós de entrada representa uma computação que não possui instruções
de desvio e que tem uma entrada de tamanho n. Entretanto, um algoritmo é representado
por uma família de DAGs {Gn}, onde Gn corresponde ao algoritmo com entrada de tamanho
n.
Este modelo é razoável para analisar computações numéricas, já que instruções de
desvio são tipicamente usadas para executar uma seqüência de operações em um certo
número de vezes, dependente do tamanho da entrada n. Neste caso, pode-se desenrolar
uma instrução de desvio duplicando a seqüência de operações a ser repetida o número
apropriado de vezes.
Um DAG especifica as operações realizadas pelo algoritmo e implica em restrições de
precedência na ordem em que estas operações devem ser realizadas. É completamente
independente da arquitetura.
Exemplo 2: Considere o problema de computar a soma S de n = 2k elementos de um
vetor A. Dois algoritmos possíveis são representados por seus DAGs na Figura 2.18 para
n = 8. O algoritmo seqüencial computa a soma parcial consecutivamente, começando com
A(1)+A(2), seguido por (A(1)+A(2))+A(3) e assim por diante. O outro algoritmo funciona
em uma árvore binária completa que começa pela computação da soma A(1)+A(2),A(3)+
A(4), ...,A(n− 1)+A(n) no nível mais baixo e repete o processo no próximo nível com n/2
elementos e assim por diante até a soma ser computada na raiz.
No Exemplo 2, para um número n de elementos, o melhor escalonamento para o
algoritmo representado na Figura 2.18 (a) gasta tempo O(n), considerando que há proces-
50 DCC/UFLA - Programação Paralela e Distribuída
sadores disponíveis. O tempo gasto na Figura 2.18 (b) é O(logn) com n/2 processadores.
Todos os nós no mesmo nível têm o mesmo tempo de execução.
Figura 2.18: Os DAGs de 2 possíveis algoritmos para o Exemplo 2. (a) Um DAG para computação
da soma de 8 elementos. (b) Um DAG alternativo para computação da soma de 8 elementos de um
esquema de árvore binária balanceada.
Exemplo 3: (Multiplicação de matrizes)
Sejam A e B duas matrizes nxn. Considere o algoritmo padrão para computar o produto
C = AB. Cada C(i, j) é computado usando a expressão C(i, j) = ∑nl=1A(i, l)B(l, j). Um DAG
para computar C(i, j) para n = 4 é mostrado na Figura 2.19. Dados n3 processadores, as
operações podem ser escalonadas nível por nível, usando n processadores para computar
cada entrada deC; então, o DAG pode ser escalonando para computarC em tempo O(logn).
2.7.2 O modelo PRAM
O tempo de execução de um algoritmo seqüencial é estimado pelo número de opera-
ções básicas requeridas pelo algoritmo em função do tamanho da entrada. A definição de
operação básica depende do problema tratado e o modelo de computação utilizado. Con-
siderando uma unidade de tempo para as operações de leitura e escrita em memória e as
operações aritméticas e lógicas (tais como adição, subtração, comparação ou multiplicação
de números e a computação de OR ou AND lógico bit-a-bit de duas palavras). Quando o
custo de uma operação não depende do tamanho da palavra é porque está sendo usado o
critério de custo uniforme. Um modelo computacional para este propósito é o Random Ac-
cess Machine (RAM), que assume a presença de uma unidade de processamento central
Plataformas para Computação Paralela 51
Figura 2.19: DAG para computação de uma entrada C(i, j) do produto de matrizes C = AB para o
caso de matrizes 4x4
com uma memória de acesso aleatório junto dela e alguma forma de tratar a entrada e a
saída das operações.
O modelo RAM tem sido usado para prever o desempenho de algoritmos seqüenciais.
A modelagem da computação paralela é consideravelmente mais desafiante dada a nova
dimensão introduzida pela presença de muitos processadores interconectados.
Um modelo algorítmico para descrever e analisar algoritmos paralelos deve ser sim-
ples o suficiente para permitir a descrição dos algoritmos paralelos facilmente e para anali-
sar matematicamente medidas de desempenho tais como speedup, comunicação e utiliza-
ção de memória. Além disso, o modelo deve ser independente de hardware e os algoritmos
paralelos desenvolvidos para o modelo devem ser facilmente implementáveis em compu-
tadores paralelos. A análise realizada deve capturar de forma significativa o desempenho
real destes algoritmos em computadores paralelos.
O modelo PRAM é uma versão síncrona do modelo de memória compartilhada. No
modelo síncrono, todos os processadores operam sincronamente sob o controle de um re-
lógio comum (relógio global). No modelo assíncrono, cada processador opera sob relógios
diferentes. E neste caso, é responsabilidade do programador estabelecer os pontos de sin-
cronização apropriados. Se o processador necessitar acessar dados é responsabilidade
do programador garantir que os valores corretos sejam obtidos, já que o valor de uma va-
riável compartilha é determinado dinamicamente durante a execução dos programas em
diferentes processadores.
No modelo PRAM, os algoritmos desenvolvidos são do tipo SIMD. Isto é, todos os
processadores executam o mesmo programa tal que durante cada unidade de tempo todos
os processadores ativos estão executando a mesma instrução, mas com diferentes dados.
Entretanto, pode-se carregar diferentes programas em memórias locais dos processadores,
52 DCC/UFLA - Programação Paralela e Distribuída
de forma que os processadores possam operar sincronamente; então, diferentes tipos de
instruções podem ser executadas durante a unidade de tempo alocada para um passo.
No modelo PRAM, os seguintes pontos devem serdestacados:
• Há técnicas bem definidas e métodos para tratar muitas classes diferentes de pro-
blemas computacionais no modelo PRAM.
• O modelo PRAM remove detalhes algorítmicos de sincronização e comunicação, e
permite ao projetista do algoritmo focar em propriedades estruturais do problema.
• O modelo PRAM captura diversos parâmetros importantes de computações parale-
las. Um algoritmo PRAM inclui um entendimento explícito de operações para serem
realizadas em cada unidade de tempo e explícita alocação de processadores para
jobs em cada unidade de tempo.
• O paradigma de projeto PRAM tem se tornado robusto. Muitos dos algoritmos da
área de redes podem ser diretamente derivados de algoritmos PRAM.
• É possível incorporar características tais como sincronização e comunicação no
modelo de memória compartilhada. Então os algoritmos PRAM podem ser analisa-
dos dentro deste framework mais geral.
Desde ponto em diante, considere o modelo PRAM como sendo um modelo de memó-
ria compartilhada síncrono (arquitetura como vista na Figura 2.6(a)). Assim, ele consiste de
p processadores e uma memória global de tamanho ilimitado que é uniformemente aces-
sível a todos os processadores. Todos os processadores acessam o mesmo espaço de
endereçamento global, mas cada processador tem sua memória local. Os processadores
compartilham um relógio comum mas podem executar diferentes instruções em cada ci-
clo. Como o modelo PRAM permite o acesso concorrente a várias locações de memória,
dependendo de como os acessos simultâneos à memória são tratados, PRAM pode ser
dividido em 4 subclasses.
1. EREW (Exclusive-Read, Exclusive-Write): nesta classe, o acesso à locação de me-
mória é exclusivo. Conflitos de leitura ou escrita não são permitidos. Este modelo
apresenta concorrência mínima em acesso à memória.
2. CREW (Concurrent-Read Exclusive-Write): nesta classe, acessos de leituras múlti-
plas à locação de memória são permitidos. Entretanto, múltiplos acessos de escrita
na mesma locação de memória são seqüencializados (conflitos de escrita não são
permitidos).
3. ERCW (Exclusive-Read Concurrent-Write): múltiplos acessos de escrita são per-
mitidos à locação de memória, mas múltiplos acessos de leitura são sequenciali-
zados.
4. CRCW (Concurrent-Read Concurrent-Write): permite múltiplos acessos de leitura
e escrita à locação de memória comum.
Plataformas para Computação Paralela 53
Permitir acesso de leitura concorrente não cria qualquer discrepância de semântica
no programa. Entretanto, acesso de escrita concorrente a uma locação de memória re-
quer cuidado. Existem diferentes protocolos para resolver escritas concorrentes no mesmo
endereço global. Os protocolos mais freqüentemente usados são:
• Comum: processadores escrevendo concorrentemente no mesmo endereço de
memória global devem escrever o mesmo valor.
• Arbitrária: se múltiplos processadores concorrentemente escrevem no mesmo en-
dereço global, somente um dos processadores que está competindo é arbitraria-
mente escolhido como vencedor e seu valor é escrito.
• Prioritária: todos os processadores são organizados em uma lista de prioridade
pré-definida e o processador com a maior prioridade realiza a escrita e os demais
falham.
• Sum: a soma de todas as quantidades é escrita (o modelo de resolução de conflito
de escrita baseado em soma pode ser estendido a qualquer operador associativo
definido sobre as quantidades sendo escritas).
Antes de apresentar os algoritmos, considere a linguagem algoritmica com os cons-
trutores: leitura_global(X,Y) e escrita_global(U,V).
O efeito da instrução leitura_global(X,Y) é mover o bloco de dados X armazenado na
memória compartilhada para a variável localY . Similarmente, o efeito de escrita_global(U,V)
é escrever o dado local U na variável compartilhada V .
Exemplo 4: Dado um vetor A composto por n = 2k números e um PRAM com n pro-
cessadores {P1,P2, ...,Pn}, deseja-se computar a soma S = A(1) + A(2) + ...+ A(n). Cada
processador executa o mesmo algoritmo, dado aqui para o processador Pi.
A Figura 2.20 ilustra o algoritmo para o caso quando n = 8. Durante os passos 1 e 2,
uma cópia B de A é criada e armazenada na memória compartilhada. O esquema de com-
putação (passo 3) é baseado na árvore balanceada binária cujas folhas correspondem aos
elementos de A. O processador responsável por desempenhar uma operação é indicado
abaixo no nó representante da operação. Note que P1, que é responsável por atualizar o va-
lor de B(1) e por escrever a soma em S, está sempre ativo durante a execução do algoritmo,
e P5, P6, P7 e P8 estão ativos somente durante os passos 1 e 2.
Este exemplo considera que os vetores A e B são armazenados em memória global e
podem ser acessados por qualquer processador. Além disso, em cada unidade de tempo, a
cada processador é permitido executar uma instrução ou ficar ocioso. Note que a condição
do comando i f no loop definido no passo 3 é satisfeito por somente alguns processadores.
Os demais processadores ficam ociosos durante aquele tempo.
54 DCC/UFLA - Programação Paralela e Distribuída
Algoritmo 1: (Soma no Modelo PRAM)
Entrada: Um vetor A de ordem n = 2k armazenado na memória compartilhada
de um PRAM com n processadores. As variáveis locais inicializadas são n e o
processador número i.
Saída: A soma das entradas de A armazenadas na locação compartilhada S.
O vetor A possui seu valor inicial.
begin
1. leitura_global(A(i),a)
2. escrita_global(a,B(i))
3. for h = 1 to log n do
if( i ≤ n/2h) then
begin
leitura_global(B(2i - 1),x)
leitura_global(B(2i),y)
Set z := x+y
escrita_global(z,B(i))
end
4. if i = 1 then escrita_global(z,S)
end
2.8 EXERCÍCIOS
1. Por que o número de processadores em um multiprocessador centralizado é limi-
tado a poucas dezenas?
2. Quais são as principais diferenças entre computadores de passagem de mensa-
gens e espaço de endereçamento compartilhado? Descreva as vantagens e des-
vantagens de cada um deles.
3. Por que é difícil construir um computador de memória compartilhada verdadeira?
Qual é o número mínimo de switches para conectar p processadores a uma me-
mória compartilhada com b palavras ( onde cada palavra pode ser acessada inde-
pendentemente)?
Plataformas para Computação Paralela 55
Figura 2.20: Soma no modelo PRAM com 8 elementos