勉強会資料 並列言語、並列化コンパイラ 高山征大 平成 14 年 5 月 1 日^{1 はじめに 近年，並列計算機は数値解析などの科学技術分野 において用いられるだけにとどまらず，ビジネス， 人工知能などの分野にも広まりつつある．これは一 つにはハードウェアの著しい進歩による，処理速度 の高速化に負う所が大きい．がしかし，並列計算機 を最も効率良く動作させるためには，その上で動く ソフトウェアの最適化が欠かせない．従来から使用 していた逐次処理言語やコンパイラをそのまま用い ただけでは，並列計算機上においてはむしろ低速に なりさえするのである． このような現状におけるソフトウェアの最適化の アプローチとしては，三種類ある． 1. 従来からの逐次処理言語を捨て，並列計算機に より適合するような言語を新しく作る方法． 2. 今ある逐次処理言語に並列処理機能を追加す るという折衷案． 3. 逐次処理言語で書かれたプログラムを，コンパ イラが自動的に並列化するという方法． 次章以降でこれら三つの方法について，簡単に触 れていく． 2 並列言語 並列言語の範疇には，前章で述べた 1， 2 が含ま れる． 2.1 並列言語の特色 並列プログラミングにおいて必要とされる機能 は，並列処理しているプロセス間の同期と通信など}^{がある．それらに加え，並列言語は並列動作が陽に 記述できなければならない． 2.1.1 同期，排他制御 並列プログラミングにおいて問題となるのが，共 有データへのアクセスである．次に挙げるような問 題が存在する． 例えば， 1 つのオブジェクトに対して読み込み及 び書き込みを行う 2 つのプロセス 1， 2 があり， 1. プロセス 1 がオブジェクトの状態を読み込み， 書き込むと判断する． 2. プロセス 2 がオブジェクトの状態を読み込み， 書き込むと判断する． 3. プロセス 2 がオブジェクトに書き込む． 4. プロセス 1 がオブジェクトに書き込む． のような順で実行されたとする． (図 1) 図 1: 競合状態の例 このとき， 3 の段階でプロセス 2 が書き込んだ値 は，その直後の 4 でプロセス 1 によって上書きされ}

1 てしまうため，失われてしまう．つまり，図 1 の点線の間の処理内容が失われてしまうのである．このように，二つ以上のプロセスの実行順序がオブジェクトやプログラムの結果に影響を与える場合に起こる現象を競合状態という．

これはオブジェクトに対して変更を行ったり，値を読み込む操作がアトミック，すなわち不可分でないために起こる問題である．このアトミックに実行されなければならない領域をクリティカルセクションという．

このような問題を解決するために，プロセス間で同期，及び排他制御を適切にとらなくてはならない．同期，排他制御のための仕組みとして， mutex，セマフォ，条件変数，モニタなどがある．

2.1.2 プロセス間通信

並列に動作する複数のプロセスが同期などを行う場合，互いに情報を交換する必要がある．これをプロセス間通信という．これも,2.1.1 で述べたようなセマフォ，条件変数，モニタなどを用いて実現する．

2.1.3 並列性の記述

プログラマは，次に挙げるような方法で並列実行させたい部分を指定することができる． fork-join

図 2 に示すように，親プロセスが並列実行可能な子プロセスを生成 (fork) し，子プロセスの終了を待って次の処理に入る (join) 方法． fork 命令を繰り返し実行することができるため，プロセスの起動を動的に行うことができる．

cobegin-coend 図 3 のように記述し，静的に指定されたとおりに，プロセスが分岐し，合流する方法．起動されるプロセス数は固定されているが，記述方法が簡単であるので，細かなレベルの並列性を記述するのに適する．

2.2 並列処理言語

はじめから並列処理向けに設計された言語．

図 2: fork-join による並列性記述

図 3: cobegin-coend による並列性記述

• メリット従来からの逐次処理概念による束縛がないため，コンパイラの構成が比較的容易になり，それ故に並列化を最も容易に追求できる．

• デメリット既存の資産（コード，プログラミング技術）が活かせない．

データフロー言語のような関数型言語や，メッセージ交換モデルをベースとした Occam などの例がある．しかし，上述したようなデメリットのため，まだ広く使われるには至っていない．

2.3 逐次処理言語の並列処理拡張

従来の逐次処理言語に，並列処理向けの機能を追加する． • メリット

既存の膨大な資産を活かすことが可能．

• デメリットプログラムをどう並列動作させるかは，プログラムする側にかかっている．このため，複雑な並行処理の知識を習得しなければならない．

2.3.1 HPF

一例として， HPF (High Performance Fortran) について述べる．

HPF は，逐次処理型言語である Fortran を並列処理拡張したものである．分散メモリシステム上での並列化において最も重要なデータ分割をユーザーに任せ，処理を owner-computes rule^{1} に基づいて各プロセッサに割り当てる方式を採っている．

科学技術計算における Fotran のこれまでの資産を活かすことができるという点，そして並列計算機の主な用途の一つが科学技術計算であることを考えると，このアプローチは非常に魅力的である．

3 自動並列化コンパイラ

並列化コンパイラは，以下のような手順でプログラムを並列化する．

1. データ依存，及び制御依存の解析

2. 並列実行可能な部分の検出

3. プログラムを並列処理できる形へ変換

4. 並列実行可能な部分をプロセッサへスケジューリング

5. スケジューリング結果に基づいた並列化コードの生成

以下，これらを順にみていく．

3.1 依存解析

データ依存には以下のものがある．フロー依存ある文で定義した変数を他の文が使う．

出力依存ある文が定義した変数を他の文が再定義する．

逆依存ある文が使用した変数を他の文が定義する．

これらの依存性がない，あるいは解消できたタスクは並列実行可能である．また，制御依存とは，タスク間において条件分岐がある場合のことをいう．

3.2 プログラム変換

前節で解析したプログラムを，並列実行可能になるように変換する．ここでは，各種の変換手法を述べる．

3.2.1 Doall， Doacross

並列化手法のうち，最も一般的なものがループに対するものである．これは，ループには潜在的に並列可能性が大きい，またプログラム実行時間のうちループにおける時間の割合が高いなどの理由による．ここで述べる Doall， Doacross は， Do ループの各反復を異なるプロセッサに割り当てて並列化しようとするものである．

• Doall 全ての反復が全く独立に計算可能な場合，つまりそれぞれの反復間に依存性がない場合に，各反復を異なるプロセッサに割り当てて実行する方法．

• Doacross Doall と同様に，各反復を異なるプロセッサに割り当てるのだが，ある反復 S1 が別の反復 S2 の結果に依存する場合に S1 は S2 の終了を待ち，その結果を得てから計算にかかる方法．当然 Doall よりも低速である．

3.2.2 スケジューリング

前節までに行った並列実行可能な箇所を各プロセッサに割り当てる．割り当て方は，コンパイル時

1 owners-computes rule : 分割されたデータを保持するプロセッサ自身がそのデータをアクセスする文を実行するよう，コードを生成する策のこと．

図 4: Doall， Doacross の例

に行う静的スケジューリングと，実行時に行う動的スケジューリングがある．静的な方法は動的な方法と比較して実行時のオーバーヘッドが少ないが，ループ中での条件分岐などのためにプロセッサ毎に処理時間が大きく異なる場合に全体としてのバランスが崩れる可能性がある．他方，動的な方法だと実行時の通信によるオーバーヘッドの問題がある．動的スケジューリングの例として，

セルフスケジューリング共有メモリ上に処理済の反復数を記憶するカウンタ変数を置く．各プロセッサは 1 つの反復を終えるとカウンタをインクリメントし，次の反復を実行する．

チャンクスケジューリングカウンタ変数を置くまではセルフスケジューリングと同様だが，各プロセッサに複数の反復を一度に割り当てる点が異なる．こうすることにより，カウンタ変数を参照するオーバーヘッドを減少させる．

ガイデッドセルフスケジューリングチャンクスケジューリングを応用したもので，ループ処理の進行とともに，チャンクスケジューリングにおける割り当てる反復の数を小さくする工夫をする．カウンタ変数を参照するオーバーヘッドを減少させつつ，全体のバランスも保つ．

などがある．

3.3 事例

3.3.1 Parafrase

Parafrase は逐次処理言語である Fortran のプログラムを，多様なアーキテクチャを対象とした並列プログラムに変換する自動並列化コンパイラである．初の自動並列化コンパイラとして， 1970 年にイリノイ大で開発が始められた．変換工程にアーキテクチャ独立なパス，中間パス，特定の計算機に依存したパスを置くことにより，多様なアーキテクチャに対応している点が特徴である．

3.3.2 TINPAR

TINPAR は，富田研究室が開発しているメッセージ交換型並列計算機のための自動並列化コンパイラである．指定された方法で各プロセッサに対して配列変数を分割し， owners-computes rule (2.3.1) に基づいて拡張 Tiny Language ^{2} で書かれた逐次プログラムから C 言語の並列実行可能なプログラムを生成する．変換時に不要コードの削除や通信コードの移動などを行うことにより，効率のよいコードを生成するのが特徴である．

参考文献

[1] 富田眞治，並列計算機構成論，昭晃堂， 1996

[2] 笠原博徳，並列処理技術，コロナ社， 1991

[3] H.Zima,B.Chapman 著村岡洋一訳，スーパーコンパイラ，オーム社， 1995

[4] 並列言語，並列化コンパイラに関する勉強会資料， 1995-1998

2 Tiny Language: Fortran に類似した簡潔な構文規則を持つ言語