Algoritmos para Síntese Física B8 EMICRO2004 Marcelo Johann

Algoritmos para Síntese FísicaAlgoritmos para Síntese FísicaB8B8

EMICRO2004

Marcelo JohannMarcelo Johann

EMICRO 2004 - Marcelo Johann - B8.2

ResumoResumo

• Introdução

• Algoritmos de Particionamento

• Algoritmos de Posicionamento

• Algoritmos de Roteamento

• Problemas de Assinalamento

• Outros Problemas de Leiaute


1 Introdução1 Introdução

Particionamento é a tarefa de dividir um circuito em duas ou mais partes:

• para dividir um problema em problemas de menor complexidade;

• para acomodar o circuito em diferentes dispositivos;

• para se obter um bom posicionamento;


1 Introdução1 Introdução

Posicionamento é a tarefa de encontrar uma posição para cada bloco ou célula que compõe o circuito sobre a área de silício:

• para planejamento topológico;

• ou em bandas;– relativo;– absoluto;


2 Particionamento2 Particionamento

Circuito representado por um grafo G=(V,E)

• bi-partitioning, multi-way-particioning;

v1

v2

v3

v4

v5

v6

v7

v8

v9

v1

v2

v3 v4

v5

v6

v7

v8

v9

componentes

redes



• Algoritmos podem ser:– construtivos ou iterativos;– determinísticos ou probabilísticos;

• Critérios de qualidade:– corte mínimo;– área de cada partição;– número de partições; – número de terminais;– atraso em redes críticas;



• Algoritmo de Kernighan-Lin;troca par com menor D(i) + D(j)onde D(i) = inedge(i) - outedge(i)

v1

v2

v3

v4

v5

v3

v4v3

v4 v6

i inedge outedge D

1 1 1 02 1 2 -13 0 3 -34 0 3 -35 1 2 -16 1 1 0

i inedge outedge D

1 2 0 22 2 1 13 2 1 14 2 1 15 2 1 16 2 0 2



Algoritmos por migração de grupos:• Algoritmo de Kernighan-Lin;

troca pares de nodos• Algoritmo de Fiduccia-Mattheyses;

troca apenas um nodo a cada vez• Algoritmo de Goldberg e Burstein;

contração de vértices• Replicação de componentes;

Outros Algoritmos: aglomerados, simulação, multi-nível, …


3 Posicionamento3 PosicionamentoEncontrar posição das células no circuito.

Qualidade do posicionamento define a dificuldade do roteamento


• minimizar comprimento total de conexões;• minimizar densidades máximas de conexões;

3.1 Funções Objetivo3.1 Funções Objetivo


Funções objetivo para posicionamento:

• minimizar número de conexões que cortam linhas imaginárias;



• minimizar atrasos em caminhos críticos;

Funções objetivo para posicionamento:



3.2 Estimativas3.2 Estimativas

Estimativa do tamanho das conexões:

• semi-perímetro do retângulo envolvente;• grafo completo;

• cadeia mínima;

• fonte para carga;

• árvore de Steiner;

• árvore mínima;


3.2 Abordagens3.2 Abordagens

Abstração da área

• Posicionamento com sobreposições

Etapas

• Posicionamento global

• Posicionamento detalhado

• Legalização– Respeitar slots, grade, espelhamento


3.3 Por particionamento3.3 Por particionamento

Posicionamento baseado em partições sucessivas (recursive bisection):

• Seqüências de cortes para posicionamento por partições:


3.4 Outros Algoritmos3.4 Outros Algoritmos... para posicionamento em bandas:• Formação de aglomerados, dirigidos por força• Algoritmos de otimização combinatorial:

– Simulação de resfriamento, simulação evolutiva, programação linear, assinalamento quadrático, redes resistivas, redes neurais, etc...

• Posicionamento Analítico – programação inteira para distribuir células

• Algoritmos mais usados:– simulação de resfriamento, recursive bisection;– particionamento multi-nível, analíticos;


3.5 3.5 Simulated AnnealingSimulated Annealing

Três funções básicas: Temperature Schedule (acima), Custo (comprimento) e Perturbação (como modificar a solução atual).

Perturbação

Custo

Rejeita / Aceita


3.6 Planta Baixa3.6 Planta Baixa

Algoritmos para Planejamento topológico:• blocos duros ou flexíveis;• bipartições, estruturas topológicas;

• Geralmente só minimizam área

1234756FGHIDEA8BCFGADEBCHI


4 Roteamento4 Roteamento

Estabelece as rotas de conexão entre pinos de E/S usando camadas metálicas e furos.

• Classificação

• Algorítmos de Roteamento Genéricos

• Roteamento de Canal

• Roteamento Planar

• Roteamento Global


Classificação de roteamento por objetivos:

• Roteamento detalhado

• Roteamento global

• Roteamento especializado

4.1 Classificação4.1 Classificação


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 roteamento de área


Classificação quanto à modelagem do espaço:

• roteamento sobre grade (e simbólico);

• roteamento topológico;

• roteamento ortogonal ou com ângulos (45o);

• larguras e espaçamentos arbitrários;

• modelos: forma da área, número de camadas, modelo de células, posição dos terminais, terminais eqüipotenciais, restrições,...



Classificação 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;




• genéricos: podem ser aplicados a muitos problemas diferentes de roteamento;

ex: maze routers = breadth-first search

• 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ãoroteamento planar ...


4.2 4.2 Maze Router (BFS)Maze Router (BFS)

pesquisa em largura numa grade (Lee 1961)• expansão• retraço• reinicialização

problemas• tempo• memória• ordenaçãogarantiageneralidade


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

• definição: terminais superiores e inferiores;

• dificuldade de roteamento: horizontal;

4.3 Roteamento de Canal4.3 Roteamento de Canal


Algoritmos para roteamento de canal:

• Left-Edge;

• Dogleg;

• Y-K;

• Greedy;

• YACR2;

• Hierárquico;

Roteamento de switch boxes

4.3 Roteamento de Canal4.3 Roteamento de Canal


4.3 Algoritmo 4.3 Algoritmo Left-EdgeLeft-Edge

• segmentos que unam todos os pinos das redes

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4

Instância de um canal HCG1

2

34

5

6

1

3

5

2

4

6



• segmentos que unam todos os pinos das redes

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


2

34

5

6

VCG 1

2

34

5

6

1

3

5

2

4

6



• máximo clique de HCG define mínima altura

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


2

34

5

6

VCG 1

2

34

5

6

1

3

5

2

4

6

trilha 1trilha 2trilha 3trilha 4

Obrigado!!!



• máximo clique de HCG define mínima altura

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4

Instância de um canal

VCG 1

2

34

5

6


3

2

1 4

5 6

HCG1

2

34

5

6


VCG 1

2

34

5

6


• combinar os nodos de VCG na mesma trilha

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


VCG

HCG1

2

34

5

6trilha 1trilha 2trilha 3trilha 4

VCG 1

2

34

5

6

3

2

1 4

5 6



• combinar os nodos de VCG na mesma trilha

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


VCG5,6

1,4

2

3

HCG1

2

34

5

6trilha 1trilha 2trilha 3trilha 4

3

2

1 4

5 6



• VCG não pode ter ciclos para fazer conexões

1 05 0 0 6

0 6 0

2

0 2

1 0

1 53

3

3 3

4

4


2

34

5

6

VCG5,6

1,4

2

3

Mas e se tiver ciclos???


Obrigado!!!

1 42

5 63


4.3 Algoritmo 4.3 Algoritmo GreedyGreedy

Insere novo pinoem trilha livreUne redesdivididasAproxima trechosde redes divididasAproxima redes depróximos pinos Insere novatrilha5)1)2)3)4)

• opera da esquerda para a direita estendendo trilhas• busca unir ou aproximar redes divididas• a cada coluna executa 5 passos:


Roteamento usando apenas uma camada, não possui vias (furos). As vias:

• tem menor confiabilidade de fabricação;

• geram maior atraso por aumento de R;

• reduzem imunidade a ruído pela introdução de resistências em série;

• necessitam maior área devido a margem dos metais sobre os furos;

4.4 Roteamento Planar4.4 Roteamento Planar


Roteamento planar de uma caixa:



Roteamento em rio (river routing):



Single Row Routing Problem (SRRP):



• Roteamento Global para General Cells:– reconhecimento e/ou definição dos espaços;– ordenação dos canais;– grafo modela espaços como vértices ou arestas

4.5 Roteamento Global4.5 Roteamento Global


• Roteamento Global de Área:– divide-se a área em células globais;– distribuir as conexões



• Roteamento Global para leiaute em bandas:– conexões verticais com feedthroughs;

• Encontrar árvores para cada rede



Encontrar um mapeamento bi-unívoco entre dois conjuntos. Pode ser linear, quadrático, etc...

• Assinalamento de portas;

• Assinalamento de pinos;

• Assinalamento de terminais às bordas;

• Assinalamento de pontos de cruzamento;

5 Assinalamento5 Assinalamento


• Minimização de vias, de doglegs;

• compactação (de canal, geral, 1D, 2D);

• ordenação de transistores;

• alinhamento de terminais ou feedthroughs;

• formação de redes com reforçadores;

• verificação de regras de projeto (DRC);

• extração, cálculo de criticalidade do leiaute;

• processamento para exibição, fabricação;

6 Outros Problemas6 Outros Problemas

Algoritmos para Síntese FísicaAlgoritmos para Síntese FísicaB8B8EMICRO2004

Marcelo JohannMarcelo Johann

[email protected]

www.inf.ufrgs.br/~johann

That’s all!

Documents

Algoritmos para Síntese Física B8 EMICRO2004 Marcelo Johann