JP5419419B2 - システム - Google Patents

Description

本発明は、コンピュータアーキテクチャに関し、特に、アルゴリズムにおけるネステッドループの加速に関する。

計算機器はユビキタスになり、携帯電話、パーソナルディジタル機器および携帯型オーディオプレイヤーなど多くの電子機器が人々により日常生活において持ち運ばれる製品となっている。

これらの製品はフォンノイマンのアーキテクチャとして知られているコンピューティングパラダイムにしたがう内蔵プロセッサにより実現されてきた。内蔵機器が複雑になればなるほどより速いクロック周波数を必要とし、かつ、より多くのパワーを消費するようになってきた。これは従来型プロセッサが指示を連続的に実行し、かつ、データを連続的に取り出すからである。バッテリを電源とする機器についてフォンノイマンコンピューティングパラダイムは維持されえず、代わりになるものが見出されなくてはならない。

最近、より平行なアーキテクチャへの大きな関心が、マルチメディアおよびコミュニケーションアルゴリズムの強い計算ニーズに向けられている。アプリケーション専用集積回路（ＡＳＩＣｓ）が、アルゴリズムの重要部分において並行に実行される処理の数を増加させるのに用いられており、クロック周波数の増大を回避し、その結果としてエネルギー消費を実用的な限度内に維持している。しかし、ＡＳＩＣｓは開発時間が長く、一度組み立てられると変更されえない。これでは非常に速く変化するマーケットの動きおよび最近の電子機器の短いライフ期間には合致しえない。

プログラマブル手法は実際にはより理想的であり、これがテクノロジーおよびリコンフィギュラブルコンピューティングが実現された経緯である。リコンフィギュラブルコンピュータはコンフィギュレーションメモリのコンテンツを変更することにより、ポストシリコン時においてアーキテクチャが変更されうるマシーンである。リコンフィギュラブルコンピュータの不可欠な要素はプログラマブルマルチプレクサである（図１）。プログラマブルマルチプレクサはインプットＡおよびＢと、アウトプットＣと、Ｓビットのコンフィギュレーションとを有する。Ｓが０に設定された場合、ＡからＣへの経路が生成される。Ｓが１に設定された場合、ＢからＣへの経路が生成される。プログラマブルマルチプレクサを十分に保有することにより、異なるアルゴリズムをより適当に実行するために異なるハードウェアアーキテクチャを迅速に生成するように、機能ユニットおよびメモリ要素を思い通りに接続させることができる。本発明はリコンフィギュラブルアーキテクチャのクラスを得るためのテンプレートである。

存在するリコンフィギュラブルアーキテクチャは（１）ファイングレインアレイおよび（２）コースグレインアレイの２つに分類される。

ファイングレインアレイはフィールドプログラマブルゲートアレイ（ＦＰＧＡｓ）の形成における広く拡散したポピュラリティを獲得した。ＦＰＧＡはプログラマブルスイッチの大きなネットワークにより接続された狭いビットスライスに対して論理機能を実行する小さなプログラマブル機能ユニットの大きなアレイである。機能ユニットは本質的にプログラマブルルックアップテーブル（ＬＵＴｓ）であり、スイッチのネットワークは前述のプログラマブルマルチプレクサからなる。商業的なＦＰＧＡ機器はさまざまなメーカーにより製品化されている。ＦＰＧＡｓは電子プログラミングにより要求される回路の生成を許容するにもかかわらず、ＬＵＴｓの豊富なアレイおよびルーティングスイッチは巨大なエリアおよびパワーの不利益を表わしている。専念ハードウェアにおいて実施されている同じ回路におけるエネルギー欠乏は非常に小さくかつ少なくなる。したがって、バッテリ運転機器におけるＦＰＧＡｓの使用はルールというよりもむしろ排除されてきた。

ＦＰＧＡｓは、必要とされる巨大回路エリアを軽減しかつパフォーマンスを改善するため、標準的なプロセッサ、ならびに、マルチプライヤおよび設置されているＲＡＭｓのような特定ブロックに結合されている。このように、アルゴリズムの特定および重要部分の多くがリコンフィギュラブルファブリックに対して実行され、その一方、その他のわずかな重要部分がプロセッサにより実行される。このようなハイブリッドアーキテクチャの例が研究者により提案され（非特許文献４，１６，１１参照）、かつ、ＦＰＧＡの取引業者により市場に導入された。しかし、これらの回路はいまだシリコンエリアの意味で無駄が多く、かつ、クロック周波数およびコンフィギュレーション時間の意味で遅い。

コースグレインアレイは柔軟性および汎用性を犠牲にすることでファイングレインアレイの前記のような制限を克服する。コースグレインアレイは最近の研究対象とされ、きわめてわずかのアーキテクチャが研究者により提案され（非特許文献３，６，１２，５，７，８，１０，９，１３，２，１４，１７参照）、かつ、会社が設立された（非特許文献１８，１９参照）。これらのアレイは高いグラニュラリティの機能ユニットおよび少ない複合接続ネットワークを有し、マルチメディアおよびコミュニケーションのような目標とするＤＳＰアプリケーションを改善する。機能ユニットは通常は２〜３バイトのスライスよりもむしろ２〜３バイトで計算および論理処理を実行する。結果は汎用的ではないもののわずかなコンフィギュレーションデータを必要とする非常にコンパクトかつ高速のリコンフィギュラブルシステムとなり、このシステムは実行時間において機敏かつ部分的に交換されうる。

他の重要な視点はリコンフィギュラブルユニットがどのように内蔵マイクロプロセッサに接続されているかということである。当初、再構築はプロセッサファンクショナルユニットレベルで始まり、かつ、特別な指示により誘起された（非特許文献１５，１２，１参照）。その後、リコンフィギュラブルユニットはプロセッサに緊密に接続されたコプロセッサになり、かつ、動作するためになおも特別な指示を必要とする（非特許文献４，１６，３，６，１２参照）。より最近では、システムバスに取り付けられ、かつ、ホストプロセッサ指示セットの延長を必要としないコプロセッサが主要な研究対象となってきている（非特許文献２，７，１７参照）。われわれの仕事は最後のカテゴリに合致している。
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+β₁)*j + β₂)%γ)+δ
x = M₂.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;
}

前記擬似コードにしたがってＳＧノードをＨＧノードにマッピングする際における最初の事項はグラフのノードのすぐ次のノードを取得することである。アルゴリズムがグラフシンクからグラフソースに進行するのでこれらのノードはすでにＨＧノードにマップされている。次のＨＧノードから作業は、ＳＧに対応する通常のすぐ先のＨＧノードのリストを計算し、未使用の乗算器により到達されうる。これは質問されているノードにマップされうる、可能性があるＨＧノードのリストである。このリストにおけるノードは適切な候補を見つけるために検索される。第１に候補ＨＧノードは加算器、乗算器、メモリ等のノードと同じタイプでなくてはならない。第２にノードは使用されていてはならない。これらのテストのうち一方が満たされていない場合、処理は失敗となる。これらのチェックが実行されると、ＨＧノードはその次のＨＧノードに伝送される。すなわち、次のＨＧノードのインプット乗算器が当該ノードを受け取るように設定される。もしこれがマップ対象となる最期のノードである場合、処理は成功となる。そうでない場合、マップ処理はＳＧの次のノードに反復的に適用される。もし成功すれば処理は成功となる。そうでない場合、これは次のノードのマッピングが現在または先のノードの現在のマッピングにより達成されなかったことを意味する。この場合、次のノードへの伝送は行われず次の候補ＨＧノードが試行される。すべての候補ノードへの試行が失敗した後、処理は失敗となる。

本発明により創出されたリコンフィギュラブルある実験用コプロセッサの適用例は次に示される。例はＭＰＥＧ１層ＩＩＩ（ＭＰ３）のデコーダーアルゴリズムである。アルゴリズムは（１）従来型プロセッサおよび（２）実験用コプロセッサにより加速された同一の従来型コプロセッサにおいて実行された。プロセッサは３２ビットで０．８１ＤＭＰＴＳの演算能力を有するハーバードアーキテクチャである。実験用コプロセッサは２つのネステッドループ、３２ビットデータ経路、２つの加算器および累算器、２つの乗算器および切替器、４キロバイトのＲＯＭおよび８キロバイトのＲＡＭをまとめた３つのデュアルポートメモリブロックにより生成された。

ＭＰ３のベンチマークのセットの実行から得られた実験結果が表１に示されている。従来型プロセッサにおけるアルゴリズムの最初のプロファイリングから、われわれは２つの過程（多相合成および逆改良型離散コサイン変換（ＩＭＤＣＴ））が時間の９５％を費やすことを発見した。このため、コプロセッサにおいて当該過程を加速した場合、加速に対するポテンシャルは２０である。多相合成過程は平均で１８．７倍加速された。ＩＭＤＴＣ過程は平均で４３．９倍加速された。これはアルゴリズムを全体的に１１．９倍加速する。プロセッサおよびコプロセッサにより形成された完全なシステムのプロファイリングは主要な処理に対する演算処理負荷配分のバランスに優れている。完全なシステムにおいて多層合成およびＩＭＤＴＳ過程は、加速前の演算処理負荷が９５％であるのに対して演算処理負荷が３４％であった。

本実施例ではコプロセッサインスタンスの追加の結果としてシリコンエリアは２倍になった。演算処理能力は１２倍に上昇し、このことはプロセッサ−コプロセッサシステムが演算処理能力を同じレベルに維持しながら、おおよそ６倍もの消費電力が節約されたことを意味する。

前記リコンフィギュラブルコプロセッサアーキテクチャテンプレートが単に本発明の原則を記述しているにしか過ぎないことはいうまでもない。前記アーキテクチャの変更または改良は本発明の原則から外れない範囲で可能である。すべての変更または改良は本発明の本発明の技術的範囲に属し、特許請求の範囲により保護されなくてはならない。

プログラマブルマルチプレクサ コプロセッサアーキテクチャテンプレートの上面図 アドレス生成ユニットのアーキテクチャ タイミングユニットマトリックス ディレイユニット 基礎累算器ユニット 複合累算器ユニット 許可クロスバーにおける許可および再開イネイブルシグナル累算器の選択 インプットクロスバーにおける各許可ユニット用のスタート、インクリメントおよびオフセットシグナルの選択 アウトプットクロスバーにおける累算器カウントシグナルからのメモリポートアドレスの選択 機能ユニット用のシグナルの選択 システムアウトプットおよびメモリインプットの選択 制御コンフィギュレーション、データインおよびデータアウトインターフェース 制御レジスタ ステータスレジスタ 制御回路 機能ユニットから発せられたブレーク状態の選択 Ｉ／Ｏ依存ユニットの許可の選択 コプロセッサプログラミングフロー データフローグラフの一例 アドレスフローグラフの一例

Claims (21)

1. 計算および論理オペレーションを含む表現のコンピューティングネステッドループの演算に用いられるリコンフィギャブルコプロセッサを有するシステムであって、
   前記リコンフィギャブルコプロセッサが、
   アプリケーションドメインにしたがって選択され、かつ、パイプラインとは無関係な不特定数かつ不特定型のリコンフィギュラブルファンクショナルユニットを構成要素として有するリニアアレイと、
   中間データおよびアドレス計算を保存する不特定数かつ不特定型の設置メモリを構成要素として有するリニアアレイと、
   前記設置メモリのアドレスの複合シーケンスを計算するリコンフィギュラブルアドレス生成ブロックと、
   システムインプット、メモリデータアウトプットポートおよびプログラムされた定数を前記リコンフィギュラブルファンクショナルユニットのインプットに接続するために接続前において定義される部分的かつリコンフィギュラブルリードクロスバーと、
   ファンクショナルユニットのアウトプットをシステムアウトプットまたはメモリデータインプットポートに接続するために接続前において定義される部分的かつリコンフィギュラブルライトクロスバーと、
   制御、ステータスおよびコンフィギュレーションレジスタを有するレジスタファイルとを備え、
   前記コンフィギュレーションレジスタは、前記リコンフィギュラブルファンクショナルユニット、前記リコンフィギュラブルアドレス生成ブロック、前記部分的かつリコンフィギュラブルリードクロスバー及び前記部分的かつリコンフィギュラブルライトクロスバーのコンフィギュレーションを保存し、かつ、前記中間データおよびアドレス計算に用いられる定数を保存し、
   前記リコンフィギュラブルアドレス生成ブロックが、
   アドレス生成を開始、停止および再開することにより、前記コプロセッサに実行を開始、停止および再開させる制御ユニットと、
   設置メモリに格納されているインデックスアレイへのアドレスを適時生成するため、前記ファンクショナルユニットの機能を適時活性化するため、および、システムインプットおよびメモリ書き込みを適時要求するために用いられるイネイブルシグナルを生成するプログラマブルタイミングユニットと、
   複合アドレスシーケンスを生成するために接続されているプログラマブルアキュムレータを構成要素として有するリニアアレイと、
   前記イネイブルシグナルを前記アレイにおける前記アキュムレータに接続し、かつ、前記システムインプットにおける外部データの読み取りを認める接続前に定義される部分的かつリコンフィギュラブルイネイブルクロスバーと、
   接続前に定義され、アキュムレータアウトプットおよびコンフィギュレーションコンスタントを他のアキュムレータインプットに接続する部分的かつリコンフィギュラブルインプットクロスバーと、
   接続前に定義され、生成アドレスを形成するプログラマブルアキュムレータのアウトプットおよび各イネイブルシグナルをメモリアドレスポートに接続し、かつ、アドレスがメモリに格納されている場合、メモリアドレスポートからメモリデータポートへの経路を設定する部分的かつリコンフィギュラブルアウトプットクロスバーと、
   を備えていることを特徴とするシステム。
2. 請求項１記載のシステムにおいて、
   前記プログラマブルタイミングユニットが、
   各ロウが周期において同じ遅れと、コプロセッサが実行可能なネステッドループの最大数を表わすコラムの数とを有することにより特徴付けられているイネイブルシグナルのグループを生成し、一のコラムにおけるすべてのカウンタが同じエンドリミットでプログラムされ、制御される前記ループの反復回数を決定するプログラマブルカウンタのマトリクスと、
   前記プログラムされたコラムの前記数を用いて所定のコンフィギュレーションにネステッドループの実際の数を識別するエンコーダと、
   全体的な前記イネイブルシグナルを所定の最大許容遅れ以下で遅らせ、前記遅れがないイネイブルおよび所定の遅れのイネイブルを有する各イネイブルグループに対してプログラムされている遅れをもってアウトプットイネイブルシグナルを遅らせる遅延ユニットとを備え、
   前記所定の遅れは、前記システムにおける最大許容遅れと相違しうる現在のコンフィギュレーションでの最大遅れであることを特徴とするシステム。
3. 請求項２記載のシステムにおいて、
   前記プログラマブルカウンタのマトリクスにより生成された前記イネイブルシグナルが、
   データストリームをお互いに遅らせ、かつ、ファンクショナルユニットにより異なる遅れをもって導入されたデータフローグラフにおける異なる遅れを補正させるのに用いられ、
   インプットまたはメモリからデータが読み出される頃合いを見計らい、
   イネイブルシグナルおよびデータが同等に遅れるファンクショナルユニットを通じて前記データに同行し、
   かつ、アウトプットまたはメモリへデータを書き込む頃合いを見計らうことを特徴とするシステム。
4. 請求項１記載のシステムにおいて、
   前記プログラマブルアキュムレータが、
   他のアキュムレータまたはコンフィギュレーション定数により前記インプットクロスバーを介してドライブされうる、前記インプットクロスバーを前記アキュムレータの開始値を定めるインプットシグナルと、
   他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記アキュムレータのインクリメント値を定めるインプットシグナルと、
   前記アキュムレータの動作を可能とするイネイブルシグナルと、
   前記開始値をリロードする再開イネイブルシグナルと、
   前記アキュムレータが複合アキュムレータユニットである場合、他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる前記アキュムレータのオフセット値を定めるインプットシグナルと、
   前記アキュムレータが複合アキュムレータユニットである場合、前記アキュムレータのモジューロ値を定めるコンフィギュレーションレジスタと、
   他のアキュムレータの前記生成アドレスまたは前記インプットとして用いられるアウトプット計算値とを備えていることを特徴とするシステム。
5. 請求項１記載のシステムにおいて、
   前記コンフィギュレーション、ステータス／制御レジスタファイルが、
   アドレスが付されうる、運転時間中における高精度の部分的な再構築を可能とするリード／ライトメモリがマップされたインターフェースと、
   外部アシスタンスを案内または依頼するアウトプットリクエストシグナルとを有することを特徴とするシステム。
6. 請求項１記載のシステムにおいて、
   前記リコンフィギュラブルファンクショナルユニットを構成要素として有するリニアアレイに属する各ファンクショナルユニットが前記コプロセッサを停止させうるブレークシグナルを発することを特徴とするシステム。
7. 請求項１記載のシステムにおいて、
   複合システムインプットはスレーブリクエスト／アクノリッジインターフェースであり、かつ、複合システムアウトプットはマスターリクエスト／アクノリッジインターフェースであることを特徴とするシステム。
8. 請求項７記載のシステムにおいて、
   システムインプットリクエストまたはシステムアウトプットアクノリッジの欠落が、システムインプットからのデータ読み出しおよびシステムアウトプットへのデータ書き込みのうち一方または両方のために前記表現が実行される場合、コプロセッサを始動させることを特徴とするシステム。
9. 請求項１記載のシステムにおいて、
   前記制御ユニットが、
   前記コプロセッサを機能化かつ非機能化し、
   最も外側のループインデックスがラップアラウンドしたときに処理を終了し、
   前記コプロセッサのインプットデータ欠乏若しくはアウトプットデータ過剰において、又は、ファンクショナルユニット由来の一もしくは複数の遮断状態が生じた場合、前記コプロセッサを停止することを特徴とするシステム。
10. 請求項１記載のシステムにおいて、
    前記コンフィギュレーションレジスタが、
    リコンフィギュラブルファンクショナルユニットの数およびタイプの記述と、
    数、タイプ、データおよびアドレスの設置メモリの幅と、
    リコンフィギュラブルアドレス生成ブロックの記述と、
    リコンフィギュラブルリード／ライトクロスバーの記述とを備えていることを特徴とするシステム。
11. 請求項１０記載のシステムにおいて、
    前記コンフィギュレーションレジスタが、
    プログラマブルタイミングユニットブロックの記述と、
    プログラマブルアキュムレータの数およびタイプの記述と、
    リコンフィギュラブルイネイブル、インプットおよびアウトプットクロスバーの記述とを備えていることを特徴とするシステム。
12. 請求項１１記載のシステムにおいて、
    前記リコンフィギュラブルアドレス生成ブロックの記述が、
    前記プログラマブルタイミングユニットの記述が、
    グループに属するネステッドループの数の記述と、
    生成されるイネイブルシグナルの異なる遅延バージョンの数の記述とを備えていることを特徴とするシステム。
13. 請求項１０記載のシステムにおいて、
    前記コンフィギュレーションレジスタが、
    ファンクショナルユニットのコンフィギュレーションのパラメータ／値による記述と、
    前記設置メモリのコンフィギュレーションと、
    アドレス生成ブロックのリコンフィギュラブルコンフィギュレーションの記述と、
    読み取り／書き込みクロスバーのリコンフィギュラブルコンフィギュレーションの、ポートがファンクショナルユニットのインプットおよびアウトプットのうちいずれかに接続されていることから暗黙的に推察される読み取りまたは書き込みモードによる記述とを備えていることを特徴とするシステム。
14. 請求項１３記載のシステムにおいて、
    前記コンフィギュレーションレジスタにおける前記リコンフィギュラブルアドレス生成ブロックの前記コンフィギュレーションの前記記述が、
    プログラマブルタイミングユニットブロックのコンフィギュレーションの記述と、
    各プログラマブルアキュムレータのコンフィギュレーションの記述と、
    イネイブル、インプットおよびアウトプットクロスバーのコンフィギュレーションの記述とを備えていることを特徴とするシステム。
15. 請求項１４記載のシステムにおいて、
    前記プログラマブルタイミングユニットブロックのコンフィギュレーションの記述が、
    各ネステッドループの終端の記述と、
    各イネイブルシグナルグループについて遅延サイクル数の記述とを備えていることを特徴とするシステム。
16. 請求項１４記載のシステムにおいて、
    前記プログラマブルアキュムレータのコンフィギュレーションの記述が、
    コンフィギュレーション設定に接続された場合における開始および繰り上げ値と、
    前記プログラマブルアキュムレータが複合累算器ユニットであり、オフセットインプットがコンフィギュレーションに接続されている場合におけるオフセット値と、
    前記プログラマブルアキュムレータが複合累算器ユニットである場合におけるモジューロ値とを備えていることを特徴とするシステム。
17. 請求項１記載のシステムにおいて、
    前記ネステッドループのボディにおける各データ表現が、変数、アレイまたはコンフィギュレーションコンスタントを含む論理および計算表現への変数またはアレイの割り当てにより構成されていることを特徴とするシステム。
18. 請求項１７記載のシステムにおいて、
    前記データ表現における、各アレイのインデックスが（（ａｌｐｈａ＊ｉ＋ｂｅｔａ）÷ｇａｍｍａ）＋ｄｅｌｔａの形であり、ここでｉはループ変数であり、ａｌｐｈａ、ｂｅｔａ、ｇａｍｍａおよびｄｅｌｔａはｉ以内のループ変数を用いた同じ形式表現により再帰的に定義されうることを特徴とするシステム。
19. 請求項１記載のシステムにおいて、
    メモリデータポートの数以下のメモリアクセスが並列かつ１サイクルで実行され、すべてのファンクショナルユニットが並列かつ１サイクルで結果を生成しうることを特徴とするシステム。
20. 請求項１記載のシステムにおいて、
    クロック周期が増えるのを回避するためにコネクションクロスバーにおける希薄なリンクを維持しながらファンクショナルユニットおよび設置メモリの数を増やすことにより前記システムの動作がスケールされうることを特徴とするシステム。
21. 請求項１記載のシステムにおいて、
    前記リコンフィギャブルコプロセッサが同期のまたは非同期のファーストインファーストアウトメモリを用いて接続され、全体的に非同期で局所的に同期されたシステムを形成することを特徴とするシステム。

Images