Waksmanの一斉射撃アルゴリズムに対する最適化遷移規則集合の正当性について
スポンサーリンク
概要
- 論文の詳細を見る
1966年,A.Waksmanはn個のセルからなる1次元セル空間の同期(synchronization,セルラ・オートマトン上では同期化を一斉射撃(firing squad synchronization)と呼ぶ)を2n-2ステップで実現する16状態のセル・アルゴリズムを世界で最初に考案した.しかしながら,研究者の間ではWaksmanアルコリズムの遷移規則にはいくつかの誤りがあることが指摘されていた.曽我部,野村,梅尾[9]らは,汎用セル・アルゴリズム・シミュレータを用いてWaksmanの遷移規則の検証を行い,そこに含まれていた誤りを訂正するとともに完全な遷移規則とそれに基づいた一斉射撃アルゴリズムの動作状況のシミュレーション結果を示した.Waksmanのアルコリズムは3208個の遷移規則から構成されていたが,我々が訂正したアルゴリズムは202個の遷移規則からなり,結果として内部状態数は16のまま,規則数において実に全体の7%に縮小された.さらにセル数2〜10000のセル空間の最適時間一斉射撃において,202個の遷移規則が正しく動作することを示した.本稿では,先に提案した202個の遷移規則集合が任意のnについて,正当であることを示すとともに,これらの規則が必要にして十分な規則集合であることを明らかにする.
- 社団法人電子情報通信学会の論文
- 2001-03-09
著者
-
梅尾 博司
大阪電気通信大学大学院工学研究科情報工学専攻
-
曽我部 崇
株式会社インターネットイニシアティブ
-
梅尾 博司
大阪電気通信大学総合情報学部情報工学科
-
梅尾 博司
Dept. Of Applied Electronic Engineering Faculty Of Engineering Osaka Electro-communication Univ.
-
曽我部 崇
大阪電気通信大学 大学院 情報工学専攻
-
野村 行宏
大阪電気通信大学大学院工学研究科情報工学
-
野村 行宏
大阪電気通信大学
-
梅尾 博司
大阪電気通信大学
関連論文
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- セルオートマトン理論の再構築とNatural Computingへの応用
- Early Bird問題に関する一考察
- 1次元リング結合セルラーオートマトンのための4状態一斉射撃アルゴリズム
- 正方形アレイのための一般化一斉射撃アルゴリズムについて
- 1状態および2状態1ビット通信セルラ・オートマトンの数列生成能力について
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- B105 2次元セルラオートマトン上での同期アルゴリズム(ロジック,アルゴリズム)
- B104 1ビットセルオートマトン上での数列生成問題(ロジック,アルゴリズム)
- 1方向再帰性を有する線形時間一斉射撃アルゴリズムの設計と実装
- A-12-3 1 方向再帰性を有する最適時間一斉射撃アルゴリズムの設計と実装
- Early Bird問題に関する一考察
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- 1状態1ビット通信セルラ・オートマトンの数列生成能力について(光カオス,一般)
- 2状態1ビット通信セルラ・オートマトンで生成可能な2次多項式数列について
- 1ビット通信セルラ・オートマトン上での非正則数列生成アルゴリズムについて(セッション2)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 1ビット通信セルラーオートマトン上での一斉射撃アルゴリズム
- 1ビット通信セルラーオートマトン上での素数列生成アルゴリズム
- 実時間数列生成アルゴリズムの1ビット通信セルラ・オートマトン上での実装について
- 有限要素法を用いた摩擦音発生時の声道内呼気流の推定
- 2次元セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計 (コンカレント工学)
- 2値図形の並列収縮アルゴリズムに関する考察
- 単位時間あたりのセル間通信量を1ビットに制限した2次元セルラ・オートマトンによる2値図形の連結性判定のための線形時間アルゴリズム
- 単位時間あたりのセル間通信量を1ビットに制限したセルラ・オートマトンによる数列の実時間生成と連結性判定アルゴリズム
- セル間通信量を1ビットに制限した2次元セルラ・オートマトンによる連結図形の線形時間認識について
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- ハイパーキューブアルゴリズムの可視化に関する研究
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- 星野 力 (著), "誰がどうやってコンピュータを創ったのか?", 共立出版, 158p, 2200円, 1995, ISBN4-320-02742-6
- セルラオートマトン
- VPMT : 分散メモリ型並列計算機のための並列プログラム可視化システム
- VPMT: 分散メモリ型並列計算機のための並列プログラム可視化システム
- 疎結合並列計算機上でのプロセッサ・ファームの効果的実装法
- 並列計算機(トランスピュータ・システム)における動作モニタの開発とその有効性
- トランスピュータ並列計算機による生物集団の行動パターンシミュレーション
- SIMD上の並列アルゴリズム (並列アルゴリズムの現状と動向)
- 小特集「並列アルゴリズムの現状と動向」の編集にあたって
- シストリック・アーキテクチャとそのアルゴリズム(パラレル・アルゴリズム)
- プレフィクス計算のための並列アルゴリズム (コンピュ-タと情報処理)
- ハイパ-キュ-ブ結合並列計算機上でのデ-タ・ル-ティング・アルゴリズム (コンピュ-タと情報処理)
- ブロードキャスト機能を備えた網目結合並列計算機のためのアルゴリズムに関する最近の研究
- 実時間シストリック・コンボルバの設計について
- シストリック・アレイによる線形時間限定セルラ・オ-トマンの模倣
- 1ビット・セルラオートマトンにおける最適時間一斉射撃アルゴリズムの実現
- 最適時間一斉射撃アルゴリズムの1ビット・セルラ・オートマトン上での実現
- I/O Time Complexity and Synchronization in Iterative(or Systolic) Arrays
- Time-optimum parallel binary address setting algorithms for array processors(Mathematical Theories on Computing Schemes and Their Applications)
- 一斉射撃を用いた並列・データ・ルーティング・アルゴリズム
- Waksmanの一斉射撃アルゴリズムに対する最適化遷移規則集合の正当性について
- A.Waksmanの一斉射撃アルゴリズムに関する一考察
- A. Waksmanの一斉射撃アルゴリズムに関する一考察
- 2次元正方形アレイ上での最適時間一斉射撃アルゴリズムの設計
- D-1-10 2次元セルラーオートマトン上での最適時間一般化一斉射撃アルゴリズムの設計(D-1. コンピュテーション)
- D-1-9 2次元最適時間一斉射撃アルゴリズムの実装について(D-1. コンピュテーション)
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 多将軍一斉射撃問題について
- 一斉射撃問題の一般化に関する考察
- 2次元長方形セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計と実装
- 2次元一斉射撃アルゴリズムのための新しい設計手法
- 2次元一般化一斉射撃アルゴリズムについて
- 2次元セルラオートマトン上での一斉射撃アルゴリズム
- D-1-1 2次元セルラオートマトン上での一般化一斉射撃アルゴリズムの設計と実装
- 6 状態 3n ステップ一斉射撃アルゴリズムの設計と実装
- Bookガイド--わたしの書棚から(39)並列/分散アルゴリズム編
- 繰り返し論理回路による高速数列生成アルゴリズム
- ピラミッド・コンピュ-タに関する最近の研究
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-009 正方形一斉射撃アルゴリズムの実現に関する考察(A分野:モデル・アルゴリズム・プログラミング)
- 遷移規則変換に基づく三角形セルラーオートマトンのための同期プロトコルの設計について (テーマ:知能・適応と社会,ネットワーク) -- (ネットワーク・WWW)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 進化戦略を用いた多足歩行ロボットの歩容学習(一般講演8)
- シストリック計算幾何アルゴリズムに関する最近の研究
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計と実装
- マルチビット最適時間一斉射撃アルゴリズムの設計(NLP一般)
- A-12-7 通信量を1ビットに制限した小さな自己複製セルラーオートマトンの構成(A-12.コンカレント工学,一般セッション)
- 2次元セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(一般,コンカレントシステム及び一般)
- セルラーオートマトン上での耐故障性自己増殖モデルの設計
- 1ビット通信セルラーオートマトン上での自己増殖機能の実現
- 最適実時間シストリック・多項式除算アルゴリズム
- シストリック・アレイ
- 分割統治法に基づいた線形時間・画像連結要素ラベリング・アルゴリズム
- セルラ計算機のための最適時間・並列アドレス設定アルゴリズム
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 分散ネットワークサービス基盤を実現するアクセス網のクラウド化 : ネットワーク仮想化と資源発見機構(ネットワーク研究開発テストベッド運用・利用,一般)
- 多次元最適時間FSSPアルゴリズム
- 大規模コンテンツ配信基盤を実現するアクセス網のクラウド化手法(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- DYPOP:Datacenter beside Your POPの紹介 : アクセス網に直結された分散ネットワークサービス基盤にむけて(産学官連携研究開発成果発表会,Resilient Network,ディザスタ・リカバリ,BCP(Business Continuity Plan),臨時ネットワーク構築,省電力ネットワーク技術,TCP/IP,プロトコル,ルーチング,ネットワーク管理,認証/ID管理及び一般)
- 多次元最適時間FSSPアルゴリズム
- ISP運用のためのネットワーク品質測定(インターネット運用・管理,一般 メジャーメント)
- ゼブラマッピングを利用した2次元一斉射撃アルゴリズムの実装(学生セッション)
- DYPOP : Datacenter beside Your POP の紹介アクセス網に直結された分散ネットワークサービス基盤にむけて
- 大規模コンテンツ配信基盤を実現するアクセス網のクラウド化手法