先行制御方式におけるオーバヘッドの解析  [in Japanese] An Analysis of Overheads on Advance and Parallel Processing Control Scheme  [in Japanese]

分散処理は,集中処理に比べ経済性,拡張性,変更容易性,高速性,信頼性など数多くの利点を持つ.上述のような多くの利点の中で,特に大規模なジョブの高速処理を狙った分散処理の部分概念として並行処理がある.並行処理は,処理能力を持つ構成要素(以下,プロセッサと呼ぶ)をほとんどすべて並列に動作せることにより処理効率の向上を達成しようというものである.このため並行処理の対象となるジョブは当然高い並列性を持つジョブであるが,これには事前に処理計画がたてられるスケジュール可能なジョブと確率的不確定要素を含むために処理計画をたてることができないスケジュール不可能なジョブの2つがある.前者の例としては画像処理,行列計算等があり,これらのジョブの実行を行なう並行処理システムはすでに多数発表され実用システムも存在する.一方,待ち行列網シミュレーションや分散データベースのようにスケジュール不可能なジョブでは,プロセッサ間での通信がいつ発生するかわからないため,プロセッサ間における処理順序に矛盾なく処理を進めることは容易ではなく,プロセッサ間の同期法が問題となる.この同期法の1つに一時的な矛盾を許し,キャンセル処理によりそれを解消する先行制御方式がある.しかしながら,処理速度低下の原因となる分散化オーバヘッドならびにプロセッサへのジョブ分割割当法に関しては十分な知見が得られていないのが現状である.そこで,本稿ではスケジュール不可能なジョブを実行する並行処理システムの同期法として処理能力がプロセッサ台数に対して線形に増加する先行制御方式をとりあげ,処理速度低下に深く関係する矛盾発生について検討を行う.