Advanced
Analysis of Various Characteristics of the Half Pancake Graph
Analysis of Various Characteristics of the Half Pancake Graph
Journal of Korea Multimedia Society. 2014. Jun, 17(6): 725-732
Copyright © 2014, Korea Multimedia Society
  • Received : May 21, 2014
  • Accepted : June 09, 2014
  • Published : June 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정현 서
Dept. of Computer Engineering, Sunchon National University
형옥 이
Dept. of Computer Education, Sunchon National University

Abstract
The Pancake graph is node symmetric and useful interconnection network in the field of data sorting algorithm. The Half Pancake graph is a new interconnection network that reduces the degree of the Pancake graph by approximately half and improves the network cost of the Pancake graph. In this paper, we analyze topological properties of the Half Pancake graph HP n . Fist, we prove that HP n has maximally fault tolerance and recursive scalability. In addition, we show that in HP n , there are isomorphic graphs of low-dimensional HP n . Also, we propose that the Bubblesort B n can be embedded into Half Pancake HP n with dilation 5, expansion 1. These results mean that various algorithms designed for the Pancake graph and the Bubble sort graph can be executed on HP n efficiently.
Keywords
1. 서 론
지난 30여 년간 고성능 컴퓨팅(high performance computing) 분야는 과학·공학·비즈니스 분야의 연구자들로부터 집중적으로 연구되고 있다. 고성능 컴퓨터에 관한 연구는 병렬 컴퓨팅, 그리드 컴퓨팅, 클라우드 컴퓨팅, Peer-to-Peer(P2P) 등 새로운 패러다임을 등장 시켰다 [1] . 상호연결망은 고성능 컴퓨터의 프로세서를 연결하는 위상(topology), network on chip(NoC)에서 대용량 집적회로 내부에 있는 프로세서-코어의 물리적 연결 구조, 무선 센서 네트워크에서 싱크노드와 소스노드들의 논리적 연결 구조, 생물학에서 유전자 계산 모델, 수학에서 정렬문제 등 다양한 분야에서 응용되고 있다 [2 - 5] .
상호연결망은 프로세서는 노드(node)에 프로세서를 연결하는 통신링크는 에지(edge)에 대응하는 그래프로 표현된다. 임의의 노드와 결합된 에지의 수를 분지수(degree)라고 한다. 상호연결망은 망을 확장할 때 노드의 수에 비례하여 분지수가 증가하는 하이퍼큐브(hypercube) [6] 부류, 스타(star) 그래프 [7] 부류와 망을 확장하더라도 분지수가 상수인 메쉬(mesh) [8] 부류의 연결망으로 크게 나눌 수 있다. 하이퍼큐브 부류는 iPSC/2, iPSC/860, n-CUBE/2 등으로 상용화 되었고 [9] . 메쉬 부류는 MasPar Intel Paragon, XP/S, Touchstone DELTA System, Mosaic C, Cray T3D, MIT의 J-Machine, Tera Computer등으로 상용화 되었다 [10 , 11] .
스타 그래프 부류는 하이퍼큐브 부류와 비슷한 노드 개수를 가질 때 상대적으로 적은 분지수와 짧은 지름을 갖는 장점이 있어 고성능 컴퓨팅 분야에서 하이퍼 큐브의 대안이 되었다 [7] . 스타 그래프 부류는 노드 형태가 계층구조를 갖는 매크로-스타 그래프 [12] , 행렬스타 그래프 등이 있고, 계층 구조가 아닌 것으로 스타 그래프, (n,k)-스타 그래프, 팬케익 그래프 [13] , 버블정렬 그래프 [14] , 전위 그래프 등이 있다. 최근에 팬케익 그래프의 망 비용을 개선한 하프팬케익 그래프 [15] 가 발표되었다.
설계한 상호연결망이 고성능 컴퓨터로 제작되기 위해 두 노드 사이의 메시지 전송을 위한 라우팅은 필수이고 이는 다른 많은 병렬 알고리즘의 기초가 된다. 라우팅에는 결정(deterministic) 라우팅과 적응(adaptive) 라우팅 그리고 고장 허용(fault tolerant) 라우팅이 있다. 이 외에도 설계된 상호 연결망이 효과적으로 사용되려면 고장 허용도, 재귀적 확장성, 서브 그래프 성질, 해밀턴 성질, 방송 알고리즘, 임베딩 알고리즘 등이 개발되어야 한다. 고장 허용도는 시스템의 가동이 멈추지 않는 범위에서 허용할 수 있는 노드나 에지의 고장 개수를 나타낸다. 재귀적 확장성은 연결망을 확장할 때 기존의 연결망이 그대로 존재하는지 여부를 나타낸다. 이 성질이 있는 연결망은 확장비용이 적게 든다. 임의의 연결망 G를 연결망 H에 임베딩하면 G에서 개발된 알고리즘을 H에서 재사용 할 수 있어 알고리즘 개발 비용을 줄일 수 있다. 다양한 연결망들 사이의 임베딩에 관한 연구가 있다 [16 - 18] .
본 연구에서는 하프팬케익 그래프의 재귀적 확장성, 고장허용도, 임베딩을 분석하였다. 본 논문의 구성은 다음과 같다. 2장에서 본 논문에서 사용되는 용어들을 정의하고 하프팬케익 그래프, 버블정렬 그래프의 기본특성과 임베딩의 기본개념에 대해 살펴본다. 3장에서 하프팬케익 그래프의 재귀적 구조와 최대 고장 허용도를 갖는 연결도를 분석한다. 추가하여 하프팬케익 그래프와 버블정렬 그래프 상호간의 임베딩 가능함을 보이고 연장율과 확장율을 분석한다. 마지막으로 결론을 맺는다.
2. 관련연구
이 장에서는 하프팬케익 그래프와 버블정렬 그래프의 정의와 간단한 특성을 알아보고 임베딩의 개념과 임베딩 평가척도에 대해 살펴본다.
하프팬케익 그래프 HP n n !개의 노드와 분지수 ⌊ n /2⌋+1를 갖는 정규 연결망이다. HP n = ( Vp , Ep )라고 한다. 노드집합 Vp n 개의 자연수( n 보다 크지않은)로 이루어진 모든 순열이다. 에지집합 Ep Pn -에지와 Pk -에지로 나눌 수 있다. 임의의 노드 S = s 1 s 2 s 3 s n/2⌋ s n/2⌋+1 s n-1 s n 라고 할 때, 에지 정의는 다음과 같다.
PPT Slide
Lager Image
Pn -에지는 임의의 노드와 그 노드의 모든 심볼을 역순으로 바꾼 노드를 연결한다. Pk -에지는 임의의 노드와 그 노드의 맨 왼쪽부터 k 번째까지 심볼을 역순으로 바꾼 노드를 연결한다. 여기에서 k는 2보다 크거나 같고 ⌊ n /2⌋ +1적거나 같다. 본 연구에서는 노드의 주소가 순열로 표현되므로 노드 주소와 순열을 동일한 의미로 사용한다. 또한 임의의 노드 S 와 에지 Pn 에 의해 인접한 노드를 Pn ( S )라 하고, 에지 Pk 에 의해 인접한 노드를 Pk ( S )로 나타낸다. 노드 S 에서 에지 시퀜스 < Pk , Pn >를 경유한 노드는 Pn ( Pk ( S ))이다. 예를 들어 HP 5 에서 노드 S =52143에 인접한 노드는 P 5 ( S )=34125, P 3 ( S )=12543, P 2 ( S )=25143이다. Fig. 1 은 4차원 하프팬케익 그래프이다. 하프팬케익 그래프의 정의와 기본적인 성질은 [15] 에 있다.
PPT Slide
Lager Image
4-dimension Half Pancake HP4.
버블정렬 그래프 B n n! 개의 노드와 n! ( n -1)/2개의 에지로 구성된 분지수는 n -1인 정규그래프이다. B n = ( Vb , Eb )라고 한다. 노드집합 Vb n 개의 자연수( n 보다 크지 않은)로 이루어진 모든 순열이다. 임의의 노드 B = b 1 b 2 b 3 bi b i +1 b n -1 b n 라고 할 때, 에지 정의는 다음과 같다.
i -차원 에지 : ( b 1 b 2 b 3 bi b i+1 b n-1 b n , b 1 b 2 b 3 b i+1 bi b n-1 b n ), 단 1≤ i n -1이다.
i -차원에지는 임의의 노드와 그 노드에서 이웃한 위치의 심볼 bi b i+1 이 교환된 노드를 연결한다. 단 1≤ i n -1이다. 노드 B 에 인접한 i -차원에지 개수는 n -1개이므로 분지수는 n -1이고 에지수는 n! ( n -1)/2이다. B n 의 지름은 n ( n -1)/2이고 에지를 중심으로 그래프를 분할 할 수 있으므로 계층적 연결망이다. B n 은 노드 대칭적이고 에지 대칭적이다. 또한 이분 그래프(bipartite graph)이고 해밀튼 사이클을 포함한다 [15] . Fig. 2 는 4차원 버블정렬 그래프 이다.
PPT Slide
Lager Image
4-dimension Bubblesort B4.
상호연결망은 그래프 G =( V , E )로 모델링 될 수 있다. 상호연결망의 프로세서는 노드집합 V ( G )로 표현되고 프로세서간의 통신링크는 에지집합 E ( G )로 표현된다. 상호연결망 G H 에 임베딩 되면 G 에서 설계된 병렬 알고리즘을 상호연결망 H 에 적용할 수 있다. 상호연결망 G (guest)를 상호연결망 H (host)에 임베딩 f 한다는 것은 V ( G )를 V ( H )에 사상하고 에지 E ( G )를 H 의 경로(path)에 사상하는 것이다. 임베딩을 평가하는 척도에는 확장율(expansion), 부하계수(load factor), 연장율(dilation), 밀집율(congestion)이 있다.
임베딩 f 의 확장율 e 는 임베딩에 참여하는 V ( H )의 개수 / 임베딩에 참여하는 V ( G )의 개수이다. V ( G )의 하나의 노드가 V ( H )의 하나의 노드에 사상되면 일대일 임베딩이라고 하고 V ( G )의 하나의 노드가 V ( H )의 여러 개의 노드에 사상되면 일대다 임베딩이라고 하고 V ( G )의 여러 개의 노드가 V ( H )의 하나의 노드에 사상되면 다대일 임베딩이라고 한다. 다대일 임베딩에서 임베딩 함수 f 에 의해서 H 의 임의의 하나의 노드로 사상되는 G 의 노드의 수의 최대값을 f 의 부하계수 l 이라고 하고, 부하계수가 크면 하나의 프로세서에서 많은 작업이 이루어지므로 효율적이지 못하다. 확장율 e 가 1보다 같거나 크면 일대일 임베딩이나 일다대 임베딩이 가능하다. 일대다 사상은 연장율과 프로세서의 작업량을 줄여주는 효과가 있지만 프로세서가 낭비될 위험이 있다.
그래프 G 의 에지 e 의 연장율은 H 상에서의 경로 ρ( e )의 길이를 말하고, 임베딩 f 의 연장율은 G 의 모든 에지의 연장율 중 최대값이다. 연장율의 최소값은 1이며, 연장율이 크면 G 에서 설계된 알고리즘이 H 에서 적용될 때 연장율 만큼 메시지 전송 시간이 길어진다. 그래프 H 의 에지 e' 의 밀집율은 e' 에 포함되는 ρ( e )의 개수를 말하고, 임베딩 f 의 밀집율은 H 의 모든 에지의 밀집율 중 최대값이다. 밀집율의 최적은 1이며, 밀집율이 크면 전송 트래픽이 많이 발생한다. 연장율이 크면 store-and-forward 방식의 라우팅에서는 전송시간이 길어지고, 밀집율이 크면 웜홀 방식에서 메시지 교착(dead-lock)의 가능성이 증가한다.
3. 하프팬케익 그래프의 성질과 임베딩
이 장에서는 크게 세 가지 성질은 분석한다. 첫째 하프팬케익 그래프의 재귀적 확장성을 분석하고 둘째, 최대 고장 허용도를 가지는지 분석한다. 마지막으로 하프팬케익 그래프와 버블정렬 그래프의 사이의 임베딩 방법을 제시하고 임베딩의 연장율과 확장율을 계산한다. 먼저, 하프팬케익 그래프에서 노드 개수가 적은 연결망에서 노드 개수가 많은 연결망으로 확장 가능한지 알아보기 위해 재귀적 성질을 분석한다.
[성질 1] 하프팬케익 그래프 HP n 는 재귀적으로 확장된다( n ≥4).
증명 : 하프팬케익 그래프 HP n 에서 n 의 값에 따라 홀수와 짝수로 나누어 재귀적인 확장이 가능함을 보인다.
(경우 1) HP 2k 에서 HP 2k+1 로 확장( k ≥2)
2 k -차원 하프팬케익 그래프 HP 2k 의 임의의 노드 S 의 순열을 s 1 s 2 s 3 s ⌊(2k)/2⌋ s ⌊(2k)/2⌋+1 s 2k-1 s 2k 이라 하자. HP 2k 의 에지 정의에 의해 노드 S 에 인접한 에지의 개수는 k +1개 이다. 이중에서 k 개의 에지에 의해 인접한 노드는 P 2 ( S ), P 3 ( S ), P 4 ( S ), ..., Pk ( S ), P k+1 ( S )이고, 나머지 한 개의 노드는 P 2k ( S )에 의해 인접한 노드이다. (2 k +1)-차원 하프팬케익 그래프 HP 2k+1 의 임의의 노드 S 의 순열을 s 1 s 2 s 3 s ⌊(2k+1)/2⌋ s ⌊(2k+1)/2⌋+1 s 2k-1 s 2k s 2k+1 이라 하자. HP 2k+1 의 에지 정의에 의해 노드 S 에 인접한 에지의 개수는 k +1개다. 이중에서 k 개의 에지에 의해 인접한 노드는 P 2 ( S ), P 3 ( S ), P 4 ( S ), ..., Pk ( S ), P k+1 ( S )이고, 나머지 한 개의 노드는 P 2k+1 에 의해 인접한 노드이다. 따라서 2 k -차원 하프팬케익 그래프 HP 2k 에서 (2 k +1)-차원 하프팬케익 그래프 HP 2k+1 로 확장할 때 노드의 주소를 나타내는 순열의 원소 개수는 2 k 개에서 (2 k +1)개로 증가하여 노드의 개수는 (2 k )!에서 (2 k +1)!개로 증가하지만 한 노드에 부속한 에지의 개수는 k +1개로 변하지 않는다. 그렇지만 노드의 개수가 (2 k )!에서 (2 k +1)!개 증가하였으므로 증가된 노드를 연결하기 위해 HP 2k 의 에지 P 2k 를 대신하여 HP 2k+1 에서 에지 P 2k+1 가 사용된다.
(경우 2) HP 2k+1 에서 HP 2k+2 로 확장(k≥2)
(2 k +1)-차원 하프팬케익 그래프 HP 2k+1 의 임의의 노드 S 의 순열을 s 1 s 2 s 3 s ⌊(2k+1)/2⌋ s ⌊(2k+1)/2⌋+1 s 2k-1 s 2k s 2k+1 이라 하자. HP 2k+1 의 에지 정의에 의해 노드 S 에 인접한 에지의 개수는 k +1개 이다. 이중에서 k 개의 에지에 의해 인접한 노드는 p 2 ( S ), P 3 ( S ), P 4 ( S ), ..., Pk ( S ), P k+1 ( S )이고, 나머지 한 개의 노드는 P 2k+1 ( S )에 의해 인접한 노드이다. (2 k +2)-차원 하프팬케익 그래프 HP 2k+2 의 임의의 노드 S 의 순열을 s 1 s 2 s 3 s ⌊(2k+2)/2⌋ s ⌊(2k+2)/2⌋+1 s 2k+1 s 2k+2 이라 하자. HP 2k+2 의 에지 정의에 의해 노드 S에 인접한 에지의 개수는 k +2개 이다. 노드 S k +1개의 에지에 의해 인접한 노드는 P 2 ( S ), P 3 ( S ), P 4 ( S ), ..., Pk ( S ), P k+1 ( S ), P k+2 ( S )이고, 나머지 한 개의 노드는 P 2k+2 ( S )이다.
HP 2k+2 의 노드 S 에 인접한 에지 k +2개에서 k 개는 노드 { P 2 ( S ), P 3 ( S ), P 4 ( S ), ..., Pk ( S ), P k+1 ( S )}이고, HP 2k+1 의 에지 정의에 의해 노드 S 에 인접한 k 개의 노드와 동일하다. HP 2k+2 에서 나머지 2개중 한 개는 P 2k+1 ( S )-에지가 P 2k+2 ( S )-에지로 변경된 것이고, 나머지 한 개 P k+2 ( S )는 노드 개수가 증가함으로 새로 추가된 에지에 의해 인접한 노드이다. 따라서 (2 k +1)-차원 하프팬케익 그래프 HP 2k+1 에서 (2 k +2)-차원 하프팬케익 그래프 HP 2k+2 로 확장할 때 노드의 주소를 나타내는 순열의 원소 개수는 (2 k +1)개에서 (2 k +2)개로 증가하여 노드의 개수는 (2 k +1)!에서 (2 k +2)!개로 증가하고, 한 노드에 부속한 에지의 개수는 k +1개에서 k +2개로 증가한다. 이때 노드의 개수가 (2 k +1)!에서 (2 k +2)!개 증가하였으므로 증가된 노드를 연결하기 위해 HP 2k+1 의 에지 P 2k+1 를 대신하여 HP 2k+2 의 에지 P 2k+2 가 사용되고, 추가된 한 개의 에지는 P k+2 이다. HP 2k+1 의 에지 P ⌊(2k+1)/2⌋ +1 는 HP 2k+2 의 에지 P ⌊(2k+2)/2⌋ 와 동일하고, HP 2k+2 의 에지 P ⌊(2k+2)/2⌋ +1 은 추가된 에지이다. 따라서 HP n 에서 위의 (경우1)과 (경우2)에 의해 HP n 그래프의 차원이 증가할 때, n의 성질(홀수와 짝수)에 따라 2가지 경우로 나누어 재귀적인 확장이 가능하다는 사실을 알 수 있다.
상호연결망을 구성하는 노드 또는 에지에서 고장이 발생했을 때 연결망의 고장 감내 정도를 분석하는 척도로 고장허용도가 있다. 노드(에지) 연결도는 연결망을 노드 중복 없이 2개 이상의 부분 연결망으로 나누기 위해 제거해야 할 최소 노드(에지)의 개수이다. 주어진 연결망에서 임의의 k -1개 이하의 노드가 제거되더라도 연결망이 연결되어 있고, 적절한 k 개의 노드가 제거되었을 때 연결망이 분리되면 그 연결망의 연결도를 k 라 한다. 노드 연결도와 분지수가 같은 연결망을 최대 고장 허용도(maximally fault tolerance)를 가졌다고 한다. 연결망 G 의 노드 연결도, 에지 연결도, 분지수를 각각 k ( G ), λ( G ), 그리고 δ( G )로 하고, k ( G )≤λ( G )≤δ( G )인 사실이 알려져 있다 [9] . 정리 1에서 k ( HPn )=λ( HPn )=δ( HPn )임을 통하여 하프팬케익 그래프 HPn 이 최대 고장 허용도를 가짐을 보인다.
정리 1 . k ( HPn )=⌊ n /2⌋ +1, ( n ≥4).
증명 : 하프팬케익 그래프 HP n 에서 ⌊ n /2⌋ 개의 노드를 제거해도 HP n 그래프가 2개 이상으로 분할되지 않음을 보인다. (성질1)에서 하프팬케익 그래프 HP n 에는 (⌊ n /2⌋ +1)-차원 팬케익 그래프들이 존재함을 보였다. 본 연구에서는 증명의 편의를 위해 하프팬케익 그래프 HP n 에서 (⌊ n /2⌋ +1)-차원 팬케익 그래프를 하프팬케익 그래프의 모듈이라 하자. 하프팬케익 그래프 HP n 에서 모듈과 모듈을 연결하는 에지는 각 노드의 에지 Pn 이다. 하프팬케익 그래프 HP n 에서 제거할 노드 집합을 X 라 하고, 제거할 노드 집합의 개수 | X |=⌊ n /2⌋인 HP n 의 부분집합이라 하자. HP n 에서 X 를 제거한 연결망이 연결되어 있음을 통하여 k (HP n )≥⌊ n /2⌋+1임을 보인다. HP n 에서 X 를 제거한 부분 연결망을 HP n - X 로 나타낸다. HP n 에서 X 의 위치에 따라 2가지로 나누어 부분 연결망 HP n - X 가 항상 연결되어 있음을 보인다.
(경우 1) X 가 하나의 모듈에 위치한 경우
모듈을 구성하는 각 노드의 분지수는 ⌊ n /2⌋ +1이다. 모듈에 있는 임의의 노드 S 에 인접한 ⌊ n /2⌋ +1개의 노드가 제거될 노드 X 와 동일하다면 HP n 은 2개의 부분 연결망 HP n - X 와 한 개의 노드 S 로 분할된다. 그러나 모듈을 구성하는 모든 노드는 에지 Pn 에 의해 다른 모듈의 노드와 연결되어 있고, 제거된 노드가 없는 모듈도 에지 Pn 에 의해 다른 모듈과 연결되어 있으므로, HP n 에서 한 개의 모듈에 고장 노드 X 가 모두 위치하는 경우 부분 연결망 HP n - X 는 항상 연결되어 있다.
예를 들어 HP 4 에서 고장 노드 X 의 최대 개수는 2개이다. 고장난 2개 노드가 한 개의 모듈 즉, 3차원 HP 3 에서 모두 발생하고, 임의의 노드 S 에 모두 인접한 노드가 고장난 경우이다. Fig. 3 에서 노드 S =3142 이고, 고장이 발생한 2개 노드{1342, 4132}는 ***2인 모듈에 있으면서 노드 S 에 인접한 노드이다. 노드 S =3142는 에지 P 4 에 의해 P 4 ( S )=2413과 연결되어 있으므로 HP 4 는 연결된 그래프임을 알 수 있다.
PPT Slide
Lager Image
Fault nodes X are on the same module.
(경우 2) X 가 두 개 이상의 모듈에 위치한 경우
제거할 노드가 두 개 이상의 모듈에 분산되어 있으므로, 한 개의 모듈에서 제거되는 노드는 많아야 ⌊ n /2⌋ -1개이다. 모듈의 노드 분지수는 ⌊ n /2⌋ +1이므로 모듈의 노드 S 에서 인접한 ⌊ n /2⌋ -1개의 노드를 제거해도 노드 S 를 포함하는 모듈의 노드들은 연결되어 있음을 쉽게 알 수 있다. 제거할 나머지 한 개의 노드가 S 를 포함하지 않는 다른 모듈의 어떤 노드라 해도 HP n 은 연결되어 있음을 쉽게 알 수 있다.
예를 들어 HP 4 에서 고장 노드 X 의 최대 개수는 2개이다. 고장난 2개 노드가 2개 이상의 모듈 HP 3 에서 모두 발생한 경우이다. 한 개의 HP 3 에서에서 고장 노드의 최대 개수는 1개이다. Fig. 4 에서 노드 S =3142이고, 모듈 주소가 ***3과 ***2에서 고장난 노드 {2413, 4132}가 각각 1개씩 발생하였다. 노드 S =3142는 에지 P 2 에 의해 1342에 의해 연결되어 있으므로 HP 4 는 연결된 그래프임을 알 수 있다.
PPT Slide
Lager Image
Fault nodes X are on the different module.
그러므로 HP n 에서 어떤 위치에 있는 고장 노드 X 를 제거하여도 HP n 는 항상 연결되어 있으므로 k (HP n )≥⌊ n /2⌋ +1이고, HP n 은 분지수가 ⌊ n /2⌋ +1이므로 k (HP n )≤⌊ n /2⌋ +1이다. 따라서 k (HP n )≤⌊ n /2⌋ +1이다.
정리 2. 버블정렬 그래프 B n 을 하프팬케익 그래프 HP n 에 연장율 5, 확장율 1에 일대일 임베딩 가능하다.
증명 : n 개의 심벌 {1,2,3,..., n }을 이용하여 노드 주소 n !개를 표현하는 버블정렬 그래프 B n 와 하프팬케익 그래프 HP n 의 노드는 동일한 주소를 갖는 노드로 일대일 사상이 가능하다. 따라서 임베딩에 참여하는 노드 개수를 나타내는 확장율은 1이다.
두 그래프의 노드를 사상하는 방법은 버블정렬 그래프 B n 의 노드 B(= b 1 b 2 b 3 b i-1 bi b i+1 bn )를 하프팬케익 그래프 HP n 의 노드 P (= p 1 p 2 p 3 p i-1 pi p i+1 pn )로 사상한다. 따라서 일대일 임베딩이다. 버블정렬 그래프의 노드 B i -차원에지에 의해 연결된 노드 B' 를 하프팬케익 그래프 HP n 의 노드 P' 로 사상한다(1≤ i n -1). 이때 하프팬케익 그래프 HP n 의 노드 P 에서 P' 로 최단 경로로 라우팅하는데 필요한 에지 개수가 연장율이 된다. 임베딩의 연장율을 분석하기 위해 버블정렬 그래프의 i -차원에지의 경우를 3가지로 나누어 분석한다.
(경우 1) i -차원에지, 1≤ i n /2
버블정렬 그래프 B n 의 노드 B (= b 1 b 2 b 3 b i-1 bi b i+1 bn )와 i -차원에지, 1≤ i n /2+1에 의해 인접한 노드 i ( B )는 b 1 b 2 b 3 b i-1 b i+1 bi bn 이다. 하프팬케익 그래프 HP n 의 노드 P (= p 1 p 2 p 3 p i-1 pi p i+1 pn )에서 P' (= p 1 p 2 p 3 p i-1 p i+1 pi pn )까지 라우팅을 위해 적용해야 할 에지 시퀜스는 < p i+1 , p 2 , p i+1 >이다. 노드 P 에서 p i+1 -차원에지에 인접한 노드 p i+1 ( P )의 순열은 p i+1 pi p i-1 p 3 p 2 p 1 pn 이고, 순열 p i+1 ( P )에서 p 2 -차원에지에 인접한 노드 p 2 ( p i+1 ( P ))의 순열은 pi p i+1 p i-1 p 3 p 2 p 1 pn 이고, 순열 p 2 ( p i+1 ( P ))에서 p i+1 -차원에지에 인접한 노드 p i+1 ( p 2 ( p i+1 ( P )))의 순열은 p 1 p 2 p 3 p i-1 p i+1 pi pn 이다. 따라서 (경우1)처럼 버블정렬 그래프 B n 의 노드 B 를 하프팬케익 그래프 HP n 의 노드 P 로 사상하고 B' P' 로 사상할 때 연장율은 3이다.
(경우 2) i = ( n /2+1) -차원에지
버블정렬 그래프 B n 의 노드 B (= b 1 b 2 b 3 b n/2 b n/2+1 b n/2+2 bn )와 i -차원에지, i = ( n /2+1)에 의해 인접한 노드 i ( B )의 순열은 b 1 b 2 b 3 b n/2 b n/2+2 b n/2+1 bn 이다. 하프팬케익 그래프 HP n 의 노드 P (= p 1 p 2 p 3 p n/2 p n/2+1 p n/2+2 pn )에서 P' (= p 1 p 2 p 3 p n/2 p n/2+2 p n/2+1 pn )까지 라우팅을 위해 적용해야 할 에지 시퀜스는 < p n , p n/2+1 , p 2 , p n/2+1 , p n >이다. 노드 P (= p 1 p 2 p 3 p n/2 p n/2+1 p n/2+2 pn )에서 p n -차원에지에 인접한 노드 p n ( P )의 순열은 p n p n/2+2 p n/2+1 p n/2 p 3 p 2 p 1 이고, 순열 p n ( P )에서 p n/2+1 -차원에지에 인접한 노드 p n/2+1 ( p n ( P ))의 순열은 p n/2+1 p n/2+2 p n p n/2 p 3 p 2 p 1 이고, 순열 p n/2+1 ( p n ( P ))에서 p 2 -차원에지에 인접한 노드 p 2 ( p n/2+1 ( p n ( P )))의 순열은 p n/2+2 p n/2+1 p n p n/2 p 3 p 2 p 1 이다. 논문의 기술 편의상 순열 K = p 2 ( p n/2+1 ( p n ( P )))이라고 가정한다. 순열 K 에서 p n/2+1 -차원에지에 인접한 노드 p n/2+1 ( K )의 순열은 p n p n/2+1 p n/2+2 p n/2 p 3 p 2 p 1 이고, 순열 p n/2+1 ( K )에서 p n -차원에지에 인접한 노드 p n ( p n/2+1 ( K ))의 순열은 p 1 p 2 p 3 p n/2 p n/2+2 p n/2+1 pn 이다. 따라서 (경우2)처럼 버블정렬 그래프 B n 의 노드 B 를 하프팬케익 그래프 HP n 의 노드 P 로 사상하고 B' P' 로 사상할 때 연장율은 5이다.
(경우 3) i ≥( n /2+2)-차원에지
버블정렬 그래프 B n 의 노드 B (= b 1 b 2 b 3 b i-1 bi b i+1 bn )와 i -차원에지, i ≥( n /2+2)에 의해 인접한 노드 B' ( B )는 b 1 b 2 b 3 b i-1 b i+1 bi bn 이다. 하프팬케익 그래프 HP n 의 노드 P (= p 1 p 2 p 3 p i-1 pi p i+1 pn )에서 P' (= p 1 p 2 p 3 p i-1 pi p i+1 pn )까지 라우팅을 위해 적용해야 할 에지 시퀜스는 < pn , p n-(i+1) , p 2 , p n-(i+1) , p n >이다. 노드 P (= p 1 p 2 p 3 p i-1 p i p i+1 pn )에서 p n -차원에지에 인접한 노드 p n ( P )의 순열은 p n p i+1 p i p i-1 p 3 p 2 p 1 이고, 순열 p n ( P )에서 p n-(i+1) -차원에지에 인접한 노드 p n-(i+1) ( p n ( P ))의 순열은 p i p i+1 p n p i-1 p 3 p 2 p 1 이고, 순열 p n-(i+1) ( p n ( P ))에서 p 2 -차원에지에 인접한 노드 p 2 ( p n-(i+1) ( p n ( P )))의 순열은 p i+1 p t p n p i-1 p 3 p 2 p 1 이다. 논문 기술의 편의상 순열 K = p 2 ( p n-(i+1) ( p n ( P )))이라고 가정하자. 순열 K 에서 p n-(i+1) -차원에지에 인접한 노드 p n-(i+1) ( K )의 순열은 p n p i p i+1 p i-1 p 3 p 2 p 1 이고, 순열 p n-(i+1) ( K )에서 p n -차원에지에 인접한 노드 p n ( p n/2+1 ( K ))의 순열은 p 1 p 2 p 3 p i-1 p i+1 p i pn 이다.
따라서 (경우3)처럼 버블정렬 그래프 B n 의 노드 B 를 하프팬케익 그래프 HP n 의 노드 P 로 사상하고 B' P' 로 사상할 때 연장율은 5이다.
정리 3. 하프팬케익 그래프 HP n 를 버블정렬 그래프 B n 에 임베딩 하는 연장율은 O ( n 2 )이다.
증명 : 하프팬케익 그래프 HP n 의 에지는 Pn Pk , 2 ≤ k ≤ ⌊ n /2⌋ +1 이고 분지수는 ⌊ n /2⌋ +1이다. 하프팬케익 그래프 HP n 의 노드 P (= p 1 p 2 p 3 p i-1 pi p i+1 pn )에서 에지 Pn 에 의해 인접한 노드 P' (= pn p i+1 p i p i-1 p 3 p 2 p 1 )이다. 즉 노드 P 와 에지 Pn 에 의해 인접한 노드 P' 의 순열은 노드 P 순열의 역순으로 되어 있음을 알 수 있다.
버블정렬 그래프 B n 의 라우팅 방법은 정렬과 연결하여 생각할 수 있다. 버블정렬 그래프 B n 의 노드 B (= b 1 b 2 b 3 b i-1 bi b i+1 bn )에서 n 번째 위치를 가장 먼저 정렬하고, 다음에는 ( n -1)번째 위치를 정렬하고, ( n -2), ( n -3), ..., 3, 2번째 위치 순서로 정렬하는 방식이다. 따라서 노드 B (= b 1 b 2 b 3 b i-1 bi b i+1 bn )의 순서를 뒤집어 놓은 순열 b n b n-1 b i+1 b i b i-1 b 2 p 1 이 노드 B 와 가장 멀리 떨어져 있음을 알 수 있다. 이처럼 순열의 순서가 뒤집혀 있는 두 노드간의 최단 경로 라우팅 거리는 버블정렬 그래프의 지름 값인 n ( n -1)/2에 해당한다. 따라서 하프팬케익 그래프 HP n 를 버블정렬 그래프 B n 에 임베딩 하는 연장율은 O ( n 2 )임을 알 수 있다.
4. 결 론
스타 부류 상호연결망에서 팬케익 정렬 문제로부터 출발하여 팬케익 그래프가 제안되었으며, 팬케익그래프에서 전위 합 문제, 정렬과 합병 알고리즘, 지름과 방송 알고리즘, 병렬 라우팅과 부하균등 문제, 임베딩 등 다양한 성질과 알고리즘들이 발표되었다.
본 연구에서는 팬케익 그래프의 망비용을 개선한 하프팬케익 그래프를 대상으로 고장허용도, 재귀적 확장성, 팬케익 및 버블정렬 그래프 사이의 임베딩을 분석하였다. 연구 결과로 하프팬케익 그래프는 최대 고장 허용도와 재귀적 확장성이 있다. 따라서 하프팬케익 그래프는 고장에 강한 연결망이고 노드수를 확장할 때 하드웨어 비용이 적게 든다. 추가로 하프팬케익 그래프 HP n 에는 (⌊ n /2⌋ +1)-차원 팬케익 그래프 P ⌊n/2⌋ +1 와 동형인 그래프가 많이 존재하고 있음을 보였다. 이 결과로 팬케익 그래프에서 개발된 알고리즘은 하프팬케익 그래프의 서브 그래프에서 사용 될 수 있다. 마지막으로 버블정렬 그래프 B n 을 하프팬케익 그래프 HP n 에 연장율 5, 확장율 1에 임베딩 하였다. 이 결과는 버블정렬 그래프에서 개발된 여러 가지 알고리즘을 하프팬케익 그래프에서 상수의 추가 비용을 통해 활용할 수 있음을 의미한다. 팬케익 그래프가 설계된 후, 본 연구에서 기본적인 몇 가지 성질을 분석하였다. 설계된 그래프가 병렬 컴퓨터로 상용화되기 위해 적응 라우팅, 고장 허용 라우팅, 일대다 방송, 다대다 방송, 병렬 경로, 작업 할당 알고리즘, 데이터 마이그레이션 알고리즘 등 응용 알고리즘에 대한 연구가 필요하다.
BIO
서 정 현
2008년 8월 순천대학교 컴퓨터과학과 박사
2009년~현재 순천대학교 과학교육연구소
관심분야 : 그래프이론, 알고리즘
이 형 옥
1999년 2월 전남대학교 전산학과 박사
2002년 3월~현재 순천대학교 컴퓨터교육과 교수
관심분야 : 그래프이론, 알고리즘
References
Seo J.H. 2013 “Three-dimensional Petersen-torus Network: a Fixed-degree Network for Massively Parallel Computers” Journal of Supercomputing 64 (3) 987 - 1007    DOI : 10.1007/s11227-011-0716-z
Hosseinzadeh F. , Bagherzadeh N. , Khademzadeh A. , Janidarmianm M. 2014 “Fault-Tolerant Optimization for Application-Specific Network-on-Chip Architecture” LNEE 247 (2014) 363 - 381
Thatte G. , Mitra U. 2008 “Sensor Selection and Power Allocation for Distributed Estimation in Sensor Networks: Beyond the Star Topology” IEEE Transactions on Signal Processing 56 (7) 2649 - 2661    DOI : 10.1109/TSP.2008.917038
Isaac E. , Hartman T. 2006 “A 1.375-Approximation Algorithm for Sorting by Transpositions“ IEEE/ACM Transactions on Computational Biology and Bioinfomatics 3 (4) 369 - 379    DOI : 10.1109/TCBB.2006.44
Hu X. , Liu H. 2013 “The (Conditional) Matching Preclusion for Burnt Pancake Graphs” Discrete Applied Mathematics 161 (10) 1481 - 1489    DOI : 10.1016/j.dam.2013.01.010
Saad Y. , Schultz M.H. 1988 “Topological Properties of Hypercubes” IEEE Transactions on Computers 37 (7) 867 - 872    DOI : 10.1109/12.2234
Mendia V.E. , Sarkar D. 1992 “Optimal Broadcasting on the Star Graph” IEEE Transactions on Parallel and Distributed Systems 3 (4) 389 - 396    DOI : 10.1109/71.149958
Tang K.W. , Padubidri S.A. 1994 “Diagonal and toroidal Mesh Networks” IEEE Transactions on Computers 43 (7) 815 - 826    DOI : 10.1109/12.293260
Saad Y. , Schultz M.H. 1988 “Topological Properties of Hypercubes” IEEE Transactions on Computers 37 (7) 867 - 872    DOI : 10.1109/12.2234
Decayeux C. , Seme D. 2005 “3D Hexagonal Network: Modeling, Topological Properties, Addressing Scheme, and Optimal Routing Algorithm” IEEE Transactions on Parallel and Distributed Systems 16 (9) 875 - 884    DOI : 10.1109/TPDS.2005.100
Choo H. , Yoo S.M. , Youn H.Y. 2000 “Processor Scheduling and Allocation for 3D Torus Multicomputer Systems” IEEE Transactions on Parallel and Distributed Systems 11 (5) 475 - 484    DOI : 10.1109/71.852400
Yeh C.H. , Varvarigos E.A. 1998 “Macro-Star Networks: Efficient Low-Degree Alternatives to Star Graphs” IEEE Transactions on Parallel and Distributed Systems 9 (10) 987 - 1003    DOI : 10.1109/71.730528
Konstantinova E. 2013 "On Some Structural Properties of Star and Pancake Graphs" LNCS 7777 (2013) 472 - 487
Kim M.H. , Kim D.Y. , Lee H.O. 2010 “Embedding Algorithms for Star, BubbleSort. Rotator-Faber-Moore, and Pancake Graphs” LNCS 6082 348 - 357
Kim J. , Master’s Thesis of University of Sunchon. 2014 Design and Analysis for Half Pancake Master’s Thesis of University of Sunchon.
Hsieh S.Y. 2005 "Embedding of Cycles in the Faulty Hypercube" LNCS 3740 (2005) 229 - 235
Cortese P.F. , Battista G.D. 2005 "On Embedding a Cycle in a Plane Graph" GD2005, LNCS 3843 49 - 60
Kim J. , Cho C. , Lee H. 2008 “Analysis of Topological Properties and Embedding for Folded Hyper-Star Network” Journal of Korea Multimedia Society 11 (9) 1227 - 1237