(57)【要約】      （修正有）【課題】開発期間が長期化するＡＳＩＣｓの変更設計を容易にするアーキテクチャテンプレートを提供する。【解決手段】提案するテンプレートから得られるアーキテクチャは一般的なチップシステム（ＳｏＣ）に集積され、ボディが平行のファンクショナルユニットアレイにおいて実行されるオペレーションのエクスプレッションであるネステッドプログラムループを実行するリコンフィギュラブルコプロセッサにより構成されている。【選択図】図１
2010044731.tif 000002
【特許請求の範囲】
【請求項１】
計算および論理オペレーションを含む表現のコンピューティングネステッドループ用のリコンフィギュラブルコプロセッサのアーキテクチャテンプレートであって、
アプリケーションドメインにしたがって選択されるリコンフィギュラブルファンクショナルユニットの、パイプラインの有無に無関係な不特コンスタントかつ不特定タイプのリニアアレイと、
中間データおよびアドレス計算法を保存する不特定数かつ不特定タイプの設置メモリのリニアアレイと、
前記設置メモリのアドレスの複合シーケンスを計算するリコンフィギュラブルアドレス生成ブロックと、
システムインプット、メモリデータアウトプットポートおよびプログラムされたコンスタントを前記ファンクショナルユニットインプットに接続するために前結合時において定義される部分的かつリコンフィギュラブルリードクロスバーと、
ファンクショナルユニットアウトプットをシステムアウトプットまたはメモリデータインプットポートを接続するために前合成時において定義される部分的かつリコンフィギュラブル書き込みクロスバーと、
制御、ステータスおよびコンフィギュレーションレジストリを有するレジスタファイルとを備え、前記コンフィギュレーションレジスタはリコンフィギュラブルファンクショナルユニット、リコンフィギュラブルアドレス生成ブロック、部分的かつリコンフィギュラブルコネクションクロスバーのコンフィギュレーションを保存し、前記データおよびアドレス計算法に用いられるコンスタントを保存することを特徴とするアーキテクチャテンプレート。
【請求項２】
請求項１記載のアーキテクチャテンプレートにおいて、前記リコンフィギュラブルアドレス生成ブロックが、
アドレス生成を開始、停止および再開することにより、前記コプロセッサに実行を開始、停止および再開させる制御ユニットと、
設置メモリに格納されているインデックスアレイへのアドレスを適時生成するため、前記ファンクショナルユニットの機能を適時活性化するため、および、システムインプットおよびメモリ書き込みを適時要求するために用いられるイネイブルシグナルを生成するプラグラマブルタイミングユニットと、
複合アドレスシーケンスを生成するために接続されているプラグラマブルアキュムレータのリニアアレイと、
前記イネイブルシグナルを前記アレイにおける前記アキュムレータに接続し、かつ、前記システムインプットにおける外部データの読み取りを認める前複合時に定義される部分的かつリコンフィギュラブルイネイブルクロスバーと、
前結合時に定義され、アキュムレータアウトプットおよびコンフィギュレーションコンスタントを他のアキュムレータインプットに接続する部分的かつリコンフィギュラブルインプットクロスバーと、
前複合時に定義され、生成アドレスを形成するアキュムレータアウトプットおよび各イネイブルシグナルをメモリアドレスに接続する部分的かつリコンフィギュラブルアウトプットクロスバーと、
アドレスがメモリに格納されている場合、アドレスポートを格納するルーティングメモリデータポートとを備えていることを特徴とするアーキテクチャテンプレート。
【請求項３】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、前記プログラミングユニットが、
各ロウが周期において同じ遅れと、コプロセッサが実行可能なネステッドループの最大数を表わすコラムの数とを有することにより特徴付けられているイネイブルシグナルのグループを生成し、一のコラムにおけるすべてのカウンタが同じエンドリミットでプログラムされ、制御される前記ループの反復回数を決定するプラグラマブルカウンタのマトリクスと、
前記プログラムされたコラムの前記数を用いて所定のコンフィギュレーションにネステッドループの実際の数を決定するエンコーダと、
全体的な前記イネイブルシグナルを所定の最大遅れ以下で遅らせ、前記遅れがないイネイブルおよび現在のコンフィギュレーションにおける、前記アーキテクチャにおける最大許容遅れと相違しうる前記最大遅れを有する各イネイブルグループに対してプログラムされている遅れをもってアウトプットイネイブルシグナルを遅らせるディレイユニットとを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項４】
請求項３記載のプラグラマブルタイミングユニットにおいて、
前記プラグラマブルカウンタのマトリクスにより生成された前記イネイブルシグナルがデータストリームをお互いに遅らせ、かつ、ファンクショナルユニットにより異なる遅れをもって導入された前記データフローグラフにおける異なる潜在を補償させるのに用いられ、
前記プラグラマブルタイミングユニットが、データがインプットまたは格納されてから読み出されるまでの時間を計測し、イネイブルおよびデータが同等に遅れているファンクショナルユニットを通じて前記データを同行させ、データの書き込みからアウトプットまたは格納までの時間を計測することを特徴とするプラグラマブルタイミングユニット。
【請求項５】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記プラグラマブルアキュムレータが、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記インプットクロスバーを前記アキュムレータの開始値を定めるインプットシグナルと、
他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる、前記アキュムレータのインクリメント値を定めるインプットシグナルと、
前記アキュムレータの動作を可能とするイネイブルシグナルと、
前記開始値をリロードする再開イネイブルシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、他のアキュムレータまたはコンフィギュレーションコンスタントにより前記インプットクロスバーを介してドライブされうる前記アキュムレータのオフセット値を定めるインプットシグナルと、
前記アキュムレータが複合アキュムレータユニットである場合、前記アキュムレータのモジューロ値を定めるコンフィギュレーションレジスタと、
他のアキュムレータの前記生成アドレスまたは前記インプットとして用いられるアウトプット計算値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項６】
請求項１記載のアーキテクチャテンプレートにおいて、
前記コンフィギュレーション、ステータス／制御レジスタファイルが、
アドレスが付されうる、ランタイムにおけるファイングラニュラリティの部分的なレコンフィギュレーションを可能とするリード／ライトメモリがマップされたインターフェースと、
外部アシスタンスを案内または依頼するアウトプットリクエストシグナルとを有することを特徴とするアーキテクチャテンプレート。
【請求項７】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ファンクショナルユニットアレイに属する各ファンクショナルユニットが前記コプロセッサを停止させうるブレークシグナルを発することを特徴とするアーキテクチャテンプレート。
【請求項８】
請求項１記載のアーキテクチャテンプレートにおいて、
前記複合システムインプットはスレーブリクエスト／アクノリッジインターフェースであり、かつ、前記複合システムアウトプットはマスターリクエスト／アクノリッジインターフェースであることを特徴とするアーキテクチャテンプレート。
【請求項９】
請求項８記載のアーキテクチャテンプレートにおいて、
システムインプットリクエストまたはシステムアウトプットアクノリッジの欠落が、システムインプットからのデータ読み出しおよびシステムアウトプットへのデータ書き込みのうち一方または両方のために前記表現が実行される場合、コプロセッサを始動させることを特徴とするアーキテクチャテンプレート。
【請求項１０】
請求項２記載のリコンフィギュラブルアドレス生成ブロックにおいて、
前記制御ユニットが前記コプロセッサを機能化かつ非機能化し、最も外側のループインデックスがラップアラウンドしたときに終了し、前記コプロセッサのインプットデータ欠乏、アウトプットデータ過剰、または、ファンクショナルユニットが火をつける一もしくは複数の遮断状態を停止することを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１１】
請求項１記載のコプロセッサプログラミングツールにおいて、
前記コプロセッサの前記アーキテクチャ記述のコンパイラと、
慣用プロセッサ用のオリジナルプログラムにおいてタグが付されかつ上書きされ、かつ、慣用プログラミング言語のシンタックスに本質的に類似するシンタックスを用いる前記ネステッドループシーケンス用のパーサーと、
ネステッドループシーケンスのコード用の、前記コードを前記コプロセッサの特定コンフィギュレーションに変換するコンパイラとを有するコプロセッサプログラミングツールを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項１２】
請求項１記載のアーキテクチャ記述ファイルにおいて、
リコンフィギュラブルファンクショナルユニットの数およびタイプの記述と、
数、タイプ、データおよびアドレスの設置メモリの幅と、
リコンフィギュラブルアドレス生成ブロックの記述と、
リコンフィギュラブルリード／ライトクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１３】
請求項１２記載のアーキテクチャ記述ファイルにおいて、
プラグラマブルタイミングユニットブロックの記述と、
プラグラマブルアキュムレータの数およびタイプの記述と、
リコンフィギュラブルイネイブル、インプットおよびアウトプットクロスバーの記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１４】
請求項１３記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブルタイミングユニットの記述が、
グループに属するネステッドループの数の記述と、
生成されるイネイブルシグナルの異なる遅延バージョンの数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロック。
【請求項１５】
請求項１２記載のアーキテクチャ記述ファイルのコンフィギュレーション記述ファイルが、
ファンクショナルユニットのコンフィギュレーションのパラメータ／値による記述と、
前記設置メモリのコンフィギュレーションと、
アドレス生成ブロックのリコンフィギュラブルコンフィギュレーションの記述と、
読み取り／書き込みクロスバーのリコンフィギュラブルコンフィギュレーションの、ポートがファンクショナルユニットのインプットおよびアウトプットのうちいずれかに接続されていることから暗黙的に推察される読み取りまたは書き込みモードによる記述とを備えていることを特徴とするアーキテクチャ記述ファイル。
【請求項１６】
請求項１５記載のコンフィギュレーション記述ファイルにおいて、前記コンフィギュレーション記述ファイルにおける前記リコンフィギュラブルアドレス生成ブロックの前記コンフィギュレーションの前記記述が、
前記プラグラマブルタイミングユニットブロックのコンフィギュレーションの記述と、
各プラグラマブル累算器のコンフィギュレーションの記述と、
イネイブル、インプットおよびアウトプットクロスバーのコンフィギュレーションの記述とを備えていることを特徴とするコンフィギュレーション記述ファイル。
【請求項１７】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、前記プラグラマブルタイミングユニットコンフィギュレーションの記述が、
各ネステッドループの終端の記述と、
各機能化シグナルグループについて遅延サイクル数の記述とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１８】
請求項１６記載のリコンフィギュラブルアドレス生成ブロックの記述において、
前記プラグラマブル計算機の記述が、
コンフィギュレーションコンスタントに接続された場合における開始および繰り上げ値と、
前記累算器が複合累算器ユニットであり、オフセットインプットがコンフィギュレーションに接続されている場合におけるオフセット値と、
前記累算器が複合累算器ユニットである場合におけるモジューロ値とを備えていることを特徴とするリコンフィギュラブルアドレス生成ブロックの記述。
【請求項１９】
請求項１１記載のコプロセッサプログラミングツールにおいて、
ネステッドループボディにおける計算および論理表現を解剖して完全なシステムグラフを得るファンクションと、
アーキテクチャを順番に表現するアーキテクチャを表わすハードウェアにマップされるシステムグラフのノードの当該順番のリスト生成するファンクションと、
請求項１３記載の前記アーキテクチャ記述ファイルを解剖するとともにハードウェアグラフを創出するファンクションと、
前記システムグラフの各ノードを反復的に前記ハードウェアグラフのノードにマップするファンクションとを備えていることを特徴とするコプロセッサプログラミングツール。
【請求項２０】
請求項１９記載のコプロセッサプログラミングツールにおいて、
前記システムグラフがコンフィギュレーションサブグラフのシーケンスを備え、各コンフィギュレーショングラフがネステッドグループに対応していることを特徴とするコプロセッサプログラミングツール。
【請求項２１】
請求項２０記載のシステムグラフにおいて、
各コンフィギュレーションサブグラフが、データフローサブグラフと、アドレスフローサブグラフとを備えていることを特徴とするシステムグラフ。
【請求項２２】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記データフローサブグラフが、
メモリノード（データアウトプットポート）、システムデータインプットノードおよびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（データインプットポート）およびシステムデータアウトプットノードを含むシンクノードと、
ファンクショナルユニットノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２３】
請求項２１記載のコンフィギュレーショングラフにおいて、
前記アドレスフローサブグラフが、
メモリノード（データアウトプットポート）、タイミングユニットノード（イネイブルシグナルアウトプットポート）およびコンフィギュレーションコンスタントノード含むソースノードと、
メモリノード（アドレスインプットポート）およびシステムデータインプットノード（アクノリッジシグナル）を含むシンクノードと、
アキュムレータノードを含む中間ノードとを備えていることを特徴とするコンフィギュレーショングラフ。
【請求項２４】
請求項１記載のアーキテクチャテンプレートにおいて、
前記ネステッドループボディにおける各データ表現が、変数、アレイまたはコンフィギュレーションコンスタントを含む論理および計算表現への変数またはアレイの割り当てにより構成されていることを特徴とするアーキテクチャテンプレート。
【請求項２５】
請求項２３記載のデータ表現において、前記データ表現において、各アレイのインデックスが（（ａｌｐｈａ＊ｉ＋ｂｅｔａ）÷ｇａｍｍａ）＋ｄｅｌｔａの形であり、ここでｉはループ変数であり、ａｌｐｈａ、ｂｅｔａ、ｇａｍｍａおよびｄｅｌｔａはｉ以内のループ変数を用いた同じ形式表現により再帰的に定義されうることを特徴とするデータ表現。
【請求項２６】
請求項１９記載のコプロセッサプログラミングツールにおいて、
システムグラフにおけるノードをハードウェアグラフのノードに再帰的にマップするファンクションは、所定のシステムノードにマップされうるすべてのハードウェアノード候補のリストを作成し、前記システムノードを各ハードウェアノード候補に試験的にマップして回帰的にリストにおける次のシステムノードのマップを試行し、成功した場合には現在のマッピングを維持して正（ｔｒｕｅ）を返し、失敗した場合には次のハードウェアノードを試行し、すべての候補の試行が失敗した場合には誤（ｆａｌｓｅ）を返すことにより実行されることを特徴とするコプロセッサプログラミングツール。
【請求項２７】
請求項１記載のアーキテクチャテンプレートにおいて、
メモリデータポートの数以下のメモリアクセスが平行かつ１サイクルで実行され、すべてのファンクショナルユニット平行かつ１サイクルで結果を生成しうることを特徴とするアーキテクチャテンプレート。
【請求項２８】
請求項１記載のアーキテクチャテンプレートにおいて、
クロック周期が増えるのを回避するためにコネクションクロスバーにおける希薄なリンクを維持しながらファンクショナルユニットおよび設置メモリの数を増やすことにより前記システムの動作がスケールされうることを特徴とするアーキテクチャテンプレート。
【請求項２９】
請求項１記載のアーキテクチャテンプレートにおいて、
結論コプロセッサが同位相でまたは位相が異なるファーストインファーストアウトメモリを用いて接続され、全体的に異なる位相で局所的に同位相のシステムを形成することを特徴とするアーキテクチャテンプレート。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータアーキテクチャに関し、特に、アルゴリズムにおけるネステッドループの加速に関する。
【背景技術】
【０００２】
計算機器はユビキタスになり、携帯電話、パーソナルディジタル機器および携帯型オーディオプレイヤーなど多くの電子機器が人々により日常生活において持ち運ばれる製品となっている。
【０００３】
これらの製品はフォンノイマンのアーキテクチャとして知られているコンピューティングパラダイムにしたがう内蔵プロセッサにより実現されてきた。内蔵機器が複雑になればなるほどより速いクロック周波数を必要とし、かつ、より多くのパワーを消費するようになってきた。これは従来型プロセッサが指示を連続的に実行し、かつ、データを連続的に取り出すからである。バッテリを電源とする機器についてフォンノイマンコンピューティングパラダイムは維持されえず、代わりになるものが見出されなくてはならない。
【０００４】
最近、より平行なアーキテクチャへの大きな関心が、マルチメディアおよびコミュニケーションアルゴリズムの強い計算ニーズに向けられている。アプリケーション専用集積回路（ＡＳＩＣｓ）が、アルゴリズムの重要部分において並行に実行される処理の数を増加させるのに用いられており、クロック周波数の増大を回避し、その結果としてエネルギー消費を実用的な限度内に維持している。しかし、ＡＳＩＣｓは開発時間が長く、一度組み立てられると変更されえない。これでは非常に速く変化するマーケットの動きおよび最近の電子機器の短いライフ期間には合致しえない。
【０００５】
プログラマブル手法は実際にはより理想的であり、これがテクノロジーおよびリコンフィギュラブルコンピューティングが実現された経緯である。リコンフィギュラブルコンピュータはコンフィギュレーションメモリのコンテンツを変更することにより、ポストシリコン時においてアーキテクチャが変更されうるマシーンである。リコンフィギュラブルコンピュータの不可欠な要素はプログラマブルマルチプレクサである（図１）。プログラマブルマルチプレクサはインプットＡおよびＢと、アウトプットＣと、Ｓビットのコンフィギュレーションとを有する。Ｓが０に設定された場合、ＡからＣへの経路が生成される。Ｓが１に設定された場合、ＢからＣへの経路が生成される。プログラマブルマルチプレクサを十分に保有することにより、異なるアルゴリズムをより適当に実行するために異なるハードウェアアーキテクチャを迅速に生成するように、機能ユニットおよびメモリ要素を思い通りに接続させることができる。本発明はリコンフィギュラブルアーキテクチャのクラスを得るためのテンプレートである。
【０００６】
存在するリコンフィギュラブルアーキテクチャは（１）ファイングレインアレイおよび（２）コースグレインアレイの２つに分類される。
【０００７】
ファイングレインアレイはフィールドプログラマブルゲートアレイ（ＦＰＧＡｓ）の形成における広く拡散したポピュラリティを獲得した。ＦＰＧＡはプログラマブルスイッチの大きなネットワークにより接続された狭いビットスライスに対して論理機能を実行する小さなプログラマブル機能ユニットの大きなアレイである。機能ユニットは本質的にプログラマブルルックアップテーブル（ＬＵＴｓ）であり、スイッチのネットワークは前述のプログラマブルマルチプレクサからなる。商業的なＦＰＧＡ機器はさまざまなメーカーにより製品化されている。ＦＰＧＡｓは電子プログラミングにより要求される回路の生成を許容するにもかかわらず、ＬＵＴｓの豊富なアレイおよびルーティングスイッチは巨大なエリアおよびパワーの不利益を表わしている。専念ハードウェアにおいて実施されている同じ回路におけるエネルギー欠乏は非常に小さくかつ少なくなる。したがって、バッテリ運転機器におけるＦＰＧＡｓの使用はルールというよりもむしろ排除されてきた。
【０００８】
ＦＰＧＡｓは、必要とされる巨大回路エリアを軽減しかつパフォーマンスを改善するため、標準的なプロセッサ、ならびに、マルチプライヤおよび設置されているＲＡＭｓのような特定ブロックに結合されている。このように、アルゴリズムの特定および重要部分の多くがリコンフィギュラブルファブリックに対して実行され、その一方、その他のわずかな重要部分がプロセッサにより実行される。このようなハイブリッドアーキテクチャの例が研究者により提案され（非特許文献４，１６，１１参照）、かつ、ＦＰＧＡの取引業者により市場に導入された。しかし、これらの回路はいまだシリコンエリアの意味で無駄が多く、かつ、クロック周波数およびコンフィギュレーション時間の意味で遅い。
【０００９】
コースグレインアレイは柔軟性および汎用性を犠牲にすることでファイングレインアレイの前記のような制限を克服する。コースグレインアレイは最近の研究対象とされ、きわめてわずかのアーキテクチャが研究者により提案され（非特許文献３，６，１２，５，７，８，１０，９，１３，２，１４，１７参照）、かつ、会社が設立された（非特許文献１８，１９参照）。これらのアレイは高いグラニュラリティの機能ユニットおよび少ない複合接続ネットワークを有し、マルチメディアおよびコミュニケーションのような目標とするＤＳＰアプリケーションを改善する。機能ユニットは通常は２〜３バイトのスライスよりもむしろ２〜３バイトで計算および論理処理を実行する。結果は汎用的ではないもののわずかなコンフィギュレーションデータを必要とする非常にコンパクトかつ高速のリコンフィギュラブルシステムとなり、このシステムは実行時間において機敏かつ部分的に交換されうる。
【００１０】
他の重要な視点はリコンフィギュラブルユニットがどのように内蔵マイクロプロセッサに接続されているかということである。当初、再構築はプロセッサファンクショナルユニットレベルで始まり、かつ、特別な指示により誘起された（非特許文献１５，１２，１参照）。その後、リコンフィギュラブルユニットはプロセッサに緊密に接続されたコプロセッサになり、かつ、動作するためになおも特別な指示を必要とする（非特許文献４，１６，３，６，１２参照）。より最近では、システムバスに取り付けられ、かつ、ホストプロセッサ指示セットの延長を必要としないコプロセッサが主要な研究対象となってきている（非特許文献２，７，１７参照）。われわれの仕事は最後のカテゴリに合致している。
【非特許文献１】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;
}
【００８２】
前記擬似コードにしたがってＳＧノードをＨＧノードにマッピングする際における最初の事項はグラフのノードのすぐ次のノードを取得することである。アルゴリズムがグラフシンクからグラフソースに進行するのでこれらのノードはすでにＨＧノードにマップされている。次のＨＧノードから作業は、ＳＧに対応する通常のすぐ先のＨＧノードのリストを計算し、未使用の乗算器により到達されうる。これは質問されているノードにマップされうる、可能性があるＨＧノードのリストである。このリストにおけるノードは適切な候補を見つけるために検索される。第１に候補ＨＧノードは加算器、乗算器、メモリ等のノードと同じタイプでなくてはならない。第２にノードは使用されていてはならない。これらのテストのうち一方が満たされていない場合、処理は失敗となる。これらのチェックが実行されると、ＨＧノードはその次のＨＧノードに伝送される。すなわち、次のＨＧノードのインプット乗算器が当該ノードを受け取るように設定される。もしこれがマップ対象となる最期のノードである場合、処理は成功となる。そうでない場合、マップ処理はＳＧの次のノードに反復的に適用される。もし成功すれば処理は成功となる。そうでない場合、これは次のノードのマッピングが現在または先のノードの現在のマッピングにより達成されなかったことを意味する。この場合、次のノードへの伝送は行われず次の候補ＨＧノードが試行される。すべての候補ノードへの試行が失敗した後、処理は失敗となる。
【００８３】
本発明により創出されたリコンフィギュラブルある実験用コプロセッサの適用例は次に示される。例はＭＰＥＧ１層ＩＩＩ（ＭＰ３）のデコーダーアルゴリズムである。アルゴリズムは（１）従来型プロセッサおよび（２）実験用コプロセッサにより加速された同一の従来型コプロセッサにおいて実行された。プロセッサは３２ビットで０．８１ＤＭＰＴＳの演算能力を有するハーバードアーキテクチャである。実験用コプロセッサは２つのネステッドループ、３２ビットデータ経路、２つの加算器および累算器、２つの乗算器および切替器、４キロバイトのＲＯＭおよび８キロバイトのＲＡＭをまとめた３つのデュアルポートメモリブロックにより生成された。
【００８４】
ＭＰ３のベンチマークのセットの実行から得られた実験結果が表１に示されている。従来型プロセッサにおけるアルゴリズムの最初のプロファイリングから、われわれは２つの過程（多相合成および逆改良型離散コサイン変換（ＩＭＤＣＴ））が時間の９５％を費やすことを発見した。このため、コプロセッサにおいて当該過程を加速した場合、加速に対するポテンシャルは２０である。多相合成過程は平均で１８．７倍加速された。ＩＭＤＴＣ過程は平均で４３．９倍加速された。これはアルゴリズムを全体的に１１．９倍加速する。プロセッサおよびコプロセッサにより形成された完全なシステムのプロファイリングは主要な処理に対する演算処理負荷配分のバランスに優れている。完全なシステムにおいて多層合成およびＩＭＤＴＳ過程は、加速前の演算処理負荷が９５％であるのに対して演算処理負荷が３４％であった。
【００８５】
【表１】
2010044731.tif 000003
【００８６】
本実施例ではコプロセッサインスタンスの追加の結果としてシリコンエリアは２倍になった。演算処理能力は１２倍に上昇し、このことはプロセッサ−コプロセッサシステムが演算処理能力を同じレベルに維持しながら、おおよそ６倍もの消費電力が節約されたことを意味する。
【００８７】
前記リコンフィギュラブルコプロセッサアーキテクチャテンプレートが単に本発明の原則を記述しているにしか過ぎないことはいうまでもない。前記アーキテクチャの変更または改良は本発明の原則から外れない範囲で可能である。すべての変更または改良は本発明の本発明の技術的範囲に属し、特許請求の範囲により保護されなくてはならない。
【図面の簡単な説明】
【００８８】
【図１】プログラマブルマルチプレクサ
【図２】コプロセッサアーキテクチャテンプレートの上面図
【図３】アドレス生成ユニットのアーキテクチャ
【図４】タイミングユニットマトリックス
【図５】ディレイユニット
【図６】基礎累算器ユニット
【図７】複合累算器ユニット
【図８】許可クロスバーにおける許可および再開イネイブルシグナル累算器の選択
【図９】インプットクロスバーにおける各許可ユニット用のスタート、インクリメントおよびオフセットシグナルの選択
【図１０】アウトプットクロスバーにおける累算器カウントシグナルからのメモリポートアドレスの選択
【図１１】機能ユニット用のシグナルの選択
【図１２】システムアウトプットおよびメモリインプットの選択
【図１３】制御コンフィギュレーション、データインおよびデータアウトインターフェース
【図１４】制御レジスタ
【図１５】ステータスレジスタ
【図１６】制御回路
【図１７】機能ユニットから発せられたブレーク状態の選択
【図１８】Ｉ／Ｏ依存ユニットの許可の選択
【図１９】コプロセッサプログラミングフロー
【図２０】データフローグラフの一例
【図２１】アドレスフローグラフの一例
【図１】
2010044731.tif 000004
【図２】
2010044731.tif 000005
【図３】
2010044731.tif 000006
【図４】
2010044731.tif 000007
【図５】
2010044731.tif 000008
【図６】
2010044731.tif 000009
【図７】
2010044731.tif 000010
【図８】
2010044731.tif 000011
【図９】
2010044731.tif 000012
【図１０】
2010044731.tif 000013
【図１１】
2010044731.tif 000014
【図１２】
2010044731.tif 000015
【図１３】
2010044731.tif 000016
【図１４】
2010044731.tif 000017
【図１５】
2010044731.tif 000018
【図１６】
2010044731.tif 000019
【図１７】
2010044731.tif 000020
【図１８】
2010044731.tif 000021
【図１９】
2010044731.tif 000022
【図２０】
2010044731.tif 000023
【図２１】
2010044731.tif 000024
【外国語明細書】
【発明の名称】RECONFIGURABLE COPROCESSOR ARCHITECTURE TEMPLATE FOR NESTED LOOPS AND PROGRAMMING TOOLS 
【技術分野】 
This invention relates in general to computer architecture and in particular to acceleration of nested loops in algorithms.
【背景技術】 
Computing devices are becoming ubiquitous and many electronic devices can now be found amongst the objects carried by people in their everyday life: mobile phones, personal digital assistants, portable audio players.
These objects have been enabled by embedded processors which follow the same computing paradigm known as von Neumann’s architecture. As embedded devices become more complex they require faster and faster clock frequencies and consume more and more power. This is because conventional processors execute instructions sequentially and fetch data also sequentially. For battery powered devices the von Neumann computing paradigm cannot be sustained and alternatives must be found.
Recently there has been great interest in more parallel architectures to face the demanding computational needs of multimedia and communications algorithms. Application specific integrated circuits (ASICs) have been used to increase the number of operations done in parallel in critical parts of the algorithms, thus avoiding increasing the clock frequency and therefore keeping the energy consumption within practical limits. However, ASICs have long development times, and once fabricated they cannot be changed. This is incompatible with fast changing market dynamics and the short lifespan of modern electronics.
Programmable solutions are in effect more desirable and this is how the technology of Reconfigurable Computing came into existence. A reconfigurable computer is a machine whose architecture can be changed at post-silicon time by changing the contents of configuration memories. The essential element of a reconfigurable computer is a programmable multiplexer (Fig. 1). The programmable multiplexer has inputs A and B, an output C and a configuration bit S. If S is set to 0 a path is created from A to C; if S is set to 1 apath is created from B to C. Having enough programmable multiplexers enables functional units and memory elements to be interconnected at will, creating different hardware architectures on-the-fly, for better executing different algorithms. The present invention is a template for deriving a class of reconfigurable architectures.
Existing reconfigurable architectures can be divided in two main kinds: (1) fine-grained arrays and (2) coarse-grain arrays.
Fine-grain arrays have gained widespread popularity in the form of Field Programmable Gate Arrays (FPGAs). An FPGA is a large array of small programmable functional units for performing logic functions on narrow bit slices interconnected by a large network of programmable switches. The functional units are essentially programmable Look-Up-Tables (LUTs) and the network of switches consists of the programmable multiplexers described above. Commercial FPGA devices are available through companies like Xilinx, Altera, Actel, Lattice, etc. Although FPGAs enable creating circuits on demand by electrical programming, the rich array of LUTs and routing switches represent a huge area and power penalty: the same circuits implemented in dedicated hardware would be much smaller and less energy hungry. Therefore, the use of FPGAs in battery operated devices has been the exception rather than the rule. 
FPGAs have been combined with standard processors and specific blocks such as multipliers and embedded RAMs in order to mitigate the huge circuit areas required and improve performance. In this way, only the more specific and critical parts of the algorithms are run on the reconfigurable fabric, whereas other less critical parts are run on the embedded processors. Examples of such hybrid architectures have been proposed by some researchers [4-16-11] and introduced in the market by FPGA vendors. However, these circuits are still wasteful in terms of silicon area and slow in terms of clock frequencies and configuration times.
Coarse-grain arrays overcome the mentioned limitations of fine-grain arrays at the cost of reduced flexibility and generality. Coarse-grain arrays have been the object of recent research with quite a few architectures being proposed by researchers [3 - 6 - 12 - 5 - 7 - 8 - 10 - 9 - 13 - 2 - 14 - 17] and startup companies [18 - 19]. These arrays have functional units of higher granularity and less complex interconnection networks to better target DSP applications such as multimedia and communications. The functional units normally perform arithmetic and logic operations on words of a few bytes rather than on slices of a few bits. The result is a less general but much more compact and faster reconfigurable system, requiring small amounts of configuration data, which can be agilely and partially swapped at run time.
Another important aspect is how reconfigurable units are coupled with embedded microprocessors. Initially reconfiguration began at the processor functional unit level, and was triggered by special instructions [15 - 12 - 1]. Later, reconfigurable units became coprocessors tightly coupled with processors and still requiring special instructions in order to work [4 - 16 - 3 - 6 - 12]. More recently, coprocessors attached to system busses and requiring no extensions of the host processor instruction set have become a major research topic [2 - 7 - 17]. Our work fits into the latest category.
The work in [2] presents a self-timed asynchronous data-driven implementation, which, given the difficulties of the timing scheme adopted, needed a full custom silicon implementation, somewhat impractical to use in a standard cell based technology. The architecture features two address generation processors, which run microcode instructions to create the needed sequence of memory addresses.
The architecture in [7] uses undifferentiated 8-bit functional units, including LUT-based multipliers, which are difficult to scale to 16-bit or 32-bit data words used in most multimedia and communications applications. The hierarchical interconnection scheme is structured enough to facilitate compilation. However, this work represents a single architecture design rather than an architecture template adaptable and scalable for various applications.
The work closest to ours is the one described in [17]: an architecture template consisting of an array of coarse-grain functional units interconnected to a set of embedded memories and address generation modules. The address generation modules are implemented with cascaded counters which feed a series of arithmetic and logic units (ALUs) and multipliers for the generation of complex address sequences. A set of delay lines synchronize the control of functional units and memory operations. 
In our approach the address generation blocks are implemented with programmable accumulators, reducing the complexity of the hardware compared to using ALUs and multipliers. Instead of multiplying delay lines for synchronization, we use a single delay line and multiple counters with programmable wrap around times to generate groups of enable signals with different delays. In this way, the generation of some addresses can be delayed relatively to others, enabling the execution of loop bodies expressed by unbalanced pipeline graphs. The enable signals accompany the data signals through each functional unit, so they arrive with the needed delay at the next functional unit.
Our approach explicitly structures the interconnection networks (partial crossbars) to facilitate the operation of our programming tool. In fact the architecture template and the programming tool have been co-designed to avoid creating hardware structures whose programming is difficult or intractable to automate. 
We also consider data sources and data sinks which are not necessarily the data inputs and outputs of embedded processor. The origin and destination of the data may be any piece of hardware in the system, not necessarily synchronous to the system clock. For that purpose we provide an interface simpler than processor busses, and we use asynchronous FIFOs to connect the core to other cores running at a different clock speed. 
【課題を解決するための手段】 
The architectures derived from the proposed template are integrated in a generic System on Chip (SoC) and consist of reconfigurable coprocessors for executing nested program loops whose bodies are expressions of operations performed in a functional unit array. The functional units must be able to perform the atomic operations indicated in the expressions. The data arrays are accessed in parallel from one or more system inputs and from an embedded memory array. The processed data arrays are sent back to the memory array or to system outputs.
The architectures enable the acceleration of nested loops compared to execution on a standard processor, where only one operation or datum access can be performed at a time. The invention can be used in a number of applications especially those which involve digital signal processing such as multimedia and communications. The architectures are used preferably in conjunction with von Neumann processors which are better at implementing control flow. The architectures feature an addresses generation block able to create complex sequences of addresses. The configuration register file store the information for programming the data path and the address generation block. The configuration register file is addressable, so the system can be partially and runtime reconfigurable.
The architectures loop for the programmed number of iterations or until some conditions pre-programmed in the functional units are flagged. Initialization is done using a control register, polling is possible using a status register and requests are served upon assertion of a request signal. 
The architectures can be scaled easily in the number of data stream inputs, outputs, embedded memories, functional units and configuration registers.
We envision computational systems entailing several general purpose processors and several coprocessors derived from the proposed architectural template. The processors and coprocessors are connected either synchronously or using asynchronous first in first out memories (FIFOs), forming a globally asynchronous locally synchronous system. 
Each coprocessor is programmed by tagging and rewriting the nested loops in the original processor code. The programming tool produces a coprocessor configuration per each nested loop group, which is automatically replaced in the original code with coprocessor input/output operations and control.
The available hardware in the coprocessor is modeled as a hardware graph. The expressions in loop bodies are modeled as data flow graphs. The source nodes of the data flow graph are memory outputs or system inputs and the sink nodes are memory inputs or system outputs. The expressions in the array addresses are modeled as address flow graphs. The address flow graphs continue the data flow graphs from memory ports, through address generation nodes, finally to timing nodes, forming a complete system graph.
The timing information for the generation of addresses can be extracted from the system graph. The timing information is sent along with the data in the form of enable signals, and used to synchronize the functional units.
The system graph is traversed from sinks to sources, in order to map the data flow and address flow graphs to the hardware graph, where the resources used are marked. Whenever there are multiple programmable multiplexer selections which result in different hardware resources being allocated to implement the intended flow, a decision is taken on what to try next. If after a decision the mapping becomes impossible the latest hardware mapping is undone. If there are alternative decisions, another decision is tried. If there are no more alternative decisions the previous decision is undone. This process continues until a mapping solution is found or the impossibility of mapping is proven. This procedure is exhaustive and complete.
【図の簡単な説明】
【図１】 
Figure 1. Programmable multiplexer
【図２】
Figure 2. Top level view of the coprocessor architecture template
【図３】
Figure 3. Architecture of the address generation unit
【図４】
Figure 4. Timing unit matrix
【図５】
Figure 5. Delay unit
【図６】
Figure 6. Basic accumulator unit
【図７】 
Figure 7. Complex accumulator unit
【図８】 
Figure 8. Selection of the accumulator Enable and Restart Enable signals in the Enable Crossbar
【図９】 
Figure 9.  Selection of the Start, Increment and Offset signals for each accumulator unit in the Input Crossbar
【図１０】 
Figure 10. Selection of the memory port address from the accumulator Count signals in the Output Crossbar
【図１１】 
Figure 11. Selection of the signals for functional unit inputs
【図１２】 
Figure 12. Selection of system outputs and memory inputs
【図１３】 
Figure 13. Control/configuration, data in and data out interfaces
【図１４】 
Figure 14. Control register
【図１５】
Figure 15. Status Register
【図１６】
Figure 16. Control circuit
【図１７】
Figure 17. Selection of break conditions issued by functional units
【図１８】
Figure 18. Selection of the I/O dependent system enable
【図１９】
Figure 19. Coprocessor programming flow
【図２０】
Figure 20. Data flow gaph example
【図２１】
Figure 21. Addresses flow graph example
【発明を実施するための最良の形態】 
A) Nested Loops 
The coprocessors derived from the proposed architecture template are capable of manipulating n-bit data words. We distinguish between
・Constants: single data words read from a configuration register file 
・Variables: single data words read from functional unit outputs 
・Arrays: collection of data words read from memories
The architectures are capable of executing one or more consecutive nested loop groups according to the following meta-language definitions:
{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
B) Architecture
The top-level view of the proposed architecture template is shown in Fig. 2. It basically consists of an array of functional units (FUs) and an array of embedded memories (EMs).
The data processed by the FUs are sourced from the EMs, system inputs or outputs of other FUs by the Read Crossbar. Each FU produces a single data output, but it may also produce some flags as a secondary output. These flags are routed by the Read Crossbar to other FUs where they are used as control inputs. The data processed by the FUs is written back to the EMsor sent out to system outputs using routes defined by the Write Crossbar. 
The addresses of the memories come from the Address Generator. Since the memory bandwidth is crucial for the performance of this system, in Fig. 2 all embedded memories are shown as dual port memories. Single port memories could also be used.
A configuration register file holds a set of registers containing data that define the configuration of programmable FUs, read and write crossbars, and address generation blocks. It also stores some constants used in the computation of addresses and data. The configuration register file is accessed through a configuration interface which is also used for accessing control and status registers. The configuration register file is addressable, so the system can be partially and runtime reconfigurable.
The address generation block can be seen in Fig. 3. Its architecture resembles the top level view of the architecture itself, that is, it is like a smaller reconfigurable processor inside the reconfigurable processor. Instead of the FU array there is an Accumulator Array (AA), and the Read and Write crossbars appear as the Input Crossbar and Output Crossbar, respectively.
The AA contains a collection of special accumulators which are enabled by signals coming from the Timing Unit. Some accumulators produce addresses which are routed to the memory ports by the Output Crossbar. The Output Crossbar also routes addresses stored in certain memories to be used as addresses of other memories. This provides for extreme flexibility in the generation of addresses at the expense of memory space. Other accumulators produce intermediate values which are fed back into the AA itself. The Input Crossbar provides for the feeding back of the intermediate values and routes constants from configuration register to the accumulators, in order to generate complex address sequences.
The addresses are functions of the nested loop indices. The Timing Unit generates groups of signals for enabling the AA. The enable signals are routed to the AA by the Enable Crossbar. The Enable Cross bar also routes enable signals to the system inputs to time and synchronize the admission of external data. The enables of the accumulators accompany the generated address to its memory port; in case of a read port the enable signals accompany the data read from the memory through the FUs. In the FUs the enable signals are delayed by the same amount as the data so that enables and data remain synchronous.
The control block shown in Fig. 3 is responsible for responding to user commands to initialize, start and poll the coprocessor. It also stalls the coprocessor in case some condition is detected in the functional units, or in case the system inputs are data starving or the outputs are overflowed.
The loop indices advance by unit increments as given above in the nested loop syntax. Each nested loop group uses a group of indices implemented in the Timing Unit using cascaded counters where the end count value is programmed.
The Timing Unit is shown in Fig. 4. The programmable counters are interconnected in a matrix where the first row implements enable signals for the loop indices i, j and k. The subsequent rows produce delayed versions of the loop indices. The last row always contains the most delayed version of the loop indices. The first counter represents index i and is incremented at every clock cycle. When a counter reaches the end value it wraps around and pulses the output signal to advance the next outer counter by one. When the final counter reaches the end the outmost loop finishes and the nested loop group is done. A priority encoder identifies the outmost loop (end_sel) from the non null end count values programmed in the cascaded counters. This information will indicate which counter column terminates the processing and will be used in the control block.
The circuit to delay the basic index i enable by programmable values is shown in Fig. 5. Each flip-flop D delays the i_en(t) signal by one cycle. Programmable multiplexers select the delay wanted. If there is a break condition (see below) the state of the delay unit is frozen by disabling the flip-flops and masking the output enables. If there are P memory ports in the system at most P different delayed versions of the enables are needed. In practice a lower number of delayed versions may be implemented.
Since real addresses do not advance necessarily by increments of one, the accumulator units shown in Fig. 6 and Fig. 7 are responsible for generating more complex address sequences of the form given by address_expressionas above.
The Basic Accumulator Unit (BAU) shown in Fig. 6 initializes to the value specified by the START input after the RESTART_EN signal is pulsed, and accumulates the values specified by the INCR input. The accumulator current and next outputs are given by signals CNT and CNT_NXT, respectively.
The Complex Accumulator unit shown in Fig. 7 adds the following functionality to the BAU: the accumulations are done in modulo specified by the configuration input MODULO, and added to the value specified by the OFFSET input signal.
Each accumulator selects its EN and RESTART_EN signals from the Enable Crossbar, which is driven by the enable signal groups produced in the Timing Unit. As shown in Fig. 8, first the enable group (delayed version) is selected and then the enable signals for EN and RESTART_EN are selected from within the selected group. A similar scheme is used to select the enable signals used to acknowledge the admission of external data in the system. In this way the input of external data can be timed and synchronized.
Fig. 9 illustrates the selection of the accumulator inputs from the Input Crossbar. The START, OFFSET and INCR signals can be chosen either from constants stored in the configuration registers or from the CNT and CNT_NXT signals produced by other accumulators.
Fig. 10 illustrates the selection of memory port addresses in the Output Crossbar. The CNT signals produced by the accumulators or data read from memories can be chosen to form the addresses of memory ports. The EN and RESTART_EN signals of the accumulators follow the produced addresses to the memory ports. If the memory port is a read port the enables accompany the data read to the functional units, or, if the data read is to be used as an address, the enables follow the data back to the Output Crossbar. If the memory port is a write port the EN and RESTART_EN signals are ignored.
Fig. 11 shows the selection of inputs for functional units by means of the Read Crossbar. Inputs can come from system inputs, memory output ports, or from the outputs of other functional units. This architecture template considers that any functional unit must have a special input responsible for passing the enable signals through to the next functional unit and delaying them the same number of latency cycles as the functional unit itself. In this way the enable signals are preserved and kept near the data they refer to. Functional units may be configured to route the input RESTART_EN signal to the output EN signal while losing the EN signal of the input, which ceases to be relevant from that functional unit on. The usefulness of doing so will be apparent later.
Fig. 12 shows the selection of system outputs and memory inputs in the Write Crossbar. These are selected from functional unit outputs. Note that the enables accompany the data and are to be used as memory write enables or output request signals.
The control/configuration, data in and data out interfaces are shown in Fig. 13. 
The control/configuration interface has a Request_in input signal to indicate it is being selected and to validate the Addressinput vector, which is used to select internal registers. The Write/not Read signal chooses the intended action. The data is written to ctr_data_inports and read from the ctr_data_outport. The Request_out signal flags events such as the end of processing or that some condition has been detected and the coprocessor has been halted.
The data in interface has a Req_in input signal vector. Each element Req_in[i] indicates that the data in interface i is being selected and validates the Data_in[i] vector containing the input data. The Ack_in[i] signal is used to tell the core driving interface I that the request Req_in[i] to read Data_in[i] has been accepted and executed. The Ack_in[i] signal comes from the Address Generator block, where it is selected by the Enable Crossbar.
The data out interface has a Req_out output signal vector. Each element Req_out[i] indicates that the data out interface i is being selected and validates the Data_out[i]vector containing the output data. Upon accepting the data sent out by this interface an acknowledge signal Ack_out[i]must be asserted from the outside or otherwise the coprocessor will stall to prevent data loss. From an external point of view, Ack-_out[i] should always be asserted unless it was impossible to accept the data from the last request.
Fig. 14 shows a basic control register for the architectures. It contains three bits: the Init bit to initialize the coprocessor, the Enbit to enable the coprocessor and the Req_en enable control requests from the co-processor by means of signal Request_out.
Fig. 15 shows a basic status register. It contains a single Busybit to permit polling of the co-processor.
A basic control unit is shown in Fig. 16. The coprocessor is enabled whenever the control bit En and the I/O enable bit are asserted, and remains enables until either the END(t)or the break signals remains unasserted. Whenever these signals pulse, a logic ‘1’ is caught in a flip-flop, which disables the coprocessor. An enabled co-processor has the innermost loop index active by asserting signal i_en(t), which in turn enables the outer loop indices and all the delayed versions of the enable groups. 
If control output requests are enabled (Req_en = ‘1’) then the Request_out signal is asserted when either the breaksignal or the most delayed END(t-DP) pulses.  
The END(t)and END(t-DP) signals are the wrap around signals of the outmost loop; a multiplexer uses signal end_sel explained in Fig. 4 to choose the index enable from signals i_en, j_en, or k_en, both the delay free and the delayed by DP cycles versions.
The Busysignal of the status register is generated as shown in Fig. 16. The coprocessor is busy if it is either enabled, with i_en(t) active, or has not finished the processing, i.e., END(t-DP)or break have not been asserted.
The breaksignal is used to disable the generation of loop index enables in the Delay Unit (Fig. 4). It is basically a registered inverted and one cycle delayed version of the break signal.
The selection of break conditions from functional units is illustrated in Fig. 17. For scalability reasons each functional i unit can only produce a single break condition signal cond_i. Internally, functional unit i may be programmed to fire the break condition for various reasons. However, from an external perspective, there is a single break signal per functional unit. A configuration bit cond_i_en tells whether break condition cond_i is enabled.
The selection of I/O dependent system enables is shown in Fig. 18. If the loop body expressions involve a system input i, then the co-processor can only be enabled if there is data available at that input, which is signaled by the Req_in_i signal. Similarly, if the results of the loop body expressions are being sent to system output j, then the co-processor can only be enabled if the data sent out is actually being read by another system, which is signaled by the Ack_out_j signal. When this signal is asserted it means that the data sent in the last cycle has been read. When asserted, configuration bits no_in_i and no_out_j indicate that system input i and system output j are not present in the loop body expressions, and therefore cannot disable the system.
C) Programming Tool
The coprocessor programming flow is illustrated in Fig. 19. The user starts by writing the nested loop sequence code according to the syntax given above. The coprocessor programming tool inputs the nested loop sequence code and a description of the hardware architecture, and outputs the coprocessor configuration sequences in multiple formats: text file, software include file and configuration memory images in Hardware Description Language (HDL). The text file is human readable and is used to give feedback to the user. The software include file contains the configuration memory images of the sequence; it can be included in some program which will configure and run the coprocessor. The HDL configuration images are used in FPGA emulation, for fast system verification, or HDL simulation for detailed system verification. Additionally, a software model of the architecture is compiled from the hardware description files, which provides a compromise between the speed of FPGA emulation and the detail of HDL simulation. The results (output data) produced by the software, HDL and FPGA models are analyzed by the user and used to guide the refinement of the input nested loop code.
The hardware architecture is described in a file which references the functional units used. The description of the functional units is placed in the functional unit store. The syntax of the hardware description file should be equivalent to the one given below:
//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)})}
An example of an architecture description is the following: 
//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
The configuration description text file is written in syntax similar to the architecture description file but, instead of enumerating all possible sources for a destination, it specifies the selected source. In other words, it substitutes enumeration with exclusive disjunction. A description of a possible syntax follows:
{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))
The algorithm of the Coprocessor Programming Tool is outlined below.
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;)
}
The first step is there to analyze the expressions in the nested loop bodies and to create a complete system graph SG consisting of sub-graphs for each nested loop group. This is done by function parseNLSC (nested_loop_sequence_code). Each nested loop group gives rise to a configuration memory image. The sub-graph for each nested loop group has two parts: the data flow graph and the address flow graph.
The Data Flow Graph (DFG) has the following types of nodes:
Source nodes:
・Memory node (data output ports) 
・System data input node  
・Configuration constant node
Sink nodes:
・Memory node (data input ports) 
・System data output node
Intermediate nodes
・Functional unit node
The Address Flow Graph (AFG) has the following types of graphs:
Source nodes:
・Memory node (data output ports) 
・Timing unit node (enable signals output ports)  
・Configuration constant node
Sink nodes:
・Memory node (address input ports) 
・System data input node (acknowledge signals)
Intermediate nodes
・Accumulator unit node
The edges in the DFG and AFG are directed from source nodes to intermediate nodes, from intermediate nodes to other intermediate nodes, and from intermediate nodes to sink nodes.
The DFG and the AFG can be concatenated in a single configuration graph CG by merging the memory sink nodes of the AFG with the memory source nodes of the DFG. The complete system graph SG can be constructed by concatenating successive CGs. One CG is concatenated with the next CG by merging the memory sink nodes of the current CG with the memory source nodes of the next CG. This allows leaving data in the embedded memories that will be used in the next co-processor configuration. This mechanism can be called a conscious or intentional caching mechanism, which should perform better than conventional caches which exploit stochastic locality.
The following example shows a nested loop group for which a CG is derived.
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];
}
The DFG for the nested loop group in this example is shown in Fig. 20. As can be seen, the DFG follows the expression in the body of the nested loop group. Each node of the graph represents either an FU node or a memory node. Read, write or FU operations are pipelined and the latency for each operation is indicated in Fig. 20. The longest path in the graph, from memory reads a[v] or b[w] to memory write d[u] takes 9 cycles. The path from memory read c[x] to memory write d[u] takes 4 cycles. This means that memory read c[x] should be delayed 9-4=5 cycles relative to memory reads a[v] and b[w] and that memory write d[u] should be delayed 9-1=8 cycles relative to memory reads a[v] and b[w]. With the presented architecture template there are no delays in computing the addresses. Thus differences in latency come only from FUs with different number of pipeline stages. However, extending this methodology to the case where the computation of addresses is affected by latency is straightforward.
The AFG for computing the addresses u, v, w and x is shown in Fig. 21. The computation of addresses advances with the enable signals i_en and j_en generated by the Timing Unit. The addresses that need to be delayed D cycles use a delayed enable group with signals i_en(t-D) and j_en(t-D). Note that address u, v and x need only one BAU to be computed, whereas address w is more complex and needs a CAU fed by a BAU.
Concatenating the DFG and the AFG by merging homonym memory nodes u(t-8), v(t), w(t), and x(t-5) yields the CG for the nested loop group in this example. Had there been a sequence of nested loop groups, the respective CGs would be concatenated in a similar way to yield the complete SG. 
Having created SG, the nodes in this graph are ordered in a list, in a breadth first fashion, from the system output nodes towards the system input nodes. For the example given the order of nodes could be: d[u], +=, +, c[x], *, x(t-5),  a[v], b[w], v(t) and w(t). This is what the function createNodelist(SG) in the main algorithm flow does.
Next, function parseHW(architecture_description) creates a graph that describes the hardware by means of function. The hardware graph follows the architectural description given above. Some hardware nodes map to SG nodes: I/O, memory, functional unit, address accumulators, configuration constants, timing unit nodes; other hardware nodes have no correspondence to nodes in SG, but are useful for routing signals: memory port, crossbar multiplexer, functional unit port. The selections of paths all the way up from system outputs and memory inputs up to system inputs and memory outputs, passing through several levels of functional units, constitute the data for each configuration. Unfolding the hardware graph as many times as the number of configurations gives us the complete hardware graph HG, onto which SG is mapped.
The next step is to map the nodes in SG to nodes in HG. The recursive map procedure is outlined below.
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;
}
Following the pseudo-code above, the first thing to do when mapping an SG node to a HG node is to get the immediate descendant nodes of that node in the graph. These nodes have already been mapped to a HG node, since the algorithm proceeds from graph sinks to graph sources. Working from the descendant HG nodes, one computes the list of common immediate ascendant HG nodes which have correspondence in SG and are reachable by unused multiplexers. This is a list of possible HG nodes that can be mapped to the node in question. The nodes in this list are searched to find suitable candidates. First, the candidate HG node must be of the same type as the node: adder, multiplier, memory, etc. Second, the node must not be in use. If either of these tests fail the procedure returns unsuccessfully. Having performed these checks, the HG node is routed to its descendants, that is, the input multiplexers of the descendants are set to receive data from the node. If this is the last node to be mapped the procedure returns success. Otherwise, the map procedure is recursively applied to the next node in SG. If successful, the procedure returns success. Otherwise it means that the mapping of the next nodes can not be accomplished with the current mapping of the current or previous nodes. In this case the routes to the descendants are undone and the next candidate HG node is tried. After all candidate nodes are tried unsuccessfully the procedure returns unsuccessfully.
An example of application of a reconfigurable coprocessor instance created with the present invention is presented next. The example is a MPEG 1 layer III (MP3) decoder algorithm. The algorithm has been run on (1) a conventional processor and on (2) the same conventional processor accelerated by a coprocessor instance. The processor is a 32-bit Harvard architecture with 0,81 DMIPS of performance. The coprocessor instance has been generated with the following parameterization: 2 nested loops, 32-bit data path, 2 adders/accumulators, 2 multipliers/shifters, 3 dual port memory blocks totalling 4kbytes of ROM and 8kbytes of RAM. 
The experimental results from running a set of MP3 benchmarks are shown in Table 1. From the initial profiling of the algorithm on the conventional processor we find that two procedures are taking 95% of the time: the Polyphase Synthesis and the Inverse Modified Discrete Cosine Transform (IMDCT). Thus, if we accelerate these procedures in the coprocessor the potential for acceleration is 20. The Polyphase Synthesis procedure has been accelerated 18.7 times on average. The IMDCT procedure has been accelerated 43.9 times on average. This resulted in an overall algorithm acceleration of 11.9 times. The profiling of the complete system formed by the processor and coprocessor reveals a more balanced processing load distribution among the main procedures. In the complete system the Polyphase Synthesis and IMDCT procedures account for only 34% of the processing load, in stark contrast to the 95% processing load before acceleration.
【表１】
2010044731.tif 000025
In this example the silicon area doubled as the result of adding the coprocessor instance. Since the performance has been multiplied by twelve, this means that the processor-coprocessor system dissipates roughly 6 times less power, while still keeping the same level of performance.
It must be clear that the present reconfigurable coprocessor architecture template merely states the principles of the invention. Variations and modifications to the cited architecture can be made without moving away from the scope and principles of the invention. All these modifications and variations must be enclosed in the scope of the present invention and protected by the following claims.
References
(１)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 NAPA adapative 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.                
【請求項１】
An architecture template of a reconfigurable coprocessor, specialized in computing nested loops of expressions containing arithmetic and logic operations, comprising:
・  a linear array of unspecified number and type of reconfigurable, pipelined or not, functional units, which are to be chosen according to the application domain;
・  a linear array of unspecified number and type of embedded memories to store intermediate data and address calculations;
・  a reconfigurable address generator block to compute complex sequences of addresses for the embedded memories;
・  a partial and reconfigurable read crossbar, defined at pre-synthesis time, to connect system inputs, memory data output ports, and programmed constants to the functional unit inputs;
・  a partial and reconfigurable write crossbar, defined at pre-synthesis time, to connect functional unit outputs to system outputs or memory data input ports;
・  a register file containing control, status, and configuration registers, where the configuration registers store the configuration of the reconfigurable functional units, reconfigurable address generator block, partial and reconfigurable connection crossbars and further stores constants used in the data and address calculations.
【請求項２】
The architecture template of a reconfigurable coprocessor for nested loops according to claim 1, wherein the reconfigurable address generator block comprises:
・  a control unit to start, halt and resume the generation of addresses, which causes the coprocessor to start, halt and resume execution, accordingly;
・  a programmable timing unit to generate the enable signals which are used for: timely generation of addresses to index arrays stored in the various embedded memories, timely activating functionalities in the functional units and timely requesting system outputs and memory writes;
・  a linear array of programmable accumulators which are interconnected to generate complex address sequences;
・  a partial and reconfigurable enable crossbar, defined at pre-synthesis time, to connect the enable signals to the accumulators in the array, and to acknowledge the reading of external data at the system inputs;
・  a partial and reconfigurable input crossbar, defined at pre-synthesis time, to connect accumulator outputs and configuration constants to other accumulator inputs;
・  a partial and reconfigurable output crossbar, defined at pre-synthesis time, to connect accumulator outputs, which form the generated addresses, and respective enable signals to memory address ports, and routing memory data ports to memory address ports in the case of addresses stored in memory;
【請求項３】
The reconfigurable address generator block according to claim 2, wherein the programmable timing unit comprises:
・  a matrix of programmable counters, where each row produces a group of enable signals characterized by having the same delay in cycles, and the number of columns represents the maximum number of nested loops the coprocessor can do, where all counters in a column are programmed with the same end limit, determining the number of iterations of the loop they control;
・  an encoder to determine the actual number of nested loops in a given configuration, using the number of programmed columns;
・  a delay unit to delay the global enable signal up to a maximum permitted delay, and output enable signals with a programmed delay for each enable group, including the delay free enable and the maximum delay in the current configuration, which may be different from the maximum permitted delay in the architecture.
【請求項４】
The programmable timing unit according to claim 3, wherein the enable signals produced by the matrix of programmable counters are used to delay data streams relative to each other and compensate for different latencies in the data flow graph introduced by functional units with different delays, and performs the following actions: times the reading of data from inputs or memories; accompanies the data through functional units where enables and data are delayed equally; times the writing of data to outputs or memories.
【請求項５】
The reconfigurable address generator block according to claim 2, wherein the programmable accumulators comprise:
・  an input signal specifying the start value of the accumulator, where this input may be driven by another accumulator or by a configuration constant via the input crossbar;
・  an input signal specifying the increment value of the accumulator, where this input may be driven by another accumulator or by a configuration constant via the input crossbar;
・  an enable signal to enable the operation of the accumulator;
・  a restart enable signal to reload the start value;
・  an input signal specifying the offset value of the accumulator if the accumulator is a complex accumulator unit, where this input may be driven by another accumulator or by a configuration constant via the input crossbar;
・  a configuration register specifying the modulo value of the accumulator if the accumulator is a complex accumulator unit; 
・  an output accumulated value to be used as the generated address or the input of another accumulator.
【請求項６】
The architecture template of a reconfigurable coprocessor for nested loops according to claim 1, wherein the configuration, status and control register file comprises:
・  an addressable, read/write memory mapped interface, which enable fine granularity partial reconfiguration at runtime;
・  an output request signal to inform or ask for external assistance.
【請求項７】
The architecture template of a reconfigurable coprocessor for nested loops according to claim 1, wherein each functional unit in the functional unit array issues a break signal able to stop the coprocessor.
【請求項８】
The architecture template of a reconfigurable coprocessor for nested loops according to claim 1, wherein the multiple system inputs are slave request/acknowledge interfaces and the multiple system outputs are master request/acknowledge interfaces.
【請求項９】
The architecture template of a reconfigurable coprocessor for nested loops according to claim 8, wherein the absence of system input requests or system output acknowledges will stall the coprocessor if the expressions being executed read data from system inputs and/or write data to system outputs.
【請求項１０】
The reconfigurable address generator block according to claim 2, wherein the control unit enables and disables the coprocessor, terminates the processing when the outmost loop index wraps around, halts the coprocessor on input data starving, output data overflow, or when one or more break conditions from functional units fire.
【請求項１１】
A coprocessor programming tool for the architecture template of claim 1, comprising:
・  a compiler of the architecture description of the coprocessor;
・  a parser for the nested loop sequences, tagged and rewritten in the original program for a conventional processor, and using syntax essentially similar to that of a conventional programming language;
・  a compiler for the code of a nested loop sequence, which converts it to a particular configuration of the coprocessor.
【請求項１２】
An architecture description file following the hardware architectural template of claim 1, comprising
・  the description of the number and type of reconfigurable functional units;
・  the number, type, data and address widths of embedded memories;
・  the description of the reconfigurable address generator block;
・  the description of the reconfigurable read and write crossbars.
【請求項１３】
The architecture description file of claim 12, wherein the description of the reconfigurable address generation block comprises:
・  the description of the programmable timing unit block;
・  the description of the number and type of programmable accumulators;
・  the description of the reconfigurable enable, input and output crossbars.
【請求項１４】
The description of the reconfigurable address generation block of claim 13, wherein the description  of the programmable timing unit comprises:
・  the description of the number of nested loops in a group;
・  the description of the number of different delayed versions of the enable signal to be generated.
【請求項１５】
A configuration description file according to the architecture description file of claim 12, comprising
・  the description of the configuration of the functional units in terms of parameter/value pairs;
・  the configuration of the embedded memories in terms of read or write modes implicitly inferred from whether the ports are connected to functional unit inputs or outputs;
・  the description of the configuration of the reconfigurable address generator block;
・  the description of the configuration of the reconfigurable read and write crossbars.
【請求項１６】
The configuration description file of claim 15, wherein the description of the configuration of the reconfigurable address generation block comprises:
・  the description of the configuration of the programmable timing unit block;
・  the description of the configuration of each programmable accumulator;
・  the description of the configuration of the enable, input and output crossbars.
【請求項１７】
The description of the reconfigurable address generation block of claim 16, wherein the description  of the programmable timing unit configuration comprises:
・  the description of the end limits of each nested loop;
・  the description of the number of cycle delays for each enable signal group.
【請求項１８】
The description of the reconfigurable address generation block of claim 16, wherein the description  of the programmable accumulators comprises:
・  the start and increment values if connected to configuration constants;
・  the offset value if the accumulator is a complex accumulator unit and the offset input is connected to configuration constant;
・  the modulo value if the accumulator is a complex accumulator unit.
【請求項１９】
The coprocessor programming tool of claim 11, comprising:
・  a function to parse the arithmetic and logic expressions in the nested loop bodies to derive a complete system graph;
・  a function to create an ordered list of system graph nodes, which will be mapped to a hardware graph that represents the architecture in that order;
・  a function to parse the architecture description file of claim 13, and produce the hardware graph;
・  a function to recursively map each node in the system graph to a node in the hardware graph.
【請求項２０】
The coprocessor programming tool of claim 19, wherein the system graph comprises a sequence of configuration sub-graphs, wherein each configuration graph corresponds to a nested loop group.
【請求項２１】
The system graph of claim 20, wherein each configuration sub-graph comprises:
・  a data flow sub-graph;
・  an address flow sub-graph.
【請求項２２】
The configuration graph of claim 21 wherein the data flow sub-graph comprises:
・  sources nodes: memory node (data output ports), system data input node, configuration constant nodes;
・  sink nodes: memory node (data input ports), system data output node;
・  intermediate node: functional unit node.
【請求項２３】
The configuration graph of claim 21 wherein the address flow sub-graph comprises:
・  sources: memory node (data output ports), timing unit node (enable signals output ports), configuration constant node;
・  sink nodes: memory node (address input ports), system data input node (acknowledge signals);
・  intermediate node: accumulator unit node.
【請求項２４】
The architecture template of claim 1, wherein each data expression in the nested loop bodies consists of an assignment of a variable or array to a logic and arithmetic expression involving variables, arrays or configuration constants.
【請求項２５】
The data expressions of claim 23, wherein the index of each array must have the form ((alpha*i+beta)%gamma)+delta, where i is the loop variable and alpha, beta, gamma and delta can be recursively defined by expressions of the same form using loop variables inner to i.
【請求項２６】
The coprocessor programming tool of claim 19, wherein the function to recursively map a node in the system graph to a node in the hardware graph proceeds as follows: creates a list of all candidate hardware nodes which can be mapped to a given system node; tentatively maps the system node to each candidate hardware node and recursively tries to map the next system node in the list; if successful it keeps the current mapping and returns true; if unsuccessful it tries the next candidate hardware node; if all candidates are tried unsuccessfully it returns false.
【請求項２７】
The architecture template of claim 1, wherein at most as many memory accesses as memory data ports can be performed in parallel and in a single cycle, and all functional units can produce results in parallel and in a single cycle.
【請求項２８】
The architecture template of claim 1, wherein the performance of the system can be scaled by increasing the number of functional units and embedded memories, while keeping the sparse links in the connection crossbars to avoid clock period increase.
【請求項２９】
The architecture template of claim 1, wherein the resulting coprocessors are connected either synchronously or using asynchronous first in first out memories FIFOs, forming a globally asynchronous locally synchronous system.
The architectures are capable of executing one or more consecutive nested loop groups according to the following meta-language definitions:
1.Abstract
The architectures derived from the proposed template are integrated in a generic System on Chip (SoC) and consist of reconfigurable coprocessors for executing nested program loops whose bodies are expressions of operations performed in a functional unit array in parallel. The data arrays are accessed from one or more system inputs and from an embedded memory array in parallel. The processed data arrays are sent back to the memory array or to system outputs. The architectures enable the acceleration of nested loops compared to execution on a standard processor, where only one operation or datum access can be performed at a time. The invention can be used in a number of applications especially those which involve digital signal processing, such as multimedia and communications. The architectures are used preferably in conjunction with von Neumann processors which are better at implementing control flow. The architectures can be scaled easily in the number of data stream inputs, outputs, embedded memories, functional units and configuration registers. A computational system may entail several general purpose processors and several coprocessors derived from this architectural template. The coprocessors are connected either synchronously or using asynchronous first in first out memories (FIFOs), forming a globally asynchronous locally synchronous system. Each coprocessor can be programmed by tagging and rewriting the nested loops in the original program. The programming tool produces a coprocessor configuration per each nested loop group, which is replaced in the original code with coprocessor input/output operations and control.
2．Representative Drawing
Figure 1
【図１】
2010044731.tif 000026
【図２】
2010044731.tif 000027
【図３】
2010044731.tif 000028
【図４】
2010044731.tif 000029
【図５】
2010044731.tif 000030
【図６】
2010044731.tif 000031
【図７】
2010044731.tif 000032
【図８】
2010044731.tif 000033
【図９】
2010044731.tif 000034
【図１０】
2010044731.tif 000035
【図１１】
2010044731.tif 000036
【図１２】
2010044731.tif 000037
【図１３】
2010044731.tif 000038
【図１４】
2010044731.tif 000039
【図１５】
2010044731.tif 000040
【図１６】
2010044731.tif 000041
【図１７】
2010044731.tif 000042
【図１８】
2010044731.tif 000043
【図１９】
2010044731.tif 000044
【図２０】
2010044731.tif 000045
【図２１】
2010044731.tif 000046