(57)【特許請求の範囲】
【請求項１】
ＣＤＦＧ生成処理部とＣＤＦＧスケジューリング処理部とアロケーション処理部とクロックスケジューリング処理部を有する設計装置によって、動作レベル記述回路からレジスタトランスファレベル記述回路を自動的に生成する回路合成方法であって、
動作レベル記述回路からレジスタトランスファレベル記述回路を合成する際に、各レジスタへのクロックタイミングを同時に合成する高位合成方法において、
前記ＣＤＦＧ生成処理部が、前記動作レベル記述回路をコントロールデータフローグラフに変換するＣＤＦＧ生成工程と、
前記ＣＤＦＧスケジューリング処理部が、与えられたクロックサイクル数においてレジスタ数が最小になるように前記コントロールデータフローグラフをスケジューリングするＣＤＦＧスケジューリング工程と、
前記アロケーション処理部が、前記ＣＤＦＧスケジューリング工程によってスケジューリングされたコントロールデータフローグラフに対してハードウエアを割り当てるアロケーション工程と、
前記クロックスケジューリング処理部が、前記アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングを、クロック周期が小さくなるように、クロックタイミングの調整対象である前記レジスタ間の最小遅延および最大遅延に基づいて調整するクロックスケジューリング工程と、
前記クロックスケジューリング処理部が、前記クロックスケジューリング工程によって得られたクロック周期が所望のクロック周期よりも大きいとき、前記アロケーション工程によってハードウエアが割り当てられたコントロールデータフローグラフに対するレジスタの割り当てを変更するリタイミング工程とを備え、
前記クロックスケジューリング工程によって得られたクロック周期が前記所望のクロック周期よりも小さいときは処理を終了し、
前記リタイミング工程の結果  クロック周期が改善されたとき、前記クロックスケジューリング工程に戻る
ことを特徴とする高位合成方法。
【請求項２】
請求項１に記載の高位合成方法において、
前記クロックスケジューリング工程では、
前記アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングを調整可能幅の範囲内で調整し、
前記高位合成方法は、
前記クロックスケジューリング処理部が、前記リタイミング工程の結果  クロック周期が改善されなかったとき、前記調整可能幅を広げる拡大工程をさらに備え、
前記拡大工程によって得られた調整可能幅が所定のしきい値よりも大きいときは処理を終了し、小さいときは前記ＣＤＦＧスケジューリング工程に戻る
ことを特徴とする高位合成方法。
【請求項３】
請求項１または請求項２に記載の高位合成方法において、
前記クロックスケジューリング工程では、
請求項１または２に記載のクロックスケジューリング工程における処理に代えて、
前記アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングをクロックタイミングの調整対象である前記レジスタ間の最小遅延および最大遅延に基づいて調整することによってクロック周期を削減した場合のクロック消費電力を推定し、削減したクロック周期と推定したクロック消費電力との積（クロックＰＤ積）を計算するクロックＰＤ積推定工程と、
前記アロケーション工程によって割り当てられたハードウエアをより高速なハードウエアに変更することによってクロック周期を削減した場合の回路消費電力を推定し、削減したクロック周期と推定した回路消費電力との積（回路ＰＤ積）を計算する回路ＰＤ積推定工程と、
前記クロックＰＤ積推定工程と前記回路ＰＤ積推定工程とのうち得られるＰＤ積が小さいほうの工程におけるクロック周期削減手段を実行する選択的クロック周期改善工程とを行う
ことを特徴とする高位合成方法。
【請求項４】
請求項３に記載の高位合成方法において、
前記クロックＰＤ積推定工程および前記回路ＰＤ積推定工程では、クロック周期の改善率を限界値より少なく押さえた場合で消費電力を推定し、
前記クロックＰＤ積推定工程と前記回路ＰＤ積推定工程と前記選択的クロック周期改善工程とをクロック周期が改善できなくなるまで繰り返し実行する
ことを特徴とする高位合成方法。
【請求項５】
請求項３または請求項４に記載の高位合成方法において、
前記回路ＰＤ積推定工程では、ハードウエアの１クロック周期内に動作する確率に基づいて前記回路消費電力を推定する
ことを特徴とする高位合成方法。
【請求項６】
請求項３または請求項４に記載の高位合成方法において、
前記クロックＰＤ積推定工程では、前記調整可能幅に対して単調増加する関数に基づいて前記クロック消費電力を推定する
ことを特徴とする高位合成方法。
【請求項７】
動作レベル記述回路からレジスタトランスファレベル記述回路を自動的に生成する高位合成装置であって、
前記高位合成装置は、
動作レベル記述回路からレジスタトランスファレベル記述回路を合成する際に、各レジスタへのクロックタイミングを同時に合成するものであり、
前記高位合成装置は、
前記動作レベル記述回路をコントロールデータフローグラフに変換するＣＤＦＧ生成手段と、
与えられたクロックサイクル数においてレジスタ数が最小になるように前記コントロールデータフローグラフをスケジューリングするＣＤＦＧスケジューリング手段と、
前記ＣＤＦＧスケジューリング手段によってスケジューリングされたコントロールデータフローグラフに対してハードウエアを割り当てるアロケーション手段と、
前記アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングを、クロック周期が小さくなるように、クロックタイミングの調整対象である前記レジスタ間の最小遅延および最大遅延に基づいて調整するクロックスケジューリング手段と、
前記クロックスケジューリング手段によって得られたクロック周期が所望のクロック周期よりも大きいとき、前記アロケーション手段によってハードウエアが割り当てられたコントロールデータフローグラフに対するレジスタの割り当てを変更するリタイミング手段とを備え、
前記高位合成装置は、
前記クロックスケジューリング手段によって得られたクロック周期が前記所望のクロック周期よりも小さいときは処理を終了し、
前記リタイミング手段による処理の結果  クロック周期が改善されたとき、前記クロックスケジューリング手段による処理に戻る
ことを特徴とする高位合成装置。
【請求項８】
請求項７に記載の高位合成装置において、
前記クロックスケジューリング手段は、
前記アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングを調整可能幅の範囲内で調整し、
前記高位合成装置は、
前記リタイミング手段による処理の結果  クロック周期が改善されなかったとき、前記調整可能幅を広げる拡大手段をさらに備え、
前記拡大手段によって得られた調整可能幅が所定のしきい値よりも大きいときは処理を終了し、小さいときは前記ＣＤＦＧスケジューリング手段による処理に戻る
ことを特徴とする高位合成装置。
【請求項９】
請求項７または請求項８に記載の高位合成装置において、
前記クロックスケジューリング手段に代えて、
前記アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングをクロックタイミングの調整対象である前記レジスタ間の最小遅延および最大遅延に基づいて調整することによってクロック周期を削減した場合のクロック消費電力を推定し、削減したクロック周期と推定したクロック消費電力との積（クロックＰＤ積）を計算するクロックＰＤ積推定手段と、
前記アロケーション手段によって割り当てられたハードウエアをより高速なハードウエアに変更することによってクロック周期を削減した場合の回路消費電力を推定し、削減したクロック周期と推定した回路消費電力との積（回路ＰＤ積）を計算する回路ＰＤ積推定手段と、
前記クロックＰＤ積推定手段と前記回路ＰＤ積推定手段とのうち得られるＰＤ積が小さいほうにおけるクロック周期削減手段を実行する選択的クロック周期改善手段とを備える
ことを特徴とする高位合成装置。
【請求項１０】
請求項９に記載の高位合成装置において、
前記クロックＰＤ積推定手段および前記回路ＰＤ積推定手段は、クロック周期の改善率を限界値より少なく押さえた場合で消費電力を推定し、
前記高位合成装置は、
前記クロックＰＤ積推定手段における処理と前記回路ＰＤ積推定手段における処理と前記選択的クロック周期改善手段における処理とをクロック周期が改善できなくなるまで繰り返し実行する
ことを特徴とする高位合成装置。
【請求項１１】
請求項９または請求項１０に記載の高位合成装置において、
前記回路ＰＤ積推定手段は、ハードウエアの１クロック周期内に動作する確率に基づいて前記回路消費電力を推定する
ことを特徴とする高位合成装置。
【請求項１２】
請求項９または請求項１０に記載の高位合成装置において、
前記クロックＰＤ積推定手段は、前記調整可能幅に対して単調増加する関数に基づいて前記クロック消費電力を推定する
ことを特徴とする高位合成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、動作レベルで記述された回路仕様からレジスタトランスファレベル（ＲＴＬ）の回路記述に自動的に合成する高位合成方法および高位合成装置に関する。
【０００２】
【従来の技術】
近年のＬＳＩ回路の大規模化・製品サイクルの短期化に伴いＬＳＩ設計の生産性向上が非常に重要になってきている。動作レベルで記述された回路仕様からレジスタトランスファレベル（ＲＴＬ）の回路記述に自動的に合成する高位合成技術は生産性向上に有効な手段であることが知られている。
【０００３】
今後ますます市場拡大が予想される携帯電話などのモバイル機器にとってはＬＳＩの消費電力は重要な要素であり高位合成技術でも考慮されるべきである。高位合成技術では、より少ないレジスタ数でＲＴＬ回路を実現することで低消費電力化を実現している。たとえば、レジスタ共用化によるレジスタ数の削減方法として、Ｄａｎｉｅｌ  Ｇａｊｓｋｉ，Ｎｉｋｉｌ  Ｄｕｔｔ，Ａｌｌｅｎ  Ｗｕ，Ｓｔｅｖｅ  Ｌｉｎ，”ＨＩＧＨ−ＬＥＶＥＬ  ＳＹＮＴＨＥＳＩＳ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ”，Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ，１９９２や特許第３１５０１２２号公報などが提案されている。
【０００４】
【発明が解決しようとする課題】
文献（Ａ．Ｔａｋａｈａｓｈｉ，Ｙ．Ｋａｊｉｔａ，”Ｐｅｒｆｏｒｍａｎｃｅ  ａｎｄ  Ｒｅｌｉａｂｉｌｉｔｙ  Ｄｒｉｖｅｎ  Ｃｌｏｃｋ  Ｓｃｈｅｄｕｌｉｎｇ  ｏｆ  Ｓｅｑｕｅｎｔｉａｌ  Ｌｏｇｉｃ  Ｃｉｒｃｕｉｔｓ”，Ｐｒｏｃ．  Ａｓｉａ  ａｎｄ  Ｓｏｕｔｈ  Ｐａｃｉｆｉｃ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ．３７−４２，１９９７）では、各レジスタへのクロックタイミング（クロックソースからレジスタまでの伝播遅延）を調整することによって、ゼロスキュー設計（すべてのレジスタへのクロックタイミングが同値）の場合と比較して動作周波数を１０％から２０％向上できることが報告されている（準同期設計）。
【０００５】
ところが従来の高位合成技術では、すべてのレジスタへのクロックタイミングが同値であることを前提としている（ゼロスキュー設計）。したがって、たとえば要求された動作周波数を満たす最低のパイプライン段数が、ゼロスキュー設計によれば３段必要な場合でも準同期設計によれば２段ですむ場合もありうる。
【０００６】
なお、高位合成技術の一機能であるレジスタ位置変更（リタイミング）時にクロックタイミングを調整する手法が文献（Ｘｕｎ  Ｌｉｕ，Ｍａｒｏｉｓ  Ｃ．Ｐａｐａｅｆｔｈｙｍｉｏｕ，Ｅｄｙ  Ｇ．Ｆｒｉｅｄｍａｎ，”Ｍａｘｉｍｉｚｉｎｇ  Ｐｅｒｆｏｒｍａｎｃｅ  ｂｙ  Ｒｅｔｉｍｉｎｇ  ａｎｄ  Ｃｌｏｃｋ  Ｓｋｅｗ  Ｓｃｈｅｄｕｌｉｎｇ，”Ｐｒｏｃ．Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆ．，１９９９）において提案されているが消費電力削減を目的としてないために低消費電力化は実現できない。
【０００７】
この発明は上記のような問題を解決するためになされたものであり、その目的は、低消費電力化を実現することができる高位合成方法および高位合成装置を提供することである。
【０００８】
【課題を解決するための手段】
この発明による高位合成方法は、動作レベル記述回路からレジスタトランスファレベル記述回路を自動的に生成する回路合成方法であって、動作レベル記述回路からレジスタトランスファレベル記述回路を合成する際に、各レジスタへのクロックタイミングを同時に合成する。
【０００９】
好ましくは、上記高位合成方法は、ＣＤＦＧ生成工程と、ＣＤＦＧスケジューリング工程と、アロケーション工程と、クロックスケジューリング工程と、リタイミング工程とを備える。ＣＤＦＧ生成工程では、動作レベル記述回路をコントロールデータフローグラフに変換する。ＣＤＦＧスケジューリング工程では、与えられたクロックサイクル数においてレジスタ数が最小になるように上記コントロールデータフローグラフをスケジューリングする。アロケーション工程では、ＣＤＦＧスケジューリング工程によってスケジューリングされたコントロールデータフローグラフに対してハードウエアを割り当てる。クロックスケジューリング工程では、アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングをクロック周期が小さくなるように調整する。クロックスケジューリング工程によって得られたクロック周期が所望のクロック周期よりも小さいときは処理を終了する。リタイミング工程では、クロックスケジューリング工程によって得られたクロック周期が所望のクロック周期よりも大きいとき、アロケーション工程によってハードウエアが割り当てられたコントロールデータフローグラフに対するレジスタの割り当てを変更する。リタイミング工程の結果
クロック周期が改善されたときは、クロックスケジューリング工程に戻る。
【００１０】
上記高位合成方法では、クロック周期削減のためにクロックタイミング調整技術を利用しながら、ＣＤＦＧスケジューリングをレジスタ数が最小である状態からレジスタ数が増える方向へ探索することになるため、クロックタイミングを調整しない場合と比べて少ないレジスタ数で所望のクロック周期を実現するハードウエアを実現できる。これにより低消費電力化が実現される。
【００１１】
好ましくは、上記クロックスケジューリング工程では、アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングを調整可能幅の範囲内で調整する。そして上記高位合成方法は、拡大工程をさらに備える。拡大工程では、リタイミング工程の結果  クロック周期が改善されなかったとき、調整可能幅を広げる。拡大工程によって得られた調整可能幅が所定のしきい値よりも大きいときは処理を終了し、小さいときはＣＤＦＧスケジューリング工程に戻る。
【００１２】
好ましくは、上記クロックスケジューリング工程は、クロックＰＤ積推定工程と、回路ＰＤ積推定工程と、選択的クロック周期改善工程とを含む。クロックＰＤ積推定工程では、アロケーション工程によって割り当てられたレジスタの各々に対するクロックタイミングを調整することによってクロック周期を削減した場合のクロック消費電力を推定し、削減したクロック周期と推定したクロック消費電力との積（クロックＰＤ積）を計算する。回路ＰＤ積推定工程では、アロケーション工程によって割り当てられたハードウエアをより高速なハードウエアに変更することによってクロック周期を削減した場合の回路消費電力を推定し、削減したクロック周期と推定した回路消費電力との積（回路ＰＤ積）を計算する。選択的クロック周期改善工程では、クロックＰＤ積推定工程と回路ＰＤ積推定工程とのうち得られるＰＤ積が小さいほうの工程におけるクロック周期削減手段を実行する。
【００１３】
好ましくは、上記クロックＰＤ積推定工程および回路ＰＤ積推定工程では、クロック周期の改善率を限界値より少なく押さえた場合で消費電力を推定する。そして上記高位合成方法は、クロックＰＤ積推定工程と回路ＰＤ積推定工程と選択的クロック周期改善工程とをクロック周期が改善できなくなるまで繰り返し実行する。
【００１４】
好ましくは、上記回路ＰＤ積推定工程では、ハードウエアの１クロック周期内に動作する確率に基づいて回路消費電力を推定する。
【００１５】
好ましくは、上記クロックＰＤ積推定工程は、調整可能幅に対して単調増加する関数に基づいてクロック消費電力を推定する。
【００１６】
この発明による高位合成装置は、動作レベル記述回路からレジスタトランスファレベル記述回路を自動的に生成するものであって、動作レベル記述回路からレジスタトランスファレベル記述回路を合成する際に、各レジスタへのクロックタイミングを同時に合成する。
【００１７】
好ましくは、上記高位合成装置は、ＣＤＦＧ生成手段と、ＣＤＦＧスケジューリング手段と、アロケーション手段と、クロックスケジューリング手段と、リタイミング手段とを備える。ＣＤＦＧ生成手段は、動作レベル記述回路をコントロールデータフローグラフに変換する。ＣＤＦＧスケジューリング手段は、与えられたクロックサイクル数においてレジスタ数が最小になるように上記コントロールデータフローグラフをスケジューリングする。アロケーション手段は、ＣＤＦＧスケジューリング手段によってスケジューリングされたコントロールデータフローグラフに対してハードウエアを割り当てる。クロックスケジューリング手段は、アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングをクロック周期が小さくなるように調整する。クロックスケジューリング手段によって得られたクロック周期が所望のクロック周期よりも小さいとき、上記高位合成装置は処理を終了する。リタイミング手段は、クロックスケジューリング手段によって得られたクロック周期が所望のクロック周期よりも大きいとき、アロケーション手段によってハードウエアが割り当てられたコントロールデータフローグラフに対するレジスタの割り当てを変更する。リタイミング手段による処理の結果  クロック周期が改善されたとき、クロックスケジューリング手段による処理に戻る。
【００１８】
好ましくは、上記クロックスケジューリング手段は、アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングを調整可能幅の範囲内で調整する。そして上記高位合成装置は、拡大手段をさらに備える。拡大手段は、リタイミング手段による処理の結果  クロック周期が改善されなかったとき、調整可能幅を広げる。上記高位合成装置は、拡大手段によって得られた調整可能幅が所定のしきい値よりも大きいときは処理を終了し、小さいときはＣＤＦＧスケジューリング手段による処理に戻る。
【００１９】
好ましくは、上記クロックスケジューリング手段は、クロックＰＤ積推定手段と、回路ＰＤ積推定手段と、選択的クロック周期改善手段とを含む。クロックＰＤ積推定手段は、アロケーション手段によって割り当てられたレジスタの各々に対するクロックタイミングを調整することによってクロック周期を削減した場合のクロック消費電力を推定し、削減したクロック周期と推定したクロック消費電力との積（クロックＰＤ積）を計算する。回路ＰＤ積推定手段は、アロケーション手段によって割り当てられたハードウエアをより高速なハードウエアに変更することによってクロック周期を削減した場合の回路消費電力を推定し、削減したクロック周期と推定した回路消費電力との積（回路ＰＤ積）を計算する。選択的クロック周期改善手段は、クロックＰＤ積推定手段と回路ＰＤ積推定手段とのうち得られるＰＤ積が小さいほうにおけるクロック周期削減手段を実行する。
【００２０】
好ましくは、上記クロックＰＤ積推定手段および回路ＰＤ積推定手段は、クロック周期の改善率を限界値より少なく押さえた場合で消費電力を推定する。上記高位合成装置は、クロックＰＤ積推定手段における処理と回路ＰＤ積推定手段における処理と選択的クロック周期改善手段における処理とをクロック周期が改善できなくなるまで繰り返し実行する。
【００２１】
好ましくは、上記回路ＰＤ積推定手段は、ハードウエアの１クロック周期内に動作する確率に基づいて回路消費電力を推定する。
【００２２】
好ましくは、上記クロックＰＤ積推定手段は、調整可能幅に対して単調増加する関数に基づいて前記クロック消費電力を推定する。
【００２３】
【発明の実施の形態】
以下、この発明の実施の形態を図面を参照して詳しく説明する。なお、図中同一または相当部分には同一の符号を付しその説明は繰り返さない。
【００２４】
（第１の実施形態）
図１は、この発明の第１の実施形態による高位合成方法の処理の手順を示すフローチャートである。以下、図１を参照しながら説明する。
【００２５】
まずステップＳＴ１１（ＣＤＦＧ生成工程）において、処理の動作のみを記述した動作記述を解析し、その動作記述を、演算間の実行順序の依存関係を表現するコントロールデータフローグラフ（ＣＤＦＧ）と呼ばれるデータ構造に変換する。ＣＤＦＧの一例を図２に示す。図２は、以下に示す（式１）をＣＤＦＧで表現したものである。
Ｘ＝ａ×ｂ×ｃ×ｄ＋ｅ×ｆ×ｇ×ｈ−ｉ／ｊ／ｋ／ｌ・・・（式１）
図２に示すように、ＣＤＦＧは、演算（２０１−２１１）とそれらの間の信号の流れを示す枝とで構成される。
【００２６】
次にステップＳＴ１２（ＣＤＦＧスケジューリング工程）において、所望のクロックサイクル数でかつレジスタ数が最小になるようにスケジューリングを実施する。たとえば、所望のクロックサイクル数を２として図２に示したＣＤＦＧをスケジューリングすると、図３（ａ），（ｂ）に示すような場合が考えられる。図３において線がクロスしている箇所（データの流れを示す枝とクロックサイクル境界を示す波線との交点）にレジスタが挿入されるので、図３（ｂ）のほうがより少ないレジスタ数でハードウエアを実現できることになる。したがってこの場合には図３（ｂ）に示すようにスケジューリングが実施される。
【００２７】
次にステップＳＴ１３（アロケーション工程）において、ＣＤＦＧの演算に演算器を、データの流れを示す枝とクロックサイクル境界線との交点にレジスタ（４１３，４１４）を、入出力境界に入出力ピン（４０１−４１２，４１５）をそれぞれ割り当ててハードウエアを生成する。図３（ｂ）に示したスケジューリング結果に対してハードウエアを割り当てた状態を図４に示す。なお、図４中の演算に隣接した数字は、割り付けられた演算器の動作速度を示す。
【００２８】
次にステップＳＴ１４（クロックスケジューリング工程）において、生成されたハードウエアに対して、レジスタへのクロックタイミングを調整した場合の最小クロック周期（準同期最小クロック周期）を求める。準同期最小クロック周期は、文献（Ａ．Ｔａｋａｈａｓｈｉ，Ｙ．Ｋａｊｉｔａ，”Ｐｅｒｆｏｒｍａｎｃｅ  ａｎｄ  Ｒｅｌｉａｂｉｌｉｔｙ  Ｄｒｉｖｅｎ  Ｃｌｏｃｋ  Ｓｃｈｅｄｕｌｉｎｇ  ｏｆ  Ｓｅｑｕｅｎｔｉａｌ  Ｌｏｇｉｃ  Ｃｉｒｃｕｉｔｓ”，Ｐｒｏｃ．  Ａｓｉａ  ａｎｄ  Ｓｏｕｔｈ  Ｐａｃｉｆｉｃ  ＤｅｓｉｇｎＡｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ．３７−４２，１９９７）に記載の方法を使用して求めることができる。
【００２９】
図５（ａ）は、図４に示したハードウエアに対してクロックスケジューリングを実施しない（ゼロスキュー）場合を示す。一方、図５（ｂ）は、図４に示したハードウエアに対してクロックスケジューリングを実施する場合を示す。図５中のＷｍｉｎ，Ｗｍａｘは、ハードウエアの入出力ピン（４０１−４１２）−レジスタ（４１３，４１４）間の最小遅延，最大遅延を示し、ＣＴｉ，ＣＴｊ，ＣＴｋ，ＣＴｌはクロックタイミングを示している。図５（ａ）では、すべてのクロックタイミングが同じであり、実現できる最小クロック周期は１２０となる。一方、図５（ｂ）では、クロックスケジューリングによってクロックタイミングを調整しているため、実現できる最小クロック周期（準同期最小クロック周期）は６５となる。このように、クロックスケジューリングを実施する図５（ｂ）の場合のほうが最小クロック周期が小さい。
【００３０】
次にステップＳＴ１５において、準同期最小クロック周期と所望のクロック周期とを比較する。そして、準同期最小クロック周期が所望のクロック周期以下の場合には性能を満たしていると判断して処理を終了する（Ｙｅｓ）。所望のクロック周期よりも大きい場合には性能を満たしていないと判断してステップＳＴ１６にすすむ（Ｎｏ）。
【００３１】
そしてステップＳＴ１６（リタイミング工程）において、すべてのクロックタイミングを同値に再設定し直した後に、クロック周期を小さくすることを目的としてＣＤＦＧ内のレジスタ位置（レジスタの割り当て）を変更する。これをリタイミング処理という。リタイミング処理は、（Ｃ．Ｅ．Ｌｅｉｓｅｒｓｏｎ，Ｊ．Ｈ．Ｓａｘｅ，”Ｒｅｔｉｍｉｎｇ  Ｓｙｎｃｈｒｏｎｏｕｓ  Ｃｉｒｃｕｉｔｒｙ”，Ａｌｇｏｒｉｔｈｍｉｃａ，Ｖｏｌ．６  ｐｐ．５−３５）に記載の方法を使用することで実現することができる。
【００３２】
次にステップＳＴ１７において、ステップＳＴ１６のリタイミング処理によって性能を改善できた場合はステップＳＴ１４に戻る。性能を改善できない場合は処理を終了する。
【００３３】
以上のように第１の実施形態による高位合成方法では、クロック周期削減のためにクロックタイミング調整技術を利用しながら、ＣＤＦＧのスケジューリングをレジスタ数が最小である状態からレジスタ数が増える方向へ探索することになるため、クロックタイミングを調整しない場合と比べて少ないレジスタ数で所望のクロック周期を実現するハードウエアを実現できる。
【００３４】
（第２の実施形態）
図６は、この発明の第２の実施形態による高位合成方法の処理の手順を示すフローチャートである。第１の実施形態による高位合成方法とのおもな相違点は、準同期クロック周期を決定する際に、全レジスタ中の最大クロックタイミングと最小クロックタイミングとの差（クロックタイミング調整範囲）を制限する点である。
【００３５】
図６に示す高位合成方法は、図１に示したステップＳＴ１４に代えてステップＳＴ６２を備え、図１に示した処理手順に加えてさらにステップＳＴ６１，ＳＴ６３，ＳＴ６４を備える。
【００３６】
ステップＳＴ６１はステップＳＴ１１とステップＳＴ１２との間に設けられる。ステップＳＴ６１では、クロックタイミング調整可能範囲（クロックタイミング調整可能幅）を小さい値で初期化する。小さい値としては、ゼロなどが考えられる。ゼロの場合は、全レジスタのクロックタイミングを同値にすることを意味する。
【００３７】
ステップＳＴ６２では、クロックタイミング調整範囲に制限がある状態で準同期クロック周期を求める。クロックタイミング調整範囲に制限を持ったクロックスケジューリングは、文献（依田他，“準同期式回路の高速化のための修正コストを考慮したクロックスケジューリング”，ＶＬＤ９９−３６，電子情報通信学会技術研究報告，１９９８）に記載の方法を用いることで実現できる。
【００３８】
この高位合成方法では、ステップＳＴ１７において、ステップＳＴ１６のリタイミングによっても性能が改善されない場合に処理を終了せずにステップＳＴ６３およびステップＳＴ６４を実施する。ステップＳＴ６３（拡大工程）では、クロックタイミング調整範囲を一定の値で広げる。ステップＳＴ６４では、クロックタイミング調整範囲が一定の値（しきい値）以内か否かを判定する。クロックタイミング調整範囲が一定の値（しきい値）以下の場合（Ｙｅｓ）はステップＳＴ１２に戻り、しきい値よりも大きい場合（Ｎｏ）は処理を終了する。
【００３９】
第２の実施形態による高位合成方法ではクロックタイミング調整範囲を徐々に広げながら準同期クロック周期を求めるため、第１の実施形態による高位合成方法におけるよりもクロックタイミング調整範囲が小さいクロックタイミング情報が生成される可能性がある。一般的に、クロックタイミング調整範囲が広いほどレイアウト設計段階でクロックタイミングを実現するための回路が大きくなり、クロック回路の消費電力が大きくなる。したがって、クロック回路の消費電力をあまり増加させたくない場合には第２の実施形態による高位合成方法が有効である。
【００４０】
（第３の実施形態）
この発明の第３の実施形態による高位合成方法は、図１に示したステップＳＴ１４とステップＳＴ１５との間または図６に示したステップＳＴ６２とステップＳＴ１５との間に図７に示すステップＳＴ７１−ＳＴ７３を備える。その他の処理の流れは図１または図６に示した高位合成方法と同様である。
【００４１】
図７に示すステップＳＴ７１（クロックＰＤ積推定工程）では、クロックタイミング調整でクロック周期を小さくした場合のクロック消費電力を推定し、実現したクロック周期と推定したクロック消費電力との積を求める。ここで、クロックタイミング調整範囲量に対して単調に増加する関数を過去のレイアウト結果からあらかじめ計算しておき、この関数に基づいてクロック消費電力を推定すれば、クロック消費電力の推定精度を高めることができる。
【００４２】
ステップＳＴ７２（回路ＰＤ積推定工程）では、より高速な演算器に再割り付けした場合の回路消費電力を推定し、実現したクロック周期と推定した回路消費電力との積を求める。ここで、演算器やレジスタなどのハードウエアの１クロック周期内に動作する確率（動作率）を求め、この動作率を考慮して回路消費電力を推定すれば、回路消費電力の推定精度を高めることができる。
【００４３】
ステップＳＴ７３（選択的クロック周期改善工程）では、ステップＳＴ７１で求めた値とステップＳＴ７２で求めた値とのうち値の低いほうのクロック周期改善方法を選択してクロック周期を改善する。
【００４４】
以上のように第３の実施形態による高位合成方法では、クロック周期改善効率の高い（ここでは、より小さな消費電力増加率でより大きなクロック周期改善率を得られることを「効率が高い」という。）クロック周期改善手段を用いるため、より一層消費電力の低いハードウエアを合成することができる。
【００４５】
さらに、ステップＳＴ７１およびステップＳＴ７２においてクロック周期改善をわざと低く押さえてステップＳＴ７１−ＳＴ７３をクロック周期が改善しなくなるまで繰り返せばクロックタイミング調整と高速演算器割り付けとを複雑に組み合わせることが可能となり、より一層消費電力の低いハードウエアを合成することができる。
【００４６】
【発明の効果】
本発明によれば、所望の動作周波数を実現する回路をより少ないレジスタ数で合成することができる。これにより低消費電力化が実現される。
【図面の簡単な説明】
【図１】  この発明の第１の実施形態による高位合成方法の処理の手順を示すフローチャートである。
【図２】  コントロールデータフローグラフの一例を示す図である。
【図３】  （ａ）および（ｂ）は、図２に示したコントロールデータフローグラフをスケジューリングした結果の一例を示す図である。
【図４】  図３（ｂ）に示したスケジューリング結果に対してハードウエアが割り付けられた状態を示す図である。
【図５】  （ａ）および（ｂ）は、クロックスケジューリングを説明するための図である。
【図６】  この発明の第２の実施形態による高位合成方法の処理の手順を示すフローチャートである。
【図７】  この発明の第３の実施形態による高位合成方法の特徴部の処理の手順を示すフローチャートである。
【符号の説明】
ＳＴ１１  ＣＤＦＧ生成工程
ＳＴ１２  ＣＤＦＧスケジューリング工程
ＳＴ１３  アロケーション工程
ＳＴ１４  クロックスケジューリング工程
ＳＴ１６  リタイミング工程
ＳＴ６３  拡大工程
ＳＴ７１  クロックＰＤ積推定工程
ＳＴ７２  回路ＰＤ積推定工程
ＳＴ７３  選択的クロック周期改善工程
【図１】
0004082653.tif 000002
【図２】
0004082653.tif 000003
【図３】
0004082653.tif 000004
【図４】
0004082653.tif 000005
【図５】
0004082653.tif 000006
【図６】
0004082653.tif 000007
【図７】
0004082653.tif 000008