출발지와 목적지 사이에서 가장 짧은 길을 찾았다면 배선 문제를 잘 푼 걸까요? 전선을 하나만 놓는다면 그럴 수 있습니다. 그런데 수많은 전선이 같은 통로를 쓰려 한다면요?

multi-net routing은 바로 이 문제입니다. 배선 자원을 그래프 G(V,E)로 나타내고, 연결해야 할 단자 집합들을 네트리스트 NL로 줍니다. 각 네트의 단자들을 연결하는 트리를 만들되, 어떤 간선에서도 사용량이 용량을 넘지 않아야 합니다. 그 안에서 총 배선 길이, 혼잡, 가장 긴 source–sink 경로 같은 목표를 개선합니다. 연결만 성공했다고 끝이 아니라, 여러 연결이 함께 존재할 수 있어야 합니다.

앞의 세 방법은 전역 배선이고, 마지막은 상세 배선입니다. 또 원문은 SMMT 기반 방법을 네트 하나씩 처리하는 순차 라우터로, 나머지를 여러 네트를 함께 고려하는 방법으로 분류합니다. 여기서 ‘함께 고려한다’는 말이 모든 내부 연산을 동시에 수행한다는 뜻은 아닙니다. 뒤에서 볼 MM 방법도 한 번의 갱신에서는 특정 네트 하나를 바꿉니다. 중요한 것은 다른 네트의 사용 상황을 어떻게 의사결정에 반영하느냐입니다.

먼저 혼잡을 피하고, 다음에 길이를 줄이고, 때로는 기존 선택을 철회하거나 여러 선택을 묶습니다. 이제 첫 번째 질문으로 들어가겠습니다. 전체 길이를 줄이는 대신, 가장 나쁜 간선 하나를 개선하면 무엇이 달라질까요?

간선마다 숫자가 적힌 그래프를 보겠습니다. 이 숫자를 길이가 아니라 현재 배선 사용량이라고 생각해 보세요. 어떤 트리는 대부분 한산한 간선을 쓰지만 딱 한 곳에서 매우 혼잡한 간선을 통과합니다. 다른 트리는 조금 돌아가지만 그런 병목을 피합니다. SMMT가 선호하는 것은 두 번째 방향입니다.

원문은 이 SMMT 문제를 효율적으로 최적 해결할 수 있다고 설명하지만, 그중에서 배선 길이까지 최소화하는 MSMMT는 NP-hard라고 구분합니다. 이 구분을 놓치면 “Steiner 트리를 MST로 다 풀 수 있다”는 잘못된 결론에 도달합니다.

왜 반드시 ‘단자가 아닌’ 잎만 없앨까요? 단자인 잎을 없애면 연결해야 할 목적지 자체를 버립니다. 반면 비단자 잎은 다른 단자 사이를 연결하는 데 필요하지 않은 막다른 가지입니다. 가지를 하나 자르면 안쪽 정점이 새로운 비단자 잎이 될 수 있으므로, 한 번 훑고 끝내지 않고 반복해야 합니다.

하지만 병목이 같다고 길이까지 같지는 않습니다. 특히 모든 간선의 사용량이 0인 시작 상태에서는 여러 MST가 같은 가중치 합을 가집니다. 어떤 MST를 선택했느냐에 따라 가지치기 후 길이는 달라질 수 있습니다. 따라서 SMMT 단계에는 길이 제한도 붙습니다. 원문의 예제에서는 HPBB에 계수를 곱한 임계값보다 짧은 트리를 받아들입니다.

원문의 5×5 메시 예제를 따라가겠습니다. 간선 가중치는 현재 사용량이고, 간선 용량은 3입니다. 네트는 n1부터 n5 순서로 처리하며, 길이 제한에 쓰는 계수는 2.0입니다. HPBB는 네트 단자들을 둘러싸는 경계 상자의 가로 길이와 세로 길이의 합입니다. 앞의 세 네트는 HPBB가 7이고, 뒤의 두 네트는 8입니다.

첫 네트 n1의 단자는 (1,0), (0,3), (3,2), (3,4)입니다. 가로 범위는 0부터 3, 세로 범위는 0부터 4이므로 HPBB는 7입니다. 처음에는 모든 사용량이 0이고, 전체 메시의 MST에서 불필요한 가지를 제거하여 길이 9의 트리를 얻습니다. 9 < 2×7이므로 채택합니다.

여기서 한 번 멈춰 보세요. 트리를 채택한 뒤에는 그 트리가 사용하는 간선들의 사용량이 올라갑니다. 따라서 두 번째 네트가 보는 그래프는 첫 번째 네트가 보았던 그래프와 다릅니다. 순차 배선의 순서 의존성이 바로 여기에서 생깁니다.

n3의 후보는 병목을 최소화한 트리이기는 하지만 15 > 14입니다. 따라서 거절합니다. 트리를 계산했다는 것과 배선 결과에 등록했다는 것은 다릅니다. 그렇다면 n4는 어떤 그래프를 사용해야 할까요? 거절된 n3의 사용량까지 반영한 그래프일까요? 아닙니다. n3는 채택되지 않았으므로 n4는 n1, n2만 반영된 그래프를 사용합니다. 같은 길이 15라도 네트의 기하학적 규모가 다르면 결과가 달라집니다.

한 패스가 끝나면 네 개의 네트가 배선되었고, 전체 그래프의 최대 사용량은 2입니다. n3가 이번에 거절되었다고 영원히 불가능한 것은 아닙니다. 이후 패스에서 배선 그래프가 달라지면 다시 배선될 수 있습니다.

앞에서 혼잡을 피하다 보니 돌아가는 길이 생겼습니다. 이제 질문을 바꿉니다. “현재의 용량 제약을 지키면서 더 짧게 연결할 수 없을까?” 이것이 SP 단계의 역할입니다.

절차의 시작은 새 경로 계산이 아니라 rip-up, 즉 기존 배선 제거입니다. 자기 배선을 그대로 둔 채 새 경로를 찾으면, 자신이 점유한 자원까지 다른 배선이 차지한 것처럼 보게 됩니다. 따라서 기존 트리를 제거하고 사용량을 갱신한 뒤 재배선합니다.

여기서 ‘현재 트리’라는 말을 강조하겠습니다. 처음 선택한 source에서 모든 단자까지 독립적으로 최단 경로를 구하는 것이 아닙니다. 트리가 성장할수록 새 단자는 기존 트리의 다른 지점에 붙을 수 있습니다. Prim처럼 연결된 부분을 키워 간다는 비유는 유용하지만, 이 알고리즘이 다단자 최소 길이 문제의 전역 최적해를 보장한다는 뜻은 아닙니다.

예제의 n1은 (3,2)에서 시작하여 (3,4), (0,3), (1,0) 순서로 단자를 추가합니다. 앞에서 실패한 n3는 제거할 기존 트리가 없습니다. (2,2)에서 출발해 (1,1), (4,0), (4,4)를 연결하여 이번에는 배선됩니다. 원문의 재배선 채택 조건은 배선 길이 또는 최대 간선 가중치가 감소하는 것입니다. 둘 모두가 반드시 동시에 감소해야 하는 조건으로 읽지 마세요.

또 하나 주의하세요. 앞 단계에서 후보를 만들 때 보았던 최대 가중치 0이나 1과, 표 6.1의 최종 사용량 기준 수치는 관찰 시점이 다릅니다. 나중 네트가 같은 간선을 사용하면 먼저 배선한 트리가 지나는 곳의 사용량도 올라갑니다.

지금까지는 네트 하나를 배선한 다음 다음 네트로 넘어갔습니다. 이번에는 아예 모든 네트를 한꺼번에 변수로 표현해 보겠습니다. 각 네트를 서로 다른 상품, 즉 commodity로 보고, 공통 운송망에서 각자의 출발지와 목적지를 연결하는 것입니다. 상품의 종류를 구분하는 이유는 간단합니다. 한 네트의 source에서 나온 연결을 다른 네트의 sink로 보내면 안 되기 때문입니다.

원문의 방법은 무방향 배선 간선 {u,v} 하나를 두 방향 아크 (u,v), (v,u)로 바꿉니다. 그리고 네트 k가 아크 a를 사용하면 xak = 1, 사용하지 않으면 0으로 둡니다. 이 절에서 실제로 구성하고 푸는 것은 이진 변수를 사용하는 정수 선형계획 (ILP)입니다. 원문 서론의 LP와 계산 난이도에 관한 설명을 읽을 때도, 여기서 다루는 구체적인 정수 배선 모델과 구분해 이해해야 합니다.

하지만 비용만 최소화하라고 하면 아무것도 연결하지 않는 해가 가장 싸겠지요. 그래서 연결을 강제하는 수요 제약이 필요합니다. 각 정점 v, 각 네트 k에 대해 나가는 양에서 들어오는 양을 뺀 값을 정합니다. source에서는 1, sink에서는 −1, 나머지에서는 0입니다.

다음은 용량입니다. 이 부분은 원문의 개요보다 실제 예제 수식을 정확히 봐야 합니다. 식 6.74 이후에서는 한 물리 채널에 대응하는 양방향 아크의 사용량을 함께 더해 용량과 비교합니다.

원문 예제에는 정점 12개, 무방향 간선 16개, 네트 6개가 있습니다. 숫자를 세어 보는 이유는 단순합니다. 모델을 빠뜨리지 않고 만들었는지 확인하는 첫 번째 검산이기 때문입니다.

네트는 n1={a,l}, n2={i,c}, n3={d,f}, n4={k,d}, n5={g,h}, n6={b,k}이고 각 쌍에서 앞의 정점이 source입니다. 예를 들어 n1에 대해 정점 a에서는 다음 식이 됩니다.

여기서 질문입니다. 전체 최적해라면 각 네트도 반드시 자기 최단 경로를 사용해야 할까요? 아닙니다. 이 결과에서 n6는 개별적으로 가장 짧은 길을 쓰지 않습니다. 용량을 무시한 최단 경로의 길이는 17이지만, 이 해에서는 23을 사용합니다. 그 추가 비용이 다른 네트들과 자원을 나누기 위한 조정입니다.

ILP는 문제를 정확하게 표현하지만, 원문은 큰 문제에서 계산 부담이 커진다는 점을 지적합니다. 그래서 같은 다품종 흐름 관점에서 최단 경로와 rip-up-and-reroute를 반복하는 MM (minimax) 휴리스틱을 소개합니다. 이 방법은 2핀 네트를 다루므로 다단자 네트는 여러 2핀 연결로 분해하여 처리합니다. 이 제한도 알고리즘의 성격에 포함해서 기억해야 합니다.

Jr0까지 고려한다는 점이 중요합니다. 이미 꽉 찬 통로로 혼잡을 옮기는 일을 피하려는 구조입니다. 또한 이때도 용량을 직접 제약으로 적용하는 대신, 방금 설정한 무한대 비용을 사용합니다.

원문에는 유한한 대체 경로가 하나도 없는 경우를 위한 단계 9와 탈출 절차도 있습니다. Jr0를 사용하는 네트 집합에 대해, 한 네트가 이 집합의 두 아크를 동시에 쓰는지를 검사합니다. 그런 조합이 전혀 없으면 원문 절차는 해가 없다고 판정합니다. 그렇지 않으면 해당 집합의 아크를 가장 많이 사용하는 네트를 골라, 기존 경로를 최대한 보존하면서 재배선합니다. 다만 제시된 연습 예제는 이 두 단계를 사용하지 않으며, 이 절에는 그 판정의 일반적인 증명도 제시되어 있지 않습니다.

앞의 6개 네트를 이번에는 MM으로 풀어 보겠습니다. 최단 경로가 동률이면 예제 지시대로 꺾임 수, 즉 이 모델의 비아 수를 줄이는 쪽을 택합니다. 초기 최단 경로의 길이는 차례대로 24, 24, 12, 14, 11, 17이고 합은 102입니다. ILP의 108보다 작네요. 그렇다면 더 좋은 해일까요? 아직 아닙니다. 용량을 무시해서 얻은 값이므로 실행 가능한 배선인지부터 확인해야 합니다.

채널 c(d,i)와 c(e,f)의 사용량이 3입니다. 용량은 2이므로 최대 초과량은 1이고, J1은 이 두 채널입니다. J1⁰에는 이들뿐 아니라 사용량이 정확히 2인 c(a,d), c(e,h), c(i,j), c(j,k)도 들어갑니다. 최대 초과량보다 하나 작은 값이 0이므로, 용량에 딱 맞게 사용 중인 채널까지 막는 것입니다.

첫 반복에서는 n1을 골라 a → b → c → g → l로 바꾸고 나머지는 그대로 둡니다. 갱신 뒤에도 최대 초과량은 여전히 1입니다. 여기서 “아무 개선도 없었다”고 결론 내리면 안 됩니다. 처음에는 두 채널이 넘쳤지만, 이제 넘치는 채널은 c(e,f) 하나입니다. 최대값이라는 요약 수치가 같아도, 그 최대값을 만드는 자원의 개수는 줄 수 있습니다.

두 번째 반복에서 J2는 c(e,f) 하나이고, J2⁰은 c(a,b), c(b,c), c(e,h), c(d,i), c(e,f)입니다. 다시 계산한 결과이지, 첫 반복의 금지 목록을 영구적으로 누적하는 것이 아닙니다. 두 유한 후보의 증가량이 모두 10이므로 원문은 동률을 깨고 n3를 선택합니다. d → h → j → k → f로 재배선한 뒤에는 초과가 사라지고, 최종 총길이는 24+24+22+14+11+17 = 112입니다.

이번에는 배치 형태가 달라집니다. 표준 셀들이 여러 행에 놓여 있고, 행 사이의 채널을 이용해 연결해야 합니다. 그런데 서로 이웃하지 않은 행의 셀을 연결하려면 중간 행을 통과해야 하지요. 원문은 이를 위해 feedthrough를 삽입합니다. 행을 가로질러 연결을 이어 주는 통과 지점을 만드는 것입니다.

반복 삭제 방법은 두 단계로 구성됩니다. 먼저 feedthrough를 삽입하면서 초기 연결 구조를 만들고, 다음에 네트 세그먼트를 결정하는 반복 삭제를 수행합니다. 두 단계 모두 모든 네트의 후보를 함께 고려하여 순차 배선의 네트 순서 문제를 피하려는 접근입니다.

선택 방식은 Kruskal을 떠올리게 합니다. 전체 후보 목록에서 가중치가 작은 간선부터 살펴보고, 현재 포리스트에 사이클을 만들면 건너뜁니다. 사이클이 없으면 추가하고 필요한 feedthrough를 삽입합니다. 하지만 보통의 고정 가중치 MST 문제와 중요한 차이가 있습니다. feedthrough가 들어가면 행의 폭과 일부 셀 위치가 바뀌므로, 남은 후보의 가중치도 바뀝니다.

따라서 처음 정렬한 목록을 끝까지 그대로 사용하는 것이 아닙니다. 영향을 받은 가중치를 갱신하고 다시 정렬합니다. 선택 하나가 다음 선택의 지형을 바꾸는 셈입니다. 원문이 전체 후보 목록을 사용하는 이유도 여기에 있습니다. 특정 네트 하나를 완성할 때까지 우선하지 않고, 그때그때 모든 네트의 후보 중 유리한 것을 선택합니다.

또 원문이 첫 단계의 추가 간선 수를 선형 규모, 두 번째 단계의 삭제 후보를 이차 규모로 비교하는 것은 후보 연결 수의 차이에 관한 설명입니다. 이를 전체 알고리즘의 실행 시간이 각각 단순히 선형·이차라고 읽어서는 안 됩니다. 실제 절차에는 연결성 검사와 동적인 가중치 갱신도 있습니다.

네 개의 셀 행과 세 개의 채널이 있습니다. 네트는 n1 = {b,c,g,h,i,k}, n2 = {a,d,e,f,j}입니다. 셀과 feedthrough의 폭은 2, 높이는 3이며, 삽입 시 셀들은 오른쪽으로 이동합니다. 각 셀에는 내장된 수직 통과 연결이 있다고 가정합니다. 계수는 K = 0.5, 동률은 사전식 순서로 처리하고, 새 feedthrough는 위쪽 게이트 바로 아래에 둡니다.

첫 네트는 핀 6개이므로 연결 트리에 간선 5개, 두 번째는 핀 5개이므로 간선 4개가 필요합니다. 원래 핀 사이의 연결 선택은 합계 9개입니다. 처음의 완전 그래프 후보는 C(6,2) + C(5,2) = 25개이고, 이 중에서 사이클 없이 필요한 연결을 선택합니다.

첫 일곱 선택은 (a,d), (g,i), (d,e), (h,i), (h,k), (b,c), (e,f)입니다. 중간에 등장하는 (a,e)와 (g,h)는 이미 있는 연결들과 사이클을 만들므로 건너뜁니다. 여기까지는 추가 feedthrough가 필요하지 않아 처음의 가중치 목록을 사용할 수 있습니다.

여덟 번째 후보는 (e,j)입니다. 수평 거리는 0이지만 행 3을 통과해야 하므로 비용은 0 + 0.5 × 21 = 10.5입니다. 이를 추가하면서 feedthrough x를 행 3에 넣습니다. 그러면 행 3의 폭은 21에서 23으로 늘고, 셀 h가 오른쪽으로 이동합니다.

어떤 셀이 오른쪽으로 움직이면 왼쪽 핀에서는 멀어지지만 오른쪽 핀에는 가까워질 수 있기 때문입니다. 행 폭 증가에 따른 벌점과 끝점 이동에 따른 거리 변화는 따로 계산해야 합니다.

갱신 후 가장 앞의 (d,f)는 가중치 14이지만 사이클을 만듭니다. 그다음 (c,h)가 14.5로 선택되고, 행 2에 feedthrough y를 삽입하면서 셀 f를 오른쪽으로 이동합니다. 이것이 아홉 번째 연결입니다. 최종 포리스트가 완성되었으므로 더 선택하기 위한 가중치 갱신은 필요하지 않습니다.

이 예제에서 기억할 장면은 ‘원래 더 비쌌던 (c,h)가 셀 이동 뒤 더 싸졌다’는 것입니다. 처음의 순서를 고정해 놓으면 이 변화를 놓칩니다. 또 9라는 수는 원래 핀 사이에서 선택한 연결 수입니다. feedthrough가 실제 연결의 중간 정점으로 들어가면 이후 세그먼트 그래프의 정점과 간선 수는 달라집니다.

첫 단계에서 트리가 완성되었다고 했습니다. 그런데 이제 간선을 지운다니 이상하지 않나요? 트리에서 간선을 하나라도 지우면 연결이 끊어질 텐데요.

정답은 완성된 트리 자체에서 바로 삭제를 시작하는 것이 아니라, 확보된 feedthrough를 바탕으로 후보 그래프를 다시 만든다는 것입니다. 이번에는 같은 채널에 놓인 같은 네트의 핀들 사이에 완전 그래프를 구성합니다. 이어 비인접 핀들을 연결하는 간선을 제거해 simplified net connection graph를 만듭니다. 그래프는 여전히 최종 트리보다 여분의 연결을 가지고 있으므로, 이후 삭제할 선택지가 남습니다.

이제 평가 기준도 바뀝니다. 첫 단계에서는 수평 거리와 행 통과 벌점을 사용했지만, 반복 삭제 단계에서는 밀도를 사용합니다. 특정 열의 밀도는 그 열을 지나거나, 그 열에서 시작하거나, 그 열에서 끝나는 후보 간선의 수입니다. 끝점도 포함한다는 점을 꼭 기억하세요.

삭제할 때는 가중치가 큰 간선부터 보되, 삭제 후에도 같은 네트의 핀들이 연결되어 있어야 합니다. 원문 예제의 동률 기준은 긴 수평 구간, 큰 d(e), 아래쪽 채널, 큰 사전식 순서입니다. 실제 삭제가 일어나면 그 채널의 밀도와 가중치를 갱신합니다.

여기서도 정렬 한 번으로 끝나지 않습니다. 간선 하나를 지우면 주변 후보들의 평가가 달라집니다. 앞에서는 ‘추가 때문에 가중치가 변했다’면, 이제는 ‘삭제 때문에 가중치가 변하는’ 것입니다.

(x,f), (g,h), (e,f)처럼 서로 다른 후보가 모두 가중치 1입니다. 이때 동률 기준이 실제 삭제 순서를 결정합니다. 단, 연결성은 어떤 동률 기준보다도 우선해서 지켜야 하는 조건입니다.

세 번째 삭제 뒤에도 (e,f)가 다시 등장합니다. 방금 지운 간선이 왜 또 나올까요? 이번에는 채널 1의 (e,f)이기 때문입니다. 핀 쌍이 같아도 어느 채널을 이용하는 후보인지에 따라 다른 간선입니다. 이 후보까지 지우면 f가 고립되므로 건너뜁니다.

외울 것은 이름 여섯 개보다 ‘가중치가 높아도 연결을 끊으면 보존한다’는 판단 방식입니다.

마지막 비교에서는 출발 상태도 구분하세요. 단순화된 여분 후보 그래프의 채널 1 밀도는 4였습니다. 반면 그림 6.29가 비교하는 것은 첫 단계의 실제 선택 결과와 반복 삭제 결과이고, 여기에서는 채널 1 밀도가 3에서 2로 줄어듭니다. 서로 다른 출발 그래프의 수치를 섞으면 계산이 맞지 않는 것처럼 보입니다. 반복 삭제의 핵심은 연결을 유지하면서 후보의 중복과 혼잡을 줄이는 것입니다.

이제 마지막 방법으로 넘어가겠습니다. 채널 배선에서는 위아래 두 줄에 핀들이 있고, 그 사이의 공간에서 같은 네트의 핀들을 연결합니다. 원문은 보통 수평 배선층과 수직 배선층을 하나씩 사용하는 두 층 모델을 설명합니다. 주목적은 채널 높이, 곧 필요한 트랙 수를 줄이는 것이며 비아, 길이, 누화 등은 추가 목표입니다.

앞에서 본 배선 자원 그래프와 달리 여기에서는 정점 하나가 네트 전체입니다. 간선도 실제 전선이 아니라 배치 제약입니다.

그다음은 zone 표현입니다. 각 zone은 HCG의 maximal clique에 대응합니다. ‘더 큰 clique에 포함되지 않는 집합’이라는 뜻이며, 모든 zone이 전체에서 가장 큰 clique라는 뜻은 아닙니다.

이 표현에서 네트 1은 zone 1, 네트 2는 zone 1~2, 네트 6은 zone 3~4를 차지합니다. 나중에 서로 다른 구간에서 끝나고 시작하는 네트를 찾아 같은 트랙 후보로 묶을 때 이 압축된 표현을 사용합니다. 이제 필요한 정보가 준비되었습니다. 가로 충돌, 위아래 순서, 그리고 어느 구역에서 네트가 끝나고 시작하는지입니다.

먼저 병합 없이 Constrained Left Edge를 적용해 보겠습니다. 트랙은 위에서 아래로 채우고, 같은 트랙에서는 왼쪽부터 오른쪽으로 배치합니다. 다만 가장 왼쪽 네트라고 무조건 선택하지는 않습니다. 현재 VCG에서 들어오는 간선이 없는 네트, 즉 위에 먼저 배치해야 할 네트가 남아 있지 않은 후보만 선택합니다.

그런데 이 문제에서 반드시 7개가 필요할까요? 원문이 제시하는 하한은 6입니다. HCG의 최대 clique 크기는 4이므로 적어도 네 트랙이 필요합니다. VCG에서는 1 → 3 → 5 → 8 → 9 → 7처럼 네트 여섯 개가 순서대로 놓여야 하므로 적어도 여섯 트랙이 필요합니다. 두 제약의 하한 중 큰 값이 6이고, 여기서 트랙 하한은 경로 위의 네트 수로 읽어야 합니다.

하한이 6이라는 사실만으로 곧바로 여섯 트랙 해가 존재한다고 결론 내릴 수는 없습니다. 다만 CLE가 얻은 7이 최적인지는 아직 증명되지 않았다는 뜻입니다. 다음 방법은 배치 규칙을 버리는 대신, CLE가 배치할 대상을 미리 묶어서 선택을 바꾸는 방법입니다.

여기서 병합은 서로 다른 회로 신호를 전기적으로 연결한다는 뜻이 아닙니다. 수평으로 떨어진 네트들을 같은 트랙을 사용할 배치 그룹으로 묶는 것입니다. 최종 배선에서도 서로 다른 네트의 선분은 별개로 남습니다.

왼쪽부터 이웃한 zone 쌍 (z, z+1)을 봅니다. L에는 zone z 또는 그 이전에서 끝난 네트를 모으고, R에는 zone z+1에서 시작하는 네트를 모읍니다. 이전에 끝났지만 아직 병합하지 않은 네트도 다음 비교의 L에 남을 수 있습니다.

원문은 이러한 조건을 만족하는 부분집합 P, Q를 구성하고, |P| ≥ |Q|가 되도록 필요하면 이름을 바꿉니다. 그리고 작은 집합 Q에서 먼저 네트 하나를 고른 뒤, P에서 짝을 고릅니다. 이 장에서 사용하는 것은 두 가지 제안 방법 중 ‘simple’ 휴리스틱입니다.

점수 계산을 위해 VCG에 가상 source와 sink를 붙입니다. 진입 간선이 없는 정점들은 source와, 진출 간선이 없는 정점들은 sink와 연결합니다. u(x)는 source에서 x까지의 최장 경로 길이, d(x)는 x에서 sink까지의 최장 경로 길이입니다. 예제에서는 가상 정점과 연결하는 간선까지 포함해 경로 길이를 셉니다. 위와 아래에 걸린 순서 제약의 깊이를 수치로 나타내는 것입니다.

목적은 병합으로 VCG의 최장 경로가 불필요하게 길어지는 일을 줄이는 것입니다. 이것은 원문이 제시한 휴리스틱 점수이지, 모든 입력의 최적 병합을 보장하는 식으로 소개된 것은 아닙니다.

zone 1과 2 사이에서는 L={1}, R={4}입니다. 하지만 1과 4는 VCG의 같은 경로에 있으므로 병합하지 않습니다. zone 2와 3으로 넘어가면 L={1,2}, R={5,6}입니다. 1은 5나 6과 병합할 수 없고 가능한 쌍은 (2,5), (2,6)이므로 P={5,6}, Q={2}로 둡니다.

네트 2의 (u,d)는 (4,1)입니다. 작은 값이 유리하므로 2와 6을 병합합니다. 점수의 소수보다 중요한 것은 5와 묶으면 상하 제약의 결합 부담이 늘지만, 6과 묶을 때는 이 h 증가가 없다는 사실입니다.

zone 3과 4 사이에서는 L={1,3,4}, R={7}인데 가능한 병합이 없습니다. 다음 zone 4와 5에서는 끝난 네트에 26이 추가되고, 새로 시작하는 네트는 8과 9입니다. 호환되는 후보로 P={4,26}, Q={8,9}를 구성합니다.

이번의 (u,d)는 4가 (3,3), 26이 (4,2), 8이 (4,3), 9가 (5,2)입니다. 두 쌍의 선택을 마친 후 VCG와 zone 표현을 갱신합니다. 이제 배치할 그룹은 1, 3, 5, 48, 269, 7입니다. 다시 CLE를 적용하면 위에서부터 1 / 3 / 5 / 48 / 269 / 7, 총 여섯 트랙을 사용합니다. 원문에서 제시한 하한과 같으므로 이 예제에서는 최소 트랙 수에 도달합니다.

원문의 마지막 절은 앞의 네 방법이 다른 설계 목표로 확장되는 모습을 소개합니다. 공통 질문은 “혼잡과 길이를 다루던 구조에 타이밍, 버퍼, 전력망, 누화까지 넣으면 무엇이 달라지는가?”입니다.

따라서 같은 트랙 수의 두 해라도 전기적 특성까지 같다고 할 수는 없습니다. 앞에서 본 단순한 길이 비용이, 이제 여러 종류의 자원 부담을 표현하는 비용으로 확장되는 것입니다. 반복 삭제 계열에는 ‘좋아 보이는 선택을 추가한다’에서 ‘나빠 보이는 중복을 제거한다’로 관점을 바꾼다는 공통점이 있습니다.

처음 질문으로 돌아가겠습니다. 여러 네트의 배선에서 중요한 것은 각자 가장 짧은 길을 찾는 것이 아니라, 모든 연결이 제한된 공간 안에 함께 들어가도록 만드는 것이었습니다.

원문에는 이 네 계열을 다시 적용하는 추가 문제가 있습니다. SMMT·SP 문제는 4×4 메시, 용량 3, 계수 2.0을 사용합니다. 다품종 흐름 문제는 여섯 개의 2핀 네트를 용량 2인 그래프에 배선합니다. 각 문제에서 최종 길이만 쓰지 말고, 채택·거절 직전의 사용량과 실제 반영 후의 사용량을 구분해 기록해 보세요. ILP와 MM은 제약 만족 여부를 먼저 확인한 다음 총길이를 비교해야 합니다.

세 행 배치의 반복 삭제 문제에서는 feedthrough 삽입으로 어떤 셀이 움직였는지, 그 이동이 어느 후보의 수평 거리를 바꾸는지부터 표시하세요. 이후 후보 그래프를 새로 구성하고 열별 밀도, 간선 밀도, 채널 밀도를 구분합니다. 마지막 채널 배선 문제는 10개 열로 구성된 핀 배열에 대해 HCG·VCG·zone을 만들고, 병합 전후 CLE 결과를 비교하게 합니다. 정답이 함께 주어지지 않은 이 문제들은, 결과를 추측하기보다 방금 배운 갱신 과정을 직접 재현하는 연습으로 사용하면 됩니다.