Advanced
Density Minimization for the Assignment of P-color Points
Density Minimization for the Assignment of P-color Points
Journal of the Korea Institute of Information and Communication Engineering. 2014. Aug, 18(8): 1981-1986
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : May 08, 2014
  • Accepted : May 27, 2014
  • Published : August 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
재훈 김

Abstract
본 논문에서 다루는 문제는 채널의 위쪽 행에 위치한 P 가지 색을 가지는 점들을 아래쪽 행의 점들에 밀도가 최소가 되도록 연결하는 채널 라우팅 문제이다. 위쪽 행에 위치한 점들이 동일한 색을 가지거나 단지 2가지 색을 가지는 경우는 [1 , 2] 에서 다루어졌다. 본 논문에서는 P 가지 색을 가지는 경우로 일반화한다. 우선 임의의 값 d 가 주어질 때, d 이하의 밀도를 가지는 할당이 존재하는지 결정하는 문제를 O ( p ( n + m )log( n + m ))시간에 풀 수 있음을 보인다. 이를 이용해서 최소 밀도 값의 할당을 찾는 문제를 해결할 수 있음을 보인다.
Keywords
Ⅰ. 서 론
채널에서 특정 위치들을 선으로 연결하는 채널 라우팅(channel routing) 문제는 집적 회로의 여러 레이아웃 문제에서 발생한다. 특정 위치들을 어디에 놓을 것이지 또는 어떻게 연결할 위치들을 선택할 지와 같은 결정은 라우팅 이전에 이루어져야 한다. 본 논문에서는 두 개의 수평선 상에 위치들이 놓여 있을 때, 이 위치들을 연결하는 문제를 다룰 것이다.
평면상에 일정한 간격을 두고 두 개의 수평선 U L 이 주어지는데 U L 보다 위쪽에 위치한다. 위쪽 수평선 U 에는 시작점이라 불리는 n 개의 점들이 존재하고 아래쪽 수평선 L 에는 끝점이라 불리는 m 개의 점들이 존재한다. 그리고 항상 n m 을 만족한다. 또한 위쪽 수평선 U 상의 점들은 p 가지의 색으로 구별된다.
색을 k ∈{ 1, 2, … , p }인 정수로 나타낼 때, U 상의 점
PPT Slide
Lager Image
는 색이 k i 번째 점을 나타내고 L 상의 점은 bj 로 나타낸다. 1 ≤
PPT Slide
Lager Image
, bj m 이고 색 k 인 점
PPT Slide
Lager Image
의 총 수를 nk 로 나타낸다. 우리는 U 상의 점들의 집합 PU 에서 L 상의 점들의 집합 PU 로의 일대일 함수 f : PU PL 를 찾고자 한다. 점
PPT Slide
Lager Image
가 점 bj = f (
PPT Slide
Lager Image
)로 대응되었다는 것은 점
PPT Slide
Lager Image
에서 점 bj 로 선분이 그어졌음을 의미한다. 여기서 함수 f 에 의해서 생긴 선분들에 대해서 색 k 인 시작점을 연결하는 선분을 k -색 선분 ( k -color segment)이라고 부른다. 그러면 k -색 밀도( k -color density)란 수직선을 왼쪽에서 오른쪽으로 이동하면서 만나는 k -색 선분들의 개수를 세었을 때, 만나는 k -색 선분들의 개수가 최대가 됐을 때 그 때의 선분 개수를 말한다. 다시 말해서, k -색 밀도란 모든 실수 x 에 대해서
PPT Slide
Lager Image
x < bj 또는
PPT Slide
Lager Image
> x bj 를 만족하는 k -색 선분들의 개수의 최대값으로 정의한다. 결과적으로 우리는 선분들에 대한 밀도(density)를 k -색 밀도들의 최대값으로 정의할 수 있다. 문제는 이 밀도가 최소가 되도록하는 일대일 함수 f 를 찾는 것이다.
본 논문에서는 최소 밀도를 주는 일대일 함수 f 를 찾기 이전에 임의의 상수 d 가 주어질 때, 밀도가 d 이하인 일대일 함수 f 가 존재하는지 여부를 묻는 결정 문제를해결할 것이다. 이 결정 문제 알고리즘을 이용해서 최소 밀도 값 d * 를 계산하고 이 밀도 값을 주는 일대일 함수 f 를 찾을 것이다.
Ⅱ. 관련 연구
본 논문과 가장 밀접한 관련이 있는 논문들은 [1 , 2] 이다. [1] 에서는 수평선 U 상의 점들이 모두 같은 색을 가지는 경우를 다룬다. 3장에서 다룰 결정문제에 대해서 저자들은 O ( n + m )시간 알고리즘을 제안하였다. 최소 밀도를 찾는 최적화 문제에 대해서도 또한 O ( n + m )시간 알고리즘을 제안하였다.
[2] 에서는 수평선 U 상의 점들이 단지 두 가지 종류의 색을 갖는 문제를 연구하였다. 저자들은 이 경우에 대한 결정문제에 대해서 O (( n + m )log( n + m ))시간 알고리즘을 제안하였다. 또한 최소 밀도 값을 O ( n + m )시간에 찾을 수 있음을 보였고 이 최소 밀도 값을 주는 일대일 함수 f O (( n + m )log( n + m ))시간에 찾을 수 있음을 보였다. 본 논문은 이 논문의 모델을 확장해서 U 상의 점들이 p 가지의 서로 다른 색을 가지는 경우로 일반화할 것이다.
우리는 채널 라우팅 문제를 연구한 여러 다양한 논문들을 찾을 수 있다. [3] 에서는 점들을 연결하는 선분들 이 수직과 수평 선분 부분들로 이루진 경우를 다룬다. 이 때 수평 선분 부분들의 수를 최소로 하는 레이아웃을 찾는 것이 목적이다.
[4] 에서는 L 상의 점들을 순서는 유지하면서 오른쪽으로 이동시키는 회전(rotation) 연산을 생각한다. 이 때 최소 밀도 값을 주는 회전 연산을 찾는 문제를 연구하였다.
[5] 에서는 U 또는 L 상의 점들이 요소(component) 안에 놓여 있는 경우를 다룬다. 그리고 이 요소들은 일직선상에서 왼쪽 또는 오른쪽으로 이동 가능하다. 이 요소들을 이동시켜 밀도 값이 최소가 되도록 하는 문제를 연구하였다.
Ⅲ. 결정 문제
이 장에서는 다음과 같은 결정문제 P1을 다룰 것이다:
P1 : 임의의 정수 d 가 주어질 때, 밀도가 d 보다 작거나 같은 선분들을 생성하는 일대일 함수 f 가 존재하는가?
순서쌍 u = ( i 1 , i 2 , … , ip )에 대해서, 부분할당 fu,e 을 정의한다. 이것은 각각의 색 k = 1, …, p 에 대해서, 점
PPT Slide
Lager Image
, ….
PPT Slide
Lager Image
가 벌써 L 상의 점과 연결되었고, 점 be 이 연결된 L 상의 가장 오른쪽 점이란 것을 의미한다.이 때, 다음을 만족하는 부분할당 fu,e d -할당이라고 부른다: 각각의 색 k 에 대해서, fu,e 은 색 k 인 시작점들이 k -색 밀도가 ≤ d 를 만족하는 할당으로 확장될 수 있다.
d -할당 fu,e , e h , 이 주어질 때, 끝점 b h + 1 k -레이블 jk 를 정의한다. 각 k 에 대해서, fu,e b h + 1
PPT Slide
Lager Image
을 연결하는 선분을 추가할 때 밀도가 d + 1이되면 jk = 0. jk ≠ 0이면, jk = 1 또는 jk = 2. d -할당 fu,e 가 그것의 k -색 밀도가 ≤ d 를 만족하는 할당으로 확장하기 위해서 b h + 1 가 반드시
PPT Slide
Lager Image
와 연결되어야 하면, jk = 1 . 그렇지 않다면, jk = 2 .
아래의 표 1 에서 결정 알고리즘이 주어진다. 이 알고리즘에서 함수 label 은 끝점 b h + 1 의 모든 k -레이블들의 순서쌍 w = ( j 1 , … , jp )를 출력한다. 여기서 함수 label 의 구현을 구체적으로 설명할 것이다. 각 색 k 에 대해서, jk = 0, 다시 말해서, b h + 1
PPT Slide
Lager Image
을 연결하면 k -색 밀도가 d + 1가 되는지 결정하는 것은 O (1)시간에 할 수 있다. jk = 1 또는 jk = 2 인지 결정하기 위해서 우리는 [2] 에서와 같은 균형 이진트리 Tk 를 사용할 것이다.
결정 알고리즘Table. 1Decision algorithm
PPT Slide
Lager Image
결정 알고리즘 Table. 1 Decision algorithm
PPT Slide
Lager Image
, … ,
PPT Slide
Lager Image
b f(1) , …, bf(ik) , b h + 1 , …, bm 을 정렬한 후, 각 점들을 Tk 의 잎노드에 왼쪽에서 오른쪽으로 저장한다. Tk 의 내부노드 u 는 부가적인 정보들을 저장해서 자신이 루트가 되는 서브트리의 잎노드들에 대한 k -밀도를 계산할 수 있도록 한다. 그러면 이 트리 Tk 에서 b h + 1 을 제거하는 질의를 수행한다. 결과로 k -밀도가 d + 1로 증가하면 jk = 1이고 아니면 jk = 2. 이 질의는 O (log( nk + m ))시간에 수행된다. 따라서 label 함수의 출력을 얻기위해서 모든 k 에 대해서 이 것을 수행하면 O ( p log( n + m ))시간이 소요된다. 마지막으로 결정 알고리즘이 끝점 b h + 1 을 어떤 색 c 인 시작점과 연결하기로 결정한다면 k c 인 모든 색 k 에 대해서 트리 Tk 에서 b h + 1 을 제거해서 트리를 업데이트 한다.
결정 알고리즘은 색 k 인 시작점들과 끝점들을 각각 왼쪽에서 오른쪽으로 고려하면서 수행한다. label 의 결과 순서쌍 w = ( j 1 , … , jp )에서 하나 이하의 jk 가 1이면, 현재 고려되는 끝점 b h + 1 과 색 k 인 시작점
PPT Slide
Lager Image
을 연결하는 선분 ( aik + 1, b h + 1 )을 추가한다. 그렇지 않으면, 다시 말해서, 모두가 1이 아니면, jk = 2인 색 k 중에 가장 작은 k 의 시작점과 끝점을 연결한다. 알고리즘 진행 중에 w 안에 적어도 두 개 이상의 jk 가 1이 되면, 일대일 함수 f 는 존재하지 않는다. 결과적으로 위 결정 알고리즘은 O ( p ( n + m )log( n + m ))시간에 수행됨을 알 수 있다.
Ⅳ. 최적화 문제
이 장에서는 다음과 같은 최적화문제 P2를 다룰 것이다:
P2 : 일대일 함수 f 에 의해 생성되는 선분들의 최소밀도를 찾으시오.
이 문제는 3장의 결정 알고리즘을 이용해서 풀 것이다. 다시 말해서, 결정 알고리즘을 이용해서 밀도 값 d 에 대해서 이분검색(binary search)을 수행할 것이다.
1 ≤ x, y M 인 모든 x , y 에 대해서, upk ( x, y ) 는 위치가 ≥ x 이고 ≤ y 인 색 k 인 시작점들의 수로 정의하고, down ( x, y )는 위치가 ≥ x 이고 ≤ y 인 끝점들의 수로 정의한다. 또한 outk ( x, y )는 upk ( x, y ) - down ( x, y ) 로 정의한다. 이 정의로부터 𝜓 1 ( x, y ) max{ out 1 ( x, y ), …, outp ( x, y )},
PPT Slide
Lager Image
라고 하자. 그러면 Φ 1 을 다음과 같이 정의한다:
PPT Slide
Lager Image
Φ 1 가 최적 밀도 d * 의 하한이 된다는 것, 다시 말해서, d * Φ 1 을 만족함을 보이기는 어렵지 않다.
보조정리 4.1. d * Φ 1 .
또한 d * 의 상한을 얻기 위해서 다음과 같이 Φ 2 를 정의한다:
PPT Slide
Lager Image
다음에서 우리는 Φ 2 d * 의 상한임을 보인다.
보조정리 4.2. d * Φ 2 .
증명. 밀도 Φ 2 인 일대일 함수 f 가 존재함을 보임으로 충분하다. 다시 말해서, 이전 장의 결정문제 P1에 대해서 d = Φ 2 일 때, 결정 알고리즘의 답이 항상 참임을 보이면 된다.
결론이 아니라고 가정하면, 다시 말해서, 결정 알고리즘이 거짓을 출력하였다고 가정하자. 알고리즘의 동작에서 점
PPT Slide
Lager Image
, … ,
PPT Slide
Lager Image
, b h + 1 을 고려할 때 실패하였다면 b h + 1 의 레이블 w 안에는 적어도 둘 이상이 1이다. 하지만 이런 일은 일어나지 않음을 증명할 것이다.
레이블 w 안에서 1의 값을 갖는 임의의 두 개의 인덱스를 jα jβ 라고 하자. 다시 말해서, 색 α β 각각에 대해서, 밀도 d = Φ 2 를 얻기 위해서는 b h + 1 가 각각 a iα + 1 a iβ + 1 에 연결되어야만 한다.
jα = 1 또는 jβ = 1 이 되는 다음과 같은 두 가지 이유가 있다:
  • 1)bh+ 1가 없으면, 시작점들과 연결되기 충분한 개수의 끝점이 남아 있지 않는 경우.
  • 2)bh+ 1가 없어도 충분한 끝점들이 남아있지만 밀도가 ≤Φ2이기 위해서bh+ 1와 반드시 연결되어야 하는 경우.
먼저 jα = 1, jβ = 1의 적어도 한 경우가 1) 때문인 경우를 생각하자. 남아있는 색 α β 인 점들의 총 수가 남아있는 끝점들의 수를 넘어가는 순간을 생각한다. 이것이 점
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, b t + 1 를 고려할 때 처음으로 나타난다고 가정하자. 그러면, nα - r + nβ - s m - t + 1과 같다. b t + 1 - λ 를 ≤ b t + 1 위치에 있는 연결되지 않은 가장 오른쪽 끝점이라고 하자. 그러면 이 점에서의 레이블 w = 0. 따라서 b t + 1 - λ <
PPT Slide
Lager Image
이고 b t + 1 - λ <
PPT Slide
Lager Image
. 또한 ≤ b t + 1 - λ 에 위치한 끝 점들에 연결된 > b t + 1 - λ b t + 1 사이에 있는 끝점들과 연결된 시작점들의 수라고 하자. 그러면,
PPT Slide
Lager Image
이것은 모순이다. 따라서 jα = 1, jβ = 1의 어떤 경우도 1) 때문은 아니다.
남은 것은 jα = 1, jβ = 1가 모두 2) 때문인 경우 이다. Sα 를 색 α 인 점들만을 고려해서 a 1 , …, aiα f 와 같이 연결하고 남은 점들을 b h + 1 , …, bm 에 연결하는 밀도 Φ 2 의 해답이라고 하자. 그러면 Sα 에서 적어도 하나의 좌표 xα b h + 1 에 대해서 ≤ xα 에 위치한 시작점과 > xα 인 끝점을 연결하는 Φ 2 개의 선분들이 존재한다. 따라서 위 조건을 만족하는 가장 왼쪽의 좌표를 xα 이라고 하자. 그러면 Sα 에서 ≥ b h + 1 이고 ≤ xα 인 위치의 끝점들은 모두 α 색의 시작점들과 연결된다. 비슷하게 색 β 에 대한 Sβ 를 생각할 수 있고 xβ 를 정의한다. 일반성의 손실 없이, xα xβ .
위치가 > b h + 1 이고 ≤ xα 끝점들의 개수를 δ 1 이라 하고 > b h + 1 이고 ≤ xβ 인 끝점들의 개수를 δ 2 라고 하자. 그러면
PPT Slide
Lager Image
는 위치 ≤ xα 인 가장 오른쪽 색 α 점이고
PPT Slide
Lager Image
는 위치 ≤ xβ 인 가장 오른쪽 색 β 점이다. δ 3 xα + 1과 xβ 사이의 색 α 점들의 수라고 하면,
PPT Slide
Lager Image
는 위치 ≤ xβ 인 가장 오른쪽 색 α 점이다.
우선 b h + 1 왼쪽의 모든 끝점들이 연결되어 있다고 가정하자. 그러면,
PPT Slide
Lager Image
이것은 모순이다.
b h + 1 왼쪽의 모든 끝점들이 연결되어 있지는 않다고 가정하자. bz 를 그러한 연결되지 않은 가장 오른쪽 끝점이라고 하면, < bz 인 끝점들과 연결된 각각 Φ 2 개의 색 α β 인 시작점들이 > bz 에 존재한다. 위와 비슷한 이유에 의해서 다음을 만족한다:
PPT Slide
Lager Image
그러나 이것은 모순이다. 위의 두 보조정리로부터 Φ 1 d * Φ 2 임을 알 수 있다. 따라서 밀도 값 d 에 대한 이분검색을 수행할 때, 위의 범위에서 수행하면 O ( p ( n + m )log( n + m )log( Φ 2 - Φ 1 ))시간에 풀수 있다.
Ⅴ. 결 론
본 논문에서는 [1 , 2] 에서 다루었던 문제에서 수평선 U 상의 점들이 p 가지의 색을 가지는 경우로 확장하였다. 임의의 상수 d 가 주어질 때, 밀도가 d 이하인 일대일 함수 f 가 존재하는지 여부를 묻는 결정문제에 대해서 O ( p ( n + m )log( n + m ))시간 알고리즘을 제안하였다. 또한 최소 밀도 값을 d * 를 계산하고 이 밀도 값을 주는 일대일 함수 f 를 찾는 O ( p ( n + m )log( n + m )log( Φ 2 - Φ 1 ))시간 알고리즘을 제안하였다. 앞으로 채널 라우팅 문제에 대한 여러 변형 문제들에 대해서도 연구할 수 있을 것이다.
Acknowledgements
본 연구는 2014년도 부산외국어대학교 학술연구조성비에 의해 연구되었으므로, 관계부처에 감사 드립니다.
BIO
김재훈(Jae-Hoon Kim)
1994년 서강대학교 수학과 이학사
1996년 KAIST 수학과 이학석사
2003년 KAIST 전산과 공학박사
2003년 - 현재 부산외국어대학교 컴퓨터공학과 교수
※관심분야 : 알고리즘, 최적화, 스케줄링
References
Atallah M. J. , Hambrusch S. E. 1984 “On terminal assignments that minimize the density,” Purdue University
Atallah M. J. , Hambrusch S. E. 1986 “An assignment algorithm with applications to integrated circuit layout,” Discrete Applied Mathematics 13 (1) 9 - 22    DOI : 10.1016/0166-218X(86)90064-8
Yoshimura T. , Kuh E. S. 1982 “Efficient algorithms for channel routing,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems CAD-1 (1) 25 - 35
Atallah M. J. , Hambrusch S. E. 1984 “Optimal rotation problems in channel routing,” Purdue University
Johnson D. S. , LaPaugh A. S. , Pinter R. Y. 1994 “Minimizing channel density by lateral shifting of components,” in Proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms 122 - 131