(57)【特許請求の範囲】
【請求項１】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理装置であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の要素の位置をずらしながら該対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して、該ソースプログラムに挿入する手段と、
上記見つけたリストアクセスのリスト値による上記作業配列のアクセス位置を決める命令を生成して、該ソースプログラムに挿入する手段と、
上記ソースプログラム中の上記対象配列によるリストベクトルアクセスを上記作業配列によるアクセスに変更する手段と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力するコード生成手段と
を備えたことを特徴とする処理装置。
【請求項２】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理装置であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対して、該対象配列のアクセス位置としてそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して、該ソースプログラムに挿入する手段と、
上記ソースプログラム中の上記ループの繰り返しに依存するアクセスを全て、上記生成したアクセス位置に変更する手段と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力するコード生成手段と
を備えたことを特徴とする処理装置。
【請求項３】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理装置であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の先頭位置のデータをスカラデータとしてロードするスカラ命令を生成して、該ソースプログラムに挿入する手段と、
上記対象配列のデータを表すベクトルデータの各要素に、ロードしたスカラデータを複写する命令を生成して、該ソースプログラムに挿入する手段と、
上記対象配列の代わりに上記ベクトルデータを使用した命令列を生成して、該ソースプログラムに挿入する手段と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力するコード生成手段と
を備えたことを特徴とする処理装置。
【請求項４】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理装置であって、
上記ソースプログラム中のリストアクセスのアクセス方法を変更する変更指示が該ソースプログラム中に記述されていることを検出する解析手段と、
上記変更指示が検出されたとき、該変更指示に従って、上記リストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対する、該対象配列の複数のアクセス位置が、それぞれ異なるメモリバンクに含まれるように、該リストアクセスを変更する変更処理手段と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力するコード生成手段と
を備えたことを特徴とする処理装置。
【請求項５】
上記変更処理手段は、上記対象配列の要素の位置をずらしながら該対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して、上記ソースプログラムに挿入し、該ソースプログラム中の該対象配列に対するアクセスを該作業配列に対するアクセスに変更することを特徴とする請求項４記載の処理装置。
【請求項６】
上記変更処理手段は、上記インデックスの複数の異なる値に対してそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して、該ソースプログラムに挿入し、上記リストアクセスのアクセス位置をランダムなアクセス位置に変更することを特徴とする請求項４記載の処理装置。
【請求項７】
ソースプログラムをコンパイルしてオブジェクトコードを生成するコンピュータのための記録媒体であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の要素の位置をずらしながら該対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して、該ソースプログラムに挿入する機能と、
上記見つけたリストアクセスのリスト値による上記作業配列のアクセス位置を決める命令を生成して、該ソースプログラムに挿入する機能と、
上記ソースプログラム中の上記対象配列によるリストベクトルアクセスを上記作業配列によるアクセスに変更する機能と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力する機能と
を上記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項８】
ソースプログラムをコンパイルしてオブジェクトコードを生成するコンピュータのための記録媒体であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対して、該対象配列のアクセス位置としてそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して、該ソースプログラムに挿入する機能と、
上記ソースプログラム中の上記ループの繰り返しに依存するアクセスを全て、上記生成したアクセス位置に変更する機能と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力する機能と
を上記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
ソースプログラムをコンパイルしてオブジェクトコードを生成するコンピュータのための記録媒体であって、
上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の先頭位置のデータをスカラデータとしてロードするスカラ命令を生成して、該ソースプログラムに挿入する機能と、
上記対象配列のデータを表すベクトルデータの各要素に、ロードしたスカラデータを複写する命令を生成して、該ソースプログラムに挿入する機能と、
上記対象配列の代わりに上記ベクトルデータを使用した命令列を生成して、該ソースプログラムに挿入する機能と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力する機能と
を上記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
ソースプログラムをコンパイルしてオブジェクトコードを生成するコンピュータのための記録媒体であって、
上記ソースプログラム中のリストアクセスのアクセス方法を変更する変更指示が該ソースプログラム中に記述されていることを検出する機能と、
上記変更指示が検出されたとき、該変更指示に従って、上記リストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対する、該対象配列の複数のアクセス位置が、それぞれ異なるメモリバンクに含まれるように、該リストアクセスを変更する機能と、
変更されたソースプログラムから上記オブジェクトコードを生成して出力する機能と
を上記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
上記リストアクセスを変更する機能は、上記対象配列の要素の位置をずらしながら該対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して、上記ソースプログラムに挿入し、該ソースプログラム中の該対象配列に対するアクセスを該作業配列に対するアクセスに変更する機能を含むことを特徴とする請求項１０記載の記録媒体。
【請求項１２】
上記リストアクセスを変更する機能は、上記インデックスの複数の異なる値に対してそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して、該ソースプログラムに挿入し、上記リストアクセスのアクセス位置をランダムなアクセス位置に変更する機能を含むことを特徴とする請求項１０記載の記録媒体。
【請求項１３】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理方法であって、
変更処理手段が、上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の要素の位置をずらしながら該対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して、該ソースプログラムに挿入し、
上記変更処理手段が、上記見つけたリストアクセスのリスト値による上記作業配列のアクセス位置を決める命令を生成して、該ソースプログラムに挿入し、
上記変更処理手段が、上記ソースプログラム中の上記対象配列によるリストベクトルアクセスを上記作業配列によるアクセスに変更し、
コード生成手段が、変更されたソースプログラムから上記オブジェクトコードを生成して出力する
ことを特徴とする処理方法。
【請求項１４】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理方法であって、
変更処理手段が、上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対して、該対象配列のアクセス位置としてそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して、該ソースプログラムに挿入し、
上記変更処理手段が、上記ソースプログラム中の上記ループの繰り返しに依存するアクセスを全て、上記生成したアクセス位置に変更し、
コード生成手段が、変更されたソースプログラムから上記オブジェクトコードを生成して出力する
ことを特徴とする処理方法。
【請求項１５】
ソースプログラムをコンパイルしてオブジェクトコードを生成する処理方法であって、
変更処理手段が、上記ソースプログラム中からリストアクセスが見つかった場合に、該リストアクセスの対象配列の先頭位置のデータをスカラデータとしてロードするスカラ命令を生成して、該ソースプログラムに挿入し、
上記変更処理手段が、上記対象配列のデータを表すベクトルデータの各要素に、ロードしたスカラデータを複写する命令を生成して、該ソースプログラムに挿入し、
上記変更処理手段が、上記対象配列の代わりに上記ベクトルデータを使用した命令列を生成して、該ソースプログラムに挿入し、
コード生成手段が、変更されたソースプログラムから上記オブジェクトコードを生成して出力する
ことを特徴とする処理方法。
【発明の詳細な説明】
技術分野
本発明は、メモリアクセスを高速化する高速化処理装置およびその方法に関する。
背景技術
従来、科学技術計算をベクトル計算機で行う場合、メモリアクセスのアクセス性能がプログラムの実行性能を決定する重要な要因の１つとなる。
ベクトル計算機におけるメモリアクセスの種類は、以下のように分類できる。
（１）連続アクセス：例えば、下記のソースプログラム（fortranソース）のような場合である。
0003683281.tif 000002
この場合、配列ａおよび配列ｂは、ＤＯインデックスｉで連続的にアクセスされる。
（２）距離付きアクセス：例えば、下記のソースプログラム（fortranソース）のような場合である。
0003683281.tif 000003
この場合、配列ａおよび配列ｂは、ＤＯインデックスｉで２つ飛びに距離付きアクセスされる。
（３）リストアクセス：例えば、下記のソースプログラム（fortranソース）のような場合である。
0003683281.tif 000004
この場合、配列ａおよび配列ｂは、リスト配列ｌｉｓｔの値でランダムにアクセスされる。
これらのアクセス方式を、アクセス効率（速度）の観点から見ると、（１）＞（２）＞（３）の順に効率が良いと考えられる。つまり、連続アクセスが最も速く、リストアクセスが最も遅い。このようなソースのプログラミングチューニングにおける重要な課題の１つは、使用者が、与えられたソースを高速なメモリアクセスを行うアルゴリズムに変更することである。
しかしながら、アクセス速度が最も遅い（３）のリストアクセスは、プログラムのアルゴリズム上出現を回避することが不可能であり、上記（１）や（２）のアクセスに変更できないという問題がある。
また、インタリーブ方式でアドレスが割り当てられたメモリにおいては、しばしば、１つのメモリバンクに対して一定時間内に複数のアクセス要求が送られるバンク競合という現象が生じる。リストアクセスにおいてバンク競合が生じると、そのアクセス速度は、リストのパターンによって大きく異なってくる。同一バンクに多数のアクセスが集中して競合が生じた場合には、通常の数十倍のアクセス時間を要することもある。
発明の開示
本発明は、使用者によるソースプログラムのチューニングなしに、メモリのバンク競合を回避して、リストアクセスの高速化を図ることを目的とする。
本発明においては、コンパイル時にリストアクセスのアクセス方法を最適化するために、ソースに最適化指示行を記述しておく。そして、この最適化指示行の記述により、アクセス対象のデータを作業用配列にコピーしたり、アクセスの順序をランダムに変更したり、スカラロードを行ったりして、バンク競合を回避する。
第１図は、本発明の処理装置の構成図である。第１図において、ソースプログラム１は、原始プログラムであって、メモリアクセスの高速化の対象となるプログラムである。
処理装置２は、プログラム入力手段３、ソース解析手段４、ベクトル処理手段６、およびコード生成手段９などから構成され、プログラムに従って各種処理を行う。
プログラム入力手段３は、入力されたソースプログラム１をソース解析手段４に与える。
ソース解析手段４は、最適化制御行（最適化指示行）を解析する最適化制御行解析手段５などから構成され、ソースプログラム１を解析する。
ベクトル処理手段６は、ベクトル化を行うベクトル化手段７、リストベクトルアクセスの変更処理手段８などから構成され、ベクトル化処理を行う。
コード生成手段９は、コードを生成して、プログラムを実行可能形式のオブジェクト１０に変換する。
次に、最適化制御行解析手段５および変更処理手段８の動作を説明する。
最適化制御行解析手段５が、リストアクセスのアクセス方法を変更する最適化指示行がソースプログラム１中に挿入されていることを検出すると、変更処理手段８は、それに続くリストアクセスを当該最適化指示行で指示されたアクセス方法に変更する。変更方法としては、次の３つがある。
最適化制御行解析手段５がソースプログラム１中から最適化指示行を見つけたときに、変更処理手段８がリストアクセスの対象配列の要素の位置をずらしながらその対象配列を作業配列に複数回複写することで、同じ要素がそれぞれ異なるメモリバンクに含まれるような複数のコピーを生成する命令を生成して挿入し、リストアクセスのリスト値により作業配列のアクセス位置を決める命令を生成して挿入し、対象配列に対するリストアクセスを作業配列によるアクセスに変更する。
また、最適化制御行解析手段５がソースプログラム１中から最適化指示行を見つけたときに、変更処理手段８がリストアクセスの対象配列へアクセスするためのループの繰り返しを指定するインデックスの複数の異なる値に対して、その対象配列のアクセス位置としてそれぞれ異なる複数のアクセス位置をランダムに生成する命令を生成して挿入し、リストアクセス中のループの繰り返しに依存するアクセスを全て、生成したアクセス位置に変更する。
また、最適化制御行解析手段５がソースプログラム１中から最適化指示行を見つけたときに、変更処理手段８がリストアクセスの対象配列の先頭位置のデータをスカラデータとしてロードするスカラ命令を生成して挿入し、その対象配列のデータを表すベクトルデータの各要素に、ロードしたスカラデータを複写する命令を生成して挿入し、その対象配列の代わりに転送されたベクトルデータを使用した命令列を生成して挿入する。
また、これらの処理を実行するプログラムを格納した記録媒体を生成しておき、その記録媒体からプログラムを処理装置２にロードして使用することも可能である。
このように、最適化指示行の記述にしたがってコンパイルを行うことで、リストアクセスが適切なアクセス方法に変換される。したがって、使用者によるソースチューニングなしに、バンク競合を回避して、リストアクセスの高速化を図ることが可能となる。
【図面の簡単な説明】
第１図は、本発明の処理装置の構成図である。
第２図は、記録媒体を示す図である。
第３図は、配列複写方式の動作説明フローチャートである。
第４図は、配列複写方式のソース例を示す図である。
第５図は、配列複写方式のインプリメント例を示す図である。
第６図は、配列複写方式のベクトル実行例を示す図である。
第７図は、配列ＬＩＳＴの値を示す図である。
第８図は、変更前のメモリアクセスを示す図である。
第９図は、配列複写を示す図である。
第１０図は、変更後のメモリアクセスを示す図である。
第１１図は、同一のバンクアクセスの例を示す図である。
第１２図は、ランダムアクセス方式の動作説明フローチャートである。
第１３図は、ランダムアクセス方式のソース例を示す図である。
第１４図は、ランダムアクセス方式のインプリメント例を示す図である。
第１５図は、ランダムアクセス方式のベクトル実行例を示す図である。
第１６図は、スカラロード方式の動作説明フローチャートである。
第１７図は、スカラロード方式のソース例を示す図である。
第１８図は、スカラロード方式のインプリメント例を示す図である。
第１９図は、スカラロード方式のベクトル実行例を示す図である。
第２０図は、配列Ｌと配列Ｂの値を示す図である。
第２１図は、スカラレジスタへの複写を示す図である。
第２２図は、ベクトルレジスタへの複写を示す図である。
第２３図は、マスクの作成を示す図である。
第２４図は、例外処理を示す図である。
第２５図は、配列Ａへのストアを示す図である。
発明を実施するための最良の形態
以下、第１図から第２５図までを参照しながら、本発明の実施の形態および動作を順次詳細に説明する。
第１図のソースプログラム１は、例えば、後述する図３のソース例に記載したような、メモリアクセスを高速に行う対象となるプログラムである。
処理装置２は、ＣＰＵ（中央処理装置）やメモリから構成され、プログラムに従って各種処理を行う。
ソース解析手段４は、最適化制御行を解析する最適化制御行解析手段５などから構成され、ソースプログラム１を解析する。
ベクトル処理手段６は、ベクトル化を行うベクトル化手段７、リストベクトルアクセスの変更処理手段８などから構成され、ベクトル化処理を行う。
変更処理手段８は、リストベクトルアクセス時のバンク競合を回避するために、対象配列を作業用配列にコピーする処理、アクセス順番をランダムに変更する処理、あるいはスカラロード処理をプログラムに付加する。
コード生成手段９は、コードを生成して、プログラムを実行可能形式のオブジェクト１０に変換する。
処理装置２のＣＰＵは、メモリを利用してコンパイル処理のプログラムを実行することにより、上述のような処理を行って、ソースプログラム１からオブジェクト１０を生成する。
第２図は、処理装置２を含むコンピュータ１１にプログラムを供給することのできるコンピュータ読み取り可能な記録媒体を示している。情報提供者の記憶装置１２や可搬記録媒体１３に保存されたプログラムは、処理装置２にロードされて実行される。
記憶装置１２は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置等であり、コンピュータ１１とバスまたは回線により接続される。
可搬記録媒体１３としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。
次に、第３図から第１０図までを参照しながら、配列複写方式によりバンク競合を回避する場合について詳細に説明する。
第３図は、本発明の配列複写方式の動作説明フローチャートである。
第３図において、ステップＳ１では、解析手段５が、最適化指示行の解析を行う。ここでは、例えば、第４図に示すソース例の第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｃｏｐｙ（４，Ａ）
という配列複写方式を表す最適化指示行があるかどうかが調べられる。この最適化指示行は、コメント文として記述されており、配列Ａを４つ複写する配列複写処理を表している。
ステップＳ２では、解析手段５は、配列複写方式が指示されているかどうかを判別する。その結果がＹＥＳの場合には、ステップＳ３に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ３では、解析手段５は、指示された対象配列に対するアクセスがリストアクセスかどうかを判別する。ここでは、ステップＳ２で配列複写方式を指示された配列へのアクセスの記述が、リストアクセスを示しているかどうかが判別される。その結果がＹＥＳの場合には、ステップＳ４に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ４では、変更処理手段８が、指示対象配列の大きさが判るかどうかを判別する。その結果がＹＥＳの場合には、指示対象の配列の大きさが判明したので、ステップＳ５（[1]）で静的作業配列を確保し（第５図の[1]に対応）、ステップＳ７に進む。ＮＯの場合には、ステップＳ６で動的作業配列を確保し、ステップＳ７に進む。
ステップＳ７（[2]）では、変更処理手段８は、対象配列を作業配列へ複写回数分複写する命令を生成する（第５図の[2]に対応）。
ステップＳ８（[3]）では、変更処理手段８は、リスト値による作業配列のアクセス位置を決める命令を生成する（第５図の[3]に対応）。
ステップＳ９（[4]）では、変更処理手段８は、対象配列によるリストベクトルアクセスを作業配列によるアクセスに変更する（第５図の[4]に対応）。
以下の処理によって、ソースプログラム１中に配列複写方式の最適化指示行（例えば、第４図の第３行目の！ｏｃｌ  ｌｉｓｔ＿ｃｏｐｙ（４，Ａ））が検出され、指示対象配列がリストアクセスの場合に、当該配列の作業領域が確保され（例えば、第５図の[1]に対応）、対象配列を作業配列に複写回数分複写する命令が生成され（例えば、第５図の[2]に対応）、リスト値による作業配列のアクセス位置を決める命令が生成され（例えば、第５図の[3]に対応）、対象配列によるリストベクトルアクセスが作業配列によるアクセスに変更される（例えば、第５図の[4]に対応）。
これにより、第４図のソースプログラム１が第５図のソースプログラムに変更され、これをコンパイルしてオブジェクトコードを生成して実行すると、バンク競合を削減して、リストアクセスの高速化を図ることが可能となる。この配列複写方式は、第５図を用いて後述するように、特に同じリスト値が連続している場合にバンク競合を回避するのに有効である。
第４図のソース例において、第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｃｏｐｙ（４，Ａ）
が配列複写方式の最適化指示行である。そして、第４行目および第５行目がリストアクセスを示す行である。
第５図は、第４図のソースのインプリメントイメージを示している。ここで、[1]、[2]、[3]、[4]は、既述した第３図の[1]、[2]、[3]、[4]にそれぞれ対応した結果を表す。
第５図において、[1]は、作業配列ＷＯＲＫを確保する命令である。
１番目の[2]は、作業配列ＷＯＲＫへの複写１（第１回目の複写）を行う命令である。
２番目の[2]は、作業配列ＷＯＲＫへの複写２（第２回目の複写）を行う命令である。
３番目の[2]は、作業配列ＷＯＲＫへの複写３（第３回目の複写）を行う命令である。
４番目の[2]は、作業配列ＷＯＲＫへの複写４（第４回目の複写）を行う命令である。
[3]は、リスト値による作業配列ＷＯＲＫのアクセス位置を決める命令である。
[4]は、作業配列ＷＯＲＫから引用する命令である。
ここで、メモリバンク数をＩＭ、作業配列への複写回数をＪとすると、２次元の作業配列ＷＯＲＫの第１次元の大きさＳＩＺＥは、例えば、次式により与えられる。
ＳＩＺＥ＝（（Ｎ＋Ｊ−２））／ＩＭ＋１）×ＩＭ×Ｊ    （１）
Ｎは、１次元配列Ａ、Ｂ、Ｌの大きさを表す。ＳＩＺＥは、（１）式の値より大きくすることもでき、また、より小さくすることもできる。例えば、（１）式の代わりに、次式のＳＩＺＥを用いてもよい。
ＳＩＺＥ＝Ｎ＋Ｊ−１                                  （２）
また、作業配列ＷＯＲＫの第２次元の大きさは、複写回数Ｊに一致する。
第６図は、第５図のソースをベクトル化したベクトル実行イメージを示している。ここでは、第５図のＤＯループがベクトル命令に置き換えられている。
次に、具体例を用いて、配列複写方式の動作を説明する。ここでは、説明を簡単にするために、ソース例での配列の大きさおよびＤＯループの繰り返し回数を３（Ｎ＝３）として説明する。また、メモリバンク数は８、配列の複写回数は４として説明する。配列ＬＩＳＴの値としては、第７図に示すように、次の値を用いる。
ＬＩＳＴ（１）＝１
ＬＩＳＴ（２）＝３
ＬＩＳＴ（３）＝１
第８図は、変更前のメモリアクセスの例を示している。ここでは、図示のように、配列ＬＩＳＴが第７図に示すような値を持ち、配列Ａの要素Ａ（１）、Ａ（２）、Ａ（３）は、それぞれ異なるバンクに格納されているものとする。このとき、ＤＯループの繰り返しインデックス１と３に対応するリスト値はともに１となり、配列Ａの同一位置の要素Ａ（１）がアクセスされる。このため、Ａ（１）を有するバンクに２つのアクセス要求が送られるので、バンク競合となる。
第９図は、対象配列Ａを作業用配列ＷＯＲＫにコピーした様子を示している。ここで、（２）式のＳＩＺＥを用いると、Ｎ＝３、Ｊ＝４であるから、ＳＩＺＥ＝６となる。この値はメモリバンク数８より小さいため、ＳＩＺＥ＝８とおいても、何ら支障はない。そこで、作業配列として、ＷＯＲＫ（８，４）をメモリ上に確保している。この作業配列ＷＯＲＫの第１次元のインデックス１，２，３．．．，８は、それぞれ、異なるバンクに対応している。
そして、確保された領域に、対象配列Ａが、指示通り４回複写される。このとき、配列Ａの先頭要素Ａ（１）の位置を、図示のように１つずつずらしながら複写することで、１つのバンクに同じ要素が含まれないようにしている。
第１０図は、変更後のメモリアクセスの例を示している。ここでは、図示のように、第５図の[3]、[4]の命令に従って、作業配列ＷＯＲＫのアクセス位置が決められる。したがって、配列ＬＩＳＴが第７図に示すような値を持ち、ＤＯループの繰り返しインデックス１と３に対してともにＡ（１）をアクセスする場合でも、配列ＷＯＲＫ上の異なるバンクがアクセスされ、バンク競合を回避できる。
このように、配列複写方式は、与えられたリストベクトル上で同じ値が連続していたり、繰り返し現れるような場合に、効果を発揮する。しかし、リストの値によっては、配列複写方式でバンク競合を回避したつもりでも、逆に、同一バンクに対するアクセスが増加する可能性がある。
例えば、Ｎ＝４で、Ｉ＝１，２，３，４に対してリストの値がＬＩＳＴ（Ｉ）＝４，３，２，１のとき、作業配列ＷＯＲＫは、第１１図に示すようになる。この場合、第５図の[3]、[4]の命令に従ってアクセス位置を決めると、斜線で示した４つの位置がアクセス対象となり、Ａ（４）、Ａ（３）、Ａ（２）に対するアクセスが競合してしまう。
ランダムアクセス方式は、アクセス順位をリストベクトルの値によらずにランダムに生成することで、上述のような場合でもバンク競合を回避可能にする方法である。
次に、第１２図から第１５図までを参照しながら、ランダムアクセス方式によりバンク競合を回避する場合について詳細に説明する。
第１２図は、ランダムアクセス方式の動作説明フローチャートである。
第１２図において、ステップＳ１１では、解析手段５が、最適化指示行の解析を行う。ここでは、例えば、第１３図に示すソース例の第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｒａｎｄｏｍ（Ｂ）
というランダムアクセス方式を表す最適化指示行があるかどうかが調べられる。この最適化指示行は、コメント文として記述されており、配列Ｂをランダムアクセスする処理を表している。
ステップＳ１２では、解析手段５は、ランダムアクセス方式が指示されているかどうかを判別する。その結果がＹＥＳの場合には、ステップＳ１３に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ１３では、解析手段５は、指示された対象配列に対するアクセスがリストアクセスかどうかを判別する。ここでは、ステップＳ１２でランダムアクセス方式を指示された配列へのアクセスの記述が、リストアクセスを示しているかどうかが判別される。その結果がＹＥＳの場合には、ステップＳ１４に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ１４（[1]）では、変更処理手段８が、ランダムなアクセス位置を生成する命令を生成する（第１４図の[1]に対応）。
ステップＳ１５（[2]）では、変更処理手段８は、ループの繰り返しに存在するアクセスを全て、[1]で生成したアクセス位置に変更する（第１４図の[2]に対応）。
以上の処理によって、ソースプログラム１中にランダムアクセス方式の最適化指示行（例えば、第１３図の第３行目の！ｏｃｌ  ｌｉｓｔ＿ｒａｎｄｏｍ（Ｂ））が検出され、指示対象配列がリストアクセスの場合に、ランダムアクセス位置を生成する命令が生成され（例えば、第１４図の[1]に対応）、リストアクセスの位置がランダムアクセス位置に変更される（例えば、第１４図の[2]に対応）。
これにより、第１３図のソースプログラム１が第１４図のソースプログラムに変更され、これをコンパイルしてオブジェクトコードを生成して実行すると、バンク競合を削減して、リストアクセスの高速化を図ることが可能となる。このランダムアクセス方式は、特にリストの値が４、３、２、１、４、３、２、１などのように飛び飛びで同一の値の場合に、バンク競合を回避するのに有効である。
第１３図のソース例において、第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｒａｎｄｏｍ（Ｂ）
がランダムアクセス方式の最適化指示行である。そして、第４行目および第５行目がリストアクセスの行である。
第１４図は、第１３図のソースのインプリメントイメージを示している。ここで、[1]、[2]は、既述した第１２図の[1]、[2]にそれぞれ対応した結果を表す。
第１４図において、[1]のＲＡＭＤＯＭ（Ｉ，Ｎ）は、ランダムアクセス位置の生成関数である。このランダムアクセス位置の生成関数は、ループの繰り返し回数Ｎと、オリジナルのインデックス値Ｉとから、新たなインデックス値ＩＲＡＮＤＯＭを生成する。ただし、この生成関数は、Ｎ個のインデックス値Ｉに対して、それぞれ異なるＩＲＡＮＤＯＭを生成するように設定される。
[2]は、インデックスＩの代わりにＩＲＡＮＤＯＭを用いて、配列Ｂをアクセスする命令である。
第１５図は、第１４図のソースをベクトル化したベクトル実行イメージを示している。ここでは、第１４図のＤＯループがベクトル命令に置き換えられている。
次に、第１６図から第２５図までを参照しながら、スカラロード方式によりバンク競合を回避する場合について詳細に説明する。
第１６図は、スカラロード方式の動作説明フローチャートである。
図７において、ステップＳ２１では、解析手段５が、最適化指示行の解析を行う。ここでは、例えば、第１７図に示すソース例の第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｖｌｓ（Ｂ）
というスカラロード方式を表す最適化指示行があるかどうかが調べられる。この最適化指示行は、コメント文として記述されており、配列Ｂの値をスカラロードする処理を表している。
ステップＳ２２では、解析手段５は、スカラロード方式が指示されているかどうかを判別する。その結果がＹＥＳの場合には、ステップＳ２３に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ２３では、解析手段５は、指示対象配列がリストアクセスかどうかを判別する。ここでは、ステップＳ２２でスカラロード方式を指示された配列へのアクセスの記述が、リストアクセスを示しているかどうかが判別される。その結果がＹＥＳの場合には、ステップＳ２４に進む。ＮＯの場合には、処理なしで終了する。
ステップＳ２４（[1]）では、変更処理手段８が、対象配列の先頭位置をロードするスカラ命令を生成する（第１８図の[1]に対応）。
ステップＳ２５（[2]）では、変更処理手段８は、ベクトルデータに[1]でロードしたスカラデータを複写する命令を生成する（第１８図の[2]に対応）。
ステップＳ２６（[3]）では、変更処理手段８は、例外処理の命令を生成する（第１８図の[3]に対応）。ここでは、リスト値が先頭位置の値と異なる場合に限って、対象配列に対するリストアクセスを行い、アクセスしたデータを［2]のベクトルデータへ格納するような命令が生成される。
ステップＳ２７（[4]）では、変更処理手段８は、[2]と[3]のベクトルデータを使用した命令列を生成する（第１８図の[4]に対応）。
以上の処理によって、ソースプログラム１中にスカラロード方式の最適化指示行（例えば、第１７図の第３行目の！ｏｃｌ  ｌｉｓｔ＿ｖｌｓ（Ｂ））が検出され、指示対象配列がリストアクセスの場合に、対象配列の先頭位置をロードするスカラ命令が生成され（例えば、第１８図の[1]に対応）、ベクトルデータに[1]でロードしたスカラデータを複写する命令が生成され（例えば、第１８図の[2]に対応）、例外処理が生成され（第18図の[3]に対応）、ベクトルデータを使用した命令列が生成される（第１８図の[4]に対応）。
これにより、第１７図のソースプログラム１が第１８図のソースプログラムに変更され、これをコンパイルしてオブジェクトコードを生成して実行すると、バンク競合を削減して、リストアクセスの高速化を図ることが可能となる。ＤＯループの繰り返しの間、リストの値が連続して同一の値をとる場合、配列をリストベクトル命令でアクセスするよりも、１個のスカラアクセス命令を実行して、その結果をベクトルデータで使用した方が、実行効率が良好となる。したがって、特にこのような場合に、スカラロード方式が有効である。
ここで、スカラロード方式は、メモリアクセスを１回のスカラアクセスで行い、その結果をベクトルデータに拡散して使用する方式であり、スカラアクセスの対象を配列の先頭位置と仮定している。また、先頭位置の値と異なるリスト値が出現することも考慮して、例外処理において例外マスクを生成し、対応する位置の配置データを通常のリストベクトル命令でアクセスする。
第１７図のソース例において、第３行目の
！ｏｃｌ  ｌｉｓｔ＿ｖｌｓ（Ｂ）
がスカラロード式の最適化指示行である。そして、第４行目および第５行目がリストアクセスの行である。
第１８図は、第１７図のソースのインプリメントイメージを示している。ここで、[1]、[2]、[3]、[4]は、既述した第１８図の[1]、[2]、[3]、[4]にそれぞれ対応した結果を表す。
第１８図において、[1]は、リストの値が全て１と仮定したスカラロード命令である。
[2]は、ベクトルデータへの転送命令である。
[3]は、例外処理の命令である。
[4]は、ベクトルデータを使用したメモリストアの命令列である。
第１９図は、第１８図のソースをベクトル化したベクトル実行イメージを示している。ここでは、第１８図のＤＯループがベクトル命令に置き換えられている。
次に、具体例を用いて、スカラロード方式の動作を説明する。ここでは、説明を簡単にするために、ソース例での配列の大きさおよびＤＯループの繰り返し回数を８（Ｎ＝８）とし、メモリバンク数も８として説明する。また、処理装置２は、スカラレジスタ、ベクトルレジスタ、およびマスクレジスタを含んでいるものとする。
配列Ｂとリストベクトルの配列Ｌは、第２０図に示すような要素を持つものとし、各要素はそれぞれ異なるバンクに格納されている。配列Ｌの要素の値は、Ｌ（４）とＬ（８）を除いて、すべて１である。
第１９図の（ａ）を実行すると、第２１図に示すように、配列Ｂ（１）の内容がスカラレジスタにロードされる。
第１９図の（ｂ）を実行すると、第２２図に示すように、スカラレジスタのデータがベクトルレジスタのすべての要素に複写される。
第１９図の（ｃ）を実行すると、第２３図に示すように、配列Ｌの各要素が１と比較される。そして、値が１である要素については、マスタレジスタの対応する位置にマスクデータ“偽”が格納され、値が１でない要素については、マスクレジスタの対応する位置にマスクデータ“真”が格納される。
第１９図の（ｄ）を実行すると、第２４図に示すように、マスクレジスタの値に応じてベクトルレジスタの値が補正される。ここでは、マスクデータが“真”の位置に対応するＬ（４）と値２とＬ（８）の値３を用いて、配列Ｂがベクトルアクセスされ、ベクトルレジスタの対応する要素が書き換えられる。
第１９図の（ｅ）を実行すると、第２５図に示すように、ベクトルレジスタから配列Ａにデータがストアされる。
ここでは、配列Ｂの先頭位置のデータをスカラロードの対象としているが、配列Ｂの他の特定の位置をスカラロードの対象とすることも可能である。一般に、配列Ｌの要素として最も多く含まれるリスト値に対応する位置を、スカラロードの対象位置に設定すれば、アクセス効率が最適化される。
以上説明したように、実施形態のメモリアクセス方法としては、配列複写方式、ランダムアクセス方式、およびスカラロード方式の３つの方式がある。使用者は、ソースに記述されたリストに対してこれらの方式を試行して、最も効率の良い方式を採用することができる。また、各ループ処理の前に最適化指示行を挿入することで、ループ処理毎に異なる方式を指定することができる。
また、アクセス方法を指示する最適化指示行は、必ずしもコメント文である必要はなく、オプションで適当なコマンド等を定義して用いてもよい。
産業上の利用可能性
本発明によれば、ベクトル計算機におけるコンパイル時にリストアクセスのアクセス方法を最適化する最適化指示行が、ソースプログラムに挿入される。そして、その指示に従って、自動的に、アクセス対象のデータを作業用配列にコピーしたり、アクセスの順序をランダムに変更したり、スカラロードを行ったりする構成を採用している。したがって、使用者によるソースチューニングなしに、ベクトル化に伴うバンク競合を回避して、リストアクセスの高速化を図ることができる。
【図１】
0003683281.tif 000005
【図２】
0003683281.tif 000006
【図３】
0003683281.tif 000007
【図４】
0003683281.tif 000008
【図５】
0003683281.tif 000009
【図６】
0003683281.tif 000010
【図７】
0003683281.tif 000011
【図８】
0003683281.tif 000012
【図９】
0003683281.tif 000013
【図１０】
0003683281.tif 000014
【図１１】
0003683281.tif 000015
【図１２】
0003683281.tif 000016
【図１３】
0003683281.tif 000017
【図１４】
0003683281.tif 000018
【図１５】
0003683281.tif 000019
【図１６】
0003683281.tif 000020
【図１７】
0003683281.tif 000021
【図１８】
0003683281.tif 000022
【図１９】
0003683281.tif 000023
【図２０】
0003683281.tif 000024
【図２１】
0003683281.tif 000025
【図２２】
0003683281.tif 000026
【図２３】
0003683281.tif 000027
【図２４】
0003683281.tif 000028
【図２５】
0003683281.tif 000029