FLOORPLANNING — 배치를 표현하고, 계산하고, 개선하는 네 가지 방법
배치를 표현하고,
계산하고, 개선하는 법
크기가 다른 직사각형 여덟 개를 겹치지 않게 놓고, 전체를 감싸는 사각형을 최대한 작게 만듭니다. 어디에 놓을지 묻기 전에 먼저 물어야 할 질문이 있습니다 — 배치 하나를 컴퓨터 안에서 어떻게 표현할 것인가.
큰 그림: 오늘 배우는 것은 ‘사각형을 놓는 요령’이 아니다REPRESENT · EVALUATE · SEARCH
크기가 서로 다른 직사각형 여덟 개를 받았습니다. 겹치지 않게 놓으면서 전체 외곽을 최대한 작게 만들고 싶습니다. 어떤 것은 돌릴 수 있고, 어떤 것은 면적을 유지하면서 길쭉하게 만들 수도 있습니다. 게다가 사각형끼리 전선으로 연결되어 있어서, 공간만 아낀다고 좋은 답이 되지도 않습니다. 어디서부터 시작하시겠습니까?
Floorplanning의 입력은 블록들과 연결 관계인 netlist이고, 출력은 위치와 — 유연한 블록이라면 — 폭·높이까지입니다. 교재는 전통적인 목표로 면적과 배선 길이를, 추가 고려 사항으로 열 집중과 전원 잡음을 언급합니다. 고정된 외곽선, 미리 배치된 블록, 정렬 조건 같은 제약도 등장합니다. 다만 이번 장의 네 가지 핵심 방법은 주로 면적과 배선 길이를 다룹니다.
“어디에 놓으면 좋을까?”보다 먼저 “배치 하나를 컴퓨터 안에서 어떻게 표현할까?”를 물어야 합니다. 표현이 정해져야 후보 생성, 비용 계산, 이웃 후보로의 이동이 가능하기 때문입니다.
자르는 구조가 이미 정해진 배치에서 블록의 회전 방향을 골라 면적을 최소화합니다. 트리 위에서 가능한 폭·높이를 아래에서 위로 합칩니다.
Normalized Polish Expression은 자르는 구조를 문자열로 표현합니다. 문자열을 조금 바꾸면 새 후보가 생기고, 여기에 simulated annealing을 붙입니다.
위치·회전·상대 방향을 변수로 놓고 비겹침 조건을 부등식으로 적습니다. “원래 문제”가 “풀 수 있는 모델”이 될 때 무엇이 달라지는지가 관전 포인트입니다.
두 개의 순열로 블록 간 상대 위치를 표현합니다. 좌표 복원은 놀랍게도 제약 그래프의 최장경로 문제로 바뀝니다.
오늘 내내 다음 세 질문을 붙잡아 주세요. 지금 고정된 것은 무엇인가? 지금 탐색하는 것은 무엇인가? 지금 말하는 ‘최적’은 어느 범위 안에서의 최적인가? 같은 ‘면적 최소화’라는 표현 아래에도 서로 다른 문제가 숨어 있습니다.
핵심 O/X 퀴즈
1. Floorplanning에서는 유연한 블록의 위치뿐 아니라 폭과 높이도 결정할 수 있다.
2. Stockmeyer 알고리즘과 NPE는 모두 동일한 배치 변수만 최적화하는 방법이다.
3. 이번 장을 이해하려면 배치의 표현, 평가, 탐색을 구분하는 것이 중요하다.
Slicing tree: 왜 작은 면적 하나만 남기면 안 될까DIMENSION LIST & DOMINANCE
큰 직사각형을 수평선이나 수직선으로 두 영역으로 나누고, 각 영역을 다시 나눕니다. 이렇게 재귀적으로 만들어지는 구조가 slicing tree입니다. 잎은 실제 블록이고, 내부 노드는 두 하위 배치를 합치는 절단 방향입니다.
xHy는 x가 위, y가 아래입니다. xVy는 x가 왼쪽, y가 오른쪽입니다. 여기서 V는 ‘위아래로 놓는다’는 뜻이 아닙니다. 절단선이 수직이므로 결과가 좌우로 나뉘는 것입니다. 각 블록은 자신에게 배정된 방의 왼쪽 아래 모서리에 놓습니다. (책 65쪽 그림 3.1)
두 하위 배치의 크기가 각각 (wl, hl), (wr, hr)라면 결합 결과는 이렇게 계산합니다.
H 결합 → ( max(wl, wr) , hl + hr ) 옆으로 붙이니 폭은 더하고 높이는 큰 쪽을 택합니다. 위아래로 쌓으니 높이는 더하고 폭은 큰 쪽을 택합니다.
회전을 허용하면 잎에도 선택지가 생깁니다. 크기가 (2,4)인 블록은 (4,2)로도 놓을 수 있습니다. 그렇다면 내부 노드에도 가능한 크기가 여러 개 생기겠지요.
“각 노드에서 최소 면적만 남기면 되지 않을까요?” 후보 (4,4)와 (7,2)를 비교해 봅시다. 면적은 16과 14이므로 두 번째가 좋아 보입니다. 그런데 높이 4·폭 1인 배치와 V로 합치면 앞의 후보는 (5,4)=20, 뒤의 후보는 (8,4)=32가 됩니다. 자식 단계에서 면적이 더 컸던 후보가 부모에서는 더 좋습니다. (결합식의 의미를 보이기 위해 여기서 만든 예입니다.)
따라서 보존할 것은 ‘면적 최솟값 하나’가 아니라 폭과 높이 사이의 유효한 교환 관계입니다. 폭도 더 크고 높이도 더 큰 후보는 더 작은 후보보다 유리해질 수 없습니다. 반대로 폭은 작지만 높이가 크다면 어느 쪽이 유리한지는 부모 구조에 달려 있으므로 함부로 버릴 수 없습니다.
이 관점으로 보면 Stockmeyer의 dimension list가 이해됩니다. 각 부분 트리는 부모에게 “나는 이런 모양들 중 하나로 실현될 수 있습니다”라는 목록을 올려보내는 것입니다. 아직 최종 선택을 하지 않는다는 점을 기억해 주세요.
핵심 O/X 퀴즈
1. V 결합에서는 폭을 더하고 높이는 최댓값을 취한다.
2. 각 부분 트리에서 면적이 최소인 후보 하나만 남겨도 항상 전체 최적해를 얻는다.
3. 한 후보가 다른 후보보다 폭과 높이가 모두 크다면, 위 결합식 아래에서 유리할 이유가 없다.
Stockmeyer의 핵심: 모든 조합을 만들지 않는 이유WHY O(L+R), NOT O(L×R)
왼쪽 자식에게 후보가 L개, 오른쪽 자식에게 R개 있다면 모든 조합 확인에 L×R의 시간이 들 것 같습니다. 그런데 교재는 필요한 결합이 O(L+R) 규모라고 설명합니다. 어떻게 곱을 합으로 바꾸는 걸까요?
V 결합부터 봅시다. 양쪽 목록을 폭이 증가하고 높이가 감소하는 순서로 정렬합니다. 앞으로 갈수록 더 넓고 더 낮은 모양이 나옵니다. 두 포인터를 각각 첫 후보에 놓고 현재 두 후보를 합칩니다.
이때 왼쪽 높이가 오른쪽보다 크다고 합시다. 결과 높이는 왼쪽이 결정합니다. 여기서 오른쪽 포인터만 전진시키면? 오른쪽 폭은 커지고 높이는 작아지지만 전체 높이는 여전히 왼쪽 높이입니다. 높이는 그대로인데 폭만 증가하는 후보가 만들어집니다. 일부러 만들 필요가 없습니다.
현재 최댓값을 결정하는 쪽을 전진시킵니다. V에서는 더 높은 쪽, H에서는 더 넓은 쪽입니다. 높이(폭)가 같으면 둘을 함께 전진시킵니다. 한쪽만 낮춰서는 다른 쪽 값이 그대로 남기 때문입니다.
| 단계 | 왼쪽 | 오른쪽 | 결합 결과 | 높이 결정 | 다음 전진 |
|---|---|---|---|---|---|
| 1 | (2,3) | (2,4) | (4,4) | 오른쪽 4 | 오른쪽 → |
| 2 | (2,3) | (4,2) | (6,3) | 왼쪽 3 | 왼쪽 → |
| 3 | (3,2) | (4,2) | (7,2) | 동률 2 | 종료 |
최종 목록은 (4,4), (6,3), (7,2)입니다. 전진해야 할 목록이 끝나면 멈춥니다. 반대쪽만 바꿔서는 최대 높이가 줄지 않고 폭만 늘기 때문입니다.
H 결합은 완전히 대칭적입니다. 이번에는 폭이 감소하고 높이가 증가하는 순서로 목록을 읽고, 합친 결과의 폭을 누가 결정하는지 봅니다. 규칙을 암기하기보다 “지금 max를 줄이려면 어느 쪽을 바꿔야 하지?”라고 물어보세요. 각 포인터가 한 방향으로만 움직이므로 필요한 단계 수는 두 목록의 길이를 더한 정도입니다.
핵심 O/X 퀴즈
1. V 결합에서 왼쪽 높이가 더 크다면 왼쪽 목록의 포인터를 전진시킨다.
2. H 결합에서도 다음 후보는 항상 높이가 큰 쪽에서 선택한다.
3. 선형 결합이 가능한 이유는 두 목록의 모든 원소 쌍을 검사하기 때문이다.
실습: 여덟 블록을 합쳐 면적 117까지BOTTOM-UP, TABLE 3.1
그림 3.1의 트리를 실제로 계산합니다. 블록 1~8의 원래 크기는 순서대로 (2,4), (1,3), (3,3), (3,5), (3,2), (5,3), (1,2), (2,4)입니다. 회전은 허용, 트리 구조는 고정 — 이 두 조건을 따로 기억해 주세요.
노드 연결을 말로 읽겠습니다. a는 블록 5와 1의 V 결합, b는 블록 8과 2의 H 결합입니다. c는 a와 b의 V, d는 c와 블록 4의 V, f는 d와 블록 6의 V입니다. 다른 가지에서 e는 블록 3과 7의 H이고, 루트 g는 e와 f의 H 결합입니다.
| 노드 | 결합 | 자식 | 후보 목록 |
|---|---|---|---|
| a | V | 5 · 1 | (4,4) (6,3) (7,2) |
| b | H | 8 · 2 | (4,3) (3,5) (2,7) |
| c | V | a · b | (6,7) (7,5) (8,4) (10,3) |
| d | V | c · 4 | (9,7) (10,5) (13,4) (15,3) |
| f | V | d · 6 | (12,7) (13,5) (18,4) (20,3) |
| e | H | 3 · 7 | (3,4) |
| g | H | e · f | (20,7) (18,8) (13,9) (12,11) |
c에서 실수하기 쉽습니다. b는 H로 만든 목록이므로 V 부모에서 쓰려면 순서를 뒤집어야 합니다 — (2,7), (3,5), (4,3). 부모의 결합 방향이 바뀌면 필요한 정렬 순서도 바뀝니다. 교재도 바로 이 반전을 강조합니다.
블록 4와 6은 원래 방향은 다르지만 회전을 허용하면 둘 다 {(3,5), (5,3)}이라는 같은 후보 집합을 갖습니다. e는 정사각형 블록 3 {(3,3)}과 블록 7 {(2,1),(1,2)}의 H 결합인데, 유효한 결과는 (3,4) 하나뿐입니다. 다른 결합은 폭을 줄이지 못하면서 높이만 늘립니다.
루트 g의 네 후보 면적은 각각 140, 144, 117, 132입니다. 따라서 선택할 루트 크기는 13×9, 면적 117입니다.
가장 좁은 후보는 12×11이지만 답은 13×9입니다. 폭 최소화와 면적 최소화는 다릅니다. 이제 루트의 선택을 만든 자식 후보를 거꾸로 따라가며 실제 방향을 복원해야 합니다.
핵심 O/X 퀴즈
1. H로 계산한 자식 목록을 V 부모에서 사용할 때는 필요한 정렬 순서를 다시 맞춰야 한다.
2. 루트에서 폭이 가장 작은 후보가 반드시 면적도 가장 작다.
3. 이 실습에서 주어진 slicing 구조의 최소 면적은 117이다.
위에서 아래로: 면적을 구하는 것과 해를 복원하는 것은 다르다TOP-DOWN TRACEBACK
“최소 면적은 117입니다”라는 숫자를 얻었습니다. 그런데 설계 도구가 숫자만 출력하면 쓸 수 있을까요? 실제로 어떤 블록을 돌리고 어디에 놓아야 하는지 알아야 합니다. 그래서 Stockmeyer는 아래에서 위로 계산한 다음, 위에서 아래로 선택을 복원합니다.
원래 크기와 비교하면 회전하는 블록은 2, 5, 6, 7입니다 (교재 69쪽 그림 3.2의 어둡게 표시된 블록). 부모 후보를 만들 때 사용한 자식 후보 둘을 연결해 두면 이렇게 해를 복원할 수 있습니다. 정답의 값과 그 값을 구성하는 선택은 별개의 정보입니다.
좌표도 같은 방식으로 내려보냅니다. V에서는 오른쪽 방의 시작 x좌표가 왼쪽 방의 폭만큼 이동하고, H에서는 위쪽 방의 시작 y좌표가 아래쪽 방의 높이만큼 이동합니다. 여기에 블록을 방의 왼쪽 아래에 놓는 약속을 적용합니다. 이 규칙으로 계산하면 블록 8의 좌표는 (4, 1)입니다 — b가 폭 4인 a의 오른쪽에 있고, b 안에서 블록 8이 높이 1인 블록 2 위에 있기 때문입니다.
- 전체
- 시간·공간 모두 O(n · d), d는 트리 깊이. 후보 정보가 여러 조상 단계에서 다시 처리되기 때문입니다.
- 균형 트리
- O(n log n)
- 치우친 트리
- 최악 O(n²)
- 최적성 범위
- 오늘 얻은 최적성은 주어진 slicing floorplan의 방향 선택에 대한 것입니다. 모든 배치 구조를 통틀어 117이 전역 최적이라는 뜻은 아닙니다. non-slicing floorplan의 최적 방향 문제는 NP-complete입니다.
핵심 O/X 퀴즈
1. 루트의 최적 크기를 고른 다음, 그 크기를 만든 자식 선택을 추적해야 실제 방향을 복원할 수 있다.
2. 이번 예제에서 블록 2, 5, 6, 7이 회전한다.
3. Stockmeyer의 원래 알고리즘은 트리 모양과 무관하게 항상 O(n log n)이다.
NPE: 배치 구조를 계산 가능한 문자열로POLISH EXPRESSION
“주어진 트리 자체가 별로라면?” 회전만으로 낭비를 줄일 수 없다면 블록의 그룹과 절단 방향도 바꿔야 합니다. 그때 사용할 언어가 Normalized Polish Expression입니다.
Polish expression은 slicing tree의 후위 순회 결과입니다. 왼쪽 부분 트리, 오른쪽 부분 트리, 부모 연산자 순서로 읽습니다. 블록 번호는 operand, H와 V는 operator입니다. 블록이 n개면 피연산자 n개, 이진 결합 연산자 n−1개이므로 전체 길이는 2n−1입니다.
1 2 V는 1을 왼쪽, 2를 오른쪽으로 결합합니다. 여기에 3 H를 붙인 1 2 V 3 H는 앞서 만든 좌우 배치를 위에, 블록 3을 아래에 놓습니다.
- 유일 등장
- 모든 블록이 정확히 한 번씩 등장합니다.
- balloting
property - 문자열의 어느 비어 있지 않은 앞부분을 보더라도 피연산자 수가 연산자 수보다 많아야 합니다.
- normality
property - 같은 종류의 연산자가 연속해서 나오면 안 됩니다. HH·VV는 불가, HV·VH는 가능합니다.
왜 피연산자가 더 많아야 할까요? 스택으로 읽으면 쉽습니다. 숫자를 만나면 부분 배치 하나를 넣고, 연산자를 만나면 둘을 꺼내 합친 뒤 다시 넣습니다. 연산자는 스택 크기를 하나 줄입니다. 즉 “피연산자 수 − 연산자 수”가 현재 만들어 둔 부분 배치의 개수입니다. 1 H 2는 H가 나오는 순간 합칠 두 대상이 없어 실패합니다.
반면 1 2 3 H H는 이진 결합 자체는 가능하지만 HH가 연속하므로 정규화 조건에 실패합니다. “읽을 수 있는 표현”과 “정규화된 표현”은 다릅니다. 정규화는 같은 slicing 구조를 불필요하게 여러 방식으로 다루는 일을 줄이는 장치이고, 교재는 NPE와 slicing floorplan 사이의 1대1 대응을 설명합니다.
이제 실습 표현을 읽겠습니다. 이번에는 회전이 금지입니다. 같은 여덟 블록이지만 각 잎의 크기는 하나뿐입니다.
PE₁ = 2 5 V 1 H 3 7 4 V H 6 V 8 V H핵심 O/X 퀴즈
1. 블록 n개를 나타내는 Polish expression에는 H와 V가 합쳐서 n−1개 등장한다.
2. Balloting property만 만족하면 반드시 normalized Polish expression이다.
3. 1 2 3 H H는 결합 계산은 가능하지만 normality property를 위반한다.
세 가지 move: 구조를 바꾸되 전부 다시 계산하지 않기M1 · M2 · M3
- M1
- 인접한 피연산자의 교환.
- M2
- 연산자 chain의 H와 V를 뒤집는 complementation. chain은 연속한 연산자들의 묶음입니다.
- M3
- 인접한 피연산자와 연산자의 교환. balloting·normality 위반 여부를 반드시 검사해야 합니다.
M1 — PE₁에서 블록 3과 7을 바꿉니다. 트리의 결합 방향은 그대로이고 두 잎의 블록만 바뀝니다.
PE₂ = 2 5 V 1 H 7 3 4 V H 6 V 8 V Ha는 이제 블록 3과 4를 V로 합쳐 (6,5), b는 블록 7을 H로 합쳐 (6,7)입니다. c·d는 (11,7), (13,7)이고 루트 g는 (13,14), 면적 182 — 처음의 165보다 나빠졌습니다. 주목할 점은 갱신 범위입니다. a, b, c, d, g만 다시 계산하고, 변경된 잎과 무관한 e·f의 결과는 재사용합니다.
M2 — PE₂의 마지막 chain V H를 H V로 뒤집습니다. 두 절단 방향만 바뀝니다.
d는 (11,7)과 블록 8의 (2,4)를 H로 합쳐 (11,11), g는 (4,7)과 (11,11)을 V로 합쳐 (15,11)입니다. 면적은 다시 165. 새로 계산할 노드는 d와 g뿐입니다.
M3 — PE₃에서 인접한 6 V를 V 6으로 바꿉니다. 이번에는 어느 부분 배치들이 서로 결합하는지가 바뀝니다.
새 c는 (4,7)과 (6,7)을 V로 합쳐 (10,7), 새 d는 블록 6과 8을 H로 합쳐 (5,7)입니다. 루트는 두 배치를 V로 합쳐 (15,7), 면적 105. c, d, g만 갱신하면 됩니다.
블록의 총면적은 같아도 배치 구조에 따라 외곽 면적은 크게 바뀝니다 (교재 75쪽 그림 3.7). 그리고 결정적인 질문 하나 — 처음 나빠진 순간(182)에 멈췄다면 105까지 도달했을까요?
핵심 O/X 퀴즈
1. M2는 선택한 연산자 chain에서 H와 V를 서로 바꾸는 move이다.
2. M3는 문자열에서 인접한 두 기호를 바꾸므로 유효성 검사가 필요 없다.
3. Move 이후에는 변경의 영향을 받지 않는 부분 트리의 치수를 재사용할 수 있다.
Simulated annealing: 나쁜 이동을 왜 받아들이는가T₀ ≈ 297.39
산길을 걷고 있다고 생각해 보세요. 지금보다 낮은 곳으로만 이동한다면 작은 골짜기에서 빠져나오지 못합니다. 더 깊은 골짜기로 가려면 잠시 오르막을 지나야 할 수도 있습니다.
절차는 초기 표현 PE₀를 정하는 데서 시작합니다. 초기 온도와 최종 온도, 냉각 비율 r, 각 온도에서 수행할 move 수 Mt를 정합니다. 비용은 면적 A와 배선 길이 W의 가중합입니다.
각 단계에서 move 종류와 대상을 무작위로 고릅니다. 새 해가 더 좋으면 받아들이고, 더 나쁘면 온도에 의존하는 확률로 받아들입니다. 높은 온도에서는 나쁜 move의 수용 확률이 높고, 낮은 온도에서는 낮습니다. 한 온도에서 정해진 move 수를 수행한 다음 T를 rT로 낮춥니다 (r < 1).
현재 해와 최선의 해는 다릅니다. 현재 해는 탐색을 위해 일부러 나빠질 수 있습니다. Z는 발견한 좋은 결과를 잃지 않기 위한 기록입니다. 탐색이 끝나면 마지막 현재 해가 아니라 Z를 반환합니다.
이제 초기 온도를 계산해 봅시다. 앞선 세 move의 면적 변화는 165→182, 182→165, 165→105였습니다. 변화의 절댓값을 평균 내어 대표적인 변화 크기를 구합니다.
T₀ = − Δave / ln(0.9) ≈ 297.39 증가와 감소를 상쇄시키지 않습니다. 알고 싶은 것은 탐색 한 걸음의 전형적인 규모이기 때문입니다. 이 식은 대표 증가량의 수용확률을 e^(−Δ/T)로 놓고 T를 푼 형태이며, ln(0.9)가 음수이므로 온도는 양수가 됩니다.
0.9는 “모든 move를 정확히 90퍼센트 받아들인다”는 뜻이 아닙니다. 평균 변화 크기를 기준으로 초기 온도를 정한 것일 뿐이고, 실제 후보마다 비용 변화량이 다르며 개선 move는 그대로 받아들입니다. 또 이번 온도 계산은 면적만 사용합니다 — 이 실습에는 배선 길이를 계산할 netlist 정보가 주어지지 않았습니다.
핵심 O/X 퀴즈
1. Simulated annealing에서는 현재 해가 나빠지더라도 최선의 해 Z를 따로 보관할 수 있다.
2. 초기 온도를 구할 때 이 실습은 면적 변화의 부호 있는 평균을 사용한다.
3. 교재의 종료 조건에는 최종 온도 도달이나 충분히 낮아진 move 수용 정도가 포함된다.
ILP: ‘겹치지 않는다’를 네 개의 부등식으로 번역하기MIXED INTEGER MODEL
지금까지는 배치를 표현하고 움직였습니다. 이번에는 접근을 바꿉니다 — 원하는 조건을 수식으로 모두 적고, 그 수식을 만족하는 좋은 해를 찾습니다. 연속 변수와 정수 변수를 함께 쓰는 mixed integer linear programming이며, 구성 요소는 목적함수, 비겹침 제약, 변수 종류 제약, 칩 경계 제약입니다.
블록 i의 왼쪽 아래 좌표를 (xi, yi), 폭과 높이를 (wi, hi)라 합시다. 두 직사각형이 겹치지 않으려면 i가 j의 왼쪽·오른쪽·아래·위 중 적어도 한 방향으로 분리되어야 합니다. 문제는 이 조건이 ‘또는’으로 연결된다는 것입니다. 그래서 각 쌍에 이진 변수 xij, yij를 도입합니다.
xi − wj ≥ xj − W(1 − xij + yij)
yi + hi ≤ yj + H(1 + xij − yij)
yi − hj ≥ yj − H(2 − xij − yij) W와 H는 충분히 큰 완화 상수(폭·높이 상한)입니다. 교재의 비회전 예제는 W=20, H=23을 씁니다. 비트 조합에 따라 네 관계 중 하나를 강제하고 나머지 제약은 완화합니다.
- 00
- 첫 식이 xi + wi ≤ xj — i의 오른쪽 끝이 j의 왼쪽 끝을 넘지 못하므로 i는 j의 왼쪽.
- 01
- 셋째 식이 yi + hi ≤ yj — i는 j의 아래쪽.
- 10
- i는 j의 오른쪽.
- 11
- i는 j의 위쪽.
‘하나의 관계를 선택한다’는 말은 실제 배치에서 두 방향의 분리가 동시에 일어나면 안 된다는 뜻이 아닙니다. i가 j의 왼쪽이면서 아래쪽일 수도 있습니다. 비겹침을 보증할 관계 하나를 이진 변수로 선택하는 것뿐입니다. 부등식에 등호가 허용되므로 두 블록이 경계에서 맞닿는 것도 가능합니다.
목적함수는 더 조심해야 합니다. 원래 면적은 폭×높이이므로 비선형입니다. 개요에서는 폭을 제약으로 두고 높이를 최소화한다고 설명하지만, 이어지는 종횡비 1의 실습에서는 폭과 높이를 모두 같은 변수 y*로 제한합니다.
모듈이 네 개면 쌍은 여섯 개이므로 상대 위치 비트는 열두 개, 비겹침 부등식은 스물네 개입니다. 좌표용 연속 변수는 여덟 개이고 y*도 등장합니다. 크기가 커지면 왜 계산 부담이 늘어나는지 구조가 보이기 시작하지요.
핵심 O/X 퀴즈
1. xi는 좌표 변수이고 xij는 상대 위치를 선택하는 이진 변수이다.
2. 두 블록에 대해 이진 변수로 한 관계를 선택하면 실제 배치에서도 반드시 한 방향으로만 분리되어야 한다.
3. 실습의 min y*는 임의의 직사각형 면적 W×H를 직접 최소화하는 식과 동일하다.
ILP 실습: 모델의 최적해가 원래 면적의 최적해는 아닐 수 있다12×12 → 11×11
블록은 m₁=(4,5), m₂=(3,7), m₃=(6,4), m₄=(7,7)이고 회전은 금지입니다. 교재는 폭의 합 20과 높이의 합 23을 상한으로 사용하고, GLPK로 풀어 y* = 12를 얻습니다. 좌표는 블록 1부터 (7,7), (9,0), (0,0), (0,4) — 12×12 외곽선 안에 들어갑니다 (79쪽 그림 3.8).
그런데 교재는 이 배치를 면적 관점에서 sub-optimal이라고 설명합니다. 블록 2를 왼쪽으로 1만큼 옮기면 겹침 없이 실제 폭을 11로 줄일 수 있습니다. 높이는 여전히 12이므로 실제 외곽은 11×12가 되지만, 정사각형 한 변인 y*는 여전히 12입니다. 솔버가 최적화를 잘못한 것이 아니라 최적화한 목적이 실제 직사각형 면적과 다르기 때문입니다.
이제 회전을 허용합니다. 블록마다 이진 변수 zi를 추가해 0이면 원래 방향, 1이면 90도 회전으로 둡니다.
h̃i = (1 − zi)·hi + zi·wi wi, hi가 고정된 상수이므로 이 식은 이진 변수에 대한 선형식입니다. 변수끼리 곱하는 항이 없습니다. 공통 완화 상수는 M = max(20, 23) = 23.
| 모듈 | 원래 크기 | 좌표 | z | 회전 |
|---|---|---|---|---|
| m₁ | (4,5) | (7,6) | 0 | — |
| m₂ | (3,7) | (0,0) | 1 | 회전 |
| m₃ | (6,4) | (7,0) | 1 | 회전 |
| m₄ | (7,7) | (0,3) | 0 | — |
외곽 크기는 11×11입니다. 그렇다면 두 방향 중 하나를 고르는 대신, 면적을 유지하며 폭을 연속적으로 바꾸면 어떨까요? 폭과 높이의 곱이 다시 문제가 됩니다.
핵심 O/X 퀴즈
1. 12×12 배치를 11×12로 줄일 수 있어도 정사각형 외곽선 변수 y*는 그대로 12일 수 있다.
2. 고정된 wi, hi에 대한 회전 치수식은 이진 변수 zi에 대해 선형이다.
3. 회전을 허용한 예제에서는 블록 1과 4가 회전하여 11×11 배치가 된다.
Soft module: 선형화가 만들어 낸 ‘너무 좋은 답’의 정체APPROXIMATION ERROR
블록 1과 2만 고정 모듈로 두고 회전을 허용합니다. 블록 3은 면적 24, 종횡비 범위 [0.5, 2]인 유연한 모듈이고, 블록 4는 면적 49, 종횡비 [0.3, 2.5]입니다. 종횡비는 폭을 높이로 나눈 값입니다. 좌표에 더해 폭 w₃, w₄를 연속 변수로, 고정 모듈의 방향 z₁, z₂를 이진 변수로 사용합니다.
면적을 정확히 유지하려면 h = S/w입니다. 폭을 두 배로 늘리면 높이는 절반이 되어야 합니다. 하지만 이 관계를 그대로 넣으면 선형 모델이 아닙니다. 그래서 최대 폭 부근에서 Taylor 전개를 이용해 높이를 폭의 일차식으로 근사합니다.
경계 h = S/w를 종횡비 식에 넣으면 w/h = w²/S가 되므로 얻는 범위입니다. 교재의 수치: 3.46 ≤ w₃ ≤ 6.93, 3.83 ≤ w₄ ≤ 11.07
→ h₃ = −0.5·w₃ + 6.93 | h₄ = −0.4·w₄ + 8.85 높이 범위는 각각 약 [3.47, 5.20], [4.42, 7.32]. 고정 모듈의 회전 가능성까지 반영해 폭 상한 30.00, 높이 상한 24.52를 구하고 완화 상수 M을 30.00으로 둡니다.
모델을 풀면 y* = 10.46, w₃ = 3.46, w₄ = 3.83을 얻습니다. 블록 1과 2는 회전하고, 높이는 근사식에 따라 5.20과 7.32입니다. 그림 3.10의 실제 외곽은 10.46 × 10.32 — “정말 좋아졌네요!”라고 말하기 전에 반드시 해야 할 검사가 있습니다.
각 블록의 실제 면적이 맞는가? 블록 3의 근사 면적은 3.46 × 5.20 ≈ 17.99로 요구 면적 24보다 작습니다. 블록 4는 3.83 × 7.32 ≈ 28.04인데 요구 면적은 49입니다. 배치를 잘한 것처럼 보였던 이유 중 하나는 블록 자체를 실제보다 작게 계산했기 때문입니다.
| 블록 | 요구 면적 | 폭 | 근사 높이 | 근사 면적 | 실제 필요 높이 |
|---|---|---|---|---|---|
| 3 | 24 | 3.46 | 5.20 | 17.99 | 6.94 |
| 4 | 49 | 3.83 | 7.32 | 28.04 | 12.79 |
높이가 늘어나면서 원래 배치에 겹침이 발생합니다 (86쪽 그림 3.11(a)). 겹침을 제거한 (b)의 외곽 크기는 10.46 × 15.79, 종횡비는 약 0.66으로 원하던 정사각형과 멀어집니다.
여기서 배워야 할 것은 ‘선형화는 나쁘다’가 아닙니다. 근사식이 어느 방향으로 오차를 내는지 확인해야 한다는 것입니다. 이번 방식은 면적을 과소평가해 가짜 여유 공간을 만듭니다. 반대로 크게 잡는 근사는 겹침 위험은 피하지만 공간을 과하게 예약합니다.
12×12 예제는 목적함수의 차이였고, 이번 예제는 크기 제약의 근사 오차였습니다. 목적을 바꾼 오차와 제약을 바꾼 오차를 구분하세요. 솔버의 최적성만 확인해서는 발견되지 않습니다.
핵심 O/X 퀴즈
1. 유연한 블록의 면적을 정확히 유지하면 높이는 폭에 대한 일차함수이다.
2. 이 실습에서는 선형 근사로 구한 블록 면적이 실제 요구 면적보다 작다.
3. 근사 모델에서 겹침이 없더라도 실제 모듈 치수로 복원하면 겹침이 생길 수 있다.
Sequence Pair: 두 개의 순서가 어떻게 평면을 표현할까NON-SLICING REPRESENTATION
지금까지의 기본 NPE는 slicing tree를 사용했습니다. Sequence pair는 non-slicing floorplan을 표현하기 위해 소개되며, 구조는 놀랄 만큼 단순합니다 — 모든 블록 이름이 한 번씩 등장하는 순열 두 개, SP = (S₁, S₂). 공간을 직접 저장하지 않고 두 순서의 비교 결과로 상대 위치를 정합니다.
완성된 배치에서 순서를 얻는 방법은 이렇습니다. 각 블록에서 위·오른쪽 방향의 계단선과 아래·왼쪽 방향의 계단선을 그립니다. 모듈 경계를 가로지르지 않으면서 수평과 수직 진행을 번갈아 합니다. 이 둘이 positive step-line을 만들고, 왼쪽·위쪽과 오른쪽·아래쪽으로 가는 선들이 negative step-line을 만듭니다. 같은 부호의 계단선들이 서로 교차하지 않는다는 성질을 이용해, positive를 왼쪽에서 오른쪽으로 읽은 순서가 첫 순열, negative를 아래에서 위로 읽은 순서가 둘째 순열이 됩니다.
- 둘 다 앞
- a가 두 순열에서 모두 b보다 앞 → a는 b의 왼쪽
- 둘 다 뒤
- a가 두 순열에서 모두 b보다 뒤 → a는 b의 오른쪽
- 앞 / 뒤
- 첫 순열에서 앞, 둘째에서 뒤 → a는 b의 위쪽
- 뒤 / 앞
- 첫 순열에서 뒤, 둘째에서 앞 → a는 b의 아래쪽
순서가 같으면 좌우, 순서가 반대이면 상하입니다. 다만 상하 중 어느 쪽인지는 첫 순열과 둘째 순열의 역할을 구분해서 읽어야 합니다.
블록 4와 5를 보세요. 첫 순열에서도 4가 먼저이고 둘째 순열에서도 4가 먼저이므로 4는 5의 왼쪽입니다. 1과 8은? 첫 순열에서는 1이 먼저, 둘째에서는 8이 먼저이므로 1은 8의 위쪽입니다. 조금 더 보면 1은 다른 모든 블록보다 위에 있고 8은 다른 모든 블록보다 아래에 있습니다. 이렇게 쌍별 비교를 모으면 각 모듈의 좌우·상하 집합이 만들어집니다 (표 3.2).
교재는 순서쌍과 배치의 대응을 1대1이라고 소개하지만, 이 발췌문에서는 그 유일성이 어떤 배치 동등성을 전제로 하는지 따로 설명하지 않습니다. 여기서는 명시된 상대 위치 규칙과 이어지는 최장경로 복원 절차를 계산의 기준으로 삼겠습니다. 아직 4가 5보다 왼쪽이라는 사실만 알지, x좌표가 몇인지는 모릅니다.
핵심 O/X 퀴즈
1. a가 두 순열에서 모두 b보다 먼저 나오면 a는 b의 왼쪽이다.
2. a가 첫 순열에서는 b보다 먼저, 둘째 순열에서는 나중에 나오면 a는 b의 아래쪽이다.
3. 순서쌍의 상대 위치 정보만 읽은 단계와 실제 좌표를 계산한 단계는 구별된다.
제약 그래프: 최소 크기를 구하는데 왜 최장경로를 쓸까HCG · VCG · LONGEST PATH
a가 b의 왼쪽이라면 xb ≥ xa + wa여야 합니다. 이 제약을 a에서 b로 향하는 간선으로 표현한 것이 HCG(Horizontal Constraint Graph)이고, 상하 관계로는 VCG를 만듭니다. VCG의 간선은 아래 블록에서 위 블록으로 향합니다.
우리는 작은 배치를 원하는데 왜 ‘최장’경로를 구할까요? 여러 블록이 내 왼쪽에 있어야 한다면 그중 하나만 피해서는 안 됩니다. 모든 선행 제약을 만족해야 하므로 가장 강한 하한을 따라야 합니다.
yb = max( 0, maxa→b ( ya + ha ) ) 두 식의 간선은 각각 HCG와 VCG의 것입니다. 각 순열의 순서와 일관된 방향으로 간선이 생기므로 순환 없이 계산할 수 있습니다 — DAG에서 선행 노드의 값을 전달하는 최장경로 계산입니다.
교재는 source s와 sink t를 추가합니다. HCG에서 s부터 각 블록까지의 최장경로 길이가 그 블록의 x좌표이고, s부터 t까지가 전체 폭입니다. VCG에서는 각각 y좌표와 전체 높이입니다.
블록의 왼쪽 아래 좌표를 구할 때는 그 블록 자신의 폭이나 높이를 더하지 않습니다. 자신의 치수는 오른쪽 끝이나 위쪽 끝을 구할 때 들어갑니다.
SP₁의 HCG에서 4→5→6 경로를 읽으면 폭은 3+3+5 = 11입니다. VCG에서 8→4→7→1을 읽으면 높이는 4+5+2+4 = 15입니다 (90쪽 그림 3.14의 굵은 선). 따라서 이 순서쌍의 최소 외곽은 11 × 15, 면적 165입니다.
| 블록 | x | y | 블록 | x | y |
|---|---|---|---|---|---|
| 1 | 0 | 11 | 5 | 3 | 7 |
| 2 | 3 | 4 | 6 | 6 | 7 |
| 3 | 6 | 4 | 7 | 0 | 9 |
| 4 | 0 | 4 | 8 | 0 | 0 |
예를 들어 블록 6의 x좌표는 6이고 폭은 5이므로 오른쪽 끝은 11입니다. 블록 1의 y좌표는 11이고 높이는 4이므로 위쪽 끝은 15입니다. 좌표와 외곽 크기를 혼동하지 마세요. 한편 그림 3.12는 전체 HCG와 추이 간선을 제거한 그래프를 함께 보여 줍니다 — a가 b보다 왼쪽이고 b가 c보다 왼쪽이면 a가 c보다 왼쪽이라는 관계는 이미 따라오므로, 이런 중복 관계는 생략해 그림을 단순하게 만듭니다.
핵심 O/X 퀴즈
1. HCG에서 a→b는 b의 x좌표에 하한을 부여한다.
2. 블록 b의 왼쪽 아래 x좌표를 구할 때는 b 자신의 폭까지 포함한다.
3. 여러 선행 제약을 동시에 만족해야 하므로 최장경로가 필요한 최소 좌표를 결정한다.
Sequence Pair의 move: 관계를 바꾸는 것과 크기를 바꾸는 것P-ADMISSIBLE
Sequence pair에도 세 가지 move가 있습니다. 다만 NPE의 M1·M2·M3와 이름이 같다고 같은 연산은 아닙니다.
- M1
- 첫 순열에서만 임의의 두 블록을 교환합니다.
- M2
- 두 순열 모두에서 같은 두 블록을 교환합니다.
- M3
- 선택한 블록을 90도 회전합니다. 순열은 그대로입니다.
M1 — SP₁의 첫 순열에서 1과 3을 바꿉니다. 한 순열만 바꾸면 일부 쌍은 두 순서가 같던 상태에서 반대인 상태로 바뀝니다. 따라서 수평 관계가 수직 관계로, 또는 그 반대로 바뀔 수 있습니다.
SP₂ = ( 3 7 4 5 2 6 1 8 , 8 4 7 2 5 3 6 1 )새 제약 그래프를 평가하면 폭 13, 높이 14, 면적 182입니다. 블록 1은 (11,4), 블록 3은 (0,11)로 갑니다 (그림 3.16, 표 3.5).
M2 — SP₂의 두 순열에서 4와 6을 모두 바꿉니다.
SP₃ = ( 3 7 6 5 2 4 1 8 , 8 6 7 2 5 3 4 1 )결과는 폭 13, 높이 12, 면적 156입니다. 블록 6은 (0,4), 블록 4는 (8,4), 블록 3은 (0,9)입니다.
앞의 NPE 실습에서 마지막 면적이 105였던 것과 섞지 마세요. 다른 표현에 다른 move를 적용한 별개의 예제입니다. 또 최장경로가 하나뿐이라고 생각해서도 안 됩니다 — 교재는 SP₃의 수직 그래프에서 s→8→6→7→3→t도 최장경로라고 따로 언급합니다. 같은 높이를 강제하는 경로가 여러 개라면, 한 경로의 일부를 바꿔도 다른 경로가 전체 높이를 유지할 수 있습니다.
M3는 성격이 다릅니다. 순열을 그대로 두고 블록을 돌리면 상대 위치 관계는 유지되지만 HCG·VCG에서 사용하는 폭·높이가 바뀝니다. 그래프의 관계가 같더라도 좌표와 최장경로는 다시 평가해야 합니다.
마지막으로 중요한 용어 하나, P-admissible. Sequence pair가 정의하는 해 공간에는 최적 floorplan을 표현하는 해가 존재한다는 뜻입니다. 이것은 표현 공간의 능력에 관한 말이지, simulated annealing을 유한 시간 실행하면 반드시 그 최적해를 찾는다는 보장은 아닙니다.
핵심 O/X 퀴즈
1. Sequence pair의 M1은 두 순열에서 같은 두 블록을 동시에 교환한다.
2. 블록을 회전하면 순열이 같아도 그래프에 사용되는 치수가 바뀔 수 있다.
3. P-admissible이면 임의의 탐색 실행이 반드시 전역 최적해를 찾는다.
추가 연습: 답을 외우지 않고 절차를 재현하는 방법교재 95~96쪽
이 부분에는 문제들이 제시되어 있고, 앞의 실습처럼 완성된 수치 해답이 실려 있지는 않습니다. 따라서 어떤 절차를 재현해야 하는지를 정리합니다.
4 3 5 H 1 V 6 7 V H 2 V 8 H V, 블록 1~8의 크기는 (5,3), (2,3), (6,3), (2,5), (6,2), (5,1), (3,8), (6,3). 회전 전 배치를 계산한 뒤 잎의 회전 후보를 만들고 결합합니다. 루트 면적만 적지 말고 방향 선택까지 복원해 회전 전후를 비교하세요.SP₁=(63528417, 17452836)에서 첫 순열의 3과 4를 교환하고, 그다음 두 순열의 1과 6을 교환합니다. 그래프 → 최장경로 → 좌표 → 배치 순으로 복원합니다.hover(w) = S(a + b − w) / (a·b) a와 b는 최소·최대 폭, S는 면적. 두 끝점에서는 실제 높이와 같고 그 사이에서는 필요한 높이를 더 크게 잡습니다. 이 식은 강의에서 직접 유도한 근사식이며, 새 ILP의 최적 배치를 계산한 것은 아닙니다.
작은 모델 면적만 비교하지 마세요. 과소평가는 실제 치수 복원과 겹침 제거가 필요하고, 과대평가는 공간을 과하게 예약할 수 있습니다. 같은 실제 모듈 조건에서 유효한 최종 배치를 비교해야 합니다. 이 문제의 수치적 승자는 발췌문에 제시되지 않습니다.
핵심 O/X 퀴즈
1. Stockmeyer 연습에서는 최소 면적을 구한 뒤 실제 방향 선택까지 복원해야 회전 후 배치를 그릴 수 있다.
2. 과소평가 모델이 출력한 면적이 작으면 실제 치수로 수정한 뒤에도 반드시 더 좋은 배치이다.
3. Sequence pair 연습은 상대 위치 추출, 그래프 구성, 좌표 계산의 순서로 진행할 수 있다.
확장 연구와 최종 정리: 결국 무엇을 설계하고 있었는가PROBING FURTHER
마지막으로 네 도구가 실제 제약과 계산 규모를 만나 어떻게 확장되는지 봅니다. 각 연구가 어떤 제한을 완화하는지에 집중하세요.
non-slicing을 위한 generalized cutline — 한 직선 대신 이어진 선들의 묶음으로 나눕니다(slicing에 가까운 구조에서 특히 효과적). 또 realization tree를 이용해 트리 모양과 무관하게 최악 복잡도를 O(n log n)으로 개선합니다.
미리 배치된 모듈을 shape curve 계산에 반영하고, 치수가 확정되지 않으면 폭·높이를 확률변수로 두어 합과 최댓값을 통계적으로 처리합니다. 버스 배선에서는 routability와 timing까지 고려하며 채널을 버퍼 삽입에 이용합니다. compaction을 붙여 non-slicing까지 확장한 연구도 있습니다 — 기본 표현과 확장된 방법의 범위를 구별하세요.
successive augmentation은 모듈 일부를 먼저 배치해 큰 모듈로 묶은 뒤 다시 배치하는 휴리스틱입니다. 후속 연구는 geometric programming을 convex optimization으로 변환해 선형화 오차를 피하거나, 변수·제약 수를 줄이거나, 정수 변수 없이 여러 LP를 반복해 풉니다. 마이크로아키텍처 배치에서는 실행 중 블록 간 연결 사용 빈도를 활용하기도 합니다.
BSG, O-tree, B*-tree, CBL, TCG 등이 이어집니다. 관심은 “표현할 수 있는가”를 넘어 인접·경계·정렬 제약을 얼마나 쉽게 다루느냐로 넓어집니다. soft·pre-placed 모듈 확장에서는 크기 결정을 convex programming으로 풀고 그 결과를 annealing 탐색에 씁니다.
평가 속도도 연구 대상입니다. 순서쌍 평가를 가중 longest common subsequence 문제로 연결해 배치 복원 복잡도를 O(n²)에서 O(n log log n)으로 줄이는 연구가 소개됩니다. 평가가 빨라지면 같은 시간에 더 많은 후보를 탐색할 수 있습니다.
Fixed-outline 문제는 외곽을 줄이는 대신 주어진 외곽 안에 블록을 넣으면서 배선 길이를 줄이는 문제이며, 교재는 Parquet의 목적함수와 move 확장을 소개합니다. TCG-S는 순서쌍의 빠른 packing·변형과 TCG의 제약 처리·증분 평가 장점을 결합하고, 3D floorplanning에서는 여러 평면에 걸친 관계와 열을 고려하며 CBA 표현이 TCG를 확장합니다. 마지막 PATOMA는 simulated annealing 대신 톱다운 재귀 분할과 legalization을 사용합니다 — 즉 탐색이 반드시 annealing일 필요는 없습니다.
오늘 배운 것은 기하학적 선택을 계산 가능한 구조로 바꾸는 방법입니다. Stockmeyer는 형태 후보를 트리에서 합치고, NPE는 구조를 문자열로 바꿉니다. ILP는 선택과 제약을 변수와 부등식으로, sequence pair는 상대 위치를 두 순서와 최장경로로 바꿉니다.
- 01
- 무엇이 고정되는가?
- 02
- 무엇을 탐색하는가?
- 03
- 최적성은 어느 범위에서 성립하는가?
- 04
- 모델에서 좋은 답이 실제 기하학에서도 유효한가?