(57)【要約】【課題】  高性能低コストの回路を合成するために、ループ繰り返しスケジュールを決定する際にクロックサイクルタイム解析を使用する方法を提供する。【解決手段】  提案されたループ繰り返しスケジュールの有効性を判断する方法は、オペレーションおよびオペレーション間のエッジを含む依存グラフを受け取る（２０１）ステップと、性能仕様を受け取るステップと、上記依存グラフのオペレーションに対する待ち時間の割り当てを受け取るステップと、すべての依存制約条件およびタイミング制約条件が性能仕様（２０６、２０７）について満たされるような、上記依存グラフにおけるクロックサイクル境界の配置の存在を決定するステップと、を含む。
2006502501.tif 000002
【特許請求の範囲】
【請求項１】
提案されたループ繰り返しスケジュールの有効性を判断する方法であって、
オペレーションおよび該オペレーション間のエッジを含む依存グラフを受け取る（２０１）ことと、
性能仕様を受け取ることと、
前記依存グラフのオペレーションに対する待ち時間の割り当てを受け取ることと、
すべての依存制約条件およびタイミング制約条件が前記性能仕様（２０６、２０７）について満たされるような、前記依存グラフにおけるクロックサイクル境界の配置の存在を決定することと
を含む方法。
【請求項２】
マクロセルライブラリを受け取ることと、
前記依存グラフのオペレーションに待ち時間を割り当てることと
をさらに含む請求項１に記載の方法。
【請求項３】
提案されたループ繰り返しスケジューリングベクトルを受け取ることと、
前記依存グラフに含まれるエッジのオメガを計算することと
をさらに含む請求項１に記載の方法。
【請求項４】
前記依存グラフにおけるクロックサイクル境界の配置の前記存在は、
前記依存グラフのあらゆる反復サイクルについて、そのように配置されたクロックサイクル境界の総数が、前記反復サイクルに属する前記エッジの前記オメガの合計に前記提案された開始間隔を乗算したものに等しくなるように、
そのように配置された連続したクロックサイクル境界間の最大遅延が、前記提案されたクロックサイクルタイムよりも大きくないように
行われる
請求項３に記載の方法。
【請求項５】
前記存在は、
前記依存グラフのすべての反復サイクルを列挙することと、
このような各反復サイクルについて、
そのように配置されたクロックサイクル境界の総数が、前記反復サイクルに属する前記エッジの前記オメガの合計に前記提案された開始間隔を乗算したものに等しくなるように、
そのように配置された連続したクロックサイクル境界間の前記最大遅延が、前記提案されたクロックサイクルタイムよりも大きくないように、
前記反復サイクルに沿ってクロックサイクル境界の配置を決定することと、
前記各反復サイクルに沿ってクロックサイクル境界の配置の存在となるように前記存在を導出することと
によって決定される
請求項４に記載の方法。
【請求項６】
提案されたループ繰り返しスケジュールの有効性を確認する装置であって、
依存グラフのオペレーションに待ち時間を割り当てる手段と、
前記依存グラフのオペレーションに関連付けられたエッジのそれぞれについてオメガを計算する手段と、
前記依存グラフのクロックサイクル境界の配置の存在を決定する手段と、
提案された繰り返しスケジュールベクトルの有効性を判断する手段と
を備える装置。
【請求項７】
前記クロックサイクル境界の前記配置を決定する手段
をさらに備える請求項６に記載の装置。
【請求項８】
前記依存グラフにおける前記クロックサイクル境界の前記配置に応じて、前記提案されたループ繰り返しスケジュールの比較コストを求める手段
をさらに備える請求項６に記載の装置。
【請求項９】
クロックサイクル境界の前記配置の存在を決定する前記手段は、
前記依存グラフのあらゆる反復サイクルについて、そのように配置されたクロックサイクル境界の総数が、前記依存グラフの前記関連した反復サイクルに属する前記エッジの前記オメガの合計に、提案された開始間隔を乗算したものに等しくなることと、
そのように配置された連続したクロックサイクル境界間の最大遅延が、提案されたクロックサイクルタイムと等しいか小さいこと
を含む請求項６に記載の装置。
【請求項１０】
存在を決定する前記手段は、
前記依存グラフのすべての反復サイクルを列挙することと、
このような各反復サイクルについて、
そのように配置されたクロックサイクル境界の総数が、前記反復サイクルに属する前記エッジの前記オメガの合計に前記提案された開始間隔を乗算したものに等しくなるように、
そのように配置された連続したクロックサイクル境界間の前記最大遅延が、前記提案されたクロックサイクルタイムよりも大きくないように、
前記反復サイクルに沿ってクロックサイクル境界の配置を決定することと、
前記各反復サイクルに沿ってクロックサイクル境界の配置の存在となるように前記存在を導出することと
を含む請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、デジタル回路設計を対象にし、より詳細には、高性能低コストの回路を合成するために、ループ繰り返しスケジュールを決定する際にクロックサイクルタイム解析を使用する方法を対象にする。
【背景技術】
【０００２】
［関連出願の相互参照］
本出願は、本発明の譲受人に譲渡された「SYSTEM FOR AND METHOD OF CLOCK CYCLE-TIME ANALYSIS USING MODE-SLICING MECHANISM」という発明の名称の米国特許出願第［代理人整理番号第１００２００５５９−１号］、および、「METHOD FOR DESIGNING MINIMAL COST, TIMING CORRECT HARDWARE DURING CIRCUIT SYNTHESIS」という発明の名称の米国特許出願第［代理人整理番号第１００２００５６０−１号］に関連するものである。
これらの出願は本出願と同時に出願され、この引用によって、それらの開示は、全内容が参照により本明細書に援用される。
【０００３】
技術の継続的な進歩および生産コストの削減が組み合わさることによって、高度なデジタル回路を実装または使用する電子デバイスが急増している。
これらの電子デバイスには、デスクトップコンピュータ、ラップトップコンピュータ、ハンドヘルドデバイス、プリンタ、デジタルカメラ、ファクシミリ装置、およびそれ以外の電子デバイスが含まれる。
また、ハンドヘルドデバイスとしては、携帯情報端末（ＰＤＡ）、ハンドヘルドコンピュータ、携帯電話等がある。
これらのデジタル回路は、電子デバイスの機能を提供するのに必要とされるアプリケーションまたはアルゴリズムを実行する。
これらのデジタル回路は、最小限のコストで高性能を有することが望ましい。
回路のコストは、通常、その回路のシリコン面積の点から測定され、多くの場合、回路内のコンポーネント（例えば、機能ユニット、レジスタ、配線等）の個数から見積もられる。
回路の性能は、スループット（すなわち、クロックサイクルごとに実行されるタスク数）、待ち時間（すなわち、単一のタスクを完了するためのクロックサイクル数）、およびクロック速度といったいくつかのメトリックの組み合わせとして表現することができる。
【０００４】
アプリケーションまたはアルゴリズムをデジタル回路ハードウェアにマッピングするプロセスは、いくつかのステップを含む。
これらのステップの１つは、スケジュールするステップである。
すなわち、アクティビティを特定の時点で行うように割り当てるステップである。
多くのアプリケーションの性能は、そのアプリケーションコードまたはアルゴリズムに存在することがあるループネストの性能によって支配されるので、このループ繰り返しをスケジューリングするステップは特に重要である。
ループは、或る範囲の値についての１つまたは複数の式（expression）の繰り返しである。
ループネストは、各ループが別のループ内に連続的にネストした１組のループである。
あるいは、ネストしたループは、「深さｎ」のループネストを有する、Ｃ、Ｊａｖａ（登録商標）、Ｐａｓｃａｌ等の高級言語のプログラムを指す。
ここで、ｎは整数である。
換言すると、深さ２のネストしたループでは、第１のループが第２のループ内にネストしている。
【０００５】
ループ繰り返しスケジューリングは、ループレスト（ネスト）の各繰り返しの開始時間を特定のクロックサイクルに割り当てることである。
このステップは、結果のハードウェアが所望の性能でループネストを実行しなければならないという目的、または、結果のハードウェアが最大限の性能でループネストを実行しなければならないという目的で実行される。
さらに、結果のハードウェアのコストを最小にすることが望ましい場合がある。
ループネストの性能は、そのスループット、すなわち単位時間あたりに開始されるループ繰り返しの回数によって決定される。
スループットはＩＩ×Ｔの逆数として表現される。
ここで、開始間隔（ＩＩ（Initiation Interval））は、連続したループ繰り返しの開始と開始との間のクロックサイクル数として定義され、Ｔはクロック周期である。
【０００６】
ループ繰り返しスケジューリングのこれらの目的を満たすために、通常、１組の候補の繰り返しスケジュールが生成され、次いで、有効性について評価される。
さらに、この１組の候補の繰り返しスケジュールは、必要ならば、コストについても評価することができる。
候補のループ繰り返しスケジュールが有効であるということは、ループネストが所与のＩＩおよび所与のＴでその候補のループ繰り返しスケジュールに従ってスケジューリングされた場合に、すべてのデータ依存関係およびタイミング制約条件を満たすことが可能であることを意味する。
或るプログラムオペレーションからそれ自身へのデータフロー依存が後続のループ繰り返しに存在する場合に、反復サイクル（recurrence cycle）が引き起こされる。
データ依存関係がループの反復サイクルを巡って満たされるには、次の１組の不等式を満たさなければならない。
Ｄｅｌａｙ（Ｃ１）≦ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ１）
Ｄｅｌａｙ（Ｃ２）≦ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ２）
…
Ｄｅｌａｙ（ＣＮ）≦ＩＩ×Ｄｉｓｔａｎｃｅ（ＣＮ）
ここで、依存グラフＣ１、Ｃ２、…、ＣＮには、「Ｎ」個の反復サイクルがあり、Ｄｅｌａｙ（Ｃｉ）は、反復サイクルＣｉを巡る総待ち時間であり、Ｄｉｓｔａｎｃｅ（Ｃｉ）は、反復サイクルＣｉに沿った各依存エッジのオメガの合計である。
反復サイクルを巡る待ち時間は、依存関係が反復サイクルを巡って進むのに要するクロック周期の個数であり、依存エッジのオメガは、そのデータフローにおけるプロデューサオペレーションとコンシューマオペレーションとの間の、候補の繰り返しスケジュールによって与えられたループ繰り返し分離（loop iteration separation）である。
【０００７】
これに関連して、候補のループ繰り返しスケジュールが所与のＩＩおよびＴの間に有効であると確認されるように、各反復サイクルを巡る総待ち時間は小さいことが望ましい。
従来の手法は、クロックサイクルの整数倍として表現されたオペレーション待ち時間を使用する。
これらの手法によって計算された反復サイクル待ち時間は控えめなものであり、それによって、いくつかの候補の繰り返しスケジュールは、有効でないとして悲観的に却下されることになる。
これを図１Ａ〜図１Ｃの例によって示す。
【０００８】
図１Ａは、ネストしたループを表すコードフラグメントである。
コードフラグメント１００は、外部ループ１０１ならびに内部ループ１０２および命令文１０３を含む。
図１Ｂは、図１Ａのネストしたループのコードフラグメントに対応するループ依存グラフである。
図１Ｂにおいて、繰り返し間の依存エッジには、逐次的なセマンティクスで表現されたループのソースコードから導出された繰り返し距離ベクトルの注釈が付けられている。
図１Ｂの依存グラフは、オペレーション１０４→エッジ１０６→オペレーション１０５→エッジ１０７から成る反復サイクルＣ１、および、オペレーション１０４→エッジ１０６→オペレーション１０５→エッジ１０８から成る反復サイクルＣ２の２つの反復サイクルを有する。
【０００９】
一例として、必要な性能は、ＩＩが３に等しく、Ｔが２．０ナノ秒に等しくなることを要求することができる。
候補の繰り返しスケジューリングベクトルλが［１００  １］Ｔに等しい場合、対応する繰り返しスケジューリング波面を図１Ｃの繰り返し空間に示す。
繰り返し距離ベクトルｄの注釈が付けられたエッジのオメガは、内積λＴ・ｄである。
この関係を使用すると、λによって与えられた、繰り返しスケジュールのエッジ１０７のオメガは、［１００  １］・［０  １］Ｔ＝１となる。
同様に、λによって与えられた、繰り返しスケジュールのエッジ１０８のオメガは、［１００  １］・［１  −９９］Ｔ＝１となる。
他のすべてのエッジのオメガは、その繰り返し距離ベクトルｄが［０  ０］Ｔに等しいので、０となる。
反復サイクルＣ１に関連した距離、すなわちＤｉｓｔａｎｃｅ（Ｃ１）は、そのエッジ（すなわち、図１Ｂのエッジ１０６および１０７）に沿ったオメガの合計によって与えられる。
したがって、Ｄｉｓｔａｎｃｅ（Ｃ１）は０＋１＝１となる。
同様に、反復サイクルＣ２に関連した距離、すなわちＤｉｓｔａｎｃｅ（Ｃ２）は０＋１＝１となる。
従来の手法は、クロックサイクルの整数倍として表現されたオペレーション待ち時間を使用する。
例えば、乗算オペレーション（×）の待ち時間は３クロックサイクルとなることがあり、加算オペレーション（＋）の待ち時間は１クロックサイクルとなることがある。
反復サイクルＣ１では、遅延は３＋１＝４クロックサイクルとなる。
Ｄｅｌａｙ（Ｃ１）?ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ１）の不等式を使用すると、４−３×１≦０が与えられるが、これは満たされていない。
同様に、反復サイクルＣ２では、遅延は３＋１＝４クロックサイクルとなる。
Ｄｅｌａｙ（ｃ１）?ＩＩ×Ｄｉｓｔａｎｃｅ（ｃ１）の不等式を使用すると、４−３×１≦０が与えられるが、これも満たされていない。
したがって、オペレーション待ち時間がクロックサイクルの整数倍として表現されると、［１００  １］Ｔに等しい候補の繰り返しスケジューリングベクトルλは、有効でないことが分かる。
【非特許文献１】CHENG-TSUNG HWANG ET AL : " A FORMAL APPROACH TO THE SCHEDULING PROBLEM IN HIGH LEVEL SYNTHESIS" IEEE TRANSACTIONS ON COMPUTER AIDED DESIGN OF INTEGRATED ClRCUITS AND SYSTEMS, IEEE INC. NEW YORK, US, vol. 10 no. 4, 1 April l991(1991-04-01), pages 464-475 , XP000219191 ISSN: 0278-0070 abstract page 464, left-hand column, Iine 1- right-hand column, line 35 page 465, right-hand column, line 9- page 471, left-hand column, line 43 page 473, right-hand column, line 4- page 474, left-hand column, line 10
【非特許文献２】PUGH W: "A PRACTICAL ALGORITHM FOR EXACT ARRAY DEPENDENCE ANALYSIS" COMMUNICATIONS OF THE ASSOCIATION FOR COMPUTING MACHINERY, ASSOCIATION FOR COMPUTING MACHINERY. NEW YORK. US. vol. 35, no. 8, 1 August 1992 (1992-08-01), pages 102-114, XP000331496 ISSN: 0001-0782 page 102 - page 103 page 108, right-hand column, line 8 - page 109, left-hand column, line 15 page 109, right-hand column, line 20 -page 110, right-hand column, line 49
【非特許文献３】GOVINDARAJAN R ET AL: "A novel framework for multi-rate scheduling in DSP applications" APPLICATION-SPECIFIC ARRAY PROCESSORS, 1993. PROCEEDINGS., INTERNATIONAL CONFERENCE ON VENICE, ITALY 25-27 OCT.1993, LOS ALAMITOS, CA, USA, IEEE COMPUT. SOC, US, 25 October 1993 (1993-l0-25), pages 77-88. XP010136775 ISBN:' 0-8186-3492-8 the whole document
【非特許文献４】GOOSSENS G ET AL: "LOOP OPTIMIZATION IN REGISTER-TRANSFER SCHEDULING FOR DSP-SYSTEMS*" PROCEEDINGS OF THE DESIGN AUTOMATION CONFERENCE. LAS VEGAS, JUNE 25 - 29, 1989, PROCEEDINGS OF THE DESIGN AUTOMATION CONFERENCE (DAC), NEW YORK, IEEE, US, vo1. CONF. 26, 25 June 1989 (1989-06-25), pages 826-831, XP000145908 ISBN: 0-89791-310-8 the whole document
【非特許文献５】C. E. LeisersonおよびJ. B. Saxeの「RETIMING SYNCHRONOUS CIRCUITRY」第８節, Alogorithmica, 6(1):5-35, 1991
【発明の開示】
【課題を解決するための手段】
【００１０】
［概要］
本発明は、提案されたループ繰り返しスケジュールの有効性を判断する方法であって、オペレーションおよびオペレーション間のエッジを含む依存グラフを受け取るステップと、性能仕様を受け取るステップと、依存グラフのオペレーションに対する待ち時間の割り当てを受け取るステップと、すべての依存制約条件およびタイミング制約条件が性能仕様について満たされるような、依存グラフにおけるクロックサイクル境界の配置の存在を決定するステップと、を含む方法を含む。
【発明を実施するための最良の形態】
【００１１】
［詳細な説明］
従来の手法は、クロックサイクルの整数倍として表現されたオペレーション待ち時間を使用する。
その結果、反復サイクル待ち時間は控えめなものとなり、それによって、いくつかの候補の繰り返しスケジュールは、有効でないとして悲観的に却下されることになる。
本発明は、実時間の遅延（例えば、ナノ秒）として表現されたオペレーション待ち時間を使用して、同じクロック周期内の複数のフロー依存オペレーションのスケジューリングを可能にし、それによって、より小さな反復サイクル待ち時間を導出する。
これによって、より多くの候補の繰り返しスケジュールを有効にすることができ、より高い性能を有するループネストの繰り返しスケジューリングがもたらされる。
【００１２】
図２は、候補のループ繰り返しスケジューリングベクトル（λ）、開始間隔ＩＩ、およびクロックサイクルタイム（Ｔ）から得られたループ繰り返しスケジュールの有効性を判断するフロー図を示している。
ループ繰り返しスケジュールが有効であるということは、ループネストが候補のＩＩおよび候補のＴでλに従ってスケジューリングされた場合に、すべてのデータ依存関係およびタイミング制約条件を満たすことが可能であることを意味する。
元のループネストに対応する依存グラフは、ステップ２０１で入力として受け取られる。
通常、この依存グラフは、ノードとしての加算、乗算、減算等の複数のオペレーションと、ノードを相互接続してオペレーション間の依存関係を示すエッジとを含む。
ステップ２０２は、マクロセルライブラリを受け取るのに使用される。
ステップ２０３および２０４は、性能仕様、すなわち、繰り返し間隔（ＩＩ）およびクロックサイクル（Ｔ）をそれぞれ受け取るのに使用される。
ステップ２０５は、候補のループ繰り返しスケジューリングベクトル（λ）を受け取るのに使用される。
一実施の形態では、性能仕様は、開始間隔およびクロックサイクルを構成する。
マクロセルライブラリの各マクロセルは、概念的には、所定の１組のオペレーションを実行できる１組のハードウェア実施態様を表す。
本発明者等は、各マクロセルに１組の待ち時間を関連付ける。
これらの待ち時間は、多くの異なる方法で表現することができ、例えば、クロックサイクルタイムＴの整数倍として表現することもできるし、ナノ秒の単位の実時間遅延として表現することもできる。
好ましい実施の形態では、待ち時間は、＜Δｉｎ，ｐｄ，Δｏｕｔ＞の形の待ち時間タプルとして表現される。
各タプルは、マクロセルのハードウェア実施態様で実行されるオペレーションと関連付けられ、そのハードウェア実施態様がそのオペレーションを実行するのに要する時間に対応する。
より具体的には、Δｉｎは、入力信号が到着した時とこの信号がハードウェア実施態様の最初のラッチに達した時との間の遅延を指す。
パイプライン深度（ｐｄ）は、ハードウェア実施態様におけるラッチのステージ数である。
最後に、Δｏｕｔは、信号がハードウェア実施態様の最終のラッチを出発した時とその信号が出力に到着した時との間の遅延を指す。
ΔｉｎおよびΔｏｕｔはナノ秒の単位で表現される。
パイプライン深度は整数≧０である。
パイプライン深度が０である場合、待ち時間タプルは＜Δｔｈｒｕ＞としてコンパクトに記載することができる。
＜Δｔｈｒｕ＞は、ハードウェア実施態様の入力から出力に向かう信号の遅延を表す。
マクロセルライブラリは、或る組のオペレーションを構成する１組のハードウェア実施態様を表す。
例えば、加算器マクロセルは、加算器のハードウェア実施態様の複数の表現を表すことができる。
上述したように、マクロセルライブラリは、さまざまなハードウェア実施態様に関連付けられたタプルを含む。
【００１３】
ステップ２０６では、待ち時間が、依存グラフに含まれる各オペレーションに割り当てられる。
好ましい実施の形態では、ループ依存グラフの各オペレーションは、このオペレーションを実行できるライブラリ内のすべてのマクロセルの中で最も高速のハードウェア実施態様に対応する待ち時間タプルに関連付けられる。
これは、オペレーションｏｐについては＜Δｉｎ，ｏｐ，ｐｄｏｐ，Δｏｕｔ，ｏｐ＞と表記することができる。
一実施の形態では、ｐｄ１＜ｐｄ２またはｐｄ１＝ｐｄ２、かつ、Δｉｎ１≦Δｉｎ２、かつ、Δｏｕｔ１≦Δｏｕｔ２である場合に限って、待ち時間タプル＜Δｉｎ１，ｐｄ１，Δｏｕｔ１＞を有するハードウェア実施態様は、待ち時間タプル＜Δｉｎ２，ｐｄ２，Δｏｕｔ２＞を有する別のハードウェア実施態様よりも遅くないとみなされる。
マクロセルのタプルの組は、全順序関係ではなく、半順序関係のみを形成することができる。
例えば、＜０．２，１，０．６＞と＜０．４，１，０．５＞は順序付けられない。
【００１４】
ステップ２０７では、あらゆる依存エッジｅのオメガが、λＴ・ｄとして計算される。
ここで、ｄは、所与の依存グラフにおけるｅの繰り返し距離ベクトルである。
ステップ２０８は、依存制約条件およびタイミング制約条件が、指定された性能について満たされるような、依存グラフのオペレーションおよびエッジにおけるクロックサイクル境界の配置の存在を決定する。
依存制約条件は、各反復サイクルＣを巡って配置されたクロックサイクル境界の個数がＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ）に等しい場合に満たされる。
ここで、Ｄｉｓｔａｎｃｅ（Ｃ）は、Ｃにおけるエッジのオメガの合計である。
タイミング制約条件は、連続したクロックサイクル境界とクロックサイクル境界との間の最大遅延がＴ以下である場合に満たされる。
このような配置が存在する場合には、ステップ２０８は「有効」出力を返し、存在しない場合には、ステップ２０８は「非有効」出力を返す。
【００１５】
また、図２に示す本発明の実施の形態は、入力された候補のスケジューリングベクトル（ステップ２０５）、入力された開始間隔（ステップ２０３）、および入力されたクロックサイクルタイム（ステップ２０４）によって提案された繰り返しスケジュールの比較コストを求めることにも使用することができる。
この比較コストの実施の形態では、ステップ２０８は、依存グラフのエッジ上に、クロックサイクル境界の配置を生成することができ、この配置を使用して、提案された繰り返しスケジュールに関連した結果のハードウェアのコストを見積もることができる。
一実施の形態では、このコストは、その配置によって与えられたクロックサイクル境界ビット数の合計に等しい。
依存エッジ上のクロックサイクル境界の配置に対応するクロックサイクル境界ビット数は、依存エッジのビット幅に等しい。
【００１６】
図３は、反復サイクルの列挙を使用して、λ、ＩＩ、およびＴから得られたループ繰り返しスケジュールの有効性を判断する方法のフロー図である。
図３は、図２で説明した本発明の一実施の形態を示している。
ここで、サイクルの列挙は、λ、ＩＩ、およびＴから得られたループ繰り返しスケジュールの有効性を判断するのに使用される。
図３のステップ２０１〜２０７は、図２のステップ２０１〜２０７と同一である。
ステップ３０１では、依存グラフの反復サイクルが列挙されて検査される。
ステップ３０２では、各反復サイクルＣについて、その反復サイクルのオペレーションおよびエッジに沿ったクロックサイクル境界の配置が、次の条件を満たすように決定される。
すなわち、（ｉ）Ｄｉｓｔａｎｃｅ（Ｃ）をＣにおけるエッジのオメガの合計とすると、反復サイクルＣを巡って配置されたクロックサイクル境界の個数がＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ）に等しくなるように、かつ、（ｉｉ）連続したクロックサイクル境界とクロックサイクル境界との間の最大遅延がＴ以下となるように決定される。
異なる実施の形態では、追加条件も満たすように要求することができる。
この追加条件とは、クロックサイクル境界が、他の反復サイクルの解析のために事前に配置された場合に、それらクロックサイクル境界を反復サイクルＣの解析で尊重しなければならないという条件である。
【００１７】
図３のステップ３０２の好ましい実施の形態では、反復サイクルＣのオペレーションおよびエッジは、Ｃの或るオペレーションから開始して依存順序で検査される。
そして、クロックサイクル境界は、その待ち時間タプルのあらゆるパイプラインステージ（ｐｄ）のオペレーションに配置されるか、あるいは、クロックサイクル境界は、もしあれば、Ｃにおいて最も近時に配置されたクロックサイクル境界から、エッジが入って行くオペレーションへの最大遅延がＴを超えるたびにエッジに配置される。
また、クロックサイクル境界は、パイプライン化されていないマルチサイクルオペレーション、すなわち、その待ち時間が＜Δｔｈｒｕ，ｏｐ＞の形を有するオペレーションに配置することもできる。
ここで、Δｔｈｒｕ，ｏｐはＴよりも大きい。
クロックサイクル境界は、２つのオペレーションを連鎖できる場合に当該２つのオペレーション間のエッジには配置できないことに留意されたい。
オペレーションの出力遅延と、そのオペレーションが入って行くオペレーションの入力遅延との合計が、入力されたクロックサイクルタイムＴ以下である場合に、演算子の連鎖が発生し得る。
Ｃを巡って配置されたクロックサイクル境界の総数（Ｎ）が≦ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ）である場合、ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ）−Ｎ個のクロックサイクル境界を、反復サイクルＣに沿ったエッジのいずれかに追加した配置することができる。
次に、Ｃを巡って配置されたクロックサイクル境界の総数がＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ）に等しく、かつ、Ｃに沿って配置された連続したすべてのクロックサイクル境界とクロックサイクル境界との間の最大遅延がＴ以下である場合に、反復サイクルＣについて配置が発見されたと言われ、そうでない場合には、反復サイクルＣについて配置は発見されていない。
【００１８】
配置がステップ３０２で発見されなかった場合には、ステップ３０３が「非有効」出力を返し、配置が存在しない場合には、ステップ３０４が行われる。
ステップ３０４は、さらに別の未検査の反復サイクルがあるかどうかをチェックして調べる。
さらに別の未検査の反復サイクルがある場合には、ステップ３０１が再び行われる。
さらに別の未検査の反復サイクルが存在しない場合には、「有効」出力が返される。
【００１９】
図４は、図３のフロー図を使用して配置されたクロックサイクル境界を有する図１Ｂの依存グラフである。
図４は、図３の方法を例示する一例を示している。
この例では、図３のステップ２０１で入力されて受け取られた依存グラフが、図１Ｂに示す依存グラフとなる。
ステップ２０２（図３）のマクロセルライブラリは、乗算（×）オペレーション用のタプル＜１．６ｎｓ，２，０．６ｎｓ＞および＜０．３ｎｓ，３，０．２ｎｓ＞と、加算（＋）オペレーション用のタプル＜１．２ｎｓ＞および＜０．１ｎｓ，１，０．１ｎｓ＞を含む。
ＩＩは３であり（図３のステップ２０３）、λ＝［１００  １］Ｔであり（図３のステップ２０５）、Ｔ＝２．０ｎｓである（図３のステップ２０４）。
ステップ２０６では、マクロセルライブラリからの最も高速のマクロセルに関連付けられた待ち時間が、各オペレーションに割り当てられ、その結果、＜１．６ｎｓ，２，０．６ｎｓ＞タプルは×オペレーションに割り当てられ、＜１．２ｎｓ＞タプルは＋オペレーションに割り当てられる。
＜０．３ｎｓ，３，０．２ｎｓ＞のｐｄ＝３は、＜１．６ｎｓ，２，０．６ｎｓ＞のｐｄ＝２よりも遅い×オペレーションを示すので、×用のタプルが選択されている。
同様に、タプル＜１．２ｎｓ＞のｐｄ＝０は、＋オペレーション用のタプル＜０．１ｎｓ，１，０．１ｎｓ＞のｐｄ＝１よりも小さい。
【００２０】
ステップ２０７では、各エッジについてオメガが計算される。
繰り返し距離ベクトルｄの注釈が付けられたエッジのオメガは内積λＴ・ｄである。
この関係を使用すると、エッジ１０７のオメガは、［１００  １］・［０  １］Ｔ＝１となる。
同様に、エッジ１０８のオメガは、［１００  １］・［１  −９９］Ｔ＝１となる。
他のすべてのエッジのオメガは、その距離ベクトルｄが［０  ０］Ｔに等しいので、０となる。
ステップ３０１では、反復サイクルＣ１およびＣ２が個別に検査される。
ステップ３０２は、反復サイクルＣ１を巡るクロックサイクル境界の配置を決定する。
反復サイクルＣ１を巡って配置できるクロックサイクル境界の最大数は、ＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ１）、すなわち３×（０＋１）＝３に等しい。
反復サイクルＣ１を巡るクロックサイクル境界の配置は次のように決定される。
×オペレーション（オペレーション１０４）から開始して、クロックサイクル境界４０１および４０２が、×オペレーションの内部パイプラインステージに対応するように配置される。
タプルによって定義されるように、×オペレーションは２のパイプライン深度を有する。
×オペレーションおよび＋オペレーションが連鎖できるかどうかを判断する際に、＋オペレーション（オペレーション１０５）のΔｉｎが、×オペレーションのΔｏｕｔに加算される。
タプルから、１．２ｎｓが０．６ｎｓに加算され、その結果、１．８ｎｓの値になる。
１．８ｎｓはＴ（２．０ｎｓである）よりも小さく、その結果、クロックサイクル境界はこのエッジには必要とされない。
次に、×オペレーションも、連鎖に追加するように試みられるが、最大遅延が、Δｏｕｔ，×＋Δｉｎ，＋＋Δｉｎ，×＝０．６＋１．２＋１．６＝３．４ｎｓに等しく、これはＴを超える。
したがって、クロックサイクル境界４０３がエッジ１０７に配置される。
反復サイクルＣ１では、以下の双方の条件が満たされている。
すなわち、Ｃ１（＝３）を巡って配置されたクロックサイクル境界の個数がＩＩ×Ｄｉｓｔａｎｃｅ（Ｃ１）（＝３×（０＋１）＝３）に等しいこと、連続したクロックサイクル境界とクロックサイクル境界との間の最大遅延≦Ｔであることが満たされている。
したがって、ステップ３０３は、反復サイクルＣ１について配置が存在すると判断する。
同様に、これらの条件は、クロックサイクル境界４０４をエッジ１０８に配置することによって、反復サイクルＣ２についても満たされる。
したがって、ステップ３０４では、ループ繰り返しスケジュールが有効であるとの判断が行われる。
【００２１】
また、図３の本発明の実施の形態は、入力された候補のスケジューリングベクトル（ステップ２０５）、入力された開始間隔（ステップ２０３）、および入力されたクロックサイクルタイム（ステップ２０４）によって提案された繰り返しスケジュールの比較コストを求めることにも使用することができる。
ここで、ステップ３０２が、各反復サイクルＣのエッジにクロックサイクル境界の配置を生成すると、これらの配置を組み合わせて、依存グラフのエッジにクロックサイクル境界の配置を形成することができる。
この結果の配置は、提案された繰り返しスケジュールに関連付けられた結果のハードウェアのコストを見積もるのに使用することができる。
【００２２】
図５は、リタイミングを使用して、λ、ＩＩ、およびＴから得られたループ繰り返しスケジュールの有効性を判断する方法のフロー図を示している。
図５は、図２で説明した本発明の別の実施の形態を示している。
ここで、リタイミングは、λ、ＩＩ，およびＴから得られたループ繰り返しスケジュールの有効性を判断するのに使用される。
図５のステップ２０１〜２０７は、図２のステップ２０１〜２０７と同一である。
ステップ５０１では、依存グラフが同期回路に変換される。
この同期回路では、オペレーションは、組み合わせノード、配線、およびレジスタの組として表され、エッジは、配線およびレジスタとして表される。
この変換は次のように行われる。
割り当てられた待ち時間タプルがΔｔｈｒｕ，ｏｐ（すなわち、０のパイプライン深度を有する）であるオペレーションの場合、そのオペレーションは、同期回路グラフでは、遅延＝Δｔｈｒｕ，ｏｐを有する組み合わせノードとしてモデル化される。
＜Δｉｎ，ｏｐ，１，Δｏｕｔ，ｏｐ＞の形の待ち時間を割り当てられたオペレーションは、同期回路グラフでは、配線により直列に接続された３つの組み合わせノードの組としてモデル化される。
第１の組み合わせノードには、遅延＝Δｉｎ，ｏｐが割り当てられる。
第２の組み合わせノードには、遅延＝Ｔが割り当てられる。
第３の組み合わせノードには、遅延＝Δｏｕｔ，ｏｐが割り当てられる。
これに加えて、第１のノードと第２のノードとの間に配置されたレジスタ。
パイプライン深度ｐｄが１よりも大きい＜Δｉｎ，ｏｐ，ｐｄ，Δｏｕｔ，ｏｐ＞の形の待ち時間を割り当てられたオペレーションは、同期回路グラフでは、配線によって直列に接続されたｐｄ＋１個の組み合わせノードの組としてモデル化される。
最初の組み合わせノードには、遅延＝Δｉｎ，ｏｐが割り当てられる。
最後の組み合わせノードには、遅延＝Δｏｕｔ，ｏｐが割り当てられる。
ｐｄ−１個の他のすべての中間の組み合わせノードには、遅延＝Ｔが割り当てられる。
さらに、依存グラフの各エッジは、同期回路では、ｗ（ｅ）個のレジスタを含む配線になる。
ここで、ｗ（ｅ）＝ＩＩ×λ・ｄｅである。
この方法論を使用すると、依存グラフは、組み合わせ回路素子を表すノードから成る同期回路に変換されている。
この組み合わせ回路素子は、０または１つ以上のレジスタを含む配線と接続され、関連した遅延を有するものである。
【００２３】
ステップ５０２では、結果の回路が、指定されたＴを満たすように、同期回路がリタイミングされる。
リタイミングはすでに知られた技法であり、C. E. LeisersonおよびJ. B. Saxeの「RETIMING SYNCHRONOUS CIRCUITRY」, Alogorithmica, 6(1):5-35, 1991の第４節から第６節を参照されたい。
この文献は、この引用によって、その全内容が参照により本明細書に援用される。
この技法では、所与の回路の所与のクロック周期を満たすために、回路の全体的な機能的振る舞いが保存されるように、レジスタが、その回路の或るポイントに追加され、他のポイントから除去される。
【００２４】
ステップ５０３では、リタイミングの解が存在するかどうかについての判断が行われる。
解が存在する場合には、そのループ繰り返しスケジュールは有効であり、そうでない場合には、そのループ繰り返しスケジュールは有効ではない。
【００２５】
図６Ａは、図５のフロー図を図１Ｂの依存グラフに適用することによって導出された同期回路である。
図６は、図５の方法を例示する一例を示している。
この例では、図５のステップ２０１で入力されて受け取られた依存グラフが、図１Ｂに示す依存グラフとなる。
ステップ２０２（図５）のマクロセルライブラリは、乗算（×）オペレーション用のタプル＜１．６ｎｓ，２，０．６ｎｓ＞および＜０．３ｎｓ，３，０．２ｎｓ＞と、加算（＋）オペレーション用のタプル＜１．２ｎｓ＞および＜０．１ｎｓ，１，０．１ｎｓ＞を含む。
ＩＩは３であり（図５のステップ２０３）、λ＝［１００  １］Ｔであり（図５のステップ２０５）、Ｔ＝２．０ｎｓである（図５のステップ２０４）。
ステップ２０６では、マクロセルライブラリからの最も高速のマクロセルに関連付けられた待ち時間が、各オペレーションに割り当てられ、その結果、＜１．６ｎｓ，２，０．６ｎｓ＞タプルは×オペレーションに割り当てられ、＜１．２ｎｓ＞タプルは＋オペレーションに割り当てられる。
＜０．３ｎｓ，３，０．２ｎｓ＞のｐｄ＝３は、＜１．６ｎｓ，２，０．６ｎｓ＞のｐｄ＝２よりも遅い×オペレーションを示すので、×用のタプルが選択されている。
同様に、タプル＜１．２ｎｓ＞のｐｄ＝０は、＋オペレーション（オペレーション１０５）用のタプル＜０．１ｎｓ，１，０．１ｎｓ＞のｐｄ＝１よりも小さい。
ステップ２０７では、各エッジについてオメガが計算される。
繰り返し距離ベクトルｄの注釈が付けられたエッジのオメガは内積λＴ・ｄである。
この関係を使用すると、エッジ１０７のオメガは、［１００  １］・［０  １］Ｔ＝１となる。
同様に、エッジ１０８のオメガは、［１００  １］・［１  −９９］Ｔ＝１となる。
他のすべてのエッジのオメガは、その距離ベクトルｄが［０  ０］Ｔに等しいので、０となる。
ステップ５０１では、加算オペレーション（オペレーション１０５）が、１．２ｎｓの遅延を有する図６Ａの組み合わせノード６０１としてモデル化される。
これに加えて、乗算オペレーション（図１Ｂのオペレーション１０４）は、３つのノードとしてモデル化される。
ノード６０２は、乗算器の入力ステージに対応し、１．６ｎｓの待ち時間を有する。
ノード６０３は、乗算器の単一の内部パイプラインステージに対応し、Ｔ＝２．０ｎｓの待ち時間が割り当てられる。
ノード６０４は、乗算器の出力ステージに対応し、０．６ｎｓの待ち時間を有する。
次に、各エッジ６０５および６０６のレジスタの個数が、ｗ（６０５）＝ＩＩ×λ・ｄ６０５およびｗ（６０６）＝ＩＩ×λ・ｄ６０６によって求められる。
例えば、エッジ（７０６）＝３×［１００  １］Ｔ・［１  −９９］＝３個のレジスタである。
図６Ａは変換された同期回路を示している。
【００２６】
図６Ｂは、図６Ａに対応するリタイミングされた同期回路である。
ステップ５０２では、結果の回路がＴを満たすように、図６Ａの同期回路がリタイミングされる。
図６Ｂは、リタイミングに成功した後の回路を示している。
リタイミング問題では、各パイプラインエッジ６０７および６０８はレジスタを含まなければならない。
これらのレジスタは、乗算オペレーションの内部パイプラインステージまたは内部ラッチステージに対応する。
リタイミングは、これらの判定基準を使用して、レジスタを回りに移動させ、その結果、図６Ｂの回路図になる。
図６Ｂが示すように、バックエッジ６０５および６０６のそれぞれからの３つのレジスタの１つが、６０２頂点を通って移動されており、バックエッジ６０５および６０６のそれぞれからの３つのレジスタの第２のレジスタが、６０２頂点および６０３頂点を通って移動されている。
これによって、タイミング制約条件を満たすことが確保される。
図６Ｂが示すように、あらゆるエッジは、次に０または１つ以上のレジスタを有する（換言すると、どのエッジも負のレジスタを含まない）。
これに加えて、図６Ｂのレジスタ間のパス遅延は、指定されたクロック周期以下の遅延を有する。
したがって、リタイミング問題の解が発見されており、ステップ５０３は「有効」を返す。
【００２７】
図５の実施の形態は、入力された候補のスケジューリングベクトル（ステップ２０５）、入力された開始間隔（ステップ２０３）、および入力されたクロックサイクルタイム（ステップ２０４）によって提案された繰り返しスケジュールの比較コストを求めることにも使用することができる。
ここで、ステップ５０２が、ステップ５０１の同期回路のリタイミングに成功できると、入力された依存グラフにおけるエッジ上のクロックサイクル境界の配置は、リタイミングの結果の回路から直接導出することができる。
一実施の形態では、入力された依存グラフにおけるエッジ上のクロックサイクル境界の個数は、リタイミングされた回路における対応する配線上のレジスタの個数に等しい。
この配置は、提案された繰り返しスケジュールに関連付けられた結果のハードウェアのコストを見積もるのに使用することができる。
ステップ５０２の異なる実施の形態では、同期回路は、Ｔを満たすようにリタイミングされ、最小限のレジスタビット数を有する。
このリタイミングの定式化もすでに知られており、C. E. LeisersonおよびJ. B. Saxeの「RETIMING SYNCHRONOUS CIRCUITRY」, Alogorithmica, 6(1):5-35, 1991の第８節を参照されたい。
この技法では、所与の回路の所与のクロック周期を満たすために、回路の全体的な機能的振る舞いが保存されるように、また、レジスタの全ビット数を最小にするために、レジスタが、その回路の或るポイントに追加され、他のポイントから除去される。
【図面の簡単な説明】
【００２８】
【図１Ａ】ｎ＝２の場合の深さｎのネストしたループのコードフラグメントを示す図である。
【図１Ｂ】図１Ａのネストしたループのコードフラグメントに対応する依存グラフを示す図である。
【図１Ｃ】図１Ａのネストしたループのコードフラグメントおよび図１Ｂの依存グラフに対応する繰り返し空間およびスケジューリングベクトルを示す図である。
【図２】ループ繰り返しスケジューリングベクトル（λ）、開始間隔ＩＩ、およびクロックサイクルタイム（Ｔ）から得られたループ繰り返しスケジュールの有効性を判断する方法のフロー図である。
【図３】反復サイクルの列挙を使用して、λ、ＩＩ、およびＴから得られたループ繰り返しスケジュールの有効性を判断する方法のフロー図である。
【図４】図３のフロー図を使用して配置されたクロックサイクル境界を有する図１Ｂの依存グラフを示す図である。
【図５】リタイミングを使用して、λ、ＩＩ、およびＴから得られたループ繰り返しスケジュールの有効性を判断する方法のフロー図である。
【図６Ａ】図５のフロー図を図１Ｂの依存グラフに適用することによって導出された同期回路を示す図である。
【図６Ｂ】図６Ａに対応するリタイミングされた同期回路を示す図である。
【符号の説明】
【００２９】
１０４，１０５・・・オペレーション，
１０７，１０８・・・エッジ，
４０１〜４０４・・・クロックサイクル境界，
６０２〜６０４・・・ノード，
６０５，６０８・・・エッジ，
６０２，６０３・・・頂点，
【図１Ａ】
2006502501.tif 000003
【図１Ｂ】
2006502501.tif 000004
【図１Ｃ】
2006502501.tif 000005
【図２】
2006502501.tif 000006
【図３】
2006502501.tif 000007
【図４】
2006502501.tif 000008
【図５】
2006502501.tif 000009
【図６Ａ】
2006502501.tif 000010
【図６Ｂ】
2006502501.tif 000011
【国際調査報告】
2006502501.tif 000012
2006502501.tif 000013
2006502501.tif 000014