PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS
Programa de Pós-graduação em Engenharia Elétrica
Proposta e Desenvolvimento de um
Processador de Rede com Chave Crossbar
Reconfigurável
Henrique Cota de Freitas
Belo Horizonte
2003
Henrique Cota de Freitas
Proposta e Desenvolvimento de um
Processador de Rede com Chave Crossbar
Reconfigurável
Dissertação apresentada ao Programa de Pós-graduação em
Engenharia Elétrica, da Pontifícia Universidade Católica de
Minas Gerais, como requisito parcial para obtenção do título
de Mestre em Engenharia Elétrica.
Orientador: Carlos Augusto Paiva da Silva Martins
Belo Horizonte
2003
Henrique Cota de Freitas
Proposta e Desenvolvimento de um Processador de Rede com Chave Crossbar
Reconfigurável
Dissertação apresentada ao Programa de Pós-graduação em Engenharia Elétrica, da Pontifícia
Universidade Católica de Minas Gerais, como requisito parcial para obtenção do título de
Mestre em Engenharia Elétrica.
Belo Horizonte, 2003.
_______________________________________________________
Prof. Dr. Carlos Augusto Paiva da Silva Martins (Orientador)
Pontifícia Universidade Católica de Minas Gerais – PUC Minas
_______________________________________________________
Prof. Dr. Edward David Moreno Ordonez
Fundação de Ensino Eurípides Soares da Rocha – FEESR-SP
_______________________________________________________
Prof. Dr. Pyramo Pires da Costa Júnior
Pontifícia Universidade Católica de Minas Gerais – PUC Minas
I
DEDICATÓRIA
Dedico a Deus que me iluminou em todos os momentos.
Aos meus pais Walter e Marlene que me deram toda a estrutura, confiança
e sempre acreditaram nos meus objetivos.
Ao meu irmão Túlio que sabe valorizar as pequenas e grandes conquistas.
A minha esposa Silvana que acreditou na vida durante o mestrado.
Aos meus tios e tias que sempre me incentivaram nos estudos.
Aos meus avôs e avós que estão presentes em meu coração.
II
AGRADECIMENTOS
Primeiramente agradeço a Deus por ter me dado saúde e força para superar
os obstáculos, e idéias para convencer minha esposa de que existe vida
durante o mestrado.
Aos meus pais por terem me ensinado o valor do estudo.
Ao meu orientador Prof. Dr. Carlos Augusto Paiva da Silva Martins pela
oportunidade de trabalho em conjunto e pelas horas dedicadas ao incentivo
da pesquisa e na busca de resultados.
Aos colegas do Grupo de Sistemas Digitais e Computacionais (GSDC),
em especial Amanda Regina Mascarenhas Diniz e Luís Fabrício
Wanderley Góes pelo apoio e troca de idéias.
Ao Programa de Pós-graduação em Engenharia Elétrica (PPGEE), em
especial Maria Isabel Siqueira pela atenção, paciência e disponibilidade.
Ao DATAPUC Processamento de Dados pela flexibilidade de horas, que
foi essencial para realização do mestrado.
Aos colegas da Assessoria de Suporte Tecnológico pelo apoio e incentivo.
III
RESUMO
O aumento de desempenho e flexibilidade dos equipamentos de rede é uma exigência
que cresce a cada dia, decorrente do grande uso dos meios de comunicação de dados,
principalmente da Internet. Por este motivo, nos últimos anos, as pesquisas envolvendo os
processadores destes equipamentos têm se tornado freqüentes nas universidades e indústrias.
Em meados da década de 90, a indústria americana desenvolveu um novo segmento de
processadores dedicados chamados de “Processadores de Rede”. As principais características
destes processadores são relativas aos requerimentos e soluções ligadas ao desempenho e à
qualidade de serviço (QoS) garantindo e efetivando a comunicação entre os diversos nós de
uma rede de comunicação de dados.
O principal objetivo da nossa proposta nesta dissertação é apresentar o desenvolvimento
de um processador de rede conceitual que possui em sua arquitetura uma chave crossbar
reconfigurável para aumento de desempenho e flexibilidade no chaveamento de pacotes de
dados e na implementação dinâmica de topologias.
Seguindo a evolução das arquiteturas de processadores de propósito geral,
apresentamos inicialmente o desenvolvimento de um processador de rede CISC (Complex
Instruction Set Computing) e o seu simulador (NPSIM – Network Processor Simulator) de
arquitetura e conjunto de instruções. Sendo assim, o próximo passo foi o desenvolvimento de
um processador de rede RISC (Reduced Instruction Set Computing) considerando como
características mais importantes nesta nova versão, a unidade de comunicação dedicada e
principalmente a chave crossbar reconfigurável.
Os principais resultados desta dissertação são as propostas de arquiteturas e as análises
de desempenho do processador de rede CISC comparado com um GPP (General-purpose
processor) conceitual, do processador de rede RISC comparado com o processador de rede
CISC, a chave crossbar reconfigurável para implementação dinâmica de topologias, uma
análise do aumento de sua flexibilidade baseada em modelagem de grafos e sua simulação
comportamental usando ambiente de desenvolvimento de circuitos digitais em VHDL (VHSIC
Hardware Description Language).
Portanto, apresentamos arquiteturas de processadores de rede (CISC e RISC) com
chave crossbar reconfigurável, considerados também System-on-Chip (SoC), que obtiveram
ganho de desempenho e flexibilidade através dos modelos matemáticos e das simulações
comportamentais realizadas em comparação com outros modelos conceituais.
IV
ABSTRACT
The Internet and other data communication systems require high performance and good
flexibility in their network equipments. Therefore in the latest years, some researches about
dedicated processors for those equipments emerge in universities and companies. During the
last decade, the American companies developed a new segment of dedicated processors called
Network Processors. The main features of those processors are: performance and flexibility to
solve quality-of-service (QoS) requirements in data communication network.
The main objective of this master’s thesis is to present the development of a conceptual
network processor with reconfigurable crossbar switch for increasing the performance, the
flexibility and the data switching.
Based on the architecture evolution of general-purpose processors, we initially present a
CISC (Complex Instruction Set Computing) design for the network processor, with the
architecture and instruction set simulation tool NPSIM (Network Processor Simulator).
Afterwards, we present a RISC (Reduced Instruction Set Computing) design for the network
processor, considering its dedicated communication unit and its reconfigurable crossbar switch
as important features for this new version.
The main results are: mathematic performance analysis between CISC network processor
proposal and a conceptual general-purpose processor; mathematic performance analysis
between the two network processor proposals (RISC and CISC); the increase of flexibility of
reconfigurable crossbar switch based on graph modeling and the behavior simulation using
VHDL (VHSIC Hardware Description Language) digital circuit development environment.
Thus, we present two network processor architectures (CISC and RISC) with a
reconfigurable crossbar switch as a System-on-Chip (SoC) proposal, that got a performance
speedup in comparison to other conceptual models, based on our behavior simulations and
mathematic models.
V
SUMÁRIO
DEDICATÓRIA.......................................................................................................................... I
AGRADECIMENTOS ..............................................................................................................II
RESUMO.................................................................................................................................. III
ABSTRACT.............................................................................................................................. IV
SUMÁRIO .................................................................................................................................. V
LISTA DE FIGURAS.............................................................................................................VII
LISTA DE TABELAS ............................................................................................................. IX
SIGLAS....................................................................................................................................... X
1 – INTRODUÇÃO.....................................................................................................................1
1.1 – CONTEXTO....................................................................................................................1
1.2 – OBJETIVOS ....................................................................................................................3
1.2.1 – Objetivos Principais .................................................................................................3
1.2.2 – Objetivos Intermediários ..........................................................................................3
1.2.3 – Metas principais .......................................................................................................4
1.3 – IMPORTÂNCIA E RELEVÂNCIA................................................................................5
1.4 – MOTIVAÇÕES ...............................................................................................................6
1.5 – ESCOPO ..........................................................................................................................7
2 – ESTADO DA ARTE .............................................................................................................8
2.1 – REDES DE INTERCONEXÃO DE DADOS .................................................................8
2.1.1 – Chaveamento de Pacotes de Dados..........................................................................8
2.1.2 – Roteamento de Mensagens......................................................................................12
2.1.3 – Teoria de Grafos Aplicada a Modelagem de Redes de Interconexão ....................14
2.2 – PROCESSADORES DE REDE ....................................................................................16
2.2.1 – Avanço Histórico e Tecnológico.............................................................................16
2.2.2 – Arquitetura de Referência de um Processador de Rede .........................................17
2.2.3 – Funcionamento Básico de um Processador de Rede..............................................20
2.3 – CONCEITOS DE COMPUTAÇÃO RECONFIGURÁVEL ........................................22
2.3.1 – Linguagens de Descrição de Hardware .................................................................23
2.3.2 – Dispositivos Programáveis .....................................................................................24
2.4 – TRABALHOS CORRELATOS ....................................................................................26
2.4.1 – Pesquisas Acadêmicas ............................................................................................27
2.4.2 – Pesquisas em Indústrias .........................................................................................31
2.4.3 – Eventos Relacionados .............................................................................................34
3 – MATERIAIS E MÉTODO ................................................................................................36
3.1 – MATERIAIS..................................................................................................................36
3.2 – MÉTODO ......................................................................................................................36
VI
4 – PROPOSTA DE UM PROCESSADOR DE REDE RECONFIGURÁVEL .................39
4.1 – ARQUITETURA DO PROCESSADOR DE REDE.....................................................39
4.1.1 – Arquitetura e Conjunto de Instruções CISC ...........................................................40
4.1.2 – Arquitetura e Conjunto de Instruções RISC ...........................................................44
4.1.3 – Unidade de Comunicação Dedicada e Reconfigurável (UCDR) ...........................49
4.2 – ARQUITETURA DA CHAVE CROSSBAR RECONFIGURÁVEL ..........................50
4.2.1 – Chave Crossbar Reconfigurável de 1 bit................................................................52
4.2.2 – Chave Crossbar Reconfigurável de 2 bits ..............................................................54
5 – RESULTADOS ...................................................................................................................57
5.1 – ANÁLISE DE DESEMPENHO DAS ARQUITETURAS E DOS CONJUNTOS DE
INSTRUÇÕES........................................................................................................................57
5.1.1 – Análise de Desempenho do RCNP em Relação a um GPP Conceitual..................57
5.1.2 – Análise de Desempenho do R2NP em Relação ao RCNP ......................................61
5.1.3 – Análise de Desempenho usando a Chave Crossbar Reconfigurável......................68
5.2 – ANÁLISE DA IMPLEMENTAÇÃO DINÂMICA DE TOPOLOGIAS USANDO
TEORIA DE GRAFOS...........................................................................................................70
5.3 – VERIFICAÇÃO COMPORTAMENTAL DA CROSSBAR RECONFIGURÁVEL...75
5.3.1 – Simulação em VHDL da Chave Crossbar Tradicional ..........................................75
5.3.2 – Simulação em VHDL da Chave Crossbar Reconfigurável de 1 bit........................78
5.3.3 – Simulação em VHDL da Chave Crossbar Reconfigurável de 2 bits ......................81
6 – CONCLUSÕES...................................................................................................................86
7 – REFERÊNCIAS BIBLIOGRÁFICAS.............................................................................91
8 – BIBLIOGRAFIA SUGERIDA ........................................................................................104
9 – ANEXOS............................................................................................................................105
VII
LISTA DE FIGURAS
Figura 1 – Exemplos de topologias regulares [De Rose 2001].....................................................9
Figura 2 – Exemplos de redes estáticas e dinâmicas [De Rose 2001]..........................................9
Figura 3 – Classificação de switching fabrics ............................................................................10
Figura 4 – Chave crossbar tradicional........................................................................................11
Figura 5 – Rede Banyan [De Rose 2001] ...................................................................................12
Figura 6 – Arquitetura básica de um roteador ............................................................................13
Figura 7 – Topologia de rede modelada em grafo ......................................................................15
Figura 8 – Estrutura da arquitetura de referência de um processador de rede............................19
Figura 9 – Exemplo de um SoC..................................................................................................20
Figura 10 – Fluxo de pacotes......................................................................................................21
Figura 11 – Arquitetura de um FPGA [Martins 2003, 2002] .....................................................25
Figura 12 – Módulo de interface principal do NPSIM ...............................................................40
Figura 13 – Arquitetura do RCNP apresentada módulo de interface do NPSIM .......................41
Figura 14 – Descrição de parte da arquitetura do RCNP no módulo de interface do NPSIM ...42
Figura 15 – Conjunto de instruções no módulo de interface do NPSIM....................................42
Figura 16 – Descrição das instruções no módulo de interface do NPSIM .................................43
Figura 17 – Formato das instruções do R2NP ............................................................................44
Figura 18 – Estágios de pipeline do R2NP .................................................................................46
Figura 19 – Hierarquia de memória (visão da saída de dados)...................................................47
Figura 20 – Arquitetura do R2NP...............................................................................................48
Figura 21 – Arquitetura da UCDR..............................................................................................49
Figura 22 – Bloco da chave crossbar reconfigurável .................................................................51
Figura 23 – Arquitetura da chave crossbar de 1 bit ...................................................................52
Figura 24 – Topologia implementada usando chave crossbar de 1 bit ......................................53
Figura 25 – Arquitetura da chave crossbar de 2 bits..................................................................55
Figura 26 – Topologia implementada usando chave crossbar de 2 bits.....................................56
Figura 27 – Topologia hipercubo
............................................................................................58
Figura 28 – Topologia árvore
............................................................................................58
Figura 29 – Acessos à memória..................................................................................................60
Figura 30 – Instruções de entrada e saída ...................................................................................60
Figura 31 – Topologia anel unidirecional...................................................................................62
Figura 32 – Topologia hipercubo................................................................................................63
VIII
Figura 33 – Topologia árvore balanceada...................................................................................64
Figura 34 – Topologia árvore balanceada por bits de reconfiguração........................................69
Figura 35 – Topologias dinâmicas..............................................................................................71
Figura 36 – Arestas do grafo com peso (latência em ms)...........................................................73
Figura 37 – Tabelas de roteamento para o nó 5..........................................................................74
Figura 38 – Ambiente de projeto para chave crossbar tradicional - ISE WebPack ...................76
Figura 39 – Conexões simuladas em VHDL (chave crossbar tradicional) ................................77
Figura 40 – Resultado de simulação da chave crossbar tradicional...........................................78
Figura 41 – Ambiente de projeto da chave crossbar de 1 bit - ISE WebPack ...........................79
Figura 42 – Topologias simuladas em VHDL (chave crossbar de 1 bit) ...................................80
Figura 43 – Resultados da simulação da chave crossbar de 1 bit ..............................................81
Figura 44 – Ambiente de projeto da chave crossbar de 2 bits - ISE WebPack..........................82
Figura 45 – Topologias simuladas em VHDL (chave crossbar de 2 bits) .................................83
Figura 46 – Resultados de simulação da chave crossbar de 2 bits.............................................84
IX
LISTA DE TABELAS
Tabela 1 – Instruções do R2NP ..................................................................................................45
Tabela 2 – Descrição das instruções de rede do R2NP...............................................................45
Tabela 3 – Programa assembly para topologia hipercubo (ISA RCNP).....................................58
Tabela 4 – Programa assembly para topologia árvore (ISA RCNP)...........................................59
Tabela 5 – Assembly anel unidirecional......................................................................................62
Tabela 6 – Assembly hipercubo ..................................................................................................63
Tabela 7 – Assembly árvore balanceada .....................................................................................64
Tabela 8 – Comparativo de desempenho....................................................................................66
Tabela 9 – Quantidade de instruções (sem chave crossbar).......................................................67
Tabela 10 – Quantidade de instruções (com chave crossbar) ....................................................70
Tabela 11 – Bits dos nós da chave crossbar de 2 bits ................................................................82
X
SIGLAS
AHDL – Altera Hardware Description Language
ASIC – Application Specific Integrated Circuit
ASIP – Application Specific Instruction Set Processor
CISC – Complex Instruction Set Computing
CLB – Configurable Logic Block
DMA – Direct Memory Access
E/S – Entrada/Saída
Fc – Freqüência do clock
FPGA – Field Programmable Gate Array
Gd – Ganho de desempenho
GPP – General-purpose Processor
GSDC – Grupo de Sistemas Digitais e Computacionais
HDL – Hardware Description Language
HPCA – High Performance Computer Architecture
I/O – Input/Output
ICCAD – International Conference on Computer-Aided Design
ICCD – International Conference on Computer Design
ICS – International Conference on Supercomputing
ICCCN – International Conference on Computer Communication Network
IOB – Input Output Block
ISA – Instruction Set Architecture
ISCA – International Symposium on Computer Architecture
ISCAS – International Symposium on Circuit and Systems
JHDL – Java Hardware Description Language
LCN – Conference on Local Computer Networks
MICRO – International Symposium on Microarchitecture
Ncc – Número de ciclos de clock do programa
Nip – Número de instruções do programa
Nmci – Número médio de ciclos por instrução
NoC – Network-on-Chip
NP – Network Processor
NP – Workshop on Network Processor and Applications
XI
NPC – Network Processors Conference
NPSIM – Network Processor Simulator
PCI – Peripheral Component Interconnect
PPGEE – Programa de Pós-graduação em Engenharia Elétrica
QoS – Quality-of-Service
R2NP – Reconfigurable RISC Network Processor
RCNP – Reconfigurable CISC Network Processor
RISC – Reduced Instruction Set Computing
SAN – System Area Network
SBAC-PAD – Symposium on Computer Architecture and High Performance Processing
SBCCI – Symposium on Integrated Circuits and Systems Design
SBRC – Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos
SoC – System-on-Chip
TDM – Time Division Multiplex
Tp – Tempo de processador
UCDR – Unidade de Comunicação Dedicada e Reconfigurável
VHDL – VHSIC Hardware Description Language
VHSIC – Very High Speed Integrated Circuit
WCAE – Workshop on Computer Architecture Education
WSCAD – Workshop em Sistemas Computacionais de Alto Desempenho
1
1 – INTRODUÇÃO
O objetivo principal desta dissertação é apresentar a proposta, desenvolvimento e os
resultados principais de verificação de um processador de rede com chave crossbar
reconfigurável [Freitas 2003a, 2002b, 2001]. Portanto, nesta introdução apresentamos:
contexto, objetivos, metas, importância, relevância, motivações e escopo. A computação
reconfigurável [Martins 2003] é um conceito importante usado na proposta e desenvolvimento
do processador de rede, principalmente na chave crossbar reconfigurável, sendo apresentada
no tópico 2.3 do estado da arte.
1.1 – CONTEXTO
Os primeiros processadores de rede surgiram no final da década de 90 [Intel 2000]
[Motorola 1999]. Sua principal aplicação era em equipamentos de rede [ADC 2002] [Intel
2001] [Dasan 2001] tais como os roteadores [Cisco 2002, 2001a, 2001b, 2001c, 2001d, 2001e,
2000a, 2000b, 2000c, 1998], substituindo os processadores GPPs (General-purpose processor)
[Patterson 2000], largamente utilizados. Com isso, foi possível aumentar consideravelmente o
desempenho [Menascé 2003] destes equipamentos, já que os processadores GPPs ganhavam
em flexibilidade mais perdiam em desempenho. Era fundamental o desenvolvimento rápido dos
processadores de rede, uma vez que a Internet, principal rede de comunicação de dados do
mundo, necessitava de maior velocidade e vazão de dados. Os equipamentos de rede, por
estarem em pontos de concentração, são considerados pontos de gargalo e por isso são
constantemente alvos de análise e avaliação para melhoria de desempenho.
Durante o processo de desenvolvimento dos processadores de rede, algumas empresas se
uniram, são elas: Lucent e Agere [Agere 2001a, 2001c, 2001d], Motorola e C-Port [C-Port
2002, 2001] [Motorola 1999], Sitera e Vitesse [Vitesse 2002]. Além destas empresas, podemos
citar outras: Intel [Intel 2000], EZChip [EZChip 2002], IBM [Allen 2002] [IBM 2002] e
Chameleon [Chameleon 2000]. A Chameleon foi a primeira empresa a lançar no mercado (no
ano 2000), um processador de rede com um bloco reconfigurável em tempo de execução.
Algumas universidades iniciaram pesquisas sobre processadores de rede por volta do ano
2000. Nos Estados Unidos dois grupos fortes são das seguintes universidades: Washington
University in St. Louis e University of Washington. Por iniciativa dos professores Mark
Franklin e Patrick Crowley foi criado em 2002 o Workshop on Network Processor que é
realizado em conjunto com o HPCA (High Performance Computer Architecture). No Brasil,
2
após busca no sistema Lattes e em Anais e Proceedings de eventos em áreas relacionadas, foi
possível constatar que existe apenas mais um grupo de pesquisa envolvido diretamente com
processadores de rede, localizado na Fundação de Ensino Eurípides Soares da Rocha (Marília,
São Paulo), sob orientação do professor Dr. Edward David Moreno Ordonez. Por esta se tratar
de uma pesquisa recente (iniciada em 2002), não encontramos publicações.
Os processadores de rede [FutureSoft 2003] [Crowley 2002a] [Stenberg 2002] [Agere
2001b, 2001e] [Shah 2001] [Kohler 2000] surgiram com o objetivo de aumentar o desempenho
e a qualidade de serviço (QoS: Quality of Service) [Striegel 2002] [Blum 2000] [Aurrecoechea
1998], diminuindo a latência, o tempo de processamento e aumentando a vazão de pacotes de
dados referentes às redes de comunicação de dados. Desta forma, estes processadores foram
projetados utilizando-se modelos de arquiteturas como ASIP (Application Specific Instruction
Set Processor) [Kästner 2003] [Hoffmann 2001] e SoC (System-on-Chip) [Kochte 2003] [Kalte
2002] [Liang 2000] [Mensch 2000] como forma de agregar ao modelo RISC (Reduced
Instruction Set Computing) [Patterson 2000] maior desempenho computacional.
Estes processadores possuem o nível ISA (Instruction Set Architecture) dedicado para
operações de rede. Sendo assim, o conjunto de instruções e a arquitetura dos processadores de
rede são específicos para realizar operações típicas de redes de comunicação de dados, como
por exemplo, o roteamento [Tanenbaum 2003].
Os processadores de rede além de melhorar a qualidade de serviço, também estabelecem
a comunicação entre diversos equipamentos de rede e hosts (computadores conectados à
Internet) presentes em uma rede de comunicação de dados. Por este motivo são utilizados
blocos de chaveamento de dados externos (switching fabrics) [Ahmadi 1989] [Anderson 1975]
capazes de estabelecer o caminho pelo qual os dados deverão seguir.
Além da nossa proposta de arquitetura de processador de rede, esta dissertação apresenta
também a arquitetura e os resultados obtidos através de análises matemáticas e simulações de
uma chave crossbar reconfigurável para a unidade de chaveamento de dados do nosso
processador conceito. Apesar dos processadores de rede comerciais utilizarem switching
fabrics como blocos externos ao processador, no nosso caso, estaremos inserindo este bloco
dentro do próprio processador, tornando o nosso projeto de processador de rede também um
SoC (System-on-Chip).
Os problemas / perguntas que buscamos resolver são os seguintes:
1. Qual o tipo de arquitetura que permitiria um aumento de desempenho para o
processador de rede?
3
2. Qual conjunto de instruções é mais adequado para o processador de rede
proposto?
3. Qual tipo de switching fabric é mais adequado para a nossa proposta?
4. Como aumentar a flexibilidade e o desempenho em uma chave crossbar?
5. Como implementar topologias dinamicamente?
6. Como e onde aplicar a computação reconfigurável [Martins 2003] em um
processador de rede?
1.2 – OBJETIVOS
Neste tópico apresentamos os principais objetivos e metas desta dissertação.
1.2.1 – Objetivos Principais
O objetivo principal desta dissertação é apresentar a proposta e desenvolvimento de um
processador de rede com chave crossbar reconfigurável que em tempo de execução possa
implementar dinamicamente diferentes tipos de topologias e chavear pacotes de dados
aumentando o desempenho e a flexibilidade em uma rede de comunicação de dados. Sendo
assim, estaremos agregando ao processador de rede o conceito System-on-Chip, já que a chave
crossbar reconfigurável (juntamente com outros blocos) faz parte da arquitetura do processador
de rede proposto. Esta chave crossbar, por ser o ponto de conexões entre entradas e saídas, tem
por objetivo diminuir o tempo de resposta, diminuir a latência e aumentar a vazão de dados,
implementando dinamicamente topologias de interconexão e otimizando o processamento em
uma rede de comunicação de dados.
1.2.2 – Objetivos Intermediários
Os objetivos intermediários que dão suporte ao projeto e desenvolvimento do processador
de rede com chave crossbar reconfigurável são [Freitas 2003a, 2002a, 2002b, 2002c, 2001,
2000a, 2000b]:
Projetar a arquitetura dedicada do processador de rede CISC;
Projetar o conjunto de instruções dedicadas de rede para o processador de rede
CISC;
4
Desenvolver um simulador funcional para o processador de rede CISC;
Analisar matematicamente o desempenho entre o processador de rede CISC e um
processador de propósito geral conceitual com base nos conjuntos de instruções;
Projetar a arquitetura dedicada de processador de rede RISC;
Projetar o conjunto de instruções dedicadas de rede para o processador de rede
RISC;
Analisar matematicamente o desempenho dos processadores de rede projetados
(CISC x RISC) com base nos dois conjuntos de instruções;
Projetar a arquitetura da Unidade de Comunicação Dedicada e Reconfigurável
(UCDR), na qual a chave crossbar reconfigurável se encontra;
Projetar as arquiteturas da chave crossbar reconfigurável (versões de 1 e 2 bits);
Analisar matematicamente o desempenho dos processadores projetados (CISC x
RISC) usando a chave crossbar reconfigurável;
Analisar o modelo em grafos da implementação dinâmica de topologias;
Implementar um código para a chave crossbar reconfigurável em VHDL (VHSIC
Hardware Description Language) para simulação e verificação comportamental
do chaveamento de pacotes de dados e implementação dinâmica de topologias.
Estes objetivos intermediários foram alcançados e estão apresentados nos capítulos 4 e 5.
A Unidade de Comunicação Dedicada e Reconfigurável (UCDR) é composta por um conjunto
de blocos dedicados para comunicação de dados, dentre os quais se destaca a chave crossbar
reconfigurável. Esta unidade será descrita com mais detalhes no capítulo 4.
1.2.3 – Metas principais
As metas principais que foram atingidas são as seguintes:
Arquiteturas de processadores de rede CISC e RISC reconfiguráveis;
Simulador do processador de rede CISC proposto;
Arquitetura da Unidade de Comunicação Dedicada e Reconfigurável (UCDR);
Arquiteturas das chaves crossbar reconfiguráveis (versões de 1 e 2 bits);
Códigos em VHDL da chave crossbar reconfigurável;
Documentação didática em formato de curso [Freitas 2003b] para sobre os
processadores de rede;
Página web em língua portuguesa e inglesa para divulgação da pesquisa;
Artigos para divulgação dos resultados de nossa pesquisa científica.
5
1.3 – IMPORTÂNCIA E RELEVÂNCIA
Os processadores de rede são tecnologia recente na busca de alto desempenho em
equipamentos de rede. Estes equipamentos requerem um excelente desempenho no
processamento de pacotes de dados e por este motivo são considerados pontos de concentração
ou gargalo nas redes de comunicação de dados. A utilização de processadores de rede em
alternativa aos processadores de propósito geral aumentaram consideravelmente o desempenho
destes equipamentos [Cisco 2002].
Apesar de estarmos tratando de forma mais específica a Internet, nada impede a aplicação
destes processadores em outros tipos de redes tais como: System Area Network (SAN) e
Wireless (redes sem fio). Como citado em [Ulmer 2002], existem pesquisas sendo realizadas
para aumentar a qualidade de serviço em redes SAN e os processadores de rede são uma boa
opção para este tipo de exigência. Em [Salefski 2001] é citada a aplicação do processador de
rede CS2000 da Chameleon em redes sem fio. A realização de pesquisas de aplicações de
processadores de rede em sistemas de redes sem fio, buscando maior desempenho e qualidade
de serviço também é um fator relevante na obtenção de melhores resultados de processamento.
Podemos citar também a computação em aglomerados (clusters) [Buyya 1999] ou grades
(grids) [Dantas 2003] como um segmento importante para novas pesquisas [Liljeqvist 2002]
usando processadores de rede. Como as computações em cluster e grid requerem uma rede de
interconexão muito eficaz, é também necessária a utilização de equipamentos e processadores
eficazes para que a comunicação se faça em tempo hábil. Desta forma, a aplicação dos
processadores de rede pode ser extremamente interessante para obtenção de resultados de
desempenho mais satisfatórios.
Um fator relevante se refere à computação reconfigurável [Compton 2002] [Martins
2003, 2002], utilizado também pelo CS2000 [Chameleon 2000]. A utilização deste modelo de
computação possibilita alterar a arquitetura do hardware ou software em tempo de execução.
Esta é uma das principais características de nossa proposta: um processador de rede com chave
crossbar reconfigurável. Desta forma, é possível aumentar a flexibilidade do processador sem
perder desempenho, que é uma característica importante para processadores ASIPs ou SoCs.
A grande vantagem de se utilizar reconfiguração em nossa proposta, é possibilitar a
utilização do processador em diversos tipos de equipamentos ou de redes de comunicação,
apenas alterando os bits de reconfiguração ou programa de gerenciamento, para que
dinamicamente possa existir uma reconfiguração da arquitetura da chave crossbar em relação
6
às características e necessidades de funcionamento da rede. Ou seja, se ganha em flexibilidade
sem perder o desempenho.
Um dos fatores mais relevantes desta dissertação é o fato da nossa proposta de
processador de rede possuir uma chave crossbar reconfigurável. Não encontramos nenhum
trabalho correlato que utilizasse a mesma idéia de arquitetura. Os equipamentos de rede são
considerados gargalos, e os switching fabrics são responsáveis por efetivar a conexão entre as
entradas e saídas da rede de comunicação de dados. Sendo assim, incluímos a arquitetura da
chave crossbar reconfigurável no próprio processador de rede (SoC) para aumentar a
flexibilidade e desempenho da comutação de pacotes e saída de dados.
1.4 – MOTIVAÇÕES
Neste tópico descrevemos nossas motivações com base em um relato histórico.
Durante a graduação houve um interesse muito grande em agregar nosso conhecimento
de arquitetura de processadores em um ambiente de redes de comunicação de dados. Como isto
aconteceu no segundo semestre de 1999, as pesquisas nas universidades sobre processadores de
rede ainda eram muito poucas e não encontrávamos artigos disponíveis relacionados ao
assunto. Ou seja, tínhamos começado nossa pesquisa sem muitas informações sobre o estado da
arte. Desta forma, decidimos dedicar nossas atenções ao projeto de um processador dedicado
para roteamento [Freitas 2000a, 2000b].
Em meados do ano 2000 encontramos os primeiros artigos [Crowley 2000] [Wolf 2000a,
2000b, 2000c, 2000d] relacionados com os processadores de rede. Percebemos que nossa
proposta se enquadrava nas descrições teóricas de um processador de rede e decidimos mudar o
enfoque da pesquisa. Em 2001 publicamos o primeiro artigo tendo como objetivo uma proposta
de processador de rede. Desde o início procurávamos agregar computação reconfigurável ao
nosso projeto de processador de rede para aumento de desempenho e flexibilidade, mas foi no
ano de 2001 que decidimos que a chave crossbar da nossa proposta inicial (CISC) seria
reconfigurável. Porém, não encontrávamos documentos que relacionavam processadores de
rede e computação reconfigurável.
No ano de 2002 descobrimos que parte das documentações disponíveis se tratava de
processadores de comunicação reconfiguráveis [Chameleon 2000]. No mesmo ano surgiram as
primeiras publicações internacionais [Memik 2002] [Troxel 2002] [Iliopoulos 2000],
disponibilizadas na Internet, usando o termo processador de rede e reconfiguração. Estas
7
publicações nos deixaram bastante satisfeitos e nos motivaram cada vez mais, a buscar novos
resultados aqui no Brasil.
Atualmente nossa principal motivação é desenvolver e implementar um processador de
rede com chave crossbar reconfigurável como unidade de chaveamento de pacotes e
implementações dinâmicas de topologias. Segundo nossas avaliações sobre as outras pesquisas
correlatas (tópico 2.4), esta seria uma proposta ainda inédita. Além de estarmos motivados em
projetar uma arquitetura reconfigurável para a chave crossbar, acreditamos na possibilidade do
System-on-Chip (SoC) reconfigurável ser uma boa opção para os projetos de processadores de
rede. Ou seja, a flexibilidade de operação, agregada a um aumento da vazão de dados e
diminuição da latência é um fator motivador para o projeto de uma arquitetura de processador
de rede usando conceitos de computação reconfigurável.
1.5 – ESCOPO
A nossa pesquisa se limita em propor e desenvolver uma arquitetura de processador de
rede reconfigurável. Já possuímos uma quantidade razoável de produção científica que dá
suporte aos nossos resultados e pretendemos atingir até meados de 2004 os resultados finais do
projeto inicial.
O foco principal da dissertação é a proposta e desenvolvimento de uma arquitetura de
processador de rede com uma chave crossbar reconfigurável interna à sua arquitetura, tornando
o projeto e implementação final da proposta, um System-on-Chip (SoC) conforme descrevemos
no tópico 2.2.2.
Iremos nos limitar a projetar as arquiteturas principais (processador, UCDR e crossbar),
analisar matematicamente alguns parâmetros e simular (através de VHDL) o comportamento
da chave crossbar reconfigurável conceitual. No tópico Materiais e Métodos tratamos das
etapas prioritárias para conclusão do mestrado e definimos como etapa final para a dissertação
a simulação comportamental da chave crossbar reconfigurável.
8
2 – ESTADO DA ARTE
Neste capítulo apresentamos uma síntese do estado da arte relacionado aos processadores
de rede. Os seguintes tópicos, que julgamos os mais importantes, serão apresentados: Redes de
Interconexão de Dados, Processadores de Rede, Computação Reconfigurável e Trabalhos
Correlatos.
2.1 – REDES DE INTERCONEXÃO DE DADOS
Como nossa proposta nesta dissertação é apresentar arquiteturas, resultados matemáticos
e de simulação comportamental do processador de rede com chave crossbar reconfigurável, é
necessário que se faça uma revisão de alguns conceitos de redes de comunicação e
interconexão de dados [Tanenbaum 2003] [Dantas 2002] [Rocha 2002] [De Rose 2001]
[Coulouris 2000] [Comer 1995] [Ahmadi 1989] [Anderson 1975], já que através destas é que
são feitos os chaveamentos de pacotes e roteamento de dados. Portanto, descrevemos o
chaveamento de pacotes de dados, tipos de topologias, classificação das redes de interconexão,
roteamento de mensagens e uma modelagem em grafos [Netto 2001] [Calvert 1997, 1992] para
redes de interconexão.
2.1.1 – Chaveamento de Pacotes de Dados
O chaveamento de pacotes de dados em uma rede é feito através de redes de
interconexão. Porém, cada uma destas redes pode ter um formato diferente, ou uma topologia
[De Rose 2001] diferente. A topologia é o formato como os diversos equipamentos de rede ou
hosts estão interligados em uma rede de comunicação de dados. Portanto, existem topologias
em que o formato de interligação segue um padrão de ligação (topologia regular) e topologias
onde não é possível definir um formato ou um padrão de ligação (topologias irregulares).
A figura 1 ilustra algumas possíveis variações de topologias regulares.
9
Figura 1 – Exemplos de topologias regulares [De Rose 2001]
As redes de interconexão são divididas em estáticas e dinâmicas [De Rose 2001].
Podemos observar através da figura 2 alguns exemplos desta divisão tomando como referência
os nomes dados às topologias.
Figura 2 – Exemplos de redes estáticas e dinâmicas [De Rose 2001]
A definição destes dois tipos de redes está baseada na estrutura de interconexão
(topologia) como veremos a seguir:
•
Redes Estáticas:
Neste tipo de rede a topologia adotada oferece um caminho fixo da origem até
o destino. Desta forma, podemos entender como estática a rede de
interconexão onde a comunicação se faz por conexões fixas, que não mudam
ao longo do tempo.
10
•
Redes Dinâmicas:
Ao contrário das redes estáticas, as redes dinâmicas oferecem alternativas de
conexão. A topologia não possui pontos fixos de conexão. Ou seja, o caminho
de comunicação não é fixo. Portanto, podemos considerar que em uma rede
dinâmica as conexões são realizadas de acordo com a necessidade de
comunicação ou transferência de dados. Uma rede dinâmica, onde a conexão
entre dois pontos impossibilita outra conexão, que não seja destes dois pontos,
é chamada de rede dinâmica bloqueante.
Para o contexto de chaveamento de pacotes de dados, em específico para processadores
de rede, existem unidades ou estruturas de chaveamento chamadas switching fabrics [Ahmadi
1989] [Anderson 1975]. Estas estruturas são responsáveis por estabelecer o meio (rede) de
interconexão para que os pacotes processados possam ser redirecionados ou roteados. Uma das
formas de apresentar a classificação dos switching fabrics está ilustrada na figura 3.
Figura 3 – Classificação de switching fabrics
Primeiro estágio da classificação (divisão no tempo e no espaço):
Divisão no tempo: Esta classificação se refere às unidades que utilizam multiplexação de
dados no tempo para alcançar o chaveamento entre entrada e saída.
•
Memória compartilhada: Os pacotes são guardados e analisados em memória.
Este método evita a necessidade de “bufferização”, porém obriga que a velocidade
da memória seja igual ao throughput (vazão) de roteamento de dados.
•
Meio compartilhado: Para se transmitir dados pelo barramento (figura 1) é
utilizado multiplexação por divisão de tempo (TDM). O grande problema deste
tipo de switching fabric é a largura de banda, uma vez que apenas uma entrada
11
pode transmitir enquanto as outras escutam até a liberação do barramento. Esta é a
melhor opção para multicast e broadcast uma vez que todos os nós estão
conectados ao mesmo ponto.
A grande vantagem da utilização de switching fabrics por divisão no tempo é a não
necessidade de pontos de cruzamento como alternativas de caminhos para transmissão de
dados. Porém, uma grande desvantagem deste tipo de unidade de chaveamento é o atraso
ocorrido na espera do processamento de conexões.
Divisão no espaço: O chaveamento entre entradas e saídas é feito através de caminhos
realizados espacialmente, através de pontos de conexão. Porém para este tipo de switching
fabric existe uma separação em dois níveis de topologias de interconexão:
•
Nível único: São switching fabrics compostos por apenas uma unidade de
chaveamento, sem que seja feita composição em cascatas. O exemplo de unidade
mostrado na figura 4 é da chave crossbar. Esta unidade de chaveamento é similar
a uma matriz de conexões onde cada célula é um ponto para fechamento de
comunicação entre entradas e saídas. A característica de bloqueamento não existe
neste nível. Porém, para a chave crossbar tradicional, uma determinada entrada só
se conecta a uma saída por vez, não havendo, portanto, a simultaneidade de
conexões. Ou seja, uma entrada não se conecta a várias saídas ao mesmo tempo,
não realizando, por exemplo, broadcast e multicast.
Figura 4 – Chave crossbar tradicional
12
•
Multinível: Neste tipo de switching fabric, são utilizados vários elementos
(matrizes) de chaveamento, em níveis consecutivos como forma de diminuir a
ocorrência de conflitos entre conexões de pares diferentes. Um exemplo deste tipo
de rede é a Banyan, mostrada na figura 5, onde cada bloco representa uma matriz
de chaveamento 2x2.
Figura 5 – Rede Banyan [De Rose 2001]
A grande vantagem da utilização de unidades de chaveamento no espaço se refere ao
desempenho devido à maior vazão de dados, uma vez que não há atraso por espera de
processamento e sim uma conexão (caminho de roteamento) fechada instantaneamente. Porém
a maior desvantagem se refere a grande quantidade de pontos de conexão, que podem
ocasionar um alto custo e em alguns casos funções bloqueantes.
2.1.2 – Roteamento de Mensagens
Conforme descrito no tópico anterior, os switching fabrics são responsáveis por
estabelecer a conexão e o tráfego de dados entre portas de entrada e saída em um sistema de
comunicação de dados. Eles oferecem o meio pelo qual um determinado processador, seja ele
de propósito geral (GPP), ou dedicado para a aplicação de rede, possa ler o cabeçalho das
mensagens e definir o melhor caminho para que os dados possam seguir.
A figura 6 ilustra a arquitetura básica de um roteador [Chao 2002] [Misra 2001] [Keshav
1998] composta por portas de entrada e saída, um processador e um switching fabric.
13
Figura 6 – Arquitetura básica de um roteador
•
Portas de Entrada e Saída
São portas de entrada e saída que atuam na camada física e tem por objetivo
receber e transmitir dados. Nestas portas é feita a medida da taxa de
transmissão, para evitar congestionamentos no switching fabric.
•
Processador
O bloco Processador nada mais é do que um processador responsável pelo
processamento e gerenciamento dos pacotes. Este processador pode ser de
propósito geral ou dedicado (processadores de rede).
O roteamento de mensagens é feito com base em dois modos de comutação de redes
[Tanenbaum 2003]: i) Comutação por circuitos e ii) Comutação por pacotes.
Comutação por circuitos: Neste caso, podemos fazer uma analogia com as centrais
telefônicas. Quando um determinado fax disca um número, a central realiza a chamada e fecha
uma conexão entre os dois pontos. Existem, neste momento, dois equipamentos conectados em
um circuito físico disponível apenas para trafegar as informações referentes à transmissão e
recepção de dados entre os dois pontos. Neste caso o transmissor possui a segurança de que
seus dados serão recebidos pelo destinatário, uma vez que o meio oferece a garantia da conexão
entre os dois. Uma das vantagens é a alta taxa de transmissão de dados e a desvantagem é o alto
custo.
Comutação por pacotes: A grande diferença é que neste caso não existe uma conexão
disponível apenas para a comunicação de dados entre os dois pontos. O que existe é o
roteamento de dados através de diversos pontos intermediários da rede até o ponto destino.
Existe um compartilhamento do meio físico entre diversas comunicações. Cada host destino
possui um endereço e é através deste endereço, que as máquinas são identificadas na rede.
14
Toda a transmissão de dados é dividida em pacotes. Cada pacote de dados possui um cabeçalho
de informações, que contém o endereço de destino e de origem além de dados referentes ao
ordenamento e seqüência dos pacotes. Desta forma quando todos os pacotes chegam ao
destino, eles podem ser ordenados e interpretados. A grande vantagem deste tipo de rede é o
custo e a simultaneidade de comunicações. Além do baixo custo, vários hosts podem utilizar o
mesmo meio para estabelecer a comunicação. A desvantagem é o aumento da utilização do
meio, causando congestionamento, aumentando o tempo de espera e diminuindo a vazão de
dados da comunicação.
Cada um destes modos de comutação influencia de maneira diferente no roteamento de
mensagens, afeta inclusive nos protocolos utilizados e, portanto, no tipo de rede de
interconexão que será utilizada. Sendo assim, podemos considerar que na comutação por
circuitos, não existe rota a ser definida, ela já está pronta. Na comutação por pacotes, a rota é
definida ao longo do caminho, podendo ser alterada por um agente (roteador) do sistema de
acordo com as necessidades.
2.1.3 – Teoria de Grafos Aplicada a Modelagem de Redes de Interconexão
Como descrito no tópico anterior uma topologia representa basicamente um formato ou
um padrão de ligações existentes em uma rede de comunicação de dados. Normalmente
precisamos projetar ou analisar uma topologia existente para verificar se ela atende ou não as
necessidades de comunicação. Sendo assim, muitas vezes é necessário adotar alguns modelos
matemáticos que facilitam na solução de alguns problemas.
A teoria de grafos [Netto 2001] [Calvert 1997, 1992] é um destes modelos que melhor
atende e facilita a avaliação e a análise de adequação de uma topologia para redes de
comunicação de dados. É possível, por exemplo, representar em um modelo de grafo, vários
parâmetros necessários para a verificação de funcionalidade da topologia adotada.
A figura 7 ilustra uma topologia de rede de comunicação de dados modelada em um
grafo.
15
Figura 7 – Topologia de rede modelada em grafo
É possível ver que todos os parâmetros apresentados possuem um correspondente em
teoria de grafos e a partir destes parâmetros é possível analisar resultados e características de
um grafo que refletem diretamente em uma rede de comunicação de dados.
Um grafo é composto basicamente de vértices e arestas. Os vértices são conectados
através de arestas que por sua vez oferecem caminhos entre cada um dos vértices do grafo. As
arestas podem possuir pesos, que refletem diretamente no custo de utilização desta aresta. Em
outras palavras, se for necessário calcular o menor caminho entre dois vértices, uma aresta de
peso muito alto pode não ser a melhor opção de trajeto.
Utilizando teoria de grafos vários algoritmos foram e são desenvolvidos. Três exemplos
famosos para cálculo do melhor caminho entre dois vértices são:
•
Algoritmo de Dyjkstra: O problema consiste em achar o caminho mais curto entre
duas cidades quaisquer. Modelando em grafos, as cidades são os vértices, as arestas
são as estradas e os pesos são considerados distâncias. [Netto 2001]
•
Algoritmo de Trémaux: Este algoritmo poderia ser usado por alguém perdido em um
labirinto (cada bifurcação é um vértice e cada caminho uma aresta). Este algoritmo
tem a característica de pesquisa em profundidade envolvendo decisões locais, sem
que se tenha conhecimento de todo o grafo. [Netto 2001]
•
Algoritmo de Bellman-Ford: Este algoritmo também pode ser chamado de vetor de
distância. As informações de distância são passadas dos vértices adjacentes (de trás
para frente) até a origem, que recebe os vetores de distância. Então, o vértice origem
constrói uma tabela resultante com sua distância até qualquer outro vértice do grafo.
Este algoritmo é utilizado, por exemplo, em roteamentos [Tanenbaum 2003] na
Internet.
No entanto, para modelagem de topologias de redes dois parâmetros [Calvert 1997, 1992]
importantes são descritos a seguir:
16
•
Grau médio do grafo: Conforme apresentado na figura 7, um vértice possui grau 2
quando o número de arestas ou conexões também é igual a 2. Ou seja, quanto maior o
grau médio do grafo, maior o número de arestas, conexões ou opções de caminhos
para roteamento. Podemos calcular o grau médio de um grafo através da seguinte
equação: Grau médio = (2 x quantidade de arestas) / quantidade de vértices
•
Diâmetro de um grafo: O diâmetro de um grafo é o maior caminho (número de saltos
– arestas) entre quaisquer dois vértices de um grafo. Como o maior interesse é reduzir
o número de saltos entre vértices, um grafo com diâmetro pequeno é uma opção
melhor quando precisamos sair de um vértice para chegar a outro. Em um grafo onde
não existe influência dos pesos das arestas (todos os pesos são iguais), o menor
caminho entre dois vértices é aquele que possui um menor número de saltos ou uma
menor quantidade de arestas entre eles.
Com base nestes dois parâmetros, podemos concluir que um grafo completo (figura 1 –
onde todos os vértices possuem arestas de ligação para todos os outros vértices) é a melhor
opção, uma vez que teremos o grau máximo do grafo (valor varia – depende da quantidade de
vértices) e o menor diâmetro, uma vez que o salto máximo de um vértice para outro é igual a 1.
No entanto, devemos ressaltar que uma topologia completa pode possuir um maior custo e não
refletir a real necessidade de um sistema de comunicação de dados.
2.2 – PROCESSADORES DE REDE
Este tópico apresenta os principais conceitos sobre processadores de rede. Procuramos
descrever o avanço histórico e tecnológico, a arquitetura de referência e o funcionamento
básico dos processadores de rede.
2.2.1 – Avanço Histórico e Tecnológico
O processador de rede nasceu da necessidade crescente de desempenho e da qualidade de
serviço (QoS) [Striegel 2002] [Blum 2000] [Aurrecoechea 1998], que era exigido dos
equipamentos de rede. Inicialmente utilizavam-se processadores de propósito geral (GPPs:
General-purpose Processor) [Patterson 2000], depois circuitos dedicados (ASICs: Application
Specific Integrated Circuit) [Kästner 2003] e por fim processadores específicos (ASIPs:
Application Specific Instruction Set Processor) [Kästner 2003] de rede. As gerações de
equipamentos de rede e suas principais características podem ser definidas da seguinte forma:
17
•
1a Geração
o Processador de Propósito Geral (GPP): Baseado na utilização de softwares
para definição de comportamento. Processador flexível para diversas
aplicações,
porém
para
aplicações
de
rede
são
limitados
em
funcionalidades e desempenho.
•
2a Geração
o Circuito de aplicação específica (ASIC): Circuitos projetados para
executar determinadas funções específicas. Não utilizam softwares, são
bastante rápidos e o grande problema é a flexibilidade, uma vez que o
ASIC é projetado apenas para uma aplicação.
•
3a Geração
o Processadores
de
Rede:
Os
processadores
de
rede
possuem
microarquitetura dedicada para trabalhar em redes de comunicação de
dados. O conjunto de instruções também é específico. Por se tratar de
processadores, eles são flexíveis e por serem específicos também possuem
bom desempenho.
Sendo assim, podemos considerar um processador de rede como um processador de
aplicação específica (ASIP: Application Specific Instruction Set Processor).
Vantagens: União de flexibilidade e desempenho devido, por exemplo, ao projeto
dedicado do conjunto de instruções e da arquitetura.
Desvantagens: É mais lento do que um ASIC e menos flexível do que um GPP.
2.2.2 – Arquitetura de Referência de um Processador de Rede
Existem dois modelos para projeto de processadores: CISC e RISC [Patterson 2000]
[Ricarte 1999]. O primeiro utilizado no início da história de desenvolvimento de processadores
é o CISC (Complex Instruction Set Computing). Sua principal característica é o conjunto de
instruções com formatos variados. Ou seja, uma única instrução do tipo ADD pode acessar
registradores e memória, e utilizar vários modos de endereçamento. Desta forma, cada
instrução possuía uma grande amplitude nos modos de endereçamento.
No entanto, com o avanço tecnológico, constatou-se que apenas uma pequena fração do
código de programa necessitava acessar a memória e como sabemos, acessar a memória é mais
18
demorado do que acessar registradores. Baseado nesta constatação foi projetado um novo
modelo de processadores RISC (Reduced Instruction Set Computing). Neste novo modelo de
processador, o objetivo é reduzir o número de instruções que acessam a memória, tornando as
manipulações do processador concentradas em registradores. Desta forma, apenas instruções do
tipo load e store podem acessar a memória, o que não acontecia no modelo CISC onde uma
instrução de soma, como ADD, também podia realizar este acesso.
De acordo com o estudo feito por nós, os processadores de rede existentes no mercado
são RISC. Estes processadores possuem um pequeno número de ciclos para execução de cada
instrução, menor quantidade de instruções que acessam a memória, sendo mais eficientes que
os processadores CISC.
Existem duas características que podem diferenciar os processadores de rede:
• Utilização apenas de tecnologia RISC com sistemas complexos de paralelismo.
• Baseado em tecnologia RISC e ASIC. O ASIC acelera o processamento pelo
hardware, porém pode trazer inflexibilidade.
Em um sistema computacional complexo a utilização de todas estas tecnologias
normalmente é feita. Porém, em situações mais específicas, deve-se analisar as variáveis,
desempenho, flexibilidade e custo para a escolha da melhor tecnologia.
A arquitetura de referência derivada da análise de diversos trabalhos [FutureSoft 2003]
[Crowley 2002a] [Stenberg 2002] [Agere 2001b, 2001e] [Shah 2001] [Kohler 2000] é
apresentada na figura 8 com o intuito de definir uma base para o estudo, análise e projeto dos
processadores de rede.
Os principais blocos lógicos de um processador de rede são:
•
Um ou vários processadores RISC;
•
Co-processadores ou engines;
•
ASICs (programáveis ou não) para operações de rede;
•
Interface de memória de alto desempenho;
•
Interface de E/S de alto desempenho;
•
Interface dedicada para comunicação entre processadores de uma mesma família;
•
Interface para processadores de propósito geral.
19
Figura 8 – Estrutura da arquitetura de referência de um processador de rede
A figura 8 ilustra uma arquitetura de referência de processador de rede com alguns blocos
construtivos. Estes blocos não necessariamente aparecem nas arquiteturas de todos os
processadores de rede. Com base na figura 8 podemos destacar os seguintes blocos:
•
Unidades ASICs: Unidades PCI, QoS, rede, switching fabric, portas de entrada e
saída e memória interna.
•
Unidades de processamento: Processadores RISC e microengines.
Caso não exista nenhum bloco dedicado internamente à arquitetura do processador de
rede (Ex. memória interna), as interfaces são usadas para acesso externo.
Atualmente a tecnologia está evoluindo para infra-estruturas de rede, que suportam a voz
sobre IP (VoIP), vídeo, comércio eletrônico entre outros. Para isto é necessário aumentar a
largura de banda, diminuir a latência e melhorar o processamento. Os processadores de rede
surgiram para aumentar o desempenho de processamento nas redes de comunicação e ajudar na
crescente demanda por esta nova tecnologia.
Atualmente está sendo usado para o projeto de processadores o conceito System-on-Chip
[kochte 2003] [Kalte 2002] [Liang 2000] [Mensch 2000]. O SoC nada mais é do que um
sistema de blocos lógicos diversos como processadores, portas de E/S, memória e hardwares
dedicados, construídos internamente em um circuito integrado, com o intuito de diminuir o
tamanho do hardware, aumentando a velocidade de processamento.
Muitos projetos de processadores de aplicação específica utilizam esta técnica de
desenvolvimento e implementação, que aumenta consideravelmente o desempenho, uma vez
que os blocos lógicos ficam mais próximos da unidade de processamento, tal como em
hierarquias de memória.
A figura 9 ilustra um exemplo de SoC e seus blocos construtivos.
20
Figura 9 – Exemplo de um SoC
A figura 8 também pode ser considerada como um SoC devido aos blocos construtivos
que são internos à arquitetura de um processador de rede.
Após o surgimento dos modelos System-on-Chip (SoC) constatou-se a necessidade de
uma elevada velocidade de transmissão e recebimento de dados internos, já que grande parte
dos dispositivos de entrada, saída e armazenamento são internos. Sendo assim, o conceito
Network-on-Chip (NoC) [Kochte 2003] [Karim 2002] surgiu para que fosse agregado todo um
sistema de rede de interconexão de dados eficiente para garantir o aumento de vazão de dados e
por conseqüência de processamento do SoC.
2.2.3 – Funcionamento Básico de um Processador de Rede
As ações básicas de um processador de rede são as seguintes:
•
Analisar e classificar o conteúdo dos campos do cabeçalho do pacote em análise;
•
Procurar em tabelas, regras de associação com o campo encontrado no cabeçalho do
pacote;
•
Resolver o caminho do destino ou requerimentos de QoS;
•
Modificar o pacote em análise se necessário.
Um processador de rede deve ser construído para que os pacotes tenham um
processamento e roteamento rápido, evitando gargalos. Para isto o processador deve ter
caminhos internos que possam distinguir, através do software ou hardware (ASIC), os pacotes
que terão um processamento mais complexo e por isso levarão mais tempo para serem enviados
ao destino e aqueles que terão um processamento mais simples e rapidamente serão
redirecionados. Sendo assim, podemos definir duas classes [Kohler 2000] ilustradas na figura
10: i) Processamento “rápido” e ii) Processamento “lento”.
21
Figura 10 – Fluxo de pacotes
Os pacotes que precisam de um processamento “rápido” normalmente são simples e
utilizam recursos dedicados para acelerar o processamento. O caminho “rápido” é composto
basicamente por co-processadores e ASICs. Desta forma, o processador de rede não faz, por
exemplo, a análise ou alteração de campos de cabeçalhos e não faz consulta às tabelas de
roteamentos. Neste caso o caminho “rápido” facilita o trabalho do processador principal, que
estará encarregado de outras tarefas.
Quando o pacote precisa de um processamento mais “lento” ou complexo (análise de
tabela, regras de algoritmos e modificação em campos de cabeçalho, por exemplo) o caminho a
ser adotado é mais “lento”, é necessário talvez, o uso de memória e de um processador
principal.
Esta definição de qual caminho a seguir pode ser feita utilizando circuitos dedicados ou
softwares que estejam sendo executados no processador. As duas classes de processamento
caracterizam e auxiliam na distinção dos pacotes e por conseqüência no desempenho final do
processador.
As redes ativas [Tennenhouse 1997] são muito importantes quando falamos de qualidade
de serviço. Uma das tarefas do processador de rede é analisar o campo do cabeçalho de um
pacote e tomar as decisões necessárias, inclusive de modificação do pacote. Sendo assim
podemos relacionar as ações básicas de um processador de rede com o texto descrito a seguir:
•
Redes ativas nada mais são do que redes em que roteadores e switches executam
tarefas (computação) a partir de mensagens que atravessam por eles. Neste tipo de
rede, o pacote possui instruções que, lidas pelo roteador ou switch, resultarão em um
processamento interno, que pode modificar o cabeçalho ou o pacote, antes mesmo que
chegue ao destino.
Um processador de rede deve dar suporte a redes ativas. A necessidade de qualidade de
serviço (QoS) exige melhorias de desempenho nos equipamentos de rede e a evolução destes
equipamentos está ligada diretamente aos processadores de rede.
22
2.3 – CONCEITOS DE COMPUTAÇÃO RECONFIGURÁVEL
Ao longo dos últimos anos duas soluções de implementação computacional [Martins
2003, 2002] foram largamente utilizadas:
•
Solução por hardware fixo:
Solução baseada em arquiteturas ASIC (Application Specific Integrated
Circuit), onde o hardware projetado funciona apenas para uma determinada
aplicação. Alto desempenho, mas com pouca flexibilidade.
•
Solução por hardware programável + software:
A solução de hardware programável + software é baseada na programação de
um hardware através de software. Esta solução pode ser exemplificada através
dos dispositivos programáveis como processadores que utilizam instruções
para responder a uma determinada requisição e processar dados desta
requisição. Possui uma alta flexibilidade de trabalho, podendo ser usado em
outros tipos de aplicações, mas com um menor desempenho em relação ao
modelo de hardware fixo.
Estas duas soluções dominam todos os sistemas computacionais que encontramos
implantados em instituições e empresas. Porém, sempre existiu a necessidade de unir as
vantagens de cada uma destas soluções para que o sistema computacional ganhasse maior
desempenho e flexibilidade.
A solução que vem sendo pesquisada e difundida nos últimos anos é a Computação
Reconfigurável [Compton 2002] [Martins 2003, 2002] [Hartenstein 2001] [Bondalapati 2000].
Esta nova solução tem sido usada como intermediária para resolver problemas de melhoria de
desempenho, flexibilidade, generalidade, eficácia, custo e outros. Como os conceitos
relacionados à computação reconfigurável ainda estão se formando, devido ao fato dos
resultados ainda serem muito recentes, citamos algumas definições existentes:
“Dispositivo que realiza computação usando conexão espacial ‘pós-fabricação’ de
elementos de computação”, enquanto os computadores tradicionais realizam computação
fazendo conexões no tempo. [Dehon 2000]
“Computação Reconfigurável representa uma nova idéia em filosofia de computação, na
qual algum agente de hardware de propósito geral é configurado para realizar uma tarefa
23
específica, mas pode ser reconfigurado sob demanda para realizar outras tarefas específicas”.
[Reconfigurable 2003]
“Um novo paradigma de computação no qual circuitos integrados programáveis são
usados em conjunto com software para reconfigurar circuitos integrados FPGA dinamicamente
e produzir arquiteturas de computador sob demanda”. [Star 2003]
Este novo modelo ou paradigma (Computação Reconfigurável) ainda não é amplamente
utilizado. Porém, soluções usando computação reconfigurável têm sido pesquisadas e já
encontramos na indústria sistemas computacionais desenvolvidos para atender a essa nova
demanda de flexibilidade + desempenho.
As linguagens de descrição de hardware, tais como VHDL (VHSIC Hardware
Description Language), podem ser utilizadas para o desenvolvimento de sistemas
computacionais reconfiguráveis. A prototipação e a implementação de circuitos reconfiguráveis
é feita em dispositivos programáveis tais como os FPGAs (Field Programmable Gate Array).
Nos tópicos 2.3.1 e 2.3.2 fazemos uma breve abordagem das características principais de cada
um.
2.3.1 – Linguagens de Descrição de Hardware
As linguagens de descrição de hardware (HDL: Hardware Description Language)
[Ordonez 2003] [Martins 2003, 2002] [Ashenden 1998, 1990] [Glesner 1998] [Xilinx 1998]
foram criadas com o objetivo de facilitar a modelagem, projeto e implementação de um circuito
(hardware). Através destas linguagens é possível simular o funcionamento e analisar os
resultados de simulação antes da prototipação.
A seguir apresentamos quatro exemplos de linguagens de descrição de hardware:
•
VHDL: VHSIC (Very High Speed Integrated Circuit) Hardware Description
Language. Criada em 1983 pelo departamento de defesa americano (DOD).
•
Verilog: Proprietária da Cadence Design System Corporation até 1990, quando foi
criado o Open Verilog International (OVI) e a linguagem passou a ser de domínio
público. Muito parecida com a linguagem C.
•
AHDL: Altera Hardware Description Language (linguagem desenvolvida pela
empresa Altera)
•
JHDL: Java Hardware Description Language. Utiliza a linguagem Java para a
programação, usando bibliotecas estendidas de descrição de hardware.
24
Um programa em VHDL pode ser escrito usando dois tipos de modelos de descrição:
•
Estrutural:
São feitas descrições estruturais do sistema, especificando entradas, saídas,
componentes lógicos e como são feitas as ligações entre eles. Já existem
bibliotecas em VHDL, que possuem algumas entidades (exemplo: somadores)
e que podem ser inseridas no desenvolvimento do projeto.
•
Comportamental:
Neste caso não é necessário conhecer a estrutura dos componentes lógicos do
sistema. Quando a estrutura interna do circuito não é conhecida ou é muito
complexa, é utilizada a abordagem comportamental, onde se descreve o
comportamento e funcionamento, sem se preocupar com a estrutura.
Além do VHDL ser padrão IEEE para desenvolvimento de hardware, ele está
diretamente relacionado com o avanço da tecnologia de circuito integrado de alta velocidade
(VHSIC: Very High Speed Integrated Circuit).
Maiores detalhes sobre VHDL, incluindo os demais conceitos, estruturas, palavras
reservadas e bibliotecas podem ser encontrados nas seguintes referências: [Ordonez 2003]
[Ashenden 1998, 1990]
2.3.2 – Dispositivos Programáveis
Um dos dispositivos que encontramos no mercado para implementação de
circuitos/sistemas reconfiguráveis é chamado de FPGA (Field Programmable Gate Array)
[Ordonez 2003] [Martins 2003, 2002] [Glesner 1998] [Xilinx 1998]. Os FPGAs são
dispositivos programáveis em campo, ou seja, podem ter sua configuração alterada após sua
fabricação. Cada FPGA normalmente é composto por matrizes de elementos. Antes que cada
elemento seja utilizado ele deve ser configurado. Esta configuração se faz através de um
conjunto de bits chamados de bitstream. Esta matriz está ilustrada na figura 11.
Para que seja possível a utilização do modelo ou paradigma de computação
reconfigurável é necessário um dispositivo (hardware) programável. Esta afirmação nos leva a
uma pergunta: Por que não um dispositivo reconfigurável?
25
A programação do dispositivo é feita para que todos ou alguns dos componentes do
dispositivo se interliguem e implementem um circuito qualquer. Esta é a implementação
realizada no primeiro momento. Se houver a programação deste dispositivo novamente para
implementação de um novo circuito (ou mudança no mesmo circuito) consideramos que o
circuito implementado foi reconfigurado. Portanto, é necessário que se defina um primeiro
nível estático e programável, para que as implementações realizadas neste primeiro nível
possam ser reconfiguráveis. Se o dispositivo fosse reconfigurável, poderíamos alterar ou
reconfigurar o dispositivo e não a implementação de um circuito neste dispositivo. Um
exemplo seria aumentar a quantidade de componentes que fazem parte deste dispositivo, o que
não é possível. Mas aumentar o número de componentes usados no circuito implementado é
possível (existe o limite de componentes do produto), basta reconfigurar esta implementação,
ou programar novamente o dispositivo.
Figura 11 – Arquitetura de um FPGA [Martins 2003, 2002]
A arquitetura típica de um FPGA é a seguinte:
•
CLB (Configurable Logic Block): Matriz de blocos lógicos configuráveis;
•
Rede de Interconexão Programável: Blocos de interconexão que interligam todos os
CLBs;
•
IOB (Input Output Block): Na periferia de todo o circuito existem blocos de entrada e
saída para interface externa.
26
Em um dispositivo FPGA os métodos de reconfiguração podem ser classificados como:
•
Reconfiguração Total: Todo o dispositivo programável é reconfigurado.
•
Reconfiguração Parcial: Apenas uma parte do dispositivo é reconfigurada. Se afetar
outras partes não reconfiguradas, todo o sistema deve ser parado para ser reiniciado.
•
Reconfiguração Dinâmica: Reconfiguração em tempo de execução. Reconfiguração
realizada durante o funcionamento do dispositivo.
Portanto, a implementação de um hardware reconfigurável usa um dispositivo
programável (FPGA). A reconfiguração se faz através de bits (bitstreams), que podem ser
gerados através de um código desenvolvido em VHDL descrito no tópico anterior.
2.4 – TRABALHOS CORRELATOS
Conforme já descrevemos na introdução, o número de trabalhos e pesquisas envolvendo
processadores de rede ainda é muito pequeno. No entanto, citamos no tópico 2.4.1 algumas
pesquisas acadêmicas que julgamos relevantes para a área e que podem acrescentar
conhecimento para futuros projetos e resultados relacionados a nossa pesquisa.
É importante citar que, não encontramos pesquisas trabalhando com processadores de
rede com chave crossbar reconfiguráveis, mas alguns grupos já iniciaram trabalhos
relacionados com processadores de rede reconfiguráveis. Entre os grupos citados, ressaltamos a
pesquisa do Prof. Dr. Edward Ordonez e do aluno de mestrado Ricardo Petruzza como o único
grupo no Brasil, além do nosso, a pesquisar e agregar computação reconfigurável aos
processadores de rede. Esta pesquisa, iniciada recentemente, ainda não possui publicações dos
resultados.
Em algumas pesquisas o uso do FPGA (Field Programmable Gate Array) implica em um
projeto de computação reconfigurável, já que são feitas várias implementações dos dispositivos
no FPGA. No nosso caso escolhemos o FPGA apenas como suporte para implementação, a
nossa reconfiguração, como descrita no tópico 4.2, se limita à implementação de topologias na
chave crossbar. Ou seja, não há reconfiguração da implementação realizada no FPGA, mas sim
das implementações (topologias) realizadas pela chave crossbar. Para obter a reconfiguração
não programamos o FPGA, mas sim a chave crossbar.
27
2.4.1 – Pesquisas Acadêmicas
A seguir estão relacionados os nomes de algumas universidades, respectivos
departamentos, pessoas envolvidas e as pesquisas relacionadas aos processadores de rede:
•
Chalmers University of Technology, Department of Computer Engineering, Suécia,
Björn Liljeqvist e Lars Bengtsson, [Liljeqvist 2003, 2002]
o Dissertação sobre processadores de rede: “Visions and Facts – A Survey
of Network Processors”;
o Computação em grade usando processadores de rede.
•
Columbia University / University of Texas, EUA, Michael E. Kounavis, Andrew T.
Campbell, Harrick Vin [Kounavis 2003] [Campbell 2002]
o Direções na classificação de pacotes para processadores de rede;
o Ferramenta para construção de caminhos de dados em processadores de
rede baseados em roteadores.
•
North Caroline University, Computer Engineering Program, EUA, Deepak
Suryanarayanan, Gregory T. Byrd [Suryanarayanan 2002]
o Metodologia e simulador para estudo de processadores de rede.
•
Purdue University, School of Electrical and Computer Engineering, EUA, Jahangir
Hasan, Satish Chandra e T. N. Vijaykumar [Hasan 2003]
o Estudo do uso da largura de banda da memória para aumentar vazão dos
processadores de rede.
•
Swiss Federal Institute of Technology (ETH), Computer Engineering and Networks
Laboratory, Zürich, Suíça, Lothar Thiele, Samarjit Chakraborty, Mathias Gries e
Simon Künzli [Thiele 2002]
o Uma abordagem de exploração de arquiteturas de processadores de rede.
•
University of California, Berkeley, Department of Electrical Engineering and
Computer Sciences, EUA, Nirja Shah, Will Plishker, Kurt Keutzer, Chidamber
Kulkarni, Christian Sauer [Shah 2001, 2002] [Tsai 2002]
o Dissertação de mestrado: “Understanding the Network Processors”;
o Estudo sobre a história dos processadores de rede;
o Metodologia de benchmarking para processadores de rede;
o Modelo de programação para processadores de rede.
•
University of California, Riverside, Department of Computer Science & Engineering,
EUA, Haiyong Xie, Li Zhou e Laxmi Bhuyan [Xie 2002]
28
o Análise arquitetural de aplicações de criptografia para processadores de
rede.
•
University of California, San Diego, Department of Computer Science &
Engineering, EUA, Timothy Sherwood, George Varghese e Brad Calder [Sherwood
2003]
o Estudo sobre arquitetura de memória usando conceitos de pipeline para
aumento de vazão de processadores de rede.
•
University of Washington, Department of Computer Science & Engineering, EUA,
Patrick Crowley e Jean-Loup Baer [Crowley 2000, 2002a, 2002b]
o Tutorial sobre processadores de rede;
o Caracterização de arquiteturas de processadores para interfaces de rede
programáveis;
o Modelagem de Framework para sistemas de processadores de rede.
•
University of Wisconsin, EUA, Madhu Sudanan Seshadri, John Bent e Tevfik Kosar
[Seshadri 2003]
o Análise e projeto de processadores de rede para uso em roteamentos.
•
Washington University in St. Louis, School of Engineering & Applied Science, EUA,
Tilman Wolf, Mark A. Franklin e Edward W. Spitznagel [Franklin 2002, 2003] [Wolf
2000a, 2000b, 2000c, 2000d, 2001]
o Considerações sobre desempenho
e consumo de potência para
processadores de rede;
o Questões de projeto para roteadores ativos de alto desempenho;
o Análise de carga de trabalho para programação de tarefas para os
processadores de rede;
o Projeto de processadores de rede embarcados;
o Desempenho e benchmark para processadores de rede;
o Projeto de conjunto de instruções para processadores de rede.
Os grupos relacionados a seguir trabalham com computação reconfigurável aplicada aos
processadores de rede:
•
University of Patras, Department of Electrical Engineering and Computer
Technology, Grécia, Marios Iliopoulos e Theodore Antonakopoulos, [Iliopoulos
2000]
29
o Processadores de rede reconfiguráveis baseados em circuitos programáveis
em campo (Ex. FPGAs).
•
University of Florida, HCS Research Lab, ECE Department, EUA, I. A. Troxel, A. D.
George e S. Oral, [Troxel 2002]
o Projeto
e
análise
de
um
processador
de
rede
reconfigurável
dinamicamente.
•
University of California, Los Angeles, Department of Electrical Engineering, EUA,
Gohan Memik, Seda Ogrenci Memik e William H Mangione-Smith, [Memik 2002]
o Projeto de um bloco acelerador para aumento de desempenho no
processamento de aplicações de rede em um processador de rede usando
implementações em FPGAs.
•
Fundação Eurípides de Marília, Programa de Pós-graduação em Ciência da
Computação, Brasil, Prof. Dr. Edward Ordonez e mestrando Ricardo Petruzza.
o Projeto de um processador de rede reconfigurável usando FPGAs.
Apesar de nenhum destes grupos trabalharem com pesquisas relacionadas a processadores
de rede com chave crossbar usando ou não computação reconfigurável, verificamos algumas
que podem agregar conhecimento em trabalhos futuros do nosso grupo.
A primeira pesquisa [Suryanarayanan 2002] é sobre o simulador desenvolvido pelo grupo
da North Caroline University para estudo de um processador de rede da Cisco chamado
TOASTER que não conseguimos referências técnicas, além do próprio artigo. Desta forma,
pretendemos manter contato com o professor Gregory T. Byrd para uma maior aproximação
entre os grupos e futuros projetos relacionados a simuladores de processadores de rede. É
importante ressaltar que o processador TOASTER é proprietário da Cisco e, portanto, não está
disponível para venda e utilização por outros fabricantes, o que justifica a dificuldade de em
encontrar informações e datasheets sobre este processador.
A pesquisa [Liljeqvist 2002] relacionada com computação em grade usando
processadores de rede também é muito interessante devido as duas áreas recentes e que juntas
possuem poucas publicações de resultados.
No entanto, os grupos mais fortes são da Washington University in St. Louis e University
of Washington. Com estes grupos podemos agregar conhecimentos relativos à utilização de
processadores de rede em roteadores ativos, consumo de potência de processadores de rede,
análise de desempenho, benchmarks, entre outros.
30
Com relação aos trabalhos que usam computação reconfigurável, as pesquisas usam o
dispositivo FPGA apenas como um meio para a implementação da proposta de processador de
rede. O nosso maior interesse está na proposta de processador de rede reconfigurável e não no
dispositivo FPGA. No entanto, o bloco acelerador desenvolvido pelo grupo da University of
California, Los Angeles [Memik 2002] é interessante e pode agregar mais conhecimento na
nossa proposta de desenvolvimento de processador de rede. Este bloco acelerador é um ASIC e
pode ser encontrado em outras arquiteturas com outro nome e para outras funções. A palavra
“acelerador” apenas informa de forma mais direta, que este é um bloco responsável por
aumentar ou acelerar o desempenho de processamento, tal como uma microengine que é
encontrada em processadores de rede comerciais, tal como o IXP1200 [Intel 2000] e na nossa
proposta descrita no capítulo 4. No entanto, estes aceleradores possuem arquiteturas diferentes
e funções diferentes e podem não receber o nome “acelerador”.
Encontramos algumas dissertações e teses sobre processadores de rede concluídas, são
elas:
•
California Polytechnic State University, EUA, Edison David, “A Network Processor
Platform Implemented in Programmable Hardware”, 2003 [David 2003];
•
Virginia Polytechnic Institute, EUA, Scott J. Harper, “A Secure Adaptive Network
Processor”, 2003 [Harper 2003];
•
Chalmers University of Technology, Suécia, Björn Liljeqvist, “Visions and Facts – A
Survey of Network Processors”, 2003 [Liljeqvist 2003];
•
Royal Institute of Tecnology (KTH), Suécia, Daniel Hedberg, “Network Processor
based Exchange Terminal – Implementation and Evaluation”, 2002 [Hedberg 2002];
•
Lulea University of Technology, Suécia, Anders Stenberg, “Network Processor Core
Architecture”, 2002 [Stenberg 2002];
•
Linköpings Universitet, Suécia, Tomas Henriksson, “Hardware Architecture for
Protocol Processing”, 2001 [Henriksson 2002];
•
University of California Berkeley, EUA, Niraj Shah, “Understanding Network
Processors”, 2001 [Shah 2001].
Apesar das 4 dissertações suecas e 3 americanas, não encontramos publicações
significativas, relacionadas a processadores de rede, destes pesquisadores. A exceção do Niraj
Shah, que tem publicações no Workshop on Network Processors (2002 e 2003) [Shah 2002] (a
31
publicação de 2003 não está presente entre as referências) e do Björn Liljeqvist no IASTED
2002 [Liljeqvist 2002].
Apesar de nenhuma proposta ou pesquisa de processador de rede com chave crossbar
reconfigurável ter sido encontrada, selecionamos alguns trabalhos relacionados às chaves
crossbar utilizando dispositivos FPGAs para implementação:
•
Colm Fewer, et. al., “Chave Crossbar implementada em FPGAs”. [Fewer 2002,
2003];
•
Maryam Keyvani, Arash Haidari-Khabbaz, Simon Fraser University, Canadá,
“Implementação de uma chave crossbar simétrica de alta velocidade”. [HaidariKhabbaz 2000] [Keyvani 2001] (uma dissertação e uma monografia);
•
Holger Eggers, Patrick Lysaght, Hugh Dick e Gordon McGregor, University of
Strathclyde, Reino Unido, “Chave Crossbar implementada em FPGA”, [Eggers
1996].
No entanto, um artigo de 2002 sugeriu uma arquitetura de interconexão para
processadores de rede System-on-Chips baseando-se em características de flexibilidade, de
velocidade e custo. O artigo propõe uma arquitetura Network-on-Chip (NoC) baseada em uma
topologia de interconexão Octagon para processadores de rede, onde cada nó representa um
conjunto processador / memória.
•
Faraydon Karim e Anh Nguyen da STMicroelectronics, Sujit Dey da University of
San Diego, “An Interconnect Architecture for Networking Systems on Chips” [Karim
2002].
Neste tópico foram relacionadas algumas pesquisas, mas existem outros grupos não
citados. A maior concentração de artigos relacionados a processadores de rede pode ser
encontrada no evento Workshop on Network Processors and Applications. O tópico 2.5.3
apresenta alguns eventos importantes onde é possível encontrar artigos relacionados.
2.4.2 – Pesquisas em Indústrias
Neste tópico não entramos em detalhes técnicos sobre os processadores de rede
comerciais. Apresentamos algumas empresas, o nome dos principais processadores de rede e
alguns pontos interessantes da arquitetura ou da aplicação. O capítulo sobre processadores de
32
rede comerciais do nosso minicurso [Freitas 2003b] publicado na III Escola Regional de
Informática RJ/ES é apresentado no anexo 2 e descreve as principais características técnicas
dos processadores a seguir:
•
Intel: IXP1200 [Intel 2000]
o Duas unidades de processamento:
Processador StrongARM: construção e manutenção de tabelas e
gerenciamento de redes;
Microengines (seis no total): processamento e redirecionamento de
pacotes.
•
IBM: PowerNP NP4GS3 [Allen 2002] [IBM 2002]
o Duas unidades de processamento:
Embedded
Processor
Complex:
Contém
oito
Dyadic
Picoprocessors e nove co-processadores. Determina o que deve ser
feito com os frames recebidos;
Embedded PowerPC: Encaminhar e filtrar pacotes analisando
campos do protocolo IP (Internet Protocol), controlar protocolos
de roteamento, gerenciar, configurar, diagnosticar e suportar
agentes SNMP(Simple Network Management Protocol).
•
Motorola/C-Port: C-5 Family [C-Port 2002, 2001]
o Três unidades de processamento
Channel Processors: Processadores por porta (16 no total), que
recebem, processam e transmitem os dados;
Executive Processor: Processador principal para gerenciamento de
recursos;
Fabric Processor: Atua como uma interface de rede de alta
velocidade. Provê a conectividade com outros processadores de
rede.
•
Lucent/Agere: FPP/ASI/RSP [Agere 2001a, 2001c, 2001d]
o Conjunto de três processadores:
Fast Pattern Processor (FPP): gerenciamento e monitoramento de
redes, processamento de lista e controle de acesso;
Agere
System
Interface
(ASI):
atualizações
atualizações em filas, exceções e estatísticas;
em
tabelas,
33
Routing
Switching
Processor
(RSP):
enfileiramento,
gerenciamento de tráfego e modificação de pacote.
•
EZChip: NP-1 [EZChip 2002]
o Arquitetura composta por estágios:
TOPparse: identifica protocolos e extrai cabeçalhos dos pacotes;
TOPsearch: executa lookups em diferentes níveis;
TOPresolve: assinala pacotes para enfileirar ou enviar para portas;
TOPmodify: modifica conteúdo dos pacotes.
•
Sitera/Vitesse: Prism IQ2000 Family [Vitesse 2002]
o Roteamento de multi-protocolos complexos;
o Classificação, filtragem, inspeção e criptografia;
o Políticas de QoS;
o Multicast;
o Tradução de endereços de rede;
o Outras operações de processamento de pacotes.
•
Chameleon: CS2000 Family [Chameleon 2000]
o Arquitetura Reconfigurável (Reconfigurable Processing Fabric):
Unidades de Caminho de Dados;
Multiplicadores;
Memórias Locais;
Unidades de Controle.
o Principais aplicações:
Estações base sem fio de 2G e 3G;
Wireless Local Loop;
Voz sobre IP.
É importante ressaltar, que os trabalhos acadêmicos estão gerando resultados nos últimos
3 anos. Dentro do contexto de pesquisas relacionadas com processadores de rede, as indústrias
possuem uma história maior e mais sólida. Dentre os processadores relacionados o CS2000 é o
único que utiliza computação reconfigurável.
Nestes processadores apresentados, encontramos algumas características na arquitetura
que de forma direta ou indireta contribuíram na nossa proposta:
•
Processador principal de gerenciamento: Presente no IXP1200 da Intel, PowerNP
NP4GS3 da IBM e no C-5 da C-Port/Motorola.
•
Microengines: Presente no IXP1200 da Intel.
34
•
Computação Reconfigurável: Presente no CS2000 da Chameleon.
Apesar das arquiteturas dos processadores comerciais serem diferentes da nossa proposta,
a separação de funções de processamento surgiu por influência destes processadores. Portanto,
será visto no capítulo 4 que existem na arquitetura do R2NP (Reconfigurable RISC Network
Processor) um processador de gerenciamento e oito microengines. No entanto o CS2000 é a
exceção, a computação reconfigurável foi uma idéia anterior ao seu conhecimento, porém,
mostrou que o projeto de um processador de rede usando conceitos de computação
reconfigurável é viável e está sendo utilizado pela indústria.
2.4.3 – Eventos Relacionados
Neste tópico apresentamos os principais eventos relacionados às áreas de arquitetura e
redes de computadores e concepção de circuitos, que possuem espaço para publicações
referentes aos processadores de rede. É importante ressaltar dois eventos: O Workshop on
Network Processors and Applications, que é mais acadêmico e o Network Processors
Conference, mais ligado à indústria. No entanto, são os únicos eventos específicos sobre
processadores de rede. Podemos ressaltar também o ISCA (International Symposium on
Computer Architecture) e o HPCA (Symposium on High-Performance Computer Architecture)
por relacionarem o tema “Processadores de Rede” entre os tópicos principais de sugestão de
submissão como uma forma de incentivo para esta nova área do conhecimento.
•
Network Processors Conference (NPC);
•
Workshop on Network Processors and Applications (NP);
•
Annual International Symposium on Microarchitecture (MICRO);
•
Annual International Symposium on Computer Architecture (ISCA);
•
International Symposium on High-Performance Computer Architecture (HPCA);
•
International Conference on Computer Communication Network (ICCCN);
•
Conference on Local Computer Networks (LCN);
•
International Conference on Supercomputing (ICS);
•
International Symposium on Circuits and Systems (ISCAS);
•
International Conference on Computer Design (ICCD);
•
International Conference on Computer-Aided Design (ICCAD);
35
•
Symposium on Computer Architecture and High Performance Processing (SBACPAD), Brasil;
•
Symposium on Integrated Circuits and Systems Design (SBCCI), Brasil;
•
Workshop em Sistemas Computacionais de Alto Desempenho (WSCAD), Brasil;
•
Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC),
Brasil.
Os quatro últimos eventos são nacionais, mas apenas o WSCAD [Freitas 2002b, 2001,
2000b] publicou artigos sobre processadores de rede. No SBAC-PAD, SBCCI e no SBRC
nenhum artigo relacionado foi publicado.
36
3 – MATERIAIS E MÉTODO
Neste capítulo apresentamos os materiais e o método utilizado para o projeto e
desenvolvimento das arquiteturas propostas e obtenção dos resultados apresentados nesta
dissertação.
3.1 – MATERIAIS
Os materiais utilizados para obtenção dos resultados desta dissertação foram:
Os artigos e livros relacionados;
Os manuais e datasheets dos processadores de rede e de processadores de
propósito geral;
Compilador C++ Builder 5.0;
Simulador do processador de rede (CISC) desenvolvido [Freitas 2002a, 2002c];
Ambiente de projeto em VHDL da Xilinx (ISE Webpack);
Ambiente de simulação da Xilinx (ModelSim).
3.2 – MÉTODO
Definimos por começar o projeto da proposta de processador de rede através do modelo
CISC (Complex Instruction Set Computing) para depois projetar o modelo RISC (Reduced
Instruction Set Computing).
As etapas planejadas de acordo com os prazos estipulados para a conclusão da dissertação
são apresentadas a seguir:
1. Estudo do estado da arte (etapa executada continuamente durante todo o projeto);
2. Projeto do conjunto de instruções para o processador de rede CISC;
3. Projeto da microarquitetura do processador para o processador de rede CISC;
4. Projeto do simulador do conjunto de instruções e microarquitetura do processador
de rede CISC;
5. Verificação do processador de rede CISC usando o simulador projetado;
6. Verificação através de análise matemática do desempenho entre a proposta de
conjunto de instruções do modelo CISC e um GPP conceitual;
7. Projeto do conjunto de instruções para o processador de rede RISC;
8. Projeto da microarquitetura para o processador de rede RISC;
37
9. Projeto da arquitetura da Unidade de Comunicação Dedicada e Reconfigurável
(UCDR);
10. Verificação através de análise matemática do desempenho entre as propostas de
conjunto de instruções dos processadores de rede CISC e RISC (modelos sem e
com pipeline);
11. Análise da modelagem em grafos da implementação dinâmica de topologias;
12. Projeto das arquiteturas das chaves crossbar reconfiguráveis (versões de 1 e 2
bits);
13. Desenvolvimento dos códigos em VHDL para as chaves crossbar reconfiguráveis
(versões de 1 e 2 bits);
14. Simulação do código em VHDL do comportamento de uma chave crossbar
tradicional para chaveamento de pacotes de dados;
15. Simulação do código em VHDL do comportamento das chaves crossbar
reconfiguráveis de 1 e 2 bits para chaveamento de pacotes de dados e
implementação de topologias dinâmicas;
16. Análise de flexibilidade do uso de computação reconfigurável na crossbar;
17. Síntese dos resultados, conclusões e finalização da dissertação.
Desenvolvemos o simulador (NPSIM: Network Processor Simulator) [Freitas 2002a,
2002c] descrito no capítulo 4 e no anexo 1, para verificar o funcionamento do conjunto de
instruções e dos blocos funcionais da arquitetura do processador CISC proposto. A verificação
do simulador se fez através da análise do funcionamento correto dos programas apresentados
no tópico 5.1, utilizados para análise de desempenho entre os conjuntos de instruções da nossa
proposta e um GPP conceitual.
Com base no conjunto de instruções CISC foi desenvolvido um novo conjunto, utilizando
conceitos de projeto RISC para melhoria do desempenho das instruções propostas inicialmente.
Após o projeto do novo conjunto de instruções, que passou a utilizar pipeline [Patterson 2000],
modelamos matematicamente o ganho de desempenho obtido, considerando a nova proposta
RISC e a anterior CISC com base nos mesmos programas já verificados.
Simultaneamente ao processo de melhoria do conjunto de instruções CISC, foi realizado
um novo projeto da arquitetura do processador de rede proposto para uma versão RISC. A
alteração principal foi na arquitetura dos blocos pertencentes à estrutura de recebimento e
chaveamento de pacotes de dados de entrada. Foram projetadas propostas de multiplexadores
reconfiguráveis, microengines, buffers reconfiguráveis e uma chave crossbar reconfigurável,
38
dando origem a uma grande Unidade de Comunicação Dedicada e Reconfigurável (UCDR). O
objetivo desta unidade é garantir uma maior flexibilidade e desempenho no processamento e
chaveamento dos pacotes de dados em relação à proposta anterior que possuía apenas os
buffers e a chave crossbar reconfigurável.
Veremos no tópico 4.2, que a chave crossbar reconfigurável foi proposta em duas versões
de arquitetura (1 e 2 bits). No entanto, estes dois projetos pertencem apenas à proposta RISC.
No início do projeto da arquitetura CISC a chave crossbar não era reconfigurável. A versão de
chave crossbar reconfigurável de 1 bit foi adicionado ao processador de rede CISC durante o
projeto.
A definição da chave crossbar como ponto final para conclusão do mestrado, foi baseada
na importância dos resultados da aplicação da computação reconfigurável (flexibilidade e
desempenho de operação). É importante ressaltar, que a escolha da chave crossbar entre os
demais tipos de switching fabrics se deve à vantagem de sua estrutura ser baseada em uma
matriz de conexões, que favorece a implementação dinâmica de topologias em tempo de
execução, conforme citamos nos objetivos e simulações do tópico 5.3.
Sendo assim, concluímos que além da arquitetura dedicada do processador, a unidade de
chaveamento de pacotes de dados e de implementação dinâmica de topologias (a chave
crossbar reconfigurável) é uma das principais contribuições do projeto. Por este motivo,
adotamos como prioritárias para a finalização desta dissertação as etapas de projeto e
simulação comportamental da chave crossbar reconfigurável.
Estes resultados sendo analisados servem como direcionamento para a aplicação do
conceito de reconfiguração em outros blocos funcionais da UCDR e por conseqüência no
processador de rede proposto.
39
4 – PROPOSTA DE UM PROCESSADOR DE REDE RECONFIGURÁVEL
Neste capítulo apresentamos as propostas de arquiteturas do processador de rede com
chave crossbar reconfigurável [Freitas 2003a, 2002b, 2001, 2000a, 2000b]. De acordo com o
que já foi descrito iremos apresentar no primeiro tópico deste capítulo a arquitetura CISC do
processador de rede proposto (RCNP: Reconfigurable CISC Network Processor). Após a
apresentação da proposta de arquitetura de processador de rede RISC (R2NP: Reconfigurable
RISC Network Processor) e da Unidade de Comunicação Dedicada e Reconfigurável (UCDR),
iremos apresentar em outro tópico a arquitetura da chave crossbar reconfigurável. Sendo assim,
neste capítulo apresentamos os principais objetos de estudo e de análise de resultados desta
dissertação.
É importante ressaltar que, as arquiteturas propostas e desenvolvidas para o processador
de rede possuem vários circuitos dedicados que após a prototipação poderão fazer parte do
mesmo chip. Ou seja, o nosso projeto descreve uma arquitetura de processador de rede que
utiliza conceitos Sytem-on-Chip (SoC). Desta forma, pretendemos obter ao final do projeto um
maior desempenho devido principalmente à relação de proximidade dos blocos funcionais do
processador. Ressaltamos a UCDR (Unidade de Comunicação Dedicada e Reconfigurável) e
hierarquicamente a chave crossbar reconfigurável, como os principais blocos construtivos
dedicados que serão inseridos dentro do mesmo circuito integrado do processador de rede
proposto com características reconfiguráveis.
4.1 – ARQUITETURA DO PROCESSADOR DE REDE
Serão mostradas duas arquiteturas: uma CISC e outra RISC. O simulador NPSIM
(Network Processor Simulator) já citado em tópicos anteriores será utilizado para apresentar e
verificar a arquitetura CISC.
As características pertencentes às duas arquiteturas são:
•
Oito portas de entrada e oito de saída;
•
Buffers de entrada;
•
Chave crossbar;
•
Interface PCI;
•
Interface dedicada de comunicação;
•
Módulo DMA (Acesso Direto à Memória).
40
É importante citar que, a arquitetura CISC apesar de não se tratar do melhor modelo de
projeto para processadores de rede e também não encontrado entre os processadores de rede
comerciais, foi escolhido para dar início aos estudos por se tratar de um modelo inicial na
evolução dos processadores e, portanto, como seqüência didática para estudos e projeto das
arquiteturas.
4.1.1 – Arquitetura e Conjunto de Instruções CISC
O processador RCNP (Reconfigurable CISC Network Processor) [Freitas 2001, 2000a,
2000b] é apresentado através do simulador funcional (NPSIM: Network Processor Simulator)
[Freitas 2002a, 2002c] desenvolvido para testes de verificação funcional da arquitetura e do
conjunto de instruções.
O principal módulo de interface do NPSIM (Anexo 1) é apresentado na figura 12. Este
módulo contém os registradores dedicados e de propósito geral, a memória e o editor do código
assembly.
Figura 12 – Módulo de interface principal do NPSIM
Através do NPSIM foi possível verificar os resultados de comparação de desempenho
apresentados no tópico 5.1.
41
As figuras 13, 14, 15 e 16 são referentes aos módulos de interface de ajuda do NPSIM,
onde podemos encontrar informações relativas à arquitetura e ao conjunto de instruções do
RCNP. Os detalhes técnicos da versão CISC podem ser obtidos nas referências [Freitas 2001,
2000a, 2000b].
Figura 13 – Arquitetura do RCNP apresentada módulo de interface do NPSIM
A arquitetura básica é a seguinte (figura 13):
1. Oito portas de entrada
Buffers específicos para cada entrada
Buffers reconfiguráveis.
2. Oito portas de saída
3. Chave crossbar (Bloco Seletor de Conexão – Conexão entre as portas de entrada e
saída e registradores)
4. Módulo DMA (Acesso Direto à Memória)
5. Oito registradores de propósito geral
6. Barramento de dados de 8 bits e 24 bits de endereçamento
7. Memória de tamanho máximo de 16Mbytes (palavra de memória de 1byte)
A figura 14 (módulo do NPSIM) descreve e ilustra algumas características importantes da
arquitetura do RCNP.
42
Figura 14 – Descrição de parte da arquitetura do RCNP no módulo de interface do NPSIM
A figura 15 ilustra o conjunto de instruções do RCNP. Foram acrescentadas durante o
projeto deste conjunto algumas instruções que inicialmente não faziam parte do primeiro
conjunto proposto, gerando a tabela resultante ilustrada na figura 15.
Figura 15 – Conjunto de instruções no módulo de interface do NPSIM
43
Alguns exemplos de instruções:
1. Conjunto de instruções de propósito geral
Instruções aritméticas (Ex. ADD e SUB)
Instruções lógicas (Ex. AND e OR)
Instruções de acesso à memória (Ex. LOD, STO e ADI)
Instruções de desvio (Ex. JMP e JNZ)
2. Sub-conjunto de instruções de rede
Leitura da porta de entrada (Ex. ENT)
Escrita na porta de saída (Ex. SAI)
Controle da crossbar (Ex. SEC)
Controle do reg. de status (Ex. LRS e SRS)
A figura 16 descreve os efeitos principais da utilização das instruções propostas.
Figura 16 – Descrição das instruções no módulo de interface do NPSIM
Por se tratar de uma arquitetura CISC, algumas instruções além de load e store também
possuem no formato de instrução um campo específico para acesso à memória. Estes tipos de
instruções não mais existirão no projeto RISC, uma vez que o acesso à memória será restrito a
44
poucas instruções. Outra característica deste projeto é o microcódigo (palavra de controle)
gerado pela unidade de controle. Cada estágio da instrução (Ex. busca, decodificação e
execução) é representado por um microcódigo diferente. O caminho de dados do processador
RCNP não possui estrutura em pipeline, o que obriga a execução de uma instrução após a
outra, seqüencialmente. O ponto forte desta arquitetura é a unidade de comunicação composta
por portas de entrada e saída, chave crossbar e buffers reconfiguráveis, que permaneceram no
projeto RISC (chamada de UCDR) com algumas diferenças. Seu conjunto de instruções
também mostrou um ganho considerável em relação a um processador de propósito geral
conceitual, como será descrito no tópico de resultados (capítulo 5).
4.1.2 – Arquitetura e Conjunto de Instruções RISC
O projeto R2NP (Reconfigurable RISC Network Processor) [Freitas 2003a, 2002b] tem
como objetivo melhorar o caminho de dados, a arquitetura da unidade de comunicação de
dados, o formato e o conjunto de instruções, com o intuito de aumentar o desempenho e vazão
dos pacotes de dados. Neste projeto cada instrução possui um formato fixo, o que facilita o
estágio de decodificação de instruções. A figura 17 ilustra o formato de instruções do R2NP.
Figura 17 – Formato das instruções do R2NP
Exemplos:
Formato 1: ADD (operador) A (operando 1), B (operando 2), C (operando 3)
Formato 2: MOV (operador) A (operando 1), B (operando 2)
Formato 3: LRS (operador) A (operando 1)
Formato 4: HLT (operador)
45
A tabela 1 relaciona todas as instruções do R2NP e a tabela 2 descreve a função das
instruções de rede.
Tabela 1 – Instruções do R2NP
ADD A,B,C
SUB A,B,C
MUL A,B,C
DIV A,B,C
AND A,B,C
OU A,B,C
XOR A,B,C
NEG A
ROD A
ROE A
Propósito geral
MOV A,B
SPUSH A
INC A
LPOP A
DEC A
JMP A
LOD A,End32
JZ A
LDA A,End16
JMZ A
LOX A,B
JMI A
LDI A,Imed16
JNZ A
STO End32,A
JNI A
STR End16,A
CALL A
STX A,B
RET
CONV
Rede
FCX A,B,C
LOB A
BRC A
SAI A,B
LRS A
SRS A
SEC A,B
ENT A,B,C
No caso de instruções de load e store, existem dois tipos de instruções: uma que acessa
apenas a memória interna de 64 kbytes (LDA, LDI, STR) e outra (LOD, STO) que acessa
memória interna e externa de tamanho máximo 16Gbytes. Quando se utiliza o segundo tipo, a
próxima posição de memória guarda o endereço de 32 bits. Portanto as instruções LOD e STO
utilizam duas células de memória e por isso é necessário um ciclo de busca a mais para o
endereço. No entanto, as instruções LDA, LDI e STR, que precisam de apenas 16 bits para
endereçar a memória interna, ocupam apenas uma célula de memória e utilizam apenas um
ciclo de busca.
Tabela 2 – Descrição das instruções de rede do R2NP
Rede
ENT A,B,C
BRC A
SAI A,B
LRS A
SRS A
SEC A,B
FCX A,B,C
LOB A
Descrição do funcionamento
Lê buffer (reg. B) posição (reg. C) e carrega no reg. A
Broadcast do buffer (reg. A) para todas as saídas
Valor do reg. A para saída (reg. B)
Carrega no reg. Status valor do reg. A
Carrega no reg. A valor do reg. de Status
Redireciona buffer (reg. A) para saída (reg. B)
Fecha conexão entre buffer (reg.A) e saída (reg. B)
Reg. C carrega byte de desconexão no buffer (reg. A)
Carrega no reg. A, no da porta de entrada que recebeu o
pacote
46
O pipeline de instrução está dividido em 5 estágios (figura 18):
Busca da instrução (B).
Decodificação da instrução (D). Leitura em banco de registradores.
Execução da instrução (E).
Acesso de escrita ou leitura na memória (M) ou Buffer reconfigurável (BF).
Resultados (R). Escrita em banco de registradores.
Figura 18 – Estágios de pipeline do R2NP
A diferença básica para o modelo conceitual dos estágios de pipeline é a inclusão do
estágio BF (Buffer Reconfigurável). Este estágio está sobreposto ao estágio de acesso à
memória, porque os dois não são executados por uma mesma instrução. Uma instrução load
utiliza o estágio M e uma instrução de entrada (ENT) utiliza o estágio BF. É importante
ressaltar, que hierarquicamente os buffers estão em melhor posição do que a memória
(processador
registradores
buffers
memória). Para esta hierarquia a melhor posição é
aquela que se encontra mais próxima das saídas de dados. A figura 19 ilustra a hierarquia de
memória (visão da saída de dados) dos processadores RCNP e R2NP e a evolução do projeto.
A hierarquia de memória padrão está em relação ao processador, conforme a primeira
hierarquia da figura 19. Porém, fizemos uma análise da hierarquia em função da saída de
dados, já que o processamento está dividido em microengines e Processador de Gerenciamento,
conforme será descrito nos tópicos seguintes.
47
Figura 19 – Hierarquia de memória (visão da saída de dados)
As principais características da arquitetura são:
1. Oito microengines (ASICs – Application-Specific Integrated Circuits substituindo
cada buffer específico de entrada do projeto RCNP).
2. Multiplexador, crossbar e buffers reconfiguráveis
3. DMA (Acesso Direto à Memória) – Circuito dedicado (ASIC)
4. Memória interna e cache do Processador de Gerenciamento.
5. Quantidade total (máximo) de registradores: 256 (palavra de 64 bits)
6. Barramento de dados e de endereço de 32 bits
7. Memória de tamanho máximo de 16Gbytes (palavra de 32 bits / 4G células)
A figura 20 ilustra a arquitetura do R2NP.
48
Figura 20 – Arquitetura do R2NP
O bloco chamado Processador de Gerenciamento corresponde à unidade principal de
processamento. Neste bloco estão situados os registradores de propósito geral e também as
caches de dados e de instruções. Este processador de gerenciamento é responsável pela leitura
e execução de todas as instruções do R2NP. Nele estão presentes as unidades lógica, aritmética
e de controle de pipeline. Este processador define como os vários blocos construtivos da
arquitetura irão trabalhar, inclusive as microengines. Este processador é considerado a unidade
principal responsável pelas tarefas que requerem um detalhamento maior, tais como:
construção e manutenção de tabelas e gerenciamento de redes. O processador de gerenciamento
e as microengines são blocos projetados a exemplo das arquiteturas de processadores
comerciais, conforme citado nos trabalhos correlatos.
A Unidade de Reconfiguração é o bloco responsável pelo controle e envio dos bits de
reconfiguração para o multiplexador reconfigurável, buffers reconfiguráveis e chave crossbar
reconfigurável. Este bloco é gerenciado pelo processador de gerenciamento, e pelas
microengines, que podem receber instruções através de pacotes de rede.
Os detalhes de funcionamento da unidade de comunicação dedicada e reconfigurável
(UCDR), onde está presente a chave crossbar reconfigurável, estão descritos no tópico
seguinte. A UCDR com todos os seus blocos funcionais só existe na versão RISC.
49
4.1.3 – Unidade de Comunicação Dedicada e Reconfigurável (UCDR)
A UCDR (figura 21) é a grande unidade de comunicação de dados do R2NP. Nesta
unidade são feitos o recebimento, processamento e saída de pacotes de dados, muitas vezes sem
a necessidade do uso do processador de gerenciamento. Seu principal objetivo é aumentar a
flexibilidade e velocidade de processamento relacionados aos pacotes de entrada. A UCDR faz
parte da arquitetura do R2NP, e utiliza computação reconfigurável como forma de obter
flexibilidade, escalabilidade, vazão e desempenho de processamento. Desta forma, a UCDR
também agrega ao R2NP o conceito System-on-Chip (SoC) conforme já havíamos descrito.
Figura 21 – Arquitetura da UCDR
Os principais blocos funcionais da UCDR são:
A microengine é um circuito dedicado e programável que tem a função de tomar decisões
preliminares lendo espaços de memória, onde estão guardadas informações referentes ao
protocolo, redirecionando os pacotes para os buffers reconfiguráveis ou para saída através da
chave crossbar. As microengines também podem alterar ou acrescentar informações nos
cabeçalhos dos pacotes (redes ativas, por exemplo) sendo útil durante o processamento interno
do R2NP, como será visto no tópico 4.2.2. Cada microengine pode ser utilizada para funções
diferentes (depende do programa). Ela pode redirecionar um pacote de entrada diretamente
para a chave crossbar reconfigurável, que enviará para a saída, ou pode não fazer nada,
deixando que todos os pacotes de entrada sejam enviados para os buffers reconfiguráveis
aumentando o trabalho de processamento do processador de gerenciamento.
50
Os buffers reconfiguráveis são espaços de alocação dos pacotes de dados antes que estes
pacotes sejam enviados para a saída. Estes buffers são utilizados como armazenamento
temporário de pacotes evitando que estes dados sejam guardados em memória quando a saída
está sendo utilizada (ocupada). Desta forma, o projeto destes buffers implementa outro nível na
hierarquia tradicional de memória de acordo com a ilustração da figura 19. O conceito de
reconfiguração foi adotado para melhorar o desempenho do armazenamento de pacotes. Ou
seja, em tempo de execução um conjunto de buffers é preparado para servir de espaço de
armazenamento de tamanho o mais próximo possível do pacote de dados que será recebido.
Neste caso, reservamos mais espaço livre para um novo armazenamento de dados. É
importante ressaltar, que estes pacotes somente utilizarão estes buffers caso as saídas estejam
congestionadas (ocupadas) ou um programa indique o caminho de armazenamento em buffers
de forma obrigatória.
A função do multiplexador é possibilitar a reutilização de uma porta de entrada, que
estava ligada a uma microengine. Pode-se perder uma microengine, mas continua-se com 8
portas. Sua utilização também é importante como forma de liberar uma microengine para
trabalhar de forma independente do restante. Ou seja, podemos usar uma microengine para
processar alguma tarefa que seja diferente das demais e que não seja executada pelo
processador de gerenciamento para evitar uma sobrecarga de processamento, ou diminuição de
capacidade de vazão de dados.
A Chave Crossbar Reconfigurável é similar a uma matriz interna de conexões capaz de
redirecionar os pacotes das portas de entrada para as portas de saída. No entanto, ela é diferente
de uma crossbar tradicional devido ao fato de haver a possibilidade de alteração das conexões
e implementação de topologias no tempo e no espaço. Os detalhes da chave crossbar
reconfigurável estão descritos no tópico 4.2.
Do ponto de vista da pesquisa, a UCDR é o grande bloco reconfigurável que garante ao
R2NP maior desempenho e flexibilidade de operação.
4.2 – ARQUITETURA DA CHAVE CROSSBAR RECONFIGURÁVEL
Uma chave crossbar tradicional, como mostrado no tópico 2.1, é capaz de fechar, em
intervalos de tempo, a mesma entrada com diversas saídas e vice-e-versa. Portanto, não é
possível implementar uma topologia fixa (no espaço), já que as diversas conexões são abertas
ou fechadas ao longo do tempo. Entretanto, a nossa proposta de chave crossbar reconfigurável
51
(figura 22), além de funcionar como uma chave crossbar tradicional, implementa topologias
também no espaço através de seus bits de reconfiguração.
Figura 22 – Bloco da chave crossbar reconfigurável
A proposta de reconfiguração da chave crossbar não se aplica em mudança de concepção
de circuito. Não há diminuição de latches ou flip-flops quando se implementa uma nova
topologia. Após a mudança nos bits de reconfiguração, o mesmo circuito da chave crossbar irá
modificar os nós habilitados para o fechamento de circuito ou simplesmente fechar ou abrir um
circuito de entrada e saída. Ou seja, os conceitos de reconfiguração serão aplicados para
implementar topologias sobre a chave crossbar e não para mudar a implementação da mesma.
Portanto, a reconfiguração não é dependente de um dispositivo programável (Ex. FPGA).
Durante os primeiros resultados de simulação da chave crossbar reconfigurável em
VHDL, definimos duas arquiteturas reconfiguráveis: a primeira de 1 bit e a segunda de 2 bits.
Estes bits representam os sinais de entrada da chave crossbar responsáveis pela reconfiguração.
A chave crossbar reconfigurável (figura 23 e 25) possui algumas entradas relacionadas ao
barramento de dados e ao registrador de Status. O barramento de dados é por onde trafegam os
dados utilizados pelo processador e que, através de instruções podem interferir no chaveamento
ou não dos nós que ligam as entradas e saídas. O registrador de Status (figura 13 e 20) é um
registrador de 8 bits responsável por armazenar quais são as saídas que estão sendo utilizadas.
Através deste registrador é possível evitar conflitos no envio de dados para as saídas. Estes dois
barramentos são comuns às duas arquiteturas, havendo alteração apenas no barramento de
reconfiguração, que é o barramento usado pela unidade de reconfiguração, responsável pelo
controle dos bits de reconfiguração.
Existe também em cada nó (ponto) de conexão da chave crossbar um validador de
endereços que tem a função de comparar se o endereço no cabeçalho do pacote é igual ao seu
ponto de conexão. Caso seja igual, o pacote é redirecionado para a saída. Isto significa que, a
microengine ao receber um pacote, lê o cabeçalho e descobre que o destino está na saída 3. A
microengine acrescenta neste cabeçalho (ou um pré-cabeçalho) o valor 3 e quando o pacote
52
passar pelo validador (ou comparador) de endereços do ponto de conexão da saída 3, o mesmo
será redirecionado. Desta forma evitamos a utilização do processador de gerenciamento para
descobrir destinos e rotear pacotes, aumentando o desempenho de roteamento.
Nos tópicos seguintes iremos apresentar as diferenças das duas arquiteturas e como elas
funcionam.
4.2.1 – Chave Crossbar Reconfigurável de 1 bit
Nesta arquitetura, os bits de reconfiguração funcionam como sinais de fechamento ou de
abertura dos nós de conexão. Adotamos o bit 0 como nó aberto e bit 1 como nó fechado.
Quando precisamos implementar uma topologia na chave crossbar apenas entramos no
barramento de reconfiguração com a matriz de reconfiguração, composta por todos os bits ou
apenas com os bits dos nós que precisam ser alterados. Após a reconfiguração, a topologia
desejada está implementada na chave crossbar e somente através dos pontos conectados é que
poderá haver comunicação entre as entradas e saídas.
De acordo com a figura 23, a chave crossbar de 1 bit possui uma barramento de dados de
32 bits (referente à arquitetura do R2NP), um barramento de 8 bits (referente ao registrador de
status do arquitetura do R2NP) e um barramento interno de reconfiguração de 64 bits, que
define quais nós estão fechados e portanto, qual topologia foi implementada. Para esta chave
crossbar (quadrada) existem 8 entradas e 8 saídas ou 64 nós reconfiguráveis. Esta não é a
realidade da chave crossbar reconfigurável do nosso processador de rede. De acordo com a
arquitetura da UCDR, possuímos além das entradas que vêm das microengines, as entradas
originadas dos buffers reconfiguráveis. Como esta quantidade ainda não está definida, a chave
crossbar será apresentada ao longo desta dissertação com 8 entradas e 8 saídas ou 4 entradas e
4 saídas.
Figura 23 – Arquitetura da chave crossbar de 1 bit
53
Portanto, a chave crossbar reconfigurável após receber os bits de reconfiguração não
permite que instruções do processador de gerenciamento possam interferir e alterar as conexões
realizadas. Esta arquitetura de 1 bit possui flexibilidade de implementação de topologias
durante tempo de execução, mas não permite que se tenha flexibilidade de alteração pelo
processador de gerenciamento. Esta limitação impede, por exemplo, que programas não
autorizados alterem a topologia escolhida e que muitas vezes mantém a segurança de uma rede.
A grande vantagem é contar com uma conexão pronta para manter a comunicação entre
os pontos de origem e destino, sem perder tempo de processamento e fechamento de conexões,
que poderiam retardar o envio de um pacote de dados. O processador de gerenciamento apenas
irá processar questões relativas aos parâmetros de qualidade de serviço, por exemplo.
A figura 24 ilustra uma topologia anel criada na chave crossbar reconfigurável. Somente
os nós que receberam o bit 1 foram fechados e os demais ficaram abertos. Neste caso, partindo
do suposto que cada entrada e respectiva saída estão conectadas a computadores, somente
haverá comunicação, por exemplo, do computador 1 para os computadores 2 e 8 e vice-e-versa.
Nesta topologia o computador 1 somente irá se comunicar com o computador 5 se houver a
passagem do pacote entre os caminhos 2, 3 e 4 ou 8, 7 e 6.
Figura 24 – Topologia implementada usando chave crossbar de 1 bit
Esta arquitetura tem como característica a flexibilidade de implementação dinâmica de
topologias através de bits de reconfiguração, mas retira a intervenção do processador de
gerenciamento no fechamento ou abertura de conexões na chave crossbar. É importante
ressaltar que, apesar do processador não conseguir alterar diretamente um nó reconfigurado, ele
consegue interferir na unidade de controle de reconfiguração, informando a necessidade de
alteração da topologia escolhida. Neste caso, até que a nova topologia fosse configurada, o
pacote de entrada poderia ser armazenado temporariamente em um buffer reconfigurável. A
54
não interferência direta do processador de gerenciamento cria níveis de segurança e acesso para
implementação de topologias. Desta forma, mesmo que o usuário do processador altere o
programa, para que ele consiga reconfigurar a topologia diretamente na chave crossbar, ele não
terá sucesso. Os motivos principais para esta restrição se devem a questões de segurança em
hardware. Sendo assim, uma topologia criada significa conexão e comunicação permitida. Se
houver uma falha no programa executado pelo processador uma conexão não permitida poderá
ser fechada.
Não consideramos esta arquitetura de 1 bit a mais adequada por julgarmos interessante,
que em determinadas situações, o processador de gerenciamento (através de suas instruções)
possa realizar o fechamento ou abertura de uma conexão. Por este motivo, desenvolvemos a
proposta da chave crossbar de 2 bits que é apresentada no tópico 4.2.2. No entanto, mostramos
no capítulo 5 (Resultados) que a implementação dinâmica de topologias através da chave
crossbar reconfigurável de 1 bit se mostrou melhor do que em uma chave crossbar tradicional,
quando se tem um padrão de comunicação entre os nós da topologia de rede.
4.2.2 – Chave Crossbar Reconfigurável de 2 bits
Nesta nova arquitetura, procuramos criar a possibilidade de intervenção do processador
de gerenciamento na topologia implementada pela chave crossbar reconfigurável. Por este
motivo aumentamos os bits de reconfiguração de 1 para 2. Por conseqüência o barramento de
reconfiguração (para esta chave crossbar) aumentou para 128 bits (64 nós de conexão).
Conforme ilustrado pela figura 25, é possível verificar que, para fechar um nó seria
necessário dois bits iguais a 1 e para abrir um nó dois bits iguais a 0. No entanto, as variações
01 e 10 poderão ser usadas pelo processador de gerenciamento da seguinte forma:
•
01: Nó aberto. O processador de gerenciamento pode acessar e fechar este nó
utilizando os bits 10.
•
10: Nó fechado. O processador de gerenciamento pode acessar e abrir este nó
utilizando os bits 01.
Sendo assim, 00 e 01 significam nó aberto e 11 e 10 significam no fechado. A diferença é
que nas situações em que os bits de reconfiguração são iguais (00 e 11) o processador de
gerenciamento não terá acesso para alteração e implementação de novas topologias.
É importante ressaltar que, as quatro variações (00, 01, 10, 11) são bits de reconfiguração,
porém os pares diferentes e os pares iguais permitem ou não a intervenção de instruções do
processador de gerenciamento para implementação de topologias. O ganho que se tem em
55
adotar a arquitetura de 2 bits está diretamente relacionado com o aumento de flexibilidade. A
questão é que agora podemos implementar uma topologia na chave crossbar através da unidade
de reconfiguração e através do processador de gerenciamento.
Figura 25 – Arquitetura da chave crossbar de 2 bits
A figura 26 ilustra o mesmo exemplo citado para a chave de 1 bit. Implementando a
topologia em anel é possível fechar outras conexões e permitir um maior número de
comunicações entre os pontos (entradas e saídas). Supondo novamente a existência de
computadores em cada entrada e saída desta topologia, podemos observar que inicialmente as
conexões obedecem a mesma ordem definida para a chave crossbar de 1 bit. No entanto se
fosse necessário que o computador 1 se comunicasse com outros computadores, os bits 01
enviados para os nós E1S3, E1S4, E1S5, E1S6 e E1S7 iriam permitir o acesso de instruções do
processador de gerenciamento e conseqüentemente o fechamento (através dos bits 10) destas
conexões. Isto pode ser muito útil se for constatado uma permanente comunicação entre o
computador 1 e outros micros. Evitaria-se um aumento de tráfego pelos caminhos
intermediários, permitindo um maior desempenho e vazão de dados.
56
Figura 26 – Topologia implementada usando chave crossbar de 2 bits
Apesar da melhoria da arquitetura, poderíamos fazer a seguinte pergunta: E se o conjunto
de bits 11 precisasse se tornar 00 sem reconfiguração, as instruções do processador
conseguiriam alterar?
A resposta é não. Partimos do princípio de que uma conexão fechada é uma possibilidade
autorizada de comunicação implementada pelo gerenciador dos bits de reconfiguração. Caso
fosse necessário impedir esta comunicação, sem alteração de bits de reconfiguração, a solução
seria através das microengines. As microengines têm um papel importante em todo o
processamento de pacotes porque ela é o primeiro ponto de processamento de entrada. A
microengine pode ler o cabeçalho e acrescentar informações, que barrariam o pacote de dados
quando lidas em cada ponto de conexão da chave crossbar, evitando o seu envio até o destino.
Neste caso, a atuação de uma microengine seria mais rápida do que as próprias instruções do
processador, pela sua própria localização na arquitetura do R2NP (primeiro ponto de
processamento).
As topologias realizadas no espaço da chave crossbar reconfigurável (1 ou 2 bits) podem
representar uma segmentação de rede, permitindo a comunicação em grupos separados de
computadores ou sub-redes. É possível implementar broadcast e multicast sem que haja
conflitos. Quando duas entradas enviam dados simultaneamente para uma única saída, pode
ocorrer um conflito. Neste caso, técnicas como multiplexação são mais eficientes do que um
processador lendo cabeçalhos e enviando instruções para abertura ou fechamento de conexões.
Veremos no capítulo de resultados que a técnica utilizada para evitar conflitos foi através de
um registrador de controle. Apesar de não ser tão eficiente, é bastante simples e foi útil para
que conseguíssemos verificar a flexibilidade do chaveamento de dados e implementação
dinâmica de topologias da proposta da chave crossbar reconfigurável.
57
5 – RESULTADOS
Neste capítulo apresentamos os principais resultados [Freitas 2003a, 2002a, 2002b,
2002c, 2001] obtidos durante a execução da pesquisa. Iremos destacar algumas análises
matemáticas e simulações realizadas para verificar o comportamento das arquiteturas e dos
conjuntos de instruções das propostas de processadores de rede.
É importante ressaltar, que apesar deste capítulo abordar aspectos de análise, simulação e
verificação, podemos considerar as propostas de arquiteturas apresentadas no capítulo anterior
como importantes resultados da pesquisa. O desenvolvimento de modelos de arquiteturas do
processador de rede, da UCDR e da chave crossbar reconfigurável também são resultados
alcançados que compõem o processo de consolidação dos objetivos, metas e método adotado.
5.1 – ANÁLISE DE DESEMPENHO DAS ARQUITETURAS E DOS CONJUNTOS DE
INSTRUÇÕES
Neste tópico apresentamos resultados comparativos de desempenho dos conjuntos de
instruções projetados na versão RCNP (Reconfigurable CISC Network Processor) e na versão
R2NP (Reconfigurable RISC Network Processor). É feita uma comparação de desempenho
entre o processador RCNP e um processador GPP conceitual, e posteriormente, entre os
processadores RCNP e R2NP. Ao final mostramos qual o impacto do projeto e do uso da chave
crossbar reconfigurável na utilização das instruções pelos processadores de rede.
5.1.1 – Análise de Desempenho do RCNP em Relação a um GPP Conceitual
Os códigos, descritos a seguir, estão baseados em duas topologias (Figuras 27 e 28), onde
cada nó representa um processador (RCNP). Foram implementados dois algoritmos de
roteamento e não foi levada em consideração a possibilidade de conflito na saída de pacotes.
Por isso, o registrador de Status não foi verificado em nenhum dos algoritmos.
Estes códigos foram simulados usando o NPSIM (Network Processor Simulator), descrito
no anexo 1. Como estamos interessados em verificar o desempenho das instruções não
utilizaremos a flexibilidade da chave crossbar. Portanto, podemos considerar que os bits de
reconfiguração foram setados para 01 ou 10. Desta forma, toda a responsabilidade de
roteamento será do processador de gerenciamento e não da implementação dinâmica de
58
topologias pela chave crossbar. Podemos considerar também, que estamos usando uma chave
crossbar tradicional.
Figura 27 – Topologia hipercubo
•
Figura 28 – Topologia árvore
Topologia baseada em Hipercubo
o Cada endereço do hipercubo tem apenas 1 bit de diferença para os
endereços dos nós adjacentes (figura 27). Este algoritmo foi desenvolvido
para o processador P3. Para esta topologia foi desenvolvido o seguinte
código de roteamento (Tabela 3):
Tabela 3 – Programa assembly para topologia hipercubo (ISA RCNP)
LDX F,000006
LDI D,03
PUT
SUI B,00
JZ 000000
LDI B,00
LDI C,05
ENT BC
XOR D
MOV E,A
JZ F
ANI A,01
JMZ 000029
ANI E,02
JMZ 000025
LDI B,03
SEC
JMP F
LDI B,02
SEC
JMP F
LDI B,01
SEC
JMP F
//Endereço de PUT
//Processador = P3
//Busca buffer permanente
//B recebe valor do buffer.
//Se for zero, não existe pacote
//Posição que se encontra endereço.
//Posição que se encontra endereço.
//Busca o endereço no buffer
//Operação XOR (A ⊕ D)
//Move dado de reg. A para reg. E
//Se chegou ao destino, volta a PUT
//Senão verifica se é saída 01
//Se for maior é verdadeiro e jump S1
//Verifica se é saída 02
//Se for maior é verdadeiro e jump S2
//Saída 3, carregada em B
//Redireciona, buffer entrada OS 03
//Voltar a PUT
//Saída 2, carregada em B
//Redireciona, buffer entrada OS 02
//Voltar a PUT
//Saída 1, carregada em B
//Redireciona, buffer entrada OS 01
//Voltar a PUT
59
•
Topologia baseada em árvore:
o O endereço de cada nó está no desenho da topologia ilustrada na figura 28.
À esquerda de cada nó, sempre existe um endereço de menor valor. À
direita, sempre um endereço de maior valor. O algoritmo foi desenvolvido
para o processador P 06 e para esta topologia foi desenvolvido o seguinte
código de roteamento (Tabela 4):
Tabela 4 – Programa assembly para topologia árvore (ISA RCNP)
LDI D,06
PUT
SUI B,00
JZ 000025
LDI B,00
LDI C,05
ENT BC
SUB D
JMI 00001A
LDI B,04
SEC
JMP 000002
JZ 000025
LDI B,05
SEC
JMP 000002
HLT
//Processador 06 – P 06
//Busca aleatória do buffer de entrada
//B recebe valor do buffer.
//Se for zero, não existe pacote.
//Posição que se encontra endereço.
//Posição que se encontra endereço.
//Busca o endereço no buffer
//Verifica se é menor ou maior do que 06.
//Jump se maior ou igual
//Senão, a saída é 04
//Redireciona, buffer entrada PS 04
//Volta para PUT
//Se for 0, já chegou ao destino
//Se for maior, a saída é 05
//Redireciona, buffer entrada PS 05
//Volta para PUT
//Fim do programa
Obs.: P 06 = local, P 04 = PS 04, P 12 = PS 05
Os gráficos das Figuras 29 e 30 ilustram a quantidade de acessos à memória e a
quantidade de instruções de entrada e saída usadas pelo processador proposto e por um
processador conceitual CISC GPP de 8 bits, para execução dos dois algoritmos descritos. Os
valores dos gráficos são referentes a um pacote de apenas 10 bytes. Independentemente do
tamanho do pacote, a simulação ocorreu tendo o endereço de destino na posição 5 do pacote.
60
Figura 29 – Acessos à memória
Figura 30 – Instruções de entrada e saída
Se o pacote fosse de 1500 bytes, os valores do processador proposto, permaneceriam em
9 e 8 para acessos à memória, e 3 e 3 para quantidade de instruções de entrada e saída. Estes
valores são independentes do tamanho do pacote. Para o processador de propósito geral, os
valores subiriam para 1061 e 1060, para acessos à memória, e 511 e 511 para quantidade de
instruções de entrada e saída. Estes valores variam de acordo com o tamanho do pacote.
É importante ressaltar que as instruções de entrada e saída do processador proposto
acessam buffers internos, ao contrário do processador de propósito geral, que acessa buffers
externos. O processador proposto utiliza apenas uma instrução para ler o endereço de destino
do buffer interno, enquanto o GPP precisa ler byte a byte do buffer externo e guardar em
memória, até que a posição do pacote, que guarda o destino, seja lida. Apenas uma instrução é
utilizada para redirecionar todo conteúdo do buffer interno para a saída desejada, enquanto que
o GPP precisa ler byte a byte do buffer externo e escrever byte a byte na saída desejada. O
código gerado para o GPP possui loops com instruções de acesso à memória e de leitura e
61
escrita nas portas de entrada e saída. O processador proposto é mais rápido, lê-se diretamente
da posição desejada do buffer e redireciona todo o conteúdo para a saída sem precisar ler ou
escrever nas portas de entrada e saída e/ou na memória.
No tópico seguinte apresentamos a relação de desempenho entre os processadores RCNP
e R2NP.
5.1.2 – Análise de Desempenho do R2NP em Relação ao RCNP
Apresentamos neste tópico uma análise matemática do ganho obtido através do projeto do
processador de rede (R2NP) usando pipeline no conjunto de instruções. Desta forma, iremos
apresentar os mesmos programas desenvolvidos (apresentados no tópico anterior –
acrescentando o anel unidirecional) para os processadores RCNP e R2NP e quais as métricas e
parâmetros adotados [Patterson 2000] para verificar a relação de desempenho entre as duas
propostas.
Nesta verificação iremos considerar que a chave crossbar não é reconfigurável ou que
todos os bits de reconfiguração estão setados em 01 ou 10, possibilitando apenas que o
processador de gerenciamento faça as conexões desejadas. Sendo assim, estaremos verificando
o funcionamento das instruções dedicadas que fazem acesso às portas de entrada e saída e à
chave crossbar.
Para as métricas estão definidas as seguintes variáveis:
Fc
Freqüência do clock (Hz)1
Tp
Tempo de processador (s)
Ncc
Número de ciclos de clock do programa
Nmci
Número médio de ciclos por instrução
Nip
Número de instruções do programa
Gd
Ganho de desempenho
Então, podemos relacioná-las da seguinte forma:
Nmci = Ncc / Nip
Tp = Nip * Nmci / Fc
Gd = Tp(RCNP) / Tp(R2NP)
1. Os protótipos dos processadores RCNP e R2NP ainda não existem, portanto, será utilizada uma freqüência de 500MHz.
62
É importante ressaltar que o modelo RCNP não utiliza pipeline, suas instruções são
executadas seqüencialmente, uma após o término da outra. Para o modelo R2NP é utilizado o
pipeline e em casos ideais, a diferença entre a execução de uma instrução e a próxima é de
apenas 1 ciclo (pipeline cheio). Esta condição depende do programa ou da carga de trabalho
que está sendo executado, já que instruções condicionais e de salto podem provocar bolhas
(espaços vagos) durante a execução no pipeline.
As figuras 31 (anel unidirecional), 32 (hipercubo) e 33 (árvore balanceada) são as
topologias utilizadas para análise de desempenho dos programas representados nas tabelas 5, 6
e 7.
Anel unidirecional: O objetivo desta topologia é criar uma condição em que cada micro
esteja conectado com sua porta de saída na porta de entrada do micro à esquerda. Esta
topologia foi criada por apenas um processador R2NP. A chave crossbar é responsável por
estabelecer todas as conexões através das instruções do processador. Portanto, na tabela 5 o
programa ilustra a construção da topologia ao longo do tempo.
Figura 31 – Topologia anel unidirecional
Tabela 5 – Assembly anel unidirecional
1
2
3
4
5
6
7
8
9
10
11
12
13
RCNP
LDI A,07
LDI B,01
PUT B
LDI B,08
SEC
FCX
PUT B
DCR B
SEC
FCX
DCR A
JMZ 000009
HLT
Ciclos
5
5
4
5
4
4
4
4*8
4*7
4*7
4*7
5*8
4
R2NP
LDI A,0008
LDI B,0001
LDI C,000A
LDI D,0007
FCX A,B,C
DEC A
LDI B,0006
FCX A,B,C
DEC A
DEC B
JMZ D
HLT
---------------
Ciclos
5
1
1
1
1
1
1
1+1*7
1*7
1*7
2+1*7
1
----------
63
Hipercubo: Nesta topologia, o endereço de cada nó difere de apenas 1 bit para o nó
adjacente. Esta diferença de bit é utilizada no programa de roteamento da tabela 6. Cada nó
desta topologia pode ser considerado com um processador R2NP. Neste caso, o processador P0
possui três entradas e três saídas da chave crossbar sendo usadas. A tabela 6 ilustra o mesmo
programa descrito na tabela 3, porém com a inclusão da versão para o R2NP.
Figura 32 – Topologia hipercubo
Tabela 6 – Assembly hipercubo
RCNP
Ciclos
R2NP
Ciclos
1 LDX F,000006
5
LDI N,0013
5
2 LDI D,03
5
LDI M,0015
1
3 PUT
4
LDI F,0007
1
4 SUI B,00
5
LDI A,0003
1
5 JZ 000000
5
LDI B,0002
1
6 LDI B,00
5
LDI C,0001
1
7 LDI C,05
5
LDI E,0005
1
8 ENT BC
4
ENT G,E,Trab
1
9 XOR D
4
MOV H,Trab
1
10 MOV E,A
4
DEC H
1
11 JZ F
4
JZ I
1
12 ANI A,01
5
XOR J,G,A
1
13 JMZ 000029
5
JZ F
1
14 ANI E,02
5 NE AND L,J,C
1
15 JMZ 000025
5 NE JMZ M
1
16 LDI B,03
5 NE AND L,J,B
1 NE
17 SEC
4 NE JMZ N
1 NE
18 JMP F
4 NE SEC A,Trab
1 NE
19 LDI B,02
5 NE JMP F
1 NE
20 SEC
4 NE SEC B,Trab
1 NE
21 JMP F
4 NE JMP F
1 NE
22 LDI B,01
5
SEC C,Trab
1
23 SEC
4
JMP F
1
24 JMP F
4
---------------------NE: Instrução não executada na simulação (saltos do tipo JMP)
64
Árvore balanceada: Os endereços de cada vértice crescem da esquerda para a direita,
servindo como referência para o programa de roteamento da tabela 7. Parte desta topologia
pode estar presente na chave crossbar, assim como cada nó pode representar um processador
R2NP. O programa da tabela 7 é o mesmo da tabela 4, porém com a inclusão da versão para o
R2NP.
Figura 33 – Topologia árvore balanceada
Tabela 7 – Assembly árvore balanceada
RCNP
Ciclos
R2NP
Ciclos
1 LDI D,06
5
LDI E,000B
5
2 PUT
4
LDI F,0017
1
3 SUI B,00
5
LDI H,0014
1
4 JZ 000025
5
LDI B,0000
1
5 LDI B,00
5
LDI D,0006
1
6 LDI C,05
5
LDI C,0005
1
7 ENT BC
4
MOV G,C
1
8 SUB D
4
ENT A,C,Trab
1
9 JMI 00001A
5
SUB I,Trab,B
1
10 LDI B,04
5
JZ H
1
11 SEC
4
SUB I,A,D
1
12 JMP 000002
5
JMI F
1
13 JZ 000025
5 NE
DEC G
1
14 LDI B,05
5 NE
SEC G,Trab
1
15 SEC
4 NE
JMP E
1
16 JMP 000002
5 NE
JZ H
1 NE
17 HLT
4 NE
SEC G,Trab
1 NE
18 --------------- ---------- JMP E
1 NE
19 --------------- ---------- HLT
1 NE
NE: Instrução não executada na simulação (saltos do tipo JMP)
Para o programa da topologia anel unidirecional, os resultados são os seguintes:
Proposta RCNP
Nip = 45, Ncc = 191, Ncmi = 191 / 45 = 4,244
Tp = 191 / 500 10E6 = 0,382 µs
65
Proposta R2NP
Nip = 39, Ncc = 43, Ncmi = 43 / 39 = 1,102
Tp = 43 / 500 10E6 = 0,086 µs
Gd = 0,382 / 0,086 = 4,44
Podemos concluir que, para o programa da topologia anel unidirecional, o processador
R2NP foi 4,44 vezes mais rápido.
Para o programa da topologia hipercubo, os resultados são os seguintes:
Proposta RCNP
Nip = 16, Ncc = 73, Ncmi = 73 / 16 = 4,562
Tp = 73 / 500 10E6 = 0,146 µs
Proposta R2NP
Nip = 17, Ncc = 21, Ncmi = 21 / 17 = 1,235
Tp = 21 / 500 10E6 = 0,042 µs
Gd = 0,146 / 0,042 = 3,47
Neste caso o ganho de desempenho mostrou que o processador R2NP foi 3,47 vezes mais
rápido.
Para o programa da topologia árvore balanceada, os resultados são os seguintes:
Proposta RCNP
Nip = 12, Ncc = 56, Ncmi = 56 / 12 = 4,666
Tp = 56 / 500 10E6 = 0,112 µs
Proposta R2NP
Nip = 15, Ncc = 19, Ncmi = 19 / 15 = 1,266
Tp = 19 / 500 10E6 = 0,038 µs
Gd = 0,112 / 0,038 = 2,94
Para esta topologia o ganho de desempenho mostrou que o processador R2NP foi 2,94
vezes mais rápido.
A tabela 8 apresenta uma análise comparativa de desempenho.
66
Tabela 8 – Comparativo de desempenho
Anel
Hipercubo
Árvore
No médio de ciclos
RCNP
R2NP
4,244
1,102
4,562
1,235
4,666
1,266
Ganho de desempenho
RCNP (µs) / R2NP (µs)
4,44
3,47
2,94
O ganho de desempenho favorável ao R2NP é resultado de um projeto de processador
baseado em um modelo RISC. Como apenas instruções específicas (load e store) podem fazer
acesso à memória em um processador RISC, um loop com acessos à memória foi facilmente
evitado, o que não ocorreu com o RCNP. A linha 12 da tabela 5 mostra o acesso à memória
feito pela instrução JMZ (8 vezes), que provocou um aumento da relação de desempenho. O
segundo e terceiro programas são executados sem loop e nestes dois casos os ganhos
diminuíram, mas não deixaram de ser relevantes. Apesar do número de instruções entre os
processadores RCNP e R2NP serem muito próximos, a quantidade de ciclos do R2NP
(reduzida pelo pipeline) proporcionou um tempo menor de processamento (Tp) e também um
número médio de ciclos bem próximo a 1. No entanto, estes números podem enganar. Se o
programa da árvore balanceada não estivesse bem projetado e possuísse uma instrução a mais,
executada em 1 ciclo, o número médio de 1,266 ciclos iria cair para 1,250 e o ganho de
desempenho iria baixar de 2,94 para 2,80. Não adianta aproximar o número médio de ciclos
para 1 se a quantidade de ciclos aumentar. Em processadores CISC sem pipeline, como o
RCNP, o número de ciclos em relação ao de instruções aumenta consideravelmente em um
loop, favorecendo o ganho de desempenho para um processador RISC (R2NP).
Neste capítulo não é feita uma análise detalhada de conflitos no pipeline, porém, algumas
considerações podem ser feitas: Os conflitos estruturais são resolvidos através do caminho de
dados, não ocorrendo, portanto, no R2NP. Para o conflito de controle é adotada a técnica de
predição em instruções do tipo jump condicional. A linha 11 da tabela 5 exemplifica o ciclo a
mais referente à bolha. O conflito de dados é resolvido, por exemplo, através de técnicas de
adiantamento de dados, não ocorrendo, portanto, no R2NP.
Com relação aos valores encontrados na tabela 8 podemos concluir que, para o
processador RCNP ser mais rápido, sem alterar o projeto, seria necessário aumentar a
freqüência de clock, o que poderia implicar em problemas externos ao projeto como custo e
temperatura, por exemplo. Os principais fatores de melhoria do projeto R2NP e que
67
favoreceram a relação do ganho de desempenho, são os conceitos RISC baseados no formato
de instrução e no caminho de dados em pipeline.
Apresentamos até o momento um comparativo de desempenho do conjunto de instrução
com base no uso do pipeline. No entanto, é possível verificar o impacto do ponto de vista da
quantidade de instruções que são usadas para acessar a memória e as portas de entrada e saída
(tabela 9), conforme apresentamos no tópico 5.1.1.
Tabela 9 – Quantidade de instruções (sem chave crossbar)
Anel
Hipercubo
Árvore
Memória
RCNP R2NP
11
5
9
7
8
6
Portas de E/S
RCNP
R2NP
18
9
3
2
3
2
Nesta primeira análise iremos destacar o fato de que os bits de reconfiguração
permanecem setados em 01 ou 10 (o processador de gerenciamento é o único que manipula os
nós de conexão). Ou seja, podemos considerar também que a chave crossbar utilizada ainda é
tradicional.
Os valores encontrados nesta tabela refletem diretamente no ganho de desempenho
encontrado na análise do impacto do uso do pipeline. Um número mais alto de acessos à
memória pode prejudicar o desempenho do processador. Este detalhe fica bastante evidenciado
nos resultados da topologia Anel. O dobro de instruções é utilizado, devido principalmente ao
loop. O R2NP utiliza instruções de acesso à memória fora do loop e apesar da diferença da
quantidade instruções diminuir nos outros dois programas, a quantidade de ciclos foi
responsável pela relevância no ganho de desempenho.
Quanto menos acessos às portas de entrada e saída, mais liberdade o processador terá para
executar outras tarefas. A análise do pacote fica mais eficiente e rápida com a utilização de
menos instruções. A diferença é mínima do RCNP para o R2NP, pois o conjunto de instruções
de rede é parecido e possui um bom projeto nos dois modelos.
No entanto, ao comparar os dois processadores com modelos GPPs (General-purpose
processor), como apresentado no WSCAD’01 [Freitas 2001], a diferença aumenta
consideravelmente. O RCNP apresentou um ganho de desempenho que chegou a ser 10 vezes
melhor em instruções de acesso à memória, comparando com um GPP CISC conceitual. Os
processadores GPPs não possuem características dedicadas, que facilitariam e aumentariam o
desempenho em aplicações de rede.
68
É importante ressaltar que os valores usados na análise do RCNP foram obtidos usando o
NPSIM (simulador desenvolvido para testes funcionais). Portanto, os valores analisados
matematicamente para o R2NP foram comparados com resultados de simulação em software
(RCNP / NPSIM).
5.1.3 – Análise de Desempenho usando a Chave Crossbar Reconfigurável
Até o momento estamos analisando aspectos relacionados apenas para chave crossbar
sem implementação dinâmica de topologias. Portanto, podemos agora analisar qual seria o
impacto de uma implementação dinâmica de topologias sobre a chave crossbar reconfigurável
em relação à utilização somente de instruções do processador de rede proposto, conforme
mostrado nos tópicos anteriores.
Primeiramente iremos destacar alguns passos durante o redirecionamento de pacotes de
dados com a chave crossbar reconfigurável:
1. Os bits de reconfiguração setam a chave crossbar e a topologia é criada;
2. Os pacotes de dados redirecionados pelas microengines são enviados para a chave
crossbar;
ou
3. Os pacotes de dados são encaminhados para os buffers reconfiguráveis;
ou
4. Os pacotes de dados são encaminhados para a memória;
5. O processador de gerenciamento lê o cabeçalho do pacote de dados, armazenado
em memória ou buffers, e encaminha para a chave crossbar ou diretamente para
porta de saída.
Ou seja, se não houver conflitos de saída ou a necessidade de criação de uma nova
conexão pelo processador, não haverá utilização de instruções para leitura dos cabeçalhos dos
pacotes de dados. Os pacotes chegarão pelas portas de entrada, haverá uma leitura destes
pacotes pelas microengines e o redirecionamento para as portas de saída através da chave
crossbar reconfigurável. Somente no momento em que este pacote é guardado em buffers ou
memória ou da necessidade de uma nova conexão (não implementada pelos bits de
reconfiguração), é que se fará uso das instruções do processador de gerenciamento para leitura
dos cabeçalhos dos pacotes e acesso à memória.
Desta forma, poderíamos ter para a topologia em árvore (figura 34), implementada por
bits de reconfiguração, nenhum acesso às portas de entrada, saída ou memória pelas instruções
69
do processador de gerenciamento. Nesta topologia, todas as entradas e saídas estão
representadas através das conexões em cada nó. Ou seja, todos os supostos computadores desta
topologia estão conectados através da mesma chave crossbar.
Nas figuras 28 e 33 a situação é diferente, a topologia ilustra uma rede que não
necessariamente está toda conectada em um mesmo processador de rede e por conseqüência em
sua chave crossbar. Portanto, haveria uma tabela de roteamento onde o suposto computador P
06 teria que ler para que soubesse qual rota seguir para atingir, por exemplo, o computador P
11. Na chave crossbar do processador P 06 haveria os processadores P 04 e P 12 conectados
nas portas de entrada e saída.
Figura 34 – Topologia árvore balanceada por bits de reconfiguração
Independentemente de toda a rede estar representada ou não através da topologia
implementada pela mesma chave crossbar, o fato é que existe uma diminuição na utilização de
instruções para acessos às portas de entrada e saída e memória, fazendo com que o processador
de gerenciamento execute tarefas mais “nobres”, tais como:
•
Construção e manutenção de tabelas de roteamento;
•
Gerenciamento da rede e questões relativas à qualidade de serviço (QoS);
•
Gerenciamento de memória.
Como as microengines só existem na arquitetura do R2NP, ao usarmos os bits de
reconfiguração, a tabela 9 ficaria com os seguintes resultados (tabela 10):
70
Tabela 10 – Quantidade de instruções (com chave crossbar)
Anel
Hipercubo
Árvore
Memória
RCNP R2NP
11
0
9
0
8
0
Portas de E/S
RCNP
R2NP
18
0
3
0
3
0
Desta forma, estaríamos aproveitando a topologia implementada, através dos bits de
reconfiguração, para aumentar a flexibilidade, a vazão de dados e o desempenho de operação
do processador. Portanto, não haveria necessidade da execução de instruções pelo processador
de gerenciamento para que houvesse comutação dos nós da chave crossbar e conseqüente
roteamento dos pacotes de dados. Este roteamento iria acontecer sem o atraso de
processamento de instruções uma vez que a topologia já estaria implementada e o roteamento
acontecendo através da combinação microengines e chave crossbar reconfigurável, liberando o
processador de gerenciamento para execução de outras atividades.
É importante ressaltar que, apesar dos resultados garantirem uma eficiência do conjunto
de instruções, uma alteração na arquitetura do R2NP ou na chave crossbar, pode provocar uma
melhoria de desempenho e uma necessidade de modificação do conjunto de instruções,
alterando, acrescentando ou removendo uma instrução, como aconteceu durante o
desenvolvimento do modelo CISC para o RISC.
5.2 – ANÁLISE DA IMPLEMENTAÇÃO DINÂMICA DE TOPOLOGIAS USANDO
TEORIA DE GRAFOS
De acordo com os resultados do tópico 5.1.3, verificamos que a utilização da chave
crossbar reconfigurável pode reduzir a zero, o número de instruções de acesso à memória ou
portas de entrada e saída. É importante ressaltar que isto ocorre em casos específicos (conforme
algoritmos e topologias propostas). No entanto, a tendência é que a reconfiguração e
implementação dinâmica de topologias possibilitem o uso mínimo de instruções para
roteamento. Sendo assim, neste tópico apresentamos algumas métricas e parâmetros para
verificar a flexibilidade e o aumento de desempenho usando teoria de grafos.
Como visto no tópico 2.1.3, existem algumas métricas [Netto 2001] [Calvert 1997, 1992]
adotadas para a modelagem de grafos aplicada às redes de comunicação de dados. Iremos
adotar duas para analisar o impacto da utilização da chave crossbar reconfigurável como
unidade de chaveamento de pacotes e implementação dinâmica de topologias em uma rede de
interconexão de dados. São elas:
71
•
Grau médio do grafo;
Podemos considerar como grau médio de um grafo, o quanto os vértices estão
conectados entre si através das arestas, proporcionando uma maior
possibilidade de caminhos alternativos.
Grau médio (GM) = 2*QtdAresta (A) / QtdVértice (V)
•
Diâmetro do grafo e menor distância entre vértices.
Podemos considerar como diâmetro de um grafo, o maior caminho
(quantidade de saltos) entre quaisquer dois vértices do grafo. Desta forma,
podemos dizer que, quanto menor o diâmetro também menor será o caminho
entre dois vértices. Neste caso, não levando em consideração os possíveis e
diferentes pesos nas arestas. Podemos considerar, portanto, que o menor
diâmetro é o menor caminho entre dois vértices.
Com base nestas duas métricas procuramos apresentar como a flexibilidade da
implementação dinâmica de topologias pode ajudar no desempenho de processamento de
dados.
A figura 35 apresenta três topologias que poderiam ser implementadas na chave crossbar
reconfigurável (em tempo de execução) de acordo com a necessidade de processamento de
pacotes.
Figura 35 – Topologias dinâmicas
Para modelarmos as topologias de comunicação de dados em grafos adotamos que os nós
das redes são os vértices e as linhas de comunicação são as arestas.
Em uma situação hipotética, o seguinte problema poderia ser apresentado: uma topologia
anel é implementada na chave crossbar reconfigurável através dos bits de reconfiguração.
72
Porém, constatou-se um crescente número de envio de pacotes do nó 1 para os demais nós da
topologia, tal como um broadcast. Neste caso, se apenas o nó 1 estabelecesse comunicação
com os demais, a melhor topologia seria estrela. Contudo, as demais comunicações
permanecem e por este motivo devem ser mantidas na implementação da nova topologia.
Como a chave crossbar é reconfigurável, as conexões diretas que faltavam foram
implementadas dinamicamente. Desta foram, diminui-se o número de saltos para a
comunicação e conseqüentemente aumenta o desempenho e a vazão de dados do nó 1 para os
demais nós.
Para a topologia apresentada no início (anel) e para a topologia final (anel/estrela), os
seguintes resultados com base nas duas métricas de modelagem em grafos são:
Topologia Anel (8 Vértices e 8 Arestas):
•
Grau médio do grafo: GM = 2*8/8 = 2
•
Menor Diâmetro do vértice 1 ao 5: MD = 4
Topologia Anel/Estrela (8 Vértices e 13 Arestas):
•
Grau médio do grafo: GM = 2*13/8 = 3,25 = 3
•
Menor Diâmetro do vértice 1 ao 5: MD = 1
Portanto, as métricas baseadas em modelos de grafos mostraram o quanto é importante
uma topologia específica ou dedicada à aplicação. Há um aumento da capacidade de
estabelecer a comunicação (grau médio do grafo) com os demais vértices e por este motivo, há
uma diminuição no tempo de resposta de comunicação (menor diâmetro – caminho entre
vértices) e por conseqüência um melhor desempenho de processamento de pacotes, já que
instruções desnecessárias não serão utilizadas.
É importante ressaltar que, o cálculo do diâmetro com base apenas no número de saltos
pode não ser satisfatório, uma vez que as arestas podem ter pesos diferentes (linhas de
comunicação com custos – tráfegos – ou latências diferentes). Porém, em casos onde estes
pesos são iguais em todas as arestas, esta análise é suficiente para o cálculo de menor caminho.
No nosso caso, todas as arestas possuem o mesmo peso, já que cada aresta representa uma
conexão realizada pela chave crossbar (entre entradas e saídas). Desta forma, o resultado do
cálculo de menor diâmetro reflete a realidade da chave crossbar reconfigurável proposta.
No entanto, podemos considerar que o processador de rede (R2NP) conhece a influência
do tráfego, latência e tempo de transmissão [Menascé 2003] para que a mensagem enviada para
uma saída chegue ao seu destino, em algum outro ponto da rede. Ou seja, todas as saídas da
73
chave crossbar levam a outras redes ou outros destinos, coincidentes ou não. Sendo assim,
vamos considerar que somente a latência influencia no cálculo de menor caminho e que toda a
influência externa está modelada no grafo da figura 36, onde cada nó representa um
processador R2NP e não mais a chave crossbar. Porém, para o processador R2NP-1 (nó 1) a
sua chave crossbar possui sete entradas e sete saídas conectadas aos demais nós ou
processadores R2NPs da rede e os demais possuem 2 ou 3 entradas e saídas conectadas aos
demais. Como o algoritmo que será apresentado a seguir trata de roteamento, definimos que
cada processador R2NP está presente em um roteador e, portanto, cada nó poderá ser chamado
também de roteador.
Figura 36 – Arestas do grafo com peso (latência em ms)
Neste grafo as latências entre os nós são dadas em milisegundos (ms). Usaremos o
algoritmo conhecido como roteamento com vetor de distância [Tanenbaum 2003] para
definição da melhor rota para envio dos pacotes de dados.
Neste algoritmo, cada roteador (presente em cada nó da topologia) mantém uma tabela
(tabela de roteamento resultante – figura 37) que fornece a menor distância entre a origem e
cada destino da rede. Estas tabelas são atualizadas pelos roteadores vizinhos (ou nós
adjacentes) informando a distância entre estes roteadores vizinhos e cada outro roteador da
rede. Desta forma, com as informações enviadas pelos vizinhos é construída uma nova tabela
com a menor distância resultante para se chegar a qualquer nó da rede, usando como primeiro
passo o roteador vizinho que oferecer o menor caminho.
A figura 37 ilustra as duas tabelas (enviada pelos vizinhos e resultante de distância) com
um exemplo evidenciado: Se for necessário enviar um pacote do nó 5 para o nó 3, qual seria o
melhor caminho?
Se as novas conexões entre o nó 1 e todos os outros nós da rede não fossem realizadas, a
resposta seria do nó 5 para o 4 finalizando nó 3, com uma latência total de 10ms. Porém com as
74
novas conexões, verificamos que existem 3 caminhos para se chegar ao destino, possuímos
uma maior opção de roteamento. Como em uma rede de computadores, o vetor de distância
enviado por um nó adjacente pode não estar atualizado, faremos a seguinte consideração para
mostrar a importância de mais de uma opção de roteamento: o nó adjacente 6 não recebeu a
informação de que para chegar até o nó 3, passando pelo nó 1 e 2, gasta-se apenas 6 ms. Esta
informação deve ser enviada pelo nó adjacente 1 ao 6, porém o nó 6 enviou o vetor de distância
ao nó 5 contento sua última informação de melhor caminho para chegar ao nó 3 gastando 7 ms.
Esta informação também foi obtida através do nó 1, porém em um momento em que a melhor
opção não usava o nó 2 como caminho, mas o link direto ao nó 3, conforme figura 36.
Portanto, de acordo com as informações enviadas pelos nós adjacentes (figura 37) a
melhor opção de roteamento seria através do nó 1 com latência total de 7ms. Ou seja, o pacote
de dados chegaria 3ms mais cedo ao seu destino se comparado à topologia anterior (anel) onde
haveria apenas dois caminhos alternativos (pelo nó 4 ou pelo nó 6).
Figura 37 – Tabelas de roteamento para o nó 5
Neste tópico mostramos a influência e o impacto da implementação dinâmica de
topologias para definição de rotas. É importante ressaltar que, usando somente a chave
crossbar reconfigurável é possível definir o melhor caminho, basta seguir a topologia onde
todos os pesos das arestas são iguais. Ou se necessário, consultando tabelas de roteamento,
gerenciadas pelo processador de gerenciamento, que irá definir qual o melhor caminho a ser
adotado, com base em influências externas. Contudo, independente da influência externa, o
aumento do grau médio e a diminuição do diâmetro entre dois nós (parâmetros alterados pela
reconfigurabilidade da chave crossbar), foram responsáveis diretos pelos números obtidos na
75
tabela de roteamento resultante ilustrada na figura 37. Outras análises usando algoritmos
diferentes podem ser obtidas nas referências [Tanenbaum 2003] e [Netto 2001].
5.3 – VERIFICAÇÃO COMPORTAMENTAL DA CROSSBAR RECONFIGURÁVEL
O objetivo deste tópico é apresentar as simulações realizadas para verificação de
flexibilidade e desempenho da chave crossbar reconfigurável. A linguagem VHDL (VHSIC
Hardware Description Language) foi escolhida para ser usada no projeto, simulação e síntese
da chave crossbar proposta, devido a sua facilidade de descrição de circuitos lógicos e
portabilidade de desenvolvimento. Foram escolhidos como ambientes de projeto e simulação os
softwares ISE WebPack e ModelSim da Xilinx.
São apresentadas três simulações, referentes às arquiteturas de chave crossbar tradicional,
e reconfiguráveis de 1 e 2 bits. Não foi nossa intenção simular o projeto da chave crossbar
reconfigurável com todas as suas entradas e saídas de dados ou seus barramentos de controle. O
objetivo é simular o funcionamento comportamental da chave crossbar apenas para apresentar
a característica principal que é a flexibilidade de operação ou implementação dinâmica de
topologias. Portanto, não estão sendo consideradas nesta simulação todas as entradas, saídas e
barramentos, que são partes integrantes da arquitetura do R2NP e da própria chave crossbar
reconfigurável.
Para facilitar a captura das telas de simulação, decidimos simular uma chave crossbar
4x4, onde iremos implementar dinamicamente as seguintes topologias: anel, árvore, estrela e
pirâmide (esta última apenas para crossbar reconfigurável de 2 bits).
Nos três tópicos a seguir apresentamos os resultados das simulações.
5.3.1 – Simulação em VHDL da Chave Crossbar Tradicional
Nesta simulação procuramos verificar os resultados de chaveamento de uma chave
crossbar tradicional, conforme descrito no tópico 2.1. Neste caso, somente há fechamento de
conexão entre entrada e saída no intervalo de tempo. Não podemos, portanto, ter uma mesma
entrada conectada a várias saídas ao mesmo tempo (simultaneamente).
A figura 38 ilustra o ambiente de projeto e por conseqüência a Entity da chave crossbar
tradicional. Como as conexões (ou topologias) não estão implementadas na chave crossbar, é
necessário indicar qual entrada e qual saída deverão efetuar a comunicação. Para isto, usamos
dois registradores:
76
•
Regin: registrador que indica qual a entrada.
•
Regout: registrador que indica qual a saída.
Estes registradores definem qual entrada e saída irão se comunicar, e, portanto, qual nó da
chave crossbar irá fechar. Exemplo:
•
Regin = 0001 (entrada 0)
•
Regout = 0010 (saída 1)
•
Nó fechado = 01 (A01 de uma matriz – figura 39)
Em implementações mais complexas alguma alternativa de controle poderia ser feita para
que entradas e saídas diferentes pudessem se comunicar ao mesmo tempo (mantendo as
restrições de fechamento de coluna), porém no nosso caso usaremos apenas estes dois
registradores.
Figura 38 – Ambiente de projeto para chave crossbar tradicional - ISE WebPack
A figura 39 ilustra as conexões fechadas na simulação e qual topologia poderia ser
implementada no tempo.
77
Figura 39 – Conexões simuladas em VHDL (chave crossbar tradicional)
De acordo com o resultado de simulação apresentado na figura 40, o comportamento
verificado em tempo de simulação (intervalos definidos pelo programador) foi o seguinte:
•
De 0 a 100ns:
É fechada a conexão entre a entrada 0 e a saída 1. Como havia sinal de entrada
com nível lógico alto na entrada 0, a saída 1 recebeu o bit 1.
•
De 100ns a 200ns:
É fechada a conexão entre a entrada 0 e a saída 2. Como havia sinal de entrada
com nível lógico alto na entrada 0, a saída 2 recebeu o bit 1.
•
De 200ns a 300ns:
É fechada a conexão entre a entrada 0 e a saída 3. Como havia sinal de entrada
com nível lógico baixo na entrada 0, a saída 3 recebeu o bit 0.
Podemos verificar que a entrada 0 envia dados para as demais saídas da chave crossbar
(1,2 e 3). Sendo assim, a topologia estrela foi implementada no tempo (usando técnicas de
multiplexação) e não no espaço.
•
De 300ns a 400 ns:
É fechada a conexão entre a entrada 1 e a saída 2. Como havia sinal de entrada
com nível lógico alto na entrada 1, a saída 2 recebeu o bit 1.
•
De 400ns a 500ns:
É fechada a conexão entre a entrada 2 e a saída 3. Como havia sinal de entrada
com nível lógico baixo na entrada 2, a saída 3 recebeu o bit 0.
•
Após 500ns:
É fechada a conexão entre a entrada 3 e a saída 1. Como havia sinal de entrada
com nível lógico alto na entrada 3, a saída 1 recebeu o bit 1.
Ao fim dos 600ns verificamos que os nós que enviam dados para o nó central (nó 0)
também começaram a se conectar, formando juntamente com as conexões realizadas de 0 a
300ns uma topologia temporal chamada pirâmide.
78
Figura 40 – Resultado de simulação da chave crossbar tradicional
Portanto, a chave crossbar tradicional é capaz de realizar conexões espaciais, mas realiza
a implementação de topologias de forma temporal. Nos dois tópicos a seguir estaremos
apresentando os resultados de simulação do comportamento das duas propostas de arquitetura
de chave crossbar reconfigurável e como podemos verificar a implementação de topologias no
espaço.
5.3.2 – Simulação em VHDL da Chave Crossbar Reconfigurável de 1 bit
A figura 41 apresenta o ambiente de simulação em VHDL da chave crossbar
reconfigurável de 1 bit. A Entity que descreve a arquitetura da crossbar está representada nesta
figura e possui as seguintes portas definidas, que caracterizam a arquitetura da chave crossbar
para simulação da flexibilidade de reconfiguração:
•
Entrada0, Entrada1, Entrada2, Entrada3:
Representam as quatro entradas de dados da chave crossbar por onde chegam
os pacotes de dados redirecionados pelas microengines, ou pelo processador
de gerenciamento. No teste de simulação estas entradas foram agrupadas em
um vetor de 4 bits.
•
Nó_00 até Nó_33:
Representam os dezesseis bits responsáveis pela reconfiguração da chave
crossbar. As numerações que seguem as palavras “Nó” são referentes aos
índices de uma matriz 4x4.
•
RegHabilitaEntrada:
79
Na nossa proposta de chave crossbar reconfigurável é possível fechar uma
conexão entre uma entrada e várias saídas, ou vice-e-versa. Por este motivo é
necessário que se tenha um controle contra conflitos. Optamos por acrescentar
um registrador (“RegHabilitaEntrada”) que habilita o envio de dados para
simplificar a arquitetura simulada.
•
Saída0, Saída1, Saída2, Saída3:
Representam as quatro saídas de dados da chave crossbar. No teste de
simulação estas entradas foram agrupadas em um vetor de 4 bits.
Figura 41 – Ambiente de projeto da chave crossbar de 1 bit - ISE WebPack
A figura 43 mostra os resultados de simulação e verificação do funcionamento da chave
crossbar. Nesta simulação podemos observar três diferentes topologias implementadas ao
longo do tempo, conforme ilustrado pela figura 42. A seguir será descrito o funcionamento da
reconfiguração nos seus intervalos de tempo correspondentes.
Nos primeiros 400ns a topologia anel bidirecional foi implementada. Neste intervalo de
tempo, nós podemos observar que o registrador “RegHabilitaEntrada” habilita a entrada 0.
80
Sendo assim, as saídas 1 e 3 que foram conectadas à entrada 0 através dos pontos de conexão
Nó_01 e Nó_03, de acordo com a topologia implementada, recebem os sinais da entrada 0
durante os 400ns.
No intervalo de 400ns a 800ns a topologia foi reconfigurada para árvore bidirecional.
Neste instante o registrador “RegHabilitaEntrada” habilita a entrada 2, mas não há nenhum
dado a ser enviado. Por este, motivo nos primeiros 100ns as portas de saídas não receberam
nenhum sinal. Após os 500ns as entradas 0 e 2 enviam sinal para a chave crossbar, porém o
registrador está habilitando apenas a entrada 2, e por conseqüência a saída 0 é a única a receber
o sinal vindo desta entrada 2.
Nos últimos 200ns foi implementado, através dos bits de reconfiguração, a topologia
estrela bidirecional. Nos primeiros 100ns nenhuma entrada da crossbar foi habilitada. Após
estes 100ns, o registrador “RegHabilitaEntrada” habilita a entrada 3 para enviar dados. De
acordo com a topologia estrela, a entrada três está conectada através do Nó_30 à saída 0, por
este motivo somente esta saída irá receber o sinal enviando pela entrada 3.
Figura 42 – Topologias simuladas em VHDL (chave crossbar de 1 bit)
81
Figura 43 – Resultados da simulação da chave crossbar de 1 bit
Através dos resultados obtidos nesta simulação, observamos que o funcionamento da
chave crossbar corresponde à proposta apresentada de flexibilidade. Ou seja, ao longo do
tempo e durante o período de trabalho da chave, é possível alterar ou reconfigurar a topologia
implementada, para uma aplicação específica em tempo de execução.
5.3.3 – Simulação em VHDL da Chave Crossbar Reconfigurável de 2 bits
Para esta simulação modificamos a arquitetura da chave crossbar reconfigurável para 2
bits de reconfiguração. Por este motivo, a Entity foi alterada conforme ilustrado na figura 44.
As entradas de reconfiguração foram definidas como um vetor lógico de duas posições e foi
acrescentado um registrador de 5 bits para representar a intervenção do processador de
gerenciamento. As demais entradas e saídas permaneceram iguais.
82
Figura 44 – Ambiente de projeto da chave crossbar de 2 bits - ISE WebPack
Os bits do registrador do processador de gerenciamento significam o seguinte:
•
Quinto bit (mais significativo da esquerda para direita): este bit indica se vai abrir
(0) ou fechar (1) uma conexão.
•
Os quatro bits restantes: indicam qual nó da chave crossbar reconfigurável será
aberto ou fechado, conforme tabela 11:
Tabela 11 – Bits dos nós da chave crossbar de 2 bits
Nós
00
01
02
03
10
11
12
13
Bits
0000
0001
0010
0011
0100
0101
0110
0111
Nós
20
21
22
23
30
31
32
33
Bits
1000
1001
1010
1011
1100
1101
1110
1111
83
Foram
simuladas
as
mesmas
topologias,
porém,
através
do
regproc
(RegistradorProcessador – registrador que recebe dados do processador de gerenciamento), a
topologia estrela foi alterada para topologia pirâmide, conforme ilustrado na figura 45. As setas
que aparecem em cada topologia desta figura indicam qual o sentido de comunicação
habilitado durante a simulação.
Figura 45 – Topologias simuladas em VHDL (chave crossbar de 2 bits)
A figura 46 ilustra os resultados de simulação que podem ser descritos da seguinte forma:
•
De 0 a 100ns:
Topologia Anel. Entrada 0 habilitada enviando sinal para as saídas 1 e 3,
conforme vetor de saída (1010). O registrador regproc tenta fechar (10010) a
conexão 02, mas o bit de reconfiguração deste nó setado para 00 não permite.
•
De 100ns a 200ns:
Topologia Árvore. Entrada 2 habilitada enviando sinal para saída 0, conforme
vetor de saída (0001). O registrador regproc tenta fechar (11011) a conexão
23, mas o bit de reconfiguração deste nó setado para 00 não permite.
•
De 200ns a 300ns:
Topologia Estrela. Entrada 3 habilitada enviando sinal para saída 0, conforme
vetor de saída (0001). O registrador regproc tenta fechar (10110) a conexão
12, mas o bit de reconfiguração deste nó setado para 00 não permite.
•
Após 300ns:
A topologia pirâmide começa a ser implementada através do Processador de
Gerenciamento, aproveitando a reconfiguração implementada para topologia
estrela. De 300ns a 800ns somente a entrada 3 estará habilitada a enviar sinal
para suas saídas conectadas. De 300ns a 500ns as conexões 12 e 21 são
fechadas através do regproc (10110 e 11001), porém somente a saída 0 recebe
o sinal, conforme o vetor de saída (0001), já que as conexões realizadas pelo
84
processador não são referentes à entrada 3 (única habilitada). No intervalo de
500ns a 600ns a conexão 13 (10111) é fechada (sentido 1 para 3), mas como
somente a entrada 3 está habilitada, o vetor de saída continua sendo 0001. No
intervalo de 600ns a 800ns as conexões 31 (11101) e 23 (11011) são fechadas
e a entrada 3 passa a enviar sinal para as saídas 0 e 1 (vetor de saída = 0011),
já que o sentido 2 para 3 não está habilitado. A partir de 800ns as saídas 0, 1 e
2 passam a receber sinais da entrada 3, já que a conexão 32 (11110) é fechada.
Neste instante o vetor de saída passa para 0111.
Figura 46 – Resultados de simulação da chave crossbar de 2 bits
É importante frisar que, o pacote só é enviado para as saídas com conexão fechada, caso
todas as saídas sejam consideradas destino (esta afirmação vale para os dois tipos de arquitetura
da chave crossbar). Por exemplo, no caso da pirâmide o sinal é enviado da entrada 3 para as
saídas 0, 1 e 2. Se apenas a saída 2 fosse o destino, as outras duas saídas não receberiam o
pacote de dados. Entretanto, este controle não foi implementado para nenhuma das duas
simulações da chave crossbar, preocupamos apenas com a simulação de flexibilidade e
implementação dinâmica de topologias através da reconfiguração que ocorre em tempo de
execução.
A grande diferença entre as duas chaves crossbar reconfiguráveis está na interferência do
processador de gerenciamento na construção dinâmica de topologias. Existe uma maior
flexibilidade de trabalho com alternativas de soluções para respostas de roteamento, construção
de sub-redes e segurança de comunicação.
85
Podemos concluir que os resultados de simulação verificam o funcionamento e o
desempenho das duas chaves crossbar reconfiguráveis, especificadas durante o projeto e
apresentação da proposta (capítulo 4), ressaltando o fato de que ambas as propostas apresentam
o conceito de uma unidade chaveamento espacial e de implementação de topologias espaciais,
ao contrário de uma chave crossbar tradicional, que é capaz de chavear espacialmente, mas
apenas “implementa” topologias temporais.
86
6 – CONCLUSÕES
No projeto do R2NP os principais blocos construtivos da arquitetura de referência foram
utilizados na tentativa de obter um modelo o mais próximo das características típicas de um
processador de rede. Por isto, optamos pelo projeto de um processador que pudesse conter
múltiplas unidades de processamento (processador de gerenciamento e microengines),
hardwares dedicados ou ASICs (chave crossbar e memória) e unidades com reconfiguração
dinâmica (chave crossbar e buffers reconfiguráveis).
De acordo com os resultados obtidos, foi possível constatar que o modelo de arquitetura e
de conjunto de instruções do processador de rede evoluiu consideravelmente do modelo CISC
para o RISC, principalmente com relação ao desempenho obtido pela inserção do pipeline na
arquitetura RISC, que fez com que obtivéssemos uma relação de ganho de aproximadamente 4
vezes em alguns casos. Podemos considerar também, que a redução de instruções que acessam
a memória, produziu uma melhora considerável no impacto de desempenho de acesso aos
dados inclusive quando existem loops no programa utilizado. O conjunto de instruções
dedicado para operações de rede se mostrou eficaz, uma vez que atingiu o objetivo de leitura de
dados de entrada, e redirecionamento para a saída. É importante ressaltar, que estas instruções
foram criadas como forma de se ter uma liberdade maior de manipulação dos dados. Mesmo a
chave crossbar reconfigurável sendo capaz de implementar uma topologia, estas instruções
também são capazes de estabelecer conexões (usando a chave crossbar) entre entradas e saídas
conforme os programas simulados demonstraram. No anexo estão presentes informações
referentes ao simulador NPSIM (Network Processor Simulator) usado para simular e verificar
o funcionamento da arquitetura e do conjunto de instruções do modelo CISC, onde os
programas mostrados no capítulo de resultados foram simulados.
Aplicando os parâmetros para modelagem de grafos, diâmetro e o grau médio, foi
possível verificar a principal característica da chave crossbar reconfigurável, que é o aumento
de flexibilidade para o chaveamento de pacotes de dados e a implementação dinâmica de
topologias. Estas duas características representam uma maior vazão de dados e uma maior
possibilidade de caminhos alternativos, já que aumenta a quantidade de arestas ou links
presentes. Isto ficou evidenciado quando usamos o algoritmo de vetor de distância para
verificar a escolha da melhor rota com base em influências das latências dos meios externos.
Os resultados de simulação em VHDL verificam o comportamento da chave crossbar
reconfigurável. Nestas simulações foi possível constatar que a implementação dinâmica de
topologias facilita a comunicação entre os diversos pontos conectados na crossbar e possibilita
87
a utilização de uma topologia mais específica ou dedicada de acordo com as necessidades de
cada aplicação (interconexão ou comunicação). As chaves crossbar de 1 bit e de 2 bits se
mostraram eficientes e foi possível verificar a possibilidade de intervenção do processador de
gerenciamento, através de suas instruções, para aumentar a principal característica das duas
chaves crossbar que é a flexibilidade. Em relação à chave crossbar tradicional, verificamos
situações onde foi necessário fechar 3 conexões (uma após a outra) ao longo do tempo. Nas
chaves crossbar reconfiguráveis, com a topologia implementada, estas 3 conexões já estão
fechadas e, portanto, ao contrário de 3 unidades de tempo para enviar um pacote para 3
destinos diferentes, gastaríamos apenas 1 unidade de tempo. Ou seja, um ganho de 3 vezes em
relação a chave crossbar tradicional.
Uma chave crossbar tradicional é uma unidade de chaveamento espacial. Ou seja,
conforme a figura 4 e simulação apresentada na figura 36, ela não realiza a comunicação entre
dois pontos de forma temporal utilizando técnicas de multiplexação. No entanto, quando uma
determinada coluna da chave já está conectada, nenhum outro ponto desta coluna poderá ser
fechado. Podemos considerar então que cada topologia ocorre no tempo e, portanto, uma
comunicação pode ter que esperar que um outro chaveamento tenha que ser desfeito se a
mesma coluna tiver que ser usada. Concluímos então, que uma chave crossbar tradicional é
uma unidade de chaveamento espacial e de topologias temporais.
As chaves crossbar reconfiguráveis propostas são unidades de chaveamento espacial e de
topologias espaciais. O motivo pelo qual classificamos assim, se deve ao fato de existir a
implementação dinâmica de topologias na chave crossbar reconfigurável. Estas topologias são
representações de interconexões espaciais ou de chaveamentos espaciais, não é necessário
esperar um encerramento de conexão ou um fechamento de conexão para que o chaveamento
seja realizado, pois ele já está pronto. Esta conclusão pode ser ilustrada pelas figuras 24, 26 e
34 onde as topologias são espaciais e as colunas ou linhas possuem mais de uma conexão.
O principal desafio é encontrar o ponto ótimo de desempenho para os processadores de
rede. Qual técnica utilizar e quanto ótimo é o modelo ISA (Instruction Set Architecture) e a
arquitetura do processador. Sabemos que GPPs são mais flexíveis, os ASIPs são menos
flexíveis, porque são dedicados e os ASICs são muito velozes, porém pouco flexíveis.
Acreditamos que a inserção de dispositivos (ex. chave crossbar) dentro da pastilha do
processador (SoC) é interessante e pode aumentar o desempenho de processamento. Os
projetos que utilizam as várias técnicas possíveis, provavelmente irão se aproximar do melhor
ganho de desempenho.
88
De acordo com os problemas apresentados na introdução podemos concluir que:
1. Uma arquitetura RISC com estrutura em pipeline usando conceitos System-onChip (através de blocos ASICs) permitiria o aumento de desempenho do
processador de rede;
2. Conjunto de instruções RISC composto de instruções de propósito geral e outras
instruções dedicadas para redes seria o mais adequado;
3. A melhor opção de switching fabric para a nossa proposta é a chave crossbar.
Escolha baseada em sua estrutura em formato de uma matriz de chaveamento.
Chave crossbar interna a arquitetura do processador de rede;
4. Utilizar uma estrutura de chave crossbar reconfigurável para implementação
dinâmica de topologias, proporcionando broadcast, multicast e topologias
dedicadas para padrões de comunicação melhorando a flexibilidade e a vazão de
dados;
5. As topologias podem ser implementadas programando os nós de conexão da
chave crossbar para fechar ou abrir uma comunicação entre as entradas e saídas;
6. A computação reconfigurável é a técnica adotada para aumentar a flexibilidade e
o desempenho de alguns blocos da UCDR do processador de rede. Em específico,
tratamos da chave crossbar, que é programada através de bits de reconfiguração
para implementação de novas topologias ao longo do tempo. As topologias
configuradas são conseqüências dos bits de reconfiguração que podem controlar
(fechar ou abrir) os nós da chave crossbar.
Atualmente existe uma grande exigência por desempenho nas redes de comunicação de
dados. O estudo dos diversos equipamentos e as funções, que cada um desempenha,
influenciou no projeto e desenvolvimento de processadores dedicados, que pudessem suprir as
necessidades de desempenho e qualidade. Desta forma surgiu o processador de rede, que em
sua concepção inicial, veio contribuir com o aumento de velocidade e de qualidade de serviço
nos sistemas de comunicação de dados.
Foi possível constatar, através de toda a bibliografia consultada que, os processadores de
rede são objetos de estudos recentes nas empresas e universidades. Os grupos estão se
formando, e a partir do ano de 2000 começaram a aparecer os principais artigos. No Brasil,
além do nosso grupo, está se formando outro grupo de pesquisa na Fundação de Ensino
Eurípides Soares da Rocha em Marília SP, sob coordenação e orientação do professor Dr.
Edward Ordonez. Foram consultados os anais e proceedings do WSCAD e SBAC dos últimos
89
anos e também o banco de dados do sistema Lattes do CNPq e verificamos que além dos dois
grupos não existem outros que façam pesquisas na área. É por esta razão que acreditamos nos
resultados de divulgação da nossa pesquisa como forma de incentivar outros grupos a se
formarem e contribuírem com resultados para esta nova área do conhecimento.
Nossa pesquisa possui uma história que começa na iniciação científica durante a
graduação. Estamos gerando conhecimento sobre processadores de rede e é nossa intenção,
aprofundar nos detalhes técnicos e manter em atividade um grupo de pesquisa que possa ser
referência no estudo e desenvolvimento de processadores de rede e dispositivos relacionados,
tal como as unidades de chaveamento (switching fabrics).
As principais contribuições alcançadas e apresentadas nesta dissertação estão listadas
abaixo:
Arquiteturas de processadores de rede CISC e RISC;
Arquiteturas de chaves crossbar reconfiguráveis para implementação dinâmica de
topologias e chaveamento de pacotes de dados;
Resultados matemáticos de análise de desempenho, modelagem usando grafos e
simulações por VHDL;
Produção científica abordando resultados de pesquisa desta nova área do
conhecimento;
Minicurso sobre processadores de rede ministrado na Escola Regional de
Informática RJ/ES em 2003 e no Workshop em Sistemas Computacionais de Alto
Desempenho também em 2003.
Portanto, os principais objetivos e metas se refletiram em contribuições, que são
conseqüências das idéias e dos resultados obtidos no estudo e desenvolvimento de uma
proposta de processador de rede para aumento de flexibilidade e de desempenho de
processamento e chaveamento de pacotes de dados em uma rede de comunicação.
Acreditamos que uma outra contribuição importante seja o incentivo para o surgimento
de novas pesquisas e produções científicas em uma área recente e pouco explorada
academicamente, uma vez que os resultados de projeto de arquiteturas de processadores de rede
têm se limitado às pesquisas industriais.
Conforme descrevemos no capítulo de materiais e métodos, existem etapas futuras para
conclusão da pesquisa. Desta forma, descrevemos a seguir os principais trabalhos futuros:
1. Simulação funcional por software do modelo RISC;
2. Desenvolvimento de um compilador para processador modelo RISC;
3. Análise de métricas e avaliação de resultados de desempenho;
90
4. Projeto e simulação do código em VHDL de toda a UCDR em etapas separadas
tal como foi feito para a chave crossbar;
5. Análise de métricas de desempenho para a UCDR;
6. Prototipação também em etapas separadas da UCDR utilizando FPGAs;
7. Simulação e prototipação da arquitetura do processador RISC em VHDL e
FPGAs;
8. Testes em uma rede de comunicação de dados real (poderá ser realizado para
alguns blocos funcionais em separado).
9. Agregar e projetar novamente a arquitetura R2NP usando conceitos NoC
(Network-on-Chip)
10. Refazer etapas 7 e 8 para o novo modelo R2NP/NoC.
A UCDR é um dos objetos principais de estudo do R2NP. Nesta unidade, foi proposta
uma nova forma de processar os dados ou pacotes de rede, que chegam pela porta de entrada.
Esperamos nos próximos anos, realizar simulações e testes no protótipo da UCDR.
Ao final destas etapas pretendemos obter o protótipo do processador de rede R2NP em
FPGA para simular e testar em ambiente real o desempenho de processamento em relação aos
demais processadores comerciais (Rede e/ou GPP). Sendo assim, é interesse para os anos de
2004 e 2005, o aumento do número de pesquisadores envolvidos no projeto, principalmente
alunos de graduação, como forma de incentivo à iniciação científica e preparação para o
mestrado e/ou doutorado.
91
7 – REFERÊNCIAS BIBLIOGRÁFICAS
[ADC 2002]
ADC, “Cuda 12000, Packet Telephony Module (PTM)”, 2002, URL:
http://www.adc.com/documentationlibrary/ (último acesso em outubro de
2003)
[Agere 2001a]
Agere System, “Agere System Interface (ASI)”, Product Brief, June
2001, URL: http://www.agere.com/enterprise_metro_access/docs/PB01131.pdf
(último acesso em outubro de 2003)
[Agere 2001b]
Agere System, “Building for Next Generation Network Processors”,
April 2001,
URL:
http://www.agere.com/enterprise_metro_access/network_processors.html
(último acesso em outubro de 2003)
[Agere 2001c]
Agere System, “Fast Pattern Processor (FPP)”, Product Brief,
November 2001,
URL: http://www.agere.com/enterprise_metro_access/docs/PB01132.pdf (último
acesso em outubro de 2003)
[Agere 2001d]
Agere System, “Routing Switch Processor (RSP)”, Product Brief,
April 2001,
URL: http://www.agere.com/enterprise_metro_access/docs/rsp_product_brief.pdf
(último acesso em outubro de 2003)
[Agere 2001e]
Agere System, “The Challenge for Next Generation Network
Processors”, April 2001,
URL:
http://www.agere.com/enterprise_metro_access/network_processors.html
(último acesso em outubro de 2003)
[Ahmadi 1989]
Ahmadi, H., Denzel, W. E., “A Survey of Modern High-Performance
Switching Techniques”, IEEE Journal on Selected Areas in
Communications, Vol. 7, No. 7, September 1989
[Allen 2003]
Allen, J., et al, “PowerNP Network Processor, Hardware, Software
and Applications”, IBM Journal of Research and Development,
Communication Technologies, Vol. 47, No. 2/3, 2003,
URL: http://www.research.ibm.com/journal/rd/472/allen.pdf (último acesso em
outubro de 2003)
92
[Anderson 1975]
Anderson, G. A., Jensen, E. Douglas, “Computer Interconnection
Structures: Taxonomy, Characteristics, and Examples”, ACM
Computing Surveys, Vol. 7, No. 4, December 1975
[Ashenden 1998]
Ashenden, P. J., “The Student’s Guide to VHDL”, Morgan Kaufmann
Publishers, Inc, San Francisco, California, USA, 1998
[Ashenden 2003]
Ashenden, P. J., “The VHDL Cookbook”, unpublished technical
report. Dept. of Computer Science, University of Adelaide, South
Australia, 1990,
URL: http://tams-www.informatik.uni-hamburg.de/vhdl/doc/cookbook (último
acesso em outubro de 2003)
[Aurrecoechea 1998]
Aurrecoechea, C., Campbell, A. T., Hauw, L., “A Survey of QoS
Architectures”, ACM/Springer Verlag Multimedia Systems Journal
Special Issue on QoS Architecture, Vol. 6, No. 3, pp.138-151, 1998
[Blum 2003]
Blum, R., “Network Quality of Service”, International Network
Services,
pp.1-16,
November
20,
2000,
http://www.ins.com/downloads/surveys/sv_network_qos_1100.pdf
URL:
(último
acesso em outubro de 2003)
[Bondalapati 2000]
Bondalapati,
K.,
Prasanna,
V.,
“Reconfigurable
Computing:
Architectures, Models and Algorithms”, Current Science, Vol. 78,
Number 7, pp.828-837, April 10, 2000
[Buyya 1999]
Buyya, R., “High Performance Cluster Computing”, Volume 1,
Prentice Hall, 1999
[Calvert 1992]
Calvert, K. L., Doar, M. B., Zegura, E. W., “A Quantitative
Comparison of Graph-based Models for Internet Topology”,
IEEE/ACM Transactions on Networking, Vol. 5, No. 6, pp.770-783,
December 1992
[Calvert 1997]
Calvert, K. L., Doar, M. B., Zegura, E. W., “Modeling Internet
Topology”, IEEE Communications Magazine, Vol. 35, Issue 6,
pp.160-163, June 1997
[Campbell 2002]
Campbell, A. T., Chou, S. T., Kounavis, M. E., Stachtos, V. D.,
Vicente, J., “NetBind: A Binding Tool for Constructing Data Paths in
93
Network Processor-Based Routers”, IEEE OPENARCH 2002, pp.91103, 2002
[Chameleon 2000]
Chameleon Systems, “CS2000 Reconfigurable Communications
Processor”, Family Product Brief, 2000, URL: http://www.chameleonsystems.com (último acesso em outubro de 2003)
[Chao 2002]
Chao, H. J., “Next Generation Routers”, Proceedings of the IEEE,
Vol. 90, No. 9, pp.1518-1558, September 2002
[Cisco 1998]
Cisco Systems, Catalyst 8500 CSR Architecture, White Paper, 1998,
URL:
http://www.cisco.com/warp/public/cc/pd/si/casi/ca8500/tech/8510_wp.pdf
(último acesso em outubro de 2003)
[Cisco 2000a]
Cisco Systems, 7200 Series Network Processor Family, NPE-400,
NPE-300
and
NPE-225,
Datasheet,
2000,
URL:
http://www.cisco.com/warp/public/cc/pd/rt/7200/nse1/prodlit/nse1_ds.pdf (último
acesso em outubro de 2003)
[Cisco 2000b]
Cisco Systems, Route Switch Processor 8 for Cisco 7500 Series
Routers, Datasheet, 2000,
URL:
http://www.cisco.com/warp/public/cc/pd/rt/7500/prodlit/rsp8_ds.pdf
(último acesso em outubro de 2003)
[Cisco 2000c]
Cisco Systems, Versatile Interface Processor 4 for Cisco 7500 Series
Routers, Datasheet, 2000,
URL: http://www.cisco.com/warp/public/cc/pd/ifaa/ifpz/vrifpz/prodlit/vip4_ds.pdf
(último acesso em outubro de 2003)
[Cisco 2001a]
Cisco Systems White Paper, “The Evolution of high-end Router
Architectures-Basic Scalability and Performance Considerations for
Evaluating
Large-Scale
Router
Designs”,
2001,
http://www.cisco.com/warp/public/cc/pd/rt/12000/tech/ruar_wp.pdf
URL:
(último
acesso em outubro de 2003)
[Cisco 2001b]
Cisco Systems, 1600 Series Router Architecture, 1992-2001, URL:
http://www.cisco.com/warp/public/63/arch_1600_5406.pdf (último acesso em
outubro de 2003)
94
[Cisco 2001c]
Cisco Systems, 2500 Series Router Architecture, 1992-2001, URL:
http://www.cisco.com/warp/public/63/arch_2500_5750.pdf (último acesso em
outubro de 2003)
[Cisco 2001d]
Cisco Systems, 7200 Series Router Architecture, 1992-2001, URL:
http://www.cisco.com/warp/public/63/arch_7200_5810.pdf (último acesso em
outubro de 2003)
[Cisco 2001e]
Cisco Systems, 7500 Series Router Architecture, 1992-2001, URL:
http://www.cisco.com/warp/public/cc/pd/rt/7500/prodlit/7500r_ds.pdf
(último
acesso em outubro de 2003)
[Cisco 2002]
Cisco Systems, 10000 Series Router Architecture, Data Sheet, 19922002,
URL:
http://www.cisco.com/warp/public/cc/pd/rt/10000/prodlit/10ksr_ds.pdf
(último acesso em outubro de 2003)
[Comer 1995]
Comer, D. E., “Internetworking with TCP/IP Principles, Protocols and
Architecture”, Volume 1, 3rd Edition, Pearson, 1995
[Compton 2002]
Compton, K. e Hauck, S., “Reconfigurable Computing: A Survey of
Systems and Software”, ACM Computing Surveys, Vol. 34, No. 2,
pp. 171-210, June 2002
[Coulouris 2000]
Coulouris, G., Dollimore, J., Kindberg T., “Distributed Systems
Concepts and Design”, Addison-Wesley, 3rd Edition, August 11, 2000
[C-Port 2001]
C-Port, “C5 Network Processor”, Data Sheet, March 2001, URL:
http://e-www.motorola.com/webapp/sps/site/taxonomy.jsp?nodeId=01DFTQ3126q62S
(último acesso em outubro de 2003)
[C-Port 2002]
C-Port, “C5e Network Processor”, Product Brief, January 2002, URL:
http://e-www.motorola.com/webapp/sps/site/taxonomy.jsp?nodeId=01DFTQ3126q62S
(último acesso em outubro de 2003)
[Crowley 2000]
Crowley, P., Fiuczynski, Baer, J. L., Bershad, B. N., “Characterizing
Processor Architectures for Programmable Network Interfaces”,
Proceedings of the International Conference on Supercomputing,
Santa Fe, NM, pp.54-65, May, 2000
95
[Crowley 2002a]
Crowley, P. e Yavatkar, R., “An Introduction to Network Processor
Research and Design”, Tutorial apresentado no 35th Annual
International Symposium on Microarchitecture, 2002,
URL: http://www.cs.washington.edu/homes/pcrowley/ (último acesso em
outubro de 2003)
[Crowley 2002b]
Crowley, P., Baer, J. L., “A Modeling Framework for Network
Processor Systems”, Workshop on Network Processor, Cambridge,
MA, 11p., February 3, 2002
[Dantas 2002]
Dantas,
M.,
“Tecnologias
de
Redes
de
Comunicação
e
Computadores”, Editora Axcel Books, 2002
[Dantas 2003]
Dantas, M., “Cluster, Grid Computing e Processamento Paralelo
Oportunístico na Internet”, III Escola Regional de Informática RJ/ES,
pp.41-61, 06 a 08 de outubro de 2003
[Dasan 2001]
Dasan
Networks,
Product
Overview,
2001,
URL:
http://www.dasannetworks.com (último acesso em outubro de 2003)
[David 2003]
David, E., “A Network Processor Platform Implemented in
Programmable Hardware”, Dissertação de mestrado em Engenharia
Elétrica da California Polytechnic State University, USA, Julho, 2003
[De Rose 2001]
De Rose, C. A. F., “Arquiteturas Paralelas”, Escola Regional de Alto
Desempenho, ERAD 2001, Gramado, RS, pp. 3-33, 09 a 13 de janeiro
de 2001
[Dehon 2000]
Dehon, A., “The Density Advantage of Configurable Computing”,
IEEE Computer, Vol. 33, No. 4, pp. 41-49, 2000
[Eggers 1996]
Eggers, H., Lysaght, P., Dick H., McGregor, G., “Fast Reconfigurable
Crossbar Switching in FPGAs”, Proceedings of 6th International
Workshop on Field-Programmable Logic and Applications, Springer
LNCS 1142, pp.297-306, 1996
[EZChip 2002]
EZChip
Network
Processors,
2002,
URL:
http://www.ezchip.com/html/in_prod.html (último acesso em outubro de
2003)
96
[Fewer 2002]
Fewer, C., “Cross Bar Switch Implemented in FPGAs”, White Paper,
Xilinx, WP166 (v1.0), September 9, 2002
[Fewer 2003]
Fewer, C., et al., “A High I/O Reconfigurable Crossbar Switch”, 11th
Annual
IEEE
Symposium
on
Field-Programmable
Custom
Computing Machines, Napa, Califormia, pp.3-10, April 09-13, 2003
[Franklin 2002]
Franklin, M. A., e Wolf, T., “A Network Processor Performance and
Design Model with Benchmark Parameterization”, Workshop on
Network Processors, Cambridge, MA, pp.63-74, February 3, 2002
[Franklin 2003]
Franklin, M. A., e Wolf, T., “Power Considerations in Network
Processor
Design”,
Workshop
on
Network
Processors
and
Applications, Anaheim, California, pp.10-22, February 8-9, 2003
[Freitas 2000a]
Freitas, H. C. e Martins, C. A. P. S., “Processador Dedicado para
Roteamento em Sistemas de Comunicação de Dados”, I Congresso de
Lógica Aplicada à Tecnologia (LAPTEC 2000), São Paulo, SP,
pp.717-721, 2000 (Iniciação Científica)
[Freitas 2000b]
Freitas, H. C. e Martins, C. A. P. S., “Projeto de Processador com
Microarquitetura Dedicada para Roteamento em Sistemas de
Comunicação de Dados”, I Workshop de Sistemas Computacionais de
Alto Desempenho (WSCAD 2000), São Pedro, SP, Brasil, pp.63,
2000 (Iniciação Científica)
[Freitas 2001]
Freitas, H. C. e Martins, C. A. P. S., “Processador de Rede com
Suporte a Multi-protocolo e Topologias Dinâmicas”, II Workshop de
Sistemas Computacionais de Alto Desempenho (WSCAD 2001),
Pirenópolis, GO, pp.31-38, 2001
[Freitas 2002a]
Freitas, H. C. e Martins, C. A. P. S., “NPSIM: Simulador de
Processador de Rede”. XXVIII Latin-American Conference on
Informatics (CLEI 2002), Montevideo, Uruguay, 12p., 2002
[Freitas 2002b]
Freitas, H. C. e Martins, C. A. P. S., “R2NP: Processador de Rede
RISC Reconfigurável”, III Workshop de Sistemas Computacionais de
Alto Desempenho (WSCAD 2002), Vitória, ES, Brasil, pp. 60-67,
2002
97
[Freitas 2002c]
Freitas, H. C. e Martins, C. A. P. S., “Simulation Tool of Network
Processor for Learning Activities”, ASEE/IEEE Frontiers in
Education Conference (FIE 2002), November 6-9, Boston, MA, USA,
Session S2F, pp. 1-6, 2002
[Freitas 2003a]
Freitas, H. C. e Martins, C. A. P. S., “Didactic Architectures and
Simulator for Network Processor Learning”, Workshop on Computer
Architecture Education (WCAE 2003), San Diego, CA, USA, pp.8695, 2003
[Freitas 2003b]
Freitas, H. C. e Martins, C. A. P. S., “Processadores de Rede:
Conceitos, Arquiteturas e Aplicações”, minicurso apresentado na III
Escola Regional de Informática RJ/ES, Vitória, pp.127-166, 07 de
outubro, 2003
[FutureSoft 2003]
FutureSoft, “Challenges in Building Network Processor Based
Solutions”,
White
Paper,
2003,
URL:
http://www.futsoft.com/pdf/NPwp.pdf, (último acesso em outubro de 2003)
[Glesner 1998]
Glesner, M. e Kirschbaum, A., “State-of-the-Art in Rapid
Prototyping”, XI Brazilian Symposium on Integrated Circuit Design
(SBCCI 98), Búzios, Rio de Janeiro, pp.60-65, 1998
[Haidari-khabbaz 2000] Haidari-khabbaz, A., “Hardware Implementation of a High-Speed
Symmetric Crossbar Switch”, Monografia de bacharelado, School of
Engineering Science Communication Networks Laboratory, Simon
Fraser University, Canadá, 27 de novembro, 2000
[Harper 2003]
Harper, S. J., “A Secure Adaptive Network Processor”, Tese em
Engenharia Elétrica do Instituto Politécnico da Virginia, EUA, 30 de
abril, 2003
[Hartenstein 2001]
Hartenstein, R., “A Decade of Reconfigurable Computing: A
Visionary Retrospective”, In Proceedings of International Conference
on Design Automation and Testing in Europe, pp.642-649, 2001
[Hasan 2003]
Hasan, J., Chandra, S., Vijaykumar, T. N., “Efficient Use of Memory
Bandwidth
to Improve Network
Proceedings of the 30
th
Processor Throughput”,
In
International Symposium on Computer
Architecture (ISCA 2003), pp.300-313, June 2003
98
[Hedberg 2002]
Hedberg, D., “Network Processor based Exchange Terminal –
Implementation and Evaluation”, Dissertação de mestrado do
Departamento de Microeletrônica e Tecnologia da Informação do
Royal Institute of Tecnology (KTH), Stockholm, Suécia, 05 de
dezembro, 2002
[Henriksson 2001]
Henriksson, T., “Hardware Architecture for Protocol Processing”,
Tese 911 em Engenharia Elétrica do Instituto de Tecnologia da
Linköpings Universitet, Suécia, 2001
[Hoffmann 2001]
Hoffmann A., Schiebusch, O., Nohl, A., Braun, G., “A Novel
Methodology for the Design of Application Specific Instruction Set
Processors (ASIP) Using the Machine Description Language”, In
IEEE Transactions on Computer-Aided Design of Integrated Cicuits
and Systems, Vol. 20, No. 11, pp.1338-1354, November, 2001
[IBM 2002]
IBM, PowerNP NP4GS3 Databook, 2002, URL: http://www3.ibm.com/chips/products/wired/products/network_processors.html
(último
acesso em outubro de 2003)
[Iliopoulos 2000]
Iliopoulos M. e Antonakopoulos, T., “Reconfigurable Network
Processors Based on Field Programmable System Level Integrated
Circuits”, 10th International Workshop on Field-Programmable Logic
and Applications, Proceedings of the The Roadmap to Reconfigurable
Computing, Villach, Austria, pp. 39-47, August 27-30, 2000
[Intel 2000]
Intel, “IXP 1200 - Network Processor”, Datasheet, 2000, URL:
http://www.intel.com/design/network/products/npfamily/index.htm
(último
acesso em outubro de 2003)
[Intel 2001]
Intel, “WAN/LAN Access Switch Example Design for the Intel IXP
1200
Network
Processor”,
2001,
URL:
http://www.intel.com/design/network/prodbrf/27904401.pdf (último acesso em
outubro de 2003)
[Kalte 2002]
Kalte, H., Langen, D., Vonnahme, E., Brinkmann, A. e Rückert, U.,
“Dynamically Reconfigurable System-on-Programmable-Chip”, 10th
Euromicro Workshop on Parallel, Distributed and Network-based
99
Processing (EUROMICRO-PDP 2002), Canary Islands, Spain,
pp.235-242, January 09-11, 2002
[Karim 2002]
Karim, F., Nguyen, A., Dey, S., “An Interconnect Architecture for
Networking Systems on chips”, IEEE MICRO, Vol. 22, Issue 5,
pp.36-45, September-October, 2002
[Kästner 2003]
Kästner, D., “Classification of Microprocessors”, Material do curso
de Sistemas Embutidos, Departamento de Ciência da Computação,
Universität des Saarlandes, Alemanha, 2003, URL: http://rw4.cs.unisb.de/~kaestner/ES0203.html (último acesso em outubro de 2003)
[Keshav 1998]
Keshav, S., Sharma, R., “Issues and Trends in Router Design”, IEEE
Communications Magazine, Vol. 36, No. 5, pp.144-151, May 1998
[Keyvani 2001]
Keyvani M., “VHDL Implementation of a High-Speed Symmetric
Crossbar Switch”, Dissertação de Mestrado, School of Engineering
Science Communication Networks Laboratory, Simon Fraser
University, Canadá, Agosto, 2001
[Kochte 2003]
Kochte M., Tang, Y., “Packet-Switching Networks on Systems-on-aChip”, Networks on Chip: Seminário de graduação, Universidade de
Stuttgart, Alemanha, 12 de Junho, 2003, URL: http://www.ra.informatik.unistuttgart.de/~tangyi/noc/noc-packet-switched-networks.pdf
(último
acesso
em
outubro de 2003)
[Kohler 2000]
Kohler, M., “NP Complete”, Embedded Systems Programming, 2000,
URL: http://www.embedded.com/2000/0011ia1.htm (último acesso em
outubro de 2003)
[Kounavis 2003]
Kounavis, M. E., Kumar, A., Vin, H., Yavatkar, R. e Campbell, A. T.,
“Directions in Packet Classification for Network Processors”,
Workshop on Network Processors and Applications, Anaheim,
California, 10p., February 8-9, 2003
[Liang 2000]
Liang, J., Swaminathan, S. e Tessier, R., “aSOC: A Scalable, SingleChip Communications Architecture”, International Conference on
Parallel Architectures and Compilation Techniques, pp.37-46,
October 15-19, 2000
100
[Liljeqvist 2002]
Liljeqvist, B., Bengtsson, L., “Grid Computing Distribution Using
Network Processors”, Fourth IASTED International Conference
Parallel and Distributed Computing and Systems, MIT, Cambridge,
USA, pp.12-17, November 4-6, 2002
[Liljeqvist 2003]
Liljeqvist, B., “Visions and Facts – A Survey of Network Processors”;
Dissertação de Mestrado, Chalmers University of Technology,
Suécia, 2003
[Martins 2002]
Martins, C. A. P. S., et al., “Computação Reconfigurável: conceitos,
tendências e aplicações”, Escola de Informática do Norte (EIN), 2002
[Martins 2003]
Martins, C. A. P. S., et al., “Computação Reconfigurável: conceitos,
tendências e aplicações”, Jornada de Atualização em Informática,
Congresso da Sociedade Brasileira de Computação, Capítulo 8, 2003
[Memik 2002]
Memik, G., Memik, S. O. e Mangione-Smith, W. H., “Design and
Analysis of a Layer Seven Network Processor Accelerator Using
Reconfigurable Logic”, The 10th Annual IEEE Symposium on FieldProgrammable Custom Computing Machines, Napa, California,
pp.131-140, 21-24 April, 2002
[Menascé 2003]
Menascé, D. A., Almeida, A. F., “Planejamento de Capacidade para
Serviços na Web, Métricas, Modelos e Métodos”, Campus, 2003
[Mensch 2000]
Mensch. Jr., W. D. e Silage, D. A., “System-on-chip Design
Methodology in Engineering Education”, International Conference on
Engineering Education, ICEE2000 (IEEE/CS), Taipei, Taiwan, pp.
224-228, August 2000
[Misra 2001]
Misra, K. M. e Kharoliwalla, F., “Study of Internet Router
Architectures”, May 1, 2001
URL: http://www.egr.msu.edu/~misrakir/projects/InternetRouters.PDF (último
acesso em outubro de 2003)
[Motorola 1999]
Motorola Corporation, MPC860 PowerQUICC Processor, Hardware
Specifications,
1999,
URL:
www.motorola.com/webapp/sps/site/taxonomy.jsp?nodeId=01M0ylsDFTQ
(último acesso em outubro de 2003)
http://e-
101
[Netto 2001]
Netto, P. O.B., “Grafos: Teoria, Modelos e Algoritmos”, Segunda
Edição, Editora Edgard Blücher, 2001
[Ordonez 2003]
Ordonez, E. D. M., Pereira, F. D., Penteado, C. G., Pericini, R. A.,
“Projeto, Desempenho e Aplicações de Sistemas Digitais em
Circuitos Programáveis (FPGAs)”, Bless Gráfica e Editora Ltda, 2003
[Patterson 2000]
Patterson, D. A. e Hennessy, J. L., “Organização e Projeto de
Computadores: A Interface Hardware/Software”, LTC, 2a Edição,
2000
[Reconfigurable 2003]
Reconfigurable Computing Definition, Association for Computing
Machinery (ACM), 2003,
URL: http://www.acm.uiuc.edu/sigarch/projects/reconf/report_1.html (último
acesso em outubro de 2003)
[Ricarte 1999]
Ricarte,
I.
L.
M.,
“Organização
de
Computadores”,
FEEC/UNICAMP, 1999,
URL: http://www.dca.fee.unicamp.br/courses/EA960/ (último acesso em
outubro de 2003)
[Rocha 2003]
Rocha, A., “Redes de Computadores”, Liga de Ensino do Rio Grande
do Norte, Faculdade Natalense para o Desenvolvimento do Rio
Grande
do
Norte
(FARN),
2003,
URL:
http://www.farn.br/bsi/redes/Redes.pdf (último acesso em outubro de 2003)
[Salefski 2001]
Salefski, B. e Caglar, L., “Re-Configurable Computing in Wireless”,
38th Design Automation Conference, Las Vegas, Nevada, USA,
pp.178-183, June 18-22, 2001
[Seshadri 2003]
Seshadri, M. S., Bent, J., Kosar, T., “Intelligent Routing using
Network Processors: Guiding Design Through Analysis”, Relatório
Técnico do Departamento de Ciência da Computação da Universidade
de Wisconsin, EUA, Abril de 2003
[Shah 2001]
Shah, N., “Understanding Network Processors”, Dissertação de
mestrado, University of California Berkeley, EUA, 2001
[Shah 2002]
Shah, N., Keutzer, K., “Network Processors: Origin of Species”,
Proceedings
of
ISCIS
XVII,
The
Seventeenth
International
Symposium on Computer and Information Sciences, 5p., 2002
102
[Sherwood 2003]
Sherwood, T., Varghese, G., Calder, B., “A Pipelined Memory
Architecture for High
Throughput Network
Processors”, In
Proceedings of the 30th International Symposium on Computer
Architecture (ISCA), pp.288-299, June 2003
[Star 2003]
Star Bridge Systems, 2003, URL: http://www.starbridgessystems.com
(último acesso em outubro de 2003)
[Stenberg 2002]
Stenberg, A., “Network Processor Core Architecture”, Dissertação de
mestrado do Departamento de Ciência da Computação e Engenharia
Elétrica, Divisão Engenharia da Computação da Lulea University of
Technology, Suécia, março, 2002
[Strigel 2002]
Strigel A., Manimaran, G., “A Survey of QoS Multicasting Issues”,
IEEE Communications Magazine, Vol. 40, Issue 6, pp.82-87, June
2002
[Suryanarayanan 2002] Suryanarayanan, D., Byrd, G. T., Marshall, J., “A Methodology and
Simulator for the Study of Network Processors”, Workshop on
Network Processor, Cambridge, MA, 15p., February 3, 2002
[Tanenbaum 2003]
Tanenbaum, A. S., “Redes de Computadores”, Editora Campus, 4a
Edição, 2003
[Tennenhouse 1997]
Tennenhouse, D. L., Smith, J. M., Sincoskie, W. D., Wetherall, D. J. e
Minden, G. J., “A Survey of Active Network Research”, IEEE
Communications Magazine, Volume 35, No. 1, pp.80-86, 1997
[Thiele 2002]
Thiele, L., Chakraborty, S., Gries, M., Künzli, S., “Design Space
Exploration of Network Processor Architectures”, Workshop on
Network Processors, Cambridge, MA, 16p., February 3, 2002
[Troxel 2002]
Troxel, I. A., George, A. D. e Oral, S., “Design and Analysis of a
Dynamically Reconfigurable Network Processor”, IEEE Conference
on Local Computer Networks (LCN), Tampa, Florida, pp.483-492,
November 6-8, 2002
[Tsai 2002]
Tsai, M., Kulkarni, C., Sauer, C., Shah, N., Keutzer, K., “A
Benchmarking Methodology for Network Processors”, Workshop on
Network Processors, Cambridge, MA, 12p., February 3, 2002
103
[Ulmer 2002]
Ulmer, C., Wood, C. e Yalamanchili, S., “Active SANs: Hardware
Support for Integrating Computation and Communication”, Workshop
on Novel Uses of System Area Networks at HPCA, 12p., 2002
[Vitesse 2002]
Vitesse IQ2000, Network Processor Product Brief, 2002, URL:
http://www.vitesse.com/products/briefs/IQ2200_Family.pdf (último acesso em
outubro de 2003)
[Wolf 2000a]
Wolf, T. e Turner, J., “Design Issues for High Performance Active
Routers”,
International
Zurich
Seminar
on
Broadband
Communications, Zurich, Switzerland, pp. 199-205, February 2000
[Wolf 2000b]
Wolf, T., “Design of an Instruction Set for Modular Network
Processors”, IBM Report, RC21865, October 2000
[Wolf 2000c]
Wolf, T., Franklin, M. A., “COMMBENCH – A Telecommunications
Benchmark for Network Processors”, IEEE International Symposium
on Performance Analysis of Systems and Software, Austin, TX, USA,
pp.154-162, April 2000
[Wolf 2000d]
Wolf, T., Franklin, M. A., Spitznagel, E. W., “Design Tradeoffs for
Embedded Network Processors”, Technical Report, WUCS-00-24,
Washington University in St. Louis, USA, July 10, 2000
[Wolf 2001]
Wolf, T., Franklin, M. A., “Locality-Aware Predictive Scheduling of
Network Processors”, IEEE International Symposium on Performance
Analysis of Systems and Software, Tucson, Arizona, USA, pp.152159, November 4-6, 2001
[Xie 2002]
Xie, Haiyong, Zhou, L., Bhuyan, L., “Architectural Analysis of
Cryptographic Applications for Network Processors”, Workshop on
Network Processors, Cambridge, MA, 11p., February 3, 2002
[Xilinx 2002]
Xilinx Development System, “Synthesis and Simulation Design
Guide”, 2002,
URL:
http://toolbox.xilinx.com/docsan/xilinx5/pdf/docs/sim/sim.pdf
acesso em outubro de 2003)
(último
104
8 – BIBLIOGRAFIA SUGERIDA
Os primeiros livros sobre processadores de rede foram lançados recentemente. O
Workshop on Network Processor and Applications seleciona e publica os melhores artigos em
um livro ao final de cada ano. O único material em formato de livro em língua portuguesa é o
nosso minicurso ministrado durante a III Escola Regional de Informática de 2003 [Freitas
2003b]. A relação dos livros segue abaixo (não estão presentes no capítulo de referências):
[1]
Panos C. Lekkas, “Network Processors: Architectures, Protocols and Platforms”,
McGraw-Hill, Agosto de 2003
[2]
Bill Carlson, “Intel Internet Exchange Architecture and Applications: A Practical
Guide to Intel’s Network Processors”, Intel Press, Junho de 2003
[3]
Douglas E. Comer, “Network Systems Design Using Network Processors”, Prentice
Hall, Janeiro de 2003
[4]
Patrick Crowley, et al., “Network Processor Design: Issues and Practices”, Morgan
Kaufmann, Outubro de 2002 (Livro gerado com os melhores artigos do Workshop
on Network Processors – NP1)
105
9 – ANEXOS
Anexo 1: NPSIM: Simulador de Processador de Rede
Artigo publicado no XXVIII Latin-American Conference on Informatics, CLEI 2002,
Montevidéu, Uruguai, 2002.
Anexo 2: Capítulo 5 “Processadores de Rede Comerciais” do Minicurso “Processadores
de Rede: Conceitos, Arquiteturas e Aplicações”
Ministrado e publicado na III Escola Regional de Informática RJ/ES, Vitória ES, 2003.
Artigo publicado no XXVIII Latin-American Conference on Informatics, CLEI’2002, Montevideo, Uruguay, 2002
NPSIM: Simulador de Processador de Rede
Henrique C. de Freitas
Pontifícia Universidade Católica de Minas Gerais, Programa de Pós-graduação em Engenharia
Elétrica,
Belo Horizonte, Brasil, 30535-610
[email protected]
Carlos Augusto P. S. Martins
Pontifícia Universidade Católica de Minas Gerais, Programa de Pós-graduação em Engenharia
Elétrica,
Belo Horizonte, Brasil, 30535-610
[email protected]
Abstract
The main goal of this paper is to present NPSIM (Network Processor Simulator). The NPSIM was developed to
simulate and validate the functioning of our network processor, called RCNP (Reconfigurable CISC Network
Processor). The main feature of network processors is the data communication support between various network
equipments and devices. The RCNP was developed to validate beginning concepts of network microarchitecture,
like described in introduction topic. Although the NPSIM is functional simulation software, it can be used as
learning software. The paper topics will show the RCNP validation process and how basic concepts of processor
microarchitecture and data communication can be learned, through the use of NPSIM simulator.
Keywords: network processors, functional simulator, data communication, processor architecture, learning
Resumo
O objetivo principal deste artigo é apresentar o NPSIM (Network Processor Simulator). O NPSIM foi desenvolvido
com o objetivo de simular e verificar o funcionamento do processador de rede, projetado por nós, chamado RCNP
(Reconfigurable CISC Network Processor). A principal característica dos processadores de rede é o suporte a
comunicação de dados, estabelecendo e efetivando a comunicação entre os diversos equipamentos e dispositivos de
rede. O RCNP foi desenvolvido para validação de conceitos iniciais da proposta de nova microarquitetura de rede,
tal como será descrito no item introdutório. Além de ser um software de simulação funcional, o NPSIM também
pode ser utilizado como software de aprendizagem. Os itens deste artigo irão ilustrar como podem ser trabalhados os
conceitos básicos de arquitetura de processadores de rede e de comunicação de dados, e como foi feita a validação
através do simulador NPSIM.
Palavras chave: processadores de rede, simulador funcional, comunicação de dados, arquitetura de processadores,
aprendizagem.
1
Introdução
O NPSIM foi desenvolvido com base na necessidade de verificação de funcionamento da proposta de
microarquitetura e conjunto de instruções do RCNP (Reconfigurable CISC Network Processor) [10,11]. O RCNP
faz parte do projeto RNP (Reconfigurable Network Processor) que possui ainda o R2NP (Reconfigurable RISC
Network Processor) [12] em desenvolvimento. A versão CISC foi projetada por se tratar de um modelo
conceitualmente mais simples de projetar. Suas características de rede foram validadas e serviram como base inicial
para o projeto R2NP. O NPSIM validou a microarquitetura e o conjunto de instruções do RCNP, através de
simulações [7,13], e garantiu que o projeto pudesse evoluir. O objetivo deste artigo é apresentar o NPSIM, suas
interfaces, funcionalidades (simulações e validação) e as possibilidades de aprendizagem dos conceitos básicos de
arquitetura [28] de processadores de rede e de comunicação de dados [33].
Partindo da validação inicial, constatou-se o potencial do NPSIM para fins didáticos [13]. Através deste simulador
passou a ser possível estudar conceitos de arquitetura [28] tais como: i) Microarquitetura, ii) Conjunto de instruções
(linguagem de máquina), iii) hierarquia de memória, iv) Interfaces de comunicação e v) Desempenho. Estes são
itens genéricos e que se aplicam a todos os tipos de processadores, por isso, estes itens possuem amplitude suficiente
para o estudo de processadores dedicados e neste caso os processadores de rede. Outros itens, referentes à
comunicação de dados [33], podem ser estudados através do NPSIM, são eles: i) Topologias, ii) Redes, iii)
Protocolos e iv) Algoritmos de rede.
Todos os itens citados serão descritos, durante o artigo, ilustrando a potencialidade didática do NPSIM e como sua
estrutura de interfaces ajudou a validar o RCNP. Com isto, pretendemos mostrar que, além de ajudar a entender o
funcionamento dos processadores de rede, que são resultados de projetos recentes das empresas de
microprocessadores, o funcionamento de processadores genéricos também poderão ser entendidos através dos
conceitos já citados.
O processador de rede [20,21] é resultado de pesquisa recente da área. Seu surgimento aconteceu durante meados da
década de 90 e ainda hoje é motivo de segredo para muitas empresas. Alguns datasheets são difíceis de encontrar
tornando o processo de aquisição de informação muito restrito. Podemos citar, entre outras, as seguintes empresas
como fabricantes de processadores de rede: Intel (IXP1200) [17], IBM (NP4GS3) [15], Cisco (Toaster 2) [7],
Motorola/C-Port (C5e) [5], Sitera/Vitesse (PRISM IQ2000) [29], Agere/Lucent (FPP) [1], Lexra (Netvortex) [19],
EZChip (EZChip) [8], MMC (EPIF) [24], Chameleon [3].
O processador de rede é responsável direto pela evolução dos equipamentos de rede [4,16]. Os roteadores ativos
[6,31] são resultado da evolução dos processadores de rede. As microarquiteturas dedicadas favorecem o
desempenho dos equipamentos tornando-os mais eficazes durante o processo de comunicação. A qualidade de
serviço (QoS) é exigência e os processadores de rede estão preparados para atuar de forma eficiente e eficaz para
suportar as necessidades de comunicação.
Poucas pesquisas estão sendo realizadas. Foi constato através de consulta ao sistema Lattes do CNPq e através de
alguns proceedings, que ainda não existem grupos, com exceção do nosso, trabalhando com processadores de rede
em universidades brasileiras. Algumas universidades americanas estão realizando pesquisas na área e entre elas
podemos citar as seguintes: i) University of Washington [27], ii) Washington University in St. Louis [32], iii) North
Caroline State University [7] e iv) University of Califórnia, Berkeley [26]. Recentemente foi criado o Workshop on
Network Processor [34], específico para discutir estudos referentes a processadores de rede dentro do HPCA (High
Performance and Computer Architecture) onde as principais pesquisas são discutidas.
Foi com base na importância dos processadores de rede, que decidimos desenvolver o projeto RNP. Um dos
produtos e também resultado do projeto é o NPSIM. Além da sua capacidade como validador funcional do RCNP,
acreditamos na sua capacidade de auxiliar o ensino de processadores e principalmente na difusão e aprendizagem do
processador de rede, pouco conhecido, porém de extrema importância tecnológica para a sociedade atual.
Este artigo está estruturado com os seguintes tópicos:
Tópico 2: Simulador NPSIM
Tópico 3: Conceitos de Arquitetura e Redes através do NPSIM
Tópico 4: Resultados de Simulações
Tópico 5: Conclusões
Referências
2
2
Simulador NPSIM
Este simulador tem a função de realizar testes funcionais dos diversos blocos do processador. Através deste
simulador é possível escrever e executar diversos algoritmos, escritos em assembly, e visualizar a execução e os
resultados através dos registradores, pilhas e matrizes representados pelos diversos componentes existentes no
compilador C++ Builder 5.0, utilizado para construir e compilar o simulador.
Através deste simulador também é possível estudar o comportamento de um processador de rede CISC, escrever
algoritmos de roteamento e oferecer aos desenvolvedores, a possibilidade de escrever compiladores para o
processador virtual (simulador) de rede, tal como uma máquina virtual.
O simulador está dividido em sete interfaces:
Memória, Registradores e Botões de Acesso Rápido;
Montador (janela de edição do programa assembly)
Buffers Permanentes (buffers reconfiguráveis da porta de entrada)
Buffers Temporários (oito buffers fixos de entrada)
Pacotes de Entrada (janela de edição de pacotes)
Seletor de Conexão (matriz de comutação entre entrada e saída)
Registradores de DMA (acesso direto à memória)
Apenas a primeira interface é fixa. Esta interface, que contém a modelagem da memória, registradores e os botões
de execução, permanece sempre à esquerda do simulador, para que o usuário possa visualizar os resultados que são
comuns a todas as outras interfaces. A primeira e segunda interface são descritas através da figura 1.
2.1 Interface gráfica da Memória, Registradores, Botões de Acesso Rápido e Montador (Assembler)
Como descrito anteriormente, este simulador possui uma interface gráfica fixa (figura 1), comum a todas as outras
janelas gráficas. Esta interface é composta inicialmente pela representação da memória. A primeira coluna
representa o endereço de memória e a segunda coluna a palavra de 1 byte, tamanho máximo de cada célula.
Ao todo são oito registradores de controle, representados pelos seus valores em hexadecimal e decimal. É também
representado o registrador de instrução, registrador de endereços, o registrador de status (informa porta de saída
livre), registrador de Carry, registrador de magnitude (resultado da última operação realizada), contador de
programa e por fim o registrador da palavra de controle (sinal de controle para cada bloco lógico).
Os registradores das portas de entrada e saída e do Seletor de Conexão aparecem com o nome da instrução que os
acessa, como na figura 9. Estes registradores são responsáveis por guardar dados referentes à porta de entrada que
está sendo acessada, porta de saída para qual o pacote está sendo enviado, entre outros.
Figura 1 – Interface Principal
Por fim, a janela fixa termina com os botões de acesso rápido. Estes botões são responsáveis por executar o
3
programa armazenado na memória (Rodar), executar o programa passo a passo (Passos) e resetar o contador de
programa (Resetar).
A primeira janela móvel é o montador (assembler). O montador é responsável pela edição do programa assembly
(instruções dedicadas do processador projetado) e pela conversão das instruções em byte code, que são armazenadas
na memória. O botão Montar converte e armazena os byte codes na memória a partir do endereço da caixa de edição
ao lado.
2.2 Interface gráfica Buffers Permanentes (buffers reconfiguráveis da porta de entrada)
Buffers permanentes (figura 2) significam os buffers reconfiguráveis usados para armazenar os pacotes que não
puderam ser enviados para o destino no momento que chegaram. Esta interface não simula a reconfiguração [18],
porém existem buffers de tamanhos diferentes, usados para receber os pacotes enviados pelos buffers temporários
(oitos buffers para cada entrada física). Ou seja, dependendo do tamanho do pacote um buffer permanente será
escolhido para recebê-lo. Cada buffer permanente possui um registrador que indica qual a entrada que recebeu o
pacote inicialmente. Este registrador ajuda, por exemplo, no momento em que o pacote tem que ser reenviado para a
origem.
Figura 2 – Buffers permanentes
2.3 Interface gráfica Buffers Temporários (oito buffers fixos de entrada)
Cada uma das oito entradas físicas da Porta de Entrada (figura 3) possui um buffer temporário. Este buffer é usado
primeiramente para receber os pacotes e fornecer ao processador a primeira leitura do pacote. Desta forma o
processador pode decidir se re-direciona o pacote imediatamente para a Porta de Saída, através do Seletor de
Conexão, guarda nos buffers reconfigurávéis ou na memória. Neste simulador o pacote é recebido pelos buffers
temporários e só é enviado para reconfiguração após o clique no botão reconfigurar. Desta forma o aluno pode ver o
pacote ser recebido pelo buffer temporário e em seguida ser enviado para o buffer permanente. É importante dizer
que, um buffer permanente só recebe um pacote após o mesmo ter passado por um buffer temporário.
Figura 3 – Buffers temporários
4
Como este simulador foi construído com os buffers permanentes já reconfigurados, o pacote recebido só é enviado
para os buffers que podem recebê-los. Esta é a razão da caixa de edição Qtd. O valor desta caixa define que o pacote
só pode ser enviado para os buffers reconfigurados selecionados. Ou seja, caso este valor seja igual a 10, somente os
buffers entre 10 e 20 poderão ser usados para o cálculo de otimização do armazenamento do pacote. O simulador foi
construído com 20 buffers já reconfigurados, por isto, se o pacote for de 16 kbytes, os buffers de tamanho inferior a
este não poderão ser usados como base de cálculo para recebimento do pacote.
Um buffer temporário pode ser conectado a uma saída por tempo indeterminado usando a instrução FCX. Um byte
setado pela instrução SETDSC pode ser usado para desfazer esta conexão, por isto cada buffer possui um registrador
que guarda este byte.
2.4 Interface gráfica Pacotes de Entrada (janela de edição de pacotes)
Tal como o Montador esta janela (figura 4) oferece uma caixa de edição para criação dos pacotes usados em testes
nos buffers da Porta de Entrada. Após digitar o texto, basta digitar qual a entrada que deverá receber o pacote e
clicar em Enviar. O texto escrito na caixa de edição é convertido (Tabela 1) para ASCII e carregado no buffer
referente à entrada digitada. Existe a opção de converter o pacote para ASCII ou para Hexadecimal. Neste último
caso é necessário que o início da linha comece com duas barras e que contenha apenas números entre 0 e 65535.
Uma nova barra na mesma linha separa números diferentes. Com exceção das barras, espaços e marcadores de
parágrafo são convertidos para ASCII e enviados.
Tabela 1 – Exemplos de conversão
Texto
Conversão
Simulador
53696D756C61646F72 (ascii)
255
323535 (ascii)
//255
FF (hexa)
//44055/762
AC1702FA (hexa)
Figura 4 – Editor de pacotes
2.5 Interface gráfica Seletor de Conexão (matriz de comutação entre entrada e saída)
O Seletor de Conexão (figura 5) nada mais é do que uma chave crossbar configurável. Através desta chave são
possíveis inúmeras combinações entre entrada (buffers) e saída. A interface da figura 5 mostra que o byte 0Ah está
sendo enviado do buffer B9 para a saída S3. Cada linha da matriz é representada por um buffer e cada coluna por
uma saída. Por problemas de espaço e para evitar uma barra de rolagem, os primeiros buffers permanentes
compartilham as linhas com os buffers temporários.
5
Figura 5 – Chave crossbar
2.6 Interface gráfica Registradores de DMA (acesso direto à memória)
Esta interface (figura 6) representa o bloco lógico que lê e escreve dados da entrada na memória ou da memória para
a saída, sem a interferência dos registradores de controle do processador. Este bloco possui alguns registradores que
auxiliam no endereçamento de memória e na escolha dos buffers de entrada e saída. O primeiro registrador guarda a
posição inicial de leitura ou escrita em memória, o segundo registrador guarda o tamanho do pacote e o terceiro a
posição final de memória. Outros dois registradores definem qual buffer será lido ou em qual saída será escrito o
pacote, que estava guardado em memória.
Figura 6 – Bloco DMA
3 Conceitos de Arquitetura e Redes através do NPSIM
Neste tópico serão apresentadas as possibilidades de aprendizagem utilizando o NPSIM. Os conceitos de arquitetura
[28] e de comunicação de dados [33] dos processadores de rede e em específico do RCNP [10,11] serão descritos
nos sub itens a seguir. É importante ressaltar que o NPSIM irá oferecer um conhecimento introdutório sobre
processadores de rede, afinal, existem processadores de rede comerciais com diferentes implementações
arquiteturais e muito mais complexos.
Abstração computacional [28] é o conhecimento dos níveis de arquitetura software / hardware que compõem o
computador, no nosso caso, os processadores de rede. Os níveis de abstração são os seguintes: i) linguagem de alto
nível (Ex.: orientada a objeto), ii) Assembly, iii) Sistema operacional, iv) arquitetura do conjunto de instruções, v)
microarquitetura e vi) Nível lógico digital.
No nosso caso trataremos de um número mais reduzido de níveis. A linguagem de mais alto nível utilizada no
NPSIM é o assembly, não é utilizado sistema operacional e também não será ilustrado o nível digital do RCNP.
6
O NPSIM possui um menu com dois links que oferecem informações sobre o próprio simulador e também sobre o
RCNP. Os links são: i) Sobre (processador de rede, o simulador, arquitetura e instruções do RCNP) e ii) Ajuda
(informações de como utilizar o NPSIM).
3.1 Microarquitetura
Figura 7 - Microarquitetura
Figura 8 - Informações
Através da opção Sobre é possível ter acesso a detalhes da microarquitetura do RCNP. A figura 7 ilustra o diagrama
em blocos do processador de rede. A figura 8 ilustra detalhes dos buffers da porta de entrada e da chave crossbar. É
possível também obter informações referentes à microarquitetura através do texto à esquerda da figura. Portanto,
além de poder simular o código no NPSIM, estão disponíveis nesta opção, os diagramas necessários para entender o
caminho de dados, de controle e também as interligações entre blocos que possibilitam o funcionamento dedicado
para redes de comunicação de dados (Ex. portas de entrada e saída).
3.2 Conjunto de Instruções
As figuras abaixo também fazem parte do menu Sobre. A figura 9 ilustra o conjunto de instruções e o respectivo
código de operação. Por se tratar de um processador conceitual, com o objetivo de otimização dos blocos de rede, o
conjunto de instrução é bastante simples. Não se usa formato de instrução otimizado, cada instrução é codificado por
1 byte. Instruções que possuem endereços de memória, como operandos, ocupam mais posições de memória. A
figura 10 descreve a ação de cada instrução. Estas duas figuras, juntamente com as figuras 7 e 8, oferecem a
possibilidade de estudo do funcionamento e comportamento de cada instrução e o impacto que cada uma delas tem
na microarquitetura, principalmente as específicas de rede, que otimizam o processamento de pacotes. A simulação
de um código, como será visto no item 4, resulta na visualização de causa e efeito das instruções executadas,
favorecendo a melhoria de aprendizagem e mostrando como instruções específicas de rede aumentam o desempenho
de processamento.
Figura 9 – Conjunto de instrução
Figura 10 - Ações
3.3 Hierarquia de Memória
Um ponto importante no estudo da arquitetura de processadores é a hierarquia de memória [28], ou seja, como a
proximidade e o tamanho de cada tipo de memória pode influenciar no desempenho do processador. A figura 11
7
ilustra a estrutura padrão de hierarquia de memória e a hierarquia utilizada no RCNP. Como a microarquitetura é
dedicada para trabalhar em redes de comunicação de dados, quanto mais rápido o pacote, que está na porta de
entrada, for processado ou redirecionado para a saída, maior o desempenho do processador. Por isto que os buffers
de entrada (temporários e permanentes) são os melhores pontos na estrutura de hierarquia do RCNP. Isto ocorre,
porque no RCNP existem dois pontos de referência, o processador e a porta de entrada. Por possuir alocação para os
pacotes, é desnecessário em situação ideal, que os pacotes sejam deslocados da porta de entrada, o que não ocorre
em processadores de propósito geral, que não possuem este tipo de espaço para alocação. As figuras 2 e 3 ilustram a
estrutura de buffers da porta de entrada.
Figura 11 – Hierarquia de memória
3.4 Interfaces de Comunicação
Os blocos funcionais que são responsáveis pela caracterização do RCNP como processador de rede, estão ilustrados
na figura 12. Os blocos do conjunto 1 são dedicados para o recebimento e tratamento dos pacotes. Estão presentes
neste conjunto as portas de entrada e saída, a chave crossbar, os buffers de entrada (temporários e permanentes) e o
registrador de status (guarda saída livre ou ocupada). O bloco 2 representa as interfaces com outros processadores. A
unidade PCI é responsável pela interface com processadores de propósito geral e a unidade dedicada é responsável
pela comunicação entre processadores de tipo RCNP. Esta unidade utiliza protocolo leve para obter maior
velocidade de comunicação. Estas duas unidades de interface não estão representadas no NPSIM.
1
2
Figura 12 – Blocos de comunicação
3.5 Desempenho
O principal motivo para o desenvolvimento dos processadores de rede é o desempenho [28]. A crescente
necessidade por velocidade e qualidade de serviço, principalmente na Internet, tem impulsionado as pesquisas na
área. Através do NPSIM é possível obter por simulações, resultados quantitativos que demonstram a melhoria de
processamento quando se tem uma microarquitetura e conjunto de instruções dedicadas. Os resultados quantitativos
foram obtidos e descritos no item 4. É importante ressaltar que o NPSIM não foi desenvolvido para testes de
desempenho, porém, sua característica de funcionalidade provê a possibilidade de visualização e comparação de
execução das instruções com demais tipos de processadores.
3.6 Redes e Topologias
Do ponto de vista de arquitetura de comunicação de dados [33], duas variáveis importantes no estudo são os tipos de
rede e topologias. Atualmente as redes mais utilizadas são: LAN (Local Area Network), MAN (Metropolitan Area
Network) e WAN (Wide Area Network). As redes locais (LAN) são utilizadas em prédios de instituições e empresas,
as redes MAN e WAN são redes de maior abrangência e se tornaram populares através da Internet. No entanto
outros tipos de redes são muito importantes para o aumento de desempenho de processamento. Quando aglomerados
8
(clusters) [2,25] de processadores ou computadores necessitam de maior resposta ou vazão de dados é necessário à
utilização de redes menores, onde os nós de processamento estão mais próximos. Este tipo de rede é chamado de
System Area Network (SAN). Redes em nível de sistema computacional, onde protocolos leves são responsáveis
pela comunicação entre os processadores, são normalmente utilizadas em aplicações de processamento paralelo ou
distribuído de alto desempenho.
As topologias são a representação física da rede, como os nós (computadores, processadores ou dispositivos) estão
distribuídos. No item resultados, serão descritos três tipos de topologias. Programas foram escritos e simulados para
as topologias que representam clusters em uma rede SAN.
3.7 Protocolos e Programas de Comunicação
O padrão de comunicação entre os equipamentos de uma rede é definido pelo protocolo [33]. Desta forma a troca de
informações é estabelecida através de programas previamente desenvolvidos que são capazes de interpretar
corretamente os dados encontrados em cada posição do pacote.
A figura 1 ilustra o Assembler (Montador). Através do Assembler é possível escrever, editar e carregar na memória o
programa desenvolvido para ser executado pelo NPSIM. A figura 4 ilustra o editor de pacotes. Nesta interface é
possível escrever um pacote e enviá-lo para uma das 8 entradas da figura 2.
O item de resultados irá exemplificar melhor, as topologias e protocolos de comunicação.
4
Resultados de Simulações
Algumas simulações foram realizadas para verificação funcional do RCNP [10,11]. Partindo destes resultados,
também é possível comprovar as potencialidades didáticas do simulador. A seguir serão descritos os programas e
topologias utilizadas para os testes. Será feito análise de como as simulações validam o RNCP e ajudam na
aprendizagem prática dos conceitos ensinados em sala de aula. Não é intenção, destas simulações, comparar o
desempenho entre as topologias. Elas foram escolhidas apenas com o intuito de exemplo didático e como forma de
comparar os resultados quantitativos de acesso à memória e portas de I/O com processadores GPP’s.
As topologias simuladas são:
Hipercubo: Nesta topologia cada nó (vértice) representa um processador RCNP. Um algoritmo de roteamento foi
feito e está descrito na tabela 2. Nesta topologia o endereço de cada vértice é diferente em apenas 1 bit para o
endereço do vértice adjacente. Este foi o critério usado para cálculo de rota.
Anel unidirecional: Apenas um processador RCNP é responsável por criar esta topologia. A chave crossbar interliga
todos os nós da rede. Nesta topologia, a saída do computador, à esquerda, está conectado com a entrada do
computador à direita.
Árvore balanceada: Cada vértice também é um processador RCNP. Neste caso o programa de roteamento utiliza a
padronização de endereços existente na topologia. Os endereços crescem da esquerda para a direita.
Figura 13 – Topologias simuladas
A tabela 2 descreve os três programas e a quantidade de ciclos que foi gasto por cada instrução. É importante
ressaltar que o RCNP não utiliza pipeline, por isto a quantidade de ciclos por instrução é alta.
A quantidade de ciclos por instrução, mostrado na tabela 2, não é resultado do simulador. Estes ciclos foram
definidos no projeto das instruções e estão apenas ilustrando a quantidade que cada instrução gasta para ser
executada antes que outra instrução comece a ser processada.
9
Tabela 2 – Programas testados
Qtd.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Hipercubo
LDX F,000006
LDI D,03
PUT
SUI B,00
JZ 000000
LDI B,00
LDI C,05
ENT BC
XOR D
MOV E,A
JZ F
ANI A,01
JMZ 000029
ANI E,02
JMZ 000025
LDI B,03
SEC
JMP F
LDI B,02
SEC
JMP F
LDI B,01
SEC
JMP F
Ciclos
5
5
4
5
5
5
5
4
4
4
4
5
5
5 NE
5 NE
5 NE
4 NE
4 NE
5 NE
4 NE
4 NE
5
4
4
Árvore Balanceada
LDI D,06
PUT
SUI B,00
JZ 000025
LDI B,00
LDI C,05
ENT BC
SUB D
JMI 00001A
LDI B,04
SEC
JMP 000002
JZ 000025
LDI B,05
SEC
JMP 000002
HLT
-------------------------------------------------------------------------------------------------------------------------------
Ciclos
5
4
5
5
5
5
4
4
5
5
4
5
5 NE
5 NE
4 NE
5 NE
4 NE
----------------------------------------------------------------
Anel unidirecional
LDI A,07
LDI B,01
PUT B
LDI B,08
SEC
FCX
PUT B
DCR B
SEC
FCX
DCR A
JMZ 000009
HLT
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Ciclos
5
5
4
5
4
4
4
4*8
4*7
4*7
4*7
5*8
4
----------------------------------------------------------------------------------------------------
NE: Não executado na simulação
Comparando os resultados de simulação do RCNP [10,11] com resultados de processadores de propósito geral,
chegamos aos resultados ilustradas na figura 14 (simulação da topologia hipercubo). Para o processador RCNP
simulado através do NPSIM, foi obtido valores baixos de acesso à memória e às portas de entrada e saída. Com
apenas duas intruções de I/O foi possível redirecionar um pacote inteiro da origem para o destino. Para um
processador de propósito geral de mesmas características, foi necessário a utilização de 21 instruções. Estes valores
foram obtidos simulando um pacote pequeno. Quanto maior o pacote e mais complexo for o cabeçalho, maior será o
ganho de performance obtido pelo RCNP em relação a um GPP. Como o GPP tem que guardar o pacote e várias
informações na memória, o acesso de leitura e escrita também é muito maior, e cresce juntamente com o tamanho do
pacote.
Um processador dedicado de rede opera com um desempenho muito mais rápido do que um GPP (General-purpose
processor). Resultados como estes ajudam a entender a necessidade de projetos otimizados e que venham
acrescentar velocidade de processamento em ambientes exigentes como a comunicação de dados.
Dentro do projeto RNP está em fase de desenvolvimento a versão RISC do RCNP, o R2NP. Este processador
aproveita as vantagens da microarquitetura de rede otimizada com as vantagens do modelo RISC. Está em fase final
o projeto de simulador reconfigurável [30] que verificará funcionalmente o R2NP. Este simulador tem a finalidade
de se tornar uma ferramenta eficaz no ensino de arquitetura de computadores, uma fez que seu objetivo é a
flexibilidade de simulações. Qualquer tipo de processador poderá ser simulado apenas acrescentando arquivos de
configuração específicos.
Acesso a memória e portas de
I/O
90
81
80
70
Acessos
60
50
Memória
40
I/O
30
20
10
21
12
2
0
RCNP
GPP
Processadores
Figura 14 – Quantidade de Acessos
10
5
Conclusões
Através do NPSIM foi possível comprovar que processadores de rede são muito mais eficientes que processadores
de propósito geral. Chegamos a constatar um ganho 7 vezes de performance, em relação a um processador GPP,
para acesso a memória. O conjunto de instruções de rede otimizou consideravelmente o processamento de pacotes.
Com apenas 2 instruções é possível redirecionar todo o pacote para a saída, o que não acontece com o GPP, que
precisa guardar em memória para depois redirecionar. As interfaces de auxílio, encontradas no menu, acrescentam
conhecimento à cerca de processadores de rede e do funcionamento do RCNP. As interfaces de execução ilustram o
movimento de dados, que ocorre durante a execução dos programas, podendo passo a passo, ilustrar a seqüência
correta de efeito e influência de cada instrução nos blocos funcionais ilustrados em todas as interfaces do NPSIM.
Ressaltamos como resultados obtidos pelo NPSIM, a validação da microarquitetura e conjunto de instruções do
RCNP, que comparadas se mostraram bastante eficientes.
Podemos concluir que o objetivo do NPSIM foi alcançado. Desenvolvemos uma ferramenta de simulação capaz de
validar o projeto inicial do RCNP e de oferecer uma nova opção de aprendizagem [13] de arquitetura de
processadores de rede e comunicação de dados.
Como contribuição, apresentamos um simulador que além de todas as características já mencionadas, procura
difundir os processadores de rede, ainda pouco conhecidos, na comunidade científica. Como descrito na introdução,
existem poucas pesquisas na área de processadores de rede. Porém podemos ressaltar o projeto do simulador
CnetSim (Component Network Simulator) [7], desenvolvido na North Caroline State University em parceria com a
Cisco para o processador Toaster 2. Os objetivos principais desta pesquisa são: i) Descrever a arquitetura do Toaster
2, ii) Obter resultados de performance e iii) Uma metodologia de estudo e desenvolvimento de hardware.
Entre as características mencionadas do projeto do simulador CNetSim, ressaltamos os resultados de performance,
não implementado no NPSIM. Porém, a principal diferença se encontra no fato de que o CNetSim simula um
processador comercial e o NPSIM simula um processador conceitual. Os objetivos, descrição de arquitetura e
método de estudo (simulador didático) são encontrados no NPSIM.
As pesquisas relacionadas com processadores de rede reconfiguráveis [10,11,12] ainda são mais recentes e podemos
citar as seguintes universidades: i) University of California, Los Angeles [9], ii) University of Florida [14], iii)
University of Patras [23]. A computação reconfigurável [18] tem por objetivo aumentar a flexibilidade e o
desempenho dos processadores de rede.
Como trabalhos futuros da nossa pesquisa, podemos citar o seguinte: i) Acrescentar contadores no NPSIM para
testes e simulações de desempenho, ii) Simular o R2NP com o simulador reconfigurável (Reconf_KMT) [30], iii)
Simular o R2NP em VHDL (VHSIC Hardware Description Language) [22], iv) Prototipar o R2NP em FPGA (Field
Programmable Gate Array) [22], v) Simular o R2NP em uma rede de comunicação real e vi) criar ambiente de
auxílio ao estudo através dos simuladores de processadores de rede desenvolvidos.
Referências
[1] Agere System, Fast Pattern Processor (FPP) Product Brief, April 2001, http://www.agere.com
[2] Buya, R., High Performance Cluster Computing, Volume 1, Prentice Hall, 1999
[3] Chameleon Systems, “CS2000 Reconfigurable Communications Processor”, Family Product Brief, 2000
[4] Cisco Systems White Paper, “The Evolution of high-end Router Architectures-Basic Scalability and
Performance Considerations for Evaluating Large-Scale Router Designs”, 2001, http://www.cisco.com
[5] C-Port, C5e Network Processor Product Brief, January 2002, http://www.motorola.com
[6] D. L. Tennenhouse, J. M. Smith, W. D. Sincoskie, D. J. Wetherall, G. J. Minden, “A Survey of Active Network
Research”, IEEE Communications Magazine, Volume 35, No 1, pp.80-86, 1997
[7] D. Suryanarayanan, G. T. Byrd and J. Marshall, “A Methodology and Simulator for the Study of Network
Processors”, Workshop on Network Processor (NP1 at HPCA 8), Cambridge Massachusetts, February 2-6,
2002
[8] EZChip Network Processors, http://www.ezchip.com
[9] G. Memik, S. O. Memik, W. H. Mangione-Smith, “Design and Analysis of a Layer Seven Network Processor
Accelerator Using Reconfigurable Logic”, The 10th Annual IEEE Symposium on Field-Programmable Custom
Computing Machines FCCM’02, Napa, California, 21-24 April, 2002
11
[10] H. C. Freitas, C. A. P. S. Martins, “Processador de Rede com Suporte a Multi-protocolo e Topologias
Dinâmicas”, II Workshop de Sistemas Computacionais de Alto Desempenho, WSCAD’2001, Pirenópolis - GO,
Brasil, pp.31-38
[11] H. C. Freitas, C. A. P. S. Martins, “Projeto de Processador com Microarquitetura Dedicada para Roteamento em
Sistemas de Comunicação de Dados”, I Workshop de Sistemas Computacionais de Alto Desempenho,
WSCAD’2000, São Pedro - SP, Brasil, pp.63, (Iniciação Científica)
[12] H. C. Freitas, C. A. P. S. Martins, “R2NP: Processador de Rede RISC Reconfigurável”, III Workshop de
Sistemas Computacionais de Alto Desempenho, WSCAD’2002, Vitória, ES, Brasil, pp. 60-67
[13] H. C. Freitas, C. A. P. S. Martins, “Simulation Tool of Network Processor for Learning Activities”. Frontiers in
Education Conference (FIE 2002), Boston, MA, USA, November 2002, Session S2F, pp.1-6
[14] I. A. Troxel, A. D. George, S. Oral, “Design and Analysis of a Dynamically Reconfigurable Network
Processor”, IEEE Conference on Local Computer Networks (LCN), Tampa, Florida, November 6-8, 2002
[15] IBM PowerNP NP4GS3 Databook, http://www.ibm.com
[16] Intel WAN/LAN Access Switch Example Design for the Intel IXP 1200 Network Processor, May, 2001,
http://www.intel.com
[17] Intel, “IXP 1200 - Network Processor”, Datasheet, May 2000, http://www.intel.com
[18] K. Compton, S. Hauck, “Reconfigurable Computing: A Survey of Systems and Software”, ACM Computing
Surveys, Vol. 34, No. 2, June 2002, pp. 171-210
[19] Lexra, NetVortex Network Communications System Multiprocessor NPU, http://www.lexra.com
[20] Lucent Technologies, Building for Next Generation Network Processors, September 1999
[21] Lucent Technologies, The Challenge for Next Generation Network Processors, September 10, 1999
[22] M. Glesner, A. Kirschbaum, “State-of-the-Art in Rapid Prototyping”, XI Brazilian Symposium on Integrated
Circuit Design, SBCCI’98, Búzios, Rio de Janeiro, 1998, pp.60-65
[23] M. Iliopoulos, T. Antonakopoulos, “Reconfigurable Network Processors Based on Field Programmable System
Level Integrated Circuits”, Field-Programmable Logic and Applications, The Roadmap to Reconfigurable
Computing, 10th International Workshop, FPL 2000, Villach, Austria, August 27-30, 2000, pp. 39-47
[24] MMC Networks, “EPIF-105, EPIF-200, GPIF-207, XPIF-300, Packet Processors”, http://www.mmcnet.com
[25] Myrinet Overview, http://www.myri.com/myrinet/overview/index.html
[26] N. Shah; “Understanding Network Processors”, Trabalho de Dissertação apresentado na Universidade de
Berkeley, 4 de setembro de 2001
[27] P. Crowley, J.-L. Baer, “A Modeling Framework for Network Processor Systems”, Workshop on Network
Processor (NP1 at HPCA 8), Cambridge Massachusetts, February X-X, 2002
[28] Patterson, D. A., J. L. Hennessy, Computer Organization and Design: The Hardware/Software Interface,
Morgan Kaufmann Publisher, 1997
[29] Sitera IQ2000, Network Processor Product Brief, http://www.sitera.com
[30] T. H. Medeiros, C. A. P. S. Martins, “Reconf_KMT, Uma Ferramenta Reconfigurável para a Simulação de
Microprocessadores”, III Workshop de Sistemas Computacionais de Alto Desempenho, WSCAD’2002, Vitória,
ES, Brasil, pp. 32-38
[31] T. Wolf and J. Turner, “Design Issues for High Performance Active Routers”, International Zurich Seminar on
Broadband Communications, Zurich, Switzerland, February 2000, pp. 199-205
[32] T. Wolf and M. A. Franklin, “Design of an Instruction Set for Modular Network Processors”, IBM Research
Report, RC21865, October 2000
[33] Tanembaum, A. S., Redes de Computadores, 3a Edição, Editora Campus, 1997
[34] Workshop on Network Processor, http://www.cs.washington.edu/NP2/
12
Capítulo sobre Processadores Comerciais do Minicurso Processadores de Rede: Conceitos, Arquiteturas
e Aplicações. Publicado na III Escola Regional de Informática RJ/ES, Vitória, 07 de outubro de 2003
141
5. Processadores de Rede Comerciais
Apresentamos nesta seção os Processadores de Rede comerciais de cada fabricante
descrito na introdução. A descrição dos principais blocos lógicos, o funcionamento e
alguns dados quantitativos de cada processador. Na seção 8 apresentamos alguns
resultados da nossa proposta de um processador acadêmico.
Os Processadores de Rede comerciais possuem uma arquitetura muito
parecida com a que foi descrita na seção 4, como sendo de referência. Neste tópico
iremos descrever arquiteturas específicas de alguns fabricantes.
5.1. Motorola – PowerQUICC Family
Neste tópico será apresentado o processador de comunicação de dados MPC860
[Motorola 1999] da família PowerQUICC. As aplicações principais deste processador
são: roteadores e switches de LAN/WAN, dispositivos de integração de redes,
concentradores de rede, gateways, DSL/cable modems e sistemas de voz sobre IP.
A classificação da Motorola para os Processadores de Rede define que estes
são destinados ao aumento de desempenho na qualidade de serviço (QoS), o que não
se aplica, neste caso, aos processadores de comunicação de dados da Motorola. Porém
estas duas classes de processadores da Motorola são complementares.
O MPC860 possui um barramento auto-ajustável de 8-, 16-, e 32 bits. Existem
três blocos principais na figura 5.1, que serão descritos com mais detalhes a seguir:
Figura 5.1. – Arquitetura do MPC860
Bloco 1 (PowerPC core):
Este bloco possui o processador principal de 32 bits (PowerPC) responsável
pela execução dos códigos das camadas mais altas, com o intuito de aumentar o
throughput (vazão). Possui cache de instrução e de dados de 4kbytes e duas unidades
de gerenciamento de memória, relacionada cada uma com seu respectivo cache.
Bloco 2 (System Interface Unit):
Bloco responsável pela interface do barramento interno com barramentos
externos. Possui uma controladora de memória, um barramento de interface, uma
unidade de funções do sistema, clock e uma unidade de interface PCMCIA.
Bloco 3 (Communications Processor Module):
Este é o módulo de comunicação de dados. Através deste modulo é possível
enviar e receber dados de diferentes tipos de dispositivos através de quatro canais
seriais de comunicação (SCC) e dois de gerenciamento (SMC). Os dispositivos
142
conectados podem ser usados de forma individual ou, através destes canais, usar um
barramento multiplexador por divisão de tempo.
Este módulo possui um micro-controlador de 32 bits e 16 canais seriais de
DMA (Acesso Direto a Memória). Oito canais para transmissão e oito para recepção.
Os canais de DMA são de uso exclusivo do micro-controlador, sendo usados para
obter e mover dados para a memória.
Alguns dos protocolos suportados por este módulo são: Ethernet, Fast
Ethernet, ATM, HDLC, Appletalk, UART (Universal Asynchronous Receive and
Transmit) e ISDN.
A comunicação entre os dois processadores é feita através da memória interna.
Através desta memória cada processador pode escrever bits de controle e ler bits de
status, possibilitando a requisição e resposta dos dados.
Neste processador o processamento “rápido” é feito pelo micro-controlador e
o processamento “lento” é feito pelo PowerPC.
5.2. Motorola/C-Port – C5 Family
Esta família de processador foi projetada pela C-Port / Motorola [C-Port 2001, 2002]
para aplicações de rede mais ligada à qualidade de serviço QoS. Portanto, as duas
famílias de processadores da Motorola se complementam, um estabelece a
comunicação com mais consistência e o outro prioriza os critérios de QoS, exigência
crescente entre as aplicações e serviços de rede.
Os principais blocos do C-5 NP (Network Processor), são os seguintes (figura
5.2):
•
Channel Processors (CP)
•
Executive Processor (EP)
•
Fabric Processor (FP)
•
Buffers Management Unit (BMU)
•
Table Lookup Unit (TLU)
•
Queue Management Unit (QMU)
Channel Processors
O C-5 NP possui dezesseis processadores de canal que recebem, processam e
transmitem os dados. O número de processadores por porta é configurável,
dependendo do tipo de interface. Inicialmente um processador é alocado para
aplicações onde a largura de banda é média, porém quando há necessidade de
utilização de uma interface de alta velocidade, múltiplos processadores podem ser
alocados por porta. Múltiplas portas podem alocar apenas um processador, neste caso
é utilizado um multiplexador externo e o tipo de aplicação é para aplicação de banda
baixa.
Esta arquitetura suporta protocolos seriais e paralelos:
•
10Mb Ethernet (RMII)
•
100Mb Ethernet (RMII)
143
•
1Gb Ethernet (RMII e TBI)
•
OC-3
•
OC-12
•
DS1/DS3, através de multiplexadores externos
Executive Processor
Este processador é o ponto principal de processamento. Ele é responsável por
gerenciar as interfaces e suas funções são:
•
Resetar e iniciar o C-5 NP
•
Carregar o programa e controla os CP’s
•
Controla as exceções
•
Gerenciar a interface host pela PCI
•
Gerenciar a interface PCI, o barramento e a memória PROM
O sistema de interface é composto por:
•
PCI: Utilizada para conectar com outros processadores (host)
•
SBI: Interface bidirecional de propósito geral
•
PROM: Memória flash usada para boot. Interface de baixa velocidade.
Tamanho máximo de 8Mbytes.
Fabric Processor
Este processador atua como uma interface de rede de alta velocidade. Ele
suporta transferência bi-direcional de pacotes, frames ou células do C-5 NP para as
interfaces de hardware que provêem conectividade com outros Processadores de Rede
ou hardwares de processamento similar.
Buffers Management Unit
Esta unidade é responsável pela interface do C-5 NP com a arquitetura de
pipeline externo, Single Data Rate Synchronous DRAM. A memória externa é
particionada e usada como buffers para receber e transmitir dados entre CP’s, FP e
EP. Ela está no segundo nível de hierarquia de memória do Executive Processor.
Table Lookup Unit
É responsável pela busca e a atualização em tabela e serviços associados para
os processadores CP, EP e FP. Possui também interface para memória externa.
Queue Management Unit
Gerencia o número de aplicações definidas nos descritores de fila. Esta
unidade possui um chip interno responsável por guardar os descritores na memória
SRAM externa.
144
Figura 5.2. – Arquitetura do C-5 NP
5.3. Intel – IXP1200
Este Processador de Rede [Intel 2000] (figura 5.3) é composto por sete processadores
RISC. O primeiro processador é chamado de StrongARM e é responsável pelo
processamento mais complexo, tal como construção e manutenção de tabelas e
gerenciamento da rede. Os outros seis processadores são chamados de microengines.
Eles trabalham com multi-processamento e multi-thread e são responsáveis pelo
processamento e re-direcionamento dos pacotes. Com base nestes dados iniciais, já é
possível definir que, a classe de processamento “rápido” está relacionada com as
microengines e a classe de processamento “lento” está relacionada com o processador
StrongARM.
Figura 5.3. – Arquitetura do IXP1200
A seguir serão descritas algumas características básicas de cada bloco lógico:
Processador StrongARM
Processador RISC de 32 bits, com 16kbytes de cache de instrução e 8kbytes
de cache de dados. Possui um mini-cache de 512bytes, unidade de gerenciamento de
memória e acesso às unidades FBI, PCI e memória SDRAM.
Microengines
Suportam multi-thread, possuem ULA’s (Unidades Lógicas e Aritméticas) e
128 registradores de propósito geral e 128 de transferência. Possuem cache de
instrução e de dados e acesso à unidade FBI, aos canais PCI DMA, SRAM e
SDRAM.
145
Memórias
A memória SDRAM possui um máximo de endereçamento de 256Mbytes e a
SRAM um máximo de 8Mbytes. Existe também uma memória FlashROM de
8Mbytes para boot do processador StrongARM.
Unidade FBI e Barramento IX
A unidade FBI trabalha na camada MAC sobre o barramento IX e é
responsável pelo serviço de periféricos. O barramento IX possui 64 bits em 66 MHz e
é responsável pela interface com a ETHERNET, ATM e outros processadores da
família IXP.
Unidade PCI
É uma unidade padrão PCI de 32 bits responsável pela interface com outros
dispositivos PCI, processadores (CPU’s) e dispositivos MAC. Opera em uma
freqüência de 66 Mhz.
Este processador possui ainda uma porta serial UART (Universal
Asynchronous Receive and Transmit), e quatro portas I/O de propósito geral.
A família de Processadores de Rede da Intel ainda é composta pelos seguintes
processadores: IXP2850, IXP2800, IXP2400, IXP425, IXP422, IXP421 e IXP420.
5.4. IBM – PowerNP NP4GS3
Serão descritos neste tópico, os principais blocos do NP4GS3 (figura 5.4),
Processador de Rede IBM [IBM 2002].
Multiplexador Camada Física
Provê a interface do Processador de Rede com portas de comunicação externa.
Existem dez unidades de transferência de dados (Data Mover Units), sendo que, cinco
de entrada e cinco de saída. Quatro pares são usados para interfaces externas. Cada
DMU suporta os seguintes tipos de configuração:
•
10 x 10/100 FDX Ethernet, por DMU
•
1 x 1GB, por DMU
•
4 x OC-3, por DMU
•
1 x OC-12, por DMU
•
1 x OC-48, por 4 DMU’s
O outro par DMU é para comunicação interna ao processador (Wrap Port).
Ingress EDS (I-EDS)
Este bloco é responsável por encaminhar os frames recebidos pelo DMU. Suas
principais funções são:
•
Guardar os frames em memória interna RAM.
•
Filtrar e decidir algumas alterações no frame.
•
Desenfileirar, encaminhar ou descartar o frame.
146
Switch Interface
Provê uma célula de dados baseado na interface entre NP’s via um switching
fabric (para três ou mais NP’s) ou conexão direta entre dois NP’s. Este bloco está
dividido nas seguintes partes:
•
I/E-SDM: Interface lógica entre o I/E-EDS e a célula.
•
I/E-SCI: Transmite e recebe células da interface física.
•
DASL: Interface física entre:
o NP e switch fabric
o Entrada/saída de 1 NP
o Entrada/saída de 2 NP’s
Egress EDS (E-EDS)
Suas principais funções são:
•
Receber frames do Switch Interface.
•
Enfileirar os frames e guardar em memória RAM externa.
•
Processar os pacotes, desenfileirar e encaminhar os frames.
Shaper
Gerencia a largura de banda por frame com base nas portas Egress – DMU.
Embedded Processor Complex
Determina o que deve ser feito com os frames recebidos pelo I-EDS e E-EDS.
Contém oito Dyadic Picoprocessors e nove co-processadores.
“O código faz parecer que o processador é um ASIC programável”.
Embedded PowerPC (ePPC)
O PowerPC 405 engine foi desenvolvido para controle de funções de rede tais
como:
•
Encaminhar e filtrar pacotes analisando campos do protocolo IP.
•
Controlar protocolos de roteamento tal como: RIP, OSPF e BGP.
•
Gerenciar, configurar, diagnosticar e suportar agentes SNMP.
System Memory
Este bloco suporta memórias interna e externa. Os tipos são:
•
SRAM (interna)
•
Z BT SRAM (externa)
•
DDR SDRAM (externa)
147
Figura 5.4. – Arquitetura do NP4GS3
5.5. Lucent/Agere – FPP/ASI/RSP
A solução da Lucent/Agere [Agere 2001] consiste em três tipos de processadores:
FPP (Fast Pattern Processor), RSP (Routing Switch Processor) e ASI (Agere System
Interface).
A figura 5.6 ilustra a arquitetura da solução usando os três processadores. O
pipeline de dados é realizado através de interface física entre o FPP e o RSP. O
processador ASI é utilizado apenas quando há um excesso no gerenciamento.
Figura 5.6. – Arquitetura integrada dos três processadores
Fast Pattern Processor (FPP)
O FPP (figura 5.7) é um processador com pipeline e suporte até 64 threads.
Cada unidade de pacote de dados (PDU) que chega do barramento UTOPIA é
assinalado como uma nova thread. O suporte em hardware para o chaveamento de
contexto habilita o FPP a processar múltiplas PDU’s em paralelo.
148
Figura 5.7. – Arquitetura do FPP
As principais aplicações para este processador são:
•
Roteadores e switches;
•
Firewalls, gerenciamento e monitoramento de redes;
•
Segmentação ATM e Frame Relay;
•
Processamento de lista e controle de acesso.
Routing Switching Processor (RSP)
O RSP (figura 5.8) recebe a classificação dos dados e as PDU’s do FPP e
entrega para a fabric. As quatro principais funções do RSP são: enfileiramento,
gerenciamento de tráfego, gerenciamento de modelo e modificação de pacote.
O RSP recebe os pacotes de instrução do FPP e guarda as PDU’s na SDRAM.
Baseado nos cálculos de gerenciamento de tráfego, as PDU’s podem ser enfileiradas
ou descartadas. A PDU pode então, ser transmitida ou buscada de memória,
modificada e então transmitida.
Figura 5.8. – Arquitetura do RSP
Agere System Interface (ASI)
A principal função do ASI (figura 5.9) é referente ao processamento que
requer o caminho “lento”. Este processamento é caracterizado por: roteamento,
atualizações em tabelas, atualizações em filas, exceções e estatísticas.
Existe uma interface PCI para gerenciamento externo e uma interface PCI133
SDRAM, para acesso à memória.
149
Figura 5.9. – Arquitetura do ASI
5.6. EZChip – NP - 1
O NP-1 [EZChip 2002] é um Processador de Rede full-duplex de 10Gbits camada 7.
Este processador incorpora a tecnologia TOPcore (Top Optimized Processing Core),
que consiste em um array integrado de processadores customizados em uma
arquitetura super-escalar que provê desempenho e flexibilidade de processamento de
pacotes.
Suas principais aplicações são:
•
Equipamentos de rede, tais como roteadores, switches e gateways;
•
Balanceamento de carga;
•
Analisadores e testadores de rede;
•
Firewalls e VPN’s.
A figura 5.10 ilustra as interfaces do NP-1.
Figura 5.10. – Interfaces do NP-1
Interfaces:
•
Uma porta OC-192 com interface SPI4.2;
•
Duas portas Ethernet 10 Gbits com uma MAC integrada;
•
Oito portas Ethernet 1 Gbit com oito MAC’s integradas de 10/100/1000
Mbps;
•
Uma interface padrão CSIX (Common Switch Interface) provê
conectividade com um switch fabric;
•
Uma interface PCI é usada para interconectar o NP-1 com outro tipo de
processador.
150
A figura 5.11 ilustra a arquitetura TOPcore. A função de cada estágio é a
seguinte:
•
TOPparse: identificar protocolos e extrair cabeçalhos dos pacotes;
•
TOPsearch: executar lookups em diferentes níveis;
•
TOPresolve: assinala pacotes para enfileirar ou enviar para portas;
•
TOPmodify: modifica conteúdo dos pacotes;
Figura 5.11. – Arquitetura do NP-1
5.7. Sitera/Vitesse – Prism IQ2000 Family
Este é um Processador de Rede [Vitesse 2002] (figura 5.12), que trabalha como um
processador padrão. Enquanto o processador padrão faz o trabalho de controle,
processamento e gerenciamento de sistemas, o co-Processador de Rede faz o trabalho
de processamento dos pacotes, classificação, lookups e análise de QoS (Quality of
Service) e Cós (Class of Service). O IQ2000 trabalha na camada 2 e 3 em
equipamentos como switches e roteadores e suporta pacotes com taxas de 2.5Gbps.
Figura 5.12. – Arquitetura do IQ2000
Algumas aplicações do IQ2000:
•
Roteamento de multi-protocolos complexos;
•
Classificação, filtragem, inspeção e criptografia;
•
Políticas de QoS;
•
Multicast;
•
Tradução de endereços de rede;
•
Outras operações de processamento de pacotes.
151
Algumas características técnicas:
•
Quatro processadores escalares de 200Mhz;
•
Largura de banda (DS-0 a OC-48);
•
Suporte nativo para implementações MIPS, PowerPC e outros RISC’s;
•
Co-processadores especializados;
•
Conjunto de instruções especializado para operações de rede;
•
Suporte em hardware para Qualidade de Serviço (QoS)
5.8. Chameleon CS2000 Family
O processador de comunicação reconfigurável da Chameleon Systems [Chameleon
2000] foi o primeiro da indústria de Processadores de Rede a utilizar reconfiguração
(seção 8.1.) dinâmica como parte do sistema normal de operação. A arquitetura do
CS2000 é ilustrada na figura 5.13.
Algumas características técnicas do CS2000:
•
Fabric reconfigurável de 32 bits;
•
84 unidades de caminho de dados de 32 bits;
•
24 unidades de multiplexadores de 16x24 bits;
•
3000 MMACS de 16 bits;
•
24000 MOPS de 16 bits;
•
Fabric reconfigurável em 1 ciclo de clock;
•
Canais de voz/dados/vídeo por chip;
•
Processador ARC integrado de 32 bits;
•
Controlador PCI integrado de 32 bits;
•
Controlador de memória integrado de 64 bits;
•
Controlador de DMA integrado de 16 canais;
•
160 pinos de entrada e saída programáveis;
•
Largura de banda de 2Gbytes por segundo.
Algumas de suas principais aplicações são: Estações base sem fio de 2G e 3G,
Wireless Local Loop (WLL) [Salefski 2001], Voz sobre IP e alto desempenho DSL.
Figura 5.13. – Arquitetura do CS2000
152
A unidade reconfigurável [Compton 2002] [Martins 2002] do CS2000 é o
Processing Fabric (figura 5.14). Esta unidade é dividida em fatias, as unidades
básicas de reconfiguração. O CS2112 possui quatro fatias, cada uma pode ser
reconfigurada independentemente. Cada fatia consiste de três blocos, constituídos de
Unidades de Caminho de Dados, Multiplicadores, Memórias Locais e Unidades de
Controle.
Figura 5.14. – Fabric reconfigurável