JPH01191252A - 負荷分散制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （１）発明の属する技術分野 本発明はネットワーク結合型の並列プロセッサシステム
における負荷分散制御方式に関するものである。

（２）従来の技術 ＬＳＩ技術の発展に支えられ、最近多数の処理要素をネ
ットワーク状（処理要素相互をリンクにより結合するも
ので、リング、アレイ、トリー。

ハイパキューブ等各種の結合形態がある）に結合した並
列プロセッサシステムの研究・開発が活発化してきてい
る。このような並列プロセッサシステムの応用には、各
処理要素が割り当てられた仕事を処理する過程で次の新
たな仕事を発生し、かつその仕事がいずれの処理要素で
処理されてもよいような応用分野がある（自然言語処理
や知識処理等のＡＩ処理に多くみられる）、この種の応
用では、いかにして各処理要素に常時、均等に仕事（以
下負荷と呼ぶ）を割り当てるか、すなわち各処理要素が
休止状態にならないようにいかに負荷を分散するかが大
きな課題となる。この制御は一般に負荷分散制御と呼ば
れている。

従来この種のシステムにおける負荷分散制御は。

処理要素とは独立に負荷分散制御装置を設け、該装置が
全処理要素の負荷の状況を監視し、いずれかの処理要素
の負荷が重くなった場合には負荷が軽い（負荷待ちの休
止状態を含む）処理要素にそれを分散させることにより
実現されていた。ここで、具体的な負荷の分散法として
は、該制御装置が負荷が重い処理要素から実際に負荷を
収集して負荷の軽い処理要素にそれを分配する方法と、
該制御装置が負荷の重い処理要素に負荷の軽い処理要素
番号を知らせて実際の負荷の移動に当ってはその間の処
理要素を中継して行う（処理要素間のリンクを利用）方
法とがある。

従来の負荷分散制御は以上のように、専用の装置が集中
的に負荷の状態の監視、具体的な負荷の収集・分配、あ
るいは分散の指示を行っているため、これらの動作は各
処理要素に対し逐次的にしかなされず、システムにおけ
る処理要素数が多くなった場合にはこの負荷分散制御が
大きなオーバヘッドとなり、処理要素数比例のシステム
性能が得られないという欠点があった。

（３）発明の目的 本発明の目的は１以上の欠点を解決し、処理要素数が多
いシステムにおいても迅速な負荷分散を実現できる制御
方式を提供することにある。

（４）発明の構成 （４−１）　　発明の特徴と従来の技術との差異本発明
は、負荷の監視１分散制御機構を各処理要素内に設け、
各処理要素が該機構により局所的な負荷分散を並列的に
行うことにより、実効的にシステム全体の負荷分散を実
現するものである。

具体的には、各処理要素は該機構により、自内の負荷が
該処理要素にリンクにより物理的に結合されているすべ
ての処理要素の最小負荷より２以上大きいときのみ最小
負荷を持つ処理要素に対し１つの負荷を分散させる。す
なわち１本発明は負荷分散を局所的、並列的、かつ迅速
、単純に制御することを最も主要な特徴とする。従来の
技術とは負荷分散制御用の機構の設置態様、負荷状態の
監視Ｂ様、具体的な負荷の分散態様が異なる。

（４−２）　　実施例 第１図は本発明をリング結合型の並列プロセッサシステ
ムに適用した場合の実施例であり２図ではそのうちの３
つの処理要素のみを示している。

図中、１は処理要素、２は負荷を処理し又負荷を発生す
るプロセッサ、３は処理待ちの負荷を蓄積するバッファ
（プロセッサ２で発生されただちに処理できない負荷は
ここに収容しておく）、４はバッファ３に蓄積されてい
る負荷の数を常時計数し表示する負荷量表示手段、５は
自処理要素内の負荷量表示手段４の示す値と該処理要素
にリンクにより物理的に結合されたすべての処理要素（
以下隣接処理要素と呼ぶ）内の負荷量表示手段４の値と
を比較し、自内の負荷量表示手段４の示す値がすべての
隣接処理要素内の負荷量表示手段４のその最小値を示す
方向の隣接処理要素に対し１つの負荷を分散すべく負荷
送受手段６に指示する分散方向決定手段である。負荷送
受手段６は分散方向決定手段５によって指定された方向
の隣接処理要素に負荷分散のため、バッファ３に蓄積さ
れている１つの負荷を送出し、あるいは送出されてきた
負荷を受信しバッファ３に収容する。

第２図は本発明の動作説明図であり、四角で示した処理
要素内の数値はその処理要素の負荷の数（負荷量表示手
段４の示す値）を表わしている。

図中のＰＥ、は夫々上記処理要素１に対応するものであ
る。

以下２両図に従って本発明の詳細な説明する。

本発明において負荷分散制御は全処理要素で非同期的に
行われてもよいが、ここでは説明を簡単にするため全処
理要素で一斉にかつ一定周期で同期をとって行うものと
する。時刻ｔ０では各処理要素の負荷は第２図ｉ）の状
態であったとする。このとき処理要素ＰＥＩの分散方向
決定手段５は。

自己の負荷が「５」で、隣接処理要素の負荷の最小値「
Ｏ」　（処理要素ＰＥ、の負荷）より２以上大きいため
、負荷送受手段６に対し処理要素ＰＥ、に１だけ負荷を
分散するよう指示する。同しく、処理要素ＰＥ、、ＰＥ
８の分散方向決定手段５はそれぞれ処理要素ＰＥ、、Ｐ
Ｅ７への負荷の分散を指示する。これに対し、処理要素
ＰＥＧ。

ＰＥｘ、ＰＥｑ、ＰＥｓ、ＰＥｂ、ＰＥｖ、ＰＥｑは白
肉の負荷が隣接処理要素の負荷より２以上大きくないた
め、それぞれの分散方向決定手段５は負荷の分散を負荷
送受手段６に指示しない。

従って１時刻１．においては第２図１１）のような負荷
状態となる。次にこの状態では、処理要素ＰＥ１．ＰＥ
、がそれぞれ処理要素ＰＥ２．ＰＥ、への負荷の分散を
指示される。この負荷分散の後は同図ｉｉｉ　）の負荷
状態となり、このときは処理要素ＰＥ４から処理要素Ｐ
Ｅ３への負荷分散が行われ。

最終的には同図ｉｖ）のほぼ平均化された負荷状態とな
る。

以上説明したように木方式では、全処理要素がそれらの
隣接処理要素間で局所的な負荷分散を並列的に実施する
ため、従来の集中的、逐次的な制御方式に比べ、システ
ム全体の負荷分散処理が大幅に迅速化される。さらにこ
の効果はシステム内の処理要素数が増加する程大きくな
る。なお１以上の説明ではその簡単化のためリング結合
型の並列プロセッサシステムを例としたが、アレイ、ハ
イパキューブ、トリー等、他のネットワーク型並列プロ
センサにおいても本発明を適用できることはいうまでも
ない。又、第１図ではすべての手段をハードウェアで実
現する如く表現しているが。

これらの機能・手順をプログラム化しプロセッサ２にこ
れを実行させるようにしても本発明の効果を損うもので
はない。又、ここでは具体的な負荷の移動、隣接処理要
素への負荷の値の通知は、処理要素間のリンクを利用し
、それ専用の信号線を設けないことを想定している。

第３図は本発明の他の実施例であり、　　１．　４゜５
は第１図と同じ、７は負荷量表示手段４の示す値が所定
値（Ａ）以下であることを検出する小負荷検出手段、８
は同じく同手段が示す値が所定値「（Ａ）＋ネットワー
クの最大距１（Ｌ）＋１４以上であることを検出する大
負荷検出手段である。

ここでネットワークの最大距離（Ｌ）とは、ネットワー
ク型の並列プロセッサシステムにおける任意の２つの処
理要素間の距離（その間にある処理要素の数＋１）の最
大値である。例えば、処理要素数がＮの場合、リング型
ではＮが偶数のときＬ＝Ｎ／２．奇数のときＬ＝　（Ｎ
−４）／２であり、トーラス結合された２次元アレイ型
ではＬ＝５、ハイパキューブ型ではＬ−１ｏｇ、Ｎであ
る。

又、９．１０は−１ｒｅｄ　　ＯＲ線、１１はＷｉｒｅ
ｄＯＲ線９．１０の論理積をとり１両者がａｃｔｉｖｅ
になっているときのみ分散方向決定手段５をａｃｔｉｖ
ｅにする負荷分散制御の起動手段である。

一般に並列処理システムでは、全処理要素の負荷が如何
に不均一であっても、それらが大きい場合には負荷分散
を行う効果は少ない、なぜなら負荷分散の目的は休止状
態の処理要素を減少させることであり、全処理要素が所
定の負荷を持っていればその時点では負荷分散の必要性
はないといえるからである。第３図の実施例は、この点
に注目し、各処理要素の負荷が所定値Ａ以下になった場
合のみ負荷分散を実施しようとするものである（第１図
の場合には第２図のｉｖ）の状態になっても実際の負荷
の移動以外のすべての動作は一定周期で行われる）。さ
らに本方式では、負荷の差が２以上でないと負荷分散を
行わないため最悪の場合、全処理要素の最大負荷と最小
負荷との差がネットワークの最大距離（Ｌ）以下になっ
たとき負荷分散が行われない状態になることがある０例
えば第２図のｉｖ）では最大負荷と最小負荷との差が２
で平衡状態となっている（この例の場合には。

Ｌ＝５であるから最悪この差が５でも負荷分散が行われ
ないことがある。例えば処理要素ＰＲ，〜ＰＥ、の負荷
がそれぞれ０，１，２，３，４．５゜４、　３．　２．
　１になったとき）。従って、負荷分散を実施するには
もう一つの条件、すなわち全処理要素の最大負荷と最小
負荷との差がＬ＋１以上であることが必要となる。

第３図の実施例はこれら２つの条件、すなわち。

システムでの最小負荷が所定値（Ａ）以下であり。

かつ最大負荷が（Ｌ＋Ａ＋１）以上のときのみ。

起動手段１１により分散方向決定手段５をａｃｔｉｖｅ
にし負荷分散を実行するものである。具体的には本実施
例での負荷分散制御は、全処理要素のうちいずれかの処
理要素の小負荷検出手段７がＡ以下の小負荷を検出し、
かついずれかの処理要素の大負荷検出手段８が（Ｌ＋Ａ
＋１）以上の大負荷を検出したとき、それぞれ−１ｒｅ
ｄ　　ＯＲ線９，１０がａｃｔｉｖｅとなり、起動手段
１１を介し１分散方向決定手段５がａｃｔｉｖｅとなる
ことにより行われる。従って、同図の実施例では負荷分
散が必要かつ有効な場合のみ、それが実施されるため負
荷分散制御のオーバヘッドが第１図の実施例以上に減少
することが可能となる。

なお２木刀式をプログラムによりソフト的に実現しよう
とする場合には、負荷分散処理を割込み処理ルーチンと
し、起動手段１１がａｃｔｉｖｅになったときプロセッ
サ２に割込みを発生しこれに負荷分散処理を行なわせ、
それ以外のときはプロセッサ２に一般の処理だけを行わ
せるように動作させてもよい。

（５）発明の詳細 な説明したように１本発明によれば、負荷の監視１分散
制御機構を並列プロセッサシステムを構成する全処理要
素に設け、全処理要素がそれらの隣接処理要素との間だ
けで負荷の大小を比較し。

自己の負荷が２つ以上大きいときのみ隣接処理要素に負
荷を移動させる局所的な負荷分散を行うため、システム
全体としては負荷分散が並列的に行われることになりそ
の迅速化が達成されるという利点がある。すなわち、従
来の集中的、逐次的な負荷分散制御に比べそのオーバヘ
ッドを大幅に削減でき、処理要素数相応の高いシステム
性能を実現できる利点がある。

【図面の簡単な説明】

第１図は本発明をリング結合型の並列プロセッサシステ
ムに適用した場合の実施例、第２図ば第１図の実施例の
動作説明図、第３図は必要かつ有効な期間のみ負荷分散
制御を行うように構成した他の実施例である。 ■＝処理要素 ２：プロセッサ ３：バッファ ４：負荷量表示手段 ５：分散方向決定手段 ６：負荷送受手段 ７：小負荷検出手段 ８：大負荷検出手段 ９、　１０　：　Ｗｉｒｅｄ　　ＯＲ線１１：起動手段 特許出願人　　日本電信電話株式会社

Claims (2)

【特許請求の範囲】
1. （１）多数の処理要素がネットワーク状に結合された並
   列プロセッサシステムにおいて、 各処理要素に、 処理待ちになっている負荷の数を常時、係数・表示する
   負荷量表示手段、 自処理要素内の該負荷量表示手段の示す値と該処理要素
   に物理的に結合されているすべての少なくとも隣接処理
   要素内の負荷量表示手段の示す値とを比較し、自処理要
   素内の負荷をいずれの隣接処理要素に分散するか決定す
   る分散方向決定手段 および隣接処理要素に自処理要素内の負荷を送出し、あ
   るいはそれらからの負荷を受け取る負荷送受手段を設け
   、 各処理要素に、自内の負荷量表示手段の示す値がすべて
   の隣接処理要素内の負荷量表示手段の示す値の最小値に
   対して予め定めた値以上大きいときのみ、その最小値を
   示す方向の隣接処理要素に対し１つの負荷を分散させる ことを特徴とする負荷分散制御方式。
2. （２）特許請求の範囲１における各処理要素に、自内の
   負荷量表示手段の値が所定値（Ａ）以下になったことを
   検出する小負荷検出手段および所定値「（Ａ）＋ネット
   ワークの最大距離（Ｌ）＋１」以上になったことを検出
   する大負荷検出手段を設け、 全処理要素のうちいずれかの処理要素の負荷が該所定値
   （Ａ）以下になり、かつ全処理要素のうちいずれかの処
   理要素の負荷が（Ａ＋Ｌ＋１）以上になった場合のみ、
   特許請求の範囲１記載の制御を行わせる ことを特徴とする負荷分散制御方式。