회로의 연결 관계가 정해졌다면 설계가 거의 끝난 것일까요? 아직 중요한 질문이 남아 있습니다. “그 게이트들을 실제 칩의 어디에 놓을 것인가?” 오늘 배우는 placement, 즉 배치는 바로 이 질문을 다룹니다.

교재가 제시하는 전통적인 목표는 배선 길이, 타이밍, 혼잡입니다. 게이트의 위치는 열 집중, 전력 소모, 전원 잡음 같은 문제에도 영향을 줍니다. 다만 오늘의 세 가지 대표 알고리즘과 계산 예제는 주로 배선 길이를 줄이는 배치에 초점을 맞춥니다. 이 강의를 모든 배치 목적을 한꺼번에 해결하는 방법으로 이해하면 안 됩니다.

오늘 공부할 방법은 세 가지입니다. Mincut placement는 연결을 적게 끊으면서 회로와 공간을 나눕니다. GORDIAN은 좌표를 변수로 삼아 이차 최적화를 수행하고, 셀들이 퍼지도록 제약을 추가합니다. TimberWolf는 셀을 교환하면서 배치를 개선하되, 교환 때문에 주변 셀을 밀어야 하는 비용까지 고려합니다. 교재에서 앞의 두 방법은 전역 배치에, TimberWolf는 전역 배치와 상세 배치 양쪽에 연결됩니다.

넷은 서로 연결되어야 하는 단자 또는 셀들의 집합입니다. 예를 들어 교재의 표 4.1에는 n₁={e,f}, n₂={a,e,i}가 있습니다. 첫 번째는 두 게이트를, 두 번째는 세 게이트를 함께 연결해야 한다는 뜻입니다.

여기서 질문입니다. 세 게이트를 연결하는 넷을 일반 그래프로 표현하려면 어떻게 해야 할까요?

이 절에서는 그 세 정점 사이에 모든 쌍의 간선을 만드는 clique 기반 모델을 사용합니다. 원래 하나의 다단자 연결을 여러 쌍의 연결로 바꾸는 것입니다. 그림 4.2에서 굵은 간선의 가중치는 1, 가는 간선의 가중치는 0.5입니다. 교재는 이 그래프 표현을 KL 분할 알고리즘에 연결하고, FM을 사용하려면 하이퍼그래프 표현도 사용할 수 있다고 설명합니다.

이제 회로를 좌우로 나눕니다. 양 끝이 서로 다른 파티션에 들어가는 간선들은 경계를 가로지릅니다. 그 가중치를 합한 것이 이 그래프에서의 cutsize, 절단 비용입니다. 단순히 선이 몇 개 보이는지 세면 안 됩니다. 가중치가 0.5인 선 두 개와 가중치가 1인 선 하나는 같은 비용을 냅니다.

그런데 절단 비용이 3이라고 해서 실제 배선 길이도 3일까요? 아닙니다. 절단 비용은 양 끝이 서로 다른 편인지에 반응합니다. 반면 물리적 배선 길이는 좌표 차이에 반응합니다. 경계만 넘은 가까운 연결과 칩의 먼 쪽까지 가는 연결을 구별해야 하죠.

교재가 배치 결과를 평가할 때 사용하는 중요한 척도가 HPWL입니다. Half-perimeter wirelength, 넷의 바운딩 박스 반둘레입니다. 넷에 속한 위치들을 전부 포함하는 가장 작은 축 정렬 사각형을 생각하면 됩니다.

뒤의 예제에서는 각 넷의 값을 구해서 전체 비용으로 합합니다. 실제 배선을 상세하게 그려 얻은 길이가 아니라, 바운딩 박스로 평가한 비용이라는 점도 구별해 두세요. 교재의 mincut 예제와 TimberWolf 예제가 이 방식으로 길이를 계산합니다.

첫 번째 발상은 이렇습니다. “강하게 연결된 게이트를 같은 구역에 넣고, 그 안에서 같은 일을 반복하자.” 이것이 재귀적 분할을 이용한 mincut placement입니다.

중요한 것은 두 가지를 함께 나눈다는 점입니다. 회로를 두 부분으로 나누고, 그 회로가 들어갈 배치 영역도 가로 또는 세로로 나눕니다. 분할을 반복해 한 구역에 게이트 하나만 남으면 겹치지 않는 배치를 얻을 수 있습니다. 더 큰 작은 회로 단위에서 멈췄다면, 각 구역 안의 게이트에 고유한 위치를 주는 legalization이 추가로 필요합니다.

교재 예제에는 a부터 p까지 16개 게이트가 있고, 최종 목적지는 4×4 격자입니다. Area skew는 0입니다. 따라서 매번 완전히 균형 잡힌 이분할을 원합니다. 여기서 “연결을 적게 끊기 위해 15개를 왼쪽, 1개를 오른쪽에 두자”는 선택은 허용되지 않습니다. 절단 비용 최소화에는 면적 균형 조건이 붙어 있습니다.

Quadrature는 세로와 가로 절단을 조합해 네 영역을 만들고 이를 재귀적으로 세분화합니다. 교재의 첫 세로 절단에서는 왼쪽에 {a,b,e,f,i,j,m,n}, 오른쪽에 {c,d,g,h,k,l,o,p}가 들어갑니다. 절단 비용은 3입니다.

두 번째 가로 절단 뒤 왼쪽 위는 {b,f,j,n}, 왼쪽 아래는 {a,e,i,m}입니다. 오른쪽 위는 {c,g,k,o}, 오른쪽 아래는 {d,h,l,p}입니다. 이제 첫 번째 수준의 네 사분면이 만들어졌습니다. 세 번째 절단은 왼쪽 영역을 세로로 더 나눕니다. 위에서는 {j,n}과 {b,f}, 아래에서는 {i,m}과 {a,e}가 갈립니다. 네 번째 절단은 오른쪽 영역을 세로로 나누어 위쪽의 {c,g}, {k,o}, 아래쪽의 {d,l}, {h,p}를 구분합니다. 마지막 두 가로 절단은 위쪽과 아래쪽의 두 셀 묶음을 각각 한 셀씩 분리합니다.

그림 4.3(f)의 최종 격자를 위에서 아래로 읽으면 다음과 같습니다.

n  b  c  o
j  f  g  k
m  e  l  p
i  a  d  h

교재는 이 배치의 n₁부터 n₁₃까지 HPWL을 순서대로 1, 2, 2, 2, 2, 3, 1, 3, 3, 1, 1, 2, 4로 계산합니다. 합은 27입니다. 특히 n₁₃={k,n,o}는 가로로 넓게 벌어져 있어 비용이 4가 됩니다.

그런데 구역 안에서만 절단을 잘하면, 다른 구역의 이웃과의 거리도 좋아질까요? 빠진 외부 정보를 되살리는 장치가 terminal propagation입니다.

오른쪽 구역의 게이트 x를 위와 아래 중 어디에 둘지 결정한다고 합시다. x는 왼쪽 위 구역의 게이트 y와 연결되어 있습니다. 그런데 오른쪽 내부 연결만 보고 분할하면 어떤 정보가 사라질까요? “x에게는 왼쪽 위에 이웃이 있다”는 정보입니다.

그런데 외부 이웃을 전부 반영하면 될까요? 교재는 그렇지 않다고 봅니다. 내부 연결과 외부 연결의 영향 사이에 균형이 필요하기 때문입니다. 그래서 cutline과 평행한 두 선으로 window를 만듭니다. 이 예제는 가운데 3분의 1에 해당하는 mid-third window를 사용합니다. 외부 이웃이 그 안에 있으면 전파하지 않고, 밖에 있으면 경계의 고정 단자로 전파합니다.

절단 순서도 중요합니다. 교재는 breadth-first recursive bipartitioning을 사용합니다. 처음에는 모든 게이트를 전체 영역의 중심에 있다고 봅니다. 세로로 나눈 뒤에는 각 절반의 중심에 있다고 보고, 왼쪽을 가로로 나눈 다음 오른쪽을 가로로 나눕니다. 이처럼 같은 깊이의 구역들을 차례로 처리하면서 위치 정보가 더 구체화됩니다. 그 위치가 이후 외부 단자 판단에 사용됩니다.

같은 16개 게이트와 4×4 격자, 같은 균형 조건을 사용하겠습니다. 달라지는 것은 분할 순서와 외부 단자 처리입니다.

나머지 여덟 번의 절단은 각 두 셀 묶음을 한 셀씩 나누는 단계입니다. 교재는 이 단계의 세부 단자 전파를 생략합니다. 총 15번의 이분할 뒤 그림 4.10(d)는 다음 배치가 됩니다.

m  n  o  p
i  j  k  h
e  f  g  l
a  b  c  d

각 넷의 HPWL은 n₁부터 순서대로 1, 2, 2, 2, 2, 2, 1, 2, 3, 1, 1, 2, 2입니다. 합은 23입니다. 앞의 27과 비교하면 n₆가 3에서 2로, n₈이 3에서 2로, n₁₃이 4에서 2로 줄었습니다. 다른 넷은 교재의 두 결과에서 같습니다. 외부 연결의 위치 정보를 살린 효과를 구체적인 넷 단위로 볼 수 있습니다.

Mincut에서는 “어느 구역에 넣을까?”를 물었습니다. GORDIAN은 질문을 바꿉니다. “연결 길이를 수식으로 적고, 가장 좋은 좌표를 직접 구하면 어떨까?”

GORDIAN은 회로의 연결 정보에서 이차 목적함수를 만들고 quadratic programming, QP를 풉니다. 목표는 셀 사이의 제곱 배선 길이를 줄이는 것입니다.

하지만 여기에는 함정이 있습니다. 셀을 서로 가깝게 만드는 요구만 있다면 어떻게 될까요? 한곳에 모일수록 유리해집니다. 교재는 경계에 고정된 일부 IO 셀이 필요하며, 그렇지 않으면 모든 셀을 한 위치에 놓는 결과가 나온다고 설명합니다. 고정 IO는 움직이지 않는 연결 기준점이 됩니다.

고정 IO가 있다고 문제가 끝나는 것도 아닙니다. 셀들은 여전히 일부 지역에 몰리고 겹칠 수 있습니다. GORDIAN은 이를 다루기 위해 최적화와 top-down partitioning을 번갈아 수행합니다. 좌표를 구한 뒤 셀들을 파티션으로 묶고, 각 묶음의 면적 가중 무게중심이 해당 영역의 중심과 일치하도록 제약을 겁니다.

수준 l=0에서는 무게중심 제약 없이 QP를 풉니다. l=1에서는 영역을 둘로 나눈 뒤 제약을 추가합니다. l=2에서는 앞 절단에 수직인 절단을 넣어 영역을 더 나눕니다. 이런 과정을 영역이 충분히 작아질 때까지 반복합니다.

또한 무게중심을 맞췄다고 셀의 겹침이 자동으로 없어지지는 않습니다. 교재는 GORDIAN 종료 뒤에도 겹침이 남을 수 있고, DOMINO 같은 후처리로 이를 제거한다고 설명합니다. 평균 위치 제약과 비중첩 조건은 서로 다른 요구입니다.

행렬의 각 숫자에 “어느 연결에서 왔니?”라고 물어보겠습니다. 예제의 이동 가능한 셀은 a부터 j까지 10개입니다. IO는 w₁부터 w₄, z₁부터 z₄까지 8개이고, 위치가 고정됩니다. 셀 면적과 넷 가중치는 모두 1, 핀은 셀 중심에 있다고 가정합니다.

크기 k인 넷은 k-clique가 되고 각 간선은 2/k의 가중치를 받습니다. 따라서 2단자 넷은 1, 3단자 넷은 2/3, 4단자 넷은 1/2입니다. 같은 셀 쌍이 여러 넷에서 연결되면 그 기여를 더합니다. 그림에 7/6 같은 값이 나오는 것도 이런 합산으로 이해할 수 있습니다.

한 가지 검산 요령도 수식에서 바로 나옵니다. C의 한 행을 더하면 이동 셀 연결은 상쇄되고 고정 IO 연결 가중치의 합이 남습니다. 따라서 이 C를 보며 “라플라시안이니 모든 행 합이 반드시 0일 것”이라고 판단하면 안 됩니다. 고정 노드가 별도로 처리된 시스템이라는 점을 보아야 합니다.

이제 고정 IO의 위치를 넣겠습니다. 그림 4.12의 IO 좌표는 w₁=(0,1), w₂=(0,2), w₃=(0,3), w₄=(1,4), z₁=(2,0), z₂=(3,0), z₃=(4,1), z₄=(4,2)입니다. 이 순서를 P의 열 순서와 일치시켜야 합니다.

연결이 존재해도 해당 좌표가 0이면 그 방향의 벡터 기여는 0일 수 있다는 점에 주의하세요.

셀 순서 a~j
dx = (-1,  0, -2/3, -2/3, -1,    -1, 0,  -3, -4, -4)
dy = (-2, -13/6, -25/6, -25/6, -4/3, 0, 0, 0, -1, -2)

이 음수 부호가 낯설다면 한 연결의 제곱 항을 펼쳐 보세요. (xᵢ − x_p)²를 전개하면 −2xᵢx_p라는 교차항이 나옵니다. 고정된 x_p와 연결 가중치가 이동 변수 xᵢ의 선형항에 들어가는 구조입니다. 이것은 원문의 d 정의를 이해하기 위한 대수적 전개입니다.

셀   a     b     c     d     e     f     g     h     i     j
x   0.95  0.92  1.21  1.32  1.32  1.61  1.98  2.13  2.59  2.51
y   1.27  1.83  2.48  2.61  1.16  1.45  1.84  0.92  1.41  2.03

교재는 QP solver인 MOSEK으로 이 결과를 얻었다고 설명합니다. 연결을 줄이는 좌표는 얻었지만, 전체 4×4 영역을 고르게 사용하는 배치는 아닙니다. 분할과 무게중심 제약이 필요한 이유입니다.

이제 수준 0에서 얻은 좌표를 다음 단계의 정보로 사용합니다. 첫 분할은 세로 방향이고 면적 균형 인자 α는 0.5입니다. 셀 면적이 같으므로 x좌표 순서로 정렬한 뒤 다섯 개씩 나누면 됩니다.

교재의 정렬 순서는 {b,a,c,e,d,f,g,h,j,i}입니다. 따라서 왼쪽에는 {a,b,c,d,e}, 오른쪽에는 {f,g,h,i,j}가 들어갑니다. 표에 반올림된 d와 e의 x값은 둘 다 1.32로 보이지만, 원문은 e를 먼저 둡니다. 이 예제에서는 둘 다 같은 왼쪽 그룹에 들어가므로 결과적인 소속에는 차이가 없습니다.

전체 영역이 4×4이고 좌우를 반씩 나누므로 중심은 왼쪽 (1,2), 오른쪽 (3,2)입니다. 이를 벡터로 적으면 u_x⁽¹⁾=(1,3)ᵀ, u_y⁽¹⁾=(2,2)ᵀ입니다. 각 그룹의 평균 좌표를 계산하는 행렬이 A⁽¹⁾입니다.

          a    b    c    d    e    f    g    h    i    j
A(1) = [ 1/5  1/5  1/5  1/5  1/5   0    0    0    0    0  ]
       [  0    0    0    0    0   1/5  1/5  1/5  1/5  1/5 ]

첫 행에 x를 곱하면 a부터 e까지의 x좌표 평균이 나옵니다. 둘째 행은 나머지 다섯 셀의 평균입니다. 따라서 A⁽¹⁾x = u_x⁽¹⁾는 두 집단의 평균 x좌표를 각각 1과 3으로 맞추라는 뜻입니다. y도 같은 방식으로 두 집단의 평균을 2로 맞춥니다.

목적함수 C와 d는 그대로 두고, 이 선형 등식 제약을 붙여 LQP를 풉니다. 결과는 다음과 같습니다.

셀   a     b     c     d     e     f     g     h     i     j
x   0.70  0.71  1.17  1.21  1.22  2.17  3.10  2.84  3.56  3.33
y   1.34  1.94  2.66  2.76  1.30  1.83  2.45  1.32  1.91  2.49

아닙니다. 평균만 1이어야 합니다. 반올림된 값을 더하면 5.01이므로 평균은 1.002, 즉 약 1.00입니다. y좌표 합은 10.00이므로 평균은 2.00입니다. 교재의 중심 (1,2)와 일치한다는 검산은 출력 좌표의 반올림을 고려해 읽으면 됩니다. 개별 셀 대신 집단의 평균을 고정하므로, 각 셀에는 연결을 개선할 자유가 남습니다.

이번에는 좌우 각각의 다섯 셀을 위아래로 나눕니다. 다섯 개를 같은 개수의 두 집단으로 나눌 수 있을까요? 불가능합니다. 그래서 가능한 한 균형에 가깝게 두 셀과 세 셀로 나눕니다.

수준 1의 y좌표를 기준으로 왼쪽 위는 {c,d}, 왼쪽 아래는 {a,b,e}가 됩니다. 오른쪽 위는 {g,j}, 오른쪽 아래는 {f,h,i}입니다. 교재는 이 네 파티션을 순서대로 p₁,p₂,p₃,p₄라고 부릅니다.

그림에서 가로 절단이 정확히 높이의 절반을 지나지 않는다는 점을 보세요. 위쪽에는 두 셀, 아래쪽에는 세 셀이 배정되어 있습니다. 교재가 제시한 중심은 위쪽 y=3.2, 아래쪽 y=1.2입니다. 이 좌표를 영역의 기하와 연결하면 절단선은 y=2.4이고, 위쪽 높이는 1.6, 아래쪽 높이는 2.4입니다. 즉 2:3의 구성을 영역에도 반영한 것입니다.

A를 외우는 대신 각 행이 무엇을 평균 내는지 쓰겠습니다.

p1 행: c와 d의 열에 각각 1/2
p2 행: a, b, e의 열에 각각 1/3
p3 행: g와 j의 열에 각각 1/2
p4 행: f, h, i의 열에 각각 1/3
그 밖의 원소는 모두 0

이 네 행을 모은 것이 원문의 A⁽²⁾입니다. 예를 들어 (x_c+x_d)/2 = 1, (y_c+y_d)/2 = 3.2가 p₁의 제약입니다. p₂에는 (x_a+x_b+x_e)/3 = 1, (y_a+y_b+y_e)/3 = 1.2가 적용됩니다. 다시 동일한 전역 목적함수에 A⁽²⁾x = u_x⁽²⁾와 A⁽²⁾y = u_y⁽²⁾를 적용해 풉니다.

셀   a     b     c     d     e     f     g     h     i     j
x   0.83  0.78  1.00  1.00  1.39  2.28  2.89  3.06  3.66  3.11
y   1.01  1.78  3.08  3.32  0.82  1.44  3.18  0.59  1.57  3.22

c와 d의 평균은 정확히 (1, 3.2)입니다. g와 j의 평균도 (3, 3.2)입니다. 아래쪽 그룹도 출력의 반올림 오차 안에서 목표 중심에 맞습니다. 그림 4.18에는 이 좌표 위에 clique 연결을 다시 표시해, 공간적으로 나뉜 뒤에도 전체 연결이 유지됨을 보여 줍니다.

이번에는 놓인 셀을 교환하면서 배치를 개선합니다. 교재가 다루는 TimberWolf는 simulated annealing 기반의 배치·배선 도구입니다. 여기서 설명하는 버전과 성능 평가는 교재에 소개된 당시 연구를 기준으로 합니다.

두 번째 개선이 이 절의 중심인 overlap-free placement입니다. 교재 설명에 따르면 이전 버전은 겹침을 허용하면서 벌점으로 줄이고, 끝까지 남은 겹침은 마지막에 셀을 밀어 제거했습니다. 그런데 이 후처리가 앞서 얻은 배치의 품질을 떨어뜨릴 수 있습니다. 그래서 7.0에서는 annealing 중에도 겹침 없는 배치를 유지하면서 셀 이동을 효율적으로 처리하려고 합니다.

좁은 셀이 있던 자리에 넓은 셀이 들어오면 무엇이 생길까요? 옆 셀과 겹칩니다. 반대로 넓은 셀의 자리에 좁은 셀이 들어가면 빈틈이 생깁니다. 따라서 두 셀의 좌표만 맞바꾸고 끝낼 수 없습니다.

교재는 더 넓은 셀을 받는 행에서 주변 셀을 밀어 겹침을 없앱니다. 방향은 이동시켜야 하는 셀의 수가 적은 쪽을 고릅니다. 좁은 셀을 받은 행의 빈틈은 즉시 없애려고 하지 않습니다. 이후 교환에서 채워질 수 있기 때문입니다. 또 행 길이의 차이가 작게 유지되도록 교환을 선택해 전체 빈틈을 줄이려 합니다.

다음 절의 Model A와 Model B는 바로 이 shifting 비용을 빠르게 평가하기 위한 모델입니다. 교환 비용 계산 전체를 대충 대신하는 모델이 아니라, 비용식의 특정 항을 추정한다는 점을 기억하세요.

한 셀 z를 수평으로 민다고 합시다. 연결된 넷의 HPWL은 어떻게 달라질까요? 넷의 나머지 셀들이 만드는 가로 범위 안에서 움직이는 동안에는 바운딩 박스의 폭이 바뀌지 않을 수 있습니다. 하지만 그 범위를 벗어나면 z가 새로운 경계가 되어 폭이 늘어납니다.

Model A는 이 구조를 두 breakpoint, a와 b로 표현합니다. [a,b] 안에서는 해당 넷의 길이가 일정합니다. 왼쪽 구간에서는 오른쪽으로 움직일 때 길이가 줄고, 오른쪽 구간에서는 오른쪽으로 움직일 때 길이가 늘어납니다. 여러 넷의 구간별 함수를 합쳐 z의 이동 비용을 평가합니다.

Model B는 전체 꺾은선을 다루는 대신 현재 위치에서의 기울기를 사용합니다. 교재의 규칙은 넷 i에서 z가 왼쪽 경계면 D_i(0) = −1, 오른쪽 경계면 +1, 어느 쪽도 아니면 0입니다. 연결된 모든 넷에 대해 더하면 셀의 gradient가 됩니다.

두 번째 예를 보세요. 왼쪽 이동이라고 비용이 줄어드는 것이 아닙니다. 바운딩 박스를 왼쪽으로 더 넓혔으므로 길이가 증가합니다.

왜 추정이라고 부를까요? 지금의 기울기를 전체 이동 구간에 적용하기 때문입니다. 이동 중 breakpoint를 지나 경계 역할이 바뀌면 현재의 기울기만으로는 변화 전체를 표현하지 못할 수 있습니다. 교재는 인용 연구에서 Model B가 Model A와 비슷한 정확도를 내면서 더 빨랐다고 소개합니다. 이를 모든 입력과 모든 이동에서 두 값이 반드시 같다는 명제로 확대하면 안 됩니다.

n1={a,e,g}      n2={f,o}          n3={b,c,k,n}
n4={d,h,i}      n5={j,l,m}        n6={d,k,j}
n7={c,e,f,h,n}  n8={d,l}          n9={b,g,i,m}
n10={a,k,o}

초기 HPWL은 n₁부터 순서대로 19, 14, 19, 19, 11, 21, 28, 12, 19, 23입니다. 예를 들어 n₄는 가로 5와 세로 14를 더해 19가 됩니다. n₇은 가로 14, 세로 14여서 28입니다.

첫 교환은 (b,e)입니다. 더 넓은 b가 위쪽 행으로 들어가므로 그 옆의 h를 오른쪽으로 1만큼 밀어야 합니다. 반대편으로 여러 셀을 미는 것보다 h 하나를 미는 쪽을 택합니다. 아래쪽에는 좁은 e가 들어가므로 작은 빈틈이 남습니다.

셀이 움직였다고 연결된 모든 넷의 길이가 반드시 달라지는 것은 아닙니다. n₇처럼 바운딩 박스가 유지되는 넷도 있습니다.

이제 h의 shifting을 계산합니다. h는 n₄={d,h,i}와 n₇={c,e,f,h,n}에 속합니다. 그림 4.20에서 h는 n₄의 오른쪽 경계이므로 +1, n₇에서는 어느 가로 경계도 아니므로 0입니다. 따라서 gradient(h) = 1입니다. 이동량은 오른쪽 1이므로 ΔW_S = 1×1 = 1, 전체 변화는 ΔC = 19 + 1 = 20입니다.

교재는 실제 값도 확인합니다. h를 밀면 n₄는 19에서 20으로 증가하고, n₇은 28을 유지합니다. 실제 증가량 역시 1입니다. Model A로 보아도 같습니다. n₄의 breakpoint는 i와 d, n₇의 breakpoint는 f와 n입니다. 그림 4.21에서 h의 작은 오른쪽 이동은 n₄의 증가 구간에 있고 n₇의 평평한 구간 안에 있습니다.

앞의 교환이 끝난 배치에서 이어갑니다. 최초 그림으로 돌아가면 이후 넷 길이가 맞지 않습니다.

먼저 (m,o)입니다. 넓은 m이 들어가는 자리를 확보하기 위해 d와 g를 오른쪽으로 각각 2만큼 밉니다.

교재의 교환 항:
n5: 11 → 12, +1     n9: 26 → 22, -4
n2: 14 →  7, -7     n10: 23 → 23,  0
→ 교재의 ΔW = -10

d의 gradient는 n₄에서 0, n₆에서 +1, n₈에서 +1이므로 2입니다. g는 n₁과 n₉ 모두의 오른쪽 경계여서 gradient가 2입니다. 두 셀을 오른쪽으로 2씩 미므로 ΔW_S = 2×2 + 2×2 = 8입니다. 원문은 이를 합해 ΔC = −10 + 8 = −2를 제시합니다.

다음 교환은 (k,m)입니다. 이번에는 중간 행에 더 넓은 k가 들어갑니다. 왼쪽의 빈틈을 활용하면서 c를 왼쪽으로 1만큼 이동시킵니다. 그림에서는 o까지 실제로 움직일 필요는 없습니다. 짧은 쪽에 있는 모든 셀을 무조건 같은 거리만큼 미는 것이 아니라, 겹침을 없애는 데 필요한 이동을 해야 합니다.

교재는 k와 m의 연결 넷에 대해 n₃의 변화 +1, n₆의 변화 −7, n₁₀의 변화 −10, n₅의 변화 +9, n₉의 변화 0을 제시하여 ΔW = −7로 계산합니다. c는 n₃의 왼쪽 경계이고 n₇의 가로 경계는 아니므로 gradient(c) = −1입니다. 이동량도 −1이므로 ΔW_S = (−1)×(−1) = +1, 원문의 최종 값은 ΔC = −6입니다.

(m,o)에서 g를 아직 밀지 않으면 n₉의 좌표는 b(8,14), g(12,7), i(6,0), m(7,7)입니다. 따라서 길이는 (12−6) + (14−0) = 20입니다. g를 오른쪽으로 2 민 뒤에야 22가 됩니다. 원문은 ΔW 계산에 이미 22를 사용하고, ΔW_S에서 g에 의한 증가 2를 다시 포함합니다. 순수 교환과 이동을 분리하면 ΔW = −12, ΔW_S = 8이고 합은 −4입니다.

(k,m)에서도 c를 아직 밀지 않으면 n₃의 x범위는 4~14, y범위는 0~14이므로 길이는 24입니다. c를 왼쪽으로 1 밀었을 때 25가 됩니다. 원문의 교환 항에는 이미 그 증가 1이 들어 있고, shifting 항에서 또 1을 더합니다. 그림을 기준으로 두 단계를 분리한 검산값은 ΔW = −8, ΔW_S = 1, 합은 −7입니다. 이 검산은 그림 4.22와 4.25에 그려진 배치를 기준으로 합니다.

이제 풀이가 없는 추가 문제를 보겠습니다. 여기서 확인할 것은 숫자를 기억했는지가 아니라, 입력이 바뀌었을 때 모델과 계산 순서를 다시 구성할 수 있는지입니다.

「Probing Further」는 포괄적 문헌 조사가 아니라 대표 연구의 소개입니다. 당시 소개된 연구들이 어떤 약점을 보완하는지 연결하겠습니다.

먼저 mincut 계열입니다. 가장 자연스러운 질문은 “둘로 나누는 것, cutsize를 최소화하는 것, 정해진 절단 순서를 쓰는 것이 각각 꼭 최선인가?”입니다.

다음은 GORDIAN과 분석적 배치 계열입니다. 질문은 “제곱 길이가 우리가 궁극적으로 원하는 선형 길이와 얼마나 잘 맞는가? 셀을 어떻게 퍼뜨려야 연결 관계를 덜 망가뜨리는가?”입니다.

표현은 달라도 “가깝게 연결하면서 겹치지 않게 퍼뜨리기”라는 긴장은 동일합니다.

마지막은 TimberWolf의 확장입니다. 신호 방향의 cone을 묶어 soft macro로 배치한 뒤 행 기반 표준 셀 배치로 바꾸는 연구가 소개됩니다. 타이밍 확장에서는 지연식을 annealing 비용에 넣고, 개선할 critical path 집합을 반복해서 갱신합니다. 병렬화 연구들은 작업 분배와 통신, 병렬 이동, 여러 Markov chain 등을 다룹니다. 교재는 소개된 비교에서 speculative computation이 효과적이지 않았다는 결과도 함께 전합니다. MGP는 증분 전역 배선으로 혼잡 비용을 갱신하고 계층적 밀도를 제어하며, 최상위 클러스터의 배치에 TimberWolf를 사용합니다.

이제 첫 질문으로 돌아가겠습니다. 게이트를 어디에 놓을 것인가? 우리는 세 가지 답을 배웠습니다. 연결을 적게 끊도록 공간을 나누고, 밖의 이웃은 단자로 반영합니다. 연결을 이차식으로 만들고, 집단의 무게중심을 제약해 공간에 퍼뜨립니다. 이미 놓인 셀을 교환하되, 주변 셀을 밀어 자리를 만드는 비용까지 계산합니다.