JPH0628324A - 並列計算機及びコンパイラ - Google Patents

Abstract

(57)【要約】 【構成】 基本ブロック内のデータ依存関係のある命令
毎に命令群を構成し、並列実行可能な命令群を対応づけ
る［Ａ］。各命令群の最初の命令から最後の命令までの
総実行時間と、各命令群の最初の命令から他の命令群の
発行可能時間を算出する［Ｂ］。着目する命令群以降に
この命令群と並列実行可能な命令群の有無を判断する
［Ｄ］。有る場合は並列実行可能な命令群を繰り上げる
ことで総実行時間を短縮できる命令群の有無を判断する
［Ｅ］。有る場合は総実行時間を最も短縮できる命令群
を繰り上げる［Ｆ］。無い場合は全命令群の処理を行っ
たかを判断し、行った場合は終了し、未処理命令群が有
る場合は次の命令群を処理する［Ｇ〜Ｈ］。 【効果】 命令によって実行時間の異なる場合でも、実
行時間が最も短い命令列にコンパイルできる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、命令をパイプライン
で処理する計算機で使用される目的プログラムを生成す
るコンパイラ、物理現象のシミュレーションを行なう際
に現れる連立一次方程式を解く並列計算機、及び複数の
演算要素プロセッサを持ち、行列の乗算を少ないメモリ
で行う並列計算機に関する。

【０００２】

【従来の技術】従来より、並列計算機などの計算機に用
いられているコンパイラには、ターゲットアーキテクチ
ャのパイプラインなどの特性を考慮して、命令列ができ
るだけ短時間で実行されるように配置する“命令スケジ
ューリング”と呼ばれる最適化方法がある。図２６〜３
０を参照して、以後の説明で用いる用語と、従来の命令
スケジューリング方法を簡単に説明する。

【０００３】まず初めに、用語の定義と説明をする。

【０００４】パイプライン処理：機械命令の読み出しか
ら実行完了までの過程を、いくつかのステージに分割
し、各ステージを複数の命令に対して並列実行すること
によって、全体の処理を高速化するハードウェア技術。
代表的なパイプラインと命令実行の様子を、図３０
（ａ），（ｂ），（ｃ）に示す。図３０（ａ）は４段パ
イプライン、（ｂ）は５段パイプライン、（ｃ）は６段
パイプラインを表している。

【０００５】基本ブロック：先頭の命令から最後の命令
までが１つづつ順番に実行される一連の命令の並び。す
なわち、ラベルの定義や分岐命令、コール命令を含まな
い命令列。

【０００６】資源：レジスタ、メモリ、プロセッサの状
態、キャリなどのこと。

【０００７】データ依存関係：２つの命令で同一の資源
を、｀定義´−｀参照´、｀参照´−｀定義´、｀定義
´−｀定義´、のいずれかの関係で使用している場合、
その２つの命令はデータ依存関係を持つという。ここで
いう｀定義´とは、値を設定する処理であり、｀参照´
とは演算で用いる処理である。

【０００８】インタロック パイプライン処理で、ある命令の結果が他の命令で使用
されるか、または特定の資源が２つの命令で同時に必要
となる場合には、最初の命令が完了するまで他方の命令
は待たなければならない。このような場合に、ハードウ
ェアが並列実行を一旦停止し、同期制御を行うような状
態。

【０００９】パイプライン処理系を持ち、並列に実行可
能な複数の演算器（加算器３１、乗算器３２、除算器３
３、及びレジスタ３４）を持った図２７（ａ）の計算機
において、図２７（ｂ）のプログラムが図２７（ｃ）の
命令列にコンパイルされたとする。

【００１０】パイプラインは、図２６（ｂ）に示す５つ
のステージからなり、load（メモリからの読み込み）、
store （メモリへの書き込み）、add （加算）、mul
（乗算）の各命令は、共に命令フェッチからレジスタへ
の書き込みまでの各ステージを１クロックで、div （除
算）命令は命令実行ステージ（Ｅステージ）を６クロッ
ク、他のステージを１クロックで実行するとする。

【００１１】パイプライン処理では、命令を１クロック
毎に発行し、パイプラインの各ステージを並列に行うこ
とができるため、命令に依存関係がなければ、除算命令
は１０クロック、それ以外の命令は５クロック後に実行
を完了する。

【００１２】しかし、図２７（ｃ）の命令列では、命令
３が命令１と命令２の演算結果を使用するため、命令３
は命令フェッチ（Ｆステージ）の後、命令１、命令２の
実行結果がレジスタに書き込まれるまでレジスタの読み
込み（Ｒステージ）を開始できない。そのため、ここに
インタロックが発生する。図２８（ａ）で斜線部分がイ
ンタロックの状態を示している。

【００１３】同様に、命令５と命令３、命令４、命令６
と命令５、命令８と命令７、命令９と命令８にもデータ
依存関係があり、先に発行された命令の実行結果が出る
まで、詳しくはＷステージが終了するまで、次の命令の
デコード（Ｒステージ）を開始できず、インタロックが
発生する。

【００１４】図２７（ｃ）の命令列を実行すると図２８
（ａ）のようになり、各命令間で起きているインタロッ
クによって、パイプライン演算部に空き状態が発生し、
全体の実行時間を長くする原因となっている。

【００１５】このような命令列に対してプログラムの意
味を変えないでインタロックの発生回数をできるだけ少
なくする、あるいはパイプライン演算部の空き状態をで
きるだけ少なくし、実行時間を短くするように命令を並
べ変える“命令スケジューリング”と呼ばれるコンパイ
ラの最適化手法がある。

【００１６】従来用いられている代表的な命令スケジュ
ーリング方法の１例を、P.B.Gibbons abd S.S.Muchnic
k, “Efficient Instruction Scheduling for a Pipeli
ned Architecture ”,Proceedings of SIGPLAN Symposi
um on Compiler Construction,Palo Alto,CA,June 198
6,pp.11-16に従って、紹介する。

【００１７】（１） 基本ブロック内の命令に対して、
依存有向グラフを作成する。グラフは、基本ブロック内
の各命令をノードとし、資源の使用に関して依存関係が
ある２つの命令間を’→’で結んで構成する。’ａ→
ｂ’ならば、「ａはｂより前に実行しなければならな
い」ことを示す。

【００１８】（２） 依存有向グラフの根ノード（上の
例では、ａ）を、スケジューリングの際の根ノードの候
補集合におく。

【００１９】（３） 候補集合が空になるまで、以下を
繰り返す。

【００２０】［３−１］ 候補集合の中から最適なノー
ドを、次の規則に従って選択する。

【００２１】・最後にスケジュールされた命令と依存関
係のない命令を選ぶ。

【００２２】・依存グラフ内の命令のいずれかと依存関
係のある命令を選ぶ。

【００２３】・サクセッサ数の多いものを選ぶ。

【００２４】・依存グラフ内の残りの命令に対する最長
パスの長さが長いものを選ぶ。

【００２５】［３−２］ 新しくスケジュールされた命
令を候補集合及び依存グラフから取り除き、依存グラフ
上で新しく根ノードとなった命令を候補集合に加える。

【００２６】ここでサクセッサ数とは、着目する命令
と’→’で結ばれているノードの数を表し、パス長と
は、着目する命令以降のサクセッサを実行し終わるまで
にかかる実行時間のことを表している。例えば、図２８
（ｂ）の依存有向グラフで、命令１のサクセッサ数は
３、命令４のサクセッサ数は２、命令７のパス長は命令
７、命令８、命令９の実行時間を加算した２０クロッ
ク、命令５のパス長は１０クロックである。これは、除
算命令を１０クロック、それ以外を５クロックとしてい
るためである。

【００２７】図２７（ｃ）の命令列は、ラベル定義や分
岐命令を含んでいないので、基本ブロックである。この
命令列に対して（１）の処理を行って得たのが図２８
（ｂ）の依存有向グラフである。この依存グラフをもと
に、上記（２），（３）の処理を行う。

【００２８】最初に根ノードの候補となるのは、パスが
２０クロックで最長の命令１または命令２または命令７
であるが、命令１と命令２はサクセッサ数が３、命令７
は２であるので、命令１または命令２のいずれかが最初
に根ノードとなる。この場合、どちらの命令を先に根ノ
ードとしてもよく、一例として命令１を選択する。命令
１に対し、［３−１］の選択を行うと、パス長が最長の
命令２または命令７が候補になるが、サクセッサ数が最
大の命令２が選択される。

【００２９】命令２に対して同様の選択を行う。この場
合、サクセッサ数が２で最大の命令３、命令４、命令７
が候補になるが、パス長が２０クロックで最長の命令７
が選択される。

【００３０】同様にして命令７以降の命令に対して処理
を行うと、図２９に示すパターンＡ、あるいはパターン
Ｂの命令列ができる。この他、命令２を最初の根ノード
とする場合など、命令の選び方によっていくつかのパタ
ーンができる。

【００３１】パターンＡ，Ｂの命令列は、それぞれ図３
０（ａ），（ｂ）のように実行され実行時間は共に２０
クロックである。命令スケジューリング前の実行時間が
２４クロック図２８（ａ）であったのに対し、従来の命
令スケジューリングによって４クロック短縮されたこと
がわかる。

【００３２】しかしながら、命令の並びとしては、図２
９で示したようにパターンＣのような命令列も考えられ
る。パターンＣの実行のようすを図３０（ｃ）に示す。

【００３３】パターンＡ，パターンＢの実行時間が２０
クロックであるのに対し、パターンＣの命令列の実行時
間は１９クロックで、さらに実行時間が短縮されている
ことが分かる。そのため、パターンＣは、最適な命令ス
ケジューリングであると言える。

【００３４】ここで、図３０の各図においてインタロッ
クの状態を斜線で表すと、命令１の次に命令２を発行し
ても、命令７を発行してもインタロックは発生していな
い。また、命令２、命令７ともに残りの命令のパス長は
２０クロックで最長である。そのため、命令１の次に発
行する命令を決定するのは、命令２、命令７のうち、
［３−１］の処理によってサクセッサ数の多い方とな
り、命令２が先に選択されることになる。つまり、従来
の命令スケジューリング方法では、パターンＣの命令列
が選ばれることはない。

【００３５】一方、このようなコンパイラを備えた並列
計算機では、物理現象を偏微分方程式に基づいてシミュ
レーションすることが盛んに行なわれている。

【００３６】並列計算機で、半導体デバイスシミュレー
ションのように、物理現象を偏微分方程式に基づいてシ
ミュレーションを行なう際は、対象の領域を格子状に分
割し、格子点で偏微分方程式を離散化し、さらに必要な
らば線形化を行ない、連立一次方程式を解くことに帰着
させて解く。このときに、解くべき連立一次方程式の係
数行列は、特殊なスパース行列となる。

【００３７】この連立一次方程式を解く解法として広く
用いられているのは、前処理付き共役勾配法と呼ばれる
反復解法である。この解法については、村田健郎他著、
「スーパーコンピュータ、科学技術計算への適用」（丸
善、１９８５）に記述されている。

【００３８】前処理付き共役勾配法は、ベクトル化また
は並列化による高速化の観点から考えると、高速化のネ
ックになるのは前処理となる不完全ＬＵ分解、および近
似行列Ｌ，Ｕの逆行列を求める処理で、いわゆる前進後
退代入処理となり、逐次的な処理となる。

【００３９】これらの処理を高速に行う方法として、格
子状に分割された物理領域のシミュレーションであらわ
れる行列の特殊性を生かしてベクトル化する方法があ
り、超平面法と呼ばれるものがある。これについて、以
下に説明する。

【００４０】例えば、図９に示す２次元格子についてシ
ミュレーションする場合には、図１０に示すような形を
した下三角行列を係数行列にもつ連立一次方程式を解く
必要がある。図１０において、(1)〜(16)は図９におけ
る格子点１〜１６に相当し、黒丸は非零要素を示してい
る。この黒丸は、例えば格子点５の物理量は、格子点１
の物理量が求まると計算可能であることを意味してい
る。

【００４１】通常の方法では、格子点１から順に番号順
に解を求めるが、超平面法では、１、２、５、３、６、
９、４、７、１０、１３、・・・・のような順序で解を
求める。これは、図９に破線で示した格子点の集合を
(1) 〜(7) の順序で解を求めることに相当する。破線上
にある格子点の解の計算は依存関係がないためベクトル
化が可能となるが、従来はこの計算を１つのベクトルプ
ロセッサで行っていた。また近年、複数の演算要素プロ
セッサ（ＰＥ：Processing Element）を同時に動作さ
せ、高速に処理を行う並列計算機が盛んに開発されてい
る。そのような並列計算機は、例えば図３１のような構
成になっている。

【００４２】図３１において、ＰＥ４１は演算要素プロ
セッサである。ＰＥ４１はアレイコントローラＡＣＵ１
０４からのマイクロコードにしたがって、演算を実行す
る。ＰＥ４１は、ネットワーク１０３によってｍ×ｎの
２次元アレイ状に配置され、ＰＥアレイを構成する。

【００４３】各々のＰＥ４１は、上下左右の互いに隣接
するＰＥ４１と接続されている。また、右端のＰＥ４１
は同じ行の左端のＰＥ４１と、上端のＰＥ４１は同じ列
の下端のＰＥ４１と、それぞれ接続されている。いわゆ
るトーラス状の２次元格子結合である。各ＰＥ４１はデ
ータメモリ４２を持ち、接続されたＰＥ４１とデータ通
信を行うことができる。これにより、他のＰＥ４１のデ
ータメモリ４２に格納されたデータを演算に用いること
ができる。

【００４４】各ＰＥ４１は、ＡＣＵ４４から送られるマ
イクロコードにしたがって、一斉に同じ処理を行う。い
わゆるＳＩＭＤ（Single Instruction Multiple Data S
tream ）形式の並列処理である。ＡＣＵ４４は、ＰＥ４
１の制御機能を付加した情報処理装置で、命令メモリ４
５に格納されている命令を解読し、解読した命令がＰＥ
４１向けの命令ならば、ＰＥ４１向けにマイクロコード
を発生して全ＰＥ４１に転送する。解読した命令が、Ａ
ＣＵ４４自身でのデータ処理に関するものならば、ＡＣ
Ｕ４４自身で処理を行う。

【００４５】ここでは、便宜上ｍ＝ｎと仮定し、ｎ×ｎ
の２次元状に配置されたＰＥアレイで、ｎ×ｎ行列の
積、Ｃ＝Ａ＊Ｂを求める場合を考える。ｉ行目ｊ列目に
位置するＰＥ４１をＰＥ（ｉ，ｊ）で表すものとする
（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−１）。

【００４６】各ＰＥ４１は、初期データとして、行列の
１つの被演算要素を持つようにデータを配置する。すな
わち、ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−
１）は、初期データａ[i][j]、ｂ[i][j]を持つ。４×４
行列の場合に初期データが配置された様子を図３２に、
行列の積を図３３に示す。

【００４７】ＰＥ（ｉ，ｊ）では、行列Ｃの要素ｃ[i]
[j]の演算を受け持ち、全ＰＥ４１で一斉に実行する。
ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−１）で
行う演算は次の通りである。

【００４８】 ｃ[i][j]＝０； ｋ＝０ to ｎ−１まで ｃ[i][j]＝ｃ[i][j]＋ａ[i][k]＊ｂ[k][j]；を繰り 返す。 …（Ｉ） ＰＥ（ｉ，ｊ）はａ[i][j]、ｂ[i][j]以外のデータを持
っていないので、各ＰＥ（ｉ，ｊ）は、ＰＥアレイの同
じ行にあるすべてのＰＥ４１からａ[i][k]（０≦ｋ≦ｎ
−１）を、同じ列にあるすべてのＰＥ４１からｂ[k][j]
（０≦ｋ≦ｎ−１）を転送される必要がある。

【００４９】従来の乗算式は、図３５のフローチャート
のような手順で実行される。

【００５０】（１） まず、行方向にデータを転送す
る。各ＰＥ４１は、一斉に、右隣のＰＥ４１に、自分の
持つａを転送する（ステップ１３１，１３２）。すなわ
ち、ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−
１）は、ａ[i][j]を右隣のＰＥ４１に転送する。そし
て、ａ[i][j-1]を左隣のＰＥ４１から受け取り、メモリ
４２に格納する（ステップ１３３）。

【００５１】（２） 各ＰＥ（ｉ，ｊ）は、（１）で左
隣のＰＥ（ｉ，ｊ−１）から受け取ったａ[i][j-1]を、
一斉に右隣のＰＥ４１に転送する。これによって、ＰＥ
（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−１）は、左
隣のＰＥ４１からａ[i][j-2]を受け取ることになり、こ
れをメモリ４２に格納する。この処理をｎ−１回繰り返
すことによって、ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０
≦ｊ≦ｎ−１）は、ａ[i][0]〜ａ[i][n-1]を受け取るこ
とができる（ステップ１３３〜１３５）。

【００５２】つまり、同じ行にあるｎ台のＰＥ４１のす
べてが、互いに他のｎ−１台のＰＥ４１からデータを転
送されたことになる。これをｎ対ｎ放送と呼ぶことにす
る。これは、すべての行で、並列に実行できる（ステッ
プ１３３〜１３５）。

【００５３】（３） 同様に列方向でデータ転送を行
う。すべてのＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ
≦ｎ−１）が、ｂ[0][j]〜ｂ[n-1][j]を受け取る。つま
り、列方向にｎ対ｎ放送を行う（ステップ１３６〜１４
０）。この時点での、各ＰＥ４１の保持するデータの様
子を図３５に、ｎ＝４の場合について示す。

【００５４】（４） 演算に必要なデータはすべてそろ
ったので、各ＰＥ４１で一斉に（Ｉ）式の計算を行う。
各ＰＥ４１で結果が求まる（ステップ１４１〜１４
５）。

【００５５】２次元格子状に配置されたＰＥアレイで
は、行方向、あるいは列方向へのｎ対ｎ放送を高速に行
うことができる。ｎ台のＰＥ４１のうち１台から、他の
ｎ−１台に同じデータを転送することを１対ｎ放送と呼
ぶことにすると、１対ｎ放送に要する時間は、１回の隣
接ＰＥ間通信時間を１サイクルとして、ｎ−１サイクル
かかる。一方、１回のｎ対ｎ放送に要する時間は、同じ
くｎ−１サイクル終了する。

【００５６】したがって、２次元格子結合のＰＥアレイ
では、１対ｎ放送よりも、ｎ対ｎ放送の方が効率よくデ
ータ転送できることになる。行列乗算全体で、データ転
送に要する時間は、２（ｎ−１）サイクルである。

【００５７】以上のｎ対ｎ放送に基づく行列乗算方法で
は、データ転送が高速に行われる反面、各ＰＥ４１で、
演算に必要な全データをあらかじめ保持する事になる。
行方向でｎ、列方向でｎ個のデータを受け取るため、図
３５で示したように２ｎ個のデータを格納できるメモリ
量が必要となる。すなわち、ｎが大きい場合に多大のメ
モリ量が要求されていた。

【００５８】

【発明が解決しようとする課題】従来の技術で説明した
ように、従来のコンパイラでは、命令によって実行クロ
ック数時間が異なる場合に、先に発行されたクロック数
の多い命令と依存関係のある命令の発行時間が遅れた
り、あるいは、ある命令と依存関係のあるクロック数の
多い命令が後から発行されることで、命令全体の実行時
間を長くしてしまうという問題があった。

【００５９】これは、従来の方法では、個々の命令に対
する情報にもとづいてスケジューリングを行っているた
め、依存関係のある命令全体の実行時間を考慮していな
いためである。

【００６０】一般に、依存関係のある命令間では、先に
発行された命令が完了するまで、次の命令はレジスタ読
み込み以降の処理を開始できないため、それ以前に発行
しても実行時間を短縮することはできないが、従来のコ
ンパイラでは、依存関係のある命令でも、次のノードを
選択する際の候補になる場合があり、選択に無駄があっ
たり、あるいはそのような命令が先に選ばれたために、
もっと有効な命令が発行できなくなるという問題もあっ
た。

【００６１】また、従来のベクトル計算機では、超平面
法を用いてとしても、１つのプロセッサで連立一次方程
式を解いていたので、ベクトルパイプラインで得られる
並列度以上の高速化は原理的にできない。このため、３
次元領域のシミュレーションのように本質的により大き
い並列度があるのにそれを生かしきれないという問題が
あった。並列計算機上での解法としては、ＳＯＲ法など
の並列度の高い方法があるが、数値的な安定性が良くな
い場合があるという問題もあった。

【００６２】さらに、従来の並列計算機では、行列の乗
算を行うための、各ＰＥでの必要なデータを、演算開始
前にすべて保持していたため、各ＰＥのメモリ量が少な
い場合には、演算が実行できないという欠点があった。

【００６３】本発明はこのような問題点を解決するもの
であり、第１の発明の目的は、命令によって実行クロッ
ク数が異なるような場合にも、総実行時間が最も短くな
るような命令列を選択すること、パイプラインの空き状
態をできるだけ小さくし、また依存関係のある命令に対
して、次命令を選択する際の効率を向上させる命令スケ
ジューリングを行うことができるコンパイラを提供する
ことにある。

【００６４】また、第２の発明の目的は、複数個のプロ
セッサを１次元状あるいは２次元状に配置することによ
り、超平面法を並列に計算し、連立一次方程式を高速に
解くことができる並列計算機を提供することにある。

【００６５】さらに、第３の発明は、各ＰＥあたりのメ
モリ量が少ない場合でも、行列の乗算を実行することが
できる並列計算機を提供することにある。

【００６６】

【課題を解決するための手段】上記目的を達成させるた
め、第１の発明は、並列に実行可能な複数の演算器を備
え、命令をパイプラインで処理する計算機で使用される
目的プログラムを生成するコンパイラであって、基本ブ
ロック内の命令列に対し、依存関係のある命令毎に命令
群を構成し、命令群を単位として、パイプラインの空き
状態が小さくなるように命令群の実行順序の入れ換え、
繰り上げ、あるいは繰り下げを行う命令スケジューリン
グ部を備えている。

【００６７】また、第２の発明は、シミュレーションの
対象となる物理領域が２次元の場合には、図６のように
複数のプロセッサが１次元状に配置された並列計算機を
用いる。各プロセッサは、格子点の物理データを計算す
る計算手段と、計算したデータを記憶する記憶手段と、
記憶しているデータを右に隣接するプロセッサへ送出す
る送信手段と、左に隣接するプロセッサから送出されて
きたデータを受信する受信手段とを有している。

【００６８】あるいは第２の発明は、シミュレーション
の対象となる物理領域が３次元の場合には、図７のよう
に複数のプロセッサが２次元状に配置された並列計算機
を用いる。各プロセッサは、格子点のデータを計算する
計算手段と、計算したデータを記憶する記憶手段と、記
憶しているデータを右に隣接するプロセッサおよび下に
隣接するプロセッサへ送出する送信手段と、左に隣接す
るプロセッサおよび上に隣接するプロセッサから送出さ
れてきたデータを受信する受信手段とを有している。

【００６９】さらに、第３の発明は、２次元状に配置さ
れた複数の演算要素プロセッサから構成される並列プロ
セッサで、２つの行列の積を求める並列計算機であっ
て、第１の行列データと第２の行列データを、該２つの
行列で同じ割り付けを行い、該行列の行方向のデータを
持つ演算プロセッサ間で、１つの演算プロセッサから他
の複数の演算プロセッサへデータを放送する手段と、該
行列の列方向のデータを持つ演算プロセッサ間で、１つ
の演算プロセッサから他の複数の演算プロセッサへデー
タを放送する手段と、繰り返し回数を制御する手段と、
該データ放送と演算プロセッサでの演算を制御する制御
手段とを備えている。

【００７０】

【作用】上記手段により、第１の発明では、依存関係の
ある命令同士で命令群を構成し、スケジューリングを命
令群単位で行うことにより、命令によって実行時間が異
なる場合でも最適なスケジューリングを行うことができ
る。

【００７１】また、第１の発明によれば、上記の通り、
命令群を単位としてスケジューリングを行うため、ある
命令と依存関係のある命令の発行時間を固定することが
でき、それによって、依存関係のある命令が効果のない
段階で次の命令の候補に選ばれるという無駄がなくな
り、次命令を選択する際の効率を向上させている。

【００７２】さらに、第１の発明では、並列に実行可能
な命令群を括弧などによって対応づけることで、発行順
序の入れ換えや発行時間の繰り上げの対象となる命令群
を限定するので、命令の選び方に冗長性をなくすことが
できる。

【００７３】一方、第２の発明は、シミュレーション対
象が２次元の場合は、ｙ座標が同一のものを１つのプロ
セッサの記憶手段に保持させる。すなわち格子の１行を
１つのプロセッサに割り当てる。

【００７４】求解の処理手順は、まずプロセッサの受信
手段が左隣のプロセッサからデータを受け取り、受けと
ったデータと自プロセッサで前に計算した変数値、行列
要素、定数ベクトル要素を用いて格子点の変数値を計算
手段で計算する。次に計算結果を記憶手段で記憶すると
共に、右隣のプロセッサに送信手段から送出する。この
処理をすべてのプロセッサで、すべての変数が求められ
るまで繰り返す。

【００７５】ただし、すべてのプロセッサが同時にこの
処理を開始するわけではなく、計算するのに必要なデー
タを左隣のプロセッサから受け取るまでは、待つか、こ
の求解処理とは無関係な処理を行なう。

【００７６】ここで、計算手段で下三角行列を係数にも
つ連立一次方程式 Ｌｘ＝ｂ を解くことを考える。ここで、Ｌは下三角行列、ｘは変
数ベクトル、ｂは定数ベクトルである。

【００７７】このとき、例えば、不完全ＬＵ分解（１，
１）を用いた場合には、 x[i]＝(b[i] - L[i,i-1] * x[i-1] - L[i,i-m] * x[i-
m])/L[i,i] の式により、変数値を求める。不完全ＬＵ分解（１，
２）を用いた場合には、 x[i]＝(b[i] - L[i,i-1] * x[i-1] - L[i,i-m] * x[i-
m]- L[i,i-m+1] * x[i-m+1])/L[i,i] の式により、変数値を求める。

【００７８】あるいは、第２の発明は、シミュレーショ
ン対象が３次元の場合には、受信手段では、左隣のプロ
セッサおよび上隣のプロセッサが送出するデータを受け
取り、保持する。計算手段は、２次元の場合と同様に変
数値を計算し、この結果を記憶手段に記憶する。送信手
段は右隣のプロセッサと下隣のプロセッサに、計算手段
で計算した変数値を送出する。

【００７９】さらに、第３の発明は、前記第１の行列
の、繰り返し回数で指定される１列のデータを保持する
各演算プロセッサが、各列データと同じ行に属するデー
タを保持する複数の演算プロセッサに対して各列データ
を同時並列に転送する。同様に、前記第２の行列の、繰
り返し回数で指定される１行のデータを保持する各演算
プロセッサが、各行データと同じ列に属するデータを保
持する複数の演算プロセッサに対して各行データを同時
並列に転送する。

【００８０】各演算プロセッサで、転送された前記第１
の行列のデータと、転送された前記第２のデータの２つ
の数の積を求め、この積を繰り返し毎に累算する。この
ような操作を、行列の大きさから得られる所定回数だけ
繰り返すことによって行列の積を求めている。

【００８１】

【実施例】以下に、本発明の実施例を図面に基づいて説
明する。

【００８２】第１の発明 まず、第１の発明について図１〜５を用いて説明する。

【００８３】図１は、第１の発明のコンパイラに係わる
一実施例の構成を示すブロック図である。

【００８４】図１に示すコンパイラは、ソースプログラ
ム１を入力するソースプログラム入力部２と、入力され
たソースプログラム１の字句を解析する字句解析部３
と、ソースプログラム１の文法を解釈する構文解析部４
と、ソースプログラム１を中間言語プログラムに変換す
る中間コード生成部５と、第１の発明の中心となる命令
スケジューリング部６と他の最適化を行う最適化部７を
持った中間コード最適化部８と、中間コードを目的プロ
グラム１１に変換するオブジェクトコード生成部９と、
目的プログラム１１を出力して供給する目的プログラム
出力部１０とから構成される。

【００８５】命令スケジューリング部６では、図２に示
すフローチャートに従って、中間コードの命令列のスケ
ジューリングを行う。

【００８６】以下に、図２のフローチャートの各ステッ
プについて説明する。

【００８７】ステップＡ：中間コードで表現された基本
ブロック内の命令に対して、データ依存関係のある命令
毎にグループ（以下単に“命令群”と呼ぶ）を構成し、
並列に実行可能な命令群を対応づける。並列に実行可能
な命令群は、一例として括弧を用いて対応づけることが
できる。

【００８８】一命令だけで独立に演算可能な命令は、１
命令のみで命令群を構成する。

【００８９】ステップＢ：各命令群に対し、最初に発行
される命令から最後に終了する命令までの総実行時間
と、各命令群の最初の命令が発行されてから、他の命令
群（他の命令群に属する命令）を発行することが可能な
時間が何クロック目であるかを算出する。

【００９０】ステップＣ：第１番目の命令群から着目
し、全命令群に対してステップＤ以下の処理を実行す
る。

【００９１】ステップＤ：着目する命令群と並列に実行
可能な（発行順序を入れ換える、あるいは発行時間を繰
り上げることのできる）命令群が、着目する命令群以降
の命令群の中にあるか判断する。判断は括弧の対応をも
とに行う。あればステップＥへ、なければステップＧへ
移行する。

【００９２】ステップＥ：着目する命令群に対し、ステ
ップＤで得た命令群の発行時間を繰り上げることによっ
て、２つの命令群の総実行時間を短縮することができる
ような命令群はあるか判断する。

【００９３】ここで、命令群の発行時間を繰り上げると
は、着目する命令群と並列に実行可能な命令群の発行時
間を、既に発行されている命令群の実行時間の間で他の
命令群を発行することが可能な時間に移動すること、あ
るいは、２つの命令群の発行順序を入れ換えることを表
す。

【００９４】繰り上げによって実行時間が短縮できるよ
うな命令群が１つ以上ある場合には、ステップＦへ移行
する。該当する命令群が存在しない場合には、ステップ
Ｇへ移行する。

【００９５】ステップＦ：ステップＥで得た命令群が２
つ以上ある場合には、命令群のうちで、２つの命令群の
総実行時間を最も短縮できるものを選び、着目する命令
群に対する発行時間を繰り上げ、ステップＧへ移行す
る。

【００９６】ステップＧ：全ての命令群に対して処理を
行ったかを判断し、行った場合は終了し、未処理の命令
群が残っている場合はステップＨへ移行する。

【００９７】図３（ａ）のプログラム、図３（ｂ）の命
令列はそれぞれ、従来例で用いた図２７（ｂ）のプログ
ラム、図２７（ｃ）の命令列と同じである。本実施例
を、図３（ｂ）の命令列を用いて以下に説明する。

【００９８】命令スケジューリング部６では、図３
（ｂ）の命令列に対し、図２のフローチャートに従って
最適化を行う。図３（ｂ）の命令列が命令スケジューリ
ング部６によって最適化されていく様子を、図２のフロ
ーチャートに従って以下に説明する。

【００９９】（１） 図３（ｂ）の命令列に対し、依存
関係のある命令毎に命令群を構成し、並列に実行可能な
命令群を対応づける（ステップＡ）。１命令だけで独立
に演算可能な命令は、１命令のみで命令群を構成する。
一例として、並列に実行可能な命令群を’（）’で対応
づけた図を図４（ａ）に、各命令群に番号付けした図を
図４（ｂ）に示す。並列に実行可能な命令群は、それぞ
れ’（）’の対応で表現されている。

【０１００】図４（ａ）において、１命令だけ
で’（）’に囲まれてる命令１、命令２、命令４、命令
７は、それぞれ１命令だけで独立に実行可能な命令を表
している。また、命令１、命令２、命令３の３命令で１
つの命令群（命令群３）を構成し、命令群３と命令４，
５で１つの命令群（命令群５）を構成していることを表
している。同様に命令群６、命令群８、命令群９も複数
の依存関係のある命令から構成されている。

【０１０１】（２） 各命令群に対し、最初に発行され
る命令から最後に終了する命令までの総実行時間と、各
命令群の最初の命令が発行されてから、他の命令群（他
の命令群に属する命令）を発行することが可能な時間が
何クロック目であるかを算出する（ステップＢ）。各命
令群の総実行時間と次命令群発行可能時間を図４（ｃ）
に示す。

【０１０２】図４（ｃ）において、例えば命令群３は、
図２８（ａ）における命令３のＦステージを５クロック
目まで繰り下げることができるので、１，５クロック目
以外が次命令群発行可能時間であることを示している。

【０１０３】（３） 命令群１に着目し、ステップＤ以
降の処理を行う。

【０１０４】（４） 命令群１と並列に実行可能な命令
群を、命令群２以降の命令群の中から探す（ステップ
Ｄ）。ここでは命令群２が該当し、ステップＥへ移行す
る。

【０１０５】（５） 命令群１に対して命令群２の発行
時間を繰り上げても、２つの命令の総実行時間は６クロ
ックで変化がない。発行時間を繰り上げることで実行時
間を短縮することのできる命令群はないので（ステップ
Ｅ）、ステップＧへ移行する。 （６） 命令群２以降の処理が残っているので、ステッ
プＨへ移行し、命令群２に着目する。

【０１０６】（７） 命令群２と並列に実行可能な命令
群を、命令群３以降の命令群の中から探す（ステップ
Ｄ）。括弧の対応から、命令群２と並列に実行可能な命
令群は、命令群１のみであるが、ここでは命令群１は入
れ換えの対象ではないため、ステップＧ、ステップＨへ
移行する。

【０１０７】（８） 命令群３と並列に実行可能な命令
群を、命令群４以降の命令群の中から探す（ステップ
Ｄ）。ここでは、命令群４が該当し、ステップＥへ移行
する。

【０１０８】（９） この場合、命令群３に対し、命令
群４の発行時間を繰り上げても、命令群３と命令群４の
総実行時間は変化しない。しかし、後から命令群９をス
ケジューリングする際に、命令３のＦステージを３クロ
ック繰り下げ、命令群９を４クロック繰り上げると、命
令群９の中の命令８の発行時間が命令４の発行時間とか
ち合ってしまう。

【０１０９】命令８は、命令７と依存関係があるので、
発行を早めることができないため、命令４の発行時間を
１クロック早めることで、命令群９の実行時間を短縮す
ることができる。ステップＦへ移行する。

【０１１０】（１０） 命令４の発行時間を１クロック
繰り上げ、命令３の発行時間を３クロックは繰り下げて
ステップＧ，Ｈへ移行する。

【０１１１】（１１） 命令群４と並列に実行可能な命
令群は、命令群３のみであるので、ここでは対象となら
ない。ステップＧ，Ｈへ移行する。

【０１１２】（１２） 命令群５と並列に実行可能な命
令群はないため、ステップＧ，Ｈへ移行する。

【０１１３】（１３） 命令群６と並列に実行可能な命
令群は、命令群９である。該当する命令群があるので、
ステップＥへ移行する。

【０１１４】（１４） 命令群６に対し、命令群９の発
行時間を繰り上げると、２つの命令群の総実行時間は短
縮されるので、ステップＦへ移行する。

【０１１５】（１５） ステップＦでは、先に発行され
た命令群に対して、後続の命令の発行時間を繰り上げる
場合と、２つの命令の発行時間を入れ換える場合のどち
らか、より総実行時間を短縮できる方を選択する。

【０１１６】命令群６を先に発行し、命令群９の発行時
間を繰り上げるよりも、２つの命令群の発行時間を入れ
換える方が、より２つの命令群の総実行時間を短縮する
ことができるため、このステップでは、２つの命令群の
発行時間を入れ換える。ステップＧ，Ｈへ移行する。

【０１１７】（１６） 命令群７と並列に実行可能な命
令群はないので、ステップＧ，Ｈへ移行する。

【０１１８】（１７） 同様に命令群８と並列に実行可
能な命令群もないので、ステップＧ，Ｈへ移行する。

【０１１９】（１８） 命令群９と並列に実行可能な命
令群は、命令群６であるが、ここでは対象とならないた
め、ステップＧへ移行し、全命令群に対して処理を行っ
たので終了する。

【０１２０】以上の処理により、図３（ｂ）の命令列は
図５（ａ）の命令列に変換され、実行は図５（ｂ）にな
り、命令列の総実行時間は、命令スケジューリングを行
う前には２４クロックであったのに対し、１９クロック
に短縮され、従来の命令スケジューリング方法では２０
クロックであったのに比べても１クロック短縮すること
ができる。

【０１２１】第２の発明 次に、第２の発明について図６〜１６を用いて説明す
る。

【０１２２】まず、シミュレーションの対象となる領域
を４×４の２次元の格子状に分割し、不完全ＬＵ分解
（１，１）を適用した場合について説明する。

【０１２３】不完全ＬＵ分解（１，１）で得られる下三
角行列は、図１０に示すような形となる。この下三角行
列を係数行列にもつ連立一次方程式を解く場合、図１１
に示すような変数求解の依存関係が得られる。図１１に
おいて、ｉ→ｊは、ｊを計算するためには、ｉの値が必
要であることを示している。

【０１２４】図６は、この連立一次方程式を解くための
並列計算機である。この並列計算機は、格子の行数分の
プロセッサ（１）〜（４）が１次元状に配置されてい
る。第ｉプロセッサは、第（ｉ＋１）プロセッサへデー
タを転送することが可能となっている。

【０１２５】各プロセッサは、自分自身のローカルな記
憶手段となるメモリ１３と、図示していないが受信手
段、計算手段、及び送信手段をもつ。

【０１２６】この計算機上で、上述の連立一次方程式を
解くためには、まず、各格子点のデータを各格子点の計
算を担当するプロセッサのローカルメモリ１３に配置す
る。第１プロセッサ(1) には、第１行の格子点（１〜
４）のデータを配置する。第２プロセッサ(2) には、第
２行の格子点（５〜８）のデータを配置する。第３、第
４のプロセッサ(3),(4) についても同様に、第３行の格
子点（９〜１２）、第４行の格子点（１３〜１６）を配
置する。

【０１２７】図８は、データが配置された並列計算機の
大まかな動作を表すフローチャートである。まずプロセ
ッサの受信手段が隣接プロセッサからデータを受け取り
（ステップ９１）、受けとったデータを用いて格子点の
変数値を計算手段で計算する（ステップ９２）。次に計
算結果を記憶手段で記憶すると共に、隣接プロセッサに
送信手段から送出する（ステップ９３）。この処理を、
このプロセッサが担当するすべての変数が計算されるま
で繰り返す（ステップ９４）。

【０１２８】以下に、各プロセッサの具体的な動作を説
明する。

【０１２９】まず、第１段階では、第１プロセッサで、
第１格子点の変数を計算する。第２〜４プロセッサでは
何もしない。計算が終了した後、第１格子点の変数値を
第２プロセッサへ転送する。

【０１３０】第２段階では、第１プロセッサで、第１段
階で計算された変数値を用いて第２格子点の変数を計算
する。このとき同時に、第２プロセッサでは、第５格子
点の変数を計算する。このとき、第１段階で第１プロセ
ッサから転送されてきた第１格子点の変数値を用いる。
計算が終了した後、第１のプロセッサから、第２格子点
の変数の値を第２プロセッサへ、第２プロセッサから第
５格子点の変数の値を第３プロセッサへそれぞれ転送す
る。

【０１３１】第３段階では、第１プロセッサで、第２段
階で計算された変数値を用いて第３格子点の変数を計算
する。同時に、第２プロセッサでは第６格子点の変数、
第３プロセッサでは第９格子点の変数をそれぞれ計算す
る。それぞれのプロセッサで計算された格子点の変数の
値は、それぞれの隣接するプロセッサへ転送する。

【０１３２】以降、同様の処理を、第７段階で、第１６
格子点の変数が計算されるまで繰り返す。

【０１３３】この計算の結果、第ｉ行の格子の変数の値
は、第ｉプロセッサのローカルメモリ１３に得られる。

【０１３４】このときの計算の様子は、図１１から分か
るように、同一行に横方向に並んでいる格子点は、１つ
のプロセッサに割り当てられ、同一列に縦方向に並んで
いる格子点は、各プロセッサにおいて同時に計算されて
いる。全体的には、左側の列の格子点から計算が開始さ
れる。

【０１３５】各列の上に示した数字(1) 〜(7) は、その
列上の格子点の変数が第何段階に計算が行なわれるかを
示している。プロセッサ間のデータ転送は、斜め方向の
矢印がある格子点間で行なわれている。横方向の矢印
は、プロセッサ間のデータ転送を表しているのではな
い。

【０１３６】データの転送に要する時間が無視できると
すると、１つのプロセッサだけで計算した場合に比べ、
７／１６＝０．４４倍の計算時間ですむことになる。

【０１３７】次に、同じ２次元領域について、不完全Ｌ
Ｕ分解（１，２）を適用した場合について説明する。

【０１３８】不完全ＬＵ分解（１，２）を用いた場合の
下三角行列は、図１２のようになる。この行列を係数に
もつ連立一次方程式を解くために用いる並列計算機は、
不完全ＬＵ分解（１，１）の場合と同じである。各格子
点のデータも同じように配置する。解の依存関係は、図
１３のようになる。

【０１３９】まず、第１段階では、第１プロセッサで、
第１格子点の変数を計算する。このとき第２〜４プロセ
ッサでは何もしない。計算が終了した後、第１格子点の
変数値を第２プロセッサへ転送し、保持する。

【０１４０】第２段階では、第１プロセッサで、第１段
階で計算された変数値を用いて第２格子点の変数を計算
する。このとき第２〜４プロセッサは何もしない。計算
が終了した後、計算した第２格子点の変数値を第２のプ
ロセッサへ転送し、保持する。

【０１４１】第３段階では、第１プロセッサで、第２段
階で計算された変数値を用いて第３格子点の変数を計算
する。これと同時に第２プロセッサでは、第５格子点の
変数を計算する。このとき、第１段階及び第２段階で計
算された第１及び第２格子点の変数値を用いる。

【０１４２】第３、４プロセッサは何もしない。計算が
終了した後、第１プロセッサは、第３格子点の変数値を
第２プロセッサへ転送し、保持する。第２プロセッサ
は、第５格子点の変数値を第３プロセッサへ転送し、保
持する。

【０１４３】以降、同様の処理を、第４プロセッサで第
１６格子点の変数が計算されるまで繰り返す。

【０１４４】この計算の結果、不完全ＬＵ分解（１，
１）の場合と同様に、第ｉ行の格子の変数の値は、第ｉ
プロセッサのローカルメモリ１３に得られる。

【０１４５】このときの計算の様子は、図１３から分か
るように、同一行に横方向に並んでいる格子点は、１つ
のプロセッサに割り当てられ、同一列に縦方向に並んで
いる格子点は、各プロセッサにおいて同時に計算されて
いる。全体的には、左側の列の格子点から計算が開始さ
れる。

【０１４６】各列の上に示した数字(1) 〜(10)は、その
列上の格子点の変数が第何段階に計算が行なわれるかを
示している。プロセッサ間のデータ転送は、斜め方向の
矢印がある格子点間で行なわれている。１つの格子点に
対し２本の矢印が出ているが、実際には、プロセッサ間
データ転送を２回やるわけではなく、格子点の計算結果
が得られた直後にデータ転送を行ない、転送先のプロセ
ッサで記憶しておけば、１回のデータ転送ですむ。横方
向の矢印は、プロセッサ間のデータ転送を表しているの
ではない。

【０１４７】データの転送に要する時間が無視できると
すると、１つのプロセッサだけで計算した場合に比べ、
１０／１６＝０．６３倍の計算時間ですむことになる。

【０１４８】次に、シミュレーション領域が図１４に示
すような３×３×３の大きさの３次元領域である場合
に、不完全ＬＵ分解（１，１，１）を適用した場合につ
いて説明する。不完全ＬＵ分解（１，１，１）により得
られる下三角行列は、図１５のようになる。この下三角
行列を係数行列にもつ連立一次方程式を解く場合、図１
６のような変数求解の依存関係となる。

【０１４９】図７は、この連立一次方程式を解くための
並列計算機である。この並列計算機は、３×３個のプロ
セッサ（１，１）〜（３，３）が２次元状に配置されて
いる。（ｉ，ｊ）プロセッサは、（ｉ＋１，ｊ）プロセ
ッサおよび（ｉ，ｊ＋１）プロセッサの２つの隣接プロ
セッサへデータ転送することが可能となっている。ま
た、図示していないが、各プロセッサは、自分自身のロ
ーカルな記憶手段となるメモリ、受信手段、計算手段、
及び送信手段をもっている。

【０１５０】この計算機上で、上述の連立一次方程式を
解くためには、次のように各格子点のデータを各プロセ
ッサのローカルメモリに配置する。すなわち、ｙ座標、
ｚ座標が同一の３つの格子点のデータを１つのプロセッ
サに配置する。例えば、１〜３の格子点のデータは、
（１，１）プロセッサに配置され、４〜６の格子点のデ
ータは（１，２）プロセッサに配置する。さらに、１０
〜１２の格子点のデータは（２，１）プロセッサに配置
する。

【０１５１】まず、第１段階では、（１，１）プロセッ
サで第１格子点の変数を計算する。このとき他のプロセ
ッサでは何もしない。計算終了後、計算された第１格子
点の変数値を（１，２）プロセッサ、（２，１）プロセ
ッサの２つの隣接プロセッサへ転送する。

【０１５２】第２段階では、（１，１）プロセッサで
は、第２の格子点の変数を計算し、（１，２）プロセッ
サでは、第４の格子点の変数を計算し、（２，１）プロ
セッサでは、第１０の格子点の変数を計算する。

【０１５３】計算終了後、それぞれのプロセッサで計算
した格子点の変数値をそれぞれのプロセッサの右および
下の隣接プロセッサへ転送する。すなわち、（１，１）
プロセッサは、（１，２）および（２，１）プロセッサ
へ、（１，２）プロセッサは、（１，３）および（２，
２）プロセッサへ、（２，１）プロセッサは、（２，
２）および（３，１）プロセッサへ、計算結果を転送す
る。

【０１５４】以降、同様の処理を、第７段階で第２７格
子点の変数が計算されるまで繰り返す。

【０１５５】以上の計算の結果、各格子点の変数値は、
各格子点のデータが配置されたプロセッサ上に得られ
る。

【０１５６】このときの計算の様子は、図１６から分か
るように、同一行に横方向に並んでいる格子点は、１つ
のプロセッサに割り当てられ、同一列に縦方向に並んで
いる格子点は、各プロセッサにおいて同時に計算されて
いる。全体的には、左側の列の格子点から計算が開始さ
れる。

【０１５７】各列の上に示した数字(1) 〜(7) は、その
列上の格子点の変数が第何段階に計算が行なわれるかを
示している。プロセッサ間のデータ転送は、斜め方向の
矢印がある格子点間で行なわれている。横方向の矢印
は、プロセッサ間のデータ転送を表しているのではな
い。

【０１５８】データ転送に要する時間が無視できるとす
ると、１つのプロセッサだけで計算した場合に比べ、７
／２７＝０．２６倍の計算時間ですむことになる。４０
×４０×４０の場合であれば、４０×４０個のプロセッ
サで、１１８／６４０００＝０．００１８倍の計算時間
ですむことになる。

【０１５９】なお、第２の発明は、半導体デバイスシミ
ュレーションで用いられる、いわゆるカップル法のよう
に各行列要素が小行列となる場合があるが、この場合で
も同様に実施可能である。

【０１６０】第３の発明 最後に、第３の発明について図１７〜２５を参照しなが
ら説明する。

【０１６１】図１７は、第３の発明の並列計算機に係わ
る一実施例の構成を示すブロック図である。

【０１６２】同図において、第３の発明の並列計算機
は、大きく、演算制御部２１と演算実行部２２とから構
成される。演算制御部２１と、演算実行部２２は、デー
タバス２３で接続される。演算制御部２１は、命令メモ
リ２４と接続される。命令メモリ２４には、行列の乗算
手順を記述したプログラムが格納されている。

【０１６３】演算制御部２１は、命令メモリ２４から命
令を読み込み、解読する。読み込んだ命令が、演算実行
部２２での演算を指示するものであれば、ＰＥ向けのマ
イクロコードに展開し、データバス２３を介して、演算
実行部２２に転送する。

【０１６４】読み込んだ命令が、ループ変数の更新等、
演算制御部２１内での処理を指示するものであれば、演
算制御部２１内で処理を行う。

【０１６５】演算実行部２２は、複数の演算要素プロセ
ッサ（Processing Element）ＰＥ２５から構成される。
ＰＥ２５は、各自でデータメモリ２６を持ち、データメ
モリ２６のデータに対して処理を行う。ＰＥ２５は互い
にネットワーク２７で結合されており、他のＰＥ２５と
データ通信を行うことができる。ＰＥ２５は、演算制御
部２１から放送されるマイクロコードにしたがって動作
する。

【０１６６】ネットワーク２７は、各ＰＥ２５を結合
し、ＰＥ間通信を可能にするもので、その形態として
は、例えば図１８に示すような２次元格子結合や、図１
９に示すｘ−ｙバス結合、さらには図示していないがハ
イパー・キューブ結合等がよく知られている。

【０１６７】以下では、図１８の２次元格子結合を例に
とって説明を続けるが、ｘ−ｙバス結合や、ハイパーキ
ューブ結合等、その他のネットワーク形態についても適
用可能である。

【０１６８】演算制御部２１は、演算実行部２２の各Ｐ
Ｅ２５に対して、次のような制御を行うことができる。

【０１６９】（１） すべてのＰＥ２５が、一斉に同じ
処理を行う。

【０１７０】（２） 少なくとも、２次元上に配置され
たＰＥ２５の、一行全てあるいは一列全てのＰＥ２５を
選択して、選択されたＰＥ２５のみ、一斉に同じ処理を
行う。以上で説明した並列計算機を用いて、２つの行列
の乗算を行う手順を説明する。

【０１７１】ここでは、ｎ×ｎの２次元状に配置された
ＰＥアレイ上で、ｎ×ｎ行列の積、Ｃ＝Ａ＊Ｂを求める
場合を考える。ｉ行目ｊ列目に位置するＰＥ２５をＰＥ
（ｉ，ｊ）で表すものとする（０≦ｉ≦ｎ−１，０≦ｊ
≦ｎ−１）。各ＰＥ２５は、初期データとして、行列
Ａ，Ｂのそれぞれ１つの要素を持つようにデータを配置
する。

【０１７２】すなわち、ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−
１，０≦ｊ≦ｎ−１）は、初期データａ[i][j]、ｂ[i]
[j]を持つ。ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ
≦ｎ−１）では、それぞれ行列Ｃの要素ｃ[i][j]の演算
を受け持ち、全ＰＥ２５で一斉に演算を行う。ＰＥ
（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−１）で行う
演算は、次の通りである。

【０１７３】 ｃ[i][j]＝０； ｋ＝０ to ｎ−１まで ｃ[i][j]＝ｃ[i][j]＋ａ[i][k]＊ｂ[k][j]；を繰り 返す。 …（Ｉ） 乗算手順１を図２０のフローチャートにしたがって説明
する。

【０１７４】（１） 各ＰＥ（ｉ，ｊ）で、ｃ[i][j]＝
０として、ｃを初期化する（ステップ１０１）。

【０１７５】（２） ＰＥ（ｉ，ｊ）で１回目に行う演
算は、 ｃ[i][j]＝ｃ[i][j]＋ａ[i][0]＊ｂ[0][j]； …（II） である。

【０１７６】ここで、ＰＥ（ｉ，ｊ）（１≦ｉ≦ｎ−
１，１≦ｊ≦ｎ−１）では、ａ[i][0]とｂ[0][j]は自分
のデータメモリ２６には存在しないため、データ転送が
必要である。ａ[i][0]は、第１列目のＰＥ（ｉ，０）
（０≦ｉ≦ｎ−１）が持ち、ｂ[0][j]は、ＰＥ（０，
ｊ）（１≦ｊ≦ｎ−１）が持つ。

【０１７７】まず、第１列にあるＰＥ（ｉ，０）（Ｏ≦
ｉ≦ｎ−１）は、同じ行に存在する他のＰＥ（ｉ，１）
〜ＰＥ（ｉ，ｎ−１）に、ａ[i][0]を転送する。これは
１対ｎ放送の形式になる。

【０１７８】ａ[i][0]の１対ｎ放送は、ＰＥ（ｉ，０）
が、まず隣接するＰＥ（ｉ，１）にａ[i][0]を転送し、
次にＰＥ（ｉ，１）がＰＥ（ｉ，２）にａ［ｉ］［０］
を転送し、……、最後にＰ（ｉ，ｎ−１）、ａ[i][0]が
転送される、という形式で、放送されるデータａ[i][0]
が、ＰＥ間でシフトされることによって、ｎ−１サイク
ルで実行できる。

【０１７９】なお、この行方向への１対ｎ放送は、すべ
ての行（０≦ｉ≦ｎ−１）で、同時に実行できる（ステ
ップ１０２〜１０３）。図２１に、ｎ＝４の場合の行方
向への１対ｎ放送の様子を示す。

【０１８０】（３） 次にｂ[0][j]を転送するために、
第１行にあるＰＥ[0][j]（０≦ｊ≦ｎ−１）は同じ列に
存在する他のＰＥ[0][j]〜ＰＥ[n-1][j]に、同様に１対
ｎ放送する（ステップ１０４）。この１対ｎ放送は、す
べての列で同時に実行できる。図２２にｎ＝４の場合の
列方向への１対ｎ放送の様子を示す。

【０１８１】（４） 以上の２回の１対ｎ放送によっ
て、各ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−
１）は、ａ[i][0]とｂ[0][j]を取得したので、（II）式
の一回目の演算を行う（ステップ１０５）。

【０１８２】（５） ２回目の演算は、 ｃ[i][j]＝ｃ[i][j]＋ａ[i][1]＊ｂ[1][j]； … (III) である。

【０１８３】すなわち、ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−
１，０≦ｊ≦ｎ−１）は、ａ[i][1]とｂ[1][j]とがデー
タ転送されることが必要である。このためには、第２列
目のＰＥ（ｉ，１）（０≦ｉ≦ｎ−１）が、ａ[i][1]を
同じ行の他のＰＥ２５に１対ｎ放送を行い、次に、第２
行目のＰＥ（１，ｊ）（０≦ｊ≦ｎ−１）が、ｂ[1][j]
を同じ列の他のＰＥ２５に１対ｎ放送する。

【０１８４】図２３，２４に、ｎ＝４の場合の、第２列
目および第２行目の列方向及び行方向への１対ｎ放送の
様子を示す。各ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦
ｊ≦ｎ−１）では、(III）式の演算を行う。

【０１８５】（６） 以上をｎ回繰り返すことによっ
て、各ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−
１）で、それぞれ行列の積であるｃ[i][j]が求まる（ス
テップ１０３〜１０７）。

【０１８６】以上の乗算手順１によれば、演算を行うた
びに、各ＰＥ２５で結果が累算されるので、あらかじ
め、全データを持つ必要がなく、少ないメモリ量で行列
の乗算が実行できる。すなわち、各ＰＥ２５で必要なメ
モリ量は、初期データ２つ、１回の繰り返しで転送され
るデータ２つ、解となるｃのための１つで合計５データ
分のメモリ２６があればよく、ｎの値に依存しない。す
なわちｎの値が大きくなっても、各ＰＥ２５のメモリ量
は少なくて済む。

【０１８７】但し、この乗算手順１は、データ放送に要
する時間が従来方式よりも遅くなる。本方式では、１回
の繰り返しで、行、列方向の１対ｎ放送をそれぞれ一回
ずつ行う。１対ｎ放送は、ｎ−１サイクルかかるので、
行列乗算全体のデータ転送時間は２＊ｎ＊（ｎ−１）サ
イクルとなる。一方従来方式では、データ転送は、２＊
（ｎ−１）サイクルであり、データ転送時間についは、
ｎが大きくなるほど不利になる。

【０１８８】そこで、次のような解決策が考えられる。
行方向に対しては、従来の方法通り、あらかじめｎ対ｎ
放送によって、演算に必要なデータをすべて保持してお
く。列方向に対しては、前述した乗算手順１にしたがっ
て１対ｎ放送を繰り返す。これを乗算手順２として図２
５のフローチャートにしたがって説明する。

【０１８９】（１） まず、行方向に関して、必要なデ
ータをすべて取得する。すなわちＰＥ（ｉ，ｊ）（０≦
ｉ≦ｎ−１，０≦ｊ≦ｎ−１）は、ａ[i][0]〜ａ[i][n-
1]を、同じ行の他のＰＥ２５から取得する。このための
方法は、従来の方法と同じである。すなわち、まず、各
ＰＥ２５一斉に、右隣のＰＥ２５に自分のデータを転送
する（ステップ１１１〜１１３）。

【０１９０】次に各ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−１，
０≦ｊ≦ｎ−１）は、左隣のＰＥ（ｉ，ｊ−１）から受
けったａ[i][j-1]を、右隣のＰＥ２５に転送する。これ
によって、ＰＥ（ｉ，ｊ）は、左隣のＰＥ２５からａ
[i][j-2]を受け取ることになり、これをメモリ２６に格
納する。

【０１９１】この処理をｎ−１回繰り返すことによっ
て、ＰＥ（ｉ，ｊ）は、ａ[i][0]〜ａ[i][n-1]を受け取
ることができる（ステップ１１４〜１１６）。以上によ
り、行方向の必要なデータは、すべて所得できる。この
ｎ対ｎ放送は、各行で並列に実行できる。放送に要する
時間はｎ−１サイクルである。

【０１９２】（２） 以下では、列方向のデータ転送
と、演算とを繰り返して行う。１回目の演算で必要なデ
ータとして、１行目のＰＥ（０，ｊ）（０≦ｊ≦ｎ−
１）が、列方向のＰＥ２５にｂ[0][j]を１対ｎ放送す
る。１対ｎ放送は、まず隣接するＰＥ（１，ｊ）にｂ
[0][j]を転送し、次にＰＥ（１，ｊ）がＰＥ（２，ｊ）
にｂ[0][j]を転送し……、最後にＰＥ（ｎ−１，ｊ）に
ｂ[0][j]が転送される、という形式で、放送されるデー
タｂ[0][j]が、ＰＥ間でシフトされることによって、ｎ
−１サイクルで実行できる（ステップ１１７〜１１
８）。

【０１９３】（３） 各ＰＥ（ｉ，ｊ）（０≦ｉ≦ｎ−
１，０≦ｊ≦ｎ−１）で（II）式の演算を行う（ステッ
プ１１９）。

【０１９４】（４） ２回目の演算に必要なデータとし
て、２行目のＰＥ（１，ｊ）（０≦ｊ≦ｎ−１）が、列
方向のＰＥ２５にｂ[1][j]を１対ｎ放送する（ステップ
１２０〜１１８）。

【０１９５】（５） ２回目の演算として、 (III)式を
計算する（ステップ１１９）。

【０１９６】（６） 以上を繰り返すことによって、行
列の乗算を行うことができる（ステップ１１８〜１２
１）。

【０１９７】ここでは、行方向にあらかじめｎ対ｎ放送
ですべてのデータを保持し、列方向の１対ｎ放送と演算
を繰り返す方法を示したが、列方向に関してあらかじめ
ｎ対ｎ放送ですべてのデータを保持する場合も、全く同
様に実行できる。

【０１９８】この乗算手順２では、各ＰＥ２５で演算に
必要なメモリ量は、行あるいは列のどちらか一方の全デ
ータとなるのでｎ個でよく、従来方式の1/2 ですむ。ま
た、データ転送時間は、最初の行方向のｎ対ｎ放送はｎ
−１サイクル、その後の列方向の１対ｎ放送がｎ−１サ
イクルでｎ回なので、総転送サイクル数は、ｎ＊（ｎ−
１）＋ｎ−１サイクルとなり、行、列両方向に１対ｎ放
送を行う場合の1/2 に短縮される。

【０１９９】さらに、図１９で示したように、行方向、
列方向のＰＥ２５に対して、１サイクルで行方向の全て
のＰＥあるいは、列方向の全てのＰＥに放送が行えるよ
うな、ｘ−ｙバス結合方式を考えることもできる。ｘ−
ｙバス結合は、同じ行に存在するＰＥ（ｉ，０）〜ＰＥ
（ｉ，ｎ−１）（０≦ｉ≦ｎ−１）がバス結合され、ま
た、同じ列に存在するＰＥ（０，ｊ）〜ＰＥ（ｎ−１，
ｊ）（０≦ｊ≦ｎ−１）がバス結合される結合方式であ
る。

【０２００】このｘ−ｙバス結合方式を用いて行列乗算
を行う手順は、乗算手順１，２で説明した１対ｎ放送を
除いては、上述した方法をそのまま適用できる。データ
放送は、放送するＰＥ２５が放送データをバスに読み出
し、残りのＰＥ２５が、バスからデータを読み込むこと
で実現できるので、１回のデータ放送に要する時間は１
サイクルである。

【０２０１】行列乗算全体としては、データ転送に要す
る時間は２＊ｎサイクルとなり、２次元格子結合方式で
従来の乗算方式を用いた場合とほぼ同じ転送時間に迎え
られる。もちろん、演算に必要なメモリ量は、従来方式
と比較して、極めて少なくて済む。

【０２０２】以上詳細にに述べたように、第３の発明の
並列計算機は、従来方式と比較して、ＰＥ当りの使用メ
モリ量が著しく削減できるため、ＰＥ当りのメモリ量が
少なくても乗算を実行できる。データ転送時間は、２次
元格子結合の倍は増加するが、ｘ−ｙバス結合等を導入
することによって、データ転送時間を従来方式と同等に
押えることかできる。

【０２０３】ここで用いた演算式（Ｉ）は、各繰り返し
において、すべてのＰＥ２５で同じ演算を行う。また、
データ転送も、行、あるいは列単位で同じ処理を行うの
で、ＳＩＭＤ計算機に適合した乗算方法であるといえ
る。しかし、ＭＩＭＤ（Multiple Instruction Multipl
e Data Stream ）型並列計算機でももちろん実行可能で
ある。このＭＩＭＤ計算機は、各ＰＥ２５が命令メモ
リ、命令デコーダ部を持ち、各ＰＥ２５で異なった処理
を行えるのが特徴であるが、この第３の発明の乗算方法
も実行可能である。

【０２０４】

【発明の効果】第１の発明によれば、依存関係のある命
令ごとに命令群を構成し、命令群を１つの単位として命
令スケジューリングを行うことで、命令によって実行時
間の異なる場合でも、実行時間が最も短縮されるような
命令列にコンパイルすることができる。また、命令群を
単位としてスケジューリングを行うため、スケジューリ
ングを効率よく行うことができるようになる。

【０２０５】また、第２の発明の並列計算機によれば、
１次元状または２次元状に配置された複数プロセッサを
もつ並列計算機上で、連立一次方程式の求解を数値的特
性を損うことなく、隣接するプロセッサ間のみデータ通
信を行なえばよいため、効率よく高速に実行することが
可能となる。

【０２０６】さらに、第３の発明の並列計算機によれ
ば、各演算要素プロセッサ当たりのメモリ量が少なくて
も、行列の乗算が実行可能である。大規模行列乗算を、
多数の演算要素プロセッサで構成し、特に演算要素プロ
セッサ当たりのメモリ量に制限がある場合に効果的であ
る。

【図面の簡単な説明】

【図１】第１の発明のコンパイラの構成を示すブロック
図。

【図２】図１で示した命令スケジューリング部のフロー
チャート。

【図３】第１の発明のコンパイラによるスケジューリン
グ方法を説明する際に用いられた、ソースプログラム及
びスケジューリング前の命令列。

【図４】第１の発明におけるスケジューリングを説明す
るための命令群構成及び各命令群の実行時間と次命令発
行可能時間一覧表。

【図５】第１の発明による命令スケジューリング後の命
令列及び実行の様子。

【図６】第２の発明における２次元領域をシミュレーシ
ョンする際の並列計算機の構成図。

【図７】第２の発明における３次元領域をシミュレーシ
ョンする際の並列計算機の構成図。

【図８】第２の発明における並列計算機の動作を表すフ
ローチャート。

【図９】物理領域を２次元状に分割したときの格子点。

【図１０】２次元領域の問題で不完全ＬＵ分解（１，
１）をして得られる下三角行列Ｌ。

【図１１】２次元領域の問題で不完全ＬＵ分解（１，
１）を用いた場合の、解の計算の依存関係を表す図。

【図１２】２次元領域の問題で不完全ＬＵ分解（１，
２）をして得られる下三角行列Ｌ。

【図１３】２次元領域の問題で不完全ＬＵ分解（１，
２）を用いた場合の、解の計算の依存関係を表す図。

【図１４】物理領域を３次元状に分割したときの格子
点。

【図１５】３次元領域の問題で不完全ＬＵ分解（１，
１，１）をして得られる下三角行列Ｌ。

【図１６】３次元領域の問題で不完全ＬＵ分解（１，
１，１）を用いた場合の、解の計算の依存関係を表す
図。

【図１７】第３の発明の並列計算機に係わる一実施例の
構成を示すブロック図。

【図１８】図１７で示した演算実行部の一構成例。

【図１９】図１８と異なる演算実行部の一構成例。

【図２０】第３の発明における行列乗算手順を示すフロ
ーチャート。

【図２１】第３の発明における行方向のデータ放送の様
子を示す図。

【図２２】第３の発明における列方向のデータ放送の様
子を示す図。

【図２３】図２１と同様な行方向のデータ放送の様子を
示す図。

【図２４】図２２と同様な列方向のデータ放送の様子を
示す図。

【図２５】図２０と異なる行列乗算手順を示すフローチ
ャート。

【図２６】代表的なパイプラインと実行の様子。

【図２７】従来のコンパイラを説明するための計算機の
構成、ソースプログラム、及びスケジューリング前の命
令列。

【図２８】図２７で示した命令列の実行の様子及び命令
列に対する依存有向グラフ。

【図２９】従来のコンパイラによって得られるパター
ン。

【図３０】図２９で示した各パターンに対する実行の様
子。

【図３１】第３の発明に対する従来の並列計算機の構成
例。

【図３２】図３１で示した各ＰＥに初期データが配置さ
れた様子を示す図。

【図３３】２つの４×４行列の積を示す数式。

【図３４】第３の発明に対する従来の行列乗算手順を示
すフローチャート。

【図３５】図３１で示した各ＰＥが必要な全データを保
持した様子を示す図。

【符号の説明】

１ ソースプログラム ２ ソースプログラム入力部 ３ 字句解析部 ４ 構文解析部 ５ 中間コード生成部 ６ 命令スケジューリング部 ７ 最適化部 ８ 中間コード最適化部 ９ オブジェクトコード生成部 １０ 目的プログラム出力部 １１ 目的プログラム （１）〜（４），（１，１）〜（３，３） プロセッサ １３ ローカルメモリ ２１ 演算制御部 ２２ 演算実行部 ２３ データバス ２４ 命令メモリ ２５ ＰＥ（演算プロセッサ） ２６ データメモリ ２７ ネットワーク

Claims (4)

【特許請求の範囲】
1. 【請求項１】 並列に実行可能な複数の演算器を備え、
   命令をパイプラインで処理する計算機で使用される目的
   プログラムを生成するコンパイラであって、 基本ブロック内の命令列に対し、依存関係のある命令毎
   に命令群を構成し、命令群を単位として、パイプライン
   の空き状態が小さくなるように命令群の実行順序の入れ
   換え、繰り上げ、あるいは繰り下げを行う命令スケジュ
   ーリング部を備え、 命令列の実行時間が最も短くなるように最適化を図るこ
   とを特徴とするコンパイラ。
2. 【請求項２】 ２次元の格子状に分割された２次元領域
   の物理現象のシミュレーションであらわれる連立一次方
   程式を解く、複数個のプロセッサからなる並列計算機で
   あって、 第ｉプロセッサは、第（ｉ−１）プロセッサから送出さ
   れた物理量を受信する受信手段と、受信した物理量を用
   いてこの第ｉプロセッサに対する格子点の物理量を計算
   する計算手段と、計算した物理量を記憶する記憶手段
   と、計算した物理量を第（ｉ＋１）プロセッサへ送出す
   る送信手段とを有し、 前記２次元格子の第ｉ行上の格子点の物理量計算を第ｉ
   プロセッサに割り当て、この第ｉプロセッサは、第ｉ行
   上の割り当てられた格子点の物理量計算が可能になった
   とき以降、第（ｉ−１）プロセッサの送信手段によって
   送出された物理量を受信手段で受信し、受信した物理量
   を用いて割り当てられた格子点の物理量を計算手段で計
   算し、計算した物理量を記憶手段で記憶すると共に、送
   信手段で第（ｉ＋１）プロセッサへ送出することを、第
   ｉ行のすべての格子点について繰り返すことを特徴とす
   る並列計算機。
3. 【請求項３】 ３次元の格子状に分割された３次元領域
   の物理現象のシミュレーションであらわれる連立一次方
   程式を解く、複数個のプロセッサからなる並列計算機で
   あって、 （ｉ，ｊ）プロセッサは、（ｉ−１，ｊ）プロセッサ及
   び（ｉ，ｊ−１）プロセッサから送出された物理量を受
   信する受信手段と、受信した物理量を用いてこの（ｉ，
   ｊ）プロセッサに対する格子点の物理量を計算する計算
   手段と、計算した物理量を記憶する記憶手段と、計算し
   た物理量を（ｉ，ｊ＋１）プロセッサおよび（ｉ＋１，
   ｊ）プロセッサプロセッサへ送出する送信手段とを有
   し、 前記３次元格子の同一軸上の格子点の物理量計算を同一
   プロセッサに割り当て、（ｉ，ｊ）プロセッサは、割り
   当てられた同一軸上の格子点の物理量計算が可能になっ
   たとき以降、（ｉ−１，ｊ）プロセッサ及び（ｉ，ｊ−
   １）プロセッサの送信手段によって送出された物理量を
   受信手段で受信し、受信した物理量を用いて割り当てら
   れた格子点の物理量を計算手段で計算し、計算した物理
   量を記憶手段で記憶すると共に、送信手段で（ｉ＋１，
   ｊ）プロセッサ及び（ｉ，ｊ＋１）プロセッサへ送出す
   ることを、割り当てられた同一軸上のすべての格子点に
   ついて繰り返すことを特徴とする並列計算機。
4. 【請求項４】 ２次元状に配置された複数の演算要素プ
   ロセッサから構成される並列プロセッサで、２つの行列
   の積を求める並列計算機であって、 第１の行列データと第２の行列データを、該２つの行列
   で同じ割り付けを行い、 該行列の行方向のデータを持つ演算プロセッサ間で、１
   つの演算プロセッサから他の複数の演算プロセッサへデ
   ータを放送する手段と、該行列の列方向のデータを持つ
   演算プロセッサ間で、１つの演算プロセッサから他の複
   数の演算プロセッサへデータを放送する手段と、 繰り返し回数を制御する手段と、 該データ放送と演算プロセッサでの演算を制御する制御
   手段とを備え、 該第１の行列の、繰り返し回数で指定される１列のデー
   タを保持する各演算プロセッサが、各列データと同じ行
   に属するデータを保持する複数の演算プロセッサに対し
   て各列データを同時並列に転送し、 該第２の行列の、繰り返し回数で指定される１行のデー
   タを保持する各演算プロセッサが、各行データと同じ列
   に属するデータを保持する複数の演算プロセッサに対し
   て各行データを同時並列に転送し、 各演算プロセッサで、転送された該第１の行列のデータ
   と、転送された該第２のデータの２つの数の積を求め、
   該積を繰り返し毎に累算し、 以上の操作を、行列の大きさから得られる所定回数だけ
   繰り返すことによって、行列の積を求めることを特徴と
   する並列計算機。