VLSI-CAD

A basic implementation of analytical gate placer

Placer Types: Randomized vs Analytical

Randomized type uses Simulated Annealing. In this implementation, we are considering an analytical placer.

Wire estimation models

Two popular models are: a) Half Perimeter Wire Length (HPWL) b) Quadratic model

Iterative quadratic placer

• Based on quadratic wire length estimation
• Model multi-point net using Clique
• Cost function = L = Σ(w_ij Δ𝑥_𝑖𝑗 )^2+(𝑤_𝑖𝑗 Δ𝑦_𝑖𝑗 )^2
• L = Lmin when derivatives = 0
• Solve system of linear equations -> Get 𝑥_𝑖, 𝑦_𝑖
• Recursive partitioning to resolve gate clustering :Assign, Contain, Solve, repeat …

Code

Graph class

• Parses the netlist file into graph representation (adjacent list).
• Stores the gates, pads, their connectivity and calculated weights

Region class

• Stores physical dimensions of region.
• Stores pointer array to gates

Functions

• build matrix (system of linear equations): 𝐴𝑋=𝑏_𝑥 , 𝐴𝑌=𝑏_𝑦
• solve and updated gate locations
• cut Vertical, cut Horizontal
• Sorting-based assignment of gates
• Containment of connected pads/gates in region.

Solver class

Conjugate gradient iterative solver [A] is sparse matrix (sparse matrix representation)

Build

g++ -o main main.cpp solver.cpp 

Flowchart