Exploração do
Espaço de Projeto
do Dragão Limão
Renato Hentschke
[email protected]
Exploração do espaço de projeto de aplicações descritas em um grafo.
Baseia-se em uma biblioteca de componentes. Usa algoritmos genéticos
para realizar a busca.
Roteiro
• Fluxo da ferramenta
• Exemplo de entrada
• Método de busca
• Exemplo de saída
• Curvas de Paretto
• Trabalhos Futuros
GUI
Serial ou Paralelo
Pesos de Otimização
Potência, Atraso, Área
Arquivos
Parâmetros do Algoritmo
Genético
Trace do
Programa
Mapeado
Componentes
Trace da
Aplicação
Curvas
De
Paretto
(2D e 3D)
Trace da Aplicação
1 Seno
3 Sort
3 Sort
15 Tabela
15 RotinaX
1 Cos
Entrada de Dados
Aplicação pode ser executada em paralelo ou não.
N Proc.
Tipo de solução desejada em área, potência e timing.
Pesos Busca
Rotinas
Escolha das variáveis para encontrar curvas de Paretto.
Biblioteca
Paretto
Configuração do algoritmo genético:
tamanho da população, taxa de crossover/mutação, etc.
Alg. Gen.
Grafo
Aplicação
Mecanismo de Busca
Algoritmo
Mapeamento
Inicial
Busca
Exaustiva
Genético
Solução
“ótima”
Saída do programa
1 SenoLUT
1 Seno
3 QuickSort
3 Sort
3 MergeSort
3 Sort
15
15TabelaHash
Tabela
15 RotinaX_ImplA
15 RotinaX
1 CosLUT
1 Cos
Curvas de Paretto (2D x 3D)
2D
1) Escolha de duas variáveis entre
área, potência e timing.
3D
Ex: timing e potência
2) Durante a busca, guarda a
potência ótima encontrada para
cada variação de timing.
1) Escolha a ordem das três
variáveis.
Ex: timing, potência e área
2) Durante a busca, guarda a área
ótima encontrada para cada par
timing/potência.
3) Ao final, têm-se o mapeamento
que atinge a mínima potência para
cada variação de timing.
3) Ao final, têm-se o mapeamento
que atinge a mínima área para cada
variação de timing/potência.
Curvas de Paretto (2D x 3D)
2D
3D
Power x Timing
Power x Timing x Area
Curvas de Paretto (Busca)
Mapeamento
Inicial
Busca
Algoritmo
Genético
Solução
“ótima”
Exaustiva
Paretto
Encontra todos os
pontos da curva
garantidamente
Paretto
Encontra os
“principais” pontos
da curva.
O tempo de CPU
das buscas aumenta
cerca de 20% ao
procurar pelas
curvas de Paretto
Curvas de Paretto (saída)
1 SenoLUT
3 QuickSort
3 MergeSort
15 TabelaHash
15 RotinaX_ImplA
1 CosLUT
Trabalhos Futuros
- Usar a ferramenta com exemplos reais de aplicações
- Técnicas de busca mais rápidas
- Número fixo de processadores