(57)【要約】      （修正有）【課題】ハイブリッドハードウェアプラットフォームでの実行管理に関連したサポートコードを含む統一された実行可能要素を生成するために、高級言語標準に準拠して書込まれたコンピュータコードをコンパイルするためのシステムおよび方法の提供。【解決手段】上位レベルのドライバは、コンパイル段階で、生成されているＣＦＣ表現を、ハードウェア記述表現に処理され得る最適化されたパイプラインロジックを表わすハイブリッド制御フローデータフローグラフ表現に翻訳する。ドライバは、再構成可能なコンピュータのためのビットストリームを生成するために必要とされるネットリストファイルを生成する。コンパイルドライバからの出力を取得し、かつ命令プロセッサおよび再構成可能なプロセッサの双方で実行することのできる統一された実行可能要素を生成するためにすべての必要な構成要素を互いに結合するためのサポートを与える。【選択図】図１
2010146577.tif 000002
【特許請求の範囲】
【請求項１】
高級言語ソースコードを統一された実行可能要素に変換する方法であって、
当該高級言語ソースコードの再構成可能なハードウェア部分からオブジェクトファイルを生成するステップと、
当該オブジェクトファイルを当該統一された実行可能要素に統合するステップとを含む、方法。
【請求項２】
前記方法は、当該高級言語ソースコードを制御フローグラフ表現に変換するステップを含む、請求項１に記載の方法。
【請求項３】
前記方法は、当該制御フローグラフ表現を制御データフローグラフ表現に変換するステップを含む、請求項２に記載の方法。
【請求項４】
前記方法は、当該制御フローデータグラフを、命令プロセッサ部分および当該再構成可能なハードウェア部分に区分化するステップを含む、請求項３に記載の方法。
【請求項５】
前記方法は、当該再構成可能なハードウェア部分をハードウェア定義言語ファイルに変換するステップを含む、請求項１に記載の方法。
【請求項６】
前記方法は、当該ハードウェア定義言語ファイルを再構成可能なハードウェアビットストリームファイルに変換するステップを含む、請求項５に記載の方法。
【請求項７】
前記方法は、当該再構成可能なハードウェアビットストリームファイルを当該オブジェクトファイルに変換するステップを含む、請求項６に記載の方法。
【請求項８】
統一された実行可能要素を形成する方法であって、
高級言語ソースコードを制御フローグラフ表現に変換するステップと、
当該制御フローグラフ表現を制御データフローグラフ表現に変換するステップと、
当該制御データフローグラフを、命令プロセッサ部分および再構成可能なハードウェア部分に区分化するステップと、
当該制御データフローグラフの当該再構成可能なハードウェア部分をハードウェア定義言語部分に、および当該命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換するステップと、
当該ハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換するステップと、
当該再構成可能なハードウェアビットストリームを、命令プロセッサが読取ることのできるビデオストリームオブジェクトファイルに変換するステップと、
当該統一された実行可能要素を形成するために、当該ビットストリームオブジェクトファイルを当該命令プロセッサオブジェクトファイルに統合するステップとを含む、方法。
【請求項９】
統一された実行可能要素を形成するためのシステムであって、
制御データフローグラフデータを、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部を含む、システム。
【請求項１０】
前記システムは、高級言語を制御フローグラフ表現に変換するための高級言語コンバータを含む、請求項９に記載のシステム。
【請求項１１】
前記システムは、当該制御フローグラフ表現を当該制御データフローグラフデータに変換するための制御データフローグラフコンバータへの制御フローグラフを含む、請求項１
０に記載のシステム。
【請求項１２】
前記システムは、当該制御データフローグラフデータの当該再構成可能なハードウェア部分をハードウェア定義言語ファイルに変換するためのハードウェア定義言語コンバータへの制御データフローグラフを含む、請求項９に記載のシステム。
【請求項１３】
前記システムは、当該ハードウェア定義言語ファイルをビットストリームファイルに変換するためのビットストリームコンバータへのハードウェア定義言語を含む、請求項１２に記載のシステム。
【請求項１４】
前記システムは、当該ビットストリームファイルをビットストリームオブジェクトファイルに変換するためのオブジェクトファイルコンバータへのビットストリームを含む、請求項１３に記載のシステム。
【請求項１５】
前記システムは、当該ビットストリームオブジェクトファイルを当該統一された実行可能要素に統合するためのリンカを含む、請求項１４に記載のシステム。
【請求項１６】
前記システムはサポートハードウェアロジックモジュールを含む、請求項９に記載のシステム。
【請求項１７】
前記システムはユーザハードウェアロジックモジュールを含む、請求項９に記載のシステム。
【請求項１８】
前記システムはランタイムライブラリを含む、請求項９に記載のシステム。
【請求項１９】
前記システムは、命令プロセッサおよび再構成可能なハードウェアを含むハイブリッドコンピュータを含む、請求項９に記載のシステム。
【請求項２０】
前記再構成可能なハードウェアは、多重適応プロセッサ（ＭＡＰ）を含む、請求項１９に記載のシステム。
【請求項２１】
ハイブリッドで再構成可能なハードウェア命令プロセッサコンピュータで実行することのできる統一された実行可能要素を形成するためのシステムであって、前記システムは、
高級言語を制御フローグラフ表現に変換するための高級言語コンバータと、
当該制御フローグラフ表現を制御データフローグラフ表現に変換するための制御データフローグラフコンバータへの制御フローグラフと、
当該制御データフローグラフ表現を、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部と、
当該制御データフローグラフ表現の当該再構成可能なハードウェア部分を、ハードウェア定義言語ファイルに変換するためのハードウェア定義言語コンバータへの制御データフローグラフと、
当該ハードウェア定義言語ファイルをビットストリームに変換するためのビットストリームコンバータへのハードウェア定義言語と、
当該ビットストリームファイルをビットストリームオブジェクトファイルに変換するためのオブジェクトファイルコンバータへのビットストリームと、
当該ビットストリームオブジェクトファイルを当該統一された実行可能要素に統合するためのリンカとを含む、システム。
【請求項２２】
統一された実行可能要素の形成を引き起こすために中に実現されたコンピュータ読取可能プログラムコードを有するコンピュータ使用可能媒体を含み、当該コンピュータ読取可
能プログラムコードは、
コンピュータに、高級言語ソースコードを制御フローグラフ表現に変換させるためのコンピュータ読取可能プログラムコードと、
当該コンピュータに、当該制御フローグラフを制御データフローグラフに変換させるためのコンピュータ読取可能プログラムコードと、
当該コンピュータに、当該制御データフローグラフを命令プロセッサ部分および再構成可能なハードウェア部分に区分化させるためのコンピュータ読取可能プログラムコードと、
当該コンピュータに、当該制御データフローグラフの当該再構成可能なハードウェア部分をハードウェア定義言語部分に、および当該命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコードと、
当該コンピュータに、当該ハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換させるためのコンピュータ読取可能プログラムコードと、
当該コンピュータに、当該再構成可能なハードウェアビットストリームを命令プロセッサが読取ることのできるビットストリームオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコードと、
当該統一された実行可能要素を形成するために、当該コンピュータに、当該ビットストリームオブジェクトファイルを当該命令プロセッサオブジェクトファイルに統合させるためのコンピュータ読取可能プログラムコードとを含む、コンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
著作権表示／許可
この特許文献の開示の一部には、著作権保護の対象となる資料が含まれる。著作権所有者は、米国特許商標局の特許ファイルまたは特許記録に現われるように、特許開示の特許文献の何人による複製にも異議を唱えないが、それ以外ではいかなるすべての著作権を保有する。以下の表示は、適用可能であれは図面を含む以下に記載のソフトウェアおよびデータに適用される。(C)２００２  エス・アール・シィ・コンピューターズ・インコーポレイテッド（SRC Computers, Inc.)
発明の背景
発明の分野
本発明は一般的に、高級言語プログラムをハイブリッドの再構成可能なハードウェア命令プロセッサの計算環境で動作するように適合させることに関する。より特定的に、本発明は、高級言語プログラムをハイブリッドの再構成可能なハードウェア命令プロセッサコンピュータで実行することのできる統一された実行可能要素に変換することに関する。
【背景技術】
【０００２】
背景
命令プロセッサが処理能力を急速に向上させ続ける中で、命令プロセッサはかつてスーパーコンピュータのみによって行なわれていたコンピュータを多用する計算を行なうために用いられることが多くなった。しかしながら、たとえば、現代の命令プロセッサで行なうにはまだ実用的でない、数値計算のイメージ処理および流体力学的なシミュレーションを含むコンピュータを多用するタスクが存在する。
【０００３】
再構成可能な計算は、計算技術において関心の高まっている技術である。従来の汎用計算は、１つ以上の汎用プロセッサで順次実行されるコンピュータコードを特徴とする。再構成可能な計算は、フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ（Field Programmable Gate Arrays））等の再構成可能なハードウェアを論理ルーチンを実行するようにプログラムすることを特徴とする。
【０００４】
再構成可能な計算によって、コンピュータを多用する処理において著しい性能の進歩がもたらされる。たとえば、再構成可能なハードウェアは、従来の命令プロセッサと比較して高い並列性およびパイプライン化の特性を有する論理構成でプログラムされ得る。さらに、再構成可能なハードウェアは、プログラムによって割当てられたタスクを実行するのに非常に効率的なカスタム論理構成でプログラムされ得る。さらに、プログラムの処理要求を命令プロセッサおよび再構成可能なハードウェア間で分割することによって、コンピュータの全体的な処理能力が向上し得る。
【０００５】
汎用プロセッサおよび再構成可能なハードウェアの双方を含むハイブリッド計算プラットフォームが開発された。例示のハイブリッド計算プラットフォームは、米国、コロラド州、コロラドスプリングズ（Colorado Springs）のＳＲＣコンピュータ株式会社（SRC Computers, Inc.）から市販されているＳＲＣ−６Ｅである。このＳＲＣ−６Ｅシステムアーキテクチャは、標準のオペレーティングシステム、たとえばリナックス（Linux）（登録商標）を実行する多数の汎用命令プロセッサを含む。汎用命令プロセッサに取付けられているのは、特別に構成された多重適応プロセッサ（ＭＡＰ（Multi-Adaptive Processors））である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１０−３２０２１４号公報
【特許文献２】特開平１１−２５０１１２号公報
【非特許文献】
【０００７】
【非特許文献１】Bohm, W. et al.“Mapping a Single Assignment Programming Language to Reconfigurable Systems”, The Journal of Supercomputing, Springer Netherlands, 2002年2月, Vol.21, No.2, pp.117〜130
【発明の概要】
【発明が解決しようとする課題】
【０００８】
再構成可能な計算を用いることを望み得るユーザにとっての重要な障害要素は、再構成可能なハードウェアをプログラムすることが困難であるという問題がある。再構成可能なハードウェアをプログラムする従来の方法には、ハードウェア記述言語（ＨＤＬ（Hardware description language））、すなわちデジタル回路の専門技術およびタイミングの明示的処理を必要とする低級言語の使用が含まれた。したがって、高級言語で書かれたプログラムを受入れ、かつこれを、元のプログラムに最小限の修正を行なうだけでハイブリッドで再構成可能なハードウェア命令プロセッサコンピュータで実行することのできるコードに変換できるプロセスが必要である。
【課題を解決するための手段】
【０００９】
概要
本発明の一実施例は、高級言語ソフトコードを統一された実行可能要素に変換する方法を含み、上記方法は、高級言語ソースコードの再構成可能なハードウェア部分からオブジェクトファイルを生成するステップと、オブジェクトファイルを統一された実行可能な要素に統合するステップとを含む。
【００１０】
本発明の別の実施例は、統一された実行可能要素を形成する方法を含み、上記方法は、高級言語プログラムを制御フローグラフ表現に変換するステップと、制御フローグラフ表現を制御データフローグラフ表現に変換するステップと、制御データフローグラフを命令プロセッサ部分および再構成可能なハードウェア部分に区分化するステップと、制御データフローグラフの再構成可能なハードウェア部分をハードウェア定義言語部分に、および命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換するステップと、ハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換するステップと、再構成可能なハードウェアビットストリームを命令プロセッサが読むことのできるビットストリームオブジェクトファイルに変換するステップと、ビットストリームオブジェクトファイルを命令プロセッサオブジェクトファイルと統合して、統一された実行可能要素を形成するステップとを含む。
【００１１】
本発明の別の実施例は、制御データフローグラフ表現を、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部を含む統一された実行可能要素を形成するためのシステムを含む。
【００１２】
本発明の別の実施例は、ハイブリッドの再構成可能なハードウェア命令プロセッサコンピュータで実行可能な統一された実行可能要素を形成するためのシステムを含み、上記システムは、高級言語を制御フローグラフ表現に変換するための高級言語コンバータと、制御フローグラフ表現を制御データフローグラフ表現に変換するための制御フローグラフから制御データフローグラフへのコンバータと、制御データフローグラフ表現を、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部と、制御デ
ータフローグラフ表現の再構成可能なハードウェア部分をハードウェア定義言語ファイルに変換するための制御データフローグラフからハードウェア定義言語へのコンバータと、ハードウェア定義言語ファイルをビットストリームファイルに変換するためのハードウェア定義言語からビットストリームへのコンバータと、ビットストリームファイルをビットストリームオブジェクトファイルに変換するためのビットストリームからオブジェクトファイルへのコンバータと、ビットストリームオブジェクトファイルを統一された実行可能要素に統合するためのリンカとを含む。
【００１３】
本発明の別の実施例は、コンピュータプログラム製品を含み、上記コンピュータプログラム製品は、統一された実行可能要素を形成させるために組み入れられたコンピュータ読取可能プログラムコードを有するコンピュータ利用可能媒体を含み、上記コンピュータ読取可能プログラムコードは、コンピュータに高級言語ソースコードを制御フローグラフ表現に変換させるためのコンピュータ読取可能プログラムコード、コンピュータに制御フローグラフ表現を制御データフローグラフ表現に変換させるためのコンピュータ読取可能プログラムコード、コンピュータに制御データフローグラフを命令プロセッサ部分および再構成可能なハードウェア部分に区分化させるためのコンピュータ読取可能プログラムコード、コンピュータに制御データフローグラフの再構成可能なハードウェア部分をハードウェア定義言語部分に、および命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコード、コンピュータにハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換させるためのコンピュータ読取可能プログラムコード、コンピュータに再構成可能なビットストリームを命令プロセッサが読むことのできるビットストリームオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコード、およびコンピュータにビットストリームオブジェクトファイルを命令プロセッサオブジェクトファイルと統合して、統一された実行可能要素を形成させるためのコンピュータ読取可能プログラムコードとを含む。
【００１４】
さらに新しい特徴は、部分的には以下に続く説明で述べられ、部分的には以下の明細書を検討すれば当業者にとって明らかになり、または本発明を実施することによって知ることができる。本発明の特徴および利点は、別掲の特許請求の範囲で特に指摘される手段、組合せ、および方法によって実現され、達成され得る。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施例に従う、高級言語（ＨＬＬ）プログラムを統一された実行可能要素に変換するためのシステムを示す図である。
【図２】本発明の実施例に従う、ＨＬＬプログラムを統一された実行可能要素に変換するためのフロー図である。
【図３】本発明の実施例に従う、高級言語（ＨＬＬ）ソースコードをハードウェアロジック実行可能要素に変換するためのフロー図である。
【図４】本発明の実施例に従う、命令プロセッサ実行可能要素をハードウェアロジック実行可能要素に変換するためのフロー図である。
【図５】本発明の実施例に従う、ＨＬＬソースを分離するための図である。
【図６】本発明の実施例に従う、ＨＬＬソースコードを制御フローグラフ表現に変換するためのフロー図である。
【図７】本発明の実施例に従った制御フローグラフの一部を示す図である。
【図８】本発明の実施例に従ったデータフローグラフを示す図である。
【図９】本発明の実施例に従ったハイブリッドＣＦＧ−ＤＦＧセグメントの例を示す図である。
【図１０】本発明の実施例に従った条件付きのデータフローグラフの例を示す図である。
【図１１】本発明の実施例に従った並列のコードブロックの例を示す図である。
【図１２】本発明の実施例に従う、ＣＦＧ表現をハイブリッド制御データフローグラフに変換するためのフロー図である。
【図１３】本発明の実施例に従ったデータフローグラフの別の例を示す図である。
【図１４】本発明の実施例に従ったパラメータ対ローカル変数の記憶の例を示す図である。
【図１５】オペコードシーケンスの図表による解釈の例を示す図である。
【図１６】本発明の実施例に従う、図１０のオペコードシーケンスから構築されたＤＦＧフラグメントの例を示す図である。
【図１７】本発明の実施例に従う、スカラパラメータ間接を除去した後のＤＦＧフラグメントの例を示す図である。
【図１８】本発明の実施例に従ったＤＦＧブロックコードの例を示す図である。
【図１９】本発明の実施例で用いられる３つのアレイ参照の例を示す図である。
【図２０】本発明の実施例に従う、サブルーチンコールのオペコード構造および対応するブロックコードを示す図である。
【図２１】本発明の実施例に従う、関数コールのオペコード構造および対応するブロックコードを示す図である。
【図２２】本発明の実施例に従う、分岐および対応するコードブロックのオペコード構造を示す図である。
【図２３】本発明の実施例に従う、基本ブロックと、入力および出力フロー制御を扱うために中心ブロックに追加されたロジックとを有するＣＦＧ表現の一部を示す図である。
【図２４】本発明の実施例に従った、ブロックのＯＲノードに結合されたセレクタ入力を有する基本ブロックを示す図である。
【図２５Ａ】本発明の実施例で用いられるオペコードのサブ木の例を示す図である。
【図２５Ｂ】本発明の実施例で用いられるオペコードサブ木のさらに他の例を示す図である。
【図２６】本発明の実施例で用いられるループのための例示のＤＦＧを示す図である。
【図２６Ａ】本発明の実施例で用いられるループのための例示のＤＦＧを示す図である。
【図２６Ｂ】本発明の実施例で用いられるループのための例示のＤＦＧを示す図である。
【図２７】本発明の実施例に従った、遅延のないパイプライン化されたＤＦＧの例を示す図である。
【図２８】本発明の実施例に従った、マージした後のコードブロックの一部を示す図である。
【図２９】本発明の実施例に従った、ＣＦＧ−ＤＦＧ表現を再構成可能なハードウェア部分および命令プロセッサ部分に区分化するためのフロー図である。
【図３０】本発明の実施例に従う、統一された実行可能要素を形成するためのフロー図である。
【図３１】本発明の実施例に従った、例示のＭＡＰエミュレータシステムを示す図である。
【図３２】本発明の実施例に従った、別の例示のＭＡＰエミュレータシステムを示す図である。
【図３３】本発明の実施例に従った、データフローシミュレータのフロー図である。
【図３４】本発明の実施例に従った、データフローシミュレーションにおけるトークンの流れの例を示す図である。
【発明を実施するための形態】
【００１６】
詳細な説明
システムの概観
ここで図１を参照すると、高級プログラミング言語で書かれたプログラムを、統一された実行可能要素に変換するためのハイブリッドの再構成可能なハードウェア命令プロセッサシステム１００の実施例が示されている。一実施例において、システム１００の再構成可能なハードウェア部分は、多重適応プロセッサ（ＭＡＰ）を含み得、これはフィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）の再構成可能な回路をロジックと統合して、ＦＰＧＡを制御し、システム１００の命令プロセッサ部分と通信し得る。別の実施例において、システム１００における再構成可能なハードウェアおよび命令プロセッサ間の電子通信は、スイッチ／ネットワークアダプタポートおよび／または多重ＭＡＰを命令プロセッサにリンクするためのスイッチの使用を含み得る。
【００１７】
システム１００の実施例は、特に、ＭＡＰ、命令プロセッサ、高級言語（ＨＬＬ（highlevel language））ファイルから統一された実行可能要素へのコンバータ１０４、サポートハードウェアロジックモジュール１１８、ユーザハードウェアロジックモジュール１２０およびランタイムライブラリ１２２を含むＭＡＰプログラミング環境を含む。システム１００の実施例において、ＨＬＬソースコードファイル１０２はコンバータ１０４に入力される。ＨＬＬソースコードファイル１０２は、たとえば特に、Ｃ，Ｃ＋＋，Fortran,ＣＯＢＯＬ,ＢＡＳＩＣ,ＰＡＳＣＡＬおよびＪａｖａ（登録商標）等の従来の高級言語で書かれてもよい。
【００１８】
ＨＬＬファイル１０２はコンバータ１０４に入力され、これはコンバータ１０４の構成要素によって統一された実行可能要素１２４に変換され得る。コンバータ１０４の実施例は、特に、ＨＬＬコンバータ１０６、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８、区分化部１１０、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ１１２、ＨＤＬからビットストリームへのコンバータ１１４およびリンカ１１６を含み得る。
【００１９】
コンバータ１０４は、高級言語ファイルを制御フローグラフ（ＣＦＧ（control flow graph））表現に変換するＨＬＬコンバータ１０６を含み得る。一実施例において、ＨＬＬコンバータ１０６は、高級言語ソースコードを読出し、ソースコードをパーズし、コードを内部表現およびシンボルテーブルに変換することによって、従来のコンパイルを開始するための論理命令を含むソフトウェアモジュールを含む。ＨＬＬコンバータ１０６は、ソースコードの構文および意味検査を行ない、かつソースコードにおけるエラーに応じて適切な診断メッセージを生成するための論理命令を含み得る。
【００２０】
さらに、ＨＬＬコンバータ１０６は、ソースコードの内部表現の最適化のための論理命令を含み得る。特に、ＨＬＬコンバータ１０６はＣＦＧ表現を出力する。ＣＦＧ表現は、命令プロセッサコンパイラによって命令プロセッサシーケンスを生じるようにさらに処理されるか、またはデータフロー分析および再構成可能なプロセッサ（たとえばＭＡＰ）のための論理生成のために、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８等の別のソフトウェアモジュールに渡される可能性がある。
【００２１】
一実施例において、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８は、ＨＬＬコンバータ１０６によって生成されたＣＦＧ表現を受信し、かつＣＦＧ表現を制御データフローグラフ表現に変換するための論理命令を含むソフトウェアモジュールであってもよい。制御データフローグラフは、コンパイラの段階の残り全体にわたって用いられ得る。ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８は、コンパイル済みのコードにおける並列度を最適化し得る。ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８の機能は、特に、コンバータ１０４の残りの構成要素によって用いられ得る、ＨＬＬコンバータ１０６によって渡されたＣＦＧ表現からの制御データフローグラフの生成と、基本ブロックの、データフローグラフにおけるコードブロックへの変換と、入出力スカラの変換と、出入力アレイの変
換と、コードブロックにおけるスカラ参照の処理と、コードブロックにおけるアレイ参照の処理と、ループ制御の構成と、ポインタ参照の処理と、命令プロセッサコードへのコールの処理と、命令プロセッサＯＳへのシステムコールの処理と、組込関数コールの拡張と、外部関数コールの拡張と、ループの最適化と、マルチスレッドの最適化と、データ経路および論理装置のデータ幅の最適化と、不必要な構造の除去を含む構造の最適化とを含み得る。
【００２２】
区分化部１１０は、ロジックをハイブリッドの計算システムの利用可能な資源に適合するようにサイズ設定するための論理命令を含むソフトウェアモジュールであってもよい。区分化部１１０は、入力としてＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８によって生成された制御データフローグラフを受信し得、制御データフローグラフを利用可能なリソースにマップして性能を最適化し得る。
【００２３】
例示の実施例において、区分化部１１０は、以下の情報、すなわちハードウェアロジックモジュール情報ファイルからの論理演算装置のサイズ、リソースファイルからのチップサイズ、リソースファイルからのインターフェイスサイズおよび速度、リソースファイルからのデータ記憶性能およびサイズ、プラグマまたは指示子等のプログラマからの区分化構文入力、制御データフローグラフ（ＣＦＧ−ＤＦＧ）エミュレータからのプロファイリング情報、ならびに命令プロセッサプロファイリングツールからのプロファイリング情報を入力として受信し得る。
【００２４】
例示の実施例において、区分化部１１０は、ＣＦＧ−ＤＦＧに上記の情報の注釈を付け、かつ命令プロセッサおよびＭＡＰにおける実行に基づくサブグラフの性能パラメータを推定するための論理命令を含み得る。区分化部１１０は、ロジックのサイズ設定を評価し、かつたとえば集積回路およびＭＡＰのリソースに基づいてロジックを割付けるための論理命令をさらに含んでもよい。
【００２５】
区分化部１１０は、ＭＡＰ上でインターフェイスロジックを定義し、かつＭＡＰプロキシコードを命令プロセッサに割当てるための論理命令を含んでもよい。ＭＡＰプロキシは、ＭＡＰ上の制御されたスレッドに遷移する命令プロセッサコードの目標を与える。ＭＡＰプロキシはコールを受け、ＭＡＰに必要とされるいかなるパラメータの受け渡しも開始する。ＭＡＰプロキシはＭＡＰからの要求も受信し得る。
【００２６】
区分化部１１０の出力は、ＭＡＰにおけるロジックとして実現化され得るＣＦＧ−ＤＦＧ、および命令プロセッサで実現化され得るＣＦＧ−ＤＦＧを含んでもよい。
【００２７】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ１１２は、ＣＦＧ−ＤＦＧを、ＭＡＰにおける再構成可能なプロセッサでインスタンス化される物理的なロジックのハードウェア定義に変換するための論理命令を含むソフトウェアモジュールであってもよい。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ１１２は、入力としてＣＦＧからＣＦＧ−ＤＦＧへのコンバータ１０８からのＣＦＧ−ＤＦＧファイルを受信し、ＣＦＧ−ＤＦＧファイルを内部表現に変換する。ハードウェアロジックモジュール情報ファイルを読み出して、ノード入力、出力および待ち時間の情報を与える。ノードおよびノード間の経路は、その互換性およびビット幅の一貫性について検査される。
【００２８】
一部のノードは、ノードをインスタンス化するのではなくインライン化される。インライン化とは、インスタンス化された論理モジュールとしての定義を参照することではなく、ハードウェア定義を生成することを示す。ＣＦＧ−ＤＦＧにおけるノードのすべては、適切なノード依存および一貫したデータフローかどうかを検査される。各ノードは次にインスタンス化されて、ノードを接続するすべての配線が宣言される。ハードウェア定義言
語を含む出力ファイルが生成される。出力ファイルは、VerilogまたはＥＤＩＦ等のハードウェア定義言語で書かれてもよい。
【００２９】
ＨＤＬからビットストリームへのコンバータ１１４は、VerilogからＥＤＩＦへコンパイルするための従来の合成ツールを含み得、ＥＤＩＦファイルをＭＡＰにロード可能なビットストリームに変換するための位置およびルート（Place and Route）ツールを用いて、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ１１２の出力を処理し得る。
【００３０】
リンカ１１６は、ビットストリームオブジェクトファイル、命令プロセッサファイルおよび他のオブジェクトファイルを含むオブジェクトファイルを受入れ、かつこれらを統合して統一された実行可能要素１２４を形成するための論理命令を含むソフトウェアモジュールであってもよい。
【００３１】
別の実施例において、システム１００は、ＭＡＰで実行されるべきロジックに変換されない高級言語の一部をコンパイルするために用いられ得る従来の命令プロセッサコンパイラ（図示せず）を含んでもよい。
【００３２】
システム１００はまた、統一された実行可能なファイルを生成するための論理命令を含むソフトウェアモジュールを含み得るビットストリーム構成部（コンフィギレータ）（図示せず）を含んでもよい。ビットストリームファイルは、コンパイル済みのＣルーチンとしてカプセル化され、このＣルーチンはコンパイラおよび標準リンカを用いて、実行可能なファイルに組込むことができる。アプリケーション命令プロセッサの命令、ＭＡＰ論理ビットストリーム、および必要とされるいかなるライブラリコードをも含む実行可能要素は、統一された実行可能要素と呼ばれてもよい。
【００３３】
システム１００は、コンバータ１０４への比較ツールであるバイナリトランスレータ（図示せず）を含み得る。コンバータ１０４は、入力として高級言語ソースコードを受入れ、かつＣＦＧ表現および統一された実行可能要素を生成し得る。バイナリトランスレータは、実行可能なファイルを受入れ、これをＣＦＧ表現に変換し、かつこれをコンバータ１０４への二次入力に与えて、ソースコードの必要性を回避し得る。
【００３４】
システム１００は、モジュール１１８および１２０ならびにライブラリ１２２を含み、これはＨＬＬから統一された実行可能要素への変換プロセスのためのランタイム環境を与え得る。ランタイム環境は、各アプリケーションの命令プロセッサ部分に含まれるライブラリルーチンを含み得る。これらのライブラリルーチンは、ＭＡＰのためのサポートサービスを与える。これは、リソースの割付けおよび割付け解除、命令プロセッサおよびＭＡＰ間の通信、デバッグおよび性能分析を含む。少なくとも３つの別個の環境、すなわち１）ＭＡＰハードウェアでの実行、２）エミュレートされるＭＡＰおよびデータフローグラフエミュレーションでの実行、３）エミュレートされるＭＡＰおよびシミュレートされるユーザロジックでの実行が、ランタイムルーチンによってサポートされ得る。
【００３５】
方法の概観
ここで図２を参照すると、本発明の実施例に従って高級言語（ＨＬＬ）を、統一された実行可能要素に変換する方法２００が示されている。方法２００は、ステップ２０２でＨＬＬプログラムを制御フローグラフ（ＣＦＧ）に変換することによって開始され得る。一実施例において、ＨＬＬプログラムの、指定されたＣＦＧフォーマットへの変換２０２は、従来のＨＬＬコンパイラによって行なわれ得る。ＨＬＬプログラムのＣＦＧへの変換２０２では、ＨＬＬプログラムをＣＦＧ表現にパーズし、かつ命令プロセッサで実行可能な命令コードを生成するためにコンパイラが用いられてもよい。命令コードは次にオブジェクトファイルに書込まれ、このオブジェクトファイルはアドレスを解くリンカ・ローダと
ともにリンクされ得る。
【００３６】
ＨＬＬプログラムで用いられるプログラミング言語は、特にＣ，Ｃ＋＋，Fortran,ＣＯＢＯＬ,ＢＡＳＩＣ,Ｊａｖａ（登録商標）,ＰＡＳＣＡＬ等の従来の高級言語であってもよい。ＨＬＬプログラムは、スカラ、アレイおよびユーザ指定の集合体、特にその関連のオペレータを含むさまざまなデータエンティティを含み得る。ＨＬＬプログラムは、関数コール、サブルーチン、ループおよび条件、特に演算を含み得る。
【００３７】
本発明の実施例において、方法２００の次のステップは、ステップ２０４での、ＣＦＧ表現のハイブリッドな制御データフローグラフ表現（ＣＦＧ−ＤＦＧ）への変換であり得る。簡単に言うと、この変換２０４は、ＣＦＧ表現をその構成要素の基本ブロックに分離するステップと、ロードおよび記憶データを基本ブロックの上部および下部に追加するステップと、基本ブロックをＣＦＧ−ＤＦＧ表現のコードブロックに変換するステップとを含み得る。変換２０４のより詳細な説明が以下で行なわれる。
【００３８】
方法２００の次のステップは、ステップ２０６での、ＣＦＧ−ＤＦＧ表現の再構成可能なハードウェア部分および命令プロセッサ部分への区分化であってもよい。一実施例において、ＣＦＧ−ＤＦＧ表現は、区分化プログラムに入力され得、この区分化プログラムはデータをスキャンして、それを構成可能なハードウェアの部分および命令プロセッサの部分に分割し得る。別の実施例において、区分化プログラムは、ユーザが挿入した区分化構文からの命令、たとえばＣプラグマまたはコンパイラ指示子を受信し得、この命令はＣＦＧ−ＤＦＧコードがいかにして再構成可能なハードウェア部分および命令プロセッサ部分に区分化されるかを案内する。たとえば、プラグマは、区分化プログラムに、区分化されたＣＦＧ−ＤＦＧ表現の命令プロセッサ部分に特定のループ演算を入れるように命令してもよい。プラグマは、元のＨＬＬプログラムのソースコードに含まれてもよく、または区分化プログラムに直接与えられてもよい。
【００３９】
方法２００のこの実施例におけるこの時点で、区分化ステップ２０６からの区分化されたＣＦＧ−ＤＦＧ表現は、別々のプロセスステップに分割され得る。区分ステップ１０６からの命令プロセッサ部分は、命令プロセッサオブジェクトファイル２０８に変換され得る。一実施例において、ハイブリッドのＣＦＧ−ＤＦＧ表現の命令プロセッサ部分は、ＣＦＧ表現に戻され、次に命令プロセッサで実行可能な命令コードに変換され得る。命令コードは、次に、アドレスを解くリンカ・ローダとともにリンクされ得るオブジェクトファイルに書込まれ得る。別の実施例において、ハイブリッドのＣＦＧ−ＤＦＧ表現の命令プロセッサ部分は、元のＣＦＧ表現の一部と同一とみなされてもよく、元のＣＦＧ表現のこの部分はオブジェクトファイルに変換されてもよい。
【００４０】
ここで区分化ステップ２０６からのＣＦＧ−ＤＦＧ表現の再構成可能なハードウェア部分に注目すると、この部分は、ＣＦＧ−ＤＦＧ表現からＨＤＬ（hardware definition language）に変換され得る（２１０）。ハードウェア定義言語は、特にVerilogおよびＥＤＩＦの従来のＨＤＬを含み得る。
【００４１】
ハードウェア定義言語ファイルは、次にビットストリームデータファイルに変換されてもよく（２１２）、このファイルは再構成可能なハードウェアにおける個々の再構成可能な回路にロード（load）することができる。たとえば、ビットストリームデータファイルは、本発明のハイブリッドの命令プロセッサの再構成可能なハードウェアコンピュータで用いられる多重適応プロセッサ（ＭＡＰ）におけるフィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）にロードされてもよい。実施例において、「位置およびルート」プログラムを用いて、ＨＤＬからビットストリームへの変換２１２を行なってもよい。ＨＤＬファイルに基づいて、「位置およびルート」プログラムはインスタンス化され、再構成可
能なハードウェアのハードウェアロジックモジュールと相互接続されてもよい。「位置およびルート」プログラムは、モジュールが物理的にどこに進み得るか、およびこれらが再構成可能なハードウェアにおいていかにして互いに結合されるかを指示する。
【００４２】
方法２００の実施例において、ビットストリームファイルが生成された後で、これらはステップ２１４でビットストリームオブジェクトファイルに変換され得る。ビットストリームからオブジェクトファイルへの変換２１４は、ビットストリームデータを高級言語ソースコードに変換し（たとえばＣ構造にビットストリームを配置し）、かつ高級言語ファイルを命令プロセッサが読むことのできるオブジェクトファイルに変換するステップを含み得る。
【００４３】
方法２００の実施例において、ステップ２１４でビットストリームファイルをビットストリームオブジェクトファイルに変換し、かつステップ２０８でＣＦＧ−ＤＦＧ表現の命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換した後で、オブジェクトファイルはステップ２１６で収集され得る。追加のオブジェクトファイルは、ビットストリームオブジェクトファイルおよび命令プロセッサのオブジェクトファイルとともに収集され得る。たとえば、追加のオブジェクトファイルは、方法２００の前の反復からもたらされてもよい。追加のオブジェクトファイルは、前の命令プロセッサのコンパイルから、およびオブジェクトライブラリから取得してもよい。
【００４４】
ビットストリームオブジェクトファイル、マイクロプロセッサオブジェクト命令プロセッサファイル、およびいかなる追加のオブジェクトファイルが一旦収集されると、これらは互いにリンクされて（２１８）、統一された実行可能要素２２０を形成する。実施例において、オブジェクトファイル２１８のリンクは、リンカプログラムによって行われてもよい。統一された実行可能要素２２０は、命令プロセッサによって読取り可能であり、このプロセッサは、統一された実行可能要素２２０を実行して、ハイブリッドの再構成可能なハードウェア・マイクロプロセッサコンピュータがＨＬＬプログラムを実行するように構成し得る。
【００４５】
ここで図３を参照すると、本発明の実施例に従って高級言語ソースコードをハードウェアロジック実行可能要素に変換する方法のフロー図が示されている。この方法は、区分化ステップ３０４で処理される高級言語（ＨＬＬ）ソースコード３０２の分析で開始され得る。ＨＬＬソースコード３０２で区分が発見された場合、このコードは、ステップ３０６および３０８で分割され、制御フローグラフ（ＣＦＧ）表現に変換され得る。
【００４６】
一実施例において、ＨＬＬソースコード３０２の区分化された部分がステップ３０８でＣＦＧ表現に変換された後で、このＣＦＧ表現を用いて、ＭＡＰプロキシ３２２（高級言語コンバータセクションのＭＡＰプロキシの詳細を参照）を生成するか、またはステップ３１６でハードウェアロジックのためのＣＦＧ−ＤＦＧ表現に変換し得る。ＣＦＧ表現のうちＭＡＰプロキシ３２２の生成をもたらす部分について、この部分はステップ３２４でバイナリ命令プロセッサコードに変換され、次にステップ３２６ですべての他のバイナリファイルとリンクされて、ハードウェアロジックの実行可能要素３２８の一部となり得る。ＣＦＧ表現のうち、ステップ３１６でハードウェアロジックのためにＣＦＧ−ＤＦＧ表現に変換された部分について、ＣＦＧ−ＤＦＧ表現は、ステップ３１８でVerilogコード等のＨＤＬ（hardware definition logic）コードに変換され、次にステップ３２０でハードウェアロジックバイナリに変換され、ステップ３２６で他のすべてのバイナリファイルとリンクされて、ハードウェア実行可能要素３２８の一部となり得る。区分化されたソースコードの一部ではない残りのＨＬＬソースコード３０２は、ステップ３０６でＣＦＧ表現に変換され得る。次に、ＣＦＧ表現は、ステップ３２４で命令プロセッサのバイナリコードに変換された後で、すべての他のバイナリファイルとリンクされて（３２６）、ハ
ードウェアロジック実行可能要素３２８（すなわち統一された実行可能要素）の一部となり得る。
【００４７】
区分を有さないＨＬＬソースコード３０２について、コード全体はステップ３１０でＣＦＧ表現に変換されてもよく、ステップ３１２で再構成可能なハードウェア部分および命令プロセッサ部分に区分化されてもよい。命令プロセッサ部分は、ステップ３２４で命令プロセッサバイナリコードに変換され、最終的にハードウェアロジック実行可能要素３２８へと形成され得る。再構成可能なハードウェア部分は区分化され得、この部分はステップ３２２でＭＡＰプロキシを生成し、一方でこの同じ部分はＣＦＧ−ＤＦＧ表現に変換される。この区分化された部分は、最終的にハードウェアロジック実行可能要素３２８の一部になり得る。
【００４８】
ここで図４を参照すると、本発明の実施例に従ったバイナリトランスレータの演算方法４００のフロー図が示されている。一実施例において、命令プロセッサ実行可能要素４０２は、ステップ４０４で編集されて、これがハードウェアロジック実行可能要素４２６の一部になるようにしてもよい。別の実施例において、命令プロセッサ実行可能要素４０２は、ステップ４０６でＣＦＧ表現に翻訳されてもよい。
【００４９】
ステップ４０６で命令プロセッサ実行可能要素４０２がＣＦＧ表現に変換され、かつＣＦＧ−ＤＦＧ表現に変換された後で、これは次にステップ４０８で再構成可能なハードウェア部分および命令プロセッサ部分に区分化され得る。命令プロセッサ部分およびＣＦＧ表現のいかなる残りの部分４２０も、次にステップ４２２で命令プロセッサバイナリコードに変換され得る。命令プロセッサバイナリコードは、次にステップ４２４ですべての他のバイナリファイルとリンクされて、ハードウェアロジック実行可能要素４２６の一部になり得る。
【００５０】
再構成可能なハードウェア部分は区分化され得、この部分はステップ４１６でＭＡＰプロキシを生成し、一方でこの同じ部分がステップ４１４でハードウェア定義言語（ＨＤＬ）コード（たとえばVerilog）に変換され、これは次にステップ４１８でハードウェアロジックバイナリに変換され得る。ハードウェアロジックバイナリは、ステップ４２４ですべての他のバイナリファイルとリンクされて、ハードウェアロジック実行可能要素４２６の一部になり得る。
【００５１】
区分化された部分によって生成されたＭＡＰプロキシは、ステップ４２２で命令プロセッサバイナリコードに変換され、次にステップ４２４ですべての他のバイナリファイルとリンクされて、ハードウェアロジック実行可能要素４２６の一部になり得る。
【００５２】
図２および３は、本発明の実施例に従って、ＨＬＬプログラムを統一された実行可能要素またはハードウェアロジック実行可能要素に変換するステップで用いられ得る方法のステップを示している。図４は、命令プロセッサ実行可能ファイルをハードウェアロジック実行可能要素に変換するプロセスで用いられ得る方法のステップを示している。追加のステップおよび示されたステップの代替のシーケンスが、本発明の追加の実施例で考察されることが認識されるべきである。
【００５３】
マップ実行セレクタ
例示の実施例において、ハードウェアロジックのために分離されかつ目標にされ得る、高級言語で書かれたソースコードの領域を識別するための方法が提供され、一方でコードの他の部分は、従来のプロセッサで実行するためにコンパイルされ得る。例示の方法では、コードのうちどの領域がハードウェアロジックで実行されるべきかを示す特別なブラケット構文が用いられ、ブラケット領域内に含まれる変数のスコーピング（scoping）情報
が提供される。この情報を用いて、ユーザがさらに介入することなく、ハードウェアロジックで実行するように識別された領域の実行を容易にする通信およびデータ移動ルーチンを構築し得る。
【００５４】
多くの高級プログラミング言語は言語構成体を含み、この言語構成体を用いて、汎用プロセッサではなく、ハードウェアロジックでコンパイルされ実行され得るユーザコードの領域を指定し得る。たとえば、Fortran言語で、構文“!dir$”を用いてもよく、Ｃにおいて構文“#pragma”を用いてもよい。これらの構成体を用いて、ユーザコードにブラケットを付ける構文は、開始または停止識別子のいずれか、ブラケットコード内に含まれる変数のスコーピングルール、および専用に（privately）計算されたデータをコピーするための追加の構文を含む。
【００５５】
たとえば、以下の小さなFortranプロシージャを考えることにする。
【００５６】
【数１】
2010146577.tif 000003
【００５７】
このコードセグメントは、最初に３つのアレイ（ａ，ｂ，ｃ）を宣言し、このアレイは計算で用いられるデータを保持するために用いられる。このアレイは共通のブロックで宣言され、これらの記憶の割付けが、命令プロセッサのメモリで行なわれ、そしてこのプロシージャに関連したローカルスタックスペースでは行なわれないことを意味している。プロシージャに対する外部コールがあり、これはアレイにおけるデータを初期化するものと想定することができる。この初期化の後で、コールはこのプロシージャの計算部分を含むドゥ・ループ（do-loop）である。
【００５８】
コードのうちハードウェアロジックで実行するように識別された部分は、ドゥ・ループ構成体で囲まれたループ本体であると決定される。ハードウェアロジックを生成する、コンパイルシステムによって認識される構文を用いて、Fortranコードを以下に類似するように修正してもよい。
【００５９】
【数２】
2010146577.tif 000004
【００６０】
ここで、ドゥ・ループは、コンパイルシステムが必要とする情報を与える一対の指示子とともにブラケットを付けられている。コンパイルシステムは、この情報を処理して、汎用プロセッサで実行するプロシージャ、およびハードウェアロジックで実行するサブプログラムの双方を構築する。
【００６１】
この単一のFortranプロシージャの、別々にコンパイル可能なプロシージャへの変換は、複数のコンパイル段階を含み得る。１つの段階において、コンパイルシステムはプログラムに含まれる個々のソースファイルを処理し、ハードウェアコンパイルが望まれることを示す構文を有さないさらに再構成可能なハードウェアロジックコンパイルソースファイルを廃棄する。コンパイルシステムが、再構成可能なハードウェアコンパイルが望まれることを示す構文に出合ったときに、コンパイルシステムは、命令プロセッサおよびハードウェアロジックのブラケット部分の双方でこのソースファイルのコンパイルを実行するのに必要なインフラストラクチャを構築し始める。命令プロセッサのコンパイル段階およびハードウェアロジックのコンパイル段階に必要とされるソースファイルを生成することに加えて、ハードウェアロジックリソースを割付け、予約し、かつ解放するために用いられる機構が生成される。
【００６２】
ブラケット構文は、ブラケット領域内で用いられるすべての変数のためのスコーピング情報を含み得る。このスコーピング情報は、コンパイルシステムによって用いられて、補正データ移動文を構築し、プログラムの完全性が、完全に命令プロセッサで実行された場合と同じであることを保証し得る。「グローバル」としてのスコーピングデータおよび変数は、コンパイルシステムに対して、このデータが命令プロセッサおよびハードウェアロジック間のコール境界にわたって持続性を有することを示す。データをハードウェアロジックに動かしかつハードウェアロジックからデータを取出す機構は、コンパイルシステムによって生成される新しいサブプログラムに構築され得る。グローバルデータは同様の態
様で処理されてデータの完全性が保護され得る。
【００６３】
「専用」とされたスコーピングデータおよび変数は、コンパイルシステムに対して、これらの変数がスコープにおいてちょうどハードウェアロジックのローカルにあることを示し、したがってその結果として生じる値がハードウェアロジックの実行地点を越えて持続する必要はない。この構文の変形として、専用データをソースファイルの命令プロセッサバージョンでローカル変数に「コピー」することのできる追加の構文がある。
【００６４】
このコンパイルシステムはこのデータスコーピング情報を用いて、２つの分離したソースファイルを生成し、その各々はブラケット構文を含む元のソースファイルの一部を示す。新しいソースファイルのうちの１つがコンパイルされて、命令プロセッサのシステムで実行される。他のソースファイルを用いてハードウェアロジックを生成する。このプロセスは図５に示されている。
【００６５】
高級言語コンバータ
コンパイルシステムのうち最初にコールされた構成要素が、いかなる命令プロセッサシステムでのコンパイルと同様の従来のコンパイル段階を開始する。この構成要素は、入力としていかなるプログラミング言語コードも受信し、ソースファイルから次にパーズすることのできるトークンを抽出する。パーズ段階が行なわれている間、意味解析も行なわれて、この段階の後でコードおよびシンボルテーブルの内部表現が生成されるようにしてもよい。意味上の誤り検査が行なわれて、適切な診断メッセージが出される。
【００６６】
現在このコンパイル段階で生成されたソースコードの内部表現は、コードの制御フローブロックと類似している。次のステップでは、この制御フローブロックを、オプティマイザが処理する内部言語に拡張する。この拡張段階の間に、各制御フローブロックは、基本ブロックまたは拡張された基本ブロックのいずれかと呼ばれるユニットに拡張され得る。フローグラフは、関数での基本ブロックの有向グラフであってもよく、これは関数の制御フローを示している。グラフの各ノードは基本ブロックに相当する。このフローグラフは、最適化が行なわれると、コンパイルの際に更新され得る。このステップの間に行なわれる主要なグローバルとしての最適化は、一定したコードの動き、すなわち誘導変数分析、グローバルレジスタの割当を含み得る。他の最適化は、コードブロックのマージおよび最適化された制御フローコードブロックをもたらすピープホールの最適化を含んでもよい。
【００６７】
グローバルレジスタの割当の最適化の後で、ルーチンのコールパラメータが中間ファイルに書込まれ、このファイルは次のコンパイル段階への入力として用いられ得る。コールパラメータは、そのデータタイプとともに書込まれ、次にルーチンおよびそのデータタイプに関連したユーザシンボルが続く。ルーチンで用いられるシンボルを書出した後で、ファイルの次の部分は端末コードブロックのトラバーサルを含み、これは示された基本ブロックのタイプおよびコードブロックに関連した命令を示している。一旦この制御フロー表現が生成されると、最終的なステップでは、ルーチンのコンパイルの際に生成されたすべての命令が生成される。これらの命令は、制御フローブロックにリストされた命令に相当するかもしれない。
【００６８】
いかなるアーキテクチャでもそうであるように、コンパイラは、高級言語で書かれたプログラムを、コンピュータで実行するために機械語での等価のプログラムに処理することが必要とされる。システム１００は、従来の命令プロセッサのみのためのプログラムを翻訳する能力によって、または再構成可能なプロセッサとの組合せによって、上記の要求を満たしている。この高級言語を翻訳するのに用いられるコンパイラの段階は、命令プロセッサコンパイラ技術に基づいている。ＨＬＬコンバータは、言語特定のフロントエンドを有するコンパイルの混合モデルを用いて、共通の高級中間表現を生成する。この第１のレ
ベルの表現は次に、制御フロー分析を含むさまざまな基本的な最適化に入力されるため、結果として生じる第２のレベルの中間表現は制御フロー表現と呼ぶことができる。制御フロー表現は、ＨＬＬコンバータが出力として生成する制御フロー情報における主要な構成要素となる。以下の文章では、このファイルおよびこの段階でのコンパイルの結果として生成することのできる追加のファイルの内容についての一層の詳細が示される。
【００６９】
ＨＬＬコンバータへの入力は、２つの異なるタイプのソースコードからなる可能性がある。いかなる高級言語のソースコードも、このコードがそれが示す言語表示に準拠するように書き込まれた場合、ＨＬＬコンバータへの入力として用いることができる。ＨＬＬコンバータへの別の入力は、もともと表現された高級言語の制御フロー情報を表わすソースコードである。この制御フロー情報を、（以下で説明されるように）明確に規定されたインターフェイス仕様に書込んで、以前のコンパイルからの制御フロー情報を用いることができるようにするか、または別のマイクロプロセッサ実行可能要素等の別のソースから導き出された制御フロー情報を用いることができるようにする。
【００７０】
制御フロー分析が各プロシージャにおける制御の階層的なフローを明らかにした後で、制御フローの表現を中間言語として生成することができる。この時点で生成される制御フロー情報ファイルは、以下のもの、すなわちエントリシンボル、ユーザ命令、特にシンボル、基本ブロックおよび中間表現を含むが、必ずしもこれらに限定されない。
【００７１】
エントリシンボルは、ＨＬＬコンバータによって生成されたシンボルを表わし、これはコールルーチンで渡されたパラメータであり、これは実行可能要素の命令プロセッサの部分およびハードウェアロジック間のインターフェイスとして機能する。これらのシンボルは、計算のためにハードウェアロジックおよびスカラ値がアクセスするデータのアドレスを渡し得る。
【００７２】
ユーザシンボルは、コードのうちハードウェアロジックのためにコンパイルされる領域における変数を示すシンボルである。これらのシンボルは、アレイおよび構造等の構成体を含む高級ソースコードにおける変数名に対応する。シンボルはいかなる外部ルーチンコールも表わし得る。ここでハードウェアロジックモジュールはコンパイルプロセスで見ることができるかもしれない。
【００７３】
基本ブロックは最大シーケンスの命令であってもよく、この命令はその最初の部分のみで入力され、かつその最後の部分のみから終了することができる。所与のコードソースを示す基本ブロックがここに列挙される。すべての基本ブロックは、ブロック情報ヘッダエントリとともに開始される。このエントリは、相対ブロック番号、この基本ブロックを示すソース行番号、関連のシンボルテーブルで示されるように（存在すれば）このブロックが定義したラベルを与える。この情報の後には、これらの基本ブロックのための属性を示すフラグのリストがある。これらのフラグは、たとえばこのブロックがプロシージャへのエントリを含むか、このブロックが何らかの外部参照を有するか、およびこのブロックの制御が失敗してすぐ次の後続点に渡されるかといったブロックに関するさらに多くの情報を与える。このブロック情報ヘッダラインの直後に来るのは端末ノードを示す命令のリストである。これらのタイプの命令の例として、メモリへのデータの記憶（store）、無条件のもしくは条件付きの分岐、またはプロシージャコールが挙げられる。各端末ノードは、基本ブロック内のその相対数、文を示す命令の「木」を指す行番号、およびこのノードについてのさらに多くの情報を与えるフラグによって示されている。
【００７４】
この基本ブロックセクションが参照した命令は、中間表現命令において列挙され得る。このセクションは、コンパイルの際に生成されかつこの時点まで最適化のために用いられた個々の命令を含む。これらの命令は、基本ブロックに分類され、その互いの関係は前の
セクションで既に確立されている。これらはここで、コンパイルのプロセスで生成された順序で生成される。
【００７５】
第１のエントリは、この命令リストにおける命令の相対数である。次に来るのは命令名であり、その後にこの命令の各オペランドが続く。オペランドが変数のテーブルにおけるエントリおよびエントリポイント名を指すラベルであれば、オペランドのための情報が提供され得る。内部で生成されたコンパイルからの名前が示される。メモリからロードされた、または記憶されたデータベースに関する情報が提供されてもよい。制御フロー情報ファイルで参照することのできる命令のタイプに関する一層の詳細が、インターフェイス仕様セクションにおいて示される。
【００７６】
制御フロー情報ファイルの生成は、コンパイルコマンドラインまたはソースコードそれ自体のいずれかで与えられたオプションに基づく。このオプションをコンパイルコマンドに追加することによって、サブプログラムのより大きなソースファイルに含まれるサブプログラムのうちどれがハードウェアロジックの目標にされているべきかを指定する。コンパイルの際に、指定されたサブプログラムのみが、後続のハードウェアロジックコンパイルのために分離ファイルに書出されるその制御フロー情報を有する。残りのソースコードサブプログラムはコンパイルされて、命令プロセッサ機械コードを生成する。
【００７７】
制御フロー情報ファイルは、区分化またはブラケット、コンパイラによって認識されかつパーズされる構文の存在に基づいて生成することができる。この区分化構文は、言語特定のソース行と関連して用いられて、このソースコードが異なるアーキテクチャのためにコンパイルされる場合、区分化構文はコンパイルの際に無視されるようにし得る。この構文のために定義されたキーワードによって、ソースコード全体の領域を、ハードウェアロジックのための分離したサブプログラムとして抽出し、コンパイルすることができる。コマンドラインオプションについて上述したように、この特別にブラケットを付けられた領域のみが、後続のハードウェアロジックのコンパイルのために分離した制御フロー情報ファイルへと書出されるその制御フロー情報を有する。
【００７８】
区分化構文がコードに存在せず、かつハードウェアロジックコンパイルために目標にされる特定のサブプログラムを指定するコマンドラインオプションがない場合、コンパイラは省略値をとって、ハードウェアロジックの候補としてソースコード全体をコンパイルし得る。各サブプログラムに関する制御フロー情報が書出され、後続のコンパイルために渡され得る。次のコンパイルステップでは、部分集合の制御フロー情報を生成するために区分化するための、制御フローにおける最良の地点を決定する際に必要とされる分析を行なう。この新しい制御フロー情報ファイルはＨＬＬコンバータに戻されて、必要とされるＭＡＰプロキシルーチンを生成する。
【００７９】
高級言語から制御フロー情報ファイルを生成し、または以前に生成された制御フロー情報ファイルを処理するために用いられるコンパイラは、ハードウェアロジックの実行のために必要な機能性を提供するさまざまな他のプロシージャも生成しなければならない。これらのプロシージャは、マイクロプロセッサのコードの実行および再構成可能なプロセッサのコードの実行の間のインターフェイスをサポートすることによって機能性を提供する。このインターフェイスの機能性は、「ＭＡＰプロキシ」と呼ばれる。図６はインターフェイスの機能性の例を示している。
【００８０】
制御フロー情報ファイル６１０に含まれるコードは、ハードウェアロジックで実行されるソースコードの領域を含んでもよい。このファイルは、コンパイルプロセスを継続し、その結果としてＦＰＧＡビットストリームはハードウェアロジックの実行に好適なものとなる。
【００８１】
ＭＡＰプロキシ６１５に含まれるコードは、ハードウェアロジックで実行されるように区分化された制御フロー情報の領域に代わって、命令プロセッサで実行するためにスケジュールされてもよい。このコードは、目標とされる再構成可能なプロセッサにとって適切なデータ操作構成物を挿入することによってハードウェアロジックの実行をサポートするのに必要とされるデータ移動を処理する。ＭＡＰプロキシはまた、オペレーティングシステムと対話するように実行されるときに用いられるランタイムライブラリコールを挿入してもよい。この対話は、ハードウェアロジックリソースの割付け、すなわちハードウェアロジックステータスの照会、ハードウェアロジックリソースのシステムへの解放、および命令プロセッサのプロセスからハードウェアロジックへの制御の移動を含む。
【００８２】
ＨＬＬコンバータの最終的なステップでは、目標とされる命令プロセッサで実行する必要のある機械コードが生成される。ＨＬＬコンバータは、ソースコード全体およびＭＡＰプロキシコードのための制御フロー情報を生成する。この情報は次に機械コードに翻訳されて、このコンパイルから生成されたバイナリファイルは、統一された実行可能要素をもたらすリンクステップへの入力として用いることができる。
【００８３】
ハードウェアロジックモジュール情報ファイル：概念および構造
コンパイルシステムの別の構成要素は、オペレータ、組込関数コール、および既存の（規定されたシステムの）ハードウェアロジックモジュールへのＭＡＰプロシージャのソースにおけるプロシージャコールのマッピングを示すデータベースである。このデータベースはシステムinfoファイルと呼ばれる。
【００８４】
選択的に、ユーザは追加のハードウェアロジックモジュールを定義してもよく、このモジュールは、ＭＡＰプロシージャのソースにおけるプロシージャをコールするようにコールされてもよく、またはシステムinfoファイルに記載された組込システムで定義されたハードウェアロジックモジュールを再定義するために用いられてもよい。ユーザが定義したハードウェアロジックモジュールを用いたＭＡＰのためのコンパイルを行なうために、ユーザは、ユーザが定義したハードウェアモジュールにオーバーロードされたプロシージャの名前またはオペレータをマップするデータベースを提供しなければならない。
【００８５】
コンパイルされるＭＡＰプロシージャのデータフローグラフ表現のノードにおけるすべてのオペコードがinfoファイルエントリで定義されなければならない。
【００８６】
ハードウェアロジックモジュール情報ファイルは、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータのデータフローグラフ生成部、およびＣＦＧ−ＤＦＧからＨＤＬへのコンバータのコンパイルのVerilog生成段階の双方によって用いられる。
【００８７】
ハードウェアロジックモジュール情報ファイルは、単一のファイルに連結される１つ以上のエントリを含む。各エントリは、データグラフにおいて示される一意の演算（オペコード）または、コンパイルされるＭＡＰプロシージャからのコールを通してインスタンス化された関数またはサブルーチンを示している。この記述は、ハードウェアロジックモジュールへのインターフェイスを含み、これはその入力、出力、モジュールが接続されるべきいかなる入力または出力信号、およびハードウェアロジックモジュールの特徴を含む演算を行なうように、インスタンス化されるべきである。選択的に、入力は機能的に等しい擬似コードを含んでもよく、このコードは、データフローグラフのエミュレートモード、またはモジュールの機能性をエミュレートする／シミュレートするためのさまざまなシミュレーションモードで用いられてもよい。
【００８８】
ハードウェアロジックモジュール情報ファイルエントリは、開始-defおよび終了-defマ
ーカで区切られ、以下の形をとる。
【００８９】
【数３】
2010146577.tif 000005
【００９０】
<opcode>は、演算に対応するデータフローグラフにおけるオペコードに一致するＡＳＣＩＩストリング、またはＭＡＰプロシージャのソースコードでコールされるプロシージャの名前である。この<mapping and emulation information>は、入力のシーケンスからなり、各々はセミコロンで終わる。ハードウェアロジックモジュール情報ファイルエントリのこれらのセクションの順序は重要ではない。
【００９１】
【数４】
2010146577.tif 000006
【００９２】
<macro_name>は、ハードウェアロジックモジュール情報ファイルエントリが示す演算またはプロシージャの機能を果たすハードウェアロジックモジュールの名前を示すＡＳＣＩＩストリングである。
【００９３】
【数５】
2010146577.tif 000007
【００９４】
<num>は、ハードウェアロジックモジュールの入力へのデータの提示および出力に関する対応する結果の可用性の間のクロックサイクルの数を指定する整数値である。
【００９５】
【数６】
2010146577.tif 000008
【００９６】
ＹＥＳは、ハードウェアロジックモジュールが典型的に内部レジスタにおける反復の間の状態を保持することを指し、ＮＯはそれが保持しないことを指す。
【００９７】
【数７】
2010146577.tif 000009
【００９８】
ＹＥＳは、ハードウェアロジックモジュールがそのコードブロックの外部のエンティティと対話することを指し、ＮＯはそれが対話しないことを指す。
【００９９】
【数８】
2010146577.tif 000010
【０１００】
ＹＥＳは、ハードウェアロジックモジュールが各クロックで新しい入力を受取ることができるようにパイプライン化されることを指し、ＮＯはそうでないことを指す。
【０１０１】
【数９】
2010146577.tif 000011
【０１０２】
<num>は、ＭＡＰプロシージャのソースにおける演算もしくはプロシージャへの、またはデータフローグラフでそれを示すノードへの入力もしくは出力の数である。入力または出力規則子で指定された<num>入力または出力の仕様がなければならない。
【０１０３】
各<input spec>は以下の形をとる。
【０１０４】
【数１０】
2010146577.tif 000012
【０１０５】
各<output spec>は以下の形をとる。
【０１０６】
【数１１】
2010146577.tif 000013
【０１０７】
<ｎ>は、ＭＡＰプロシージャのソースにおけるもしくはデータフローグラフのノードにおける演算またはプロシージャコールへのゼロに基づく入力もしくは出力シーケンスの数を指定している。入力および出力の番号付けは独立しており、各々はゼロから始まる。
【０１０８】
<type>は、入力または出力のデータタイプである。これは、ＩＮＴ，ＦＬＯＡＴまたはＡＤＤＲＥＳＳであるかもしない（これは追加のタイプ、COMPLEX, LOGICAL, REAL, INTEGER, CHAR, CHARACTERを含むように拡張される）。<input_port_name>および<output_port_name>は、関連のハードウェアロジックモジュールの対応する入力または出力ポート名を示している。
【０１０９】
【数１２】
2010146577.tif 000014
【０１１０】
これらは、ソースコードまたはデータフローグラフのレベルでは見ることのできないハードウェアロジックモジュール接続を示している。<nbits>は、入力または出力信号のビット数である。<macro_port_name>は、ハードウェアロジックモジュールへの信号（IN_SIGNAL）のまたはそこからの信号（OUT_SIGNAL）の名前である。<internal_signal_name>は、ソース（IN_SIGNAL）、またはコンパイルされたハードウェアロジックにおける目標の（OUT_SIGNAL）信号の名前である。
【０１１１】
現在のところ３つの内部ソース信号が利用可能である。
【０１１２】
【数１３】
2010146577.tif 000015
【０１１３】
ＣＬＯＣＫは、すべてのハードウェアロジックモジュールのクロックソースである。rstは一度限りのグローバルリセットである。code_blok_resetは、ハードウェアロジックモジュールのコードブロックを起動したときに常に起動されるリセット信号である。
【０１１４】
現在目標とされる信号は記録されていない。これらは、将来的にハードウェアロジックモジュールの実行の際に検出される、エラー、オーバーフロー、または例外条件を含む。
【０１１５】
【数１４】
2010146577.tif 000016
【０１１６】
<simcode>は、データフローのエミュレーションの際にハードウェアロジックモジュールの動作を機能的に定義するものとして用いられるＣコードである。
【０１１７】
ハードウェアロジックモジュールのこれらのまたは追加の特徴の変化を指定するハードウェアロジックモジュールの情報ファイルエントリへの構文拡張が計画される。これらの特性の変化および追加は、ｎ回の反復ごとに新しい入力を受信することができる、およびｎ回の反復のための入力を受信し、かつｊのクロック期間の後でｉを生成することのできるハードウェアロジックモジュールの記述、ハードウェアロジックモジュールが実行される頻度を指定する手段、実際のコードまたはシミュレーションのためにハードウェアロジックモジュールを定義するＨＤＬコードを含むファイルへのディレクトリパス(path）、およびハードウェアロジックモジュールのためのリソース要求の仕様を含むが、これらに限定されない。
【０１１８】
ハードウェアロジックモジュール情報ファイルの翻訳
データフローグラフに加えて、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータへの第２の入力ファイルがある。これは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータバイナリファイルであり、このファイルは、インターフェイスおよびハードウェアロジックモジュール情報ファイルに含まれるハードウェアロジックモジュールに関する情報を含む。本発明の実施例において、小さな実行可能要素を用いてもよく、この要素は、ＡＳＣＩＩハードウェアロジックモジュール情報ファイルをＣＦＧ−ＤＦＧからＨＤＬへのコンバータの内部テーブルに翻訳し、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータをコールする前にコンパイルの際に実行される。
【０１１９】
この翻訳プログラムは、１つの必須のおよび２つの選択的なコマンドラインのオプションでコールされ得る。必須のオプション、-o outfileは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルが書出されるべき出力ファイルの名前を示している。オプション−ｄdeleted_signalは、無視されるべきハードウェアロジックモジュール情報ファイルの入力および出力信号の名前を示している。すなわち、翻訳プログラムは、a−ｄオプションで指定されたハードウェアロジックモジュール情報ファイルでdeleted_signalとよばれる信号の処理をスキップする。これによって、ハードウェアロジックモジュールのためのハードウェアロジックモジュール情報ファイルのエントリは、実際のハードウェアロジックを生成するときに存在しないかもしれない、シミュレーションで用いられる検査信号または信号を含むことができる。第２の選択的なコマンドラインの引き数は、-r sigval=newsigvalである。この翻訳プログラムは、ハードウェアロジックモジュール情報ファイルにおけるsigvalによって指定されたピンまたはワイヤ名の出現を、結果として生じるＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルにおけるストリングnewsigvalと置き換える。このオプションによって、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータによって接続されるべきハードウェアロジックモジュールの入力および出力信号の改名が可能になる。ＣＦＧ
−ＤＦＧからＨＤＬへのコンバータは、名前が“unconnected_”で始まるワイヤに接続されるべきいかなる接続も無視し得る。このオプションによって“unconnected_”ワイヤを改名することによって、これらはＣＦＧ−ＤＦＧからＨＤＬへのコンバータによって処理され得る。−ｄオプションに関して、−ｒはVerilogのようなＨＤＬを生成するときに有用であり、Verilogは、テストベンチまたはシミュレーション環境において用いられ、結果として生じるハードウェアロジックのために生成されたVerilogには実際に存在しない信号を有し得る。多重の−ｄおよび−ｒのオプションを指定してもよい。
【０１２０】
翻訳プログラムは、構築されるべきＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルを初期化し、かつＣＦＧ−ＤＦＧからＨＤＬへのコンバータサポートライブラリにおけるgr_tables_initをコールすることによって開始され得る。次に、コマンドラインオプションが処理され得る。−ｄコマンドラインオプションによって指定された削除済信号のリストを含むキャラクタポインタのアレイが構築される。２つの並列のアレイのキャラクタポインタは、改名された信号（−ｒオプション）のために構築される。第１のアレイはオプションにおけるsigvalで指定されたストリングを含み、第２のアレイはオプションにおけるnewsigvalで指定されたストリングを含む。第１のアレイにおける所与の改名された信号について、その対応する新しい名前は、第２のアレイの同じ索引に配置される。−ｏオプションで指定された出力ファイル名は、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータOUTPUT_FILESテーブルに挿入される。
【０１２１】
テーブルが初期化され、かつコマンドラインが処理された後で、ハードウェアロジックモジュール情報ファイルはパーズされ、subrefデータ構造のアレイが構成される。任意の数のエントリを含む２つのハードウェアロジックモジュール情報ファイルがあるかもしれない。１つのハードウェアロジックモジュール情報ファイルは、インターフェイスを含むものと想定され、このインターフェイスはコンパイルシステム（組込み演算）に知られる特定のハードウェアロジックモジュールへのデータフローグラフのノードで現れるオペコードをマップするものである。このハードウェアロジックモジュール情報ファイルは、システムハードウェアロジックモジュール情報ファイルと呼ばれ、環境変数を読出すことによって配置される。オプションとしての第２のハードウェアロジックモジュール情報ファイルは、本来コンパイラには知られていないハードウェアロジックモジュールを備えたユーザ、および組込みハードウェアロジックモジュールのいずれの再定義をも与えられたいかなるユーザに対するインターフェイスを含む。ハードウェアロジックモジュール情報ファイルのパーズおよびsubref構造のアレイの生成は、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータと共有される機能、fetch_all_subrefによって行なわれる。fetch_all_subrefのパーザおよび意味ルーチンは、ＧＮＵツールのフレックス（flex）およびバイソン（bison）によって生成され得る。
【０１２２】
subref構造を用いて、翻訳プログラムおよびＣＦＧからＣＦＧ−ＤＦＧへのコンバータの内部にあるハードウェアロジックモジュール情報ファイルに情報を記憶する。各オペコード情報ファイルの定義がパーズされると、情報はsubref構造に記憶される。パーズは、すべてのハードウェアロジックモジュール情報ファイルがパーズされ、かつsubref構造のアレイが構築されるまで継続される。翻訳プログラムは次に、一度に１つのsubref構造を処理するアレイを通してループに入り、一方でハードウェアロジックモジュールインターフェイスを保持するＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルを構築する。
【０１２３】
subref構造を処理することによって構築されたＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルは、ＥＱＵＩＶ＿ＩＮ, ＥＱＵＩＶ＿ＯＵＴ, ＥＱＵＩＶ＿ＩＮ＿ＰＲＳ,ＰＩＮ＿ＮＡＭＥＳ,ＨＥＬＤ,ＢＥＨＡＶ＿ＶおよびＢＥＨＡＶ＿Ｃである。これらのテーブルの各々の内容は、（以下の）subref構造の処理の説明で示される。処理される各subref構造のために生成された１つのＥＱＵＩＶ＿ＩＮおよび１つのＥＱＵＩＶ＿ＯＵＴテー
ブルエントリがある。所与のsubrefのためのＥＱＵＩＶ＿ＩＮおよびＥＱＵＩＶ＿ＯＵＴテーブルエントリのテーブル索引は同じである。
【０１２４】
subref構造の処理は、subref構造のオペコードの名前欄を検査することによって開始される。ハードウェアロジックモジュール情報ファイルエントリで名前が指定されていなければ、エラーが出され、現在のsubref構造の残りがスキップされる。名前が指定される場合、以前のsubref処理から構築されたＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルは、同じオペコード名を有する以前のsubrefがないかを探索される。これが見つかった場合、警告が発せられ、重複して名前をつけられたsubrefの一層の処理がスキップされ得る。オペコード名のための第１のハードウェアロジックモジュール情報ファイルエントリが用いられる。なおユーザの情報ファイルエントリがパーズされる最初のエントリであり、その対応のsubref構造は最小のアレイ索引を有するsubrefアレイで現れる。したがって、ユーザは本来コンパイラに知られるいかなる所与のオペコードのための独自のハードウェアロジックモジュールを提供し得、subrefアレイの処理の順序のために、そのオペコードのためのユーザのinfoファイルエントリは、システムのinfoファイルにおけるいかなるエントリとも置き換えられる。
【０１２５】
ＥＱＵＩＶ＿ＩＮ＿ＰＲＳにおける最初の自由なエントリの索引が保存され、後で現在のハードウェアロジックモジュール情報ファイルエントリのためのＥＱＵＩＶ＿ＩＮテーブルエントリに置かれる。これを用いて、ハードウェアロジックモジュールのための第１の入力パラメータを置く。ハードウェアロジックモジュールの待ち時間は、現在のinfoファイルエントリのためのＥＱＵＩＶ＿ＯＵＴテーブルエントリに後で挿入するために保存される。待ち時間が指定されていないまたはそれが負である場合、エラーが出されて、ゼロの値が待ち時間のために用いられる。
【０１２６】
出力パラメータが最初に処理され得る。各出力について、ＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリが生成される。出力のビット幅およびこのsubrefのためのＥＱＵＩＶ＿ＩＮ／ＥＱＵＩＶ＿ＯＵＴテーブルエントリへの索引がＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリに挿入される。これが出力であることを示すフラグがＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリに設定されて、これを入力と区別する。次にＰＩＮ＿ＮＡＭＥＳテーブルエントリが出力パラメータのために生成される。ＰＩＮ＿ＮＡＭＥＳテーブルエントリは、出力パラメータの名前、そのビット幅、その以前に生成されたＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリへの索引、現在のsubrefのＥＱＵＩＶ＿ＩＮ／ＥＱＵＩＶ＿ＯＵＴテーブルエントリの索引、およびこれが出力ピンのセットであることを示すフラグを有する。これが現在のsubref（モジュールのために処理された最初の出力パラメータ）のために生成された最初のＰＩＮ＿ＮＡＭＥＳテーブルエントリである場合、ＰＩＮ＿ＮＡＭＥＳテーブル索引が、現在のsubrefのためのＥＱＵＩＶ＿ＯＵＴテーブルに後で挿入されるために保存される。
【０１２７】
オペコードの出力信号は出力パラメータの後で処理される。出力信号をＣＦＧ−ＤＦＧからＨＤＬへのコンバータＨＥＬＤおよびＰＩＮ＿ＮＡＭＥＳテーブルに入力すべきかどうかを決定するために−ｄコマンドラインオプションによって指定された削除済信号のリストが検索される。これが見つかった場合、信号はスキップされる。そうでなければＨＥＬＤテーブルエントリが生成される。このＨＥＬＤテーブルエントリは、信号のための関連したＰＩＮ＿ＮＡＭＥＳテーブルエントリへの索引、信号のビット幅、および出力信号が接続されるべき外部信号の名前を含む。−ｒコマンドラインオプションで指定された改名された信号のテーブルを検索して、信号が再びマップされたかどうかを見ることができる。再びマップされていれば、再びマップされた信号名が用いられる。そうでなければ、ハードウェアロジックモジュール情報ファイルで指定された名前が用いられる。外部信号名が指定さない場合、エラーが出される。ＰＩＮ＿ＮＡＭＥＳテーブルエントリが、次に
出力信号のために生成され得る。ＰＩＮ＿ＮＡＭＥＳテーブルエントリは、現在のsubrefエントリのためのＥＱＵＩＶ＿ＩＮ／ＥＱＵＩＶ＿ＯＵＴテーブル索引、出力信号のビット幅、この信号のために生成されるＨＥＬＤテーブルエントリの索引、ハードウェアロジックモジュールの内部の信号名、および信号が出力でありかつ信号のためのＨＥＬＤテーブルエントリがあることを示す２つのフラグを含む。これがsubref構造のために処理される最初の信号である場合、ＰＩＮ＿ＮＡＭＥＳテーブルエントリの索引は、subrefのためのＥＱＵＩＶ＿ＯＵＴテーブルエントリに挿入されるために保存される。
【０１２８】
出力信号が処理された後で、subrefのための入力パラメータが処理される。ＥＱＵＩＶ＿ＩＮ＿ＰＲＳおよびＰＩＮ＿ＮＡＭＥＳテーブルエントリが各入力について生成される。ＥＱＵＩＶ＿ＩＮ＿ＰＲＳエントリの内容は、出力パラメータを示すフラグが設定されていないことを除き、出力パラメータのために生成されたものと内容が一致しているかもしれない。ＰＩＮ＿ＮＡＭＥＳテーブルエントリは、出力パラメータを指すフラグではなく、入力を指すフラグが設定されることを除いて、出力パラメータのためのＰＩＮ＿ＮＡＭＥＳテーブルエントリと同じ情報を含む。
【０１２９】
入力信号は入力パラメータの後で処理される。各入力信号について、ＨＥＬＤおよびＰＩＮ＿ＮＡＭＥＳテーブルエントリが生成される。入力信号の処理および結果として生じるテーブルエントリは、信号が出力ではなく入力であることを示しているフラグがＰＩＮ＿ＮＡＭＥＳテーブルエントリに挿入されることを除いて、出力信号のそれと同じである。
【０１３０】
最後のＰＩＮ＿ＮＡＭＥＳエントリがsubrefのために生成され、最後のエントリの索引は、subrefのＥＱＵＩＶ＿ＯＵＴテーブルエントリに挿入するために保存される。
【０１３１】
最終的に、subrefのためのＥＱＵＩＶ＿ＩＮおよびＥＱＵＩＶ＿ＯＵＴテーブルエントリが生成される。このＥＱＵＩＶ＿ＩＮテーブルエントリは、このsubref構造を処理するために生成された最初のＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリの索引を含む。このsubrefのための最後のＥＱＵＩＶ＿ＩＮ＿ＰＲＳテーブルエントリの索引が生成され、テーブルフローグラフのオペコードの名前はこのsubrefが定義する。ＥＱＵＩＶ＿ＯＵＴテーブルエントリは、関連するハードウェアロジックモジュールの待ち時間、ハードウェアロジックモジュールの名前、subrefと関連した第１のＰＩＮ＿ＮＡＭＥＳテーブルエントリの索引、subrefと関連した最後のＰＩＮ＿ＮＡＭＥＳテーブルエントリの索引を含む。
【０１３２】
ここでsubrefの処理が完了する。info2grfはすべてのsubref構造が処理されるまで継続される。処理の際にエラーが発見されなければ、ＣＦＧ−ＤＦＧからＤＨＬへのコンバータテーブルは出力ファイルに書込まれ、ゼロステータスコードが戻される。そうでなければ、テーブルは出力されず、非ゼロステータスコードが戻される。次に翻訳プログラムが終了され得る。
【０１３３】
ＣＦＧからハイブリッドＣＦＧ−ＤＦＧへの変換
ＣＦＧ表現をハイブリッドＣＤＦＧ−ＤＦＧ表現に変換するための実施例がここで説明される。もとのＣＦＧ表現は、ノードおよび有向の辺（directed edges）を含んでもよく、各ノードはコードの基本ブロックであるかもしれず、各辺は１つのブロックの終わりから別のブロックの始めへの制御の移動を示し得る。基本ブロックにおけるコードは、エントランスの単一の点、および単一の出口を有し得、すなわちこれは、始めおよび終わりのそれぞれ以外へ、またはそれ以外から分岐することのできない直線のシーケンスの文を示し得る。基本ブロックにおける文は連続しているかもしれない。
【０１３４】
ハイブリッドＣＦＧ−ＤＦＧ表現は、その上位レベルでＣＦＧ表現を有し得るが、各コ
ードブロックにおいてデータフローグラフを有する。一実施例において、ＣＦＧからＣＦＧ−ＤＦＧへの変換は、内部ループをフラットであるいはパイプライン化されたコードブロックへと形成するグループを含む基本ブロックのグループを統合し得る。
【０１３５】
図７は、以下のコードフラグメントに対応するＣＦＧの一部の例を示している。
【０１３６】
【数１５】
2010146577.tif 000017
【０１３７】
この例において、‘ａ’および‘ｂ’を比較する条件テストは、レジスタまたは一時変数に記憶され得、これはその基本ブロックにおける最後の文であるかもしれない。比較の結果に基づいて、制御は条件付き構成体の「真」および「偽」の部分を示す２つのブロックのうちの１つに移動され得る。これらのブロックの各々は、その文を実行した後で、制御を条件に従うコードを含むブロックに移動し得る。なお、ＣＦＧにおけるコードブロックは順次の文を含み得、この各々はレジスタまたは変数を読出し、書込むことによってこれらを参照し得る。さらに、ブロック間の有向の辺は、１ビットの「トリガ」信号としてみなされる制御の移動を示し得ることに注目されたい。
【０１３８】
ＣＦＧ表現は内部中間表現のように多くのコンパイラにおいて用いられるかもしれないが、データフローグラフは通常用いられない。なぜなら、データフロー実行パラダイムは、任意の多くの機能ユニットの使用および非同期の実行のため、従来のノイマン型プロセッサにあまり適していないからである。しかしながら、データフローモデルは再構成可能なハードウェアに非常に適切である。データフローグラフにおいて、ノードは機能ユニット（たとえば整数の加算）を示すかもしれない。ノード間の有向の辺は、１つの機能ユニットからの出力データ項目を他の機能ユニットの入力にもたらすデータ接続を示し得る。図４は以下のコードフラグメントのデータフローグラフを示している。
【０１３９】
【数１６】
2010146577.tif 000018
【０１４０】
入力値の‘ｂ’および‘ｃ’がグラフの上部にロードされ得る。これらの値はＬＯＡＤノードの出力ポート（底部）から流れ得る。データフローグラフでは、命令レベルの並列性が明らかにされ得る。ここで、３つの命令（２つの乗算および１つの減算）が同時に起こり得る。なお、‘ｄ’変数は記憶を必要としないかもしれない。なぜならこれはグラフ
のローカルにあるかもしれず、辺として存在するかもしれないからである。さらに、‘ａ’に割当てられた中間値はその変数に記憶されず、単に辺として存在するかもしれない。なぜなら以下の順次の割当では‘ａ’の最終値が生成されるかもしれないからである。このようなデータフローグラフは、選択された機能ユニットを初期化することによって、再構成可能なハードウェアに直接マップされ得る。この例において、１つの加算、２つの減算、および２つの乗算が生成される。
【０１４１】
ＣＦＧ表現の各基本ブロックにおいて連続している文は、データフローグラフに変換されることにより、ハイブリッドを生成し、このハイブリッドで上位レベルのノードはシングルビットの辺を有するコードブロックであり、各ブロック内では、ノードが機能ユニットであり、かつ辺がデータ接続であるデータフローグラフであってもよい。図８は、図７のＣＦＧに適用されたこのような変換の例を示している。
【０１４２】
本発明の実施例において、ＣＦＧ表現における基本ブロックの部分集合は、単一のデータフローコードブロックにマージされ、条件は、双方の側を計算し、次に条件の述語式に基づいて適切な値を選択することによって処理され得る。図９は、このようなコードブロックの例を示しており、ここでは図８のコードブロックがマージされる。
【０１４３】
スカラおよびアレイデータのタイプに加えて、高級言語は、より単純なタイプの複合であってもよいユーザ指定のデータタイプの構造を有し得る。従来のコンパイラのフロントエンドは、ＣＦＧ表現を生成するときに、生成する基本ブロックにおいて適切なアドレス計算をもたらすことによってこれらを処理し得る。このような構造がローカルメモリであるときに、アドレス計算は、グラフをコントロールデータフローグラフに変換する際に変更されないままであってもよい。ローカル変数としての構造の場合、変換プロセスは、アドレスのオフセットとともにタイプ情報を用いて、構造のどのフィールドが参照されるべきかを決定する。
【０１４４】
ポインタは、目標のマシンのアーキテクチャの詳細に従って扱われ得る。再構成可能なハードウェアが、それに対するアドレスパラメータを渡したプロセッサと同じメモリ空間を「見つけた」場合、ポインタ演算は修正されずに作用し得る。これを見つけられなかった場合、調整因子がランタイムで計算される。この因子は、プロセッサのメモリにおけるアドレスおよび、データが再構成可能なハードウェアのＯＢＭにコピーされた場所の差であるかもしれない。制御データフローグラフは、ポインタを参照するときにこの因数の加算を含み得るように生成される。
【０１４５】
従来の高級言語は、小さな組をなす固定サイズの算術データタイプ（たとえば３２ビットおよび６４ビットの整数）を有し得る。これは、目標にするノイマン型プロセッサが固定サイズの機能ユニットを有し得るということに対応している。再構成可能なハードウェアにおいて、いかなるビット幅の機能ユニットもインスタンス化することが可能であってもよく、これは所与のプログラムに必要とされる量の精度を用いることによってスペースの節約を達成し得る。この節約を行ない得る１つの方法は、高級言語をユーザ指定のビット幅を有する新しいデータタイプを含むように拡張することであってもよい。別のアプローチは、ユーザがソースコードのセクションのための標準タイプ（たとえば“int”）のビット幅を指定することができるようにすることであってもよい。
【０１４６】
コンパイラが、一部の機能ユニットおよびそれらが接続されるデータ経路の精度を減じることの安全性を推論することが可能であってもよい。たとえば、
【０１４７】
【数１７】
2010146577.tif 000019
【０１４８】
のコードにおいて、加算の演算を８ビットの加算器に変更することが無難であるかもしれない。なぜなら、高いビットの結果は、その結果を割当てるときに失われるかもしれないからである。
【０１４９】
別の実施例において、ＣＦＧ表現の制御データフローグラフへの翻訳の構成要素は、オペレータおよび既存のハードウェアロジックモジュールへの関数コールのマップを記述するデータベースであるかもしれない。このデータベースは、「infoファイル」と呼ばれてもよく、コンパイルの際にさまざまなステップで用いられてもよい。
【０１５０】
関数コールは、コールされるルーチンの性質に依存してさまざまな方法で扱われ得る。すなわち、ルーチンがハードウェアロジックモジュールを有する「infoファイル」を介して関連付けられた場合、単一のノードがデータフローグラフにおいて生成されて、それを機能ユニットとして示し得る。ルーチンが適切な基準に達した場合、これはコール機構を必要としないようにインライン化され得る。関数が末端再帰的である場合、これはループに変換され得る。関数が上記のカテゴリに当てはまらない場合、スタック志向のコール機構が用いられ得る。別の実施例において、ＬＩＦＯスタックが再構成可能なロジックで実現されてもよく、このロジックは、再帰が起るとローカル変数のさまざまなインスタンス化を保持し得る。スタック情報は、制御の流れを、再帰的なコールの復帰が適切に生じるように導き得る。
【０１５１】
ハイブリッド制御データフローグラフは、それ自身を再構成可能なハードウェアにコンパイルしたサブルーチン内の実行の多重スレッドに適合させ得る。高級言語の意味が順次の実行（１コードブロックはいかなる所与の時間でも活動状態であり得る）を指定する一方で、コードブロックレベルでの並列性は、コンパイラが、並列な実行が不正確な結果をもたらさないと決定することができるときに実現しやすいかもしれない。この決定は、言語およびその可能な拡張に依存してさまざまな方法で行なわれ得る。たとえば、言語が並列の構成体を含む場合、並列性はＣＦＧ表現の一部で生じるかもしれない。さらに、逐次型言語はユーザプラグマによって拡張されてもよく、このユーザプラグマによって、プログラマはコンパイラを、コード並列のある部分を生成するように導くことができる。分析によって、コンパイラは、あるコードブロックが並列した状態で無事に実行され得ることを証明することができる。
【０１５２】
図１１は、左にＣＦＧ表現の順次の部分を、右に２つのコードブロックが並列に置かれた変形されたグラフを有する実施例を示している。先行のブロックからのトリガ信号は、双方の並列したブロックをトリガするように広がり、ＬＡＴＣＨ＿ＡＮＤと呼ばれる「結合」機構を用いて、２つのブロックからの「完了（done）」信号をマージし得る。ＬＡＴＣＨ＿ＡＮＤは、ハイになったときに各入力信号をラッチするように設計されて、当該入来するトリガが同時に起らないようにし得る。
【０１５３】
制御データフローグラフの接続性の情報を用いて、ＦＰＧＡにおける論理配置の性能を向上させ得る。現在の位置およびルートツールにおいて、配置の問題は非常に低位レベルで見られ、配置される項目は非常に小さな論理ブロックであってもよい。コンパイラが利
用できるハードウェアロジックモジュールが指定された形状であると既に決定されている場合、コンパイラは、さらに高度な、したがってさらに単純な細分性のレベルで配置を行い、プロセスを潜在的にかなり高速化することができる。
【０１５４】
図１２は、サブルーチンのＣＦＧ表現をハイブリッド制御データフローグラフに変換するための最高レベルにおけるプロセスを示す。１つ以上の「infoファイル」が読込まれて、再構成可能ロジックとしてのデータフローグラフの実現のために利用可能であり得る利用可能なハードウェアロジックマクロについての情報が入手され得る。ＣＦＧ表現をその内部データ構造の中に読込んだ後、コンパイラは「外部」ハードウェアロジックモジュールコールを個々のブロックに分離し得る。これが行われ得るのは、外部モジュールがそのコードブロックの外側のリソースと対話し、並行的に実行する場合には乱調状態が結果として生じ得るからである。次に、図１０の例におけるように、個々のブロックはより大きなブロックへと組合せられ得る。
【０１５５】
次に各々のブロックが処理され得る。非ループのブロックの場合、参照される種々のスカラ値についてＬＯＡＤノードが作成され得る。次に、ブロックの計算のデータフローグラフが作成され得る。最後に、ＳＴＯＲＥノードは、その終値を記憶するための各々のスカラ変数について作成され得る。内部ループはいくらかの追加の処置を必要とし得る。内部ループのヘッドブロックが見つかると、このループのブロックの残りが集められて位相的にソートされ得る。次に、ＬＯＡＤおよびＣＩＲＣＵＬＡＴＥ（循環）ノードが当該のスカラについて構築され得る。次に、ループのコードブロックは、非ループブロックのそれに類似の方法で処理され得る。
【０１５６】
各々のＤＦＧが作成された後、データフローグラフを通じて（クロックの刻みで測ることのできる）経路長さのバランスをとるために遅延ノードが挿入され得る。次に、上記グラフに対して種々の最適化が実行され得る。ＤＦＧがすべて作成された後、これらはＤＦＧファイルに書込まれてロジックエミュレートファイルが作成され得る。
【０１５７】
ＣＦＧ表現は２つの部分、すなわち、オペコードのアレイと基本ブロックのシーケンスとから構成され得る。オペコードは、構造からなるアレイであってその要素が１オペコードとこのオペコードのデータソースへの参照とからなる、構造からなるアレイに読込まれ得る。ＣＦＧ表現における各々の基本ブロックは、以下に示すような構造内に記憶され得る。
【０１５８】
【数１８】
2010146577.tif 000020
【０１５９】
或るブロックについてデータフローグラフが構築されると、そのノードは基本ブロック構造の「プール」フィールドの中で割付けられ得る。データフローノード構造の一例を以下に示す。
【０１６０】
【数１９】
2010146577.tif 000021
【０１６１】
一実施例では、出力として２つのファイルが書込まれ得る。すなわちデータフローグラフファイルとエミュレートロジックファイルとである。これらのファイルの例として以下の単純なＣソース関数があり得る。
【０１６２】
【数２０】
2010146577.tif 000022
【０１６３】
以下のコードの例は、Ｃ関数の例がコンパイルされると生成され得るデータフローグラフファイルを示す。
【０１６４】
【数２１】
2010146577.tif 000023
【０１６５】
上記のデータフローグラフの例は２つのセクションを有する。その第１はパラメータおよびローカル変数のリストであり、名前、タイプおよび種類（パラメータまたはローカル
）による。第２のセクションはコードブロックをリストにしたものである。この例においては、コードブロックはマージされていない。各々のブロックは一義的なＩＤ数および１組のデータフローノードを有する。各ブロックはいずれも、その始まりのノードおよび終わりのノードとしてＳＲＣ＾ＩＮＩＴＩＡＴＥ（開始）ノードおよびＳＲＣ＾ＯＵＴＰＵＴ（出力）ノードを有する。各々のノードにつき以下の情報がある。すなわち、その機能、その入力および出力カウント、各々の入力のビット幅、入力が定数として指定される入力についての定数値、各々の出力のビット幅、各々の出力の目標リスト（すなわち他のノード入力ポートのうちどれがこの出力によって供給がなされるのか）、である。入力および出力ポートはまた括弧の中に一義的な擬似レジスタＩＤを有し得る。
【０１６６】
各々のブロックの終りは、ブロックから出るときに制御フローがどこへ行くのかを指定し得る。ブロックが条件文で終わるときには、２つの目標ブロックがＴＲＵＥおよびＦＡＬＳＥ目標として指定され得る。他では、１つのブロックが指定され得るか、または、ブロックが関数の終了であれば、ＥＸＩＴが指定され得る。図１３はこのコードブロック組を図示するものである。
【０１６７】
データフローグラフファイルとともにエミュレートロジックファイルもまた書込まれ得る。これはスレッドとして実行され得る単純なＣルーチンであって、プログラムの再構成可能ロジック部分をエミュレートするものであり得る。Ｃ関数の例についてのエミュレートロジックファイルの一例を以下に示す。
【０１６８】
【数２２】
2010146577.tif 000024
【０１６９】
上記のエミュレートロジックファイルの例では、無限ループがＦＰＧＡとして働き得る。したがってこれは同じプロトコルに従ってもよく、この例では開始および終了ハンドシェイクとしてそれぞれフラグレジスタＦＲ２およびＦＲ４を用いる。それが開始信号をＦＲ２から受取ると、エミュレートルーチンはユーザサブルーチンのパラメータについての初期値をロードし得る。次にdfg_simulateがコールされて、実行されるべきＤＦＧファイルの名前が中へ通され得る。データフローシミュレータはトークン駆動シミュレーションを行ないＥＸＩＴコードブロックの完了時に戻り得る。それからパラメータの終値が返されてこれにＦＲ４ハンドシェイクが続き得る。次にルーチンはループの最上部へ戻って、実行すべき次の信号を待つことができる。
【０１７０】
次に、ＣＦＧにおける基本ブロックの、ＤＦＧにおけるコードブロックへの変換についての別の実施例について説明する。この実施例においては、ロード／記憶は、スカラ参照であるかアレイ参照であるかに依存して２つの異なる方法で扱われ得る。スカラ参照はＤＦＧ辺に変換され得るが、ここで単一のロードがブロックの開始部にあり、単一の記憶が終了部にある。アレイ参照はオンボードメモリ（ＯＢＭ）参照へと変換され得る。
【０１７１】
参照渡し（pass-by-reference）パラメータについてのスカラ変数参照はローカル変数参照とは異なり得る。コンパイラのフロントエンドのＣＦＧ出力はこれを反映し得る。すなわち、或るレベルの間接をこのようなパラメータ参照の中に置くことがあり得る。図１４はこの相異を例示する。
【０１７２】
別の例として以下の演算の組について検討する。
【０１７３】
【数２３】
2010146577.tif 000025
【０１７４】
図１５に示すように、フロントエンドはそのＣＦＧ出力において１組のオペコードを生成し得る。これはFortranソースであったため、スカラは参照によって持ち込まれ得て、ＬＤＡ（ロードアドレス）ノードは、これに入力され得るアドレスからアドレスをフェッチすることで間接ステップを実行することができる。
【０１７５】
グラフ共有は共通の部分式を表わさないこともあることに注目されたい。たとえば、ノードの出力は２つの場所に行ってコードにおいて変数‘ｃ’についての２つの読取値を表わす場合がある。しかし、これら２つの読取値は同じ値を生成しないことがあるが、それはその間に介在する記憶があり得るからである。
【０１７６】
一実施例において、基本ブロックの処理における最初のステップは、オペコードからデータフローグラフフラグメントを構築することであり得る。これは、各々のアンカー（最下部）オペコードで開始しその上に再帰的に木を構築するルーチンによって行なわれ得る。フラグメント間での共有はあり得ないため、このルーチンの結果は図１６に示すフラグメントを構築することであってもよい。
【０１７７】
一実施例において、ＤＦＧフラグメントの構築後、スカラ参照渡しパラメータを担うＡＣＯＮ（アドレス定数）の下からＬＤＡノードがなくされ得る。これが反映しているのは、ＭＡＰコンパイラ（すなわちシステムのうち、再構成可能ハードウェアへＨＬＬソースコードの一部をコンパイルする部分）がこれを参照によってではなくコピー・アンド・リストアとして扱い得る、という事実である。これに伴い、ＤＦＧフラグメントは図１７に示すようなものとなり得る。
【０１７８】
次に、アンカーから始まって上方を向いてＡＣＯＮを見つけることにより、参照される変数すべてのリストが作成され得る。ＤＦＧのヘッドとしてＩＮＩＴＩＡＴＥノードが作成され、スカラの初期値を持ち込むためのＬＤ＿ＳＣＡＬＡＲノードの層が作成され得る。データ構造の一時アレイが各々の変数のソースについての参照として作成され得る。この構造の一例を以下に示す。
【０１７９】
【数２４】
2010146577.tif 000026
【０１８０】
このアレイを初期化してそのＬＤ＿ＳＣＡＬＡＲノードに変数すべてを参照させることができる。サブルーチンおよび関数コールが処理されてからＤＦＧフラグメントがＤＦＧへ変換され得る。
【０１８１】
一実施例において、ＣＦＧからＤＦＧへの変換は、各々のＤＦＧフラグメントの最下部で開始して以下のことを行なうルーチンであり得る。すなわち、上方へスキャンしてロードノードを見つける。各々のロードにつき、その上にあるＡＣＯＮを見てどの変数がロードされているかを決定する。ロードノードをなくしてから目標となっているノードを配線し直し、この変数の現在のソースによって供給がなされるようにする。アンカーがスカラの記憶であれば、右側の入力を見てどの変数が記憶されているかを判断する。次に、記憶ノードがなくされてノードの左のソースがその変数についての新たなソースとして記録され得る。
【０１８２】
この例においては、最初のアンカーが処理されると、値‘ｂ’および‘ｃ’についてのＬＤＫＲノードを見つけることができる。これらはなくすことができ、これらが供給をするノードを配線し直してＤＦＧの最上部にあるＬＤ＿ＳＣＡＬＡＲノードから供給がなされるようにできる。次に、ＳＴＫＲノードをなくしてＫＡＤＤノードを一時アレイにおいて変数‘ａ’の新たなソースであるとして示すことができる。次のアンカーが処理されると、その２つのＬＤＫＲノードを見つけることができる。‘ｂ’値のソースはなおそのＬＤ＿ＳＣＡＬＡＲノードであり得るが、‘ａ’値のソースはＫＡＤＤであり得る。ＬＤＫＲノードをなくしてその目標を適当なソースへ配線することができる。次にＳＴＫＲノードをなくしてＫＳＵＢノードを変数‘ｃ’の新たなソースとして示すことができる。３番目のアンカーが処理されると、そのＬＤＫＲをなくしてその目標をＫＳＵＢの出力へ配線し直すことができる。次に、ＳＴＫＲをなくしてＫＭＵＬを変数‘ａ’の新たなソースとして示すことができる。
【０１８３】
アンカーがすべて処理された後、ＳＴ＿ＳＣＡＬＡＲノードの層を作成することで、スカラの終値を、これら変数の最後のソースを参照することで記憶させることができる。ＳＴ＿ＳＣＡＬＡＲはＬＡＴＣＨ＿ＡＮＤノードへと集められ得るトリガ出力を有し、このノードはＤＦＧの最下部にあるＯＵＴＰＵＴノードの供給をすることができる。出力が未使用であるＬＤ＿ＳＣＡＬＡＲノードはいずれも用済みコード除去パス（pass）によってなくされ得る。コンパイラはまた、この変数のＬＤ＿ＳＣＡＬＡＲノードから来る値を記憶しているＳＴ＿ＳＣＡＬＡＲノードを探すことができ、これらについての値は変化していないのでこれらをなくすことができる。図１８は、この例についての結果のＤＦＧコードブロックの一例を示す。
【０１８４】
一実施例において、ＤＦＧ生成部は、スカラ変数のロード／記憶とアレイ要素のロード／記憶とを区別し得る。ＤＦＧ発生器はロードまたは記憶ノード（たとえばＬＤＫＲまたはＳＴＫＲ）を見ると、そのアドレス入力を見ることでロード／記憶の種類を決定することができる。図１４に示す形での何かを見ると、ＡＣＯＮノードを用いて変数の名前を見つけることができ、内部「変数」データ構造を調べてこれがスカラ変数であるかどうかを判断することができる。
【０１８５】
図１９はアレイ参照の一例を示す。ハードコードされた「１」索引のこの例においては、参照は構造的にスカラローカル変数参照と同じように現われ、「変数」構造を調べることでこれがアレイであり得ると知られ得ることに注目されたい。また、ＡＣＯＮノードが変数名および定数オフセットを有し得ることに注目されたい。図１９における２番目の例では、参照が基底アドレスから６要素離れておりかつ各々の要素のサイズは８バイトであるという事実から４８のオフセットが導き出される。３番目の形では、アドレスは表現木によって供給がなされる。ここでは‘ＢＢ’についてのＡＣＯＮノードには−８のオフセットが与えられ、アレイの索引が１で始まるという事実を補償している。アドレスはバイト指向であるためＩＭＵＬノードは８倍し得る。
【０１８６】
アレイ参照についてのロードおよび記憶ノードを定位置に残しておくこともできるが、各々の記憶ノードには追加のイネーブル入力を与えることもできる。基本ブロックの場合、このイネーブル入力はブロックのＩＮＩＴＩＡＴＥノードによって供給がなされ得る。
【０１８７】
もう１つの、ブロックのＣＦＧがＤＦＧに変換される実施例においては、アンカーは記憶でなくサブルーチンコールであり得る。以下のコードフラグメントを検討する。
【０１８８】
【数２５】
2010146577.tif 000027
【０１８９】
このコードについてのフロントエンド出力を図２０の左に示す。これはＡＲＧＡＲノードについてのリンクされたリストによって供給がなされて、各々が１つの引き数をコールへ持ち込むことがあり得る。ＤＦＧ生成部がオペコードからＤＦＧフラグメントを構築した後、サブルーチンコールアンカーを見つけるルーチンがコールされ得る。これは各々１つにつきＡＲＧＡＲノードについてのリンクされたリストをなくすことができ、複数のコールノードに、それらが配線されている、引き数を有する多重入力を与える。これにはサブルーチンについての知見が必要であるが、これは‘info’ファイルから引出され得る。状態を持つノードについては、イネーブル信号への接続のために付加的な入力が作成され得る。外部ノードについては、トリガおよび完了（done）信号のために付加的な入力および付加的な出力が与えられ得る（このステップが実行されているときにまでにはスカラパラメータのための付加的な間接は既になくされている場合もあることに注目されたい）。
【０１９０】
infoファイルは各々の引き数につきそれが値であるかアドレスであるかを指定し得る。さらに、どれが入力でどれが出力かを指定し得る。入力引き数が値である（しかし定数ではない）場合、適当なロードノードが作成され得る。アドレスである場合には変化のないまま残され得る。この例の場合、これが２入力、１出力のサブルーチンであると仮定する。図２０の中央において、コールがＤＦＧＪＳＲに変換されてＬＤＫＲノードが２つの入力について追加された後におけるサブルーチンコールについてのＤＦＧコードフラグメントが示される。
【０１９１】
サブルーチンコール処理中でその後に、ＤＦＧＪＳＲノードはinfoファイルがもう１回調べられることを引き起こし得る。２つの入力は他のノードへの入力と同じ方法で扱われ得る。すなわち、変数のソースが示され、ＬＤＫＲノードがなくされ、そして入力がソースへ直接配線されるということがあり得る。出力については、入来する辺がなくされ、ＡＣＯＮノードを調べてどの変数が出力値を受取っているかが判断され、そしてこの出力をその変数の新たなソースとして示すということがあり得る。図２０の右側においてＤＦＧ
への変換後の完全なコードブロックが示される。
【０１９２】
組込関数へのコールはＣＦＧ出力において非アンカーＪＳＲおよびＱＪＳＲノードとして現われ得る。サブルーチンコールに対処がなされた後、残っているＪＳＲおよびＱＪＳＲノードは関数コールであり得る。
【０１９３】
このような関数コールの一例を以下に示す。
【０１９４】
【数２６】
2010146577.tif 000028
【０１９５】
この関数コールのもたらすＣＦＧは、その２番目の割当てが図２１に示されるものである場合がある。サブルーチンコールについてと同様、これの引き数はリンクされたリストを形成する。この図の中央に示すように、引き数は多数の入力へと平らにされ得る。この点から、ＤＦＧの構築は一般的な方法で行なうことができ、その結果図２１の右側に示すグラフが得られる。
【０１９６】
基本ブロックは条件文で終わることがある。この場合、ＯＵＴＰＵＴノードへの２番目の入力は比較の結果によって供給がなされ得る。一例として以下のコードを検討する。
【０１９７】
【数２７】
2010146577.tif 000029
【０１９８】
“ａ＝ａ＋１”文は基本ブロックの一部ではないことに注目されたい。このブロックは条件検査で終わる。最後のアンカーはＩＣＪＭＰＺノードであり、その上の構造を図２２の左側に示す。ＱＪＳＲ、ＤＦＲＩＲおよびＩＣＪＭＰＺノードはＫＣＪＭＰで取って代わられる。この後、ＫＣＪＭＰがＫＣＭＰ＿ｌｅにされ得る。右側にコードブロックについてのＤＦＧを示し、ここではＫＣＭＰ＿ｌｅノードは‘ａ’の終値によって供給がなされ得てその出力はＯＵＴＰＵＴの２番目の入力へ行く。
【０１９９】
図９および図１０に示したように、基本ブロックは単一の大きなコードブロックへとマージされ得る。このプロセスは、コードブロックの内部の条件文に対処するために、すべての経路を計算し、ＳＥＬＥＣＴＯＲ（セレクタ）ノードと呼ばれるマルチプレクサを用いて適当な値を選択するステップを含み得る。一例として以下のコードを検討する。
【０２００】
【数２８】
2010146577.tif 000030
【０２０１】
この例においては、ａａ＋１およびａａ−１両方の式は各々の反復において計算され、‘ＢＬ’アレイに割当てられた‘ｂｂ’値はＳＥＬＥＣＴＯＲによって供給がなされる。マージされたコードブロックをさまざまな基本ブロックから構築するジョブは、個々のブロックについてＤＦＧセグメントを構築するステップと、条件文の述語表現から導き出された制御信号およびセレクタを用いてこれらを配線し合わせるステップとを含み得る。
【０２０２】
一実施例において、マージされたコードブロックの作成における最初のステップは、マージされた基本ブロックを位相的にソートするステップを含み得る。ブロックが処理される際、所与のブロックに制御を供給するブロックはそのブロックの変換前に変換され得る。処理における早いステップにおいて、各々のブロックは個々のブロックに類似のＤＦＧに変換され得る。ＬＤ＿ＳＣＡＬＡＲノードはＤＦＧの最上部に構築され得る。次に、コードブロックが変換され得る。マージされたコードブロックと個々の基本ブロックとの相異は、ブール制御信号およびセクタノードフックアップ（selector node hookup）を含み得る。
【０２０３】
一例として、マージされるべき１組のブロックにおける恣意的なブロック‘Ｂ’であって、３つのブロックが制御を‘Ｂ’に送ることができ、‘Ｂ’が制御をその終了時に２つのブロックのうちの１つに送る、ブロック‘Ｂ’について検討する（制御をブロックに送ることができるブロックの数は任意であるが、所与のブロックは２つのブロックに制御を送ることに注目されたい）。図２３の左側にこれを示す。制御をブロック‘Ｂ’に転送していればハイ（high）である入来するブロックの各々からの１ビット信号があると仮定する。ブロック‘Ｂ’のアクティブ信号は、入来する信号の論理和（ＯＲ）をとることで計算される。次に、ブロック‘Ｂ’は、自らが起動し得る２つのブロックについて起動信号を計算し得る。‘Ｂ’は、２つのブロックを起動できるので条件文で終わる。この条件文の述語とブロックの起動信号との論理積（ＡＮＤ）をとることにより、「真」の信号についての起動信号をもたらし、反対の述語とブロックの起動信号との論理積（ＡＮＤ）をとることにより「偽」の信号についての起動信号をもたらす。図２３の右側に、‘Ｂ’においてこれら信号を計算するノードを示す。
【０２０４】
基本ブロックデータ構造は、以下のものを含み得る制御情報を記憶するフィードを有する。すなわち、「入来」フィールドは、現在のブロックへ制御フロー辺を有するブロックのすべてについてのリンクされたリストである。「アクティブ」フィールドは、ノードであってその出力が現在のブロックのアクティブな信号すなわちＯＲノードシーケンスの出力を表わすノード、のＩＤである。“src_true”フィールドは、「真」の出力制御信号を計算するノードのＩＤである。“src_false”フィールドは、「偽」の出力制御信号を計算するノードのＩＤである。
【０２０５】
制御信号の構築後、セレクタは入来するデータ値についてインストールされる。図２３は、図２４の例に追加されたセレクタノードを変数‘ｘ’について示す。ＯＲチェーンからの出力はこれらセレクタの供給し得る。ループ内の各々の変数につき１組のセレクタが
作成され得る。
【０２０６】
内部ループの、パイプライン化されたＤＦＧへの変換は、上述の変換技術に基づき得る。以下に示すループの例を検討する。
【０２０７】
【数２９】
2010146577.tif 000031
【０２０８】
このループは単一の基本ブロックであり、それ自身への条件分岐を伴っている。図２５Ａ，２５Ｂはアンカーについてのコードフラグメントを示す。その１番目のものは‘ＡＬ（ｉ）’を読込んでこれを‘ａａ’に記憶する。２番目のものはサブルーチン‘ｘｙｚ’をコールする。３番目のものは‘ｂｂ’を“ＢＬ（ｉ）”に記憶する。４番目のものは‘ｉ’を増分する。５番目のものは‘．Ｙ０００１’を減分する。６番目のものは‘．Ｙ０００１’を検査し、これがゼロよりも大きい場合にこのブロックへ分岐して戻る。
【０２０９】
このループのコードブロックは基本ブロックの手法を用いて変換され得る。ブロックが発火（fire）されるたびに、これはそのロードを行ない、その値を計算し、その記憶を行なうことになる。次に、それは制御を自分自身に渡して次の反復について繰返す。この実行にはいくらかの命令レベル並列性があり得る。別の実施例において、アレイ値が読込まれて各々すべてのクロックで書込まれ、種々の機能ユニットについてのパイプライン化された実現を利用する。
【０２１０】
パイプライン化された実行を達成するために、ループ「生成部」を作成することができ、これは、指定された間隔で反復を発火することにより、ループを制御する。このノードはＬＯＯＰ＿ＤＲＩＶＥＲと呼ばれ得る。これは、コードブロックのヘッドでＩＮＩＴＩＡＴＥノードによりトリガされ得て１列のパルスの放出を開始し得る。各々のパルスはループの１反復の発火を合図し得る。ＬＯＯＰ＿ＤＲＩＶＥＲノードはループがいつ終了するかを決定しない場合がある。データフローグラフにおける他の部分が終了条件について検査し得る。反復は、各々のクロックの刻みごとに発火され得るか、またはループキャリー依存性もしくは多数のＯＢＭアクセスに対応できるように遅くされ得る。ＬＯＯＰ＿ＤＲＩＶＥＲノードへの入力はその「デューティサイクル」（すなわち反復の発火同士の間に生じるべきクロックの刻みの数）を指定し得る。
【０２１１】
ループキャリースカラ依存性は、パイプライン化されたループでこれらを管理するための機構があることができるように存在し得る。ＣＩＲＣＵＬＡＴＥノード（３２または６４ビット形式）はスカラ変数の現在の値を保持するために存在し、ＬＯＯＰ＿ＤＲＩＶＥＲノードの出力に接続され得る。ＣＩＲＣＵＬＡＴＥは、その１番目の入力がハイになるのを見ると、ループがスタートアップしつつあることを知る。その２番目の入力から初期値を取り込み得て、その後これに続いて、ＬＯＯＰ＿ＤＲＩＶＥＲが反復を発火するたびにその３番目の入力から新たな値を取込む。この３番目の入力はその「循環させられた」値である。スカラ変数がループ内でその値を変化させない場合、ＣＩＲＣＵＬＡＴＥノードの出力はそれ自身の３番目の入力に直接接続され得る。
【０２１２】
一実施例において、ループ終了はループ本体におけるどこかで条件検査により決定され得る。ループはパイプライン化され得るため、終了条件が検出されるときまでには既にいくつかの追加の反復が行なわれている場合がある。これらオーバーフローの反復は、値をＯＢＭに書込まないようにされている限り有害ではない。したがって終了検出はループ内でＯＢＭ記憶へイネーブル信号をゲーティングし得る。またＴＥＲＭＩＮＡＴＩＯＮ（終了）ノードをトリガすることがあり、これはＳＴ＿ＳＣＡＬＡＲノードに合図してスカラ変数の現在の値を取込ませる。
【０２１３】
図２６は、図２５Ａ，２５ＢのループについてのＤＦＧの一実施例を示す。ＬＤ＿ＳＣＡＬＡＲノードの最上層およびＳＴ＿ＳＣＡＬＡＲノードの最下層は単純な基本ブロックＤＦＧにおけるものと同じであり得る。網掛けを付した区域はグラフのループ固有の部分を示す。変数‘ａｌ’、‘ｂｌ’、‘．Ｙ０００１’および‘ｉ’についてＣＩＲＣＵＬＡＴＥノードがある。これらのうち最初の２つは、変化しない基底アドレスであり得る。最後の２つはそれぞれダウンカウンタおよびアップカウンタである。ＬＯＯＰ＿ＤＲＩＶＥＲはループの制御部である。その２番目の入力にあるゼロは、それがループ反復同士の間にクロックの刻みを挿入する必要がないことを示している。ＣＩＲＣＵＬＡＴＥノードは、ＬＯＯＰ＿ＤＲＩＶＥＲの出力信号を監視するものであり、これが新たなループ反復を示すたびごとに上記ノードはその循環する入力値を取込む。ループ終了は、ダウンカウンタをゼロと比較するＩＧＴノードにより検出され得る。ＩＧＴの出力が偽になると、ＬＯＯＰ＿ＶＡＬＩＤはこれを検出してＬＤＫＲおよびＳＴＫＲノードを不能にし、ＴＥＲＭＩＮＡＴＩＯＮノードを合図する。そしてＴＥＲＭＩＮＡＴＩＯＮノードはＳＴ＿ＳＣＡＬＡＲをトリガし、これがＣＩＲＣＵＬＡＴＥノードから終値を取込めるようにする。
【０２１４】
一実施例において、各々の機能ユニット内のパイプライン化されたロジックは各々のクロックの刻みごとにアクティブになり得る。所与の機能ユニットの入力ポートに現われる値につき適当な「マッチング」が行なわれ得る。図２７の左側に、ノードの隣にいくらかの待ち時間をもって式Ｃ＝Ａ−（Ａ＋Ｂ）＊Ｂを計算するＤＦＧフラグメントを示す。その下は、各々のクロックの刻みにおける信号の値を示すチャートである。ノードの待ち時間のため、乗算および除算ノードのポートに現われる値は適切に整列されないことがある。右側に示すように、固定長のＦＩＦＯ待ち行列であるＤＥＬＡＹ（遅延）ノードが挿入され得る。この挿入は、ＤＦＧ内の各々すべてのノードにつき、その入力すべてへの経路長が等しくなるように行なわれる。
【０２１５】
ＤＦＧの構築後には種々の最適化が実行され得る。たとえば、制御データフローグラフコードブロックの作成後、グラフ内のいくつかのＳＥＬＥＣＴＯＲノードは、同じソースから供給された両方の値入力を有し得る。このようなノードはなくしてもよいが、それは供給をする述語値にかかわらず同じ値が選択されているからである。この状況は、基本ブロックがマージされて１つのより大きなコードブロックを形成する際にしばしば生じる。図２８は、以下のコードフラグメントがそのブロックをマージされたときに生じるコードブロックの一部を示す。
【０２１６】
【数３０】
2010146577.tif 000032
【０２１７】
この例では、最も右側のＳＥＬＥＣＴＯＲにおける２つの値入力は同じソースから供給されるが、それは、‘ｃ’は条件文についてのいずれかの分岐において割当てられていないからである。このＳＥＬＥＣＴＯＲはなくしてもよい。
【０２１８】
別の例では、マージされたコードブロックはしばしば、ブール演算式の簡略化のための機会を示す。図２８は一例を示す。ＯＲノードの出力はブール演算式‘ex＋ex’であり、これはｅへと簡略化する。ＯＲノードはなくされ得る。入れ子にされた条件文がマージされるときには上記に似た、さらに顕著な機会が生じる。また、パイプライン化されたループコードブロックがヒューズ（fuse）されることもあり、これにより１つのループから出力値を直接別のループに供給する。
【０２１９】
区分化部
次に図２９を参照して、本発明の区分化部要素の一実施例を示す。一実施例において、区分化部要素は、アルゴリズムの一部が実行されることになるところを決定でき、したがってコンパイルプロセスの目標を決定できる。区分化部は、制御データフローグラフに対して、コンパイルされているアルゴリズムを定義するＨＬＬの内部表現を演算し得る。区分化部により取られる制御データフローグラフは、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータにより生成されるＣＦＧ−ＤＦＧであり得る。ＣＦＧ−ＤＦＧは、コンパイルされているファイルの中に見つかり得る１組の関数のグラフである。決定プロセスの結果、命令プロセッサのための命令を目標としたコードのうちの部分と、多数の再構成可能プロセッサの中に入っている多数の再構成可能チップ内のロジックのうちの部分がもたらされる。
【０２２０】
区分化プロセスは、入力として単一の制御データフローグラフを取って１組の出力制御データフローグラフを生成することがあり得る。その各々は特定の目標化した実現による。出力ＣＦＧ−ＤＦＧは、元のもののサブグラフである区分ブロックと、区分化されたコード間の接続を表わす辺とから構成され得る。
【０２２１】
区分化部の決定は以下を含むいくつかの要因に基づく。すなわち、入力制御データフローグラフの性質、利用可能なハードウェアリソース、およびハードウェアリソースのサイズと性能特性、等の要因である。
【０２２２】
多数の区分化アルゴリズムを考案可能であり、代替的なアルゴリズムを呼出して決定プロセスで評価することができる。各々のこのような区分化プロセスは、最適化戦略に従うハードウェアリソースの目標化を目的とする。入力制御データフローグラフは、１組の最適化基準を満たしながらハイブリッド計算プラットフォームの利用可能なリソース内に合う１組の接続されたサブグラフを作成し得ることとする。最適化基準はたとえば、再構成可能リソースの使用を最大化する、再構成可能チップの数を最小化する、相互接続を最小化する、または全体の性能を最大化する、等であり得る。
【０２２３】
初期制御データフローグラフから、区分ブロックおよび辺から構成され得る新たなグラフが作成される。各々の区分ブロックは、元の制御データフローグラフ（すなわちＣＦＧ−ＤＦＧ）のサブグラフと、再構成可能チップまたは命令プロセッサへの割当とを含む。この新たなグラフにおける各々の辺は、割当てられたリソース間の物理的な接続を表わし得る。
【０２２４】
次に、区分化のタスクは、最適化基準やサイズ制限を満たし区分ブロックを作成するタスクとなる他の区分ブロックに無理なく接続され得る。以下にハイブリッドシステムにわたり最適な性能を達成するためのそのような区分化手法の１つについて説明する。
【０２２５】
一実施例において、区分化ステップは、入力制御データフローグラフにおいて注釈として区分化部に渡されたＣプラグマまたはコンパイラ指示子といったプログラマ供給の区分化構文または指示子に基づき区分ブロックに対するサブグラフの割当として定義され得る。
【０２２６】
区分化の際にプログラマ供給の区分化構文指示に対して働いた後にＣＦＧ−ＤＦＧサブグラフがいくらかでも残っている場合、コンパイラ開始の区分化が以下のように進行し得る。すなわち、残ったＣＦＧ−ＤＦＧのサブグラフすべてを候補の区分ブロックとして列挙する；命令プロセッサプロファイラからのプロファイリングデータと、ＤＦＧエミュレートプロファイリングと、並列性の程度に基づく性能推定と、ブロックについての各々の動作のためのハードウェアロジックモジュール情報ファイルの中に見つかる性能情報と、候補の区分ブロックおよび隣接するブロック間にあるデータフローの性能と、を含む情報を用いて、候補の区分ブロックを潜在的可能性の順序で順序付ける；再構成可能ロジック対命令プロセッサコードとしての区分ブロックの推定性能を比較する；比較に基づき候補の区分ブロックをチップまたは命令プロセッサに割当てる；すべての候補ブロックを通じて進行する；推定された性能により候補の区分ブロックを順序付ける；そして、区分ブロックを含むＣＦＧ−ＤＦＧ構成体出力ＣＦＧ−ＤＦＧを完全にカバーする最終候補ブロックを選択する。
【０２２７】
これが完了すると、区分ブロックの組は、実行場所と、上記リソースにロードされる制御データフローグラフとを定義し得る。区分ブロックはＨＬＬコンバータに渡される。命令プロセッサで実行されることを意図されたブロックは、コンパイルプロセスをコード生成およびオブジェクトファイル生成へと継続し得る。再構成可能チップを目標としたブロックはＨＬＬコンバータに渡されてＭＡＰプロキシコードを生成でき、それからＣＦＧ−ＤＦＧをＣＧＦからＣＦＧ−ＤＦＧへのコンバータに渡してロジック生成プロセスを継続できる。最終的には、区分ブロックはコンパイルプロセスをＣＦＧ−ＤＦＧからＨＤＬへのコンバータまで継続し、そして最終的に、統一された実行可能要素に含められるべきビットストリームの生成に至る。
【０２２８】
ＨＤＬ変換のための準備
ＣＦＧからＣＦＧ−ＤＦＧへのコンバータの出力の１つは、コンパイルされているプロシージャについての変換されたデータフローグラフを表わすＡＳＣＩＩテキストファイルである。コンパイルにおける次のステップは、コンパイルにおける、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータのVerilogコード生成段階により利用可能なフォーマットへと上記ファイル（すなわち．ｄｆｇファイル）を翻訳するステップである。ＭＡＰコンパイラは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ「タプル」フォーマットでコンパイルされているプロシージャを表わす、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの内部フォーマット化テーブルへＡＳＣＩＩ．ｄｆｇファイルを翻訳する論理命令を含むソフトウェアモジュールを実現する。翻訳されたテーブルは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータへの入力の１つであるバイナリフォーマット化ファイル（．ｇｒｆファイル）に書込まれ得る。
【０２２９】
トランスレータの一実施例は以下のステップを有し得る。すなわち、最初のステップでは、コマンドラインがパーズされ得る。ソフトウェアモジュールは、入力ファイル名（すなわち．ｄｆｇファイル）である１つの任意でない引き数を有する。入力ファイル引き数が指定されれば、ファイル名は保存されファイルは開かれる。入力ファイルが開けられ得ない場合は処理は終了する。
【０２３０】
変換における次のステップは入力ファイルの読込およびパーズである。パーズはフレックス（flex）（スキャナ生成部）およびバイソン（bison）（パーサ生成）により生成さ
れたルーチンをコールすることにより実行され得る。ファイルがパーズされると、ソフトウェアモジュールは内部データ構造を構築してデータフローグラフを表現する。グラフの表現に用いられる内部データ構造は、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータにより用いられるのと同じ構造である。上記２つの一次構造は、プロシージャ変数を表現する構造のアレイと、コンパイルされているプロシージャの実行可能部分を含む基本コードブロックを表現する構造のアレイとである。
【０２３１】
次に、ソフトウェアモジュールは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルの組立てを開始し得る。一実施例において、このステップは、データフローグラフについての内部構造の構築後に実行される。出力ファイル名は入力ファイル名から、たとえば．ｄｆｇサフィックスを．ｇｒｆサフィックスと置き換えることで構成され得る。入力ファイル名はＣＦＧ−ＤＦＧからＨＤＬコンバータのＦＩＬＥＮＡＭＥテーブルに入れられ、出力ファイル名はＣＦＧ−ＤＦＧからＨＤＬコンバータのＯＵＴＰＵＴ＿ＦＩＬＥＳテーブルへと入れられるということがあり得る。
【０２３２】
次に、シンボルテーブルは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータのＳＣＡＬＡＲＳテーブルへ翻訳され得る。一実施例において、このステップは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルの初期化後に行なわれる。コンパイルされているプロシージャに対する仮パラメータは、習慣上、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータのＳＣＡＬＡＲＳテーブルにおける最初のエントリである。データフローグラフの変数アレイを通じてパス（pass）が行なわれて仮パラメータを抽出する。各々のパラメータにつき、ＳＣＡＬＡＲＳテーブルにおいてフラグが設定されてこれがプロシージャに対する仮パラメータであることを示し得る。２つの他のフラグのうち１つが各々のエントリにおいて設定されて当該パラメータがスカラ変数であるかアレイであるかを示し得る。スカラまたは単一のアレイ要素についての．ｄｆｇメモリ記憶サイズはそのビット長である。これはバイト長へ変換されて各々のパラメータにつきＳＣＡＬＡＲＳテーブルエントリに挿入され得る。最後に、パラメータの名前がＳＣＡＬＡＲＳテーブルエントリに挿入され、エントリ完了パラメータエントリがＳＣＡＬＡＲＳテーブルに挿入される。
【０２３３】
すべての仮パラメータが処理された後、データフローグラフシンボルテーブルを通じて２番目のパス（pass）が行なわれ得て、当該のプロシージャに対する仮パラメータでない変数についての残りのエントリが処理され得る。この処理は仮パラメータについて説明したのと同様に実行され得るが、ＳＣＡＬＡＲＳテーブルエントリは、エントリが仮パラメータについてであることを示すフラグの代わりに、ローカル変数フラグが中に設定される。
【０２３４】
データフローグラフ基本コードブロックの翻訳はシンボルテーブルの翻訳に従う。データフローグラフの中の１ブロックはノードの順次のリストである。ノードは、１つ以上の出力を伴う１つ以上の入力オペランドに対して実行される演算である。この演算はＡＳＣＩＩストリングオペコードとして表現される。オペランドは、入力または出力値を含む擬似レジスタ数を表わす整数として表現される。これに代えて、入力オペランドは定数であり得る。データフローグラフブロックの翻訳において、４つのＣＦＧ−ＤＦＧからＨＤＬへのコンバータVerilog生成部テーブルが構築される。コードブロックのリストであるＢＬＯＣＫＳテーブルがある。ＲＡＷ＿ＮＯＤＥＳテーブルは、ブロック内に入っているノードの順次のリストである。ＰＲＳテーブルは、定義される擬似レジスタと、定数と、各々のノードで参照される擬似レジスタとのリストである。ＣＯＮＳＴＡＮＴＳテーブルは、コンパイルされているプロシージャで使用されるあらゆる定数値を含む。
【０２３５】
トランスレータは、一度に１ブロックを処理しながらデータフローグラフのブロックアレイを通じてパス（pass）する。各々の新たなブロックはＣＦＧ−ＤＦＧからＨＤＬへの
コンバータＢＬＯＣＫＳテーブルの中にエントリを得る。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータのＢＬＯＣＫＳテーブルエントリは、以下に記載するブロック内のノードについての最初および最後のＣＦＧ−ＤＦＧからＨＤＬへのコンバータのＲＡＷ＿ＮＯＤＥＳテーブルエントリに対する索引を含む。ブロックが終了ブロックであり、すなわちコンパイルされているプロシージャからの戻りを含むブロックであることを意味している場合、ＢＬＯＣＫＳテーブルエントリにはこれ以上の情報は入れられない。ブロックがドロップスルーブロックであり、条件分岐で終わらないことを意味している場合、後継のブロックのためのＢＬＯＣＫＳテーブルエントリに対する索引が現在のブロックのＢＬＯＣＫＳテーブルエントリに入れられる。他ではブロックは条件分岐で終わることになる。この場合、２つのあり得る後継のブロック（分岐の真のブロックおよび分岐の偽ブロック）のＢＬＯＣＫＳテーブル索引が現在のブロックＢＬＯＣＫＳテーブルエントリに入れられる。
【０２３６】
ＲＡＷ＿ＮＯＤＥＳテーブルエントリはトランスレータがブロック内の各々のノードを通じてパス（pass）することにより組立てられる。ノードの処理は以下のように進行する。各々の出力擬似レジスタがＰＲＳテーブルに入れられる。これは出力であり、したがってノードの動作により定義されるので、ＰＲＳテーブルエントリにはフラグが設定されてこれがそのノードにより定義されることを示す。また、擬似レジスタ数がＰＲＳテーブルエントリに挿入されるとともに親ノードＲＡＷ＿ＮＯＤＥＳテーブルエントリの索引が各々のＰＲＳテーブルエントリに挿入される。出力擬似レジスタがノードについて処理された後、入力が処理される。入力擬似レジスタは、定義されたフラグがそのエントリで設定されないことを除き出力と同様にＰＲＳテーブルに入れられる。定数であるノードへの入力もまたＰＲＳテーブルエントリを得る。定数の入力が現われると、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータのＣＯＮＳＴＡＮＴＳテーブルにおいて、現在の定数と一致するエントリが探される。一致が見つかれば一致の索引が用いられ、そうでなければ新たなＣＯＮＳＴＡＮＴＳテーブルエントリが作られて新たなエントリの索引が用いられる。定数についてのＰＲＳテーブルエントリにはＣＯＮＳＴＡＮＴＳテーブルエントリが挿入され、フラグが設定されてこれが定数であり擬似レジスタ参照エントリでないことを示し、親ノードのＲＡＷ＿ＮＯＤＥＳテーブル索引がその中に挿入される。
【０２３７】
ノードについてのすべての入力および出力が処理されると、ノードについてＲＡＷ＿ＮＯＤＥＳテーブルエントリが作られる。ＲＡＷ＿ＮＯＤＥＳテーブルエントリには、ノードのオペコードと、ノードと関連付けられた最初および最後のＰＲＳテーブルエントリのＰＲＳテーブル索引とが入っている。
【０２３８】
すべてのノードが翻訳されると、トランスレータは、データフローグラフが．ｇｒｆ出力ファイルへ翻訳されることで構築されたＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルを書き出し、そして処理は完了する。
【０２３９】
ＣＦＧ−ＤＦＧからＨＤＬへの変換
再構成可能ＦＰＧＡチップについてのコンパイルシステムの一構成要素について説明する。このコンパイルシステムは、ＣやFortranのようなより高級な言語を、より大きな実行フレームワーク内で動作するＦＰＧＡのための構成ビットストリームにコンパイルする能力を有する。
【０２４０】
このより大きな実行フレームワークはＳＲＣ  ＭＡＰ製品の設計に特有である。理論的には、このコンパイルシステムはこのような任意の環境に容易に適合可能である。
【０２４１】
ここに記載する構成要素は「ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ」である。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの目的は、「ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ」の出力をVerilog言語に変換することである。Verilogは、ＦＰＧＡチップの製造業
者によって提供される標準的なツールセットへの入力として用いられ得るＨＤＬ（hardware description language）である。
【０２４２】
ＣＦＧからＣＦＧ−ＤＦＧへのコンバータはコンパイルシステムの別の構成要素である。このＣＦＧからＣＦＧ−ＤＦＧへのコンバータの目的は、伝統的な高級言語コンパイラのオペコードを処理して、ＭＡＰ／ＦＰＧＡシステムでのパイプライン化された実行のためにより適した形にすることである。
【０２４３】
ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ出力は、実質的に、伝統的なコンパイラ出力から作成されたデータフローグラフ（ＤＦＧ）からなり、これはむしろ制御フローグラフ（ＣＦＧ）の形を取る。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは、その機能を実行するためにＤＦＧの形を必要としない。それはＣＦＧスタイルの入力で容易に作動することができる。しかしながら、ＭＡＰ／ＦＰＧＡにおける効率的な実行にはＤＦＧの形が必要となる。
【０２４４】
全体的なコンパイル戦略としては、伝統的なコンパイラ／ＣＦＧからＣＦＧ−ＤＦＧへのコンバータ／ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの組合せにより作成されたVerilog言語を手引きとして用いることにより、ユーザコードのＦＰＧＡ／ＭＡＰに対する効率的な表現を達成するために予め定められた「ハードウェア」モジュールを相互に接続する方法を導き出す。したがって、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは、Verilog言語へのオペコード構成体の「合成」を行なわない。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは単に、知られている予め定められた１組のハードウェアモジュールから、特定のオペコードノードが必要とする機能に一致するモジュールを選択し、その間の相互接続をもたらす。予め定められたハードウェアモジュールの作成、維持および管理は、全体的なコンパイル作業の主な構成要素であり、オペコードノードと予め定められたハードウェアモジュールとの間の関係をどのように管理するかについての議論を除いてはここでは論じない。
【０２４５】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは、そのタスクを実行する間、処理に必要な情報のさまざまな部分を表現する１組の内部テーブルを管理する。最終的に、これらテーブルはユーザコードのVerilog表現が出力され得るのに十分な情報を有する。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータについての入力ファイルは単純なファイルフォーマットから構成され、これは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルフォーマットへ既に予め処理されているいくらかの情報を含む。
【０２４６】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは単一のテーブルフォーマットのみを有することに注目されたい。テーブル管理は、テーブルエントリの削除ではなく追加のみを可能とすることにより単純化される。エントリはフラグにより無効であるとマークされ得て、単にテーブル展開における後続の段階へコピーされない。また、テーブルエントリは固定サイズであり、テーブル探索を速やかにする。
【０２４７】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの入力は、コマンドラインスイッチと２つのタイプの入力ファイルとから構成される。コマンドラインスイッチは、入力ファイルの名前を指定する、およびＣＦＧ−ＤＦＧからＨＤＬへのコンバータの処理の厳密な詳細を制御するために用いられる。この文献の目的にとっては、上記スイッチにより制御されるＣＦＧ−ＤＦＧからＨＤＬへのコンバータ処理の詳細は重要ではない。したがって、ここで述べる２つのタイプの入力ファイルのみが重要な入力である。
【０２４８】
入力オペコードファイルは“−ｆ”スイッチで指定される。ただ１つのオペコードファイルが入力され得る。このファイルは、上述の“ｄｆｇ２ｇｒｆ”と呼ばれるトランスレ
ータユーティリティにより、ＣＦＧ−ＤＦＧからＨＤＬコンバータファイルフォーマットへと変換されたＣＦＧからＣＦＧ−ＤＦＧコンバータのデータフローグラフ出力からなる。
【０２４９】
オペコードノード：オペコードノードは、ノードの名前と、入力および出力擬似レジスタのリストとから構成される。擬似レジスタは単に或る数であり、ノード間のデータの流れを相互に関連づけるために用いられる。
【０２５０】
ブロック情報。オペコードがどのように基本ブロックに分割されるかを示す。基本ブロックは、伝統的なコンパイラにおけるものと同じ定義を有する。すなわち、単一の入口点および単一の出口点を有する命令シーケンスである。
【０２５１】
定数情報。オペコードノードは、擬似レジスタの代わりに入力として定数値を参照し得る。
【０２５２】
「スカラ」情報。コンパイルされたサブルーチン関数に渡される引き数についての情報である。
【０２５３】
ファイル名情報。生成されるVerilogファイルの出力ファイル名を生成するために用いられる。
【０２５４】
任意の数の「ＣＦＧ−ＤＦＧからＨＤＬへのコンバータinfo」ファイルは、“−ａ”スイッチの使用により入力され得る。「ＣＦＧ−ＤＦＧからＨＤＬへのコンバータinfo」ファイルは、“info２grf”ユーティリティによりＣＦＧ−ＤＦＧからＨＤＬへのコンバータファイル／テーブルフォーマットに変換された“info”ファイル情報から構成される。“info２grf”への入力はアスキーテキスト“info”ファイルからなり、開発者／ユーザにより編集および維持されることを意図したものである。
【０２５５】
“info”ファイルは、オペコードノード名と、Verilog言語ファイルで出力される結果としてのモジュール名との間の関連付けを、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータが行なうための機構である。また、これを用いてユーザ定義のオペコード／モジュール関係についての情報を入力することができる。
【０２５６】
入力ＣＦＧ−ＤＦＧからＨＤＬへのコンバータハードウェアロジックモジュール情報ファイル”info”ファイルに入っている情報の中には、全体としてコンパイルシステムにより用いられるモジュールについての情報すべてが入っている。ここではＣＦＧ−ＤＦＧからＨＤＬへのコンバータにより用いられる情報のみについて述べる。ＣＦＧ−ＤＦＧからＨＤＬへのコンバータにより用いられる情報は以下のものである。
【０２５７】
オペコードノードの名前。オペコードノードに対応するモジュールの名前。入力と対応の出力との間の時間のクロックにおける待ち時間。入力、そのビット幅およびその名前のリスト（擬似レジスタがオペコードノード内でＣＦＧからＣＦＧ−ＤＦＧへのコンバータ出力フローグラフにおいて現われる順序にある）。出力、そのビット幅およびその名前のリスト（擬似レジスタがオペコードノード内でＣＦＧからＣＦＧ−ＤＦＧへのコンバータ出力フローグラフにおいて現われる順序にある）。実行のために必要とされるがフローグラフには現われないハードウェア関係のモジュールＩ／Ｏ接続についての名前、ビット幅およびそれらが接続する外部信号名（これはたとえば、ブロック内で所与のノードの常駐場所のコンテキストにおいて暗黙であり得るイネーブル／リセット信号またはＣＬＯＣＫ信号が含まれる）。
【０２５８】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ出力：ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ出力は、アスキーテキストであるVerilog言語ファイルから構成される。ファイル名はオペコード入力ファイルに担われる情報から生成される。一般的に、ファイル名は“．ｖ”をサフィックスとする高級言語ファイルの「基底名」である。たとえば、“toto．ｃ”と名付けられた高級言語ファイルは、結果として“toto．ｖ”と名付けられたVerilog言語ファイルをもたらす。
【０２５９】
Verilog言語ファイルは、“ＰＲＥＡＭＢＬＥ．ｖ”、“ＡＭＢＬＥ．ｖ”、および“ＰＯＳＴＡＭＢＬＥ．ｖ”“ＯＢＭ＿ＤＲ＿ＳＥＴ．ｖ”および“ＦＲ＿ＳＥＴ．ｖ”を参照する３つの“include”文を有する。これら３つのinclude文は、生成されたVerilogコードの宣言およびインスタンスのセクションを括弧でくくって分割する。これらによって、includeを分解するための異なるファイルをもたらすことによりさまざまな実行およびシミュレーションの環境において変更なしに、生成されたVerilogコードを使用することが可能となる。
【０２６０】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ処理フロー：初期化：ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの初期化処理は、コマンドラインスイッチの妥当性検証と入力ファイルの読込とからなる。入力ファイル内のデータは内部のＣＦＧ−ＤＦＧからＨＤＬへのコンバータテーブルへ直接読込まれる。
【０２６１】
主な機能の１つは、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータ処理を通じて使用されるべき情報を含む多数の内部テーブルの作成である。作成される２つの最も主なテーブルはＥＱＵＩＶ＿ＩＮおよびＥＱＵＩＶ＿ＯＵＴテーブルである。これらのテーブルには、“info”ファイルに入っている情報の最も重要な部分が入っている。これら２つのテーブル内のエントリは１対１対応関係を有しており、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータに指示することにより、入力フローグラフにおける所与の名前のオペコードノードを、出力Verilogファイルにおける予め定められたハードウェアモジュールの所与のインスタンス化に変換させる。ＭＯＤＥＵＬＥＳテーブルもまた作成され、これはＥＱＵＩＶ＿ＯＵＴにより索引付けされるモジュールについてのモジュール接続の詳細を有する。
【０２６２】
初期化においては、特別な目的の処理のためのさまざまなテーブルもまた作成される。これにより、目標のハードウェア特定の処理のための情報をソースコードの１区域に収容することが可能となる。目標のハードウェア環境に対して特定的な特別目的処理のすべてはたとえば、この初期化段階に生成される種々のフラグおよびテーブル設定により制御され得る。したがって、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータの処理を別のプラットフォームに目標付け直すことが可能であり、これをするために、まず他のところで必要とされるだけこのような機能を追加し、それからこれを可能にするために生じるであろう初期化処理を選択する。理論的には、コマンドラインスイッチの単純な使用により、異なる実行環境がサポートされ得る。
【０２６３】
このような特殊な場合の目標ハードウェア特定の処理は、以下のサポートを含む。すなわち、モジュールの非擬似レジスタ関係の接続が接続するであろうグローバル信号のリスト。メモリバンクと、メモリ関係のオペコードノードが接続される方法とに関する情報。“ＭＩＲＲＯＲ”モジュールに関する情報（これは、コンパイルされたサブルーチンへのパラメータ入力をＦＰＧＡインスタンス化設計に接続し、場合により更新値を返すためのＳＲＣ機構である）。“ｃｏｄｅ＿ｂｌｏｃｋ＿ｒｅｓｅｔ”への接続は実際、所与のモジュールについての常駐場所の現在のブロックの“block_reset”信号に接続されることになる。
【０２６４】
内部テーブルへの生の入力を処理：オペコードフローグラフノードの入力テーブルはＮ
ＯＤＥテーブルに読込まれ、オペコードノードの名前がＥＱＵＩＶ＿ＩＮテーブルにおいて探索される。見つかれば、対応のＥＱＵＩＶ＿ＯＵＴテーブルエントリは、予め定められたハードウェアモジュールのＭＯＤＵＬＥ索引を与える。このモジュール情報への索引はＮＯＤＥテーブルに置かれる。
【０２６５】
オペコードノード間のビット幅の一貫性を検証：ここで、ＮＯＤＥＳテーブル内のすべてのオペコードノードは割当てられたハードウェアモジュールを有する。ここですべての擬似レジスタを調べ、１モジュールにおいて別のモジュールの入力へ行く出力をマークする擬似レジスタについての一貫したビット幅の一致があるかどうかを検証する。この作業が実行される間、擬似レジスタ情報を含むテーブルが構築される。
【０２６６】
ＣＦＧ−ＤＦＧからＨＤＬへのコンバータは、モジュール間に流れるデータの「タイプ」についての情報またはこれの必要性を有さないことに注目されたい。ビット幅のみが重要である。
【０２６７】
「インライン化」のためのいくつかのシフト関数をマーク：ＮＯＤＥＳテーブルが調べられ、「シフト」演算を表現するいくつかのモジュールが処理される。モジュールの名前の慣用により、シフトが一定の量によるものか、そしてどれほどのものかが示される。モジュールがそのようなシフトであれば、この事実とシフトの方向とが、フラグによりＮＯＤＥＳテーブルエントリ内でマークされる。モジュールについてのシフトカウントもまた抽出されてＮＯＤＥＳテーブルエントリ内のフィールドに置かれる。この情報は、「インライン化」するために生成されたVerilogコードの出力中に使用されるか、または、実際にモジュールをインスタンス化することなくモジュールの機能をVerilogコード構文で直接表現する。
【０２６８】
オペコードノードの依存性を分析：ここで、ＮＯＤＥＳテーブルおよびそれに関連付けられた擬似レジスタを調べてノード依存性のテーブル（ＮＯＤＥ＿ＤＥＰＳ）を作成する。このＮＯＤＥ＿ＤＥＰＳテーブルは、ＮＯＤＥＳテーブル内のどのオペコードノードが他のオペコードノードの前提条件である（すなわち擬似レジスタを介して直接流れるデータを有する）かを示す。
【０２６９】
オペコードノードは以下のように発行される。すなわち、ＮＯＤＥ＿ＤＥＰＳテーブルが調べられ、所与のＮＯＤＥエントリについての先行要素の数の総カウントが作成されてＮＯＤＥテーブルエントリに記憶される。各々すべてのＮＯＤＥテーブルエントリ内の「クロックカウンタ」がゼロにされる。ゼロの先行要素カウントを有する各々すべてのＮＯＤＥエントリのリストを有するテーブル（ＰＩＣＴ＿ＮＯＤＥＳ）が作成される。
【０２７０】
以下のようにオペコードノードを発行：ＰＩＣＴ＿ＮＯＤＥＳテーブル内におけるＮＯＤＥＳテーブルエントリの索引の配置は、オペコードノードが「発行された」ことの基本的な指示である。ＰＩＣＴ＿ＮＯＤＥエントリが作られると、モジュールの特定のインスタンスをリスト化するテーブル内にエントリが作られる（ＩＮＳＴＡＮＣＥＳテーブル）。同じモジュールタイプについて多くのインスタンスがあり得るので、所与のモジュールタイプにおける各々のインスタンスについて一意の名前が生成されるのはＩＮＳＴＡＮＣＥＳテーブルを通じてである。
【０２７１】
上述の初期化段階の後、オペコードノードの発行プロセスは以下のように継続する。すなわち、ＰＩＣＴ＿ＮＯＤＥＳテーブル内のすべての新たなエントリにつきＮＯＤＥ＿ＤＥＰＳテーブルを調べて、発行されたオペコードノードを先行要素として有するＮＯＤＥテーブルエントリ内の先行要素カウントを減分する。先行要素であったモジュールの待ち時間によって影響を受ける各々のＮＯＤＥテーブルエントリのクロックカウントを調整す
る。新たにＰＩＣＴ＿ＮＯＤＥＳテーブルに追加される各々のノードにつき、関連付けられたＩＮＳＴＡＮＣＥＳテーブルエントリを作成する。
【０２７２】
ＷＩＲＩＮＧテーブル内に情報を構築することにより、新たに作成されたＩＮＳＴＡＮＣＥＳテーブルエントリに先行要素ＩＮＳＴＡＮＣＥＳテーブルエントリの出力の「配線」を実行する。ＷＩＲＩＮＧテーブルは、ソースおよび宛先のＩＮＳＴＡＮＣＥＳテーブル索引に関する情報および引き数またはパラメータ数を有する。
【０２７３】
ここで、新たに先行要素カウントがゼロになったオペコードノードについてのＮＯＤＥＳテーブルを調べる。これらエントリをＰＩＣＴ＿ＮＯＤＥＳテーブルに追加して上述のように継続する。このプロセスを、すべてのオペコードノードが発行されてしまうまで継続する。
【０２７４】
ＨＤＬファイルを出力：このときまでに処理は、ＨＤＬファイルの出力が開始できる点まで展開している。このプロセス中に行なわれる処理がなおいくらかあり、これにはすべての「配線」接続について宣言文を発することと、基本ブロックを互いに接続するよう配線することとが含まれる。
【０２７５】
ＩＮＳＴＡＮＣＥＳテーブル内のすべてのエントリにつき、「インライン化」されたかどうかをまず調べる。そうであれば、適当なＨＤＬ構文を出力する。そうでなければ、ＷＩＲＩＮＧテーブルに記述されているように、適当なモジュール、および種々のワイヤへのモジュールのＩ／Ｏピンの接続等、のインスタンス宣言を出力する。
【０２７６】
ビットストリーム構成
コンパイルシステムの１構成要素であって、ユーザの実行可能要素へと最終的に統合されることになるコンパイル可能なＣコードへザイリンクス（Xilinx）ツールから作成されるビットストリームファイルを含める作業を行なう。この構成要素は、プログラミングデータのみを含むバイナリファイルの中にある１または２のＦＰＧＡビットストリームファイルを入力として取る。このコンパイル段階の結果は、一方が各々のＦＰＧＡビットストリームについてある２つの構造を含むＣコードである。各々の構造は、下記のように、アレイの中に入ったＦＰＧＡビットストリームについてのパックされた表現；ビットストリームについての内部場所を指すポインタ；このビットストリームが表現するＦＰＧＡの数、ビットストリームアレイの長さ；ビットストリームアレイの始まりのアドレス；および、エミュレートに用いられるＭＡＰルーチンのＣバージョンを指すポインタ、を含む。
【０２７７】
ＦＰＧＡビットストリームファイルは４０９６バイト量としてバッファに読込まれる。次にこのバッファは６４ビットワードへパックされ、適当なビットストリームの構造の中に入ったビットストリームアレイへ書き出される。ビットストリームファイルから読込まれた最後の量は完全な６４ビットワードとなるようにパディングされ、これらのワードもまたアレイに書き出される。ビットストリームファイル全体の完了後、最後のワードがキャッシュラインにおける最後のワードであるかどうかを判断するための検査が行なわれる。もしそうでなければ、より多くのパディングを行なって、最後のアレイワードが、マイクロプロセッサシステムにおける４ワードキャッシュラインを完全に満たすことを確実にする。
【０２７８】
ビットストリームファイルの翻訳の完了後、残る情報およびポインタは最初のＦＰＧＡビットストリームを表わす構造に挿入される。同じプロセスが再び行なわれて２番目のＦＰＧＡビットストリームが読込まれて翻訳される。これらビットストリームのうち一方が存在するか、またはいずれもこのコンパイル段階では存在しないかのいずれかである。ビットストリーム構成部は、ヌルまたは存在するＦＰＧＡビットストリームファイルについ
てのすべての場合に対処し、これを反映するために適当なデータ構造を構築する。
【０２７９】
統一された実行可能要素への統合
異なりしたがって一様でないプラットフォームに対して実行されるであろうオブジェクトファイルを作成した結果として、コンパイルプロセスにおける次のステップは、これらさまざまな構成要素を、「統一された実行可能要素」と称されるものを構築するようにまとめなければならない。次に、統一された実行可能要素は、命令プロセッサで実行されるマシンコードと、ハードウェアロジックプロセッサで実行されるマシンコードとの両方を含む。
【０２８０】
上記統一された実行可能要素は、その実行中には命令プロセッサのアドレス空間に常駐するので、統一された実行可能要素のフォーマットは、命令プロセッサの受入れるアプリケーションインターフェイスに対応したものでなければならない。統一された実行可能要素内にＦＰＧＡビットストリームが存在できるようにするために、ビットストリームデータを受入れ可能なフォーマットにカプセル化するための方法が開発された。
【０２８１】
コンパイルプロセスによりビットストリームが生成された後、これらはＣ構造に読込まれ、ここで、このプログラム内でアクセスされる各々のビットストリームにつき１つのＣ構造が作成される。これらＣ構造は各々のビットストリームに対して一意である。Ｃ構造は、制御フロー情報ファイル生成段階中に作成された内部名に一致するように名付けられているからである。別個の制御フロー情報ファイルに一意の名前をタグ付けることによって、結果としてのビットストリームもまた、Ｃ構造に構築されると一意の識別子を有することができる。ビットストリーム構成が別のコンパイルプロセスで用いられることを意図されている場合、Ｃ構造はこの時点でバイナリファイルとして保存され得る。
【０２８２】
ビットストリームＣ構造は、統一された実行可能要素内に常駐するか、またはマイクロプロセッサにおいて、実行中に利用可能とされた場所に常駐するかのいずれかであり得る。コンパイルプロセス中に作成されたビットストリームは、統一された実行にデフォルトで埋込まれ、したがって実行の時点ではアドレス空間の中にある。特定の実行可能要素のために構成されたビットストリーム構造が多数ある場合、統一された実行可能要素内に埋込まれるビットストリームＣ構造はそのいくつかだけであることも、または全くないこともあり得る。ビットストリーム構造のうちすべてが実行の時点で実行可能要素のアドレス空間内に常駐しない場合、ランタイム環境は、このビットストリームについてのハードウェアロジック構成が呼出される点で適当なビットストリーム構造を読込む必要がある。
【０２８３】
ビットストリームＣ構造を統一された実行可能要素内に含めるかどうかを判断した後、マイクロプロセッサにある利用可能な標準のリンカを用いてこれをオブジェクトファイルから作成することができる。すべてのオブジェクトファイルは適当なバイナリインターフェイスのものであるため、マイクロプロセッサのマシンコードおよびハードウェアロジックのマシンコード両方を含むことを可能にするには特別なことをしなくてもよい。
【０２８４】
以下の図に示すように、実行の時点で実行されるべきハードウェアロジック構成を表現するビットストリームは図３０に示す２つの場所のうち１つに存在し得る。
【０２８５】
ランタイム環境
統一されたバイナリが実行されるランタイム環境は、命令プロセッサバイナリが実行されるランタイム環境を超えて拡張され得る。ＭＡＰライブラリは、データフローグラフのエミュレートおよびシミュレーションのためのサポートルーチンを含み得る。ユーザの観点からは、ランタイム環境にはルーチンについて３つのカテゴリがある。すなわちメモリ管理、ＭＡＰリソース管理、およびＭＡＰ実行である。
【０２８６】
メモリ管理：ハードウェアの制限により、命令プロセッサ環境と再構成可能プロセッサ環境との間で転送されるメモリのブロックはキャッシュの境界で開始することが必要な場合がある。このようなハードウェア制限が存在する場合でのキャッシュ整列を支援するための２つの関数が設けられる。
【０２８７】
第１の関数であるaddr３２（またはこれに代えてFortranについてはＩＡＤＤＲ３２）は、恣意的なメモリアドレスを受入れて、入力アドレス引き数以上のメモリの１番目のキャッシュ整列ワードのアドレスを返すための論理命令を含むソフトウェアモジュールである。整列されるべきアレイは、キャッシュラインのメモリに近づくアレイの始まりおよび終わりにてパディングで宣言され得る。キャッシュ整列アレイを指し示すためのポインタが宣言され得る。パディングされたアレイはaddr３２へ引き数として渡され得て、ポインタはこの関数の結果に設定され得る。整列されたアレイへの参照はポインタを通じて行なわれ得る。
【０２８８】
第２の関数であるキャッシュ整列割付け（またはこれに代えてFortranについてはＣＡＣＨＥ＿ＡＬＩＧＮＥＤ＿ＡＬＬＯＣＡＴＥ）は、単一の整数の引き数を受取り、キャッシュ整列境界で始まる割付けられた空間へのポインタを生成するための論理命令を含むソフトウェアモジュールである。引き数はバイトでのメモリ割付け要求のサイズであり得る。この関数はポインタを宣言するために使用され得る。これに加え、ユーザはこの関数をコールしてアレイのために必要な空間を割付け、ポインタをこの関数の結果に設定することができる。このアレイへの参照はポインタを通じて行なわれ得る。
【０２８９】
ＭＡＰリソース管理：ランタイム環境に対して動的に変更を加えることが可能であり、これを行なうためにジョブに再構成可能ハードウェアリソースを追加または削除する。命令プロセッサで実行される間、ＭＡＰリソースは必要とされない。ＭＡＰプロシージャを実行するのに先立ち、再構成可能ハードウェアリソースはジョブに割付けられなければならない。これはジョブのスタートアップ時に行なわれても、またはＭＡＰ実行に先立ついずれのときに行なわれてもよい。ＭＡＰプロシージャの実行後、統一されたバイナリの実行はしばらくの間ＭＡＰリソースを必要としない場合があるため、これらは再び必要とされるまで１つ以上のＭＡＰプロセッサを解放することが望ましい場合がある。同様に、別のＭＡＰプロシージャを実行するのに先立ち追加のＭＡＰリソースを追加することが必要である場合がある。ＭＡＰリソースの管理に２つの関数が設けられる。
【０２９０】
第１の関数であるmap_allocate（FortranについてはＭＡＰ＿ＡＬＬＯＣＡＴＥ（Ｎ，ＳＴＡＴ））は、割付けられるべきＭＡＰリソースの数を示す単一の入力引き数を受取るソフトウェアモジュールである。ゼロの結果値（FortranではＳＴＡＴ）は、割付けが成功したことを示す。ゼロでない結果（ＳＴＡＴ）は、要求が首尾よく満足されなかったことを示す。
【０２９１】
第２の関数であるmap_free（FortranについてはＭＡＰ＿ＦＲＥＥ（Ｎ，ＳＴＡＴ））は、ジョブから解放されるべきＭＡＰリソースの数を示す単一の入力引き数を有するソフトウェアモジュールである。ゼロの戻り値（FortranについてはＳＴＡＴ）は、リソースがジョブから首尾よく解放されたことを示す。ゼロでない戻り値（ＳＴＡＴ）は、リソースの解放を試みた際にエラーが生じたことを示す。
【０２９２】
ＭＡＰリソースはＭＡＰ  ＩＤ数によって識別される。ジョブに割付けられた１番目のＭＡＰは０のＭＡＰ  ＩＤを有する。任意の時点でｎ個のリソースがジョブに割付けられていれば、これらは０，１，…ｎ−１として識別される。最大の値のＭＡＰ  ＩＤ数を有するＭＡＰリソースは最初に割付けを解除される。たとえば、７個のＭＡＰリソースがジ
ョブに割付けられている場合、これらは整数０〜６で識別される。３つが割付け解除されれば、ＭＡＰ  ＩＤ０〜３はジョブに割付けられたままである。そして、２つが割付けられれば、最も最近に割付けられたＭＡＰ  ＩＤは４および５である。
【０２９３】
ＭＡＰ実行：ロジックビットストリームで再構成可能ハードウェアを構成する詳細、および再構成可能ハードウェアへ、そして命令プロセッサへの制御の転送の詳細は、ランタイム環境においてユーザから隠される。ＨＬＬコンバータにより生成されるＭＡＰプロキシコードがこれらのタスクを実行する。このプロキシコードによりコールされたルーチンＭＡＰ＿Executeについてここで論じる。
【０２９４】
ＭＡＰ＿Executeおよびそのさまざまなランタイム入口点は以下の機能を実行する。最初に、ＭＡＰプロキシコードは、ＭＡＰプロシージャの実行のためにどのＭＡＰリソースが使用されるべきかを示している。ＭＡＰ＿Executeはリソースをロックすることにより、ＭＡＰプロシージャの実行中に他の実行スレッド（またはユーザジョブ）がリソースにアクセスすることを防ぐ。使用されるべきリソースが、実行されるべきＭＡＰプロシージャのためにユーザロジックで正しく構成されているかを調べる。もしそうでなければ、適当なロジックビットストリームの場所を突止めてＭＡＰリソースを構成する。再構成可能ハードウェアにおける実行が開始される。ＭＡＰ＿Executeは実行が完了するのを待ち、リソースをアンロックし、それから命令プロセッサに対して完了を合図するかまたは制御を転送して返す。
【０２９５】
ランタイム環境におけるエミュレーション
エミュレートは極めて有用なデバッグツールであるとともに、データフローグラフレベルでの性能プロファイリングを可能にするツールである。エミュレーションの能力は、ＭＡＰコンパイルシステムにより構築される実行可能要素のランタイム環境の中に構築される。
【０２９６】
ランタイムライブラリは３つの別個の環境をサポートする。すなわち、１）ＭＡＰハードウェアでの実行、２）エミュレートされるＭＡＰおよびデータフローグラフエミュレーションでの実行、３）エミュレートされるＭＡＰおよびシミュレートされるユーザロジックでの実行、である。特定の環境の選択は環境変数設定に基づきランタイムで行なわれる。
【０２９７】
【数３１】
2010146577.tif 000033
【０２９８】
エミュレーションモードが使用される場合、追加の環境変数により、ＭＡＰについてのロジックがどのように扱われるかが決定される。
【０２９９】
【数３２】
2010146577.tif 000034
【０３００】
ＭＡＰＨＷ＝ＥＭＵＩＩＩが設定されると、ＭＡＰを管理するランタイムのライブラリルーチンは、ＭＡＰハードウェアサポートルーチンの代わりにＭＡＰエミュレートルーチンをコールする。各々すべての実行可能要素はハードウェアにおいてまたはエミュレートで実行可能である。ＭＡＰエミュレータはＭＡＰ制御プロセッサおよびそのリソースの代わりとなる。すなわち、通信リンク、オンボードメモリ、データレジスタ、およびフラグレジスタであり、これらリソースのソフトウェアエミュレートバージョンをもたらす。図３１および図３２はＭＡＰエミュレータの構造を示す。
【０３０１】
ＭＡＰエミュレータは、命令プロセッサアプリケーションコードおよびプロセスから別個のｐスレッド（pthread）として実行される。エミュレータスレッドは、ＭＡＰハードウェアモードでなくエミュレーションモードが選択されたとランタイムルーチンが検出したときに開始される。ＭＡＰハードウェアが命令プロセッサに対して非同期的に実行されるのと同様、エミュレータもまた非同期的に実行される。
【０３０２】
ＭＡＰエミュレータの機能は、命令プロセッサベースのアプリケーションへの通信および制御リンクをエミュレートし、データフローエミュレーションで、またはVerilogシミュレーションとして実行されるユーザロジックへのインターフェイスをもたらすことである。
【０３０３】
また、データフローのエミュレートは、フラグレジスタ、データレジスタおよびオンボードメモリを読込むまたは書込むために用いられるインターフェイスルーチンを通じてＭＡＰエミュレータへのインターフェイスを取る別個のｐスレッドとして実行される。
【０３０４】
ＭＡＰコンパイラにより生成されたユーザロジックがVerilogとして作成された場合、Verilogシミュレータを用いてＭＡＰエミュレータとともにユーザロジックを実行することができる。Verilogシミュレーションは、共有メモリセグメントを通じてＭＡＰエミュレータと通信する別個の実行可能要素として実行される。この場合、シミュレータは、オンボードメモリ、データレジスタおよびフラグレジスタをもたらし、一方でＭＡＰエミュレータはＭＡＰ制御プロセッサをもたらす。
【０３０５】
図３１は、ＤＦＧエミュレーションとともにＭＡＰエミュレータを示し、図３２はVerilogシミュレータとＭＡＰエミュレータを示す。
【０３０６】
別の実施例においては、データフローグラフエミュレートは以下のように行なわれ得る。すなわち、ＭＡＰコンパイラの、ＣＦＧからＣＦＧ−ＤＦＧへのコンバータステップにおいて、２つのファイル、すなわちユーザのサブルーチンのデータフローグラフ（テキスト形式）とエミュレートロジックファイルとが作成される。データフローグラフファイルの目的は２つあり得る。すなわち、ＣＦＧ−ＤＦＧからＨＤＬへのコンバータによって使用されてサブルーチンのVerilog翻訳を生成でき、さらには、ソースコードを妥当性確認するまたは性能データを収集するためにエミュレートが用られているときにエミュレート論理ルーチンによって読込まれ得る。
【０３０７】
一実施例において、データフローグラフはノードおよび指示された辺を含むことができ、ここでノードは機能ユニットであることができ、辺は、１つのノードからの出力値を他のノードの入力へ運ぶデータ接続である。データフローグラフを用いてデータフローシミュレータを実行することが可能であり得る。シミュレーションは以下のことに有用であり得る。すなわち、１）ソースコードと、そのデータフロー形式への翻訳とをともに妥当性確認する、２）デバッグのためのトレース情報をプリントする、そして３）性能推定を収集する、といった機能である。
【０３０８】
一実施例において、データシミュレーションは「トークン駆動（token driven）」シミュレーションモードで行なうことができ、これは、緩く結合された非同期的なシミュレーションであってシーケンス付けは有効であり得るが時間は考慮されないものであり得る。このモードにおいては、物事が「同時に」起こるという概念は存在しない。いずれのノードも、その入力に利用可能な値がある限り任意の時点で実行され得る。データ値は「トークン」と呼ばれ、トークンはノードの入力ポートで待ち行列を作ることができる。別の実施例においては、「クロック正確性（clock accurate）」シミュレーションが、システムクロックと機能ユニットの実行待ち時間とを考慮する。この場合、「同時」という語は意味を有する。
【０３０９】
図３３は、トークン駆動データフローシミュレータの一実施例のフローチャートを示す。一実施例の一例においては、ルーチン“dfg_simulate”がエミュレートロジックファイルからコールされてシミュレータを開始させ得る。この例においては、シミュレータはまずＤＦＧファイルを読込んで内部表現を構築することができる。そして、シミュレーションを開始し、ブロックゼロ（定義においては入口のブロック）で始まる。コードブロックをシミュレートするたびごとに、まず待ち行列およびノード状態をクリアして、それから、ブロックの最上部にあるＩＮＩＴＩＡＴＥノードに単一のトークンを送ることでブロックの実行をトリガする。それからループして、発火できるノードを探す。この例においては、ほとんどのノードについての「発火規則」は、ノードはその入力のうちの各々１つに利用可能なトークンがあれば発火できるというものである。「発火」は、各々の入力待ち行列からトークンを取るステップと、これらの値を用いてノードの特定の機能を実行するステップとからなる。この機能から１つ以上の出力値が得られ、これらはトークンとしてノードの出力で送り出される。出力が多数のノードに広がるときには、値トークンが目標のノードの待ち行列の各々に届けられ得る。
【０３１０】
図３４は、一実施例に従うＤＦＧフラグメントの一例を示し、ここではフラグメントはシミュレータの内部ループの反復のたびに段階的に実行される。開始時には３つの値が入力待ち行列で待っている。最上部にある２つのノードは発火可能であるとマークされる。これらは各々の待ち行列から１つのトークンを消費し、結果のトークンを、その出力により供給がなされるノードの待ち行列に送る。ｔ＝１において、最下部にあるノードはその右側の入力に値を有するがその左側の入力には値を有さないので発火できないことに注目されたい。ｔ＝２では、最下部のノードにおける右側の入力の待ち行列には２つのトークンがある。シミュレータの内部ループの５パス（pass）の後、このフラグメントには処理され得る値がもはやなくなる。
【０３１１】
一般的に、データフローグラフには正しい発火順序が多数ある。上述の例においては、上の方のノードを３回発火させてからその他のノードのいずれかを発火させることもまた等しく有効であったであろう。トークンが順序に従って待ち行列に到着するという事実により、各々のノードの出力にある対応の値は正しく「マッチアップ」することが確実となる。シミュレータにおけるノード入力待ち行列は、必要に応じて拡張できるように設計される。すなわち、値が待ち行列に送られその待ち行列が一杯であるときはいつでも、待ち行列のサイズを増大させて新たな値に対応できるようにする。フローチャートに示した処理順序においては、ノードにわたる各々の掃引においてノードは処理できたであろう値をより多く持っていたとしても一度しか発火しないが、この処理順序は、必要な待ち行列の長さを最小化するために選択され得る。
【０３１２】
非同期的データフローシミュレーション中に生じ得るさまざまなノード発火順序は、データフローノードが「純粋に機能的である」、すなわち各々のノードの出力トークンが、出力を計算するためにフェッチされた入力トークンに依存し得るときに、等価の結果を生成する。すべてのノードが純粋に機能的であるとは限らない。いくつかのノードは「状態
」を有する、すなわち以前に行なったことについての記憶をいくらか有している場合がある。このようなノードは「状態を持つ」と呼ばれ得る。いくつかのノードはこれを取囲むハードウェアと対話する、すなわちフラグレジスタ、データレジスタまたはオンボードメモリに読み書きをする場合がある。データフローシミュレータは、適当なＭＡＰエミュレータ関数へのコールを行なうことによりこれらノードを実行し得る。
【０３１３】
別の実施例においては、データフローシミュレーションは、再構成可能ハードウェアに起こることをより近く真似るモードで行なわれ得る。クロック正確性シミュレーションはシステムクロックが存在することを仮定し、機能ユニットは同期してクロックにより連携させられながら実行される。ハードウェアでは、各々すべての機能ユニットは、その入力に有効なデータがあるか否かにかかわらず、各々すべてのクロックサイクルにおいて演算を実行し得る。データフローグラフと、グラフから生成された論理回路とは、機能ユニットからの「ジャンク」データが無視されるように生成され得る。
【０３１４】
クロック正確性シミュレーションは、各々すべてのクロックサイクルにおいてグラフでの各々のノードが計算をするモードで動作する場合には、計算時間を極めて無駄に費やす場合がある。一実施例では、トークン駆動シミュレーションと同様にデータフローノードにより有効な計算が実行され、「タイムスタンプ」をトークンに取付けることによりシステムの同期的な様相が取込まれるというモードで、シミュレーションをすることが可能である。このシミュレーションにおいては、入力にてトークンが待ち行列をなし、ノードの発火および実行は、そのタイムスタンプにより待ち行列における値をマッチアップし得る。
【０３１５】
クロック正確性シミュレーションは非同期的なトークン駆動シミュレーションよりも複雑であり得るが、再構成可能ハードウェアで起こる動作および同期化をより忠実に反映し得る。したがって、クロック正確性シミュレーションは以下の利点を有する。すなわち、１）クロック正確性シミュレーションにおいては、不正確に置かれた遅延ノードはエラー指示を生成する。これに対してこれらは非同期的なシミュレーションでは正しく実行されているように見える。２）クロック正確性シミュレーションはシステムクロックをシミュレートするため、正確な実行時間予測値を与えることが可能である。３）同じメモリバンクへの読み書きが非同期的シミュレーションで起こるとき、これが起こる順序は指定されていない場合があるため、再構成可能ハードウェアで起こるであろう同じ順序で起こらない場合がある。しかし、クロック正確性シミュレーションによると、ハードウェアでおきることに一致するよう保証された実行順序をもたらすことができる。
【０３１６】
別の実施例においては、ＭＡＰコンパイラにより生成されるデータフローグラフのシミュレーションに関係した問題への対処がなされる。これには以下のものが含まれる。
【０３１７】
状態を持つノードの問題：状態を持つノードは、そのノード構造の中に、過去に生じたことについての或る様相を追跡するために用いる１つ以上の内部フィールドを有する。状態を持つノードの一例として、その入力にあるトークンストリームの値を合計するアキュムレータが挙げられる。アキュムレータノードはそのノード構造の中に、累算する合計の現在の値を保持するための場所を必要とする。その他のノードのタイプではより複雑な状態が必要とされる場合がある。データフローノード構造は、タイプ“NodeState”のフィールドを有する。これは以下のstructで定義される。
【０３１８】
【数３３】
2010146577.tif 000035
【０３１９】
一実施例において、コードブロックが入れられるときは必ず、その状態を持つノードの「初期化された」フィールドが「偽」に設定される。状態を持つノードについてのノード実行ルーチンはこのフィールドを調べて、偽であれば初期化を実行することができる。これは典型的に、ノードタイプの状態のために適当なデータ構造を割付けて、これを指し示すように「状態」ポインタを設定することによって行なわれる。また、この構造のフィールドが適当な開始状態に設定される。それから、「初期化された」フィールドが「真」に設定され、こうしてノードにおける後続の発火が再初期化を試みないようにする。
【０３２０】
発火規則および実行規則：一実施例において、データフローグラフにおける各々のノードタイプには、それに関連付けられた２つの機能、すなわち「発火規則」および「実行規則」がある。ほとんどのノードについての発火規則は単純なものであり得る。すなわち、ノードは、その入力のいずれにもデータ値があり得るときに発火できるという規則である。これには、ループデータフローグラフについてのパイプライン化された挙動を管理するループ制御ノードの場合にいくつかの例外があり得る。ノードについての実行規則は、その入力値をどのように用いて出力値を生成するかについての仕様であり、すなわち実行規則はノードの関数であり得る。シミュレータがデータフローグラフファイルを読込み、内部ノード構造を構築するとき、各々のノードは、このノードについての発火および実行関数を指し示すために用いられ得る２つの関数ポインタを有する。
【０３２１】
ユーザマクロ：一実施例において、ＭＡＰコンパイラにより、ユーザはコードの再構成可能ハードウェアへのコンパイル時に自分自身のハードウェア論理ユニットを参照することができる。コンパイルされたコードのデータフローシミュレーションを行なうために、ユーザは参照されている各々のユニットにつき実行関数を与える。これはこのノードについての「実行規則」である。ユーザマクロの場合、これは「通常の」発火規則に従う、すなわちノードは各々すべての出力に値があるときに発火できると仮定される。ユーザマクロについてのデータフローシミュレーションルーチンは、“info”ファイルから読込まれて、それからＳＲＣ組込マクロが扱われるのと同じ方法で内部的に扱われる。すなわち、ユーザのシミュレーション関数がコンパイルされ得て、関連付けられたデータフローノードにはこの関数へのポインタが与えられる。
【０３２２】
或る程度の具体性をもって本発明を記載および例示したが、この開示は単に例としてなされたものであって、先に請求された本発明の意味および範囲から逸脱することなく当業者は構成要素の組合せおよび配置において数多くの変更に頼ることが可能であることが理解される。
【０３２３】
この明細書および前掲の特許請求の範囲で使用される「備える」「備えた」「含む」および「含んだ」という用語は、記載される特徴、完全体、構成要素またはステップの存在を特定することを目的としたものであるが、その他１つ以上の特徴、完全体、構成要素、ステップまたは群の存在または追加を除外するものではない。
【符号の説明】
【０３２４】
１００  ハードウェア命令プロセッサシステム、  １０２  ＨＬＬソースコードファイル、１０４  コンバータ、１０６  ＨＬＬコンバータ、１０８  コンバータ、１１０  区
分化部、１１２  コンバータ、１１４  コンバータ、１１６  リンカ。
【図１】
2010146577.tif 000036
【図２】
2010146577.tif 000037
【図３】
2010146577.tif 000038
【図４】
2010146577.tif 000039
【図５】
2010146577.tif 000040
【図６】
2010146577.tif 000041
【図７】
2010146577.tif 000042
【図８】
2010146577.tif 000043
【図９】
2010146577.tif 000044
【図１０】
2010146577.tif 000045
【図１１】
2010146577.tif 000046
【図１２】
2010146577.tif 000047
【図１３】
2010146577.tif 000048
【図１４】
2010146577.tif 000049
【図１５】
2010146577.tif 000050
【図１６】
2010146577.tif 000051
【図１７】
2010146577.tif 000052
【図１８】
2010146577.tif 000053
【図１９】
2010146577.tif 000054
【図２０】
2010146577.tif 000055
【図２１】
2010146577.tif 000056
【図２２】
2010146577.tif 000057
【図２３】
2010146577.tif 000058
【図２４】
2010146577.tif 000059
【図２５Ａ】
2010146577.tif 000060
【図２５Ｂ】
2010146577.tif 000061
【図２６】
2010146577.tif 000062
【図２６Ａ】
2010146577.tif 000063
【図２６Ｂ】
2010146577.tif 000064
【図２７】
2010146577.tif 000065
【図２８】
2010146577.tif 000066
【図２９】
2010146577.tif 000067
【図３０】
2010146577.tif 000068
【図３１】
2010146577.tif 000069
【図３２】
2010146577.tif 000070
【図３３】
2010146577.tif 000071
【図３４】
2010146577.tif 000072
【手続補正書】
【提出日】平成22年1月26日(2010.1.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
高級言語ソースコードを実行可能ファイルに変換する方法であって、
コンピュータで、前記高級言語ソースコードを制御データフローグラフ表現に変換するステップを備え、前記制御データフローグラフ表現は、複数のブロックと各々が当該ブロックに接続された辺とを含み、
前記コンピュータで、前記制御データフローグラフ表現を、命令プロセッサによって実行される命令プロセッサ部分と、再構成可能ハードウェアによって実行される再構成可能ハードウェア部分とに区分化するステップと、
前記コンピュータによって、前記再構成可能ハードウェア部分からオブジェクトファイルを導出するステップと、
前記コンピュータによって、前記オブジェクトファイルを、統合実行可能ファイルを構成するリンクされたオブジェクトファイルのセットに統合するステップとを備え、前記統合実行可能ファイルは、前記命令プロセッサでの実行に互換性のある機械コードと、前記再構成可能ハードウェアでの実行に互換性のある機械コードとを含む、方法。
【請求項２】
前記高級言語ソースコードを制御フローグラフ表現に変換するステップと、
前記制御フローグラフ表現を前記制御データフローグラフ表現に変換するステップとをさらに備える、請求項１に記載の方法。
【請求項３】
前記再構成可能ハードウェア部分を再構成可能ハードウェアビットストリームファイルに変換するステップと、
前記再構成可能ハードウェアビットストリームファイルを前記オブジェクトファイルに変換するステップとをさらに備える、請求項１または２に記載の方法。
【請求項４】
高級言語ソースコードから実行可能ファイルを生成するシステムであって、前記実行可能ファイルは、再構成可能ハードウェア−命令プロセッサのハイブリッドなコンピュータで実行可能であり、前記システムは、
前記高級言語ソースコードを制御データフローグラフに変換することのできる高級言語コンバータと、
前記制御データフローグラフを、再構成可能ハードウェアによって実行される第１の部
分と、命令プロセッサによって実行され第２の部分とに区分化するための区分化部と、
前記再構成可能ハードウェアによって実行される第１の部分をハードウェア定義言語ファイルに変換することのできる言語コンバータと、
前記ハードウェア定義言語ファイルをビットストリームファイルに変換することのできるビットストリームコンバータと、
前記ビットストリームファイルをビットストリームオブジェクトファイルに変換することのできるオブジェクトファイルコンバータと、
前記ビットストリームオブジェクトファイルを、統合実行可能ファイルを構成するリンクされたビットストリームオブジェクトファイルのセットに統合することのできるオブジェクトファイルリンカとを備え、前記統合実行可能ファイルは、前記再構成可能ハードウェア−命令プロセッサのハイブリッドなコンピュータで実行可能である、システム。
【請求項５】
前記高級言語ソースコードを制御フローグラフ表現に変換することのできる高級言語コンバータをさらに備える、請求項４に記載のシステム。
【請求項６】
前記制御フローグラフ表現を前記制御データフローグラフに変換することのできる制御フローグラフ−制御データフローグラフ変換部をさらに備える、請求項５に記載のシステム。
【請求項７】
コンピュータによって実行されるコンピュータ読取可能プログラムコードを格納したコンピュータ読取可能な記憶媒体であって、当該プログラムコードは、高級言語から実行可能ファイルを生成するように具現化されており、前記コンピュータ読取可能プログラムコードは、
制御データフローグラフの、命令プロセッサによって実行される第１の部分と、再構成可能ハードウェアによって実行される第２の部分への区分化を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードと、
前記再構成可能ハードウェアによって実行される第２の部分の再構成可能ハードウェアオブジェクトファイルへの変換、および、前記命令プロセッサによって実行される第１の部分の命令プロセッサオブジェクトファイルへの変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードと、
前記再構成可能ハードウェアオブジェクトファイルと前記命令プロセッサオブジェクトファイルとの、統合実行可能ファイルを構成するリンクされたオブジェクトファイルのセットへの統合を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードとを含む、コンピュータ読取可能な記憶媒体。
【請求項８】
前記コンピュータ読取可能プログラムコードは、
前記再構成可能ハードウェアによって実行される第２の部分のハードウェア定義言語部分への変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードをさらに含む、請求項７に記載のコンピュータ読取可能な記憶媒体。
【請求項９】
前記コンピュータ読取可能プログラムコードは、
前記ハードウェア定義言語部分の再構成可能ハードウェアビットストリームへの変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードをさらに含む、請求項８に記載のコンピュータ読取可能な記憶媒体。
【請求項１０】
前記コンピュータ読取可能プログラムコードは、
前記再構成可能ハードウェアビットストリームの、前記命令プロセッサによって読取可能な前記再構成可能ハードウェアオブジェクトファイルへの変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードをさらに含む、請求項９に記載のコンピュータ読取可能な記憶媒体。
【請求項１１】
前記コンピュータ読取可能プログラムコードは、
前記高級言語の制御フローグラフ表現への変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードをさらに含む、請求項７〜１０のいずれか１項に記載のコンピュータ読取可能な記憶媒体。
【請求項１２】
前記コンピュータ読取可能プログラムコードは、
前記制御フローグラフ表現の前記制御データフローグラフへの変換を、コンピュータに実行させるためのコンピュータ読取可能プログラムコードをさらに含む、請求項１１に記載のコンピュータ読取可能な記憶媒体。