Ferramentas para Síntese Na aula Anterior…johann/cmp241/aula07.partplacefloor.ppt.pdf · 2 CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1 Aula

1

Aula 07 : Slide 1CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Ferramentas para SínteseAutomática de Circuitos IntegradosProfs: Ricardo Reis e Marcelo Johann

ParticionamentoPosicionamentoFloorplanning


Na aula Anterior…

Randomized Algorithms

SA - Simulated Annealing TA - Threshold Accepting GA - Genetic Algorithm MA - Memetic Algorithm AC - Ant Colony


Three basic functions: Temperature Schedule (above), Cost(wire length) and Perturbation (changes in current solution).

PerturbationCost

Reject / Accept

thanks to Renato Hentschke

AnnealingAnnealing


In a In a NutshellNutshell

While (temp*=0.99 > finalvalue) { make_perturbation(); if ( newcost < actualcost || rand() < e^(-deltacost / temp) ) accept(); else reject(); }

Simulated annealing does:


Threshold AcceptingThreshold Accepting

While (threshold*=0.99 > finalvalue) { make_perturbation(); if ( newcost < actualcost + threshold ) accept(); else reject(); }

Threshold Accepting is solely:

It is easier and more efficientbut Why???


Threshold AcceptingThreshold Accepting1) Integrating a constant distribution leads to the same normal distribution of perturbations

2) It is easier to advance:

2


Threshold AcceptingThreshold Accepting

Results 1 - 10 of about 1,870,000 for"simulated annealing". (0.26 seconds)

Results 1 - 10 of about 28,000 for"threshold accepting". (0.18 seconds)

Results 1 - 10 of about 145 for"bachelor acceptance". (0.26 seconds)


Understanding Understanding S.A. S.A. and and T.A.T.A.S.A. and T.A. are random walks in the

space stateThe more you walk, more likely you end upclose to the optimal…

Requires some tuning and expertiseAppletshttp://www-lehre.inf.uos.de/~sborggre/SimulatedAnnealing.html

http://www.duke.edu/~jmu2/color/gc.html


Algoritmos GenéticosOu Evolução Simulada

População Qualidade do Indivíduo define sobrevivência Cruzamento Mutação Elitismo e Importância da Morte

Memória


Algoritmos Meméticos

Os individuos aprendem durante a vida A aprendizagem é transmitida em DNA

mitocondrial


Hoje

Particionamento Posicionamento Floorplanning


ParticionamentoParticionamentoCircuito representado por um grafo G=(V,E) bi-partitioning, multi-way-particioning;

v1v2

v3

v4

v5

v6

v7

v8

v9

v1

v2

v3 v4

v5

v6

v7

v8

v9

componentesredes

3


ParticionamentoParticionamento

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;


2 2 ParticionamentoParticionamento

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 D1 1 1 02 1 2 -13 0 3 -34 0 3 -35 1 2 -16 1 1 0

i inedge outedge D1 2 0 22 2 1 13 2 1 14 2 1 15 2 1 16 2 0 2


ParticionamentoParticionamento

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, …


Particionamento Atualmente

Algoritmos baseados em FM Multi-nível Muito boa escalabilidade

Ver hmetis


Placement


FloorplanningIn the beginning… Bottom-up construction Poor area usageStructured Design Methods Hierarchical partitioning like in software Floorplan-based design methodology

(take into account physical positions in decomposition) Most information is estimated

4


Floorplanning


Slicing FloorplanUses a matched hierarchical structure

Slicing Tree Floorplan


Slicing Floorplan Some floorplans cannot be represented

Wheel FloorplanAula 07 : Slide 22CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Floorplan Tree Floorplan of order 5


Polar GraphsCan represent

any floorplan

Segments are nodesEach cell is an edge

from is top/leftboundary to itsbottom/right one


Related Optimization Problems

1. Mapping of structural description Manual and structural Independent (like placement) But placement has precise information

2. Floorplan sizing Hard and soft cells/blocks Need to specify/check cell shapes

3. Generation of flexible cells

5


Shape functions


Floorplanning Today Search for Floorplan papers at ISPD, DAC; Search for “floorist”, an example of

floorplan/placement legalization; Serach for…


Próxima aula

RoutingTrees

Documents

Ferramentas para Síntese Na aula Anterior…johann/cmp241/aula07.partplacefloor.ppt.pdf · 2 CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1 Aula