게이트가 아주 많은 회로를 하나 받았습니다. 어디에 배치할지, 어떻게 여러 영역으로 나눌지 결정해야 합니다. 그런데 처음부터 모든 게이트를 개별적으로 다루면 문제의 규모가 너무 큽니다. 서로 관련 있는 게이트들을 먼저 작은 묶음으로 만들면 어떨까요?

클러스터링은 게이트들을 묶고, 그 묶음 사이의 연결로 새로운 회로 네트워크를 만드는 일입니다. 회로 분할과 배치의 전처리로 사용되어 이후에 풀 문제를 작게 만들어 줍니다. 다만 단순히 정점 수만 줄이면 끝나는 것은 아닙니다. 어떤 게이트를 함께 묶느냐에 따라 묶음 사이의 연결 수와 경로 지연이 달라집니다.

또 하나 구분합시다. 클러스터링 자체에서는 만들 클러스터의 개수가 미리 정해져 있지 않고, 클러스터끼리 면적이 비슷해야 한다는 조건도 보통 요구하지 않습니다. 뒤에서 등장할 균형 이분할은 두 영역의 크기를 비슷하게 만드는 문제입니다. 따라서 “클러스터링을 전처리로 사용한다”와 “클러스터링 단계부터 모든 묶음의 크기를 균등하게 맞춘다”는 같은 말이 아닙니다.

앞의 둘은 지연 중심, 마지막은 컷 크기 중심이라는 차이를 기억하세요. 이번 강의에서 실제로 배우는 것은 세 알고리즘의 이름이 아닙니다. 회로를 그래프나 하이퍼그래프로 바꾸는 방법, 최적화 목적을 수식으로 표현하는 방법, 라벨이라는 요약 정보를 계산하는 방법, 정점 분리를 이용해 입력 수 제한을 네트워크 컷으로 바꾸는 방법, 그리고 작은 문제의 해를 다시 원래 회로의 해로 복원하는 방법입니다.

먼저 회로를 DAG, 즉 방향성 비순환 그래프로 보겠습니다. 화살표는 신호가 흘러가는 방향입니다. PI는 외부에서 신호가 들어오는 주입력, PO는 결과를 내보내는 주출력입니다. 우리의 관심은 어느 PI에서 출발하든 어느 PO에 도달하든, 그중 가장 늦게 도착하는 경로입니다. 평균적으로 빠른 회로가 아니라 가장 느린 경로가 가능한 한 빠른 회로를 찾습니다.

이제 알고리즘이 사용할 재료를 준비합시다. 원문의 라벨 l(v)는 여기서 읽기 쉽게 ℓ(v)라고 쓰겠습니다. 이것은 PI에서 v까지 도달하는 최대 지연을 요약한 값입니다. 또 하나 중요한 값이 Δ(x,v)입니다.

PDF 3쪽 그림 1.1을 보세요. PI는 a, b, c이고 PO는 k, l입니다. 모든 노드 지연은 1, 클러스터 사이의 지연 D는 3, 클러스터 크기 한도는 4입니다. 예를 들어 a→d에서는 a의 출력부터 재므로 Δ(a,d)=1입니다. b→e→g→i에서는 e, g, i의 지연만 더하여 Δ(b,i)=3입니다. b→e→g→i→k에서는 Δ(b,k)=4입니다.

    a b c d e f g h i j k l
a   0 0 0 1 0 1 0 0 2 0 3 0
b   0 0 0 1 1 0 2 0 3 3 4 4
c   0 0 0 0 1 0 2 1 3 3 4 4
d   0 0 0 0 0 0 0 0 1 0 2 0
e   0 0 0 0 0 0 1 0 2 2 3 3
f   0 0 0 0 0 0 0 0 1 0 2 0
g   0 0 0 0 0 0 0 0 1 1 2 2
h   0 0 0 0 0 0 0 0 0 1 2 2
i   0 0 0 0 0 0 0 0 0 0 1 0
j   0 0 0 0 0 0 0 0 0 0 1 1
k   0 0 0 0 0 0 0 0 0 0 0 0
l   0 0 0 0 0 0 0 0 0 0 0 0

전체 알고리즘은 두 단계입니다. 위상 순서로 라벨과 후보 클러스터를 계산한 뒤, 출력에서 입력 방향으로 필요한 클러스터를 만듭니다. 설계도를 모두 준비하되, 필요한 설계도만 골라 조립하는 셈입니다.

한도가 4라면 v도 한 자리를 쓰므로 다른 노드는 최대 세 개입니다. 왜 큰 값부터 넣을까요? 밖에 남겨 놓으면 큰 지연을 유발할 후보부터 안으로 들여오겠다는 생각입니다.

이제 선택을 끝낸 뒤의 라벨을 계산해야 합니다. 두 종류의 경로를 따로 봅니다.

이제 실제 숫자로 감각을 만들겠습니다. PDF의 비-PI 위상 순서는 d, e, f, g, h, i, j, k, l입니다. 처음에는 ℓ(a)=ℓ(b)=ℓ(c)=1입니다.

d부터 봅시다. G_d={a,b,d}입니다. ℓ_d(a)=1+1=2이고, ℓ_d(b)도 2입니다. d와 함께 a, b를 넣어도 크기가 3이므로 cluster(d)={a,b,d}가 됩니다. 안에 있는 두 PI가 만드는 값은 2이고, 밖에 남은 후보는 없습니다. 따라서 ℓ(d)=2입니다. 첫 계산에서는 아직 경계 통과 비용 D=3이 등장하지 않았습니다. 필요한 선행 노드를 전부 같은 클러스터에 넣었기 때문입니다.

e도 같은 구조입니다. b와 c를 함께 넣어 cluster(e)={b,c,e}, ℓ(e)=2입니다. f는 a만 필요하므로 cluster(f)={a,f}, ℓ(f)=2입니다. g에서는 b, c, e가 선행 노드입니다. b와 c에서는 1+2=3, e에서는 2+1=3이 나옵니다. g를 포함해 정확히 네 노드이므로 cluster(g)={b,c,e,g}, ℓ(g)=3입니다. h는 c와 함께 묶여 cluster(h)={c,h}, ℓ(h)=2입니다.

여기까지는 편안했습니다. 필요한 것을 모두 넣을 수 있었으니까요. 이제 i를 만나면 상황이 달라집니다. G_i={a,b,c,d,e,f,g,i}이므로, i 외에도 후보가 일곱 개나 됩니다. 그러나 빈자리는 세 개뿐입니다.

원문에서는 cluster(i)={i,g,e,c}를 선택합니다. 안의 PI c가 만드는 값은 l₁=4입니다. 밖에 남은 S={b,a,d,f}에서는 b의 값이 가장 크므로 l₂=4+3=7입니다. 따라서 ℓ(i)=7입니다. 6쪽 그림 1.3의 점선 경로는 네 노드의 지연 4와 한 번의 클러스터 경계 지연 3을 보여 줍니다. 숫자 7은 단순히 노드가 일곱 개라는 뜻이 아닙니다.

j도 유사합니다. b, c, e, g의 ℓ_j 값은 4이고, h의 값은 3입니다. 원문의 선택은 cluster(j)={b,e,g,j}입니다. 내부 PI b 때문에 l₁=4이고, 밖에 남은 c 때문에 l₂=4+3=7입니다. 따라서 ℓ(j)=7입니다. 여기서도 b 대신 c를 넣은 대안이 제시됩니다. 표에 적힌 동률 원소의 나열 순서보다, 실제로 선택한 집합과 그 집합이 만드는 값에 집중합시다.

이제 PO인 k를 봅시다. i와 j의 라벨이 7이므로 ℓ_k(i)=ℓ_k(j)=8입니다. b, c, e, g의 값은 5이고, a, d, f, h의 값은 4입니다. 따라서 원문은 가장 큰 두 후보 i, j와 값 5인 g를 넣어 cluster(k)={g,i,j,k}를 만듭니다.

이번에는 내부 PI가 없습니다. 그러므로 l₁=0입니다. 바깥에 남은 후보 중 최대 ℓ_k 값은 5이므로 l₂=5+3=8, 결국 ℓ(k)=8입니다. 여기서 내부 PI가 없다는 말은 입력이 없다는 뜻이 아닙니다. 이 클러스터는 다른 클러스터가 만들어 준 신호를 받아 동작합니다.

PO l에서는 j의 값이 8, b·c·e·g의 값이 5, h의 값이 4입니다. 원문은 cluster(l)={e,g,j,l}을 택합니다. 내부 PI는 없고, 바깥 최대값은 5이므로 ℓ(l)=8입니다.

7쪽 표 1.1의 후보 목록을 이제 실제 회로로 바꿉니다. 출력 집합 L={k,l}에서 시작합니다. k를 꺼내 cl(k)를 만들면, 바깥에서 이 클러스터로 신호를 넣는 노드는 f, d, e, h입니다. 8쪽 그림 1.4에서 회색으로 표시된 노드들입니다. 이들을 새 작업 대상으로 등록합니다. l의 클러스터를 만들 때에는 입력 노드 b, c, h가 추가됩니다.

원문 순서대로 f, d, e, h, b, c를 처리하면 작업 집합이 빕니다. 만들어지는 클러스터의 뿌리는 k, l, f, d, e, h, b, c, 총 여덟 개입니다. 각 구성은 앞의 표에서 해당 행을 가져오면 됩니다. 특히 PI b와 c도 이 일반 지연 모델의 복원 예제에서는 단독 클러스터로 등장합니다. 뒤의 FlowMap에서는 PI를 LUT로 만들지 않으므로 이 차이를 기억해 두세요.

최대 지연은 8입니다. 9쪽 그림 1.5의 c→e→g→i→k나 c→e→g→j→l이 그 예입니다. 노드 지연 합 5에 한 번의 클러스터 경계 비용 3을 더하면 8입니다. 라벨과 실제 경로의 시간이 일치합니다.

이제 제약을 바꿉시다. 앞에서는 내부 노드 수가 중요했다면, FlowMap에서는 클러스터 바깥에서 들어오는 서로 다른 입력을 몇 개까지 받아들일 수 있는가가 중요합니다. 이것이 핀 제약이고, K입력 LUT로 FPGA 회로를 매핑하는 문제에 해당합니다.

“새로운 노드 t를 처리할 때, 앞선 노드보다 한 단계 더 깊어져야 할까?”

FlowMap은 이 질문을 반복합니다. t의 직접 fan-in 라벨 중 최댓값을 p라고 합시다. 목표는 t를 깊이 p 안에 수용할 수 있는지 확인하는 것입니다. 가능하면 ℓ(t)=p, 불가능하면 ℓ(t)=p+1로 정합니다. 이미 p에 있는 중요한 앞부분을 t와 함께 묶을 수 있다면, 경계를 하나 더 만들지 않고 기존 깊이를 유지할 수 있다는 생각입니다. 저장할 클러스터는 원문의 표기대로 X̄_t라고 부르겠습니다.

실습 회로는 각 게이트의 입력이 최대 두 개인 2-bounded 네트워크이고, K=3입니다. 따라서 깊이 p를 유지하는 데 실패해도 t만 새 LUT로 만들면 직접 입력 수가 핀 제약을 넘지 않습니다. 이것이 이 예제에서 p+1이라는 다음 선택지를 사용할 수 있는 이유입니다. 처음부터 아무 입력 제한도 없는 게이트에 같은 주장을 적용하는 것은 아닙니다.

그러면 남은 문제는 하나입니다. “깊이를 유지하면서 외부 입력을 K개 이하로 제한할 수 있는가?” FlowMap은 이 질문을 네트워크 컷 문제로 바꿉니다.

왜 보통 간선을 모두 용량 1로 두면 안 될까요?

우리가 세려는 것은 원래 회로의 선 개수가 아니라, 클러스터가 외부로부터 받아야 하는 입력 노드의 수이기 때문입니다. 하나의 신호가 안쪽 여러 곳으로 퍼진다고 해서 서로 다른 외부 입력이 여러 개 생기는 것은 아닙니다. 정점 하나를 통과하는 비용을 1로 표현하려고 그 정점을 둘로 나눈 것입니다.

원문은 증가 경로를 찾는 방식으로 이를 판정합니다. 단위 유량을 기준으로 K를 초과하는 흐름을 확보하면, 컷 용량이 K 이하일 수 없으므로 해당 판정을 끝낼 수 있습니다. 가능한 컷이 여러 개라면 ‘높이’도 봅니다. 컷 C(X, X̄)에서 X는 소스 쪽이고, 컷의 높이는 그쪽 회로 노드들의 라벨 중 최댓값입니다. 원문은 K-feasible cut 중 최소 높이를 선택한다고 설명합니다. 따라서 컷 크기와 컷 높이는 서로 다른 숫자입니다.

이런 입력 경계를 정리하여 X̄_t를 얻고 ℓ(t)=p로 정합니다. 컷이 없으면 X̄_t={t}, ℓ(t)=p+1입니다. 결국 유량 계산은 깊이를 유지하면서 외부 입력 신호를 K개 이하로 제한할 수 있는지 판정하는 장치입니다.

a에서 시작합시다. 직접 입력인 PI들의 라벨은 0이므로 p=0입니다. 이들을 a로 축약하면 그림 1.7처럼 s에서 a로 가는 무한 용량 연결이 남습니다. 용량 3 이하로 자르는 컷은 없습니다. 따라서 X̄_a={a}, ℓ(a)=1입니다. b, c도 같은 이유로 자기 자신만 저장하고 라벨은 1입니다.

d에서는 p=1입니다. 13쪽 그림 1.8에서 a와 d를 함께 처리하고 바깥 PI 세 개를 입력으로 삼는 컷을 얻습니다. 컷 크기는 3이고, 소스 쪽 라벨의 최댓값은 0입니다. 따라서 X̄_d={a,d}, ℓ(d)=1입니다. a 다음에 d가 있다고 해서 반드시 라벨이 2가 되는 것은 아닙니다. 같은 LUT 안에 흡수할 수 있기 때문입니다.

e는 단독으로 라벨 1을 얻습니다. f는 c와 함께 묶여 X̄_f={c,f}, 라벨 1입니다. g도 X̄_g={c,g}, 라벨 1이고, 그림 1.9에서 외부 입력이 두 개로 정리됩니다. h에서는 a, d, h를 함께 묶을 수 있어 X̄_h={a,d,h}, 라벨은 여전히 1입니다. 세 게이트를 지나가는 원래 경로라도 하나의 LUT로 구현되면 이 모델의 깊이는 한 단계입니다.

이제 i가 전환점입니다. p=1인 상태에서 b, c, f를 i 쪽으로 축약합니다. 14쪽 그림 1.11의 유량 그래프를 보면 다섯 PI를 통하는 다섯 개의 단위 용량 통로가 남습니다. K=3으로는 이들을 모두 분리할 수 없습니다. 따라서 깊이 1을 유지하지 못하고 X̄_i={i}, ℓ(i)=2가 됩니다.

j는 어떨까요? 이제 p=2입니다. i를 j와 함께 넣고, 바깥의 e, b, f를 입력으로 받는 컷을 찾을 수 있습니다. 그러므로 X̄_j={i,j}, ℓ(j)=2입니다. k도 i와 함께 묶고 b, f, g를 입력으로 받으면 되어 X̄_k={i,k}, ℓ(k)=2입니다. 두 컷의 높이는 모두 1입니다.

짧게 정리하면 a부터 h까지 라벨은 1, i·j·k는 2입니다. 그러나 같은 라벨을 가졌다고 저장된 클러스터도 같은 것은 아닙니다. 라벨은 도착 깊이라는 요약값이고, 클러스터는 그 값을 달성하는 구체적인 구현 정보입니다.

출력 L={h,j,k}에서 필요한 입력을 거슬러 올라가며 실제 LUT 네트워크를 만들겠습니다. 다만 FlowMap은 저장된 클러스터의 비-PI 노드들을 LUT로 만들고, PI 자체는 LUT로 만들지 않습니다.

먼저 h를 꺼냅니다. h′={a,d,h}이고, 입력은 세 PI입니다. PI를 작업 집합에 넣지 않으므로 다음 작업은 j와 k뿐입니다. j를 꺼내면 j′={i,j}, 입력은 {e,b,f}입니다. k를 꺼내면 k′={i,k}, 입력은 {b,f,g}입니다. 두 LUT가 같은 입력을 요구할 수 있으므로 작업 집합에서는 중복을 관리해야 합니다. 남은 e, b, f, g를 처리하면 각각 e′={e}, b′={b}, f′={c,f}, g′={c,g}입니다. 모든 입력이 PI까지 연결되었으므로 복원이 끝납니다.

총 일곱 개의 LUT입니다. 표에서 같은 원래 노드가 어디에 두 번 나타나는지 찾아보세요. c는 f와 g의 LUT 안에, i는 j와 k의 LUT 안에 나타납니다. 이 둘이 복제됩니다.

최대 지연은 2입니다. h는 한 단계에서 끝나지만, j와 k 쪽은 앞단 LUT의 결과를 받아 두 단계에서 끝납니다. 여기서 지연 최적이라는 말이 LUT 개수까지 최소라는 뜻은 아닙니다. 이 알고리즘의 중심 목적은 깊이이고, 면적을 나타내는 LUT 개수는 별개의 관심사입니다. 뒤에서 소개할 후속 연구들이 바로 이 차이를 파고듭니다.

세 번째 주제로 넘어갑시다. 이제는 최장 지연 대신, 크기가 대략 같은 두 영역 사이를 가로지르는 연결 수를 줄이려 합니다. 여기서는 클러스터링이 최종 목적이라기보다 좋은 분할을 만들기 위한 계층적 준비 작업입니다.

여기서는 그래프 대신 하이퍼그래프가 등장합니다. 한 넷이 여러 게이트를 함께 연결하므로, 넷 하나를 여러 정점을 포함하는 hyperedge 하나로 표현합니다. 20쪽 그림 1.16의 예제는 다음 여섯 넷으로 이루어집니다.

n1 = {a, c, e}    n2 = {b, c, d}    n3 = {c, e, f}
n4 = {d, f}       n5 = {e, g}       n6 = {f, g, h}

이제 EC, HEC, MHEC라는 세 방법으로 같은 네트워크를 묶어볼 것입니다. EC는 정점의 짝을 찾고, HEC는 하이퍼에지 전체를 묶으며, MHEC는 HEC가 놓친 남은 정점들을 한 번 더 처리합니다. 세 결과를 비교할 때는 클러스터 수와 남은 하이퍼에지 수를 따로 보세요. 더 적은 클러스터가 반드시 더 적은 연결을 뜻하지는 않습니다.

EC에서는 먼저 모든 정점을 미표시 상태로 둡니다. 방문한 미표시 정점 v에 대해 같은 하이퍼에지를 공유하는 미표시 이웃들을 찾고, 가장 큰 연결 가중치를 가진 이웃과 짝지어 합칩니다. 합친 두 정점은 표시하여 같은 단계에서 다시 묶이지 않게 합니다.

n1 → {C1, C3}          n2 → {C1, C2}
n3 → {C1, C3, C4}      n4 → {C2, C4}
n5 → 삭제 (내부 넷)       n6 → {C3, C4}

결과: 클러스터 4개 · 하이퍼에지 5개

예를 들어 n1={a,c,e}는 처음에는 {C1,C1,C3}으로 바뀌고, 중복을 제거하여 {C1,C3}이 됩니다. n5={e,g}는 {C3,C3}이므로 내부 넷이 됩니다. 여기서 삭제는 원래 회로의 논리적 연결을 없앤다는 뜻이 아니라, 축약된 외부 연결 목록에서 내부 넷을 제외한다는 뜻입니다.

HEC는 출발점이 다릅니다. 정점마다 짝을 찾는 대신 하이퍼에지를 방문합니다.

예제의 순서는 n4, n5, n1, n2, n3, n6입니다. 먼저 n4={d,f}로 C1을 만들고, n5={e,g}로 C2를 만듭니다. 그다음 n1에는 e, n2에는 d가 이미 표시되어 있으므로 넘어갑니다. n3에는 e와 f, n6에는 f와 g가 이미 표시되어 있습니다. 결국 a, b, c, h가 남아 각각 C3={a}, C4={b}, C5={c}, C6={h}가 됩니다.

n1 → {C3, C5, C2}      n2 → {C4, C5, C1}
n3 → {C5, C2, C1}      n4 → 삭제 (내부 넷)
n5 → 삭제 (내부 넷)       n6 → {C1, C2, C6}

결과: 클러스터 6개 · 하이퍼에지 4개

“n1의 e가 이미 사용되었다고 해서, 아직 남은 a와 c까지 따로 놓아둘 필요가 있을까요?” MHEC는 바로 이 지점을 바꿉니다.

먼저 HEC 방식으로 통째로 묶을 수 있는 하이퍼에지를 선택합니다. 그다음 같은 정렬 순서로 하이퍼에지를 다시 방문하고, 앞에서 처리하지 못한 하이퍼에지에 남은 미표시 정점들을 함께 묶습니다.

예제에서는 C1={d,f}, C2={e,g}가 먼저 정해집니다. 이제 건너뛴 n1={a,c,e}를 다시 보세요. e는 표시되었지만 a와 c는 남아 있으므로 C3={a,c}로 묶습니다. n2={b,c,d}에서는 이제 b만 남았으므로 C4={b}입니다. n3은 모두 표시되어 넘어갑니다. n6={f,g,h}에서는 h만 남아 C5={h}가 됩니다.

n1 → {C3, C2}          n2 → {C4, C3, C1}
n3 → {C3, C2, C1}      n4 → 삭제 (내부 넷)
n5 → 삭제 (내부 넷)       n6 → {C1, C2, C5}

결과: 클러스터 5개 · 하이퍼에지 4개

원문은 MHEC가 넷 수를 더 줄이고 클러스터 크기를 균형화하는 경향을 설명합니다. 다만 이 예제에서는 HEC보다 정점 수만 줄고 넷 수는 같습니다. 이러한 경향을 모든 입력에서 엄격하게 넷 수가 감소한다는 보장으로 바꾸어 읽으면 안 됩니다.

25~26쪽의 일곱 문제는 앞의 답을 외웠는지 확인하는 문제가 아닙니다. 어떤 조건이 바뀌었고 그 조건이 계산의 어느 부분에 영향을 주는지 묻습니다.

두 번째 문제는 제시된 회로에 D=3, 크기 한도 3, 단위 노드 지연을 적용합니다. 세 번째는 그림 1.6을 K=4인 LUT로 매핑하고, 네 번째는 그림 1.20의 새 회로를 3-LUT로 매핑합니다.

다섯 번째는 가중 HEC입니다. 넷 가중치는 n1부터 순서대로 5, 2, 3, 3, 1, 5입니다. 정렬 규칙을 직접 적용하면 n1·n6가 먼저이고, 가중치 3끼리는 크기 2인 n4가 크기 3인 n3보다 먼저입니다. 같은 가중치와 크기에서는 넷 번호 순서를 택하면 전체 순서는 n1, n6, n4, n3, n2, n5입니다. 이 순서에서 직접 묶어보면 {a,c,e}, {f,g,h}가 먼저 선택되고, b와 d는 단독으로 남습니다.

여섯 번째는 그림 1.17(b)에 EC를 다시 적용합니다. 이제 C1부터 C4까지가 새 정점입니다. ‘클러스터를 다시 클러스터링한다’는 다단계 개념을 직접 실행하는 문제입니다. 일곱 번째의 새 네트리스트는 다음과 같습니다.

n1 = {a, b, d, e}   n2 = {b, d, f}     n3 = {a, e, g}
n4 = {c, e, f, h}   n5 = {c, g}        n6 = {a, d, f, h}

EC는 알파벳 순서로 방문하고 동률을 처리합니다. 반면 HEC와 MHEC의 동률은 무작위로 처리하라고 되어 있습니다. 따라서 마지막 두 방법의 결과를 비교할 때에는 동률 선택도 함께 기록해야 합니다. 원문이 무작위를 허용한 자리에 임의의 유일 정답을 만들어 놓으면 안 됩니다.

이제 ‘Probing Further’에 실린 연구 흐름을 보겠습니다. 이름을 외우기보다 기존 문제에 무엇이 추가되는지 따라가세요.

깊이를 잘 줄였는데 LUT가 너무 많다면 어떨까요? 깊이는 같지만 실행 시간이 너무 오래 걸린다면 어떨까요?

DAOmap은 CutMap 대비 면적과 실행 시간 개선을 보고하지만, 이것을 모든 회로와 구현에 대한 보편적인 우열로 확대하지는 맙시다. priority cuts는 노드마다 하나의 컷만 저장해도 평가한 벤치마크와 LUT 크기 조합의 95%에서 깊이 최적해를 얻었고, 메모리와 실행 시간은 회로 크기에 선형이라고 설명합니다. 95%는 실험 결과이지 모든 입력에 대한 최적성 증명이 아닙니다.

HPM은 같은 계층 안에서도 모든 수준에 똑같은 목적을 적용할 필요가 없다는 사례입니다. Hwang–Pedram은 IO 경로의 지연을 악화시키는 역방향 연결을 구분해서 봅니다. 같은 컷 한 개라도 어느 방향인지, 어떤 경로에 놓였는지에 따라 중요도가 달라질 수 있습니다.

다시 첫 시간의 질문입니다. “회로를 묶는다는 것은 무엇을 최적화하는 일일까?”

답은 목적과 제약에 달려 있습니다. Rajaraman–Wong은 일반 지연 모델과 크기 제한 아래에서 ℓ_v(x)=ℓ(x)+Δ(x,v)를 계산하고 내부·외부 경로의 최대를 비교했습니다. FlowMap은 입력 수 K를 제한하면서 네트워크 컷으로 깊이 p를 유지할 수 있는지 판단했습니다. 둘 다 라벨과 후보를 먼저 계산한 뒤 출력에서 필요한 부분을 복원했고, 복제를 허용했습니다. 다단계 코어스닝은 연결을 내부화하며 문제를 작게 만든 뒤, 분할한 해를 펼치며 개선했습니다. EC는 짝을, HEC는 하이퍼에지 전체를, MHEC는 그 뒤의 남은 정점들을 묶었습니다.