STEINER ROUTING — 짧게 연결하는 문제에서 빠르게 전달하는 문제까지
짧게 연결하는 문제에서
빠르게 전달하는 문제까지
단자들을 잇는 가장 좋은 배선 트리는 무엇일까요? 케이블을 가장 적게 쓰는 트리, 가장 먼 싱크가 가까운 트리, 모든 싱크가 각자 최단 경로를 갖는 트리, 실제 신호 지연이 작은 트리 — 비슷하게 들리지만 전부 다른 문제입니다. 이 노트는 그 네 개의 목적이 어떻게 서로 다른 알고리즘을 만들어내는지 따라갑니다.
큰 그림: 우리가 최적화하려는 것은 정확히 무엇인가?WHAT ARE WE MINIMIZING
여러 도시를 통신선으로 연결한다고 생각해 봅시다. 가장 좋은 연결망은 케이블을 가장 적게 쓰는 것일까요, 본사에서 가장 먼 지사까지 빨리 도착하는 것일까요, 아니면 모든 지사에 신호가 실제로 가장 빠르게 도착하는 것일까요?
이 장의 주제는 Steiner routing입니다. 주어진 단자들을 연결하되, 필요하면 새로운 분기점을 도입하는 배선 트리 구성입니다. 원래 단자 집합을 P, 추가하는 점들의 집합을 S라고 하면 기본 문제는 P와 S를 함께 연결하는 최소 신장 트리의 길이가 작아지도록 S를 찾는 것입니다. 수평·수직 배선만 쓰는 버전이 rectilinear Steiner tree, 줄여서 RST입니다.
질문이 “주어진 점을 어떻게 연결할까?”에서 “연결에 유리한 점을 어디에 새로 만들까?”로 확장됩니다. 새로운 도시가 아니라, 여러 케이블이 만나는 중간 분기점을 만드는 셈입니다.
설치한 선의 총량을 줄입니다.
소스에서 각 싱크까지 트리를 따라 이동한 거리 중 최댓값을 제한합니다.
모든 싱크에 대해 개별 소스–싱크 경로를 최단으로 만듭니다.
저항과 정전용량을 반영한 지연을 직접 줄입니다.
칠판에 이렇게 적겠습니다. “총길이 → 최장 경로 → 모든 개별 경로 → 실제 지연 모델.” 뒤로 갈수록 앞의 목표를 버리는 것이 아닙니다. 무엇을 직접 최적화하고 무엇을 제약이나 간접 지표로 쓸지가 바뀝니다.
L-RST는 기존 MST의 간선을 L자로 꺾어 겹침을 늘립니다. 1-Steiner는 새로운 점을 하나씩 넣으면서 트리를 개선합니다. BPRIM과 BRBC는 배선 길이와 radius를 절충합니다. A-tree는 모든 싱크의 최단 경로를 유지하면서 공유 배선을 찾습니다. ERT와 SERT는 후보 연결을 실제로 붙여 본 뒤 Elmore 지연으로 평가합니다.
알고리즘마다 세 가지를 물어보세요. “무엇을 바꿀 수 있는가?”, “좋고 나쁨은 무엇으로 판단하는가?”, “어떤 조건이 있어야 이 선택을 정당화할 수 있는가?” 같은 트리를 다루더라도 이 세 질문의 답이 다르면 전혀 다른 알고리즘입니다.
핵심 O/X 퀴즈
1. Steiner routing에서는 원래 단자 이외의 점을 연결망에 추가할 수 있다.
2. 총배선 길이를 최소화하면 모든 싱크의 실제 신호 지연도 반드시 최소가 된다.
3. 이 장의 알고리즘들은 연결 구조뿐 아니라 목적함수와 제약조건에서도 차이가 난다.
L-RST의 출발점: 왜 아무 MST나 가져오면 안 될까?SEPARABLE MST
가장 익숙한 도구인 MST에서 출발합니다. 다만 거리부터 확인해야 합니다. 여기서 두 점 i, j 사이의 거리는 맨해튼 거리입니다.
그림에 대각선이 그려져 있어도 그 선분의 유클리드 길이를 비용으로 읽으면 안 됩니다. 대각선은 두 단자를 연결한다는 관계를 표현할 뿐이고, 실제 직교 배선 길이는 맨해튼 거리로 계산합니다.
왜 MST에서 출발할까요? 원문은 rectilinear MST의 길이가 최적 RST 길이의 3/2보다 크지 않다는 성질과, Prim이나 Kruskal로 효율적으로 구성할 수 있다는 점을 동기로 제시합니다. 좋은 출발점을 빠르게 얻은 다음 개선하자는 전략입니다.
두 점을 연결하는 최단 직교 경로에는 위쪽으로 꺾는 upper-L과 아래쪽으로 꺾는 lower-L이 있습니다. 개별 간선의 길이는 같습니다. 그런데 여러 간선을 함께 보면 차이가 생깁니다. 어떤 방향으로 꺾느냐에 따라 배선 일부를 공유할 수 있기 때문입니다.
도로 두 개를 따로 놓으면 길이가 각각 필요하지만, 일부 구간을 같은 도로로 사용하면 실제 건설량은 줄어듭니다. L-RST가 최대로 만들려는 것이 이 공유량, 즉 overlap입니다.
간선이 m개이면 방향 선택은 2m가지입니다. 모든 조합을 확인할 수는 없으니, 먼저 separable MST를 만듭니다. 핵심 성질은 서로 인접하지 않는 간선들의 L자 배선이 겹치지 않는다는 것입니다. 멀리 떨어진 선택끼리 영향을 주지 않도록 출발 트리를 정리하는 셈입니다.
이때 간선 가중치는 숫자 하나가 아니라 다음 세 값의 사전식 순서입니다.
먼저 짧은 간선을 선택합니다. 길이가 같으면 수직 차이가 큰 간선, 그것도 같으면 더 오른쪽에 있는 간선을 선호합니다. 뒤의 두 기준은 길이 최소화라는 첫 번째 목표를 바꾸는 것이 아니라, 같은 비용의 선택을 구조적으로 정리합니다.
| 간선 | 가중치 | 판정 |
|---|---|---|
| (b, d) | (4, −3, −4) | 두 번째 값이 가장 작아 먼저 선택 |
| (b, f) | (4, −1, −7) | 더 오른쪽이지만 두 번째 기준에서 밀림 |
| (b, a) | (4, −1, −4) | 길이는 같으나 순위 최하 |
“더 오른쪽인 f가 먼저 아닌가요?”라는 질문에는, 사전식 비교에서 두 번째 기준을 먼저 확인한다고 답하면 됩니다. 예제의 선택 순서는 (b,d), (d,c), (c,a), (b,f), (f,g), (g,h), (f,e), (e,i)이고 초기 총길이는 32입니다. 이제 이 구조를 고정하고 L자 방향을 결정합니다.
핵심 O/X 퀴즈
1. L-RST에서 upper-L과 lower-L의 개별 길이가 같아도 전체 배선 길이는 달라질 수 있다.
2. 세 값으로 된 가중치는 길이보다 오른쪽 위치를 우선한다.
3. Separability는 멀리 떨어진 간선 선택 사이의 겹침 의존성을 없애는 데 중요하다.
L-RST의 핵심: 부모 간선의 방향만 기억하는 트리 DPTWO CONDITIONAL STATES
b를 루트로 잡았다고 합시다. 어떤 노드 v의 아래쪽 배선을 모두 결정하려는데, 위쪽 상황은 얼마나 알아야 할까요? 전체 조상의 방향을 다 기억해야 한다면 DP가 커집니다. 하지만 이 문제에서는 부모와 연결되는 간선의 방향 하나가 핵심 경계 조건이 됩니다.
- Tv
- v를 루트로 하는 서브트리.
- ev
- v와 부모를 잇는 간선.
- Tv+
- 부모 간선까지 포함한 구조.
- Φl(v)
- ev를 lower-L로 고정했을 때의 최적 배선.
- Φu(v)
- ev를 upper-L로 고정했을 때의 최적 배선.
두 상태는 “v에서 지금 더 좋은 쪽 하나”가 아닙니다. 부모가 나중에 어떤 방향을 요구하더라도 답할 수 있도록 두 조건부 최적해를 모두 저장하는 것입니다.
식당에서 메뉴를 하나만 준비하는 것이 아니라, 손님이 두 종류의 식단 중 무엇을 주문해도 대응하도록 미리 둘 다 준비해 두는 셈입니다.
겹침량을 Z라고 하면 계산은 두 조각으로 나뉩니다. 하나는 v에 직접 붙은 간선들 사이에서 발생하는 겹침 Z1, 다른 하나는 자식 서브트리 내부에서 이미 계산한 겹침 Z2입니다. p.141 그림 5.1이 이 두 겹침의 위치를 구분해 보여 줍니다.
자식이 w1부터 wd까지 있다고 합시다. 부모 간선을 lower-L로 고정하고 자식 간선의 방향을 모두 시험한 뒤, 각 조합에 대해 다음 값을 계산합니다.
그중 최댓값이 lower 상태의 답입니다. 부모 간선을 upper-L로 고정해 같은 계산을 하면 upper 상태도 얻습니다. 값뿐 아니라 그 값을 만든 자식 방향 조합도 저장해야 합니다. 나중에 실제 배선을 복원해야 하니까요.
“자식 상태 중 큰 것만 독립적으로 고르면 되지 않나요?” 안 됩니다. 어떤 자식 방향은 서브트리 내부에서는 유리하지만 v 주변의 겹침에는 불리할 수 있습니다. Z1과 자식들의 값을 함께 평가해야 합니다.
겹침을 단순히 모든 간선 쌍의 교집합 길이 합으로 이해하지 마세요. 여러 선이 같은 구간을 공유할 때 우리가 원하는 것은 실제 배선량이 얼마나 줄었는지입니다. 회계 장부에서 같은 절감액을 여러 번 더하면 안 되는 것과 같습니다.
원문은 separability와 상수로 제한되는 차수를 이용해 초기 트리가 주어진 뒤의 L자 치환 단계를 선형 시간에 처리한다고 설명합니다. MST 구성 비용까지 전부 선형이라는 뜻은 아닙니다.
핵심 O/X 퀴즈
1. Φl(v)는 v의 부모 간선을 lower-L로 고정한 조건부 최적해이다.
2. 각 자식에서 겹침이 큰 상태만 독립적으로 선택하면 항상 정답이다.
3. 최적 배선을 출력하려면 DP 값과 함께 그 값을 만든 방향 선택도 기억해야 한다.
L-RST 예제: 32가 어떻게 28이 되는가?pp.145–150
추상적인 DP를 숫자로 확인하겠습니다. 아래쪽 노드들의 상태값부터 모읍니다.
| 노드 | lower 상태 | upper 상태 | 이유 |
|---|---|---|---|
| c | 1 | 0 | (c,d)를 lower로 고정하면 (c,a)도 lower로 만들어 길이 1을 공유 |
| e | 0 | 1 | 부모 간선이 upper일 때 자식 쪽에서 길이 1의 겹침 |
| g | 0 | 1 | e와 같은 형태 |
| d | 1 | 1 | d 주변에는 겹침이 없지만 아래 c의 좋은 상태를 가져옴 |
현재 노드에서 이득이 없어도, 아래에서 가져오는 이득은 남습니다. d가 바로 그 경우입니다.
이제 자식이 둘인 f를 보겠습니다. 자식은 e와 g입니다. 부모 간선 (f,b)의 방향을 고정하고 자식 방향 조합을 네 가지로 시험합니다.
| (f,b) 고정 | l–l | l–u | u–l | u–u | 최적 |
|---|---|---|---|---|---|
| lower | 1 | 1 | 2 | 2 | 2 · (e=u, g=l) |
| upper | 1 | 2 | 1 | 2 | 2 · (e=l, g=u) |
두 상태의 값은 똑같이 2입니다. 그렇다고 합쳐도 될까요? 아닙니다. 동일한 DP 값이 동일한 복원 정보를 뜻하지는 않습니다. lower 상태는 e를 upper·g를 lower로, upper 상태는 e를 lower·g를 upper로 선택합니다.
마지막으로 루트 b에는 d와 f가 달려 있습니다. 두 간선의 방향을 네 가지로 시험하면 총겹침은 3, 3, 3, 4입니다. 둘 다 upper-L일 때만 b 주변에서 추가 겹침 1을 얻어 최종값이 4가 됩니다.
p.150 그림 5.11은 최초 트리와 최종 배선을 나란히 보여 주고, 그림 5.12는 일부 연결을 다른 계단형 경로로 바꾸어도 추가 겹침이 생기지 않는다는 재배선 안정성을 보여 줍니다.
“안정적”과 “가능한 모든 Steiner tree 중 전역 최적”은 구분해야 합니다. 여기서 최적으로 푼 것은 주어진 separable MST의 L자 방향 선택입니다. 새 분기점을 자유롭게 추가하며 구조까지 다시 탐색하는 문제는 다음 알고리즘의 영역입니다.
핵심 O/X 퀴즈
1. 예제의 최종 배선 길이는 초기 길이 32에서 겹침 4를 빼서 얻는다.
2. 두 DP 상태의 최적값이 같으면 복원할 자식 방향도 반드시 같다.
3. 주어진 MST에 대한 최적 L자 치환을 얻었다고 해서 모든 RST 중 전역 최적임이 바로 따라오지는 않는다.
Naive 1-Steiner: 점 하나를 넣고 MST를 다시 만들자KAHNG–ROBINS
질문을 바꿔 봅시다. “현재 간선들을 어떻게 꺾을까?”가 아니라 “점을 하나 새로 넣으면 더 짧은 MST를 만들 수 있을까?”입니다. 단자 집합 P에 점 s를 추가했을 때 MST(P∪{s})가 MST(P)보다 짧아지면, 그 s가 개선에 기여하는 1-Steiner point입니다.
이름의 1은 최종 트리에 분기점을 하나만 허용한다는 뜻이 아닙니다. 한 번의 개선에서 하나씩 추가한다는 뜻입니다. 개선이 가능하면 이 작업을 반복합니다.
원문이 소개하는 복잡도는 naive 방법 O(n5), 더 정교한 방법 O(n3)입니다. 다만 이 책은 정교한 방법의 내부 알고리즘을 다루지 않고 naive 방법만 예제로 설명합니다. 여기서 배우는 핵심은 복잡한 기하 자료구조가 아니라 후보 삽입과 MST 재구성을 반복하는 탐색 구조입니다.
| 단계 | 길이 | 상황 |
|---|---|---|
| 초기 | 20 | 첫 삽입 후보는 16곳, 그중 6곳에서 길이가 줄어듦 |
| 1점 추가 | 18 | 가장 좋은 두 선택이 모두 18. 예제는 그림 5.15(c)를 채택 |
| 2점 추가 | 17 | 길이 17인 후보가 세 개 — 여기가 갈림길 |
| 3점 추가 | 16 | 그림 5.16(c)에서 출발했을 때만 도달 |
여기서 잠깐 멈춰 보세요. “어차피 모두 17이면 아무거나 골라도 최종 결과는 같겠지?” 그림 5.16(a), (b)에서는 더 이상 점 하나를 추가해 개선할 수 없습니다. 그런데 (c)를 고르면 세 번째 점을 추가해 16까지 내려갑니다.
이 예제의 주인공은 숫자 16이 아니라 동률 선택의 후속 효과입니다. 게임에서 현재 점수가 같은 두 위치가 이후에 같은 승률을 갖지는 않는 것과 비슷합니다.
“점 하나 추가로 더 좋아지지 않는다”는 종료 조건은 여러 점을 함께 바꾸는 더 큰 탐색에서도 최적이라는 증거가 아닙니다. L-RST에서는 탐색 공간이 L자 방향들이었고, 여기서는 한 점 추가 뒤의 MST 재구성이 탐색 단위입니다. 무엇에 대한 최적인지 계속 구분해야 합니다.
핵심 O/X 퀴즈
1. 1-Steiner 알고리즘은 최종적으로 Steiner point를 정확히 하나만 가진다.
2. 원문 예제에서는 현재 길이가 같은 트리라도 이후 추가 개선 가능성이 달라진다.
3. Naive 방법은 각 후보를 추가한 뒤 MST를 다시 계산해 후보를 평가한다.
간선 기반 1-Steiner: 새 연결을 넣고 사이클에서 비싼 간선을 빼자BORAH–OWENS–IRWIN
매번 모든 후보에서 MST를 다시 만드는 것은 비쌉니다. Borah–Owens–Irwin 방법은 현재 트리에 대한 국소적인 교환으로 접근합니다. 점 p1과 간선 e1 = (i, j)를 하나 짝지어 보겠습니다.
e1의 직교 배선 위에서 p1과 가장 가까운 점 p를 찾습니다. p를 새 분기점으로 삼아 p1을 연결하면 사이클이 생깁니다. 이 사이클에서 가장 긴 간선을 e2라고 합시다.
왜 원래 간선 e1의 길이는 식에 없을까요? e1을 없애지만 p에서 i와 j로 연결해 그 경로를 대체하기 때문입니다. 실제 구조 변경은 다음과 같습니다.
- 제거
- e1 = (i, j) 와 사이클 최장 간선 e2.
- 추가
- (p, p1), (p, i), (p, j).
- 순증감
- 새로 붙이는 (p, p1)의 길이와 제거하는 e2의 길이만 남습니다.
e2는 트리 전체에서 가장 긴 간선이 아닙니다. 이번 연결로 생긴 사이클에서 제거할 간선입니다. 사이클 밖의 긴 간선을 마음대로 없애면 어떤 부분이 떨어져 나갈 수 있습니다.
p.155의 {b, (a,c)}를 계산해 봅시다. b에서 새 점 p까지의 길이는 2이고 제거할 (b,c)의 길이는 4입니다. 따라서 이득은 4−2=2, 새 총길이는 20−2=18입니다.
| 후보 | gain | 실행 |
|---|---|---|
| {b, (a,c)} | 2 | 실행 → (a,c)와 (b,c)가 사라짐 |
| {a, (b,c)} | 2 | 건너뜀 — 필요한 간선이 이미 삭제됨 |
| {c, (b,d)} | 1 | 건너뜀 |
| {b, (c,e)} | 1 | 건너뜀 |
| {c, (e,f)} | 1 | 실행 → 최종 길이 17 |
남은 이득 2, 2, 1, 1, 1을 모두 더해 총 7을 절약한다고 계산하면 안 됩니다. 앞선 교환이 간선을 지우면 뒤 후보는 더 이상 실행 가능하지 않습니다.
“이득 계산”과 “그 이동이 아직 유효한가?”는 별개입니다. 예약할 때 남아 있던 좌석이 결제 순간에도 남아 있는지 확인하듯, 구조 변경 뒤에는 후보의 유효성을 다시 봐야 합니다.
일반 절차는 pass를 반복하고 더 이상 길이가 줄지 않을 때 종료합니다. 원문은 이 방법을 O(n2) 휴리스틱으로 소개합니다. 앞의 naive 예제는 16, 여기서 수행한 한 pass는 17이지만, 이것을 모든 입력에서의 고정된 우열로 확대해서는 안 됩니다. 이 사례는 탐색 비용과 개선 품질의 절충을 보여 줍니다.
핵심 O/X 퀴즈
1. 이득은 제거하는 사이클 간선의 길이에서 새 연결 길이를 뺀 값이다.
2. 처음에 양의 이득으로 계산한 후보는 앞선 삽입 이후에도 반드시 실행 가능하다.
3. 원문 예제의 한 pass에서는 서로 충돌하지 않는 두 삽입으로 길이 20을 17로 줄인다.
BPRIM: 가까운 점을 붙이되 너무 돌아가지는 말자BOUNDED RADIUS
지금까지는 선의 총량을 줄였습니다. 그런데 소스에서 어떤 싱크까지 가는 길이 길게 돌아간다면 어떨까요? 전체 배선은 짧아도 중요한 신호의 이동 경로는 길 수 있습니다. 여기서 radius가 등장합니다.
점 집합 자체의 radius R은 소스에서 가장 먼 싱크까지의 직접 맨해튼 거리이고, 트리의 radius ρ(T)는 트리를 따라 잰 소스–싱크 거리의 최댓값입니다. 직접 거리가 10인 목적지라도 트리에서 빙 돌아가면 15가 될 수 있습니다.
BPRIM은 Prim처럼 현재 트리에서 가장 가까운 외부 노드 y를 찾습니다. 연결 후보가 (x, y)이면 다음 조건을 검사합니다.
조건을 만족하면 붙입니다. 초과하면 y를 포기하는 것이 아니라, x에서 소스 방향으로 거슬러 올라가며 적절한 새 연결점 x′을 찾습니다. 원문 개요는 이때 더 엄격한 조건인 distT(s, x′) + D(x′, y) ≤ R을 사용한다고 설명합니다.
예제에서는 R = 12입니다. ε=0이면 허용 radius는 12, ε=0.5이면 18입니다. ε가 무한대이면 거리 제한이 없어져 Prim의 MST 구성이 됩니다. ε=0에서 처음에는 (s,a), (a,b), (b,c)를 붙여 경로 길이가 5, 9, 12가 됩니다. 다음에 (c,d)를 붙이면 12+5=17이어서 탈락하므로, 대체 간선 (s,d)를 사용합니다.
| ε | 허용 radius | 실제 radius | 총길이 |
|---|---|---|---|
| 0 | 12 | 12 | 56 |
| 0.5 | 18 | 18 | 49 |
| ∞ | 제한 없음 | 22 | 36 |
거리를 엄격히 제한할수록 배선량을 더 지불하는 모습입니다. 이것은 해당 예제의 결과이지, 모든 입력에서 변화량이 같다는 법칙은 아닙니다.
원문을 읽으며 구분해야 할 대목이 있습니다. 개요는 대체 연결에 R을 사용하지만, ε=0.5인 Table 5.3은 (c,h)를 대체 간선으로 채택합니다. 그림의 거리로 계산하면 s→c가 12, c→h가 6이므로 합은 18입니다. 즉 개요의 엄격한 R 조건과 이 예제 표의 선택은 일치하지 않습니다. 구현할 때도 어느 기준을 적용했는지 명시해야 합니다.
핵심 O/X 퀴즈
1. 점 집합의 radius R과 실제 트리의 radius는 항상 같다.
2. BPRIM은 가까운 연결 후보가 radius 제한을 넘으면 소스 방향으로 대체 연결점을 찾는다.
3. ε가 무한대이면 BPRIM의 radius 제한은 실질적으로 사라진다.
BRBC: MST에 지름길을 추가한 뒤 최단 경로 트리를 뽑자MST → AUGMENT → SPT
BPRIM이 성장 중인 트리를 즉석에서 조절했다면, BRBC는 순서가 다릅니다.
왜 중간에 그래프가 필요할까요? 처음부터 모든 선택을 트리 하나로 확정하지 않고, 비용이 싼 기본 연결망에 지름길 후보들을 더해 두려는 것입니다. 마지막 SPT 단계가 실제로 사용할 연결을 정리합니다.
소스가 루트인 MST를 DFS로 순회합니다. p.165 예제의 순서는 다음과 같습니다.
이것은 각 정점을 한 번만 적은 전위 순서가 아니라 DFS가 실제로 걸어간 왕복 경로입니다. 누적 이동량을 계산하므로 복귀 간선도 중요합니다.
순회하면서 S에 이동한 간선 길이를 더합니다. 노드 Li에 도착했을 때 ε·D(s, Li) < S이면 소스 직결 간선 (s, Li)를 Q에 추가하고 S를 0으로 초기화합니다. 그러므로 S는 소스에서 현재 노드까지의 트리 거리가 아니라 마지막 초기화 이후의 순회 누적 길이입니다.
| 도착 노드 | 누적 S | 기준 ε·D(s,L) | 판정 |
|---|---|---|---|
| a | 5 | 2.5 | S가 크므로 간선 추가 후 초기화 ((s,a)는 이미 존재해도 규칙은 그대로 적용) |
| b | 4 | 3.5 | 초과 → 초기화 |
| c | 3 | 3 | 같으므로 초기화하지 않음 (엄격한 부등식) |
| e | 8 | 3.5 | 초과 → 초기화 |
조건이 ‘작거나 같다’가 아니라 엄격한 부등식이라는 점이 보이지요. 원문의 Table 5.4는 복귀 방문까지 포함해 이 누적값의 변화를 보여 줍니다.
| 알고리즘 | 총길이 | radius |
|---|---|---|
| BPRIM | 49 | 18 |
| BRBC | 52 | 12 |
BRBC는 이 사례에서 선을 3만큼 더 쓰고 최장 경로를 6만큼 줄였습니다. 원문은 BRBC의 배경으로 비용과 거리를 함께 제한하는 shallow-light 구성을 소개합니다. 그 배경 설명의 상계는 ε>0에서 MST 대비 비용 (2 + 2/ε)배, 점 집합 diameter 대비 diameter (1 + 2ε)배입니다.
이 상계는 diameter 기준이므로 앞에서 사용한 radius와 구분해 읽어야 합니다. 핵심 관점은 한 목표만 극단적으로 줄이지 않고 비용과 거리의 증가를 함께 통제한다는 것입니다.
핵심 O/X 퀴즈
1. BRBC의 DFS 누적 길이는 되돌아오는 간선의 이동도 포함한다.
2. 보강 그래프 Q 자체가 항상 최종 출력 트리이다.
3. 예제의 BRBC는 BPRIM보다 총길이가 조금 길지만 radius는 더 작다.
A-tree의 준비: 모든 싱크의 최단 경로를 지키려면?dx · dy · df
Radius 제한만으로는 각 싱크가 자기의 최단 경로를 갖는다고 보장할 수 없습니다. 가장 먼 싱크가 만드는 상한 아래에서, 가까운 싱크는 여전히 돌아갈 수 있기 때문입니다.
MSP-SA는 모든 소스–싱크 경로가 주어진 그래프에서 최단이도록 하면서 전체 트리 비용을 최소화하는 문제입니다. Hanan grid나 균일 격자 위의 직교 버전이 MRSA입니다. 원문은 두 문제를 NP-hard로 소개합니다. 또 버퍼 삽입이나 선폭·드라이버 크기 조절을 적용하면 지연이 경로 길이에 선형적으로 비례하는 경향을 MRSA의 동기로 설명합니다.
소스가 원점에 있고 싱크들이 오른쪽 위에 있는 배치를 생각합시다. 각 싱크를 따로 떨어진 트리의 루트로 놓고 시작합니다. 현재 숲을 Fk, 아직 처리할 루트 집합을 R(Fk)라고 하겠습니다. 소스에서 뻗는 대신, 싱크 쪽의 작은 트리들을 소스 방향으로 모으는 느낌입니다.
- NW(p)
- x좌표가 더 작고 y좌표가 더 큰 점들의 영역 (엄격한 부등식).
- SE(p)
- 그 반대 방향의 영역 (엄격한 부등식).
- D(p, Fk)
- 연결 대상 중 x와 y가 모두 p 이하인 지배 영역 (등호 포함).
원문의 blockage는 배선 장애물 전체를 뜻하는 말이 아닙니다. 북서쪽 점 q에서 p의 높이까지 수직선을 내릴 때 다른 노드가 그 선을 가로막으면 q가 blocked입니다. 남동쪽 점에서는 p의 x좌표까지 수평선을 그어 같은 식으로 판단합니다. p.171 그림 5.33이 두 경우를 보여 줍니다.
- dx / mx
- 가려지지 않은 북서쪽 루트들 중 최소 수평 거리와 그 상대.
- dy / my
- 가려지지 않은 남동쪽 루트들 중 최소 수직 거리와 그 상대. 후보가 없으면 무한대.
- df / MF
- 지배되는 연결 대상 중 최소 맨해튼 거리와, 그 거리를 달성하는 점들의 집합. 루트가 아닌 노드도 포함될 수 있습니다.
- mfw / mfs
- MF 안에서 가장 서쪽인 점 / 가장 남쪽인 점.
mfw는 “전체 점 중 가장 서쪽”이 아니라 최소 거리 후보들 중 가장 서쪽입니다. 거리를 먼저 좁히고, 그다음에 방향으로 고릅니다.
예제의 c에서는 북서쪽의 b가 a에 가려져 mx = a, dx = 3입니다. 남동쪽 후보가 없어서 dy는 무한대입니다. 지배되는 후보 중 가장 가까운 점은 f이고 df = 4입니다. 따라서 c는 세 숫자 (3, ∞, 4)로 다음 이동을 판단합니다. 복잡한 기하 정보가 세 거리와 몇 개의 대표점으로 압축되었습니다.
핵심 O/X 퀴즈
1. Radius를 최소로 만들면 모든 싱크의 개별 경로도 자동으로 최단이 된다.
2. dx와 dy는 가려지지 않은 해당 방향의 루트들을 대상으로 계산한다.
3. df의 최소 거리 후보에는 현재 루트가 아닌 노드도 포함될 수 있다.
A-tree의 다섯 이동: 보장되는 선택과 휴리스틱 선택SAFE MOVES vs HEURISTIC MOVES
여기서 safe는 단순히 트리가 끊어지지 않는다는 뜻을 넘어, 원문이 설명하는 배선 최적성 보존 성질을 가진 이동입니다.
p를 mfw에 연결하고 루트 집합에서 제거합니다. 두 트리를 병합하는 이동입니다.
p에서 아래로 수직 배선을 Δy = min{ dV(p, mfs), dy } 만큼 연장하고, 끝점 p′을 새 루트로 둡니다.
왼쪽으로 수평 배선을 Δx = min{ dH(p, mfw), dx } 만큼 연장하고, 끝점 p′을 새 루트로 둡니다.
각 루트 p의 mfw를 살펴보고, 그 연결 대상이 소스에서 가장 먼 경우를 선택해 연결합니다.
두 루트를 연결하는 lower-L의 왼쪽 아래 꺾임점 p′을 생각해, 그 p′이 소스에서 가장 먼 쌍을 고릅니다. 두 루트를 p′에 연결하고 p′을 새 루트로 둡니다. 원문은 H1과 H2 사이에서도 연결 후 대표점이 더 먼 이동을 선호한다고 설명합니다.
S1은 병합, S2와 S3는 성장이라는 구별을 먼저 잡으세요. 세 조건을 외우기보다 두 방향의 거리와 df를 비교해서 무엇을 먼저 확정하는지 이해하는 편이 낫습니다.
Safe move가 있으면 먼저 사용하고, 없을 때 휴리스틱을 사용합니다. 매 이동 뒤에는 루트 집합뿐 아니라 관련 dx, dy, MF 정보를 갱신해야 합니다. 처음 계산한 값을 끝까지 사용하는 알고리즘이 아닙니다.
“safe move의 순서가 중요하지 않다”는 설명을 “어떤 순서로 실행해도 그림이 완전히 같다”로 바꾸지 마세요. 중요한 것은 최적성을 보존한다는 성질입니다. 휴리스틱 이동까지 사용하는 일반 실행에서는 전체 배선 길이의 최적성이 보장되지 않습니다.
핵심 O/X 퀴즈
1. S2는 기존 루트에서 아래로 배선을 연장하고 새 끝점을 루트로 삼는다.
2. H1은 현재 루트 p 자체가 소스에서 가장 먼 경우를 선택한다.
3. 휴리스틱 이동을 사용하는 일반 A-tree 실행에서도 전역 최소 배선 길이가 항상 보장된다.
A-tree 예제: 아홉 번의 safe move로 길이 18 만들기Table 5.5 · Figure 5.39
초기 루트는 a, b, c, d, e, f입니다. 세 값 (dx, dy, df)와 가능한 이동은 다음과 같습니다.
| 루트 | (dx, dy, df) | 가능한 이동 |
|---|---|---|
| a | (∞, 1, 5) | S2 |
| b | (∞, 3, 2) | S1 |
| c | (3, ∞, 4) | S3 |
| d | — | S2 |
| e, f | — | S3 |
예제는 가능한 safe move 중 알파벳 순서로 선택합니다. 처음 a를 아래로 내릴 때 a와 mfs인 소스 사이의 수직 거리는 4이고 dy는 1이므로, 1만 내려가 a1을 만듭니다. 루트 a는 사라지고 a1이 들어옵니다. 원래 단자 a 자체가 삭제되는 것은 아닙니다.
| # | 이동 | 내용 | 추가 길이 |
|---|---|---|---|
| 1 | S2 | a를 1만큼 내려 a1 생성 (수직거리 4와 dy=1 중 작은 값) | 1 |
| 2 | S2 | a1을 2만큼 내려 a2 생성 (수직거리 3과 dy=2 중 작은 값) | 2 |
| 3 | S1 | a2를 소스에 연결 | 2 |
| 4 | S1 | b를 a에 연결 | 2 |
| 5 | S1 | c를 a1에 연결 | 3 |
| 6 | S2 | d를 4만큼 내려 d1 생성 | 4 |
| 7 | S1 | d1을 c에 연결 | 2 |
| 8 | S1 | e를 d1에 연결 | 1 |
| 9 | S1 | f를 a2에 연결 | 1 |
화면을 멈추고 루트와 실제 노드를 구분해 보세요. a와 a1은 더 이상 현재 루트가 아니지만 이미 만들어진 트리 안에 남아 있습니다. 그러므로 다른 트리가 이 점들에 붙을 수 있습니다. a가 루트 집합에서 사라졌다는 이유로 b가 a를 후보에서 제외했다면 이 예제를 재현할 수 없습니다.
p.177 그림 5.39는 이 아홉 단계의 숲을 연속해서 보여 줍니다. 검은 노드는 그때의 현재 루트이고, 최종 그림의 흰 사각형은 사용된 Steiner node를 표시합니다. 선이 늘어나면서 검은 루트가 합쳐지거나 교체되는 흐름을 함께 보면 표가 훨씬 쉽게 읽힙니다.
이 예제에서는 모든 이동이 safe move이고, 최종 소스–싱크 경로들은 모두 최단이며 총길이는 18입니다. 일반 A-tree가 언제나 휴리스틱 없이 끝난다고 확대하면 안 됩니다.
한 문장으로 복습하겠습니다. 단자들을 소스 방향으로 성장시키고 병합하되, 현재 루트와 이미 만들어진 전체 숲의 노드를 구분하며 정보를 갱신한다.
핵심 O/X 퀴즈
1. 루트 집합에서 제거된 노드는 배선 트리에서도 삭제되어 이후 연결 대상이 될 수 없다.
2. 원문 예제는 safe move만으로 총길이 18의 최종 트리를 만든다.
3. 이동 후에는 새 루트 위치가 달라지므로 거리 정보와 가능한 이동을 다시 확인해야 한다.
Elmore delay: 길이가 아니라 저항이 떠안는 부하를 보자RC MODEL
경로 길이가 같으면 신호 지연도 같을까요? 앞에서 썼던 길이와 radius는 성능의 간접 지표였습니다. 실제 RC 트리에서는 어떤 저항이 얼마나 많은 정전용량을 충전해야 하는지도 중요합니다.
- rd
- 드라이버 출력 저항.
- Cs
- 전체 트리의 정전용량.
- re / ce
- 해당 배선 간선의 저항과 정전용량.
- Cv
- 그 간선 아래쪽 노드 v에서 시작하는 서브트리의 전체 정전용량.
식을 말로 읽어 봅시다. 드라이버는 전체 트리 부하를 감당합니다. 그리고 소스에서 목적지까지 만나는 각 배선 저항은 자기 배선 정전용량의 절반과 아래쪽 전체 부하를 감당합니다. 이 기여를 경로를 따라 더합니다.
다른 가지가 왜 내 싱크의 지연을 바꿀까요? 새 가지는 전체 정전용량 Cs를 바꾸고, 공유하는 상위 경로의 아래쪽 정전용량도 바꾸기 때문입니다. 내 싱크로 가는 선을 직접 늘리지 않아도, 같은 공급 경로에 매달린 부하가 늘면 내 지연이 증가할 수 있습니다.
계산 순서는 먼저 아래에서 위입니다. 싱크 입력 정전용량을 zv로 쓰면, 서브트리 정전용량은 자식 w들에 대해 zv와 c(v,w) + Cw를 더해 얻습니다. 부모에서 v로 들어오는 간선은 이 Cv 안에 다시 넣지 않습니다. 그 간선의 정전용량은 지연식에서 별도로 처리하기 때문입니다.
부하는 bottom-up, 지연은 source-to-sink입니다. 앞의 L-RST에서도 트리 순회가 중요했지만, 이번에 전달하는 정보는 겹침량이 아니라 정전용량과 지연입니다.
길이의 제곱이 나타나는 이유도 식에서 볼 수 있습니다. 단위 길이 저항과 정전용량이 r, c인 길이 ℓ의 배선에서는 자기 배선 기여에 rℓ · cℓ/2가 들어가므로 ℓ2 항이 생깁니다. 다만 가지와 싱크 부하가 있는 일반 트리의 지연 전체가 경로 길이 하나만으로 결정된다는 뜻은 아닙니다.
| 항목 | 값 | 격자 한 칸 (1mm) |
|---|---|---|
| r | 0.4 Ω/μm | 400 Ω |
| c | 0.2 fF/μm | 200 fF |
| rd | 250 Ω | — |
| 싱크 부하 | 50 fF | — |
최소 격자 간격은 1μm가 아니라 1mm입니다. 저항을 kΩ로 쓰면 kΩ × fF가 ps가 되어 원문의 계산과 맞습니다. mm와 μm를 혼동하면 자릿수가 크게 틀어집니다.
핵심 O/X 퀴즈
1. Elmore 지연은 해당 싱크로 가는 경로 길이만 알면 항상 계산할 수 있다.
2. 다른 가지에 새 부하를 추가해도 기존 싱크의 지연이 변할 수 있다.
3. 예제에서 격자 한 칸은 1μm가 아니라 1mm이다.
ERT: Prim처럼 자라지만, 가장 짧은 간선을 고르지는 않는다ELMORE ROUTING TREE
ERT는 소스 하나에서 시작해 싱크를 하나씩 추가합니다. 겉모습은 Prim과 비슷하지만 다음 연결을 고르는 질문이 다릅니다. “어느 간선이 가장 짧은가?”가 아니라 “이 연결을 추가한 뒤 현재 모든 싱크의 최대 Elmore 지연이 가장 작아지는가?”입니다.
현재 트리의 각 노드 u에서 외부 싱크 중 가장 가까운 후보를 찾습니다. 각 후보를 임시로 연결해 트리의 정전용량과 싱크 지연들을 계산하고, 최대 지연이 가장 작은 연결을 선택합니다.
원문은 싱크 입력 정전용량이 모두 같을 때 이 최근접 후보 축소를 사용합니다. 입력 부하가 서로 다르면 가장 가까운 싱크가 지연 관점에서도 최선이라고 할 수 없어서, 각 u에 대해 다른 외부 싱크들도 검사해야 합니다. 본문 알고리즘을 구현하면서 이 각주를 빼면 적용 범위가 달라집니다.
예제에서 처음에는 소스 s의 최근접 싱크 a를 추가합니다. 두 번째 반복의 후보는 (a,b)와 (s,c)입니다. 첫 후보를 붙이면 가장 느린 싱크는 b입니다.
+ 1.2(300 + 50 + 1200 + 50)
+ 2.4(600 + 50) = 3955 ps DRIVER + (s,a) + (a,b)
첫 항은 드라이버 저항이 전체 부하를 감당하는 부분입니다. 둘째 항의 저항 1.2는 (s,a)의 저항이고, a 아래에 새로 매달린 (a,b)의 배선과 b의 부하까지 들어갑니다. 셋째 항은 (a,b) 자체의 기여입니다. 단순히 새 간선의 길이만 계산한 것이 아니라는 점을 확인하세요.
| 반복 | 후보 | 최대 지연 | 선택 |
|---|---|---|---|
| 2 | (a,b) / (s,c) | 3955 / 2035 ps | (s,c) |
| 3 | (a,b) / (s,d) / (c,d) | 4267.5 / 2937.5 / 5917.5 ps | (s,d) |
| 4 | b→a / b→s / b→c / b→d | 4630 / 4720 / 10720 / 8310 ps | (a,b) |
“항상 소스에 직접 붙이면 가장 빠르겠지”도 정답이 아닙니다. 마지막 비교에서는 a를 거치는 구조의 최대 지연(4630)이 소스 직결(4720)보다 조금 더 작습니다. 배선 공유에 따른 전체 부하와 경로 저항을 함께 평가해야 합니다.
또 새로 추가한 싱크의 지연만 보고 결정하면 안 됩니다. 기존 싱크의 지연도 달라질 수 있으므로 목적함수는 추가 후 현재 모든 싱크의 최댓값입니다. 원문 예제에서 특정 싱크만 계산하는 장면은 그 싱크가 최댓값을 가진다고 확인했기 때문입니다.
원문은 ERT 결과에 MST라는 표현도 사용하지만, 여기서 따라가는 선택 기준은 총배선 길이가 아니라 지연입니다. 길이 최소성을 보장하는 Prim과 동일시하지 말고, 제시된 후보들 중 지연이 좋은 연결을 선택하는 성장 절차로 이해해야 합니다.
핵심 O/X 퀴즈
1. ERT는 Prim과 마찬가지로 항상 길이가 가장 짧은 간선을 선택한다.
2. 원문의 최근접 외부 싱크 후보 축소에는 균일한 싱크 입력 정전용량이라는 조건이 있다.
3. 후보 평가에서는 새 싱크뿐 아니라 기존 싱크들의 지연도 고려해야 한다.
SERT: 기존 노드 사이가 아니라, 기존 배선의 중간에도 붙이자STEINER ELMORE ROUTING TREE
ERT에서는 기존 노드에 새 싱크를 붙였습니다. 이제 배선의 중간에도 새 분기점을 넣을 수 있게 해 봅시다.
이번 원문 예제는 앞의 ERT와 공정 매개변수가 다릅니다. r=0.073 Ω/μm, c=0.083 fF/μm, 드라이버 저항 212 Ω, 싱크 입력 정전용량 7.1 fF인 1.2μm 기술 사례입니다. 따라서 앞에서 얻은 4630ps와 여기서 얻을 값을 그대로 나눠 알고리즘 성능 향상률이라고 하면 안 됩니다.
| 반복 | 후보 | 최대 지연 | 선택 |
|---|---|---|---|
| 1 | a 연결 | — | a 추가. (s,a)의 L자 방향은 유연하게 둠 |
| 2 | b→a 413.0 / b→s 464.2 d→p 326.1 / d→s 331.0 c→p 268.6 / c→s 273.5 | 최소 268.6 | 새 분기점 p를 통해 c 연결 (그림 5.45(e)) |
| 3 | b 추가 533.3 / 579.6 / 569.6 / 553.7 d 추가 446.4 / 413.3 / 420.5 | 최소 413.3 | (p,c)에 새 분기점 q를 만들고 d 연결 |
| 4 | 606.3 / 652.5 / 680.0 / 833.0 / 762.5 / 608.0 | 최소 606.3 | b를 a에 연결 (이때 d의 지연은 557.3) |
세 번째 반복에는 일곱 개의 서로 구별되는 후보가 있습니다. 여러 간선의 접속 후보가 같은 p를 가리키는 경우가 있어서, 단순한 후보 수 계산보다 서로 다른 구조의 수가 작아질 수 있습니다. 마지막 반복에서는 소스 직결의 608.0ps와 아주 가까워도, 주어진 모델에서 더 작은 606.3ps 쪽을 고릅니다.
SERT를 “무조건 Steiner point를 많이 넣는 방법”으로 이해하면 안 됩니다. 새 점이 유리한 후보를 제공할 때 사용하고, 마지막 b처럼 기존 노드에 붙이는 쪽이 좋으면 그렇게 합니다. 원문 그림의 p, q, r도 각 후보 구조 안에서 도입되는 분기점이므로, 같은 문자만 보고 서로 다른 후보의 점을 한꺼번에 합치면 안 됩니다.
전체 흐름을 한 번에 읽겠습니다. 외부 싱크 선택, 접속할 기존 간선 또는 소스 선택, 필요하면 분기점 도입, 모든 싱크 지연 재평가. ERT에서 SERT로의 차이는 평가 기준을 바꾼 것이 아니라 연결할 수 있는 위치의 범위를 넓힌 것입니다.
핵심 O/X 퀴즈
1. SERT는 간선 중간의 분기점뿐 아니라 기존 끝점이나 소스에 연결하는 경우도 고려한다.
2. 원문의 ERT 최종값 4630ps와 SERT 최종값 606.3ps는 같은 전기적 조건의 직접 비교이다.
3. SERT에서도 최단 접속 거리와 최종 후보를 고르는 지연 목적함수는 구분해야 한다.
후속 연구의 지도: 같은 기본 아이디어가 어디로 확장되는가?PROBING FURTHER, pp.192–196
이 부분은 앞의 알고리즘들이 끝점이 아니라 이후 연구의 재료가 된다는 것을 보여 줍니다. 논문 이름을 모두 외우기보다 무엇을 유지하고 무엇을 바꾸었는지에 주목하겠습니다.
- 차수 제한
- L-RST 뒤에는 최대 차수를 제한하는 MST 문제가 소개됩니다.
- 유연한 트리
- 일부 Steiner point를 움직이면서도 안정성과 topology를 유지하는 트리를 연구합니다. 배선 과정에서 경로를 조정할 여지가 있는지도 보자는 관점입니다.
- 1-Steiner 가속
- 한 점 추가로 생기는 MST 변화가 작은 상수 개수로 제한된다는 관찰을 이용한 구현과 병렬화. 적어도 하나의 MST를 포함하는 spanning graph로 검사할 점–간선 쌍을 줄여 O(n log n) 시간, O(n) 공간을 쓰는 휴리스틱도 있습니다.
- 모델로서의 라우팅
- 선형계획 완화 기반 RV 접근과 기하적 축소의 결합, 1-Steiner 모델을 SOC 전역 배선 길이 분포 예측에 사용하는 연구.
- AHHK
- 추가할 간선의 비용에 길이와 경로 거리의 영향을 함께 반영합니다.
- diameter
- 소스가 여러 개라면 한 소스 기준 radius 대신 임의의 두 노드 사이 최대 거리가 중요해집니다.
- C-tree
- 비슷한 싱크들을 묶어 하위 트리를 만든 다음 상위 수준에서 timing-driven 연결을 수행합니다.
- 활용
- 버퍼 블록 계획이나 다단계 라우팅으로 이어집니다.
- 동시 결정
- 트리를 먼저 확정하고 버퍼·선폭을 나중에 조절하는 대신, 트리 구성·버퍼 삽입·wire sizing을 함께 결정합니다.
- PFA / IDOM
- FPGA의 일반 가중 그래프에서 최단 경로들을 겹쳐 접거나, Steiner node를 반복 선택합니다.
- 구현 스펙트럼
- greedy, 정확한 branch-and-bound, 동적 계획법, 계산 범위를 줄인 근사적 변형.
- Minimal Cover
- 원점에서 다이아몬드 경계를 넓혀 가며 간선 연장·Steiner point 도입·싱크 도달을 처리하고, O(n log n) 시간에 최적 RSA 길이의 두 배 이하를 보장합니다.
- gain의 교체
- 간선 교환 방식의 1-Steiner도 gain을 배선 길이 감소 대신 Elmore 지연 개선으로 바꿉니다.
- P-tree
- 싱크 순열에서 topology를 만들고 면적·지연을 절충하며 선폭 조절도 통합합니다.
- MVERT
- 단순한 최대 지연 대신 최대 지연 위반을 줄이고, Hanan grid 밖의 점까지 사용해 배선 길이를 개선합니다.
- RATS-tree · 3D
- RC뿐 아니라 인덕턴스를 포함한 RLC 효과를 고려하고, 3D IC에서는 층 사이를 잇는 TSV 위치와 열 최적화를 위한 재배치까지 다룹니다.
이 연구 지도를 관통하는 질문은 같습니다. 후보를 더 효율적으로 찾을 것인가, 목적함수를 바꿀 것인가, 가능한 구조를 넓힐 것인가, 물리 모델을 정교하게 만들 것인가?
핵심 O/X 퀴즈
1. 한 점을 추가한 뒤의 MST 갱신 범위를 줄이는 것은 1-Steiner 속도 개선의 한 방향이다.
2. 여러 소스를 다루어도 반드시 하나의 고정 소스에 대한 radius만 고려해야 한다.
3. 후속 연구에는 버퍼·선폭·인덕턴스·3D 연결처럼 기본 RC 평면 트리 밖의 요소도 등장한다.
전체 복습: 알고리즘 이름보다 선택의 이유를 설명하자WRAP-UP
누군가 단자 그림 하나를 주며 “좋은 배선 트리를 만들어 주세요”라고 하면, 바로 알고리즘을 실행하지 마세요. 먼저 무엇을 좋은 결과라고 부르는지 물어야 합니다.
| 원하는 것 | 해당 알고리즘 |
|---|---|
| 기존 MST의 연결 관계를 유지하며 직교 배선의 공유를 늘리고 싶다 | L-RST |
| 점을 새로 추가하며 현재 트리의 길이를 개선하고 싶다 | 1-Steiner |
| 소스에서 너무 돌아가는 경로를 막고 싶다 | BPRIM · BRBC |
| 모든 싱크에 개별 최단 경로를 요구한다 | A-tree |
| 저항과 부하를 반영한 시간값을 직접 비교하려 한다 | ERT · SERT |
같은 “짧다”라는 말도 네 가지로 번역됩니다. 총배선이 짧다 · 가장 긴 경로가 짧다 · 각각의 경로가 최단이다 · 모델상의 신호 지연이 작다. 이 말을 구분할 수 있으면 서로 다른 알고리즘의 출력이 왜 달라지는지 설명할 수 있습니다.
원문의 추가 연습문제도 이 구분을 시험합니다. L-RST의 재배선 안정성을 확인하고, 1-Steiner에서 다른 동률 선택으로 출발하고, BPRIM과 BRBC의 결과를 비교하게 합니다. A-tree의 safe move를 역알파벳 순서로 실행해 보라는 문제도 있습니다. 정답 그림을 외웠는지보다 선택 순서와 불변 성질을 이해했는지를 묻는 것입니다.
특히 p.191의 두 비교를 기억하세요. 하나는 같은 입력에서 1-Steiner와 A-tree의 총길이뿐 아니라 소스–싱크 경로도 비교하는 것입니다. 길이만 보면 경로 제약의 의미를 놓칩니다. 다른 하나는 SERT 예제를 ERT와 같은 65nm 매개변수로 다시 실행하는 것입니다. 공정 수치가 다른 결과를 바로 비교하지 말라는 점을 실제 계산으로 확인하는 연습입니다.
- L-RST
- 부모 간선 방향별 상태와 복원 선택.
- 1-Steiner
- 추가·삭제한 간선과 gain.
- bounded-radius
- 직접 거리와 트리 거리를 나누어 기록.
- A-tree
- 현재 루트와 전체 숲의 노드를 구분.
- Elmore 계열
- 서브트리 정전용량과 최대 지연을 만드는 싱크.
Steiner routing은 점들을 연결하는 그림 문제가 아니라, 공유할 배선과 허용할 우회, 그리고 감당할 전기적 부하를 목적에 맞게 선택하는 문제입니다. 이제 새로운 트리를 보면 “연결되었네”에서 멈추지 말고, “왜 이 구조를 선택했으며 무엇을 보장하는가?”까지 질문해 보세요.