| 講演名 | 2007/7/26 パンケーキグラフにおける半素な耐クラスタ故障経路選択(分散システム) 渡部 達朗, 金子 敬一, 彭 旭東, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 並列計算システムの規模拡大に伴い,システム内に故障要素を持ったまま動作可能なアルゴリズムの開発は不可避である.また,単一故障より複数のクラスタ故障を想定したアルゴリズムの方が現実的である.本論文では,並列計算機の位相として有望なn-パンケーキグラフにおいて,n-1-k個のクラスタ故障を仮定し,1つの節点からk個の節点への半素な経路を構成する耐クラスタ故障経路選択アルゴリズムを提案した.このアルゴリズムが与える最大経路長は,2n+3であり,経路の構成にかかる時間計算量はO(kn^2)である. |
| 抄録(英) | With rapid increase of parallel computation systems in their sizes, it is inevitable to develop algorithms that are applicable even if there exists faulty elements in the systems. In addition, the algorithms should tolerate cluster faults instead of a single fault for actual operation. In this paper, we assumed n-1-k cluster faults in an n-pancake graph, which is promising for a topology of interconnection networks and we developed a cluster-fault-tolerant routing algorithm that constructs disjoint paths from one node to k distinct nodes. The maximum length of the paths given by the algorithm is 2n + 3, and the time complexity to construct the paths is O(kn^2). |
| キーワード(和) | 並列計算 / アルゴリズム / 耐故障性 / ディペンダビリティ / ケイリーグラフ |
| キーワード(英) | parallel computation / algorithm / fault tolerance / dependability / Cayley graph |
| 資料番号 | DC2007-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2007/7/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パンケーキグラフにおける半素な耐クラスタ故障経路選択(分散システム) |
| サブタイトル（和） | |
| タイトル（英） | Node-to-Set Cluster-Fault-Tolerant Disjoint Routing in Pancake Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列計算 / parallel computation |
| キーワード(2)（和/英） | アルゴリズム / algorithm |
| キーワード(3)（和/英） | 耐故障性 / fault tolerance |
| キーワード(4)（和/英） | ディペンダビリティ / dependability |
| キーワード(5)（和/英） | ケイリーグラフ / Cayley graph |
| 第 1 著者 氏名（和/英） | 渡部 達朗 / Tatsuro WATANABE |
| 第 1 著者 所属（和/英） | 東京農工大学工学府 Graduate School of Engineering, Tokyo University of Agriculture and Technology |
| 第 2 著者 氏名（和/英） | 金子 敬一 / Keiichi KANEKO |
| 第 2 著者 所属（和/英） | 東京農工大学工学府 Graduate School of Engineering, Tokyo University of Agriculture and Technology |
| 第 3 著者 氏名（和/英） | 彭 旭東 / Shietung PENG |
| 第 3 著者 所属（和/英） | 法政大学情報科学部 Faculty of Computer and Information Sciences, Hosei University |
| 発表年月日 | 2007/7/26 |
| 資料番号 | DC2007-8 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 174 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |