| 한글제목(Korean Title) |
2^(2n-k)×2k 토러스와 HFN(n,n), HCN(n,n) 사이의 임베딩 알고리즘 |
| 영문제목(English Title) |
Embedding Algorithm between 2^(2n-k)×2k Torus and HFN(n,n), HCN(n,n) |
| 저자(Author) |
김종석
강민식
Jong-Seok Kim
Min-Sik Kang
|
| 원문수록처(Citation) |
VOL 14-A NO. 06 PP. 0327 ~ 0332 (2007. 12) |
한글내용
(Korean Abstract) |
본 논문에서는 2^(2n-k×2k) 토러스 연결망과 상호연결망 HFN(n,n)과 HCN(n,n) 사이의 임베딩을 분석한다. 먼저, 2^(2n-k×2k) 토러스를 HFN(n,n)에 연장율 3과 밀집율 4로 임베딩 가능함을 보이며, 평균연장율이 2 이하임을 증명한다. 그리고 2^(2n-k×2k) 토러스를 HCN(n,n)에 연장율 3으로 임베딩 가능함을 보이며, 평균 연장율이 2 이하임을 증명한다. 또한 HFN(n,n)과 HCN(n,n)이 2^(2n-k×2k) 토러스에 임베딩하는 연장율이 O(n)임을 보인다. 이러한 결과는 토러스에서 개발된 여러 가지 알고리즘을 HCN(n,n)과 HFN(n,n)에서 효율적으로 이용할 수 있음을 의미한다.
|
영문내용
(English Abstract) |
In this paper, we will analysis embedding between 22n-k×2k torus and interconnection networks HFN(n,n), HCN(n,n). First, we will prove that 22n-k×2k torus can be embedded into HFN(n,n) with dilation 3, congestion 4 and the average dilation is less than 2. And we will show that 22n-k×2k torus can be embedded into HCN(n,n) with dilation 3 and the average dilation is less than 2. Also, we will prove that interconnection networks HFN(n,n) and HCN(n,n) can be embedded into 22n-k×2k torus with dilation O(n). These results mean so many developed algorithms in torus can be used efficiently in HFN(n,n) and HCN(n,n).
|
| 키워드(Keyword) |
토러스
HFN(n,n)
HCN(n,n)
임베딩
Torus
embedding
|
| 파일첨부 |
PDF 다운로드
|
