최근 이미지 파일, 동화상, 실시간 처리 등의 많은 응용 분야에서 고성능의 컴퓨터에 대한 요구가 증가하고 있다. 고성능을 얻기 위한 방법으로 병렬처리에 대한 필요성이 크게 증가하여 병렬처리 컴퓨터에 대한 연구가 많이 진행되고 있다. 병렬처리 컴퓨터는 다중프로세서 시스템과 다중컴퓨터 시스템으로 분류하는데 다중 컴퓨터 시스템은 자신의 기억장치를 갖는 프로세서들을 상호 연결망으로 연결하고, 프로세서들 간의 통신은 상호 연결망을 통하여 메시지 전송 방식으로 구동되는 시스템이다. 상호 연결망은 전체 시스템의 성능과 시스템의 확장성에 큰 영향을 미친다. 널리 알려진 상호 연결망으로 메쉬, 하이퍼큐브, 스타 그래프 등이 있다.

상호연결망에서 메쉬 구조는 평면그래프로서 VLSI회로 설계 같은 분야에서 많이 이용되는 구조로 현재까지 널리 이용되고 있으며 다양한 시스템으로 상용화되었다. 이러한 메쉬 구조에서 지름과 고장허용도를 개선한 상호연결망이 토러스 구조인데, 토러스는 메쉬의 행과 열에 하나의 에지를 추가하여 각각의 행과 열이 링형태를 갖는 연결망이다. 이러한 토러스 구조는 MPP (Goodyear Aerospace), MP-I(MASPAR), Victor(IBM), Paragon(Intel), T3D(Cray) 등에 상용화되어 사용되고있다[1].

최근에 새로운 상호연결망으로 하이퍼-토러스 네트 워크QT(m,n)가 제안되었다[2]. QT(m,n)는 3차원 하이퍼큐브를 기본 모듈로 갖고 분지수가 4인 상호연결망이다. QT(m,n)는 기존에 발표된 메쉬 구조를 갖는 상호연 결망보다 망비용이 더 개선되었다. 지금까지QT(m,n)의 여러 가지 성질들 - 지름, 분지수, 대칭성, 이분할에 지수, 방송, 해밀토니안 사이클 - 이 발표되었다[2,3].

상호연결망의 다양한 구조에서 여러 가지 문제들을 풀기 위해 병렬 알고리즘들이 설계되었다. 이미 개발된 알고리즘들을 원래와는 다른 연결망 구조에서 실행시킬 수 있는 방법이 있다면 개발된 알고리즘을 효율적으로 활용할 수 있는 장점이 있을 것이다. 이러한 연구 분 야 중 임베딩 분석이 널리 사용되고 있다[4-7]. 임베딩은 한 연결망의 프로세서와 통신링크를 다른 연결망의 프로세서와 통신링크들로 사상(mapping)시키는 방법을 일컫는다.

본 논문에서는 토러스와 하이퍼-토러스 네트워크 사이의 임베딩을 분석한다.

토러스 T(4k,2l)는 8kl개의 노드로 구성된 연결망으로 각 노드의 주소는 (a,b)로 표현된다(1≤k,l, 0≤a≤4k-1, 0≤b≤2l-1, a,b=정수). 노드 주소 (a,b)에서 a는 X축 좌표, b는 Y축 좌표를 나타낸다. T(4k,2l)의 노드 (a,b)에 인접한 두 노드 U와 V를 연결하는 에지는 다음과 같다. (a,b)-((a+1)%4k,b), (a,b)-((a-1+4k)%4k,b), (a,b)-(a,(b+1)%2l), (a,b)-(a,(b-1+2l)%2l). 심벌 ‘%’는 나머지 연산자이다.

3차원 하이퍼큐브 Q₃는 8개의 노드로 구성되었으며, 노드 주소는 3개의 이진비트스트링으로 표현되며, 주소에서 1비트가 다른 두 노드 사이에 에지가 발생한다.

하이퍼-토러스 연결망 QT(m,n)은 Q₃를 기본 모듈로삼는 m×n 토러스 연결망이다(1≤m,n). QT(m,n)의 에지는 외부에지와 내부에지로 구성된다. 내부에지는 Q₃를 구성하는 에지이고, 외부에지는 모듈과 모듈을 연결하는 에지이다. 각 모듈의 주소는 (x,y), 각 노드의 주소는 (x,y,q)로 나타낸다. x는 X축 좌표, y는 Y축 좌표, q는 기본 모듈 Q₃에 있는 노드 주소를 나타낸다. 외부에지는 다음과 같다.

① 세로 에지: ((x,y,101), (x,(y+1)%n,001))과 ((x,y,001), (x,(y-1+n)%n,101)). ② 가로 에지: ((x,y,111), ((x+1)%m,y,011))과 ((x,y,011), ((x-1+m)%m,y,111)). ③ 사선 에지: ((x,y,110), ((x+1)%m,(y+1)%n,010))과 ((x,y,010), ((x-1+m)%m,(y-1+n)%n, 110)). ④ 역사선 에지: ((x,y,000), ((x-1)%m,(y+1+n)%n,100))과 ((x,y,100), ((x+1+m)%m,(y-1)%n,000)).

임의의 한 연결망을 G라고 할 때, G의 노드 집합을 V(G), 에지 집합을 L(G), 경로 집합을 P(G)로 표현하겠다. 연결망 G(V,L)를 G'(V',L')로 임베딩 하는 함수 (Φ,ρ)은 V(G)의 노드들을 V'(G')의 노드들로 사상하고, L(G)의 에지들을 P(G')의 경로들로 사상하는 것을 말한다. 즉, Φ: V→V'이고, ρ: L→P(G')이다. 임베딩의 비용을 나타내는 척도로 연장율과 밀집율과 확장율이 있다. 연장율은 G의 한 에지가 G'에 사상되었을 때 경로 길이를 나타내고, 밀집율은 G'의 한 에지가 임베딩을 위해 사용된 횟수를 나타내며, 확장율은 G의 노드의 개수에 대한 G'의 노드의 개수의 비율이다.

메쉬 구조 4×2는 Q₃의 서브연결망임을 그림 1과 2에 의해 쉽게 알 수 있다. 그러므로 다음과 같은 보조정리를 구할 수 있다.

보조정리 1 메쉬 구조 4×2는 Q₃에 연장율 1, 확장율 1, 밀집율 1로 임베딩 가능하다.

임베딩을 위해 Q₃의 노드 주소를 그림 3과 같이 정수로 나타내겠다.

증명을 위해 토러스 T(4k,2l)의 노드 (a,b)의 노드 주소를 다음과 같이 정의하겠다. 노드 이다. 주소에서 b가 짝수이면 q=a%4이고, b가 홀수이면 q=(a%4)+4이다. 라고 하자. 그러면 동일한 주소 (x,y)를 갖는 노드의 개수는 8개 가 되고, 이 8개의 노드로 구성되는 연결망은 4×2 메쉬구조가 된다. 그리고 토러스 T(4k,2l)를 구성하는 4×2 메쉬의 개수는 k×l이다. 본 논문에서 사용하는 라우팅 경로(routing path)의 표현은 다음과 같다. 예를 들어 임의의 3개 노드 {(x,y,4), (x,y,5), (x,y,6)}에서 노드 (x,y,4)에서 출발하여 노드 (x,y,5)를 경유하고, 도착 노드가 (x,y,6)인 경우 라우팅 경로는 (x,y,4)-(x,y,5)-(xx,y,6)로 표현하였다. 즉 노드와 노드 사이의 하이픈(-)은 2개 노드를 연결하는 에지를 나타낸다. 위의 라우팅 경로에서 (x,y,4)-(x,y,5)은 노드 (x,y,4)과 (x,y,5)를 연결하는 한 에지를 의미한다.

정리 1 토러스 T(4k,2l)는 QT(m,n)에 연장율 5, 밀집율 4, 확장율 1에 임베딩 가능하다(k=m, l=n).

증명 토러스 T(4k,2l)의 노드 (a,b)=(x,y,q)는 QT(m,n)의 노드에 다음과 같이 임베딩한다.

Φ(a,b)=(x,y,q), b가 짝수이면 q=a%4이고, b가 홀수이면 q=(a%4)+4이다. 위의 임베딩 기법을 이용하면 T(4k,2l)의 각 4×2 메쉬는 QT(m,n)의 기본 모듈인 Q₃에 각각 임베딩 된다. 4×2 메쉬 내부의 에지가 Q₃의 내부 에지에 임베딩 되는 경우는 보조정리 1에 의해 연장율 1, 밀집율 1, 확장율 1임을 알 수 있으므로 본 증명에서는 4×2 메쉬와 4×2 메쉬를 연결하는 에지의 임베딩만을 증명한다. 노드 V와 인접한 노드 W의 조건식에 따라 다음의 2가지 경우로 나누어 증명하겠다.

경우 1) V=(a,b)와 W=(a,(b+1)%2l)가 인접한 경우: Φ(V)=(x,y,(a%4)+4)이고, Φ(W)= (x,(y+1)%n,a%4)이다.

경우 1-1) (a%4)+4=4인 경우: Φ(V)=(x,y,4)와Φ(W)=(x,y+1,0) 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x, y, 4) - (x, y, 5) - (x, y, 6) - (x, (y+1)%n, 5) - (x,(y+1)%n,4)-(x,(y+1)%n,0). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.

경우 1-2) (a%4)+4=5인 경우: Φ(V)=(x,y,5)와 Φ(W)=(x,y+1,1) 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,5)-(x,y,6)-(x,(y+1)%n,5)-x,(y+1)%n,1). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.

경우 1-3) (a%4)+4=6인 경우: Φ(V)=(x,y,6)와 Φ(W)=(x,y+1,2)사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,6)-(x,y+1,5)-(x,(y+1)%n,1)-(x,(y+1)%n,2). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.

경우 1-4) (a%4)+4=7인 경우: Φ(V)=(x,y,7)와 Φ(W)=(x,y+1,3)사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,7)-(x,y,6)-(x,(y+1)%n,5)-(x,(y+1)%n,6)-(x,y+1,7)-(x,(y+1)%n,3). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.

위의 4가지 경우의 각 경로 ρ(Φ(V),Φ(W)) 상에는 에지 (x,y,6)-(x,(y+1)%n,5)이 모두 사용되었음을 알 수 있다. 그러므로 경우 1의 밀집율은 4임을 알 수 있다.

경우 2) V=(a,b)와 W=((a+1)%4k,b)가 인접한 경우:

경우 2-1) b가 짝수인 경우: Φ(V)=(x,y,3)이며, Φ(W)=((x+1)%m,y,0)이므로 두 노드 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,3)-(x,y,2)-((x+1)%m,y,1)-((x+1)%m,y,0). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.

경우 2-2) b가 홀수인 경우: Φ(V)=(x,y,7)이며, Φ(W)=((x+1)%m,y,4)이므로 두 노드 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,7)-(x,y,3)-(x,y,2)-((x+1)%m,y,1)-((x+1)%m,y,0)-((x+1)%m,y,4). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.

위의 2가지 경우에 의해 경우 2의 밀집율은 2임을 알 수 있다. 그러므로 토러스 T(4k,2l)는 QT(m,n)에 연장율 5, 밀집율 4, 확장율 1에 임베딩 가능하다.

정리 2 QT(m,n)는 T(4k,2l)에 연장율 3, 밀집율 3, 확장율 1에 임베딩 가능하다(k=m, l=n).

증명 QT(m,n)의 노드 (x,y,q)는 T(4k,2l)의 노드에 다음과 같이 임베딩 한다. Φ((x,y,q))=(x,y,q)=(a,b). 위의 임베딩 기법을 이용하면 QT(m,n)의 기본 모듈인 Q₃는 T(4k,2l)의 4×2 메쉬에 각각 임베딩 된다. 다음의 2가지 경우로 나누어 증명하겠다.

경우 1) 내부에지가 임베딩 되는 경우:

경우 1-1) 노드 V=(x,y,0)의 인접 노드가 W=(x,y,3)인 경우: Φ(V)=(x,y,0)=(a,b)이고, Φ(W)=(x,y,3)=((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).

경우 1-2) 노드 V=(x,y,4)의 인접 노드가 W=(x,y,7)인 경우: Φ(V)=(x,y,4)=(a,b)이고, Φ(W)=(x,y,7)= ((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).

경우 1-3) 경우 1-1)과 1-2)를 제외한 Q₃의 나머지 내부 에지가 임베딩되는 경우: 노드 (x,y,0)과 (x,y,3)을 연결하는 에지와 노드 (x,y,4)와 (x,y,7)은 연결하는 에지를 제거한 Q₃는 4×2 메쉬 구조임을 쉽게 알 수 있으므로 이 경우 연장율이 1임을 알 수 있다.

경우 2) 외부에지가 임베딩 되는 경우:

경우 2-1) V=(x,y,0)와 W=((x-1+m)%m, (y-1+n)%n,3)가 인접한 경우: Φ(V)=(x,y,0)=(a,b)이고, Φ(W)=((x-1+m)%m, (y-1+n)%n, 3) =((a-1+4k)%4k, (b-2+2l)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a-1+4k)%4k,(b-2+2l)%2l).

경우 2-2) 노드 V=(x,y,1)의 인접 노드가 W=((x-1+m)%m,y,2)인 경우: Φ(V)=(x,y,1)=(a,b)이고, Φ(W)=((x-1+m)%m,y,2)=((a-3+4k)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a-1+4k)%4k,b)-((a-2+4k)%4k,b)-((a-3+4k)%4k,b).

경우 2-3) 노드 V=(x,y,2)의 인접 노드가 W=((x+1)%m,y,1)인 경우: Φ(V)=(x,y,2)=(a,b)이고, Φ(W)=((x+1)%m,y,1)=((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).

경우 2-4) 노드 V=(x,y,3)의 인접 노드가 W=((x+1)%m,(y+1)%n,0)인 경우: Φ(V)=(x,y,3)=(a,b)이고, Φ(W)=((x+1)%m,(y+1)%n,0)=((a+1)%4k,(b+2)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l)-((a+1)%4k,(b+2)%2l).

경우 2-5) 노드 V=(x,y,4)의 인접 노드가 W=((x-1+m)%m,(y+1)%n,7)인 경우: Φ(V)=(x,y,4)=(a,b) 이고, Φ(W)=((x-1+m)%m,(y+1)%n,7)=((a-1+4k)%4k, (b+2)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l)-((a-1+4k)%4k,(b+2)%2l).

경우 2-6) 노드 V=(x,y,5)의 인접 노드가 W=(x,(y-1+n)%n,6)인 경우: Φ(V)=(x,y,5)=(a,b)이고, Φ(W)=(x,(y-1+n)%n,6)=((a+1)%4k,(b-2+2l)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a+1)%4k,(b-2+2l)%2l).

경우 2-7) 노드 V=(x,y,6)의 인접 노드가 W=(x,(y+1)%n,5)인 경우: Φ(V)=(x,y,6)=(a,b)이고, Φ(W)=(x,(y+1)%n,5)=((a-1+4k)%4k,(b+2)%2l)이다. ρ(Φ(V), Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l )-((a-1+4k)%4k,(b+2)%2l).

경우 2-8) 노드 V=(x,y,7)의 인접 노드가 W=((x+1)%m,(y-1+n)%n,4)인 경우: Φ(V)=(x,y,4)=(a,b)이고, Φ(W)=((x+1)%m,(y-1+n)%n,4)=((a+1)%4k, (b-2+2l)%2l)이다. ρ(Φ(V), Φ(W))=(a, b) - (a, (b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a+1)%4k, (b-2+2l)%2l).

위의 8가지 경우의 각 경로 ρ(Φ(V),Φ(W))의 연장율은 3이다. 에지 (x,y,0)-(x,y,1)은 경우 1-1), 1-3), 2-2)에서 사용되었으며, 에지 (x,y,2)-(x,y,3)은 경우 1-1), 1-3), 2-3)에서 사용되었으며, 에지 (x,y,3)-(x,y,7)은 경우 1-3), 2-4), 2-8)에서 사용 되었으므로 밀집율은 3임을 알 수 있다. 그러므로 QT(m,n)는 T(4k,2l)에 연장율 3, 밀집율 3, 확장율 1에 임베딩 가능하다.

본 논문에서는 토러스 T(4k,2l)와 하이퍼-토러스 네트워크 QT(m,n) 사이의 임베딩을 분석하였다. T(4k,2l)는 QT(m,n)에 연장율 5, 밀집율 4, 확장율 1에 임베딩 가능함을 보였다. 그리고 QT(m,n)은 T(4k,2l)에 연장율 3, 밀집율 3, 확장율 1에 임베딩 가능함을 보였다. 이러한 연구 결과는 T(4k,2l)와 QT(m,n)에서 개발된 많은 알고리즘을 QT(m,n)와 T(4k,2l)에서 적은 비용을 추가하여 활용할 수 있음을 의미한다.