(57)【要約】 【課題】冗長な配列アクセスが動作記述中に追加されることを防止し、生成されるハードウェアの面積の増加を防止して高速動作を可能とする半導体装置の設計装置、設計方法、設計プログラムを提供する。【解決手段】解析部は、記憶部に記憶された動作記述より、配列アクセス間の再利用関係を添え字及び条件文の条件に基づき解析し、配列アクセス間のデータの再利用距離、配列アクセス間の前記再利用距離の差、及び前記配列アクセスの再利用が発生する条件を算出する。第１の処理部は、再利用距離の差と規定値に基づき循環バッファの記述、又はシフトレジスタの記述を追加する。第２の処理部は、配列アクセスを、シフトレジスタ、又は循環バッファの入出力端を表す一時変数アクセスに置き換え、条件文を追加して、最適化された動作記述を生成する。【選択図】図５
2014225200.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. dissertation, 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
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、冗長なメモリアクセスが動作記述中に残ることを防止し、生成されるハードウェアの面積の増加を防止して高速動作を可能とする半導体装置の設計装置、設計方法、設計プログラムを提供するものである。
【課題を解決するための手段】
【０００８】
本発明の半導体装置の設計装置の態様は、複数の配列アクセス及び条件文を含むデジタル回路の動作が記述された動作記述が記憶された記憶部と、前記記憶部に記憶された前記動作記述より、前記配列アクセス間の再利用関係を前記条件文に基づき解析し、前記配列アクセス間のデータの再利用距離、前記配列アクセス間の前記再利用距離の差、及び前記配列アクセスの再利用が発生する条件を算出する解析部と、前記解析部により算出された前記再利用距離が長い方から順に、前記再利用距離の差と規定値とを比較し、前記再利用距離の差が前記規定値以上である場合、前記動作記述に循環バッファの記述を追加し、前記再利用距離の差が前記規定値未満である場合、前記動作記述にシフトレジスタの記述を追加する第１の処理部と、前記動作記述の配列アクセスを、前記循環バッファの入出力端に対応する一時変数へのアクセス、又はシフトレジスタの入出力端に対応する一時変数へのアクセスに置き換え、前記一時変数へのアクセスの記述に条件文を追加して、動作記述を生成する第２の処理部とを具備することを特徴とする。
【図面の簡単な説明】
【０００９】
【図１】動作記述の一例を示す図。
【図２】図１に示す動作記述に対応する再利用グラフの例を示す図。
【図３】既存手法による最適化された動作記述の一例を示す図。
【図４】本実施形態が適用される動作記述の最適化装置の一例を示す構成図。
【図５】図４に示す制御部と記憶装置の機能を示す構成図。
【図６】本実施形態の動作を示すフローチャート。
【図７】本実施形態の動作記述に対応する再利用グラフの例を示す図。
【図８】本実施形態の再利用条件を含む解析結果を示す図。
【図９】本実施形態に係る再利用の発生状態を示す図。
【図１０】本実施形態による処理途中の動作記述の一例を示す図。
【図１１】本実施形態による最適化された動作記述の一例を示す図。
【図１２】既存手法により生成された回路の一例を示す図。
【図１３】本実施形態により生成された回路の一例を示す図。
【図１４】本実施形態に係り、ループ回数がパラメータである場合の動作記述の一例を示す図。
【図１５】図１４に示す例の場合における再利用条件を含む解析結果を示す図。
【図１６】図１４に示す例の場合における再利用の発生状態を示す図。
【図１７】図１４に示す例の場合における最適化された動作記述の一例を示す図。
【図１８】最適化された動作記述に基づき生成された回路の一例を示す図。
【発明を実施するための形態】
【００１０】
前述したように、高位合成を使用して動作記述からハードウェアを自動生成する場合において、配列アクセスは、メモリアクセスに対応する。メモリアクセスは、長時間を要するため、配列アクセスを削除することが有効である。また、前述したスカラリプレイスは、メモリへのアクセスをレジスタのアクセスに置換することにより、メモリアクセス数を削減する方法である。すなわち、スカラリプレイスは、メモリから読み出されたデータをシフトレジスタに保持し、このシフトレジスタに保持されたデータを再利用することにより、同じメモリからの同時アクセスを削減するものである。
【００１１】
スカラリプレイスを行うため、メモリからアクセスしたデータをシフトレジスタに保存し、配列アクセス間の依存関係に基づき、シフトレジスタに保存されたデータが再利用される機会を解析する必要がある。
【００１２】
配列アクセス間の依存関係とは、同じメモリ領域に複数回アクセスがあった場合、配列アクセス間に依存があると見做される。依存としては、次の４種類がある。読み出し後の読み出し（read after read : RAR）、書き込み後の読み出し（read after write : RAW）、読み出し後の書き込み（write after read : WAR）、及び書き込み後の書き込み（write after write : WAW）。このうち、再利用を行うことが可能な依存は、ＲＡＲ、ＲＡＷ、ＷＡＷの３つである。
【００１３】
例えば図１に示すＣ言語により記載された動作記述が入力された場合、配列アクセスＡ［ｙ］［ｘ］、Ａ［ｙ］［ｘ−２］、Ａ［０］［ｘ］、Ａ［ｙ−３］［ｘ］は、配列アクセスＡ［ｙ］［ｘ］のデータがＡ［ｙ］［ｘ−２］、Ａ［０］［ｘ］、Ａ［ｙ−３］［ｘ］に再利用されるため、依存関係にある。
【００１４】
この動作記述に対して、配列アクセス間の再利用の関係が解析され、再利用距離が計算される。この解析結果を利用して、動作記述中にシフトレジスタが挿入され、配列アクセスが一時変数アクセス、すなわち、シフトレジスタへのアクセスに置換される。
【００１５】
ここで、本実施形態に適用される用語を次のように定義する。
【００１６】
図２（ａ）（ｂ）は、図１に示す動作記述に対応する再利用グラフを示している。再利用グラフとは、各配列アクセスから再利用データの供給源（以下、再利用元、ジェネレータとも言う）のノード、又は、供給先（以下、再利用先とも言う）のノードを作成し、供給源のノードと供給先のノードをエッジと称する矢印で接続したものである。このエッジには、再利用ベクトルが書き添えられる。
【００１７】
図２（ａ）（ｂ）に示す再利用グラフにおいて、それぞれ４つの丸印は、配列アクセスＡ［ｙ］［ｘ］、Ａ［ｙ］［ｘ−２］、Ａ［０］［ｘ］、Ａ［ｙ−３］［ｘ］を表し、エッジにより再利用関係が表されている。エッジの付け根が再利用元としてのジェネレータであり、エッジの先が再利用先である。
【００１８】
図２（ａ）（ｂ）において、配列アクセスＡ［ｙ］［ｘ］は、配列アクセスＡ［ｙ］［ｘ］から外側に向いたエッジのみが接続され、配列アクセスＡ［ｙ］［ｘ］に向いたエッジが接続されていない。このため、配列アクセスＡ［ｙ］［ｘ］は、ジェネレータである。
【００１９】
エッジには、再利用ベクトル＜ｄｙ、ｄｘ＞が付加されている。再利用ベクトル＜ｄｙ、ｄｘ＞は、エッジで接続された配列アクセスの添え字同士の差により構成されている。例えば、配列アクセスＡ［ｙ］［ｘ］とＡ［ｙ］［ｘ−２］との再利用ベクトルは、＜０、２＞として求められ、配列アクセスＡ［ｙ］［ｘ］とＡ［ｙ−３］［ｘ］との再利用ベクトルは、＜３、０＞として求められる。
【００２０】
図２（ａ）に示す再利用ベクトル＜ｄｙ、ｄｘ＞は、各配列アクセスがジェネレータに対して何回ループが回った後に再利用されるかを表している。例えば再利用ベクトル＜ｄｙ、ｄｘ＞（２重ループの時）の場合、外側ループがｄｙ回、内側ループがｄｘ回回ったら、再利用元から再利用先に再利用が発生することを示す。
【００２１】
図２（ｂ）に示す再利用距離ｄは、各配列アクセスがジェネレータに対して何回ループが回った後に再利用されるかを、最も内側のループ回数に換算して、表している。再利用距離ｄは、図２（ａ）に示す再利用ベクトルに基づき計算される。すなわち、再利用距離ｄは、再利用ベクトル＜ｄｙ，ｄｘ＞、内側のループ回数をｊとした場合、“ｄ＝ｄｙ×ｊ＋ｄｘ”で表される。図２（ａ）に示す再利用ベクトル＜３，０＞の場合、内側のループ回数は図１より１０回である。これに基づき、再利用距離ｄを計算すると、３×１０＋０＝３０となる。また、再利用ベクトル＜０、２＞の場合、０×１０＋２＝２となる。３重以上のループの場合も同様の方法で再利用距離ｄを計算でき、例えば非特許文献３に計算方法が掲載されている。
【００２２】
また、内側のループが３０回回った後、配列アクセスＡ［ｙ］［ｘ］にてストアされたデータが配列アクセスＡ［ｙ−３］［ｘ］にてロードされる。したがって、３０個のレジスタにより構成されるシフトレジスタを用意し、配列アクセスＡ［ｙ］［ｘ］でライトアクセスするデータをシフトレジスタの先頭のレジスタに格納し、内側ループが回転する毎にシフトレジスタのデータをシフトし、配列アクセスＡ［ｙ−３］［ｘ］のリードアクセスをシフトレジスタの最後のレジスタアクセスに置き換えることにより、配列アクセスＡ［ｙ−３］［ｘ］をシフトレジスタへのアクセスに置き換えることができる。
【００２３】
図３は、既存の手法により配列アクセスがシフトレジスタへのアクセスに置換された様子を示している。図３に示すように、図１に示す配列アクセスＡ［ｙ］［ｘ−２］、Ａ［ｙ−３］［ｘ］が一時変数アクセスｓ２、ｓ３０（第５行、第８行）に置換され、さらに、第１０行乃至第３９行に示すように、Ａ［ｙ］［ｘ］からＡ［ｙ−３］［ｘ］の再利用、及びＡ［ｙ］［ｘ］からからＡ［ｙ］［ｘ−２］への再利用のために、シフトレジスタｓ１〜ｓ３０が追加される（第１０行乃至第３９行）。すなわち、合計３０個のレジスタが追加される。
【００２４】
上記既存手法の場合、シフトレジスタをフリップフロップ回路により実現する記述（ｓ３０＝ｓ２９、ｓ２９＝ｓ２８、…）を必要とするため、大規模な面積のシフトレジスタが導入される。
【００２５】
さらに、図２（ａ）に破線の矢印で示すように、再利用ベクトルの形式に制限があり、例えば画像処理において頻出する添え字に定数が含まれる配列アクセスＡ［０］［ｘ］（図３、第７行）を削除することが不可能である。この結果、メモリアクセスの削減が不十分となり、性能向上が不十分である。
【００２６】
さらに、削除できない配列アクセスＡ［０］［ｘ］があるため、配列Ａ［ｙ］［ｘ］も削除することができず、配列Ａを格納するメモリを残す必要がある。したがって、回路面積が増大し、動作周波数が低下するという問題がある。
【００２７】
そこで、本実施形態は、動作記述に対する配列アクセス間の再利用関係を、再利用の発生条件も考慮して解析する。さらに、再利用距離、具体的には距離の差に基づき、配列アクセスをシフトレジスタへのアクセス、又は循環バッファへのアクセスで記述する。これにより、さらなる配列アクセスの削減を可能とし、回路面積を削減でき、動作周波数の低下を防止可能とする。
【００２８】
（実施形態）
以下、実施形態について、具体的に説明する。
【００２９】
本実施形態は、例えば動作記述の最適化による集積回路設計の最適化について説明する。動作記述の最適化は、高位合成の下位概念であり、動作記述の最適化も高位合成と同様に、Ｃ言語などのプログラミング言語により構成された動作記述からＲＴＬ記述を生成する際に使用され、例えば画像処理やオーディオ信号処理回路の設計に広く適用されている。しかし、本実施形態は、動作記述の最適化に限定されるものではなく、高位合成に適用することも可能である。
【００３０】
（装置構成）
図４は、本実施形態が適用される動作記述の最適化装置の一例を示している。動作記述の最適化装置１０は、例えばコンピュータにより構成され、このコンピュータは、例えば制御部１１に接続された入力装置１２、出力装置１３、記憶装置１４、メモリ１５により構成されている。
【００３１】
制御部１１は、例えばＣＰＵ（Central Processing Unit）であり、メモリ１５に記憶されたプログラムに従って所定の動作を実行する。
【００３２】
入力装置１２は、半導体集積回路の動作を示す動作記述や、半導体集積回路の制約等の動作記述の最適化処理に必要な情報を入力するための例えばキーボードである。
【００３３】
出力装置１３は、生成された動作記述等を出力するものであり、例えばプリンタにより構成されている。
【００３４】
記憶装置１４は、例えばハードディスク装置やフラッシュメモリなどのコンピュータにより読み取り可能な記憶媒体である。この記憶装置１４には、例えば制御部１１の動作に必要なプログラムや、動作記述の最適化の処理に必要なプログラム、或いは例えばＣ言語による動作記述などが記憶される。
【００３５】
メモリ１５は、例えばＲＡＭ（Random Access Memory）であり、記憶装置１４から読み出された制御部１１の動作に必要なプログラムなどがロードされる。
【００３６】
尚、記憶装置１４は、制御部１１に直接接続されている必要はなく、ネットワークを介して接続されていてもよい。
【００３７】
図５は、図４に示す制御部１１と記憶装置１４により実現される機能を示している。
【００３８】
制御部１１は、解析処理部１１ａ、第１の処理部１１ｂ、及び第２の処理部１１ｃを有している。
【００３９】
また、記憶装置１４には、動作記述１４ａと、制御部１１の動作の過程において生成された例えば配列アクセス間の再利用情報１４ｂ、及び最適化された動作記述１４ｃが格納される。
【００４０】
（動作）
図６は、制御部１１の動作を示すものであり、図６を参照して図５に示す各機能について説明する。
【００４１】
先ず、制御部１１の解析処理部１１ａは、記憶装置１４から動作記述１４ａを読み出し、動作記述１４ａ中の“ｉｆ条件文”及び配列アクセスの添え字を考慮して配列アクセス間の再利用関係を解析する（Ｓ１１）。この解析により、図７（ａ）（ｂ）に示す再利用グラフを生成するため、再利用ベクトルが生成される。
【００４２】
例えば図１に示す動作記述の場合、配列アクセスは、前述したように、第３行のＡ［ｙ］［ｘ］、第４行のＡ［ｙ］［ｘ−２］、第６行のＡ［０］［ｘ］、第７行のＡ［ｙ−３］［ｘ］であり、ジェネレータとしての配列アクセスＡ［ｙ］［ｘ］と、再利用先としての配列アクセスＡ［ｙ−３］［ｘ］、Ａ［ｙ］［ｘ−２］、Ａ［０］［ｘ］との間の再利用ベクトルが生成される。このとき、動作記述中の“ｉｆ条件文”及び配列アクセスの添え字を考慮して配列アクセス間の再利用関係が調べられる。
【００４３】
すなわち、配列アクセスＡ［０］［ｘ］は、図１に示す第５行、第６行の記述より、ループ変数ｙが、ｙ＝１又はｙ＝２の時、Ａ［０］［ｘ］がＡ［ｙ］［ｘ］でアクセスされた値を再利用することが分かる。このため、図７（ａ）に示すように、配列アクセスＡ［ｙ］［ｘ］と配列アクセスＡ［０］［ｘ］の間には、ｙ＝１のときの再利用ベクトル＜１、０＞と、ｙ＝２のときの再利用ベクトル＜２、０＞が生成される。
【００４４】
また、配列アクセスＡ［ｙ］［ｘ］と配列アクセスＡ［ｙ−３］［ｘ］との間の再利用ベクトル＜３、０＞、及び配列アクセスＡ［ｙ］［ｘ］と配列アクセスＡ［ｙ］［ｘ−２］との間の再利用ベクトル＜０、２＞も同様にして生成される。
【００４５】
次いで、図７（ｂ）に示す配列アクセス間の再利用距離、及び再利用距離の差が算出される（Ｓ１２）。再利用距離の差については、後述する。
【００４６】
この後、動作記述に基づき、再利用グラフ中の矢印に付加する再利用発生条件、すなわち、ｙ＝１、ｙ＝２などが算出される（Ｓ１３）。
【００４７】
ここで、再利用発生条件とは、再利用先の配列アクセスにて再利用が発生するときに、成り立つ条件を言う。例えば本実施形態において、ループ変数ｙ＝１又はｙ＝２の時、Ａ［０］［ｘ］がＡ［ｙ］［ｘ］でアクセスされた値を再利用する。再利用条件は、動作記述に含まれる配列アクセスの添え字、及び“ｉｆ条件文”を解析することにより導出される。
【００４８】
次に、上記解析結果に基づき、再利用発生条件を含んだ表が生成される（Ｓ１４）。この再利用発生条件を含んだ表は、例えば配列アクセス間の再利用情報１４ｂとして、記憶装置１４内に保存される。
【００４９】
図８は、上記解析結果に基づき、生成された再利用発生条件を含んだ表を示し、図９は、再利用発生条件を含んだ表に基づき生成された再利用発生グラフの一例を示している。
【００５０】
この表、及びグラフは、注目する配列(配列Ａ)の再利用グラフの各矢印を、再利用距離の小さい順に上から並べたものであり、アクセス種類、配列アクセス、再利用距離ｄｎ（ｎは、自然数）、配列アクセスの置き換え後の変数名、再利用距離の差、再利用発生条件を含んでいる。
【００５１】
図８、図９において、アクセス種類の先頭の要素は、ジェネレータであり、以下、各再利用先が記載されている。
【００５２】
配列アクセス、及び再利用距離は、再利用グラフの各配列アクセス、及び再利用距離に対応されている。
【００５３】
置き換え後の変数名は、再利用先としての配列アクセスを一時変数に置き換える際の変数名であり、この変数名は、例えば「s + 再利用距離」に設定されている。
【００５４】
再利用距離の差は、注目する再利用先の再利用距離と、注目する再利用先の一つ前の再利用先の再利用距離との差である。換言すると、再利用距離の小さい順に並べられた複数の再利用距離において、隣接する２つの再利用距離の差である。この再利用距離の差が、必要なシフトレジスタ、又は、循環バッファのサイズとなる。すなわち、再利用距離の差は、シフトレジスタを構成するレジスタの数、又は、循環バッファを構成するメモリの要素数を示している。
【００５５】
再利用発生条件としては、再利用グラフを用いて解析された配列アクセスＡ［０］［ｘ］に関するｙ＝１、ｙ＝２が設定されている。
【００５６】
次に、図５に示す第１の処理部１１ｂにおいて、記憶装置１４に記憶された再利用発生条件を含んだ表、再利用発生グラフ、及び動作記述に基づき、シフトレジスタ又は循環バッファの記述が、最も内側のループの最後部に追加される（Ｓ１５）。
【００５７】
具体的には、図９に示す再利用発生グラフを参照し、ジェネレータから最も離れたエッジから順に、シフトレジスタ、又は循環バッファの記述が追加される。換言すると、再利用距離が最も長い配列アクセスから順に、置き換え後にアクセスするシフトレジスタ、または循環バッファの記述が追加される。この時、例えば再利用距離の差に規定値を設定し、この規定値に基づき、シフトレジスタ、又は循環バッファの記述が追加される。
【００５８】
前述したように、再利用距離の差は、シフトレジスタを構成するレジスタの数、又は、循環バッファを構成するメモリの要素数を示している。再利用距離の差が大きい場合において、シフトレジスタを適用した場合、回路規模が増大する。このため、再利用距離の差に規定値を設定し、回路規模の増大を防止して、配列アクセスをシフトレジスタ、又は循環バッファに置き換えるようにしている。
【００５９】
本実施形態において、規定値は例えば“８”に設定される。再利用距離の差が“８”以上である場合、シフトレジスタにより構成した場合、大規模な回路となるため、循環バッファの記述が追加される。また、“８”未満である場合、シフトレジスタにより構成しても回路規模はそれ程増加しないため、シフトレジスタの記述が追加される。
【００６０】
図８に示す例の場合、Ａ［ｙ］［ｘ］→Ａ［ｙ］［ｘ−２］の再利用距離の差は“２”であるため、シフトレジスタの記述が追加される。シフトレジスタを構成するレジスタの数は、再利用距離の差、この場合、“２”に設定される。
【００６１】
また、Ａ［ｙ］［ｘ−２］→Ａ［０］［ｘ］（ｙ＝１のとき）の再利用距離の差、Ａ［０］［ｘ］（ｙ＝１のとき）→Ａ［０］［ｘ］（ｙ＝２のとき）の再利用距離の差、Ａ［０］［ｘ］（ｙ＝２のとき）→Ａ［ｙ−３］［ｘ］の再利用距離の差は、いずれも“８”以上である。このため、３つの循環バッファが追加される。循環バッファを構成するメモリの要素数は、再利用距離の差“８”“１０”“１０”にそれぞれ設定される。
【００６２】
シフトレジスタや循環バッファの入出力端の変数名は、再利用発生条件を含んだ表に基づき、それぞれ再利用グラフの矢印の再利用元、再利用先に対して置き換える一時変数名とされる。
【００６３】
尚、図１０は、第１の処理部１１ｂの段階において、シフトレジスタ、及び循環バッファの記述を追加したのみで、配列アクセスは削除されていない記述である。
【００６４】
次に、図５に示す第２の処理部１１ｃにおいて、配列アクセスが、追加されたシフトレジスタ、及び循環バッファの入出力端に対応する一時変数アクセスに置き換えられ、さらに、条件文が挿入されて、最適化された動作記述が生成される（Ｓ１６）。
【００６５】
すなわち、配列アクセスは、一時変数に置き換えられる。具体的には、再利用発生条件によって、複数の一時変数を参照する配列アクセス、例えばＡ［０］［ｘ］に対応して複数の一時変数を接続した一時変数が用意され、その変数に、再利用発生条件によって対応する一時変数が代入される。このようにして、動作記述が置き換えられ、最適化された動作記述が生成される。
【００６６】
図１１は、図１に示す動作記述に対して、シフトレジスタ、及び循環バッファの記述を追加し、配列アクセスを一時変数アクセスに置き換え、さらに、条件文を挿入した状態を示している。
【００６７】
図１１において、図１に示す第３行、第４行、第６行、第７行の配列アクセスが、第３行乃至第１１行において、一時変数アクセスに置き換えられている。特に、第７行、第８行の“ｉｆ条件文”において代入されている変数は、再利用発生条件により新たに追加された一時変数を示している。
【００６８】
さらに、第１３行乃至第２４行に３つの循環バッファが記述され、第２５行、第２６行にシフトレジスタが記述されている。これら循環バッファ、及びシフトレジスタの記述は、ジェネレータからの再利用距離が長い順に挿入されている。
【００６９】
３つの循環バッファｂｕｆ２、ｂｕｆ１、ｂｕｆ０の記述において、第１５行、第１６行、第１９行、第２０行、第２３行、第２４行に、バッファを構成するメモリのアクセス位置を指示するポインタｐ２、ｐ１、ｐ０の記述が付加されている。
【００７０】
図１２は、既存のスカラリプレイスにより、図１に示す動作記述の配列アクセスを一時変数アクセスに変換した場合におけるシフトレジスタの構成を示している。既存のスカラリプレイスの場合、前述したように、配列アクセスがシフトレジスタへのアクセスに置換される。このため、図１２に示すように、シフトレジスタを構成する３０個のレジスタｓ１〜ｓ３０が追加される。各レジスタｓ１〜ｓ３０は、フリップフロップ回路により構成されるため、回路面積が増大する。
【００７１】
一方、図１３は、本実施形態により、図１に示す動作記述の配列アクセスを一時変数アクセスに変換した場合の構成を示している。本実施形態の場合、３つの循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２と、５個のレジスタｓ１、ｓ２、ｓ１０、ｓ２０、ｓ３０により構成されている。このうち、レジスタｓ１、ｓ２はシフトレジスタを構成している。循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２は、それぞれ例えばデュアルポートメモリにより構成されている。循環バッファｂｕｆ０は、７個のメモリ要素により構成され、循環バッファｂｕｆ１及びｂｕｆ２は、９個のメモリ要素により構成されている。
【００７２】
上記循環バッファｂｕｆ０〜ｂｕｆ３において、用意するメモリ要素の数、メモリのアクセス位置を指示するポインタを復帰させるｉｆ文の条件式における値は、“対応するエッジの再利用距離−１”となる。
【００７３】
具体的には、バッファｂｕｆ０の場合、入出力端に接続される配列アクセスであるＡ［ｙ］［ｘ−２］とＡ［０］［ｘ］の間の再利用距離が“８”であるため、バッファｂｕｆ０のメモリ要素の数は、“８−１＝７”となり、バッファｂｕｆ１、２の場合、隣接するバッファまでの再利用距離が“１０”であるため、バッファｂｕｆ１、２のメモリ要素の数は、“１０−１＝９”となる。
【００７４】
これら循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２は、それぞれポインタｐ０、ｐ１、ｐ２によりメモリのアクセス位置が指示される。このポインタｐ０、ｐ１、ｐ２は、配列アクセスの添え字に対応している。このポインタｐ０、ｐ１、ｐ２により指示されたメモリ要素とレジスタｓ２、ｓ１０、ｓ２０、ｓ３０との間でデータがリード又はライトされる。すなわち、例えばバッファｂｕｆ０において、ポインタｐ０により指示されたメモリのデータはレジスタｓ１０に読み出され、この後、ポインタｐ０により指示されたメモリにレジスタｓ２のデータが書き込まれる。次いで、ポインタｐ０は次のメモリ要素を指示するようにインクリメントされる。次のループでも同様の動作が実行され、ポインタｐ０がインクリメントされる。ポインタｐ０は最後のメモリ要素まで指示すると、最初のループで指示した先頭のメモリ要素に復帰される。この後、次のループで、最初のループで指示した、先頭のメモリ要素に保持されているデータがレジスタｓ１０に読み出される。レジスタｓ１０に保持されているデータは、最初のループでｓ２から書き込まれたデータとなる。つまり、最初のループで最初のメモリ要素に保持されたデータが、設定されたループ回数の間、循環バッファｂｕｆ０に保持された後、レジスタｓ１０に読み出されたこととなり、シフトレジスタと同様の機能を得ることができる。
【００７５】
メモリにより構成された循環バッファは、フリップフロップ回路により構成されたシフトレジスタに比べて回路面積を格段に削減することが可能である。
【００７６】
上記のようにして、最適化された動作記述は、制御部１１を構成する第２の処理部１１ｃから出力され、記憶装置１４に、例えば最適化済み動作記述１４ｃとして格納される。
【００７７】
尚、上記の例は、循環バッファを実現するメモリが非同期メモリの場合である。循環バッファを同期メモリで実現する場合、シフトレジスタと同様、“再利用距離”が、循環バッファの要素数と等しくなる。その場合、出力コードを若干修正する必要がある。
【００７８】
（実施形態の効果）
上記実施形態によれば、動作記述に含まれる“ｉｆ条件文”に記述された再利用発生条件を考慮して配列アクセス間の再利用関係を解析し、各配列アクセス間の再利用距離が小さい順に並べた状態において、隣接する２つの再利用距離の差を算出するとともに、各配列アクセスを一時変数アクセスに置き換えた後の変数名、及び再利用の発生条件を設定した表、及びグラフを作成している。このため、配列アクセスの再利用関係を厳密に解析することが可能である。
【００７９】
さらに、再利用距離の差に規定値を設定し、上記グラフに基づき、ジェネレータから再利用距離が最も離れた配列アクセスから順に、再利用距離の差と規定値とを比較し、再利用距離の差が規定値以上である場合、配列アクセスをメモリにより構成された循環バッファに置き換え、再利用距離の差が規定値未満である場合、シフトレジスタに置き換えることにより、動作記述を最適化している。メモリにより構成された循環バッファは、シフトレジスタに比べて回路規模が小さいため、生成されるハードウェアの面積の増加を防止することが可能である。
【００８０】
しかも、配列アクセスの再利用関係を厳密に解析しているため、冗長な配列アクセスをさらに削除することが可能であり、高速動作が可能となる。
【００８１】
特に、画像処理の技術においては、添え字に定数を含んだ配列アクセス、例えばＡ［０］［ｘ］のような記述が多用される。この記述は、例えば画像処理における画像の端の部分の処理などに対応する。
【００８２】
このような配列アクセスを含む動作記述に対して既知のスカラリプレイスを実行した場合、配列アクセスを十分削除できず、性能向上が不十分となり、配列Ａを格納するメモリを残す必要があるため、面積が大規模になる。
【００８３】
これに対して、本実施形態の場合、添え字に定数が含まれる配列アクセスを削除することが可能である。このため、配列を格納するメモリを削減でき、格段の性能向上を図ることが可能である。
【００８４】
尚、循環バッファが同期式メモリで実現される場合、「循環バッファの入出力端に対応する一時変数へのアクセス」の代わりに「循環バッファに対応する配列（ｂｕｆ２、ｂｕｆ１等）へのアクセス」にすることも可能である。この場合、循環バッファの要素数は１個増加するが、レジスタ（ｓ３０、ｓ２０等）をそれぞれ１つ削減することが可能である。
【００８５】
また、第１の処理部は、再利用距離の差と規定値とを比較し、この比較結果に基づき、動作記述に循環バッファ又はシフトレジスタの記述を追加したが、これに限定されるものではなく、例えば予め再利用距離の差と循環バッファ及びシフトレジスタの対応関係を規定した表を設け、再利用距離の差に基づいて表を引くことによって循環バッファ又はシフトレジスタ決めることも可能である。
【００８６】
（ループ回数が定数ではなくパラメータである場合）
さらに、本実施形態の場合、動作記述中のループ回数が定数ではなく、例えばＮ、Ｍなどのパラメータである場合においても、配列アクセスの削減を簡単、且つ効率良く実現することが可能である。但し、Ｎ、Ｍの最大値は決まっているものとする。
【００８７】
例えば図１４に示す動作記述において、第１行、第２行にループ回数がパラメータ“Ｎ”として記述されている。この動作記述に対して、既存のスカラリプレイス技術を適用した場合、パラメータＮに対応する入力数の大きなマルチプレクサが実装されることとなる。すなわち、この場合、想定されたループ回数の最大値に一致した数のレジスタにより構成されたシフトレジスタが設けられる。このシフトレジスタの任意のレジスタからループ回数に応じデータを読み出すため、多くの入力端を有する大きなサイズのマルチプレクサが配置され、このマルチプレクサの多くの入力端がシフトレジスタの任意のレジスタに接続される。このため、回路規模が増大することとなる。
【００８８】
これに対して、本実施形態の場合、図６に示すステップＳ１１乃至Ｓ１４において、図１４に示す動作記述の“ｉｆ条件文”を考慮して配列アクセス間の再利用距離、再利用距離の差、及び再利用発生条件が算出され、図１５に示す再利用条件を含んだ表が作成される。
【００８９】
すなわち、図１５に示すように、配列アクセスＡ［０］［ｘ］の再利用条件“ｙ＝１”に対応する再利用距離ｄ３が“Ｎ”、配列アクセスＡ［０］［ｘ］の再利用条件“ｙ＝２”に対応する再利用距離ｄ４が“２＊Ｎ”、配列アクセスＡ［ｙ−３］［ｘ］に対応する再利用距離ｄ５が“３＊Ｎ”と算出され、これら再利用距離から再利用距離の差が“ｄ２−ｄ１＝２”、“ｄ３−ｄ２＝Ｎ−２”、“ｄ４−ｄ３＝Ｎ”、“ｄ５−ｄ４＝Ｎ”と算出される。
【００９０】
また、置き換え後の変数名は、配列アクセスＡ［ｙ］［ｘ］、配列アクセスＡ［ｙ］［ｘ−２］、配列アクセスＡ［０］［ｘ］、配列アクセスＡ［０］［ｘ］、配列アクセスＡ［ｙ−３］［ｘ］のそれぞれに対応して、“ｓ０”“ｓ２”“ｓ＿Ｎ”“ｓ＿２Ｎ”“ｓ＿３Ｎ”に設定される。
【００９１】
次いで、上記作成された表に基づき、図１６に示す再利用発生グラフが生成される。このグラフに記載された各矢印に基づいて、ジェネレータから最も遠い矢印から順に、シフトレジスタ、又は循環バッファが追加される（Ｓ１５）。
【００９２】
具体的には、再利用距離の差と規定値に基づき、シフトレジスタ又は循環バッファの記述が追加される。
【００９３】
例えば規定値として“８”が設定された場合、再利用距離の差が“８”以上である場合、循環バッファの記述が追加され、再利用距離の差が“８”未満である場合、シフトレジスタの記述が追加される。ただし、シフトレジスタ、及び循環バッファを追加するときは、再利用距離の差に出現する“Ｎ”には、Ｎの最大値を代入して、規定値と比較する。
【００９４】
この後、シフトレジスタ及び循環バッファへのアクセスが一時変数アクセスに置き換えられ、さらに、条件文が挿入され、最適化された動作記述が生成される（Ｓ１６）。
【００９５】
図１７は、図１４に示す動作記述に対して、シフトレジスタ、及び循環バッファへのアクセスを一時変数アクセスに置き換え、さらに、条件文を挿入した状態を示している。
【００９６】
図１７において、図１４の第３行、第４行、第６行、第７行の配列アクセスが、第３行乃至第１１行の一時変数アクセスに置き換えられ、さらに、第１３行乃至第２４行に３つの循環バッファが記述され、第２５行、第２６行にシフトレジスタが記述されている。
【００９７】
図１８は、本実施形態のスカラリプレイスにより、図１４に示す動作記述の配列アクセスを一時変数アクセスに変換した場合におけるシフトレジスタの構成を示している。本実施形態の場合、３つの循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２と、５個のレジスタｓ１、ｓ２、ｓ＿Ｎ、ｓ＿２Ｎ、ｓ＿３Ｎにより構成されている。このうち、レジスタｓ１、ｓ２はシフトレジスタを構成している。循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２は、例えばデュアルポートメモリにより構成されている。
【００９８】
循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２を構成するメモリ要素の数は、上述したように、「対応するエッジの再利用距離−１」である。例えばＮの最大値が１０のとき、循環バッファｂｕｆ０は、Ｎ−３＝７個のメモリ要素により構成され、循環バッファｂｕｆ１及びｂｕｆ２は、Ｎ−１＝９個のメモリ要素により構成されている。これら循環バッファｂｕｆ０、ｂｕｆ１、ｂｕｆ２は、それぞれポインタｐ０、ｐ１、ｐ２により記憶アドレスが指示される。このポインタは、配列アクセスの添え字に対応している。
【００９９】
上記のように、本実施形態によれば、動作記述中のループ回数が定数ではなく、例えばＮ、Ｍなどのパラメータである場合においても、配列アクセスの削減を簡単、且つ効率良く実現することが可能である。したがって、回路規模の増大を防止することができ、高速動作が可能な回路を実現することが可能である。
【０１００】
尚、図７（ａ）（ｂ）に示す再利用グラフ、図８に示す再利用発生条件を含んだ表、再利用発生グラフの作成は、任意であり、算出された再利用距離、再利用距離の差、及び規定値に基づき、配列アクセスをシフトレジスタや循環バッファへのアクセスに置き換えることも可能である。
【０１０１】
その他、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【０１０２】
１０…動作記述の最適化装置、１１…制御部、１４…記憶装置、１１ａ…解析処理部、１１ｂ…第１の処理部、１１ｃ…第２の処理部、１４ａ…動作記述、１４ｂ…配列アクセス間の再利用情報、１４ｃ…最適化済み動作記述。
【図１】
2014225200.tif 000003
【図２】
2014225200.tif 000004
【図３】
2014225200.tif 000005
【図４】
2014225200.tif 000006
【図５】
2014225200.tif 000007
【図６】
2014225200.tif 000008
【図７】
2014225200.tif 000009
【図８】
2014225200.tif 000010
【図９】
2014225200.tif 000011
【図１０】
2014225200.tif 000012
【図１１】
2014225200.tif 000013
【図１２】
2014225200.tif 000014
【図１３】
2014225200.tif 000015
【図１４】
2014225200.tif 000016
【図１５】
2014225200.tif 000017
【図１６】
2014225200.tif 000018
【図１７】
2014225200.tif 000019
【図１８】
2014225200.tif 000020