B8 Algoritmos para Síntese Física
Marcelo Johann
EMICRO2004
Resumo
•
•
•
•
•
•
Introdução
Algoritmos de Particionamento
Algoritmos de Posicionamento
Algoritmos de Roteamento
Problemas de Assinalamento
Outros Problemas de Leiaute
EMICRO 2004 - Marcelo Johann - B8.2
1 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;
EMICRO 2004 - Marcelo Johann - B8.3
1 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;
EMICRO 2004 - Marcelo Johann - B8.4
2 Particionamento
Circuito representado por um grafo G=(V,E)
• bi-partitioning, multi-way-particioning;
componentes
redes
v7
v3
v2
v4
v5
v8
v9
v1
v8
v3
v1
v4
v5
v7
v2
v6
v6
EMICRO 2004 - Marcelo Johann - B8.5
v9
2 Particionamento
• 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;
EMICRO 2004 - Marcelo Johann - B8.6
2 Particionamento
• Algoritmo de Kernighan-Lin;
troca par com menor D(i) + D(j)
onde D(i) = inedge(i) - outedge(i)
v1
v3
v4
v5
v2
v3
v4
v6
i
1
2
3
4
5
6
inedge
21
21
20
20
21
21
EMICRO 2004 - Marcelo Johann - B8.7
outedge
1
0
12
13
13
12
1
0
D
0
2
1-1
1-3
1-3
1-1
0
2
2 Particionamento
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, …
EMICRO 2004 - Marcelo Johann - B8.8
3 Posicionamento
Encontrar posição das células no circuito.
Qualidade do posicionamento define a
dificuldade do roteamento
EMICRO 2004 - Marcelo Johann - B8.9
3.1 Funções Objetivo
• minimizar comprimento total de conexões;
• minimizar densidades máximas de conexões;
EMICRO 2004 - Marcelo Johann - B8.10
3.1 Funções Objetivo
Funções objetivo para posicionamento:
• minimizar número
de conexões que
cortam linhas
imaginárias;
EMICRO 2004 - Marcelo Johann - B8.11
3.1 Funções Objetivo
Funções objetivo para posicionamento:
• minimizar
atrasos em
caminhos
críticos;
EMICRO 2004 - Marcelo Johann - B8.12
3.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;
EMICRO 2004 - Marcelo Johann - B8.13
3.2 Abordagens
Abstração da área
• Posicionamento com sobreposições
Etapas
• Posicionamento global
• Posicionamento detalhado
• Legalização
– Respeitar slots, grade, espelhamento
EMICRO 2004 - Marcelo Johann - B8.14
3.3 Por particionamento
Posicionamento baseado em partições
sucessivas (recursive bisection):
• Seqüências de cortes para posicionamento
por partições:
EMICRO 2004 - Marcelo Johann - B8.15
3.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;
EMICRO 2004 - Marcelo Johann - B8.16
3.5 Simulated Annealing
Perturbação
Custo
Rejeita / Aceita
Três funções básicas: Temperature Schedule (acima), Custo
(comprimento) e Perturbação (como modificar a solução atual).
EMICRO 2004 - Marcelo Johann - B8.17
3.6 Planta Baixa
Algoritmos para Planejamento topológico:
• blocos duros ou flexíveis;
• bipartições, estruturas topológicas;
1
B
2
3
4
7
H
A
5
C
6
F
F
G
H
I
D
E
I
A
8
B
D
C
• Geralmente só minimizam área
EMICRO 2004 - Marcelo Johann - B8.18
E
G
4 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
EMICRO 2004 - Marcelo Johann - B8.19
4.1 Classificação
Classificação de roteamento por objetivos:
• Roteamento detalhado
• Roteamento global
• Roteamento especializado
EMICRO 2004 - Marcelo Johann - B8.20
4.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
EMICRO 2004 - Marcelo Johann - B8.21
roteamento de área
4.1 Classificação
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,...
EMICRO 2004 - Marcelo Johann - B8.22
4.1 Classificação
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;
EMICRO 2004 - Marcelo Johann - B8.23
4.1 Classificação
• 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ão
roteamento planar ...
EMICRO 2004 - Marcelo Johann - B8.24
4.2 Maze Router (BFS)
pesquisa em largura numa grade (Lee 1961)
• expansão
• retraço
• reinicialização
problemas
• tempo
• memória
• ordenação
garantia
generalidade
EMICRO 2004 - Marcelo Johann - B8.25
4.3 Roteamento de Canal
• Modelo de canal: espaço entre duas bandas;
• definição: terminais superiores e inferiores;
• dificuldade de roteamento: horizontal;
EMICRO 2004 - Marcelo Johann - B8.26
4.3 Roteamento de Canal
Algoritmos para roteamento de canal:
• Left-Edge;
• Dogleg;
• Y-K;
• Greedy;
• YACR2;
• Hierárquico;
Roteamento de switch boxes
EMICRO 2004 - Marcelo Johann - B8.27
4.3 Algoritmo Left-Edge
• segmentos que unam todos os pinos das redes
Instância de um canal
1 5
0 0
2
1
0
0
3
1
4 6
5
6
2
4
3
0
1
0
5
3
4
6
0
2
HCG
3
1
3
5
2
4
6
EMICRO 2004 - Marcelo Johann - B8.28
3
4.3 Algoritmo Left-Edge
• segmentos que unam todos os pinos das redes
Instância de um canal
1 5
0 0
2
1
0
0
3
HCG
1
4 6
5
6
2
4
3
0
1
0
5
3
4
6
1
0
2
3
3
1
VCG
5
3
5
6
2
2
4
6
EMICRO 2004 - Marcelo Johann - B8.29
4
3
4.3 Algoritmo Left-Edge
• máximo clique de HCG define mínima altura
Instância de um canal
1 5
trilha
trilha
trilha
trilha
0 0
2
1
0
0
3
1
4 6
1
2
3
4
HCG
5
6
2
4
3
0
1
0
5
3
4
6
1
0
2
3
3
1
VCG
5
3
5
6
2
2
4
Obrigado!!!
6
EMICRO 2004 - Marcelo Johann - B8.30
4
3
4.3 Algoritmo Left-Edge
• máximo clique de HCG define mínima altura
Instância de um canal
1 5
trilha
trilha
trilha
trilha
0 0
2
1
1
2 3
3
4
1
0
0
3
1
4 6
HCG
5
4
6
5
2
6
2
4
3
0
1
0
5
3
4
6
0
2
3
3
1
VCG
5
6
2
4
3
EMICRO 2004 - Marcelo Johann - B8.31
4.3 Algoritmo Left-Edge
• combinar os nodos de VCG na mesma trilha
Instância de um canal
1 5
trilha
trilha
trilha
trilha
0 0
2
1
0
0
3
1
4 6
1
2
3
4
HCG
5
6
2
4
3
0
1
0
5
3
4
6
0
2
3
3
1
VCG
5
6
1
2
4
3
5
6
2
4
3
EMICRO 2004 - Marcelo Johann - B8.32
4.3 Algoritmo Left-Edge
• combinar os nodos de VCG na mesma trilha
Instância de um canal
1 5
trilha
trilha
trilha
trilha
0 0
2
1
0
0
3
1
4 6
1
2
3
4
HCG
5
6
2
4
3
0
1
0
5
3
4
6
0
2
3
3
VCG
1
1,4
5,6
2
4
3
5
6
2
3
EMICRO 2004 - Marcelo Johann - B8.33
4.3 Algoritmo Left-Edge
• VCG não pode ter ciclos para fazer conexões
Instância de um canal
1 5
trilha
trilha
trilha
trilha
0 0
2
1
1
0
0
3
HCG
1
4 6
5
4
1
2
3
4 3
2
6
5
2
6
4
3
0
1
0
5
3
4
6
0
2
3
3
VCG
1,4
5,6
Obrigado!!!
Mas e se tiver ciclos???
2
3
EMICRO 2004 - Marcelo Johann - B8.34
4.3 Algoritmo Greedy
• opera da esquerda para a direita estendendo trilhas
• busca unir ou aproximar redes divididas
• a cada coluna executa 5 passos:
1)
2)
Insere novo pino
em trilha livre
3)
Une redes
divididas
4)
Aproxima trechos
de redes divididas
5)
Aproxima redes de
próximos pinos
EMICRO 2004 - Marcelo Johann - B8.35
Insere nova
trilha
4.4 Roteamento Planar
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;
EMICRO 2004 - Marcelo Johann - B8.36
4.4 Roteamento Planar
Roteamento planar de uma caixa:
EMICRO 2004 - Marcelo Johann - B8.37
4.4 Roteamento Planar
Roteamento em rio (river routing):
EMICRO 2004 - Marcelo Johann - B8.38
4.4 Roteamento Planar
Single Row Routing Problem (SRRP):
EMICRO 2004 - Marcelo Johann - B8.39
4.5 Roteamento Global
• 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
EMICRO 2004 - Marcelo Johann - B8.40
4.5 Roteamento Global
• Roteamento Global de Área:
– divide-se a área em células globais;
– distribuir as conexões
EMICRO 2004 - Marcelo Johann - B8.41
4.5 Roteamento Global
• Roteamento Global para leiaute em bandas:
– conexões verticais com feedthroughs;
• Encontrar árvores para cada rede
EMICRO 2004 - Marcelo Johann - B8.42
5 Assinalamento
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;
EMICRO 2004 - Marcelo Johann - B8.43
6 Outros Problemas
•
•
•
•
•
•
•
•
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;
EMICRO 2004 - Marcelo Johann - B8.44
B8 Algoritmos para Síntese Física
EMICRO2004
Marcelo Johann
[email protected]
www.inf.ufrgs.br/~johann