JPS603752A

JPS603752A - 問題解決並列処理システム

Info

Publication number: JPS603752A
Application number: JP58112414A
Authority: JP
Inventors: Fumihiro Maruyama; 文宏丸山
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1983-06-22
Filing date: 1983-06-22
Publication date: 1985-01-10

Abstract

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

Description

【発明の詳細な説明】（５）発明の技術分野本発明は１問題解決並列処理システム、特に問題解決情
報を参照しつつ、与えられた問題を処理する如き処理シ
ステムにおいて、上記与えられた問題を複数の部分問題
に区分すると共に、スケジューラ・プロセッサと部分問
題解決プロセッサとが並列して処理を実行してゆくよう
にした問題解決並列処理システムに関するものである。

ＩＢＩ　技術の背景と問題点本発明はそれに限られるものではないが１例えば、言語
Ｐデｏｌｏｇを用いて、データ・ペースに対して問合わ
せを行う間合わせ問題の解決処理に当っては１例えば「
地中海とアジアの国とに国境を接している国（変数Ｃ）
をめよ」という問題に対応して。

Ａｎａｖｙａｒ　（Ｃ）＋：１Ｃｏｓｎｔｒｙ　（Ｃ）
　＆　Ｂｏｒｄａｒｔｔ　（Ｃ、ｍｇｄｉｔａｒ−ｒａ
ｎａａ館　）　＆　Ｃｏ５ｎｔｒｙ　（Ｃ＋）　＆　Ａ
ｓ１ａｎ　（Ｃｔ）＆　Ｂｏｒｄｅｒ　（Ｃ，Ｃｔ　）の如き形で問題が指示される。なおＣ，Ｃ，は夫々変数
であると考えてよい。

このような間合わせ問題を解くに当っては９次の如き５
個の部分問題を解く必要がある。即ち。

■　Ｃｏｕｎｔｒｙ　（Ｃ）・・・・・・Ｃは国である
。

■　Ｂｏｒｄｓｒ　（Ｃｔ　ｔｎｓｄｉｔａｒｒａｎｅ
ａｎ　）°−−Ｃは地中海に接している。

■　Ｃｏｕｎｔｒｙ　（Ｃ１）−−Ｃｔは国である。

■　Ａ　ｓ　ｔａｎ　（ＣＩ　）・・・・・・Ｃ１はア
ジアのものである。

■　Ｂｏｒｄｅｒ　（Ｃ２Ｃ１）・・・・・　ＣとＣ１
とは接している。

上記の如き部分問題はデータ・ベース上の例えば地理情
報を参照しながら解決してゆくようにされる。例えば＝
　Ｃｏｕｎｔｒｙ　（Ｃ）はデータ・ベース上の地理情
報（問題解決情報の１つ）から、１つの国を見付け、変
数Ｃの値はその国にする。次の部分問題Ｂｏｒｄｍｒ（
Ｃ、ｍｇｄｉｔｇｒｒａｎｅａｎ　）についでは１既に
Ｃの値が仮に定っているために、その国Ｃと地中海とが
接しているという事実が問題解決情報中で見出せるか否
かをチェックすることによって解決される。もしも見出
せたなら次の部分問題に進み、見出せないなら前の部分
問題に戻って別の国Ｃを探す。このように、最終的にす
べての部分問題を満足するＣ９Ｃｌ　をめ、Ｃを直接の
解とする。

上記の如く処理してゆくが、上記の順序で部分問題を解
決してゆかねばならないことはない。むしろ上記の順序
を採用することは効率が悪いつＣれは９次々と国を挙げ
てはそれが地中海に接しているか否かを調べるという具
合だからである。上記よりも１例えは地中海に接してい
るもの（接しているものは国だけではなく大西洋やスエ
ズ運河などが含まれる）の中から１国を見付りることが
効率が良い。これは１世界中の国の数にくらべて地中海
に接しでいる「もの」の数が少ないからである。

厳密には、効率の良い解決順序は、夫々の部分問題の解
の数によって決まる。勿論、実際の解の数は解いてみな
いと判らないが、データ・ベースの中味（問題解決情報
）の量（即ち数量あるいは個数）に関連した情報（例え
ば国の個数など）から推定できる。即ち、成る部分問題
を解くに当って何倍の可能性を考慮しなければならない
かを　１「コスト」として定め、これを部分問題に割付
けるようにする。例えば上述の部分問題を解く上での基
礎データとして５次の如きものが判っているとする。即
ち。

（ａ）　Ｃｏｕｎｔｒｙ　（Ｃ）に関して１国の個数（
サイズ）がｒ１５０Ｊであり、当該１５０個の国の中か
ら１つを選ぶに当って３００個の引数が存在し得るとし
。

（６Ｊ　Ａｓ１ａｎ　（Ｃｔ）に関して、アジア内の国
の個数（サイズ）がｒｌｏＯＪであり、上記と同様にそ
れに対応する引数のサイズがｒ３００Ｊであるとし。

（Ｃ）　Ｂｏｒｄｅｒ　（＊ｉ　、　＊ｚ）に関して、
サイズが１９００Ｊであり、上記＊ｌに対応する引数の
サイズがｒ１８０Ｊで、上記＊２に対応する引数のサイ
ズがｒ１８０Ｊであるとする。

この場合、上記（α）に関するコストはｌ　１５０Ｊで
あり、上記（ｂ）に関するコストはｒｌｏｏＪである。

また、上記１ｃ）に関して、上記＊１も＊２も共に未知
のもの（変数のまま）である場合にはコストはｒ９００
Ｊであり、上記＊ｌや＊２のいずれか一方が例えばＵＳ
Ａや地中海の如く既知である場合にはコストはｒ９００
／１８０＝５Ｊであり、上記＊ｌと＊２との両者が既知
である場合にはコストはｒ９００／１８０Ｘ１８０＝１
／３６Ｊ　として与えられる。

（Ｃ１発明の目的と構成本発明は、上記の点を考慮しつつ、スケジューラ・プロ
セッサと部分問題解決プロセッサとが並列に実行しつつ
問題を解決するようにすることを目的としている。そし
てそのため１本発明の問題解決並列処理システムは２問
題解決情報を参照しつつ、与えられた問題を処理するデ
ータ処理システムにおいて、上記問題解決情報をアクセ
スしつつ指定された部分問題を解く少なくとも１つの部
分問題解決プロセッサと、上記問題を複数個に区分した
各部分問題の処理順序を指示するスケシュ　−ラ・プロ
セッサと、スケジューリングに利用される基礎データを
保持する基礎データ保時部とをそなえてなり、上記スケ
ジューラ・プロセッサと上記部分問題解決プロセッサと
が並列に上記与えられた問題解決処理を実行するように
したことを特徴としでいる。以下図面を参照しつつ間合
わせ問題を解決する態様を例に挙げで説明する。

ＩＤＩ　発明の実施例第１図は本発明の一実施例構成を示し、第１２図Ｖ％Ｊ
　１１３１　ｔｅｌは本発明による一実施例処理態様を
示す。

Ｎ−１図において、■はデータ・ベースであって問題解
決情報が格納されているもの、２は本発明にいう基礎デ
ータ保持部、３はスケジューラ・プロセッサ、４は部分
問題解決プロセッサを表わしでいる。、また５は１部分
問題区分処理機能部であって、質問された間合わせ問題
を複数の部分問題に区分する処理を行うよう動作する。

６は、基礎データ読込み部であって、基礎データ保持部
２から上述の（α）　、　（ｂ）　、　（６１の如き基
礎データを読込むよう動作する。７は、コスト計算処理
部であって。

コストを計算するように動作する。８は９割込み要求発
生部であって、上記コスト計算の結果、現に部分問題解
決プロセッサ４がＩｌｉゲぎつつある部分問題と異なる
部分問題を選択すべきである場合に。

この旨を割込みによって通知する。また９は、解決通知
処理部であって１部分間題解決プロセッサ４から１つの
部分問題が解けた旨の通知があったとぎに１次に実行す
べき部分問題を選択せしめるべく指示を発する。

更に、１０は、リスト保持部であって、当面法に実行す
べきと考えられる部分問題をリストの形でもっている。

１１は９問題処理機能部であって。

個々の部分問題についてデータ・ベース１をアクセスし
つつ解いてゆくように動作する。１２は。

割込み受付処理部であって、スケジューラ・プロセッサ
３からの割込みに対応して真に次に実行すべき部分問題
の解決をスタートせしめるように動作する。１３は、解
決通知発信部であって、１つの部分問題が解けた時点で
、この旨をスケジューラ・プロセッサ３に通知するよう
に働らく。

以下、″Ａ−２図！Ａ）　、　ｉｎｌ　、　ｉｃｌを参
照して９本発明による一実施例処理態様を説明しでゆく
。

（１）　例えば本明細書［Ｂｌ技術の背景と問題点の欄
に　１記述した如き間合わせ問題が与えられたとすると
き０部分問題区分処理機能部３は、同じく上記欄に記述
した如き複数の部分問題を抽出する。

（２）基礎データ保持部（補助データ・ベース）２には
、第２図囚図示の如く基礎データが格納されている。ス
ケジューラ・プロセッサ３内の基礎データ読込み部６は
、各部分問題に関連する基礎データを読込む。

（３）　そして、コスト計算処理部７は、木２図囚図示
の如く、上記各部分問題（１）、■、■、■、■に対応
するコストを計算する。

部分問題■のコストはｒ１５０Ｊである。部分問題（り
のコストは、地中海が既知であることから１５」である
。部分問題■のコストはｒ１５０Ｊである。部分問題■
のコストはｒｌｏＯＪである。

部分問題■のコストはｒ９００Ｊである。

（４）　この間２部分間題解決プロセッサ４においては
、リスト保持部１０に対して９部分間題の処理順が仮に
■、■、■、■、■の如く与えられている。コノため、
当該プロセッサ４の問題処理機能部１１は１部分間題の
を解くべく処理を開始する。即チ１国名として、アフガ
ニスタンｐアルバニア、アルジエンチン、・・・・・　
の如＜、国ヲ抽出してゆく。

（５）シかし、上記処理（３）において、コスト最小の
部分問題は問題■であることが判り９割込み要求発生部
８は、この旨をプロセッサ４に通知する。

（６）　プロセッサ４は、これを割込み受付処理部１２
によって受付け１部分問題■の実行を停止し。

部分問題■の実行を開始する。そして、リスト保持部１
０の内容が更新される。

（７）　部分問題■が解決されると、解決通知発信部１
３ばこの旨をプロセッサ３に通知する。

（３）　これによって、プロセッサ３における解決通知
処理部９は、コスト計算処理部７を発動せしめる。

（９）　このとき１部分問題■の新しいコストは［１５
０／３００＝　ｌ／２Ｊとなり１部分問題■の新しいコ
ストはｒ９００／１８０＝５」となる。この結果１部分
間題■が最小のコストをもつものであることが判る。こ
のとき、プロセッサ４においては２部分間題（１）が実
行されていることから。

その実行を継続せしめる。

０ｑ　プロセッサ４において部分問題■が解かれると、
この旨が通知される。

ａυ　プロセッサ３においては２部分問題■が最小のコ
ストをもつことが判る。このとき、プロセッサ４におい
ては、リスト保持部ｌＯの内容にもとづいて９部分問題
■を実行していることから、プロセッサ３は割込み要求
を発する。

＠　この結果、プロセッサ４は部分問題■を開始する。

α傍　部分問題■が解かれると、この旨がプロセッサ３
に対して通知される。

０勺　この結果のコストは１部分問題■においてｒ１５
０／３００＝Ｖ’ｌ、Ｊであり１部分問題■においてｒ
１００／３００＝　１／３Ｊであり２部分問題■のコス
トが最小であることが判る。

Ｑリ　シタ力って、プロセッサ３はプロセッサ４に割込
み１部分問題■を実行せしめる。

（社）　プロセッサ４は１部分間題（４）を実行した後
に。

部分問題■を実行する。

以上の如く、処理が行われてゆく。）−記説明に当って
９間合わせ問題を解決することを・例に挙げて説明した
が１本発明はそれに限られることなく。

例えば上記スケジューラ・プロセッサが９部分間題解決
プロセッサの処理を監視し２部分間題解決に失敗した如
き場合の原因を推論して指導を行う如き制御を行うこと
などを含むことは言うまでもない。また部分問題解決プ
ロセッサが単一の問題のみを長期間処理し続けているこ
とを監視するなどの場合も同様である。

ｔＥ）　発明の詳細な説明した如く１本発明によれ（′ｉ１例えは間合わせ
問題解決に当って、いわば最も効率のよい順序で部分問
題を実行してゆくことが可能となる。

なお上記説明において、スケジューラ・プロセッサ３と
部分問題解決プロセッサ４とを装置として別体のものと
して説明したが、マルチプロゲラ　１ミング処理の形で
単一の装置によって実行されでもよいことは言うまでも
ない。

【図面の簡単な説明】

第１図は本発明の一実施例借成を示し９月１２図Ｖ％Ｊ
　１１３＋　ｔｅｌは本発明による一実施例処理態様を
示す。図中、１はデータ・ベース、２は裁礎データ保持部、３
はスケジューラ・プロセッサ、４は部分問題解決プロセ
ツザ、５は部分間題区分処理機能部、６は基礎データ読
込み部、７はコスト計算処理部、８は割込み要求発生部
、９は解決通知処理部、１０はリスト保持部、１１は問
題処理機能部。１２は割込み受付処理部、１３は解決通知発信部を表わ
す。特許出願人　富士通株式会社

Claims

【特許請求の範囲】問題解決情報を参照しつつ、与えられた問題を処理する
データ処理システムにおいて、上記問題解決情報をアク
セスしつつ指定された部分問題を解く少なくとも１つの
部分問題解決プロセッサと。上記問題を複数個に区分した各部分問題の処理順序を指
示するスケジューラ・プロセッサと、スケジューリング
に利用される基礎データを保持する基礎データ保持部と
をそなえてなり、上記スケジューラ・プロセッサと上記
部分問題解決プロセッサとが並列に上記与えられた問題
解決処理を実行するようにしたことを特徴とする問題解
決並列処理システム。