JPS6188360A - 処理分散制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はプロセッサを複数個使用してデータ処理を並列
処理するデータ処理方式に係り、特にあるプロセッサで
データ処理を遂行するときに必要なサブ処理を他のプロ
セッサに依頼して並列処理を行う場合において、このサ
ブ処理を実行するアイドル状態のプロセッサを容易に検
出できるようにした処理分散制御方式に関する。

〔従来の技術〕

ある問題を解決する場合、その問題を構成する複数のサ
ブ問題を解決する必要がある。例えば第５図に示す如く
、ネットワーク３０に接続された複数のプロセッサ素子
３１−０．３１−１−・−３１−ｎにより構成されたデ
ータ処理システムにおいて、これらのプロセッサ索子３
１−０．３１−１・・・３１−ｎから構成される並列処
理システムにより前記の如き問題を解決する場合、処理
の各時点で複数のサブ問題を各プロセッサ素子３１−０
．３１−１・−３１−ｎに均等に処理させることにより
システム全体として効率よく並列処理（並行処理も含む
）を進めてゆくことが必要である。なお前記プロセッサ
素子としては例えばマイクロプロセッサの如きプロセッ
サが使用される。

〔発明が解決しようとする問題点〕

ところで第５図に示す如きシステムで、例えば上位シス
テムからの指示によりプロセッサ素子３１−〇にて問題
を処理するとき、サブ問題の並列処理が必要な場合、従
来は次の■、■に示す２つの方式が考えられている。

■　適宜選択したプロセッサ素子にサブ問題を依頼する
こと。

■　特別な管理プール用のプロセッサを設け、集中管理
すること。

■の方式は、例えばプロセッサ素子３１−０が問題処理
を遂行しているときに、サブ問題量が多いと判断した場
合、他のプロセッサ素子３１−１−−−３１−　ｎの処
理状態には一切関係なしに、例えば乱数を用いて決まっ
たプロセッサ素子とか、あるいは隣接するプロセッサ素
子等、一義的に決めたプロセッサ素子にこの余分なサブ
問題処理を転送するものである。しかもこの方式では、
あくまでもサブ問題処理の依頼転送先であるプロセッサ
素子の処理状況を考えずに、自プロセッサ素子で処理量
が多いと判断すると、前記の如く適当に選んだプロセッ
サ素子にサブ問題を転送するので均等なサブ問題処理分
散が望めないという問題がある。

また、■の方式は、同様にプロセッサ素子３１−０がサ
ブ問題量が多いと判断した場合には、特別な管理プール
に転送し、その管理プールの管理を特定のプロセッサ素
子に行わせるものである。

そして処理に余裕のあるプロセッサ素子がこの管理プー
ルにサブ問題を取りにいくものである。しかしこの方式
では管理プールを管理しているプロセッサ素子に対し要
求の集中が予想され、この集中管理部分のプロセッサ素
子がビジーになり処理がおくれることになり、並列効率
の点から問題があると考えられる。

〔問題点を解決するための手段〕

前記の問題点を解決するため、本発明の処理分散制御方
式では、ネットワークに接続された複数のプロセッサ素
子により構成される並列処理システムにおいて、各プロ
セッサ素子をシフト・ループリンクで接続するとともに
各プロセッサ素子にリクエスト情報を含むデータスロッ
トを出力するデータ入出力手段と、自アドレス保持手段
と、取込みＰＦ、アドレス保持手段と、比較手段と、転
送データ制御手段を設け、前記シフト・ループリンクに
前記データスロットを巡環させるとともに、前記リクエ
スト情報を解読してアイドル状態にあるプロセッサ素子
を検出して分散処理すべきデータ処理事項を依頼するよ
うにしたことを特徴とする。

〔作用〕

本発明によりアイドル状態のプロセッサ素子を非席に簡
単に確実に検出できるので必要なサブ問題処理を早急に
実行することができる。

〔実施例〕

本発明を一実施例にもとづき詳述するに先立ちその概略
を第１図及び第２図により説明する。

本発明ではネットワーク１０に接続されているプロセッ
サ素子１−０．１−１．１−２−・１−１５にそれぞれ
結合部２−０．２−１．２−２・−・２−１５を設け、
各結合部２−〇〜２−１５をシフト・ループリンタ３で
結合する。そしてこのシフト・ループリンタ３に、第２
図に示す如き、デ−タ・スロットＤＳを各プロセッサ素
子１−０〜１−１５ごとに流す、このデータ・スロット
ＤＳには、第２図に示す如く、そのスロットの属するプ
ロセッサ素子（Ｐ　Ｅ）を示すＰＥアドレス（プロセッ
サ素子が１６個の場合は４ビツト）部分と、サブ問題処
理が可能か否かを示すリクエスト部分、例えば区分４〜
７までの４ビツトが設けられている。この場合各プロセ
ッサ素子は４つまでのザブ問題処理能力を有するもので
あり、この処理能力の分だけリクエスト部分が存在する
。最初釜プロセッサ素子１−０〜１−１５はいずれもサ
ブ問題処理を遂行していないので、各データ・スロット
においてリクエスト部分はすべて「０」にしておく。そ
して例えばプロセッサ素子１−０においてサブ問題処理
が必要になったとき、結合部２−０においてリクエスト
部分が１ビツトでも「０」のデータ・スロットを検出し
てそのリクエスト部分を１ビツト「１」に書き替え、そ
のＰＥアドレス部分を読み出して得た、例えばプロセッ
サ素子１−２にネットワーク１０を経由してサブ問題処
理を依頼する。プロセッサ素子１−２ではこの依頼され
たサブ問題処理を完了してプロセッサ素子ｌ−２に属す
るシフト・ループリンク３上のデータ・スロットを捉え
て、自プロセンサ素子の処理状態により、先に記入した
リクエスト部分の「１」を「０」に落とす、このように
することによりサブ問題処理を行うことが可能なプロセ
ッサ素子を１臼ｉζに検出できる。

次に本発明の一実施例を、第１図、第２図の外に第３図
および第４図にもとづき詳述する。

第３図は前記結合部の詳細図であり、第４図は本発明の
動作説明図である。

第３図において、１はプロセッサ素子、２は結合部、１
１はサブ問題プール部、１２はプール・コントローラ、
２１は入出力レジスタ、２２は自アドレス保持レジスタ
、２３は取込ＰＥアドレス保持レジスタ、２４．２５は
それぞれ比較器、２６は転送データ制御部、２７はセレ
クタである。

なお第１図におけるプロセッサ素子１−０〜１−１５お
よび結合部２−０〜２−１５はいずれも同一構成であり
、第３図に示すプロセッサ素子１および結合部２はこれ
らを代表するものであ、る。

プロセッサ素子１には、他のプロセッサ素子で並列的に
処理して欲しいサブ問題をプールするサブ問題プール部
１１と、このサブ問題を他のプロセッサ素子に処理の依
頼を行ったり、必要があれば依頼先のプロセッサ素子か
ら依頼ずみのサブ問題処理結果を受取る等のサブ問題プ
ールに関する制御を行うプール・コントローラ１２を設
けている。

゛　結合部２は自プロセッサ素子の処理状態を見ながら
データスロットをシフト・ループリンタ３に送受信する
ものであって、入出力レジスタ２１、自アドレス保持レ
ジスタ２゛２、取込ＰＥアドレス保持レジスタ２３、比
較器２４．２５転送デ一タ制御部２６、セレクタ２７等
を具備している。

入出力レジスタ２１はシフト・ループリンタ３より入力
されたデータスロットＤＳが１時保持されるものであり
、自アドレス保持レジスタ２２にはその結合部の属する
プロセッサ素子の識別番号が記入されている。例えば第
１図における結合部２−２の場合にはＰＥアドレスには
ｒｏ　０１０Ｊが記入されている。

取込ＰＥアドレス保持レジスタ２３はサブ問題処理依頼
先のプロセッサ素子の識別番号が記入されるものであり
、複数の依頼先が保持できるよう。

に構成されている。この場合、取込ＰＥアドレス保持レ
ジスタ２３はサブ問題処理依頼先のプロセッサ素子の識
別番号が記入されるものである。サブ問題処理を依頼し
ようとして、依頼しようとしたプロセッサ素子のデータ
スロットのリクエスト部を「０」から「１」に変更した
後で、サブ問題処理を依頼できなかった場合に（前記変
更してから依頼するまでの間に自プロセッサ素子での処
理が終りそのサブ問題の処理を自プロセッサ素子で処理
可能となったような場合）、変更したデータスロットを
再び「０」状態に戻す必要がある。そのときに該データ
スロットを見出すために取込ＰＥアドレス保持レジスタ
２３を使用することになる。この場合、取込ＰＥアドレ
ス保持レジスタ２３に保持されている識別記号を比較器
２５により比較する。

転送データ制御部２６は、自プロセッサ素子の処理状態
を常に把握しており、そのため状態レジスタ２６−０を
備えている。この状態レジスタ２６−０には自プロセッ
サ素子の状態が自プロセッサ素子により書込まれるもの
であり、これに自プロセッサ素子の状態、例えばアイド
ル状態の他のプロセッサ素子の検出要求等がコードによ
り記入されることになる。そして転送データ制御部２６
はデータスロットのリクエスト部分にリクエストずみの
フラグ「１」を記入したり、依頼できなくなった場合に
変更したデータスロットのフラグを「ｌ」からｒＯＪに
戻したり、また依頼されたサブ問題処理を完了したこと
によりリクエストずみのフラグｒｌＪを落したりするよ
うなシフト・ループリンク上に転送する転送データつま
りデータスロットに対する各種制御を行うものである。

セレクタ２７は入出力レジスタ２１に保持されたデータ
スロットをシフト・ループリンタ３に出力するのかそれ
とも転送データ制御部２６により加工された（すなわち
リクエストフラグを「１」、または「０」にセットされ
た）データスロットを出力するのか選択するものであっ
て、その選択制御信号は転送データ制御部２６から出力
される。

本発明の動作について説明する。

（１）まず第１図に示すデータ処理装置の電源投入時に
各プロセッサ素子１−〇〜１−１５はその結合部内の入
出力レジスタ２１に自己のプロセッサ素子アドレス（Ｐ
Ｅアドレス）と制御情報（リクエスト区分に記入する情
報で、通常はオール「０」）を書込む。この入出力レジ
スタ２１に形成された出力情報は次のクロックでセレク
タ２７より出力されて隣のプロセッサ素子の結合部の入
出力レジスタにセットされる。したがって自分の入出力
レジスタには１つ前のプロセッサ素子の出力情報がセッ
トされる。このようにしてクロック毎に各プロセッサ素
子のデータスロットがシフト・ループリンク３上を順次
移動して、また自己のプロセッサ素子に戻るという巡環
移動される。

（２）　　ところでプロセッサ素子１−０で問題処理中
にサブ問題処理の要求が生じたとき、このサブ問題をサ
ブ問題プール部１１に渡し、プールコントローラ１２は
そのようなプロセッサ素子１−０の処理状態を転送デー
タ制御部２６に知らせる。

そしてそのことを認知した転送データ制御部２６はサブ
問題処理のための他のプロセッサ素子の検出を始める。

（３）　　これにより、転送データ制御部２６は、入出
力レジスタ２１に順次セットされるデータスロットのリ
クエスト区分にリクエストフラグの立っているもの、つ
まり「０」の存在するものを検出する。このようにして
リクエスト区分に「０」の存在するデータスロットを検
出したときそのＰＥアドレス例えばＰＥ２を読み、これ
を取込１）　Ｅアドレス保持レジスタ２３にセットする
とともに前記リクエスト区分の「０」をエビ・シト「ｌ
」に書替える。このようにして書替えられたデータスロ
ットは転送データ制御部２６からセレクタ２７を経由し
てシフト・ループリンタ３に出力される。

（４）ところで転送データ制御部２６はリクエスト区分
を「１」に書替えたデータスロットのＰＥアドレスｒＰ
Ｅ２Ｊをプールコントローラ１２に報告する。プールコ
ントローラ１２はこれによりこのＰＥ２のアドレスのプ
ロセッサ素子１−２にサブ問題処理のためのアイドル状
態にあることを認知し、サブ問題プール部１１に保持さ
れているサブ問題をプロセッサ素子１−２に送出する。

これによりこのサブ問題はプロセッサ素子１−２で並列
処理されることになる。

この場合、サブ問題プール部１１に格納されていたサブ
問題が自プロセッサ素子において処理されようとしてい
ることも考えられる。その場合には、そのサブ問題はプ
ロセンサ素子１−２には送出しない。このときには、プ
ールコントローラ１２はその旨を転送データ制御部２６
に知らせる。そして、転送データ制御部２６は入出力レ
ジスタ２１に順次セットされるデータスロットのＰＥア
ドレスを取込ＰＥアドレス保持レジスタ２３で保持して
いるＰＥアドレスｒＰＥ２Ｊと一致するか否かを比較器
２５にて検出させ、このＰＥ２のアドレスを有するデー
タスロットを検出したとき、そのリクエスト区分の「１
」を「０」に戻して、これをセレクタ２７よりシフト・
ループリンタ３に出力する。

（５）プロセッサ素子１−２はこのサブ問題処理を終了
したとき、（自プロセッサ素子の処理状態により、）自
データスロット・リクエスト区分の「１」を「０」に落
とし、これをセレクタ２７よリシフト・ループリンク３
に出力する。

第２図の例では、各プロセッサ素子が４つのサブ問題を
処理できる例を示しているので、リクエスト区分の４ビ
ツトがすべて「１」になったときそのプロセッサ素子は
ビジー状態となり、処理中のサブ問題の処理が少なくと
も１つ終了しない限りアイドル状態にはならない。

またアイドル状態か否かはそのリクエスト区分の「０」
の有無をチェックすることにより簡単に判断することが
できる。

第４図に入出力レジスタ２１からの取込みと書出しのタ
イムチャートを示す。

クロックＣＬＫの立上りで他の結合部から送出されたデ
ータスロットが入出力レジスタ２１に取込まれる。そし
てそのデータスロットのＰＥアドレスが比較され、その
結果制御情報を変更しない場合にはクロックＣＬＫの立
上りにより入出力レジスタ２１のデータがそのまま出力
される。また変更がある場合には制御情報が書替えられ
たあとでクロックＣＬＫの立上りにより出力されること
になる。

なお前記説明ではデータスロットの発行元を識別するた
めアドレスを記入した例について説明したが、カウンタ
を使用して発行元を識別してもよい。このとき、基準と
なる特定プロセッサ素子のデータスロットにはこの基準
を示すデータ（例えば最初に「１」）が記入されており
、これよりの順位をカウントすることによりデータスロ
ットの発行元を識別することができる。

またサブ問題処理の例としては詰め将棋を解く場合にお
いて指手が金または銀より行うというような複数の処理
が並行して存在するようなことがある。このように並列
処理可能な状態が発生したことをプロセッサ素子が認識
した場合、いずれか一つを自プロセッサ素子で処理し他
を他のプロセッサ素子で処理すればデータ処理（詰め将
棋の場合は正解の検出）を早（遂行することができる。

なお前記実施例においては、プロセッサ素子が問題を処
理している途中で、並列に行える処理が発生した場合に
プロセッサ素子側から積極的に結合部を介してアイドル
状態の他プロセツサ素子を探索するものであった。

しかし本発明の他の実施例として次のような例もある。

すなわち、プロセッサ素子は問題を処理しているだけで
、積極的にはアイドルの他のプロセッサ素子の検出依頼
は行わない。ただし自分の処理状態（例えば割込み可能
とか、今は割込まれては困る等）を転送データ制御部２
６に常に知らせておく。このような自己の処理状態は状
態レジスタ２６−０にコードを記入することにより行う
ことができる。結合部では、転送データ制御部を通して
プロセッサ素子の処理状態を常に知り、アイドルの他の
プロセッサ素子を検出した場合、もし自プロセッサ素子
の処理状態が割込可能であれば自プロヒッサ素子に知ら
せる。このときのデータスロットの扱いは前記実施例と
同様である、すなわちリクエスト区分の「０」を「１」
に書替えるとともに、そのデータスロットのＰＥアドレ
スを取込ＰＥアドレス保持レジスタ２３にセットする。

ただ１つ異なる点は、前記実施例とは異なり。

そのアイドルのプロセッサ素子に処理を与えられる力）
否かは自プロセッサ素子で１周らべてみなければ全く判
断がつかない点である。そして自プロセッサ素子で調ら
べてみてアイドルのプロセッサ素子に処理を与えられな
い場合には、前記実施例においてアイドルなプロセッサ
素子を取込んだ際にサブ問題がすでに自プロセッサ素子
で処理されかげていてサブ問題を与えようとしたアイド
ルなプロセッサ素子のデータスロットを元に戻す処理と
同じ処理をすればよい。すなわち取込ＰＥアドレス保持
レジスタ２３にセットされたプロセッサ素子のリクエス
ト区分の「１」を「０」に書替え処理を行えばよい。

〔発明の効果〕　　　一 本発明によればあらかじめ各プロセッサ素子におけるサ
ブ問題処理が可能か否かを示す制御情頼を有するデータ
スロットを用窓し、これを読取ることによりアイドリン
グ状態にあるプロセッサ素子を正確に検出することがで
きる。それ故、ザブ問題の処理を効率よく並列的に処理
することができるので、データ処理速度を向上させるこ
とができる。

【図面の簡単な説明】

第１図は本発明の概略構成図、第２図は本発明に使用す
るデータスロットの説明図、第３図は本発明における結
合部の詳細図、第４図はその動作説明図、第５図は従来
の分散処理装置の概略構成図である。 図中、１はプロセッサ素子、２は結合部、３はシフト・
ループリンク、１１はサブ問題プール部、１２はプール
コントローラ、２１は入出力レジスタ、２２は自アドレ
ス保持レジスタ、２３は取込ＰＥアドレス保持レジスタ
、２４．２５は比較器、２６は転送データ制御部、２７
はセレクタを示す。

Claims (1)

1. 【特許請求の範囲】 １、ネットワークに接続された複数のプロセッサ素子に
   より構成される並列処理システムにおいて、各プロセッ
   サ素子をシフト・ループリンクで接続するとともに各プ
   ロセッサ素子にリクエスト情報を含むデータスロットを
   出力するデータ入出力手段と、自アドレス保持手段と、
   取込みＰＥアドレス保持手段と、比較手段と、転送デー
   タ制御手段を設け、前記シフト・ループリンクに前記デ
   ータスロットを巡環させるとともに、前記リクエスト情
   報を解読してアイドル状態にあるプロセッサ素子を検出
   して分散処理すべきデータ処理事項を依頼するようにし
   たことを特徴とする処理分散制御方式。 ２、前記転送データ制御手段は前記プロセッサ素子にお
   いて分散処理すべきデータ処理事項が発生したときに該
   プロセッサ素子からの要求に応じてアイドル状態にある
   プロセッサ素子を検出するようにしたことを特徴とする
   特許請求の範囲第１項記載の処理分散制御方式。 ３、前記転送データ制御手段は前記プロセッサ素子の動
   作状態を判断してアイドル状態にある他のプロセッサ素
   子を検出してこれをリザーブし、前記自プロセッサ素子
   に対して他のプロセッサ素子に対して分散処理すべきデ
   ータ処理事項が存在しているか否かを判断するようにし
   たことを特徴とする特許請求の範囲第１項記載の処理分
   散制御方式。