(57)【要約】      （修正有）【課題】３つの誤りタイプ（過渡的、間欠的及び永久的）の対処により解決される誤り耐性ルータ、及び前記誤り耐性ルータを使用する２Ｄ又は３Ｄ−ＩＣを提供する。【解決手段】ＩＣに有する複数のコアのそれぞれに対応して備えられた誤り耐性ルータであって、それぞれのコアに対応する複数の入力ポート部１〜７と、前記入力ポート部１〜７の出力を、所定の出力先に接続するクロスバー１３と、予測テーブル１０を有する誤り制御モジュール２０を有し、各入力ポート部は、入力バッファ１１、ランダムアクセスバッファ９、前記入力バッファ１１のスロット誤りを検知する誤り検知回路を有し、前記誤り検知回路がスロット誤りを検知する時、他の残りのスロットが占有されている場合は、誤り制御モジュール２０にフラグを送り、前記予測テーブル１０は、トラフィック情報を格納していて、最良の入力バッファを選択して、前記ランダムアクセスバッファ９に通知する。【選択図】図１
2015119387.tif 000002
【特許請求の範囲】
【請求項１】
ＩＣに有する複数のコアのそれぞれに対応して備えられた欠陥耐性ルータであって、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート部（１−７）と、
前記複数の入力ポート部（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する欠陥制御モジュール（２０）を有し、
前記複数の入力ポート部（１−７）のそれぞれに、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット欠陥を検知する欠陥検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、 
前記欠陥検知回路（９１）が前記入力バッファ（１１）のスロット欠陥を検知する時、前記ランダムアクセスバッファ（９）が、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記欠陥制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）が、トラフィック情報を格納していて、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する、
ことを特徴とする欠陥耐性ルータ。
【請求項２】
請求項１において、
前記予測テーブル（１０）は、所定のタイミング周期で、前記複数の入力ポート部（１−７）の各々からトラフィック負荷情報を収集し、平均フリッツ到達を計算し、欠陥入力バッファのフリッツを受け入れる最適の入力ポートを決定する、
ことを特徴とする欠陥耐性ルータ。
【請求項３】
請求項１において、
さらに、前記クロスバー（１３）に対する複数のバイパス路（１３１、１３２）と、
前記クロスバー（１３）のリンク状態をチエックするクロスバー制御部（１７）を有し、
前記クロスバー制御部（１７）が、１又は複数のリンクの欠陥を検出する時、前記欠陥制御モジュール（２０）にフラグを送り、
前記欠陥制御モジュール（２０）は、前記クロスバー欠陥リンクを不能にして、適切な数の前記複数のバイパスリンク（１３１、１３２）を可能とする、
ことを特徴とする欠陥耐性ルータ。
【請求項４】
請求項３において、
推定される欠陥率を分析し、前記バイパスリンクの数が、実行処理が落ち着く、或いは変化のない状態になるまで増加される、
ことを特徴とする欠陥耐性ルータ。
【請求項５】
請求項１−４のいずれか１項において、
前記ＩＣが、それぞれに複数のコアが形成された複数の積層ウェハで構成される３Ｄ−ＩＣであることを特徴とする欠陥耐性ルータ。
【請求項６】
それぞれ複数のコアを備える複数のウェハで構成され、前記複数のコアに対応して複数の欠陥耐性ルータを有する３次元ＩＣであって、
前記複数の欠陥耐性ルータのそれぞれが、
それぞれ対応するコアの方向からの入力を受ける複数の入力ポート部（１−７）と、
前記複数の入力ポート部（１−７）の出力を所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する欠陥制御モジュール（２０）を有し、
前記複数の入力ポート部（１−７）のそれぞれに、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット誤りを検知する欠陥検知回路（９１）と、
ランダムアクセスバッファ（９）を備え、
前記欠陥検知回路（９１）が前記入力バッファ（１１）のスロット誤りを検知する時、前記ランダムアクセスバッファ（９）は、他のスロットが占有されているかを判断し、
他のスロットが占有されている場合、前記誤り制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を保持していて、最良の入力バッファを選択して、ランダムアクセスバッファ部（９）に通知する、
ことを特徴とする３次元ＩＣ。
【請求項７】
請求項５において、
前記予測テーブル（１０）は、所定のタイミング周期で、前記複数の入力ポート部（１−７）の各々からトラフィック負荷情報を収集し、平均フリット到達時間を計算し、欠陥入力フリッツを扱う適切な入力ポートを決定する、
ことを特徴とする３次元ＩＣ。
【請求項８】
請求項５において、
さらに、前記クロスバー（１３）に対する複数のバイパス路（１３１、１３２）と、
前記クロスバー（１３）のリンク状態をチエックするクロスバー制御部（１７）を有し、
前記クロスバー制御部（１７）により、１又は複数のリンクの欠陥が検出される時、前記誤り制御モジュール（２０）にフラグを送り、
前記誤り制御モジュール（２０）は、前記誤りのクロスバーリンクリンクを不能にして、前記複数のバイパス路（１３１、１３２）の適切な数を可能とする、
ことを特徴とする３次元ＩＣ。
【請求項９】
請求項７において、
推定される欠陥率を分析し、前記バイパスリンクの数が、実行処理が落ち着く、或いは変化のない状態になるまで増加される、
ことを特徴とする欠陥耐性ルータ。
【請求項１０】
請求項６−９のいずれか１項において、
前記ＩＣが、それぞれに複数のコアが形成された複数のウェハで構成される３Ｄ−ＩＣであることを特徴とする欠陥耐性ルータ。
【請求項１１】
ＩＣの複数のコアのそれぞれに対応して備えられた欠陥耐性ルータの制御方法であって、
第１の処理ステージとして、
ランダムアクセスバッファ（９）により、それぞれの入力ポート（１−７）の入力バッファ（１１）のデッドロックと欠陥状態を検知し、
前記入力ポート（１−７）のそれぞれの入力バッファ（１１）に付属するプローブからトラフィック情報を受信し、
入力フリッツから次のポートに対する識別情報を取得し、
スイッチ要求信号をスイッチ配置器（１６）に送り、
第２の処理ステージとして、
欠陥制御モジュール（２）からの受信信号に基づくルーチングモジュールによって実行される次のノードに対する次のポートを計算し、
前記スイッチ配置器（１６）により管理される異なるポートからのリクエスト間をスケジューリングし、
前記スイッチ配置器（１６）から要求された出力ポートの使用を許可する要求信号と制御信号を、スケジューリング結果についての情報を有するクロスバー（１３）に送り、
第３の処理ステージとして、
入力バッファ（１１）からのフリッツをチェックし、適切な隣接ノードに送る
ことを特徴とする欠陥耐性ルータの制御方法。
【請求項１２】
請求項１１において、
前記ＩＣは、複数のコアのそれぞれが備えられ、積層されたウェハで形成された３Ｄ−ＩＣである、
ことを特徴とする欠陥耐性ルータの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、チップ上の複数のコアネットワークのためのオンデマンドのバイパスリンクに基づく欠陥耐性ルータ、前記ルータを有する２又は３次元ＩＣ、及び前記欠陥耐性ルータの制御方法に関する。
【背景技術】
【０００２】
２又は３次元ＩＣに用いられるマルチコアチップ（ＣＭＰ）構造において、ＮｏＣ（ネットワーク-オン-チップ）は、プロセッサノード及びそのプライベート(個別)キャッシュを、共用キャッシュとメモリコントローラに接続する。ＮｏＣは、また、インタラプト(中断)リクエストのような他の制御トラフィックを伝送する。
【０００３】
そのような構造において、ルータは、各ノードに存在して、パイプラインリンクでコアを隣接のコアと接続する。ノード間のコミニュケーションユニットは、パケットあるいはフリッツ(Flit)であり、パケットは、リンク幅に等しいフリッツ又はユニットに分割される。
【０００４】
三次元ＩＣ(３Ｄ-ＩＣ)は、いくつかのウェハを積み重ねて形成され、ワイヤの長さ及び遅延を短縮する。３Ｄ-ＩＣにおいて、複数のコアが、それぞれのウェハに配置して備えられ、そして、複数のルータがそれぞれのコアに対して備えられている。
【０００５】
それぞれのルータは、“三次元ネットワークオンチップ(３Ｄ-ＮｏＣ)”システムと称される３Ｄ-ＩＣ上のネットワークシステムを通して複数のコアを接続する。
【０００６】
３Ｄ-ＮｏＣのネットワーク形態が、近年研究されて来て、いくつかの研究が、三次元ネットワークオンチップ（３Ｄ-ＮｏＣ）システムにおける欠陥耐性に取り組まれている。研究は、目標システム、欠陥のタイプ、あるいは欠陥をどのように扱うか（例えば、経路計算あるいは構造解法を用いて）に依存して分類することができる。
【０００７】
提案された欠陥耐性３Ｄ-ＮｏＣ解法のいくつかは、生産を改善するためのスルーシリコンビア（Through-Silicon-Vias：TSVs)において生じる永久欠陥に焦点を当てている。例えば、それらのいくつかは、予備挿入：spare insertion（非特許文献１）、あるいは連載：serialization（非特許文献２）である。
【０００８】
他の解法は、欠陥耐性ルーイング構造を適用してリンク欠陥のみに焦点を当てている。既に存在する解法（非特許文献3-6）の大半は、ルーティングテーブルに基づき、周囲の欠陥リンクの情報を格納し、デッドロックの発生を回避する。それらは、仮想チャネル(ＶＣｓ)を用いる(非特許文献７)。他は、ＶＣｓの使用を回避し、その代わりに転換-モデルルーチングを用いてデッドロックを回避するものであった（非特許文献８）。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願公開第２０１２／０１５５４８２号明細書
【非特許文献】
【００１０】
【非特許文献１】I. Loi、 Subhasish Mitra、Thomas H. Lee、Shinobu Fujita、and Luca Benini. A low-overhead fault tolerance scheme for TSV-based 3D network-on chip links. In ICCAD 08: Proceedings of the 2008 IEEE/ACM コンピュータ利用デザインに関する国際会議、頁598-602、 2008年.
【非特許文献２】S. Pasricha. Exploring serial vertical interconnects for 3D ICs. In DAC 09: 第46回定期デザイン自動化の会議のプロシーディング、 頁581-586、 New York、 NY、 USA、 2009年. ACM.
【非特許文献３】Ch. Feng. M. Zhang、J. Li. J. Jiang. Z. Lu and A. Jantsch. A Low-overhead Fault-Aware Deflection Routing Algorithm for 3D Network-on-Chip. IEEE のＶＬＳＩについてのコンピュータ部門定期シンポジウム、頁19-24. ７月2011年.
【非特許文献４】Y. Li Shietung Peng、and Wanming Chu. Adaptive box-based efficient fault-tolerant routing in 3D torus. 頁71 -77、 2005 .
【非特許文献５】Ch. Feng. Z、 Lu、 A. Jantsch、J. Li and M. Zhang. A Reconfigurable Fault-tolerant Deflection Routing Algorithm Based on Reinforcement Learning for Network-on-Chip. チップ構造におけるネットワークについての第３回国際ワークショップ、頁11-16、 １２月2010年.
【非特許文献６】D. Xiang、 Y. Zhang and Y. Pan. Practical Deadlock-Free Fault-Tolerant Routing Based on the Planar Network Fault Model. コンピュータに関するIEEE トランザクション、 58(5):620-633. 5月2009年.
【非特許文献７】W. J. Dally. Virtual-channel flow control. IEEE Trans. on Parallel and Distributed Systems、3(2): 194-205、3月1992年．
【非特許文献８】S. Pasricha and Y. Zou. A Low Overhead Fault Tolerant Routing Scheme for 3D Networks-on-Chip. The 12th International Symposium on Quality Electronic Design、 頁1-8、 3月2011年．
【非特許文献９】T. Lehtonen、P. Liljeberg and J. Plosila. Online Reconfigurable Self-timed links for Fault Tolerant NoC. VLSI Design、(2007): 1-13、2007年.
【非特許文献１０】DeOrio、 A. et. al.、 A Reliable Routing Architecture and Algorithm for NoCs. IEEE Transactions on CAD of Integrated Circuits and Systems. 5月2012年、 頁726-739.
【非特許文献１１】A. Ben Ahmed and A. Ben Abdallah. Architecture and Design of High-throughput、Low-latency、and Fault-Tolerant Routing Algorithm for 3D-Network-on-Chip (3D-NoC). スーパーコンピュティングジャーナル、 DOI:10月1007年/s 11227-013-0940-9
【非特許文献１２】A. Ben Ahmed and A. Ben Abdallah. Fault-tolerant Routing Algorithm with Deadlock Recovery Support for 3D-NoC Architectures. 第７回IEEE 組込みマルチコアSoCs国際シンポジウム. 9月2013年.
【非特許文献１３】A. Ben Abdallah、Multicore Systems-on-Chip: 実用ハードウエア/ソフトウエアデザイン、 ２版、 Publisher発行社: Springer、(2013)、ISBN-13: 978-9491216916.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上記に説明したように、３Ｄ-ＮｏＣシステムにおける欠陥耐性問題を述べている既存の種々の解法に拘わらず、以下に述べるようにいくつかの問題を依然として残している。
【００１２】
第一に、いくつかの解法は、永久欠陥のみに焦点を当て、他のタイプの欠陥を考慮していなかった。しかし、非特許文献９に述べられているように、欠陥の大半（８０％）は、過渡的欠陥により生じ、残りの欠陥が、主に永久的並びに間欠的な欠陥に基づくものである。
【００１３】
第二に、多くの解法は、リンク欠陥に焦点を当てていた。しかし、非特許文献１０によると、入力バッファ及びクロスバーは、それぞれ８０％、１０％に達する、３Ｄ-ＮｏＣシステムにおいて大きな領域を占めている。一方、残りの素子のそれぞれは、ルータ全領域の３％を超えない。これは、入力バッファ及びクロスバーにおける欠陥が、より大きな重要性を与えられるべきである事を意味している。さらに、信頼できる解法は、そのような種類の欠陥を扱うことが出来なければならない。
【００１４】
第三に、既に提案されている研究は、デッドロックの発生を回避するためにＶＣｓに基づいている。ＶＣｓは、システムがデッドロックに繋がらないことを保証する。しかし、それらは、調整を行うために要求されるレーテンシーの不利に加えて、ハードウエアの複雑性という点で高価となる調整に基づいている。転換モデルに基づくルーティング構造は、ＶＣｓの使用を必要としない。しかし、非最小の性質は、システムのスループットに影響を与える不要のクロックサイクルをもたらす。
【００１５】
上記を要約すると、従来システムは以下の問題点を有している。
【００１６】
第一に、従来システムは、永久欠陥のみに焦点をあて、他の欠陥タイプを考慮していなかった。しかし、ＮｏＣにおける欠陥の大半は、過渡的欠陥により生じる、一方、残りの欠陥は、主に永久的及び間欠的欠陥による。
【００１７】
大半の従来の解法は、リンク欠陥に焦点を当てていた。しかし、２Ｄ又は ３Ｄ-ＮｏＣシステムにおいて、入力バッファ及びクロスバーが大きな領域を占めており、よって、入力バッファ及びクロスバーにおける欠陥に大きな重要性を与えられるべきである。
【００１８】
さらに、デッドロックの発生が、ＶＣｓに基づき回避される。ＶＣｓは、システムのデッドロックを保証するが、ハードウエアの複雑性という点で高価となるアービタに基づいている。
【００１９】
したがって、本発明の目的は、上記問題を３つの欠陥タイプ（過渡的、間欠的及び永久的）の対処により解決される欠陥耐性ルータ、及び前記欠陥耐性ルータを使用するＩＣを提供することである。提案する解法は、前記提案する欠陥ルータを使用する２Ｄ又は３Ｄ−ＩＣに備えられるリンク、入力バッファ、及びクロスバー回路における異なるタイプの欠陥に向けられている。
【課題を解決するための手段】
【００２０】
本発明において、使用されるランダムアクセスバッファ技術（ＲＡＢ）は、バッファにおけるデッドロックの理由であるフリッツを第一に検出するスマートコントローラ(RAB cntrl)に基づく。検出メカニズムは、ある時間周期の後、もし処理される要求が許可されないと、フラグを発行して、前記要求を破棄するタイマーに依存する。 
【００２１】
そして、ＲＡＢは、バッファにおけるいくつかのスロットをフリーにし、従属性を断つことが許可される他のフリッツを求める。ＲＡＢは、各入力バッファにおいて一時に一要求を扱う。したがって、ＶＣｓに対する場合のように、調整の存在はもはや必要がない。さらに、ＶＣｓの数が増えると、ＶＣ配置の複雑さも増える。そして、効果的なスケジューリング方法の利用が重要となる。しかし、ＲＡＢを伴って、バッファの深さは、そのパフォーマンスに影響を与えない。対照的に、非ブロックのフリッツを探す確率は、速いデッドロックの回復をさせる。
【００２２】
本発明に従う第一の技術側面は、積層ウェハを有する３Ｄ-ＩＣに備えられる複数のコアの各々に対応して備えられる欠陥耐性ルータであって、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート（１−７）と、
前記複数の入力ポート（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する欠陥制御モジュール（２０）を有し、
前記複数の入力ポート（１−７）のそれぞれが、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット欠陥を検知する欠陥検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、
前記欠陥検知回路（９１）で前記入力バッファ（１１）のスロット欠陥を検知する時、前記ランダムアクセスバッファ（９）は、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記欠陥制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を格納し、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する。
【００２３】
本発明に従う第２の技術側面は、それぞれ複数のコアと、前記複数のコアのそれぞれに対応するルータを有する、積層されたウェハで形成された３Ｄ-ＩＣであって、
それぞれのルータが、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート（１−７）と、
前記複数の入力ポート（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する欠陥制御モジュール（２０）を有し、
前記複数の入力ポート（１−７）のそれぞれが、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット欠陥を検知する欠陥検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、
前記欠陥検知回路（９１）で前記入力バッファ（１１）のスロット欠陥を検知する時、前記ランダムアクセスバッファ（９）は、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記欠陥制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を格納し、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する。
【００２４】
本発明に従う第３の技術的側面は、３Ｄ-ＩＣを形成するウェハに備えられた複数のコアの各々に対応して有する欠陥耐性ルータの制御方法であって、
第１の処理ステージとして、
ランダムアクセスバッファ（９）により、それぞれの入力ポート（１−７）の入力バッファ（１１）のデッドロック状態と欠陥状態を検知し、
入力ポート（１−７）のそれぞれの入力バッファ（１１）に付属のプローブからトラフィック情報を受信し、
入力フリッツから次のポートの識別情報を取得し、スイッチ配置器（１６）にスイッチ要求信号を送信し、
第２の処理ステージとして、
欠陥制御モジュール（２）から受信した信号に基づき、ルーティングモジュールにより実行される次のノードに対する次のポートを計算し、
前記スイッチ配置器（１６）により管理される異なるポートからの要求間をスケジューリングし、
前記スイッチ配置器（１６）から要求された出力ポートの使用を許可する要求信号と制御信号を、スケジューリング結果の情報を持つクロスバー（１３）に送り、
第３の処理ステージとして、
入力バッファ（１１）からの送信フリッツをチェックし、適切な隣接ノードに送信する。
【発明の効果】
【００２５】
大半の従来の３Ｄ-ＮｏＣシステムは仮想チャネル（ＶＣｓ)に基づき、デッドロックの発生を回避する。ＶＣｓは、システムのデッドロックなしにすることを保証する。しかし、これらの利点は、そのような技術を含む複雑さに加え、高次の追加的ハードウエアを伴う。さらに、ＶＣｓは、超過的パイプラステージ（通常、ＶＣ配置器として参照される）、及び従って追加的クロックサイクルを必要とする複数の要求を扱うために、調整を有することが必要である。このように、このレーテンシーは、システム全体に渉って重要な効果を有する。
【００２６】
本発明において、使用されるランダムアクセスバッファ技術（ＲＡＢ）は、フリッツが、バッファのデッドロックの理由であることを、先ず検出するスマートコントローラ（RAB cntrl）に基づく。検出メカニズムは、ある時間周期後、処理される要求が許可されないと、フラグを発行し、その要求を破棄するタイマーに基づいている。
【００２７】
そして、ＲＡＢは、バッファにおけるいくつかのスロットをフリーにして、従属性を断つために、要求が許可される他のフリッツを求める。ＲＡＢは、各入力バッファにおいて一時に一要求を処理する。したがって、ＶＣｓに対する場合のように、調整の存在はもはや必要がない。さらに、ＶＣｓの数が増えると、ＶＣ配置器の複雑さも増える。そして、効果的なスケジューリング方法の利用が重要となる。しかし、ＲＡＢを伴って、バッファの深さは、そのパフォーマンスに影響を与えない。対照的に、非ブロックのフリッツを探す確率は、速いデッドロックの回復をさせる。
【図面の簡単な説明】
【００２８】
【図１】本発明に従い、提案する３Ｄ欠陥耐性OASIS-ＮｏＣルータ構造のブロックダイヤグラムを示す図である。
【図２】ランダムアクセスバッファ９のブロックダイヤグラムを示す図である。
【図３】予測テーブル１０を説明をする概略図である。
【図３Ａ】システムがスタートする時のカウンタ値を示す図である。
【図３Ｂ】第１の１００サイクル後の出力された入力フリッツの数を示す図である。
【図３Ｃ】平均フリッツ到達の計算を示す図である。
【図３Ｄ】最良候補バッファの決定を示す図である。
【図３Ｅ】最良候補バッファの送信を示す図である。
【図４】ルックアヘッド欠陥耐性ルーティングのアルゴリズムを示す図である。
【図５】バイパスリンク-オンデマンドメカニズムを示す図である。
【図６】本発明に従う３Ｄ欠陥耐性ＮｏＣ（3D-FTNoC）の動作におけるタイムチャートを示す図である。
【図７】最も一般に使用される従来のルータのタイムチャートを示す図である。
【発明を実施するための形態】
【００２９】
本発明の実施例を添付図面に従い、説明する。実施例は、発明の良い理解のためのものであり、発明の保護の範囲がこの実施例に制限されるものではない。
【００３０】
複数の小さなウェハの積み重ねにより形成される３Ｄ-ＩＣについて主として説明が行われるが、本発明は、一つのウェハに形成された複数のコアと、前記複数のコアを接続するネットワークを有して形成される２Ｄ-ＩＣにも適用可能である。
【００３１】
[３Ｄ-欠陥耐性ルータ-ＮｏＣアークテクチャ]
図1は、本発明に従い、提案する３Ｄ-欠陥耐性-OASIS-ＮｏＣルータ構造のブロックダイヤグラムを示す。
【００３２】
図1において、ＮｏＣルータは、それぞれ積層されたウェハに形成されたコアの対応する方向からの入力を受信する、ローカル入力ポート１、ノース入力ポー２、イースト入力ポート３、サウス入力ポート４、ウエスト入力ポート５、アップ入力ポート６、及びダウン入力ポート７である複数の入力ポートユニットを有する。
【００３３】
入力ポートユニット１-７の各々は、非特許文献１１で先に提案された、欠陥リンクを扱うルックアヘッド欠陥耐性（ＬＡＦＴ）ルーティングアルゴリズム８を有する。ＬＡＦＴルー-ティングアルゴリズム８に加えて、本発明に従い、更に欠陥耐性を支えるために、二つの主要コンポーネントが用いられる。
【００３４】
すなわち、入力バッファ１１の欠陥のための欠陥制御モジュール２０内に位置するトラフィック予測ユニットの一エレメントである予測テーブル（ＰＴ）１０を有して用いられるランダムアクセスバッファ（ＲＡＢ）メカニズム９が、入力ポートユニット１−７の各々に備えられる。さらに、クロスバー１３における欠陥のためのバイパスリンクオンデマンド（ＢＬＯＤ）１２が備えられる。
【００３５】
ランダムアクセスバッファ（ＲＡＢ）メカニズム９は、ＲＡＢコントローラ９０に加えて、デッドロック管理機能、欠陥管理機能を有する。
【００３６】
ランダムアクセスバッファ（ＲＡＢ）メカニズム９のＲＡＢコントローラ９０は、対応する入力バッファの欠陥状態を規則的にモニタする。欠陥スロットの存在を検知する時、残りのスロットが占有されているか、否かをチェックする。
【００３７】
残りのスロットが占有されている場合は、ＲＡＢコントローラ(cntrl)９０は、予測テーブル１０に、単一ビットの“バッファフラグ：Buffer-flg”信号を送る。この予測テーブル１０は、残りの入力バッファのそれぞれのトラフィック負荷についての情報を既に有していて、“最良−バッファ：Best-buff”信号を、RAB-コントローラ９０に送り返す。RAB-コントローラ９０は、パケットから分割され、リンク幅に等しい入力フリッツを新しく選択された入力バッファにリダイレクトする。 
【００３８】
入力バッファにおいて先に検知された欠陥が解消された場合、あるいは入力バッファが殆ど空いていて、他の入力フリッツを受けることができる場合、“バッファフラグ：Buffer-flg”信号が０に戻され、予測テーブル１０に、他の入力バッファ資源を使用する必要がないことを通知する。そして、先の欠陥バッファが新しい入力フリッツの受信、及び格納を開始する。
【００３９】
[ランダム アクセス バッファコントローラ（RAB buffer cntrl）９]
図２は、提案するランダムアクセスバッファ９のブロックダイヤグラムを示す。ランダムアクセスバッファ９は、先に上記非特許文献１２にデッドロックフリーを確実にするための基本的、且つ低負荷解法として提案されていた。
【００４０】
本発明において、拡張されたランダムアクセスバッファが備えられて、ランダムアクセスバッファメカニズム（RAB mechanism）として、入力バッファ１１における過渡的、間欠的、及び永久的な欠陥を検知し、回復することができる。
【００４１】
ランダムアクセスバッファ９は、二つの主たる並列位相に分配される。第一の位相は、欠陥の検出及び欠陥の回復が行われることを意味する、局部的な処理である。第二の位相は、全体的な(即ち、ルータ全体における)処理であって、ランダムアクセスバッファ９が、予測テーブル（PT）１０で支持され、後に説明するように、システムのパフォーマンスを更に高める。
【００４２】
欠陥の検知のために、図２に示す欠陥検知回路９１が使用され、入力バッファ１１のバッファスロットの欠陥状態のチェックを行う。欠陥検知回路９１によりスロットの一つにおいて、欠陥が検知される時、欠陥検知回路９１は、“欠陥スロット：faulty-slot”信号をバッファコントローラ（Buffer_Contrl）９０内のＲＡＢモジュール９２に送り、バッファコントローラ（Buffer_Contrl）９０内のＦＩＦＯ９３から書込アドレス“Wr_adr”、及び読出アドレス“Read_adr”を付与する時に、フラグを立てられたスロットを考慮させる。 
【００４３】
欠陥スロットの記録を維持するために、n2ビットアイテム（nは、バッファの深さ）を扱うアレーから成るステータスレジスタが、ＲＡＢモジュール９２に備えられる。
【００４４】
ステータスレジスタに保持される各アイテムの値が、“００”であるとき、対応するフリッツがデッドロックを生じてなく、バッファスロットが欠陥でないことを通知する。“０１”であるとき、バッファスロットが欠陥でないが、扱われるフリッツの要求がデッドロックを起こしていることを示す。最後に、欠陥が対応するバッファスロットで検知される場合、ステータスレジスタにおけるエレメントが、“１１”に更新される。したがって、スロットは、（壊れたスロットを調べるための追加的待ち時間を避けるために）使われることも、入力するフリッツを格納することもできない。
【００４５】
[予測テーブル（ＰＴ）１０] 
図３は、トラフィック予測ユニット１００に備えられる予測テーブル１０の使用を説明する簡単な例を示す。しばしば生じる興味あるケースは、所定の入力バッファ１１が、いくつかの欠陥スロットを有する場合、残りのスロットが、他のフリッツで占有され、同じルータの他の入力バッファが空になるということである。パフォーマンスを拡大し、全てのルータ資源を完全に使用するために、本発明においては、全ての入力ポート１-７において入力バッファ資源を共有させる技術を採用する。これは、入力バッファ１１が、（欠陥スロットの存在、残りのスロットの占有のために、）更にフリッツを扱うことをできない時、入力フリッツを他の隣接する空きの入力バッファに振り向けて、速く到達先に送ることができることを意味する。
【００４６】
この目的を達成するために、使用可能な空き入力バッファ中で、振り向けたフリッツを受信する最良の候補を知ることが、非常に重要である。本発明において、図３に示す様に、予測テーブル（ＰＴ）１０が使用され、特定の時間周期で、それぞれの入力ポートのトラフィック負荷（信号５０）の情報を収集する。これらの情報は、ルータ内の入力バッファ１-７のそれぞれに付加されているモニタリングプローブ（Prb0-Prb6）１４から受信される。収集されたトラフィックのスナップショットが、各入力バッファにおける平均フリッツの到達を計算するために使用される。そして、予測テーブル１０が渋滞を生じさせないで、欠陥入力バッファのフリッツを扱うことができる最良の入力ポートを決定することができる。
【００４７】
最良の入力バッファが選択されると（本実施例では、イーストバッファ３）、予測テーブル１０は、ＲＡＢコントローラ（RAB cntrl 0-6）９０から発行されるフラグ５１を待つ。図２に示すバッファ欠陥は、バッファ（ノース入力ポート２の入力バッファ１１）が欠陥であり、同時に一杯であることの情報を与える。この場合、予測テーブル１０は、ノース入力ポート２の対応する入力バッファに他の信号を返送し、新しい入力バッファを指定する（例えば、イースト入力ポート３の入力バッファ）、その入力バッファが破線矢印５２で示す様に、いくつかのスロットが開放になり、ノース入力ポート２の入力バッファが再び入力フリッツを受信できるまで、入力フリッツを受け入れる。
【００４８】
所定のパケットのいくつかのフリッツがバッファに格納され、それが欠陥であり、一杯になっていると宣言される。そして、ＲＡＢメカニズム９に従い、このパケットの残りのフリッツが異なるバッファに格納される場合がある。このよう場合は、残りのフリッツが異なるバッファに格納されているので、これらのフリッツが順序を外れて到達するかも知れない。
【００４９】
結果として、到達ノードでは再配列処理が必要となり、あるいは、残りのフリッツと同時に到達できるようにいくつかのフリッツに追加すべき遅延が生じる。本発明では、簡単は解決として、ヘッダである場合、振り向けフリッツのみをスタートさせる。この場合、このパケットの残りのフリッツは、ヘッダフリッツと同じバッファに格納される。この追加的規制に伴い、パケットのフリッツが追加のハードウエア／パワーの過負荷もパーマンスの劣化もなしに、パケットのフリッツが適切に到着する。
【００５０】
図３Ａ−３Ｅは、トラフィック予測ユニット１００の動作の詳細を示す図である。
【００５１】
図３Ａ-３Ｅにおいて、プローブ１-６は、ローカル（Local）プローブ、ノース（Nth）プローブ、イースト（Est）プローブ、サウス（Sth）プローブ、ウエスト（Wst）プローブ、アップ（Up）プローブ、及びダウン（Dwn）プローブにそれぞれ対応する。プローブ１-６のそれぞれは、キュー信号を用いて、新たなフリッツが入力バッファ１１に到達する都度、歩進するカウンタを有する。カウンタのカウント値は、１００サイクルで到達するフリッツの数を記憶することができる８ビットのレジスタに格納される。
【００５２】
トラフィック予測ユニット１００は、それぞれ８ビットサイズの７つの入力を受け入れできる予測テーブル１０を含む。それぞれの入力は、一つの入力ポートに割り当てられ、そのフリッツ到達率を格納する。
【００５３】
トラフィック予測ユニット１００は、以下のステップに従い動作する。
【００５４】
１）それぞれのプローブが、その値を出力し、１００サイクル毎（レジスタサイズを小さくするために）、予測テーブル１０に送る。
【００５５】
２）トラフィック予測ユニット１００は、プローブから来た値と既に予測テーブル１０に有る値とを使用して１００サイクル（フリッツ／１００サイクル）でフリッツの平均値を計算する。
【００５６】
３）新しい平均値が予測テーブル１０に更新される。
【００５７】
４）トラフィック予測ユニットとは、７つの入力ポートの平均をチェックし、最良の候補と考えられる最小値を選択する。
【００５８】
５）ＲＡＢが、フルバッファにおいて欠陥があることの表示（Buffer_flg信号）をするとき、トラフィック予測ユニット１００が計算した、待避チャネルとして用いられる最良の候補を送る。
【００５９】
ここで、上記ステップに従い、トラフィック予測ユニット１００における動作の例を説明する。
【００６０】
図３Ａにおいて、システムがスタートすると、プローブのカウンタの値と予測テーブル１０の入力がゼロに初期化される。
【００６１】
そして、図３Ｂにおいて、最初の１００サイクルの後、入力フリッツの数が、プローブから出力され、トラフィック予測ユニット１００に送られ、平均値がカウントできないので、直接に予測テーブル１０に格納される。同時に、プローブのカウンタは、０にリセットされる。ウエストが次いで、フリッツの平均が、最小値である１０であるとき、最良の候補バッファとして計算される。
【００６２】
図３Ｃにおいて、１００サイクル経過毎に、プローブはその値を出力し、トラフィック予測ユニット１００に送る。トラフィック予測ユニット１００は、所定の入力ポートから入力情報を読み取り、予測テーブル１０における対応する値を読み、平均フリッツの到達値を計算する。
【００６３】
ついで、図３Ｄにおいて、プローブのカウンタは、再びゼロにリセットされる。予測テーブル１０の入力は、計算された平均値で更新される。予測テーブル１０における最小値が計算され、最良の候補バッファが計算される（その平均値が最小の３５であるローカルが、最良の候補である）。 
【００６４】
図３Ｅにおいて、トラフィック予測ユニット１００が、（バッファ１１が空きがなく、欠陥を有することを通知する、図１参照）ＲＡＢモジュール９からのバッファフラグ（Buffer_flg）信号を受信するとき、トラフィック予測ユニット１００は、入力フリッツに対する代替の入力バッファとして使用される最新の最良の候補バッファを、フラグされたバッファに送る。
【００６５】
[先読み（Look-Ahead）欠陥耐性ルータ（“LAFT”）]
先読みルーティングの利点を保持するために、先に提案された先読み欠陥耐性（LAFT）[非特許文献１１]が、リンク状態を考慮する次のノードに対するルーティングの決定を実行し、図４のアルゴリズム１に示されるように、最良の最小パスを選択する。
【００６６】
欠陥コントロールモジュール（ＦＣＭ）２０から受信した欠陥情報（図１における欠陥リンク）がLAFTが実行される各入力ポートにより読まれる。
【００６７】
このアルゴリズムの第１のフェーズは、次のノードアドレスを計算する。所定の最終到達先にフリッツを送りたい所定のノードに対して、X、 Y、 Z次元のそれぞれを通して最大３つの可能な方向が存在する。
【００６８】
第２のフェーズでは、LAFTは、現在と到達先ノードの両方のX、Y、Z座標を同時に比較して、この３方向の計算を実行する。これらの方向の計算と同時に、欠陥制御モジュール２０は、フリッツから次のポートの識別子を読み、対応する入力ポートに適切な欠陥情報を送る。この第２のフェーズ終わりまでに、LAFTは、次のノードの欠陥状態についてと、最小のルートのためのこれら可能な３方向についての情報を持つ。
【００６９】
次のフェーズでは、ルート選択が実行される。この決定のために、本発明では、以下に示す極性条件ａ、ｂ、ｃのセットが採用され、欠陥耐性と、欠陥の有無によらず高いパフォーマンスを保証する。
【００７０】
ａ．選択された方向は、最小パスを確実にし、ルート選択において、高い優先度を与えられる。
【００７１】
ｂ．方向は、大きな次の期待するパスの変化を持って、選択される。
【００７２】
ｃ．輻輳状態は、最も低い優先度が与えられる。
【００７３】
これらの優先度に基づき、LAFTは、欠陥制御モジュール２０から受信される次のノードの欠陥状態を読み、可能な非欠陥の最小方向の数をチェックする。３つの可能な方向が最小の時で、同じ方向の変化を有する時、ルート選択は、各出力ポートの輻輳に依存して行われる。
【００７４】
[要求に応じたバイパスリンク]
図５は、基準の７×７クロスバー１３における欠陥の数が増加する度に、追加の回避チャネルを与える、要求に応じたバイパスリンクのメカニズムを示す。
【００７５】
図５において、２つのバイパスリンク１３１、１３２は、実施例構成である。この図５において示されるクロスバーサブコントローラ（cntrl unit）１７は、クロスバーリンク状態をチェックし、一つ又はいくつかのリンクにおいて欠陥が検知される場合、フラグ（Faulty_Cross：欠陥クロス）を欠陥制御モジュール２０に送り、欠陥クロスバーリンクを不能にさせ、適切な数のバイパスリンクを可能にさせる。
【００７６】
容易なアプローチは、全てのクロスバーに対して指定のバイパスリンクを与えることである。この態様において、欠陥耐性及びパフォーマンスの両方が保証される。なぜならば、入力ポートの要求は、基準の７×７クロスバー１３の全ての基準の７×７クロスバーリンクが欠陥であっても、共有しないためである。しかし、この方法は、全クロスバーを二重にすることと同じであり、従って、追加の領域及び電力消費が確実に生じる。さらに、欠陥率が小さい時は、２又は３個のバイパスリンクのみで、欠陥クロスバーリンクの要求に十分対応できる。
【００７７】
この事実に従えば、本発明において、歩進アプローチが実行され、使用ベンチマーク及び推定欠陥率が、分析される。バイパスリンクの数は、パフォーマンスが一定あるいは殆ど変化しない時まで、歩進される。
【００７８】
バイパスリンクの数は、大変重要であり、領域及び電力消費を少なくするために、可能な限り、最小にすべきである。したがって、システムに既に存在する不使用のクロスバーリンクが利用される。
【００７９】
これらリンクは、基本的にネットワークの端に位置し、隣接するノードがない。したがって、対応するクロスバーは不使用である。この最適化を伴って、重要な領域及び電力の削減が可能に成り、一方、パフォーマンスを最大に維持することができる。
【００８０】
[欠陥制御モジュール（ＦＣＭ）２０]
欠陥制御モジュール（ＦＣＭ）２０は、本発明の主要要素の一つである。これは、３つの主要要素、即ちルータ間リンク、入力バッファ、及びクロスバーの全ての種類の欠陥の回復を管理するからである。ルータ間リンクから始め、各ルータのリンク状態とその隣接ルータ欠陥状態が、 “リンク状態”と名付けられた小さなアレイに格納される。
【００８１】
これらの情報は、常に、LAFTルーティングモジュール８に送られ、次のノードに対応する“次のポート”の選択の間、使用される。入力ポートのために、予測テーブル１０が、先に説明したように、必要とされるとき、他のバッファ資源の割当を扱う。しかし、全てのバッファ資源が欠陥であり、もはやフリッツを受け付けることができないとき、欠陥制御モジュール２０が、ＲＡＢコントローラ９０から（図１に示す）“バッファ 欠陥” 信号を受信する。
【００８２】
この“バッファ 欠陥” 信号を受信するとき、欠陥制御モジュール２０は、入力ポート全体を不能にして、動的パワーを削減する。同時に、欠陥制御モジュール２０は、欠陥バッファに接続されたリンクをフラグして“リンク状態アレイ”を更新する。これらの情報は、常に全ての隣接ノードにおける欠陥制御モジュール２０に送られる。 
【００８３】
最後に、クロスバー１３において、欠陥を扱うために、欠陥制御モジュール２０は、後に詳細を説明するように、３つの主要タスクを有する。
【００８４】
１）(図１に示す)制御（cntrl）ユニット１７から受信する情報に応じて、“Crss_link”状態レジスタ２２を更新する。
【００８５】
２）検出された欠陥の数に応じて、“バイパスリンク”１３１、１３２の適切な数を稼働し及び非稼働にする。
【００８６】
３）欠陥クロスバーリンクについて、“Sw_req_cntrl” １５に通知し、スイッチ配置部１６に送る前に、要求を変えることができる。
【００８７】
図１に示す様に、制御ユニット１７は、ベースライン７ｘ７クロスバー１３と追加の“バイパスリンク”１２との間の素子である。この制御ユニット１７の第１の役割は、クロスバー１３における欠陥の存在を検知して、その欠陥の状態について欠陥制御モジュール２０への通知を継続する。欠陥制御モジュール２０は、この入力する欠陥情報をモニタし、レジスタ２１に“クロスリンク”状態と名付けて格納する（図１）。
【００８８】
欠陥が検出される時、欠陥制御モジュール２０は、同時に３つの信号を送信する。：制御ユニット１７に対する２つは、バイパスリンクの一つを有効にし、欠陥クロスバーリンクを不能にする。そして、第２の一つは、“スイッチ要求 制御Sw_req_cntrl“ ユニット１５に送られ、フリッツが欠陥クロスバーリンクに要求することを阻止し、その代わりに、“バイパスリンク：Bypass_links” の一つを使用することの許可を求める。
【００８９】
欠陥の数が増加するとき、欠陥制御モジュール２０は、公平な方法で、可能なバイパスリンクに異なる要求を配布することを管理する。一方、制御ユニット１７は、欠陥制御モジュール２０から受信する信号に応じて、電力削減のためにクロックゲート技術を用いてバイパスリンクを有効にしたり無効にしたりする役割を有する。これは、クロスバー１３が有効である時、バイパスリンクがスリープ状態とされて動的電力を削減し、欠陥が検出されると、制御ユニット１７は、欠陥制御モジュール２０からの情報に応じて、適切な数のバイパスリンクを起こすことを意味する。制御ユニット１７は、マルチプレクサーとディマルチプレクサーで構成される。ディマルチプレクサーは、欠陥クロスバーリンクに代わり、起動された“バイパスリンク”に入力フリッツを再仕向けするために使用され、マルチプレクサーは、基準クロスバー１３と“バイパスリンク”間を切り替える機能を有し、フリッツの次の隣接ノードへ通過させる。
【００９０】
図６は、本発明に従う３Ｄ欠陥耐性ＮｏＣ（3D-FTNoC）の動作を示す図である。この図に示すように、3D-FTNoCは、３つの主要なパイプラインステージI、II、IIIを含む。最初のパイプラインステージIは、バッファ書き込みステージであり、３つの主要要素が並列に以下の様に働く。
【００９１】
１）ＲＡＢメカニズム９のＲＡＢコントローラ９０は、上記したように、デッドロックと入力バッファ１１の欠陥状態をモニタする。
【００９２】
２）予測テーブル１０は、それぞれの入力ポート１−７の入力バッファ１１に付属のプローブ（Prb0-Prb6）１４からトラフィック情報を受ける。
【００９３】
３）スイッチ調整コントローラ（Sw-reqcntrl）１５は、入力フリッツから“次のポート：Next-port”の識別子を読み、スイッチ配置器１６に対し、“スイッチ要求：sw-req”信号を発行する。
【００９４】
第２のパイプラインステージIIは、ルーティング計算／スイッチ配置ステージである。このステージにおいて、二つの主要処理が同時に行われる。第１の処理は、欠陥制御モジュール（FCM）２０における“リンク状態”レジスタ２１から受信される信号に応じて、LAFTルーティングモジュール８により実行される次のノードに対する“次のポート”の計算である。第２の処理は、入力として、異なる“スイッチ要求信号”を有するスイッチ配置器１６により管理される異なる入力ポートからの異なる要求間のスケジューリングである。出力として、スイッチ配置器１６は、要求された出力ポートの使用を許可する“スイッチ許可”信号と、スケジュール結果についての情報を有するクロスバー１３に対する“クロスコントロールCrss_contrl”信号を発行する。 
【００９５】
これら二つのステージI、IIの並列化は、本発明に従うシステムが依拠するルックアヘッド（Look ahead）により達成できる。この種のルーティングで、従来システムにおいては通常直列に実行される二つのステージIとII間の従属性は、除去することが可能である。
【００９６】
最後に、第３のパイプラインステージIIIとしてクロスバー交叉ステージにおいて、フリッツは、入力ポート１-７の入力バッファ１１から取り込まれ、適切な隣接ノードに送られる。図６に見られるように、欠陥制御モジュール２０は、その主の機能が異なるルータの素子間の通信を制御し、確立することであるので、三つのパイプラインステージI、 II、 IIIに沿って、異なるタスクを実行する。
【００９７】
本発明によるアーキテクチャの新規性の理解のために、図７は、本発明のアーキテクチャと比較される、最もポピュラーなシステムに使用される従来のルータのタイムチャートを示す。
【００９８】
この従来システムについての最初のコメントは、欠陥検知あるいは、回復のいずれのための要素が見当たらない場合、欠陥耐性支持を欠くということである。さらに、図７に見られるように、図６に示す本発明の３つのステージの代わりに、５つのパイプラインステージI-Vがある。
【００９９】
第１のステージは、本発明のシステムにおけると基本的に同様の機能を有するバッファ書き込みステージIと同じである。しかし、単一バッファ１１を使用する代わりに、仮想チャネル（VCs）が用いられ、デッドロック回避要件を満足させる。ＶＣｓの数は、システムアーキテクチャ及び、一般的に２乃至４つのＶＣｓ間で変えることのできるルーティングアルゴリズムに依存する。
【０１００】
次のステージIIは、ルーティング演算であり、大部分のシステムが静的なXYZルーティングあるいは、後者に基づく他のルーティングを採用する。ルックアヘッドルーティングがないために、次の２つのステージは、XYZルーティングモジュールから結果を受けなければ動作できない。
【０１０１】
第３のステージIIIは、仮想チャネル配置ステージである。ＶＣｓの使用は、追加のクロック周期を付加する調整が必要である。したがって、全てのパイプラインステージが異なるＶＣｓ間の調整のために関与する。図７と比較すると、本発明のシステムは、デッドロック回避に使用されるＲＡＢモジュールのためであるこのステージを削除している。
【０１０２】
ＶＣが許可を与えた後、図６に示す本発明と同じであるスイッチ配置ステージIVに切り替わる。しかし、唯一異なることは、ルーティング演算ステージIIと独立に行われることである。そして、本発明のシステムに対するように並行しては実行されない。最終的に、最後のステージＶ（クロスバー交叉）において、クロスバー１３は、スイッチ配置器１６から受信される調整結果に従い、フリッツの隣接ノードへの転送を行う。
【図４】
2015119387.tif 000003
【図１】
2015119387.tif 000004
【図２】
2015119387.tif 000005
【図３】
2015119387.tif 000006
【図３Ａ】
2015119387.tif 000007
【図３Ｂ】
2015119387.tif 000008
【図３Ｃ】
2015119387.tif 000009
【図３Ｄ】
2015119387.tif 000010
【図３Ｅ】
2015119387.tif 000011
【図５】
2015119387.tif 000012
【図６】
2015119387.tif 000013
【図７】
2015119387.tif 000014
【手続補正書】
【提出日】平成26年3月12日(2014.3.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数コアのチップ上のネットワークのためのオンデマンドのバイパスリンクに基づく誤り耐性ルータ、前記ルータを有する２又は３次元ＩＣ、及び前記誤り耐性ルータの制御方法に関する。
【背景技術】
【０００２】
２又は３次元ＩＣに用いられるマルチコアチップ（ＣＭＰ）構造において、ＮｏＣ（ネットワーク-オン-チップ）は、プロセッサノード及びそのプライベート(個別)キャッシュを、共用キャッシュとメモリコントローラに接続する。ＮｏＣは、また、インタラプト(中断)リクエストのような他の制御トラフィックを伝送する。
【０００３】
そのような構造において、ルータは、各ノードに存在して、パイプラインリンクでコアを隣接のコアと接続する。ノード間のコミニュケーションユニットは、パケットあるいはフリッツ(Flit)であり、パケットは、リンク幅に等しいフリッツ又はユニットに分割される。
【０００４】
三次元ＩＣ(３Ｄ-ＩＣ)は、いくつかのウェハを積み重ねて形成され、ワイヤの長さ及び遅延を短縮する。３Ｄ-ＩＣにおいて、複数のコアが、それぞれのウェハに配置して備えられ、そして、複数のルータがそれぞれのコアに対して備えられている。
【０００５】
それぞれのルータは、“三次元ネットワークオンチップ(３Ｄ-ＮｏＣ)”システムと称される３Ｄ-ＩＣ上のネットワークシステムを通して複数のコアを接続する。
【０００６】
３Ｄ-ＮｏＣのネットワーク形態が、近年研究されて来ているが、三次元ネットワークオンチップ（３Ｄ-ＮｏＣ）システムにおける誤り耐性に取り組んだ研究は少ない。研究は、目標システム、誤りのタイプ、あるいは誤りをどのように扱うか（例えば、ルーティングアルゴリズムあるいは構造解法を用いて）に依存して分類することができる。
【０００７】
提案された誤り耐性３Ｄ-ＮｏＣ解法のいくつかは、生産を改善するためのスルーシリコンビア（Through-Silicon-Vias：TSVs)において生じる永久誤りに焦点を当てている。例えば、それらのいくつかは、スペアTSVパッド挿入：spare TSV pads insertion（非特許文献１）、あるいはシリアライゼーション：serialization（非特許文献２）に基づくものである。
【０００８】
他の解法は、誤り耐性ルーティングアルゴリズムを適用してリンク誤りのみに焦点を当てている。既に存在する解法（非特許文献3-6）の大半は、ルーティングテーブルに基づき、周囲の誤りリンクの情報を格納し、デッドロックの発生を回避する。それらは、仮想チャネル(ＶＣｓ)を用いる(非特許文献７)。他は、ＶＣｓの使用を回避し、その代わりに転換-モデルルーチングを用いてデッドロックを回避するものであった（非特許文献８）。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願公開第２０１２／０１５５４８２号明細書
【非特許文献】
【００１０】
【非特許文献１】I. Loi, Subhasish Mitra, Thomas H. Lee, Shinobu Fujita, and Luca Benini. A low-overhead fault tolerance scheme for TSV-based 3D network-on chip links. In ICCAD 08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, pages 598-602, 2008
【非特許文献２】S. Pasricha. Exploring serial vertical interconnects for 3D ICs. In DAC 09: Proceedings of the 46th Annual Design Automation Conference, pages 581-586, New York, NY, USA, 2009. ACM
【非特許文献３】Ch. Feng. M. Zhang, J. Li. J. Jiang. Z. Lu and A. Jantsch. A Low-overhead Fault-Aware Deflection Routing Algorithm for 3D Network-on-Chip. IEEE Computer Society Annual Symposium on VLSI, pages 19-24. July 2011
【非特許文献４】Y. Li Shietung Peng, and Wanming Chu. Adaptive box-based efficient fault-tolerant routing in 3D torus. pages 71 -77, 2005
【非特許文献５】Ch. Feng. Z, Lu, A. Jantsch, J. Li and M. Zhang. A Reconfigurable Fault-tolerant Deflection Routing Algorithm Based on Reinforcement Learning for Network-on-Chip. The 3rd International Workshop on Network on Chip Architectures, pages 11-16, December 2010
【非特許文献６】D. Xiang, Y. Zhang and Y. Pan. Practical Deadlock-Free Fault-Tolerant Routing Based on the Planar Network Fault Model. IEEE Transactions on Computers, 58(5):620-633. May 2009
【非特許文献７】W. J. Dally. Virtual-channel flow control. IEEE Trans. on Parallel and Distributed Systems, 3(2): 194-205,March 1992
【非特許文献８】S. Pasricha and Y. Zou. A Low Overhead Fault Tolerant Routing Scheme for 3D Networks-on-Chip. The 12th International Symposium on Quality Electronic Design, pages 1-8, March 2011
【非特許文献９】T. Lehtonen, P. Liljeberg and J. Plosila. Online Reconfigurable Self-timed links for Fault Tolerant NoC. VLSI Design, (2007): 1-13, 2007
【非特許文献１０】DeOrio, A. et. al., A Reliable Routing Architecture and Algorithm for NoCs. IEEE Transactions on CAD of Integrated Circuits and Systems. May 2012, pp. 726-739
【非特許文献１１】A. Ben Ahmed and A. Ben Abdallah. Architecture and Design of High-throughput, Low-latency, and Fault-Tolerant Routing Algorithm for 3D-Network-on-Chip (3D-NoC). The Journal of Supercomputing, DOI:10.1007/s 11227-013-0940-9
【非特許文献１２】A. Ben Ahmed and A. Ben Abdallah. Fault-tolerant Routing Algorithm with Deadlock Recovery Support for 3D-NoC Architectures. The 7th IEEE International Symposium on Embedded Multicore SoCs. September 2013
【非特許文献１３】A. Ben Abdallah, Multicore Systems-on-Chip: Practical Hardware/Software Design, 2nd Edition, Publisher: Springer, (2013), ISBN-13: 978-9491216916
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上記に説明したように、３Ｄ-ＮｏＣシステムにおける誤り耐性問題を述べている既存の種々の解法に拘わらず、以下に述べるようにいくつかの問題を依然として残している。
【００１２】
第一に、いくつかの解法は、永久誤りのみに焦点を当て、他のタイプの誤りを考慮していなかった。しかし、非特許文献９に述べられているように、誤りの大半（８０％）は、過渡的誤りにより生じ、残りの誤りが、主に永久的並びに間欠的な誤りに基づくものである。
【００１３】
第二に、多くの解法は、リンク誤りに焦点を当てていた。しかし、非特許文献１０によると、入力バッファ及びクロスバーは、それぞれ８０％、１０％に達する、３Ｄ-ＮｏＣシステムにおいて大きな領域を占めている。一方、残りの素子のそれぞれは、ルータ全領域の３％を超えない。これは、入力バッファ及びクロスバーにおける誤りが、より大きな重要性を与えられるべきである事を意味している。さらに、信頼できる解法は、そのような種類の誤りを扱うことが出来なければならない。
【００１４】
第三に、既に提案されている研究は、デッドロックの発生を回避するためにＶＣｓに基づいている。ＶＣｓは、システムがデッドロックに繋がらないことを保証する。しかし、それらは、調整を行うために要求される待ち時間の不利に加えて、ハードウエアの複雑性という点で高価となる調整に基づいている。転換モデルに基づくルーティングアルゴリズムは、ＶＣｓの使用を必要としない。しかし、非最小の性質は、システムのスループットに影響を与える不要のクロックサイクルを結果として必要とする。
【００１５】
上記を要約すると、従来システムは以下の問題点を有している。
【００１６】
第一に、従来システムは、永久誤りのみに焦点をあて、他の誤りタイプを考慮していなかった。しかし、ＮｏＣにおける誤りの大半は、過渡的誤りにより生じる、一方、残りの誤りは、主に永久的及び間欠的誤りによる。
【００１７】
大半の従来の解法は、リンク誤りに焦点を当てていた。しかし、２Ｄ又は ３Ｄ-ＮｏＣシステムにおいて、入力バッファ及びクロスバーが大きな領域を占めており、よって、入力バッファ及びクロスバーにおける誤りに大きな重要性を与えられるべきである。
【００１８】
さらに、デッドロックの発生が、ＶＣｓに基づき回避される。ＶＣｓは、システムのデッドロック回避を保証するが、ハードウエアの複雑性という点で高価となるという判断に基づいている。
【００１９】
したがって、本発明の目的は、上記問題を３つの誤りタイプ（過渡的、間欠的及び永久的）の対処により解決される誤り耐性ルータ、及び前記誤り耐性ルータを使用するＩＣを提供することである。提案する解法は、前記提案する誤り耐性ルータを使用する２Ｄ又は３Ｄ−ＩＣに備えられるリンク、入力バッファ、及びクロスバー回路における異なるタイプの誤りに向けられている。
【課題を解決するための手段】
【００２０】
本発明において、使用されるランダムアクセスバッファ技術（ＲＡＢ）は、バッファにおけるデッドロックの理由であるフリッツを第一に検出するスマートコントローラ(RAB cntrl)に基づく。検出メカニズムは、ある時間周期の後、もし処理される要求が許可され
ないと、フラグを発行して、前記要求を破棄するタイマーに依存する。 
【００２１】
そして、ＲＡＢは、バッファにおけるいくつかのスロットをフリーにし、従属性を断つことが許可される他のフリッツを求める。ＲＡＢは、各入力バッファにおいて一時に一要求を扱う。したがって、ＶＣｓに対する場合のように、調整の存在はもはや必要がない。さらに、ＶＣｓの数が増えると、ＶＣ配置の複雑さも増える。そして、効果的なスケジューリング方法の利用が重要となる。しかし、ＲＡＢの場合は、バッファの深さは、そのパフォーマンスに影響を与えない。対照的に、非ブロックのフリッツを探す確率が高まり、速いデッドロックの回復をさせる。
【００２２】
本発明に従う第一の技術側面は、積層ウェハを有する３Ｄ-ＩＣに備えられる複数のコアの各々に対応して備えられる誤り耐性ルータであって、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート（１−７）と、
前記複数の入力ポート（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する誤り制御モジュール（２０）を有し、
前記複数の入力ポート（１−７）のそれぞれが、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット誤りを検知する誤り検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、
前記誤り検知回路（９１）で前記入力バッファ（１１）のスロット誤りを検知する時、前記ランダムアクセスバッファ（９）は、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記誤り制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を格納し、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する。
【００２３】
本発明に従う第２の技術側面は、それぞれ複数のコアと、前記複数のコアのそれぞれに対応するルータを有する、積層されたウェハで形成された３Ｄ-ＩＣであって、
それぞれのルータが、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート（１−７）と、
前記複数の入力ポート（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する誤り制御モジュール（２０）を有し、
前記複数の入力ポート（１−７）のそれぞれが、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット誤りを検知する誤り検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、
前記誤り検知回路（９１）で前記入力バッファ（１１）のスロット誤りを検知する時、前記ランダムアクセスバッファ（９）は、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記誤り制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を格納し、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する。
【００２４】
本発明に従う第３の技術的側面は、３Ｄ-ＩＣを形成するウェハに備えられた複数のコ
アの各々に対応して有する誤り耐性ルータの制御方法であって、
第１の処理ステージとして、
ランダムアクセスバッファ（９）により、それぞれの入力ポート（１−７）の入力バッファ（１１）のデッドロック状態と誤り状態を検知し、
入力ポート（１−７）のそれぞれの入力バッファ（１１）に付属のプローブからトラフィック情報を受信し、
入力フリッツから次のポートの識別情報を取得し、スイッチ配置器（１６）にスイッチ要求信号を送信し、
第２の処理ステージとして、
誤り制御モジュール（２）から受信した信号に基づき、ルーティングモジュールにより実行される次のノードに対する次のポートを計算し、
前記スイッチ配置器（１６）により管理される異なるポートからの要求間のスケジューリングを行い、
前記スイッチ配置器（１６）から要求された出力ポートの使用を許可する要求信号と制御信号を、スケジューリング結果の情報を持つクロスバー（１３）に送り、
第３の処理ステージとして、
入力バッファ（１１）からの送信フリッツをチェックし、適切な隣接ノードに送信する。
【発明の効果】
【００２５】
大半の従来の３Ｄ-ＮｏＣシステムは仮想チャネル（ＶＣｓ)に基づき、デッドロックの発生を回避する。ＶＣｓは、システムのデッドロックなしにすることを保証する。しかし、これらの利点は、そのような技術を実装する際の複雑さに加え、高次の追加的ハードウエアを伴う。さらに、ＶＣｓは、複数の要求を扱うために、調整を有することが必要となり、その結果、余分なパイプラインステージの追加（通常、ＶＣ配置器として参照される）、及び従って追加的クロックサイクルを必要とする。このように、この待ち時間は、システム全体のスループットに重要な影響を与える。
【００２６】
本発明において、使用されるランダムアクセスバッファ技術（ＲＡＢ）は、フリッツが、バッファのデッドロックの理由であることを、先ず検出するスマートコントローラ（RAB cntrl）に基づく。検出メカニズムは、ある時間周期後、処理される要求が許可されないと、フラグを発行し、その要求を破棄するタイマーに基づいている。
【００２７】
そして、ＲＡＢは、バッファにおけるいくつかのスロットをフリーにして、従属性を断つために、要求が許可される他のフリッツを求める。ＲＡＢは、各入力バッファにおいて一時に一要求を処理する。したがって、ＶＣｓに対する場合のように、調整の存在はもはや必要がない。さらに、ＶＣｓの数が増えると、ＶＣ配置器の複雑さも増える。そして、効果的なスケジューリング方法の適用が必須となる。しかし、ＲＡＢの場合には、バッファの深さは、そのパフォーマンスに影響を与えない。対照的に、非ブロックのフリッツを探す確率が高まり、速いデッドロックの回復をさせる。
【図面の簡単な説明】
【００２８】
【図１】本発明に従い、提案する３Ｄ誤り耐性OASIS-ＮｏＣルータ構造のブロックダイヤグラムを示す図である。
【図２】ランダムアクセスバッファ９のブロックダイヤグラムを示す図である。
【図３】予測テーブル１０を説明をする概略図である。
【図３Ａ】システムがスタートする時のカウンタ値を示す図である。
【図３Ｂ】第１の１００サイクル後の出力された入力フリッツの数を示す図である。
【図３Ｃ】平均フリッツ到達の計算を示す図である。
【図３Ｄ】最良候補バッファの決定を示す図である。
【図３Ｅ】最新の最良候補バッファの送信を示す図である。
【図４】ルックアヘッド誤り耐性ルーティングのアルゴリズムを示す図である。
【図５】バイパスリンク-オンデマンドメカニズムを示す図である。
【図６】本発明に従う３Ｄ誤り耐性ＮｏＣ（3D-FTNoC）の動作におけるタイムチャートを示す図である。
【図７】最も一般に使用される従来のルータのタイムチャートを示す図である。
【発明を実施するための形態】
【００２９】
本発明の実施例を添付図面に従い、説明する。実施例は、発明をより良く理解するためのものであり、発明の保護の範囲がこの実施例に制限されるものではない。
【００３０】
複数の小さなウェハの積み重ねにより形成される３Ｄ-ＩＣについて主として説明が行われるが、本発明は、一つのウェハに形成された複数のコアと、前記複数のコアを接続するネットワークを有して形成される２Ｄ-ＩＣにも適用可能である。
【００３１】
[３Ｄ-誤り耐性ルータ-ＮｏＣアークテクチャ]
図１は、本発明に従い、提案する３Ｄ-誤り耐性-OASIS-ＮｏＣルータ構造のブロックダイヤグラムを示す。
【００３２】
図１において、ＮｏＣルータは、それぞれ積層されたウェハに形成されたコアの対応する方向からの入力を受信する、ローカル入力ポート１、ノース入力ポー２、イースト入力ポート３、サウス入力ポート４、ウエスト入力ポート５、アップ入力ポート６、及びダウン入力ポート７である複数の入力ポートユニットを有する。
【００３３】
入力ポートユニット１-７の各々は、非特許文献１１で先に提案された、誤りリンクを扱う先読み誤り耐性（ＬＡＦＴ）ルーティングアルゴリズム８を有する。ＬＡＦＴルーティングアルゴリズム８に加えて、本発明に従い、更に誤り耐性を支えるために、二つの主要コンポーネントが用いられる。
【００３４】
すなわち、入力バッファ１１の誤りのための誤り制御モジュール２０内に位置するトラフィック予測ユニットの一エレメントである予測テーブル（ＰＴ）１０を有して用いられるランダムアクセスバッファ（ＲＡＢ）メカニズム９が、入力ポートユニット１−７の各々に備えられる。さらに、クロスバー１３における誤りのためのバイパスリンクオンデマンド（ＢＬＯＤ）１２が備えられる。
【００３５】
ランダムアクセスバッファ（ＲＡＢ）メカニズム９は、ＲＡＢコントローラ９０に加えて、デッドロック管理機能、誤り管理機能を有する。
【００３６】
ランダムアクセスバッファ（ＲＡＢ）メカニズム９のＲＡＢコントローラ９０は、対応する入力バッファの誤り状態を規則的にモニタする。誤りスロットの存在を検知する時、残りのスロットが占有されているか、否かをチェックする。
【００３７】
残りのスロットが占有されている場合は、ＲＡＢコントローラ(cntrl)９０は、予測テーブル１０に、単一ビットの“バッファフラグ：Buffer-flg”信号を送る。この予測テーブル１０は、残りの入力バッファのそれぞれのトラフィック負荷についての情報を既に有していて、“最良−バッファ：Best-buff”信号を、RAB-コントローラ９０に送り返す。RAB-コントローラ９０は、パケットから分割され、リンク幅に等しい入力フリッツを新しく選択された入力バッファにリダイレクトする。 
【００３８】
入力バッファにおいて先に検知された誤りが解消された場合、あるいは入力バッファが殆ど空いていて、他の入力フリッツを受けることができる場合、“バッファフラグ：Buffer-flg”信号が０に戻され、予測テーブル１０に、他の入力バッファ資源を使用する必要がないことを通知する。そして、先の誤りバッファが新しい入力フリッツの受信、及び格納を開始する。
【００３９】
[ランダム アクセス バッファコントローラ（RAB buffer cntrl）９]
図２は、提案するランダムアクセスバッファ９のブロックダイヤグラムを示す。ランダムアクセスバッファ９は、先に上記非特許文献１２にデッドロックフリーを確実にするための基本的、且つ低負荷解法として提案されていた。
【００４０】
本発明において、拡張されたランダムアクセスバッファが備えられて、ランダムアクセスバッファメカニズム（RAB mechanism）として、入力バッファ１１における過渡的、間欠的、及び永久的な誤りを検知し、回復することができる。
【００４１】
ランダムアクセスバッファ９は、二つの主たる並行したフェーズに分配される。第一のフェーズは、誤りの検出及び誤りの回復が行われることを意味する、局部的な処理である。第二のフェーズは、全体的な(即ち、ルータ全体における)処理であって、ランダムアクセスバッファ９が、予測テーブル（PT）１０で支持され、後に説明するように、システムのパフォーマンスを更に高める。
【００４２】
誤りの検知のために、図２に示す誤り検知回路９１が使用され、入力バッファ１１のバッファスロットの誤り状態のチェックを行う。誤り検知回路９１によりスロットの一つにおいて、誤りが検知される時、誤り検知回路９１は、“誤りスロット：faulty-slot”信号をバッファコントローラ（Buffer_Contrl）９０内のＲＡＢモジュール９２に送り、バッファコントローラ（Buffer_Contrl）９０内のＦＩＦＯ９３から書込アドレス“Wr_adr”、及び読出アドレス“Read_adr”を付与する時に、フラグを立てられたスロットを考慮させる。 
【００４３】
誤りスロットの記録を維持するために、n2ビットアイテム（nは、バッファの深さ）を扱うアレーから成るステータスレジスタが、ＲＡＢモジュール９２に備えられる。
【００４４】
ステータスレジスタに保持される各アイテムの値が、“００”であるとき、対応するフリッツがデッドロックを生じてなく、バッファスロットが誤りでないことを通知する。“０１”であるとき、バッファスロットが誤りでないが、扱われるフリッツの要求がデッドロックを起こしていることを示す。最後に、誤りが対応するバッファスロットで検知される場合、ステータスレジスタにおけるエレメントが、“１１”に更新される。したがって、スロットは、（壊れたスロットを調べるための追加的待ち時間を避けるために）使われることも、入力するフリッツを格納することもできない。
【００４５】
[予測テーブル（ＰＴ）１０] 
図３は、トラフィック予測ユニット１００に備えられる予測テーブル１０の使用を説明する簡単な例を示す。しばしば生じる興味あるケースは、所定の入力バッファ１１が、いくつかの誤りスロットを有する場合、残りのスロットが、他のフリッツで占有され、同じルータの他の入力バッファが空になるということである。パフォーマンスを拡大し、全てのルータ資源を完全に使用するために、本発明においては、全ての入力ポート１-７において入力バッファ資源を共有させる技術を採用する。これは、入力バッファ１１が、（誤りスロットの存在、残りのスロットの占有のために、）更にフリッツを扱うことをできない時、入力フリッツを他の隣接する空きの入力バッファに振り向けて、速く到達先に送ることができることを意味する。
【００４６】
この目的を達成するために、使用可能な空き入力バッファ中で、振り向けたフリッツを受信する最良の候補を知ることが、非常に重要である。本発明において、図３に示す様に、予測テーブル（ＰＴ）１０が使用され、特定の時間周期で、それぞれの入力ポートのトラフィック負荷（信号５０）の情報を収集する。これらの情報は、ルータ内の入力バッファ１-７のそれぞれに付加されているモニタリングプローブ（Prb0-Prb6）１４から受信される。収集されたトラフィックのスナップショットが、各入力バッファにおける平均フリッツの到達を計算するために使用される。そして、予測テーブル１０が渋滞を生じさせないで、誤り入力バッファのフリッツを扱うことができる最良の入力ポートを決定することができる。
【００４７】
最良の入力バッファが選択されると（本実施例では、イーストバッファ３）、予測テーブル１０は、ＲＡＢコントローラ（RAB cntrl 0-6）９０から発行されるフラグ５１を待つ。図２に示すバッファ誤りは、バッファ（ノース入力ポート２の入力バッファ１１）が誤りであり、同時に一杯であることの情報を与える。この場合、予測テーブル１０は、ノース入力ポート２の対応する入力バッファに他の信号を返送し、新しい入力バッファを指定する（例えば、イースト入力ポート３の入力バッファ）、その入力バッファが破線矢印５２で示す様に、いくつかのスロットが開放になり、ノース入力ポート２の入力バッファが再び入力フリッツを受信できるまで、入力フリッツを受け入れる。
【００４８】
所定のパケットのいくつかのフリッツがバッファに格納され、それが誤りであり、一杯になっていると宣言される。そして、ＲＡＢメカニズム９に従い、このパケットの残りのフリッツが異なるバッファに格納される場合がある。このよう場合は、残りのフリッツが異なるバッファに格納されているので、これらのフリッツが順序通りに到達しない可能性がある。
【００４９】
結果として、到達ノードでは順序の並べ替え処理が必要となり、あるいは、残りのフリッツと同時に到達できるようにいくつかのフリッツに追加すべき遅延が生じる。本発明では、簡単な解決として、ヘッダである場合、振り向けフリッツのみをスタートさせる。この場合、このパケットの残りのフリッツは、ヘッダフリッツと同じバッファに格納される。この追加的規制に伴い、パケットのフリッツが追加のハードウエア／パワーの過負荷もパーマンスの劣化もなしに、パケットのフリッツが順序通りに到着する。
【００５０】
図３Ａ−３Ｅは、トラフィック予測ユニット１００の動作の詳細を示す図である。
【００５１】
図３Ａ-３Ｅにおいて、プローブ１-６は、ローカル（Local）プローブ、ノース（Nth）プローブ、イースト（Est）プローブ、サウス（Sth）プローブ、ウエスト（Wst）プローブ、アップ（Up）プローブ、及びダウン（Dwn）プローブにそれぞれ対応する。プローブ１-６のそれぞれは、キュー信号を用いて、新たなフリッツが入力バッファ１１に到達す
る都度、歩進するカウンタを有する。カウンタのカウント値は、１００サイクルで到達するフリッツの数を記憶することができる８ビットのレジスタに格納される。
【００５２】
トラフィック予測ユニット１００は、それぞれ８ビットサイズの７つの入力を受け入れできる予測テーブル１０を含む。それぞれの入力は、一つの入力ポートに割り当てられ、そのフリッツ到達率を格納する。
【００５３】
トラフィック予測ユニット１００は、以下のステップに従い動作する。
【００５４】
１）それぞれのプローブが、その値を出力し、１００サイクル毎（レジスタサイズを小さくするために）、予測テーブル１０に送る。
【００５５】
２）トラフィック予測ユニット１００は、プローブから来た値と既に予測テーブル１０に有る値とを使用して１００サイクル（フリッツ／１００サイクル）でフリッツの平均値を計算する。
【００５６】
３）新しい平均値が予測テーブル１０に更新される。
【００５７】
４）トラフィック予測ユニットとは、７つの入力ポートの平均をチェックし、最良の候補と考えられる最小値を選択する。
【００５８】
５）ＲＡＢが、フルバッファにおいて誤りがあることのフラグ（Buffer_flg信号）を立てるとき、トラフィック予測ユニット１００が計算した、待避チャネルとして用いられる最良の候補を送る。
【００５９】
ここで、上記ステップに従い、トラフィック予測ユニット１００における動作の例を説明する。
【００６０】
図３Ａにおいて、システムがスタートすると、プローブのカウンタの値と予測テーブル１０の入力がゼロに初期化される。
【００６１】
そして、図３Ｂにおいて、最初の１００サイクルの後、入力フリッツの数が、プローブから出力され、トラフィック予測ユニット１００に送られ、平均値がカウントできないので、直接に予測テーブル１０に格納される。同時に、プローブのカウンタは、０にリセットされる。ウエストが次いで、フリッツの平均が、最小値である１０であるとき、最良の候補バッファとして計算される。
【００６２】
図３Ｃにおいて、１００サイクル経過毎に、プローブはその値を出力し、トラフィック予測ユニット１００に送る。トラフィック予測ユニット１００は、所定の入力ポートから入力情報を読み取り、予測テーブル１０における対応する値を読み、平均フリッツの到達値を計算する。
【００６３】
ついで、図３Ｄにおいて、プローブのカウンタは、再びゼロにリセットされる。予測テーブル１０の入力は、計算された平均値で更新される。予測テーブル１０における最小値が計算され、最良の候補バッファが決定される（その平均値が最小の３５であるローカルが、最良の候補である）。 
【００６４】
図３Ｅにおいて、トラフィック予測ユニット１００が、（バッファ１１が空きがなく、誤りを有することを通知する、図１参照）ＲＡＢモジュール９からのバッファフラグ（Buffer_flg）信号を受信するとき、トラフィック予測ユニット１００は、入力フリッツに対する代替の入力バッファとして使用される最新の最良の候補バッファを、フラグが立てられたバッファに送る。
【００６５】
[先読み（Look-Ahead）誤り耐性ルータ（“LAFT”）]
先読みルーティングの利点を保持するために、先に提案された先読み誤り耐性（LAFT）[非特許文献１１]が、リンク状態を考慮して次のノードに対するルーティングの決定を実行し、図４のアルゴリズム１に示されるように、最良の最小パスを選択する。
【００６６】
誤りコントロールモジュール（ＦＣＭ）２０から受信した誤り情報（図１における誤りリンク）がLAFTが実行される各入力ポートにより読まれる。
【００６７】
このアルゴリズムの第１のフェーズは、次のノードアドレスを計算する。所定の最終到達先にフリッツを送りたい所定のノードに対して、X、Y、Z次元のそれぞれを通して最大３つの可能な方向が存在する。
【００６８】
第２のフェーズでは、LAFTは、現在と到達先ノードの両方のX、Y、Z座標を同時に比較して、この３方向の計算を実行する。これらの方向の計算と同時に、誤り制御モジュール２０は、フリッツから次のポートの識別子を読み、対応する入力ポートに適切な誤り情報を送る。この第２のフェーズ終わりまでに、LAFTは、次のノードの誤り状態についてと、最小のルートのためのこれら可能な３方向についての情報を持つ。
【００６９】
次のフェーズでは、ルート選択が実行される。この決定のために、本発明では、以下に示す優先度付け条件ａ、ｂ、ｃのセットが採用され、誤り耐性と、誤りの有無によらず高いパフォーマンスを保証する。
【００７０】
ａ．選択された方向は、最小パスを保証し、ルート選択において、高い優先度を与えられる。
【００７１】
ｂ．方向は、次に期待されるパスの広がりが最大のものが選択される。
【００７２】
ｃ．輻輳状態は、最も低い優先度が与えられる。
【００７３】
これらの優先度に基づき、LAFTは、誤り制御モジュール２０から受信される次のノードの誤り状態を読み、可能な非誤りの最小方向の数をチェックする。３つの可能な方向が最小で、且つ同じ広がりを有する時、ルート選択は、各出力ポートの輻輳に依存して行われる。
【００７４】
[要求に応じたバイパスリンク]
図５は、基準の７×７クロスバー１３における誤りの数が増加する度に、追加の回避チャネルを与える、要求に応じたバイパスリンクのメカニズムを示す。
【００７５】
図５において、２つのバイパスリンク１３１、１３２は、実施例構成である。この図５において示されるクロスバーサブコントローラ（cntrl unit）１７は、クロスバーリンク状態をチェックし、一つ又はいくつかのリンクにおいて誤りが検知される場合、フラグ（Faulty_Cross：誤りクロス）を誤り制御モジュール２０に送り、誤りクロスバーリンクを不能にさせ、適切な数のバイパスリンクを可能にさせる。
【００７６】
最も簡易なアプローチは、全てのクロスバーに対して指定のバイパスリンクを与えることである。この態様において、誤り耐性及びパフォーマンスの両方が保証される。なぜならば、入力ポートの要求は、基準の７×７クロスバー１３の全ての基準の７×７クロスバーリンクが誤りであっても、バイパスリンクを共有しないためである。しかし、この方法は、全クロスバーを二重にすることと同じであり、従って、追加の領域及び電力消費が確実に生じる。さらに、誤り率が小さい時は、２又は３個のバイパスリンクのみで、誤りクロスバーリンクの要求に十分対応できる。
【００７７】
この事実に従えば、本発明において、徐々に増加するアプローチが実行され、使用ベンチマーク及び推定誤り率が、分析される。バイパスリンクの数は、パフォーマンスが一定あるいは殆ど変化しない時まで、徐々に増加される。
【００７８】
バイパスリンクの数は、大変重要であり、領域及び電力消費を少なくするために、可能な限り、最小にすべきである。したがって、システムに既に存在する不使用のクロスバーリンクが利用される。
【００７９】
これらリンクは、基本的にネットワークの端に位置し、隣接するノードがない。したがって、対応するクロスバーは不使用である。この最適化によって、重要な領域及び電力の削減が可能に成り、一方、パフォーマンスを最大に維持することができる。
【００８０】
[誤り制御モジュール（ＦＣＭ）２０]
誤り制御モジュール（ＦＣＭ）２０は、本発明の主要要素の一つである。これは、３つの主要要素、即ちルータ間リンク、入力バッファ、及びクロスバーの全ての種類の誤りの回復を管理するからである。ルータ間リンクから始め、各ルータのリンク状態とその隣接ルータ誤り状態が、“リンク状態”と名付けられた小さなアレイに格納される。
【００８１】
これらの情報は、常に、LAFTルーティングモジュール８に送られ、次のノードに対応する“次のポート”の選択の間、使用される。入力ポートのために、予測テーブル１０が、先に説明したように、必要とされるとき、他のバッファ資源の割当を扱う。しかし、全てのバッファ資源が誤りであり、もはやフリッツを受け付けることができないとき、誤り制御モジュール２０が、ＲＡＢコントローラ９０から（図１に示す）“バッファ 誤り” 信号を受信する。
【００８２】
この“バッファ 誤り” 信号を受信するとき、誤り制御モジュール２０は、入力ポート全体を不能にして、動的パワーを削減する。同時に、誤り制御モジュール２０は、誤りバッファに接続されたリンクにフラグを立て“リンク状態アレイ”を更新する。これらの情報は、常に全ての隣接ノードにおける誤り制御モジュール２０に送られる。 
【００８３】
最後に、クロスバー１３において、誤りを扱うために、誤り制御モジュール２０は、次に詳細を説明するように、３つの主要タスクを有する。
【００８４】
１）(図１に示す)制御（cntrl）ユニット１７から受信する情報に応じて、“Crss_link”状態レジスタ２２を更新する。
【００８５】
２）検出された誤りの数に応じて、“バイパスリンク”１３１、１３２の適切な数を稼働し及び非稼働にする。
【００８６】
３）誤りクロスバーリンクについて、“Sw_req_cntrl” １５に通知し、スイッチ配置部１６に送る前に、要求を変えることができるようにする。
【００８７】
図１に示す様に、制御ユニット１７は、ベースライン７ｘ７クロスバー１３と追加の“バイパスリンク”１２との間の素子である。この制御ユニット１７の第１の役割は、クロスバー１３における誤りの存在を検知して、その誤りの状態について誤り制御モジュール２０への通知を継続する。誤り制御モジュール２０は、この入力する誤り情報をモニタし、レジスタ２１に“クロスリンク”状態と名付けて格納する（図１）。
【００８８】
誤りが検出される時、誤り制御モジュール２０は、同時に３つの信号を送信する。：制御ユニット１７に対する２つは、バイパスリンクの一つを有効にし、誤りクロスバーリンクを不能にする。そして、残りの一つは、“スイッチ要求 制御Sw_req_cntrl“ ユニット１５に送られ、フリッツが誤りクロスバーリンクに要求することを阻止し、その代わりに、“バイパスリンク：Bypass_links” の一つを使用することの許可を求める。
【００８９】
誤りの数が増加するとき、誤り制御モジュール２０は、公平な方法で、可能なバイパスリンクに異なる要求を配布することを管理する。一方、制御ユニット１７は、誤り制御モジュール２０から受信する信号に応じて、電力削減のためにクロックゲート技術を用いてバイパスリンクを有効にしたり無効にしたりする役割を有する。これは、クロスバー１３が有効である時、バイパスリンクがスリープ状態とされて動的電力を削減し、誤りが検出されると、制御ユニット１７は、誤り制御モジュール２０からの情報に応じて、適切な数のバイパスリンクを起こすことを意味する。制御ユニット１７は、マルチプレクサーとディマルチプレクサーで構成される。ディマルチプレクサーは、誤りクロスバーリンクに代わり、起動された“バイパスリンク”に入力フリッツを再仕向けするために使用され、マルチプレクサーは、基準クロスバー１３と“バイパスリンク”間を切り替える機能を有し、フリッツの次の隣接ノードへ通過させる。
【００９０】
図６は、本発明に従う３Ｄ誤り耐性ＮｏＣ（3D-FTNoC）の動作を示す図である。この図に示すように、3D-FTNoCは、３つの主要なパイプラインステージI、II、IIIを含む。最初のパイプラインステージIは、バッファ書き込みステージであり、３つの主要要素が並列
に以下の様に働く。
【００９１】
１）ＲＡＢメカニズム９のＲＡＢコントローラ９０は、上記したように、デッドロックと入力バッファ１１の誤り状態をモニタする。
【００９２】
２）予測テーブル１０は、それぞれの入力ポート１−７の入力バッファ１１に付属のプローブ（Prb0-Prb6）１４からトラフィック情報を受ける。
【００９３】
３）スイッチ調整コントローラ（Sw-reqcntrl）１５は、入力フリッツから“次のポート：Next-port”の識別子を読み、スイッチ配置器１６に対し、“スイッチ要求：sw-req”信号を発行する。
【００９４】
第２のパイプラインステージIIは、ルーティング計算／スイッチ配置ステージである。このステージにおいて、二つの主要処理が同時に行われる。第１の処理は、誤り制御モジュール（FCM）２０における“リンク状態”レジスタ２１から受信される信号に応じて、LAFTルーティングモジュール８により実行される次のノードに対する“次のポート”の計算である。第２の処理は、入力として、異なる“スイッチ要求信号”を有するスイッチ配置器１６により管理される異なる入力ポートからの異なる要求間のスケジューリングである。出力として、スイッチ配置器１６は、要求された出力ポートの使用を許可する“スイッチ許可”信号と、スケジュール結果についての情報を有するクロスバー１３に対する“クロスコントロールCrss_contrl”信号を発行する。 
【００９５】
これら二つのステージI、IIの並列化は、本発明に従うシステムが依拠する先読み（Look ahead）ルーティングにより達成できる。この種のルーティングで、従来システムにおいては通常直列に実行される二つのステージIとII間の従属性は、除去することが可能である。
【００９６】
最後に、第３のパイプラインステージIIIとしてクロスバー交叉ステージにおいて、フリッツは、入力ポート１-７の入力バッファ１１から取り込まれ、適切な隣接ノードに送られる。図６に見られるように、誤り制御モジュール２０は、その主な機能が異なるルータの素子間の通信を制御し、確立することであるので、三つのパイプラインステージI、 II、 IIIに沿って、異なるタスクを実行する。
【００９７】
本発明によるアーキテクチャの新規性の理解のために、図７は、本発明のアーキテクチャと比較される、最もポピュラーなシステムに使用される従来のルータのタイムチャートを示す。
【００９８】
この従来システムについての最初のコメントは、誤り検知あるいは、回復のいずれのための要素が見当たらない場合、誤り耐性支持を欠くということである。さらに、図７に見られるように、図６に示す本発明の３つのステージの代わりに、５つのパイプラインステージI-Vがある。
【００９９】
第１のステージは、本発明のシステムにおけると基本的に同様の機能を有するバッファ書き込みステージIと同じである。しかし、単一バッファ１１を使用する代わりに、仮想チャネル（VCs）が用いられ、デッドロック回避要件を満足させる。ＶＣｓの数は、システムアーキテクチャ及び、一般的に２乃至４つのＶＣｓ間で変えることのできるルーティングアルゴリズムに依存する。
【０１００】
次のステージIIは、ルーティング演算であり、大部分のシステムが静的なXYZルーティングあるいは、後者に基づく他のルーティングを採用する。先読みルーティングがないために、次の２つのステージは、XYZルーティングモジュールから結果を受けなければ動作できない。
【０１０１】
第３のステージIIIは、仮想チャネル配置ステージである。ＶＣｓの使用は、追加のクロック周期を付加する調整が必要である。したがって、全てのパイプラインステージが異なるＶＣｓ間の調整のために関与する。図７と比較すると、本発明のシステムは、デッドロック回避に使用されるＲＡＢモジュールのおかげでこのステージを削除している。
【０１０２】
ＶＣが許可を与えた後、図６に示す本発明と同じであるスイッチ配置ステージIVに切り替わる。しかし、唯一異なることは、ルーティング演算ステージIIと独立に行われることである。そして、本発明のシステムに対するように並行しては実行されない。最終的に、最後のステージＶ（クロスバー交叉）において、クロスバー１３は、スイッチ配置器１６から受信される調整結果に従い、フリッツの隣接ノードへの転送を行う。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＩＣに有する複数のコアのそれぞれに対応して備えられた誤り耐性ルータであって、
それぞれ対応するコアの方向からの入力を受ける様に形成された複数の入力ポート部（１−７）と、
前記複数の入力ポート部（１−７）の出力を、所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する誤り制御モジュール（２０）を有し、
前記複数の入力ポート部（１−７）のそれぞれに、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット誤りを検知する誤り検知回路（９１）と、
ランダムアクセスバッファ（９）を有し、 
前記誤り検知回路（９１）が前記入力バッファ（１１）のスロット誤りを検知する時、前記ランダムアクセスバッファ（９）が、他の残りのスロットが占有されているか否かをチェックし、
他の残りのスロットが占有されている場合、前記ランダムアクセスバッファ（９）は、前記誤り制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）が、トラフィック情報を格納していて、最良の入力バッファを選択して、ランダムアクセスバッファ（９）に通知する、
ことを特徴とする誤り耐性ルータ。
【請求項２】
請求項１において、
前記予測テーブル（１０）は、所定のタイミング周期で、前記複数の入力ポート部（１−７）の各々からトラフィック負荷情報を収集し、平均フリッツ到達を計算し、誤り入力バッファのフリッツを受け入れる最適の入力ポートを決定する、
ことを特徴とする誤り耐性ルータ。
【請求項３】
請求項１において、
さらに、前記クロスバー（１３）に対する複数のバイパス路（１３１、１３２）と、
前記クロスバー（１３）のリンク状態をチエックするクロスバー制御部（１７）を有し、
前記クロスバー制御部（１７）が、１又は複数のリンクの誤りを検出する時、前記誤り制御モジュール（２０）にフラグを送り、
前記誤り制御モジュール（２０）は、前記クロスバー誤りリンクを不能にして、適切な数の前記複数のバイパスリンク（１３１、１３２）を可能とする、
ことを特徴とする誤り耐性ルータ。
【請求項４】
請求項３において、
推定される誤り率を分析し、前記バイパスリンクの数が、実行処理が落ち着く、或いは変化のない状態になるまで増加される、
ことを特徴とする誤り耐性ルータ。
【請求項５】
請求項１−４のいずれか１項において、
前記ＩＣが、それぞれに複数のコアが形成された複数の積層ウェハで構成される３Ｄ−ＩＣであることを特徴とする誤り耐性ルータ。
【請求項６】
それぞれ複数のコアを備え、前記複数のコアに対応して複数の誤り耐性ルータを有する３次元ＩＣであって、
前記複数の誤り耐性ルータのそれぞれが、
それぞれ対応するコアの方向からの入力を受ける複数の入力ポート部（１−７）と、
前記複数の入力ポート部（１−７）の出力を所定の出力先に接続するクロスバー（１３）と、
予測テーブル（１０）を有する誤り制御モジュール（２０）を有し、
前記複数の入力ポート部（１−７）のそれぞれに、
入力バッファ（１１）と、
前記入力バッファ（１１）のスロット誤りを検知する誤り検知回路（９１）と、
ランダムアクセスバッファ（９）を備え、
前記誤り検知回路（９１）が前記入力バッファ（１１）のスロット誤りを検知する時、前記ランダムアクセスバッファ（９）は、他のスロットが占有されているかを判断し、
他のスロットが占有されている場合、前記誤り制御モジュール（２０）にフラグを送り、
前記予測テーブル（１０）は、トラフィック情報を保持していて、最良の入力バッファを選択して、ランダムアクセスバッファ部（９）に通知する、
ことを特徴とする３次元ＩＣ。
【請求項７】
請求項５において、
前記予測テーブル（１０）は、所定のタイミング周期で、前記複数の入力ポート部（１−７）の各々からトラフィック負荷情報を収集し、平均フリット到達時間を計算し、誤り入力フリッツを扱う適切な入力ポートを決定する、
ことを特徴とする３次元ＩＣ。
【請求項８】
請求項５において、
さらに、前記クロスバー（１３）に対する複数のバイパス路（１３１、１３２）と、
前記クロスバー（１３）のリンク状態をチエックするクロスバー制御部（１７）を有し、
前記クロスバー制御部（１７）により、１又は複数のリンクの誤りが検出される時、前記誤り制御モジュール（２０）にフラグを送り、
前記誤り制御モジュール（２０）は、前記誤りのクロスバーリンクリンクを不能にして、前記複数のバイパス路（１３１、１３２）の適切な数を可能とする、
ことを特徴とする３次元ＩＣ。
【請求項９】
請求項７において、
推定される誤り率を分析し、前記バイパスリンクの数が、実行処理が落ち着く、或いは変化のない状態になるまで増加される、
ことを特徴とする誤り耐性ルータ。
【請求項１０】
請求項６−９のいずれか１項において、
前記ＩＣが、それぞれに複数のコアが形成された複数のウェハで構成される３Ｄ−ＩＣであることを特徴とする誤り耐性ルータ。
【請求項１１】
ＩＣの複数のコアのそれぞれに対応して備えられた誤り耐性ルータの制御方法であって、
第１の処理ステージとして、
ランダムアクセスバッファ（９）により、それぞれの入力ポート（１−７）の入力バッファ（１１）のデッドロックと誤り状態を検知し、
前記入力ポート（１−７）のそれぞれの入力バッファ（１１）に付属するプローブからトラフィック情報を受信し、
入力フリッツから次のポートに対する識別情報を取得し、
スイッチ要求信号をスイッチ配置器（１６）に送り、
第２の処理ステージとして、
誤り制御モジュール（２）からの受信信号に基づくルーティングモジュールによって実行される次のノードに対する次のポートを計算し、
前記スイッチ配置器（１６）により管理される異なるポートからのリクエスト間をスケジューリングし、
前記スイッチ配置器（１６）から要求された出力ポートの使用を許可する要求信号と制御信号を、スケジューリング結果についての情報を有するクロスバー（１３）に送り、
第３の処理ステージとして、
入力バッファ（１１）からのフリッツをチェックし、適切な隣接ノードに送る
ことを特徴とする誤り耐性ルータの制御方法。
【請求項１２】
請求項１１において、
前記ＩＣは、複数のコアのそれぞれが備えられ、積層されたウェハで形成された３Ｄ−ＩＣである、
ことを特徴とする誤り耐性ルータの制御方法。
【外国語明細書】
2015119387000001.pdf