The Optimal Routing Algorithm in Hierarchical Cubic Network and Its Properties

スポンサーリンク

概要

• 論文の詳細を見る

• A Hierarchical Cubic Network (HCN) is a hierarchical hypercube network proposed by Ghose[4]. The HCNis topologically superior to many other similar networks, in particular, the hypercube. It has a considerably lower diameter than a comparable hypercube and is realized using almost half the number of links per node as a comparable hypercube. In this paper, we propose the shortest routing algorithm in HCN(n, n) and show that the diameter of HCN(n, n) with 2^<2n> nodes is n + ⌊ (n + 1)/3⌋ + 1 which is about 2/3 of that of a comparable hypercube. We also propose the optimal routing algorithm in HCN(m, n) where m ≦ n and obtain that its diameter is n+ ⌊ (m+1)/3 ⌋ +1. Typical parallel algorithms run in HCN(m, n) with the same time complexity as a hypercube and the hypercube topology can be emulated with O(1) time complexity in it.

• 一般社団法人電子情報通信学会の論文
• 1995-04-25

著者

• Yun Sang-kyun

  Computer Engineering Research Laboratory Department Of Electrical Engineering Korea Advanced Institu

• Park Ho

  Computer Engineering Research Laboratory Department of Electrical Engineering, Korea Advanced Instit

• Park Ho

  Computer Engineering Research Laboratory Department Of Electrical Engineering Korea Advanced Institu

関連論文

• The Optimal Routing Algorithm in Hierarchical Cubic Network and Its Properties

スポンサーリンク