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 Computação
Mestrado Acadêmico em Sistemas e Computação
Otimização de Topologia Irregular Para
Aplicações Tempo Real e Não Tempo Real em
MP-SoCs Baseadas em Redes-em-Chip
Samuel da Silva Oliveira
Natal-RN
Dezembro de 2018
Samuel da Silva Oliveira
Otimização de Topologia Irregular Para Aplicações
Tempo Real e Não Tempo Real em MP-SoCs Baseadas
em Redes-em-Chip
Dissertação de Mestrado apresentada ao Pro-
grama 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 re-
quisito parcial para a obtenção do grau de
Mestre em Sistemas e Computação.
Linha de pesquisa:
Sistemas Integrados
Orientador
Prof. Dr. Márcio Eduardo Kreutz
PPgSC – Programa de Pós-Graduação em Sistemas e Computação
DIMAp – Departamento de Informática e Matemática Aplicada
CCET – Centro de Ciências Exatas e da Terra
UFRN – Universidade Federal do Rio Grande do Norte
Natal-RN
Dezembro / 2018
Oliveira, Samuel da Silva.
   Otimização de topologia irregular para aplicações tempo real
e não tempo real em MP-SoCs baseadas em redes-em-chip / Samuel
da Silva Oliveira. - 2018.
   104f.: il.
   Dissertação (Mestrado em Sistemas e Computação) -
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 Computação.
Natal, 2018.
   Orientador: Márcio Eduardo Kreutz.
   1. Computação - Dissertação. 2. Redes-em-chip - Dissertação.
3. Topologia irregular - Dissertação. 4. Exploração de espaço
projeto - Dissertação. I. Kreutz, Márcio Eduardo. II. Título.
RN/UF/CCET                                            CDU 004
Universidade Federal do Rio Grande do Norte - UFRN
Sistema de Bibliotecas - SISBI
Catalogação de Publicação na Fonte. UFRN - Biblioteca Setorial Prof. Ronaldo Xavier de Arruda - CCET
Elaborado por Joseneide Ferreira Dantas - CRB-15/324

Dedico este trabalho a minha família, em especial a meu pai Luiz, minha mãe Socorro e
minha esposa Jayne.
Agradecimentos
Ao longo dessa jornada turbulenta ocorreram vários problemas e tiveram momentos
difíceis que eu poderia ter desistido. Agradeço primeiramente a Deus que me deu ânimo,
sabedoria e forças para continuar. Aos meus pais por sempre acreditarem em mim e
saberem que eu era capaz. A minha esposa que me apoiou durante todo o percusso. Ao
professor Kreutz pela confiança e oportunidade que me concedeu em ser seu orientando.
As professoras Monica e Marjory pela paciência em me ouvir e me ajudar com ideias
e lições. Aos amigos Jefferson, Hiago, Raul e Adelino que sempre contribuíram no que
podiam e não me deixaram desanimar. Ao Eduardo que sempre respondia meus e-mails
e me socorria. A UFRN, DIMAp e ao LaSIC por me acolherem e cederem seus espaços
para estudos e pesquisas. Aos meus familiares e amigos que me acompanham e torciam
por mim, sou grato a todos vocês.
As pessoas que vencem neste mundo são as que procuram as circunstâncias de que
precisam e, quando não as encontram, as criam.
George Bernard Shaw
Otimização de Topologia Irregular Para Aplicações
Tempo Real e Não Tempo Real em MP-SoCs Baseadas
em Redes-em-Chip
Autor: Samuel da Silva Oliveira
Orientador(a): Prof. Dr. Márcio Eduardo Kreutz
Resumo
Com o avanço nas arquiteturas multiprocessadas as redes-em-chip se tornaram uma solu-
ção viável na etapa de comunicação das mesmas. Devido existirem vários tipos de arquite-
turas de comunicação entre as redes-em-chip, algumas usam topologias regulares, que são
mais comuns e fáceis de se projetar. Outras, no entanto preveem alguma irregularidade
nos padrões de comunicação, assim utilizam topologias irregulares. Uma boa exploração
de espaço de projeto pode levar a configurações mais otimizadas. Este trabalho propõe
uma rede com topologia irregular otimizada, onde a comunicação é baseada em tabelas de
roteamento e uma ferramenta que busca realizar essa exploração através de um Algoritmo
Genético. A rede proposta nesse trabalho apresenta roteadores heterogêneos (que podem
ajudar na otimização da rede) e oferece suporte a pacotes tempo real e não tempo real.
O objetivo principal desse trabalho consiste na proposta de uma exploração de espaço de
projeto que objetiva encontrar redes otimizadas para latência média, uma maior porcen-
tagem de pacotes tempo real entregues dentro do prazo estipulado e um ganho em área,
através da diminuição do número de roteadores.
Palavras-chave: Rede-em-Chip, Topologia Irregular, Exploração de Espaço Projeto.
Optimization of Irregular Topology for Real-Time and
No-Real-Time Applications in MP-SoCs Based on
Networks-on-Chip
Author: Samuel da Silva Oliveira
Supervisor: Prof. Dr. Márcio Eduardo Kreutz
Abstract
With the evolution of multiprocessing architectures, Networks-on-Chip (NoCs) have be-
come a viable solution for the communication subsystem. Since there are many possible
architectural implementations, some use regular topologies, which are more common and
easier to design. Others however, follow irregularities in the communication pattern, tur-
ning into irregular topologies. A good design space exploration can give us the configura-
tion with better performance among all architectural possibilities. This work proposes a
network with optimized irregular topology, where the communication is based on routing
tables and a tool that seeks to perform this exploration through a Genetic Algorithm.
The network proposed in this work presents heterogeneous routers (which can help with
network optimization) and supports real-time and non real- time packets. The goal of this
work is to find a network (or a set of networks), through the design space exploration,
that has the best average latency and the highest percentage of packets that meet their
deadlines.
Keywords : Network-on-Chip, Irregular Topology, Design Space Exploration.
Lista de figuras
1 Exemplo de um MP-SoC conectado através de uma NoC . . . . . . . . p. 23
2 Exemplo de uma arquitetura de roteador . . . . . . . . . . . . . . . . . p. 24
3 Formato de uma mensagem . . . . . . . . . . . . . . . . . . . . . . . . p. 25
4 Topologias Diretas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
5 Topologia Indireta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
6 Topologia Irregular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 28
7 Permutação dos Roteadores e Links na Aplicação (ABABEI, 2010) . . . p. 32
8 Etapa de Broadcasting nos Roteadores UTNoCs (MESQUITA et al., 2016) p. 33
9 Framework de Simulação IrNIRGAM (CHOUDHARY; GAUR; LAXMI, 2011) p. 34
10 Roteadores Rasoc (a), Tonga (b) e Mago (c) (KREUTZ et al., 2005b) . . p. 37
11 Modelo de Fluxograma de um Algoritmo Genético . . . . . . . . . . . . p. 47
12 Exemplo de um Cromossomo no Nosso GA . . . . . . . . . . . . . . . . p. 48
13 Exemplo de Recombinação Entre Cromossomos . . . . . . . . . . . . . p. 50
14 Exemplo de Mutação Entre Cromossomos . . . . . . . . . . . . . . . . p. 51
15 Exemplo de Uma Topologia Irregular Usando a Arquitetura Proposta . p. 52
16 Modelos de Roteadores Usados . . . . . . . . . . . . . . . . . . . . . . p. 54
17 Tabela de Roteamento do Roteador R2 . . . . . . . . . . . . . . . . . . p. 56
18 Preenchimento das Tabelas de Roteamento . . . . . . . . . . . . . . . . p. 57
19 Ferramentas de Tráfego e Simulação . . . . . . . . . . . . . . . . . . . . p. 59
20 Primeira Aplicação (a) e Segunda Aplicação (b) - 10 Tarefas . . . . . . p. 62
21 Terceira Aplicação (a) e Quarta Aplicação (b) - 10 Tarefas . . . . . . . p. 62
22 Gráfico com os valores comparativos de latência para um grafo com 10
aplicações e deadline longo . . . . . . . . . . . . . . . . . . . . . . . . . p. 64
23 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 10 aplicações e deadline longo . . . . . . . . . . . . . . . . . p. 64
24 Gráfico com os valores comparativos de area para um grafo com 10 apli-
cações e deadline longo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 65
25 Gráfico com os valores comparativos de latência para um grafo com 10
aplicações e deadline médio . . . . . . . . . . . . . . . . . . . . . . . . p. 67
26 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 10 aplicações e deadline médio . . . . . . . . . . . . . . . . . p. 67
27 Gráfico com os valores comparativos de área para um grafo com 10 apli-
cações e deadline médio . . . . . . . . . . . . . . . . . . . . . . . . . . p. 68
28 Gráfico com os valores comparativos de latência para um grafo com 10
aplicações e deadline curto . . . . . . . . . . . . . . . . . . . . . . . . . p. 70
29 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 10 aplicações e deadline curto . . . . . . . . . . . . . . . . . p. 70
30 Gráfico com os valores comparativos de área para um grafo com 10 apli-
cações e deadline curto . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
31 Primeira Aplicação (a) e Segunda Aplicação (b) - 15 Tarefas . . . . . . p. 72
32 Terceira Aplicação (a) e Quarta Aplicação (b) - 15 Tarefas . . . . . . . p. 73
33 Gráfico com os valores comparativos de latência para um grafo com 15
aplicações e deadline longo . . . . . . . . . . . . . . . . . . . . . . . . . p. 74
34 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 15 aplicações e deadline longo . . . . . . . . . . . . . . . . . p. 75
35 Gráfico com os valores comparativos de área para um grafo com 15 apli-
cações e deadline longo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 75
36 Gráfico com os valores comparativos de latência para um grafo com 15
aplicações e deadline médio . . . . . . . . . . . . . . . . . . . . . . . . p. 77
37 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 15 aplicações e deadline médio . . . . . . . . . . . . . . . . . p. 78
38 Gráfico com os valores comparativos de área para um grafo com 15 apli-
cações e deadline médio . . . . . . . . . . . . . . . . . . . . . . . . . . p. 78
39 Gráfico com os valores comparativos de latência para um grafo com 15
aplicações e deadline curto . . . . . . . . . . . . . . . . . . . . . . . . . p. 80
40 Gráfico com os valores comparativos de entrega de pacotes RT para um
grafo com 15 aplicações e deadline curto . . . . . . . . . . . . . . . . . p. 81
41 Gráfico com os valores comparativos de área para um grafo com 15 apli-
cações e deadline curto . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 81
42 Primeira Aplicação Otimizada - 10 Tarefas - Deadline Longo . . . . . . p. 92
43 Segunda Aplicação Otimizada - 10 Tarefas - Deadline Longo . . . . . . p. 93
44 Terceira Aplicação Otimizada - 10 Tarefas - Deadline Longo . . . . . . p. 93
45 Quarta Aplicação Otimizada - 10 Tarefas - Deadline Longo . . . . . . . p. 94
46 Primeira Aplicação Otimizada - 10 Tarefas - Deadline Médio . . . . . . p. 94
47 Segunda Aplicação Otimizada - 10 Tarefas - Deadline Médio . . . . . . p. 95
48 Terceira Aplicação Otimizada - 10 Tarefas - Deadline Médio . . . . . . p. 95
49 Quarta Aplicação Otimizada - 10 Tarefas - Deadline Médio . . . . . . . p. 96
50 Primeira Aplicação Otimizada - 10 Tarefas - Deadline Curto . . . . . . p. 96
51 Segunda Aplicação Otimizada - 10 Tarefas - Deadline Curto . . . . . . p. 97
52 Terceira Aplicação Otimizada - 10 Tarefas - Deadline Curto . . . . . . p. 97
53 Quarta Aplicação Otimizada - 10 Tarefas - Deadline Curto . . . . . . . p. 98
54 Primeira Aplicação Otimizada - 15 Tarefas - Deadline Longo . . . . . . p. 98
55 Segunda Aplicação Otimizada - 15 Tarefas - Deadline Longo . . . . . . p. 99
56 Terceira Aplicação Otimizada - 15 Tarefas - Deadline Longo . . . . . . p. 99
57 Quarta Aplicação Otimizada - 15 Tarefas - Deadline Longo . . . . . . . p. 100
58 Primeira Aplicação Otimizada - 15 Tarefas - Deadline Médio . . . . . . p. 100
59 Segunda Aplicação Otimizada - 15 Tarefas - Deadline Médio . . . . . . p. 101
60 Terceira Aplicação Otimizada - 15 Tarefas - Deadline Médio . . . . . . p. 101
61 Quarta Aplicação Otimizada - 15 Tarefas - Deadline Médio . . . . . . . p. 102
62 Primeira Aplicação Otimizada - 15 Tarefas - Deadline Curto . . . . . . p. 102
63 Segunda Aplicação Otimizada - 15 Tarefas - Deadline Curto . . . . . . p. 103
64 Terceira Aplicação Otimizada - 15 Tarefas - Deadline Curto . . . . . . p. 103
65 Quarta Aplicação Otimizada - 15 Tarefas - Deadline Curto . . . . . . . p. 104
Lista de tabelas
1 Trabalhos Relacionados x Métricas Utilizadas . . . . . . . . . . . . . . p. 44
2 Topologias Irregulares com 10 cores e Deadline Longo . . . . . . . . . . p. 63
3 Topologia Mesh 4x4 e Deadline Longo . . . . . . . . . . . . . . . . . . p. 63
4 Teste T - 10 Tarefas - Deadline Longo . . . . . . . . . . . . . . . . . . p. 63
5 Topologias Irregulares com 10 cores e Deadline Médio . . . . . . . . . . p. 66
6 Topologia Mesh 4x4 e Deadline Médio . . . . . . . . . . . . . . . . . . p. 66
7 Teste T - 10 Tarefas - Deadline Médio . . . . . . . . . . . . . . . . . . p. 67
8 Topologias Irregulares com 10 cores e Deadline Curto . . . . . . . . . . p. 69
9 Topologia Mesh 4x4 e Deadline Curto . . . . . . . . . . . . . . . . . . . p. 69
10 Teste T - 10 Tarefas - Deadline Curto . . . . . . . . . . . . . . . . . . . p. 70
11 Topologias Irregulares com 15 cores e Deadline Longo . . . . . . . . . . p. 73
12 Topologia Mesh 4x4 e Deadline Longo . . . . . . . . . . . . . . . . . . p. 74
13 Teste T - 15 Tarefas - Deadline Longo . . . . . . . . . . . . . . . . . . p. 74
14 Topologias Irregulares com 15 cores e Deadline Médio . . . . . . . . . . p. 77
15 Topologia Mesh 4x4 e Deadline Médio . . . . . . . . . . . . . . . . . . p. 77
16 Teste T - 15 Tarefas - Deadline Médio . . . . . . . . . . . . . . . . . . p. 77
17 Topologias Irregulares com 15 cores e Deadline Curto . . . . . . . . . . p. 80
18 Topologia Mesh 4x4 e Deadline Curto . . . . . . . . . . . . . . . . . . . p. 80
19 Teste T - 15 Tarefas - Deadline Curto . . . . . . . . . . . . . . . . . . . p. 80
Lista de abreviaturas e siglas
MP-SoC – Multiprocessor System-on-Chip
NoC – Network-on-Chip
DSE – Design Space Exploration
RT – Real-Time
No-RT – No Real-Time
GA – Genetic Algorithm
EP – Elemento de Processamento
SoC – System-on-Chip
SI – Sistema Integrado
I/O – Input/Output
RR – Round-Robin
FIFO – First In First Out
CF – Controle de FLuxo
CV – Canais Virtuais
CTG – Communication Task Graph
IP – Intellectual Property
UTNoC – Undefined Topology Network on Chip
RR – Round-Robin
SoCINhet – System-on-Chip Interconnection Network Heterogeneous
SoCIN – System-on-Chip Interconnection Network
RTNoC – Real-Time Network-on-Chip
DAS – Double Arbiter and Switching router
QoS – Quality of Service
NSGA-II – Non-dominated Sorting Genetic Algorithm II
RTL – Register Transfer Language
NS – Nanossegundos
TLM – Transaction Level Modeling
T1 – Roteadores do Tipo 1
T2 – Roteadores do Tipo 2
CI – Circuito Integrado
WiNoC – Wireless Network-on-Chip
Sumário
1 Introdução p. 18
1.1 Objetivos e Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . p. 19
1.2 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . p. 21
2 Referencial Teórico p. 22
2.1 Comunicação em MP-SoCs . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
2.2 Redes-em-Chip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
2.2.1 Comunicação em uma NoC . . . . . . . . . . . . . . . . . . . . p. 23
2.2.2 Arquitetura de uma NoC . . . . . . . . . . . . . . . . . . . . . . p. 26
2.3 Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 28
2.3.1 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3 Trabalhos Relacionados p. 31
3.1 Topologias Irregulares . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31
3.2 Redes-em-Chip Heterogêneas . . . . . . . . . . . . . . . . . . . . . . . . p. 35
3.3 Aplicações Com Tarefas Tempo Real . . . . . . . . . . . . . . . . . . . p. 38
3.4 Métodos de Avaliação em NoCs . . . . . . . . . . . . . . . . . . . . . . p. 40
4 Método Proposto p. 45
4.1 Métricas de Avaliação da Rede Proposta . . . . . . . . . . . . . . . . . p. 45
4.2 Exploração do Espaço Projeto . . . . . . . . . . . . . . . . . . . . . . . p. 46
5 Topologia Irregular Proposta p. 52
5.1 Roteadores Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53
5.2 Roteamento Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55
6 Resultados p. 58
6.1 Ferramenta de Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . p. 58
6.2 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
6.2.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
6.2.2 Testes Com 10 Tarefas - Deadline Longo . . . . . . . . . . . . . p. 62
6.2.3 Testes Com 10 Tarefas - Deadline Médio . . . . . . . . . . . . . p. 66
6.2.4 Testes Com 10 Tarefas - Deadline Curto . . . . . . . . . . . . . p. 69
6.2.5 Testes Com 15 Tarefas - Deadline Longo . . . . . . . . . . . . . p. 72
6.2.6 Testes Com 15 Tarefas - Deadline Médio . . . . . . . . . . . . . p. 76
6.2.7 Testes Com 15 Tarefas - Deadline Curto . . . . . . . . . . . . . p. 79
7 Considerações Finais p. 84
Referências p. 86
Apêndice A -- Topologias Irregulares Otimizadas p. 91
18
1 Introdução
Com o aumento crescente no número de transistores em uma mesma pastilha de silício
foi possível colocar vários processadores em um mesmo chip (ITRS, 2018), caracterizando
assim o que chamamos de sistemas em chip multiprocessados (Multiprocessor System-on-
Chip - MP-SoCs) . Esses sistemas demandam um processamento maior na comunicação,
devido ao número de cores que é utilizado no projeto. Barramento então passou a não
comportar o grande número de cores devido ao aumento do fio e com isso sua capacitância.
Redes-em-Chip (Networks-on-Chip - NoCs) (BENINI; MICHELI, 2002) foram pensadas
para suprir a comunicação em um MP-SoC. As NoCs são escaláveis e isso as tornam uma
solução mais apropriada.
As NoCs são compostas por roteadores que são dispostos em uma topologia, essa
topologia que caracteriza a rede (TOSUN; AR; OZDEMIR, 2012). As mensagens são trocadas
entre os roteadores a fim de se cumprir o percurso entre origem e destino. O modo como
os roteadores se interligam afeta diretamente o desempenho da rede (DAS et al., 2009),
já que os mesmos definem o caminho entre os cores fonte e destino dos pacotes, o que
pode causar um aumento na latência média. Topologias diferentes ocupam áreas diferentes
devido a forma como os roteadores estão dispostos.
Aplicações genéricas são comumente usadas em topologias regulares, devido a sua
natureza simples e fácil implementação. No entanto devido ao padrão de tráfego muitas
vezes alguns roteadores ficam em desuso, acarretando assim uma maior área e consumo de
energia desnecessário, influenciando assim o desempenho. Otimizações podem ser feitas
alterando a localização dos nodos fonte e destino da rede, tendo assim um melhor uso
dos roteadores, acarretando assim em uma menor latência média e consumo de energia.
Uma mudança de topologia também pode melhorar no uso da rede. Topologias irregulares
oferecem uma otimização em latência, área e potência (TOSUN; AR; OZDEMIR, 2012) já que
pode-se utilizar apenas os roteadores que necessários. Em tempo de projeto pode ser feita
uma exploração das possibilidades da localização dos roteadores dentro da topologia. Essa
exploração do espaço de projeto (DSE - Design Space Exploration) realiza uma busca
19
variando a quantidade de roteadores e posições dos nodos fonte e destino pode mostrar
valores que consigam economia de recursos e obter melhores resultados em relação as
métricas que estão sendo priorizadas. Para isso uma ferramenta em alto nível ajudaria
realizando essa exploração de espaço projeto.
1.1 Objetivos e Contribuições
Então é visto que uma busca no espaço de projeto é uma solução adequado a fim de
se otimizar a rede de acordo com as métricas estabelecidas e que topologias irregulares é
uma provável escolha para uma aplicação específica, pois esse tipo de topologia tende a
diminuir os custos em área e latência. Quando se é trabalhado com aplicações que conte-
nham tarefas de tempo real (Real-Time - RT) , a preocupação para que os pacotes com
essa característica cheguem ao seu destino dentro do prazo estipulado é bem maior, já
que o atraso pode acarretar grandes perdas para o funcionamento da aplicação. Diversas
técnicas podem ser usadas para conseguir alcançar esse objetivo de otimização de latên-
cia média e entrega dos pacotes tempo real no prazo. Uma forma de se fazer isso seria
adicionar prioridades aos pacotes RT, para que os mesmos possam ter uma certa prefe-
rência no momento de uma contenção do canal. O uso de uma arquitetura com roteadores
heterogêneos também pode ter um grande impacto na latência final, já que diferentes
tipos roteadores podem obter desempenhos diferentes e uma mescla nesses roteadores na
topologia pode nos dá um aumento de desempenho (KREUTZ et al., 2005b).
Em sua dissertação, Jonathan Mesquita demonstra que é possível gerar uma rede com
topologia irregular capaz de alcançar um desempenho em latência que seja otimizado (de-
sempenho próximo ao grafo de aplicação da rede). Em seu trabalho são utilizadas arquite-
turas homogêneas e apenas pacotes não tempo real (No-Real-Time - No-RT) (MESQUITA,
2016).
Dessa forma esse trabalho se propõe a responder a seguinte pergunta de pesquisa:
• É possível gerar uma rede irregular com melhor possível desempenho de latência
média, quando comparado a uma rede com topologia mesh, uma taxa de entrega de
pacotes tempo real dentro do prazo estipulado que seja mais próxima da totalidade
possível e conseguir um valor em área abaixo ao do grafo da aplicação?
Esse trabalho tem como proposta realizar uma exploração de espaço projeto para
encontrar um conjunto de topologias de redes irregulares otimizadas, a fim de obter um
20
bom desempenho para uma determinada aplicação específica. As redes irregulares aqui
propostas suportam aplicações com tarefas de tempo real e não tempo real. Objetiva-se
então, desenvolver um método para realizar a exploração da arquitetura, para encontrar
redes otimizadas para valores de latência média e pacotes tempo-real que consigam chegar
dentro do prazo estipulado. Além disso é buscada também uma diminuição da área das
redes, através da busca por topologias contendo o menor número de roteadores possível.
Para ajudar nessa tarefa algumas estratégias foram adotadas, como o uso de arquiteturas
com roteadores heterogêneos, onde os mesmos estão em função de melhorar o desempenho
da NoC (CARDOSO et al., 2005); pacotes RT com prioridades, assim em um tráfego muito
alto, os pacotes RT teriam prioridade a passar na porta de um roteador, por exemplo;
canais virtuais preemptivos que ajudariam no tráfego da rede A otimização em si fica por
conta de um algoritmo genético (Genetic Algorithm - GA) . Esse algoritmo recebe como
entrada os valores de latência, deadline e quantidade de roteadores e então o posiciona-
mento e o número dos roteadores são alterados, colocando-se em alguns roteadores mais
de um core associado, para gerar novas redes otimizadas. Esse procedimento é repetido
algumas vezes, até que o algoritmo genético forme uma população e dela crie novos des-
cendentes com novos valores de simulação. O procedimento continua a se repetir até uma
condição de parada ser dada e o algoritmo obter o melhor conjunto de redes irregulares,
dadas as métricas escolhidas para otimização. Topologias irregulares não usam métodos
comuns de roteamento devido a sua natureza arquitetural, portanto nesse trabalho foi
usada uma forma de tabelas de roteamento que ajuda na comunicação entre os roteado-
res, onde cada roteador tem uma tabela armazenada que informa a que distância estão
os outros roteadores da rede.
Para realizar a exploração no espaço de projeto foi usado um algoritmo genético
como heurística. O GA possibilita o percurso no projeto, selecionando as redes irregulares
através das métricas escolhidas e ao mesmo tempo realiza eventuais otimizações. O GA
é portátil e é separado da representação do problema (SOUZA, 2008), o tornando assim
uma boa escolha para esse trabalho.
Para esse trabalho foi desenvolvida uma ferramenta de simulação em SystemC (SYS-
TEMC, 2018). A ferramenta simula as características de uma NoC irregular com seus
padrões de tráfego e gera um resultado com a latência média, porcentagem dos pacotes
entregues dentro do deadline e a quantidade de roteadores utilizados. Foi desenvolvido um
algoritmo genético para ser usado como heurística e realizar a otimização das topologias
irregulares aqui utilizadas.
21
1.2 Organização do trabalho
Os capítulos seguintes desse trabalho estão organizados da seguinte forma: no próximo
capítulo será apresentado alguns conceitos de redes-em-chip, a fim que possa-se entender
melhor como funciona uma NoC e espera-se compreender mais adequadamente as técni-
cas empregadas nesse trabalho e como foi implementada a a rede utilizada nesse projeto.
No terceiro capítulo serão vistos alguns trabalhos que se relacionam com esse, para que
possa-se ver o que tem sido estudado na área. Os trabalhos relacionados se dividem em
três categorias: os trabalhos sobre topologias irregulares, os trabalhos sobre arquiteturas
heterogêneas e os trabalhos sobre aplicações com tarefas tempo real. O quarto capítulo
trata das métricas de avaliações em uma NoC e modos de otimização das mesmas. Nesse
capítulo serão vistos técnicas que podem ser empregadas para melhorar o desempenho
em uma NoC e o funcionamento do GA que é utilizado como forma de heurística nessa
pesquisa, a fim de melhorar o desempenho da rede. O quinto capítulo descreve o funcio-
namento da arquitetura aqui proposta e o funcionamento da rede. Nesse capítulo pode-se
ter uma ideia geral da metodologia usada para a implementação das redes e escolha das
mesmas, também se têm uma boa visão do funcionamento da comunicação dentro da
rede. No sexto capítulo pode-se encontrar alguns resultados preliminares. Esses resulta-
dos foram feitos em uma versão inferior a versão final de como ficará a ferramenta de
simulação. Esses experimentos são feitos tendo como base uma arquitetura puramente
homogênea e conta apenas com pacotes de tempo real. E por último o sétimo capítulo
trata da conclusão e do cronograma das atividades que ainda faltam ser executadas.
22
2 Referencial Teórico
Este capítulo aborda os fundamentos sobre as tecnologias estudadas e apresentadas
nesse trabalho. Abaixo seguem-se concentos que vão desde a explicação de como funci-
ona a comunicação entre os elementos de processamento, até a forma como será feita a
otimização da rede com o uso de heurísticas.
2.1 Comunicação em MP-SoCs
Diversos elementos de processamento (EP) tem sido adicionados a SoCs (System-on-
Chips) (AGARWAL; ISKANDER; SHANKAR, 2009), devido a uma maior integração desses
EPs em uma pastilha de silício e a diminuição do tamanho do transistor (ZEFERINO,
2003). Com isso têm-se o que chamamos de MP-SoCs. Atualmente em um único chip
pode-se ter diversos componentes, como: processadores, memórias, dispositivos de I/O,
etc.
O barramento que até então realizava a comunicação entre esses EPs tornou-se não
tão eficiente, já que o mesmo possui um limite de elementos que podem ser conectados
a ele. Segundo (COTA; AMORY; LUBASZEWSKI, 2011), os barramentos não atendem o de-
sempenho necessário para muitas aplicações e também não fornece a largura de banda,
latência e consumo de energia que são necessários. Portanto, uma nova arquitetura de
comunicação se faz necessária para atender essa demanda de aplicações. As NoCs são ar-
quiteturas escaláveis e reutilizáveis, portanto apresentam vantagens sobre os barramentos
e são uma boa escolha para projetos com MP-SoCs.
2.2 Redes-em-Chip
A figura 1 mostra um exemplo de uma NoC fazendo a comunicação de um MP-SoC.
Uma NoC é composta por um conjunto de roteadores conectados ponto a ponto de forma
que estejam em algum tipo de topologia. Esses roteadores são conectados por sua vez a
23
Figura 1: Exemplo de um MP-SoC conectado através de uma NoC
cores em um sistema integrado (SI) , como dispositivos de entrada e saída (I/O) , memó-
rias, processadores, etc. Esses cores se comunicam entre si trocando mensagens através
dos roteadores. Os roteadores recebem as mensagens do core a que estão interconectados
e as roteiam até chegar no roteador ligado ao core destino das mensagens. (ZEFERINO et
al., 2007) fala que dentre as vantagens da NoC, há duas que tem destaque em relação ao
barramento: o crescimento da largura de banda de acordo com aumento do número de
EPs, enquanto a do barramento é fixa. A outra vantagem é o paralelismo na comunica-
ção que o barramento não oferece, o que gera uma grande diferença na latência média
final. Outras vantagens da NoC são: compartilhamento de fios, possibilitando assim uma
utilização mais eficiente e diminuição da área consumida (BOLOTIN et al., 2004), (DALLY;
TOWLES, 2004); confiabilidade devido a diversas técnicas que podem ser utilizadas que
permitem esse aumento de confiabilidade (VELLANKI; BANERJEE; CHATHA, 2004); e reuso
devido a sua modularização, assim pode-se aproveitar a estrutura de comunicação e os
cores existentes para outra aplicação (BENINI; MICHELI, 2002).
2.2.1 Comunicação em uma NoC
Na figura 2 é mostrado um exemplo do funcionamento interno de um roteador de NoC.
O roteador é o componente responsável por fazer as ligações entre os cores e também
realizar o roteamento das mensagens, para que as mesmas cheguem nos seus destinos
(AGARWAL; ISKANDER; SHANKAR, 2009). Um roteador é composto por um conjunto de
portas de entrada e saída por onde os pacotes trafegam. Existe também uma porta que
é chamada de local, no qual essa porta é a responsável direto pela conexão do core ao
roteador. Essas portas são interligadas internamente por um crossbar, que nada mais é que
24
Figura 2: Exemplo de uma arquitetura de roteador
um núcleo de chaveamento (COTA; AMORY; LUBASZEWSKI, 2011). Como pode ser visto
na figura abaixo, cada porta de entrada é conectada em todas as portas de saída, exceto
na sua própria. O roteador tem como função principal o roteamento dos pacotes que saem
de um core fonte e são enviadas através dos roteadores e enlaces até o core destino. Esse
roteamento é possível através de um algoritmo que lê informações contidas no cabeçalho
do pacote, assim escolhendo uma porta de saída do roteador, para que o pacote possa então
seguir por um caminho até chegar ao core desejado. O algoritmo deve tentar prever e/ou
evitar deadlock e liveloock (ZEFERINO, 2003). O roteamento pode ser determinístico ou
adaptável. Roteamento determinístico é quando os pacotes já saem do roteador sabendo
todo o seu percusso o que ajuda a prevenir deadlock e liveloock. Roteamento adaptável é
quando o pacote vai tomando a decisão de por onde seguir à medida que vai passando de
roteador em roteador, isso pode ser útil em caso de congestionamento da rede.
As mensagens podem ser divididas em pacotes, o que por sua vez podem ser divididos
em flits (MATOS, 2010), como a figura 3 abaixo mostra. O chaveamento é responsável
direto pelo modo que as mensagens serão enviadas pela rede. O chaveamento pode ser
25
Figura 3: Formato de uma mensagem
de dois tipos: no chaveamento por circuito, um caminho dedicado é aberto do roteador
fonte até o destino, assim fazendo que a mensagem percorra esse caminho sem nenhum
desvio e que pacote chegue íntegro até a sua meta. Nesse modelo pode haver um aumento
na latência devido a outra mensagem precisar passar por um roteador que está alocado e
ter que esperar até ficar livre (COTA; AMORY; LUBASZEWSKI, 2011); no chaveamento por
pacote cada pacote é então roteado passando pelos roteadores sem existir a necessidade
da alocação do caminho. Os pacotes podem então tomar caminhos diferentes, dependendo
do algoritmo de roteamento implementado. Nesse caso que não existe um caminho pré
definido e reserva de recursos, um maior uso da rede se torna possível (CARDOSO et al.,
2005). Esse modo de chaveamento possibilita uma latência média menor, já que se é feito
um melhor uso do paralelismo da NoC. Esse modelo de comunicação se assemelha as
redes de computadores, onde as mensagens são transformadas em pacotes e são enviadas
através de um meio de comunicação, tendo uma preocupação com o congestionamento da
rede e integridade do pacote ao chegar no destino.
A arbitragem lida com conflitos internos do roteador. Quando mais de uma porta de
entrada quer enviar um pacote ao mesmo tempo pela mesma porta de saída, é o árbitro
quem decide de quem é a vez de enviar o pacote. Cada porta pode ter o seu árbitro (dis-
tribuído) ou termos um único árbitro por roteador (centralizado). As prioridades podem
ser estáticas e cada porta ter uma prioridade diferente ou pode ser algo dinâmico em que
as prioridades de cada porta variem de acordo com um certo período de tempo (COTA;
AMORY; LUBASZEWSKI, 2011). A exemplo temos a arbitragem do tipo Round-Robin (RR)
, que pode ser chamado de árbitro justo. Esse modelo de arbitragem escolhe uma porta na
rodada para ser a que tem maior prioridade, depois de um período de tempo essa maior
26
prioridade é passada para a porta seguinte e esse ciclo continua infinitamente.
A memorização se dá por buffers ligados as portas de entrada do roteador. Quando
o fluxo de pacotes chegando é muito alto e não dá para alocar esses pacotes nas por-
tas de saída em tempo hábil, esses buffers armazenam os pacotes até eles poderem ser
encaminhados. Geralmente os buffers utilizam modelo FIFO (First In First Out) , onde
o primeiro pacote a entrar é o primeiro a sair. O tamanho e o número de buffers em
uma NoC pode afetar diretamente o desempenho da rede, pode beneficiar na questão do
tráfego e também pode consumir uma área maior ((COTA; AMORY; LUBASZEWSKI, 2011).
O controle de fluxo (CF) tem como objetivo definir como os recursos de rede serão
alocados. Decisões sobre saber de antemão se o canal que irá receber o pacote está livre
ou não é trabalho do controle de fluxo, tentando assim garantir uma melhor performance.
O CF pode ser centralizado ou distribuído. No centralizado as decisões de roteamento são
tomadas globalmente e aplicadas a todos os roteadores. No modo distribuído as decisões
são tomadas em cada roteador individualmente (COTA; AMORY; LUBASZEWSKI, 2011).
Canais virtuais (CV) também é uma técnica de CF. O CV combina técnicas de CF
baseado em créditos e memorização multi-via. Cada canal físico é compartilhado por
vários canais lógicos. Esse compartilhamento ocorre usando multiplexação de tempo. O
objetivo desses canais virtuais é melhorar o desempenho da rede, evitar os deadlocks e
garantir um tráfego seguro (BJERREGAARD; MAHADEVAN, 2006).
2.2.2 Arquitetura de uma NoC
As topologias são parte importante nas NoCs. As topologias definem como os rotea-
dores estão fisicamente interconectados. Os roteadores podem ser representados por um
grafo G = (R,C), onde R é o conjunto de roteadores e C o conjunto dos canais de comuni-
cação. As topologias afetam diretamente o desempenho da rede e também pode interferir
no tipo de roteamento a ser escolhido (DAS et al., 2009), (MATOS, 2010). As topologias
podem ser divididas em diretas e indiretas (JUNIOR, 2010).
Na figura 4 acima pode-se ver alguns exemplos de topologias diretas: (a) Mesh-2D;
(b) Torus; (c) Hipercubo. As topologias diretas são caracterizadas por cada roteador ser
conectado ao EP, constituindo assim um nodo.
Na figura 5 é mostrado um exemplo de topologia indireta, a chamada Árvore Gorda(ZEFERINO,
2003). Nesse tipo de topologia os EPs são ligados apenas há alguns roteadores e esses ro-
teadores são conectados com outros a fim de cada EP consiga enviar mensagem para
27
Figura 4: Topologias Diretas
Figura 5: Topologia Indireta
qualquer outro EP na rede.
As topologias regulares possuem padrões de conexão já definidos entre os roteadores
da rede (DUATO; YALAMANCHILI; NI, 2003). Como as conexões entre os roteadores já é
pré-definida, o endereço desses roteadores podem ser dados por coordenadas. As topolo-
gias regulares são de fácil implementação e reutilizáveis devido a sua estrutura. Diversos
tipos de aplicações podem ser utilizadas com essas topologias. Mas, dada uma aplicação
específica essas topologias podem não ser tão otimizadas, pois o grafo da aplicação pode
conter menos cores que a topologia tem de roteadores. Mesmo os roteadores podendo ser
desligados, ainda sim estarão ocupando área no chip (TOSUN; AR; OZDEMIR, 2012).
Topologias irregulares podem prover essa otimização para aplicações específicas de-
vido à natureza arquitetural desse tipo de topologia. Os roteadores apresentam padrões
diferentes de conexões, assim uma topologia irregular é mais viável para uma aplicação
específica (PASRICHA; DUTT, 2010), como pode ser vista na figura 6.
As topologias irregulares permitem a otimização em latência, área e potência. Dessa
forma essas topologias são um grande objeto de pesquisas na academia e também na
indústria (TOSUN; AR; OZDEMIR, 2012), (OZTURK; DEMIRBAS, 2010). A topologia irregular
28
Figura 6: Topologia Irregular
tem um consegue obter melhores resultados de desempenho para aplicações específicas,
caso a aplicação seja mudada o desempenho pode não ser o mesmo, além disso ela não é
escalável.
2.3 Heurísticas
A exploração do espaço do projeto é uma importante fase para se conseguir redes
que sejam otimizadas para alguma métrica buscada. No entanto, como se trata de um
problema de otimização NP-Completo o uso de heurísticas ajuda na busca exaustiva por
uma solução que seja a mais aceitável para o projeto.
Métodos heurísticos são algoritmos que buscam resolver problemas de forma explo-
ratória. Uma solução ótima nem sempre é alvo desses métodos, podendo apenas visarem
uma solução que seja a mais viável para o problema. Essa característica tem como base a
inteligência humana (BUENO, 2009).
Existem diversos tipos de heurísticas que podem realizar o reagrupamento dos ro-
teadores para achar uma topologia que seja mais adequada ao problema abordado. As
heurísticas podem ser divididas nos seguintes grupos:
• heurísticas de construção: são aquelas soluções que são construídas elemento a ele-
mento, que segue um critério de otimização até achar uma solução que seja viável;
• heurísticas de busca de vizinhança: são as quais partem necessariamente de uma
solução que é inicialmente viável e tenta melhorar essa solução através de troca até
que não seja mais possível haver uma melhorias ou uma condição de parada ser
29
atingida;
• heurísticas sistemáticas: são aquelas que as soluções são percorridas utilizando cri-
térios de ramificação e corte da árvore;
• heurísticas híbridas: é a combinação de duas ou mais heurísticas que tenham estra-
tégias diferentes;
• meta-heurísticas: são heurísticas genéricas que são mais sofisticadas, onde uma heu-
rística é gerenciada por algum tipo de procedimento que inteligentemente visa ex-
plorar o campo de soluções.
Para esse trabalho foram então analisados diversos tipos de heurísticas e o Algoritmo
Genético foi escolhido por ser fácil implementação e poder ser separado do problema, o
que o torna portátil.
2.3.1 Algoritmo Genético
Algoritmo genético é uma técnica de heurística que foi desenvolvida na década de
70 por Holland (HOLLAND, 1992). O algoritmo foi desenvolvido baseado na teoria da
evolução de Charles Darwin. Seguindo os mesmos princípios da teoria de Darwin, os
algoritmos genéticos começam com uma população que competem entre si para então
serem gerados descendentes, esses descendentes sofrem algum tipo de mutação e assim vai
seguindo, para que os cromossomos melhorados possam passar através dos descendentes
até formarem uma população otimizada para um dado problema.
Os GA tem algumas características que são um pouco peculiares em relação a outros
métodos de buscas já existentes:
• são baseados em um conjunto de soluções possíveis;
• não envolvem modelagem do problema;
• o algoritmo apresenta como resultado uma população de soluções;
• trata-se de um método probabilístico.
O GA também possui algumas terminologias que são emprestadas da biologia, tais
como:
30
• população: conjunto de cromossomos ou possíveis soluções;
• cromossomo ou indivíduo: conjunto de genes que representa uma solução para o
problema;
• gene: menor unidade de informação do cromossomo;
• cruzamento: processo de reprodução sexuada em que combinam-se genes de dois
cromossomos para formar um novo indivíduo; mutação: anomalias que causam al-
teração aleatória nos genes;
• geração: iteração do algoritmo genético;
• aptidão ou fitness: indicador qualitativo do indivíduo;
• função objetivo: é a função matemática que avalia o cromossomo em relação ao
problema.
31
3 Trabalhos Relacionados
O estudo sobre topologias irregulares tem tido um crescimento, devido a sua capaci-
dade de otimização. Muitos pesquisadores têm tratado de vários temas relevantes, como
síntese, otimização, roteamento, exploração de espaço e projeto. Neste capítulo serão vis-
tos alguns trabalhos da literatura que tratam sobre síntese e otimização de topologias
irregulares. Também serão abordados nesse capítulo trabalhos que contemplam arquite-
turas heterogêneas de rede e que suportam aplicações com tarefas de tempo real.
3.1 Topologias Irregulares
(ABABEI, 2010) propõe sintetizar uma topologia customizada de uma NoC através
de floorplaning. A síntese é feita usando um simulador programado através da linguagem
C++. O simulador suporta roteadores com um número arbitrário de portas e canais
virtuais. As topologias são verificadas usando precisão de ciclos. Um grafo das tarefas e
comunicações é dado (Communication Task Graph - CTG) e uma floorplan inicial. O
objetivo é gerar M floorplans diferentes a fim de obter melhores resultados de latência
e área. A alocação dos IP/cores para os roteadores é feita para cada floorplan. Quatro
roteadores são colocados nos cantos de cada core. Essa atribuição é feita usando um
algoritmo de correspondência e um grafo bipartido que utiliza dois conjuntos de nós: os
nós que representam os cores da aplicação e os nós que representam os roteadores. Os
IP(Intellectual Property) ou cores são ligados aos roteadores e a criação dos links é feita.
A medida que os que o simulador vai otimizando os floorplans, os links dos roteadores são
removidos, assim também diminuindo o número de portas e a área ocupada. O roteamento
é realizado por tabelas dentro de cada roteador. Após toda a estruturação dos links dos
roteadores, os caminhos de roteamento são calculados e armazenados nas tabelas de cada
roteador. Os experimentos foram feitos usando algumas aplicações variando os números
de cores e a taxa de injeção. Os resultados se mostram satisfatórios quando comparados
com uma topologia regular Mesh. A figura 7 mostra como é realizada a alocação dos
32
roteadores e links e também a otimização dos números de links.
Figura 7: Permutação dos Roteadores e Links na Aplicação (ABABEI, 2010)
As tarefas do grafo são divididas através de um algoritmo de correspondência e um
grafo bipartido, onde cada tarefa é alocada a quatro roteadores, um roteador para cada
canto depois que a tarefa for alocada em uma floorplan. Os links então são montados e
depois reduzidos a fim de uma otimização na área.
A rede chamada UTNoC (Undefined Topology Network on Chip) proposta por (MES-
QUITA et al., 2016) possui uma topologia irregular e cada roteador pode se conectar com
qualquer outro na rede. Cada roteador pode se ligar a apenas um core. O roteamento é
realizado através de tabelas dentro de cada roteador. Cada roteador só tem conhecimento
prévio dos roteadores ligados diretamente a eles, então para a realização da comunicação
integral entre todos os roteadores, cada roteador envia uma mensagem de broadcasting
enviando as informações do roteador de origem, a fim de montar a tabela de roteamento
de cada roteador, contendo a distância de cada roteador que compõe a rede. A figura 8
mostra como funciona a etapa de broadcasting na rede UTNoC. Os roteadores da rede
UTNoC podem ter um número variado de portas, já que cada roteador pode se ligar a
um número variado de roteadores.
Cada roteador envia uma mensagem de broadcasting, essa mensagem é então passada
por todos os outros roteadores e à medida que eles vão recebendo essa mensagem, é feita
uma leitura de um campo que contabiliza por quantos roteadores a mensagem passou
desde a origem, assim então é possível montar uma tabela dentro de cada roteador con-
tendo o nome dos outros roteadores e quantos saltos são necessários para chegar nesses
33
Figura 8: Etapa de Broadcasting nos Roteadores UTNoCs (MESQUITA et al., 2016)
roteadores.
Os experimentos executados tomando como base a rede UTNoC foram rodados em um
simulador desenvolvido em SystemC. A ferramenta de simulação também conta com o uso
de um algoritmo genético para percorrer o espaço de busca procurando redes UTNoCs.
As instâncias da rede são criadas através dos parâmetros da aplicação que são passados
como entrada na ferramenta. As redes têm o comportamento de comunicação simulados
e a latência média é retornada, esse resultado de latência é devolvido a ferramenta de ex-
ploração. Esse valor é usado pelo algoritmo genético para assim escolher novos indivíduos.
A topologia irregular da UTNoC toma como base uma topologia da rede regular Mesh
e são retirados links a fim de otimizar a rede em relação a latência média e obter um
desempenho bem próximo ao do CTG da aplicação. Os experimentos foram executados
em 4 aplicações com taxas de injeções variadas. Os resultados alcançados mostram que é
possível obter uma topologia irregular com um desempenho próximo ao grafo da aplica-
ção, com uma redução no número de conexões e apenas um pequeno aumento na latência
média. Quando comparado a uma Mesh a taxa de latência é bem menor. Diferente do
proposto neste trabalho, onde são considerados roteadores heterogêneos e pacotes RT.
IrNIRGAM é um framework baseado no NIRGAM que oferece suporte a topologias
irregulares que é desenvolvido usando SystemC e C++ para simular o desempenho de uma
34
NoC irregular, que faz a utilização de canais virtuais, arbitragem Round-Robin (RR) e
roteamento baseado em tabelas. A topologia é direta, então cada IP/Core é conetado
diretamente a um único roteador. (CHOUDHARY; GAUR; LAXMI, 2011) apresenta a ferra-
menta IrNIRGAM para simular o comportamento de NoCs com topologias irregulares.
A ferramenta suporta diversas topologias e algoritmos de roteamento e gera como saída
resultados de latência. Parâmetros como topologia, tipo do roteamento, tráfego dos pa-
cotes, dentre outros, são passados ao simulador através de arquivos de configuração. A
ferramenta também pode gerar gráficos das saídas da simulação. A figura 9 mostra como
funciona o framework IrNIRGAM. O IrNIRGAM recebe como entrada um arquivo de con-
figuração, onde é feita a escolha da topologia. Também como entrada é tida a aplicação
específica e o padrão de tráfego. Depois disso o simulador com essas informações realiza
os testes e gera os resultados esperados e também faz a síntese da rede.
Figura 9: Framework de Simulação IrNIRGAM (CHOUDHARY; GAUR; LAXMI, 2011)
Quanto aos experimentos, foram gerados um conjunto de topologias irregulares para
aplicações específicas. A injeção dos flits é feita a cada dois ciclos de clock, mantendo assim
esse intervalo do ínicio ao fim da simulação. As simulações foram realizadas utilizando
10000 ciclos. As comparações de resultados foram feitas em cima de uma Mesh 2D. São
usadas aplicações que tem entre 16 e 81 cores. Os resultados de latência na topologia
irregular têm uma taxa de 9,4 a 18,4 ciclos contra 13,2 a 69 ciclos da Mesh. No quesito
de consumo de energia temos 18,5% a 25,8% da topologia irregular contra 24,6% a 53%
da rede Mesh.
35
(TOSUN; AR; OZDEMIR, 2012) buscando minimizar o consumo de energia e a latência na
comunicação dos pacotes, para isso ele cria topologias irregulares através de dois métodos
distintos. O primeiro método usado é dividido em duas etapas. A primeira parte procura
decompor o grafo da aplicação que é dado em cluster e baseado no grafo da aplicação,
na melhor forma possível e cada core é associado a um roteador. A segunda parte do
primeiro método busca conectar todos os roteadores em uma topologia que possa ter
os menores custos de comunicação. O outro método utiliza um algoritmo genético que
recebe uma aplicação e gera várias soluções de redes. Essas soluções são dadas através de
operadores do algoritmo genético. No final o algoritmo genético retorna a melhor rede,
com os menores custos de comunicação e com a menor quantidade de roteadores possíveis.
Depois que as redes irregulares são criadas, é realizado o floorplaning da rede, com isso é
observado o consumo de energia da rede e os custos de comunicação, a partir daí a melhor
rede é escolhida. Os resultados dos experimentos desse trabalho mostram que a segunda
técnica tem melhores resultados que a primeira.
(MILFONT et al., 2017) procura avaliar restrições de caminhos em topologias irregulares,
através do uso de uma ferramenta que visa garantir o deadlock free e gera métricas para
analisar e avaliar em tempo de projeto a qualidade do roteamento. É utilizado um modelo
de falha para gerar topologias com links falhos, o que permite explorar a manufatura em
cenários usando tecnologia CMOS de 65nm e 22nm, a partir da variabilidade do atraso
de links e da força de correlação espacial. É também usado um algoritmo de segmentação
para diminuir a distância média entre as falhas na topologia. Os resultados experimentais
mostram que a porcentagem de falhas aumenta de forma significativa com a força de
correlação espacial, enquanto a distância entre falhas diminui. Também quanto maior a
porcentagem de falha, maior a distância média de roteamento.
3.2 Redes-em-Chip Heterogêneas
Redes-em-Chip podem ser uma ótima solução para um SoC devido ao seu alto desem-
penho causado pelo paralelismo na comunicação. Entretanto, esse paralelismo demanda
uma quantidade maior de elementos (roteadores) para ajudar na comunicação entre os
cores e com isso têm-se um bom aumento na área do SoC. (CARDOSO et al., 2005) propõe
uma solução envolvendo roteadores de tamanhos heterogêneos, para assim minimizar os
custos em área. A rede considerada compreende um trade-off entre latência e área, bus-
cando assim reduzir a área e manter o desempenho da rede. A rede proposta é chamada
de SoCINhet (System-on-Chip Interconnection Network Heterogeneous) e é baseada na
36
rede SoCIN (System-on-Chip Interconnection Network) (ZEFERINO; SUSIN, 2003). A rede
desenvolvida por (CARDOSO et al., 2005) utiliza dois tipos de roteadores Rasoc (ZEFERINO;
SUSIN, 2003) e Tonga (CARDOZO et al., 2004). O roteador Rasoc tem desempenho melhor
quando comparado ao Tonga, mas ocupa mais área, portanto uma mescla desses dois
roteadores em uma rede pode acarretar em um bom balanço entre área e desempenho. O
roteador Rasoc é compatível com as topologias Mesh e Torus e pode ter até 5 portas bi-
direcionais. Usa roteamento XY, árbitro RR e buffers FIFO. O roteador Tonga é baseado
no Rasoc, a diferença entre eles está na interconexão interna das portas. Na figura 10a e
10b podem ser vistos os roteadores Rasoc e Tonga respectivamente.
Pelos resultados alcançados na sintetização dos roteadores, o roteador Tonga teve
aproximadamente 40% menos área que o roteador Rasoc. A otimização na rede é feita
usando a Busca-Tabu como heurística para percorrer o espaço de busca do projeto a
fim de encontrar melhores resultados de área e latência mesclando o uso dos dois tipos
de roteadores. A rede resultante é uma rede Mesh, devido à natureza arquitetural dos
roteadores. As redes usadas nos experimentos foram descritas em C++ e simuladas em
um simulador descrito em SystemC. Foram usadas redes de tamanhos até 10x10 e os
resultados obtidos mostram uma redução na área de até 35%, conseguindo manter o
desempenho da rede.
(KREUTZ et al., 2005b) também aborda a criação de NoCs usando roteadores hetero-
gêneos, a fim de otimizar a latência e consumo de energia. Um algoritmo de otimização é
empregado para poder posicionar os roteadores da melhor forma possível e poder alcançar
os resultados desejados. É usado o padrão de comunicação da aplicação para ajudar na
busca do melhor posicionamento dos roteadores em relação aos cores, assim permitindo a
avaliação de latência e consumo de energia para diferentes topologias de NoC. (KREUTZ
et al., 2005b) também usa a rede SoCINhet. Além dos roteadores Rasoc e Toga, o roteador
Mago também é utilizado nesse trabalho. O roteador Mago é dentre os três o que tem
melhores valores de aŕea, enquanto o Rasoc mostra um desempenho melhor. A figura 10
mostra como funcionam os roteadores Rasoc, Tonga e Mago.
O roteador Rasoc é um roteador mais comum, o mesmo contém 4 portas para conexões
para outros roteadores e uma porta local, o que aumenta a sua eficiência em desempenho,
mas dá um bom aumento na área do projeto. O roteador Tonga utiliza dois multiplexa-
dores, um para cada duas portas, assim perde-se um pouco no desempenho, mas ganha-se
uma redução em área. O último roteador é o Mago que utiliza um único multiplexador
para as quatro portas de entrada. O ganho em área é muito maior se comparado ao Rasoc,
37
Figura 10: Roteadores Rasoc (a), Tonga (b) e Mago (c) (KREUTZ et al., 2005b)
mas em questão de desempenho as perdas são grandes. Desse modo o Tonga fica como
meio termo entre os três roteadores.
O uso combinado desses três tipos de roteadores na rede e o uso da Busca-Tabu para
a realização da otimização da mesma, consegue gerar um trade-off entre latência média
e consumo de energia. Dada uma aplicação específica e um CTG é feita uma busca pelo
espaço do projeto. Essa busca é feita através de um algoritmo de otimização chamado
Busca-Tabu. A permuta dos roteadores é então testada para serem achados os melhores
resultados para o problema em questão. A busca é então feita levando em consideração
a latência ou consumo de energia como prioridade, assim o algoritmo leva essa métrica
em consideração e devolve uma solução que mostre uma rede otimizada para a prioridade
escolhida. Quando a diminuição de energia é priorizada, a rede é inicialmente composta
por roteadores Mago, já que os mesmos têm as melhores taxas de energia. Caso os valores
de latência não sejam alcançados, alguns roteadores então são trocados a fim de atingir
38
os resultados esperados. Quando a prioridade é latência, a rede inicialmente começa com
todos os roteadores sendo do tipo Rasoc, já que o Rasoc tem melhores valores de latência
média. Caso os resultados para consumo de energia não sejam os esperados, então são
trocados alguns roteadores e acrescentados os outros dois tipos, para assim chegarem aos
valores ideais de energia.
Os roteadores usados no trabalho foram descritos em C++, e foram usados em um
simulador compilado em código C++. Os resultados alcançados foram satisfatórios e
mostram que é possível conseguir um trade-off entre latência média e consumo de energia
para redes com arquiteturas diferentes de roteadores. Os resultados mostram que em uma
rede heterogênea o consumo de energia e a latência conseguem ser menores que em uma
rede homogênea.
(BEN-ITZHAK et al., 2015) apresenta uma nova arquitetura de NoC que utiliza também
roteadores heterogêneos. Esses modelos de roteadores suportam diferentes larguras de
banda e têm números diferentes de canais virtuais por cada porta. Os roteadores utilizam
buffers compartilhados e tem como vantagens desacoplamentos de largura de banda de
entrada e saída, também apresenta um melhor desempenho quando se é comparado a
uma arquitetura de roteador de buffer de entrada. (BEN-ITZHAK et al., 2015) também
introduzem e comprovam formalmente uma nova abordagem que reduz o número médio
de buffers compartilhados que são necessários, sem assim comprometer o desempenho
do roteador. Quando é comparado com um roteador homogêneo com buffer de entrada,
o roteador proposto por (BEN-ITZHAK et al., 2015) consegue melhorar a saturação da
taxa de transferência de 6% a 47% para padrões de tráfego padrão. O roteador também,
atinge uma melhoria significativa no tempo de execução. Também é oferecida uma melhor
escalabilidade, redução de área e energia de 15% a 60% para NoCs com tamanhos entre
4x4 e 16x16.
3.3 Aplicações Com Tarefas Tempo Real
Aplicações com tarefas tempo real demandam um cuidado maior na hora de projetar
a rede-em-chip, já que as mensagens trafegadas tem um prazo de tempo para chegarem
ao destinatário.
Quando se é falado de aplicações de tempo real, pode-se dividir em duas categorias:
hard real time e software real time. A primeira categoria implica que não pode haver algum
atraso na entrega do pacote, o que pode ocasionar um erro fatal no uso do sistema, como
39
por exemplo o atraso no acionamento do airbag de um automóvel. A segunda categoria
aceita atraso na entrega do pacote, esse atraso pode trazer mal funcionamento do sistema,
mas é algo que é aceitável, como por exemplo o atraso do áudio em uma transmissão de
vídeo.
Para essa pesquisa será adotado o uso de aplicações que sejam hard real time.
(SAYUTI; INDRUSIAK, 2013) em seu trabalho propõe uma rede para otimização do
consumo de energia sem sacrificar o tempo de entrega das mensagens. Essa otimização é
feita usando um algoritmo genético, onde os cromossomos desenvolvidos representam a
alocação das tarefas para os cores da aplicação. Esses cromossomos são guiados por uma
função multi-objetiva que combina macro modelos de consumo de energia e análise de
tempo de entrega das mensagens. Os prazos de deadline são bem precisos e um pequeno
atraso pode ser considerado como um descarte total do pacote.
A rede utilizada por (SHI, 2009) é uma NoC homogênea, usando comutação por pacotes
do tipo wormhole e cada core pode executar mais de uma tarefa e usam arbitragem com
prioridade preemptiva. O roteamento usado é do tipo determinístico e canais virtuais com
prioridade preemptiva. O algoritmo genético usado tem como função principal otimizar
a rede, para isso o GA conta com duas funções fitness que buscam encontrar alocações
melhores de tarefas que possam atender as restrições de uma aplicação RT e também
minimizar a dissipação de energia. Os melhores descendentes da população gerada são
escolhidos por torneio e esses são os aptos a gerarem uma nova população.
Duas aplicações de benchmark foram usadas para a realização dos experimentos. Um
deles é baseado em um veículo autônomo realista e consiste em 33 tarefas e 39 mensagens.
O segundo benchmark é baseado em uma aplicação sintética que é constituída de 50
tarefas RT e 50 mensagens RT. Foram usadas redes Mesh-2D 4x4 e 5x5, roteamento XY
e buffers de duas posições por canais virtuais. Para as aplicações testadas o algoritmo
genético conseguiu otimizar as especificações da NoC, de modo que foi possível diminuir
o consumo de energia e manter as restrições de tempo real para as aplicações usadas.
(LV et al., 2008) propõe um simulador que para NoC com comunicações de tempo
real (RTNoC) . O simulador em questão utiliza comutação de pacotes do tipo wormhole.
A ferramenta também é usada para avaliar o desempenho de diversos algoritmos de es-
calonamento para um conjunto de tarefas de tempo real. A topologia escolhida para os
experimentos foi a Mesh-2D pela sua fácil implementação e por ser uma das topologias
mais utilizadas em projetos de redes-em-chip. O roteamento empregado é o XY, onde
primeiro é percorrida a linha e depois a coluna, trançando uma rota do nodo origem
40
até o nodo destino. Os tempos que levam enviando e recebendo pacotes são calculados
dentro do tempo da tarefa. Um conjunto de tarefas são consideradas desejáveis se todas
elas chegam ao destino dentro do prazo estipulado, portanto eles entendem que a tarefa é
escalável. O RTNoC é um simulador de tempo discreto, o tempo avança um intervalo fixo
para cada nova etapa da simulação. A ferramenta de simulação é implementada no Visual
C++ 6.0. O conjunto de tarefas pode ser inserido manualmente ou gerado pelo RTNoC.
A simulação é executada em segundo plano e retorna se a rede é ou não escalonável.
Para os experimentos são gerados 100 conjuntos de tarefas, cada conjunto contendo no
máximo 6 tarefas. Os resultados mostram que a ferramenta de simulação RTNoC é uma
boa ferramenta para simulação de redes que fazem uso de aplicações de tempo real.
(DRIDI et al., 2017) propõe um novo roteador de canal virtual projetado para sistemas
de criticidade mista implantada nas NoCs. O objetivo principal desse roteador é reduzir o
tempo de latência de pior caso na comunicação de sistemas altamente críticos. O segundo
objetivo é melhorar a taxa de utilização da rede e reduzir a latência de comunicação para
fluxos de baixa importância. O roteador proposto é chamado DAS (Double Arbiter and
Switching router) usa as técnicas Wormhole e Store and Forward de forma conjunta para
se adaptar a fluxos não críticos e críticos, respectivamente. Simulações com precisão de
ciclo feitas em SystemC mostram uma taxa de uso da rede de 15%, o atraso na comuni-
cação muita crítica caiu em 80% e o atraso na comunicação não crítica teve um aumento
de 18%, quando comparado a roteadores que usam vários canais virtuais.
3.4 Métodos de Avaliação em NoCs
O uso de redes-em-chips pode ser uma ótima escolha para uso em diversos tipos
de MP-SoCs. Devido a sua natureza, as NoCs concedem grandes vantagens no que diz
respeito a latência, devido ao uso de paralelismo na comunicação, também tem a questão
do reuso de uma mesma NoC para outra aplicação e também a escalabilidade. No entanto
devido ao uso de roteadores a área ocupada pela aplicação é bem maior do que seria se o
barramento fosse usado. O consumo de energia em uma NoC também é maior, já que cada
roteador usado também tem um consumo de energia atrelado a ele. Por isso os projetistas
buscam através de diversas técnicas otimizar a rede segundo algumas métricas desejadas,
assim a rede teria um custo aceitável. Um exemplo seria a otimização de uma rede para
diminuir a área usada, onde a área é uma restrição maior de projeto.
(CORRÊA, 2007) fala que para se cumprir as restrições para NoCs RT dentro do
41
deadline esperado, algumas adaptações devem ser feitas a fim de otimizar a rede, e buscado
manter o desempenho da rede, ao mesmo tempo garantindo a qualidade de serviço (QoS –
Quality of Service) e os deadlines para os pacotes tempo real. A exploração do espaço de
projeto é então feita no nível mais alto de abstração, dessa forma é esperado manter o nível
do projeto e realizar uma busca mais ampla e rápida. Nessa exploração a configuração da
rede tem impacto direto na QoS e nos requisitos temporais. Seu trabalho é baseado na
rede SoCIN, a topologia utilizada é a Mesh-2D, o roteamento é o XY e o chaveamento é
o por pacotes do tipo wormhole. As métricas utilizadas na avaliação de desempenho da
rede foram a arbitragem, a memorização e o controle de fluxo. (CORRÊA, 2007) também
menciona que uma abordagem de permutação dos cores de acordo com a largura de
banda que as mensagens exigem pode ser uma forma de evitar que os pacotes cheguem
fora do deadline. As estratégias utilizadas objetivavam permitir o uso mínimo dos recursos,
para assim atender os requisitos das aplicações RT dentro das exigências da QoS. Como
resultado pode-se ver que as escolhas nos parâmetros da rede tem impacto no desempenho
da aplicação, diminuindo os pacotes que não chegam dentro do prazo de entrega, assim
melhorando a latência e também o consumo de energia.
(BRUCH, 2015) também usa aplicações de tempo real em sua pesquisa e ele busca uma
garantia que esses pacotes RT sejam entregues dentro do tempo de deadline previsto. Para
isso é feito uso de canais virtuais e atribuídos níveis de prioridade para cada pacote. Assim
cada roteador além dos buffers padrões de armazenamento também conta com alguns CV
preemptivos, onde os pacotes RT que tem uma prioridade maior passam a frente dos
pacotes com prioridades mais baixas, dessa forma é garantida uma melhor entrega nesses
pacotes e uma quantidade de deadlines perdidos menores. Na pesquisa do (BRUCH, 2015)
o foco é achar um trade-off entre garantia de prazos, consumo de energia e a quantidade
de canais virtuais utilizados, já que quanto mais canais, mais consumo de energia. Para
isso é usada uma heurística para realizar a alocação de tarefas multiobjetivo baseada no
algoritmo genético NSGA-II Non-dominated Sorting Genetic Algorithm II . A heurística
foi utilizada na identificação de alocações que venham a apresentar um bom compromisso
entre garantia de prazos, consumo de energia e quantidade de canais virtuais que são
utilizados pela arquitetura de comunicação. Nos resultados é visto que a heurística foi
capaz de encontrar alocações com 99,9% de pacotes entregues dentro do prazo. As soluções
de energia estão diretamente ligadas ao número de canais virtuais. As melhores alocações
em quesito de energia eram os que não apresentavam canais virtuais, mas esses apresentam
as maiores perdas nos prazos.
(MURALI; BENINI; MICHELI, 2005) apresentam uma ferramenta chamada SUNMAP,
42
essa ferramenta é capaz de realizar a alocação das tarefas para uma aplicação específica
em uma NoC. A SUNMAP trabalha com diversos tipos de topologias, como topologias
diretas e indiretas, entre elas podemos destacar, Mesh, Torus, Hypercube e. Butterfly. A
ferramenta também conta com vários tipos de roteamento: caminho mínimo, divisão de
tráfego, dimensão ordenada. A SUNMAP também conta com uma heurística de busca
tabu, que tem uma função multi-objetiva que engloba atraso de comunicação média, área
e consumo de energia. A ferramenta recebe como entrada as métricas desejadas, para em
cima disso escolher a melhor topologia. Tais métricas podem ser: minimizar o atraso na
comunicação, área, dissipação de energia, largura de banda, etc. No processo de alocação
são usados alguns modelos de tráfego, como abstração da comunicação entre os cores. O
projeto pode também ser gerado em SystemC, assim podem ser simulados para verificação
se todas as restrições foram atendidas. O objetivo principal da ferramenta é escolher a
melhor topologia para uma dada aplicação e com isso realizar a alocação das tarefas para
rede.
(CARVALHO, 2009) foca na alocação e otimização de MP-SoCs heterogêneos usando
redes-em-chip. O trabalho faz uma investigação e avaliação do desempenho de heurísticas
para a realização da alocação dinâmico de tarefas, com o principal objetivo de minimizar
os congestionamentos que acontecem na comunicação de uma NoC. As tarefas são aloca-
das de acordo com os tráfegos de comunicação e as requisições e ocupações dos canais da
NoC. São utilizadas técnicas de algoritmos gulosos na alocação e as tarefas são alocadas
uma por vez. Então a decisão é baseada na informação local da aplicação, que são apenas
relacionadas a tarefa requisitada. Através dos experimentos realizados com base na mo-
delagem do sistema em um nível RTL (Register Transfer Language) , pode-se então obter
uma redução de até 31% nas cargas dos canais de comunicação, 15% na latência média e
de até 78% nos níveis médios de congestionamento da rede.
A tabela 1 elenca todos os pontos abordados nesse trabalho e relaciona com todos os
trabalhos relacionados apresentados nesse capítulo. Diferente do que foi visto em todos
esses trabalhos relacionados, essa pesquisa abordará estratégias que contará com NoCs de
topologia irregular, e também será feito uso de pacotes tempo real e não tempo real. O
intuito desta pesquisa é o desenvolvimento de uma ferramenta para exploração de espaço
e projeto, para a otimização de topologias irregulares e a diminuição dos custos de latência
média, quantidade dos pacotes tempo real que são entregues fora do prazo. Ao mesmo
tempo que se tem um foque nessas métricas é visado também reduzir a área do chip, para
que que essa área fique a menor possível, respeitando as restrições de projeto. O uso do
algoritmo genético como heurística ajuda a conseguir esses objetivos através da geração
43
de várias permutações da rede e da diminuição do número de roteadores, alocando mais
de um core por roteador, conseguindo assim, uma redução de área.
44
Ta
be
la
1:
Tr
ab
al
ho
s
R
el
ac
io
na
do
s
x
M
ét
ri
ca
s
U
ti
liz
ad
as
Tr
ab
al
ho
s/
M
ét
ri
ca
s
D
SE
To
po
lo
gi
a
Ir
re
gu
la
r
La
tê
nc
ia
M
éd
ia
R
ot
ea
do
re
s
H
et
er
og
ên
eo
s
P
ac
ot
es
R
T
Á
re
a
(
A
B
A
B
E
I
,2
01
0)
X
X
X
(
M
E
SQ
U
IT
A
et
al
.,
20
16
)
X
X
X
(
C
H
O
U
D
H
A
R
Y
;G
A
U
R
;L
A
X
M
I
,2
01
1)
X
X
(
T
O
SU
N
;A
R
;O
ZD
E
M
IR
,2
01
2)
X
X
X
(
M
IL
FO
N
T
et
al
.,
20
17
)
X
(
C
A
R
D
O
SO
et
al
.,
20
05
)
X
X
X
X
(
K
R
E
U
T
Z
et
al
.,
20
05
b)
X
X
X
X
(B
E
N
-I
T
ZH
A
K
et
al
.,
20
15
)
X
X
(
SA
Y
U
T
I;
IN
D
R
U
SI
A
K
,2
01
3)
X
X
(
SH
I
,2
00
9)
X
X
(
LV
et
al
.,
20
08
)
X
(
D
R
ID
I
et
al
.,
20
17
)
X
X
(
C
O
R
R
Ê
A
,2
00
7)
X
X
(
B
R
U
C
H
,2
01
5)
X
X
(
M
U
R
A
LI
;B
E
N
IN
I;
M
IC
H
E
LI
,2
00
5)
X
X
X
(
C
A
RV
A
LH
O
,2
00
9)
X
X
X
E
st
e
Tr
ab
al
ho
X
X
X
X
X
X
45
4 Método Proposto
Esse capítulo aborda como é realizada a avaliação da rede aqui proposta. Será mos-
trada a metodologia e o funcionamento da heurística de otimização da rede, que busca
encontrar soluções para a aplicação específica de acordo com a métricas escolhidas.
4.1 Métricas de Avaliação da Rede Proposta
Uma rede-em-chip é uma arquitetura de comunicação capaz de enviar e receber men-
sagens entre os cores de uma determinada aplicação. O principal objetivo de uma NoC é
garantir que todas essas mensagens sejam entregues, assim o sistema pode se comportar
da maneira esperada (RIJPKEMA et al., 2003). Para aplicações com tarefas tempo real essa
preocupação é ainda maior, já que muitas vezes a integridade do sistema depende que to-
das as mensagens RT cheguem aos seus destinos dentro do prazo. Portanto a avaliação de
desempenho de uma rede consiste em verificar se a mesma atende os requisitos necessários
quanto a latência e vazão.
Neste trabalho pretende-se avaliar a latência média da rede, a porcentagem de pacotes
RT que conseguem chegar ao seu destino dentro do deadline e a diminuição da área através
da redução do número de roteadores. Para se calcular a porcentagem RT que conseguiram
chegar ao destino foi implementado um contador em cada porta local, que fica responsável
por contabilizar os pacotes tempo real que chegam ao seu destino. Assim que um pacote RT
chega o contador é incrementado e no final se tem a quantidade de pacotes que chegaram
dentro do prazo estipulado, esse valor é comparado com a quantidade de pacotes enviados
e então é feito o cálculo da porcentagem dos pacotes RT entregues. A área nesse trabalho
será calculada através do número de roteadores. Como a simulação é realizada em SystemC
TLM, não se tem os valores exatos de tamanho para cada roteador e seus componentes.
Por isso é optado calcular a área somando cada unidade de roteador presente na topologia.
A latência basicamente é a quantidade de tempo gasta que um pacote leva para chegar
ao seu destino. Geralmente o valor da latência é calculado em cima dos ciclos de clock
46
que são gastos para um pacote percorrer seu caminho até chegar no destino esperado
(DUATO; YALAMANCHILI; NI, 2003). Para esse trabalho esse valor de latência será medido
em nanossegundos (NS) .
A latência de um pacote individualmente não causa grandes mudanças na rede como
um todo. Por isso quando se é falado em latência de uma rede, geralmente se é referido
a latência média da mesma. Essa latência média é mais significativa para a avaliação do
desempenho da rede (DUATO; YALAMANCHILI; NI, 2003). A latência média pode então
ser obtida através da soma da latência de cada pacote trafegado na rede e dividido pelo
número total de pacotes. Abaixo pode-se ver melhor como essa relação funciona.
Latência Média =
No de Pctes∑
i=1
Latência do Pcte
No de Pctes
Nesse trabalho são usadas topologias irregulares, objetivando-se otimizar a rede e
também o desempenho referente a latência média. São usados também roteadores hete-
rogêneos para melhorar a rede proposta aqui, já que diversos tipos de roteadores podem
contribuir para a melhora da latência e área (KREUTZ et al., 2005b). Em relação aos dea-
dlines das mensagens RT, técnicas como canais virtuais e prioridades diferenciadas podem
ajudar a ter uma melhor performance e evitar deadlines perdidos.
4.2 Exploração do Espaço Projeto
A exploração do espaço e projeto nesse trabalho é feita através de um algoritmo
genético. Dada uma aplicação específica e um conjunto de topologias irregulares iniciais,
o GA busca então alterar a permutação dos roteadores dentro da rede e gerar o melhor
conjunto de topologias otimizadas. Para realizar essa otimização o GA leva em conta os
valores de latência média, porcentagem de pacotes que conseguiram atingir o deadline e
a quantidade de roteadores presentes na topologia. A figura 11 através de fluxograma nos
mostra como funciona um algoritmo genético.
O algoritmo genético inicia com uma geração zero, apenas com uma população inicial.
Essa população é então avaliada através de uma função fitness. A avaliação é feita através
das métricas propostas, que são latência média, porcentagem do deadline dos pacotes RT
e o número de roteadores. É atribuída então uma aptidão a cada indivíduo da população e
são escolhidos os melhores para se reproduzirem. Essa escolha é realizada tomando como
métrica principal a quantidade de pacotes RT que cumpriram o deadline, depois são
47
Figura 11: Modelo de Fluxograma de um Algoritmo Genético
observados a latência média e quantidade de roteadores presentes na topologia. Estando
escolhidos, é então feito o cruzamento trocando informações genéticas dos cromossomos.
Depois da nova população ter sido gerada uma mutação é aplicada nessa população. O
número de geração é então incrementado e tudo é repetido até uma condição de parada
ser atingida.
Um cromossomo que é utilizado no algoritmo genético representa uma solução para o
problema. A representação desse cromossomo depende do problema abordado e também
do que se deseja manipular geneticamente (PACHECO et al., 1999). No caso desse trabalho,
um cromossomo seria a representação de uma ligação entre os roteadores para uma rede
irregular, ou seja, basicamente a forma como os roteadores estão interligados fisicamente.
O cromossomo é uma representação de ligação entre os roteadores da rede, então o
cromossomo representa como os roteadores estão ligados entre si. Na figura 12 pode ser
48
Figura 12: Exemplo de um Cromossomo no Nosso GA
visto então um cromossomo com duas fileiras, cada fileira contém os roteadores presentes
na rede e a ligação entre esses roteadores é realizada entre um roteador e o que está
diretamente abaixo dele na outra fileira. Dessa forma os roteadores que não possuírem
ligação entre si, para se comunicar com os outros roteadores é preciso então encaminhar as
mensagens para os roteadores no qual eles se conectam e esses por sua vez enviam até que
as mensagens cheguem no destino final. A população inicial é criada de forma aleatória
e começa com um roteador para cada core no grafo da aplicação e então a função fitness
avalia a rede de acordo com a latência média e deadline. O algoritmo genético fiscaliza se as
topologias criadas são válidas, ou seja, se cada roteador pode se comunicar com qualquer
outro na topologia e também um mesmo roteador só pode aparecer no máximo 4 vezes no
cromossomo, já que um roteador pode se conectar no máximo com outros quatro. O GA
vai então retirando roteadores da topologia para então otimizá-la em espaço. As novas
gerações de topologias vão sendo testadas a fim de encontrar uma topologia que atenda
aos requisitos de latência, área e deadline. Abaixo pode-se ver a relação quanto ao número
de roteadores dentro da topologia.
bN
o de Cores
2
c ≤ No de Roteadores ≤ No de Cores
O número de roteadores na topologia utilizada aqui, tem então no máximo o mesmo
número de cores da aplicação e no mínimo o piso do número total de cores da aplicação
sobre dois. Inicialmente cada roteador começa com um core associado a ele, então o
algoritmo genético vai retirando roteadores a fim de diminuir a área. No final a topologia
pode ficar com até metade dos roteadores, visto que um número menor de roteadores
poderia comprometer a performance de latência média e deadline dos pacotes RT. Então
a cada execução completa de avaliação do GA um roteador é decrementado da topologia e
a avaliação começa novamente. Esse processo se repete até chegar na quantidade mínima
de roteadores. Dessa forma cada roteador terá no máximo dois cores associados a eles, o
que acarretará em uma redução na área, sem comprometer tanto o desempenho de latência
e deadline. Cada core é ligado na porta local de um roteador, quando é então realizada a
49
redução no número de roteadores, os cores que eram associados a eles são ligados em outros
roteadores, fazendo com que um roteador venha a ter mais de um core conectado a ele.
Cada roteador pode ter um número variado de portas, tendo como limite máximo 4 portas.
Dessa forma pode-se dizer que na rede utilizada aqui, cada roteador tem no máximo ligação
direta com outros quatro. O algoritmo genético também é responsável por mesclar os tipos
de roteadores usados na topologia. Inicialmente a topologia começa utilizando apenas um
tipo de roteador, a cada simulação vão sendo testadas diferentes combinações entre os
tipos de roteadores, para se verificar se houve aumento na performance, esperando assim
se conseguir resultados mais otimizados de simulações.
Depois de todos os indivíduos da população inicial serem testados e terem uma aptidão
atribuída a eles, é então escolhido os indivíduos com os melhores níveis de aptidão a fim
de ser realizado o cruzamento. O cruzamento é realizado através da geração de uma string
de bits aleatórios que variam entre 0 e 1, essa string tem o mesmo tamanho que os pais.
São então gerados dois filhos, o primeiro filho é feito utilizando as posições com valor 1
na primeira linha da string de bits e substituindo pelo número correspondente da mesma
posição do primeiro pai. O restante da fileira que contém valores 0 são substituídos pelos
valores da mesma posição da primeira linha do segundo pai. Para preencher a segunda
linha do primeiro filho é feito o inversão. Os valores que contém 1 são substituídos pelos
valores da mesma posição da segunda linha do segundo pai e os valores restantes são
trocados pelo equivalente da segunda linha do primeiro pai. O segundo filho é gerado de
forma inversa, assim não se corre o risco de repetir conexões já testadas. Na figura 13
abaixo pode ser visto como funcionar uma operação de crossover em nossos cromossomos.
Alguns indivíduos da nova população criada podem então sofrer o que é chamado de
mutação. A mutação nada mais é do que alteração nas características dos cromossomos, a
fim de aumentar a sua diversidade. Esses indivíduos que sofrem mutação são geralmente
uma porcentagem bem pequena e são escolhidos aleatoriamente. Existem diversas formas
de se realizar essa mutação, nesse trabalho será usada a abordagem de troca de genes
(PACHECO et al., 1999). Na etapa de mutação é então trocada o primeiro roteador da
fileira de cima pelo o último da mesma fileira. A figura 14 exemplifica como essa troca é
realizada no processo de mutação.
Como se é visto na figura 14, é feita uma permuta entre o primeiro roteador da
primeira fileira pelo último, alterando assim a conexão entre dois pares de roteadores.
Para finalizar são escolhidos os indivíduos que continuarão a fazer parte da popula-
ção e os que serão eliminados. Nesse trabalho é utilizado o método do elitismo, onde os
50
Figura 13: Exemplo de Recombinação Entre Cromossomos
indivíduos mais aptos são mantidos e os menos aptos são descartados. Esses seres serão
simulados novamente e gerarão uma nova população. Esse procedimento se repete até
uma condição de parada ser atendida.
51
Figura 14: Exemplo de Mutação Entre Cromossomos
52
5 Topologia Irregular Proposta
Uma topologia irregular nada mais é do que uma topologia sem um padrão definido
de interconexão entre os roteadores. Dessa forma em uma topologia irregular cada rote-
ador pode se conectar com qualquer outro roteador dentro da topologia. Contando com
essa irregularidade na topologia pode-se então conseguir desempenhos melhores do que
topologias regulares, para certas aplicações. Nesse capítulo será abordado a forma como
a topologia irregular usada nesse trabalho funciona. Na figura 15 temos um exemplo de
uma topologia irregular usando a arquitetura proposta aqui.
Figura 15: Exemplo de Uma Topologia Irregular Usando a Arquitetura Proposta
53
5.1 Roteadores Propostos
A arquitetura proposta aqui prevê o uso de mais de um core por roteador, de forma que
possa-se obter uma economia na área total ocupada pelo chip. Inicialmente a arquitetura
começa usando um roteador para cada core no grafo da aplicação. Com o uso do do
algoritmo genético o número de roteadores é decrementado e nos roteadores restantes são
adicionados os cores da aplicação de forma que um roteador receba mais de um core, dessa
forma a topologia consegue comportar todos os cores em um número menor de roteadores.
Cada roteador tem um número variado de portas, podendo ter até 4 portas para
comunicação com os demais roteadores e uma porta local para se comunicar com o core
da aplicação. Quando o GA faz a diminuição no número de roteadores e aloca mais de um
core por roteador, é então criada uma outra porta local e alocada ao novo core. Usando
esse método pode-se alocar até dois cores por roteador e são usadas no máximo 4 ligações
de roteador com roteador.
Nessa arquitetura como é disposto o uso de topologia irregulares, técnicas comuns
de roteamento não se aplicam. Então os algoritmos muito usados como o XY, YX, West
First não podem ser aproveitados para o nosso caso. Então foi proposta uma abordagem
de roteamento baseado em tabelas. Cada roteador utiliza uma tabela de roteamento que
contém as informações sobre as posições dos outros roteadores dentro da topologia. O
árbitro utilizado é o Round-Robin, o chaveamento é o Wormhole, o controle de fluxo é o
Handshake.
É proposto nesse trabalho o uso de roteadores heterogêneos para se tentar minimizar
os custos de latência e tentar garantir que os pacotes RT consigam chegar ao seu des-
tino dentro do prazo estabelecido. Então são utilizados 2 tipos de roteadores na nossa
arquitetura. Na figura 16 pode-se ver os roteadores que serão utilizados.
São usados dois tipos de roteadores. Um tipo de roteador simples (figura 16.a) que
tem até 4 portas para comunicação com outros roteadores e uma porta local, um árbitro
centralizado, uma tabela de roteamento e um algoritmo de roteamento. O segundo mo-
delo de roteador (figura 16.b) também faz uso da técnica de controle de fluxo de canais
virtuais. Esse modelo usa dois CVs preemptivos por cada canal físico em cada porta de
entrada do roteador, um árbitro centralizado, uma tabela de roteamento e um algoritmo
de roteamento. O primeiro modelo de roteador que não contém canais virtuais leva 8 ciclos
para atravessar um pacote. O segundo modelo de roteador, que contém canais virtuais
preemptivos leva 3 ciclos para atravessar um pacote.
54
Figura 16: Modelos de Roteadores Usados
A topologia começa usando apenas o primeiro modelo de roteador e à medida que o GA
vai otimizando a topologia, roteadores do segundo tipo são adicionados e com isso forma-se
uma topologia com roteadores mesclados. Os roteadores têm pesos diferentes, já que uns
55
ocupam mais área que outros. É importante levar em consideração o peso dos roteadores
quando se é calculada a área final da rede. Os pacotes RT gerados pela aplicação específica
têm uma prioridade maior em relação aos pacotes comuns que circulam pela rede. Esses
pacotes com níveis de prioridade maior fazem bom uso dos canais virtuais preemptivos e
quando existe um pacote RT e um pacote comum, o pacote RT tem preferência no uso
dos canais.
5.2 Roteamento Proposto
Devido à natureza da topologia, nesse projeto o roteamento não pode contar com os
algoritmos usados em topologias regulares comuns. Para isso uma abordagem de rotea-
mento baseado em tabelas é utilizada para resolver o problema do roteamento.
Cada roteador possui uma tabela com 3 colunas e uma linha para cada roteador na
rede. Na tabela temos informações sobre o roteador de destino, o número da porta de
saída para chegar nesse roteador e número de saltos para conseguir chegar nesse roteador.
A figura 17 mostra como exemplo a tabela de roteamento do roteador R2.
Em cada linha da tabela temos informações sobre cada roteador que compõe a topo-
logia da rede. No exemplo acima têm-se que para chegar no roteador R2 não é necessário
nenhum salto, já que que o pacote já se encontra no roteador de destino. A porta de
saída do roteador R2 mostrada na tabela refere-se qual porta deve ser usada para enviar
os pacotes para o core que está associado a esse roteador. As linhas restantes falam dos
outros roteadores e a que distância esses roteadores estão do roteador R2.
As tabelas em cada roteador são construídas durante a formação da topologia da rede.
Cada tabela contém o endereço de qualquer roteador presente na topologia, portanto
quanto maior for a topologia, maior será a tabela e o seu espaço ocupado dentro do
roteador. Como nesse trabalho a área é medida pela quantidade de roteadores e não pelo
espaço ocupado de fato por cada roteador e seus componentes, esse é um problema que
não será abordado nesse trabalho, mas sim futuramente.
Quando os roteadores são alocados cada um em sua posição eles vão construindo e
mapeando as tabelas ao mesmo tempo. Na figura 18 pode ser visto como isso ocorre.
Na figura 18.a têm-se a rede com todos os roteadores em seu estado inicial e com
suas respectivas tabelas vazias. Na figura 18.b as tabelas começam a ser preenchidas
com os valores referente as posições de cada roteador na topologia e como chegar nesses
56
Figura 17: Tabela de Roteamento do Roteador R2
roteadores. Para formar as tabelas de roteamento é utilizado um algoritmo de caminho
mínimo, assim em cada tabela só teremos uma única rota para cada roteador na rede.
O uso de tabelas para realizar o roteamento na topologia impacta diretamente na
latência da rede, já que as tabelas precisam ser acessadas para se conhecer o caminho que
os pacotes têm que percorrer. Outro impacto direto é no quesito área, já que as tabelas
fazem com que os roteadores tenham um aumento no seu tamanho.
57
Figura 18: Preenchimento das Tabelas de Roteamento
58
6 Resultados
Neste capítulo serão mostrados os resultados obtidos referente as simulações e ex-
perimentos executados. Os resultados alcançados são gerados em redes com topologias
irregulares. Essas redes usam um algoritmo genético para otimizar as ligações entre os
roteadores e diminuir a área da rede através da retirada de roteadores. Os experimentos
focam na latência média da rede e no deadline dos pacotes de tempo real. Também são
utilizados roteadores heterogêneos que também visam a otimização da rede.
Para a obtenção dos resultados foi desenvolvida uma ferramenta em C++ que con-
tribuirá na geração de tráfego da rede. Também foi desenvolvida outra ferramenta em
C++, assistida da biblioteca SystemC, onde a mesma é o simulador das arquiteturas de
redes-em-chip. Os experimentos foram feitos através de explorações do espaço e projeto
da rede, a fim de atender otimização em taxa de latência média e quantidade de pacotes
que conseguiram chegar dentro do prazo estipulado.
6.1 Ferramenta de Simulação
A figura abaixo mostra o diagrama e a relação entre as ferramentas desenvolvidas e
utilizadas. Foram desenvolvidas duas ferramentas. A primeira ferramenta é uma geradora
de tráfego que foi desenvolvida em C++. Um grafo de uma aplicação serve de entrada
para a ferramenta geradora de tráfego contendo o padrão de comunicação da rede, como os
nodos de origem e destino para cada par de comunicação. Então são acrescidos os números
de pacotes a serem transmitidos e o prazo que um pacote RT tem para chegar ao destino
esperado. Esse prazo é dado em nanossegundos. Cada par de comunicação de origem e
destino recebe a mesma quantidade de pacotes a serem trafegado e também a o deadline
dado é o mesmo para todos os pacotes RT da aplicação. Ao final de tudo é gerado um
arquivo contendo todas as informações de tráfego da aplicação. A segunda ferramenta é
o simulador da rede, que foi desenvolvido usando a biblioteca do SystemC, o que garante
uma precisão maior nos resultados. O simulador foi implementado usando SystemC em
59
Figura 19: Ferramentas de Tráfego e Simulação
nível TLM (Transaction Level Modeling) (PANDA, 2001). Essa ferramenta também realiza
a DSE através da junção da simulação da rede em SystemC e do GA que é utilizado para
gerar as topologias otimizadas. O tempo de execução de cada simulação é o mesmo tempo
de prazo de entregas para os pacotes de tempo real. Quando o prazo de deadline acaba a
simulação termina e verifica a quantidade de pacotes RT que conseguiram cumprir esse
tempo. Também é feito o cálculo da latência média para todos os pacotes que foram
entregues durante esse tempo de simulação.
A ferramenta associa cada tarefa ao seu roteador correspondente, por exemplo: a
tarefa 1 é associada ao roteador 1, a tarefa 2 ao roteador 2 e assim por diante. Assim são
criados apenas a quantidade de roteadores necessárias, o que já nos dá uma otimização
em área.
A princípio o algoritmo genético cria uma população aleatória. Cada indivíduo dessa
população é uma representação de uma topologia irregular para a rede. Essas topologias
são então passados para a ferramenta de simulação e a mesma utiliza um algoritmo de
menor caminho para criar as tabelas de roteamento de cada roteador, assim cada roteador
recebe uma tabela que diz a que distância estão os outros roteadores da rede e através
de qual roteador deve ser realizado o acesso. O arquivo contendo as informações sobre o
tráfego da rede é recebido como uma entrada e só depois disso a ferramenta começa a
simular a comunicação na rede. A ferramenta de simulação gera como saída os cromosso-
mos que foram dados inicialmente pelo genético totalmente avaliados. Valores de aptidão
60
são dados para cada métrica que está sendo analisada, servindo como referência maior a
quantidade de pacotes RT que conseguiram cumprir o deadline estipulado.
Cada população contém 50 indivíduos. A cada simulação são escolhidos os 10 melhores
e os 10 piores. Essa escolha é feita baseada na taxa de latência média final (dada em
nanossegundos) e a taxa de pacotes que conseguem cumprir com seu deadline (dada em
porcentagem). Com os 10 melhores é feito o cruzamento, a fim de gerar 10 novos filhos
que irão substituir os 10 piores escolhidos. A mutação ocorre em cima de 50% dos novos
filhos gerados. Esse valor foi escolhido devido a ser um número médio de cromossomos que
seriam afetados e terem seus genes alterados. Essa nova população passará novamente por
simulação, a fim de gerar os resultados e novamente outra população. O processo é então
repetido 50 vezes. Esse é um valor também médio para otimização do problema, já que
um valor maior traria um maior custo computacional e de tempo para se obter a solução
desejada e um valor menor poderia não encontrar uma solução que seja bastante otimizada
para o problema. Para cada otimização completa de conexão entre os roteadores, é também
feita uma otimização nos tipos de roteadores utilizados. É diminuído o roteador do tipo
1 e ao mesmo tempo aumentado o do tipo 2, até que todas as formas de combinações
tenham sidos testadas. Também é realizada uma otimização no número de roteadores,
onde também a cada ciclo de otimização das conexões entre os roteadores e também dos
tipos de roteadores, são retirados roteadores um por um até chegar no limite mínimo
de roteadores estabelecidos. No final é escolhido o indivíduo que apresentou os melhores
valores de latência média, quantidade de pacotes que chegaram ao destino dentro do prazo
e menor número de roteadores.
6.2 Experimentos
Essa seção tratará dos experimentos feitos para validar a rede proposta aqui neste tra-
balho. As subseções falaram da metodologia utilizada para a realização dos experimentos
e também traz os resultados obtidos e suas respectivas análises. As simulações de cada
aplicação levaram em média 12 horas de simulação.
6.2.1 Metodologia
As aplicações utilizadas nesses experimentos são sintéticas e foram criadas através da
ferramenta TGFF (DICK; RHODES; WOLF, 1998). Foram gerados dois conjuntos de aplica-
ções. O primeiro conjunto de aplicações contém 10 tarefas associadas. O segundo conjunto
61
de aplicações contém 15 tarefas associadas. Todos os grafos gerados possuem fluxos de
comunicação diferentes. O volume de dados, a quantidade de pacotes transmitidos e o
prazo de entrega dos pacotes RT são diferentes em cada aplicação.
Os experimentos serão testados a priori com um valor de deadline longo para os
pacotes tempo real, e depois serão testados para mais dois conjuntos, onde o tempo de
deadline é diminuído, a fim de se descobrir quando a rede proposta deixa de atender às
necessidades de projeto. O maior valor de deadline testado para as aplicações é de 12000
nanossegundos, devido a ser um número médio de deadline para aplicações RT e o valor
mais curto de deadline utilizado é de 500 nanossegundos, que é um valor pequeno para
deadline de uma aplicação RT e foi escolhido para saber se a aplicação conseguirá ser
otimizada até esse ponto.
O primeiro conjunto de aplicações contará com o prazo total de deadline que foi
estabelecido pela ferramenta geradora de tráfego. O segundo conjunto apresentará um
deadline médio que terá seu valor diminuído pela metade. O terceiro conjunto contará
com valores que são 10 vezes menores que o primeiro conjunto de deadline.
Os resultados serão mostrados em tabelas. Na tabela será mostrada a aplicação e
os valores de latência e porcentagem dos pacotes RT entregues dentro do deadline. A
tabela contará também com a quantidade de roteadores do tipo 1 (T1) e a quantidade
de roteadores do tipo 2 (T2) . A tabela apresentará o resultado mais otimizado para cada
aplicação.
Cada aplicação também será simulada em uma rede com topologia Mesh 4x4 que
consegue atender a quantidade de tarefas usadas nas topologias irregulares. Os conjuntos
de resultados serão comparados através do Teste T (HSU; LACHENBRUCH, 2014), que é
um teste estatístico muito utilizado na literatura para comparar dois conjuntos de dados.
Após serem mostrados os resultados para todas as aplicações em forma de tabelas,
também serão mostrados gráficos diferentes para cada métrica avaliada. Cada gráfico
apresentará nas comparações entre as topologias irregulares e rede mesh.
As próximas subseções mostram as simulações e resultados quanto aos testes com
diferentes tempos de simulação e diferentes grafos com tamanhos e fluxo de dados variados.
Os grafos referentes as aplicações serão mostradas em forma de imagens. Ao todo são 8
grafos que são divididos com 4 grafos sendo usados com 10 tarefas e 4 com 15 tarefas.
62
6.2.2 Testes Com 10 Tarefas - Deadline Longo
Abaixo podem ser visualizados os grafos utilizados nas aplicações que contém 10
tarefas.
Figura 20: Primeira Aplicação (a) e Segunda Aplicação (b) - 10 Tarefas
Figura 21: Terceira Aplicação (a) e Quarta Aplicação (b) - 10 Tarefas
63
As figuras 20 e 21 mostram os grafos de comportamento das 4 aplicações sintéticas
criadas que possuem 10 tarefas.
A partir de agora serão mostrados os resultados dos experimentos em formato de
tabelas e no final de tudo serão apresentados gráficos, contendo todas as informações
sobre os resultados. As figuras relativas a cada topologia escolhida serão mostrado no
Apêndice A. A tabela 2 mostra os resultados referentes as topologias irregulares. A tabela
3 mostra os resultados na topologia mesh e a tabela 4 faz a comparação desses resultados
através do teste estatístico.
Tabela 2: Topologias Irregulares com 10 cores e Deadline Longo
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 279,350 100% 5 1
2 188,101 100% 3 3
3 177,907 100% 3 3
4 700,154 100% 4 2
Tabela 3: Topologia Mesh 4x4 e Deadline Longo
Aplicação Latência Média Pacotes RT Entregues
1 418,700 45%
2 306,733 31,33%
3 419,44 30%
4 198,636 18,18%
Tabela 4: Teste T - 10 Tarefas - Deadline Longo
Latência Média Pacotes RT Entregues
0.9975 0.0010
O teste estatístico T utilizado é um teste que tem um nível de confiança de 95%. O
modo do teste escolhido é o pareado e bicaudal. São então comparados os dois conjuntos
de latência média das 4 aplicações, para as redes irregulares e as redes mesh. Também
são analisados os dados do outro conjunto, que consiste da porcentagem dos pacotes de
tempo real que conseguiram ser entregues antes prazo acabar.
A figura 23 mostra os resultados em forma de gráfico para os valores de deadline com
10 aplicações e um deadline longo. Quando se tem um valor abaixo de 0,05 no resultado
do teste T, é porque há uma grande diferença entre os dois conjuntos de dados, como
é o caso da porcentagem de pacotes RT entregues dentro do deadline, cujo resultado da
64
Figura 22: Gráfico com os valores comparativos de latência para um grafo com 10 aplicações
e deadline longo
Figura 23: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
10 aplicações e deadline longo
comparação dos conjuntos é 0,0010. Pelas tabelas pode-se observar que nos testes com
topologias irregulares, o algoritmo genético foi capaz de otimizar a rede de de uma forma
que conseguisse entregar todos os pacotes tempo real no tempo estimado. Nas topologias
65
Figura 24: Gráfico com os valores comparativos de area para um grafo com 10 aplicações e
deadline longo
irregulares a aplicação 1 conseguiu entregar 55% a mais de pacotes RT. Na aplicação 2
essa diferença foi de 68,67%. Na aplicação 3 a topologia irregular obteve uma melhora de
70% e na aplicação 4 essa diferença foi de 81,2%. Devido a um longo período de deadline e
também a aplicações não tão grandes foi possível garantir a entrega em todas as aplicações
testadas.
A figura 22 apresenta um gráfico com os valores de latência para comparação da
topologia irregular e mesh. Quanto a análise nos conjuntos que representam os valores
de latência média, o resultado foi 0,9975. Não existe uma grande variação nos dados
desses dois conjuntos, mas, observando as tabelas pode-se perceber que em sua maioria
a aplicação usando topologia irregular conseguiu obter valores maiores no quesito de
latência. Na questão de latência a primeira aplicação teve uma redução de 33,28% em
relação a rede mesh equivalente. A segunda aplicação apresenta uma redução de 38,67%.
A terceira aplicação obteve uma redução de 57,58% na latência média e a quarta aplicação
teve um acréscimo de 252,48% na latência média, se comparado a sua equivalente rede
mesh. Como o deadline era logo as aplicações conseguiram realizar uma maior de entregas
de pacotes e conseguiu obter valores de latência média menores.
A figura 24 específica os valores quanto a área. Em relação a área, os roteadores têm
pesos diferentes já que ocupam espaços diferentes de área. Então se existissem duas redes
que tivessem os mesmos valores em porcentagem de pacotes entregues, latência média
66
e quantidade de roteadores, e mudasse apenas quantos roteadores de cada tipo cada
topologia tem, a rede escolhida seria aquela que contivesse menos roteadores do tipo 2, já
que é o que ocupa mais área dentro do chip. No presente trabalho os valores mostrados
nas tabelas de resultados já são os valores mais otimizados para cada aplicação testada.
Então os tipos de roteadores são levados em conta na hora de escolher a topologia mais
otimizada.
Ainda se tratando de área, pode-se observar que as topologias irregulares conseguiram
ser otimizadas para essas aplicações de modo que os números de roteadores caíssem 40%,
assim obtendo um melhor aproveitamento da área da arquitetura. Se for comparar com
uma topologia mesh, seria preciso uma topologia 4x4 para acomodar todos os 10 cores
das aplicações testadas, então essa redução no número de roteadores é de 62,5%.
6.2.3 Testes Com 10 Tarefas - Deadline Médio
Essa subseção foca nos experimentos e resultados para os mesmos grafos com 10
tarefas, mas com um deadline médio para os pacotes de tempo real. Na tabela 5 pode-
se visualizar os resultados referente as topologias irregulares. Na tabela 6 os resultados
equivalentes usando uma topologia mesh regular e na tabela 7 pode-se observar o teste
estatístico T comparando os resultados dessas duas abordagens. Após as tabelas serão
mostradas as figuras que representam as topologias irregulares otimizadas para cada apli-
cação.
Tabela 5: Topologias Irregulares com 10 cores e Deadline Médio
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 3120 100% 6 2
2 9140 37,5% 0 10
3 1830 100% 3 4
4 802,789 34,42% 0 10
Tabela 6: Topologia Mesh 4x4 e Deadline Médio
Aplicação Latência Média Pacotes RT Entregues
1 140,700 15%
2 856 12%
3 142,800 12%
4 720,45 9,84%
67
Tabela 7: Teste T - 10 Tarefas - Deadline Médio
Latência Média Pacotes RT Entregues
0.1641 0.0516
Figura 25: Gráfico com os valores comparativos de latência para um grafo com 10 aplicações
e deadline médio
Figura 26: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
10 aplicações e deadline médio
A figura 26 apresenta um gráfico que mostra a diferença entre os pacotes RT que
conseguiram ser entregues nas duas topologias testdas. Como pode ser observado nos testes
68
Figura 27: Gráfico com os valores comparativos de área para um grafo com 10 aplicações e
deadline médio
estatísticos, os valores de latência média e porcentagem de pacotes RT entregues ficaram
acima do valor de significância, que é 0,05. Então pode-se dizer que as duas amostras
não têm valores grandes de diferenças nesses conjuntos. Duas aplicações não conseguiram
serem otimizadas suficientes para entregar os pacotes RT cumprindo um valor médio de
deadline. As topologias mesh no entanto não conseguiram 100% em nenhuma. A aplicação
1 conseguiu entregar 85% a mais de pacotes RT do que a sua topologia mesh equivalente.
A segunda aplicação obteve uma vantagem de 25,5% com relação a sua mesh concorrente.
A topologia 3 conseguiu 88% de vantagem se comparada a uma NoC mesh. A última
aplicação utilizando topologia irregular teve um aumento de 34,10%. A segunda aplicação
não conseguiu entregar todos os pacotes dentro do prazo devido a essa aplicação ser a
que mais trafega pacotes. A quarta aplicação é a que contém o grafo com o maior número
de conexões, esse fator foi o responsável pelo algoritmo não conseguir entregar todos os
pacotes RT no prazo.
A figura 25 foca nos resultados de latência para aplicações com 10 tarefas e um valor
médio de deadline. Quanto aos valores de latência média, tivemos casos onde a latência da
arquitetura mesh foi mais eficiente, porém nenhuma das vezes foi conseguido receber todos
os pacotes de tempo real. A primeira aplicação teve um acréscimo de 95,49% na latência.
Para a segunda aplicação esse valor foi para 90,63%. Na terceira aplicação a diferença
continua aumentando e a topologia irregular teve um acréscimo de 92,19%. E na quarta
aplicação teve-se um aumento da latência média. Devido a um deadline já menor, se
69
comparado com os experimentos anteriores, foi possível entregar menos pacotes antes da
simulação da rede acabar, o que pode ter acarretado em maiores valores de latência.
A figura 27 foca nos resultados referentes as áreas das topologias quando começa
inicialmente, quando é otimizada e a topologia da mesh. No quesito área a aplicação 1
conseguiu uma redução de 20% quando comparado a sua quantidade original de roteado-
res. Se comparado a topologia mesh, essa redução foi de 50%. A aplicação 3 conseguiu uma
redução de 30% quando comparada a seu tamanho original de roteadores e uma redução
de 56,25% se comparada a topologia mesh. Por fim as aplicações 2 e 4 não conseguiram
reduzir seu número de roteadores e ainda assim utilizando apenas roteadores com canais
virtuais, ainda não foi possível cumprir com o deadline. De toda forma essas topologias
ainda apresentam uma redução de 37,5% no número de roteadores, em comparação com
uma mesh 4x4, que é a utilizada aqui.
6.2.4 Testes Com 10 Tarefas - Deadline Curto
Essa subseção apresenta os experimentos e resultados relativos aos grafos com 10 ta-
refas, mas dessa vez utilizando um deadline Curto para as simulações. As tabelas de 8
a 10 mostram os valores encontrados de latência e pacotes entregues para as topologias
irregulares otimizadas, para os experimentos com as NoC Mesh e para o teste T compa-
rativo, respectivamente. As figuras 30 a 33 por sua vez mostram as topologias irregulares
otimizadas para cada grafo.
Tabela 8: Topologias Irregulares com 10 cores e Deadline Curto
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 1530 100% 6 2
2 1058 100% 3 3
3 530 20% 1 9
4 173,757 21,73% 0 10
Tabela 9: Topologia Mesh 4x4 e Deadline Curto
Aplicação Latência Média Pacotes RT Entregues
1 990 1%
2 760 1,33%
3 780 2%
4 522,7 0,75%
70
Tabela 10: Teste T - 10 Tarefas - Deadline Curto
Latência Média Pacotes RT Entregues
0.7983 0.0816
Figura 28: Gráfico com os valores comparativos de latência para um grafo com 10 aplicações
e deadline curto
Figura 29: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
10 aplicações e deadline curto
A figura 29 mostra um gráfico que é relativo aos valores de taxas de entrega dos
pacotes RT dentro do deadline, para aplicações com 10 tarefas e um deadline curto. Para
71
Figura 30: Gráfico com os valores comparativos de área para um grafo com 10 aplicações e
deadline curto
um deadline mais Curto o teste T não apresenta grandes variações entre os conjuntos
de latência média e taxa dos pacotes RT entregues. Da mesma forma como no deadline
médio, duas aplicações não conseguiram mesmo depois da otimização entregar todos os
pacotes de tempo real e da mesma forma como nos deadlines longo e médio a topologia
mesh não obteve também uma taxa de 100% de entrega para todas as aplicações testadas.
A aplicação 1 usando topologias irregulares otimizadas conseguiu entregar 99% a mais de
pacotes de tempo real do que a sua contraparte mesh. A segunda aplicação obteve uma
taxa de 98,67% se comparado a topologia mesh usando a mesma aplicação. A aplicação
número 3 conseguiu entregar 18% a mais e a quarta aplicação conseguiu 20,98% a mais se
comparada a topologia mesh. A terceira aplicação dentre todas as outra é a que contém
um deadline menor, por esse motivo não conseguiu entregar todos os pacotes RT. A quarta
aplicação é a que contém um grafo com um maior número de conexões, por esse motivo
não conseguiu ser totalmente otimizada, para esse prazo de deadline.
A figura 28 exibe um gráfico com os valores de latência média para as topologias
irregulares e mesh. Se tratando de valores de latência os resultados são bem equiparados.
Em 50% dos casos a da topologia mesh foi melhor e nos outros 50% a topologia irregular
otimizada se sobressaiu. Mesmo nos casos onde a topologia mesh obteve melhores valores
quanto a latência, ainda não conseguiu ter bons valores referentes a entrega dos pacotes
RT. A primeira aplicação teve um aumento na latência de 35.29% quando comparado a
topologia mesh. A segunda aplicação teve um aumento de 28,16% nos valores de latência.
72
A terceira aplicação obteve uma redução de 47,16% na latência se comparada a topologia
mesh utilizando a mesma aplicação. Na quarta aplicação houve uma redução de 200,82%
no valor da latência média, em comparação a topologia mesh. Mesmo com um deadline
curto o uso dos roteadores do tipo 2 ajudaram a alcançar valores mais otimizados de
latência, fazendo com que em metade dos casos fossem melhores que os da rede mesh.
A figura 30 mostra um gráfico com um comparativo de área para as topologias utili-
zadas. No quesito área, houveram algumas aplicações que conseguiram diminuir a área na
otimização realizada pelo algoritmo genético. A primeira aplicação conseguiu uma redução
de 20% quando comparado as topologias irregulares iniciais que continham 10 roteado-
res e uma redução de 50% quando comparado a topologia mesh utilizada. A aplicação
número 2 obteve uma redução de 40% em relação as primeiras topologias irregulares e
62,5% se comparada a topologia mesh. A terceira aplicação não obteve redução em re-
lação a topologia irregular, mas teve uma redução de 37,5% quando comparado a mesh.
A aplicação número 4 também não obteve redução para a topologia irregular, mas ainda
assim apresenta uma redução de 37,5% em comparação a topologia mesh.
6.2.5 Testes Com 15 Tarefas - Deadline Longo
A partir dessa subseção serão mostrados experimentos utilizando grafos com 15 tarefas
cada. As figuras 34 e 35 mostram os comportamentos dos 4 grafos de 15 tarefas que foram
utilizados para simular esses experimentos.
Figura 31: Primeira Aplicação (a) e Segunda Aplicação (b) - 15 Tarefas
73
Figura 32: Terceira Aplicação (a) e Quarta Aplicação (b) - 15 Tarefas
A seguir poderá serem visualizadas as tabelas de 11 a 13 onde podem serem vistos os
resultados quanto aos experimentos de uma rede contendo 15 elementos de processamento
e um longo valor de deadline. As tabelas 11 e 12 mostram os resultados usando topolo-
gias irregulares e também utilizando rede mesh, respectivamente. A tabela 13 mostra as
estatísticas abordando os conjuntos de dados relativos à latência média e porcentagem de
pacotes entregues. As figuras 36 a 39 mostras as topologias irregulares otimizadas para
essas aplicações e valores de deadline.
Tabela 11: Topologias Irregulares com 15 cores e Deadline Longo
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 658,867 62,51% 0 10
2 895,676 100% 5 3
3 750,993 100% 3 5
4 488,399 61,90% 0 10
74
Tabela 12: Topologia Mesh 4x4 e Deadline Longo
Aplicação Latência Média Pacotes RT Entregues
1 262,125 19,37%
2 161,375 61,25%
3 192,471 20,58%
4 204,563 36,87%
Tabela 13: Teste T - 15 Tarefas - Deadline Longo
Latência Média Pacotes RT Entregues
0.0152 0.0277
Figura 33: Gráfico com os valores comparativos de latência para um grafo com 15 aplicações
e deadline longo
A figura 34 mostra um gráfico para os resultados dos pacotes RT entregues, usando
aplicações de 15 tarefas e um deadline longo. Os resultados mostrados acima dizem res-
peito a aplicações que utilizam 15 elementos de processamento e tem um deadline longo de
entrega dos pacotes tempo real. A tabela 12 que é referente ao teste estatístico T mostra
que há uma grande diferença entre os conjuntos de dados de latência média e de taxas
de pacotes RT entregues para as topologias irregulares e a topologia mesh. A primeira
aplicação conseguiu uma taxa de entrega dos pacotes tempo real de 43,21% em cima dos
valores da mesma aplicação utilizando a rede mesh. A segunda aplicação obteve uma taxa
de 38,75% maior, quando comparado a topologia mesh. A aplicação número 3 conseguiu
um desempenho a mais de 79,42% em relação a rede mesh. A aplicação número 4 teve
75
Figura 34: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
15 aplicações e deadline longo
Figura 35: Gráfico com os valores comparativos de área para um grafo com 15 aplicações e
deadline longo
uma taxa de entrega maior de 25,03% quando comparada a topologia mesh executando
a mesma aplicação. A primeira e quarta aplicação não conseguiram entregar totalmente
os pacotes RT devido a um aumento no número de cores utilizados para os mesmos valo-
res usados para 10 tarefas. A quantidade de vezes que o algoritmo genético atualiza sua
população não foi suficiente para essas aplicações.
A figura 33 exibe um gráfico para valores de latência envolvendo os dois tipos de
76
topologias utilizadas. Se tratando de latência média a topologia mesh conseguiu valores
menores de latência, mas não conseguiu melhores valores de entregas de pacotes RT
dentro do deadline. Quanto a valores de latência a primeira aplicação teve um aumento
de 60,21% de latência, em relação a topologia mesh executando a primeira aplicação.
A segunda aplicação obteve um aumento de 81,98% quando comparado a rede mesh.
A terceira aplicação conseguiu um aumento de 74,37% em relação a topologia mesh. A
quarta aplicação obteve um aumento de 58,11% nos valores de latência média quando
comparado a topologia mesh executando a mesma aplicação. Com um valor longo de
deadline foi possível obter resultados de latência não tão altos, se comparados a rede
mesh, mesmo a aplicação contendo 15 tarefas.
A figura 35 mostra os valores de área e seus comparativos em forma de gráfico. No
que diz respeito a área pode-se observar que a primeira aplicação obteve uma redução de
33,33% se comparado a topologia original e uma redução de 37,5% quando comparado
a topologia mesh. A segunda aplicação teve uma redução de 46,66% na área em relação
a topologia mesh original e uma diminuição de 50% referente a rede mesh. A terceira
aplicação conseguiu reduzir a área em 46,66% em comparação a rede irregular inicial e
uma redução de 50% quando comparado a rede mesh. A quarta aplicação teve a área
diminuída em 33,33% em relação a rede irregular inicial e uma diminuição de 37,5% em
comparação a rede mesh utilizada.
6.2.6 Testes Com 15 Tarefas - Deadline Médio
Nesta subseção serão tratados os experimentos relativos aos grafos com 15 tarefas.
Aqui serão abordadas as simulações envolvendo um deadline médio a fim de analisarmos
se o algoritmo genético conseguirá otimizar a topologia o suficiente de forma que todos
os pacotes RT sejam entregues.
As tabelas de 14 e 15 são responsáveis por mostrar os resultados referente as topologias
irregulares e as topologias mesh equivalente, para cada grafo de aplicação. Também poderá
ser visto, na tabela 16, o teste T que tem por finalidade analisar estatisticamente dois
conjuntos de valores. A figuras 40 a 43 ficam a cargo de mostrar como as topologias
irregulares escolhidas são.
77
Tabela 14: Topologias Irregulares com 15 cores e Deadline Médio
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 184,467 100% 6 2
2 3720 19,14% 0 10
3 873,848 100% 2 6
4 324,339 35,29% 0 10
Tabela 15: Topologia Mesh 4x4 e Deadline Médio
Aplicação Latência Média Pacotes RT Entregues
1 881,25 9,37%
2 587,50 6,25%
3 831,18 9,41%
4 873,75 9,37%
Tabela 16: Teste T - 15 Tarefas - Deadline Médio
Latência Média Pacotes RT Entregues
0.6284 0.0767
Figura 36: Gráfico com os valores comparativos de latência para um grafo com 15 aplicações
e deadline médio
A figura 37 apresenta um gráfico para as taxas de pacotes RT entregues dentro do
prazo. Esses valores são para aplicações com 15 tarefas e um deadline médio. Pode-se ob-
servar no teste T que não houve uma grande variação de valores em nenhum dos conjuntos,
mas ainda assim pode-se perceber que os valores de latência se encontram equilibrados
78
Figura 37: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
15 aplicações e deadline médio
Figura 38: Gráfico com os valores comparativos de área para um grafo com 15 aplicações e
deadline médio
e os de porcentagem dos pacotes de tempo real entregues mostram que as topologias ir-
regulares se saíram melhor. A primeira aplicação teve uma taxa de entrega de pacotes
RT 90,63% melhor do que usando uma topologia mesh. A segunda aplicação teve uma
melhora de 12,89% se comparado a topologia mesh. A terceira aplicação obteve um desem-
penho de 90,59% a mais que a topologia mesh. A quarta aplicação teve uma melhora no
desempenho de 22,92% quando comparado a rede mesh. A segunda e a quarta aplicação
79
são as que possuem os grafos com um maior número de conexões, o que pode ocasionar
um volume maior na rede. Além disso a segunda aplicação é a que possui uma maior
quantidade de pacotes sendo trafegados.
A figura 36 tras um gráfico com um comparativo dos valores de latência para as
topologias irregulares e as redes mesh. Em relação aos valores de latência a aplicação 1
teve uma diminuição na latência de 377,77% em relação a topologia mesh. A aplicação 2
teve um aumento de 84,20% na latência média se comparado a rede mesh. A aplicação
3 teve um aumento na latência de 4,88% em comparação a topologia mesh. A aplicação
4 obteve uma diminuição na latência média de 169,39% em relação a sua contraparte
mesh. Ainda que tenha se usado valores médios de deadline nessa simulação o uso dos
canais virtuais em alguns roteadores asseguraram valores melhores que os da rede mesh
na metade dos casos.
A figura 38 exibe um gráfico com os valores das áreas alcançadas pela otimização
da rede, os valores iniciais de roteadores pra topologia irregular inicial e a quantidade de
roteadores utilizados na topologia mesh. Quanto a área pode-se observar que sempre houve
uma diminuição no número de roteadores, mesmo que não se tenha conseguido entregar
todos os pacotes RT, os valores mostrados ainda assim são das topologias mais otimizadas.
Aplicação 1 teve uma diminuição de 46,66% em relação as primeiras topologias e uma
diminuição de 50% em relação a topologia mesh. A segunda aplicação teve uma diminuição
de 33,33% comparado com as primeiras topologias irregulares e uma diminuição de 37,5%
quando comparado a topologia mesh. A aplicação 3 obteve uma redução de 46,66% no
número de roteadores, em relação as primeiras topologias irregulares e 50% se comparado
a mesh. A quarta aplicação teve uma queda de 33,33% no número de roteadores da
topologia irregular e 37,5% em relação a topologia mesh.
6.2.7 Testes Com 15 Tarefas - Deadline Curto
Aqui serão mostrados os valores de resultados para os experimentos realizados com
grafos de 15 tarefas tendo um Curto valor de deadline para os pacotes de tempo real.
As tabelas 17 e 18 mostram exatamente os valores obtidos para latência e pacotes RT
entregues para as topologias irregulares e as topologias mesh, respectivamente. Pode-se
ser visto também, na tabela 19, os valores de comparação entre conjuntos, feitos pelo teste
T. As figuras 44 a 47 mostram as topologias irregulares otimizadas.
80
Tabela 17: Topologias Irregulares com 15 cores e Deadline Curto
Aplicação Latência Média Pacotes RT Entregues Roteadores T1 Roteadores T2
1 450 100% 6 2
2 566,67 100% 6 2
3 741,765 100% 5 3
4 184,467 88,69% 0 10
Tabela 18: Topologia Mesh 4x4 e Deadline Curto
Aplicação Latência Média Pacotes RT Entregues
1 6 0,625%
2 412,5 0,41%
3 547,1 0,58%
4 618,8 0,625%
Tabela 19: Teste T - 15 Tarefas - Deadline Curto
Latência Média Pacotes RT Entregues
0.6629 0.0001
Figura 39: Gráfico com os valores comparativos de latência para um grafo com 15 aplicações
e deadline curto
A figura 40 exibe um gráfico para a comparação dos pacotes RT que foram entregues
dentro do prazo, em um deadline curto e com aplicações de 15 tarefas. Os resultados
relativos ao teste estatístico mostram que no conjunto de latência média, cujo o p valor foi
0,6629, não houve uma grande variação, e como ser observado nas tabelas os valores estão
81
Figura 40: Gráfico com os valores comparativos de entrega de pacotes RT para um grafo com
15 aplicações e deadline curto
Figura 41: Gráfico com os valores comparativos de área para um grafo com 15 aplicações e
deadline curto
equiparados. Já no conjunto de taxa dos pacotes RT entregue, o p valor é 0,0001, o que
mostra uma grande variação entre os valores dos dois tipos de arquitetura. Esses valores
também podem ser consultados nas tabelas. As topologias irregulares não conseguiram
entregar 100% dos pacotes em apenas uma aplicação. A primeira aplicação obteve uma
taxa de entrega 93375% maior que quando usado a topologia mesh. A segunda aplicação
teve 9959% de pacotes tempo real a mais entregues do que sua contraparte usando a
82
topologia mesh. A terceira aplicação conseguiu ter um desempenho 99,42% melhor que
quando usado rede mesh. A quarta aplicação teve um desempenho de 88,065%, quando
comparado a rede mesh. A quarta aplicação é a segunda que possui um grafo com maior
número de conexões, o que aliada a um Curto valor de deadline e o fato de ter uma grande
quantidade de cores resultou na não entrega de todos os pacotes RT. Uma busca maior
do algoritmo genético poderia otimizar ainda mais essa aplicação.
A figura 39 mostra um gráfico com valores de latência média para as topologias irregu-
lares e mesh. No que diz respeito a latência média os resultados se mostram equilibrados.
A primeira aplicação teve uma latência 98,66% a mais que quando usado topologia mesh.
A segunda aplicação teve um aumento de 27,20% nos valores de latência. A terceira apli-
cação teve um aumento na latência de 26,24% em relação a topologia mesh. A quarta
aplicação conseguiu ter uma melhora de 235,45% nos valores de latência média. Devido
a um curto deadline, as taxas de latência média não conseguiram ser melhores que as da
rede mesh que executavam a mesma aplicação, tendo como exceção a ultima aplicação.
A figura 41 apresenta um gráfico que mostra a comparação da área para um deadline
curto e aplicações com 15 tarefas. No quesito área, com certeza existe uma melhora nas
topologias. A primeira, segunda e terceira aplicação conseguiram uma melhora de 46,66%
em relação as topologias irregulares iniciais e também conseguiram uma redução de 50% se
comparado a topologia mesh. A quarta aplicação obteve uma melhora na área de 33,33%
e 37,5% se comparado a topologia mesh.
Os resultados obtidos em todos os experimentos mostram que as redes irregulares
otimizadas pelo algoritmo genético apresentadas neste trabalho conseguem gerar cenários
mais otimizados, em relação às as redes com topologia mesh. No que diz respeito as
taxas de entrega dos pacotes de tempo real (em casos com taxas variadas de deadline
e grafos com comunicações variadas), conseguem entregar 100% dos pacotes RT dentro
do prazo estipulado. Ainda assim as redes que não conseguem entregar totalmente os
pacotes RT, conseguem uma taxa de entrega maior, quando comparada à rede mesh. No
que diz respeito a latência os resultados foram equilibrados; em algumas aplicações a rede
mesh conseguiu obter melhores resultados, e em outras, as topologias irregulares. Em
relação ao quesito área, as topologias irregulares conseguiram obter uma diminuição no
número de roteadores na maioria dos testes em todas as aplicações, o que acarreta em uma
diminuição da área total da rede. Quando comparado as topologias mesh sempre houve
uma diminuição no número de roteadores, já que para comportar todos os elementos de
processamento das aplicações utilizadas é preciso uma rede 4x4 e as topologias irregulares
83
utilizaram no máximo 10 roteadores.
84
7 Considerações Finais
O uso de redes-em-chip ao invés do barramento para realizar a comunicação entre as
tarefas em um MP-SoC se provou uma boa maneira se obter melhores valores de latência.
O fato de se ter reuso e escalabilidade também contribuem para essa escolha.
O uso de topologias irregulares para aplicações específicas pode oferecer um ganho
em latência, área e potência, por isso as topologias irregulares foram escolhidas para este
trabalho. Uma boa exploração no espaço e projeto da rede pode fornecer informações
sobre o uso da rede. Essas informações são capazes de ajudar na hora da confecção final
do circuito integrado (CI) .
Para se conseguir redes que sejam mais adequadas a aplicações específicas e otimizadas
para que atendam às restrições de projeto, é necessário realizar uma exploração do espaço
de projeto, verificando o maior número possível de configurações, de forma que se possa
encontrar soluções que atendam todas as características esperadas. O grande espaço de
projeto dificulta os testes das redes, inviabilizando uma busca exaustiva. Uma solução
para percorrer esse espaço de busca se dá através do uso de heurísticas que venham a
otimizar esse processo.
Este trabalho fez uma análise no que diz respeito a exploração de espaço do projeto e
ao uso de topologias irregulares para se obter redes com melhores valores de latência, área
e uma maior taxa de pacotes de tempo real entregues dentro do deadline estipulado. As
redes utilizadas aqui são otimizadas através de um algoritmo genético e conta com o uso
de roteadores heterogêneos que buscam otimizar a rede de forma que possa-se alcançar as
métricas desejadas.
Durante o trabalho foram usadas diferentes aplicações, com diferentes padrões de
comunicação e deadlines para os pacotes RT. O algoritmo genético é responsável pela
DSE e busca encontrar redes que sejam as mais otimizadas possíveis no que diz respeito
a latência média, pacotes RT entregues e quantidade de roteadores. O uso de roteadores
heterogêneos também contribui para a otimização da rede, já que um tipo de roteador
85
possui canais virtuais preemptivos, o que tende a diminuir a latência de pacotes de tempo
real.
Os resultados mostrados nesse trabalho mostram que é possível realizar uma DSE
e encontrar redes que sejam otimizadas para diferentes aplicações e prazos de entrega
de pacotes. As redes irregulares, através do algoritmo genético, conseguiram encontrar
topologias que atenderam os requisitos de latência, área e prazo de entrega dos pacotes
RT. Na comparação realizada com as redes mesh, as redes irregulares que usam roteadores
heterogêneos se mostraram superiores e atenderam as restrições de projeto.
Futuramente planeja-se evoluir esse trabalho utilizando redes hibridas que utilizem
roteadores ligados por fio e roteadores que se conectam por pequenas antenas ligadas
aos roteadores, as chamadas WiNoCs (Wireless Network-on-Chip) . Também planeja-
se analisar, além do já proposto nesse trabalho, o consumo de energia para verificar a
eficiência de uma rede hibrida e o uso de roteadores heterogêneos.
86
Referências
ABABEI, C. Efficient congestion-oriented custom network-on-chip topology synthesis.
In: IEEE. Reconfigurable Computing and FPGAs (ReConFig), 2010 International
Conference on. [S.l.], 2010. p. 352–357.
AGARWAL, A.; ISKANDER, C.; SHANKAR, R. Survey of network on chip (noc)
architectures & contributions. Journal of engineering, Computing and Architecture, v. 3,
n. 1, p. 21–27, 2009.
AJABSHIR, V. B.; TOSUN, S. Fault-tolerant routing for irregular-topology-based
network-on-chips. In: IEEE. Computing and Networking (CANDAR), 2014 Second
International Symposium on. [S.l.], 2014. p. 123–129.
ANIRUDH, G. S.; SOUMYA, J. Routing algorithm for application-specific network-on-
chip with irregular core sizes. In: IEEE. Nanoelectronic and Information Systems (iNIS),
2017 IEEE International Symposium on. [S.l.], 2017. p. 56–60.
BEN-ITZHAK, Y. et al. Heterogeneous noc router architecture. IEEE Transactions on
Parallel and Distributed Systems, IEEE, v. 26, n. 9, p. 2479–2492, 2015.
BENINI, L.; MICHELI, G. D. Networks on chip: a new paradigm for systems on chip
design. In: IEEE. Design, Automation and Test in Europe Conference and Exhibition,
2002. Proceedings. [S.l.], 2002. p. 418–419.
BENYAMINA, A. E. H. et al. Mapping real time applications on noc architecture
with hybrid multi-objective algorithm. In: META’10 Intenational Conference on
Metaheuristics and Nature Inspired Computing. [S.l.: s.n.], 2010.
BEREJUCK, M. D. et al. Rede intra-chip com qualidade de serviços para uso em
telecomunicações. Universidade do Vale do Itajaí, 2009.
BJERREGAARD, T.; MAHADEVAN, S. A survey of research and practices of
network-on-chip. ACM Computing Surveys (CSUR), ACM, v. 38, n. 1, p. 1, 2006.
BLICKLE, T. Theory of evolutionary algorithms and application to system synthesis.
[S.l.]: vdf Hochschulverlag AG, 1997.
BOLOTIN, E. et al. Qnoc: Qos architecture and design process for network on chip.
Journal of systems architecture, Elsevier, v. 50, n. 2-3, p. 105–128, 2004.
BRUCH, J. V. Mapeamento estático de tarefas de aplicações de tempo real em sistemas
baseados em redes-em-chip. 2015.
BUENO, F. Métodos heurísticos: Teoria e implementações. Instituto Federal de Santa
Catarina, Araranguá, 2009.
87
CARDOSO, R. et al. Design space exploration on heterogeneous network-on-chip. In:
IEEE. Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on.
[S.l.], 2005. p. 428–431.
CARDOZO, R. d. S. Redes-em-chip de baixo custo. 2005.
CARDOZO, R. S. et al. Tonga: A low cost router for nocs. In: WORKSHOP IBERCHIP.
[S.l.: s.n.], 2004. v. 10.
CARVALHO, E. L. d. S. Mapeamento dinâmico de tarefas em mpsocs heterogêneos
baseados em noc. Pontifícia Universidade Católica do Rio Grande do Sul, 2009.
CHOUDHARY, N.; GAUR, M.; LAXMI, V. Irregular noc simulation framework:
Irnirgam. In: IEEE. Emerging Trends in Networks and Computer Communications
(ETNCC), 2011 International Conference on. [S.l.], 2011. p. 1–5.
CHOUDHARY, N. et al. Conjoined irregular topology and routing table generation for
network-on-chip. In: IEEE. India Conference (INDICON), 2009 Annual IEEE. [S.l.],
2009. p. 1–4.
CORRÊA, E. d. F. Redes-em-chip para sistemas embarcados visando a otimização de
medidas de qualidade de serviço para aplicações de tempo real. 2007.
COTA, É.; AMORY, A. de M.; LUBASZEWSKI, M. S. Reliability, Availability and
Serviceability of Networks-on-chip. [S.l.]: Springer Science & Business Media, 2011.
DALLY, W. J.; TOWLES, B. P. Principles and practices of interconnection networks.
[S.l.]: Elsevier, 2004.
DAS, R. et al. Design and evaluation of a hierarchical on-chip interconnect for
next-generation cmps. In: IEEE. High Performance Computer Architecture, 2009. HPCA
2009. IEEE 15th International Symposium on. [S.l.], 2009. p. 175–186.
DICK, R. P.; RHODES, D. L.; WOLF, W. Tgff: task graphs for free. In: IEEE
COMPUTER SOCIETY. Proceedings of the 6th international workshop on
Hardware/software codesign. [S.l.], 1998. p. 97–101.
DRIDI, M. et al. Das: an efficient noc router for mixed-criticality real-time systems. In:
IEEE. 2017 IEEE 35th International Conference on Computer Design (ICCD). [S.l.],
2017. p. 229–232.
DUATO, J.; YALAMANCHILI, S.; NI, L. M. Interconnection networks: an engineering
approach. [S.l.]: Morgan Kaufmann, 2003.
HOLLAND, J. H. Adaptation in natural and artificial systems: an introductory analysis
with applications to biology, control, and artificial intelligence. [S.l.]: MIT press, 1992.
HSU, H.; LACHENBRUCH, P. A. Paired t test. Wiley StatsRef: Statistics Reference
Online, Wiley Online Library, 2014.
ITRS. ITRS. mar. 2018. Mar., 2018. Disponível em: <http://www.itrs2.net/>. Acesso
em Março 14, 2018.
88
JUNIOR, N. A. G. Análise e simulaçao de topologias de redes em chip. 2010.
KASAPAKI, E. et al. Argo: A real-time network-on-chip architecture with an efficient
gals implementation. IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, IEEE, v. 24, n. 2, p. 479–492, 2016.
KHAN, S. et al. An efficient algorithm for mapping real time embedded applications on
noc architecture. IEEE Access, IEEE, 2018.
KHAWAJA, S. G. et al. A novel multiprocessor architecture for k-means clustering
algorithm based on network-on-chip. In: IEEE. Multi-Topic Conference (INMIC), 2016
19th International. [S.l.], 2016. p. 1–5.
KREUTZ, M. et al. Energy and latency evaluation of noc topologies. In: IEEE. Circuits
and Systems, 2005. ISCAS 2005. IEEE International Symposium on. [S.l.], 2005. p.
5866–5869.
KREUTZ, M. et al. Design space exploration comparing homogeneous and heterogeneous
network-on-chip architectures. In: ACM. Proceedings of the 18th annual symposium on
Integrated circuits and system design. [S.l.], 2005. p. 190–195.
KREUTZ, M. E. Método para a otimização de plataformas arquiteturais para sistemas
multiprocessados heterogêneos. 2005.
LAHIRI, K.; RAGHUNATHAN, A.; DEY, S. Design space exploration for optimizing
on-chip communication architectures. IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems, IEEE, v. 23, n. 6, p. 952–961, 2004.
LAI, G.; LIN, X. Floorplan-aware application-specific network-on-chip topology synthesis
using genetic algorithm technique. The Journal of Supercomputing, Springer, v. 61, n. 3,
p. 418–437, 2012.
LAI, G.; LIN, X.; LAI, S. Ga-based floorplan-aware topology synthesis of application-
specific network-on-chip. In: IEEE. Intelligent Computing and Intelligent Systems (ICIS),
2010 IEEE International Conference on. [S.l.], 2010. v. 2, p. 554–558.
LEARY, G. et al. Design of network-on-chip architectures with a genetic algorithm-based
technique. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, IEEE,
v. 17, n. 5, p. 674–687, 2009.
LEI, T.; KUMAR, S. A two-step genetic algorithm for mapping task graphs to a network
on chip architecture. In: IEEE. Digital System Design, 2003. Proceedings. Euromicro
Symposium on. [S.l.], 2003. p. 180–187.
LIU, M. Real-Time Communication over Wormhole-Switched On-Chip Networks. Tese
(Doutorado) — Malardalen University Press, 2017.
LV, M. et al. Rtnoc: a simulation tool for real-time communication scheduling on
networks-on-chips. In: IEEE. Computer Science and Software Engineering, 2008
International Conference on. [S.l.], 2008. v. 4, p. 102–105.
MATOS, D. d. S. M. Interfaces parametrizáveis para aplicações interconectadas por uma
rede-em-chip. 2010.
89
MCMENAMIN, A.; AUDSLEY, N. C. Partial paging for real-time noc systems. OSPERT
2015, p. 13, 2015.
MESIDIS, P.-a. Mapping of Real-time Applications on Network-on-Chip based MPSOCS.
Tese (Doutorado) — University of York, 2011.
MESQUITA, J. W. d. Exploração de espaço de projeto para geração de redes em chip de
topologias irregulares otimizadas: a rede UTNoC. Dissertao (Mestrado) — Brasil, 2016.
MESQUITA, J. W. de et al. Design space exploration using utnocs and genetic algorithm.
In: IEEE. Computing Systems Engineering (SBESC), 2016 VI Brazilian Symposium on.
[S.l.], 2016. p. 198–202.
MILFONT, R. et al. Analysis of routing algorithms generation for irregular noc
topologies. In: IEEE. Test Symposium (LATS), 2017 18th IEEE Latin American. [S.l.],
2017. p. 1–5.
MURALI, S.; BENINI, L.; MICHELI, G. D. Mapping and physical planning of
networks-on-chip architectures with quality-of-service guarantees. In: ACM. Proceedings
of the 2005 Asia and South Pacific Design Automation Conference. [S.l.], 2005. p. 27–32.
OZTURK, O.; DEMIRBAS, D. Heterogeneous network-on-chip design through
evolutionary computing. International Journal of Electronics, Taylor & Francis, v. 97,
n. 10, p. 1139–1161, 2010.
PACHECO, M. A. C. et al. Algoritmos genéticos: princípios e aplicações. ICA:
Laboratório de Inteligência Computacional Aplicada. Departamento de Engenharia
Elétrica. Pontifícia Universidade Católica do Rio de Janeiro. Fonte desconhecida, p. 28,
1999.
PANDA, P. R. Systemc: a modeling platform supporting multiple design abstractions.
In: ACM. Proceedings of the 14th international symposium on Systems synthesis. [S.l.],
2001. p. 75–80.
PASRICHA, S.; DUTT, N. On-chip communication architectures: system on chip
interconnect. [S.l.]: Morgan Kaufmann, 2010.
QI, J. et al. A new hierarchical genetic algorithm for low-power network on chip design.
In: IEEE. Intelligent Control and Information Processing (ICICIP), 2010 International
Conference on. [S.l.], 2010. p. 159–162.
REINBRECHT, C. R. W. Desenvolvimento e avaliação de redes-em-chip hierárquicas e
reconfiguráveis para mpsocs. 2012.
RIJPKEMA, E. et al. Trade-offs in the design of a router with both guaranteed
and best-effort services for networks on chip. IEE Proceedings-Computers and Digital
Techniques, IET, v. 150, n. 5, p. 294–302, 2003.
ROMANOV, A. Y.; ROMANOVA, I. Use of irregular topologies for the synthesis of
networks-on-chip. In: IEEE. Electronics and Nanotechnology (ELNANO), 2015 IEEE
35th International Conference on. [S.l.], 2015. p. 445–449.
90
SAYUTI, M. N. S. M.; INDRUSIAK, L. S. Real-time low-power task mapping in
networks-on-chip. In: IEEE. VLSI (ISVLSI), 2013 IEEE Computer Society Annual
Symposium on. [S.l.], 2013. p. 14–19.
SHAH, P.; KANNIGANTI, A.; SOUMYA, J. Fault-tolerant application specific
network-on-chip design. In: IEEE. Embedded Computing and System Design (ISED),
2017 7th International Symposium on. [S.l.], 2017. p. 1–5.
SHI, Z. Real-time communication services for networks on chip. Tese (Doutorado) —
University of York, 2009.
SILVA, J. I. S. da; SILVA, I. S. Malha de interconexão para sistemas em chip único.
SOUZA, S. A. d. Algoritmos genéticos aplicados à proteção e estimação de harmônicos
em sistemas elétricos de potência. Tese (Doutorado) — Universidade de São Paulo, 2008.
SYSTEMC. SYSTEMC. mar. 2018. OMar., 2018. Disponível em: <http://www.
accellera.org/downloads/standards/systemc>. Acesso em Março 16, 2018.
TEDESCO, L. Uma proposta para geração de tráfego e avaliação de desempenho para
nocs. Pontificia Universidade Catolica Do Rio Grande Do Sul: Porto Alegre, p. 125,
2005.
TOSUN, S. et al. Fault-tolerant irregular topology design method for network-on-chips.
In: IEEE. Digital System Design (DSD), 2014 17th Euromicro Conference on. [S.l.],
2014. p. 631–634.
TOSUN, S.; AR, Y.; OZDEMIR, S. Application-specific topology generation algorithms
for network-on-chip design. IET computers & digital techniques, IET, v. 6, n. 5, p.
318–333, 2012.
VELLANKI, P.; BANERJEE, N.; CHATHA, K. S. Quality-of-service and error control
techniques for network-on-chip architectures. In: ACM. Proceedings of the 14th ACM
Great Lakes symposium on VLSI. [S.l.], 2004. p. 45–50.
WETTIN, P. et al. Design space exploration for wireless nocs incorporating irregular
network routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, IEEE, v. 33, n. 11, p. 1732–1745, 2014.
ZEFERINO, C. A. Redes-em-chip: arquiteturas e modelos para avaliação de área e
desempenho. 2003.
ZEFERINO, C. A. et al. Avaliação de desempenho de rede-em-chip modelada em systemc.
In: Proceedings of the 27rd Congress of Brazilian Computer Society-WPerformance. [S.l.:
s.n.], 2007. p. 559–578.
ZEFERINO, C. A.; SANTO, F. G.; SUSIN, A. A. Paris: a parameterizable interconnect
switch for networks-on-chip. In: ACM. Proceedings of the 17th symposium on Integrated
circuits and system design. [S.l.], 2004. p. 204–209.
ZEFERINO, C. A.; SUSIN, A. A. Socin: a parametric and scalable network-on-chip. In:
IEEE. Integrated Circuits and Systems Design, 2003. SBCCI 2003. Proceedings. 16th
Symposium on. [S.l.], 2003. p. 169–174.
91
APÊNDICE A -- Topologias Irregulares
Otimizadas
Aqui serão exibidas as figuras com as topologias mais otimizadas referentes as aplica-
ções contendo 10 e 15 tarefas. As topologias serão mostradas para cada grupo de testes
que foram realizados.
A figura 42 mostra a topologia mais otimizada encontrada para a primeira aplicação
com 10 tarefas e um deadline longo. A figura 43 mostra a topologia para a segunda apli-
cação envolvendo o mesmo caso. A figura 44 mostra a topologia para a terceira aplicação
e a figura 45 a topologia mais otimizada para a quarta aplicação com 10 tarefas e um
deadline longo.
A figura 46 mostra como ficou a topologia mais otimizada para a primeira aplicação
envolvendo 10 tarefas e um deadline médio de entrega dos pacotes de tempo real. A figura
47 apresenta a topologia otimizada para a segunda aplicação que contém 10 tarefas e
utiliza um deadline médio na simulação. A figura 48 exibe a topologia relativa a terceira
aplicação no mesmo cenário e a figura 49 mostra a topologia para a quarta aplicação.
A figura 50 é relativa a topologia mais otimizada da primeira aplicação contendo 10
tarefas em um cenário onde a entrega dos pacotes envolve um curto deadline. A figura
51 mostra como seria a topologia otimizada para a segunda aplicação de 10 tarefas e um
curto prazo de deadline. A figura 52 exibe a melhor topologia para a terceira aplicação do
mesmo cenário. A figura 53 representa a topologia mais otimizada para a quarta aplicação
com 10 tarefas e um curto prazo de entrega dos pacotes de tempo real.
A figura 54 representa a topologia mais otimizada para a primeira aplicação contendo
15 tarefas e um longo deadline para os pacotes RT. A figura 55 apresenta a melhor
configuração de topologia envolvendo a segunda aplicação de 15 tarefas e um deadline
longo. A figura 38 mostra a melhor topologia para a terceira aplicação com 56 elementos
de processamento e um longo deadline. A figura 57 exibe a topologia mais otimizada para
a quarta aplicação nesse mesmo cenário.
92
A figura 58 apresenta a topologia mais otimizada para a primeira aplicação de 15
tarefas com um médio deadline de entrega dos pacotes RT. A figura 59 mostra a melhor
topologia para a segunda aplicação com 15 tarefas, em um cenário com um médio deadline.
A figura 60 exibe a topologia mais otimizada para a terceira aplicação com 15 elementos
de processamento e um deadline médio para os pacotes de tempo real. A figura 61 mostra
a topologia otimizada para a quarta aplicação de 15 tarefas e um médio deadline.
A figura 62 mostra a topologia mais otimizada para a primeira aplicação envolvendo
15 tarefas e um prazo curto de deadline. A figura 63 exibe a melhor topologia para a
segunda aplicação que utiliza 15 tarefas e tem um curto deadline para entrega dos pacotes
RT. A figura 64 apresenta a topologia mais otimizada para a terceira aplicação com 15
elementos de processamento e um curto prazo de deadline. A figura 65 mostra a topologia
otimizada para a quarta aplicação com 15 elementos de processamento e um período curto
de deadline para entrega dos pacotes de tempo real.
Figura 42: Primeira Aplicação Otimizada - 10 Tarefas - Deadline Longo
93
Figura 43: Segunda Aplicação Otimizada - 10 Tarefas - Deadline Longo
Figura 44: Terceira Aplicação Otimizada - 10 Tarefas - Deadline Longo
94
Figura 45: Quarta Aplicação Otimizada - 10 Tarefas - Deadline Longo
Figura 46: Primeira Aplicação Otimizada - 10 Tarefas - Deadline Médio
95
Figura 47: Segunda Aplicação Otimizada - 10 Tarefas - Deadline Médio
Figura 48: Terceira Aplicação Otimizada - 10 Tarefas - Deadline Médio
96
Figura 49: Quarta Aplicação Otimizada - 10 Tarefas - Deadline Médio
Figura 50: Primeira Aplicação Otimizada - 10 Tarefas - Deadline Curto
97
Figura 51: Segunda Aplicação Otimizada - 10 Tarefas - Deadline Curto
Figura 52: Terceira Aplicação Otimizada - 10 Tarefas - Deadline Curto
98
Figura 53: Quarta Aplicação Otimizada - 10 Tarefas - Deadline Curto
Figura 54: Primeira Aplicação Otimizada - 15 Tarefas - Deadline Longo
99
Figura 55: Segunda Aplicação Otimizada - 15 Tarefas - Deadline Longo
Figura 56: Terceira Aplicação Otimizada - 15 Tarefas - Deadline Longo
100
Figura 57: Quarta Aplicação Otimizada - 15 Tarefas - Deadline Longo
Figura 58: Primeira Aplicação Otimizada - 15 Tarefas - Deadline Médio
101
Figura 59: Segunda Aplicação Otimizada - 15 Tarefas - Deadline Médio
Figura 60: Terceira Aplicação Otimizada - 15 Tarefas - Deadline Médio
102
Figura 61: Quarta Aplicação Otimizada - 15 Tarefas - Deadline Médio
Figura 62: Primeira Aplicação Otimizada - 15 Tarefas - Deadline Curto
103
Figura 63: Segunda Aplicação Otimizada - 15 Tarefas - Deadline Curto
Figura 64: Terceira Aplicação Otimizada - 15 Tarefas - Deadline Curto
104
Figura 65: Quarta Aplicação Otimizada - 15 Tarefas - Deadline Curto