JPH02183833A - マルチプロセッサ用コンパイル方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、技術計算などで重要な、異種類の互いに並列
実行可能な並列ループの計算をマルチプロセッサ上で効
率的に実行させるためのプロセッサ割付方式に関するも
のである。

〔従来の技術〕

多重並列ループをマルチプロセッサに割付けるアルゴリ
ズムは、インターナショナル　コンファレンス　オン　
パラレルプロセッシング　予稿集（１９８６年）第５１
９ページから第５２７ページ（Ｐｒｏｃｅｅｄｉｎｇｓ
　ｏｆ　ｔｈｅ　ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆ
ｅｒｅｎｃｅ　ｏｎ　Ｐａｒａｌｌｅｌ　Ｐｒｏｃｅｓ
ｓｉｎｇ。

ｐＰ、５Ｌ９−５２７．１９８６）において論じられて
いる。そこでは、使用可能プロセッサ台数がｎ台である
とした場合に、最内側の並列ループから始めて、順次外
側の並列ループに向って、そのレベルの並列ループ全体
に１からｎ台のプロセッサを割り当てた各々の場合の並
列処理時間を計算する。ｋ台（１≦に≦ｎ）による並列
処理時間としては、そのレベルの並列ルール自体にｊ台
、内側の並列ループに［ｋ／ｊ１台を割り当てた時得ら
れる処理時間のうち１≦ｊ≦ｋに関して最短なものを採
用する。最外側の並列ループに達したときのｋ　＝　ｎ
の場合の割り付けが求めるプロセッサ割付けであるとし
ている。この割り付は法では、重要な仮定として、各レ
ベルの並列ループ内の演算量はループ操り返しに関して
一定であるとみなしている。

〔発明が解決しようとする問題点〕

数値計算では多重並列ループで表現される並列構造をと
る場合もあるが、演算量の不均一な並列ループ同志がさ
らに並列処理できる構造をとっている場合も多い。上記
従来技術は後者のような並列構造を考慮しておらず、後
者をマルチプロセッサで実行する際のプロセッサ割付法
としては利用できないという問題があった。

本発明の目的は、このような異種類の並列実行可能な並
列ループ群に対しても、各並列ループの並列性と演算量
の異なる各並列ループ間の並列性の両方をいかにして並
列実行時間を極小化する、マルチプロセッサシステムに
おける汎用性の高いプロセッサ割付法にもとづいたオブ
ジェクトコードを生成することにある。

〔問題点を解決するための手段〕

互いに並列実行可能なｍ個の異なる並列ループをｎ台の
プロセッサで構成されるマルチプロセッサシステム上で
並列実行する場合において、上記目的は（１）各並列ル
ープ毎にプロセッサ台数を１台からｎ台まで変化させた
各々の場合に対する並列実行時間を求め、（２）各並列
ループ毎に並列実行時間最小値を与える最少プロセッサ
割付台数を求め、（３）ｍ個の並列ループに関する該最
少プロセッサ割付台数の総和がｎ台を越える場合に、い
ずれかの並列ループから割付プロセッサ台数を削減する
ことを繰り返し、総プロセッサ割付台数ｎ台のもとての
並列実行時間が極小となる割付を決定し、（４）その割
付に従って各プロセッサ用のオブジェクトコードを生成
することにより実現される。

〔作用〕

各並列ループ毎にプロセッサ台数を１台からｎ台まで変
化させた各々の場合に対する並列実行時間を求める処理
（１）と、各並列ループ毎に並列実行時間最小値を与え
る最少プロセッサ割付台数を求める処理（２）とは、プ
ロクラム全体にｎ台のプロセッサで与えられたきの並列
実行時間を極小化する処理（３）に対する前処理である
。処理（１）は、処理（３）が各並列ループに任、意台
数のプロセッサを割り付ける場合の並列実行時間評価を
直ちに得ることができるようにするものである。処理（
２）は、各並列ループの実行時間最少値を謔えない範囲
で必要プロセッサ台数を予め最小化するよう動作するの
で、処理（３）におけるｎ台での極少並列実行時間探索
を大幅に嵩速化することができる。処理（３）はｍ個の
各々の並列ループに関する最少プロセッサ割付台数の総
和がｎ台を越える場合に、いずれかに並列ループから割
付プロセッサ台数を削減することを繰り返し、最終的に
総プロセッサ台数ｎ台のもとての並列実行時間が極少と
なるプロセッサ割付を決定するように動作する。これ等
の処理が決定した割付情報は処理（４）のオブジェクト
生成に直接反映され、異種類の並列ループ群もマルチプ
ロセッサで効率的に並列処理することが可能となる。

〔実施例〕

以下、本発明の１実施例を図面を用いて説明する。第１
図は、マルチプロセッサシステムにおいて、異種類の並
列実行可能な並列ループ群に対するプロセッサ割付を行
なう場合の５本発明の１実施例の全体構成である６第２
図は異種類の並列実行可能な並列ループ群を含むプログ
ラムの具体例である。第３図は予め各並列ループに対し
てプロセッサ台数を変化させた場合の並列実行時間を演
算しておく部分の説明、第４図は各並列ループに対して
、最短計算時間を増加させない範囲でプロセッサ台数を
予め最少化しＣおくための処理の説明、第５図は各並列
ループを最短時間で実行できる最少プロセッサ台数の総
和が使用可能プロセッサ台数を越える場合に、いずれか
の並列ループからプロセッサ台数を削減することを繰り
返し、総和を使用可能台数に納めるための処理の説明で
ある。第６図は、第５図の中核部の詳細説明である。

第７図〜第１０図は、４台のマルチプロセッサシステム
において第２図のプログラム例に本実施例を適用した結
果の説明である。第７図は各並列ループに１〜４台のプ
ロセッサを割り付ける場合の計算時間評価結果である。

第８図は各並列ループ毎に最短計算時間を与える最少プ
ロセッサ台数を評価した結果である。第９図は各並列ル
ープ毎のプロセッサ台数の総和を４台までに削減する過
程を示したものである。第１０図は４台への割り付は結
果を実際の実行状況イメージで示したものである。

第１図において、入力となるものとして異種類の互いに
並列処理可能な並列ループ群を含むソースプログラム１
、およびプロセッサ構成６がある。

プロセッサ割付処理は、予め各並列ループに対してプロ
セッサ台数を変化させた場合の並列実行時間を算出して
おく処理２、各並列ループに対して、最短計算時間を越
えない範囲でプロセッサ台数を予め最少化しておくため
の処理３．並列ループを最短時間で実行できる最少プロ
セッサ台数の総和が使用可能プロセッサ台数を越える場
合に、いずれかの並列ループからプロセッサ台数を削減
することを繰り返し、総和を使用可能台数に納めるため
の処理４、とからなる。結果として、各並列ループに対
する割付プロセッサ台数５が得られる。

処理７は、以上の情報からマルチプロセッサ用オブジェ
クトコードを生成する。

第２図において、ソースプログラム１は３個の並列ルー
プｄｏａｌｌと３゛個の逐次演算部から成り、これら６
個の演算部分は互いに並列実行可能な構造ｐａｒａｌｌ
ｅｌ　ｃａｓｅを構成している。これらのうち、　ｃａ
ｓｅ（４）〜ｃａｓｅ（６）はループ回数１回の並列ル
ープとみなすことができる。

第３図において、プロセッサ台数を１台からｎ台まで変
化させた場合の並列ループ毎の並列実行時間の評価は計
算式２１によって得られる。各並列ループについてこの
評価をここで行なっておく。

第４図において、初期最少台数算出処理３１は、各並列
ループ毎の最短計算時間を越えない範囲で最少プロセッ
サ台数を算出する。次に、その最少プロセッサ台数のも
とての各並列ループの並列実行時間のうちの最大値を求
める最大ｃａｓｅ算出処理３２を実行する。それに引き
続き、この最大値を越えない範囲で、各並列ループ毎に
さらにプロセッサ台数を削減する最少台数更新処理３３
を実行する。以上により、並列ループ群全体を最短時間
で処理できる最少プロセッサ台数が各並列ループ毎に求
められる。

第５図において、これらの最少プロセッサ台数の総和が
使用可能台数より少なければそこで割り付けは終了する
。そうでなければ、最少プロセッサ台数が２台以上の並
列ループから１台を削減した場合のうち、最短時間を与
えるものを求める。

その時の実行時間をし２とする。次に、最少プロセッサ
台数が１台の並列ループからその１台を解放しその並列
ループを他の並列ループと融合して計算する場合のうち
最短計算時間を与えるものを専用プロセッサ解放処理４
１で求める。その時の計算時間をｔ４とする。もしｔｌ
がし２と等しいか又はより大きければｔ２を与えた並列
ループからプロセッサ台数を１台削減する。逆であれば
、最少台数が１台であった並列ループから１台を削減す
る場合を採用する。これを採用した場合は、プロセッサ
を解放した並列ループがどの並列ループと融合させたか
を記録する。以上の処理を、各並列ループに割り付けら
れるプロセッサ台数の総数が使用可能台数に達するまで
繰り返す。

第６図において、最少プロセッサ台数が１台であったい
ずれの並列ループから１台を削減するかの決定を行なう
専用プロセッサの解放処理４１の群細か示されている。

ここでは、仮想的なプロセッサを想定いして、計算時間
を最短にする並列ループ融合の組み合わせをクリチカル
パス法を応用して求めている。

第７図において、第２図のプログラムについての、各並
列ループ、すなわち各Ｃａ５ｅ毎にプロセッサ台数１〜
４台に対する並列実行時間算出結果２１１が示されてい
る、この計算は第２図に示した各ケースの演算量２９を
用いて行ったものである。第８図において、第７図に引
き続いて実施された、プロセッサ台数最少化結果３１１
が示されている。第９図において１割り付は台数の総数
８台の状態から使用可能なプロセッサ台数である４台ま
でに削減する様子を示す、割り付は台数削減過程４１１
が示されている。第１０図において。

第９図の最終結果である、総台数４台における並列実行
状況６００が実行時のイメージで示されている。第１０
図で決定された各プロセッサ毎の受持ち処理内容を表現
するオブジェク１−コードが７で生成される。

従来技術では、本実施例で示したような異種類の並列実
行可能な並列ループ群に対するプロセッサ割り付けはほ
とんど不可能であったが、本実施例によれば第１０図に
示すように、並列ループ毎の並列性と並列ループ間の並
列性の両方を効果的に利用できるプロセッサ割付が可能
になるという効果がある。

〔発明の効果〕

本発明によれば、現実のプログラムに出現する、多数の
異なる並列ループ群から成る並列構造に対し、各並列ル
ープの演算量とループ回数にもとづいて、使用可能プロ
セッサ台数のもとて並列実行時間が極少化するよう、各
並列ループにプロセッサ台数を分配できるので、一般の
マルチプロセッサシステムにおける実行効率の良い汎用
的なプロセッサ割付が可能になるという効果がある。

【図面の簡単な説明】

第１図は、本発明の１実施例の全体構成図である。第２
図は対象とする並列プログラムの具体例およびその中の
各ケースの、必要演算量を示す図である。第３図は並列
実行時間評価処理のフローチャート、第４図は最少プロ
セッサ台数評価処理のフローチャート、第５図はプロセ
ッサ台数削減処理のフローチャート、第６図は、専用プ
ロセッサの解放処理のフローチャートである。第７〜第
１０図は、第２図の並列プログラムに対し４台のマルチ
プロセッサシステムにおいて本実施例を適用した結果の
説明図である。 符号の説明 ２・・並列ループ実行時間算出処理、３・・・プロセッ
サ台数最少化処理、４・・・割り付は台数削減処理。 ３１・・？ＪＪ期最少台数算出処理、３２・・・最大ｃ
ａｓｅ算出処理、３３・・・最少台数更新処理、４１・
・・専用プロセッサの解放処理。 第２図

Claims (1)

【特許請求の範囲】
1. 原始プログラムにおける互いに並列実行可能なｍ個の異
   なる並列ループに対し、（１）各並列ループ毎にプロセ
   ッサ台数を１台から総台数ｎ台まで変化させた各々の場
   合に対する最少並列実行時間を求め、（２）各並列ルー
   プ毎に並列実行時間最少値を与える最少割付プロセッサ
   台数を求め、（３）ｍ個の並列ループの各々に関する該
   最少割付プロセッサ台数の総和がｎ台を越える時には、
   ２台以上割付けられている並列ループのいずれかから１
   台削減する場合と１台のみ割付けられている並列ループ
   のいずれかを他の並列ループが割付けられているプロセ
   ッサへ重複して割付ける様に変更する場合とのうち最少
   時間を与える割付を採用することを繰り返して最終的に
   総プロセッサ割付台数ｎ台のもとでの並列実行時間が極
   小となる割付を決定し、（４）該割付決定に従った各プ
   ロセッサ毎のオグジェクトコードを生成することを特徴
   とするマルチプロセッサ用コンパイル方式。