JPH1040223A - 分散並列システムにおける集合通信認識の最適化方法 - Google Patents

Abstract

(57)【要約】 【課題】分散並列システムにおける集合通信認識を最適
化すること。 【解決手段】均質な問題に対して、通信セットをアクセ
ス規則性を生かしたデータ構造及びプロセッサ数に左右
されないプロセッサ表現を導入し、データ構造とプロセ
ッサ表現とを使って配列の次元ごとに通信セットを計算
し、次元ごとの通信セットから通信を構築する際に集合
通信を抽出する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する利用分野】本発明は分散並列システムに
おける集合通信認識の最適化方法に関する。

【０００２】

【従来の技術】分散並列計算機などの分散並列システム
用にデータ並列言語で記述されたアプリケーションで
は、遠隔ホスト上にある計算に必要なデータをローカル
・ホストへ通信するコードが、コンパイラによって生成
される。このデータ並列言語は、並列計算機上で並列プ
ログラムを書く際に、重要な役割を有している。特に、
このようなシステムに大規模な数値計算を実行させる
際、コンパイラがプロセッサの集合通信を適切に検出で
きることは非常に重要である。そこで、まず本発明が対
象とする「コンパイラ処理系による集合通信認識」の重
要性を以下の順序で説明した後に、従来の技術の内容及
び問題点について説明する。 （１）データ並列言語プログラムにおける通信の種類 （２）コンパイラによる通信の最適化 （３）集合通信ライブラリ

【０００３】（１）データ並列言語プログラムにおける
通信の種類 データ並列言語プログラムにおけるプロセッサ間通信の
種類は、主として、並列化ループ実行前のデータのプリ
フェッチのための通信と、配列の分配方式を変更、すな
わち再分配のための通信がある。プリフェッチは、ルー
プ実行前に、予め、読み出し参照する右辺配列領域のデ
ータを有するプロセッサから実行文の計算を行うプロセ
ッサに、そのデータを転送することである。

【０００４】また、再分配とは配列を分配し直すことで
あるが、これは次の場合に必要となる。まず、アルゴリ
ズムの性質上、配列の分配方式を変更した方が実行性能
の向上を見込める場合である。この場合、アルゴリズム
の実行前に、読み出し参照する右辺配列領域を適切に分
配し直す。また、サブルーチンの境界で引数配列の分配
方法が変わる場合にも再分配が行われる。

【０００５】プリフェッチについて図１に示すハイ・パ
フォーマンス・フォートラン（以下ＨＰＦという）で記
述されたプログラムリストを例（ＬＵ分解のカーネル・
ループ）にさらに説明する。データ並列言語コンパイラ
が行う通信解析は、ループ実行中にアクセスされる右辺
配列領域Ｒ_kをプロセッサＰ_iがプロセッサＰ_jへ通信す
る、という通信セットの計算である。

【０００６】ループを並列化するために、コンパイラ
は、２重ループの前に右辺配列オペランドa(i,k)のプリ
フェッチ通信コードを生成する。ＮＰ台のプロセッサで
「所有者計算(owner computers)方針」に沿ってループ
を実行すると、配列領域a(:,k)が分割、保持されるプロ
セッサｐは、配列領域a(k+1:n,k)を、左辺でアクセスさ
れる配列領域a(k+1:n,k+1:n)を所有するプロセッサに通
信する必要がある。つまり通信セットは、送信としてa
(k+1:n,k)とそれを分配されたプロセッサｐ、受信とし
てa(k+1:n,k+1:n)を分配されたプロセッサ・グループで
ある。

【０００７】図２はプリフェッチにおけるデータ通信を
説明する概念図である。この図において、記号（ｋ，
ｉ，ｊ，ｎ）は図１のプログラム中の変数に対応してい
る。また、縦たんざく状の領域は配列がサイクリック(c
yclic)分割されていることを示しており、斜線部分は通
信される配列領域を示している。

【０００８】次に再分割についてさらに説明する。配列
が(block,block)で分割されている場合、図３に示すプ
ログラムリストに示されているサブルーチンを呼ぶと再
分配が発生する。図４は再分配におけるデータ通信を説
明する概念図である。この図において、正方形の領域は
配列aが分割された領域を示している。２次元プロセッ
サ形式p(i,j)に最初に分配された配列領域をＡ_ijとして
いる。サブルーチン呼び出し(call sub(a))の際に、２
次元プロセッサの１次元目iの各プロセッサが同じ配列
領域（Ａ_i1、・・・、Ａ_in）を有するように再分配が起こ
る。通信セットは、プロセッサP(i,:)が配列領域
（Ａ_i1、・・・、Ａ_in）をそれぞれの分配先から受信し、
プロセッサp(i,j)がＡ_ijをプロセッサp(i,:)に送信す
る。

【０００９】（２）コンパイラによる通信の最適化 ＨＰＦなどのデータ並列言語で記述されたプログラム中
で必要となるプロセッサ間の通信は、コンパイラが抽出
する。この抽出において、並列計算機の性能を十分に発
揮させプログラムの実行速度を向上させるために、その
計算機の特性を生かすように、通信を最適化することが
重要である。特にプロセッサ毎にメモリを有するような
分散メモリ並列計算機の場合、データ並列言語では配列
をプロセッサ間に分配するため、この最適化が非常に重
要になる。このような計算機において、ローカル・プロ
セッサが、自己のメモリ中に存在しないデータを使って
計算を実行する場合にプロセッサ間の通信が生じる。こ
の通信のための時間は、メモリのアクセスの時間と比べ
て非常に遅いので、通信のオーバーヘッドは並列計算機
のパフォーマンスに直接影響を与える。

【００１０】（３）集合通信ライブラリ 並列計算機システムには、ネットワークを有効に活用す
る最適化通信サブシステムである集合通信(collective
data movement)ライブラリが提供されている。あるプロ
セッサ・グループにおいて通信が必要となった際に、そ
の通信がライブラリ中の定められたパターンに合致する
場合には、このライブラリに従って最適な通信が行われ
る。集合通信ライブラリの国際的な標準としてＭＰＩが
よく知られている。並列アプリケーションのパフォーマ
ンスを向上させるためには、通信が必要な場合に、集合
通信ライブラリをいかに活用できるかということが重要
である。例えば、図１のプログラムリストでは、放送(b
roadcast)というライブラリを適用することができ、ま
た図３のリストでは、全収集(all gather)というライブ
ラリを適用することができる。

【００１１】従来の集合通信を認識するアプローチは、
ループ本体中に存在する左辺配列と右辺配列の分配方法
がコンパイル時に決められ、分配されているプロセッサ
形式が同じであると仮定して、上述のような集合通信の
認識を行うものである。この方式は、コンパイル時に認
識するものはプロセッサ形式を１つしか許さないという
強い制約を持つ。また、分配方式が実行時に決まる場合
や、実行時に通信すべき配列領域が変化する場合には対
応しない。従って、以下のような場合には適用できな
い。 ・左辺と右辺のプロセッサ形式が相違している場合 ・右辺または左辺の配列の分配方式が実行時に決定され
る場合 ・右辺または左辺のアクセス領域が実行時に決定される
場合

【００１２】一般的なアプリケーションは、プリフェッ
チまたは再分割が、任意のプロセッサ形式、任意の配列
分割方法で行われる場合が多くあるので、従来の技術の
ようなコンパイル時における手法は現実のアプリケーシ
ョンに有効に適用できないという問題を有している。一
方、実行時に集合通信を認識する方法(scatter, gathe
r, alltoallを活用する手法)も提案されているが、ｍ次
元配列についての高価な計算量Ｏ（ｎ₀＋・・・＋ｎ_m-1）
（ｎ_iはｉ次元目の配列サイズ）なので大規模な数値計
算には向かない。

【００１３】

【発明が解決しようとする課題】このような課題を解決
するために、本発明は、分散並列システムにおける集合
通信認識の最適化方法において、均質な問題に対して、
通信セットをアクセス規則性を生かしたデータ構造と
し、プロセッサ数に左右されないプロセッサ表現を導入
し、データ構造とプロセッサ表現とを使って配列の次元
ごとに通信セットを計算し、次元ごとの通信セットから
通信を構築する際に集合通信を抽出することを特徴とす
る方法を提供する。

【００１４】

【課題を解決するための手段】均質な問題に対して、通
信セットをアクセス規則性を生かしたデータ構造（ＩＴ
Ｒリスト）とし、プロセッサ数に左右されないプロセッ
サ表現（４つ組表現）を導入し、データ構造とプロセッ
サ表現とを使って配列の次元ごとに通信セットを計算
し、次元ごとの通信セットから通信を構築する際に集合
通信を抽出することを特徴とする方法。

【００１５】

【作用】図５は、本発明が適用可能な範囲を説明するた
めの概念図である。本発明では、ＩＴＲリストと４つ組
表現を用いるため、実行時に他プロセッサと情報の交換
を行う必要がなく、プリフェッチと再分配の両方につい
て同じ手法で、配列次元数のオーダーの計算量で集合通
信を抽出できる。これは、配列サイズや並列計算機の規
模に依存しない。

【００１６】

【発明の実施の形態】まず、本アルゴリズムが有する特
徴であるＩＴＲリスト及び４つ組表現について説明し、
それに基づく実行時における集合通信の高速認識につい
て述べる。 ［ＩＴＲリスト］均質な問題に対して、通信セットをア
クセス規則性を生かしたデータ構造としてＩＴＲリスト
を生成する。通信セットを配列の各次元ことのＩＴＲリ
ストで表現する。ＩＴＲリストは、次に示すＩＴＲの列
とその管理情報であるＩＴＲマスタから構成される。

【００１７】ＩＴＲ：｛開始：終了：跳び幅｝の３つ組
で指定される配列領域とその領域の相手プロセッサ群を
表現 ＩＴＲマスタ：管理データ構造。リスト上のどのＩＴＲ
をどのプロセッサ群が取得すべきかという情報

【００１８】図６は、ＩＴＲリスト上での通信セット計
算を説明するための概念図である。通信解析の際、使用
するＩＴＲリスト上のＩＴＲを各プロセッサ上で計算す
る。均質な問題であればほとんどの場合、配列アクセス
方法にプロセッサ間規則性があるため、その規則性が、
ＩＴＲリストによりリストの規則による圧縮という形で
表現される。例えば、blockで５台のプロセッサに分配
された配列a(100)において、a(1:100)でアクセスされれ
ば、プロセッサｐがアクセスする配列は、a(1+p*20:20+
p*20)の用に、プロセッサＩＤでパラメータ化できる。

【００１９】通信セットの計算では配列の各次元ごと
に、配列の持ち方ＩＴＲリストと配列ＩＴＲリストを入
力とする演算を行うことで結果のＩＴＲリストを得る。
通信する配列セクションは、各次元のＩＴＲリストから
各プロセッサが自分用に取得したＩＴＲリストの組み合
わせによって表現される。

【００２０】ＩＴＲリストのデータ構造について具体的
に説明する。図９に示すようなＩＯＳ（後述する）は配
列の次元ことにＩＴＲリストで表現される。上述の如
く、ＩＴＲリストはＩＴＲブロックと管理データ構造で
あるＩＴＲマスタとから構成されている。

【００２１】ＩＴＲブロックは、開始(bg)：終了(ed)：
跳び幅(st)の３つ組で指定される配列区間Ｒ_ITRと、そ
の領域の通信相手を指定する４つ組Ｑ_ITR＝(dx:ps:nd:n
p)とから構成され、次式のように表現されるＩＴＲの集
まりである。

【数１】 ＩＴＲ＝[Ｒ_ITR，Ｑ_ITR] ＝[bg:eg:st,dx:ps:nd:np]

【００２２】ＩＴＲリスト上のＩＴＲブロックも４つ組
で指定される。これを通信元４つ組と呼ぶ。これと区別
するために、ＩＴＲが記述している４つ組を通信先４つ
組と呼ぶ。送信の場合は、前者は送信プロセッサを、後
者は受信プロセッサを表し、受信の場合のその逆とな
る。ＩＴＲマスタＭ_ITRLには、通信元４つ組のmps,mnd,
mnpが記述される。

【００２３】各プロセッサは、自分のプロセッサＩＤを
通信元４つ組に変換し、自分が関連するＩＴＲブロック
を得る。pidをＩＤとするプロセッサを含む通信元４つ
組は、Ｍ_ITRLには、通信元４つ組のmps、mnd、mnpが記
述される。各プロセッサは、自分のプロセッサＩＤを通
信元４つ組に変換し、自分が関連するＩＴＲブロックを
得る。pidをＩＤとするプロセッサを含む通信元４つ組
は、Ｍ_ITRLを使って分割位置mdxを求める次式によって
計算される。

【数２】

【００２４】この分割位置mdxがＩＴＲリスト上のＩＴ
Ｒブロック位置を示す。ＩＴＲリストＩＴＲＬを次のよ
うに表記する。

【数３】

【００２５】こうして得られた配列次元ごとのＩＴＲブ
ロックが含むＩＴＲは、以下に示すＩＴＲ積（◇で表
す）によって、すべての次元で組み合わされ、１つの配
列領域とその通信相手プロセッサを指定する。ｄ次元の
配列の場合、ｉ次元目で選ばれた、ｎ_i（１≦ｉ≦ｄ）
個のＩＴＲのそれぞれをＩＴＲⁱ _ki（１≦ｋ_i≦ｎ_i）と
し、ＩＴＲブロックを｛ＩＴＲⁱ _ki｝_ki=1...niとする。
するとプロセッサが関連するすべての通信、すなわち通
信セットは、次式で表される。

【数４】

【００２６】ここで、ＩＴＲ¹ _k1◇...◇ＩＴＲ^d _kdは通
信記述子である。ＩＴＲ積の具体的な操作は以下のよう
になる。ＩＴＲⁱ _kiの２つの構成要素である配列区間と
通信先４つ組をそれぞれ、Ｒⁱ _ki、Ｑⁱ _kiとすると、ＩＴ
Ｒ¹ _k1◇...◇ＩＴＲ^d _kdは次式で表される。

【数５】

【００２７】ここで、‖Ｒ，Ｑ‖は通信する配列セクシ
ョンＲ、通信先プロセッサＱをもつ通信記述子である。
Ｒは、ＩＴＲブロックをＲⁱ _kiの集合とみなしたＩＴＲ
ブロックの直積集合(Cartesian product)の要素であ
る。ＱはＱⁱ _kiをプロセッサの集合とみなした時の積集
合である。積集合演算はビット・ベクタの論理積なので
高速に実行できる。

【００２８】また、ＩＴＲリストはAugmented Regular
Section Descriptorと同様に、ＩＴＲブロックの周期性
を生かしてＩＴＲブロック列が圧縮される。例えば、[i
*10-9:i*10:1,i+1:4:32]_i=1..3は３つのＩＴＲを表現す
る圧縮形である。圧縮形によって、プロセッサは自分以
外のプロセッサが関連するＩＴＲの内容である配列区間
通信先プロセッサをＩＴＲリストを検索せずに知ること
ができる。シフト通信を認識する際に活用される。

【００２９】ＩＴＲ積の際、通信元４つ組mdx:M_ITRLに
ついても演算∩が行われる。∩演算の結果は同じ通信記
述子を有するプロセッサである。同じ通信元４つ組を有
するプロセッサは複数存在する。通信元４つ組は配列各
次元ごとに同じ通信パターンをとるプロセッサ仲間の自
然な表現になっている。以上から、プロセッサは自分が
関連する通信記述子を計算することによって、同様の通
信パターンを有する自分以外のプロセッサを知ることが
できる。

【００３０】図９に示したＩＯＳは２次元配列の例であ
る。ここで例としてプロセッサＰ３が関連する通信をＩ
ＯＳの各次元ごとのＩＴＲリストから抽出する。配列１
次元目では、上記数３に図９の表の値を代入した1+mod
((3-1)/1,2)より１番目、配列２次元目では1+mod((3-1)
/2,2)より２番目のＩＴＲブロックを各次元から１つず
つ（１次元目のＩＴＲブロックには２つのＩＴＲ。２次
元目には１つのＩＴＲ）抽出することが分かる。１次元
目の[50:50,2:1,2:4]と２次元目の[50:99,2:2,2:4]との
ＩＴＲ積を考えると、配列セクションは(50,50:99)、通
信先４つ組は(4:1:4:4)が得られる。これはＰ３がＰ４
と配列セクション(50,50:99)を通信することを表す。通
信元４つ組についても(1:1:2:8)∩(2:2:2:8)でＰ７が同
じ通信を行うことが分かる。

【００３１】［４つ組表現］プロセッサ数に左右されな
いプロセッサ表現として４つ組表現を用いる。ＩＴＲリ
スト上のＩＴＲとそのＩＴＲが記述する通信相手プロセ
ッサは次の４つ組で表現される。

【００３２】・分割位置 ・プロセッサ跳び幅 ・分割数 ・プロセッサ合計数

【００３３】図７は４つ組表現に基づく通信参加プロセ
ッサの計算を示す概略図である。この図における繰り返
し数については後述する。４つ組表現によるプロセッサ
群は、任意のプロセッサ形式の１次元プロセッサ形式表
現である。これにより、異なるプロセッサ形式に分配さ
れた配列間での通信におけるプロセッサ形式の違いを吸
収する。通信する配列セクションを求める組み合わせの
際に、ＩＴＲとＩＴＲマスタのそれぞれで４つ組でのプ
ロセッサ集合演算を行い、通信相手プロセッサ群と通信
元プロセッサ群をそれぞれ計算する。１次元プロセッサ
形式は、一般にビット・ベクタで実現され、計算機はビ
ット・ベクタ演算を高速に処理できるため、並列計算機
の台数が多い場合においても高速な演算ができる。

【００３４】また、本アルゴリズムでは、通信するプロ
セッサ、すなわち配列要素の所有者が複数化している
（リプリテイケド）状態、または受信するプロセッサが
複数存在する状態においても、上記と全く同様な扱いで
集合通信を認識する。送信プロセッサが複数有ることを
活用して、通信を送信プロセッサの数で分割して、プロ
セッサ間の同期を減らすことが可能となる。

【００３５】４つ組の詳細な構造について説明する。４
つ組のデータ構造は以下のようになっている。 ・分割情報(dx) ・プロセッサ跳び幅(ps) ・分割数(nd) ・プロセッサ合計数(np)

【００３６】４つ組(dx:ps:nd:np)は１次元プロセッサ
形式上において複数のプロセッサを指定する。４要素間
の関係は次の通りである。まずプロセッサ合計値npだけ
のプロセッサ群（プロセッサ1...np）を考える。次に１
つでps個のプロセッサ群を表現するプロセッサ分割(dec
omp)という概念を導入する。１次元プロセッサ形式は、
分割数nd文のプロセッサ分割の、さらにrf回の繰り返し
というプロセッサ分割の列で構成されると考えられる。
この場合、以下の数６が成立する。

【数６】rf＝np/ps/nd

【００３７】４つ組の分割位置dxは、個のプロセッサ分
割列の内nd個の中の位置を指定する。１つのプロセッサ
分割を指定することは、図８に示すように、ps×rf個の
プロセッサを指定することに等しい。

【００３８】例えば、４つ組(1:2:4:32)を考える。３２
台の１次元プロセッサ形式上、１つのプロセッサ分割は
２台のプロセッサを代表する。４つのプロセッサ分割
が、32/(2*4)、すなわち４回繰り返す。１回の繰り返し
は８台である。分割位置１は繰り返しそれぞれのうちの
最初のプロセッサ分割を指す。結果的にこの４つ組は、
プロセッサ１、２、９、１０、１７、１８、２５、２６
を指定する。

【００３９】［実行時における集合通信の高速認識］Ｉ
ＴＲリストと４つ組表現により、以下に示すような自プ
ロセッサに関する通信の計算とその結果だけで放送、シ
フト、全収集といった集合通信を検出することが可能と
なる。

【００４０】放送(broadcast) 通信セクションを求める際に行った４つ組の集合演算
は、自分が取得するＩＴＲを同様に取得する他のプロセ
ッサがどれなのかを示す情報をＩＴＲマスタ中に残して
いる。このため、放送通信となるような配列セクション
の通信を求める場合、受信の通信セットの計算では、Ｉ
ＴＲマスタの４つ組は複数のプロセッサが同じ配列セク
ションを受信することを示している。そうしたＩＴＲマ
スタがそれぞれのプロセッサで得られている。

【００４１】一方、送信の通信セット計算では、組合わ
さったＩＴＲの４つ組が同じ配列セクションを受信する
受信プロセッサ・グループを示している。従って、これ
により放送通信と認識される。こうした認識がプロセッ
サ間で情報をやりとりすることなく行わるため、不要な
プロセッサ間の同期を取ることなく、集合通信ライブラ
リの呼び出しに必要なプロセッサ・グループの構成が可
能となる。

【００４２】シフト(shift) シフト通信は固定オフセットによる規則的な配列アクセ
スによる結果である。この場合、規則的ＩＴＲリストだ
けが構成され、シフト通信を認識する。

【００４３】均質な問題では、配列アクセスの規則性が
ＩＴＲリストに反映される。ＩＴＲリストはその規則性
によって圧縮されれる。この圧縮はなメモリ量を削減す
るためだけの目的で行われるわけではない。ある配列次
元のＩＴＲリストで規則性のための圧縮が行われれば、
ＩＴＲリストを走査しなくても、その次元における他の
プロセッサのアクセスを計算することができる。

【００４４】全収集・全対全 複数のプロセッサから構成されるプロセッサ・グループ
を考えた場合、そのグループ中のある通信プロセッサが
同じ配列領域を他のすべての受信プロセッサに通信し、
それがすべての送信プロセッサについて行われる場合、
この集合通信を全収集(all gather）と呼ぶ。典型的に
は、配列のかけ算(matrix multiply)において全収集が
行われる。

【００４５】全収集の場合、ＩＴＲリストからＩＴＲを
取得しようとするプロセッサ群（ＩＴＲマスタの４つ
組）と、その配列セクションの通信相手となるプロセッ
サ群（ＩＴＲの４つ組）が等しくなる。その場合に全収
集通信を認識する。全対全通信も同様に認識される。全
対全が全収集と異なる点は、異なる配列領域を通信する
ことである。

【００４６】図１０は、ＬＵ分解カーネルのn=2000の場
合が、１対１対通信を使った場合と実際に本アルゴリズ
ムを適用して放送通信を使った場合との性能差を台数効
果との関係で示したグラフである。このグラフは、放送
通信ライブラリを活用することが非常に重要であること
を示すと同時に、本アルゴリズムの性能改善効果を示し
ている。並列計算システムで提供される集合通信ライブ
ラリを活用しない場合に対して、本アルゴリズムを適用
した集合通信ライブラリの活用により性能が向上してい
ることが分かる。

【００４７】

【実施例】本実施例は以下の流れで実行される。 （１）ＡＯＳ作成 （２）ＬＩＳ作成 （３）ＩＯＳ作成 （４）集合通信認識

【００４８】ここで、ＡＯＳとはアレイ・オーナシップ
メント・セットの略称であり、配列の分割を記述したデ
ータ構造である。ＨＰＦの場合、block(n),syclic(n)な
どで配列が分配された結果を記述する。またＬＩＳと
は、ローカル・イタレーション・セットの略称であり、
所有者計算方針に基づいて、各プロセッサに分配された
プロセッサ固有のループ繰り返し空間である。これらの
作成は、可能な限りコンパイル時に行われ、実行時オー
バーヘッドを削減するが、情報が不足する場合には実行
時に行われる。実行時に行う場合でも作成結果の再利用
によって実行時オーバーヘッドを削減することが可能で
ある。

【００４９】（１）ＡＯＳ作成 ＨＰＦではpd次元のプロセッサ形式P(m₁,・・・,m_pd)とad
次元の配列Ａ(n₁,・・・,n_ad)とのマッピングを行う。Ａの
ｉ次元目であるＡ_iは、Ｐのｊ次元目で分割されるか、
または全く分割されない(collapsed)。分割を行わない
Ｐの次元について複製化(replicated)が起きる。

【００５０】Ａ_iがＰ_jで分割されている場合、ＡＯＳの
ｉ次元目はＩＴＲリストは、下式のように表現される。
なお、Ｒ_kは分配方式に応じて決まる。

【数７】

【００５１】（２）ＬＩＳ作成 プロセッサに分配される前の多重ループの繰り返し空間
をグローバル・イタレーション・セット(global iterat
ion set)と呼びこれをＧＩＳという。ＧＩＳのd重目Ｇ
ＩＳ_dは左辺Ａの配列次元との対応の有無で分類する。
対応があるとは、対応する配列次元の添字式がＧＩＳ_d
のインデックス変数iv_dを用いて表せることである。対
応がない場合はそのままＬＩＳを構成する。

【００５２】ＧＩＳ_dと配列のil次元目が対応している
婆、ＧＩＳ_dは所有者計算方式に基づき分割されてＬＩ
Ｓ_dとなる。ここで、ループの下限lb_d、上限ub_d、跳び
幅by_dとし、配列の添字式をＳ_il(iv_d)と表す。すると、
ＧＩＳ_dを用いて左辺で各プロセッサがアクセスする領
域（以下、ＬＷＳと呼ぶ）は、Ｓ_il・ＧＩＳ_dとＩＴＲＬ
_{AO S}上の各ＩＴＲの配列区間の交わりによって求められ
る。Ｐ^lは左辺が分配されるプロセッサ形式、jlは配列
次元ilが対応するＰ^lの次元である。

【数８】

【００５３】ＬＩＳ_dは、下式のようにして求めること
ができる。

【数９】

【００５４】（３）ＩＯＳ作成 ＬＩＳを用いてアクセスされる右辺Ｂの配列領域をＬＲ
Ｓ(local read set)と呼ぶ。ＩＯＳはＬＲＳとＡＯＳと
の演算で求まる。右辺Ｂのir次元目Ｂ_irはＧＩＳと対応
があるか否かで分けられる。対応がない場合はそのまま
ＬＲＳを構成する。

【００５５】Ｂのir次元目Ｂ_irとループｄ重目ＧＩＳ_d
／ＬＩＳ_dとが対応する場合を考える。Ｂ_irの添字式を
Ｔ_ir（iv_d）とする。ＬＲＳはＴ_ir・ＬＩＳ_dによって求
められる。ＬＲＳは次式のようになる。

【数１０】

【００５６】ここで２つめのＩＴＲリストのＩＴＲ分割
（これを「／」上に「〜」を付した記号で示す）を定義
する。ＩＴＲ分割は非除数であるＩＴＲリストのＩＴＲ
を、除数であるＩＴＲリストのＩＴＲで分割する。分割
結果のＩＴＲには、配列区間は非除数ＩＴＲの配列区間
Ｒ_s、除数ＩＴＲの配列区間Ｒ_dとするとＲ_s∩Ｒ_d、４つ
組は（除数ＩＴＲの分割位置：除数ＩＴＲマスタ）が入
る。Ｒ_s∩Ｒ_d≠φであるすべてのＲ_dについて行われ
る。

【００５７】ここで、Ｐ^rを右辺が分配されるプロセッ
サ形式、jrは配列次元irが対応するＰ^rの次元とする
と、ＩＴＲＬ_AOSは、次式のように表される。

【数１１】

【００５８】ＩＯＳは、２つのＩＴＲリストのＩＴＲ分
割を求めることにより、次式のように示される。

【数１２】

【００５９】これらをまとめてイン／アウト・セット
（ＩＯＳ）と呼ぶ。これらの演算の意味は次の通りであ
る。ＬＲＳのＩＴＲリストをＡＯＳのＩＴＲリストでＩ
ＴＲ分割すると、その結果のＩＴＲリストは各プロセッ
サが右辺でアクセスする配列領域のそれぞれをどのプロ
セッサから読むかを記述するイン・セット（ＩＴＲ
Ｌ_IS）が求まる。またＡＯＳのＩＴＲリストをＬＲＳの
ＩＴＲリストでＩＴＲ分割すれば、その結果のＩＴＲリ
ストは各プロセッサが所有する配列領域の内読まれる領
域と読むプロセッサを記述するアウト・セット（ＩＴＲ
Ｌ_OS）が求まる。分割されていない配列次元の場合は、
ＩＴＲの４つ組に入る分割位置には分割がないことを示
すφを入れる。

【００６０】例えば、ＩＴＲＬ_LRS＝＜1:2:4＞｛[2:11,
φ],[12:20,φ]｝とＩＴＲＬ_AOS＝＜2:2:4＞｛[1:10,
φ],[11:20,φ]｝を考える。インセットは、＜1:2:4＞
｛[2:10,1:2:2:4][11,2:2:2:4][12:20,2:2:2:4]｝にな
る。またアウト・セットは＜2:2:4＞｛[2:10,1:1:2:4],
[11,1:1:2:4][12:20,2:1:2:4]｝になる。

【００６１】（４）集合認識 イン・セット(In Set)またはアウト・セット(Out Set)
の各次元のＩＴＲリストのＩＴＲ積をとり、通信セット
を計算する方法は［ＩＴＲリスト］の欄で既に述べた。
ここでは、通信記述子を求める際に、どのようにして集
団通信を検出するかを具体的に説明する。

【００６２】シフト(shift) ＩＴＲリストは周期性がある場合には圧縮される。ここ
でＩＯＳのすべての次元のＩＴＲリストが周期性(regul
arity)によって圧縮されている場合、またはすべてのプ
ロセッサで共通のＩＴＲリストである場合を考える。Ｉ
ＴＲの通信先４つ組がＩＴＲの分割位置ｍｄｘ_iの線形
表現ｍｄｘ_i＋ｃ_iで表される場合、圧縮されている次元
ｉでは、すべてそれをシフトと認識する。シフトでは、
プロセッサ形式上で決まったベクタ(・・・,ｃ_i,・・・) をオ
フセットとするプロセッサと通信している。従って、シ
フト固有の最適化が可能となる。

【００６３】放送(broadcast) イン・セットから求めた通信記述子を共有するプロセッ
サが他にもある場合、つまり同一配列領域を受信するプ
ロセッサが複数いる場合には、放送通信と認識する。但
し、次に述べる全収集・全対全の場合は除く。イン・セ
ットから通信記述子を求める際のＩＴＲ積で、通信元４
つ組、イン・セットの場合なら受信４つ組も∩演算が行
われる。その結果の受信４つ組が複数のプロセッサを指
定している場合、ＩＴＲ積の結果の通信記述子はそれら
で共通している。後述するＬＵ分解では放送通信の認識
例を示す。

【００６４】全収集(all gather）・全対全(all to al
l) イン／アウト・セット上において、通信先４つ組が表現
するプロセッサ・グループが、通信元４つ組が表現する
プロセッサ・グループと等しい場合、全収集あるいは全
対全通信と認識する。２者の違いは、前者が同じ配列領
域を送信するのに対し、後者は相手プロセッサ毎に異な
る領域を送信する。

【００６５】集結(gather)・分散(scatter) １つのプロセッサだけがイン・セットから通信記述子を
構成でき、そのプロセッサが関連するＩＴＲブロックは
複数のＩＴＲを有し、それぞれが異なるプロセッサを指
している場合を考える。またアウト・セットのすべての
ＩＴＲリストは周期性圧縮されているか、または全プロ
セッサで共通しているかのどちらかである。従って、す
べての送信プロセッサは１プロセッサに通信することが
分かる。この場合は集結通信と認識する。分散の場合は
この逆である。

【００６６】［集合通信認識例：ＬＵ分解］図１に示し
たＬＵ分解のプログラム・リストを用いて、ｎ＝128,32
台のプロセッサの場合に、本アルゴリズムが放送通信を
認識する実際の動作を説明する。

【００６７】（１）ＡＯＳ作成 図１のプログラム・リストでは、配列aのＡＯＳの２次
元目は周期的であり、プロセッサｐ（１≦ｐ≦３２）に
ついて、以後ｍｄｘ＝１＋mod((p-1)/1,32)であること
を用いるとＩＴＲＬは下式で表される。

【数１３】

【００６８】［Ｒ,Ｑ］_p・・・qはプロセッサｐからｑまで
のＩＴＲを示す。

【００６９】（２）ＬＩＳ作成 ｋ＝112の場合におけるＧＩＳ₂＝(113:128:1)_jと配列添
字式Ｓがｊ、そしてＩＴＲＬ_AOS2ａとからＬＷＳは下式
で表される。

【数１４】

【００７０】ＩＴＲＬ_AOS2ａとＳ^-1が自明であるから、
ｊループのＬＩＳのＩＴＲリストは下式のようになる。

【数１５】

【００７１】[]_p・・・qはプロセッサｐからｑまでのＩＴ
Ｒの中身がないことを示している。またｉループと対応
する配列１次元目は分割されていないことから、ｉルー
プのＬＩＳはＧＩＳと同じであるから以下のようにな
る。

【数１６】

【００７２】（３）ＩＯＳ計算 ｋ＝112の場合における、右辺配列a(i,k)に注目する。
ＩＴＲＬ_LISiと１次元目の配列添字式ｉが対応すること
から、a(i,112)のＬＲＳは以下のようになる。

【数１７】

【００７３】ここで、ループ実行に参加しないプロセッ
サa(i,k)にアクセスしないので、a(i,k)に対応しないｊ
ループのＩＴＲＬ_LISjにおいて空でないＩＴＲを有する
プロセッサをマスクとして使用した。上式で求められた
ＩＴＲＬについて、配列各次元ごとにＩＴＲ分割を行う
と次のイン／アウト・セットが得られる。

【数１８】

【００７４】（４）集合通信認識 プロセッサｐのＩＴＲ^p _IS1∈ＩＴＲＬ_IS1a(i,k)と、Ｉ
ＴＲ^p _IS2∈ＩＴＲＬ_{IS2 a(i,k)}を抽出する。これらのＩ
ＴＲによる受信及び受信は以下のようになる。

【数１９】

【００７５】ＩＴＲブロックは１つのＩＴＲのみから構
成されているので、これが通信セット全体となる。プロ
セッサ１７から３２はイン・セットのＩＴＲ積を計算す
る際、通信元４つ組として同じ17..32:1:32:32を持ち続
ける。そのため、それらのプロセッサは求めたイン・セ
ットと同じものをプロセッサ１７から３２が持つことが
分かるので、放送通信の認識する。

【００７６】

【効果】このように本発明では、均質な問題(regular p
roblem)に対して、実行時に高速に集合通信を認識する
ことができる。通信に参加するプロセッサを指定するた
めに４つ組プロセッサという表現手法を導入し、あるプ
ロセッサが行う通信が、配列領域とこの４つ組表現とで
記述される。通信解析を行う際、均質な問題の規則性を
生かし、４つ組上で定義された集合演算により、配列サ
イズや並列計算機のプロセッサ台数によらず配列次元の
オーダーで集合通信の認識を実行時に行うことをができ
る。このため本発明では実行時のオーバーヘッドを小さ
くすることができるのみならず、超並列計算機上の大規
模数値計算に適している。

【図面の簡単な説明】

【図１】プリフェッチを説明するためのＨＰＦで記述さ
れたＬＵ分解のプログラムリストの一例である。

【図２】プリフェッチにおけるデータ通信を説明する概
念図である。

【図３】再分配を説明するためのＨＰＦで記述されたプ
ログラムリストの一例である。

【図４】再分配におけるデータ通信を説明する概念図で
ある。

【図５】本発明が適用可能な範囲を説明するための概念
図である。

【図６】ＩＴＲリスト上での通信セット計算を説明する
ための概念図である。

【図７】４つ組表現に基づく通信参加プロセッサの計算
を示す概念図である。

【図８】４つ組を詳述するための概念図である。

【図９】ＩＯＳの一例を示した表である。

【図１０】ＬＵ分解カーネルのn=2000の場合が、１対１
対通信を使った場合と実際に本アルゴリズムを適用して
放送通信を使った場合との性能差を示すグラフである。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 小松 秀昭 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内

Claims (1)

【特許請求の範囲】
1. 【請求項１】分散並列システムにおける集合通信認識の
   最適化方法において、 均質な問題に対して、通信セットをアクセス規則性を生
   かしたデータ構造とし、プロセッサ数に左右されないプ
   ロセッサ表現を導入し、前記データ構造と前記プロセッ
   サ表現とを使って配列の次元ごとに通信セットを計算
   し、次元ごとの前記通信セットから通信を構築する際に
   集合通信を抽出することを特徴とする方法。