Layout (GORDIAN)

Standard cell array - gridline for cells
Sea-of-gate - there is not gridline for the cells


GORDIAN
- global optimization, rectangular disection and final placement
- it's an improvement over approach that combines min-cut bisection with divide-and-conquer


Global optimization
- minimizing distance^2 instead of distance, it decouples x from y

Partitioning
- brute force enumeration
- FM
- repartition (after global opt.)

Final Placement

- For standard cell




shape function

LQP: for x w.l.o.g.,

Minimize "spring distance", squared distances

min: L = sum(xu + c - xn)^2)
constraints: Xc = sum(wu * xu)

LQP ==> UQP

- pick xd in terms of xi

- sub xd's in L ==> Lt

- min Lt by solving Lt' = 0, which is a (Ax = b) problem, use G.E.

Complexity:

- space: O(m)

- time: (O(GO) + O(RD)) * levels of slicing tree ==> (m^3 + m^2lg(m)) * lg(m)