JPH08305580A - 並列プログラムの言語処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 連鎖的な計算処理過程において同期待ちの回
数が少ない効率良い並列処理が行なえるようプログラム
を変換する並列プログラム言語処理装置を提供する。 【構成】 構文解析装置１により内部表現に変換された
原始プログラムは、プログラム変換装置２によりローカ
ルメモリを備えた複数のプロセッサから成る並列計算機
システムで並列動作するよう変換され、目的コード生成
装置３により目的プログラムに変換され出力される。そ
の際、データ転送コード挿入装置４により各プロセッサ
の割当て部分の処理に必要な被演算数配列を各ローカル
メモリ上に当該処理の開始前に転送するようプログラム
を変換することで処理中途での被演算数の転送をなく
し、計算処理分割割当て装置５により処理の中間結果の
一部を複数のプロセッサで重複して計算させるよう変換
することで処理中途での中間結果の転送をなくす。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、原始プログラムを、ロ
ーカルメモリを備えた複数のプロセッサから成る並列計
算機システムで並列動作するような目的プログラムに変
換する並列プログラム言語処理装置に関するものであ
る。

【０００２】

【従来の技術】ローカルメモリを備えた複数のプロセッ
サから成る並列計算機システムでプログラムを実行させ
る際、プログラム中の計算処理にかかる被演算数や結果
を保持する配列を、互いに素な部分配列に分割し、前記
複数のプログラムにそれぞれ割り当てて、各プロセッサ
は自己の分担する部分配列の更新計算処理のみを実行す
るという方式、すなわち所有者計算規則（ｏｗｎｅｒ
ｃｏｍｐｕｔｅ ｒｕｌｅ）に基づく並列処理が、広く
行なわれている。所有者計算規則に基づくプログラム言
語処理系は、たとえば「Ｌａｎｇｕａｇｅｓ，Ｃｏｍｐ
ｉｌｅｒｓ ａｎｄ Ｒｕｎ−Ｔｉｍｅ Ｅｎｖｉｒｏ
ｎｍｅｎｔｓ ｆｏｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｍｅ
ｍｏｒｙ Ｍａｃｈｉｎｅｓ（Ｓａｌｔｓ，Ｍｅｈｒｏ
ｔｒａ共編，１９９２）」の１３９〜１７６ページ、
「Ｃｏｍｐｉｌｅｒ Ｓｕｐｐｏｒｔｆｏｒ Ｍａｃｈ
ｉｎｅ−Ｉｎｄｅｐｅｎｄｅｎｔ Ｐａｒａｌｌｅｌ
Ｐｒｏｇｒａｍｍｉｎｇ ｉｎ Ｆｏｒｔｒａｎ Ｄ」
に提案されている。

【０００３】この方式の並列処理では、あるプロセッサ
が計算処理を行なう上で他のプロセッサに割り当てられ
た部分配列上の被演算数を必要とする場合、当該プロセ
ッサ間で被演算数の転送処理が必要となる。

【０００４】

【発明が解決しようとする課題】前記従来方式の並列処
理では、あるプロセッサが計算処理を行なう上で他のプ
ロセッサに割り当てられた部分配列上の被演算数を必要
とする場合、当該プロセッサ間で被演算数の転送処理が
必要となり、転送処理が終了するまでは計算処理を開始
することができないため、これに伴って同期待ちが発生
する。しかしながら、通常のプログラムに見られるよう
な連鎖的な計算処理過程、すなわちある計算処理の結果
が次の計算処理の被演算数となるような計算処理過程に
おいては、過程の各段階ごとに前記データ転送が発生
し、これに伴うプロセッサ間の同期待ちの回数が増大し
て並列処理の効率が損なわれるという問題があった。

【０００５】図７は図６に示す従来のプログラム言語処
理装置で後述する図４のプログラムを処理し、ローカル
メモリを備えた複数のプログラムから成る並列計算機シ
ステムで実行させた場合のデータの流れを示している。
図７では配列Ａ，Ｂ，Ｃ，Ｄを１０等分し、連続する１
００個ずつの要素を１０台のプロセッサに割り当てた場
合の２台目のプロセッサ（配列要素番号１０１〜２００
を保持している）の様子を表している。長方形のマス目
はそれぞれ配列要素を表しており、中の数字はその要素
番号である。また矢印はデータの流れであり、各ステッ
プで上側の要素から下側の要素が計算されることを表し
ている。

【０００６】図７では、ステップ１でのＢおよびＣの計
算にはデータ転送は必要ないが、ステップ２においてＤ
の計算をするために、Ｂ，Ｃのそれぞれ２要素ずつ合計
４要素を他のプロセッサから転送しなければならないこ
とがわかる。これらが転送元のプロセッサ上で計算され
るまで転送処理を始めることができないため、ステップ
１とステップ２の間でプロセッサ間の同期待ちが発生
し、並列処理の効率が損なわれる。

【０００７】本発明はこのような点に鑑み、連鎖的な計
算処理過程において同期待ちの回数が少ない効率良い並
列処理が行なえるようプログラムを変換する並列プログ
ラム言語処理装置を提供することを目的とする。

【０００８】

【課題を解決するための手段】第１の発明の並列プログ
ラム言語処理装置は、原始プログラム中の連鎖的な処理
単位ごとに、各プロセッサが当該処理を行なうにあたっ
て必要とする配列が各ローカルメモリ上に当該処理単位
の開始前に用意されるようプロセッサ間においてデータ
転送させ、かつ当該配列を扱う計算処理の一部を複数の
プロセッサで重複して実行させるようプログラムを変換
することを特徴としている。

【０００９】第２の発明の並列プログラム言語処理装置
は、プロセッサに原始プログラムの配列を分割配置する
にあたり、その一部を複数のプロセッサに重複して配置
し、かつ当該配列を扱う計算処理の一部を複数のプロセ
ッサで重複して実行させるようプログラムを変換するこ
とを特徴としている。

【００１０】

【作用】第１の発明においては、原始プログラム中の連
鎖的な処理単位ごとに、各プロセッサが当該処理を行な
うにあたって必要とする配列が各ローカルメモリ上に当
該処理単位の開始前に用意されるようプロセッサ間にお
いてデータ転送させることにより、一連の計算処理の中
途での被演算数のデータ転送の必要性を除去する。ま
た、当該配列を扱う計算処理の一部を複数のプロセッサ
で重複して実行させることにより、連鎖的な計算処理の
過程で生成される中間結果であって各プロセッサの後段
の処理に必要となる部分を、各プロセッサのローカルメ
モリ上のデータのみを用いてそれぞれに計算させ、一連
の計算処理の中途での中間結果のデータ転送の必要性を
除去する。

【００１１】第２の発明においては、配列の一部を複数
のプロセッサに重複させて配置することにより、計算処
理に必要な被演算数を当該処理の開始前にすべてローカ
ルメモリ上に用意し、計算処理の中途での被演算数のデ
ータ転送の必要性を除去する。また、当該配列を扱う計
算処理の一部を複数のプロセッサで重複して実行させる
ことにより、連鎖的な計算処理の過程で生成される中間
結果であって各プロセッサの後段の処理に必要となる部
分を、各プロセッサのローカルメモリ上のデータのみを
用いてそれぞれに計算させ、一連の計算処理の中途での
中間結果のデータ転送の必要性を除去する。

【００１２】

【実施例】本発明について、図１〜図３を参照して実施
例を説明する。図１は第１の発明の実施例の概略構成を
示す。本実施例は、入力であるＦｏｒｔｒａｎ原始プロ
グラムを装置の内部表現に変換する構文解析装置１と、
内部表現された原始プログラムをローカルメモリを備え
た複数のプロセッサから成る並列計算機システムで並列
動作する内部表現された並列化プログラムに変換するプ
ログラム変換装置２と、内部表現をそれと等価なＦｏｒ
ｔｒａｎ目的プログラムに変換し出力する目的コード生
成装置３と、内部表現されたプログラムの処理単位ごと
に、各プロセッサが当該処理を行なうにあたって必要と
する配列が各ローカルメモリ上に当該処理単位の開始前
に用意されるようプロセッサ間においてデータ転送させ
るようなデータ転送コードを挿入するデータ転送コード
挿入装置４と、内部表現データで表されたプログラムの
配列を扱う計算処理の一部を複数のプロセッサで重複し
て実行させるように分割・割り当てを行なう計算処理分
割割当て装置５とから構成される。

【００１３】本装置への入力であるＦｏｒｔｒａｎ原始
プログラムは、構文解析装置１へ与えられる。構文解析
装置１は原始プログラムの文法の検出を行ないつつ、原
始プログラムを装置全体で用いる内部表現に変換し、プ
ログラム変換装置２へ渡す。プログラム変換装置２では
渡された原始プログラムを解析し、従来の方法によりプ
ログラム中の配列の分割配置方法を決定する。配列の分
割方法を決定したことで、所有者計算規則により計算処
理の分割方法もこの時点でおおむね自動的に決定する。

【００１４】次に、プログラム変換装置２はプログラム
をデータ転送コード挿入装置４に渡す。データ転送コー
ド挿入装置４では、渡されたプログラムをサブルーチ
ン、その他の論理的処理単位に分割し、各処理単位ごと
に、各プロセッサが当該処理を行なうにあたって最低限
必要とする配列、すなわち当該処理の入力データを求
め、入力データが各ローカルメモリ上に当該処理単位の
開始前に用意されるようプロセッサ間においてデータ転
送させるようなコードを挿入する。入力データを求める
にあたっては、当該処理の中間結果が他のプロセッサで
計算される場合であっても自プロセッサ内で計算するも
のとして扱う。これによって当該処理単位の中途でのデ
ータ転送の必要性が除去される。

【００１５】データ転送コード挿入装置４によりデータ
転送コードが挿入されたプログラムは、次に計算処理分
割割当て装置５に渡される。ここでは、所有者計算規則
により決定される計算処理の分割方法に基づいて、実際
に各プロセッサが各自の担当部分のみを実行するようプ
ログラムを変換する。また、データ転送コード挿入装置
４で前記のように自プロセッサ内で計算するものとして
扱った中間結果の計算処理を、実際に自プロセッサで行
なわせるようプログラムを調整する。この計算処理は本
来、それを行なうべきプロセッサにおいても当然行なわ
れることになるため、結果として当該計算処理は複数の
プロセッサで重複して実行されることになる。

【００１６】以上の処理により並列化されたプログラム
は、再びプログラム変換装置２に戻され、通常の言語処
理装置において行なわれるような調整が施された後、最
後に目的コード生成装置３に渡されて、出力であるＦｏ
ｒｔｒａｎ目的プログラムに変換される。

【００１７】図２にデータ転送コード挿入装置４の構成
を示す。データ転送コード挿入装置４は、プログラム変
換装置２から渡されたプログラムをサブルーチン単位ま
たは原始プログラムの文面上に指示された処理単位に分
割する計算処理セクション化部４１と、計算処理セクシ
ョン化部４１で分割された処理単位ごとにデータの定義
・参照関係を勘案しながらプログラムの制御の流れをた
どることにより、当該処理単位の最終結果となる配列の
各プロセッサ相当部分の計算処理に最小限必要なデータ
集合を求めるデータフロー解析部４２と、計算処理セク
ション化部４１で分割された処理単位ごとに、データフ
ロー解析部４２で求められたデータ集合のうち各プロセ
ッサのローカルメモリ上に割り当てられていないデータ
を、当該データを所有するプロセッサから転送する命令
を当該処理単位の先頭に挿入するデータ転送命令挿入部
４３とから構成される。

【００１８】計算処理セクション化部４１では、プログ
ラムをサブルーチン単位または原始プログラムの文面上
に指示された処理単位に分割し、処理単位ごとにデータ
フロー解析部４２に渡す。データフロー解析部４２で
は、渡された処理単位を「Ｃｏｍｐｉｌｅｒｓ−Ｐｒｉ
ｎｃｉｐｌｅｓ，Ｔｅｃｈｎｉｑｕｅｓ，ａｎｄ Ｔｏ
ｏｌｓ（Ａｈｏほか，１９８６）」第１０章に詳述され
るデータフロー解析手法により解析し、当該処理単位の
出口に到達する定義集合から当該処理単位の最終結果と
なる配列とそのインデックス範囲を求め、続いて各プロ
セッサに関し最終結果のうち担当する部分の要素から始
めてデータフローを逆向きに遡ることにより、前記要素
を計算するために当該処理単位の入口で用意されている
べき配列要素の集合を求める。この時、計算の中間結果
であって、自プロセッサに割り当てられていないものが
ある場合には記録しておき、計算処理分割割当て装置５
においてその情報をもとに、当該中間結果を自プロセッ
サでも計算させるようにコードを調整する。データ転送
命令挿入部４３では、データフロー解析部４２で求まっ
た当該処理単位の入口で用意されているべき配列要素の
集合のうち、当該プロセッサに割り当てられていないも
のについて、当該処理単位の先頭において当該要素を所
有するプロセッサからデータを転送する命令を挿入す
る。

【００１９】図３は第２の発明の実施例の概略構成を示
す。本実施例は図１の第１の発明の実施例と比較して、
データ転送コード挿入装置４を用いる代わりに配列デー
タ分割割当て装置６を使用している点が異なっている。
配列データ分割割当て装置６では、実行中プロセッサ間
においてデータ転送させる代わりに、各プロセッサが当
該処理を行なうにあたって必要とする配列が各ローカル
メモリ上にプログラムの実行開始時に用意されているよ
うそれらの配列の分割方法自体を変更する。ここでは前
記データフロー解析の手法ないし、原始プログラムの文
面上に指示された方法によって、配列の分割方法を決定
する。

【００２０】図４に示すＦｏｒｔｒａｎプログラムを例
に本発明の効果を説明する。このプログラムは２段階に
分かれており、ステップ１で被演算数Ａから中間結果Ｂ
およびＣを計算し、ステップ２でＢ，Ｃから最終結果Ｄ
を計算している。

【００２１】図５は第１の発明のプログラム言語処理装
置で図４のプログラムを処理し、同条件でプロセッサに
割り当てて実行させた場合のデータの流れである。自プ
ロセッサ内に存在しない要素Ａ（１００）とＡ（２０
１）をステップ１に先だって転送し、ステップ１におい
て本来自プロセッサに割り当てられていない計算（図で
は楕円で囲んだ部分）を併せて行なうことにより、処理
の中途でデータ転送することなしにすべての計算を自プ
ロセッサ内で行なうことができる。したがって、処理の
途中では同期待ちが発生せず、本発明によって並列処理
の効率が向上する。

【００２２】また、第２の発明によって配列Ａをあらか
じめＡ（１００）〜Ａ（２０１）の範囲でプロセッサに
割り当てておけば、ステップ１開始前のデータ転送が不
要になるため、さらに並列処理の効率が向上する。

【００２３】なお、本発明は上述の実施例に限定される
ものではない。例えば入力言語は配列構造を持つ任意の
プログラムの言語であってもよく、出力はプログラム言
語、機械オブジェクト、実行可能コードのいずれであっ
てもよい。また、実施例の各構成要素は明確に分離され
ている必要はなく、一部を他の構成要素と共有するよう
な構成であってもよい。その他、本発明はその要旨を逸
脱しない範囲で種々変形して実施することができる。

【００２４】

【発明の効果】以上説明してきたように、第１の発明に
よれば処理の中途でデータ転送することなしにすべての
計算を自プロセッサ内で行なうことができ、したがっ
て、処理の途中では同期待ちが発生せず、並列処理の効
率が向上する。

【００２５】また、第２の発明によれば、ステップ１の
開始前のデータ転送が不要になるため、さらに並列処理
の効率が向上する。

【図面の簡単な説明】

【図１】第１の発明の一実施例を示す構成図である。

【図２】図１に示されたデータ転送コード挿入装置の一
例を示す構成図である。

【図３】第２の発明の一実施例を示す構成図である。

【図４】本発明の効果を説明するためのプログラムの例
である。

【図５】本発明の装置により処理したプログラムの実行
の様子を示す図である。

【図６】従来の装置の構成図である。

【図７】従来の装置により処理したプログラムの実行の
様子を示す図である。

【符号の説明】 １ 構文解析装置 ２ プログラム変換装置 ３ 目的コード生成装置 ４ データ転送コード挿入装置 ５ 計算処理分割割当て装置 ６ 配列データ分割割当て装置 ４１ 計算処理セクション化部 ４２ データフロー解析部 ４３ データ転送命令挿入部

Claims (3)

【特許請求の範囲】
1. 【請求項１】 原始プログラムを、ローカルメモリを備
   えた複数のプロセッサから成る並列計算機システムで並
   列動作するような並列化プログラムに変換するプログラ
   ム変換装置を備えたプログラム言語処理装置において、 原始プログラム中の、ある計算処理の結果が次の計算処
   理の被演算数となるような処理単位（連鎖的な処理単
   位）ごとに、各プロセッサが当該処理を行なうにあたっ
   て必要とする一群のデータ（配列）が各ローカルメモリ
   上に当該処理単位の開始前に用意されるようプロセッサ
   間においてデータ転送させるようなデータ転送コードを
   プログラムに挿入するデータ転送コード挿入装置と、 当該配列を扱う計算処理の一部を複数のプロセッサで重
   複して実行させるようプログラムを変換する装置と、を
   備えたことを特徴とする並列プログラム言語処理装置。
2. 【請求項２】 請求項１記載のプログラム言語処理装置
   において、前記データ転送コード挿入装置は、 前記プログラム変換装置から渡されたプログラムをサブ
   ルーチン単位または原始プログラムの文面上に指示され
   た処理単位に分割する計算処理セクション化部と、 該計算処理セクション化部で分割された処理単位ごとに
   データの定義・参照関係を勘案しながらプログラムの制
   御の流れをたどることにより、当該処理単位の最終結果
   となる配列の各プロセッサ相当部分の計算処理に最小限
   必要なデータ集合を求めるデータフロー解析部と、 前記計算処理セクション化部で分割された処理単位ごと
   に、前記データフロー解析部で求められたデータ集合の
   うち各プロセッサのローカルメモリ上に割り当てられて
   いないデータを、当該データを所有するプロセッサから
   転送する命令を当該処理単位の先頭に挿入するデータ転
   送命令挿入部とから構成されることを特徴とする並列プ
   ログラム言語処理装置。
3. 【請求項３】 原始プログラムを、ローカルメモリを備
   えた複数のプロセッサから成る並列計算機システムで並
   列動作するような目的プログラムに変換するプログラム
   言語処理装置において、 プロセッサに原始プログラムの配列を分割配置するにあ
   たり、その一部を複数のプロセッサに重複して配置させ
   るようプログラムを変換する装置と、 当該配列を扱う計算処理の一部を複数のプロセッサで重
   複して実行させるようプログラムを変換する装置と、を
   備えたことを特徴とする並列プログラム言語処理装置。