JPH08305672A

JPH08305672A - 計算分割最適化方法

Info

Publication number: JPH08305672A
Application number: JP7110473A
Authority: JP
Inventors: Makoto Sato; 真琴佐藤; Kiyomi Umehara; 清美梅原
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1995-05-09
Filing date: 1995-05-09
Publication date: 1996-11-22
Also published as: US5781777A

Abstract

(57)【要約】【目的】ループ内に複数文がある場合、ループ分割せ
ず、ループ内に実行時判定文のない変換プログラムを生
成すること。【構成】並列化コンパイラ100は、構文解析部102、デ
ータ分割解析部103、計算分割部104、通信生成部105、
および、各プロセスに対し、その区間内では各文は実行
されるか否かのいずれかに決まるような区間の集合であ
る非交差区間列をループ実行範囲から生成する非交差区
間列生成部107、非交差区間列をループの実行範囲と
し、ループ本体は元のものを用いたループを複製するル
ープ複製部108、ループ中の文の実行時判定文を削除す
るコード変換部109からなる計算分割最適化部106から構
成される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、電子計算機を用いて、
データ分割指示付きソースプログラムを、並列ライブラ
リ呼び出しを含む分散記憶型並列機向けソースプログラ
ムまたは分散記憶型並列機向けオブジェクトプログラム
に変換するトランスレータまたはコンパイラに関し、特
に、分散記憶型並列計算機への計算分割を最適化する計
算分割最適化方法に関する。

【０００２】

【従来技術】データ分割および計算分割を含む並列化コ
ンパイラの従来の構成を図４０に示す。同図において、
４０００は従来の並列化コンパイラ、１０１はデータ分
割指示付きソースプログラム、１１１はデータ通信入り
ソースプログラム、１１２は辞書、１１３は中間語であ
る。並列化コンパイラ４０００は、データ分割指示付き
ソースプログラム１０１を入力して辞書１１２および中
間語１１３を出力する構文解析部１０２、辞書１１２お
よび中間語１１３を入力してデータ分割を行なった結果
を辞書１１２に反映させるデータ分割解析部１０３、辞
書１１２および中間語１１３を入力してプログラム内の
計算を各プロセッサに分割してその結果を中間語１１３
に反映させる計算分割部１０４、辞書１１２および中間
語１１３を入力して他のプロセッサの持つデータを参照
するための通信命令中間語を生成して、それを中間語１
１３に挿入する通信生成部１０５、中間語１１３を入力
してデータ通信入りソースプログラム１１１を生成する
ソースコード生成部１１０から構成される。

【０００３】まず従来技術を説明する前に、本明細書で
使用する「データ分割指示」、「分散記憶型並列機向け
プログラム」、「計算分割」、「ループ分割」の各用語
について、図２に示したデータ分割指示付きソースプロ
グラム１０１の具体例を用いて説明しておく。最初に
「データ分割指示」について説明する。「データ分割指
示」とは、例えば、図２における文２０２ないし文２０
５で表現されるものである。ここで、文２０２ないし文
２０４でデータを分割することを、文２０５で分割した
データを異なるプロセッサないしプロセスに割り付ける
ことを、それぞれコンパイラに指示している。さらに具
体的に説明すると、文２０２は仮想プロセッサ群の配置
を宣言した文である。仮想プロセッサ群にＭＰという名
前を付け、それらが４台、１次元的に配置されているこ
とを表わしている。即ち、４台の仮想プロセッサは、そ
れぞれ、ＭＰ（１）、ＭＰ（２）、ＭＰ（３）、ＭＰ
（４）という名前で参照される。これら４台の仮想プロ
セッサと実際のプロセッサ（以後、物理プロセッサと呼
ぶ）との対応付けは、通常、ＯＳ（オペレーティングシ
ステム）が行なっている。また、ＯＳは、仮想プロセッ
サをプロセスで実現するので、複数の仮想プロセッサを
１台の物理プロセッサに対応させることも可能である。
本明細書では、以後、仮想プロセッサとプロセスを同じ
意味で用いる。

【０００４】文２０３は、ｎ個の要素Ｔ（１），・・・，
Ｔ（ｎ）からなる仮想配列の宣言であり、複数のユーザ
配列に対してデータ分割をまとめて指示する場合に用い
る。即ち、文２０４およびそれに続く２行により、複数
のユーザ配列を仮想配列Ｔ（Ｊ）に対応させ、後述する
ように文２０５により仮想配列に対するデータ分割を指
示すれば、上記複数配列にデータ分割指示をしたことと
同じことになる。ここで、「仮想配列」とは、実際には
この配列に対するメモリ領域は確保せず、単に、ユーザ
がデータ分割を記述しやすくするためだけに用いる配列
のことである。

【０００５】文２０４は、Ａ（１）とＴ（１），Ａ
（２）とＴ（２），・・・，Ａ（ｎ）とＴ（ｎ）が同じ仮
想プロセッサにある、というユーザ配列Ａ（Ｊ）と仮想
配列Ｔ（Ｊ）との間の対応関係を表わしたものである。
また、それに続く２行は、Ｂ（１）とＴ（１），Ｂ
（２）とＴ（２），・・・，Ｂ（ｎ）とＴ（ｎ）が同じ仮
想プロセッサにあり、Ｃ（１）とＴ（１），Ｃ（２）と
Ｔ（２），...，Ｃ（ｎ）とＴ（ｎ）が同じ仮想プロセ
ッサにある、というユーザ配列Ｂ（Ｊ）およびＣ（Ｊ）
と仮想配列Ｔ（Ｊ）との間の対応関係を表わしたもので
ある。ここで、Ｊは配列添字のパラメータを表わしてお
り、Ｔの宣言文２０３にある１からｎまでの全ての添字
にわたって、上記配列要素毎の対応関係が成立すること
を表わしている。

【０００６】文２０５は、仮想配列Ｔ（Ｊ）のデータ分
割方法と分割データの仮想プロセッサへの割り付け方法
を指示した文である。文２０５の「Ｔ（ＢＬＯＣＫ）」
は仮想配列Ｔ（Ｊ）を配列添字Ｊが連続する部分配列へ
分割することを表わしている。文２０５の「ＯＮＴＯ
ＭＰ」は分割された部分配列を仮想プロセッサＭＰへ割
り付けることを表わしている。

【０００７】即ち、文２００よりｎが「５１２」であ
り、文２０２より仮想プロセッサＭＰは「４台」である
ので、このデータ分割指示は、Ｔ（１），・・・，Ｔ（１
２８）をＭＰ（１）へ、Ｔ（１２９），・・・，Ｔ（２５
６）をＭＰ（２）へ、Ｔ（２５７），・・・，Ｔ（３８
４）をＭＰ（３）へ、Ｔ（３８５），・・・，Ｔ（５１
２）をＭＰ（４）へ、それぞれ割り付けることを表して
いる。このとき、配列Ａ，Ｂ，Ｃの宣言は、文２０１よ
り範囲が（０：ｎ＋１）であって仮想配列Ｔの宣言
（１：ｎ）より大きいため、例えば、Ａ（０）およびＡ
（５１３）に対する割り付けは特に指定されてないが、
「ＢＬＯＣＫ」が添字が連続する部分配列へ分割するこ
とを表わすことから、それぞれＭＰ（１）およびＭＰ
（４）へ割り付けることとする。

【０００８】次に、「分散記憶型並列機向けプログラ
ム」について説明する。「分散記憶型並列機向けプログ
ラム」とは、ここでは、ＳＰＭＤ（Ｓingle Ｐrogram
Ｍultiple Ｄata）型プログラムを指している。ＳＰＭ
Ｄ型プログラムとは、多数のプロセッサないしプロセス
（以後、両者をまとめてプロセスと呼ぶ）を動作させる
ときに用いるプログラムの一種である。即ち、多数のプ
ロセスに対してそれらを動作させるプログラムは唯１つ
（Ｓingle Ｐrogram）であるが、プロセス毎にデータが
異なる（Ｍultiple Ｄata）プログラムのことをいう。
ここで、各プロセスは同じプログラムを実行するが、こ
のことは必ずしも各プロセスがプログラムの同じ部分を
実行することを意味するものではない。即ち、プロセス
は固有のプロセス番号を持っており、プログラム中にこ
のプロセス番号を獲得する文と、その番号により、処理
の仕方を変える文があれば、プロセス毎に異なる処理を
記述することが可能である。

【０００９】図３は、図２のデータ分割指示付きソース
プログラムを図４０の並列化コンパイラ４０００中の構
文解析部１０２ないし通信生成部１０５およびソースコ
ード生成部１１０を用いて変換した結果生成されるデー
タ通信入りソースプログラム１１１を示している。この
データ通信入りソースプログラム１１１はＳＰＭＤ型プ
ログラムの一例である。即ち、図２の文２０２で指示し
た４つのプロセスがこの一つのプログラムを実行し、各
プロセスは配列Ａ，Ｂ，Ｃの異なる部分を用いて計算を
行なう。例えば、図３の文３００中の配列Ａの宣言は０
から１２９になっているが、これは各プロセスのデータ
が全て同じであることを意味しているのではなく、元の
プログラムの配列Ａの添字と各プロセスに割り付けられ
た配列Ａの添字との対応はプロセスにより異なってい
る。図３のプログラムでは、プロセス番号は０から３ま
でであり、プロセス番号０、１、２、３のプロセスが、
それぞれ、前述したＭＰ（１）、ＭＰ（２）、ＭＰ
（３）、ＭＰ（４）に対応しており、例えば、プロセス
番号０、１、２、３における配列要素Ａ(1)は、それぞ
れ、データ分割前の配列要素Ａ(1)、Ａ(129)、Ａ(25
7)、Ａ(385)に対応している。

【００１０】また、図３のプログラムはプロセス毎に、
プログラムの実行の仕方が異なることも示している。文
３０２はプロセス番号を獲得する文である。この文を実
行することにより変数ＭＰにプロセスに固有なプロセス
番号が格納される。

【００１１】図４は、図３における"LOWLIM1,UPPLIM1,L
OWLIM2,UPPLIM2,LOWLIM3,UPPLIM3の値設定コード"３０
４を表わしたものである。ここでは、例えば、文４０
０、４０３、４０６が示すように、プロセス番号ＭＰの
値により、処理を変えている。

【００１２】次に、「計算分割」について説明する。
「計算分割」とは、データ分割指示付きソースプログラ
ムをデータ通信入りソースプログラムに変換する際に、
各プロセスが分担すべき計算部分を求めることを意味し
ている。例えば、図３の文３０５はＤＯループの実行範
囲がLOWLIM1からUPPLIM1までであることを表わしている
が、この値はプロセスによって異なっている。文３０
４、即ち、それを表した図４において、文４０１と文４
０２、文４０４と文４０５、文４０７と文４０８が、そ
れぞれ、プロセス番号がプロセス０、プロセス１〜２、
プロセス３に対するLOWLIM1とUPPLIM1の値を設定してい
る。

【００１３】ここで、計算分割に際しては、"owner com
pute rule"を用いる。これは、ある代入文をどのプロセ
スが実行するかを決める規則である。この規則では、代
入文は、その左辺の配列要素を持つプロセスが計算を行
なうものとする。このルールに従うと、図２におけるＡ
(1)およびＡ(129)は、それぞれ、プロセス番号０および
プロセス番号１のプロセスに割り付けられているので、
Ｊの値が１および１２９の時のループ２０６内の文２０
７は、それぞれ、プロセス番号０および１のプロセスに
よって実行される。

【００１４】次に、「ループ分割」について説明する。
「ループ分割」とは、１つのループを複数のループに分
割することを意味している。図５に一つのループをルー
プ分割した例を示す。図５の文５００および文５０１
が、図２のＤＯループ２０６を２つのループにループ分
割したものを示している。

【００１５】次に、データ分割指示付きソースプログラ
ムを入力し、分散記憶型並列機向けプログラムに変換す
るトランスレータ乃至コンパイラに関する２つの従来技
術を説明する。第１の従来技術は、ループ内に複数の代
入文があり、かつ、上記トランスレータ乃至コンパイラ
のプログラム変換過程において、そのループ内の、ある
２つの代入文の実行範囲が異なる場合、即ち、あるプロ
セスを固定した時、ある文と別の文をそのプロセスが実
行する時のループ制御変数の動く範囲が異なる場合、そ
のループ計算を各プロセスに分割する計算分割の結果と
して、上記ループの実行範囲をループ内の各文の実行範
囲の和集合とし、ループ内の各文を条件文の下で自分の
実行範囲の時のみを実行するコードを生成するものであ
る。上記第１の従来技術として、例えば、コミュニケー
ションズオブジエイー・シー・エム、オーガスト
１９９２／ボリューム３５、ナンバー８、第６６頁〜
第８０頁（COMMUNICATIONS OF THE ACM, August 1992/V
ol.35, No.8, pp.66-80）に記載されたものがある。

【００１６】図３および図４は、図２のプログラムを上
述した第１の従来技術により変換した結果を示す図であ
る。文３００は配列Ａ、Ｂ、Ｃをデータ分割した結果の
配列宣言である。添字０と１２９を追加したことは、通
信のための一時領域（隣からの通信データを格納するた
めの通信用バッファ領域）として用いるために配列の宣
言を拡張したことを表わしている。文３０１はプロセス
番号を格納する変数を宣言する文である。文３０２はＭ
Ｐにプロセス番号を格納する手続き呼び出し文である。
文３０３はデータ通信を表わすコードであるが、本明細
書では省略している。

【００１７】図２の文２００によりｎの値は「５１２」
であり、文２０２〜文２０５により、元の配列Ａ、Ｂ
の、各プロセスへの割り付けは、Ａ(0)〜Ａ(128)とＢ
(0)〜Ｂ(128)がプロセス０に、Ａ(129)〜Ａ(256)とＢ(1
29)〜Ｂ(256)がプロセス１に、Ａ(257)〜Ａ(384)とＢ(2
57)〜Ｂ(384)がプロセス２に、Ａ(385)〜Ａ(513)とＢ(3
85)〜Ｂ(513)がプロセス３に、それぞれ、割り付けられ
ることを示している。

【００１８】これと上述した"owner compute rule"よ
り、文２０７を実行するＪの値は、プロセス０、１、
２、３に対応して、それぞれ、1〜128、129〜256、257
〜384、385〜512となる。これを図３の文３００のよう
に配列を宣言した場合には、各プロセスに対して、すべ
て1〜128となる。これを表わしたのが、図４の文４０９
から文４１７である。この詳細は上記文献に記述されて
いる。

【００１９】同様にして、文２０８を実行する（Ｊ＋
１）の値は、プロセス０、１、２、３に対応して、それ
ぞれ、2〜128、129〜256、257〜384、385〜513となる。
従って、文２０８を実行するＪの値は、プロセス０、
１、２、３に対応して、それぞれ、1〜127、128〜255、
256〜383、384〜512となる。これを図３の文３００のよ
うに配列を宣言した場合には、プロセス０、１、２、３
に対応して、それぞれ、１〜１２７、0〜127、0〜127、
0〜128となる。これを表わしたのが、図４の文４１８か
ら文４２６である。

【００２０】上記のように、ループ内の２つの文の実行
範囲が異なるので、第１の従来技術では、これらの実行
文を実行するために、ループの実行範囲を大きく取らな
ければならない。即ち、上記２つの実行範囲の和集合を
各プロセス範囲毎に取る。和集合をとることによって文
２０７と文２０８に対する実行範囲は、プロセス０、
１、２、３に対して、それぞれ、1〜128と1〜127、1〜1
28と0〜127、1〜128と0〜127、1〜128と0〜128なので、
和集合を取った結果は、それぞれ、1〜128、0〜128、0
〜128、0〜128となる。これを表わしたのが図４の文４
００から文４０８である。この結果、各文は余分な計算
をしないように、和集合で表わされる実行範囲の内、実
行に必要な範囲だけを判定して実行しなければならな
い。これを表わしたのが、図３の文３０６と文３０８で
ある。

【００２１】次に、第２の従来技術について説明する。
第２の従来技術は、ループ内に複数の代入文があったと
しても、そのループがループ分割可能で、その結果、分
割された各ループ内の代入文の実行範囲が全て同じ場合
には、計算分割の結果として、上記分割された各ループ
の実行範囲がループ内の各代入文の実行範囲と同一で、
ループ内の各文には条件文が付かないようなコードを生
成するものである。上記第２の従来技術として、Ｈans
Ｚima＆Ｂarbara Ｃhapman 著「Ｓupercompilers fo
r Ｐarallel and Ｖector Ｃomputers」 1991年（Ａd
dison-Ｗesley Ｐublishing Ｃompany 発行）に記載さ
れたものがある。

【００２２】上述した第２の従来技術を用いた具体例を
以下に説明する。図５は図２の一つのループを複数のル
ープに分割した結果を示したものである。すなわち、図
２の一つのＤＯループ２０６〜２０８を図５の２つのＤ
Ｏループ５００，５０１に分割している。図６は、図５
を上記第２の従来技術により変換した結果である。文６
００は"LOWLIM1,UPPLIM1の値設定コード"であり、この
内容は図７に表わしている。ＤＯループ６０１は図５の
ＤＯループ５００を計算分割した結果である。文６０３
は"LOWLIM2,UPPLIM2の値設定コード"であり、この内容
は図８に示されている。ＤＯループ６０４はＤＯループ
５０１を計算分割した結果である。計算分割によって得
られたＤＯループ６０１，６０４を見れば分かるよう
に、ループ内の各文には条件文が付いていない。なお、
図７および図８におけるLOWLIM1,UPPLIM1,LOWLIM2,UPPL
IM2の値の求め方は、それぞれ、図４で説明したLOWLIM
2,UPPLIM2,LOWLIM3,UPPLIM3の求め方と同じである。

【００２３】

【発明が解決しようとする課題】次に、上述した従来技
術における問題点について検討する。上記第１の従来技
術は変換プログラムの処理速度の点について考慮されて
おらずＤＯループ内に条件文が入っているため処理の高
速化が図れない。例えば、図３において、プログラム変
換後のＤＯループ３０５内の代入文３０７，３０９の実
行時には、それぞれ条件文３０６，３０８を毎回実行し
なくてはならないため、条件文の実行時間が余計にかか
り処理の高速化が図れない、という問題点がある。ま
た、上記第２の従来技術は、変換プログラムの処理速度
の点について考慮されておらずループが増加するに伴い
終了判定に実行時間が余計にかかり処理の高速化が図れ
ない。例えば、図２のＤＯル−プ２０６がル−プ分割さ
れ並列化されて、図６のＤＯル−プ６０１，６０４とな
った結果、増加したループの個数だけループの終了判定
回数が増加してしまう、また、ループ分割により１ルー
プ内の文の数が図２の２０７，２０８の２文から図６の
６０２，６０５の各１文づつに減少するのに伴い、命令
スケジューリングやスーパースカラ等の効果が減少し、
さらに、分割ループの間でデータをやり取りする必要の
ある場合には、余分なLOAD/STORE命令が必要となる、と
いう問題点があった。また、上記第２の従来技術はルー
プ分割が可能な場合に限定されており、ループ分割不可
能なプログラムに対する変換方法の点については全く考
慮されていないため適用範囲が狭い、という問題点があ
った。

【００２４】本発明の目的は、ループ分割せず、ループ
内に条件文のない変換プログラムを生成することであ
る。本発明の別の目的は、上記性質を持つ変換プログラ
ムを生成する際、変換プログラム中に新たに生成される
ループの数を減らすことである。本発明の別の目的は、
ループ分割せず、実行回数が比較的少ないループに対し
ては、各文毎に条件文を生成し、実行回数が多いループ
に対しては、ループ内に条件文がない変換プログラムを
生成することである。本発明の別の目的は、上記いずれ
かの性質を持つ変換プログラムを生成する際、実行しな
いコードを削除することである。

【００２５】

【課題を解決するための手段】本発明の計算分割最適化
方法は、上記目的を達成するために、データ分割指示付
きプログラムを解析して配列要素とそれを割り付けるプ
ロセスとの関係を決定するステップと、各プロセスにつ
いて、配列と文を関係づける規則および配列添字とルー
プ制御変数の間の関係に基づいてループ中の文を自プロ
セスで実行するためのループ制御変数の値の範囲である
文の実行範囲をループ中の各文について決定するステッ
プと、各プロセスについて、互いに重なりのない複数の
区間からなり、それらの和集合が各文の実行範囲の和集
合を包含するような非交差区間列を生成する非交差区間
列生成処理を行なうステップと、非交差区間列の個々の
区間をループ実行範囲とし、ループ内の文は元のループ
と同一のループを複製するループ複製処理を行なうステ
ップと、ループ実行範囲と各文の実行範囲を用いて複製
したループ内の各文に対するコードを変換するコード変
換処理を行なうステップとを有している。

【００２６】ここで、上記非交差区間列生成処理を行う
ステップは、互いに重なりのない各区間内において各文
は実行されるか否かのいずれかに決まるような非交差区
間列を生成するものである。さらに、上記非交差区間列
生成処理を行うステップは、与えられた非交差区間列に
対し、非交差区間列の内、指定された区間選択方法で選
択したいくつかの区間の集合を第１の非交差区間列と
し、選択しなかった区間の内、隣接する区間を融合して
一つの区間として得られる区間の集合を第２の非交差区
間列とし、上記第１の非交差区間列と上記第２の非交差
区間列の和集合を新しい非交差区間列とするものであ
る。なお、上記区間選択方法は、区間の長さが長い順に
並べ、先頭から指定個数までの区間を選択するか、また
は、区間の長さが長い順に並べ、先頭から各区間の長さ
の和を求め、該長さの和が指定の値に達するまでの区間
を選択するようにしたものである。また、上記ループ複
製処理を行うステップは、各プロセスについて、当該プ
ロセスか否かを判定する条件文を生成し、条件文の条件
が成立したとき、プロセスの非交差区間列を用いてルー
プを複製するものである。さらに、上記ループ複製処理
を行うステップは、非交差区間の選択順序を全プロセス
にまたがって決定するために順序表現の作成を行ない、
順序表現に基づいて、全プロセスから、選択するプロセ
スと非交差区間を決定する非交差区間選択処理を行な
い、非交差区間を選択したプロセスに対しては、選択さ
れた非交差区間をループ実行範囲とするプロセスに共通
な単一のループを生成するループ複製処理を行ない、非
交差区間を選択しなかったプロセスに対しては、ループ
を実行しないようなコードを生成し、これらの処理をど
のプロセスにも選択されない非交差区間がなくなるまで
続けるものである。

【００２７】また、上記順序表現の作成は、与えられた
数と与えられた区間に対し、上記数が上記区間の下限値
より小さいときに１、上記区間に含まれるときに２、上
記区間の上限値より大きいときに３を、上記数に対応さ
せることを数の区間に対する順序表現といい、与えられ
た数と与えられた順序付けられた複数の区間に対し、上
記数の区間に対する順序表現を与えられた順序付けに従
って並べてできる数列を、数の順序付き区間に対する順
序表現といい、与えられた数列と与えられた順序付き区
間に対し、上記数列中の各数の上記順序付き区間に対す
る順序表現を上記数列の値の小さい順に並べてできる数
列を数列の順序付き区間に対する順序表現というとき、
各プロセスについて、与えられたループ内の各文に対す
る実行範囲と与えられた非交差区間列に対し、上記非交
差区間列の下限値からなる数列を生成し、上記実行範囲
に指定された順序付けを与え、上記生成された数列の順
序付き区間に対する順序表現を求めるものである。ま
た、上記非交差区間選択処理は、各プロセスについて、
上記求められた順序表現のまだ選択されてない数列の
内、最小の値を選択し、上記選択された値の内、全プロ
セスで最小の数に対応する非交差区間とそのプロセスを
選択するものである。また、上記コード変換処理は、ル
ープ内文の実行範囲がループ実行範囲を包含するとき当
該ループ中の当該文を実行時判定なしで実行するコード
に変換する実行時判定削除処理と、ループ内文の実行範
囲とループ実行範囲が互いに重なりがないとき当該ルー
プ中の当該文を削除する文削除処理とのうち少なくとも
いずれか一方を行ない、上記以外の場合は当該ループ中
の当該文をループ制御変数が当該文の実行範囲に含まれ
る時のみ実行するコードに変換するものである。さら
に、上記コード変換処理は、各プロセスについて、もし
ループ中の全ての文が上記文削除処理により削除される
場合当該ループを実行しないコードに変換するものであ
る。

【００２８】

【作用】本発明では、各プロセスについて、互いに素な
（重なりのない）複数の区間からなり、それらの和集合
がループ中の各文の実行範囲の和集合を包含し、かつ、
その区間内ではループ内の各文は実行されるか否かのい
ずれかに決まるような非交差区間列を生成し、上記非交
差区間列の個々の区間をループ実行範囲としループ本体
は元のループと同じであるループを複製するようにして
いるので、上記各ループ中の各実行文はループ内におい
て、常に実行されるか、常に実行されないかのいずれか
に決まるので、ループ内に条件文のないプログラムの生
成が可能である。よって、コード変換において、ループ
内文の実行範囲がループ実行範囲を包含するなら当該ル
ープ中の当該文を実行時判定なしで実行するコードに変
換し、ループ内文の実行範囲とループ実行範囲が互いに
素なら当該ループ中の当該文を削除すればよい。ここ
で、各プロセス毎に異なる上記非交差区間をループ実行
範囲として持つループをＳＰＭＤ型プログラムとして生
成するための１方法として、ループ生成処理において、
各プロセスについて、当該プロセスか否かを判定する条
件文を生成し、上記条件文の条件が成立したとき、その
プロセスの非交差区間列を用いたループ実行するよう
に、ループを生成すればよい。以上により、ループ分割
せず、ループ内に条件文のない変換プログラムが生成で
きる。

【００２９】また、ループ生成処理において、非交差区
間をループ実行範囲と考えたとき、各プロセスの非交差
区間に対する順序表現が同じになる場合は、順序表現の
定義から、ループ内で常に実行される文の集合が一致す
るので、各プロセスは、ループの実行範囲はプロセス毎
に異なるが、プロセスで共通なループを使うことができ
る。これは、順序表現に基づいて、全プロセスから、選
択するプロセスと非交差区間を決定する非交差区間選択
処理を行ない、上記非交差区間を選択したプロセスに対
しては、選択された非交差区間をループ実行範囲とする
上記プロセスに共通な単一のループを生成するループ生
成処理を行ない、上記非交差区間を選択しなかったプロ
セスに対しては、ループを実行しないようなコードを生
成し、上記ステップをどのプロセスにも選択されない非
交差区間がなくなるまで続けることにより実現できる。
以上により、ループ分割せず、ループ内に条件文のない
変換プログラムを生成する際、変換プログラム中に新た
に生成されるループの数が少ないプログラムが生成でき
る。

【００３０】また、与えられた非交差区間列に対し、上
記非交差区間列の内、指定された区間選択方法で選択し
たいくつかの区間の集合を第１の非交差区間列とし、選
択しなかった区間の内、隣接する区間を融合して一つの
区間として得られる区間の集合を第２の非交差区間列と
し、上記第１の非交差区間列と上記第２の非交差区間列
の和集合を新しい非交差区間列とし、区間選択方法とし
て、区間の長さが長い順に指定個数まで選択するか、区
間の長さが長い順に長さの和が指定の値に達するまで選
択することにより、実行回数が比較的少ないループに対
しては、各文毎に条件文を生成し、第１の非交差区間列
には実行回数が比較的多いループを、また、第２の非交
差区間列には実行回数が比較的少ないループを対応させ
られる。

【００３１】また、このとき、第１の非交差区間列に対
応する各ループ内では、ループ中の各実行文はループ内
において、常に実行されるか、常に実行されないかのい
ずれかに決まるので、ループ内に条件文のないプログラ
ムの生成が可能である。一方、第２の非交差区間列に対
応する各ループ内では、これは成り立たないので、ルー
プ中の各実行文には条件文を付ける必要がある。これ
は、コード変換において、ループ内文の実行範囲がルー
プ実行範囲を包含するなら当該ループ中の当該文を実行
時判定なしで実行するコードに変換し、ループ内文の実
行範囲とループ実行範囲が互いに素（重なりがない）な
ら当該ループ中の当該文を削除し、上記以外の場合は当
該ループ中の当該文をループ制御変数が当該文の実行範
囲に含まれる時のみ実行するコードに変換することによ
り実現できる。以上により、ループ分割せず、実行回数
が比較的少ないループに対しては、各文毎に条件文を生
成し、実行回数が多いループに対しては、ループ内に条
件文がない変換プログラムが生成できる。また、コード
変換の実行時判定削除処理において、各プロセスについ
て、もしループ中の全ての文が削除されるなら当該ルー
プを実行しないコードに変換すれば、上述したいずれか
の性質を持つ変換プログラムを生成する際、実行しない
コードを削除した変換プログラムが生成できる。

【００３２】

【実施例】以下、本発明の第１の実施例を図１〜図４、
図９〜図２６を用いて詳細に説明する。図１は、本発明
に関わる並列化コンパイラの全体構成を示したものであ
る。同図において、１００は並列化コンパイラ、１０１
はデータ分割指示付きソースプログラム、１１１はデー
タ通信入りソースプログラム、１１２は辞書、１１３は
中間語である。並列化コンパイラ１００は、データ分割
指示付きソースプログラム１０１を入力して辞書１１２
および中間語１１３を出力する構文解析部１０２、辞書
１１２および中間語１１３を入力してデータ分割を行な
った結果を辞書１１２に反映させるデータ分割解析部１
０３、辞書１１２および中間語１１３を入力してプログ
ラム内の計算を各プロセッサに分割してその結果を中間
語１１３に反映させる計算分割部１０４、辞書１１２お
よび中間語１１３を入力して他のプロセッサの持つデー
タを参照するための通信命令中間語を生成して、それを
中間語１１３に挿入する通信生成部１０５、中間語１１
３を入力して計算分割結果を最適化する計算分割最適化
部１０６、中間語１１３を入力してデータ通信入りソー
スプログラム１１１を生成するソースコード生成部１１
０から構成される。なお、簡単化のために、同図におい
て図４０の従来の並列化コンパイラと同じ構成要素には
同じ符号を付けてある。計算分割最適化部１０６は、本
発明の特徴とする部分であり、通信生成部１０５で生成
された中間語１１３を入力して、その中の全てのループ
に対して、ループ内の文の実行範囲から互いに重なりの
ない実行範囲の集合である非交差区間列を生成する非交
差区間列生成部１０７、非交差区間列をループの実行範
囲とし、ループ本体は元のものを用いたループを複製す
るループ複製部１０８、ループ中の文の実行時判定文を
削除するコード変換部１０９より構成される。

【００３３】次に、本発明に関わる並列化コンパイラに
おける処理を、図１の並列化コンパイラの構成図を基に
し、図２〜図４および図９〜図２６を用いて詳細に説明
する。図２はデータ分割指示付きソースプログラム１０
１の具体例である。図２に関する説明は従来技術の説明
の際に既に行なったので省略する。図３は図２のデータ
分割指示付きソースプログラムを図１の並列化コンパイ
ラ１００中の構文解析部１０２から通信生成部１０５ま
でと、ソースコード生成部１１０を用いて変換した結果
の、データ通信入りソースプログラム１１１の具体例で
ある。図４は図３における"LOWLIM1,UPPLIM1,LOWLIM2,U
PPLIM2,LOWLIM3,UPPLIM3の値設定コード"を表わしたも
のである。これらに関する説明も従来技術の説明の際に
既に行なったので省略する。

【００３４】図１６および図１８〜図２０は、上記図３
および図４に対する通信生成部１０５における処理直後
の中間語を表わしたもの、および該中間語によって指さ
れる各種テーブルを示すものであり、これらが本実施例
における計算分割最適化部１０６の入力となる。以下、
これらについて詳細に説明する。図１６は中間語の構造
体を表わすための英字と、中間語同士を結ぶポインタを
表わす矢印からなる。ここで、矢印は、その始点にあた
る中間語の構造体の中に、終点にあたる中間語のアドレ
スが格納されていることを表わしている。図１６中、LI
NK１６００はある中間語に不定個の中間語を接続するの
に用いられる中間語である。例えば、STML１６０７に、
SINFO１６０８,ASGN１６０９,SINFO１６１４,ASGN１６
１５の４つの中間語を接続したい場合には、それらの中
間にLINK１６００を挿入してLINK１６００に前記４つの
中間語を接続し、LINK同士を接続し、STML１６０７には
先頭のLINK１６００のみ接続すればよい。このLINKを用
いることにより不定個の中間語を接続するのが可能にな
る。

【００３５】LINFO１６０１はループテーブル１７０１
（図１７参照）を指す中間語である。この中間語および
ループテーブル１７０１の作成は計算分割部１０４が行
なう。LOOP１６０２はＤＯループを表わす中間語であ
る。これは２つのポインタ格納部分をもっており、それ
ぞれLOOPH１６０３とSTML１６０７の中間語のアドレス
が格納されている。LOOPH１６０３はＤＯループの情報
を表わす中間語である。これは３つのポインタ格納部分
をもっており、それぞれJ１６０４，LOWLIM1１６０５，
UPPLIM1１６０６の中間語のアドレスが格納されてい
る。J１６０４は、ループ制御変数を表わす中間語であ
る。LOWLIM1１６０５は、ループの下限値を表わす中間
語である。図１６では変数を表わしている。UPPLIM1１
６０６は、ループの上限値を表わす中間語である。図１
６では変数を表わしている。STML１６０７は、複数の文
をまとめる働きをする中間語である。図１６ではＤＯル
ープ内の文をまとめる中間語を表わしている。

【００３６】SINFO１６０８は、文実行範囲テーブル１
７００（図１７参照）を指す中間語である。この中間語
（SINFO）および文実行範囲テーブル１７００の作成は
計算分割部１０４が行なう。ASGN１６０９は、代入文に
おける等号を表わす中間語である。これは２つのポイン
タ格納部分をもっており、それぞれ代入文の左辺である
A(J)１６１０と代入文の右辺であるMUL１６１１の中間
語のアドレスが格納されている。A(J)１６１０は、配列
を表わす中間語である。MUL１６１１は、掛け算を表わ
す中間語である。C(J)１６１２は、配列を表わす中間語
である。AA１６１３は、変数を表わす中間語である。AS
GN１６０９〜AA１６１３の５つの中間語は、図３の文３
０７に対応する”A(J)＝C(J)*AA”を表わしている。ま
た、ASGN１６１５とそれに接続される中間語は全体で図
３の文３０９に対応する”B(J+1)＝C(J)*BB”を表わし
ている。

【００３７】次に、図１７を用いて、それぞれ中間語SI
NFO，LINFOによって指される文実行範囲テーブル１７０
０，ループテーブル１７０１について説明する。文実行
範囲テーブル１７００は、ＤＯループ内の実行文の計算
分割後の実行範囲、すなわち、ＤＯループ内の実行文の
計算が各プロセスに分割されたとき、各プロセスがその
文を実行するときのループ繰り返し範囲を表わしてい
る。文実行範囲テーブル１７００は、nextp１７０６，p
lownum１７０７，puppnum１７０８，slowlim１７０９，
supplim１７１０から構成される。nextp１７０６は、次
の文実行範囲テーブルへのポインタを表わす。plownum
１７０７は、この文実行範囲テーブルを持つプロセス番
号の下限値である。puppnum１７０８は、この文実行範
囲テーブルを持つプロセス番号の上限値である。slowli
m１７０９は、plownum１７０７とpuppnum１７０８が示
す範囲内にあるプロセス番号を持つプロセスが、文を実
行するときのループ繰り返し範囲の下限値である。supp
lim１７１０は、plownum１７０７とpuppnum１７０８が
示す範囲内にあるプロセス番号を持つプロセスが、文を
実行するときのループ繰り返し範囲の上限値である。

【００３８】ループテーブル１７０１は、ＤＯループの
計算分割後の実行範囲を表わすループ実行範囲テーブル
１７０２を指すとともに、ループの付加情報を表わすテ
ーブルであり、lptblp１７１１およびnstmt１７１２か
ら構成される。lptblp１７１１はループ実行範囲テーブ
ル１７０２へのポインタを表わす。nstmt１７１２はル
ープ内の実行文の数を表わす。

【００３９】ループ実行範囲テーブル１７０２は、ＤＯ
ループの計算分割後の実行範囲、すなわち、ＤＯループ
の計算が各プロセスに分割されたとき、各プロセスがル
ープを実行するときのループ繰り返し範囲を表わすテー
ブルであり、nextp１７１３，plownum１７１４，puppnu
m１７１５，llowlim１７１６，lupplim１７１７，lary
（lary2）１７１８，selectp１７１９，snum１７２０，
sflag１７２１から構成される。nextp１７１３は、次の
ループ実行範囲テーブルへのポインタを表わす。plownu
m１７１４は、このループ実行範囲テーブルを持つプロ
セス番号の下限値である。puppnum１７１５は、このル
ープ実行範囲テーブルを持つプロセス番号の上限値であ
る。llowlim１７１６は、plownum１７１４とpuppnum１
７１５が示す範囲内にあるプロセス番号を持つプロセス
が、ループを実行するときのループ繰り返し範囲の下限
値である。lupplim１７１７は、plownum１７１４とpupp
num１７１５が示す範囲内にあるプロセス番号を持つプ
ロセスが、ループを実行するときのループ繰り返し範囲
の上限値である。lary（lary2）１７１８は、ポインタ
配列１７０３の要素数を表わす数である。これは以下の
説明の都合上、初めはlaryと言う変数名で参照される
が、後にlary2という変数名に変わる。selectp１７１９
は、ポインタ配列１７０３へのポインタである。snum１
７２０とsflag１７２１は第１の実施例では用いない。

【００４０】ポインタ配列１７０３は、非交差区間テー
ブル１７０４を指すポインタからなる配列である。その
要素数はループ実行範囲テーブル１７０２中のlary（la
ry2）１７１８に格納されている。

【００４１】非交差区間テーブル１７０４は、各プロセ
ス毎のループ実行範囲を、「非交差区間」と呼ぶ互いに
重なりのない区間に分割した時の区間情報を表わすテー
ブルであり、nextp１７２２，nlowlim１７２３，nuppli
m１７２４，length１７２５，orderp１７２６から構成
される。nextp１７２２は次の非交差区間テーブルへの
ポインタである。nlowlim１７２３は非交差区間の下限
値である。nupplim１７２４は非交差区間の上限値であ
る。length１７２５は非交差区間の区間の長さである。
orderp１７２６は第１の実施例では用いない。

【００４２】図１８は、SINFO１６０８が指す文実行範
囲テーブルを模式的に表したものである。文実行範囲テ
ーブルは、３つのプロセス範囲（プロセス番号０，１〜
２，３）に対応して、３つの文実行範囲テーブル１８０
０、１８０１、１８０２がポインタ（図１７のnextp参
照）で順に接続されている。最初の文実行範囲テーブル
１８００は図４の文４０９〜文４１１に対応している。
文４０９はプロセス番号が０の場合を扱うための判定文
である。これは１８０３でプロセス番号の下限値が
「０」、１８０４でプロセス番号の上限値が「０」であ
ることに対応している。このとき、文４１０は実行文３
０７を実行するループ範囲の下限値LOWLIM2が「１」で
あることを表わしているので、１８０５は「１」であ
る。同様にして文４１１は実行文３０７を実行するルー
プ範囲の上限値UPPLIM2が「１２８」であることを表わ
しているので、１８０６は「１２８」である。

【００４３】次の文実行範囲テーブル１８０１は図４の
文４１２〜文４１４に対応している。文４１２はプロセ
ス番号が１から２までの場合を扱う判定文である。これ
は１８０７でプロセス番号の下限値が「１」、１８０８
でプロセス番号の上限値が「２」であることに対応して
いる。このとき、文４１３は実行文３０７を実行するル
ープ範囲の下限値LOWLIM2が「１」であることを表わし
ているので、１８０９は「１」である。同様にして文４
１４は実行文３０７を実行するループ範囲の上限値UPPL
IM2が「１２８」であることを表わしているので、１８
１０は「１２８」である。

【００４４】次の文実行範囲テーブル１８０２は図４の
文４１５〜文４１７に対応している。文４１５はプロセ
ス番号が３の場合を扱う判定文である。これは１８１１
でプロセス番号の下限値が「３」、１８１２でプロセス
番号の上限値が「３」であることに対応している。この
とき、文４１６は実行文３０７を実行するループ範囲の
下限値LOWLIM2が「１」であることを表わしているの
で、１８１３は「１」である。同様にして文４１７は実
行文３０７を実行するループ範囲の上限値UPPLIM2が
「１２８」であることを表わしているので、１８１４は
「１２８」である。

【００４５】図１９は、SINFO１６１４が指す文実行範
囲テーブルを模式的に表わしたものである。文実行範囲
テーブルは、３つのプロセス範囲（プロセス番号０，１
〜２，３）に対応して、３つの文実行範囲テーブル１９
００、１９０１、１９０２がポインタで順に接続されて
いる。最初の文実行範囲テーブル１９００は図４の文４
１８〜文４２０に対応している。文４１８はプロセス番
号が０の場合を扱う判定文である。これは１９０３でプ
ロセス番号の下限値が「０」、１９０４でプロセス番号
の上限値が「０」であることに対応している。このと
き、文４１９は実行文３０９を実行するループ範囲の下
限値LOWLIM3が「１」であることを表わしているので、
１９０５は「１」である。同様にして文４２０は実行文
３０９を実行するループ範囲の上限値UPPLIM3が「１２
７」であることを表わしているので、１９０６は「１２
７」である。

【００４６】次の文実行範囲テーブル１９０１は図４の
文４２１〜文４２３に対応している。文４２１はプロセ
ス番号が１から２までの場合を扱う判定文である。これ
は１９０７でプロセス番号の下限値が「１」、１９０８
でプロセス番号の上限値が「２」であることに対応して
いる。このとき、文４２２は実行文３０９を実行するル
ープ範囲の下限値LOWLIM3が「０」であることを表わし
ているので、１９０９は「０」である。同様にして文４
２３は実行文３０７を実行するループ範囲の上限値UPPL
IM3が「１２７」であることを表わしているので、１９
１０は「１２７」である。次の文実行範囲テーブル１９
０２は図４の文４２４〜文４２６に対応している。文４
２４はプロセス番号が３の場合を扱う判定文である。こ
れは１９１１でプロセス番号の下限値が「３」、１９１
２でプロセス番号の上限値が「３」であることに対応し
ている。このとき、文４２５は実行文３０９を実行する
ループ範囲の下限値LOWLIM3が「０」であることを表わ
しているので、１９１３は「０」である。同様にして文
４２６は実行文３０７を実行するループ範囲の上限値UP
PLIM3が「１２８」であることを表わしているので、１
９１４は「１２８」である。

【００４７】図２０は、LINFO１６０１が指すループテ
ーブルとループ実行範囲テーブルを表わしたものであ
る。ループテーブル２０００はループ実行範囲テーブル
をポインタで接続し、ループ実行範囲テーブルは、３つ
のプロセス範囲（プロセス番号０，１〜２，３）に対応
して、３つのループ実行範囲テーブル２００１、２００
２、２００３がポインタ（図１７の１７１３）で順に接
続されている。ループテーブル２０００は図２の文２０
６に対応しており、ループ中に２つの実行文があること
から、２００４は「２」となる。最初のループ実行範囲
テーブル２００１は図４の文４００〜文４０２に対応し
ている。文４００はプロセス番号が０の場合を扱う判定
文である。これは２００５でプロセス番号の下限値が
「０」、２００６でプロセス番号の上限値が「０」であ
ることに対応している。このとき、文４０１はループ３
０５のループ範囲の下限値LOWLIM1が「１」であること
を表わしているので、２００７は「１」である。同様に
して文４０２はループ３０５のループ範囲の上限値UPPL
IM1が「１２８」であることを表わしているので、２０
０８は「１２８」である。

【００４８】次のループ実行範囲テーブル２００２は図
４の文４０３〜文４０５に対応している。文４０３はプ
ロセス番号が１から２までの場合を扱う判定文である。
これは２００９でプロセス番号の下限値が「１」、２０
１０でプロセス番号の上限値が「２」であることに対応
している。このとき、文４０４はループ３０５のループ
範囲の下限値LOWLIM1が「０」であることを表わしてい
るので、２０１１は「０」である。同様にして文４０５
はループ３０５のループ範囲の上限値UPPLIM1が「１２
８」であることを表わしているので、２０１２は「１２
８」である。次のループ実行範囲テーブル２００３は図
４の文４０６〜文４０８に対応している。文４０６はプ
ロセス番号が３の場合を扱う判定文である。これは２０
１３でプロセス番号の下限値が「３」、２０１４でプロ
セス番号の上限値が「３」であることに対応している。
このとき、文４０７はループ３０５のループ範囲の下限
値LOWLIM1が「０」であることを表わしているので、２
０１５は「０」である。同様にして文４０８はループ３
０５のループ範囲の上限値UPPLIM1が「１２８」である
ことを表わしているので、２０１６は「１２８」であ
る。ループ実行範囲テーブル２００１、２００２、２０
０３の上記以外の欄には、初期化されて「０」が入って
いる。

【００４９】次に、上記図１６〜図２０を入力として、
計算分割最適化部１０６が行なう処理を、図１、図９〜
図１５、および図２１〜図２６を用いて説明する。計算
分割最適化部１０６において、全てのループに対して、
非交差区間列生成部１０７，ループ複製部１０８，コー
ド変換部１０９の処理が行われる。まず、非交差区間列
生成部１０７について説明する。非交差区間列生成部１
０７は、各プロセッサ毎に、指定された区間選択法を用
いて非交差区間列を生成する部分である。図９は非交差
区間列生成部１０７の処理の説明図である。まず、ステ
ップ９００において未処理のプロセス範囲があるか否か
を判定する。今の場合、プロセス範囲の数はループ実行
範囲テーブルや文実行範囲テーブルの数と同じになるよ
うに設計されているので、プロセス範囲は図２０の２０
０５、２００６、２００９、２０１０、２０１３、１０
１４の値から分かるように、０、１〜２、３の３つがあ
るため、ステップ９００は判定結果はＹＥＳとなる。以
下、プロセス範囲は、０、１〜２、３の順に動かし、以
降の処理はすべて指定されたプロセス範囲内で行なうも
のとする。

【００５０】次に、ステップ９０１において、２個の整
数からなる構造体ARYの配列で、要素数がループ中の文
の数の２倍のものを確保する。今の場合、ループ中の文
の数は図２０の２００４（ループ中の実行文の数）の値
が「２」なので、ステップ９０１では要素数が４個（２
の２倍）の構造体ARYの配列を確保する。図１０は構造
体ARYを説明するための図である。構造体ARYは２つの構
成要素からなり、それぞれ整数型である。第１の構成要
素LIM１０００には区間の上限値または下限値を表わす
数が格納され、第２の構成要素FLAG１００１にはLIM１
０００に格納された数が上限値であるか下限値であるか
の区別を表わす数が格納される。

【００５１】次に、非交差基本区間列生成ステップ９０
２の処理を行なう。非交差基本区間列生成ステップ９０
２は、任意の１つのプロセスに対して、ループ中の各文
の実行範囲の上限値、下限値から、重なりのない区間列
である非交差区間列を生成するステップである。図１１
は非交差基本区間列生成ステップ９０２の詳細を説明す
る図である。図１１では、まずステップ１１００におい
て、ｊが１から（ループ中の文の数）まで、ARY(2*j-
1).LIMにｊ番目の文の実行範囲の下限値を、ARY(2*j-
1).FLAGに１を、ARY(2*j).LIMにｊ番目の文の実行範囲
の上限値を、ARY(2*j).FLAGに２を格納する。今の場
合、（ループ中の文の数）は２なので、以下、ステップ
１１００における代入処理を２回行なう。ｊ＝１の時、
１番目の文の実行範囲の下限値は、図１８におけるプロ
セス範囲が０の場合を考えればよいのだから、１８０５
より「１」となる。ｊ＝１の時、ARY(2*j-1)＝ARY(1)な
ので、ARY(1).LIMには「１」が格納される。ここで、AR
Y(1).LIMは、１番目の配列要素ARY(1)の第１の構成要素
LIMを表わす。同様にして、１番目の文の実行範囲の上
限値は１８０６より「１２８」となり、ARY(２).LIMに
は「１２８」が格納される。ｊ＝２の時、２番目の文の
実行範囲の下限値は、図１９における、プロセス範囲が
０の場合を考えればよいのだから、１９０５より「１」
となる。ｊ＝２の時、ARY(2*j-1)＝ARY(３)なので、ARY
(３).LIMには「１」が格納される。同様にして、２番目
の文の実行範囲の上限値は１９０６より「１２７」とな
り、ARY(４).LIMには「１２７」が格納される。

【００５２】図２１はステップ１１００の処理の結果、
値を格納された構造体の配列アレイを表わしたものであ
る。配列アレイ２１００はプロセス範囲が０の場合に対
応するアレイである。ARY(１).LIM、ARY(２).LIM、ARY
(３).LIM、ARY(４).LIMはそれぞれ、２１０３、２１０
４、２１０５、２１０６に対応し、上の説明で格納され
た値が入っている。ステップ１１００における、”ARY
(2*j-1).FLAG←１”、”ARY(2*j).FLAG←２”の処理結
果は２１０７、２１０８、２１０９、２１１０に対応し
ている。

【００５３】次に、ステップ１１０１において、配列ア
レイをLIMとFLAGによる辞書式順序で昇順にソートす
る。即ち、LIMの値が小さい配列要素を前に移動し、LIM
の値が同じ場合には、FLAGの値が小さいものを前に移動
する。次に、ステップ１１０２で、ソートされた配列ア
レイから重複を除いたものをARY(1),...,ARY(lary)とす
る。図２２は、以上の処理結果の、構造体の配列アレイ
を表わしたものである。例えば、図２１の配列アレイ２
１００に対して、ステップ１１０１、１１０２を施した
結果が配列アレイ２２００である。図２１の配列アレイ
２１００において、２１０５と２１０９は２１０３と２
１０７と重複しているので、図２２の配列アレイ２２０
０では除かれている。このとき、配列要素の数laryは
「３」になる。

【００５４】次に、ステップ１１０３、１１０４の説明
を図２２、図２３を用いて行なう。ステップ１１０３で
は、（lary−１）個の非交差区間テーブルNIIAを確保
し、ポインタで順に接続する。図２２の配列アレイ２２
００の場合、laryが３なので、２個（＝lary−１）の非
交差区間テーブルNIIAを確保し、ポインタで順に接続す
る。図２３はステップ１１０３、１１０４の結果の、非
交差区間テーブルNIIAを表わしたものである。ステップ
１１０３で確保された２個の非交差区間テーブルNIIA
は、図２３（ａ）の非交差区間テーブル２３００、２３
０１に対応している。両者は矢印で示される方法でポイ
ンタで接続されている。

【００５５】次に、ステップ１１０４において、全ての
非交差区間テーブルNIIAについて、ｊ＝１から（lary−
１）まで、ARY(j).FLAG＝１ならNIIA.nlowlimにARY(j).
LIMを、ARY(j).FLAG＝２ならNIIA.nlowlimにARY(j).LIM
＋１を、ARY(j+1).FLAG＝１ならNIIA.nupplimにARY(j+
1).LIM-１を、ARY(j+1).FLAG＝２ならNIIA.nupplimにAR
Y(j+1).LIMを格納する。以下、ステップ１１０４の処理
を、図２２の配列アレイ２２００と図２３（ａ）の２つ
の非交差区間テーブル２３００、２３０１を用いて説明
する。この場合、laryが３なので、ｊは１から２（＝ｊ
−１））までの範囲を動く。ｊ＝１の時、非交差区間テ
ーブル２３００を結果の格納に用いる。図２２の配列ア
レイ２２００のの２１０７よりARY(１).FLAG=1なので、
NIIA.nlowlim２３０７には２１０３に対応したARY(１).
LIM＝「１」が入る。また、２１１０よりARY(２).FLAG=
２なので、NIIA.nupplim２３０８には２１０６に対応し
たARY(２).LIM＝「１２７」が入る。なお、２３０９、
２３１０は初期化により「０」が格納されている。ｊ＝
２の時、非交差区間テーブル２３０１を結果の格納に用
いる。図２２の配列アレイ２２００の２１１０よりARY
(２).FLAG=２なので、NIIA.nlowlim２３１１には２１０
６に対応したARY(２).LIM＝１２７に１を加えた「１２
８」が入る。また、２１０８よりARY(３).FLAG=２なの
で、NIIA.nupplim２３１２には２１０４に対応したARY
(３).LIM＝「１２８」が入る。なお、２３１３、２３１
４は初期化により「０」が格納されている。

【００５６】次に、非交差区間列選択ステップ９０３を
図１２、図１３、図２４、図２５を用いて説明する。非
交差区間列選択ステップ９０３は、図１１で生成した非
交差基本区間列のうち、図１３で説明する区間選択法に
より選択されなかった区間について、それらの内で隣接
する区間があれば融合するステップである。図１２は非
交差区間列選択ステップ９０３を詳細に説明するための
図である。ステップ１２００では、要素数（lary−１）
の配列Selectを確保し、（lary−１）個の非交差区間テ
ーブルのアドレスを格納する。今の場合、laryが３なの
で、要素数２（＝lary−１）の配列Selectを確保し、２
個の非交差区間テーブルのアドレスを格納する。要素数
２の配列Selectを表わしたのが、図２４（ａ）の２４０
０、２４０１で、２個の非交差区間テーブル２３００、
２３０１へ向かう矢印がポインタを表わしている。

【００５７】次に区間選択ステップ１２０１の処理を行
なう。区間選択ステップ１２０１は、図１１で生成した
非交差基本区間の内、与えられた指定方法により区間を
選択する区間選択を行なうステップである。本実施例で
は区間の長さが長い順に指定個数まで選択する区間選択
法について説明する。他の区間選択法として区間の長さ
が長い順に長さの和が指定の値に達するまで選択する区
間選択法がある。この区間選択法は、指定個数まで選択
する本実施例の処理に、区間の長さを求める処理と、上
記長さの和が指定値に達したか否かを判定する処理を付
加すればよい。

【００５８】図１３は区間選択ステップ１２０１の詳細
なフローチャートである。図１３において、ステップ１
３００で、全ての非交差区間テーブルNIIAについて、j=
1〜（lary−１）まで、NIAA.lengthを、NIIA.nupplim-N
IIA.nlowlim＋１にする処理を行なう。今の場合、lary
が「３」なので、２個（＝lary−１）の非交差区間テー
ブル２３００、２３０１について、ｊが１から２までの
処理を行なう。非交差区間テーブル２３００におけるNI
IA.nupplimは２３０８より「１２７」であり、NIIA.nlo
wlimは２３０７より１である。従って、NIIA.length２
３０９には「１２７」が入る。また、非交差区間テーブ
ル２３０１におけるNIIA.nupplimは２３１２より「１２
８」であり、NIIA.nlowlimは２３１１より「１２８」で
ある。従って、NIIA.length２３１３には「１」が入
る。これらの結果を図２４（ａ）に示す。図２４は区間
選択ステップ１２０１の処理後の配列Selectと非交差区
間テーブルを示したものである。

【００５９】ステップ１３０１では、ステップ１３００
で求めたlengthをキーにして配列Selectを降順にソート
する。２３００におけるlength、即ち、NIIA.lengthは
「１２７」であり、２３０１におけるlength、即ち、NI
IA.lengthは「１」なので、配列Select２４００、２４
０１のソート結果は元のままである。次のステップ１３
０２では、Select(1)からSelect(ns)までが指す非交差
区間テーブルを選択する。今の場合、ｎｓ＝１として、
Select(1)が指す非交差区間テーブルのみを選択する。
ここで、nsは選択した非交差区間の数を表わし、以降、
ns＝１とする。以上でステップ１２０１の処理を終わ
る。以降の処理では、選択したことを表わす印は何も必
要なく、単にｎｓに値が保存されていればよい。

【００６０】次に、ステップ１２０２では、Select(ns
＋1)，・・・Select(lary-1)をそれらが指す非交差区間テ
ーブルの下限値をキーにして昇順にソートする。今の場
合、ｎｓが１、laryが３なので、(ns＋1)＝(lary-1)＝
２であり、１つの配列要素Select(２)２４０１が指す非
交差区間テーブルを下限値をキーにして昇順にソートす
る。配列要素は唯１つなので、ソートの結果は元のまま
である。ステップ１２０３では、ｊにns＋１を、ｊｊに
ｊを入れ、ｊ＜(lary-1)かつｊｊ＜(lary-1)の間、uppJ
JにSelect(jj)が指すテーブルの上限値を、uppJJ１にSe
lect(jj＋１)が指すテーブルの下限値を、uppJJ＋１＝u
ppJJ１ならSelect(j)が指すテーブルの上限値をSelect
(jj＋１)が指すテーブルの上限値を格納し、jjにjj+1を
入れる。また、上記以外ならjにj+1を、jjにjj＋１を入
れ、Select(j)にSelect(jj)を入れる。今の場合、ｎｓ
が「１」、laryが「３」なので、ｊの初期値は「２」、
ステップ１２０３中のループはｊが２未満の時、ループ
処理を行なう。従って、今の場合ｊが２未満でないの
で、ステップ１２０３ではループ処理を行なわない。

【００６１】次のステップ１２０４では、ｎｓ≧lary-1
ならlary2にｎｓを、それ以外ならlary2にｊを入れる。
今の場合、ｎｓが「１」、laryが「３」なので、ns ≧
lary-1は成立せず、lary2にはｊ、即ち、ステップ１２
０３における初期値「２」が代入される。ステップ１２
０５では、Select(1)、・・・Select(lary2)をそれらが指
す非交差区間テーブルの下限値をキーとして昇順にソー
トする。今の場合、lary2が２なので、Select(1)２４０
０, Select(2)２４０１をそれらが指す非交差区間テー
ブルの下限値をキーにして昇順にソートする。Select
(1)２４００が指す非交差区間テーブル２３００の下限
値２３０７は「１」、Select(２)２４０１が指す非交差
区間テーブル２３０１の下限値２３１１は「１２８」な
ので、ソートの結果は元のままである。図２５は非交差
区間列生成部１０７の処理後の、非交差区間テーブルを
表わす。

【００６２】図９のフローチャートで示されるように、
以上でプロセス範囲が０の場合の非交差区間列生成部１
０７の処理が終了する。従って、図２５（ａ）がプロセ
ス範囲が０の場合の、非交差区間列生成部１０７におけ
る処理後の非交差区間テーブルの状態を表したものとな
っている。上記ステップ１２０５までの説明により、図
２５（ａ）における２４００、２４０１、２３００、２
３０１は図２４（ａ）のままである。以上でプロセス範
囲０の場合の非交差区間列生成部１０７の処理を終了す
る。

【００６３】次に、ステップ９０４で、次のプロセス範
囲に処理を移す。今の場合、プロセス範囲が１〜２の場
合がまだ存在するので、ステップ９００における判定は
ＹＥＳとなる。以下、プロセス範囲が０の場合と同様に
処理を行なうので、簡単に説明する。ループ中の文の数
は図２０の実行文の数を示す２００４より「２」なの
で、ステップ９０１では要素数が４個の構造体ARYの配
列を確保する。次に、非交差基本区間列生成ステップ９
０２の処理を行なう。ステップ９０２では、その詳細を
示す図１１のステップ１１００における（ループ中の文
の数）は「２」なので、以下、ステップ１１００の代入
処理を２回行なう。ｊ＝１の時、１番目の文の実行範囲
の下限値は、図１８における、プロセス範囲が１〜２の
場合、即ち、１８０１を考えればよいのだから、１８０
９より「１」となる。同様にして、１番目の文の実行範
囲の上限値は１８１０より「１２８」となる。ｊ＝２の
時、２番目の文の実行範囲の下限値は、図１９におけ
る、プロセス範囲が１〜２の場合、即ち、１９０１を考
えればよいのだから、１９０９より「０」となる。同様
にして、２番目の文の実行範囲の上限値は１９１０より
「１２７」となる。

【００６４】以上より、図２１の配列アレイ２１０１に
おける、２１１１、２１１２、２１１３、２１１４の値
は、それぞれ、「１」、「１２８」、「０」、「１２
７」となる。また、ステップ１１００における、FLAGへ
の代入文の処理結果より、２１１５、２１１６、２１１
７、２１１８はそれぞれ、「１」、「２」、「１」、
「２」となる。次に、ステップ１１０１においてLIMとF
LAGによる辞書式順序で昇順にソートする。その結果を
図２２の配列アレイ２２０１に示す。ステップ１１０１
でソートした結果は重複を持たないので、ステップ１１
０１、１１０２の処理結果は、図２２の配列アレイ２２
０１に示すようになる。このとき、配列要素の数laryは
「４」となる。次のステップ１１０３では、laryが
「４」なので、３個（＝lary−１）の非交差区間テーブ
ルNIIAを確保し、ポインタで順に接続する。上で確保さ
れた３個の非交差区間テーブルNIIAは、図２３（ｂ）の
２３０２、２３０３、２３０４に対応している。

【００６５】次に、ステップ１１０４において、laryが
「４」なので、ｊは１から３（＝lary−１）までの範囲
を動く。以下、図２２の配列アレイ２２０１と図２３
（ｂ）の非交差区間テーブルNIIA２３０２、２３０３、
２３０４を用いて説明する。ｊ＝１の時、２２１７より
ARY(１).FLAG=1なので、NIIA.nlowlim２３１５には２１
１３に対応したARY(１).LIM＝「０」が入る。また、２
１１５よりARY(２).FLAG=１なので、NIIA.nupplim２３
１６には２１１１に対応したARY(２).LIM＝１から１を
引いた「０」が入る。ｊ＝２の時、２１１５よりARY
(２).FLAG=１なので、NIIA.nlowlim２３１９には２１１
１に対応したARY(２).LIM＝「１」が入る。また、２１
１８よりARY(３).FLAG=２なので、NIIA.nupplim２３２
０には２１１４に対応したARY(３).LIM＝「１２７」が
入る。ｊ＝３の時、２１１８よりARY(２).FLAG=２なの
で、NIIA.nlowlim２３２３には２１１４に対応したARY
(２).LIM＝１２７に１を加えた「１２８」が入る。ま
た、２１１６よりARY(３).FLAG=２なので、NIIA.nuppli
m２３２４には２１１２に対応したARY(３).LIM＝「１２
８」が入る。以上でプロセス１〜２でのステップ９０２
の処理を終わる。この時の結果を図２３（ｂ）に示す。

【００６６】次に、ステップ９０３の詳細を示した図１
２のステップ１２００では、laryが「４」なので、要素
数３（＝lary−１）の配列Select２４０２、２４０３、
２４０４を確保し、上記３個の非交差区間テーブルのア
ドレスを順に格納する。次に区間選択ステップ１２０１
を行なう。区間選択ステップ１２０１の詳細を示す図１
３のステップ１３００では、laryが「４」なので、３個
（＝lary−１）の非交差区間テーブル２３０２、２３０
３、２３０４について、ｊが１から３までの間、処理を
行なう。その結果はそれぞれ、図２４で示すとおり、２
３１７が「１」、２３２１が「１２７」、２３２５が
「１」となる。ステップ１３０１では、上記ステップ１
３００で求めたlengthをキーにしてSelectを降順にソー
トするので、結果は、２３０３、２３０２、２３０４の
順になり、２４０２、２４０３、２４０４がそれぞれ、
図２４に矢印で示しているように、２３０３、２３０
２、２３０４を指す。ステップ１３０２では、ｎｓ＝１
として、Select(1)が指す非交差区間テーブル２３０３
のみを選択する。次のステップ１２０２では、ｎｓが
「１」、laryが「４」なので、Select(２)２４０２、Se
lect(３)２４０４が指す非交差区間テーブルを下限値を
キーにして昇順にソートする。ソートの結果は元のまま
である。

【００６７】ステップ１２０３では、ｎｓが「１」、la
ryが「４」なので、ｊおよびｊｊの初期値は「２」、ス
テップ１２０３中のループはｊおよびｊｊが３未満の
時、処理を行なう。まず、uppjj, uppjj1の値は、それ
ぞれ、Select(2)が指すテーブル２３０２の上限値
「０」, Select(3)が指すテーブル２３０４の下限値
「１２８」なので、uppjj+1=uppjj1は成立しない。よっ
て、ｊ，ｊｊは共に３となり、Select(3)からSelect(3)
へ代入が行なわれるが、これは結局、何もしないのと同
じである。このとき、ｊ，ｊｊの値はループの判定条件
を満たさなくなるので、ループ処理はこれで終了する。
ステップ１２０４では、ｎｓが「１」、laryが「４」な
ので、ns ≧ lary-1は成立せず、lary2にはj、即ち、ス
テップ１２０３において得られた「３」が代入される。
ステップ１２０５では、lary2が「３」なので、Select
(1)２４０３, Select(2)２４０２、Select(３)２４０４
をそれらが指す非交差区間テーブルの下限値をキーにし
て昇順にソートする。上記下限値は、順に、「１」、
「０」、「１２８」なので、昇順にソートした結果は図
２５（ｂ）の２４０２、２４０３、２４０４のようにな
る。以上でプロセス範囲１〜２の処理を終了する。

【００６８】次に、ステップ９０４で次のプロセス範囲
に処理を移す。まだプロセス範囲３が存在するので、ス
テップ９００における判定はＹＥＳとなる。ループ中の
文の数は図２０の２００４より「２」なので、ステップ
９０１では要素数が４個（２の２倍）の構造体ARYの配
列を確保する。

【００６９】次に、非交差基本区間列生成ステップ９０
２の処理を行なう。ステップ１１００における（ループ
中の文の数）は「２」なので、以下、ステップ１１００
に書かれた代入処理を２回行なう。ｊ＝１の時、１番目
の文の実行範囲の下限値は、図１８における、プロセス
範囲が３の場合、即ち、１８０２を考えればよいのだか
ら、１８１３より「１」となる。同様にして、１番目の
文の実行範囲の上限値は１８１４より「１２８」とな
る。ｊ＝２の時、２番目の文の実行範囲の下限値は、図
１９における、プロセス範囲が３の場合、即ち、１９０
２を考えればよいのだから、１９１３より「０」とな
る。同様にして、２番目の文の実行範囲の上限値は１９
１４より「１２８」となる。以上より、２１０２におけ
る、２１１９、２１２０、２１２１、２１２２の値は、
それぞれ、「１」、「１２８」、「０」、「１２８」と
なる。また、ステップ１１００における、FLAGへの代入
文の処理結果より、２１２３、２１２４、２１２５、２
１２６はそれぞれ、「１」、「２」、「１」、「２」と
なる。ステップ１１０１でソートした結果は重複を持つ
ので、ステップ１１０１、１１０２の処理結果は、２２
０２のようになる。このとき、配列要素の数laryは
「３」となる。ステップ１１０３では、laryが「３」な
ので、２個（＝lary−１）の非交差区間テーブルNIIAを
確保し、ポインタで順に接続する。上で確保された２個
の非交差区間テーブルNIIAは、図２３（ｃ）の２３０
５、２３０６に対応している。

【００７０】次に、ステップ１１０４において、laryが
「３」なので、ｊは１から２までの範囲を動く。以下、
図２２の２２０２と図２３の２３０５、２３０６を用い
て説明する。ｊ＝１の時、２１２５よりARY(１).FLAG=1
なので、NIIA.nlowlim２３２７には２１２１に対応した
ARY(１).LIM＝「０」が入る。また、２１２３よりARY
(２).FLAG=１なので、NIIA.nupplim２３２８には２１１
９に対応したARY(２).LIM＝１から１を引いた「０」が
入る。ｊ＝２の時、２１２３よりARY(２).FLAG=１なの
で、NIIA.nlowlim２３３１には２１１９に対応したARY
(２).LIM＝「１」が入る。また、２１２４よりARY(３).
FLAG=２なので、NIIA.nupplim２３３２には２１２０に
対応したARY(３).LIM＝「１２８」が入る。ステップ１
２００では、laryが「３」なので、要素数２（＝lary−
１）の配列Select２４０５、２４０６を確保し、これら
２個の非交差区間テーブルのアドレスを順に格納する。

【００７１】次に区間選択ステップ１２０１を行なう。
ステップ１２０１の詳細を示す図１３のステップ１３０
０では、laryが「３」なので、２個（＝lary−１）の非
交差区間テーブル２３０５、２３０６について、ｊが１
から２までの間、処理を行なう。その結果はそれぞれ、
図２４（ｃ）で示すとおり、２３２９が「１」、２３３
３が「１２８」となる。ステップ１３０１では、ステッ
プ１３００で求めたlengthをキーにしてSelectを降順に
ソートするので、その結果は、２３０６、２３０５の順
になり、２４０５、２４０６がそれぞれ、図２４に矢印
で示しているように、２３０６、２３０５を指す。ステ
ップ１３０２では、ｎｓ＝１として、Select(1)が指す
非交差区間テーブル２３０６のみを選択する。

【００７２】次のステップ１２０２では、ｎｓが
「１」、laryが「３」なので、１個の配列要素Select
(２)２４０６が指す非交差区間テーブルを下限値をキー
にして昇順にソートする。配列要素は唯１つなので、ソ
ートの結果は元のままである。ステップ１２０３では、
ｎｓが「１」、laryが「３」なので、ｊの初期値は
「２」（＝ｎｓ＋１）、ステップ１２０３中のループは
ｊが２未満の時、ループ処理を行なう。従って、今の場
合、ｊは２未満でないから、ステップ１２０３ではルー
プ処理を行なわない。次のステップ１２０４では、ｎｓ
が「１」、laryが「３」なので、ns ≧ lary-1は成立せ
ず、lary2には「ｊ」、即ち、ステップ１２０３におけ
る初期値「２」が代入される。ステップ１２０５では、
lary2が「２」なので、Select(1)２４０５, Select(2)
２４０６をそれらが指す非交差区間テーブルの下限値を
キーにして昇順にソートする。上記下限値は、順に、
「１」、「０」なので、ソートした結果は図２５（ｃ）
の２４０５、２４０６のようになる。以上でプロセス範
囲３の処理を終了する。次に、ステップ９０４では次の
プロセス範囲に処理を移すが、他にプロセス範囲は存在
しないので、ステップ９００における判定はＮＯとな
り、これで非交差区間列生成部１０７の処理を全て終了
する。

【００７３】次に、ループ複製部１０８を、図１４、図
２５、図２６を用いて説明する。ループ複製部１０８
は、プログラムを実行するプロセス番号を判定する条件
文と、各プロセス毎に、そのプロセスの非交差区間列の
各区間の上下限値をループの上下限値とする、区間の数
だけのループを、元のループから複製して生成する部分
である。図１４はループ複製部１０８を説明するための
図である。図２６はループ複製部１０８、およびコード
変換部１０９の処理結果を中間語の代わりに、ソースプ
ログラムスタイルで表わしたものである。まず、図１４
のステップ１４００において、未処理のプロセス範囲が
あるか否かを判定する。今の場合、図２０のループ実行
範囲テーブルが、プロセス範囲が０、１〜２、３の３つ
あることから、上記判定はＹＥＳとなる。以下、プロセ
ス範囲が０、１〜２、３の順に処理を行なう。

【００７４】次に、ステップ１４０１において、プロセ
ス番号がプロセス範囲に含まれる条件を表す条件文ＩＬ
を生成し、上記条件文を元のループ直前で実行するよう
にプログラムＩＬに接続する。ここで、プロセス番号を
表わす変数は適当に作成する。今の場合、ＭＰをプロセ
ス番号を表わす変数とする。生成プログラムでは、ＭＰ
に実際のプロセス番号を格納するために、実行時にシス
テム問い合わせサブルーチンを呼ぶ。図２６の文２６０
０のWHOAMIがこれにあたり、これによって、ＭＰに実際
のプロセス番号が格納される。今はプロセス範囲が０の
場合を考えているので、ステップ１４０１における、プ
ロセス番号がプロセス範囲に含まれる条件は、"IF(MP.E
Q.0)"となる。この条件文を元のループ直前で実行する
ようにプログラムＩＬに接続したものをソースプログラ
ムスタイルで表わしたものが図２６のＩＦ文２６０１で
ある。ここで、ＩＦ文２６０１のブロックの直後には、
元のループがあるはずだが、これは後にステップ１４０
５により削除されるので、図２６には書かれていない。

【００７５】次のステップ１４０２では、元のループＩ
Ｌのコピーをlary2個作成し、上記条件の成立時、順に
ループを実行するように上記条件文ＩＬに接続する。プ
ロセス範囲が０の場合のlary2は、図２５における配列S
elect２４００、２４０１の要素数と同じなので「２」
である。従って、ステップ１４０２では、元のループＩ
Ｌのコピーを２個作成し、条件文２６０１が成立すると
きに実行するように接続する。次のステップ１４０３で
は、上記lary2個のループＩＬの上限値、下限値をSelec
t(1),・・・Select(lary2)が示す非交差区間テーブルの上
限値、下限値に設定する。今の場合、図２５のSelect
(1)２４００が指す非交差区間テーブルの上限値、下限
値はそれぞれ、２３０７、２３０８より、「１」、「１
２７」なので、第１のＤＯループの上限値、下限値はそ
れぞれ、「１」、「１２７」となる。これを表わしたの
が図２６の２６０２であり、このＤＯループは条件文２
６０１が成立するときのみ実行される。また、図２５の
Select(２)２４０１が指す非交差区間テーブルの上限
値、下限値はそれぞれ、２３１１、２３１２より、「１
２８」、「１２８」なので、第２のＤＯループの上限
値、下限値はそれぞれ、「１２８」、「１２８」とな
る。これを表わしたのが図２６の２６０５であり、この
ＤＯループは条件文２６０１が成立するときのみ実行さ
れる。以上でプロセス範囲０における処理を終了する。

【００７６】次のステップ１４０４により、次のプロセ
ス範囲の処理へ移る。まず、ステップ１４００における
判定は、現在のプロセス範囲が１〜２であることから、
ＹＥＳとなる。今度はプロセス範囲が１〜２なので、ス
テップ１４０１における、プロセス番号がプロセス範囲
に含まれる条件は、"IF(MP.GE.1.AND.MP.LE.2)"とな
る。この条件文を元のループ直前で実行するようにプロ
グラムＩＬに接続したものをソースプログラムスタイル
で表わしたものが図２６の２６０７である。プロセス範
囲が１から２の場合のlary2は、図２５における配列Sel
ect２４０２、２４０３、２４０４の要素数と同じなの
で「３」である。従って、ステップ１４０２において、
元のループＩＬのコピーを３個作成し、条件文２６０７
が成立するときに実行するように接続する。

【００７７】次に、ステップ１４０３において、図２５
のSelect(1)２４０２が指す非交差区間テーブルの上限
値、下限値はそれぞれ、２３１５、２３１６より、
「０」、「０」なので、第１のＤＯループの上限値、下
限値はそれぞれ、「０」、「０」となる。これを表わし
たのが２６０８であり、このＤＯループは条件文２６０
７が成立するときのみ実行される。また、図２５のSele
ct(２)２４０３が指す非交差区間テーブルの上限値、下
限値はそれぞれ、２３１９、２３２０より、「１」、
「１２７」なので、第２のＤＯループの上限値、下限値
はそれぞれ、「１」、「１２７」となる。これを表わし
たのが２６１０であり、このＤＯループは条件文２６０
７が成立するときのみ実行される。また、図２５のSele
ct(３)２４０４が指す非交差区間テーブルの上限値、下
限値はそれぞれ、２３２３、２３２４より、「１２
８」、「１２８」なので、第３のＤＯループの上限値、
下限値はそれぞれ、「１２８」、「１２８」となる。こ
れを表わしたのがＤＯループ２６１３であり、このＤＯ
ループは条件文２６０７が成立するときのみ実行され
る。以上でプロセス範囲１〜２の処理を終了する。

【００７８】ステップ１４０４により、次のプロセス範
囲の処理へ移る。まず、ステップ１４００における判定
は、現在のプロセス範囲が３であることから、ＹＥＳと
なる。今はプロセス範囲が３なので、ステップ１４０１
における、プロセス番号がプロセス範囲に含まれる条件
は、"IF(MP.EQ.3)"となる。この条件文を元のループ直
前で実行するようにプログラムＩＬに接続したものをソ
ースプログラムスタイルで表わしたものが図２６の条件
文２６１５である。プロセス範囲が３の場合のlary2
は、図２５における配列Select２４０５、２４０６の要
素数と同じなので「２」である。従って、ステップ１４
０２において、元のループＩＬのコピーを２個作成し、
条件文２６１５が成立するときに実行するように接続す
る。

【００７９】次に、ステップ１４０３において、図２５
のSelect(1)２４０５が指す非交差区間テーブルの上限
値、下限値はそれぞれ、２３２７、２３２８より、
「０」、「０」なので、第１のＤＯループの上限値、下
限値はそれぞれ、「０」、「０」となる。これを表わし
たのがＤＯループ２６１６であり、このＤＯループは条
件文２６１５が成立するときのみ実行される。

【００８０】また、図２５のSelect(２)２４０６が指す
非交差区間テーブルの上限値、下限値はそれぞれ、２３
３１、２３３２より、「１」、「１２８」なので、第２
のＤＯループの上限値、下限値はそれぞれ、「１」、
「１２８」となる。これを表わしたのがＤＯループ２６
１８であり、このＤＯループは条件文２６１５が成立す
るときのみ実行される。以上でプロセス範囲３の処理を
終了する。次に、ステップ１４０４により、次のプロセ
ス範囲の処理へ移る。ステップ１４００では現在のプロ
セス範囲が他に存在しないことから、判定はＮＯとな
り、ステップ１４０５へ移る。ステップ１４０５におい
て元のループＩＬを削除する。これでループ複製部１０
８の処理を全て終了する。

【００８１】次に、コード変換部１０９の処理を図１５
と図２６を用いて説明する。コード変換部１０９は、図
１４で生成した各ループ内の各文について、文をそのま
まにするか、削除するか、条件文を文に付加するか、あ
るいはループそのものを削除するか、の処理を行う部分
である。図１５はコード変換部１０９の処理の処理を説
明するための図である。ステップ１５００は、複製ルー
プがあるか否かを判定するステップである。今の場合、
ループ複製部１０８で複製されたループが、図２６に示
すように、２６０２、２６０５、２６０８、２６１０、
２６１３、２６１６、２６１８だけあるので、判定はＹ
ＥＳである。以下、上記順序で各ループに対して処理を
行なう。

【００８２】ステップ１５０１においてループ内に文が
あるか否かを判定する。今の場合、各ループ内には、AS
GN１６０９から始まる文とASGN１６１５から始まる文の
２つの文があるので、判定はＹＥＳである。以下、上記
順序で各文に対して処理を行なう。さらに、第１の文の
処理には、ASGN１６０９および直前のSINFO１６０８が
指す文実行範囲テーブルを参照しながら処理を行なう。
同様に、第２の文の処理には、ASGN１６１５および直前
のSINFO１６１４が指す文実行範囲テーブルを参照しな
がら処理を行なう。

【００８３】以下、ループ２６０２はプロセス範囲が０
の場合のループなので、文実行範囲テーブルもプロセス
範囲が０の場合を参照することに注意する。ステップ１
５０２において、文の実行範囲がループ実行範囲を包含
するなら文ＩＬをそのままにし、文の実行範囲とループ
実行範囲が互いに素（重なりがない）なら文ＩＬを削除
し、上記以外ならループ制御変数が文の実行範囲内にあ
ることを表す条件ＩＬを生成、上記条件の成立時に文を
実行するように文ＩＬを上記条件ＩＬに接続し、上記条
件ＩＬをプログラムＩＬに接続する。今の場合、ＤＯル
ープ２６０２のループ実行範囲は文２６０２に示されて
いるように「１〜１２７」であり、第１の文の実行範囲
は図１８の文実行範囲テーブルの１８０５、１８０６に
示されているように、「１〜１２８」なので、文の実行
範囲がループ実行範囲を包含している。従って、ステッ
プ１５０２は、文ＩＬに対して何も処理しない。これを
示したのが図２６の文２６０３である。

【００８４】次のステップ１５０４で次の文へ移る。ス
テップ１５０１では、まだ第２の文があるので、判定は
ＹＥＳである。第２の文の実行範囲は図１９の文実行範
囲テーブルの１９０５、１９０６に示すように、「１〜
１２７」なので、文の実行範囲とループ実行範囲は等し
い。これは包含していると言い替えることができる。従
って、ステップ１５０２は、文ＩＬに対して何も処理し
ない。これを示したのが、図２６の文２６０４である。

【００８５】再びステップ１５０４で次の文へ移る。次
のステップ１５０１では、ループ２６０２に対して２つ
の文の処理を終えたので、他に文は存在しない。よっ
て、今度はステップ１５０１の判定はＮＯとなり、ステ
ップ１５０３へ移る。ステップ１５０３では、ループ内
に文は元のまま２つあるので、何も処理せず、次の複製
ループへ移る。

【００８６】ステップ１５００における判定は、まだ複
製ループ２６０５が存在するので、ＹＥＳである。次の
ステップ１５０１における判定は、ループ内にASGN１６
０９およびASGN１６１５で示される２つの文があるの
で、これもＹＥＳである。以下、上記順序で各文に対し
て処理を行なう。また、ループ２６０５はプロセス範囲
が０の場合のループなので、文実行範囲テーブルもプロ
セス範囲が０の場合を参照する。ループ２６０５のルー
プ実行範囲は２６０５に示すように「１２８〜１２８」
であり、第１の文の実行範囲は図１８の文実行範囲テー
ブルの１８０５、１８０６に示すように、「１〜１２
８」なので、文の実行範囲がループ実行範囲を包含して
いる。従って、ステップ１５０２は、文ＩＬに対して何
も処理しない。これを示したのが、図２６の文２６０６
である。

【００８７】ステップ１５０４で次の文へ移る。ステッ
プ１５０１における判定は、第２の文があるので、ＹＥ
Ｓである。第２の文の実行範囲は図１９の文実行範囲テ
ーブルの１９０５、１９０６に示すように、「１〜１２
７」なので、文の実行範囲とループ実行範囲は互いに素
（重なりがない）である。従って、ステップ１５０２に
おいて第２の文を削除する。これにより文２６０５のル
ープ内には第２の文は現われない。

【００８８】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６０５に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定は
ＮＯとなり、ステップ１５０３へ移る。ステップ１５０
３では、ループ内に文は１つ存在するので、何も処理せ
ず、次の複製ループへ移る。

【００８９】ステップ１５００における判定は、複製ル
ープ２６０８が存在するので、ＹＥＳである。ステップ
１５０１における判定は、ループ内にASGN１６０９およ
びASGN１６１５で示される２つの文があるので、ＹＥＳ
である。以下、上記順序で各文に対して処理を行なう。
また、ループ２６０８はプロセス範囲が１〜２の場合の
ループなので、文実行範囲テーブルもプロセス範囲が１
〜２の場合を参照する。ループ２６０８のループ実行範
囲は文２６０８に示すように「０〜０」であり、第１の
文の実行範囲は図１８の文実行範囲テーブルの１８０
９、１８１０に示すように、「１〜１２８」なので、文
の実行範囲とループ実行範囲は互いに素（重なりがな
い）である。従って、ステップ１５０２において第１の
文を削除する。これにより文２６０８のループ内には第
１の文は現われない。

【００９０】ステップ１５０４で次の文へ移る。ステッ
プ１５０１における判定は、第２の文があるので、ＹＥ
Ｓである。第２の文の実行範囲は図１９の文実行範囲テ
ーブルの１９０９、１９１０に示すように、「０〜１２
７」なので、文の実行範囲がループ実行範囲を包含して
いる。従って、ステップ１５０２は、文ＩＬに対して何
も処理しない。これを示したのが、図２６の文２６０９
である。

【００９１】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６０８に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定は
ＮＯとなり、ステップ１５０３へ移る。ステップ１５０
３では、ループ内に文は１つ存在するので、何も処理せ
ず、次の複製ループへ移る。

【００９２】ステップ１５００における判定は、複製ル
ープ２６１０が存在するので、ＹＥＳである。ステップ
１５０１における判定は、ループ内にASGN１６０９およ
びASGN１６１５で示される２つの文があるので、ＹＥＳ
である。

【００９３】以下、上記順序で各文に対して処理を行な
う。また、ループ２６１０はプロセス範囲が１〜２の場
合のループなので、文実行範囲テーブルもプロセス範囲
が１〜２の場合を参照する。ループ２６１０のループ実
行範囲は文２６１０に示すように「１〜１２７」であ
り、第１の文の実行範囲は図１８の文実行範囲テーブル
の１８０９、１８１０に示すように、「１〜１２８」な
ので、文の実行範囲がループ実行範囲を包含している。
従って、ステップ１５０２は、文ＩＬに対して何も処理
しない。これを示したのが、図２６の文２６１１であ
る。

【００９４】ステップ１５０４で次の文へ移る。ステッ
プ１５０１における判定は、第２の文があるので、ＹＥ
Ｓである。第２の文の実行範囲は図１９の文実行範囲テ
ーブルの１９０９、１９１０に示すように、「０〜１２
７」なので、文の実行範囲がループ実行範囲を包含して
いる。従って、ステップ１５０２は、文ＩＬに対して何
も処理しない。これを示したのが、図２６の文２６１２
である。

【００９５】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６１０に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定結
果はＮＯとなり、ステップ１５０３へ移る。ステップ１
５０３では、ループ内に文は元のまま２つあるので、何
も処理せず、次の複製ループへ移る。

【００９６】ステップ１５００における判定は、複製ル
ープ２６１３が存在するので、ＹＥＳである。ステップ
１５０１における判定は、ループ内にASGN１６０９およ
びASGN１６１５で示される２つの文があるので、ＹＥＳ
である。以下、上記順序で各文に対して処理を行なう。
また、ループ２６１３はプロセス範囲が１〜２の場合の
ループなので、文実行範囲テーブルもプロセス範囲が１
〜２の場合を参照する。ループ２６１３のループ実行範
囲は文２６１３に示すように「１２８〜１２８」であ
り、第１の文の実行範囲は図１８の文実行範囲テーブル
の１８０９、１８１０に示すように、「１〜１２８」な
ので、文の実行範囲がループ実行範囲を包含している。
従って、ステップ１５０２は、文ＩＬに対して何も処理
しない。これを示したのが、図２６の文２６１４であ
る。ステップ１５０４で次の文へ移る。ステップ１５０
１では、第２の文があるので、判定はＹＥＳである。第
２の文の実行範囲は図１９の文実行範囲テーブルの１９
０９、１９１０に示すように、「０〜１２７」なので、
文の実行範囲とループ実行範囲は互いに素（重なりがな
い）である。従って、ステップ１５０２は、第２の文を
削除する。これにより図２６の文２６１３のループ内に
は第２の文は現われない。

【００９７】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６１３に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定結
果はＮＯとなり、ステップ１５０３へ移る。ステップ１
５０３では、ループ内に文は１つ存在するので、何も処
理せず、次の複製ループへ移る。ステップ１５００にお
ける判定は、複製ループ２６１６が存在するので、ＹＥ
Ｓである。ステップ１５０１における判定は、ループ内
にASGN１６０９およびASGN１６１５で示される２つの文
があるので、ＹＥＳである。以下、上記順序で各文に対
して処理を行なう。また、ループ２６１６はプロセス範
囲が３の場合のループなので、文実行範囲テーブルもプ
ロセス範囲が３の場合を参照する。ループ２６１６のル
ープ実行範囲は文２６１６に示すように「０〜０」であ
り、第１の文の実行範囲は図１８の文実行範囲テーブル
の１８１３、１８１４に示すように、「１〜１２８」な
ので、文の実行範囲とループ実行範囲は互いに素（重な
りがない）である。従って、ステップ１５０２は、第１
の文を削除する。これにより図２６の文２６１６のルー
プ内には第１の文は現われない。

【００９８】ステップ１５０４で次の文へ移る。ステッ
プ１５０１における判定は、第２の文があるので、ＹＥ
Ｓである。第２の文の実行範囲は図１９の文実行範囲テ
ーブルの１９１３、１９１４に示すように、「０〜１２
８」なので、文の実行範囲がループ実行範囲を包含して
いる。従って、ステップ１５０２は、文ＩＬに対して何
も処理しない。これを示したのが、図２６の文２６１７
である。

【００９９】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６１６に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定結
果はＮＯとなり、ステップ１５０３へ移る。ステップ１
５０３では、ループ内に文は１つ存在するので、何も処
理せず、次の複製ループへ移る。

【０１００】ステップ１５００における判定は、複製ル
ープ２６１８が存在するので、ＹＥＳである。ステップ
１５０１における判定は、ループ内にASGN１６０９およ
びASGN１６１５で示される２つの文があるので、ＹＥＳ
である。以下、上記順序で各文に対して処理を行なう。
また、ループ２６１８はプロセス範囲が３の場合のルー
プなので、文実行範囲テーブルもプロセス範囲が３の場
合を参照する。ループ２６１８のループ実行範囲は文２
６１８に示すように「１〜１２８」であり、第１の文の
実行範囲は図１８の文実行範囲テーブルの１８１３、１
８１４に示すように、「１〜１２８」なので、文の実行
範囲がループ実行範囲を包含している。従って、ステッ
プ１５０２は、文ＩＬに対して何も処理しない。これを
示したのが、図２６の文２６１９である。

【０１０１】ステップ１５０４で次の文へ移る。ステッ
プ１５０１における判定は、第２の文があるので、ＹＥ
Ｓである。第２の文の実行範囲は図１９の文実行範囲テ
ーブルの１９１３、１９１４に示すように、「０〜１２
８」なので、文の実行範囲がループ実行範囲を包含して
いる。従って、ステップ１５０２は、文ＩＬに対して何
も処理しない。これを示したのが、図２６の文２６２０
である。

【０１０２】ステップ１５０４で次の文へ移る。ステッ
プ１５０１では、ループ２６１８に対して２つの文の処
理を終えたので、他に文は存在しない。よって、判定結
果はＮＯとなり、ステップ１５０３へ移る。ステップ１
５０３では、ループ内に文は元のまま２つあるので、何
も処理せず、次の複製ループへ移る。

【０１０３】ステップ１５００における判定は、他に複
製ループは存在しないので、今度はＮＯである。これ
で、不要な文を削除するコード変換部１０９の処理を全
て終了する。以上の処理を行った後、ソースコード生成
部１１０を経て出力されたデータ通信入りソースプログ
ラムが図２６に示すものである。

【０１０４】次に、本発明の第２の実施例を図１、図１
６、図１７、図１８〜図２０、図２５、図２７〜図３８
を用いて説明する。第２実施例と第１実施例の違いは図
１におけるループ複製部１０８のみである。従って、こ
こでは、非交差区間列生成部１０７までの部分の説明は
省略して、ループ複製部１０８以降の処理についてのみ
説明する。ループ複製部１０８に対する入力は、図１６
の中間語、図１８から図２０までのテーブル、および図
２５の配列Selectと非交差区間テーブルである。但し、
図２０において、lary2１７１８に対応する部分には、
配列Selectの要素数が格納されており、selectp１７１
９に対応する部分には、配列Selectの先頭要素のアドレ
スが格納されている。ここで、図１７における１７０５
は、順序表現を格納する配列orderを示し、orderp１７
２６には配列order１７０５の先頭アドレスが格納され
る。

【０１０５】図２７は第２の実施例におけるループ複製
部１０８の処理を説明するための図である。ループ複製
部１０８は、プログラムを実行する全てのプロセスに対
して、同じ数だけのループを、元のループから複製して
生成する部分である。まず、順序表現作成ステップ２７
００の処理を行なう。この処理内容は図２８で説明され
る。図２８は、後述する図２９のプロセス間共用ループ
複製ステップにおいて各プロセス毎の非交差区間列から
どの区間を選択するか、またはそのプロセスからは選択
しないかを決定するのに必要な順序表現を作成するステ
ップである。図３０は、図２８の処理の結果得られる、
ループ実行範囲テーブル、およびそれからポイントされ
るテーブルの状態を示したものである。

【０１０６】以下、図３０を使って、図２８の順序表現
作成ステップを詳細に説明する。ステップ２８００にお
いて、nstmt（図１７参照）にループ中の実行文の数を
入れる。本実施例では、図１６において、LOOP１６０２
に接続された中間語が、ループをASGN１６０９，ASGN１
６１５に接続された中間語が文を示しているので、ルー
プ中の実行文の数は「２」となる。よって、ステップ２
８００ではnstmtに「２」が代入される。次のステップ
２８０１において、処理すべきプロセス範囲があるか否
かを判定する。今の場合、図２０のループ実行範囲テー
ブルが、プロセス範囲が０、１〜２、３の３つあること
から、判定結果はＹＥＳとなる。以下、プロセス範囲が
０、１〜２、３の順に処理を行なう。ステップ２８０２
では、ｊを「１」に初期化する。ステップ２８０３にお
いて、１≦ｊ≦lary2 か否かを判定する。今の場合、l
ary2は配列Selectの要素数に等しいので、図２５より
「２」となる。従って、ステップ２８０３の条件式は"1
≦ｊ≦2"となる。今はｊは値が「１」に初期化されてい
るので、ステップ２８０３における判定結果はＹＥＳと
なる。

【０１０７】次のステップ２８０４において、要素数ns
tmtの配列orderを確保し、Select(j)が指す非交差区間
テーブルに接続し、文番号ｋに１を入れ、low に Selec
t(j)が指す非交差区間テーブルの下限値を代入する。今
の場合、要素数２の配列orderを確保して、これをSelec
t(1)２４００が指す非交差区間テーブル２３００に接続
する。配列orderを表わしたのが、図３０の３０００、
３００１であり、この配列orderは図３０に示されるよ
うに、非交差区間テーブル２３００中の２３１０（orde
rp）によってポイントされる。さらに、ステップ２８０
４では、文番号ｋに「１」を、lowにSelect(1)２４００
が指す非交差区間テーブル２３００の２３０７に格納さ
れた下限値「１」を代入する。

【０１０８】次のステップ２８０５において、１≦ｋ≦
nstmtか否かを判定する。今の場合、文番号ｋが
「１」、nstmtが「２」なのでこの判定はＹＥＳとな
る。次のステップ２８０６において、test_lowに文の実
行範囲の下限値を、test_uppに文の実行範囲の上限値を
入れるとともに、low＜test_lowならorder(K)に「１」
を入れ、low≧test_low、かつ、low≦test_uppならorde
r(K)に「２」を入れ、low＞test_lowならorder(K)に
「３」を入れる。今の場合、プロセス範囲が０で第１の
文を考えているのだから、test_low, test_uppは、それ
ぞれ、図１８の１８０５、１８０６より「１」、「１２
８」となる。ｋとlowはともに「１」なので、"low≧tes
t_low、かつ、low≦test_upp"が成立し、order(1)には
「２」が代入される。これを表わしたのが、図３０の３
０００である。ステップ２８０７ではｋを１更新してス
テップ２８０５に戻る。今の場合、ｋの値を「２」に更
新する。

【０１０９】ステップ２８０５では、今度は文番号ｋが
「２」で、nstmtが「２」なので判定はＹＥＳとなる。
ステップ２８０６では、今、プロセス範囲が０で第２の
文を考えているのだから、test_low, test_uppは、それ
ぞれ、図１９の１９０５、１９０６より「１」、「１２
７」となる。ｋは「２」、lowは「１」なので、"low≧t
est_low、かつ、low≦test_upp"が成立し、order(2)に
は「２」が代入される。これを表わしたのが、図３０の
３００１である。次のステップ２８０７により、ｋを更
新し「３」とする。ステップ２８０５では、文番号ｋが
「３」、nstmtが「２」なので判定結果はＮＯとなる。
ステップ２８０８において、ｊの値を１更新してステッ
プ２８０３に戻る。今の場合、ｊを「２」に更新する。

【０１１０】ステップ２８０３において、ｊは「２」
で、lary2は「２」なので、判定結果はＹＥＳとなる。
ステップ２８０４では、要素数２の配列orderを確保し
て、これをSelect(２)２４０１が指す非交差区間テーブ
ル２３０１に接続する。配列orderを表わしたのが、図
３０の３００２、３００３であり、これは図３０に示さ
れるように、非交差区間テーブル２３０１中の２３１４
によってポイントされる。さらに、ステップ２８０４で
は、文番号ｋに「１」を、lowにSelect(２)２４０１が
指す非交差区間テーブル２３０１の２３１１に格納され
たの下限値「１２８」を代入する。ステップ２８０５で
は、文番号ｋが「１」、nstmtが「２」なので判定結果
はＹＥＳとなる。ステップ２８０６は、今の場合、プロ
セス範囲が０で第１の文を考えているのだから、test_l
ow, test_uppは、それぞれ、図１８の１８０５、１８０
６より「１」、「１２８」となる。ｋは「１」、lowは
「１２８」なので、"low≧test_low、かつ、low≦test_
upp"が成立し、order(1)には「２」が代入される。これ
を表わしたのが、図３０の３００２である。ステップ２
８０７により、ｋの値を「２」に更新してステップ２８
０５に戻る。

【０１１１】ステップ２８０５では、文番号ｋが
「２」、nstmtが「２」なので判定結果はＹＥＳとな
る。ステップ２８０６は、今の場合、プロセス範囲が０
で第２の文を考えているのだから、test_low, test_upp
は、それぞれ、図１９の１９０５、１９０６より
「１」、「１２７」となる。ｋは「２」、lowは「１２
８」なので、"low＞test_upp"が成立し、order(2)には
「３」が代入される。これを表わしたのが、図３０の３
００３である。ステップ２８０７により、ｋの値を
「３」に更新する。ステップ２８０５では、文番号ｋが
「３」、nstmtが「２」なので判定結果はＮＯとなる。
ステップ２８０８により、ｊの値を「３」に更新する。
ステップ２８０３において、ｊは「３」、lary2は
「２」なので、判定結果はＮＯとなる。ステップ２８０
９で次のプロセス範囲へ処理を移し、ステップ２８０１
に戻る。

【０１１２】ステップ２８０１では、まだプロセス範囲
１〜２が存在するので、判定結果はＹＥＳとなる。ステ
ップ２８０２では、ｊを「１」に初期化する。ステップ
２８０３におけるlary2は配列Selectの要素数に等しい
ので、図２５より「３」となる。従って、ステップ２８
０３の条件式は"1≦j≦３"となる。今の場合はｊは値が
「１」に初期化されているので、ステップ２８０３での
判定はＹＥＳとなる。ステップ２８０４では、要素数２
の配列orderを確保して、これをSelect(1)２４０２が指
す非交差区間テーブル２３０２に接続する。配列order
を表わしたのが、図３０の３００４、３００５であり、
これは図３０に示されるように、非交差区間テーブル２
３０２中の２３１８からポイントされている。さらに、
ステップ２８０４では、文番号ｋに「１」を、lowにSel
ect(1)２４０２が指す非交差区間テーブル２３０２の２
３１５に格納された下限値「０」を代入する。ステップ
２８０５は、文番号ｋが「１」、nstmtが「２」なので
判定結果はＹＥＳとなる。ステップ２８０６は、今の場
合、プロセス範囲が１〜２で第１の文を考えているのだ
から、test_low, test_uppは、それぞれ、図１８の１８
０９、１８１０より「１」、「１２８」となる。ｋは
「１」、lowは「０」なので、"low＜test_low"が成立
し、order(1)には「１」が代入される。これを表わした
のが、図３０の３００４である。ステップ２８０７によ
り、ｋの値を「２」に更新してステップ２８０５に戻
る。

【０１１３】ステップ２８０５は、文番号ｋが「２」、
nstmtが「２」なので、判定結果はＹＥＳとなる。ステ
ップ２８０６は、今の場合、プロセス範囲が１〜２で第
２の文を考えているのだから、test_low, test_uppは、
それぞれ、図１９の１９０９、１９１０より「０」、
「１２７」となる。ｋは「２」、lowは「０」なので、"
low≧test_low、かつ、low≦test_upp"が成立し、order
(2)には「２」が代入される。これを表わしたのが、図
３０の３００５である。ステップ２８０７により、ｋの
値を「３」に更新してステップ２８０５に戻る。ステッ
プ２８０５は、文番号ｋが「３」、nstmtが「２」なの
で判定結果はＮＯとなる。ステップ２８０８において、
ｊの値を「２」に更新してステップ２８０３に戻る。

【０１１４】ステップ２８０３において、ｊは「２」、
lary2は「３」なので、判定結果はＹＥＳとなる。ステ
ップ２８０４では、要素数２の配列orderを確保して、
これをSelect(２)２４０３が指す非交差区間テーブル２
３０３に接続する。配列orderを表わしたのが、図３０
の３００６、３００７であり、これは図３０に示される
ように、非交差区間テーブル２３０３中の２３２２から
ポイントされている。さらに、ステップ２８０４では、
文番号ｋに「１」を、lowにSelect(２)２４０３が指す
非交差区間テーブル２３０３の２３１９に格納された下
限値「１」を代入する。ステップ２８０５は、文番号ｋ
が「１」、nstmtが「２」なので判定結果はＹＥＳとな
る。ステップ２８０６は、今の場合、プロセス範囲が１
〜２で第１の文を考えているのだから、test_low, test
_uppは、それぞれ、図１８の１８１３、１８１４より
「１」、「１２８」となる。ｋは「１」、lowは「１」
なので、"low≧test_low、かつ、low≦test_upp"が成立
し、order(1)には「２」が代入される。これを表わした
のが、図３０の３００６である。ステップ２８０７によ
り、ｋの値を「２」に更新してステップ２８０５に戻
る。

【０１１５】ステップ２８０５は、文番号ｋが「２」、
nstmtが「２」なので判定結果はＹＥＳとなる。ステッ
プ２８０６は、今、プロセス範囲が１〜２で第２の文を
考えているのだから、test_low, test_uppは、それぞ
れ、図１９の１９１３、１９１４より「０」、「１２
８」となる。ｋは「２」、lowは「１」なので、"low≧t
est_low、かつ、low≦test_upp"が成立し、order(2)に
は「２」が代入される。これを表わしたのが、図３０の
３００７である。ステップ２８０７により、ｋの値を
「３」に更新してステップ２８０５に戻る。ステップ２
８０５は、文番号ｋが「３」、nstmtが「２」なので判
定結果はＮＯとなる。ステップ２８０８により、ｊの値
を「３」に更新してステップ２８０３に戻る。

【０１１６】ステップ２８０３において、ｊは「３」、
lary2は「３」なので、判定結果はＹＥＳとなる。ステ
ップ２８０４では、要素数２の配列orderを確保して、
これをSelect(３)２４０４が指す非交差区間テーブル２
３０４に接続する。配列orderを表わしたのが、図３０
の３００８、３００９であり、これは図３０に示される
ように、非交差区間テーブル２３０４中の２３２６から
ポイントされている。さらに、ステップ２８０４では、
文番号ｋに「１」を、lowにSelect(1)２４０４が指す非
交差区間テーブル２３０４の２３２３に格納された下限
値「１２８」を代入する。ステップ２８０５は、文番号
ｋが「１」、nstmtが「２」なので判定結果はＹＥＳと
なる。ステップ２８０６は、今、プロセス範囲が１〜２
で第１の文を考えているのだから、test_low, test_upp
は、それぞれ、図１８の１８０９、１８１０より
「１」、「１２８」となる。ｋは「１」、lowは「１２
８」なので、"low≧test_low、かつ、low≦test_upp"が
成立し、order(1)には「２」が代入される。これを表わ
したのが、図３０の３００８である。ステップ２８０７
により、ｋの値を「２」に更新してステップ２８０５に
戻る。

【０１１７】ステップ２８０５は、文番号ｋが「２」、
nstmtが「２」なので判定結果はＹＥＳとなる。ステッ
プ２８０６は、今、プロセス範囲が１〜２で第２の文を
考えているのだから、test_low, test_uppは、それぞ
れ、図１９の１９０９、１９１０より「０」、「１２
７」となる。ｋは「２」、lowは「１２８」なので、"lo
w＞test_upp"が成立し、order(2)には「３」が代入され
る。これを表わしたのが、図３０の３００９である。ス
テップ２８０７により、ｋの値を「３」に更新してステ
ップ２８０５に戻る。ステップ２８０５は、文番号ｋが
「３」、nstmtが「２」なので判定結果はＮＯとなる。
ステップ２８０８により、ｊの値を「４」に更新してス
テップ２８０３に戻る。ステップ２８０３において、ｊ
は「４」、lary2は「３」なので、判定結果はＮＯとな
る。ステップ２８０９で、次のプロセス範囲へ処理を移
しステップ２８０１に戻る

【０１１８】ステップ２８０１では、プロセス範囲３が
存在するので、判定結果はＹＥＳとなる。ステップ２８
０２において、ｊを「１」に初期化する。ステップ２８
０３におけるlary2は配列Selectの要素数に等しいの
で、図２５より「２」となる。従って、ステップ２８０
３の条件式は"1≦j≦2"となる。今の場合はｊは値が
「１」に初期化されているので、ステップ２８０３での
判定結果はＹＥＳとなる。ステップ２８０４では、要素
数２の配列orderを確保して、これをSelect(1)２４０５
が指す非交差区間テーブル２３０５に接続する。配列or
derを表わしたのが、図３０の３０１０、３０１１であ
り、これは図３０に示されるように、非交差区間テーブ
ル２３０５中の２３３０からポイントされている。さら
に、ステップ２８０４では、文番号ｋに「１」を、low
にSelect(1)２４０５が指す非交差区間テーブル２３０
５の２３２７に格納された下限値「０」を代入する。

【０１１９】ステップ２８０５は、文番号ｋが「１」、
nstmtが「２」なので判定結果はＹＥＳとなる。ステッ
プ２８０６は、今、プロセス範囲が３で第１の文を考え
ているのだから、test_low, test_uppは、それぞれ、図
１８の１８１３、１８１４より「１」、「１２８」とな
る。ｋは「１」、lowは「０」なので、"low＜test_low"
が成立し、order(1)には「１」が代入される。これを表
わしたのが、図３０の３０１０である。ステップ２８０
７により、ｋの値を「２」に更新してステップ２８０５
に戻る。

【０１２０】ステップ２８０５は、文番号ｋが「２」、
nstmtが「２」なので判定結果はＹＥＳとなる。ステッ
プ２８０６は、今、プロセス範囲が３で第２の文を考え
ているのだから、test_low, test_uppは、それぞれ、図
１９の１９１３、１９１４より「０」、「１２８」とな
る。ｋは「２」、lowは「０」なので、"low≧test_lo
w、かつ、low≦test_upp"が成立し、order(2)には
「２」が代入される。これを表わしたのが、図３０の３
０１１である。ステップ２８０７により、ｋの値を
「３」に更新しステップ２８０５に戻る。ステップ２８
０５は、文番号ｋが「３」、nstmtが「２」なので判定
結果はＮＯとなる。ステップ２８０８により、ｊの値を
「２」に更新してステップ２８０３に戻る。

【０１２１】ステップ２８０３において、ｊは「２」、
lary2は「２」なので、判定はＹＥＳとなる。ステップ
２８０４では、要素数２の配列orderを確保して、これ
をSelect(２)２４０６が指す非交差区間テーブル２３０
６に接続する。配列orderを表わしたのが、図３０の３
０１２、３０１３であり、これは図３０に示されるよう
に、非交差区間テーブル２３０６中の２３３４からポイ
ントされている。さらに、ステップ２８０４では、文番
号ｋに「１」を、lowにSelect(２)２４０６が指す非交
差区間テーブル２３０６の２３３１に格納された下限値
「１」を代入する。ステップ２８０５では、文番号ｋが
「１」、nstmtが「２」なので、判定はＹＥＳとなる。
ステップ２８０６は、今、プロセス範囲が３で第１の文
を考えているのだから、test_low, test_uppは、それぞ
れ、図１８の１８１３、１８１４より「１」、「１２
８」となる。ｋは「１」、lowは「１」なので、"low≧t
est_low、かつ、low≦test_upp"が成立し、order(1)に
は「２」が代入される。これを表わしたのが、図３０の
３０１２である。ステップ２８０７により、ｋの値を
「２」に更新してステップ２８０５に戻る。

【０１２２】ステップ２８０５は、文番号ｋが「２」、
nstmtが「２」なので判定結果はＹＥＳとなる。ステッ
プ２８０６は、今の場合、プロセス範囲が３で第２の文
を考えているのだから、test_low, test_uppは、それぞ
れ、図１９の１９１３、１９１４より「０」、「１２
８」となる。ｋは「２」、lowは「１」なので、"low≧t
est_low、かつ、low≦test_upp"が成立し、order(2)に
は「２」が代入される。これを表わしたのが、図３０の
３０１３である。ステップ２８０７により、ｋの値を
「３」に更新してステップ２８０５に戻る。ステップ２
８０５は、文番号ｋが「３」、nstmtが「２」なので判
定結果はＮＯとなる。ステップ２８０８により、ｊの値
を「３」に更新してステップ２８０３に戻る。ステップ
２８０３において、ｊは「３」、lary2は「２」なの
で、判定結果はＮＯとなる。ステップ２８０９で、次の
プロセス範囲へ処理を移し、ステップ２８０１に戻る。
ステップ２８０１は、プロセス範囲が存在しないので、
判定結果はＮＯとなる。以上で、順序表現作成ステップ
２７００の全ての処理を終了する。

【０１２３】次に、プロセス間共用ループ複製ステップ
２７０１の処理を図１７、図２９〜図３８を用いて説明
する。プロセス間共用ループ複製ステップ２７０１は、
図２８で説明した順序表現作成ステップ２７００におけ
る処理結果を用いて、各プロセス毎の非交差区間列から
どの区間を選択するか、またはそのプロセスからは選択
しないかを決定し、選択された一般に複数の区間の上下
限値をループの上下限値とするループを、元のループか
ら複製して生成するステップである。複数の区間に対し
て１つのループを生成するため、ループ直前にはプログ
ラムを実行するプロセス番号を判定する条件文と、各プ
ロセス毎に、そのプロセスの選択された区間の上下限値
をループの上下限値にする代入文が生成される。図２９
はプロセス間共用ループ複製ステップ２７０１の処理を
説明するための図である。図３１はループ実行テーブル
に対して、ステップ２９００を適用した結果を示す図で
ある。図３２はループ実行テーブルに対して、ステップ
２９０１を最初に適用した結果を示す図である。図３３
はループ実行テーブルに対して、ステップ２９０１を２
度目に適用した結果を示す図である。図３４はループ実
行テーブルに対して、ステップ２９０１を３度目に適用
した結果を示す図である。図３５はプロセス間共用ルー
プ複製ステップ２７０１の適用結果のＩＬをソースプロ
グラムスタイルで記述したものである。図３６は図３５
におけるLOWLIM1, UPPLIM1の値設定コード３５００であ
る。図３７は図３５におけるLOWLIM2, UPPLIM2の値設定
コード３５０３である。図３８は図３５におけるLOWLIM
3, UPPLIM3の値設定コード３５０７である。ここで、図
１７のsnum１７２０は選択候補の非交差区間を示すため
の配列Selectの添字である。sflag１７２１は選択候補
の非交差区間が実際に選択されるか否かを示すフラグで
ある。

【０１２４】ステップ２９００ではｊに「１」を代入
し、全プロセス範囲について、ループ実行テーブルのsn
umに「１」を、sflagに「OFF」を代入する。snumに
「１」を代入した結果は、図３１の３１００、３１０
２、３１０４に示されている。sflagに「OFF」を代入し
た結果は、図３１の３１０１、３１０３、３１０５に示
されている。プロセス範囲が０、プロセス範囲が１〜
２、プロセス範囲が３の時、lary2はそれぞれ、
「２」、「３」、「２」である。ステップ２９０１にお
いて、minvalにsnum≦lary2なる各プロセス範囲のSelec
t(snum)が指す非交差区間テーブルが指す配列orderの値
の、辞書式順序での最小値を代入するとともに、snum≦
lary2なる全プロセス範囲内について、minval＝（各プ
ロセス範囲の現在のorderの値）ならsflagを「ON」に
し、プログラム中でユニークな変数名low(j)、upp(j)を
作成する。今の場合、全プロセス範囲についてsnumが
「１」で、snum≦lary2を満たしているので、Select(1)
が指す非交差区間テーブルが指す配列orderの値の辞書
式順序での最小値を求めてminvalに代入する。図３０に
おいて、Select(1)が指す非交差区間テーブルが指す配
列orderの値は、プロセス範囲が０の時は３０００、３
００１より「２；２」、プロセス範囲が１〜２の時は３
００４、３００５より「１；２」、プロセス範囲が３の
時は３０１０、３０１１より「１；２」となるので、辞
書式順序での最小値は「１；２」となり、minvalには
「１；２」が代入される。次に上で求めたminvalと各プ
ロセス範囲の現在のorderの値が等しくなるのは、プロ
セス範囲が１〜２とプロセス範囲が３のときなので、両
者に対してsflagを「ON」にする。これを表わしたの
が、図３２の３１０３、３１０５である。

【０１２５】次のステップ２９０２は、プログラム中で
ユニークな変数名low(1)=LOWLIM1,upp(1)=UPPLIM1を作
成するステップである。このステップでは、全プロセス
範囲について、プロセス番号がプロセス範囲内にある条
件を表わす条件ＩＬを生成するとともに、次の２文のＩ
Ｌを生成し、プロセス番号がプロセス範囲内にあるとき
実行するよう、上記条件ＩＬに接続する。sflagが「O
N」のとき、low(j)＝非交差区間の下限値、upp(j)＝非
交差区間の上限値上記以外のとき、low(j)＝１、upp(j)＝０ステップ２９０２では、プロセス範囲が０、プロセス範
囲が１〜２、プロセス範囲が３の順に処理を行なう。

【０１２６】まず、プロセス範囲が０の時、プロセス番
号がプロセス範囲内にある条件を表わすＩＬを生成す
る。この結果は図３６の３６００に示されている。プロ
セス範囲が０の時、図３２の３１０１に示すように、sf
lagは「OFF」なので、low(j)＝１、upp(j)＝０であり、
上記LOWLIM1, UPPLIM1を使って、"LOWLIM1=1","UPPLIM1
=0"のＩＬを作成して、上記３６００に対応する条件Ｉ
Ｌに接続する。この結果を表わしたのが、図３６の３６
０１、３６０２である。次に、プロセス範囲が１〜２の
時、プロセス番号がプロセス範囲内にある条件を表わす
ＩＬを生成する。この結果は図３６の３６０３に示され
ている。プロセス範囲が１〜２の時、図３２の３１０３
に示すように、sflagは「ON」である。図３２の３１０
２よりsnumは「１」なので、図３０のSelect(1)が指す
非交差区間テーブル２３０２を参照する。これから、下
限値２３１５、上限値２３１６の値は「０」、「０」な
ので（low(j)＝０、upp(j)＝０）、上記LOWLIM1,UPPLIM
1を使って、"LOWLIM1=0", "UPPLIM1=0"のＩＬを作成し
て、上記３６０３に対応する条件ＩＬに接続する。この
結果を表わしたのが、図３６の３６０４、３６０５であ
る。

【０１２７】次に、プロセス範囲が３の時、プロセス番
号がプロセス範囲内にある条件を表わすＩＬを生成す
る。この結果は図３６の３６０６に示されている。プロ
セス範囲が３の時、図３２の３１０５に示すように、sf
lagは「ON」である。図３２の３１０４よりsnumは
「１」なので、図３０のSelect(1)が指す非交差区間テ
ーブル２３０５を参照する。これから、下限値２３２
７、上限値２３２８の値は「０」、「０」なので、上記
LOWLIM1, UPPLIM1を使って、"LOWLIM1=0","UPPLIM1=0"
のＩＬを作成して、上記３６０６に対応する条件ＩＬに
接続する。この結果を表わしたのが、図３６の３６０
７、３６０８である。

【０１２８】次のステップ２９０３において、条件ＩＬ
をループ直前で実行するよう、プログラムＩＬに接続ル
ープの複製を作成し、ループの下限値をlow(j)、上限値
をupp(j)とし、上記複製を条件ＩＬ直後で実行するよう
プログラムＩＬに接続する。今の場合、図３６で作成さ
れたＩＬを図３５の３５００として、図３５に接続し、
ループの複製を作成し、ループの下限値、上限値をLOWL
IM1, UPPLIM1とし、これを上記ＩＬ３５００直後に接続
する。これを表わしたのが、図３５のＤＯループ３５０
１である。

【０１２９】次のステップ２９０４において、どのプロ
セス範囲にも未選択の非交差区間がないか否かを判定す
る。判定の結果、ＹＥＳであればプロセス間共有ループ
複製ステップ２７０１の処理を全て終了する。ＮＯであ
ればステップ２９０５に進む。今の場合、プロセス範囲
０には未選択の非交差区間テーブルがまだあるので、判
定結果はＮＯであり、ステップ２９０５に進む。ステッ
プ２９０５において、ｊの値を１更新し、sflagが「O
N」ならsnumを１更新し、sflagを「OFF」に初期化して
ステップ２９０１に戻る。今の場合、ｊの値を１更新し
て「２」とするとともに、プロセス範囲が１〜２、およ
びプロセス範囲が３の場合にはsflagが「ON」であるか
ら（図３２参照）、snumの値を「１」だけ増加する。こ
れを表わしたのが、図３３の３１０２、３１０４であ
る。また、全てのsflagを「OFF」に初期化する。

【０１３０】プロセス範囲が０、プロセス範囲が１〜
２、プロセス範囲が３の時、lary2はそれぞれ、
「２」、「３」、「２」である。ステップ２９０１で
は、プロセス範囲が０の時はsnumが「１」で、プロセス
範囲が１〜２、およびプロセス範囲が３の時はsnumの値
が「２」なので、snum≦lary2を満たし、プロセス範囲
が０の時はSelect(1)が指す非交差区間テーブルが指す
配列orderの値、プロセス範囲が１〜２、およびプロセ
ス範囲が３の時はSelect(２)が指す非交差区間テーブル
が指す配列orderの値を見て、それぞれの値の辞書式順
序での最小値を求めて、minvalに代入する。図３０にお
いて、上記配列orderの値は、プロセス範囲が０の時は
３０００、３００１より「２；２」、プロセス範囲が１
〜２の時は３００６、３００７より「２；２」、プロセ
ス範囲が３の時は３０１２、３０１３より「２；２」と
なるので、辞書式順序での値は全て同じで、最小値は
「２；２」となり、minvalには「２；２」が代入され
る。次に、上で求めたminvalと各プロセス範囲の現在の
orderの値は全てのプロセス範囲で等しくなるので、全
プロセス範囲に対してsflagを「ON」にする。これを表
わしたのが、図３３の３１０１、３１０３、３１０５で
ある。

【０１３１】次に、プログラム中でユニークな変数名lo
w(2)=LOWLIM2, upp(2)=UPPLIM2を作成する。ステップ２
９０２では、プロセス範囲が０、プロセス範囲が１〜
２、プロセス範囲が３の順に処理を行なう。プロセス範
囲が０の時、プロセス番号がプロセス範囲内にある条件
を表わすＩＬを生成する。この結果は図３７の条件文３
７００に示されている。プロセス範囲が０の時、図３３
の３１０１に示すように、sflagは「ON」である。図３
３の３１００よりsnumは「１」なので、図３０のSelect
(1)が指す非交差区間テーブル２３００を参照する。こ
れから、下限値２３０７、上限値２３０８の値は
「１」、「１２７」なので、上記LOWLIM2, UPPLIM2を使
って、"LOWLIM2=1", "UPPLIM2=127"のＩＬを作成し
て、上記３７００に対応する条件ＩＬに接続する。この
結果を表わしたのが、図３７の文３７０１、３７０２で
ある。次に、プロセス範囲が１〜２の時、プロセス番号
がプロセス範囲内にある条件を表わすＩＬを生成する。
この結果は図３７の条件文３７０３に示されている。プ
ロセス範囲が１〜２の時、図３３の３１０３に示すよう
に、sflagは「ON」である。図３３の３１０２よりsnum
は「２」なので、図３０のSelect(２)が指す非交差区間
テーブル２３０３を参照する。これから、下限値２３１
９、上限値２３２０の値は「１」、「１２７」なので、
上記LOWLIM2, UPPLIM2を使って、"LOWLIM2=1", "UPPLI
M2=127"のＩＬを作成して、上記３７０３に対応する条
件ＩＬに接続する。この結果を表わしたのが、図３７の
文３７０４、３７０５である。

【０１３２】次に、プロセス範囲が３の時、プロセス番
号がプロセス範囲内にある条件を表わすＩＬを生成す
る。この結果は図３７の条件文３７０６に示されてい
る。プロセス範囲が３の時、図３３の３１０５に示すよ
うに、sflagは「ON」である。図３３の３１０４よりsnu
mは「２」なので、図３０のSelect(２)が指す非交差区
間テーブル２３０６を参照する。これから、下限値２３
３１、上限値２３３２の値は「１」、「１２８」なの
で、上記LOWLIM2, UPPLIM2を使って、"LOWLIM2=1", "U
PPLIM2=128"のＩＬを作成して、上記３７０６に対応す
る条件ＩＬに接続する。この結果を表わしたのが、図３
７の文３７０７、３７０８である。ステップ２９０３で
は図３７で作成されたＩＬを３５０３として、図３５に
接続し、ループの複製を作成し、ループの下限値、上限
値をLOWLIM2, UPPLIM2とし、これを上記ＩＬ３５０３直
後に接続する。これを表わしたのが、図３５のＤＯルー
プ３５０４である。ステップ２９０４は、プロセス範囲
０に未選択の非交差区間テーブルがあるので、判定はＮ
Ｏである。次のステップ２９０５で、ｊの値を「３」に
更新し、sflagが「ON」の場合、即ち、今の場合全プロ
セス範囲に対してsnumの値を１だけ増やす。これを表わ
したのが、図３４の３１００、３１０２、３１０４であ
る。また、全てのsflagを「OFF」に初期化する。プロセ
ス範囲が０、プロセス範囲が１〜２、プロセス範囲が３
の時、lary2はそれぞれ、「２」、「３」、「２」であ
る。その後ステップ２９０１に戻る。

【０１３３】次のステップ２９０１では、プロセス範囲
が０の時はsnumが「２」、プロセス範囲が１〜２、およ
びプロセス範囲が３の時はsnumの値が「３」なので、プ
ロセス範囲が０の時はSelect(２)が指す非交差区間テー
ブルが指す配列orderの値、プロセス範囲が１〜２の時
はSelect(３)が指す非交差区間テーブルが指す配列orde
rの値を見て、それぞれの値の辞書式順序での最小値を
求めて、minvalに代入する。プロセス範囲が３の時はsn
umの値がlary2より大きくなるので処理しない。図３０
において、プロセス範囲が０の時はSelect(２)が指す非
交差区間テーブルが指す配列orderの値は、３００２、
３００３より「２；３」、プロセス範囲が１〜２の時は
３００８、３００９より「２；３」、プロセス範囲が３
の時は処理しないので、辞書式順序での最小値は「２；
３」となり、minvalには「２；３」が代入される。次に
上で求めたminvalと各プロセス範囲の現在のorderの値
が等しくなるのは、プロセス範囲が０とプロセス範囲が
１〜２のときなので、両者に対してsflagを「ON」にす
る。これを表わしたのが、図３４の３１０１、３１０３
である。

【０１３４】次にプログラム中でユニークな変数名low
(3)=LOWLIM3, upp(3)=UPPLIM3を作成する。ステップ２
９０２では、プロセス範囲が０、プロセス範囲が１〜
２、プロセス範囲が３の順に処理を行なう。プロセス範
囲が０の時、プロセス番号がプロセス範囲内にある条件
を表わすＩＬを生成する。この結果は図３８の条件文３
８００に示されている。プロセス範囲が０の時、図３４
の３１０１に示すように、sflagは「ON」である。図３
４の３１００よりsnumは「２」なので、図３０のSelect
(２)が指す非交差区間テーブル２３０１を参照する。こ
れから、下限値２３１１、上限値２３１２の値は「１２
８、１２８」なので、上記LOWLIM3, UPPLIM3を使っ
て、"LOWLIM3=128", "UPPLIM3=128"のＩＬを作成し
て、上記３８００に対応する条件ＩＬに接続する。この
結果を表わしたのが、図３８の文３８０１、３８０２で
ある。

【０１３５】次に、プロセス範囲が１〜２の時、プロセ
ス番号がプロセス範囲内にある条件を表わすＩＬを生成
する。この結果は図３８の条件文３８０３に示されてい
る。プロセス範囲が１〜２の時、図３４の３１０３に示
すように、sflagは「ON」である。図３４の３１０２よ
りsnumは「３」なので、図３０のSelect(３)が指す非交
差区間テーブル２３０４を参照する。これから、下限値
２３２３、上限値２３２４の値は「１２８」、「１２
８」なので、上記LOWLIM3, UPPLIM3を使って、"LOWLIM3
=128", "UPPLIM3=128"のＩＬを作成して、上記３８０
３に対応する条件ＩＬに接続する。この結果を表わした
のが、図３８の文３８０４、３８０５である。次に、プ
ロセス範囲が３の時、プロセス番号がプロセス範囲内に
ある条件を表わすＩＬを生成する。この結果は図３８の
条件文３８０６に示されている。プロセス範囲が３の
時、図３４の３１０５に示すように、sflagは「OFF」で
ある。上記LOWLIM3, UPPLIM3を使って、"LOWLIM3=1","U
PPLIM3=0"のＩＬを作成して、上記３８０６に対応する
条件ＩＬに接続する。この結果を表わしたのが、図３８
の文３８０７、３８０８である。

【０１３６】ステップ２９０３では図３８で作成された
ＩＬを３５０７として、図３５に接続し、ループの複製
を作成し、ループの下限値、上限値をLOWLIM3, UPPLIM3
とし、これを上記ＩＬ３５０７直後に接続する。これを
表わしたのが、図３５のＤ０ループ３５０８である。次
のステップ２９０４において、今度は未選択の非交差区
間テーブルはないので、判定はＹＥＳであり処理を終了
する。以上でプロセス間共用ループ複製ステップ２７０
１の全ての処理を終了する。また、以上でループ複製部
１０８の処理も終了する。

【０１３７】次にコード変換部１０９の処理を図１５、
図１８、図１９と図３５〜図３８までを用いて説明す
る。図１５のステップ１５００において、ループ複製部
１０８で複製されたループが、図３５に示すように、３
５０１、３５０４、３５０８の３個あるので、判定はＹ
ＥＳである。以下、上記順序で各ループに対して処理を
行なう。ステップ１５０１において、各ループ内には、
ASGN１６０９から始まる文とASGN１６１５から始まる文
の２つの文があるので、判定はＹＥＳである。以下、上
記順序で各文に対して処理を行なう。さらに、第１の文
の処理には、ASGN１６０９および直前のSINFO１６０８
が指す文実行範囲テーブルを参照しながら処理を行な
う。同様に、第２の文の処理には、ASGN１６１５および
直前のSINFO１６１４が指す文実行範囲テーブルを参照
しながら処理を行なう。ループ３５０１のループ実行範
囲は、図３６に示すように、プロセス範囲が０、プロセ
ス範囲が１〜２、プロセス範囲が３の時、それぞれ、
「１〜０」、「０〜０」、「０〜０」である。一方、第
１の文の実行範囲は、図１８の１８０５と１８０６、１
８０９と１８１０、１８１３と１８１４に示すように、
全プロセス範囲に対して「１〜１２８」である。ここ
で、プロセス範囲が０の時のループ実行範囲である「１
〜０」に対しては、これ以降、包含関係を判定しないこ
とにする。よって、０以外のプロセス範囲に対して文の
実行範囲とループ実行範囲は互いに素（重なりがない）
となり、ステップ１５０２は第１の文に対する文ＩＬを
削除する。ステップ１５０４で次の文へ移る。

【０１３８】ステップ１５０１は、第２の文があるの
で、判定はＹＥＳである。第２の文の実行範囲は、図１
９の１９０５と１９０６、１９０９と１９１０、１９１
３と１９１４に示すように、プロセス範囲が０、プロセ
ス範囲が１〜２、プロセス範囲が３の時、それぞれ、
「１〜１２７」、「０〜１２７」、「０〜１２８」であ
る。範囲１〜０に対しては、包含関係を判定しないの
で、０以外のプロセス範囲に対して文の実行範囲はルー
プ実行範囲を包含する。従って、ステップ１５０２は、
第２の文に対する文ＩＬをそのままにする。この結果を
表わしたのが図３５の文３５０２である。ステップ１５
０４で次の文へ移る。

【０１３９】ステップ１５０１では、ループ３５０１に
対して２つの文の処理を終えたので、他に文は存在しな
い。よって、判定はＮＯとなり、ステップ１５０３へ移
る。ステップ１５０３では、ループ内に文は１つあるの
で、何も処理せず、次の複製ループへ移る。ステップ１
５００は、複製ループ３５０４が存在するので、判定は
ＹＥＳである。ステップ１５０１は、各ループ内には、
ASGN１６０９から始まる文とASGN１６１５から始まる文
の２つの文があるので、判定はＹＥＳである。以下、上
記順序で各文に対して処理を行なう。ループ３５０４の
ループ実行範囲は、図３７に示すように、プロセス範囲
が０、プロセス範囲が１〜２、プロセス範囲が３の時、
それぞれ、「１〜１２７」、「１〜１２７」、「１〜１
２８」である。一方、第１の文の実行範囲は１８０５と
１８０６、１８０９と１８１０、１８１３と１８１４に
示すように、全プロセス範囲に対して「１〜１２８」で
ある。よって、全プロセス範囲に対して文の実行範囲ル
ープ実行範囲を包含する。従って、ステップ１５０２
は、文ＩＬをそのままにする。この結果を表わしたのが
図３５の文３５０５である。ステップ１５０４で次の文
へ移る。

【０１４０】ステップ１５０１では第２の文があるの
で、判定はＹＥＳである。第２の文の実行範囲は、図１
９の１９０５と１９０６、１９０９と１９１０、１９１
３と１９１４に示すように、プロセス範囲が０、プロセ
ス範囲が１〜２、プロセス範囲が３の時、それぞれ、
「１〜１２７」、「０〜１２７」、「０〜１２８」であ
る。よって、全プロセス範囲に対して文の実行範囲ルー
プ実行範囲を包含する。従って、ステップ１５０２で
は、文ＩＬをそのままにする。この結果を表わしたのが
図３５の文３５０６である。ステップ１５０４で次の文
へ移る。ステップ１５０１では、ループ３５０４に対し
て２つの文の処理を終えたので、他に文は存在しない。
よって、判定はＮＯとなり、ステップ１５０３へ移る。
ステップ１５０３では、ループ内に文は２つあるので、
何も処理せず、次の複製ループへ移る。

【０１４１】ステップ１５００では、複製ループ３５０
８が存在するので、判定はＹＥＳである。ステップ１５
０１において、各ループ内には、ASGN１６０９から始ま
る文とASGN１６１５から始まる文の２つの文があるの
で、判定はＹＥＳである。以下、上記順序で各文に対し
て処理を行なう。ループ３５０８のループ実行範囲は、
図３８に示すように、プロセス範囲が０、プロセス範囲
が１〜２、プロセス範囲が３の時、それぞれ、「１２８
〜１２８」、「１２８〜１２８」、「１〜０」である。
一方、第１の文の実行範囲は、図１８の１８０５と１８
０６、１８０９と１８１０、１８１３と１８１４に示す
ように、全プロセス範囲に対して「１〜１２８」であ
る。よって、３以外のプロセス範囲に対して文の実行範
囲はループ実行範囲を包含する。従って、ステップ１５
０２は、文ＩＬをそのままにする。この結果を表わした
のが図３５の文３５０９である。ステップ１５０４で次
の文へ移る。

【０１４２】ステップ１５０１では、第２の文があるの
で、判定はＹＥＳである。第２の文の実行範囲は、図１
９の１９０５と１９０６、１９０９と１９１０、１９１
３と１９１４に示すように、プロセス範囲が０、プロセ
ス範囲が１〜２、プロセス範囲が３の時、それぞれ、
「１〜１２７」、「０〜１２７」、「０〜１２８」であ
る。よって、３以外のプロセス範囲に対して文の実行範
囲とループ実行範囲は互いに素（重なりがない）であ
る。従って、ステップ１５０２は、第２の文に対応する
文ＩＬを削除する。ステップ１５０４で次の文へ移る。

【０１４３】ステップ１５０１では、ループ３５０８に
対して２つの文の処理を終えたので、他に文は存在しな
い。よって、判定はＮＯとなり、ステップ１５０３へ移
る。ステップ１５０３では、ループ内に文が１つあるの
で、何も処理せず、次の複製ループへ移る。ステップ１
５００では、複製ループは他に存在しないので、判定は
ＮＯとなる。以上でコード変換部１０９の処理を終了す
る。以上の処理の結果、ソースコード生成部１１０を経
て出力されたデータ通信入りソースプログラム１１１は
図３５〜図３８に示したようになる。

【０１４４】上述した本発明のコンパイラによる計算分
割最適化制御方法は電子計算機を用いて実行されるもの
であることはいうまでもない。。また、このようにして
最適分割された計算は並列計算機システムで実行され
る。図３９は、本発明の並列化コンパイラが対象とする
並列計算機システムの一構成例を示したものである。同
図において、１はローカルメモリ、２はプロセッサエレ
メント、３はネットワーク、４は入出力用プロセッサエ
レメント、５は入出力用コンソールまたはワークステー
ションを示している。本発明の並列化コンパイラは、入
出力用コンソールまたはワークステーション５において
実行され、通信を含むソースプログラムまたはオブジェ
クトプログラムに変換される。前者のソースプログラム
は、さらに、各プロセッサエレメント２向けのコンパイ
ラによってオブジェクトプログラムに変換される。上記
オブジェクトプログラムはリンカーによりロードモジュ
ールに変換され、入出力用プロセッサエレメント４を通
じて各プロセッサエレメント２のローカルメモリ１に配
置され、各プロセッサエレメント２により実行され、ネ
ットワーク３を通じて通信を行なう。本発明の並列化コ
ンパイラによる計算分割最適化方法を用いると、上記の
如き並列計算機システムによる処理を高速化し、ハード
ウエアを有効に利用することが可能になる。

【０１４５】

【発明の効果】本発明によれば、各ループ内には条件文
がないので、ループ内に条件文のある第１の従来技術に
比べて、実行時間が短い、という効果がある。実際、図
２に対する本発明の変換結果である図３５から図３８ま
でのプログラムと、図２に対する第１の従来技術の変換
結果である図３と図４のプログラムを、nCUBE2という分
散記憶型並列機４台で実行したときの実行時間の比は、
５３対１００となった。また、本発明によれば、ループ
分割を行なわないので、ループ分割を行なう第２の従来
技術に比べて、ループの終了判定が少なくなるので実行
時間が短い、という効果がある。実際、図２に対する本
発明の変換結果である図３５から図３８までのプログラ
ムと、図２に対する第２の従来技術の変換結果である図
６から図８までのプログラムを、nCUBE2という分散記憶
型並列機４台で実行したときの実行時間の比は、５３対
６８となった。また、本発明によれば、ループ分割を行
なわないので、ループ分割が可能な場合しか適用できな
かった第２の従来技術に比べて、適用範囲はより広い、
という効果がある。また、本発明によれば、変換プログ
ラム中に新たに生成されるループの数を減らすことがで
きるので、変換プログラムサイズがそれほど大きくなら
ないようにできる、という効果がある。また、本発明に
よれば、実行回数が比較的少ないループに対しては、各
文毎に条件文を生成し、実行回数が多いループに対して
は、ループ内に条件文がない変換プログラムを生成でき
るので、実行性能と変換プログラムサイズの両方を考慮
した変換ができる、という効果がある。また、本発明に
よれば、変換プログラムを生成する際、実行しないコー
ドを削除することができるので、変換プログラムサイズ
を小さくし、かつ、ユーザが読みやすいプログラムを生
成できるという効果がある。

【図面の簡単な説明】

【図１】本発明による並列化コンパイラの構成図であ
る。

【図２】データ分割指示付きソースプログラム１０１の
具体例である。

【図３】図２のデータ分割指示付きソースプログラムを
図１の並列化コンパイラ１００中の構文解析部１０２か
ら通信生成部１０５までと、ソースコード生成部１１０
を用いて変換した結果の、データ通信入りソースプログ
ラムである。

【図４】図３におけるLOWLIM1,UPPLIM1,LOWLIM2,UPPLIM
2,LOWLIM3,UPPLIM3の値設定コードである。

【図５】図２のプログラムをループ分割した結果であ
る。

【図６】図５のプログラムを図１の並列化コンパイラ１
００中の構文解析部１０２から通信生成部１０５まで
と、ソースコード生成部１１０を用いて変換した結果
の、データ通信入りソースプログラムである。

【図７】図６におけるLOWLIM1,UPPLIM1の値設定コード
である。

【図８】図６におけるLOWLIM2,UPPLIM2の値設定コード
である。

【図９】非交差区間列生成部１０７の処理の説明図であ
る。

【図１０】構造体ARYを説明した図である。

【図１１】非交差基本区間列生成ステップ９０２を説明
した図である。

【図１２】非交差区間列選択ステップ９０３を説明した
図である。

【図１３】区間選択ステップ１２０１を説明した図であ
る。

【図１４】ループ複製部１０８を説明した図である。

【図１５】コード変換部１０９の処理の処理を説明した
図である。

【図１６】中間語を説明するための図である。

【図１７】中間語から指される文実行範囲テーブル、ル
ープテーブルを説明するための図である。

【図１８】SINFO１６０８が指す文実行範囲テーブルを
表わしたものである。

【図１９】SINFO１６１４が指す文実行範囲テーブルを
表わしたものである。

【図２０】LINFO１６０１が指すループテーブルとルー
プ実行範囲テーブルを表わしたものである。

【図２１】ステップ１１００の処理の結果、値を格納さ
れた構造体の配列ARYを表わしたものである。

【図２２】処理の結果の、構造体の配列ARYを表わした
ものである。

【図２３】ステップ１１０３、１１０４の結果の、非交
差区間テーブルNIIAを表わしたものである。

【図２４】区間選択ステップ１２０１の処理後の配列Se
lectと非交差区間テーブルを示したものである。

【図２５】非交差区間列生成部１０７の処理後の、非交
差区間テーブルである。

【図２６】ループ複製部１０８、およびコード変換部１
０９の処理結果を中間語の代わりに、ソースプログラム
スタイルで表わしたものである。

【図２７】ループ複製部１０８の処理を説明した図であ
る。

【図２８】順序表現作成ステップ２７００を説明した図
である。

【図２９】プロセス間共用ループ複製ステップ２７０１
の処理を説明した図である。

【図３０】順序表現作成ステップ２７００の結果得られ
る、ループ実行範囲テーブル、およびそれからポイント
されるテーブルの様子を表わしたものである。

【図３１】ループ実行テーブルに対して、ステップ２９
００を適用した結果を示したものである。

【図３２】ループ実行テーブルに対して、ステップ２９
０１を最初に適用した結果を示したものである。

【図３３】ループ実行テーブルに対して、ステップ２９
０１を２度目に適用した結果を示したものである。

【図３４】ループ実行テーブルに対して、ステップ２９
０１を３度目に適用した結果を示したものである。

【図３５】プロセス間共用ループ複製ステップ２７０１
の適用結果のＩＬをソースプログラムスタイルで記述し
たものである。

【図３６】図３５におけるLOWLIM1, UPPLIM1の値設定コ
ードを示したものである。

【図３７】図３５におけるLOWLIM2, UPPLIM2の値設定コ
ードを示したものである。

【図３８】図３５におけるLOWLIM3, UPPLIM3の値設定コ
ードを示したものである。

【図３９】本発明のコンパイラが対象とする並列計算機
のシステム構成例である。

【図４０】従来技術による並列化コンパイラの構成図で
ある。

【符号の説明】

１００：並列化コンパイラ１０１：データ分割指示付きソースプログラム１０２：構文解析部１０３：データ分割解析部１０４：計算分割部１０５：通信生成部１０６：計算分割最適化部１０７：非交差区間列生成部１０８：ループ複製部１０９：コード変換部１１０：ソースコード生成部１１１：データ通信入りソースプログラム１１２：辞書１１３：中間語

Claims

【特許請求の範囲】

【請求項１】電子計算機を用いてデータ分割指示付き
プログラムを複数のプロセス上で動作する並列プログラ
ムに変換する方法であって、前記データ分割指示付きプログラムを解析して配列要素
とそれを割り付けるプロセスとの関係を決定するステッ
プと、各プロセスについて、配列と文を関係づける規則および
配列添字とループ制御変数の間の関係に基づいてループ
中の文を自プロセスで実行するためのループ制御変数の
値の範囲である文の実行範囲をループ中の各文について
決定するステップと、各プロセスについて、互いに重なりのない複数の区間か
らなり、それらの和集合が上記各文の実行範囲の和集合
を包含するような非交差区間列を生成する非交差区間列
生成処理を行なうステップと、上記非交差区間列の個々の区間をループ実行範囲とし、
ループ内の文は元のループと同一のループを複製するル
ープ複製処理を行なうステップと、上記ループ実行範囲と上記各文の実行範囲を用いて上記
複製したループ内の各文に対するコードを変換するコー
ド変換処理を行なうステップと、を有することを特徴と
する計算分割最適化方法。
【請求項２】上記非交差区間列生成処理を行うステッ
プは、上記互いに重なりのない各区間内において各文は
実行されるか否かのいずれかに決まるような非交差区間
列を生成するものであることを特徴とする請求項１記載
の計算分割最適化方法。
【請求項３】上記非交差区間列生成処理を行うステッ
プは、与えられた非交差区間列に対し、上記非交差区間
列の内、指定された区間選択方法で選択したいくつかの
区間の集合を第１の非交差区間列とし、選択しなかった
区間の内、隣接する区間を融合して一つの区間として得
られる区間の集合を第２の非交差区間列とし、上記第１
の非交差区間列と上記第２の非交差区間列の和集合を新
しい非交差区間列とすることを特徴とする請求項１記載
の計算分割最適化方法。
【請求項４】上記区間選択方法は、区間の長さが長い
順に並べ、先頭から指定個数までの区間を選択するよう
にしたことを特徴とする請求項３記載の計算分割最適化
方法。
【請求項５】上記区間選択方法は、区間の長さが長い
順に並べ、先頭から各区間の長さの和を求め、該長さの
和が指定の値に達するまでの区間を選択するようにした
ことを特徴とする請求項３記載の計算分割最適化方法。
【請求項６】上記ループ複製処理を行うステップは、
各プロセスについて、当該プロセスか否かを判定する条
件文を生成し、上記条件文の条件が成立したとき、上記
プロセスの非交差区間列を用いてループを複製するもの
であることを特徴とする請求項１記載の計算分割最適化
方法。
【請求項７】上記ループ複製処理を行うステップは、
非交差区間の選択順序を全プロセスにまたがって決定す
るために順序表現の作成を行ない、上記順序表現に基づ
いて、全プロセスから、選択するプロセスと非交差区間
を決定する非交差区間選択処理を行ない、上記非交差区
間を選択したプロセスに対しては、選択された非交差区
間をループ実行範囲とする上記プロセスに共通な単一の
ループを生成するループ複製処理を行ない、上記非交差
区間を選択しなかったプロセスに対しては、ループを実
行しないようなコードを生成し、上記ステップをどのプ
ロセスにも選択されない非交差区間がなくなるまで続け
るものであることを特徴とする請求項１記載の計算分割
最適化方法。
【請求項８】上記順序表現の作成は、与えられた数と
与えられた区間に対し、上記数が上記区間の下限値より
小さいときに１、上記区間に含まれるときに２、上記区
間の上限値より大きいときに３を、上記数に対応させる
ことを数の区間に対する順序表現といい、与えられた数と与えられた順序付けられた複数の区間に
対し、上記数の区間に対する順序表現を与えられた順序
付けに従って並べてできる数列を、数の順序付き区間に
対する順序表現といい、与えられた数列と与えられた順序付き区間に対し、上記
数列中の各数の上記順序付き区間に対する順序表現を上
記数列の値の小さい順に並べてできる数列を数列の順序
付き区間に対する順序表現というとき、各プロセスについて、与えられたループ内の各文に対す
る実行範囲と与えられた非交差区間列に対し、上記非交
差区間列の下限値からなる数列を生成し、上記実行範囲
に指定された順序付けを与え、上記生成された数列の順
序付き区間に対する順序表現を求めるものであること特
徴とする請求項７記載の計算分割最適化方法。
【請求項９】上記非交差区間選択処理は、各プロセス
について、上記求められた順序表現のまだ選択されてな
い数列の内、最小の値を選択し、上記選択された値の
内、全プロセスで最小の数に対応する非交差区間とその
プロセスを選択するものであることを特徴とする請求項
７記載の計算分割最適化方法。
【請求項１０】上記コード変換処理は、ループ内文の
実行範囲がループ実行範囲を包含するとき当該ループ中
の当該文を実行時判定なしで実行するコードに変換する
実行時判定削除処理と、ループ内文の実行範囲とループ
実行範囲が互いに重なりがないとき当該ループ中の当該
文を削除する文削除処理とのうち少なくともいずれか一
方を行ない、上記以外の場合は当該ループ中の当該文を
ループ制御変数が当該文の実行範囲に含まれる時のみ実
行するコードに変換するものであることを特徴とする請
求項１記載の計算分割最適化方法。
【請求項１１】上記コード変換処理は、各プロセスに
ついて、もしループ中の全ての文が上記文削除処理によ
り削除される場合当該ループを実行しないコードに変換
するものであることを特徴とする請求項１０記載の計算
分割最適化方法。