Definition of Integrated Operations

A adoção de sistemas multiprocessados, aliada ao uso eficiente dos recursos destes, permi- te o aumento de desempenho quando comparado ao emprego de sistemas monoprocessados [JER05a]. Computacionalmente, as vantagens decorrem da divisão de uma aplicação em unidades menores, chamadas tarefas, e a exploração do paralelismo de execução destas. A distribuição das tarefas pelos PEs que compõem uma plataforma multiprocessada viabiliza a exploração do parale- lismo. Sob o ponto de vista de comunicação, é natural que um conjunto de tarefas que define uma aplicação deva colaborar, implicando na necessidade de troca de informações entre tarefas. Desta forma, os ganhos que podem ser alcançados com a exploração do paralelismo em aplicações exi- gem a preocupação com aspectos de comunicação, tais como o modo pelo qual as tarefas colabo- ram entre si e a forma como são utilizados recursos de comunicação.

Diferentes aspectos influenciam na comunicação, indo desde características arquiteturais da infraestrutura de comunicação (e.g. topologia, algoritmo de roteamento) até as estratégias ado- tadas para a comunicação (e.g. uso de memória global, a definição do protocolo). Definidos tais aspectos, a ocorrência de congestionamentos é fator de degradação da comunicação e de conse- quente diminuição da eficiência do uso de sistemas multiprocessados. Desta forma, o congestio- namento na comunicação é um efeito que deve ser controlado.

No presente trabalho, propõem-se duas infraestruturas de comunicação e mecanismos pa- ra controle da diminuição da eficiência da comunicação. Neste Capítulo são revisados trabalhos relacionados ao tema, divididos em três temas: (i) propostas de infraestruturas de comunicação em chip, (ii) o conceito de congestionamento e (iii) propostas de mecanismos de adaptação de trá- fego em infraestruturas de comunicação em chip. Cabe ressaltar que, no que tange infraestruturas de comunicação, neste trabalho o foco está em redes em chip.

2.1 INFRAESTRUTURA DE COMUNICAÇÃO EM CHIP

transmissão de dados entre entidades comunicantes em um sistema, sendo representados pelo

hardware que o implementa e pelos serviços por ele disponibilizados, tal como envio e recepção

de pacotes. Diferentes infraestruturas de comunicação em chip podem ser empregadas para a in- terconexão de módulos em sistemas embarcados, tal como conexões dedicadas, barramentos e redes em chip (i.e. NoCs). Destas, NoCs são vistas como tendência devido a suas vantagens de es- calabilidade, diminuição/redução de fios globais, aumento da largura de banda de comunicação, suporte a baixa dissipação de potência entre outras [BEN02] [HO01]. No presente trabalho, NoCs são objeto central na pesquisa. Revisa-se agora algumas propostas de NoCs, divididas segundo a regularidade das topologias.

2.1.1 NOCS DE TOPOLOGIA REGULAR

Com a evolução das tecnologias submicrônicas e a constante busca pelo aumento de de- sempenho de dispositivos eletrônicos, a adoção de sistemas multiprocessados é tendência no pro- jeto de CIs. MPSoCs deverão conter cada vez mais PEs, e o custo de lidar com esta multiplicação pode levar à adoção de PEs uniformes segundo aspectos tais como dimensões e fator de forma no intuito de facilitar o projeto automatizado e o reuso de módulos e subsistemas. Também, é possí- vel que se adote a idéia de clusters de processamento ao invés de PEs de aplicação específica. Do ponto de vista da infraestrutura de comunicação, tende-se a adotar arquiteturas parametrizáveis, mas de topologia regular, o que facilita a replicação de PEs homogêneos em funcionalidade e di- mensões. Revisa-se a seguir alguns trabalhos que propõem infraestruturas de comunicação em chip parametrizáveis para o atendimento genérico de requisitos de comunicação.

Guerrier et al. [GUE00] propuseram a rede em chip SPIN. SPIN adota uma topologia árvore

gorda, onde cada núcleo IP que compõem a plataforma está localizado em um roteador folha da topologia, representados na Figura 2.1(a) como círculos escuros. Os núcleos IP colaboram entre si através da troca de mensagens, que são fragmentadas em pacotes antes de serem inseridas na re- de. Sequências de palavras de 36 bits compõem um pacote. O cabeçalho do pacote fica na primeira palavra, onde um byte do cabeçalho identifica o endereço destino, e os demais bits são usados pa- ra informações de roteamento e controle. A carga útil dos pacotes pode ser de tamanho variável. Cada pacote é finalizado por um terminador que contém informações utilizáveis na detecção de erros de transmissão.

Karim et al. [KAR01] propuseram a rede Octagon. Conforme ilustrado na Figura 2.1(b), oito

roteadores interconectados por doze canais de comunicação definem a topologia base desta NoC. Os roteadores são organizados em um anel cordal, com um canal para cada lado e um canal de ca- da roteador para o roteador localizado no ponto oposto do octógono virtual definido na topologia. Assim, cada roteador tem três conexões, uma com o roteador à sua esquerda, uma com roteador à sua direita e uma com o roteador oposto do octógono. Cada conexão entre dois roteadores inter- conectados diretamente é denominada hop. A distância entre dois roteadores quaisquer da rede é sempre no máximo dois hops dentro de um anel cordal. A rede Octagon é escalável. Se um dos ro- teadores é utilizado como ponte, mais octógonos podem ser agrupadas, conforme ilustra a Figura 2.2. Note-se que neste caso os roteadores que conectam dois octógonos são distintos dos demais, sendo denominados de pontes. A rede Octagon foi originalmente proposta para servir à escalabili- dade na construção de processadores de rede (em inglês, network processors) maciçamente para- lelos.

(a) Árvore Gorda (SPIN) (b) Anel Cordal (Octagon) (c) Malha 2D (Cliché, SOCIN, Hermes) Figura 2.1 – Exemplos de topologias regulares e de NoCs que empregam estas.

Kumar et al. [KUM02] propuseram a rede em chip CLICHÉ, na qual foi adotada uma topolo-

gia em malha 2D, conforme ilustra a Figura 2.1(c). Cada roteador é conectado a um PE e o número de roteadores é igual ao número de PEs. Dependendo da posição do roteador na topologia, o nú- mero de roteadores vizinhos imediatos pode variar entre 2 e 4. Os Autores mostram que sob tráfe- go moderado, roteadores com tamanho de buffer igual a 8 é suficiente para reduzir a probabilida- de de perda de pacotes na rede. Todavia, se a carga da rede é superior a metade da capacidade da mesma, então a perda de pacotes persiste mesmo quando se aumenta o tamanho das filas de ar- mazenamento.

Zeferino et al. [ZEF03] propuseram a rede SoCIN, especificando-a de forma a permitir a a-

doção tanto da topologia malha 2D quanto toróide 2D. A SoCIN tem como elemento de roteamen- to um módulo denominado RASoC. Este roteador, descrito em VHDL, permite parametrizações em

quatro dimensões, quais sejam: (i) o número de portas de comunicação (limitado a 5), (ii) a largura do canal de comunicação, (iii) profundidade das filas de armazenamento e (iv) o número de bits utilizados no roteamento de pacotes (visando a escalabilidade da rede). O roteamento dos pacotes é definido pelo algoritmo determinístico XY.

Figura 2.2 – Exemplo da infraestrutura Octagon de dimensões superiores a topologia base.

Moraes et al. [MOR04] propuseram a rede Hermes. Assim como a SoCIN, a rede Hermes

permite a parametrização do número de portas dos roteadores, da largura dos canais e da profun- didade das filas de armazenamento. Em sua primeira versão, a rede Hermes deu suporte somente à topologia malha 2D e ao algoritmo de roteamento XY determinístico. Com a evolução dos traba- lhos em torno desta infraestrutura de comunicação, incluiu-se uma série de novas características, incluindo o suporte a topologia toro 2D, a adoção de algoritmos de roteamento adaptativos (e.g.

West first, North last, negative first), a possibilidade de uso de canais virtuais, e a opção por con-

trole de fluxo baseado em crédito (em inglês, credit based) ou handshake.