(57)【要約】 【課題】冗長なレジスタを動作記述中に追加することを防止し、動作記述のコード量の増大を防止し、生成されるハードウェアの面積の増加を防止して高速動作を可能とする半導体装置の設計装置、設計方法、設計プログラムを提供する。【解決手段】解析部は、動作記述より、第１の配列アクセスの添え字の取り得る範囲を解析する。第１の処理部は、第１の配列アクセスの添え字の取り得る範囲を包含するように、第１のループの範囲を第２のループの範囲に変更する。第２の処理部は、第２のループの範囲で、第１の配列アクセスの添え字の範囲を全て含む第２の配列アクセスを追加する。第３の処理部は、第１、第２の配列アクセス間のデータ再利用関係を調べ、各配列アクセス間の再利用距離を算出し、シフトレジスタの記述を第２のループに追加し、第１の配列アクセスを再利用距離と同じ番号を有するレジスタに置き換える。【選択図】図５
2014225201.tif 000002
【特許請求の範囲】
【請求項１】
複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述が記憶された記憶部と、
前記記憶部に記憶された前記動作記述より、前記第１の配列アクセスの添え字の取り得る範囲をそれぞれ解析する解析部と、
前記解析部により解析された前記第１の配列アクセスの添え字の取り得る範囲を包含するような第２の配列アクセスが存在するように、前記第１のループの範囲を第２のループの範囲に変更する第１の処理部と、
前記第２のループの範囲において、前記第１の配列アクセスの添え字の範囲を全て含む前記第２の配列アクセスを追加する第２の処理部と、
前記第１、第２の配列アクセス間のデータ再利用関係を調べ、各配列アクセス間の再利用距離を算出し、前記再利用距離の最大値と同じサイズのシフトレジスタの記述を前記第２のループに追加し、前記第１の配列アクセスを前記再利用距離と同じ番号を有するレジスタへのアクセスに置き換える第３の処理部と
を具備することを特徴とする半導体装置の設計装置。
【請求項２】
前記第１の処理部は、前記解析部により解析された複数の前記配列アクセスの添え字の取り得る範囲の和集合を算出することを特徴とする請求項１記載の半導体装置の設計装置。
【請求項３】
前記第２の処理部は、前記配列の添え字の範囲を全て含む配列アクセスを、前記第２のループの最も内側のループの先頭に追加することを特徴とする請求項１記載の半導体装置の設計装置。
【請求項４】
前記第３の処理部は、前記シフトレジスタを前記第２のループの最も内側のループの最後部に追加することを特徴とする請求項１記載の半導体装置の設計装置。
【請求項５】
複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述が記憶された記憶部と、
記憶部に記憶され、複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述より、前記第１の配列アクセスの添え字の取り得る範囲をそれぞれ解析し、
前記解析された前記第１の配列アクセスの添え字の取り得る範囲を包含するような第２の配列アクセスが存在するように、前記第１のループの範囲を第２のループの範囲に変更し、
前記第２のループの範囲において、前記第１の配列アクセスの添え字の範囲を全て含む前記第２の配列アクセスを追加し、
前記第１、第２の配列アクセス間のデータ再利用関係を調べ、各配列アクセス間の再利用距離を算出し、前記再利用距離の最大値と同じサイズのシフトレジスタの記述を前記第２のループに追加し、前記第１の配列アクセスを前記再利用距離と同じ番号を有するレジスタへのアクセスに置き換えることを特徴とする半導体装置の設計方法。
【請求項６】
複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述が記憶された記憶部と、
記憶部に記憶され、複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述より、前記第１の配列アクセスの添え字の取り得る範囲をそれぞれ解析し、
前記解析された前記第１の配列アクセスの添え字の取り得る範囲を包含するような第２の配列アクセスが存在するように、前記第１のループの範囲を第２のループの範囲に変更し、
前記第２のループの範囲において、前記第１の配列アクセスの添え字の範囲を全て含む前記第２の配列アクセスを追加し、
前記第１、第２の配列アクセス間のデータ再利用関係を調べ、各配列アクセス間の再利用距離を算出し、前記再利用距離の最大値と同じサイズのシフトレジスタの記述を前記第２のループに追加し、前記第１の配列アクセスを前記再利用距離と同じ番号を有するレジスタへのアクセスに置き換える処理をコンピュータに実行させることを特徴とする半導体装置の設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル回路の動作が記述された動作レベル記述（以下、単に動作記述と称す）を最適化する半導体装置の設計装置、設計方法、設計プログラムに関する。
【背景技術】
【０００２】
高位合成技術（非特許文献１）は、Ｃ言語等のプログラムにより構成された動作記述（以下、Ｃ記述とも言う）からＲＴＬ(Register Transfer Level)記述を自動生成できるため、ＶＬＳＩ(Very Large Scale Integration)の設計効率を大きく向上できる。しかし、高性能なＲＴＬ記述を生成するには、通常、Ｃ記述上でメモリアクセスの最適化が必要となる。現在、高位合成ツールによるメモリアクセスの最適化は、高位合成ツールの利用者が、人手でＣ記述を最適化する必要があり、設計時間の増大を招いている。
【０００３】
メモリアクセスの最適化技術の１つとしてスカラリプレイスと呼ばれる技術がある（非特許文献２、３、４）。Ｃ記述での配列と一時変数は、ハードウェア上において、メモリとレジスタとなる。スカラリプレイスは、Ｃ記述中の複数の配列へのアクセスを一時変数へのアクセス、すなわち、メモリへのアクセスをレジスタへのアクセスに置き換える技術であり、例えばシフトレジスタを用意することにより、配列へのアクセスを削減できる。これを高位合成前のＣ記述に適用することにより、自動生成されるハードウェアのメモリアクセスを削減でき、性能の向上が期待できる。
【０００４】
しかし、既存のスカラリプレイスは、予め用意したシフトレジスタに初期値を設定する必要がある場合がある。その際、コード量が増大し、ハードウェアの面積が増大するとともに、動作速度が低下するという問題を有している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２−１１８８３５号公報
【非特許文献】
【０００６】
【非特許文献１】Daniel D. Gajski, “High Level Synthesis: An Introduction to Chip and System Design,” Kluwer Academic Publishers, 1992.
【非特許文献２】Steve Carr, Ken Kennedy, “Scalar Replacement in the Presence of Conditional Control Flow,” Software-Practice and Experience, Vol. 24, Issue 1, pp. 51-77, 1994.
【非特許文献３】Byoungro So, “An Efficient, Design Space Exploration For Balance Between Computation And Memory”, Ph.D. University of Southern California, 2003.
【非特許文献４】Nastaran Baradaran, Pedro C. Diniz, and Joonseok Park, “Extending the Applicability of Scalar Replacement to Multiple Induction Variables,” pp. 455-469, Languages and Compilers for High Performance Computing, 2004
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、シフトレジスタを初期化する際、ハードウェアの面積の増加を防止して高速動作を可能とする半導体装置の設計装置、設計方法、設計プログラムを提供するものである。
【課題を解決するための手段】
【０００８】
本発明の半導体装置の設計装置の態様は、複数の第１の配列アクセス、及び第１のループを含むデジタル回路の動作が記述された動作記述が記憶された記憶部と、前記記憶部に記憶された前記動作記述より、前記第１の配列アクセスの添え字の取り得る範囲をそれぞれ解析する解析部と、前記解析部により解析された前記第１の配列アクセスの添え字の取り得る範囲を包含するような第２の配列アクセスが存在するように、前記第１のループの範囲を第２のループの範囲に変更する第１の処理部と、前記第２のループの範囲において、前記第１の配列アクセスの添え字の範囲を全て含む前記第２の配列アクセスを追加する第２の処理部と、前記第１、第２の配列アクセス間のデータ再利用関係を調べ、各配列アクセス間の再利用距離を算出し、前記再利用距離の最大値と同じサイズのシフトレジスタの記述を前記第２のループに追加し、前記第１の配列アクセスを前記再利用距離と同じ番号を有するレジスタへのアクセスに置き換える第３の処理部とを具備することを特徴とする。
【図面の簡単な説明】
【０００９】
【図１】動作記述の一例を示す図。
【図２】図１に示す動作記述に対して既存手法によるスカラリプレイス、初期化、及びループピーリングを実行した場合の途中経過を示す図。
【図３】図１に示す動作記述に対して既存手法によるスカラリプレイス、初期化、及びループピーリングを実行した場合の結果を示す図。
【図４】本実施形態が適用される動作合成装置の一例を示す構成図。
【図５】図４に示す制御部と記憶装置の機能を示す構成図。
【図６】本実施形態の動作を示すフローチャート。
【図７】本実施形態に適用される動作記述の一例を示す図。
【図８】図７に示す動作記述中の各配列アクセスの添え字が取り得る範囲を示す図。
【図９】本実施形態に係る第１の処理部の処理結果を示す図。
【図１０】本実施形態に係る第２の処理部の処理結果を示す図。
【図１１】図１１（ａ）（ｂ）は、本実施形態の配列アクセス間の再利用の関係を示す図。
【図１２】図１１（ｂ）に示す再利用の関係をまとめて示す図。
【図１３】本実施形態に係る第３の処理部の処理結果を示すものであり、最適化された動作記述の一例を示す図。
【図１４】図７に示す動作記述に対して、既存の配列アクセスの削除と初期化用配列アクセスを追加した場合の動作記述を示す図。
【図１５】図１４に示す動作記述の外側のループ（ループｉ）を１回分、既存のループピーリングした場合の動作記述を示す図。
【図１６】図１５に示す動作記述の内側のループ（ループｊ）を１回分、既存のループピーリングした場合の動作記述を示す図。
【発明を実施するための形態】
【００１０】
前述したように、スカラリプレイスでは、予め用意したシフトレジスタに初期値を設定する必要がある場合がある。例えば図１に示す動作記述に既存のスカラリプレイス技術と既存の初期化技術を適用した場合、最終的な結果は、図３に示すようになる。図２は、図１から図３に至る途中経過のコードを示している。図２、図３において、“ｓｈｉｆｔ＿ｒｅｇｉｓｔｅｒｓ（Ｂ＿ｒｅｇ＿５， ．．．， Ｂ＿ｒｅｇ＿０）”は、図１の配列アクセスをシフトレジスタへのアクセスに置き換える際に必要となる、シフトレジスタの記述を簡易的に示している。図２において、第３行と第５行は、シフトレジスタを初期化するための実行文である。
【００１１】
図１の第３行の配列アクセスＢ［ｉ］［ｊ］は、再利用ジェネレータ（再利用元）である。すなわち、配列アクセスＢ［ｉ−１］［ｊ−１］に再利用されるデータを供給するための供給源である。したがって、Ｂ［ｉ］［ｊ］でアクセスしたデータをシフトレジスタにコピーするため、図２の第３行の実行文が必要となる。しかし、この初期化だけではレジスタＢ＿ｒｅｇ＿０に値が代入されるだけで、図２の第６行のレジスタＢ＿ｒｅｇ＿５には値が存在しない。したがって、シフトレジスタ内に値が満たされるまでは、レジスタＢ＿ｒｅｇ＿５に対して、図２の第５行のように、適切な値を設定する必要がある。
【００１２】
既存手法では、図２に示すスカラリプレイス及び初期化を適用した後、ループピーリング（Loop peeling）を適用し、ループを分割することにより、初期化に伴って発生した配列アクセスがメインループから除去される。ここで、ループピーリングとは、ループの最初、または、最後の繰り返しのいくつかを、メインループから分けて実行することであり、結果としてメインループ内の配列アクセスを繰り返し実行する図２の第５行のような実行文をループの外側に移動することであり、メインループ実行の開始間隔を短縮し、性能を向上させる技術である。
【００１３】
図３は、図２に示す動作記述に対してループピーリングを適用した結果を示している。ループピーリングを適用したことにより、図３の第１２行乃至第１６行に示す最も内側のループでは、ループ１回あたり配列Ｂへのアクセスを１回にすることができる。しかしながら、ループピーリングによってコード量が増加するため、高位合成を使用してハードウェア化する際、面積を増加させる要因となる。
【００１４】
そこで、本実施形態は、ループピーリングを必要としないシフトレジスタの初期化について説明する。
【００１５】
（実施形態）
以下、図面を参照して実施形態について、具体的に説明する。
【００１６】
本実施形態は、例えば動作記述の最適化による集積回路設計の最適化について説明する。動作記述の最適化は、高位合成の下位概念であり、動作記述の最適化も高位合成と同様に、Ｃ言語などのプログラミング言語により構成された動作記述からＲＴＬ記述を生成する際に使用され、例えば画像処理やオーディオ信号処理回路の設計に広く適用されている。しかし、本実施形態は、動作記述の最適化に限定されるものではなく、高位合成に適用することも可能である。
【００１７】
（装置構成）
図４は、本実施形態が適用される動作記述の最適化装置の一例を示している。動作記述の最適化装置１０は、例えばコンピュータにより構成され、このコンピュータは、例えば制御部１１に接続された入力装置１２、出力装置１３、記憶装置１４、メモリ１５により構成されている。
【００１８】
制御部１１は、例えばＣＰＵ（Central Processing Unit）であり、メモリ１５に記憶されたプログラムに従って所定の動作を実行する。
【００１９】
入力装置１２は、半導体集積回路の動作を示す動作記述や、半導体集積回路の制約等の動作記述の最適化処理に必要な情報を入力するための例えばキーボードである。
【００２０】
出力装置１３は、生成された動作記述等を出力するものであり、例えばプリンタにより構成されている。
【００２１】
記憶装置１４は、例えばハードディスク装置やフラッシュメモリなどのコンピュータにより読み取り可能な記憶媒体である。この記憶装置１４には、例えば制御部１１の動作に必要なプログラムや、動作記述の最適化の処理に必要なプログラム、或いは例えばＣ言語による動作記述などが記憶される。
【００２２】
メモリ１５は、例えばＲＡＭ（Random Access Memory）であり、記憶装置１４から読み出された制御部１１の動作に必要なプログラムなどがロードされる。
【００２３】
図５は、図４に示す制御部１１と記憶装置１４により実現される機能を示している。
【００２４】
制御部１１は、解析処理部１１ａ、第１の処理部１１ｂ、第２の処理部１１ｃ、及び第３の処理部１１ｄを有している。
【００２５】
尚、記憶装置１４は、制御部１１に直接接続されている必要はなく、ネットワークを介して接続されていてもよい。
【００２６】
また、記憶装置１４には、動作記述１４ａと、制御部１１の動作の過程において生成された例えば配列アクセスの範囲情報１４ｂ、及び最適化された動作記述１４ｃが格納される。
【００２７】
（動作）
図６は、制御部１１の動作を示すものであり、図６を参照して図５に示す各機能について説明する。
【００２８】
先ず、制御部１１の解析処理部１１ａは、記憶装置１４から動作記述１４ａを読み出し、動作記述１４ａ中の配列アクセスの添え字が取る範囲を解析する（Ｓ１１）。
【００２９】
図７は、記憶装置１４に記憶された動作記述の一例を示している。配列アクセスは、“ｆｏｒ”ループ中で出現する配列への実際の参照のことであり、動作記述が図７に示すような場合、配列Ａに関して、１つの配列アクセスＡ[ｉ]［ｊ］が含まれ、配列Ｂに関して、３つの配列アクセスＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ−１］［ｊ］が含まれる。
【００３０】
また、配列アクセスの添え字とは、例えば配列アクセスＢ［ｘ］［ｙ］に対して、“ｘ”及び“ｙ”のことを言い、図７に示す例えばＢ［ｉ−１］［ｊ］の場合、“ｉ−１”“ｊ”のことを言う。添え字が取る範囲とは、設定されたループ中において、添え字が変化する範囲のことを言う。したがって、配列アクセスの添え字が取る範囲を解析するとは、ループの実行を制御する変数、すなわちループ変数“ｉ”“ｊ”が、ループで指定された範囲（図７において、１＜＝ｉ＜＝３２、１＜＝ｊ＜＝１６）を動く際に、配列アクセスの添え字が動く範囲を調べることである。例えば上記３つの配列アクセスＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ−１］［ｊ］に対して、添え字の動く範囲は、次のようになる。
【００３１】
Ｂ［ｉ］［ｊ＋１］  ：  １＜＝ｉ＜＝３２、  ２＜＝ｊ＋１＜＝１７
Ｂ［ｉ］［ｊ］      ：  １＜＝ｉ＜＝３２、  １＜＝ｊ＜＝１６
Ｂ［ｉ−１］［ｊ］  ：  ０＜＝ｉ−１＜＝３１、  １＜＝ｊ＜＝１６
図８に示す破線は、配列アクセスＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ−１］［ｊ］の添え字の範囲を示している。
【００３２】
次に、解析処理部１１ａは、上記解析された配列アクセスの添え字が取る範囲に基づき、配列の添え字の取る範囲を解析する（Ｓ１２）。
【００３３】
配列の添え字の取る範囲とは、配列毎に、各配列アクセスの添え字の取る範囲の和集合を求めることである。例えば図７に示す動作記述において配列Ｂの添え字［Ｘ］［Ｙ］の取る範囲は、次のようになる。
【００３４】
｛１＜＝Ｘ＜＝３２ ∪ １＜＝Ｘ＜＝３２ ∪ ０＜＝Ｘ＜＝３１｝
＝｛０＜＝Ｘ＜＝３２｝、
｛２＜＝Ｙ＜＝１７ ∪ １＜＝Ｙ＜＝１６ ∪ １＜＝Ｙ＜＝１６｝
＝｛１＜＝Ｙ＜＝１７｝
図８に示す実線の枠は、二次元配列Ｂの添え字［Ｘ］［Ｙ］が取り得る範囲を示している。
【００３５】
上記のようにして解析された配列アクセスの添え字が取る範囲、及び配列の添え字の取る範囲の情報は、記憶装置１４内に配列アクセスの範囲情報１４ｂとして記憶される。
【００３６】
次に、上記解析結果に基づき、第１の処理部１１ｂにより、ループ範囲が変更される（Ｓ１３）。
【００３７】
すなわち、上記配列の添え字が取る範囲に基づき、ループ変数の初期値と最終値が変更される。例えば、図７に示す動作記述において、各配列アクセスに再利用データの供給源となる配列アクセス、すなわち、ジェネレータとしての配列アクセスＢ［ｉ］［ｊ＋１］の添え字が、“ｉ、ｊ＋１”であり、これら添え字の取る範囲が配列の添え字の取る範囲を含むようになればよい。このため、これら添え字は、それぞれ０＜＝ｉ＜＝３２、且つ、１＜＝ｊ＋１＜＝１７となればよい。すなわち、変更後のループ変数の範囲は、０＜＝ｉ＜＝３２、０＜＝ｊ＜＝１６となり、変更後のループ変数の範囲のもとで、再利用ジェネレータとなる配列アクセスＢ［ｉ］［ｊ＋１］と同じ添え字を持つ配列アクセスＢ［ｉ］［ｊ＋１］の添え字の取る範囲は各配列アクセスの添え字の取り得る範囲を包含する範囲となる。したがって、図７に示す元の動作記述と同じ動作を保つため、ループ範囲が下記のように変更される。
【００３８】
ｆｏｒ（ｉ＝０；ｉ＜３３；ｉ＋＋）｛
ｆｏｒ（ｊ＝０；ｊ＜１７；ｊ＋＋）｛
ｉｆ（（ｉ＞＝１）＆＆（ｊ＞＝１））｛
尚、変更するループ範囲の決定方法は、換言すると次のようになる。
【００３９】
図７に示す初期化が必要な動作記述において、配列の添え字の取る範囲が、ジェネレータとなる配列アクセスの添え字の取る範囲に含まれること。
【００４０】
例えば、図７に示す動作記述において、ジェネレータとしての配列アクセスＢ［ｉ］［ｊ＋１］の取る範囲は、前述したように、１＜＝ｉ＜＝３２、２＜＝ｊ＋１＜＝１７である。配列Ｂの添え字の取る範囲は、Ｂ［Ｘ］［Ｙ］｛０＜＝Ｘ＜＝３２｝且つ｛１＜＝Ｙ＜＝１７｝である。再利用ジェネレータとなる配列アクセスＢ［ｉ］［ｊ＋１］と同じ添え字を持つ配列アクセスに対して、添え字の取る範囲を、配列の添え字の取る範囲と一致させるのに必要なループ変数の範囲が求められる。図７に示す動作記述の場合、再利用ジェネレータの添え字が“ｉ、ｊ＋１”であり、これらの添え字が、それぞれ、０＜＝ｉ＜＝３２、且つ１＜＝ｊ＋１＜＝１７となればよいため、ループ変数の範囲は、０＜＝ｉ＜＝３２、且つ０＜＝ｊ＜＝１６となる。
【００４１】
図９は、ループ範囲の変更後の動作記述を示している。図９の第１行において、“ｉ＝１”から“ｉ＝０”に変更され、第２行において、“ｊ＝１”から“ｊ＝０”に変更され、第３行に条件文が挿入されている。
【００４２】
この後、第２の処理部１１ｃにより、配列アクセスが追加される（Ｓ１４）。具体的には、図１０の第３行に示すように、配列の添え字の範囲を全て含む配列アクセス“Ｂｒｅｇ０＝Ｂ［ｉ］［ｊ＋１］”が最も内側のループの先頭に追加される。
【００４３】
次に、第３の処理部１１ｄにより、配列アクセスが削除される。
【００４４】
具体的には、複数の配列アクセス間の再利用の依存関係が解析される（Ｓ１５）。
【００４５】
配列アクセスＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ―１］［ｊ］は、配列アクセスＢ［ｉ］［ｊ＋１］のデータがＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ―１］［ｊ］に再利用されるため、依存関係にある。
【００４６】
この動作記述に対して、配列アクセス間の再利用の関係が解析され、再利用距離が計算される。
【００４７】
図１１は、図１０に示す動作記述に対応する再利用グラフを示している。再利用グラフとは、各配列アクセスに対して、再利用データの供給源（再利用元）としてのジェネレータのノード、又は供給先（以下、再利用先とも言う）のノードを作成し、供給源のノードと供給先のノードをエッジと称する矢印で接続したものである。このエッジには、再利用ベクトルが書き添えられる。
【００４８】
図１１（ａ）（ｂ）に示す再利用グラフにおいて、４つの丸印は、配列アクセスＢ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ＋１］、Ｂ［ｉ］［ｊ］、Ｂ［ｉ―１］［ｊ］を表し、エッジにより再利用関係が表されている。エッジの付け根が再利用元としてのジェネレータであり、エッジの先が再利用先である。
【００４９】
図１１（ａ）（ｂ）において、二重丸で囲まれた配列アクセスＢ［ｉ］［ｊ＋１］は、配列アクセスＢ［ｉ］［ｊ＋１］から外側に向いたエッジのみが接続され、配列アクセスＢ［ｉ］［ｊ＋１］に向いたエッジが接続されていない。このため、二重丸で囲まれた配列アクセスＢ［ｉ］［ｊ＋１］は、ジェネレータである。
【００５０】
図１１（ａ）に示すように、エッジには、再利用ベクトル＜ｄｙ、ｄｘ＞が付加されている。再利用ベクトル＜ｄｙ、ｄｘ＞は、エッジで接続された配列アクセスの添え字同士の差により構成されている。例えば、配列アクセスＢ［ｉ］［ｊ＋１］とＢ［ｉ］［ｊ＋１］との再利用ベクトルは、＜０、０＞として求められ、配列アクセスＢ［ｉ］［ｊ＋１］とＢ［ｉ］［ｊ］との再利用ベクトルは、＜０、１＞として求められ、配列アクセスＢ［ｉ］［ｊ＋１］とＢ［ｉ−１］［ｊ］との再利用ベクトルは、＜１、１＞として求められる。
【００５１】
次に、上記配列アクセス間の依存関係に基づき、第３の処理部１１ｄにより、再利用距離ｄが算出される（Ｓ１６）。
【００５２】
図１１（ａ）に示す再利用ベクトル＜ｄｙ、ｄｘ＞は、各配列アクセスがジェネレータに対して何回ループが回った後に再利用されるかを表している。例えば再利用ベクトル＜ｄｙ、ｄｘ＞（２重ループの時）の場合、外側ループがｄｙ回、内側ループがｄｘ回回った後、再利用元から再利用先に再利用が発生することを示す。
【００５３】
図１１（ｂ）に示す再利用距離ｄは、各配列アクセスがジェネレータに対して何回ループが回った後に再利用されるかを、最も内側のループ回数に換算して、表している。再利用距離ｄは、図１１（ａ）に示す再利用ベクトルに基づき計算される。すなわち、再利用距離ｄは、再利用ベクトル＜ｄｙ，ｄｘ＞、ループ回数をｊとした場合、“ｄ＝ｄｙ×ｊ＋ｄｘ”で表される。図１１（ａ）に示す再利用ベクトル＜０、０＞の場合、内側のループ回数は図１０より１７回である。これに基づき、再利用距離ｄ１を計算すると、ｄ１＝０×１７＋０＝０となる。また、再利用ベクトル＜０、１＞の場合、再利用距離ｄ３は、ｄ３＝０×１７＋１＝１となる。さらに、再利用ベクトル＜１、１＞の場合、再利用距離ｄ４は、ｄ４＝１×１７＋１＝１８となる。
【００５４】
図１２は、配列アクセスの削除に必要な情報をまとめた表であり、アクセス種類、配列アクセス、及び再利用距離により表されている。この表は、注目する配列(配列Ｂ)の再利用グラフの各矢印を、再利用距離の小さい順に上から並べたものである。
【００５５】
この後、第３の処理部１１ｄにより、シフトレジスタの記述が、最も内側のループの最後部に追加され、さらに、配列アクセスが一時変数アクセスに置き換えられる（Ｓ１７）。
【００５６】
シフトレジスタのサイズ、すなわち、シフトレジスタを構成するレジスタの数は、再利用距離の最大値に設定される。この例の場合、再利用距離の最大値は、ｄ４＝１８であるため、シフトレジスタは、１８個のレジスタにより構成される。
【００５７】
さらに、再利用先の配列アクセスが対応する再利用距離の番号を持つシフトレジスタを参照するように配列アクセスが一時変数アクセスに置き換えられ、動作記述が最適化される。
【００５８】
図１３は、配列アクセスが削除され、最適化された動作記述の例を示している。図１３に示す第５行において、再利用先の配列アクセスが再利用距離の番号を持つ一時変数アクセス（レジスタアクセス）に置き換えられ、第７行乃至第２４行にシフトレジスタの記述が追加されている。このシフトレジスタの記述は、ループが１回りする毎にＢｒｅｇｉのデータがＢｒｅｇｉ＋１にシフトされることを示している。
【００５９】
図５に示すように、上記最適化された動作記述１４ｃは、記憶装置１４に記憶される。
【００６０】
（実施形態の効果）
上記実施形態によれば、動作記述に含まれる各配列アクセスの添え字が取り得る範囲、及びこれら配列アクセスの添え字が取る範囲を包含する範囲を解析し、この解析結果に基づき、ループ範囲を拡張することによりループ範囲を変更し、この変更したループ範囲に基づき、配列アクセスを追加し、この追加した配列アクセスを含む複数の配列アクセスの再利用関係を解析し、解析された再利用関係から再利用距離を算出し、この算出された再利用距離の最大値に対応するサイズのシフトレジスタを動作記述に追加し、さらに、配列アクセスを再利用距離の番号を有するレジスタへのアクセスに置き換え、このレジスタによりシフトレジスタを参照するようにしている。このため、既存のループピーリングを用いる場合に比べて、動作記述のコード量を削減でき、冗長なシフトレジスタの追加を防止することができる。したがって、生成されるハードウェアの面積の増加を防止することが可能である。
【００６１】
具体的には、既存のループリーリングを用いた初期化手法の場合、ループを分割するため、複数のループが作られてしまうが、本実施形態の場合１つのループによるスカラリプレイスが可能となるため、コードの短縮が可能である。
【００６２】
図１４乃至図１６は、図７に示す動作記述に対して、既存のスカラリプレイスとループピーリングを適用した場合の動作記述を示している。
【００６３】
図１４は、図７に示す動作記述に対して、配列アクセスの削除と初期化用配列アクセスを追加した後のコードを示している。
【００６４】
図１５は、図１４に示す動作記述から、外側のループ（ループｉ）を１回分、ループピーリングしたコードを示している。
【００６５】
図１６は、図１５に示す動作記述に対して、図１５の第２７行に示す内側のループ（ループｊ）を１回分、ループピーリングしたコードを示している。第５０行乃至第６８行に示すように、ループピーリングにより、破線で囲まれたメインループの記述から、初期化用の配列アクセスが全て削除されている。
【００６６】
図１６に示すように、図７に示す元の動作記述に対して、既存のスカラリプレイスとループピーリングを実行した場合のコード量と、図１３に示す本実施形態によるループピーリングを用いないスカラリプレイス適用後のコード量を比較すると、既存手法の場合、図１６に示すように、７０行のコードが必要である。これに対して、本実施形態の場合、２５行のコードで構成される。このため、本実施形態の場合、既存のスカラリプレイスとループピーリングを用いた場合に比べて、コード量を６３％削減することができる。したがって、生成されるハードウェアの面積を既存手法に比べて大幅に低減することが可能である。
【００６７】
しかも、ハードウェアの面積を低減し、冗長なレジスタの増加を防止することが可能であるため、高速動作が可能となる。
【００６８】
尚、図１１（ａ）（ｂ）に示す再利用グラフ、図１２に示す再利用発生グラフの作成は、任意であり、算出された再利用距離に基づき、配列アクセスをシフトレジスタに置き換えることも可能である。
【００６９】
その他、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００７０】
１０…動作記述の最適化装置、１１…制御部、１４…記憶装置、１１ａ…解析処理部、１１ｂ…第１の処理部、１１ｃ…第２の処理部、１１ｄ…第３の処理部、１４ａ…動作記述、１４ｂ…配列アクセスの範囲情報、１４ｃ…最適化された動作記述。
【図１】
2014225201.tif 000003
【図２】
2014225201.tif 000004
【図３】
2014225201.tif 000005
【図４】
2014225201.tif 000006
【図５】
2014225201.tif 000007
【図６】
2014225201.tif 000008
【図７】
2014225201.tif 000009
【図８】
2014225201.tif 000010
【図９】
2014225201.tif 000011
【図１０】
2014225201.tif 000012
【図１１】
2014225201.tif 000013
【図１２】
2014225201.tif 000014
【図１３】
2014225201.tif 000015
【図１４】
2014225201.tif 000016
【図１５】
2014225201.tif 000017
【図１６】
2014225201.tif 000018