JPH06266683A

JPH06266683A - 並列処理装置

Info

Publication number: JPH06266683A
Application number: JP5052744A
Authority: JP
Inventors: Setsu Suzuoka; 節鈴岡
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1993-03-12
Filing date: 1993-03-12
Publication date: 1994-09-22
Also published as: US6092097A

Abstract

(57)【要約】【目的】本発明は、データのプリフェッチを容易にす
るサポート機能を有し、また実行のために発生する制御
コードを実行するためのオーバーヘッドを取り除くコン
パイル方式を採用した並列処理装置を提供することを目
的とする。【構成】複数台の処理装置と分散共有メモリとそれら
の間の情報転送路を持つ並列処理装置において、第１の
処理装置は第２の処理装置からの要求を受けることなく
第２の処理装置がどの自保有データを必要としているか
を認識するためにデータの依存関係を解析する解析手段
を有し、第２の処理装置は他の処理装置からデータを転
送してもらうための領域として分散共有メモリ上にデー
タ領域を有し、かつ同じシンボルデータに対して多重化
されたデータ領域を用意し、第１の処理装置は他の処理
装置のデータ領域に順番に巡回的にデータを書き込む書
き込み手段とを備えて構成される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列処理装置における
不定回ループの高速処理及び効率のよいプログラム実行
をするためのコンパイル方式に関する。

【０００２】

【従来の技術】まず、プリフェッチに関する基本的な技
術について述べた後に、二重バッファ系の技術について
説明し、最後に非同期転送法について言及する。

【０００３】J.L.Hennesy D.A.Patterson,「コンピュー
タ・アーキテクチャ」日経BP社（1992）,pp.456-458 に
記載されているように、「通常の命令の逐次実行を高速
化するために、多くのマシンで命令のプリフェッチ・バ
ッファ（instruction-prefetch buffer,以下では単に命
令バッファと記す）を使用している。一般的な命令バッ
ファは、２〜８個の連続した命令を保持するように作ら
れる。命令が１つずつＣＰＵで実行される度に、後続の
命令語がプリフェッチされる」。このように近い将来に
実行される可能性が高い命令を、先行する命令の実行と
並行してあらかじめロードしておくことにより命令のロ
ードのための時間を隠蔽するという技法は通常用いられ
ている。

【０００４】このプリフェッチの対象を命令からデータ
に拡張するということも行なわれている。この場合、近
い将来使われる可能性が高いデータを、それを実際に必
要とする以前にＣＰＵで他のデータ処理をしている間
に、キャッシュメモリにロードする。但し、プリフェッ
チとしてロードしてから実際にアクセスするまでに、そ
のデータに対して書き込みが起こった場合にはそのプリ
フェッチによってロードされたデータを無効化する。一
般にデータの場合は命令の場合よりも近い将来に必要と
なるデータの予測が困難である。そこで、無駄になる可
能性はあるとしても使う可能性が高いデータをあらかじ
めロードしておくという研究がなされている（A.Rogers
and k.li,"Software Support for Speculative Load
s",SIGPLAN NOTICES,Vol.27,No.9,Sept,1992).以上は逐
次型計算機の場合の技術である。ＭＩＮＤ型の並列計算
機の場合には命令のプリフェッチを逐次型計算機と同様
に行なうことができる。しかし、ＭＩＭＤ型計算機での
データのプリフェッチは逐次型の場合の技術をそのまま
用いることはできない。なぜならば、並列計算機の場合
には複数の処理装置が並列にデータを変更するので、デ
ータがいつ有効になり、いつアクセスしても良いのかを
知る必要があるからである。Rettberg等は並列計算機に
おいてもデータのプリフェッチを行ないたいと言ってい
るが具体的方策は示されていない（R.D.Rettberg,W.R.C
rowther,P.P.Carvey,and R.S.Tomlison,"The Monarch P
arallel Processor Hardware Design",IEEE Computer,V
ol.No.4,pp.18-30,1990). なお、彼らのプロジェクトは
打ち切りになったので、彼らの並列計算機におけるデー
タのプリフェッチの研究も未完のまま中止になった。

【０００５】ＭＩＭＤ型並列計算機でプリフェッチを行
なう場合、命令は書き換え不能でかつ通常自ローカルメ
モリに持っているのでプリフェッチに要するプロトコル
も時間もあまり問題とならない。しかし、データの場合
には、値は変わるものであり、さらに他の処理装置に格
納されていることもあり、そのような場合にはプリフェ
ッチのためのプロトコルは複雑になり、所要時間もしば
しば非常に大きくなる。また投機的（speculative の訳
語：必ずしも使われないが使われる可能性が高いと思わ
れるるデータはプリフェッチしておくという戦略）なプ
リフェッチを行なうと処理装置間の情報転送時の負荷を
高め、プリフェッチの効果を相殺することすらあり得
る。

【０００６】入出力ドライバのような特殊な部分に限れ
ば、二重バッファ系（dual buffersystem) がある(A.N.
Habermann,"オペレーティングシステムの基礎",p.40,
倍風館,1978)。この技法では、一つの入出力デバイスに
対して二つのバッファを用意しておく。ある入力装置か
らデータをＣＰＵに読みとるには、入力装置がバッファ
１にデータの書き込みを行なっている間にＣＰＵはもう
一つのバッファ２からデータを読み込み、次に二つのバ
ッファを切替え、入力装置がバッファ２にデータの書き
込みを行なっている間にＣＰＵはもう一つのバッファ１
からデータを読み込む（図１２参照）。このようにし
て、バッファのアクセスに対してＣＰＵと入力装置とが
競合を起こさないようにして、効率的にデータを入力す
る。この技法はデバイスドライバのような特殊なプログ
ラミングにおいては行なわれているが、一般のユーザア
プリケーションプログラムにおいては行なわれていな
い。なぜならばそのような高度な変換を行なったりコー
ドを生成するコンパイラがないからである。

【０００７】並列計算機の非同期通信については、バッ
ファがfullであるかempty であるかを一つのフラグを用
いて実現する方法が知られている（星野,"ＰＡＸコンピ
ュータ",オーム社,pp.81-82,1985) 。この場合データを
書く場合にはこのフラグがempty になるまでポーリング
しながら待ち、データを読むにはこのフラグがfullにな
るポーリングしてまで待つ（図１３参照）。ＰＡＸのよ
うに隣合った処理装置間の共有メモリにフラグを置くな
らば、フラグにアクセスする時間コストはあまりかから
ない。しかし一般の並列計算機では処理装置間はネット
ワークで結合されており、一つのフラグにアクセスする
ためにはネットワークを介してアクセスしなければなら
ず、フラグにアクセスする時間コストはかかる上に、ポ
ーリングをするとその間中ネットワークを使用している
ので、ネットワークの負荷を高め、他の処理装置による
ネットワークの利用を妨げることがある。

【０００８】通常のコンパイラにおいても定数ばかりの
計算は実行時ではなく、コンパイル時に行なうことは行
なわれている。例えば、ｘ＝１＋２という文はコンパイラによってｘ＝３という文に変換されてから、さらに実行コードに変換さ
れる。

【０００９】これをもっと積極的に行なう技法として部
分計算法がある。ここではプログラムの入力の一部がわ
かっていると、そのプログラムをわかっている範囲で部
分計算して、残った入力のみを変数とすることにより、
効率の良いプログラムに変換する（古川、藤田、" 部分
計算について",ＩＣＯＴジャーナル,No.23,1990 年,7
月）。

【００１０】例えば、図４１（ａ）のプログラムがあっ
た場合に、ｘの値は１０であることがわかっているの
で、図４１（ｂ）のように変換するというものである。

【００１１】また、Uwe Meyer,"Techniques for Partia
l Evaluation of Imperative Language",SIGPLAN NOTIC
ES,Vol.26,No.9 Sept,1991,pp.94-105にはＰＡＳＧＡＬ
に準拠した言語で記述された例が挙がっている。この例
は図４２（ａ）にあるようにＮとＸとを読み込み、Ｘの
Ｎ乗を計算し、その結果をＹに代入した後に所定の位置
に書き込むものである。ここでφ−シンボル（この例で
はＸ）は未知数であるとする。ここで入力Ｎが３である
とわかっているとすると、図４２（ａ）のプログラムは
図４２（ｂ）の実行効率の良いプログラムになる。

【００１２】このように実行前になんらかの手段により
変数の値がわかっている場合には部分計算により効率の
良いコードを出力することができる。しかし、実行時に
しか予測できないような変数に対しては対応できない。

【００１３】これに対して実行時にしか変数の値が全く
わからないような場合に対しても、コンパイル時に実行
を一部行なうことにより、変数を定数化して部分実行を
行なうという方法がある。（特開平４−４４１８１号公
報、「並列変換処理方法」）。この方法では以下の方法
により実行コードを生成し、これを実行コードとし、後
に計算機にロードして実行する。

【００１４】１．プログラム中でコンパイル中にあらか
じめ実行するプレ実行部分を定める。ここで定められた
変数は以降で再定義されてはならないことを確証する
（但し、プレ実行範囲の決め方については明細書の中に
記述されていない）。

【００１５】２．コンパイル中にコンパイラもしくはイ
ンタプリタによってプレ実行部分を実行し、変数を定数
化する。

【００１６】３．上記で定数化された情報に基づいて部
分計算を行ない、より効率が高い実行コードを生成す
る。

【００１７】この例として図４３（ａ）のプログラムに
対して、図４３（ｂ）のようにプレ実行部を定め（PREE
XEC START からPREEXEC END までの範囲）、コンパイル
時にデータファイルを得てプレ実行部を実行し、入力Ｍ
１，Ｍ２の値を定数化する。これによりこれに続くＤＯ
ループにおけるループの反復回数が定数化し、実行コー
ドの最適化が容易になる。

【００１８】ここで図４３（ａ）のソースプログラムか
ら４台の処理装置で動作するような実行コードを生成す
ることを考える。配列Ａは循環的（cyclic) に４分割
し、名前をＰＡとする。即ち配列Ａ(i) は処理装置ＭＯ
Ｄ(i-1,4)+1 番のＰＡ(i/4) に対応する。もしこれを通
常の方法でコンパイルするならば、図４４（ａ）のよう
な複雑なコードを生成しなければならない。まず、自分
の処理装置番号MYPEを関数MYPENUM() によって取り出
す。次に端数に注意してＤＯループの始点Ｎ１と終点Ｎ
２とを求める。

【００１９】もしこの図４３（ｂ）のプレ実行により、
Ｍ１＝１，Ｍ２＝１６とわかったとすると、図４３
（ａ）のプログラムは図４４（ｂ）の効率良いプログラ
ムに変換される。

【００２０】この方法で最も困難である点は二つある。

【００２１】・プレ実行の範囲を決めるのが困難であ
る。

【００２２】図４３，４４の例の場合にはＭ１，Ｍ２は
一回のデータ読み出しによって値が決定したので、プレ
実行の範囲が容易に定まった。しかし、一般にはプレ実
行範囲を決定するのは本質的に容易ではない。一般にこ
の範囲を決定するのが困難である理由は、変数の値が決
まるのが一回のデータ読み出しではなく、様々な値の参
照代入によるからである。ある値を知るには、その値を
定義する式の中で参照されている値を知る必要がある。
この連鎖によりプレ実行範囲は、実際に実行しているの
と変わらないぐらいに広くなる可能性がある。

【００２３】・プレ実行の範囲が広がると中間結果の量
が膨大になる。

【００２４】上記の理由によりプレ実行範囲が広がる
と、プレ実行範囲で求まった全ての変数を実行コード中
に埋め込む必要がある。プレ実行をしないならば初期値
未定領域として領域だけ実行時に確保すればよく、オブ
ジェクトを大きくしなかった変数についても、プレ実行
により値が求まると値を確定値としてオブジェクトに含
ませる必要がある。単純なアルゴリズムにより大きな定
数テーブルを作る場合には、これはオブジェクトを大き
くすることになる。

【００２５】ここで並列計算機におけるプログラムの実
行について考えてみる。図４５のようにホスト計算機に
接続された並列計算機において、Single Program Multi
pleStream(SPMD)型プログラムを実行する場合を考察す
る。従来はプログラムの実行として以下の方法が採られ
ている。

【００２６】１．ホスト計算機２１３においてソースプ
ログラム２１５をホスト計算機２１３内のコンパイラ２
１３ａを用いて並列計算機の個々の処理装置で実行可能
なノードプログラムに変換する。

【００２７】２．ホスト計算機２１３においてホスト計
算機２１３内のコンパイラ２１３ａを用いてノードプロ
グラムをコンパイルして、実行コード２１７を作成す
る。

【００２８】３．上で作成された実行コード２１７をホ
スト−処理装置間ネットワーク２１９を介して並列処理
装置にロード（放送）し、各処理装置のメモリ領域２２
１に格納する。

【００２９】４．個々の処理装置上でロードされた実行
コード２２１を実行する。

【００３０】例えば、文献(Seema Hiranandani, Ken Ke
nnedy Chau-Wen Tseng,"CompilingFortran D for MIMID
distributed-memory machines",CACM,Aug,1992,Vol.3
5,No.8,pp.66-80)には、Fortran D で記述されたJacobi
法のプログラムをノードプログラムに変換して実行する
例が乗っている。まず元のFortran D で記述された一般
的なJacobi法のプログラムを図４６に示す。この図４６
のプログラムでは１００×１００の二次元配列Ａの各要
素において、上下左右の要素の平均を代入することをti
me回反復するものである。ここで配列Ｂは配列Ａのバッ
クアップとして用いられている。このプログラムを４台
の並列処理装置で実行することを考える。配列Ａの分割
の仕方としては次のようにする（^＊は任意を表す）。

【００３１】処理装置１：Ａ（＊，１）〜Ａ（＊，２５）処理装置２：Ａ（＊，２６）〜Ａ（＊，５０）処理装置３：Ａ（＊，５１）〜Ａ（＊，７５）処理装置４：Ａ（＊，７６）〜Ａ（＊，１００）但し、実際には境界部分の配列要素データの受け渡しの
ために、いわゆるのりしろとして配列の切断面において
は一つずつ大きめにデータ領域を確保する。このため
に、図４７のプログラムでは配列Ｂは、Ｂ（１００，２
５）ではなくＢ（１００，０：２６）となっている（配
列の大きさが整数一つの場合は下限が１である。即ち、
２５は添字が１〜２５を意味する。これに対して下限を
１以外にするにはコロンで区切って明示的に宣言する。
例えば、０：２６は添字の下限が０で上限が２６を意味
する）。Plocalは処理装置の番号で１〜４の値を取り、
Pleft とPrightは境界における配列の隣の要素を持つプ
ロセッサの番号（１〜４）を表す。Ib1 とub1 はそれぞ
れ処理装置内における配列の操作大正の下限を上限とを
表す。これらの値は処理装置の位置によって微妙に異な
る。また処理装置の位置によってデータの送受信のパタ
ーンが異なるので、if文でデータの送受信を場合分けす
る必要がある。このように元のプログラムにおいては存
在しなかった処理装置Plocalによる場合分けがノードプ
ログラムには存在する。このために実行のオーバーヘッ
ドが入り込む。

【００３２】並列計算機において、ホストでコンパイル
しただけで、実行時に獲得できた処理装置の台数が異な
っても効率良く実行できる方法というのも提案されてい
る（公開S62-274451「並列計算機」）。それはデータの
識別子を処理装置番号、処理装置内番号の連接と見なす
方法である（図４８）。この場合処理装置の台数が変わ
っても実行時にデータの識別子からそのデータの処理装
置番号と処理装置内番号とが取り出せるというものであ
る。しかし、この方法には二つの重大な問題がある。

【００３３】・特別なハードウェアの必要性データの識別子から処理装置番号と処理装置内番号とを
取り出すには、特別なハードウェアがないと実行速度は
大幅に悪化する。

【００３４】・処理装置の台数は２の乗数に限られること通常の２進計算機の場合、処理装置の台数が２の乗数で
ある場合には、処理装置番号と処理装置内番号とはフィ
ールドの連接で表現できるので、ビットマスクで必要な
フィールドを取り出すことができる。しかし、実行する
処理装置の台数が２の乗数以外の場合には、除算器が必
要となり実際的でない。

【００３５】処理装置の台数に２の乗数という制約がな
く、ソフトウェアだけで十分高速に処理可能な方法が望
まれる。

【００３６】

【発明が解決しようとする課題】このように従来の並列
計算機ではアプリケーションプログラムにおいてデータ
のプリフェッチを行なうコンパイラ技術やそのハードウ
ェアサポートがなかった。本発明は、並列計算機におい
てデータのプリフェッチを容易にするサポート装置を提
供することを目的とする。

【００３７】また、定数可能な変数を変数として実行す
る実行コードは実行効率が低い。これを改善するために
コンパイル時に静的にわかる情報から部分計算を行な
い、効率の高い実行コードを生成することが試みられて
いるものの、まだ十分とは言えない。特にプログラムを
並列実行する場合には、並列化のために制御コードを多
数挿入することになるが、これが大きなオーバーヘッド
となる。また、従来はコンパイル中に決定できる情報し
か取り込めないので、本質的に実行時に獲得できた処理
装置の台数や構成といった、実行時にしかわからない情
報を用いてコンパイルすることはできない。

【００３８】本発明は、並列計算機における実行のため
に発生する制御コードを実行するためのオーバーヘッド
を取り除くコンパイル方式を提供することを目的とす
る。

【００３９】

【課題を解決するための手段】上記目的を達成するため
本願第１の発明は、複数台の処理装置と分散共有メモリ
とそれらの間の情報転送路を持つ並列処理装置であっ
て、第１の処理装置は第２の処理装置からの要求を受け
ることなく第２の処理装置がどの自保有データを必要と
しているかを認識するためにデータの依存関係を解析す
る解析手段を有し、第２の処理装置は他の処理装置から
データを転送してもらうための領域として分散共有メモ
リ上にデータ領域を有し、かつ同じシンボルデータに対
して多重化されたデータ領域を用意し、第１の処理装置
は他の処理装置のデータ領域に順番に巡回的にデータを
書き込む書き込み手段を有することを要旨とする。

【００４０】また、本願第２の発明は、複数台の処理装
置と分散共有メモリとそれらの間の情報転送路を持つ並
列処理装置であって、第１の処理装置は第１のフラグを
備え、第２の処理装置は第２のフラグを備え、第１の処
理装置が第２の処理装置にデータを書き込むときには、
初期状態として第２の処理装置の第２のフラグを僞、第
１の処理装置の第１のフラグを真とし、第１の処理装置
は第１のフラグが真になった後に、第１のフラグを偽に
してから第２の処理装置にデータを書き、もしくは第２
の処理装置にデータを書いてから第１のフラグを偽に
し、さらに第２の処理装置の第２のフラグを真にし、ま
た第２の処理装置は第２のフラグが真になった後に、第
２のフラグを偽にしてからデータを読み、もしくはデー
タを読んでから第２のフラグを偽にし、さらに第１の処
理装置の第１のフラグを真にするプロトコルを有するこ
とを要旨とする。

【００４１】また、本願第３の発明は、複数の処理装置
からなる並列計算機であって、プログラムをコンパイル
するときに、実際に実行する処理装置に関しない部分に
ついては他のモジュールと結合可能なオブジェクトまで
コンパイルし、依存する部分については中間コードを生
成すると共に、該プログラムを実行する処理装置に当該
中間コードをロードし、それぞれの処理装置において、
実際に用いる処理装置に関する情報を用いて、中間コー
ドを最適コードにコンパイルすることをを要旨とする。

【００４２】さらに、本願第４の発明は、複数の処理装
置からなる並列計算機であって、ノードプログラムにお
いて並列化のために付加したコードについては中間コー
ドのまま各処理装置で保持し、その中間コードに出現す
る変数が前回同じコードで実行してから変更されたかを
知る手段として、それに係わる変数が変更されたことを
記すフラグを持つか、あるいはそれに係わる変数ごとに
変更時刻を記録するタイムスタンプを持ち、その中間コ
ード部を実行する直前にそのコードを実行するのが始め
てかどうかを知るフラグを持ち、その中間コードを実行
するのが始めてか、もしくは前回実行してからその中間
コードに係る部分の変数が変更されたときには、その中
間コードを変数を定数化してからコンパイルして実行
し、かつその実行コードを保持し、その中間コードを実
行するのが二度目以降であり、かつ前回実行してからそ
の中間コードに係る変数が変更されていないときには、
前回用いた実行コードを実行することを要旨とする。

【００４３】

【作用】本願第１の発明は、ソースプログラムからデー
タの依存性を解析することにより、データの送信側の処
理装置がどのデータをどの処理装置が必要とする可能性
が高いかを知ることができる。この情報を元に効率の高
い情報転送を行なうことが可能となる。即ち、データを
保持している処理装置がそのデータを読み込む必要があ
る処理装置にデータを転送する。従来のように、データ
を読み込む処理装置がそのデータを保持している処理装
置にデータを要求するとデータ要求を出す必要がある
が、本方式ではデータ要求を出す必要がない。

【００４４】但しこのように書き込みを基本とするデー
タを取り込む場所が問題となる。即ち、書き込む先の処
理装置で使用中のデータを書き換えてはならない。これ
を防ぐためにデータを書き込む先を多重に用意する。同
じシンボルデータ（例えばｘというデータ）に対しての
メモリ領域を複数用意し、それらをバージョンが変わる
（値が更新される）ごとに循環的に新しい位置にデータ
を書き込むようにする。このようにして読み手の処理装
置が使っていない場所に書き手は書き込むことにより、
安全なデータ転送を行なうことが可能となる。なお、あ
る一つのデータに対して値を変更する権利がある処理装
置は一台であるので、一つのデータに対して他の処理装
置に書き込みを行なうのも一台である。従って、その書
き込みを行なう処理装置が多重化した領域の次にどこに
書くべきかは一元管理できる。図１５ではｘというデー
タのための書き込み領域（ｘ0,ｘ1,ｘ2 ）が処理装置Ｒ
に三重に確保されており、処理装置Ｗは自分のみが値の
更新権を持つ変数ｘを循環的に領域（ｘ0,ｘ1,ｘ2 ）に
書き込む。このとき領域（ｘ0,ｘ1,ｘ2 ）のどこに書き
込むかを記憶するために、ｘのためのカウンタｉを持っ
ている。このカウンタは、ｎ重のデータ領域の場合に
は、０〜（ｎ−１）の値を循環的に取り、次に書き込む
べき場所ｘ_iを示す。データを書き込んだ後はカウタン
の値ｉを一つ増加させる。但し増加させた結果カウンタ
の値ｉがｎになった場合には、カウタンの値ｉを０とす
る。従ってｘのカウンタの値ｉはｘのバージョンの値を
ｎでモジュロを取った値を保持する。このデータｘを送
られるべき処理装置に依存せず、送信処理装置Ｗにのみ
依存する値である。従って処理装置Ｗでのみこのカウン
タを管理すれば良く、データｘを必要とする処理装置が
何台あろうともデータｘについてはカウンタは一つあれ
ば十分である。

【００４５】本願第２の発明は、分散共有メモリを有す
る並列計算機上で、処理装置Ｗが処理装置Ｒ上の分散共
有メモリにデータを書き込むことを考える。従来のよう
に一つのデータに対してフラグが一つであるとする。も
しそのフラグが処理装置Ｒの方にあるとすれば、処理装
置Ｒがデータに書き込まれていることを知るためには自
分の処理装置内にあるフラグにローカルにアクセスすれ
ば良いが、処理装置Ｗがデータを書き込んで良いかを知
るためには処理装置Ｒ上のフラグにリモートアクセスを
ポーリングによって繰り返さなければならない（図１６
参照）。これとは逆にそのフラグが処理装置Ｗの方にあ
るとすれば、処理装置Ｗがデータを書き込んで良いかを
知るためには自分の処理装置内にあるフラグにローカル
にアクセスすれば良いが、処理装置Ｒがデータに書き込
まれていることを知るためには処理装置Ｗ上のフラグに
対するリモートアクセスをポーリングによって繰り返さ
なければならない（図１７参照）。

【００４６】このリモートアクセスのポーリングという
オーバーヘッドを本方式ではフラグを処理装置ＲとＷと
に分けて分散配置することにより解決する。即ち、処理
装置Ｗはデータを書き込み許可を表すフラグＷを持ち、
処理装置Ｒはデータを読み込み許可を表すフラグＲを持
つ（図１８参照）。処理装置ＷはフラグＷが真になるま
でポーリングによって待つが、フラグＷは処理装置Ｗ内
のデータであるのでアクセスしてもネットワークに負荷
を与えない。このフラグＷは処理装置Ｒによって真にさ
れる。また、処理装置ＲはフラグＲが真になるまでポー
リングによって待つが、フラグＲは処理装置Ｒ内のデー
タであるのでアクセスしてもネットワークに負荷を与え
ない。このフラグＲは処理装置Ｗによって真にされる。
図１９に状態遷移グラフを示す。処理装置Ｗがデータを
処理装置Ｒに書き込む動作と処理装置ＷがフラグＷを偽
にする動作が逆点し、処理装置Ｒがデータを処理装置Ｗ
に書き込む動作と処理装置ＲがフラグＲを偽にする動作
が逆点していても同様の効果が得られる。これらの組み
合わせによりこの他に３種類の変形がある。その一つの
状態遷移グラフを図２０に示す。

【００４７】二重以上のループであり、かつ内側のルー
プがD0 ALL（もしくはFOR ALL)型のループ（ループの交
換によってこのような性質を持つものも含む）を対象と
する場合には、内側ループ内で最後に代入が行なわれた
時点から以降においてデータの送信を行なう。

【００４８】DO ALL（もしくはFOR ALL)とはそのループ
を任意の順序で実行しても良いことを示す文である。こ
のときそのループ内で使われる変数はそのループに入る
前の値である。従ってそのような変数は、その内側のル
ープを終了し次の内側のループに入るまでに必要な処理
装置に送られていれば良い。

【００４９】処理装置Ａがデータａを保持し、処理装置
Ｂ_i（１≦ｉ≦Ｎ）がそれぞれデータｂ_iを保持し、処
理装置Ａがデータａを更新するのに、最新のｂ_iのデー
タを必要とし、処理装置Ｂ_iがデータｂ_iを更新するの
に、最新のａのデータを必要とする場合に、前記多重化
されたデータ書き込み領域を二重に持つ。

【００５０】この処理装置Ａは二重化されたデータ書き
込み用に２Ｎ個のフラグｆ_i,pを持ち、フラグｆ_i,pは
処理装置Ｂ_i用のデータ書き込み領域のｐ番目の領域に
対応し、処理装置Ｂ_iは処理装置Ａに対して二つのデー
タ書き込み領域に交互にデータを書き込み、かつデータ
を書き込んだ後にその領域に対するフラグを真にし、処
理装置Ａはそのデータを読み込んだのちにそれに対応す
るフラグを持つ。

【００５１】処理装置Ａがｊ番目に更新されたａのデー
タ値を計算している時には、処理装置Ｂ_iもｊ番目に更
新されたｂ_iのデータ値を計算しているかもしくは計算
し終わっている時である。このとき、処理装置Ｂ_iも
（ｊ−１）番目に更新されるｂ_iのデータ値を計算して
いることはない。そうだとすると（ｊ−１）番目のｂ_i
のデータは未確定の状態であり、このような状態ではｊ
番目のａのデータは計算できるはずはない。また、この
ときに処理装置Ｂ_iが（ｊ＋１）に更新されるｂ_iのデ
ータ値を計算していることもない。この時点ではａの値
は確定していないので、処理装置Ｂ_iはｂ_iの（ｊ＋
１）番目の更新値の計算には取り掛かれない。

【００５２】このような状況では、処理装置Ａがｊ番目
のａを計算してその値を書き込もうとしている時には、
処理装置Ｂ_iはａの値については（ｊ−１）番目の値の
みを保持しておけば良く、（ｊ−２）番目以前のａの値
を保持している必要はない。従って、処理装置Ａはｊ番
目のａの値が計算できた後に、（ｊ−２）番目のａの値
が書かれていた場所にｊ番目のａの値を処理装置Ｂ_iに
確認を求めることなく書き込むことができる。即ち、ａ
のためのデータ書き込み領域として、処理装置Ｂ_iは二
重にデータ領域を持っていれば十分である。

【００５３】また、通信する２つの処理装置がフラグＷ
とＲとで互いに追い越しがないように制御しても良い。
また、２つの処理装置が論理的に協調して計算を進めて
行く場合には、データ領域における追い越しはありえな
い。しかし、フラグの制御の追い越しはありえる。そこ
で、フラグをデータ書き込み領域ごとに持たせることに
する。こうすると書き込み領域を二重にしてフラグＷと
Ｒを持ったときと、フラグのための所要メモリ量は変わ
らない。しかし、請求項目第２記載の一般的な場合に
は、１回のデータ書き込みに対してフラグＲとＷとの両
方のフラグの設定が必要であったが、２つのフラグを交
互に利用する場合には、１回のデータ書き込みに対して
一つのフラグの設定で済み、フラグ制御のための時間が
節約できる。ここではフラグの値を読み取ることは考慮
していないが、フラグの書き込みはリモートアクセスで
あるのに対して、フラグの読み込みはローカルアクセス
であることを考えると、フラグの設定の方が参照よりも
重要である。

【００５４】プログラマに対しては、前記多重化された
データ領域はデータのバージョンを意味するものとし、
プログラムの中からそれらを区別してアクセスできる環
境を提供する。

【００５５】計算機として複数のバージョンの値を保持
しているならば、それらの値をプログラムから参照でき
るようにするとさらにプログラミングが容易となる。例
えば、新旧２つの値の差の絶対値の和がある一定値以下
になったら、繰り返し終了させるような場合を考える。
もし新旧２つのバージョンがあることをユーザに見せな
いと、プログラマは旧値を保持する配列を用意し、そこ
に旧値をコピーしておくことになる。ところが本発明の
ように旧値もプログラムからアクセス可能にすると、そ
のようなオーバーヘッドが不要となる。

【００５６】本願第３の発明のコンパイル方式は以下の
ように構成される。複数の処理装置からなる並列計算機
においてプログラムを実行する場合に、ソースプログラ
ムをコンパイルする時に、実際に実行する処理装置の台
数や結合状態とは関係がない部分については他のモジュ
ールと結合可能なオブジェクトまでコンパイルするが、
依存する部分については中間コードを生成し、次にその
プログラムを実行する処理装置にその中間コードをロー
ドし、それぞれの処理装置において、実際に用いる処理
装置の台数およびその結合形態情報を用いて、中間コー
ドを最適コードにコンパイルする。

【００５７】基本構成を図２１に示す。従来のコンパイ
ル方式と大きく異なる点は、ホストと並列処理装置との
両方にコンパイラを持つ点である。ホスト計算機１３は
ネットワーク１９を介して複数の処理装置２１ａ，２１
ｂ…，２１ｎと接続されている。ホスト１３のコンパイ
ラ１３ａはソースプログラム１５を解析して、並列化の
ための制御に関係しない部分については従来手法によっ
てコンパイルし、他のモジュールとリンク可能なオブジ
ェクトモジュールを生成する。これに対して並列化のた
めのプログラム変換によって制御コードを含むような部
分は、中間コードのまま残しておく。

【００５８】並列化のための制御コードとは、処理装置
番号に依存した制御コードを含む部分である。例えば、
処理装置が何番ならどうするかという部分であり、図４
７のPlocal変数を含む行がこれに該当する。この部分が
どこにあるかは従来の技術によって解決できる。即ち、
世にある並列化コンパイラではソースプログラムから並
列化されたノードプログラムを生成する。このときに並
列化のための制御コードを含んだコードを生成する。こ
の部分を中間コードのまま残しておけば良い。ここで生
成された上記二種類のモジュール（リンク可能なオブジ
ェクトモジュールと中間コードのモジュール）を中間プ
ログラムとしてファイル１７に格納する。

【００５９】このプログラムを実行する際には、まず、
実行すべき処理装置を獲得する。次に獲得した処理装置
に同一のファイル１７の内容を各処理装置のメモリ（中
間モジュール）２３にロードする。更に各処理装置にお
いて、処理装置の台数や結合形態情報を用いて、メモリ
２３に置かれた中間コードをノード側コンパイラ２５に
よって最適化コンパイルし、モジュールをリンクして実
行可能なオブジェクト（実行コード）２１を生成する。
ここで各処理装置で台数や結合形態情報を用いて最適化
コンパイルするとは、自処理装置番号や獲得できた処理
装置の総数の情報などを用いて部分計算することを意味
する。例えば獲得できた処理装置が４台で図４６のプロ
グラムを実行する場合には、自処理装置番号Plocalを得
て、各処理装置では図２２，２３，２４のようにコンパ
イルを行う。即ち処理装置により異なったコードが生成
されることになる。

【００６０】なお、処理装置でコンパイラが起動される
のは、プログラムがロードされた直後のみであると限定
するものではない。処理装置でのコンパイラはプログラ
ム実行後に再び起動されてもよい。プログラムが実行さ
れる環境が整った（実行する処理装置が決まった）後に
処理装置でコンパイルするというのは、コンパイルと実
行とを並行して行う本発明の一例に過ぎない。

【００６１】実行途中でコンパイルを行うには、どの部
分をいつコンパイルするかという基準が必要である。ま
ず「どの部分」かについては、中間コード部（並列処理
のためのコードをソースコードに挿入した部分）とす
る。さらに「いつ」という点については、eager evalua
tion(eager compilation) とlazy evaluation(lazy com
pilation) の二つの方法が考えられる。前者はこれは中
間コードに含まれる疑似定数もしくはホスト側コンパイ
ラが抽出した変数の状態が変わる度に、実行コードを有
効化（再コンパイル）したり、無効化する。後者は実際
に中間コード部を実行するときになって、その中間コー
ドをコンパイルしてから実行するか、既にコンパイルし
た実行コードを再利用して実行するかを決める方式であ
る。

【００６２】本願第４の発明の中間コードに影響を持つ
変数の管理について説明する。

【００６３】ノードプログラムにおいて並列化のために
付加したコードについては中間コードのまま各処理装置
で保持し、その中間コードに出現する変数が前回同じコ
ードで実行してから変更されたかを知る手段として、そ
れに係わる変数が変更されたことを記すフラグを持つ
か、あるいはそれに係わる変数ごとに変更時刻を記録す
るタイムスタンプを持ち、その中間コード部を実行する
直前にそのコードを実行するのか始めてかどうかを知る
フラグを持ち、その中間コードを実行するのが始めて
か、もしくは前回実行してからその中間コードに係わる
部分の変数が変更された場合には、その中間コードを変
数を定数化してからコンパイルして実行し、かつその実
行コードを保持し、その中間コードを実行するのが二度
目以降であり、かつ前回実行してからその中間コードに
係わる変数が変更されていない場合には、前回用いた実
行コードを実行する。

【００６４】プログラム実行前には変数である部分計算
ができなかったが、実行により変数が定数化される（あ
る時点以降値が変化しなくなる）ことがある。この場合
には部分計算が可能になり、より実行効率が高いコード
にコンパイルすることが可能となる。ここで問題てなる
のは、変数が定数化されたからと言って毎回コンパイル
していたのでは、同じ計算を毎回行う効率が低いコード
を実行するのと処理効率は変わらない。コンパイルする
のは、変数が変化した時のみにしなければならない。こ
のためには変数が変化したということを知ることが必要
である。

【００６５】この表現方法として２つの方法が考えられ
る。１つは変数にその変数が変更されたかどうかを表す
フラグを持つ。ある中間コードを再コンパイルしたとき
に、そのフラグを真にし、その後でその変数を変更した
ら変更時にフラグを偽にする。そのルーチンを再度実行
する場合に、フラグが真であれば、そのままそのルーチ
ンを実行するし、フラグが偽であればそのルーチンを再
コンパイルする。

【００６６】もう１つは変数にバージョン番号を持たせ
る方式である。この場合には変数は値を変更する度にバ
ージョン番号を増加させて行く。あるルーチンを再コン
パイルする時には、その時用いた変数のバージョンを記
憶しておく。そして次にそのルーチンを実行するときに
は、そのルーチンの再コンパイルに係わるバージョンが
前回から変化していないかを調べ、もし同じならばその
ルーチンをそのまま実行する。もし変化していればその
ルーチンを再コンパイルしてから実行する。

【００６７】ここに図４３，４４のプログラムを本発明
方式に則って変形した例を挙げる。図２５のプログラム
では、図４３，４４のプログラム同様に下限Ｍ１から上
限Ｍ２までの配列Ａについて、Ａ（Ｉ）＝Ｉを行う。図
４３，４４の場合には、変数Ｍ１及び変数Ｍ２は一旦設
定された後は固定であったが、図９の場合には、変数Ｍ
１および変数Ｍ２が時々変化するものとする。図２５で
はＬ７のMETA-CODE BEGIN 〜Ｌ１４のMETA-CODE ENd ま
での間が中間コードであるという指定になっている。こ
の指定はホスト側のコンパイラによって付加される。図
２１のファイル７６に格納される場合には、Ｌ７〜Ｌ１
４は中間コードのまま残され、Ｌ１６〜Ｌ１９はリンク
可能なモジュール形態（アセンブラもしくはリロケータ
ブル形式）になっている。各処理装置で実行していると
きにこのサブルーチンPEX に至った時に、このルーチン
が始めての実行であるか、もしくはＬ８で指定されたリ
ストの変数MYPE，Ｍ１，Ｍ２の値が変更されたかどうか
を調べ、いすれか一方の条件が成り立つときのみＬ７〜
Ｌ１４を実行可能コードにまでコンパイルしてから実行
する。両方とも成り立たない場合（通常の場合はこちら
である）には、前回用いた実行コードを再利用する。な
お、Ｌ８で示されたリストは、Ｌ７〜Ｌ１４の中で参照
される変数のリストであり、これについてはホスト側の
コンパイラがソースプログラムを構文解析することによ
り自動的に生成可能である。

【００６８】ここで再コンパイルの時間的コストは、定
数化した変数を変数として従来通りに計算するのと同等
の時間コストである必要がある。そうすれば、例え、毎
回再コンパイルしても従来方法と同等の実行性能であ
る。一般には同じ値のまま実行するルーチンが多いであ
ろうから、実行速度は向上する。

【００６９】つぎに、定数化／変数化可能な疑似定数の
導入について説明する。

【００７０】プログラム中のシンボルは、変数、定数、
疑似定数のいずれかの属性を持ち、疑似定数とはプログ
ラムの中から定数化／変数化が指定できるシンボルであ
り、定数化の指定がされたら、次に変数化されるまで、
値を変更することが許されず、値を変更するとメモリ保
護例外の実行時エラーを起こす。

【００７１】一般にプログラムには値を持つものとし
て、変数と定数とがある。これに加えて本発明では疑似
定数という種類の値を持つ。これには図２５（ａ）のよ
うにPSEUDO属性を付けて明示的に疑似定数である宣言を
してもよいし、図２６（ｂ）のように普通の変数と同じ
ように疑似定数を宣言したとしてもよい。このようにし
ても、疑似定数ならばその後で、定数化を指示するFREE
ZE命令や、変数化を指示するMELT命令が出現するので、
どれが疑似定数であるかは機械的に判別可能である。こ
こで、PSEUDO指定をしたり、FREEZE,MELT 命令を記述す
るのはプログラマの責任とする。

【００７２】図２５に対応するプログラムを図２７に示
す。但し疑似定数は初期状態（プログラム開始時）には
変数化状態（値を変更できる状態）にあるとする。ここ
ではサブルーチンINITIALIZE（Ｌ１〜Ｌ８) は、Ｌ２で
自処理装置番号をMYPEに代入した後に、Ｌ３でMYPEを定
数化する。同様にＬ４〜Ｌ５では、Ｍ１，Ｍ２の値を決
定した後に、Ｌ６でそれらを定数化する。

【００７３】この定数化の作業では、２つのことを行
う。１つは定数化による最適化であり、図２７の場合で
は、Ｌ２２〜Ｌ２５でＮ１，Ｎ２を計算しているが、こ
の計算はサブルーチンPEX を実行する度に毎回実行する
のではなく、疑似定数が定数化されたとき（これについ
ては［５］参照）、もしくはサブルーチンPEX で疑似定
数の値が前回と異なっていたとき（これについては
［６］参照）に行う。

【００７４】もう一つは疑似定数のプロテクトである、
疑似定数を定数化した時には、それらの疑似定数に書き
込みができないように、書き込み禁止指定をする。これ
にはＯＳの協力を得て、指定された疑似定数を含むメモ
リのページを書き込み禁止にする方法が挙げられる。こ
れとは逆に疑似定数を変数化した時には、それらの疑似
定数に書き込みができるように、書き込み許可指定をす
る。これにはＯＳの協力を得て、指定された疑似定数を
含むメモリのページを書き込み許可にする方法が挙げら
れる、このためには、同時にFREEZE,MELT される疑似定
数単位で同一のメモリのページに割り付けられているこ
とが望ましい。もしプログラム中で定数化された疑似定
数の値を変更しようとしたならば、実行時のエラーを出
すようにする。例えば、サブルーチンREINIT( Ｌ９〜Ｌ
１６）では疑似定数Ｍ１，Ｍ２の値を変更している（Ｌ
１１〜Ｌ１２）。この変更前にＬ１０のMELT命令で変数
化している。もし、MELT命令なしに疑似定数Ｍ１，Ｍ２
の値を変更しようとした場合には、エラーを表示する。
勿論、コンパイラによって静的にこのような誤った書き
込みが検出可能な場合には、コンパイルエラーという形
でプログラマに教示し、それが不可能な場合には実行時
のエラーとして表示する。

【００７５】なお、全ての疑似定数を同時に定数化／変
数化するためには、引数なしのFREEZE()命令やMELT()命
令を用いることも考えられる。このようにすると、全て
の疑似定数を同一のページに入れて管理でき、しかもME
TA-CODE をコンパイルするべきか否か、また無効にすべ
きか否かが容易にわかるようになり、インプリメンテー
ション上の効率は向上する。

【００７６】次に、疑似定数と中間コードとの関係につ
いて説明する。中間コードを確定（最適化コンパイル）
するべき時、およびコンパイルされた実行コード無効に
する時を知るためには、その中間コードの確定に影響を
及ぼす疑似定数の値が変化したかどうかを知る必要があ
る。このために中間コードをコンパイルするために必要
な疑似定数のリストを持ち、ある疑似定数が定数化され
た時に、その定数化により確定可能な中間コードがあれ
ば、その中間コードを確定（最適化コンパイル）し、逆
にある疑似定数が定数化された時に、その疑似定数を含
む確定済みの中間コードを無効化する。

【００７７】疑似定数がありそれについて定数化の指示
がある場合、それをきっかけにして中間コードをコンパ
イルする。ある中間コードが疑似定数を含む場合、二つ
の疑似定数のうち一方だけが定数化された時に、その事
実だけを記憶しておき中間コードのコンパイルはしな
い。さらにもう一方の疑似定数も定数化されたときに、
その中間コードをコンパイルする。また、二つの疑似定
数のうち一つでも変数化された時には、その中間コード
がコンパイル済みの場合にはその実行コードを無効化す
る。また、全ての疑似定数が定数化されていない内に、
その中間コードを実行する必要が生じた場合には、その
中間コードを実行する直前にそれをコンパイルした後
に、その実行コードを実行し、しかる後にその実行コー
ドを無効化する。

【００７８】つぎに中間コードのeager evaluationにつ
いて説明する。疑似定数が定数化されたときに、その疑
似定数に関する中間コードについて最適化コンパイルを
行ない、疑似定数が変数化されたときに、その疑似定数
に関する中間コードについて最適化コードのについて最
適化コンパイルされた実行コードを無効化する。

【００７９】処理装置の上で部分計算してコンパイルし
た実行コードが有効であるのは、その部分計算に係わる
疑似定数が不変の間である。従ってそれらの値が更新さ
れたときには部分計算によって最適化コンパイルした実
行コードを無効にする必要がある。実際にコードを使う
かどうかということではなく、これは疑似定数の状態が
変わる度に、実行コードを有効化（再コンパイル）した
り，無効化するという意味で実行コードのeager evalua
tion(eager compilation) と言える。これに対してlazy
evaluation(lazy compilation) という手法もある。こ
れについて次に述べる。

【００８０】次に、中間コードのlazy evaluation につ
いて説明する。中間コード部を実行する直前にその中間
コードを実行するのが始めてか、もしくは前回実行して
からその中間コードに係わる部分の変数が変数化された
場合には、その中間コードを変数を定数化してからコン
パイルして実行し、かつその実行コードを保持し、その
中間コードを実行するのが二度目以降であり、かつ前回
実行してからその中間コードに係わる変数が変数化され
ていない場合には、前回用いた実行コードを実行する。

【００８１】この場合には先と反対に、実際にコードを
実行するときにその実行コードが有効かどうかを調べ、
有効ならばそのまま実行し、無効ならばコンパイルして
新しい実行コードを得てから実行するという方式であ
る。これは［５］と比較して言うならば、lazy evaluat
ion （lazy compilation）である。

【００８２】

【実施例】本発明の一実施例に係わる並列処理装置につ
いて以下に３つの例について説明する。

【００８３】実施例１：図２に示すソースプログラムを
並列実行する場合について例を示す。ここで，N,COEF,E
PSILONは定数である。このＣライクなプログラムは一次
元配列ｘについて、自分と両隣の値の和にCOEFを掛けた
ものを新しい値とし、これを新値と旧値との差の自乗和
がEPSILON 以下に収束するまで繰り返すというものであ
る。

【００８４】このソースプログラムをデータ依存性解析
手段により解析し、配列old-ｘは配列ｘの一つ前のバー
ジョンを保持するものであると認識する。並列処理を考
慮して図３，４のようなプログラムに変換して実行す
る。以下にプログラムの説明をする。この配列ｘを並列
計算機上で処理装置当たりの分担が等しくなるように分
散配置させる（図１）。こうすると端以外では処理装置
間でｘの値を交換し合うことになる。各処理装置では分
割された配列ｘを持つ（分散配置した後もｘという同じ
変数名を使っていることに注意）。これは(iterate+2)
個の要素を持つ配列で、処理装置ｉのx[0]には処理装置
（i-1 ）のx[iterate]の値が格納され、x[1]〜x[iterat
e]には処理装置ｉの担当分のｘのデータが格納され、x
[iterate+1]には処理装置(i+1) のx[1]の値が格納され
る（図１参照）。なお、簡便のため処理装置ｉにとって
処理装置(i+1) を右隣の処理装置と呼び、処理装置ｉに
とって処理装置(i-1) を左隣の処理装置と呼ぶ。フラグ
の対応関係を図５に示す。以下に変換されたプログラム
（図３及び図４）を説明する。

【００８５】Ｌ６〜Ｌ７：処理装置ｉは処理装置(i-1)
とのデータ通信のために、flagWLとflagRLとを持ち、処
理装置ｉは処理装置(i+1) とのデータ通信のために、fl
agWRとflagRRとを持つ。

【００８６】Ｌ９：sync(REQUEST) は全処理装置が同期
して動作するための同期要求である。ここでは処理装置
は同期要求だけを出して待つことはしない。

【００８７】Ｌ１０〜１１：全処理装置の台数をPE NUM
とし、配列の大きさをｎとすると、処理装置pe id(0
pe id in) はiterate 個の要素を担当する。ここでiter
ate はpe id ＜ｎのとき(n+PE NUM-1)/PE NUM であり、
pe id=n-1 のときn-(PE NUM-1)*(n+PE NUM-1)/(PE NUM)
である。

【００８８】Ｌ１２：sync(WAIT)で全処理装置が同期を
取るまで待つ。

【００８９】Ｌ１４：flagWL,flagWR が真である状態か
ら始めたとし、まずflagWL,flagWR を偽にする。

【００９０】Ｌ１５〜Ｌ１７：処理装置pe id>0 は左隣
の処理装置のx[iterate+1]にx[1]の値を書き込む。ここ
で、左辺式LHE@処理装置PE は処理装置PEに格納されているデータの左辺式LHE であ
ることを表す。それから、左隣のrflag1を偽にする。

【００９１】Ｌ１８〜Ｌ１９：最左の処理装置の場合に
は、単に自分のflagRRを真にする。

【００９２】Ｌ２１〜Ｌ２３：処理装置pe id < (PE NU
M-1)は、右隣の処理装置のx[0]に自分のx[iterate]を書
き込む。

【００９３】Ｌ２４〜Ｌ２５：最右の処理装置の場合に
は、単に自分のflagRLを真にする。

【００９４】Ｌ３２〜Ｌ３３：データが書き込まれるま
で待つ。

【００９５】Ｌ３４：配列Ｘの新旧交替をする。

【００９６】Ｌ３５〜Ｌ４０：各処理装置でｘの値を更
新し、新旧の値の差の自乗の部分和をdif に集める。

【００９７】Ｌ４１〜Ｌ４２：まず自乗和gsumを未定儀
（ＵＮＤＥＦ）にしてから、非同期にdif の処理装置全
体での和を求める。非同期というのは、このgsumを求め
る操作とプログラムコードの以下の実行とが並列に行な
われるということを意味する。即ち、部分和dif の総和
を求める作業とこれから行うｘの新しい値の送信とが並
列に行なわれる。gsumがいつ求まったか明らかにするた
めに、gsumにはあらかじめＵＮＤＥＦという負の値をい
れておく。自乗和は必ず非負である。従ってgsumに非負
の値がセットされれば、gsumの値が求まったと言える。

【００９８】Ｌ４３〜Ｌ４５：データを使い終えたの
で、flagRL,flagRR を偽にし、flagWL,flagWR を真にす
る。

【００９９】Ｌ４７〜Ｌ６７：データを送信するための
ルーチンである。flagWL,flagWR と先に真になった方か
ら処理を始める。もし、flagWLが先に真になれば、Ｌ４
８〜Ｌ５６でまず、左隣の処理装置にx[1]のデータを転
送し、左隣の処理装置のflagRLを真にする。Ｌ５２でfl
agWRが真になるのを待って、右隣の処理装置にx[iterat
e]を転送し、右隣のflagRRを真にする。これとは逆に、
フラグＷＲが先に真になれば、Ｌ５７〜Ｌ６５でまず、
右隣の処理装置にx[iterate]のデータを転送し、右隣の
flagRRを真にする。Ｌ６１でflagWLが真になるのを待っ
て、左隣の処理装置にx[0]を転送し、左隣のflagRLを偽
にする。

【０１００】Ｌ４８〜Ｌ６６のコードでは端の処理装置
の考慮が、高速化のためにわかりにくくなっているの
で、これについて説明する。最左の処理装置０がＬ４８
の条件文を満たすと、Ｌ４９の(pe id-1) が不適切な値
となる可能性がある。しかし、処理装置０では、flagWL
の値はＬ１４で偽にされ、flagWLを真にする唯一の文で
あるＬ４５は処理装置０のためには絶対に実行されない
ので、処理装置０ではflagWLは常に偽である。従って、
Ｌ４８の条件文を満たすことはありえない。このためＬ
４８の条件に先だって、処理装置番号が０よりも大きい
ことという条件を検査することは不要になる。同様に処
理装置PE NUM-1において、flagWRは常に偽であるので、
不具合は起こらない。

【０１０１】Ｌ６８：Ｌ４２で要求したdif の総和がgs
umに求まるまで待つ。

【０１０２】Ｌ６９：誤差の自乗和がEPSILON 以下にな
るまでループＬ２８〜Ｌ６８までを繰り返す。

【０１０３】実施例２：図６に示すソースプログラムを
並列実行する場合について例を示す。ここで、N,COEF,E
PSILONは定数である。このＣライクなプログラムは一次
元配列ｘについて、自分と両隣の値の和にCOEFを掛けた
ものを新しい値とし、これを新値と旧値との差の自乗和
がEPSILON 以下に収束するまで繰り返すというものであ
る。このプログラムは実施例１のものとほぼ同様である
が、配列ｘがリング状になっている点が異なる。即ち、
処理装置(PE NUM-1)の配列のｘの最後の要素の次の要素
は、処理装置０の配列ｘの最初の要素である。また、処
理装置０の配列のｘの最初の要素の前の要素は、処理装
置(PE NUM-1)の配列ｘの最後の要素である。

【０１０４】このソースプログラムをデータ依存性解析
手段により解析し、配列old x は配列ｘの一つ前のバー
ジョンを保持するものであると認識する。またさらにこ
の場合には、特許請求の範囲４にある条件を満たしてい
ることを認識する。並列処理を考慮して図７，８のよう
なプログラムに変換して実行する。以下にプログラムの
説明をする。

【０１０５】この配列ｘを並列計算機上で処理装置当た
りの分担が等しくなるように分散配置させる。こうする
と端以外では処理装置間でｘの値を交換し合うことにな
る。各処理装置では分割された配列ｘを持つ。これは(i
terate+2) 個の要素を持つ配列で、処理装置ｉのx[0]に
は処理装置(i-1) のx[iterate]の値が格納され、x[1]〜
x[iterate]には処理装置ｉの担当分のｘのデータが格納
され、x[iterate+1]には処理装置(i+1) のx[1]の値が格
納される。なお、簡便のため処理装置ｉにとって処理装
置(i+1) を右隣の処理装置と呼び、処理装置ｉにとって
処理装置(i-1)を左隣の処理装置と呼ぶ。フラグの対応
関係を図９に示す。以下に変換されたプログラム（図
７，８）を説明する。

【０１０６】Ｌ７：変数phase は０と１との値を交互に
取り、いずれのバッファ、もしくはフラグを設定するか
を記憶する。

【０１０７】Ｌ８：処理装置ｉは処理装置(i-1) からデ
ータが書き込まれたことを知るためにフラグRL[2] を持
ち、処理装置ｉは処理装置(i+1) からデータが書き込ま
れたことを知るためにフラグRR[2] を持つ。

【０１０８】Ｌ１０：sync(REQUEST) は全処理装置が同
期して動作するための同期要求である。ここでは処理装
置は同期要求だけを出して待つことはしない。

【０１０９】Ｌ１１〜Ｌ１２：即ち、全処理装置の台数
をPE NUMとし、配列の大きさをｎとすると、処理装置pe
id(0 ≦pe id in) はiterate 個の要素を担当する。こ
こでiterate はpe id < n のとき(n+PE NUM-1)/PE NUM
であり、pe id=n-1 のときn-(PE NUM-1)*((n+PE NUM-1)
/PE NUM)である。

【０１１０】Ｌ１３：sync(WAIT)で全処理装置が同期を
取るまで待つ。

【０１１１】Ｌ１５：データがリング状に管理されてい
ることを考慮して、左隣の処理装置の番号をpeに代入す
る。

【０１１２】Ｌ１６：左隣の処理装置にデータを転送す
る。

【０１１３】Ｌ１７：左隣の処理装置のflagRR[phase]
を真にする。左隣の処理装置にとってみれば、右隣から
のデータがセットされたという意味だから、flagRLでは
なくflagRRを真にする。

【０１１４】Ｌ１９：データがリング状に管理されてい
ることを考慮して、右隣の処理装置の番号をpeに代入す
る。

【０１１５】Ｌ２０：右隣の処理装置にデータを転送す
る。

【０１１６】Ｌ２１：右隣の処理装置のflagRL[phase]
を真にする。

【０１１７】Ｌ２３〜Ｌ５１：収束するまで反復を繰り
返す。

【０１１８】Ｌ２７：左の処理装置からphase のデータ
が書き込まれるまで待つ。

【０１１９】Ｌ２８：右の処理装置からphase のデータ
が書き込まれるまで待つ。

【０１２０】Ｌ２９：配列ｘの新旧交替をする。

【０１２１】Ｌ３０〜Ｌ３５：全部の配列ｘの要素につ
いて、新しい値を計算する。

【０１２２】Ｌ３３：誤差の自乗をｖに求める。

【０１２３】Ｌ３４：誤差の自乗和をdif に求める。

【０１２４】Ｌ３６〜Ｌ３７：まず自乗和gsumを未定儀
（ＵＮＤＥＦ）にしてから、非同期にdif の処理装置全
体での和を求める。

【０１２５】Ｌ３８：左右の処理装置のデータ書き込み
完了フラグflagRL[phase],flagRR[phase] を偽にする。

【０１２６】Ｌ３９：フェーズphase を進める（反転さ
せる）。

【０１２７】Ｌ４１〜Ｌ４３：左隣の処理装置にデータ
を転送し、左隣の処理装置のフラグflagRR[phase] を真
にする。

【０１２８】Ｌ４５〜Ｌ４７：右隣の処理装置にデータ
を転送し、左隣の処理装置のフラグflagRL[phase] を真
にする。

【０１２９】Ｌ４９：Ｌ３７で要求したdif の総和がgs
umに求まるまで待つ。

【０１３０】Ｌ５０：誤差の自乗和がEPSILON 以下にな
るまでループＬ２３〜Ｌ５０までを繰り返す。

【０１３１】実施例３：従来のプログラム（図１０）で
は配列Ｘの値の新値を旧値の差の絶対値の和を求めるた
めにループ１０で配列Ｘの値を配列Ｙに一旦退避してい
る。その後でループ３０において差の絶対値の和をDIEF
に求めている。これに対して、本発明によれば、図１１
のように簡便に記述することができるようになる。ここ
で、Ｘ’(I) はＸ(I) の一つ古いバージョンの値を表す
ものとする。また、UPDATE(X) は配列Ｘをバージョンア
ップすることを指示する疑似命令であるとする。この例
では単に配列Ｘか配列Ｙへのコピーの記述が不要になっ
ただけでなく、コーという動作さえしていないことに注
意されたい。すなわち、古い値は多重バッファに残って
いるのでコピーをする必要がないからである。

【０１３２】次に本発明に係るコンパイル方式の一実施
例について説明する。第４の実施例は共有分散メモリへ
のアクセスを高速にする方法であり、これは主に実行前
のコンパイルを想定している。また第５の実施例は定型
的ではあるが場合によっては変わり得る変数（疑似定
数）を含むコードを高速に処理する方法で、実行とコン
パイルとが並行に進む例である。

【０１３３】まず、第４の実施例について説明する。二
次元格子状に接続された分散共有メモリを持つ並列処理
装置に二次元配列x(n,m)を配置して実行する(x(1,1) 〜
x(n,m)のn ×m 個の要素を持つ）。ここでn,m は定数と
する。実行に用いる処理装置はN ×M 個の二次元格子状
に接続されたものとする（図２９）。

【０１３４】ここで、配列要素x(j,i)は、処理装置(((j
-1)/L)+1),((i-1)/W)+1) の処理装置内配列PXのPX(((j
-1)%L)+1),((i-1)%L)+1)にある。但し、L=n/N,W=m/M を
意味し（簡単のためn はN で割り切れ、m はM で割り切
れるものとする）、％記号は剰余を表すものとする。

【０１３５】例えば、n=1000,m=500の場合に、従来では
静的コンパイル時にはN やM の値がわからず、さらには
L やW の値が不明であった。このため、x(123,71) のデ
ータにアクセスするには処理装置((122/L)+1.(70/W)+1)
の部分配列PX((122%L)+1.(70%W)+1)をアクセスするコー
ドを生成しなければならなかった。この計算には割算を
２回含むので実行効率が悪い。

【０１３６】これに対して本発明方式によれば、実行開
始時に処理装置の台数や構成(N,M)を知り、部分計算を
行う。この場合には、N,M の値が確定した時点で、L,W
の値も確定し((L=10,W=5となる) 、より効率が良いコー
ドが生成できる。例えば、x(123,71) のデータにアクセ
スするには処理装置((122/10)+1,(70/5)+1)=(13,15)の
部分配列PX((122%10)+1,(70/5)+1)=PX(3,1) をアクセス
すれば良い。このアドレス計算（コンパイル）は処理装
置獲得後プログラム実行直前に一回だけ実行すれば良
い。以降の実行では、この定数化された効率の良いコー
ドが利用できる。

【０１３７】上記は具体的にx(123,71) の値にアクセス
する場合であったが、ループにおいて配列要素にアクセ
スする場合も同様に効率化が行える場合が少なくない。

【０１３８】例えば図３０（ａ）に示す全体プログラム
は、各処理装置にとってみれば図３０（ｂ）のように見
える。このプログラムでPEY およびPEX は、担当処理装
置の二次元の識別子(PEY,PEX) を表現するものとする。
部分配列では起点が元のプログラムと異なっているの
で、CONST でそのずれを補正している。

【０１３９】更に、図３０（ｂ）のプログラム中に現れ
るのはpx(j,i) という変数であるが、部分配列pxが連続
アドレス領域に確保されているという通常のインプリメ
ンテーションがなされ、かつこれがベクトルプロセッサ
によって処理されるならば、配列要素の先頭であるpx
(1,1) のアドレスが高速にわかればよい。

【０１４０】このpx(1,1) は変数を含まないので、x(12
3,71) と同様に効率のよいアクセスが可能となる。ま
た、ベクトル処理をしない場合であっても、図３０
（ｂ）のループ処理の場合には、操作する配列要素の列
挙が可能である。列挙が可能であるということは具体的
な配列要素が指示できるということであり、この場合に
は効率の良いコードを生成できる。

【０１４１】次に第５の実施例について説明する。配列
の要素M からN までを、配列A を配列B にコピーするソ
ースコード（図３１参照）を並列実行することを考え
る。

【０１４２】並列計算機は複数の処理装置を持ち、実行
時に実際に使える処理装置の台数PENUM は実行時になる
までわからないとする。さらにPENUM 台の処理装置に配
列AとB とを均等に分割して配置するものとする（図３
３（ａ）参照）。

【０１４３】ここで問題となるのは、ループの始点M と
終点N とがどの処理装置の担当するどの要素であるかを
いかに知り得るかということである。逆に処理装置の視
点に立って見れば、自分の保持する配列のどの部分に対
して繰り返し演算を行うかをいかに効率良く知り得るか
という問題である。

【０１４４】例えば、図３１に示すソースプログラムの
並列版として図３２に示すソースプログラムのように記
述することもある。このプログラムでは、自処理装置番
号をPEとし(PE は１〜PENUM の範囲の値をとる自然
数）、一台の処理装置が担当している配列の要素数をＬ
としている。こうすると、処理装置PEが担当する配列は
要素LOW=(L*(PE-1)+1)から要素HIGH=L*PE となる（図３
３（ｂ）参照）。

【０１４５】そこで、各処理装置において繰り返しの添
字の範囲M 〜N とを考慮して、各処理装置における繰り
返しの範囲MX〜NXを求める（図３２のＬ４〜Ｌ５）。こ
の正しさは図１８の６つの場合分けを考えてみればわか
る（ループＬ７〜Ｌ８を実行しない場合には、MX> NXに
なっている）。

【０１４６】場合(1) MX=LOW,NX=N →MX> Nx 場合(2) MX=LOW,NX=N →LOW 〜N 場合(3) MX=LOW,NX=HIGH−LOW 〜HIGH 場合(4) MX=M,NX=N →M 〜N 場合(5) MX=M,NX=HIGH−M 〜HIGH 場合(6) MX=M.NX=HIGH−MX> NX 実際の配列のコピー操作を図３２のＬ７〜Ｌ８のループ
で実際に計算を行う。

【０１４７】図３２は一つの記述方法であるが、従来行
なわれていたように、これを直接実行することは効率が
悪い。実行時（プロセスが処理装置に割り付けられた
時）にはPEおよびPENUM の値はわかり、配列Ａ，Ｂが領
域獲得された時には、Ｌの値も確定する。即ちM および
N の値が決定した時点でMXおよびNXの値は確定するので
ある。それにもかかわらず、ＤＯループを行う度にMX、
NXを計算し直す図１６のプログラムは効率が悪い。

【０１４８】図３４に示す６つの場合分けに沿った実行
コードにすれば、効率が高いプログラムとなる。ある処
理装置にとってみれば、LOW とHIGHとは確定である。さ
らに図３４を式で記述すると図３５のようになる。さら
に図３５は全体としての配列ＡとＢを用いているので、
これを処理装置に小分割された部分配列PAとPBとを用い
て記述すると図３６のようになる。ここで部分配列は各
処理装置の担当分の配列で要素番号はいずれも１〜Ｌで
ある。

【０１４９】以上の準備の元に図３１に示すソースプロ
グラムを本発明の方式でコンパイルすると、ホスト側コ
ンパイラによって図３８に示すコードを中間コードとし
て生成する。このコードでは便宜上、FOO() というサブ
ルーチンになっている（図３８のＬ１）。

【０１５０】このサブルーチン全体がMETA-CODE の範囲
Ｌ２〜Ｌ３７になっている。かつ、このMETA-CODE を決
定するパラメータがＬ２によって、N,M,L,PEであること
が示されている。

【０１５１】そこでこれらの疑似定数の定数化の情報か
ら、サブルーチンFOO を実行時にコンパイルする。これ
によれば、各処理装置で実行するのはサブルーチンFOO
の場合(1) 〜(6) のいずれかであり、そのいずれかであ
るかを判別する条件文は処理装置でのコンパイル時に処
理されるので、効率が高い実行が可能となる。

【０１５２】これはプログラム全体としては、図３７の
ような初期化ルーチンをあらかじめ実行しておくことに
なる。

【０１５３】ここではまず、自処理番号PEを関数MYPENU
M() から取り出した（Ｌ２）後に定数化している（Ｌ
３）。さらに自処理装置における配列PAおよびPBの大き
さＬを入力した（Ｌ４）後に定数化している（Ｌ５）。
この後に配列PAおよびPBのための領域を実際に確保し
（Ｌ６，Ｌ７）、それらの配列をread文によって初期化
している（Ｌ８，Ｌ９）。

【０１５４】まずMETA-CODE をコンパイルする仕組みに
ついて述べる。META-CODE において定数化(FREEZE)およ
び変数化(MELT)に対して、META-CODE の疑似定数の定数
化表をセットする（図４０参照）。

【０１５５】即ち、初期状態では表の要素はすべて偽で
ある。定数化すると対応する表の要素を真にし、変数化
すると対応する表の要素を偽にする。ここで、表の全て
の要素が真になったときにMETA-CODE をコンパイルし、
表の要素の一つでもが偽になった時に既にコンパイルさ
れたMETA-CODE を無効にする。

【０１５６】このプログラムで、処理装置に仕事が割り
付けられ、実行が開始した後では、PEおよびＬの値は一
度定まれば後は永遠に不変である。しかし、M およびN
は配列要素の操作対象を指示するものであり、プログラ
ムの進行中に場合によっては変更され得る。そのような
場合には上記の機構によってサブルーチンFOO() は再コ
ンパイルされる。このような場合の例について説明す
る。

【０１５７】このプログラムの実行例としてを図２１
（Ｃ）に示す。まず、プログラムの図２１（ａ）の初期
化ルーチンINITIALIZE()を呼ぶ。この後で疑似定数N,M
の値を決めた（Ｌ２〜Ｌ３）後に定数化する（Ｌ４）。
ここでサブルーチンFOO() のための疑似定数N,M,L,PEが
確定しているので、サブルーチンFOO() を部分計算を用
いてコンパイルする。その後にサブルーチンFOO() を実
行する（Ｌ５）。次にＬ７でサブルーチンFOO() を実行
するまでに、疑似定数N,M,L,PEの値が変更されなけれ
ば、Ｌ７で実行するサブルーチンFOO() のためには、前
回Ｌ５で実行したときに用いた実行コードを再利用す
る。この後で、疑似定数N,M が変数化された時には（Ｌ
９）、サブルーチンFOO() をＬ１０で実行する前に、再
度サブルーチンFOO() をコンパイルし直してから実行す
る。

【０１５８】初期状態すなわちプログラム開始時は、疑
似定数は、定数化状態でも変数化状態でもいずれかでも
よい。いずれにしてもプログラムでいずれの状態である
か指定できるようになっていれば良い。但し、疑似定数
は最初に代入された後に、後は定数として使うことが一
般的であるので、デフォルトとして初期状態では疑似定
数は変数状態である方がプログラミングが容易あること
が予想される。

【０１５９】

【発明の効果】以上に説明したように、本発明によれ
ば、処理装置間で互いにデータの依存関係のあるプログ
ラムに対して、ＣＰＵで計算処理を行なっている間に近
い将来に他の処理装置を必要とするデータを前もって転
送しておくことができる。これにより、データ転送のオ
ーバーヘッドを隠蔽することができ、効率よく並列処理
することができる。また、実際に処理装置でのプログラ
ムの実行と並行してコンパイルを行うので、実行時にお
ける定数としての情報を活用した部分計算を行うことが
できる。これにより、実行前に静的にコンパイルしてい
た従来方法よりも遥かに実行効率が高い実行コードを生
成できる。

【図面の簡単な説明】

【図１】データの割り付けを示す図である。

【図２】第１の実施例に係る対象となるプログラムであ
る。

【図３】変換されたプログラムである。

【図４】変換されたプログラムである。

【図５】フラグの関係を示す図である。

【図６】第２の実施例に係る対象となるプログラムであ
る。

【図７】変換されたプログラムである。

【図８】変換されたプログラムである。

【図９】フラグの関係を示す図である。

【図１０】従来の新旧のデータを参照するプログラム例
の図である。

【図１１】本発明の新旧のデータを参照するプログラム
例の図である。

【図１２】ＯＳにおける二重バッファ系を説明するため
の図である。

【図１３】ＰＡＸにおける非同期通信を説明するための
図である。

【図１４】基本構成図である。

【図１５】多重化されたデータ領域の書き込み位置の管
理方法を示す図である。

【図１６】データの状態フラグが書き込まれる側の処理
装置にある場合の図である。

【図１７】データの状態フラグが書き込む側の処理装置
にある場合の図である。

【図１８】データの状態フラグが書き込む側と書き込ま
れる側の両方の処理装置に分散されてある場合の図であ
る。

【図１９】図１８の場合の状態遷移図（その１）であ
る。

【図２０】図１８の場合の状態遷移図（その２）であ
る。

【図２１】本発明に係るコンパイル方式を説明するため
のブロック図である。

【図２２】処理装置ごとにコンパイルした場合の実行コ
ードの例を示す図である。

【図２３】処理装置ごとにコンパイルした場合の実行コ
ードの例を示す図である。

【図２４】処理装置ごとにコンパイルした場合の実行コ
ードの例を示す図である。

【図２５】図のプログラムを本発明方式で実現した場
合の図である。

【図２６】疑似定数の定義／用法の例を示す図である。

【図２７】図２５のプログラムを疑似定数を用いて記述
した場合の例を示す図である。

【図２８】全ての疑似定数の定数化の例を示す図であ
る。

【図２９】配列データのマッピングの例を示す図であ
る。

【図３０】分散配置された配列データを操作するプログ
ラムの例を示す図である。

【図３１】第４の実施例説明用の元のソースプログラム
例を示す図である。

【図３２】図３１のプログラムの従来手法によるノード
プログラムの例を示す図である。

【図３３】配列データのマッピングの例を示す図であ
る。

【図３４】繰り返しの領域と担当領域との関係の場合分
けを示す図である。

【図３５】図３４の場合分けを全体的に見た場合を示す
図である。

【図３６】図３４の場合分けを処理装置ごとに見た場合
を示す図である。

【図３７】図３１のプログラムの本発明手法による中間
コードの例を示す図である。

【図３８】図３１のプログラムの本発明手法による中間
コードの例を示す図である。

【図３９】図３１のプログラムの本発明手法による中間
コードの例を示す図である。

【図４０】疑似定数とメタコードとの関係の例を示す図
である。

【図４１】部分計算の例（その１）を示す図である。

【図４２】部分計算の例（その２）を示す図である。

【図４３】従来のプレ実行方式の例を示す図である。

【図４４】従来のプレ実行方式の例を示す図である。

【図４５】一般的なＭＩＭＤ型並列計算機を示す図であ
る。

【図４６】プログラムの並列化の例を示す図である。

【図４７】プログラムの並列化の例を示す図である。

【図４８】データ識別子の構造の例を示す図である。

【符号の説明】

１第１の処理装置３第２の処理装置５第３の処理装置７第４の処理装置

Claims

【特許請求の範囲】

【請求項１】複数台の処理装置と分散共有メモリとそ
れらの間の情報転送路を持つ並列処理装置であって、第１の処理装置は第２の処理装置からの要求を受けるこ
となく第２の処理装置がどの自保有データを必要として
いるかを認識するためにデータの依存関係を解析する解
析手段を有し、第２の処理装置は他の処理装置からデータを転送しても
らうための領域として分散共有メモリ上にデータ領域を
有し、かつ同じシンボルデータに対して多重化されたデ
ータ領域を用意し、第１の処理装置は他の処理装置のデータ領域に順番に巡
回的にデータを書き込む書き込み手段を有することを特
徴とする並列処理装置。
【請求項２】複数台の処理装置と分散共有メモリとそ
れらの間の情報転送路を持つ並列処理装置であって、第１の処理装置は第１のフラグを備え、第２の処理装置は第２のフラグを備え、第１の処理装置が第２の処理装置にデータを書き込むと
きには、初期状態として第２の処理装置の第２のフラグを僞、第
１の処理装置の第１のフラグを真とし、第１の処理装置
は第１のフラグが真になった後に、第１のフラグを偽に
してから第２の処理装置にデータを書き、もしくは第２
の処理装置にデータを書いてから第１のフラグを偽に
し、さらに第２の処理装置の第２のフラグを真にし、また第２の処理装置は第２のフラグが真になった後に、
第２のフラグを偽にしてからデータを読み、もしくはデ
ータを読んでから第２のフラグを偽にし、さらに第１の
処理装置の第１のフラグを真にするプロトコルを有する
ことを特徴とする並列処理装置。
【請求項３】複数の処理装置からなる並列計算機であ
って、プログラムをコンパイルするときに、実際に実行する処
理装置に関しない部分については他のモジュールと結合
可能なオブジェクトまでコンパイルし、依存する部分に
ついては中間コードを生成すると共に、該プログラムを
実行する処理装置に当該中間コードをロードし、それぞ
れの処理装置において、実際に用いる処理装置に関する
情報を用いて、中間コードを最適コードにコンパイルす
ることを特徴とするコンパイル方式。
【請求項４】複数の処理装置からなる並列計算機であ
って、ノードプログラムにおいて並列化のために付加したコー
ドについては中間コードのまま各処理装置で保持し、その中間コードに出現する変数が前回同じコードで実行
してから変更されたかを知る手段として、それに係わる
変数が変更されたことを記すフラグを持つか、あるいは
それに係わる変数ごとに変更時刻を記録するタイムスタ
ンプを持ち、その中間コード部を実行する直前にそのコ
ードを実行するのが始めてかどうかを知るフラグを持
ち、その中間コードを実行するのが始めてか、もしくは
前回実行してからその中間コードに係る部分の変数が変
更されたときには、その中間コードを変数を定数化して
からコンパイルして実行し、かつその実行コードを保持
し、その中間コードを実行するのが二度目以降であり、
かつ前回実行してからその中間コードに係る変数が変更
されていないときには、前回用いた実行コードを実行す
ることを特徴とするコンパイル方式。