ネステッドループおよびプログラミングツールのためのリコンフィギュラブルコプロセッサアーキテクチャテンプレート
【課題】開発期間が長期化するＡＳＩＣｓの変更設計を容易にするアーキテクチャテンプレートを提供する。
【解決手段】提案するテンプレートから得られるアーキテクチャは一般的なチップシステム（ＳｏＣ）に集積され、ボディが平行のファンクショナルユニットアレイにおいて実行されるオペレーションのエクスプレッションであるネステッドプログラムループを実行するリコンフィギュラブルコプロセッサにより構成されている。
【解決手段】提案するテンプレートから得られるアーキテクチャは一般的なチップシステム（ＳｏＣ）に集積され、ボディが平行のファンクショナルユニットアレイにおいて実行されるオペレーションのエクスプレッションであるネステッドプログラムループを実行するリコンフィギュラブルコプロセッサにより構成されている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータアーキテクチャに関し、特に、アルゴリズムにおけるネステッドループの加速に関する。
【背景技術】
【０００２】
計算機器はユビキタスになり、携帯電話、パーソナルディジタル機器および携帯型オーディオプレイヤーなど多くの電子機器が人々により日常生活において持ち運ばれる製品となっている。
【０００３】
これらの製品はフォンノイマンのアーキテクチャとして知られているコンピューティングパラダイムにしたがう内蔵プロセッサにより実現されてきた。内蔵機器が複雑になればなるほどより速いクロック周波数を必要とし、かつ、より多くのパワーを消費するようになってきた。これは従来型プロセッサが指示を連続的に実行し、かつ、データを連続的に取り出すからである。バッテリを電源とする機器についてフォンノイマンコンピューティングパラダイムは維持されえず、代わりになるものが見出されなくてはならない。
【０００４】
最近、より平行なアーキテクチャへの大きな関心が、マルチメディアおよびコミュニケーションアルゴリズムの強い計算ニーズに向けられている。アプリケーション専用集積回路（ＡＳＩＣｓ）が、アルゴリズムの重要部分において並行に実行される処理の数を増加させるのに用いられており、クロック周波数の増大を回避し、その結果としてエネルギー消費を実用的な限度内に維持している。しかし、ＡＳＩＣｓは開発時間が長く、一度組み立てられると変更されえない。これでは非常に速く変化するマーケットの動きおよび最近の電子機器の短いライフ期間には合致しえない。
【０００５】
プログラマブル手法は実際にはより理想的であり、これがテクノロジーおよびリコンフィギュラブルコンピューティングが実現された経緯である。リコンフィギュラブルコンピュータはコンフィギュレーションメモリのコンテンツを変更することにより、ポストシリコン時においてアーキテクチャが変更されうるマシーンである。リコンフィギュラブルコンピュータの不可欠な要素はプログラマブルマルチプレクサである（図１）。プログラマブルマルチプレクサはインプットＡおよびＢと、アウトプットＣと、Ｓビットのコンフィギュレーションとを有する。Ｓが０に設定された場合、ＡからＣへの経路が生成される。Ｓが１に設定された場合、ＢからＣへの経路が生成される。プログラマブルマルチプレクサを十分に保有することにより、異なるアルゴリズムをより適当に実行するために異なるハードウェアアーキテクチャを迅速に生成するように、機能ユニットおよびメモリ要素を思い通りに接続させることができる。本発明はリコンフィギュラブルアーキテクチャのクラスを得るためのテンプレートである。
【０００６】
存在するリコンフィギュラブルアーキテクチャは（１）ファイングレインアレイおよび（２）コースグレインアレイの２つに分類される。
【０００７】
ファイングレインアレイはフィールドプログラマブルゲートアレイ（ＦＰＧＡｓ）の形成における広く拡散したポピュラリティを獲得した。ＦＰＧＡはプログラマブルスイッチの大きなネットワークにより接続された狭いビットスライスに対して論理機能を実行する小さなプログラマブル機能ユニットの大きなアレイである。機能ユニットは本質的にプログラマブルルックアップテーブル（ＬＵＴｓ）であり、スイッチのネットワークは前述のプログラマブルマルチプレクサからなる。商業的なＦＰＧＡ機器はさまざまなメーカーにより製品化されている。ＦＰＧＡｓは電子プログラミングにより要求される回路の生成を許容するにもかかわらず、ＬＵＴｓの豊富なアレイおよびルーティングスイッチは巨大なエリアおよびパワーの不利益を表わしている。専念ハードウェアにおいて実施されている同じ回路におけるエネルギー欠乏は非常に小さくかつ少なくなる。したがって、バッテリ運転機器におけるＦＰＧＡｓの使用はルールというよりもむしろ排除されてきた。
【０００８】
ＦＰＧＡｓは、必要とされる巨大回路エリアを軽減しかつパフォーマンスを改善するため、標準的なプロセッサ、ならびに、マルチプライヤおよび設置されているＲＡＭｓのような特定ブロックに結合されている。このように、アルゴリズムの特定および重要部分の多くがリコンフィギュラブルファブリックに対して実行され、その一方、その他のわずかな重要部分がプロセッサにより実行される。このようなハイブリッドアーキテクチャの例が研究者により提案され（非特許文献４，１６，１１参照）、かつ、ＦＰＧＡの取引業者により市場に導入された。しかし、これらの回路はいまだシリコンエリアの意味で無駄が多く、かつ、クロック周波数およびコンフィギュレーション時間の意味で遅い。
【０００９】
コースグレインアレイは柔軟性および汎用性を犠牲にすることでファイングレインアレイの前記のような制限を克服する。コースグレインアレイは最近の研究対象とされ、きわめてわずかのアーキテクチャが研究者により提案され（非特許文献３，６，１２，５，７，８，１０，９，１３，２，１４，１７参照）、かつ、会社が設立された（非特許文献１８，１９参照）。これらのアレイは高いグラニュラリティの機能ユニットおよび少ない複合接続ネットワークを有し、マルチメディアおよびコミュニケーションのような目標とするＤＳＰアプリケーションを改善する。機能ユニットは通常は２〜３バイトのスライスよりもむしろ２〜３バイトで計算および論理処理を実行する。結果は汎用的ではないもののわずかなコンフィギュレーションデータを必要とする非常にコンパクトかつ高速のリコンフィギュラブルシステムとなり、このシステムは実行時間において機敏かつ部分的に交換されうる。
【００１０】
他の重要な視点はリコンフィギュラブルユニットがどのように内蔵マイクロプロセッサに接続されているかということである。当初、再構築はプロセッサファンクショナルユニットレベルで始まり、かつ、特別な指示により誘起された（非特許文献１５，１２，１参照）。その後、リコンフィギュラブルユニットはプロセッサに緊密に接続されたコプロセッサになり、かつ、動作するためになおも特別な指示を必要とする（非特許文献４，１６，３，６，１２参照）。より最近では、システムバスに取り付けられ、かつ、ホストプロセッサ指示セットの延長を必要としないコプロセッサが主要な研究対象となってきている（非特許文献２，７，１７参照）。われわれの仕事は最後のカテゴリに合致している。
【非特許文献１】Katherine Compton, Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002.
【非特許文献２】A. Abnous, "Low-Power Domain-Specific Processors for Digital Signal Processing," PhD thesis, Dept. of EECS, UC Berkeley, CA, USA, 2001.
【非特許文献３】T. Miyamori, K. Olukotun, "REMARC: Reconfigurable Multimedia Array Coprocessor," IEICE Trans. on Information and Systems, vol. E82-D, No. 2, February 1999, pp. 389-397.
【非特許文献４】John Reid Hauser , John Wawrzynek, Augmenting a microprocessor with reconfigurable hardware, 2000.
【非特許文献５】Seth Copen Goldstein, Herman Schmit, Matthew Moe, Mihai Budiu, Srihari Cadambi, R. Reed Taylor, Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia.
【非特許文献６】Hartej Singh, Ming-Hau Lee, Guangming Lu, Nader Bagherzadeh, Fadi J. Kurdahi, Eliseu M. Chaves Filho, MorphoSys: An Integrated Reconfigurable System for Data-Parallel and Computation-Intensive Applications, IEEE Transactions on Computers, v.49 n.5, p.465-481, May 2000.
【非特許文献７】Ahmad Alsolaim , Janusz Starzyk , Jurgen Becker , Manfred Glesner, Architecture and Application of a Dynamically Reconfigurable Hardware Array for Future Mobile Communication Systems, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.205, April 17-19, 2000.
【非特許文献８】Reiner W. Hartenstein , Rainer Kress, A datapath synthesis system for the reconfigurable datapath architecture, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.77-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan.
【非特許文献９】Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997.
【非特許文献１０】E. Mirsky, A. DeHon, "MATRIX: A Reconfigurable Computing Architecture with Configurable Instruction Distribution and Deployable Resources," FCCM '96 - IEEE Symposium on FPGAs for Custom Computing Machines, Napa, CA, April 1996.
【非特許文献１１】Alan Marshall, Tony Stansfield , Igor Kostarnov, Jean Vuillemin, Brad Hutchings, A reconfigurable arithmetic array for multimedia applications, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.135-143, February 21-23, 1999, Monterey, California.
【非特許文献１２】R. D. Witting and P.Chow, OneChip: An FPGA processor with reconfigurable logic. In Proceedings of the IEEE Symposium on FPGAs for Cistom Computing Machines (FCCM’96), pages 126-135, 1996.
【非特許文献１３】J.M. Rabaey, “Reconfigurable Computing: The Solution to Low Power Programmable DSP”, Proceedings 1997 ICASSP Conference, Munich, April 1997.
【非特許文献１４】Ebeling, C., Cronquist, D., and Franklin, P. 1996 RaPID - Reconfigurable Pipelined Datapath. In the 6th International Workshop on Field-Programmable Logic and Applications.
【非特許文献１５】R. Razdan and M. D. Smith. High-performance microarchitectures with hardware-programmable functional units. In Proceedings of the IEEE/ACM International Symposium on Mircoarchitecture, pages 172-180, 1994.
【非特許文献１６】C. R. Rupp, M. Landguth, T. Garverick, E. Gomersall, H. Holt, J.M. Arnold, and M. Gokhale. The NAPAadapative processing architecture. In Porceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM’98), pages 28-37, 1998.
【非特許文献１７】Salvatore M. Carta, Danilo Pani, Luigi Raffo. Reconfigurable Coprocessor for Multimedia Application Domain, In Journal of VLSI Signal Processing 44, 135-152, 2006.
【非特許文献１８】CHAMELEON SYSTEMS, Inc. 2000. CS2000 Advance Product Specification. Chameleon Systens Inc., Sna Jose, CA.
【非特許文献１９】Pact XPP Technologies, “XPP-III Processor Overview (White Paper)”, July 2006.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
非特許文献２における仕事は、採用されるタイミングスキームの困難性をもたらし、標準的なセルを基礎とする技術に適用するには幾分非現実的なほどに完全にあつらえられたシリコンの完成を必要とするセルフタイム非同時データ駆動実行が存在する。アーキテクチャは、メモリアドレスの必要シーケンスを生成するためのマイクロコード指示を実行する２つのアドレス生成プロセッサにより特徴付けられている。
【００１２】
非特許文献７におけるアーキテクチャは、大半のマルチメディアおよびコミュニケーション分野で用いられている１６ビットまたは３２ビット言語にスケールを調節するのが困難なＬＵＴを基礎とするマルチプライヤを有する非区分の８ビットのファンクショナルユニットを用いる。階層的な接続スキームが編集の便宜を図るのに十分なだけ構築されている。しかし、この仕事は、さまざまなアプリケーションに採用かつスケール調節されうるアーキテクチャテンプレートというよりもむしろ１つのアーキテクチャの設計を表わしている。
【００１３】
われわれの仕事に最も近いのが非特許文献１７に開示されているものである。アーキテクチャテンプレートは内蔵メモリおよびアドレス生成モジュールのセットに接続されているコースグレインファンクショナルのアレイにより構成されている。アドレス生成モジュールは計算および論理ユニット（ＡＬＵｓ）と、複雑なアドレスシーケンスを生成するためのマルチプライヤとのシリーズを与える段階的カウンタにより実現されている。遅れラインのセットはファンクショナルユニットの制御およびメモリオペレーションと同期する。
【課題を解決するための手段】
【００１４】
われわれのアプローチにおいてアドレス生成ブロックはプラグラマブル累算器により実現され、ＡＬＵｓおよびマルチプライヤを用いる場合と比較してハードウェアの複雑さが低減されている。同期のために遅れラインを増やす代わりに、われわれは単一の遅れラインおよびプラグラマブル巻き時間を有する複数のカウンタを用いて、異なる遅れを伴うイネイブルシグナルのグループを生成する。この方法により、いくつかのアドレスの生成が他のアドレスの生成に対して相対的に遅らされ、アンバランスパイプライングラフにより表現されるループボディの実行が許可される。イネイブルシグナルは各ファンクショナルユニットを通じてデータシグナルに付属し、当該イネイブルシグナルは必要な遅れを伴って次のファンクショナルユニットに到着する。
【００１５】
われわれのアプローチはプログラミングツールのオペレーションの便宜を図るため、接続ネットワーク（部分クロスバー）を明快に構築する。実際、アーキテクチャテンプレートおよびプログラミングツールは、プログラミングが困難なまたは自動化しにくいハードウェア構造が生じるのを回避するために共同設計されてきた。
【００１６】
われわれは内蔵プロセッサのデータインプットおよびアウトプットである必要はないデータソースおよびデータシンクについても考察する。データの出所および宛先はシステムにおけるハードウェアのあらゆる部分であり、システムクロックに同期する必要はない。当該目的のため、われわれはプロセッサバスよりも簡単なインターフェースを提供し、かつ、非同期ＦＩＦＯｓを用いて一のコアを異なるクロックスピードで動いている他のコアに接続する。
【００１７】
提案するテンプレートから得られるアーキテクチャは一般的なチップ上のシステム（ＳｏＣ）に集積されており、かつ、ボディがファンクショナルユニットアレイにおいて実行される演算処理の表現であるネステッドプログラムループを実行するリコンフィギュラブルコプロセッサにより構成されている。ファンクショナルユニットは当該表現において示される原子演算処理を実行することができなくてはならない。データアレイは一または複数のシステムインプットおよび内蔵メモリアレイからアクセスされる。処理データアレイはメモリアレイまたはシステムアウトプットに送り返される。
【００１８】
アーキテクチャは一の演算処理またはデータのアクセスのみが一度に実行されうる標準的なプロセッサにおける実行と比較してネステッドループの加速を可能とする。本発明は多くのアプリケーション、特にマルチメディアおよびコミュニケーションのようなディジタルシグナル処理を含むアプリケーションにおいて応用されうる。アーキテクチャは制御フローの実行に優れているフォンノイマン型のプロセッサとともに利用される。アーキテクチャは複雑なアドレスシーケンスを生成可能なアドレス生成ブロックにより特徴付けられている。コンフィギュレーションレジスタファイルはデータ経路およびアドレス生成ブロックをプログラミングするための情報を保存する。コンフィギュレーションレジスタファイルは上書き可能であるため、システムは部分的にかつ運転時間中に再構築されうる。
【００１９】
プログラムされた数の反復のためまたはファンクショナルユニットにおいて事前にプログラムされたいくつかの条件が満たされるまでアーキテクチャはループする。制御レジスタを用いて初期化が実行され、状態レジスタを用いて投票が可能であり、かつ、リクエストはリクエストシグナルの断定に役立つ。
【００２０】
データストリームインプット、アウトプット、内蔵メモリ、ファンクショナルユニットおよびコンフィギュレーションユニットの数に関してアーキテクチャのスケールが容易に調節される。
【００２１】
われわれは、提案するアーキテクチャテンプレートから得られる複数の一般的な目的のプロセッサおよび複数のコプロセッサをコンピュータシステムに課することをもくろんでいる。プロセッサおよびコプロセッサは同期して、または、非同期のファーストインファーストアウトメモリ（ＦＩＦＯｓ）を用いて接続され、全体として非同期であり局所的に同期したシステムを形成する。
【００２２】
各コプロセッサはオリジナルプロセッサコードにおけるネステッドルームのタグ付けおよび書き直しによりプログラムされている。プログラミングツールはオリジナルコードにおいてコプロセッサインプット／アウトプット作動および制御に置換されるネステッドループグループのそれぞれごとにコプロセッサコンフィギュレーションを演出する。
【００２３】
コプロセッサにおいて利用可能なハードウェアはハードウェアグラフとしてモデル化されている。ループボディにおける表現はデータフローグラフとしてモデル化されている。データフローグラフのソースノードはメモリアウトプットまたはシステムインプットであり、シンクノードはメモリインプットまたはシステムアウトプットである。アレイアドレスにおける表現はアドレスフローグラフとしてモデル化されている。アドレスフローグラフはメモリポートからアドレス生成ノードを通じてタイミングノードまでデータフローグラフを継続し、完全なシステムグラフを形成する。
【００２４】
アドレス生成用のタイミング情報はシステムグラフから抽出される。タイミング情報はデータに沿ってイネイブルシグナルの形で送信され、ファンクショナルユニットを同期させるのに用いられる。
【００２５】
システムグラフはデータフローおよびアドレスフローグラフをハードウェアグラフにマップする順序でシンクからソースに横断し、使用されたリソースはマークされる。該当するフローを実施するように配置されている異なるハードウェアリソースをもたらす複合的なプラグラマブル複合プレクサセレクションが存在する場合は常に次回に試行する対象が決定される。マッピングが不可能になったと判定された場合、最後のハードウェアマッピングは実施されない。代替的な判定がされた場合、ほかの判定が試行される。代替的な判定が無い場合、先の判定が実施されない。この過程はマッピングが解決されるまたはマッピングが不可能であることが証明されるまで継続する。この過程は消耗的かつ完全である。
【発明を実施するための最良の形態】
【００２６】
（Ａ）ネステッドループ
提案されるアーキテクチャテンプレートから得られるコプロセッサはｎビットデータ言語を操作することができる。われわれは次を区別する。（１）コンスタント：コンフィギュレーションレジスタファイルから読み取られたシングルデータ言語。（２）バリアブル：ファンクショナルユニットアウトプットから読み取られたシングルデータ言語。（３）アレイ：メモリから読み出されたデータ言語集合。
【００２７】
アーキテクチャは次のメタ言語定義にしたがって一または複数の連続するネステッドループグループを実行することができる。
【００２８】
{nested_loop_group}
//curled brackets indicates repetition
nested_loop_group ::=
//”::=” means definition
for(index=0; index<index_end; index++) \{
//index and index_end are integers
// ‘\’ is an escape character removing the meta meaning of // the next character
{nested_loop_group;}
{assignment_statement;}
{break_statement;}
\}
assignment_statement::=
(variable | array_element) = expression
//’|’ means exclusive or
array_element ::= array_name\[address_expression\]
address_expression ::=
(((address_expression | alpha) * index + (address_expression | beta)) % modulo) + offset
//alpha, beta, modulo and offset are integers
expression ::=
F({(expression | array | variable | constant)})
//where F is a function computed by some functional unit //given a list of inputs or arguments separated by blank
//spaces
break_statement ::= break( expression );
//causes execution to break if expression evaluates to non //zero
【００２９】
（Ｂ）アーキテクチャ
提案されたアーキテクチャテンプレートの最上位レベルの様子が図２に示されている。これは基本的にファンクショナルユニット（ＦＵｓ）のアレイおよび設置メモリ（ＥＭｓ）のアレイにより構成されている。
【００３０】
ＦＵｓにより処理されるデータはＥＭｓ、リードクロスバーによる他のＦＵｓのシステムインプットまたはアウトプットから供給される。各ＦＵは単一データアウトプットを創出し、そのほかに２次アウトプットとしてフラグを創出する。当該フラグはリードクロスバーにより、当該フラグが制御インプットとして使用される他のＦＵｓに発送される。ＦＵｓにより処理されるデータはライトクロスバーにより定義されたルートを用いてＥＭｓに書き戻される、または、システムアウトプットに送り出される。
【００３１】
メモリのアドレスはアドレス生成器から出てくる。メモリのバンド幅が本システムのパフォーマンスにとって重要であり、図２においてすべての設置メモリはデュアルポートメモリとして開示されている。シングルポートメモリも採用されうる。
【００３２】
コンフィギュレーションレジスタファイルは、プラグラマブルＦＵｓ、リードおよびライトクロスバー、ならびに、アドレス生成ブロックのコンフィギュレーションを定義するデータを含むレジスタを保持している。それはアドレスおよびデータの計算に用いられるコンスタントを保存する。コンフィギュレーションレジスタファイルは、制御および状態レジスタにアクセスするためのコンフィギュレーションインターフェースを通じてアクセスされる。コンフィギュレーションレジスタファイルはアドレス付与可能であり、システムは部分的に実行時間が再構築可能である。
【００３３】
アドレス生成ブロックは図３に示されている。そのアーキテクチャはアーキテクチャ自体の最上位レベルの様子に類似しており、言い換えるとリコンフィギュラブルプロセッサの内部の小さなリコンフィギュラブルプロセッサのようである。ＦＵアレイの代わりに累算器レイ（ＡＡ）があり、リードおよびライトクロスバーのそれぞれはインプットクロスバーおよびアウトプットクロスバーのそれぞれとして現れている。
【００３４】
ＡＡはタイミングユニットからのシグナルにより許可される特別の累算器の集合を含んでいる。累算器はアウトプットクロスバーによりメモリポートに発送されるアドレスを創作する。アウトプットクロスバーはあるメモリに保存されている、他のメモリのアドレスとして使用されるアドレスを発送する。これによりメモリスペースを犠牲にしてアドレスを生成することに顕著な柔軟性をもたらす。他の累算器はＡＡ自体にフィードバックされる中間値を創作する。インプットクロスバーは複合アドレスシーケンスを生成するために中間値をフィードバックさせ、コンフィギュレーションレジスタから累算器にコンスタントを発送する。
【００３５】
アドレスはネステッドループインデックスの機能である。タイミングユニットはＡＡを許可するシグナルのグループを生成する。イネイブルシグナルは許可クロスバーによりＡＡに伝送される。許可クロスバーはイネイブルシグナルをシステムインプットに発送して外部データのインプット許可を、頃合を見計らって行いかつ同期させる。累算器の許可は生成されたアドレスをそのメモリポートに同行させる。リードポートの場合、イネイブルシグナルはＦＵｓを通じてメモリから読み出されたデータに同行する。ＦＵｓにおいてイネイブルシグナルはデータと同じだけ遅れ、許可およびデータを同位相に維持する。
【００３６】
図３に示されている制御ブロックはユーザのコマンドに応答してコプロセッサを初期化し、始動し、かつ、投票する。ある状態がファンクショナルユニットにおいて検出された場合、または、システムインプットがデータ枯渇もしくはアウトプットが過剰になる場合、コプロセッサが失速して立ち往生する。
【００３７】
ループインデックスは前述のようにネステッドループシンタックスにおいてユニット繰上げにより進行する。各ネステッドループグループはタイミングユニットにおいて最終カウント値がプログラムされているカスケードカウンタを用いて実行されたインデックスのグループを用いる。
【００３８】
タイミングユニットが図４に示されている。第１行がループインデックスｉ，ｊおよびｋに対するイネイブルシグナルを実行するマトリックスにおいてプラグラマブルカウンタが接続されている。続く列はループインデックスの遅れ要素を創出する。最後の行は常にループインデックスの最も遅れた要素を含んでいる。第１カウンタはインデックスｉを表わし、クロックサイクルごとに繰り上げられる。カウンタが最終値に到達したとき、アウトプットシグナルを巻くとともに鼓動して次の外側のカウンタを１つだけ進める。最後のカウンタが終端に達したとき最も外側のループが終了しネステッドループグループが遂行される。優先エンコーダがカスケードカウンタにおいてプログラムされた０ではない最終カウント値から最も外側のループ（end_sel）を確認する。この情報はいずれのカウンタカラムが演算処理を終結させるとともに制御ブロックにおいて使用されるかを示している。
【００３９】
基本インデックスｉの許可をプラグラマブル値だけ遅延させる回路が図５に示されている。各フリップ・フロップＤは１サイクルだけｉ_ｅｎ（ｔ）を遅延させる。プラグラマブル乗算器は所望の遅れを選択する。破壊状態（下記参照）が存在する場合、フリップ・フロップを禁止するとともにアウトプット許可を遮蔽することにより遅れユニットの状態は凍結されている。Ｐ個のメモリポートがシステムに存在する場合、最多でＰ個の異なる遅延した許可が必要とされる。実際にはより少ない遅延した許可が実行される。
【００４０】
現実のアドレスは１つの繰り上げにより進まないので、図６および図７に示されている乗算器は前記のようにaddress_expressionによりあたえられる複合的なアドレスシーケンスを生成する責任を負う。
【００４１】
図６に示されている基礎累算ユニット（ＢＡＵ）はRESTART_ENシグナルが鼓動された後でSTARTインプットにより特定される値に初期化し、INCRインプットにより特定される値を累算する。累算器の現在および次回アウトプットのそれぞれはCNTおよびCNT_NXTシグナルにより与えられる。
【００４２】
図７に示されている複合累算ユニットは次の機能性をＢＡＵに加える。すなわち、コンフィギュレーションインプットMODULOにより特定されるモジューロにおいて実行される累算が実行され、OFFSETインプットシグナルにより特定される値に加えられる。
【００４３】
各累算器はタイミングユニットにおいて創造されたイネイブルシグナルグループにより駆動されｒｙ許可クロスバーからENシグナルおよびRESTART_ENシグナルを選択する。図８に示されているように第１の許可グループ（遅延したもの）が選択され、かつ、ENおよびEN_RESTARTに対するイネイブルシグナルが当該選択グループから選択される。同様の手法がシステムにおいて外部データの受け入れの承認に用いられるイネイブルシグナルを選択するために採用される。この方法において外部データのインプットが頃合を計られるとともに同期させられる。
【００４４】
図９はインプットクロスバーからの累算器インプットの選択を示している。START、OFFSETおよびINCRシグナルはコンフィギュレーションレジスタに保存されているコンスタント、または、他の累算器により生成されたCNTおよびCNT_NXTシグナルから選択される。
【００４５】
図１０はアウトプットクロスバーにおけるメモリポートアドレスの選択を示している。累算器により生成されたCNTシグナルまたはメモリから読み出されたデータが選択されてメモリポートのアドレスを形成する。累算器のENシグナルおよびRESTART_ENシグナルは生成されたアドレスをメモリポートにしたがわせる。メモリポートがリードポートである場合許可は読み出されたデータをファンクショナルユニットに同行させ、あるいは、読み出されたデータがアドレスとして使用される場合、許可はアウトプットクロスバーに戻るデータにしたがう。メモリポートがライトポートである場合、ENシグナルおよびRESTART_ENシグナルは無視される。
【００４６】
図１１はファンクショナルユニットに対するインプットのリードクロスバーを用いた選択を示している。インプットはシステムインプットもしくはメモリアウトプットポートまたは他のファンクショナルユニットのアウトプットからもたらされる。このアーキテクチャテンプレートはあらゆるファンクショナルユニットがイネイブルシグナルを次のファンクショナルユニットに通過させるとともに、当該イネイブルシグナルをファンクショナルユニットそれ自体と同じ数の潜伏サイクルだけ遅延させる責任がある特別インプットを有していなくてはならないことを考慮する。この方法においてイネイブルシグナルは当該イネイブルシグナルが参照するデータのそばに保存または維持される。ファンクショナルユニットは当該ファンクショナルユニットに関係するのをやめるインプットENシグナルを消失する一方でインプットRESTART_ENシグナルをアウトプットENシグナルに伝送するように構成されうる。この実行の有用性は後で明らかになる。
【００４７】
図１２はライトクロスバーにおけるシステムアウトプットおよびメモリインプットの選択を示している。これらはファンクショナルユニットアウトプットから選択される。許可はデータに同行するとともにメモリ書き込み許可またはアウトプット要求シグナルとして用いられる。
【００４８】
制御／コンフィギュレーション、データインおよびデータアウトインターフェースが図１３に示されている。
【００４９】
制御／コンフィギュレーションインターフェースは、それが選択されていることを示すとともに、内部レジスタの選択に用いられるAddressインプットベクトルを有効化するRequest_inインプットシグナルを有している。書き込み／読み出し停止シグナルは意図されたアクションを選択する。データはcrt_data_inポートに書き込まれ、かつ、crt_data_outポートから読み出される。Request_outシグナルは演算処理の終了またはある状態が検出されかつコプロセッサが停止された等のイベントにフラグを立てる。
【００５０】
インターフェースのデータはReq_inインプットシグナルベクトルを有している。各要素Req_in[i]はインターフェースｉのデータが選択されているとともにインプットしデータを有しているData_in[i]ベクトルを有効化することを示している。
【００５１】
Ack_in[i]シグナルはData_in[i]を読み出すリクエストReq_in[i]が受け容れられかつ実行されるところの中核駆動インターフェースＩを語るのに用いられる。Ack_in[i:シグナルはそれが許可クロスバーにより選択されるところのアドレス生成ブロックからもたらされる。
【００５２】
データアウトインターフェースはReq_outアウトプットシグナルベクトルを有している。各要素Req_out[i]はデータアウトインターフェースｉが選択されておりかつアウトプットデータを有するData_out[i]ベクトルを有効化していることを示している。このインターフェースにより送出されたデータが受容されたとき、承認シグナルAck_out[i]は外側から主張され、あるいは、データ損失を防止するためにコプロセッサが立ち往生させる。外側の観点から、最後のリクエストからデータを受容することが不可能であったのでなければAck_out[i]は常に主張される。
【００５３】
図１４はアーキテクチャに対する基礎制御レジスタを示している。これはコプロセッサを初期化するInitビット、コプロセッサを許可するEnビット、および、Request_outシグナルによりコプロセッサからの制御リクエストを許可するReq_enビットという３つのビットを含有している。
【００５４】
図１５は基礎状態レジスタを示している。これはコプロセッサの投票を許容する単一のBusyビットを含有している。
【００５５】
基礎制御ユニットは図１６に示されている。コプロセッサは制御ビットEnおよびI/O許可ビットが現出されているときは常に許可され、END(t)またはbreakシグナルが現出されないままにされるまで許可のままに維持する。当該シグナルが生じたときは常に、コプロセッサを停止するフリップ・フロップにロジックおいてロジック「１」が捕らえられる。許可されたコプロセッサは外側のループインデックスおよびすべての遅延した許可グループを順番に許可するシグナルi_en(t)により現出される最も内側のループインデックス活性を有している。
【００５６】
制御アウトプットリクエストが許可された場合（Req_en＝1である場合）、breakシグナルまたは最も遅延したEND(t-DP)が生じたときRequest_outシグナルは現出される。
【００５７】
END(t)シグナルおよびEND(t-DP)シグナルは最も外側のループのラップアラウンドシグナルである。乗算器は図４において説明されたend_selシグナルをi_en、j_enまたはk_enシグナル、遅延がないおよびDPサイクルだけ遅延したバージョンからインデックス許可を選択するのに用いられる。
【００５８】
ステータスレジスタのBusyシグナルは図１６に示されているように生成される。コプロセッサがi_en(t)アクティブにより許可されている場合、または、コプロセッサが演算処理を完了していない、すなわちEND(t-DP)またはbreakが現出していない場合は当該コプロセッサはビジーである。
【００５９】
Breakシグナルはディレイユニットにおけるループインデックス許可の生成を不可能にするために用いられる（図４）。これは基本的に登録され、反対の、かつ、１サイクル遅延したbreakシグナルのバージョンである。
【００６０】
ファンクショナルユニットからの遮断状態の選択が図１７に示されている。縮小／拡大可能な理由のため、各ファンクショナルｉユニットは単一の遮断状態シグナルcond_iのみを生成することができる。本質的にファンクショナルユニットｉはさまざまな理由のために遮断状態に火をつけるようにプログラムされている。しかし、外からはファンクショナルユニットごとに単一の遮断シグナルが存在するように見える。コンフィギュレーションビットcond_i_en_tellsは遮断状態cond_iが許可されたか否かを語る。
【００６１】
I/O依存システム許可の選択が図１８に示されている。ループボディ表現がシステムインプットｉを含む状況で、そのインプットにおいて有効な、Req_in_iシグナルによりシグナル化されるデータが存在する場合にはコプロセッサは許可されうるのみである。同様に、ループボディ表現の結果がシステムアウトプットｊに送られる状況で、Ack_out_jシグナルによりシグナル化される送出データが実際に他のシステムにより読み出された場合、コプロセッサは許可されうるのみである。このシグナルが現出したとき、それは前回サイクルにおいて送られたシグナルが読み出されたことを意味している。現出のとき、コンフィギュレーションビットno_in_iおよびno_out_jはシステムインプットｉおよびシステムアウトプットｊがループボディ表現に存在しないことを示しており、したがってシステムを停止することはできない。
（Ｃ）プログラミングツール
コプロセッサプログラミングフローが図１９に示されている。ユーザがネステッドループシーケンスコードを前記のシンタックスにしたがって書くことにより始まる。コプロセッサプログラミングツールはネステッドループ試験すコードおよびハードウェアアーキテクチャの記述をインプットし、コプロセッサコンフィギュレーションをテキストファイル、ファイルを有するソフトウェアおよびハードウェア記述言語（ＨＤＬ）におけるコンフィギュレーションメモリイメージといった複合フォーマットでアウトプットする。テキストファイルは人間が視覚を通じて読むことが可能であり、ユーザにフィードバックを与えるために使用される。ソフトウェアはコプロセッサを成形かつ動作するいくつかのプログラムに含まれうるシーケンスのコンフィギュレーションメモリイメージを含むファイルを有する。ＨＤＬコンフィギュレーションイメージはシステム高速変化のためのＦＰＧＡエミュレーション、または、システム詳細評価のためのＨＤＬシミュレーションにおいて使用される。さらに、アーキテクチャのソフトウェアモデルはＦＰＧＡエミュレーションのスピードおよびＨＤＬシミュレーションの詳細度を和解させるハードウェア記述ファイルからコンパイルされる。ソフトウェアにより創作された結果（アウトプットデータ）、ＨＤＬおよびＦＰＧＡモデルはユーザにより解析され、インプットネステッドループコードの改良の案内に用いられる。
【００６２】
ハードウェアアーキテクチャは使用されたファンクショナルユニットを参考するファイルにおいて記述されている。ファンクショナルユニットの記述はファンクショナルユニットストアに置かれる。ハードウェア記述ファイルのシンタックスは次に示されるものと等価である。
【００６３】
//Constant declaration section
{({constant_name})}
//Input/output declaration section
{input input_name\[range\]}
{output output_name\[range\]}
range ::= integer..0
/Memory declaration section
{memory memory_name (singleport | twoport | dualport)
addrA\[range\] dataA\[range\]
[addrB\[range\] dataB\[rage\]]}
//Functional unit declaration section
{functional_unit functional_unit_name functional_unit_type}
//Read Crossbar declaration section
{functional_unit_name.input_name <=
({functional_unit_name.output_name}) ({memory_name.(dataA | dataB)})
({constant_name})
//Write Crossbar declaration section
{output_name <= ({functional_unit_name.output_name})}
{memory_name.(data | dataB) <=
({functional_unit_name.output_name})}
//Address Generator declaration section
//Timing Unit
number_of_nested_loops := integer
number_of_enable_delay_groups := integer
//enable groups become named en_grp_0, en_grp_1, …, up to //en_grp_number_of_enable_delay_groups-1
//enabled signals in enable group I become named //en_grp_i.en_0, en_grp_i.en_0, …, up to
//en_grp_i.en_number_of_nested_loops-1
//Accumulators declaration section
number_of_baus := integer
number_of_caus := integer
//accumulators become named bau_0, bau_1, …, up to //bau_number_of_baus-1 or cau_0, cau_1, …, up to //cau_number_of_caus-1
//Enable Crossbar declaration section
{(bau | cau)_name.(en restart_en) <=
({en_grp_name.(en restart_en)})}
// Input Crossbar declaration section
{(bau | cau)_name.start <=
({bau_name.cnt_nxt} {constant_name})}
{(bau | cau)_name.incr <=
({bau_name.cnt} {constant_name})}
{cau_name.offset <= ({bau_name.cnt} {constant_name})}
// Output Crossbar declaration section
{memory_name.(addrA | addrB) <=
({cau_name.cnt} {memory_name.(data | dataB)})}
【００６４】
アーキテクチャ記述の一例は次のとおりである。
【００６５】
//Input/output declaration section
input I0[31..0]
output O0[31..0]
//Memory declaration section
memory M0 dualport
addrA[511..0],dataA[31..0] addrB[511..0] dataB[31..0]
memory M1 dualport
addrA[511..0] dataA[31..0] addrB[511..0] dataB[31..0]
memory M2 dualport
addrA[511..0] dataA[31..0] addrB[511..0] dataB[31..0]
//Functional unit declaration section
functional_unit ADD1 adder_32
functional_unit ADD2 adder_32
functional_unit MULT1 mult_32
functional_unit MULT2 mult_32
functional unit MUX mux_2_1_32
//Read Crossbar declaration section
ADD1.d_input0 <= (I0 M0.dataA M1.dataA MULT1.d_output)
ADD2.d_input1 <= (I0 M0.dataB const_rd MULT2.d_output)
MUX.s_input <= (ADD1.zero_flag ADD2.zero_flag)
MUX.d_input0 <= (MULT1.d_output M2.dataA)
MUX.d_input1 <= (MULT2.d_output M2.dataB)
//… and so on for other FUs
//Write Crossbar declaration section
O0 <= (ADD1.d_output MULT1.d_output)
M0.dataB <= (ADD1.d_output MULT1.d_output)
M1.dataB <= (ADD2.d_output MULT2.d_output)
//… and so on for other memory ports
//Address Generator declaration section
//Timing Unit
number_of_nested_loops := 3
number_of_enable_delay_groups := 3
//Accumulators declaration section
number_of_baus := 4
number_of_caus := 2
//Enable Crossbar declaration section
cau_0.(en restart_en) <= (en_grp_0.en_0 en_grp_1.en_1)
//… same for other baus and caus
bau_0.(en restart) <= (en_grp_1.en_1 en_grp_2.en_2)
//… same for other baus and caus
// Input Crossbar declaration section
bau_1.start <= (bau_2.cnt_nxt const_addr)
bau_1.incr <= (const_addr_incr bau_2.cnt)
cau_2.offset <= (const_addr_offset bau_3.cnt)
//… same for other baus and caus
// Output Crossbar declaration section
M0.addrA <= (cau_3.cnt cau_0.cnt M2.dataB)
//… same for other memories
【００６６】
コンフィギュレーション記述テキストファイルはアーキテクチャ記述ファイルに類似するシンタックスにより書かれるが、目的のためのすべての可能性があるソースの競争の代わりに指定ソースを特定する。言い換えると、それは排他的な分離の競争の代わりに用いられる。可能性があるシンタックスの記述は次のとおりである。
【００６７】
{config_sequence}
config_sequence ::=
label: config_sequence begin {configuration} end
configuration ::=
configuration begin config_body end
config_body ::=
data_path_config addr_gen_config
data_path_config ::=
fu_config read_xbar_config write_xbar_config
fu_config ::=
{fu_name.parameter_name = parameter_value}
//parameter name and parameter value depend on the //functional unit being used
read_xbar_config ::=
{functional_unit_name.input_name <=
(input_name | functional_unit_name.output_name | memory_name.(dataA | dataB) | constant_name )}
write_xbar_config ::=
{memory_name.((dataA | dataB) write) <=
functional_unit_name.(output_name (out_en|out_restart_en))}
{output_name.(data_out req_out) <=
functional_unit_name.(output_name (out_en|out_restart_en))}
addr_gen_config ::=
tu_config acc_config enable_xbar_config input_xbar_config output_xbar_config
tu_config ::= end_array delay_array
end_array ::= ({integer})
//list must have number_of_nested_loops elements
delay_array ::= ({integer})
//list must have number_of_enable_delay_groups elements
acc_config ::=
cau_name.modulo = integer
enable_xbar_config ::=
{(bau | cau)_name.(en restart_en) <=
en_grp_name.(en_name en_name)}
input_xbar_config ::=
(bau | cau)_name.start <=
(constant_name | bau_name.cnt_nxt )
(bau | cau)_name.incr <=
(constant_name | (bau | cau)_name.cnt )
cau_name.offset <= (constant_name | (bau | cau)_name.cnt)
output_xbar:config ::=
memory_name.(addrA | addrB) <=
((bau | cau)_name.cnt | memory_name.(data | dataB))
【００６８】
コプロセッサプログラミングツールのアルゴリズムは次のように略述される。
【００６９】
coprocessorTool (nested_loop_sequence_code){
SG = parseNLSC(nested_loop_sequence_code);
nodeList = createNodelist(SG);
HG = parseHW(architecture_description)
if (map(nodeList.head, SG, HG) == true)
writeConfigurationImages();
exit(SUCCESSFUL);
else
exit(UNSUCCESSFUL;)
}
【００７０】
ここで第１段階はネステッドループボディにおける表現を解析し、各ネステッドループに対するサブグラフにより構成される完全なシステムグラフＳＧを創造することである。これはファンクションパーズＮＬＳＣ(nested_loop_sequence_code).により遂行される。各ネステッドループグループはコンフィギュレーションメモリイメージを引き起こす。各ネステッドループグループに対するサブグラフはデータフローグラフおよびアドレスフローグラフという２つの部分を有している。
【００７１】
データフローグラフ（ＤＦＧ）は次のようなタイプのノードを有している。
【００７２】
ソースノード：
・メモリノード（データアウトプットポート）
・システムデータインプットノード
・コンフィギュレーションコンスタントノード
シンクノード：
・メモリノード（データインプットポート）
・システムデータアウトプットノード
中間ノード：
・ファンクショナルユニットノード
アドレスフローグラフ（ＡＧＦ）は次のようなタイプのグラフを有している。
【００７３】
ソースノード：
・メモリノード（データアウトプットポート）
・タイミングユニットノード（イネイブルシグナルアウトプットポート）
・コンフィギュレーションコンスタントノード
シンクノード：
・メモリノード（アドレスインプットポート）
・システムデータインプットノード（承認シグナル）
中間ノード：
・累算器ユニットノード
ＤＦＧおよびＡＦＧの端部はソースノードから中間ノードに向けられ、中間ノードから他の中間ノードに向けられ、かつ、中間ノードからシンクノードに向けられる。
【００７４】
ＤＦＧおよびＡＦＧは、ＡＦＧのメモリシンクノードおよびＤＦＧのメモリソースノードを併合することにより単一のコンフィギュレーショングラフＣＧにまとめられうる。完全なシステムグラフＳＧは連続的なＣＧｓを連鎖することにより構築されうる。一のＣＧのメモリシンクノードおよび次のＣＧのメモリソースノードを併合することにより当該一のＣＧが当該他の
ＣＧに連鎖される。これにより次のコプロセッサコンフィギュレーションで使用されるデータを設置メモリに残しておくことが可能となる。このメカニズムは意識的なまたは意図的なキャッシングメカニズムと呼ばれうるものであり、統確率的な局所性を不当に使用する従来のキャッシュよりも優れたパフォーマンスを示す。
【００７５】
次の例はＣＧが得られるところのネステッドループグループを示す。
u = α0*(i-8)+β0
v=j
w = ((α1*i+β1)*j + β2)%γ)+δ
x = M2.dataA[j-5]
for(i=0; i<i_end; i++) {
for(j=0; j<j_end; j++)
d[u] += a[v]*b[w] + c[x];
}
【００７６】
本実施形態におけるネステッドループに対するＤＦＧが図２０に示されている。これから明らかなようにＤＦＧがネステッドループグループのボディにおける表現に追従している。グラフの各ノードはＦＵノードまたはメモリノードを表わしている。リード、ライトまたはＦＵの動作はパイプラインで連結され、各動作の潜伏が図２０に示されている。メモリ読み出しａ［ｖ］またはｂ［ｖ］からメモリ書き込みｄ［ｕ］に至るグラフにおける最長の経路は９サイクルにわたっている。メモリ読み出しｃ［ｘ］からメモリ書き込みｄ［ｕ］に至る経路は４サイクルにわたっている。これはメモリ読み出しｃ［ｘ］がメモリ読み出しａ［ｖ］およびｂ［ｖ］に対して９−４＝５サイクル遅れ、メモリ書き込みｄ［ｕ］はメモリ読み出しａ［ｖ］およびｂ［ｗ］に対して９−１＝８サイクル遅れることを意味している。このアーキテクチャテンプレートによればアドレスを計算する際に遅れは生じない。このような潜伏における相違は異なる数のパイプラインステージを伴うＦＵｓにのみ起因する。しかし、アドレスの計算が潜伏により影響を受けるような場合までこの手法の適用範囲はのびている。
【００７７】
アドレスｕ，ｖ，ｗおよびｘの計算に対するＡＦＧが図２１に示されている。アドレスの計算はタイミングユニットにより生成されたイネイブルシグナルｉ_ｅｎおよびｊ_ｅｎにより推進される。Ｄサイクルノードｕ（ｔ−８）だけ遅れる必要があるアドレスはシグナルｉ_ｅｎ（ｔ−Ｄ）およびｊ_ｅｎ（ｔ−Ｄ）を伴う遅れ許可グループを用いる。アドレスｕ，ｖおよびｘは１つのＢＡＵのみが計算される必要がある一方、アドレスｗはより複雑でありＢＡＵにより供給されるＣＡＵを必要とすることに注意されたい。
【００７８】
同音意義語メモリｕ（ｔ−８），ｖ（ｔ），ｗ（ｔ）およびｘ（ｔ−５）の併合によるＤＦＧおよびＡＦＧの連鎖は本実施形態におけるネステッドループグループに対するＣＧを生み出す。ネステッドループグループのシーケンスが存在していたとすると、各ＣＧｓは同様の方法により連鎖されて完全なＳＧを生み出したであろう。
【００７９】
創出されたＳＧを有すると、このグラフにおけるノードがシステムアウトプットノードからシステムインプットノードに向かって第１ファッションの幅でリストにおいて順序付けられる。ノードを順序付ける例として、ｄ［ｕ］，＋＝，＋，ｃ［ｘ］，*，ｘ（ｔ−５），ａ［ｖ］，ｂ［ｗ］，ｖ［ｔ］およびｗ［ｔ］が挙げられる。これはメインフローにおいてファンクションcreateNodelist（SG）が実行されるところである。
【００８０】
次にファンクションparseHW（architecture_description）がハードウェアをファンクションにより記述するグラフを創造する。ハードウェアグラフは前述のアーキテクチャの記述にしたがう。いくつかのハードウェアノードはＩ／Ｏ、メモリ、ファンクショナルユニット、アドレス累算器、コンフィギュレーションコンスタント、タイミングユニットノード等のＳＧノードにマップする。他のハードウェアノードはＳＧにおけるノードとまったく対応していないがメモリポート、クロスバー乗算器、ファンクショナルユニットポート等へのシグナルの発送に有用である。システムアウトプットおよびメモリインプットから複数レベルのファンクションユニットを通過してシステムインプットおよびメモリアウトプットに至るまでの経路の選択は書くコンフィギュレーションに対するデータを構成する。コンフィギュレーションの数と同じ回数にわたるハードウェアグラフの展開はＳＧがマップされるところの完全なハードウェアグラフＨＧをわれわれにもたらす。
【００８１】
次の段階はＳＧにおけるノードをＨＧにおけるノードにマップすることである。再起呼び出しマップ過程は次のように略説される。
bool map (node, SG, HG){
descendantHwNodes =
getHwNodes(node.getDescendants(), HG);
candidateHwNodes =
descendantHwNodes.getHwCommonAscendants(HG);
if (candidateHwNodes == null)
return(false);
foreach hwNode in candidateHwNodes {
if (hwNode.type != node.type)
next;
if(hwNode.isUsed())
next;
hwNode.route(descendantHwNodes, HG);
if(node.next == null)
return(true);
if((map(node.next, SG, HG))
return(true);
hwNode.unroute(descendentHwNodes, HG);
}
return false;
}
【００８２】
前記擬似コードにしたがってＳＧノードをＨＧノードにマッピングする際における最初の事項はグラフのノードのすぐ次のノードを取得することである。アルゴリズムがグラフシンクからグラフソースに進行するのでこれらのノードはすでにＨＧノードにマップされている。次のＨＧノードから作業は、ＳＧに対応する通常のすぐ先のＨＧノードのリストを計算し、未使用の乗算器により到達されうる。これは質問されているノードにマップされうる、可能性があるＨＧノードのリストである。このリストにおけるノードは適切な候補を見つけるために検索される。第１に候補ＨＧノードは加算器、乗算器、メモリ等のノードと同じタイプでなくてはならない。第２にノードは使用されていてはならない。これらのテストのうち一方が満たされていない場合、処理は失敗となる。これらのチェックが実行されると、ＨＧノードはその次のＨＧノードに伝送される。すなわち、次のＨＧノードのインプット乗算器が当該ノードを受け取るように設定される。もしこれがマップ対象となる最期のノードである場合、処理は成功となる。そうでない場合、マップ処理はＳＧの次のノードに反復的に適用される。もし成功すれば処理は成功となる。そうでない場合、これは次のノードのマッピングが現在または先のノードの現在のマッピングにより達成されなかったことを意味する。この場合、次のノードへの伝送は行われず次の候補ＨＧノードが試行される。すべての候補ノードへの試行が失敗した後、処理は失敗となる。
【００８３】
本発明により創出されたリコンフィギュラブルある実験用コプロセッサの適用例は次に示される。例はＭＰＥＧ１層ＩＩＩ（ＭＰ３）のデコーダーアルゴリズムである。アルゴリズムは（１）従来型プロセッサおよび（２）実験用コプロセッサにより加速された同一の従来型コプロセッサにおいて実行された。プロセッサは３２ビットで０．８１ＤＭＰＴＳの演算能力を有するハーバードアーキテクチャである。実験用コプロセッサは２つのネステッドループ、３２ビットデータ経路、２つの加算器および累算器、２つの乗算器および切替器、４キロバイトのＲＯＭおよび８キロバイトのＲＡＭをまとめた３つのデュアルポートメモリブロックにより生成された。
【００８４】
ＭＰ３のベンチマークのセットの実行から得られた実験結果が表１に示されている。従来型プロセッサにおけるアルゴリズムの最初のプロファイリングから、われわれは２つの過程（多相合成および逆改良型離散コサイン変換（ＩＭＤＣＴ））が時間の９５％を費やすことを発見した。このため、コプロセッサにおいて当該過程を加速した場合、加速に対するポテンシャルは２０である。多相合成過程は平均で１８．７倍加速された。ＩＭＤＴＣ過程は平均で４３．９倍加速された。これはアルゴリズムを全体的に１１．９倍加速する。プロセッサおよびコプロセッサにより形成された完全なシステムのプロファイリングは主要な処理に対する演算処理負荷配分のバランスに優れている。完全なシステムにおいて多層合成およびＩＭＤＴＳ過程は、加速前の演算処理負荷が９５％であるのに対して演算処理負荷が３４％であった。
【００８５】
【表１】
【００８６】
本実施例ではコプロセッサインスタンスの追加の結果としてシリコンエリアは２倍になった。演算処理能力は１２倍に上昇し、このことはプロセッサ−コプロセッサシステムが演算処理能力を同じレベルに維持しながら、おおよそ６倍もの消費電力が節約されたことを意味する。
【００８７】
前記リコンフィギュラブルコプロセッサアーキテクチャテンプレートが単に本発明の原則を記述しているにしか過ぎないことはいうまでもない。前記アーキテクチャの変更または改良は本発明の原則から外れない範囲で可能である。すべての変更または改良は本発明の本発明の技術的範囲に属し、特許請求の範囲により保護されなくてはならない。
【図面の簡単な説明】
【００８８】
【図１】プログラマブルマルチプレクサ
【図２】コプロセッサアーキテクチャテンプレートの上面図
【図３】アドレス生成ユニットのアーキテクチャ
【図４】タイミングユニットマトリックス
【図５】ディレイユニット
【図６】基礎累算器ユニット
【図７】複合累算器ユニット
【図８】許可クロスバーにおける許可および再開イネイブルシグナル累算器の選択
【図９】インプットクロスバーにおける各許可ユニット用のスタート、インクリメントおよびオフセットシグナルの選択
【図１０】アウトプットクロスバーにおける累算器カウントシグナルからのメモリポートアドレスの選択
【図１１】機能ユニット用のシグナルの選択
【図１２】システムアウトプットおよびメモリインプットの選択
【図１３】制御コンフィギュレーション、データインおよびデータアウトインターフェース
【図１４】制御レジスタ
【図１５】ステータスレジスタ
【図１６】制御回路
【図１７】機能ユニットから発せられたブレーク状態の選択
【図１８】Ｉ／Ｏ依存ユニットの許可の選択
【図１９】コプロセッサプログラミングフロー
【図２０】データフローグラフの一例
【図２１】アドレスフローグラフの一例
【技術分野】
【０００１】
本発明は、コンピュータアーキテクチャに関し、特に、アルゴリズムにおけるネステッドループの加速に関する。
【背景技術】
【０００２】
計算機器はユビキタスになり、携帯電話、パーソナルディジタル機器および携帯型オーディオプレイヤーなど多くの電子機器が人々により日常生活において持ち運ばれる製品となっている。
【０００３】
これらの製品はフォンノイマンのアーキテクチャとして知られているコンピューティングパラダイムにしたがう内蔵プロセッサにより実現されてきた。内蔵機器が複雑になればなるほどより速いクロック周波数を必要とし、かつ、より多くのパワーを消費するようになってきた。これは従来型プロセッサが指示を連続的に実行し、かつ、データを連続的に取り出すからである。バッテリを電源とする機器についてフォンノイマンコンピューティングパラダイムは維持されえず、代わりになるものが見出されなくてはならない。
【０００４】
最近、より平行なアーキテクチャへの大きな関心が、マルチメディアおよびコミュニケーションアルゴリズムの強い計算ニーズに向けられている。アプリケーション専用集積回路（ＡＳＩＣｓ）が、アルゴリズムの重要部分において並行に実行される処理の数を増加させるのに用いられており、クロック周波数の増大を回避し、その結果としてエネルギー消費を実用的な限度内に維持している。しかし、ＡＳＩＣｓは開発時間が長く、一度組み立てられると変更されえない。これでは非常に速く変化するマーケットの動きおよび最近の電子機器の短いライフ期間には合致しえない。
【０００５】
プログラマブル手法は実際にはより理想的であり、これがテクノロジーおよびリコンフィギュラブルコンピューティングが実現された経緯である。リコンフィギュラブルコンピュータはコンフィギュレーションメモリのコンテンツを変更することにより、ポストシリコン時においてアーキテクチャが変更されうるマシーンである。リコンフィギュラブルコンピュータの不可欠な要素はプログラマブルマルチプレクサである（図１）。プログラマブルマルチプレクサはインプットＡおよびＢと、アウトプットＣと、Ｓビットのコンフィギュレーションとを有する。Ｓが０に設定された場合、ＡからＣへの経路が生成される。Ｓが１に設定された場合、ＢからＣへの経路が生成される。プログラマブルマルチプレクサを十分に保有することにより、異なるアルゴリズムをより適当に実行するために異なるハードウェアアーキテクチャを迅速に生成するように、機能ユニットおよびメモリ要素を思い通りに接続させることができる。本発明はリコンフィギュラブルアーキテクチャのクラスを得るためのテンプレートである。
【０００６】
存在するリコンフィギュラブルアーキテクチャは（１）ファイングレインアレイおよび（２）コースグレインアレイの２つに分類される。
【０００７】
ファイングレインアレイはフィールドプログラマブルゲートアレイ（ＦＰＧＡｓ）の形成における広く拡散したポピュラリティを獲得した。ＦＰＧＡはプログラマブルスイッチの大きなネットワークにより接続された狭いビットスライスに対して論理機能を実行する小さなプログラマブル機能ユニットの大きなアレイである。機能ユニットは本質的にプログラマブルルックアップテーブル（ＬＵＴｓ）であり、スイッチのネットワークは前述のプログラマブルマルチプレクサからなる。商業的なＦＰＧＡ機器はさまざまなメーカーにより製品化されている。ＦＰＧＡｓは電子プログラミングにより要求される回路の生成を許容するにもかかわらず、ＬＵＴｓの豊富なアレイおよびルーティングスイッチは巨大なエリアおよびパワーの不利益を表わしている。専念ハードウェアにおいて実施されている同じ回路におけるエネルギー欠乏は非常に小さくかつ少なくなる。したがって、バッテリ運転機器におけるＦＰＧＡｓの使用はルールというよりもむしろ排除されてきた。
【０００８】
ＦＰＧＡｓは、必要とされる巨大回路エリアを軽減しかつパフォーマンスを改善するため、標準的なプロセッサ、ならびに、マルチプライヤおよび設置されているＲＡＭｓのような特定ブロックに結合されている。このように、アルゴリズムの特定および重要部分の多くがリコンフィギュラブルファブリックに対して実行され、その一方、その他のわずかな重要部分がプロセッサにより実行される。このようなハイブリッドアーキテクチャの例が研究者により提案され（非特許文献４，１６，１１参照）、かつ、ＦＰＧＡの取引業者により市場に導入された。しかし、これらの回路はいまだシリコンエリアの意味で無駄が多く、かつ、クロック周波数およびコンフィギュレーション時間の意味で遅い。
【０００９】
コースグレインアレイは柔軟性および汎用性を犠牲にすることでファイングレインアレイの前記のような制限を克服する。コースグレインアレイは最近の研究対象とされ、きわめてわずかのアーキテクチャが研究者により提案され（非特許文献３，６，１２，５，７，８，１０，９，１３，２，１４，１７参照）、かつ、会社が設立された（非特許文献１８，１９参照）。これらのアレイは高いグラニュラリティの機能ユニットおよび少ない複合接続ネットワークを有し、マルチメディアおよびコミュニケーションのような目標とするＤＳＰアプリケーションを改善する。機能ユニットは通常は２〜３バイトのスライスよりもむしろ２〜３バイトで計算および論理処理を実行する。結果は汎用的ではないもののわずかなコンフィギュレーションデータを必要とする非常にコンパクトかつ高速のリコンフィギュラブルシステムとなり、このシステムは実行時間において機敏かつ部分的に交換されうる。
【００１０】
他の重要な視点はリコンフィギュラブルユニットがどのように内蔵マイクロプロセッサに接続されているかということである。当初、再構築はプロセッサファンクショナルユニットレベルで始まり、かつ、特別な指示により誘起された（非特許文献１５，１２，１参照）。その後、リコンフィギュラブルユニットはプロセッサに緊密に接続されたコプロセッサになり、かつ、動作するためになおも特別な指示を必要とする（非特許文献４，１６，３，６，１２参照）。より最近では、システムバスに取り付けられ、かつ、ホストプロセッサ指示セットの延長を必要としないコプロセッサが主要な研究対象となってきている（非特許文献２，７，１７参照）。われわれの仕事は最後のカテゴリに合致している。
【非特許文献１】Katherine Compton, Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002.
【非特許文献２】A. Abnous, "Low-Power Domain-Specific Processors for Digital Signal Processing," PhD thesis, Dept. of EECS, UC Berkeley, CA, USA, 2001.
【非特許文献３】T. Miyamori, K. Olukotun, "REMARC: Reconfigurable Multimedia Array Coprocessor," IEICE Trans. on Information and Systems, vol. E82-D, No. 2, February 1999, pp. 389-397.
【非特許文献４】John Reid Hauser , John Wawrzynek, Augmenting a microprocessor with reconfigurable hardware, 2000.
【非特許文献５】Seth Copen Goldstein, Herman Schmit, Matthew Moe, Mihai Budiu, Srihari Cadambi, R. Reed Taylor, Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia.
【非特許文献６】Hartej Singh, Ming-Hau Lee, Guangming Lu, Nader Bagherzadeh, Fadi J. Kurdahi, Eliseu M. Chaves Filho, MorphoSys: An Integrated Reconfigurable System for Data-Parallel and Computation-Intensive Applications, IEEE Transactions on Computers, v.49 n.5, p.465-481, May 2000.
【非特許文献７】Ahmad Alsolaim , Janusz Starzyk , Jurgen Becker , Manfred Glesner, Architecture and Application of a Dynamically Reconfigurable Hardware Array for Future Mobile Communication Systems, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.205, April 17-19, 2000.
【非特許文献８】Reiner W. Hartenstein , Rainer Kress, A datapath synthesis system for the reconfigurable datapath architecture, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.77-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan.
【非特許文献９】Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997.
【非特許文献１０】E. Mirsky, A. DeHon, "MATRIX: A Reconfigurable Computing Architecture with Configurable Instruction Distribution and Deployable Resources," FCCM '96 - IEEE Symposium on FPGAs for Custom Computing Machines, Napa, CA, April 1996.
【非特許文献１１】Alan Marshall, Tony Stansfield , Igor Kostarnov, Jean Vuillemin, Brad Hutchings, A reconfigurable arithmetic array for multimedia applications, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.135-143, February 21-23, 1999, Monterey, California.
【非特許文献１２】R. D. Witting and P.Chow, OneChip: An FPGA processor with reconfigurable logic. In Proceedings of the IEEE Symposium on FPGAs for Cistom Computing Machines (FCCM’96), pages 126-135, 1996.
【非特許文献１３】J.M. Rabaey, “Reconfigurable Computing: The Solution to Low Power Programmable DSP”, Proceedings 1997 ICASSP Conference, Munich, April 1997.
【非特許文献１４】Ebeling, C., Cronquist, D., and Franklin, P. 1996 RaPID - Reconfigurable Pipelined Datapath. In the 6th International Workshop on Field-Programmable Logic and Applications.
【非特許文献１５】R. Razdan and M. D. Smith. High-performance microarchitectures with hardware-programmable functional units. In Proceedings of the IEEE/ACM International Symposium on Mircoarchitecture, pages 172-180, 1994.
【非特許文献１６】C. R. Rupp, M. Landguth, T. Garverick, E. Gomersall, H. Holt, J.M. Arnold, and M. Gokhale. The NAPAadapative processing architecture. In Porceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM’98), pages 28-37, 1998.
【非特許文献１７】Salvatore M. Carta, Danilo Pani, Luigi Raffo. Reconfigurable Coprocessor for Multimedia Application Domain, In Journal of VLSI Signal Processing 44, 135-152, 2006.
【非特許文献１８】CHAMELEON SYSTEMS, Inc. 2000. CS2000 Advance Product Specification. Chameleon Systens Inc., Sna Jose, CA.
【非特許文献１９】Pact XPP Technologies, “XPP-III Processor Overview (White Paper)”, July 2006.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
非特許文献２における仕事は、採用されるタイミングスキームの困難性をもたらし、標準的なセルを基礎とする技術に適用するには幾分非現実的なほどに完全にあつらえられたシリコンの完成を必要とするセルフタイム非同時データ駆動実行が存在する。アーキテクチャは、メモリアドレスの必要シーケンスを生成するためのマイクロコード指示を実行する２つのアドレス生成プロセッサにより特徴付けられている。
【００１２】
非特許文献７におけるアーキテクチャは、大半のマルチメディアおよびコミュニケーション分野で用いられている１６ビットまたは３２ビット言語にスケールを調節するのが困難なＬＵＴを基礎とするマルチプライヤを有する非区分の８ビットのファンクショナルユニットを用いる。階層的な接続スキームが編集の便宜を図るのに十分なだけ構築されている。しかし、この仕事は、さまざまなアプリケーションに採用かつスケール調節されうるアーキテクチャテンプレートというよりもむしろ１つのアーキテクチャの設計を表わしている。
【００１３】
われわれの仕事に最も近いのが非特許文献１７に開示されているものである。アーキテクチャテンプレートは内蔵メモリおよびアドレス生成モジュールのセットに接続されているコースグレインファンクショナルのアレイにより構成されている。アドレス生成モジュールは計算および論理ユニット（ＡＬＵｓ）と、複雑なアドレスシーケンスを生成するためのマルチプライヤとのシリーズを与える段階的カウンタにより実現されている。遅れラインのセットはファンクショナルユニットの制御およびメモリオペレーションと同期する。
【課題を解決するための手段】
【００１４】
われわれのアプローチにおいてアドレス生成ブロックはプラグラマブル累算器により実現され、ＡＬＵｓおよびマルチプライヤを用いる場合と比較してハードウェアの複雑さが低減されている。同期のために遅れラインを増やす代わりに、われわれは単一の遅れラインおよびプラグラマブル巻き時間を有する複数のカウンタを用いて、異なる遅れを伴うイネイブルシグナルのグループを生成する。この方法により、いくつかのアドレスの生成が他のアドレスの生成に対して相対的に遅らされ、アンバランスパイプライングラフにより表現されるループボディの実行が許可される。イネイブルシグナルは各ファンクショナルユニットを通じてデータシグナルに付属し、当該イネイブルシグナルは必要な遅れを伴って次のファンクショナルユニットに到着する。
【００１５】
われわれのアプローチはプログラミングツールのオペレーションの便宜を図るため、接続ネットワーク（部分クロスバー）を明快に構築する。実際、アーキテクチャテンプレートおよびプログラミングツールは、プログラミングが困難なまたは自動化しにくいハードウェア構造が生じるのを回避するために共同設計されてきた。
【００１６】
われわれは内蔵プロセッサのデータインプットおよびアウトプットである必要はないデータソースおよびデータシンクについても考察する。データの出所および宛先はシステムにおけるハードウェアのあらゆる部分であり、システムクロックに同期する必要はない。当該目的のため、われわれはプロセッサバスよりも簡単なインターフェースを提供し、かつ、非同期ＦＩＦＯｓを用いて一のコアを異なるクロックスピードで動いている他のコアに接続する。
【００１７】
提案するテンプレートから得られるアーキテクチャは一般的なチップ上のシステム（ＳｏＣ）に集積されており、かつ、ボディがファンクショナルユニットアレイにおいて実行される演算処理の表現であるネステッドプログラムループを実行するリコンフィギュラブルコプロセッサにより構成されている。ファンクショナルユニットは当該表現において示される原子演算処理を実行することができなくてはならない。データアレイは一または複数のシステムインプットおよび内蔵メモリアレイからアクセスされる。処理データアレイはメモリアレイまたはシステムアウトプットに送り返される。
【００１８】
アーキテクチャは一の演算処理またはデータのアクセスのみが一度に実行されうる標準的なプロセッサにおける実行と比較してネステッドループの加速を可能とする。本発明は多くのアプリケーション、特にマルチメディアおよびコミュニケーションのようなディジタルシグナル処理を含むアプリケーションにおいて応用されうる。アーキテクチャは制御フローの実行に優れているフォンノイマン型のプロセッサとともに利用される。アーキテクチャは複雑なアドレスシーケンスを生成可能なアドレス生成ブロックにより特徴付けられている。コンフィギュレーションレジスタファイルはデータ経路およびアドレス生成ブロックをプログラミングするための情報を保存する。コンフィギュレーションレジスタファイルは上書き可能であるため、システムは部分的にかつ運転時間中に再構築されうる。
【００１９】
プログラムされた数の反復のためまたはファンクショナルユニットにおいて事前にプログラムされたいくつかの条件が満たされるまでアーキテクチャはループする。制御レジスタを用いて初期化が実行され、状態レジスタを用いて投票が可能であり、かつ、リクエストはリクエストシグナルの断定に役立つ。
【００２０】
データストリームインプット、アウトプット、内蔵メモリ、ファンクショナルユニットおよびコンフィギュレーションユニットの数に関してアーキテクチャのスケールが容易に調節される。
【００２１】
われわれは、提案するアーキテクチャテンプレートから得られる複数の一般的な目的のプロセッサおよび複数のコプロセッサをコンピュータシステムに課することをもくろんでいる。プロセッサおよびコプロセッサは同期して、または、非同期のファーストインファーストアウトメモリ（ＦＩＦＯｓ）を用いて接続され、全体として非同期であり局所的に同期したシステムを形成する。
【００２２】
各コプロセッサはオリジナルプロセッサコードにおけるネステッドルームのタグ付けおよび書き直しによりプログラムされている。プログラミングツールはオリジナルコードにおいてコプロセッサインプット／アウトプット作動および制御に置換されるネステッドループグループのそれぞれごとにコプロセッサコンフィギュレーションを演出する。
【００２３】
コプロセッサにおいて利用可能なハードウェアはハードウェアグラフとしてモデル化されている。ループボディにおける表現はデータフローグラフとしてモデル化されている。データフローグラフのソースノードはメモリアウトプットまたはシステムインプットであり、シンクノードはメモリインプットまたはシステムアウトプットである。アレイアドレスにおける表現はアドレスフローグラフとしてモデル化されている。アドレスフローグラフはメモリポートからアドレス生成ノードを通じてタイミングノードまでデータフローグラフを継続し、完全なシステムグラフを形成する。
【００２４】
アドレス生成用のタイミング情報はシステムグラフから抽出される。タイミング情報はデータに沿ってイネイブルシグナルの形で送信され、ファンクショナルユニットを同期させるのに用いられる。
【００２５】
システムグラフはデータフローおよびアドレスフローグラフをハードウェアグラフにマップする順序でシンクからソースに横断し、使用されたリソースはマークされる。該当するフローを実施するように配置されている異なるハードウェアリソースをもたらす複合的なプラグラマブル複合プレクサセレクションが存在する場合は常に次回に試行する対象が決定される。マッピングが不可能になったと判定された場合、最後のハードウェアマッピングは実施されない。代替的な判定がされた場合、ほかの判定が試行される。代替的な判定が無い場合、先の判定が実施されない。この過程はマッピングが解決されるまたはマッピングが不可能であることが証明されるまで継続する。この過程は消耗的かつ完全である。
【発明を実施するための最良の形態】
【００２６】
（Ａ）ネステッドループ
提案されるアーキテクチャテンプレートから得られるコプロセッサはｎビットデータ言語を操作することができる。われわれは次を区別する。（１）コンスタント：コンフィギュレーションレジスタファイルから読み取られたシングルデータ言語。（２）バリアブル：ファンクショナルユニットアウトプットから読み取られたシングルデータ言語。（３）アレイ：メモリから読み出されたデータ言語集合。
【００２７】
アーキテクチャは次のメタ言語定義にしたがって一または複数の連続するネステッドループグループを実行することができる。
【００２８】
{nested_loop_group}
//curled brackets indicates repetition
nested_loop_group ::=
//”::=” means definition
for(index=0; index<index_end; index++) \{
//index and index_end are integers
// ‘\’ is an escape character removing the meta meaning of // the next character
{nested_loop_group;}
{assignment_statement;}
{break_statement;}
\}
assignment_statement::=
(variable | array_element) = expression
//’|’ means exclusive or
array_element ::= array_name\[address_expression\]
address_expression ::=
(((address_expression | alpha) * index + (address_expression | beta)) % modulo) + offset
//alpha, beta, modulo and offset are integers
expression ::=
F({(expression | array | variable | constant)})
//where F is a function computed by some functional unit //given a list of inputs or arguments separated by blank
//spaces
break_statement ::= break( expression );
//causes execution to break if expression evaluates to non //zero
【００２９】
（Ｂ）アーキテクチャ
提案されたアーキテクチャテンプレートの最上位レベルの様子が図２に示されている。これは基本的にファンクショナルユニット（ＦＵｓ）のアレイおよび設置メモリ（ＥＭｓ）のアレイにより構成されている。
【００３０】
ＦＵｓにより処理されるデータはＥＭｓ、リードクロスバーによる他のＦＵｓのシステムインプットまたはアウトプットから供給される。各ＦＵは単一データアウトプットを創出し、そのほかに２次アウトプットとしてフラグを創出する。当該フラグはリードクロスバーにより、当該フラグが制御インプットとして使用される他のＦＵｓに発送される。ＦＵｓにより処理されるデータはライトクロスバーにより定義されたルートを用いてＥＭｓに書き戻される、または、システムアウトプットに送り出される。
【００３１】
メモリのアドレスはアドレス生成器から出てくる。メモリのバンド幅が本システムのパフォーマンスにとって重要であり、図２においてすべての設置メモリはデュアルポートメモリとして開示されている。シングルポートメモリも採用されうる。
【００３２】
コンフィギュレーションレジスタファイルは、プラグラマブルＦＵｓ、リードおよびライトクロスバー、ならびに、アドレス生成ブロックのコンフィギュレーションを定義するデータを含むレジスタを保持している。それはアドレスおよびデータの計算に用いられるコンスタントを保存する。コンフィギュレーションレジスタファイルは、制御および状態レジスタにアクセスするためのコンフィギュレーションインターフェースを通じてアクセスされる。コンフィギュレーションレジスタファイルはアドレス付与可能であり、システムは部分的に実行時間が再構築可能である。
【００３３】
アドレス生成ブロックは図３に示されている。そのアーキテクチャはアーキテクチャ自体の最上位レベルの様子に類似しており、言い換えるとリコンフィギュラブルプロセッサの内部の小さなリコンフィギュラブルプロセッサのようである。ＦＵアレイの代わりに累算器レイ（ＡＡ）があり、リードおよびライトクロスバーのそれぞれはインプットクロスバーおよびアウトプットクロスバーのそれぞれとして現れている。
【００３４】
ＡＡはタイミングユニットからのシグナルにより許可される特別の累算器の集合を含んでいる。累算器はアウトプットクロスバーによりメモリポートに発送されるアドレスを創作する。アウトプットクロスバーはあるメモリに保存されている、他のメモリのアドレスとして使用されるアドレスを発送する。これによりメモリスペースを犠牲にしてアドレスを生成することに顕著な柔軟性をもたらす。他の累算器はＡＡ自体にフィードバックされる中間値を創作する。インプットクロスバーは複合アドレスシーケンスを生成するために中間値をフィードバックさせ、コンフィギュレーションレジスタから累算器にコンスタントを発送する。
【００３５】
アドレスはネステッドループインデックスの機能である。タイミングユニットはＡＡを許可するシグナルのグループを生成する。イネイブルシグナルは許可クロスバーによりＡＡに伝送される。許可クロスバーはイネイブルシグナルをシステムインプットに発送して外部データのインプット許可を、頃合を見計らって行いかつ同期させる。累算器の許可は生成されたアドレスをそのメモリポートに同行させる。リードポートの場合、イネイブルシグナルはＦＵｓを通じてメモリから読み出されたデータに同行する。ＦＵｓにおいてイネイブルシグナルはデータと同じだけ遅れ、許可およびデータを同位相に維持する。
【００３６】
図３に示されている制御ブロックはユーザのコマンドに応答してコプロセッサを初期化し、始動し、かつ、投票する。ある状態がファンクショナルユニットにおいて検出された場合、または、システムインプットがデータ枯渇もしくはアウトプットが過剰になる場合、コプロセッサが失速して立ち往生する。
【００３７】
ループインデックスは前述のようにネステッドループシンタックスにおいてユニット繰上げにより進行する。各ネステッドループグループはタイミングユニットにおいて最終カウント値がプログラムされているカスケードカウンタを用いて実行されたインデックスのグループを用いる。
【００３８】
タイミングユニットが図４に示されている。第１行がループインデックスｉ，ｊおよびｋに対するイネイブルシグナルを実行するマトリックスにおいてプラグラマブルカウンタが接続されている。続く列はループインデックスの遅れ要素を創出する。最後の行は常にループインデックスの最も遅れた要素を含んでいる。第１カウンタはインデックスｉを表わし、クロックサイクルごとに繰り上げられる。カウンタが最終値に到達したとき、アウトプットシグナルを巻くとともに鼓動して次の外側のカウンタを１つだけ進める。最後のカウンタが終端に達したとき最も外側のループが終了しネステッドループグループが遂行される。優先エンコーダがカスケードカウンタにおいてプログラムされた０ではない最終カウント値から最も外側のループ（end_sel）を確認する。この情報はいずれのカウンタカラムが演算処理を終結させるとともに制御ブロックにおいて使用されるかを示している。
【００３９】
基本インデックスｉの許可をプラグラマブル値だけ遅延させる回路が図５に示されている。各フリップ・フロップＤは１サイクルだけｉ_ｅｎ（ｔ）を遅延させる。プラグラマブル乗算器は所望の遅れを選択する。破壊状態（下記参照）が存在する場合、フリップ・フロップを禁止するとともにアウトプット許可を遮蔽することにより遅れユニットの状態は凍結されている。Ｐ個のメモリポートがシステムに存在する場合、最多でＰ個の異なる遅延した許可が必要とされる。実際にはより少ない遅延した許可が実行される。
【００４０】
現実のアドレスは１つの繰り上げにより進まないので、図６および図７に示されている乗算器は前記のようにaddress_expressionによりあたえられる複合的なアドレスシーケンスを生成する責任を負う。
【００４１】
図６に示されている基礎累算ユニット（ＢＡＵ）はRESTART_ENシグナルが鼓動された後でSTARTインプットにより特定される値に初期化し、INCRインプットにより特定される値を累算する。累算器の現在および次回アウトプットのそれぞれはCNTおよびCNT_NXTシグナルにより与えられる。
【００４２】
図７に示されている複合累算ユニットは次の機能性をＢＡＵに加える。すなわち、コンフィギュレーションインプットMODULOにより特定されるモジューロにおいて実行される累算が実行され、OFFSETインプットシグナルにより特定される値に加えられる。
【００４３】
各累算器はタイミングユニットにおいて創造されたイネイブルシグナルグループにより駆動されｒｙ許可クロスバーからENシグナルおよびRESTART_ENシグナルを選択する。図８に示されているように第１の許可グループ（遅延したもの）が選択され、かつ、ENおよびEN_RESTARTに対するイネイブルシグナルが当該選択グループから選択される。同様の手法がシステムにおいて外部データの受け入れの承認に用いられるイネイブルシグナルを選択するために採用される。この方法において外部データのインプットが頃合を計られるとともに同期させられる。
【００４４】
図９はインプットクロスバーからの累算器インプットの選択を示している。START、OFFSETおよびINCRシグナルはコンフィギュレーションレジスタに保存されているコンスタント、または、他の累算器により生成されたCNTおよびCNT_NXTシグナルから選択される。
【００４５】
図１０はアウトプットクロスバーにおけるメモリポートアドレスの選択を示している。累算器により生成されたCNTシグナルまたはメモリから読み出されたデータが選択されてメモリポートのアドレスを形成する。累算器のENシグナルおよびRESTART_ENシグナルは生成されたアドレスをメモリポートにしたがわせる。メモリポートがリードポートである場合許可は読み出されたデータをファンクショナルユニットに同行させ、あるいは、読み出されたデータがアドレスとして使用される場合、許可はアウトプットクロスバーに戻るデータにしたがう。メモリポートがライトポートである場合、ENシグナルおよびRESTART_ENシグナルは無視される。
【００４６】
図１１はファンクショナルユニットに対するインプットのリードクロスバーを用いた選択を示している。インプットはシステムインプットもしくはメモリアウトプットポートまたは他のファンクショナルユニットのアウトプットからもたらされる。このアーキテクチャテンプレートはあらゆるファンクショナルユニットがイネイブルシグナルを次のファンクショナルユニットに通過させるとともに、当該イネイブルシグナルをファンクショナルユニットそれ自体と同じ数の潜伏サイクルだけ遅延させる責任がある特別インプットを有していなくてはならないことを考慮する。この方法においてイネイブルシグナルは当該イネイブルシグナルが参照するデータのそばに保存または維持される。ファンクショナルユニットは当該ファンクショナルユニットに関係するのをやめるインプットENシグナルを消失する一方でインプットRESTART_ENシグナルをアウトプットENシグナルに伝送するように構成されうる。この実行の有用性は後で明らかになる。
【００４７】
図１２はライトクロスバーにおけるシステムアウトプットおよびメモリインプットの選択を示している。これらはファンクショナルユニットアウトプットから選択される。許可はデータに同行するとともにメモリ書き込み許可またはアウトプット要求シグナルとして用いられる。
【００４８】
制御／コンフィギュレーション、データインおよびデータアウトインターフェースが図１３に示されている。
【００４９】
制御／コンフィギュレーションインターフェースは、それが選択されていることを示すとともに、内部レジスタの選択に用いられるAddressインプットベクトルを有効化するRequest_inインプットシグナルを有している。書き込み／読み出し停止シグナルは意図されたアクションを選択する。データはcrt_data_inポートに書き込まれ、かつ、crt_data_outポートから読み出される。Request_outシグナルは演算処理の終了またはある状態が検出されかつコプロセッサが停止された等のイベントにフラグを立てる。
【００５０】
インターフェースのデータはReq_inインプットシグナルベクトルを有している。各要素Req_in[i]はインターフェースｉのデータが選択されているとともにインプットしデータを有しているData_in[i]ベクトルを有効化することを示している。
【００５１】
Ack_in[i]シグナルはData_in[i]を読み出すリクエストReq_in[i]が受け容れられかつ実行されるところの中核駆動インターフェースＩを語るのに用いられる。Ack_in[i:シグナルはそれが許可クロスバーにより選択されるところのアドレス生成ブロックからもたらされる。
【００５２】
データアウトインターフェースはReq_outアウトプットシグナルベクトルを有している。各要素Req_out[i]はデータアウトインターフェースｉが選択されておりかつアウトプットデータを有するData_out[i]ベクトルを有効化していることを示している。このインターフェースにより送出されたデータが受容されたとき、承認シグナルAck_out[i]は外側から主張され、あるいは、データ損失を防止するためにコプロセッサが立ち往生させる。外側の観点から、最後のリクエストからデータを受容することが不可能であったのでなければAck_out[i]は常に主張される。
【００５３】
図１４はアーキテクチャに対する基礎制御レジスタを示している。これはコプロセッサを初期化するInitビット、コプロセッサを許可するEnビット、および、Request_outシグナルによりコプロセッサからの制御リクエストを許可するReq_enビットという３つのビットを含有している。
【００５４】
図１５は基礎状態レジスタを示している。これはコプロセッサの投票を許容する単一のBusyビットを含有している。
【００５５】
基礎制御ユニットは図１６に示されている。コプロセッサは制御ビットEnおよびI/O許可ビットが現出されているときは常に許可され、END(t)またはbreakシグナルが現出されないままにされるまで許可のままに維持する。当該シグナルが生じたときは常に、コプロセッサを停止するフリップ・フロップにロジックおいてロジック「１」が捕らえられる。許可されたコプロセッサは外側のループインデックスおよびすべての遅延した許可グループを順番に許可するシグナルi_en(t)により現出される最も内側のループインデックス活性を有している。
【００５６】
制御アウトプットリクエストが許可された場合（Req_en＝1である場合）、breakシグナルまたは最も遅延したEND(t-DP)が生じたときRequest_outシグナルは現出される。
【００５７】
END(t)シグナルおよびEND(t-DP)シグナルは最も外側のループのラップアラウンドシグナルである。乗算器は図４において説明されたend_selシグナルをi_en、j_enまたはk_enシグナル、遅延がないおよびDPサイクルだけ遅延したバージョンからインデックス許可を選択するのに用いられる。
【００５８】
ステータスレジスタのBusyシグナルは図１６に示されているように生成される。コプロセッサがi_en(t)アクティブにより許可されている場合、または、コプロセッサが演算処理を完了していない、すなわちEND(t-DP)またはbreakが現出していない場合は当該コプロセッサはビジーである。
【００５９】
Breakシグナルはディレイユニットにおけるループインデックス許可の生成を不可能にするために用いられる（図４）。これは基本的に登録され、反対の、かつ、１サイクル遅延したbreakシグナルのバージョンである。
【００６０】
ファンクショナルユニットからの遮断状態の選択が図１７に示されている。縮小／拡大可能な理由のため、各ファンクショナルｉユニットは単一の遮断状態シグナルcond_iのみを生成することができる。本質的にファンクショナルユニットｉはさまざまな理由のために遮断状態に火をつけるようにプログラムされている。しかし、外からはファンクショナルユニットごとに単一の遮断シグナルが存在するように見える。コンフィギュレーションビットcond_i_en_tellsは遮断状態cond_iが許可されたか否かを語る。
【００６１】
I/O依存システム許可の選択が図１８に示されている。ループボディ表現がシステムインプットｉを含む状況で、そのインプットにおいて有効な、Req_in_iシグナルによりシグナル化されるデータが存在する場合にはコプロセッサは許可されうるのみである。同様に、ループボディ表現の結果がシステムアウトプットｊに送られる状況で、Ack_out_jシグナルによりシグナル化される送出データが実際に他のシステムにより読み出された場合、コプロセッサは許可されうるのみである。このシグナルが現出したとき、それは前回サイクルにおいて送られたシグナルが読み出されたことを意味している。現出のとき、コンフィギュレーションビットno_in_iおよびno_out_jはシステムインプットｉおよびシステムアウトプットｊがループボディ表現に存在しないことを示しており、したがってシステムを停止することはできない。
（Ｃ）プログラミングツール
コプロセッサプログラミングフローが図１９に示されている。ユーザがネステッドループシーケンスコードを前記のシンタックスにしたがって書くことにより始まる。コプロセッサプログラミングツールはネステッドループ試験すコードおよびハードウェアアーキテクチャの記述をインプットし、コプロセッサコンフィギュレーションをテキストファイル、ファイルを有するソフトウェアおよびハードウェア記述言語（ＨＤＬ）におけるコンフィギュレーションメモリイメージといった複合フォーマットでアウトプットする。テキストファイルは人間が視覚を通じて読むことが可能であり、ユーザにフィードバックを与えるために使用される。ソフトウェアはコプロセッサを成形かつ動作するいくつかのプログラムに含まれうるシーケンスのコンフィギュレーションメモリイメージを含むファイルを有する。ＨＤＬコンフィギュレーションイメージはシステム高速変化のためのＦＰＧＡエミュレーション、または、システム詳細評価のためのＨＤＬシミュレーションにおいて使用される。さらに、アーキテクチャのソフトウェアモデルはＦＰＧＡエミュレーションのスピードおよびＨＤＬシミュレーションの詳細度を和解させるハードウェア記述ファイルからコンパイルされる。ソフトウェアにより創作された結果（アウトプットデータ）、ＨＤＬおよびＦＰＧＡモデルはユーザにより解析され、インプットネステッドループコードの改良の案内に用いられる。
【００６２】
ハードウェアアーキテクチャは使用されたファンクショナルユニットを参考するファイルにおいて記述されている。ファンクショナルユニットの記述はファンクショナルユニットストアに置かれる。ハードウェア記述ファイルのシンタックスは次に示されるものと等価である。
【００６３】
//Constant declaration section
{({constant_name})}
//Input/output declaration section
{input input_name\[range\]}
{output output_name\[range\]}
range ::= integer..0
/Memory declaration section
{memory memory_name (singleport | twoport | dualport)
addrA\[range\] dataA\[range\]
[addrB\[range\] dataB\[rage\]]}
//Functional unit declaration section
{functional_unit functional_unit_name functional_unit_type}
//Read Crossbar declaration section
{functional_unit_name.input_name <=
({functional_unit_name.output_name}) ({memory_name.(dataA | dataB)})
({constant_name})
//Write Crossbar declaration section
{output_name <= ({functional_unit_name.output_name})}
{memory_name.(data | dataB) <=
({functional_unit_name.output_name})}
//Address Generator declaration section
//Timing Unit
number_of_nested_loops := integer
number_of_enable_delay_groups := integer
//enable groups become named en_grp_0, en_grp_1, …, up to //en_grp_number_of_enable_delay_groups-1
//enabled signals in enable group I become named //en_grp_i.en_0, en_grp_i.en_0, …, up to
//en_grp_i.en_number_of_nested_loops-1
//Accumulators declaration section
number_of_baus := integer
number_of_caus := integer
//accumulators become named bau_0, bau_1, …, up to //bau_number_of_baus-1 or cau_0, cau_1, …, up to //cau_number_of_caus-1
//Enable Crossbar declaration section
{(bau | cau)_name.(en restart_en) <=
({en_grp_name.(en restart_en)})}
// Input Crossbar declaration section
{(bau | cau)_name.start <=
({bau_name.cnt_nxt} {constant_name})}
{(bau | cau)_name.incr <=
({bau_name.cnt} {constant_name})}
{cau_name.offset <= ({bau_name.cnt} {constant_name})}
// Output Crossbar declaration section
{memory_name.(addrA | addrB) <=
({cau_name.cnt} {memory_name.(data | dataB)})}
【００６４】
アーキテクチャ記述の一例は次のとおりである。
【００６５】
//Input/output declaration section
input I0[31..0]
output O0[31..0]
//Memory declaration section
memory M0 dualport
addrA[511..0],dataA[31..0] addrB[511..0] dataB[31..0]
memory M1 dualport
addrA[511..0] dataA[31..0] addrB[511..0] dataB[31..0]
memory M2 dualport
addrA[511..0] dataA[31..0] addrB[511..0] dataB[31..0]
//Functional unit declaration section
functional_unit ADD1 adder_32
functional_unit ADD2 adder_32
functional_unit MULT1 mult_32
functional_unit MULT2 mult_32
functional unit MUX mux_2_1_32
//Read Crossbar declaration section
ADD1.d_input0 <= (I0 M0.dataA M1.dataA MULT1.d_output)
ADD2.d_input1 <= (I0 M0.dataB const_rd MULT2.d_output)
MUX.s_input <= (ADD1.zero_flag ADD2.zero_flag)
MUX.d_input0 <= (MULT1.d_output M2.dataA)
MUX.d_input1 <= (MULT2.d_output M2.dataB)
//… and so on for other FUs
//Write Crossbar declaration section
O0 <= (ADD1.d_output MULT1.d_output)
M0.dataB <= (ADD1.d_output MULT1.d_output)
M1.dataB <= (ADD2.d_output MULT2.d_output)
//… and so on for other memory ports
//Address Generator declaration section
//Timing Unit
number_of_nested_loops := 3
number_of_enable_delay_groups := 3
//Accumulators declaration section
number_of_baus := 4
number_of_caus := 2
//Enable Crossbar declaration section
cau_0.(en restart_en) <= (en_grp_0.en_0 en_grp_1.en_1)
//… same for other baus and caus
bau_0.(en restart) <= (en_grp_1.en_1 en_grp_2.en_2)
//… same for other baus and caus
// Input Crossbar declaration section
bau_1.start <= (bau_2.cnt_nxt const_addr)
bau_1.incr <= (const_addr_incr bau_2.cnt)
cau_2.offset <= (const_addr_offset bau_3.cnt)
//… same for other baus and caus
// Output Crossbar declaration section
M0.addrA <= (cau_3.cnt cau_0.cnt M2.dataB)
//… same for other memories
【００６６】
コンフィギュレーション記述テキストファイルはアーキテクチャ記述ファイルに類似するシンタックスにより書かれるが、目的のためのすべての可能性があるソースの競争の代わりに指定ソースを特定する。言い換えると、それは排他的な分離の競争の代わりに用いられる。可能性があるシンタックスの記述は次のとおりである。
【００６７】
{config_sequence}
config_sequence ::=
label: config_sequence begin {configuration} end
configuration ::=
configuration begin config_body end
config_body ::=
data_path_config addr_gen_config
data_path_config ::=
fu_config read_xbar_config write_xbar_config
fu_config ::=
{fu_name.parameter_name = parameter_value}
//parameter name and parameter value depend on the //functional unit being used
read_xbar_config ::=
{functional_unit_name.input_name <=
(input_name | functional_unit_name.output_name | memory_name.(dataA | dataB) | constant_name )}
write_xbar_config ::=
{memory_name.((dataA | dataB) write) <=
functional_unit_name.(output_name (out_en|out_restart_en))}
{output_name.(data_out req_out) <=
functional_unit_name.(output_name (out_en|out_restart_en))}
addr_gen_config ::=
tu_config acc_config enable_xbar_config input_xbar_config output_xbar_config
tu_config ::= end_array delay_array
end_array ::= ({integer})
//list must have number_of_nested_loops elements
delay_array ::= ({integer})
//list must have number_of_enable_delay_groups elements
acc_config ::=
cau_name.modulo = integer
enable_xbar_config ::=
{(bau | cau)_name.(en restart_en) <=
en_grp_name.(en_name en_name)}
input_xbar_config ::=
(bau | cau)_name.start <=
(constant_name | bau_name.cnt_nxt )
(bau | cau)_name.incr <=
(constant_name | (bau | cau)_name.cnt )
cau_name.offset <= (constant_name | (bau | cau)_name.cnt)
output_xbar:config ::=
memory_name.(addrA | addrB) <=
((bau | cau)_name.cnt | memory_name.(data | dataB))
【００６８】
コプロセッサプログラミングツールのアルゴリズムは次のように略述される。
【００６９】
coprocessorTool (nested_loop_sequence_code){
SG = parseNLSC(nested_loop_sequence_code);
nodeList = createNodelist(SG);
HG = parseHW(architecture_description)
if (map(nodeList.head, SG, HG) == true)
writeConfigurationImages();
exit(SUCCESSFUL);
else
exit(UNSUCCESSFUL;)
}
【００７０】
ここで第１段階はネステッドループボディにおける表現を解析し、各ネステッドループに対するサブグラフにより構成される完全なシステムグラフＳＧを創造することである。これはファンクションパーズＮＬＳＣ(nested_loop_sequence_code).により遂行される。各ネステッドループグループはコンフィギュレーションメモリイメージを引き起こす。各ネステッドループグループに対するサブグラフはデータフローグラフおよびアドレスフローグラフという２つの部分を有している。
【００７１】
データフローグラフ（ＤＦＧ）は次のようなタイプのノードを有している。
【００７２】
ソースノード：
・メモリノード（データアウトプットポート）
・システムデータインプットノード
・コンフィギュレーションコンスタントノード
シンクノード：
・メモリノード（データインプットポート）
・システムデータアウトプットノード
中間ノード：
・ファンクショナルユニットノード
アドレスフローグラフ（ＡＧＦ）は次のようなタイプのグラフを有している。
【００７３】
ソースノード：
・メモリノード（データアウトプットポート）
・タイミングユニットノード（イネイブルシグナルアウトプットポート）
・コンフィギュレーションコンスタントノード
シンクノード：
・メモリノード（アドレスインプットポート）
・システムデータインプットノード（承認シグナル）
中間ノード：
・累算器ユニットノード
ＤＦＧおよびＡＦＧの端部はソースノードから中間ノードに向けられ、中間ノードから他の中間ノードに向けられ、かつ、中間ノードからシンクノードに向けられる。
【００７４】
ＤＦＧおよびＡＦＧは、ＡＦＧのメモリシンクノードおよびＤＦＧのメモリソースノードを併合することにより単一のコンフィギュレーショングラフＣＧにまとめられうる。完全なシステムグラフＳＧは連続的なＣＧｓを連鎖することにより構築されうる。一のＣＧのメモリシンクノードおよび次のＣＧのメモリソースノードを併合することにより当該一のＣＧが当該他の
ＣＧに連鎖される。これにより次のコプロセッサコンフィギュレーションで使用されるデータを設置メモリに残しておくことが可能となる。このメカニズムは意識的なまたは意図的なキャッシングメカニズムと呼ばれうるものであり、統確率的な局所性を不当に使用する従来のキャッシュよりも優れたパフォーマンスを示す。
【００７５】
次の例はＣＧが得られるところのネステッドループグループを示す。
u = α0*(i-8)+β0
v=j
w = ((α1*i+β1)*j + β2)%γ)+δ
x = M2.dataA[j-5]
for(i=0; i<i_end; i++) {
for(j=0; j<j_end; j++)
d[u] += a[v]*b[w] + c[x];
}
【００７６】
本実施形態におけるネステッドループに対するＤＦＧが図２０に示されている。これから明らかなようにＤＦＧがネステッドループグループのボディにおける表現に追従している。グラフの各ノードはＦＵノードまたはメモリノードを表わしている。リード、ライトまたはＦＵの動作はパイプラインで連結され、各動作の潜伏が図２０に示されている。メモリ読み出しａ［ｖ］またはｂ［ｖ］からメモリ書き込みｄ［ｕ］に至るグラフにおける最長の経路は９サイクルにわたっている。メモリ読み出しｃ［ｘ］からメモリ書き込みｄ［ｕ］に至る経路は４サイクルにわたっている。これはメモリ読み出しｃ［ｘ］がメモリ読み出しａ［ｖ］およびｂ［ｖ］に対して９−４＝５サイクル遅れ、メモリ書き込みｄ［ｕ］はメモリ読み出しａ［ｖ］およびｂ［ｗ］に対して９−１＝８サイクル遅れることを意味している。このアーキテクチャテンプレートによればアドレスを計算する際に遅れは生じない。このような潜伏における相違は異なる数のパイプラインステージを伴うＦＵｓにのみ起因する。しかし、アドレスの計算が潜伏により影響を受けるような場合までこの手法の適用範囲はのびている。
【００７７】
アドレスｕ，ｖ，ｗおよびｘの計算に対するＡＦＧが図２１に示されている。アドレスの計算はタイミングユニットにより生成されたイネイブルシグナルｉ_ｅｎおよびｊ_ｅｎにより推進される。Ｄサイクルノードｕ（ｔ−８）だけ遅れる必要があるアドレスはシグナルｉ_ｅｎ（ｔ−Ｄ）およびｊ_ｅｎ（ｔ−Ｄ）を伴う遅れ許可グループを用いる。アドレスｕ，ｖおよびｘは１つのＢＡＵのみが計算される必要がある一方、アドレスｗはより複雑でありＢＡＵにより供給されるＣＡＵを必要とすることに注意されたい。
【００７８】
同音意義語メモリｕ（ｔ−８），ｖ（ｔ），ｗ（ｔ）およびｘ（ｔ−５）の併合によるＤＦＧおよびＡＦＧの連鎖は本実施形態におけるネステッドループグループに対するＣＧを生み出す。ネステッドループグループのシーケンスが存在していたとすると、各ＣＧｓは同様の方法により連鎖されて完全なＳＧを生み出したであろう。
【００７９】
創出されたＳＧを有すると、このグラフにおけるノードがシステムアウトプットノードからシステムインプットノードに向かって第１ファッションの幅でリストにおいて順序付けられる。ノードを順序付ける例として、ｄ［ｕ］，＋＝，＋，ｃ［ｘ］，*，ｘ（ｔ−５），ａ［ｖ］，ｂ［ｗ］，ｖ［ｔ］およびｗ［ｔ］が挙げられる。これはメインフローにおいてファンクションcreateNodelist（SG）が実行されるところである。
【００８０】
次にファンクションparseHW（architecture_description）がハードウェアをファンクションにより記述するグラフを創造する。ハードウェアグラフは前述のアーキテクチャの記述にしたがう。いくつかのハードウェアノードはＩ／Ｏ、メモリ、ファンクショナルユニット、アドレス累算器、コンフィギュレーションコンスタント、タイミングユニットノード等のＳＧノードにマップする。他のハードウェアノードはＳＧにおけるノードとまったく対応していないがメモリポート、クロスバー乗算器、ファンクショナルユニットポート等へのシグナルの発送に有用である。システムアウトプットおよびメモリインプットから複数レベルのファンクションユニットを通過してシステムインプットおよびメモリアウトプットに至るまでの経路の選択は書くコンフィギュレーションに対するデータを構成する。コンフィギュレーションの数と同じ回数にわたるハードウェアグラフの展開はＳＧがマップされるところの完全なハードウェアグラフＨＧをわれわれにもたらす。
【００８１】
次の段階はＳＧにおけるノードをＨＧにおけるノードにマップすることである。再起呼び出しマップ過程は次のように略説される。
bool map (node, SG, HG){
descendantHwNodes =
getHwNodes(node.getDescendants(), HG);
candidateHwNodes =
descendantHwNodes.getHwCommonAscendants(HG);
if (candidateHwNodes == null)
return(false);
foreach hwNode in candidateHwNodes {
if (hwNode.type != node.type)
next;
if(hwNode.isUsed())
next;
hwNode.route(descendantHwNodes, HG);
if(node.next == null)
return(true);
if((map(node.next, SG, HG))
return(true);
hwNode.unroute(descendentHwNodes, HG);
}
return false;
}
【００８２】
前記擬似コードにしたがってＳＧノードをＨＧノードにマッピングする際における最初の事項はグラフのノードのすぐ次のノードを取得することである。アルゴリズムがグラフシンクからグラフソースに進行するのでこれらのノードはすでにＨＧノードにマップされている。次のＨＧノードから作業は、ＳＧに対応する通常のすぐ先のＨＧノードのリストを計算し、未使用の乗算器により到達されうる。これは質問されているノードにマップされうる、可能性があるＨＧノードのリストである。このリストにおけるノードは適切な候補を見つけるために検索される。第１に候補ＨＧノードは加算器、乗算器、メモリ等のノードと同じタイプでなくてはならない。第２にノードは使用されていてはならない。これらのテストのうち一方が満たされていない場合、処理は失敗となる。これらのチェックが実行されると、ＨＧノードはその次のＨＧノードに伝送される。すなわち、次のＨＧノードのインプット乗算器が当該ノードを受け取るように設定される。もしこれがマップ対象となる最期のノードである場合、処理は成功となる。そうでない場合、マップ処理はＳＧの次のノードに反復的に適用される。もし成功すれば処理は成功となる。そうでない場合、これは次のノードのマッピングが現在または先のノードの現在のマッピングにより達成されなかったことを意味する。この場合、次のノードへの伝送は行われず次の候補ＨＧノードが試行される。すべての候補ノードへの試行が失敗した後、処理は失敗となる。
【００８３】
本発明により創出されたリコンフィギュラブルある実験用コプロセッサの適用例は次に示される。例はＭＰＥＧ１層ＩＩＩ（ＭＰ３）のデコーダーアルゴリズムである。アルゴリズムは（１）従来型プロセッサおよび（２）実験用コプロセッサにより加速された同一の従来型コプロセッサにおいて実行された。プロセッサは３２ビットで０．８１ＤＭＰＴＳの演算能力を有するハーバードアーキテクチャである。実験用コプロセッサは２つのネステッドループ、３２ビットデータ経路、２つの加算器および累算器、２つの乗算器および切替器、４キロバイトのＲＯＭおよび８キロバイトのＲＡＭをまとめた３つのデュアルポートメモリブロックにより生成された。
【００８４】
ＭＰ３のベンチマークのセットの実行から得られた実験結果が表１に示されている。従来型プロセッサにおけるアルゴリズムの最初のプロファイリングから、われわれは２つの過程（多相合成および逆改良型離散コサイン変換（ＩＭＤＣＴ））が時間の９５％を費やすことを発見した。このため、コプロセッサにおいて当該過程を加速した場合、加速に対するポテンシャルは２０である。多相合成過程は平均で１８．７倍加速された。ＩＭＤＴＣ過程は平均で４３．９倍加速された。これはアルゴリズムを全体的に１１．９倍加速する。プロセッサおよびコプロセッサにより形成された完全なシステムのプロファイリングは主要な処理に対する演算処理負荷配分のバランスに優れている。完全なシステムにおいて多層合成およびＩＭＤＴＳ過程は、加速前の演算処理負荷が９５％であるのに対して演算処理負荷が３４％であった。
【００８５】
【表１】
【００８６】
本実施例ではコプロセッサインスタンスの追加の結果としてシリコンエリアは２倍になった。演算処理能力は１２倍に上昇し、このことはプロセッサ−コプロセッサシステムが演算処理能力を同じレベルに維持しながら、おおよそ６倍もの消費電力が節約されたことを意味する。
【００８７】
前記リコンフィギュラブルコプロセッサアーキテクチャテンプレートが単に本発明の原則を記述しているにしか過ぎないことはいうまでもない。前記アーキテクチャの変更または改良は本発明の原則から外れない範囲で可能である。すべての変更または改良は本発明の本発明の技術的範囲に属し、特許請求の範囲により保護されなくてはならない。
【図面の簡単な説明】
【００８８】
【図１】プログラマブルマルチプレクサ
【図２】コプロセッサアーキテクチャテンプレートの上面図
【図３】アドレス生成ユニットのアーキテクチャ
【図４】タイミングユニットマトリックス
【図５】ディレイユニット
【図６】基礎累算器ユニット
【図７】複合累算器ユニット
【図８】許可クロスバーにおける許可および再開イネイブルシグナル累算器の選択
【図９】インプットクロスバーにおける各許可ユニット用のスタート、インクリメントおよびオフセットシグナルの選択
【図１０】アウトプットクロスバーにおける累算器カウントシグナルからのメモリポートアドレスの選択
【図１１】機能ユニット用のシグナルの選択
【図１２】システムアウトプットおよびメモリインプットの選択
【図１３】制御コンフィギュレーション、データインおよびデータアウトインターフェース
【図１４】制御レジスタ
【図１５】ステータスレジスタ
【図１６】制御回路
【図１７】機能ユニットから発せられたブレーク状態の選択
【図１８】Ｉ／Ｏ依存ユニットの許可の選択
【図１９】コプロセッサプログラミングフロー
【図２０】データフローグラフの一例
【図２１】アドレスフローグラフの一例
【特許請求の範囲】
【請求項１】
計算および論理オペレーションを含む表現のコンピューティングネステッドループ用のリコンフィギュラブルコプロセッサのアーキテクチャテンプレートであって、
アプリケーションドメインにしたがって選択されるリコンフィギュラブルファンクショナルユニットの、パイプラインの有無に無関係な不特コンスタントかつ不特定タイプのリニアアレイと、
中間データおよびアドレス計算法を保存する不特定数かつ不特定タイプの設置メモリのリニアアレイと、
前記設置メモリのアドレスの複合シーケンスを計算するリコンフィギュラブルアドレス生成ブロックと、
システムインプット、メモリデータアウトプットポートおよびプログラムされたコンスタントを前記ファンクショナルユニットインプットに接続するために前結合時において定義される部分的かつリコンフィギュラブルリードクロスバーと、
ファンクショナルユニットアウトプットをシステムアウトプットまたはメモリデータインプットポートを接続するために前合成時において定義される部分的かつリコンフィギュラブル書き込みクロスバーと、
制御、ステータスおよびコンフィギュレーションレジストリを有するレジスタファイルとを備え、前記コンフィギュレーションレジスタはリコンフィギュラブルファンクショナルユニット、リコンフィギュラブルアドレス生成ブロック、部分的かつリコンフィギュラブルコネクションクロスバーのコンフィギュレーションを保存し、前記データおよびアドレス計算法に用いられるコンスタントを保存することを特徴とするアーキテクチャテンプレート。
【請求項２】
請求項１記載のアーキテクチャテンプレートにおいて、前記リコンフィギュラブルアドレス生成ブロックが、
アドレス生成を開始、停止および再開することにより、前記コプロセッサに実行を開始、停止および再開させる制御ユニットと、
設置メモリに格納されているインデックスアレイへのアドレスを適時生成するため、前記ファンクショナルユニットの機能を適時活性化するため、および、システムインプットおよびメモリ書き込みを適時要求するために用いられるイネイブルシグナルを生成するプラグラマブルタイミングユニットと、
複合アドレスシーケンスを生成するために接続されているプラグラマブルアキュムレータのリニアアレイと、
前記イネイブルシグナルを前記アレイにおける前記アキュムレータに接続し、かつ、前記システムインプットにおける外部データの読み取りを認める前複合時に定義される部分的かつリコンフィギュラブルイネイブルクロスバーと、
前結合時に定義され、アキュムレータアウトプットおよびコンフィギュレーションコンスタントを他のアキュムレータインプットに接続する部分的かつリコンフィギュラブルインプットクロスバーと、
前複合時に定義され、生成アドレスを形成するアキュムレータアウトプットおよび各イネイブルシグナルをメモリアドレスに接続する部分的かつリコンフィギュラブルアウトプットクロスバーと、
アドレスがメモリに格納されている場合、アドレスポートを格納するルーティングメモリデータポートとを備えていることを特徴とするアーキテクチャテンプレート。
【請求項３】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、前記プログラミングユニットが、
各ロウが周期において同じ遅れと、コプロセッサが実行可能なネステッドループの最大数を表わすコラムの数とを有することにより特徴付けられているイネイブルシグナルのグループを生成し、一のコラムにおけるすべてのカウンタが同じエンドリミットでプログラムされ、制御される前記ループの反復回数を決定するプラグラマブルカウンタのマトリクスと、
前記プログラムされたコラムの前記数を用いて所定のコンフィギュレーションにネステッドループの実際の数を決定するエンコーダと、
全体的な前記イネイブルシグナルを所定の最大遅れ以下で遅らせ、前記遅れがないイネイブルおよび現在のコンフィギュレーションにおける、前記アーキテクチャにおける最大許容遅れと相違しうる前記最大遅れを有する各イネイブルグループに対してプログラムされている遅れをもってアウトプットイネイブルシグナルを遅らせるディレイユニットとを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項４】
請求項３記載のプラグラマブルタイミングユニットにおいて、
前記プラグラマブルカウンタのマトリクスにより生成された前記イネイブルシグナルがデータストリームをお互いに遅らせ、かつ、ファンクショナルユニットにより異なる遅れをもって導入された前記データフローグラフにおける異なる潜在を補償させるのに用いられ、
前記プラグラマブルタイミングユニットが、データがインプットまたは格納されてから読み出されるまでの時間を計測し、イネイブルおよびデータが同等に遅れているファンクショナルユニットを通じて前記データを同行させ、データの書き込みからアウトプットまたは格納までの時間を計測することを特徴とするプラグラマブルタイミングユニット。
【請求項５】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記プラグラマブルアキュムレータが、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記インプットクロスバーを前記アキュムレータの開始値を定めるインプットシグナルと、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記アキュムレータのインクリメント値を定めるインプットシグナルと、
前記アキュムレータの動作を可能とするイネイブルシグナルと、
前記開始値をリロードする再開イネイブルシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる前記アキュムレータのオフセット値を定めるインプットシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、前記アキュムレータのモジューロ値を定めるコンフィギュレーションレジスタと、
他のアキュムレータの前記生成アドレスまたは前記インプットとして用いられるアウトプット計算値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項６】
請求項１記載のアーキテクチャテンプレートにおいて、
前記コンフィギュレーション、ステータス／制御レジスタファイルが、
アドレスが付されうる、ランタイムにおけるファイングラニュラリティの部分的なレコンフィギュレーションを可能とするリード／ライトメモリがマップされたインターフェースと、
外部アシスタンスを案内または依頼するアウトプットリクエストシグナルとを有することを特徴とするアーキテクチャテンプレート。
【請求項７】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ファンクショナルユニットアレイに属する各ファンクショナルユニットが前記コプロセッサを停止させうるブレークシグナルを発することを特徴とするアーキテクチャテンプレート。
【請求項８】
請求項１記載のアーキテクチャテンプレートにおいて、
前記複合システムインプットはスレーブリクエスト／アクノリッジインターフェースであり、かつ、前記複合システムアウトプットはマスターリクエスト／アクノリッジインターフェースであることを特徴とするアーキテクチャテンプレート。
【請求項９】
請求項８記載のアーキテクチャテンプレートにおいて、
システムインプットリクエストまたはシステムアウトプットアクノリッジの欠落が、システムインプットからのデータ読み出しおよびシステムアウトプットへのデータ書き込みのうち一方または両方のために前記表現が実行される場合、コプロセッサを始動させることを特徴とするアーキテクチャテンプレート。
【請求項１０】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記制御ユニットが前記コプロセッサを機能化かつ非機能化し、最も外側のループインデックスがラップアラウンドしたときに終了し、前記コプロセッサのインプットデータ欠乏、アウトプットデータ過剰、または、ファンクショナルユニットが火をつける一もしくは複数の遮断状態を停止することを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１１】
請求項１記載のコプロセッサプログラミングツールにおいて、
前記コプロセッサの前記アーキテクチャ記述のコンパイラと、
慣用プロセッサ用のオリジナルプログラムにおいてタグが付されかつ上書きされ、かつ、慣用プログラミング言語のシンタックスに本質的に類似するシンタックスを用いる前記ネステッドループシーケンス用のパーサーと、
ネステッドループシーケンスのコード用の、前記コードを前記コプロセッサの特定コンフィギュレーションに変換するコンパイラとを有するコプロセッサプログラミングツールを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項１２】
請求項１記載のアーキテクチャ記述ファイルにおいて、
リコンフィギュラブルファンクショナルユニットの数およびタイプの記述と、
数、タイプ、データおよびアドレスの設置メモリの幅と、
リコンフィギュラブルアドレス生成ブロックの記述と、
リコンフィギュラブルリード／ライトクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１３】
請求項１２記載のアーキテクチャ記述ファイルにおいて、
プラグラマブルタイミングユニットブロックの記述と、
プラグラマブルアキュムレータの数およびタイプの記述と、
リコンフィギュラブルイネイブル、インプットおよびアウトプットクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１４】
請求項１３記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブルタイミングユニットの記述が、
グループに属するネステッドループの数の記述と、
生成されるイネイブルシグナルの異なる遅延バージョンの数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１５】
請求項１２記載のアーキテクチャ記述ファイルのコンフィギュレーション記述ファイルが、
ファンクショナルユニットのコンフィギュレーションのパラメータ／値による記述と、
前記設置メモリのコンフィギュレーションと、
アドレス生成ブロックのリコンフィギュラブルコンフィギュレーションの記述と、
読み取り／書き込みクロスバーのリコンフィギュラブルコンフィギュレーションの、ポートがファンクショナルユニットのインプットおよびアウトプットのうちいずれかに接続されていることから暗黙的に推察される読み取りまたは書き込みモードによる記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１６】
請求項１５記載のコンフィギュレーション記述ファイルにおいて、前記コンフィギュレーション記述ファイルにおける前記リコンフィギュラブルアドレス生成ブロックの前記コンフィギュレーションの前記記述が、
前記プラグラマブルタイミングユニットブロックのコンフィギュレーションの記述と、
各プラグラマブル累算器のコンフィギュレーションの記述と、
イネイブル、インプットおよびアウトプットクロスバーのコンフィギュレーションの記述とを備えていることを特徴とするコンフィギュレーション記述ファイル。
【請求項１７】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、前記プラグラマブルタイミングユニットコンフィギュレーションの記述が、
各ネステッドループの終端の記述と、
各機能化シグナルグループについて遅延サイクル数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１８】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブル計算機の記述が、
コンフィギュレーションコンスタントに接続された場合における開始および繰り上げ値と、
前記累算器が複合累算器ユニットであり、オフセットインプットがコンフィギュレーションに接続されている場合におけるオフセット値と、
前記累算器が複合累算器ユニットである場合におけるモジューロ値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１９】
請求項１１記載のコプロセッサプログラミングツールにおいて、
ネステッドループボディにおける計算および論理表現を解剖して完全なシステムグラフを得るファンクションと、
アーキテクチャを順番に表現するアーキテクチャを表わすハードウェアにマップされるシステムグラフのノードの当該順番のリスト生成するファンクションと、
請求項１３記載の前記アーキテクチャ記述ファイルを解剖するとともにハードウェアグラフを創出するファンクションと、
前記システムグラフの各ノードを反復的に前記ハードウェアグラフのノードにマップするファンクションとを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項２０】
請求項１９記載のコプロセッサプログラミングツールにおいて、
前記システムグラフがコンフィギュレーションサブグラフのシーケンスを備え、各コンフィギュレーショングラフがネステッドグループに対応していることを特徴とするコプロセッサプログラミングツール。
【請求項２１】
請求項２０記載のシステムグラフにおいて、
各コンフィギュレーションサブグラフが、データフローサブグラフと、アドレスフローサブグラフとを備えていることを特徴とするシステムグラフ。
【請求項２２】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記データフローサブグラフが、
メモリノード（データアウトプットポート）、システムデータインプットノードおよびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（データインプットポート）およびシステムデータアウトプットノードを含むシンクノードと、
ファンクショナルユニットノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２３】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記アドレスフローサブグラフが、
メモリノード（データアウトプットポート）、タイミングユニットノード（イネイブルシグナルアウトプットポート）およびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（アドレスインプットポート）およびシステムデータインプットノード（アクノリッジシグナル）を含むシンクノードと、
アキュムレータノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２４】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ネステッドループボディにおける各データ表現が、変数、アレイまたはコンフィギュレーションコンスタントを含む論理および計算表現への変数またはアレイの割り当てにより構成されていることを特徴とするアーキテクチャテンプレート。
【請求項２５】
請求項２３記載のデータ表現において、前記データ表現において、各アレイのインデックスが（（ａｌｐｈａ＊ｉ＋ｂｅｔａ）÷ｇａｍｍａ）＋ｄｅｌｔａの形であり、ここでｉはループ変数であり、ａｌｐｈａ、ｂｅｔａ、ｇａｍｍａおよびｄｅｌｔａはｉ以内のループ変数を用いた同じ形式表現により再帰的に定義されうることを特徴とするデータ表現。
【請求項２６】
請求項１９記載のコプロセッサプログラミングツールにおいて、
システムグラフにおけるノードをハードウェアグラフのノードに再帰的にマップするファンクションは、所定のシステムノードにマップされうるすべてのハードウェアノード候補のリストを作成し、前記システムノードを各ハードウェアノード候補に試験的にマップして回帰的にリストにおける次のシステムノードのマップを試行し、成功した場合には現在のマッピングを維持して正（ｔｒｕｅ）を返し、失敗した場合には次のハードウェアノードを試行し、すべての候補の試行が失敗した場合には誤（ｆａｌｓｅ）を返すことにより実行されることを特徴とするコプロセッサプログラミングツール。
【請求項２７】
請求項１記載のアーキテクチャテンプレートにおいて、
メモリデータポートの数以下のメモリアクセスが平行かつ１サイクルで実行され、すべてのファンクショナルユニット平行かつ１サイクルで結果を生成しうることを特徴とするアーキテクチャテンプレート。
【請求項２８】
請求項１記載のアーキテクチャテンプレートにおいて、
クロック周期が増えるのを回避するためにコネクションクロスバーにおける希薄なリンクを維持しながらファンクショナルユニットおよび設置メモリの数を増やすことにより前記システムの動作がスケールされうることを特徴とするアーキテクチャテンプレート。
【請求項２９】
請求項１記載のアーキテクチャテンプレートにおいて、
結論コプロセッサが同位相でまたは位相が異なるファーストインファーストアウトメモリを用いて接続され、全体的に異なる位相で局所的に同位相のシステムを形成することを特徴とするアーキテクチャテンプレート。
【請求項１】
計算および論理オペレーションを含む表現のコンピューティングネステッドループ用のリコンフィギュラブルコプロセッサのアーキテクチャテンプレートであって、
アプリケーションドメインにしたがって選択されるリコンフィギュラブルファンクショナルユニットの、パイプラインの有無に無関係な不特コンスタントかつ不特定タイプのリニアアレイと、
中間データおよびアドレス計算法を保存する不特定数かつ不特定タイプの設置メモリのリニアアレイと、
前記設置メモリのアドレスの複合シーケンスを計算するリコンフィギュラブルアドレス生成ブロックと、
システムインプット、メモリデータアウトプットポートおよびプログラムされたコンスタントを前記ファンクショナルユニットインプットに接続するために前結合時において定義される部分的かつリコンフィギュラブルリードクロスバーと、
ファンクショナルユニットアウトプットをシステムアウトプットまたはメモリデータインプットポートを接続するために前合成時において定義される部分的かつリコンフィギュラブル書き込みクロスバーと、
制御、ステータスおよびコンフィギュレーションレジストリを有するレジスタファイルとを備え、前記コンフィギュレーションレジスタはリコンフィギュラブルファンクショナルユニット、リコンフィギュラブルアドレス生成ブロック、部分的かつリコンフィギュラブルコネクションクロスバーのコンフィギュレーションを保存し、前記データおよびアドレス計算法に用いられるコンスタントを保存することを特徴とするアーキテクチャテンプレート。
【請求項２】
請求項１記載のアーキテクチャテンプレートにおいて、前記リコンフィギュラブルアドレス生成ブロックが、
アドレス生成を開始、停止および再開することにより、前記コプロセッサに実行を開始、停止および再開させる制御ユニットと、
設置メモリに格納されているインデックスアレイへのアドレスを適時生成するため、前記ファンクショナルユニットの機能を適時活性化するため、および、システムインプットおよびメモリ書き込みを適時要求するために用いられるイネイブルシグナルを生成するプラグラマブルタイミングユニットと、
複合アドレスシーケンスを生成するために接続されているプラグラマブルアキュムレータのリニアアレイと、
前記イネイブルシグナルを前記アレイにおける前記アキュムレータに接続し、かつ、前記システムインプットにおける外部データの読み取りを認める前複合時に定義される部分的かつリコンフィギュラブルイネイブルクロスバーと、
前結合時に定義され、アキュムレータアウトプットおよびコンフィギュレーションコンスタントを他のアキュムレータインプットに接続する部分的かつリコンフィギュラブルインプットクロスバーと、
前複合時に定義され、生成アドレスを形成するアキュムレータアウトプットおよび各イネイブルシグナルをメモリアドレスに接続する部分的かつリコンフィギュラブルアウトプットクロスバーと、
アドレスがメモリに格納されている場合、アドレスポートを格納するルーティングメモリデータポートとを備えていることを特徴とするアーキテクチャテンプレート。
【請求項３】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、前記プログラミングユニットが、
各ロウが周期において同じ遅れと、コプロセッサが実行可能なネステッドループの最大数を表わすコラムの数とを有することにより特徴付けられているイネイブルシグナルのグループを生成し、一のコラムにおけるすべてのカウンタが同じエンドリミットでプログラムされ、制御される前記ループの反復回数を決定するプラグラマブルカウンタのマトリクスと、
前記プログラムされたコラムの前記数を用いて所定のコンフィギュレーションにネステッドループの実際の数を決定するエンコーダと、
全体的な前記イネイブルシグナルを所定の最大遅れ以下で遅らせ、前記遅れがないイネイブルおよび現在のコンフィギュレーションにおける、前記アーキテクチャにおける最大許容遅れと相違しうる前記最大遅れを有する各イネイブルグループに対してプログラムされている遅れをもってアウトプットイネイブルシグナルを遅らせるディレイユニットとを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項４】
請求項３記載のプラグラマブルタイミングユニットにおいて、
前記プラグラマブルカウンタのマトリクスにより生成された前記イネイブルシグナルがデータストリームをお互いに遅らせ、かつ、ファンクショナルユニットにより異なる遅れをもって導入された前記データフローグラフにおける異なる潜在を補償させるのに用いられ、
前記プラグラマブルタイミングユニットが、データがインプットまたは格納されてから読み出されるまでの時間を計測し、イネイブルおよびデータが同等に遅れているファンクショナルユニットを通じて前記データを同行させ、データの書き込みからアウトプットまたは格納までの時間を計測することを特徴とするプラグラマブルタイミングユニット。
【請求項５】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記プラグラマブルアキュムレータが、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記インプットクロスバーを前記アキュムレータの開始値を定めるインプットシグナルと、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記アキュムレータのインクリメント値を定めるインプットシグナルと、
前記アキュムレータの動作を可能とするイネイブルシグナルと、
前記開始値をリロードする再開イネイブルシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる前記アキュムレータのオフセット値を定めるインプットシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、前記アキュムレータのモジューロ値を定めるコンフィギュレーションレジスタと、
他のアキュムレータの前記生成アドレスまたは前記インプットとして用いられるアウトプット計算値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項６】
請求項１記載のアーキテクチャテンプレートにおいて、
前記コンフィギュレーション、ステータス／制御レジスタファイルが、
アドレスが付されうる、ランタイムにおけるファイングラニュラリティの部分的なレコンフィギュレーションを可能とするリード／ライトメモリがマップされたインターフェースと、
外部アシスタンスを案内または依頼するアウトプットリクエストシグナルとを有することを特徴とするアーキテクチャテンプレート。
【請求項７】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ファンクショナルユニットアレイに属する各ファンクショナルユニットが前記コプロセッサを停止させうるブレークシグナルを発することを特徴とするアーキテクチャテンプレート。
【請求項８】
請求項１記載のアーキテクチャテンプレートにおいて、
前記複合システムインプットはスレーブリクエスト／アクノリッジインターフェースであり、かつ、前記複合システムアウトプットはマスターリクエスト／アクノリッジインターフェースであることを特徴とするアーキテクチャテンプレート。
【請求項９】
請求項８記載のアーキテクチャテンプレートにおいて、
システムインプットリクエストまたはシステムアウトプットアクノリッジの欠落が、システムインプットからのデータ読み出しおよびシステムアウトプットへのデータ書き込みのうち一方または両方のために前記表現が実行される場合、コプロセッサを始動させることを特徴とするアーキテクチャテンプレート。
【請求項１０】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記制御ユニットが前記コプロセッサを機能化かつ非機能化し、最も外側のループインデックスがラップアラウンドしたときに終了し、前記コプロセッサのインプットデータ欠乏、アウトプットデータ過剰、または、ファンクショナルユニットが火をつける一もしくは複数の遮断状態を停止することを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１１】
請求項１記載のコプロセッサプログラミングツールにおいて、
前記コプロセッサの前記アーキテクチャ記述のコンパイラと、
慣用プロセッサ用のオリジナルプログラムにおいてタグが付されかつ上書きされ、かつ、慣用プログラミング言語のシンタックスに本質的に類似するシンタックスを用いる前記ネステッドループシーケンス用のパーサーと、
ネステッドループシーケンスのコード用の、前記コードを前記コプロセッサの特定コンフィギュレーションに変換するコンパイラとを有するコプロセッサプログラミングツールを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項１２】
請求項１記載のアーキテクチャ記述ファイルにおいて、
リコンフィギュラブルファンクショナルユニットの数およびタイプの記述と、
数、タイプ、データおよびアドレスの設置メモリの幅と、
リコンフィギュラブルアドレス生成ブロックの記述と、
リコンフィギュラブルリード／ライトクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１３】
請求項１２記載のアーキテクチャ記述ファイルにおいて、
プラグラマブルタイミングユニットブロックの記述と、
プラグラマブルアキュムレータの数およびタイプの記述と、
リコンフィギュラブルイネイブル、インプットおよびアウトプットクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１４】
請求項１３記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブルタイミングユニットの記述が、
グループに属するネステッドループの数の記述と、
生成されるイネイブルシグナルの異なる遅延バージョンの数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１５】
請求項１２記載のアーキテクチャ記述ファイルのコンフィギュレーション記述ファイルが、
ファンクショナルユニットのコンフィギュレーションのパラメータ／値による記述と、
前記設置メモリのコンフィギュレーションと、
アドレス生成ブロックのリコンフィギュラブルコンフィギュレーションの記述と、
読み取り／書き込みクロスバーのリコンフィギュラブルコンフィギュレーションの、ポートがファンクショナルユニットのインプットおよびアウトプットのうちいずれかに接続されていることから暗黙的に推察される読み取りまたは書き込みモードによる記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１６】
請求項１５記載のコンフィギュレーション記述ファイルにおいて、前記コンフィギュレーション記述ファイルにおける前記リコンフィギュラブルアドレス生成ブロックの前記コンフィギュレーションの前記記述が、
前記プラグラマブルタイミングユニットブロックのコンフィギュレーションの記述と、
各プラグラマブル累算器のコンフィギュレーションの記述と、
イネイブル、インプットおよびアウトプットクロスバーのコンフィギュレーションの記述とを備えていることを特徴とするコンフィギュレーション記述ファイル。
【請求項１７】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、前記プラグラマブルタイミングユニットコンフィギュレーションの記述が、
各ネステッドループの終端の記述と、
各機能化シグナルグループについて遅延サイクル数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１８】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブル計算機の記述が、
コンフィギュレーションコンスタントに接続された場合における開始および繰り上げ値と、
前記累算器が複合累算器ユニットであり、オフセットインプットがコンフィギュレーションに接続されている場合におけるオフセット値と、
前記累算器が複合累算器ユニットである場合におけるモジューロ値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１９】
請求項１１記載のコプロセッサプログラミングツールにおいて、
ネステッドループボディにおける計算および論理表現を解剖して完全なシステムグラフを得るファンクションと、
アーキテクチャを順番に表現するアーキテクチャを表わすハードウェアにマップされるシステムグラフのノードの当該順番のリスト生成するファンクションと、
請求項１３記載の前記アーキテクチャ記述ファイルを解剖するとともにハードウェアグラフを創出するファンクションと、
前記システムグラフの各ノードを反復的に前記ハードウェアグラフのノードにマップするファンクションとを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項２０】
請求項１９記載のコプロセッサプログラミングツールにおいて、
前記システムグラフがコンフィギュレーションサブグラフのシーケンスを備え、各コンフィギュレーショングラフがネステッドグループに対応していることを特徴とするコプロセッサプログラミングツール。
【請求項２１】
請求項２０記載のシステムグラフにおいて、
各コンフィギュレーションサブグラフが、データフローサブグラフと、アドレスフローサブグラフとを備えていることを特徴とするシステムグラフ。
【請求項２２】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記データフローサブグラフが、
メモリノード（データアウトプットポート）、システムデータインプットノードおよびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（データインプットポート）およびシステムデータアウトプットノードを含むシンクノードと、
ファンクショナルユニットノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２３】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記アドレスフローサブグラフが、
メモリノード（データアウトプットポート）、タイミングユニットノード（イネイブルシグナルアウトプットポート）およびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（アドレスインプットポート）およびシステムデータインプットノード（アクノリッジシグナル）を含むシンクノードと、
アキュムレータノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２４】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ネステッドループボディにおける各データ表現が、変数、アレイまたはコンフィギュレーションコンスタントを含む論理および計算表現への変数またはアレイの割り当てにより構成されていることを特徴とするアーキテクチャテンプレート。
【請求項２５】
請求項２３記載のデータ表現において、前記データ表現において、各アレイのインデックスが（（ａｌｐｈａ＊ｉ＋ｂｅｔａ）÷ｇａｍｍａ）＋ｄｅｌｔａの形であり、ここでｉはループ変数であり、ａｌｐｈａ、ｂｅｔａ、ｇａｍｍａおよびｄｅｌｔａはｉ以内のループ変数を用いた同じ形式表現により再帰的に定義されうることを特徴とするデータ表現。
【請求項２６】
請求項１９記載のコプロセッサプログラミングツールにおいて、
システムグラフにおけるノードをハードウェアグラフのノードに再帰的にマップするファンクションは、所定のシステムノードにマップされうるすべてのハードウェアノード候補のリストを作成し、前記システムノードを各ハードウェアノード候補に試験的にマップして回帰的にリストにおける次のシステムノードのマップを試行し、成功した場合には現在のマッピングを維持して正（ｔｒｕｅ）を返し、失敗した場合には次のハードウェアノードを試行し、すべての候補の試行が失敗した場合には誤（ｆａｌｓｅ）を返すことにより実行されることを特徴とするコプロセッサプログラミングツール。
【請求項２７】
請求項１記載のアーキテクチャテンプレートにおいて、
メモリデータポートの数以下のメモリアクセスが平行かつ１サイクルで実行され、すべてのファンクショナルユニット平行かつ１サイクルで結果を生成しうることを特徴とするアーキテクチャテンプレート。
【請求項２８】
請求項１記載のアーキテクチャテンプレートにおいて、
クロック周期が増えるのを回避するためにコネクションクロスバーにおける希薄なリンクを維持しながらファンクショナルユニットおよび設置メモリの数を増やすことにより前記システムの動作がスケールされうることを特徴とするアーキテクチャテンプレート。
【請求項２９】
請求項１記載のアーキテクチャテンプレートにおいて、
結論コプロセッサが同位相でまたは位相が異なるファーストインファーストアウトメモリを用いて接続され、全体的に異なる位相で局所的に同位相のシステムを形成することを特徴とするアーキテクチャテンプレート。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１０−４４７３１（Ｐ２０１０−４４７３１Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−２８０２２５（Ｐ２００８−２８０２２５）
【出願日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（５０８３２５０６１）コアワークス エスエー (1)
【氏名又は名称原語表記】ＣＯＲＥＷＯＲＫＳ， Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２８０２２５（Ｐ２００８−２８０２２５）
【出願日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（５０８３２５０６１）コアワークス エスエー (1)
【氏名又は名称原語表記】ＣＯＲＥＷＯＲＫＳ， Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]