アクセス計算量 : 新しい並列計算量の枠組みの提案(プログラミングモデル・ツール)

概要

論文の詳細を見る
近年の計算機ハードウェアの進化により, 既存の計算量理論ではアルゴリズムの解析に十分とはいえない局面が多くなってきている.計算機のメモリ階層は深化し, RAMモデルと現実とは著しく乖離している.また, クラスタや大規模分散計算など, 各計算機間の通信遅延やその違いを無視できない並列環境が一般的になっているが, 現状の並列計算コストモデルは, 通信遅延の差異を考慮しないものや特定のネットワークトポロジに特化したものしか存在しない.我々は, 単一計算機内のメモリ階層から計算機間のネットワーク遅延の差異までを統一的に記述できる計算量モデル, 「アクセス計算量モデル」を提案した.このモデルは, 計算のコストの本質は演算ではなく通信にこそ存在するという立場をとる.このモデルは十分簡潔なものであり, 並列アルゴリズムの計算量を解析的に求めることができることを, いくつかのアルゴリズムで実証することができた.また, bitonic sortアルゴリズムの実計算機上での実行と比較することで, このモデルの妥当性を示すことができた.
一般社団法人情報処理学会の論文
2005-08-15