Floorplan 자료 구조 표현

Floorplan의 면적 혹은 총 Wire 길이를 계산하기 위해서는 Floorplan 데이터를 추상화할 필요성이 있다.

 

그러면 어떤 자료구조를 이용해서 Floorplan design을 추상화할까?

 

이 추상화 방법에는 대략 3가지 방법이 있다.

 

1. Slicing/nonslicing floorplan tree

 

아래 그림과 같이 Floorplan을 이진트리에 저장하는 방법이다.

 

Slicing/Nonslicing floorplan tree

 

V : 수직으로 자르는 방향(Vertical)

H : 수평으로 자르는 방향(Horizontal)

W : 수직과 수평으로 자르는 것으로 표현할 수 없는 부분을 Wheel이라고 한다.

 

여기서 가장 끝의 노드(leaf node 혹은 terminal node)가 

V와 H는 수직과 수평으로 자른 것으로 표현할 수 있으니, Slicing floorplan tree라고 말하고,

W는 수직과 수평으로 자른 것으로 표현할 수 없으니, Non slicing floorplan tree라고 말한다.

 

 

2. Constraint-graph-pair

 

Floorplan을 두개의 방향성 그래프로 나타내는 것이다.

 

t(sink) node와 s(source) node를 지정하여 순서를 표현한다.

 

1) Verical constraint graph (VCG)

: Node에 가중치를 추가하여 저장한 방식이다. (가중치가 의미하는 것은 해당하는 블럭의 높이이다.)

 

2) horizontal constraint graph (HCG)

: Node에 가중치를 추가하여 저장한 방식이다. (가중치가 의미하는 것은 해당하는 블럭의 너비이다.)

 

3. Sequence Pair

$S_+$와 $S_-$라는 블럭 순열로 나타내는 방식이다.

 

 

설명을 이렇게만 들으니 받아들이기 매우 어렵다.

 

아래 그림과 같이 이해해보자.

 

Floorplan의 여러 표현 방법을 나타낸 그림

 

 

왼쪽 위 그림이 Floorplan의 밑그림이며, 왼쪽 아래 그림은 이것의 HCG, 오른쪽 위 그림은 이것의 VCG, 마지막으로 오른쪽 아래는 SP이다.

 

VCG나 HCG는 위 그림을 보면 금방 이해가 된다.

(s node(source node)에서 t node(sink node)까지 이르는 경로가 직관적인 구조로 나오므로)

 

또한, Sequence Pair또한 두 순서를 따라가다 보면 어떤 순서로 이루어져 있는지 알 수 있다.

 

Sequence Pair는 두개의 순열로 구분된다.

 

첫번째로 S+는 왼쪽 상단부터 시작하여 오른쪽 하단까지 이르는 경로의 순서이고,

 

두번째로 S-는 왼쪽 하단부터 시작하여 오른쪽 상단까지 이르는 경로의 순서이다.

 

 

이 둘 순열의 정보를 통해서 우리는 데이터 양을 줄이며 단순하게 Cell의 위치만을 나타낼 수 있어서

 

앞으로 나올 알고리즘에는 Sequence pair가 자주 쓰인다.