JPH06214801A - 自動並列化翻訳装置及び方法 - Google Patents
自動並列化翻訳装置及び方法Info
- Publication number
- JPH06214801A JPH06214801A JP626293A JP626293A JPH06214801A JP H06214801 A JPH06214801 A JP H06214801A JP 626293 A JP626293 A JP 626293A JP 626293 A JP626293 A JP 626293A JP H06214801 A JPH06214801 A JP H06214801A
- Authority
- JP
- Japan
- Prior art keywords
- loop
- parallel
- code
- loops
- parallelization
- 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.)
- Withdrawn
Links
Landscapes
- Multi Processors (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】
【目的】 逐次型言語で記述された原コードを入力し、
並列計算機により並列実行の可能な並列ＤＯループ及
び、並列実行の不可能な逐次ＤＯループを原コードから
抽出し、抽出された並列ＤＯループについて、ＤＯルー
プ内の各項を並列実行させるＤＯループ内並列化コード
を作成することにより原コードを並列計算機用の目的コ
ードに変換する自動並列化翻訳装置及び方法に関し、処
理の手数を削減することにより、処理を高速化し、処理
時間を削減し、並列計算機の処理効率を高めることがで
きるので、並列計算機の有効利用を図ることを目的とす
る。 【構成】 抽出された前記ＤＯループの間の依存関係の
検出を行い、前記ＤＯループ内並列化コード及び検出さ
れた前記ＤＯループ間の依存関係に基づいて、ＤＯルー
プ間での並列実行を可能とするＤＯループ間並列化コー
ドを作成するように構成する。
並列計算機により並列実行の可能な並列ＤＯループ及
び、並列実行の不可能な逐次ＤＯループを原コードから
抽出し、抽出された並列ＤＯループについて、ＤＯルー
プ内の各項を並列実行させるＤＯループ内並列化コード
を作成することにより原コードを並列計算機用の目的コ
ードに変換する自動並列化翻訳装置及び方法に関し、処
理の手数を削減することにより、処理を高速化し、処理
時間を削減し、並列計算機の処理効率を高めることがで
きるので、並列計算機の有効利用を図ることを目的とす
る。 【構成】 抽出された前記ＤＯループの間の依存関係の
検出を行い、前記ＤＯループ内並列化コード及び検出さ
れた前記ＤＯループ間の依存関係に基づいて、ＤＯルー
プ間での並列実行を可能とするＤＯループ間並列化コー
ドを作成するように構成する。
Description
【０００１】
【産業上の利用分野】本発明は、自動並列化翻訳装置
（コンパイラ）及び方法に係り、特に、逐次型言語で記
述された原コードを入力し、並列計算機により並列実行
の可能な並列ＤＯループ及び、並列実行の不可能な逐次
ＤＯループを原コード（プログラム）から抽出し、抽出
された並列ＤＯループについて、ＤＯループ内で各項
（ステップ、イテレーション）を並列実行するようにＤ
Ｏループ内並列化コードを作成することにより原コード
を並列計算機用の目的コード（プログラム）に変換する
自動並列化翻訳装置及び方法に関する。現在、高速な計
算機（スーパーコンピュータ）を実現する方式として、
並列計算機が注目を浴びている。並列計算機をプログラ
ミングする手法の１つとして、Ｆｏｒｔｒａｎ等の従来
から広く使われている逐次型言語で処理を記述し、それ
を自動並列化コンパイラを用いて、並列計算機用のコー
ドに変換する方法が重要である。理由としては、並列処
理を直接記述する事の困難さ、並列処理を記述する標準
的なプログラミング言語が未だ存在しない事、過去にＦ
ｏｒｔｒａｎ等で書かれた資産を活かす事が挙げられ
る。本発明は、この自動並列化翻訳装置及び方法（自動
並列化コンパイラ）において、ＤＯループを並列に実行
する為の技術に関する。
（コンパイラ）及び方法に係り、特に、逐次型言語で記
述された原コードを入力し、並列計算機により並列実行
の可能な並列ＤＯループ及び、並列実行の不可能な逐次
ＤＯループを原コード（プログラム）から抽出し、抽出
された並列ＤＯループについて、ＤＯループ内で各項
（ステップ、イテレーション）を並列実行するようにＤ
Ｏループ内並列化コードを作成することにより原コード
を並列計算機用の目的コード（プログラム）に変換する
自動並列化翻訳装置及び方法に関する。現在、高速な計
算機（スーパーコンピュータ）を実現する方式として、
並列計算機が注目を浴びている。並列計算機をプログラ
ミングする手法の１つとして、Ｆｏｒｔｒａｎ等の従来
から広く使われている逐次型言語で処理を記述し、それ
を自動並列化コンパイラを用いて、並列計算機用のコー
ドに変換する方法が重要である。理由としては、並列処
理を直接記述する事の困難さ、並列処理を記述する標準
的なプログラミング言語が未だ存在しない事、過去にＦ
ｏｒｔｒａｎ等で書かれた資産を活かす事が挙げられ
る。本発明は、この自動並列化翻訳装置及び方法（自動
並列化コンパイラ）において、ＤＯループを並列に実行
する為の技術に関する。
【０００２】
【従来の技術】従来、図１２に示すように、逐次型言語
で記述された原コードから、並列計算機により並列実行
の可能な並列ＤＯループ及び、並列実行の不可能な逐次
ＤＯループを抽出するＤＯループ抽出部１と、抽出され
た並列ＤＯループについて、ＤＯループ内の各項を並列
実行するようにＤＯループ内並列化コードを作成するＤ
Ｏループ内並列化コード作成部８とを有し、前記原コー
ドを並列計算機用の目的コードに変換する自動並列化翻
訳装置があった。科学技術計算系のプログラムは通常、
プログラム内のＤＯループに大半の処理時間が費やされ
ている事が知られている。従来の並列化では、前記ＤＯ
ループ抽出部１により、ＤＯループの中から各イテレー
ション（項、ステップ）を並列実行できるもの（並列Ｄ
Ｏループ）を抽出し、ＤＯループ並列化コード作成部８
により各項（イテレーション、ステップ）をプロセッサ
に割り付けて並列実行する目的コードを作成している。
で記述された原コードから、並列計算機により並列実行
の可能な並列ＤＯループ及び、並列実行の不可能な逐次
ＤＯループを抽出するＤＯループ抽出部１と、抽出され
た並列ＤＯループについて、ＤＯループ内の各項を並列
実行するようにＤＯループ内並列化コードを作成するＤ
Ｏループ内並列化コード作成部８とを有し、前記原コー
ドを並列計算機用の目的コードに変換する自動並列化翻
訳装置があった。科学技術計算系のプログラムは通常、
プログラム内のＤＯループに大半の処理時間が費やされ
ている事が知られている。従来の並列化では、前記ＤＯ
ループ抽出部１により、ＤＯループの中から各イテレー
ション（項、ステップ）を並列実行できるもの（並列Ｄ
Ｏループ）を抽出し、ＤＯループ並列化コード作成部８
により各項（イテレーション、ステップ）をプロセッサ
に割り付けて並列実行する目的コードを作成している。
【０００３】
【発明が解決しようとする課題】さて、以上説明したよ
うな従来例にあっては、並列ＤＯループの各ステップを
プロセッサにマッピングし、並列実行させる方式では、
逐次ＤＯループの部分の処理は常に逐次処理せざるをえ
ず、並列計算機の良さが活かされず時間がかかるという
問題点を有していた。また、最近では、１つのＤＯルー
プを１つのタスクと考え、タスクレベルでの並列化を行
う方法も提案されている。しかし、このタスクレベルの
処理では、せっかくそのＤＯループが並列ＤＯループで
あったとしても、その事が活かされず、より高い並列性
を引き出せないという問題点を有していた。そこで、本
発明は、両方の良さを引き出せる並列実行方式を実現す
るために、複数のＤＯループが全て逐次ＤＯループであ
り、かつタスクレベルでも、依存関係があり並列実行で
きない場合にも、何らかの並列化を行って、高速に処理
を行うことができるコードを得る自動並列化翻訳装置及
び方法を提供することを目的としてなされたものであ
る。
うな従来例にあっては、並列ＤＯループの各ステップを
プロセッサにマッピングし、並列実行させる方式では、
逐次ＤＯループの部分の処理は常に逐次処理せざるをえ
ず、並列計算機の良さが活かされず時間がかかるという
問題点を有していた。また、最近では、１つのＤＯルー
プを１つのタスクと考え、タスクレベルでの並列化を行
う方法も提案されている。しかし、このタスクレベルの
処理では、せっかくそのＤＯループが並列ＤＯループで
あったとしても、その事が活かされず、より高い並列性
を引き出せないという問題点を有していた。そこで、本
発明は、両方の良さを引き出せる並列実行方式を実現す
るために、複数のＤＯループが全て逐次ＤＯループであ
り、かつタスクレベルでも、依存関係があり並列実行で
きない場合にも、何らかの並列化を行って、高速に処理
を行うことができるコードを得る自動並列化翻訳装置及
び方法を提供することを目的としてなされたものであ
る。
【０００４】
【課題を解決するための手段】以上の技術的課題を解決
するため、第一の発明は、図１及び請求項１に示すよう
に、逐次型言語で記述された原コードから、並列計算機
により並列実行の可能な並列ＤＯループ及び、並列実行
の不可能な逐次ＤＯループを抽出するＤＯループ抽出部
１０と、抽出された並列ＤＯループについて、ＤＯルー
プ内の各項を並列実行させるＤＯループ内並列化コード
を作成するＤＯループ内並列化コード作成部８０とを有
し、前記原コードを並列計算機用の目的コードに変換す
る自動並列化翻訳装置において、抽出されたＤＯループ
の間の依存関係の検出を行うＤＯループ間依存関係検出
部２０と、前記ＤＯループ内並列化コード及び検出され
たＤＯループ間の依存関係に基づいて、動的にＤＯルー
プ間での並列実行を可能とするＤＯループ間動的並列化
コードを作成するＤＯループ間動的並列化コード作成部
３０とを有するものである。
するため、第一の発明は、図１及び請求項１に示すよう
に、逐次型言語で記述された原コードから、並列計算機
により並列実行の可能な並列ＤＯループ及び、並列実行
の不可能な逐次ＤＯループを抽出するＤＯループ抽出部
１０と、抽出された並列ＤＯループについて、ＤＯルー
プ内の各項を並列実行させるＤＯループ内並列化コード
を作成するＤＯループ内並列化コード作成部８０とを有
し、前記原コードを並列計算機用の目的コードに変換す
る自動並列化翻訳装置において、抽出されたＤＯループ
の間の依存関係の検出を行うＤＯループ間依存関係検出
部２０と、前記ＤＯループ内並列化コード及び検出され
たＤＯループ間の依存関係に基づいて、動的にＤＯルー
プ間での並列実行を可能とするＤＯループ間動的並列化
コードを作成するＤＯループ間動的並列化コード作成部
３０とを有するものである。
【０００５】第二の発明は、図２及び請求項２に示すよ
うに、逐次型言語で記述された原コードを入力し（Ｓ
１）、並列計算機により並列実行の可能な並列ＤＯルー
プ及び、並列実行の不可能な逐次ＤＯループを原コード
から抽出し、抽出された並列ＤＯループについて、ＤＯ
ループ内の各項を並列実行させるＤＯループ内並列化コ
ードを作成する（Ｓ２）ことにより原コードを並列計算
機用の目的コードに変換する自動並列化翻訳方法におい
て、抽出された前記ＤＯループの間の依存関係の検出を
行い（Ｓ３）、前記ＤＯループ内並列化コード及び検出
された前記ＤＯループ間の依存関係に基づいて、動的に
ＤＯループ間での並列実行を可能とするＤＯループ間動
的並列化コードを作成する（Ｓ４）ことである。
うに、逐次型言語で記述された原コードを入力し（Ｓ
１）、並列計算機により並列実行の可能な並列ＤＯルー
プ及び、並列実行の不可能な逐次ＤＯループを原コード
から抽出し、抽出された並列ＤＯループについて、ＤＯ
ループ内の各項を並列実行させるＤＯループ内並列化コ
ードを作成する（Ｓ２）ことにより原コードを並列計算
機用の目的コードに変換する自動並列化翻訳方法におい
て、抽出された前記ＤＯループの間の依存関係の検出を
行い（Ｓ３）、前記ＤＯループ内並列化コード及び検出
された前記ＤＯループ間の依存関係に基づいて、動的に
ＤＯループ間での並列実行を可能とするＤＯループ間動
的並列化コードを作成する（Ｓ４）ことである。
【０００６】第三の発明は、図３及び請求項３に示すよ
うに、逐次型言語で記述された原コードから、並列計算
機により並列実行の可能な並列ＤＯループ及び、並列実
行の不可能な逐次ＤＯループを抽出するＤＯループ抽出
部１０と，抽出された並列ＤＯループについて、ＤＯル
ープ内の各項を並列実行させるＤＯループ内並列化コー
ドを作成するＤＯループ内並列化コード作成部８０とを
有し、前記原コードを並列計算機用の目的コードに変換
する自動並列化翻訳装置において、抽出されたＤＯルー
プの間の依存関係の検出を行うＤＯループ間依存関係検
出部２０と、処理が割り付けられるプロセッサを予め指
定する指定情報を出力する指定情報出力部４０と、前記
ＤＯループ内並列化コード、検出されたＤＯループ間の
依存関係、及び前記指定情報に基づいて、静的にＤＯル
ープ間での並列実行を可能とするＤＯループ間静的並列
化コードを作成するＤＯループ間静的並列化コード作成
部３１とを有するものである。
うに、逐次型言語で記述された原コードから、並列計算
機により並列実行の可能な並列ＤＯループ及び、並列実
行の不可能な逐次ＤＯループを抽出するＤＯループ抽出
部１０と，抽出された並列ＤＯループについて、ＤＯル
ープ内の各項を並列実行させるＤＯループ内並列化コー
ドを作成するＤＯループ内並列化コード作成部８０とを
有し、前記原コードを並列計算機用の目的コードに変換
する自動並列化翻訳装置において、抽出されたＤＯルー
プの間の依存関係の検出を行うＤＯループ間依存関係検
出部２０と、処理が割り付けられるプロセッサを予め指
定する指定情報を出力する指定情報出力部４０と、前記
ＤＯループ内並列化コード、検出されたＤＯループ間の
依存関係、及び前記指定情報に基づいて、静的にＤＯル
ープ間での並列実行を可能とするＤＯループ間静的並列
化コードを作成するＤＯループ間静的並列化コード作成
部３１とを有するものである。
【０００７】第四の発明は、図４及び請求項４に示すよ
うに、逐次型言語で記述された原コードを入力し（Ｓ
１）、並列計算機により並列実行の可能な並列ＤＯルー
プ及び、並列処理の不可能な逐次ＤＯループを原コード
から抽出し、抽出された並列ＤＯループについて、ＤＯ
ループ内で並列実行させるＤＯループ内並列化コードを
作成する（Ｓ２）ことにより原コードを並列計算機用の
目的コードに変換する自動並列化翻訳方法において、抽
出された前記ＤＯループの間の依存関係の検出を行い
（Ｓ３）、前記ＤＯループ内並列化コード、検出された
ＤＯループ間の依存関係、及び処理が割り付けられるべ
きプロセッサを予め指定する指定情報に基づいて、静的
にＤＯループ間での並列実行を行わせるＤＯループ間静
的並列化コードを作成する（Ｓ１４）ことである。
うに、逐次型言語で記述された原コードを入力し（Ｓ
１）、並列計算機により並列実行の可能な並列ＤＯルー
プ及び、並列処理の不可能な逐次ＤＯループを原コード
から抽出し、抽出された並列ＤＯループについて、ＤＯ
ループ内で並列実行させるＤＯループ内並列化コードを
作成する（Ｓ２）ことにより原コードを並列計算機用の
目的コードに変換する自動並列化翻訳方法において、抽
出された前記ＤＯループの間の依存関係の検出を行い
（Ｓ３）、前記ＤＯループ内並列化コード、検出された
ＤＯループ間の依存関係、及び処理が割り付けられるべ
きプロセッサを予め指定する指定情報に基づいて、静的
にＤＯループ間での並列実行を行わせるＤＯループ間静
的並列化コードを作成する（Ｓ１４）ことである。
【０００８】
【作用】続いて、本発明の処理動作について説明する。
ステップＳ１で、自動並列化翻訳を行う対象となる逐次
型言語で記述された原コードを前記ＤＯループ抽出部１
０に入力する。ここで、「自動並列化翻訳」とは、逐次
型言語で記述された原コード（原プログラム）を並列計
算機用の目的コード（目的プログラム）に変換すること
をいう。また、「逐次型言語」とは例えば、ＦＯＲＴＲ
ＡＮ等の従来から広く使われている言語であって、予め
指定された命令の系列に従って、計算機を逐次自動的に
制御する言語をいう。ステップＳ２で、前記ＤＯループ
抽出部１０は並列ＤＯループと逐次ＤＯループを前記原
コードから抽出する。ここで、「並列ＤＯループ」と
は、並列計算機により各項（ステップ、イテレーショ
ン）が並列実行可能なＤＯループであり、「逐次ＤＯル
ープ」とは、並列計算機により各項が不規則的な依存関
係をもつこと等により、並列実行不可能なＤＯループを
いう。並列ＤＯループの抽出はＤＯループ内の各項間の
データ依存関係を調べることにより、各項が独立な場合
には、並列実行が可能であり、並列ＤＯループであるこ
とになる。例えば、各項（ｉ＝１，２，…，ｎ）が各々 Ａ（ｉ）とＡ（ｉ−１） のように表される場合である。また、並列実行可能でな
い場合とは、例えば、各項（ｉ＝１，２，…，ｎ）が各
々 Ａ（ｉ）とＡ（ｎ＋１−ｉ） のように表される場合である。並列ＤＯループが抽出さ
れた場合には、前記ＤＯループ内並列化コード作成部８
０は、並列ＤＯループ内の各項を並列実行するようにＤ
Ｏループ内並列化コードを作成する。
ステップＳ１で、自動並列化翻訳を行う対象となる逐次
型言語で記述された原コードを前記ＤＯループ抽出部１
０に入力する。ここで、「自動並列化翻訳」とは、逐次
型言語で記述された原コード（原プログラム）を並列計
算機用の目的コード（目的プログラム）に変換すること
をいう。また、「逐次型言語」とは例えば、ＦＯＲＴＲ
ＡＮ等の従来から広く使われている言語であって、予め
指定された命令の系列に従って、計算機を逐次自動的に
制御する言語をいう。ステップＳ２で、前記ＤＯループ
抽出部１０は並列ＤＯループと逐次ＤＯループを前記原
コードから抽出する。ここで、「並列ＤＯループ」と
は、並列計算機により各項（ステップ、イテレーショ
ン）が並列実行可能なＤＯループであり、「逐次ＤＯル
ープ」とは、並列計算機により各項が不規則的な依存関
係をもつこと等により、並列実行不可能なＤＯループを
いう。並列ＤＯループの抽出はＤＯループ内の各項間の
データ依存関係を調べることにより、各項が独立な場合
には、並列実行が可能であり、並列ＤＯループであるこ
とになる。例えば、各項（ｉ＝１，２，…，ｎ）が各々 Ａ（ｉ）とＡ（ｉ−１） のように表される場合である。また、並列実行可能でな
い場合とは、例えば、各項（ｉ＝１，２，…，ｎ）が各
々 Ａ（ｉ）とＡ（ｎ＋１−ｉ） のように表される場合である。並列ＤＯループが抽出さ
れた場合には、前記ＤＯループ内並列化コード作成部８
０は、並列ＤＯループ内の各項を並列実行するようにＤ
Ｏループ内並列化コードを作成する。
【０００９】ステップＳ３で、前記ＤＯループ間依存関
係検出部２０は抽出されたＤＯループの間の依存関係の
検出を行う。一般的に、ＤＯループ間で依存関係がない
場合には、当該ＤＯループ間では処理を独立に行うこと
ができて、並列実行が可能ということになる。ステップ
Ｓ４で、前記ＤＯループ間動的並列化コード作成部３０
は前記ＤＯループ間依存関係検出部２０により検出され
た依存関係、及びＤＯループ内並列化コード作成部８０
により作成されたＤＯループ内並列化コードに基づい
て、動的にＤＯループ間での並列実行を可能とするＤＯ
ループ間動的並列化コードを作成する。ここで、「動
的」とは「動的スケジューリング」を意味し、コンパイ
ル時には、並列計算機のプロセッサ台数に依存しないプ
ログラム（コード）を生成する。実行時に処理を空いて
いるプロセッサに割り付ける（スケジューリング）ため
のコードを挿入する。長所は負荷分散が容易である。短
所は実行時にプロセッサ割り付けのオーバーヘッドが生
じる。一方、「静的」とは「静的スケジューリング」を
意味し、コンパイル時に、並列実行すべきプログラムを
プロセッサに割り付けてしまうやり方。長所は実行時に
プロセッサ割り付け（スケジューリング）のオーバーヘ
ッドがない。短所は負荷分散が難しい。例えば、請求項
５及び請求項６に示すように、各逐次ＤＯループと並列
ＤＯループとの間に依存関係がないことが検出された場
合には、実行時には逐次ＤＯループを優先的に並列計算
機のプロセッサに割り付け、残りのプロセッサで並列Ｄ
Ｏループを実行させるようにＤＯループ間並列化コード
又はＤＯループ間静的並列化コードを作成する。
係検出部２０は抽出されたＤＯループの間の依存関係の
検出を行う。一般的に、ＤＯループ間で依存関係がない
場合には、当該ＤＯループ間では処理を独立に行うこと
ができて、並列実行が可能ということになる。ステップ
Ｓ４で、前記ＤＯループ間動的並列化コード作成部３０
は前記ＤＯループ間依存関係検出部２０により検出され
た依存関係、及びＤＯループ内並列化コード作成部８０
により作成されたＤＯループ内並列化コードに基づい
て、動的にＤＯループ間での並列実行を可能とするＤＯ
ループ間動的並列化コードを作成する。ここで、「動
的」とは「動的スケジューリング」を意味し、コンパイ
ル時には、並列計算機のプロセッサ台数に依存しないプ
ログラム（コード）を生成する。実行時に処理を空いて
いるプロセッサに割り付ける（スケジューリング）ため
のコードを挿入する。長所は負荷分散が容易である。短
所は実行時にプロセッサ割り付けのオーバーヘッドが生
じる。一方、「静的」とは「静的スケジューリング」を
意味し、コンパイル時に、並列実行すべきプログラムを
プロセッサに割り付けてしまうやり方。長所は実行時に
プロセッサ割り付け（スケジューリング）のオーバーヘ
ッドがない。短所は負荷分散が難しい。例えば、請求項
５及び請求項６に示すように、各逐次ＤＯループと並列
ＤＯループとの間に依存関係がないことが検出された場
合には、実行時には逐次ＤＯループを優先的に並列計算
機のプロセッサに割り付け、残りのプロセッサで並列Ｄ
Ｏループを実行させるようにＤＯループ間並列化コード
又はＤＯループ間静的並列化コードを作成する。
【００１０】さらに、請求項７及び請求項８には、前記
ＤＯループ間依存関係検出部２０により、データ依存関
係にある２つのＤＯループ間で、そのデータ依存が２つ
のループの各項の項番号（添字）について常に等距離で
あることが検出された場合には、前記ＤＯループ動的並
列化コード作成部３０又はＤＯループ静的並列化コード
作成部３１は各項の実行についてはパイプラインを実行
させるようなＤＯループ間動的並列化コード又はＤＯル
ープ間静的並列化コードを作成する。ここで、「等距
離」とは“Distansce vector”で表現可能であることを
示す。例えば、２つのＤＯループの各項が各々Ａ（ｉ）
と、Ａ（ｉ−１）とで表される場合がこれにあたる。そ
れに対し、２つのＤＯループの各項が各々Ａ（ｉ）と、
Ａ（１００−ｉ）と表される場合は、等距離でない場合
の例である。請求項９には、階層型メモリを持った並列
計算機上で複数のＤＯループをパイプライン実行させる
際には、ＤＯループ間の通信が階層を越えないように同
じクラスターに割り付けるようにＤＯループ間動的並列
化コード又はＤＯループ間動的並列化コードを作成す
る。ここで、「階層型メモリ」とは、システム上である
プロセッサに注目した場合に、そのプロセッサから種々
の距離に接続されている複数のメモリ装置をいい、その
距離に応じて階層が設定されている。例えば、プロセッ
サから最も近い距離にあるのがキャッシュメモリであ
り、その次が当該クラスターの主記憶装置、さらに、ネ
ットワークを介して接続された他のクラスターの主記憶
装置……というような階層に各メモリが配置されてい
る。階層型のメモリを持った並列計算機で、ＤＯループ
間のパイプライン実行をさせる場合、それらのＤＯルー
プ間の通信が階層をまたがないように、同じクラスター
に割り付ける。これにより、高速なパイプライン実行が
可能になる。また、そのクラスター内のキャッシュ・コ
ヒーレンシーを保つプロトコルが、キャッシュからキャ
ッシュへ直接コピーするものである場合には、メモリを
介在せず直接キャッシュ間でデータがパイプライン転送
されるため、その効果は一層大きい。本発明により、従
来の並列化コンパイラにより、より高い並列性を得るこ
とができる。また、ＤＯループ間のパイプライン実行を
行う際に、そのデータを高速に転送させることができ
る。以上により、高速な演算の実行が並列計算機上で可
能になる。
ＤＯループ間依存関係検出部２０により、データ依存関
係にある２つのＤＯループ間で、そのデータ依存が２つ
のループの各項の項番号（添字）について常に等距離で
あることが検出された場合には、前記ＤＯループ動的並
列化コード作成部３０又はＤＯループ静的並列化コード
作成部３１は各項の実行についてはパイプラインを実行
させるようなＤＯループ間動的並列化コード又はＤＯル
ープ間静的並列化コードを作成する。ここで、「等距
離」とは“Distansce vector”で表現可能であることを
示す。例えば、２つのＤＯループの各項が各々Ａ（ｉ）
と、Ａ（ｉ−１）とで表される場合がこれにあたる。そ
れに対し、２つのＤＯループの各項が各々Ａ（ｉ）と、
Ａ（１００−ｉ）と表される場合は、等距離でない場合
の例である。請求項９には、階層型メモリを持った並列
計算機上で複数のＤＯループをパイプライン実行させる
際には、ＤＯループ間の通信が階層を越えないように同
じクラスターに割り付けるようにＤＯループ間動的並列
化コード又はＤＯループ間動的並列化コードを作成す
る。ここで、「階層型メモリ」とは、システム上である
プロセッサに注目した場合に、そのプロセッサから種々
の距離に接続されている複数のメモリ装置をいい、その
距離に応じて階層が設定されている。例えば、プロセッ
サから最も近い距離にあるのがキャッシュメモリであ
り、その次が当該クラスターの主記憶装置、さらに、ネ
ットワークを介して接続された他のクラスターの主記憶
装置……というような階層に各メモリが配置されてい
る。階層型のメモリを持った並列計算機で、ＤＯループ
間のパイプライン実行をさせる場合、それらのＤＯルー
プ間の通信が階層をまたがないように、同じクラスター
に割り付ける。これにより、高速なパイプライン実行が
可能になる。また、そのクラスター内のキャッシュ・コ
ヒーレンシーを保つプロトコルが、キャッシュからキャ
ッシュへ直接コピーするものである場合には、メモリを
介在せず直接キャッシュ間でデータがパイプライン転送
されるため、その効果は一層大きい。本発明により、従
来の並列化コンパイラにより、より高い並列性を得るこ
とができる。また、ＤＯループ間のパイプライン実行を
行う際に、そのデータを高速に転送させることができ
る。以上により、高速な演算の実行が並列計算機上で可
能になる。
【００１１】
【実施例】本発明の実施例を図５に基づいて説明する。
同図に示すように、本実施例は、逐次型言語で記述され
た原コードが格納された原コードファイル５と、当該原
コードを並列計算機用の目的コードに変換する自動並列
化翻訳装置（コンパイラ）７と、自動並列化翻訳装置７
により原コードから変換された目的コードを格納する目
的コードファイル６と、処理が割り付けられるべきプロ
セッサを予め指定する指定情報を格納する指定情報格納
部４とを有する。さらに、前記自動並列化翻訳装置７
は、同図に示すように、並列計算機により並列実行の可
能な並列ＤＯループ及び、並列実行の不可能な逐次ＤＯ
ループを抽出するＤＯループ抽出部１と、抽出された並
列ＤＯループについて、ＤＯループ内の各項を並列実行
させるＤＯループ内並列化コードを作成するＤＯループ
内並列化コード作成部８と、抽出されたＤＯループの間
の依存関係の検出を行うＤＯループ間依存関係検出部２
と、前記ＤＯループ内並列化コード及び検出されたＤＯ
ループ間の依存関係または前記指定情報に基づいて、Ｄ
Ｏループ間での並列実行を可能とするＤＯループ間並列
化コードを作成するＤＯループ間並列化コード作成部３
とを有するものである。当該ＤＯループ間並列化コード
作成部３は、同図に示すように、前記ＤＯループ間依存
関係検出部２により、各逐次ＤＯループと並列ＤＯルー
プとの間の依存関係がないことが検出された場合には、
実行時には逐次ＤＯループを優先的に割り付け、残りの
プロセッサで並列ＤＯループを実行させるようなＤＯル
ープ間動的並列化コード又はＤＯループ間静的並列化コ
ード作成の指示を行う独立並列ＤＯループ作成指示部３
ａと、前記ＤＯループ間依存関係検出部２により、デー
タ依存関係にある２つのＤＯループ間で、そのデータ依
存が２つのループの各イテレーション（項）の添字（項
番号）について常に等距離であることが検出された場合
には、各項の実行についてはパイプラインを実行させる
ＤＯループ間動的並列化コード又はＤＯループ間静的並
列化コードの作成の指示を行う等距離逐次ＤＯループ割
付指示部３ｂと、データ依存関係にある２つのＤＯルー
プ間で、そのデータ依存が２つのループの各項の項番号
について常に等距離であることが検出された場合には、
各項の処理についてはパイプライン処理を実行させるよ
うなＤＯループ間動的並列化コード又はＤＯループ間静
的並列化コードを作成する指示を行う等距離ＤＯループ
割付指示部３ｃと、階層型のメモリを持った並列計算機
上で複数のＤＯループをパイプライン実行させる際に
は、ＤＯループ間の通信が階層を越えないように同じク
ラスターに割り付けるようにＤＯループ間動的並列化コ
ード又はＤＯループ間静的並列化コードの作成を指示す
る階層型メモリ割付指示部３ｄと、前記独立並列ＤＯル
ープ割付指示部３ａ、等距離逐次ＤＯループ割付指示部
３ｂ、等距離ＤＯループ割付指示部３ｃ及び階層型メモ
リ割付指示部３ｄからの割り付けの指示があった場合に
は、前記ＤＯループ内並列化コード及び検出されたＤＯ
ループ間の依存関係または前記指定情報格納部４から読
みだされた指定情報に基づいて、目的コードの作成を行
う目的コード作成部３ｅとを有するものである。
同図に示すように、本実施例は、逐次型言語で記述され
た原コードが格納された原コードファイル５と、当該原
コードを並列計算機用の目的コードに変換する自動並列
化翻訳装置（コンパイラ）７と、自動並列化翻訳装置７
により原コードから変換された目的コードを格納する目
的コードファイル６と、処理が割り付けられるべきプロ
セッサを予め指定する指定情報を格納する指定情報格納
部４とを有する。さらに、前記自動並列化翻訳装置７
は、同図に示すように、並列計算機により並列実行の可
能な並列ＤＯループ及び、並列実行の不可能な逐次ＤＯ
ループを抽出するＤＯループ抽出部１と、抽出された並
列ＤＯループについて、ＤＯループ内の各項を並列実行
させるＤＯループ内並列化コードを作成するＤＯループ
内並列化コード作成部８と、抽出されたＤＯループの間
の依存関係の検出を行うＤＯループ間依存関係検出部２
と、前記ＤＯループ内並列化コード及び検出されたＤＯ
ループ間の依存関係または前記指定情報に基づいて、Ｄ
Ｏループ間での並列実行を可能とするＤＯループ間並列
化コードを作成するＤＯループ間並列化コード作成部３
とを有するものである。当該ＤＯループ間並列化コード
作成部３は、同図に示すように、前記ＤＯループ間依存
関係検出部２により、各逐次ＤＯループと並列ＤＯルー
プとの間の依存関係がないことが検出された場合には、
実行時には逐次ＤＯループを優先的に割り付け、残りの
プロセッサで並列ＤＯループを実行させるようなＤＯル
ープ間動的並列化コード又はＤＯループ間静的並列化コ
ード作成の指示を行う独立並列ＤＯループ作成指示部３
ａと、前記ＤＯループ間依存関係検出部２により、デー
タ依存関係にある２つのＤＯループ間で、そのデータ依
存が２つのループの各イテレーション（項）の添字（項
番号）について常に等距離であることが検出された場合
には、各項の実行についてはパイプラインを実行させる
ＤＯループ間動的並列化コード又はＤＯループ間静的並
列化コードの作成の指示を行う等距離逐次ＤＯループ割
付指示部３ｂと、データ依存関係にある２つのＤＯルー
プ間で、そのデータ依存が２つのループの各項の項番号
について常に等距離であることが検出された場合には、
各項の処理についてはパイプライン処理を実行させるよ
うなＤＯループ間動的並列化コード又はＤＯループ間静
的並列化コードを作成する指示を行う等距離ＤＯループ
割付指示部３ｃと、階層型のメモリを持った並列計算機
上で複数のＤＯループをパイプライン実行させる際に
は、ＤＯループ間の通信が階層を越えないように同じク
ラスターに割り付けるようにＤＯループ間動的並列化コ
ード又はＤＯループ間静的並列化コードの作成を指示す
る階層型メモリ割付指示部３ｄと、前記独立並列ＤＯル
ープ割付指示部３ａ、等距離逐次ＤＯループ割付指示部
３ｂ、等距離ＤＯループ割付指示部３ｃ及び階層型メモ
リ割付指示部３ｄからの割り付けの指示があった場合に
は、前記ＤＯループ内並列化コード及び検出されたＤＯ
ループ間の依存関係または前記指定情報格納部４から読
みだされた指定情報に基づいて、目的コードの作成を行
う目的コード作成部３ｅとを有するものである。
【００１２】また、図８には、前記自動並列化コンパイ
ラ（翻訳装置）により変換された目的コードにより並列
実行の行われる本実施例に係る並列計算機のシステム構
成図を示す。同図に示すように、本システムでは、階層
型のメモリであるキャッシュ・メモリ１５11ｂ〜１５24
ｂ及び主記憶装置１３1 、１３2 をもつ並列計算機であ
り、大きくは２つのクラスター１１1 、１１2 がネット
ワーク１２により接続されたシステムである。各クラス
ター１１1 、１１2 には、プロセッサ１５11ａ〜１５24
ａ及びキャッシュ・メモリ１５11ｂ〜１５24ｂの複数の
組１５11〜１５24と、すべてのプロセッサ１５11ａ〜１
５24ａからのアクセス可能な共通の主記憶装置１３1 、
１３2とを有する。また、各主記憶装置１３1 、１３2
には、実行時の各プロセッサの使用状況を示すスケジュ
ーラ１４1 、１４2 と、前記目的コードを格納する格納
部１６1 、１６2 とを有する。
ラ（翻訳装置）により変換された目的コードにより並列
実行の行われる本実施例に係る並列計算機のシステム構
成図を示す。同図に示すように、本システムでは、階層
型のメモリであるキャッシュ・メモリ１５11ｂ〜１５24
ｂ及び主記憶装置１３1 、１３2 をもつ並列計算機であ
り、大きくは２つのクラスター１１1 、１１2 がネット
ワーク１２により接続されたシステムである。各クラス
ター１１1 、１１2 には、プロセッサ１５11ａ〜１５24
ａ及びキャッシュ・メモリ１５11ｂ〜１５24ｂの複数の
組１５11〜１５24と、すべてのプロセッサ１５11ａ〜１
５24ａからのアクセス可能な共通の主記憶装置１３1 、
１３2とを有する。また、各主記憶装置１３1 、１３2
には、実行時の各プロセッサの使用状況を示すスケジュ
ーラ１４1 、１４2 と、前記目的コードを格納する格納
部１６1 、１６2 とを有する。
【００１３】続いて、本実施例に係る動作について説明
する。図６に示すように、ステップＳＪ１で、自動並列
化翻訳の対象となる逐次型言語で記述された原コードを
前記原コードファイル５から読み出し、自動並列化翻訳
装置（コンパイラ）７に入力する。すると、ステップＳ
Ｊ２で、前記ＤＯループ抽出部１はＤＯループを抽出す
る。ステップＳＪ３でＤＯループがない場合には終了
し、ＤＯループの抽出があった場合にはステップＳＪ４
に進み、並列ＤＯループか否かの判断を行う。並列ＤＯ
ループか否かの判断はＤＯループ内の各項のデータ依存
関係を調べることにより、各項が独立な場合には、並列
ＤＯループであると判断される。ステップＳＪ４で、並
列ＤＯループであると判断された場合には、ステップＳ
Ｊ５に進み、前記ＤＯループ内並列化コード作成部８は
ＤＯループ内の各イテレーション（項）を複数のプロセ
ッサで並列実行可能なように、ＤＯループ内での並列化
コードを作成する。ステップＳＪ６で、前記ＤＯループ
間並列化コード作成部３の等距離逐次ＤＯループ割付指
示部３ｂはデータ依存関係のあるうちで添字（項番号）
が等距離の逐次ＤＯループの検索を行う。ステップＳＪ
７で、添字が等距離の逐次ＤＯループがあった場合に
は、ステップＳ１５で、前記目的コード作成部３ｅは指
示に従って、パイプライン処理が行われるような目的コ
ードを作成する。
する。図６に示すように、ステップＳＪ１で、自動並列
化翻訳の対象となる逐次型言語で記述された原コードを
前記原コードファイル５から読み出し、自動並列化翻訳
装置（コンパイラ）７に入力する。すると、ステップＳ
Ｊ２で、前記ＤＯループ抽出部１はＤＯループを抽出す
る。ステップＳＪ３でＤＯループがない場合には終了
し、ＤＯループの抽出があった場合にはステップＳＪ４
に進み、並列ＤＯループか否かの判断を行う。並列ＤＯ
ループか否かの判断はＤＯループ内の各項のデータ依存
関係を調べることにより、各項が独立な場合には、並列
ＤＯループであると判断される。ステップＳＪ４で、並
列ＤＯループであると判断された場合には、ステップＳ
Ｊ５に進み、前記ＤＯループ内並列化コード作成部８は
ＤＯループ内の各イテレーション（項）を複数のプロセ
ッサで並列実行可能なように、ＤＯループ内での並列化
コードを作成する。ステップＳＪ６で、前記ＤＯループ
間並列化コード作成部３の等距離逐次ＤＯループ割付指
示部３ｂはデータ依存関係のあるうちで添字（項番号）
が等距離の逐次ＤＯループの検索を行う。ステップＳＪ
７で、添字が等距離の逐次ＤＯループがあった場合に
は、ステップＳ１５で、前記目的コード作成部３ｅは指
示に従って、パイプライン処理が行われるような目的コ
ードを作成する。
【００１４】一方、ステップＳＪ４で、抽出されたＤＯ
ループが逐次ＤＯループであると判断された場合には、
ステップＳＪ８に進み、前記ＤＯループ間依存関係検出
部２は当該逐次ＤＯループとデータ依存関係のない並列
ＤＯループを検索する。ステップＳＪ９で、データ依存
関係のない並列ＤＯループがあった場合には、ステップ
ＳＪ１０に進み、前記独立並列ＤＯループ割付指示部３
ａは、逐次ＤＯループを優先的に並列計算機のプロセッ
サに割り付け、残りのプロセッサに対して、並列ＤＯル
ープを割り付けることになる。ステップＳＪ９で、依存
関係のない並列ＤＯループが存在しない場合には、ステ
ップＳＪ１１に進み、前記等距離逐次ＤＯループ割付指
示部３ｂは添字（項）が等距離の逐次ＤＯループの検索
を行い、ステップＳＪ１２でそのような逐次ＤＯループ
があったと判断された場合には、ステップＳＪ１５に進
み、前記目的コード作成部３ｅに対し、パイプライン処
理の実行が行われるように割付け等の指示を行う。
ループが逐次ＤＯループであると判断された場合には、
ステップＳＪ８に進み、前記ＤＯループ間依存関係検出
部２は当該逐次ＤＯループとデータ依存関係のない並列
ＤＯループを検索する。ステップＳＪ９で、データ依存
関係のない並列ＤＯループがあった場合には、ステップ
ＳＪ１０に進み、前記独立並列ＤＯループ割付指示部３
ａは、逐次ＤＯループを優先的に並列計算機のプロセッ
サに割り付け、残りのプロセッサに対して、並列ＤＯル
ープを割り付けることになる。ステップＳＪ９で、依存
関係のない並列ＤＯループが存在しない場合には、ステ
ップＳＪ１１に進み、前記等距離逐次ＤＯループ割付指
示部３ｂは添字（項）が等距離の逐次ＤＯループの検索
を行い、ステップＳＪ１２でそのような逐次ＤＯループ
があったと判断された場合には、ステップＳＪ１５に進
み、前記目的コード作成部３ｅに対し、パイプライン処
理の実行が行われるように割付け等の指示を行う。
【００１５】一方、ステップＳＪ１２で、添字が等距離
の逐次ＤＯループが存在しない場合には、ステップＳＪ
１３に進み、前記等距離ＤＯループ割付指示部３ｃは添
字が等距離の並列ＤＯループを検索し、当該並列ＤＯル
ープがあった場合には、ステップＳＪ１５で、前記目的
コード作成部３ｅに対し、パイプライン処理の実行がな
されるように指示を行う。但し、ステップＳＪ１５で、
並列計算機が階層型のメモリをもつ場合には、ＤＯルー
プ間でパイプライン実行を実現させる場合には、パイプ
ラインで実行させる双方のＤＯループの間の通信が階層
をまたがないように、同じクラスター（図８の符号１１
1 、１１2 ）に割り付けるようにする。これにより、高
速なパイプライン実行が可能になる。また、そのクラス
ター内のキャッシュ・コヒーレンシを保つ（当該クラス
ター内の任意のプロセッサが数値データ等を設定した場
合には、他のプロセッサの各キャッシュ・メモリ内にも
同様の数値データ等が設定されること）プロトコルが、
キャッシュ・メモリからキャッシュ・メモリへ直接コピ
ーするものである場合には、パイプラインで通信される
データ量がキャッシュ・メモリに入りきる大きさであれ
ば、共有メモリを介在せず直接キャッシュ・メモリ間で
データがパイプライン転送されるため、その効果は一層
大きい。尚、以上の説明で、動的スケジューリングの場
合には、実行状況に応じて使用可能なプロセッサの台数
により割り付けが行われるような目的コードが作成され
るが、静的スケジューリングの場合には、前記指定情報
格納部４からの情報に基づいてプロセッサの割り付けの
ための目的コードが作成される。
の逐次ＤＯループが存在しない場合には、ステップＳＪ
１３に進み、前記等距離ＤＯループ割付指示部３ｃは添
字が等距離の並列ＤＯループを検索し、当該並列ＤＯル
ープがあった場合には、ステップＳＪ１５で、前記目的
コード作成部３ｅに対し、パイプライン処理の実行がな
されるように指示を行う。但し、ステップＳＪ１５で、
並列計算機が階層型のメモリをもつ場合には、ＤＯルー
プ間でパイプライン実行を実現させる場合には、パイプ
ラインで実行させる双方のＤＯループの間の通信が階層
をまたがないように、同じクラスター（図８の符号１１
1 、１１2 ）に割り付けるようにする。これにより、高
速なパイプライン実行が可能になる。また、そのクラス
ター内のキャッシュ・コヒーレンシを保つ（当該クラス
ター内の任意のプロセッサが数値データ等を設定した場
合には、他のプロセッサの各キャッシュ・メモリ内にも
同様の数値データ等が設定されること）プロトコルが、
キャッシュ・メモリからキャッシュ・メモリへ直接コピ
ーするものである場合には、パイプラインで通信される
データ量がキャッシュ・メモリに入りきる大きさであれ
ば、共有メモリを介在せず直接キャッシュ・メモリ間で
データがパイプライン転送されるため、その効果は一層
大きい。尚、以上の説明で、動的スケジューリングの場
合には、実行状況に応じて使用可能なプロセッサの台数
により割り付けが行われるような目的コードが作成され
るが、静的スケジューリングの場合には、前記指定情報
格納部４からの情報に基づいてプロセッサの割り付けの
ための目的コードが作成される。
【００１６】図７には、当該自動並列化翻訳装置（コン
パイラ）７により原コードを目的コードに変換した場合
の具体例を示す。同図（ａ）には、原コードのＤＯルー
プを示す。この例では、前記指定情報として、例えば、
プロセッサが４台の場合、各プロセッサの番号（０，
１，２，３）は変数Ｐに設定されているとする。ここで
プロセスとはプロセッサに割り付けられる処理の単位を
いう。同図（ｂ）には、当該原コードを予め指定した指
定情報に基づいて、前記ＤＯループ間並列化コード作成
部３により、目的コードであるＤＯループ間静的並列化
コードを作成した例を示す。この例では、４つのプロセ
ッサが同時に以下の処理を行うことになる。しかし、各
プロセッサ内でのＰの値は違うので、プロセッサφでは
ＤＯ Ｉ＝１，２５６ を意味し、プロセッサ１では、
ＤＯ Ｉ＝２５７，５１２……というふうに実行される
ことになる。一方、同図（ｃ）には、、動的スケジュー
リングの場合の目的コードであるＤＯループ間動的並列
化コードを示す。同図で、Ｉは全てのプロセッサから共
通にアクセスできるグローバルな変数ｉは各プロセッサ
内だけのプライベートな変数であり、各プロセッサは、
１から２５６までの数の中から順に１つずつ値を取り出
して、自分のローカルな変数ｉに入れて、その処理を行
う２つ以上のプロセッサが同じ値を取り出さないよう
に、例えば、前記スケジューラに設けられたキューをア
クセスする場合には、当該プロセッサのみのアクセスが
可能であって、他のプロセッサからのアクセスを禁止し
て重複した実行を防止するために、“ＬＯＣＫ”を行
い、キューからの読出しが終了した段階で、“ＬＯＣ
Ｋ”を解除することになる。
パイラ）７により原コードを目的コードに変換した場合
の具体例を示す。同図（ａ）には、原コードのＤＯルー
プを示す。この例では、前記指定情報として、例えば、
プロセッサが４台の場合、各プロセッサの番号（０，
１，２，３）は変数Ｐに設定されているとする。ここで
プロセスとはプロセッサに割り付けられる処理の単位を
いう。同図（ｂ）には、当該原コードを予め指定した指
定情報に基づいて、前記ＤＯループ間並列化コード作成
部３により、目的コードであるＤＯループ間静的並列化
コードを作成した例を示す。この例では、４つのプロセ
ッサが同時に以下の処理を行うことになる。しかし、各
プロセッサ内でのＰの値は違うので、プロセッサφでは
ＤＯ Ｉ＝１，２５６ を意味し、プロセッサ１では、
ＤＯ Ｉ＝２５７，５１２……というふうに実行される
ことになる。一方、同図（ｃ）には、、動的スケジュー
リングの場合の目的コードであるＤＯループ間動的並列
化コードを示す。同図で、Ｉは全てのプロセッサから共
通にアクセスできるグローバルな変数ｉは各プロセッサ
内だけのプライベートな変数であり、各プロセッサは、
１から２５６までの数の中から順に１つずつ値を取り出
して、自分のローカルな変数ｉに入れて、その処理を行
う２つ以上のプロセッサが同じ値を取り出さないよう
に、例えば、前記スケジューラに設けられたキューをア
クセスする場合には、当該プロセッサのみのアクセスが
可能であって、他のプロセッサからのアクセスを禁止し
て重複した実行を防止するために、“ＬＯＣＫ”を行
い、キューからの読出しが終了した段階で、“ＬＯＣ
Ｋ”を解除することになる。
【００１７】以下、図９〜図１１に基づいて実行時のプ
ロセッサの割り付け例を示す。この各例では、原コード
は、ＤＯループ１の各項はＡ（ｉ）からなるＤＯループ
（Ｌｏｏｐ）であり、 ＤＯ ｉ＝１，１６ Ａ（ｉ） ＤＯループ２の各項はＢ（ｉ）からなるＤＯループであ
り、 ＤＯ ｉ＝１，１６ Ｂ（ｉ） で表され、Ａ（ｉ）とＢ（ｉ）は互いにデータの依存関
係はないものとする。また、説明の簡単のため、ＤＯル
ープ１とＤＯループ２とでの各ステップの処理時間は等
しいものとし、各項（ステップ、イテレーション）の項
（ステップ）数は１６とする。また、ｐ０〜ｐ３は割り
付けられるべき並列計算機を形成する各プロセッサを示
す。
ロセッサの割り付け例を示す。この各例では、原コード
は、ＤＯループ１の各項はＡ（ｉ）からなるＤＯループ
（Ｌｏｏｐ）であり、 ＤＯ ｉ＝１，１６ Ａ（ｉ） ＤＯループ２の各項はＢ（ｉ）からなるＤＯループであ
り、 ＤＯ ｉ＝１，１６ Ｂ（ｉ） で表され、Ａ（ｉ）とＢ（ｉ）は互いにデータの依存関
係はないものとする。また、説明の簡単のため、ＤＯル
ープ１とＤＯループ２とでの各ステップの処理時間は等
しいものとし、各項（ステップ、イテレーション）の項
（ステップ）数は１６とする。また、ｐ０〜ｐ３は割り
付けられるべき並列計算機を形成する各プロセッサを示
す。
【００１８】図９の（ａ）は従来例に係る場合であっ
て、並列ＤＯループであるＤＯループ１を各プロセッサ
に分割して並列実行させた後、逐次ＤＯループであるＤ
Ｏループ２を１台のプロセッサによって実行させた様子
を示す。この場合には必要とするステップ数は２０とな
る。同図（ｂ）には、並列ＤＯループであるＤＯループ
１と逐次ＤＯループであるＤＯループ２を並列に実行さ
せた様子を示している。逐次ＤＯループ２を１台のプロ
セッサに割り付け、並列ＤＯループ１を残りの３台のプ
ロセッサに分散させて並列実行させている。全体の処理
の為に必要なステップ数（項数）は１６となり高速化さ
れている。
て、並列ＤＯループであるＤＯループ１を各プロセッサ
に分割して並列実行させた後、逐次ＤＯループであるＤ
Ｏループ２を１台のプロセッサによって実行させた様子
を示す。この場合には必要とするステップ数は２０とな
る。同図（ｂ）には、並列ＤＯループであるＤＯループ
１と逐次ＤＯループであるＤＯループ２を並列に実行さ
せた様子を示している。逐次ＤＯループ２を１台のプロ
セッサに割り付け、並列ＤＯループ１を残りの３台のプ
ロセッサに分散させて並列実行させている。全体の処理
の為に必要なステップ数（項数）は１６となり高速化さ
れている。
【００１９】図１０の場合にはＤＯループ１及びＤＯル
ープ２をどちらも逐次ＤＯループとし、ＤＯループ１か
らＤＯループ２へは、それぞれの添字を比較した場合、
距離０のデータ依存関係がある場合を示す。この場合、
２つのループのパイプライン実行が可能になる。図１０
（ａ）では、従来例に相当する場合であって、ＤＯルー
プ１を実行した後に、ＤＯループ２を実行させた様子を
示している。この場合処理に必要なステップ数は３２と
なる。図１０（ｂ）はＤＯループ１とＤＯループ２とを
パイプライン実行させたようすを示す。この場合、処理
に必要なステップ数は１７となり高速化されている。
ープ２をどちらも逐次ＤＯループとし、ＤＯループ１か
らＤＯループ２へは、それぞれの添字を比較した場合、
距離０のデータ依存関係がある場合を示す。この場合、
２つのループのパイプライン実行が可能になる。図１０
（ａ）では、従来例に相当する場合であって、ＤＯルー
プ１を実行した後に、ＤＯループ２を実行させた様子を
示している。この場合処理に必要なステップ数は３２と
なる。図１０（ｂ）はＤＯループ１とＤＯループ２とを
パイプライン実行させたようすを示す。この場合、処理
に必要なステップ数は１７となり高速化されている。
【００２０】図１１（ｂ）の場合は、ＤＯループ１が逐
次ＤＯループであり、ＤＯループ２を並列ＤＯループと
し、ＤＯループ１からＤＯループ２へのデータ依存関係
が存在する場合には、従来例では、図１１（ｂ）のよう
になり、ステップ数は２０となる。ＤＯループ２の並列
実行は行わずに、図１０の場合と同じようにパイプライ
ン実行させる（図１０（ｂ））ことによりステップ数は
１７と高速化される。以上説明したように、本実施例に
あっては、ＤＯループを出来るかぎり並列処理を行うよ
うにしている。したがって、その処理のステップ数を削
減することができるので、処理を高速化することができ
る。また、図８に示すように、階層型のメモリをもった
並列型計算機の場合には、前述したように、ＤＯループ
間のパイプライン実行を実現する際に、パイプラインで
実行させる双方のＤＯループを同じクラスター内に割り
付けることで、データの通信がネットワークを介在する
ことなく実現でき、高速な実行が可能となる。パイプラ
インで通信されるデータ量がキャッシュ・メモリに入り
きる大きさであれば、共有メモリを介在することもな
く、キャッシュ・メモリから相手側のキャッシュ・メモ
リに直接転送され、さらに高速な実行が可能となる。さ
らに、本実施例では、静的スケジューリングの場合だけ
でなく、動的スケジューリングの場合について、原コー
ドを目的コードに変換するようにしている。したがっ
て、各々の場合の長所を場合に応じて選択することがで
きるので、便利である。即ち、静的スケジューリングは
実行時にプロセッサの割付けを行う必要がないので、そ
の処理（オーバヘッド）分の時間が省略できて、処理が
高速になる。また、動的スケジューリングは、コンパイ
ルされたプログラム（目的コード）はどんなプロセッサ
台数構成の並列計算機上でも動作することができ便利で
ある。
次ＤＯループであり、ＤＯループ２を並列ＤＯループと
し、ＤＯループ１からＤＯループ２へのデータ依存関係
が存在する場合には、従来例では、図１１（ｂ）のよう
になり、ステップ数は２０となる。ＤＯループ２の並列
実行は行わずに、図１０の場合と同じようにパイプライ
ン実行させる（図１０（ｂ））ことによりステップ数は
１７と高速化される。以上説明したように、本実施例に
あっては、ＤＯループを出来るかぎり並列処理を行うよ
うにしている。したがって、その処理のステップ数を削
減することができるので、処理を高速化することができ
る。また、図８に示すように、階層型のメモリをもった
並列型計算機の場合には、前述したように、ＤＯループ
間のパイプライン実行を実現する際に、パイプラインで
実行させる双方のＤＯループを同じクラスター内に割り
付けることで、データの通信がネットワークを介在する
ことなく実現でき、高速な実行が可能となる。パイプラ
インで通信されるデータ量がキャッシュ・メモリに入り
きる大きさであれば、共有メモリを介在することもな
く、キャッシュ・メモリから相手側のキャッシュ・メモ
リに直接転送され、さらに高速な実行が可能となる。さ
らに、本実施例では、静的スケジューリングの場合だけ
でなく、動的スケジューリングの場合について、原コー
ドを目的コードに変換するようにしている。したがっ
て、各々の場合の長所を場合に応じて選択することがで
きるので、便利である。即ち、静的スケジューリングは
実行時にプロセッサの割付けを行う必要がないので、そ
の処理（オーバヘッド）分の時間が省略できて、処理が
高速になる。また、動的スケジューリングは、コンパイ
ルされたプログラム（目的コード）はどんなプロセッサ
台数構成の並列計算機上でも動作することができ便利で
ある。
【００２１】
【発明の効果】以上説明したように、本発明にあって
は、並列計算機でＤＯループの実行を行う際には、単に
各並列ＤＯループ内の各項の間だけでなく、各ＤＯルー
プ間でも、可能な限り各プロセッサにより並列実行させ
るように原コードを目的コードに変換している。したが
って、処理の手数を削減することにより、処理を高速化
し、処理時間を削減し、並列計算機の処理効率を高める
ことができるので、並列計算機の有効利用を図ることが
できる。また、第一及び第二の発明の場合には動的スケ
ジューリングの場合についての並列化を行っているの
で、翻訳されたプログラムはどんなプロセッサ台数の構
成の並列計算機上でも動作する。さらに、第三及び第四
の発明の場合には、静的スケジューリングの場合につい
ての並列化を行っているので、実行時にプロセッサ割付
けを行う必要がなく、その分処理が高速化されることに
なる。
は、並列計算機でＤＯループの実行を行う際には、単に
各並列ＤＯループ内の各項の間だけでなく、各ＤＯルー
プ間でも、可能な限り各プロセッサにより並列実行させ
るように原コードを目的コードに変換している。したが
って、処理の手数を削減することにより、処理を高速化
し、処理時間を削減し、並列計算機の処理効率を高める
ことができるので、並列計算機の有効利用を図ることが
できる。また、第一及び第二の発明の場合には動的スケ
ジューリングの場合についての並列化を行っているの
で、翻訳されたプログラムはどんなプロセッサ台数の構
成の並列計算機上でも動作する。さらに、第三及び第四
の発明の場合には、静的スケジューリングの場合につい
ての並列化を行っているので、実行時にプロセッサ割付
けを行う必要がなく、その分処理が高速化されることに
なる。
【図１】第一の発明の原理ブロック図
【図２】第二の発明の原理流れ図
【図３】第三の発明の原理ブロック図
【図４】第四の発明の原理ブロック図
【図５】実施例に係るブロック図
【図６】実施例に係る流れ図
【図７】実施例に係るＤＯループのコードの変換例を示
す図
す図
【図８】実施例に係る並列計算機のシステム構成を示す
図
図
【図９】従来例及び実施例に係る実行時の割付け例を示
す図（１）
す図（１）
【図１０】従来例及び実施例に係る実行時の割付け例を
示す図（２）
示す図（２）
【図１１】従来例及び実施例に係る実行時の割付け例を
示す図（３）
示す図（３）
【図１２】従来例に係るブロック図
１０，１ ＤＯループ抽出部 ２０，２ ＤＯループ間依存関係検出部 ３０ ＤＯループ間動的並列化コード作成部 ３１ ＤＯループ間静的並列化コード作成部 ４０（４） 指定情報出力部（指定情報格納部） ８０，８ ＤＯループ内並列化コード作成部
Claims (10)
- 【請求項１】 逐次型言語で記述された原コードから、
並列計算機により並列実行の可能な並列ＤＯループ及
び、並列実行の不可能な逐次ＤＯループを抽出するＤＯ
ループ抽出部（１０）と、抽出された並列ＤＯループに
ついて、ＤＯループ内の各項を並列実行させるＤＯルー
プ内並列化コードを作成するＤＯループ内並列化コード
作成部（８０）とを有し、前記原コードを並列計算機用
の目的コードに変換する自動並列化翻訳装置において、 抽出されたＤＯループの間の依存関係の検出を行うＤＯ
ループ間依存関係検出部（２０）と、 前記ＤＯループ内並列化コード及び検出されたＤＯルー
プ間の依存関係に基づいて、動的にＤＯループ間での並
列実行を可能とするＤＯループ間動的並列化コードを作
成するＤＯループ間動的並列化コード作成部（３０）と
を有することを特徴とする自動並列化翻訳装置。 - 【請求項２】 逐次型言語で記述された原コードを入力
し（Ｓ１）、並列計算機により並列実行の可能な並列Ｄ
Ｏループ及び、並列実行の不可能な逐次ＤＯループを原
コードから抽出し、抽出された並列ＤＯループについ
て、ＤＯループ内の各項を並列実行させるＤＯループ内
並列化コードを作成する（Ｓ２）ことにより原コードを
並列計算機用の目的コードに変換する自動並列化翻訳方
法において、 抽出された前記ＤＯループの間の依存関係の検出を行い
（Ｓ３）、 前記ＤＯループ内並列化コード及び検出された前記ＤＯ
ループ間の依存関係に基づいて、動的にＤＯループ間で
の並列実行を可能とするＤＯループ間動的並列化コード
を作成する（Ｓ４）ことを特徴とする自動並列化翻訳方
法。 - 【請求項３】 逐次型言語で記述された原コードから、
並列計算機により並列実行の可能な並列ＤＯループ及
び、並列実行の不可能な逐次ＤＯループを抽出するＤＯ
ループ抽出部（１０）と，抽出された並列ＤＯループに
ついて、ＤＯループ内の各項を並列実行させるＤＯルー
プ内並列化コードを作成するＤＯループ内並列化コード
作成部（８０）とを有し、前記原コードを並列計算機用
の目的コードに変換する自動並列化翻訳装置において、 抽出されたＤＯループの間の依存関係の検出を行うＤＯ
ループ間依存関係検出部（２０）と、 処理が割り付けられるプロセッサを予め指定する指定情
報を出力する指定情報出力部（４０）と、 前記ＤＯループ内並列化コード、検出されたＤＯループ
間の依存関係、及び前記指定情報に基づいて、静的にＤ
Ｏループ間での並列実行を可能とするＤＯループ間静的
並列化コードを作成するＤＯループ間静的並列化コード
作成部（３１）とを有することを特徴とする自動並列化
翻訳装置。 - 【請求項４】 逐次型言語で記述された原コードを入力
し（Ｓ１）、並列計算機により並列実行の可能な並列Ｄ
Ｏループ及び、並列処理の不可能な逐次ＤＯループを原
コードから抽出し、抽出された並列ＤＯループについ
て、ＤＯループ内で並列実行させるＤＯループ内並列化
コードを作成する（Ｓ２）ことにより原コードを並列計
算機用の目的コードに変換する自動並列化翻訳方法にお
いて、 抽出された前記ＤＯループの間の依存関係の検出を行い
（Ｓ３）、 前記ＤＯループ内並列化コード、検出されたＤＯループ
間の依存関係、及び処理が割り付けられるべきプロセッ
サを予め指定する指定情報に基づいて、静的にＤＯルー
プ間での並列実行を行わせるＤＯループ間静的並列化コ
ードを作成する（Ｓ１４）ことを特徴とする自動並列化
翻訳方法。 - 【請求項５】 前記ＤＯループ間依存関係検出部（２
０）により、各逐次ＤＯループと並列ＤＯループとの間
に依存関係がないことが検出された場合には、実行時に
は逐次ＤＯループを優先的にプロセッサに割り付け、残
りのプロセッサで並列ＤＯループを実行させるＤＯルー
プ間動的並列化コード又はＤＯループ間静的並列化コー
ドを作成するＤＯループ動的並列化コード作成部（３
０）又はＤＯループ静的並列化コード作成部（３１）を
有することを特徴とする請求項１又は請求項３記載の自
動並列化翻訳装置。 - 【請求項６】 各逐次ＤＯループと並列ＤＯループとの
間に依存関係がないことが検出された場合には、実行時
には逐次ＤＯループを優先的にプロセッサに割り付け、
残りのプロセッサで並列ＤＯループを実行させるＤＯル
ープ間動的並列化コード又はＤＯループ間静的並列化コ
ードを作成することを特徴とする請求項２又は４記載の
自動並列化翻訳方法。 - 【請求項７】 前記ＤＯループ間依存関係検出部（２
０）により、データ依存関係にある２つのＤＯループ間
で、そのデータ依存が２つのループの各項の項番号につ
いて常に等距離であることが検出された場合には、前記
ＤＯループ動的並列化コード作成部（３０）又はＤＯル
ープ静的並列化コード作成部（３１）は各項の実行につ
いてはパイプラインを実行させるＤＯループ間動的並列
化コード又はＤＯループ間静的並列化コードを作成する
ことを特徴とする請求項１又は請求項３記載の自動並列
化翻訳装置。 - 【請求項８】 データ依存関係にある２つのＤＯループ
間で、そのデータ依存が２つのループの各項の項番号に
ついて常に等距離であることが検出された場合には、各
項の処理についてはパイプライン処理を実行させるＤＯ
ループ間動的並列化コード又はＤＯループ間静的並列化
コードを作成することを特徴とする請求項２又は請求項
４記載の自動並列化翻訳方法。 - 【請求項９】 階層型のメモリを持った並列計算機上で
複数のＤＯループをパイプライン実行させる際には、Ｄ
Ｏループ間の通信が階層を越えないように同じクラスタ
ーに割り付けるようにＤＯループ間動的並列化コード又
はＤＯループ間静的並列化コードを作成すること特徴と
する請求項７の自動並列化翻訳装置。 - 【請求項１０】 階層型のメモリを持った並列計算機上
で複数のＤＯループをパイプライン実行させる際には、
ＤＯループ間の通信が階層を越えないように同じクラス
ターに割り付けるようにＤＯループ間動的並列化コード
又はＤＯループ間動的並列化コードを作成すること特徴
とする請求項８記載の自動並列化翻訳方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP626293A JPH06214801A (ja) | 1993-01-18 | 1993-01-18 | 自動並列化翻訳装置及び方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP626293A JPH06214801A (ja) | 1993-01-18 | 1993-01-18 | 自動並列化翻訳装置及び方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH06214801A true JPH06214801A (ja) | 1994-08-05 |
Family
ID=11633549
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP626293A Withdrawn JPH06214801A (ja) | 1993-01-18 | 1993-01-18 | 自動並列化翻訳装置及び方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH06214801A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011118752A (ja) * | 2009-12-04 | 2011-06-16 | Toshiba Corp | コンパイル装置 |
| CN118860369A (zh) * | 2024-08-29 | 2024-10-29 | 北京清程极智科技有限公司 | 代码并行化方法、装置、计算机设备、可读存储介质和程序产品 |
-
1993
- 1993-01-18 JP JP626293A patent/JPH06214801A/ja not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011118752A (ja) * | 2009-12-04 | 2011-06-16 | Toshiba Corp | コンパイル装置 |
| CN118860369A (zh) * | 2024-08-29 | 2024-10-29 | 北京清程极智科技有限公司 | 代码并行化方法、装置、计算机设备、可读存储介质和程序产品 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| TWI525540B (zh) | 具有橫跨多個處理器之平行資料執行緒的映射處理邏輯 | |
| CN111090464B (zh) | 一种数据流处理方法及相关设备 | |
| Bauer et al. | Singe: Leveraging warp specialization for high performance on gpus | |
| US8296743B2 (en) | Compiler and runtime for heterogeneous multiprocessor systems | |
| KR101559090B1 (ko) | 이종 코어를 위한 자동 커널 마이그레이션 | |
| US8417919B2 (en) | Assigning different serialization identifier to operations on different data set for execution in respective processor in multi-processor system | |
| US8528001B2 (en) | Controlling and dynamically varying automatic parallelization | |
| Huynh et al. | Scalable framework for mapping streaming applications onto multi-GPU systems | |
| US20120331278A1 (en) | Branch removal by data shuffling | |
| JP2019049843A (ja) | 実行ノード選定プログラム、実行ノード選定方法及び情報処理装置 | |
| Zhang et al. | Optimizing the Barnes-Hut algorithm in UPC | |
| Noaje et al. | Source-to-source code translator: OpenMP C to CUDA | |
| US20030126589A1 (en) | Providing parallel computing reduction operations | |
| Meenderinck et al. | A case for hardware task management support for the StarSs programming model | |
| JPH06214801A (ja) | 自動並列化翻訳装置及び方法 | |
| He et al. | ARACHNE: Optimizing distributed parallel applications with reduced inter-process communication | |
| Kaouane et al. | SysCellC: Systemc on cell | |
| US20250370768A1 (en) | A computer-implemented method and a computer-readable medium | |
| US20260119144A1 (en) | Techniques for compiler lowering of task-based programs to asynchronous accelerators | |
| Cole et al. | Efficient resource oblivious algorithms for multicores | |
| Wang et al. | micMR: An efficient MapReduce framework for CPU–MIC heterogeneous architecture | |
| Hu et al. | Adjust ELF format for multi-core architecture | |
| Liang et al. | Automatically migrating sequential applications to heterogeneous system architecture | |
| Patil | Auto Conversion of Serial C Code into Cuda-C-Code for Faster Execution Utilizing GPU | |
| Xiaowen | Research on Multi-Core PC Parallel Computation Based on OpenMP |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20000404 |