Novos Algoritmos para Roteamento de Área Aluno:Marcelo Johann Orientador:Ricardo Reis Proposta de Tese

Novos Algoritmos para Novos Algoritmos para Roteamento de Área Roteamento de Área

Aluno:Aluno: Marcelo JohannMarcelo JohannOrientador:Orientador: Ricardo ReisRicardo Reis

Proposta de TeseProposta de Tese

Novos Algoritmos para Roteamento de Área - Marcelo Johann / 1999

ResumoResumo

• 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


IntroduçãoIntroduçã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;

11


Algoritmos de RoteamentoAlgoritmos de Roteamento

Algoritmos de roteamento solucionam problemas de roteamento.

• Classificação

• Algoritmos de Roteamento Genéricos

• Roteamento de Canal

• Roteamento Global

22


• Roteamento detalhado

• Roteamento global

• Roteamento especializado

2.1 2.1 ClassificaçãoClassificação

Classificação de roteamento por objetivos:


• espaços dedicados: canais e switch boxes;

• sobre as células, roteamento de área,...

Classificação de roteamentoquanto ao espaço:

general cell standard cells roteamento de área


• 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;

Classificação dos algoritmos de roteamento quanto ao processamento:


• 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 canalcaixas de conexão

roteamento planar ...

Classificação dos algoritmos de roteamento quanto à aplicação:


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;

2.2 2.2 Algoritmos de Roteamento GenéricosAlgoritmos de Roteamento Genéricos


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


• Modelo de canal: espaço entre duas bandas;

• definição: terminais superiores e inferiores;

• dificuldade de roteamento: horizontal;

2.32.3 Roteamento de Canal Roteamento de Canal

1 2 0 0 0

0 0 0

0

01

4

42 3 35

56 6

trilhas

dogleg

branches

Números das redes

terminais

base, ou borda inferior

topo, ou borda superior

vias

segmentos (trunks)n = 6h = 3l = 10


• Left-Edge;

• Dogleg;

• Y-K;

• Greedy;

• YACR2;

• Hierárquico;

Roteamento de switch boxes

Algoritmos para roteamento de canal:


• 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

O Algoritmo Left-Edge:

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4

HCG VCGInstância de um canal1

2

34

5

6

1

2

34

5

6

13

52

46

13

52

4

6

1

35

24

6


1

35

24

6

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

O Algoritmo Greedy:

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


• 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;

2.52.5 Roteamento Global Roteamento Global


Grafo de todasconexões possíveis

Árvore demenor tamanho

Árvore com caminhosmais eqüilibrados

Terminais de uma rede econexões possíveis

Exemplos de roteamento global:


• 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*

Algoritmos de Algoritmos de Pesquisa de Caminhos Pesquisa de Caminhos 33


3.13.1 Definição do Problema 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.

v1

v2

v3v4

v5

v6

v7v8

v9

st


3.23.2 Princípios da Pesquisa 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)

v1

v2

v3

v4

v5

v6

v7v8

v9

s t


3.33.3 Algoritmos de Pesquisa Algoritmos de Pesquisa

Pesquisa em Profundidade (Depth-First)Tão logo um novo nodo é gerado ele é selecionado

para ser expandido (LIFO).

st


Pesquisa em Largura (Breadth-First)

Primeiro expande todos os nodos a uma mesma distância da origem (FIFO).

origem

destino

Pesquisa intermediária

Pesquisa completa


Pesquisa Heurística (A*)

Primeiro expande os nodos mais promissores, segundo a função: f(n) = g(n) + h(n)

origem destino

Pesquisa intermediária

Pesquisa completa

g(n) h(n)

Efeito da eficiência

das estimativas


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

origem

destino

Pesquisa da origem

Pesquisa unidirecional

Pesquisa do destino

Nodo de encontro

m


Pesquisa Heurística bidirecional

Objetivo: Unir as vantagens de ambas

Dificuldades:• problema das frentes desencontradas• intersecção das pesquisas• condição de término

Suposto problema das frentes desencontradas

Objetivo

Bi-A*

Bi-BFS


Wave-Shapping (frente-a-frente)

Calcula distância até cada nodo da frente oposta

f(n) = gs (n) + min[k(n,pi) + gt (pi)]

gs(n) gt(pi)

k(n,pi )

s

n

t

pi

Requer tempo (ou espaço) quadrático para tal


Pesquisa por perímetro

Dois processos de pesquisa seguidos

o primeiro BFS e o segundo A* ou IDA*, geralmente

gs(n)

gt(pi)

k(n,pi ) s n

t

pi

Primeira pesquisa, até um perímetro determinado

Segunda pesquisa, com estimativas frente-a-frente

Demonstra potencial dos heurísticos bidirecionais


3.43.4 Propriedades em pesquisa heurística Propriedades em pesquisa heurística

• Admissibilidade (**): custo de n a t h(n)

garante menor caminho

• Consistência: k(n1,n2) + k(n2,n3) k(n1,n3)

só expande nodos com

custo mínimo conhecido

n1

n2

n3k(n1,n2)

k(n2,n3)

k(n1,n3)

tn

h(n)

Menor caminho de n a t

h(n) = k(n,t)


3.53.5 Pesquisa Heurística bidirecional 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

s t

abn

mn

s ta

bn

mn

a) Esforço necessário em Bi-A*b) Esforço mínimo desejado em pesquisa bidirecionalcooperativa.


3.63.6 Algoritmo LCS* 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


• Resistência (min idea [Kaindl 96])

• Penalidade (max idea [Kaindl 96])

gs(n)

gt(pi)

s n

t

pi

ht(n) hs(n)

ht(pi)

gt(pi) t

pi

k(pi ,t)

Rt = Min[gt(pi) - k(pi,t)]

Pt = Min[gt*(pi) - k(pi,s)]

Estimação dinâmica

F(n) = f(n) + Rt

F(n) = gs(n) + Pt - ht(n)


Resultados preliminares de LCS*

Em grafos aleatórios70 nodos, distância 1000 de 1000, 1 arco por nodo [solúveis] A*s average search nodes = 126156 78306

A* best search nodes = 71576 61016

A* worst search nodes = 180736 95596

LCS* nodes = 77710 59869

Em grafos geométricos70 nodos, distância 300 de 1000, 10% conexões [+ 1 arco] A*s average nodes = 39095 28406

A* best search nodes = 24438 21428

A* worst search nodes = 53752 35384

LCS* nodes = 38662 34130



Grade 200 por 200 com custos aleatórios, média 100, mínimo 50, máximo 300

050000

100000150000200000250000300000350000

100

140

180

220

260

300

340

380

420

460

500

variação de custos aleatórios gerados

tota

l de

no

do

s

ex

pa

nd

ido

s

LCS*

melhor A*

pior A*

Em grade, admissibilidade completa



Grade 200 por 200 com custos aleatórios, média 100, mínimo 50, máximo 300

050000

100000150000200000250000300000350000

100

140

180

220

260

300

340

380

420

460

500

variação de custos aleatórios gerados

tota

l de

no

do

s

ex

pa

nd

ido

s

LCS*

melhor A*

pior A*

Em grade, admissibilidade relativa


• grande área livre, sem estrutura • terminais e obstáculos arbitrários

Roteamento de ÁreaRoteamento de Área 44

decomposição necessária

para roteamento detalhado


4.14.1 Decomposição em caixas de conexão 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


4.24.2 Roteamento de área sem decomposição 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


4.34.3 O algoritmo LEGAL 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


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

Roteamento com Roteamento com o Algoritmo LCS* o Algoritmo LCS* 55


5.25.2 Pesquisa com múltiplos destinos Pesquisa com múltiplos destinos

• Seleção de destino

por retângulo envolvente

• Seleção de destino

mais próximo

• Cálculo de janela

de aproximação

s

t1

t2

t1

st2

s

t1

t2


5.35.3 Formação de redes Formação de redes

• Formação de redes de comprimento mínimo

• Formação de redes de caminhos mínimos

Apagando o custo g() nos caminhos já encontrados

Mantendo o custo g() nos caminhos já encontrados Driver

Driver

g()=0

g()=0g()=0

g()=0

g()=0

g()=5g()=9

g()=7


5.45.4 Modelos de custo 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;


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

Roteamento com Roteamento com o Algoritmo LEGAL o Algoritmo LEGAL 66


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

Conclusões Conclusões e Cronograma e Cronograma 77


• 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

Cronograma:

Documents

Novos Algoritmos para Roteamento de Área Aluno:Marcelo Johann Orientador:Ricardo Reis Proposta de Tese