TL;DR

• placement는 “셀 좌표 찍기”가 아니라, router가 살아남을 수 있게 만드는 단계다.
• placer의 본질은 wirelength를 어떻게 근사하고(cost function), 그걸 어떻게 줄이느냐다.
• 대표적인 세 가지 접근:
  1. Greedy / Random swap: 이해용, 로컬 미니멈에 쉽게 갇힘
  2. Simulated Annealing(SA): 나쁜 이동도 확률적으로 허용 → 전역 탐색 가능
  3. Analytical(Quadratic) placement: 문제를 선형방정식 (Ax=b)로 바꿔 크게 푼다
• 현대 상용 flow는 보통
  Global placement → Legalization → Detailed placement 구조다.

ASIC Placement: Router가 울지 않게 만드는 첫 단계

placement는 흔히 “layout 초반 단계”로 불린다.
실제로는 뒤에 올 모든 고통을 미리 결정하는 단계다.

placement가 잘못되면:

• wire가 길어진다
• congestion이 터진다
• routing 실패 or timing ECO 지옥이 열린다

그래서 placement는 이렇게 이해하는 게 정확하다.

placement는 “최적화의 시작”이 아니라
후반 설계가 가능해질지 말지를 결정하는 관문이다.

1. 우리가 배치하는 대상: standard cell

ASIC/SOC 설계의 기본 단위는 standard cell이다.

• NAND, NOR, INV, FF 같은 논리 블록
• 내부 트랜지스터 구조는 숨기고, 외부에는 사각형 + 핀만 노출
• 모든 cell은 높이는 동일, 폭은 서로 다름

이 추상화 덕분에 placer는 “전자회로”가 아니라 기하 문제로 설계를 다룰 수 있다.

2. 왜 wirelength를 “추정”할 수밖에 없나

placer의 진짜 목표는 잘 라우팅되는 배치다.
문제는 placer 내부에서 router를 매번 돌릴 수 없다는 점이다. 너무 비싸다.

그래서 현실의 placer는 이렇게 목표를 바꾼다.

estimated wirelength다.

3. HPWL: 가장 유명한 wirelength estimator

멀티핀 net은 실제 routing 경로가 무수히 많다.
그래서 가장 단순하고 강력한 근사가 HPWL (Half-Perimeter WireLength) 이다.

각 net의 모든 핀 좌표를 ((x_k, y_k))라 하면,

[HPWL = (\max x - \min x) + (\max y - \min y)]

HPWL의 성질:

• 계산이 매우 쉽다
• 멀티핀 net에도 바로 적용 가능
• 실제 routing wirelength의 lower bound로 동작한다

실제 디자인을 보면:

• 대부분의 net은 짧다
• 소수의 긴 net이 timing / congestion의 주범이다

4. 가장 단순한 placer: 랜덤 배치 + greedy swap

개념 이해용으로 가장 직관적인 방식이다.

1. 모든 cell을 랜덤 위치에 배치
2. 임의의 두 cell을 선택해 swap
3. HPWL 변화량 (\Delta L) 계산
4. (\Delta L < 0)이면 accept, 아니면 undo

while improvement exists:
  pick random Gi, Gj
  swap(Gi, Gj)
  ΔL = new_HPWL - old_HPWL
  if ΔL < 0:
    keep
  else:
    undo

중요한 구현 포인트:

• 매번 전체 HPWL을 다시 계산하면 망한다
• swap된 cell과 연결된 net만 다시 계산해야 한다 (incremental update)

5. Greedy의 한계: local minimum

이 방식은 항상 좋아지는 방향만 이동한다.
그래서 어느 순간 “그럴듯한 배치”에 도달하면, 그게 전역 최적이 아니어도 더 이상 움직이지 않는다.

즉, local minimum에 갇힌다.

6. Simulated Annealing: 일부러 나빠져서 탈출한다

이를 해결하기 위해 등장한 것이 Simulated Annealing(SA) 이다.

핵심 아이디어:

• 나빠지는 이동도 확률적으로 허용
• 초반에는 자유롭게, 후반에는 점점 보수적으로

Metropolis criterion

swap으로 인해 (\Delta L > 0)일 때,

[P(\text{accept}) = \exp(-\Delta L / T)]

• (T)가 클수록: 나쁜 이동도 잘 허용 (탐색)
• (T)가 작아질수록: greedy에 가까워짐 (수렴)

SA는 실제로 HPWL을 잘 줄인다.
다만 대규모 디자인에서는 속도가 병목이 된다.

7. 현대 placement의 주력: Analytical (Quadratic) placement

대형 디자인에서 SA 대신 쓰이는 방식이 analytical placement다.

아이디어는 단순하다.

wirelength를 quadratic 형태로 바꾸면
placement가 선형방정식 문제로 바뀐다.

7.1 Quadratic wirelength model

2-pin net의 경우:

[WL_{quad} = (x_1 - x_2)^2 + (y_1 - y_2)^2]

멀티핀 net은 clique model로 분해한다:

• 모든 핀 pair를 연결
• 과도한 영향 방지를 위해 보통 (1/(k-1)) 같은 weight 보정 적용

7.2 왜 (Ax=b) 형태가 나오나

quadratic cost function을 각 좌표에 대해 미분하면:

[A x = b_x,\quad A y = b_y]

• (A): net 연결로부터 만들어진 sparse matrix
• (b): fixed pad / IO pin 위치가 만들어내는 항

이 선형 시스템을 풀면, 모든 cell의 좌표가 한 번에 나온다.

직관적으로는 이렇다.

각 net은 spring처럼 동작한다.
quadratic placement는 “모든 spring 에너지의 합을 최소화”한다.

8. 문제점: QP는 overlap을 무시한다

quadratic placement는 cell을 point로 취급한다.
그래서 결과는 그럴듯하지만:

• cell이 서로 겹치고
• row 정렬도 무시된다

이걸 그대로 쓰면 불법이다.

9. 해결책: Recursive partitioning + legalization

일반적인 해결 흐름은 다음과 같다.

1. Global placement
   • QP로 전체적인 형태를 잡는다
2. Recursive partitioning
   • 영역을 분할하고
   • cell을 좌표 기준으로 나누어 밀어 넣는다
   • 경계에는 pseudo-pad를 둬서 외부 영향을 유지한다
3. Legalization
   • overlap 제거
   • standard cell row에 정확히 맞춘다
4. Detailed placement
   • local swap / reorder로 HPWL, timing, congestion 미세 개선