JPH08501167A - 並列コンピュータシステムにおけるアプリケーションプログラムの処理方法 - Google Patents

Abstract

(57)【要約】 １つの並列システムの種々のＣ１におけるユーザプログラムの実行の際問題となるのは一方のコンピュータにて実行されるデータ項目が他方のコンピュータにより並列的に実行されるプロセスにて生成されることである。データ項目に対するアクセスを含む各インストラクション（命令）に対してプログラム実行中当該データ項目が並列プロセスで求められるか否かをしらべる必要性を回避するためにユーザプログラムのコンパイルの際既にデータ項目へのアクセスを行わせるコマンドがタグ付けされ、上記データ項目は実際の（現在の）プロセスにて既に計算されているか、又は並列プロセスにてアクセスの時点にて既に計算されて存在しているものである。上記コマンドの実行は直列ケースにおけるように行われる。

Description

【発明の詳細な説明】 並列コンピュータシステムにおけるアプリケーションプログラムの処理方法 斬新な、比較的高速のノイマン形コンピュータの発展は次のような事情により 損なわれる、即ち使用されているテクノロジーの物理的限界に達することにより 損なわれる。最近数十年の趨勢における更なる性能の増大の見込みは見られない 。並列コンピュータは当該状況を次のようにして緩和している、即ちアプリケー ションプログラムの実行のため複数のプロセッサが使用されるのである。勿論こ のことは並列コンピュータの用意だけでは不十分である。簡単に自動的に並列化 され得る、アプリケーションプログラムは極めて僅かである。いずれにしろ必要 なのは当該並列化（手法）ないし並行性を明示的に生成することを可能にするイ ンストラクション（命令）又はコンストラクト（構成子）である。 過去何年にも亘って、並列プログラミングのために並列化（手法）を表現する ことを可能にする種々のプログラミング言語−コンストラクト（構成体）多数が 創出された。然し乍ら、いずれの並列化（手法）も関与する各プロセッサ間の管 理（機能）を包含するという問題を回避できない。従って一般的に、甘受しなけ ればならないことには各並列化プログラムは１つのプロセッサに関して先ず速度 損失を甘受しなければならない。なんとなれば並列的環境ではプログラムは直列 的環境におけるよりも並列的環境では緩慢に進行経過するからである。潜在的並 列化（手法）のみでも付加的コストを要する。従って並列化（手法）により達成 される、プログラム処理の加速度の一部が失われる。 上記問題を図１及び図２を用いて説明する。 通常の直列的ノイマン（コンピュータ）にてすべてのデータＤＡは主（ワーク ）メモリＳＰのロケーションＳＰ内に保持される。それによりプログラムの実行 の際必要とされるデータヘ直接的にアクセスをし得る（図１）。 これに反して並列的に処理さるべきプログラムの実行時間に屡々データは並列 的に計算される。従って、データは直列的な場合におけるようにデータが表され 得るのではなく、一層より複雑な構造が存在する（図２）メモリロケーションＳ Ｐ１は識別子ＫＮを含みこの識別子は通常の（シーケンシャルなケース）又は並 列的に計算さるべきデータ項目が生じているか否かの情報を含み、ＳＰは場合に よりデータ項目が見出されるべきか否かについての情報を含む。並列評価の特徴 とするところはデータが既に計算されているか否か又はそうでないかが不明のこ とである。当該特性は直列的プログラムの場合プログラムの実行により生じるが 、 並列的場合にはより一層複雑な状況が生じる。データ項目は他のプロセッサにて 実行されるプロセスで計算されるべきこととなり得る。第１のケースが生じる場 合は当該データは既に並列化プロセスにて計算されているかも知れないし、そう でないかも知れない。そのような関係状況を図２に示す。ケース２はそれ自体図 １のケースに相応しており、そして次のような点でのみ異なる、即ちプログラム は可能な並列的実行処理のためデータ項目の異なる他の記憶を必要とするという 点でのみ異なる。ここでデータ項目ＤＡは識別子ＫＮと結合されており、このＫ Ｎは当該データ項目は直列的に又は通常のように計算されていることを表す。そ のようなデータ項目は以下“現行”（ｐｒｅｓｅｎｔ）（“ｐｒｅｓｅｎｔ”） と称され、コード中では＄符号を付与される。一方ケース１はアプリケーション プログラムのプロセスの並列的処理が生起しているケースに係わる。ここでは各 メモリロケーション毎に識別子ＫＮが用意されており、この識別子はデータ項目 が並列に実行されるプログラムにて求められることを表す。データ項目の代わり に、ダミーＰＬが用意されており、このＰＬはデータ項目ＤＡがメモリロケーシ ョンＡＳＰ内のどこに存在しているかを表す。ケース１，１ではデータ項目ＤＡ は既に計算済みであるべきものとする（当該データ項目へアクセスが行われると き）。このケースは以下“確定的”（ｄｅｔｅｒｍｉｎｅｄ） （ｄｅｔｅｒｍｉｎｅｄ）と称され、以下コード中で感嘆マーク（！）で表示さ れる。これに反しケース１，２ではダミーＰＬによりデータ項目に対してアクセ スの時点で空き状態におかれている（つまり当該データ項目は並列に実行される プロセスでは未だ計算されていない）メモリロケーションＳＰ２である。このケ ースは以下“未確定”又は“未知”（ｕｎｋｎｏｗｎ）と称され、コード中で“ ？”と略称される。 プログラムのプロセスの並列の計算の際の前述の問題点は刊行物ＷＯ９１／１ ９５２（ＰＣＴ出願）において、一層詳しく述べられている。 並列化（手法）モデルでは任意のインストラクション（命令）に対して図２の 簡単なケース２のほかに図２のケース１，１又は１，２のうちの１つが起こり得 る。要するに各アクセス毎に、インストラクション（命令）は実行の際当該のデ ータ項目を本当に必要とするか否かが調べられなければならない。１つのデータ 項目を本当に必要とするアクセスを以下“非参照”（形）（“ｄｅｒｅｆｅｒｅ ｎｅｉｎｇ”）（略称ｄｅｒｅｆ）と称される。非参照（形）アクセスの場合、 常に留意しなければならないのは場合により間接的に（ケース１，１）又は直接 的に（ケース２）データにアクセスしなければならず、そして、未だ計算されて ない（ケース１，２）データにはアクセスしないことである。これによりデータ 項目をアクセスするインス トラクション（命令）の場合プログラムの実行の際下記について常にチェックし なければならない。 ａ）通常の（ケース２）又は並列に計算さるべき（ケース１）データ項目が存 在するか否か（“現行”（ｐｒｅｓｅｎｔ）テスト） ｂ）場合により、ケースＩにおいてデータ項目が既に計算されたか否かがチェ ックされる（“確定的”（ｄｅｔｅｒｍｉｎｅｄ）テスト） データ項目が既に計算されている場合データ項目にアクセスできる（ケース１ ，１）。そうでない場合（ケース１，２）、データ項目の計算を待機しなければ ならず、そして、その際はじめて、ケース１，１におけるように進行経過され得 る。当該の待機のため以下暗黙的同期化について言及する。 本発明の基礎を成す問題点とするところは処理さるベきアプリケーションプロ グラムのコンパイルの際既にどのインストラクション（命令）に対してテストａ ないしｂが省かれ得るかが確定される方法を提供することにある。上記問題は請 求の範囲１の構成要件により解決される。 従って、コンパイルの際どのカテゴリ内にプログラムのインストラクション（ 命令）が分類さるべきかが調べられ、次のようにインストラクション（命令）が タグ付けされる、即ち“現行”（ｐｒｅｓｅｎｔ）（ケース２）又は“確定的” （ｄｅｔｅｒｍｉｎｅｄ） （ケース１，１）であるデータ項目へアクセスを行わせるインストラクション（ 命令）がタグ付けされる。当該の２つのケース（場合）に対して、“現行”（ｐ ｒｅｓｅｎｔ）テスト又は“確定的”（ｄｅｔｅｒｍｉｎｅｄ）テストを行うこ とはもはや必要でない。なおケース１，２においてのみ従来通常一般のように手 段を講じなければならない。換言すれば“現行”（ｐｒｅｓｅｎｔ）テスト及び “確定的”（ｄｅｔｅｒｍｉｎｅｄ）テストが実施され、データ項目の計算を待 機しなければならない。 プログラミングの言語のすべてのインストラクション（命令）はそれのコンテ キストにより１つのリストにて指定されるようにすると有利である。ここにおい て上記コンテキストにより指示されるのは当該インストラクション（命令）の実 行が次のようなアクセスを含む、即ち、データ項目を必要とする（“非参照的” （ｄｅｒｅｆｅｒｅｎｃｉｎｇ） （“ｄｅｒｅｆ”）又は必要としない（非参 照的（ｄｅｒｅｆ）でない”（“ｎｏｎ−ｄｅｒｅｆ”）アクセスを含むことで ある。上記のリストを用いてはコンパイル中にその中にインストラクション（命 令）が位置付けられているコンテキストが調べられる。 プログラムのコンパイルの際インストラクション（命令）中に含まれている変 数に、それの特性が対応付けられる、要するに、それが“現行（ｐｒｅｓｅｎ ｔ）” “確定的”（ｄｅｔｅｒｍｉｎｅｄ）又は“未知”（ｕｎｋｎｏｗｎ） であるかの特性が対応付けられる。このことは概して次のようにすれば調べられ 得る、即ち個々の変数がそれの発生時にシンボルテーブル内に含まれそこに付加 的に、どのような特性を各変数が有するかが指示されるようにして調べられ得る 。プログラム実行と共に、それら特性は変化し得る。従って、テーブル中には各 変数（これはインストラクション（命令）検査（検証）の時点に用いられ得る） に対する前履歴（プレヒストリ）が含まれている。 分岐化命令を表すインストラクション（命令）は有利に次のように扱い処理（ ハンドリング）される、即ち各分岐に対して変数の特性が調べられ（確定され） 、シンボルテーブル内にエントリされ、次いで判断のため分岐（それの変数特性 が最も不利である）が用いられ得るように取り扱い処理される。 １つのインストラクション（命令）が再帰を包含する場合、スタート特性“現 行”（ｐｒｅｓｅｎｔ）及び（“非参照的”（ｄｅｒｅｆ））特性を出発点とし 、再帰を、変数の特性がもはや変化しなくなるまで実施すると有利である。 ループのため、シンボルテーブルから生じる特性を基礎として、パスは、変数 の特性がもはや変化しなくなるまで反復される。 すべての変数（これは特性“確定的”（ｄｅｔｅｒ ｍｉｎｅｄ）を有する）に特性“現行”（ｐｒｅｓｅｎｔ）が対応付けられ（割 り当てられ）、そのために付加的にインストラクション（命令）を導入し、この インストラクション（命令）は当該インストラクション（命令）の実行を変数の 定まる（“確定的”（ｄｅｔｅｒｍｉｎｅｄ）になる）までストップすると有利 である。 本発明の他の発展形態は引用請求項に示される。 図示の実施処理例を用いて本発明を説明する。 各図の内容は次の通りである。 図３は比較的に容易な理解のため擬似コードで既述されているプログラムセク ションを示す。 図４は本発明に相応したタグ（識別子）符号を有する同じプログラムを示し、 図５〜図１３は本発明の方法により個々のインストラクション（命令）又はコン ストラクトを調べる手法の各例を示す。 暗黙的同期化付きの大抵の言語において、当該の同期化に関して基本オペレー ション（演算）（コンストラクト又はインストラクション（命令））のセマンテ ィクス（意味）を定義付ける（規定）することが必要である。このことはリスト （この中に当該の特性が含まれている）を用いて行われ得る。例えば次のような 定義付け（規定）が成立ち得る。 当該インストラクション（命令）はそれの引数の各々に関して下記のように修 飾される。 −引数は常に“非参照的”（ｄｅｒｅｆ）に必要とされる。 −引数は時々“非参照的”（ｄｅｒｅｆ）に必要とされる。 −引数は当該インストラクション（命令）により“非参照的”（ｄｅｒｅｆ） には必要とされない。 上記の事前定義付けられたインストラクション（命令）はそれの結果の各々に 関して修飾され、ここにおいて、複数の結果を有するインストラクション（命令 ）又は関数が存在する。 −結果は常に計算された（計算済み）値である； −結果は必ずしも計算済み値ではない。 引数が“非参照的”（ｄｅｒｅｆ）形態で、又はそうでない特性（“ｎｏｎ− ｄｅｒｅｆ”）形態で必要とされるかに関する各インストラクション（命令）の 特性はリスト内に収集され、事後的にコンパイルの際使用され得る。 インストラクション（命令）の結果の特性は“非参照的”（ｄｅｒｅｆ）又は そうでない（“ｎｏｎ−ｄｅｒｅｆ”）ような修飾（化）に依存するのみならず 、使用された変数がどのような特性を有するか、“現行”（ｐｒｅｓｅｎｔ）、 “確定的”（ｄｅｒｅｍｉｎｅｄ）又は“未知”（ｕｎｋｎｏｗｎ）であるかの 特性に依存する。変数のそれらの特性は所謂シンボルテーブルにて収集され得る 。 方法ないしメソッドは図３のプログラムセクションを用いて最良に説明され得 る。ここでは幾つかの典型的なインストラクション（命令）が擬似コードで表現 されており、当該インストラクション（命令）はどのようなコンテキストにて生 じているかが指定されている。シンボルテーブル中には生起変数がどのような特 性を有するかが指定されている。付加的にはプログラムコードのどのロケーショ ン（個所）に変数がタグ付けさるべきかがｓｅｌｆの下方に示されている。 シンボルテーブル中にはインストラクション（命令）の実行処理の前後の特性 が指示されている。コンテキストの割当は夫々のサブ構造に係わる。当該のサブ 構造が２つのコンポーネントを有する場合（例えばＸ＝＝４）Ｌ又はＲコンテキ ストについて言及され、唯一のコンポーネントが存在する場合（ｐｒｉｎｔ（Ｙ ））にはたんにコンテキストについて言及する。付加的には相応のサブ構造のｓ ｅｌｆ ｖａ１ｕｅ）が含まれている。それにより目的プログラムがタグ（識別 子）付けさるべき個所（ロケーション）が得られる。ここでもＬ−及びＲは左及 び右（サブ構造指定（参照）のため利用される。留意すべきとことには非参照的 （ｄｅｒｅｆ）な個所（ロケーション）においてのみｓｅｌｆ特性は意味を有す る（有意である）ということである。ここにおいてのみ、実行時に“現行” （ ｐｒｅｓｅｎｔ）に対するテストが行われるが、ここにおい てのみ抑圧すべきものがある。 Ｘ−ｉｎｉｔ−ｖａｌｕｅ及び Ｙ−ｉｎｉｔ−ｖａｌｕｅ に対して想定してあることには Ｘ−ｉｎｉｔ−ｖａｌｕｅは“未知”（ｕｎｋｎｏｗｎ） （？）であり Ｙ− ｉｎｉｔ−ｖａｌｕｅは“現行”（ｐｒｅｓｅｎｔ） （＄）である。 図３のプログラムセクションではたんに２つの変数Ｘ，Ｙが生じ、これらは第 １コマンドで挿入され、シンボルテーブル中に含まれる。インストラクション（ 命令）２により 変数Ｘには１が割付られ、従って、Ｘに対してシンボルテーブ ル中に特性ｐｒｅｓｅｎｔが取り込まれる（包含される）。インストラクション （命令）２のコンテキストは明確であり、それ以上説明する必要はない。 インストラクション（命令）３の内容はＹをＸの関数として計算することであ る。関数Ｆは“未知”（ｕｎｋｎｏｗｎ）であるのでこの時点で変数Ｙは“未知 ”（ｕｎｋｎｏｗｎ）である。このことはシンボルテーブル内にエントリされる 。Ｆは“未知”（ｕｎｋｎｏｗｎ）であるので、非参照的（ｄｅｒｅｆ）でない （確実な近似化）と仮定される。 プログラムのライン４〜６はｉｆ．．．ｔｈｅｎ．．．ｅｌｓｅインストラク ション（命令）を有する。インストラクション（命令）のコマンド（その中にー チ ェックさるべき条件が含まれている）はコンテキスト中ではｄｅｒｅｆであり、 使用される変数Ｘはシンボルテーブルから明らかなようにｐｒｅｓｅｎｔであり 、要するに条件はチェックされ得る。インストラクション（命令）のコマンド５ ではＹがプリントされるべきである（条件が充足された場合には）。Ｙは“未知 ”（ｕｎｋｎｏｗｎ）であるので、当該コマンドはＹがインストラクション（命 令）３により計算されたときのみ実行され得る。システムはこのことを待機しな ければならない。換言すれば当該コマンドが実行されると変数Ｙは“確定的”（ ｄｅｔｅｒｍｉｎｅｄ）でなければならない。コマンド４による条件が充足され ない場合、コマンド６が実行されるべきであり、以て変数Ｙは１に等しくセット され、そして“現行”（ｐｒｅｓｅｎｔ）になることになる。 変数Ｘに対するプリントコマンドを与えるインストラクション（命令）７はコ ンテキスト中でｄｅｒｅｆである、それというのは変数Ｘが存在する場合のみプ リントし得るからである。このことは変数が存在するので可能である。 インストラクション（命令）８は変数Ｙに対するプリントコマンドを与える。 当該インストラクション（命令）は同様にｄｅｒｅｆであり、また同様に実行さ れ得る。それというのはＹは少なくとも特性“確定的”（ｄｅｔｅｒｍｉｎｅｄ ）を有しなければならな いからである。コマンド５はプリントコマンド８の時点で実行されているか、又 はコマンド６の割付４が行われているからである。 インストラクション（命令）９ａ，９ｂは算術的演算即ち加算を表している。 算術的演算のコンテキストは常にｄｅｒｅｆである。当該インストラクション（ 命令）は実行され得る、それというのはＸが“現行”（ｐｒｅｓｅｎｔ）である からである。それにより、Ｙも“現行”（ｐｒｅｓｅｎｔ）であり、相応にシン ボルテーブル中で指定される。 インストラクション（命令）はやはりｉｆインストラクション（命令）インス トラクション（命令）４〜６に相応して扱われる。インストラクション（命令） のコマンドのコンテキストはｄｅｒｅｆである；変数は“現行”（ｐｒｅｓｅｎ ｔ）であるので、コマンドはまた直ちに実行され得る。それにより変数の特性は 変化せず、その結果シンボルテーブルにて変数に対する変化はエントリされる必 要はない。 従って、図３からはどのようにプログラムにて使用された変数が第１の割付の 際シンボルテーブル内にエントリされ得るか、及びどのように次いで、変数の当 該の特性は事後的に他のインストラクション（命令）の際に使用され、その際特 性的に変化し得るかが明らかである。要するに各インストラクション（命令）の 変数に対してシンボルテーブル内に含まれている前履 歴（プレヒストリ）が存在する。インストラクション（命令）のコンテキストは インストラクション（命令）を表す関数から生じ、リスト内に定義つけられ得る 。 図４は変数の特性のタグ識別子付きのプログラムセクションを示す。変数の特 性が“現行”（ｐｒｅｓｅｎｔ）である場合変数の後方に＄シンボルがセットさ れ、そして、変数の特性が“確定的”（ｄｅｔｅｒｍｉｎｅｄ）である場合！が セットそれが“未知”（ｕｎｋｎｏｗｎ）である場合は変数はタグ（識別子）を 付されない。更にインストラクション（命令）の結果は相応に識別子を付される 。このことは例えばコマンド４又は９から看取され得る。プログラムのインスト ラクション（命令）がそのように識別子を付された場合、プログラム実行中下記 を調べ得る、即ちデータへのアクセス付きインストラクション（命令）の場合に 当該データは直接的にアドレッシングされ得るか、又はダミーを介してアドレッ シングされ得るのか、そして存在しること、又はダミーを介してアドレッシング されなければならず、そして、存在しないことを調ベ得る。それに相応して上述 のテストが省かれ得（アクセスにより“現行”（ｐｒｅｓｅｎｔ）であるデータ 項目が生ぜしめられる場合には）、一方ｄｅｔｅｒｍｉｎｅｄであるデータ項目 へのアクセスに対してはデータ項目を待機しなければならないことはない。 付加的には“確定的”（ｄｅｔｅｒｍｉｎｅｄ）で あるデータ項目をアクセスするすべてのインストラクション（命令）にて当該デ ータ項目に特性“現行”（ｐｒｅｓｅｎｔ）が割り付けられる場合、換言すれば ダミーがデータ項目によりオーバーライトされる場合、当該ケース（場合）に対 してもテストはもはや必要でない。 本発明の方法を以下何らのアプリケーションに特定されずに一層抽象的に論じ る。このためにプログラミング言語による幾つかの典型的インストラクシヨン（ 命令）を検討する。 図５はインストラクション（命令）の結果がタグ（識別子）付きされなければ ないか、又はされなくてもよいかを調べるためどのような解析を実施しなければ ならないかを全く一般的に示す。このためにインストラクション（命令）のコマ ンドの引数コンテキス卜（この中にインストラクション（命令）が位置している ）、インストラクション（命令）の引数の特性の検査が必要である。このことは 解析関数の左式中に擬似コードで表される。検査の結果により結果コード（ＲＥ Ｓコード）が得られ、この結果コードはタグ付き又はそうでない。更に結果シン ボルテーブル（ＲＥＳ−Ｓｙｍｂ）が得られ、ここにおいて、インストラクショ ン（命令）の実行により生じる、結果変数の特性の変化がエントリされ、付加的 に、結果の特性（これはコードのタグ中に表現される）は再度概略的（ｓｙｎ ｏｐｔｉｃ）コンテキストの解析の際利用のためｓｅｌｆ−ｐｒｏｐの指示の下 方に与えられる。 第１に算術演算を行うべき（図６）インストラクション（命令）を調べる。こ こで２つの算術演算は２つのオペランドｌｅｆｔ，ｒｉｇｈｔを結合するもので ある。解析関数を用いて両オペランドと結果の双方が再帰的に調べられる。左オ ペランドｌｅｆｔ（今やｎｌｅｆｔと称される）が明らかにしているように当該 オペランドはコンテキストｄｅｒｅｆを有し、オペランドの特性がシンボルテー ブルＳＹＭＢ、要するに当該変数の前履歴（プレヒストリ）から明らかになる。 このことは図６の第２行に示されている。次ぎに右オペランドｒｉｇｈｔが調べ られる（検査される）。勿論当該オペランドもコンテキスト中でｄｅｒｅｆであ り、特性はｌｅｆｔオペランドの検査後に存在するようなシンボルテーブルから 明らかになる。それ故に、そのテーブル、ここではＬ−ＳＹＭＢと称される。結 果（ｒｅｓｕｌｔ）が明らかにしているところによれば、インストラクション（ 命令）ｎ−Ｌｅｆｔ＋ｎ−Ｒｉｇｈｔは常に特性ｐｒｅｓｅｎｔを有しなければ ならず以て、コード中＄でタグ付きされるべきである。結果の特性はオペレーシ ョンの実行により得られる特性により規定される。オペランドの特性がｌｅｆｔ ないしｒｉｇｈｔがｄｅｔｅｒｍｉｎｅｄでもｐｒｅｓｅｎｔでもない場合、タ グ付けされない。このことが 意味することとなるのはオペランドが少なくともｄｅｔｅｒｍｉｎｅｄになるま でオペレーシヨンの実行をシステムは待たねばならないということである。それ にも拘わらずオペレーションの結果は常にｐｒｅｓｅｎｔである、ないし存在す る。それというのはオペランドがｄｅｔｅｒｉｎｅｄである場合、新たな値が生 成されるからである。 図７は関数Ｃｏｎｓ（これによりリストが形成される）の検査の様子を示す。 上記関数はリスト（それのコンポーネントはＣｏｎｓの２つの引数である）を形 成する。リスト形成には引数の有効値は重要でないので、ここで再帰的呼出（コ ール）が行われこれはコンテキストでｎｏｎ−ｄｅｒｅｆである。ここでもイン ストラクション（命令）のコンテキストの検査の時点でのシンボルテーブルから 引数の特性が明らかになる。換言すれば、シンボルテーブルは常時最も新しい状 態に保持される。結果ｒｅｓｕｌｔはインストラクション（命令）Ｃｏｎｓの場 合ｐｒｅｓｅｎｔであり、換言すればリストノードは直ちに生成される（リスト エレメント自体はその際は未計算状態にあり得る）。 図８はＬＥＴインストラクション（命令）に係わる。例えば図３のプログラム が示すように、ＬＥＴコマンドの生起に対して初期値は存在する必要がない、換 言すれば“ＶＡＬＵＥ”はコンテキスト中でｄｅｒｅｆである。ＶＡＬＵＦの特 性は（ＶＡＬＵＥの解析）に より生じる。図３から更に明らかなように新たなシンボルテーブル内に変数Ｘが エントリされる。それの特性はＶＡＬＵＦの特性と同一である。ｎｅｗＳＹＭＢ はＢＯＤＹへ渡される（パスされる）、換言すればＥＮＤとＬＥＴ−ＥＮＤとの 間のプログラム領域へ渡される。ＢＯＤＹのコンテキストはＬＥＴインストラク ション（命令）全体のコンテキストと同じである。生成されるシンボルテーブル はＢＯＤＹにて計算されたシンボルテーブルであり、ここでＸの新たなエントリ が除かれる（Ｃｕｔ−Ｔｏｐ−Ｌｅｖｅｌ）。それというのは当該のＬＥＴクロ ーズ（ｃｌａｕｓｅ）外で可視でないからである。上述の事情関係は図８から明 らかである。 割当のケースを図９に示す。ここでは変数Ｘに変数Ｙが割り当てられる。変数 ＸはＹのすべての特性を継承（インヘリタンス）する。Ｘの特性は変わらない状 態におかれ、前履歴（プレヒストリ）から明らかになる。当該インストラクショ ン（命令）の結果特性は右辺の特性と一致する。それというのは、ある１つの割 当の結果は常に割当られる値に等しいからである。ｎｅｗＳＹＭＢ（Ｘ／ＲＥＳ −ＰＲＯＰ）の表記の意味するところはシンボルテーブルｎｅｗＳＹＭＢにてＸ の下方でＲＥＳ−ＰＲＯＰの特性がエントリされることである。 図１０はｉｆ−ｔｈｅｎ−ｅｌｓｅインストラクシ ョン（命令）に係わる。当該のインストラクシヨン（命令）からは所定の特性が ｄｅｒｅｆに関して明瞭になる。条件ＢＥＤは実行中常に必要とされる。ｉｆは それの第１の引数においてｄｅｒｅｆであり、而して、解析関数ＡＮＡの呼出し （ｃａｌｌ ｕｐ）の際一定のコンテキストｄｅｒｅｆが転送（トランスファ） される。２つのケース識別（差別化）分岐はケース識別分類全体のコンテキスト を継承する。評価順序としては先ず条件の実行、次いで、両分岐のうちの１つの 実行である。条件は“未知”（ｕｎｋｎｏｗｎ）であるので、仮定されていると ころによれば両ケース識別（差別化）分岐は処理されなければならず、結果につ いて保存的（保守的）に近似される。ＲＥＳ−ＰＲＯＰは両分岐の特性のカット （ｃｕｔ）により規定され、従って値として比較的に劣った特性を受け取る。同 様にシンボルテーブルはカット（ｃｕｔ）により計算される；すべてのエントリ に対してその都度比較的悪い値が取られる。 保存的（保守的）近似の同じパターンは他のインストラクション（命令）によ り適用される。（部分）コントラクトがパス（転送）されるか否か、又はどのく らい頻繁にパスされるか分からない場合、すべての可能性が考慮され、カットの 形成により保存的に近似化される。例えばループはそのようにして扱い処理（ハ ンドリング）される；ループは多重に（幾回も）扱い 処理され、ここで新たな終端条件及び終端シンボルテーブルは先行のものをもっ てカットされる。もはや何も変わらない状態が起こると直ちに任意の数のループ パスに亘って近似化が行われている。スタチック（ランダム）に識別可能なルー プの特性は定まっている。 図１１の例のついて、変数の特性がどのように変化し得るか（新たな値を取る ことなく）を説明する。例えばインストラクション（命令）が検査される； Ｙ＝ＩＦ ＶＡＲ ＴＨＥＮ ＶＡＲ ＋１ ＥＬＳＥ ＶＡＲ 変数ＶＡＲは条件ｄｅｒｅｆの形態にて必要とされる。 このことから明らかなように加算にて変数の利用の際以下のことを基礎とし得 る、即ち，ＶＡＲが少なくとも“確定的”（ｄｅｔｅｒｍｉｎｅｄ）であること を基礎とし得る。この例において当該特性はＹに継承される。それにより図１１ による変数に対する一般的な解析関数が生ぜしめられる。ＶＡＲが先だって“確 定的”（ｄｅｔｅｒｍｉｎｅｄ）でなかった場合、留意すべきことにはｄｅｒｅ ｆなアクセスにより変数は“現行（ｐｒｅｓｅｎｔ）”でなく“確定的”（ｄｅ ｔｅｒｍｉｎｅｄ）になることである。 個々のユーザにより定義付けれられた関数の解析はそれらが呼び出す他のユー ザ定義関数の解析に有用である。例えば、いずれの単一変数の単一値の関数Ｆ； ｆ→Ｙに対して、図１２による関数ＡＮＡ−Ｆが生成される。関数引数の元来の 特性から出発して、次のような特性が計算される、即ち、引数及び、当該の呼出 しの結果が有する特性が計算される。比較的多くの引数及び結果を有する関数に 対して同様のことが成立つ。関数の解析中呼び出された関数のソースコードがア クセス可能ではなくなると直ちにペシミスティックに近似化される。そのような 関数の呼出では呼出ロケーションのすべての特性が破壊される。 再帰的関数はループと同様に扱われる（ハンドリングされる）。 再帰的関数呼出のための初期特性を基にして、関数ボディが解析される。当該 手続きプロセデュアは繰り返される。：関数の新たに計算された特性を基にして 、再びボディは解析される。ここで、新たな特性が決定される。特性がもはや変 化しないと直ちに、当該手続きプルセデュアは終了され得る。ここで重要なこと は適正な初期特性を選定することである。解析における他のすべてのポイントに おけるとは異なって、ここではオプティミスティックな近似化が行われるべきで ある。初期特性が表しているところでは再帰的関数のすべての引数がｄｅｒｅｆ になり、すべての結果がｐｒｅｓｅｎｔになる。 ｄｅｒｅｆなアクセスにより変数は特性“確定的”（ｄｅｔｅｒｍｉｎｅｄ） を獲得する。比較的良好な 結果が得られることとなる（変数がｐｒｅｓｅｎｔになれば）。このことは欠点 を生じさせることなく行われ得る。メソッドは次のように変化をさせなければな らない、即ち、変化が“確定的”（ｄｅｔｅｒｍｉｎｅｄ）になると直ちに自己 の値でオーバーライトされるように変化されなければならない。これによりケー ス１，１はケース２により置換される（図２）。特性が可用であるので、すべて の更なる相応の変数のｄｅｒｅｆな利用においてテストがもはや必要でない。同 じことが当該特性を継承するすべての更なる変数に対して成立つ。１つの例を図 １３に示す。 本発明の方法の利点とするところはパラレル（並列）プログラムの実行時に行 うべきダイナミックなチェックが除去されることである。プログラムのスタチッ ク（ランダム）な解析によってはどのロケーションにそのようなチェックを行な わなくてもよいかが確かめられる、それというのはプログラムのシーケンスがチ ェックの結果がどのようなものかが明白になるからである。 そのために下記のことが重要である。 ベーシックコンストラクト又はインストラクション（命令）は特性ｄｅｒｅｆ 、時々ｄｅｒｅｆ，ｄｅｒｅｆで決してない、に関して修飾されると、 −変数及び（部分）式はそれの特性“現行”（ｐｒｅｓｅｎｔ）“確定的”（ ｄｅｔｅｒｍｉｎｅｄ）、 又は“未知”（ｕｎｋｎｏｗｎ）に従ってプログラムの抽象的解釈により修飾さ れることが必要である。解析の結果は変換されたプログラムであり、これからは テストがどこで省かれ得るかが明らかである。 −“確定的”（ｄｅｔｅｒｍｉｎｅｄ）である変数はそれの固有の値でオーバ ーライトされ、それにより”現行”（ｐｒｅｓｅｎｔ）になることが重要である 。それにより解析結果は決定的に改善され、その際プログラムの意義重要性が変 わることはない。 個々の関数の解析結果の利用が他の関数の解析に用いられ得る。 再帰の扱い処理（ハンドリング）、がオプティミスティックな近似化を基にし て反復により行われることが重要である。

【手続補正書】特許法第１８４条の８ 【提出日】１９９４年９月５日 【補正内容】 請求の範囲 １．並列コンピュータにおけるアプリケーションプログラムの処理方法において 、 ａ）プログラムの個々のプロセスを種々のコンピュータにて処理し、 ｂ）アプリケーションプログラムのコードを読込み、 ｃ）アプリケーションプログラムのコンパイルの際各インストラクション（命 令）に対して、リストを用いてそれの実行にはデータ項目に対するアクセスが必 要とされるか否かをしらべ、上記リスト中にはインストラクション（命令）の実 行がデータ項目に対するアクセスを必要とするか（ｄｅｒｅｆ）否かが指定され ており、 ｄ）当該インストラクション（命令）に対してシンボルテーブル中にそれらの 特性に対する変数が下記の状態（ｄ１〜ｄ３）におかれているか、否かが特性と してエントリされ、 ｄ１）実際のプロセスにて既に書込まれているか（ｐｒｅｓｅｎｔ）否か ｄ２）並列的に実行可能であり、実際のプロセスが変数を必要とする際既に計 算されているか否か（ｄｅｔｅｒｍｉｎｅｄ） ｄ３）並列的に実行可能であり、実際のプロセスが変数を必要とする際おそら く未だ計算されていない 状態におかれている（ｕｎｋｎｏｗｎ）か否か、エントリされ ｅ）コンパイルされたプログラミングにてケースｄ１）の成立つインストラク ションには第１の（識別）タグ符号が付与され、これに対して、ケース（ｄ２， １）の成立つインストラクション（命令）には第２のタグ識別子が付与されると ことを特徴とする並列コンピュータシステムにおけるアプリケーションプログラ ムの処理方法。 ２．−各分岐に対する分岐化コマンドに対して結果の特性が調べられ、シンボル テーブル内にエントリされ −分岐化コマンドの結果として当該結果及び分岐のシンボルテーブルが選定 され、上記分岐の特性は最も不利なものであるようにした請求の範囲１記載の方 法。 ３．再帰インストラクション（命令）ないしループインストラクション（命令） の際スタート特性“現行”（ｐｒｅｓｅｎｔ）を基にして、ないし前履歴に相応 して“非参照的”（ｄｅｒｅｆ）関数は特性がもはや変化しなくなるまで反復的 に解析される請求の範囲１記載の方法。 ４．特性“確定的”（ｄｅｔｅｒｍｉｎｅｄ）を有するすべての変数は特性“現 行”（ｐｒｅｓｅｎｔ）を割り付けられ、そのために所定インストラクショ ン（命令）が付加的に挿入され、上記所定インターフェースは変数が定まるイン ストラクシヨン（命令）の実行処理をストップするようにした請求の範囲１から ３までのいずれか１項記載の方法。

Claims (1)

1. 【特許請求の範囲】 １．並列コンピュータシステムにおけるアプリケーションプログラムの処理方法 において、 ａ）プログラムの個々のプロセスを種々異なるコンピュータで処理し、 ｂ）各インストラクションに対してユーザプログラムのコンパイルの際それの 実行にはデータ項目に対するアクセスが必要とされるか否かを調べ（確定し） ｃ）上記インストラクションに対して当該の必要とされたデータ項目は下記に ついて調べられ（確定され）、 ｃ１）考察された実際のプロセスにて計算されたか否か、がしらべられ、 ｃ２）並列的に進行経過する（実行される）プロセスにより供給されたか否 かが調べられ、そしてｃ２）の場合にはｃ２．１）が調べられ即ち、 ｃ２．１）データ項目へのアクセスの時点でデータ項目が存在しているか否 かが調べられ、 ｄ）コンパイルされたプログラムにてケースｃ１）の成立つインストラクショ ンには第１の（識別）タグ符号が付与され、これに対して、ケース（ｃ２．１） の成立つインストラクション（命令）には第２のタグ識別子が付与されることを 特徴とする並列コンピュータシステムにおけるアプリケーションプロ グラムの処理方法。 ２．リストを用いて下記が指示され、即ちコマンドの実行がアクセスを包含する に際して、該アクセスはデータ項目を必要とする（“非参照的”（ｄｅｒｅｆ） ）か、又は必要としないかが指示されるものである請求の範囲１記載の方法。 ３．プログラムのコンパイルの際にインストラクション（命令）の変数の特性が 調べられ、そして下記のものに区別される、 −実際のプロセスにて既に書き込まれたもの（“現行” （ｐｒｅｓｅｎｔ） ） −変数が実際のプロセスにより必要とされるとき並列的に実行処理可能であり 、既に計算済みであるもの、 −変数が実際のプロセスにより変数が必要とされるときなお“未知”（ｕｎｋ ｎｏｗｎ）であって並列的に実行処理可能であるもの（“未知”（ｕｎｋｎｏｗ ｎ））に区別される請求範囲１又は２記載の方法。 ４．プログラムのコードが読み込まれ −インストラクション（命令）の各変数に対してシンボルテーブル中に変数の 特性（“現行”（ｐｒｅｓｅｎｔ）“確定的”（ｄｅｔｅｒｍｉｎｅｄ）“未知 ”（ｕｎｋｎｏｗｎ））がエントリされ、 −各インストラクション（命令）に対して当該イ ンストラクション（命令）のコンテキストが調べられ、 −実行されたインストラクション（命令）の結果はそれの特性に従ってタグ付 け（識別）され、結果変数はそれの特性をもってシンボルテーブル内にエントリ されるようにしたことを特徴とする請求の範囲３記載の方法。 ５．−各分岐に対する分岐命令に対して結果の特性が調べられ、シンボルテーブ ル内にエントリされ −分岐化コマンドの結果として当該結果及び分岐のシンボルテーブルが選定さ れ、上記分岐の特性は最も不利なものであるようにした請求の範囲４記載の方法 。 ６．再帰インストラクション（命令）ないしループインストラクション（命令） の際スタート特性“現行”（ｐｒｅｓｅｎｔ）を基にしてないし前履歴に相応し て“非参照的”（ｄｅｒｅｆ）関数は特性がもはや変化しなくなるまで反復的に 解析される請求の範囲４記載の方法。 ７．特性“確定的”（ｄｅｔｅｒｍｉｎｅｄ）を有するすべての変数は特性“現 行”（ｐｒｅｓｅｎｔ）を割り付けられ、そのために所定インストラクション（ 命令）が付加的に挿入され、上記所定インターフェースは変数が定まるインスト ラクシヨン（命令）の実施処理をストップするようにした請求の範囲３ から６までのうちいずれか１項記載の方法。