Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C047 Finals Page 1002 10-10-2008 #19
1002 Handbook of Algorithms for Physical Design Automation
29. Y. -S. Kwon, P. Lajevardi, A. P. Chandrakasan, F. Honoré, and D. E. Troxel. A 3-D FPGA wire resource
prediction model validated using a 3-D placement and routing tool. In Proceedings of the 2005 International
Workshop on System Level Interconnect Prediction (SLIP), San Francisco, CA, pp. 65–72, 2005.
30. M. Alexander, J. Cohoon, J. Colflesh, J. Karro, E. Peters, and G. Robins. Placement and routing for three-
dimensional FPGAs. In Fourth Canadian Workshop on Field-Pro grammable Devices, Toronto, Canada,
pp. 11–18, 1996.
31. J. Karro and J. P. Cohoon. A spiffy tool for the simultaneous placement and global routing for three-
dimensional field-programmable gate arrays. In P roceedings of the Great Lakes Symposium on VLSI,Ann
Arbor, M I, pp. 230–231, 1999.
32. C. Ababei, H. Mogal, and K. Bazargan. Three-dimensional place and route for F PGAs. IEEE Transactions
on Computer-Aided Design, 25(6):1132–1140, June 2006.
33. V. Betz and J. Rose. VPR: A new packing placement and routing tool for FPGA research. In
F ield-Progr ammable Logic and Applications, London, U.K., pp. 213–222, 1997.
34. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multi-level hypergraph partitioning: Applica-
tions in VLSI design. In Proceedings of the ACM/IEEE Design Automation Conference, Anaheim, CA,
pp. 526–529, 1997.
35. P. Maidee, C. Ababei, and K. Bazargan. Fast timing-driven partitioning-based placement for island
style FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference, Anaheim, CA,
pp. 598–603, 2003.
36. C. Ababei, Y. Feng, B. Goplen, H. Mogal, T. Zhang, K. Bazargan, and S. Sapatnekar. Placement and routing
in 3D integrated circuits. IEEE Design and Test, 22(6):520–531, November–December 2005.
37. B. Goplen and S. S. Sapatnekar. Placement of thermal vias in 3-D ICs using various thermal objectiv es.
IEEE Transactions on Computer-Aided Design, 26(4):692–709, April 2006.
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1003 9-10-2008 #3
Index
A
Amplitude and intensity, for conventional mask, 709
Absorption metric, role of, 114
Abutment constraints, 172, 175–176, 199, 201

Accurate gate delay, steps of, 549
ACG, see Analytical constraint generation
Across chip linewidth v ariation (ACLV), 774
Actel ProASIC3 logic blocks, 947
Adapti ve tree adjustment technique, 574
Adhesion metric, of logic network, 448–449
Ad hoc look-ahead floorplanning, 302–303
Adjacency graph, 140, 151, 158, 178, 217, 224–225
Adjacency matrix, of graph, 114
Adjacent constraint graph
define, 224
for floorplan, 224–225
perturbations for, 226–227
properties of
directed edges, 225
geometrical relations, 225–226
Admittance propagation, 547
ADS, see Attached dead-space
Advanced simulated a nnealing algorithm, 317
Adva nced synthesis techniques, 823
Agglomerative clustering, 127–130
Aggressor net logic error, 42
Aggressor–victim pair, 44
AHHK spanning tree, 513
AHHK tree, euclidean plane, 513
Algebraic multigrid (AMG) technique, 378, 380, 923, 926
Algorithm for, buffer block planning, 661
Algorithmis complexity analysis, 73–74
Alpha 21264, 889, 901–904
clock

grids, 903
hierarchy, 902
GCLK grid, 901
global clock, distribution network of , 902
American map, definition of, 339
Analog floorplanning, 250–251
Analytical constraint generation, 295, 456
Analytical placement
algorithms, 284
basic idea of, 327
geometric partitioning, 337–341
netlength minimization of
linear netlength minimization, 331–332
netlength definition, 328–330
objecti ve functions of, 334–335
quadratic netlength minimization, 332–334
parallelization technique and macros, 344
partitioning information usages in, 341–343
quadratic placement properties, 335–337
repartitioning technique, 343–344
steps of, 328
Annealing schedule, 312–313
Anticipated plot, acceptance rate vs. generated ne w
configurations, 315
APlace, 365
and l og-sum-exp approximation, 366–369
relaxation in, 392–393
Appending, 226; see also Adjacent constraint graph
Application specific integrated circuit, 179, 450, 628, 942
counterparts, 957

and system-on-chip (SOC) design, 427
Approximation scheme; see also Fractional global routing
minimizing relative congestion, 635–638
adva ntages of approximation algorithm, 638
for any give n approximation ratio 1 + 
0
, 635
inequality, use of, 636–637
by linear programming duality (theorem 1),
expression, 636
maximum number of phases bounded by, 638
modified update rule for y
e
and prove to theorem,
635–638
theorem, with relative congestion at most 1, 635
upper bound on approximation ratio ρ, 637
minimizing total weighted netlength, 639–640
additional dual variable y
L,
use of, 639
to m i nimize total weighted netlength, 639–640
minimum-cost multicommodity flo w problem,
use of, 639
Steiner tree and total increment e xpression, 639–640
Arbitraryweighted graphs, 519
Arc, capacity of, 124–125
Area-optimal slicing floorplans, 177–178
ASIC, see Application specific i ntegrated circuit
Assignment problem

constructive methods for, 13
iterati ve methods for, 12–13
Asymptotic waveform evaluation technique, 586
Atomic test pattern generation (ATPG), 918
A-tree router, in congestion-driven placement
techniques, 463
Attached dead-space, 654–655
Augmenting path, 83
Automated wire-routing, 476
Automatic move strategy, 321
Avoid blockages, rip-up and reroute, 574
B
Backend-of-line (BEOL), 792
Bakoglu’s metric, 543
Balanced binary tree, 166–167
Basic blocks, 973; see also G AMA, linear-time simultaneous
placement and ma pping method
Basic logic element (BLE), 945
cluster basic and, 946
LUT coupled with a flip-flop, 946
Batched greedy a lgorithm ( BGA), 502
1003
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1004 9-10-2008 #4
1004 Index
Batched iterated 1-Steiner , 455
Batched 1-Steiner (B1S) algorithm, 492
Baxter number, 194
BBT, see Balanced binary tree
BB (V) model, 329
BC-subtrees, 576

BDD, see Boolean decision diagram
Bellman–Ford algorithm, 81–82, 668
Bell-shaped potential function, 367–369
Berkele y BSIM4 model, components, 919–920
Berkeley short-channel IGFET model (BSIM), 919
Berman algorithm, 503
Best-choice clustering method, 387–388; see also
Multiscale optimization, in placement
BFS, see Br eadth first search
Binary routing tree, 538
Binary search, concave segment, 526
Bin-based placement model a nd placement-dri ven
synthesis, 818
ne wcell insertion, 817
Bipartite graphs, i n rectangular dual, 144
Bisector list quad trees, 66–67
BI1ST, see Batched iterated 1–Steiner
4-Bit bus circuit simulation, 867
Block-based designs, evolution of, 259
Block-dominated design, 260
placement and partitioning, 269
Blocks
adjacency matrix, 121
define, 126
delay for, 40–41
interconnection of, 39–40
neighborhood graph, 143
pin access, wire, 616
BLQT, see Bis ector lis t quad trees
BNG, see Block neighborhood graph

Boltzmann distribution, 313, 322
BonnPlace placer, 339
Boolean decision diagram, 823
Boolean function in K-LUT, 958
Boolean network logic s ynthesis, 610
Bossung plot, 726
Bottleneck gaps thin wire, 621
Bottom-up moment computation, 548
Bottom-up solution propagation process, 581
Boundary constraint, 199
B
∗
-tree conditions and, 233–234
checking, algorithm for, 200
modules, 233
in slicing floorplans, 173–174
Boundary merging and embedding (BME), 892
Bounded quad trees, 68
Bounded-radius bounded-cost, 511
Bounded-radius minimum routing tree, 511
Bounded-skew routing tree (BST), 892
Bounded-sliceline grid
constituents of, 216
perturbations, 218
transformation into placement, 217–218
Bounding boxes in estimating distance, use of, 844
Bounding box netlength, 329, 332, 335
BQT, see Bounded quad trees
BRBC, see Bounded-radius bounded-cost
BRBC spanning tree algorithm, 512

Breadth first search, 78
runtime comple xity of, 79
Brent–Kung scheme, 946
BRMRT, see Bounded-radius minimum routing tree
BSG, see Bounded-sliceline grid
B
∗
-tree
admissible placement and, 207–208
perturbations, 208
Buffer
blockage, 570
long wire insertion, 265
Buffered clock trees, 888–889
Buffered paths
blockage avoidance
dynamic programming-based method, 571–572
graph-based approaches, 572–573
Buffered Steiner tree, environment aware
placement and routing congestion
measurement of, 577–578
plate-based tree adjustment
dynamic programming-based adjustment, 578–579
hybrid approach for tree adjustment, 579–581
relating buffering candidate locations
layout environment, 582–583
Buffered tree with blockage avoidance
simultaneous tree construction and buffer insertion
dynamic programming-based method, 574–575
graph-based method, 575–577

tree adjustment technique, 574
Buffer graph, 572
Buffering cost, 557
Buffering routes and blockages, interaction, 559
Buffering signal polarity, 558
Buffering sinks, 558
Buffer inse rtion, 545
parts of, 580
Buffer inse rtion algorithms, majority of, 580
Buffe r library, 542
Buffer planning, 246; see also Interconnect planning
Buffer positions, low congestion path, 580
Bus-driven floorplanning, 247
C
CAD, see Computer-aided design
Candidate buffer block, 653–654, 660–661
Capaciti ve coupling noise injection, circuit
and waveforms, 675
Capo fixes blocks, 303
Catastrophic yield optimization methods, in y ield
optimization, 783–785
CBB, see Candidate buffer block
CBL, see Corner block list
CD, see Critical dimension
Cell area, clustering in, 130
Cell-based flow design, thermal vias, 987–989
Cell compilation, 19–20
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1005 9-10-2008 #5
Index 1005
Cell labeling, coding schemes for, 477

Cell mirroring technique, in local im provement, 414–415
Cell modeling and decoupling capacitance, 916–918
Cell shifting technique, in space management, 410
Channel routing
algorithm, 471
constraints, 14–15
in design styles, 1 4
phase problem between placement and, 18, 22
terminology in, 15
Chemical–mechanical polishing, 697, 737–739
aware global routing, illus t ration, 796
characterization and modeling of, 741–747
density analysis methods in, 747–749
design flows for fill synthesis, 760–765
fill synthesis methods
density-driven fill synthesis, 749–754
impact on interconnect performance, 754–758
model-based fill synthesis, 754
STI fill insertion, 758–760
impacts on interconnect design and manufacturing,
739–741
model, 795
process, 921
wire density distribution, 793
Chemical vapor deposition (CVD), 758
Chip fabrication
field programmable gate arrays, 18
masks for, 17
Chip-level signal-integrity verification, 681
Circuit, dia gram of, 110

Circuit hyper graphs, 110
Circuit sizes, acceptance rate vs. generated
ne w configurations, 315
Classical floorplanning
interconnect, 241
module shape and flexibility, 240–241
outline-free vs. fixed-outline, 240
Classical slicing floorplan design, 169
mincut-based method, 170
point-configuration based, 171
simulated annealing based, 171–172
CLBs, see Configurable logic blocks
Clique
define, 110
model, 112, 329, 333
net model, 129
Clock-aware placement, 283
Clock network design, 897
Alpha 21164
clock driver locations and delay, 890
ALPHA 21264, 901, 904
clock hierarchy, 902
GCLK and clock grids of, 903
global clock distribution network of, 902
clock
hazards and timing c onstraints, 892
skew sc heduling, 891–893
handling variability, 893–894
IBM PO WER4, 900–901
global clock distribution network, 900

IBM S/390, 900
clock distribution network, first-level tree, 898
last/macrolevel clock distribution, 899
Intel Itanium, 907
clock distrib ution t opology of, 908
deskew buffer architecture of, 909
global core H-tree of, 908
thirty regional clocks o f, 909
Intel Itanium 2 clock distrib ution, 909–910
dual-core, 911
Intel Pentium 4, 905
global clock distribution in, 906
90-nm Pentium 4, eight stripes, 907
three spines in a 0.18-µ m Pentium, 906
Intel Pentium I I
global clock distribution n etwork of, 904
Intel Pentium I II
two-spine global clock distrib ution of, 905
metrics for
clock sk ew and transition time, 882
phase delay/latency, area and power, 883
nontree structures, 889
grid and spine, 889–890
hybrid, 890–891
tree structure, 883
deferred merge embedding (DME), 887–888
exact zero-skew algorithm, 885–887
geometric matching algorithm (GMA), 884–885
method of means and medians (MMM), 884
wire width and buffer considerations in, 888–889

Clock signal, logic blocks, 29
Closure problems, 22
Clustering, 126–127
agglomerative, 127–130
define, 109–110
hierarchical, 127
Clustering algorithms, 958
multileve l, 962
Clustering based approaches, in multilevel optimization,
385–386
Clustering metrics, 112–114
CMOS, see Complementary metal oxide s e miconductor
CMOS circuit, charge/discharge operation, 44–45
CMP, see Chemical–mechanical polishing
CMP process models, 741–742
Coarse-grained power gating with macro/core, 832
Coarsening algorithms, for multiscale placement, 386–387
Coherent illumination, 717
Combinational circuit, 590
Combinational logic circuit, as timing graph, 39–40
Combinatorial optimization algorithm, goal of, 311
Common path pessimism removal, 786
Compaction
layout, 20
two-dimensional and one-dimensional, 63
Complementary metal oxide semiconductor, 181, 674, 901,
904–905, 907, 909–910, 919, 942
Completely embedded and buffered tree, 561
Computational geometry
based placement migration method, in space

management, 409–410
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1006 9-10-2008 #6
1006 Index
convex hull, 85–86
Voronoi diagram and Delaunay triangulation, 86
Computation by superposition, 704; see also
Lithographic modeling
array multiplication, 704–705
fast Fourier transform, 705
pixel r epresentation of the mask, 704
pixel representation of the pupil, 704
Computer-aided design, 139, 509, 914
tools, 957
Configurable logic blocks, 180, 946
Congestion-aware logic synthesis, 449–450
Congestion-driven placement techniques, 447
global-placement congestion improvement
free space management, 455–456
incorporating congestion estimation, 452–454
steiner wirelength optimization, 454–455
netlist-connectivity-based
congestion-aware logic synthesis, 449–450
metrics for structural logic synthesis, 448–449
perimeter-degree, 450–452
router integration in, 458
simulated annealing for
A-tree router, 463
over flow ( OF), 462–463
RISA routability model in, 461–462
sparse parameter, 463–464

whitespace management in, 458–460
Congestion-driven routing, 981
Congestion estimation, placement-level
fast global routing
estimation based, 606–607
with probabilistic methods, 607–608
fast m e trics for routing congestion, 601–602
probabilistic estimation methods, 602–606
Congestion ev a luation metrics, 245–246
Congestion minimization, 689
Connecti vity factor, 160–161; see also
Clustering algorithms
Conservative noise filter s, hierarchy, 684
Constraint functions, 96, 102
Constraint graph and constraint hypergraph
for noise cluster, 686
Constraints, convex, inconsistency of, 14
Constraints, vertical, 14
Constructive congestion map generation, 608–609
Contemporary layout with printing features and S RAF, 708
Contemporary scanner lens design, 718
Continuous wire sizing, 588
Contour-based EPE, 715–717
Convex cone, 91
Convex functions , 91–92
Convex hull, 85–86
of subgradients of dual function, 97
Convex optimization problem, 92
global optimal s olutions, 93
Convex pruning, nonredundant candidates, 552–553

Convex quadratic program , 592
Convex se ts, 90–91
Copper CMP modeling, 743–745
Corner block list
corner block, 187–188
define, 188–189
extended (see Extended CBL)
floorplanning algorithm, 188–189
linear-time transformations between floorplan and, 189
Corner Sequence, 208
construction from placement, 209
perturbations, 211–213
transformation into placement
dynamic sequence packing scheme for, 209–211
solution space, 210
Corner stitching data structure
generalizations to geom etries, 65
pointers for tile, 63
point-find operation in, 64
Coupled tree network circuit simulation, 867
Coupling capacitance, 475
Coupling noise
causes of, 42
transient approach to calculate, 44
Coupling noise phenom enon
coupling noise injection, 675–676
interconnect capacitance, 674–675
CPM-based a lgorithm
application to timing graph, 39
on a circuit with inverting gates, 4 0

CPPR, see Common path pessimism removal
Critical area analysis (CAA), 697, 826
Critical-area-aware routing for random defect minimization,
796–798
Critical-area rectangles (CARs), 780
Critical dimension, 726, 728, 740, 774, 787
Critical nets environment, cost impact of, 581
Critical-sink routing t ree problem (CSRT), 520
CS, see Corner Sequence
C-Tree, algorithm, 560
Current deep-submicron technologies, 866
D
DAG, see Directed acyclic gr aph
Data structures
geometric
benefits of, 57
interval trees, 57–58
kd trees, 58–59
max-plus lists (see Max-plus lists)
spanning graphs, 59–60
DDM, ilustration of, 724
Dead spaces, 654
Deep submicron (DSM) technologies, 277, 448
Deferred merge embedding (DME), 887–888
algorithm, 894
Degree of freedom (DOF), 763–764, 801
Delaunay triangulation, 86
Delay-locked loop (DLL), 905
Depth first search
process, 78

runtime comple xity of, 79
Depth-first search, 78–79, 205, 207, 450
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1007 9-10-2008 #7
Index 1007
Depth-of-focus (DOF), 763–764
Design automation
for layout synthesis, 14
modern flows in, 23
Design for manufacturability (DFM), 786, 805–806, 856
Design of deep submicron v erylarge scale integration (VLSI)
circuits, 586
Design rule checker/checking, 62, 69, 729, 764, 778, 792,
802–803, 805, 857
Deskewing techniques, 882
Detached dead-space (DDS), 654
3D floorplanning, 250
in slicing flooring, 181–182
3D floorplan representations
3D-subTCG (see 3D-subTCG)
sequence triplet (see Sequence triplet)
T-trees (see T-trees)
2D Fourier transform, 702
DFS, see Depth–first search
Diffusion-based placement migration technique, in space
management, 408
Diffusion (diff) layer, 62
Digital frequency dividers (DFDs), 910
Digital signal processing (DSP), 874, 952–953
Dijkstra’s algorithm, 81, 975
Dijkstra’s shortest path algorithm, 572, 573

Dijkstra’s shortest paths tree, 518
Directed ac yclic graph, 170, 449
Directed Ac yclic Graph (DAG), 79, 170, 178, 449–451, 582
Discrete cosine transform (DCT), 360
Discrete Fourier transform (DFT), 705
Discrete wire sizing, 588–589
Distribution characteristic function (DCF), 755–756
Domain decomposition method (D DM), 723–724
Domain des kewregister (DDR), values of, 906
DP, see Dynamic programming
3D-packing, of sequence triplet, 231
Dragon2006, mixed-size placement in, 299
Draininduced barrier lowering (DIBL), 919
DRC, see Design rule checker/checking
3D-SUBTCG
placement with modules, 231–232
topological representation, 232
transitive graphs, 231
Dual-core Itanium 2 microprocessor, clock distribution, 911
Dual function, 94
Dynamic netweighting algorithms, 433
Dynamic netweighting, intiming-driven placement, 432–434
Dynamic power
approach to reduce, 46
CMOS circuit, 44–45
Dynamic programming
algorithm, 311
in linear placement, 419–420
based buffered path algorithm
pseudocode of, 572

di vide-and-conquer approach, 77
example, 76–77
in mathematical partitioning formulations, 126
method, in floorplanning, 158
E
ECBL
λ
, see Extended CBL
Ecos and accounting, 267–268
ECO-system, 305
EDA, see E lectronic design a utomation
EDA flow, 696
Edge placement error, 713, 715, 799–800
Edge-separability clustering (ESC), 387
Electrically erasable programmable read-only memory
(EEPROM), 942
Electrical violations, 581
Electric amplitude of diffraction (EAD), 799
Electronic design automation, 628, 696, 840,
856–857
Elmore delay, 24, 30, 510, 536
based routing constructions, 520–522
calculations, 318
formula, analyses of, 510
limitations of, 35
model, 524–525, 543, 546, 572
for nontree RC netw ork, 33–34
for RC trees
additi ve property, 33
between two nodes, 32

sle w, 34–35
step response, in circuit analysis, 31–32
Elmore routing tree, 520, 522, 524
Embedded computation blocks
embedded processors, 953
multipliers and DSP blocks, 952–953
Embedded memory blocks (EMBs), 950–952
Embedded topology tree, 561
Empty room insertion process, 198
EPE, see Edge placement error
ERT, see Elmore routing tree
ERT algorithm
Elmore delay formula, 520
timing-driven SERT, 520
Euclidean traveling salesman problem, 503
E-V matrix, formation of, 999
Exact zero-skew algorithm, 885–887
Extended CBL
definition of, 189
solution space of, 190
Extended Krylov subspace (EKS), 927–928
Extraction, 731; see also PV-bands
Extremal-density window analysis, 747
F
Facial k-cycle, 149
Fanin cones
depth-optimal mappings, 959
fanout and sibling relationships, 971
Fast Fourier transforms (FFTs), 705, 717,
742–743

Fast global routing techniques, 606–608
Fast lookup table based wirelength estimation
technique, 455
FastPlace, fixed points in, 357–359
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1008 9-10-2008 #8
1008 Index
Fast tim ing metrics, 35
FDP/LSD, relaxation in, 393
FDTD, see Finite–difference time domain
Feasible routing region ( FRR), 785
Fiduccia–Mattheyses (FM)
algorithm, 436
in classical slicing floorplan design, 170
heuristic method, 115–116
improvements on, 116–117
partitioner, 305
Fiedler vector, 120
Field programmable g ate array lookup table
(FPGALUT), 322
Field programmable g ate arrays, 117, 162, 322,
386, 458, 941, 957
antifuse-based, 944
commercial FPGAs, 952
design flow for, 958
3D designs using FPGAs, 993–994
estimation of, 994–997
monolithic 3D technology, 996
and switch, 998
embedded computation blocks
multipliers and DSP blocks, 952–953

soft and hard embedded processors, 953
flash-based
flash switch in, 943–944
hierarchical placement, 969
island-style placement, 967–968
linear datapath placement, 972–974
logic and memory in, 951
lookup-tables (LUTs), 944
carry chains, 946–947
clusters, 945–946
flip-flop coupling with, 946
low power placement, 975
memories
distributed, 952
embedded, 950
logic interconnect architecture and block, 951–952
non-LUT-based logic blocks, 947
physical synthesis and incremental placement
methods, 969–972
placement algorithms, 966
routing architectures, 947–948
bus-based routing architectures, 949–950
pipelined interconnect architectures, 950
programmable switches, 948
segmentation, 947–948
switch blocks and connection blocks, 948–949
SRAM-based
disadvantages of, 942–943
variation-aware placement, 974–975
Xilinx, Altera, and La ttice, vendors of, 942

Figure of merit (FOM), 426, 428, 430
Fine-grained power gating within block, 832
Fine-granularity clustering method, 389; see also
Multiscale optimization, in placement
Finite-difference time domain, 720–723
First-in-first-out (FIFO) schemes, 116
Fixed-die r outing model, 402
Fixed layout region placement, 281
Fixed-outline floorplanning, 240
automated
Parquet, 243
slack-based moves, 242
Fixed points
define, 352–353
in FastPlace, 357–359
in mFAR, 353–357
Flat floorplan, 261
Flat placements, cell color code, 263
Flip-flop insertion, 265, 549
FLM architecture, 944–945
Floorplan/microarchitecture interactions
cycle-accurate simulators and, 247
SA algorithm, 248
Floorplanner
estimating parasitics and timing, 265–266
hierarchical design style, 259
Floorplanning, 4; see also Interconnect planning
academic vs. industrial, 261
ad hoc look-ahead, 303
branch-and-bound strategy for sizing, 156–157

canonical embedding of, 150
classical (see Clas sical floorplanning)
data structure, 966
definition of, 139–140
3D floorplanning problem , 989
dynamic, 964–966
on FPGAS with heterogeneous res ources, 963–964
heterogeneous FPGA, 179–181
hierarchical, 151–153
application of, 19
methods, 961–963
placement, 302
knowledge-based, 157–158
with macro clustering, 301–303
macros in bin, 303
for m anufacturability, 252–253
method for topology generation and sizing, 158
module locations, 242
optimization, 20–21
and power/ground cosynthesis, 249
problem, def ine, 204
process of, 266
rectangular duals and, 141–142
dualizability, 142–145
slicibility of, 145–147
sizing algorithms, 154–155
sizing methods, 153
for specialized architectures
analog circuits, 250–251
3D integrated circuits, 250

FPGA, 249–250
statistical (see Statistical floorplanning)
success of, 19
topology generation, 140–141
Floorplans, 18; see also Floorplanning
constraints
boundary constraints, 233–234
rectilinear modules, 234–236
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1009 9-10-2008 #9
Index 1009
define, 161, 188
design, placement constraints in
boundary check, 200
boundary constraints, 199
CBL, 199
design problem, 162–163
design, success of, 19
mosaic (see Mosa ic floorplan)
power consumption of, 168–169
quarter-state sequence of (see Quarter-state
sequence)
representation (see Cornor block list; Q-sequence;
Twin binary sequence; Twin binary trees)
Flow and dif fusion-based legalization technique, 411
Flow-based overlap removal method, in space
management, 404–405
transportation problem, calculation of, 406–408
transportation problem, solving and setting the,
405–406
FlowMap tool, 959

FLO YD, in floorplanning, 157
FLUTE, see Fast lookup table based wirelength
estimation technique
FLUTE algorithm, 503
FLUTE in floorplanning, 157
FM algorithm, principal modification to, 117
FMAX testing, in yield loss, 773
FM iterative improvement par titioning algorithm,
bucket structure in, 116
Focused ion beam (FIB), 773
Force-directed methods, 347–349
basic elements of
force-based spreading, 351–352
quadratic optimization preliminaries, 349–351
enhancements in
interleave d optimizations, 361–364
multilev el optimization, 364
issues related to, 371–373
nonquadratic, continuous methods
aplace and log-sum-exp approximation,
366–369
mPL g eneralization of, 369–371
placement via line search, 365–366
spreading cells techniques
fixe d points and bin shifting, 352–359
frequency-based methods, 359–360
Force-directed net-constraint placement, 437
Force-directed placer (FDP), 352, 362–363, 365, 386,
391, 393
Force-directed relaxation, 12

Ford Fulkerson method, run-time complexity of, 83
Four-cycle theorem, 146
Fourier lens, 717
Four routing solutions, for four-pin net, 518
FPGA, see Field programmable gate array
FPGA floorplanning, 250; see also Floorplans
problem in, 249
FPGAs, see Field programmable gate arrays
Fractional global r outing, 629
dual linear program of linear program, 630
with the dual solution, example for, 631
extensions, 641–642
coupling capacitance and parallel m ultithreaded
implementation, 642
fully polynomial-time approximation scheme for,
634–635
minimizing the relative congestion, 635–638
minimizing the totalweighted netlength, 639–640
linear programming relaxation, 629
relati ve congestion of edge (e), 630
theorem 1: given any nonnegative v alues y
e
for edge, 630–631
verification, theorem 1, 631
Fractional packing problems, 633
Fracturing on mask write time, effects, 858
Fraunhofer diffraction formula, 702
Free space m a nagement, in global placement, 455–456
Front-end process, 258
Full multigrid (FMG), 380

Fully polynomial-time approximation schemes
(FPTAS), 634
Functional noise
failure criteria for, 679–681
approach noise budgeting, use of, 681
based on using local noise threshold values, 680
digital gates s uppress propagation of pulses, 679
propagation of injected noise pulse, 679
types of, 677
G
GAMA, linear-time simultaneous placement and mapping
method, 972–974
Gamma statistical distribution, 35–36
Gate arrays, 14
Gate capacitors, char ging and discharging of, 45
Gate sizing
incremental synthesis, 820–822
with multiple-VT libraries, 819–820
Gate sizing problem, as GP, 103–104
Gate tunneling current, 46
Gaussian variable, 974
Gcells, 843
congestion measurement on every layer
at boundaries, 846
with routing nodes, 845
GCLK grid of ALPHA 21264, 901–903
General routing-tree topology, 524
Genetic programming
adva ntage o f, 322
stochastic algorithm, 322

Geometric data structures
benefits of, 57
interval trees, 57–58
kd trees, 58–59
Geometric matching algorithm (GMA), 884
recursive steps of, 885
Geometric programming
convex reformulation of, 102–103
gate sizing problem, 103–104
GiLa algorithm, 551
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1010 9-10-2008 #10
1010 Index
Global clock grid (GCG), 907
Global interconnects on circuit performance,
planning basics, 645
buffer blocks and sites, 649–650
buffer block planning, 650–652
buffer site planning, 652–653
buffer planning basics, 646–648
buffer and wire model, 647
feasible regions, for buffer insertion, 647–649
independent feasible re gions (IFR), 649
parameters of wire and buffer, 648
two-dimensional feasible region, 649
flip-flop and buffer planning
area constrained wire retiming, 668–669
latency c onstrained optimization, 666–667
minimizing latency, 664–666
wire retiming, 667–668
interconnect planning and buffer planning

buffer planning with noise constraints, 661–663
noise-awa re buffer planning, 658–661
pin assignment with buffer planning, 657–658
routability-dri ven buffer planning, 653–656
Global placement algorithms, 278, 281
Global-placement congestion improvement
free space management in, 455–456
incorporating congestion estimation in, 452–454
Steiner wirelength optimization in, 454–455
Global r outing, 792
algorithms, 470
cells, 600
commonly used metrics for
bend count, 474
congestion, 473–474
coupling, 475
timing, 475
wirelength, 474–475
design constraints, 616
grid models for
capacity computation, 472–473
channel-based graph model, 470–471
tile-based graph model, 471–472
of m ultiple net
concurrent, 484
sequential, 482–484
objecti ve of, 473
as phys ical design process, 469
problem formulation, 628–629
global routing graph with two l ayers, 628

for minimizing the maximum relative
congestion, 629
of single net, 475–476
Lee’s maze routing algorithm, 476–477
line-search algorithms, 479–481
maze-routing enhancements, 477–479
with multiple terminals, 481–482
pattern routing, 481
VLSI minimum-area, 488
X interconnect architecture, 843
Gordian method, for bipartitioning, 338
GP, see Geometric p rogramming
Graph-based routing, 979–980
Graph-based simultaneous tree construction
and buffer insertion, 576
Graphical user interf aces (GUIs), 258
Graph iterated 1-Steiner (GI1S) algorithm, 494
time complexity of, 499–500
Graphs
directed, 82
minimum spanning tree of, 79
Kruskal’s algorithm a nd Prim’s algorithm, 80
path, tree, and cycles, 77
searching by
breadth first s earch, 78
depth first search, 78–79
topological ordering, 79
shortest paths in
Bellman Ford algorithm, 81–82
Dijkstra’s algorithm, 81

single-source shortest path problem, 80
theory, 77
Graph Steiner arborescence (GSA), 515
Graph Steiner mi nimal tree (GSMT) problem, 494
Greedy algorithms, 75
Grid-based
approaches, congestion computation by, 245–246
detailed routing system and D RC correction flow, 803
Gridded routing space rotation, 849
Grid expansion algorithm
input of, 10
space complexity, 10
techniques to reduce, 11
Grid-warping partitioning, 339–340
Grid warping technique, in space ma nagement, 410–411
Group Steiner trees, 496–497
applications of, 497–498
bounded-radius, 501–502
depth-bounded, 498–499
empirical performance of, 502
H
Hadlock’s minimum detour algorithm, 477
worst-case time complexity of, 478
Half-perimeter wire length, 291, 293–296, 303–304,
349, 361, 365–366, 378, 392, 400, 425, 438,
454–455, 457–458, 463
Half-rectangle perimeter, 601
Hall placement, 13
Hanan grid, 522
minimum Steiner tree embedded, 523

points, 491, 528
Hanan’s theorem, 489
Hard processors, 953
Hardware description l anguage (HDL), 259
Heavy-edge ma tching, 126–127, 387
Heterogeneous FPGA floorplanning, 179–181
Heuristic Steiner tree, cost of, 511
H-flipping operation, 885
H-gamma, 35–36
Hierarchical clustering, 127
Hierarchical floorplanning, 5, 23, 151–153
Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C048 Finals Page 1011 9-10-2008 #11
Index 1011
Hierarchical moment computation, 594
Hierarchical partitioning method, 923–924
Hierarchy, use of
vs. flat design, 262
floorplanning and prototyping, 261
logical vs. physical, 262–263
High density plasma (HDP), 759
Hightower algorithm, 480
Hinted quad trees
for design-rule checking, 69
vs. QLQT, 69–70
HiPRIME algorithm, 928
Hopkins approach, 719
Horizontal constraints, 14
Hot electron injection (HCI), 676
HPWL, see Half–perimeter wirelength
HQT, see Hinted quad trees

HRPM, see Half–rectangle perimeter
H-tree structure, clock network, 884
Huang’s metric, 112
Hungarian method, 12
HV trees
bounds and, 69
components of, 68
Hwang’s theorem, 492, 504
Hybrid mesh/tree structure, 928
Hypergraph (GPS90), 126
Hypergraph partiti oning, define, 112–114
I
IBM01 benchmark, from IBM-MSwPins
in four-tier 3 D process, 987
placement, before and after legalization, 299
placement in four-tier 3D technology, 987
progress of mixed-size floorplacement on, 297
IBM Power4, 900–901
IBM S/390 clock distribution network
Enterprise Server Generation-4 system, 898
first-level tree of, 898
last/macrolevel clock distribution, 899
IC chip, heat transfer from, 48–49
IC floorplanners, 261
IDDQ testing, in yield loss, 773
IDOM algorithm, ex ecution a nd producing
arborescences, 519
ILD, see Interlayer dielectric
Incidence matrix, define, 119
Incremental floorplanning problem, 244–245

Incremental mincut placement, 306
Incremental netweighting, 433
Incremental placement algorithm, 971
Incremental timing analysis, in tim ing-driven
placement, 432
Inductance
CAD tools and performance, requirements, 876–877
effects of, 871
coupling on delay uncertainty, 873–874
on delay and signal rise time, 872
on power dissipation, 873
historical perspective, 865–866
importance of, 866–868
inducti ve noise, 874–876
physical design, effects, 877–878
power and clock distribution networks, 878
Industrial floorplanning
chip, design of, 258
chip, versions of, 258
design and capabilities of
common changes, 267–268
incomplete and inconsistent designs
working with, 268
power supply design, 266–267
steps of, 257
Industrial global routers, 606
Inferior solutions, define, 542
INLP, see Integer linear program
Integer linear program , 124
Integer linear programming (ILP), 252, 484, 656, 754

Integer p rogramming formulations, 123–124; see also
Mathematical partitioning formulations
Integrated circuit
mechanisms of substrate noise propagation in, 876
yield of, 771
Integrated circuit, 3D, 986
Intelligent fill synthesis, 764
Intel IA-64 architecture, 907–908
Intel Pentium III microprocessor, 905
Interacti ve floorplanning, 244
Intercluster placement, 962–963
Interconnect delay, 3–4, 585
Interconnect performance, CMP f ill impact, 754–758
Interconnect planning
bus-driven floorplanning, 247
congestion considerations during
grid-based approaches, 246
probabilistic map, 245
with fixed interval buffer insertion constraint, 655
dead spaces, partitioned into ES blocks
and c omputation, 656
methodology, as inte ger linear program (ILP), 656
integrated buffer planning and, 246–247
routability-dri ven buffer planning, 653–654
coarser tile structure, use of, 653–654
congestion cost, of routing tile in two-le vel tile, 654
with dead space redistribution, 654–655
defining CBB locations, 653
VLSI design methodologies, 653
Interconnect tree, 589

Interconnect wires, coupling and grounded
capacitances of, 675
Interior merging and embedding (IME), 892
Interlayer capacitance, 472
Interlayer dielectric, 739–740, 754, 762
International Symposium on P hysical Design, 4, 7, 286,
300–301, 303, 394, 443, 484
International Technolo gy Roadmap for Semiconductors,
762, 775, 913
Interval trees, 57
for set of intervals, 58
Inverter processing, 821–822