第3章 ハイエンドコンピューティング研究開発の動向
笠原 博徳 委員
1. プロジェクトの構成
アドバンスト並列化コンパイラ技術研究体は、図1に示すように早稲田大学 笠原博徳を研究開発責任者（PL：プロジェクトリーダ）、早稲田大学山名早人と産業総合研究所小池汎平をサブリーダ、アドバンスト並列化コンパイラ技術グループリーダJIPDEC（富士通より出向）堀田浩一郎、並列コンパイラ性能評価技術グループリーダJIPDEC（日立より出向）安崎篤郎、管理法人（財）日本情報処理開発協会（JIPDEC）、JIPDECに出向（兼務）して研究を行う㈱日立製作所及び富士通（株）からの研究員23名、及び共同研究先として産業技術総合研究所、早稲田大学、再委託先として電気通信大学、東京工業大学、東邦大学で構成されている。これらのメンバは、産技制度初の試みである各研究拠点をネットワーク等の利用による「ネットワーク集中研究所方式」で研究開発を行っている。ただし、より密な共同研究開発・当該分野の人材育成を目指し、ネットワークベースの議論に加え、物理的に一カ所に集まり、講演会・開発技術に関する討論を行う技術研究会も頻繁に開催しており、その数は3年間で46回に達している。
さらに、本プロジェクトでは海外との協調、目標設定の妥当性、成果の海外へのアピール及び国内評価委員会の参考として世界的権威による評価を自主的に受けることを目標に国際協調委員会を設置し、平成13年9月第1回委員会を開催し、第2回委員会はAPCプロジェクトの最終成果報告会を兼ね平成15年3月20日に早稲田大学理工学部で開催される国際シンポジウム（APC2003）に併設して開催する予定である。委員会の中核となるインターナショナルアドバイザリボードはUniv. of Illinois, Prof. Padua （Parafrase, Cedar Fortran, Polaris等並列コンパイラの世界的権威）、Stanford Univ, Prof. Lam （Suif, National Compiler Infrastructure, Suif Explorer等コンパイラ、チューニングツール分野の権威）、Purdue Univ Prof. Eigenmann （Polarisコンパイラ, SPEC HPC等、コンパイラ及び性能評価の権威）、Ecole des Mines de Paris, Prof. Irigoin （PIPS Parallelizer手続き間解析の権威）で構成されている。ボードメンバとは協調委員会の席だけではなく、ネットワークベースで、技術動向、プロジェクトの進め方、世界への成果のアピール等について議論して戴くと共に、プロジェクトの中間評価も行って戴いた。その評価概要は以下である。
1）粗粒度タスク並列処理・アフィン変換等世界をリードする研究テーマで興味深い。
2）3年間で性能を2倍向上させるという数値目標は、世界の従来のコンパイラによる性能向上が年平均数％であることを考えると非常に難しい目標であり、数値目標にとらわれずに機能の向上を目指すべき。
3）粗粒度タスク並列化等で予想を上回る成果が出ている。
4）成果を海外でよりアピールすべき。
2. 開発技術
APCでは、共有メモリ型マルチプロセッサを中心としたマルチプロセッサの実効性能、価格性能比、使いやすさを向上させ、ハイエンドサーバ自身及びそれを使用する各種研究開発の競争力強化を支援すると共に、今後の携帯電話、PDA、ゲーム等チップマルチプロセッサを使用する各種の情報機器の競争力強化に資することを目的としている。特に、並列処理ではユーザは並列化チューニングに非常に大きな時間を費やさねばならず、本来のモデル開発、ゲームを含めたアプリケーション開発に十分な時間をとれないという問題を抱えている。この問題を軽減し、ソフトウェア開発の生産性を向上させハードウェアと合わせ市場を開拓していくことが今後のIT機器開発では重要であり、そのためにも本自動並列化コンパイラの開発を急ぐ必要がある。
本プロジェクトでは、従来の市販ループ並列化コンパイラの性能を同一マシン上で概ね2倍上回るということを目標としているが、ハードウェアと異なりコンパイラの性能は100%を上限とした実行効率で評価されるため2倍は非常に難しい値である。これを達成するためには、従来のループ並列化ではなく新たな並列処理方式の導入が必須であり、APCではマルチグレイン並列化をコア技術として次に示すコンパイラ技術の研究開発を行っている。また、コンパイラの数値目標の評価も従来世界のプロジェクトで例がないため開発技術による性能向上を客観的に示すために性能評価手法に関する研究も行っている。
2.1 自動マルチグレイン並列化技術の開発
マルチグレイン並列化は、従来のループ並列化に加え、サブルーティン・ループ間などの粗粒度タスク間並列性、近細粒度並列性等を階層的に使用する方式で、低オーバーヘッドでプログラム全域にわたるより大きな並列性を利用することが可能である。また、このマルチグレイン並列処理の性能を向上させるデータ依存解析技術、キャッシュあるいは分散共有メモリの有効利用によりメモリアクセスオーバーヘッドの軽減を目指すデータ自動分散技術等に関する研究・開発を行っている。
まず、プログラム中のサブルーティン、ループ、基本ブロック間の並列性を利用する粗粒度並列処理は、マクロデータフロー処理とも呼ばれ[1][6][7]、APCコンパイラのコアの一つとなる早稲田大学OSCARマルチグレインFortran並列化コンパイラで初めてが実現された[1]。
OSCARコンパイラでは、図2に示すように、粗粒度タスク（マクロタスク）として、単一のFORTRANプログラムよりRB （Repetition Block）、SB （Subroutine Block）、BPA（Block of Pseudo Assignment Statements）の3種類のマクロタスクを生成する。RBは各階層での最外側ナチュラルループであり、SBはサブルーティン、BPAはスケジューリングオーバーヘッドあるいは並列性を考慮し融合あるいは分割された基本ブロックである。
次にマクロタスク間の制御フロー[1]とデータ依存を解析し、図3（a）のようなマクロフローグラフ（MFG）を生成する。MFGでは、各ノードがマクロタスク（MT）、点線のエッジが制御フロー、実線のエッジがデータ依存、ノード内の小円が条件分岐文を表している。また、MT7のループ（RB）は、内部で階層的にMT及びMFGを定義できることを示している。
次に、マクロタスク間制御依存[1][6]及びデータ依存より各マクロタスクが最も早く実行できる条件（最早実行可能条件）[1]すなわちマクロタスク間の並列性を検出する。この並列性をグラフ表現したのが図3（b）に示すマクロタスクグラフ（MTG）である。MTGでも、ノードはMT、実線のエッジがデータ依存、ノード内の小円が条件分岐文を表す。ただし点線のエッジは拡張された制御依存を表し、矢印のついたエッジは元のMFGにおける分岐先、実線の円弧はAND関係、点線の円弧はOR関係を表している。例えば、MT6へのエッジは、MT2中の条件分岐がMT4の方向に分岐するか、MT3の実行が終了した時、MT6が最も早く実行が可能になることを示している。
次にコンパイラは、MTG上のMTをプロセッサグループへスタティックに割当てを行う（スタティックスケジューリング）か、実行時に割当てを行うためのダイナミックスケジューリングプログラムをDynamic CPアルゴリズムを用いて生成し、これを生成する並列化プログラム中に埋め込む。これは、従来のマルチプロセッサのようにOSあるいはランタイムライブラリに粗粒度タスクの生成、スケジューリングを依頼すると数千から数万クロックという大きなオーバーヘッドが生じてしまう可能性があり、これを避けるためである。このような並列化プログラムをOpenMPを用いて生成するために、APCコンパイラでは図4に示すワンタイムシングルレベルスレッド生成法を開発した。図4は、第一階層のマクロタスクグラフがデータ依存エッジのみをもっているため第一階層の4つのマクロタスクをコンパイラがスタティックスケジューリングを適用し、各4スレッドからなる2つのスレッドグループに割り当てる様子を示している。また、サブルーティンであるマクロタスクMT1_3及び並列化できないループであるマクロタスクタスクMT1_4内では、階層的にマクロタスクグラフを生成し、各グラフの並列度を推定後、その並列性にあったスレッドグループを生成し階層的に並列処理する際の並列プログラムのイメージを示している。この例の場合、これらのマクロタスクグラフは条件分岐を含んでいるため、ダイナミックスケジューリングが適用される。図中では、マクロタスクグラフMTG1_3に対しては、一つのスレッドにスケジューリングを任せる集中型ダイナミックスケジューリングを適用する場合のコードイメージが示されており、マクロタスクグラフMTG1_4に対しては4スレッドを2スレッドずつの2グループに分け、各スレッドグループがスケジューリングを行う分散型ダイナミックスケジューリングの場合のコードイメージが示されている。
また、APCコンパイラは、図5のSPEC CFP95 SU2CORプログラムのように多重にネストされたプログラムに対しても、各階層のマクロタスクグラフの並列性をループ並列性も含め推定し、各階層で利用できる並列性に見合ったスレッドグループ数を自動的に決定できるようになっている[7]。なおこの図5の例では、サブルーティンLOOPS中に図6に示すような粗粒度タスク並列性が大きい部分を見つけ、この図6で表されるマクロタスクグラフに7スレッドから成る2つのスレッドグループを割り当てていることが示されている。
さらに、このような粗粒度並列性を抽出する際には、サブルーティン間にわたるデータ依存を正確に解析することが重要となる。APCプロジェクトではこのインタープロシージャ解析の高度化に関する研究開発も行った。APCコンパイラは、サブルーティンにわたる定数の伝搬を行い、必要に応じクローンと呼ぶサブルーティンのコピーを作成し、その結果不要となる条件分岐文等を削除しプロシージャ間のデータ依存を正しく解析できるようにしている[7]。これにより粗粒度タスク間の並列性をより多く引き出せると共に、ループボディ中にサブルーティンコールを含むループの並列化もより高精度に行うことができるようになった[7]。
またAPCでは、不完全ネストループより並列性を引き出すと共に、データローカリティを高め、さらにイタレーション間同期オーバーヘッドを減らす手法としてスタンフォード大Suifグループにより提案されたがコンパイラには実装できなかったAffine Partitioning[8]を実現する実用的な手法開発し、パイプライン化された並列コードをOpenMPを用いて生成することに成功した[7]。
2.2 メモリ利用最適化技術
実際のマルチプロセッサシステム上で効果的な並列処理を実現するためには、並列性の抽出のみならず、メモリアクセスオーバーヘッドを如何に抑えるかが重要な課題となっている。これはプロセッサの動作速度向上に対しメモリのアクセス速度向上が追いついていないために生じるもので、主記憶共有メモリ型マルチプロセッサではキャッシュの有効利用が、分散共有メモリ型マルチプロセッサでは近接メモリの有効利用が性能に大きく影響する。
このためAPCコンパイラでは、主記憶共有型マルチプロセッサ用の分散キャッシュメモリの有効利用を目指したデータローカライゼーション技術と、分散共有メモリ型マルチプロセッサのためのファーストタッチ制御方式を開発した。
データローカライゼーションは、図7に示すようにマクロタスクグラフ上でデータ依存が存在する複数の異なるループにわたりイタレーション間のデータ依存を解析し（インターループデータ依存解析）、プロセッサ間データ転送が最小になり、さらにデータがキャッシュに収まるようにループとデータを分割（ループ整合分割）する[6]。さらに一度キャッシュ上に載せたデータを複数のループにわたり使用できるように、前のループが終了してから次のループを実行するという通常の実行順序ではなく、図8に示すように前のループの一部（整合分割されたループの一部）を実行すると同一のデータにアクセルする次のループの一部、またその次のループの一部を実行するという方式で、キャッシュ上のデータを長期間有効利用することを可能にしている。
さらに、プログラム中の配列サイズがキャッシュサイズの整数倍あるいは整数分の1のサイズだと配列間でラインコンフリクトが頻発することがある。これを避けるため、本データローカライゼーション手法では、図9に示すように配列サイズをコンパイラが拡張する配列間パディングを行い、ローカライゼーション後のラインコンフリクトを最小化する方式も実装している[7]。
また、分散共有メモリ型マルチプロセッサ用の自動データ分散では、SGI社Origin2000のOSが、最初に当該データを触ったプロセッサ上のメモリにデータを割り付けるファーストタッチ方式を採用していることから、これを利用しコンパイラが望むデータ分散を実現する方式を開発した。これは、プログラム中で最も処理時間を消費するループ（メインループ）で要求されるデータ分散に合わせ、コンパイラがその分散を実現するダミーのループ（ファーストタッチ制御ループ）を生成し、メインループ内での遠隔分散共有メモリへのアクセスを最小化する。この方式を用いると、配列へのアクセスパターンが実行時まで分からないため人手でもデータ分散が難しかった配列の間接参照を伴うプログラムに対しても最適なデータ分散を実現できる。これにより、SGI社コンパイラに対し、32プロセッサOrigin2000上でNAS Parallel Benchmarks CGプログラムを6.6倍高速に実行できることを確かめている。
3. APCマルチグレイン並列化コンパイラの性能
ここでは、前章までで述べたコンパイラ技術を統合したAPCコンパイラを市販の主記憶共有メモリ型マルチプロセッサシステム上で性能評価した結果について述べる。
APCコンパイラは、逐次型FORTRANプログラムを入力するとOpenMP指示文を用いて並列化されたFORTRANプログラムを生成する。今回評価に使用したマシンは、Power4チップを搭載したIBM pSeries690 16プロセッサ・ハイエンドサーバ、IBM RS6000 604e high-node 8プロセッサ・ミッドレンジサーバ、SUN Ultra80 4プロセッサデスクトップワークステーションである。これらのマシンを使用するにあたって、使用するコンパイラは、pSeries690では最新のIBMコンパイラ XL Fortran Ver.8.1、RS6000ではAPCプロジェクト開始時のコンパイラXL Fortran Ver. 7.1、Ultra80ではSUN Forte Ver.6 update 2を用いた。評価においては、SPEC CFP95及び SPEC CFP2000の内の全FORTRAN77プログラム16本に対しAPCコンパイラを適用し、生成されたOpenMPコードを上述の各社コンパイラを用いてコンパイルして実行した。本アドバンスト並列化コンパイラプロジェクトにおいてはプロジェクトの基本計画としてプロジェクト開始当時のループ並列化コンパイラの性能を概ね2倍上回るという数値目標を与えられており、この性能評価を客観的に行うために性能評価を担当するグループがプロジェクト内に設置されている。コンパイラ開発プロジェクトで数値目標をもった研究開発は世界でも例がなく、2倍をどのように評価するかが問題になるが、本プロジェクトにおいては使用可能なプロセッサ数までのプロセッサを用いた際の商用コンパイラの最高性能とAPCコンパイラの最高性能を比較する方式をとることとした。これはループ並列性のみを使っている市販コンパイラに比べ、APCコンパイラはより大きな並列性及びメモリアクセスオーバーヘッドの軽減が可能であるためプロセッサ数と共に性能が向上する場合が多いが、市販コンパイラの場合プロセッサを増やしすぎると逆に性能が低下してしまう場合があり、例えば同じ16プロセッサ同士の性能を比較すると見かけ上APCコンパイラの性能が非常によく見えてしまうためである。
このように各マシンが持つ最大プロセッサ数までの最高性能を、逐次処理に対するスピードアップ率として表示したのが、図10から図12である。
図10は、16プロセッサpSeries690上での性能であり、各バー2本の組の内、左側がXL Fortran Ver.8.1ループ並列化コンパイラを用いた時のスピードアップ率であり、右側がAPCコンパイラを用いた時のスピードアップ率である。図中プログラム名の下に書かれている数値は逐次処理時間[s]を表しており、各バー上の数字は並列処理時の処理時間[s]を、またカッコ内の数字はAPC コンパイラのXL Fortranコンパイラに対する速度向上率を示している。この図を見ると分かるように、APCコンパイラはSPEC CFP95 turb3dプログラムに対し、pSeries690上で最高10.7倍の高速化を達成できることが分かる。また16プログラムの平均速度向上率を計算すると算術平均で3.5倍という数値が得られており、最新のマシン及び最新の市販コンパイラに対してプロジェクト目標を大幅に上回る性能を得ることができた。
また、図11は8プロセッサIBM RS6000上での性能を表している。プロセッサ数が少ないこともあり、pSeries690と比べ性能向上率は小さいが、最大で6.2倍、平均で2.4倍の性能を得ることができた。これらのIBMマシンで最大性能が得られたturb3dでは、クローニングを伴うインタープロシージャ解析、ワンタイムシングルレベルスレッド生成を用いたマルチグレイン並列化が有効に働き上記のような性能が得られている。また、tomcatv、swim等のプログラムではデータローカライゼーションを用いたキャッシュ最適化が有効に働き、良好な速度向上が得られた。
図12は上記2マシンと比べ価格の低い4プロセッサ主記憶共有型ワークステーション上での性能を表している。このマシンは、上記2マシンに比べメモリ性能が低いため、キャッシュ最適化が性能に大きく影響する。このマシン上では、レベル2キャッシュがダイレクトマップ方式であるためパディングによるラインコンフリクト除去を併用したキャッシュ最適化が極めて有効で、SPEC CFP95 swimでは4プロセッサで逐次処理に比べ9.3倍の速度向上、Forteコンパイラに比べ5.4倍の速度向上を得ることができた。全16プログラムに対する速度向上の平均でも2.0倍という数値を得られている。
以上のように、APCコンパイラは複数の機種の主記憶共有メモリ型マルチプロセッサに対して極めて高い性能を示すことが確かめられた。
4. まとめ
アドバンスト並列化コンパイラプロジェクトは2003年3月に実質2年半の研究開発を終了する。このような短い研究開発期間を選んだのは、競争の激しいこの分野でマルチグレイン並列化という新しい技術の優位性を示すには、参加メンバーが所有しているコンパイラ技術をフル活用し短期間での開発実証が重要と考えたためである。
プロジェクトを通じ、従来例を見ない数値目標は大きなプレッシャーであったが、最新の16プロセッササーバー上で、そのマシン向けの最新のコンパイラと比べ、平均3.5倍の速度向上を達成できたことは、開発者としても予想しなかった好成績である。これは、同一のハードウェア上で、APCコンパイラを一度通すだけで自動的に性能向上を得られることを意味しており、この技術をさらに磨けばマルチプロセッサを使用する各種アプリケーションのユーザの方の計算速度向上及びプログラム開発期間の短縮が可能になると考えている。
また、このコンパイラは高性能コンピュータの利用者のみならず、今後のチップマルチプロセッサの性能向上、価格性能比向上、アプリケーション開発期間の短縮にも役立つものと期待できる。特に、ゲーム、携帯電話、PDAなどのSoC分野ではハードウェア・ソフトウェアの開発期間短縮、価格性能比の向上、アプリケーションソフトウェアの質が市場を分ける重要な要素となるため、自動並列化コンパイラは今後この分野でも有効に使用できるものと期待される。
参考文献
[1] 笠原博徳, 並列処理技術, コロナ社, 1991
[2] Banerjee U., Loop Parallelization, Kluwer Academic Pub., 1994
[3] Wolfe M., High Performance Compilers for Parallel Computing, Addison Wesley, 1996
[4] Eigenmann, R., Hoeflinger, J. and Padua, D.: On the Automatic Parallelization of the Perfect Benchmarks, IEEE Trans. on parallel and distributed systems, Vol.9, No.1 （1998）.
[5] Hall, M. W., Anderson, J. M., Amarasinghe, S. P., Murphy, B. R., Liao, S.-W., Bugnion, E. and Lam, M. S.: Maximizing Multiprocessor Performance with the SUIF Compiler, IEEE Computer （1996）.
[6] Kasahara H., Obata M., Ishizaka K., Kimura K., Kaminaga H., Nakano H., Nagasawa K., Murai A., Itagaki H., and Shirako J., “Multigrain Automatic Parallelization in Japanese Millenium Project IT21 Advanced Parallelizing Compiler”, Proc. of IEEE PARELEC, Warsaw, Poland, Sep. 23, 2002.
[7] APC2003:アドバンスト並列化コンパイラ国際シンポジウム資料, （財）日本情報処理開発協会（JIPDEC）, 早稲田大学理工学部, Mar.20, 2003.
[8] Lim, A. W. and Lam., M. S.: Cache Optimizations With Affine Partitioning, Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing （2001）.