JPH07141305A

JPH07141305A - 並列計算機の実行制御方法

Info

Publication number: JPH07141305A
Application number: JP28640493A
Authority: JP
Inventors: Chisato Konno; 千里金野; Toshio Okochi; 俊夫大河内
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1993-11-16
Filing date: 1993-11-16
Publication date: 1995-06-02

Abstract

(57)【要約】【目的】並列計算機を不特定多数のユーザで同時に用
いる際に、プロセッサの利用効率を上げる方法を提供す
る。【構成】各ジョブをサブミットする際に、ジョブの最
小要求プロセッサ台数、使用上限プロセッサ台数、要求
実行時間など実行条件を指定し、プロセッサの各実行ジ
ョブに対する利用状況と空きプロセッサ数を管理するテ
ーブル３と、各稼働ジョブの占有使用プロセッサと経過
時間を管理するテーブル４と、各実行待ちジョブの実行
条件を管理するテーブル２を利用し、実行待ちジョブの
先頭のジョブについて、そのジョブが要求する最小のプ
ロセッサ台数が空き状態にあるかいなかを判別する。割
り当てるべき空きプロセッサが不足のときには、そのジ
ョブが必要とする数のプロセッサが空き状態になるま
で、後続のジョブを起動することなく待たせるか、ある
いはその後続のジョブを先に起動するかを上記テーブル
内の情報を使用して判別する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列計算機を不特定多
数のユーザで共用する際に、並列計算機の要素プロセッ
サの稼働率を高めるための、プログラムのスケジューリ
ングに関する。

【０００２】

【従来の技術】並列計算機を構成する複数のプロセッサ
の数が増大するにともない、それらのプロセッサを一つ
のプログラム（ジョブ）に占有させるのではなく、それ
らのプロセッサを複数群に分割して複数のジョブに割り
当て、これらのジョブを並列に実行させることが望まし
い。この際、いずれかの上部の実行が終了した時点で、
実行待ちの複数のジョブを、そのときの空きプロセッサ
の台数に応じて適宜スケジューリングして、並列計算機
にて実行させることになる。

【０００３】このスケジューリングのためには、各ジョ
ブに割り当てるプロセッサの台数をどのように決定する
かと言う問題がある。

【０００４】そのための一つの方法は、ジョブごとにそ
れが必要とするプロセッサの台数を予め決定しておくこ
とである。

【０００５】この決定されたジョブの台数を確保する方
法の一つとして、ジョブ中にそのジョブが必要とする台
数のプロセッサを確保する命令列を入れておくき、その
ジョブの実行時に、この命令を実行して、必要な数のプ
ロセッサを確保するという方法が、特開平３−４３８３
５に述べられている。

【０００６】

【発明が解決しようとする課題】上記のごとく、各プロ
グラム毎にそれの実行時に使用するプロセッサ台数を決
めておき、そのジョブを実行すべきときに、その必要な
台数のプロセッサを割り当てる方法では、その必要台数
より少ないプロセッサが空き状態になっても、それらの
プロセッサが使用されないままに放置されることにな
り、プロセッサの使用率が低くなる。この問題は、実行
待ちジョブが必要とするプロセッサの台数が大きいほど
顕著になる。

【０００７】本発明の目的は上記問題を解決し、不特定
多数のユーザが同時に並列計算機を使用する際に、最大
の利用効率を得るための計算機の実行制御方法を提供す
ることにある。

【０００８】

【課題を解決するための手段】本発明では、実行待ちジ
ョブの各々に関して、最小プロセッサ台数、使用要求上
限プロセッサ数、ジョブの実行要求時間を登録し、これ
らの登録情報を使用して、空き状態にプロセッサの台数
が実行待ちジョブの内の先頭のジョブが必要とする最小
プロセッサ台数より多いか否かを判別し、前者が後者よ
り多い場合には、その先頭の実行待ちジョブを起動し、
前者が後者より小さい場合には、その先頭空き待ちジョ
ブが要求する最小プロセッサ台数以上のプロセッサが空
き状態になる時刻を予想し、現在からその予想された時
刻までの経過時刻と、その先頭のジョブが要求する実行
時間と、そのプロセッサが要求する最小プロセッサ台数
と、その先頭のジョブの現在までの累積実行待ち時間と
に基づいて、そのジョブの後続のジョブを起動しない
で、その先頭のジョブが要求するプロセッサ台数のプロ
セッサが空き状態になるまで待つかあるいはその後続の
ジョブを起動するかを判別する。

【０００９】

【作用】ジョブの実行要求時間を登録することにより、
一定時間後のプロセッサの空き状況の予測を可能にし、
また各ジョブの使用プロセッサ数として、最小台数、最
大台数を指定することによって幅を持たせて登録するこ
とにより、スケジューラが計算機の稼働状況に応じてプ
ロセッサ数を指定された範囲の中から選択して実行する
ことを可能にする、これにより多数のプロセッサを使用
するジョブも確実に実行し、且つ、並列計算機のプロセ
ッサの稼働率を上げることができる。

【００１０】

【実施例】本発明の実施例を、図面を参照して説明す
る。

【００１１】図１に本発明が適用される計算機システム
の構成をしめす。

【００１２】図において、６１は並列計算機で、各プロ
セッサエレメントは、プロセッサ６２とそのプロセッサ
に対するローカルメモリ６３とからなり、このローカル
メモリ６３には、対応するプロセッサで実行されるプロ
グラムとそのプログラムで使用するデータとを保持す
る。これらのプロセッサはバス６４を介してフロントエ
ンドプロセッサ７０に接続されている。このフロントプ
ロセッサ７０には、実行すべき複数のジョブがこのフロ
ントエンドプロセッサに付随する記憶装置７１に入力さ
れ、それらのジョブを実行するタイミングとそれらを実
行するプロセッサとを決定することを主として行なう。
なお、図では、簡単化のためにジョブの入力装置は図示
されていない。

【００１３】実行要求（サブミット）されたジョブ（計
算機への実行要求単位）は、オペレーティングシステム
（以下ＯＳ）１により、実行待ちジョブ管理テーブル２
に、それらの実行要求の発生順に並べて登録される。

【００１４】サブミットは通常そのジョブの実行に必要
なプログラムとデータの所在および計算機側へのリソー
ス要求量などの指示を指定することにより行われる。

【００１５】ジョブのサブミットは、ジョブ制御言語も
しくはコマンドにより行なわれる。

【００１６】本実施例では、各ジョブのサブミット時に
は、各ジョブの実行に必要なプロセッサの最小の台数、
そのジョブの実行時に使用するプロセッサの上限台数、
該当ジョブにその最小台数のプロセッサが割り当ててそ
のジョブを実行したときに、そのジョブの実行に消費す
べき最大実行時間を示す実行要求時間（言い方を変えれ
ば、そのジョブの実行開始後その時間が経過したとき
に、そのジョブの実行が終了していない場合には、その
ジョブの実行を打ち切るべきことを示す時間）、記憶装
置７１内のそのジョブの記憶位置のアドレスを指定する
ようになっている。

【００１７】実行待ちジョブ管理テーブル２は、図２に
示すように、各々のジョブの名称ＷＯＢｉとともに、そ
のジョブに関して入力された、最小プロセッサ台数ＰＭ
ｉ（２１）、使用要求上限プロセッサ台数ＰＵｉ（２
２）、実行要求時間ＴＥｉ（２３）、と記憶装置７１内
のそのジョブの格納アドレスを示すポインタ（２４）を
保持するとともに、そのジョブの実行が要求されてから
のそのジョブの実行待ち時間ＴＭｉ（２５）を保持する
ようになっている。

【００１８】稼働ジョブ管理テーブル４は、図３に示す
ように、現在稼働しているジョブに関する実行状況を保
持するテーブルで、各ジョブＥＪＯＢｉが使用している
プロセッサ台数ＰＥｉと、そのジョブの実行開始時刻
と、そのジョブの打切り残り時間ＴＲｉを保有する。こ
のうち、打ち切り残り時間は、そのジョブの実行が終了
しない場合にそのジョブを打ち切ってもよい残り時間で
ある。この残り打ち切り時間は、そのジョブについて指
定された要求実行時間とこれまでのそのジョブの実行開
始後の経過時間とから算出する。

【００１９】各ジョブの実行要求時間はそのジョブを、
そのジョブに対してユーザが指定した最小台数のプロセ
ッサを割り当てて、そのジョブを実行したときに、その
実行を打ち切ってもよい時刻である。しかし、後述する
ように、本実施例では、各ジョブには、最小台数から最
大台数の間の台数のプロセッサを割り当てる。従って、
そのジョブに対して最小台数より多いプロセッサを割り
当てた場合には、各ジョブを実行開始してからその実行
を打ち切ってもよい時刻までの経過時間（修正された要
求実行時間）は、ユーザ指定した要求実行時間ＴＥｉよ
り小さくてもよいはずである。つまり、修正された要求
実行時間は、近似的には、ユーザが要求した要求実行時
間ｘ（そのジョブへ割り当てたプロセッサ台数時間とそ
のジョブに対してユーザが要求した最小台数との比）と
することが出来る。この場合、残り打ち切り時間は、こ
の修正要求実行時間から、そのジョブの実行後の経過時
間を引いたものである。

【００２０】一般には、ジョブの実行時間は、そのジョ
ブに割り当てられたプロセッサの台数には比例はしな
い。例えば、２倍の台数でそのジョブを実行したとして
も、そのジョブの実行時間は半分になるわけでない。従
って、上記修正要求時間の計算も、上述のように上記台
数の比に比例しないで計算する方がより正確になる。

【００２１】しかし、この要求実行時間自体は、ジョブ
の実行が異常に長く掛かったときにそのジョブの実行を
打ち切るか否かを決めるための時間であり、その値自体
は絶対的に重要ではない。言わば打ち切りのための目安
である。従って、本実施例では、上記修正要求実行時間
の計算は、簡単化のために上述のようにする。

【００２２】プロセッサ管理テーブル３は、図４に示す
ように、プロセッサエレメントの使用状況を管理するた
めのテーブルで、現在からいろいろの将来の時刻までの
経過時間ＴＦｋにおける空きプロセッサ台数ＰＶｋの予
測値を保有する。

【００２３】この空き台数ＰＶｋは、現在の空きプロセ
ッサ台数ＰＶ０と、テーブル４の各稼働ジョブの打切り
残り時間ＴＲｉと使用プロセッサ台数ＰＥｉを利用して
ＯＳ１により算出される。すなわち、稼働ジョブ管理テ
ーブル４のジョブ打切り時間ＴＲｍをソーティングして
空きプロセッサの増加する予測経過時間列｛ＴＦｋ｝を
求め、各ＴＦｋのそれ以下のＴＲｉの使用プロセッサ台
数ＰＥｉの総和とＰＶ０の和によりＰＶｋが求まる。式
で表すと、ＰＶｋ＝（ΣＰＥｉ）＋ＰＶ０で、ΣはＴＲ
ｉ＜ＴＦｋとなる全てのｉに関する総和である。

【００２４】ここで使用する将来の経過時間ＴＦｋは、
実行中のいずれかのジョブの上記残り打ち切り時間が現
時点より経過した時点である。

【００２５】次にスケジューリングの全体処理フローを
図５を用いて説明する。

【００２６】ＯＳは、実行中のジョブのいずれかの実行
が終了したとき、あるいは新たなジョブの実行要求があ
る毎に、以上に説明したテーブルの内容を更新し（ステ
ップ５０）、その後以下の処理を、実行待ちジョブの中
から先頭のジョブを選び（５１）、選ばれたジョブに対
して以下を行う。

【００２７】そのジョブの要求最小プロセッサ台数ＰＭ
ｉより多くの空きプロセッサ数ＰＶ０があるか否かを判
定する（５２）。

【００２８】要求最小台数ＰＭｉ以上の空きプロセッサ
がある場合、ステップ５３において、その最小台数ＰＭ
ｉ以上で要求上限台数ＰＵｉ以下の範囲でなるべく多く
の空きプロセッサをそのジョブ用に確保する。すなわ
ち、空きプロセッサ数ＰＶ０が使用上限プロセッサ数Ｐ
Ｕｉより小さければＰＶ０台のプロセッサをそのジョブ
に割り当て、空きプロセッサ数ＰＶ０が使用上限プロセ
ッサ数ＰＵｉより大きければＰＵｉ台のプロセッサをそ
のジョブに割り当てる。

【００２９】ステップ５３では、さらにテーブル４２、
４３、４４をアップデートし、そのジョブを起動する
（５３）。

【００３０】起動にあたっては、フロントエンドプロセ
ッサ７０は、記憶装置７１からそのジョブのプログラム
を確保されたプロセッサ６２に接続されたローカルメモ
リ６３に転送して行なう。その際、確保されたプロセッ
サの識別子等、そのジョブをそれらの確保されたプロセ
ッサで分散して実行させるのに必要な情報を併せて転送
する。

【００３１】本実施例では、各ジョブに対して、最小プ
ロセッサ台数ＰＭｉ以上のプロセッサを割り当てるの
は、ユーザが期待する速度に近い速度であるいはそのジ
ョブが必要とする最小限の台数のプロセッサでそのジョ
ブを実行するためである。

【００３２】さらに、起動するジョブに割り当てる台数
を最大プロセッサ台数ＰＵｉ以下にするのは、ユーザが
期待する最大実行速度に近い速度でそのジョブを実行さ
せれば、スケジューリングとしてはユーザの要求に十分
答えたことになる上に、一般にジョブが必要とする最適
なプロセッサ台数以上の台数をそのジョブに割り当てて
も実行速度は格別増大しないからである。

【００３３】判定５２において、空きプロセッサ数ＰＶ
0がそのジョブの要求する必要最小台数ＰＭｉより少な
い時は、そのジョブの起動は中止する。その際、以下に
のべるようにして、その最低台数ＰＭｉ以上のプロセッ
サが空き状態になるまで待ってからそのジョブを起動す
るかあるいはそのジョブの後続のジョブが、そのジョブ
を追い越して起動可能か否かの判定を行なう。

【００３４】まず、プロセッサ管理テーブル３をサーチ
し、その先頭のジョブの必要台数のプロセッサが開放さ
れるまでの予測経過時間ＴＦｋを算出する（５４）。

【００３５】次にこうして求めた予測経過時間（即ち稼
働できるまでの最大待ち時間）ＴＦｋと、テーブル２、
４に登録されているこのジョブの要求最小プロセッサ台
数ＰＭｉ、要求実行時間ＴＥｉ，およびこれまでの累積
待ち時間ＴＭｉが予め定めた条件式を満たすか否かを判
断する（５５）。

【００３６】この条件式は、占有するプロセッサ数ＰＭ
ｉや要求実行時間ＴＥｉが小さく、稼働可能時間ＴＦｋ
までの待ちが小さく、更に累積待ち時間ＴＭｉがある程
度大きければ、このジョブが必要とする要求最小プロセ
ッサ台数の空きを待つようにするためのものである。

【００３７】例えば、ｈ，ｇ，ｌ，ｆを一次関数で、そ
れぞれパラメータＴＦｋ、ＴＥｉ、ＰＭｉ、ＴＭｉの係
数に正の数を持つものとして、条件式はつぎのものであ
る。

【００３８】（ある定数）＜ｆ（ＴＭｉ）または、ｈ（ＴＦｋ）＊ｇ（ＴＥｉ）＊ｌ（ＰＭｉ）＜ｆ（ＴＭ
ｉ）ここで、時刻に関する種々のパラメータは予め定めた単
位でもって計測するものとする。

【００３９】後者は、ＴＦｋやＴＥｉやＰＭｉが小さ
く、かつＴＭｉが大きければ成り立ち易い条件で、上述
したように、占有するプロセッサ数や時間が小さく、稼
働可能時間までの待ちが小さく、更に累積待ち時間があ
る程度大きければ、該当ジョブを実行するための条件で
ある。

【００４０】前者はある規定時間以上待ったジョブは必
ず実行してやるための条件である。前者は実質的には後
者の特別な場合と解釈できるが、累積待ち時間ＴＭｉが
ある限界を越えたときには、他のパラメータの値とは無
関係に、後続のジョブを起動することなく、先頭ジョブ
が必要とするプロセッサが空き状態になるまで待つこと
にしている。

【００４１】ｈ，ｇ，ｌ，ｆの最も単純なものは、それ
らの関数の変数そのものである。

【００４２】その時は上の条件式は、ＴＦｋ＊ＴＥｉ＊ＰＭｉ＜ＴＭｉまたは定数＜ＴＭ
ｉとなる。

【００４３】ステップ５５でこのときの先頭のジョブが
これらの条件のいずれかを満たすと判断されたときには
そのジョブに対しては、スケジューリングを凍結し、
ＰＭｉ以上のプロセッサの空くのを待って、プロセッサ
を確保しそのジョブの起動をかけ、テーブル２、３、４
をアップデートする（５６）。

【００４４】本状態で待っている間は、各ジョブの終了
が報告される度に、テーブル２、３、４をアップデート
し、その時点でＰＶｏがＰＭｉより大きくなっていれば
このときの先頭ジョブの起動をかけることになる。

【００４５】ステップ５５で、このときの先頭のジョブ
がこれらの条件のいずれかをも満たさないと判断された
ときにはそのジョブの後続のジョブに対してステップ
５２から５６を実行する。この結果、この後続のジョブ
に対してステップ５２により、その後続のジョブが必要
とする要求最小プロセッサ台数の空きプロセッサがある
と判断されたときには、その後続のジョブに対してステ
ップ５３を行なう。この場合、前述の先頭のジョブを追
い越してこの後続のジョブを起動することになる。

【００４６】しかし、この後続のジョブに対して、ステ
ップ５５により、そのジョブが必要とする台数のプロセ
ッサが空き状態になるまでスケジューリングを凍結する
と判断されされたときには、さらに後続のジョブに対し
て上記ステップ５６を行なう。

【００４７】こうして、いずれかのジョブに対してステ
ップ５３またはステップ５６が実行されるまで、ステッ
プ５２から５６の処理が繰り返される。

【００４８】いずれかのジョブに対して、ステップ５３
あるいは５６が実行されたときには、この時点でのスケ
ジューリングは終了する。その後、実行中のジョブの実
行が終了したときあるいは新たなジョブの実行要求が入
力されたときに、再度ステップ５０からスケジューリン
グが繰り返される。

【００４９】図６は、以上のスケジューリングによるプ
ロセッサの動作例を示したものである。

【００５０】この例は、図７に例示する、実行待ちジョ
ブ管理テーブル２の要部に示されているような複数のジ
ョブに対してスケジュールの例である。ここでは、プロ
セッサ総数が８台の場合を例にしている。

【００５１】とくに、ここでは、ジョブＪ２が最小８台
のプロセッサを必要とするが、ジョブ１の実行中には、
その台数のプロセッサが空き状態にならないので、その
台数のプロセッサの空きを待たないで、それぞれ最小２
台のプロセッサを要求する後続のジョブＪ２、Ｊ３、Ｊ
４、Ｊ５を２台のプロセッサが空きになるごとに順次起
動する。ジョブ６は最小４台のプロセッサを要求する
が、この台数のプロセッサの空きを待たないでそれぞれ
最小２台のプロセッサを要求する後続のジョブＪ７、Ｊ
８、Ｊ９を起動している。ジョブ１が終了した時点で
は、２台の空きプロセッサしかないため、先頭の実行待
ちジョブＪ２は、相変わらず起動されないが、次の実行
待ちジョブＪ６に関する前述の条件式による判別の結
果、このジョブ７が終了するまで待ち、それが終了した
した時点でジョブ６をが起動する方がよいと判断されて
いる。こうして、ジョブＪ７の終了時に、ジョブＪ６が
起動されている。

【００５２】ジョブＪ６が終了した時点では、実行待ち
ジョブの先頭のジョブＪ２は累積経過時間が長いため
に、他のジョブを実行させることなくこのジョブが必要
な８台のプロセッサが空きになるまで待つ状態になる。
こうして、ジョブ５、９が終了した時点でこのジョブＪ
２が起動され、それが終了すると、残りのジョブの先頭
のジョブＪ１０が起動される。

【００５３】この例から分かるように、実行待ちの先頭
のジョブが必要な台数のプロセッサが空き状態になって
いないときに、後続のジョブで、その台数以下のプロセ
ッサを使用するジョブを起動することにより、プロセッ
サの利用率を高めている。しかし、こうして起動が後回
しにされたジョブがいつまでの起動されないままになる
のを防止するようになっている。

【００５４】なお、以上において、並列計算機の全プロ
セッサ数を使用上限プロセッサ台数ＰＵiとするジョブ
をサブミットする場合、使用上限プロセッサ台数ＰＵi
の指定を省略するようにすることも出来る。同様に、要
求最小プロセッサ台数ＰＭiが１台であるジョブをサブ
ミットする場合、要求最小プロセッサ台数ＰＭiの指定
を省略するようにすることも出来る。

【００５５】（変形例）更に本スケジューリングには以
下のような変形例が考えられる。

【００５６】（１）図３のステップ５３において、累積
待ち時間ＴＭiが所定値を越えているか否かだけを判別
するようにすることも出来る。このとき、ステップ５４
は省略される。

【００５７】（２）さらに、ステップ５２における稼動
されるまでの待ち時間ＴＦｋ、実行要求時間ＴＥi、最
小要求プロセッサ台数ＰＭi、累積待ち時間ＴＭiに関す
る条件式を、稼動されるまでの待ち時間ＴＦｋと累積待
ち時間ＴＭiとに関する条件式に変更することもよい。
すなわち、関数ｆ（ＴＭi）とｈ（ＴＦｋ）との比ｆ
（ＴＭi）／ｈ（ＴＦｋ）が所定値を越えるかいなかを
判別する条件式に代える。この比が所定値を越えている
ときには、ステップ５６に進む。

【００５８】こうして、ＴＭｉがある程度大きく、ＴＦ
ｋが小さくなると、後続のジョブを起動することなく、
この先頭の実行待ちジョブが必要なプロセッサ台数が空
くのを待つことになる。

【００５９】（３）図３のステップ５２において、実行
待ちジョブの先頭のジョブの実行要求時間ＴＥｉも考慮
にいれてその実行を決定することも可能である。

【００６０】すなわち、その時間があまり長時間である
場合には、例えば、その時間が一定値より長い場合、そ
のプロセッサが要求する最小要求プロセッサ台数以上の
空きプロセッサが利用可能であっても、そのジョブを起
動しないようにし、実行待ちの次のジョブの起動可否を
判別する。こうして、そのような長時間にわたりプロセ
ッサを占有するジョブのプライオリティを下げる。

【００６１】（４）また図３のステップ５３において、
要求最小プロセッサ台数ＰＭｉ以上で、かつ、空きプロ
セッサ台数ＰＶ0と使用上限プロセッサ台数ＰＵIの内の
最小値ｍｉｎ（ＰＶ０，ＰＵｉ）以下の何台のプロセッ
サを使用するかを、後続のジョブの最小要求プロセッサ
台数に依存して決めることも可能である。例えば、空き
プロセッサ台数ＰＶ0と要求最小プロセッサ台数ＰＭｉ
の差以下のプロセッサ台数を要求する後続の実行待ちジ
ョブがある場合、この後続のプロセッサが要求する最小
要求プロセッサ台数を、上記空き台数から差引き、その
残りを上記先頭の実行待ちジョブに割り当てる。これに
より、この先頭の実行待ちジョブとその後続の実行待ち
ジョブとを続けて起動することが可能になり、本実施例
に比べて、より多くのジョブの同時稼働が可能となる。

【００６２】（５）また図３のステップ５５において、
ｈ，ｇ，ｌ，ｆを関数としたが、これは常に固定で用い
る必要はなく、経験によって関数のパラメタを動的に変
更したり、運用によって関数自体の形式を変更させるこ
とも考えられる。

【００６３】例えば、待ち時間がある値以上になること
が多いようであれば、条件式を緩和させたり、運用によ
ってある時間帯は関数ｇやｌをある基準より大きな独立
変数に対しては十分大きな値をとらせることにより、あ
る時間帯はある程度より小さいジョブのみを優先して走
らせることも可能である。

【００６４】（６）また、図３のステップ５６におい
て、最小要求プロセッサ台数ＰＭｉ以上のプロセッサが
空き状態となる最大待ち時間ＴＦｋ内は単に待っている
だけでなく、その時間内に終り、かつ現状の空きプロセ
ッサ台数ＰＶ0以下のプロセッサで実行可能な後続ジョ
ブが一つあるいは複数あればそのひとつのジョブあるい
はそれらの複数のジョブを起動することも望ましい。こ
の際、ＰＭｉ以上のプロセッサの空く最大待ち時間ＴＦ
ｋは変わることはない。

【００６５】（７）また、本実施例は、全てのジョブを
待ち順序に従ってスケジューリングされる例を示した
が、ある範囲内のプロセッサ数を要求するジョブ群毎に
クラスを設けて、特定のプロセッサ群をそのクラスに割
当て、そのクラス内で上記のスケジューリングをするこ
とも可能である。

【００６６】

【発明の効果】複数のジョブが並列計算機上で同時に実
行する際に問題になるプロセッサの割り付けやトータル
スループットを解決し、並列計算機の不特定多数による
同時利用の際のプロセッサの利用効率を上げることがで
きる。

【００６７】また、多数のプロセッサを要求する巨大ジ
ョブも、小型ジョブに割り込まれて永久にスケジューリ
ングされないことを回避することができる。

【図面の簡単な説明】

【図１】本発明を適用される計算機システムの全体構成
図。

【図２】図１のシステムに使用する実行待ちジョブ管理
テーブルの内容を示す図。

【図３】図１のシステムに使用する稼動ジョブ管理テー
ブルの内容を示す図。

【図４】図１のシステムに使用するプロセッサ管理テー
ブルの内容を示す図。

【図５】図１のシステムのＯＳが実行するスケジューリ
ングのフローチャート。

【図６】図１のシステムによるスケジューリングの具体
例を示す図。

【図７】図６の具体例に使用した複数のジョブの関す
る、実行待ちジョブ管理テーブルの内容例を示す図。

Claims

【特許請求の範囲】

【請求項１】(a)複数のプロセッサを有する並列計算機
における実行を待つ複数のジョブの各々に対して、その
ジョブに関して指定された、そのジョブの実行に使用す
べきプロセッサの台数を表す要求プロセッサ台数を記憶
し、 (b)いくつかの空きプロセッサが発生した時点で、該複
数の実行待ちジョブのうち、最先に実行要求が発行され
たジョブ（最先のジョブ）に関して記憶された要求プロ
セッサ台数が、該空きプロセッサの総数以下か否かを判
別し、 (c)そのステップ(b)による判別の結果、その最先のジョ
ブに対して記憶された要求プロセッサ台数がその空きプ
ロセッサの総数より小さいと判別されたときに、その最
先のジョブに対して該要求プロセッサ台数以上のプロセ
ッサを割り当てて、該最先のジョブを起動し、 (d)そのステップ(b)による判別の結果、その最先のジョ
ブに対して記憶された要求プロセッサ台数がその空きプ
ロセッサの総数より大きいと判別されたときに、その最
先のジョブの実行要求が発行されてから現在までの累積
待ち時間に基づいて、該最先のジョブとその後続のジョ
ブのいずれを優先して起動すべきかを判別し、 (e)該最先のジョブを優先して起動すべきと判別された
ときには、該最先のジョブに対して記憶された要求プロ
セッサ台数以上の空きプロセッサが発生するのを待ち、 (f)該最先のジョブに優先していずれかの後続のジョブ
を起動すべきと判別されたときには、該最先のジョブの
後続のジョブに関して、該ステップ(b),(c)を実行する
ステップからなる並列計算機の実行制御方法。
【請求項２】(g)各実行待ちジョブに対して使用上限プ
ロセッサ台数を記憶するステップをさらに有し、上記ステップ(a)で各ジョブに対して記憶された該要求
プロセッサ台数は、そのジョブを実行するための要求最
小プロセッサ台数であり、上記ステップ(c)は、該空きプロセッサ台数と上記最先
のジョブに対して記憶された、要求最小プロセッサ台数
および使用上限プロセッサ台数とに基づいて、該最先の
ジョブに割り当てるべきプロセッサの台数を決定するス
テップを有する請求項１記載の並列計算機の実行制御方
法。
【請求項３】上記ステップ(c)は、該空きプロセッサ台
数と上記最先のジョブに対して記憶された使用上限プロ
セッサ台数の内のいずれか小さい方の台数を該最先のジ
ョブに割り当てるステップからなる請求項２記載の並列
計算機の実行制御方法。
【請求項４】上記ステップ(c)は、後続の実行待ちの複数のジョブに対して記憶された使用
最小プロセッサ台数のうちの最小の値を検出し、検出された最小の値と、該空きプロセッサ台数と上記最
先のジョブに対して記憶された、要求最小プロセッサ台
数および使用上限プロセッサ台数とに基づいて、該最先
のジョブに割り当てるべきプロセッサの台数を決定する
ステップを有する請求項１記載の並列計算機の実行制御
方法。
【請求項５】上記ステップ(c)は、該検出された値が、該空きプロセッサの総数と該最先に
実行要求が発行されたジョブに関して記憶された要求最
小プロセッサ台数との差以下であるか否かを判別し、該検出された値が上記差以下であるとき、その最先のジ
ョブには、該空きプロセッサ台数と該検出された値との
差の台数のプロセッサを割り当てるステップをさらに有
する請求項４記載の並列計算機の実行制御方法。
【請求項６】(a)複数のプロセッサを有する並列計算機
における実行を待つ複数のジョブの各々に対して、その
ジョブに関して指定された、そのジョブの実行に使用す
べきプロセッサの台数を表す要求プロセッサ台数を記憶
し、 (b)いくつかの空きプロセッサが発生した時点で、該複
数の実行待ちジョブのうち、最先に実行要求が発行され
たジョブ（最先のジョブ）に関して記憶された要求プロ
セッサ台数が、該空きプロセッサの総数以下か否かを判
別し、 (c)ステップ(b)による判別の結果、その最先のジョブに
対して記憶された要求プロセッサ台数がその空きプロセ
ッサの総数より小さいと判別されたときに、その最先の
ジョブに対して該要求プロセッサ台数以上のプロセッサ
を割り当てて、該最先のジョブを起動し、 (d)ステップ(b)による判別の結果、その最先のジョブに
対して記憶された要求プロセッサ台数がその空きプロセ
ッサの総数より大きいと判別されたときに、実行中の一
つまたは複数のジョブの各々の終了時刻を予想し、 (e)実行中の各ジョブについての予想終了時刻に基づい
て、現在から、該最先のジョブに対して記憶された要求
最小プロセッサ台数以上の空きプロセッサが発生する時
刻までの経過時間を予想し、 (f)少なくとも該予想経過時間に基づいて、該最先のジ
ョブとその後続のジョブのいずれを優先して起動すべき
かを判別し、 (g)該最先のジョブを優先して起動すべきと判別された
ときには、該最先のジョブに対して記憶された要求プロ
セッサ台数以上の空きプロセッサが発生するのを待ち、 (h)該最先のジョブに優先していずれかの後続のジョブ
を起動すべきと判別されたときには、該最先のジョブの
後続のジョブに関して、該ステップ(b),(c)を実行する
ステップからなる並列計算機の実行制御方法。
【請求項７】(i)各実行待ちジョブに対して、そのジョ
ブに対して記憶された要求プロセッサ台数のプロセッサ
でそのジョブを実行するときの最大ジョブ実行時間を表
す実行要求時間を記憶するステップをさらに有し、上記ステップ(d)は、実行中のジョブの各々に対して記
憶された実行要求時間とそのジョブの実行開始時刻とに
基づいて、そのジョブの終了時刻を予想するステップか
らなる請求項６記載の並列計算機の実行制御方法。
【請求項８】(i)各実行待ちジョブに対して使用上限プ
ロセッサ台数を記憶するステップをさらに有し、上記ステップ(a)で各ジョブに対して記憶された該要求
プロセッサ台数は、そのジョブを実行するための要求最
小プロセッサ台数であり、上記ステップ(c)は、該空きプロセッサ台数と上記最先
のジョブに対して記憶された、要求最小プロセッサ台数
および使用上限プロセッサ台数とに基づいて、該最先の
ジョブに割り当てるべきプロセッサの台数を決定するス
テップを有する請求項６記載の並列計算機の実行制御方
法。
【請求項９】(j)各実行待ちジョブに対して、そのジョ
ブに対して記憶された要求最小プロセッサ台数のプロセ
ッサでそのジョブを実行するときの最大ジョブ実行時間
を表す実行要求時間を記憶するステップをさらに有し、上記ステップ(d)は、実行中のジョブの各々に対して記憶された要求最小プロ
セッサ台数と、そのジョブに割り当てられたプロセッサ
台数と、そのジョブに対して記憶された実行要求時間と
に基づいて、その要求最小プロセッサ台数に代えて、そ
の割り当て台数でそのジョブを実行するときのそのジョ
ブの最大実行時間を表す修正実行要求時間を算出し、各実行中のジョブに対して算出された修正実行要求時間
とそのジョブの実行開始時刻とに基づいて、そのジョブ
の予想終了時刻を予想するステップを有する請求項８記
載の並列計算機の実行制御方法。
【請求項１０】上記ステップ(c)は、該空きプロセッサ
台数と上記最先のジョブに対して記憶された使用上限プ
ロセッサ台数の内のいずれか小さい方の台数を該最先の
ジョブに割り当てるステップからなる請求項８記載の並
列計算機の実行制御方法。
【請求項１１】上記ステップ(c)は、後続の実行待ちの複数のジョブに対して記憶された使用
最小プロセッサ台数のうちの最小の値を検出し、検出された最小の値と、該空きプロセッサ台数と上記最
先のジョブに対して記憶された、要求最小プロセッサ台
数および使用上限プロセッサ台数とに基づいて、該最先
のジョブに割り当てるべきプロセッサの台数を決定する
ステップを有する請求項８記載の並列計算機の実行制御
方法。
【請求項１２】上記ステップ(c)は、該検出された値が、該空きプロセッサの総数と該最先に
実行要求が発行されたジョブに関して記憶された要求最
小プロセッサ台数との差以下であるか否かを判別し、該検出された値が上記差以下であるとき、その最先のジ
ョブには、該空きプロセッサ台数と該検出された値との
差の台数のプロセッサを割り当てる請求項１１記載の並
列計算機の実行制御方法。
【請求項１３】(a)複数のプロセッサを有する並列計算
機における実行を待つ複数のジョブの各々に対して、そ
のジョブに関して指定された、そのジョブの実行に使用
すべきプロセッサの台数を表す要求プロセッサ台数を記
憶し、 (b)いくつかの空きプロセッサが発生した時点で、該複
数の実行待ちジョブのうち、最先に実行要求が発行され
たジョブ（最先のジョブ）に関して記憶された要求プロ
セッサ台数が、該空きプロセッサの総数以下か否かを判
別し、 (c)その判別ステップによる判別の結果、その最先のジ
ョブに対して記憶された要求プロセッサ台数がその空き
プロセッサの総数より小さいと判別されたときに、その
最先のジョブに対して該要求プロセッサ台数以上のプロ
セッサを割り当てて、該最先のジョブを起動し、 (d)ステップ(b)による判別の結果、その最先のジョブに
対して記憶された要求プロセッサ台数がその空きプロセ
ッサの総数より大きいと判別されたときに、実行中の一
つまたは複数のジョブの各々の終了時刻を予想し、 (e)実行中の各ジョブについての予想終了時刻に基づい
て、現在から、該最先のジョブに対して記憶された要求
最小プロセッサ台数以上の空きプロセッサが発生する時
刻までの経過時間を予想し、 (f)少なくとも該予想経過時間と、その最先のジョブの
実行要求が発行されてから現在までの累積待ち時間とに
基づいて、該最先のジョブとその後続のジョブのいずれ
を優先して起動すべきかを判別し、 (g)該最先のジョブを優先して起動すべきと判別された
ときには、該最先のジョブに対して記憶された要求プロ
セッサ台数以上の空きプロセッサが発生するのを待ち、 (h)該最先のジョブに優先していずれかの後続のジョブ
を起動すべきと判別されたときには、該最先のジョブの
後続のジョブに関して、該ステップ(b),(c)を実行する
ステップからなる並列計算機の実行制御方法。
【請求項１４】(i)各実行待ちジョブに対して、そのジ
ョブに対して記憶された要求プロセッサ台数のプロセッ
サでそのジョブを実行するときの最大ジョブ実行時間を
表す実行要求時間を記憶するステップをさらに有し、上記ステップ(d)は、実行中のジョブの各々に対して記
憶された実行要求時間とそのジョブの実行開始時刻とに
基づいて、そのジョブの終了時刻を予想するステップか
らなる請求項１３記載の並列計算機の実行制御方法。
【請求項１５】(i)各実行待ちジョブに対して使用上限
プロセッサ台数を記憶するステップをさらに有し、上記ステップ(a)で各ジョブに対して記憶された該要求
プロセッサ台数は、そのジョブを実行するための要求最
小プロセッサ台数であり、上記ステップ(c)は、該空きプロセッサ台数と上記最先
のジョブに対して記憶された、要求最小プロセッサ台数
および使用上限プロセッサ台数とに基づいて、該最先の
ジョブに割り当てるべきプロセッサの台数を決定するス
テップを有する請求項１３記載の並列計算機の実行制御
方法。
【請求項１６】(j)各実行待ちジョブに対して、そのジ
ョブに対して記憶された要求最小プロセッサ台数のプロ
セッサでそのジョブを実行するときの最大ジョブ実行時
間を表す実行要求時間を記憶するステップをさらに有
し、上記ステップ(d)は、実行中のジョブの各々に対して記憶された要求最小プロ
セッサ台数と、そのジョブに割り当てられたプロセッサ
台数と、そのジョブに対して記憶された実行要求時間と
に基づいて、その要求最小プロセッサ台数に代えて、そ
の割り当て台数でそのジョブを実行するときのそのジョ
ブの最大実行時間を表す修正実行要求時間を算出し、各ジョブに対して算出された修正実行要求時間と、その
ジョブの実行開始時刻とに基づいて、そのジョブの終了
時刻を予想するステップからなる請求項１５記載の並列
計算機の実行制御方法。
【請求項１７】上記ステップ(c)は、該空きプロセッサ
台数と上記最先のジョブに対して記憶された使用上限プ
ロセッサ台数の内のいずれか小さい方の台数を該最先の
ジョブに割り当てるステップからなる請求項１５記載の
並列計算機の実行制御方法。
【請求項１８】上記ステップ(c)は、後続の実行待ちの複数のジョブに対して記憶された使用
最小プロセッサ台数のうちの最小の値を検出し、検出された最小の値と、該空きプロセッサ台数と上記最
先のジョブに対して記憶された、要求最小プロセッサ台
数および使用上限プロセッサ台数とに基づいて、該最先
のジョブに割り当てるべきプロセッサの台数を決定する
ステップを有する請求項１５記載の並列計算機の実行制
御方法。
【請求項１９】上記ステップ(c)は、該検出された値が、該空きプロセッサの総数と該最先に
実行要求が発行されたジョブに関して記憶された要求最
小プロセッサ台数との差以下であるか否かを判別し、該検出された値が上記差以下であるとき、その最先のジ
ョブには、該空きプロセッサ台数と該検出された値との
差の台数のプロセッサを割り当てる請求項１８記載の並
列計算機の実行制御方法。
【請求項２０】(a)複数のプロセッサを有する並列計算
機における実行を待つ複数のジョブの各々に対して、そ
のジョブに関して指定された、そのジョブの実行に必要
なプロセッサの最小台数を表す要求最小プロセッサの台
数と、該必要なプロセッサの上限台数を表す使用上限プ
ロセッサ台数と、その要求最小プロセッサ台数のプロセ
ッサでそのジョブを実行するときの最大ジョブ実行時間
を表す実行要求時間とを記憶し、 (b)いくつかの空きプロセッサが発生した時点で、該複
数の実行待ちジョブのうち、最先に実行要求が発行され
たジョブ（最先のジョブ）に関して記憶された要求最小
プロセッサ台数が、該空きプロセッサの総数以下か否か
を判別し、 (c)ステップ(b)による判別の結果、その最先のジョブに
対して記憶された要求最小プロセッサ台数がその空きプ
ロセッサの総数より小さいと判別されたときに、その最
先のジョブに対して該要求最小プロセッサ台数以上で、
かつ、その最先のジョブに対して記憶された使用上限プ
ロセッサ台数以下の台数のプロセッサを割り当てて、該
最先のジョブを起動し、 (d)ステップ(b)による判別の結果、その最先のジョブに
対して記憶された要求最小プロセッサ台数がその空きプ
ロセッサの総数より大きいと判別されたときには、各実
行中の一つまたは複数のジョブの各々の予想終了時刻を
予想し、 (e)実行中の各ジョブについての予想終了時刻に基づい
て、現在から、該最先のジョブに対して記憶された要求
最小プロセッサ台数以上の空きプロセッサが発生する時
刻までの経過時間を予想し、 (f)該予想経過時間と、その最先のジョブの実行要求が
発行されてから現在までの累積待ち時間と、そのジョブ
に対して記憶された要求最小プロセッサ台数および要求
実行時間とに基づいて、該最先のジョブとその後続のジ
ョブのいずれを優先して起動すべきかを判別し、 (g)該最先のジョブを優先して起動すべきと判別された
ときには、該最先のジョブに対して記憶された要求プロ
セッサ台数以上の空きプロセッサが発生するのを待ち、 (h)該最先のジョブに優先していずれかの後続のジョブ
を起動すべきと判別されたときには、該最先のジョブの
後続のジョブに関して、該ステップ(b),(c)を実行する
ステップからなる並列計算機の実行制御方法。
【請求項２１】上記ステップ(d)は、実行中のジョブの各々に対して記憶された要求最小プロ
セッサ台数と、そのジョブに割り当てられたプロセッサ
台数と、そのジョブに対して記憶された実行要求時間と
に基づいて、その要求最小プロセッサ台数に代えて、そ
の割り当て台数でそのジョブを実行するときのそのジョ
ブの最大実行時間を表す修正実行要求時間を算出し、各ジョブに対して算出された修正実行要求時間と、その
ジョブの実行開始時刻とに基づいて、そのジョブの終了
時刻を予想するステップからなる請求項２０記載の並列
計算機の実行制御方法。
【請求項２２】複数のプロセッサを有する並列計算機に
おける実行を待つ複数のジョブの各々に対して、そのジ
ョブに関して指定された、そのジョブの実行に必要な要
求最小プロセッサ台数、要求プロセッサ上限台数とを記
憶し、いくつかの空きプロセッサが発生した時点で、該複数の
実行待ちのジョブのうち、それらの空きプロセッサの総
数以下の要求最小プロセッサ台数を要求する一つのジョ
ブに、その要求最小プロセッサ台数以上で、該要求プロ
セッサ上限台数以下の台数の空きプロセッサを割り当て
て、そのジョブを起動するステップを有する並列計算機
の実行制御方法。
【請求項２３】該割り当てを行なう空きプロセッサの台
数は、該空きプロセッサの総数と該要求プロセッサ台数
の内のいずれか小さい方である請求項２２記載の並列計
算機の実行制御方法。
【請求項２４】該複数の実行待ちジョブのうち、最先に
実行要求が発行されたジョブ（最先のジョブ）に関して
記憶された要求最小プロセッサ台数が、該空きプロセッ
サの総数以下か否かを判別し、その判別ステップによる判別の結果、その最先のジョブ
に対して記憶された要求最小プロセッサ台数がその空き
プロセッサの総数より小さいと判別されたときに、その
最先のジョブに対して上記割り当てを行なう請求項２２
記載の並列計算機の実行制御方法。
【請求項２５】該割り当てを行なう空きプロセッサの台
数は、該空きプロセッサの総数と該要求プロセッサ台数
の内のいずれか小さい方である請求項２４記載の並列計
算機の実行制御方法。
【請求項２６】該最先のジョブの後続のいずれかのジョ
ブに関して記憶されている他の要求最小プロセッサ台数
が、該空きプロセッサの総数と該最先に実行要求が発行
されたジョブに関して記憶された要求最小プロセッサ台
数との差以下であるか否かを判別し、上記最先のジョブへのプロセッサの割り当てステップは
割り当てにおいては、この判別結果が肯定的であると
き、その最先のジョブには、該空きプロセッサ台数と該
後続のジョブに対して記憶された該他の要求最小プロセ
ッサ台数との差の台数のプロセッサを割り当てる請求項
２４記載の並列計算機の実行制御方法。