Baixe Introdução Redes Chip e outras Manuais, Projetos, Pesquisas em PDF para Informática, somente na Docsity! Introdução às Redes-em-Chip Cesar Albenes Zeferino Universidade do Vale do Itajaí – CTTMar/CSED Rua Uruguai, 458, CP 360 – CEP 88330-202 – Itajaí, SC, Brazil zeferino@inf.univali.br http://www.inf.univali.br/~zeferino Resumo. Os futuros sistemas integrados exigirão arquiteturas de comunicação que ofereçam baixo consumo de energia, paralelismo em comunicação e sejam escaláveis e reutilizáveis. As arquiteturas de comunicação utilizadas nos sistemas integrados atuais não atenderão a todos esses requisitos simultaneamente, sendo que as redes-em-chip emergem como a melhor alternativa para atende-los. Este capítulo discute as questões associadas à comunicação em sistemas integrados e apresenta conceitos básicos sobre redes-em-chip. O texto é ilustrado com um estudo de caso e uma breve descrição a respeito do histórico de publicações sobre redes-em-chip na literatura. 1 Introdução O advento dos processos submicrônicos tem permitido um aumento do nível de integração de transistores em uma mesma pastilha de silício e viabilizará a sustentação da Lei de Moore por ainda muitos anos. Esse avanço na tecnologia tem possibilitado a integração de múltiplos componentes, como processadores, controladores e memória, em um único chip, resultando na integração de um sistema completo em uma mesma pastilha. Esses sistemas são denominados sistemas integrados ou SoCs (Systems-On-Chip). Para atender às pressões do mercado e amortizar os custos de projeto entre vários sistemas, é importante que os componentes integrados em um SoC sejam reutilizáveis. Dessa forma, as metodologias de projeto adotadas devem ser baseadas no reuso de componentes pré-projetados e pré-verificados. Esses componentes reutilizáveis são denominados núcleos (ou blocos de propriedade intelectual – IP Blocks) e podem ser desenvolvidos pela empresa responsável pelo projeto do sistema ou adquiridos de terceiros. Os núcleos de um sistema integrado são interconectados por meio de uma estrutura de canais denominada arquitetura de comunicação (também referenciada pelos termos arquitetura, estrutura ou rede de interconexão). Tipicamente, são utilizadas duas abordagens para a interconexão dos núcleos: canais ponto-a-ponto dedicados e canais multiponto compartilhados. A primeira alternativa é a que oferece o melhor desempenho, pois cada comunicação ocorre independentemente das demais por meio de canais exclusivos. Contudo, ela requer um projeto específico e, portanto, possui reusabilidade limitada. Já na arquitetura multiponto, conhecida por barramento, a mesma estrutura pode ser reutilizada em diferentes sistemas, reduzindo o tempo de projeto. Segundo estudos do ITRS (International Technology Roadmap for Semiconductors) [1], até o final desta década, estarão sendo disponibilizadas tecnologias de processo de 100 - 50 nm. Com tais tecnologias, será possível a integração de até quatro bilhões de transistores e dezenas a centenas de núcleos em uma mesma pastilha de silício [2], o que permitirá o desenvolvimento de novas aplicações nas áreas de multimídia, telecomunicações e eletrônica de consumo. Contudo, enquanto isso abre novas oportunidades de projeto, surgem também novas dificuldades com relação à especificação, mapeamento e avaliação das opções de projeto, assim como questões associadas às arquiteturas de comunicação. Do ponto de vista da comunicação, o problema reside no fato de que esses sistemas serão tão complexos que inviabilizarão o uso de interconexões dedicadas face às dificuldades envolvidas e à falta de reusabilidade dessa abordagem. Por outro lado, os requisitos de desempenho em comunicação, como largura de banda escalável e paralelismo em comunicação, dificilmente serão atendidos pelas arquiteturas baseadas no barramento. Isso decorre da natureza arquitetural do barramento que impõe uma série de problemas já identificados. Nos futuros sistemas integrados, os comprimentos dos fios de um barramento irão se manter proporcionais ao tamanho da pastilha (die size) e não irão diminuir com o aumento da freqüência de relógio devida à redução dos transistores. Por utilizar conexões do tipo multiponto, quanto maior for o número de núcleos conectados ao barramento, maior será a sua capacitância parasita. Assim, o atraso na movimentação de dados ao longo dos fios irá se tornar incrivelmente significativo e limitará o desempenho do sistema. Quanto à potência, o problema é que o barramento opera por difusão e cada sinal deve chegar a todos os pontos do barramento, exigindo uma grande quantidade de energia. Além desses, existem outros problemas, como largura de banda não escalável e arbitragem centralizada, que dificultarão em muito o uso de barramentos em SoCs complexos [3]. Logo, é evidente a necessidade de desenvolvimento de novos sistemas de comunicação que ataquem os problemas acima enumerados. Nesse contexto, a solução proposta pela comunidade científica está no uso de redes de interconexão chaveada, como aquelas encontradas em computadores paralelos. Essas redes têm como vantagens: a largura de banda escalável, o uso de conexões ponto-a-ponto curtas e o paralelismo na comunicação, entre outras. Embora tenham como desvantagens maiores custos e latência na comunicação, esses problemas serão atenuados pela grande disponibilidade de transistores e por soluções arquiteturais que permitem reduzir a latência da rede e seus efeitos no desempenho da aplicação. Essas redes chaveadas, quando aplicadas à comunicação intrachip, recebem múltiplas denominações na literatura: Micronetworks, On-Chip Networks (OCNs) e Networks-on-Chip (NoCs). Contudo, todas elas se referem à mesma base arquitetural (redes de interconexão chaveada para computadores paralelos), sendo que o termo Network-on-Chip (Rede-em-Chip, em português) tem tido a maior aceitação. 2.2 Starvation, Livelock e Deadlock Uma rede-em-chip transporta mensagens através dos seus canais físicos e dos buffers dos roteadores. Uma comunicação é realizada com sucesso quando a informação enviada é devidamente recebida pelo destinatário. Entretanto, existem três situações que podem impedir que uma mensagem chegue ao seu destinatário: starvation, livelock e deadlock. Quando o cabeçalho de uma mensagem chega a um roteador, ele é processado pelo mecanismo de roteamento que determina o canal de saída a ser utilizado e emite uma requisição ao árbitro responsável pela alocação do canal. Desde que podem haver múltiplas requisições simultâneas para um mesmo canal de saída, o árbitro aplica um critério de prioridades para selecionar uma dessas requisições. Dependendo de como esse critério é atualizado e em uma situação de alto tráfego por esse canal de saída, uma mensagem pode ser preterida indefinidamente e nunca ser selecionada para utilizar o canal requisitado, vindo a sofrer o que se chama de starvation. Por outro lado, se o algoritmo de roteamento permitir que qualquer canal de saída seja utilizado, então o starvation será minimizado. Contudo, isso pode permitir que, a cada roteador, o mecanismo de roteamento selecione um canal de saída que afaste a mensagem do seu destinatário e ela nunca chegue ao mesmo. Esse problema é conhecido por livelock. Contudo, o terceiro problema, denominado deadlock, é o mais grave de todos, pois, além de impedir que uma mensagem chegue ao seu destinatário, ele pode levar à paralização da rede. O deadlock ocorre quando há uma dependência cíclica na rede como a ilustrada na Fig. 3.a, na qual cada mensagem garantiu a alocação de um canal e requer o uso de outro canal já alocado a outra mensagem. Em uma rede como essa, podem ocorrer dois tipos de ciclos, ilustrados na Fig. 3.b, sendo que a solução de menor custo utilizada para evitar a ocorrência de deadlock consiste em proibir a realização de um subconjunto das curvas (ou voltas) que uma mensagem poderia realizar, evitando o surgimento de ciclos. Por exemplo, na Fig. 3.c, foram proibidas todas as curvas do eixo vertical (Y) para o eixo horizontal (X). Com isso, qualquer mensagem deve primeiro trafegar pelo eixo X para depois tomar o eixo Y, se necessário, não podendo mais ser encaminhada pelo eixo X. (a) (b) (c) Fig. 3. Dependência cíclica entre mensagens em uma rede-em-chip. Em geral, a garantia da ausência de starvation é dada pelo mecanismo de arbitragem utilizado, enquanto que a ausência de livelock e deadlock depende exclusivamente do algoritmo de roteamento adotado. 2.3 O Espaço de Projeto das Redes-em-Chip As redes-em-chip são fortemente baseadas nas redes de interconexão chaveada utilizadas em computadores paralelos. Contudo, elas utilizam um subconjunto do espaço de projeto dessas redes de interconexão. Isso se deve ao fato de que existem restrições e requisitos diferentes entre os dois níveis de implementação. Por exemplo, as topologias utilizadas nas redes de interconexão chaveada para computadores destinados ao processamento paralelo massivo possuem estruturas 3-D ou maiores. Já as redes-em-chip são construídas utilizando-se estruturas 2-D como a grelha e a árvore gorda, as quais são mais adequadas às tecnologias atuais de fabricação. Outro exemplo diz respeito à largura dos canais de dado. Nos roteadores da redes de interconexão, essa largura é limitada pelo número de pinos do encapsulamento, enquanto que, nas redes-em-chip, não existe tal limitação, pois os canais de comunicação são internos. Na Tabela. 1, são listadas as alternativas de mecanismos de comunicação mais utilizadas nas redes-em-chip atuais (por limitações de espaço, não são fornecidas maiores explicações a respeito das características de cada uma delas). Tabela 1. Alternativas de mecanismos de comunicação utilizadas nas redes-em-chip atuais Mecanismo Alternativas Controle de fluxo Handshake, baseado em créditos e baseado em canais virtuais Roteamento Determinístico, parcialmente adaptativo e adaptativo Arbitragem Distribuída ou centralizada Chaveamento Por circuito e por pacotes do tipo wormhole Memorização Na entrada (FIFO ou multi-via) e centralizada De fato, algumas das alternativas listadas acima foram extraídas de artigos que apresentam apenas propostas de redes-em-chip, sendo que, em sua maioria, as implementações já realizadas baseiam-se nas soluções de menor custo. 3 Estudo de Caso: a Rede SoCIN Para ilustrar os conceitos introduzidos na seção anterior, esta seção apresenta uma breve descrição da rede SoCIN (System-on-Chip Interconnection Network), a qual foi desenvolvida no escopo de uma tese de Doutorado do Programa de Pós-Graduação em Computação da Universidade Federal do Rio Grande do Sul (PPGC-UFRGS) [3]. A rede SoCIN foi especificada de modo a permitir a construção de redes-em-chip baseadas em topologias diretas ortogonais 2-D como a grelha (Fig. 4.a) e o toróide (e suas variações). Ela se baseia em um soft-core de um roteador parametrizável denominado RASoC (Router Architecture for SoC). Esse soft-core é descrito em VHDL e possui quatro parâmetros básicos: (i) número de portas de comunicação (até 5); largura da parte de dados do canal físico (n); profundidade dos buffers de memorização (p); e largura da informação utilizada para roteamento das mensagens (m), a qual determina a dimensão máxima da rede. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Roteador Enlace n val ack n+2 n+2 Enlace SoCIN bop eop data Cabeçalho Terminador . . . 10 00 01 b o p e o p n bits Carga útil n+2 bits (a) (b) (c) Fig. 4. Topologia básica em grelha, enlace SoCIN e formato do pacote Na Fig. 4.b, é ilustrado o enlace da rede SoCIN, o qual possui dois canais unidirecionais em oposição. Cada canal possui n sinais de dado, dois sinais de enquadramento da mensagem (bop e eop) e dois sinais de controle de fluxo (val e ack). O sinal bop (begin-of-packet) marca o início da mensagem, enquanto que o eop (end-of-packet) marca o seu final. O sinal val (valid) é utilizado pelo emissor para sinalizar a presença de um dado válido no canal, enquanto que o sinal ack (acknowledgement) é utilizado pelo receptor para confirmar o recebimento do dado. Os n sinais de dado e os sinais de enquadramento constituem o phit (n+2 bits). 3.1 Chaveamento e Roteamento A rede SoCIN utiliza chaveamento por pacotes do tipo wormhole. As mensagens são transferidas sob a forma de pacotes, os quais possuem uma palavra de cabeçalho e uma carga útil (corpo) de tamanho irrestrito (Fig. 4.c), sendo que o término de um pacote é determinado pela ativação do sinal de enquadramento eop na última palavra da carga util. Na terminologia do chaveamento wormhole, cada conjunto formado por uma ou mais palavras e sobre o qual é realizado o controle de fluxo é denominado flit (flow control unit). Na rede SoCIN cada flit equivale a uma palavra, ou seja, um phit. As características que diferem o chaveamento wormhole de outras técnicas de chaveamentos por pacotes é que um roteador pode encaminhar um pacote tão logo recebe o seu cabeçalho e o canal de saída necessário esteja livre e, em caso de indisponibilidade desse canal, o roteador não precisa absorver todos os flits do pacotes. De fato o buffer de entrada pode ser dimensionado de modo a armazenar alguns poucos flits, sendo que os demais flits são mantidos nos buffers dos roteadores anteriores no caminho do pacote. Quanto ao roteamento, a rede SoCIN utiliza o roteamento XY, uma técnica determinística baseada no ordenamento por dimensão. A comunicação entre um remetente e um destinatário posicionados em linhas e colunas diferentes deve primeiro percorrer os canais da direção X até atingir a coluna à qual o destinatário está posicionado, quando então deve percorrer os canais da direção Y. Essas técnicas permitem obter um roteador rápido e de baixo custo. Contudo, elas possuem desvantagens. No chaveamento wormhole, a contenção da rede aumenta com a redução da profundidade dos buffers. Já o roteamento XY subutiliza a largura de banda disponível na rede e não oferece tolerância à falhas. Em 2003, a difusão de publicações sobre redes-em-chip cresceu significativamente. A editora Kluwer publicou o livro intitulado “Networks on Chip” [13], editado por Axel Jantsch e Hannu Tenhunen, com capítulos escritos por diferentes autores. Foram também lançadas duas chamadas de trabalho para a publicação de edições especiais sobre o tema no Journal of Systems Architecures e no VLSI Journal. Diversas conferências internacionais tiveram artigos publicados tratando de questões associadas ao projeto, teste e aplicação de redes-em-chip (eg. DATE, VTS, ISCAS, VLSI, IDPS, SBCCI, entre outras). No contexto nacional, são conhecidas apenas duas redes-em-chip: a rede SoCIN, apresentada na seção anterior, e a rede HERMES, desenvolvida por pesquisadores da Pontifícia Universidade Católica do Rio Grande do Sul (PUC-RS) [14]. Contudo, observa-se um interesse crescente pelo tema junto aos pesquisadores brasileiros, pois o espaço de projeto é bastante amplo e oferece um grande número de oportunidades de pesquisa em vários contextos: arquitetura, teste, projeto para baixa potência, metodologias de projeto, avaliação de desempenho, projeto de SoCs baseados em NoCs, entre outros. Além das NoCs citadas acima, existem várias outras descritas na literatura (eg. Proteo, CLICHÉ, SoCBUS), sendo que, na Tabela 2, são resumidas as características de algumas das que são descritas com maior detalhamento. Contudo, nem todas características usadas no resumo são encontradas nos artigos disponíveis. Esses casos são indicados pelo texto “– × –”. Tabela 2. Quadro resumo com características de algumas redes-em-chip Rede SoCIN SPIN HERMES Octagon CLICHÉ Topologia Grelha 2-D Árvore-gorda Grelha 2-D Anel cordal Grelha 2-D Chaveamento Wormhole Wormhole Wormhole Circuito ou Pacotes Wormhole Roteamento Determinístico Adaptativo Parcialmente adaptativo Determinístico Determinístico Arbitragem Distribuída Distribuída Centralizada Centralizada Distribuída Memorização Entrada Entrada e centralizada Entrada – × – Entrada Controle de fluxo Handshake Baseado em créditos Handshake – × – – × – Referências principais [3][5] [7][8] [14] [15] [16] OBS: A rede aSOC não foi incluída pois, devido ao fato de utilizar escalonamento em tempo de compilação, ela não pode ser descrita claramente usando a sistemática acima. 5 Redes-em-Chip na Internet Esta seção apresenta apenas uma lista de links para alguns dos principais projetos e sites com informações a respeito de redes-em-chip. − Projeto SoCIN http://inf.univali.br/~socin/ − Projeto SPIN http://www-asim.lip6.fr/~adrijean/ − Projeto aSoC http://vsp2.ecs.umass.edu/vspg/ASOC/ − Projeto NOCARC http://www.imit.kth.se/info/FOFU/NOC/ Para encontar artigos disponíveis na Internet, sugere-se a busca através de mecanismos como o Google aplicando-se as palavras chaves “Network-on-Chip”, “Networks-on-Chip”, “On-Chip Network” e “Micronetwork”. 6 Considerações Finais Este texto apresentou uma introdução às redes-em-chip visando fornecer alguns conceitos básicos a respeito do tema e contextualizar o leitor no cenário do desenvolvimento dessas redes. Diversos aspectos mais avançados não foram considerados devido às limitações de espaço e ao objetivo proposto de ser um texto introdutório. Deve-se destacar que existe uma literatura rica sobre o tema, sendo, em sua maioria, constituída por artigos publicados em conferências e jornais da IEEE, os quais podem ser obtidos pela Internet. Ao leitor que está iniciando seus estudos sobre esse tema, sugere-se, fortemente, que as primeiras leituras sejam feitas com base nos artigos [2], [8], [10] e [11]. Após, o leitor deve ficar livre para buscar as referências citadas nesses textos ou partir para referências mais atuais. Agradecimentos Os estudos que serviram de base a esse texto foram desenvolvidos no decorrer do doutoramento deste autor no PPGC-UFRGS, com bolsa de doutorado do Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq). O mesmo órgão fomentou a realização de estágio no Laboratoire d´Informatique Paris VI junto ao Projeto SPIN, sob a supervisão do Prof. Dr. Alain Greiner. Um agradecimento muito especial é dado ao Prof. Dr. Altamiro Amadeu Susin (PPGC-UFRGS), orientador da tese, o qual vislumbrou e sempre acreditou no uso de redes chaveadas para interconexão intrachip desde o início de nossos estudos, em 1998. Referências 1. ITRS : International Technology Roadmap for Semiconductors. Disponível por WWW em http://public.itrs.net/ (15 de junho de 2003) 2. Benini, L., De Micheli, G. : Networks on Chips: A New SoC Paradigm. IEEE Computer, v.35, n.1 (2002) 70–78 3. Zeferino, C. A. : Redes-em-Chip: Arquiteturas e Modelos para Avaliação de Área e Desempenho. (Tese de Doutorado) Porto Alegre : PPGC-UFRGS (2003) 4. Duato, J. et al. : Interconnection Networks: An Engineering Approach. Los Alamitos : IEEE Computer Society Press (1997) 515p. 5. Zeferino, C. A., Susin, A. A. : SoCIN: A Parametric and Scalable Network-on-Chip. In: Symposium on Integrated Circuits and Systems, 16, 2003, São Paulo. Los Alamitos : IEEE Computer Society Press (2003) 6. Tewksbury, S. K., Uppuluri, M., Hornak, L. A. : Interconnections/Micro-Networks for Integrated Microelectronics. In: IEEE Global Telecommunications Conference, Orlando, 1992. Proceedings... Los Alamitos, IEEE Computer Society Press (1992) 180–186 7. Guerrier, P., Greiner, A. : A Scalable Architecure for System-on-Chip Interconnections. In: Sophia-Antipolis Micro-Electronics Conference, 1999, France, Proceedings… Sophia Antipolis : [s.n.] (1999) 90–93 8. Guerrier, P., Greiner, A. : A Generic Architecture for On-Chip Packet-Switched Interconnections. In: Design Automation and Test in European Conference, 2000, Paris Proceedings... Los Alamitos, IEEE Computer Society Press (2000) 250-256 9. Liang, J. et al. : aSOC: A Scalable, Single-Chip Communication Architecture. In: International Conference on Parallel Architectures and Compilation Techniques, 2000, Philadelphia Proceedings... Los Alamitos : IEEE Computer Society (2000) 10. Hemani, A. et al. : Network on chip: An architecture for billion transistor era. In: Proceeding of the IEEE NorChip Conference (2000) 11. Dally, W. J., Towles, B. : Routing Packets, Not Wires: On-Chip Interconnection Networks. In: Design Automation Conference, 38, LasVegas, 2001. Proceedings... Los Alamitos : IEEE Computer Society Press (2002) 684-689 12. Lavagno, L. (ed.) : IEEE Micro. v. 22, n. 5 (2002) 13. Jantsch, A., Tenhunen, H. (eds.) : Networks on Chip. Dordrecht : Kluwer (2003) 14. Moraes, F. G. et al. : A Low Area Overhead Packet-switched Network on Chip: Architecture and Prototyping In: International Conference on Very Large Scale Integration, Darmstadt, 2003. Proceedings… [S.l, s.n.] (2003) 15. Karim, A. N. F., Nguyen, A., Dey, R. R. S. : An Interconnect Architecture for Networking Systems on Chips. IEEE Micro, v.22, n.5 (2002) 36-45 16. Kumar, S. et al. : A Network on Chip Architecture and Design Methodology. In: Int. Symposium on Very Large Integration Scale, Pittsburg, 2002. Proceedings... Los Alamitos: IEEE Computer Society (2002) 105-112