JPH0570867B2

JPH0570867B2 -

Info

Publication number: JPH0570867B2
Application number: JP63058492A
Authority: JP
Inventors: Hiroshi Sakai; Shigeki Shibayama; Akihiko Nakase
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1988-03-14
Filing date: 1988-03-14
Publication date: 1993-10-06
Also published as: JPH01232461A

Description

【発明の詳細な説明】［発明の目的］（産業上の利用分野）この発明は、マルチプロセツサシステムにおけ
る各要素プロセツサからのアクセス要求に対し、
処理すべきデータの格納位置情報を与える並列処
理制御装置に関する。

（従来の技術）マルチプロセツサシステムは、複数の要求のそ
れぞれに別のプロセツサを割当てて処理させるこ
とにより単位時間当りのシステムの処理件数を高
める方法と、個々の要求を複数のプロセツサで共
同で処理することにより、個々の要求の処理時間
を短縮する方法とが有り、これらが分野に応じて
使い分けられている。

このうち、個々の要求を複数のプロセツサで共
同して処理する方法では、複数のプロセツサに接
続可能な共有メモリやマルチポート・ページメモ
リ（田中護、Multiport Page−Memory
Archteeture and Ａ Multiport Disk−Cache
System、New Generation Computing ２、
1984年）などを用いて、各プロセツサからデータ
の格納位置を指定して、その場所に格納されてい
るデータの参照及びその場所へのデータの書込み
を行なうようなシステムが用いられる。

このような並列処理では、各プロセツサが記憶
装置にアクセスする場合に、それぞれのプロセツ
サがどのデータの処理を担当すべきかを調停する
処理が必要で、この処理がシステムの性能向上を
図る上でのネツクとなつている。例えば、第５図
に示すように、記憶装置１に従業員番号と従業員
の氏名の組がデータとして格納されており、「そ
の中から従業員番号が149828の従業員の氏名を求
めよ」という要求を複数のプロセツサP₁，P₂，
…，Pnで共同して処理する場合を考える。但し、
これらのデータは、いくつかずつまとめて、ある
決まつた大きさのページに格納されているものと
する。この場合、各プロセツサP1〜Pnは、記憶
装置から従業員番号と従業員の氏名の組を格納し
たページを読込み、その中に含まれるデータのそ
れぞれについて、従業員番号が条件に等しいかど
うかを検査する訳であるが、あるページを何台か
のプロセツサで重複して読込んだり、逆にどのプ
ロセツサからも読込まれないページがあつては、
正しい結果が得られない。そこで、全てのページ
は、いずれかのプロセツサにより、必ず１回だけ
読込むということを保障する必要がある。

これを保障する手段として従来から知られてい
る方法には次の２つの方法がある。

第１の方法は、個々のプロセツサが担当するペ
ージを処理にかかる前に予め決定しておく方法で
ある。例えばプロセツサ台数をｎとすると、各ペ
ージに０から始まる通し番号をつけたとして、第
ｉ（ｉ＝０、１、…、ｎ−１）番目のプロセツサ
には、通し番号をｎで割つた余りが（ｉ−１）に
等しいページを処理させる。このような方法をと
ると、最初から各ページを担当するプロセツサが
確定しているため、プロセツサ間の通信が少なく
て済むという長所がある。しかし、この方法は、
処理途中でプロセツサの台数を変更できないこ
と、データによつて処理負荷の異なる場合、プロ
セツサによつて処理時間にばらつきを生じ、全体
の処理時間は最も負荷の重い処理をしたプロセツ
サの処理時間となつてしまうことなどの短所があ
る。

これに対し、第２の方法は、各プロセツサから
アクセス可能な共有メモリを使用し、そこに各プ
ロセツサ間で共通に参照すべき情報を格納する方
法である。例えば、共有メモリの上に、次に記憶
装置から読込むべきページの格納位置を格納して
おく。そして、各プロセツサは、その位置にある
データを、記憶装置から読込むとともに、格納位
置の値を次に読込むべきページの格納位置に更新
する。この方式では、各プロセツサは、ひとつの
ページの処理を終了したものから順に、次のペー
ジの処理を行なうことができる。そのため、処理
途中でのプロセツサの追加、削減が可能で、しか
も、プロセツサ間の処理時間のばらつきを小さく
することができ、全体の処理時間の短縮が望め
る。しかし、この方法では、あるプロセツサが共
有メモリ上の格納位置を参照してからそれを更新
するまでの間、即ち、格納位置情報の読出しと、
更新のための書込みとを行なう期間、その情報を
他のプロセツサが参照したり、書替えたりしない
ようにする必要がある。このような処理を、ここ
では同期処理と呼ぶことにすると、共有メモリを
用いた同期処理の欠点は、同期処理は排他的に行
なう必要があるため、マルチボード・ページメモ
リのように、複数プロセツサから、同時にアクセ
ス可能な記憶装置を使用しても、同期処理のた
め、記憶装置の持つ潜在的なデータ転送能力を生
かせないという点に有る。また、第６図に示すよ
うに、データ処理装置による本来のページ入出力
の時間をＴ、それに必要な同期処理の時間をxT
とすると、同期処理の部分は、１台のプロセツサ
しか動作できないため、同期処理の時間が長い
程、プロセツサ台数を増やしても並列度は上がら
ないという欠点がある。

（発明が解決しようとする課題）このように、従来の共有メモリを用いたマルチ
プロセツサによる並列処理では、記憶装置に格納
されているデータを、各プロセツサで処理を分担
する場合に必要となる同期処理が、性能の向上を
図る上での障害となつていた。

本発明は、このような同期処理を高速化してマ
ルチプロセツサシステムの処理効率の向上に寄与
し得る並列処理制御装置を提供することを目的と
する。

［発明の構成］（課題を解決するための手段）本発明は、Ｎ個の要素プロセツサを含むマルチ
プロセツサシステムに接続され、アクセス要求の
出力された前記要素プロセツサに対し、処理すべ
きデータの格納位置情報を与える並列処理制御装
置であつて、次にアクスセ要求があつたときに出
力する前記処理すべきデータの格納位置情報を記
憶する記憶手段と、前記要素プロセツサからのア
クセス要求を受け付けると、ｉを１からＮまでの
整数とするとき、第１番目の要素プロセツサから
第ｉ番目の要素プロセツサまでの内で、同時にア
クセス要求しているプロセツサの個数を各ｉにつ
いて求める個数出力手段と、この個数出力手段で
求められた個数と前記記憶手段に記憶されている
格納位置情報とを各ｉについて加算する加算手段
と、前記記憶手段に記憶されている格納位置情報
を第１番目の要素プロセツサに対して出力し、前
記加算手段の（ｉ−１）についての加算結果を第
ｉ番目の要素プロセツサに対して出力する加算結
果出力手段と、前記加算手段のＮについての加算
結果を用いて前記処理すべきデータの格納位置情
報を更新する更新手段とを具備している。

（作用）本発明によれば、前記要素プロセツサからのア
クセス要求を受け付けると、個数出力手段によつ
て同時にアクセス要求しているプロセツサの個数
が求められ、この個数がデータの格納位置に加算
されて処理すべきデータの格納位置情報が更新さ
れるので、当該格納位置情報を読出した要素プロ
セツサが次の書込みサイクルで格納位置情報を書
替える必要がなくなり、この従来の書込みサイク
ルに相当する期間に次のプロセツサのアクセス要
求に応答できる。従つて、本発明によれば、上記
格納位置情報の書替え時間の分だけ同期処理が高
速化され、マルチプロセツサシステムの処理効率
の向上に寄与することになる。

（実施例）以下、図面に基づいて本発明の実施例について
説明する。

第１図は本発明の一実施例に係る並列処理制御
装置の構成を示す図である。この並列処理制御装
置１０は、４つの要素プロセツサP₁，P₂，P₃，
P₄と接続され、これら４つの要素プロセツサP₁
〜P₄を制御するもので、入力レジスタ１１₁〜１
１₄と、制御メモリ１２と、４つの加算器１３₁〜
１３₄と、記憶部１４と、出力レジスタ１５₁〜１
５₄とにより構成されている。

即ち、各要素プロセツサP₁〜P₄から出力され
るアクセス要求信号は、アクセス要求時は“１”、
その他の“０”となる１ビツトの信号で、それぞ
れに対応した入力ポート１１〜１４を介して入力
レジスタ１１₁〜１１₄にそれぞれ入力されてい
る。入力レジスタ１１₁〜１１₄からの各１ビツト
の出力は、制御メモリ１２の４ビツトの入力とし
て与えられている。制御メモリ１２は、第２図に
示すような入力対出力の関係を持つテーブルであ
る。即ち、出力M₁は、１ビツトの出力で、プロ
セツサP₁がアクセス要求を出している時“１”、
それ以外の時“０”となる。出力M₂は、２ビツ
トの出力で、プロセツサP₁，P₂のうちアクセス
要求を出しているプロセツサの台数を示してい
る。出力M₃は、２ビツトの出力で、プロセツサ
P₁，P₂，P₃のうちアクセス要求を出しているプ
ロセツサの台数を示している。出力M₄は、３ビ
ツトの出力で、プロセツサP₁，P₂，P₃，P₄のう
ちアクセス要求を出しているプロセツサの台数を
示している。これら制御メモリ１２の出力M₁〜
M₄は、加算器１３₁〜１３₄の一方の入力に与え
られている。加算器１３₄は、次の処理すべきデ
ータの格納番地の更新手段となるもので、その出
力は、記憶部１４に入力され、記憶部１４の内容
を更新する。記憶部１４は、16ビツトのレジスタ
で、処理すべきデータの格納番地が格納されてい
る。この記憶部１４の出力は、出力レジスタ１５
_１及び出力ポートO₁を介してプロセツサP₁に出力
されるとともに、４つの加算器１３₁〜１３₄の他
方の入力として与えられている。加算器１３₁，
１３₂，１３₃からの出力は、出力レジスタ１５₂，
１５₃，１５₄にそれぞれ与えられ、更に出力ポー
トO₂，O₃，O₄にそれぞれ介してプロセツサP₂，
P₃，P₄に出力されている。

即ち、出力ポートO₁には記憶部１４の内容が
そのまま出力されるので、プロセツサP₁は、他
のプロセツサP₂〜P₄がアクセス要求を出してい
るか否かに拘らず、常に記憶部１４が指す番地の
データの処理をすることになる。

また、出力ポートO₂には、加算器１３₁により
記憶部１４の内容と制御メモリ１２の出力M₁と
を加算した結果が出力されるので、プロセツサ
P₂は、プロセツサP₁がアクセス要求を同時に出
した時に記憶部１４の内容＋１番地のデータを処
理し、その他の場合には記憶部１４の内容が指す
番地のデータを処理する。

出力ポートO₃には、加算器１３₂により記憶部
１４の内容と制御メモリ１２の出力M₂とを加算
した結果が出力されるので、プロセツサP₃は、
プロセツサP₁及びP₂のうち、同時にアクセスを
要求を出力しているプロセツサの台数を、記憶部
１４の内容に加算した番地のデータを処理する。

更に、出力ポートO₄には、加算器１３₃により
記憶部１４の内容と制御メモリ１２の出力M₃と
を加算した結果が出力されるので、プロセツサ
P₄は、プロセツサP₁，P₂及びP₃のうち、同時に
アクセス要求を出力しているプロセツサの台数
を、記憶部１４の内容に加算した番地のデータを
処理する。

そして、記憶部１４には、制御メモリ１２の出
力M₄、即ちプロセツサP₁乃至P₄のうち、アクセ
ス要求を出力しているプロセツサ台数が、加算器
１３₄によつて、現在の記憶内容に加算されて新
たに格納される。これにより、記憶部１４の内容
が更新される。

この並列処理制御装置を用いた場合につき、各
プロセツサが記憶装置に格納されているデータを
漏れなく読込む場合の処理フローの例を第３図に
示す。この例では、各プロセツサは、処理すべき
データの個数を知つており、このデータの個数
と、並列処理制御装置の出力ポートから得た内容
（S1、S2）との大小を判定して（S3）、処理すべ
きデータのがまだあるのかどうかを判定し、処理
すべきデータがある場合には、データの読込み
（S4）と、その処理（S5）とを行なうようになつ
ている。この例からも分るように、並列処理制御
装置を使用することにより、各プロセツサは、他
のプロセツサの動作を考慮する必要がなく、同期
処理を含めた総合的な記憶装置へのアクセスを高
速化できる。

第４図に本発明の他の実施例を示す。

この並列処理制御装置２０は、４台の要素プロ
セツサP₁〜P₄と、共有バス３０を介して接続さ
れている。

並列処理制御装置２０は、インターフエース回
路２１と、アドレス選択回路２２、記憶部２３及
び加算器２４とが内部バス２５を介して接続され
た構成となつている。

処理すべきデータの格納位置を記憶する記憶部
２３は、レジスタフアイルで構成れており、各レ
ジスタには共有バス３０上の異なるアドレスが割
当てられている。従つて、並列に処理すべきデー
タの集まりが種々ある場合に、それぞれのデータ
の集まりについて、次に処理すべきデータの格納
位置を記憶することができる。

要素プロセツサからのアクセス要求は、処理し
たいデータの格納位置を記憶しているレジスタフ
イルム内のレジスタに対する読出しを実行するこ
とにより行ない、データの格納位置はその読出し
の実行によつて読出されるデータとして与えられ
る。即ち、あるプロセツサPiから記憶部２３であ
るレジスタフアイル内のレジスタに対して読出し
要求を発すると、そのレジスタの内容は、まず、
並列処理制御装置２０の内部バス２５を介してイ
ンターフエース回路２１に送られ、更に共有バス
３０を介して読出し要求を出したプロセツサPiに
送られる。それと同時に、並列処理制御装置２０
の内部バス２５を介して加算器２４にレジスタの
内容が送られ、加算器２４に１を加えた結果を、
再び同じレジスタに格納するように制御する。

本実施例では、加算器２４が次の処理すべきデ
ータの格納番地の更新手段であり、この加算器２
４による加算動作によつて同期処理を高速化させ
ることができる。

また、この実施例では、共有バス３０を介して
並列処理制御装置３０と各要素プロセツサP₁〜
P₄とを結合しているため、図示しない調停手段
の働きにより、２つ以上のアクセス要求が同時に
並列処理制御装置に到着することはない。従つ
て、アクセス要求に対応する読出しのサイクル内
で、上記の処理を完結することにより、複数プロ
セツサからのアクセス要求に矛盾なく、データ格
納位置を与えることができる。この実施例は、上
記第１の実施例と比較して、プロセツサから同時
にアクセス要求を出せない欠点を有しているが、
実現に要するハードウエア量の点で格段に有利で
ある。また、共有メモリを使用した同期処理と比
較して要素プロセツサからの排他制御が必要ない
で、同期処理に要する時間を短かくできる。

［発明の効果］以上述べたように、本発明によれば、要素プロ
セツサが処理すべきデータの格納位置情報を読出
すのに伴つて、前記更新手段が、前記処理すべき
データの格納位置情報を更新するので、従来のよ
うに格納位置情報の書替え時間を必要とせず、そ
の分だけ同期処理が高速化される。このため、マ
ルチプロセツサシステムの処理効率の向上に寄与
することができる。

【図面の簡単な説明】

第１図は本発明の一実施例に係る並列処理制御
装置を用いた並列処理システムのブロツク図、第
２図は同並列処理制御装置における制御メモリの
内容を示す図、第３図は同並列処理システムにお
けるプロセツサの処理フローを示す図、第４図は
本発明の他の実施例に係る並列処理制御装置を用
いた並列処理システムのブロツク図、第５図はデ
ータベースにおける検索処理の例を説明するため
のブロツク図、第６図は従来の同期処理を含む並
列処理のタインミング図である。１……記憶装置、１０，２０……並列処理制御
装置、１１₁〜１１₄……入力レジスタ、１２……
制御メモリ、１３₁〜１３₄，２４……加算器、１
４，２３……記憶部、１５₁〜１５₄……出力レジ
スタ、２１……インターフエース回路、２２……
アドレス選択回路、２５……内部バス、３０……
共有バス、P₁〜P₄……要素プロセツサ。

Claims

【特許請求の範囲】１Ｎ個の要素プロセツサを含むマルチプロセツ
サシステムに接続され、アクセス要求の出力され
た前記要素プロセツサに対し、処理すべきデータ
の格納位置情報を与える並列処理制御装置であつ
て、次にアクスセ要求があつたときに出力する前記
処理すべきデータの格納位置情報を記憶する記憶
手段と、前記要素プロセツサからのアクセス要求を受け
付けると、ｉを１からＮまでの整数とするとき、
第１番目の要素プロセツサから第ｉ番目の要素プ
ロセツサまでの内で、同時にアクセス要求してい
るプロセツサの個数を各ｉについて求める個数出
力手段と、この個数出力手段で求められた個数と前記記憶
手段に記憶されている格納位置情報とを各ｉにつ
いて加算する加算手段と、前記記憶手段に記憶されている格納位置情報を
第１番目の要素プロセツサに対して出力し、前記
加算手段の（ｉ−１）についての加算結果を第ｉ
番目の要素プロセツサに対して出力する加算結果
出力手段と、前記加算手段のＮについての加算結果を用いて
前記処理すべきデータの格納位置情報を更新する
更新手段とを具備したことを特徴とする並列処理制御装置。