一斉射撃アルゴリズムにおける状態変化計算量に関する考察

カテゴリ: 全国大会

論文No: 3-099

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

発行日: 2004/03/17

タイトル(英語): State-Change Complexity for Firing Squad Synchronization Algorithms on One-Dimension Cellular Automata

著者名: 松本 康平(大阪電気通信大学),曽我部 崇(インターネットイニシアティブジャパン),梅尾 博司(大阪電気通信大学)

著者名(英語): Kouhei Matsumoto(Osaka Electro-Communication University),Takashi Sogabe(Internet Initiative Japan),Hiroshi Umeo(Osaka Electro-Communication University)

キーワード: アルゴリズム|並列処理|分散処理|セルラーオートマトン

要約(日本語): セルラーオートマトンとは,同期型並列計算モデルのひとつであり,有限個の内部状態を持つオートマトンから構成される.各オートマトンをセルと呼び,各セルは隣接するセルの局所情報を読み取り,セル自身が持つ遷移規則を用いて内部状態を変化させる.セルラーオートマトンに対する同期問題は,一斉射撃問題(Firing Squad Synchronization Problem)と呼ばれ,これまでに数多くの研究が行われている.当初,一斉射撃問題は自己増殖セルラーオートマトン上の一部の領域を同時に動作させるための問題としてMyhillより考案され,Balzer [1],Waksman [13]らにより最適時間アルゴリズが提案された.一斉射撃問題とは時刻t=0に将軍から発せられた,「準備ができたら一斉に射撃せよ」という命令により,未来の時刻t=αにおいて一斉に特殊な状態(射撃状態)に遷移するように遷移規則を決定する問題である.局所的な通信しか持たないモデルにおいてグローバルな制御を行うことが多くの研究者の興味を引き,広く研究されている [1-8,10-14].セルラーオートマトン上で動作するアルゴリズムの複雑さを評価する手段として,時間計算量,セル数,セルの内部状態数,遷移規則数,並びに状態変化回数等が知られている [1-14].本稿では,1次元並びに2次元セルラーオートマトン上で動作する一斉射撃アルゴリズムの状態変化回数について,コンピュータシミュレーションにより調査し,その結果を報告する.まずBalzer [1],Gerken [3],Mazoyer [5],Waksman [13]らによる従来から知られている1次元アレイ上での最適時間一斉射撃アルゴリズムは,O(n²)の状態変化計算量を持つことを示し,それらの状態変化計算量を比較する.次に3nステップで動作する線形時間一斉射撃アルゴリズムについても同様な調査を行い,O(nlogn)の状態変化計算量を持つことを示し,Fischer [2],Minsky [6],Yunes [14]アルゴリズムにおける状態変化計算量を比較する.最後に,2次元アレイ上での同様なアルゴリズムについても検討し,O(min(m,n)・(m+n)²)の状態変化計算量を持つことを明らかにする.

原稿種別: 日本語

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