Please enable JavaScript.
Coggle requires JavaScript to display documents.
Modelos de computação paralela - Coggle Diagram
Modelos de computação paralela
PRAM
Modelo teórico inviável
Conexão entre processadores e memória muito exigiria uma área enorme
Tempo de acesso constante a memória não é realista
Características
Estrutura de comunicação é importante
Rede vista como um grafo G=(N, A)
Nó i E N é um processador
Aresta(i,j) E A representa uma comunicçaõ entre os processadores
i
e
j
Operações: Envia(X, Pi), Recebe(X, Pi)
Sem memória compartilhada global
Problemas
Diàmetro da comunicação
O diâmetro é a maior distância entre um par de nós
Se o diâmetro de um modelo é d, o limite inferior
para qualquer cálculo nesse modelo é Ω(d)
A comunicação entre os dois nós mais distantes leva
Ω(d) unidades de tempo
Largura da bissecção
A largura da bissecção de um modelo de rede é o número mínimo de links a serem removidos para decompor o grafo em duas partes iguais
Maior a largura, mais rápido a resolução de problemas
Escalabilidade
Facilidade para adicionar novos processadores
Se o número de links for grande para cada processador, é difícil adicionar novos processadores, pois muitos links novos precisam ser adicionados
Rede Mesh
Cada processador se conecta a 4 vizinhos
Para conectar duas redes é necessário apenas links extras nas bordas
Altamente escalável
:warning: Largura e bissecção em O(sqrt(n))
Hipercubo
Cada processador está diretamente conectado a outros
processadores
O caminho mais curto entre um par de processadores é no
máximo d
Rede
Cada nó de um hipercubo d-dimensional é numerado
usando d bits
Dois nós são conectados por um link direto se seus
números diferirem apenas em um bit
Um hipercubo d-dimensional tem n = 2^d processadores.
:warning: A largura da bissecção de um hipercubo d-dimensional é 2d-1
:warning: O diâmetro de um hipercubo d-dimensional é d
Redes de interconexão
Estáticas
os nós de processamento são conectados
por links de comunicação ponto a ponto
Ex: Processador a processador através de nós, mesh, hipercubo
Dinamicas
os links de comunicação são conectados dinamicamente pelos comutadores (switches) para estabelecer caminhos entre nós de processamento e bancos de memória (redes indiretas)
Redes Múltiplos estágios
Omega, + Butterfly + Perfect shuffle
Necessita de comutadores
Características Omega:
D = d-1
Largura de bissecção = n/2
Tamanho comutador = 2
Número de comutador= d(n/2)
BSP
O modelo BSP abstrai a topologia da rede usando dois parâmetros (L, g) relacionados à latência e largura de banda da rede
Os valores de L e g para uma máquina dependente da topologia de sua rede. O parâmetro L é delimitado abaixo pelo diâmetro da rede, enquanto o g é delimitado abaixo pela razão de p com uma largura de banda da bissecção
Merece um Mapa a parte hehee :stuck_out_tongue: