Chapter 05

플로어플랜과 배치

합성이 끝나면 손에 남는 것은 “어떤 셀이 몇 개 있고 무엇이 무엇과 연결되는가”를 적은 넷리스트뿐이다. 그 안에는 위치가 없다. 이제 수십만~수십억 개의 표준 셀을 칩 위 어디에 놓을지 정해야 한다. 먼저 칩의 크기와 뼈대, 즉 다이·코어·전원망·매크로 자리를 잡는 것이 플로어플랜(Floorplan)이고, 그 틀 안의 행(row)에 셀을 하나씩 앉히는 것이 배치(Placement)다. 서로 연결된 셀을 가까이 둘수록 배선이 짧아지고, 짧은 배선은 빠르고 전력을 덜 쓰며 배선하기도 쉽다. 이 장에서는 그 “가까이”를 수식으로 정의하고, 실제 배치 알고리즘을 돌려 엉킨 넷이 풀리는 모습을 본다.

P&R 도구의 입력(넷리스트·LEF·테크 LEF·SDC)과 출력(DEF)이 각각 무엇을 담는지 안다.
셀 면적·이용률·종횡비에서 코어·다이 크기와 행 수를 계산하고, 코어 제한과 패드 제한을 구분한다.
표준 셀 행이 뒤집혀 전원 레일을 공유하는 구조와 사이트 격자를 설명한다.
HPWL·스타이너 트리·클리크·스타 모델로 배선 길이를 추정한다.
이차(힘 기반) 전역 배치와 시뮬레이티드 어닐링을 돌려 보고 차이를 비교한다.
합법화(Tetris·Abacus)와 상세 배치, 타이밍·혼잡 인지 배치, 필러·탭·엔드캡 셀의 역할을 안다.

P&R 도구가 받는 것과 내놓는 것

배치와 배선(Place and Route, P&R) 도구는 논리 세계와 물리 세계를 잇는다. 논리 쪽에서는 합성 결과인 넷리스트(Netlist, 보통 게이트 수준 Verilog)와 타이밍 제약 SDC(Synopsys Design Constraints)를 받는다. 물리 쪽에서는 셀 하나하나의 “겉모습”만 요약한 LEF(Library Exchange Format)를 받는다. P&R 도구는 셀 안쪽의 트랜지스터 레이아웃(4장)을 알 필요가 없다. 셀의 크기, 핀의 위치와 층, 그리고 배선이 지나가면 안 되는 차단 영역만 알면 된다.

그림 05-1. P&R의 입력과 출력. 셀 LEF는 셀의 겉모습만, 테크 LEF는 금속층과 설계 규칙을 담는다. 결과인 DEF(Design Exchange Format)에는 각 셀의 좌표·방향과 배선 경로가 적히고, 마지막에 셀의 실제 레이아웃(GDS)과 합쳐져 마스크 데이터가 된다(12장).

파일	담는 내용	예시 줄
넷리스트 (.v)	셀 인스턴스와 넷 연결. 위치 없음	`NAND2_X1 u12 (.A(n3), .B(n7), .ZN(n9));`
셀 LEF	셀 크기(사이트 배수), 대칭, 핀 도형과 층, 차단(OBS)	`SIZE 0.76 BY 1.26 ; PIN A ... LAYER M1`
테크 LEF	층 순서·선호 방향·피치·최소 폭/간격, 비아 정의, 사이트	`LAYER M2 DIRECTION HORIZONTAL ; PITCH 0.14`
SDC	클럭 주기, 입출력 지연, 예외 경로	`create_clock -period 1.0 [get_ports clk]`
Liberty (.lib)	셀 지연·전력 표(8장)	`cell_rise (table) { ... }`
DEF (출력)	다이 영역, 행, 셀 좌표·방향, 배선 경로, 비아	`- u12 NAND2_X1 + PLACED ( 3800 12600 ) FS ;`

플로어플랜: 칩의 뼈대 정하기

플로어플랜은 배치 전에 정하는 큰 틀이다. 칩 전체 크기인 다이(Die), 그 안에서 표준 셀이 놓이는 코어(Core), 바깥 둘레의 IO 패드나 플립칩 범프, SRAM·PLL·아날로그 블록 같은 큰 매크로(Macro)의 자리, 그리고 전원을 실어 나르는 전원망이 여기서 정해진다. 한번 정하면 바꾸기 어렵다. 매크로를 잘못 두면 그 주변에 배선이 몰려 몇 주 뒤 배선 단계에서야 문제가 드러난다.

그림 05-2. 플로어플랜의 구성. 코어를 전원 링이 감싸고, 상위 금속의 수직 스트랩이 링에서 전원을 받아 코어 안으로 나르며, 각 행의 M1 레일이 스트랩과 비아로 연결되어 셀에 전원을 준다. 매크로는 보통 코어 가장자리에 두어 표준 셀 영역을 쪼개지 않게 하고, 둘레에 헤일로를 두어 핀 접근 배선의 자리를 남긴다.

가장 먼저 정하는 수치는 이용률(Utilization)이다. 코어에서 셀이 실제로 덮는 면적의 비율로, 보통 60~80%에서 시작한다. 100%로 꽉 채우면 면적은 최소지만 버퍼를 넣을 자리도, 배선이 지나갈 여유도 없다. 이용률과 종횡비(Aspect ratio, 높이/폭)를 정하면 코어 크기가 나온다.

$$A_{\text{core}} = \frac{A_{\text{cell}}}{U} + A_{\text{macro}}(1+\eta_{\text{halo}}), \qquad H_{\text{core}} = \sqrt{A_{\text{core}}\cdot AR}, \quad W_{\text{core}} = \frac{A_{\text{core}}}{H_{\text{core}}}$$

$A_{\text{cell}}$은 표준 셀 면적 합, $U$는 목표 이용률, $AR$은 종횡비. 코어 높이는 셀 높이(EDU45 1.26 µm)의 정수배, 폭은 사이트 폭(0.19 µm)의 정수배로 올림한다. 행 수 $N_{\text{row}} = H_{\text{core}}/1.26\,\mu\text{m}$.

다이 크기는 코어만으로 정해지지 않는다. 와이어 본딩 칩은 둘레에 IO 패드를 일정 간격(수십 µm)으로 늘어놓아야 하므로, 신호가 많은 작은 칩은 패드를 다 두르려고 다이를 키워야 한다. 이것을 패드 제한(Pad-limited) 설계라 하고, 반대로 셀 면적이 크기를 정하면 코어 제한(Core-limited)이다. 플립칩은 다이 전면에 범프를 깔아 이 제약을 크게 푼다. 범프·패키지 공정은 ProcessBook 13장의 첨단 패키징 이야기와 이어진다.

SIMULATOR

플로어플랜 계산기: 게이트 수 → 코어 → 다이

게이트 수 (NAND2 환산) SRAM 매크로 면적 합 목표 이용률 U 종횡비 H/W 신호 IO 개수

패키지

표준 셀 면적 합—

코어 W × H—

행 수 × 행당 사이트—

다이 크기—

제한 요인—

실효 이용률—

해볼 것: ① 게이트 수를 2만 개(10^1.3k)쯤으로 줄이고 IO를 200개로 두면 코어는 0.2 mm 남짓인데 패드를 두르느라 다이가 몇 mm가 된다. 패드 제한이다. 실효 이용률이 몇 %로 떨어지는 것을 보라. ② 패키지를 플립칩으로 바꾸면 같은 IO로도 다이가 줄어든다. ③ 이용률을 0.9 이상으로 올리면 면적은 줄지만 배선 혼잡이 급격히 커진다(7장). (가정: NAND2 환산 게이트 1개 = 4 사이트 × 1.26 µm = 0.958 µm², 매크로 헤일로 10%, 전원 링 20 µm, 와이어 본딩 IO 패드 높이 120 µm·피치 60 µm, 플립칩 범프 피치 150 µm·신호 1개당 범프 2개(전원 포함), IO 셀 높이 60 µm. 교육용 근사.)

전원망: 링, 스트랩, 레일

전원망(Power delivery network, PDN)은 배치 전에 깐다. 둘레의 링이 패드나 범프에서 전류를 받고, 굵은 상위 금속의 스트랩이 격자 모양으로 코어를 가로지르며, 표준 셀 행마다 M1 레일이 셀의 VDD·VSS 핀에 닿는다. 전류가 이 그물을 지나며 저항 때문에 전압이 떨어지는 IR 드롭과, 큰 전류 밀도에서 생기는 전자 이동은 9장과 ProcessBook 11장에서 다룬다. 스트랩은 배선 트랙을 차지하므로, 전원망을 촘촘히 깔수록 IR 드롭은 줄지만 신호 배선 자원이 준다. 최신 공정에서는 전원망을 웨이퍼 뒷면으로 옮기는 후면 전력 공급(BSPDN, ProcessBook 13장)이 이 맞바꿈을 깬다.

표준 셀 행과 사이트

코어 안은 높이가 같은 행(Row)으로 나뉜다. 모든 표준 셀의 높이가 같기 때문에(EDU45: 9 트랙 = 1260 nm) 가능한 구조다. 행 안은 다시 사이트(Site)라는 최소 폭 단위로 나뉘고, 셀의 폭은 언제나 사이트의 정수배다. EDU45에서 사이트 폭은 게이트 피치 CPP와 같은 190 nm라, 셀의 폴리 게이트가 칩 전체에서 한 격자 위에 정렬된다. 리소그래피가 규칙적인 격자를 좋아하는 이유는 ProcessBook 4장에 있다.

그림 05-3. 표준 셀 행. 한 행 걸러 셀을 위아래로 뒤집어(FS, flipped-south) 놓으면, 인접한 두 행이 VDD 또는 VSS 레일 하나를 함께 쓰고 N웰도 이어진다(분홍=N웰, 파랑 기운=P 영역). 레일 수가 절반이 되고 웰 간격 규칙도 저절로 지켜진다. 점선은 사이트 경계로, 모든 셀의 왼쪽 끝은 사이트 경계에 맞춰야 한다. 셀 내부 구조는 4장.

DEF에 적히는 셀의 방향은 여덟 가지(N, S, E, W와 각각의 거울상 FN, FS, FE, FW)지만, 행에 들어가는 표준 셀은 사실상 N(그대로)과 FS(위아래 뒤집기), 그리고 같은 행 안에서 좌우를 바꾸는 FN·S만 쓴다. 좌우 뒤집기는 핀 위치를 바꿔 배선을 짧게 하는 상세 배치 기법으로 쓰인다.

배선 길이를 어떻게 셀까

배치가 좋은지 나쁜지 판단하려면 아직 그려지지 않은 배선의 길이를 미리 추정해야 한다. 배치 알고리즘은 이 추정치를 수백만 번 계산하므로 빠르고 단순해야 한다. 가장 널리 쓰는 것이 반둘레 배선 길이(HPWL, Half-perimeter wirelength)다. 넷의 모든 핀을 감싸는 최소 직사각형의 가로와 세로를 더한 값이다.

$$\text{HPWL}(e) = \Big(\max_{i\in e} x_i - \min_{i\in e} x_i\Big) + \Big(\max_{i\in e} y_i - \min_{i\in e} y_i\Big), \qquad W = \sum_{e} w_e\,\text{HPWL}(e)$$

$w_e$는 넷 가중치(타이밍이 급한 넷일수록 크게). 배선은 수평·수직으로만 가므로 거리는 맨해튼 거리다.

실제 배선에 가장 가까운 것은 핀들을 수평·수직 선분만으로 잇는 최소 길이 트리, 즉 직교 스타이너 최소 트리(RSMT, Rectilinear Steiner minimal tree)다. 핀이 아닌 곳에 가지점(스타이너 점)을 만들 수 있다. 핀이 2~3개면 RSMT 길이는 HPWL과 정확히 같고, 핀이 많아질수록 HPWL보다 길어진다. RSMT를 구하는 문제는 NP-어렵기 때문에 배치 단계에서는 HPWL에 핀 수에 따른 보정 계수를 곱해 쓰고, 배선 단계에서야 FLUTE 같은 빠른 근사 알고리즘으로 트리를 만든다.

그림 05-4. 핀 4개인 한 넷의 네 가지 모델. HPWL(230)은 실제 스타이너 트리(260)의 하한이다. 클리크와 스타는 넷을 2핀 “스프링” 묶음으로 바꿔 이차 배치(아래 절)에 쓰인다. 핀이 k개면 클리크는 k(k−1)/2개의 스프링, 스타는 가상 노드 하나와 k개의 스프링이라 큰 넷에는 스타가 유리하다.

핀 수 k	2	3	4	5	6	8	10
RSMT / HPWL 평균 (무작위 핀)	1.00	1.00	~1.08	~1.15	~1.22	~1.34	~1.45
클리크 스프링 수	1	3	6	10	15	28	45

실제 칩에서 넷의 대부분(보통 60~70%)은 핀이 2~3개라 HPWL이 꽤 정확하다. 클럭이나 리셋처럼 핀이 수천 개인 넷은 배치 비용에서 빼고 따로 다룬다(클럭은 6장).

전역 배치: 넷을 스프링으로 생각하기

셀 수가 N이면 가능한 배치는 천문학적으로 많다. 그래서 배치는 두 단계로 나눈다. 먼저 겹침을 어느 정도 허용하며 셀의 대략 위치를 연속 좌표로 정하는 전역 배치(Global placement), 그다음 이를 행과 사이트에 겹침 없이 붙이는 합법화와 상세 배치다.

전역 배치의 고전적인 방법은 이차 배치(Quadratic placement)다. 넷을 클리크 모델로 2핀 연결로 바꾸고, 각 연결을 스프링으로 본다. 모든 스프링의 탄성 에너지(길이의 제곱 합)를 최소화하는 위치를 찾으면 된다.

$$\Phi(\mathbf{x},\mathbf{y}) = \sum_{(i,j)} w_{ij}\big[(x_i-x_j)^2 + (y_i-y_j)^2\big] \;\Rightarrow\; \frac{\partial \Phi}{\partial x_i}=0 \;\Rightarrow\; x_i = \frac{\sum_j w_{ij}\,x_j}{\sum_j w_{ij}}$$

$\Phi$는 x와 y가 분리된 볼록 이차식이라 $Q\mathbf{x}=\mathbf{b}_x$, $Q\mathbf{y}=\mathbf{b}_y$라는 희소 선형 방정식 두 개를 풀면 최적해가 나온다. $\mathbf{b}$에는 고정된 IO 핀이 들어간다. 오른쪽 식은 “각 셀을 이웃들의 가중 평균 위치로 옮긴다”는 뜻이고(힘이 0인 위치), 이를 되풀이하면 가우스–자이델 반복법이 된다. 힘 기반 배치(Force-directed)라는 이름이 여기서 나왔다.

문제는 이 최적해가 셀들을 한가운데에 와르르 모아 버린다는 것이다. 스프링은 셀끼리 끌어당기기만 하고 밀어내지 않기 때문이다. 고정 IO 핀이 셀들을 바깥으로 조금 당기지만 부족하다. 그래서 실제 도구는 셀이 몰린 곳에서 셀을 퍼뜨린 목표 위치를 만들고, 각 셀을 그 목표에 묶는 가상 스프링(앵커)을 점점 세게 하며 다시 푼다(SimPL·RePlAce 계열, 후자는 밀도를 전하 분포로 보고 정전기적 반발력을 쓴다). 반대로 시뮬레이티드 어닐링(Simulated annealing, SA)은 셀을 격자 칸에 두고 무작위로 맞바꾸며, 나빠지는 교환도 온도에 따른 확률로 받아들여 국소 최적을 탈출한다.

$$P_{\text{accept}} = \begin{cases}1 & \Delta W \le 0\\ e^{-\Delta W/T} & \Delta W > 0\end{cases}, \qquad T_{k+1} = \alpha\,T_k\;(0.8<\alpha<0.999)$$

$\Delta W$는 교환 전후 총 배선 길이 차. 온도 $T$가 높을 때는 거의 모든 교환을 받아 넓게 탐색하고, 식으면서 개선만 받아들이는 탐욕 탐색이 된다. 냉각이 느릴수록(α가 1에 가까울수록) 결과가 좋지만 오래 걸린다. 1980년대 TimberWolf가 대표적이다.

SIMULATOR

배치 알고리즘: 무작위 → 이차 배치 → 어닐링

셀 수

초기 온도 T₀ 냉각률 α

총 HPWL—

상태 · 반복—

밀도 초과 (겹침)—

어닐링 온도 · 수락률—

해볼 것: ① ①로 섞은 뒤 ②를 누르면 처음 20여 번 반복 동안 셀이 가운데로 몰리며 HPWL이 크게 준다(겹침 급증). 이후 퍼뜨리기 앵커가 세지며 셀이 펴지고 HPWL이 조금 다시 오른다. 겹침 없는 배치를 위한 대가다. ② 무작위 배치에서 바로 ③을 돌려 보고, ② 결과에서 ③을 이어 돌려 보라. 좋은 출발점에서는 낮은 T₀로도 충분하다. ③ 냉각률을 0.85로 낮추면 빨리 끝나지만 HPWL이 덜 줄고, 0.99면 느리지만 더 좋다. (영역 100 µm × 100 µm, 네모 = 셀, 삼각형 = 고정 IO 핀, 선 = 넷(다핀 넷은 중심으로 모은 별 모양). 넷리스트는 숨은 좋은 배치가 존재하도록 이웃끼리 연결해 만들었다. 이차 배치는 클리크 모델 가우스–자이델 반복 + 재귀 이분할 퍼뜨리기 앵커, 어닐링은 셀 칸 교환·이동과 온도에 비례해 줄어드는 이동 창.)

왜 HPWL을 바로 최소화하지 않을까

HPWL은 max/min이 들어 있어 미분이 안 되는 점이 많다. 이차식은 미분이 깔끔해 선형 방정식 하나로 풀리지만, 긴 넷을 제곱으로 과하게 벌한다. 최신 배치기(RePlAce, DREAMPlace)는 HPWL을 매끈하게 근사한 로그-합-지수(LSE)나 가중 평균(WA) 함수를 쓰고, 밀도 제약과 함께 경사 하강법으로 푼다. DREAMPlace는 이것이 신경망 학습과 같은 구조임을 이용해 GPU로 수백만 셀을 몇 분에 배치한다.

합법화와 상세 배치

전역 배치의 결과에는 아직 겹침이 남아 있고 좌표도 연속값이다. 합법화(Legalization)는 각 셀을 가장 가까운 행에, 사이트 경계에 맞춰, 겹치지 않게 붙이는 단계다. 목표는 전역 배치가 애써 찾은 상대 위치를 망치지 않는 것, 곧 변위(Displacement)를 최소로 하는 것이다.

Tetris (Hill, 2002): 셀을 x 좌표 순으로 정렬해 하나씩 꺼내, 각 행의 현재 오른쪽 끝 이후 자리 중 변위가 가장 작은 곳에 놓는다. 테트리스 블록처럼 왼쪽부터 쌓인다. 매우 빠르지만 앞서 놓인 셀은 다시 움직이지 않아 오른쪽으로 밀리는 셀이 생긴다.
Abacus (Spindler 외, 2008): 셀을 행에 넣을 때마다 그 행의 셀들을 클러스터로 묶어, 행 안 변위 제곱합이 최소가 되도록 클러스터 위치를 다시 계산한다. 이미 놓인 셀도 조금씩 양보하므로 변위가 고르게 나뉜다.

$$\min_{x_i} \sum_{i\in\text{row}} e_i\,(x_i - x_i^{\,0})^2 \;\;\text{s.t.}\;\; x_{i+1} \ge x_i + w_i \quad\Rightarrow\quad x_c = \frac{\sum_{i\in c} e_i\,(x_i^{\,0} - o_i)}{\sum_{i\in c} e_i}$$

$x_i^{\,0}$은 전역 배치 위치, $w_i$는 셀 폭, $e_i$는 가중치(보통 1 또는 셀 면적). 맞붙은 셀 묶음(클러스터) $c$의 최적 시작 위치 $x_c$는 각 셀의 원하는 위치에서 클러스터 안 오프셋 $o_i$를 뺀 값의 가중 평균이다. 이웃 클러스터와 겹치면 합쳐서 다시 계산한다.

SIMULATOR

합법화 비교: Tetris 대 Abacus

보기

행 이용률 전역 배치 뭉침 정도

합법화 전 겹침 면적—

Tetris 총 · 최대 변위—

Abacus 총 · 최대 변위—

Abacus 개선—

해볼 것: ① “전역 배치” 보기에서 겹친 셀(짙은 부분)을 보고, Tetris와 Abacus를 번갈아 보라. 점선 상자는 원래 위치, 선은 이동량이다. ② 이용률을 0.95까지 올리면 Tetris는 뒤에 오는 셀을 오른쪽 끝이나 먼 행으로 밀어내 최대 변위가 커지고, Abacus는 앞의 셀들이 함께 양보해 고르게 나눈다. ③ 뭉침을 0으로 하면 원래 겹침이 적어 둘 다 변위가 작다. (10행 × 48사이트, 셀 폭 2~8사이트, 변위 = |Δx|×0.19 µm + |Δy|×1.26 µm. 두 알고리즘 모두 셀을 x 순으로 처리하고 행 선택은 같은 변위 기준.)

합법화 뒤에는 상세 배치(Detailed placement)가 국소적으로 다듬는다. 이웃한 셀 두세 개의 순서를 모두 바꿔 보는 창 최적화, 같은 크기 셀끼리의 전역 교환, 행 안에서 셀을 좌우로 미는 최적 이동, 좌우 뒤집기로 핀을 넷 쪽으로 돌리기 같은 기법이 쓰인다. 배선 길이가 5~10% 더 준다.

타이밍, 혼잡, 그리고 특수 셀

배선 길이만 줄이는 배치는 실제 칩에서 실패한다. 두 가지를 더 봐야 한다.

타이밍 구동 배치(Timing-driven placement): 임계 경로 위의 넷은 조금만 길어져도 타이밍을 어긴다. 그래서 정적 타이밍 분석(8장)으로 슬랙을 구하고, 슬랙이 작은 넷의 가중치 $w_e$를 키워 다시 배치한다. 배치 중간중간 긴 넷에 버퍼를 넣고(버퍼링), 부하가 큰 셀을 큰 구동력 셀로 바꾸는(게이트 크기 조정) 최적화도 함께 돈다. 그래서 배치 후 셀 수는 합성 직후보다 5~15% 늘어나는 일이 흔하다.

$$w_e \leftarrow w_e\left(1 + \beta\left(1-\frac{\text{slack}_e}{T_{\text{clk}}}\right)^{\gamma}\right)$$

넷의 슬랙이 작을수록(임계에 가까울수록) 가중치가 커진다. $\beta,\gamma$는 도구가 정하는 조절값. 넷 가중치 방식은 단순하지만 반복할수록 다른 경로가 임계가 되는 진동이 생길 수 있다.

혼잡 인지 배치(Congestion-driven / routability-driven placement): 셀을 너무 촘촘히 모으면 배선 길이 합은 짧아도 한 영역에 배선 수요가 몰려 배선이 지나갈 트랙이 모자란다. 배치기는 배선 혼잡도를 빠르게 추정하고(7장의 혼잡도 지도), 혼잡한 곳의 셀에 가상 여백(셀 패딩)을 붙이거나 목표 밀도를 낮춰 셀을 퍼뜨린다. 배치 밀도와 배선 혼잡은 맞바꿈이다. 이용률 70%에서 잘 배선되던 블록이 85%에서는 배선이 끝나지 않는 일이 흔하다.

특수 셀	하는 일	넣는 시점
엔드캡 (Endcap, boundary cell)	행 양 끝에서 웰·확산·폴리 무늬를 마감해 가장자리 효과(OPC·응력)를 막는다	플로어플랜 직후, 배치 전
탭 셀 (Well tap)	N웰을 VDD, P기판을 VSS에 묶어 래치업을 막는다. 일정 간격(수십 µm)마다 체커보드로	배치 전 (고정)
디캡 (Decap)	VDD–VSS 사이 커패시터. 순간 전류에 의한 전압 강하를 완화(9장)	배치 후 빈 곳에
필러 (Filler)	남은 빈 사이트를 채워 웰·임플란트 층과 전원 레일을 끊김 없이 잇는다	배선 직전 또는 후, 마지막
스페어 셀 (Spare)	마스크 몇 장만 고쳐 버그를 수정(ECO)할 수 있게 미리 흩뿌린 여분 게이트	배치 단계

공정과 이어지는 배치 규칙

탭 셀 간격은 웰 저항과 래치업 내성에서 정해진다(ProcessBook 8장의 웰 주입). 엔드캡은 행 끝의 폴리·확산 무늬 밀도 변화가 노광·식각 결과를 바꾸는 근접 효과를 막는다(11장). 필러가 웰과 임플란트를 이어 주지 않으면 셀 사이 틈에 작은 웰 섬이 생겨 DRC 위반(10장)이 된다.

핵심 정리

P&R은 넷리스트·셀 LEF·테크 LEF·SDC를 받아 셀 위치와 배선을 담은 DEF를 낸다. 셀 LEF는 셀의 크기·핀·차단 영역만 담은 추상이다.
코어 면적 = 셀 면적 / 이용률 + 매크로. 행 수 = 코어 높이 / 1.26 µm. IO가 많은 작은 칩은 패드 제한이 된다.
표준 셀 행은 한 행 걸러 뒤집혀 VDD·VSS 레일을 공유한다. 셀 폭은 사이트(CPP 190 nm)의 정수배.
배선 길이는 HPWL로 추정한다. 2~3핀 넷에서는 스타이너 트리와 같고 핀이 많을수록 과소 추정한다.
이차 배치는 넷을 스프링으로 보고 선형 방정식을 풀며, 셀이 몰리는 것을 퍼뜨리기 앵커로 막는다. 어닐링은 확률적 교환으로 국소 최적을 탈출한다.
합법화(Tetris·Abacus)는 변위를 최소로 하며 셀을 행·사이트에 붙이고, 상세 배치가 국소적으로 다듬는다.
타이밍 구동(넷 가중치·버퍼링)과 혼잡 인지(셀 패딩·밀도 제한)가 함께 돌며, 배치 밀도와 배선 혼잡은 맞바꿈이다.

확인 퀴즈

표준 셀 면적 합이 0.49 mm², 목표 이용률이 0.7, 매크로가 없고 종횡비가 1이다. 코어 한 변의 길이와 EDU45의 행 수는 대략?

코어 면적 = 0.49 / 0.7 = 0.70 mm², 한 변 = √0.70 ≈ 0.837 mm. 행 수 = 837 µm / 1.26 µm ≈ 664행.

핀 좌표가 (0,0), (4,1), (2,5)인 3핀 넷의 HPWL은?

x 범위 0~4 → 4, y 범위 0~5 → 5, 합 9. 3핀 넷이므로 직교 스타이너 최소 트리 길이도 정확히 9다.

순수한 이차 배치(앵커 없이 스프링 에너지만 최소화)의 대표적인 문제는?

스프링은 당기기만 하므로 겹침을 막는 힘이 없다. 그래서 밀도를 퍼뜨리는 앵커나 정전기적 반발력(RePlAce)을 더한다. 고정 핀이나 양의 앵커가 모든 자유 성분을 구속하여 축소 행렬이 양의 정부호일 때 해가 하나이며, 볼록성만으로 유일하지는 않다. 고정 핀과 단절된 성분은 함께 평행 이동해도 에너지가 같을 수 있다. 긴 넷은 오히려 제곱으로 과하게 벌한다.

인접한 두 표준 셀 행 중 하나를 위아래로 뒤집어(FS) 놓는 주된 이유는?

뒤집으면 맞닿는 쪽이 같은 전원(VDD끼리 또는 VSS끼리)이 되어 레일 하나를 함께 쓰고, N웰도 이어져 웰 간격 규칙 문제가 사라진다.

Abacus 합법화가 Tetris보다 대체로 변위가 작은 이유는?

Tetris는 이미 놓인 셀을 움직이지 않는다. Abacus는 클러스터의 최적 위치(가중 평균)를 다시 계산하므로 기존 셀이 조금씩 양보한다. 두 방법 모두 합법화에 성공한 결과는 겹침이 없다. 높은 이용률에서 Tetris는 배치 실패·겹침을 남길 수 있으므로 실패 수를 먼저 확인하고, 모두 성공한 결과끼리 변위를 비교한다.