JPH1027167A - 並列計算機の負荷分散方法 - Google Patents

Abstract

(57)【要約】 【課題】 複数の構成プログラムから構成される並列プ
ログラム１１の各構成プログラムを複数の計算機１−
１，１−２，・・・から構成される並列計算機の各計算
機１に割り当てるとき、構成プログラム自身が計算機１
にかける負荷を考慮した負荷分散を行い、並列プログラ
ム全体の経過時間を短縮する。 【解決手段】 各計算機１の履歴採取プログラム４は、
構成プログラム２の資源使用率データを採取し、資源使
用履歴１２に格納する。スケジューラ６は、資源使用履
歴１２から平均の資源使用率を求めて平均資源使用デー
タ１３に格納し、ユーザ設定情報１４に設定された注目
すべき資源について現在負荷データ１５に格納される各
計算機１の使用率を参照し、注目する資源の使用率の大
きい構成プログラムから順に構成プログラムを注目する
資源の使用率の小さい計算機から順に計算機１に割り当
てる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数の計算機から
構成される並列計算機に係わり、特に複数の構成プログ
ラムから構成される並列プログラムの各構成プログラム
を各計算機に割り当てて並行して実行するときの負荷分
散方法に関する。

【０００２】

【従来の技術】近年、複数の計算機から構成され、各々
専用の記憶装置とプロセッサを有する計算機が高速のネ
ットワークを介して相互に接続される分散メモリ型の並
列計算機が普及し始めている。複数の構成プログラムか
ら構成される並列プログラムの各構成プログラムは、各
計算機に割り当てられ、並行して実行される。構成プロ
グラムがネットワークを介して他の構成プログラムと通
信するとき、ＭＰＩ（Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ
Ｉｎｔｅｒｆａｃｅ）、ＰＶＭ（Ｐａｒａｌｌｅｌ
Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ）などの並列通信ライ
ブラリを介してプログラム間のメッセージ通信を行う。
これらの並列通信ライブラリは、構成プログラムが他の
構成プログラムと容易に通信できるようなアプリケーシ
ョン・インタフェースを提供する。

【０００３】各構成プログラムを計算機に割り当てると
き、スケジューリングする計算機は、各計算機の負荷情
報を収集し、負荷の小さい計算機から順に各構成プログ
ラムを割り当てていた。

【０００４】なおこの種の技術として関連するものに
は、特開平７−２３４８４７号公報、特開平５−７３５
１５号公報等がある。

【０００５】

【発明が解決しようとする課題】上記従来技術によれ
ば、各構成プログラム自身が計算機にかける負荷につい
ては考慮されていなかった。このため複数の構成プログ
ラムの中で実行時の経過時間の長い構成プログラムが負
荷の重い計算機に割り当てられることがあり、この結果
このような構成プログラムの経過時間が引き延ばされて
ボトルネックとなり、並列プログラム全体の経過時間が
増大するという問題があった。特に並列プログラムが何
回も繰り返して実行されるようなプログラムである場合
に、経過時間の安定したプログラム実行が望まれる。

【０００６】本発明は、構成プログラム自身が計算機に
かける負荷を考慮した負荷分散を行い、並列プログラム
全体の経過時間を短縮することを目的とする。

【０００７】

【課題を解決するための手段】本発明は、各構成プログ
ラムを各計算機で実行するときの資源使用率を取得し、
構成プログラムを実行しない状態での各計算機全体の資
源使用率を取得し、注目する資源の使用率の大きい構成
プログラムから順に構成プログラムを注目する資源の使
用率の小さい計算機から順に計算機に割り当てる並列計
算機の負荷分散方法を特徴とする。

【０００８】本発明によれば、ＣＰＵ，Ｉ／Ｏなどの資
源のうちで構成プログラムの特性からボトルネックにな
り易い資源に注目し、この注目する資源の使用率の大き
い構成プログラムから順に構成プログラムを注目する資
源の使用率の小さい計算機から順に対応するように計算
機に割り当てるので、ボトルネックになり易い構成プロ
グラムの経過時間の延びを防止でき、もって並列プログ
ラム全体の経過時間を短縮することができる。

【０００９】

【発明の実施の形態】以下、本発明の一実施形態につい
て図面を用いて説明する。

【００１０】図１は、分散メモリ型の並列計算機の構成
図である。並列計算機を構成する各計算機１−１，１−
２，１−３，１−４，１−５は、共通の通信路２０に接
続され、それぞれ同等の処理能力を有する演算処理装置
と専用の記憶装置を有する。並列プログラム１１は、１
個又は複数個の構成プログラムによって構成され、各構
成プログラムはいずれかの計算機１に割り付けられ、他
の構成プログラムと並行して実行されるユーザのアプリ
ケーションプログラムである。構成プログラム２は、計
算機１−１〜１−４に割り付けられ、専用の記憶装置に
ロードされて実行される構成プログラムを示している。
通信プログラム３は、計算機１が他の計算機１と情報の
送受信を行うプログラムであり、容易に利用できるアプ
リケーション・インタフェースを提供するという点で並
列通信ライブラリを含む通信制御プログラムが好適であ
る。履歴採取プログラム４は、構成プログラム２の資源
使用率及び実行時の経過時間の履歴データを採取するプ
ログラムである。負荷データ収集部５は、計算機１全体
の資源使用率データを収集するハードウェア及びプログ
ラムである。計算機１−２，１−３及び１−４の構成
は、計算機１−１と同じであり、各計算機の構成プログ
ラム２、通信プログラム３、履歴採取プログラム４及び
負荷データ収集部５を区別するときには、計算機の識別
子１〜５を付加する。

【００１１】資源使用履歴１２は、通信路２０に接続さ
れすべての計算機によって共有される記憶装置上に格納
され、履歴採取プログラム４が収集した履歴データであ
る。平均資源使用データ１３は、各構成プログラム２の
平均の資源使用率及び経過時間のデータを格納する。ユ
ーザ設定情報１４は、各構成プログラム２を計算機１に
割り当てるスケジューリングの際に使用されるパラメー
タである。現在負荷データ１５は、各計算機１の資源使
用率データである。予測負荷データ１６は、現在の計算
機１の負荷に割り当てた構成プログラム２の資源使用率
を追加するとき予測される負荷データである。並列プロ
グラム１１、平均資源使用データ１３、ユーザ設定情報
１４、現在負荷データ１５及び予測負荷データ１６は、
計算機１−５が有する専用の記憶装置上に格納される。

【００１２】スケジューラ６は、計算機１−５の専用記
憶装置に格納されて実行されるプログラムであり、資源
使用履歴１２を読み込み、各構成プログラム２の平均の
資源使用データを計算して平均資源使用データ１３に格
納し、ユーザ設定情報１４を読み込んでそのパラメータ
に基づいて各構成プログラムの割当優先順位を決定し、
負荷データ収集部５を介して各計算機１の現在の負荷デ
ータを収集して現在負荷データ１５に格納し、構成プロ
グラムの割当優先順位に従って平均資源使用データ１３
と現在負荷データ１５とから構成プログラム２を追加し
たときの各計算機１の負荷を計算して予測負荷データ１
６に格納するとともに、各計算機１に割り当てる構成プ
ログラム２を決定する。通信プログラム７は、計算機１
−５が他の計算機１と情報の送受信を行うプログラムで
ある。なお計算機１−５は、スケジューリング専用の計
算機でもよいし、スケジューリングの後、他の計算機１
と並行して構成プログラムを実行する計算機であっても
よい。

【００１３】図２は、資源使用履歴１２のデータ形式を
示す図である。資源使用履歴１２は、各構成プログラム
２を少なくとも１回実行したときの資源使用率と経過時
間を記録する。項番は実行回数を示す番号である。経過
時間は、構成プログラム２が実行開始されてから終了す
るまでの時間である。トランザクション処理のような場
合には、経過時間は構成プログラム２にトランザクショ
ンが投入されてから結果のデータが出力されるまでの時
間であり、ターンアラウンドタイムに相当する。ＣＰＵ
使用率は、構成プログラム２が単独で実行される場合、
構成プログラム２の経過時間に対する演算処理装置の使
用時間の比率である。Ｉ／Ｏ使用率は、構成プログラム
２の経過時間に対する外部記憶装置、通信路２０伝送な
ど入出力装置の使用時間の比率である。

【００１４】最初に構成プログラム２−１，２−２，２
−３及び２−４がそれぞれ計算機１−１，１−２，１−
３及び１−４に割り当てられ、並行して実行されるもの
とする。構成プログラム２は、必要に応じて通信プログ
ラム３及び通信路２０を介して他の構成プログラム２と
通信しながら処理を進める。各履歴採取プログラム４
は、構成プログラム２が実行されている間のＣＰＵ使用
率、Ｉ／Ｏ使用率及び経過時間のデータを採取し、通信
プログラム３及び通信路２０を介して資源使用履歴１２
に格納する。このようにして履歴採取プログラム４は、
構成プログラム２が実行されるたびにその資源使用率及
び経過時間のデータを採取して資源使用履歴１２に格納
する。同一プログラムであっても、入力データによって
資源使用率及び経過時間が異なる場合があり、このよう
な場合には構成プログラム２を複数回実行させ、各々の
履歴データを資源使用履歴１２に記録するのが望まし
い。計算機１では構成プログラム２以外の図示しない他
のアプリケーションプログラムを構成プログラム２と同
時に走行させてよいが、履歴採取プログラム４が構成プ
ログラム２の履歴データを採取している間は他プログラ
ムを走行させないのが望ましい。また他プログラムの資
源使用率は定常的であって時間的に大きな変化をしない
ものとする。負荷データ収集部５は、少なくとも他プロ
グラムを実行している間、計算機１全体の資源使用率デ
ータを収集する。

【００１５】図３は、平均資源使用データ１３のデータ
形式を示す図である。平均資源使用データ１３は、資源
使用履歴１２のデータに基づいて計算された各構成プロ
グラム２の平均の資源使用率及び平均の経過時間であ
る。優先順位は、各構成プログラム２を計算機１に割り
当てるときの選択する順番を示す。

【００１６】ユーザ設定情報１４は、構成プログラム２
の割当スケジューリングの際に使用されるパラメータの
例であり、次のようなパラメータから構成される。 （ａ）優先資源使用率：ＣＰＵ使用率 （ｂ）ＣＰＵ使用率限界値：９０％ （ｃ）Ｉ／Ｏ使用率限界値：９０％ （ｄ）経過時間の最小値：１０秒 優先資源使用率は、ＣＰＵ使用率とＩ／Ｏ使用率のうち
どちらを優先して構成プログラム２を計算機１に割り当
てるかを指定するものであり、経過時間のボトルネック
となり得る資源の使用率を指定する。一般にＣＰＵバウ
ンドの並列プログラムについてはＣＰＵ使用率を指定
し、Ｉ／Ｏバウンドの並列プログラムについてはＩ／Ｏ
使用率を指定する。ＣＰＵ使用率限界値は、計算機１の
ＣＰＵ使用率の上限を指定し、Ｉ／Ｏ使用率限界値は、
計算機１からみたＩ／Ｏ使用率の上限を指定する。資源
使用率の限界値は、計算機１がその限界値を越えたと
き、資源使用率のわずかの増加によって経過時間が急激
に増大するような場合の実際の限界となる資源使用率を
与えるものである。経過時間の最小値は、経過時間の小
さい構成プログラム２の優先度を下げるために設定する
経過時間の下限を指定するパラメータである。

【００１７】図４は、現在負荷データ１５のデータ形式
を示す図である。現在負荷データ１５は、各計算機１ご
とに負荷の大きさとして平均の資源使用率を設定する。

【００１８】図５は、予測負荷データ１６のデータ形式
を示す図である。予測負荷データ１６は、各計算機１ご
とに割り当てた構成プログラム２、構成プログラム２を
付加したときの予想される負荷の大きさとして予測資源
使用率を設定する。

【００１９】図６は、スケジューラ６の処理の流れを示
すフローチャートである。スケジューラ６は、資源使用
履歴１２に構成プログラム２が少なくとも１回実行され
たときの履歴データが格納され、各計算機１に構成プロ
グラム２がロードされる前の状態で処理を開始する。各
計算機１は構成プログラム２以外の他のプログラムを実
行していてもよい。スケジューラ６は、通信プログラム
７及び通信路２０を介して資源使用履歴１２のデータを
読み込み（ステップ６１）、各構成プログラム２につい
て平均資源使用率と平均経過時間を計算して（ステップ
６２）、平均資源使用データ１３に格納する（ステップ
６３）。次にユーザ設定情報１４を読み込んで（ステッ
プ６４）、その優先資源使用率に基づいて各構成プログ
ラム２に割当優先順位を付与する（ステップ６５）。例
えばＣＰＵ使用率が優先資源使用率であれば、平均資源
使用データ１３を参照して平均ＣＰＵ使用率の大きい構
成プログラム２から順に１，２，・・・の優先順位を付
与する。次に平均資源使用データ１３を参照して平均経
過時間がユーザ設定情報１４に設定する最小値以下の構
成プログラム２があればそれを抽出し（ステップ６
６）、抽出した構成プログラム２を除外して平均ＣＰＵ
使用率の大きい構成プログラム２から順に１，２，・・
・の優先順位を付け直し、除外した構成プログラム２に
ついては経過時間の大きい構成プログラム２から順に続
きの優先順位を付与するように優先順位を付け直す（ス
テップ６７）。この処理によって経過時間が最小値以下
の構成プログラム２は最下位から順に優先順位が付与さ
れ、残りの構成プログラム２は優先資源使用率の大きい
ものから順に１，２，・・・の優先順位が付与されるこ
とになる。経過時間の極端に小さい構成プログラム２
は、計算機１に加える負荷が小さいために、優先資源使
用率が大きいか否かにかかわらず負荷の大きい計算機１
に割り当てる。この処理によって経過時間の極端に小さ
い構成プログラム２が誤って負荷の小さい計算機１に割
り当てられ、結果として不平衡な負荷分散が行われて並
列プログラム全体の経過時間が増大することを防止す
る。次にスケジューラ６は、通信プログラム７及び通信
路２０を介して負荷データ収集部５に計算機１の負荷デ
ータを要求し、取得した計算機１の資源使用率を現在負
荷データ１５に格納する（ステップ６８）。次に構成プ
ログラム２の割当を終了していなければ（ステップ６９
ＮＯ）、割当の済んでいない最も優先順位の高い構成プ
ログラム２を選択して、まだ割当の済んでいない計算機
１の中で優先資源使用率が最も小さい計算機１に仮割当
し、次の計算式により計算機１の予測資源使用率を計算
する（ステップ７０）。 予測資源使用率＝計算機１の現在の平均資源使用率＋選
択した構成プログラム２の平均資源使用率 予測資源使用率は、ＣＰＵ使用率とＩ／Ｏ使用率の両方
についてそれぞれ計算する。次に計算した予測資源使用
率とユーザ設定情報１４から入力されたＣＰＵ使用率限
界値及びＩ／Ｏ使用率限界値とをそれぞれ比較する（ス
テップ７１）。ＣＰＵ使用率とＩ／Ｏ使用率のいずれも
限界値を越えていないとき（ステップ７１ＮＯ）、選択
した構成プログラム２を仮割当した計算機１に割り当て
ることにし（ステップ７２）、予測負荷データ１６の該
当する計算機１に対応して割り当てた構成プログラム２
の識別子、計算した予測ＣＰＵ使用率及び予測Ｉ／Ｏ使
用率を格納する。ＣＰＵ使用率とＩ／Ｏ使用率のいずれ
かが限界値を越えたとき（ステップ７１ＹＥＳ）、予測
負荷データ１６の該当する計算機１に対応してフラグを
立て、割当が済んでいないか、仮割当の試行をしていな
い残りの計算機１があれば（ステップ７３ＹＥＳ）、ス
テップ７０に戻って上記処理を繰り返す。このようにし
てすべての構成プログラム２を計算機１に割り当てたと
き（ステップ６９ＹＥＳ）、スケジューラ６は予測負荷
データ１６上の構成プログラム２の割当に従って並列プ
ログラム１１から各構成プログラム２を読み出して割り
当てた計算機１にローディングし、起動する（ステップ
７４）。残りの計算機１がなくなったとき（ステップ７
３ＮＯ）、スケジューラ６は図示しない表示装置上に並
列プログラムの実行を中止する旨のメッセージを表示す
る（ステップ７５）。

【００２０】上記のスケジューラ６の処理によって、例
えば図３に示す資源使用データをもつ構成プログラム２
の割当優先順位は、上記ユーザ設定情報１４の例によれ
ば図３に示す順位となり、現在負荷データ１５が図４に
示すものとしたとき、結果として各計算機１に割り当て
られる構成プログラム２及び予測資源使用率は図５に示
すものとなる。この例ではまず構成プログラム２−３が
計算機１−１に割当された後、構成プログラム２−２が
計算機１−２に仮割当されるが、計算機１−２の予測Ｉ
／Ｏ使用率が限界値を越えるため、計算機１−３に割当
されることになり、構成プログラム２−１及び２−４は
仮割当通りそれぞれ計算機１−２及び１−４に割当され
る。

【００２１】上記実施形態によれば、並列プログラムを
構成する構成プログラムの中で、構成プログラムの実行
時経過時間を引き延ばすボトルネックとなり易い資源に
ついてその資源使用率においてボトルネックとなり易い
構成プログラムをその資源使用率の負荷が小さい計算機
に割り当てるため、このような構成プログラム２の経過
時間を増大させない方向で負荷分散が行われ、結果とし
て並列プログラム１１全体の経過時間あるいはターンア
ラウンドタイムを短縮できる。またこのとき経過時間の
極端に小さい構成プログラム２は、並列プログラム全体
の経過時間に注目したときその経過時間が多少延びても
ボトルネックにならないものとして比較的負荷の大きい
計算機に割当されるため、このような構成プログラム２
によって上記の原則が乱されることがなく、結果として
並列プログラム１１全体の経過時間の短縮に寄与する。
さらに計算機１の資源使用率の限界値を越えるような構
成プログラム２の割当を排除するために、上記のような
構成プログラム２自体に起因するボトルネック以外の新
たなボトルネックが発生して構成プログラム２の経過時
間が増大することを防止し、結果として並列プログラム
１１全体の経過時間の短縮に寄与する。

【００２２】なお並列計算機を構成する計算機の数が並
列プログラムを構成する構成プログラムの数より多い場
合、スケジューラ６は注目する資源の使用率の小さいも
のから順に構成プログラムの数に相当する計算機を選択
し、選択した計算機について上記の割当スケジューリン
グを行えばよい。

【００２３】また上記実施形態では、資源使用率として
ＣＰＵ使用率とＩ／Ｏ使用率を挙げたが、Ｉ／Ｏ使用率
を通信路２０の使用率と通信路２０以外の入出力装置使
用率とに分離してもよい。またメモリ（主記憶）使用率
を加えてもよい。

【００２４】

【発明の効果】本発明によれば、並列プログラムを構成
する構成プログラムについてボトルネックとなり易い資
源に注目し、この資源の使用率においてボトルネックと
なり易い構成プログラムをその資源使用率の負荷が小さ
い計算機に割り当てるため、並列プログラム全体の経過
時間あるいはターンアラウンドタイムが短縮され、特に
繰り返し実行される並列プログラムの安定したターンア
ラウンドタイムを実現できる。

【図面の簡単な説明】

【図１】実施形態の分散メモリ型の並列計算機の構成図
である。

【図２】実施形態の資源使用履歴１２のデータ形式を示
す図である。

【図３】実施形態の平均資源使用データ１３のデータ形
式を示す図である。

【図４】実施形態の現在負荷データ１５のデータ形式を
示す図である。

【図５】実施形態の予測負荷データ１６のデータ形式を
示す図である。

【図６】実施形態のスケジューラ６の処理の流れを示す
フローチャートである。

【符号の説明】

１：計算機、２：構成プログラム、４：履歴採取プログ
ラム、６：スケジューラ、１１：並列プログラム、１
２：資源使用履歴、１３：平均資源使用データ、１４：
ユーザ設定情報、１５：現在負荷データ、１６：予測負
荷データ

Claims (3)

【特許請求の範囲】
1. 【請求項１】複数の構成プログラムから構成される並列
   プログラムの各構成プログラムを複数の計算機から構成
   される並列計算機の各計算機に割り当てて並行して実行
   するときの計算機によってスケジュールされる負荷分散
   方法において、 各構成プログラムを該計算機で実行するときの構成プロ
   グラムの資源使用率を取得し、該構成プログラムを実行
   しない状態での各計算機全体の資源使用率を取得し、注
   目する資源の使用率の大きい構成プログラムから順に構
   成プログラムを注目する資源の使用率の小さい計算機か
   ら順に計算機に割り当てることを特徴とする並列計算機
   の負荷分散方法。
2. 【請求項２】さらに各構成プログラムを該計算機で実行
   するときの経過時間を取得し、経過時間が所定時間に達
   しない構成プログラムを除外して上記割当を行い、除外
   した構成プログラムについては経過時間の大きい構成プ
   ログラムから順に構成プログラムを注目する資源の使用
   率の小さい残りの計算機から順に計算機に割り当てるこ
   とを特徴とする請求項１記載の並列計算機の負荷分散方
   法。
3. 【請求項３】各構成プログラムを該計算機に割り当てる
   とき、構成プログラムの各資源使用率に割り当てる計算
   機の対応する資源使用率を加えた合計の資源使用率が所
   定の限界値を越える場合に割当をやめて注目する資源の
   使用率の次に大きい計算機に割り当てることを特徴とす
   る請求項１記載の並列計算機の負荷分散方法。