PHYSICAL DESIGN
GRAPH THEORY IN
PLACEMENT & ROUTING
ADVANCED 20 INTERVIEW
QUESTIONS WITH SOLUTIONS
KEY TOPICS
Minimum Spanning Trees (MST)
Shortest Path Algorithms
(Dijkstra, A*)
Steiner Trees for Wire
Optimization
Graph Coloring for Routing
Congestion
Maximum Flow in Routing
Channels
Interview Guide
and Many More
By ProV Logic
INTRODUCTION
Graph theory plays a crucial role in physical design, particularly in
placement and routing. The goal of placement and routing is to
determine the optimal layout of standard cells, macros, and
interconnects while minimizing wire length, congestion, and
delay. Graph-based algorithms are widely used to model and
solve these optimization problems efficiently.
KEY GRAPH THEORY CONCEPTS IN PHYSICAL
DESIGN
1. Graph Representation in VLSI
A circuit can be represented as a graph, where:
Vertices (nodes) represent cells or routing points.
Edges represent connections (nets) between these
components.
2. Minimum Spanning Tree (MST)
Used for net routing to minimize wire length.
Algorithms: Prim’s algorithm, Kruskal’s algorithm.
3. Shortest Path Algorithms
Used in global routing to determine the shortest interconnect
path.
Common algorithms: Dijkstra’s algorithm, A algorithm,
Bellman-Ford algorithm*.
4. Steiner Tree Problem
Used to optimize routing paths by adding extra points (Steiner
points) to reduce wire length.
5. Graph Coloring in Congestion Analysis
Helps determine the minimum number of routing tracks
needed in a routing channel.
6. Maximum Flow Algorithms
Used in power and current flow analysis in power grids.
Algorithm: Ford-Fulkerson method.
INTERVIEW QUESTIONS ON GRAPH THEORY
IN PHYSICAL DESIGN
Q: Given a set of pins P = {P1, P2, P3, P4, P5} with the following
distances:
P1-P2: 3
P1-P3: 2
P2-P3: 1
P2-P4: 4
P3-P4: 2
P3-P5: 3
P4-P5: 1
Find the minimum spanning tree (MST) using Kruskal’s
algorithm.
Solution:
1. Sort the edges in increasing order:
P2-P3 (1)
P4-P5 (1)
P1-P3 (2)
P3-P4 (2)
P1-P2 (3)
P3-P5 (3)
P2-P4 (4)
2. Select edges without forming a cycle:
Include P2-P3 (1)
Include P4-P5 (1)
Include P1-P3 (2)
Include P3-P4 (2)
3. Final MST edges: (P2-P3, P4-P5, P1-P3, P3-P4)
4. Total cost of MST = 1 + 1 + 2 + 2 = 6.
Final Answer: The minimum spanning tree has a cost of 6.
Q: Given a grid-based routing problem, where a signal must
travel from node A to node F, and the weight of each edge
represents the wire length, find the shortest path using
Dijkstra’s Algorithm.
From → To Weight
A→B 4
A→C 1
B→D 5
B→E 2
C→E 3
D→F 2
E→F 1
Solution:
1. Initialize distances:
Start at A, set A = 0, all others = ∞.
2. Select the smallest distance node (A):
Update B = 4, C = 1.
3. Select the smallest distance node (C):
Update E = 1 + 3 = 4.
4. Select the smallest distance node (B):
Update D = 4 + 5 = 9, E = 4 (no change).
5. Select the smallest distance node (E):
Update F = 4 + 1 = 5.
6. Select F (destination reached).
Final Answer: The shortest path from A to F is A → C → E → F
with a total cost of 5.
Q: Given four points P1, P2, P3, P4, compute the Steiner Tree to
minimize total wire length. Assume a Manhattan distance
metric.
Solution:
1. Compute the direct MST (without Steiner points).
2. Identify potential Steiner points (grid intersections not
originally in the netlist).
3. Choose Steiner points that minimize wire length.
4. Construct the final routing tree.
Let’s assume:
Direct MST cost = 10 units.
With an added Steiner point (S), optimized cost = 8 units.
Final Answer: Using a Steiner point reduces routing cost from
10 to 8.
Q: Given a routing channel with 5 nets, determine the minimum
number of tracks needed using graph coloring.
Solution:
1. Model the problem as a graph where each net is a vertex and
an edge represents nets that overlap in routing.
2. Apply graph coloring (each color represents a track).
3. Calculate the chromatic number (minimum number of colors
required).
Let's assume:
Nets: A, B, C, D, E
Conflict pairs: (A, B), (A, C), (B, D), (C, E), (D, E)
Graph coloring gives Chromatic Number = 3.
Final Answer: Minimum tracks needed = 3.
Q: A routing grid has 4 sources and 4 sinks, with given
capacities between them. Use Max-Flow (Ford-Fulkerson
Algorithm) to determine the maximum current flow.
From → To Capacity
S1 → N1 10
S1 → N2 5
S2 → N2 15
S2 → N3 10
S3 → N3 10
S3 → N4 5
S4 → N4 10
N1 → T1 10
N2 → T2 10
N3 → T3 10
N4 → T4 10
Solution:
1. Construct the flow network.
2. Find augmenting paths with available capacity.
3. Push flow along the paths and update residual capacities.
4. Repeat until no more augmenting paths exist.
Using Ford-Fulkerson, we get:
Maximum Flow = 20 units.
Final Answer: Max Flow = 20 units.
Q: Given a design with 1000 logic gates and a Rent exponent of
0.6, estimate the total number of interconnects using Rent’s
Rule:
W=k⋅Np
where k=4 (Rent’s coefficient) and p=0.6 (Rent’s exponent).
Solution:
W = 4 × 10000.6
W = 4 × 63.1 ≈ 252
Final Answer: Estimated number of interconnects = 252.
Q: A critical path in a circuit has a required time of 10 ns and an
actual arrival time of 12 ns. Calculate the slack.
Solution:
Slack = Required Time - Arrival Time
= 10 − 12 = −2 ns
Final Answer: Slack = -2 ns (negative, indicating timing
violation).
Q: Given a set of nets that must be routed in a channel, with a
maximum overlap of 4 nets at any horizontal segment,
determine the minimum number of tracks required.
Solution:
The minimum number of tracks required is equal to the maximum
overlap at any segment.
Final Answer: 4 tracks are required.
Q: A clock signal reaches Register A at 3 ns and Register B at 5
ns. What is the clock skew?
Solution:
Clock Skew = Arrival time difference
=5−3=2 ns
Final Answer: Clock Skew = 2 ns.
Q: A wire has an intrinsic delay of 2 ns/mm. If a buffer reduces
the delay per mm to 0.5 ns and is inserted at 5 mm intervals,
what is the total delay for a 20 mm wire?
Solution:
Without buffering:
20 × 2 = 40 ns
With buffering:
(4 segments × 5 mm) × 0.5 = 10 ns
Final Answer: Total delay with buffering = 10 ns.
Q: Given a CMOS circuit with supply voltage Vdd=1.2V,
switching frequency f=100 MHz, load capacitance CL=10 fF,
calculate the dynamic power dissipation.
Solution:
Dynamic Power formula: P=CLVdd2f
= ( 10 * 10-15) * (1.2)2 * (100 * 106)
= 1.44 x 10-6 W
=1.44 µW
Final Answer: Power dissipation = 1.44 µW.
Q: A clock signal reaches Register A at 3 ns and Register B at 5
ns. What is the clock skew?
Solution:
Clock Skew = Arrival time difference
=5−3=2 ns
Final Answer: Clock Skew = 2 ns.
Q: A wire of resistance 100 Ω and capacitance 50 pF has an RC
delay of?
Solution:
RC Delay =
R × C = 100 × 50 × 10−12 = 5 ns
Final Answer: RC delay = 5 ns.
Q: Two adjacent wires have mutual inductance M=1 nH and
rate of current change dI/dt=109 A/s. Find the inductive
crosstalk voltage.
Solution:
Inductive crosstalk voltage formula:
V = M(dI/dt)
= (1 x 10-9) x 109 = 1 V
Final Answer: Inductive crosstalk voltage = 1 V.
Q: A clock tree is designed using an H-tree structure for 16
sinks, where each level halves the distance. If the initial
segment length is 10 mm, find the total wire length.
Solution:
For an H-tree, total wire length is given by:
Ltotal = 2 × ( L0 + L1 + L2 + ... + Ln−1)
For 16 sinks ( n = 4 levels ):
Ltotal = 2 × (10 + 5 + 2.5 + 1.25)
= 2 × 18.75 = 37.5 mm
Final Answer: Total wire length = 37.5 mm.
Q: A chip dissipates 10 W and has a thermal resistance of 5
∘C/W. If the ambient temperature is 30 ∘C, find the junction
temperature.
Solution:
IJunction temperature formula:
Tj = Ta + P x Rθ
= 30 + (10 x 5)
= 30 + 50 = 80∘C
Final Answer: Junction temperature = 80∘C
Q: A clock tree has three paths with delays of 2.5 ns, 3.1 ns,
and 3.8 ns. Find the worst-case clock skew.
Solution:
Clock skew is given by:
Skew = max delay − min delay
= 3.8 − 2.5 = 1.3 ns
Final Answer: Worst-case clock skew = 1.3 ns.
Q: A wire has an RC delay of 6 ns. If the width is doubled,
resistance is halved, and capacitance increases by 20%. Find
the new delay.
Solution:
Clock skew is given by:
RCnew= (R/2) × (1.2C) = 0.6RC
= 0.6 × 6 = 3.6 ns
Final Answer: New RC delay = 3.6 ns.
Q: If a signal passes through three buffer stages with
resistances of 200 Ω, 100 Ω, and 50 Ω, find the total effective
resistance.
Solution:
Since buffers are in series:
Rtotal = 200 + 100 + 50 = 350Ω
Final Answer: 350 Ω.
Q: A global interconnect of 2 mm is routed in metal-5 with
resistance 0.10.10.1 Ω/μm and capacitance 0.20.20.2 fF/μm.
Find the wire delay using the RC delay formula.
Solution:
Clock skew is given by:
τ = 0.69RCL2
=0.69 × (0.1×10−3) × (0.2×10−15) × (2000×10−6)2
= 0.69 × 10−4 × 0.2 × 4 × 10−6
= 5.52 ps
Final Answer: 5.52 ps.
INTERVIEW GUIDE
If you are preparing for a Physical Design (PD) interview, here’s a
structured guide covering technical preparation, common
questions, tips, and strategies to perform well.
UNDERSTANDING THE INTERVIEW PROCESS
Most PD interviews have three main stages:
Technical Screening – Covers basics of PD flow, STA, timing,
and concepts.
Problem-Solving & Coding – Includes Verilog/SystemVerilog,
scripting (TCL, Perl, Python), and algorithms.
Project & Practical Questions – Discuss previous projects,
challenges faced, and optimizations done.
TECHNICAL TOPICS TO PREPARE
Physical Design Flow Timing Analysis (STA)
ASIC Flow: From RTL to Setup & Hold Violations
GDSII Clock Tree Synthesis
PD Steps: Floorplanning, Delay Calculations
Placement, CTS, Routing, (Elmore Delay)
DRC/LVS OCV, AOCV, POCV
Standard Cells: Libraries, Clock Skew, Jitter,
LEF/DEF files Latency
Graph Theory in PD Power, IR Drop & Thermal
Minimum Spanning Tree Analysis
Dijkstra’s Algorithm for Dynamic & Static Power
Shortest Path Power Grid Design
Steiner Tree Problem EM & IR Drop Issues
Graph Coloring for
Routing Congestion Scripting & Automation
Max Flow in Routing TCL/Python for
automation in PD tools
DFT & Sign-Off Checks Perl scripting for log file
Scan Chain Insertion parsing
DRC/LVS Basics Shell scripting for
Antenna Violations automation
TIPS TO CRACK A PD INTERVIEW
1. Master the Basics – Revise PD flow, STA, DRC/LVS rules, and
scripting.
2. Practice Graph Algorithms – MST, Dijkstra, Steiner Tree, Graph
Coloring.
3. Learn Tool-Specific Concepts – Synopsys ICC, Cadence
Innovus, etc.
4. Prepare Your Projects Well – Discuss your PD project in detail
with optimizations.
5. Work on Scripting – Automate PD tasks with TCL, Perl, or
Python.
Excellence in World class
VLSI Training & Placements
Do follow for updates & enquires
+91- 9182280927
