2次元アレイ上における最適時間一斉射撃アルゴリズムの手法

カテゴリ: 全国大会

論文No: 3-027

グループ名: 【全国大会】平成22年電気学会全国大会論文集

発行日: 2010/03/05

タイトル(英語): An Implementation of an Optimum-Time Firing Squad Synchronization Algorithm on Two-Dimensional Arrays

著者名: 西出 絹夫(大阪電気通信大学),山脇 卓也(大阪電気通信大学),梅尾 博司(大阪電気通信大学)

著者名(英語): Kinuo Nishide(Univ. of Osaka Electro-Communication),Takuya Yamawaki(Univ. of Osaka Electro-Communication),Hiroshi Umeo(Univ. of Osaka Electro-Communication)

キーワード: セルラー・オートマトン|一斉射撃問題

要約(日本語): セルラ・オートマトンはNeumann によって考案された並列計算モデルの１つである.セルラ・オートマトンにおける同期問題は一斉射撃問題と呼ばれ,1987 年にMyhillによって提唱された. 本稿は,1次元アレイ上での最適時間一斉射撃アルゴリズムを利用し, 新しい2 次元アレイ上での最適時間一斉射撃アルゴリズムの手法である.最適時間とは, その時間より少ない時間で同期を行うことができない時間のことを示し, その証明もされている.本アルゴリズムは長方形状の角に将軍を生成し, どんなセルサイズm・nでも最適時間で同期できるものである.本アルゴリズムの実施は2次元セルラーオートマトン上で行い,124状態と45128の遷移規則から成り立つ.

原稿種別: 日本語

PDFファイルサイズ: 1,983 Kバイト