서로 자주 이야기해야 하는 사람 여덟 명을 두 사무실에 나눈다고 생각해 봅시다. 네 명씩 나누는 일 자체는 어렵지 않습니다. 그런데 대화가 필요할 때마다 다른 사무실로 이동해야 한다면요? 자주 협력하는 사람은 같은 방에 두고 싶어집니다. 그렇다고 모두 한 방에 넣으면 두 사무실로 나누라는 요구를 어기게 됩니다.

회로 분할, partitioning도 이 두 요구 사이에서 출발합니다. 게이트들을 여러 파티션에 나누되 파티션의 크기는 대략 비슷해야 합니다. 동시에 서로 다른 파티션에 걸쳐 있는 네트의 수, 즉 cutsize는 작아야 합니다. 자료는 지연이나 전력 같은 다른 목적도 언급하지만, 이번 장의 중심은 연결을 적게 자르면서 균형을 맞추는 문제입니다.

첫 번째 질문입니다. “연결을 가장 적게 자르는 분할을 구하면 균형도 자연스럽게 맞지 않을까요?” 그렇지 않습니다. 연결이 적은 게이트 하나만 떼어내면 cutsize는 작을 수 있지만, 크기는 극단적으로 불균형해집니다. 오늘 등장할 네 알고리즘은 이 충돌을 서로 다르게 다룹니다.

그러니 이번 강의에서 실제로 배우는 것은 알고리즘 이름 네 개가 아닙니다. 같은 회로를 어떤 수학적 대상으로 표현할 것인가, 좋은 분할을 어떤 숫자로 평가할 것인가, 후보를 어떻게 탐색할 것인가, 그리고 균형 조건을 어디에 넣을 것인가입니다.

각 알고리즘에서는 공식을 외우기 전에 그 공식이 무엇을 세는지 먼저 보겠습니다. 계산의 목적은 답 하나를 얻는 것이 아니라, 다음 상태를 스스로 예측할 수 있게 되는 것입니다.

게이트는 정점으로 생각할 수 있습니다. 그렇다면 네트는 무엇일까요? 두 정점 사이의 간선이라고 답하기 쉽지만, 하나의 네트에는 세 개 이상의 게이트가 함께 연결될 수 있습니다. 그래서 회로의 네트를 그대로 표현하려면 여러 정점을 한꺼번에 묶는 hyperedge가 자연스럽습니다.

그런데 KL은 가중 무방향 그래프를 사용합니다. 여러 게이트를 묶는 네트를 보통 간선들로 바꿔야 하죠. 자료가 사용하는 변환이 k-clique 모델입니다. 게이트 k개가 들어 있는 네트를 완전그래프로 바꾸고, 각 간선에 1/(k−1)의 가중치를 줍니다. 이미 존재하는 간선이면 새 간선을 따로 두지 않고 가중치를 더합니다.

예를 들어 세 게이트가 하나의 네트에 들어 있다면 삼각형을 만들고 각 변에 0.5를 줍니다. 두 게이트짜리 네트라면 간선 하나의 가중치가 1입니다. 그림 2.1(b)의 가는 선과 굵은 선은 바로 0.5와 1을 구분합니다. 선이 굵다는 것은 연결이 두 번 잘린다는 뜻이 아니라, 그 간선을 자를 때 목적함수에 더하는 값이 크다는 뜻입니다.

이 질문에 쉽게 ‘그렇다’고 답하면 KL과 FM의 차이를 놓치게 됩니다. 변환식을 직접 계산해 보죠.

따라서 앞으로 KL의 cutsize를 계산할 때는 잘린 간선의 개수가 아니라 잘린 간선의 가중치 합을 구해야 합니다. 그리고 그 값이 원래 회로의 잘린 네트 개수와 항상 같다고 생각하면 안 됩니다. 자료도 일반적인 회로의 모든 절단을 가중 무방향 그래프로 정확히 표현하는 데 한계가 있음을 설명하고, FM의 하이퍼그래프 표현을 대비시킵니다.

KL의 출발점은 이미 주어진 균형 분할입니다. 왼쪽과 오른쪽에 같은 수의 셀이 있고, 한쪽에서 하나씩 골라 교환합니다. 그러면 셀 개수의 균형을 유지하면서 연결 관계만 바꿀 수 있습니다.

어떤 두 셀을 골라야 할까요? 모든 교환을 똑같이 볼 수는 없으니, 교환했을 때 cutsize가 얼마나 줄어드는지를 점수로 삼습니다. 이것이 gain입니다. 부호를 먼저 고정하겠습니다. gain이 양수면 개선, 0이면 변화 없음, 음수면 악화입니다. 따라서 새 cutsize = 이전 cutsize − gain입니다.

셀 x를 하나 보겠습니다. x와 반대쪽 파티션을 잇는 간선 가중치의 합을 외부 비용 Eₓ, 같은 파티션을 잇는 간선 가중치의 합을 내부 비용 Iₓ라고 합니다. x 혼자 반대쪽으로 옮긴다고 상상하면, 외부 간선들은 내부 간선으로 바뀌어 이득이고 내부 간선들은 절단 간선으로 바뀌어 손해입니다. 그래서 단독 이동의 변화량은 Eₓ−Iₓ로 읽을 수 있습니다.

왜 마지막에 2c(x,y)를 뺄까요? 이 부분을 이해하면 공식을 오래 기억할 수 있습니다. x와 y는 교환 전에도 서로 반대편이고, 교환 후에도 서로 반대편입니다. 즉 둘을 잇는 간선은 실제로 계속 잘려 있습니다. 그런데 x 혼자 옮긴다고 계산할 때 그 간선이 사라지는 절단 비용으로 한 번 들어가고, y 혼자 옮긴다고 계산할 때도 한 번 더 들어갑니다. 실제로는 절약되지 않는 비용을 두 번 이득으로 셌으니, 두 배를 빼서 보정하는 것입니다.

한 가지 더 짚겠습니다. 이 예제는 셀 수를 같게 유지하는 교환입니다. ‘한 개씩 교환한다’는 사실과 ‘서로 다른 실제 면적까지 항상 보존한다’는 주장은 같은 말이 아닙니다. 오늘의 손계산에서는 자료의 동일 크기 셀 분할을 따라가고, 뒤의 FM에서는 명시적인 면적 구간을 확인하겠습니다.

가장 좋은 교환을 했습니다. 그런데 다음 교환의 최대 gain이 음수입니다. 여기서 멈추면 될까요? KL의 중요한 아이디어는 “일단 더 가 보고, 나중에 어디까지 받아들일지 결정하자”입니다.

자료의 예제를 따라가겠습니다. 초기 분할은 왼쪽 {a,b,d,e}, 오른쪽 {c,f,g,h}, 초기 cutsize는 5입니다. 첫 교환은 방금 계산한 (d,c)이고 gain은 2입니다. 두 번째 교환에서는 잠긴 d와 c를 후보에서 빼고 다시 계산하여 (b,g)를 얻습니다.

여기서 질문 하나 더. “음수 gain을 허용한다면서, 이 예제에서는 결국 음수 교환을 모두 취소했네요?” 맞습니다. 음수 이동을 허용한다는 것은 반드시 음수 이동을 최종 해에 남긴다는 뜻이 아닙니다. 탐색 중 일시적인 악화를 허용하고, 그 뒤 더 큰 개선이 나오면 그 악화까지 포함한 앞부분을 채택할 수 있다는 뜻입니다.

이 예제처럼 모든 셀이 정확히 한 번씩 반대편으로 가면 마지막에는 처음의 좌우가 뒤집힙니다. 절단값이 초기값으로 돌아오는 것도 자연스럽습니다. 이 관찰은 검산에 쓸 수 있지만, 중요한 것은 마지막 값이 아니라 중간 최솟값입니다.

KL에서는 두 셀을 골라 교환했습니다. FM은 셀 하나를 옮깁니다. 또 회로를 가중 그래프로 바꾸지 않고 하이퍼그래프로 직접 다룹니다. pass와 gain이라는 생각은 이어받지만, 평가 대상과 기본 동작이 달라지는 것입니다.

왜 빼면 될까요? x가 이쪽의 마지막 셀인 네트에서는 x를 옮기면 모든 셀이 반대쪽으로 모입니다. 잘리던 네트가 더 이상 잘리지 않으므로 이득 1입니다. 반대로 모두 이쪽에 있던 네트에서 x만 옮기면 이제 네트가 양쪽에 걸칩니다. 새 절단이 생겨 손해 1입니다. 나머지는 이동 전후 모두 잘려 있어 변화가 없습니다.

셀 c를 보죠. c는 n₁, n₂, n₃에 들어 있고 그중 n₃={c,f,e}에서만 c가 왼쪽의 유일한 셀입니다. 그러므로 FS(c)=1입니다. 세 네트 모두 현재 잘려 있으므로 TE(c)=0이고 gain(c)=1입니다. 셀 g는 더 좋습니다. n₄와 n₆ 모두에서 왼쪽에 g만 있으니 FS(g)=2, 내부 네트는 없어서 gain(g)=2입니다. 오른쪽의 e 역시 n₁과 n₆에서 유일한 오른쪽 셀이므로 gain(e)=2입니다. 반면 a는 어느 네트의 절단도 없애지 못하고 새 절단도 만들지 않아 gain(a)=0입니다.

gain이 가장 큰 셀을 찾았으니 바로 옮기면 될까요? FM에서는 한 번 더 확인해야 합니다. 셀 하나만 옮기므로 크기 균형이 깨질 수 있습니다. 자료는 이동 후에도 면적 제약을 만족하는 셀만 합법적이라고 정의합니다. 최대 gain이라는 조건은 합법적인 후보들 안에서 적용해야 합니다.

예제의 허용 구간은 [3,5]입니다. 각 파티션이 셀을 세 개 이상, 다섯 개 이하 가져야 한다는 뜻입니다. 4 대 4에서 한 셀을 옮겨 5 대 3을 만드는 것은 가능합니다. 그러나 거기서 작은 쪽의 셀을 큰 쪽으로 또 옮겨 6 대 2를 만드는 것은 불가능합니다.

다음은 bucket입니다. gain이 같은 셀들을 같은 칸에 모아 둡니다. 이 예제에서 한 셀이 속하는 네트 수의 최댓값 Pmax는 3이므로 버킷의 gain 범위는 −3부터 3까지입니다. 여기서 Pmax는 ‘한 네트에 들어 있는 셀 수의 최댓값’이 아니라 ‘한 셀에 접한 네트 수의 최댓값’입니다.

그런데 한 셀을 옮길 때마다 모든 셀의 gain을 처음부터 계산해야 할까요? 아닙니다. x의 이동이 직접 바꾸는 것은 x가 들어 있는 네트들의 상태입니다. 따라서 그 네트를 공유하는, 아직 잠기지 않은 이웃들의 gain만 갱신하고 값이 바뀐 셀은 해당 버킷 칸으로 옮겨 줍니다. 잠긴 셀은 선택 후보에서 빠지지만 회로 자체에서 사라지는 것은 아닙니다. 그 셀의 위치는 여전히 다른 셀의 gain에 영향을 줍니다.

시작은 왼쪽 {a,c,d,g}, 오른쪽 {b,e,f,h}, cutsize 6입니다. 최대 gain은 e와 g의 2이고 두 이동 모두 합법적입니다. 알파벳 순서로 e를 오른쪽에서 왼쪽으로 옮깁니다. 크기는 5 대 3, cutsize는 4가 됩니다.

e를 잠근 뒤 이웃 a, c, g, f만 갱신합니다. 새 gain은 각각 −1, −1, 0, 2입니다. 여기서 멈추고 질문하겠습니다. “이제 gain이 2인 f를 옮기면 되겠죠?” 아닙니다. f는 오른쪽에 있고, 오른쪽은 이미 세 개뿐이므로 f를 왼쪽으로 보내면 6 대 2가 됩니다. 따라서 합법적인 후보 중 gain이 가장 큰 d를 옮깁니다.

표의 중간을 더 따라가 보면 결정의 근거가 보입니다. 두 번째 이동 뒤에는 b, c, f의 gain이 모두 0으로 갱신되고, 동률이므로 알파벳이 빠른 b를 옮깁니다. 네 번째에는 gain 0인 g, h, f가 눈에 들어오지만 h와 f는 작은 오른쪽에 있어 왼쪽으로 갈 수 없으므로 왼쪽의 g를 옮깁니다. 여섯 번째에는 c의 gain이 0으로 회복되었는데도 c가 작은 왼쪽에 있어 선택하지 못하고, 오른쪽의 f를 골라 cutsize가 5로 올라갑니다.

KL의 초기값 5와 FM의 초기값 6도 함부로 비교하지 마세요. 두 예제의 초기 분할 자체가 다릅니다. 알고리즘 이름 옆의 숫자만 비교해서 어느 쪽이 우수하다고 결론 내릴 수는 없습니다. 오늘 비교할 것은 동작 원리입니다. KL은 쌍을 교환하고, FM은 합법적인 단일 셀을 이동하며, 둘 다 pass의 최선의 앞부분을 남깁니다.

지금까지는 한 번에 무엇을 움직일지 고민했습니다. EIG는 질문을 바꿉니다. “회로 전체의 연결을 반영하여 셀들을 일렬로 세운다면, 그 줄을 자르는 방식으로 좋은 분할을 찾을 수 있지 않을까?” 이제 이동 순서가 아니라 정점의 배치 순서를 구합니다.

왜 곱으로 나눌까요? 전체 정점 수가 같을 때 1 대 9의 곱은 9이고 5 대 5의 곱은 25입니다. 분자가 같다면 균형 잡힌 쪽의 ratio cut이 더 작습니다. 그러나 분자가 같다는 조건을 잊으면 안 됩니다. 하나만 떼어낼 때 cutsize가 매우 작다면 불균형한 분할이 여전히 이길 수 있습니다.

행렬을 거대한 숫자판으로 보지 마세요. 각 행이 한 정점의 연결 정보를 담고 있다고 읽으면 됩니다. 자료는 인접행렬 A와 차수행렬 D를 만들고 라플라시안을 Q = D − A로 정의합니다. A의 원소 aᵢⱼ는 간선 가중치이고, D의 대각 원소 dᵢᵢ는 정점 i에 접한 간선 가중치의 합입니다.

양수 대각 원소는 연결량 전체를, 음수 비대각 원소는 이웃과의 연결을 나타냅니다. 각 행의 합이 0인 이유는 자기 연결량의 합에서 이웃별 연결량을 모두 빼기 때문입니다. 정점 i의 일차원 좌표를 xᵢ라고 놓고 Q의 정의를 전개하면 다음 식을 얻습니다.

여기서는 원문 설명의 생략도 구분해야 합니다. 자료는 좌표 제곱합이 1인 정규화를 설명하면서 둘째 고유벡터의 배치를 소개합니다. 그러나 그 정규화 하나만 적으면 모든 좌표를 1/√n으로 같게 둔 경우도 허용되어 위 비용이 0이 됩니다. 따라서 ‘모두 같은 위치’인 상수 방향을 제외하는 의미와 좌표 크기를 정규화하는 의미는 구별해야 합니다. 이는 Q의 정의로부터 확인한 수학적 점검이며, 발췌본이 제약 조건의 전체 유도를 제공한다는 뜻은 아닙니다.

자료의 실제 알고리즘은 두 번째로 작은 고유값의 고유벡터를 선택합니다. 개요에는 Lanczos 방법이 제시되고 수치 예제에서는 Matlab 계산 결과를 사용합니다. 우리가 손으로 따라갈 핵심은 고유값 계산기 내부가 아니라, 얻어진 벡터의 각 성분을 해당 셀의 좌표로 해석하고 정렬하는 단계입니다. 또 책의 행렬에는 0.33, 0.58 같은 소수 표기와 그 합인 2.99, 3.99가 사용되므로, 뒤의 표를 재현할 때는 이 제시값을 기준으로 계산합니다.

자료의 둘째 고유값은 0.6281입니다. 각 정점의 좌표는 a −0.6346, b 0.1605, c 0.5711, d −0.1898, e 0.2254, f −0.2822, g 0.0038, h 0.1995, i −0.1641, j 0.1104입니다. 좌표가 작은 것부터 세우면 순서 Z는 다음과 같습니다.

첫 후보부터 직접 계산하죠. a에서 바깥으로 나가는 간선은 a–d와 a–f이며 둘 다 0.5입니다. cutsize는 1이고 ratio cut은 1/(1×9)=0.1111입니다. 첫 두 셀 a, f를 묶으면 cutsize가 3으로 커지고 ratio cut은 3/(2×8)=0.1875입니다. 더 많은 셀을 묶었는데도 목적함수는 나빠졌습니다. 분모뿐 아니라 분자도 함께 바뀌기 때문입니다.

마지막으로 둘째 고유값은 어디에 쓸까요? 이 자료의 ratio cut 정의에서는 하한이 λ₂ 자체가 아니라 λ₂/n입니다. n=10이므로 하한은 0.6281/10 = 0.06281이고, 표의 모든 값은 이보다 큽니다. 하한이라는 것은 그보다 내려갈 수 없다는 기준이지, 이번에 구한 값과 반드시 같아진다는 뜻은 아닙니다. 또 지금 ‘최소’라고 부른 값은 이 순서에서 만든 아홉 후보 중 최솟값이며 모든 가능한 분할을 열거한 것이 아닙니다.

앞에서는 좋은 이동을 찾거나 좋은 정점 순서를 찾았습니다. 이번에는 max-flow min-cut 관계를 이용합니다. 다만 회로 네트를 평범한 간선 하나로 바꾸는 것으로는 충분하지 않습니다. 여러 단자를 가진 네트가 잘릴 때 비용이 한 번만 발생하도록 모델을 만들어야 합니다.

왜 이런 우회 구조를 쓸까요? 정의에서 직접 확인해 봅시다. 어떤 셀은 소스 쪽 S에 있고 같은 네트의 다른 셀은 싱크 쪽 T에 있다고 합시다. S에 있는 셀에서 n_in으로 무한대 간선이 있으므로, 유한한 절단을 만들려면 n_in도 S에 두어야 합니다. 또 n_out에서 T의 셀로 무한대 간선이 있으므로 n_out은 T에 두어야 합니다. 그러면 용량 1의 다리 간선이 S에서 T로 건너갑니다. 네트가 양쪽으로 갈라지면 바로 이 다리에서 비용 1을 지불하는 것입니다. 반대로 그 네트의 셀들이 모두 같은 쪽에 있다면 보조 정점들도 그쪽에 두어 절단 비용을 0으로 만들 수 있습니다.

여기서 ‘모델이 네트 절단 비용을 표현한다’는 사실과 ‘균형까지 갖춘 최적 분할을 한 번에 얻는다’는 주장을 섞으면 안 됩니다. 이 모델에서 s와 t를 지정하고 최대유량을 구하면 우선 s와 t를 분리하는 최소절단을 얻습니다. 그 절단의 양쪽 크기가 적절한지는 아직 확인하지 않았습니다.

최소절단 알고리즘이 아주 작은 절단을 찾았습니다. 그런데 소스 쪽에는 셀이 하나뿐입니다. 알고리즘이 실패한 것일까요? s와 t를 적은 비용으로 분리하라는 문제에는 성공했지만, 우리가 원하는 균형 조건까지 만족한 것은 아닙니다.

FBB는 최대유량을 계산한 뒤 얻을 수 있는 최소절단 후보들 중 균형이 좋은 분할을 살펴봅니다. 그중 면적 조건을 만족하는 것이 있으면 종료합니다. 없다면 현재 경계를 바탕으로 정점들을 병합하고 최대유량을 다시 계산합니다.

또 최대유량에서 포화된 네트라고 해서 그것 하나를 지우면 반드시 s와 t가 분리되는 것은 아닙니다. 포화는 흐름에 대한 정보이고, 절단은 모든 s–t 연결을 끊는 조건입니다. 자료의 예제는 포화 네트들 가운데 실제로 분리를 만드는 조합을 확인합니다.

반복 계산이 너무 비싸지는 않느냐는 질문도 자연스럽습니다. 자료는 이전 반복에서 찾은 증가 경로를 재활용하여 전체 반복의 점근적 시간복잡도를 단일 최대유량 계산과 같은 차수로 유지하는 점을 강조합니다. 매번 아무 정보 없이 처음부터 시작하는 방식으로 이해하면 안 됩니다. 병합 후보는 일반 설명에서는 무작위 선택을 사용하다가 균형에 가까워지면 후보들을 더 자세히 조사하며, 손계산 예제는 알파벳 순서를 지정합니다.

자료의 그림 2.23에는 a부터 i까지 아홉 셀이 있습니다. 면적 조건은 [4,5]이므로 4 대 5 또는 5 대 4로 나누어야 합니다. 처음 소스는 a, 싱크는 i이고, 병합할 셀은 알파벳 순서로 고릅니다.

같은 최소절단 비용을 갖더라도 셀을 배치하는 자유도가 남고, 그 자유도를 균형 개선에 사용할 수 있다는 점을 보세요. 처음 유량 1에서 마지막 유량 3으로 커졌으니 알고리즘이 나빠진 것 아니냐고 물을 수도 있습니다. 하지만 우리가 처음 원했던 것은 단순히 가장 작은 s–t 절단이 아니라 균형을 만족하는 분할이었습니다. 값 1의 분할은 1 대 8이어서 사용할 수 없었고, 병합으로 그런 해를 배제하면서 균형 있는 후보에 도달한 것입니다.

기본 예제를 따라 했다면, 이제 같은 계산을 반복하는 대신 조건 하나를 바꿔 보겠습니다. 중요한 것은 정답 숫자보다, 조건이 바뀌었을 때 어느 단계가 달라지는지 아는 것입니다.

EIG-IG의 intersection graph도 등장합니다. 여기서는 셀이 아니라 원래 회로의 네트가 정점이 되고, 두 네트가 셀을 공유하면 서로 연결됩니다. ‘정점 하나가 무엇을 뜻하는가’부터 다시 읽어야 하는 모델입니다. 자료의 추가 문제는 다음 가중치 정의를 명시합니다.

여기서는 각 연구의 세부 구현을 새로 채우기보다, 기본 알고리즘의 어떤 약점을 겨냥했는지 읽어 보겠습니다. 자료도 이 목록이 포괄적인 전체 조사는 아니라고 밝힙니다.

다만 KFM·RFM·KPM 비교는 소개된 연구의 결과이지, 모든 입력에서의 무조건적인 성능 보장으로 읽으면 안 됩니다.

EIG에서는 고유벡터 하나를 좌표로 읽었습니다. 그렇다면 여러 고유벡터를 쓰면 어떨까요? 자료는 작은 고유값들에 대응하는 여러 고유벡터를 사용하여 정점들을 다차원 공간에 놓고 이를 다중 분할로 확장한 연구를 소개합니다. 고유값 계산 전에 클러스터링으로 문제 크기를 줄이는 방법도 함께 제안됩니다.

한편 분할에 유용한 일차원 순서를 꼭 같은 고유벡터 절차로만 얻을 필요는 없습니다. 자료의 Gordian-L 관련 접근은 해석적 배치 결과에서 셀 순서를 얻고 그 순서를 잘라 ratio cut을 평가합니다. 여기서 공통 구조는 ‘배치로 순서를 얻고, 순서로 분할 후보를 만든다’입니다. MELO 관련 설명은 여러 고유벡터를 이용하여 각 정점을 다차원 벡터로 바꾸고, 그래프 분할을 벡터 분할의 관점에서 다룹니다. 자료는 모든 고유벡터를 사용할 때 두 문제의 정확한 대응을 설명하며, 이를 바탕으로 정점 순서를 만들어 이분할과 다중 분할을 얻는 접근을 소개합니다.

마지막으로 좌표를 만들 때 어떤 길이 비용을 쓸지도 바꿀 수 있습니다. 자료는 선형 목적이 배선 길이에 유리한 측면과, 이차 목적이 정점들을 더 성기게 배치하여 겹침을 줄이는 측면을 대비시킵니다. α-order 목적은 1 ≤ α ≤ 2 사이를 조절하여 두 성격을 함께 활용하려는 시도입니다.

지금까지는 셀을 어디에 둘지만 바꾸었습니다. 그런데 경계를 넘는 연결을 줄이기 위해 일부 논리를 양쪽에 복제할 수도 있다면 어떨까요? 분할만 정하는 문제에서, 어떤 논리를 복제할지도 함께 결정하는 문제로 넓어집니다.

자료는 주어진 분할에서 최소절단 논리 복제를 찾는 유량 기반 접근을 소개합니다. 하이퍼그래프로 확장하고 면적 균형을 위한 휴리스틱을 더하여, 여러 FPGA에 회로를 나눌 때 필요한 핀과 FPGA 수를 줄이는 방향으로 응용합니다. 여기서 복제는 공짜가 아닙니다. 연결 비용 감소와 면적 증가를 함께 보아야 합니다.

이어지는 연구는 초기 분할을 반드시 주어야 하는 상황에서 더 나아가 분할과 복제를 동시에 계산합니다. 자료에서 최적 알고리즘으로 설명하는 출발 조건은 두 단자 네트와 면적 제약이 없는 경우이고, 여러 단자 네트와 면적 균형에는 휴리스틱 확장을 덧붙입니다. ‘최적’이라는 말 옆에 어떤 조건이 붙는지 읽어야 한다는 교훈이 여기서도 반복됩니다.

또 FBB의 다중 분할 확장은 면적뿐 아니라 핀 제약도 함께 다룹니다. 반복적인 최대유량 계산으로 두 제약을 만족하는 셀 집합을 찾고, 한 FPGA에 넣을 수 있는 면적을 크게 하여 사용 FPGA 수를 줄이려 합니다. 복제 문제에서도 목적함수를 구별해야 합니다. 절단 비용을 최소화했다고 해서 복제한 셀 수까지 최소인 것은 아닙니다. 자료는 복제 면적까지 고려하는 min-area min-cut replication과 더 간결한 하이퍼그래프 유량 모델을 소개하고, 마지막에는 시간을 나누어 논리를 사용하는 동적 재구성 FPGA에서 여러 단계 사이의 통신을 줄이는 temporal logic replication으로 이어집니다.

이제 첫 질문으로 돌아갑시다. “회로를 반으로 나누는 데 왜 이렇게 다양한 알고리즘이 필요할까요?” 무엇을 정확히 보존하는 모델을 쓰는지, 어떤 후보를 탐색하는지, 어떤 제약을 언제 적용하는지가 다르기 때문입니다.