Projeto de rede de interconexão

A interconnection networkem uma máquina paralela, transfere informações de qualquer nó de origem para qualquer nó de destino desejado. Esta tarefa deve ser concluída com a menor latência possível. Deve permitir que um grande número de tais transferências ocorram simultaneamente. Além disso, deve ser barato em comparação com o custo do resto da máquina.

A rede é composta de links e switches, o que ajuda a enviar as informações do nó de origem para o nó de destino. Uma rede é especificada por sua topologia, algoritmo de roteamento, estratégia de comutação e mecanismo de controle de fluxo.

Estrutura organizacional

As redes de interconexão são compostas dos seguintes três componentes básicos -

• Links- Um link é um cabo de uma ou mais fibras ópticas ou fios elétricos com um conector em cada extremidade conectado a um switch ou porta de interface de rede. Com isso, um sinal analógico é transmitido de uma extremidade, recebido na outra para obter o fluxo de informação digital original.

• Switches- Uma chave é composta de um conjunto de portas de entrada e saída, uma “barra cruzada” interna conectando todas as entradas a todas as saídas, buffer interno e lógica de controle para efetuar a conexão de entrada-saída em cada momento. Geralmente, o número de portas de entrada é igual ao número de portas de saída.

• Network Interfaces- A interface de rede se comporta de maneira bastante diferente dos nós de switch e pode ser conectada por meio de links especiais. A interface de rede formata os pacotes e constrói as informações de roteamento e controle. Ele pode ter buffer de entrada e saída, em comparação com um switch. Ele pode executar verificação de erros de ponta a ponta e controle de fluxo. Portanto, seu custo é influenciado por sua complexidade de processamento, capacidade de armazenamento e número de portas.

Rede de Interconexão

As redes de interconexão são compostas por elementos de comutação. Topologia é o padrão para conectar os switches individuais a outros elementos, como processadores, memórias e outros switches. Uma rede permite a troca de dados entre processadores no sistema paralelo.

• Direct connection networks- As redes diretas têm conexões ponto a ponto entre nós vizinhos. Essas redes são estáticas, o que significa que as conexões ponto a ponto são fixas. Alguns exemplos de redes diretas são anéis, malhas e cubos.

• Indirect connection networks- Redes indiretas não têm vizinhos fixos. A topologia de comunicação pode ser alterada dinamicamente com base nas demandas do aplicativo. As redes indiretas podem ser subdivididas em três partes: redes de barramento, redes de vários estágios e switches crossbar.

  • Bus networks- Uma rede de barramento é composta de várias linhas de bits às quais vários recursos são anexados. Quando os ônibus usam as mesmas linhas físicas para dados e endereços, os dados e as linhas de endereço são multiplexados no tempo. Quando há vários barramentos-mestre conectados ao barramento, um árbitro é necessário.

  • Multistage networks- Uma rede de vários estágios consiste em vários estágios de switches. É composto de interruptores 'axb' que são conectados usando um padrão de conexão interestadual (ISC) particular. Elementos de switch 2x2 pequenos são uma escolha comum para muitas redes de vários estágios. O número de estágios determina o atraso da rede. Ao escolher diferentes padrões de conexão entre os estágios, vários tipos de rede com vários estágios podem ser criados.

  • Crossbar switches- Um switch de barra transversal contém uma matriz de elementos de switch simples que podem ser ligados e desligados para criar ou interromper uma conexão. Ativando um elemento de chave na matriz, uma conexão entre um processador e uma memória pode ser feita. Os interruptores da barra cruzada não bloqueiam, ou seja, todas as permutações de comunicação podem ser realizadas sem bloqueio.

Avaliando trade-offs de design na topologia de rede

Se a principal preocupação for a distância de roteamento, então a dimensão deve ser maximizada e um hipercubo feito. No roteamento store-and-forward, assumindo que o grau da mudança e o número de links não foram um fator de custo significativo, e o número de links ou o grau de mudança são os custos principais, a dimensão deve ser minimizada e uma malha construído.

No pior caso, o padrão de tráfego para cada rede, é preferível ter redes de dimensões altas onde todos os caminhos são curtos. Em padrões onde cada nó está se comunicando com apenas um ou dois vizinhos próximos, é preferível ter redes de baixa dimensão, uma vez que apenas algumas das dimensões são realmente usadas.

Encaminhamento

O algoritmo de roteamento de uma rede determina qual dos caminhos possíveis da origem ao destino é usado como rotas e como a rota seguida por cada pacote específico é determinada. O roteamento de ordem de dimensão limita o conjunto de caminhos legais para que haja exatamente uma rota de cada origem para cada destino. Aquela obtida percorrendo primeiro a distância correta na dimensão de ordem superior, depois a próxima dimensão e assim por diante.

Mecanismos de Roteamento

Aritmética, seleção de porta com base na origem e consulta de tabela são três mecanismos que os comutadores de alta velocidade usam para determinar o canal de saída das informações no cabeçalho do pacote. Todos esses mecanismos são mais simples do que o tipo de cálculos de roteamento geral implementados em roteadores LAN e WAN tradicionais. Em redes paralelas de computadores, o switch precisa tomar a decisão de roteamento de todas as suas entradas em cada ciclo, portanto, o mecanismo precisa ser simples e rápido.

Roteamento Determinístico

Um algoritmo de roteamento é determinístico se a rota seguida por uma mensagem é determinada exclusivamente por sua origem e destino, e não por outro tráfego na rede. Se um algoritmo de roteamento seleciona apenas os caminhos mais curtos em direção ao destino, ele é mínimo, caso contrário, não é mínimo.

Deadlock Freedom

O deadlock pode ocorrer em várias situações. Quando dois nós tentam enviar dados um ao outro e cada um começa a enviar antes de receber um, pode ocorrer um deadlock 'frontal'. Outro caso de conflito ocorre, quando há várias mensagens competindo por recursos na rede.

A técnica básica para provar que uma rede está livre de deadlock é limpar as dependências que podem ocorrer entre os canais como resultado de mensagens que se movem pelas redes e mostrar que não há ciclos no gráfico geral de dependência do canal; portanto, não há padrões de tráfego que possam levar a um conflito. A maneira comum de fazer isso é numerar os recursos do canal de modo que todas as rotas sigam uma determinada sequência crescente ou decrescente, de modo que nenhum ciclo de dependência surja.

Switch Design

O projeto de uma rede depende do projeto do switch e de como os switches são conectados. O grau do switch, seus mecanismos de roteamento interno e seu buffer interno decidem quais topologias podem ser suportadas e quais algoritmos de roteamento podem ser implementados. Como qualquer outro componente de hardware de um sistema de computador, um switch de rede contém caminho de dados, controle e armazenamento.

Ports

O número total de pinos é, na verdade, o número total de portas de entrada e saída vezes a largura do canal. Como o perímetro do chip cresce lentamente em comparação com a área, os interruptores tendem a ser limitados por pinos.

Caminho de dados interno

O caminho de dados é a conectividade entre cada um dos conjuntos de portas de entrada e todas as portas de saída. É geralmente referido como barra transversal interna. Uma barra cruzada sem bloqueio é aquela em que cada porta de entrada pode ser conectada a uma saída distinta em qualquer permutação simultaneamente.

Buffers de canal

A organização do armazenamento de buffer dentro do switch tem um impacto importante no desempenho do switch. Os roteadores e switches tradicionais tendem a ter grandes buffers SRAM ou DRAM externos à estrutura do switch, enquanto nos switches VLSI o buffer é interno ao switch e sai do mesmo orçamento de silício que o caminho de dados e a seção de controle. À medida que o tamanho e a densidade do chip aumentam, mais armazenamento em buffer fica disponível e o designer da rede tem mais opções, mas ainda assim o espaço do buffer vem em uma escolha principal e sua organização é importante.

Controle de fluxo

Quando vários fluxos de dados na rede tentam usar os mesmos recursos de rede compartilhados ao mesmo tempo, alguma ação deve ser executada para controlar esses fluxos. Se não quisermos perder nenhum dado, alguns fluxos devem ser bloqueados enquanto outros prosseguem.

O problema de controle de fluxo surge em todas as redes e em muitos níveis. Mas é qualitativamente diferente em redes de computadores paralelas do que em redes locais e de área ampla. Em computadores paralelos, o tráfego de rede precisa ser entregue com a mesma precisão do tráfego em um barramento e há um grande número de fluxos paralelos em uma escala de tempo muito pequena.