The KIPS Transactions:PartA (정보처리학회논문지A)

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

Hierarchical Folded Hyper-Star Network(HFH): A New Interconnection Network Based on Folded Hyper-Star Network

계층적 Folded 하이퍼-스타 연결망(HFH): Folded 하이퍼-스타 연결망을 기반으로 하는 새로운 상호연결망

  • 김종석 (영남대학교 전자정보공학부 BK21) ;
  • 이형옥 (순천대학교 컴퓨터교육과)
  • Published : 2008.04.30
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we propose a new interconnection network topology, hierarchical folded hyper-star network HFH($C_n,\;C_n$), which is based on folded hyper-star network. Our results show that the proposed hierarchical folded hyper-star network performs very competitively in comparison to folded hyper-star network and hierarchical network HCN(m,m), HFN(m,m) have been previously proposed, when diameter ${\times}$ degree is used as a network cost measure. We also investigate various topological properties of HFH($C_n,\;C_n$) including connectivity, routing algorithm, diameter, broadcasting.

본 논문에서는 Folded 하이퍼-스타 연결망을 기반으로 하는 새로운 상호연결망, 계층적 Folded 하이퍼-스타 연결망 HFH($C_n,\;C_n$)을 제안한다. 그리고 본 논문에서 제안한 HFH($C_n,\;C_n$)가 Folded 하이퍼-스타 연결망과 기존에 제안된 계층적 연결망인 HCN(m,m), HFN(m,m)보다 망비용(지름${\times}$분지수) 측면에서 우수한 연결망임을 보인다. 또한 HFH($C_n,\;C_n$)의 여러 가지 망 성질(연결도, 라우팅 알고리즘, 지름, 방송)을 분석한다.

Keywords

References

  1. S. Abraham, “The Twisted Cube Topology for Multiprocessor: A Study in Network Asymmetry,” Journal of Parallel and Distributed Computer, Vol.13, pp.104-110, 1991 https://doi.org/10.1016/0743-7315(91)90113-N
  2. D-R. Duh, G-H. Chen and J-F. Fang, “Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules,” IEEE Trans. Parallel and Distributed Systems, Vol.6, No.7, pp.714-723, July, 1995 https://doi.org/10.1109/71.395400
  3. A. H. Esfahanian, L. M. Ni and B. E. Sagan, “The Twisted N-Cube with Application to Multiprocessing,” IEEE Trans. Computer, Vol.40, No.1, pp.88-93, Jan., 1991 https://doi.org/10.1109/12.67323
  4. S. L. Johnsson, “Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures,” Journal of Parallel Distributed Computer, Vol.4, pp.133-172, 1987 https://doi.org/10.1016/0743-7315(87)90002-5
  5. J. Kim and K-G. Shin, “Operationally Enhanced Folded Hypercubes,” IEEE Trans. Parallel and Distributed Systems, Vol.5, No.12, pp.1310-1316, 1994 https://doi.org/10.1109/71.334904
  6. H.-O. Lee, J.-S. Kim, E. Oh, H.-S. Lim, “Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube,” Lecture Notes in Computer Science : EurAsia-ICT 2002, LNCS 2510, pp.858-865, 2002 https://doi.org/10.1007/3-540-36087-5_99
  7. F. T. Leighton, “Introduction to Parallel Algorithms and Architectures : Arrays, Hypercubes,” Morgan Kaufmann Publishers, 1992
  8. A. S. Vaidya, P. S. N. Rao and S. r. Shankar, “A Class of Hypercube_like Networks,” Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing, pp.800-803, 1993
  9. S.-K. Yun and K.-H. Park, “Comments on Hierarchical Cubic Networks”, IEEE Trans. Parallel Distributed systems., Vol.9, No.4, pp.410-414, 1998 https://doi.org/10.1109/71.667900
  10. 김종석, 오은숙, 이형옥, “하이퍼-스타 연결망의 위상적 망 성질과 방송 알고리즘,” 정보처리학회논문지A, Vol.11-A, No.5, pp.341-346, 2004
  11. 김종석, 이형옥, “상호연결망 HS(2n,n)의 이분할 에지수와 고장 지름 분석,” 정보처리학회논문지A, Vol.12-A, No.6, pp.499-506, 2005. 12 https://doi.org/10.3745/KIPSTA.2005.12A.6.499
  12. 김종석, 이형옥, “PMC 모델과 비교진단모델을 이용한 하이퍼-스타 연결망의 진단도 분석,” 정보처리학회논문지A, Vol.13-A, No.1, pp.19-26, 2006. 2 https://doi.org/10.3745/KIPSTA.2006.13A.1.019
  13. 김종석, “Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석,” 정보처리학회논문지A, Vol.14-A, No.5, pp.263-268, 2007. 10 https://doi.org/10.3745/KIPSTA.2007.14-A.5.263

Cited by

  1. Embedding Algorithm between Folded Hypercube and HFH Network vol.2, pp.4, 2013, https://doi.org/10.3745/KTCCS.2013.2.4.151