Comments
Description
Transcript
博士論文審査報告書
早稲田大学大学院国際情報通信研究科 博士論文審査報告書 論 文 題 目 Program Parallelization for Effective Use of Computational Resources 計算資源の有効利用を目的とした プログラム並列化 申 請 者 Hidehiro KANEMITSU 金光 永煥 国際情報通信学専攻 情報ネットワークシステム研究 II 2012 年 2 月 計算機を用いた技術，具体的には処理速度の高速化，保持するデータの大容量化及びそれ らをアプリケーションとして実現する技術などが，ハードウェアとソフトウェア双方におい て発展してきたが，最近，グリッド計算や高スループット計算のような高性能計算モデルが 注目を浴びている．それらの計算モデルの目的の一つは，応答時間を最小化することである． もう一つの目的は計算スループット（単位時間当たりに処理できる計算量）の最大化であり， 高性能計算モデルは想定される状況や環境によって異なる．また，従来,タスクという処理 単位を実行するためのモデルとしては，「マスター・ワーカモデル」に見られるように，分 散環境において実行に必要なデータを分割して各計算機に配布し，異なるデータに対して同 一の処理をするという，いわゆる SIMD（Single Instruction/Multiple Data）形のものが 主流であった．このようなデータ集約型のジョブ（複数のタスクから構成される一つの処理 単位）とは対照的に，計算集約型のジョブをどのように分割して各計算機で並列実行させる かという問題に対する理論的な方法は未だ十分には確立されていない． このような背景から，申請者は計算グリッドのようなグリッド環境においてジョブをタス クに分割する際に，各プロセッサを有効利用する（応答時間の短縮に向け，各プロセッサの 貢献度を最大化する）手法の研究に取り組み，理論的な手法の確立を目指した． 実環境で想定されるシステムは主に均一分散環境と不均一分散環境に大別される．前者で は，各処理速度及び通信帯域幅はそれぞれ同一であり，後者ではそれぞれ任意の値をとりう る．本研究では，これら二種類のそれぞれの環境においてプロセッサを有効利用するための 手法を検討している． これまで行われてきたタスク分割手法には大きく分けて二つの手法がある．一つは，予め 利用可能なプロセッサ数が与えられている条件でタスク分割を行う手法であり，もう一方は， 利用可能なプロセッサ数がわからない条件でタスク分割を行った後，利用可能なプロセッサ 数に合わせて集約を行うという手法である．いずれの手法も，一つのジョブがシステムを専 有するという仮定の下でタスク分割を行うもので，一つの分散処理システムを複数のジョブ で共用する場合には，システムを有効に活用できないという問題があった． 本研究は「プロセッサ有効利用のために，各割り当て処理単位（クラスタ）の大きさに下 限値を設定し，実行プロセッサ数を制限する」という，従来なかったユニークな発想に基づ き，この下限値を理論的に導出する手法を確立したもので，学術的にも高く評価されるだけ でなく，複数の利用者が単一の計算グリッドを共用する場合にシステムを有効活用する手法 を示唆していることも評価できる． 本博士学位論文は申請者が本学大学院国際情報通信研究科に在学中に行った研究， 並び に，本学の助手として行った研究などで得られた成果をまとめたものであり，全 5 章で構成 されている．なお, 博士学位論文及び概要書は英文で記述されている．以下に各章の概要を 述べるとともに，評価を加える． 第1章「Introduction」は本論文の研究背景，本研究の狙いについて述べるとともに，本論 文の構成を示している． 第2章「Preliminary」では本研究で扱うジョブのモデルを定義している．ジョブは，各代入 文や関数呼び出し等をタスクとして表現し，さらにタスクから構成される一つのプログラム として抽象化する．一方，タスク間でやり取りされるデータは，ネットワーク上での通信に 対応する．ジョブは各タスクをノードに，各通信を辺に対応させた非循環有向グラフ（DAG） のタスクグラフとしてモデル化される．本研究で想定する実行モデルは，プロセッサ有効利 用という目標の下に，タスクグラフで表現できるジョブを完全結合型ネットワークで実行す るために並列化するものとなる. 第3章「Task clustering in homogeneous distributed systems」は均一分散環境における プロセッサの有効利用を論じる．本章では，各タスクがスケジュールされる前に各クラスタ の大きさに対する下限値を静的に決定する手順を導入している．この下限値を算出する段階 では，応答時間を決定できないため，応答時間を見積もりつつ，下限値を決めることが必要 となる． そこで，本研究では「各タスクができるだけ後に実行される場合の，応答時間が取りうる 最大値」として最長スケジュール長(WSL)を定義する．この WSL を用いて応答時間を見積も り，その一方で各クラスタをタスク集約処理によって生成する．WSL の変動と応答時間の最 小化の関係についての解析結果から，「WSL を小さくすることが応答時間の下限値及び上限 値を小さくする」ことを理論的に証明している．さらに，WSL を最小化するクラスタ内のタ スクの組み合わせを解析し，クラスタサイズの下限値 を変数とすることにより，WSL が最 小化されるときの 値（ここでは opt とする）を算出し，その opt を考慮して各クラスタを生 成する方法を提示した． 次に，計算量を抑えつつ，WSLを最小化することを目的としたタスククラスタリングアル ゴリズム（タスク集約処理を複数回行う処理）を提案した．本提案手法はシミュレーション 実験により，均一分散環境においてプロセッサ有効利用を達成するために適用可能な手法で あることが示されている． 本章で述べられた研究結果は，「クラスタの大きさに下限値を設定し，実行プロセッサ数 を制限する．その結果，応答時間の短縮に向け，各プロセッサの貢献度を最大化する」とい う，従来にはなかったユニークな発想に基づくものであり，その下限値を理論的に導出した ことは，高性能計算モデルの研究に新たな道を拓いたものとして学術的にも高く評価できる． 第4章「Task clustering in heterogeneous distributed systems」は不均一分散環境にお けるプロセッサ有効利用を実現するための手法を検討している． 本章で扱う不均一分散環境では第3章で扱った均一分散環境とは異なり，各タスク実行時 間は，割り当てられたプロセッサの処理速度と通信帯域幅に依存する．そのため，クラスタ 実行時間の下限値は，割り当て対象となるプロセッサに従って決定されねばならない．応答 時間の指標として第3章と同様に最長スケジュール長WSLを定義する．ただし，第3章の場合 と異なり，不均一分散環境でのWSLはクラスタをどのプロセッサに割り当てるかにより異な り，WSLはプロセッサ割り当てに依存する． 本章では先ず不均一分散環境においてもWSLを小さくすることが応答時間の下限値及び上 限値を小さくすることにつながることを理論的に示した．次いで，不均一分散環境における プロセッサ有効利用の具体的な手法として，以下の提案を行っている． ① クラスタ実行時間（当該プロセッサ上で実行されるタスク実行時間の総和）の下限値 sopt (Pp ) を，プロセッサ能力を考慮して決定する方法． ② クラスタの割り当て先プロセッサの選択基準． ③ ②で選択されたプロセッサに割り当てるべきクラスタを生成するためのタスククラス タリングアルゴリズム．（このアルゴリズムにより，①で決定された下限値を超えるクラス タ実行時間を持つクラスタが生成される．） シミュレーション実験により，WSLを小さくすることが応答時間を小さくすることにつな がることを実証し，クラスタ実行時間の下限値 sopt (Pp ) の適切性，並びに，提案したプロセッ サ割り当て手法の有用性を明らかにしており，本提案が極めて実用的であることが示されて いる． 本章は，より現実的な不均一な分散環境でも，前章と同様の理論的な結論が導出されるこ とを示すだけでなく，ジョブ並列化の具体的なアルゴリズムを提示するものであり，今後の 高性能計算モデル研究の方向性を示す研究として高く評価できる． 第5章「Conclusion」は本研究が分散環境におけるプロセッサ有効利用のための新しい手法 を提案したこと，特にその根拠となる，プロセッサに割り当てるべき処理単位（クラスタ） の大きさを理論的に導出したことを述べるとともに，ホップ数や，通信のボトルネックを考 慮してプロセッサの有効利用を達成するための手法が今後の課題であることにも言及して いる． 以上要するに，本論文は各プロセッサが互いにネットワーク上で接続された分散環境にお けるプロセッサ有効利用を目指し，「割り当て処理単位（クラスタ）の大きさに下限値を設 定し，実行プロセッサ数を制限する」という，新たな発想に基づき，この下限値を理論的に 導出したものであり，学術的に高く評価できる．同時に複数の利用者が単一の計算グリッド を有効活用する手法を提示するものであり，新たな研究の方向性を示唆している．本論文は 急速な発展が見込まれるグリッド環境での高性能計算モデルの研究に多大に貢献し，今後の 情報通信の進展に資することが期待され，国際情報通信学の発展に寄与するところは極めて 大きい．よって，本論文は博士（国際情報通信学）の学位を授与するに値するものであると 認める． 2012年2月24日 審査員 （主任） 早稲田大学教授 工学博士（早稲田大学） 浦野 義頼 早稲田大学教授 工学博士（早稲田大学） 亀山 渉 早稲田大学教授 工学博士（早稲田大学） 朴 早稲田大学教授 Ph.D.（イリノイ大学） 中里 容震 秀則