(57)【要約】【課題】  変数配列の統合による高位合成での自由度の減少を抑制し、回路面積が小さく、高速動作が可能な論理回路のＲＴＬ記述を生成する自動高位合成方法及び高位合成プログラムを提供する。【解決手段】  合成制約記憶領域に格納される合成制約条件を読み出し、その合成制約条件に基づいて、高位合成対象の動作記述から、その動作記述に記述された複数の演算の実行の順序を設定したコントロールデータフローグラフを抽出するステップと、コントロールデータフローグラフに基づいて複数の演算を実行する順序を設定するための優先順位を設定するステップと、優先順位を基準として、動作記述に記述された複数の変数配列を統合した変数配列の記憶装置の割り当て及び複数の演算を実行する順序を設定する実行スケジューリングを行うステップとを含む。【選択図】      図１
2005346290.tif 000002
【特許請求の範囲】
【請求項１】
ＣＤＦＧ抽出部が、合成制約記憶領域に格納される合成制約条件を読み出し、該合成制約条件に基づいて、高位合成対象の動作記述から、該動作記述に記述された複数の演算の実行の順序を設定したコントロールデータフローグラフを抽出するステップと、
スケジューリング処理部が、前記コントロールデータフローグラフに基づいて前記複数の演算を実行する順序を設定するための優先順位を設定するステップと、
前記スケジューリング処理部が、前記優先順位を基準として、前記動作記述に記述された複数の変数配列を統合した変数配列の記憶装置の割り当て及び前記複数の演算を実行する順序を設定する実行スケジューリングを行うステップ
とを含むことを特徴とする自動高位合成方法。
【請求項２】
前記優先順位の設定は、前記複数の演算がそれぞれ実行可能なサイクルを抽出して行うことを特徴とする請求項１に記載の自動高位合成方法。
【請求項３】
前記実行スケジューリングは、前記複数の演算のうち１実行サイクル時間内に実行可能な演算を抽出して行うことを特徴とする請求項１又は２に記載の自動高位合成方法。
【請求項４】
アロケーション部が、前記実行スケジューリングの実行結果に基づき、前記動作記述に記述された回路動作を実現する論理回路の演算器及び前記記憶装置の必要数を算出し、前記演算及び前記変数配列を演算器及び記憶装置に割り当てるステップを更に含むことを特徴とする請求項１乃至３のいずれか１項に記載の自動高位合成方法。
【請求項５】
高位合成装置において、
ＣＤＦＧ抽出部に、合成制約記憶領域に格納される合成制約条件を読み出させ、該合成制約条件に基づいて、高位合成対象の動作記述から、該動作記述に記述された複数の演算の実行の順序を設定したコントロールデータフローグラフを抽出させる命令と、
スケジューリング処理部に、前記コントロールデータフローグラフに基づいて前記複数の演算を実行する順序を設定するための優先順位を設定させる命令と、
前記スケジューリング処理部に、前記優先順位を基準として、前記動作記述に記述された複数の変数配列を統合した変数配列の記憶装置の割り当て及び前記複数の演算を実行する順序を設定する実行スケジューリングを行わせる命令
とを実行させるための高位合成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高位合成方法に係り、特に記憶装置を割り当てる自動高位合成方法及び高位合成プログラムに関する。
【背景技術】
【０００２】
ＬＳＩの設計において、ハードウェアを意識せずに回路動作を指定する動作記述に基づき、ハードウェアやクロック同期等を意識したレジスタ転送レベル記述（以下において、「ＲＴＬ記述」という。）を自動的に合成する高位合成技術が実用化されてきている。
【０００３】
高位合成技術では、回路動作を記述した動作記述、及び動作記述に記述された回路動作を実現するハードウェアの種類や個数の制約等を記述した合成制約を高位合成装置に入力する。そして、先ず所望の回路動作を行うために必要な演算の実行やデータ参照の順序を設定したコントロールデータフローグラフ（以下において、「ＣＤＦＧ」という。）を抽出する。その後、抽出したＣＤＦＧに基づいて、使用可能なハードウェアを考慮して、高位合成対象の動作記述に記述された演算にハードウェア及び実行するサイクルの割り当てを設定するスケジューリング（以下において、「実行スケジューリング」という。）を行う。ハードウェアの割り当ての設定において、動作記述中の変数配列は、ＲＡＭ等の記憶装置に割り当てるのが一般的である。この場合は、変数配列への読み出しと書き込みが、記憶装置の読み出しと書き込みとして高位合成される。
【０００４】
しかし、動作記述は、ハードウェアを意識せずに論理回路の機能のアルゴリズムを指定する。そのため、動作記述に記載された変数配列の構成が、割り当てようとする記憶装置の構成と一致しない場合がある。例えば、動作記述では変数配列ａと変数配列ｂの２つの変数配列を使用しているのに対し、回路動作を実現するハードウェアでは１つの記憶装置を使用したい場合は、高位合成前に変数配列ａと変数配列ｂを１つの変数配列に統合した動作記述に変更する必要がある。
【０００５】
このような動作記述を変更する作業を軽減するために、動作記述中の複数の変数配列を自動的に統合する方法が提案されている（例えば、特許文献１参照。）。
【０００６】
変数配列の統合前の動作記述では、変数配列ａと変数配列ｂの読み出し・書き込みの順序を変更して高位合成することができる。しかし、特許文献１で提案された方法では、変数配列の統合前の動作記述では異なる変数配列の変数への読み出し・書き込み動作が、統合後の変数配列では、同じ変数への読み出し・書き込み動作になって、読み出し・書き込みの順序を変更した際に、論理回路が誤動作する可能性が否定できなくなる。したがって、統合後の変数配列の読み出し・書き込みの順序を動作記述に記載された順序に限定して高位合成が行われる。
【０００７】
そのため、高位合成での記憶装置の読み出し・書き込みのスケジューリングの自由度が減少する。その結果、使用するレジスタの増加等が生じて論理回路の面積が増加したり、使用可能なハードウェアの制約によって所望の回路動作を完了するまでの動作ステップ数（以下において、「動作レイテンシ」という。）が大きく動作時間の長い論理回路のＲＴＬ記述が生成される。
【特許文献１】特開平５−１０１１４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、変数配列の統合による高位合成での自由度の減少を抑制し、回路面積が小さく、高速動作が可能な論理回路のＲＴＬ記述を生成する自動高位合成方法及び高位合成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第１の特徴は、（イ）ＣＤＦＧ抽出部が、合成制約記憶領域に格納される合成制約条件を読み出し、その合成制約条件に基づいて、高位合成対象の動作記述から、その動作記述に記述された複数の演算の実行の順序を設定したコントロールデータフローグラフを抽出するステップと、（ロ）スケジューリング処理部が、コントロールデータフローグラフに基づいて複数の演算を実行する順序を設定するための優先順位を設定するステップと、（ハ）スケジューリング処理部が、優先順位を基準として、動作記述に記述された複数の変数配列を統合した変数配列の記憶装置の割り当て、及び複数の演算を実行する順序を設定する実行スケジューリングを行うステップとを含む自動高位合成方法であることを要旨とする。
【００１０】
第２の特徴は、高位合成装置において、（イ）ＣＤＦＧ抽出部に、合成制約記憶領域に格納される合成制約条件を読み出させ、その合成制約条件に基づいて、高位合成対象の動作記述から、その動作記述に記述された複数の演算の実行の順序を設定したコントロールデータフローグラフを抽出させる命令と、（ロ）スケジューリング処理部に、コントロールデータフローグラフに基づいて複数の演算を実行する順序を設定するための優先順位を設定させる命令と、（ハ）スケジューリング処理部に、優先順位を基準として、動作記述に記述された複数の変数配列を統合した変数配列の記憶装置の割り当て、及び複数の演算を実行する順序を設定する実行スケジューリングを行わせる命令とを実行させるための高位合成プログラムであることを要旨とする。
【発明の効果】
【００１１】
本発明によれば、変数配列の統合による高位合成での自由度の減少を抑制し、回路面積が小さく、高速動作が可能な論理回路のＲＴＬ記述を生成する自動高位合成方法及び高位合成プログラムを提供することができる。
【発明を実施するための最良の形態】
【００１２】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。
【００１３】
また、以下に示す実施の形態は、この発明の技術的思想を具体化するための装置や方法を例示するものであって、この発明の技術的思想は、構造、配置等を下記のものに特定するものでない。この発明の技術的思想は、特許請求の範囲において、種々の変更を加えることができる。
【００１４】
図１に示す本発明の実施の形態に係る自動高位合成方法は、例えば図２に示すような高位合成装置によって実行することが可能である。そのため、図２を先に説明する。図２に示す高位合成装置は、処理装置１０、記憶装置２０、入力装置３０及び出力装置４０を備える。更に、処理装置１０は、ＣＤＦＧ抽出部１１、スケジューリング処理部１２、動作記述変更部１３、アロケーション処理部１４、ＲＴＬ作成部１５を備える。
【００１５】
ＣＤＦＧ抽出部１１は、高位合成対象の動作記述からＣＤＦＧを抽出する。スケジューリング処理部１２は、モビリティ抽出部１２０及び実行スケジューリング部１３０を備える。モビリティ抽出部１２０は、動作記述に記述された演算のモビリティを抽出する。「モビリティ」とは、動作記述に記述されたそれぞれの演算について、その演算を実行可能なサイクルの範囲を示すパラメータである。モビリティはＣＤＦＧに基づいて計算できる。モビリティは、実行スケジューリングにおける演算を実行する順序を設定するための優先順位付け等に利用できる。モビリティ抽出部１２０は、ＣＤＦＧに記述された演算について、それぞれの演算を実行するサイクルを割り当てるＣＤＦＧスケジューリングを行うＣＤＦＧスケジューリング部１２１、ＣＤＦＧスケジューリングの結果から動作記述中の演算のモビリティを計算するモビリティ計算部１２２を備える。
【００１６】
実行スケジューリング部１３０は、モビリティ抽出部１２０によって抽出されるモビリティに基づき、実行スケジューリングを行う。実行スケジューリング部１３０は、演算を実行する論理回路のサイクル（以下において、「実行サイクル」という。）を設定するサイクル設定部１３１、動作記述中の演算から実行スケジューリングが可能な演算を抽出する演算抽出部１３２、演算の優先順位を設定する優先順位設定部１３３、演算に演算器及び記憶装置等のハードウェアを割り当てる割り当て処理部１３４、演算の処理時間を計算する演算時間処理部１３５を備える。
【００１７】
又、動作記述変更部１３は、高位合成対象の動作記述に記述された複数の変数配列を統合して、新たに変更動作記述を作成する。アロケーション処理部１４は、実行スケジューリングが行われた実行サイクル、演算及び配列アクセスの状態等を解析して、動作記述に記述された回路動作を実現するために必要な演算器及び記憶装置の必要数を算出し、演算及び変数配列を演算器及び記憶装置に割り当てるアロケーションを実行する。ＲＴＬ作成部１５は、アロケーションの実行結果に基づいて、ＲＴＬ記述を作成する。
【００１８】
記憶装置２０は、動作記述を格納する動作記述記憶領域２０１、合成制約を格納する合成制約記憶領域２０２、ＣＤＦＧを格納するＣＤＦＧ記憶領域２０３、ＣＤＦＧスケジューリングの結果を格納するＣＤＦＧスケジュール記憶領域２０４、演算のモビリティを格納するモビリティ記憶領域２０５、ハードウェアを割り付け可能な演算の情報を格納する候補リスト記憶領域２０６、実行スケジューリング結果が記憶される実行スケジュール記憶領域２０７、実行スケジューリングが可能な演算の情報を格納する抽出リスト記憶領域２０８、変数配列が統合された変更動作記述を格納する変更動作記述記憶領域２０９、アロケーション結果が格納されるアロケーション記憶領域２１０、ＲＴＬ記述が格納されるＲＴＬ記憶領域２１１を備える。
【００１９】
入力装置３０はキーボード、マウス、ライトペン又はフレキシブルディスク装置などで構成される。入力装置３０より高位合成実行者は、入力する動作記述や合成制約を指定したり、設定することができる。又、出力装置４０としては、高位合成結果を表示するディスプレイやプリンタ、或いはコンピュータ読み取り可能な記憶媒体に保存する記録装置等が使用可能である。ここで、「コンピュータ読み取り可能な記憶媒体」とは、例えばコンピュータの外部メモリ装置、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの電子データを記録することができるような媒体などを意味する。具体的には、フレキシブルディスク、ＣＤ−ＲＯＭ，ＭＯディスク、カセットテープ、オープンリールテープなどが「コンピュータ読み取り可能な記憶媒体」に含まれる。
【００２０】
図１に示した高位合成方法を説明する前に、図２に示すＣＤＦＧ抽出部１１が動作記述から抽出するＣＤＦＧに基づき、モビリティ抽出部１２０が動作記述に記述された演算のモビリティを抽出する方法の例を、図３を用いて説明する。以下に、図５に示す合成制約に基づき、図４に示す動作記述のモビリティを抽出する場合について説明する。図５に示す合成制約から、図４に示す動作記述を実現するために使用可能なハードウェアは、２ポートを有するＲＡＭが１個、乗算器が２個、加算器が２個である。又、図４に示す動作記述に記述された変数配列ａ及びｂは、それぞれデータサイズ２５６の変数配列として高位合成が行われる。更に、最大レイテンシは１０である。以下の説明では、動作記述中の変数配列の読み出し及び書き込み等の配列アクセス動作を演算として抽出し、変数配列ａの読み出しを演算「ｍＲ＿ａ」、書き込みを演算「ｍＷ＿ａ」とする。又、変数配列ｂの読み出しを演算「ｍＲ＿ｂ」、書き込みを演算「ｍＷ＿ｂ」とする。
【００２１】
（イ）先ず、図３のステップＳ２１において、図２に示すＣＤＦＧ抽出部１１が、合成制約記憶領域２０２から読み出す配列のデータサイズ、使用可能なメモリの条件に基づいて、図４に示す動作記述から図６に示すＣＤＦＧを抽出する。変数配列ａ及びｂは共にデータサイズ２５６の変数配列であり、使用できるＲＡＭは１個である。そのため、統合後の変数配列への配列アドレス動作として変数が重ならないように、変数ｂ[ｘ]への配列アクセス動作は、変数ｂ[ｘ＋２５６]への配列アクセス動作として動作記述からＣＤＦＧが抽出される（ｘ：１以上、２５６以下の整数。）。抽出されたＣＤＦＧは、図２に示すＣＤＦＧ記憶領域２０３に格納される。
【００２２】
（ロ）次に、ステップＳ２２において、ＣＤＦＧスケジューリング部１２１が、ＣＤＦＧ記憶領域２０３からＣＤＦＧを読み出し、合成制約記憶領域２０２から読み出す合成制約の最大動作レイテンシに基づいて、ＣＤＦＧに記述された演算を実行するサイクルの割り当てを設定するＣＤＦＧスケジューリングを行う。ＣＤＦＧスケジューリングを行う際には、使用可能なハードウェアの制限を考慮しない。ＣＤＦＧスケジューリングを行った例を図７に示す。合成制約の最大動作レイテンシが１０であるため、図７に示すように、サイクル１〜１０において図６に示すＣＤＦＧの演算が実行されるようにＣＤＦＧスケジューリングが実行される。図７に示したアズ・スーン・アズ・ポシブル（ＡＳＡＰ）スケジューリングは、動作レイテンシが最大１０という制約の中で、最も早く図４に示した動作記述に記述された演算を終了させるＣＤＦＧスケジューリングである。例えば、使用する引数の値が確定した演算はできるだけ早いサイクルで実行するようにスケジューリングしている。図７に示すように、ＡＳＡＰスケジューリングでは、動作記述に記述された演算はサイクル１〜５にＣＤＦＧスケジューリングされる。一方、アズ・レイト・アズ・ポシブル（ＡＬＡＰ）スケジューリングは、動作レイテンシが最大１０という制約の中で、最も遅く動作記述に記述された演算を終了させるＣＤＦＧスケジューリングである。即ち、ＡＬＡＰスケジューリングでは、最後の演算がサイクル１０で実行されるようにスケジューリングされ、図７に示すように、動作記述に記述された演算はサイクル７〜１０で回路動作が行われる。作成されたＣＤＦＧスケジューリングの情報は、ＣＤＦＧスケジュール記憶領域２０４に格納される。
【００２３】
（ハ）ステップＳ２３において、モビリティ計算部１２２が、ＣＤＦＧスケジュール記憶領域２０４からＣＤＦＧを読み出す。そして、モビリティ計算部１２２は、ＡＳＡＰスケジューリングで実行されるサイクルとＡＬＡＰスケジューリングで実行されるサイクルの差として、ＣＤＦＧに含まれるそれぞれの演算のモビリティを抽出する。例えば、図４に示す動作記述における行番号０１の演算「Ａ＊Ｂ」は、図７のＡＳＡＰスケジューリングではサイクル１で実行され、ＡＬＡＰスケジューリングではサイクル７で実行される。したがって、演算「Ａ＊Ｂ」のモビリティは６である。図８に、モビリティ計算部１２２によって計算された、図６に示したＣＤＦＧに含まれる演算のモビリティを示す。図８は、それぞれの演算について、演算に使用する引数、ＡＳＡＰスケジューリングによって割り当てられたサイクル、ＡＳＬＰスケジューリングによって割り当てられたサイクル、計算されたモビリティ及び図４に示した動作記述での行番号を示す。又、ＣＤＦＧに含まれる演算の引数として変数配列ａ又は変数配列ｂが使用される場合は、統合後の変数配列ｃとして演算の引数とする。
【００２４】
上述したように、例えば、演算「Ａ＊Ｂ」が、ＡＳＡＰスケジューリングではサイクル１で実行され、ＡＬＡＰスケジューリングではサイクル７で実行されるということは、演算「Ａ＊Ｂ」がサイクル１〜７のいずれかで実行可能であることを示している。即ち、ＡＳＡＰスケジューリングで実行されるサイクルとＡＬＡＰスケジュールで実行されるサイクルの差として定義されるモビリティが大きい演算ほど実行スケジューリングでの自由度が大きい。したがって、モビリティの小さい演算ほど優先順位を高くして実行スケジューリングを行うことにより、全体としての実行スケジューリングでの自由度を大きくできる。
【００２５】
次に、図２に示す高位合成装置を用いて、図１に示す高位合成方法によって高位合成を行う例を説明する。以下の説明では、図４に示す動作記述及び図５に示す合成制約に基づき、動作記述に記述された変数配列ａ及びｂを統合して１つの記憶装置に割り当てる高位合成を行う場合を示す。図５に示す合成制約により、１回の実行サイクルに使用できるハードウェアのリソースの上限は、演算器２個、乗算器２個、２ポートＲＡＭ１個であり、１回の実行サイクルでの読み出し演算及び書き込み演算は最大２回という制約に基づいて実行スケジューリングが行われる。
【００２６】
（イ）先ず、図１のステップＳ１１において、図２に示す入力装置３０を介して、図４に示す高位合成を行う動作記述、及び図５に示す合成制約が入力され、それぞれ動作記述記憶領域２０１、及び合成制約記憶領域２０２に格納される。
【００２７】
（ロ）ステップＳ１２において、ＣＤＦＧ抽出部１１が、動作記述記憶領域２０１から変数配列を統合する前の動作記述を読み出し、読み出した動作記述からＣＤＦＧを抽出する。ＣＤＦＧを抽出する方法は、図３のステップＳ２１で説明した方法等が採用可能であり、合成制約記憶領域２０２から読み出す合成制約に基づいてＣＤＦＧを抽出する。抽出されたＣＤＦＧは、ＣＤＦＧ記憶領域２０３に格納される。
【００２８】
（ハ）次に、ステップＳ１３において、動作記述変更部１３が、動作記述記憶領域２０１に格納された動作記述を読み出し、変数配列ａ及びｂを統合した変数配列ｃを用いた、図９に示すような変更動作記述を作成する。作成された変更動作記述は、変更動作記述記憶領域２０９に格納される。
【００２９】
（ニ）次に、ステップＳ１４において、実行スケジューリング部１３０が、ＣＤＦＧ記憶領域２０３に格納されたＣＤＦＧを読み出す。そして、実行スケジューリング部１３０は、ＣＤＦＧに基づき、合成制約記憶領域２０２から読み出す合成制約に基づいて、実行スケジューリングを行う。実行スケジューリングの方法の詳細は後述する。なお、実行スケジューリング部１３０は、変更動作記述記憶領域２０９から変更動作記述を読み出し、変更動作記述に対応した実行スケジューリングを行う。具体的には、変数配列ａ又は変数配列ｂへの配列アクセス動作は、変数配列ｃへの配列アクセス動作として実行スケジューリングを行う。実行スケジューリング結果は、実行スケジュール記憶領域２０７に格納される。
【００３０】
（ホ）ステップＳ１５において、アロケーション処理部１４が、実行スケジュール記憶領域２０７から実行スケジューリング結果結果を読み出す。そして、アロケーション処理部１４は、実行スケジューリング結果結果に基づき、アロケーションを実行する。抽出されたアロケーション結果は、アロケーション記憶領域２１０に格納される。
【００３１】
（ヘ）ステップＳ１６において、ＲＴＬ作成部１５が、アロケーション記憶領域２１０に格納されたアロケーション結果を読み出す。そして、読み出したアロケーション結果に基づいて、ＲＴＬ記述を作成する。作成されたＲＴＬ記述は、ＲＴＬ記憶領域２１１に格納される。ＲＴＬ記憶領域２１１に格納されたＲＴＬ記述は、出力装置４０を介して高位合成装置の外部に出力することができる。
【００３２】
次に、図１のステップＳ１４における実行スケジューリングを行う方法について説明する。以下に、図１０に示すリスト・スケジューリング・アルゴリズムを用いて実行スケジューリングを行う例を示す。又、ステップＳ１４で説明したように、変数配列ａ又は変数配列ｂへの配列アクセス動作は、変数配列ａと変数配列ｂを統合した変数配列ｃへの配列アクセス動作として実行スケジューリングを行う。変数配列ｃへの配列アクセス動作は、読み出し演算を「ｍＲ＿ｃ」、書き込み演算を「ｍＷ＿ｃ」で示す。
【００３３】
（イ）先ず、図１０に示すステップＳ３０１において、図２に示すサイクル設定部１３１が、演算を割当てる実行サイクルＳを０にセットする。次いで、ステップＳ３０２において、演算抽出部１３２が、ＣＤＦＧ記憶領域２０３に格納されたＣＤＦＧを読み出す。そして、演算抽出部１３２は、ＣＤＦＧに含まれる演算のうちから実行スケジューリングされていない演算があるか判定する。実行スケジューリングされていない演算がある場合は、ステップＳ３０３に進む。すべての演算について実行スケジューリングされている場合は、処理を終了する。
【００３４】
（ロ）ステップＳ３０３において、サイクル設定部１３１が、実行サイクルＳを１つ進める。次いで、ステップＳ３０４において、演算抽出部１３２がＣＤＦＧ記憶領域２０３の情報を読み出し、実行スケジューリングされておらず、且つ使用する引数が確定している演算を抽出する。抽出された演算は、候補リストに追加される。候補リストは、候補リスト記憶領域２０６に格納される。又、演算抽出部１３２は、抽出された演算は実行スケジューリングされているとして、ＣＤＦＧ記憶領域２０３の情報を更新する。
【００３５】
（ハ）次に、ステップＳ３０５において、ＣＤＦＧ記憶領域２０３に格納された演算のモビリティを抽出する。モビリティを抽出する方法は、図３で説明した方法等が採用可能である。抽出したモビリティは、モビリティ記憶領域２０５に格納される。
【００３６】
（ニ）ステップＳ３０６において、優先順位設定部１３３が、モビリティ記憶領域２０５から読み出すモビリティの小さい順に、候補リスト記憶領域２０６に格納された演算を並び替える。並び替えられた順序が、演算の優先順位となる。実行サイクルＳ＝１の場合に、図８に示すモビリティの情報から、優先順位付けされた演算の表の例を図１１に示す。
【００３７】
（ホ）次いで、ステップＳ３０７において、割り当て処理部１３４が、合成制約記憶領域２０２から読み出す合成制約に基づいて、演算の割当てを行っている実行サイクルＳにおいて、候補リスト記憶領域２０６に格納された演算に割り当て可能なハードウェアのリソースがあるかどうか、モビリティが小さい演算から順に判定する。割り当て可能なリソースが無い場合は、ステップＳ３１３に進む。割り当て可能なリソースがある場合は、ステップＳ３０８に進む。
【００３８】
（ヘ）ステップＳ３０８において、割り当て処理部１３４が、ステップＳ３０４においてリソースに割り当て可能と判定した演算ｏｐを候補リスト記憶領域２０６に格納された候補リストから削除する。そして、ステップＳ３０９において、割り当て処理部１３４が、演算ｏｐにリソースを割り当てる。リソースを割り当てられた演算ｏｐの情報は、実行サイクルＳで実行される演算の情報として、実行スケジュール記憶領域２０７に格納される。
【００３９】
（ト）ステップＳ３１０において、演算抽出部１３２が、ＣＤＦＧ記憶領域２０３に格納されたＣＤＦＧを読み出す。そして、演算抽出部１３２は、演算ｏｐの演算結果を引数とするすべての演算ｓｏｐ１、ｓｏｐ２、・・・・・、ｓｏｐｍの情報を、ＣＤＦＧから抽出する（ｍ：正の整数。）。抽出された演算ｓｏｐ１、ｓｏｐ２、・・・・・、ｓｏｐｍの情報は抽出リスト記憶領域２０８に格納される。
【００４０】
（チ）次に、ステップＳ３１１において、演算時間処理部１３５が、実行スケジュール記憶領域２０７から演算ｏｐの情報を読み出し、抽出リスト記憶領域２０８から演算ｓｏｐ１、ｓｏｐ２、・・・・・、ｓｏｐｍの情報を読み出す。そして、演算時間処理部１３５は、演算ｓｏｐ１、ｓｏｐ２、・・・・・、ｓｏｐｍのそれぞれの処理時間Ｔ（ｓｏｐｍ）を計算する。更に演算時間処理部１３５は、演算ｏｐの処理時間Ｔ（ｏｐ）と処理時間Ｔ（ｓｏｐｍ）の和と、実行サイクル時間Ｔｓを比較する。実行サイクル時間Ｔｓは、高位合成対象の動作記述を実現する実際の論理回路の動作クロック等によって決定される実行サイクルＳの実行時間である。処理時間Ｔ（ｏｐ）と処理時間Ｔ（ｓｏｐｍ）の和が実行サイクル時間Ｔｓ以下の場合は、演算の割当てを行っている実行サイクルＳにおいて、演算ｏｐを実行した残りの時間で演算ｓｏｐｍが実行できることを意味する。その場合は、ステップＳ３１２において、演算ｓｏｐｍを候補リスト記憶領域２０６に追加する。
【００４１】
（リ）次に、ステップＳ３１３において、候補リスト記憶領域２０６に演算が残っているかを判定する。演算が残っている場合は、ステップＳ３０７に戻る。演算が残っていない場合は、ステップＳ３０２に戻る。
【００４２】
以上に説明した方法によって、実行スケジュール記憶領域２０７に格納された実行サイクルＳ＝１の実行スケジューリング結果を図１２に示す。図１１に示した優先順位３の演算「Ｃ＊Ｄ」と、その演算結果を引数とする優先順位４の演算「（Ｃ＊Ｄ）＋５」が実行サイクル時間Ｔｓにおいて連続して実行可能であるため、実行サイクルＳ＝１に演算「Ｃ＊Ｄ」と演算「（Ｃ＊Ｄ）＋５」が割り当てられている。又、優先順位１〜４である演算にハードウェアを割り付けた時点で、乗算器２個、加算器２個を使用しているため、図１１で優先順位５、６である演算「２５６＋Ｊ」、「２５６＋ｓ」は、利用可能なハードウェアのリソースが無く、実行サイクルＳ＝２以降に持ち越しになる。
【００４３】
以上に説明した実行スケジューリング方法では、ステップＳ３０４〜Ｓ３０６において、実行スケジューリングされていない演算のモビリティを再計算し、実行サイクルＳ＝２以降の優先順位付けを行う。実行サイクルＳ＝２における実行スケジューリングの対象となる演算のモビリティの表及び優先順位表の例を図１３及び図１４にそれぞれ示す。図１３に示すモビリティの表では、既に実行スケジューリングされた演算の部分をグレイ表示し、実行サイクルＳ＝２における実行スケジューリングの対象となる演算を太枠で示している。以下のモビリティの表においても同様である。
【００４４】
図１４に示した優先順位表に基づいて実行スケジューリングされた実行サイクルＳ＝２の結果を追加した、実行サイクルＳ＝１〜２における実行スケジューリング結果の例を図１５に示す。
【００４５】
図１６及び図１７は、実行サイクルＳ＝３に割り付けされる演算のモビリティの表及び優先順位表の例を示す。図１８は、図１７に示した優先順位表に基づいて実行スケジューリングされた実行サイクルＳ＝３の結果を追加した、実行サイクルＳ＝１〜３の実行スケジューリング結果の例を示す。
【００４６】
上記の説明と同様にして実行サイクルＳ＝４以降の実行スケジューリングを行った結果の例を図１９に示す。
【００４７】
図１９に示した実行スケジューリング結果に基づき、アロケーションを行った結果の例を図２０に示す。アロケーション結果は、図５に示した合成制約の２ポートＲＡＭが１個、乗算器及び加算器が各２個という制約を満足し、最大レイテンシが１０という制約に対し、実行サイクル数、即ち動作レイテンシは４である。
【００４８】
図２１に、以上に説明した方法によって作成されたＲＴＬ記述に基づき、合成された論理回路のブロック図の例を示す。第１の乗算器６１、第２の乗算器６２、第１の加算器７１、第２の加算器７２、及び第１ポートと第２ポートを有する１つのＲＡＭ８０によって論理回路が構成されている。
【００４９】
図２２及び図２３に、図４に示す動作記述及び図５に示す合成制約に基づき、変数配列を統合した図９に示す動作記述を作成した後に、図９に示す動作記述からＣＤＦＧを抽出し、高位合成を行ったスケジューリング結果及びアロケーション結果を示す。図２３に示すように、アロケーション結果は、２ポートＲＡＭが１個、乗算器及び加算器が各２個、動作レイテンシは６である。図２０に示した、同一の動作記述、合成制約から図１に示す高位合成方法を使用して高位合成を行ったアロケーション結果と比較して、図２３に示すアロケーション結果の動作レイテンシは大きい。
【００５０】
本発明の実施の形態に係る高位合成方法によれば、変数配列が統合される前の動作記述からＣＤＦＧを抽出して、演算及び配列アクセスのモビリティが抽出される。したがって、ＣＤＦＧを抽出する段階では変数配列が区別されている。そのため、変数配列が統合された後の動作記述に記述された順序に限定されずに、配列アクセスの順序を入れ替えること等が可能であり、実行スケジューリングの自由度が大きい。その結果、動作レイテンシの小さな回路のＲＴＬ記述を生成することができ、高速動作が可能な論理回路を実現することができる。
【００５１】
図１に示した一連の高位合成方法は、図１と等価なアルゴリズムのプログラムにより、図２に示した高位合成装置を制御して実行できる。このプログラムは、図２に示した高位合成装置を構成する記憶装置２０に記憶させればよい。また、このプログラムは、コンピュータ読取り可能な記憶媒体に保存し、この記憶媒体を図２に示した記憶装置２０に読み込ませることにより、本発明の一連の高位合成操作を実行することができる。
【００５２】
＜変形例＞
図１に示す高位合成方法により、図４に示す動作記述及び図２４に示す合成制約に基づき、実行スケジューリングを行った結果の例を図２５に示す。図２４に示す合成制約は、使用できる乗算器及び加算器が各１個である点が、図５に示した合成制約と異なる。更に、図２５に示す実行スケジューリング結果に基づき、アロケーションを行った結果の例を図２６に示す。２ポートＲＡＭが１個、乗算器及び加算器が各１個という制約を満足し、最大レイテンシは５である。
【００５３】
図２２に示した、変数配列を統合した後の動作記述からＣＤＦＧを抽出する高位合成方法によって作成されたアロケーション結果と比べて、乗算器及び加算器の数がそれぞれ１個少なく、且つ動作レイテンシが５に改善されている。
【００５４】
図２７に、図４に示す動作記述及び図２４に示す合成制約に基づき、図１に示した自動高位合成方法によって合成された論理回路のブロック図の例を示す。乗算器６１、加算器７１、及び第１ポートと第２ポートを有する１つのＲＡＭ８０によって論理回路が構成されている。
【００５５】
以上に説明したように、本発明の実施の形態の変形例に係る高位合成方法によれば、使用するハードウェアの少ない回路のＲＴＬ記述を生成することができる。その結果、面積が小さく、消費電力が小さな回路を実現することができる。
【００５６】
（その他の実施の形態）
上記のように、本発明は実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。
【００５７】
既に述べた実施の形態の説明においては、２つの変数配列を１つの変数配列に統合する例を示したが、３つ以上の変数配列を１つの変数配列に統合する場合にも本発明を適用することができる。
【００５８】
このように、本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。したがって、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【００５９】
【図１】本発明の実施の形態に係る高位合成方法を説明するフローチャートである。
【図２】本発明の実施の形態に係る高位合成方法を実行する高位合成装置の構成を示す模式的な回路構成図である。
【図３】本発明の実施の形態に係る高位合成方法におけるモビリティを計算する方法を説明するフローチャートである。
【図４】本発明の実施の形態に係る高位合成方法が適用される動作記述の例である。
【図５】本発明の実施の形態に係る高位合成方法を行う場合の合成制約の例である。
【図６】本発明の実施の形態に係る高位合成方法によって、図４に示す動作記述から抽出されるＣＤＦＧの例である。
【図７】本発明の実施の形態に係る高位合成方法によって、図６に示すＣＤＦＧについてＣＤＦＧスケジューリングを行った例である。
【図８】本発明の実施の形態に係る高位合成方法によって、モビリティを計算した例である（その１）。
【図９】本発明の実施の形態に係る高位合成方法において、変数配列の統合を行った後の動作記述の例である。
【図１０】本発明の実施の形態に係る高位合成方法における実行スケジューリング方法を説明するフローチャートである。
【図１１】本発明の実施の形態に係る高位合成方法によって、演算の優先順位付けを行った表である（その１）。
【図１２】本発明の実施の形態に係る高位合成方法による実行スケジューリング結果である（その１）。
【図１３】本発明の実施の形態に係る高位合成方法によって、モビリティを計算した例である（その２）。
【図１４】本発明の実施の形態に係る高位合成方法によって、演算の優先順位付けを行った表である（その２）。
【図１５】本発明の実施の形態に係る高位合成方法による実行スケジューリング結果である（その２）。
【図１６】本発明の実施の形態に係る高位合成方法によって、モビリティを計算した例である（その３）。
【図１７】本発明の実施の形態に係る高位合成方法によって、演算の優先順位付けを行った表である（その３）。
【図１８】本発明の実施の形態に係る高位合成方法による実行スケジューリング結果である（その３）。
【図１９】本発明の実施の形態に係る高位合成方法による実行スケジューリング結果である（その４）。
【図２０】本発明の実施の形態に係る高位合成方法によるアロケーション結果の例を示す表である。
【図２１】本発明の実施の形態に係る高位合成方法によって合成される論理回路のブロック図の例である。
【図２２】変数配列の統合を行った後に、高位合成を行った実行スケジューリング結果の例である。
【図２３】変数配列の統合を行った後に、高位合成を行ったアロケーション結果を示す表である。
【図２４】本発明の実施の形態に係る高位合成方法を行う場合の他の合成制約の例である。
【図２５】本発明の実施の形態に係る高位合成方法による他の実行スケジューリング結果の例である。
【図２６】本発明の実施の形態に係る高位合成方法による他のアロケーション結果の例を示す表である。
【図２７】本発明の実施の形態に係る高位合成方法によって合成される他の論理回路のブロック図の例である。
【符号の説明】
【００６０】
１１…ＣＤＦＧ抽出部
１２…スケジューリング処理部
１４…アロケーション処理部
２０３…ＣＤＦＧ記憶領域
２０７…実行スケジュール記憶領域
２１０…アロケーション記憶領域
【図１】
2005346290.tif 000003
【図２】
2005346290.tif 000004
【図３】
2005346290.tif 000005
【図４】
2005346290.tif 000006
【図５】
2005346290.tif 000007
【図６】
2005346290.tif 000008
【図７】
2005346290.tif 000009
【図８】
2005346290.tif 000010
【図９】
2005346290.tif 000011
【図１０】
2005346290.tif 000012
【図１１】
2005346290.tif 000013
【図１２】
2005346290.tif 000014
【図１３】
2005346290.tif 000015
【図１４】
2005346290.tif 000016
【図１５】
2005346290.tif 000017
【図１６】
2005346290.tif 000018
【図１７】
2005346290.tif 000019
【図１８】
2005346290.tif 000020
【図１９】
2005346290.tif 000021
【図２０】
2005346290.tif 000022
【図２１】
2005346290.tif 000023
【図２２】
2005346290.tif 000024
【図２３】
2005346290.tif 000025
【図２４】
2005346290.tif 000026
【図２５】
2005346290.tif 000027
【図２６】
2005346290.tif 000028
【図２７】
2005346290.tif 000029