Netlist and System Partitioning : FM 알고리즘

<오류의 지적을 매우매우 환영합니다.>

 

앞서 우리는 큰 회로를 부분적으로 나누는 알고리즘인 KL 알고리즘에 대해서 알아 보았다.

 

위의 알고리즘은 큰 회로를 부분적으로 나누면서, 하위 회로간의 연결이 최소가 되도록 하는게 목표였다.

 

하지만 실제 회로에 적용하기에는 부족한 부분이 많았는데, 더 고려해야 할 사항은 무엇일까?

 

일단 첫번째로, Cell과 하위 회로의 크기에 있다.

앞서 말한 KL 알고리즘은 모든 Cell의 크기를 같다고 두고 있다. 하지만 분명히 AND게이트, XOR게이트, Adder 등의 Standard/Macro cell은 서로 크기가 다르므로, 서로 크기를 같다고 하는 것은 현실 세계에 맞지 않는다.

또한 큰 회로를 하위 회로로 나누는데, 이 하위 회로끼리의 크기는 서로 비슷해야 시간 복잡도 측면에서 유리하다.

(합병/퀵 정렬 알고리즘을 생각하면 편하다. 서로 비슷하게 나뉘어야 처리 부하가 고르게 분산되므로)

 

두번째는, Cell의 Swap방식이다.

앞서 말한 KL 알고리즘은 서로 다른 파티션의 두 셀을 선정하여 바꾸는 방법을 택했는데, 이렇게 하면 두 Cell을 선정하는 시간이 추가로 들게 된다. 또한, Node의 크기 정보까지 고려하여 분리하고 싶을 때 선택하기 좋은 방법은 아니다. (단순히 연결 정보만 가지고 cell을 Swap하면 하위 회로의 크기는 달라지므로)

 

세번째는, Hyper graph 지원 유무이다.

실제 회로는 Graph로 표현하는 것보다 Hyper Graph로 표현하는게 훨씬 알맞다. (Junction등을 하나의 Edge로 표현하여 Edge를 줄일 수 있으므로) 따라서 위 사안도 고려해야 할 부분이다.

 

위와 같은 이유들로 인해서, KL 알고리즘을 좀 더 현실에 맞게 개선한 Fiduccia-Mattheyses(FM) 알고리즘이 등장하게 되었다.

 

특징

• Cell의 크기와 하위 회로의 크기를 고려하여 그래프를 나눌 수 있다.
• Hyper graph를 지원한다.
• Cell을 Swap하는 방식이 아니라, 선택된 Cell만 반대편으로 넘기는 방식을 택한다.

자, 그럼 천천히 FM 알고리즘의 기본 개념들을 알아보자.

 

 

1. 반대편으로 넘길 Cell은 어떻게 정하는가?

 

KL 알고리즘과 마찬가지로 여기서도 이득(Gain) 공식을 기반으로 넘길 Cell을 결정한다.

 

Cell c의 이득 공식

해당 이득 공식은 위의 공식과 같다.

여기서 FS(c)가 의미하는 것은 "c 노드의 현재 상태에서 잘린 Edge의 수"이다.

(+ 근데 그 Edge가 c의 파티션 내의 다른 Cell과도 연결되어 있다면 이것은 Count하지 않는다.)

위 내용을 여기서 이해하기엔 어려울테니 밑의 예제에서 이해하면 될 것같다.

 

그리고 TE(c)가 의미하는 것은 "c 노드의 현재 상태에서 온전한 Edge의 수"이다.

 

따라서, 위 식을 해석해보면

 

"이득 = 잘린 Edge - 안 잘린 Edge" 정도로 해석될 수 있으며

 

이 이득이 큰 노드일수록 반대편으로 넘겼을 때, 큰 Cut Edge 이득을 얻을 수 있다.

 

또한, 이런 과정을 여러 번 거쳐서 최종 최대 이득을 구하게 된다.

(이러한 개념들이 어렵다면, 바로 밑에 내려가서 예제를 통해 이해하면 된다.)

 

Maximum positive cut cost

최종적으로 위 식의 G 값이 가장 큰 값의 상태를 채택함으로써 알고리즘은 끝이 난다.

(이건 KL 알고리즘과 똑같다.)

 

 

 

2. 면적을 어떻게 고려할 것이고, 서로 균등하게 나눌 것인가?

 

일단 여기서는 ratio factor를 사용하여, 하위 회로끼리의 크기 비율을 임의적으로 맞춰줄 수 있다.

 

Ratio factor

A가 차지하는 공간 + B가 차지하는 공간 = 총 공간

 

위의 Ratio factor는 말그대로 전체 공간에서 A회로가 차지하는 비율을 말하며, 이는 우리가 임의적으로 정해줄 수 있다.

 

위 수식들을 이용해서 우리는 Cell 이동 시 면적 또한 고려할 수 있게 되었다.

 

A가 차지할 수 있는 공간

 

뜬금없이 위의 공간 제약 조건에서 Area_max(V)를 고려하는 이유는 Cell을 이동시켜야 할 때, 유연성을 주기 위함이다.

 

예시를 들면, 각 셀의 크기가 area(a) = 5, area(b) = 5, area(c) = 5, area(d) = 5, area(e) = 4, area(f) = 26 이며, A회로와 B회로가 서로 동일한 크기를 갖는 것을 원하여, r = 0.5 로 설정한 경우를 가정하자.

 

그러면, 전체 회로의 면적은 area(V) = 5 + 5 + 5+ 5+ 4 + 26 = 50 이 되고, 이 중 우리가 원하는 A회로의 면적은 r*area(V) 이므로 25가 된다.

 

하지만, Cell 크기가 전부 1인 것도 아니고 A회로의 면적을 매번 정확히 25로 맞추며 Cell을 이동하는 것은 불가능하다.

 

따라서, 우리는 Cell이 이동할 수 있는 허용 공간 범위를 설정하여야 한다. 특히 Cell은 선택하고 이동할 때는 가장 큰 크기를 가지는 Cell도 이동할 수 있어야 한다. (여기서는 26 크기를 가지는 Cell f)

 

따라서, 그 범위를 가장 큰 Cell의 크기(Variation)으로 설정한다. 실제로 밑의 예제를 보면 매 반복시마다 이 범위에 들어오도록 Cell을 이동시켜, A회로의 면적이 우리가 설정한 r값에 지속적으로 가까운 상태를 유지한다는 것을 알 수있다.

 

어느정도 개념을 알았으니, 알고리즘 슈도코드와 예제 풀이를 통해 실제 응용 단계를 이해하도록 하자.

 

Pseudo code

FM 알고리즘의 Pseudo code

Example

기본 조건과 그 Graph

 

일단 위 조건을 이용하여, area(A)의 범위를 구하면, 

다음과 같이 구할 수 있다.

 

또한, Partition을 이동할 Cell을 선정하기 위해 각 Cell의 Gain을 구해보면,

 

FS(a) = 2 (N3와 N4가 잘리므로 2이다. 여기서 N2를 고려하지 않는 이유는 a와 같은 Partition내에 b노드와도 연결되어 있기 때문이다.)

 

TE(a) = 1 (N1은 잘리지 않은 Edge이기 때문이다.)

 

g(a) = 2 - 1 = 1 (a Node를 반대편으로 옮기면 Edge 1개가 더 잘리지 않는 이득을 얻을 수 있다.)

 

이후 b~e Node에 대해서도 진행해보면,

 

나머지 Node들의 Gain

여기서 이동시 가장 이득이 큰 Node는 a 혹은 e이다. (둘다 1로 동점이다.)

 

이후, a와 e에 대해서 크기 조건을 적용하여 더 효율적으로 이동하는 노드를 선정한다.

 

1. a를 A에서 B로 이동시 : area(A) = area(b) = 4

2. e를 B에서 A로 이동시 : area(A) = area(a) + area(b) + area(e) = 11

 

여기서 area(A)의 제약 조건에 더 알맞게 맞추는 Node는 a이므로, a를 B회로로 옮긴다.

 

 

첫번째 반복 : A1 = {b}, B1 = {a, c, d, e}, 고정된 Node는 a

a Node를 B회로로 이동한 그래프

이러한 과정을 거치면 위처럼 새롭게 Cut된 그래프가 나오게 되는데, 이 그래프에서 다시 Node마다 이득을 구하는 위 과정을 반복하여 모든 노드가 고정(한번 이동하면 그 회로에 고정된다.)되면 알고리즘이 끝나게 된다.

 

- 이득을 구하는 방법을 반복

 

FS(b) = 2 (N1과 N2가 잘리므로)

TE(b) = 0

 

g(b) = 2 - 0 = 2

 

이후 c~e 노드에 대해서도 진행해보면,

(+ FS(c)가 1이 아닌 이유는 같은 Partition(B회로) a Node와 N2를 공유하고 있기 때문이다.)

 

다음과 같은 결과를 얻을 수 있다.

 

하지만, 위처럼 매번 새로운 그래프에서 다시 Node의 이득을 구하는 것은 연산량과 시간 측면에서 단점이 크다.

 

따라서, 처음에만 그래프의 이득 값을 구하고, 이후에는 갱신하는 방법을 사용하게 되면 연산량과 시간 측면에서 매우 유리하여, 이 알고리즘에서는 그 방법에 대해서 설명하고 있다.

 

원리는 이렇다. 처음 계산한 이득에서 움직이기로 결정한 노드와 연결된 Edge만 계산하는 방식인데, 실제로 이 방법이 연산량이 훨씬 적기 때문에 사용한다. 밑에는 이를 위해 필요한 개념들을 적어 놓았다.

(여기서는 이러한 Net을 Critical Net이라고 부르고 있다.)

 

 

F(net) : 이동하기 전 회로 net에 연결된 Node의 수(A -> B라면 A만 고려한다.)

T(net) : 이동하기 전 회로 net에 연결된 Node의 수(A -> B라면 B만 고려한다.)

 

F'(net) : 이동한 후 회로 net에 연결된 Node의 수(A -> B라면 A만 고려한다.)

T'(net) : 이동한 후 회로 net에 연결된 Node의 수(A -> B라면 B만 고려한다.)

 

 

설명을 이렇게만 들으면 이해하기 매우 어려운데, 쉽게 예시를 하나 들어보자.

 

앞선 예제에서 사용된 그래프 (좌 : 이동 전, 우 : 이동 후)

우리는 처음 이득을 계산하고 이동할 노드를 선정하는 과정에서 a Node를 움직이기로 결정하였다.

 

그래서 실제 변화되는 이득과 연관있는 것은 a Node와 연결된 Edge뿐이다.

 

즉, N1, N2, N3, N4 Edge에 연결된 Node들만 이득을 갱신하여 불필요한 연산을 줄인다.

 

이는 밑의 과정에서 잘 볼 수 있다.

 

1. 이동 전 그래프(위 사진의 왼쪽)에서 얻는 정보 (잘리지 않은 Edge 정보)

(이미 a를 A->B로 이동하는 방법을 선택하였으므로, F(from)는 A회로만 고려하고, T(to)는 B회로만 고려한다.)

 

T(N1) = 0 (B회로 입장에서 보면 N1에는 어떠한 노드도 연결되어 있지 않다.)

-> N1과 연결된 b노드의 이득을 1 올린다. (T(net) 값이 0이면)

 

T(N2) = 1 (B회로 입장에서 보면 N2에 c노드 하나가 연결되어 있으므로 1이다.)

-> N2와 연결된 c노드의 이득을 1 내린다. (T(net) 값이 1이면)

 

T(N3) = 1 (B회로 입장에서 보면 N3에 d노드 하나가 연결되어 있으므로 1이다.)

-> N3와 연결된 d노드의 이득을 1 내린다. (T(net) 값이 1이면)

 

T(N4) = 1 (B회로 입장에서 보면 N4에 e노드 하나가 연결되어 있으므로 1이다.)

-> N4와 연결된 e노드의 이득을 1 내린다. (T(net) 값이 1이면)

 

2. 이동 후 그래프(위 사진의 오른쪽)에서 얻는 정보 (a 노드 이동 후에 잘린 Edge 정보)

 

F'(N1) = 1 (A회로 입장에서 보면 N1에 b노드 하나가 연결되어 있으므로 1이다.)

-> N1와 연결된 b노드의 이득을 1 올린다. (F'(net) 값이 1이면)

 

F'(N2) = 1 (A회로 입장에서 보면 N2에 b노드 하나가 연결되어 있으므로 1이다.)

-> N2와 연결된 b노드의 이득을 1 올린다. (F'(net) 값이 1이면)

 

F'(N3) = 0 (A회로 입장에서 보면 N3에는 어떠한 노드도 연결되어 있지 않다.)

-> N3와 연결된 d노드의 이득을 1 내린다. (F'(net) 값이 0이면)

 

F'(N4) = 0 (A회로 입장에서 보면 N4에는 어떠한 노드도 연결되어 있지 않다.)

-> N4와 연결된 e노드의 이득을 1 내린다. (F'(net) 값이 0이면)

 

 

위의 내용을 종합하면,

 

b노드 : 기존 이득에 비해 이득이 3만큼 올라감 (-1 + 3 = 2)

c노드 : 기존 이득에 비해 이득이 1만큼 내려감 (0 - 1 = -1)

d노드 : 기존 이득에 비해 이득이 2만큼 내려감 (0 - 2 = -2)

e노드 : 기존 이득에 비해 이득이 2만큼 내려감 (1 - 2 = -1)

 

처럼 정리할 수 있으며, 이는 처음 그래프의 이득 값과의 상대적인 차이를 이용하여 새로운 그래프의 이득 값을 빠르고 효율적으로 구할 수 있다.

 

 

 

이 이후 알고리즘을 조금만 더 반복해보자.

 

먼저 가장 이득 값이 높은 노드인 b노드(이득 값 = 2)를 이동시킬 노드로 선정해 본다.

 

1. b를 A에서 B로 이동시 : area(A) = 0 이 되므로, 균등하게 회로를 분할해야 한다는 조건에 맞지 않는다.

(1 < area(A) < 11 조건을 만족시켜야 하므로)

 

따라서, 그 다음으로 큰 이득(이득 값 = -1)을 갖는 c와 e를 고려한다.

 

2. c를 B에서 A로 이동시 : area(A) = area(b) + area(c) = 5

3. e를 B에서 A로 이동시 : area(A) = area(b) + area(e) = 9

 

이 중 area(A)의 범위 중간 값과 가까운 2번 경우가 가장 적합하며, 이동할 노드는 c로 결정한다.

 

두번째 반복 : A1 = {b, c}, B1 = {a, d, e}, 고정된 Node는 a, c

 

이후 모든 노드가 한번씩 이동할 때까지 반복한다.

 

이후 반복 과정의 결과

 

모든 과정을 마치고, 각 과정에 따른 Maximum positive cut cost 를 구해보면 다음과 같다.

 

위 결과에 따라서 우리는 1번째 반복 결과, 3번째 반복 결과, 4번째 반복 결과가 가장 좋은 이득을 내었다는 것을 확인할 수 있으며, 이 중 4번째 반복 결과가 가장 균형 잡힌 크기(area(A) = 5)를 보여주므로, 4번째 반복 상태를 최종 상태로 결정하면 된다.

 

최종적으로 선택된 상태

 

이렇게 하면 여러 조건이 있는 상태에서도 그래프 분할을 효과적이고 현실적이게 적용할 수 있다.