JPH0154740B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は並列型推論計算機に係り、各プロセツ
サエレメント間のゴールの受け渡し頻度を減らす
ことによつて、同時に動作しうるプロセツサエレ
メント数を増加させるゴールの分配方式に関す
る。

〔発明の背景〕 従来の推論計算機では、推論処理の逐次的実行
が一般的であつた。その代表的な処理方式は、
「エジンバラ大学人工知能学部研究報告（Dept.of
Artificial Intelligence Research Report）第39
号および第40号（1977）」に詳しく述べられてい
る。こうした逐次型推論計算には、ひとつのプロ
セツサによつて、ひとつひとつの推論処理を逐次
実行するために、処理性能が低いという問題点が
あつた。一般にひとつのゴールの推論処理からは
複数の新しいゴールが派生し、これらの新しいゴ
ールは、並列に処理することが可能である。この
点に着目して、例えば、「第５世代コンピユータ
システムに関する国際会議（1984年）、講演論文
集（Proc.of Int.Conf、on Fifth Generation
Computer Systems1984、ICOT）、第479頁―第
489頁」（公知例）のように複数のプロセツサ・
エレメントをネツトワークによつて結合し、複数
の推論処理を並列実行することによつて処理性能
を向上させようという並列型推論計算機の提案が
なされてきた。

並列型推論計算機では、次の２点が課題とてな
つている。

(1) 推論処理をできるだけ多くのプロセツサ・エ
レメントの分散させ、並列動作するプロセツ
サ・エレメントの台数を大きくする。

(2) スループツトの小さいネツトワークで、効率
的にゴールを分配する。

(1)、(2)は無関係ではなく、ネツトワーク・スル
ープツトは実現的にはある値に制限されるので、
(1)の達成には、(2)の課題の克服が不可欠である。

さて、従来の並列型推論計算機では、例えば、
公知例に示されているように、各プロセツサ・
エレメントはひとつのゴール処理の結果派生した
新しいゴールをプール（ゴール・プールと呼ぶ）
に送つていた。各プロセツサ・エレメントは、ゴ
ール・プールにアクセスして、ゴールを取り出
し、推論処理を行なう。このため、プロセツサ・
エレメントにおける推論処理毎にゴール・プール
を介しての各プロセツサ・エレメント間での交信
が必要になり、ネツトワークのスループツトが十
分でない場合には、並処動作できるプロセツサ・
エレメントの数が制限されてしまう。

また、情報処理学会第30回全国大会予稿集6C
―９（p.201）（公知例）の例のように、東、西、
南、北のプロセツサ・エレメントと接続して、網
状のネツトワークを形成し、新しいゴールを、そ
れを生成したプロセツサ・エレメント（自プロセ
ツサ・エレメントと呼ぶ）→東プロセツサ・エレ
メント→南プロセツサ・エレメント→自プロセツ
サ・エレメント→………と順次分配することによ
つて、必要とされるネツトワーク・スループツト
を低く抑えようという従来例もある。公知例で
は４近傍接続の網状ネツトワークの導入によつ
て、必要とされるネツトワーク・スループツトを
低く抑えているが、〜1Gb／secのスループツト
が必要であり、通常のネツトワークでは、並列動
作するプロセツサ台数が十分には大きくできなか
つた。

〔発明の目的〕

本発明の目的は、ネツトワークを介しての各プ
ロセツサエレメント間の交信の頻度を減らすこと
のできるゴールの分配方式を提供し、高性能の並
列型推論計算機を実現することにある。

〔発明の概要〕

プロセツサエレメントのゴール処理の結果生じ
る新しいゴールは通常１、２個であり、１個の場
合も多い。したがつて、生成した新しいゴール
を、処理を行なつたプロセツサエレメントの次の
処理用のゴールとすれば、ネツトワークを介して
他のプロセツサエレメントにゴールを受け渡す必
要がない。

〔発明の実施例〕

以下、本発明の一実施例を詳細に説明する。並
列型推論計算機は、一例として、一階述語論理に
基づいたプロログ（Prolog）という言語によつ
て書かれたプログラムを実行することができる。

プロログの文法、プログラミング法、プログラ
ム例に関しては、中島秀之「Prolog」（産業図
書）等の教科書に述べられている。第２図に、こ
うしたプロログプログラムの例を示す。第２図第
１行は質問で「花子は何が好きですか。」と読む。
第２行は、ルールを記述しており、「ＸがＹを好
きだということは、ＸがＺの子供で、かつ、Ｚが
Ｙを好きだということである。」と読む。第３行
〜第７行は事実関係を記述している。

第２図のプログラムは次のように実行される。
第１行の質問を第３行〜第７行の事実に照らし合
わせ、花子に対する事実が見当らないので、第２
行のルールを適用する。その結果、第１行の質問
は“子供（花子、Ｚ）、好き（Ｚ，Ｙ）”即ち、
「花子は誰かの子供で、この誰かは何が好きか。」
という質問に置き換えられる。第１行の質問をゴ
ールと呼ぶ。次に、置き換えられた結果の新しい
質問（ゴール）は第２図、第３行〜第７行の事実
と照らし合わされ、“子供（花子、太郎）、好き
（太郎、野球）”即ち、「花子は太郎の子供で、か
つ太郎は野球が好きだ。」という結果と、“子供
（花子、和子）、好き（和子、本）”という結果が
得られる。第１の結果からは、“好き（花子、野
球）”が、第２の結果からは“好き（花子、本）”
が得られる。

本発明の実施例を第１図に示す。最初の質問に
対応するゴール、“好き（花子、Ａ）”がプロセツ
サエレメント＃０に渡され処理された結果、“子
供（花子、太郎）、好き（太郎、Ｙ）”と“子供
（花子、和子）、好き（和子、Ｙ）”という２つの
新しいゴールが生成される。これら２つの新ゴー
ルのうち、第１番目のゴールだけがゴールプール
に渡され、第２番目のゴールはプロセツサエレメ
ント＃０で処理される。ゴールプールに渡された
第１番目のゴールは、待機中のプロセツサエレメ
ントのひとつ＃ｎに渡され処理される。システム
で処理可能なゴールのすべてを処理するためのプ
ログラムおよびデータはシステムに共通な記憶場
所（図示せず）に記憶され、各プロセツサは適宜
これをアクセスする。

本実施例では、公知例の場合に２回ずつ行な
つた新ゴールの、プロセツサエレメントからゴー
ルプールへの転送とゴールプールがプロセツサエ
レメントの転送を、それぞれ１個ずつに減少させ
ることができる。この結果、ネツトワークの使用
頻度が、公知例の５回から３回に減るので、そ
の分だけ多くのプロセツサエレメントを並列動作
させることができる。

公知例では、新ゴールの発生のたびに、自プ
ロセツサ・エレメント→東プロセツサ・エレメン
ト→南プロセツサ・エレメント→自プロセツサ・
エレメントと循環的に分配先を変えていくので、
発生した新ゴールのうちの1/3しか自プロセツサ
に閉じ込めることができない。即ち、ネツトワー
クの使用頻度は高々2/3にしか低減できない。本
発明ではひとつの推論処理毎に、少くともひとつ
の新ゴールを自プロセツサに分配するので、より
高いゴールの閉じ込め率を得ることができる。特
に、ひとつの推論処理から１、２個の新ゴールし
か発生しない場合には、公知例との差が大きく
なり有効である。

〔発明の効果〕

第１図の例では、２回のゴール処理で結果が得
られたが、通常、結果が得られる迄には10回以上
のゴール処理が必要とされる。本発明ではゴール
処理の結果生成した新ゴールのうちのひとつは、
ネツトワークを介してゴールプールに送ることな
く、ゴール処理を実施したプロセツサエレメント
に閉じ込める。したがつて、本発明によれば、ネ
ツトワークの使用頻度を従来の場合の10分の１程
度にまで低下させることができるので、並列型推
論計算機の性能を10倍に高める効果がある。

【図面の簡単な説明】

第１図は、プロセツサエレメント間のゴールの
受け渡しを模式的に表わした図、第２図は、プロ
ログのプログラムの例である。第２図、第１図に
おける、Ａ，Ｘ，Ｙ，Ｘは変数を表わす。

Claims (1)

【特許請求の範囲】
1. １ 複数のプロセツサエレメントから成り、それ
   ぞれのプロセツサエレメントが別個のゴールを同
   時に処理し、該ゴール処理の結果生成した新しい
   ゴールを各プロセツサエレメント間の交信によつ
   て他のプロセツサエレメントに渡し、該プロセツ
   サエレメントが次にそのゴール処理を行なう並列
   型推論計算機において、ゴールの処理毎に、その
   結果生成した新しいゴールのうちのひとつを、該
   ゴール処理を実行したプロセツサ・エレメントに
   分配し、残りの新しいゴールを他のプロセツサ・
   エレメントに分配することを特徴とする並列型推
   論計算機におけるゴール分配方式。