Outline
CAD Tools
•
•
•
•
Physical Design and CAD Tools
The evolution to Chip Design
Physical Design Flow
Problems and Solution Space
Complexity, Graphs and Optimization
Problems and Algorithms
Marcelo Johann
www.inf.ufrgs.br/~johann
[email protected]
• Placement Algorithms
SA, TA, Analytical, PEKO
• Routing Algorithms
Maze Router and A*
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Integrated Systems
Scale Active devices
So we went from...
System Function
Year
SSI
1-100
Gates, OP-Amp, linear App.
1960
MSI
100-1.000
Registers, Filters
1965
LSI
1.000-10.000
Microprocessor, ADC
1970
Memory, Computers, Signal
Processor
1975
VLSI 10.000-100.000
ULSI 100.000-50.000.000 Pentium IV.
??SI
50.000.000-7bilion
2/117
Multi Core, complex
integrated systems
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
2001
2013
“Simple”, “one-man” hand design in 1971
SIM/EMICRO 2013
3/117
To this kind of designs (actually, old - 2004)
Porto Alegre, Brasil - Abril/2013
4/117
People Clearly Need...
IBM Cell
Tools
To handle:
- Billions of elements
- Associated complexity (macro and nano)
- Short time-to-market
4 years,
$400M design
400 engineers
234M transistors
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
5/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
6/117
Tools
Tools
A long time ago we discovered the first tools…
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
…tools started to get more sophisticated…
SIM/EMICRO 2013
7/117
Tools
Porto Alegre, Brasil - Abril/2013
8/117
Tools
…more sophisticated and complex…
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
…and then came VLSI CAD tools!
SIM/EMICRO 2013
9/117
Tools
Porto Alegre, Brasil - Abril/2013
10/117
Tools
Designers use CAD tools to make Chips
And there is a chain of tools that make tools.
g++
STL
Math
CS
EE
CE
EE
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
11/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
12/117
Microelectronics is...
A Design Flow
Programming
Algorithms
Graph Theory
Optimization
g++
STL
Designer makes initial description (ex: VHDL)
and uses a methodology, a set of
operations using tools to get the circuit:
• High-Level Synthesis;
Algorithm to RTL
• Logic Synthesis:
RTL to mapped netlist
• Physical Synthesis:
Placement & Routing
Math
CS
EE
CE
EE
VLSI Design
EE
Phy
Che
Foundry
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
13/117
Porto Alegre, Brasil - Abril/2013
14/117
Physical Design Flow Example
process(clk,rst)
begin
if (rst='1') then
r_reg<= (0=> '1', others =>'0');
elsif (clk'event and clk='1') then
r_reg<= r_next;
end if;
end process;
r_next<= r_reg(0) & r_reg(3 downto 1);
q<= r_reg;
• High-Level Synthesis;
Algorithm to RTL
• Logic Synthesis:
RTL to mapped netlist
• Physical Synthesis:
Placement & Routing
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
o
o
o
o
o
o
o
o
o
Input
Floorplanning
Power Planning
Placing Standard Cells
First Optimization Phase
Clock Tree Synthesis
Post-CTS Optimization
Final Routing
Post-Route Optimization
o
o
o
o
o
Ading Filler Cells
Check/Verification
Saving and using Hierarchy
Chip Place & Route with Macro Blocks
Simulation and Chip Assembly
15/117
Input and Floorplanning
Power and STD Cells
o Take the result from RTL/Logic Synthesis
o Power Planning
o Placing Standard Cells
– mapped netlist
– timing information
o Floorplanning
– For modules, specify:
• Aspect ratio
• Core utilization
• Core margins
• Row spacing
– For the chip
• Placement of hard and soft blocks
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
16/117
SIM/EMICRO 2013
18/117
Porto Alegre, Brasil - Abril/2013
o First Optimization Phase
– Try meeting timing
17/117
Porto Alegre, Brasil - Abril/2013
Clock Tree
Routing
o Clock Tree Synthesis
o Post-CTS Optimization
o Final Routing
o Post-Route
Optimization
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
19/117
Additional Steps
Porto Alegre, Brasil - Abril/2013
20/117
Now, how those tools work?
o Ading Filler Cells
o Check/Verification
o Saving and
using Hierarchy
o Chip P&R
with Macro Blocks
o Simulation
o Chip Assembly
ALGORITHMS
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
21/117
The Placement Problem
SIM/EMICRO 2013
22/117
SIM/EMICRO 2013
24/117
Porto Alegre, Brasil - Abril/2013
The Placement Problem
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
23/117
Porto Alegre, Brasil - Abril/2013
The Placement Problem
a b c d e
i
g h
j
The Placement Problem
But why
this way?
f
b k e
g d j a
l
k
f
SIM/EMICRO 2013
HPWL
The “Rats Nest”
Because in some dispositions cells to
connect are a lot closer
SIM/EMICRO 2013
The Placement Problem
Ok. Lets see how many options we have…
f
g d j a
SIM/EMICRO 2013
Bad news - Complexity
Polynomial
Bad!
n = 10
n = 20
102
103
106
2
6
10
20
3n
6
18
30
60
3 * 102 3 * 103 3 * 106
0.6
4.7
10
26
2 * 102 3 * 103 6 * 106
36
102
216
103
n2
4
n3
8
2n
4
64
n!
2
720
103
l
That’s
479.001.600
i
Porto Alegre, Brasil - Abril/2013
for a circuit
with only
12 cells!!!
28/117
Problem Classes
do need a computer!
n = 102 n = 103 n = 106
n
n log10 n
12 !
c h
SIM/EMICRO 2013
27/117
Cobham's thesis
too small: not a concern
function n = 2 n = 6
26/117
Porto Alegre, Brasil - Abril/2013
b k e
Porto Alegre, Brasil - Abril/2013
i
l
25/117
Porto Alegre, Brasil - Abril/2013
And not
this way?
c h
4*
102
104
106
1012
8*
103
106
109
1018
1030
10301
> 10500
106
Classe P
• Problemas para os quais existe um algoritmo
determinístico em tempo polinomial que os
solucionam exatamente
3 * 106 2 * 1018 9 * 10157 > 10500 > 10500
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
29/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
30/117
Problem Classes
Complexity and Classes
Classe NP
• Problemas para os quais existe um algoritmo
em tempo polinomial que verifica se uma
dada solução é a correta
Classe NP-Completo ⊂ NP
Existem problemas cuja resposta pode ser verificada
em tempo polinomial, que não possam ser
resolvidos em tempo polinomial?
Classe NP-Difícil: ao menos tão difícil
quanto NP
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
P ≠NP ?
31/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
32/117
More bad news:
Complexity and Speed
Both are important in practice
Complexity
• When the problem’s instance size increases
Restricted cases
Suboptimal solutions
Good Optimization algorithms
Speed
• When the problem’s instance size is
bounded
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
• Most CAD problems are NPcomplete or NP-Hard
• So, How do we solve them???
33/117
Solution Space
How is this Cost Function?
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
35/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
36/117
Many Optimization Algorithms
Linear Models
• Otimização Convexa (I’ve got a model!)
Pesq. Oper., Progr. linear, quadrática, geométrica
• Mecanismos de Busca
Guloso, Backtrack, Local, Exaustiva, Branch-andbound, Programação Dinâmica, Tabu, GRASP
• Algoritmos de Otimização Randomizados ou
Meta-Heurísticas
SA, TA, GA, MA, AC
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
37/117
Quadratic Models
Porto Alegre, Brasil - Abril/2013
38/117
Search Procedures
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
39/117
Randomized Algorithms
Guloso, Backtrack, Local, Exaustiva, Branch-and-bound, Programação Dinâmica, Tabu, GRASP
SIM/EMICRO 2013
40/117
Porto Alegre, Brasil - Abril/2013
Randomized Example 1
Identifying the repeated element
• Array half filled with a repeated number
What?
- Use a random number generator to
sample or select decisions
Why?
- Better efficiency
• Any deterministic algorithm requires at least
(n/2)+1 comparisons
Probabilistic, Las Vegas, Monte Carlo
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
41/117
• An algorithm that randomly chooses two
elements terminates with O(log n) atempts
with high probabillity
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
42/117
Randomized Example 2
Randomized Example 3
Computing π
Power supply analysis
int main (int argc, char ** argv)
{
long experiments, total = 1000000;
long inside = 0;
• Haifeng Qian, Sani R. Nassif, Sachin S. Sapatnekar.
Random Walks in a Supply Network, DAC 2003
for (experiments=0 ; experiments < total; ++experiments )
{
double x = (double) rand()/(double) RAND_MAX;
double y = (double) rand()/(double) RAND_MAX;
if (sqrt(x*x+y*y) <= 1)
++ inside;
if ((experiments%10000)==0)
printf("With %ld experiments PI = %lf\n",
experiments,(double)4*inside/experiments);
}
}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Randomized Meta-Heuristics
Placement Problem
Simulated Annealing
…and we need a graph
SA - Simulated Annealing
TA - Threshold Accepting
GA - Genetic Algorithm
MA - Memetic Algorithm
Many others more recently…
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
44/117
Porto Alegre, Brasil - Abril/2013
Let’s put together...
Meta-Algorithms that work for many
optimization problems
•
•
•
•
•
SIM/EMICRO 2013
43/117
SIM/EMICRO 2013
45/117
Graph Theory
46/117
Porto Alegre, Brasil - Abril/2013
Representation
Graph
A Set and a set or Pairs
Circuit represented as a Graph G=(V,E)
Relation
Each element of the pair belongs to
one of the sets
components
Function
There is a single element from the
second set associated to each
element of the first set
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
nets
v7
v3
v2
v9
47/117
v4
v1
v5
v8
v6
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
48/117
Simulated Annealing in 512 bytes
Annealing
Marcelo Johann
EMICRO2004
EM
Microelectronics School
BRAZIL
thanks to Renato Hentschke
Perturbation
Cost
Reject / Accept
Three basic functions: Temperature Schedule (above), Cost
(wire length) and Perturbation (changes in current solution).
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
S.A. in 512+ bytes
50/117
S.A. in 512+ bytes
Looks crazy, but works!
#include<stdio.h>
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
A big number!!!
#include<stdio.h>
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
51/117
S.A. in 512+ bytes
Porto Alegre, Brasil - Abril/2013
52/117
S.A. in 512+ bytes
Loop a times
#include<stdio.h>
Read a from stdin
#include<math.h>
Exchange k[a] with k[b]
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
53/117
#include<stdio.h>
#include<math.h>
x,y position of each node
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
54/117
S.A. in 512+ bytes
S.A. in 512+ bytes
#include<stdio.h>
#include<math.h>
#define z 9999
source and target of each arc
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
#include<stdio.h>
cells and wires, number of rows
#include<math.h>
and list of wires (node node)
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Input graph reading: number of
SIM/EMICRO 2013
55/117
S.A. in 512+ bytes
Porto Alegre, Brasil - Abril/2013
56/117
S.A. in 512+ bytes
Input graph reading: number of
#include<stdio.h>
cells and wires, number of rows
#include<math.h>
and list of wires (node node)
#define z 9999
#define F(a)for(i=0;i<a;++i)
initial placement
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Cost function: adds the length
#include<stdio.h>
of all arcs in the graph
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
57/117
S.A. in 512+ bytes
Porto Alegre, Brasil - Abril/2013
58/117
S.A. in 512+ bytes
Temperature scheduling
#include<stdio.h>
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
59/117
Perturbation: exchange a
#include<stdio.h>
random selected pair of cells
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
60/117
S.A. in 512+ bytes
S.A. in 512+ bytes
Accepting criteria (inverted)
#include<stdio.h>
Reject if the cost is higher
#include<math.h>
and the probability is not
#define z 9999
#define F(a)for(i=0;i<a;++i) satisfied
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Probabilistic: inversely
#include<stdio.h>
proportional to the temperature
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
61/117
S.A. in 512 bytes
Porto Alegre, Brasil - Abril/2013
62/117
Now “Threshold Acepting”
Simulated annealing does:
Take off cost reports to get
#include<stdio.h>
your 512-byte SA placer!
#include<math.h>
#define z 9999
#define F(a)for(i=0;i<a;++i)
#define R(a)scanf("%d",&a);
#define T(k)d=k[a];k[a]=k[b];k[b]=d;
long a,b,c=0,i,v,e,d,l,X[z],Y[z],E[9*z],G[9*z];double t;
w(){int i;d=0;F(e)d+=abs(X[E[i]]-X[G[i]])+abs(Y[E[i]]-Y[G[i]]);return d;}
main(){R(v)R(e)R(a)F(v){X[i]=i/a;Y[i]=i%a;}F(e){R(E[i])R(G[i])}
for(t=z*a;c++<z*9;t*=.9){F(1){a=rand()%v;b=rand()%v;l=w();T(X)T(Y);
if(d=(w()-l)>0)if(rand()%z>z*exp(-d/t)){T(X)T(Y)}}}
F(v)printf("%d %d %d %d\n",i,X[i],Y[i],w());}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
While (temp*=0.99 > finalvalue)
{
make_perturbation();
if ( newcost < actualcost || rand() < e^(-deltacost / temp) )
accept();
else
reject();
}
SIM/EMICRO 2013
63/117
Threshold Accepting
Porto Alegre, Brasil - Abril/2013
64/117
Threshold Accepting
1) Integrating this constant acceptance leads to
a similar decreasing probability of bad moves
Threshold Accepting is solely:
While (threshold*=0.99 > finalvalue)
{
make_perturbation();
if ( newcost < actualcost + threshold )
accept();
else
reject();
}
It is easier and
2) It is easier to advance:
more efficient
but Why???
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
65/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
66/117
Threshold Accepting
Using S.A. And T.A.
Temperature (or threshold)
• Initial identification, adaptive schedule,
for how long, low temperature…
Neighborhood
• Check for valid perturbations
Cost shape
• Stratification, global behavior, …
Other issues
• Heuristic moves, windowing…
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)
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
67/117
Alternatives
ALTERNATIVAS
Quadratic Placement
Clustering
Are there other ways of
doing placement?
Of course!
68/117
Porto Alegre, Brasil - Abril/2013
Quadratic
Placement
Global !
Legalization
"(x,y) =
1 n $
* c ij
2 i, j=1 &%
2
(x
i
2
2'
2
2
1 n
1 n
# x j ) + ( y i # y j ) ) = * c ij ( x i # x j ) + * c ij ( y i # y j )
( 2 i, j=1
2 j=1
!##"##$ !i,#
#"##$
"( x )
"(x) = [ x
T
m
#Q mm
x ]%
$Q fm
T
f
"( y )
Linear System of Equations
Q mf &#x m &
(% (
Q ff '$x f ' derivative Q x = !Q x
mm
m
mf
!
Detailed Place
Detailed
Legalization
...
Placement
Refinement
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
69/117
Clustering
Bins
Adding Spreading Forces
An Over Utilized Bin
Quadratic
Placement
Global
Legalization
Detailed Place
Detailed
Legalization
Placement
Refinement
70/117
Porto Alegre, Brasil - Abril/2013
Cell Shifting
A Placement
f
cell spreading
Equilibrium
state, after
minimization:
resultant force
over all the cells
is null!
Clustering
Quadratic
Placement
Global
Legalization
Placement After
Some Cell Shifting
Iterations
Detailed Place
Cell Shifting
After cell
shifting, new
forces are acting
on cells. Update
connectivity
matrix Q.
Detailed
Legalization
…
Placement
Refinement
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
71/117
k=
SIM/EMICRO 2013
F
"x 2 + "y 2
72/117
Porto Alegre, Brasil - Abril/2013
!
Analytical Placement - FastPlace
PEKO
• Qual seria a solução ótima?
• Jason Cong (UCLA) 2002
– “Inventa” circuitos com posicionamento ótimo
– Respeita qualquer distribuição de redes
• Falhas
– Circuitos são malhas, sem globais
– Peko killer e outros trabalhos;
• Placement Contest no ISPD2005
– Patrick Madden mostra visualmente a
qualidade dos posicionadores em circuitos
Peko
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
73/117
Dragon
Capo
74/117
Renato Hentschke’
Hentschke’s ZPlace
Feng Shui Suboptimality Gallery
mPL
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
PhD
UFRGS
2007
now Intel
feng shui Beacon
Prof. Jason Cong
Prof. Majid Sarrafzadeh
Prof. Igor Markov
Prof. Patrick H. Madden
Satoshi Ono
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
Flach’s PlaceDL and Colors
75/117
MsC UFRGS 2010, PhD ongoing
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
77/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
76/117
PLaceDL and the “Rock and Sand” problem
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
78/117
Placement and Floorplanning
Now, lets talk
a bit about
ROUTING
From Igor Markov’s webpage
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
79/117
The Routing Problem
Why Routing still Important Today?
After placement
• Lets see how we can add connections to
the cells so that we build a real circuit
Many technology/design issues
• Scaling…
• Timing…
• Buffering…
=
+
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
SIM/EMICRO 2013
81/117
Why Routing still Important Today
82/117
Porto Alegre, Brasil - Abril/2013
Reverse Scaling
Atraso de porta (Tgate):
a)
• pode ser reduzido com o reprojeto da porta
R = 4, C = 4
RC = 16
b)
R=2,C=6
RC = 12
c)
R=1,C=8
RC = 8
Atraso de interconexão (Tint):
• exige o reprojeto das próprias interconexões
Rint
Rtr
+
-
Cint
CL
T50% = Tgate + Tint
Tgate = Rtr (0.7 Cint + 0.7 CL)
Tint = Rint (0.4 Cint + 0.7 CL)
Camadas têm características diferentes
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
83/117
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
84/117
Routing Algorithms
The MAZE Router
• 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 ...
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
The MAZE Router
Porto Alegre, Brasil - Abril/2013
86/117
The MAZE Router
X X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
S
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
X
X
X
X
T
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X X
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
X X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
2
X
X
2 1 2
X
X
2
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
X
X
X
X
T
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X X
SIM/EMICRO 2013
87/117
The MAZE Router
X X X X X
X
X
X
4
X
4 3
X
4 3 2
X
4 3
X
4
X
X
X
X X
X
X
X
X
X
X
X
X
X X X X X
SIM/EMICRO 2013
85/117
Porto Alegre, Brasil - Abril/2013
88/117
The MAZE Router
X X X X X X X X X X X X X X X
X
X
3
X
2 3
X
1 2 3
X
2 3
X
3
X
X
X
X X X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
89/117
X X X
7
7 6
7 6 5
6 5 4
5 4 3
6 5 4
7 6 5
7 6
7
X
X
6
5
4
3
2
3
4
5
6
X
X
5
4
3
2
1
2
3
4
5
X
X
6
5
4
3
2
3
4
5
6
X
X X X X X X X X X X X X X
X
6 7
X
5 6 7
X
4 5 6 7
X
3 4 5 6 7
X
4 5 6 7
X
5 6 7
X
6
X
X
X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
90/117
The MAZE Router
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
9
8
7
6
5
6
7
8
9
10
11
12
X
8
7
6
5
4
5
6
7
8
9
10
11
12
X
7
6
5
4
3
4
5
6
7
X
11
12
X
6
5
4
3
2
3
4
5
6
X
12
The MAZE Router
X
5
4
3
2
1
2
3
4
5
X
X
6
5
4
3
2
3
4
5
6
X
X
7
6
5
4
3
4
5
6
7
X
X
8
7
6
5
4
5
6
7
8
X
X
9
8
7
6
5
6
7
8
9
X
X
10
9
8
7
6
7
8
9
10
X
X
11
10
9
8
7
8
9
10
11
X
X
12
11
10
9
8
9
10
11
12
X
X X X X X X X
X
X
12
X
11 12
X
10 11 12
X
11 12
X
12
X
X
X
X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
12
11
10
9
10
11
12
SIM/EMICRO 2013
g++
Maze Router’s Expansion
SIM/EMICRO 2013
The MAZE Router
X
7
6
5
4
3
4
5
6
7
X
11
12
13
14
15
16
X
6
5
4
3
2
3
4
5
6
X
12
13
14
15
16
X
6
5
4
3
2
3
4
5
6
X
12
13
14
15
16
X
5
4
3
2
1
2
3
4
5
X
13
14
15
16
X
6
5
4
3
2
3
4
5
6
X
14
15
16
X
7
6
5
4
3
4
5
6
7
X
15
16
X X X
X
X
16 X
15 X
14 X
15 X
16 X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X
8
7
6
5
4
5
6
7
8
X
16
T
X
9
8
7
6
5
6
7
8
9
X
X
10
9
8
7
6
7
8
9
10
X
X
11
10
9
8
7
8
9
10
11
X
X
12
11
10
9
8
9
10
11
12
X
X
13
12
11
10
9
10
11
12
13
X
X
14
13
12
11
10
11
12
13
14
X
X
15
14
13
12
11
12
13
14
15
X
X
6
5
4
3
2
3
4
5
6
X
14
15
16
X
7
6
5
4
3
4
5
6
7
X
15
16
X
8
7
6
5
4
5
6
7
8
X
16
T
X
9
8
7
6
5
6
7
8
9
X
X
10
9
8
7
6
7
8
9
10
X
X
11
10
9
8
7
8
9
10
11
X
X
12
11
10
9
8
9
10
11
12
X
X
13
12
11
10
9
10
11
12
13
X
X
14
13
12
11
10
11
12
13
14
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
9
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
X
8
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
16
X
7
6
5
4
3
4
5
6
7
X
11
12
13
14
15
16
X
6
5
4
3
2
3
4
5
6
X
12
13
14
15
16
X
5
4
3
2
1
2
3
4
5
X
13
14
15
16
X
6
5
4
3
2
3
4
5
6
X
14
15
16
X
7
6
5
4
3
4
5
6
7
X
15
16
X
8
7
6
5
4
5
6
7
8
X
16
T
X
9
8
7
6
5
6
7
8
9
X
Porto Alegre, Brasil - Abril/2013
92/117
X X X
X
X
16 X
15 X
14 X
15 X
16 X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X
10
9
8
7
6
7
8
9
10
X
X
11
10
9
8
7
8
9
10
11
X
X
12
11
10
9
8
9
10
11
12
X
X
13
12
11
10
9
10
11
12
13
X
X
14
13
12
11
10
11
12
13
14
X
X
15
14
13
12
11
12
13
14
15
X
X
16
15
14
13
12
13
14
15
16
X
95/117
X
16
15
14
13
12
13
14
15
16
X
16
15
14
13
14
15
16
SIM/EMICRO 2013
94/117
Porto Alegre, Brasil - Abril/2013
g++
1-You have to store the
node and where it
came from in the queue
using a pair<int,int>
2-Instead of Space, use
Expansion[n] to store
where the nodes came
from and Taken[n] to
represent obstacles
and routes
4-Write backtrack(t,s)
from target to source
following Expansion[n]
X X X
X
16
X
15 16 X
14 15 X
13 14 X
14 15 X
15 16 X
16
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
SIM/EMICRO 2013
X
15
14
13
12
11
12
13
14
15
X
16
15
14
13
14
15
16
SIM/EMICRO 2013
Maze Router’s Tracking
X
5
4
3
2
1
2
3
4
5
X
13
14
15
16
X
16
15
14
13
12
13
14
15
16
X
Porto Alegre, Brasil - Abril/2013
93/117
Porto Alegre, Brasil - Abril/2013
X
8
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
16
X
7
6
5
4
3
4
5
6
7
X
11
12
13
14
15
16
The MAZE Router
void print(void);
#include <iostream>
int bfs(int source, int target)
#include <queue>
{
using namespace std;
queue<int> q;
#define SIDE 20
q.push(source);
#define PLACE(x,y) ((y)*SIDE+(x))
while (!q.empty())
#define WEST(n) (n-1)
{
#define EAST(n) (n+1)
int n = q.front();
#define NORTH(n) (n-SIDE)
q.pop();
#define SOUTH(n) (n+SIDE)
if (n==target)
char Space[SIDE*SIDE];
return 1;
void init (void)
if (Space[n] != 'X')
{
{
for (int i=0; i<SIDE*SIDE; ++i)
Space[n] = 'X';
Space[i] = ' ';
print();
for (int i=0; i<SIDE; ++i)
getchar();
{
q.push(WEST(n));
Space[PLACE(i,0)] = 'X';
q.push(EAST(n));
Space[PLACE(i,SIDE-1)] = 'X';
q.push(NORTH(n));
Space[PLACE(0,i)] = 'X';
q.push(SOUTH(n));
Space[PLACE(SIDE-1,i)] = 'X';
}
}
}
for (int i=3; i<SIDE-3; ++i)
return
0;
Space[PLACE(i,10)] = 'X';
}
}
X
9
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
X
8
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
16
91/117
Porto Alegre, Brasil - Abril/2013
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
9
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
typedef pair<int,int> Ref;
char Expansion[SIDE*SIDE]; // 0
char Taken[SIDE*SIDE]; // ' '
int bfs(int source, int target)
{
queue<Ref> q;
q.push(Ref(source,0));
while (!q.empty())
{
int n = q.front().first;
int p = q.front().second;
q.pop();
if (n==target)
return 1;
if (Expansion[n] == 0 &&
Taken[n] == ' ')
{
Expansion[n] = p;
q.push(Ref(WEST(n),n));
. . . }
}
return 0;
}
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
96/117
The MAZE Router
X X X X X X
X
X
X
X
X
> > > >
X
^
X
^
X
^
X
^
X
^ X X X
X
^
X
^ < < <
X
X
X
X
X
X
X X X X X X
The MAZE Router
X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X
X
X
< < <
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
X X X X X X X
X
X
X
X
X
> > > >
X
^
X
^
X
^
S
X
^
X
^ X X X X
X
^
T
X
^ < < < <
X
X
X
X
X
X
X X X X X X X
X X X X X X X
X
X
X
X
X
> > > >
X
^
X
^
X
^
< < <
X
^
X
^ X X X X
X
^
> > >
X
^ < < < <
X
X
X
X
X
X
X X X X X X X
SIM/EMICRO 2013
97/117
The MAZE Router
X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X
X
X
< <
X
X
X
X
X
X
X
X X X X X X X X X X X X X
Porto Alegre, Brasil - Abril/2013
98/117
The MAZE Router
X X X X X X X X X X X X X
X
X
X
X
X
X
X
< < < < < < < < < < <
X
^
X
X X X X X X X X X X ^
X
> > > > > > > > > > ^
X
< <
X
X
X
X
X
X
X
X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X
X
X
X
> > > > >
X
^
X
^
X
^ > > >
X
^ ^
X
^ ^ X X X X X X X X X X X X X X
X
^ ^ < <
X
^ < < < < < < <
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
We can try another ordering…
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
The MAZE Router
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
SIM/EMICRO 2013
99/117
Porto Alegre, Brasil - Abril/2013
100/11
7
The A* ALgorithm
X X X X X X X X X X X X X X X X X X X
X
X
X
T
X
> > > > >
X
^
X
^
X
^ > > >
X
^ ^
X
^ ^ X X X X X X X X X X X X X X
X
^ ^ < <
X
^ < < < < < < <
X
S
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
10
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
X
X
X
X
T
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X X
7
3
…or another ordering…
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
h = estimation function
101/11
7
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
102/11
7
The A* Algorithm
The A* Algorithm
X X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
10
X
X
10
X
X
10
X
X
X
X
X
X
X X X X X X X X X X X X X X
X
X
X
X
T
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X X
Min f = g + h
X X X X X X
X
X
X
X
X
10
X
10
X
10
X
10
X
10
X
X X X
X
X
X
X
X
X
X
X
X X X X X X
Max g
Min f = g + h
SIM/EMICRO 2013
The A* ALgorithm
Max g
SIM/EMICRO 2013
103/11
7
Porto Alegre, Brasil - Abril/2013
X X X X X X
X
X
X
X
X
10
X
10
X
10
X
10
X
10
X
X X X
X
X
X
X
X
X
X
X
X X X X X X
X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
10
X
X X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
Porto Alegre, Brasil - Abril/2013
104/11
7
The A* ALgorithm
X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
10 10 10
X
X X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
X X X X X X
X
X
X
X
X
10
X
10
X
10
X
10
X
10
X
X X X
X
X
X
X
X
X
X
X
X X X X X X
Straingth path from S to T
X X X X X X X X X X X X X X
X
X
X
X
10 10 10
X
10 10 10
X
10 10 10
X
10 10 10
X
10 10 10
X
X X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X
X X X X X X X X X X X X X X
Degrees of freedom
SIM/EMICRO 2013
SIM/EMICRO 2013
105/11
7
Porto Alegre, Brasil - Abril/2013
The A* Algorithm
Porto Alegre, Brasil - Abril/2013
106/11
7
The A* Algorithm
X X X X X X X X X X X X X X X X X X X
X
X
X
X
12 12 12 12
X
12 10 10 10 10 12
X
12 10 10 10 10 12
X
12 10 10 10 10 12
X
12 10 10 10 10 12
X
12 10 10 10 10 12
X
X X X X X X X X X X X X X X
X
X
T
X
X
X
X
X
X
X X X X X X X X X X X X X X X X X X X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X X X X X X X X X
X
X
16 16 16 16
X
16 14 14 14 14
X
16 14 12 12 12 12
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 X X X X X X
X
16
X
16 16 16 16 16 16 T
X
X
X
X
X
X
X X X X X X X X X
Maze router-like with obstacles
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
X X X X X X X X X X X
X
X
16
X
14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
X X X X X X X X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X
Maze router-like with obstacles
107/11
7
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
108/11
7
The A* Algorithm
So, Maze Router...
X X X X X X X X X
X
X
16 16 16 16
X
16 14 14 14 14
X
16 14 12 12 12 12
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 14 12 10 10 10 10
X
16 X X X X X X
X
16
X
16 16 16 16 16 16 T
X
X
X
X
X
X
X X X X X X X X X
has:
Nice Properties
• It always finds a path if there is one
• It always returns the shortest possible path
X X X X X X X X X X X
X
X
16
X
14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
12 14 16
X
X X X X X X X X
X
X
X
X
X
X
X
X
X
X X X X X X X X X X X
Saved
effort
but:
Advantages turn to be problems…
• The paths might be too complicated
• We rarely need “THE” optimal path…
SIM/EMICRO 2013
SIM/EMICRO 2013
109/11
7
Porto Alegre, Brasil - Abril/2013
On the other hand...
Porto Alegre, Brasil - Abril/2013
110/11
7
Routing Scopes/Applications
Maze Routers are known for having
3 Big Problems
• Memory
• Speed
• Ordering
• Roteamento detalhado
• Roteamento global
But today:
• We have plenty of memory, in general
• Speed can be addressed by A*, Hannan Grids
• Ordering can be dealt with by NEGOTIATION
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
• Roteamento especializado
111/11
7
(Steiner) Tree Topologies
MRST
BRST
SIM/EMICRO 2013
112/11
7
SIM/EMICRO 2013
114/11
7
Porto Alegre, Brasil - Abril/2013
Clock Routing
MRSA
Star
CSA
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
113/11
7
Porto Alegre, Brasil - Abril/2013
Package Routing
Other CAD tools
•
•
•
•
•
•
•
•
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
115/11
7
!
ou
y
k
n
ha
T
Physical Design and CAD Tools
Marcelo Johann
www.inf.ufrgs.br/~johann
[email protected]
Síntese - agregam informação ao projeto
Extração (análise)
Simulação
Verificação Formal
Otimização
Visualização
Processamento para fabricação
Projeção para novas tecnologias (tech CAD)
SIM/EMICRO 2013
Porto Alegre, Brasil - Abril/2013
116/11
7