(57)【要約】ループ本体の連続的反復の中で入力値を処理し出力値を生成するループ本体を含み、出力値がループ本体に結合される循環ノードによって捉えられ、さらに、ループ本体に結合される、最終のループ反復を判断するループ有効ノードと、循環ノードに結合される出力値記憶ノードとを含み、出力値記憶ノードが、ループ有効ノードが最終のループ反復が起こったと判断した後生成される出力値を無視する、制御フローデータフローグラフのパイプライン化されたループ構造。さらに、ループ本体の連続的反復の中で入力値を処理して出力値を生成するループ本体を含み、出力値がループ本体に結合される循環ノードによって捉えられ、さらに、循環ノードに結合されるループドライバノードを含み、ループドライバノードがループ本体の各反復に対して周期を設定する、制御フローデータフローグラフのパイプライン化されたループ構造。【特許請求の範囲】
【請求項１】
制御フローデータフローグラフのパイプライン化されたループ構造であって、
ループ本体の連続的反復の中で入力値を処理し出力値を生成するループ本体を含み、前記出力値は前記ループ本体に結合される循環ノードに捉えられ、前記構造はさらに、
前記ループ本体に結合される、最終のループ反復を判断するループ有効ノードと、
前記循環ノードに結合される出力値記憶ノードとを含み、前記出力値記憶ノードは、ループ有効ノードが前記最終のループ反復が起ったと判断した後生成される出力値を無視する、パイプライン化されたループ構造。
【請求項２】
前記ループ有効ノードは、前記最終のループ反復が起ったと判断するとループ有効終了信号を出力する、請求項１に記載のパイプライン化されたループ構造。
【請求項３】
前記ループ有効ノードは、前記最終のループ反復が起った後前記ループが再開されるまで各ループ反復において前記ループ有効終了信号を出力する、請求項２に記載のパイプライン化されたループ構造。
【請求項４】
前記ループ有効終了信号はデータビットを含む、請求項２に記載のパイプライン化されたループ構造。
【請求項５】
前記ループ有効ノードおよび前記出力値記憶ノードに結合される終了ノードを含む、請求項１に記載のパイプライン化されたループ構造。
【請求項６】
前記終了ノードは、前記ループ有効ノードからループ有効終了信号を受取るための終了入力を含む、請求項５に記載のパイプライン化されたループ構造。
【請求項７】
前記終了ノードは、記憶ノード終了信号を前記出力値記憶ノードに送るための終了出力を含む、請求項６に記載のパイプライン化されたループ構造。
【請求項８】
前記循環ノードに結合されるループドライバノードを含み、前記ループドライバノードは前記ループ本体の各反復に周期を設定する、請求項１に記載のパイプライン化されたループ構造。
【請求項９】
クロックレイテンシは、前記ループドライバノードに入力される周期値に基づく、請求項８に記載のパイプライン化されたループ構造。
【請求項１０】
制御フローデータフローグラフのパイプライン化されたループ構造であって、
ループ本体の連続的反復の中で入力値を処理し出力値を生成するループ本体を含み、前記出力値は前記ループ本体に結合される循環ノードに捉えられ、前記構造はさらに、
前記循環ノードに結合されるループドライバノードを含み、前記ループドライバノードは前記ループ本体の各反復に対して周期を設定する、パイプライン化されたループ構造。
【請求項１１】
前記ループドライバノードは、ループが開始していることを前記循環ノードに告げるためのCIRC_TRIGGER信号を出力する、請求項１０に記載のパイプライン化されたループ構造。
【請求項１２】
前記ループドライバノードは、ループの開始をトリガするためのSTART信号を出力する、請求項１０に記載のパイプライン化されたループ構造。
【請求項１３】
前記ループドライバノードは、リセットパルスを必要とするノードの状態をクリアする
ためのLOOP_STARTING信号を出力する、請求項１０に記載のパイプライン化されたループ構造。
【請求項１４】
前記ループドライバノードは、値をロードするよう定期的入力ノードに告げるためのLEADING信号を出力する、請求項１０に記載のパイプライン化されたループ構造。
【請求項１５】
周期値は、前記パイプライン化されたループ構造におけるループ運搬される最長のスカラサイクルの周期に等しい、請求項１０に記載のパイプライン化されたループ構造。
【請求項１６】
前記周期は、前記ループドライバノードに入力される周期値に基づく、請求項１０に記載のパイプライン化されたループ構造。
【請求項１７】
前記ループ本体に結合される、最終のループ反復を判断するループ有効ノードを含む、請求項１０に記載のパイプライン化されたループ構造。
【請求項１８】
前記ループ有効ノードは、前記最終のループ反復が起ったと判断するとループ有効終了信号を出力する、請求項１７に記載のパイプライン化されたループ構造。
【請求項１９】
前記循環ノードに結合される出力値記憶ノードを含む、請求項１８に記載のパイプライン化されたループ構造。
【請求項２０】
前記出力値記憶ノードは、前記ループ有効ノードが前記最終のループ反復が起ったと判断した後生成される出力値を無視する、請求項１９に記載のパイプライン化されたループ構造。
【請求項２１】
前記ループ有効ノードおよび前記出力値記憶ノードに結合される終了ノードを含む、請求項２０に記載のパイプライン化されたループ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
関連特許出願との相互参照
本発明は、本発明の譲受人であるコロラド（Colorado）州、コロラド・スプリングス（Colorado Springs）のエス・アール・シィ・コンピューターズ・インコーポレイテッド（SRC Computers, Inc.）に譲渡された、２００２年１０月３１日出願の米国特許出願連続番号第１０／２８５，２９９号「高級プログラミング言語のプログラムをハイブリッド計算プラットフォームのための統一された実行可能なプログラムに変換するためのプロセス」（" Process For Converting Programs In High-Level Programming Languages To A Unified Executable For Hybrid Computing Platforms "）の主題に関連する主題を含み、その開示はここに引用により援用される。
【０００２】
著作権表示／許可
この特許文献の開示の一部には、著作権保護の対象となる資料が含まれる。著作権所有者は、米国特許商標局の特許ファイルまたは特許記録に現われるように、特許開示の特許文献の何人による複製にも異議を唱えないが、それ以外ではいかなる著作権をも保有する。以下の表示は、適用可能であれは図面を含む以下に記載のソフトウェアおよびデータに適用される。(C)２００２  エス・アール・シィ・コンピューターズ・インコーポレイテッド（SRC Computers, Inc.)。
【０００３】
発明の背景
発明の分野
本発明は、再構成可能なハードウェアコンパイラによって作り出される、パイプライン化されたループ構造に関する。より具体的には、本発明は、数が変動するループサイクルおよび長さが変動するクロックレイテンシを有する、パイプライン化されたループ構造のコンパイルに関する。
【背景技術】
【０００４】
関連する背景
命令プロセッサは処理能力が急速に向上し続けているため、かつては専らスーパーコンピュータによってなされていたコンピュータインテンシブな計算に益々頻繁に使われている。しかしながら、たとえばコンピュータインテンシブな画像処理および流体力学的シミュレーションを含む、今日の命令プロセッサで実行するのは未だ現実的ではないコンピュータインテンシブなタスクが、依然存在する。
【０００５】
再構成可能な計算は、計算技術の中で益々注目を集める技術である。伝統的な汎用計算は、１つ以上の汎用プロセッサにおいて順次実行されるコンピュータコードによって特徴付けられる。再構成可能な計算は、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などの再構成可能なハードウェアを論理ルーチンを実行するようプログラミングすることを特徴とする。
【０００６】
再構成可能な計算によって、コンピュータインテンシブな処理において著しい性能の進歩がもたらされる。たとえば、再構成可能なハードウェアは従来の命令プロセッサよりさらに多くの並列処理およびパイプライン化の特性を有する論理構成でプログラミングされ得る。さらに、再構成可能なハードウェアは、プログラムによって割当てられたタスクを実行するのに非常に効率のよいカスタム論理構成でプログラミングされ得る。さらに、命令プロセッサと再構成可能なハードウェアとの間でプログラムの処理要件を分担すると、コンピュータの処理能力全体を向上させることができる。
【０００７】
たとえば、Ｃまたはフォートランなどの高級言語で書かれたソフトウェアプログラムは、ＭＡＰコンパイラのある再構成可能なハードウェアで実行可能なソフトウェアに変換され得る。高級言語のループ構造は、ＭＡＰコンパイラによって、再構成可能なハードウェアの並行処理およびパイプライン化の特性を発揮する形式に変換され得る。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
不運なことに、既存のＭＡＰコンパイラは、数ある要件の中でも、ループが終了する前のループ反復の回数が予め定められており、かつループの周期が１クロックであるようなすべてのループ構造のうち小さなサブセットにしか動作しない。したがって、ループが予定の反復数の後に終了してしまわず、かつループが１クロックより大きい周期を有するような、ループ構造をコンパイルできるコンパイラが依然として必要である。
【課題を解決するための手段】
【０００９】
発明の概要
したがって、本発明の１つの実施例は、制御フローデータフローグラフのパイプライン化されたループ構造であって、ループ本体の連続的反復の中で入力値を処理し出力値を生成するループ本体を含み、出力値は、ループ本体に結合される循環ノードによって捉えられ、上記構造はさらに、ループ本体に結合される、最終のループ反復を判断するループ有効ノードと、循環ノードに結合される出力値記憶ノードとを含み、出力値記憶ノードは、ループ有効ノードが最終のループ反復が起ったと判断した後生成される出力値を無視する。
【００１０】
本発明の他の実施例は、ループ本体の連続的反復の中で入力値を処理して出力値を生成するループ本体を含む、制御フローデータフローグラフのパイプライン化されたループ構造を含み、出力値はループ本体に結合される循環ノードによって捉えられ、さらに、循環ノードに結合されるループドライバノードを含み、ループドライバノードは、周期、すなわち連続した２つのループ反復の実行の間で起るクロックの回数を、ループに対して設定する。
【００１１】
追加的な新規な特徴が、一部は下記の説明に明示され、一部は下記の明細を考察することで当業者には明らかとなるか、または本発明の実施により学習されるであろう。本発明の特徴と利点とは、付随する請求項の中で特に指摘される、指示、組合せ、および方法によって認識され、会得されるであろう。
【発明を実施するための最良の形態】
【００１２】
発明の詳細な説明
単純なループ関数においては、ループは、固定した予定の回数を反復してから最終のループ反復の後停止する。対照的に、より複雑なループ関数は、固定した回数を反復した後終了するのではなく、条件が合うまで予測不可能な回数を反復し得る。これらのより複雑なループ関数は最終のループ反復の後も動き続け、そのため、終値の後に続く出力ではない、最終のループ反復出力値を出力記憶ノードが捉えることが困難になる。
【００１３】
本発明は、条件が合うまで予測不可能な回数を反復するループ関数を含む、パイプライン化されたループ構造、およびループのパイプライン化の方法を含む。本発明の１つの実施例は、各ループ反復について生成される情報を受け、その情報が最終のループ反復を指示するか否かを判断する、ループ有効ノードを含む。たとえば、各ループ反復について生成された情報はループ有効ノードによって処理され、ループの終了を要求する条件が満たされたか否かが判断される。条件が満たされると、ループ有効ノードは、ループからの次
の出力値が最終のループ反復出力値であることを、終了ノードおよび出力値記憶ノードなどの他のノードに知らせることができる。
【００１４】
多くのパイプライン化されたループ関数が、１反復につき１クロックよりも大きな周期をさらに必要とする。これらのループ関数と、１クロックサイクルにつき１入力値または１出力値の周波数でのみ動作するパイプライン化されたループ構造とは、互換性がなくてもよい。本発明では、ループ本体に入力される値と値の間で１以上のクロックサイクルが経過するよう周期を調整することができる、ループドライバノードが与えられる。本発明の１つの実施例において、ループドライバノードは周期値「Ｄ」を受入れ、Ｄ値はループ関数の入力および／または出力の間で経過するクロックサイクルの回数を表わす。
【００１５】
図１を参照すると、本発明による、パイプライン化されたループ構造１００の１つの実施例が示される。パイプライン化されたループ構造１００は、ロードスカラノード１０４および１０６とループドライバノード１０８とにループ関数の実行を開始するよう信号を送る、開始ノード１０２で始まる。ループドライバノード１０８は、次に、循環ノード１１０，１１２，１１４に、ロードスカラノード１０４および１０６から初期値をロードしてその値をループ本体１１６に示すよう信号を送る。ループ本体１１６の各反復において、循環ノード１１０，１１２，１１４は、ループ本体１１６のそれぞれの反復で生成される出力値を捉え、それらをループ本体１１６の次の反復のための入力値として送るよう準備する。
【００１６】
下記にさらに詳細に説明されるように、ループドライバノード１０８は「Ｄ」とラベル付けされた入力を受入れることができ、Ｄ値はループ反復の間に追加で起るクロックサイクルの回数を表わす。たとえば、Ｄ＝０の場合、１反復につき１クロックサイクルであり、Ｄ＝１の場合は１反復につき２クロックサイクルである。
【００１７】
Ｄ値はループ関数のすべての反復に対して固定されていてもよく、またはより複雑なループ関数動作においては、ループ反復間で変動してもよい。Ｄ値はプログラマによって手動で入力されてもよく、またはループ関数の分析に基づいて自動的に計算されてもよい。ループ関数が開始されると、ループドライバノード１０８は、パイプライン化されたループ構造１００において循環ノード１１０，１１２，１１４などの他のノードをアクティブにする速度を、Ｄ値を用いて決定する。
【００１８】
パイプライン化されたループ構造１００におけるループの終了は、循環ノード１１４と繋がっているループ有効ノード１１８によって開始できる。１つの実施例において、シングルビット値によって表わせるループ終了信号がループ有効ノード１１８に入力され、ループの終了を指示する条件が満たされたか否かが判断される。ループ有効ノード１１８は「無効」出力信号（「偽」信号とも呼ばれる）を循環ノード１１４に送り、ループ関数が再開されるまで無効な出力信号を送り続ける状態に自らをラッチすることができる。
【００１９】
循環ノード１１４がループ有効ノード１１８から無効な出力信号を受取った後、信号は終了ノード１２０に渡される。終了ノード１２０は次に出力値記憶ノード１２２，１２４をトリガして、ループ本体１１６の最終のループ反復からの最終のループ反復出力値を捉える準備ができる。この機構により、ループが最終反復の後にフリーランを続けたとしても、出力値記憶ノード１２２，１２４は最終のループ反復出力値を捉えることができる。
【００２０】
ループが終了し、最終のループ反復出力値が出力値記憶ノード１２２，１２４に格納されると、続いてそれらの値はラッチアンドノード１２６によってラッチされ、次に出力ノード１２８を介して分配される。パイプライン化されたループ構造１００において、終了ノード１２０はラッチアンドノード１２６にさらに結合され、出力値記憶ノード１２２，
１２４からいつ値を捉えるべきかをノード１２６に知らせることができる。
【００２１】
図２を参照すると、図１のループドライバノード１０８に含まれ得るタイミング信号のタイミング図が示される。CLOCK信号は、クロックサイクルの開始をトリガする、システムのクロック信号から与えられる入力である。START信号はループの開始をトリガする。この信号は開始ノード１０２から受取られる。CIRC_TRIGGER信号はループが開始していることを循環ノードに知らせる。この信号は、循環ノード１１０，１１２，１１４が初期値をロードするために用いる出力である。LOOP_STARTING信号は、リセットパルスを必要とするノードに、新たなループ実行のために状態をクリアするよう告げる。LEADING信号は初期値をロードするよう定期的入力ノードに告げる。最後に、ACTIVE_LAST信号が各反復の最後のクロックにおいてハイになる。この信号を用いて、パイプライン化されたループ構造１００のノードが有効な入力を有することをノードに示す。
【００２２】
ループ運搬されるスカラ変数は、制御フローデータフローのパイプライン化されたループ構造において周期を生成することができる。周期はループ反復間のクロックサイクル数を増やし、それにより、次にＤ値を上げて、ループ本体と循環ノードとが同期して正しいループ本体出力値を確実に捉え、新たな各ループ反復を開始できるようにする必要がある。
【００２３】
図３は、パイプライン化されたループ構造３００の部分の例を示し、そこでループドライバノード３０８のＤ値は、少なくとも１ループ反復につき追加の４クロックサイクルを表わす４に、設定されなければならない。上記の図１と同様に、パイプライン化されたループ構造３００は、ロードスカラノード３０４，３０６およびループドライバノード３０８に信号を送る開始ノード３０２で、開始する。この例において、Ｄ＝４の値がループドライバノード３０８に入力されてループ構造の周波数を１ループ反復につき５クロックサイクルとする。Ｄ＝４の値は、ＭＵＬＴノード３１４で体現される乗算マクロの固有のクロックサイクルレイテンシに基づいて選択される。Ｄ＝４をループドライバノード３０８に入力することにより、循環ノード３１０，３１２は５クロックサイクル毎にＭＵＬＴノード３１４に値を入力する。
【００２４】
一般にＤ値は、パイプライン化されたループ構造における循環ノードの入力および出力の間の経路の最長のものに比例する。図３は、循環ノード３１０，３１２の出力がすべてＭＵＬＴノード３１４に送られ、その入力をＭＵＬＴノード３１４が直接ノード３１０，３１２に送り返す単純な例を示す。より複雑なループ関数と、それらのパイプライン化されたループ構造との例を次にいくつか示す。
【００２５】
図４は、１ループ反復につき４クロックサイクルのレイテンシを有する第１の関数（Ｆ１）ノード４１４、および１ループ反復につき６クロックサイクルのレイテンシを有する第２の関数（Ｆ２）ノード４１６がある、制御フローデータフローグラフのパイプライン化されたループ構造４００を示す。パイプライン化されたループ構造４００は、ロードスカラノード４０４，４０６およびループドライバノード４０８に信号を送る開始ノード４０２で開始する。この例においてＤ値は、パイプライン化されたループ構造４００におけるループ関数のうち、最長のレイテンシに基づいて選択される。第２の関数（Ｆ２）ノードは１反復につき６クロックサイクルの最長レイテンシを有するので、Ｄ値は６である。循環ノード４１０，４１２は、Ｄ値に基づいてタイミングを取られるループドライバから信号を受取り、それにより７クロックサイクル毎に値を第１の関数（Ｆ１）ノード４１４および第２の関数（Ｆ２）ノード４１６に入力する。
【００２６】
図５は、循環ノード５１６，５１８，５２０，５２２，５２４とループ関数本体５２６，５２８，５３０，５３２、５３４，５３６，５３８，５４０との間に多くの循環経路を
有する、さらに複雑な、パイプライン化されたループ構造５００を示す。この例において、ループ関数５００の実行は、ロードスカラノード５０４，５０６，５０８，５１０，５１２とロードドライバノード５１４とに信号を送る開始ノード５０２で開始する。ループドライバノード５１４に入力されるＤ値は次の態様で決定され得る。
【００２７】
パイプライン化されたループ構造５００は、サイクルに関連するノードと関連しないノードとに分けられ得る、循環ノードを有する。サイクルに関連する循環ノードについて、パイプライン化されたループ構造における循環経路は次のように説明され得る。
【００２８】
１．Ｃ１→Ｄ１→Ｄ６→Ｃ１
２．Ｃ１→Ｄ０→Ｄ６→Ｃ１
３．Ｃ１→Ｄ２→Ｃ２→Ｃ３→Ｄ４→Ｄ６→Ｃ１
ここで、Ｃ０，Ｃ１，Ｃ２，Ｃ３およびＣ４は循環ノード５１６，５１８，５２０，５２２および５２４のそれぞれのラベルであり、Ｄ０，Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５，Ｄ６およびＤ７はループ関数ノード５２６，５２８，５３０，６３２，５３４，５３６，５３８および５４０のそれぞれのラベルである。
【００２９】
Ｄ値を決定する際、サイクルに関連しない循環ノードは無視してもよい。なぜならノードのすべての入力に遅延を挿入することでループ本体に押し込まれるからである。この例では循環（Ｃ４）ノード５２４はパイプライン化されたループ構造５００のサイクルに関連せず、Ｄ値を決定する際に無視される。
【００３０】
残りの循環（Ｃ０，Ｃ１，Ｃ２，Ｃ３）ノード５１６，５１８，５２０，５２２については、図６に示される表１のような表が作られ、値が１つの循環ノードから他の循環ノードへと移動するか、または同じ循環ノードに戻るのに、どのループ関数本体を通るかを示す。たとえばセルＣ０，Ｃ０は、値が循環（Ｃ０）ノード５１６から出て元の位置に戻るまでに通らなければならないループ関数本体を特定する。パイプライン化されたループ構造５００において、Ｃ０は元の位置に戻る循環経路を有しておらず、セルは空のまま残される。対照的に、値が循環（Ｃ１）ノード５１８から出て元の位置に戻るために通ることができる循環経路が存在し、この経路はセルＣ１，Ｃ１においてＤ１＋Ｄ６で表わされる。
【００３１】
Ｄ０からＤ６のループ関数本体の各々に対してクロックレイテンシが決定され、これらのレイテンシを表１に当てはめて、最長のレイテンシを有する循環経路が決定できる。最長のレイテンシ値を用いて次にＤの最小値が設定され、最小値はループドライバノード５１４に入力されて、パイプライン化されたループ構造５００全体の周期を決定する。
【００３２】
状態を持つノード：制御フローデータフローのパイプライン化されたループ構造において、ノードの状態をクリアし、各反復がいつ起るかをノードに告げ、ノードの入力がいつ有効であるかをノードに告げるなどの、状態を持つノードに関する問題を扱うために、状態を持つノードは追加的サポートを必要とする。図７は、ループドライバノード７０８の３個の信号がこの情報を伝えるためにどのよう用いられ得るかを示す。
【００３３】
図７に示されるパイプライン化されたループ構造７００の例は、状態を持つノード７１６の存在を除いては、他のパイプライン化されたループ構造の例と同様に見える。ループ関数は、ロードスカラノード７０４，７０６およびループドライバノード７０８に開始ノード７０２から信号を送らせることによって実行される。ループドライバノード７０８がループの周期により決定された速度で循環ノード７１０，７１２，７１４に活性化信号を送る間、ロードスカラノード７０４，７０６が循環ノード７１０，７１２，７１４に初期値をロードする。循環ノード７１０，７１２，７１４は１つ以上のループ本体（図示され
ない）に結合され、それは次に状態を持つノード７１６に結合される。
【００３４】
上述のように、状態を持つノード７１６に情報を伝えるために、ループドライバノード７０８によって３個の信号が与えられる。これらのうち最初の信号は「有効」信号と呼ばれ、ループドライバノード７０８に結合される循環ノード７１４によって状態を持つノード７１６に到達する。有効信号はさらに、状態を持つノードが条件式内にある場合、条件式を経ることができる。
【００３５】
ループ関数の中で条件がどのように構築されるかに依存して、有効な信号は状態を持つノード７１６から無視されてもよい。ノードを条件テストの中に置くのではなく、ノードに明示的な述語入力を与えることにより、状態を持つノードの条件が扱われると、有効信号は無視されてもよい。例示的に、４２より大きなアレイの値をすべて合計するためにアキュムレータを扱う場合の方法を２つ考える。
【００３６】
【数１】
2006510125.tif 000002
【００３７】
下記と比較する。
【００３８】
【数２】
2006510125.tif 000003
【００３９】
第２のアプローチでは、コンパイラによって構築されるループ構造は、条件付きデータフローを構築する必要がないのでより単純である。さらに、第１のアプローチでは条件式が真のときのみ値が「ｒｅｓ」に割当てられるのに対し、第２のアプローチでは、各反復において値が「ｒｅｓ」に割当てられる。したがって、アキュムレータが第２のアプローチによって構築されると、状態を持つノードに対する有効な信号入力は不要であり、信号は無視されてもよい。有効な信号が所望される場合、状態を持つノードは信号を受入れるために１ビット入力で設計されてもよい。
【００４０】
状態を持つノード７１６に対する第２の信号は、ノード内部の状態をクリアするのに用いられる「starting」信号である。この信号はloop_startings出力においてループドライバ７０８によって生成され得る。ループドライバ７０８からの信号が状態を持つノード７１６に到達する前に遅延を経る場合、状態を持つノード７１６はコードブロックの「code_block_reset」信号に接続されない。なぜなら、ループがコードブロックに入る際にブロックの以前の実行からフリーランを続けている可能性があり、「code_block_reset」信号が遅延を経ていないと「code_block_reset」信号を用いることによりノードがリセットし、コードブロックの以前の実行によって依然生じている値の処理を始める可能性があるか
らである。
【００４１】
状態を持つノード７１６に対する第３の信号入力は、各ループ反復において最後のクロックサイクルでハイになる信号である。この信号は元来はループドライバノード７０８から「active_last」信号として出たものであってもよい。状態を持つノード７１６はこの信号がハイになったのを見ると、入力に有効なデータがあると推定する。
【００４２】
通常は、状態を持つノード７１６はループ終了とは無関係である。ループの終了条件が満たされると、対応する結果が捉えられ、そしてループは動き続ける。しかし、ループのコードブロックが次回実行されるまで、状態を持つノード７１６がその状態を保持しなければならない場合もあり、ノードはループがいつ終了したのかを知る必要がある。この場合、マクロは「有効」入力を用い、「starting」信号を見てもリセットしない。なぜなら、その状態はコードブロック呼出の間保持されることになっているからである。
【００４３】
図８は状態を持つノード７１６に対して用いられ得る信号のタイミング図の例を示す。この例において、「有効」信号は第１の反復の間ハイである。なぜならループは少なくとも１つの反復を実行するボトムテストループだからである。以後、ハイの「有効」信号は、ループが未だ終了しておらず、ノードが条件内にあると、その条件付きの分岐がとられることを示す。「starting」信号はループが始まる前に１クロックの間ハイになり、状態を持つノード７１６の状態をクリアするのに用いられることができる。「active_last」信号は各ループ反復において最後のクロックサイクルでハイになり、ループが終了した後であってもこの動作を続ける。状態を持つノード７１６へのデータ入力は「active_last」信号がハイのとき有効と推定される。
【００４４】
「leading」信号は定期的入力ノードに適切な同期を与える。１クロックサイクル毎に新たな入力を受入れることができないノードもある。たとえばある整数乗算は、単一のオンチップ乗算機を再使用して３クロック毎にのみ入力を受入れることができる。この問題は、入力の集合とそれに対応する出力との間のクロック遅延の回数であるレイテンシの問題と直交する。ノードが１クロック毎に入力を受入れられない場合は入力が正しく整調された状態に置く必要があり、そこにはノードがいつ新たな入力を受けるかを確立する同期が存在する必要がある。これは「leading」信号によって与えられる関数であり、このようなノードの「valid in」入力に接続され得る。ループドライバノードのＤ値もさらに、少なくとも定期的入力ノードが正しく動作するのに十分な程度にループを遅らせるよう設定されなければならない。
【００４５】
本発明で用いられてもよい状態を持つノードには少なくとも２種類がある。１つの種類では、ノードのレイテンシはループの反復周期に拘らず（すなわちループドライバノードへのＤ入力の値に拘らず）一定である。他の種類では、状態を持つノードのレイテンシはループの反復周期に基づいて変動する。たとえば、出力の生成を開始する前にＮ個のデータアイテムを受ける状態を持つノードは、ループがループドライバノードによって遅くなる場合、第１の結果が生成される前により多くのクロックサイクルを消費する。状態を保つノードのこの種の動作は、その情報ファイルエントリによって特定される。ノード書込器はこのような状態を持つノードを書込むことを選択し、ループが遅くならない場合、すなわちＤ＝０の場合にのみノードが正しく機能するようにし、かつノードの情報ファイルエントリがその事実を特定しなければならない。
【００４６】
この明細書および付随する特許請求の範囲で使用される「備える」「備えた」「含む」および「含んだ」という用語は、記載される特徴、完全体、構成要素またはステップの存在を特定することを目的としたものであるが、その他１つ以上の特徴、完全体、構成要素、ステップまたは群の存在または追加を除外するものではない。
【図面の簡単な説明】
【００４７】
【図１】本発明の実施例による制御フローデータフローグラフのパイプライン化されたループ構造の例を示す図である。
【図２】ループ反復の間が２クロックサイクルであるループドライバノードのタイミング図の例を示す図である。
【図３】ループ運搬されるスカラサイクルを持つループを有する制御フローデータフローグラフのパイプライン化されたループ構造の例を示す図である。
【図４】２つ以上の循環ノードを用いるループ運搬されるスカラサイクルがあるループを有する制御フローデータフローグラフのパイプライン化されたループ構造の例を示す図である。
【図５】多くのループ運搬されるスカラサイクルを有する、制御フローデータフローグラフのパイプライン化されたループ構造の例を示す図である。
【図６】図５に示されるループ構造の、循環ノードの間の経路を表わすチャートの例を示す図である。
【図７】状態を持つノードを含む、制御フローデータフローグラフのパイプライン化されたループ構造の例を示す図である。
【図８】状態を持つノードマクロのタイミング図の例を示す図である。
【図１】
2006510125.tif 000004
【図２】
2006510125.tif 000005
【図３】
2006510125.tif 000006
【図４】
2006510125.tif 000007
【図５】
2006510125.tif 000008
【図６】
2006510125.tif 000009
【図７】
2006510125.tif 000010
【図８】
2006510125.tif 000011
【国際調査報告】
2006510125.tif 000012