Projeto de Circuitos Integrados Um estudo dos algoritmos envolvidos e sua aplicabilidade em relação ao desenho de grafos, baseado no livro: Combinatorial

Projeto de Projeto de Circuitos Circuitos IntegradosIntegradosUm estudo dos algoritmos envolvidos e sua aplicabilidade Um estudo dos algoritmos envolvidos e sua aplicabilidade em relação ao desenho de grafos, baseado no livro: em relação ao desenho de grafos, baseado no livro: “Combinatorial Algorithms for Integrated Circuit Layout” “Combinatorial Algorithms for Integrated Circuit Layout” de de Thomas LengauerThomas Lengauer e e Estrutura de Roteamento em Estrutura de Roteamento em Circuitos Circuitos VLSI VLSI Por MARCELO DE OLIVEIRA JOHANNPor MARCELO DE OLIVEIRA JOHANN

Vitor Pastor Baracho

IntroduçãoIntrodução

O problema de layout de circuitos integrados é um problema de otimização O problema de layout de circuitos integrados é um problema de otimização com restrições. Isto é, dado um circuito (sua descrição, com os com restrições. Isto é, dado um circuito (sua descrição, com os componentes e interconectividade entre eles), o problema se resume a componentes e interconectividade entre eles), o problema se resume a buscar as coordenadas geométricas dos componentes em um plano (ou buscar as coordenadas geométricas dos componentes em um plano (ou em uma das poucas camadas planares) que satisfaz as condições do em uma das poucas camadas planares) que satisfaz as condições do fabricante. Tudo isto deve ser feito minimizando o critério de custo.fabricante. Tudo isto deve ser feito minimizando o critério de custo.

Porém, praticamente todas as versões deste problema são NP-difíceis, e Porém, praticamente todas as versões deste problema são NP-difíceis, e portanto um método heurístico deve ser utilizado. Inicialmente, portanto um método heurístico deve ser utilizado. Inicialmente, quebramos o problema em uma série de subproblemas cuja solução quebramos o problema em uma série de subproblemas cuja solução heurística é mais facilmente aplicável. heurística é mais facilmente aplicável.

Desta séries de subproblemas, dois se mostram úteis ao nosso projeto: o Desta séries de subproblemas, dois se mostram úteis ao nosso projeto: o PLACEMENT e o ROUTING (global-routing + detailed-routing). PLACEMENT e o ROUTING (global-routing + detailed-routing).

Obs.: O livro cita que muitas vezes o algoritmo utilizado não é ótimo devido ao Obs.: O livro cita que muitas vezes o algoritmo utilizado não é ótimo devido ao fato de utilizar o posicionamento dos componentes (placement) antes da fato de utilizar o posicionamento dos componentes (placement) antes da conexão entre eles (routing) – “incompatibilidade entre as funções de custo”. conexão entre eles (routing) – “incompatibilidade entre as funções de custo”. Isto causa a otimização de um fator de custo que pode não ser o mais Isto causa a otimização de um fator de custo que pode não ser o mais significativo, pois prioriza a economia da área de circuito em detrimento das significativo, pois prioriza a economia da área de circuito em detrimento das conexões (que podem ser maiores devido à necessidade de contornar conexões (que podem ser maiores devido à necessidade de contornar componentes previamente posicionados). Isto porém não prejudica nosso componentes previamente posicionados). Isto porém não prejudica nosso problema, visto que a tela sinótica prioriza o tamanho (limitado por uma tela) problema, visto que a tela sinótica prioriza o tamanho (limitado por uma tela) em relação as conexões (que podem até mesmo se cruzar).em relação as conexões (que podem até mesmo se cruzar).

Placement, Assignment and Placement, Assignment and FloorplanningFloorplanning

Dependendo do estilo do layout, PLACEMENT pode ter diferentes objetivos. Dependendo do estilo do layout, PLACEMENT pode ter diferentes objetivos. No nosso caso, o objetivo será de minimizar a área utilizada. A medida No nosso caso, o objetivo será de minimizar a área utilizada. A medida de área considera o espaço utilizado pelos componentes, assim como de área considera o espaço utilizado pelos componentes, assim como pelas conexões. E também os componentes, podem ser atômicos (como pelas conexões. E também os componentes, podem ser atômicos (como transformadores) ou blocos inteiros (como o transformador, juntamente transformadores) ou blocos inteiros (como o transformador, juntamente com um bypass e outros componentes). com um bypass e outros componentes).

O problema de PLACEMENT possui duas vertentes principais: um problema O problema de PLACEMENT possui duas vertentes principais: um problema de empacotamento em duas dimensões e a questão da minimização do de empacotamento em duas dimensões e a questão da minimização do comprimento das conexões. O problema do empacotamento (“packing”) comprimento das conexões. O problema do empacotamento (“packing”) consiste em “encaixar” um número de componentes (ou blocos) de consiste em “encaixar” um número de componentes (ou blocos) de diferentes tamanhos e formatos no menor retângulo possível.diferentes tamanhos e formatos no menor retângulo possível.

A maior dificuldade está no fato de não ser possível estimar precisamente a A maior dificuldade está no fato de não ser possível estimar precisamente a área a ser gasta com as subseqüentes conexões.área a ser gasta com as subseqüentes conexões.

A seção de “Regular Placement” leva em consideração apenas a função de A seção de “Regular Placement” leva em consideração apenas a função de custo de conexão, não considerando o empacotamento. Desta forma, ela custo de conexão, não considerando o empacotamento. Desta forma, ela não é útil ao nosso problema. Portanto irei descrever apenas a seção 7.2, não é útil ao nosso problema. Portanto irei descrever apenas a seção 7.2, sobre “General Placement and Floorplanning” que leva em conta os dois sobre “General Placement and Floorplanning” que leva em conta os dois lados: o empacotamento e as conexões.lados: o empacotamento e as conexões.

Não é possível (hoje) tratar os dois casos simultaneamente (empacotamento Não é possível (hoje) tratar os dois casos simultaneamente (empacotamento e conexões), por isto o livro aborda primeiro a otimização das conexões e conexões), por isto o livro aborda primeiro a otimização das conexões para depois otimizar o empacotamento – o que pode ser ruim para o para depois otimizar o empacotamento – o que pode ser ruim para o nosso caso. Como os componentes do nosso problema possuem nosso caso. Como os componentes do nosso problema possuem tamanho definido, não será preciso realizar as estimativas de tamanho tamanho definido, não será preciso realizar as estimativas de tamanho para células variáveis descritas no livro (o chamado FLOORPLANNING).para células variáveis descritas no livro (o chamado FLOORPLANNING).

Assim sendo, nosso problema se encaixa no caso de “GENERAL-CELL Assim sendo, nosso problema se encaixa no caso de “GENERAL-CELL PLACEMENT” que é um caso particular do floorplanning, onde as células PLACEMENT” que é um caso particular do floorplanning, onde as células possuem tamanhos e formatos fixos.possuem tamanhos e formatos fixos.

General-Cells PlacementGeneral-Cells Placement

A estrutura de dados manipulada neste problema é chamada “A estrutura de dados manipulada neste problema é chamada “floorplanfloorplan”, e ”, e pode ser do tipo pode ser do tipo sized sized ou ou unsizedunsized. Consideraremos apenas o floorplan do . Consideraremos apenas o floorplan do tipo sized, visto que o tamanho da área do nosso posicionamento é tipo sized, visto que o tamanho da área do nosso posicionamento é limitada.limitada.

Definições:Definições:

Um Um floorplanfloorplan para um circuito G é um grafo planar direcionado F, para um circuito G é um grafo planar direcionado F, representando a subdivisão de um retângulo (chamado base) em representando a subdivisão de um retângulo (chamado base) em subretângulos, chamados salas.subretângulos, chamados salas.

Os vértices de F são os cantos das salas, e as arestas são as paredes Os vértices de F são os cantos das salas, e as arestas são as paredes (que são sempre orientadas na vertical ou horizontal). Cada vértice "e" (que são sempre orientadas na vertical ou horizontal). Cada vértice "e" (edge) é marcado com uma "orientation label": dir(e) que pode ser (edge) é marcado com uma "orientation label": dir(e) que pode ser {hor,ver}.{hor,ver}.

Um Um floorplanfloorplan que não possui nenhum vértice com grau 4 (4 arestas que não possui nenhum vértice com grau 4 (4 arestas saindo/chegando nele) é chamado saindo/chegando nele) é chamado normalnormal. .

Um Um sized floorplan sized floorplan é definido como o par (F,L) onde L é chamado é definido como o par (F,L) onde L é chamado sizing sizing de Fde F. . “L”“L” pode ser definido para cada sala ou para o flooplan inteiro, pode ser definido para cada sala ou para o flooplan inteiro, determinando a altura e largura destes (hdeterminando a altura e largura destes (hLL e w e wLL) além dos layouts ) além dos layouts escolhidos para cada bloco.escolhidos para cada bloco.

Obs.: o fato de um floorplan ser normal simplifica conceitos e algoritmos, e Obs.: o fato de um floorplan ser normal simplifica conceitos e algoritmos, e como um floorplan não-normal pode ser facilmente transformado em um como um floorplan não-normal pode ser facilmente transformado em um normal, todos serão assumidos normais.normal, todos serão assumidos normais.

Sizing function Sizing function “s“s””:: Função que determina as possibilidade de layout Função que determina as possibilidade de layout para um bloco.para um bloco.

Função escolha (choice function) Função escolha (choice function) “a“a””:: é uma função que escolhe o é uma função que escolhe o layout para cada sala. Um sizing “L” é válido para uma escolha layout para cada sala. Um sizing “L” é válido para uma escolha “a”, se cada sala “r” acomodar a alternativa com as proporções “a”, se cada sala “r” acomodar a alternativa com as proporções a(r) x s(a(r)), onde “s” é a sizing function de r.a(r) x s(a(r)), onde “s” é a sizing function de r.

O floorplan size measure é uma função Φ(w,h). Algumas versões O floorplan size measure é uma função Φ(w,h). Algumas versões populares dela consideram a área “wh” ou o semi-perímetro “w + populares dela consideram a área “wh” ou o semi-perímetro “w + h”. (isto vai depender do que considerarmos melhor no problema h”. (isto vai depender do que considerarmos melhor no problema da cemig, mas imagino que considerar a área seja uma boa da cemig, mas imagino que considerar a área seja uma boa alternativa).alternativa).

O problema então, consiste em determinar “a” com “L” válido, de O problema então, consiste em determinar “a” com “L” válido, de modo a obter Φ mínimo.modo a obter Φ mínimo.

Com estes conceitos, é possível começar a estudar os algoritmos!Com estes conceitos, é possível começar a estudar os algoritmos!

A heurística Mincut consiste em:A heurística Mincut consiste em:

1- Biparticionar recursivamente o circuito;1- Biparticionar recursivamente o circuito;

2- É necessário que cada bloco do circuito G possua um peso 2- É necessário que cada bloco do circuito G possua um peso correspondente à sua área. Então, o floorplan inicial é uma base correspondente à sua área. Então, o floorplan inicial é uma base retangular vazia com peso total igual ao peso dos vértices de G. O retangular vazia com peso total igual ao peso dos vértices de G. O processo de bipartição vai processando cada nó da árvore, e o processo de bipartição vai processando cada nó da árvore, e o separando em dois novos nós, considerando os pesos dos vértices de G separando em dois novos nós, considerando os pesos dos vértices de G realocados em cada sala (nó). O processo se repete até que cada sala realocados em cada sala (nó). O processo se repete até que cada sala contenha apenas 1 vértice de G (um bloco). contenha apenas 1 vértice de G (um bloco).

3- O processo de partição recursivo gera uma árvore binária. Cada nó da 3- O processo de partição recursivo gera uma árvore binária. Cada nó da árvore representa um subgrafo do circuito G e uma sala retangular na árvore representa um subgrafo do circuito G e uma sala retangular na área de layout;área de layout;

MincutMincut

O livro cita um trabalho realizado por Ulrich Lauther (General-Cell Placement O livro cita um trabalho realizado por Ulrich Lauther (General-Cell Placement baseado em Oriented MinCut), que mostrou ser mais próximo do nosso baseado em Oriented MinCut), que mostrou ser mais próximo do nosso problema, por otimizar o general-cell placement utilizando otimizações problema, por otimizar o general-cell placement utilizando otimizações baseadas no fato de os blocos possuírem tamanhos definidos.baseadas no fato de os blocos possuírem tamanhos definidos.

Este trabalho é focado em rotacionar e reposicionar os elementos de modo a Este trabalho é focado em rotacionar e reposicionar os elementos de modo a otimizar a área ocupada, sempre visando deixar o roteamento possível. otimizar a área ocupada, sempre visando deixar o roteamento possível. Como a posição, tamanho e ordem dos elementos do problema da Como a posição, tamanho e ordem dos elementos do problema da CEMIG são fixos, não é interessante analisar a fundo este trabalho.CEMIG são fixos, não é interessante analisar a fundo este trabalho.

O enfoque a seguir será dado na questão do roteamento entre os elementos O enfoque a seguir será dado na questão do roteamento entre os elementos pré-fixados.pré-fixados.

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

EMICRO2004

Marcelo JohannMarcelo Johann

Examinando a parte de roteamento do Examinando a parte de roteamento do trabalho do Marcelo Johann...trabalho do Marcelo Johann...

Roteamento - IntroduçãoRoteamento - Introdução

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

ClassificaçãoClassificação Algoritmos de Roteamento GenéricosAlgoritmos de Roteamento Genéricos Roteamento de CanalRoteamento de Canal Roteamento PlanarRoteamento Planar Roteamento GlobalRoteamento Global

Classificação de roteamento por objetivos:Classificação de roteamento por objetivos:

ClassificaçãoClassificação

Roteamento detalhadoRoteamento detalhado

O roteamento detalhado, cuja definição é intuitiva, é a tarefa de especificar completa e detalhadamente as rotas de cada conexão, seus materiais, furos, posições e dimensões exatas. Sendo um problema muito complexo para o circuito inteiro, é normalmente tratado por partes.

Roteamento globalRoteamento global

O roteamento global é a etapa responsável por dividir o problema de roteamento de todo o circuito para um conjunto completamente especificado de roteamentos detalhados suficientemente pequenos para que sejam tratáveis. Esta divisão certamente tira proveito da localidade de conexões e espaços. Entretanto, em todos os casos, o roteamento global necessita planejar as conexões mais longas decompondo-as em pequenas conexões locais a cada roteamento detalhado.

Roteamento especializadoRoteamento especializado

O roteamento funcionalmente especializado é aquele necessário para conexões com características especiais, como alimentação, relógio, barramento, ou sinais de entrada e saída.

O roteamento tecnologicamente especializado ocorre em situações específicas da tecnologia de fabricação de equipamentos eletrônicos.

Classificação de roteamento quanto ao espaço:Classificação de roteamento quanto ao espaço:

espaços dedicados: canais e espaços dedicados: canais e switch boxesswitch boxes;; sobre as células, roteamento de área...sobre as células, roteamento de área...

general cellgeneral cell standard cell roteamento de standard cell roteamento de áreaárea

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

roteamento sobre roteamento sobre gradegrade (e simbólico); (e simbólico); roteamento topológico (semântica do problema);roteamento topológico (semântica do problema); roteamento ortogonal ou com ângulos (45roteamento ortogonal ou com ângulos (45oo);); larguras e espaçamentos arbitrários;larguras e espaçamentos arbitrários; modelosmodelos: forma da área, número de camadas, : forma da área, número de camadas,

modelo de células, posição dos terminais, terminais modelo de células, posição dos terminais, terminais eqüipotenciais, restrições,...eqüipotenciais, restrições,...

Classificação quanto ao processamento:Classificação quanto ao processamento:

incrementaisincrementais ou ou seqüenciaisseqüenciais: fazem uma conexão a : fazem uma conexão a cada vez. Problema: ordenação; <- ruimcada vez. Problema: ordenação; <- ruim

integraisintegrais ou ou paralelosparalelos: consideram todas as : consideram todas as conexões ao mesmo tempo;conexões ao mesmo tempo;

refinadoresrefinadores ou ou iterativositerativos: partem de uma solução : partem de uma solução inicial e repetem a operação de desfazer e refazer inicial e repetem a operação de desfazer e refazer conexões até o fim;conexões até o fim;

O artigo apresenta diversos modelos que O artigo apresenta diversos modelos que condicionam o roteamento, porém não é condicionam o roteamento, porém não é interessante abordá-los visto que eles estão interessante abordá-los visto que eles estão intimamente ligado à características dos intimamente ligado à características dos circuitos que não interessam ao problema da circuitos que não interessam ao problema da CEMIG.CEMIG.

Algoritmos de Roteamento:Algoritmos de Roteamento:

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

ex:ex: maze routersmaze routers = = breadth-first searchbreadth-first search

restritosrestritos: exploram características ou restrições : exploram características ou restrições particulares de um problema para encontrar soluções particulares de um problema para encontrar soluções com maior eficiência;com maior eficiência;ex:ex: roteamento de canalroteamento de canal

caixas de conexãocaixas de conexãoroteamento planar ...roteamento planar ...

Maze Router (BFS)Maze Router (BFS)

pesquisa em largura numa grade (Lee 1961)pesquisa em largura numa grade (Lee 1961) expansãoexpansão retraçoretraço reinicializaçãoreinicialização

problemasproblemas tempotempo memóriamemória ordenaçãoordenação

garantiagarantiageneralidadegeneralidade

Modelo de canal:Modelo de canal: espaço entre duas bandas; espaço entre duas bandas; definição:definição: terminais superiores e inferiores; terminais superiores e inferiores; dificuldade de roteamento: dificuldade de roteamento: horizontalhorizontal;;

Roteamento de CanalRoteamento de Canal

Algoritmos para roteamento de canal:Algoritmos para roteamento de canal:

Left-Edge;Left-Edge; DoglegDogleg;; Greedy;Greedy; YACR;YACR;

Roteamento de CanalRoteamento de Canal

AlgoritmoAlgoritmo Left-EdgeLeft-Edge segmentos que unam todos os pinos das redessegmentos 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

AlgoritmoAlgoritmo Left-EdgeLeft-Edge segmentos que unam todos os pinos das redessegmentos 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

AlgoritmoAlgoritmo Left-EdgeLeft-Edge

máximo clique de HCG define mínima alturamá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


máximo clique de HCG define mínima alturamá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 trilhacombinar 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 trilhacombinar 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õesVCG 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

Não resolve problema Não resolve problema de ciclos! (dogleg)de ciclos! (dogleg)


1 42

5 63

AlgoritmoAlgoritmo GreedyGreedy

Insere novo pinoem trilha livre

Une redesdivididas

Aproxima trechosde redes divididas

Aproxima redes depróximos pinos

Insere novatrilha

5)1) 2) 3) 4)

opera da esquerda para a direita estendendo opera da esquerda para a direita estendendo trilhastrilhas

busca unir ou aproximar redes divididasbusca unir ou aproximar redes divididas a cada coluna executa 5 passos:a cada coluna executa 5 passos:

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

tem menor confiabilidade de fabricação;tem menor confiabilidade de fabricação; geram maior atraso por aumento de geram maior atraso por aumento de RR;; reduzem imunidade a ruído pela reduzem imunidade a ruído pela

introdução de resistências em série;introdução de resistências em série; necessitam maior área devido a margem necessitam maior área devido a margem

dos metais sobre os furos;dos metais sobre os furos;

Roteamento PlanarRoteamento Planar

Roteamento planar de uma caixa:Roteamento planar de uma caixa:


Roteamento em rio (Roteamento em rio (river routingriver routing):):


Single Row RoutingSingle Row Routing Problem (SRRP):Problem (SRRP):


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

Roteamento GlobalRoteamento Global

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


Roteamento Global para leiaute em bandas:Roteamento Global para leiaute em bandas: conexões verticais com conexões verticais com feedthroughsfeedthroughs;;

Encontrar árvores para cada redeEncontrar árvores para cada rede


ReferenciasReferencias

http://cadapplets.lafayette.edu/ChannelRouter.htmlhttp://cadapplets.lafayette.edu/ChannelRouter.html http://ieeexplore.ieee.org/http://ieeexplore.ieee.org/

iel5/8229/25383/01137670.pdf?arnumber=1137670iel5/8229/25383/01137670.pdf?arnumber=1137670 http://www.rulabinsky.com/cavd/text/chap04-3.htmlhttp://www.rulabinsky.com/cavd/text/chap04-3.html http://www.inf.ufrgs.br/~johann/papers/qualify5.pdfhttp://www.inf.ufrgs.br/~johann/papers/qualify5.pdf http://inst.eecs.berkeley.edu/~ee244/fa97/http://inst.eecs.berkeley.edu/~ee244/fa97/

Lectures/ee2443_2/Lectures/ee2443_2/

Documents

Projeto de Circuitos Integrados Um estudo dos algoritmos envolvidos e sua aplicabilidade em relação ao desenho de grafos, baseado no livro: Combinatorial