(57)【要約】【課題】  動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択でき、且つ、メモリアクセスのサイクル数を最適なものとし得る高位合成方法及び高位合成装置を提供することにある。【解決手段】  先ず、動作レベル回路に記述された変数が参照される参照回数を算出する。次に、変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定する。次に、選定された複数のメモリについて、参照回数と変数のビット幅とに基づいて、変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出する。その後、算出されたサイクル数の合計が最小となるメモリを、変数の割り当て対象として選択する。【選択図】  図２
2005173648.tif 000002
【特許請求の範囲】
【請求項１】
動作レベル回路に記述された変数をメモリに割り当てて論理回路を生成する高位合成方法であって、
（ａ）前記変数が前記動作レベル回路において参照される参照回数を算出する工程と、
（ｂ）前記変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定する工程と、
（ｃ）前記（ｂ）の工程において選定された複数のメモリについて、前記参照回数と前記変数のビット幅とに基づいて、前記変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出する工程と、
（ｄ）前記（ｃ）の工程において算出された前記メモリアクセスのサイクル数の合計が最小となるメモリを、前記変数の割り当て対象として選択する工程とを有することを特徴とする高位合成方法。
【請求項２】
前記動作レベル回路に記述された複数の配列変数又は構造体変数を結合して、新たな変数を生成する工程を更に有し、
前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される請求項１記載の高位合成方法。
【請求項３】
前記動作レベル回路に記述された配列変数又は構造体変数を分割して、それに含まれる複数の変数によって構成された新たな変数を生成する工程を更に有し、
前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される請求項１記載の高位合成方法。
【請求項４】
前記動作レベル回路に記述された複数の配列変数又は構造体変数を結合して、新たな配列変数又は構造体変数を生成する工程と、
前記新たな配列変数又は構造体変数を分割して、それに含まれる複数の変数で構成された新たな変数を生成する工程とを更に有し、
前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される請求項１記載の高位合成方法。
【請求項５】
前記複数の変数が、前記動作レベル回路において同一区間に記述されている変数である請求項２〜４のいずれかに記載の高位合成方法。
【請求項６】
前記複数の変数それぞれが、前記動作レベル回路において同一区間に記述されていない変数である請求項２〜４のいずれかに記載の高位合成方法。
【請求項７】
前記（ａ）の工程の実行前に、前記動作レベル回路に記述された全ての変数を互いに異なるメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、
前記スケジューリングの結果に基づいて、前記配列変数又は構造体変数がアクセスされる実行サイクルを特定し、予め定められた実行サイクルのサイクル数の範囲内でアクセスされる変数を前記同一区間に記述された変数と判断し、前記範囲内でアクセスされない変数を前記同一区間に記述されていない変数と判断する工程とを更に有する請求項５又は６記載の高位合成方法。
【請求項８】
前記同一区間が、前記動作レベル回路における繰り返し処理によって規定されており、
前記動作レベル回路に記述された同一の配列変数又は構造体変数に含まれる複数の変数の中から、前記同一区間に記述されている変数を特定する工程を更に有している請求項５又は６記載の高位合成方法。
【請求項９】
前記動作レベル回路に記述された配列変数又は構造体変数について依存解析を行って、前記配列変数又は構造体変数間の距離ベクトルを算出し、算出された距離ベクトルに基づいて、前記複数の変数を特定する工程を更に有している請求項２〜４のいずれかに記載の高位合成方法。
【請求項１０】
前記動作レベル回路に記述された変数によって構成された変数グループを設定する工程を更に有し、
前記（ｂ）の工程において、前記変数グループのビット幅と、前記変数グループを構成していない変数のビット幅とが抽出され、前記変数グループ及び前記変数グループを構成していない変数それぞれについて前記複数のメモリが選定される請求項１記載の高位合成方法。
【請求項１１】
前記変数グループを構成している変数が、前記動作レベル回路において同一区間に記述された変数である請求項１０記載の高位合成方法。
【請求項１２】
前記変数グループを構成している変数が、前記動作レベル回路において同一区間に記述されていない変数である請求項１０記載の高位合成方法。
【請求項１３】
前記（ａ）の工程の実行前に、前記動作レベル回路に記述された全ての変数を互いに異なるメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、
前記スケジューリングの結果に基づいて、各変数がアクセスされる実行サイクルを特定し、予め定められた実行サイクルのサイクル数の範囲内でアクセスされる変数を前記同一区間に記述された変数と判断し、前記範囲内でアクセスされない変数を前記同一区間に記述されていない変数と判断する工程とを更に有する請求項１１又は１２記載の高位合成方法。
【請求項１４】
前記変数グループについて選定された前記複数のメモリそれぞれのビット幅が異なっている請求項１０記載の高位合成方法。
【請求項１５】
設定可能な前記変数グループの個数が、予め設定されている請求項１０記載の高位合成方法。
【請求項１６】
前記変数グループが複数設定されており、
少なくとも一の変数グループを構成している変数の数は、他の変数グループを構成している変数の数と異なっている請求項１１記載の高位合成方法。
【請求項１７】
前記（ｃ）の工程の実行前に、前記（ｂ）の工程において選定されたメモリに前記変数を割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程を更に有し、
前記（ｃ）の工程において、前記スケジューリング結果に基づいて、前記メモリアクセスと並行して実行することが可能な演算処理が存在しているかどうかを判定し、前記演算処理が存在している場合に、前記メモリアクセスのサイクル数の合計を補正する請求項１記載の高位合成方法。
【請求項１８】
前記動作レベル回路に記述された繰り返し処理を抽出し、前記繰り返し処理に含まれる変数の依存関係を解析する工程と、
前記依存関係の解析の結果に基づいて、同時に参照される前記変数が同一の実行サイクルで実行されるように、前記繰り返し処理内の実行順序の入れ替えを行う工程とを更に有する請求項１７記載の高位合成方法。
【請求項１９】
前記（ｃ）の工程の実行前に、前記（ｂ）の工程において選定されたメモリに前記変数を割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、
前記（ｄ）の工程の実行後に、前記スケジューリングから得られる前記選択されたメモリへのアクセスパターンを表示する工程とを更に有する請求項１記載の高位合成方法。
【請求項２０】
前記スケジューリングの結果から、同一メモリへの予め設定されたサイクル数以上の連続したアクセスを抽出し、前記アクセスを示すアクセスパターンを表示する請求項１９記載の高位合成方法。
【請求項２１】
前記スケジューリングの結果から、同一の実行サイクルでアクセスされない複数のメモリを抽出し、抽出した前記複数のメモリのアクセス状態を示すアクセスパターンが表示される請求項１９記載の高位合成方法。
【請求項２２】
前記選択されたメモリに対応する複数のメモリセルを特定し、更に、複数のメモリセルの中から、１実行サイクルにおける遅延時間が予め設定された条件を満たすメモリセルを選択する工程を更に有し、
前記１実行サイクルにおける遅延時間が予め設定された条件を満たすメモリセルを選択できなかった場合に、前記（ｄ）の工程を再度実行する請求項１記載の高位合成方法。
【請求項２３】
前記変数を前記選択されたメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程を更に有し、
前記メモリセルの選択が、前記スケジューリングの結果と前記複数のメモリセルそれぞれのアクセス時間とに基づいて、前記複数のメモリセルそれぞれの１実行サイクルにおける遅延時間を算出し、算出した遅延時間が前記予め設定された条件を満たすかどうかを判定することによって行われている請求項２２記載の高位合成方法。
【請求項２４】
前記（ｄ）の工程の実行後に、前記変数を前記選択されたメモリに割り当てて配置配線を行うことによって、前記選択されたメモリの配置位置と前記選択されたメモリに接続される回路の配置位置とを少なくとも特定するレイアウト情報を生成する工程を更に有し、
前記複数のメモリセルそれぞれのアクセス時間が、前記レイアウト情報から求められている請求項２２記載の高位合成方法。
【請求項２５】
前記（ｄ）の工程の実行後に、前記変数を前記選択されたメモリに割り当てて配置配線を行うことによって、前記選択されたメモリの配置位置と前記選択されたメモリに接続される回路の配置位置とを少なくとも特定するレイアウト情報を生成する工程と、
前記レイアウト情報に基づいて、前記選択されたメモリのアクセス時間、配線混雑度、及びデッドスペースの面積のうち少なくとも一つを求める工程と、
前記算出したアクセス時間を用いて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程とを更に有している請求項１記載の高位合成方法。
【請求項２６】
前記求められた配線混雑度が、予め設定された条件を満たすかどうかを判定する工程を更に有し、
前記求められた配線混雑度が、前記予め設定された条件を満たさない場合に、前記選択されたメモリ以外のメモリについて前記（ｄ）の工程を再度実行する請求項２５記載の高位合成方法。
【請求項２７】
前記求められたデッドスペースの面積が、予め設定された条件を満たすかどうかを判定する工程を更に有し、
前記求められたデッドスペースの面積が、前記予め設定された条件を満たさない場合に、前記選択されたメモリ以外のメモリについて前記（ｄ）の工程を再度実行する請求項２５記載の高位合成方法。
【請求項２８】
動作レベル回路に記述された変数をメモリに割り当てて論理回路を生成する高位合成装置であって、
前記変数が前記動作レベル回路において参照される回数を算出する参照回数算出部と、
前記変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定するビット幅抽出部と、
前記選定された複数のメモリについて、前記参照回数と前記変数のビット幅とに基づいて、前記変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出し、算出された前記メモリアクセスのサイクル数が最小となるメモリを、割り当て対象として選択するメモリ選択部とを少なくとも有していることを特徴とする高位合成装置。
【請求項２９】
コンピュータに、動作レベル回路に記述された変数のメモリへの割り当てを行わせて、論理回路を生成させるためのプログラムであって、
（ａ）前記変数が前記動作レベル回路において参照される参照回数を算出するステップと、
（ｂ）前記変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定するステップと、
（ｃ）前記（ｂ）の工程において選定された複数のメモリについて、前記参照回数と前記変数のビット幅とに基づいて、前記変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出するステップと、
（ｄ）前記（ｃ）の工程において算出された前記メモリアクセスのサイクル数の合計が最小となるメモリを、前記変数の割り当て対象として選択するステップとを前記コンピュータに実行させる命令を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動作レベルで記述された回路から、レジスタ転送レベル又はゲートレベルの回路を合成する高位合成装置及び高位合成方法に関する。
【背景技術】
【０００２】
近年、ＬＳＩの大規模化に伴い、ＬＳＩ設計期間の短縮のため、高位合成を使用した回路設計が行われている。高位合成では、アルゴリズムのような抽象度の高い動作レベルで記述された回路から、レジスタ転送レベル又はゲートレベルの回路を合成する。
【０００３】
ところで、レジスタ転送レベルで回路記述を行い、この回路記述に基づいて論理合成を行う回路設計においては、メモリ等のメガセルは論理合成の対象にはならないため、メモリ等のメガセルを使用する場合は、回路設計者がレジスタ転送レベルの回路記述中に、直接、インスタンス記述を行う必要がある。
【０００４】
一方、高位合成を使用した回路設計においては、動作レベルで記述が行なわれるので、メガセルは配列変数や構造体変数等の変数で記述することができる。このため、変数は、高位合成を行うときに、メモリ、レジスタファイル、又はレジスタ等の記憶素子資源に割り当てられる。
【０００５】
従来の高位合成において、変数をレジスタ等に割り当てる手法としては、例えば非特許文献１で説明されているレフトエッジアルゴリズムを用いた手法が挙げられる。レフトエッジアルゴリズムを用いた手法では、先ず、動作レベルで記述された各演算を実行するサイクルを決定するためのスケジューリングが行なわれ、変数のライフタイムの解析が行なわれる。
【０００６】
その後、変数は、ライフタイム順にソートされ、ライフタイムが重ならないように順にレジスタに割り当てられる。例えば、変数が配列変数である場合は、配列変数の各配列要素が、前述の手法に従って、個々にレジスタに割り当てられる。
【０００７】
また、従来の高位合成において、変数をメモリに割り当てる手法としては、回路設計者が配列変数を特定のメモリに割り当てるように指定することによって、演算の実行順序を決定するスケジューリングの実行前に、配列変数が事前にメモリに割り当てられる手法が挙げられる。例えば特許文献１に開示された高位合成装置においては、回路設計者が、メモリ割り当てコマンドを使用して、動作レベル回路に記述された任意の配列変数を任意のメモリに割り当てている。
【特許文献１】特開平５−１０１１４１号公報
【非特許文献１】ガイスキー(Gajski)、ウー(Wu)、ダット(Dutt)、リン(Lin)著「高位合成：チップとシステム設計入門(HIGH-LEVEL SYNTHESIS, Introduction to Chip and System Design)」、（発行国：米国）、クルーワーアカデミックパブリッシャー(Kluwer Academic Publishers)、１９９２年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した配列変数をメモリに割り当てる手法においては、配列変数をメモリに割り当てた後、スケジューリングが行なわれており、スケジューリングは、割り当てを指定されたメモリに依存した制約下において行われる。このため、配列変数のメモリへの割り当てが最適でない場合は、最適なスケジューリング結果が得られないという問題がある。
【０００９】
例えば、Ｃ言語における構造体変数を使用した配列変数の場合、動作レベル回路の記述において、構造体変数全体として参照される場合と、構造体に含まれるメンバー変数として参照される場合とがある。各場合は、それぞれの参照方法の違いにより、データを転送するビット幅が異なっている。
【００１０】
また、特許文献１における高位合成においては、構造体変数をメモリに割り当てる場合、メモリのデータ転送のビット幅は、メモリ毎に１種類に限定される。よって、構造体変数全体が参照される場合と、メンバー変数が単独で参照される場合との両方の場合において、データ転送のビット幅が最適なメモリを割り当てることは困難である。
【００１１】
更に、割り当てたメモリにおけるデータ転送のビット幅の制約によって、構造体変数全体が参照される場合のメモリアクセスのサイクル数、及びメンバー変数が単独で参照される場合のメモリアクセスのサイクル数が決定されてしまう。
【００１２】
このため、メモリアクセスのサイクル数がスケジューリングの結果に影響を与える場合は、最適なスケジューリング結果が得られないことになる。このような問題を解決するため、高位合成においては、スケジューリング結果に影響を与えないように、又は最適なサイクル数が得られるように、割り当て対象となるメモリを選択することが求められている。
【００１３】
本発明の目的は、上記問題を解消し、動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択でき、且つ、メモリアクセスのサイクル数を最適なものとし得る高位合成方法及び高位合成装置を提供することにある。
【課題を解決するための手段】
【００１４】
上記目的を達成するために本発明における高位合成方法は、動作レベル回路に記述された変数をメモリに割り当てて論理回路を生成する高位合成方法であって、（ａ）前記変数が前記動作レベル回路において参照される参照回数を算出する工程と、（ｂ）前記変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定する工程と、（ｃ）前記（ｂ）の工程において選定された複数のメモリについて、前記参照回数と前記変数のビット幅とに基づいて、前記変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出する工程と、（ｄ）前記（ｃ）の工程において算出された前記メモリアクセスのサイクル数の合計が最小となるメモリを、前記変数の割り当て対象として選択する工程とを有することを特徴とする。
【００１５】
また、上記目的を達成するため本発明における高位合成装置は、動作レベル回路に記述された変数をメモリに割り当てて論理回路を生成する高位合成装置であって、前記変数が前記動作レベル回路において参照される回数を算出する参照回数算出部と、前記変数のビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定するビット幅抽出部と、前記選定された複数のメモリについて、前記参照回数と前記変数のビット幅とに基づいて、前記変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出し、算出された前記メモリアクセスのサイクル数が最小となるメモリを、割り当て対象として選択するメモリ選択部とを少なくとも有していることを特徴とする。
【００１６】
また、本発明は、上記の本発明における高位合成装置を具現化するためのプログラムであっても良い。このプログラムをコンピュータにインストールして実行することにより、本発明における高位合成方法を実行できる。
【発明の効果】
【００１７】
以上のように本発明における高位合成装置及び高位合成方法によれば、動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択でき、且つ、メモリアクセスのサイクル数を最適なものとできる。
【発明を実施するための最良の形態】
【００１８】
上記本発明における高位合成方法においては、前記動作レベル回路に記述された複数の配列変数又は構造体変数を結合して、新たな変数を生成する工程を更に有し、前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される態様とすることができる。
【００１９】
また、前記動作レベル回路に記述された配列変数又は構造体変数を分割して、それに含まれる複数の変数によって構成された新たな変数を生成する工程を更に有し、前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される態様とすることもできる。
【００２０】
更に、前記動作レベル回路に記述された複数の配列変数又は構造体変数を結合して、新たな配列変数又は構造体変数を生成する工程と、前記新たな配列変数又は構造体変数を分割して、それに含まれる複数の変数で構成された新たな変数を生成する工程とを更に有し、前記新たな変数について前記（ａ）〜（ｄ）の工程が実施される態様とすることもできる。
【００２１】
これらの態様においては、前記複数の変数は、前記動作レベル回路において同一区間に記述されている変数であっても良いし、前記複数の変数それぞれが、前記動作レベル回路において同一区間に記述されていない変数であっても良い。
【００２２】
この場合、前記（ａ）の工程の実行前に、前記動作レベル回路に記述された全ての変数を互いに異なるメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、前記スケジューリングの結果に基づいて、前記配列変数又は構造体変数がアクセスされる実行サイクルを特定し、予め定められた実行サイクルのサイクル数の範囲内でアクセスされる変数を前記同一区間に記述された変数と判断し、前記範囲内でアクセスされない変数を前記同一区間に記述されていない変数と判断する工程とを更に有していても良い。
【００２３】
また、前記同一区間が、前記動作レベル回路における繰り返し処理によって規定されており、前記動作レベル回路に記述された同一の配列変数又は構造体変数に含まれる複数の変数の中から、前記同一区間に記述されている変数を特定する工程を更に有していても良い。
【００２４】
更に、上記の態様においては、前記動作レベル回路に記述された配列変数又は構造体変数について依存解析を行って、前記配列変数又は構造体変数間の距離ベクトルを算出し、算出された距離ベクトルに基づいて、前記複数の変数を特定する工程を更に有していても良い。
【００２５】
上記本発明における高位合成方法においては、前記動作レベル回路に記述された変数によって構成された変数グループを設定する工程を更に有し、前記（ｂ）の工程において、前記変数グループのビット幅と、前記変数グループを構成していない変数のビット幅とが抽出され、前記変数グループ及び前記変数グループを構成していない変数それぞれについて前記複数のメモリが選定される態様とするのが好ましい。
【００２６】
また、この態様においては、前記変数グループを構成している変数は、前記動作レベル回路において同一区間に記述された変数であっても良いし、前記動作レベル回路において同一区間に記述されていない変数であっても良い。
【００２７】
また、この場合、前記（ａ）の工程の実行前に、前記動作レベル回路に記述された全ての変数を互いに異なるメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、前記スケジューリングの結果に基づいて、各変数がアクセスされる実行サイクルを特定し、予め定められた実行サイクルのサイクル数の範囲内でアクセスされる変数を前記同一区間に記述された変数と判断し、前記範囲内でアクセスされない変数を前記同一区間に記述されていない変数と判断する工程とを更に有するのが好ましい。
【００２８】
更に、上記の態様においては、前記変数グループについて選定された前記複数のメモリそれぞれのビット幅が異なっていても良いし、設定可能な前記変数グループの個数が、予め設定されていても良い。また、前記変数グループが複数設定されており、少なくとも一の変数グループを構成している変数の数は、他の変数グループを構成している変数の数と異なっていても良い。
【００２９】
また、上記本発明における高位合成方法においては、前記（ｃ）の工程の実行前に、前記（ｂ）の工程において選定されたメモリに前記変数を割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程を更に有し、前記（ｃ）の工程において、前記スケジューリング結果に基づいて、前記メモリアクセスと並行して実行することが可能な演算処理が存在しているかどうかを判定し、前記演算処理が存在している場合に、前記メモリアクセスのサイクル数の合計を補正する態様とするのが好ましい。
【００３０】
この態様においては、前記動作レベル回路に記述された繰り返し処理を抽出し、前記繰り返し処理に含まれる変数の依存関係を解析する工程と、前記依存関係の解析の結果に基づいて、同時に参照される前記変数が同一の実行サイクルで実行されるように、前記繰り返し処理内の実行順序の入れ替えを行う工程とを更に有するのが好ましい。
【００３１】
また、上記本発明における高位合成方法においては、前記（ｃ）の工程の実行前に、前記（ｂ）の工程において選定されたメモリに前記変数を割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程と、前記（ｄ）の工程の実行後に、前記スケジューリングから得られる前記選択されたメモリへのアクセスパターンを表示する工程とを更に有する態様とするのも好ましい。
【００３２】
この態様においては、前記スケジューリングの結果から、同一メモリへの予め設定されたサイクル数以上の連続したアクセスを抽出し、前記アクセスを示すアクセスパターンを表示することができる。また、前記スケジューリングの結果から、同一の実行サイクルでアクセスされない複数のメモリを抽出し、抽出した前記複数のメモリのアクセス状態を示すアクセスパターンを表示することもできる。
【００３３】
また、上記本発明における高位合成方法においては、前記選択されたメモリに対応する複数のメモリセルを特定し、更に、複数のメモリセルの中から、１実行サイクルにおける遅延時間が予め設定された条件を満たすメモリセルを選択する工程を更に有し、前記１実行サイクルにおける遅延時間が予め設定された条件を満たすメモリセルを選択できなかった場合に、前記（ｄ）の工程を再度実行する態様とするのが好ましい。
【００３４】
この態様においては、前記変数を前記選択されたメモリに割り当てて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程を更に有し、前記メモリセルの選択が、前記スケジューリングの結果と前記複数のメモリセルそれぞれのアクセス時間とに基づいて、前記複数のメモリセルそれぞれの１実行サイクルにおける遅延時間を算出し、算出した遅延時間が前記予め設定された条件を満たすかどうかを判定することによって行われているのが好ましい。
【００３５】
また、前記（ｄ）の工程の実行後に、前記変数を前記選択されたメモリに割り当てて配置配線を行うことによって、前記選択されたメモリの配置位置と前記選択されたメモリに接続される回路の配置位置とを少なくとも特定するレイアウト情報を生成する工程を更に有し、前記複数のメモリセルそれぞれのアクセス時間が、前記レイアウト情報から求められている態様としても良い。
【００３６】
更に、上記本発明における高位合成方法においては、前記（ｄ）の工程の実行後に、前記変数を前記選択されたメモリに割り当てて配置配線を行うことによって、前記選択されたメモリの配置位置と前記選択されたメモリに接続される回路の配置位置とを少なくとも特定するレイアウト情報を生成する工程と、前記レイアウト情報に基づいて、前記選択されたメモリのアクセス時間、配線混雑度、及びデッドスペースの面積のうち少なくとも一つを求める工程と、前記算出したアクセス時間を用いて、前記動作レベル回路における実行サイクルのスケジューリングを行う工程とを更に有している態様とするのが好ましい。
【００３７】
また、この態様においては、前記求められた配線混雑度が、予め設定された条件を満たすかどうかを判定する工程を更に有し、前記求められた配線混雑度が、前記予め設定された条件を満たさない場合に、前記選択されたメモリ以外のメモリについて前記（ｄ）の工程を再度実行するのが好ましい。
【００３８】
更に、この態様においては、前記求められたデッドスペースの面積が、予め設定された条件を満たすかどうかを判定する工程を更に有し、前記求められたデッドスペースの面積が、前記予め設定された条件を満たさない場合に、前記選択されたメモリ以外のメモリについて前記（ｄ）の工程を再度実行するのも好ましい。
【００３９】
以下、本発明の高位合成方法及び高位合成装置について図面を用いて説明する。なお、本発明の高位合成方法及び高位合成装置は、以下の実施の形態に何等限定されるものではない。
【００４０】
（実施の形態１）
以下、本発明の実施の形態１における高位合成装置及び高位合成方法について、図１〜図４を参照しながら説明する。最初に、本実施の形態１における高位合成装置の構成について図１を用いて説明する。図１は本発明の実施の形態１における高位合成装置の概略構成を示すブロック図である。
【００４１】
図１に示す高位合成装置１０は、動作レベル回路１１に記述された複数の変数のうちメモリに割り当てることが指定された変数のメモリへの割り当てを行って、論理回路を生成する装置である。
【００４２】
図１に示すように高位合成装置１０は、参照回数算出部１と、ビット幅抽出部２と、メモリ選択部３と、スケジューリング部４と、リソース割当部５とを有している。動作レベル回路１１は、Ｖｅｒｉｌｏｇ−ＨＤＬ等のハードウェア記述言語やＣ言語等のプログラミング言語によって記述された動作レベルの回路である。
【００４３】
参照回数算出部１は、動作レベル回路１１を読み込み、動作レベル回路１１に記述されている変数の中から、メモリに割り当てることを指定された全ての変数を特定し、各変数について参照回数を算出する。参照回数は、各変数が動作レベル回路１１で参照される回数である。算出された参照回数は、変数情報データベース１２へと出力され、変数情報データベース１２に格納される。
【００４４】
ビット幅抽出部２は、動作レベル回路１１を読み込み、参照回数算出部１によって参照回数が算出された全ての変数について、そのビット幅を抽出し、抽出したビット幅のデータ転送が可能な複数のメモリを選定する。ビット幅抽出部２は、選定されたメモリのリスト（メモリ候補リスト）を作成し、これをメモリ情報データベース１３に出力する。メモリ候補リストは、メモリ情報データベース１３に格納される。
【００４５】
なお、メモリ候補リストには、選定されたメモリ（メモリ候補）を識別するための識別情報やメモリのビット幅に関する情報が付加されている。また、ビット幅抽出部２は、各変数の抽出されたビット幅を特定する情報も、メモリ情報データベース１３に出力している。各変数の抽出されたビット幅を特定する情報は、メモリ情報データベース１３において、メモリ候補と関連付けられて格納されている。
【００４６】
メモリ選択部３は、メモリ候補のなかから、メモリに割り当てることを指定された変数毎に、割り当て対象となる適切なビット幅のメモリを選択する。本実施の形態１においては、メモリ選択部３は、メモリ情報データベース１３にアクセスして、メモリ候補リスト及び変数のビット幅を取得し、更に変数情報データベース１２にアクセスして参照回数を取得する。
【００４７】
更に、メモリ選択部３は、後述の図４に示すメモリアクセスサイクル表を参照しながら、取得した情報に基づいて、各メモリ候補に変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出する。また、メモリ選択部３は、各メモリ候補のサイクル数を互いに比較して、算出されたサイクル数の合計が最小となるメモリを割り当て対象として選択する。
【００４８】
この結果、動作レベル回路１１における変数に対して割り当てられるメモリ、即ち、変数の値を保存するメモリが決定される。更に、メモリ選択部３は、割り当てられるメモリが決定された変数を有する動作レベル回路を回路データベース１４に出力する。
【００４９】
具体的には、本実施の形態１においては、回路データベース１４には、動作レベル回路１１に記述された制御関係や、演算と変数の関係が、ＣＤＦＧ（Control Data Flow Graph）やＡＳＴ（Abstract Syntax Tree）等によって表現されて格納されている。このため、メモリ選択部３は、回路データベース１４上の変数に、割り当てるメモリの情報（プロパティ）を付加する。
【００５０】
なお、本実施の形態１においては、制御関係や演算と変数の関係は、ＣＤＦＧによって表現されている。ＣＤＦＧは、制御の流れ（Control Flow）と、データの流れ（変数と演算の入出力関係：Data Flow）とで構成されるグラフである（図２９参照）。よって、メモリ選択部３は、回路データベース１４に格納されているＣＤＦＧ中の変数ノードに、割り当てるメモリの情報（プロパティ）を付加している。
【００５１】
スケジューリング部４は、選択されたメモリを割り当ててスケジューリングを行う。具体的には、スケジューリング部４は、回路データベース１４からメモリの割当が決定した回路（ＣＤＦＧ）を取り出し、取り出した回路（ＣＤＦＧ）に対して演算の実行サイクルを決定するスケジューリングを行う。また、スケジューリング部４は、スケジューリングが完了した後、演算の実行サイクルが決定した回路（ＣＤＦＧ）を回路データベース１４に出力する。
【００５２】
リソース割当部５は、回路データベース１４から演算の実行サイクルが決定した回路（ＣＤＦＧ）を取り出し、これに基づいて、各演算のリソース割当やレジスタ割当等のメモリ割当を除くリソースへの割り当てを行い、レジスタ転送レベル又はゲートレベルで論理回路を生成する。生成された論理回路は、外部に出力される。なお、本実施の形態１において、スケジューリング部４及びリソース割当部５は、上記の非特許文献１で開示された手法を実行可能に構成されている。
【００５３】
次に、本実施の形態１における高位合成方法について図２〜図４を用いて説明する。本実施の形態１における高位合成方法は、図１に示した本実施の形態１における高位合成装置を動作させることによって実施される。このため、以下においては、適宜図１を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。図２は、本発明の実施の形態１における高位合成方法を示すフローチャートである。
【００５４】
図２に示すように、最初に、参照回数算出部１によって、動作レベル回路１１に記述されている変数の中から、メモリに割り当てることを指定された全ての変数を特定し、各変数について参照回数の算出を行う（ステップＳ１）。参照回数算出部１は、算出した参照回数を変数情報データベース１２に出力する。
【００５５】
次に、ビット幅抽出部２によって、ステップＳ１において参照回数が算出された変数のビット幅を抽出する（ステップＳ２）。更に、ビット幅抽出部２によって、抽出したビット幅のデータ転送が可能な複数のメモリをメモリ候補として選定し、メモリ候補を特定するメモリ候補リストを作成し、これをメモリ情報データベース１３に出力する（ステップＳ３）。
【００５６】
次いで、メモリ選択部３によって、ステップＳ１で算出された参照回数とステップＳ２で抽出された各変数のビット幅とに基づいて、各メモリ候補について、ステップＳ１で特定された変数が割り当てられた場合におけるメモリアクセスのサイクル数の合計を算出する（ステップＳ４）。
【００５７】
その後、メモリ選択部３によって、全てのメモリ候補について、メモリアクセスのサイクル数の合計が算出されているかどうかの判断を行う（ステップＳ５）。メモリ情報データベース１３に格納されている全てのメモリ候補についてメモリアクセスのサイクル数の合計の算出が終了していない場合は、メモリ選択部３によって、再度ステップＳ４を実行する。一方、全てのメモリ候補についてメモリアクセスのサイクル数の算出が終了している場合は、メモリ選択部３によってステップＳ６を実行する。
【００５８】
ステップＳ６においては、メモリ選択部３によって、ステップＳ３で算出したメモリアクセスのサイクル数の合計の比較が行われ、メモリアクセスのサイクル数の合計が最小となるメモリ候補が割り当て対象として選択される。
【００５９】
更に、メモリ選択部３によって、割り当てられるメモリが決定された変数を有する動作レベル回路が回路データベース１４に出力される。このように、ステップＳ１〜Ｓ６を実行することにより、動作レベル回路１１に記述されている変数のメモリへの割り当てが終了する。
【００６０】
この後、スケジューリング部４によるスケジューリング（ステップＳ７）及び、リソース割当部５によるリソースの割当等が行なわれ、論理回路が生成される（ステップＳ８）。生成された論理回路は外部へと出力される。
【００６１】
ここで、図３及び図４を用いて、図２におけるステップＳ１〜Ｓ６を更に具体的に説明する。図３は、実施の形態１で用いられる動作レベル回路とメモリアクセスのサイクル数とを示す図であり、図３（ａ）は動作レベル回路の一例を示し、図３（ｂ）は動作レベル回路に記述された変数の参照回数とビット幅とを示し、図３（ｃ）はメモリ候補のビット幅とメモリアクセスのサイクル数の合計とを示している。図４は、選定されたメモリにおけるメモリアクセスのサイクル数の算出に用いられるメモリアクセスサイクル表を示す図である。
【００６２】
図３（ａ）の例に示す動作レベル回路においては、配列変数ａとｂとが、メモリに割り当てることが指定された変数である。なお、図３（ａ）においては、メモリへの割当が指定された変数が二つである場合を示しているが、本発明では、メモリへの割当が指定された変数の数は特に限定されるものではない。
【００６３】
また、図３（ａ）において、配列変数ａは、メンバー変数ｍ１及びｍ２を含む構造体ａａａの配列変数である。例えば、メンバー変数ｍ１は、配列変数ａとして全体で参照される場合と、メンバー変数ｍ１の個別で参照される場合とがあり、２種類の参照方法が存在する変数である。
【００６４】
このため、ステップＳ１においては、図３（ｂ）に示すように、参照回数算出部１は、メモリへの割り当てが指定された変数として、配列変数ａ及びｂに加え、メンバー変数ａ．ｍ１及びａ．ｍ２も特定している。
【００６５】
また、参照回数算出部１は、図３（ｂ）に示すように、図３（ａ）に示す動作レベル回路１１から、配列変数ａ及びｂの参照回数（「Ｒｅａｄ」及び「Ｗｒｉｔｅ」）に加え、配列変数ａの各メンバー変数ａ．ｍ１及びａ．ｍ２の参照回数も算出する。
【００６６】
図３（ａ）に示す動作レベル回路１１において、メンバー変数ｍ１及びｍ２のデータ型はｃｈａｒ型で指定されている。ｃｈａｒ型は変数のビット幅が８ビットであることを示す。また、配列変数ａのビット幅は、構造体に含まれる全てのメンバー変数のビット幅を合計した値となる。更に、図３（ａ）に示す動作レベル回路１１において、配列変数ｂのデータ型はｉｎｔ型で指定されており、ｉｎｔ型は変数のビット幅が３２ビットであることを示す。
【００６７】
このため、ステップＳ２においては、図３（ｂ）に示すように、ビット幅抽出部２は、メンバー変数ａ．ｍ１及びａ．ｍ２のビット幅として８ビット、配列変数ａのビット幅として１６ビット、配列変数ｂのビット幅として３２ビットを抽出する。
【００６８】
更に、ステップＳ３において、ビット幅抽出部２は、配列変数ａを割り当てるメモリのビット幅を８ビット又は１６ビットと決定し、配列変数ｂを割り当てるメモリのビット幅を３２ビットと決定する。
【００６９】
その後、ビット幅抽出部２は、図３（ｃ）に示すように、配列変数ａを割り当てるメモリとして、ビット幅が８ビットのメモリＭ１とビット幅が１６ビットのメモリＭ２とを選定し、配列変数ｂのメモリ候補としてビット幅が３２ビットのメモリＭ３を選定する。
【００７０】
また、ビット幅抽出部２は、メモリＭ１とＭ３との組み合わせをメモリ候補Ａ、メモリＭ２とＭ３との組み合わせをメモリ候補Ｂとして、メモリ候補リストの作成及び出力を行う。なお、図３（ｃ）において、「ａビット幅」は、配列変数ａが割り当てられるメモリのビット幅を示し、「ｂビット幅」は、配列変数ｂが割り当てられるメモリのビット幅を示している。
【００７１】
ステップＳ４においては、メモリ選択部３は、図４に示すメモリアクセスサイクル表を参照して、各メモリ候補についてメモリアクセスのサイクル数の合計を算出する。図４に示すように、メモリアクセスサイクル表は、変数のビット幅（以下「ＢＷ（変数）」）とメモリのビット幅（以下「ＢＷ（メモリ）」）の大小関係ごとに、変数が割り当てられたメモリで行なわれるメモリアクセスのサイクル数を、読み込み（Ｒｅａｄ）時と書き込み（Ｗｒｉｔｅ）時とに分けて示している。図４で示されたメモリアクセスのサイクル数は、変数の一回の参照に必要なメモリアクセスサイクルの回数を示している。
【００７２】
具体的には、メモリ選択部３は、メモリ候補毎に、ＢＷ（変数）とＢＷ（メモリ）との関係を図４に示すメモリアクセスサイクル表に当てはめ、各メモリ候補について、変数を一回参照するために必要なメモリアクセスのサイクル数を、読み込み時と書き込み時それぞれについて算定する。
【００７３】
更に、メモリ候補毎に、この算定されたメモリアクセスのサイクル数と、参照回数とを乗算して、メモリアクセスのサイクル数の合計を算出する。なお、メモリ候補が、複数のメモリの組み合わせによる場合は、組み合わされているメモリ毎に上記の乗算を行い、得られた乗算値の合計が算出される。
【００７４】
例えば、変数ａの割り当て対象をメモリＭ１（ビット幅：８ビット）、変数ｂの割り当て対象をメモリＭ３（ビット幅：３２ビット）とした場合を考える。変数ａ．ｍ１のビット幅８ビットとメモリＭ１のビット幅８ビットが等しいことからＢＷ（変数）＝ＢＷ（メモリ）となる。
【００７５】
よって、図４から、メモリアクセスのサイクル数は、読み込み時と書き込み時の両方において、「１」となる。図３（ｂ）から、変数ａ．ｍ１の参照回数は、読み込み時及び書き込み時の両方において「１０回」であるから、変数ａ．ｍ１の読み込み及び書き込みにはそれぞれ１０サイクル、合計２０サイクル必要となる。
【００７６】
同様に、変数ａ.ｍ２については１０サイクル、変数ａについては２０サイクル必要となる。このことから、メモリＭ１を変数ａに割り当てた場合のメモリアクセスサイクル数の合計は５０サイクルとなる。また、変数ｂをメモリＭ３に割り当てた場合は、メモリのビット幅が３２ビットであることから、合計１０サイクルが必要となる。
【００７７】
但し、配列変数ａが割り当てられるメモリＭ１と、配列変数ｂが割り当てられるメモリＭ３は、別々のメモリであるため、図３（ａ）に示す第３番目の「ｆｏｒ」内における変数ａの読み込みと変数ｂの書き込みとは、同時に行うことができる。よって、ステップＳ５におけるメモリの選択の判断には、メモリＭ１のサイクル数の合計が用いられる（図３（ｃ）参照）。
【００７８】
次に、変数ａの割り当て対象をメモリＭ２（ビット幅：１６ビット）、変数ｂの割り当て対象をメモリＭ３（ビット幅：３２ビット）とした場合を考える。図３（ｂ）及び図４から、メモリＭ２を変数ａに割り当てた場合のサイクル数の合計は６０サイクルとなる。また、この場合も変数ａの読み込みと変数ｂの書き込みとは、同時に行うことができるので、ステップＳ５におけるメモリの選択の判断には、メモリＭ２のサイクル数の合計が用いられる（図３（ｃ）参照）。
【００７９】
なお、図４において、変数のビット幅よりメモリのビット幅が大きい場合（ＢＷ（変数）＜ＢＷ（メモリ））に、書き込みサイクルが２サイクルになっているのは、一度に書き込むビット幅分のデータを事前に一旦読み込んでおく必要があるからである。
【００８０】
例えば、ビット幅が１６ビットのメモリを変数ａに割り当てた場合は、変数ａの単位で書き込み動作が行なわれる。従って、メンバー変数ａ．ｍ１のみに書き込む場合でも、メンバー変数ａ．ｍ２にも書き込みが行われてしまう。このため、予め変数ａのデータを読み込んでから書き込みを行う必要があり、読み込みで１サイクル、書き込みで１サイクルの計２サイクルかかるのである。
【００８１】
ステップＳ６においては、メモリ選択部３は、図３（ｃ）で示した結果に基づいて、変数ａの割り当て対象としてメモリＭ１（ビット幅：８ビット）を選択し、変数ｂの割り当て対象としてメモリＭ３（ビット幅：３２ビット）を選択する。
【００８２】
なお、図３（ａ）に示す動作レベル回路では、８ビットのビット幅のメモリを選択した場合に、サイクル数の合計は最小となるが、メンバー変数ａ．ｍ１及びａ．ｍ２において個々の参照がない場合は、３２ビットのビット幅のメモリを選択した場合に、トータルのサイクル数が最小となる。
【００８３】
以上のように、本実施の形態１によれば、動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択できるので、メモリアクセスのサイクル数を最適なものとできる。
【００８４】
例えば、Ｃ言語における構造体変数等の複数の変数参照方法が存在する変数をメモリに割り当てる場合に、ビット幅の異なる複数の割り当て対象となるメモリが存在していても、最もメモリアクセスのサイクル数が小さくなるメモリを割り当て対象として選択できる。このため、本実施の形態１によれば、従来技術において示した高位合成装置や高位合成方法と異なり、最適なスケジューリング結果を得ることができる。
【００８５】
本実施の形態１における高位合成装置は、コンピュータに、図２に示すステップＳ１〜Ｓ８を具現化させるプログラムをインストールし、このプログラムを実行することによって実現できる。この場合、コンピュータのＣＰＵ（central  processing  unit）は、参照回数算出部、ビット幅抽出部、メモリ選択部、スケジューリング部、リソース割当部として機能し、処理を行う。
【００８６】
また、本実施の形態１では、変数情報データベース１２、メモリ情報データベース１３、及び回路データベース１４は、コンピュータに備えられたハードディスク等の記憶装置に、これらを構成するデータファイルを格納することによって、又はこのデータファイルが格納された記録媒体をコンピュータと接続された読取装置に搭載することによって実現できる。また、これらのデータベースは、参照回数算出部１等を構築するコンピュータとは別のコンピュータによって実現されていても良い。なお、後述する実施の形態２〜８における高位合成装置も、本実施の形態１における高位合成装置と同様に、コンピュータによって実現できる。
【００８７】
（実施の形態２）
次に、本発明の実施の形態２における高位合成装置及び高位合成方法について、図５〜図９を参照しながら説明する。最初に、図５を用いて、実施の形態２における高位合成装置の構成について説明する。図５は、本発明の実施の形態２における高位合成装置の概略構成を示すブロック図である。
【００８８】
図５に示すように、本実施の形態２における高位合成装置２０は、変数分割部２１を備えており、この点で実施の形態１において図１に示した高位合成装置１０と異なっている。この点以外については、本実施の形態２における高位合成装置２０は、実施の形態１において図１に示した高位合成装置１０と同様に構成されている。
【００８９】
変数分割部２１は、動作レベル回路１１に記述されている変数を複数の変数に分割して、新たな変数を生成し、これを用いて動作レベル回路１１を修正する。また、本実施の形態２においては、実施の形態１と異なり、参照回数算出部１及びビット幅抽出部２は、変数分割部２１によって修正された動作レベル回路（以下、「修正後動作レベル回路」という。）２２を読み込んで処理を行う。
【００９０】
ここで、変数分割部２１によって行われる変数分割について説明する。本実施の形態２において変数分割部２１が行う変数分割の方法としては、アクセス集中化方法とアクセス分散化方法との２つがある。
【００９１】
アクセス集中化方法は、動作レベル回路１１の同一の配列変数又は構造体変数に含まれる複数の変数であって同一区間に記述されたものを、別の一つの配列変数又は構造体変数に割り当て、同一区間に記述されていない複数の変数をそれぞれ別々の配列変数又は構造体変数に割り当てる分割方法である。アクセス分散化方法は、動作レベル回路１１の同一の配列変数又は構造体変数に含まれる複数の変数であって同一区間に記述されたものを、それぞれ別々の配列変数又は構造体変数に割り当てる分割方法である。
【００９２】
例えば、アクセス集中化方法で構造体変数を分割して、同一区間に記述された複数のメンバー変数を一つのメモリに割り付け、同一区間に記述されていない複数のメンバー変数をそれぞれ別々のメモリに割り付けた場合は、一定時間内においてメモリへのアクセスが１つのメモリに集中するために、他の非動作メモリを停止しておくことが可能となる。
【００９３】
一方、アクセス分散化方法で構造体変数を分割した場合は、一定時間内にアクセスするメモリが別々になるために、異なるメモリへの同時アクセスが可能となり、メモリへのアクセスのサイクル数を短縮することができる。
【００９４】
このように変数の分割方法により得られる効果が異なるため、変数分割部２１においては、最終製品であるＬＳＩにおいて求められる効果に応じて分割方法が指定される。
【００９５】
次に、図６〜図８を用いて、本実施の形態２における高位合成方法について説明する。本実施の形態２における高位合成方法は、図５に示した本実施の形態１における高位合成装置を動作させることによって実施される。このため、以下においては、適宜図５を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。
【００９６】
図６は、本発明の実施の形態２における高位合成方法を示すフローチャートである。図７は、実施の形態２において用いられる動作レベル回路の一例を示す図であり、図７（ａ）は変数分割を行う前の状態を示し、図７（ｂ）は変数分割を行った後の状態を示している。
【００９７】
図８は、変数分割を行った場合と変数分割を行わなかった場合とのサイクル数の合計を示す図であり、図８（ａ）は変数分割を行った場合における変数の参照回数とビット幅とを示し、図８（ｂ）は変数分割を行った場合におけるメモリ候補のビット幅とサイクル数の合計とを示し、図８（ｃ）は変数分割をしなかった場合のメモリ候補のビット幅とサイクル数の合計とを示している。
【００９８】
図６に示すように、最初に、変数分割部２１によって、動作レベル回路１１に記述された配列変数又は構造体変数に含まれている複数の変数の中から、同一区間に記述されている変数が特定される（ステップＳ１０１）。
【００９９】
具体的には、例えば、動作レベル回路１１が図７（ａ）に示すものである場合は、構造体変数ａａａに含まれる複数のメンバー変数（ａ．ｍ１、ａ．ｍ２、ａ．ｍ３、ａ．ｍ４）の中から、同一区間に記述されている変数が特定される。
【０１００】
また、本実施の形態２においては、繰り返し処理によって規定された区間を同一区間としており、同一区間に記述されているかどうかの判断は、一つのｆｏｒ文内に記述されているかどうかによって行われる。このため、ａ．ｍ１とａ．ｍ３が同一区間に記述されていると判断され、又ａ．ｍ２とａ．ｍ４も同一区間に記述されていると判断される。
【０１０１】
次いで、変数分割部２１によって、動作レベル回路１１に記述された配列変数又は構造体変数の分割が行われ、それに含まれる変数によって構成された新たな変数が生成される（ステップＳ１０２）。また、変数分割部２１は、新たな変数が記述された修正後動作レベル回路２２（図７（ｂ）参照）を作成する。
【０１０２】
本実施の形態２においては、変数分割部２１は、構造体変数を分割して、それに含まれるメンバー変数で構成された新たな構造体変数を生成している。また、変数分割部２１は、アクセス分散化方法によって変数分割を行っており、新たな変数を構成する各メンバー変数は、同一区間に記述されていない。
【０１０３】
具体的には、図７（ｂ）に示すように、変数分割部２１は、構造体変数ａａａを分割して、互いに同一区間に記述されていないａ．ｍ１及びａ．ｍ２によって構成された構造体変数ａａａ１と、互いに同一区間に記述されていないａ．ｍ３及びａ．ｍ４によって構成された構造体変数ａａａ２とを生成している。
【０１０４】
次に、参照回数算出部１によって、修正後動作レベル回路２２が読み込まれ、修正後動作レベル回路２２に記述されている変数の中から、メモリに割り当てることを指定された全ての変数が特定され、各変数について参照回数の算出が行われる（ステップＳ１１）。
【０１０５】
ステップＳ１１は、修正後動作レベル回路２２が読み込まれる以外は、実施の形態１におけるステップＳ１と同様に行なわれる。また、図８（ａ）の表の第２カラム及び第３カラムに示すように、配列変数ａ１、ａ２及びｂの参照回数に加え、構造体ａａａ１のメンバー変数ａ１．ｍ１及びａ１．ｍ２と、構造体ａａａ２のメンバー変数ａ２．ｍ３及びａ２．ｍ４の参照回数も算出される。
【０１０６】
次いで、ビット幅抽出部２によって、修正後動作レベル回路２２が読み込まれ、図８（ａ）の表の第４カラムに示すように、ステップＳ１１において参照回数が算出された変数のビット幅が抽出される（ステップＳ１２）。ステップＳ１２は、修正後動作レベル回路２２が読み込まれる以外は、実施の形態１におけるステップＳ２と同様に行なわれる。
【０１０７】
更に、ビット幅抽出部２によって、メモリ候補となるメモリが選定され、メモリ候補を特定するメモリ候補リストが作成される（ステップＳ１３）。また、メモリ候補リストはメモリ情報データベース１３に出力される。
【０１０８】
本実施の形態２においては、ビット幅抽出部２は、配列変数ａ１を割り当てるメモリとしてメモリＭ１１（８ビット）とメモリＭ１２（１６ビット）とを選定し、配列変数ａ２を割り当てるメモリとしてメモリＭ１３（８ビット）とメモリＭ１４（１６ビット）とを選定し、配列変数ｂを割り当てるメモリとしてメモリＭ１５（３２ビット）を選定している。
【０１０９】
また、ビット幅抽出部２は、メモリＭ１１、Ｍ１３及びＭ１５の組み合わせをメモリ候補Ａ、メモリＭ１１、Ｍ１４及びＭ１５の組み合わせをメモリ候補Ｂ、メモリＭ１２、Ｍ１３及びＭ１５の組み合わせをメモリ候補Ｃ、メモリＭ１２、Ｍ１４及びＭ１５の組み合わせをメモリ候補Ｄとして、メモリ候補リストの作成及び出力を行っている。
【０１１０】
次いで、メモリ選択部３によって、実施の形態１におけるステップＳ４と同様に図４に示すサイクル表を参照して、メモリ候補Ａ〜Ｄについて、図８（ｂ）の第４カラムに示すメモリアクセスのサイクル数の合計が算出される（ステップＳ１４）。
【０１１１】
なお、本実施の形態２においても、配列変数ａ１を割り当てるメモリ、配列変数ａ２を割り当てるメモリ、及び配列変数ｂを割り当てるメモリは、それぞれ別々のメモリである。このため、図７（ｂ）に示す「ｆｏｒ」内における各配列変数への読み込み及び書き込みは同時に行われる。よって、図８（ｃ）に示すメモリアクセスの「サイクル数の合計」の欄には、最もサイクル数が多い配列変数のサイクル数の合計が記載されている。
【０１１２】
その後、メモリ選択部３によって、実施の形態１におけるステップＳ５と同様に、全てのメモリ候補について、メモリアクセスのサイクル数の合計が算出されているかどうかの判断が行われる（ステップＳ１５）。
【０１１３】
全てのメモリ候補についてサイクル数の合計の算出が終了していない場合は、メモリ選択部３によって、再度ステップＳ１４が実行され、終了している場合は、メモリ選択部３によってステップＳ１６が実行される。
【０１１４】
ステップＳ１６においては、実施の形態におけるステップＳ６と同様に、メモリ選択部３によって、メモリ候補Ａ〜Ｄについてサイクル数の合計の比較が行われ、メモリアクセスのサイクル数の合計が最小となるメモリ候補が割り当て対象として選択される。
【０１１５】
この後、実施の形態１と同様に、スケジューリング部４によるスケジューリング（ステップＳ１７）及び、リソース割当部５によるリソースの割当等が行なわれ、論理回路が生成される（ステップＳ１８）。生成された論理回路は外部へと出力される。
【０１１６】
ここで、ステップＳ１０１及びステップＳ１０２を実行しない場合、即ち変数分割を行わない場合について検討する。この場合においては、配列変数ａ（図７（ａ）参照）と配列変数ｂとについてメモリ候補Ａ´及びＢ´が選定される。この場合のメモリアクセスのサイクル数は図８（ｃ）に示すようになる。
【０１１７】
図８（ｂ）及び図８（ｃ）から分るように、変数分割を行わなかった場合は最低でも７０サイクルを要するが、変数分割を行った場合は４０サイクルに削減できる。このように、本実施の形態２においては、構造体変数を分割して、同一区間に記述されたメンバー変数を別々のメモリに割り付けることが可能であるため、実施の形態１の場合よりも、更にサイクル数の削減を図ることができる。
【０１１８】
なお、本実施の形態２においては、上述したように、変数分割部２１はアクセス分散化方法によって変数分割を行っているが、例えば、ａ．ｍ１及びａ．ｍ３を含む構造体変数と、ａ．ｍ２及びａ．ｍ４を含む構造体変数とに分割するアクセス集中化方法によって変数分割を行うこともできる。
【０１１９】
この場合は、ａ．ｍ１とａ．ｍ３とは同じメモリに割り付けられ、またａ．ｍ２とａ．ｍ４も同じメモリに割り付けられるため、メモリ毎に未使用になる期間が長くなる。よって、その間のメモリ停止が可能になり、ＬＳＩの消費電力の削減を図ることができる。
【０１２０】
また、本実施の形態２において、同一区間はｆｏｒ文によって記述された区間としているが、これに限定されるものではない。例えば、動作レベル回路１１又は修正後動作レベル回路２２における基本ブロックを同一区間と定義しても良い。
【０１２１】
更に、スケジューリング部４によって、ステップＳ１７におけるスケジューリングとは別の仮スケジューリングを行い、この仮スケジューリングの結果から同一サイクルでアクセスされる可能性があると判断できる複数のメンバー変数については、同一区間に記述されていると定義することもできる。
【０１２２】
ここで、スケジューリング部４によって仮スケジューリングを行う態様について説明する。仮スケジューリングを行う態様であっても、高位合成装置は、図５に示す構成を有している。但し、変数分割部２１（図５参照）及びスケジューリング部４（図５参照）における動作の点で、図５に示す高位合成装置と異なっている。このため、高位合成方法を実施するための工程も、図６に示すものと異なっている。
【０１２３】
図９を用いて仮スケジューリングが行われる場合の実施の形態２における高位合成方法について説明する。図９は、仮スケジューリングを行う場合の実施の形態２における高位合成方法を示すフローチャートである。なお、以下の説明においては、適宜図５を参照する。
【０１２４】
図９に示すように、先ず、スケジューリング部４によって、仮スケジューリングが行われる（ステップＳ１１１）。具体的には、スケジューリング部４は、動作レベル回路１１に記述された全ての変数を互いに異なるメモリに割り当てて、動作レベル回路１１の実行サイクルのスケジューリングを行う。
【０１２５】
次に、変数分割部２１によって、同一区間に記述されている変数が特定される（ステップＳ１１２）。具体的には、先ず、変数分割部２１によって、ステップＳ１１０の仮スケジューリングの結果に基づいて、配列変数又は構造体変数がアクセスされる実行サイクルが特定される。更に、変数分割部２１によって、予め定められた実行サイクルのサイクル数の範囲内でアクセスされている変数が特定され、同一区間に記述されているかどうかが判断される。
【０１２６】
例えば、実行サイクルのサイクル数の範囲を３に設定した場合に、図７（ａ）に示された「ａ［ｉ］．ｍ１」の実行サイクルがサイクル１、「ａ［ｉ］．ｍ３」の実行サイクルがサイクル３であれば、これらはサイクル数が３の範囲内でアクセスされることから、同一区間に記述されていると判断される。
【０１２７】
次いで、ステップＳ１１２の結果に基づいて、変数分割部２１によって変数分割が行われる（ステップＳ１１３）。その後、図６の例と同様に、ステップＳ１１〜ステップＳ１８が実行される。このような態様においても、同一区間に記述された変数を別々のメモリに割り付けることが可能であるため、実施の形態１の場合よりも、更にサイクル数の削減を図ることができる。
【０１２８】
（実施の形態３）
次に本発明の実施の形態３における高位合成装置及び高位合成方法について、図１０〜図２０を参照しながら説明する。
【０１２９】
本実施の形態３における高位合成装置及び高位合成方法は、変数分割だけでなく、同一の配列変数又は構造体変数に含まれる複数の変数（メンバー変数や配列要素）を統合して、新たな変数の生成（変数統合）を行うことができる。また、動作レベル回路に記述された構造体変数をメンバー変数で分割する実施の形態２と異なり、動作レベル回路に記述された配列変数を配列要素で分割することができる。
【０１３０】
図１０は、本発明の実施の形態３における高位合成装置の一例の概略構成を示すブロック図である。図１１は、実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１１（ａ）は変数結合を行う前の状態を示し、図１１（ｂ）は変数結合を行った後の状態を示している。
【０１３１】
図１０に示すように、高位合成装置３０は、変数統合部３１を有しており、この点で実施の形態２において図５に示した高位合成装置２０と異なっている。これ以外の点では、高位合成装置３０は、図５に示した高位合成装置２０と同様に構成されている。変数統合部３１は、動作レベル回路１１に記述された複数の配列変数又は構造体変数を結合して、新たな変数を生成する。具体的には、変数統合部３１は、動作レベル回路１１に記述され、且つ、同一の配列変数に含まれる複数の配列要素のうち幾つかを統合して、新たな配列変数を生成する。
【０１３２】
例えば、図１１（ａ）に示した動作レベル回路１１において、配列変数ａの配列要素であるａ［ｉ］とａ［ｉ＋１］は、同一のｆｏｒ内に記述されており、一度にアクセスされる可能性がある。このため、図８（ｂ）に示すように、変数統合部３１は、ａ［ｉ］とａ［ｉ＋１］とを統合して、新たな構造体変数ａａａを生成する。
【０１３３】
また、図１０に示す高位合成装置３０を動作させることによって高位合成方法を実行する場合は、実施の形態２において図６に示したステップＳ１０２の代わりに、変数統合部３１によって変数統合が行われる。また、この場合は、参照回数算出部１とビット幅抽出部２とは変数統合後の修正動作レベル回路３２（図１１（ｂ）参照）を読み込むことになる。なお、他のステップは、実施の形態２における高位合成方法と同様のステップで実施される。
【０１３４】
図１２は、変数統合を行わない場合と変数統合を行った場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅及びサイクル数の合計を示す図であり、図１２（ａ）は変数統合を行わない場合を示し、図１２（ｂ）は変数統合を行った場合を示している。
【０１３５】
変数統合部３１（図１０参照）によって、動作レベル回路１１（図１１（ａ）参照）に対して変数統合を行った場合は、修正後動作レベル回路３２（図１１（ｂ）参照）に記述された配列変数ａに対して、１６ビットのメモリ（メモリ候補Ａ）を割り付けることができる。この場合、図１２（ｂ）に示すように、メモリアクセスのサイクル数の合計は１０サイクルとなる。
【０１３６】
一方、図１２（ａ）に示すように、動作レベル回路１１（図１１（ａ）参照）に対して変数統合を行わないでメモリ候補Ａ´に割り当てた場合は、メモリアクセスのサイクル数は、ａ［ｉ］が１０回、ａ［ｉ＋１］が１０回の合計２０サイクルとなる。また、図１２（ａ）の例では、配列変数ａに対して８ビットのメモリが割り付けられているが、このメモリの代わりに１６ビットのメモリを割り付けても、メモリアクセスのサイクル数は２０サイクルである（図４参照）。
【０１３７】
このように、本実施の形態３においても、実施の形態２と同様に、実施の形態１の場合よりも更にサイクル数の削減を図ることができる。
【０１３８】
また、本実施の形態３における図１０に示す高位合成装置３０においては、変数統合部３１の代わりに、図１１（ａ）に示す動作レベル回路１１に記述された配列変数ａを配列要素で分割することが可能な変数分割部が備えられた態様とすることができる。
【０１３９】
図１３は、配列変数を配列要素で分割した後の動作レベル回路、変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図１３（ａ）は、図１１（ａ）に示す動作レベル回路を変数分割した後の状態を示しており、図１３（ｂ）は、変数分割を行った場合における変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示している。
【０１４０】
図１３に示すように、図１１（ａ）に示す配列変数ａを配列要素で分割して、配列変数ａ１とａ２とを作成した場合は、作成された各配列変数のビット幅は８ビットになる。また、各配列変数は、それぞれ８ビットのメモリＭ２１又はＭ２２（メモリ候補Ａ）に割り付けることができ、各メモリには別々にアクセスできることから、メモリアクセスのサイクル数の合計は１０サイクルとなる。
【０１４１】
図１３から分るように、このような態様によっても、変数統合を行った場合と同様に、サイクル数の低減を図ることができ、実施の形態１の場合よりも更にサイクル数の削減を図ることができる。
【０１４２】
次に、本実施の形態３における高位合成装置及び高位合成方法の別の例について説明する。図１４は、本発明の実施の形態３における高位合成装置の他の例の概略構成を示すブロック図である。図１５は、実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１５（ａ）は変数分割及び変数結合を行う前の状態を示し、図１５（ｂ）は変数分割及び変数結合を行った後の状態を示している。
【０１４３】
図１４に示すように、高位合成装置３３は、変数分割統合部３４を有しており、この点で実施の形態２において図５に示した高位合成装置２０と異なっている。これ以外の点では、高位合成装置３３は、図５に示した高位合成装置２０と同様に構成されている。変数分割統合部３４は、動作レベル回路１１に記述された複数の配列変数又は構造体変数を結合して、新たな配列変数又は構造体変数を生成し、更に、この新たな配列変数又は構造体変数を分割して、それに含まれる複数の変数で構成された新たな変数を生成する。つまり、分割統合部３４は、変数分割及び変数統合を行うことができる。
【０１４４】
本実施の形態３においては、変数分割統合部３４は、２次の配列変数ａ（図１５（ａ）参照）に含まれる複数の配列要素を結合して、新たな配列変数（図示せず）を生成し、更に、この新たな配列変数を分割して、それに含まれる配列要素で構成された新たな配列変数ａ１、ａ２（図１５（ｂ）参照）を生成している。
【０１４５】
また、図１４に示す高位合成装置３３を動作させることによって高位合成方法を実行する場合は、実施の形態２において図６に示したステップＳ１０２の代わりに、変数分割統合部３４によって変数統合及び変数分割が行われる。また、この場合は、参照回数算出部１とビット幅抽出部２とは変数統合及び変数分割後の修正後動作レベル回路３５（図１７（ｂ）参照）を読み込むことになる。なお、他のステップは、実施の形態２における高位合成方法と同様のステップで実施される。
【０１４６】
このように変数統合と変数分割との両方を実施できる態様とすれば、図１５（ａ）に示す動作レベル回路のように、２次以上の配列変数と、この配列変数へのアクセス順序が異なる複数の繰り返しループとが記述されている場合に、各繰り返しループにおいて重複して行われる処理を削除できるため、サイクル数の低減を図ることができる。
【０１４７】
図１６は、変数統合及び変数分割を行った場合と変数統合及び変数分割を行わない場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図１６（ａ）は変数統合及び変数分割を行わない場合を示し、図１６（ｂ）は変数統合及び変数分割を行った場合を示している。
【０１４８】
図１６（ｂ）に示すように、変数分割統合部３４によって（図１４参照）、動作レベル回路１１（図１４及び図１５（ａ）参照）に対して変数統合及び変数分割を行った場合は、修正後動作レベル回路３５（図１５（ｂ）参照）に記述された配列変数ａ１及びａ２に対して、１６ビットのメモリＭ３１又Ｍ３２（メモリ候補Ａ）を割り付けることができる。また、各メモリには別々にアクセスできる。よって、この場合、メモリアクセスのサイクル数の合計は２００サイクルとなる。
【０１４９】
一方、図１６（ａ）に示すように、動作レベル回路１１（図１１（ａ）参照）に対して変数統合及び変数分割を行わなかった場合は、配列変数ａは一つの８ビットのメモリ（メモリ候補Ａ´）に割り付けられるため、メモリアクセスのサイクル数の合計は８００サイクルとなる。また、図１２（ａ）の例では、配列変数ａに対して８ビットのメモリが割り付けられているが、この代わりに１６ビットのメモリを割り付けても、メモリアクセスのサイクル数は８００サイクルである（図４参照）。
【０１５０】
このように、本態様においても、実施の形態２と同様に、実施の形態１の場合よりも更にサイクル数の削減を図ることができる。
【０１５１】
次に、本実施の形態３における高位合成装置及び高位合成方法の更なる別の例について説明する。図１７は、本発明の実施の形態３における高位合成装置の他の例の概略構成を示すブロック図である。図１８は、実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１８（ａ）は変数分割を行う前の状態を示し、図１８（ｂ）は変数分割を行った後の状態を示している。
【０１５２】
図１７に示すように、高位合成装置３６は、依存解析部３７と変数分割部３８とを有しており、この点で実施の形態２において図５に示した高位合成装置２０と異なっている。これ以外の点では、高位合成装置３６は、図５に示した高位合成装置２０と同様に構成されている。
【０１５３】
依存解析部３７は、動作レベル回路１１に記述された配列変数又は構造体変数について依存解析を行って、配列変数又は構造体変数間における依存関係の有無を判定する。依存関係が存在する場合は、依存解析部３７は依存関係がある変数間の距離ベクトルを算出する。また、依存解析部３７は、依存関係の有無を特定する情報と、算出された距離ベクトルとを変数依存情報データベース１５に出力する。
【０１５４】
また、変数分割部３８は、変数依存情報データベース１５から情報を取り出して、依存関係の有無を確認する。変数分割部３８は、依存関係が存在する場合は、算出された距離ベクトルに基づいて、生成される新たな変数を構成する変数を特定して、変数分割を行う。変数分割部３８は、この点で図５に示した変数分割部２１と異なっている。なお、変数間に依存関係がない場合は、変数分割部３８は、図５に示した変数分割部２１と同様に、同一区間に記述されている変数を特定して、変数分割を行うこともできる。
【０１５５】
具体的には、動作レベル回路１１が図１８（ａ）に示すものである場合、依存解析部３７は、配列要素ａ［ｉ］とａ［ｉ＋１］との間に距離ベクトル１の依存関係があると判定する。この場合、変数分割部３８は、配列変数ａを変数分割する。但し、距離ベクトルが１であることから、変数分割部３８は、図１８（ｂ）に示すように、１つおきに配列要素を別々の変数に分割する。これにより、新たな配列変数ａ１とａ２とが生成される。
【０１５６】
なお、配列要素の依存解析は、「中田、“コンパイラの構成と最適化”、朝倉書店、１９９９」に説明されているように、配列変数のインデックス変数からディオファンタス方程式を求め、この方程式を解くことによって行うことができる。
【０１５７】
ここで、図１７に示した高位合成装置３６の動作について説明する。高位合成装置３６を動作させることによっても、実施の形態３における高位合成方法が実施される。図１９は、図１７に示す高位合成装置の動作の流れを示すフローチャートである。なお、以下の説明においては適宜図１７が参照される。
【０１５８】
図１９に示すように、最初に、依存解析部３７によって、動作レベル回路１１に記述された配列変数又は構造体変数について依存解析が行われ（ステップＳ１２１）、依存解析の結果が変数依存データベース１５に出力される。
【０１５９】
次いで、変数分割部３８によって、依存関係の有無について確認が行われる（ステップＳ１２２）。依存関係が存在しない場合は、変数分割部３８は、図６に示したステップＳ１０１と同様に、同一区間に記述されている変数の特定を行い（ステップＳ１２４）、その後、図６に示したステップＳ１０２と同様に変数分割を行う（ステップＳ１２５）。
【０１６０】
一方、依存関係が存在する場合は、変数分割部３８は、算出された距離ベクトルに基づいて、新たな変数（配列変数）を構成する変数を特定して（ステップＳ１２３）、変数分割を行う（Ｓ１２５）。なお、ステップＳ１２５においては、変数分割部３８によって変数分割が行なわれた修正後動作レベル回路３９が作成される。
【０１６１】
その後、修正後動作レベル回路３９に基づいて、参照回数の算出（ステップＳ１１）、ビット幅の抽出（ステップＳ１２）が行われる。更に、図６の例と同様に、ステップＳ１３〜ステップＳ１８が実行される。
【０１６２】
図２０は、変数分割を行った場合と変数分割を行わなかった場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図２０（ａ）は変数分割を行わなかった場合を示し、図２０（ｂ）は変数分割を行った場合を示している。
【０１６３】
図２０（ｂ）に示すように、変数分割部３８によって（図１７参照）、動作レベル回路１１（図１８（ａ）参照）に対して変数統合及び変数分割を行った場合は、修正後動作レベル回路３９（図１８（ｂ）参照）に記述された配列変数ａ１及びａ２それぞれに対して、８ビットのメモリを割り付けることができる。この場合、メモリアクセスのサイクル数の合計は１０サイクルとなる。
【０１６４】
一方、図２０（ａ）に示すように、動作レベル回路１１（図１１（ａ）参照）に対して変数分割を行わなかった場合は、配列ａに対して８ビットのメモリが一つしか割り付けられないため、メモリアクセスのサイクル数の合計は２０サイクルとなる。
【０１６５】
このように、本態様においても、実施の形態２と同様に、実施の形態１の場合よりも更にサイクル数の削減を図ることができる。
【０１６６】
また、本実施の形態３によれば、配列変数を配列要素で分割又は統合できるため、メモリ割り付けのバリエーションの増加を図ることができ、その結果、より少ないサイクル数を実現するメモリ割り付け方法を得ることが出来る。
【０１６７】
（実施形態４）
次に、本発明の実施の形態４における高位合成装置及び高位合成方法について、図２１〜図２３を参照しながら説明する。最初に、図２１を用いて、実施の形態４における高位合成装置の構成について説明する。図２１は、本発明の実施の形態４における高位合成装置の概略構成を示すブロック図である。
【０１６８】
図２１に示すように、本実施の形態４における高位合成装置４０は、変数グループ設定部４１を備えており、この点で実施の形態１において図１に示した高位合成装置１０と異なっている。また、高位合成装置４０に備えられたビット幅抽出部４２は、図１に示した高位合成装置１０に備えられたビット幅抽出部２と機能の点で異なっている。これらの点以外については、高位合成装置４０は、図１に示した高位合成装置１０と同様に構成されている。
【０１６９】
変数グループ設定部４１は、動作レベル回路１１に記述された変数によって構成された一又は複数の変数グループを設定する。このため、ビット幅抽出部４２は、変数グループのビット幅と、変数グループを構成していない変数のビット幅とを抽出する。また、ビット幅抽出部４２は、変数グループと変数グループを構成していない変数とについて割り当て対象となる複数のメモリ（メモリ候補）を選定する。
【０１７０】
ここで、変数グループ設定部４１によって行われる変数グループの設定について説明する。本実施の形態４において、変数グループ設定部４１が行う変数グループの設定方法としては、集中グループ化方法と、分散グループ化方法との２つがある
集中グループ化方法は、動作レベル回路１１において同一区間に記述された変数によって変数グループを構成する方法である。分散グループ化方法は、動作レベル回路１１において同一区間に記述されていない変数によって変数グループを構成する方法である。分散グループ化方法によれば、同一区間に記述された複数の変数は別々の変数グループを構成することになる。
【０１７１】
例えば、集中グループ化方法で複数のグループを設定し、変数グループ毎に別々のメモリに割り付けた場合、一定時間内においてメモリへのアクセスが１つのメモリに集中するために、他の非動作メモリを停止しておくことが可能である。
【０１７２】
一方、分散グループ化方法で複数のグループを設定した場合は、一定時間内にアクセスするメモリが別々になるために、異なる変数への同時アクセスが可能となり、メモリアクセスのサイクル数を短縮することができる。
【０１７３】
このように変数のグループ化方法により得られる効果が異なるため、変数グループ設定部４１においては、最終製品であるＬＳＩにおいて求められる効果に応じて分割方法が指定される。
【０１７４】
また、集中グループ化方法においては、変数グループの設定方法として、各変数グループを構成する変数の数量が変数グループ間で均一となるように設定する設定方法と、不均一となるように設定する設定方法とがある。
【０１７５】
前者の設定方法を採用した場合は、各変数グループのメモリ使用量を均一にできるため、同サイズのメモリを使用できる。よって、ＬＳＩにおけるレイアウトが容易になるという利点がある。
【０１７６】
一方、後者の設定方法を採用した場合は、変数グループ間で変数の数量を異ならせることによって、参照される期間が短い変数グループを設定できるため、一定時間内にアクセスが必要なメモリの数を減らすことができる。よって、メモリを停止する時間を長くすることが可能になる。
【０１７７】
また、本実施の形態４においては、変数グループ設定部４１によって設定できる変数グループの個数に上限を設定することができる。このように変数グループの個数に上限を設定した場合は、割り当てるメモリの数が多くなってＬＳＩにおけるオーバーヘッドの面積が増加するという事態を回避することができる。
【０１７８】
次に、図２２〜図２３を用いて、本実施の形態４における高位合成方法について説明する。本実施の形態４における高位合成方法は、図２１に示した本実施の形態４における高位合成装置４０を動作させることによって実施される。このため、以下においては、適宜図２１を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。
【０１７９】
図２２は、本発明の実施の形態４における高位合成方法を示すフローチャートである。図２３は、実施の形態４において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図２３（ａ）は動作レベル回路の一例を示し、図２３（ｂ）は図２３（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図２３（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【０１８０】
図２２に示すように、最初に、参照回数算出部１によって、動作レベル回路１１が読み込まれ、動作レベル回路１１に記述されている各変数について参照回数の算出が行われる（ステップＳ２１）。なお、ステップＳ２１は、図２に示したステップＳ１と同様に行なわれる。
【０１８１】
具体的には、図２３（ａ）に示す動作レベル回路の場合は、配列変数ａ及びｂと、メンバー変数ａ．ｍ１、ａ．ｍ２、ａ．ｍ３、ａ．ｍ４、ｂ．ｎ１、及びｂ．ｎ２について参照回数の算出が行われる。
【０１８２】
次に、変数グループ設定部４１によって、ステップＳ２１によって特定された各変数が同一区間に記述されているかどうかが判断され、判断結果に基づいて、変数グループの設定が行われる（ステップＳ２２）。本実施の形態４においても、実施の形態２と同様に、同一区間に記述されているかどうかの判断は、一つのｆｏｒ文内に記述されているかどうかによって行われている。
【０１８３】
図２２の例では、変数グループ設定部４１は、分散グループ化方法を採用しており、動作レベル回路１１において同一区間に記述されていない変数によって変数グループを構成する。図２３（ａ）に示す動作レベル回路においては、配列変数ａとｂとは、同一のｆｏｒ内に記述されていない、即ち、同一区間に記述されていない。このため、図２２の例では、変数グループ設定部４１は、図２３（ｂ）に示すように配列変数ａとｂとで構成されるグループｇ１を設定する。
【０１８４】
次に、ビット幅抽出部４２によって、変数グループと変数グループを構成していない変数とについてビット幅の抽出が行われ（ステップＳ２３）、更にメモリ候補となるメモリが選定されたメモリ候補リストの作成が行われる（ステップＳ２４）。また、ビット幅抽出部４２はメモリ候補リストをメモリ情報データベース１３に出力する。
【０１８５】
具体的には、ビット幅抽出部４２は、図２３（ｂ）に示すように、変数グループｇ１と、変数グループｇ１を構成していないメンバー変数ａ．ｍ１、ａ．ｍ２、ａ．ｍ３、ａ．ｍ４、ｂ．ｎ１、及びｂ．ｎ２とについてビット幅を抽出する。
【０１８６】
図２３の例では、変数グループのビット幅の抽出は、変数グループに含まれる変数の中からビット幅が最大となる変数を特定し、この特定された変数のビット幅を抽出することによって行われている。例えば、図２３（ａ）の例においては、配列変数ａ、ｂの両方が３２ビットであるため、変数グループｇ１のビット幅は３２ビットとなる。また、仮に、ｎ１及びｎ２がｃｈｒ型であり、配列変数ｂのビット幅が１６ビットであっても、配列変数ａのビット幅が３２ビットである場合は、変数グループｇ１のビット幅は３２ビットとなる。
【０１８７】
また、図２２の例では、変数グループとそれを構成していないメンバー変数とは、一つのメモリに割り当てられる。このため、図２３（ｃ）に示すように、メモリ候補としては、８ビットのメモリＭ４１、１６ビットのメモリＭ４２、３２ビットのメモリＭ４３が選定されている。
【０１８８】
なお、図２３（ａ）に示す動作レベル回路の場合、変数グループは一つしか設定されていないが、本実施の形態４においては、変数グループが複数ある場合は、各変数グループについてビット幅の抽出が行われる。また、変数グループが複数存在する場合は、複数の変数グループを１つのメモリに割り付ける場合も含めてメモリ候補リストが作成される。
【０１８９】
次いで、メモリ選択部３によって、ステップＳ２１で算出された参照回数とステップＳ２３で抽出されたビット幅とに基づいて、図２３（ｃ）に示すように各メモリ候補についてメモリアクセスのサイクル数の合計が算出される（ステップＳ２５）。なお、ステップＳ２５は、図２に示したステップＳ４と同様に行なわれる。
【０１９０】
更に、その後、図２に示したステップＳ５と同様に、メモリ選択部３によって、全てのメモリ候補について、メモリアクセスのサイクル数の合計が算出されているかどうかの判断が行われる（ステップＳ２６）。
【０１９１】
全てのメモリ候補についてサイクル数の合計の算出が終了していない場合は、メモリ選択部３によって、再度ステップＳ２５が実行される。一方、全てのメモリ候補についてサイクル数の算出が終了している場合は、メモリ選択部３によってステップＳ２７が実行される。
【０１９２】
ステップＳ２７においては、図２に示したステップＳ６と同様に、メモリ選択部３によって、各メモリ候補についてサイクル数の合計の比較が行われる。本実施の形態４においては、メモリアクセスのサイクル数の合計が最小となる３２ビットのメモリＭ４３が割り当て対象として選択される。
【０１９３】
その後、図２に示したステップＳ７及びＳ８と同様に、スケジューリング部４によるスケジューリング（ステップＳ２８）及び、リソース割当部５によるリソースの割当等が行なわれ、論理回路が生成される（ステップＳ２９）。生成された論理回路は外部へと出力される。
【０１９４】
以上のように、本実施の形態４においても、実施の形態１と同様に、動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択できるので、メモリアクセスのサイクル数を最適なものとできる。
【０１９５】
また、本実施の形態４においては、実施の形態１と異なり、メモリを割り付ける対象となる複数の変数が１つのメモリに割り付けられるため、複数のメモリを使用する場合に生じるオーバーヘッドの面積分を削減できる。このため、ＬＳＩにおいて使用されるメモリの面積を小さくすることが可能になる。
【０１９６】
また、本実施の形態４において、同一区間はｆｏｒ文によって記述された区間としているが、これに限定されるものではない。実施の形態２と同様に、例えば、動作レベル回路１１における基本ブロックを同一区間と定義しても良い。
【０１９７】
更に、スケジューリング部４によって、ステップＳ２８におけるスケジューリングとは別の仮スケジューリングを行い、この仮スケジューリングの結果から同一サイクルでアクセスされる可能性があると判断できる複数の変数については、同一区間に記述されていると定義することもできる。
【０１９８】
ここで、スケジューリング部４によって仮スケジューリングを行う態様について説明する。仮スケジューリングを行う態様であっても、高位合成装置は、図２１に示す構成を有している。但し、変数グループ設定部４１（図２１参照）及びスケジューリング部４（図５参照）における動作の点で、図２１に示す高位合成装置４０と異なっている。このため、高位合成方法を実施するための工程も図２２に示すものと異なっている。
【０１９９】
図２４を用いて仮スケジューリングが行われる場合の実施の形態４における高位合成方法について説明する。図２４は、仮スケジューリングを行う場合の実施の形態４における高位合成方法を示すフローチャートである。なお、以下の説明においては、適宜図２１を参照する。
【０２００】
図２４に示すように、先ず、スケジューリング部４によって、図９に示したステップＳ１１１と同様に、仮スケジューリングが行われる（ステップＳ１３１）。具体的には、スケジューリング部４は、動作レベル回路１１に記述された全ての変数を互いに異なるメモリに割り当てて、動作レベル回路１１の実行サイクルのスケジューリングを行う。
【０２０１】
次に、ステップＳ２１が実行され（図２２参照）、更に、変数グループ設定部４１によって、ステップＳ１３１のスケジューリングの結果に基づいて、同一区間に記述されている変数が特定されて、変数グループが設定される（ステップＳ１３２）。
【０２０２】
具体的には、変数グループ設定部４１によって、予め定められた実行サイクルのサイクル数の範囲内でアクセスされている変数が特定され、同一区間に記述されているかどうかが判断される。同一区間かどうかの判断は、図９に示したステップＳ１１２と同様に行なわれる。
【０２０３】
その後、図２２の例と同様に、ステップＳ２３〜Ｓ２９が実行される。このような態様においても、同一区間に記述されていない変数によって構成された変数グループを設定でき、メモリを割り付ける対象となる複数の変数を１つのメモリに割り付けることができる。
【０２０４】
（実施の形態５）
次に、本発明の実施の形態５における高位合成装置及び高位合成方法について、図２５〜図３０を参照しながら説明する。最初に、図２５を用いて、実施の形態５における高位合成装置の構成について説明する。図２５は、本発明の実施の形態５における高位合成装置の概略構成を示すブロック図である。
【０２０５】
図２５に示すように、本実施の形態５における高位合成装置５０は、依存解析部５１及び実行順序入替部５３を備えており、この点で実施の形態１において図１に示した高位合成装置１０と異なっている。また、高位合成装置５０に備えられたメモリ選択部５２及びスケジューリング部５４は、図１に示した高位合成装置１０に備えられたメモリ選択部３及びスケジューリング部４と機能の点で異なっている。これらの点以外については、高位合成装置５０は、図１に示した高位合成装置１０と同様に構成されている。
【０２０６】
依存解析部４１は、実施の形態３において図１７に示した依存解析部３７とは異なる機能を備えている。依存解析部４１は、動作レベル回路１１に記述された繰り返し処理を抽出し、抽出された繰り返し処理に含まれる変数の依存関係を解析し、解析結果を変数依存情報データベース５５に出力する。また、実行順序入替部５３は、依存解析部５１による依存関係の解析の結果に基づいて、同時に参照される変数が同一の実行サイクルで実行されるように、繰り返し処理内の実行順序の入れ替えを行う。
【０２０７】
スケジューリング部５４は、実施の形態１において図１に示したスケジューリング部４と異なり、変数に割り当てられるメモリが決定される前にスケジューリングを行う。本実施の形態５においては、スケジューリング部５４は、メモリ選択部５２がメモリアクセスのサイクル数を算出する前に、メモリ候補として選定されたメモリに変数を割り当てて、動作レベル回路１１における実行サイクルのスケジューリングを行う。これにより、メモリへのアクセスが行われるサイクルと演算の実行されるサイクルとの関係が得られる。
【０２０８】
また、メモリ選択部５２は、実施の形態１において図１に示したメモリ選択部３と同様の機能に加えて、スケジューリング部５４によるスケジューリングの結果に基づいて、メモリアクセスと並行して実行することが可能な演算処理が存在しているかどうかを判定し、演算処理が存在している場合は、算出したメモリアクセスのサイクル数の合計を補正する機能を有している。
【０２０９】
本実施の形態５においては、メモリ選択部５２は、スケジューリングの結果から、メモリアクセスが読み出し後に書き込みを行う先行読み出し処理であるかどうか、又この先行読み出しサイクルと他の演算処理とを並行して実行できるかどうかを判定する。また、メモリ選択部５２は、判定の結果、先行読み出しサイクルが存在し、これを他の演算処理と並行して実行することができる場合は、メモリアクセスの先行読み出しサイクル数がトータルのサイクル数に含まれないようにトータルのサイクル数を補正する。
【０２１０】
次に、図２６〜図３０を用いて、本実施の形態５における高位合成方法について説明する。本実施の形態５における高位合成方法は、図２５に示した本実施の形態５における高位合成装置５０を動作させることによって実施される。このため、以下においては、適宜図２５を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。
【０２１１】
図２６は、本発明の実施の形態５における高位合成方法を示すフローチャートである。図２７は、実施の形態５において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図２７（ａ）は動作レベル回路の一例を示し、図２７（ｂ）は図２７（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図２７（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【０２１２】
図２６に示すように、最初に、参照回数算出部１によって、動作レベル回路１１が読み込まれ、動作レベル回路１１に記述されている各変数について参照回数の算出が行なわれる（ステップＳ３１）。なお、ステップＳ３１は、図２に示したステップＳ１と同様に行なわれる。
【０２１３】
具体的には、図２７（ａ）に示す動作レベル回路の場合は、図２７（ｂ）に示すように、配列変数ａ〜ｃと、メンバー変数ａ．ｍ１、ａ．ｍ２、ｂ．ｍ１、ｂ．ｍ２、ｃ．ｍ１、及びｃ．ｍ２について参照回数の算出が行われる。なお、図２７（ｂ）においては、配列変数ａ、メンバー変数ａ．ｍ１及びａ．ｍ２の参照回数のみが示されている。
【０２１４】
次に、依存解析部５１によって、動作レベル回路１１に記述されたｆｏｒループ内に含まれる変数について、依存関係の解析が行われる（ステップＳ３２）。具体的には、図２７（ａ）に記述された１番目〜４番目のｆｏｒ文に含まれている変数について依存解析が行われる。また、依存解析部５１は、解析結果を変数依存情報データベース５５に出力する。
【０２１５】
次いで、実行順序入替部５３によって、変数情報依存情報データベース５５から依存解析部５による解析結果が読み出され、これに基づいて、実行順序の入れ替えが可能かどうか、つまり、同時に参照される複数の変数がｆｏｒ文に含まれているかどうかの判断が行われる（ステップＳ３３）。
【０２１６】
判断の結果、実行順序の入れ替えが可能でない場合は、ビット幅抽出部２によって、実施の形態１において図２に示したステップＳ２と同様に、各変数のビット幅（図２７（ｂ）参照）の抽出が行われる（ステップＳ３５）。
【０２１７】
一方、実行順序の入れ替えが可能であると判断した場合は、実行順序入替部５３によって実行順序の入れ替えが行われ（ステップＳ３４）、その後、ステップＳ３５が実施される。
【０２１８】
本実施の形態５においては、実行順序入替部５３は、図２７（ａ）に示した動作レベル回路の３番目のｆｏｒ文について実行順序の入れ替えが可能であると判断し、３番目のｆｏｒ文について実行順序の入れ替えが行われる。この点について、図２８を用いて説明する。
【０２１９】
図２８は、図２７（ａ）に示した動作レベル回路の３番目のｆｏｒ文における実行順序示す図であり、図２８（ａ）は実行順序の入れ替えの前を示し、図２８（ｂ）は実行順序の入れ替えの後を示している。また、図２８においては、３番目のｆｏｒ文はソースコードによって表現されている。
【０２２０】
本実施の形態５においては、実行順序入替部５３は、図２８（ａ）に示す動作レベル回路から、書き込み処理の前に必要となる読み出し処理（先行読み出し処理）を抽出し、図２８（ｂ）に示すように、先行読み出し処理の順序を入れ替えている。
【０２２１】
図２８（ａ）から分るように、入れ替え前においては、一回のｆｏｒループで配列変数がアクセスする回数は３回であり、必要とされるサイクルの合計は２７サイクルとなる。それに対し、図２８（ｂ）から分るように、入れ替え後においては、一回のｆｏｒループで配列変数がアクセスする回数は２回となり、１回分が削減される。また、必要となるサイクルの合計は１９サイクル（ループ内１８サイクル、ループ外１サイクル）となり、合計で８サイクルが削減される。
【０２２２】
ステップＳ３５が実行されると、ビット幅抽出部２によって、配列変数ａ、ｂ及びｃを割り当てるメモリが選定される。本実施の形態５においては、各配列変数について８ビットのメモリと１６ビットのメモリとがメモリ候補として選定されている。なお、図２７（ｃ）においては、配列変数ａのメモリ候補Ｍ５１（８ビット）とＭ５２（１６ビット）のみが示されている。
【０２２３】
次いで、スケジューリング部５４によって、動作レベル回路１１における実行サイクルのスケジューリングが行われる（ステップＳ３７）。なお、スケジューリングは、メモリ候補として選定されたメモリに変数を割り当てて行われており、メモリ候補ごとに行われる。
【０２２４】
図２９は、図２７（ａ）に示した動作レベル回路をスケジューリングした結果を示す図である。また、図２９は、メモリ候補が１６ビットの場合のスケジューリング結果を示している。更に、図２９においては、図２７（ａ）に示した動作レベル回路における２番目のｆｏｒ文と３番目のｆｏｒ文とが示されている。
【０２２５】
図２９において、実線で描かれた矢印はデータ及び制御の流れを示している。破線で描かれた矢印は、メモリのビット幅が変数のビット幅よりも大きい場合に、書き込み（Ｗ）処理の前に必要となる読み出し（Ｒ）処理（先行読み出し処理）の流れを示している。
【０２２６】
また、図２９において、６２ａ及び６２ｂは、メモリのビット幅が変数のビット幅よりも大きい場合の書き込み（Ｗ）処理を示し、６１ａ〜６１ｃは、メモリのビット幅が変数のビット幅よりも大きい場合の先行読み出し処理を示している。三角記号は、ｆｏｒループの繰り返し判定を示している。また、６３は演算処理「＊」を示し、６４は演算処理「＋」を示している。６５は読み出し処理を示している。
【０２２７】
次に、メモリ選択部５２によって、各メモリ候補についてメモリアクセスのサイクル数の算出が行われる（ステップＳ３８）。本実施の形態５においては、サイクル数の算出には、他の実施の形態と異なり、図３０に示すメモリアクセスサイクル表が用いられる。図３０は、実施の形態５において用いられるメモリアクセスサイクル表を示す図である。
【０２２８】
また、本実施の形態５においては、メモリ選択部５２は、メモリアクセスが先行読み出し処理であるかどうか、先行読み出し処理である場合は他の演算処理と並行して実行できるかどうかを判断し、判断結果に基づいてサイクル数の算出に補正を行っている。更に、メモリ選択部５２は、ステップＳ３４における実行順序の入れ替えがあった場合も、サイクル数の算出に補正を行っている。この点について図２７（ｂ）を参照しながら説明する。
【０２２９】
図２７（ｃ）における「サイクル数１（第３カラム）」は、ステップＳ３７のスケジューリング及びステップＳ３４の実行順序の入れ替えを考慮しないで、算出されたサイクル数を示している。つまり、図２７（ｂ）に示す参照回数と図３０に示すメモリアクセスサイクル表とを参照して、実施の形態１において図２に示したステップＳ４と同様に算出されたサイクル数を示している。
【０２３０】
具体的には、メモリ候補がＭ５１の場合は、ｍ１（Ｒ）＋ｍ１（Ｗ）＋ｍ２（Ｗ）＋ａ（Ｒ）＝９＋１０＋９＋（１０×２）＝４８となる。メモリ候補がＭ５２の場合は、ｍ１（Ｒ）＋ｍ１（Ｗ）＋ｍ２（Ｗ）＋ａ（Ｒ）＝９＋（１０×２）＋（９×２）＋１０×２＝５７となる。
【０２３１】
また、図２７（ｃ）における「サイクル数２（第４カラム）」は、スケジューリング結果から、先行読み出しサイクルが存在し、これを他の演算処理と並行して実行することができるとメモリ選択部５２が判断した場合のサイクル数を示している。
【０２３２】
図２９に示すように、メモリ候補が１６ビットのＭ５２の場合は、図２９に示す演算処理「＋」６４と、先行読み出し処理６１ａとは同一サイクルにあり、並行して実行できるため、変数ａ．ｍ１に対する先行読み出し処理６１ａのサイクル数がトータルのサイクル数に含まれないようにして算出が行われている。
【０２３３】
具体的には、メモリ候補がＭ５２の場合は、ｍ１（Ｒ）＋ｍ１（Ｗ）＋ｍ２（Ｗ）＋ａ（Ｒ）＝９＋１０＋（９×２）＋１０＝４７となる。なお、メモリ候補がＭ５１の場合は、先行読み出し処理は行われないため、サイクル数は「サイクル数１（第３カラム）」の場合と同じになる。
【０２３４】
また、図２７（ｃ）における「サイクル数３（第５カラム）」は、サイクル数２の場合に加えて、更に、ステップＳ３４の実行順序の入れ替えをも考慮して算出されたサイクル数を示している。
【０２３５】
図２９に示された３番目のｆｏｒ文から分るように、ステップＳ３４の実行順序の入れ替えにより、読み出し処理６５と先行読み出し処理６１ｃとは同一の実行サイクルで並行して行われる。このため、先行読み出し処理６１ｃのサイクル数がトータルのサイクル数に含まれないようにして算出が行われている。但し、先行読み出し処理６１ｂがループ外で行われるため、先行読み出し処理６１ｂのサイクル数（１回）を加算する必要がある。
【０２３６】
具体的には、メモリ候補がＭ５２の場合は、ｍ１（Ｒ）＋ｍ１（Ｗ）＋ｍ２（Ｗ）＋ａ（Ｒ）＝９＋１０＋（９＋１）＋１０＝３９となる。なお、メモリ候補がＭ５１の場合は、先行読み出し処理は行われないため、サイクル数は「サイクル数１（第３カラム）」の場合と同じになる。
【０２３７】
その後、図２に示したステップＳ５と同様に、メモリ選択部５２によって、全てのメモリ候補について、メモリアクセスのサイクル数の合計が算出されているかどうかの判断が行われる（ステップＳ３９）。
【０２３８】
全てのメモリ候補についてサイクル数の合計の算出が終了していない場合は、メモリ選択部５２によって、再度ステップＳ３８が実行される。一方、全てのメモリ候補についてサイクル数の算出が終了している場合は、メモリ選択部３によってステップＳ４０が実行される。
【０２３９】
ステップＳ４０においては、図２に示したステップＳ６と同様に、メモリ選択部５２によって、各メモリ候補についてサイクル数の合計の比較が行われる。本実施の形態５においては、メモリアクセスのサイクル数の合計が最小となる１６ビットのメモリＭ５２が割り当て対象として選択される。
【０２４０】
最後に、図２に示したステップＳ８と同様に、リソース割当部５によるリソースの割当等が行なわれ、論理回路が生成される（ステップＳ４１）。生成された論理回路は外部へと出力される。
【０２４１】
以上のように、本実施の形態５においても、実施の形態１と同様に、動作レベル回路に記述されている動作に依存した最適なビット幅のメモリを選択できるので、メモリアクセスのサイクル数を最適なものとできる。
【０２４２】
また、本実施の形態５によれば、依存解析やスケジューリングによって、メモリアクセスと並行して実行可能な演算処理の有無を解析でき、結果メモリアクセスのサイクルの一部が隠蔽される場合を考慮できるため、実施の形態１に比べて更に最適なビット幅のメモリの割り付けを行うことが可能となる。
【０２４３】
（実施の形態６）
次に、本発明の実施の形態６における高位合成装置及び高位合成方法について、図３１〜図３３を参照しながら説明する。最初に、図３１を用いて、実施の形態６における高位合成装置の構成について説明する。図３１は、本発明の実施の形態６における高位合成装置の概略構成を示すブロック図である。
【０２４４】
図３１に示すように、本実施の形態６における高位合成装置６０は、メモリアクセス解析部４４を備えており、この点で実施の形態４において図２１に示した高位合成装置４０と異なっている。また、高位合成装置６０のスケジューリング部４３は、図２１に示した高位合成装置４０のスケジューリング部４と機能の点で異なっている。これらの点以外については、高位合成装置６０は、実施の形態４において図２１に示した高位合成装置４０と同様に構成されている。
【０２４５】
スケジューリング部４３は、スケジューリング部４（図２１参照）と異なり、ビット幅抽出部４２によるメモリ候補リストの作成後であってメモリ選択部３によるメモリの選択前に、選定されたメモリ（メモリ候補）に変数を割り当てて、動作レベル回路１１における実行サイクルのスケジューリングを行う。スケジューリング部４３によるスケジューリングは、メモリ候補毎に行われる。
【０２４６】
このようなスケジューリングにより、メモリへのアクセスが行われるサイクルと演算の実行されるサイクルとの関係を示す情報が得られ、この情報はスケジューリング部４３によってメモリアクセス解析部４４へと出力される。
【０２４７】
また、メモリアクセス解析部４４は、メモリ選択部３がメモリ候補の中から割り当て対象となるメモリを選択した後に、スケジューリング部４３によるスケジューリングから得られるメモリへのアクセスパターンを表示装置４５によって表示する。
【０２４８】
本実施の形態６においては、メモリアクセス解析部４４は、同一メモリへの予め設定されたサイクル数以上の連続したアクセスが存在している場合と、同一サイクルでアクセスされない複数のメモリが存在している場合に、アクセスパターンを抽出し、これを表示装置４６に表示させる。
【０２４９】
また、メモリアクセス解析部４４には、入力装置４６が接続されており、高位合成装置６０を利用する利用者からの指示が入力装置４６を介して入力される。
【０２５０】
次に、図３２〜図３３を用いて、本実施の形態６における高位合成方法について説明する。本実施の形態６における高位合成方法は、図３１に示した本実施の形態６における高位合成装置６０を動作させることによって実施される。このため、以下においては、適宜図３１を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。図３２は、本発明の実施の形態６における高位合成方法を示すフローチャートである。
【０２５１】
図３２に示すように、先ず、実施の形態４において図２２に示した例と同様に、動作レベル回路１１に記述された各変数の参照回数の算出（ステップＳ２１）、変数グループの設定（ステップＳ２２）、ビット幅の抽出（ステップＳ２３）、メモリ候補リストの作成（ステップＳ２４）が順次行なわれる。
【０２５２】
次に、本実施の形態６においては、実施の形態４において図２２に示した例と異なり、スケジューリング部４３によってスケジューリングが行われる（ステップＳ５１）。具体的には、スケジューリング部４３は、メモリ候補リストに特定されているメモリ候補に変数を割り当てて、動作レベル回路１１における実行サイクルのスケジューリングを行う。
【０２５３】
次に、メモリ選択部３によって、実施の形態４において図２２に示した例と同様に、メモリアクセスのサイクル数の算出が行われる（ステップＳ２５）。更に、メモリ選択部３によって、全てのメモリ候補について、スケジューリング及びサイクル数の合計の算出が完了しているかどうかの判断が行われる（ステップＳ５２）。
【０２５４】
全てのメモリ候補についてスケジューリング及びサイクル数の合計の算出が完了していない場合は、再度ステップＳ５１及びＳ２５が再度実行される。一方、全てのメモリ候補についてスケジューリング及びサイクル数の算出が完了している場合は、メモリ選択部３によって、実施の形態４において図２２に示した例と同様に、サイクル数の合計が最小となるメモリが割り当て対象として選択される（ステップＳ２７）。
【０２５５】
次に、メモリアクセス解析部４４によって表示装置４６へとアクセスパターンの表示データが出力され、表示装置４６に、ステップＳ５１のスケジューリング結果を示すアクセスパターンが表示される（ステップＳ５３）。なお、ステップＳ５３で出力されるアクセスパターンは、ステップＳ２７において選択されたメモリを変数に割り当てた場合のアクセスパターンである。
【０２５６】
具体的には、メモリアクセス解析部４４は、先ず、ステップＳ５１におけるスケジューリングの結果から、同一メモリへの予め設定されたサイクル数以上の連続したアクセスや、同一サイクルでアクセスされない複数のメモリについて抽出を行う。
【０２５７】
この結果、前者について抽出できた場合は、メモリアクセス解析部４４は、この連続したアクセスを示すアクセスパターン（図３３（ａ）参照）を表示装置４６に表示させる。後者について抽出できた場合は、この複数のメモリのアクセス状態を示すアクセスパターン（図３３（ｂ）参照）を表示装置４６に表示させる。ここで、図３３を用いてアクセスパターンについて説明する。
【０２５８】
図３３は、アクセスパターンの一例を示す図であり、図３３（ａ）は同一メモリへの予め設定されたサイクル数以上の連続したアクセスを示すアクセスパターンを示し、図３３（ｂ）は同一サイクルでアクセスされない複数のメモリのアクセス状態を示すアクセスパターンを示している。
【０２５９】
図３３（ａ）及び（ｂ）に示すように、アクセスパターンは、スケジューリング結果を示す「スケジューリングビュー」とスケジューリングビュー内の変数のメモリマップ状況を図示する「メモリアクセスビュー」とを備えている。メモリアクセスビューにおいては、縦軸は実行サイクル数を示しており、図中の数字はアクセスされたメモリアドレスを示している。なお、図３３中のＭ６１、Ｍ６２は変数ａを割り付けたメモリを示している。
【０２６０】
図３３（ａ）及び（ｂ）に示すスケジューリングビューにおいて、各実行サイクルは破線によって区分けされている。例えば、Ｗ：ａ［２ｉ］とＷ：ａ［２ｉ＋１］とは、別々の実行サイクルにスケジューリングされたことを示している。また、図３３（ａ）及び（ｂ）に示したアクセスパターンは、変数ｉを１ずつ増加させる繰り返しループが記述された動作レベル回路のアクセスパターンである。
【０２６１】
このような図３３（ａ）に示すアクセスパターンが表示装置４５に表示されると、利用者は、メモリＭ６１に一定サイクル以上連続でアクセスが行われていることを知ることができる。一方、図３３（ｂ）に示すアクセスパターンが表示装置４５に表示されると、メモリＭ６１とメモリＭ６２とが同一サイクルでアクセスされていないことを知ることができる。よって、利用者は現在のメモリの割り当てによって得られるアクセスパターンが意図したものかどうかを判断することができる。
【０２６２】
その後、メモリアクセス解析部４４によって、入力装置４６から、利用者の意図したアクセスパターンであることを示す入力があったかどうかの判断が行われる（ステップＳ５４）。利用者からの入力が利用者の意図したアクセスパターンではないことを示す場合は、ステップＳ２２の変数グループの設定から再度実行される。一方、利用者からの入力が利用者の意図したアクセスパターンであることを示す場合は、論理回路の生成が行われ（ステップＳ５５）、その後処理は終了する。
【０２６３】
以上のように、本実施の形態６によれば、利用者は、変数のメモリへの割り付けが意図した通りであるかどうかを、表示されたメモリへのアクセスパターンによって確認することができる。このため、意図していないアクセスパターンの場合は、変数グループの設定から再度やり直すこと出来るので、より効果的なグループ分類が可能となる。
【０２６４】
なお、図３１〜図３３に示す例では、変数グループを設定する場合について説明しているが、本実施の形態６はこのような態様に限定されず、例えば、実施の形態１〜３のように、変数の分割や統合を行う場合にも適用できる。
【０２６５】
（実施の形態７）
次に、本発明の実施の形態７における高位合成装置及び高位合成方法について、図３４〜図３７を参照しながら説明する。最初に、図３４を用いて、実施の形態７における高位合成装置の構成について説明する。図３４は、本発明の実施の形態７における高位合成装置の概略構成を示すブロック図である。
【０２６６】
図３４に示すように、本実施の形態７における高位合成装置７０は、制約条件判定部７２を備えており、この点で実施の形態１において図１に示した高位合成装置１０と異なっている。また、高位合成装置７０に備えられたメモリ選択部７１は、図１に示した高位合成装置１０に備えられたメモリ選択部３と機能の点で異なっている。これらの点以外については、高位合成装置７０は、図１に示した高位合成装置１０と同様に構成されている。
【０２６７】
制約条件判定部７２は、メモリ選択部７１によって変数を割り付けるメモリが選択されると、選択されたメモリに対応する複数のメモリセルを特定する。なお、本実施の形態７において、メモリセルの特定は、ＬＳＩ設計用のライブラリ（図示せず）に基づいて行われている。
【０２６８】
また、制約条件判定部７２は、特定されたメモリセルのアクセス時間が予め設定された条件を満たすかどうか、即ち遅延違反となっていないかどうかを判定する。判定の結果、遅延違反となっていないメモリセルが存在する場合は、アクセス時間が最も短いメモリセルを選択する。一方、全ての特定されたメモリセルが遅延違反となっている場合は、メモリセルの選択を行わない。
【０２６９】
具体的には、本実施の形態７においては、制約条件判定部７２は、先ず、ＬＳＩ設計用のライブラリから、特定されたメモリセルのアクセス時間を取得し、次に、スケジューリング部４によるスケジューリングの結果から、特定されたメモリセルにおけるメモリアクセス以外の演算の実行時間とを求め、１サイクルにおける遅延時間を算出する。例えば、メモリアクセス時間が４ｎｓ、メモリアクセス以外の演算の実行時間が７ｎｓである場合は、遅延時間は１１ｎｓとなる。
【０２７０】
更に、制約条件判定部７２は、算出した遅延時間と、予め設定された１実行サイクルにおける遅延時間（以下、「遅延制約時間」という。）とを比較する。例えば、遅延制約時間が１０ｎｓに設定されている場合を考える。上記のように算出された遅延時間が１１ｎｓの場合は、１ｎｓ（＝１１ｎｓ−１０ｎｓ）の遅延違反となる。また、このことから、メモリアクセス時間の制約は、３ｎｓ（＝４ｎｓ−１ｎｓ）となる。
【０２７１】
一方、上記の場合よりもメモリアクセス時間が短い場合、例えばメモリアクセス時間が３ｎｓの場合は、遅延時間は１０ｎｓ（＝３ｎｓ＋７ｎｓ）となり、遅延制約時間の範囲内にあるので、遅延制約を満たす。
【０２７２】
また、メモリ選択部７１は、一旦メモリを選択した後、制約条件判定部７２によって、メモリセルが選択されていない場合は、選択されていたメモリ候補を除いて、再度メモリ候補の中からメモリを選択する。
【０２７３】
次に、図３５〜図３６を用いて、本実施の形態７における高位合成方法について説明する。本実施の形態７における高位合成方法は、図３４に示した本実施の形態７における高位合成装置７０を動作させることによって実施される。このため、以下においては、適宜図３４を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。
【０２７４】
図３５は、本発明の実施の形態７における高位合成方法を示すフローチャートである。図３６は、実施の形態６において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図３６（ａ）は動作レベル回路の一例を示し、図３６（ｂ）は図３６（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図３６（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【０２７５】
図３５に示すように、先ず、実施の形態１において図２に示したステップＳ１及びＳ２と同様に、動作レベル回路１１に記述された各変数の参照回数の算出（ステップＳ６１）、ビット幅の抽出（ステップＳ６２）、メモリ候補リストの作成（ステップＳ６３）が行われる。
【０２７６】
この結果、図３６（ｂ）に示すように、各変数の参照回数とビット幅とが特定される。また、図３６（ｃ）に示すように、８ビットのメモリＭ７１と３２ビットのメモリＭ７２とがメモリ候補として選定される。
【０２７７】
次に、実施の形態１において図２に示したステップＳ４〜Ｓ６と同様に、メモリ候補それぞれについてメモリアクセスのサイクル数の合計の算出（ステップＳ６４）、全てのメモリ候補について算出が終了したかどうかの確認（ステップＳ６５）、サイクル数の最も小さいメモリの選択（ステップＳ６６）が行われる。
【０２７８】
本実施の形態７においては、図３６（ｃ）から分るように、３２ビットのメモリＭ７２を選択した場合にサイクル数の合計は最も小さくなるため、メモリＭ７２が選択される。
【０２７９】
次いで、実施の形態１において図２に示したステップＳ７と同様に、選択されたメモリ（メモリＭ７２）に変数を割り当てて、スケジューリングが行われる（Ｓ６７）。
【０２８０】
その後、実施の形態１であれば論理回路が生成されて処理は終了するが、本実施の形態７においては、続いて、制約条件判定部７２によって、選択されたメモリ（メモリＭ７２）に対応するメモリセルの特定が行なわれる（ステップＳ６８）。
【０２８１】
次いで、制約条件判定部７２によって、特定された各メモリセルにおける遅延時間が算出され、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在するかどうかの判定が行われる（ステップＳ６９）。
【０２８２】
判定の結果、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在する場合は、制約条件判定部７２は、メモリアクセス時間が最も短いメモリセルを選択する（ステップＳ７０）。その後、実施の形態１における図２の例と同様に、論理回路の生成が行なわれ（ステップＳ８）、その後処理は終了する。
【０２８３】
一方、判定の結果、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在しない場合は、再度ステップＳ６６が実行される。但し、このステップＳ６６は、最初に選択されたメモリをメモリ候補リストから除外して実行される。
【０２８４】
なお、図３５の例では、一度スケジューリングを行い、スケジューリングの結果から遅延時間を求めて遅延違反の判定を行っているが、本実施の形態７においては、例えば、スケジューリングを行わずに事前にアクセス時間に上限を設定しておき、このアクセス時間の上限値によって遅延違反かどうかの判定を行うこともできる。
【０２８５】
ここで、図３７を用いて、ステップＳ６６〜Ｓ７０を具体的に説明する。図３７は、３２ビットのメモリを実装可能な物理メモリセルの一覧を示す図である。図３７には、各メモリセルを使用した場合のアクセス時間と面積が記述されている。
【０２８６】
例えば、上述のように遅延制約時間が１０ｎｓに設定されており、メモリアクセス以外の演算の実行時間が７ｎｓである場合について説明する。この場合、メモリアクセス時間の制約は、３ｎｓである。
【０２８７】
先ず、図３７に示すように、メモリ選択部７１によって選択されたメモリに対応するメモリセルとして、メモリセル「Ｔ１６１０」、「Ｔ１６２０」、「Ｔ３２１０」、「Ｔ３２２０」が特定される。
【０２８８】
次いで、各メモリセルについて遅延違反があるかどうかの判定が行なわれる。例えば、図３７に示すメモリセル「Ｔ３２２０」の場合、アクセス時間は４ｎｓであるので、ステップＳ６８においては遅延違反が１ｎｓであると判定される。同様に、メモリセル「Ｔ１６２０」においては、遅延違反が０．５ｎｓであると判定される。
【０２８９】
一方、メモリセル「Ｔ１６１０」のアクセス時間は２．５ｎｓ、メモリセル「Ｔ３２２０」のアクセス時間は３．０ｎｓであるので、これらのメモリセルについては、遅延違反はない。よって、アクセス時間が制約を満たすメモリセルが存在していると判定される。
【０２９０】
この後、アクセス時間が短いメモリセル「Ｔ１６１０」が選択される。なお、本実施の形態７においては、アクセス時間を基準にして最終的なメモリセルの選択を行っているが、例えばメモリセルの面積を基準に選択を行うこともできる。つまり、メモリセルの面積が最も小さいメモリセル「Ｔ３２１０」を選択することもできる。
【０２９１】
以上のように、本実施の形態７によれば、メモリの大きさに応じてアクセス時間が異なる場合であっても、アクセス時間をメモリ選択時の評価指標とできるため、変数を最適なメモリに割り付けることが可能となる。
【０２９２】
（実施の形態８）
次に、本発明の実施の形態８における高位合成装置及び高位合成方法について、図３８〜図３９を参照しながら説明する。最初に、図３８を用いて、実施の形態８における高位合成装置の構成について説明する。図３８は、本発明の実施の形態８における高位合成装置の概略構成を示すブロック図である。
【０２９３】
図３８に示すように、本実施の形態８における高位合成装置８０は、配置配線部８４を備えており、この点で、実施の形態７において図３４に示した高位合成装置７０と異なっている。また、高位合成装置８０に備えられたメモリ選択部８１、制約条件判定部８２及びスケジューリング部８３は、図３４に示した高位合成装置７０に備えられたメモリ選択部７１、制約条件判定部７２及びスケジューリング部４と機能の点で異なっている。これらの点以外については、高位合成装置８０は、図３４に示した高位合成装置７０と同様に構成されている。
【０２９４】
配置配線部８４は、メモリ選択部８１によって選択されたメモリに変数を割り当てて、配置配線を行い、これによってレイアウト情報を生成する。レイアウト情報は、選択されたメモリの配置位置と、このメモリに接続される回路の配置位置とを特定する情報であり、レイアウト情報データベース８６に出力される。
【０２９５】
本実施の形態８においては、配置配線部８４によるレイアウト情報の生成は、リソース割当部５によって生成された論理回路に基づいて、レイアウト設計を行うことによって行われている。つまり、本実施の形態８においては、リソース割当部５は、配置配線部８４によるレイアウト設計のための論理回路の生成も行っている。生成された論理回路は回路接続情報データベース８５に出力されており、配置配線部８４は必要に応じて回路接続情報データベースにアクセスしている。
【０２９６】
また、配置配線部８４は、レイアウト情報に基づいて、選択されたメモリのアクセス時間、配線混雑度、デッドスペースの面積を求め、これらについてもレイアウト情報と共にレイアウト情報データベース８６に出力する。
【０２９７】
制約条件判定部８２は、実施の形態７において図３４に示した制約条件判定部７２と同様に、選択されたメモリに対応するメモリセルを特定し、更に各メモリセルの遅延時間を算出し、これが遅延制約時間の範囲内にはいるかどうかの判定を行うことができる。
【０２９８】
更に、本実施の形態８においては、制約条件判定部８２は、このような機能に加え、求めた配線混雑度及びデッドスペースの面積のうち少なくとも一方が、予め設定された条件（以下、「レイアウト制約」という。）を満たしているかどうかの判定を行う機能も備えている。
【０２９９】
また、メモリ選択部８１は、実施の形態７において図３４に示したメモリ選択部７１と同様の機能に加え、配線混雑度及びデッドスペースの面積のうち少なくとも一方がレイアウト制約を満たしていないと制約条件判定部８２によって判定された場合に、選択されたメモリ以外のメモリをメモリ候補として再度メモリの選択を行う機能も有している。
【０３００】
次に、図３９を用いて、本実施の形態８における高位合成方法について説明する。本実施の形態８における高位合成方法は、図３８に示した本実施の形態８における高位合成装置８０を動作させることによって実施される。このため、以下においては、適宜図３８を参酌しながら、高位合成装置の動作に基づいて高位合成方法を説明する。図３９は、本発明の実施の形態８における高位合成方法を示すフローチャートである。
【０３０１】
図３８に示すように、先ず、実施の形態７において図３５に示したステップＳ６１〜Ｓ６６と同様に、参照回数の算出（ステップＳ７１）、ビット幅の抽出（ステップＳ７２）、メモリ候補リストの作成（ステップＳ７３）、メモリアクセスのサイクル数の合計の算出（ステップＳ７４）、全てのメモリ候補について算出が終了したかどうかの確認（ステップＳ７５）、サイクル数の最も小さいメモリの選択（ステップＳ７６）が行われる。
【０３０２】
本実施の形態８において、対象となる動作レベル回路１１が、図３６（ａ）に示すものである場合は、実施の形態７と同様に、図３６（ｃ）に示すメモリＭ７２が選択される。
【０３０３】
次に、本実施の形態８においては、実施の形態７と異なり、配置配線部８４によって、動作レベル回路１１に記述された変数を選択されたメモリに割り当てて、配置配線が行われ、更にレイアウト情報が生成される（ステップＳ７７）。ステップＳ７７により、選択されたメモリのアクセス時間、配線混雑度、及びデッドスペースの面積が得られる。
【０３０４】
なお、図３９においては図示していないが、実際には、配置配線を行うためのスケジューリング及びリソースの割り当て（論理回路の合成）が、スケジューリング部８３及びリソース割当部５によって行われており、これによって得られた論理回路に基づいて配置配線が行われている。
【０３０５】
次いで、制約条件判定部８２によって、ステップＳ７７において得られた配線混雑度が及びデッドスペースの面積が、レイアウト制約を満たしているかどうかの判定が行われる（ステップＳ７８）。
【０３０６】
具体的には、ステップＳ７７において得られた配線混雑度が、予め設定された配線混雑度の範囲内にあるかどうか、又ステップＳ７７において得られたデッドスペースの面積が予め設定されたデッドスペースの面積の範囲内にあるかどうかが判定される。なお、本実施の形態８においては、配線混雑度及びデッドスペースの面積の両方について判定が行われているが、いずれか一方についてのみの判定であっても良い。
【０３０７】
判定の結果、レイアウト制約が満たされている場合は、スケジューリング部８３によって、選択されたメモリを割り当ててスケジューリングが行なわれる（ステップＳ７９）。なお、本実施の形態８においては、実施の形態７と異なり、ステップＳ７９におけるスケジューリングは、ステップＳ７７の配置配線によって得られたメモリのアクセス時間を用いて行われている。
【０３０８】
一方、レイアウト制約が満たされていない場合は、再度、メモリ選択部８１によってメモリの選択が行われる（ステップＳ７６）。但し、この場合のステップＳ７６においては、既に選択されたメモリを除いたメモリ候補リストが用いられる。
【０３０９】
その後、ステップＳ７９のスケジューリングが終了すると、制約条件判定部８２によって、図３５に示したステップＳ６８と同様に、選択されたメモリ（メモリＭ７２）に対応するメモリセルの特定が行なわれる（ステップＳ８０）。
【０３１０】
次いで、図３５に示したステップＳ６９と同様に、特定された各メモリセルにおける遅延時間が算出され、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在するかどうかの判定が行われる（ステップＳ８１）。
【０３１１】
但し、本実施の形態８においては、選択されたメモリにおける遅延時間の算出は、ＬＳＩ設計用のライブラリから特定されたメモリセルのアクセス時間に、ステップＳ７７の配置配線によって得られたメモリのアクセス時間を加えて行われている。このため、メモリセルのアクセス時間の算出における精度の向上が図られている。
【０３１２】
判定の結果、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在する場合は、制約条件判定部８２は、メモリアクセス時間が最も短いメモリセルを選択する（ステップＳ８２）。その後、実施の形態１における図２の例と同様に、論理回路の生成が行なわれ（ステップＳ８）、その後処理は終了する。
【０３１３】
一方、判定の結果、算出された遅延時間が遅延制約時間の範囲内にあるメモリセルが存在しない場合は、再度ステップＳ７６が実行される。但し、このステップＳ７６は、最初に選択されたメモリをメモリ候補リストから除外して実行される。
【０３１４】
以上のように、本実施の形態８によれば、配置配線を行い、それから得られるレイアウト情報に基づいてメモリの割り付けを行うことができる。つまり、本実施の形態８によれば、メモリとこれに接続される回路との物理的な配置情報を基にした、精度の高いアクセス時間に関する情報を得ることができ、又配線可能性やレイアウト面積効率を考慮できるため、物理実装に対して最適なメモリの割り付けを行うことが可能となる。
【図面の簡単な説明】
【０３１５】
【図１】本発明の実施の形態１における高位合成装置の概略構成を示すブロック図である。
【図２】本発明の実施の形態１における高位合成方法を示すフローチャートである。
【図３】実施の形態１で用いられる動作レベル回路とメモリアクセスのサイクル数とを示す図であり、図３（ａ）は動作レベル回路の一例を示し、図３（ｂ）は動作レベル回路に記述された変数の参照回数とビット幅とを示し、図３（ｃ）はメモリ候補のビット幅とメモリアクセスのサイクル数の合計とを示している。
【図４】選定されたメモリにおけるメモリアクセスのサイクル数の算出に用いられるメモリアクセスサイクル表を示す図である。
【図５】本発明の実施の形態２における高位合成装置の概略構成を示すブロック図である。
【図６】本発明の実施の形態２における高位合成方法を示すフローチャートである。
【図７】実施の形態２において用いられる動作レベル回路の一例を示す図であり、図７（ａ）は変数分割を行う前の状態を示し、図７（ｂ）は変数分割を行った後の状態を示している。
【図８】変数分割を行った場合と変数分割を行わなかった場合とのサイクル数の合計を示す図であり、図８（ａ）は変数分割を行った場合における変数の参照回数とビット幅とを示し、図８（ｂ）は変数分割を行った場合におけるメモリ候補のビット幅とサイクル数の合計とを示し、図８（ｃ）は変数分割をしなかった場合のメモリ候補のビット幅とサイクル数の合計とを示している。
【図９】仮スケジューリングを行う場合の実施の形態２における高位合成方法を示すフローチャートである。なお、以下の説明においては、適宜図５を参照する。
【図１０】本発明の実施の形態３における高位合成装置の一例の概略構成を示すブロック図である。
【図１１】実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１１（ａ）は変数結合を行う前の状態を示し、図１１（ｂ）は変数結合を行った後の状態を示している。
【図１２】変数統合を行わない場合と変数統合を行った場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅及びサイクル数の合計を示す図であり、図１２（ａ）は変数統合を行わない場合を示し、図１２（ｂ）は変数統合を行った場合を示している。
【図１３】配列変数を配列要素で分割した後の動作レベル回路、変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図１３（ａ）は、図１１（ａ）に示す動作レベル回路を変数分割した後の状態を示しており、図１３（ｂ）は、変数分割を行った場合における変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示している。
【図１４】本発明の実施の形態３における高位合成装置の他の例の概略構成を示すブロック図である。
【図１５】実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１５（ａ）は変数分割及び変数結合を行う前の状態を示し、図１５（ｂ）は変数分割及び変数結合を行った後の状態を示している。
【図１６】変数統合及び変数分割を行った場合と変数統合及び変数分割を行わない場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図１６（ａ）は変数統合及び変数分割を行わない場合を示し、図１６（ｂ）は変数統合及び変数分割を行った場合を示している。
【図１７】本発明の実施の形態３における高位合成装置の他の例の概略構成を示すブロック図である。
【図１８】実施の形態３において用いられる動作レベル回路の一例を示す図であり、図１８（ａ）は変数分割を行う前の状態を示し、図１８（ｂ）は変数分割を行った後の状態を示している。
【図１９】図１７に示す高位合成装置の動作の流れを示すフローチャートである。
【図２０】変数分割を行った場合と変数分割を行わなかった場合とにおける変数のビット幅、参照回数、メモリ候補のビット幅、及びサイクル数の合計を示す図であり、図２０（ａ）は変数分割を行わなかった場合を示し、図２０（ｂ）は変数分割を行った場合を示している。
【図２１】本発明の実施の形態４における高位合成装置の概略構成を示すブロック図である。
【図２２】本発明の実施の形態４における高位合成方法を示すフローチャートである
【図２３】実施の形態４において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図２３（ａ）は動作レベル回路の一例を示し、図２３（ｂ）は図２３（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図２３（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【図２４】仮スケジューリングを行う場合の実施の形態４における高位合成方法を示すフローチャートである。
【図２５】本発明の実施の形態５における高位合成装置の概略構成を示すブロック図である。
【図２６】本発明の実施の形態５における高位合成方法を示すフローチャートである。
【図２７】実施の形態５において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図２７（ａ）は動作レベル回路の一例を示し、図２７（ｂ）は図２７（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図２７（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【図２８】図２７（ａ）に示した動作レベル回路の３番目のｆｏｒ文における実行順序示す図であり、図２８（ａ）は実行順序の入れ替えの前を示し、図２８（ｂ）は実行順序の入れ替えの後を示している。また、図２８においては、３番目のｆｏｒ文はソースコードによって表現されている。
【図２９】図２７（ａ）に示した動作レベル回路をスケジューリングした結果を示す図である。
【図３０】実施の形態５において用いられるメモリアクセスサイクル表を示す図である。
【図３１】本発明の実施の形態６における高位合成装置の概略構成を示すブロック図である。
【図３２】本発明の実施の形態６における高位合成方法を示すフローチャートである。
【図３３】アクセスパターンの一例を示す図であり、図３３（ａ）は同一メモリへの予め設定されたサイクル数以上の連続したアクセスを示すアクセスパターンを示し、図３３（ｂ）は同一サイクルでアクセスされない複数のメモリのアクセス状態を示すアクセスパターンを示している。
【図３４】本発明の実施の形態７における高位合成装置の概略構成を示すブロック図である。
【図３５】本発明の実施の形態７における高位合成方法を示すフローチャートである。
【図３６】実施の形態６において用いられる動作レベル回路、変数のビット幅、及びメモリアクセスのサイクル数を示す図であり、図３６（ａ）は動作レベル回路の一例を示し、図３６（ｂ）は図３６（ａ）に示す動作レベル回路に記述された変数の参照回数とビット幅とを示し、図３６（ｃ）はメモリアクセスのサイクル数の合計をメモリ候補毎に示している。
【図３７】３２ビットのメモリを実装可能な物理メモリセルの一覧を示す図である。
【図３８】本発明の実施の形態８における高位合成装置の概略構成を示すブロック図である。
【図３９】本発明の実施の形態８における高位合成方法を示すフローチャートである。
【符号の説明】
【０３１６】
１    参照回数算出部
２、４２    ビット幅抽出部
３、５２、７１、８１    メモリ選択部
４、５４、８３    スケジューリング部
５    リソース割当部
１０、２０、３０、３３、３６、４０、５０、６０、７０、８０    高位合成装置
１１    動作レベル回路
１２    変数情報データベース
１３    メモリ情報データベース
１４    回路データベース
１５    変数依存情報データベース
２１、３８    変数分割部
２２、３２、３５、３９    修正後動作レベル回路
３１    変数統合部
３４    変数分割統合部
３７、５１    依存解析部
４１    変数グループ設定部
４４    メモリアクセス解析部
４５    表示装置
４６    入力装置
５３    実行順序入替部
５５    変数依存情報データベース
６１ａ〜６１ｃ    先行読み出し処理
６２ａ、６２ｂ    書き込み処理
６３、６４    演算処理
６５    読み出し処理
７２、８２    制約条件判定部
８４    配置配線部
８５    回路接続情報データベース
８６    レイアウト情報データベース
【図１】
2005173648.tif 000003
【図２】
2005173648.tif 000004
【図３】
2005173648.tif 000005
【図４】
2005173648.tif 000006
【図５】
2005173648.tif 000007
【図６】
2005173648.tif 000008
【図７】
2005173648.tif 000009
【図８】
2005173648.tif 000010
【図９】
2005173648.tif 000011
【図１０】
2005173648.tif 000012
【図１１】
2005173648.tif 000013
【図１２】
2005173648.tif 000014
【図１３】
2005173648.tif 000015
【図１４】
2005173648.tif 000016
【図１５】
2005173648.tif 000017
【図１６】
2005173648.tif 000018
【図１７】
2005173648.tif 000019
【図１８】
2005173648.tif 000020
【図１９】
2005173648.tif 000021
【図２０】
2005173648.tif 000022
【図２１】
2005173648.tif 000023
【図２２】
2005173648.tif 000024
【図２３】
2005173648.tif 000025
【図２４】
2005173648.tif 000026
【図２５】
2005173648.tif 000027
【図２６】
2005173648.tif 000028
【図２７】
2005173648.tif 000029
【図２８】
2005173648.tif 000030
【図２９】
2005173648.tif 000031
【図３０】
2005173648.tif 000032
【図３１】
2005173648.tif 000033
【図３２】
2005173648.tif 000034
【図３３】
2005173648.tif 000035
【図３４】
2005173648.tif 000036
【図３５】
2005173648.tif 000037
【図３６】
2005173648.tif 000038
【図３７】
2005173648.tif 000039
【図３８】
2005173648.tif 000040
【図３９】
2005173648.tif 000041