相互排他アルゴリズムのメモリ競合解析
スポンサーリンク
概要
- 論文の詳細を見る
非同期共有メモリ並列アルゴリズムにおいて,その複雑度の尺度の多くはプロセスのステップ数と共有メモリの消費量である.しかし,実際には共有メモリ・マルチプロセッサのアルゴリズムの性能は競合(contention)に大きく影響を受ける.競合とは複数のプロセスが同時に同じメモリロケーションにアクセスする状態である.本稿では,Petersonの相互排他アルゴリズムについてその競合を解析し,2プロセス相互排他アルゴリズムのamortized競合が1/2であることを示す.また,n>__-3であるnプロセス相互排他アルゴリズムについては,そのamortized競合がn/3-5/9より大きいことを示す.
- 社団法人電子情報通信学会の論文
- 1999-10-25
著者
-
西谷 泰昭
岩手大学工学部情報システムエ学科:(現)(株)日本ネットシステム
-
西谷 泰昭
群馬大学工学部情報工学科
-
古屋 博貴
群馬大学工学部情報工学科
-
須田 佳史
群馬大学工学部情報工学科
-
黄 文鈞
群馬大学工学部情報工学科
関連論文
- 変換履歴の再利用による高レベルのプログラム変換
- ハイパーリングのハイパーキューブへの埋め込み
- AND-EXOR論理式の簡単化並列アルゴリズム
- 拡張前提式を用いたATMSの並列化
- リフレクション原理によるフレームシステムの拡張
- ハイパーキューブ上の安全な情報伝達 (計算モデルとアルゴリズム)
- 情報伝播アルゴリズムによる安全なメッセージ伝達
- Some Modifications of Lockout-Free Mutual Exclusion Algorithms (Algorithms and Theory of Computing)
- ロックアウトフリーな相互排除アルゴリズム
- プログラム変換によるCPSコンパイラの最適化に関する研究
- 状態に依存したプログラムの合成
- 相互排他アルゴリズムのメモリ競合解析
- パーミュテーショナルグラフの独立全域木
- パーミュテーショナルグラフのブロードキャスティング
- 2段MOS論理回路網設計のための論理関数のグラフによる表現
- MOSセルを用いた2段論理回路綱の設計
- 2値画像の一符号化法と演算アルゴリズム
- 可逆論理回路のToffoliゲート数の下界(研究速報)
- AND-EXOR論理式最小化アルゴリズム
- AND-EXOR論理式最小化アルゴリズム
- AND-EXOR論理式最小化アルゴリズム
- 論理関数のあるクラスについて最小性を保証するAND-EXOR論理式の簡単化アルゴリズム
- 故障があるアレンジメントグラフのブロードキャスティング
- 故障があるアレンジメントグラフのブロードキャスティング
- プログラム変換における変換履歴再利用の支援
- 再帰関数への変換による不変表明の生成