(57)【特許請求の範囲】
【請求項１】
ハードウェア記述言語（ＨＤＬ）によって入力される動作記述に基づいてコントロールデータフローグラフ（以下、ＣＤＦＧと略称する）を生成するＣＤＦＧ生成部と、
前記ＣＤＦＧ生成部により生成されたＣＤＦＧを、タイムステップに割り当ててスケジューリングを生成するスケジューリング部と、
前記スケジューリング部によって生成されたスケジューリングに基づいてアロケーションを行なうアロケーション部とを有する高位合成装置によって実施される高位合成方法であって、
前記ＣＤＦＧ生成部に、実行時間が定数でない可変時間処理をそれぞれ含む一連の処理をそれぞれ独立して並列に実行する並列処理記述が入力されると、該ＣＤＦＧ生成部が該並列処理記述に基づいて、前記各一連の処理をそれぞれ処理ブロックに分割して、各処理ブロックにおける各処理のＣＤＦＧを生成する工程と、
前記スケジューリング部が、前記ＣＤＦＧ生成部にて生成された各処理ブロックにおけるＣＤＦＧを、前記可変時間処理が現れるまでの各処理ブロックにおけるそれぞれの処理が同期して動作するようにタイムステップを割り当てるとともに、前記可変時間処理以降における各処理ブロックのそれぞれの処理を各処理ブロック毎に独立したタイムステップにそれぞれ割り当ててスケジューリングを生成する工程と、
前記アロケーション部が、前記各処理ブロックにおいて前記可変時間処理が現れるまでの異なるタイムステップにそれぞれ割り当てられた処理が共通の場合に、該共通の各処理に対して共通のハードウェア資源を割り当て、前記可変時間処理以降において前記各処理ブロックにおける処理が共通の場合には、該共通の各処理に対して独立のハードウェア資源をそれぞれ割り当てる工程とを包含することを特徴とする高位合成方法。
【請求項２】
前記アロケーション部は、前記可変時間処理以降において前記各処理ブロックの各処理が共通であって相互に排他的に実行される場合には、該共通の各処理に対して共通のハードウェア資源を割り当てる、請求項１に記載の高位合成方法。
【請求項３】
ハードウェア記述言語（ＨＤＬ）によって入力される動作記述に基づいてコントロールデータフローグラフ（以下、ＣＤＦＧ略称する）を生成するＣＤＦＧ生成部と、
前記ＣＤＦＧ生成部により生成されたＣＤＦＧを、タイムステップに割り当ててスケジューリングを生成するスケジューリング部と、
前記スケジューリング部によって生成されたスケジューリングに基づいてアロケーションを行なうアロケーション部とを有する高位合成装置であって、
前記ＣＤＦＧ生成部に、実行時間が定数でない可変時間処理をそれぞれ含む一連の処理をそれぞれ独立して並列に実行する並列処理記述が入力されると、該ＣＤＦＧ生成部が該並列処理記述に基づいて、前記各一連の処理をそれぞれ処理ブロックに分割して、各処理ブロックにおける各処理のＣＤＦＧを生成し、
前記スケジューリング部が、前記ＣＤＦＧ生成部にて生成された各処理ブロックにおけるＣＤＦＧを、前記可変時間処理が現れるまでの各処理ブロックにおけるそれぞれの処理が同期して動作するようにタイムステップを割り当てるとともに、前記可変時間処理以降における各処理ブロックのそれぞれの処理を各処理ブロック毎に独立したタイムステップにそれぞれ割り当ててスケジューリングを生成し、
前記アロケーション部が、前記各処理ブロックにおいて前記可変時間処理が現れるまでの異なるタイムステップにそれぞれ割り当てられた処理が共通の場合に、該共通の各処理に対して共通のハードウェア資源を割り当て、前記可変時間処理以降において前記各処理ブロックにおける処理が共通の場合には、該共通の各処理に対して独立のハードウェア資源をそれぞれ割り当てることを特徴とする高位合成装置。
【請求項４】
前記アロケーション部は、前記可変時間処理以降において前記各処理ブロックの各処理が共通であって相互に排他的に実行される場合には、該共通の各処理に対して共通のハードウェア資源を割り当てる、請求項３に記載の高位合成装置。
【請求項５】
請求項１に記載の高位合成方法を実行するためのプログラムが記録されていることを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動作記述によって表現された半導体集積回路の論理回路を合成する高位合成方法に関し、特に並列処理記述および可変時間処理記述を含んだ動作記述から論理回路を合成する高位合成方法に関する。
【０００２】
【従来の技術】
半導体集積回路の多機能化、高密度化に伴い、その回路規模は増大する傾向にあり、回路設計に要する時間も増加しつつある。
【０００３】
この回路設計に要する時間を短縮する方法の一つとして、ハードウェア記述言語（ＨＤＬ）により記述された動作記述から回路を自動合成する方法がある。
【０００４】
この動作記述から回路を自動合成する方法として、並列処理、および、同期通信等実行時間が定数でない処理（可変時間処理）を記述可能なＨＤＬで記述された動作記述から回路を自動合成する高位合成方法が、特開平１０−１１６３０２号公報に開示されている。
【０００５】
同期通信とは、送り側と受け側の両方が準備できた時に通信を行う通信方法である。
【０００６】
送り側が準備ができて受け側の準備ができていない時には、受け側の準備ができるまで送り側は待ち続ける。
【０００７】
受け側が準備ができて送り側の準備ができていない時は、送り側の準備ができるまで受け側は待ち続ける。
【０００８】
このように処理の実行時間が相手の状況により変化するため、同期通信は可変時間処理となる。
【０００９】
この高位合成方法で用いられるＨＤＬでは、並列記述として記述された各処理は独立に実行されるという前提がある。
【００１０】
すなわち、並列記述として記述された各処理のうち、1つの処理が同期通信等の可変時間処理により一時的に停止したとしても、他の処理は停止せずに実行を続けるという前提であり、多くの並列記述言語がこの前提を持っている。
【００１１】
また、他の従来技術として「Ｇｌｏｂａｌ  Ｈａｒｄｗａｒｅ  Ｓｙｎｔｈｅｓｉｓ  ｆｒｏｍ  Ｂｅｈａｖｉｏｒａｌ  Ｄａｔａｆｌｏｗ  Ｄｅｓｃｒｉｐｔｉｏｎｓ（２７ｔｈ  ＤＡＣ，  １９９０，  ｐｐ４５６−４６１）」に記載された方法がある。
【００１２】
この方法は、並列処理を記述可能なＨＤＬで記述された動作記述から、並列処理間でハードウェア資源を共有した回路を自動合成する方法である。
【００１３】
この方法では、並列処理の各処理が独立に実行されることを前提としていない。
【００１４】
【発明が解決しようとする課題】
前記特開平１０−１１６３０２号公報に開示された高位合成方法では並列処理間でハードウェア資源の共有が行われない。
【００１５】
すなわち本質的に共有可能なハードウェア資源であっても共有が行われず、回路規模が大きくなるという欠点があった。
【００１６】
また、「Ｇｌｏｂａｌ  Ｈａｒｄｗａｒｅ  Ｓｙｎｔｈｅｓｉｓ  ｆｒｏｍ  Ｂｅｈａｖｉｏｒａｌ  Ｄａｔａｆｌｏｗ  Ｄｅｓｃｒｉｐｔｉｏｎｓ」に記載されている方法によれば、並列処理を記述可能なＨＤＬで記述された動作記述から、並列処理間でハードウェア資源を共有した回路を生成できるが、入力される動作記述が、並列記述として記述された各処理を独立に実行するという前提を持たず、可変時間処理記述を含むことができない。
【００１７】
そのため、同期通信処理、ループ、条件分岐等を扱うことができないという欠点があった。
【００１８】
本発明は、上記問題点を解決するためになされたものであり、第１の目的は、独立に実行される並列処理、および可変時間処理を記述可能なＨＤＬで記述された動作記述から、並列処理間でハードウェア資源を共有した回路を生成でき、回路規模の縮小を図ることが可能な高位合成方法を提供することである。
【００１９】
また、本発明の第２の目的は、独立に実行される並列処理、および可変時間処理を記述可能なＨＤＬで記述された動作記述から、並列処理間でハードウェア資源を共有した回路を生成でき、回路規模の縮小を図ることが可能な高位合成装置を提供することである。
【００２０】
さらに、本発明の第３の目的は、独立に実行される並列処理、および可変時間処理を記述可能なＨＤＬで記述された動作記述から、並列処理間でハードウェア資源を共有した回路を生成でき、回路規模の縮小を図ることが可能な高位合成プログラムを記録した記録媒体を提供することである。
【００２１】
【課題を解決するための手段】
本発明の高位合成方法は、ハードウェア記述言語（ＨＤＬ）によって入力される動作記述に基づいてコントロールデータフローグラフ（以下、ＣＤＦＧと略称する）を生成するＣＤＦＧ生成部と、前記ＣＤＦＧ生成部により生成されたＣＤＦＧを、タイムステップに割り当ててスケジューリングを生成するスケジューリング部と、前記スケジューリング部によって生成されたスケジューリングに基づいてアロケーションを行なうアロケーション部とを有する高位合成装置によって実施される高位合成方法であって、前記ＣＤＦＧ生成部に、実行時間が定数でない可変時間処理をそれぞれ含む一連の処理をそれぞれ独立して並列に実行する並列処理記述が入力されると、該ＣＤＦＧ生成部が該並列処理記述に基づいて、前記各一連の処理をそれぞれ処理ブロックに分割して、各処理ブロックにおける各処理のＣＤＦＧを生成する工程と、前記スケジューリング部が、前記ＣＤＦＧ生成部にて生成された各処理ブロックにおけるＣＤＦＧを、前記可変時間処理が現れるまでの各処理ブロックにおけるそれぞれの処理が同期して動作するようにタイムステップを割り当てるとともに、前記可変時間処理以降における各処理ブロックのそれぞれの処理を各処理ブロック毎に独立したタイムステップにそれぞれ割り当ててスケジューリングを生成する工程と、前記アロケーション部が、前記各処理ブロックにおいて前記可変時間処理が現れるまでの異なるタイムステップにそれぞれ割り当てられた処理が共通の場合に、該共通の各処理に対して共通のハードウェア資源を割り当て、前記可変時間処理以降において前記各処理ブロックにおける処理が共通の場合には、該共通の各処理に対して独立のハードウェア資源をそれぞれ割り当てる工程とを包含することを特徴とする。
前記アロケーション部は、前記可変時間処理以降において前記各処理ブロックの各処理が共通であって相互に排他的に実行される場合には、該共通の各処理に対して共通のハードウェア資源を割り当てる。
本発明の高位合成装置は、ハードウェア記述言語（ＨＤＬ）によって入力される動作記述に基づいてコントロールデータフローグラフ（以下、ＣＤＦＧ略称する）を生成するＣＤＦＧ生成部と、前記ＣＤＦＧ生成部により生成されたＣＤＦＧを、タイムステップに割り当ててスケジューリングを生成するスケジューリング部と、前記スケジューリング部によって生成されたスケジューリングに基づいてアロケーションを行なうアロケーション部とを有する高位合成装置であって、前記ＣＤＦＧ生成部に、実行時間が定数でない可変時間処理をそれぞれ含む一連の処理をそれぞれ独立して並列に実行する並列処理記述が入力されると、該ＣＤＦＧ生成部が該並列処理記述に基づいて、前記各一連の処理をそれぞれ処理ブロックに分割して、各処理ブロックにおける各処理のＣＤＦＧを生成し、前記スケジューリング部が、前記ＣＤＦＧ生成部にて生成された各処理ブロックにおけるＣＤＦＧを、前記可変時間処理が現れるまでの各処理ブロックにおけるそれぞれの処理が同期して動作するようにタイムステップを割り当てるとともに、前記可変時間処理以降における各処理ブロックのそれぞれの処理を各処理ブロック毎に独立したタイムステップにそれぞれ割り当ててスケジューリングを生成し、前記アロケーション部が、前記各処理ブロックにおいて前記可変時間処理が現れるまでの異なるタイムステップにそれぞれ割り当てられた処理が共通の場合に、該共通の各処理に対して共通のハードウェア資源を割り当て、前記可変時間処理以降において前記各処理ブロックにおける処理が共通の場合には、該共通の各処理に対して独立のハードウェア資源をそれぞれ割り当てることを特徴とする。
前記アロケーション部は、前記可変時間処理以降において前記各処理ブロックの各処理が共通であって相互に排他的に実行される場合には、該共通の各処理に対して共通のハードウェア資源を割り当てる。
本発明のコンピュータ読取可能な記録媒体は、請求項１に記載の高位合成方法を実行するためのプログラムが記録されていることを特徴とする。
【００２９】
【発明の実施の形態】
図１は、本発明の実施の形態における高位合成方法の処理手順を説明するフローチャートである。
【００３０】
この高位合成方法は、各処理が独立に実行されることを前提とした並列記述、もしくは同期通信等実行時間が定数でない処理（可変時間処理）を記述可能なＨＤＬで記述された動作記述を入力とし、並列記述により明示的に記述された並列処理間で演算器等のハードウェア資源を共有した回路を生成する回路合成部１を含む。
【００３１】
図２は、前記回路合成部１の処理手順を説明するためのフローチャートである。
【００３２】
まず、ＣＤＦＧ生成部２で、並列記述、もしくは可変時間処理記述を含む動作記述をコントロールデータフローグラフ（ＣＤＦＧ）に変換する。
【００３３】
ＣＤＦＧとは、データの入出力、演算、制御の分岐等を節点で表し、節点間のデータの流れや制御の流れを枝で表したグラフである。
【００３４】
高位合成において、動作記述をＣＤＦＧに変換する理由は、動作記述に記述された動作が保証される上に、合成される論理回路に並列化の余地を残すことが可能な動作表現だからである。
【００３５】
ＣＤＦＧの詳細を記した文献としては、Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ，  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓがある。
【００３６】
本発明における高位合成方法では、並列記述や同期通信等可変時間処理記述を含む動作記述を入力とするため、これらをＣＤＦＧで表現する必要がある。
【００３７】
そこで、これらを表現可能なＣＤＦＧ表現を用いる。
【００３８】
図４に、図３の動作記述を表現したＣＤＦＧの例を示す。
【００３９】
図３の動作記述において、ｐａｒは並列記述であり、ｐａｒに含まれる各並列処理７、８を並列に実行する。
【００４０】
並列構文３を表現するために、ＣＤＦＧにおけるｐａｒブロック４を用いる。
ｐａｒブロック内部は、並列に動作する処理ブロック５、６に分割されており、並列記述３で記述された各並列処理７、８は、それぞれ処理ブロック５、６に割り当てられる。
【００４１】
また、同期通信９、１０をＣＤＦＧの節点１１、１２で表す。
【００４２】
ここで、図2の説明に戻る。
【００４３】
スケジューリング部１３では、ＣＤＦＧの各演算、同期通信等可変時間処理を、コントロールステップとよばれるタイムステップに割り当てるスケジューリングを行う。
【００４４】
なお、ＣＤＦＧの全ての演算、可変時間処理をコントロールステップに割り当てた状態をスケジューリングと呼ぶ。
【００４５】
高位合成における一般的なスケジューリング方法の詳細を記した文献としては、Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ，  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓがある。
【００４６】
図５は、このスケジューリング部の処理手順の一例を説明するフローチャートである。
【００４７】
まず、初期スケジューリング決定部１４で、初期スケジューリングを決定する。
【００４８】
次にハードウェアコスト見積り部１５で、現在のスケジューリングでのハードウェアコストを見積り、スケジューリングと見積り結果記憶部１６で、現在のスケジューリングと共に記憶する。
【００４９】
そしてスケジューリング変更部１７でスケジューリングを変更し、ハードウェアコスト見積り部１５に戻って処理を続ける。
【００５０】
これを、全てのスケジューリングが網羅されるまで続け、コスト最小スケジューリング選択部１８でハードウェアコストが最小になるスケジューリングを選択し、これを最終的なスケジューリング結果とする。
【００５１】
ここで、ハードウェアコスト見積り部１５におけるハードウェアコスト見積りの方法を、図６、図７を用いて説明する。
【００５２】
図６に示すＣＤＦＧおよびスケジューリングにおいて、最初に可変時間処理１９、２８が現れる以前の並列処理部分２０では、並列動作する２つの処理ブロック２１、２２は同期して動作させることができる。
【００５３】
すなわち、最初のステップで乗算２３と減算２４を実行し、次のステップで減算２５と乗算２６を実行する。
【００５４】
しかし、可変時間処理１９、２８以降の並列処理部分２７では、２つの処理ブロック２１、２２は独立に動作させる必要がある。
【００５５】
なぜなら、可変時間処理により一つの処理が一時的に停止したとしても、それと並列に実行される処理は動作し続けなければならないからである。
【００５６】
並列処理部分２０の区間では、並列動作する各処理ブロック２１、２２は同期して動作させることができるため、各処理ブロックにおける処理を共通の有限状態遷移機械（ＦＳＭ）で制御することができる。
【００５７】
並列処理部分２７の区間では、並列動作する各処理ブロック２１、２２は独立して動作させる必要があるため、各処理ブロックにおける処理を独立した有限状態遷移機械（ＦＳＭ）で制御しなければならない。
【００５８】
共通のＦＳＭで制御可能な並列処理部分２０においては、異なるコントロールステップにスケジューリングされた演算同士では、並列処理間であっても演算器の共有を行うことができるが、独立したＦＳＭで制御される並列処理部分２７においては、処理の排他性が保証されない限り、並列処理間で演算器の共有を行うことができない。
【００５９】
よって、図６のスケジューリングにおけるハードウェアコストの見積り値は、乗算器１個、減算器１個、加算器２個となる。
【００６０】
なお、独立したＦＳＭで制御される並列処理部分においても、処理の排他性が保証されれば、並列処理間で演算器の共有を行うことができる。
【００６１】
図７の例で、同期通信２９で送信されたデータは同期通信３０で受信されることがわかっているとする。
【００６２】
その場合、加算３１と加算３２の排他性が保証されるため、演算器の共有を行うことができる。
【００６３】
すなわち、図７のスケジューリングにおけるハードウェアコストの見積り値は、乗算器１個、減算器１個、加算器１個となる。
【００６４】
図５におけるハードウェアコスト見積り部１５では、現在のスケジューリングに対してこのようにハードウェアコストを見積り、全てのスケジューリングを網羅するまで、スケジューリング変更部１７によりスケジューリングを変更しながら、処理を続ける。
【００６５】
そして、コスト最小スケジューリング部１８で、コスト最小となるスケジューリングを選択し、最終的なスケジューリング結果とする。
【００６６】
再び、図２に戻り、アロケーション部でアロケーションを行う。
【００６７】
アロケーションとは、スケジューリング結果を受けて、ＣＤＦＧの演算節点に演算器を割り当て、データ選択のためのマルチプレクサ、データ記憶のためのレジスタ、および、演算器、レジスタ、マルチプレクサを制御するためのコントローラーを生成し、それぞれを接続することにより回路を合成する処理である。
【００６８】
アロケーションでは、時間的に共有できるハードウェア資源は共有されるように回路が合成される。
【００６９】
高位合成における一般的なアロケーション方法の詳細を記した文献とし
ては、Ｈｉｇｈ−Ｌｅｖｅｌ  Ｓｙｎｔｈｅｓｉｓ，Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓがある。
【００７０】
【発明の効果】
本発明の高位合成方法によれば、回路合成工程は、並列処理間でハードウェア資源を共有した回路を生成するため、回路規模の縮小を図ることが可能となるという効果を奏する。
【００７１】
また、本発明の高位合成方法によれば、スケジューリング工程は、並列処理間でのハードウェア資源共有を考慮してスケジューリングを行うため、並列処理間でハードウェア資源を共有した回路を合成でき、回路規模の縮小を図ることができるという効果を奏する。
【００７２】
また、本発明の高位合成方法によれば、回路合成工程は、共通の有限状態遷移機械（ＦＳＭ）で制御可能な並列処理部分間でハードウェア資源を共有した回路を生成するため、回路規模の縮小を図ることが可能となるという効果を奏する。
【００７３】
また、本発明の高位合成方法によれば、回路合成工程は、独立な有限状態遷移機械（ＦＳＭ）で制御される並列処理部分間でハードウェア資源を共有した回路を生成するため、回路規模の縮小を図ることが可能となるという効果を奏する。
【００７４】
また、本発明の高位合成方法によれば、スケジューリング工程は、共通の有限状態遷移機械（ＦＳＭ）で制御可能な並列処理部分間でのハードウェア資源共有を考慮してスケジューリングを行うため、並列処理間でハードウェア資源を共有した回路を合成でき、回路規模の縮小を図ることができるという効果を奏する。
【００７５】
また、本発明の高位合成方法によれば、スケジューリング工程は、独立な有限状態遷移機械（ＦＳＭ）で制御される列処理部分間でのハードウェア資源共有を考慮してスケジューリングを行うため、並列処理間でハードウェア資源を共有した回路を合成でき、回路規模の縮小を図ることができるという効果を奏する。
【００７６】
本発明の高位合成装置によれば、回路生成手段は、並列処理間でハードウェア資源を共有した回路を生成するため、回路規模の縮小を図ることが可能となるという効果を奏する。
【００７７】
本発明の記録媒体によれば、回路生成ステップは、並列処理間でハードウェア資源を共有した回路を生成するため、回路規模の縮小を図ることが可能となるという効果を奏する。
【図面の簡単な説明】
【図１】本実施の形態における高位合成方法の処理手順を説明するフローチャートである。
【図２】図１の回路合成部の処理手順を説明するためのフローチャートである。
【図３】並列記述、可変時間処理記述を含む動作記述の例である。
【図４】図３の動作記述を表現したＣＤＦＧの例である。
【図５】図２のスケジューリング部の処理手順の一例を説明するフローチャートである。
【図６】共通の有限状態遷移機械（ＦＳＭ）で制御可能な並列処理部分間でのハードウェア資源共有を考慮してスケジューリングを行う場合のハードウェアコスト見積り方の説明図である。
【図７】独立した有限状態遷移機械（ＦＳＭ）で制御される並列処理部分間でのハードウェア資源共有を考慮してスケジューリングを行う場合のハードウェアコスト見積り方の説明図である。
【符号の説明】
１        回路合成部
２        ＣＤＦＧ生成部
３        並列構文
７、８    並列処理
９、１０  同期通信構文
１３  スケジューリング部
【図１】
0003942061.tif 000002
【図２】
0003942061.tif 000003
【図３】
0003942061.tif 000004
【図４】
0003942061.tif 000005
【図５】
0003942061.tif 000006
【図６】
0003942061.tif 000007
【図７】
0003942061.tif 000008