본문 바로가기
KERD
논문KCI 등재

상호연결망 폴디드 하이퍼-스타 FHS(2n,n)의 대칭성과 임베딩 알고리즘

Symmetry and Embedding Algorithm of Interconnection Networks Folded Hyper-Star FHS(2n,n)

김성원|김종석|이형옥
한국정보처리학회|2009.12|정보처리학회논문지. 컴퓨터 및 통신시스템 (KIPS Transactions on Computer and Communication Systems)|제16권 제6호|pp. 501-508

0

조회

0

다운로드

2

인용

0

참고문헌

키워드

임베딩Embedding폴디드 하이퍼-스타 연결망노드 대칭성이분할 연결망Folded Hyper-Star NetworkNode SymmetryBipartite Network
주제분류컴퓨터학

초록

본 논문에서는 상호연결망 폴디드 하이퍼-스타 연결망 FHS(2n,n)이 노드 대칭임을 증명하고, 이분할 연결망임을 증명한다. FHS(2n,n)이 오드 연결망 On+1에 연장율 2, 밀집율 1로 임베딩 가능함을 보이고, 오드 연결망 Od이 FHS(2d,d)에 연장율 2, 밀집율 1로 임베딩 가능함을 보인다. 또한 2n×n 토러스가 FHS(2n,n)에 연장율 2, 밀집율 2로 임베딩 가능함을 보인다.

Abstract

In this paper, we prove that folded hyper-star network FHS(2n,n) is node-symmetric and a bipartite network. We show that FHS(2n,n) can be embedded into odd network On+1 with dilation 2, congestion 1 and Od can be embedded into FHS(2n,n) with dilation 2 and congestion 1. Also, we show that 2n×n torus can be embedded into FHS(2n,n) with dilation 2 and congestion 2.

참고문헌 (18)

  1. S. B. Akers, "The star graph: An attractive alternative to the n‐cube", Proc. of the Int. Conf. Parallel Processing, pp.216~223 (1986)
  2. N. Biggs, "Some Odd Graph Theory", Annals of New York Academy of Sciences, 319, pp.71~81 (1979)
  3. E. Cheng, "Structural properties of hyper- stars", Ars Combinatoria, 80, pp.65~73 (2006)
  4. E. Cheng, "A strong structural theorem for hyper-stars", Congressus Numerantium, 179, pp.181~191 (2006)
  5. W. Dally, "The Torus Routing Chip", Distrib. Comput, 1, pp.187~196 (1986)
  6. Q. Dong, "Embedding A Family of Disjoint 3D Meshes into A Crossed Cube", Information Sciences, 178(11), pp.2396~2405 (2008)
  7. J. Fan, "Embedding Meshes into Crossed Cubes", Information Sciences, 177(15), pp.3151~3160 (2007)
  8. A. Ghafoor, "A Study of Odd Graphs as Fault-Tolerant Interconnection Networks", IEEE Trans. Computers, 40(2), pp.225~232 (1991)
  9. J.-S. Kim, "Embedding hypercubes, rings and odd graphs into Hyper-stars", International Journal of Computer Mathematics, 86(5), pp.771~778 (2009)
  10. H.-O. Lee, "Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube", Lecture Notes in Computer Science : EurAsia-ICT 2002, 통권 : 2510, pp.858~865 (2002)
  11. W. Shi, "Hierarchical star: a new two level interconnection network", Journal of Systems Architecture, 51, pp.1~14 (2005)
  12. 김종석, "하이퍼-스타 연결망의 위상적 성질과 방송 알고리즘", 정보처리학회논문지A, 11(6), pp.341~346 (2004), 한국정보처리학회
  13. 김종석, "상호연결망 하이퍼-스타 HS(2n,n)의 이분할 에지수와 고장지름 분석", 정보처리학회논문지. 컴퓨터 및 통신시스템, 12(7), pp.499~506 (2005), 한국정보처리학회
  14. 김종석, "PMC 모델과 비교진단 모델을 이용한 하이퍼-스타 연결망의 진단도 분석", 정보처리학회논문지A, 13(1), pp.19~26 (2006), 한국정보처리학회
  15. 김종석, "Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석", 정보처리학회논문지A, 14(5), pp.263~268 (2007), 한국정보처리학회
  16. 김숙연, "메쉬의 교차큐브에 대한 임베딩", 정보처리학회논문지A, 15(6), pp.301~308 (2008), 한국정보처리학회
  17. 이형옥, "하이퍼-스타 그래프 : 다중 컴퓨터를 위한 새로운 상호 연결망", 정보처리논문지, 5(12), pp.3099~3108 (1998)
  18. 이형옥, "Folded 하이퍼-스타 그래프의 병렬 경로", 정보처리논문지, 6(7), pp.1756~1769 (1999)

관련 논문AI추천

폴디드 하이퍼큐브와 HFH 네트워크 사이의 임베딩 알고리즘김성원, 김종석, 이형옥한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2013 · 제2권 제4호Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석김종석한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2007 · 제14권 제5호계층적 폴디드 하이퍼스타 네트워크의 임베딩 알고리즘김성원, 김종석, 이형옥한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2009 · 제16권 제4호22n-k×2k 토러스와 HFN(n,n), HCN(n,n) 사이의 임베딩 알고리즘강민석, 김종석한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2007 · 제14권 제6호계층적 Folded 하이퍼-스타 연결망(HFH): Folded 하이퍼-스타 연결망을 기반으로 하는 새로운 상호연결망김종석, 이형옥한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2008 · 제15권 제2호상호연결망 폴디드 하이퍼-스타 연결망 FHS(2n,n)의 고장 지름김종석, 이형옥한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2010 · 제17권 제1호

이 간행물의 다른 논문 (11건)

A Massively Parallel Algorithm for Fuzzy Vector Quantization김철홍, Luong Van Huynh, 김종면pp. 411-418Semi-Lagrangian 이류항 계산의 추적법 개선백낙훈, 유관우, 박수완pp. 419-426혼합현실 환경에서 레가시 데이터를 활용하는 가상 공정배치 시뮬레이션 시스템이종환, 신수철, 한순흥pp. 427-436다중프로세서 시스템을 위한 여유시간 기반의 온라인 실시간 스케줄링 알고리즘조규억, 김용석pp. 437-442임베디드 프로세서의 성능 향상을 위한 DIAM의 진보한 아키텍처백윤흥, 신세철, 조정훈, 윤종희pp. 443-452
원문 보기