JPS6325734A - 論理プログラム処理の方法及びシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 発明の背景 発明の分野 本発明は、少なくとも１個のプロセッサを用いて複数の
論理プログラムを並行処理−特にプロログ（Ｐｒｏｌｏ
ｇ）様言語で−するものであって、“親”と呼ばれる既
存のプロセスによって並行−かつ遡及的−処理を行い、
前記親と並列関係に立つ“子”と呼ばれる少なくとも一
つのプロセスを生成することができる方法及びシステム
に関する。

先行技術の説明 複数の論理プログラムの並行処理−特にプロログ様言語
−における従来技術として、分割ＯＲノードの後の旧プ
ロセスによるすべての設定を解除した後、新プロセスへ
の共通の設定をコピーすることにより逐次計算をＯＲ並
列計算に遡及的に転換する方法がある。このようにして
、代替ＯＲ並列ブランチにより共通変数への相反する設
定を行うことが可能となる。何故ならば、各プロセスは
変数設定のために必要とされる記憶スペースの専用コピ
ーを有するからである。ところで、この方法の難点はコ
ピーのための時間と空き領域を必要とし、さらに設定を
解除するために時間を要することである。しかも、この
ＯＲ並列プロセスは幾つかのステップの後で失敗に終わ
る場合が多く、従ってその生成のために費やされた時間
の多くが無駄になるという欠点がある。

その（−の用語及び表現については、追って本発明の好
適な実施例の詳細な説明の初めの個所で定義する。

発明の要約 本発明は、逐次演算の並列演算へのフレキシブルな転換
や、これらの処理モードを低いオーバーヘッドで計画的
に組合わせることが可能な論理プログラムの同時処理ま
たは並行処理の方法及びシステムを提供することを主目
的とする。

この課題は、１ハ７シエ・ウィンドウ”　（ｈａｓｈ−
ｗｒｎｄｏｔｓ）と呼ばれる巾広い設定リストを新規生
成のＯＲ並列プロセス専用に創り出す論理プログラム処
理方法を創案することにより解決される。

本発明は、少なくとも１個のプロセッサを用いて複数の
論理プログラムを並行処理−特にプロログ様言語で−す
るものであって−“親”と呼ばれる既存のプロセスによ
り並行−かつ遡及的−処理を行い、前記の親とＯＲ並列
関係に立つ“子゛と呼ばれる少なくとも一つのプロセス
を選択的ＯＲ並列ノードで生成する方法において、新規
生成の子プロセス専用に１ハツシユ・ウィンドウ”と呼
ばれる深設定リストを創り出して、子が分岐ＯＲ並列ブ
ランチを処理しつつ、子自体と親の双方に共通にアクセ
ス可能な“共通アクセス可能変数”と呼ばれる変数の設
定を行うようにした論理プログラム処理方法である。

このハッシェ・ウィンドウにおいて、前記プロセスはそ
れ自体と、前記プロセスが並列関係に立つ各プロセス、
例えば親プロセスとに共通的にアクセス可能な諸変数へ
の設定を行なう、これはプロセス生成におけるオーバー
へラドが極めて低いという利点がある。プロセスの生成
は共通変数の複写や無関係な設定の解除を必要としない
。この方法により得られる節約は、旧プロセスより既に
なされた作業に依存する。すなわち、分割の発生が遅い
ほど、節約の度合が大きい。この方法においては、ＯＲ
並列スプリットのコストは低く、履歴に依存しない。

本発明に従った好ましい方法によれば、親プロセスのＯ
Ｒ並列ノードは“ＯＲ分岐レベル１と呼ばれるラベルで
識別される。これは変数設定の範囲を指定する、すなわ
ち、各変数設定が有効な演算の部分を指定する基準フレ
ームが得られるという利点がある。

本発明に従った他の好ましい方法では、新規創出プロセ
ス、すなわち子プロセスは、その分岐元である親プロセ
スにおけるＯＲ並列ノードのＯＲ分岐レベルを示す“分
岐ラベル”と呼ばれるレベルへのアクセスを有する。こ
れは、新規生成プロセスが前記の基準フレームでみて親
の演算のどの部分に当たるかを知りうる利点がある。

本発明の他の好ましい方法によれば、旧プロセス、すな
わち所謂“親゛は、浅い設定を用いてそれ自体とＯＲ並
列プロセスとに共通的にアクセス可能な諸変数への設定
を実行し、これらに親プロセスにおける最も若い既存の
ＯＲ並列ノードのＯＲ分岐レベルを示す“設定ラベル”
と呼ばれるラベルのｅＪ識づけを行なう、浅い設定の利
点は、深い設定のリストを探す必要がないので諸変数へ
の迅速なアクセスが得られることである。設定ラベルに
より各設定の範囲の識別が可能となる。

本発明の他の好ましい方法では、−プロセスにおいて何
れかの時点で存在するＯＲ並列ノードのＯＲ分岐レベル
は、前記ノードの創出時点までに順序付けされたシーケ
ンスを形成する。これは、１プロセスの演算の一部が他
のプロセスの演算に含まれているかどうかのテストを容
易にする利点がある。

本発明の４ｈの好ましい方法では、分岐プロセスは前記
の分岐ラベルを前記設定ラベルと比較して、設定が分岐
前または分岐後に旧プロセスの目的により行われたもの
かどうが、従ってラベル付けされた設定が旧プロセスの
みならず分岐プロセスにも有効かどうかを判断する。こ
の方法の利点は、親プロセスにはあまりオーバーヘッド
を課することなく、すべてのＯＲ並列ノードにおいて遡
及的にＯＲ並列プロセスを創り出せることにある。親プ
ロセスでは、ＯＲ並列ノードは現在のＯＲ分岐レベルを
増やすだけで生成される。すなわち、オーバーヘッドは
微小である。しかし、これによりこれらのすべてのポイ
ントでＯＲ並列プロセスは遡及的に追加することが可能
となり、従って並列プロセッサ・システムの適合ローデ
ィングを確実に行なうことができる。親プロセスは直接
オーバーヘッドが低いだけでなく、間接オーバーヘッド
が皆無なので、深い設定を用いることを要しない。

また、前記の課題は、複合コールの独立サブコールのＡ
ＮＤ並列実行の結果を増分ごとに組合わせる論理プログ
ラム並行処理の方法により解決される。これは、複合コ
ールへの解の対を可及的速やかに形成しうる利点がある
。

本発明に従った他の好ましい方法によれば、前記の組合
わせ解は、前記のサブコールの解のポインタを含む“ジ
ョイン・セル”と呼ばれる構造体として形成、表示され
る。これは、複写を必要としないので、各対を掻めて低
コスト−時間とメモリでみて−で形成しうる利点を有す
る。これは、分散メモリの場合に特に有利である。何故
ならば、他のプロセッサのメモリを呼出すことなしにベ
アリングを行うことができるからである。

本発明に従った特に好ましい方法は、すべての実行モー
ド、すなわち逐次、ＯＲ並列、及び／又はＡＮＤ並列の
各モードを選択的に組合わせたものである。これは、本
発明の方法を実行するシステムにおいて、並列プロセス
の量を利用可能な資源に適応させることが可能となる。

システムが飽和状態にない場合には、ＯＲ並列ならびに
ＡＮＤ並列処理の有効利用により更に多くの並列プロセ
スを創出することができる。他方、システムが飽和状態
にある場合には、公知の既に開発されているの逐次プロ
ログ実行方式と比べて殆ど追加のオーバーへノドなしに
、極めて効率的な逐次処理が可能である。

本発明の他の好ましい方法によれば、ＡＮＤ並列処理へ
の逆戻り（バックトランキング）を行うことが可能であ
る。すなわち、まず右側ブランチと呼ばれる一方のＡＮ
Ｄ並列ブランチへの逆戻りを行い、次いで、該右側ブラ
ンチのすべての解が見い出された後、左側ブランチと呼
ばれる他方ブランチへの逆戻りを行う。これは、従来技
術による逐次プロログ処理方式と矛盾しない処理を行え
る利点がある。

本発明の他の好ましい方法では、右側ブランチへの逆戻
り解は浅い設定からい設定へ転換され、そのまま保存さ
れて、追って演算される左側前とペアに組み合わされる
。これは、最大限度の非同期演算を確実にするもので、
これにより全ての解が可及的速やかに演算されるという
利点がある。

本発明の他の好ましい方法によれば、右側のすべての解
が逆戻しされた後、この逆戻しされた右側の解を追って
演算される左側の解と対にする際に、その再演算がなさ
れる。これは、極めて簡単かつスペース効率的で、しか
も従来の逐次プロログ処理方式に高度に合致した処理が
可能となる利点を有する。更にまた、深い設定のリスト
のサーチを必要としない利点を有する。

本発明の他の好ましい方法では、逆戻し解は動的プログ
ラミングにより、即ち解の保存復元により再演算される
。これは、基本的再計算方式の簡易性と深い設定の回避
という長所を残しつつ、冗長な再計算を回避しうる利点
を有する。また、再計算の都度保存される右側解の一形
態を提供してクロスプロダクトの増分形成を軽減すると
いう利点がある。

本発明の他の好ましい方法によれば、−または複数の右
側解の再計算を必要とする左側前は、全ての右側解が次
回に逆戻しされる時までいかなる右側解とも対にされな
い。これは、再計算の際に、どの・右側解を左側前とベ
アに組合わせる必要があるか、またどれがすでに再計算
されていて改めて再計算の必要がないか等の追跡を回避
することにより、クロスプロダクトの増分構成を簡易化
する効果がある。これは、再計算に動的プログラミング
を用いない場合に特に大きな意義を有する。

本発明の（ｔの好ましい方法によれば、プロセスの創造
は飽和状態にないプロセッサにおいてのみ行われる。こ
れは、並列プロセッサシステムへの過負荷を回避する利
点があるす並行処理のオーバーヘンドープロセス管理と
、深設定リストの生成、及び深設定リストのサーチ−は
実際に並行の実行がある場合にのみ必要である。ＯＲノ
ードとＡＮＤノードの双方を遡及的に並列化できるため
、このような特殊化により並行処理の機会が損なわれる
ことはない。この簡単に得られる遡及的並列化と、不飽
和プロセッサのみにおける並列化により、プロセッサが
最適に実現しうる限りの量の並列プロセッサの創出が可
能となる。

本発明のイｔの目的と利点は、添付図面を参照した本発
明の好適な実施例についての以下の詳細な説明から明ら
かになるであろう。

〔好適な実施例の詳細な説明〕

本発明のよりよい理解のため、本発明に従った論理プロ
グラム処理の方法に関して使用する言語及び述語の主な
タイプについて簡易な説明を記載する。

この発明の演算方法またはシステムのユーザー言語は修
正プロログである。プロログ・プログラムは二つのタイ
プのモジュールに区分される。すなわち、逐次モジュー
ルと並列モジュールである。

逐次モジュールはユーザー・インタフェースと他の入出
力を含み、これらは通常のプロログで書かれる。これら
は、その述１吾の一つを”ｂａｇｏｆ”、　”５ｅｔｏ
ｆ”、または”ｏｎｅｏｆ”の述語を介して呼出すこと
により並列モジュールを呼出すことができる。並列モジ
ュールの言語には、”ｃｕｔｓ’、”ａｓｓｅｒｔｓ’
又は”　ｒｅ　Ｌｒａｃ　ｔｓ″はなく、Ｉｌｏもない
。

ＯＲ並列処理 並行モジュールにおける各述語の定義は、本発明に従っ
て処理を行う場合−属性の宣言が先行する。属性には次
の三種がある。

解： 述語すべての解または単一の解が計算される。

この概念は通常のプロログのｃｕｔ’に代わるものであ
る。

節： この述語の節はプログラムの本文の順序で処理（順序づ
け）しなければならない場合と、順序に制限のない（非
順序づけ）の場合がある。

実行： この属性は述語を実行する方法の勧告である。

“イーガー（ｅａｇｅｒ）”実ｊテモードでは、この述
語のすべての節は同時処理、すなわち並列処理を意図し
ており、“レイジー（ｌａｚｙ）”実行モードでは、解
の生成は逆戻り法（バンクトラッキング）により一度に
一つづつ行う。

ＡＮＤ並列処理 ＡＮＤ並列処理は、プログラマ−により明確に制御され
る。二つのコール間のコンマは逐次処理の実施であり、
ハフシュ（＃）はＡＮＤ並列処理の実施である。

フレーム編成 以下に論理プログラム処理の方法に使用するフレーム編
成について説明する。

フレームの一種に起動レコードがある。コールの各呼出
について、起動レコードが作られる。その主な構成要素
は呼び出されたコールのすべてのローカル変数について
のスロットである。これらのスロットには、変数の設定
または変数が設定されていない旨のマークを含む。

そのタイプのフレーム、例えばハフシュ・ウィンドウ、
ジョイン・セル等については、追って説明する。

ＯＲ並列処理 ＯＲ並列処理について以下説明する。

１プロセツサの場合： まず、１プロセツサしがない場合の処理の方法を説明す
る。

各プロセッサは“主ブランチ”と呼ばれるプロセスを処
理する。最初のコールの呼び出しの際に作成された起動
レコードを実行時間スタックに配分する。次のコールの
呼び出し時に、別の起動レコードを実行時間スタックに
入れる。統一化がら生じた変数の設定を起動レコードの
スロットに記録する。生成者の起動レコードのスロット
における記録設定をい設定と呼ぶ、設定された全ての変
数のアドレスをトレールスタック（ｔｒａｔｌ　５ｔａ
ｃｋ）に記録する。

呼び出された述語が多数の単一化可能な節を有し、かつ
述語の実行モードが“レイジー”の場合には、該主ブラ
ンチにより直ちに実行される最初のものを除いて、これ
らの節を全てリストしている実行時間スタックに選択ポ
イントを入れる。述語が“レイジー”でなく“イーガー
”の場合には、選択ポイントの代わりに分岐ポイントを
用いる。

これは同様な構成であるが、それはリストされている節
の並列処理を可能とする。分岐ポイントを実行時間スタ
ックに入れる都度、プロセスの現在のＯＲ分岐レベルが
その分拡張される。ＯＲ分岐レベル生成の際は、該レベ
ルを一定の値、例えば０に初期化する。各設定には、該
設定を行った時現在のＯＲ分岐レベルのタグを付する。

あるコールについて単一化可能な節が見当たらない場合
には、最終の選択ポイントまたは分岐ポイントまでの全
ての起動レコードを、まだ試みられていない代替のもの
と共に実行時間スタックから削除し、この起動記録が削
除されたコールによってなされたすべての設定は、トレ
ールスタックを用いて“未設定”にリセットする。この
操作を逆戻しくバックトランキング）という。次の未試
みの代替節を呼び出し、その起動記録は前記のフリーに
なったスタックのスペースに配分する。

変数に夫々の設定コールのＯＲ分岐レベルのタグを付す
る場合を除き、従来の逐次プロログ処理に比較して、追
加のオーバーヘッドを要しない。

プロセッサ多数の場合 プログラム処理に多数のプロセッサを利用できる場合に
ついて、第１図により本発明の詳細な説明する。

第１図は“ＯＲ並列チルドレン゛と呼ばれる二つの分割
されたプロセスを有している主ブランチを示す。各プロ
セスのコールは垂直に配列されている。各コールのそれ
ぞれの番号はそのＯＲ分岐レベルを示すや分割プロセス
のハツシュ・ウィンドウは°Ｈ”と、更に垂直な２本の
線が付されている。これらは、夫々が属するプロセスの
右側に配され、水平の線でそれに接続されている。

主ブランチが多数の単一化可能の節を有する“イーガー
”と宣言された述語に到達し、利用可能な遊びプロセッ
サが十分にある場合には、最初の節を除いて各プロセッ
サに一つの節が与えられる。最初の節は元プロセッサに
止まる。新プロセッサは新たな主ブランチ、即ち、ＯＲ
並列チルドレンを起動する。

ＯＲ並列チルドレンが述語の一方の節についての作業を
開始すると、それらは元の主ブランチの諸変数を矛盾す
る数値に設定する場合がある。従って、チルドレンはこ
れらの変数を設定することを許されない、つまり、浅い
設定を行うことを許されない、寧ろ、それらはこれらの
変数の専用深設定リスト中で設定しなければならない、
これらの新プロセスは夫々“ハツシュ・ウィンドウ”と
呼ばれる深設定リストを有する。ハツシュ・ウィンドウ
は設定変数のアドレスを配置してその局所的数値を計算
する。各新プロセスは前述の作業を開始する。

新ブランチにより生成された変数の呼び出しは、浅い設
定が用いられるため直接的である。新ブランチ外の変数
の呼び出しは、もはや直接の１ステップ操作ではない。

寧ろ、変数の元の位置をチェックして該変数が主ブラン
チ中の先祖により設定されたものかどうかを調べなけれ
ばならない。この場合、この設定は有効である。変数が
未設定の場合には、子のハツシュ・ウィンドウを呼び出
して該変数がＯＲ並列チャイルド、即ち現コール前の分
割後の新設主ブランチのコールによって設定されたもの
かどうかをチェックする。ハツシュ・ウィンドウに記載
がない場合には、該変数は未設定である。

ＯＲ並列述語の一つの節は元ブロセフサにより処理され
、共通先祖の変数については浅い設定を用いる。他のプ
ロセッサにおけるＯＲ並列子はこれらの設定を無視しな
ければならない、これは各ＯＲ分岐レベルを比較するこ
とにより達せられる。

現ブランチ外の先祖で発見された設定は、アクセスする
子孫が設定コール以後に分離したものである場合に限り
有効である。

主ブランチから子が分離したポイント識別のため、第２
図に示すように、子は例えばそのハツシュ・ウィンドウ
中に子が分離した親のＯＲ分岐レベルへのアクセスを有
する。

第２図の主ブランチでは、四つの起動レコードが夫々の
ＯＲ分岐レベルと共に示されており、レベル１の第２の
ものは単一化可能な節を一つのみ有する述語への呼び出
し、即ち“レイジー”モードのものである。このコール
は第１コールの変敗Ｘを“ａ″に設定している。この設
定はそのＯＲ分岐レベル“１”を付されている。一つの
子プロセスはレベル０以後に分離し、他のものはレベル
１以後に分離している。前者については、主ブランチの
レベル１の段階で“１”とタグ付けされた設定がなされ
る以前のレベル０以後の段階でプロセスが派生している
ので、Ｘは未設定である。レベル１以後に分離した子の
場合は、プロセスがレベル１の設定後に分離しているの
で、変数は“ａ”に設定されてい′る。

子が親の実行時間スタックの設定変数にアクセスする場
合には、設定するコールのＯＲ分岐レベルと該設定のタ
グをハツシュ・ウィンドウの分離レベルと比較する。設
定レベルが分離段階のものより高くない場合に限り、設
定は有効である。

変数が自己のレベルで設定される一生成者により又は以
後のコールにより次のＯＲ並列ノード以前に一場合には
、設定は常に有効である。この場合には、ハツシュ・ウ
ィンドウのチェックを要しない。

入子式ＯＲ並列処理 第３図は、二つのプロセスが同じ主ブランチから分離し
た例を示す、以下、第３図により、１プロセスが既に分
離している他のプロセスから分離して生成した入子式Ｏ
Ｒ分岐レベルについて説明する。第３図は、レベル０以
後に主ブランチから分離した第１の子プロセスと、この
第１の子のレベル２以後に該第１の子から分離した第２
の子を示す。

第３図から分かるように、分離した子から、更に子が分
離した場合、それらもまた専用のハツシュ・ウィンドウ
を必要とする。第３図の左側の主ブランチは、図示しな
い他のプロセスから分離したものである。従って、この
主フ゛ランチはそれ自体のハツシュ・ウィンドウＨｏを
有するからである。第３図の全てのハツシュ・ウィンド
ウは全て、親プロセスのハフシュ・ウィンドウを示すよ
うにチェーン接続されている。これにより、ハツシュ・
ウィンドウのトリーが生じる。現主ブランチで生成され
ておらず、しかもその発生元である主ブランチの先祖に
より設定されていない変数にアクセスする場合、該変数
の生成時に現存していた設定又はハツシュ・ウィンドウ
が見つかるまで、チェーンの全てのハツシュ・ウィンド
ウを探索しなければならない。

第３図の場合において、第２の子が主ブランチのレベル
１により設定された変数Ｘにアクセスするときは、該変
数は“ｌ”のタグを有しているので、第２の子はその専
用ハツシュ・ウィンドウである現ハツシュ・ウィンドウ
Ｈ２から始まるハツシュ・ウィンドウのチェーンを追跡
して、変数Ｘの設定がなされた時点現在のハフシュ・ウ
ィンドウを見つけなければならない。この場合、それは
ハツシュ・ウィンドウＨｏである。該第２の子によりそ
の直前に探知されたハフシュ・ウィンドウＨ１では、そ
れ自体の分離レベル−この場合“０以後”−が記録され
る。第１の子のハフシュ・ウィンドウＨ１におけるレベ
ル番号“Ｏ以後”は、第１の子が前記の変数Ｘの設定が
主ブランチのレベル１のコールによりなされる以前に主
ブランチから分離したことを示しており、従って該変数
は第１の子ならびに第２の子については未設定であるこ
とが分かる。一般に、手続は次のようになる。

変数が浅く設定されている場合には、派生した子の更に
子は、叔父の設定値と祖父の設定値とは区別しなければ
ならない。それらの子はそれぞれの現在のハツシュ・ウ
ィンドウを用いて該当する分離レベルを見つけることは
できない。何故ならば、第３図に示されるように、これ
らのウィンドウは最後の分離における父のレベルを含ん
でいるにすぎないからである。それらの子は、そのハフ
シュ・ウィンドウ・チェーンを遡って当該設定がなされ
た時現在のハフシュ・ウィンドウ、ずなわち、当該設定
が記録されている逐次ブランチに属するハフシュ・ウィ
ンドウをつきとめなければならない。チェーン中におい
てこれの直前に探知されたハツシュ・ウィンドウは、現
ブランチの祖先が当該設定がなされたブランチから分離
した時に創り出されたものである。それには、該当する
分離レベルが記載されている。

設定値が実行記録でなく、ハツシュ・ウィンドウにおい
て見いだされる場合、これは言うまでもなく、該設定が
なされた時現在のハツシュ・ウィンドウである。

同し逐次ブランチのＯＲ分岐レベルのみが比較される。

子のハフシュ・ウィンドウにおけるＯＲ分岐レベルはそ
の親のＯＲ分岐レベルである。従って、これらの番号の
みが１ブランチ内で一意のものたるべきであり、１ブラ
ンチの芥子はそのＯＲ分岐レベルを再初期化することが
できる。

ＯＲ分岐レベルに配分されたピントの数があふれる場合
、例えば８ビツトのタグに対して２５６づつの潜在的Ｏ
Ｒ並列ノードがある場合には、全てのブランチがハツシ
ュ・ウィンドウを受けねばならない。これは、主ブラン
チも新しいハフシュ・ウィンドウを得て、その現在のレ
ベルの初期値を設定し、このハフシュ・ウィンドウより
古い変数への浅い設定を行うことを許されないというこ
とであるや 遡及的ＯＲ並列処理 以上説明した論理プログラム処理の方法によれば、逐次
計算を遡及的に並列計算に転換することも極めて低コス
トで簡単に行える。主ブランチについては、それがＯＲ
並列チルドレンを有する場合も、有しない場合も、何ら
の差異はない。従って、他のプロセッサに新規のＯＲ並
列処理プロセスを創設する場合も、他のプロセスから分
離するブランチに何らの変更を加える必要もない。

ＡＮＤ並列処理 次に本発明のプログラム処理の方法に従ったＡＮＤ並列
処理について説明する。ＡＮＤ並列処理は独立コールに
ついてのみ遂行される。書込オペレーションが読取りオ
ペレーシヨンを含む場合において、二つ以上のコールの
夫々が、他方が書込む変数を読み取れないとき、これら
のコールは独立コールである。従って、同期の問題はな
い。

基本的ＡＮＤ並列処理 本発明に従ったＡＮＤ並列処理の主な原理を説明するた
め、まず、その実行が分岐ポイントの生成を生じない二
つのコールの基本的ＡＮＤ並列処理について説明する。

ＯＲ並列処理の場合と対照的に、矛盾する設定が生じな
いので、ＡＮＤ並列コールは、別個のハツシュ・ウィン
ドウを設けることなくそのまま並行して開始することが
できる。左側のコールはＯＲ並列ブランチと同じメカニ
ズムを使う他の遊びプロセッサに右側コールがオファ−
される間、同じプロセッサにとどまっている。

右側コールが左側コールの完了時に放棄されていない場
合には、同じプロセッサで右側のコールを処理する。こ
の−倒プロセッサの場合、本発明の方法は通常の逐次プ
ロログの場合と同様に作用する。

左側コールの計算中に右側コールのプロセッサが利用で
きるときには、真のＡＮＤ並列処理が達せられる。遠隔
プロセスのハフシュ・ウィンドウが必要でなくとも、キ
ャッシュ用に一つを用いることができる。最後に、ＯＲ
並列ブランチのジョイニングを行う。時間的に速い方は
、他方の完了を持たねばならない。

一個の論理和並行ブランチがある場合のＡＮＤ並列処理 ＡＮＤ並列ブづンチのうちの一つのみが分岐点を有する
場合には、ＯＲ並列処理の通常のメカニズムを使用し、
分岐したすべての子はハツシュ・ウィンドウを取得する
。これらのブランチの一つがＡＮＤの終点に達した時に
はいつでも、他側がその解を出すまで待たねばならない
。解が存在する場合には、並列ブランチはそのまま処理
を続行する。

この非ＯＲ並列ブランチはＯＲ並列ブランチの夫々によ
り共有される。非ＯＲ並列ブランチは分岐点は含まない
ので、ＯＲ分岐レベルが増大することはない、すべての
設定は、分岐時点現在のレベルでタグ付けされる。従っ
て、これらの設定は、ＯＲ並列ブランチのすべての子に
ついて可視である。

ＯＲ並列処理を伴ったＡＮＤ並列処理処理ジョイン・セ
ル ＡＮＤ並列スプリントの両側が分岐点を含む場合には、
両方のブランチについて多数の解が同時に存在しうる。

この場合、左右両側の解のセントのクロスプロダクトを
形成しなければならない。

クロスプロダクトの一つの構成要素は、左側の１プロセ
スと右側の１プロセスを祖先とするプロセスである。こ
れらの祖先の設定値へのアクセスは、ハツシュ・ウィン
ドウ方式の拡張、部ち、第４図に示すシライン・セルに
より実現される。

第４図において、単純なブロックはハツシュ・ウィンド
ウを示し、夫々実行されたコールの名を付されている。

第４図の例では、コールｐの後にＡＮＤ並列コール１及
びｒが呼び出され、１は代わってＯＲ並列コールＸ、、
Ｚ２を呼び出し、「はＯＲ並列コールｒ工、ｒ２を呼び
出している。

図面では、ハフシュ・ウィンドウの生成Ｓ−生ｖタコー
ルのみを示しである。水平２本線を付したブロックはジ
ョイン・セルである。

プロセスはハツシュ・ウィンドウで識別でき、各プロセ
スは正確に１個の現在のハツシュ・ウィンドウを有して
いる。従って、二つのプロセスをベアとなしうるために
は、ジョイン・セルは３ケのポインタを有する。すなわ
ち、左側解のハツシュ・ウィンドウを示す１ポインタと
、右側間のハツシュ・ウィンドウを示す「ポインタと、
第３のポインタとして、ＡＮＤ並列分割時点現在のハ。

シュ・ウィンドウを示す最終共通ハツシュ・ウィンドウ
・ポインタである。ＡＮＤ並列ジョイン後のコールに対
する変数の状況をみると次の如くである。“探索終了時
変数”は、対象の非局所的変数の定義コールに関連する
ハツシュ・ウィンドウのアドレスに初期設定される。ハ
ツシュ・ウィンドウの直線チェーンを通例のようにして
ジョイン・セルのところまで引く。ここでブランチが必
要である。ジョイン・セルの１ポインタと探索終了時変
数の現在数値をスタックに入れる。この探索終了時変数
の数値をジョイン・セルの最後の共通ハフシュ・ウィン
ドウにセットし、ジョイン・セルのｒポインタを引く。

この右側ブランチのサーチが好結果を得なかった場合、
すなわち変数の設定発見前に探索終了時数値に達した場
合には、最後の１ポインタはホップアップしてサーチを
再開し、探索終了時数値をスタックから取り出す、スタ
ックが空きになる場合は、変数が未設定ということにな
る。

第５図は、次のプログラム実行後の入子式０Ｒ−ＡＮＤ
並列処理におけるフレーム・レイアウトを示す。

ｐニー＃ｊ！ｒ、ｓ　　ｒ！！：　　”　　ｌ：　　、
。

ｒＩ！Ｉｌ・・　Ｉｌ：　−、・ ｒ　：　−ｒｊ！＃ｒｒ、　　ｒｒ：　＝°　３　：　
−・・「　：　−□　　　　　　　　　　ｒｒ：　　−
、、ｓ：　　−り節ｐでは、コールｌ、ｒはＡＮＤ並列
関係にある。！及び「はＯＲ並行述語であり、夫々二つ
の解を有する。説明の便宜上、これらはハフシュ・ウィ
ンドウと共に示しである。ｒブランチの一つには、ＡＮ
ＤｌｏＲが並列入子式、即ちｒがｒＩ！、ｒｒを呼び出
した状態になっている。これらはＡＮＤ並列コールであ
り、共にＡＮＤ並列述語である。

ＯＲ並列ブランチも、図解のためハフシュ・ウィンドウ
を付して示しである。最後のコールＳはＯＲ並列である
。その呼びについては、ブランチの一つ（ハツシュ・ウ
ィンドウを付したちの）を第５図に示した。ｐに関連す
るハフシュ・ウィンドウは、グローバルな連結に使用す
るもの、すなわち、ｐ以前の最終のＯＲ並列スプリント
のものを示す。ハフシュ・ウィンドウは、′Ｈ″のマー
クを付しである。ジョイン・セルには平行二重線と最終
の共通ハツシュ・ウィンドウのマークを付した。

ＯＲ分岐レベル 独立のＡＮＤ並列処理の二つのブランチは同一の計算に
居するもので、従って識別を要しない。

すなわち、共に同じＯＲ分岐レベルを用いうる。

両ブランチが特別な警告なしにＯＲ並列になったときは
、二つのプロセス、二つの主ブランチとなり、ＡＮＤ並
列分割前に共通のパートにこれを書込むことができる。

これらは同じＯＲ分岐レベルを使用するので、共通パー
トにおける夫々の設定値は識別できない。それらの設定
値を識別可能にするためには、右側ブランチにおける最
初のＯＲ並列スプリントのすべての節を深設定を用いて
実行−子プロセスによると親プロセスによるとを問わす
−しなければならない。

ジョイン・セルは、クロスプロダクトのメンバーで両方
のＡＮＤブランチへの解がハフシュ・ウィンドウを含む
ものについてのみ必要である。左側解でハツシュ・ウィ
ンドウのないものが一つあってもよい、この場合には、
ジョイン・セルは、その左側解を含むクロスプロダクト
のメンバーについては必要でない。

第６図は二つのブランチが分離されてＯＲ並列となって
いる場合のＡＮＤ並列の実行状況を示す。

これは、次のプログラムの実行後のフレームのレイアウ
トを示したものである。主コールｚ＋、、ｌ。

Ｉ！ｅ’、ｒｒ’　の起動レコードは示されていない。

？−ｃ＋、−、ｌ　’／／ｒ’＋ｓ。

１’ニー１．ｌ　Ａ’、　　ｌ　ｌ’：　−１＋　、　
　　ｅ　７！’：　−１２ｒニーｒ、ｒｒ、　　ｒｒ’
ニーｒ１．　　　ｒｒ’ニーｒ２コールＣの後、ＡＮＤ
並列コールＲ”、ｒ’　が呼び出されている。ｌ゛　は
全での解に共通の部分ｌと、ＯＲ並列独立パートｌ１１
，１２からなる。ｒ”についても同様である。太線は起
動レコードと制御流れを示す、起動レコードは、右側に
コールの名称、左側にコールのレベル番号を示しいる。

各プロセスのコールは垂直に整列されている。マルで囲
んだものは、生成する四つのプロセス１１，１２，２１
゜２２ヲ示す、“接地”のシンボルはプロセス終了を示
す、細線はハフシュ・ウィンドウで、′Ｈ”と二重垂直
線のマークを付している。ジョイン・セルは二重水平線
とそれらが代表する解のペアを付した。各ジョイン・セ
ルの“最終共通ハフシュ・ウィンドウ”はＣを付された
ものである。水平ラインは各プロセスと夫々のハツシュ
・ウィンドウを結んでいる。ポインタの“ｎのあとの”
タグは“世代ｎのあとの分離”を示す。

ＡＮＤ並列コールとその先行部へのＳ及びその子孫から
の変数アクセスは上記の通り行われる。

ただし、ジョイン・セル（プロセス２Ｌ　２２）が存在
する場合には、′ハツシュ・ウィンドウ・チェーンを追
求している際にジョイン・セルに遭遇した場合には、右
側のブランチを先ず調査し、最終共通ハツシュ・ウィン
ドウを発見するまでこれを続ける。次いで、左側ブラン
チを追跡し、スプリント以遠までこれを続ける。”「に
よりなされた非局所的設定は、ｌ以前かつＣのハフシュ
・ウィンドウを含むＣまでの起動レコードに記載されて
いる。これらは、ｌの設定と識別不能であり、従って該
設定と共に読まれることになる。ｒ自体の設定はレベル
ｎのものであ゛す、従って常に有効である。最左側のジ
ョイン・セルの右側のポインタにおけるＯの後の”タグ
は、ｒｌおよびその関連ハツシュ・ウィンドウにおいて
レベル１のプロセス１１のコールＳによりなされた設定
をプロセス２１が無視するに際して必要である。このこ
とは、「２においてプロセス１２によりなされた設定を
プロセス２２が無視する際にも同様である。

第６図の点線で示したジョイン・セルは、概念上必要な
ものにすぎず、ここでは理解の便宜上水した。実際には
、それらは存在しない、これらの場合、ジョイン・セル
（プロセス１１．１２）がないときは、２１の設定はレ
ベルｎ＋１２のタグを付して示されるが、最初の右側ス
プリントのハフシュ・ウィンドウが通常の“レベルｎｌ
＆スプリント”のタグを含んでいる場合には、それらは
目に見えないものである０代わりに、第６図では、それ
らは並列ＡＮＤの右側の最初のＯＲ並列スプリントとし
て特に“☆”を付して示されている。そのようなポイン
タの付されたハツシュ・ウィンドウに遭遇した場合には
、次の二つのケースがある。

１、　それが示す親ハフシュ・ウィンドウは探索終了ポ
インタに均しいものである。すなわち、ジョイン・セル
の発見時に使用されるスタックの頂部の最終共通ハツシ
ュ・ウィンドウに相当する。この場合、ジョイン・セル
が存在し、従ってＮ、（プロセス２Ｌ　２２）を含むク
ロスプロダクトのメンバーではなかった。従って、左側
ブランチを通常の通り探索しなければならない。

２、　前記の二つのポインタは異なるものである。

つまり、ジョイン・セルは存在しないことになる。

これは、左側ブランチ７！１とペアに組まれた右側ブラ
ンチの最初の段階のことであるが、この場合、ハツシュ
・ウィンドウは不定のレベル以後に分割されたものとみ
なされた。従って、Ｃから１１の末端までの左側ブラン
チの全ての設定は有効である。左側のサーチは不要であ
る。

左右両側とも同じプロセッサでスタートする場合分岐ポ
イントが選択ポイントであるかの如く実行されることが
ありうるが、同様に並列ＡＮＤが逐次プロセスであるか
の如く実行されることができ、元プロセスが左側解を有
するＡＮＤジツインに到達した場合、右側がまだ放棄さ
れていない場合がありうる。そのような場合、元プロセ
ス処理がＡＮＤの右側と共に続けられることができる。

追加のハツシュ・ウィンドウを設ける必要はない。

しかし、ＯＲ分岐レベルは増やさなければならない、こ
のようにすれば、左側によりなされた設定は右側により
なされたものと識別することができる。この場合、プロ
セスはそれ自体が実行する右側の最初の潜在的ＯＲ並列
ノードの節に関して深設定を用いる必要はない。ＡＮＤ
コールは、最小数のハツシュ・ウィンドウを用いて実行
される。

真のＯＲ並列処理のみがハツシュ・ウィンドウを必要と
する。ＡＮＤコールが単一のプロセッサのみで実行され
る場合には、ハフシュ・ウィンドウの生成は全く行われ
ない。これについては、次の項で詳細に説明する。

第７図は次のプログラムのＡＮＤ並列コールにおける遡
及的並列処理の概略フレーム配置構成を示す。ここでも
、ハツシュ・ウィンドウや主コールの起動レコードは示
されていない。

’？’Ｃ＋　ｌ　’Ｉｒ’。

１’ニー　　１’、／７！’、　　ＩｌＡ’ニー　　１
１．　　　Ｊｆｆ’ニー　ｘ２ｒ　　ニー　　ｒ、ｒｒ
’、　ｒｒ’ニー　　ｒｌ！、　　　ｒｒ’ニー　　ｒ
２コールＣのあと、ＡＮＤ並列コールｌ”及びｒ゛が呼
び出される。ｌ′は全ての解に共通のバート！と、独立
パートの１！１及びＩ！２からなる。ｒ＋も同様である
。第７図は、ＡＮＤ並列コールが最初逐次実行される場
合を示す。利用できるプロセッサかないため、最初の解
ｊ！１、ｒ＋は逐次実行した。ＡＮＤコールの前に、Ａ
ＮＤの両側の共通の先行コールであるコールＣが存在し
た。同しプロセッサで左側についてもスタートし、追っ
て潜在的分岐ポイントを生成した後、最初の解１１を出
した。右側はまだ放棄されておらず、従って同しプロセ
ンサでこの処理を行うこととして、まず全ての右側解ｒ
に共通の計算を何か行い、次いで最初の解「１を出した
。常時浅い設定を適用した。

従って、ｃ、ｊ’、１１、ｒ、ｒｌの設定は夫々のレベ
ルの番号によってのみ識別可能であり、一部はＣの起動
レコードまたはハツシュ・ウィンドウにも見いでされた
。

、　その後、プロセッサが利用可能となったので、ＯＲ
並列のチルドレン１２、ｒ２を分離して他のプロセッサ
に割り当てた。

ＡＮＤのジョインで、１．、Ｉｔ２をｒｌと対にした。

クロスプロダクト後の変数の探索については、特別の注
意が必要である。１２、ｒ＋を含むクロスプロダクトの
メンバーの後身が変数の設定を探索する場合、１１によ
り行われた設定は、無視しなければならない。ジョイン
・セルのブランチ１２の調査については、１２はｌ！１
以前に主ブランチから分離したものであり、従って２．
とそのチルドレンの設定は無視されるので、特に危険は
ない、しかし、ブランチｒｌでは、後述のレベル番号の
追加使用を行わな（でも、１１の設定が視認できる。

最終共通ハツシュ・ウィンドウ・ポインタは、右側がス
タートするＯＲ分岐レベルにより増幅される。最終共通
ハツシュ・ウィンドウと関連する深設定レベルにおける
変数設定は、左側へはね戻るまでに、この段階で、又は
、以１多の段階（例えばｒ設定）で調べられる。これ以
前のレベルのもの（Ｖｌｌえば１１設定）は調べられな
い。

１１のマスキングは、１１を含んでいるクロスプロダク
トのメンバーに関してのみ必要である。

１１を含まないペアはジョイン・セルを全く必要としな
い。せいぜいＡＮＤ並列ブランチ（右側）がハツシュ・
ウィンドウを有するにすぎないからである。サーチはｒ
ｌ又はｒ２〜ｒ、　　ｊ７Ｉ、　　Ｉ！及びＣを介して
、これらを識別する必要なしに行われる。既に述べたよ
うに、ｒｌは同じプロセッサで１１の後で実行される場
合でも、ハツシュ・ウィンドウを必要としない。７！１
及び「１を含むクロスプロダクトのメンバーは同じプロ
セスで一段高いレベルで実行を続けることができる。

制御 次に、本発明に従った論理プログラムの処理方法の制御
について説明する。

ＯＲ並列処理 多数の節を有するイーガーな述語を呼び出す場合にはい
つでも、分岐点を設定する。多数の節ををするレイジー
な述語を呼び出すと、選択ポイントが生成される。この
結果、各分岐点に始まる枝を有する逐次プロセスのトリ
ーが生成する。第８図は、そのようなトリーの一例を示
し、Ｃは選択ポイント、Ｂは分岐点を示す。分岐点の最
左側の技は同じプロセッサに止まっている。

遡及的ＯＲ並列プロセスの生成 前述のように本発明の方法の極めて重要な特色は、逐次
計算を並行計算へ極めて低いコストで遡及的に転換しう
ろことである。プロセッサは飽和状態にならないかぎり
、タスクを要求する。不飽和プロセッサは、例えばネッ
トワークの潜在時間のため、待ち状態にある遊びプロセ
ッサである。

全てのプロセッサは、未処理の代替節に関して夫々の分
岐点のリストを有している。これらの−が選択されて遊
びプロセッサに与えられる。新規のプロセスを分離した
ブランチには、なんらの変更を要しない。このメカニズ
ムにより、システムが資源を提供する限り、多くのプロ
セスを発生させることが可能である。従って、並列処理
、例えばプロセス生成や深設定のオーバーヘッドは、並
行プロセスが実際にスタートした場合にのみ必要である
。

プロセスを生成するには、コールを現時点のノ１ッシェ
・ウィンドウのポインタと、親レベルの指示と共に伝達
することを要するだけである。更に共通変数を得るため
のプロセス間連絡であるオーバーヘッドは、変数の実際
使用の際にその要求のある場合に必要なだけである。従
って、生み出されたプロセスが例えば失敗に終わって早
々と終了していても、専用環境の創出や、これに対する
変数設定値の複写にあまり作業の無駄を生じることはな
い。他方、プロセスが古くなった場合には、更に多くの
共通変数を読み出して局部ハツシュ・ウィンドウに貯蔵
することができ、これによりプロセスの独立性を高める
ことができる。

逆戻り（バックトラッキング） プロセスが失敗の場合には、同プロセスにおける前段階
の選択ポイン１４たは分岐点に逆戻りする。もしこれが
選択ポイントの場合は、次の代選択を実行する。分岐点
の場合は、まだ放棄されていない次の選択が実行される
。未放棄の代替のものがない場合には、当該分岐ポイン
トのすべての子の終了を待った上で該分岐ポイントに戻
る。プロセスに選択ポイントまたは分岐ポイントがない
場合は、プロセスを終了させる。

探索トリー全体が確実に探索されるようにするため、す
べてのブランチは最終的には失敗して元へ戻るようにし
なければならない。これは、成果を収めたブランチはそ
の解を通報した後に失敗するようにさせることにより達
せられる。

ＡＮＤ並列処理 ＡＮＤ並列プロセスの生成は、ＯＲ並列プロセスの場合
と同じメカニズムを用いて行う。潜在的ＡＮＤ並列スプ
リントは、未処理の代替項を有する潜在ＯＲ並列分岐点
と同じリストに入れる。このようにして、ＡＮＤ並列プ
ロセスは、遊びプロセッサの要求によってのみ、かつ遡
及的に創出される。

右側解と左側解のクロスプロダクトは、解の到達時に増
分的に形成される。左側解が得られたときには、直ちに
既存のすべての右側解と対にする。

逆の場合も同様である。必要ならば、ジョイン・セルを
生成する。ジョイン・セルは、両側のＡＮＤブランチが
ハフシュ・ウィンドウを有する場合にのみ必要である。

これらの各ペアについては、プロセッサが利用可能であ
れば、又、可能になればプロセスをスタートさせる。遊
びプロセッサがない場合には、元プロセッサが各ペアご
とに順次実行する。

ＯＲ並列、ＡＮＤ並列、逐次処理の組合わせＡＮＤの右
側解がクロスプロダクトが計算される点であるジヨイン
トに到達する場合には、延長可能な分岐ポイントを創出
する。これの子孫は、前記右側解と現時点までに見出さ
れた各左側解く左側の計算結果のリストからのもの）と
の集合である。

第９〜１７図において、入子式ＡＮＤ１０Ｒ並列処理へ
の逆戻りについて説明する。これらの図面で“Ａ”はＡ
ＮＤ並列スプリットを示す。左側の解は小文字、例えば
ａ：のタグを付しである。右側解にはアラビア数字、例
えば１：のタグを付しである。Ｂ′は拡張可能な分岐ポ
イントを示し、その等価は未定である。逆戻り選択ポイ
ントはＣ゛のタグを付しである。括弧内の文字、例えば
右側の（ａ）はクロスプロダクトの当該メンバーについ
ての左１り解を示す。

第９図は各側の最初のブランチがジゴインに達して間も
なくのＡＮＤ並列処理を示す。第１０図は、追加の右側
解の到達が追加の拡張可能分岐ポイントの生成につなが
る状況を示す。ＡＮＤの左側の解がジョインに到達する
と、それまでに生成された全ての右側解の拡張可能分岐
ポイントは、１１１１ｉ！の追加の子孫で拡張される。

右側解の分岐ポイントと右側の結果のリスト中に見いだ
される。第１１図は、追加の左側解の到達が拡張可能分
岐ポイントの拡張につながる状況を示す。

拡張回部分岐ポイントに始まる全てのブランチが失敗す
ると、並列ＡＮＤへの逆戻りが必要となる。左側はなお
まだ解の計算が可能なので、逆戻りした右側解を以後の
左側解と対にする余地を見込まねばならない。

このための最新の逐次プロログ処理技術に即応した最も
簡単で最も空間効率的な方法は、右側の再計算を行うこ
とである。

ＡＮＤ並列並列ジンイン逆戻り 右側を左側の計算と非同期に繰り返し計算することによ
り、一般に、左側解を一部の右側解と、他の右側解との
場合よりも再計算１回分早く対にすることができる。し
かし、各左側解を単一の再計算による右側解のみと組み
合わせる場合には、右側解の再計算、即ち不変数の確認
は不必要である。このためには、最初の拡張可能分岐ポ
イント逆戻り時と右側の失敗後群計算した時点との間に
到達したすべての左側解を記載した２回目の左側計算結
果リストを加える。最初の結果リストを“現世代゛と呼
び、新しいものを“次世代°と呼ぶ。

第１２図では、最初の拡張可能分岐ポイントの逆戻りが
なされており、従って“次世代”の結果のリストが必要
な場合を示している。新しい左側解は、第１３図に示す
ように、分岐ポイントを拡張することなく、新世代に加
えられる。第１４図では、新しい右側解が現世代の各メ
ンバーについてｍ個の子との分岐ポイントを形成してい
る。

右側が失敗して論理積並行分岐ポイントへ逆戻りする場
合、３つのことが発生する。

−“現世代”のすべての左側ブランチがこれに原因して
失敗する。

−“次世代゛が“現世代”となる。

−右側が再計算される。

これは第１５図に示す。いま、サイクルが完了してスタ
ート時と同じように実行がなされ、例えば第１６図の状
態となる。

なお、まだ一つの問題がある。それは空き世代が禁じら
れていることである。右側解が拡張可焼な空き分岐ポイ
ントを形成する場合、まだ左側の解が出ていないため、
直ちには逆戻りできず、寧ろ分岐ポイントの拡張を待つ
ことになる。第１７図は拡張可能な空き分岐ポイントを
待たなければならない場合の例である。

失敗 方便１が失敗した場合、即ち逆戻りの結果、左側解の各
世代が出され、夫々が右側の全ての解とベアに組まれて
いる場合にのみ、左側はなお前回の選択ポイントまたは
並列ＡＮＤに先行する分岐ポイントへの逆戻りを続ける
。しかし、左側の逆戻りが並列ＡＮＤ以遠に及ばないう
ちに、右側も失敗してＡＮＤ分岐へ戻ってしまっている
。

全ての待機中の拡張可能な空き分岐ポイントが失敗を余
儀な（される場合、右側は結局失敗することになる。こ
れは、右側の結果のリストから発見可能である。

左側が一旦失敗すれば、右側解全てを再計算する４・要
はなくなる。必要なのは右側解が失敗することだけであ
る。従って、無用な作業量を減らすため何らかの方法を
加える。この方法は三つの形態をとりうる。

一選択ポインドを除去できる。

一未活動ブランチをスケジューラ−の注意対象から除け
る。

一活性ブランチを抹消できる。

右側の解がない場合に左側を失敗させるためには、この
ような方法を実行することも当然考えられてよい。

以上、好適な実施例について説明したが、添付請求範囲
を通説することなく種々の変更や改変をこれに加えうる
ちのである。

【図面の簡単な説明】

第１図は、プログラムのＯＲ並列処理を示す説明図、第
２図はＯＲ分岐レベルの使用を示す説明図、第３図は入
子構成のＯＲ分岐レベルの使用を示す説明図、第４図は
ジツイン・セルによるクロスプロダクトの形成状況を示
す説明図、第５図は入子式Ａ　Ｎ　Ｄｌｏ　Ｒ並列構成
を模式的に示す説明図、第６図はＯＲ並列系をＡＮＤ並
列系に入子式にした構成を示す説明図、第７図はＡＮＤ
並列コールにおける遡及的並列構成を示す説明図、第８
図はＯＲ並列構成と逆戻り法を組み合わせたサーチトリ
ー（木）を示す説明図、第９図は各側に第一の解がある
ＡＮＤ並列処理の実行例を示す説明図、第１０図は右側
に他の解があるＡＮＤ並列処理の実行例を示す説明図、
第１１図は左側に他の解があるＡＮＤ並列処理の実行例
を示す説明図、第１２図は逆戻しは次の世代を必要とす
るＡＮＤ並列処理の実行例を示す説明図、第１３図は左
側に次世代の解があるＡＮＤ並列処理の実行例を示す説
明図第１４図は右側の新しい解に現世代のものを用いて
いるＡＮＤ並列処理の実行例を示す説明図、第１５図は
右側が故障の場合のＡＮＤ並列処理の実行例を示す説明
図、第１６図は実行が開始時の状態のまま続いているＡ
ＮＤ並列処理の実行例を示す説明図、第１７図は待ちが
必要な状況であるＡＮＤ並列処理の実行例を示す説明図
である。 特許出願人　ユーロピアン・コンピューターインダスト
リー・リサーチ・ センター・ゲーエムベーハー （フォルシュンゲスツエントラム） 代理人　弁理士　　河　　野　　登　　人工　　５　　
図 シーケンシャル ブラント １：Ｂ＊ １８　　図 １：Ｂ＊ 第　９　図 一イーーへへへ Ｂ　　　　　　　　　　Ｂ 第　１０　図 王　１３　図 第　１４　図 失敗　　失敗

Claims (1)

1. 【特許請求の範囲】 １、少なくとも１個のプロセッサを用いて複数の論理プ
   ログラムを並行処理−特にプロログ（Ｐｒｏｌｏｇ）様
   言語で−するものであって、既存のプロセス（“親”）
   により若干の一可能な全ての−ＯＲ並列ノードにおいて
   前記親とＯＲ並列関係に立つ少なくとも一つのプロセス
   （“子”）を並行−かつ遡及的−処理により生成する方
   法において、 前記の新たに生成した子についてのみ深設 定リスト（“ハッシュ・ウィンドウ”）を創出して、子
   が分岐生成されたＯＲ並列ブランチを処理しつつ、それ
   自体と親の双方に共通にアクセス可能な変数（“共通ア
   クセス可能変数”）の設定を遂行し得るようにするステ
   ップを特徴とする論理プログラムを並行処理する方法。 ２、親における潜在的ＯＲ並列ノードにラベル（“ＯＲ
   分岐レベル”）を付するステップを特徴とする特許請求
   の範囲第１項に記載の方法。 ３、分岐した子がその分岐元である親のＯＲ並列ノード
   のＯＲ分岐レベル（“分岐ラベル”）へのアクセスを有
   することを特徴とする特許請求の範囲第１項又は第２項
   に記載の方法。 ４、親が浅設定方式を用いて共通アクセス可能な変数を
   設定し、これらの変数に親の最も若いＯＲ並列ノードの
   ＯＲ分岐レベルであるラベル（“設定ラベル”）を付す
   ることを特徴とする特許請求の範囲第１〜３項のいずれ
   かに記載の方法。 ５、各プロセスに任意の時点において存在する潜在的Ｏ
   Ｒ並列ノードのＯＲ分岐レベルが前記ＯＲ並列ノードが
   生成された時点までは順番づけられたシーケンスを形成
   することを特徴とする特許請求の範囲第２〜４項のいず
   れかに記載の方法。 ６、前記の子が前記の分岐ラベルを前記の設定ラベルと
   比較して、設定が分岐前又は分岐後のコールにより遂行
   されるか否か、従ってラベル付けされた設定が前記の子
   に関して有効か否かを確認することを特徴とする特許請
   求の範囲第３〜５項のいずれかに記載の方法。 ７、少なくとも１個のプロセッサを用いて複数の論理プ
   ログラムを並行処理−特にプロログ様言語で一するもの
   であって、既存のプロセス（“親”）により該親と独立
   のＡＮＤ並列関係に立つ少なくとも一つのプロセス（“
   子”）を並行−かつ遡及的−処理により生成する方法に
   おいて、 ＡＮＤ並列ブランチの結果のクロスプロダ クトが増加的に形成されることを特徴とする論理プログ
   ラムを並行処理する方法。 ８、前記のクロスプロダクトのメンバーがＡＮＤ並列ブ
   ランチの解のポインタを含む構造体（“ジョイン・セル
   ”）として形成されることを特徴とする特許請求の範囲
   第７項記載の方法。 ９、少なくとも一つの他のプロセスに対して独立のＡＮ
   Ｄ関係に立つプロセスが前記プロセスとＯＲ並列関係に
   立つ第三のプロセスの親であり得ることを特徴とする特
   許請求の範囲第１〜８項のいずれかに記載の方法。 １０、少なくとも一つの他のプロセスに対してＯＲ並列
   関係に立つプロセスが前記プロセスと独立のＡＮＤ関係
   に立つ第三のプロセスの親であり得ることを特徴とする
   特許請求の範囲第１〜９項のいずれかに記載の方法。 １１、逐次処理、ＯＲ並列処理、及び／又はＡＮＤ並列
   処理の選択的組合わせを特徴とする特許請求の範囲第１
   〜１０項のいずれかに記載の方法。 １２、一方のＡＮＤ並列ブランチ−右側−への逆戻しを
   まず行い、次いで前記右側ブランチへのすべての解が見
   いだされた後に他方のブランチ−左側−ヘの逆戻しを行
   うことにより、並列ＡＮＤへの逆戻しを行うステップを
   特徴とする特許請求の範囲第７〜１１項のいずれかに記
   載の方法。 １３、右側の逆戻しにより潜在的に失われた解（“ 戻し解”）をい設定からい設定に 転換して存することにより、それらを追っ て計算される左側の解と対にすることを特徴とする特許
   請求の範囲第１２項に記載の方法。 １４、右側の全ての解を逆戻しした後、この逆戻しの右
   側の解を追って計算される左側の解と対にする際に再計
   算することを特徴とする特許請求の範囲第１２項に記載
   の方法。 １５、再計算を動的プログラミングにより行うことを特
   徴とする特許請求の範囲第１４項に記載の方法。 １６、右側の一または二以上の解の再計算を必要とする
   左側の解は、右側のすべての解を次回に逆戻しするまで
   右側のいかなる解とも対にしないことを特徴とする特許
   請求の範囲第１３〜１５項のいずれかに記載の方法。 １７、前記のＯＲ及び／又はＡＮＤ並列プロセスのみを
   未飽和プロセッサで生成することを特徴とする特許請求
   の範囲第１〜１６項のいずれかに記載の方法。 １８、少なくとも１個のプロセッサを備えて複数の論理
   プログラム−特にプロログ様言語の−を同時また並行処
   理可能であり、既存のプロセス（“親”）により若干の
   −可能なすべての−ＯＲ並列ノードにおいて該親とＯＲ
   並列関係に立つ少なくとも一つのプロセス（“子”）を
   並行−かつ遡及的−処理により生成可能なデータ処理シ
   ステムであって、 前記の新たに生成した子プロセスのみが− 分岐生成されたＯＲ並列ブランチを処理しつつ−それ自
   体と親の双方に共通にアクセス可能な変数（“共通アク
   セス可能変数”）の設定を遂行するようにした深設定リ
   ストが設けられていることを特徴とするデータ処理シス
   テム。 １９、少なくとも１個のプロセッサを備えて複数の論理
   プログラム−特にプロログ様言語の−を同時または並行
   処理可能であり、既存のプロセス（“親”）により前記
   親と独立のＡＮＤ並列関係に立つ少なくとも一つのプロ
   セス（“子”）を並行−かつ遡及的−処理により生成可
   能なデータ処理システムであって、 ＡＮＤ並列ブランチの結果のクロスプロダ クトが増加的に形成されることを特徴とするデータ処理
   システム。 ２０、特許請求の範囲第１〜１７項のいずれかに記載の
   方法を使用するデータ処理システム。