ads:
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE CIÊNCIAS EXATAS E DA TERRA
DEPARTAMENTO DE INFORMÁTICA E MATEMÁTICA APLICADA
PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E INFORMAÇÃO
MESTRADO EM SISTEMAS E COMPUTAÇÃO
E
E
S
S
T
T
U
U
D
D
O
O
D
D
A
A
V
V
I
I
A
A
B
B
I
I
L
L
I
I
D
D
A
A
D
D
E
E
D
D
O
O
D
D
E
E
S
S
E
E
N
N
V
V
O
O
L
L
V
V
I
I
M
M
E
E
N
N
T
T
O
O
D
D
E
E
S
S
I
I
S
S
T
T
E
E
M
M
A
A
S
S
I
I
N
N
T
T
E
E
G
G
R
R
A
A
D
D
O
O
S
S
B
B
A
A
S
S
E
E
A
A
D
D
O
O
S
S
E
E
M
M
R
R
E
E
D
D
E
E
S
S
E
E
M
M
C
C
H
H
I
I
P
P
S
S
E
E
M
M
P
P
R
R
O
O
C
C
E
E
S
S
S
S
A
A
D
D
O
O
R
R
E
E
S
S
:
:
S
S
I
I
S
S
T
T
E
E
M
M
A
A
I
I
P
P
N
N
O
O
S
S
Y
Y
S
S
Sílvio Roberto Fernandes de Araújo
Abril, 2008
Natal/RN
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
SÍLVIO ROBERTO FERNANDES DE ARAÚJO
E
E
S
S
T
T
U
U
D
D
O
O
D
D
A
A
V
V
I
I
A
A
B
B
I
I
L
L
I
I
D
D
A
A
D
D
E
E
D
D
O
O
D
D
E
E
S
S
E
E
N
N
V
V
O
O
L
L
V
V
I
I
M
M
E
E
N
N
T
T
O
O
D
D
E
E
S
S
I
I
S
S
T
T
E
E
M
M
A
A
S
S
I
I
N
N
T
T
E
E
G
G
R
R
A
A
D
D
O
O
S
S
B
B
A
A
S
S
E
E
A
A
D
D
O
O
S
S
E
E
M
M
R
R
E
E
D
D
E
E
S
S
E
E
M
M
C
C
H
H
I
I
P
P
S
S
E
E
M
M
P
P
R
R
O
O
C
C
E
E
S
S
S
S
A
A
D
D
O
O
R
R
E
E
S
S
:
:
S
S
I
I
S
S
T
T
E
E
M
M
A
A
I
I
P
P
N
N
O
O
S
S
Y
Y
S
S
Dissertação submetida ao Programa de Pós-
Graduação em Sistemas e Computação do
Departamento de Informática e Matemática
Aplicada da Universidade Federal do Rio Grande
do Norte como parte dos requisitos para obtenção
do título de Mestre em Sistemas e Computação
(MSc.).
Orientador: Prof. Ivan Saraiva Silva
Abril, 2008
Natal/RN
ads:
SÍLVIO ROBERTO FERNANDES DE ARAÚJO
E
E
S
S
T
T
U
U
D
D
O
O
D
D
A
A
V
V
I
I
A
A
B
B
I
I
L
L
I
I
D
D
A
A
D
D
E
E
D
D
O
O
D
D
E
E
S
S
E
E
N
N
V
V
O
O
L
L
V
V
I
I
M
M
E
E
N
N
T
T
O
O
D
D
E
E
S
S
I
I
S
S
T
T
E
E
M
M
A
A
S
S
I
I
N
N
T
T
E
E
G
G
R
R
A
A
D
D
O
O
S
S
B
B
A
A
S
S
E
E
A
A
D
D
O
O
S
S
E
E
M
M
R
R
E
E
D
D
E
E
S
S
E
E
M
M
C
C
H
H
I
I
P
P
S
S
E
E
M
M
P
P
R
R
O
O
C
C
E
E
S
S
S
S
A
A
D
D
O
O
R
R
E
E
S
S
:
:
S
S
I
I
S
S
T
T
E
E
M
M
A
A
I
I
P
P
N
N
O
O
S
S
Y
Y
S
S
Dissertação submetida ao Programa de Pós-Graduação em Sistemas e Computação do
Departamento de Informática e Matemática Aplicada da Universidade Federal do Rio Grande
do Norte como parte dos requisitos para obtenção do título de Mestre em Sistemas e
Computação (MSc.).
Aprovado em
BANCA EXAMINADORA
_________________________________________
Prof. Dr. Ivan Saraiva Silva
_________________________________________
Prof. Dr. Sérgio Bampi
_________________________________________
Prof. Dr. Fernando Rangel de Sousa
_________________________________________
Prof. Dr. Eduardo Bráulio Wanderlei Netto
Dedico este trabalho, aos meus pais
de quem herdei a coragem de
transformar as adversidades em
motivações para construção do
sucesso.
Agradecimentos
Parece muito clichê agradecer a Deus antes de tudo, mas vendo o resultado
desse trabalho, conseguido em tempo hábil, sob todas as circunstâncias que estive durante o
mestrado, chego à conclusão que a ciência só é tão exata por que de fato “Deus não joga
dados”. E graças a Ele tive o empenho necessário para consegui-lo.
Também não poderia deixar de agradecer à minha família, meus pais e irmãos,
pela colaboração, incentivo e compreensão, que são sem dúvidas os grandes propulsores na
minha escalada na carreira acadêmica.
Agradeço aos meus amigos que sempre estiveram do meu lado mesmo quando
estive “isolado na caverna, tentando descobrir o fogo”. E mesmo assim sempre pude contar
com eles nas alegrias ou lamentações.
Ao meu grande mestre, “Seu Saraiva”, que já deixou de ser apenas o orientador
desde o quarto período da graduação, e se tornou meu amigo, grande incentivador e exemplo
de professor pesquisador. Ivan foi peremptório para realização desse trabalho, não só pela
genial idéia inicial do trabalho, mas por ser estimulante durante toda minha pesquisa,
sobretudo nos momentos de incerteza. Além de também ser um espelho para minha formação
como professor.
Aos colegas do LASIC que sempre colaboraram construtivamente para o
sucesso desse trabalho, sobretudo a Bruno Cruz e Miklécio Costa que “colocou a mão na
massa” comigo para obtenção dos resultados.
E finalmente, aos meus alunos, que foram pra mim “um laboratório” do que é
ser um professor pesquisador, e me permitiram concluir, antecipadamente, que estou no
caminho certo.
“O único lugar onde o sucesso vem
antes do trabalho é no dicionário.”
Albert Einstein
ARAÚJO, Sílvio Roberto Fernandes. ESTUDO DA VIABILIDADE DO
DESENVOLVIMENTO DE SISTEMAS INTEGRADOS BASEADOS EM REDES EM
CHIP SEM PROCESSADORES: SISTEMA IPNOSYS. Dissertação submetida ao Programa
de Pós-Graduação em Sistemas e Computação do Departamento de Informática e Matemática
Aplicada da Universidade Federal do Rio Grande do Norte como parte dos requisitos para
obtenção do título de Mestre em Sistemas e Computação, Natal, 2008.
Resumo
O aumento na capacidade de integração de transistores permitiu o
desenvolvimento de sistemas completos, com inúmeros componentes, dentro de um único
chip, são os chamados SoCs (System-on-Chip). No entanto, o subsistema de interconexão
utilizado pode limitar a escalabilidade dos SoCs, como os barramentos, ou ser uma solução ad
hoc, como a hierarquia de barramentos. Desse modo, a solução ideal para interconexão no
SoCs são as redes em chip ou NoCs (Network-on-Chip). As NoCs permitem múltiplas
conexão ponto-a-ponto entre os componente e podem ser reusadas em projetos diversos.
Entretanto, o uso de NoCs pode representar o aumento na complexidade do projeto do
sistema, da área em chip e/ou potência dissipada. Dessa forma, é necessário ampliar o
horizonte de utilização dos sistemas ou quebrar o paradigma do seu desenvolvimento.
Assim, é proposto um sistema baseado em uma NoC, onde as aplicações são
descritas em forma de pacotes e executadas de roteador em roteador durante o percurso entre
origem e destino dos pacotes, sem a necessidade do uso de processadores convencionais. Para
permitir a execução de aplicações, independente do número de instruções e das dimensões da
rede, foi desenvolvido o algoritmo spiral complement, que permite re-rotear pacotes até que
todas as instruções contidas nele sejam executadas.
Portanto, o objetivo desse trabalho foi estudar a viabilidade do
desenvolvimento de tal sistema, denominado sistema IPNoSys. Nesse estudo, foi
desenvolvida em SystemC, com precisão de ciclo, uma ferramenta para simulação do sistema,
a qual permite executar aplicações implementadas na linguagem de descrição de pacotes,
também desenvolvida para esse fim. Através da ferramenta podem ser obtidos diversos
resultados que permitem avaliar o funcionamento e desempenho do sistema. A metodologia
empregada para descrição das aplicações corresponde, a priori, em obter o grafo de fluxo de
dados da aplicação em alto nível, e desse grafo descrevê-la em um ou mais pacotes.
Utilizando essa metodologia, foram realizados três estudos de casos: contador,
DCT-2D e adição de ponto flutuante. O contador foi usado para avaliar a capacidade do
sistema em tratar situações de deadlock e executar aplicações em paralelo. A DCT-2D foi
utilizada para realizar comparações com a plataforma STORM. E, finalmente, a adição de
ponto flutuante teve como objetivo ser usada como rotina de tratamento de uma instrução não
implementada em hardware.
Os resultados de simulação apontam favoravelmente com relação à viabilidade
do desenvolvimento do sistema IPNoSys. Mostrando que é possível executar aplicações em
forma de pacotes, inclusive paralelamente, sem interrupções provocadas por eventuais
deadlocks, e ainda indicam maior eficiência do sistema IPNoSys a respeito do tempo de
execução comparada a plataforma STORM.
Palavras-chave: sistema em chip (SoC), redes em chip (NoC), algoritmo spiral complement,
sistema IPNoSys.
ARAÚJO, Sílvio Roberto Fernandes. THE STUDY OF VIABILITY OF DEVELOPMENT
OF NO PROCESSOR INTEGRATED SYSTEM BASED ON NETWORK-ON-CHIP:
IPNOSYS SYSTEM. Dissertation submitted to Postgraduate Program in Systems and
Computing from Informatics and Applied Mathematics Department of Federal University of
Rio Grande do Norte like part of requisites to obtain the master’s degree, Natal, 2008.
Abstract
The increase of capacity to integrate transistors permitted to develop
completed systems, with several components, in single chip, they are called SoC (System-on-
Chip). However, the interconnection subsystem cans influence the scalability of SoCs, like
buses, or can be an ad hoc solution, like bus hierarchy. Thus, the ideal interconnection
subsystem to SoCs is the Network-on-Chip (NoC). The NoCs permit to use simultaneous
point-to-point channels between components and they can be reused in other projects.
However, the NoCs can raise the complexity of project, the area in chip and the dissipated
power. Thus, it is necessary or to modify the way how to use them or to change the
development paradigm.
Thus, a system based on NoC is proposed, where the applications are
described through packages and performed in each router between source and destination,
without traditional processors. To perform applications, independent of number of
instructions and of the NoC dimensions, it was developed the spiral complement algorithm,
which finds other destination until all instructions has been performed.
Therefore, the objective is to study the viability of development that system,
denominated IPNoSys system. In this study, it was developed a tool in SystemC, using
accurate cycle, to simulate the system that performs applications, which was implemented in a
package description language, also developed to this study. Through the simulation tool,
several result were obtained that could be used to evaluate the system performance. The
methodology used to describe the application corresponds to transform the high level
application in data-flow graph that become one or more packages.
This methodology was used in three applications: a counter, DCT-2D and float
add. The counter was used to evaluate a deadlock solution and to perform parallel
application. The DCT was used to compare to STORM platform. Finally, the float add aimed
to evaluate the efficiency of the software routine to perform a unimplemented hardware
instruction.
The results from simulation confirm the viability of development of IPNoSys
system. They showed that is possible to perform application described in packages,
sequentially or parallelly, without interruptions caused by deadlock, and also showed that the
execution time of IPNoSys is more efficient than the STORM platform.
Keywords: system-on-chip (SoC), network-on-chip (NoC), spiral complement algorithm,
IPNoSys system.
Lista de Figuras
Figura 1 - Arquitetura de uma rede em chip ............................................................................... 5
Figura 2 - Topologias diretas de NoC ........................................................................................ 7
Figura 3 - Topologias indiretas de NoC ..................................................................................... 7
Figura 4 - Comunicação usando canais virtuais ......................................................................... 8
Figura 5 - Paralelismo dos sistemas: (a) SISD; (b) SIMD; (c) MIMD; (d) MISD ................... 11
Figura 6 - Sistemas paralelos: (a) Multiprocessadores; (b) Multicomputadores ...................... 11
Figura 7 - Execução da expressão (a+b)/(b-c) em uma queue machine ................................... 14
Figura 8 - IPNoSys 4x4 ............................................................................................................ 17
Figura 9 - Pacote: (a) antes da execução de INST1; (b) após execução de INST1 .................. 18
Figura 10 - Expressão (y+x)*(x-z): (a) Grafo de fluxo de dados; (b) Pacote IPNoSys ........... 19
Figura 11 - Execução da expressão (x+y)*(x-z) no sistema IPNoSys ..................................... 21
Figura 12 - Roteamento XY ..................................................................................................... 22
Figura 13 - Comunicação dos nodos de uma NoC 4x4 usando o padrão complement ............ 23
Figura 14 - Spiral complement: (a) 1ª. espiral; (b) 2ª. espiral; (c) 3ª. espiral; (d) 4ª. espiral ... 24
Figura 15 - Formato do pacote do IPNoSys ............................................................................. 27
Figura 16 - Arquitetura da UPR ............................................................................................... 31
Figura 17 - Fluxograma do funcionamento da UPR ................................................................ 31
Figura 18 - Situação de deadlock ............................................................................................. 34
Figura 19 - Metodologia empregada no ambiente de simulação .............................................. 36
Figura 20 - Concentração de instruções em cada UPR nas execuções seqüenciais ................. 40
Figura 21 - Concentração de instruções em cada UPR nas execuções paralelas ..................... 41
Figura 22 - Tempo de execução para as aplicações simuladas ................................................. 42
Figura 23 - Tempo médio de transmissão das palavras na execução seqüencial do contador . 43
Figura 24 - Tempo médio de transmissão das palavras na execução paralela do contador ..... 43
Figura 25 - Utilização média dos canais na execução seqüencial ............................................ 45
Figura 26 - Utilização média dos canais na execução paralela ................................................ 45
Figura 27 - Taxa efetiva de transmissão seqüencial ................................................................. 47
Figura 28 - Taxa efetiva de transmissão paralela ..................................................................... 47
Figura 29 - Relação entre os pacotes na aplicação da DCT-2D ............................................... 50
Figura 30 - Memória requerida no IPNoSys com e sem laço de repetição e na STORM ........ 54
Figura 31 - Memória requerida no IPNoSys com laço de repetição e na STORM .................. 55
Figura 32 - Comparação do tempo de execução entre STORM e IPNoSys ............................. 56
Figura 33 - Representação do valor 2,5 no padrão IEEE 754 .................................................. 56
Figura 34 - Fluxograma do algoritmo da adição de ponto flutuante ........................................ 57
Lista de Tabelas
Tabela 1 - Resultados de simulação da DCT-2D ..................................................................... 52
Tabela 2 - Resultados de simulação STORM e IPNoSys ......................................................... 53
Tabela 3 - Resultados de simulação da adição de ponto flutuante ........................................... 58
Lista de Quadros
Quadro 1 - Algoritmo spiral complement................................................................................. 24
Quadro 2 - Pares origem/destino do roteamento spiral complement para uma grelha 4x4 ...... 26
Quadro 3 - Sintaxe da linguagem de descrição de pacotes....................................................... 37
Sumário
Introdução ................................................................................................................................. 1
1.1 Objetivos ........................................................................................................................... 3
1.1.1 Gerais ......................................................................................................................... 3
1.1.2 Específicos ................................................................................................................. 3
1.2 Motivações ....................................................................................................................... 3
Embasamento Teórico .............................................................................................................. 5
2.1 Redes em Chip .................................................................................................................. 5
2.2 Sistemas Multiprocessados em Chip .............................................................................. 10
2.3 Computadores Baseados em Fila .................................................................................... 13
Sistema IPNoSys ..................................................................................................................... 16
3.1. Algoritmo de Roteamento ............................................................................................. 21
3.2. Formato do Pacote ......................................................................................................... 26
3.3. Núcleo de Acesso a Memória (NAM) ........................................................................... 28
3.4. Unidade de Processamento e Roteamento (UPR) ......................................................... 30
3.4.1 Tratamento de deadlock........................................................................................... 33
Metodologia ............................................................................................................................. 36
Resultados ............................................................................................................................... 39
5.1 Estudo de Caso 1: Contador ........................................................................................... 39
5.2 Estudo de Caso 2: DCT-2D ............................................................................................ 47
5.3 Estudo de Caso 3: adição de ponto flutuante .................................................................. 56
Considerações Finais .............................................................................................................. 60
Referências .............................................................................................................................. 63
1
Capítulo 1
Introdução
Existe uma grande exigência do mercado quanto à rapidez no projeto e
desenvolvimento de um produto em tempo hábil para lucratividade máxima. Esta exigência é
explicada pela curva de faturamento (MADEIRA, 2004), que demonstra a lucratividade de
um produto com relação ao tempo de seu lançamento, até se tornar obsoleto. Para satisfazer
esta exigência, a indústria de hardware, já há algum tempo, utiliza a idéia de modularização e
reuso de componentes, como uma forma de acelerar o projeto e a fabricação de seus produtos.
Nos dias atuais, já é um fato a integração de vários componentes de hardware
em um único chip. Os sistemas dessa natureza são chamado de SoCs (System-on-Chip)
(WAWRZYNIAK, 1999). Como nos SoCs todos os componentes do sistema estão dentro do
mesmo chip, a distância física entre os componentes deixou de ser um problema. Desse modo,
os mecanismos de interconexão e comunicação entre os componentes podem ser mais
complexos e eficientes (REGO, 2006).
Nos SoCs, assim como em sistemas de processamento paralelo, o mecanismo
de interconexão e comunicação, ou o subsistema de comunicação, é tão relevante quanto o
próprio sistema formado pelos componentes. O subsistema de comunicação influencia no
mecanismo de comunicação entre os componentes e, por conseqüência, o desempenho do
sistema como um todo. Os barramentos ainda são bastante utilizados, apesar de ser uma
solução antiga e constantemente identificada como o elemento central do chamado “Gargalo
de Von Neumann”, (BACKUS, 1978). Além disto, já são bem conhecidas as diversas
limitações do uso de barramentos como subsistema de comunicação, em particular a baixa
escalabilidade (TANENBAUM, 2006). Para minimizar o problema da baixa escalabilidade, as
hierarquias de barramentos foram utilizadas com algum êxito, entretanto, na era dos SoC,
onde os sistemas podem conter de dezenas a centenas de núcleos independentes
(EDENFELD, 2004), esta solução ainda não apresenta a escalabilidade desejada. Outra
desvantagem da hierarquia de barramentos é a impossibilidade de reuso, uma hierarquia de
barramento é sempre uma solução ad hoc para um sistema. Logo, a solução tida como ideal
para os subsistemas de comunicação dos SoCs são as redes em chip ou NoCs (Network-on-
Chip) (BENINI, 2002).
2
As NoCs são baseadas nos modelos de rede de computadores, com a diferença
de estarem dentro do chip e, conseqüentemente, estarem restritas às características próprias
desse ambiente. Assim, na literatura, as NoC têm sido uma das soluções mais utilizadas para
sistemas multiprocessados em chip único ou MP-SoC (Multiprocessor SoC).
Além do subsistema de interconexão, também têm surgido propostas de
arquiteturas que utilizam outros paradigmas de processamento, como os computadores
baseados em fila (PREISS, 1985), (CANEDO, 2007). Processadores que utilizam esse
paradigma podem ser usados como eficientes máquinas superescalares (SCHMIT, 2002) ou
como uma boa alternativa para sistemas embarcados (CANEDO, 2007).
A dissertação apresentada nesse texto investiga as vantagens das redes em chip
como subsistema de interconexão para o desenvolvimento de sistemas multiprocessados, bem
como os conceitos dos processadores baseados em fila. Propõe-se um estudo sobre a
viabilidade do desenvolvimento de um sistema integrado baseado na estrutura física das redes
em chip, com suas múltiplas conexões ponto-a-ponto e no paradigma de processamento
semelhante ao paradigma utilizado pelos processadores baseados em fila. Para obtenção de
resultados práticos, também é proposto o desenvolvimento de uma ferramenta de simulação
do sistema utilizando a linguagem SystemC (OSCI, 2005) com precisão de ciclos. Como
inovação o sistema proposto dispensa a utilização de processadores, colocando quase que todo
o processamento necessário nos roteadores da NoC.
O texto está organizado de forma que as próximas seções desse capítulo
apresentam os objetivos e as motivações para o tema tratado nesta dissertação. O capítulo 2
faz uma revisão da literatura sobre as características, benefícios e desvantagens das NoCs,
MP-SoCs e computadores baseados em fila. O capítulo 3 apresenta a proposta do sistema
integrado baseado em NoC sem processadores, além de detalhar os conceitos envolvidos e a
arquitetura do sistema. No capítulo 4 é apresentada a metodologia utilizada no
desenvolvimento da ferramenta de simulação do sistema, bem como o modo de
desenvolvimento de aplicações para o sistema. Os resultados obtidos através das simulações
são apresentados no capítulo 5, enquanto que no capítulo 6 são apresentas as conclusões e
trabalhos futuros. E em seguida, são apresentadas as referências e os anexos.
3
1.1 Objetivos
1.1.1 Gerais
• Estudar a viabilidade do desenvolvimento de um sistema integrado
baseado em redes em chip sem processadores convencionais.
• Realizar a validação funcional desse sistema através de simulações.
1.1.2 Específicos
• Modificar os roteadores de uma NoC implementada e validada
(SOARES, 2004) para o desenvolvimento do sistema.
• Desenvolver a forma de representar aplicações para o sistema proposto.
• Desenvolver núcleos que substituam os processadores e injetem as
aplicações no sistema proposto.
• Desenvolver um algoritmo que permita o roteamento dos pacotes na
NoC de forma a atender as restrições do novo sistema.
1.2 Motivações
Projetos de sistemas integrados devem atender requisitos de desempenho, no
que diz respeito ao tempo de resposta e à freqüência de operação; área, relacionada a espaço
ocupado do chip por cada parte do sistema, sem comprometimento da funcionalidade e
desempenho; e baixo consumo de energia. Projetos eficientes, no entanto, geralmente tentam
equilibrar esses requisitos ou priorizam um ou outro, de acordo com a aplicação ou classe de
aplicações.
No caso de projetos de MP-SoCs, principalmente aqueles baseados em redes
em chip (NoCs), que ainda não se tornaram corriqueiros em produtos disponíveis no mercado,
a otimização de qualquer um destes requisitos, ainda é uma questão aberta. No que diz
respeito ao projeto das redes em chip, em particular, a funcionalidade está relativamente
consolidada. Entretanto, área e potência dissipada, além de alguns aspectos funcionais, tais
como, qualidade de serviço (QoS – Quality of Service) e roteamento adaptativo, necessitam
ainda de algum desenvolvimento. Com relação ao projeto das unidades de processamento ou
núcleos, discutem-se aspectos relacionados à complexidade ou granularidade, reconfiguração
4
e heterogeneidade. Programabilidade de MP-SoCs, modelos de computação e hierarquia de
memória também são assuntos que merecem muita atenção e esforço de pesquisa e
desenvolvimento.
Alguns resultados nesta linha de pesquisa foram previamente obtidos pelo
grupo de pesquisa, ao qual o autor desse texto faz parte, principalmente em temas
relacionados à: reconfiguração (PEREIRA, 2007), (PEREIRA, 2008a); Redes em chip
(SOARES, 2004); Plataformas MP-SoC (GIRÃO, 2007); e aplicações (GIRÃO, 2005),
(CARVALHO, 2006), (PEREIRA, 2008b).
Entretanto, nos sistema em chip atuais baseados em NoC, a comunicação entre
os núcleos é realizada através de pacotes, os quais são roteados independente do seu
conteúdo. Em geral esse conteúdo é formado por dados e instruções trocados entre
processadores e memória. No trajeto dos pacotes, da origem ao destino, certo número de
roteadores “interessa-se” apenas pelo cabeçalho do pacote, dando vazão a todo o restante de
seu conteúdo sem que nenhum processamento útil, do ponto de vista da execução da
aplicação, seja executado.
E ainda questiona-se o uso de NoCs como subsistema de interconexão. Tais
questionamentos são baseados no argumento de que as NoCs são responsáveis pelo aumento
da área em chip e da potência dissipada. Contudo, quando se toma como referência a
prototipagem em FPGA (Field Programmable Gate Arrays) do processador NIOS II/f
(ALTERA) e do roteador ParIS da NoC SoCINfp (ZEFERINO, 2004), tem-se que a área em
FPGA do processador é superior em mais de dez vezes a área do roteador (NIOS II/f = 2446
elementos lógicos; ParIS = 239 elementos lógicos; prototipados no dispositivo
EP2C35F672C6 da família Altera Cyclone II). Em conseqüência da quantidade de elementos
lógicos, pode-se inferir que a potência dissipada pelo processador também é superior a do
roteador. Assim, também há mais espaço para redução de área e potência dissipada no sistema
quando se investe em simplificação, sem perda de desempenho, dos elementos de
processamento.
Neste texto propõe-se verificar a viabilidade de desenvolver um modelo de
sistema integrado baseado em redes em chip onde os roteadores da NoC realizam a maior
parte do processamento da aplicação. Esse sistema se beneficia do tráfego de dados e
instruções entre os roteadores no trajeto dos pacotes. Com isto é possível reduzir
sensivelmente a complexidade dos núcleos ou unidades de processamento, reduzindo, área
ocupada pelo sistema e potência dissipada.
5
Capítulo 2
Embasamento Teórico
Nesse capítulo são discutidos os principais conceitos relacionados ao sistema
proposto. Os conceitos correspondem às redes em chip, sistemas multiprocessados em chip e
computadores baseados em fila. Nessa revisão, são apresentadas as características de cada um
desses sistemas, as quais serviram de base ou apresentam alguma semelhança ao sistema
proposto. Não são apresentados trabalhos relacionados, visto que o trabalho proposto nesse
texto é um tema bastante inovador, não sendo do conhecimento do autor do texto nenhum
outro trabalho da mesma natureza.
2.1 Redes em Chip
Como definido em (ZEFERINO, 2003), uma rede em chip ou NoC (Network-
on-Chip), é formada por um conjunto de roteadores e canais ponto-a-ponto que interconectam
os núcleos (do inglês Cores) de um sistema integrado. A arquitetura de comunicação em uma
NoC é baseada em canais bidirecionais (enlaces) chaveados que interligam os núcleos. A
Figura 1 ilustra uma rede em chip que interliga quatro núcleos através dos enlaces entre os
roteadores. Esses enlaces permitem comunicações simultâneas entre diferentes núcleos ou
entre os mesmo núcleos nos dois sentidos da comunicação.
Figura 1 - Arquitetura de uma rede em chip
6
Em uma NoC o modelo de comunicação é geralmente baseado na troca de
mensagens entre os núcleos do sistema. Essas mensagens são encapsuladas junto com
informações adicionais (como o cabeçalho) que são utilizadas pelos roteadores para
encaminhá-las da origem até o destino. O conjunto: mensagem (também chamada de carga
útil), cabeçalho, e eventualmente um finalizador da mensagem, é comumente chamado de
pacote.
Um pacote é normalmente formado por um conjunto de palavras de
determinada largura, onde uma ou mais palavras iniciais formam o cabeçalho e as palavras
seguintes, a mensagem propriamente dita. O cabeçalho da mensagem contém informações que
permitem a um roteador encaminhar o pacote para o próximo roteador a caminho do destino,
e este encaminha a um outro, e assim segue até o roteador apto a entregar o pacote para o
núcleo destino. No cabeçalho também pode haver outras informações, como comprimento do
pacote e informações específicas para o núcleo que receberá a mensagem contida no pacote.
Existem diversos modelos de NoC que se diferenciam nas seguintes
características: topologia, roteamento, chaveamento, controle de fluxo, arbitragem e
armazenamento.
A topologia de uma NoC está relacionada aos canais ponto-a-ponto entre os
roteadores, isto é, como os roteadores estão ligados entre si. As topologias podem ser
classificadas em diretas e indiretas (CARARA, 2004). A topologia direta é aquela onde cada
roteador está ligado a um núcleo do sistema. Nas topologias indiretas isso não acontece com
todos os roteadores, alguns são usados como pontes entre roteadores ligados a núcleos. Dentre
as topologias diretas estão: Grelha 2D; Torus 2D; Cubo 3D; Cubo 4D ou Hipercubo; e
Totalmente Conectada, que são representadas na Figura 2. Nessa figura cada círculo
representa um nodo do sistema, ou seja, um par formado por um roteador e um núcleo.
Exemplos de topologias indiretas são crossbar e rede multiestágio Ômega, apresentadas na
Figura 3.
7
Figura 2 - Topologias diretas de NoC
Figura 3 - Topologias indiretas de NoC
O modo como um pacote é encaminhado da origem até o destino, ou seja, o
caminho, ou rota, que o pacote percorre para alcançar o destino é determinado pelo
roteamento. Um roteador escolhe, segundo um algoritmo de roteamento, por qual de seus
canais de saída, interligados a outros roteadores, um pacote será encaminhado. Os algoritmos
de roteamento podem ser classificados de acordo com número de destinos, decisão de
roteamento, adaptabilidade e minimalidade (MELLO, 2005b). Além disso, os algoritmos de
roteamento devem prever e/ou evitar situações de deadlock, livelock e starvation.
Deadlock pode ser definido como uma dependência cíclica dos recursos entre
nodos, de forma que nenhum deles possa obter progresso algum, independente da seqüência
de eventos que ocorra. Livelock refere-se a pacotes circulando na rede sem fazer nenhum
8
progresso em direção ao seu destino. Starvation ocorre quando um canal de saída está sempre
ocupado e, portanto, nunca é alocado para outro pacote de uma fila de requisição do canal
(MELLO, 2005b).
Inúmeros algoritmos de roteamento já foram propostos para evitar essas
situações (BERMAN, 1992), (FELPERIN, 1991), (GLASS, 1992), (LI, 2006). Uma forma
muito comum de evitá-las, principalmente em topologias Grelha-2D, é usar algoritmos de
roteamento sem nenhuma adaptatividade, ou seja, completamente determinísticos. Os
algoritmos de roteamento mais simples são determinísticos e, portanto, definem um único
caminho entre origem e destino, como o algoritmo XY. Há também, os algoritmos
parcialmente adaptativos, como West-First, North-Last e Negative-First, que não permitem
que os pacotes sejam roteados por qualquer caminho curto (SCHWIEBERT, 1993). Enquanto
que os algoritmos completamente adaptativos, como (GLASS, 1992) e (LI, 2006), são
definidos em função do tráfego da rede (DUATO, 2002) ou com o objetivo de encontrar
caminhos mais curtos. Os algoritmos adaptativos são mais propícios ao surgimento dos
problemas de deadlock e livelock, e em geral as soluções estão associadas ao uso de canais
virtuais (MELLO, 2005b). Canais virtuais são canais lógicos que compartilham o mesmo
canal físico (canal ponto-a-ponto) em modo de multiplexação no tempo (SARBAZI-AZAD,
2000). A Figura 4 ilustra o processo de transmissão de dois pacotes entre dois roteadores
utilizando canais virtuais. Nesse processo, o canal físico é alocado de forma alternada
(multiplexação no tempo) para a transmissão das palavras de cada pacote. No roteador
receptor o processo inverso (demultiplexação) permite recebê-los mantendo sua integridade.
Figura 4 - Comunicação usando canais virtuais
O roteamento tem a função de escolher a rota por onde um pacote é
encaminhado até seu destino. No entanto, o modo como à transmissão entre os roteadores é
feita diz respeito ao chaveamento. Os principais mecanismos de chaveamento são: store-and-
forward, virtual-cut-through e wormhole (RIJPKEMA, 2001). No chaveamento store-and-
forward cada pacote que chega a um roteador é inteiramente armazenado antes de ser
encaminhado para o próximo roteador, escolhido pelo algoritmo de roteamento. O virtual-cut-
9
through é um aperfeiçoamento do anterior, visto que nesse mecanismo o pacote só é
armazenado quando o roteador seguinte estiver ocupado. Finalmente, o wormhole particiona o
pacote em pequenas unidades chamadas flits (FLow control unIT) e as transmite como em um
pipeline. No wormhole os flits são transmitidos tão rapidamente quanto possível de um
roteador para outro, ou seja, assim que o roteador seguinte está apto a recebê-lo. O primeiro
flit contém o cabeçalho que serve de guia para o roteamento de todos os flits seguintes do
mesmo pacote.
Para um pacote ser encaminhado de um roteador para outro, cada roteador
fonte deve cuidar para que a transmissão se faça a uma taxa aceitável pelo roteador receptor.
Esse mecanismo é conhecido como controle de fluxo. O controle de fluxo é um protocolo de
sincronização para transmissão e recepção de informação (DUATO, 2002). Sua função é
gerenciar a utilização dos buffers e canais de comunicação durante a transmissão de um
pacote. Os tipos de controle de fluxo mais utilizados, segundo (DALLY, 2003), são: baseado
em crédito, on/off e ack/nack. No mecanismo baseado em crédito, antes de fazer a transmissão
o roteador consulta o espaço disponível no buffer do roteador que receberá o pacote e o
transmite caso haja espaço suficiente. No controle de fluxo do tipo on/off cada roteador
habilita o sinal on quando a ocupação do buffer estiver abaixo de certo limite e habilita o sinal
off quando a ocupação do buffer ultrapassar o limite superior. Assim, antes da transmissão do
pacote o roteador verifica os sinais on e off dos buffers do roteador que receberá o pacote. No
controle de fluxo Ack/Nack (também chamado de Handshake) o roteador transmite o pacote
sem consultar o espaço disponível do receptor. Se houver espaço disponível o receptor envia
um sinal de acknowledge (ack), caso contrário envia um acknowledge negado (nack).
O controle de fluxo estabelece o sincronismo entre o emissor e o receptor de
um pacote. No entanto, se dois ou mais pacotes são roteados para um mesmo canal ou porta
de saída, é preciso controlar o acesso ao canal ou porta de saída do roteador. O mecanismo
que controla as disputas por uma porta de saída é chamado de arbitragem. A arbitragem pode
ser centralizada ou distribuída. A primeira é realizada por um módulo central do roteador que
controla todas as portas de saída. Na arbitragem distribuída, cada porta de saída possui um
árbitro próprio para resolver as disputas. Cada árbitro utiliza um algoritmo que determina a
prioridade de envio dos buffers que disputam o canal de saída, como o algoritmo round robin.
Segundo o chaveamento usado ou devido à possibilidade de haver disputa pelo
acesso a um canal ou porta de saída de um roteador, na transmissão de um pacote entre
roteadores, muitas vezes é necessário armazená-lo. O armazenamento é o mecanismo que
10
realiza essa tarefa, e pode ser feita na entrada ou na saída do roteador. A estratégia de
armazenamento mais comum e simples é o uso de um simples buffer FIFO (First in First out).
No entanto existem estratégias mais complexas como SAFC (Statically Allocated Fully
Connected), SAMQ (Statically Allocated Multi-Queue) e DAMQ (Dinamically Allocated
Multi-Queue).
Visto as várias características e as inúmeras propostas para cada uma delas, as
NoCs têm se tornado um dos mais promissores subsistemas de interconexão dos sistemas
integrados, sobretudo nos sistemas multiprocessadores dentro de um único chip. As principais
vantagens das NoCs com relação a barramentos (CALAZANS, 2007) são:
• Largura de banda escalável
• Arquitetura reutilizável
• Arbitragem distribuída
• Conexões curtas e ponto-a-ponto
• Paralelismo na comunicação
• Comunicação assíncrona
• Canais de comunicação em forma de pipeline
E as principais desvantagens das NoCs com relação a barramentos
(CALAZANS, 2007):
• Latência para atravessar um roteador
• Contenção na rede pode aumentar a latência
• Custo em área
• Requer uso de adaptadores de protocolo (wrappers)
• Mecanismos de hardware para garantir a coerência de cache não são
simples
2.2 Sistemas Multiprocessados em Chip
Os sistemas de processamento são classificados, com relação ao paralelismo,
com base nos fluxos de instruções e nos fluxos de dados. Essa classificação foi definida por
(FLYNN, 1972), e corresponde a: SISD (Single Instruction Single Data), SIMD (Single
Instruction Multiple Data), MIMD (Multiple Instruction Multiple Data) e MISD (Multiple
Instruction Single Data). A Figura 5 ilustra os tipos de sistemas, com relação ao paralelismo,
classificado por Flynn.
11
Figura 5 - Paralelismo dos sistemas: (a) SISD; (b) SIMD; (c) MIMD; (d) MISD
Os sistemas verdadeiramente paralelos, MIMD, possuem diversas unidades de
processamento e diferenciam-se pelo compartilhamento da memória. Quando utilizam
memória distribuída são chamados de multicomputadores e quando utilizam memória
compartilhada são chamados de multiprocessadores (TANENBAUM, 1995), a Figura 6
exemplifica os dois casos.
Figura 6 - Sistemas paralelos: (a) Multiprocessadores; (b) Multicomputadores
O advento dos SoCs (System-on-Chip) também impulsiona o desenvolvimento
de sistemas de processamento paralelo, especialmente os multiprocessadores. Nesse contexto
12
esses sistemas são denominados Sistemas Multiprocessadores em Chip ou MP-SoC
(Multiprocessor SoC).
Aposta-se nos MP-SoCs como a futura geração de computadores (WOLF,
2004), para os quais já existem modelos comerciais (INTEL, 2002), (ARTIERI, 2006),
(HELMIG) e inúmeros trabalhos acadêmicos. No entanto, algumas das propostas utilizam
barramento como mecanismo de comunicação, sobretudo os modelos comerciais, mesmo já
conhecidas as restrições de escalabilidade. Uma alternativa cada vez mais empregada nos
trabalhos recentes (REGO, 2006), (MELLO, 2005a), (GIRÃO, 2007) é a utilização de NoC
como sistema de comunicação.
Na NoC trafegam os pacotes de requisições e respostas entre os núcleos do
MP-SoC, a maioria tendo origem nos processadores e destino na memória do sistema. Nesse
ambiente a NoC se comporta como um dispositivo passivo, atuando apenas como meio de
ligação entre os dois pontos da comunicação, os únicos interessados no conteúdo dos pacotes.
É bem clara a superioridade das NoCs em relação aos barramentos no que diz respeito a
escalabilidade. Entretanto, a utilização de NoC em sistemas integrados, particularmente nos
MP-SoCs acarreta, aumento na complexidade do projeto do sistema, aumento de área do
sistema com conseqüente aumento de potência dissipada, necessidade de distribuição de
dados e instruções entre eventuais blocos de memória presentes no sistema e aumento na
complexidade de desenvolvimento de aplicações que executam nesses sistemas.
Nesta perspectiva a utilização de redes em chip (NoCs) poderia estar sendo
fortemente questionada. Entretanto, o aumento do poder de processamento, proporcionado
pela maior capacidade de integração de transistores na mesma pastilha de silício (chip), leva
ao desenvolvimento de aplicações cada vez mais exigentes no que diz respeito à capacidade
de processamento. Esta realidade faz com que se projete para o final desta década a existência
de sistemas com até quatro bilhões de transistores (EDENFELD, 2004), constituídos de
centenas de núcleos processadores. Com esta complexidade tem-se, de um lado, a
impossibilidade de utilização de barramentos ou hierarquia de barramentos e, de outro lado, a
impossibilidade de utilizar soluções ad hoc para o desenvolvimento de qualquer sistema
integrado sem que se coloque em risco a exeqüibilidade financeira e temporal do projeto.
Vemos então o surgimento do ápice dos problemas causados pelo chamado
“Gargalo de Von Neumann” onde o acesso aos dados, ou os cuidados com coerência e
consistência destes (GIRÃO, 2007), podem tornar inviável a utilização máxima da capacidade
de integração de sistemas em chip. Para, mais uma vez, contornarmos este problema devemos
13
ampliar o horizonte de utilização dos sistemas como os conhecemos ou quebrar o paradigma
de desenvolvimento destes.
Nos sistemas em chip baseados em NoC, circulam dados e instruções sob a
forma de pacotes. No seu trajeto da origem ao destino os roteadores interessam-se apenas pelo
cabeçalho do pacote sem que nenhum processamento útil, do ponto de vista da execução da
aplicação, seja realizado. Esse processo de transmissão funciona como um pipeline, que
poderia ser aproveitado para a execução das instruções e dados da aplicação. No entanto, não
é do conhecimento do autor deste texto nenhum trabalho que proponha algo semelhante na
literatura. Na literatura ainda se encontram os Computadores Baseados em Fila que, com
relação à dissertação aqui apresentada, propõe um modelo de computação semelhante,
entretanto não utiliza NoCs.
2.3 Computadores Baseados em Fila
Os computadores baseados em filas são brevemente descritos neste capítulo de
revisão bibliográfica devido a semelhança entre o modelo de computação usado pelo sistema
proposto e o modelo de computação usado por tais processadores. Computadores Baseados
em Fila (Queue-based computers) ou (Queue machines) são fundamentados no uso de
referência implícita para uma fila de operandos na execução das instruções, de modo análogo
às stack machines (PREISS, 1985). Algumas pesquisas têm observado que o fato de
operandos e instruções serem ordenados, nas queue machines, é possível construir eficientes
máquinas superescalares ou máquinas de fluxos de dados (data flow machine) (SCHMIT,
2002).
Segundo (CANEDO, 2007) computadores baseado em fila são uma nova
alternativa para arquiteturas embarcadas devido seus compactos conjuntos de instrução, que
promovem códigos densos, alta capacidade de paralelismo em nível de instrução e hardware
simples, que reduz a área em chip e o consumo de energia. Vários modelos de computação em
fila têm sido propostos na literatura (ABDERAZEK, 2006a), (ABDERAZEK, 2006b),
(SCHMIT, 2002), (SOWA, 2005), em grande parte pelo grupo de pesquisa da University of
Electro-Communications of Tokyo.
Nas queue machines os operandos da instrução corrente são encontrados no
início de uma fila de operandos e os resultados de instruções são colocados no final dessa fila.
Esse simples modelo de execução é estendido através da associação de uma prioridade aos
resultados de cada instrução. O destino dos resultados é uma posição na fila de operandos
14
determinado por essa prioridade. Assim, o resultado pode ser inserido em qualquer lugar na
fila. E os operandos são removidos apenas no início da fila (SCHMIT, 2002). Problemas com
inserção de resultados no meio da fila de operandos podem ser contornados com o uso de
registradores de início e fim da fila (QH – queue head; QT – queue tail) que guarda os
endereços correntes de início e fim da fila.
Na Figura 7 é exemplificado o modelo de execução da expressão (a+b)/(b-c)
em uma queue machine, extraído de (CANEDO, 2007), que usa os registradores QH e QT
para indicar o início e o fim da fila respectivamente.
Figura 7 - Execução da expressão (a+b)/(b-c) em uma queue machine
É assumido que a fila está inicialmente vazia. A primeira instrução busca o
valor a e o coloca na fila de operandos, na posição indicada pelo registrador QT. Esse
registrador avança para a próxima posição vazia da fila. Em seguida, o mesmo processo
acontece para incluir os valores b e c na fila. Nesse momento o registrador de início de fila
(QH) armazena a posição do primeiro valor (a) e o registrador de fim de fila (QT) a próxima
posição vazia na fila, após o último valor carregado (c). A quarta instrução indica a adição
entre o primeiro valor da fila (QH com deslocamento 0) e o segundo valor da fila (QH com
15
deslocamento 1), ou seja, a adição dos valores a e b. O resultado dessa operação é inserido no
fim da fila (indicado pelo QT) e seguido pelo deslocamento do QT para a próxima posição na
fila. Nesse momento o registrador QH aponta para o próximo valor depois de b e o QT aponta
para a próxima posição vazia da fila, após o valor a+b. A quinta instrução é a subtração do
valor apontado por QH recuado em 1 (valor b) e o valor atual apontado por QH (valor c). O
resultado (b-c) é inserido no final da fila (após a+b) e os registradores QH e QT avançam
para suas próximas posições. Agora, a instrução atual indica a divisão entre os valores
apontados por QH com deslocamento 0 e QH com deslocamento 1, ou seja, os valores (a+b) e
(b-c). Esse resultado também é inserido no final da fila e posteriormente escrito na memória
através da última instrução.
O fluxo de execução nas queue machines pode ser representado através dos
grafos de fluxo de dados acíclicos dos programas (DFG - do inglês data-flow graph), como
apresentado na Figura 7(a) onde os nós correspondem às instruções e os arcos representam o
movimento dos operandos (PREISS, 1985). A partir desse modelo de computação já foram
propostas algumas arquiteturas baseadas em fila (ABDERAZEK, 2004), (ABDERAZEK,
2006a), inclusive com capacidade de processamento paralelo (ABDERAZEK, 2006b).
Como as queue machines fazem uso de fila para avaliação das expressões, o
conjunto de instruções não faz referências a registradores, assim estão sendo propostas
estratégias de alocação dinâmica de registradores (SMELYANSKIY, 2000), (CANEDO,
2007), técnicas para geração e otimização de código para esse paradigma e compiladores para
tais arquiteturas (SCHMIT, 2002), (CANEDO, 2006).
O modelo de computação utilizado nos computadores baseados em fila pode
ser muito bem utilizado no desenvolvimento de um modelo de computação para um sistema
integrado baseado em NoC onde os elementos roteadores executem todas, ou a maior parte
das operações, dispensando-se assim a utilização de processadores convencionais.
16
Capítulo 3
Sistema IPNoSys
Para o estudo da viabilidade do desenvolvimento do sistema IPNoSys
(Integrated Processing NoC System), levou-se em consideração as vantagens apresentadas
pelas redes em chip como subsistema de interconexão. As redes em chip (NoC) possibilitam
comunicação (transmissão) paralela de pacotes entre os núcleos através dos diversos canais
ponto-a-ponto. Além disto, permitem o armazenamento temporário de pacotes ou partes de
pacotes antes da transmissão, e a transmissão se dá como em um pipeline de roteador em
roteador até o destino. No roteador destino, antes de entregar a mensagem ao núcleo local, o
pacote é novamente roteado e só então a mensagem é entregue ao núcleo. Desta constatação
percebemos que o tráfego de pacotes entre origem e destino pode ser usado para transformar a
NoC em um subsistema com capacidade de processamento no ambiente sistema integrado.
Esta proposta é viável na medida em que:
• As transformações necessárias nos roteadores da NoC sejam compensadas por
simplificações nos processadores, únicos elementos, até o presente momento, que
“se interessavam” pelo conteúdo da carga útil dos pacotes.
• Seja possível manter um fluxo de pacotes sem deadlock, livelock e starvation
apesar das novas funcionalidades atribuídas aos roteadores.
• Seja possível representar uma aplicação através de certa quantidade de pacotes de
instruções e dados capazes de prover suporte a todos os recursos das linguagens de
alto nível atuais.
O sistema proposto é baseado na comunicação de uma rede com topologia em
Grelha 2D de dimensão quadrada, ou seja, o número de linhas igual ao de colunas; utiliza dois
canais virtuais; roteamento XY; chaveamento que combina VCT e wormhole, uma vez que é
necessário armazenar, em cada novo roteador do percurso, o início do pacote (que
corresponde ao cabeçalho, a primeira instrução e os respectivos operandos) para executar esta
instrução. Após a execução, o restante do pacote é apenas encaminhado para o próximo
roteador, sem a necessidade de armazenamento, assim como acontece no chaveamento
wormhole; controle de fluxo baseado em crédito; arbitragem distribuída; e armazenamento na
entrada. Entretanto, algumas dessas características sofreram alterações de acordo com as
17
particularidades do sistema. Nessa proposta os processadores são substituídos por Núcleos de
Acesso à Memória (NAM) e os roteadores tornam-se Unidades de Processamento e
Roteamento (UPR). Os pacotes deixam de ser apenas mensagens de requisições e respostas
para se tornarem uma estrutura contendo instruções e operandos a serem processadas durante
o percurso do pacote. A Figura 8 ilustra o sistema IPNoSys formado por uma rede 4x4.
Figura 8 - IPNoSys 4x4
Aproveitando o comportamento pipeline da transmissão, os pacotes passam a
funcionar como seqüências de instruções, onde a operação corrente é aquela que está no início
do pacote e os resultados podem ser inseridos em qualquer parte do pacote como operandos
de outras instruções, semelhante ao processamento das máquinas baseadas em fila. Nesse
modelo, cada UPR executa a primeira instrução e encaminha o restante do pacote para a
próxima UPR, desde que o canal de transmissão esteja disponível. Quando o canal de
transmissão está indisponível o restante do pacote não pode ser encaminhado à UPR seguinte,
desse modo a UPR com o cabeçalho do pacote deve executar também a próxima instrução
desse pacote. A Figura 9, ilustra em (a), um pacote antes da execução da primeira instrução
(INST1) e em (b), o pacote após a execução da primeira instrução (INST1) e após a inserção
do resultado dessa instrução (Dado a).
18
Figura 9 - Pacote: (a) antes da execução de INST1; (b) após execução de INST1
Na figura, após a execução da instrução INST1, o resultado é inserido na
sétima palavra do pacote e esse pacote é transmitido sem a instrução executada (INST1) e
seus respectivos operandos. Então o restante do pacote (Figura 9 (b)) deve ser encaminhado à
próxima UPR para que a instrução seguinte (INST2) seja executada do mesmo modo que
INST1.
Dessa forma, o pacote diminui à medida que se aproxima do destino. Essa é
uma das grandes contribuições desse sistema, visto que o volume de dados tende a diminuir à
medida que o pacote flui pela rede, o que diminui as chances de congestionamentos e aumenta
a capacidade da rede receber novos pacotes mais rapidamente.
A figura a seguir ilustra como uma simples aplicação, representada por
(y+x)*(x-z), é definida no sistema IPNoSys. A Figura 10(a) apresenta o grafo de fluxo de
dados da aplicação, onde os nós desse grafo representam as operações e os arcos representam
os operandos. A partir desse grafo é possível criar um pacote (Figura 10 (b)) para execução no
sistema IPNoSys, ilustrada na Figura 11. Nessa figura é mostrado o passo-a-passo da
execução das instruções do pacote, na ordem indicada no canto superior direito de cada passo,
juntamente com grafo de fluxo de dados destacando a instrução em execução. Primeiramente
os valores Y, X e Z são carregados da memória e incluídos no pacote como operandos da
adição (ADD) e subtração (SUB). Em seguida, os resultados dessas instruções são usados
como operandos para a multiplicação (MUL) que por sua vez, produz o resultado que deve ser
escrito na memória através da instrução STORE. A posição no pacote onde os resultados das
instruções são incluídos é indicada na própria instrução, destacada na Figura 11 na instrução
19
que está sendo executada. Perceba que todas as palavras do pacote na Figura 11 estão
numeradas, e, no entanto alguns números foram omitidos. Os números omitidos são referentes
aquelas palavras que serão incluídas com os resultados de instruções prévias. Os outros
campos do pacote serão apresentados em detalhes na Seção 3.2 desse capítulo.
Figura 10 - Expressão (y+x)*(x-z): (a) Grafo de fluxo de dados; (b) Pacote IPNoSys
20
6
7
1
2
3
4
5
8
21
Figura 11 - Execução da expressão (x+y)*(x-z) no sistema IPNoSys
As próximas seções apresentam o algoritmo de roteamento, o formato do
pacote, e as estruturas do NAM e da UPR.
3.1. Algoritmo de Roteamento
O número de instruções, e operandos, é variável em cada pacote. O tamanho do
pacote, as instruções e dados que ele possui, bem como as posições onde os dados calculados
devem ser inseridos, são definidos pelo grafo de fluxo de dados da aplicação, como
apresentado na Seção anterior. Em geral, cada UPR executa apenas uma instrução por vez, de
um pacote. Dessa forma, o destino de cada pacote deve ser suficientemente distante da origem
para que todas as instruções contidas no pacote possam ser executadas, considera-se a
distância entre destino e origem como o número de UPRs intermediárias entre origem e
destino. Entretanto, o mais provável (já verificado nas simulações atuais) é que a distância
entre origem e destino, de uma NoC com dimensões limitadas, não seja suficiente para a
execução de todas as instruções de um pacote que represente uma aplicação real, mesmo que
simples. Neste caso o pacote deve, ao chegar no destino, ser novamente roteado, isto é, um
novo destino deve ser definido, a fim de que a execução continue.
Nenhum algoritmo de roteamento atual está preparado para encontrar um novo
destino para processar as demais instruções contidas no pacote. Foi necessário, portanto, o
desenvolvimento de um novo algoritmo de roteamento dotado desta capacidade. O algoritmo
desenvolvido foi denominado spiral complement, e é capaz de rotear novamente um pacote,
tantas vezes quanto for necessário, até que seja garantida a execução de todas as instruções,
independentemente do número de instruções e das dimensões da rede (número de UPRs).
Esse algoritmo é inspirado no roteamento XY e no padrão de tráfego complement.
9
10
22
No roteamento XY, é considerado que cada nodo da Grelha 2D é endereçado
pelas coordenadas XY do plano cartesiano onde estão situados. Dessa forma o pacote é
encaminhado no sentido do eixo X até a coluna da coordenada Y do destino e em seguida
segue no sentido do eixo Y até a linha da coordenada X do destino, quando finalmente o
pacote é entregue ao seu receptor. Na Figura 12, o nodo 0,0 envia um pacote para o nodo 3,3.
Esse pacote é primeiramente transmitido horizontalmente até o roteador 0,3, que está
localizado na mesma coluna, ou coordenada Y, do destino. A partir desse roteador o pacote
segue verticalmente até a linha, ou coordenada X, do destino, quando o pacote é entregue ao
receptor, o nodo 3,3.
Figura 12 - Roteamento XY
O Complement é um padrão de tráfego, independente do algoritmo de
roteamento, usado para calcular os destinos dos pacotes em simulações, normalmente usadas
para avaliação de desempenho de NoCs. Nesse padrão o destino é calculado através da
inversão dos bits da origem (MELLO, 2005b), isto é, o complemento da origem. No padrão
complement o nodo origem que possui coordenadas no formato binário
0121
,,,, aaaa
nn
K
−−
tem como destino o nodo com coordenadas
0121
,,,, aaaa
nn
¬
¬
¬
¬
−−
K . Assim, os nodos de
uma NoC 4x4 usando o padrão complement se comunicam como mostrado na Figura 13.
23
Figura 13 - Comunicação dos nodos de uma NoC 4x4 usando o padrão complement
No algoritmo spiral complement, o destino inicial de um pacote é o
complemento da origem. Então, quando um pacote atinge seu destino e o número de
instruções contidas no pacote é maior que zero, um novo destino deve ser calculado, ou seja, é
feito um novo roteamento. Neste novo roteamento, a origem passa a ser o antigo destino, ou
seja, o nodo corrente que calcula o novo destino, e o novo destino é calculado levando-se em
consideração a necessidade de se obter a melhor distribuição de carga possível entre os canais
da NoC.
No sistema IPNoSys os pacotes são inicialmente injetados em um dos quatro
cantos da grelha. Esta restrição foi inicialmente imposta, devido às maiores distâncias entre
origem e destino em uma rede nessa topologia, serem os cantos opostos (por exemplo, os
nodos 0,0 e 3,3 em uma grelha 4x4), esse também é o motivo dos módulos de memória
estarem nos cantos da rede.
Com isso, para o cálculo de um novo destino, o algoritmo spiral complement
leva em conta duas informações (veja o Quadro 1): (i) o antigo destino do pacote (nó corrente
que calcula o novo destino); e (ii) a antiga origem (nó que enviou o pacote ao nó corrente). Ao
considerar o antigo destino o algoritmo verifica se este está em um dos quatro cantos da rede.
Se não estiver, o novo destino é calculado como sendo a antiga origem com o incremento ou
decremento da coordenada X ou coordenada Y em uma unidade. A operação de incremento
ou decremento de uma das coordenadas, geralmente, é alternada e a coordenada afetada
também alterna em cada novo cálculo. Se o antigo destino (nó que calcula o novo destino)
estiver em um dos cantos da rede o algoritmo considera ainda a antiga origem (nó que o
enviou o pacote). Se a antiga origem for um dos quatro cantos da rede o novo destino é
calculado em dois passos: no primeiro é calculado o complemento do nó corrente e no
24
segundo acontece o incremento ou decremento, de uma unidade, de umas das duas
coordenadas, X ou Y. Entretanto, se a antiga origem não for um dos quatro cantos da rede o
novo destino será calculado em um único passo, o complemento do nó corrente. A Figura 14
mostra o roteamento utilizando o algoritmo spiral complement para uma matriz de 4x4 UPRs,
para pacotes originados em cada um dos quatro cantos da rede.
A transmissão propriamente dita dos pacotes, entre origem e destino, é
realizada utilizando o roteamento XY.
Figura 14 - Spiral complement: (a) 1ª. espiral; (b) 2ª. espiral; (c) 3ª. espiral; (d) 4ª. espiral
y Se destino inicial
| Complemento do nó corrente
y Senão
| Se o nó corrente estiver em um dos 4 cantos
y Se o nó que enviou o pacote for o complemento do nó corrente
| Calcula o complemento do nó corrente
| Incremento/decremento de X ou Y do complemento (alternado)
y Senão
| Complemento do nó corrente
| Senão
y Endereço do nó que enviou o pacote com incremento/decremento de X ou
Y
(
alternado
)
Quadro 1 - Algoritmo spiral complement
25
Na Figura 14(a) o pacote é injetado inicialmente no canto superior esquerdo
(nodo 0,0), então o primeiro destino é calculado como sendo o complemento, ou seja, o canto
inferior direito (nodo 3,3). Nos demais cálculos dessa espiral, os novos destinos são
calculados alternando entre incremento da coordenada X e decremento da coordenada Y da
origem atual do pacote. Quando o pacote transmitido do nodo 0,0 atinge seu destino o canto
inferior direito (nodo 3,3), o segundo destino é calculado com os dois passos descritos
anteriormente: complemento da origem atual e o incremento de uma unidade da coordenada
X do complemento calculado. No exemplo o complemento é o nodo 0,0 que após o
incremento da coordenada X determinará o novo destino, o nodo 1,0. O pacote é transmitido
para o novo destino (nodo 1,0) com a nova origem (nodo 3,3). Em seguida tem-se que a nova
origem não está em um dos quatro cantos da rede. O próximo destino é então calculado
subtraindo-se uma unidade à coordenada Y da origem (nodo 3,3), resultando no nodo 3,2
como destino. Ao chegar ao nodo 3,3, que também não está em um dos quatro cantos da rede,
o processo se repete, e o próximo destino é calculado como sendo a coordenada do nodo
origem (nodo 1,0) com o incremento da coordenada X de uma unidade, resultando no nodo
2,0. E assim segue a execução do algoritmo spiral complement, alternando entre incremento
da coordenada X e decremento da coordenada Y da origem atual do pacote. O algoritmo
provoca o movimento do pacote como em uma espiral levando-o até o canto inferior
esquerdo.
Quando o pacote tem origem no canto inferior esquerdo (Figura 14(b)), após o
complemento, os destinos são calculados alternando-se apenas a coordenada afetada por
operação de incremento. Neste caso o algoritmo inicia com o incremento da coordenada Y e
no cálculo do próximo destino com o incremento da coordenada X da antiga origem,
realizando a segunda espiral, isto é, os novos destinos vão levando o pacote para o canto
inferior direito da rede. Para pacotes originados no canto inferior direito (Figura 14(c)), os
destinos são calculados alternando em decremento da coordenada X e incremento da
coordenada Y da antiga origem, realizando a terceira espiral. E, quando são originados no
canto superior direito (Figura 14(d)) a alternância acontece entre o decremento da
coordenada Y e o decremento da coordenada X da origem, realizando a quarta espiral. A
seguir a Quadro 2 demonstra todas origens e destinos das quatro espirais para a rede de
dimensões 4x4 da Figura 14.
26
1ª. Espiral 2ª. Espiral 3ª. Espiral 4ª. Espiral
Origem Destino Origem Destino Origem Destino Origem Destino
0,0 → 3,3 3,0 → 0,3 3,3 → 0,0 0,3 → 3,0
3,3 → 1,0 0,3 → 3,1 0,0 → 2,3 3,0 → 0,2
1,0 → 3,2 3,1 → 1,3 2,3 → 0,1 0,2 → 2,0
3,2 → 2,0 1,3 → 3,2 0,1 → 1,3 2,0 → 0,1
2,0 → 3,1 3,2 → 2,3 1,3 → 0,2 0,1 → 1,0
3,1 → 3,0 2,3 → 3,3 0,2 → 0,3 1,0 → 0,0
Quadro 2 - Pares origem/destino do roteamento spiral complement para uma grelha 4x4
Perceba que o destino final de cada espiral é igual à primeira origem da espiral
seguinte, e que o último destino (da quarta espiral) coincide com a origem da primeira espiral,
dessa forma, se o pacote percorre toda uma espiral, os próximos destinos a serem calculados
serão aqueles da espiral seguinte, como se o pacote tivesse sido injetado pelo nodo inicial
dessa nova espiral, fechando o ciclo e permitindo o roteamento recomeçar.
3.2. Formato do Pacote
O pacote utilizado na IPNoSys é uma modificação do pacote da NoC da
plataforma STORM (REGO, 2006). Essa modificação foi necessária devido ao algoritmo de
roteamento e aos diferentes tipos de informação contidas nas palavras do pacote para executar
aplicações. O pacote da IPNoSys é um conjunto variável de palavras de trinta e dois bits de
largura, onde as três primeiras palavras formam o cabeçalho, seguidas pelas palavras com
instruções e operandos, terminado por uma palavra que indica o fim do pacote. Além dos
trinta e dois bits de largura do pacote, são usados mais quadro bits sinalizadores que
informam o tipo de palavra transmitida: cabeçalho, instrução, operando ou fim de pacote. A
Figura 15 apresenta o formato do pacote junto aos bits de controle.
27
Figura 15 - Formato do pacote do IPNoSys
Em cada palavra apenas um dos quatro bits do controle pode estar ativo (nível
lógico um), todos os demais devem estar desativados (nível lógico zero). A seguir é feita a
descrição dos campos de cada palavra, com os respectivos tamanhos em bits.
• Cabeçalho – apenas o 1º. bit do controle pode estar ativo.
o Destino (8 bits): endereço da UPR final do roteamento atual.
o Origem (8 bits): endereço da UPR que iniciou o roteamento atual.
o Num_intruções (8 bits): número de instruções corrente contidas no pacote.
o Re-rotear (3 bits): indicam a forma de calcular o novo endereço de destino.
Prox (1 bit): próxima coordenada a ser alterada (‘0’ = X; ‘1’ = Y).
CX (1 bit): como alterar a coord. X (‘0’= incremento; ‘1’=
decremento).
CY (1 bit): como alterar a coord. Y (‘0’= incremento; ‘1’=
decremento).
o Flag (5 bits): usado para indicar o tipo do pacote (“00000” = as instruções do
pacote podem ser executadas em qualquer UPR (pacotes regulares); “00001” =
as instruções do pacote devem ser executadas apenas no nodo destino (pacotes
de controle)).
28
o Num_Pacote (32 bits): identificador único do pacote para uma dada aplicação.
o Apontador (32 bits): possui o número de palavras processadas ao longo do
percurso do pacote, indicando a próxima instrução a ser executada.
• Instrução – apenas o 3º. bit do controle pode estar ativo
o Instrução (8 bits): identificador da instrução a ser executada
o NO (2 bits): número de operandos necessário para executar a instrução (“00” =
nenhum operando; “01” = 1 operando; “10” = 2 operandos; “11” = vários
operandos, a quantidade deve ser definido no campo Resultado_2)
o Resultado_1 (11 bits): indica a quantidade de palavras a serem transmitidas
para a UPR seguinte, incluindo o cabeçalho, antes que seja necessário inserir o
resultado da instrução no pacote; em algumas instruções esse campo é usado
para indicar o endereço do nodo que deve executá-la.
o Resultado_2 (11 bits): quando o campo “NO” possui valor diferente de “11”
indica a quantidade de palavras a serem transmitidas para a UPR seguinte,
incluindo o cabeçalho, antes que seja necessário inserir o resultado da
instrução novamente; quando o campo “NO” possui valor “11” indica a
quantidade de operandos necessário para executar a instrução; possui valor
zero quando a instrução não retorna resultado ou quando o resultado retornado
não deve ser inserido em mais que uma posição do pacote
• Operando – apenas o 4º. bit do controle pode estar ativo
o Operando (32 bits): dado utilizado como operando da instrução
• Fim de pacote – apenas Só o 2º. bit do controle pode estar ativo
Fim (32 bits): terminador do pacote
3.3. Núcleo de Acesso a Memória (NAM)
Uma aplicação pode ser executadas no sistema IPNoSys através de um ou mais
pacotes no formato apresentado na seção anterior. Os pacotes são armazenados na memória e
injetados no sistema através dos Núcleos de Acesso a Memória (NAM). Estudos mais
aprofundados sobre a hierarquia de memória ainda devem ser feitos, por enquanto a
hierarquia de memória corresponde a uma memória distribuída nos quatro cantos da rede,
com o endereçamento global, como apresentado na Figura 8.
Os NAMs são responsáveis pela injeção dos pacotes no sistema IPNoSys, pela
criação de novos pacotes que estabelecem a comunicação ou realizam a sincronização entre
29
nodos específicos, e pela execução de instruções que lêem ou escrevem dados na memória,
quando estão localizados em um dos quatro cantos da rede. Os NAMs se comunicam com o
sistema, enviando e recebendo pacotes, através das portas locais das UPRs. Desse modo,
quando uma instrução específica do pacote corrente ordena a criação de um novo pacote ou
requer acesso a um dado na memória, acontece uma solicitação ao NAM para executá-la.
Apenas nestes casos os NAMs são usados, nos demais casos o processamento é
completamente realizado na UPR.
Quando uma instrução específica de NAM é destinada ao NAM corrente
(NAM associado a UPR que recebeu a primeira instrução do pacote corrente), a instrução é
executada, e o restante do pacote deve ser enviado para a próxima UPR. Caso a instrução não
seja destinada ao NAM corrente, este NAM cria um novo pacote, contendo a instrução a ser
executada e seus operandos, e injeta-o com destino ao NAM que executará a instrução. Esse
novo pacote tem o campo Flag do cabeçalho com valor “00001”, indicando ser um pacote de
controle, o qual deverá ser executado apenas no seu destino. E o restante do pacote é
encaminhado à UPR seguinte. Todos os pacotes de controle são transmitidos utilizando um
canal virtual exclusivo para esse tipo de pacote, de modo que congestionamentos e situações
deadlock iminente não interrompam a entrega desse pacote ao NAM destino, único com
permissão de executá-lo.
As instruções executadas no NAM correspondem à: leitura e escrita da
memória (Load e Store, respectivamente); ordem de execução (injeção na NoC) de um pacote
que está na memória (Exec ou SincExec); sinalização de sincronismo (Sinc); e envio de um
valor para ser inserido em um outro pacote (Send). A instrução Load utiliza apenas um
endereço de memória como operando, enquanto o Store utiliza um ou mais endereços e o
dado que será escrito na memória. Já as instruções Exec e SincExec necessitam do
identificador do pacote (número do pacote) que será injetado no sistema. A diferença entre as
duas instruções é que o SincExec é um Exec sincronizado, ou seja, além do pacote que será
injetado, a instrução também leva um ou mais identificadores de outros pacotes pelos quais
deve-se esperar um sinal de sincronismo. Assim, o SincExec ordena a injeção de um pacote
que está na memória apenas depois de receber todos os sinais de sincronização que espera.
Desse modo, a instrução Sinc é usada para sinalizar a um NAM que espera o sincronismo dos
pacotes para injetar o pacote indicado no SincExec. Juntamente com a instrução Sinc é
enviado o número do pacote ao qual ela pertence. Em alguns casos, operandos de instruções
de um pacote precisam ser atualizados com valores calculados em outros pacotes. Nesses
30
casos, o valor é enviado para o NAM, que injetará o pacote que necessita do resultado
atualizado, através da instrução Send. Essa instrução carrega consigo, além do valor enviado,
a informação de qual palavra de qual pacote esse valor deve ser inserido. Desse modo, o valor
recebido através do Send é inserido na palavra indicada durante a injeção desse pacote. Todas
essas instruções utilizam os campos Resultado_1 para indicar o endereço do NAM que
deverá executar a instrução e algumas delas utilizam Resultado_2 para indicar a quantidade
de operandos usados pela instrução, (vide o Anexo I).
Portanto, o NAM pode injetar no sistema pacotes que estão na memória, criar
pacotes de controle para enviar instruções a serem executadas em um NAM específico, fazer
sinalização de sincronismo ou enviar um valor para ser inserido em outros pacotes quando
estão sendo injetados. Mas em todos os casos, o NAM utiliza a porta local da UPR como
interface para injeção do pacote no sistema.
3.4. Unidade de Processamento e Roteamento (UPR)
As Unidades de Processamento e Roteamento (UPR) do sistema IPNoSys
foram inspiradas nos roteadores da NoC da plataforma STORM (REGO, 2006). Assim, cada
UPR possui cinco portas de entrada, chamadas norte, sul, leste, oeste e local, todas com
memorização do tipo FIFO, chamados de buffer; conta com um módulo de roteamento que
direciona os pacotes de cada buffer de entrada para uma saída, de acordo com o algoritmo de
roteamento; uma Unidade Lógica e Aritmética (ULA), onde é executada a maioria das
instruções da aplicação descrita em forma de pacotes; e, cada porta de saída, possui um árbitro
que controla as disputas pelos canais de saída, requisita e envia os dados necessários para a
ULA ou para o NAM executar uma instrução, e transmite o pacote e os resultados da
instrução pela porta de saída. A UPR difere de um roteador convencional de NoC pela
inclusão da ULA e por alterações realizadas nos árbitros e módulo de roteamento de modo
que estes possam lidar com as instruções, dados e resultados, além de criar novos destinos
para os pacotes, segundo o roteamento spiral complement, desenvolvido para o sistema
IPNoSys. A Figura 16 ilustra a arquitetura da UPR, com o detalhamento do módulo de
roteamento, com o chaveamento dos sinais de entrada/saída, os árbitros de cada porta e o
destaque para a ULA.
31
Figura 16 - Arquitetura da UPR
Quando um pacote chega a um dos buffers de entrada da UPR, o algoritmo
representado no fluxograma da Figura 17, determina seu funcionamento.
Figura 17 - Fluxograma do funcionamento da UPR
Assim, o cabeçalho do pacote é consultado antes de ser roteado. Se o campo
Flag do cabeçalho tem o valor igual a “00001”, o pacote é roteado como em uma NoC
tradicional usando o roteamento XY, sem alterar o destino nem executar as instruções da sua
carga útil, através do canal virtual exclusivo de pacotes de controle. As instruções contidas
neste tipo de pacote devem ser executadas apenas no destino. Esse tipo de pacote é usado
quando é necessário fazer comunicação ou sincronização entre dois nodos em particular.
32
Pacotes com Flag diferente de “00001” têm suas instruções executadas uma a uma, de UPR
em UPR e, quando atingem seus destinos, podem ser novamente roteados, caso existam mais
instruções a serem executadas.
Quando um pacote atinge seu destino, a UPR verifica a quantidade de
instruções contidas no pacote através do campo Num_Instruções do cabeçalho, que é
decrementado em um a cada instrução executada. Se ainda existe alguma instrução a ser
executada, o pacote deve ser novamente roteado. Nas UPRs localizadas em um dos quatro
cantos da rede, o novo destino será o complemento, caso a origem também não seja uma UPR
que se encontra nos cantos da rede (neste caso o cálculo do complemento levaria o pacote de
volta à antiga origem). Nos outros casos, o destino será o valor da antiga origem do pacote
com alguma modificação, de acordo com o algoritmo spiral complement (apresentado na
Seção 3.1). Isso é feito com o auxílio dos campos Origem, Prox¸ CX e CY. A modificação
do valor da origem se dá em apenas uma das coordenadas (X ou Y), indicada no campo Prox.
Caso seja alterada a coordenada X o campo CX indica se será feito um incremento ou
decremento dessa coordenada. Caso seja a coordenada Y, a modificação a ser realizada
(incremento ou decremento) será indicada pelo campo CY. Em seguida, o bit do campo Prox
é invertido para que no próximo cálculo de novo roteamento seja realizado na outra
coordenada. Assim, o valor de apenas uma das coordenadas da origem é modificada,
alternadamente, a cada novo roteamento, e esse valor passa a ser o novo destino do pacote. A
nova origem do pacote é o endereço da UPR que calculou o novo destino. Alterando ou
mantendo o destino, o pacote é roteado utilizando o algoritmo XY.
As portas de saída são controladas pelos árbitros, que utilizam o algoritmo
round-robin como política de acessibilidade. Assim como na unidade de roteamento, os
árbitros verificam se o pacote tem Flag igual a “00001”, em caso afirmativo o pacote deve ser
transmitido sem nenhuma alteração do seu conteúdo. Caso contrário, a instrução que está
atualmente no início do pacote é removida, juntamente com seus operandos, e a ULA ou
NAM é requisitado a executá-la. As instruções executadas na ULA são do tipo lógico ou
aritmético como nas ULAs dos processadores tradicionais. O atual conjunto de instruções do
sistema IPNoSys encontra-se no Anexo I. O resultado da operação vindo da ULA é
armazenado pelo árbitro juntamente com as informações sobre as posições do pacote onde
devem ser inseridos. Estas posições são indicadas nos campos Resultado_1 e Resultado_2 da
instrução. Além disso, o campo Apontador é atualizado, somando-se seu valor ao número de
palavras removidas na execução da instrução, isso permite indicar qual a próxima instrução
33
do pacote. Quando a instrução não for lógico ou aritmética, o árbitro solicita o NAM para
executá-la, removendo-a do pacote, juntamente com seus operandos e enviando para o NAM
quando a solicitação é atendida. Assim como a ULA, o NAM atende as requisições usando a
estratégia round-robin.
Quando inicia a transmissão do pacote de um dos buffers, o árbitro mantém um
canal exclusivo com a próxima UPR até que seja transmitida a última palavra do pacote desse
buffer. Durante a transmissão, um contador é incrementado a cada palavra transmitida.
Quando o contador torna-se igual a Resultado_1 ou Resultado_2 da instrução executada, o
árbitro interrompe a transmissão do buffer e transmite o resultado retornado pela ULA, em
seguida retoma a transmissão do buffer novamente. A cada novo pacote o contador é iniciado
com o valor do campo Apontador, permitindo assim uma contagem global das palavras do
pacote mesmo em UPRs diferentes. Além do Apontador, outro campo que auxilia a
contagem durante a transmissão de instruções é o campo NO, que indica o número de
operandos necessário para executar a instrução. Quando a instrução é seguida por todos os
seus operandos, o contador de palavras é simplesmente incrementado de um a cada palavra
transmitida. Contudo, se os operandos de uma instrução serão inseridos posteriormente,
através da execução de outras instruções, o contador de palavras é somado à diferença entre o
valor de NO e a quantidade de operandos da instrução presentes no pacote.
Enquanto um pacote de um dos buffers está sendo transmitido, os demais
buffers que solicitam o árbitro podem requisitar a ULA ou NAM até que sejam selecionados
pelo árbitro para realizar a transmissão. Dessa forma, os pacotes que disputam o canal de
saída terão suas instruções executadas mesmo que não possam ser transmitidos. Também nos
casos em que um buffer é selecionado para a transmissão, mas o espaço disponível no
receptor é insuficiente, a ULA ou o NAM são novamente requisitados até que a transmissão
possa ser realizada. Essa estratégia de continuar executando as instruções do pacote enquanto
este não pode ser transmitido, é uma medida preventiva contra uma possível situação de
deadlock.
3.4.1 Tratamento de deadlock
Como o sistema IPNoSys é baseado em uma rede em chip, o sistema deve
prever e/ou tratar os problemas decorrentes desse subsistema de comunicação. Um deles é a
ocorrência de deadlock provocado pela dependência cíclica entre pacotes, impossibilitando o
tráfego nos canais de transmissão. Como no sistema IPNoSys os pacotes possuem
34
comprimentos variados, e o algoritmo de roteamento utilizado, o spiral complement, permite
um mesmo pacote passar inúmeras vezes pelos mesmos canais, uma situação de deadlock
seria inevitável, dependendo do comprimento do pacote e da dimensão da rede.
Considere um pacote injetado pelo nodo 0,0, como mostra a Figura 18. Após
quinze operações de roteamento
1
, segundo o algoritmo spiral complement, o cabeçalho do
pacote chega ao nodo 3,2 pela porta norte dessa UPR, enquanto palavras do mesmo pacote
continuam a chegar e serem roteadas da porta leste para a saída oeste da mesma UPR. É
considerado um nodo o par UPR e o NAM correspondente, o qual executa qualquer instrução
do sistema IPNoSys.
Figura 18 - Situação de deadlock
Neste caso, o buffer da entrada norte está livre para receber o cabeçalho do
pacote. Entretanto, de acordo com o spiral complement, o pacote deveria ser novamente
roteado e transmitido, da porta norte para a saída oeste, chegando novamente ao nodo 3,1.
Como o canal de transmissão entre os nodos 3,2 e 3,1 está ocupado, transmitindo outra parte
do mesmo pacote, o cabeçalho do pacote ficará a espera da liberação desse canal, provocando
a ocupação total dos buffers de entrada em toda a rota do pacote. Esta situação caracteriza um
deadlock, pois o cabeçalho não libera espaço no buffer que ocupa, por estar esperando
liberação de espaço no buffer de entrada da porta leste do nodo 3,1, entretanto, para que isto
aconteça é necessário que, o cabeçalho libere espaço, e assim continua a espera mútua.
1
É considerada uma operação de roteamento a transmissão de um pacote entre duas UPRs adjacentes a caminho
do destino desse pacote.
35
Uma solução poderia ser incluir canais virtuais. O número de canais virtuais
seria igual ao número de vezes que um pacote pode passar pelo mesmo link. O maior número
de passagens do pacote no mesmo link acontece nos cantos da rede, como apresentado na
Seção 3.1 (Figura 14). No entanto, se o pacote fosse tão grande que percorresse as quatro
espirais do algoritmo spiral complement e voltasse ao nodo que está injetando, todos os canais
virtuais estariam ocupados e novamente aconteceria um deadlock.
Assim, outra solução foi adotada para resolver definitivamente esse problema.
Solução essa que será chamada de execução localizada por se tratar da execução de inúmeras
instruções em um mesmo nodo. Como apresentado, os árbitros de uma UPR são os
responsáveis pela solicitação da ULA ou do NAM, para execução de uma instrução, e pela
transmissão dos pacotes pela porta de saída. Desse modo, quando o cabeçalho de um pacote
não pode ser transmitido (devido ao canal estar ocupado ou por não haver espaço suficiente
no buffer destino), o árbitro solicita novamente a ULA ou o NAM para executar a próxima
instrução do pacote. Assim, a cada instrução executada o árbitro tenta transmitir o pacote, e
no caso de insucesso, volta a executar a próxima instrução do pacote. Vale destacar que a
execução acontece somente no nodo que está tentando transmitir o cabeçalho, uma vez que
apenas as instruções do início do pacote podem ser executadas, nos demais nodos o pacote só
pode ser transmitido.
A solução da execução localizada trata uma iminente situação o deadlock, mas
pode requerer buffers maiores nos árbitros para armazenar os resultados das instruções que
serão transmitidos no momento oportuno ou enviados novamente para ULA ou ao NAM.
Também pode ser utilizada uma solução híbrida com canais virtuais e a execução localizada,
entretanto é neste trabalho será avaliada a eficiência da execução localizada, visto que essa
estratégia deve solucionar o problema independente do uso de canais virtuais e o inverso não
é garantido.
36
Capítulo 4
Metodologia
O estudo da viabilidade da implementação do sistema IPNoSys, incluiu o
desenvolvimento de uma ferramenta para simulação e validação funcional, utilizando
SystemC (OSCI, 2005). SystemC é uma biblioteca C++ que permite desenvolver sistemas em
hardware em diversos níveis de abstração. Desse modo, a ferramenta foi desenvolvida em
nível de precisão de clock, para permitir maior acuracidade em relação ao modelo real. A
Figura 19 apresenta a metodologia empregada no ambiente de simulação da ferramenta.
Figura 19 - Metodologia empregada no ambiente de simulação
A metodologia utilizada para executar uma aplicação no sistema proposto
corresponde a transformar a aplicação, escrita em linguagem de alto nível, em um conjunto de
pacotes com as operações e dados da aplicação. Nesse processo é utilizado o grafo de fluxo de
dados da aplicação (LEVINE, 2003) ou DFG (data-flow graph) como linguagem
intermediária. A partir do grafo é possível determinar o paralelismo e a dependência de dados
da aplicação. Subgrafos sem dependência de dados indicam pacotes independentes que podem
37
ser paralelizados, enquanto que um conjunto de operações seqüenciais e dependentes forma
um único pacote ou pacotes executados seqüencialmente (veja o Anexo II).
Para geração dos pacotes, a partir do grafo, é utilizada uma linguagem de
descrição de pacotes. A linguagem descreve os campos do pacote apresentado na Seção 3.2,
incluindo as informações do cabeçalho, as instruções do sistema, e os operandos. O quadro a
seguir apresenta a sintaxe da linguagem através das macros que determinam os valores dos
campos dos pacotes.
As macros OP=, ARGUMENTS=, RESULT= e DATA= se repetem para
cada instrução. A descrição do pacote termina com a macro END. Em seguida um novo
pacote pode ser descrito, no mesmo arquivo, utilizando a mesma sintaxe, ou seja, começando
com PCKNUMBER= e finalizando com END.
Como ainda não existe um compilador para o sistema IPNoSys, as aplicações
são escritas manualmente, a partir do grafo da aplicação, na linguagem desenvolvida para
descrição dos pacotes.
BEGIN_MEMORY_DATA=
Região da memória onde os dados são lidos ou escritos
END_MEMORY_DATA
PCKNUMBER=
Identificador único entre os pacotes da aplicação
FLAG=
0 para pacotes regulares e 1 para pacotes especiais que
possuem operações executadas apenas no destino e devem
ser roteados usando apenas XY tradicional
ADDRESS=
Endereço de rede do NAM que deve injetar o pacote
NINSTRUCTIONS=
Quantidade de instruções contidas no pacote
OP=
Identificador de operação (ADD, SUB, NOT, ...)
ARGUMENTS=
Número de operandos necessários para a instrução ser
executada
RESULT=
Um ou dois valores que indicam o número de palavras
transmitidas antes de injetar o resultado da instrução. Cada
resultado deve estar em uma linha ou separados por espaço.
DATA=
Um ou mais dados ou o
p
erandos utilizados
p
ara executar a
Quadro 3 - Sintaxe da linguagem de descrição de pacotes
38
O arquivo com a descrição dos pacotes, gerado a partir do grafo, funciona
como uma memória no simulador do sistema. Essa memória é acessada pelos NAMs para
geração e injeção dos pacotes com as instruções e operandos na interface da rede. Na
ferramenta de simulação os NAMs que acessam a memória lêem esse arquivo e identificam os
campos de cada pacote através das macros da linguagem de descrição de pacotes e injetam as
palavras correspondentes do pacote.
Durante a simulação diversas informações podem ser obtidas para avaliação de
desempenho. Entre as informações coletadas estão: tempo de execução da aplicação; memória
requerida; total de dados transmitidos (em número de palavras e em bytes); informações onde
os pacotes são criados, recebidos e roteados; informações sobre cada pacote, como
comprimento, tempo médio de transmissão e número de roteamentos; taxa de
ocupação/execução das UPRs; média de utilização dos canais; taxa efetiva de transmissão.
39
Capítulo 5
Resultados
Neste capítulo serão apresentados os resultados de 20 simulações realizadas
com o intuito de avaliar o desempenho do sistema IPNoSys. Os resultados apresentados são
fornecidos pelo ambiente de simulação, apresentado no capítulo anterior, e são utilizados
como métricas para o estudo da viabilidade do desenvolvimento do sistema proposto. As
simulações foram realizadas utilizando três aplicações. A primeira aplicação é um simples
contador, usado na avaliação da eficácia da execução localizada para o tratamento das
situações de deadlock. Nessas simulações variou-se o número de instruções utilizadas
(adições) e a estratégia de execução (paralela ou seqüencial). A segunda aplicação é a
implementação da Transformada Discreta do Cosseno em duas dimensões (DCT-2D – Two
Dimensional Discrete Cosine Transform), que também variou nas estratégias de execução, e
serviu de base para comparações de desempenho com a plataforma STORM (REGO, 2006).
A última aplicação é a adição de ponto flutuante usando o padrão IEEE 754 (PATTERSON,
1994) que poderá ser usada como uma rotina de tratamento de tal operação ao invés da
implementação em um hardware específico.
5.1 Estudo de Caso 1: Contador
Para avaliar a eficiência da execução localizada no tratamento do deadlock,
bem como para a obtenção dos primeiros resultados de desempenho do sistema proposto,
onde foram avaliadas a taxa de ocupação dos buffers de resultados nos árbitros e a quantidade
de instruções executadas em cada nodo, foram realizadas simulações com a execução do
contador simples, variando o número de instruções e a estratégia empregada (seqüencial ou
paralela). O contador foi implementado através de adições unitárias e acumulações sucessivas.
Após a última adição o resultado acumulado, que representa o número de instruções no
pacote, é armazenado na memória. Assim as simulações diferenciam-se pelo tamanho do
pacote, isto é, pelo número de instruções em cada pacote. O número de instruções usadas em
cada simulação foi de 8, 16, 32, 64, 128 e 256. E para cada simulação foi realizada uma
execução seqüencial e uma execução paralela. A estratégia de execução paralela consiste em
40
dividir as instruções da aplicação em quatro pacotes que são injetados pelos quatro cantos da
rede e executados paralelamente. A seguir serão apresentados os resultados das simulações
comparando as duas estratégias de execução.
O gráfico da Figura 20 demonstra a quantidade de bytes de instrução que foram
processados em cada nodo, de uma rede 4x4, nas seis simulações usando a estratégia
seqüencial. Nessa estratégia de execução a aplicação é descrita através de um único pacote.
Pelo gráfico percebe-se a concentração da execução das instruções nos nodos 3,1 e,
principalmente, 3,2. Isso ocorre devido à injeção do pacote no nodo 0,0 e, em conseqüência, o
tratamento do deadlock, através da execução localizada, no nodo 3,2, como apresentado
anteriormente. Para a dimensão da rede utilizada nas simulações (4x4) a execução localizada
acontece no nodo 3,2 para aplicações cujo número de instruções é superior a 32, como
demonstra o gráfico da Figura 20. Além disso, a concentração nos nodos 3,1 e 3,2 tende a
aumentar à medida que o número de instruções no pacote também aumenta. Nos outros nodos
o número de instruções executadas se mantém equilibrado.
Figura 20 - Concentração de instruções em cada UPR nas execuções seqüenciais
Através desses resultados percebe-se também o desperdício do potencial de
processamento do sistema, visto que a maior parte do processamento é feito em poucos nodos
(principalmente nos nodos 3,1 e 3,2). Assim, para melhor aproveitamento desse potencial as
mesmas seis simulações foram realizadas utilizando execução em paralelo. Para isso, a
aplicação, nas seis simulações, foi descrita através de quatro pacotes injetados cada um por
41
um dos quatro cantos da rede e executados paralelamente. A Figura 21 apresenta o gráfico
com a quantidade de byte de instrução que foram processados em cada nodo para as seis
simulações.
Figura 21 - Concentração de instruções em cada UPR nas execuções paralelas
Nessa estratégia de execução (paralela) a quantidade de instruções executadas
nos nodos é mais bem distribuída. Mesmo existindo uma maior concentração nos nodos dos
cantos da rede (nodos 0,0; 0,3; 3,0 e 3,3 ), o número de instruções executadas nos demais
nodos também cresce com o crescimento do tamanho dos pacotes, promovendo um melhor
aproveitamento do potencial de processamento do sistema
Esse gráfico também demonstra como o algoritmo spiral complement distribui
a carga nos cantos da rede, evitando congestionamento nos canais da região central da rede.
De um modo geral, o padrão de tráfego complement juntamente com o algoritmo de
roteamento XY tende a concentrar a maior parte do tráfego nos canais centrais. No caso do
sistema IPNoSys, o algoritmo de roteamento evita a concentração permitindo a injeção de
novos pacotes.
Com relação ao impacto que o paralelismo representa para a execução de uma
aplicação, foi realizada uma análise comparativa entre as estratégias seqüencial e paralela. A
comparação leva em consideração o tempo de execução, o tempo médio de transmissão de
palavras, a utilização média de canais e a taxa efetiva de transmissão.
42
A comparação do tempo de execução (em ciclos) é apresentada no gráfico da
Figura 22. A curva do tempo de execução na estratégia seqüencial cresce mais rapidamente a
partir de aplicações que possuem acima de 32 instruções, enquanto que na implementação
paralela, o tempo de execução cresce de forma quase linear. O crescimento do tempo de
execução na estratégia seqüencial se dá a partir desse número de instruções devido às
dimensões da rede (4x4), quando a situação de deadlock ocorre e acontece a execução
localizada no nodo 3,2. Logo, esse fenômeno deve acontecer sempre, mas a relação com o
número de instruções é dependente da dimensão da rede. Assim, para redes com dimensões
menores que 4x4 esse fenômeno deve acontecer com uma quantidade de instruções menor que
32, e para dimensões maiores com uma quantidade ainda maior.
Figura 22 - Tempo de execução para as aplicações simuladas
Dessa forma, é interessante utilizar métricas para avaliação da carga nos canais
entre os nodos. As métricas utilizadas correspondem a tempo médio para transmissão de
palavras, utilização média de canais e taxa efetiva de transmissão, todas definidas em
(TEDESCO, 2005). O tempo médio para transmissão das palavras dos pacotes em cada enlace
(canais bidirecional) entre os nodos é definido em pela Equação 2, que é a soma dos ciclos
por flit ou cpf (Equação 1) de todos os pacotes dividido pela quantidade de pacotes
transmitido no enlace. O cálculo de cpf corresponde ao intervalo de tempo para transmitir
todas as palavras do pacote dividido pelo tamanho desse pacote. Neste trabalho, os flits, nas
equações originais, são referenciados como palavras por não se tratar de uma rede com
chaveamento exclusivamente do tipo wormhole.
i
ii
i
pcksize
tpftpl
cpf
intint
−
= Equação 1
43
npck
cpf
avcpf
npck
i
i
channelXY
∑
=
=
1
Equação 2
Onde:
tplint
i
: momento da transmissão da última palavra de um pacote no canal;
tpfint
i
: momento da transmissão da primeira palavra de um pacote no canal;
pcksize
i
: tamanho do pacote transmitido no canal em número de palavras;
npck: número de pacotes transmitidos no canal
Para comparação entre as duas estratégias de execução, foram utilizadas apenas
as simulações com 256 instruções nas duas estratégias de execução. A Figura 23 e a Figura 24
apresentam os gráficos das estratégias de execução seqüencial e paralela, respectivamente.
N
3,0
N
3,1
N
3,2
N
3,3
N0,3
N1,3
N2,3
N3,3
1,46
1,46
0,00
0,50
1,00
1,5 0
Ciclos
NodosnoeixtoX
Nodosno
eixtoY
Tempomédiodetransmissãodepalavras
noscanaisfísicos(seqüencial)
Figura 23 - Tempo médio de transmissão das palavras na execução seqüencial do contador
N3,0
N3,1
N3,2
N3,3
N0,3
N1,3
N2,3
N3,3
1,18
0,90
1,00
1,10
1,20
Ciclos
NodosnoeixtoX
Nodosno
eixtoY
Tempo médiodetransmissãode
palavrasnoscanaisfísicos(paralela)
Figura 24 - Tempo médio de transmissão das palavras na execução paralela do contador
44
Deve-se notar que essa medida corresponde ao tempo médio de transmissão
das palavras de todos os pacotes que passaram pelo canal em ambos os sentidos. Portanto, os
valores estão relacionados ao enlace entre dois nodos, sejam eles no eixo horizontal ou
vertical. Para cada gráfico é mostrada uma visão bidimensional da rede, exibindo todos os
valores calculados nos enlaces entre os nodos correspondentes. Nesses gráficos também são
destacados os valores máximos. Na execução seqüencial os valores máximos são de 1,46
ciclos por palavras transmitidas nos enlaces entre os nodos
1,2 e 2,2 e entre os nodos 2,2 e
3,2, que são justamente os enlaces que ligam os nodos que fazem o tratamento do deadlock. E
em alguns enlaces (por exemplo entre os nodos
1,2 e 1,3; entre 2,2 e 2,3) o tempo é igual a
zero pois nesse canais nenhuma palavra foi transmitida.
Na simulação do contador (com 256 instruções) executado paralelamente,
todos os canais transmitiram alguma palavra, e como se percebe, os tempos médios mais
elevados são aqueles dos enlaces que interligam os nodos dos cantos (o valor máximo é de
1,18 ciclos entre os nodos
0,3 e 1,3). Esse resultado demonstra que quando a carga na rede é
melhor distribuída, a vazão é maior, ou seja, existe uma espera menor entre a transmissão das
palavras do pacote.
Outra métrica muito comum para avaliação do desempenho nas NoCs é a
utilização média dos canais, que corresponde ao percentual de largura da banda utilizado
pelos pacotes para transmissão de dados (Equação 3). Esse percentual é calculado através da
soma dos tempos de transmissão de cada pacote transmitido pelo canal divido pelo tempo que
o canal ficou ocupado transmitindo todos os pacotes.
Equação 3
Onde:
tplint
i
: momento da transmissão da última palavra de um pacote no canal;
tpfint
i
: momento da transmissão da primeira palavra de um pacote no canal;
tslint
i
: momento da transmissão da primeira palavra do primeiro pacote transmitido no
canal;
tsfint
i
: momento da transmissão da última palavra do o último pacote transmitido no
canal;
O gráfico da utilização média dos canais da implementação seqüencial é
apresentado na Figura 25 e da implementação paralela na Figura 26. Na implementação
seqüencial os canais da periferia da rede (exceto os canais da esquerda) são utilizados em
45
praticamente sua capacidade máxima (o valor 1 representa 100%). Isso significa que durante
todo o tempo de simulação esses canais estavam transmitindo palavras do pacote, por fazerem
parte do percurso da primeira espiral definida no spiral complement, até o tratamento do
deadlock. Inclusive quando o deadlock é completamente resolvido, o restante do pacote
continua sendo transmitidos por estes canais no percurso da primeira espiral e o início da
segunda espiral do algoritmo spiral complement, como apresentado na Figura 14.
N
3,0
N
3,1
N
3,2
N
3,3
N0,3
N1,3
N2,3
N3,3
1,00
1,00
1,00
1,00
1,00
1,00
0,00
0,50
1,00
Pe r cent ual
NodosnoeixtoX
Nodosno
eixtoY
UtilizaçãoMédiadeCanais(seqüencial)
Figura 25 - Utilização média dos canais na execução seqüencial
Na implementação paralela (Figura 26) o valor máximo de utilização é de 0,97
entre os nodos
1,2 e 1,3 e entre os nodos 1,2 e 2,2. Nessa implementação, diferentemente da
implementação seqüencial, todos os canais são utilizados e devido ao balanceamento da
carga, a média de utilização é mais uniforme.
(a) Visão tridimensional (b) Visão bidimenssional
N
3,0
N
3,1
N
3,2
N
3,3
N0,3
N1,3
N2,3
N3,3
0,97
0,97
0,00
0,50
1,00
Per ce nt ual
NodosnoeixtoX
Nodosno
eixtoY
UtilizaçãoMédiadeCanais (Paralelo)
Figura 26 - Utilização média dos canais na execução paralela
No entanto, segundo (TEDESCO, 2005), o cálculo da utilização média dos
canais pode ser superestimado em redes que utilizam o mecanismo wormhole (
IPNoSys usa
uma combinação wormhole com VCT). Isso pode acontecer, uma vez que, no mecanismo
46
wormhole, quando um canal é alocado para transmissão de um pacote, ele permanece
indisponível para transmissão de outros pacotes até o final da transmissão do primeiro, como
acontece no sistema
IPNoSys. Assim, a taxa efetiva de transmissão de dados pode representar
com maior precisão essa medida. A taxa efetiva corresponde ao número de bits de todas as
palavras transmitidas durante o tempo de transmissão no canal.
Equação 4
Onde:
pcksize
i
: tamanho do pacote transmitido no canal em número de palavras;
flitsize: largura da palavra em número de bits;
nsimc: número total de ciclos de relógio gasto para envio de todos os pacotes que
passaram pelo canal
A comparação entre a taxa efetiva na execução seqüencial e na execução
paralela é feita através dos gráficos das Figura 27 e Figura 28. A primeira tem uma taxa
efetiva praticamente uniforme para os canais usados na primeira espiral do algoritmo spiral
complement, tendo o valor máximo de 10,98 bits/ciclo. E, apesar de alguns canais estarem
ocupados em 100% do tempo, como mostrado na Figura 25, eles não apresentam uma taxa
efetiva de transmissão maior que os demais no percurso da espiral. Na implementação
paralela a taxa efetiva máxima é quase o dobro da apresentada pela implementação seqüencial
e, como era de se esperar, os maiores valores na implementação paralela estão localizados no
enlaces mais externos, principalmente nos dos cantos da rede. Além disso, como quatro
pacotes são executados paralelamente, as quatro espirais do spiral complement são realizadas,
e com isso, os canais mais externos são usados nos dois sentidos pelos quatro pacotes, até que
cada espiral encontrar o enlace interno que continua seu percurso. Por esse motivo a taxa
efetiva dos enlaces externos é superior à dos enlaces internos.
Contudo, vale ressaltar que a taxa efetiva teórica máxima é de 72 bits/ciclo, já
que o enlace entre os nodos é constituído por dois canais físicos unidirecionais de 36 bits
(sendo 32 bits da palavra do pacote e 4 bits de controle que indica o tipo de palavra). Assim, a
taxa efetiva máxima calculada das implementações seqüencial e paralela estão a 15,25% e
26,36%, respectivamente da taxa efetiva teórica máxima.
47
N
3,0
N
3,1
N
3,2
N
3,3
N0,3
N1,3
N2,3
N3,3
10,98
0,00
5,00
10,00
15,00
Bits/cic lo
Nodosnoeixt oX
Nodosno
eixtoY
TaxaEfetivadetransmissão(Seqüencial)
Figura 27 - Taxa efetiva de transmissão seqüencial
(a) Visão tridimensional (b) Visão bidimenssional
N
3,0
N
3,1
N
3,2
N
3,3
N0,3
N1,3
N2,3
N3,3
18,98
0,00
5,00
10,00
15,00
20,00
Bits/ciclo
NodosnoeixtoX
Nodosno
eixtoY
TaxaEfetivadetransmissão(Paralelo)
Figura 28 - Taxa efetiva de transmissão paralela
5.2 Estudo de Caso 2: DCT-2D
O primeiro estudo de caso, foi utilizado para comparação do sistema IPNoSys
com um MP-SoC baseado em NoC, a plataforma STORM (REGO, 2006). Esse estudo de
caso corresponde à transformada discreta do cosseno em duas dimensões (DCT-2D - Two
Dimensional Discrete Cosine Transform).
A DCT bidimensional (DCT-2D) é a base para a compressão de imagens,
como no padrão JPEG, e consiste em transformar informações do domínio espacial para o
domínio da freqüência. Os dados de entrada são uma matriz (chamada de bloco) de 8x8 pixels
da imagem, que deve ser transformada em uma matriz de freqüências com as mesmas
dimensões. A DCT-2D foi implementada usando o algoritmo da separabilidade apresentado
em (AGOSTINI, 2002), que otimizou o algoritmo proposto por (KOVAC, 1995). O algoritmo
48
da separabilidade realiza a DCT unidimensional (DCT-1D) das linhas do bloco, em seguida, a
DCT-1D sobre as colunas da matriz resultante do primeiro cálculo. O cálculo da DCT-1D
consiste em uma série de operações aritméticas realizadas em uma seqüência de seis passos
com apresentado em (AGOSTINI, 2002).
Para a implementação da DCT-2D no sistema
IPNoSys, foi usada uma
implementação em C baseada no algoritmo da separabilidade para o cálculo da DCT-2D. A
partir dessa implementação foi construído o grafo de fluxo de dados da aplicação (Anexo II),
que corresponde ao cálculo da DCT-1D de cada linha do bloco, seguido pelo mesmo cálculo
sobre cada coluna do resultado anterior. O grafo de fluxo de dados da DCT-1D apresenta um
padrão para o cálculo dos resultados, que consiste em carregar os valores (da matriz de
entrada), realizar todas as operações aritméticas seqüencialmente, onde os resultados
intermediários alimentam as operações subseqüentes, e retornar os resultados. Esse cálculo é
realizado em cada conjunto de oito pontos por vez (uma linha do bloco), sendo repetido oito
vezes para completar o bloco. Depois de terminada a DCT-1D do bloco, a matriz resultante é
transposta para que o mesmo cálculo da DCT-1D seja realizado, agora sobre as colunas do
resultado anterior. Além disso, também se percebeu que no cálculo da DCT-1D os oito
valores de cada linha da matriz de saída podem ser calculados aos pares, uma vez que a
seqüência das operações aritméticas é praticamente a mesma, diferenciando-se apenas na
última operação, e os operandos utilizados nesse cálculo são os mesmos. Isso demonstra a
dependência de dados e operações entre os pares. Assim, o cálculo de cada par de pontos de
uma linha da matriz de saída da DCT-1D foi definido por um subgrafo, sendo o cálculo de
toda a linha definido por quatro subgrafos.
De acordo com a metodologia, dois ou mais subgrafos sem dependência de
dados são transformados em pacotes independentes que podem ser executados em paralelo.
Do mesmo modo, dois ou mais subgrafos com dependências de dados, podem ser
transformados em dois ou mais pacotes que recorrem a operações explícitas de sincronização.
Dessa análise, para a implementação da DCT-2D no sistema IPNoSys, constatou-se a
necessidade de um pacote inicial, que carrega os valores da memória, e quatro pacotes para o
cálculo efetivo da DCT-1D de uma linha de um bloco 8x8. Cada um dos quatro pacotes é
responsável pelo cálculo de dois resultados da DCT-1D da linha. Os dados utilizados nas
operações desses pacotes são carregados da memória e distribuídos para eles através do
pacote inicial. Esses cinco pacotes são responsáveis pelo cálculo das DCT-1D de uma linha de
um bloco 8x8, devendo ser repetidos 8 vezes para o cálculo completo de uma DCT-1D do
49
bloco. Em seguida, a segunda DCT-1D deve ser calculada, agora sobre as colunas do
resultado da primeira DCT-1D. Um sexto pacote (controle das DCT-1D ) indica se o cálculo
corresponde a primeira ou a segunda DCT-1D. Para controlar em qual bloco da imagem cada
DCT deve ser aplicada é necessário um sétimo pacote (controle de blocos). Ao final do
cálculo sobre todos os blocos, um pacote especial, denominado pacote finalizador é
executado. O pacote finalizador tem o identificador de pacote com o valor zero e deve ser
executado ao final de qualquer aplicação no sistema
IPNoSys. Portanto, a DCT-2D usando a
propriedade da separabilidade foi implementada através de sete pacotes, além do pacote
finalizador. A Figura 29 apresenta a relação entre tais pacotes.
Na figura, pacotes dispostos lado a lado representam pacotes que podem ser
executados em paralelo ou são executados de forma excludente em uma tomada de decisão.
Pacotes abaixo um do outro, representam pacotes seqüenciais na sua injeção e/ou execução e
as setas indicam a relação entre eles. As setas com linhas cheias indicam a ordem de injeção
do pacote (utilização da instrução EXEC); seta com linhas alternando pontos e retas indicam
injeção de pacotes que necessitam de sincronização (utilização da instrução SINEXEC); setas
com apenas linhas indicam sinal de sincronização (utilização da instrução SINC); finalmente,
setas com apenas pontos indicam o envio de um valor para ser incluído em um pacote
específico durante a injeção desse pacote (instrução SEND), veja a legenda na Figura 29. Nos
pacotes: controle de blocos, controle das DCT-1D e pacote inicializador são usadas instruções
de tomada de decisão (representada pelo losango) que determina qual pacote será injetado em
seguida. Nesses três pacotes foi utilizada a instrução BE (Branch on Equal), a qual descarta
tantas quantas palavras indicadas no campo
Result_0 se os dois operandos dessa instrução
forem iguais (no caso desses pacotes, são testados se os valores dos contadores atingiram o
valor máximo de cada repetição). Se forem diferentes, a instrução seguinte deve ser
executada, desse modo é possível fazer a decisão sobre qual instrução será executada. Como
pode ser visto na Figura 29, no cálculo da DCT-1D de cada linha existe um pacote
inicializador que carrega os dados da memória, os distribui, e ordena a injeção assíncrona dos
próximos quatro pacotes, através de EXECs, e a execução sincronizada do mesmo pacote
inicializador, através de SINEXEC.
50
Figura 29 - Relação entre os pacotes na aplicação da DCT-2D
Quando cada um dos quatro pacotes, que realizam o cálculo, conclui sua
execução, escreve na memória os dois resultados produzidos nesse cálculo e envia um sinal de
sincronização (SINC) ao NAM que executou o pacote inicializador. Esse NAM também está à
espera de todos os sinais de sincronização indicados no SINEXEC para que seja possível
injetar novamente o pacote incializador e realizar o cálculo de uma nova linha da DCT-1D. A
cada injeção do pacote inicializador, uma instrução de adição contida no pacote, implementa
um contador, e o valor resultante é enviado (através da instrução de SEND) ao NAM que
injeta o pacote inicializador. Isso permite que o valor desse contador seja inserido no pacote
inicializador quando ele for novamente injetado e uma instrução de tomada de decisão
verifica se o contador atingiu o número total de linhas de um bloco (o valor oito), nesse caso
ao invés de ordenar a injeção do pacote inicializador, a ordem de injeção é para o sexto
pacote. O sexto pacote também mantém um contador (que será chamado de contador de DCT)
que indica se o cálculo realizado é da primeira ou da segunda DCT-1D, além de calcular os
endereços de memória para carregar os valores de entrada da DCT-1D e os endereços para
armazenar os resultados calculados. Enquanto não é completada as duas DCT-1D (controlado
pelo contador de DCT), esse pacote envia os endereços calculados para o NAM que injeta o
pacote inicializador, seguido pela ordem de injeção do pacote inicializador. Quando o pacote
51
inicializador ordena novamente a injeção desse pacote e o contador de DCT indica que as
duas DCT-1D foram realizadas, uma tomada de decisão determina a injeção do pacote que
controla em qual bloco da imagem deve ser calculada a próxima DCT-2D ao invés da injeção
do pacote inicializador novamente. Assim como os pacotes anteriores, o controle de em qual
bloco da imagem está sendo calculado a DCT-2D é mantido por um contador do pacote, e
enquanto esse contador não atingir a quantidade total de blocos da imagem é enviada uma
ordem de injeção do pacote que controla as DCT-1D sobre o bloco, que por sua vez invoca o
pacote incializador que ordena a injeção do quatro pacote de cálculo depois de carregar os
valores da memória.
Antes de incluir o suporte a laços de repetição no sistema
IPNoSys, eram
necessários 80 pacote para calcular a DCT-2D de cada bloco da imagem, vide o Anexo III.
Uma vez que o cálculo da DCT-1D de uma linha é realizado por cinco pacotes (pacote
inicializador e os outros quatro pacotes que produzem dois resultados cada um), assim as oito
linhas do bloco eram calculadas através de 40 pacote. No entanto, para o cálculo da segunda
DCT-1D eram necessários mais 40 pacotes, totalizando 80 pacotes. O total de pacotes para o
cálculo da DCT-2D de toda a imagem correspondia ao número de blocos da imagem
multiplicado por 80, ou seja, dependia da quantidade de blocos (tamanho da imagem). E todos
esses pacotes eram armazenados na memória e injetados durante o cálculo da DCT-2D de
cada bloco. Com o suporte a laço de repetição a mesma DCT-2D é calculada através de 7
pacotes, além do pacote finalizador, armazenados na memória que são injetados tantas vezes
quanto necessário, dependendo do tamanho da imagem.
As simulações da execução da DCT-2D no sistema
IPNoSys utilizou imagens
do tipo subQCIF (128x96). Imagens com essa dimensão são divididas em 192 blocos, os
quais eram calculados através de 15.360 pacotes antes do suporte a laços de repetição. Com
suporte a laço de repetição são necessários apenas sete pacotes como apresentados na Figura
29. Todas as simulações utilizaram uma rede de 4x4 UPRs para o sistema
IPNoSys. As
simulações foram realizadas através de três configurações de pacotes. Cada configuração
indica quais os NAMs que injetam cada um dos sete pacotes para o cálculo da DCT-1D de
uma linha. A primeira configuração consiste em uma execução seqüencial dos sete pacotes,
ou seja, todos os pacotes são injetados por um mesmo NAM de um dos cantos da rede. A
segunda configuração corresponde à injeção dos pacotes que controlam os laços (do número
de blocos e de qual DCT-1D está sendo aplicada) e o pacote inicializador por um NAM dos
cantos e os outros quatro pacotes que realizam o cálculo pelo NAM do canto mais próximo de
52
onde o pacote incializador concluiu sua execução. Já a terceira configuração consiste na
injeção dos pacotes que controlam os laços e o pacote incializador por um NAM do canto e os
outros quatro pacotes injetados cada um em um dos quatro cantos da rede, ou seja, executados
paralelamente. A seguir, a Tabela 1 apresenta os resultados de simulação para as três
configurações, com relação ao tempo de execução e total de memória requerida.
Tabela 1 - Resultados de simulação da DCT-2D
Tempo de
execução (ciclos)
Memória
requerida
(byte)
Config. 1 3316101 167562
Config. 2 3239109 167562
Config. 3 3076102 167562
Para efeito de comparação com sistemas de processamento tradicionais,
também foram realizadas simulações da execução da DCT-2D para imagens subQCIF na
plataforma STORM (REGO, 2006), que é um sistema MP-SoC parametrizável. Nas
simulações com a plataforma STORM foram utilizadas uma NoC 4x4 como subsistema de
comunicação. As instâncias da plataforma STORM utilizaram memória distribuída ou
memória compartilhada, e em todas as simulações foram realizadas execuções seqüenciais e
paralelas da aplicação. As instâncias com memória compartilhada foram compostas por
quinze processadores e uma memória, uma vez que o módulo de memória deve ocupar um
dos dezesseis nós da NoC. Essas instâncias foram simuladas com cache, sem cache, ou com
cache somente leitura. As instâncias com memória distribuída foram simuladas com dezesseis
processadores, cada um ligado ao seu módulo de memória. A Tabela 2 compara os resultados
de simulação entre a plataforma STORM e o sistema
IPNoSys. Os resultados do sistema
IPNoSys correspondem as simulações com laço de repetição e sem laço de repetição para as
três configurações. Os resultados comparados correspondem ao número de ciclos para
execução da aplicação e a quantidade de memória requerida no cálculo da DCT-2D de
imagens subQCIF.
53
Tabela 2 - Resultados de simulação STORM e IPNoSys
Arquitetura Instância
Tempo de
Execução (ciclos)
Memória Requerida
(bytes)
STORM
Com Cache (Seqüencial) 13453796 102056
Com Cache (Paralelo) 3205882 120824
Sem Cache (Seqüencial) 76554041 102072
Sem Cache (Paralelo) 31820799 120840
Cache Apenas Leitura
(Seqüencial) 15851219 102072
Cache Apenas Leitura (Paralelo) 5223436 120824
Memória Distribuída
(Seqüencial) 15914696 102188
Memória Distribuída (Paralelo) 3425962 164804
IPNoSys
Config. 1 (sem laço de repetição) 1449985 3151872
Config. 1 (com laço de repetição) 3316101 167562
Config. 2 (sem laço de repetição) 1449985 3151872
Config. 2 (com laço de repetição) 3239109 167562
Config. 3 (sem laço de repetição) 1152001 3151872
Config. 3 (com laço de repetição) 3076102 167562
A Figura 30 apresenta o gráfico de comparação de memória requerida para
execução da DCT-2D de uma imagem subQCIF nas duas arquiteturas. A memória requerida
corresponde à quantidade de bytes relativa aos dados locais e globais somados a quantidade
de bytes relativa ao código. No gráfico, o valor dessa soma é mostrado do lado direito da barra
que representa o valor. Percebe-se que a quantidade de memória requerida no sistema
IPNoSys é igual para as três configurações sem laço de repetição. O mesmo também acontece
com laço de repetição, visto que a diferença entre as três configurações está apenas nos
endereços dos NAMs que injetam os pacotes. A quantidade de memória requerida nas
simulações do sistema
IPNoSys sem laços de repetição é claramente muito superior as
mesmas configurações com laço de repetição e a qualquer uma das instâncias da plataforma
STORM. Esse fato se deve ao estilo de programação ou otimização do código. A DCT é uma
aplicação realizada através de muitas repetições, o que geralmente é resolvido por laços de
repetição nas linguagens tradicionais. No entanto, na implementação sem laço de repetição
todo o código é repetido explicitamente e como já mencionado os 15.360 pacotes necessários
para o cálculo da DCT-2D de uma imagem subQCIF são todos armazenados na memória. No
sistema
IPNoSys, todos os dados são considerados globais e a quantidade de memória
requerida para esses dados (com ou sem laço de repetição) na simulação da DCT-2D é
relativamente próxima a quantidade utilizada na plataforma STORM, sendo portanto, o
54
código o responsável pela grande quantidade de memória requerida no sistema
IPNoSys sem
laço de repetição.
Figura 30 - Memória requerida no IPNoSys com e sem laço de repetição e na STORM
No gráfico da Figura 31 é feita a comparação apenas das simulações com laço
de repetição no sistema
IPNoSys e a plataforma STORM. Nessa figura percebe-se que, nesse
caso, a quantidade de memória relativa ao código do sistema
IPNoSys é sutilmente menor que
qualquer instância da STORM e a quantidade de dados globais é maior que todas as
instâncias. No entanto, mesmo que o total de memória requerida no
IPNoSys seja superior às
instâncias da STORM, a diferença é relativamente pequena com relação à instância de
memória distribuída executada em paralelo da STORM, o que é perfeitamente razoável,
devido as semelhanças entre o
IPNoSys e essa instância da STORM.
55
Figura 31 - Memória requerida no IPNoSys com laço de repetição e na STORM
Com relação ao tempo de execução (Figura 32) o sistema
IPNoSys mostra seu
grande potencial. Na implementação da DCT-2D sem laço de repetição os pacotes são
específicos para o cálculo de uma dada DCT-1D de certo bloco, sendo necessário apenas sua
injeção no sistema para o cálculo ser realizado, portanto sendo extremamente rápida a
execução da aplicação. Com o suporte a laços de repetição os pacotes se tornaram não
específicos, necessitando, portanto de: computações extras para controle dos laços, cálculo de
endereços de memória e envio de valores atualizados para serem inseridos no momento da
injeção dos pacotes. Com isso, houve um pequeno crescimento no tempo de execução da
aplicação, e adicionalmente o sistema
IPNoSys passou a utilizar um canal virtual exclusivo
para o envio de pacotes especiais para NAMs específicas. Como o canal virtual é uma
multiplexação no tempo para transmissão de pacotes distintos através do mesmo canal físico,
a quantidade de pacotes especiais também tem impacto no tempo de execução. Na Figura 32
pode ser visto o quanto as mudanças no sistema
IPNoSys influenciaram no tempo de
execução da aplicação. Nesse gráfico também se percebe que o tempo de execução no pior
caso do
IPNoSys com laço de repetição (Configuração 1) está entre os dois melhores casos da
STORM (Memória distribuída Paralelo e Com Cache Paralelo). E o melhor caso do
IPNoSys
com laço de repetição (Configuração 3) se mostra superior a qualquer instância da STORM.
56
Figura 32 - Comparação do tempo de execução entre STORM e IPNoSys
5.3 Estudo de Caso 3: adição de ponto flutuante
O segundo estudo de caso é uma implementação da adição de ponto flutuante
baseada no padrão IEEE 754. Nesse padrão os valores ponto flutuante são representados
em notação científica normalizada
2
através de 32 bits, onde o bit mais significativo
corresponde ao sinal do número, seguido pelos próximos 8 bits que indicam o expoente e
os últimos 23 bits o significante ou mantissa. A Figura 33 ilustra a representação binária
do número 2,5 nesse padrão.
0 10000000 01000000000000000000000
s exp significante
Figura 33 - Representação do valor 2,5 no padrão IEEE 754
O algoritmo da adição de números ponto flutuante (PATTERSON, 1994)
nesse padrão é apresentado a seguir no fluxograma da Figura 34.
2
Um valor normalizado tem sua parte inteira entre 1 e 9, ou seja, maior ou igual a 1 e menor ou igual a 9
57
Figura 34 - Fluxograma do algoritmo da adição de ponto flutuante
Nesse algoritmo, os números devem está elevados à mesma potência antes de
realizar o cálculo, portanto o número de menor expoente deve ser deslocado até que se torne
igual ao maior. Em seguida seus significantes são adicionados e o resultado deve ser
normalizado, caso já não esteja. Se necessário, esse resultado deve ser arredondado para que
possa ser representado em uma determinada quantidade de bits. Caso o arredondamento torne
o número não normalizado o processo deve se repetir, senão o cálculo está concluído.
O desenvolvimento dessa aplicação para o sistema
IPNoSys tem o objetivo de
ser usada em uma futura avaliação do custo-benefício da utilização de uma rotina para
execução de uma instrução que não existe implementação específica no hardware. Assim,
mesmo que o sistema não possua uma unidade aritmética de ponto flutuante em hardware,
ainda assim, instruções desse tipo poderiam ser suportadas pelo sistema através da execução
58
dessas rotinas de tratamento, executadas sempre que houvesse instruções de ponto flutuante
nas aplicações.
A implementação do algoritmo apresentado na Figura 34 para o sistema
IPNoSys foi realizada através de sete pacotes, incluindo o pacote finalizador. O primeiro
pacote corresponde às computações necessárias para obtenção dos sinais, expoentes e
significantes de cada número e a soma dos significantes. O segundo pacote testa se deve ser
realizado o deslocamento à direita ou à esquerda da soma para realizar sua normalização, para
isso é realizada uma ordem de injeção do terceiro pacote ou do quarto pacote. O terceiro
pacote normaliza a soma através de deslocamentos à direita e testa se houve overflow. No
quarto pacote a normalização é realizada através de deslocamentos à esquerda e testa se houve
underflow. A última instrução do terceiro e do quarto pacote é uma ordem de injeção do
quinto pacote, que arredonda o significante para representação em 32 bits e testa se esse
número está normalizado. Se estiver normalizado o sexto pacote deve ser executado, caso
contrário o segundo pacote deve ser novamente executado. O sexto pacote reagrupa o sinal,
expoente e significante do resultado e envia o valor para ser armazenado através do sétimo
pacote, que também é o pacote finalizador.
As simulações realizadas utilizaram os seguintes pares de números ponto
flutuantes em notação científica: 2,5x10
0
e 3,4x10
0
; 5x10
-1
e -4,375x10
-1
; -3,52x10
0
e -
9,05x10
0
; 3x10
-3
e 5x10
-5
; 1,7x10
0
e 1x10
-5
. Os valores escolhidos para simulação levaram em
conta se os números possuem o mesmo expoente, se possuem o mesmo sinal e se é grande a
diferença entre os expoentes.
Os resultados de simulação para os 5 pares de valores utilizados nas simulações
são resumidos na tabela a seguir. Os resultados de simulação considerados correspondem a
tempo de execução, memória requerida e quantidade de pacotes injetados (pacotes regulares e
pacotes de controle).
Tabela 3 - Resultados de simulação da adição de ponto flutuante
Valores
Tempo de
Execução (ciclos)
Memória
Requerida (bytes)
Pacotes Transmitidos
Regulares Controle
2,5x10
0
e 3,4x10
0
968 1462 5 24
5x10
-1
e -4,375x10
-1
898 1462 5 21
-3,52x10
0
e -9,05x10
0
809 1462 4 20
3x10
-3
e 5x10
-5
1737 1462 10 46
1,7x10
0
e 1x10
-5
3574 1462 21 101
59
Como a idéia é utilizar a rotina para execução de instruções não implementadas
em hardware, um dos fatores determinantes é o tempo de execução. Nas simulações
realizadas, os tempos de execução tiveram grandes variações (entre 809 e 3574 ciclos)
dependendo dos valores utilizados. Isso é natural, visto que, no algoritmo apresentado na
Figura 34, a repetição do processo depende do arredondamento e da normalização do
resultado da adição. Logo, quanto maior a diferença entre os expoentes do número maior é a
chance do processo se repetir para normalização e conseqüentemente maior será o tempo de
execução, como acontece nas duas últimas simulações onde os expoentes tinham certa
diferença e nas outra não.
A respeito da quantidade de memória requerida para armazenar a rotina, não
existe nenhuma relação com os valores a serem somados, uma vez que a rotina simplesmente
carrega os valores da memória e, caso seja necessário o processo se repetir, os mesmo pacotes
são novamente injetados com os valores atuais.
Considerando a quantidade de pacotes transmitidos, novamente pode ser visto
a influência dos valores usados na adição e o número de repetições do processo de
normalização. Nas três primeiras simulações o número de pacotes regulares transmitidos
(pacotes armazenados na memória) indica que não houve repetição, ou seja, na primeira volta
do laço o resultado já foi normalizado e o resultado pôde ser armazenado na memória.
Enquanto que nas duas últimas simulações a quantidade de pacotes transmitidos sugere que
houve mais de uma volta no laço de repetição, sabido que a aplicação foi descrita através de
sete pacotes e quantidade de pacotes transmitidos é superior a isso. Durante a execução da
aplicação, as ordens de injeção de outros pacotes (EXECs), atualização de contadores
(SENDs), e leitura e escrita de valores da memória (LOADs e STOREs) são instruções a
serem executadas em NAMs específicos, portanto sendo transmitidas através de pacotes de
controle. Assim, a quantidade de pacotes de controle também depende da repetição dos
pacotes regulares que os originam, portanto a quantidade de pacotes de controle transmitidos
também é maior nas duas últimas simulações.
60
Capítulo 6
Considerações Finais
O tema apresentado nesse texto é bastante inovador, não sendo do
conhecimento do autor qualquer publicação ou pesquisa equivalente. Por este motivo foi
proposto a realização de apenas um estudo de viabilidade de desenvolvimento de tal sistema.
As dificuldades relacionadas ao desenvolvimento do tema incluem os problemas comumente
relacionados às redes em chip, bem como os problemas específicos do sistema proposto, tais
como representação de aplicações e alterações a serem realizadas na estrutura do roteador.
Todos estes problemas constituem um grande desafio à viabilidade do desenvolvimento.
Contudo, a dissertação aqui apresentada aponta soluções e resultados que argumentam a favor
da viabilização do desenvolvimento do sistema
IPNoSys.
Nos estudos e experimentos realizados viu-se que é possível representar as
aplicações através de estruturas de dados que podem perfeitamente ser implementadas sob a
forma de pacotes. Viu-se também que é possível substituir os processadores tradicionais, de
um ambiente MP-SoC, com comunicação baseada em NoC, por núcleos consideravelmente
mais simples que podem acessar a memória e injetar os pacotes que descrevem a aplicação.
Com estas observações é possível transformar a rede em chip em uma unidade que realiza a
maior parte do processamento. Para tanto, pequenas transformações são necessária nos
roteadores da rede.
Os resultados obtidos mostram que com o sistema
IPNoSys é possível acelerar
a execução das aplicações, uma vez que o processamento das instruções é realizado no
percurso do pacote entre origem e destino. Observou-se ainda a possibilidade e simplicidade
para o processamento em paralelo das aplicações, graças aos múltiplos canais ponto-a-ponto,
disponíveis na rede em chip.
Também é possível descrever aplicações em forma de pacotes que trafegam na
rede, onde o modelo de computação adotado prevê a execução das instruções presentes no
início do pacote, a medida que este entra em um roteador, com a inserção dos resultados em
outras partes do pacote para futuras computações ou armazenamento. Esse modelo de
computação pode ser realizado em uma NoC, independentemente das dimensões da rede e da
quantidade de instruções na aplicação, uma vez que um pacote pode ser novamente roteado
61
em cada destino, sempre que houver mais instruções a serem executadas nesse pacote. Para
isto foi proposto, desenvolvido e validado o algoritmo spiral complement. Esse algoritmo
também realiza a distribuição da carga, de modo que não haja disputas pelos canais iniciais da
transmissão. A carga é distribuída para as extremidades da rede, diminuindo a possibilidade
de congestionamentos na região central da rede, permitindo assim os cantos opostos se
comunicar através dos canais dessa região.
Nesse modelo de computação os pacotes diminuem à medida que são
encaminhados e processados, o que contribui para a diminuição da carga na NoC, diminuindo
também as chances de ocorrerem congestionamento e aumentando a capacidade de injeção de
mais pacotes da mesma ou de outra aplicação.
O sistema
IPNoSys está, ainda, preparado para tratar e resolver
congestionamentos e disputas por canais ou situações de deadlock ou starvation, com o
tratamento desses problemas nas portas de saídas dos roteadores através de uma solução
nomeada de execução localizada. Essa solução se mostrou eficiente no tratamento dos
problemas citados, no entanto tende a concentrar a execução das instruções nas UPRs que
tratam o problema. Desse modo, estuda-se combinar, futuramente, a execução localizada com
canais virtuais com o intuito de evitar a concentração mencionada.
Além disso, o desenvolvimento de uma ferramenta para simulação e validação
dos conceitos básicos do sistema
IPNoSys permitiu apresentar resultados práticos para o
tratamento do problema de deadlock, para comparação direta com resultados obtidos através
de uma plataforma MP-SoC, a plataforma STORM e para avaliação do uso de rotinas em
software (conjunto de pacotes) para execução de instruções não implementadas em hardware.
Através da ferramenta, pôde-se constatar a possibilidade e as vantagens da execução de
aplicações em paralelo; o impacto, principalmente em memória requerida, do uso de laços de
repetição nas aplicações; e a obtenção de parâmetros para avaliação do uso de rotinas em
software para execução de instruções. Esses resultados comprovam a eficiência e apontam a
viabilidade do desenvolvimento do sistema
IPNoSys e indicam onde ainda deve haver esforço
de desenvolvimento.
Dentre os inúmeros trabalhos futuros estão: utilização de canais virtuais na
transmissão de pacotes regulares; estudo de variações do algoritmo spiral complement ou
desenvolvimento de outros algoritmos; configuração da quantidade de instruções executadas
em cada nodo (UPR e NAM) ao invés de apenas uma; modificar a arquitetura e a linguagem
de descrição dos pacotes de modo que seja possível separar instruções e operandos em
62
pacotes distintos. Dessa forma os pacotes de instrução podem configurar as UPRs antes da
execução da aplicação. Em seguida os pacotes com os operandos são inseridos e a aplicação é
executada. Com isso é possível reduzir ainda mais o tráfego na NoC. Nesse caso, as
instruções são transmitidas apenas uma vez nos pacotes de instruções enquanto que os pacotes
de dados são transmitidos sempre que necessário. Essa estratégia também pode ser útil para
implementar os laços de repetição; incluir, ao conjunto de instruções, operações de chamada
de função, as quais vão permitir ordenar a execução de pacotes com passagem de parâmetros
e eventualmente o retorno de resultados; desenvolvimento de compilador e outros softwares
básicos que permitam transformar uma aplicação em alto nível de abstração em um conjunto
de pacotes que podem ser executados no sistema
IPNoSys; descrição do sistema IPNoSys em
uma linguagem de descrição de hardware, de modo que seja possível obter outros resultados,
como área em chip e freqüência máxima de execução, além de permitir realizar síntese do
sistema.
63
Referências
ABDERAZEK, B. A., et al. Queue Processor Architecture for Novel Queue Computing
Paradigm Based on Produced Order Scheme. In:
Proceedings of the High Performance
Computing and Grid in Asia Pacific Region, Seventh International Conference on
(HPCAsia'04) - Volume 00. IEEE Computer Society: 2004.
_______. Design and architecture for an embedded 32-bit QueueCore.
Journal of Embedded
Computing. v. 2, n. 2, p. 191 - 205, 2006a.
_______. High-Level Modeling and FPGA Prototyping of Produced Order Parallel Queue
Processor Core.
The Journal of Supercomputing. v. 38, n. 1, p. 3-15, 2006b.
AGOSTINI, L. V.
Projeto de Arquiteturas Integradas para a Compressão de Imagens
JPEG. 143f. Mestrado, Instituto de Informática, Universidade Federal do Rio Grande do Sul,
Porto Alegre, 2002.
ALTERA, C. Nios II Processor Reference Handbook, Disponível em:
http://www.altera.com/literature/lit-nio2.jsp
. Acesso em: Jan. 2008
ARTIERI, A., et al. NomadikTM Open Multimedia Platform for Next-generation Mobile
Devices, 2006. Disponível em: http://www.st.com
. Acesso em: 20 jan. 2008
BACKUS, J.
Can Programming Be Liberated from the von Neumann Style? A
Functional Style and Its Algebra of Programs. Communications of the ACM, 1978; pp
613-641.
BENINI, L.; MICHELI, G. D. Networks on Chips: A New SoC Paradigm. IEEE Computer
Society Press: 2002; Vol. 35, pp 70-78.
BERMAN, P. E., et al.
Adaptive Deadlock and Livelock Free Routing with All Minimal
Path in Torus Networks.
Fourth Symposium on Parallel Algorithms and Architectures -
SPAA ’92, 1992; pp 3-12.
CALAZANS, N. L. V. Comunicação Intra-chip Não Síncrona: Paradigmas de projeto de
hardware para futuras
tecnologias. FACIN-PUCRS: Porto Alegre, 2007.
CANEDO, A., et al.
A GCC-based Compiler for the Queue Register Processor (QRP-
GCC). The 2006 International Workshop on Modern Science and Technology, IWMST2006,
Wuhan, 2006; pp 250-255.
_______.
Queue Register File Optimization Algorithm for QueueCore Processor. 19th
International Symposium on Computer Architecture and High Performance Computing, 2007.
64
CARARA, E. A.
Uma Exploração Arquitetural de Redes Intra-chip com Topologia
Malha e Modo de Chaveamento Wormhole. 65f. Trabalho de Conclusão II, Pontifícia
Universidade Católica do Rio Grande do Sul, Porto Alegre, 2004.
CARVALHO, M., et al. Estimação de Movimento em Hardware para o Projeto SBTVD
Utilizando o Algoritmo de Busca Completa. In: MOREIRA, A. M.; COSTA., U. S. D. (Org.)
IV Workshop Técnico Científico do DIMAp – 20 Anos – Artigos Selecionados.
EDUFRN: Natal, 2006. p. 36-47.
DALLY, W.; TOWLES, B.
Principles and Practices of Interconnection Networks. Morgan
Kaufmann Publishers Inc.: 2003.
DUATO, J., et al.
Interconnection Networks: An Engineering Approach. Morgan
Kaufmann Publishers Inc.: 2002; p 650.
EDENFELD, D., et al. 2003 Technology Roadmap for Semiconductors. IEEE Computer
Society Press: 2004; Vol. 37, pp 47-56.
FELPERIN, S. A., et al. Fully-adaptive routing: packet switching performance and wormhole
algorithms. In:
Proceedings of the 1991 ACM/IEEE conference on Supercomputing.
ACM: Albuquerque, New Mexico, United States. 1991.
FLYNN, M. J.
Some Computer Organizations and Their Effectiveness. IEEE Transactions
on Computers, 1972; pp 948-960.
GIRÃO, G., et al. Implementation of a HDTV transport stream multiplexer based on ITU-T
H.222.0 recommendation. In:
Proceedings of the 11th Brazilian Symposium on
Multimedia and the web. ACM: Poços de Caldas - Minas Gerais, Brazil. 2005.
_______.
Cache Coherency Communication Cost In A Noc-Based Mp-Soc Platform. 20th
Symposium on Integrated Circuits and Systems Design, Rio de Janeiro, 2007.
GLASS, C. J.; NI, L. M. The turn model for adaptive routing. ACM: 1992; Vol. 20, pp 278-
287.
HELMIG, J. Developing core software technologies for TI’s OMAPTM platform, Disponível
em: http://www.ti.com
. Acesso em: 20 jan. 2008
INTEL. Product Brief: Intel IXP2850 Network Processor, 2002. Disponível em:
www.intel.com/design/network/prodbrf/25213601.pdf
. Acesso em: 20 jan. 2008
KOVAC, M.; RANGANATHAN, N. J.
A Fully Pipelined VLSI Architecture for JPEG
Image Compression Standard. Proceedings of the IEEE, 1995; pp 247-258.
LEVINE, B. A.; SCHMIT, H. H. Efficient Application Representation for HASTE: Hybrid
Architectures with a Single, Transformable Executable. In:
Proceedings of the 11th Annual
IEEE Symposium on Field-Programmable Custom Computing Machines.
IEEE
Computer Society: 2003.
65
LI, M., et al. DyXY: a proximity congestion-aware deadlock-free dynamic routing method for
network on chip. In:
Proceedings of the 43rd annual conference on Design automation.
ACM: San Francisco, CA, USA. 2006.
MADEIRA, S.
Um Ambiente Baseado em Componentes para Desenvolvimento de
Softwares de Sistemas Embutidos. Dissertação de Mestrado, Universidade Federal de Santa
Catarina, Santa Catarina, 2004.
MELLO, A., et al. MultiNoC: A Multiprocessing System Enabled by a Network on Chip. In:
Proceedings of the conference on Design, Automation and Test in Europe - Volume 3.
IEEE Computer Society: 2005a.
MELLO, A. V.
Canais Virtuais em Redes Intra-Chip: Um Estudo de Caso. 44f. Trabalho
Individual I, Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre, 2005b.
OSCI. SystemC, 2005. Disponível em: http://www.systemc.org
. Acesso em: 20 jan. 2008
PATTERSON, D. A.; HENNESSY, J. L.
Computer Organization and Design:
hardware/software interface. Morgan Kaufmann: San Francisco, 1994.
PEREIRA, M. M.
Proposta e Implementação de uma Arquitetura Reconfigurável
Híbrida para Aplicações Baseadas em Fluxo de Dados. 79f. Dissertação Mestrado,
DIMAp, UFRN, Natal, 2008a.
PEREIRA, M. M., et al.
Using traditional loop unrolling to fit application on a new
hybrid reconfigurable architecture. 23rd Annual ACM Symposium on Applied Computing,
Fortaleza, 2008b.
PREISS, B. R.; HAMACHER, V. C.
Data Flow on Queue Machines. 12th Int. IEEE
Symposium on Computer Architecture, 1985; pp 342-351.
REGO, R. S. D. L. S.
Projeto e Implementação de uma Plataforma MP-SoC usando
SystemC
. 144f. Dissertação de Mestrado, Departamento de Informática e Matemática
Aplicada, Universidade Federal do Rio Grande do Norte, Natal, 2006.
RIJPKEMA, E., et al.
Router Architecture for Networks on Silicon. Proceedings of
Progress 2001, 2nd Workshop on Embedded Systems, Veldhoven, the Netherlands, 2001.
SARBAZI-AZAD, H., et al.
The Effect of the Number of Virtual Channels on the
Performance of Wormhole-Routed Mesh Interconnection Networks. Proceedings 16th
Annual UK Performance Engineering Workshop, 2000; pp 95-102.
SCHMIT, H., et al. Queue Machines: Hardware Compilation in Hardware. In:
Proceedings of
the 10th Annual IEEE Symposium on Field-Programmable Custom Computing
Machines. IEEE Computer Society: 2002.
SCHWIEBERT, L.; JAYASIMHA, D. N. Optimal fully adaptive wormhole routing for
meshes. In:
Proceedings of the 1993 ACM/IEEE conference on Supercomputing. ACM:
Portland, Oregon, United States. 1993.
66
SMELYANSKIY, M., et al. Register Queues: A New Hardware/Software Approach to
Efficient Software Pipelining. In:
Proceedings of the 2000 International Conference on
Parallel Architectures and Compilation Techniques. IEEE Computer Society: 2000.
SOARES, R., et al. When reconfigurable architecture meets network-on-chip. In:
Proceedings of the 17th symposium on Integrated circuits and system design. ACM:
Pernambuco, Brazil. 2004.
SOWA, M., et al. Parallel Queue Processor Architecture Based on Produced Order
Computation Model. Kluwer Academic Publishers: 2005; Vol. 32, pp 217-229.
TANENBAUM, A. S.
Distributed Operating Systems. 1 ed. Prentice-Hall International:
1995; p 648.
_______.
Organização Estruturada de Computadores. 5 ed. Pearson: 2006; p 464
TEDESCO, L. P.
Uma proposta para geração de tráfego e avaliação de desempenho para
NoCs. 126f. Mestrado, Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre,
2005.
WAWRZYNIAK, R.
Systems-on-a-chip: A brave new world. Semico Research
Corporation Report SC101-1-99, 1999.
WOLF, W. The future of multiprocessor systems-on-chips. In:
Proceedings of the 41st
annual conference on Design automation. ACM: San Diego, CA, USA. 2004.
ZEFERINO, C. A.
Redes-em-Chip: arquiteturas e modelos para avaliação de área e
desempenho. Dissertação de Mestrado, Universidade Federal do Rio Grande do Sul, Porto
Alegre, 2003.
ZEFERINO, C. A., et al.
ParIS: A Parameterizable Interconnect Switch for Networks-on-
Chip.
SBCCI'04, Pernambuco, 2004; pp 204-209.
67
Anexo I – Conjunto de Instruções do sistema IPNoSys
As instruções atuais foram incluídas à medida que as aplicações foram mapeadas. Esse
conjunto de instruções continuará evoluindo desta forma. Todas as instruções têm o seguinte
formato:
Onde:
•
INST (8 bits): identificador da instrução
•
#op (2 bits): quantidade de operandos
o “00”: nenhum operando
o “01”: um operando
o “10”: dois operandos
o “11”: mais de operandos, a quantidade é indicada em Result_2
•
Resultado_1 (11 bits): posição no pacote onde o resultado da instrução é inserido ou
coordenada do NAM que deve executar a instrução
•
Resultado_2 (11 bits): posição no pacote onde o resultado da instrução é inserido ou a
quantidade de operandos da instrução
•
operando_1 ... operando_n (32 bits cada): operandos da instrução
Instrução Descrição
#
operandos
Formato no
pacote
Significado
Onde é
executada
ADD
Adição de
inteiros
2
ADD | 2 | r1| r2
x
y
Adiciona x e y e insere o
resultado nas posições r1 e
r2 do mesmo pacote
Qualquer
UPR
SUB
Subtração de
inteiros
2
SUB| 2 | r1 | r2
x
y
Subtrai x e y e insere o
resultado nas posições r1 e
r2 do mesmo pacote
Qualquer
UPR
MUL
Multiplicação
de inteiros
2
MUL| 2| r1| r2
x
y
Multiplica x e y e insere o
resultado nas posições r1 e
r2 do mesmo pacote
Qualquer
UPR
DIV
Divisão de
inteiros
2
DIV| 2| r1| r2
x
y
Divide x por y e insere o
resultado nas posições r1 e
r2 do mesmo pacote
Qualquer
UPR
NOT
Negação
lógica
1
NOT| 1| r1| r2
x
Negação lógica de x e
insere o resultado nas
posições r1 e r2 do mesmo
pacote
Qualquer
UPR
AND E lógico 2
AND| 2| r1| r2
x
y
E lógico de x e y e insere o
resultado nas posições r1 e
r2 do mesmo pacote
Qualquer
UPR
OR OU lógico 2
OR| 2| r1| r2
x
y
OU lógico de x e y e insere
o resultado nas posições r1
e r2 do mesmo pacote
Qualquer
UPR
INST #op Resultado_1 Resultado_2
operando_1
operando_n
...
68
XOR OU exclusivo 2
XOR| 2| r1| r2
x
y
OU exclusivo de x e y e
insere o resultado nas
posições r1 e r2 do mesmo
pacote
Qualquer
UPR
RSHIFT
Deslocamento
à direita
2
RSHIFT| 2| r1| r2
x
y
Desloca x em y bits para
direita e insere o resultado
na posições r1 e r2 do
mesmo pacote
Qualquer
UPR
LSHIFT
Deslocamento
à esquerda
2
LSHIFT| 2| r1| r2
x
y
Desloca x em y bits para
esquerda e insere o
resultado na posições r1 e
r2 do mesmo pacote
Qualquer
UPR
BE
Desvia se
igual
2
BE | 2 | r1| 0
x
y
Se x é igual a y descarta
todas as palavras antes de
r1
Qualquer
UPR
BNE
Desvia se
diferente
2
BNE | 2 | r1| 0
x
y
Se x é diferente de y
descarta todas as palavras
antes de r1
Qualquer
UPR
BL
Desvia se
menor
2
BL | 2 | r1| 0
x
y
Se x é menor que y
descarta todas as palavras
antes de r1
Qualquer
UPR
BG
Desvia se
maior
2
BG | 2 | r1| 0
x
y
Se x é maior que y
descarta todas as palavras
antes de r1
Qualquer
UPR
BLE
Desvia se
menor ou igual
2
BLE | 2 | r1| 0
x
y
Se x é menor ou igual a y
descarta todas as palavras
antes de r1
Qualquer
UPR
BGE
Desvia se
maior ou igual
2
BGE | 2 | r1| 0
x
y
Se x é maior ou igual a y
descarta todas as palavras
antes de r1
Qualquer
UPR
JUMP
Desvio
incondicional
0 JUMP | 0 | r1| 0
Descarta todas as palavras
antes de r1
Qualquer
UPR
COPY Copia valor 1
COPY | 1 | r1| r2
x
Insere x nas posições r1 e
r2 no mesmo pacote
Qualquer
UPR
NOP
Nenhuma
operação
0 NOP| 0 | r1| r2
Não realiza nenhuma
operação
Qualquer
UPR
LOAD
Ler da
memória
1
LOAD| 1 | r1 | r2
x
Carrega da memória o
valor armazenado no
endereço x e insere o
resultado na posição r2
No NAM de
coordenada
r1
STORE
Escreve na
memória
n
STORE| 3 | r1 | r2
x
end_1
...
end_n
Escreve o valor x na
memória, nos endereços
end_1, ..., end_n. Quant.
de endereços indicada em
r2
No NAM de
coordenada
r1
EXEC
Execução
assíncrona
1
EXEC| 1 | r1 | 0
x
Ordena a injeção do pacote
x
No NAM de
coordenada
r1
SINEXEC
Execução
síncrona
n
SINEXEC | 3 | r1| r2
x
pac_1
...
pac_n
Ordena a injeção do pacote
x após sincronização dos
pacotes pac_1, ..., pac_n.
Quant. de pacote indicada
em r2
No NAM de
coordenada
r1
69
SINC Sincronização 1
SINC| 1 | r1 | 0
x
Sinal de sincronização do
pacote x
No NAM de
coordenada
r1
SEND Envia valor 2
SEND| 2 | r1 | r2
x
y
Envia o valor x para ser
inserido na palavra r2 do
pacote y.
No NAM de
coordenada
r1
70
Anexo II – Grafo de fluxo de dados da DCT-2D
Subgrafos que geraram cada pacote. Os subgrafos que geram os 4 pacotes de cálculo são
apresentados separadamente a seguir.
71
Subgrafo do primeiro pacote de cálculo
In[0] In[7]
In[1] In[6]
In[3] In[4]
In[2] In[5]
Out[0] Out[4]
B[5]
B[1]
B[4]
C[0]
C[3]
Store out[0]
Store out[4]
Subgrafo do segundo pacote de cálculo
72
Subgrafo do terceiro pacote de cálculo
73
Subgrafo do quarto pacote de cálculo
In[0] In[7]
In[1] In[6]
In[3] In[4]
In[2] In[5]
m1
m4
m2
B[7]
B[2]
B[3] B[6]
C[5]
C[2]
C[6]
E[3]
E[4]
F[4]
E[7]
F[7]
D[4]
Out[1] Out[7]
256
256
256
Store out[1]
Store out[7]
74
Anexo III – Relação entre os pacotes na DCT-2D sem laço de repetição
A relação entre os 80 pacotes que realizam o cálculo da DCT-2D de 1 bloco
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
