JPH03260865A - ベクトル化処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はベクトル化処理方式に関し、特にベクトル処理
プロセンサに対するコンパイラにおいて並列実行の可能
性の判定および並列実行可能部分のベクトル化処理を行
うベクトル化処理方式に関する。

〔従来の技術） ベクトル命令によるベクトル演算機能を有するベクトル
処理プロセッサでは、ソースプログラム中のループ構造
（例えば、第２図に示すＦＯＲＴＲＡＮソースプログラ
ム中のＤＯ小ループ中に２度以上現れる配列要素に関す
る実行は、スカラ命令により順次実行した場合とベクト
ル命令により並列実行した場合とで、同一配列要素への
定義の順序が異なることから実行結果に違いが生しる（
その配列要素に関して、並列実行に矛盾するデータ依存
関係がある）ことがある。

従来、ベクトル処理プロセッサに対するコンパイラでは
、並列実行に矛盾するデータ依存関係がある配列要素が
ループ構造中に存在する場合には、そのループ構造中の
文群をベクトル化する（それらの文群をオブジェクトプ
ログラム内のベクトル命令で実行する）ことはできなか
った（文の入れ換えにより並列実行に矛盾するデータ依
存関係を解消するコンパイラも存在するが、このような
コンパイラであっても文の入れ換えでは並列実行に矛盾
するデータ依存関係を解消することができない場合には
そのループ構造中の文群をベクトル化することはできな
かった）。

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

ベクトル演算機能を有するベクトル処理プロセッサにお
いては、−ａにオブジェクトプログラム内のベクトル命
令によって実行される部分の割合を大きくすればするほ
ど実行時間を短縮することができる。

ところが、上述した従来のベクトル化処理方式では、並
列実行に矛盾するデータ依存関係がある配列要素が存在
するループ構造中の文群をベクトル化することができな
いので、ベクトル処理プロセンサの実行時間を十分に短
縮することができないという欠点がある。

本発明の目的は、上述の点に鑑み、並列実行に矛盾する
データ依存関係（特に、文の入れ換えでは解消できない
並列実行に矛盾するデータ依存関係）がある配列要素が
存在するループ構造中の文群をベクトル化することを可
能とし、ベクトル処理プロセッサの実行時間を短縮する
ことができるベクトル化処理方式を提供することにある
。

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

本発明のベクトル化処理方式は、ベクトル演算機能を有
するベクトル処理プロセッサに対するコンパイラにおい
て、ソースプログラムを読み込み構文解析を行って中間
テキストを生成する横文解析手段と、この構文解析手段
にまり生成された中間テキストを入力してソースプログ
ラム中のループ構造を検出しそのループ構造中において
並列実行に矛盾するデータ依存関係がある配列要素が存
在するか否かを判定するデータ依存関係判定手段と、こ
のデータ依存関係判定手段において並列実行に矛盾する
データ依存関係があると判定された配列要素に対してデ
ータ依存関係が並列実行に矛盾する要因を検査するデー
タ依存関係矛盾要因検査手段と、このデータ依存関係矛
盾要因検査手段による検査に基づいてベクトル長の再設
定が可能と判定した場合にベクトル長を再設定し同一配
列要素へのアクセスが重複しないように配列要素の添字
式を変形することにより並列実行に矛盾するデータ依存
関係の解消を行うベクトル長再設定手段と、このベクト
ル長再設定手段による並列実行に矛盾するデータ依存関
係の解消に基づいて前記構文解析手段により生成された
中間テキストをベクトル命令を適用するための形式に変
形する中間テキスト変形手段と、この中間テキスト変形
手段により変形された中間テキストに基づいてオブジェ
クトプログラムを生成するコード生成手段とを有する。

〔作用〕

本発明のベクトル化処理方式では、構文解析手段がソー
スプログラムを読み込み構文解析を行って中間テキスト
を生成し、データ依存関係判定手段が構文解析手段によ
り生成された中間テキストを入力してソースプログラム
中のループ構造を検出しそのループ構造中において並列
実行に矛盾するデータ依存関係がある配列要素が存在す
るか否かを判定し、データ依存関係矛盾要因検査手段が
データ依存関係判定手段において並列実行に矛盾するデ
ータ依存関係があると判定された配列要素に対してデー
タ依存関係が並列実行に矛盾する要因を検査し、ベクト
ル長再設定手段がデータ依存関係矛盾要因検査手段によ
る検査に基づいてベクトル長の再設定が可能と判定した
場合にベクトル長を再設定し同一配列要素へのアクセス
が重複しないように配列要素の添字式を変形することに
より並列実行に矛盾するデータ依存関係の解消を行い、
中間テキスト変形手段がベクトル長再設定手段による並
列実行に矛盾するデータ依存関係の解消に基づいて構文
解析手段により生成された中間テキストをベクトル命令
を適用するた、めの形式に変形し、コード生成手段が中
間テキスト変形手段により変形された中間テキストに基
づいてオブジェクトプログラムを生成する。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明のベクトル化処理方式の一実施例の構
成を示すブロフク図である０本実施例のベクトル化処理
方式は、高級言語で書かれたソースプログラムｌと、コ
ンパイラ２と、ベクトル処理プロセンサで実行されるオ
ブジェクトプログラム３とを含んで構成されている。

コンパイラ２は、ベクトル化処理手段４と、構文解析手
段２１と、コード生成手段２６と、中間テキスト２７と
を含んで構成されている。

ベクトル化処理手段４は、データ依存関係判定手段２２
と、データ依存関係矛盾要因検査手段２３と、ベクトル
長再設定手段２４と、中間テキスト変形手段２５とを含
んで構成されている。

なお、第１図中の太い矢線は制御の流れを示しており、
細い矢線はデータの流れを示している。

次に、このように構成された本実施例のベクトル化処理
方式の動作について説明する。

コンパイラ２内の構文解析手段２１は、ソースプログラ
ムｌを読み込み、構文解析を行い、中間テキスト２７を
生成する０例えば、第２図に示すようなソースプログラ
ムｌ　　（ＦＯＲＴＲＡＮソースプログラム〉を読み込
み、第４図に示すような中間テキスト２７　（形式１中
間テキスト）を生成する。

ベクトル化処理手段４内のデータ依存関係判定手段２２
は、構文解析手段２１にまり生成された中間テキスト２
７に基づいてソースプログラムｌ中のループ構造を検出
すると、そのループ構造中に並列実行に矛盾するデータ
依存関係がある配列要素が存在するか否かを次の手順で
判定する。

＋１１　　ループ構造中に含まれる全ての配列要素を検
出し、当該配列要素に対して第６図に示すような配列テ
ーブルおよび配列要素テーブルを作成する。

例えば、第２図のＤＯループ（第２図に示すソースプロ
グラムｌにおけるループ構造）の場合には、配列要素Ａ
　（１）、　Ａ　（１＋１０）、　　Ｂ　（１）、　Ｂ
　（１）、　Ｂ　（１）　、　Ｃ（１）およびＤ（＋）
に対して、配列テーブルおよび配列要素テーブルを作成
する。

配列テーブルについては、「次の配列テーブルへのポイ
ンタ」フィールド、「配列名」フィールドおよび「最初
の配列要素テーブルへのポインタ」フィールドを設定す
る。

配列要素テーブルについては、対応する配列要素の添字
式を初期値および増分値を表す形に変形し、これらを対
応するフィールド（「添字式」フィールド、「添字式の
初期値」フィールドおよび「添字式の増分値」フィール
ド）に設定する。また、対応する配列要素が含まれるソ
ース行（文）の行番号を対応するフィールド（「ソース
行番号」フィールド）に設定する。さらに、対応する配
列要素がループ構造中で定義される場合には定義配列要
素フラグ（「定義配列要素フラグ」フィールドにおける
フラグ）をオンにし、対応する配列要素がループ構造中
で引用される場合には定義配列要素フラグをオフにする
。

なお、各配列要素テーブル内のデータ依存フラグ（「デ
ータ依存フラグ」フィールドにおけるフラグ）をオフに
する。

（２）　　中間テキスト２７　（形式ｌ中間テキスト）
。

配列テーブルおよび配列要素テーブルから、ループ構造
中に２度以上現れる配列要素について、スカラ命令によ
り順次実行した場合とベクトル命令により並列実行した
場合とで同一配列要素への定義の順序または定義・引用
の順序が異なることから実行結果に違いが生じるか否か
を調べる。

この調査で実行結果に違いが生しる場合には、その配列
要素に関して並列実行に矛盾するデータ依存関係がある
と判定する。

このように、並列実行に矛盾するデータ依存関係がある
配列要素が存在すると判定した場合には、当該配列要素
の配列要素テーブルのデータ依存フラグをオンにし、第
６図に示すようなデータ依存スタックを作成し、そのデ
ータ依存スタック内の「矛盾するデータ依存関係にある
配列要素テーブルへのポインタ」フィールドに当該配列
要素に対して並列実行に矛盾するデータ依存関係がある
配列要素の配列要素テーブルへのポインタを格納する。

例えば、第２図のＤｏ小ループ場合には、Ｄ。

ループ中に２度以上現れる配列Ａ（配列要素Ａ（門およ
びＡ（１＋１０））および配列Ｂ（配列要素Ｂ（１））
がデータ依存関係の検査の対象とされる。

ここで、配列要素Ａ　（１）およびＡ（＋＋１０〉に対
しては、スカラ命令により順次実行した場合とベクトル
命令により並列実行した場合とで、同一配列要素への定
義の順序が異なるために、実行結果に違いが生じる。よ
って、並列実行に矛盾するデータ依存関係があると判定
され、配列要素Ａ（１）およびＡ（＋＋１０）の配列要
素テーブルに対応するデータ依存スタックが作成される
。

配列要素Ｂ　（１）に対しては、並列実行に矛盾するデ
ータ依存関係がないと判定され、データ依存スタックは
作成されない。

データ依存関係矛盾要因検査手段２３は、データ依存関
係判定手段２２によりデータ依存フラグがオンにされた
配列要素テーブルと当該配列要素テーブルに対応するデ
ータ依存スタックとから、以下の条件（ａ）〜（Ｃ）が
全て満たされているか否かを調べ、データ依存関係が並
列実行に矛盾する要因を検査する。

条件（ａ）　　並列実行に矛盾するデータ依存関係があ
る２つの配列要素が共に定義されている。

条件（ｂ）　　並列実行に矛盾するデータ依存関係があ
る２つの配列要素の添字式の増分値が等しい。

条件（Ｃ）　　並列実行に矛盾するデータ依存関係があ
る２つの配列要素間の添字式の初期値の差が各配列要素
の添字式の増分値の倍数である。

以上の条件（ａ）〜（Ｃ）が全て満たされている場合に
は、データ依存関係矛盾要因検査手段２３は、次式によ
ってデータ依存回次数の値を求め、その値をデータ依存
スタック内の「データ依存回次数」フィールドに設定す
る。

データ依存回次数＝配列要素間の添字式の初期値の差／
配列要素の添字式の増分値 第７図は、このような設定が行われた後における、第２
図のＤｏ小ループ場合の配列への配列テーブル、配列要
素Ａ　（１）およびＡ（＋＋１０）の配列要素テーブル
ならびに当該配列要素テーブルに対応するデータ依存ス
タックの状態を示す図である。

ベクトル長再設定手段２４は、並列実行に矛盾するデー
タ依存関係を解消するために、次のような処理を行う。

（１１配列テーブル、配列要素テーブルおよびデータ依
存スタックから、ベクトル長の再設定が可能であるか否
かを検査する。以下の条件（ｄ）および（ｅ）が全て満
たされている場合には、ベクトル長の再設定が可能であ
ると判定する。

条件（ｄ）　　並列実行に矛盾するデータ依存関係があ
る配列要素の組に対するデータ依存スタ・７り中の「デ
ータ依存回次数」フィールド内の値（データ依存回次数
）が２以上の正定数である。

条件（ｅ）　　条件（ｄ）を満たす並列実行に矛盾する
データ依存関係がある配列要素の組の他に、データ依存
フラグがオンの配列要素テーブルに係る配列要素が存在
しない。

第２図のＤＯ小ループ場合には、第７図に示すように、
配列要素Ａ　（１）およびＡ（１＋１０）に対するデー
タ依存スタックのデータ依存回次数は２以上の正定数で
あり、当該配列要素の組の他に並列実行に矛盾するデー
タ依存関係がある（配列要素テーブルのデータ依存フラ
グがオンである）配列要素は存在しないために、ベクト
ル長の再設定が可能であると判定される。

（２１ｉｌｌでベクトル長の再設定が可能と判定した場
合には、ベクトル長を再設定するための中間テキスト２
７（形式２中間テキスト）を生成する。

第２図のＤＯ小ループ場合には、配列要素Ａ（■）およ
びＡ（＋＋１０）に対するデータ依存スタックのデータ
依存回次数の１０を再設定ベクトル長とする中間テキス
ト２７が生成される。

（３１１１１でベクトル長の再設定が可能と判定した場
合には、ベクトル長を再設定することから、同一配列要
素へのアクセスが重複しないように、以下の手順（＋）
および（ｉｉ）で配列要素の添字式を変形する。

手順（ｉ）　　データ依存スタック中の「矛盾するデー
タ依存関係にある配列要素テーブルへのポインタ」フィ
ールドが指している配列要素テーブルの「ソース行番号
」フィールド内の値と等しいソース行番号のソース行（
文〉において変形を要する添字式を持つ配列要素を選出
する。

第２図のＤＯ小ループ場合には、■の文中の配列要素Ａ
（１＋１０）と配列要素Ｂ　（１）とが添字式の変形の
対象となる配列要素として選出される。

手順（ｉｉ）　　手順（１）で選出された配列要素に対
して、再設定前のベクトル長とデータ依存回次数とを用
いて、同一配列要素へのアクセスが重複しないように添
字式を変形する。

また、変形した添字式に基づき、配列要素の初期値を求
め、対応する配列要素テーブルの各フィールドを更新す
る。

第８図は、このような変形が行われた後における、第２
図のＤｏ小ループ場合の配列要素Ａ（＋＋１０）と配列
要素Ｂ（りとに対する配列テーブル、配列要素テーブル
およびデータ依存スタック等の状態を示す図である。

このようにして、第２図のＤｏ小ループおける配列要素
Ａ　（１）と配列要素Ａ（１＋１０）との間の並列実行
に矛盾するデータ依存関係が解消される。

中間テキスト変形手段２５は、更新後の配列要素テーブ
ル等を用いて、中間テキスト２７をベクトル命令を適用
するための形式に変形する。

例えば、第２図に示すようなソースプログラムｌがあた
かもベクトル化が可能な第３図に示すようなりｏループ
が２つに分割されたソースプログラムと等価になるよう
に、第４図に示すような中間テキスト２７（形式１中間
テキスト）を第５図に示すような中間テキスト２７　（
形式２中間テキスト）に変形する。

コード生成手段２６は、ベクトル化処理手段４から制御
を渡され、中間テキスト変形手段２５により変形された
中間テキスト２７（例えば、第５図に示すような形式２
中間テキスト）を人力し、その中間テキスト２７に基づ
いてオブジェクトプログラム３を生成する。

〔発明の効果〕

以上説明したように本発明は、ベクトル処理プロセッサ
において、従来ベクトル化が不可能であったループ構造
中の文群のベクトル化が可能となることにより、ベクト
ル処理プロセッサの実行時間を短縮することができると
いう効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示すブロック図、 第２図は第１図中のソースプログラムの一例を示す図、 第３図は第２図に示すソースプログラムにおける並列実
行に矛盾するデータ依存関係を解消するためのソースプ
ログラムの修正の態様を示す図、第４図は第２図に示す
ソースプログラムに対応する第１図中の中間テキスト（
第１図中の構文解析手段により生成される形式１中間テ
キスト）を示す図、 第５図は第３図に示すソースプログラムに対応する第１
図中の中間テキスト（第１図中のコード生成手段により
入力される形式２中間テキスト）を示す図、 第６図は第１図中のデータ依存関係判定手段により作成
される配列テーブル、配列要素テーブルおよびデータ依
存スタックを示す図、 第７図は配列テーブル、配列要素テーブルおよびデータ
依存スタックに対する第１図中のデータ依存関係矛盾要
因検査手段の処理の態様を説明するための図ミ 第８図は配列テーブル、配列要素テーブルおよびデータ
依存スタックに対する第１図中のベクトル長再設定手段
の処理の態様を説明するための図である。 図において、 ｌ・・・ソースプログラム、 ２・・・コンパイラ、 ３・・・オブジェクトプログラム、 ４・・・ベクトル化処理手段、 ２１・・構文解析手段、 ２２・・データ依存関係判定手段、 ２３　・ ２４　・ ２５　・ ２６　・ ２７　・ データ依存関係矛盾要因検査手段、 ベクトル長再設定手段、 中間テキスト変形手段、 コード生成手段、 中間テキストである。

Claims (1)

1. 【特許請求の範囲】 ベクトル演算機能を有するベクトル処理プロセッサに対
   するコンパイラにおいて、 ソースプログラムを読み込み構文解析を行って中間テキ
   ストを生成する構文解析手段と、 この構文解析手段により生成された中間テキストを入力
   してソースプログラム中のループ構造を検出しそのルー
   プ構造中において並列実行に矛盾するデータ依存関係が
   ある配列要素が存在するか否かを判定するデータ依存関
   係判定手段と、このデータ依存関係判定手段において並
   列実行に矛盾するデータ依存関係があると判定された配
   列要素に対してデータ依存関係が並列実行に矛盾する要
   因を検査するデータ依存関係矛盾要因検査手段と、 このデータ依存関係矛盾要因検査手段による検査に基づ
   いてベクトル長の再設定が可能と判定した場合にベクト
   ル長を再設定し同一配列要素へのアクセスが重複しない
   ように配列要素の添字式を変形することにより並列実行
   に矛盾するデータ依存関係の解消を行うベクトル長再設
   定手段と、このベクトル長再設定手段による並列実行に
   矛盾するデータ依存関係の解消に基づいて前記構文解析
   手段により生成された中間テキストをベクトル命令を適
   用するための形式に変形する中間テキスト変形手段と、 この中間テキスト変形手段により変形された中間テキス
   トに基づいてオブジェクトプログラムを生成するコード
   生成手段と を有することを特徴とするベクトル化処理方式。