§ 1문제 정의
wire-length = Σ (셀 중심 간 맨해튼 거리 × pinCount). 짧을수록 좋다. path delay = Σ (거리 / pinCount) — 짧지만 굵은 net은 좋고, 길고 가는 net은 나쁘다.
두 목표가 충돌하기 쉬운 이유: wire를 줄이려고 셀을 빽빽이 모으면 timing path가 동선이 길어진다 (path는 셀 간 여러 hop을 거치므로). 보통 시뮬레이티드 어닐링(SA) 또는 force-directed 배치 후 swap 미세조정.
실용적 시작: 네트가 많은 ‘허브 셀’을 중심에 두고, 그 주변에 net으로 연결된 셀을 거리 비례로 배치한다. 그 후 random swap으로 cost를 점진적으로 낮춘다.
두 목표 사이의 줄다리기. 한쪽을 끝까지 당기면 반대편이 무너진다.
§ 2예제 시각화 — 9 셀, 4 net
FIG. 13 — placement → swap → routing
STEP 01 / 5
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
process(cells, paths):
# 1. 초기 배치 (force-directed 또는 균등 격자)
grid_place(cells)
# 2. 어닐링 swap
T = T0
while T > T_min:
for it in range(K):
i, j = random pair
d_cost = swap_delta(i, j)
if d_cost < 0 or rand() < exp(-d_cost/T):
swap(i, j)
T *= 0.95
# 3. 검증 + deploy
for c in cells: deploy(c.index, c)