Novos Algoritmos para
Roteamento de Área
Proposta de Tese
Aluno:
Orientador:
Marcelo Johann
Ricardo Reis
Resumo
•
•
•
•
•
•
•
Introdução
Algoritmos de Roteamento
Algoritmos de Pesquisa de Caminhos
Roteamento de Área
Roteamento com o Algoritmo LCS*
Roteamento com o Algoritmo LEGAL
Conclusões e Cronograma
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
1
Introdução
Roteamento é a parte da síntese física
responsável por definir as rotas das
conexões
• é uma tarefas complexa;
• relaciona-se com a tecnologia de fabricação;
• consiste em muitos problemas distintos;
• requer uma variedade de algoritmos;
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
2
Algoritmos de Roteamento
Algoritmos de roteamento solucionam
problemas de roteamento.
• Classificação
• Algoritmos de Roteamento Genéricos
• Roteamento de Canal
• Roteamento Global
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
2.1 Classificação
Classificação de roteamento por objetivos:
• Roteamento detalhado
• Roteamento global
• Roteamento especializado
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Classificação de roteamento
quanto ao espaço:
• espaços dedicados: canais e switch boxes;
• sobre as células, roteamento de área,...
general cell
standard cells
Novos Algoritmos para Roteamento de Área
roteamento de área
- Marcelo Johann / 1999
Classificação dos algoritmos de
roteamento quanto ao processamento:
• incrementais ou seqüenciais: fazem uma
conexão a cada vez. Problema: ordenação;
• integrais ou paralelos: consideram todas as
conexões ao mesmo tempo;
• refinadores ou iterativos: partem de uma
solução inicial e repetem a operação de
desfazer e refazer conexões até o fim;
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Classificação dos algoritmos de
roteamento quanto à aplicação:
• genéricos: podem ser aplicados a muitos
problemas diferentes de roteamento;
• restritos: exploram características ou
restrições particulares de um problema para
encontrar soluções com maior eficiência;
ex: roteamento de canal
caixas de conexão
roteamento planar ...
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
2.2 Algoritmos de Roteamento Genéricos
Baseados em pesquisa de caminhos:
• maze-routers [Lee 61], derivados de BFS;
Baseados em geometria:
• line-probe e line-expansion;
Algoritmo Hierárquico:
• baseado em particionamento;
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Maze Routers
•
•
•
•
pesquisa BFS em uma grade (Lee 1961)
memória ocupada (mínimo 1 bit)
tempo de processamento
ordenação
genérico
seqüencial
muito usado
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
2.3 Roteamento de Canal
• Modelo de canal: espaço entre duas bandas;
• definição: terminais superiores e inferiores;
• dificuldade de roteamento: horizontal;
Números das redes
1
2
0
0
0
4
6
6
0
5
topo, ou borda superior
terminais
trilhas
vias
branches
n=6
h=3
l = 10
dogleg
segmentos (trunks)
2 3
0
0 4
1
0
5
Novos Algoritmos para Roteamento de Área
3 0
base, ou borda inferior
- Marcelo Johann / 1999
Algoritmos para roteamento de canal:
•
•
•
•
•
•
Left-Edge;
Dogleg;
Y-K;
Greedy;
YACR2;
Hierárquico;
Roteamento de switch boxes
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
O Algoritmo Left-Edge:
• segmentos que unam todos os pinos das redes
• ordena segmentos pelo canto esquerdo
• para cada trilha toma um a um os primeiros
segmentos que couberem no final desta
Instância de um canal
1 5 0 0 2 1 0 0 3 4 6
HCG
VCG
1
5
5
6
2
4
6
2
4
3
3 0 1 0 5 3 4 6 0 2 3
1
3
1
1
3
5
3
4
6
5
2
2
4
6
4
1
2
5
6
3
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
O Algoritmo Greedy:
Faz o roteamento coluna a coluna, em 5 passos:
• 1 - conecta novo pino à trilha mais próxima
• 2 - conecta trilhas que possuem a mesma rede
• 3 - reduz distância entre redes em mais de 1 trilha
• 4 - aproxima redes da borda destino (topo ou base)
• 5 - insere nova trilha para novo terminal
1 5 0 0 2 1 0 0 3 4 6
4
1
2
5
6
3
3 0 1 0 5 3 4 6 0 2 3
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
2.5 Roteamento Global
• Roteamento global para General Cells:
– espaços são canais ou caixas; ordenação
• Roteamento global para leiaute em bandas:
– conexões verticais com feedthroughs;
• Encontrar árvores para cada rede
– otimizar árvore e reduzir congestionamento;
• Roteamento global de área
– divisão arbitrária gera grafo regular;
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Exemplos de roteamento global:
Terminais de uma rede e
conexões possíveis
Grafo de todas
conexões possíveis
Árvore de
menor tamanho
Novos Algoritmos para Roteamento de Área
Árvore com caminhos
mais eqüilibrados
- Marcelo Johann / 1999
3
Algoritmos de
Pesquisa de Caminhos
•
•
•
•
•
Definição do problema;
Princípios da pesquisa
Algoritmos de pesquisa;
Propriedades em pesquisa heurística;
Observações sobre pesquisa heurística
bidirecional;
• O algoritmo LCS*
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
3.1 Definição do Problema
Em um grafo localmente finito G=(V,E),
encontrar o caminho mais curto entre nodos
origem s e destino t - menor custo aditivo.
v5
v1
s v3
v4
v6
v8
v2
v9
Novos Algoritmos para Roteamento de Área
t
v7
- Marcelo Johann / 1999
3.2 Princípios da Pesquisa
A partir de s, formar uma árvore de pesquisa pela
aplicação repetitiva do operador de sucessão
Um nodo é expandido quando se aplica a operação
de sucessão sobre ele (o nodo se torna fechado)
Um nodo é gerado quando é retornado pela
operação de sucessão (o nodo se torna aberto)
v
5
v
1
sv
v4
3
v2
v
6
v8
v9
Novos Algoritmos para Roteamento de Área
t
v7
- Marcelo Johann / 1999
3.3 Algoritmos de Pesquisa
Pesquisa em Profundidade (Depth-First)
Tão logo um novo nodo é gerado ele é selecionado
para ser expandido (LIFO).
s
Novos Algoritmos para Roteamento de Área
t
- Marcelo Johann / 1999
Pesquisa em Largura (Breadth-First)
Primeiro expande todos os nodos a uma mesma
distância da origem (FIFO).
Pesquisa
intermediária
destino
origem
Pesquisa
completa
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Pesquisa Heurística (A*)
Primeiro expande os nodos mais promissores,
segundo a função: f(n) = g(n) + h(n)
Efeito da eficiência
das estimativas
Pesquisa
intermediária
origem
g(n)
destino
h(n)
Pesquisa
completa
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Pesquisa Bidirecional
Duas frentes simultâneas de pesquisa
• nodo de encontro: reconhecido por ambas
• condição de término: f(n) > min[f(m)]
• sobreposição
Pesquisa do
destino
Pesquisa da
origem
destino
m
origem
Pesquisa
unidirecional
Novos Algoritmos para Roteamento de Área
Nodo de
encontro
- Marcelo Johann / 1999
Pesquisa Heurística bidirecional
Objetivo: Unir as vantagens de ambas
Dificuldades:
• problema das frentes desencontradas
• intersecção das pesquisas
• condição de término
Bi-BFS
Objetivo
Suposto problema
das frentes
desencontradas
Bi-A*
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Wave-Shapping (frente-a-frente)
Calcula distância até cada nodo da frente oposta
f(n) = gs (n) + min[k(n,pi) + gt (pi)]
pi
t
s
gt(pi)
gs(n)
n
k(n,pi )
Requer tempo (ou espaço) quadrático para tal
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Pesquisa por perímetro
Dois processos de pesquisa seguidos
o primeiro BFS e o segundo A* ou IDA*, geralmente
Primeira pesquisa,
até um perímetro
determinado
pi
t
Segunda pesquisa,
com estimativas
frente-a-frente
gt(pi)
gs(n)
s
n
k(n,pi )
Demonstra potencial dos heurísticos bidirecionais
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
3.4 Propriedades em pesquisa heurística
• Admissibilidade (*): custo de n a t  h(n)
h(n)
garante menor caminho
t
n
Menor caminho
de n a t
• Consistência: k(n1,n2) + k(n2,n3)  k(n1,n3)
só expande nodos com
n2
k(n ,n )
custo mínimo conhecido
k(n ,n )
2
1
h(n) = k(n,t)
n1
Novos Algoritmos para Roteamento de Área
2
k(n1,n3)
- Marcelo Johann / 1999
3
n3
3.5 Pesquisa Heurística bidirecional
• problema das frentes desencontradas é insignificante
• o poder de um algoritmo heurístico admissível não está em
quão rápido ele encontra um caminho da origem ao
destino, mas em quão rápido ele pode computar valores
mais altos de f() para os nodos que gera.
• a função g() de uma frente corresponde à h() da oposta
• estimação: a) estática, b) dinâmica, c) frente a frente
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
3.6 Algoritmo LCS*
•
•
•
•
•
•
Lowerbound Cooperative Search
estimação dinâmica (resistência e penalidade)
estrutura semelhante ao BS* de [Kwa 89]
visibilidade: valores estimados em referências
visibilidade: conjunto de nodos fechados único
“perfeição” e admissibilidade provadas
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Estimação dinâmica
• Resistência (min idea [Kaindl 96])
gt(pi)
Rt = Min[gt(pi) - k(pi,t)]
F(n) = f(n) + Rt
pi
t
k(pi ,t)
• Penalidade (max idea [Kaindl 96])
pi
Pt = Min[gt*(pi) - k(pi,s)]
F(n) = gs(n) + Pt - ht(n)
t
ht(pi)
gt(pi)
s
ht(n)
gs(n)
hs(n)
n
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Resultados preliminares de LCS*
Em grafos aleatórios
70 nodos, distância 1000 de 1000, 1 arco por nodo [solúveis]
A*s average search nodes =
A* best search nodes =
A* worst search nodes =
LCS* nodes =
126156
71576
180736
77710
78306
61016
95596
59869
Em grafos geométricos
70 nodos, distância 300 de 1000, 10% conexões [+ 1 arco]
A*s average nodes =
A* best search nodes =
A* worst search nodes =
LCS* nodes =
39095
24438
53752
38662
Novos Algoritmos para Roteamento de Área
28406
21428
35384
34130
- Marcelo Johann / 1999
Resultados preliminares de LCS*
Em grade, admissibilidade completa
350000
300000
250000
200000
150000
100000
50000
0
LCS*
melhor A*
0
50
0
46
0
42
0
38
0
34
0
30
0
26
0
22
0
18
0
14
0
pior A*
10
total de nodos
expandidos
Grade 200 por 200 com custos aleatórios, média
100, mínimo 50, máximo 300
variação de custos aleatórios gerados
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Resultados preliminares de LCS*
Em grade, admissibilidade relativa
350000
300000
250000
200000
150000
100000
50000
0
LCS*
melhor A*
0
50
0
46
0
42
0
38
0
34
0
30
0
26
0
22
0
18
0
14
0
pior A*
10
total de nodos
expandidos
Grade 200 por 200 com custos aleatórios, média
100, mínimo 50, máximo 300
variação de custos aleatórios gerados
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
4
Roteamento de Área
• grande área livre, sem estrutura
• terminais e obstáculos arbitrários
decomposição necessária
para roteamento detalhado
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
4.1 Decomposição em caixas de conexão
• divisão arbitrária do espaço em GRCs
• assinalamento de pontos de cruzamento (CPA)
• roteamento detalhado de caixas de conexão
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
4.2 Roteamento de área sem decomposição
• Left-Edge ignoraria restrições verticais
• Greedy não otimizaria conexões verticais
Mas um opera linha a linha e o outro coluna a coluna
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
4.3 O algoritmo LEGAL
•
•
•
•
•
opera linha por linha, como um Greedy
realiza conexões com critério Left-Edge
faz roteamento detalhado integral (todas conexões)
não avalia a área repetidas vezes como maze routers
resultados preliminares indicaram alta eficiência
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
5
Roteamento com
o Algoritmo LCS*
Propostas:
5.1 Técnicas de otimização em espaço regular;
5.2 Pesquisa com múltiplos destinos
5.3 Formação de redes
5.4 Modelos de custo
5.5 Outras técnicas de pesquisa
5.6 Pesquisa básica
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
5.2 Pesquisa com múltiplos destinos
• Seleção de destino
por retângulo envolvente
t1
t2
s
• Seleção de destino
mais próximo
t1
t2
s
• Cálculo de janela
de aproximação
Novos Algoritmos para Roteamento de Área
t1
t2
s
- Marcelo Johann / 1999
5.3 Formação de redes
• Formação de redes de comprimento mínimo
Apagando o custo g()
nos caminhos já
encontrados
g()=0
g()=0
g()=0
g()=0
Driver
• Formação de redes de caminhos mínimos
g()=5
Mantendo o custo g()
nos caminhos já
encontrados
g()=9
g()=7
g()=0
Driver
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
5.4 Modelos de custo
• referências e movimentos
• o que representam os valores:
–
–
–
–
–
comprimento da conexão;
desempenho elétrico da conexão, em função de RC;
quantidade de recursos utilizados
dificuldade pela presença de obstáculos;
congestionamento devido a outras conexões;
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
6
Roteamento com
o Algoritmo LEGAL
Propostas:
• Definição precisa
– relacionamento com roteamento global
– comparações de problemas “genéricos”
• Adaptação a situações práticas
– inserção de espaços no roteamento
– inserção de espaços no posicionamento
– roteamento em até 4 camadas
– roteamento com conexões de largura variável
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
7
Conclusões
e Cronograma
Conclusões
• LCS*: bidirecional, heurístico e eficiente
• aplicação de LCS* a roteamento VLSI
redes individuais, ambiente complexo
• LEGAL: detalhado, integral, eficiente
• definição e adaptação às aplicações
área livre, acomoda melhor as conexões
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999
Cronograma:
• novembro:
testes e implementação de roteador com LCS*
infra-estrutura: multi-grade, modelos, estruturas
• dezembro:
continuação
• janeiro:
implementação do LEGAL
testes: LCS* vs. LEGAL, LCS* + LEGAL
• fevereiro:
escrita do texto da tese
Novos Algoritmos para Roteamento de Área
- Marcelo Johann / 1999