Arquitetura de Sistemas Distribuídos Esquemas Inter Processadores Material Teórico

Prévia do material em texto

1 
 
Barramento compartilhado 
 
A organização de rede de barramento compartilhado usa um único caminho de 
comunicação entre todos os processadores e módulos de memória: a rota pela 
qual as mensagens transitam. 
 
As interfaces de barramento dos componentes manipulam operações de 
transferência. O barramento é passivo, e os componentes arbitram entre eles 
mesmos para utilizar o barramento. 
 
Um problema dos barramentos compartilhados (contenção) surge quando 
vários componentes querem usar o barramento ao mesmo tempo. Para reduzir 
a contenção e o tráfego no barramento, cada processador mantém seu próprio 
cache local. 
 
Quando o sistema puder atender a uma requisição de memória por meio do 
cache de um processador, este não precisará se comunicar com um módulo de 
memória através do barramento. 
 
Outra opção é montar uma arquitetura de barramentos múltiplos 
compartilhados que reduz a contenção, fornecendo vários barramentos que 
atendem às requisições de comunicação. Contudo, esse esquema requer uma 
lógica complexa de arbitragem de barramento e enlaces adicionais, o que 
aumenta o custo do sistema. 
 
O barramento compartilhado é um esquema simples e barato para conectar 
um número pequeno de processadores. Novos componentes podem ser 
adicionados ao sistema, ligando-os ao barramento, e o software manipula a 
detecção e a identificação dos componentes do barramento. 
 
Entretanto, devido à contenção pelo único caminho de comunicação, as 
organizações de barramento compartilhado não podem ser escaladas para 
mais do que um pequeno número de processadores. 
 
 
2 
 
 
Um barramento compartilhado com diversos processadores é rápido e barato, 
mas não particularmente tolerante à falha – se o barramento compartilhado 
falhar, os componentes não poderão se comunicar. 
 
Como exemplo de sistema que usa a arquitetura de barramento 
compartilhado, podemos citar a maioria dos sistemas multiprocessadores com 
um pequeno número de processadores, como os sistemas de dois 
processadores Pentium, da Intel. 
 
Veja, a seguir, uma figura que representa o esquema de barramento 
compartilhado: 
 
 
 
 
 
 
 
Matriz de comutação de barras cruzadas 
 
Uma matriz de comutação de barras cruzadas (crossbar switch) fornece um 
caminho separado de cada processador para cada módulo de memória. Por 
exemplo, se houver N processadores e M módulos de memória, haverá um 
total de N x M comutadores, que conectam cada processador a cada módulo 
de memória. 
 
Uma matriz de comutação de barras cruzadas pode suportar transmissões de 
dados para todos os nós ao mesmo tempo, mas cada nó pode aceitar, no 
máximo, uma mensagem por vez. Um comutador usa um algoritmo de 
arbitragem do tipo atenda o processador requisitante que tiver sido 
atendido menos recentemente neste comutador para resolver requisições 
múltiplas. 
Barramento 
Memória Memória Memória 
CPU CPU CPU 
 
 
3 
 
 
O projeto de comutação de barras cruzadas fornece alto desempenho. Todos 
os nós estão ligados aos outros nós e à transmissão através de nós de 
comutação, o que representa um custo de desempenho trivial. Em função 
disso, o diâmetro da rede mede, essencialmente, um. 
 
Cada processador está conectado a cada módulo de memória. Portanto, para 
dividir uma matriz de comutação de barras cruzadas em duas metades iguais, 
é preciso que metade dos enlaces seja cortada entre processadores e módulos 
de memória. 
 
O número de enlaces da matriz é o produto de N por M. Portanto, a largura de 
bisseção é (N x M)/2, o que resulta em forte tolerância à falha. 
 
Há muitos caminhos que uma comunicação pode tomar para chegar a seu 
destino. 
 
Uma desvantagem das matrizes de comutação de barras cruzadas é seu custo, 
que aumenta proporcionalmente ao produto N x M, o que torna inviáveis os 
sistemas de grande escala. Por essa razão, essas matrizes normalmente são 
empregadas em sistemas multiprocessadores menores (por exemplo, com 16 
processadores). 
 
Contudo, à medida que o custo do hardware diminui, tais matrizes vão sendo 
usadas mais frequentemente em sistemas maiores. 
 
Como exemplo de sistemas que usam comutadores de barras cruzadas para 
compartilhar memória, podemos citar o UltraSPARC-III da Sun e o Primepower 
2500 da Fujitsu. 
 
Veja, a seguir, figuras que representam uma matriz de comutação de barras 
cruzadas (crossbar switch): 
 
 
4 
 
 
 
 
Fonte: 
http://people.seas.harvard.edu/~jones/cscie129/nu_lectures/lecture11/switching/xbar/xbar
.html. 
 
 
 
 
 
 
 
5 
 
 
 
Legenda: 
(a) Chave de interseção 8 x 8 
(b) Interseção aberta 
(c) Interseção fechada 
 
Fonte: TANENBAUM, 2010. 
 
 
Redes em malha 2–D 
 
Em um esquema de interconexão por rede em malha 2-D, cada nó consiste em 
um ou mais processadores e um módulo de memória. No caso mais simples, os 
nós de uma rede em malha são organizados em um retângulo de N filas e M 
 
 
6 
 
colunas, e cada nó é conectado aos nós diretamente ao norte, sul, leste e 
oeste dele. Esse arranjo é denominado rede em malha 2-D de 4 conexões. 
 
Esse projeto mantém pequeno o grau de cada nó, independentemente do 
número de processadores de um sistema – os nós dos vértices têm grau dois, 
os nós das arestas têm grau três e os nós internos, grau quatro. Onde N = 4 e 
M = 5, a rede em malha 2-D pode ser dividida em duas metades iguais, 
cortando os cinco enlaces entre a segunda e a terceira linha de nós. 
 
Embora não seja tão tolerante à falha como uma matriz de comutação de 
barras cruzadas, uma rede em malha 2-D é mais tolerante do que outros 
projetos simples, como um barramento compartilhado. 
 
Como o grau máximo de um nó é quatro, o diâmetro de uma rede em malha 2-
D será demasiadamente substancial para sistemas de grande escala. 
Entretanto, redes em malha têm sido usadas em grandes sistemas nos quais a 
comunicação ocorre, principalmente, entre nós vizinhos. 
 
Como exemplo de sistema que usa uma rede em malha 2-D, podemos citar o 
multiprocessador Intel Paragon. 
 
Hipercubo 
 
Um hipercubo n-dimensional consiste em 2N nós, cada um ligado a N nós 
vizinhos. Portanto, um hipercubo bidimensional é uma rede em malha 2 x 2, e 
um hipercubo tridimensional é, conceitualmente, um cubo. 
 
Um hipercubo tridimensional é, na verdade, um par de cubos bidimensionais, 
no qual os nós correspondentes de cada cubo bidimensional estão conectados. 
Similarmente, um hipercubo tetradimensional é, na realidade, um par de 
hipercubos tridimensionais, no qual os nós correspondentes de cada hipercubo 
tridimensional estão conectados. 
 
 
 
7 
 
O desempenho de um hipercubo escala melhor do que o de uma rede em 
malha 2-D, pois cada nó está conectado a outros nós por n enlaces, o que 
reduz o diâmetro relativo da rede a uma rede em malha 2-D. 
Por exemplo, considere um multiprocessador de 16 nós implementado como 
uma rede em malha 4 x 4 ou como um hipercubo tetradimensional. O 
diâmetro de uma rede em malha 4 x 4 é 6, enquanto que o de um cubo 
tetradimensional é 4. Em alguns hipercubos, os projetistas adicionam enlaces 
de comunicação entre nós não vizinhos para reduzir ainda mais o diâmetro da 
rede. 
A tolerância à falha do hipercubo também se compara favoravelmente com a 
de outros projetos. Entretanto, o maior número de enlaces por nó aumenta o 
custo de um hipercubo em relação ao de uma rede em malha. 
O esquema de interconexão por hipercubo é eficiente para conectar um 
número modesto de processadores e é mais econômicodo que uma matriz de 
comutação de barras cruzadas. 
Como exemplo de sistema que usa o hipercubo, podemos citar o sistema 
nCUBE, usado para sistemas de mídia de tempo real e de propaganda digital. 
Esse sistema emprega hipercubos de até 13 dimensões (8.192 nós). 
 
Veja, a seguir, uma figura que representa um hipercubo: 
 
 
 
Fonte: http://www.inf.ufrgs.br/gppd/disc/cmp134/trabs/T1/991/Origin/origin.html. 
 
 
 
 
 
 
 
8 
 
Redes multiestágios 
 
Um esquema alternativo de interconexão de processadores é uma rede 
multiestágio. Como acontece no projeto de matriz de comutação de barras 
cruzadas, alguns nós são comutadores, e não nós processadores com memória 
local. Os nós de comutação são menores, mais simples e podem ser mais bem 
compactados, o que melhora seu desempenho. 
 
Há muitos esquemas para construir uma rede multiestágio. Uma rede 
multiestágio popular é denominada rede de linha básica, na qual cada nó da 
esquerda é igual ao nó da direita. Quando um processador quer se comunicar 
com outro, a mensagem viaja por uma série de comutadores. 
 
O comutador mais à esquerda corresponde ao bit menos significativo (o mais à 
direita) do identificador (1D) do processador destinatário; o comutador do 
meio corresponde ao bit do meio; e o comutador mais à direita corresponde 
ao bit mais significativo (o mais à esquerda). 
 
Só há um caminho possível para a mensagem, e o endereço de destino define 
a rota. 
 
Veja, a seguir, uma figura que representa uma rede multiestágio Ômega com 
chaves 2 x 2: 
 
 
 
 
 
9 
 
0  indica saída “superior” 1  indica saída “inferior” 
 
Fonte: TANENBAUM, 2010. 
 
Redes multiestágios representam uma solução que busca uma relação entre 
custo e desempenho. Esse projeto emprega hardware simples para conectar 
grandes números de processadores. 
 
Qualquer processador pode-se comunicar com qualquer outro sem rotear a 
mensagem por processadores intermediários. Contudo, o diâmetro de uma 
rede multiestágio é maior. Portanto, a comunicação é mais lenta do que na 
matriz de comutação de barras cruzadas – cada mensagem tem de passar por 
vários comutadores. Além disso, pode-se desenvolver contenção nos 
elementos de comutação, o que pode degradar o desempenho. 
 
Como exemplo de sistema que usa uma rede multiestágio para conectar seus 
processadores, podemos citar o multiprocessador série SP da IBM, que evoluiu 
para o POWER4. O ASCI-White da IBM, que pode executar mais de 100 trilhões 
de operações por segundo, é baseado no multiprocessador POWER3-1.