Embed Size (px)
Citation preview
UNIVERSIDADE ESTADUAL DE FEIRA DE SANTANA – UEFS
Daniel dos Anjos Costa
PROJETO DE UM ROTEADOR COM ROTEAMENTO SEMI-
ADAPTATIVO PARA REDES EM CHIP
FEIRA DE SANTANA
2010
Daniel dos Anjos Costa
PROJETO DE UM ROTEADOR COM ROTEAMENTO SEMI-
ADAPTATIVO PARA REDES EM CHIP
Monografia apresentada à disciplina Trabalho
de Conclusão de Curso do Curso de
Graduação em Engenharia da Computação da
Universidade Estadual de Feira de Santana
como requisito parcial para obtenção do Grau
de Engenheiro da Computação.
Prof. Orientador: Angelo Amancio Duarte
Feira de Santana
DANIEL DOS ANJOS COSTA
PROJETO DE UM ROTEADOR COM ROTEAMENTO SEMI-
ADAPTATIVO PARA REDES EM CHIP
Monografia apresentada à disciplina Trabalho de Conclusão de Curso ao Curso de Engenharia
da Computação da Universidade Estadual de Feira de Santana como requisito parcial para
obtenção do Grau de Engenheiro da Computação.
_________________________________________________________
Doutor Angelo Amâncio Duarte
Professor do Departamento de Tecnologia da UEFS
Orientador
__________________________________________________________
Doutor Anfranserai Morais Dias
Professor do Departamento de Tecnologia da UEFS
__________________________________________________________
Doutor Wagner Luiz Alves de Oliveira
Professor do Departamento de Tecnologia da UEFS
Feira de Santana, _______ de _______________ de _______.
Dedico a todos que de uma forma ou de outra contribuíram para a confecção deste trabalho. Em especial a Deus, a minha família, ao professor Angelo Duarte e outros professores e amigos do curso de Graduação em Engenharia da Computação da Universidade Estadual de Feira de Santana.
RESUMO
As principais conquistas tecnológicas do Século XX se deram no campo da distribuição de
informações, do processamento e mobilidade. Entra neste cenário a tecnologia de fabricação
de circuitos integrados (CIs), que evoluiu ao ponto de dificultar alguns dos principais
paradigmas subjacentes ao projeto de sistemas digitais complexos. Dentre estes, um dos mais
relevantes, é o uso de barramento como meio de interconexão intra-chip. As redes-em-chip ou
NoCs (Networks-on-Chip) apresentam-se como a melhor alternativa para a interconexão de
componentes nos futuros sistemas integrados em um único chip. Trata-se de arquiteturas de
comunicação que adaptam conceitos oriundos de redes de computadores e de sistemas
paralelos e distribuídos para o ambiente intra-chip. O presente trabalho contribui com uma
proposta de arquitetura para um roteador toro, com algoritmo de roteamento semi-adaptativo.
Além dos detalhes arquiteturais, este trabalho apresenta resultados das simulações e dos testes
de validação do projeto.
Palavras chave - Redes-em-Chip. Sistemas Integrados. NoCs.
ABSTRACT
The major technological achievements of the twentieth century occurred in the field of
distributing of information, processing and mobility. It comes in the scenery the
manufacturing technology of integrated circuits (ICs), which evolved to the point of hindering
some of the major paradigms underlying the design of complex digital systems. Among these
is the use of bus for intra-chip interconnections. Networks-on-chip, or (NoCs) are the best
alternative for interconnecting components in the future integrated systems on a single chip.
They are communication architectures that adapting concepts from computer networks and
parallel and distributed systems into the intra-chip domain. This work proposed an
architecture for a torus router, with a semi-adaptive algorithm routing. Besides the
architectural details, this work presents simulations results and validation tests of the project.
Keywords - Network-on-Chip. Integrated Systems. NoCs.
LISTA DE FIGURAS
FIGURA 1 - ILUSTRAÇÃO DE UMA REDE EM CHIP. ....................................................................... 15
FIGURA 2 - ESTRUTURA DE UMA MENSAGEM. ............................................................................ 16
FIGURA 3 - (A) FORMATO DE UMA REDE GRADE 3 X 3, (B) FORMATO DE UMA REDE TORÓIDE (C)
FORMATO DE UMA REDE HIPERCUBO. FONTE: (ZEFERINO, 2003), (CARARA, 2004). .... 17
FIGURA 4 - CONTROLE DE FLUXO BASEADO EM SLACK BUFFER. FONTE: (MELLO, 2002),
(CARARA, 2004). ............................................................................................................ 19
FIGURA 5 - ESTRUTURA DE UM ROTEADOR, COM DESTAQUE PARA O MÓDULO DE CONTROLE DE
CHAVEAMENTO. ................................................................................................................. 19
FIGURA 6 – ESTRATÉGIA DA FIFO. ............................................................................................ 22
FIGURA 7 - ESTRATÉGIA SAFC. ................................................................................................ 22
FIGURA 8 - ESTRATÉGIA SAMQ. ............................................................................................... 23
FIGURA 9 - ESTRATÉGIA DAMQ. .............................................................................................. 24
FIGURA 10 - OITO POSSÍVEIS MUDANÇAS DE DIREÇÃO PARA REDES COM TOPOLOGIA GRADE OU
TORO.................................................................................................................................. 25
FIGURA 11 - (A) AS RETAS CONTÍNUAS REPRESENTAM OS CAMINHOS PERMITIDOS E AS RETAS
PONTILHADAS, OS NÃO PERMITIDOS; (B) SEIS EXEMPLOS DE MOVIMENTAÇÃO DOS PACOTES
NA REDE............................................................................................................................. 26
FIGURA 12 - (A) AS RETAS CONTÍNUAS (CAMINHOS PERMITIDOS) E, AS RETAS PONTILHADAS
(NÃO PERMITIDOS); (B) DOIS EXEMPLOS DE MOVIMENTAÇÃO DOS PACOTES NA REDE
ROTEADOS PELO ALGORITMO WEST-FIRST. ......................................................................... 27
FIGURA 13 - (A) AS RETAS CONTÍNUAS (CAMINHOS PERMITIDOS) E AS RETAS PONTILHADAS (NÃO
PERMITIDOS). (B) QUATRO EXEMPLOS DE MOVIMENTAÇÃO DOS PACOTES NA REDE
ROTEADOS PELO ALGORITMO NORTH-LAST. ........................................................................ 28
FIGURA 14 - (A) AS RETAS CONTÍNUAS (CAMINHOS PERMITIDOS) E AS RETAS PONTILHADAS (NÃO
PERMITIDOS); (B) QUATRO EXEMPLOS DE MOVIMENTAÇÃO DOS PACOTES NA REDE
ROTEADOS PELO ALGORITMO NEGATIVE-FIRST. .................................................................. 29
FIGURA 15 - ABORDAGENS PARA IMPLEMENTAÇÃO DE ÁRBITROS: (A) CENTRALIZADA; (B)
DISTRIBUIDA. FONTE: (ZEFERINO, 2003). ....................................................................... 30
FIGURA 16 - PORTAS DE COMUNICAÇÃO DO ROTEADOR. ........................................................... 32
FIGURA 17 - VISÃO EM ALTO NÍVEL DA ARQUITETURA DO ROTEADOR. ...................................... 33
FIGURA 18 - ILUSTRAÇÃO DA ARQUITETURA DE UM TERMINAL DO ROTEADOR. ......................... 34
FIGURA 19 - ARRUMAÇÃO DOS BITS DO PACOTE PARA: (A) O CABEÇALHO; (B) O CONTEÚDO DA
MENSAGEM; (C) E O TERMINADOR. ..................................................................................... 35
FIGURA 20 - DIAGRAMA DE SEQÜÊNCIA ILUSTRANDO OS PASSOS DA SINCRONIZAÇÃO NO
MOMENTO DA TRANSFERÊNCIA. ......................................................................................... 36
FIGURA 21 - ARQUITETURA DO ÁRBITRO DE ENTRADA. .................................................... 38
FIGURA 22 - ILUSTRAÇÃO DA ARQUITETURA DO MÓDULO DE ROTEAMENTO. .................. 38
FIGURA 23 - ORGANIZAÇÃO DOS BITS DE ENDEREÇO. ................................................................ 39
FIGURA 24 - ORGANIZAÇÃO DOS BITS DE ROTA. ........................................................................ 39
FIGURA 25 - ILUSTRAÇÃO DA ARQUITETURA DO ÁRBITRO DE SAÍDA. ........................................ 41
FIGURA 26 - ARQUITETURA DA MATRIZ CROSSBAR. ............................................................ 42
FIGURA 27 - SIGNIFICADO DOS 11 BITS QUE PASSAM PELO CROSSBAR 5X5. ............................ 43
FIGURA 28 - ARQUITETURA DO AMBIENTE DE SIMULAÇÃO PARA OS EXEMPLOS I, II E III. ......... 44
FIGURA 29 - ARQUITETURA DO AMBIENTE DE SIMULAÇÃO PARA A SIMULAÇÃO IV. .................. 46
FIGURA 30 - MOMENTO DE SINCRONIZAÇÃO (SINAIS DE ENTRADA VAL E ACK) E ENTRADA DO
PACOTE PELO TERMINAL LOCAL DO ROTEADOR. ............................................................. 47
FIGURA 31 - MOMENTO DE SINCRONIZAÇÃO (SINAIS DE SAÍDA VAL E ACK) E SAÍDA DO PACOTE
PELO TERMINAL LESTE DO ROTEADOR. ............................................................................ 48
FIGURA 32 - SIMULAÇÃO DE CONGESTIONAMENTO COM O CORTE DA CONEXÃO NOS MÓDULOS
DE SAÍDA DO TERMINAL LESTE. ................................................................................... 48
FIGURA 33 - MOMENTO DE SINCRONIZAÇÃO (SINAIS DE ENTRADA VAL E ACK), ENTRADA DO
PACOTE PELO TERMINAL LOCAL DO ROTEADOR. ............................................................. 49
FIGURA 34 - MOMENTO DE SINCRONIZAÇÃO (SINAIS DE SAÍDA VAL E ACK) E SAÍDA DO PACOTE
PELO TERMINAL OESTE DO ROTEADOR. ........................................................................... 50
FIGURA 35 – ENTRADA DO PACOTE PELO TERMINAL LOCAL, E IMEDIATAMENTE DEPOIS,
DESCARTE DO MESMO PACOTE. .......................................................................................... 51
FIGURA 36 - MOMENTO QUE O PACOTE ENTRA NA REDE, PELO TERMINAL LOCAL DO
ROTEADOR (0, 1), E SAÍ PELO TERMINAL LESTE. .......................................................... 52
FIGURA 37 - MOMENTO QUE O PACOTE ENTRA PELO TERMINAL OESTE DO ROTEADOR (1, 1),
E SAÍ PELO TERMINAL LESTE. ...................................................................................... 52
FIGURA 38 - MOMENTO QUE O PACOTE ENTRA PELO TERMINAL OESTE DO ROTEADOR (2, 1),
E SAÍ PELO TERMINAL NORTE. ..................................................................................... 52
FIGURA 39 - MOMENTO QUE O PACOTE ENTRA PELO TERMINAL SUL DO ROTEADOR (2, 2), E
SAÍ DA REDE PELO TERMINAL LOCAL. ......................................................................... 53
FIGURA 40 - RESUMO DO PERCURSO DO PACOTE PELA REDE 3X3. .............................................. 53
LISTA DE TABELAS
TABELA 1 - MUDANÇAS DE DIREÇÃO ILUSTRADAS NA FIGURA 10. ............................................ 25
TABELA 2 - TABELA DE PERCURSOS DOS EXEMPLOS DA FIGURA 11B. ........................................ 26
TABELA 3 - TABELA DE PERCURSOS DOS EXEMPLOS DA FIGURA 12B. ........................................ 27
TABELA 4 - TABELA DE PERCURSOS DOS EXEMPLOS DA FIGURA 13B. ........................................ 28
TABELA 5 - TABELA DE PERCURSOS DOS EXEMPLOS DA FIGURA 14B. ........................................ 29
SUMÁRIO
1 INTRODUÇÃO .............................................................................................................. 13
2 FUNDAMENTAÇÃO TEÓRICA ................................................................................. 15
2.1 TOPOLOGIAS DE REDES EM CHIP ............................................................................ 16
2.2 CONTROLE DE FLUXO ................................................................................................ 17
2.2.1 CONTROLE DE FLUXO HANDSHAKE .................................................................... 17
2.2.2 CONTROLE DE FLUXO BASEADO EM CRÉDITOS ............................................. 18
2.2.3 CONTROLE DE FLUXO BASEADO EM SLACK BUFFER .................................... 18
2.3 CHAVEAMENTO ........................................................................................................... 19
2.4 MEMORIZAÇÃO ............................................................................................................ 21
2.5 ALGORITMOS DE ROTEAMENTO ............................................................................. 24
2.5.1 ALGORITMO DE ROTEAMENTO XY..................................................................... 26
2.5.2 ALGORITMO DE ROTEAMENTO WEST-FIRST .................................................... 27
2.5.3 ALGORITMO DE ROTEAMENTO NORTH-LAST ................................................... 28
2.5.4 ALGORITMO DE ROTEAMENTO NEGATIVE-FIRST ............................................ 29
2.6 ARBITRAGEM ................................................................................................................ 30
3 DESENVOLVIMENTO ................................................................................................. 32
3.1 TERMINAIS DO ROTEADOR ....................................................................................... 33
3.2 ÁRBITRO DE ENTRADA .............................................................................................. 37
3.3 MÓDULO DE ROTEAMENTO ...................................................................................... 38
3.4 ÁRBITRO DE SAÍDA ..................................................................................................... 41
3.5 MATRIZ CROSSBAR ...................................................................................................... 42
4 TESTES FUNCIONAIS ................................................................................................. 44
4.1 PRIMEIRA SIMULAÇÃO .............................................................................................. 46
4.2 SEGUNDA SIMULAÇÃO .............................................................................................. 48
4.3 TERCEIRA SIMULAÇÃO .............................................................................................. 50
4.4 QUARTA SIMULAÇÃO ................................................................................................. 51
5 CONSIDERAÇÕES FINAIS ......................................................................................... 54
6 REFERÊNCIAS ............................................................................................................. 56
13
1 INTRODUÇÃO
Podemos ver durante a evolução do Homem, que cada um dos três séculos anteriores
foi basicamente dominado por uma única tecnologia (TANENBAUM, 1994). O Século XVIII
foi à época dos grandes sistemas mecânicos que acompanharam a Revolução Industrial. O
Século XIX foi à era das máquinas a vapor. As principais conquistas tecnológicas do Século
XX se deram no campo da aquisição, do processamento e da distribuição de informações.
Essa nova tendência de tecnologia leva o Homem a desenvolver novos equipamentos
com cada vez mais poder de processamento, robustez e mobilidade. Devido a um mercado
capitalista bastante competitivo, os dispositivos digitais tem se tornado cada vez mais
complexos e com mais funcionalidades. Desde o inicio da eletrônica digital e da indústria de
computadores, houve uma tendência persistente e consistente de reduzir o tamanho dos
circuitos eletrônicos digitais.
As novas tecnologias de fabricação de circuitos integrados têm permitido o projeto de
sistemas completos em um único chip, os quais são denominados Systems-on-Chip (SoCs).
Sua metodologia de projeto baseia-se no reuso de blocos previamente projetados e
verificados. Esses componentes reutilizáveis são denominados núcleos (ou blocos de
propriedade intelectual – IP Blocks). Atualmente, são utilizadas duas abordagem para
interconexão dos IP Blocks: canais ponto-a-ponto dedicados e canais multiponto
compartilhados, conhecido como barramento (ZEFERINO, 2003).
As arquiteturas de comunicação baseadas no barramento, que estão na maioria dos
SoCs, não atenderão às demandas de desempenho desses sistemas. Como solução, são
apresentadas as Redes em Chips ou Networks-on-Chip (NoCs), que oferecem melhor solução
para desempenho e comunicação.
As NoCs consistem em arranjos de roteadores e enlaces, que interligam os núcleos do
SoC e, esses núcleos se comunicam através do envio e do recebimento de mensagens pela
rede. As NoCs tem como principal vantagem o uso do paralelismo na comunicação. Essa nova
abordagem aplica os conceitos das redes de interconexão para computadores paralelos, sendo
que os núcleos são considerados como os computadores, os quais são interconectados através
de uma rede formada por roteadores e canais ponto a ponto.
Como o contexto apresentado é bastante amplo, este trabalho foca na construção de
um roteador para redes em chip com roteamento semi-adaptativo. Esse roteador terá na sua
14
implementação um algoritmo que é capaz de encaminhar pacotes pela rede, podendo até
mudar suas decisões de roteamento para refletir mudanças na topologia ou no tráfego.
O resultado final do trabalho foi testado individualmente e, em uma rede com
topologia toróide 3x3. O roteador implementado, foi desenvolvido em Verilog (linguagem de
descrição de hardware) e sua verificação funcional foi feita em SystemVerilog (linguagem de
desenvolvimento, verificação e testbench de hardware). O software de simulação foi o
ModelSim ALTERA STARTER EDITION 6.4a, da Mentor Graphics Corporation.
Este trabalho está dividido da seguinte maneira: o segundo capítulo contém a
Fundamentação Teórica, dando foco às arquiteturas de rede em chip e aos algoritmos de
roteamento; no capítulo três está o Desenvolvimento com a arquitetura do roteador
implementado; o capítulo quatro apresenta alguns Testes Funcionais do roteador; e finalmente
no capítulo cinco as Considerações Finais do trabalho.
15
2 FUNDAMENTAÇÃO TEÓRICA
Este capítulo apresenta os conceitos teóricos envolvidos no trabalho, que auxiliou na
construção do roteador. Ele abrange boa parte das arquiteturas propostas na literatura para
redes em chip.
As redes em chip são compostas por componentes de processamento e chaveamento.
Por exemplo, na rede ilustrada na Figura 1 podemos ver os componentes de chaveamento
(representado na figura pela letra R de roteador), que possui ligações para quatro outros
dispositivos de chaveamento vizinhos e, para um núcleo local (representado na figura pela
letra N). Os núcleos são responsáveis pela execução das tarefas do sistema, enquanto que os
componentes de chaveamento, também chamados de roteadores, são responsáveis pela
transferência de mensagens entre os núcleos.
Figura 1 - Ilustração de uma rede em chip.
Em uma rede em chip, os roteadores e os núcleos nela conectados são interligados por
meio de canais ponto a ponto unidirecionais e assíncronos (ZEFERINO, 2003). Os canais são
fios que transportam o conteúdo da mensagem, a banda lateral e os sinais de sincronismo. A
banda lateral é utilizada para transferir informações adicionais, como os bits de
enquadramento da mensagem, bits de paridade ou bits de sinalização de erro.
Cada mensagem é constituída por três partes: um cabeçalho (header), o corpo da
mensagem (payload), e por fim um terminador (trailer). O cabeçalho contém informações que
ajudarão no encaminhamento da mensagem pela rede. O corpo da mensagem é o conteúdo
16
que deve ser transferido (conhecido também como carga útil), e o terminador sinaliza o final
da mensagem. Ele pode ser até a última palavra da carga útil, desde que haja alguma
informação adicional de enquadramento, como um bit especial, que só é ativado no final da
mensagem (ZEFERINO, 2003). Na Figura 2 está ilustrada a estrutura de uma mensagem.
Figura 2 - Estrutura de uma mensagem.
Geralmente, as mensagens são quebradas e transmitidas em pacotes. Um pacote é
constituído por uma seqüência de flits (flow control unit), cuja largura depende da largura
física do canal. Um flit é a menor unidade de dados, sobre a qual é realizado o controle de
fluxo (CARARA, 2004), (ZEFERINO, 2003).
Uma rede em chip pode ser caracterizada pela sua topologia e pelas estratégias
utilizadas para controle de fluxo, chaveamento, memorização, roteamento e arbitragem. Essas
características são discutidas a seguir.
2.1 TOPOLOGIAS DE REDES EM CHIP
Assim como uma rede de interconexão para computadores paralelos, uma rede em
chip é caracterizada pela sua topologia e pelos mecanismos de comunicação utilizados. A
representação desse tipo de estrutura é por um grafo G(N, C), onde, N representa o conjunto
de nós da rede e, C representa o conjunto de canais de comunicação, representando o conjunto
de arestas do grafo (ZEFERINO, 2003). As redes são classificadas em diretas e indiretas.
Nas redes diretas, cada dispositivo de chaveamento possui um dispositivo de
processamento associado, e esse par pode ser visto como um elemento único dentro do
sistema, conhecido também por nó da rede (CARARA, 2004). Ao contrário das redes diretas,
as redes indiretas os roteadores não são acoplados a processadores, formando um único nó
(ZEFERINO, 2003). Em redes indiretas, cada nó de chaveamento possui um conjunto de
portas bidirecionais para ligações com outros nós de chaveamento e/ou com os nós de
17
processamento, e somente alguns nós de chaveamento têm ligação com os de processamento.
A topologia da rede é definida pela estrutura de interconexão desses nós.
As topologias de redes diretas mais utilizadas são a grade (ou malha), toróide e
hipercubo, todas ilustradas na Figura 3.
Figura 3 - (a) Formato de uma rede grade 3 x 3, (b) formato de uma rede toróide (c) formato de uma
rede hipercubo. Fonte: (ZEFERINO, 2003), (CARARA, 2004).
2.2 CONTROLE DE FLUXO
O controle de fluxo lida com a alocação dos recursos (filas e canais) necessários para
uma mensagem avançar pela rede, efetuando a regulação de tráfego nos canais (CULLER,
1999). Serve, para fazer o sincronismo entre dois roteadores durante uma transferência,
ajustando a taxa de saída de um roteador origem, à taxa de entrada de um roteador destino,
evitando, assim, a perda de pacotes durante a transmissão (CARARA, 2004).
Os métodos mais conhecidos para controle de fluxo são: handshake, baseado em
crédito e baseado em Slack Buffer. A implementação desses métodos depende da estrutura do
enlace, mas o procedimento é semelhante.
2.2.1 Controle de fluxo handshake
A característica desse protocolo é que ele necessita pelo menos dois ciclos de clock
para a transmissão de cada flit (CARARA, 2004). Toda vez que o transmissor deseja
18
transmitir uma mensagem, ele emite um sinal indicando que tem dado válido na linha de
transmissão. O receptor percebendo esse sinal, verifica se tem condição de armazenar esse
dado, caso tenha, ele armazena o dado e emite um outro sinal indicando que o dado está
armazenado. O transmissor mantém o dado na linha de transmissão até receber a confirmação
de armazenamento, recebendo a confirmação, ele envia o próximo obedecendo mesmo
procedimento.
2.2.2 Controle de fluxo baseado em créditos
No controle de fluxo baseado em crédito, o transmissor informa ao receptor (por um
sinal de controle), que tem dados válidos a serem transferidos na linha de transmissão. O
receptor percebendo essa solicitação verifica se tem condição de armazenar os dados, caso
tenha, ele ativa o sinal de credito, simbolizando que está preparado para recebê-los. Enquanto
o receptor tiver espaço para armazenar dados, ele mantém o sinal de credito ativo (BOLOTIN,
2004), (CARARA, 2004). O sinal de credito é desativado quando o buffer do receptor fica
cheio, logo, transmissor mantém o dado na linha de transmissão até o receptor indicar,
novamente através do sinal de crédito, que está apto a receber os dados.
2.2.3 Controle de fluxo baseado em Slack Buffer
Também chamado de controle de fluxo on/off, trata-se de uma abordagem alternativa
para o controle de fluxo baseado em crédito. O buffer pode ser visto como um reservatório
com marcas de nível alto e baixo. Essas duas marcas indicam o limite máximo e o limite
mínimo de armazenamento, respectivamente. Quando o buffer do receptor estiver na região
abaixo da marca de nível baixo, ele sinaliza ao transmissor (com o sinal GO) que pode enviar
dados, pois ele tem espaço para armazená-los. De maneira análoga, quando o buffer do
receptor estiver em nível alto, o receptor ativa o sinal de STOP, informando que a
transferência tem que parar até o buffer alcançar o nível baixo, conforme ilustrado na Figura
4.
19
Figura 4 - Controle de fluxo baseado em slack buffer. Fonte: (MELLO, 2002).
Sinais redundantes de GO podem ser enviados em qualquer lugar abaixo da marca de
nível alto, enquanto os sinais de STOP podem ser enviados em qualquer lugar acima da marca
de nível baixo, sem nenhum efeito prejudicial (CARARA, 2004).
2.3 CHAVEAMENTO
O chaveamento é o mecanismo interno do roteador, que define a forma pela qual os
dados são transferidos de um canal de entrada para um dos seus canais de saída. Na Figura 5
está ilustrado um roteador com destaque a estrutura de chaveamento.
Figura 5 - Estrutura de um roteador, com destaque para o módulo de controle de chaveamento.
20
Existem dois métodos básicos utilizados para a transferência dos dados, que são:
chaveamento por circuito e chaveamento por pacotes.
No método chaveamento por circuito, é estabelecido um caminho completo entre o
roteador de origem e o roteador de destino, antes de iniciar do envio da mensagem (BASTOS,
2006). Para estabelecer esse caminho, inicialmente, é inserido na rede o cabeçalho da
mensagem com o endereço do destinatário e, alguns sinais de controle. Esse cabeçalho avança
pela rede reservando canais físicos para o estabelecimento do circuito. Quando o caminho é
estabelecido, a mensagem pode ser enviada, sendo que qualquer outro pedido de comunicação
que utilize os canais alocados, não será aceito. O caminho somente é desfeito quando toda a
mensagem chegar ao seu destino.
A idéia básica do chaveamento por pacotes, é que a mensagem tem que ser dividida
em pequenos pacotes. Observando o cabeçalho do pacote, o roteador decide para onde o
enviar, não existindo um caminho pré-definido. Em relação ao chaveamento por circuito, a
grande vantagem desse método, é que o canal só permanece ocupado enquanto o pacote está
sendo transferido, e a desvantagem é a necessidade de buffers para o armazenamento
temporário de pacotes.
Os modos mais usados de chaveamento de pacotes são: store-and-forward, virtual cut-
through e wormhole.
• Store-and-forward - O modo de chaveamento store-and-forward garante que todo
pacote será recebido e armazenado por inteiro, antes de ser enviado ao próximo
roteador (BASTOS, 2006). Sua principal vantagem é a simplicidade, pois
tipicamente é utilizado um buffer FIFO para armazenamento temporário.
Entretanto, como desvantagem, essa política pode criar maior latência na rede e os
pacotes têm que ter tamanhos menores que o tamanho máximo do buffer.
• Virtual cut-through - É um aperfeiçoamento do modo store-and-forward do ponto
de vista de eficiência. Sua vantagem é a redução da latência na comunicação. O
pacote pode ser repassado adiante, logo que o roteador seguinte confirmar que tem
condição de recebê-lo por inteiro (MELLO, 2006).
• Wormhole – O modo wormhole visa reduzir a quantidade de memória para
armazenar pacotes em um roteador. Os pacotes são divididos em pedaços menores
denominados flits que trafegam pela rede em modo pipeline (BASTOS, 2006).
Como a informação de roteamento é incluída no flit de cabeçalho, os flits do
21
conteúdo da mensagem devem seguir os flits de cabeçalho através da rede, logo, os
flits do conteúdo da mensagem, ficam armazenados ao longo do trajeto pela rede,
por essa razão, se diz que os flits trafegam em modo pipeline.
A grande vantagem da utilização desse modo de chaveamento é a possibilidade de
construção de roteadores pequenos e rápidos, pois os requisitos de buffers são
menores que os dos modos anteriores (ZEREFINO, 2003). A desvantagem é que
se o flit do cabeçalho ficar bloqueado em um roteador, conseqüentemente
bloqueará um número arbitrário de roteadores por onde ele passou. Outra
desvantagem é a possível ocorrência de deadlock.
2.4 MEMORIZAÇÃO
Nas arquiteturas com chaveamento por pacotes, o roteador deve garantir o
armazenamento temporário dos pacotes destinados às saídas que já estejam sendo utilizadas,
com outros pacotes. Para o caso ideal todos os roteadores teriam capacidade de
armazenamento infinita, garantindo que nenhum pacote fosse bloqueado por outro enquanto
sua saída não fosse liberada. Todavia, a memória do roteador é limitada e, o bloqueio de um
pacote pode ser inevitável.
A organização dos buffers dentro do roteador tem um impacto significativo no seu
desempenho. Há várias estratégias de memorização, dentre os quais pode-se destacar o
armazenamento na entrada, esse tipo de armazenamento consiste em inserir buffers
independentes em cada uma das portas de entrada do roteador (BASTOS, 2006). As formas
mais comuns de implementação, estão descritas a seguir: First In First Out (FIFO), Statically
Allocated, Fully Connected (SAFC), Statically Allocated Multi-Queue (SAMQ) e
Dynamically-Allocated, Multi-Queue (DAMQ).
A estratégia FIFO é a que possui um funcionamento mais simples e de menor custo,
pois os buffers têm características de fila, ou seja, os dados são escritos e lidos na mesma
ordem. (BASTOS, 2006). Mas essa estratégia tem o problema do bloqueio da cabeça da fila
(Head Of Line ou HOL), onde um pacote bloqueado por necessitar de uma saída em uso (por
outro pacote) impede que outros pacotes, atrás dele, avancem para uma porta de saída
22
qualquer que esteja disponível naquele instante (CULLER, 1999). A estratégia FIFO é
ilustrada na Figura 6.
Figura 6 – Estratégia da FIFO.
A estratégia SAFC ameniza o bloqueio da cabeça da fila dividindo o buffer de entrada
em N slots que possuam tamanho igual a 1/N do tamanho do buffer original (ZEFERINO,
2003). A desvantagem da SAFC é o custo adicional referente ao controle da crossbar, que
passará a ter uma estrutura de N2xN, e ao controle dos N buffers por porta de entrada. Além
disso, a taxa de utilização dos buffers é limitada a 1/N do espaço de armazenamento total. Na
Figura 7 é ilustrado o esquema da estratégia SAFC. O controle de fluxo torna-se mais
complexo, pois é realizado individualmente para os N slots, de cada fila de entrada.
Figura 7 - Estratégia SAFC.
23
O contrário do modelo SAFC, a estratégia SAMQ foi proposta para simplificar o
crossbar que era de N2xN agora ficará NxN (ZEFERINO, 2003). Isso é possível adicionando
multiplexadores às saídas dos buffers de entrada direcionadas à mesma porta, conforme
ilustrado na Figura 8. Alguns problemas da estratégia SAFC são eliminados quando se utiliza
a SAMQ, já que o custo do crossbar é reduzido. Entretanto, os outros problemas relacionados
ao modelo SAFC continuam, como por exemplo, os espaços alocados estaticamente.
Figura 8 - Estratégia SAMQ.
A estratégia DAMQ propõe espaços de armazenamento associado a uma porta de
entrada e, particionando de forma dinâmica entre as portas de saída, conforme a demanda dos
pacotes recebidos (BASTOS, 2006). A Figura 9 ilustra essa estratégia. As vantagens desse
modelo é que ele evita o problema do bloqueio do HOL e, o controle de fluxo é mais simples
que das estratégias SAFC e SAMQ. Como desvantagem, cita-se a implementação física mais
complexa para o gerenciamento dos buffers, pois sua implementação é baseada na idéia de
listas encadeadas.
24
Figura 9 - Estratégia DAMQ.
2.5 ALGORITMOS DE ROTEAMENTO
O roteamento é o processo que determina para qual roteador vizinho a mensagem deve
ser enviada, baseando-se no endereço do cabeçalho da mesma. Um dos objetivos mais
importantes, em relação ao algoritmo de roteamento, é garantir que ele evite problemas como:
livelock e deadlock.
O livelock é um problema do mecanismo de roteamento. Esse problema ocorre quando
o pacote mantém-se trafegando permanentemente pela rede, porque os canais necessários para
que ele chegue ao roteador de destino, encontra-se sempre indisponível (ZEFERINO, 2003).
Geralmente esse problema ocorre em algoritmos tolerantes a falhas, pois geram caminhos
não-mínimos.
O deadlock ocorre quando há uma dependência cíclica na rede. Cada mensagem
garante a alocação de um canal e requer o uso de outro canal já alocado a outra mensagem. O
deadlock é o mais grave de todos os problemas descritos anteriormente, pois, além de impedir
que uma mensagem chegue ao seu destinatário, ele pode levar à paralisação da rede
(TANENBAUM, 2000).
25
Em topologia de grade e toro, um pacote pode seguir por quatro possíveis direções:
Leste (East), Oeste (West), Norte (North) e Sul (South). No caminho percorrido pela
mensagem, oito possíveis mudanças de direção podem ser tomadas, como mostra a Figura 10.
Na Tabela 1 podemos acompanhar as mudanças de direção ilustradas na Figura 10.
Figura 10 - Oito possíveis mudanças de direção para redes com topologia grade ou toro.
Tabela 1 - Mudanças de direção ilustradas na Figura 10.
Numeração Mudança de direção 1 Oeste – Sul 2 Norte – Oeste 3 Leste – Norte 4 Sul – Leste 5 Norte – Leste 6 Leste – Sul 7 Sul – Oeste 8 Oeste – Norte
Se pelo menos duas mudanças de direção forem proibidas, pode-se dizer que o
algoritmo é livre de deadlock (ZEFERINO, 2003).
Nas próximas seções serão apresentados quatro algoritmos de roteamento: o XY
(determinístico; west-first; north-last; e negative-first (os três últimos parcialmente
adaptativos). Os algoritmos parcialmente adaptativos funcionam de maneira semelhante,
diferenciando-se nas suas direções proibidas.
Esses algoritmos funcionam com a idéia de coordenadas cartesianas de duas
dimensões. Cada roteador possui um endereço físico único, conhecido como coordenada
fonte (source) e, os cabeçalhos dos pacotes, as coordenadas destino (target), representadas
respectivamente por: (XF, YF) e (XD, YD).
26
2.5.1 Algoritmo de roteamento XY
O algoritmo XY roteia, inicialmente, o pacote na direção X, até que cheguem à
coordenada XD, para depois serem roteados na direção Y, até chegar à coordenada YD (ponto
de destino do pacote). As mudanças de direção para o eixo X, quando um pacote está na
direção Y são proibidas, sendo sinalizadas pelas linhas pontilhadas na Figura 11a. Na Tabela
2 estão os percursos exemplificado na Figura 11b, cuja as rotas foram geradas pelo algoritmo
XY.
A grande vantagem do algoritmo XY é a sua fácil implementação, além de ser livre de
deadlock, pois proíbe a mudança de percurso do eixo Y para o X.
Figura 11 - (a) As retas contínuas representam os caminhos permitidos e as retas pontilhadas, os não
permitidos; (b) Seis exemplos de movimentação dos pacotes na rede.
Tabela 2 - Tabela de percursos dos exemplos da Figura 11b.
Caminhos Fonte (XF, YF) Destino (XD, YD) (0, 0) - (1, 0) (0, 0) (1, 0)
(2, 1) - (3, 1) - (3, 0) (2, 1) (3, 0) (3, 0) - (2, 0) - (2, 1) (3, 0) (2, 1) (1, 2) - (0, 2) - (0, 1) (1, 2) (0, 1)
(3, 3) - (3, 2) (3, 3) (3, 2) (0, 3) - (1, 3) - (2, 3) - (2, 2) (0, 3) (2, 2)
27
2.5.2 Algoritmo de roteamento west-first
No algoritmo west-first, se XD ≤ XF, os pacotes são roteados deterministicamente,
como no algoritmo XY, pois sempre irão tomar a direção oeste primeiro (redes em grade).
Entretanto, quando o XD > XF o pacote pode tomar as direções norte, sul e leste. As direções
proibida para esse tipo de algoritmo são a 2 e a 7, conforme ilustrado na Figura 12a, pelas
setas pontilhadas. Na Figura 12b estão ilustrados dois exemplos de movimentação dos pacotes
na rede, e na Tabela 3 estão os percursos dos mesmos.
Figura 12 - (a) As retas contínuas (caminhos permitidos) e, as retas pontilhadas (não permitidos); (b)
Dois exemplos de movimentação dos pacotes na rede roteados pelo algoritmo west-first.
Tabela 3 - Tabela de percursos dos exemplos da Figura 12b.
Caminhos Fonte (XF, YF) Destino (XD, YD) (2, 2) - (1, 2) - (0, 2) - (0, 3) (2, 2) (0, 3)
(0, 1) - (1, 1) - (1, 0) - (2, 0) - (2, 1) - (3, 1) (0, 1) (3, 1)
28
2.5.3 Algoritmo de roteamento north-last
No algoritmo north-last se YD ≥ YF, os pacotes são roteados deterministicamente,
como no algoritmo XY, pois sempre irão tomar a direção norte, se necessário, por último.
Entretanto, quando o YD < YF o pacote pode tomar as direções oeste, sul e leste. As direções
proibida para esse tipo de algoritmo são a 2 e a 5, conforme ilustrado na Figura 13a, pelas
setas pontilhadas. Na Figura 13b estão ilustrados dois exemplos de movimentação dos pacotes
na rede, e na Tabela 4 estão os percursos dos mesmos.
Figura 13 - (a) As retas contínuas (caminhos permitidos) e as retas pontilhadas (não permitidos). (b)
Quatro exemplos de movimentação dos pacotes na rede roteados pelo algoritmo north-last.
Tabela 4 - Tabela de percursos dos exemplos da Figura 13b.
Caminhos Fonte (XF, YF) Destino (XD, YD) (3, 0) - (2, 0) - (1, 0) - (0, 0) - (0, 1) (3, 0) (0, 1) (0, 3) - (1, 3) - (1, 2) - (2, 2) - (2, 1) (0, 3) (2, 1)
29
2.5.4 Algoritmo de roteamento negative-first
No algoritmo negative-first, os pacotes são roteados primeiro nas direções negativas,
isto é, para as direções sul ou oeste. Se (XD ≤ XF e YD ≥ YF) ou (XD ≥ XF e YD ≤ YF) então os
pacotes são roteados deterministicamente, como o algoritmo XY. As direções proibida para
esse tipo de algoritmo são a 2 e a 6, conforme ilustrado na Figura 14a pelas setas pontilhadas.
Na Figura 14b estão ilustrados dois exemplos de movimentação dos pacotes na rede, e na
Tabela 5 estão os percursos dos mesmos.
Figura 14 - (a) As retas contínuas (caminhos permitidos) e as retas pontilhadas (não permitidos); (b)
Quatro exemplos de movimentação dos pacotes na rede roteados pelo algoritmo negative-first.
Tabela 5 - Tabela de percursos dos exemplos da Figura 14b.
Caminhos Fonte (XF, YF) Destino (XD, YD) (3, 3) - (2, 3) - (2, 2) - (1, 2) - (1, 1) (3, 3) (1, 1)
(2, 0) - (1, 0) - (0, 0) - (0, 1) (2, 0) (0, 1)
30
2.6 ARBITRAGEM
O processo de arbitragem decide quais entradas utilizarão o recurso compartilhado a
cada instante. Em um roteador geralmente, os recursos compartilhados são as saídas, pois
muitas vezes, mais de um pacote podem requerer simultaneamente uma mesma saída. Para
resolver esse problema entra em ação o mecanismo de arbitragem do roteador, que escolhe
um pacote para utilizar o canal de saída. O mecanismo de arbitragem tem que possuir um
critério de escolha que seja livre de starvation, ou seja, ele tem que evitar que um pacote
nunca seja selecionado para utilizar o canal requisitado (SANTOS, 2004), (BASTOS, 2006).
As duas principais formas de implementação do mecanismo de arbitragem são:
centralizada ou distribuída. Na forma centralizada, os mecanismos de roteamento e de
arbitragem são implementados de forma monolítica, ou seja, juntos em um único módulo,
conforme ilustrado na Figura 15a. Enquanto, na forma distribuída, o roteamento e a
arbitragem são implementados de forma independente, para cada porta do roteador, como
ilustrado na Figura 15b. A abordagem distribuída aumenta a capacidade de processamento,
pois cada fila de entrada tem seu próprio mecanismo de roteamento. No entanto, para
algoritmos de roteamento adaptativos, a abordagem distribuída apresenta problemas, pois para
esse tipo de roteamento é preciso um árbitro com visão global.
Figura 15 - Abordagens para implementação de árbitros: (a) centralizada; (b) distribuida. Fonte:
(ZEFERINO, 2003).
A arbitragem centralizada permite que o árbitro receba requisições de maneira
simultânea e independente. Este esquema consiste de um único módulo que recebe as
31
requisições dos buffers das portas de entrada do roteador e seleciona um (de acordo com sua
política de arbitragem), para que possa ser iniciada a transmissão.
Existem vários tipos de política de prioridade e cada uma dessas políticas tem
diferentes características, quanto ao desempenho e à complexidade de implementação. As
principais estão descritas abaixo:
• Prioridade estática: a mais simples de ser implementado, pois o árbitro aplica níveis
fixos e prioridade para as requisições. Esse tipo de política de arbitragem está sujeita a
starvation, pois uma requisição com menor prioridade pode ficar sempre esperando
para ser atendida;
• Round-Robin: Essa política utiliza um esquema de prioridades dinâmicas, baseado em
uma fila circular, onde todas as requisições tem o mesmo nível de prioridade;
• Randômica: Essa política seleciona um dos canais de entrada de maneira aleatória, ou
seja, sem a necessidade de se basear em informação alguma relativa à rede. Tem como
principal vantagem rapidez na escolha de um canal; e
• Oldest-First: Nessa política, o canal escolhido é o que tem mais tempo na fila de
espera. Uma maneira simples de implementá-la é manter um contador para cada canal
de entrada, o canal escolhido será sempre o que tiver o contador com valor maior.
Neste capítulo foi apresentada toda a parte teórica, com boa parte da arquitetura
disposta na literatura, que auxiliou na construção do roteador tratado neste trabalho. Nos
próximos capítulos, será apresentada a construção do roteador com roteamento semi-
adaptativo, juntamente com a construção da rede toro 3x3, e por fim, os testes do roteador,
juntamente com as considerações finais do trabalho.
32
3 DESENVOLVIMENTO
Neste capítulo será apresentada a arquitetura do roteador com roteamento semi-
adaptativo. Serão mostradas as estratégias utilizadas para a topologia, o controle de fluxo, o
chaveamento, a memorização, o roteamento e a arbitragem do roteador.
O roteador foi construído para ser alocado em uma topologia toróide, descrita e
ilustrada na seção 2.1 (Figura 3b). Essa topologia tem por característica a simetria entre os
roteadores. Cada roteador tem dez portas (cinco de entrada e cinco de saída), divididas em
pares denominados Norte (North), Sul (South), Leste (East), Oeste (West) e Local. Conforme
ilustrado na Figura 16.
Figura 16 - Portas de comunicação do roteador.
Basicamente, o roteador implementado é formado por cinco grandes módulos
(ilustrados na Figura 17), que são:
• TERMINAIS – responsáveis pela comunicação com os roteadores vizinhos, o controle
de fluxo dos dados e armazenamento temporário;
• MATRIZ CROSSBAR – responsável em fazer a conexão entre as entradas e as saídas
do roteador;
• ÁRBITRO DE ENTRADA – responsável em armazenar temporariamente os
endereços dos pacotes, e repassá-los ao MÓDULO DE ROTEAMENTO.
• MÓDULO DE ROTEAMENTO – responsável em dizer para qual roteador vizinho o
pacote será enviado, de acordo com as informações contidas no cabeçalho do pacote;
• ÁRBITRO DE SAÍDA – coordena a alocação dos canais de saída do roteador.
33
Figura 17 - Visão em alto nível da arquitetura do roteador.
Quando um TERMINAL recebe dados para serem transferidos, ele repassa o endereço
de destino desses dados (que está no cabeçalho de cada pacote, descrito no inicio do capítulo
2) para o ÁRBITRO DE ENTRADA, que pode receber simultaneamente novos endereços dos
cinco TERMINAIS DE ENTRADA. Ele por sua vez, armazena essa informação
temporariamente, e a repassa ao MÓDULO DE ROTEAMENTO. O ÁRBITRO DE
ENTRADA utiliza uma política de arbitragem conhecida como round-robin, para escolher
qual endereço será repassado primeiro. Recebendo o endereço do pacote, o MÓDULO DE
ROTEAMENTO calcula uma rota para o mesmo, ou seja, ele vai dizer para qual roteador
vizinho o pacote será enviado, ou para seu respectivo núcleo.
Depois que a rota é gerada, a mesma é repassada ao ÁRBITRO DE SAÍDA, que por
sua vez armazena temporariamente essa rota até o canal de saída ficar liberado. Quando o
ÁRBITRO aloca uma saída, ele a repassa a MATRIZ CROSSBAR que fará a conexão do
canal de entrada com o de saída, iniciando o trafego.
Nas próximas seções serão apresentadas as arquiteturas dos módulos internos,
juntamente com suas funcionalidades.
3.1 TERMINAIS DO ROTEADOR
Os TERMINAIS do roteador regulam o tráfego de entrada e saída de dados no
roteador. Eles possuem as seguintes funcionalidades:
34
• Comunica-se com um outro TERMINAL do roteador vizinho;
• Faz a sincronização dos sinais de controle para a transferência dos dados;
• Identifica e armazena temporariamente os dados válidos, enquanto acontece
todo o processo de liberação de tráfego, feitos pelo ÁRBITRO DE
ENTRADA, MÓDULO DE ROTEAMENTO, ÁRBITRO DE SAÍDA e
MATRIZ CROSSBAR;
• Identifica congestionamento na rede;
• Interrompe o armazenamento dos dados quando o buffer fica cheio;
• Retoma a transferência sem perdas dos dados quando o buffer se esvazia; e
• Descarta os pacotes que não podem ser roteados;
Um TERMINAL é formado por quatro outros sub-módulos, que são: Input Flow
Controller (IFC), Output Flow Controller (OFC), uma memória First In First Out (FIFO),
com capacidade de armazenamento de 64 palavras de 10 bits, e um módulo Verificador de
Falhas (VF). A Figura 18 ilustra a arquitetura de um TERMINAL.
A arquitetura usando memória FIFO é a mais simples e de menor custo, pois os dados
são escritos e lidos na mesma ordem (ZEFERINO, 2003). Isso impede que outros pacotes
atrás dele avancem para uma porta de saída qualquer que esteja disponível naquele instante
(ilustrado na seção 2.4 Figura 6).
Figura 18 - Ilustração da arquitetura de um terminal do roteador.
35
Cada flit dos pacotes contém 10 bits (decisão de projeto). O bit 9 e o bit 8 são os bits
de enquadramento do pacote, conhecidos como bop (begin-of-packet) e eop (end-of-packet),
simbolizando o inicio e o fim do pacote, respectivamente (ZEFERINO, 2003). No cabeçalho
do pacote, os bits de 7 a 0, contém o endereço de destino do pacote. Esse endereço está no
padrão XY (explicado na seção 2.5): os bits de 7 a 4 indicam a coordenada X, enquanto os de
3 a 0 indicam a coordenada Y, conforme ilustrado na Figura 19a.
.
Figura 19 - Arrumação dos bits do pacote para: (a) o cabeçalho; (b) o conteúdo da mensagem; (c) e o
terminador.
Na Figura 19b é ilustrada a organização dos bits durante a transmissão da carga útil da
mensagem. Nesse momento os bits bop e eop terão valor lógico “0”. No último flit da
mensagem, o bit eop tem nível lógico “1”, conforme ilustrado na Figura 19c.
Os blocos IFC e o OFC regulam a entrada e a saída dos dados no roteador,
respectivamente. Uma transferência de dados começa no momento em que o bloco IFC,
receber o sinal VAL em nível lógico alto, que significa que existem dados válidos a serem
transferidos. Se o módulo IFC estiver preparado para recebê-los, ele irá ativar o sinal ACK
(acknowledgement), indicando ao módulo OFC do roteador vizinho, que pode iniciar a
transferência. Todo o processo de transferência é ilustrado no diagrama de seqüência da
Figura 20.
36
Figura 20 - Diagrama de seqüência ilustrando os passos da sincronização no momento da
transferência.
O bop vem acompanhado do endereço do pacote, conforme ilustrado na Figura 19a.
Esse endereço é repassado para o ÁRBITRO DE ENTRADA pelos sinais END (com 8 bits) e
REC, que tem a função de sinalizar por um pulso de clock que tem endereço novo, a ser
processado.
No momento que o sinal de bop é reconhecido, imediatamente o sinal WR é ativado,
iniciando assim a gravação dos dados na FIFO. Se a FIFO alcançar seu limiar máximo, o
bloco IFC desativa o sinal ACK, indicando ao roteador emissor que seu buffer está cheio.
Essa técnica é conhecida como controle de fluxo baseado em slack buffer, conforme
explicado na seção 2.2.3. Para retomar a transferência, o módulo IFC reativa o sinal de ACK,
indicando ao roteador emissor que está preparado para continuar a transferência dos dados.
Quando o sinal de eop é identificado durante a transmissão, imediatamente o sinal VAL
(ativado pelo emissor) e o sinal ACK (ativado pelo receptor), são desativados e a transferência
é encerrada.
37
O módulo OFC tem dois sinais, vindos do ÁRBITRO DE SAÍDA, que se chamam
TRANS e DESCARTAR. O sinal de TRANS indica que tudo está pronto para a transferência
e, que pode iniciar a leitura do pacote na FIFO. O sinal DESCARTAR indica o descarte do
pacote, pois não houve rota para o mesmo ser enviado.
O módulo OFC também emite um sinal chamado LIVRE. Esse sinal indica ao
ÁRBITRO DE SAÍDA, quando o OFC está ocupado (transitando ou descartando dados) ou
livre esperando uma solicitação.
O último módulo a ser explicado é o VF, que nada mais é do que dois contadores, um
de 8 bits e outro 10 bits (decisão de projeto). O módulo VF recebe como entrada os sinais
VAL e ACK ligados a OFC. Ele inicia a contagem (do contador de 8 bits) quando o módulo
OFC ativa o sinal VAL, e zera a contagem quando recebe o sinal de ACK do roteador
vizinho. Caso, o sinal ACK não seja ativado até o estouro do contador, o módulo VF ativa o
sinal FALHA, indicando que há um congestionamento nessa direção. Quando o sinal FALHA
é ativado, todo o processo de enviar o endereço ao MÓDULO DE ROTEAMENTO é refeito,
para que a mesma possa calcular uma nova rota. O segundo contador (com 10 bits) inicia a
sua contagem imediatamente depois, que o sinal FALHA é ativado. O estouro do segundo
contador desativa o sinal FALHA.
3.2 ÁRBITRO DE ENTRADA
Sua principal função é armazenar temporariamente os endereços dos pacotes, enviados
pelos TERMINAIS e, repassá-los ao MÓDULO DE ROTEAMENTO, juntamente
identificação do TERMINAL de entrada dos dados. Sua lógica interna é bastante simples,
pois só tem 5 registradores de 8 bits (um para cada TERMINAL de entrada), ligados a uma
única saída por um multiplexador. A escolha de quem vai usar a saída, é feita pelo mecanismo
de arbitragem, usando uma política de arbitragem conhecida como Round-Robin, descrita na
seção 2.6. Essa estratégia foi utilizada, pela sua simplicidade e, por ser livre de starvation. Na
Figura 21 está ilustrada a arquitetura do ÁRBITRO.
38
Figura 21 - Arquitetura do ÁRBITRO DE ENTRADA.
3.3 MÓDULO DE ROTEAMENTO
É um dos módulos mais importantes do roteador, pois ele tem que gerar uma rota de
destino para o pacote, a qual deverá estar livre de livelock e deadlock, além de gerar rotas
alternativas ou indicar o descarte do pacote. A Figura 22 ilustra a arquitetura do MÓDULO
DE ROTEAMENTO, juntamente com seus sinais de entrada e saída.
O MÓDULO recebe três sinais como parâmetros, informando qual é o endereço local
do roteador (sinal END LOCAL com 8 bits), e a dimensão da rede que o roteador está
inserido (sinais SIZE X e SIZE Y). O endereço local obedece ao mesmo padrão dos endereços
que vem no cabeçalho dos pacotes (padrão explicado na seção 2.5). Os quatro últimos bits são
os da coordenada X, e os quatro primeiro da coordenada Y, conforme ilustrado na Figura 23.
Logo, os roteadores implementados suportam, até uma rede 16x16.
Figura 22 - Ilustração da arquitetura do MÓDULO DE ROTEAMENTO.
39
Figura 23 - Organização dos bits de endereço.
O sinal END DESTINO, vem do módulo do ÁBITRO DE ENTRADA. Por ele trafega
os endereços de destino dos pacotes que chegam por seus respectivos TERMINAIS.
Os sinais de saída do MÓDULO DE ROTEAMENTO são o TE_TS (Terminal de
Entrada e Terminal de Saída, com seis bits) e REC_OUT. Esses dois sinais informam ao
ÁRBITRO DE SAÍDA a rota, ou o descarte do pacote. Os bits de 5 a 3, do sinal TE_TS,
indicam o canal de entrada dos dados, e os bits de 2 a 0 o canal que deve sair os dados,
conforme ilustrado na Figura 24.
Figura 24 - Organização dos bits de rota.
O último sinal que não foi descrito na Figura 22, é o sinal FALHA (com quatro bits).
Esse sinal indica para MÓDULO DE ROTEAMENTO quais saídas estão congestionadas.
Todas as saídas, menos a saída LOCAL emitem o sinal FALHA. Essa entrada está
diretamente ligada a quatro módulos VF (Verificador de Falhas), cada qual monitora os sinais
de sincronismo nas saídas NORTE, SUL, LESTE e OESTE do roteador. O MÓDULO DE
ROTEAMENTO desconsidera a saída que estiver com sinal FALHA ativo.
O algoritmo de roteamento escolhido foi o west-first (seção 2.5.2). Isso foi feito
porque esse algoritmo de roteamento tem a capacidade de gerar rotas alternativas, caso o
caminho determinístico esteja com problemas.
O primeiro passo é verificar se o pacote está direcionado, a algum roteador que
pertença ao escopo da rede. Caso contrário, o pacote é descartado automaticamente, pois
nunca chegará ao seu destino. Esse cálculo é feito com o auxilio dos paramentos de entrada,
SIZE X e SIZE Y. O segundo passo do algoritmo é verificar se o endereço de destino do
40
pacote, coincide com o endereço local do roteador: se isso acontecer o pacote é enviado para a
porta de saída LOCAL.
A idéia principal do algoritmo west-first é sempre enviar primeiro o pacote na direção
OESTE, depois para as outras direções, mas para isso tem que obedecer as quatro
recomendações abaixo:
1. O pacote tem que passar por menos roteadores, até seu destino, tomando a
direção OESTE.
2. O pacote tem que entrar pelo TERMINAL LESTE ou LOCAL.
3. Não pode haver falha assinalada ao TERMINAL OESTE.
4. O pacote não pode ter entrado pelo TERMINAL OESTE.
Toda vez que o pacote entra pelo TERMINAL LOCAL do roteador, ele está entrando
na rede, e por essa razão esse pacote pode tomar qualquer direção, inclusive a direção
OESTE. Quando o pacote entra pelo TERMINAL LESTE, significa dizer que ele foi lançado
na direção oeste, por outro roteador, logo pode continuar na mesma direção.
Se as condições para enviar o pacote ao TERMINAL OESTE não forem aceitas, o
pacote é roteado deterministicamente. Mas sempre levando em conta quais TERMINAIS
estão congestionados, e também observando por onde o pacote entrou, pois o pacote não pode
sair pelo mesmo TERMINAL que entrou. Caso o MÓDULO DE ROTEAMENTO não
encontre uma rota, ele tenta enviar o pacote para o canal de saída que estiver sem FALHAS
assinaladas (excluindo o TERMINAL de entrada do pacote, o LOCAL e o OESTE).
Acabando as opções de roteamento o pacote é descartado.
41
3.4 ÁRBITRO DE SAÍDA
O ÁRBITRO DE SAÍDA tem que coordenar a alocação dos canais de saída do
roteador. Na Figura 25 é ilustrada a arquitetura do ÁRBITRO DE SAÍDA. Basicamente, nele
existem três módulos internos chamados de MÓDULO DE ENTRADA, MÓDULO DE
SAÍDA e REGISTRADOR DE SAÍDAS.
Figura 25 - Ilustração da arquitetura do Árbitro de Saída.
O MÓDULO DE ENTRADA tem a função de receber as rotas geradas pelo
MÓDULO DE ROTEAMENTO, armazená-las segundo seu terminal de entrada, e indicar
(pelo sinal de REC_OUT) quais são válidas. Essa organização é feita em registradores com
seis bits chamados de REG_N, REG_S, REG_E, REG_W, REG_L. Esses registradores são
diretamente ligados ao MÓDULO DE SAÍDA. Esse segundo módulo, utiliza uma política de
arbitragem conhecida como Round-Robin, descrita na seção 2.6. Ele fica sempre atento as
saídas que estão livres e, através de uma seleção por fila circular, irá escolher qual entrada
será escolhida. Essa política de arbitragem foi escolhida por ser simples e por evitar o
starvation.
O último módulo é conhecido como REGISTRADOR DE SAIDAS, ele tem a função
de armazenar quais saídas foram requisitadas para uso. Ele recebe os sinais de FALHA, vindo
dos módulos VF (Verificador de Falha), e ACK, vindo dos TERMINAIS. Esses dois sinais
indicam quando a saída está desocupada.
42
3.5 MATRIZ CROSSBAR
A MATRIZ CROSSBAR tem a função de fazer o chaveamento dos pacotes, ou seja,
ela vai fazer a interconexão do canal de entrada de dados com o canal de saída. Sua função é
organizar o chaveamento, e interromper imediatamente, a conexão com o fim da transferência
do pacote (evitando assim que duas ou mais saídas possam estar refletindo os dados de uma
mesma entrada).
A Figura 26 ilustra a arquitetura da matriz de interconexão. Ela contém um módulo
chamado CONTROLE CENTRAL, e dois módulos CROSSBAR 5x5. O CONTROLE
CENTRAL recebe as rotas do ÁRBITRO DE SAÍDA, e ativa os OPCODE dos módulos
CROSSBAR 5x5. O primeiro módulo CROSSBAR 5x5, recebe sinais de 11 bits vindos dos
TERMINAIS, obedecendo a ordem ilustrada na Figura 27.
Figura 26 - Arquitetura da MATRIZ CROSSBAR.
43
Figura 27 - Significado dos 11 bits que passam pelo CROSSBAR 5x5.
Como mostra a Figura 27, do bit 7 ao 0 são os bits que trafegam os dados válidos. Os
bits 9 e 8 são os bits de enquadramento do pacote, respectivamente. Pelo último bit trafega o
sinal de VAL (sinal mencionado na seção 3.1). Pelo segundo módulo CROSSBAR 5x5 entra o
sinal ACK, que vem do roteador vizinho.
Neste capítulo foi apresentada toda a implementação do trabalho, que envolve a
arquitetura escolhida e as estratégias utilizadas no roteador. Nos próximos capítulos serão
apresentados, os resultados obtidos e algumas simulações.
44
4 TESTES FUNCIONAIS
Neste capítulo serão apresentadas quatro simulações distintas de uso do roteador: as
três primeiras simulações serão com um roteador individual, e as últimas, com nove
roteadores interligados formando uma rede toro 3x3.
No primeiro exemplo, simulamos uma transmissão normal de dados, com o objetivo
de mostrar que o roteador tem a capacidade de direcionar e transmitir pacotes. No segundo
exemplo, simulamos um congestionamento em uma das portas do roteador, com o intuito de
mostrar que o roteador pode direcionar e transmitir pacotes para caminhos diferentes, quando
necessário. Para o terceiro exemplo, introduzimos no roteador um pacote com endereço de
destino que está fora do escopo da rede, com o intuito de mostrar que o roteador tem a
capacidade de descartar o pacote, quando necessário. E por fim, o quarto exemplo efetua a
transmissão de um pacote por uma rede 3x3 de roteadores, com o objetivo de mostrar o
funcionamento dos roteadores em rede.
Para os três primeiros exemplos foi, criado um ambiente de simulação, que está
ilustrado na Figura 28.
Figura 28 - Arquitetura do ambiente de simulação para os exemplos I, II e III.
45
No ambiente de simulação desenvolvido, temos um roteador (com seus cinco módulos
TERMINAIS de entrada e saída de dados), acoplado a mais 5 SIMULADORES DE
TERMINAL. Esses novos blocos acoplados ao roteador têm a função de coordenar a entrada
e a saída dos dados, como um TERMINAL de um roteador vizinho.
De modo geral, o processo de simulação se resume aos seguintes passos:
1. Adicionar um pacote ao SIMULADOR DE TERMINAL, no modelo aceito pelo
roteador (com cabeçalho, carga útil e terminador), conforme ilustrado na Figura 19;
2. Acionar o SIMULADOR DE TERMINAL para que ele coordene a entrada dos dados
no roteador; e
3. Monitorar as saídas do roteador para verificar se a transferência foi efetuada com
sucesso.
Nas duas primeiras simulações, foram usados pacotes com o mesmo endereço destino,
mas com conteúdos diferentes. Para que possamos acompanhar as mudanças de caminho dos
pacotes.
Para a última simulação, novamente foi desenvolvido um novo ambiente de
simulação, dessa vez com nove roteadores interligados na topologia toro-2D, formando uma
rede 3x3, conforme ilustrado na Figura 29. Nos TERMINAIS LOCAIS de cada roteador,
foram acoplados SIMULADORES DE TERMINAL, simulando um núcleo ligado ao
roteador. Logo, só monitoraremos as entradas e saídas dos TERMINAIS LOCAIS de cada
roteador.
46
Figura 29 - Arquitetura do ambiente de simulação para a simulação IV.
4.1 PRIMEIRA SIMULAÇÃO
Para esse exemplo, foi configurado o roteador para ter o endereço local (1, 1),
obedecendo ao padrão do projeto (ilustrado na Figura 23), logo, ele receberá “00010001”
como entrada. Também lhe foi passado por configuração, que ele está em uma rede 3x3 (pelos
sinais SIZE X e SIZE Y explicados na seção 3.3). Inicialmente, o roteador é inicializado
(resetado), para que se estabilizem seus sinais internos.
O pacote introduzido no roteador tem a seguinte seqüência de flits:
545 – 10 – 20 – 30 – 40 – 50 – 60 – 70 – 80 – 90 – 256
47
O cabeçalho do pacote está direcionado ao roteador (2, 1), logo, tem representação
binária “1000100001” (545 em decimal), seguindo o padrão ilustrado na Figura 19a. O bit
nove e o bit oito (do cabeçalho) são os bits de enquadramento do pacote: bop e eop. Do bit 7
ao bit 4 estão os bits da coordenada X e, do bit 3 ao 0 a coordenada Y. O último flit do pacote
tem representação binária “0100000000”, também seguindo o padrão aceito pelo projeto
(ilustrado na Figura 19c), onde o eop tem valor lógico “1”.
O pacote será armazenado no módulo SIMULADOR DE TERMINAL, acoplado ao
TERMINAL LOCAL, que é por onde o pacote entrará no roteador. Como o roteador tem
endereço (1, 1), o pacote (2, 1) e o TERMINAL DE ENTRADA é o LOCAL, logo, o pacote
deverá sair pelo TERMINAL LESTE, pois o roteador de destino do pacote é vizinho direto
(pelo TERMINAL LESTE) do roteador transmissor.
Depois que o pacote é inserido no SIMULADOR DE TERMINAL, ele se encarrega de
introduzi-lo no roteador. Na Figura 30 podemos ver o momento que o pacote entra pelo
TERMINAL LOCAL do roteador. No instante de 2400ps o sinal VAL é ativado pelo
SIMULADOR DE TERMINAL, indicando que tem dado a ser transferido para o roteador. No
instante 2550ps, o roteador emite o sinal ACK sinalizando que está preparado para recebe o
dado. E no momento 2650ps inicia-se a transferência dos dados.
Figura 30 - Momento de sincronização (sinais de entrada VAL e ACK) e entrada do pacote pelo
terminal LOCAL do roteador.
Depois da entrada do pacote, o roteador se encarregará de encaminhá-lo a um de seus
vizinhos. Na Figura 31 está ilustrado a sincronização dos sinais de saída VAL e ACK,
seguidos da saída do pacote pelo TERMINAL LESTE. No instante de 3900ps, o sinal VAL é
ativado pelo roteador, indicando que tem dado a ser transferido para o roteador vizinho do seu
lado LESTE (que está sendo substituído pelo SIMULADOR DE TERMINAL, como mostra a
Figura 28). No instante 4050ps, o SIMULADOR DE TERMINAL (acoplado ao TERMINAL
LESTE do roteador) emite o sinal ACK, sinalizando que está preparado para recebe o dado. E
no momento 4200ps inicia-se a transferência dos dados.
48
Figura 31 - Momento de sincronização (sinais de saída VAL e ACK) e saída do pacote pelo terminal
LESTE do roteador.
Na Figura 31 podemos ver que antes do pacote entrar totalmente pelo TERMINAL
LOCAL do roteador, já se inicia a transferência de saída do pacote pelo TERMINAL LESTE.
Com isso podemos concluir que o pacote saiu pelo TERMINAL esperado.
4.2 SEGUNDA SIMULAÇÃO
Para o exemplo II, foi interrompida a comunicação entre o TERMINAL LESTE do
roteador e o SIMULADOR DE TERMINAL, acoplado a ele (com o auxilio de tristates),
conforme ilustrado na Figura 32.
Figura 32 - Simulação de congestionamento com o corte da conexão nos módulos de saída do
TERMINAL LESTE.
49
O pacote que entrará no roteador terá o mesmo endereço de destino do exemplo
anterior (2, 1). Logo, ele terá que sair pelo mesmo TERMINAL do exemplo anterior
(TERMINAL LESTE), pois, o endereço do roteador é (1, 1) e, o TERMINAL de entrada é o
LOCAL. Adicionando essa interrupção ao TERMINAL LESTE, o roteador entenderá que este
caminho está congestionado, logo terá que encontrar um caminho alternativo.
De acordo com a topologia da rede (toro), se esse pacote tomar a direção OESTE, ele
terá que percorrer no mínimo dois roteadores até chegar ao seu destino, enquanto nas direções
NORTE ou SUL teria que percorrer três roteadores. Logo, o primeiro caminho alternativo
oferecido pelo MÓDULO DE ROTEAMENTO, será pelo TERMINAL OESTE.
O pacote será introduzindo no SIMULADOR DE TERMINAL acoplado ao
TERMINAL LOCAL. E em seguida, o pacote será transmitido ao roteador, que por sua vez,
se encarregará de direcioná-lo a um de seus roteadores vizinhos. O pacote que entrará no
roteador tem a seguinte seqüência de flits:
545 – 110 – 120 – 130 – 140 – 150 – 160 – 170 – 256
Todo o processo, descrito na seção anterior, de sincronização e inserção do pacote no
TERMINAL LOCAL do roteador pode ser visualizado na Figura 33. No momento 8700ps o
sinal VAL é ativado pelo SIMULADOR DE TERMINAL, acoplado ao TERMINAL LOCAL
do roteador. O roteador responde com o sinal ACK, no momento 8850ps, indicando que está
preparado para iniciar a transferência. E finalmente, a transferência inicia no instante 8950ps.
Figura 33 - Momento de sincronização (sinais de entrada VAL e ACK), entrada do pacote pelo
terminal LOCAL do roteador.
Na Figura 34 podemos ver o pacote saindo do roteador pelo TERMINAL OESTE. Nos
momentos 36800ps e 36950ps, há o sincronismo dos sinais VAL e ACK, respectivamente. E
no instante 37100ps, inicia-se a saída do pacote pelo TERMINAL OESTE.
50
Figura 34 - Momento de sincronização (sinais de saída VAL e ACK) e saída do pacote pelo terminal
OESTE do roteador.
Observando a linha temporal das Figura 33 e Figura 34, da entrada do pacote, até a sua
saída, demorou exatamente 28150ps, ou seja, aproximadamente 281 pulsos de clock. Isso
aconteceu porque o roteador persistiu na tentativa de enviar o pacote pelo TERMINAL
LESTE por 256 pulsos (que é exatamente o tempo de estouro do contador presente no módulo
VF do TERMINAL LESTE, explicado na seção 3.1). Depois dessa tentativa, a nova rota foi
calculada e o pacote foi transferido com sucesso.
O resultado do experimento está de acordo com o esperado, logo pudemos concluir
que o roteador encontrou um caminho alternativo, para o pacote em questão, e o transferiu
sem perdas de carga útil.
4.3 TERCEIRA SIMULAÇÃO
Para o exemplo III, inserimos um pacote com endereço de destino “11111111”, ou
seja, (15, 15) obedecendo ao padrão aceito pelo roteador, ilustrado na Figura 19a. O roteador
foi configurado para estar em uma rede 3x3, logo esse pacote deverá ser descartado, pois
nunca achará o roteador de destino. Esse teste tem o objetivo de demonstrar uma situação de
descarte de pacote. O pacote que entrará no roteador tem a seguinte seqüência de flits:
767 – 110 – 120 – 130 – 140 – 150 – 160 – 170 – 256
O cabeçalho do pacote é 767 (em decimal) e em binário, “1011111111”. O bit 9 e o 8
são os bits de enquadramento do pacote: bop e o eop. Do bit 7 ao 4 temos a coordenada X (15
em decimal) e, do bit 3 ao 0 a coordenada Y (15 em decimal).
Esse pacote como os outros das simulações anteriores, é inserido no módulo
SIMULADOR DE TERMINAL acoplado ao TERMINAL LOCAL. Esse módulo é
51
responsável em transferir o pacote ao roteador. Dentro do roteador, o pacote é transmitido
para um de seus vizinhos ou descartado, dependendo da situação.
Na Figura 35 podemos ver o momento da sincronização dos sinais de VAL e ACK
(nos tempos 2200ps e 2350ps, respectivamente). Logo depois da sincronização dos sinais
VAL e ACK, o pacote entra no roteador, no instante 2450ps, pelo TERMINAL LOCAL.
Figura 35 – Entrada do pacote pelo TERMINAL LOCAL, e imediatamente depois, descarte do
mesmo pacote.
Na mesma figura, podemos observar que antes do pacote entrar completamente no
roteador, já se inicia o seu descarte. No instante 3200ps, o TERMINAL LOCAL do roteador,
recebe o sinal DESCARTAR, enviado pelo ÁRBITRO DE SAIDA. Esse sinal informa ao
TERMINAL que o pacote deve ser descartado. Imediatamente depois do recebimento desse
sinal, o TERMINAL LOCAL inicia a leitura de sua FIFO, para que seja apagado o pacote.
Com isso, concluímos que em situações onde é impossível a transferência do pacote,
o roteador tem a capacidade de descartá-lo.
4.4 QUARTA SIMULAÇÃO
Como foi dito na introdução do capítulo 4, para esse quarto teste foi criado um
ambiente de simulação com nove roteadores, formando uma rede toro 3 x 3 (Figura 29). Nos
TERMINAIS LOCAIS de cada roteador foram acrescentados SIMULADORES DE
TERMINAL, para coordenar a entrada e saída dos pacotes na rede. Os outros terminais dos
roteadores estão interligados normalmente, segundo a topologia da rede.
Nesse último teste introduzimos um pacote ao roteador (1, 0) com destino ao roteador
(2, 2) e, para está simulação não submetemos situações de congestionamento à rede, logo o
pacote será roteador deterministicamente. O pacote tem a seguinte seqüência de flits:
52
546 – 123 – 4 – 56 – 98 – 45 – 33 – 99 – 0 – 1 – 256
Nas Figura 36, 37, 38 e 39 podemos acompanhar o percurso do pacote pela rede,
destacado de branco em cada uma das figuras. Na Figura 36 o pacote entra na rede pelo
TERMINAL LOCAL do roteador (0, 1), e saí pelo TERMINAL LESTE.
Figura 36 - Momento que o pacote entra na rede, pelo TERMINAL LOCAL do roteador (0, 1), e saí
pelo TERMINAL LESTE.
Na Figura 37 podemos observar a entrada do pacote no roteador (1, 1), pelo
TERMINAL OESTE e, sua saída pelo TERMINAL LESTE.
Figura 37 - Momento que o pacote entra pelo TERMINAL OESTE do roteador (1, 1), e saí pelo
TERMINAL LESTE.
A Figura 38 ilustra a entrada do pacote pelo TERMINAL OESTE, do roteador (2, 1), e
sua saída pelo TERMINAL NORTE.
Figura 38 - Momento que o pacote entra pelo TERMINAL OESTE do roteador (2, 1), e saí pelo
TERMINAL NORTE.
53
Por fim, a Figura 39 ilustra a entrada do pacote pelo TERMINAL SUL, do roteador
(2, 2), e a sua saída da rede pelo TERMINAL LOCAL.
Figura 39 - Momento que o pacote entra pelo TERMINAL SUL do roteador (2, 2), e saí da rede pelo
TERMINAL LOCAL.
Na Figura 40 podemos ver de forma resumida o caminho do pacote pela rede 3x3
montada para a simulação IV. Conclui-se, portanto, que os roteadores têm capacidade de
transportar pacotes aos seus destinos, mantendo a integridade dos seus dados.
Figura 40 - Resumo do percurso do pacote pela rede 3x3.
54
5 CONSIDERAÇÕES FINAIS
O objetivo desse trabalho foi a construção de um roteador para redes em chip com
algoritmo semi-adaptativo. Esse roteador tem capacidade alterar a rota dos pacotes, caso
exista um congestionamento na rede. Por essa razão utilizamos no MÓDULO DE
ROTEAMENTO um algoritmo de classificação sem-adaptativo, junto com alguns módulos
que auxiliarão nesse processo.
Além dos módulos responsáveis pelo roteamento, construímos os módulos
responsáveis pela comunicação de roteadores vizinhos (conhecidos como TERMINAIS), o
módulo que coordena a alocação dos canais de saída (ÁRBITRO DE SAIDA) e o módulo que
é responsável em fazer a interconexão dos canais de entrada com os de saída (MATRIZ
CROSSBAR). Para o roteador utilizamos a estratégia de armazenamento na entrada, com os
buffers no modelo FIFO (seções 2.4.1 e 3.1), juntamente com Controle de Fluxo Baseado em
Slack Buffer (seções 2.2.3 e 3.1).
No MÓDULO DE ROTEAMENTO, foi utilizado o algoritmo west-first, que tem por
característica ser semi-adaptativo e livre de deadlook (seções 2.5.2 e 3.3). No ÁRBITRO DE
SAÍDA, foi utilizada uma política de arbitragem centralizada, conhecida como Round-Robin,
que evita o starvation (seções 2.6 e 3.4). E, na MATRIZ CROSSBAR, foi utilizado um
conjunto de multiplexadores interligados, formando uma estrutura que possibilita a
interligação dos canais de entrada com os de saída do roteador.
Em todo o processo de construção do roteador, houve uma preocupação com o
funcionamento correto de cada módulo individualmente e, em conjunto dentro do roteador.
Neste documento foram relatados alguns testes funcionais do roteador individualmente e, em
uma rede 3x3 toro. O roteador e a rede 3x3 com topologia toro funcionaram corretamente em
todos os experimentos. Mas não podemos valida-los por completo, pois para isso, é necessário
aplicar todas as possíveis entradas ao roteador e, observar se seu comportamento está de
acordo com o esperado.
Trabalhos de pesquisa referentes à continuidade deste Trabalho de Conclusão, a serem
desenvolvidos a médio e a longo prazo, compreendem:
• Implementação e executar os planos de teste dos módulos internos e, do roteador
como um todo;
55
• Implementação da estratégia de Canais Virtuais à rede, para diminuir o número de
pacotes bloqueados (HOL) e reduzir o congestionamento na rede; e
• Adaptação da arquitetura do roteador para melhoramento do armazenamento na
entrada, utilizando as arquiteturas SAFC, SAMQ ou DAMQ (seção 2.1.4.1). Essa
modificação tem o objetivo de diminuir a latência no trafego dos pacotes e evitar o
problema HOL.
56
6 REFERÊNCIAS
BASTOS, E.. Mercury: Uma Rede Intra-chip com Topologia Toro 2D e Roteamento Adaptativo. 2006. 160f. Dissertação (Mestrado em Ciência da Computação)- Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre, 2006. BOLOTIN, E.; CIDON, I; GINOSAR, R.; KOLODNY, A. QNoC: QoS architecture and design process for Network on Chip. The Journal of Systems Architecture, v.20(2-3), 2004, pp. 105-128. CARARA, E.. Uma Exploração Arquitetural de Redes Intra-chip com Topologia Malha e
Modo de Chaveamento Wormhole. 2004. 65f. Trabalho de Conclusão de Curso (Especialização em Ciência da Computação)- Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre, 2004. CULLER, D. E.; SINGH, J. P.; GUPTA, A.. Parallel Computer Architecture: AHardware/Software Approach. San Francisco, California, Ed. Morgan Kaufmann Publishers, 1999. MELLO, A. Qualidade se serviço em redes Intra-Chip: Implementação e avaliação sobre a rede Hermes. Dissertação de mestrado, Porto Alegre, Brasil, Pontifícia Universidade Católica do Rio Grande do Sul, 2006. MELLO, A.; MOLLER, L.. Arquitetura Multiprocessada em SoCs: Estudo de diferentes topologias de conexão. Trabalho de Conclusão II, Porto Alegre, Brasil, Pontifícia Universidade Católica do Rio Grande do Sul - PPGCC - FACIN, 2002. SANTOS, F.; ZEFERINO, C. A.; SUSIN, A. A.. Uma Arquitetura de Roteador
parametrizável para a Síntese de Redes-em-Chip. In: IV Congresso Brasileiro de Computação - CBComp 2004 p. 269-274, 2004. TANENBAUM, A. S. Redes de Computadores, 4ª ed. Rio de Janeiro: Editora Campus, 1994. TANENBAUM, A. S. Sistemas Operacionais: projeto e implementação. 2ª ed. Porto Alegre: Bookmam, 2000.
57
ZEFERINO, C. Redes-em-Chip: Arquiteturas e Modelos para Avaliação de Área e Desempenho. 2003. 242f. Tese de Doutorado (Doutorado em Ciência Computação)- Universidade Federal do Rio Grande do Sul, Porto Alegre, Brasil, 2003.
