JPH03262074A - 疎結合並列計算機における負荷の動的均等化方法 - Google Patents
疎結合並列計算機における負荷の動的均等化方法Info
- Publication number
- JPH03262074A JPH03262074A JP2059858A JP5985890A JPH03262074A JP H03262074 A JPH03262074 A JP H03262074A JP 2059858 A JP2059858 A JP 2059858A JP 5985890 A JP5985890 A JP 5985890A JP H03262074 A JPH03262074 A JP H03262074A
- Authority
- JP
- Japan
- Prior art keywords
- job
- load
- processors
- processor
- slave
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000004891 communication Methods 0.000 claims description 19
- 238000000034 method Methods 0.000 claims description 13
- 238000012545 processing Methods 0.000 claims description 2
- 230000015572 biosynthetic process Effects 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 8
- 239000013256 coordination polymer Substances 0.000 description 5
- 238000007796 conventional method Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Landscapes
- Multi Processors (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
この発明は複数のプロセッサがネットワークにより接続
され、プロセッサの処理速度と比較して通信速度が遅い
ような疎結合並列計算機上で負荷を動的に均等化するた
めの疎結合並列計算機における負荷の動的均等化方式に
関するものである。
され、プロセッサの処理速度と比較して通信速度が遅い
ような疎結合並列計算機上で負荷を動的に均等化するた
めの疎結合並列計算機における負荷の動的均等化方式に
関するものである。
第５図は、例えば論文誌ＩＥＥＥ Ｔｒａｎｓａｃｔｉ
ｏｎｓ ｏｎＣｏｍｐｕｔｅｒｓ、 ｐａｇｅｓ １＋
０９８−１，１０９ Ｖｏｌ ３Ｂ、 Ｎｏ、 ８＋Ａ
ｕｇｕｓ”ｔ １９１３９にに、 Ｍ、 Ｂａｕｍｇａ
ｒｔｎｅｒ、及びＢ、Ｗ。
ｏｎｓ ｏｎＣｏｍｐｕｔｅｒｓ、 ｐａｇｅｓ １＋
０９８−１，１０９ Ｖｏｌ ３Ｂ、 Ｎｏ、 ８＋Ａ
ｕｇｕｓ”ｔ １９１３９にに、 Ｍ、 Ｂａｕｍｇａ
ｒｔｎｅｒ、及びＢ、Ｗ。
Ｗａｈ、らによって発表された論文”ＧＡＭＭＯＮ：
Ａ ＬｏａｄＢａｌａｎｃｉｎｇ Ｓｔｒａｔｅｇｙ
ｆｏｒ Ｌｏｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ
ｓ ｗｉｔｈ Ｍｕｌｔｉａｃｃｅｓｓ Ｎｅｔｉｖｏ
ｒｋｓ″の１，０９９ペジ右段上から１０行目以降に記
述されている、ローカルエリアネットワークによって接
続された分散コンピュータシステム上の負荷の動的均等
化方式の一例を示すものであり、第５図においてｌ〜４
はＣＰＵを、５〜８は各ＣＰＵ中の実行可能なジョブの
キュー（待ち行列）を、９〜１６は実行可能なジョブを
、１７は各ＣＰＵＩ〜４を接続するネットワークをあら
れす。
Ａ ＬｏａｄＢａｌａｎｃｉｎｇ Ｓｔｒａｔｅｇｙ
ｆｏｒ Ｌｏｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ
ｓ ｗｉｔｈ Ｍｕｌｔｉａｃｃｅｓｓ Ｎｅｔｉｖｏ
ｒｋｓ″の１，０９９ペジ右段上から１０行目以降に記
述されている、ローカルエリアネットワークによって接
続された分散コンピュータシステム上の負荷の動的均等
化方式の一例を示すものであり、第５図においてｌ〜４
はＣＰＵを、５〜８は各ＣＰＵ中の実行可能なジョブの
キュー（待ち行列）を、９〜１６は実行可能なジョブを
、１７は各ＣＰＵＩ〜４を接続するネットワークをあら
れす。
次に動作について説明する。第５図において、ＣＰＵＩ
はマスタープロセッサ、ＣＰＵ２からＣＰＵ４はスレー
ブプロセッサであるとする。ここで、負荷の分散はＣＰ
ＵＩが行う。まず、ＣＰＵ１は与えられた仕事を分割し
てジョブ９〜１３を生成する。これらはまずＣＰＵＩの
実行可能なジョブのキュー５に格納する。また、ＣＰＵ
２には別のジョブ１４．１５が、ＣＰＵ３には別のジョ
ブ１６が格納されており、ＣＰＵ４には実行可能なジョ
ブは格納されていない。次に、マスタープロセッサＣＰ
ＵＩはジョブ９〜１３をＣＰＵ２゜ＣＰＵ３．ＣＰＵ４
に割り付け、それぞれのプロセッサの負荷の均等化を行
う。
はマスタープロセッサ、ＣＰＵ２からＣＰＵ４はスレー
ブプロセッサであるとする。ここで、負荷の分散はＣＰ
ＵＩが行う。まず、ＣＰＵ１は与えられた仕事を分割し
てジョブ９〜１３を生成する。これらはまずＣＰＵＩの
実行可能なジョブのキュー５に格納する。また、ＣＰＵ
２には別のジョブ１４．１５が、ＣＰＵ３には別のジョ
ブ１６が格納されており、ＣＰＵ４には実行可能なジョ
ブは格納されていない。次に、マスタープロセッサＣＰ
ＵＩはジョブ９〜１３をＣＰＵ２゜ＣＰＵ３．ＣＰＵ４
に割り付け、それぞれのプロセッサの負荷の均等化を行
う。
負荷の均等化のために、マスタープロセッサは定期的に
全プロセッサの負荷を調べ、動的に検出した負荷の軽い
プロセッサに対してジョブを割り付ける。負荷の重さは
、実行可能なジョブのキュの長さでわかる。即ち、キュ
ーの長さが長いプロセッサは負荷が重くて忙しく、短い
プロセッサは負荷が軽くて暇である事を示している。マ
スタープロセッサは定期的にスレーブプロセッサのキュ
ーの長さをポーリングし、一番長さが短いプロセッサを
負荷の軽いＣＰＵと判断して、それらに負荷を分散させ
る。ここでは簡単のため、キュの長さが０のプロセッサ
が負荷が軽いものとする。
全プロセッサの負荷を調べ、動的に検出した負荷の軽い
プロセッサに対してジョブを割り付ける。負荷の重さは
、実行可能なジョブのキュの長さでわかる。即ち、キュ
ーの長さが長いプロセッサは負荷が重くて忙しく、短い
プロセッサは負荷が軽くて暇である事を示している。マ
スタープロセッサは定期的にスレーブプロセッサのキュ
ーの長さをポーリングし、一番長さが短いプロセッサを
負荷の軽いＣＰＵと判断して、それらに負荷を分散させ
る。ここでは簡単のため、キュの長さが０のプロセッサ
が負荷が軽いものとする。
第６図では、一定時間おきにマスタープロセッサ（ＣＰ
ＵＩ）が全プロセッサの実行可能なジョブのキューの長
さをポーリングして、負荷の軽いプロセッサを見つける
様子を示している。まず、マスタープロセッサは全プロ
セッサに対して通信メツセージ（ＲｅｑＬ： Ｒｅｑｕ
ｅｓｔ Ｑｕｅｕｅ Ｌｅｎｇｔｈ） １ Ｂ 。
ＵＩ）が全プロセッサの実行可能なジョブのキューの長
さをポーリングして、負荷の軽いプロセッサを見つける
様子を示している。まず、マスタープロセッサは全プロ
セッサに対して通信メツセージ（ＲｅｑＬ： Ｒｅｑｕ
ｅｓｔ Ｑｕｅｕｅ Ｌｅｎｇｔｈ） １ Ｂ 。
１９．２０を送出する。それらを受信した各スレーブプ
ロセッサは、自分の実行可能なジョブのキューの長さを
マスタープロセッサに対して通信メツセージ（ＲｅｑＬ
： Ｒｅｐｏｒｔ Ｑｕｅｕｅ Ｌｅｎｇｔｈ） ２１
。
ロセッサは、自分の実行可能なジョブのキューの長さを
マスタープロセッサに対して通信メツセージ（ＲｅｑＬ
： Ｒｅｐｏｒｔ Ｑｕｅｕｅ Ｌｅｎｇｔｈ） ２１
。
２２．２３を介して報告する。この例ではＣＰＵ２は２
を、ＣＰＵ３は１を、ＣＰＵ４は０をマスタープロセッ
サ（ＣＰＵＩ）に対して報告する。
を、ＣＰＵ３は１を、ＣＰＵ４は０をマスタープロセッ
サ（ＣＰＵＩ）に対して報告する。
全スレーブプロセッサからのＲｅｑＬメツセージがマス
タープロセッサに到着すると、その中からキューの長さ
が最小のものを見つける。この例では、ＣＰＵ４がキュ
ーの長さがＯであるので、ＣＰＵ４が一番負荷が軽い事
がわかる。
タープロセッサに到着すると、その中からキューの長さ
が最小のものを見つける。この例では、ＣＰＵ４がキュ
ーの長さがＯであるので、ＣＰＵ４が一番負荷が軽い事
がわかる。
第７図では、マスタープロセッサ（ＣＰＵＩ）がジョブ
９を一番負荷が軽いＣＰＵ４に割り付けた様子を示す。
９を一番負荷が軽いＣＰＵ４に割り付けた様子を示す。
この状態で全プロセッサは忙しい状態、即ち負荷が重い
状態となる。一定時間が経過した後にマスタープロセッ
サは再度負荷が軽いプロセッサを検出し、同様にしてジ
ョブ１０〜１３をスレーブプロセッサに割り付ける。以
上のようにして動的に負荷の均等化を行う。
状態となる。一定時間が経過した後にマスタープロセッ
サは再度負荷が軽いプロセッサを検出し、同様にしてジ
ョブ１０〜１３をスレーブプロセッサに割り付ける。以
上のようにして動的に負荷の均等化を行う。
従来の負荷の動的均等化方式は、以上のようにマスター
プロセッサは一定時間おきにスレーブプロセッサに対し
てポーリングせねばならず、一つのジョブを割り付ける
のに、プロセッサの台数をＮとした時に、（Ｎ−１）Ｘ
２個のメツセージ通信を必要とする。従って、プロセッ
サの台数に比例してメソセージ通信回数が増え、ＣＰＵ
の速度と比較してネットワークの転送速度が遅い一般的
な疎結合並列計算機においては、プロセッサ台数が増え
た時にはネットワークの通信がボ′トルネックとなって
、負荷の均等化が完全にはなされず、台数の拡張性が少
ないという問題点があった。
プロセッサは一定時間おきにスレーブプロセッサに対し
てポーリングせねばならず、一つのジョブを割り付ける
のに、プロセッサの台数をＮとした時に、（Ｎ−１）Ｘ
２個のメツセージ通信を必要とする。従って、プロセッ
サの台数に比例してメソセージ通信回数が増え、ＣＰＵ
の速度と比較してネットワークの転送速度が遅い一般的
な疎結合並列計算機においては、プロセッサ台数が増え
た時にはネットワークの通信がボ′トルネックとなって
、負荷の均等化が完全にはなされず、台数の拡張性が少
ないという問題点があった。
この発明は、上記のような問題点、を解消するためにな
されたもので、プロセッサの台数とは関係なく、一つの
ジョブを分散するのに一個のメツセージ通信で行うこと
を可能にし、これによりプロセッサの台数の拡張性を向
上させ、また、そのための特別なハードウェア或いはオ
ペレーティングシステムの機能を必要とせずに、負荷の
動的均等化の効率化及び高速化を図れる疎結合並列計算
機における負荷の動的均等化方式を得る事を目的とする
。
されたもので、プロセッサの台数とは関係なく、一つの
ジョブを分散するのに一個のメツセージ通信で行うこと
を可能にし、これによりプロセッサの台数の拡張性を向
上させ、また、そのための特別なハードウェア或いはオ
ペレーティングシステムの機能を必要とせずに、負荷の
動的均等化の効率化及び高速化を図れる疎結合並列計算
機における負荷の動的均等化方式を得る事を目的とする
。
この発明に係る疎結合並列計算機における負荷の動的均
等化方式においては、複数のプロセ、７すのうちの負荷
分散を行うマスタープロセッサ（ＣＰＵＩ）は、仕事を
分割して各ジョブを負荷の軽いスレーブプロセッサに割
り付ける作業を行い、予め全スレーブプロセッサ（ＣＰ
Ｕ２，３．４）に最低優先度のジョブを割り付けておき
、その最低優先度のジョブが実行されると、その最低優
先度のジョブを実行するスレーブプロセッサ（例えばＣ
ＰＵ４）上の実行可能なジョブのキューが空になること
によりそのスレーブプロセッサの負荷が軽くなった事を
その最低優先度のジョブからの応答により検出し、新た
なジョブをそのスレーブプロセッサに割り付けることを
特徴とするものである。
等化方式においては、複数のプロセ、７すのうちの負荷
分散を行うマスタープロセッサ（ＣＰＵＩ）は、仕事を
分割して各ジョブを負荷の軽いスレーブプロセッサに割
り付ける作業を行い、予め全スレーブプロセッサ（ＣＰ
Ｕ２，３．４）に最低優先度のジョブを割り付けておき
、その最低優先度のジョブが実行されると、その最低優
先度のジョブを実行するスレーブプロセッサ（例えばＣ
ＰＵ４）上の実行可能なジョブのキューが空になること
によりそのスレーブプロセッサの負荷が軽くなった事を
その最低優先度のジョブからの応答により検出し、新た
なジョブをそのスレーブプロセッサに割り付けることを
特徴とするものである。
スレーブプロセッサ（例えばＣＰＵ４）が最低優先度の
ジョブを実行すると、そのスレーブプロセッサ上の実行
可能なジョブのキューが空になり、最低優先度のジョブ
はマスタープロセッサ（ＣＰＵｌ）に対してそのスレー
ブプロセッサの負荷が軽くなった事を通知する。これに
よりそのスレブプロセッサには新たなジョブがマスター
プロセッサから割り付けられる。
ジョブを実行すると、そのスレーブプロセッサ上の実行
可能なジョブのキューが空になり、最低優先度のジョブ
はマスタープロセッサ（ＣＰＵｌ）に対してそのスレー
ブプロセッサの負荷が軽くなった事を通知する。これに
よりそのスレブプロセッサには新たなジョブがマスター
プロセッサから割り付けられる。
以下、この発明の一実施例を図により説明する。
第１図はこの実施例の負荷の動的均等化方式を説明する
ためのもので、４台のＣＰＵがネットワークで接続され
た疎結合並列計算機の構成をあられしたものである。第
１図において１，２，３゜４はＣＰＵを示し、ＣＰＵＩ
がマスタープロセッサ、ＣＰＵ２．ＣＰＵ３．ＣＰＵ４
はスレーブプロセッサを示し、１７はこれらを接続する
ネットワークを示す。また、各プロセッサの内部には実
行可能なジョブのキューがそれぞれ２本ずつあり、５．
６，７．８は優先度の高いジョブを格納するキューを示
し、２５，２６，２７．２８は優先度の低いジョブを格
納するキューを示す。９〜１６は優先度の高いジョブを
示し、３０〜３２は優先度の低いジョブを示す。
ためのもので、４台のＣＰＵがネットワークで接続され
た疎結合並列計算機の構成をあられしたものである。第
１図において１，２，３゜４はＣＰＵを示し、ＣＰＵＩ
がマスタープロセッサ、ＣＰＵ２．ＣＰＵ３．ＣＰＵ４
はスレーブプロセッサを示し、１７はこれらを接続する
ネットワークを示す。また、各プロセッサの内部には実
行可能なジョブのキューがそれぞれ２本ずつあり、５．
６，７．８は優先度の高いジョブを格納するキューを示
し、２５，２６，２７．２８は優先度の低いジョブを格
納するキューを示す。９〜１６は優先度の高いジョブを
示し、３０〜３２は優先度の低いジョブを示す。
ここで、マスタープロセッサ（ＣＰＵＩ）は仕事を分割
してジョブ９〜１３を生成し、優先度の高い実行可能な
ジョブを格納するキュー５に格納する。また、マスター
プロセッサは予め全スレーブプロセッサ（ＣＰＵ２〜４
）に優先度の低いジョブ３０，３１．３２をそれぞれ割
り付けておく。
してジョブ９〜１３を生成し、優先度の高い実行可能な
ジョブを格納するキュー５に格納する。また、マスター
プロセッサは予め全スレーブプロセッサ（ＣＰＵ２〜４
）に優先度の低いジョブ３０，３１．３２をそれぞれ割
り付けておく。
この状態で、ＣＰＵＩはジョブ１３を実行し、ＣＰＵ２
はジョブ１５を実行し、ＣＰＵ３はジョブ１６を実行す
る。この事は、これらのプロセ・ノサ（ＣＰＵ２〜４）
は現在負荷が重い、即ち忙しい事を示している。ＣＰＵ
４は実行可能なジョブは優先度の低いジョブ３２しかな
い。この事は、ＣＰＵ４は負荷が軽い、即ち暇である事
を示している。従って、負荷が軽いプロセッサ（ＣＰＵ
４）上では優先度の低いジョブ３２が実行される。
はジョブ１５を実行し、ＣＰＵ３はジョブ１６を実行す
る。この事は、これらのプロセ・ノサ（ＣＰＵ２〜４）
は現在負荷が重い、即ち忙しい事を示している。ＣＰＵ
４は実行可能なジョブは優先度の低いジョブ３２しかな
い。この事は、ＣＰＵ４は負荷が軽い、即ち暇である事
を示している。従って、負荷が軽いプロセッサ（ＣＰＵ
４）上では優先度の低いジョブ３２が実行される。
第２図は、第１図における優先度の低いジョブ３２が実
行されると、マスタープロセッサ（ＣＰＵｌ）に対して
新たなジョブを要求するための通信メツセージ（Ｒｅｑ
Ｊｏｂ： Ｒｅｑｕｅｓｔ Ｊｏｂ）が送られる様子を
あられしたものであり、第２図において１８は通信メソ
セージＲｅｑＪｏｂを示す。マスタープロセッサは、ス
レーブプロセッサから送られてきたＲｅｑＪｏｂ １
Ｂの到着によって、現在どのスレーブプロセッサの負荷
が軽いかを検出する事ができる。
行されると、マスタープロセッサ（ＣＰＵｌ）に対して
新たなジョブを要求するための通信メツセージ（Ｒｅｑ
Ｊｏｂ： Ｒｅｑｕｅｓｔ Ｊｏｂ）が送られる様子を
あられしたものであり、第２図において１８は通信メソ
セージＲｅｑＪｏｂを示す。マスタープロセッサは、ス
レーブプロセッサから送られてきたＲｅｑＪｏｂ １
Ｂの到着によって、現在どのスレーブプロセッサの負荷
が軽いかを検出する事ができる。
第３図は、負荷の軽いスレーブプロセッサを検出したマ
スタープロセッサが、自分の実行可能なジョブのキュー
の中のジョブを、負荷の軽いスレブプロセソサに割り付
けた様子を表したものであり、第３図においてジョブ９
はマスタープロセッサ（ＣＰＵＩ）のキュー５からスレ
ーブプロセッサ（ＣＰＵ４）のキュー８に割り付けられ
ている。その時、同時に新たな優先度の低いジョブ３３
がＣＰＵ４に割り付けられる。これは、ＣＰＵ４がジョ
ブ９の実行を終えて再度負荷が軽くなった時に、次のジ
ョブをマスタープロセッサに対して要求するためのジョ
ブである。
スタープロセッサが、自分の実行可能なジョブのキュー
の中のジョブを、負荷の軽いスレブプロセソサに割り付
けた様子を表したものであり、第３図においてジョブ９
はマスタープロセッサ（ＣＰＵＩ）のキュー５からスレ
ーブプロセッサ（ＣＰＵ４）のキュー８に割り付けられ
ている。その時、同時に新たな優先度の低いジョブ３３
がＣＰＵ４に割り付けられる。これは、ＣＰＵ４がジョ
ブ９の実行を終えて再度負荷が軽くなった時に、次のジ
ョブをマスタープロセッサに対して要求するためのジョ
ブである。
第４図は、スレーブプロセッサ（ＣＰ Ｕ ３ ）が第
３図におけるジョブ１６の実行を終了して負荷が軽くな
り、優先度の低いジョブ３１が実行されて負荷が軽くな
った事をマスタープロセッサ（ＣＰＵＩ）に通知し、そ
して新たなジョブ１０とジョブ３４が割り付けられた様
子を表したものである。
３図におけるジョブ１６の実行を終了して負荷が軽くな
り、優先度の低いジョブ３１が実行されて負荷が軽くな
った事をマスタープロセッサ（ＣＰＵＩ）に通知し、そ
して新たなジョブ１０とジョブ３４が割り付けられた様
子を表したものである。
以上の処理の繰り返しで、各スレーブプロセッサ（ＣＰ
Ｕ２，３．４）は負荷が軽くなるたびにマスタープロセ
ッサ（ＣＰＵＩ）に新たなジョブの割り付けを要求し、
マスタープロセッサ中のジョブは、次々と動的に負荷の
軽いプロセッサに割り付けられ、負荷の均等化が行われ
る。負荷の均等化のために必要な通信メツセージは、一
つのジョブを割り付けるのに対して一個のＲｅｑＪｏｂ
メツセージのみである。また、プロセッサの台数とは関
わりなく通信メツセージの個数は一定であり、プロセッ
サ台数の拡張性を有する。
Ｕ２，３．４）は負荷が軽くなるたびにマスタープロセ
ッサ（ＣＰＵＩ）に新たなジョブの割り付けを要求し、
マスタープロセッサ中のジョブは、次々と動的に負荷の
軽いプロセッサに割り付けられ、負荷の均等化が行われ
る。負荷の均等化のために必要な通信メツセージは、一
つのジョブを割り付けるのに対して一個のＲｅｑＪｏｂ
メツセージのみである。また、プロセッサの台数とは関
わりなく通信メツセージの個数は一定であり、プロセッ
サ台数の拡張性を有する。
以上説明したように上記実施例は、負荷分散を行うマス
タープロセッサは仕事を分割してそれらを負荷の軽いス
レーブプロセッサに割り付ける作業を行い、予め全スレ
ーブプロセンサには最低優先度のジョブを割り付けてお
き、この最低優先度のジョブが実行される事によって各
スレーブプロセッサ上の実行可能なジョブのキューが空
になった事、Ｉ！ｌＩちそのスレーブプロセッサの負荷
が軽くなった事を検出し、その最低優先度のジョブは、
マスタープロセッサに対して負荷が軽くなった事を通知
して新たなジョブの割り付けを要求する通信メツセージ
（ＲｅｑＪｏｂ： Ｒｅｑｕｅｓｔ Ｊｏｂ）を送り、
そのメソセージを送出したスレーブプロセッサに対して
マスタープロセッサがジョブを割り付けるようにしたも
のである。
タープロセッサは仕事を分割してそれらを負荷の軽いス
レーブプロセッサに割り付ける作業を行い、予め全スレ
ーブプロセンサには最低優先度のジョブを割り付けてお
き、この最低優先度のジョブが実行される事によって各
スレーブプロセッサ上の実行可能なジョブのキューが空
になった事、Ｉ！ｌＩちそのスレーブプロセッサの負荷
が軽くなった事を検出し、その最低優先度のジョブは、
マスタープロセッサに対して負荷が軽くなった事を通知
して新たなジョブの割り付けを要求する通信メツセージ
（ＲｅｑＪｏｂ： Ｒｅｑｕｅｓｔ Ｊｏｂ）を送り、
そのメソセージを送出したスレーブプロセッサに対して
マスタープロセッサがジョブを割り付けるようにしたも
のである。
したがって上記実施例によれば、従来の方式では暇なプ
ロセッサを検出するためにマスタープロセッサは一定時
間おきにスレーブプロセッサに対してポーリングし、一
つのジョブを分散するのに、プロセッサの台数をＮとし
た時に、（Ｎ−１）Ｘ２個のメツセージ通信を必要とし
たところを、特別なハードウェア或いはオペレーティン
グシステムの機能を必要とせず、予め全てのスレーブプ
ロセッサに割り付けた最低優先度のジョブの実行によっ
て負荷の軽いプロセッサを検出でき、また一つのジョブ
を分散するのに一個のメツセージ通信で行う事ができる
ため、プロセッサの台数に関わりなく一定の数の通信メ
ソセージで負荷の動的均等化ができ、プロセッサ台数の
拡張性を向上する。
ロセッサを検出するためにマスタープロセッサは一定時
間おきにスレーブプロセッサに対してポーリングし、一
つのジョブを分散するのに、プロセッサの台数をＮとし
た時に、（Ｎ−１）Ｘ２個のメツセージ通信を必要とし
たところを、特別なハードウェア或いはオペレーティン
グシステムの機能を必要とせず、予め全てのスレーブプ
ロセッサに割り付けた最低優先度のジョブの実行によっ
て負荷の軽いプロセッサを検出でき、また一つのジョブ
を分散するのに一個のメツセージ通信で行う事ができる
ため、プロセッサの台数に関わりなく一定の数の通信メ
ソセージで負荷の動的均等化ができ、プロセッサ台数の
拡張性を向上する。
なお、上記実施例においては実行可能なジョブを格納す
るキューは優先度の高いものと低いもの２本を持った疎
結合並列計算機を想定しているが、更に多段階の優先度
を持った計算機においては、上記実施例における優先度
の低いジョブを、最低優先度のジョブとすればよいのは
いうまでもない。
るキューは優先度の高いものと低いもの２本を持った疎
結合並列計算機を想定しているが、更に多段階の優先度
を持った計算機においては、上記実施例における優先度
の低いジョブを、最低優先度のジョブとすればよいのは
いうまでもない。
以上のように本発明によれば、全スレーブプロセッサに
予め最低優先度のジョブを割り付けておき、その最低優
先度のジョブの実行により該当スレーブプロセッサの負
荷が軽くなったことをマスタープロセッサに通知し、新
たなジョブを該当スレーブプロセッサに割り付けるよう
にしたので、負荷の軽いプロセッサの検出が特別なハー
ドウェア或いはオペレーティングシステムの機能を必要
と廿ずに最低優先度のジョブの実行により行うことがで
き、一つのジョブを分散するのに一個の通信メツセージ
によって行え、これによりプロセッサの台数が増えても
負荷の動的均等化のために必要な通信メツセージの数は
増加することがなく、したがってプロセッサの台数の拡
張性が向上し、また負荷の動的均等化を効率良く高速に
行えるという効果が得られる。
予め最低優先度のジョブを割り付けておき、その最低優
先度のジョブの実行により該当スレーブプロセッサの負
荷が軽くなったことをマスタープロセッサに通知し、新
たなジョブを該当スレーブプロセッサに割り付けるよう
にしたので、負荷の軽いプロセッサの検出が特別なハー
ドウェア或いはオペレーティングシステムの機能を必要
と廿ずに最低優先度のジョブの実行により行うことがで
き、一つのジョブを分散するのに一個の通信メツセージ
によって行え、これによりプロセッサの台数が増えても
負荷の動的均等化のために必要な通信メツセージの数は
増加することがなく、したがってプロセッサの台数の拡
張性が向上し、また負荷の動的均等化を効率良く高速に
行えるという効果が得られる。
第１図はこの発明の一実施例に係る負荷の動的均等化方
式を説明するための疎結合並列計算機の構成を示すブロ
ック図、第２図はこの実施例において優先度の低いジョ
ブが実行されるとマスタープロセッサに対して新たなジ
ョブを要求するための通信メツセージが送られる様子を
説明するためのブロック図、第３図はこの実施例におい
て負荷の軽いスレーブプロセッサにジョブが割り付けら
れる様子を説明するためのブロック図、第４図はこの実
施例において新たなジョブがマスタープロセッサに割り
付けられる様子を説明するためのブロック図、第５図は
従来の負荷の動的均等化方式を説明するための疎結合並
列計算機の構成を示すブロック図、第６図はこの従来例
において負荷の軽いプロセッサを見つける様子を説明す
るためのブロック図、第７図はこの従来例において一番
負荷が軽いプロセッサにジョブを割り付ける様子を説明
するためのブロック図である。 １・・・ＣＰＵ （マスタープロセッサ）、２゜３．４
・・・ＣＰＵ （スレーブプロセッサ）、５゜６．７，
８，２５，２６，２７．２８・・・キュ、９〜１６・・
・優先度の高いジョブ、１７・・・ネットワーク、１８
・・・通信メツセージ、３０．３１．３２・・・優先度
の低いジョブ（最低優先度のジョブ）。
式を説明するための疎結合並列計算機の構成を示すブロ
ック図、第２図はこの実施例において優先度の低いジョ
ブが実行されるとマスタープロセッサに対して新たなジ
ョブを要求するための通信メツセージが送られる様子を
説明するためのブロック図、第３図はこの実施例におい
て負荷の軽いスレーブプロセッサにジョブが割り付けら
れる様子を説明するためのブロック図、第４図はこの実
施例において新たなジョブがマスタープロセッサに割り
付けられる様子を説明するためのブロック図、第５図は
従来の負荷の動的均等化方式を説明するための疎結合並
列計算機の構成を示すブロック図、第６図はこの従来例
において負荷の軽いプロセッサを見つける様子を説明す
るためのブロック図、第７図はこの従来例において一番
負荷が軽いプロセッサにジョブを割り付ける様子を説明
するためのブロック図である。 １・・・ＣＰＵ （マスタープロセッサ）、２゜３．４
・・・ＣＰＵ （スレーブプロセッサ）、５゜６．７，
８，２５，２６，２７．２８・・・キュ、９〜１６・・
・優先度の高いジョブ、１７・・・ネットワーク、１８
・・・通信メツセージ、３０．３１．３２・・・優先度
の低いジョブ（最低優先度のジョブ）。
Claims (1)
- 複数のプロセッサがネットワークにより接続され、プロ
セッサの処理速度と比較して通信速度が遅いような疎結
合並列計算機上で負荷を動的に均等化するための負荷の
動的均等化方式において、上記複数のプロセッサのうち
の負荷分散を行うマスタープロセッサは、仕事を分割し
て各ジョブを負荷の軽いスレーブプロセッサに割り付け
る作業を行い、予め全スレーブプロセッサに最低優先度
のジョブを割り付けておき、その最低優先度のジョブが
実行されると、その最低優先度のジョブを実行するスレ
ーブプロセッサ上の実行可能なジョブのキューが空にな
ることによりそのスレーブプロセッサの負荷が軽くなっ
た事をその最低優先度のジョブからの応答により検出し
、新たなジョブをそのスレーブプロセッサに割り付ける
ことを特徴とする疎結合並列計算機における負荷の動的
均等化方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2059858A JPH0713817B2 (ja) | 1990-03-13 | 1990-03-13 | 疎結合並列計算機における負荷の動的均等化方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2059858A JPH0713817B2 (ja) | 1990-03-13 | 1990-03-13 | 疎結合並列計算機における負荷の動的均等化方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH03262074A true JPH03262074A (ja) | 1991-11-21 |
| JPH0713817B2 JPH0713817B2 (ja) | 1995-02-15 |
Family
ID=13125301
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2059858A Expired - Lifetime JPH0713817B2 (ja) | 1990-03-13 | 1990-03-13 | 疎結合並列計算機における負荷の動的均等化方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0713817B2 (ja) |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06301656A (ja) * | 1993-04-13 | 1994-10-28 | Mitsubishi Electric Corp | 分散計算機システムにおける負荷均等化方法 |
| JPH0830471A (ja) * | 1994-07-14 | 1996-02-02 | Hitachi Ltd | ジョブの実行プロセサ変更方式 |
| JPH11195007A (ja) * | 1998-01-07 | 1999-07-21 | Sanyo Electric Co Ltd | 分散処理システム及び分散処理方法 |
| JP2004520655A (ja) * | 2001-05-08 | 2004-07-08 | イーエムシー コーポレイション | 分散型コンピュータシステムにおける資源の選択 |
| JP2006107019A (ja) * | 2004-10-04 | 2006-04-20 | Hitachi Ltd | ディスクアレイ装置 |
| WO2013076775A1 (ja) * | 2011-11-24 | 2013-05-30 | 株式会社日立製作所 | 計算機システム、分割ジョブ処理方法及びプログラム |
| JP2018512648A (ja) * | 2015-04-16 | 2018-05-17 | インテル コーポレイション | ネットワーク負荷に基づいてプロセッサ電力使用を調整する装置及び方法 |
| JP2022109755A (ja) * | 2021-01-15 | 2022-07-28 | 日立建機株式会社 | 作業機械 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61114363A (ja) * | 1984-11-07 | 1986-06-02 | Hitachi Ltd | 計算機システム間ジヨブ転送方式 |
| JPS63211060A (ja) * | 1987-02-27 | 1988-09-01 | Nippon Telegr & Teleph Corp <Ntt> | マルチプロセツサシステムにおける負荷分散制御方式 |
-
1990
- 1990-03-13 JP JP2059858A patent/JPH0713817B2/ja not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61114363A (ja) * | 1984-11-07 | 1986-06-02 | Hitachi Ltd | 計算機システム間ジヨブ転送方式 |
| JPS63211060A (ja) * | 1987-02-27 | 1988-09-01 | Nippon Telegr & Teleph Corp <Ntt> | マルチプロセツサシステムにおける負荷分散制御方式 |
Cited By (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06301656A (ja) * | 1993-04-13 | 1994-10-28 | Mitsubishi Electric Corp | 分散計算機システムにおける負荷均等化方法 |
| JPH0830471A (ja) * | 1994-07-14 | 1996-02-02 | Hitachi Ltd | ジョブの実行プロセサ変更方式 |
| JPH11195007A (ja) * | 1998-01-07 | 1999-07-21 | Sanyo Electric Co Ltd | 分散処理システム及び分散処理方法 |
| JP2004520655A (ja) * | 2001-05-08 | 2004-07-08 | イーエムシー コーポレイション | 分散型コンピュータシステムにおける資源の選択 |
| JP2006107019A (ja) * | 2004-10-04 | 2006-04-20 | Hitachi Ltd | ディスクアレイ装置 |
| US8615625B2 (en) | 2004-10-04 | 2013-12-24 | Hitachi, Ltd. | Disk array system |
| WO2013076775A1 (ja) * | 2011-11-24 | 2013-05-30 | 株式会社日立製作所 | 計算機システム、分割ジョブ処理方法及びプログラム |
| JPWO2013076775A1 (ja) * | 2011-11-24 | 2015-04-27 | 株式会社日立製作所 | 計算機システム、分割ジョブ処理方法及びプログラム |
| US9244721B2 (en) | 2011-11-24 | 2016-01-26 | Hitachi, Ltd. | Computer system and divided job processing method and program |
| JP2018512648A (ja) * | 2015-04-16 | 2018-05-17 | インテル コーポレイション | ネットワーク負荷に基づいてプロセッサ電力使用を調整する装置及び方法 |
| JP2022109755A (ja) * | 2021-01-15 | 2022-07-28 | 日立建機株式会社 | 作業機械 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0713817B2 (ja) | 1995-02-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3678414B2 (ja) | 多重プロセッサ・システム | |
| US7251815B2 (en) | Multiple virtual machines sharing processor and work queue in memory having program/dispatch functions for assigning and accessing work items while the virtual machine was not idle | |
| US20010003831A1 (en) | Method and apparatus for allocating network resources and changing the allocation based on dynamic workload changes | |
| EP2930619A2 (en) | System and method for shared utilisation of virtualised computing resources | |
| JPH04229356A (ja) | ロードバランスシステム | |
| EP2930618A2 (en) | System and method for load balancing compute resources | |
| WO2017133623A1 (zh) | 一种数据流处理方法、装置和系统 | |
| EP3114589B1 (en) | System and method for massively parallel processing database | |
| Garala et al. | A performance analysis of load balancing algorithms in cloud environment | |
| Alam et al. | Resource-aware load balancing model for batch of tasks (BoT) with best fit migration policy on heterogeneous distributed computing systems | |
| CN116483538A (zh) | 一种一致性低延迟的数据中心任务调度方法 | |
| Soundarabai et al. | Comparative study on load balancing techniques in distributed systems | |
| JP2008226023A (ja) | ジョブ割当装置、及びジョブ割当方法 | |
| JPH03262074A (ja) | 疎結合並列計算機における負荷の動的均等化方法 | |
| JPH0628323A (ja) | プロセス実行制御方法 | |
| Patel et al. | A survey on load balancing in cloud computing | |
| Wan et al. | A batch scheduler for the Intel Paragon with a non-contiguous node allocation algorithm | |
| US9584594B2 (en) | Dynamic provisioning of processing resources in a virtualized computational architecture | |
| Haroon et al. | Interest attentive dynamic load balancing in distributed systems | |
| CN113364888A (zh) | 服务调度方法、系统、电子设备及计算机可读存储介质 | |
| KR101639947B1 (ko) | 하둡 선점 데드라인 제약 스케줄링 방법 및 그 방법을 수행하는 컴퓨터프로그램과, 그 프로그램이 기록된 매체 | |
| CN112416538B (zh) | 一种分布式资源管理框架的多层次架构和管理方法 | |
| KR20130028554A (ko) | 메시지 버스를 이용한 대용량 분산 처리 장치 및 그 방법 | |
| Naaz et al. | Load balancing algorithms for peer to peer and client server distributed environments | |
| JPH09160884A (ja) | 動的負荷分散並列計算機 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |