Rede borboleta - Butterfly network
Uma rede borboleta é uma técnica para conectar vários computadores em uma rede de alta velocidade. Esta forma de topologia de rede de interconexão de vários estágios pode ser usada para conectar diferentes nós em um sistema multiprocessador . A rede de interconexão para um sistema multiprocessador de memória compartilhada deve ter baixa latência e alta largura de banda, ao contrário de outros sistemas de rede, como redes locais (LANs) ou internet por três motivos:
- As mensagens são relativamente curtas, pois a maioria das mensagens são solicitações e respostas do protocolo de coerência sem dados.
- As mensagens são geradas frequentemente porque cada falha de leitura ou falha de gravação gera mensagens para cada nó no sistema para garantir a coerência. As perdas de leitura / gravação ocorrem quando os dados solicitados não estão no cache do processador e devem ser buscados na memória ou no cache de outro processador.
- As mensagens são geradas com frequência, tornando difícil para os processadores ocultar o atraso de comunicação.
Componentes
Os principais componentes de uma rede de interconexão são:
- Nós de processador, que consistem em um ou mais processadores junto com seus caches , memórias e auxiliar de comunicação.
- Nós de comutação ( roteador ), que conectam a assistência de comunicação de diferentes nós de processador em um sistema. Em topologias de múltiplos estágios, os nós de comutação de nível superior se conectam a nós de comutação de nível inferior, conforme mostrado na figura 1, onde os nós de comutação na classificação 0 se conectam aos nós de processador diretamente, enquanto os nós de comutação na classificação 1 se conectam aos nós de comutação na classificação 0
- Links, que são fios físicos entre dois nós de comutação. Eles podem ser unidirecionais ou bidirecionais.
Essas redes de vários estágios têm custo menor do que uma barra transversal , mas obtêm contenção menor do que um barramento . A proporção de nós de comutação para nós de processador é maior do que um em uma rede borboleta. Essa topologia , em que a proporção de nós de comutação para nós de processador é maior que um, é chamada de topologia indireta.
O nome da rede deriva de conexões entre nós em duas fileiras adjacentes (como mostrado na figura 1), que se assemelha a uma borboleta . A fusão das classificações superior e inferior em uma única classificação cria uma Rede Borboleta Envolvida. Na figura 1, se os nós de classificação 3 forem conectados de volta aos respectivos nós de classificação 0, ela se tornará uma rede de borboletas embrulhada.
BBN Butterfly , um computador paralelo maciço construído por Bolt, Beranek e Newman na década de 1980, usava uma rede de interconexão de borboletas. Mais tarde, em 1990, a máquina Cray C90 da Cray Research , usou uma rede borboleta para se comunicar entre seus 16 processadores e 1024 bancos de memória.
Edifício da rede borboleta
Para uma rede borboleta com p nós de processador, é necessário que haja p (log 2 p + 1) nós de comutação. A Figura 1 mostra uma rede com 8 nós de processador, o que implica em 32 nós de comutação. Ele representa cada nó como N (classificação, número da coluna). Por exemplo, o nó na coluna 6 na classificação 1 é representado como (1,6) e o nó na coluna 2 na classificação 0 é representado como (0,2).
Para qualquer 'i' maior que zero, um nó de comutação N (i, j) é conectado a N (i-1, j) e N (i-1, m), onde, m é o bit invertido na i- ésima localização de j. Por exemplo, considere o nó N (1,6): i é igual a 1 ej é igual a 6, portanto m é obtido invertendo o i ésimo bit de 6.
| Variável | Representação binária | Representação Decimal |
|---|---|---|
| j | 110 | 6 |
| m | 010 | 2 |
Como resultado, os nós conectados a N (1,6) são:
| N (i, j) | N (i-1, j) | N (i-1, m) |
| (1,6) | (0,6) | (0,2) |
Assim, N (0,6), N (1,6), N (0,2), N (1,2) formam um padrão borboleta. Existem vários padrões de borboletas na figura e, portanto, essa rede é chamada de Rede de Borboletas.
Roteamento de rede borboleta
Em uma rede borboleta agrupada (o que significa que a classificação 0 é mesclada com a classificação 3), uma mensagem é enviada do processador 5 para o processador 2. Na figura 2, isso é mostrado pela replicação dos nós do processador abaixo da classificação 3. O pacote transmitido pelo link segue a forma:
| Cabeçalho | Carga útil | Reboque |
O cabeçalho contém o destino da mensagem, que é o processador 2 (010 em binário). A carga útil é a mensagem, M e o trailer contêm a soma de verificação . Portanto, a mensagem real transmitida do processador 5 é:
| 010 | M | soma de verificação |
Ao atingir um nó de comutação, um dos dois links de saída é selecionado com base no bit mais significativo do endereço de destino. Se esse bit for zero, o link esquerdo é selecionado. Se esse bit for um, o link correto será selecionado. Posteriormente, esse bit é removido do endereço de destino no pacote transmitido pelo link selecionado. Isso é mostrado na figura 2.
- O pacote acima atinge N (0,5). Do cabeçalho do pacote, ele remove o bit mais à esquerda para decidir a direção. Como é zero, o elo esquerdo de N (0,5) (que se conecta a N (1,1)) é selecionado. O novo cabeçalho é '10'.
- O novo pacote atinge N (1,1). Do cabeçalho do pacote, ele remove o bit mais à esquerda para decidir a direção. Como é um, o elo direito de N (1,1) (que se conecta a N (2,3)) é selecionado. O novo cabeçalho é '0'.
- O novo pacote atinge N (2,3). Do cabeçalho do pacote, ele remove o bit mais à esquerda para decidir a direção. Como é zero, o elo esquerdo de N (2,3) (que se conecta a N (3,2)) é selecionado. O campo do cabeçalho está vazio.
- O processador 2 recebe o pacote, que agora contém apenas a carga 'M' e a soma de verificação.
Parâmetros de rede borboleta
Vários parâmetros ajudam a avaliar uma topologia de rede. Os mais proeminentes relevantes no projeto de sistemas multiprocessadores em grande escala estão resumidos abaixo e uma explicação de como eles são calculados para uma rede borboleta com 8 nós de processador, conforme mostrado na figura 1, é fornecida.
- Bisection Bandwidth : A largura de banda máxima necessária para sustentar a comunicação entre todos os nós da rede. Isso pode ser interpretado como o número mínimo de links que precisam ser cortados para dividir o sistema em duas partes iguais. Por exemplo, a rede borboleta de 8 nós pode ser dividida em duas, cortando 4 links que se cruzam no meio. Assim, a largura de banda de bissecção deste sistema em particular é 4. É uma medida representativa do gargalo da largura de banda que restringe a comunicação geral.
- Diâmetro : O pior caso de latência (entre dois nós) possível no sistema. Ele pode ser calculado em termos de saltos de rede, que é o número de links que uma mensagem deve percorrer para chegar ao nó de destino. Na rede borboleta de 8 nós, parece que N (0,0) e N (3,7) estão mais distantes, mas após inspeção, é aparente que, devido à natureza simétrica da rede, atravessando a partir de qualquer nó de classificação 0 para qualquer nó de classificação 3 requer apenas 3 saltos. Portanto, o diâmetro deste sistema é 3.
- Links : número total de links necessários para construir toda a estrutura da rede. Este é um indicador de custo geral e complexidade de implementação. O exemplo de rede mostrado na figura 1 requer um total de 48 links (16 links cada entre as classificações 0 e 1, classificação 1 e 2, classificação 2 e 3).
- Grau : A complexidade de cada roteador na rede. Isso é igual ao número de links de entrada / saída conectados a cada nó de comutação. Os nós de comutação da rede borboleta têm 2 links de entrada e 2 links de saída, portanto, é uma rede de 4 graus.
Comparação com outras topologias de rede
Esta seção compara a rede borboleta com redes de matriz linear, anel, malha 2-D e hipercubo . Observe que a matriz linear pode ser considerada uma topologia de malha 1-D. Os parâmetros relevantes são compilados na tabela ('p' representa o número de nós do processador).
| Topologia | Diâmetro | Largura de banda de bissecção | Links | Grau |
|---|---|---|---|---|
| Matriz linear | p-1 | 1 | p-1 | 2 |
| Anel | p / 2 | 2 | p | 2 |
| Malha 2-D | 2 ( √ p - 1) | √ p | 2 √ p ( √ p - 1) | 4 |
| Hipercubo | log 2 (p) | p / 2 | log 2 (p) × (p / 2) | log 2 (p) |
| Borboleta | log 2 (p) | p / 2 | log 2 (p) × 2p | 4 |
Vantagens
- Redes de borboletas têm diâmetro menor do que outras topologias, como matriz linear, anel e malha 2-D. Isso implica que na rede borboleta, uma mensagem enviada de um processador alcançaria seu destino em um número menor de saltos de rede.
- Redes borboleta têm largura de banda de bissecção maior do que outras topologias. Isso implica que na rede borboleta, um número maior de links precisa ser quebrado para evitar a comunicação global.
- Possui um alcance maior de computadores.
Desvantagens
- As redes borboleta são mais complexas e caras do que outras topologias devido ao maior número de links necessários para sustentar a rede.
A diferença entre hipercubo e borboleta está em sua implementação. A rede borboleta tem uma estrutura simétrica onde todos os nós de processador entre duas fileiras são equidistantes entre si, enquanto o hipercubo é mais adequado para um sistema multiprocessador que exige distâncias desiguais entre seus nós. Ao olhar para o número de links necessários, pode parecer que o hipercubo é mais barato e simples em comparação com uma rede borboleta, mas como o número de nós de processador vai além de 16, o custo do roteador e a complexidade (representada pelo grau) da rede borboleta torna-se menor do que o hipercubo porque seu grau é independente do número de nós.
Em conclusão, nenhuma topologia de rede única é a melhor para todos os cenários. A decisão é tomada com base em fatores como o número de nós de processador no sistema, requisitos de latência de largura de banda, custo e escalabilidade .
Veja também
Origens
- Yan, Solihin (outubro de 2009). Fundamentos da Arquitetura de Computadores Paralelos: Sistemas Multichip e Multicore . Solihin Publishing & Consulting LLC. ISBN 978-0-9841630-0-7 .