JPH04223548A - 並列処理システムの負荷配分方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、独立に実行可能な多数
のタスクを複数のプロセッサで並列処理するシステムに
おいて、各プロセッサにタスクを配分する方法に関し、
特に、プロセッサのアイドル時間の総和を許容限度以下
にすることを保証しながら、多数のタスクを少ない回数
で配分するため、タスクの配分単位の決定方法に関する
ものである。

【０００２】

【従来の技術】図３に一般的な並列処理システムの概念
図を示す。図中、１−１〜１−ＳはＳ個（Ｓ≧１）のタ
スク源で、独立に実行可能なＮ個（Ｎ≧Ｓ）のタスクを
生成する。３−１〜３−Ｐは処理能力が均一なＰ個（Ｐ
＞１）のプロセッサで、複数のタスクを並列処理する。 ２はタスク配分手段であり、個々のプロセッサ３−１〜
３−Ｐに所望の個数のタスクを配分する。

【０００３】このような並列処理システムの負荷配分方
法は、例えばＹｕｎｇ−Ｔｅｒｎｇ　Ｗａｎｇ，Ｒｏｂ
ｅｒｔ　Ｊ．Ｔ．Ｍｏｒｒｉｓ：Ｌｏａｄ　Ｓｈａｒｅ
ｉｎｇ　ｉｎ　ＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ
，ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍ
ｐｕｔｅｒｓ，Ｖｏｌ．Ｃ−３４，Ｎｏ．３，ｐｐ．２
０４−２１７，Ｍａｒ．１９８５で分類、整理されてい
るように、タスク源主導型とプロセッサ主導型に大別さ
れる。

【０００４】タスク源主導型は、各プロセッサ３−１〜
３−Ｐにタスクキューがあり、各タスク源１−１〜１−
Ｓでタスク生成されると、タスク配分手段２を用いて、
どのプロセッサにタスクを割り当てるかを決定する方法
である。配分先の決定方法としては、Ｓ＞Ｐの場合にタ
スク源をグループ分して１グループに１つのプロセッサ
を割り当てる方法（ｓｏｕｒｃｅ　ｐａｒｔｉｔｉｏｎ
）、一様分布の乱数を用いてタスクのプロセッサへの割
り当てを決定する方法（ｒａｎｄｏｍ　ｓｐｌｉｔｔｉ
ｎｇ）、各プロセッサに順にタスクを割り当てる方法（
ｃｙｃｌｉｃ　ｓｐｌｉｔｔｉｎｇ）、各プロセッサの
タスクキューの内最もタスク数の少ないところにタスク
を割り当てる方法（ｊｏｉｎ　ｔｈｅｓｈｏｒｔｅｓｔ
ｑｕｅｕｅ）などがある。

【０００５】プロセッサ主導型は、各タスク源１−１〜
１−Ｓにタスクキューがあり、各プロセッサ３−１〜３
−Ｐが空き状態になると、タスク配分手段２を用いて、
どのタスク源からタスクを取り出すかを決定する方法で
ある。配分元の決定方法としては、（Ｓ＜Ｐ）の場合に
プロセッサをグループ分けして１つのグループが１つの
タスク源からのタスクを処理する方法（ｓｅｒｖｅｒ　
ｐａｒｔｉｔｉｏｎ）、一様分布の乱数を用いてタスク
を取り出すタスク源を決定する方法（ｒａｎｄｏｍ　ｓ
ｅｒｖｉｃｅ）、各プロセッサがタスク源を順に回る方
法（ｃｙｃｌｉｃ　ｓｅｒｖｉｃｅ）、各タスク源のタ
スクキューの内最もタスク数の多いところからタスクを
取り出す方法（ｓｅｒｖｅ　ｔｈｅ　ｌｏｎｇｅｓｔｑ
ｕｅｕｅ）などがある。

【０００６】このような並列処理システムで大量のタス
クを処理する場合に、タスク数Ｎが固定であっても、タ
スクによって処理時間が異なる場合がある。代表的な例
としては、選択条件を満足するか否かによってデータ毎
の処理時間が異なるデータベス処理が挙げられる。この
場合には、各プロセッサに同数のタスクを配分するｒａ
ｎｄｏｎ　ｓｐｌｉｔｔｉｎｇ法やｃｙｃｌｉｃ　ｓｐ
ｌｉｔｔｉｎｇ法では、プロセッサによって処理の終了
時間が異なり、配分された全てのタスクの処理を早く終
えたプロセッサがアイドル状態になって、Ｎ個のタスク
の実行開始から終了までの経過時間が長くなる原因とな
る。そのため、処理が速く進んでいるプロセッサにタス
クを割り当てていくｊｏｉｎ　ｔｈｅ　ｓｈｏｒｔｅｓ
ｔ　ｑｕｅｕｅ法や、早く処理を終えたプロセッサが次
に処理するタスクを取り出していくプロセッサ主導型の
上記各方法のように、実行時のプロセッサの処理状況に
関する情報を用いて負荷配分を行う必要がある。この場
合、配分された全てのタスクを早く終えたプロセッサが
アイドルになる時間は、１タスクの処理時間以下とする
ことができる。

【０００７】しかし、従来は、１タスクを単位として配
分していたことから、負荷配分に必要な情報の収集や通
信のオーバヘッド、複数のプロセッサが同一のタスクキ
ューへアクセスすることを調停する排他制御によるオー
バヘッドおよびプロセッサの待ち時間が大きくなる問題
があった。この問題を解決する手法として、固定数Ｂ（
Ｂ≧１）個のタスクをまとめて割り当てるか又は取り出
す方法が前記文献に示されている。

【０００８】

【発明が解決しようとする課題】上記負荷配法では、タ
スクの配分単位Ｂを小さくすると、特に１タスク毎に負
荷配分すると、アイドル時間の総和は小さくできるが、
タスクの配分回数が多く、通信や排他制限のオーバヘッ
ドおよびプロセッサ間の競合が大きくなり、逆に、タス
クの配分単位Ｂを大きくすると、アイドル時間の総和が
大きくなるという問題がある。

【０００９】本発明の目的は、プロセッサのアイドル時
間の総和が許容限度以下になることを保証したままで、
タスクの配分回数を少なくし、上記オーバヘッドや競合
を少なくすることにある。

【００１０】

【課題を解決するための手段】上記目的を達成するため
に、本発明は、Ｓ個（Ｓ≧１）のタスク源と、処理能力
が均一なＰ個（Ｐ＞１）のプロセッサと、Ｓ個のタスク
源から生成されるＮ個（Ｎ≧Ｓ）の独立に実行可能なタ
スクについて、個々のプロセッサに所望の個数のタスク
を配分するタスク配分手段とを具備した並列処理システ
ムにおいて、タスク配分手段は、従来は固定であったタ
スクの配分単位を、１タスクあたりの処理時間の上限と
下限の比と、アイドル時間の総和の許容限度と、Ｓ個の
タスク源の未配分タスク数と、Ｐ個のプロセッサの未処
理タスク数とから、各プロセッサ配分できるタスク数の
上限値を決定することによって、可変としたことである
。

【００１１】

【作用】本発明の負荷配分法では、タスクの配分単位を
可変とし、これからタスクを配分するプロセッサの１つ
に配分されるタスクは全て処理時間が上限値のタスクで
あり、それ以外のプロセッサに配分されるタスクは全て
、処理時間が下限値であるという、アイドル時間の総和
が最大になる場合でも、アイドル時間の総和を指定した
許容限度以下にできるという条件を満たすタスク数の上
限をタスクの配分単位とする。これによって、最初はタ
スクの配分単位を大きくして配分回数を少なくすること
により負荷配分のオーバヘッドおよびプロセッサ間の競
合を小さくできる。一方、処理が進行するに連れて、タ
スクの配分単位を小さくすることにより、アイドル時間
の総和を小さくできる。

【００１２】

【実施例】図１は本発明の一実施例を示す図で、１はタ
スク源、２はタスク配分手段、３−１〜３−Ｐはプロセ
ッサである。ここでは、データベースの検索を例にとり
、記憶装置４−１〜４−Ｓからデータを１つ取り出し、
選択条件を満すデータであれば出力するという処理を１
つのタスクとする。従って、記憶装置４−１〜４−２が
タスク源１となる。

【００１３】タスク配分手段２は、記憶装置４−１〜４
−Ｓの未だどのプロセッサにも配分されていないタスク
数（未配分タスク数）を示す数値をそれぞれ格納してい
る未配分タスク数格納手段５−１〜５−Ｓ、各プロセッ
サ３−１〜３−Ｐに配分されてはいるが未だ処理されて
いないタスク数（未処理タスク数）を示す数値をそれぞ
れ格納している未処理タスク数格納手段６−１〜６−Ｐ
、タスク配分元のタスク源（ここでは記憶装置４−１〜
４−Ｓ）を決定する配分元決定手段７、タスク配分先の
プロセッサ３−１〜３−Ｐを決定する配分先決定手段８
、及び、配分するタスク数を決定する配分タスク数決定
手段９で構成される。未配分タスク数格納手段５−１〜
５−Ｓに格納されている数値はそれぞれ、記憶装置４−
１〜４−Ｓから未配分タスクが読み出される時に更新さ
れる。また、未処理タスク数格納手段６−１〜６−Ｐに
格納されている数値はそれぞれ、プロセッサ３−１〜３
−Ｐが未処理タスクを取り出す時およびプロセッサ３−
１〜３−Ｐが未処理タスクを処理する時に更新される。 配分元決定手段７、配分先決定手段８、配分タスク数決
定手段９の実体はプログラムである。このうち、配分元
決定手段７と配分先決定手段８のプログラムが実行する
アルゴリズムとしては、前記従来技術に示した手法など
を適用できる。

【００１４】以下では、プロセッサ主導型におけるｓｅ
ｒｖｅ　ｔｈｅ　ｌｏｎｇｅｓｔ　ｑｕｅｕｅ法、及び
、タスク源主導型におけるｊｏｉｎ　ｔｈｅ　ｓｈｏｒ
ｔｅｓｔ　ｑｕｅｕｅ法の２種を用いて、本発明の実施
例を説明することにする。

【００１５】データベースの検索では、データの内容は
未知であるがタスクの処理内容は既知であるので、１タ
スクあたりの実行時間の上限と下限、あるいは、少なく
ともその比を前以て知ることができる。そこで、　　　
　　　　　Ｓ：タスク源 　　　　　　　　Ｐ：プロセッサ数 　　　　　　　　Ｔｍａｘ：１タスクあたリの実行時間
の上限　　　　　　　　Ｔｍｉｎ：１タスクあたりの実
行時間の下限　　　　　　　　Ｔｋ：アイドル時間の総
和の許容時間（ただしＴｋ≧Ｔｍａｘ×（Ｐ−１））よ
り 　　　　　　　　α＝Ｔｋ／Ｔｍｉｎ　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　（１）　　　　　　　　β＝（
Ｔｍａｘ／Ｔｍｉｎ）×（Ｐ−１）＋１　　　　　　　
　　　　　　　　　　　　　　　（２） をあらかじめ計算しておいて、上記α、βと　　　　　
　　　ｍｉ：プロセッサｉの未処理タスク数（ｉ＝１，
２，…Ｐ）　　　　　　　　ｎｉ：タスク源ｉの未配分
タスク数の総和（ｉ＝１，２，…Ｓ）からプロセッサｉ
に配分できるタスク数の上限ｂｉを

【数１】 で計算する。

【００１６】まず、プロセッサ主導型制御との組み合わ
せ例として、配分元の決定に各タスク源のタスクキュー
の内最もタスク数の多いところからタスクを取り出すｓ
ｅｒｖｅｔｈｅ　ｌｏｎｇｅｓｔ　ｑｕｅｕｅ法を用い
た場合について説明する。

【００１７】処理開始前に予め、式（１），（２）のα
およびβを算出しておく。処理が開始されると、タスク
を未だ取り出していないプロセッサあるいは取り出した
タスクの処理を全て終えたプロセッサがタスク配分手段
２に制御を渡す。この場合のタスク配分手段２の処理順
を図２（ａ）に示す。

【００１８】取り出したタスクの処理を全て終えたプロ
セッサが自分でタスクを取り出すので、ステップ１０１
の配分先決定手段８の処理は素通りである。配分先のプ
ロセッサの番号をｉとする。

【００１９】ステップ１０２では、配分タスク数決定手
段９が、未配分タスク数格納手段５−１〜５−Ｓから読
み込んだ記憶装置４−１〜４−Ｓの未配分タスク数ｎｋ
と、未処理タスク数格納手段６−１〜６−Ｐから読み込
んだプロセッサ３−１〜３−Ｐの未処理タスク数ｍｊと
、あらかじめ算出しておいたαとβとから、プロセッサ
ｉが取り出すタスク数ｂｉを式（３）で算出する。ここ
で、ｍｉ＝０であるから、式（３）の−ｍｉの計算は不
要である。

【００２０】ステップ１０３では、配分元決定手段７が
未配分タスク数格納手当５−１〜５−Ｓの数値を読み込
み、記憶装置４−１〜４−Ｓの未配分タスク数ｎｋの最
も多いタスク源を選択する。

【００２１】ステップ１０４では、配分元決定手段７が
上記決定したタスク源からｂｉ個のタスクを取り出し、
プロセッサｉに渡す。なお、タスクの取り出された未配
分タスク数格納手段の数値はｂｉだけ減算される。

【００２２】このようにして、プロセッサｉは、取り出
されたタスクを順次実行し、タスクがなくなると、再び
タスク配分手段２に制御を渡す。これをタスクがなくな
るまで繰り返す。

【００２３】次に、タスク主導型制御との組み合わせ例
として、配分先の決定に各プロセッサのタスクキューの
内最もタスク数の少ないところにタスクを割り当てるｊ
ｏｉｎ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｑｕｅｕｅ法を用
いた場合も説明する。

【００２４】ここでは、記憶装置４−１〜４−Ｓは制御
用プロセッサ付きの磁気ディスクであるとする。上記ｓ
ｅｒｖｅ　ｔｈｅ　ｌｏｎｇｅｓｔ　ｑｕｅｕｅ法の例
と同様に、処理開始前に予め、式（１）、（２）のαお
よびβを算出しておく。処理が開始されると、制御用プ
ロセッサは磁気ディスクから複数個、例えば１トラック
分のデータを読み込む。データが読み込まれると、制御
用プロセッサはタスク配分手段２に制御を渡す。この場
合のタスク配分手段２の処理手順２の処理手順を図２（
ｂ）に示す。

【００２５】データを読み込んだ制御用プロセッサ配分
元になるので、ステップ２０１の配分元決定手段７の処
理は素通りとなる。

【００２６】ステップ２０２では、配分先決定手段８が
、未処理タスク格納手段６−１〜６−Ｐの数値を読み込
み、プロセッサ３−１〜３−Ｐから未処理タスク数ｍｊ
の最少ないプロセッサを選択する。配分先のプロセッサ
の番号をｉとする。

【００２７】ステップ２０３では、配分タスク数決定手
段９が、未配分タスク数格納手段５−１〜５−Ｓから読
み込んだ記憶装置４−１〜４−Ｓの未配分タスク数ｎｋ
と、未処理タスク数格納手段６−１〜６−Ｐから読み込
んだプロセッサ３−１〜３−Ｐの未処理タスク数ｍｊと
、あらかじめ算出しておいたαとβとから、プロセッサ
ｉに割り当てるタスク数ｂｉを式（３）で算出する。そ
して、この算出したタスク数ｂｉを配分先決定手段８に
与える。

【００２８】ステップ２０４では、配分先決定８が、決
定されたプロセッサｉにｂｉ個のタスクを割り当てる。

【００２９】プロセッサは、割り当てられたタスクを順
次実行し、制御用プロセッサは、ディスクからデータを
読み込んでは、上記タスク配分手段２に制御を渡す。以
上の手順を全てのデータが読み込まれ、割り当てられる
まで繰り返す。

【００３０】最後に、具体例として、１０台のプロセッ
サが１万レコードのデータを全て記憶装置から取り出し
て、指定された条件を満たすレコードから指定されたフ
ィールドを取り出して出力する場合を示す。条件を満す
データは千レコードのデータの処理を１タスクとし、１
レコードの処理時間の内訳を、データの取り出しに１ｍ
ｓ、条件判定に１．５ｍｓ、指定されたフィールドの取
り出しと出力に５ｍｓとすると、タスクあたりの処理時
間の下限Ｔｍｉｎ＝２．５ｍｓ、タスクあたりの処理時
間の上限Ｔｍａｘ＝７．５ｍｓとなる。アイドル時間の
総和の許容限度を、保証できる最小値であるＴｋ＝Ｔｍ
ａｘ×（Ｐ−１）＝６７．５ｍｓとする。式（１）、（
２）を用いて、α＝２７．０，β＝２８．０を前以て計
算しておく。

【００３１】タスク源は１つとする。したがって、配分
元決定手段は不要である。配分先決定手段としては、未
処理タスクがなくなったプロセッサが自分でタスクを取
り出す方法を用いる。これは、プロセッサをグループ分
けして１つのグループが１つのタスク源からのタスクを
処理するｓｅｒｖｅｒ　ｐａｒｔｉｔｉｏｎ法のグルー
プ内の動作と同じである。

【００３２】処理開始時には、全てのプロセッサの未処
理タスク数が０であるから、全てのプロセッサ配分タス
ク数決定手段（配分タスク数決定プログラム）を起動し
て、配分タスク数ｂｉ（ｉ＝１，…，１０）を式（３）
で次のように決定する。ｂｉ＝（１００００＋０＋２７
．０）／２８．０−０＝３５８従って、全てのプロセッ
サが３５８個のタスクを取り出す。

【００３３】ここで、条件を満たすレコードが記憶装置
の前半に集中しており、条件を満たすレコードから取り
出されるとすると、プロセッサ１および２は、条件を満
たすデータを扱うタスクのみ３５８個取り出し、プロセ
ッサ３は条件を満たすデータを扱うタスクを２８４個、
満たさないデータを扱うタスクを７４個取り出し、プロ
セッサ４〜１０は条件を満たさないデータを扱うタスク
を３５８個取り出すことになる。未配分タスクは６４２
０個であり、これらは満たさないデータを扱うタスクで
ある。

【００３４】次の配分は、プロセッサ４〜１０が全ての
タスクの処理を終えた時点であり、プロセッサ１及び２
は１２０タスク目を処理中、プロセッサ３は条件を満た
すデータを扱うタスクから処理されたとすると１２０タ
スク目を処理中である。したがって、未処理タスク数は
７１７個であるから、配分タスク数ｂｉ（ｉ＝４，…，
１０）は 　　　　　　ｂｉ＝（６４２０＋７１７＋２７．０）／
２８．０−０＝２５５となり、プロセッサ４〜１０は、
２５５個のタスクを取り出す。

【００３５】以後、同様の手順を繰り返して、表１のよ
うにタスクを取り出していく。プロセッサ１〜２、プロ
セッサ４〜１０は同時に処理を終えるので、表１ではま
とめて記し、配分回数は１プロセッサに付き１回として
数えている。

【００３６】

【表１】

【００３７】表１のように、本発明の負荷配分法では、
最初は多くのタスクを配分し、徐々に配分量を少なくし
ていく。本数値例では、タスクの取り出し回数は延べ１
４７回になる。

【００３８】従来の負荷配分手法では一定量のタスクを
配分するため、アイドル時間の総和の許容限度を同じに
すると、一度に配分できるタスク数は高々１個であるか
ら、１００００回のタスク配分操作が必要になる。本発
明を用いることによって、配分タスク数の簡単な計算を
少数回実行するだけで、タスクの配分回数を極めて少な
くできることが判る。

【００３９】以上に示した本発明の実施例では、１タス
ク当たりの処理時間の上限、下限、アイドル時間の総和
の許容限度をすべて時間で与えたが、処理時間の上限と
下限の比Ｔｍａｘ／Ｔｍｉｎと許容限度と下限の比Ｔｋ
／Ｔｍｉｎで与えることもできる。

【００４０】また、ここでは、タスク源主導型のｊｏｉ
ｎ　ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｑｕｅｕｅ法、プロセ
ッサ主導型のｓｅｒｖｅｒ　ｐａｒｔｉｔｉｏｎ法およ
びｓｅｒｖｅ　ｔｈｅ　ｌｏｎｇｅｓｔ　ｑｕｅｕｅ法
の例を示したが、本負荷配分法では、各プロセッサに配
分するタスク数のみを規定しており、タスクの配分する
時刻、タスクの配分元のタスク源およびタスクの配分先
のプロセッサの決定法には依存しない。これらの決定に
は、任意の負荷配分法を使用できる。

【００４１】以上説明したように、本発明の負荷配分方
法によれば、配分タスク数の簡単な計算を少数回実行す
ることだけで、アイドル時間の総和を小さく抑えたまま
でタスクの配分回数を極めて小さくでき、負荷配分に要
する通信やタスクキューの排他制御のオーバヘッドおよ
びプロセッサ間の競合を小さくできる。したがって、従
来の負荷配分法よりも、処理終了までの時間を短縮でき
る。

【図面の簡単な説明】

【図１】本発明の一実施例を示す構成図である。

【図２】本発明の処理フローの一例で、（ａ）はプロセ
ッサ主導型、（ｂ）はタスク源主導型である。

【図３】一般的な並列処理システムの概念図である。

【符号の説明】

１　　タスク源 ２　　タスク配分手段 ３−１〜３−Ｐ　　プロセッサ ５−１〜５−Ｓ　　未配分タスク数格納手段６−１〜６
−Ｐ　　未処理タスク数格納手段７　　配分元決定手段 ８　　配分先決定手段 ９　　配分タスク数格納手段

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　タスクを生成するＳ個（Ｓ≧１）のタ
   スク源と、前記タスクを処理する処理能力が均一なＰ個
   （Ｐ＞１）のプロセッサとを具備した並列処理システム
   において、タスクをプロセッサで実行した場合の処理時
   間の上限値と下限値の比である処理時間比と、全てのタ
   スクの実行を完了するまでに前記プロセッサが該タスク
   に関する処理をしていない時間の和である全プロセッサ
   のアイドル時間の総和の許容限度が与えられたときに、
   該与えられた処理時間比と、アイドル時間の総和の許容
   限度と、前記Ｓ個のタスク源の未配分タスク数と、前記
   Ｐ個のプロセッサの未処理タスク数と、プロセッサ数と
   から、前記プロセッサ各々に配分できるタスク数の上限
   値を決定し、該上限値以下のタスクを、前記プロセッサ
   に割り当てるかあるいは前記タスク源から取り出すこと
   を特徴とする並列処理システムの負荷配分方法。