Arquitetura do computador paralelo - Guia rápido

Nos últimos 50 anos, houve um grande desenvolvimento no desempenho e na capacidade de um sistema de computador. Isso foi possível com a ajuda da tecnologia Very Large Scale Integration (VLSI). A tecnologia VLSI permite que um grande número de componentes seja acomodado em um único chip e as taxas de clock aumentem. Portanto, mais operações podem ser realizadas ao mesmo tempo, em paralelo.

O processamento paralelo também está associado à localidade e comunicação de dados. Parallel Computer Architecture é o método de organizar todos os recursos para maximizar o desempenho e a programabilidade dentro dos limites dados pela tecnologia e o custo a qualquer momento.

Por que arquitetura paralela?

A arquitetura paralela do computador adiciona uma nova dimensão no desenvolvimento do sistema do computador, usando cada vez mais o número de processadores. Em princípio, o desempenho obtido pela utilização de um grande número de processadores é superior ao desempenho de um único processador em um determinado ponto do tempo.

Tendências de aplicação

Com o avanço da capacidade do hardware, a demanda por um aplicativo com bom desempenho também aumentou, o que, por sua vez, exigiu o desenvolvimento da arquitetura do computador.

Antes da era do microprocessador, o sistema de computador de alto desempenho era obtido por tecnologia de circuito exótica e organização da máquina, o que os tornava caros. Agora, o sistema de computador de alto desempenho é obtido usando vários processadores, e os aplicativos mais importantes e exigentes são escritos como programas paralelos. Portanto, para obter um desempenho superior, tanto arquiteturas paralelas quanto aplicativos paralelos precisam ser desenvolvidos.

Para aumentar o desempenho de um aplicativo, a aceleração é o fator chave a ser considerado. Speedup em processadores p é definido como -

$$Speedup(p \ processors)\equiv\frac{Performance(p \ processors)}{Performance(1 \ processor)}$$

Para o único problema resolvido,

$$performance \ of \ a \ computer \ system = \frac{1}{Time \ needed \ to \ complete \ the \ problem}$$ $$Speedup \ _{fixed \ problem} (p \ processors) =\frac{Time(1 \ processor)}{Time(p \ processor)}$$

Computação Científica e de Engenharia

A arquitetura paralela tornou-se indispensável na computação científica (como física, química, biologia, astronomia, etc.) e em aplicações de engenharia (como modelagem de reservatório, análise de fluxo de ar, eficiência de combustão, etc.). Em quase todas as aplicações, existe uma grande demanda por visualização de saída computacional resultando na demanda por desenvolvimento de computação paralela para aumentar a velocidade computacional.

Computação Comercial

Na computação comercial (como vídeo, gráficos, bancos de dados, OLTP, etc.) também são necessários computadores de alta velocidade para processar uma grande quantidade de dados em um tempo especificado. Desktop usa programas multithread que são quase como programas paralelos. Isso, por sua vez, exige o desenvolvimento de uma arquitetura paralela.

Tendências de Tecnologia

Com o desenvolvimento da tecnologia e da arquitetura, existe uma forte demanda pelo desenvolvimento de aplicativos de alto desempenho. Experimentos mostram que os computadores paralelos podem funcionar muito mais rápido do que o processador único desenvolvido. Além disso, computadores paralelos podem ser desenvolvidos dentro do limite da tecnologia e do custo.

A principal tecnologia usada aqui é a tecnologia VLSI. Portanto, hoje em dia cada vez mais transistores, portas e circuitos podem ser instalados na mesma área. Com a redução do tamanho do recurso VLSI básico, a taxa de clock também melhora em proporção a ele, enquanto o número de transistores aumenta conforme o quadrado. Pode-se esperar que o uso de muitos transistores ao mesmo tempo (paralelismo) funcione muito melhor do que aumentando a taxa de clock

As tendências tecnológicas sugerem que o bloco de construção básico de um único chip proporcionará uma capacidade cada vez maior. Portanto, aumenta a possibilidade de colocar vários processadores em um único chip.

Tendências arquitetônicas

O desenvolvimento em tecnologia decide o que é viável; a arquitetura converte o potencial da tecnologia em desempenho e capacidade.Parallelism e localitysão dois métodos em que maiores volumes de recursos e mais transistores aumentam o desempenho. No entanto, esses dois métodos competem pelos mesmos recursos. Quando várias operações são executadas em paralelo, o número de ciclos necessários para executar o programa é reduzido.

No entanto, são necessários recursos para dar suporte a cada uma das atividades simultâneas. Recursos também são necessários para alocar armazenamento local. O melhor desempenho é alcançado por um plano de ação intermediário que usa recursos para utilizar um grau de paralelismo e um grau de localidade.

Geralmente, a história da arquitetura do computador foi dividida em quatro gerações seguindo as tecnologias básicas -

• Tubos a vácuo
• Transistors
• Circuitos integrados
• VLSI

Até 1985, a duração foi dominada pelo crescimento do paralelismo de nível de bits. Microprocessadores de 4 bits seguidos por 8 bits, 16 bits e assim por diante. Para reduzir o número de ciclos necessários para executar uma operação completa de 32 bits, a largura do caminho de dados foi duplicada. Mais tarde, as operações de 64 bits foram introduzidas.

O crescimento em instruction-level-parallelismdominou meados dos anos 80 até meados dos anos 90. A abordagem RISC mostrou que era simples canalizar as etapas do processamento da instrução de modo que, em média, uma instrução fosse executada em quase todos os ciclos. O crescimento na tecnologia de compiladores tornou os pipelines de instrução mais produtivos.

Em meados dos anos 80, os computadores baseados em microprocessador consistiam em

• Uma unidade de processamento inteiro
• Uma unidade de ponto flutuante
• Um controlador de cache
• SRAMs para os dados de cache
• Armazenamento de tags

Conforme a capacidade do chip aumentou, todos esses componentes foram mesclados em um único chip. Assim, um único chip consistia em hardware separado para aritmética de inteiros, operações de ponto flutuante, operações de memória e operações de ramificação. Além de enviar instruções individuais por pipeline, ele busca várias instruções de uma vez e as envia em paralelo para diferentes unidades funcionais, sempre que possível. Este tipo de paralelismo de nível de instrução é chamadosuperscalar execution.

Máquinas paralelas foram desenvolvidas com várias arquiteturas distintas. Nesta seção, discutiremos diferentes arquiteturas paralelas de computadores e a natureza de sua convergência.

Arquitetura de Comunicação

A arquitetura paralela aprimora os conceitos convencionais de arquitetura de computador com arquitetura de comunicação. A arquitetura do computador define abstrações críticas (como limite do sistema do usuário e limite do hardware-software) e estrutura organizacional, enquanto a arquitetura de comunicação define as operações básicas de comunicação e sincronização. Também aborda a estrutura organizacional.

O modelo de programação é a camada superior. Os aplicativos são escritos em modelo de programação. Os modelos de programação paralela incluem -

• Espaço de endereçamento compartilhado
• Passagem de mensagem
• Programação paralela de dados

Shared addressprogramar é como usar um quadro de avisos, onde alguém pode se comunicar com um ou mais indivíduos postando informações em um local específico, que é compartilhado por todos os outros indivíduos. A atividade individual é coordenada observando quem está fazendo cada tarefa.

Message passing é como um telefonema ou cartas em que um destinatário específico recebe informações de um remetente específico.

Data parallela programação é uma forma organizada de cooperação. Aqui, vários indivíduos executam uma ação em elementos separados de um conjunto de dados simultaneamente e compartilham informações globalmente.

Memoria compartilhada

Os multiprocessadores de memória compartilhada são uma das classes mais importantes de máquinas paralelas. Ele oferece melhor rendimento em cargas de trabalho de multiprogramação e oferece suporte a programas paralelos.

Nesse caso, todos os sistemas de computador permitem que um processador e um conjunto de controlador de E / S acessem uma coleção de módulos de memória por alguma interconexão de hardware. A capacidade de memória é aumentada adicionando módulos de memória e a capacidade de E / S é aumentada adicionando dispositivos ao controlador de E / S ou adicionando controlador de E / S adicional. A capacidade de processamento pode ser aumentada aguardando que um processador mais rápido esteja disponível ou adicionando mais processadores.

Todos os recursos são organizados em torno de um barramento de memória central. Por meio do mecanismo de acesso ao barramento, qualquer processador pode acessar qualquer endereço físico no sistema. Como todos os processadores são equidistantes de todos os locais de memória, o tempo de acesso ou latência de todos os processadores é o mesmo em um local de memória. Isso é chamadosymmetric multiprocessor.

Arquitetura de passagem de mensagens

A arquitetura de passagem de mensagens também é uma classe importante de máquinas paralelas. Ele fornece comunicação entre os processadores como operações de E / S explícitas. Nesse caso, a comunicação é combinada no nível de E / S, ao invés do sistema de memória.

Na arquitetura de passagem de mensagens, a comunicação do usuário é executada usando o sistema operacional ou chamadas de biblioteca que realizam muitas ações de nível inferior, que incluem a operação de comunicação real. Como resultado, há uma distância entre o modelo de programação e as operações de comunicação no nível do hardware físico.

Send e receivesão as operações de comunicação de nível de usuário mais comuns no sistema de passagem de mensagens. Send especifica um buffer de dados local (que deve ser transmitido) e um processador remoto receptor. Receber especifica um processo de envio e um buffer de dados local no qual os dados transmitidos serão colocados. Na operação de envio, umidentifier ou um tag é anexado à mensagem e a operação de recebimento especifica a regra correspondente, como uma tag específica de um processador específico ou qualquer tag de qualquer processador.

A combinação de um envio e um recebimento correspondente conclui uma cópia de memória para memória. Cada extremidade especifica seu endereço de dados local e um evento de sincronização de pares.

Convergência

O desenvolvimento de hardware e software eliminou a fronteira clara entre a memória compartilhada e os campos de transmissão de mensagens. A passagem de mensagens e um espaço de endereço compartilhado representam dois modelos de programação distintos; cada um oferece um paradigma transparente para compartilhamento, sincronização e comunicação. No entanto, as estruturas básicas da máquina convergiram para uma organização comum.

Processamento Paralelo de Dados

Outra classe importante de máquina paralela é denominada de várias maneiras - matrizes de processadores, arquitetura paralela de dados e máquinas de instrução única com múltiplos dados. A principal característica do modelo de programação é que as operações podem ser executadas em paralelo em cada elemento de uma grande estrutura de dados regular (como array ou matriz).

As linguagens de programação paralela de dados são geralmente aplicadas pela visualização do espaço de endereço local de um grupo de processos, um por processador, formando um espaço global explícito. Como todos os processadores se comunicam juntos e há uma visão global de todas as operações, um espaço de endereço compartilhado ou a passagem de mensagens podem ser usados.

Questões Fundamentais de Design

O desenvolvimento do modelo de programação apenas não pode aumentar a eficiência do computador, nem o desenvolvimento do hardware sozinho. No entanto, o desenvolvimento da arquitetura do computador pode fazer a diferença no desempenho do computador. Podemos entender o problema de design nos concentrando em como os programas usam uma máquina e quais tecnologias básicas são fornecidas.

Nesta seção, discutiremos sobre a abstração de comunicação e os requisitos básicos do modelo de programação.

Abstração de comunicação

A abstração da comunicação é a principal interface entre o modelo de programação e a implementação do sistema. É como o conjunto de instruções que fornece uma plataforma para que o mesmo programa possa ser executado corretamente em muitas implementações. As operações neste nível devem ser simples.

A abstração da comunicação é como um contrato entre o hardware e o software, que permite um ao outro a flexibilidade de melhorar sem afetar o trabalho.

Requisitos do modelo de programação

Um programa paralelo possui um ou mais threads operando em dados. Um modelo de programação paralela define quais dados os threads podemname, qual operations pode ser executado nos dados nomeados e cuja ordem é seguida pelas operações.

Para confirmar que as dependências entre os programas são aplicadas, um programa paralelo deve coordenar a atividade de seus threads.

O processamento paralelo foi desenvolvido como uma tecnologia eficaz em computadores modernos para atender à demanda por maior desempenho, menor custo e resultados precisos em aplicações da vida real. Os eventos simultâneos são comuns nos computadores de hoje devido à prática de multiprogramação, multiprocessamento ou multicomputação.

Os computadores modernos possuem pacotes de software extensos e poderosos. Para analisar o desenvolvimento do desempenho dos computadores, primeiro temos que entender o desenvolvimento básico de hardware e software.

• Computer Development Milestones - Existem dois estágios principais de desenvolvimento do computador - mechanical ou electromechanicalpartes. Os computadores modernos evoluíram após a introdução de componentes eletrônicos. Elétrons de alta mobilidade em computadores eletrônicos substituíram as partes operacionais em computadores mecânicos. Para a transmissão de informações, o sinal elétrico que viaja quase à velocidade de uma luz substituiu as engrenagens ou alavancas mecânicas.

• Elements of Modern computers - Um sistema de computador moderno consiste em hardware de computador, conjuntos de instruções, programas aplicativos, software de sistema e interface de usuário.

Os problemas de computação são categorizados como computação numérica, raciocínio lógico e processamento de transações. Alguns problemas complexos podem precisar da combinação de todos os três modos de processamento.

• Evolution of Computer Architecture- Nas últimas quatro décadas, a arquitetura do computador passou por mudanças revolucionárias. Começamos com a arquitetura Von Neumann e agora temos multicomputadores e multiprocessadores.

• Performance of a computer system- O desempenho de um sistema de computador depende da capacidade da máquina e do comportamento do programa. A capacidade da máquina pode ser aprimorada com melhor tecnologia de hardware, recursos arquitetônicos avançados e gerenciamento de recursos eficiente. O comportamento do programa é imprevisível, pois depende do aplicativo e das condições de tempo de execução

Multiprocessadores e multicomputadores

Nesta seção, discutiremos dois tipos de computadores paralelos -

• Multiprocessors
• Multicomputers

Multicomputadores de memória compartilhada

Os três modelos mais comuns de multiprocessadores de memória compartilhada são -

Acesso uniforme à memória (UMA)

Neste modelo, todos os processadores compartilham a memória física uniformemente. Todos os processadores têm igual tempo de acesso a todas as palavras de memória. Cada processador pode ter uma memória cache privada. A mesma regra é seguida para dispositivos periféricos.

Quando todos os processadores têm acesso igual a todos os dispositivos periféricos, o sistema é chamado de symmetric multiprocessor. Quando apenas um ou alguns processadores podem acessar os dispositivos periféricos, o sistema é chamado deasymmetric multiprocessor.

Acesso não uniforme à memória (NUMA)

No modelo de multiprocessador NUMA, o tempo de acesso varia com a localização da palavra de memória. Aqui, a memória compartilhada é fisicamente distribuída entre todos os processadores, chamados de memórias locais. A coleção de todas as memórias locais forma um espaço de endereço global que pode ser acessado por todos os processadores.

Arquitetura de memória somente cache (COMA)

O modelo COMA é um caso especial do modelo NUMA. Aqui, todas as memórias principais distribuídas são convertidas em memórias cache.

• Distributed - Memory Multicomputers- Um sistema multicomputador de memória distribuída consiste em vários computadores, conhecidos como nós, interconectados por rede de passagem de mensagens. Cada nó atua como um computador autônomo com um processador, uma memória local e, às vezes, dispositivos de E / S. Nesse caso, todas as memórias locais são privadas e acessíveis apenas aos processadores locais. É por isso que as máquinas tradicionais são chamadasno-remote-memory-access (NORMA) máquinas.

Computadores multivetores e SIMD

Nesta seção, discutiremos supercomputadores e processadores paralelos para processamento vetorial e paralelismo de dados.

Supercomputadores vetoriais

Em um computador vetorial, um processador vetorial é conectado ao processador escalar como um recurso opcional. O computador host primeiro carrega o programa e os dados na memória principal. Em seguida, a unidade de controle escalar decodifica todas as instruções. Se as instruções decodificadas são operações escalares ou operações de programa, o processador escalar executa essas operações usando pipelines funcionais escalares.

Por outro lado, se as instruções decodificadas são operações vetoriais, as instruções serão enviadas para a unidade de controle vetorial.

Supercomputadores SIMD

Em computadores SIMD, o número 'N' de processadores é conectado a uma unidade de controle e todos os processadores têm suas unidades de memória individuais. Todos os processadores são conectados por uma rede de interconexão.

Modelos PRAM e VLSI

O modelo ideal oferece uma estrutura adequada para desenvolver algoritmos paralelos sem considerar as restrições físicas ou detalhes de implementação.

Os modelos podem ser aplicados para obter limites teóricos de desempenho em computadores paralelos ou para avaliar a complexidade VLSI na área do chip e no tempo operacional antes que o chip seja fabricado.

Máquinas paralelas de acesso aleatório

Sheperdson e Sturgis (1963) modelaram os computadores convencionais de Uniprocessador como máquinas de acesso aleatório (RAM). Fortune e Wyllie (1978) desenvolveram um modelo de máquina de acesso aleatório paralelo (PRAM) para modelar um computador paralelo idealizado com sobrecarga de acesso à memória zero e sincronização.

Um N-processador PRAM tem uma unidade de memória compartilhada. Essa memória compartilhada pode ser centralizada ou distribuída entre os processadores. Esses processadores operam em uma memória de leitura, memória de gravação e ciclo de computação sincronizados. Portanto, esses modelos especificam como as operações simultâneas de leitura e gravação são tratadas.

A seguir estão as possíveis operações de atualização de memória -

• Exclusive read (ER) - Neste método, em cada ciclo, apenas um processador pode ler de qualquer local da memória.

• Exclusive write (EW) - Neste método, pelo menos um processador tem permissão para gravar em um local da memória por vez.

• Concurrent read (CR) - Permite que vários processadores leiam as mesmas informações do mesmo local de memória no mesmo ciclo.

• Concurrent write (CW)- Permite operações de gravação simultâneas no mesmo local da memória. Para evitar conflito de gravação, algumas políticas são definidas.

Modelo de Complexidade VLSI

Os computadores paralelos usam chips VLSI para fabricar arrays de processadores, arrays de memória e redes de comutação em grande escala.

Hoje em dia, as tecnologias VLSI são bidimensionais. O tamanho de um chip VLSI é proporcional à quantidade de espaço de armazenamento (memória) disponível nesse chip.

Podemos calcular a complexidade espacial de um algoritmo pela área do chip (A) da implementação do chip VLSI desse algoritmo. Se T é o tempo (latência) necessário para executar o algoritmo, então AT fornece um limite superior no número total de bits processados ​​por meio do chip (ou E / S). Para certos cálculos, existe um limite inferior, f (s), de modo que

AT ² > = O (f (s))

Onde A = área do chip e T = tempo

Trilhas de desenvolvimento arquitetônico

A evolução dos computadores paralelos que divulgo nas seguintes trilhas -

• Várias trilhas de processador
  • Faixa de multiprocessador
  • Faixa multicomputador
• Multiple data track
  • Trilha de vetor
  • Pista SIMD
• Acompanhamento de vários tópicos
  • Faixa multithread
  • Faixa de fluxo de dados

  Dentro multiple processor track, presume-se que diferentes threads executam simultaneamente em diferentes processadores e se comunicam por meio de memória compartilhada (trilha de multiprocessador) ou sistema de passagem de mensagens (trilha de multicomputador).

  Dentro multiple data track, presume-se que o mesmo código seja executado na grande quantidade de dados. É feito executando as mesmas instruções em uma seqüência de elementos de dados (trilha de vetor) ou por meio da execução de uma mesma seqüência de instruções em um conjunto de dados semelhante (trilha SIMD).

  Dentro multiple threads track, presume-se que a execução intercalada de vários threads no mesmo processador para ocultar atrasos de sincronização entre threads em execução em diferentes processadores. A intercalação de thread pode ser grosseira (trilha multithread) ou fina (trilha de fluxo de dados).

  Na década de 80, um processador de propósito especial era popular para fazer multicomputadores chamados Transputer. Um transputador consistia em um processador central, uma pequena memória SRAM, uma interface de memória principal DRAM e quatro canais de comunicação, tudo em um único chip. Para fazer uma comunicação paralela com o computador, canais foram conectados para formar uma rede de Transputadores. Mas ele tem falta de capacidade computacional e, portanto, não pode atender à crescente demanda de aplicativos paralelos. Esse problema foi resolvido com o desenvolvimento de processadores RISC e também era barato.

  O computador paralelo moderno usa microprocessadores que usam paralelismo em vários níveis, como paralelismo de nível de instrução e paralelismo de nível de dados.

  Processadores de alto desempenho

  Os processadores RISC e RISCy dominam o mercado de computadores paralelos de hoje.

  As características do RISC tradicional são -

  • Possui poucos modos de endereçamento.
  • Tem um formato fixo para instruções, geralmente de 32 ou 64 bits.
  • Possui instruções de carregamento / armazenamento dedicadas para carregar dados da memória para registrar e armazenar dados do registro para a memória.
  • As operações aritméticas são sempre realizadas em registradores.
  • Usa pipelining.

  A maioria dos microprocessadores hoje em dia é superescalar, ou seja, em um computador paralelo, vários pipelines de instrução são usados. Portanto, os processadores superescalares podem executar mais de uma instrução ao mesmo tempo. A eficácia dos processadores superescalares depende da quantidade de paralelismo de nível de instrução (ILP) disponível nos aplicativos. Para manter os pipelines preenchidos, as instruções no nível do hardware são executadas em uma ordem diferente da ordem do programa.

  Muitos microprocessadores modernos usam a abordagem de super pipelining . No super pipelining , para aumentar a frequência do clock, o trabalho realizado em um estágio de pipeline é reduzido e o número de estágios de pipeline é aumentado.

  Processadores de palavras de instrução muito grandes (VLIW)

  Eles são derivados da microprogramação horizontal e do processamento superescalar. As instruções nos processadores VLIW são muito grandes. As operações em uma única instrução são executadas em paralelo e encaminhadas para as unidades funcionais apropriadas para execução. Então, após buscar uma instrução VLIW, suas operações são decodificadas. Em seguida, as operações são despachadas para as unidades funcionais nas quais são executadas em paralelo.

  Processadores Vetoriais

  Os processadores vetoriais são coprocessadores para microprocessadores de uso geral. Os processadores vetoriais são geralmente registradores-registradores ou memória-memória. Uma instrução de vetor é buscada e decodificada e, em seguida, uma determinada operação é realizada para cada elemento dos vetores de operando, enquanto em um processador normal uma operação de vetor precisa de uma estrutura de loop no código. Para torná-lo mais eficiente, os processadores vetoriais encadeiam várias operações vetoriais, ou seja, o resultado de uma operação vetorial é encaminhado para outra como operando.

  Cache

  Caches são elementos importantes de microprocessadores de alto desempenho. Depois de cada 18 meses, a velocidade dos microprocessadores torna-se duas vezes, mas os chips DRAM para a memória principal não podem competir com essa velocidade. Portanto, os caches são introduzidos para preencher a lacuna de velocidade entre o processador e a memória. Um cache é uma memória SRAM rápida e pequena. Muitos mais caches são aplicados em processadores modernos, como caches Translation Look-Side Buffers (TLBs), caches de instrução e de dados, etc.

  Cache Mapeado Direto

  Em caches mapeados diretamente, uma função 'módulo' é usada para mapeamento um-para-um de endereços na memória principal para localizações de cache. Como a mesma entrada de cache pode ter vários blocos de memória principal mapeados para ela, o processador deve ser capaz de determinar se um bloco de dados no cache é o bloco de dados realmente necessário. Essa identificação é feita armazenando uma tag junto com um bloco de cache.

  Cache Totalmente Associativo

  Um mapeamento totalmente associativo permite colocar um bloco de cache em qualquer lugar do cache. Usando alguma política de substituição, o cache determina uma entrada de cache na qual armazena um bloco de cache. Caches totalmente associativos têm mapeamento flexível, o que minimiza o número de conflitos de entrada de cache. Como uma implementação totalmente associativa é cara, eles nunca são usados ​​em grande escala.

  Cache associativo de conjunto

  Um mapeamento associativo de conjunto é uma combinação de um mapeamento direto e um mapeamento totalmente associativo. Nesse caso, as entradas de cache são subdivididas em conjuntos de cache. Como no mapeamento direto, há um mapeamento fixo de blocos de memória para um conjunto no cache. Mas dentro de um conjunto de cache, um bloco de memória é mapeado de maneira totalmente associativa.

  Estratégias de cache

  Além do mecanismo de mapeamento, os caches também precisam de uma série de estratégias que especificam o que deve acontecer no caso de certos eventos. No caso de caches associativos (set-), o cache deve determinar qual bloco de cache deve ser substituído por um novo bloco entrando no cache.

  Algumas estratégias de substituição bem conhecidas são -

  • Primeiro a entrar, primeiro a sair (FIFO)
  • Menos usado recentemente (LRU)

  Discutiremos multiprocessadores e multicomputadores neste capítulo.

  Multiprocessor System Interconnects

  O processamento paralelo precisa do uso de interconexões de sistema eficientes para comunicação rápida entre os dispositivos de entrada / saída e periféricos, multiprocessadores e memória compartilhada.

  Sistemas Hierárquicos de Barramento

  Um sistema de barramento hierárquico consiste em uma hierarquia de barramentos conectando vários sistemas e subsistemas / componentes em um computador. Cada barramento é composto de várias linhas de sinal, controle e energia. Barramentos diferentes, como barramentos locais, barramentos de backplane e barramentos de E / S, são usados ​​para realizar diferentes funções de interconexão.

  Os ônibus locais são os ônibus implementados nas placas de circuito impresso. Um barramento de backplane é um circuito impresso no qual muitos conectores são usados ​​para conectar placas funcionais. Os barramentos que conectam dispositivos de entrada / saída a um sistema de computador são conhecidos como barramentos de E / S.

  Interruptor de barra cruzada e memória multiporta

  As redes comutadas fornecem interconexões dinâmicas entre as entradas e saídas. Os sistemas de pequeno ou médio porte usam principalmente redes crossbar. Redes de múltiplos estágios podem ser expandidas para sistemas maiores, se o problema de latência aumentada puder ser resolvido.

  Tanto o switch crossbar quanto a organização de memória multiporta são uma rede de estágio único. Embora seja mais barato construir uma rede de estágio único, podem ser necessárias várias passagens para estabelecer certas conexões. Uma rede de vários estágios possui mais de um estágio de caixas de comutação. Essas redes devem ser capazes de conectar qualquer entrada a qualquer saída.

  Redes de múltiplos estágios e combinação

  Redes de múltiplos estágios ou redes de interconexão de múltiplos estágios são uma classe de redes de computadores de alta velocidade que são principalmente compostas por elementos de processamento em uma extremidade da rede e elementos de memória na outra extremidade, conectados por elementos de comutação.

  Essas redes são aplicadas para construir sistemas multiprocessadores maiores. Isso inclui a Omega Network, a Butterfly Network e muito mais.

  Multicomputadores

  Os multicomputadores são arquiteturas MIMD de memória distribuída. O diagrama a seguir mostra um modelo conceitual de um multicomputador -

  

  Multicomputadores são máquinas que passam mensagens que aplicam o método de comutação de pacotes para trocar dados. Aqui, cada processador tem uma memória privada, mas nenhum espaço de endereço global, pois um processador pode acessar apenas sua própria memória local. Portanto, a comunicação não é transparente: aqui os programadores precisam colocar explicitamente as primitivas de comunicação em seu código.

  Não ter memória acessível globalmente é uma desvantagem dos multicomputadores. Isso pode ser resolvido usando os dois esquemas a seguir -

  • Memória Virtual Compartilhada (VSM)
  • Memória Virtual Compartilhada (SVM)

  Nesses esquemas, o programador de aplicativos assume uma grande memória compartilhada que pode ser endereçada globalmente. Se necessário, as referências de memória feitas por aplicativos são traduzidas no paradigma de transmissão de mensagens.

  Memória Virtual Compartilhada (VSM)

  VSM é uma implementação de hardware. Portanto, o sistema de memória virtual do sistema operacional é implementado de forma transparente no topo do VSM. Portanto, o sistema operacional pensa que está sendo executado em uma máquina com memória compartilhada.

  Memória Virtual Compartilhada (SVM)

  SVM é uma implementação de software no nível do sistema operacional com suporte de hardware da unidade de gerenciamento de memória (MMU) do processador. Aqui, a unidade de compartilhamento são as páginas de memória do sistema operacional.

  Se um processador endereça um determinado local de memória, a MMU determina se a página de memória associada ao acesso à memória está na memória local ou não. Se a página não estiver na memória, em um sistema de computador normal, ela será trocada do disco pelo sistema operacional. Mas, no SVM, o sistema operacional busca a página do nó remoto que possui essa página específica.

  Três Gerações de Multicomputadores

  Nesta seção, discutiremos três gerações de multicomputadores.

  Escolhas de design no passado

  Ao selecionar uma tecnologia de processador, um designer de multicomputador escolhe processadores de baixo custo de grãos médios como blocos de construção. A maioria dos computadores paralelos é construída com microprocessadores padrão prontos para uso. A memória distribuída foi escolhida para vários computadores em vez de usar memória compartilhada, o que limitaria a escalabilidade. Cada processador possui sua própria unidade de memória local.

  Para o esquema de interconexão, os multicomputadores têm troca de mensagens, redes diretas ponto a ponto em vez de redes de comutação de endereços. Para estratégia de controle, o projetista de multi-computadores escolhe as operações assíncronas MIMD, MPMD e SMPD. O Cosmic Cube da Caltech (Seitz, 1983) é o primeiro da primeira geração de multi-computadores.

  Desenvolvimento Presente e Futuro

  A próxima geração de computadores evoluiu de multicomputadores de grão médio para fino usando uma memória virtual compartilhada globalmente. Os multi-computadores de segunda geração ainda estão em uso atualmente. Mas usando um processador melhor, como i386, i860, etc., os computadores de segunda geração evoluíram muito.

  Os computadores de terceira geração são os computadores da próxima geração em que os nós implementados VLSI serão usados. Cada nó pode ter um processador de 14 MIPS, canais de roteamento de 20 Mbytes / s e 16 Kbytes de RAM integrados em um único chip.

  O Sistema Intel Paragon

  Anteriormente, nós homogêneos eram usados ​​para fazer multicomputadores hipercubos, já que todas as funções eram atribuídas ao host. Portanto, isso limitou a largura de banda de E / S. Portanto, para resolver problemas de grande escala de forma eficiente ou com alto rendimento, esses computadores não podiam ser usados. O Intel Paragon System foi projetado para superar essa dificuldade. Ele transformou o multicomputador em um servidor de aplicativos com acesso multiusuário em um ambiente de rede.

  Mecanismos de passagem de mensagens

  Os mecanismos de passagem de mensagens em uma rede multicomputador precisam de suporte especial de hardware e software. Nesta seção, discutiremos alguns esquemas.

  Esquemas de roteamento de mensagens

  Em multicomputadores com esquema de roteamento de armazenamento e encaminhamento, os pacotes são a menor unidade de transmissão de informações. Em redes roteadas por buracos de minhoca, os pacotes são divididos ainda em flits. O comprimento do pacote é determinado pelo esquema de roteamento e implementação da rede, enquanto o comprimento do flit é afetado pelo tamanho da rede.

  Dentro Store and forward routing, os pacotes são a unidade básica de transmissão de informações. Nesse caso, cada nó usa um buffer de pacote. Um pacote é transmitido de um nó de origem para um nó de destino por meio de uma sequência de nós intermediários. A latência é diretamente proporcional à distância entre a origem e o destino.

  Dentro wormhole routing, a transmissão do nó de origem para o nó de destino é feita por meio de uma sequência de roteadores. Todos os flits do mesmo pacote são transmitidos em uma seqüência inseparável de um modo pipeline. Nesse caso, apenas o flit de cabeçalho sabe para onde o pacote está indo.

  Deadlock e canais virtuais

  Um canal virtual é um link lógico entre dois nós. É formado por flit buffer no nó fonte e no nó receptor, e um canal físico entre eles. Quando um canal físico é alocado para um par, um buffer de origem é emparelhado com um buffer de receptor para formar um canal virtual.

  Quando todos os canais estiverem ocupados por mensagens e nenhum canal do ciclo for liberado, ocorrerá uma situação de deadlock. Para evitar isso, um esquema de prevenção de deadlock deve ser seguido.

  Neste capítulo, discutiremos os protocolos de coerência de cache para lidar com os problemas de inconsistência de multicache.

  O problema de coerência do cache

  Em um sistema multiprocessador, a inconsistência de dados pode ocorrer entre níveis adjacentes ou dentro do mesmo nível da hierarquia de memória. Por exemplo, o cache e a memória principal podem ter cópias inconsistentes do mesmo objeto.

  Como vários processadores operam em paralelo e, de forma independente, vários caches podem possuir diferentes cópias do mesmo bloco de memória, isso cria cache coherence problem. Cache coherence schemes ajudar a evitar esse problema, mantendo um estado uniforme para cada bloco de dados em cache.

  

  Seja X um elemento de dados compartilhados que foi referenciado por dois processadores, P1 e P2. No início, três cópias de X são consistentes. Se o processador P1 grava um novo dado X1 no cache, usandowrite-through policy, a mesma cópia será gravada imediatamente na memória compartilhada. Nesse caso, ocorre inconsistência entre a memória cache e a memória principal. Quando umwrite-back policy for usado, a memória principal será atualizada quando os dados modificados no cache forem substituídos ou invalidados.

  Em geral, existem três fontes de problemas de inconsistência -

  • Compartilhamento de dados graváveis
  • Migração de processo
  • Atividade de I / O

  Protocolos de Snoopy Bus

  Os protocolos Snoopy alcançam consistência de dados entre a memória cache e a memória compartilhada por meio de um sistema de memória baseado em barramento. Write-invalidate e write-update as políticas são usadas para manter a consistência do cache.

  
  

  Neste caso, temos três processadores P1, P2 e P3 tendo uma cópia consistente do elemento de dados 'X' em sua memória cache local e na memória compartilhada (Figura-a). O processador P1 grava X1 em sua memória cache usandowrite-invalidate protocol. Portanto, todas as outras cópias são invalidadas pelo ônibus. É denotado por 'I' (Figura-b). Blocos inválidos também são conhecidos comodirty, ou seja, eles não devem ser usados. owrite-update protocolatualiza todas as cópias de cache por meio do barramento. Usandowrite back cache, a cópia da memória também é atualizada (Figura-c).

  

  Eventos e ações de cache

  Os seguintes eventos e ações ocorrem na execução de comandos de acesso à memória e invalidação -

  • Read-miss- Quando um processador deseja ler um bloco e ele não está no cache, ocorre uma falha de leitura. Isso inicia umbus-readOperação. Se não houver nenhuma cópia suja, a memória principal que possui uma cópia consistente fornece uma cópia para a memória cache solicitante. Se houver uma cópia suja em uma memória cache remota, esse cache restringirá a memória principal e enviará uma cópia à memória cache solicitante. Em ambos os casos, a cópia do cache entrará no estado válido após uma falha de leitura.

  • Write-hit - Se a cópia estiver suja ou reservedestado, a gravação é feita localmente e o novo estado está sujo. Se o novo estado for válido, o comando write-invalidate é transmitido a todos os caches, invalidando suas cópias. Quando a memória compartilhada é gravada, o estado resultante é reservado após essa primeira gravação.

  • Write-miss- Se um processador não consegue gravar na memória cache local, a cópia deve vir da memória principal ou de uma memória cache remota com um bloco sujo. Isso é feito enviando umread-invalidatecomando, o que invalidará todas as cópias de cache. Em seguida, a cópia local é atualizada com o estado incorreto.

  • Read-hit - O acerto de leitura é sempre executado na memória cache local sem causar uma transição de estado ou usar o barramento snoopy para invalidação.

  • Block replacement- Quando uma cópia está suja, ela deve ser gravada de volta na memória principal pelo método de substituição de bloco. No entanto, quando a cópia estiver em estado válido ou reservado ou inválido, nenhuma substituição ocorrerá.

  Protocolos baseados em diretório

  Ao usar uma rede de vários estágios para construir um grande multiprocessador com centenas de processadores, os protocolos de cache snoopy precisam ser modificados para se adequarem aos recursos da rede. A transmissão é muito cara para ser executada em uma rede de vários estágios, os comandos de consistência são enviados apenas para os caches que mantêm uma cópia do bloco. Esta é a razão para o desenvolvimento de protocolos baseados em diretório para multiprocessadores conectados à rede.

  Em um sistema de protocolos baseado em diretório, os dados a serem compartilhados são colocados em um diretório comum que mantém a coerência entre os caches. Aqui, o diretório atua como um filtro onde os processadores pedem permissão para carregar uma entrada da memória primária para sua memória cache. Se uma entrada for alterada, o diretório a atualiza ou invalida os outros caches com essa entrada.

  Mecanismos de sincronização de hardware

  A sincronização é uma forma especial de comunicação onde, em vez de controle de dados, as informações são trocadas entre processos de comunicação que residem no mesmo ou em processadores diferentes.

  Os sistemas multiprocessadores usam mecanismos de hardware para implementar operações de sincronização de baixo nível. A maioria dos multiprocessadores possui mecanismos de hardware para impor operações atômicas, como operações de leitura, gravação ou leitura-modificação-gravação de memória para implementar algumas primitivas de sincronização. Além das operações de memória atômica, algumas interrupções entre processadores também são usadas para fins de sincronização.

  Coerência de cache em máquinas de memória compartilhada

  Manter a coerência do cache é um problema no sistema multiprocessador quando os processadores contêm memória cache local. A inconsistência de dados entre diferentes caches ocorre facilmente neste sistema.

  As principais áreas de preocupação são -

  • Compartilhamento de dados graváveis
  • Migração de processo
  • Atividade de I / O

  Compartilhamento de dados graváveis

  Quando dois processadores (P1 e P2) têm o mesmo elemento de dados (X) em seus caches locais e um processo (P1) grava no elemento de dados (X), como os caches são gravados no cache local de P1, a memória principal é também atualizado. Agora, quando P2 tenta ler o elemento de dados (X), ele não encontra X porque o elemento de dados no cache de P2 ficou desatualizado.

  

  Migração de processo

  No primeiro estágio, o cache de P1 possui elemento de dados X, enquanto P2 não possui nada. Um processo em P2 grava primeiro em X e depois migra para P1. Agora, o processo começa a ler o elemento de dados X, mas como o processador P1 tem dados desatualizados, o processo não pode lê-los. Portanto, um processo em P1 grava no elemento de dados X e migra para P2. Após a migração, um processo em P2 começa a ler o elemento de dados X, mas encontra uma versão desatualizada de X na memória principal.

  

  Atividade de I / O

  Conforme ilustrado na figura, um dispositivo de E / S é adicionado ao barramento em uma arquitetura de multiprocessador de dois processadores. No início, ambos os caches contêm o elemento de dados X. Quando o dispositivo de E / S recebe um novo elemento X, ele armazena o novo elemento diretamente na memória principal. Agora, quando P1 ou P2 (suponha que P1) tenta ler o elemento X, ele obtém uma cópia desatualizada. Portanto, P1 escreve no elemento X. Agora, se o dispositivo de E / S tentar transmitir X, ele obtém uma cópia desatualizada.

  

  Acesso uniforme à memória (UMA)

  A arquitetura Uniform Memory Access (UMA) significa que a memória compartilhada é a mesma para todos os processadores do sistema. As classes populares de máquinas UMA, que são comumente usadas para servidores (de arquivo), são os chamados Multiprocessadores Simétricos (SMPs). Em um SMP, todos os recursos do sistema como memória, discos, outros dispositivos de E / S, etc. são acessíveis pelos processadores de maneira uniforme.

  Acesso não uniforme à memória (NUMA)

  Na arquitetura NUMA, existem vários clusters SMP com uma rede indireta / compartilhada interna, que são conectados em uma rede escalonável de passagem de mensagens. Portanto, a arquitetura NUMA é uma arquitetura de memória distribuída fisicamente compartilhada de maneira lógica.

  Em uma máquina NUMA, o controlador de cache de um processador determina se uma referência de memória é local para a memória do SMP ou é remota. Para reduzir o número de acessos à memória remota, as arquiteturas NUMA geralmente aplicam processadores de cache que podem armazenar os dados remotos. Mas quando os caches estão envolvidos, a coerência do cache precisa ser mantida. Portanto, esses sistemas também são conhecidos como CC-NUMA (Cache Coherent NUMA).

  Arquitetura de memória somente cache (COMA)

  As máquinas COMA são semelhantes às máquinas NUMA, com a única diferença de que as memórias principais das máquinas COMA atuam como caches mapeados diretamente ou conjuntos associativos. Os blocos de dados são transferidos para um local no cache DRAM de acordo com seus endereços. Os dados buscados remotamente são armazenados na memória principal local. Além disso, os blocos de dados não têm um local fixo de residência, eles podem se mover livremente por todo o sistema.

  A maioria das arquiteturas COMA possui uma rede hierárquica de passagem de mensagens. Um switch em tal árvore contém um diretório com elementos de dados como sua subárvore. Uma vez que os dados não têm localização inicial, eles devem ser procurados explicitamente. Isso significa que um acesso remoto requer uma travessia ao longo das opções na árvore para pesquisar seus diretórios em busca dos dados necessários. Portanto, se um switch na rede recebe várias solicitações de sua subárvore para os mesmos dados, ele os combina em uma única solicitação que é enviada ao pai do switch. Quando os dados solicitados retornam, o switch envia várias cópias deles por sua subárvore.

COMA versus CC-NUMA

A seguir estão as diferenças entre COMA e CC-NUMA.

• O COMA tende a ser mais flexível do que o CC-NUMA porque o COMA oferece suporte transparente à migração e replicação de dados sem a necessidade do sistema operacional.

• As máquinas COMA são caras e complexas de construir porque precisam de hardware de gerenciamento de memória não padrão e o protocolo de coerência é mais difícil de implementar.

• Os acessos remotos no COMA costumam ser mais lentos do que no CC-NUMA, pois a rede da árvore precisa ser atravessada para encontrar os dados.

Existem muitos métodos para reduzir o custo do hardware. Um método é integrar a assistência de comunicação e a rede de forma menos rígida no nó de processamento, aumentando a latência e a ocupação da comunicação.

Outro método é fornecer replicação automática e coerência em software, em vez de hardware. O último método fornece replicação e coerência na memória principal e pode ser executado em uma variedade de granularidades. Ele permite o uso de peças de mercadoria prontas para uso para os nós e interconexão, minimizando o custo de hardware. Isso pressiona o programador para obter um bom desempenho.

Modelos de consistência de memória relaxada

O modelo de consistência de memória para um espaço de endereço compartilhado define as restrições na ordem em que as operações de memória nos mesmos locais ou em locais diferentes parecem estar sendo executadas entre si. Na verdade, qualquer camada do sistema que suporte um modelo de nomenclatura de espaço de endereço compartilhado deve ter um modelo de consistência de memória que inclui a interface do programador, a interface do sistema do usuário e a interface do hardware-software. O software que interage com essa camada deve estar ciente de seu próprio modelo de consistência de memória.

Especificações do sistema

A especificação do sistema de uma arquitetura especifica a ordem e a reordenação das operações de memória e quanto desempenho pode realmente ser obtido com isso.

A seguir estão alguns modelos de especificação usando os relaxamentos na ordem do programa -

• Relaxing the Write-to-Read Program Order- Essa classe de modelos permite que o hardware suprima a latência das operações de gravação que foram perdidas na memória cache de primeiro nível. Quando a falha de gravação está no buffer de gravação e não é visível para outros processadores, o processador pode completar as leituras que acertam em sua memória cache ou mesmo uma única leitura que falha em sua memória cache.

• Relaxing the Write-to-Read and Write-to-Write Program Orders- Permitir que as gravações ignorem as gravações pendentes anteriores em vários locais permite que várias gravações sejam mescladas no buffer de gravação antes de atualizar a memória principal. Assim, vários erros de gravação serão sobrepostos e se tornarão visíveis fora de ordem. A motivação é minimizar ainda mais o impacto da latência de gravação no tempo de interrupção do processador e aumentar a eficiência da comunicação entre os processadores, tornando novos valores de dados visíveis para outros processadores.

• Relaxing All Program Orders- Nenhum pedido de programa é garantido por padrão, exceto dados e dependências de controle dentro de um processo. Assim, a vantagem é que as várias solicitações de leitura podem ser pendentes ao mesmo tempo e, na ordem do programa, podem ser contornadas por gravações posteriores e podem ser concluídas fora de ordem, permitindo ocultar a latência de leitura. Esse tipo de modelo é particularmente útil para processadores agendados dinamicamente, que podem continuar após as perdas de leitura para outras referências de memória. Eles permitem muitos dos reordenamentos, até mesmo a eliminação de acessos que são feitos por otimizações do compilador.

A Interface de Programação

As interfaces de programação pressupõem que as ordens do programa não precisam ser mantidas entre as operações de sincronização. É garantido que todas as operações de sincronização sejam explicitamente rotuladas ou identificadas como tal. A biblioteca de tempo de execução ou o compilador traduz essas operações de sincronização em operações adequadas de preservação de ordem exigidas pela especificação do sistema.

O sistema então garante execuções sequencialmente consistentes, embora possa reordenar as operações entre as operações de sincronização de qualquer maneira que desejar, sem interromper as dependências de um local dentro de um processo. Isso permite ao compilador flexibilidade suficiente entre os pontos de sincronização para os reordenamentos que desejar e também permite que o processador execute tantos reordenamentos quantos forem permitidos por seu modelo de memória. Na interface do programador, o modelo de consistência deve ser pelo menos tão fraco quanto o da interface de hardware, mas não precisa ser o mesmo.

Mecanismos de Tradução

Na maioria dos microprocessadores, traduzir rótulos em mecanismos de manutenção de ordem equivale a inserir uma instrução de barreira de memória adequada antes e / ou depois de cada operação rotulada como uma sincronização. Isso salvaria instruções com carregamentos / armazenamentos individuais, indicando quais pedidos cumprir e evitando instruções extras. No entanto, como as operações geralmente não são frequentes, esse não é o caminho que a maioria dos microprocessadores fez até agora.

Superando Limitações de Capacidade

Discutimos os sistemas que fornecem replicação automática e coerência em hardware apenas na memória cache do processador. Um cache de processador, sem primeiro ser replicado na memória principal local, replica os dados alocados remotamente diretamente na referência.

Um problema com esses sistemas é que o escopo da replicação local é limitado ao cache do hardware. Se um bloco for substituído da memória cache, ele deverá ser obtido da memória remota quando for necessário novamente. O principal objetivo dos sistemas discutidos nesta seção é resolver o problema da capacidade de replicação, mas ainda fornecendo coerência no hardware e na granularidade fina dos blocos de cache para eficiência.

Caches Terciários

Para resolver o problema da capacidade de replicação, um método é usar um cache de acesso remoto grande, mas mais lento. Isso é necessário para a funcionalidade, quando os nós da máquina são eles próprios multiprocessadores de pequena escala e podem simplesmente ser aumentados para desempenho. Ele também conterá blocos remotos replicados que foram substituídos da memória cache do processador local.

Arquiteturas de memória somente cache (COMA)

Em máquinas COMA, cada bloco de memória em toda a memória principal tem uma etiqueta de hardware vinculada a ele. Não há um nó fixo onde sempre há garantia de espaço alocado para um bloco de memória. Os dados migram dinamicamente ou são replicados nas memórias principais dos nós que os acessam / atraem. Quando um bloco remoto é acessado, ele é replicado na memória de atração e trazido para o cache, sendo mantido consistente em ambos os locais pelo hardware. Um bloco de dados pode residir em qualquer memória de atração e pode mover-se facilmente de um para o outro.

Reduzindo o custo do hardware

Reduzir custos significa mover algumas funcionalidades de hardware especializado para software executado no hardware existente. É muito mais fácil para o software gerenciar a replicação e a coerência na memória principal do que no cache do hardware. Os métodos de baixo custo tendem a fornecer replicação e coerência na memória principal. Para que a coerência seja controlada de forma eficiente, cada um dos outros componentes funcionais da assistência pode se beneficiar da especialização e integração de hardware.

Os esforços de pesquisa visam reduzir o custo com diferentes abordagens, como realizar o controle de acesso em hardware especializado, mas atribuindo outras atividades a software e hardware comum. Outra abordagem é realizar o controle de acesso em software e é projetada para distribuir uma abstração de espaço de endereço compartilhado coerente em nós de mercadoria e redes sem suporte de hardware especializado.

Implicações para software paralelo

O modelo de consistência de memória relaxada precisa que os programas paralelos rotulem os acessos conflitantes desejados como pontos de sincronização. Uma linguagem de programação fornece suporte para rotular algumas variáveis ​​como sincronização, que serão então traduzidas pelo compilador para a instrução de preservação de ordem adequada. Para restringir a própria reordenação dos acessos do compilador à memória compartilhada, o compilador pode usar rótulos por si mesmo.

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- Um switch é composto 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 ponto no tempo. 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. A topologia é o padrão para conectar as chaves individuais a outros elementos, como processadores, memórias e outras chaves. 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- As 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 estágios múltiplos. 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 crossbar 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 de 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 é a distância de roteamento, a dimensão deve ser maximizada e um hipercubo feito. No roteamento store-and-forward, supondo que o grau da troca e o número de links não foram um fator de custo significativo, e o número de links ou o grau de troca 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 dimensionais baixas, 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 rota 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 para 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 qualquer um dos receber, 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 de dependência geral 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, controle e armazenamento de dados.

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 cada porta 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 do 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 buffer está 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.

A velocidade dos microprocessadores aumentou em mais de um fator de dez por década, mas a velocidade das memórias commodity (DRAMs) apenas dobrou, ou seja, o tempo de acesso caiu pela metade. Portanto, a latência de acesso à memória em termos de ciclos de clock do processador aumenta por um fator de seis em 10 anos. Os multiprocessadores intensificaram o problema.

Em sistemas baseados em barramento, o estabelecimento de um barramento de alta largura de banda entre o processador e a memória tende a aumentar a latência de obtenção dos dados da memória. Quando a memória é distribuída fisicamente, a latência da rede e da interface de rede é adicionada àquela do acesso à memória local no nó.

A latência geralmente aumenta com o tamanho da máquina, à medida que mais nós implicam em mais comunicação em relação à computação, mais salto na rede para comunicação geral e provavelmente mais contenção. O principal objetivo do design de hardware é reduzir a latência do acesso aos dados, mantendo uma largura de banda alta e escalonável.

Visão geral da tolerância à latência

Como a tolerância à latência é tratada é melhor compreendida observando os recursos da máquina e como eles são utilizados. Do ponto de vista do processador, a arquitetura de comunicação de um nó para outro pode ser vista como um pipeline. Os estágios do pipeline incluem interfaces de rede na origem e no destino, bem como nos links de rede e switches ao longo do caminho. Existem também estágios no assistente de comunicação, o sistema de memória / cache local e o processador principal, dependendo de como a arquitetura gerencia a comunicação.

O problema de utilização na estrutura de comunicação da linha de base é que o processador ou a arquitetura de comunicação estão ocupados em um determinado momento e, no pipeline de comunicação, apenas um estágio está ocupado por vez, pois a única palavra sendo transmitida faz seu caminho da origem ao destino. O objetivo da tolerância à latência é sobrepor o uso desses recursos o máximo possível.

Tolerância de latência na passagem explícita de mensagens

A transferência real de dados na passagem de mensagens é normalmente iniciada pelo remetente, usando uma operação de envio. Uma operação de recebimento não motiva por si só os dados a serem comunicados, mas sim copia os dados de um buffer de entrada no espaço de endereço do aplicativo. A comunicação iniciada pelo receptor é feita através da emissão de uma mensagem de solicitação ao processo que é a fonte dos dados. O processo então envia os dados de volta por meio de outro envio.

Uma operação de envio síncrono tem latência de comunicação igual ao tempo que leva para comunicar todos os dados na mensagem ao destino e o tempo para processamento de recebimento e o tempo para uma confirmação ser retornada. A latência de uma operação de recepção síncrona é sua sobrecarga de processamento; que inclui a cópia dos dados para o aplicativo e a latência adicional caso os dados ainda não tenham chegado. Gostaríamos de ocultar essas latências, incluindo overheads, se possível, em ambas as extremidades.

Tolerância de latência em um espaço de endereçamento compartilhado

A comunicação da linha de base é por meio de leituras e gravações em um espaço de endereço compartilhado. Por conveniência, é chamada de comunicação de leitura e gravação. A comunicação iniciada pelo receptor é feita com operações de leitura que resultam no acesso aos dados da memória ou cache de outro processador. Se não houver cache de dados compartilhados, a comunicação iniciada pelo remetente pode ser feita por meio de gravações nos dados que são alocados em memórias remotas.

Com a coerência do cache, o efeito das gravações é mais complexo: a gravação leva ao remetente ou a comunicação iniciada pelo receptor depende do protocolo de coerência do cache. Iniciada pelo receptor ou pelo remetente, a comunicação em um espaço de endereço compartilhado de leitura e gravação suportado por hardware é naturalmente refinada, o que torna a latência de tolerância muito importante.

Bloquear transferência de dados em um espaço de endereçamento compartilhado

Em um espaço de endereço compartilhado, seja por hardware ou software, a união de dados e o início de transferências de bloco podem ser feitos explicitamente no programa do usuário ou de forma transparente pelo sistema. As transferências de bloco explícitas são iniciadas pela execução de um comando semelhante a um envio no programa do usuário. O comando send é explicado pelo assistente de comunicação, que transfere os dados de uma maneira pipeline do nó de origem para o destino. No destino, o assistente de comunicação puxa as palavras de dados da interface de rede e as armazena nos locais especificados.

Existem duas diferenças principais na passagem de mensagens de envio e recebimento, ambas surgem do fato de que o processo de envio pode especificar diretamente as estruturas de dados do programa onde os dados devem ser colocados no destino, uma vez que esses locais estão no espaço de endereço compartilhado .

Processamento de eventos passados ​​de longa latência em um espaço de endereçamento compartilhado

Se a operação de memória não for bloqueada, um processador pode prosseguir após uma operação de memória para outras instruções. Para gravações, isso geralmente é bastante simples de implementar se a gravação for colocada em um buffer de gravação e o processador continuar enquanto o buffer se encarrega de emitir a gravação para o sistema de memória e rastrear sua conclusão conforme necessário. A diferença é que, ao contrário de uma gravação, uma leitura geralmente é seguida muito em breve por uma instrução que precisa do valor retornado pela leitura.

Pré-comunicação em um espaço de endereçamento compartilhado

A pré-comunicação é uma técnica que já foi amplamente adotada em microprocessadores comerciais e sua importância tende a aumentar no futuro. Uma instrução de pré-busca não substitui a leitura real do item de dados, e a própria instrução de pré-busca deve ser sem bloqueio, se quiser atingir seu objetivo de ocultar a latência por sobreposição.

Nesse caso, como os dados compartilhados não são armazenados em cache, os dados pré-buscados são trazidos para uma estrutura de hardware especial chamada buffer de pré-busca. Quando a palavra é realmente lida em um registrador na próxima iteração, ela é lida na cabeça do buffer de pré-busca, e não na memória. Se a latência para ocultar fosse muito maior do que o tempo para calcular a iteração de loop único, faríamos a pré-busca de várias iterações adiante e haveria potencialmente várias palavras no buffer de pré-busca por vez.

Multithreading em um espaço de endereçamento compartilhado

Em termos de ocultar diferentes tipos de latência, multithreading suportado por hardware é talvez a técnica versátil. Ele tem as seguintes vantagens conceituais sobre outras abordagens -

• Não requer análise de software especial ou suporte.

• Como ele é chamado dinamicamente, ele pode lidar com situações imprevisíveis, como conflitos de cache, etc., assim como outras previsíveis.

• Como a pré-busca, ele não altera o modelo de consistência de memória, pois não reordena os acessos dentro de um encadeamento.

• Embora as técnicas anteriores tenham como objetivo ocultar a latência de acesso à memória, o multithreading pode potencialmente ocultar a latência de qualquer evento de longa latência com a mesma facilidade, contanto que o evento possa ser detectado no tempo de execução. Isso inclui sincronização e latência de instrução também.

Essa tendência pode mudar no futuro, pois as latências estão se tornando cada vez mais longas em comparação com as velocidades do processador. Além disso, com microprocessadores mais sofisticados que já fornecem métodos que podem ser estendidos para multithreading, e com novas técnicas de multithreading sendo desenvolvidas para combinar multithreading com paralelismo de nível de instrução, essa tendência certamente parece estar passando por alguma mudança no futuro.