JPH0341550A - 並列分散処理方法 - Google Patents
並列分散処理方法Info
- Publication number
- JPH0341550A JPH0341550A JP17782489A JP17782489A JPH0341550A JP H0341550 A JPH0341550 A JP H0341550A JP 17782489 A JP17782489 A JP 17782489A JP 17782489 A JP17782489 A JP 17782489A JP H0341550 A JPH0341550 A JP H0341550A
- Authority
- JP
- Japan
- Prior art keywords
- processor
- processors
- parallel
- processing method
- parallelism
- 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.)
- Pending
Links
Landscapes
- Multi Processors (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
この発明は、並列処理装置で実行させるプログラムを前
記並列処理装置を構成する複数のプロセフすに割り付け
る並列分散処理方法に関するものである。
記並列処理装置を構成する複数のプロセフすに割り付け
る並列分散処理方法に関するものである。
第4図は、巡回パイプライン機能を有するデータ駆動形
のプロセッサの構成を示すブロック図である。第5図は
、このデータ駆動形プロセッサで使用するパケットの構
成図であり、このパケットはタグ(データの識別子)、
第1データおよび第2データで構成され、該タグはスル
ーパケットフラグ、外部フラグ、世代番号あるいはカラ
一番号、行先ノード番号、命令およびL/Rフラグより
構成されている。 第4図において、10は外部よりデータおよびタグから
なるパケットを入力する入力部、11はデータフローグ
ラフを記憶し、前記入力部10から出力されたパケット
のタグの一部であるノード番号に従って命令を読み出し
、この読み出した命令を新たなタグとし、前記パケット
のデータとともに命令パケットを生成するプログラム記
憶部、12は前記プログラム記憶部11から出力された
命令パケットを人力し、該命令パケットが有するタグと
同一のタグを有する命令パケットを検出して演算パケッ
トとして出力するか、検出できない場合は前記プログラ
ム記憶部1工から入力された該命令パケットを記憶する
発火処理部、13は前記発火処理部12から出力された
演算パケットを入力し、該演算パケットのタグの一部で
指定される演算を実行し、結果パケットを出力する演算
処理部、14は前記演算処理部13から出力される結果
パケットを人力し、該結果パケットのタグの一部である
外部フラグの指示により外部へ出力するか、あるいは前
記入力部10へ出力する出力部である。 第6図は以上のように構成されるデータ駆動形プロセッ
サに実行させるための、従来の並列分散処理方法を示す
フローチャートであり、以下第7図で示されるデータフ
ローグラフを第8図に示すように各プロセッサに分割す
るアルゴリズムについて説明する。 分割するプログラム(第8図で示すデータフローグラフ
)は、各ランクan(n=t+z+・・・+n)にb個
のノードが並列に配置されているとすると、まず、第8
図の総ノード数を求め(ステップ5T1)、第(11式
より1つのプロセッサあたりの分割ノード数を決める(
ステップ5T2)。 総ノード数 ・・・・・・・・・(1) 使用するプロセッサ数 次にランクa1から順番に、ステップST2で求めた1
つのプロセッサあたりの分割ノード数ずつ各プロセッサ
に割り付ける。 データ駆動形プ9センサでは同一ランクのノードは並列
に実行される。従って、各ランク毎のノード数(各ラン
クの並列度と同義)を調べることにより、プロセッサに
かかる負荷変化の概要がわかる。この負荷変化の概要と
してランク数と各ランクのノード数(並列度)との関係
を示したグラフが第9図である。 上述した従来の並列分散処理方法は、各プロセッサに割
り付けるノード数を均等にしているので(第10図)、
各プロセッサのプログラム容量は均等になるが、この各
プロセッサにかかる負荷をそのプロセッサ内で並列に処
理されるノード数で測った場合、負荷が均等化されてい
るとはいえない。また、各世代でプログラムを実行させ
る場合(1度に入力する数個のパケットの組を世代と呼
び、その世代を連続的に入力する)、各プロセッサにか
かる負荷(並列に処理されるノード数)がこの各プロセ
ンサに割り付けられたノード数にほぼ等しいと仮定する
と、この負荷は均等に割り付けられているといえる。し
かし、ノードを等しくするためには、プログラムにおけ
る並列度が高い部分(第10図の場合、第4.第5プロ
セツサに割り付けられている部分)のノードを割り付け
られるプロセンサでのランク数が、他の部分よりも少な
くなり、そのため、並列度の高い部分でのプロセッサ間
転送が多くなる。また、並列度が高い部分のみ各ランク
毎のノードを分割する方法(第11図)もあるが、その
場合もプロセッサ間転送の増加は回避できない。
のプロセッサの構成を示すブロック図である。第5図は
、このデータ駆動形プロセッサで使用するパケットの構
成図であり、このパケットはタグ(データの識別子)、
第1データおよび第2データで構成され、該タグはスル
ーパケットフラグ、外部フラグ、世代番号あるいはカラ
一番号、行先ノード番号、命令およびL/Rフラグより
構成されている。 第4図において、10は外部よりデータおよびタグから
なるパケットを入力する入力部、11はデータフローグ
ラフを記憶し、前記入力部10から出力されたパケット
のタグの一部であるノード番号に従って命令を読み出し
、この読み出した命令を新たなタグとし、前記パケット
のデータとともに命令パケットを生成するプログラム記
憶部、12は前記プログラム記憶部11から出力された
命令パケットを人力し、該命令パケットが有するタグと
同一のタグを有する命令パケットを検出して演算パケッ
トとして出力するか、検出できない場合は前記プログラ
ム記憶部1工から入力された該命令パケットを記憶する
発火処理部、13は前記発火処理部12から出力された
演算パケットを入力し、該演算パケットのタグの一部で
指定される演算を実行し、結果パケットを出力する演算
処理部、14は前記演算処理部13から出力される結果
パケットを人力し、該結果パケットのタグの一部である
外部フラグの指示により外部へ出力するか、あるいは前
記入力部10へ出力する出力部である。 第6図は以上のように構成されるデータ駆動形プロセッ
サに実行させるための、従来の並列分散処理方法を示す
フローチャートであり、以下第7図で示されるデータフ
ローグラフを第8図に示すように各プロセッサに分割す
るアルゴリズムについて説明する。 分割するプログラム(第8図で示すデータフローグラフ
)は、各ランクan(n=t+z+・・・+n)にb個
のノードが並列に配置されているとすると、まず、第8
図の総ノード数を求め(ステップ5T1)、第(11式
より1つのプロセッサあたりの分割ノード数を決める(
ステップ5T2)。 総ノード数 ・・・・・・・・・(1) 使用するプロセッサ数 次にランクa1から順番に、ステップST2で求めた1
つのプロセッサあたりの分割ノード数ずつ各プロセッサ
に割り付ける。 データ駆動形プ9センサでは同一ランクのノードは並列
に実行される。従って、各ランク毎のノード数(各ラン
クの並列度と同義)を調べることにより、プロセッサに
かかる負荷変化の概要がわかる。この負荷変化の概要と
してランク数と各ランクのノード数(並列度)との関係
を示したグラフが第9図である。 上述した従来の並列分散処理方法は、各プロセッサに割
り付けるノード数を均等にしているので(第10図)、
各プロセッサのプログラム容量は均等になるが、この各
プロセッサにかかる負荷をそのプロセッサ内で並列に処
理されるノード数で測った場合、負荷が均等化されてい
るとはいえない。また、各世代でプログラムを実行させ
る場合(1度に入力する数個のパケットの組を世代と呼
び、その世代を連続的に入力する)、各プロセッサにか
かる負荷(並列に処理されるノード数)がこの各プロセ
ンサに割り付けられたノード数にほぼ等しいと仮定する
と、この負荷は均等に割り付けられているといえる。し
かし、ノードを等しくするためには、プログラムにおけ
る並列度が高い部分(第10図の場合、第4.第5プロ
セツサに割り付けられている部分)のノードを割り付け
られるプロセンサでのランク数が、他の部分よりも少な
くなり、そのため、並列度の高い部分でのプロセッサ間
転送が多くなる。また、並列度が高い部分のみ各ランク
毎のノードを分割する方法(第11図)もあるが、その
場合もプロセッサ間転送の増加は回避できない。
従来の並列分散処理方式は以上のように構成されている
ので、各プロセッサの負荷を分散して均等化すると、プ
ログラムにおける高並列度の部分ではプロセッサ間転送
が増加するなどの課題があった。 この発明は上記のような課題を解消するためになされた
もので、プロセンサ間転送を減少させるとともに、各プ
ロセッサにかかる負荷を均等化する並列分散処理方法を
得ることを目的とする。
ので、各プロセッサの負荷を分散して均等化すると、プ
ログラムにおける高並列度の部分ではプロセッサ間転送
が増加するなどの課題があった。 この発明は上記のような課題を解消するためになされた
もので、プロセンサ間転送を減少させるとともに、各プ
ロセッサにかかる負荷を均等化する並列分散処理方法を
得ることを目的とする。
この発明に係る並列分散処理方法は、並列処理装置で実
行するプログラムをランク数の均等な複数のプロセスに
分割し、前記並列処理装置を構成する複数のプロセッサ
の中から、各プロセンサの並列処理能力を考慮して各プ
ロセスの並列度に対応した台数だけ、各プロセス毎に割
り付け、各プロセス毎に決定されたプロセッサへ世代を
投入し、各世代毎に動作させることで、順次各プロセス
を実1行するようにしたものである。
行するプログラムをランク数の均等な複数のプロセスに
分割し、前記並列処理装置を構成する複数のプロセッサ
の中から、各プロセンサの並列処理能力を考慮して各プ
ロセスの並列度に対応した台数だけ、各プロセス毎に割
り付け、各プロセス毎に決定されたプロセッサへ世代を
投入し、各世代毎に動作させることで、順次各プロセス
を実1行するようにしたものである。
この発明における並列分散処理方法は、実行するプログ
ラムをランク数の均等なプロセスに分割したので、並列
度の高いプロセスを実行する場合でもプロセッサ間転送
の増加を防ぐとともに、並列度の高いプロセスは同一プ
ロセスを複数のプロセッサで実行するので、各プロセッ
サの負荷を均等化する。
ラムをランク数の均等なプロセスに分割したので、並列
度の高いプロセスを実行する場合でもプロセッサ間転送
の増加を防ぐとともに、並列度の高いプロセスは同一プ
ロセスを複数のプロセッサで実行するので、各プロセッ
サの負荷を均等化する。
以下、この発明の一実施例を第1図のフローチャートを
用いて説明するが、ここで分割するプログラムは第7図
に示したデータフローグラフを考え、実行するプロセッ
サとしては第4図に示した巡回パイプライン機能を有す
るデータ駆動形プロセッサとする。 まず、実行するプログラムをランク数が均等になるよう
に複数のプロセスに分割しくステップ5T4)、この分
割されたプロセス毎に平均並列度(各ランクの並列度は
そのランク中のノード数である)を求める(ステップ5
T5)。ここで1つのプロセスについて平均並列度とプ
ロセッサのパイプライン段数(プロセッサの機能分割数
で、この数が大きいほど並列処理能力が大きい)から各
プロセスに割り付けられるプロセッサ数mを求める(ス
テップ5T6)。 m=〔(平均並列度)/(パイプライン段数)〕・・・
(2) ここで、第(2)式の記号〔〕は(平均並列度)/(パ
イプライン段数)を越えない最大の整数を求める記号で
ある。さらにこのプロセスを実行するプロセッサを並列
処理装置を構成する複数のプロセッサの中からm個割り
付けると(ステップ5T7)、このm個のプロッサに順
次世代データを割り振るために(世代データを第2図の
ように順次割り振る)前のプロセスの出力(第3図(a
))を、第3図(b)に示すような条件で第1から第m
のこのプロセスに割り付けられたプロセッサのいずれか
へ分散的に出力するように書換える(ステップ5T8)
。以上のステップST6からの処理は各プロセスについ
て順次実行されるが、この実行したプロセスが当該プロ
グラムの最終プロセスであることが確認されると(ステ
ップ5T9)プロセッサへの割り付けは終了し、世代毎
に実行する。 連続多世代でプログラムを実行させたとき、各プロセス
にかかる負荷が、プロセス内のノード数に等しいと仮定
し、該プロセスの平均並列度がプロセッサのパイプライ
ン段数に等しい時(状態1)の負荷を1とすると、 (平均並列度)/(パイプライン段数)#m(:整数)
・・・(3) であるプロセスの負荷はmとなる(状態2)。 この発明によると状態2のプロセスは、m個のプロセッ
サに割り付けられることになり、各プロセッサの世代流
量は状c、1の1/mとなる。従って、プロセッサ1個
あたりの負荷はm x ’へ=1となり、平均並列度が
パイプライン段数に等しい場合と同じになる。また、こ
の時ランク数は他のプロセスと同じであり、実行世代毎
にプロセッサに順次投入するので、他のプロセッサと比
較して、特に該プロセスのプロセッサ間転送が増加する
ということはない。 なお、上記実施例では各プロセスに割り付けるプロセッ
サ数を決定する指標に、プロセッサのパイプライン段数
を使用したが、各プロセスの平均並列度のうち、最小値
を使用することにより、平均並列度の最小値で各プロセ
ンサの負荷を均等化できる。 また、上記実施例では動作プログラムを変化させて、ソ
フトウェアにより各プロセスを実行するプロセッサを割
り付けたが、ハードウェアの命令に世代別出力命令を付
加させる(命令数を増やす)ことにより、ハードウェア
で実現することも可能である。
用いて説明するが、ここで分割するプログラムは第7図
に示したデータフローグラフを考え、実行するプロセッ
サとしては第4図に示した巡回パイプライン機能を有す
るデータ駆動形プロセッサとする。 まず、実行するプログラムをランク数が均等になるよう
に複数のプロセスに分割しくステップ5T4)、この分
割されたプロセス毎に平均並列度(各ランクの並列度は
そのランク中のノード数である)を求める(ステップ5
T5)。ここで1つのプロセスについて平均並列度とプ
ロセッサのパイプライン段数(プロセッサの機能分割数
で、この数が大きいほど並列処理能力が大きい)から各
プロセスに割り付けられるプロセッサ数mを求める(ス
テップ5T6)。 m=〔(平均並列度)/(パイプライン段数)〕・・・
(2) ここで、第(2)式の記号〔〕は(平均並列度)/(パ
イプライン段数)を越えない最大の整数を求める記号で
ある。さらにこのプロセスを実行するプロセッサを並列
処理装置を構成する複数のプロセッサの中からm個割り
付けると(ステップ5T7)、このm個のプロッサに順
次世代データを割り振るために(世代データを第2図の
ように順次割り振る)前のプロセスの出力(第3図(a
))を、第3図(b)に示すような条件で第1から第m
のこのプロセスに割り付けられたプロセッサのいずれか
へ分散的に出力するように書換える(ステップ5T8)
。以上のステップST6からの処理は各プロセスについ
て順次実行されるが、この実行したプロセスが当該プロ
グラムの最終プロセスであることが確認されると(ステ
ップ5T9)プロセッサへの割り付けは終了し、世代毎
に実行する。 連続多世代でプログラムを実行させたとき、各プロセス
にかかる負荷が、プロセス内のノード数に等しいと仮定
し、該プロセスの平均並列度がプロセッサのパイプライ
ン段数に等しい時(状態1)の負荷を1とすると、 (平均並列度)/(パイプライン段数)#m(:整数)
・・・(3) であるプロセスの負荷はmとなる(状態2)。 この発明によると状態2のプロセスは、m個のプロセッ
サに割り付けられることになり、各プロセッサの世代流
量は状c、1の1/mとなる。従って、プロセッサ1個
あたりの負荷はm x ’へ=1となり、平均並列度が
パイプライン段数に等しい場合と同じになる。また、こ
の時ランク数は他のプロセスと同じであり、実行世代毎
にプロセッサに順次投入するので、他のプロセッサと比
較して、特に該プロセスのプロセッサ間転送が増加する
ということはない。 なお、上記実施例では各プロセスに割り付けるプロセッ
サ数を決定する指標に、プロセッサのパイプライン段数
を使用したが、各プロセスの平均並列度のうち、最小値
を使用することにより、平均並列度の最小値で各プロセ
ンサの負荷を均等化できる。 また、上記実施例では動作プログラムを変化させて、ソ
フトウェアにより各プロセスを実行するプロセッサを割
り付けたが、ハードウェアの命令に世代別出力命令を付
加させる(命令数を増やす)ことにより、ハードウェア
で実現することも可能である。
以上のように、この発明によればプログラムをランク数
の均等なプロセスに分割し、並列処理装置を構成する複
数のプロセッサの中から、各プロセスの並列度に対応し
た台数だけ実行するプロセッサをプロセス毎に割り付け
、この割り付けられたプロフサに世代データを投入して
動作させ、順次各プロセスを実行するようにしたので、
各プロセスにおけるプロセッサ間転送の回数のばらつき
を防ぎ、各プロセッサの負荷を均等化できる効果がある
。
の均等なプロセスに分割し、並列処理装置を構成する複
数のプロセッサの中から、各プロセスの並列度に対応し
た台数だけ実行するプロセッサをプロセス毎に割り付け
、この割り付けられたプロフサに世代データを投入して
動作させ、順次各プロセスを実行するようにしたので、
各プロセスにおけるプロセッサ間転送の回数のばらつき
を防ぎ、各プロセッサの負荷を均等化できる効果がある
。
第1図はこの発明の一実施例による並列分散処理方法の
動作を説明するフローチャート、第2図は各プロセスを
実行するプロセッサに投入する世代の振分は動作を示す
図、第3図は世代毎の出力プロセッサの決定動作を示す
図、第4図はこの発明および従来技術により分割された
プログラムを実行する巡回パイプライン機能を有するデ
ータ駆動形プロセッサを示すブロック図、第5図はこの
データ駆動形プロセッサに入力されるパケットを示す構
成図、第6図は従来の並列分散処理方法の動作を説明す
るフローチャート、第7図はもとのプログラムとしての
データフローグラフ図、第8図は従来の並列分散処理方
法による分割結果を示す図、第9図は第7図のデータフ
ローグラフのランク数とノード数の関係を示すグラフ図
、第10図は第9図のグラフに分割結果を示したグラフ
図、第11図は第10図と同様に第9図のグラフに分割
結果を示したグラフ図である。 図において、10は入力部、11はプログラム記憶部、
12は発火処理部、13は演算処理部、14は出力部で
ある。 なお、図中、同一符号は同一、又は相当部分を示す。 特許出 願 人 三菱電機株式会社 「 岑 ) さ ぐq の 第 9 図 うiり 第 0 図 第 ]] 図
動作を説明するフローチャート、第2図は各プロセスを
実行するプロセッサに投入する世代の振分は動作を示す
図、第3図は世代毎の出力プロセッサの決定動作を示す
図、第4図はこの発明および従来技術により分割された
プログラムを実行する巡回パイプライン機能を有するデ
ータ駆動形プロセッサを示すブロック図、第5図はこの
データ駆動形プロセッサに入力されるパケットを示す構
成図、第6図は従来の並列分散処理方法の動作を説明す
るフローチャート、第7図はもとのプログラムとしての
データフローグラフ図、第8図は従来の並列分散処理方
法による分割結果を示す図、第9図は第7図のデータフ
ローグラフのランク数とノード数の関係を示すグラフ図
、第10図は第9図のグラフに分割結果を示したグラフ
図、第11図は第10図と同様に第9図のグラフに分割
結果を示したグラフ図である。 図において、10は入力部、11はプログラム記憶部、
12は発火処理部、13は演算処理部、14は出力部で
ある。 なお、図中、同一符号は同一、又は相当部分を示す。 特許出 願 人 三菱電機株式会社 「 岑 ) さ ぐq の 第 9 図 うiり 第 0 図 第 ]] 図
Claims (1)
- 並列処理を実行する並列処理装置を構成し、多世代実行
が可能な複数のプロセッサに、前記並列処理装置で多世
代実行させるプログラムを割り付ける並列分散処理方法
において、前記並列処理装置で実行するプログラムをラ
ンク数の均等な複数のプロセスに分割し、前記各プロセ
ス毎にこのプロセスを実行するプロセッサを、プロセス
の並列度に対応した台数だけ前記複数のプロセッサの中
からそれぞれ割り付けし、前記プロセスを割り付けられ
たプロセッサに世代データを投入し、該投入された世代
毎に実行させることを特徴とする並列分散処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP17782489A JPH0341550A (ja) | 1989-07-10 | 1989-07-10 | 並列分散処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP17782489A JPH0341550A (ja) | 1989-07-10 | 1989-07-10 | 並列分散処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0341550A true JPH0341550A (ja) | 1991-02-22 |
Family
ID=16037745
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP17782489A Pending JPH0341550A (ja) | 1989-07-10 | 1989-07-10 | 並列分散処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0341550A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05225153A (ja) * | 1991-07-10 | 1993-09-03 | Internatl Business Mach Corp <Ibm> | 高レベル命令の並列処理装置及び並列処理方法 |
-
1989
- 1989-07-10 JP JP17782489A patent/JPH0341550A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05225153A (ja) * | 1991-07-10 | 1993-09-03 | Internatl Business Mach Corp <Ibm> | 高レベル命令の並列処理装置及び並列処理方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112445616B (zh) | 资源分配方法以及装置 | |
| US5794065A (en) | Data driven information processor | |
| US3668651A (en) | Working device code method of i/o control | |
| JPH1011289A (ja) | 並列処理プロセッサにおける命令数拡張方法および並列処理プロセッサ | |
| JPH01155451A (ja) | 仮想計算機システム | |
| US7529875B2 (en) | Assigning interrupts for input/output (I/O) devices among nodes of a non-uniform memory access (NUMA) system | |
| US4792894A (en) | Arithmetic computation modifier based upon data dependent operations for SIMD architectures | |
| JPS63303460A (ja) | 並列プロセッサ | |
| EP0077619B1 (en) | Data-packet driven digital computer | |
| CN112929400A (zh) | 一种分布式缓存库数据重均衡方法和系统 | |
| JPH0341550A (ja) | 並列分散処理方法 | |
| JPH0619711B2 (ja) | 優先ブランチ機構を備えたデータ処理システム | |
| Yan et al. | QTMS: A quadratic time complexity topology-aware process mapping method for large-scale parallel applications on shared HPC system | |
| US7167908B2 (en) | Facilitating operation of a multi-processor system via a resolved symbolic constant | |
| JP2021092904A (ja) | Cpuリソース管理装置 | |
| JP3338466B2 (ja) | 主記憶アクセス最適化処理装置 | |
| US5870603A (en) | Method and system for storing exponent codes in a multi-processor computer to produce putputs according to an execution schedule | |
| JPH04227589A (ja) | データフロープログラムの割付け装置および割付け方法 | |
| JPH0512337A (ja) | ハツシユ法を用いたデータ検索方式 | |
| Mizutani et al. | Evaluation of a compiler with user‐selectable execution strategies for parallel recursion | |
| JPH02224192A (ja) | プログラム分割方法 | |
| JPH08185384A (ja) | ロードモジュール割り当て方法および割り当て装置 | |
| JPH0350298B2 (ja) | ||
| JP2003131887A (ja) | 変数ロードおよび処理の一括化コンパイル方法 | |
| JPS61193250A (ja) | 周辺装置の利用方式 |