情報処理ニーズの高まりに伴い,並列処理技術に対する期待も強まっている.最近ではより費用対効果の高いクラスタ技術が注目されていることもあり,並列計算機が急速に身近になりつつある.ところで,並列計算機の実際の運用を見てみると,バッチスケジューリングを中心とした運用が多い.時分割スケジューリングの特徴を活かした対話処理は,プログラム開発効率を高めることが知られている.過去にメインフレームやスーパーコンピュータがバッチスケジューリング主体による運用から時分割スケジューリング主体の運用に移行したように,成熟しつつある並列計算機も時分割スケジューリング主体の運用にと移行するものと考えられる.クラスタ技術による並列処理の底辺の拡大は,この傾向をより強めるであろう.

　基本的に,並列計算機のジョブスケジューリングは,基本的にプロセッサ空間と時間の直交する2種類のスケジューリングから構成される.時間軸のスケジューリングは時分割スケジューリングとバッチスケジューリングに大別でき,空間軸のスケジューリングは空間分割スケジューリングと呼ばれている.時分割スケジューリングと空間分割スケジューリングを組み合わせた時空間分割スケジューリングでは,空間分割により生じる断片化の影響を低減する可能性が知られている.また,時分割スケジューリングとしてはキャングスケジューリングと非同期コスケジューリングの2つの方式が提案されている.

　これまでに並列計算機における時分割スケジューリングにおいて,スケジューリングオーバヘッドやスケーラビリティに関する詳細な報告はほとんどない.また,ギャングスケジューリングと非同期コスケジューリングのスケジューリング性能の比較においても,小規模な並列計算環境での評価しかなく,そのスケーラビリティについては不明である.さらに,時空間分割スケジューリングとバッチスケジューリングを主体とする空間分割スケジューリングの性能比較についても明確にはなっていない.そして,並列計算機における時分割スケジューリングが,現在広く使われている逐次計算機における時分割スケジューリングと同じ程度に対話処理を可能とするかということについては研究されていない.

　本研究は,分散記憶方式並列計算機において時分割スケジューリングを中心に,これらの問題を明らかにすることを目的としている.そのために,本研究ではギャングスケジューリングによる時分割スケジューリングに焦点を絞る.時分割スケジューリングの実装方式として,高い通信性能と低いスケジューリングオーバヘッドを両立させるために,ネットワークプリエンプション方式を実現する手法を提案する.また,時空間分割スケジューリング方式のひとつとして"Distributed Queue Tree(DQT)"を提案する.DQTはギャングスケジューリングを仮定した時空間分割スケジューリング方式である.

　図1は,本研究で提案するネットワークプリエンプション方式を構成するfreeze,save,restoreフェーズの処理時間を示したものである.スケジュ-リングの対象となったのは8本のプログラムで構成されるNAS並列ベンチマークであり,並列計算機としてはIntel社PentiumPro(200MHz)をプロセッサとするPCを64台,Myrcom社Myrinetネットワークにより結合したPCクラスタである.この図から,64プロセッサのギャングスケジューリングにおいて,並列プロセス切替時間(3つのフェーズの時間の総和)は4msec以下であることが判明した.この結果から,時分割間隔を100msecに設定した場合,スケジューリングオーバヘッドは4%以下であると推測され,別な評価によりこの推測がほぼ正しいことが確認された.

図1:ネットワークプリエンプションに要する時間

　このギャングスケジューラを用いて,非同期コスケジューリング(TPFSコスケジューリング)と比較した結果を図2に示す.この図の縦軸は,スケジューリングなしの実行時間を1とした時の,3つの並列プロセスをスケジューリングして全てが終るまでの時間の比である.つまり,理想的なスケジューラではプロセッサ数に依らずに常に3となる.ここでは,NAS並列ベンチマークの中から通信パターンが顕著に異なるCG,EP,FT,LUを選出した.この図2から,非同期コスケジューリングは通信がほとんど発生しないEPについては理想的なスケジューリング性能を示したものの,CGやFTにおけるスケジューリングのオーバヘッドは,ギャングスケジューリングの場合を上回る結果となった.また,この傾向は特にプロセッサ数が大きい程顕著になることも判明した.一方,ギャングスケジューリングではアプリケーションの通信パターンの違いによる影響は少ない.また,プロセッサ台数が大きくなっても安定したスケジューリング性能を示している.

図2:ギャングスケジューリングと非同期コスケジューリングの比較(3並列プロセス)

　本研究で提案されたDQT時分割スケジューリングは,シミュレーションによりいくつかのバッチスケジューリングと比較された.図3は,DQT,Fair-DQT(DQTに公平性を重視しスケジューリング性能を義性にした改良を施したもの),First-Come-First-Serveスケジューリングとバイナリバディによる空間分割の組み合わせ(これをFCFS-BBと呼ぶ)および,バッチスケジューリングにおいて高い性能を誇るScanUpのそれぞれについて,同じ条件でシミュレーションした結果である.横軸は投入した負荷率,縦軸はプロセッサ利用率である.この図から,単純なFCFS-BBスケジューリングは他のスケジューリング方式に比べ大きく劣っていることが分かる.一方,ScanUPと本研究で提案するDQTを比べると,負荷が特に高い状況においてDQTが僅かに上回る結果となった.従って,時空間分割スケジューリングは,バッチスケジューリングを主体とする空間分割スケジューリングと比べても同等の性能を発揮することが判明した.

図3:DQTとバッチスケジューリングの比較(1024プロセッサ)

　並列計算機においては時分割スケジューリングだけによる対話処理は効率的にはなり得ない.例えば,並列プログラム実行中にユーザからの入力だけを待っているような大域的なアイドル状態を検出し,プロセッサ資源の無駄な割り当てを避けることが必要である.本研究ではネットワークプリエンプション方式を応用することで,効率的に並列プログラム実行におけるアイドル状態の検出が可能であることを示す.ネットワークプリエンプションによる低い時分割スケジューリングオーバヘッドと大域的アイドル状態検出の機構により,並列計算機においても逐次計算機に近い対話処理が実現可能であることが確認された.

　本研究では,並列計算機におけるギャングスケジューリングに基づく時分割スケジューリングは,僅かなスケジューリングオーバヘッドで実現できることを実証した.一方,ギャングスケジューリングは非同期コスケジューリングに比べ,被スケジューリング並列プロセスの通信パターンやスケーラビリティという面においてより安定した挙動を示すことが確認された.また,ギャングスケジューリングとネットワークプリエンプション方式を用いることで,被スケジューリング並列プロセスの大域的なアイドル状態を検出できることを示した.さらに,時分割スケジューリングを主体とする時空間分割スケジューリングにおいてはバッチスケジューリングと同等の性能が得られることが検証された.これらの結果にから,ギャングスケジューリングと時空間分割スケジューリングを組み合わせることで,空間分割バッチスケジューリングと同等の効率で,多重プログラミング環境や対話プログラミング環境が並列計算機上で実用的になり得ることが確認されたと考えられる.

　本論文は、分散記憶方式の並列計算機環境における複数ジョブのスケジューリングについて、ソフトウェア開発時の利用効率を高める時空間分割スケジューリングを、高い実行効率を保ちながら実現する方式を提案、具体的な実装を通じて評価した研究の成果についてまとめたものである。

　従来、メモリを共有しない分散記憶方式の並列計算機環境においては、完成したソフトウェアの実行効率のみを追求したバッチスケジューリングが主流であった。一方、ソフトウェアの開発段階での利用には時分割スケジューリングが有効であることは知られていたが、高い実行効率を得ることが困難であったため広く用いられてこなかった。本研究は、ギャングスケジューリングと呼ばれる同期的なスケジューリング方式と、複数のプロセッサを時間軸と空間軸の両方に渡って複数ジョブに対して分割して割当てる時空間分割スケジューリングを洗練することによって、ソフトウェア開発時の利用効率とバッチスケジューリング方式に近い実行効率を同時に実現するスケジューリング方式を提案するとともに、提案方式に基づくスケジューラを構築、ベンチマークプログラムを用いた評価を通じてその有効性を実証的に示したもので、8章よりなる。

　第1章「序論」では、本研究の背景、目的、方針について述べている。

　第2章「関連研究サーベイ」においては、研究の対象となる分散記憶方式並列計算機の構成技術を概観し、従来のジョブスケジューリング技術の問題点を明らかにしている。ついで第3章「SCoreクラスタソフトウェア」では、本研究において提案する方式を評価するプラントフォームとした分散記憶方式並列計算機RWC PCC-IIと、その上での通信や並列実行を管理する基本的なソフトウェアであるSCoreクラスタソフトウェアについての概要と基本性能について述べている。

　第4章「ギャングスケジューリングの実装」は時分割スケジューリングを効率化するギャングスケジューラの実装に、プロセッサのみならず通信ネットワークについても時分割を徹底するネットワークプリエンプションを用いる方式を提案・実現し、そのオーベヘッドを分析、快適な利用に十分な短い間隔での時分割を行なっても大きな効率低下を伴わないことを示している。さらに第5章「ギャングスケジューリングと非同期コスケジューリングの比較」では、提案するギャングスケジューリング方式と、並列計算機上の他の有力な時分割スケジューリング方式である非同期コスケジューリングとを、並列計算機システムに対する代表的なベンチマークプログラムのひとつであるNAS並列ベンチマークを用いて比較し、全体として同等程度以上の効率を得られることと、提案方式がプロセッサ台数や通信パターンの変化による不安定性を低く抑えられることを示している。また、第6章「大域状態の検出」においては、ギャングスケジューラの実装に用いたネットワークプリエンプションを、並列プロセスの大域的状態を知るための検出機構の実現に用いる方式を提案し、この機構を実装して評価した結果、プロセッサ利用率や応答時間の改善に有効であることを示している。

　第7章「時空間分割スケジューリング」においては、提案したギャングスケジューリングを、時分割と空間分割を組合せたジョブスケジューリング方式である時空間分割スケジューリングに応用する方式としてDistributed Queue Treeを提案し、シミュレーションと実際の並列計算機上での評価を通してその特性を解析、従来提案されているバッチスケジューリング方式との性能比較を行なっている。この結果、適切なジョブ割当て方針の下では負荷の高低にかかわらず良好な性能を示すことを確認している。

　第8章では本研究の成果をまとめ、さらなる改良のための提案と共に、今後に残された課題を述べている。

　以上これを要するに、本論文では分散記憶方式の並列計算機環境における複数ジョブのスケジューリング方式について、ソフトウエア開発時の利用効率を高める時空間分割スケジューリングを、高い実行効率を保ちながら実現する方式を提案、実際の並列計算機上での実装とベンチマークプログラムを用いた評価を通してその有効性を実証しており、その成果は情報工学の研究に貢献するところが少なくない。よって本論文は博士(工学)の論文として合格と認められる。