Nothing Special   »   [go: up one dir, main page]

JP3039953B2 - 並列化装置 - Google Patents

並列化装置

Info

Publication number
JP3039953B2
JP3039953B2 JP02107575A JP10757590A JP3039953B2 JP 3039953 B2 JP3039953 B2 JP 3039953B2 JP 02107575 A JP02107575 A JP 02107575A JP 10757590 A JP10757590 A JP 10757590A JP 3039953 B2 JP3039953 B2 JP 3039953B2
Authority
JP
Japan
Prior art keywords
task
tasks
processing time
level
synchronization
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.)
Expired - Fee Related
Application number
JP02107575A
Other languages
English (en)
Other versions
JPH0380337A (ja
Inventor
和弘 梅北
雅嗣 亀谷
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.)
Hitachi Ltd
Original Assignee
Hitachi Ltd
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 Hitachi Ltd filed Critical Hitachi Ltd
Publication of JPH0380337A publication Critical patent/JPH0380337A/ja
Application granted granted Critical
Publication of JP3039953B2 publication Critical patent/JP3039953B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00Arrangements for software engineering
    • G06F8/40Transformation of program code
    • G06F8/41Compilation
    • G06F8/45Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Landscapes

  • Engineering & Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Multi Processors (AREA)

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、複数のプロセツサを有し、プロセツサ間で
通信を行う通信機構とプロセツサ間で待合せをしながら
処理を進める同期機構とを有するマルチプロセツサシス
テムが並列処理可能なオブジエクトプログラムを実行す
べきプログラムから生成する並列化装置に関する。
〔従来の技術〕 従来、マルチプロセツサシステムで並処列理を行う場
合、プログラムをジヨブやスレツド等の大きな単位に分
割し、フラグチエツクやトークン制御等の方法により、
タスク間の先行関係をすべて満たすことを確認すること
を前提としたタスクのスケジユーリングを行つていた。
なお、この種の装置として関連するものには、例えば
特開昭63−184841号公報に記載されているものがある。
〔発明が解決しようとする課題〕
上記従来技術は、プログラムを大きな単位に分割し、
並列化スケジユールするため、プログラムが本来もつて
いる並列性をひき出すことができず、効果的な並列処理
ができないという問題点があつた。
さらに、フラグチエツクやトークン制御でタスクの先
行関係を管理するため、並列化スケジユールを作成する
のに非常に多くの時間を要していた。
本発明の目的は、複数のプロセッサを有し、そのプロ
セッサ間の同期処理を行なう同期処理装置とを備えたマ
ルチプロセッサシステムが、高効率な並列処理を行なう
ことができるオブジェクトプログラムを作成し、マルチ
プロセッサの同期処理によるオーバーヘッドを小さくす
るタスクスケジュール結果を得る並列化装置を提供する
ことである。
本発明の他の目的は、マルチプロセッサの同期処理に
よるオーバーヘッドを小さくした、マルチプロセッサ中
の各プロセッサが実行すべきオブジェクトプログラム
を、各プロセッサに割り付ける並列化装置を提供するこ
とである。
本発明のさらに他の目的は、マルチプロセッサの同期
処理によるオーバーヘッドを小さくした、マルチプロセ
ッサ中の各プロセッサが実行すべきオブジェクトプログ
ラムを、各プロセッサに割り付けた後、並列処理のスケ
ジュールを繰り返す並列化装置を提供することである。
〔課題を解決するための手段〕
上記目的を達成するために本発明は、複数のプロセッ
サと、プロセッサ間の同期処理を行なう同期処理装置と
を備えたマルチプロセッサシステムに接続して、当該マ
ルチプロセッサシステムで実行すべきソースプログラム
から前記複数のプロセッサで並列処理可能なオブジェク
トプログラムを作成する並列化装置において、前記ソー
スプログラムを複数のタスクに分割し、前記タスク間の
依存関係と前記各タスクでの処理時間とを算出するタス
ク分割手段と、前記タスク分割手段が算出した前記タス
ク間の依存関係と前記各タスクの処理時間との各情報に
基づき、前記タスクを各プロセッサに割り当てるタスク
スケジュールを行なうタスクスケジュール手段とを備
え、前記タスクスケジュール手段は、一度タスクスケジ
ュールを行なった後、このタスクスケジュール結果によ
る全タスク処理時間を伸ばさないように、前記同期処理
装置による同期処理回数を減らすようにタスクを結合す
るためのタスク結合情報を生成するものである。
また、上記目的を達成するために本発明は、上記並列
化装置において、タスクスケジュール手段が、生成され
たタスク結合情報をもとに、タスクを結合するものであ
る。
さらに、上記目的を達成するために本発明を適用した
並列化装置において、更に上記の構成に加え、タスクス
ケジュール手段は、前記結合したタスクのタスク間の依
存関係と各タスクの処理時間とに基づき、再度タスクス
ケジュールを行なうものである。
〔作用〕
本発明の並列化装置によれば、タスク分割手段は、実
行すべきプログラムをタスクに分割し、タスクがどのタ
スクからの結果データから影響を受けるか、またはタス
クが出力する結果データが、どのタスクの実行に影響を
与えるかをプログラム中のオペランドデータを調べるこ
とによって、タスクの依存関係と、タスクを構成するマ
シン命令の処理時間を加算することによりタスク処理時
間情報とを生成する。
タスクスケジュール手段は、タスク分割手段が出力し
たタスク処理時間、タスク間リレーション情報をもと
に、マルチプロセッサシステムにおいて並列に実行でき
るタスクをそれぞれ別のプロセッサで実行させるため、
先行関係に矛盾が起こらないように、各プロセッサで実
行すべきタスク群とその処理シーケンス情報を生成する
と共に、同期処理装置にによる待ち合わせ処理をどの時
点で行なうべきかという同期情報を生成する。
更にタスクスケジュール手段は、タスクスケジュール
した後、タスクを結合することによって、同期処理装置
による待ち合わせ処理回数を減らすことができ、マルチ
プロセッサでの並列処理実行時間を短縮できるタスクを
結合してそれを1つのタスクとするためのタスク結合情
報を生成する。生成されたタスク結合情報をもとに、タ
スクスケジュール手段がタスクを結合する。
また更にタスクスケジュール手段は、結合したタスク
のタスク間の依存関係と各タスクの処理時間の情報をも
とに、再度タスクスケジュールを行なうことで、並列処
理オーバーヘッドを含めた全体の処理時間をほぼ最小に
する。
〔実施例〕
この発明の実施例を、図面を参照しながら説明する。
〈第1実施例〉 第1図に本発明の第1実施例を示す。本実施例の並列
化装置10はプリコンパイル手段2,核システムルーチン3,
タスク分割手段4,タスクスケジユール手段5,並列化コン
パイル手段6から成つている。
また、本発明の並列化装置10によつて、並列処理可能
となつたオブジエクトコードおよびシーケンスを実行す
る並列処理装置(ターゲツトマシン)9は、複数のプロ
セツサを備えており、各プロセツサで実行される各タス
クの実行が終了したことをチエツクし、タスク間先行関
係に矛盾なく並列処理を進めるためのプロセツサ間同期
機構および、プロセツサ間でのデータ授受を確実に行う
ための通信機構を備えている。
前者(プロセツサ間同期機構)の例として、特開昭63
−45670号に示されるプロセツサ間同期装置を用いるこ
とができ、後者(通信機構)の例として高速・高効率で
任意のプロセツサからランダムアクセス可能な共有メモ
リを用いることができる。
このような共有メモリを実現するには、各プロセツサ
とこの共有メモリとを接続するバスを、例えば特開昭62
−154057号,特開昭63−47866号に示される高速かつ高
効率な信号制御回路を用いて制御すればよい。ターゲツ
トマシン9の一例を第28図に示す。本実施例では、この
ターゲツトマシン9においては、複数のプロセツサで共
通に用いるデータは共有メモリ上におき、特定の1プロ
セツサでのみ用いるデータは該プロセツサのローカルメ
モリまたはレジスタ上に配置することとする。
ソースプログラム1をターゲツトマシン9で並列処理
できるようにするため、本発明の並列化装置10は次のよ
うに動作する。
プリコンパイル手段2はソースプログラム1を核シス
テムルーチン3の規定する仮想マシンコードに変換し、
タスク分割手段4に送る。
仮想マシンコードとは、並列化するために必要な条件
を満たし、かつプロセツサの命令を一般的に表現したマ
シンコードである。並列化するために必要な条件を満た
すため、本例では関数形式で表されたデータが一対一で
変換された仮想マシンコードを用いる。プログラムを仮
想マシンコードに変換する方法として、例えば次のよう
な方法がある。ソースプログラムを記述しているステー
トメントと核システムルーチンとの対応を示すテーブル
(以下SNテーブルと称す)を用意し、プリコンパイル手
段2は、SNテーブルと核システムルーチンによつて、プ
ログラム1を仮想マシンコードに変換する。
SNテーブルは例えばプリコンパイル手段にもたせても
よい。核システムルーチンはそれぞれ、ある処理を行う
ための仮想マシンコードによつて構成されており、この
ような核システムルーチンの集合を核言語と呼ぶ。
このようにして、プリコンパイル手段2は、ソースプ
ログラム1を仮想マシンコードに変換し、タスク分割手
段4に送る。
タスク分割手段4は、プリコンパイル手段2から送ら
れてきた仮想マシンコード群をタスクと呼ぶ単位に分割
し、各タスクの処理時間,タスク間先行関係のデータを
生成する。タスク間先行関係は次のように定義される。
すなわち、あるタスクQにおいて、別のタスクPの実行
結果を用いる場合には、タスクQの実行開始前に、タス
クPは終了していなければならず、このような場合タス
クPとQの間には先行関係があると言う。また、タスク
PをタスクQのアセンデントタスク、タスクQをタスク
Pのデイセンデントタスクと呼ぶことにする。
この関係にある時、第5図に示すように先行関係を矢
印で示すこととし、このようなタスクの先行関係を示す
図をタスクリレーシヨングラフと呼ぶことにする。タス
ク分割手段4は、次の各場合に応じて、それぞれに示し
た方法によつて、第6図に示すようにタスク間先行関係
を示すテーブル(タスクリレーシヨンテーブル)を生成
することができる。
1)ソースプログラム1が関数形式で記述されている場
合、プリコンパイル手段2から出力される仮想マシンコ
ードは関数形式になつているから、各タスクTの実行に
必要なデータを出力するタスクAが該タスクTのアセン
デントタスクとなり、タスク間リレーシヨンテーブルを
生成できる。
2)ソースプログラム1が非関数形式で書かれている場
合 a)ソースプログラムレベルのプログラム書換えを行わ
ない場合 例えば、プリコンパイル手段2にソースプログラム1
中のステートメントとこれを関数形式にした時の対応テ
ーブルをもたせ、このテーブルとプリコンパイルした仮
想マシンコードをタスク分割手段4に送り、この両方に
よつて、各タスクTの実行に必要なデータを出力するタ
スクAが該タスクTのアセンデントタスクとなり、タス
ク間リレーシヨンテーブルを生成できる。
b)ソースプログラムレベルのプログラム書換えを行う
場合。
以下に示すような方法でタスクモジユールとして最小
単位とみなせるレベルでソースプログラムを関数形式化
し、(1)に帰着させる。
i)ソースプログラムがメモリ変数のみを用いている場
合(レジスタ変数を用いない場合) これは、ソースプログラムがレジスタ演算を用いずす
べてメモリ演算のみで構成されている場合である。ここ
で、メモリとして共有メモリを選べば、このメモリ上の
データは任意のプロセツサからアクセスすることができ
る。ソースプログラムを関数形式に変換する関数形式に
する一方法として、異なる変数,定数には同一名をつけ
ない方法があり、第2図にその例を示す。第2図におい
てa=b+cとは「b+cを実行し、その結果をaに代
入する」の意味である。
このような関数形式に変換するアルゴリズムとして、
例えば、次のような変換アルゴリズムを用いる方法があ
る。
即ち、等号の左辺に同一変数または定数名を示す文字
(列)がm回(m≧2)記述されていた場合、i(2≦
i≦m)回目の式の等号左辺を第1回目の変数または定
数名を示す文字列N1と異なる文字(列)Niに変更し、こ
の式の次の式から(i+1)回目に等号左辺に同一文字
列Niが現れる式まで(この式を含む)の式における等号
右辺の該同一文字列は文字列Niに書換える。
以上の操作を2≦i≦mの各iについて行えばよい。
これにより、ソースプログラムは関数表現となり(1)
に帰着する。
ii)ソースプログラムがレジスタ変数を用いている場合 次の(イ),(ロ)いずれかの方法をとる。
イ)レジスタ演算をすべてメモリ演算に変換する。
この時、(2)−(b)−(i)に帰着される。
ロ)メモリからロードして、メモリにストアする型をと
るようにし、これをタスクの最小単位とする。これを実
現するためには、この型を満足するようにソースプログ
ラムを区切るか、または単に区切つただけでは実現でき
ない場合はメモリからのロード,メモリへのストア命令
を追加,挿入する。これにより、(2)−(b)−
(i)に帰着される。
タスク分割手段4におけるタスク分割方法として、例
えば次の方法がある。
ソースプログラム1はプリコンパイル手段2によつ
て、仮想マシンコードに変換されている。タスク分割手
段4においては、この1仮想マシンコード単位にまで展
開された仮想マシンコード群を1仮想マシンコードを1
つのタスクとしてタスクに分割し、第3図に示すタスク
登録テーブル(タスクNo.と各タスクに含まれる仮想マ
シンコード、各タスク処理時間を示すテーブル)にタス
ク内容(即ち、そのタスクに含まれる仮想マシンコー
ド)を登録する。次に第4図に示す仮想マシンコード〜
実マシンコード対照テーブルにおいて、用いようとする
ターゲツトマシン上の実プロセツサの欄を参照すること
により、そのタスクを実行するのに要する処理時間をタ
スク処理時間として、タスク登録テーブルのタスク処理
時間として、タスク登録テーブルのタスク処理時間の欄
に登録する。仮想マシンコード〜実マシンコード対照テ
ーブルは、各仮想マシンコードに対応する実プロセツサ
のマシンコードおよびその処理時間を、各仮想マシンコ
ードごとに、各実プロセツサごとに示している。第3図
に示すタスク登録テーブルにおいては、実プロセツサが
プロセツサAであつた場合の例を示してある。
タスク分割手段4のタスクリレーシヨンテーブル生成
法は先述の通りであり、第7図に示すタスクリレーシヨ
ングラフを有するタスク群のタスクリレーシヨンテーブ
ルを第6図に示す。
第7図において、丸印11の内側の数字はタスク番号、
丸印11横の数字はタスク処理時間、丸印13はタスク間先
行関係を示している。ここで、タスクNo.0のタスクは、
処理実行の開始を示すタスクで、その処理時間は0であ
る。
第6図では各タスクに対するアセンデントタスクを示
すことにより、タスク間リレーシヨンを示したが、各タ
スクに対し、デイセンデントタスクを示すことによつ
て、タスクリレーシヨンテーブルを構成することもでき
るし、タスクリレーシヨンテーブル中にアセンデントタ
スク,デイセンデントタスクの両方を示していてもよ
い。
このように、タスク分割手段4は、プリコンパイル手
段2が出力した仮想マシンコード群をタスクに分割し、
各タスクの内容および各タスクの処理時間を示すテーブ
ル(タスク登録テーブル)および、タスク間リレーシヨ
ンを示すテーブル(タスクリレーシヨンテーブル)を生
成し、タスク処理時間およびタスク間リレーシヨン情報
をタスクスケジユール手段5に送る。
タスク分割の手段として、本実施例では1仮想マシン
コードを1タスクとしたが、プリコンパイル前の1ステ
ートメントまたは複数のステートメントを1タスクと
し、該ステートメントがプリコンパイルされた仮想マシ
ンコード(群)を1タスクとして、タスク登録テーブル
に登録してもよいし、複数のマシンコードを1タスクと
してもよい。
各タスクの処理時間,タスク間リレーシヨンも先に述
べた方法で、いずれも同様に生成できる。
タスクスケジユール手段5は、タスク間の先行関係を
満たしつつ与えられたタスク群を、ターゲツトマシン9
で並列処理した際に、全体の処理時間が、与えられたタ
スク条件,タスク処理時間条件,タスク間先行関係条件
の下で実現することができる最小処理時間(クリテイカ
ル・パスの処理時間)に近づくように、タスクを並列化
する。
このようなタスクスケジユール手段を実現するために
は、例えば次のアルゴリズムを用いればよい。
まず、与えられたタスクをマスクの先行関係が許す限
り、できるだけ早く(即ち、タスクの処理可能な条件が
出そろつたら直ちに)処理するようにタスクを初期配置
する。第7図に示すタスク間リレーシヨン,タスク処理
時間を有するタスクを、この初期配置した結果を第8図
に示す。第8図において、長方形200はタスクを意味
し、線201は同期処理を示す。同期処理とは、並列処理
において、各プロセツサが処理しているタスクが、とも
に並列処理を行うプロセツサ全てにおいて終了するまで
次の処理を待ち、上記、ともに並列処理を行うプロセツ
サ全てにおいてタスクの処理が終了したことを確認した
後に次の処理に進むための待ち合わせ処理のことであ
る。任意の同期から、次の同期までをレベルと呼び、先
に実行されるレベルを上位のレベル、後に実行されるレ
ベルを下位のレベルと呼ぶこととする。
本発明においては、第8図に示すように時間順にレベ
ル1,レベル2,レベル3,…レベルnとレベル番号を付ける
こととする。よつて、レベル1が最上位のレベル、レベ
ルnが最下位のレベルとなる。従つて、同一レベルに配
置されたタスクは並列に処理可能であり、レベルnで実
行されるタスクBのアセンデントタスクAが存在する場
合は、該アセンデントタスクAはnよりも上位のレベル
になければならない。
先述の初期配置を行うためには、例えば次のアルゴリ
ズムを用いればよい。
まず、iの初期値を1として、タスクリレーシヨンテ
ーブルにおいて、タスク0をアセンデントタスクにもつ
タスクを第9図に示すレベルフアイルのレベルi(=
1)に登録する。タスクをレベルに配置,登録する際は
第8,9図に示すように処理時間の大きいタスクから順に
左から配置,登録する。
次に、レベル1〜iに登録したタスク以外のタスクに
ついて、アセンデントタスクを調べ、該アセンデントタ
スクのすべてがレベル1〜iにあれば、該タスクをレベ
ル(i+1)に登録する。そして、i=i+1として、
上記アルゴリズムで次のレベルの登録に進み、レベルに
登録されないタスクがなくなつたら(即ち、全てのタス
クがレベル登録テーブルに登録されたら)終了する。
以上がタスク初期配置のアルゴリズムの一例である。
初期配置結果は、必ずしも総処理時間を最短にするもの
にはなつていないので、更に総処理時間の短縮を図る。
そのためには、例えば次のアルゴリズムを用いればよ
い。
タスクが初期配置されたレベルを第1レベル(最上
位)〜第nレベル(最下位)と定義し、任意のレベルi
に属するタスクのうち、最左方のタスク(即ち、該レベ
ルで最大のタスク)Ti1の処理時間をST1、該レベルに属
するタスクのうち、左から2番目のタスクTi2の処理時
間をST2とし、レベルiより下位のあるレベルjに属す
るタスクのうち最大のタスクTj1の処理時間をDT1と定義
する。
まず、i=n−1として、レベルiに属するタスクの
うち最左方向のタスクTi1がレベル(i+1)より下位
でレベルnまでのいずれかのレベルに、タスク間リレー
シヨン条件を満たしながら移動可能か否かを調べる。タ
スク間リレーシヨン条件上移動可能な場合、移動先のレ
ベルをjとして、各jに対し上記定義のST1,ST2,DT1に
よつて ST1>DT1のとき;E=DT1−ST2 ST1≦DT1のとき;E=ST1−ST2 で与えられるEを評価し、このうちE≧0となるものが
あつた時、タスクTi1はレベルiから移動可能とし、E
を最大にするレベルjへタスクTi1を移動する。移動不
可能な場合は、レベルiの最左端タスクがレベルjへ移
動不可能になつた場合の処理(後述)へ進む。Eを最大
にするレベルjが複数ある場合には、なるべく下位のレ
ベルへタスクTi1を移動し、この移動によつて新たにレ
ベルiで最左端となつたタスクについても同様の操作を
行う。レベルiの最左端のタスクについて、レベルiか
らレベルjへの移動が不可能になつた時、レベルiの残
りのタスクについて、タスク処理時間の大きいタスクか
ら順に、全体の処理時間を増加させない範囲で、タスク
間リレーシヨンが許す限りできるだけ下位のレベルに移
動する。この移動ができない場合は、そのタスクを移動
せずにそのレベルにおく。
こうして、レベルiに属するすべてのタスクについて
の判断が終了したならば、i=n−2として上記の操作
をくり返し、i=n−3,n−4,…1と順次操作を行う。
上記操作によつて、タスク間リレーシヨンを満たし、
かつ初期配置より全体の処理時間を短縮するか変化なし
という条件で、全タスクをできるだけ下位のレベルに移
動させることができる。これを下方スイープアルゴリズ
ムと呼ぶ。次に、上記アルゴリズムと同様のアルゴリズ
ムで、今度は、タスク間リレーシヨンを満たし、かつ第
1回目下方スイープアルゴリズムによるスケジユール結
果よりも全体の処理時間を短縮するか変化なしという条
件で、全タスクをできるだけ上位のレベルに移動する。
これを上方スイープアルゴリズムと呼ぶ。上方スイープ
は下方スイープに比べ、タスクを移動する方向が異なる
だけであるから、下方スイープアルゴリズムにおいて、
タスクの移動方向のみを上方に変え、あとは同様のアル
ゴリズムを用いることにより上方スイープアルゴリズム
を実現できる。この下方スイープアルゴリズム、上方ス
イープアルゴリズムを交互に実行することによつて、全
体の処理時間をクリテイカルパスの処理時間に近づけて
ゆき、上方スイープ,下方スイープいずれのアルゴリズ
ムによつても、それ以上、処理時間の短縮が行われなく
なつた時点で上方,下方スイープアルゴリズムの実行を
終了すれば、与えられたタスク条件,タスク間リレーシ
ヨン条件,タスク処理時間の条下の下で、全体の処理時
間をほぼ最小にできる準最適をタスクスケジユール結果
を得ることができる。このアルゴリズムを用いて、第8
図に示すタスクの初期配置から、タスクを移動し、スケ
ジユールした結果を第10図に示す。第8図に示す初期ス
ケジユール結果に比べ、第10図に示すスケジユール結果
では、全体の処理時間を短縮することができる。
以上のスケジユーリングでは、全てのプロセツサが同
時に同期する(一斉同期)条件でのスケジユーリングを
行つたので、これを一斉同期によるスケジユーリングと
呼ぶ。
一方、いくつかのプロセツサでチームを構成し、関連
するタスクは、このチームで処理し、チーム内のプロセ
ツサ間で同期をとり、必要に応じて、チーム間の同期を
とる同期方式をチーム同期と呼び、チーム同期を用いる
スケジユーリング方式を、チーム同期を用いたスケジユ
ーリングと呼ぶ。
第10図に示した一斉同期によるスケジユーリング結果
をもとに、チーム同期を用いたスケジユーリングを行つ
た結果を第11図に示す。第11図において、プロセツサ0,
1がチームA、プロセツサ2,3がチームBを構成し、時刻
t0〜t1においては、チームAがタスク2,5,1を担当し、
チームBがタスク3,4,6,7,8,9を担当し、同期はそれぞ
れチームAの中だけ(チーム同期14)、チームBの内だ
け(チーム同期15)で行う。このようにチーム同期を用
い全体の処理時間ができるだけクテイカルパスの処理時
間に近づくようにスケジユールを作成することを、チー
ム同期を用いたスケジユーリングと呼ぶ。第10図と第11
図を比較してわかるようにチーム同期を用いたスケジユ
ーリングでは、一斉同期を用いたスケジユーリングに比
べ全体の処理時間をさらに短くすることができる。チー
ム同期を用いたスケジユーリングを行うためにはタスク
の初期スケジユールを行つた後に、例えば、次のアルゴ
リズムを用いればよい。タスクの初期スケジユールを行
う方法として、例えば先述の一斉同期を用いたスケジユ
ーリングを用いることができる。タスクの初期スケジユ
ール結果が、レベル1〜nまで存在するとする。
このスケジユール結果において、クリテイカルパスが
各レベルiの最長時間のタスクを通つているか否かを、
上位レベルから下位レベルへ順にチエツクしてゆく。通
つている場合は、次のレベルのチエツクに進み、通つて
いない場合は、このレベルiとレベル(i+1)を仮に
結合し、このレベル内のタスクのうち先行関係を有する
タスクを集めてチームを構成し、各チームについて先に
述べた一斉同期を用いたスケジユーリングのアルゴリズ
ムを用いてスケジユールを行う。スケジユール後の各チ
ームの処理時間のうち最長のものをチーム構成前の処理
時間と比較し、処理時間が短縮されていれば、これをチ
ームとして登録し、早く登録したチームからプロセツサ
0,1,2,…の順に必要な数だけのプロセツサを割当てる。
処理時間が短縮されない場合、後述の処理Uにうつる。
処理時間が改善された場合は、レベルi,i+1,i+2の一
斉同期3レベルに含まれるタスクについて、先に登録し
たチームに関係なく、改めてタスク間先行関係で結びつ
いたタスクを集めてチームを構成し、上述の操作を行
う。処理時間が短縮されれば更に次のレベルを追加し、
あらたにチームを構成し、同様の検討を行う。処理時間
の短縮がなされなくなると、次に示す処理Uに移る[処
理U:構成したチームの上位のレベルを順次追加してゆ
き、上記と同様にチームを構成し、全体の処理時間の短
縮を図る。] この結果、全体の処理時間が短縮されなくなつたとこ
ろで、再び構成されたチームの下位レベルについて、ク
リティカルパルが該各レベルの最長処理タスクを通つて
いるか否かを判定し、その結果に従い、上述の操作を繰
り返す。
さて、チーム同期によるスケジユーリングの開始に先
立つて行われる初期スケジユールは、例えば、次の方法
によつてもよい。
すなわち、まず一斉同期を用いたスケジユーリングを
行い、一斉同期によるスケジユーリング結果が、レベル
1〜nまで存在するとする。この結果をもとに、まずi
の初期値を1とし、レベルiとレベル(i+1)を仮に
結合し、このレベル内のタスクのうち先行関係を有する
タスクを集めてチームを構成し、各チームについて先に
述へた一斉同期を用いたスケジユーリングのアルゴリズ
ムを用いてスケジユールする。各チームのスケジユール
後の処理時間をスケジユール前と比較し、処理時間が短
縮されていれば、これをチームとして登録し、早く登録
したチームからプロセツサ0,1,2,…の順に必要な数だけ
のプロセツサを割当てる。処理時間が改善されない場
合、i=i+1とし上述の操作をくり返す。処理時間が
改善された場合は、レベルi,i+1,i+2の一斉同期3レ
ベルに含まれるタスクについて、先に登録したチームに
関係なく、改めてタスク間先行関係で結びついたタスク
を集めてチームを構成し、上述の操作を行う。処理時間
が短縮されれば更に次のレベルを追加し、あらたにチー
ムを構成し、同様の検討を行う。処理時間の短縮がなさ
れなくなつた所で、その時点でのチームを最終的にチー
ムとして登録し、その次のレベルをjとした時、i=j
として上述のアルゴリズムをくり返してゆき、レベルn
までの検討が終了した時点で、初期スケジユーリングの
終了とする。
以上のような一斉同期またはチーム同期を用いたスケ
ジユーリングアルゴリズムを実行するタスクスケジユー
ル手段5によつて、タスク分割手段4から出力され、タ
スク条件,タスク処理時間条件,タスク間接続関係条件
の下で、全体の処理時間をほぼ最小にでき、クリテイカ
ルパスの処理時間に近づけることができる。このスケジ
ユーリングの結果、各レベルに含まれるタスクを示した
レベルフアイルと各プロセツサが処理すべきタスク、同
期の種類を処理すべき順に示すプロセツサフアイルと共
有変数名、そのアドレスを示す共有変数フアイルが生成
される。第10図に示したスケジユール結果に対応するレ
ベルフアイルを第22図に示し、プロセツサアイルを第19
図に示す。第19図においてS0は一斉同期命令を示す。チ
ーム同期命令等他の同期命令が入る場合も、第19図と同
様のプロセツサフアイルが構成される。
例えば、第11図に示すチーム同期を用いたスケジユー
リング結果に対応するプロセツサフアイルを第25図に示
す。第25図において、S0は一斉同期命令を、S1はプロセ
ツサ0とプロセツサ1からなるチームのチーム同期命令
を、S2はプロセツサ2とプロセツサ3から成るチームの
チーム同期命令を示す。
上記スケジユール後、タスクスケジユール手段5は、
できるだけ使用するプロセツサ台数が減るように、ある
レベルにおいてあるプロセツサに割当てられているタス
クを、タスクが割当てられていないプロセツサの存在す
る他のレベルに、タスク間先行関係が許す条件下で全体
の処理時間が長くならないよう移動し、タスクが割当て
られていないプロセツサが存在する上記レベルに割当て
てもよい。例えば第12図に示すように、プロセツサ4の
レベルn+1に割当てられているタスクTを、プロセツ
サ3のレベルnに移動すれば、全体の処理時間を増加さ
せずに、使用するプロセツサ数を減らすことができる。
また、使用するプロセツサ台数が減るように、あるプ
ロセツサに割当てられているタスクを、タスク間先行関
係が許し、かつ全体の処理時間が長くならない範囲で、
他のプロセツサに割当てられているプロセツサに結合し
てもよい。
例えば、第13図に示すように、プロセツサ4のレベル
n+1に割当てられているタスクTを、プロセツサ3の
レベルnに割当てられているタスクPに結合し、プロセ
ツサ5のレベルn+1に割当てられているタスクSをプ
ロセツサ3のレベルn+1に割当てられているタスクQ
に結合することができる。これは、タスク間の先行関係
が、タスクT,Sのこのような移動を許す場合にのみ成立
する。
このとき、使用するプロセツサ台数を5台から3台に
減らすことができる。このタスクスケジユール手段5に
よつて、上記マルチプロセツサシステムが高効率な並列
処理を行うためのタスクスケジユールを高速に生成する
ことができる。上述のタスクスケジユール手段5に、更
に以下に述べるタスク結合情報生成機能をもたせてもよ
い。
さて、上述のタスクスケジユール手段5によつて、第
14図に示すタスク(丸印;丸中の記号がタスク名),タ
スク処理時間(タスク横に表示した数字),タスク間先
行関係(タスク間を結ぶ矢印)を有するタスク群を上述
のタスクスケジユール手段5によつてスケジユールする
と第16図に示す結果が得られる。第16図において、TPTi
はレベルiに属するタスクの処理時間のうち、最大のタ
スク処理時間を示し、TCTiは、レベルiの並列処理を行
うために要する時間(例えば、同期オーバーヘツド,通
信オーバーヘツド等)を示す。今、第16図に示すスケジ
ユーリング結果を実行する場合、全体の処理時間T1は、
nをレベル数として で与えられる。従つて、全体の処理時間T1を、与えられ
たタスク条件,タスク処理時間条件,タスク間接続関係
条件で最小にするためには、 を最小にする必要があるが、 を最小化するアルゴリズムはすでに実行しているわけ
(スケジユーリングアルゴリズム)であるから、 を最小にする必要がある。このためには各TCTiを小さく
するか、またはレベル数を減らせばよい。ターゲツトマ
シン9では、同期処理はハードウエア化されており、TC
Tiは最小化されているので、レベル数nを減らす方法を
とることにより、 をできるだけ小さくする。ターゲツトマシン9において
はTCTiはほとんど同期オーバーヘツドであるから、 を減らすためには、同期回数nを減らせばよい。従つ
て、2つ以上のレベルにわたつて、該レベルに存在する
タスクのうち、結合しても を増加させないタスク結合することにより同期回数を減
らし、 を小さくし、全体の処理時間を短縮する。第16図に示す
スケジユーリング結果を例とすれば、レベル1とレベル
2を結合し、その中でタスク1a,タスク1bを結合しタス
ク1とし、タスク2aとタスク2bを結合しタスク2とす
る。次に、レベル3とレベル4とレベル5とを結合し、
その中でタスク4aとタスク4bとタスク4cとを結合してタ
スク4とし、タスク3aとタスク3bとを結合してタスク3
とする。その結果、新たに生成されたタスク1〜4は、
第17図に示すようにスケジユーリングできる。その結
果、第17図に示すスケジユーリング結果に従つて処理を
実行した場合、全体の処理時間T2は、第16図に示すT1
比べΔT分だけ短縮することができる効果がある。この
タスク結合は、タスク内容およびタスク処理時間を変化
させるのみならずタスク間リレーシヨン関係も変化させ
る。第17図に示したようなタスク結合を行つた場合、第
14図に示すタスク間リレーシヨンは第15図に示すタスク
間リレーシヨンを有することになる。タスクスケジユー
ル手段5は、このように、タスクを結合することによつ
て全体の処理時間を短縮することのできるタスクのタス
ク結合情報を生成する。ただし、タスクスケジユール手
段5はスケジユールのみを行い、タスク結合情報を生成
しなくてもよい。このようなタスク結合を適用すること
により、全体の処理時間を短縮することができるタスク
間関係条件,タスク処理時間条件の一例を第18図に示
す。第18図において、レベルiとレベル(i+1)を結
合しようとする場合、レベルiに属する任意のタスクAj
のレベル(i+1)におけるデイセンデントタスクBj
1つのみであり、かつ該デイセンデントタスクBjのレベ
ルiにおけるアセンデントタスクはタスクAjのみである
場合、このタスクAjとBjを結合しても、 を増加させることはなく、かつ、 を減らすことができるので、タスク結合可とする。この
決定を判断するアルゴリズムの一例を第20図に示フロー
チヤート形式で示す。第20図はスケジユール手段5によ
るタスクスケジユーリングが終了した状態をSTARTとし
ている。また、チーム同期もチーム内では一斉同期とみ
なせるため、このタスク結合アルゴリズムは、一斉同期
のみによるスケジユーリングにもチーム同期を用いたス
ケジユーリングにも用いることができる。また、第20図
において「タスクAjとタスクBjを結合」とあるのは、例
えば、第21図に示すタスクリンクフアイル(タスクの結
合情報を示すフアイル)を生成することである。第21図
は第16図に示すスケジユール結果に上記アルゴリズムを
適用することによつて生成されるタスクリンクフアイル
である。また、タスクスケジユール手段5によつて第16
図に対応するプロセツサフアイルが生成され、これを第
24図に示す。第24図中、S0は一斉同期命令を示す。タス
クスケジユール手段5は第21図に示すようなタスクリン
クフアイルを生成した時にはこれを参照することによ
り、第24図に示すプロセツサフアイルにおいて、リンク
されたタスクとタスクとの間にある同期命令を削除す
る。こうして得られたプロセツサフアイルを第23図に示
す。タスクスケジユール手段5がタスク結合情報を生成
しない時は、同期命令を削除しない。第23図において
は、S0は一斉同期命令を示す。第23図に示すプロセツサ
フアイルに従つてタスクを実行すると、第17図に示す結
果となり、タスク結合前に比べ全体の処理時間をΔTだ
け短縮することができる効果がある。
以上示したようにタスクスケジユール手段5は、タス
ク、タスク処理時間、タスク間リレーシヨンを入力とし
て、タスクスケジユーリング結果(レベルフアイル)、
各プロセツサが実行すべきタスクと同期処理情報(プロ
セツサフアイル)、共通変数テーブルを生成し、さら
に、タスク結合情報(タスクリンクフアイル)を生成し
てもよい。このうちプロセツサフアイルと共通変数テー
ブルが並列化コンパイル手段6に送られる。並列化コン
パイル手段6では、タスク登録テーブルを参照し、タス
ク同期命令を仮想マシンコードに変換し、さらに、仮想
マシンコード〜実マシンコード変換テーブルによつて、
仮想マシンコードを実マシンコードに変換する。
この結果、各プロセツサごとに実行すべき実マシンコ
ードが実行順に並んだフアイル(オブジエクトプログラ
ム)が生成され、ターゲツトマシン9に送られる。ター
ゲツトマシン9では、送られてきたオブジエクトプログ
ラムに従つて並列処理を行う。
本発明の並列化装置によれば、ソースプログラムを小
さな単位(タスク)に分解するためソースプログラムに
含まれる並列処理可能部の多くを並列化でき、ターゲツ
トマシン9でソースプログラムを並列処理した際に全体
の処理時間が、与えられたタスク条件,タスク処理時
間,タスク先行関係条件下で実現することができる最小
処理時間に近づくようタスクを並列化することができる
ため、並列処理効率の高い並列処理可能なオブジエクト
コードおよびシーケンスを得ることができる効果があ
る。さらに、レベルの概念を用いたスケジューリングア
ルゴリズムをタスクスケジュール手段5に用いているた
め、極めて高速にスケジユーリングを行うことができる
効果がある。
また、本発明の並列化装置によれば、プリコンパイル
手段2,タスク分割手段4,タスクスケジユール手段5は、
プロセツサの種類によらない仮想マシンコードを取り扱
つていて、実マシンコードに応じて変更する必要がある
のは、並列化コンパイル手段6のみである。従つて、本
発明の並列化装置10はターゲツトマシン9上のプロセツ
サの変化に容易に対応できるという効果がある。
〈第2実施例〉 第26図は本発明の第2実施例を示している。
第2実施例の並列化装置30はプリコンパイル手段23
と、該システムルーチン24と、タスク分割手段25と、タ
スクスケジユール手段26と、並列化コンパイル手段27と
から成つている。
また、本実施例の並列化装置30によつて並列化された
プログラムを実行するターゲツトマシン31は、第1実施
例のターゲツトマシン9と同様のものでよい。
本実施例の並列化装置30は問題(ソースプログラム)
22をプリコンパイル手段23によつてプリコンパイルし、
仮想マシンコードに変換する所まで、第1実施例と同様
である。タスク分割手段25は、プリコンパイル手段23か
ら送られてきた仮想マシンコード群を、1仮想マシンコ
ードを1タスクとして、タスクに分割し、第1実施例の
所で示した方法と同様の方法によつて、タスク登録テー
ブル,タスクリレーシヨンテーブルを生成し、タスク,
タスク処理時間およびタスク間リレーシヨン情報をタス
クスケジユール手段26に送る。タスクスケジユール手段
26では、タスク分割手段25から送られたタスク,タスク
処理時間,タスク間リレーシヨン情報をもとに、第1実
施例と同様にして、タスク間先行関係を満たしつつ、与
えられたタスク群を、複数のプロセツサを有するターゲ
ツトマシン31で並列処理した際に、全体の処理時間が、
与えられたタスク条件,タスク処理時間条件,タスク間
先行関係条件の下で実現可能な最小処理時間(クリテイ
カルパスの処理時間)に近づくように、タスクを並列化
する。
タスクスケジユール手段26は第1実施例と同様の方法
をとるから、出力されるテーブル,フアイルも第1実施
例と同様である。
すなわち、タスクスケジユール手段26はタスク結合情
報(タスクリンクフアイル)を出力する。
このタスク結合情報をタスク分割手段25に送り、タス
ク分割手段25において、このタスク結合情報をもとにタ
スクの再生成を行う。すなわち、タスクリンクフアイル
に結合を指示されたタスクは1つのタスクとする。タス
クT1〜Tnをこの順に結合し、タスクNTとするために、次
の操作(1),(2)を行う。
1)タスク登録テーブルにおいて、タスクNTのタスク内
容(仮想マシンコード)をOP1,OP2,…,OPn(但しOPiは
タスクTiの仮想マシンコード)として登録し、タスクNT
のタスク処理時間TPT(NT)をTPT (但し、TPT(Ti)はタスクTiのタスク処理時間)とし
て登録する。
2)タスク間リレーシヨンテーブルにおいて、 i)アセンデントタスクでタスク間リレーシヨンを示し
ている場合。
AT(T1),AT(T2),…,AT(Tn)のうち、T1,T2,…Tn
以外のタスクをタスクNTのアセンデントタスクとして、
タスクリレーシヨンテーブルに登録する。
(但し、AT(Ti)はタスクTiのアセンデントタスクを示
す) ii)デイセンデントタスクでタスク間リレーシヨンを示
している場合 DT(T1),DT(T2),…,DT(Tn)のうち、T1,T2,…DT
(Tn)以外のタスクをタスクNTのデイセントデントタス
クとしてタスクリレーシヨンテーブルに登録する。(但
し、DT(Ti)はタスクTiのデイセンデントタスクを示
す。) iii)アセンデントタスク,デイセンデントタスクの両
方でタスク間リレーシヨンを示している場合。
AT(T1),AT(T2),…,AT(Tn)のうち、T1,T2,…Tn
以外のタスクをタスクNTのアセンデントタスクとしてタ
スク間リレーシヨンテーブルに登録し、DT(T1),DT(T
2),…,DT(Tn)のうちT1,T2,…Tn以外のタスクをタス
クNTのデイセンデントタスクとしてタスク間リレーシヨ
ンテーブルに登録する。
以上のように、タスク登録テーブル,タスク間リレー
シヨンテーブルを変更することによつてタスクの再生成
を行い、この再生成されたタスクのタスク処理時間情
報,タスク間リレーシヨン情報がタスクスケジユール手
段26に送られ、先と同様のアルゴリズムで全体の処理時
間がクリテイカルパスの処理時間にできるだけ近づくよ
うスケジユールする。
このように、タスクスケジユールとタスク結合,再生
成をくり返す。そして、上記操作をくり返しても並列処
理オーバーヘツドを含めた全体の処理時間がそれ以上短
縮できなくなつた時、このくり返しを中止し、タスクス
ケジユール手段26で生成されたプロセツサフアイルおよ
び共通変数テーブルが並列化コンパイル手段27に送られ
る。並列化コンパイル手段27以降の動作は、実施例1と
同様である。
本実施例の並列化装置を用いることによる効果を以下
に述べる。
一般に、ソースプログラムを複数のタスクに分割し、
全体の処理時間が最小になるように並列処理スケジユー
ルする場合、並列処理に起因するオーバーヘツド(同期
オーバーヘツド等)がないと仮定した場合、ソースプロ
グラムをできるだけ小さなタスクに分割した方が、並列
処理できるタスクが増して、全体の処理時間短縮に有利
であるが、実際の並列処理システムでは並処処理オーバ
ーヘツドが存在するため、タスクを小さく分解しすぎる
と、同期処理,通信等の並列処理オーバーヘツド原因と
なる動作の回数が増し、並列処理オーバーヘツドを含め
た全体の処理時間はかえつて増大する。そこで、本発明
の並列化装置を用いれば、まずタスクを最小単位にまで
分解して並列化スケジユールするため、並列処理オーバ
ーヘツドがないとした場合の最適スケジユール結果が得
られ、その結果に比べて、並列処理オーバーヘツドがな
いとした場合の全体の処理時間が増さない範囲でタスク
の結合,再生を行つて1タスクの大きさ(処理時間)を
大きくして再び並列化スケジユールすることをくり返す
ため、並列処理オーバーヘツドを含めた全体の処理時間
を、ほぼ最小にすることができる効果がある。
また、本発明の並列化装置によれば、実マシンコード
に応じて変更する必要があるのは、並列化コンパイル手
段27のみである。
従つて、本発明の並列化装置30は、ターゲツトマシン
31上のプロセツサの変化に容易に対応できるという効果
がある。
〈第3実施例〉 本発明の第3実施例を第27図に示す。第3実施例の並
列化装置219は制御用言語コンパイラ202,核システムル
ーチン(核言語)206,タスクデイバイター207,タスクス
ケジユーラ208,並列化コンパイラ213から成つており、
演算用言語コンパイラA203,演算用言語コンパイラB204,
AI用言語コンパイラ205はそれぞれ必要に応じてあつて
もよい。また、シリアルコンパイラ212があつてもよ
い。並列化コンパイラ213としては、完全並列コンパイ
ラ214,ベクトル化コンパイラ215,機能分散コンパイラ21
6のうち、少なく1つを有していればよい。
また、本実施例の並列化装置219によつて並列化され
たプログラムを実行するターゲツトマシン217は、第1
実施例のターゲツトマシン9と同様のものでよい。ター
ゲツトマシン217はシステムモニタ218,ホストモニタ211
によつてモニタすることができる。タスクスケジユーラ
208はプロセス管理向言語であるスケジユーリング言語2
09とBASIC言語210を用いて記述されている。
制御用言語で書かれたソースプログラムは制御用言語
コンパイラ202によつて、演算用言語Aで書かれたソー
スプログラムは演算用言語コンパイラA203によつて、演
算用言語Bで書かれたソースプログラムは演算用用語コ
ンパイラB204によつて、AI用言語で書かれたソースプロ
グラムはAI用言語コンパイラ205によつて、それぞれ核
システムルーチン(核言語)206の規定する仮想マシン
コードに従つて、仮想マシンコードに変換される。タス
クスケジユーラ208からタスクデイバイダー207への経路
220がない場合、タスクデイバイダー207は第1実施例に
おけるタスク分割手段4と同様の動作をし、タスクスケ
ジユーラ208は第1実施例におけるタスクスケジユール
手段5と同様の動作をし、並列化コンパイラ213が、完
全並列コンパイラ214を有しており、かつこの機能が選
択された時は、並列化コンパイラ213は、第1実施例に
おける並列化コンパイル手段6と同様の動作をする。
以上のような操作をへてターゲツトマシン217にて高
効率な並処列理可能となつたオブジエクトコードおよび
シーケンスは並列化コンパイラ213からターゲツトマシ
ン217に送られ、並列処理が実行される。
並列化コンパイラ213がベクトル化コンパイラ215を有
しており、かつこの機能が選択された場合には、ターゲ
ツトマシン217でベクトル処理が可能なように、タスク
スケジユーラ208から並列化コンパイラ213に送られてき
たプロセツサフアイルおよび共通変数テーブルを並列化
コンパイラ213はベクトル化された実マシンコードおよ
びシーケンスに変換し、ターゲツトマシン217に送り、
ターゲツトマシン217は、これに基づきベクトル処理を
行う。
並列化コンパイラ213が機能分解コンパイラ216を有し
ており、かつ、この機能が選択された場合には、ターゲ
ツトマシン217で機能分散処理が可能なように並列化コ
ンパイラ213はタスクスケジユーラ208から送られてきた
プロセツサフアイルおよび共通変数テーブルを実マシン
コードおよびシーケンスに変換し、ターゲツトマシン21
7に送り、ターゲツトマシン217は、これに基づき機能分
散処理を行う。
ターゲツトマシンがシリアル処理を行う時には、シリ
アルコンパイラ212によつて、タスクスケジユーラ208か
らシリアル処理用に出力されたプロセツサフアイルか
ら、シリアル処理用実マシンコードおよびシーケンスを
生成し、ターゲツトマシン217に送る。
シリアル処理を行う場合、または機能分散処理を行う
場合は、タスクデイバイダー207から、タスクスケジユ
ーラ208を介さずに、シリアルコンパイラ212、並列化コ
ンパイラ213にタスク情報,タスク間リレーシヨン情報
を送つてもよい。
また、タスクスケジユーラ208からタスクデイバイダ
ー207への経路220が存在する場合は、第3実施例のタス
クデイバイダー207は、第2実施例のタスク分割手段25
と同様の動作を行い、第3実施例のタスクスケジユーラ
208は、第2実施例のタスクスケジユール手段26と同様
の動作を行う。その他の動作は、上述の第3実施例にお
ける経路220がない場合と同様である。
本実施例に示す並列化装置は第1,第2実施例に示した
効果に加え、次の効果がある。
即ち、制御用言語,演算用言語A・B,AI用言語等、複
数の言語に対応でき、ターゲツトマシンがシリアル処理
を行う時にも対応できる効果がある。その上、ターゲツ
トマシンでベクトル処理,機能分散処理を行う場合にも
対応できるという効果がある。
〈第4実施例〉 第28図は本発明の第4実施例を示している。本発明の
並列化装置70は情報処理装置111および記憶装置112を有
しており、インターフエイス71を介して、ターゲツトマ
シン73に接続されている。
第1〜第3実施例で述べたような本発明の並列化装置
のアルゴリズムを記述したプログラムは、本並列化装置
70中の記憶装置112中にありこのアルゴリズムが情報処
理装置111によつて実行されて、ターゲツトマシン73に
て並列処理可能となつたオブジエクトコードおよびシー
ケンスはインターフエイス71を介してターゲツトマシン
73の外部拡張チヤネル97を通じて、ターゲツトマシン73
に送られる。本例では、特開昭63−101957号に示される
並列処理装置をターゲツトマシン73としている。
外部拡張チヤネル97を用いれば、本並列化装置70か
ら、直接、共有メモリ106〜108にアクセスできるので、
本発明の並列化装置によつて生成されたオブジエクトコ
ードおよびシーケンス(オブジエクトプログラム)を共
有メモリ106〜108に送ることができ、これに従つてプロ
セツサ77〜82は並列処理機構87〜92の制御を受けなが
ら、並列処理を実行することができる効果がある。プロ
セツサ77〜82間の通信は、第1実施例で述べたように、
信号制御回路93〜96によつて、高速・高効率のランダム
アクセスが可能なバスによつて、各プロセツサ77〜82に
接続された共有メモリ106〜108を用いて行う。ターゲツ
トマシン73中のプロセツサ数が、第28図と異なる場合で
も本実施例と同様に動作し、同様の効果が得られる。ま
た、プロセツサ77〜82は、第29図に示すように、CPU25
0,CPUローカルメモリ251,バツフア252を有している。従
つて、各プロセツサが実行するオブジエクトコードおよ
びシーケンスの情報を共有メモリ106〜108ではなく、各
プロセツサの有するCPUローカルメモリ上に有していて
もよい。また、外部拡張チヤネル84〜86を用いても、本
発明の並列化装置70によつて生成された、オブジエクト
コードおよびシーケンスをターゲツトマシン73に送るこ
ともできる。
本発明の並列化装置70として例えばパーソナルコンピ
ユータやワークステーシヨン等を用いることができ、こ
れらをマルチユースで用いてもよい。またターゲツトマ
シン中の単数または複数のプロセツサを並列化装置70と
して用いてもよい。
本実施例に示す並列化装置は、第1〜第3実施例の効
果に加えて、ターゲツトマシン73が高効率の並列処理を
行うためのオブジエクトおよびシーケンスを得ることが
できるという効果がある。
〔発明の効果〕
本発明の並列化装置によれば、マルチプロセッサの同
期処理によるオーバーヘッドを小さくするタスクスケジ
ュール効果が得られる。
【図面の簡単な説明】
第1図は本発明の第1実施例を示す図、第2図は、関数
形式表現の一例を示す図、第3図は、タスク登録テーブ
ルの一例を示す図、第4図は、仮想マシンコード〜実マ
シンコード対照テーブルの一例を示す図、第5図は、タ
スク間先行関係を示す図、第6図は、タスクリレーシヨ
ンテーブルの一例を示す図、第7図,第14図,第15図
は、タスクリレーシヨングラフの一例を示す図、第8図
は、並列化スケジユールにおけるタスクの初期配置の一
例を示す図、第9図,第22図は、レベルフアイルの一例
を示す図、第10図,第16図,第17図は、一斉同期を用い
た並列化スケジユールの一例を示す図、第11図は、チー
ム同期を用いた並列化スケジユールの一例を示す図、第
12図,第13図は使用するプロセツサ数を減らすためのタ
スクの移動の一例を示す図、第18図はタスク結合条件の
一例を示す図、第19図,第23図,第24図,第25図は、プ
ロセツサフアイルの一例を示す図、第20図は、タスク結
合判定アルゴリズムの一例を示すフローチヤート、第21
図は、タスクリンクフアイルの一例を示す図、第26図は
本発明の第2実施例を示す図、第27図は本発明の第3実
施例を示す図、第28図は本発明の第4実施例を示す図、
第29図は、プロセツサ77〜82の簡単な説明図。 1……ソースプログラム、2……プリコンパイル手段、
3……核システムルーチン、4……タスク分割手段、5
……タスクスケジユール手段、6……並列化コンパイル
手段、9……ターゲツトマシン、10……並列化装置、11
……タスク番号、12……タスク処理時間、13……タスク
間先行関係、14……プロセツサ0,1間同期、15……プロ
セツサ2,3間同期、16……一斉同期、22……ソースプロ
グラム、23……プリコンパイル手段、24……核システム
ルーチン、25……タスク分割手段、26……タスクスケジ
ユール手段、27……パラレルコンパイル手段、30……並
列化装置、70……並列化装置、71……インターフエイ
ス、73……ターゲツトマシン、77〜82……プロセツサ、
84〜86……外部拡張チヤネル、87〜92……並列処理機
構、93〜96……信号制御回路、97……外部拡張チヤネ
ル、106〜108……共有メモリ、111……情報処理装置、1
12……記憶装置、200……タスク、201……同期処理、20
2……制御用言語コンパイラ、203……演算用言語コンパ
イラA、204……演算用言語コンパイラB、205……AI用
言語コンパイラ、206……核システムルーチン、207……
タスクデイバインダー、208……タスクスケジユーラ、2
09……スケジユーリング言語、210……BASIC言語、211
……ホストモニタ、212……シリアルコンパイラ、213…
…並列化コンパイラ、214……完全並列コンパイラ、215
……ベクトル化コンパイラ、216……機能分散コンパイ
ラ、217……ターゲツトマシン、218……システムモニ
タ、219……並列化装置、250……CPU、251……CPUロー
カルメモリ、252……バツフア。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭57−109085(JP,A) 特開 昭58−149570(JP,A) 特開 昭63−59631(JP,A) 情報処理学会論文誌,Vol.28,N o.10(1987年),pp.1060〜1070 システムと制御,Vol.28,No. 6(1984年),pp.399〜410 (58)調査した分野(Int.Cl.7,DB名) G06F 9/46,9/45 G06F 15/16,17/16 JICSTファイル(JOIS) CSDB(日本国特許庁)

Claims (1)

    (57)【特許請求の範囲】
  1. 【請求項1】複数のプロセッサと、該プロセッサ間の同
    期処理を行なう同期処理装置とを備えたマルチプロセッ
    サシステムに接続して、当該マルチプロセッサシステム
    で実行すべきソースプログラムから前記複数のプロセッ
    サで並列処理可能なオブジェクトプログラムを作成する
    並列化装置であって、前記ソースプログラムを複数のタ
    スクに分割し、前記タスク間の依存関係と前記各タスク
    での処理時間とを算出するタスク分割手段と、前記タス
    ク分割手段が算出した前記タスク間の依存関係と前記各
    タスクの処理時間との各情報に基づき、前記タスクを各
    プロセッサに割り当てるタスクスケジュールを行なうタ
    スクスケジュール手段とを備えた並列化装置において、 前記タスクスケジュール手段は、一度タスクスケジュー
    ルを行なった後、このタスクスケジュール結果による全
    タスク処理時間を伸ばさないように、且つ、前記同期処
    理装置による同期処理回数を減らすようにタスクの結合
    が可能なときには当該結合についてのタスク結合情報を
    生成し、この生成されたタスク結合情報をもとに結合さ
    れたタスクを含むタスク間の依存関係と各タスクの処理
    時間とに基づき、再度タスクスケジュールを行なうこと
    を特徴とする並列化装置。
JP02107575A 1989-04-28 1990-04-25 並列化装置 Expired - Fee Related JP3039953B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP10765489 1989-04-28
JP1-107654 1989-04-28

Publications (2)

Publication Number Publication Date
JPH0380337A JPH0380337A (ja) 1991-04-05
JP3039953B2 true JP3039953B2 (ja) 2000-05-08

Family

ID=14464663

Family Applications (1)

Application Number Title Priority Date Filing Date
JP02107575A Expired - Fee Related JP3039953B2 (ja) 1989-04-28 1990-04-25 並列化装置

Country Status (4)

Country Link
US (1) US5452461A (ja)
EP (1) EP0400328B1 (ja)
JP (1) JP3039953B2 (ja)
DE (1) DE69029956T2 (ja)

Families Citing this family (82)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2921190B2 (ja) * 1991-07-25 1999-07-19 日本電気株式会社 並列実行方式
GB9305263D0 (en) * 1993-03-15 1993-05-05 Univ Westminster Parrallel computation
EP0635784B1 (de) * 1993-07-23 1999-08-25 Siemens Aktiengesellschaft Multiprozessorsystem
US6948172B1 (en) 1993-09-21 2005-09-20 Microsoft Corporation Preemptive multi-tasking with cooperative groups of tasks
CA2131406C (en) * 1993-09-21 2002-11-12 David D'souza Preemptive multi-tasking with cooperative groups of tasks
JP3190773B2 (ja) * 1993-09-30 2001-07-23 日本電気株式会社 言語処理プログラムのコンパイル処理方法
US5752036A (en) * 1993-10-05 1998-05-12 Seiko Epson Corporation Apparatus for generating a program for parallel processing
JPH0887341A (ja) * 1994-09-16 1996-04-02 Fujitsu Ltd 自動縮退立ち上げ機能を有したコンピュータシステム
US6009454A (en) * 1994-09-30 1999-12-28 Allen-Bradley Company, Llc Multi-tasking operation system for industrial controller
JP3444671B2 (ja) * 1994-11-08 2003-09-08 富士通株式会社 並列コード変換処理方法とそのシステム
US6199093B1 (en) * 1995-07-21 2001-03-06 Nec Corporation Processor allocating method/apparatus in multiprocessor system, and medium for storing processor allocating program
US6487580B1 (en) * 1995-09-25 2002-11-26 International Business Machines Corporation Method and system for managing concurrently executable computer processes
US5774728A (en) * 1995-12-27 1998-06-30 International Business Machines Corporation Method and system for compiling sections of a computer program for multiple execution environments
JP3610681B2 (ja) * 1996-06-28 2005-01-19 株式会社日立製作所 生産計画方法及び生産計画システム
US6110220A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Concurrent hardware-software co-synthesis of hard real-time aperiodic and periodic specifications of embedded system architectures
US6117180A (en) * 1997-02-24 2000-09-12 Lucent Technologies Inc. Hardware-software co-synthesis of heterogeneous distributed embedded systems for low overhead fault tolerance
US6289488B1 (en) 1997-02-24 2001-09-11 Lucent Technologies Inc. Hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems
US6178542B1 (en) 1997-02-24 2001-01-23 Lucent Technologies Inc. Hardware-software co-synthesis of embedded system architectures using quality of architecture metrics
US6112023A (en) * 1997-02-24 2000-08-29 Lucent Technologies Inc. Scheduling-based hardware-software co-synthesis of heterogeneous distributed embedded systems
US6230303B1 (en) 1997-02-24 2001-05-08 Lucent Technologies Inc. Proximity-based cluster allocation for hardware-software co-synthesis of heterogeneous distributed embedded systems
JP3675623B2 (ja) * 1997-10-31 2005-07-27 株式会社東芝 プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体
US6075935A (en) * 1997-12-01 2000-06-13 Improv Systems, Inc. Method of generating application specific integrated circuits using a programmable hardware architecture
US6086628A (en) * 1998-02-17 2000-07-11 Lucent Technologies Inc. Power-related hardware-software co-synthesis of heterogeneous distributed embedded systems
US6097886A (en) * 1998-02-17 2000-08-01 Lucent Technologies Inc. Cluster-based hardware-software co-synthesis of heterogeneous distributed embedded systems
US6324639B1 (en) * 1998-03-30 2001-11-27 Matsushita Electric Industrial Co., Ltd. Instruction converting apparatus using parallel execution code
JPH11296381A (ja) * 1998-04-08 1999-10-29 Matsushita Electric Ind Co Ltd 仮想マシン及びコンパイラ
KR100442463B1 (ko) * 1998-07-03 2004-07-30 지멘스 악티엔게젤샤프트 전체 프로세스의 제어를 설계하기 위한 방법 및 장치
US6363472B1 (en) * 1998-09-03 2002-03-26 Telefonaktiebolaget L M Ericsson (Publ) Method and system for minimizing effect of replacing programming languages in telephony systems
US6415384B1 (en) 1998-10-30 2002-07-02 Lucent Technologies Inc. Hardware/software co-synthesis of dynamically reconfigurable embedded systems
US6550059B1 (en) * 1999-10-04 2003-04-15 Advanced Micro Devices, Inc. Method for generating optimized vector instructions from high level programming languages
US6539542B1 (en) * 1999-10-20 2003-03-25 Verizon Corporate Services Group Inc. System and method for automatically optimizing heterogenous multiprocessor software performance
US6708331B1 (en) * 2000-05-03 2004-03-16 Leon Schwartz Method for automatic parallelization of software
JP2002116917A (ja) * 2000-10-05 2002-04-19 Fujitsu Ltd オブジェクト指向型プログラミング言語によるソース・プログラムをコンパイルするコンパイラ
JP3810631B2 (ja) * 2000-11-28 2006-08-16 富士通株式会社 情報処理プログラムを記録した記録媒体
US6684395B2 (en) * 2000-12-28 2004-01-27 Intel Corporation Multiple image dynamic bind and load procedure for a multi-processor
US7069556B2 (en) * 2001-09-27 2006-06-27 Intel Corporation Method and apparatus for implementing a parallel construct comprised of a single task
KR100439245B1 (ko) * 2001-10-20 2004-07-05 신기황 콘크리트 구조물용 신축이음장치
US7159211B2 (en) * 2002-08-29 2007-01-02 Indian Institute Of Information Technology Method for executing a sequential program in parallel with automatic fault tolerance
US7103881B2 (en) * 2002-12-10 2006-09-05 Intel Corporation Virtual machine to provide compiled code to processing elements embodied on a processor device
US8146063B2 (en) * 2003-02-20 2012-03-27 Koninklijke Philips Electronics N.V. Translation of a series of computer instructions
WO2005008414A2 (en) * 2003-07-11 2005-01-27 Computer Associates Think, Inc. Method and apparatus for parallel action processing
US20050193378A1 (en) * 2004-03-01 2005-09-01 Breault Richard E. System and method for building an executable program with a low probability of failure on demand
FR2873830B1 (fr) * 2004-07-30 2008-02-22 Commissariat Energie Atomique Procede d'ordonnancement de traitement de taches et dispositif pour mettre en oeuvre le procede
US8230426B2 (en) * 2004-10-06 2012-07-24 Digipede Technologies, Llc Multicore distributed processing system using selection of available workunits based on the comparison of concurrency attributes with the parallel processing characteristics
US20060179436A1 (en) * 2005-02-07 2006-08-10 Sony Computer Entertainment Inc. Methods and apparatus for providing a task change application programming interface
US8271993B2 (en) * 2005-03-04 2012-09-18 Hewlett-Packard Development Company, L.P. Method and apparatus for facilitating pipeline throughput
CN1316359C (zh) * 2005-06-09 2007-05-16 上海交通大学 用户指导的程序半自动并行化方法
JP5119590B2 (ja) * 2005-11-10 2013-01-16 富士通セミコンダクター株式会社 マルチプロセッサを有するプロセッサ装置用のタスク分配プログラム及びタスク分配装置
US8284206B2 (en) 2006-03-14 2012-10-09 Transgaming, Inc. General purpose software parallel task engine
US20070256076A1 (en) * 2006-04-27 2007-11-01 Thompson James W System and method for separating multiple workloads processing in a single computer operating environment
US8769703B2 (en) * 2006-04-27 2014-07-01 Unisys Corporation System and method for providing a mechanism to virtualize a perpetual, unique system identity on a partitioned computer system
JP4908363B2 (ja) * 2007-09-25 2012-04-04 株式会社東芝 情報処理装置、並列処理最適化方法およびプログラム
JP5036523B2 (ja) * 2007-12-21 2012-09-26 三菱電機株式会社 プログラム並列化装置
US20090172353A1 (en) * 2007-12-28 2009-07-02 Optillel Solutions System and method for architecture-adaptable automatic parallelization of computing code
US8352711B2 (en) * 2008-01-22 2013-01-08 Microsoft Corporation Coordinating chores in a multiprocessing environment using a compiler generated exception table
US7516448B1 (en) * 2008-06-30 2009-04-07 International Business Machines Corporation Method for improving irreducible region commoning compile speed
CN102197376B (zh) 2008-10-24 2014-01-15 国际商业机器公司 源代码处理方法、系统及程序
JP5245727B2 (ja) * 2008-11-04 2013-07-24 富士通株式会社 設計支援プログラム、設計支援装置、および設計支援方法
US8949786B2 (en) * 2008-12-01 2015-02-03 Kpit Technologies Limited Method and system for parallelization of sequential computer program codes
JP4629768B2 (ja) 2008-12-03 2011-02-09 インターナショナル・ビジネス・マシーンズ・コーポレーション 並列化処理方法、システム、及びプログラム
US10002161B2 (en) * 2008-12-03 2018-06-19 Sap Se Multithreading and concurrency control for a rule-based transaction engine
US20100223213A1 (en) * 2009-02-27 2010-09-02 Optillel Solutions, Inc. System and method for parallelization of machine learning computing code
JP2010204979A (ja) * 2009-03-04 2010-09-16 Renesas Electronics Corp コンパイル方法及びコンパイラ
US9250973B2 (en) 2009-03-12 2016-02-02 Polycore Software, Inc. Apparatus and associated methodology of generating a multi-core communications topology
US20120005682A1 (en) * 2010-06-30 2012-01-05 International Business Machines Corporation Holistic task scheduling for distributed computing
EP2458501A1 (en) * 2010-11-30 2012-05-30 France Telecom Method of operating a communication device and related communication device
US9823991B2 (en) * 2010-12-06 2017-11-21 International Business Machines Corporation Concurrent workload simulation for application performance testing
WO2012093496A1 (ja) * 2011-01-07 2012-07-12 富士通株式会社 マルチタスクスケジューリング方法、およびマルチコアプロセッサシステム
RU2011117765A (ru) 2011-05-05 2012-11-10 ЭлЭсАй Корпорейшн (US) Устройство (варианты) и способ реализации двухпроходного планировщика задач линейной сложности
US9727377B2 (en) * 2011-07-14 2017-08-08 Siemens Aktiengesellschaft Reducing the scan cycle time of control applications through multi-core execution of user programs
JP5341957B2 (ja) 2011-07-20 2013-11-13 トヨタ自動車株式会社 内燃機関の制御装置
CN102929214A (zh) * 2011-08-11 2013-02-13 西门子公司 一种嵌入式多处理单元并行处理系统及其运行方法
DE102013224702A1 (de) * 2013-12-03 2015-06-03 Robert Bosch Gmbh Steuergerät für ein Kraftfahrzeug
JP6435939B2 (ja) * 2015-03-18 2018-12-12 富士通株式会社 データ分類プログラム、データ分類方法およびデータ分類装置
JP6427053B2 (ja) * 2015-03-31 2018-11-21 株式会社デンソー 並列化コンパイル方法、及び並列化コンパイラ
JP6500626B2 (ja) * 2015-06-16 2019-04-17 富士通株式会社 計算機、コンパイラプログラム、リンクプログラムおよびコンパイル方法
JP6464982B2 (ja) * 2015-10-07 2019-02-06 株式会社デンソー 並列化方法、並列化ツール、車載装置
JP6428557B2 (ja) * 2015-10-09 2018-11-28 株式会社デンソー 並列化方法、並列化ツール
JP6558310B2 (ja) * 2016-06-13 2019-08-14 株式会社デンソー 並列化方法、並列化ツール
EP3704572A1 (en) * 2017-11-03 2020-09-09 Coherent Logix, Inc. Programming flow for multi-processor system
CN109359939B (zh) * 2018-09-26 2024-11-08 中国平安人寿保险股份有限公司 业务数据校验方法、装置、计算机设备和存储介质
CN111427417B (zh) * 2020-03-19 2023-08-22 珠海豹趣科技有限公司 一种时间获取方法、装置及电子设备

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3702005A (en) * 1971-05-24 1972-10-31 United Data Services Execution time analyzer
JPS6184740A (ja) * 1984-10-03 1986-04-30 Hitachi Ltd 汎用オブジエクトコ−ド生成方式
US4636948A (en) * 1985-01-30 1987-01-13 International Business Machines Corporation Method for controlling execution of application programs written in high level program language
JPH0754501B2 (ja) * 1985-12-27 1995-06-07 株式会社日立製作所 アクセス要求信号処理回路
JPH0731661B2 (ja) * 1986-10-20 1995-04-10 株式会社日立製作所 プロセツサ
JPS6345670A (ja) * 1986-08-13 1988-02-26 Hitachi Ltd プロセツサ間同期装置
JPS6347866A (ja) * 1986-08-15 1988-02-29 Hitachi Ltd 信号制御回路
US4843540A (en) * 1986-09-02 1989-06-27 The Trustees Of Columbia University In The City Of New York Parallel processing method
DE3752059T2 (de) * 1986-10-29 1997-08-14 United Technologies Corp Ereignisgesteuertes Exekutivprogramm
JPH01108638A (ja) * 1987-10-21 1989-04-25 Hitachi Ltd 並列化コンパイル方式
JP2738692B2 (ja) * 1988-01-29 1998-04-08 株式会社日立製作所 並列化コンパイル方法
US5093916A (en) * 1988-05-20 1992-03-03 International Business Machines Corporation System for inserting constructs into compiled code, defining scoping of common blocks and dynamically binding common blocks to tasks

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
システムと制御,Vol.28,No.6(1984年),pp.399〜410
情報処理学会論文誌,Vol.28,No.10(1987年),pp.1060〜1070

Also Published As

Publication number Publication date
DE69029956T2 (de) 1997-09-18
EP0400328B1 (en) 1997-02-19
US5452461A (en) 1995-09-19
EP0400328A1 (en) 1990-12-05
DE69029956D1 (de) 1997-03-27
JPH0380337A (ja) 1991-04-05

Similar Documents

Publication Publication Date Title
JP3039953B2 (ja) 並列化装置
US5828886A (en) Compiling apparatus and method for promoting an optimization effect of a program
JP2011081539A (ja) 並列化処理方法、システム、及びプログラム
JP5036523B2 (ja) プログラム並列化装置
EP0540680A4 (en) System for high-level virtual computer with heterogeneous operating systems
Gaudiot Sructure Handling in Data-Flow Systems
Kent et al. Speeding up genetic programming: A parallel BSP implementation
Lin et al. A design framework for mapping vectorized synchronous dataflow graphs onto cpu-gpu platforms
Ciglarič et al. Automated opencl gpu kernel fusion for stan math
JP3284522B2 (ja) プログラム生成装置
Yanagawa et al. Software system of the Earth Simulator
JP3276479B2 (ja) コンパイル方式
CN118245039B (zh) 一种基于国产加速器的并行算法移植优化方法
Li et al. swTVM: Towards Optimized Tensor Code Generation for Deep Learning on Sunway Many-Core Processor
Kim et al. Automatic H. 264 encoder synthesis for the cell processor from a target independent specification
Luo et al. TSCompiler: efficient compilation framework for dynamic-shape models
JP2765861B2 (ja) 並列化コンパイル方法
JP3628782B2 (ja) 並列分散処理システム
Janjic et al. Using erlang skeletons to parallelise realistic medium-scale parallel programs
Makoui et al. ALI: A CSSL/multiprocessor software interface
JP3551352B2 (ja) ループ分割方法
JP3239963B2 (ja) マルチ・プロセッサ計算機システム
Henke et al. Automated Derivation of Efficient Implementations from SDL Specifications
Zaichenkov et al. The Cost and Benefits of Coordination Programming: Two Case Studies in Concurrent Collections and S-NET
Burgess et al. An Execution Harness for Transputer-Based Embedded Systems—

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees