高並列計算のためのスレッド・マイグレーション

点击翻译按钮获取中文摘要

複数の計算機をネットワークで接続した分散システムの利点の一つは、サイト間で負荷分散を行うことによりシステム性能の向上が図れることである。特にスレッド移送を用いた動的負荷分散によって大きな性能向上が期待できる。しかし、負荷分散を行なう際には、スレッド移送に伴って発生するサイト間通信によるシステム性能の低下を考慮して行なう必要がある。本研究では、まず、動的負荷分散と、スレッド間通信によって生じるサイト間通信の通信量抑制とを同時に行なうスレッド移送スケジューリングのアルゴリズムを提案した。通信量抑制は、スレッドの最近の通信時間とCPU実行時間の比が(そのスレッドが所属するタスク内のスレッドの数)-1を越えたとき、そのスレッドを、最近最も頻繁に通信しているサイトに移送することによって行なう。さらに、提案した方式の有効性を評価するために、分散共有メモリ型バス結合マルチプロセッサのシミュレータを作成した。シミュレーションの結果、負荷分散と通信量抑制を行なった場合では、負荷分散のみを行なった場合に比べ、頻繁に通信し合うスレッドを1サイトに集めることにより応答時間が短縮されることを示した。一方、このような分散システムにおける、並列実行による加速の理論限界に関する考察も行なった。具体的には、ソーティング、置換、高速Fourier変換、行列転置、行列乗算の問題について、バス結合並列計算機モデルにおける並列計算時間の理論的下界を示すと同時に、最適アルゴリズムを提案した。