No | 115836 | |
著者(漢字) | 大山,恵弘 | |
著者(英字) | ||
著者(カナ) | オオヤマ,ヨシヒロ | |
標題(和) | スケーラブルでないモジュールを含む並列プログラムにおける高性能の達成 | |
標題(洋) | ACHIEVING HIGH PERFORMANCE IN PARALLEL PROGRAMS CONTAINING UNSCALABLE MODULES | |
報告番号 | 115836 | |
報告番号 | 甲15836 | |
学位授与日 | 2001.03.29 | |
学位種別 | 課程博士 | |
学位種類 | 博士(理学) | |
学位記番号 | 博理第3880号 | |
研究科 | 理学系研究科 | |
専攻 | 情報科学専攻 | |
論文審査委員 | ||
内容要旨 | この論文は効率的なスレッド管理と排他処理を実現するコンパイラとランタイム技術,を示す。その技術は共有メモリ並列計算機上で走る並列言語を対象とする。本研究の目的は、プロセッサ数を増やすと実行時間が減少するかほとんど変化しない性能モデルの実現である。我々はそれを理想的な性能モデルと呼ぶ。 既存の並列プログラミングシステムは、それへの並行な呼び出しを逐次化するモジュール(ボトルネックモジュール)を持つ並列プログラムでは理想的な性能モデルを常には与えない。それらのシステムではボトルネックモジュールにおけるオーバヘッドがプロセッサ数の増加につれて増加し、その結果、理想的な性能モデルが与えられない。そのオーバヘッドには、複数のプロセッサが交代でボトルネックモジュールで共有オブジェクトを更新することに起因するメモリ通信と、ボトルネックモジュールへの複数の並行な呼び出しを逐次化する処理が含まれる。我々は、既存の広く使われている並列プログラミングシステムであるSolaris threadsライブラリが提供するスレッドとロックを単純に用い、ボトルネックモジュールを含む複数の並列プログラムを記述して走らせた。それらのプログラムの性能は理想的な性能モデルに従わなかった。 すべての並列プログラムで理想的な性能モデルを実現するために達成すべき課題は、ボトルネックモジュールを持つプログラムの効率的実行である。その課題を達成するためには次の3つの本質的な問題の解決が重要である。それは、(1)ボトルネックモジュールの実行の高速化、(2)ボトルネックモジュールの実行回数の削減、(3)ボトルネックモジュール以外の部分がボトルネックモジュールへの呼び出しを表現するデータ構造を高速に生成する結果、大量のメモリが消費されることの防止である。我々の技術はそれらの問題を解決する。 第1の問題は、洗練されたスレッド管理と排他処理によって解決される。それは、ボトルネックモジュールに1プロセッサを割り当てる。そのプロセッサはそのモジュールへの複数の呼び出しを連続して実行する。ボトルネックモジュールに1プロセッサを割り当てることは、メモリ使用の時間局所性の向上と複数の並行な呼び出しを逐次化する処理の削減につながる。さらに、プリフェッチ処理や手続き間レジスタプロモーションなどの積極的な最適化の適用を可能にする。 第2の問題は、ボトルネックモジュールへの複数の並行な呼び出しを「融合」するための言語プリミティブの提供によって解決される。例えば、そのプリミティブを使えば、1つのウィンドウオブジェクトに対する再描画メソッドの複数の並行な呼び出しを融合し、再描画メソッドを1回だけ実行するようにできる。 第3の問題は、ボトルネックモジュールへの呼び出しを表現するデータ構造が多数存在している状況を検知したらプロセッサ数を減らすランタイム技法によって解決する。プロセッサ数を減らすと、ボトルネックモジュールが呼び出される頻度が下がるため、それらのデータ構造の数が減る。 各並列プログラムが与える性能モデルをよく理解するためには、プログラムの性能を決定する重要なパラメタを測るためのツールが不可欠である。重要なパラメタの一つはクリティカルパス長である。我々は、並列プログラムにコードを挿入してクリティカルパスを実行時に求める方法を構築した。その方法は、メモリ通信コストをクリティカルパス長に含めている点および第一級データ構造による通信を扱っている点で既存の方法と異なる。 我々は上の技術を備えた並列言語Amdahlを実装し、その技術の有効性を対称型共有メモリ並列計算機Sun Enterprise 1OOOOを使った実験で確認した。その実験では、複数のアプリケーションにおいて、Solaris threadsライブラリが提供するスレッドとロックを単純に使ったCプログラムが理想的な性能モデルを与えない場合にAmdahlプログラムが理想的な性能モデルを与えることを観測した。 | |
審査要旨 | 本論文は7章からなる。それぞれ順に、 1章(序章:) ここでは、本研究をするに至った動機と、問題点の抽出、さらにそれを解決するための目標の設定について述べられている。 2章: ここでは、本論文における記述言語であるAmdahlを説明する。 3章: ここでは、著者がBottleneck Moduleと定義する並列性を阻害する部分の高速化について、まず排他処理の性能の改善について述べている。具体的にBottleneck Moduleを処理するプロセッサを一つ固定し、該当するモジュールにアクセスするスレッドのリストを作って、そのプロセッサがそのリストの処理に専念する方式である。従来の排他処理の手法と比較を行ない、この方法の有効性を確かめている。 4章:ここでは、一つのモジュールに対する連続したメソッド呼び出しを融合する機構をプログラミング言語の側に持たせることで、メソッド呼び出しのオーバーヘッドを削減する手法を提案している。グラフィックス処理など、この手法が有用である例を示して、この手法の有効性を確かめている。 5章:ここでは、メモリ消費量を制御することで、消費量にあわせた最適なプロセッサを見つける手法を提案している。具体的に、メモリ消費量をタスク数で代替し、タスク数を制御している。処理プロセッサの削減は、Bottleneck Moduleの呼び出しコストの削減につながり、この面でのコストが下がることを主張している。 6章:ここでは、Bottleneck Moduleを発見するためにCritical Pathに着目し、さらにそれをオンラインで計算するアルゴリズムを提案している。 7章:ここでは、本論文のまとめを行ない、さらに将来的な展望を語っている。 本論文は、並列効果を高めるために、従来あまり顧みられていなかった、並列性を本質的に阻害する逐次モジュールの実行コストを緩和してやろうという発想から生まれたものであり、従来の「並列性を抽出できる部分をできるだけ速くする」という発想に反省を迫るものである。 本論文の特徴は1)並列(オブジェクト指向)実行環境において2)並列実行オーバーヘッドとして排他制御、メソッド呼び出し、実行タスク数制御を抽出し、3)それぞれについて有効性をベンチマークプログラムで検証した上で、提案したことにある。議論の場は長い間多くの研究者、プログラマを悩ませてきた並列性を阻害する部分にあり、この面での高性能化は並列性の抽出と並び、並列実行の性能をあげる面で非常に重要であることはいうまでもない。並列実行性能に影響を与える要因を同定し、それぞれについて提案手法の新規性と有効性をあわせて論じている点は情報科学的に見て高く評価されるべきであり、論文提出者が並列プログラミングにおいて高い職見と深い経験を持つと判断するに十分な内容である。 なお、本論文第3章、第4章、第6章は、いずれも田浦健次朗、米澤明憲との共同研究であり、論文目録内の2.-1,2.-2,2.-3で公表されているが、論文提出者が主体となって分析、検証を行なったもので、論文提出者の寄与が十分であると判断する。 以上の点を総合的に判断して、博士(理学)の学位を授与できると認めるものである。 | |
UTokyo Repositoryリンク |