JPH0744505A - 並列計算機における負荷分散方法 - Google Patents

並列計算機における負荷分散方法

Info

Publication number
JPH0744505A
JPH0744505A JP20995493A JP20995493A JPH0744505A JP H0744505 A JPH0744505 A JP H0744505A JP 20995493 A JP20995493 A JP 20995493A JP 20995493 A JP20995493 A JP 20995493A JP H0744505 A JPH0744505 A JP H0744505A
Authority
JP
Japan
Prior art keywords
processing
distribution
request
threshold value
processing element
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
Application number
JP20995493A
Other languages
English (en)
Other versions
JP2526399B2 (ja
Inventor
Tokuyasu Imon
徳安 井門
Toshiaki Tarui
俊明 垂井
Takayuki Nakagawa
貴之 中川
Machiko Asaya
真知子 朝家
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
National Institute of Advanced Industrial Science and Technology AIST
Original Assignee
Agency of Industrial Science and Technology
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Agency of Industrial Science and Technology filed Critical Agency of Industrial Science and Technology
Priority to JP5209954A priority Critical patent/JP2526399B2/ja
Publication of JPH0744505A publication Critical patent/JPH0744505A/ja
Application granted granted Critical
Publication of JP2526399B2 publication Critical patent/JP2526399B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Landscapes

  • Multi Processors (AREA)

Abstract

(57)【要約】 【目的】 負荷量を均一化し、プロセシング・エレメン
トの稼働率を向上させつつ、無駄な処理の分配を抑止に
よりオーバヘッドを抑え、並列計算機の性能を向上させ
る。 【構成】 あるプロセシング・エレメントが一つの処理
の分配要求を受け取った後、一定時間内に再度の要求を
受け取った場合にそのプロセシング・エレメントのしき
い値を下げ、その一定時間内に再度の要求を受け取らな
かった場合に上記しきい値をあらかじめ定めた値に変更
する。 【効果】 稼働率が低下し処理分配要求が頻発すると処
理分配がされやすくなり、稼働率を向上させる。稼働率
が向上し処理分配要求が少なくなると無駄な分配が抑止
される。

Description

【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明は、複数のプロセシング・
エレメントからなる並列計算機における負荷分散方法に
関する。
【0002】
【従来の技術】従来の並列計算機における負荷分散方式
では、情報処理学会研究報告89−ARC−77;「プ
ロセッサ間ソフトウェア割込処理を高速化するスリット
チェック機構」に記載のように、実行する処理の無くな
ったとなったプロセッサが他の全てのプロセッサに対し
て処理の分配を要求し、処理を受け取る負荷分散方式が
示されている(以下、第一の従来技術と呼ぶ)。また、
オーム社コンピュータアーキテクチャシリーズ・電子情
報通信学会編「並列処理マシン」154ページのしきい
値方式に記載の様に自分の負荷がしきい値以下の場合は
新たな処理を自分自身に割り当て、しきい値を超えてい
る場合はしきい値を超えていない他のプロセシング・エ
レメントに割り当てていた(以下、第二の従来技術と呼
ぶ)。
【0003】
【発明が解決しようとする課題】並列計算機の性能を向
上させるためには、各プロセシング・エレメントの稼働
率を向上させるとともに各プロセシング・エレメント間
の同期処理のオーバヘッドの削減も必要である。上記第
一の従来技術と第二の従来技術を組み合わせた負荷分散
方式、すなわち、負荷がしきい値以下のプロセシング・
エレメントが処理の分配を要求し、負荷がしきい値より
大きいプロセシング・エレメントが要求に応ずる方式で
は、しきい値を大きく設定した場合は処理の分配が発生
しないため各プロセシング・エレメントの負荷にバラツ
キが生じ稼働率が低下する。また、しきい値を小さくし
た場合は処理を多く有するプロセシング・エレメントか
らだけでなく処理の少ないプロセシング・エレメントか
らも分配が生じ、この分配は無駄なオーバヘッドを増加
させる。
【0004】本発明の目的は、少ない処理の分配でプロ
セシング・エレメントの稼働率を向上させ、それによっ
て全体の性能を向上させる並列計算機における負荷分散
方式を提供することにある。
【0005】
【課題を解決するための手段】上記目的を達成するため
に、処理の分配要求が多い時間帯はしきい値を下げ、分
配が生じるようにし、処理の分配要求が少ない時間帯は
しきい値をユーザが設定した高い値とするようにしたも
のであり、あるプロセシング・エレメントが一つの処理
の分配要求を受け取った後、一定時間内に再度の要求を
受け取った場合にそのプロセシング・エレメントのしき
い値を下げ、その一定時間内に再度の要求を受け取らな
かった場合に上記しきい値をあらかじめ定めた値に変更
する。
【0006】
【作用】一定時間内に複数の処理の分配要求が到着する
ような場合は多くのプロセシング・エレメントが処理を
有してないと判断し処理分配のしきい値を下げるため処
理の分配が頻繁に行われ稼働率が向上する。一定時間内
に複数の処理の分配要求が到着しない場合は多くのプロ
セシング・エレメントが既に処理を有していると判断し
処理分配のしきい値を設定された高い値に上げるため処
理をあまり有していないプロセシング・エレメントから
の無駄な処理の分配が生じないため少ない処理の分配で
稼働率を向上させることができる。
【0007】
【実施例】以下、本発明の一実施例を図を用いて説明す
る。図1は、並列計算機のプロセシング・エレメントに
おいて本発明の一実施例である負荷分散方式を実現した
場合のフローチャートを示す。尚、並列計算機の構成に
ついては図2に示す。まず図1を説明する。ステップ1
では、プロセシング・エレメントで実行すべき処理の有
無を判定する。実行すべき処理のある場合はステップ2
へ、無い場合はステップ3へ進む。ステップ2では処理
を実行する。ここで処理とは例えば、1つのプログラム
が複数の部分プログラムからできており、それらが並列
に実行可能なようなプログラムの部分プログラムであ
る。この次にステップ4に進む。ステップ3では、他の
プロセシング・エレメントに処理の分配を要求する。こ
こで処理分配要求はネットワークのメッセージとして他
のプロセシング・エレメントに送られる。なお、このメ
ッセージは他のすべてのプロセシング・エレメントに送
られてもよいし、何れか一つのプロセシング・エレメン
トに送られてもよい。ステップ4では、ネットワークか
ら到着したメッセージの有無を判定する。到着メッセー
ジがある場合ステップ5へ進み、無い場合ステップ1へ
進む。ステップ5では到着メッセージが処理分配要求で
あるかどうかを判定する。処理分配要求の場合ステップ
7へ、そうで無い場合ステップ6へ進む。ステップ6で
は到着メッセージを通常メッセージとして処理する。こ
のステップ6での処理はステップ2に関連する処理(例
えば、二つの部分プログラム間でのデータ通信)か処理
の分配の受け取り処理(例えば、部分プログラムの実行
待ちキューへの登録などである。図示せず。)である。
【0008】ステップ7以降は処理分配要求があった場
合であり、まずステップ7で以前に処理分配要求を受け
取った時間NEWTをOLDTにセットする。ここでM
EWT、OLDTはレジスタでもメモリでもよい。次に
NEWTにTODの値をセットする。TODはシステム
固有の時計である。その後、NEWTからOLDTを減
じた値とTTを比較し、TT以下であればステップ10
にそうでなければステップ11に進む。ここでTTはあ
らかじめ設定されている時間である。ステップ10では
しきい値THの二分の一の値を新たにTHにセットす
る。この新たにセットする値は小数点以下切捨てとす
る。ステップ11ではしきい値THにあらかじめ決めら
れている初期値をセットする。ステップ12では負荷量
がしきい値より大きい場合ステップ13へ進み、そうで
無い場合ステップ4へ進む。ステップ13では実行すべ
き処理のうちの一つを処理分配メッセージにして要求元
へ送り処理を分配し、その後、ステップ4へ戻る。
【0009】図2は先に述べたように並列計算機の構成
を示す。並列計算機は、複数のプロセシングエレメント
PE1〜PEnとこれらを相互に接続するネットワーク
NETからなる。このプロセシング・エレメントPE1
〜PEnにおいて図1で示したフローチャートにもとづ
き処理の実行が制御される。ネットワークNETは任意
のプロセシング・エレメント間でメッセージの転送を実
現できれば良く、その内部構成については問わない。
【0010】続いてこの並列計算機の動作例を説明す
る。ここではPEの数が4の場合について示す。しきい
値が小さくなり処理の分配が実行され、しきい値が初期
値に変更されて処理の分配が抑止される例を示す。まず
図3(a)では最初にすべてのPEが4つの処理を有し
ている(負荷量=4)とする。この時、しきい値THは
初期値に設定されており、ここでは16であったとす
る。次に図3(b)では図3(a)の状態から時間が経
過しPE1以外は次々と処理が無くなったとする。ま
た、PE1で実行の結果、処理が増えて8つの処理が残
っている(負荷量=8)とする。この時、PE2、PE
3、PE4からネットワークを経由して次々と処理分配
要求メッセージが、PE1に送られる。すると図1のあ
らかじめ設定されている時間TTが適切な値であれば、
処理分配要求メッセージの到着時間間隔はTTより小さ
くなり、これによってPE1では、図1のステップ10
が実行され、しきい値THが16から8へ、さらに、8
から4へと変更されPE1の有する負荷量である8より
小さくなる。この時点で図1のステップ13の処理の分
配が実行され図4(a)のようにPE2、PE3、PE
4に処理が分配される。ここで分配した処理の実行時間
が長い場合や、新たな処理を生成するような処理である
場合、PE2、PE3、PE4から処理分配要求メッセ
ージがPE1に送られなくなるため、図4(b)のよう
にPE1のしきい値THが図1のステップ11によって
16に変更されその後、処理の分配が抑止される。以上
の処理の制御によって各PEの稼働率を向上させつつ無
駄な処理の分配を抑止することができる。
【0011】
【発明の効果】本発明によれば、プロセシング・エレメ
ントの稼働率を向上しつつオーバヘッドを削減でき、こ
れらにより並列計算機の性能を向上できる。
【図面の簡単な説明】
【図1】本発明の一実施例の負荷分散方式を実現したフ
ローチャート。
【図2】本発明を実施する並列計算機の構成を示す図。
【図3】本発明を実施した並列計算機の動作例の一部を
示す図。
【図4】本発明を実施した並列計算機の動作例の他の部
分を示す図。
【符号の説明】
PE1,PE2,PE3,PE4,PEn…プロセシン
グ・エレメント、NET…ネットワーク。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 朝家 真知子 東京都国分寺市東恋ケ窪1丁目280番地 株式会社日立製作所中央研究所内

Claims (2)

    【特許請求の範囲】
  1. 【請求項1】ネットワークにより相互に接続された、複
    数のプロセシング・エレメントを並列に動作させて、各
    プロセシング・エレメントによりそれぞれ処理を実行さ
    せ、実行すべき処理の量がある定められたしきい値以下
    になったプロセシング・エレメントから該ネットワーク
    を介して他のプロセシング・エレメントに処理の分配を
    要求し、該他のプロセシング・エレメントは実行すべき
    処理の量がある定められたしきい値を超えている場合、
    該処理の分配の要求元のプロセシング・エレメントに処
    理を分配する並列計算機において、いずれかのプロセシ
    ング・エレメントに対して一つの処理の分配要求が他の
    プロセシング・エレメントからなされた後、ある定めら
    れた時間以内に新たな処理の分配要求があった場合、そ
    のプロセシング・エレメントにおける該しきい値を小さ
    くし、その時間以内に新たな処理の分配要求がなかった
    場合、該しきい値をある定められた値に変更することを
    特徴とする並列計算機における負荷分散方法。
  2. 【請求項2】該しきい値を小さくする処理は、現在のし
    きい値が1より大きい場合のみ現在のしきい値の二分の
    一(小数点以下切捨て)の値に変更する処理からなるこ
    とを特徴とする請求項1記載の並列計算機における負荷
    分散方法。
JP5209954A 1993-08-03 1993-08-03 並列計算機における負荷分散方法 Expired - Lifetime JP2526399B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP5209954A JP2526399B2 (ja) 1993-08-03 1993-08-03 並列計算機における負荷分散方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP5209954A JP2526399B2 (ja) 1993-08-03 1993-08-03 並列計算機における負荷分散方法

Publications (2)

Publication Number Publication Date
JPH0744505A true JPH0744505A (ja) 1995-02-14
JP2526399B2 JP2526399B2 (ja) 1996-08-21

Family

ID=16581422

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5209954A Expired - Lifetime JP2526399B2 (ja) 1993-08-03 1993-08-03 並列計算機における負荷分散方法

Country Status (1)

Country Link
JP (1) JP2526399B2 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998048331A1 (en) * 1997-04-23 1998-10-29 Hitachi, Ltd. Device and method for calculating required quantity of material
JP2002519758A (ja) * 1998-06-23 2002-07-02 マイクロソフト コーポレイション コンピュータ・システムにおいて一連の動作の1動作ごとの平均コストを制限するヒステリシスシステムおよび方法
WO2010100859A1 (ja) * 2009-03-03 2010-09-10 株式会社日立製作所 分散システム
JP2015032290A (ja) * 2013-08-07 2015-02-16 富士ゼロックス株式会社 マルチコアプロセッサ、画像形成装置およびプログラム

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998048331A1 (en) * 1997-04-23 1998-10-29 Hitachi, Ltd. Device and method for calculating required quantity of material
US6535773B1 (en) * 1997-04-23 2003-03-18 Hitachi, Ltd. Device and method for calculating required quantity of material
JP2002519758A (ja) * 1998-06-23 2002-07-02 マイクロソフト コーポレイション コンピュータ・システムにおいて一連の動作の1動作ごとの平均コストを制限するヒステリシスシステムおよび方法
WO2010100859A1 (ja) * 2009-03-03 2010-09-10 株式会社日立製作所 分散システム
JP2010204876A (ja) * 2009-03-03 2010-09-16 Hitachi Ltd 分散システム
CN102317916A (zh) * 2009-03-03 2012-01-11 株式会社日立制作所 分散系统
JP2015032290A (ja) * 2013-08-07 2015-02-16 富士ゼロックス株式会社 マルチコアプロセッサ、画像形成装置およびプログラム

Also Published As

Publication number Publication date
JP2526399B2 (ja) 1996-08-21

Similar Documents

Publication Publication Date Title
US7712103B2 (en) Method and system for managing load balancing in data processing system
US20120297216A1 (en) Dynamically selecting active polling or timed waits
US8364874B1 (en) Prioritized polling for virtual network interfaces
JP2526399B2 (ja) 並列計算機における負荷分散方法
US7415559B1 (en) Data processing systems and method for processing work items in such systems
EP0969367A2 (en) System and method used in a computer system for distributing tasks between multiprocessing I/O subsystems
CN111314249B (zh) 一种5g数据转发平面的避免数据包丢失的方法和服务器
CN117909087B (zh) 一种数据处理方法、装置、中央处理器及电子设备
JP4089506B2 (ja) ファイル共有システム及びサーバー並びにプログラム
JPS63223860A (ja) 複数プロセツサ構成装置
JP2007172322A (ja) 分散処理型マルチプロセッサシステム、制御方法、マルチプロセッサ割り込み制御装置及びプログラム
JPH06348662A (ja) ネットワーク用サーバ
CN117149442B (zh) 一种基于分布式架构数据库的硬件加速方法及系统
JP3082297B2 (ja) タスク制御方式
JP2580517B2 (ja) 並列計算機における負荷分散方法
JP2002140201A (ja) データベース更新方法及びそれを用いたデータベース管理システム
JPH10240697A (ja) セッション使用率をもとにした負荷分散方式
JPH09259091A (ja) トランザクション処理のホスト負荷分散方式
JPH0973432A (ja) オンライントランザクション高速処理方式
JPH10283330A (ja) 並列計算機の負荷分散制御方法
KR101483603B1 (ko) 통신 시스템에서 효율이 개선된 자원 제어 방법 및 장치
JPH05241958A (ja) 仮想記憶制御方式
CN119865392A (zh) 一种PCIe Switch WRR仲裁的实现方法
JP3050131B2 (ja) アービトレーション方式
JPH01239665A (ja) マルチプロセッサの負荷分散方式

Legal Events

Date Code Title Description
EXPY Cancellation because of completion of term