Arquitetura de Computadores Paralelos

Prévia do material em texto

Capítulo 8 − Arquitetura de Computadores Paralelos
− Necessidade de máquinas com alta capacidade de computação 
− Aumento do clock => alta dissipação de calor
− Velocidade limitada dos circuitos => velocidade da luz
− Redução do tamanho dos transistores => efeitos quânticos
− Paralelismo:
− Nível de instrução => pipeline, estrutura superescalar => fator de 10
− Nível de CPUs => fator acima de 100
8.1 Características de Computadores Paralelos
− Natureza, tamanho e quantidade de elementos de processamento ?
− Simples ULA ou CPU completa
− Pequena porção de um chip ou grande quantidade de circuitos por
elemento de processamento
− Quanto menor o elemento de processamento, maior a quantidade de
elementos que podem ser colocados em paralelo.
− Natureza, tamanho e quantidade de módulos de memória ?
− Memória geralmente dividida em módulos, independentes, em paralelo.
 − KB a MB
− Integradas próximas às CPUs ou em uma placa distinta
− Memória geralmente mais lenta do que a CPU => até quatro níveis de
cache
− Como os elementos e processamento e memória são conectados ?
− Principal diferença dos computadores paralelos
− Dois modelos principais:
− Estático: Os elementos são conectados de maneira fixa: estrela,
anel, malha
− Dinâmico: elementos conectados por um chaveador de rede que
faz o roteamento dinâmico das mensagens entre os componentes.
− Como ocorre a execução em paralelo ?
− Computadores paralelos projetados para executar independentemente
vários programas, simultaneamente => programas não conectados e sem
comunicação entre eles => vários usuários.
− Computadores paralelos projetados para executar um único programa
composto por vários processos => único usuário.
− Computadores com pipeline muito profunda ou com várias ULAs
operando com a mesma instrução ao mesmo tempo => processamento vetorial.
147
− Granulosidade: Refere−se aos algoritmos e software => analogia direta com o
hardware
− Paralelismo de grãos grandes: execução de grandes partes de software
com pouca ou nenhuma conexão entre elas.
− Paralelismo de grãos pequenos: extremo oposto, tal como no
processamento vetorial.
− Sistemas com poucas CPUs independentes e grandes que possuem conexões
de baixa velocidade entre as CPUs => sistemas pouco acoplado.
− Sistemas cujos componentes são pequenos, próximos um dos outros e com
interação constante, com redes de comunicação de alta velocidade => sistemas
altamente acoplados.
8.1.1 Modelos de Comunicação
Multiprocessadores
− Sistema de memória compartilhada
− As CPUs compartilham uma memória comum
− Todos os processos executados em um multiprocessador podem compartilhar
um único espaço de memória virtual mapeado na memória comum.
− Troca de dados entre processos => leitura e escrita na memória comum.
Multicomputadores
148
− Sistema de memória distribuída
− Cada CPU possui sua própria memória, não acessível às outras CPUs.
− Geralmente pouco acoplados.
− Possuem um único espaço físico de memória para cada CPU.
− Troca de informação entre processos => envio de mensagens usando uma
rede de conexão.
− Software mais complicado do que em um multiprocessador
− Necessária a divisão dos dados e envio para as unidades de processamento
− Multicomputadores grandes são muito mais fáceis e baratos de serem
construídos.
149
− Multiprocessadores: difíceis de serem construídos mas fáceis de serem
programados
− Multicomputadores: fáceis de serem construídos mas difíceis de serem
programados
=> Sistemas híbridos: Projetos escalonáveis => adição de CPUs com a
manutenção da performance.
− Memória compartilhada implementada em hardware: multiprocessador
− Memória compartilhada implementada pelo sistema operacional: busca de
páginas em memória remota e não do disco
− Memória compartilhada implementada pelo compilador e sistema de tempo
real: abstração de memória compartilhada
8.1.2 Redes de Conexão
150
− Redes de conexão podem conter até cinco componentes:
− CPUs
− Módulos de memória
− Interfaces
− Links
− Switches
− Interfaces: elementos da que "pegam" as mensagens de e para as CPUs e
memória.
− Geralmente um CI ou placa conectada a cada barramento local de cada
CPU.
− Links: canais físicos nos quais os bits são movimentados
− Podem ser simplex, half duplex ou full duplex.
− Switches: dispositivos com várias portas de entrada e várias portas de saída:
utilizado para fazer o roteamento de pacotes.
Topologia
− Descreve como os links e switches estão conectados
− Fanout: número de links conectados a um dado nó .
− Diâmetro: Maior distância entre dois nós dada pelo número de links que
devem ser utilizados para a conexão.
− Largura de faixa de duas seções: menor largura de faixa dos links removidos
para se formar duas seções com mesmo número de nós.
− Dimensão: determinada pelo número de escolhas que existem para sair de
uma fonte e chegar a um dado destino => dimensão zero: apenas um caminho.
151
152
Chaveamento
− Aceita pacotes de qualquer porta de entrada, enviando−o para a porta de saída
adequada.
− Chaveamento de circuito: Antes do envio do pacote todo o caminho da fonte
para o destino é reservado.
− Chaveamento de pacotes por armazenamento e envio: A fonte envia todo o
pacote para a switch, onde ele é armazenado. Depois de armazenado a switch o
envia para outra switch e assim sucessivamente.
− Necessidade de buffers:
− Buffer de entrada: Associados com a porta de entrada. Implementado
como FIFO. Pode gerar um bloqueio de cabeça de linha (head−of−line
blocking)
− Buffer de saída: Associados com a porta de saída.
− Buffer comum: única fila de buffers alocados dinamicamente para cada
porta.
153
Algoritmos de Roteamento
− Redes com dimensão um ou mais: escolha do caminho a ser percorrido.
− Deadlock: vários pacotes transitando no mesmo tempo solicitam recursos de
tal forma que nenhum deles é atendido, permanecendo bloqueados.
− Roteamento pela fonte: a fonte determina toda a rota a ser percorrida.
− Roteamento distribuído: cada switch determina para qual porta o pacote de
chegada deve ir.
− Estático: mesma escolha para um dado destino
− Adaptativo
8.1.3 Performance
Medições de Hardware
− Velocidade da CPU e I/O: iguais a um único processador
− Performance da rede de conexão:
− Latência: tempo de uma CPU enviar um pacote e receber a resposta
− Largura de faixa: 
− Largura de faixa de duas seções
− Largura de faixa agregada: soma de todas as capacidades de
todos os links
− Largura de faixa média de saída de cada CPU
Medições de Software
− Velocidade: Quanto mais rápido um programa é executado em um sistema
com n−processadores do que em um com um único processador.
154
Alcançando Grandes Performances
− Adição de mais CPUs evitando gargalos
− Sistema escalonável: possibilidade de adicionar CPUs aumentando o poder de
computação.
− Manutenção da largura de faixa média por CPU
− Manutenção do tempo de latência
− Técnicas para "esconder" o tempo de latência:
− Cópia de blocos de dados
− Prefetching
− Multithreading
− Instruções não bloqueantes
8.1.4 Software
− Arquitetura paralela => software paralelo
− Inclusão de bibliotecas numéricas especiais => apenas algumas funções
utilizarão os recursos da computação paralela
− Inclusão de bibliotecas de comunicação e controle => responsabilidade do
programador em criar e gerenciar o paralelismo dos processos.
− Inclusão de construções especiais em linguagens de programação já existentes
− Criação de uma nova linguagem especial para processamento paralelo.
Modelos de Controle
− Uma linha de controle: Existe um único programa e um único PC, mas vários
conjuntos de dados
− Múltiplas linhas de controle: Existem vários programas, cada um com o seu
próprio PC e seu próprio conjunto de dados.
155
Granulosidade do Paralelismo
− Nível mais baixo: Instruções de máquina em paralelo − Superescalar:
Programador sem consciência do paralelismo
− Paralelismo a nível de bloco: Programador controla quais comandos devem
ser executados seqüencialmente e quais devem ser executados em paralelo.
− Threads ou Processos Leves: Executadosdentro do espaço de endereçamento
do processo principal. Cada thread possui seu próprio PC, registradores e pilha,
mas compartilham o resto do espaço de endereçamento.
− Múltiplos processos: Vários processos para resolver um mesmo problema.
Paradigmas Computacionais
− SPMD: Single Program Multiple Data: Uma linha de controle para vários
conjuntos de dados
− Pipeline: Um processo utiliza o dado do processo antecessor.
− Computação por fases: Vários processos em paralelo, antes de passar para a
próxima fase o processo espera até que todos os demais tenham terminado
− Dividir e Conquistar: Um processo inicia o trabalho e cria outros processos a
medida que ele puder passar algum trabalho para eles
−Replicated Worker ou Task farm: Existência de uma fila de trabalhos a serem
executados. Cada processo retira um trabalho da fila e o executa.
Métodos de Comunicação
− Comunicação por variáveis compartilhadas: todos os processos possuem
acesso a uma determinada área de memória lógica
− Comunicação por mensagens: utilização de primitivas para o envio e
recebimento de mensagens.
− Mensagem ponto−a−ponto: um emissor e um receptor
− Broadcasting: um emissor e vários receptores (todos os
processos)
− Multicasting: um emissor e vários receptores (alguns processos)
156
Primitivas de Sincronização
− Exclusão mútua: Necessária para impedir que algum processo tente ler um
dado enquanto outro processo escreve o dado.
− Semáforos, travas, mutexes, seções críticas
− Barreira: Capacidade do processo se bloquear até que uma determinada fase
do trabalho esteja completa.
8.1.5 Taxinomia de Computadores Paralelos
− Categorização de arquiteturas paralelas: Proposta de Flynn
Multiprocessadores
− UMA: Uniform Memory Acess: Cada CPU possui o mesmo tempo de acesso
a cada módulo de memória.
− NUMA: NonUniform Memory Acess: O tempo de acesso de cada CPU varia
em função do módulo de memória acessado.
− COMA: Cache Only Memory Acess: Memória principal de cada CPU
utilizada como cache.
Multicomputadores (ou NORMA − NO Remote Memory Acess)
157
− MPP: Massively Parallel Processors: Várias CPUs muito acopladas por uma
rede proprietária de alta velocidade.
− COW − Cluster of Workstations ou NOW − Network of Workstations: Vários
PCs ou workstations conectados em rede padrão, comercial.
8.2.1 Computadores SIMD
− Uma única unidade de controle que executa a mesma instrução em múltiplos
dados.
8.2.1 Processador matricial
− Uma única unidade de controle fornece os sinais que comandam vários
elementos de processamento.
− Características:
− Tipo do elemento de processamento
− Maneira como os elementos de processamento são conectados
− Qual a autonomia dos elementos de processamento
8.2.2 Processadores Vetoriais
158
− Funções:
 − ULA vetorial:
− Combinação de processamento vetorial com pipeline: Ausência de saltos
quando se opera com vetores => não existem "buracos" na pipeline.
159