JP3711206B2

JP3711206B2 - コンパイル方法

Info

Publication number: JP3711206B2
Application number: JP34968698A
Authority: JP
Inventors: チャールズ・リード・ソロモン; アンドレア・オルギアティ
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1997-12-17
Filing date: 1998-12-09
Publication date: 2005-11-02
Anticipated expiration: 2018-12-09
Also published as: US6219833B1; JPH11249904A; DE69737750T2; DE69737750D1; EP0926594A1; EP0926594B1

Description

【０００１】
【発明の属する技術分野】
本発明は、主プロセッサおよび２次プロセッサからなるプロセッサ・アーキテクチャに対する原始コードのコンパイルおよび実行に関するものであり、特に再構成可能な２次プロセッサを用いるアーキテクチャに関するものである。
【０００２】
【従来の技術】
従来のＰＣにおけるペンティアム・プロセッサのような主プロセッサは、特定の計算タスクに最適化されることなく広範囲にわたる計算作業を取り扱うように適応されているという意味において、幅広い用途に対応している。従って、そのようなプロセッサは、並列サブワード・タスクのような計算処理集約的演算を効率的に取り扱うように最適化されていない。そのようなタスクが、コードの実行において重大なボトルネックとなる可能性がある。
【０００３】
この問題を解決する１つの手法は、特定のアプリケーションに特に適応される集積回路の開発である。それらはＡＳＩＣとして知られている(ＡＳＩＣはapplication-specific integrated circuitを省略したもので、特定アプリケーション専用集積回路を意味する)。ＡＳＩＣに応用されているタスクに関する限り、処理性能は一般的に高いが、その構成対象となっていないタスクに関してはＡＳＩＣの性能は一般的に悪い。特定のＩＣは、明らかに、特定のアプリケーションに対して構築することができるが、コンピュータの演算に対して中心にないあるいはそのコンピュータの製作時に確立されていないようなアプリケーションに対して、それは望ましい解決策ではない。
【０００４】
従って、必要に応じて異なるアプリケーションに関して最適化することができるようにするため、ＡＳＩＣが再構成可能であれば非常に役立つ。そのような装置に対するアーキテクチャの最も共通の形式は、設置場所でのプログラム可能なゲートアレイ(すなわちfield programmable gate arrayであり略してＦＰＧＡ)あって、いかなる所与のアプリケーションに対しても適切な構造を持つように構成することができる洗練されたプロセッサ構造である。そのような構造は、適切な文脈で独立プロセッサとして使用することができるが、特にコプロセッサとしての使用に適している。
【０００５】
そのような構成可能なコプロセッサは、主プロセッサの性能を向上させる潜在力を持つ。特定のタスクに関して、主プロセッサでの実行効率の悪いコードを抽出して、そのアプリケーションに関して最適化されたコプロセッサで一層効率的に動かすことができる。そのような「アプリケーション特有」２次プロセッサの継続的開発を通して、カスタムメイドのコプロセッサにとって困難なコードを抽出することによって性能を向上させる可能性が一層魅力的となる。一般的計算処理における特に重要な例は、画像処理におけるループ部分の抽出である。
【０００６】
所望の効率利得を得るため、主プロセッサおよび２次プロセッサの間でコードをどのように分けるべきか可能な限り効率的に決定し、割り当てられたコード部分の最適な実行のため２次プロセッサを構成することが必要である。１つの手法は、コプロセッサ構造に対応付けるため、作成の際コードに目印をつけることである。IEEE Symposium on FPGAs for Custom Computing Machines, Napa, California, April 1995におけるChristian IseliおよびEduardo Sanchez両氏の"A C++ Compiler for FPGA custom execution units synthesis"には、プログラマによる初期コードの適切なタグ付けの後ＶＬＩＷ(すなわち非常に長い命令ワード)構造のＦＰＧＡに対するＣ＋＋の対応付けを伴う手法が利用されている。この手法は、初期的に抽出すべきコードをプログラマが適切に選択することに依存している。
【０００７】
別の手法は、初期コードを評価して２次プロセッサに向ける最も適切なエレメントを決定するものである。Int. IEEE Symposium on Engineering of Computer Based Systems (ECBS), Friedrichshafen, Germany, March 1996における"Two-Level Hardware/Software Partitioning Using CoDe-X"の中でReiner W. Hartenstein、Jurgen BeckerおよびRainer Kressの３氏は、初期コードのどの部分がコプロセッサに対する割り当てにふさわしく、どの部分が主プロセッサのため残されるべきかを評価するプロファイラを組み込むコードサイン・ツールを提唱している。この手法では、抽出されたコードが、後続の反復的プロシージャによってコプロセッサに対して対応付けされることができるように再構成可能コプロセッサ・アーキテクチャに対するＣコードのサブセットのコンパイルが行われる。この手法は、２次プロセッサの使用を拡張するが再構成可能な論理の潜在性を十分に実現してはいない。
【０００８】
別の手法が、バークレー大学のBRASS研究プロジェクトで提案されている。FCCM'97, Symposium on Field-Programmable Custom Computing Machines, April 16-18 1997, Napa Valleyにおける"Datapath-Oriented FPGA Mapping and Placement"においてTim CallahanおよびJohn Wawrzynek両氏が提唱した手法は、ＦＰＧＡ構造への原始コードの対応付けを援助するＦＰＧＡアーキテクチャを表すテンプレート構造を使用する(この手法は、現在、http://www.cs.berkeley.edu/projects/brass/tjc_fccm_poster_thumb.psによってＷＷＷで参照できる)。原始コード・サンプルは、有向非巡回グラフ(すなわちdirected acyclic graphで以下ＤＡＧと略称される)として提示され、次にツリーに縮減される。他のものを含めてこのような基本的グラフ概念は、例えば、Michael Wolfe氏著"High Performance Compilers for Parallel Computing", pages 49 to 56, Addison-Wesley, Redwood City, 1996に記載されているが、ＤＡＧおよびツリーの定義の要点を以下に記述する。
【０００９】
グラフは、ノード・セットおよび稜線セットから構成される。各稜線は、一対のノードによって定義される(またそれらのノードを接続する線として視覚的にみなすることもできる)。グラフは、有向または無向のいずれかである。有向グラフにおいては、各稜線は方向を持つ。グラフの範囲内である１つのノードからそれ自体へ戻る経路を定義することが可能であれば、グラフは循環的であり、そうでなければ、グラフは非循環的である。ＤＡＧは、有向かつ非循環的なグラフである。従って、ＤＡＧは階層的構造である。ツリーは、特別な種類のＤＡＧである。ツリーは「ルート」と呼ばれる１つのソース・ノードを持つ。ツリーにおいてはルートからすべてのその他のノードへユニークな経路が存在する。ツリーにおいて稜線Ｘ−Ｙが存在すれば、ノードＸはＹの親と呼ばれ、ＹはＸの子と呼ばれる。ツリーにおいては、「親ノード」は１つまたは複数の「子ノード」を持つが、子ノードは１つの親だけを持つことができる。一方、一般的ＤＡＧにおいては、子は１つ以上の親を持つことができる。子を持たないツリーのノードは葉ノードと呼ばれる。
【００１０】
Christopher W.Fraser and David R. Hanson, Benjamin/Cummings Publishing Co., Inc., Redwood City, 1995, especially at pp 373407出版の"A Retargetable C Compiler Design and Implementation"において、Tim CallahanおよびJohu Wawrzynek両氏は、Iburgと呼ばれる一般に利用可能なソフトウェア・ツールである"ツリー・カバー"プログラムの使用によって上記のようなツリーをＦＰＧＡ構造に合致させるアプリケーションを紹介している。Iburgは、原始コード・ツリーを入力として取り、この入力を目標プロセッサ上の命令に対応する部分に細分する。この細分化部分はツリー・カバーと呼ばれる。この手法は、細分化部分に関して許容され得るユーザ定義パターンによって本質的に左右されるもので、比較的複雑である。すなわち、この手法は、ツリーの最下部からパターンとの合致を分析し、すべての可能な合致を記録し、次に、どの合致が最低コストを提供するかを判断するため最上部から逐次下降するパスを実行する。この手法は、やはり、あらかじめ定義された許容可能なパターン・セットという形式の大きな初期的制約を必要とし、再構成可能なアーキテクチャの潜在性を完全に実現していない。
【００１１】
【発明が解決しようとする課題】
このように、入力コードの実行において主プロセッサおよび２次プロセッサからなるシステムの性能効率を最大にする観点から、２次プロセッサへのコードの割り当ての最適な選択が可能で、抽出されたコードを実行させるため可能な限り効率的に再構成することができるような、主プロセッサおよび２次プロセッサを含むシステムの計算処理効率を一層向上させる技術および手法の開発が必要とされている。
【００１２】
【課題を解決するための手段】
本発明は、主プロセッサおよび２次プロセッサに対する原始コードをコンパイルする方法を提供する。該方法は、原始コードからのデータフローの選択的抽出、抽出したデータフローのツリーへの変換、１つのツリーを別のツリーへ変換させるための最低編集コスト関係を決定するためのツリー相互の合致の分析、上記最低編集コスト関係に基づくデータフローの１つまたは複数グループの決定ならびに各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローの作成、該包括データフローの使用による２次プロセッサのハードウェア構成の決定、２次プロセッサに対する原始コード呼び出しへの上記データフロー・グループの置き換え、および、残りの原始コードの主プロセッサに対するコンパイルを含む。
【００１３】
この手法によって、２次プロセッサ・アーキテクチャの必要条件を十分考慮しながら、(あらかじめ定められたテンプレートへの対応付けのような)適合性の事前判断を必要とせずに、２次プロセッサへの割り当てのための原始コード・データフローの最適な選択が可能となる。上記最低編集コスト関係を２次プロセッサのアーキテクチャに従って決定し、２次プロセッサの対応する再構成のハードウェア・コストを表すことも可能である。最低編集コスト関係がツリーの分類のため最低編集距離分類法で表現されるとすれば、上記方法は特に効果的である。
【００１４】
包括データフローによってサポートされるグループにおける各データフローをサポートするため原始コードの実行の間二次プロセッサの再構成が必要とされるので、二次プロセッサのハードウェア構成は原始コードの実行の間二次プロセッサの再構成を可能にする。このようにして、該方法はその最も役立つアプリケーションを見出す。従って、二次プロセッサはアプリケーション特定の命令プロセッサであることも、また、プロセッサ・ハードウェアが(本明細書の末尾の補足説明に記載のＣＨＥＳＳアーキテクチャのような)ＦＰＧＡであることもできる。
【００１５】
本発明の一つの側面において、１つのグループの包括データフローは、そのグループにおけるすべてのデータフローを相互に近似対応させ、次にマージさせることによって計算される。
【００１６】
包括データフロー構築の別の手法は、有向非循環グラフとしてデータフローを作成し、有向非循環グラフの葉ノードとルートの間のクリティカル・パスに存在しないリンクの除去によってそれらをツリーに縮減するものである。ここで、クリティカル・パスとは、最も多い数の中間ノードを通過する２つのノード間の経路である。二次プロセッサ・ハードウェアにとって一層適切であれば(例えば、二次プロセッサの演算のタイミングに対してより敏感な基準が見出されるならば)別のクリティカル・パスの基準を適用することもできる。
【００１７】
包括データフローの作成の後更に別のステップを上記方法に含めることができる。このステップでは、包括データフローが原始コードから抽出された更なるデータフローと比較され、包括データフローと十分近似していれば、それらは包括データフローに加えられる。このことにより、二次プロセッへの割り当てにふさわしい原始コードにおけるコードの一層大きい部分またはすべてを二次プロセッサに割り当てることができる。
【００１８】
上述の手法において、有向非循環グラフがツリーに縮減された後、削除されたリンクは保管され、グループのツリーの包括データフローへのマージの後包括データフローに元通り差し込まれる。
【００１９】
【発明の実施の形態】
本発明は、主および二次プロセッサを含むアーキテクチャに対する原始コードのコンパイルに適応される。そのようなアーキテクチャの例が図１に示されている。主プロセッサ１は、パーソナル・コンピュータのペンティアムIIプロセッサのような従来技術の汎用プロセッサである。二次プロセッサ２および(オプションとして)４は主プロセッサから呼び出しを受け取りそれへ応答を返す。各二次プロセッサ２、４は、主プロセッサによって効率的に取り扱われない原始コードの部分を取り扱うことによってこのアーキテクチャの計算処理能力および効率を増加させるため備えられる。ここでオプションとされている二次プロセッサ４は、(ＪＰＥＧ、ＤＳＰなどのような)特定の機能を取り扱うように構成されている。すなわち、このコプロセッサ４の構造は、特定の頻繁に使われる機能を取り扱うように製造業者によって決定される。そのようなコプロセッサ４は、本発明の特定の主題ではない。
【００２０】
対照的に、二次プロセッサ２は、特定の機能のためあらかじめ最適化されてはいないが、その代わり、主プロセッサによって効率的に取り扱われない原始コードの部分の取り扱いを改善することができるように再構成可能なものとされている。二次プロセッサ２はアプリケーション特定構造という利点を持つ。従って、二次プロセッサ２は、Ｘｉｌｉｎｘ４０１３またはＸｉｌｉｎｘ４０００シリーズの他のメンバのような従来技術のＦＰＧＡでよい。フィールド・プログラム可能な算術アレイと呼ばれる代替的クラスの再構成可能な装置が本明細書の末尾の補足説明に記述されている。そのような二次プロセッサは、当該アーキテクチャによって実行されるべきアプリケーションに関する原始コードの所望の部分を取り扱う際計算処理効率を向上させるように構成することができるものである。
【００２１】
当該コンピュータ・アーキテクチャには、主プロセッサ１によってアクセスされ、特定タイプの二次プロセッサ２については二次プロセッサ２によってアクセスされるメモリ３、および入出力経路５が含まれる。入出力経路５は、(例えばプログラミングによって)ユーザがプロセッサと対話することを可能にし、また、プロセッサがすべての他のコンピュータ装置６と対話することができるようにするために必要なすべての更なる入出力経路およびハードウェアを表している。
【００２２】
本発明は、主プロセッサ１と二次プロセッサ２の間の原始コードの最適化された分割に特に適していて、この分割によって、二次プロセッサの最適構成が原始コードに埋め込まれたアプリケーションの当該アーキテクチャによる取り扱いを最適化することを可能にする。本発明は、二次プロセッサにおいて使用されるコードの選択および抽出に極めて役立つ。
【００２３】
本発明の１つの実施形態に従ってとられる手法が図２に示されている。プロセスへの初期入力は原始コード部分である。これは原理上いかなる言語でもよい。本例はＣ言語で実施されているが、本明細書に記述される技術を他の言語で適合する方法は当業者に容易に理解されることであろう。例えば、原始コードはJavaバイト・コードでも可能である。Javaバイト・コードがそのように取り扱われることができるならば、図１のアーキテクチャは、インターネットから原始コードを直接受け取りそれを実行するように特に適応することができるであろう。
【００２４】
図２に示されるように、プロセスの第１のステップは、二次プロセッサ２によって実行される適切なる候補コードの識別である。典型的には、原始コードに対するデータフロー分析を実行し、選択されたコード行によって提示されるデータフローの適切な代表表現を構築することによって、このステップは実行される(ほとんどのプロセスにおいてこのステップの前にコードの手動プロファイル設定が行われる)。これは、一般にコンパイルする際の標準的技術であり、二次プロセッサへの応用は、例えば、Athanas氏ら著の"An Adaptive Hardware Machine Architecture and Compiler for Dynamic Processor Reconfiguration"(IEEE International Conference on Computer Design, 1991, pages 397400)に記載されている。
【００２５】
本発明において採用する手法は、選択されたコードのデータフローを表現するＤＡＧ(すなわち有向非循環グラフ)を構築するものである。この方法の利点は、データフローの抽出のために適切に構成されたコンパイラ下部構造を使用することである。適切なコンパイラ下部構造の１つは、スタンフォード大学によって開発されたＳＵＩＦである(ＳＵＩＦに関する文書はhttp://suif. stanford.edu/によってＷＷＷで参照できる)。ＳＵＩＦは、特に１つ以上のプロセッサからなるシステムを含む高性能システムに対するコンパイラ研究のため案出されたものである。標準的ＳＵＩＦユーティリティを使用してＣコードをＳＵＩＦに変換することができる。当業者がＳＵＩＦを使用してＤＡＧを構築する簡単なプロセスは、ＳＵＩＦのセクションに対してデータフロー分析を実行し、次に分析の結果を記録することである。
【００２６】
原始コードからのＤＡＧの抽出は従来技術のステップである。当該プロセスにおける次のステップは、図２に示されるように、これらＤＡＧのツリーへの変換である。このステップは、二次プロセッサ２による実行のためのコードの最適な選択を行う際の重要な因子である。ＤＡＧは複雑な構造であり、効果的に分析するのが難しい。ＤＡＧのツリーへの縮減によって、ハードウェアへの対応付けを決定する際に重要なデータフローの諸局面を保持しながら、分析的アプローチの効率を大幅に向上させるように構造を十分単純化することが可能とされる。
【００２７】
ＤＡＧのツリーへの縮減は、上記引用の"High Performance Compilers for Parallel Computing"の特に５６から６０ページに記述されている。引用文献で使用されているものとは異なる用語が本明細書において使用されるが、以下に示すように用語は同等である。本発明で構築されるツリーのタイプは、引用文献で言及されている「スパニング・ツリー」に匹敵する。
【００２８】
ＤＡＧのツリーへの縮減において採用される好ましい手法は、葉ノードとルートの間のクリティカル・パスにないリンクの除去である。この点は図３に示されている。ノードＡとノードＢの間のクリティカル・パスは、本発明の第１の実施形態において、最大数のノードを通過する経路として定義される。ＤＡＧは定義によって非循環的であるので、この基準に合致するように明確な経路を定義することができる。同じ最大数のノードを持つノードの間の異なる経路が存在する可能性があるが、それらの経路はすべてツリー構築の目的を満たすものであろう。これらの経路の間で任意の選択を行うことは有効なアプローチであるが、原始コードの対応付けの成功の鍵は、タイミング情報に依存するスケジューリングである。従って、代替的「クリティカル・パス」の間の選択を行う必要がある場合は、(経路におけるノードによって表される演算の各々を実行するためにかかる時間という観点から)最も長い時間がかかるものを選択することが望ましい。後述されるように、タイミング情報に一層直接基づく代替アプローチを採用することができる。また、そのような選択を行う際一貫したアプローチを採用することが望ましい。そうしない場合、本質的に類似したＤＡＧから形態的に異なるツリーが派生する可能性がある。
【００２９】
クリティカル・パス基準というこの第１の実施形態を適用する際に取られるプロセスは次の通りである。第一に、あらゆる葉ノードに関して、ルート方向のあらゆる可能な経路が追跡される。ＤＡＧは有向グラフであるので、これは簡単明瞭である。上述のように、各葉ノードに関して、最も大きい数のノードを持つ経路が選択され、同じ最大数のノードが検出されれば、そのうちの１つが選択される。これが当該葉ノードに関するクリティカル・パスである。選択されなかったすべての他の経路は、出発点に最も近いそれらの稜線において削除される。この削除される稜線は、副次的リンクと呼ばれる(これは参照Wolfe氏文献における"交差リンク(cross link)"と同じ意味である)。ツリーは、クリティカル・パスの集合から成り、副次的リンクを含まない。副次的リンクは別に記憶される。副次的リンクは抽出された原始コードが二次プロセッサ２に対応付けされる時必要となるが、どの原始コードが二次プロセッサにマップされるべきかを決定する際には使用されない。
【００３０】
当然のことであるが、クリティカル・パス基準を使用することなくＤＡＧからツリーを構築することは可能である。クリティカル・パスの使用には特別の利点がある。特に、副次的リンクとしてクリティカル・パスにない交差リンクの除去は、スケジューリングに対する影響をほとんど及ぼさないが、別のアプローチを取る場合、削除される交差リンクは、タイミング従ってスケジューリングにかなりの影響を及ぼす可能性がある。クリティカル・パス基準の使用は、ハードウェアへの対応付けという文脈においてＤＡＧの臨界的特性を可能な限り表現するツリーの構築を可能にする。
【００３１】
図３は、上述のプロセスの適用を示している。原始コード１１は、二次プロセッサ２による実行について考慮される３行を示している。ＤＡＧ１２は、有向非循環グラフとしてこれら３行のコードを示していて、ルート１２６(変数ｅ)および入力としての葉ルート１２１、１２９および１３０が含まれている。
【００３２】
所与の葉ノードからルートへの各経路を評価し各経路におけるノードの数を比較することは簡単明瞭である。ノード１２９(整数値２)からは、ノード１２２、１２３、１２４および１２５を通過するただ１つの経路がある。これは葉ノード１２９からルート・ノード１２６へのクリティカル・パスであり、ツリーに残される。ノード１２１(現在のケースでは以前の演算の結果でありｃと指定されている)からは２つの経路がある。第１の経路はノード１２２、１２３、１２４および１２５を通過し、第２の経路はノード１２７、１２８および１２５を通過する。第２の経路より多くのノードを通過するので、第１の経路がクリティカル・パスであり、第２の経路は上述のように削除される。
【００３３】
残りの葉ノード１３０(変数ｂ)にも２つの経路が存在する。１つの経路はノード１２３、１２４および１２５を通過し、もう一方はノード１２７、１２８および１２５を通過する。いずれもノードの数は同じであり、クリティカル・パスとして選択することができる。しかしながら、上述のようにタイミングおよび形態上の一貫性の観点から、最善の選択を行う更なる規則を設けることが望ましい。そのような更なる規則は、例えば、関連するハードウェアに基づいて決定されるものである。ここでは、第２の経路が選択される。
【００３４】
とるべき次のステップは、ＤＡＧ１２から選択されたクリティカル・パスに基づいてツリー１４を構築することである。これは、すべての非クリティカル・パスを、出発点に最も近いそれら稜線において(すなわちクリティカル・パスに含まれない出発点に最も近い稜線において)切断することによって実行される。考慮すべき第１の非クリティカル・パスは、ノード１２１からノード１２７、１２８および１２５を通過してルート１２６へ達する経路である。これは、ノード１２１および１２７の間の稜線上で切断することができる。すなわち、ツリーにおいて、これは、(１２１に対応する)ノード１４１と(１２７に対応する)ノード１４７の間の稜線１５１の除去によって表現されている。この部分は副次的リンクとして別に保管される。考慮すべき他の非クリティカル・パスは、ノード１３０からノード１２３、１２４および１２５を通過してルート１２６へ到達する経路であり、これは、ノード１３０とノード１２３の間の稜線上で切断することができる。この切断された稜線もまた副次的リンクとして記憶される。
【００３５】
単純な式と同様にＤＡＧにおいてツリーに縮減できるように条件文を表すこともできる。図８にその１つの例が示されている。これは、
If(X < 2)
a=b
else
a=1
という行のデータフローを表現するＤＡＧであり、変数および整数ノード１８１、１８２、１８３および１８４に加えたマルチプレクサ・ノード１８５および"less than"演算ノード１８６を示す。ＤＡＧとして表現され得る原始コードに関して本明細書に示される手法を使用することが可能である点は当業者に認められるであろう。
【００３６】
残されるツリー構造(このケースではツリー１４)は、後述されるように、どの原始コードが二次プロセッサ２に対応付けされるべきかを決定する際に使用できる非常に簡単な構造である。上述の技術が、実施が簡単であるので、ＤＡＧをツリーに変換するため特に適した技術であり、アプリケーションの観点から汎用的であり、クリティカル・パスの使用を通して(各ノードが単一計算処理エレメントを表現すると仮定して)最大数のノードをもつ経路を包含するので統合されるべき計算処理エンジンの最大「深度」を維持する。当業者に認めらように、ＤＡＧをツリーに変換する際にどの稜線が削除されるべきかを決定する代替的手法を採用することも可能である。ＤＡＧからツリーへの縮減プロセスの１つの代替実施形態は、あらゆるノードにタイミング基準の加重(例えば対応する計算処理エレメントを実行するために必要な時間の長さに基づく加重)を割り当て、次に、各経路の累積加重値を比較し、例えば最大累積加重値に基づいて経路を選択してツリーを定義する。二次プロセッサ２のタイミング・パラメータが実用上臨界的因子である場合、特にタイミング依存性が数えらるモードにほとんど関係しない場合(例えば加算より時間のかかる乗算が何度か行われるような構造の場合)、この手法は一層適しているかもしれない。
【００３７】
コンパイル・プロセスにおける次のステップは、図２に示されるように、入力としてツリーを取得し、二次プロセッサ２のための原始コードの選択を決定することである。図２に示されるように、このステップは一連のサブステップから成る。第１のサブステップは、候補データフローから作成されるツリーの分析および分類である。これは重要な独創的ステップであり、以下に詳細に記述する。
【００３８】
この段階でのコンパイル・プロセスの目的は、原始コードに基づいた候補データフローのどれが二次プロセッサによる実行のために最善の選択であるかを可能な限り効果的に決定することである。これは、二次プロセッサのハードウェア特性に非常に依存する。各データフローに対して同じハードウェア代表を使用できるほどすべてのデータフローが類似している場合、二次プロセッサ２への原始コードの対応付けは極度に効率的に行うことができる。従って、二次プロセッサへの対応付けのための候補データフローの効果的選択は、相互に十分類似しているデータフローのセットを見出すことによって実施することができる。これは、候補データフローから作成されるツリーを分析し分類することによって達成される。
【００３９】
本発明のこの実施形態において使用される強力なツリー合致技術は、カナダ西オンタリオ大学のKaizhong Zhang氏によって提唱されたツリー合致アルゴリズムである。これは同氏著"A Constrained Edit Distance Between Unordered Labelled Trees"(Algorithmica (1996) 15:205-222, Springer Verlag)に記載されていて、カナダ西オンタリオ大学によってツール・キットとして提供されている(このツール・キットは、インターネットを通じてftp://ftp.csd.uwo.ca/pub/kzhang/TREEtool.tar.gzから入手することができる)。複数ツリー間の類似性を決定するその他の代替ツリー合致手法を利用することができる点は認められることであろう。本発明のこの実施形態において使用されるツリー合致手法を以下に記述する。
【００４０】
Zhangアルゴリズムの動作原理は以下の通りである。２つのツリーは、動的プログラミング技術を通してノード毎に比較される。この技術は、ある１つのツリーを他のツリーへ変換するために必要な編集演算を最小限にとどめるものである。このような変換のコストを編集コストと呼ぶ。連続的に大きくなるサブツリーの編集コストが相互比較され、検出される最小コストの記録が保持される。計算処理構造は、再帰的動的プログラムの構造として特徴づけられる。再帰的動的プログラムは、作業用動的プログラミング格子を使用してコンポーネント・サブツリーの距離を計算し、中心格子のその結果を記録する。
【００４１】
利用できる編集演算は、挿入、削除および置き換えである。これら演算は、図４に示されている。図４の(ａ)には、５つのノードを持つツリー１５１および６つのノードを持つツリー１５２が示されている。２つのツリーの構造は、ツリー１５１のノード３およびノード５の間に１つのノードを追加しても同一である。この新しいノードはツリー１５２の構造を形成する。従って、ツリー１５１のツリー１５２への変換はこのノードの挿入によって達成され、ツリー１５２のツリー１５１への変換はこのノードの削除によって達成される(補足説明で記述されるＣＨＥＳＳアーキテクチャでは、ハードウェアにおいて"削除"は１単位のアレイの"バイパス"によって表され、これは、アーキテクチャ上設計された極端に低いコストの１例である)。図４の(ｂ)においては、２つのツリー１５１および１５２は同じ構造を持つが、２つのノード３は各ツリーにおいて異なるタイプの演算を表している。従って、一方から他方へツリーを変換させる際ノード３の置き換えが必要である。あらゆるノードは"ラベル"を必要とする。ラベルは、可能な種々のタイプのノードの間のノード・タイプを識別するためノードに付けられたタグである。
【００４２】
前述のように、これらの編集演算の各々はコストを持つ。コストによって代替的選択が可能にされる。例えば、いくつかのアーキテクチャにおいては、挿入および削除、あるいは置き換えによって同一の結果が達成される可能性がある。これらの異なる選択肢のコストは比較することができる。
【００４３】
このアルゴリズムによる２つのツリーの比較の結果、ノード・ペア(t1,t2)というリストが作成される。ここで、t1は第１のツリーに属し、t2は第２のツリーに属する。形成されるペアの各々は、２つのツリーにおける類似したポイントの識別を構成し、t1およびt2が相互に対応することを示唆する。これらペアのリストは、比較されるツリーのいずれかを含むことができるツリーの骨格を定義する。この骨格において、第１のツリーを第２のツリーに変換するため、各ノードt1は、それぞれのt2と置き換えられなければならない。対応のないノードは、それらが属するツリーに従って挿入または削除されなければならない。このようなペアのリストに関して、編集距離が定義される。これは、一方から他方へツリーを変換させるために必要な複数ペアについて累積される編集コストの最小値である。このアルゴリズムは、２つのツリーの間の編集距離、および、その編集距離を達成する変換セットを決定するために考案されている。代替的変換法も可能であるが、それらはより高い累積編集コストを持つであろう。
【００４４】
編集コストに基づいて編集距離を計算する価値は、１つのツリーを表現している構成から対応関係にある別のツリーを表現している構成に二次プロセッサを再構成する際の"ハードウェア・コスト"を表す編集コストを選択することが可能であることである。この"ハードウェア・コスト"は、典型的には、第１の構成を所与として第２の構成を達成するために必要とされる二次プロセッサ資源の測定量である。この点は、例えば、使用される装置の追加領域という観点から考慮されることがある。これらのコストは、二次プロセッサ・ハードウェアの特性によって決定されるであろう。異なるタイプのハードウェアに関しては、挿入、削除および置換演算の物理的実現は異なるであろう。補足説明に記述される再構成可能なＣＨＥＳＳアレイに関しては、"バイパス"演算が最小コストを含み、加算(add)と減算(sub)の間の置換が低コストを持ち、乗算(mul)と除算(div)の間の置換が高価である。
【００４５】
上述のように、２つのツリーの間の編集距離を構築することができる。しかしながら、そのためには更に以下のステップを必要とする。Zhangアルゴリズムまたは同等の手法を使用して、一組のツリーのそれぞれの間の編集距離を示すための分類法を確立することができる。このような分類法の１例が図５に示されている。ツリーの各葉ノード１６１は、ＤＡＧから抽出される候補ツリーを表現し、各中間ノード１６２は編集コストを表現する。ツリーは、葉ノードの各ペアの間のユニークな経路を提供する。ある１つのペアの２つの葉ノードの間の編集距離は、この経路上の各中間ノードで提供されるコストの合計によって把握される。例えば、ツリー＃４、ツリー＃５またはツリ＃６を表現している葉ノードのどのペアの間の編集距離も６である。しかし、ツリー＃１とツリー＃４の間の編集距離は、１２、２２１、１０７、５０および６という値をもつ中間ノードの合計の４９６である。
【００４６】
この分類法は、ツリーの間の変換を行うために必要とされる編集演算の数を示してしる。このような分類法は、候補ツリーの間の変位の度合いに関する測定基準として使用することができるので、価値あるツールである。このように、このような分類の作成によって、以下に記述するように、どのツリーが一緒にまとめることができるほど類似しているかあるいはあまりにも離れているかを容易に決定することができる。これは、編集距離しきい値の設定によって行われる。複数ツリーのグループ内のあらゆる可能なツリーのペアの各々の間の距離が編集距離しきい値より小さい場合、それらツリーは統合のため選択される。編集距離しきい値の値は任意であり、システムの性能を最適化するため特定の主および二次プロセッサの文脈の観点から相応の技術者によって選択されることができるものである。
【００４７】
複数ツリー・グループの統一の利点は、グループ全体について共通のハードウェア構成を使用することができ、各ツリーの機能をサポートする点である。小待ち時間部分的再構成メカニズムが二次プロセッサに対して利用できるＣＨＥＳＳのようなアーキテクチャについては、統一は特に適切である。一つのツリーの機能をサポートする構成から別のツリーの機能をサポートする構成に変更するため再構成が必要とされるが、これらのツリーの間の編集距離が編集しきい値より決して大きくないので、必要とされる再構成の程度が共用可能な範囲内にあることは既知となっている。複数ツリーのグループは、すべてのコンポーネント・ツリーの表現を含む"スーパーツリー(上位ツリー)"の構築によって統一される。スーパーツリーは、作成された後、以前に削除された副次的リンクの再挿入によって、原始コードから抽出された対応ＤＡＧの各々の表現に変換されることができる。次に、完全なスーパーツリーからハードウェア構成が決定される。スーパアーツリーの構築を以下詳細に記述する。
【００４８】
図６は、指定された編集コストしきい値の範囲に入るツリー・グループ(このようなツリー・グループを以下クラスと呼ぶ)からスーパーツリーを構築するステップを示している。ツリー１７１、１７２および１７３は、すべて一緒にスパーツリー１７０に対応付けされることができる。例えばツリー１７1をサポートする構成からツリー１７１をサポートする構成へハードウェア構成を変更するために必要な再構成は、２つのツリーの間の編集距離が編集しきい値より小さいので、実際に実現するに十分な範囲にある。
【００４９】
スーパーツリー構築アルゴリズムのＣ言語プログラムは本明細書の参考資料として提供される。以下、図９および図１０を参照しながら、このアルゴリズムの関数を記述する。
merge:
最大数のノードを持つクラスの中のツリーが、最初のマージ・ツリーとして選択される。等しい数のノードを持つ複数のツリーがある場合、任意の選択を行うことができる。残りのツリーは、ソース・ツリーと呼ばれる。
【００５０】
各ソース・ツリーに対して、以下の演算が適用される。
(本実施形態においてZhangアルゴリズムおよび二次プロセッサ・アーキテクチャから決定される編集コストに基づいて)計算されたマージ・ツリーとソース・ツリーの間の対応関係から、スーパーツリーが次のように構築される。
1. 最初に、対応付けされたノードのうちルートに最も近いノードが考察される。
2. ソース・ツリー演算(source演算)が、対応するマージ・ツリー演算(merge演算)に連結される。
3. ソース演算の子演算の各々に関して、
a. 子が対応付けされていれば、ソースの子に関してステップ２に戻る。
b. 子が対応付けされていなければ、その子がルートであるサブツリー(ソース・サブツリー)になんらかの対応関係あるか否か検討する。
i. 更なる対応関係がない場合、対応するマージ・ツリー・ノードの下でマージ・ツリーにマージするためそのソース・サブツリーを採用する。
ii. ソース・サブツリーの内部に更なる対応関係がある場合、次のようにサブツリーを接続する。
a. この下位の対応関係のマージ演算が既に対応付けされたサブツリーの外側にあるならば、対応付けされたソース演算をソース・ツリーから削除する。この段階には再帰動作が存在する。すなわち、対応付けされた子が既に処理されている場合、さもなければクロス・ツリー・リンクであるものを削除することが、なすべきことのすべてである。
b. これは図９および図１０に示されている。この下位対応関係のマージ演算が既に対応付けされたサブツリーの範囲にあるならば、すべての内包された下位対応関係に関して最も小さい共通の先祖が検出されるまでマージ・ツリーをさかのぼる。最も小さい共通の先祖は、ソース・マッピングのすべてを含む最初のノードである。次に、最小共通先祖親の子として未対応ソース・サブツリーのソース演算を連結することによって、また、現在時サブツリーにおいて最も近い対応付けされたソース演算のすぐ上の未対応ソース演算の子として最小共通先祖を連結することによって、未対応ソース・セグメントがマージ・ツリーに対応付けされる(この場合、"最も近い対応付けされたソース演算"はソース・ツリーの未対応付けセグメントの下方終端を区切るもので、現在時対応関係のサブツリーの範囲内にある対応付けされたノードである。すなわち、対応付けされていないソース・ノードの親はマージ・ツリーの最小共通先祖を子として採用する−この逆も真である)。
【００５１】
混ぜ合わされたツリーのペアは、新しいマージ・ツリーを形成する単一ツリーに正規化される。クラスの中のすべてのソース・ツリーがマージ・ツリーの範囲内に含まれるまでプロシージャは継続する。この結果がスーパーツリーである。
【００５２】
このプロセスが図９および図１０に示されている。図９の(ａ)は、マージ・ツリー２０１およびソース・ツリー２０２という２つのデータフロー・ツリーを示す。比較アルゴリズムによって作成されたノード間の３つの対応関係が存在する。残りのノードは適切に挿入される必要がある。上述のように、最初のステップは、ルートに最も近い対応付け済み演算を検討することである。このケースではルートである。これらの演算Ａは連結される。
【００５３】
この後、ソース・ツリーにおけるＡの子ノードが検討される。ノードＢは、対応関係を持たないし、対応関係のあるノードのいずれの先祖でもない。従って、Ａ:Ａの子としてマージされる(図９の(b)参照)。その他の子ノードＡ、Ｃは(マージ・ツリーのＤおよびＥに対応するＤおよびＥという)子孫の対応関係を持つ。両方の関連マージ演算は、(両者はＡの子孫であるので)既に対応付けされたサブツリーの範囲にある。従って、上記3(b)(ii)(b)に記述のステップに従う必要がある。対応付けされたマージ演算ＤおよびＥの両方を含む最小共通先祖はＸである。かくして、図９の(b)に示されるように、ソース・ツリーのＣは、(Ｘの親である)Ａ:Ａの子およびＸの親としてマージ・ツリーに連結される。マージ(合併)は、ソース・ツリーの残りのノードの連結またはマージによって完結するが、これらすべてのステップは簡単明瞭である。
【００５４】
結果として生成されるスーパーツリー２０３が図１０の(a)に示されている。このサウーパーツリーは、図１０の(b)に示されるように、更なる候補ソース・ツリー２０４とのマージのためのマージ・ツリーの役目を果たす。このケースでは、ソース・ツリーの各ノードはスーパーツリーのノードに対応付けされている。従って、マージは全く簡単明瞭であり、連結(すなわち置換)からのみ構成される。このようなプロセスがすべての候補ツリーがスーパーツリーにマージされるまで続く。
【００５５】
この段階で、原始コードの比較的多い部分が二次プロセッサに割り当てられることを可能にするステップを進めることができる。原始コードは、スーパーツリーの包含のため選択されるその他のＤＡＧ(例えばコードの最も計算処理集約的場所の１つに位置していないため考慮されなかったＤＡＧ)を含む。しかしながら、このようなＤＡＧは、適切に適合された二次プロセッサ上で実行されるならば、主プロセッサ上より迅速に実行できるかもしれない。従って、そのような残存ＤＡＧを後方対応付けプロセスによってスーパアーツリーと比較することには利点がある。Iburgのような従来型後方対応付け技術から導出されるプロセスをこの目的のため利用することができる。
【００５６】
しかし、最も利点のある手法は、再びZhangのアルゴリズムの使用に戻り、原始コードの更なる候補ツリーをスーパーツリーと比較するものであるが、但し今回は一層低い編集コストしきい値を使用する。そのようなＤＡＧから抽出されたツリーが直接スーパーツリーに対応付けされる場合、または、そのような対応関係に関する編集コストが一定の最小限の水準以下になる場合、必要に応じて、これらのＤＡＧのコードを二次プロセッサに割り当て、スーパーツリーを修正することができる。この後方対応付けプロセスによって付加されるそのようなデータフローに関連する制御情報もまた記憶される必要がある。
【００５７】
次に、このスーパーツリーに基づいて、ＤＡＧからツリーへの変換の際に削除された副次的リンクを挿入することは簡単である(後方対応付けによって付加されたＤＡＧもここで挿入される)。結果として生成される構造は、クラス・データフローであり、そのクラスのＤＡＧに存在するすべての情報を表す。(例えば、発生すべきいかなる再構成をも決定するための)スーパーツリー制御情報も存在しなければならない。
【００５８】
このクラス・データフローは、二次プロセッサのハードウェア構成を決定する目的で使用することができるし、二次プロセッサに対する適切な呼び出しを原始コードに縫い込むことを可能にする構造を提供するためにも使用することができる。これらのステップの詳細は以下に記述される。
【００５９】
二次プロセッサへの呼び出しの原始コードへの縫い込みは、スーパーツリーがデータフローの周辺層を規定するので、実際には、クラス・データフローではなくスーパーツリーだけを必要とする。原始コードにおける置き換えられるデータフローに関して必要とされる措置は、データフローの入力(すなわちそのデータフローから縮減されたツリーの葉)をロード・プリミティブと置き換え、データフローの出力(当該ツリーのルート)を読み取りと置き換えることである。当該ツリーの葉およびルートはスーパーツリーに含まれるので、この目的のためにはスーパーツリーだけが必要とされる。データフローに包含されたすべての残りのコードは、二次プロセッサ構成によって取り替えられるので、単に削除すればよい。
【００６０】
図７は、原始コードへの必要な置き換えを達成するための論理インタフェースを示す。入力ツリー＃３がスーパーツリーと共に図示されている。入力ツリー＃３における各ノードは、コンパイラ内部形式表現から得られるそれ自身のユニークな演算ＩＤを持つ。スーパーツリーに関しては、レジスタまたは他のＩ／Ｏ資源が葉およびルートに割り当てられている。このように、入力ツリー＃３とスーパーツリの間の暗黙の対応関係が、入力ツリー・ノードの演算ＩＤと仕様の形式でスーパーツリーに割り当てられたＩ／Ｏ資源の間の対応関係を作成する。図７において"merge"と識別されるステップにおけるこの仕様の適用は、スーパーツリーによって包含されるコードの除去およびコードにおける必要なＩ／Ｏプリミティブの置き換えを可能にする。
【００６１】
クラス・データフローから、二次プロセッサを構成することが可能である。このステップは既知の手法に従って実施することができる。このステップは、(挿入、削除および置換演算を使用し、適切な形式で動的再構成命令を含むことによって)クラス・データフローをネットリストへ縮減し、次に、コンポーネント・データフローの間の再構成の必要条件を考慮しながら、そのネットリストを特定の二次プロセッサ・ハードウェアに対応付ける。従来技術のＦＰＧＡアーキテクチャに関しては、これらのステップは、基本的には、適当な既知のツールの使用によって実行することができる。例えば、ＸＣ４０１３のような標準ＸｉｌｉｎｘＦＰＧＡの場合、適切なＸｉｌｉｎｘツールを使用することができる。最初に、ネットリストがＸｉｌｉｎｘネットリスト形式(ＸＮＦ)に翻訳される。次に、Ｘｉｌｉｎｘ細分化置き換えおよびルート・プログラム(Xilinx Partition Place and RoutプログラムすなわちＰＰＲ)によってこのネットリストを構成可能な論理ブロックおよび入出力ブロックに細分化し、その結果を、ＸｉｌｉｎｘＭａｋｅＢｉｔｓプログラムによって構成ビットストリームに変換する。この手法は、あらかじめ定められた再構成解決手段と共に、Steve Casselman氏による"Run-Time Programming Method for Reconfigurable Computer"に記載されている(この文献は、SB Associates , Inc .of 504 Nino Avenue, Los Gatos, CA 95032, USAが運用する再構成可能コンピューティングに関する円卓ＷＷＷへの貢献として、http://www .reconfig .com/specrept/ 101596/session1/library/cassel.htmで公開されている)。補足説明に記載のＣＨＥＳＳ装置のような再構成可能なプロセッサに関して、そのプロセッサにとって適切なツールを使用して、本質的に同様なプロシジャを実施することができる。
【００６２】
二次プロセッサに対する適切な呼び出しを含む原始コードが実行可能な形式で生成されたならば、また、二次プロセッサ構成が決定されたならば、原始コードはロードされ、実行されることができる。コプロセッサおよび二次プロセッサに対する呼び出しを持つ原始コードが、主プロセッサで実行される。二次プロセッサは、それに抽出されるデータフローを処理するように特に構成されているので、コードの実行速度は顕著に増加する。例えば、本発明のこの実施形態の方法のＪＰＥＧツールキットからｉＤＣＴアルゴリズムへの適用において、これは実際にはＩ／Ｏの制約のためそのような二次プロセッサへの対応付けに関する貧弱な問題ではあるが、２５％の改善が観察された。
【００６３】
このように、上述の方法は、主プロセッサおよび再構成可能な二次プロセッサを含むアーキテクチャにおいて二次プロセッサの最適の使用を可能にする上で特に効果的である。
【００６４】
本発明には、例として次のような実施様態が含まれる。
（１）主プロセッサおよび２次プロセッサに対する原始コードをコンパイルする方法であって、原始コードからデータフローを選択的に抽出するステップと、抽出したデータフローを複数のツリーへ変換するステップと、１つのツリーを別のツリーへ変換させるため、ツリー相互の合致を分析して、最低編集コスト関係を決定するステップと、上記最低編集コスト関係に基づいてデータフローの１つまたは複数グループを決定し、各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローを作成するステップと、該包括データフローを使用して２次プロセッサのハードウェア構成を決定するステップと、上記データフロー・グループを２次プロセッサに対する原始コード呼び出しに置き換えるステップと、残りの原始コードを主プロセッサに対してコンパイルするステップと、を含むコンパイル方法。
【００６５】
（２）上記最低編集コスト関係が、ツリーの分類に関する最低編集距離分類法によって実施される、上記（１）に記載のコンパイル方法。
（３）上記最低編集コスト関係が二次プロセッサのアーキテクチャに従って決定され、二次プロセッサの対応する構成のハードウェア・コストを表す、上記（１）に記載のコンパイル方法。
（４）二次プロセッサのハードウェア構成が原始コードの実行中に二次プロセッサの再構成を許容するものである、上記（１）に記載のコンパイル方法。
（５）二次プロセッサがアプリケーション特定命令プロセッサである、上記（４）に記載のコンパイル方法。
（６）二次プロセッサがＦＰＧＡすなわち設置場所でプログラム可能なゲート・アレイである、上記（４）に記載のコンパイル方法。
（７）二次プロセッサが設置場所でプログラム可能な算術アレイである、上記（４）に記載のコンパイル方法。
（８）包括データフローによってサポートされるグループ内の各データフローをサポートするため原始コードの実行の間に二次プロセッサの再構成が必要とされる、上記（４）に記載のコンパイル方法。
【００６６】
（９）１つのグループの包括データフローが、そのグループにおけるすべてのデータフローを相互に近似対応させ、次にマージさせることによって計算される、上記（１）に記載のコンパイル方法。
（１０）データフローが有向非循環グラフとして作成され、有向非循環グラフの葉ノードとルートの間のクリティカル・パスに存在しないリンクの除去によってそれらグラフがツリーに縮減される、上記（９）に記載のコンパイル方法。
（１１）上記クリティカル・パスが、最も多い数の中間ノードを通過する２つのノード間の経路である、上記（１０）に記載のコンパイル方法。
（１２）上記クリティカル・パスが、最大累積実行時間を持つ２つのノード間の経路である、上記（１０）に記載のコンパイル方法。
（１３）包括データフローの作成の後、包括データフローが、原始コードから抽出された更なるデータフローと比較され、包括データフローと十分近似しているデータフローが包括データフローに加えられる、上記（１０）に記載のコンパイル方法。
（１４）有向非循環グラフがツリーに縮減された後、削除されたリンクが保管され、グループのツリーの包括データフローへのマージの後包括データフローに再挿入される、上記（１０）に記載のコンパイル方法。
【００６７】
（１５）主プロセッサおよび２次プロセッサに対する原始コードをコンパイルするように構成されたコンピュータであって、原始コードからデータフローを選択的に抽出する手段と、抽出したデータフローを複数のツリーへ変換する手段と、１つのツリーを別のツリーへ変換させるため、ツリー相互の合致を分析して、最低編集コスト関係を決定する手段と、上記最低編集コスト関係に基づいてデータフローの１つまたは複数グループを決定し、各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローを作成する手段と、該包括データフローを使用して２次プロセッサのハードウェア構成を決定する手段と、上記データフロー・グループを２次プロセッサに対する原始コード呼び出しに置き換え、残りの原始コードを主プロセッサに対してコンパイルする手段と、を備えるコンピュータ。
【００６８】
（１６）上記最低編集コスト関係が、ツリーの分類に関する最低編集距離分類法によって実施される、上記（１５）に記載のコンピュータ。
（１７）上記最低編集コスト関係が二次プロセッサのアーキテクチャに従って決定され、二次プロセッサの対応する構成のハードウェア・コストを表す、上記（１５）に記載のコンピュータ。
（１８）二次プロセッサのハードウェア構成が原始コードの実行中に二次プロセッサの再構成を許容するものである、上記（１５）に記載のコンピュータ。
【００６９】
（１９）主プロセッサおよび２次プロセッサに対する原始コードをコンパイルする方法を実行するためコンピュータによって実行可能な命令からなるプログラムを格納する該コンピュータによって読み取り可能なプログラム記憶媒体であって、該方法が、原始コードからデータフローを選択的に抽出するステップと、抽出したデータフローを複数のツリーへ変換するステップと、１つのツリーを別のツリーへ変換させるため、ツリー相互の合致を分析して、最低編集コスト関係を決定するステップと、上記最低編集コスト関係に基づいてデータフローの１つまたは複数グループを決定し、各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローを作成するステップと、該包括データフローを使用して２次プロセッサのハードウェア構成を決定するステップと、上記データフロー・グループを２次プロセッサに対する原始コード呼び出しに置き換えるステップと、残りの原始コードを主プロセッサに対してコンパイルするステップと、を含む、プログラム記憶媒体。
【００７０】
補足説明
CHESS アレイ
CHESSアレイは、FPGAにおける場合のようにプログラム可能なエレメントがゲートではなく４ビットの演算論理ユニット(ALU)であるような種々のフィールド・プログラム可能アレイである。このアレイ構成はヨーロッパ特許出願第97300563.O号に記述されている。
【００７１】
CHESSアレイは、ALUおよび切り替えボックス構造をそれぞれ含む交互正方形を持つチェス盤レイアウトから成る。隣接する切り替えボックスのための構成メモリがALUの中に保持される。個々のALUは処理パイプラインの形態で使用することが可能であり、好ましい実施形態において、後続ALUの機能を決定するため先行ALUから命令が動的に提供されるように構成される。ALUは４ビットであり、４ビット入力AおよびBが拡張相互接続ネットワークから直接取り出され、選択的にラッチ可能な出力レジスタを経由して４ビット出力Uが上記ネットワークに提供される。１ビットのキャリー入力および出力がまた提供され、それら自身の相互接続を持つ。
【００７２】
１つのALUの出力Uから別のALUの４ビット命令入力Ｉへ動的命令を提供することができる。ALUの命令を変更するため、１つのALUのキャリー出力カウントを別のALUのCin(キャリ入力)として使用することができる。
【００７３】
CHESS ALUは、入力AおよびBの多重化をサポートするように構成され、また、関連した命令(例えばOR/NOR, AND/NAND)の間の多重化をサポートする。そのような命令の間の再構成は、ハードウェアの増加を必要とすることなく、キャリ入力および出力の適切な使用を通して達成されることができる。より複雑な再構成(例えばAND/XOR, Add/Sub)を次のような２つのALUを使用することによって達成することができる。すなわち、第１のALUは２つの代替的命令の間のマルチプレックスを行うもので、第２のALUはオペランドに関して選択された命令を実行するものである。乗算は、１以上のALUを取り上げるので、乗算演算を含む再構成を一層複雑にする。演算をバイパスするため、所与の入力の演算または伝播性能に結びつく適切な制御を用いて、CHESS ALUのマルチプレクサ機能を使用することは簡単である。命令入力から取得できる関数セットの例を下記表１に示す。ＡＬＵへの命令入力の接続の適切な論理機構に関して利用可能な広範囲にわたる可能性が存在する。それらの関数を表２に記載する。
【００７４】
【表１】

【００７５】
【表２】
名前 U 関数 C _out 関数
ADD A+B
SUBA A-B
A AND B Ui = Ai AND Bi C_out=C_in
A OR B Ui = Ai OR Bi C_out=C_in
A NOR B Ui = NOT(Ai OR Bi) C_out=C_in
A XOR B Ui = Ai XOR Bi C_out=C_in
A NXOR B Ui = NOT(Ai XOR Bi) C_out=C_in
A AND NOT B Ui = Ai AND (NOT Bi) C_out=C_in
A AND NOT A Ui = (NOT Ai) AND Bi C_out=C_in
NOT A OR B Ui = (NOT Ai) OR Bi C_out=C_in
NOT B OR A Ui = Ai OR (NOT Bi) C_out=C_in
A Ui = Ai C_out=C_in
B Ui = Bi C_out=C_in
NOT A Ui = NOT Ai C_out=C_in
NOT B Ui = NOT Bi C_out=C_in
A=B N/A iF A==B then 0,else 1
MATCH1 N/A ワード幅にわたりA AND BおよびOR
MATCH0 N/A ワード幅にわたりA OR BおよびAND
注:N/Aは該当しないことを意味する。
【００７６】
２の補数算術が使用され、この算術と整合するように算術キャリが提供される。MATCH 1の場合、AおよびBの両者において1である少なくとも１つの位置が存在すれば1という値だけが返され、一方MATCH 2の場合AおよびBの両者において0である少なくとも１つの位置が存在すれば0という値だけが返されるので、MATCH関数はそのように(match一致と)呼ばれる。
【００７７】
【発明の効果】
本発明は、主プロセッサ１と二次プロセッサ２の間の原始コードの最適化された分割に特に適していて、この分割によって、二次プロセッサの最適構成が原始コードに埋め込まれたアプリケーションの当該アーキテクチャによる取り扱いを最適化することを可能にする。本発明は、二次プロセッサにおいて使用されるコードの選択および抽出に極めて有効である。
【図面の簡単な説明】
【図１】本発明の実施に適用されることができる汎用コンピュータ・アーキテクチャを示すブロック図である。
【図２】本発明の実施形態に従って主および二次プロセッサに対して原始コードをコンパイルする方法を示す概略流れ図である。
【図３】本発明の１つの実施形態に従ってＤＡＧをツリーに変換させるステップを示す概略流れ図である。
【図４】本発明の実施形態に従ったツリー合致プロセスにおけるノード置換を示す概略流れ図である。
【図５】本発明の実施形態に従った編集距離分類法を示すブロック図である。
【図６】本発明の１つの実施形態に従って提供される包括データフローを示すブロック図である。
【図７】本発明の１つの実施形態に従った包括データフローに関する二次プロセッサ資源の割当てのための論理インタフェースを示すブロック図である。
【図８】条件付きステートメントを取り扱うためマルチプレクサを含むデータフローへのＤＡＧの適用を示すブロック図である。
【図９】図１０と共に、本発明の１つの実施形態に従って候補データフローをマージして包括データフローを形成するステップを示すブロック図である。
【図１０】図９と共に、本発明の１つの実施形態に従って候補データフローをマージして包括データフローを形成するステップを示すブロック図である。
【符号の説明】
１主プロセッサ
２二次プロセッサ
１１原始コード
１２ＤＡＧ(有向非循環グラフ)
１４ツリー

Claims

主プロセッサおよび２次プロセッサに対する原始コードをコンピュータによってコンパイルする方法であって、
コンピュータが、原始コードからデータフローを選択的に抽出するステップと、
コンピュータが、抽出したデータフローを複数のツリーへ変換するステップと、
コンピュータが、１つのツリーを別のツリーへ変換させるため、ツリー相互の合致を分析して、最低編集コスト関係を決定するステップと、
コンピュータが、上記最低編集コスト関係に基づいてデータフローの１つまたは複数グループを決定し、各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローを作成するステップと、
コンピュータが、該包括データフローを使用して２次プロセッサのハードウェア構成を決定するステップと、
コンピュータが、データフローの上記１つまたは複数グループに対して、原始コードを２次プロセッサへの呼び出しに置き換えるステップと、
コンピュータが、残りの原始コードを主プロセッサに対してコンパイルするステップと、を含むコンパイル方法。
上記最低編集コスト関係が、ツリーの分類に関する最低編集距離分類法によって実施される、請求項１に記載のコンパイル方法。
上記最低編集コスト関係が二次プロセッサのアーキテクチャに従って決定され、二次プロセッサの対応する構成のハードウェア・コストを表す、請求項１に記載のコンパイル方法。
二次プロセッサのハードウェア構成が原始コードの実行中に二次プロセッサの再構成を許容するものである、請求項１に記載のコンパイル方法。
二次プロセッサがアプリケーション特定命令プロセッサである、請求項４に記載のコンパイル方法。
二次プロセッサがＦＰＧＡすなわち設置場所でプログラム可能なゲート・アレイである、請求項４に記載のコンパイル方法。
二次プロセッサが設置場所でプログラム可能な算術アレイである、請求項４に記載のコンパイル方法。
包括データフローによってサポートされるグループ内の各データフローをサポートするため原始コードの実行の間に二次プロセッサの再構成が必要とされる、請求項４に記載のコンパイル方法。
１つのグループの包括データフローが、そのグループにおけるすべてのデータフローを相互に近似対応させ、次にマージさせることによって計算される、請求項１に記載のコンパイル方法。
データフローが有向非循環グラフとして作成され、有向非循環グラフの葉ノードとルートの間のクリティカル・パスに存在しないリンクの除去によってそれらグラフがツリーに縮減される、請求項９に記載のコンパイル方法。
上記クリティカル・パスが、最も多い数の中間ノードを通過する２つのノード間の経路である、請求項１０に記載のコンパイル方法。
上記クリティカル・パスが、最大累積実行時間を持つ２つのノード間の経路である、請求項１０に記載のコンパイル方法。
包括データフローの作成の後、包括データフローが、原始コードから抽出された更なるデータフローと比較され、包括データフローと十分近似している更なるデータフローが包括データフローに加えられる、請求項１０に記載のコンパイル方法。
有向非循環グラフがツリーに縮減された後、削除されたリンクが保管され、グループのツリーの包括データフローへのマージの後包括データフローに再挿入される、請求項１０に記載のコンパイル方法。
主プロセッサおよび２次プロセッサに対する原始コードをコンパイルする方法を実行するためコンピュータによって実行可能な命令からなるプログラムを格納する該コンピュータによって読み取り可能なプログラム記憶媒体であって、該方法が、
コンピュータが、原始コードからデータフローを選択的に抽出するステップと、
コンピュータが、抽出したデータフローを複数のツリーへ変換するステップと、
コンピュータが、１つのツリーを別のツリーへ変換させるため、ツリー相互の合致を分析して、最低編集コスト関係を決定するステップと、
コンピュータが、上記最低編集コスト関係に基づいてデータフローの１つまたは複数グループを決定し、各グループ毎にそのグループにおける各データフローをサポートすることができる包括データフローを作成するステップと、
コンピュータが、該包括データフローを使用して２次プロセッサのハードウェア構成を決定するステップと、
コンピュータが、データフローの上記１つまたは複数グループに対して、原始コードを２次プロセッサへの呼び出しに置き換えるステップと、
コンピュータが、残りの原始コードを主プロセッサに対してコンパイルするステップと、を含む、プログラム記憶媒体。