JP2017208736A

JP2017208736A - ネットワークオンチップ用の欠陥耐性ルータ

Info

Publication number: JP2017208736A
Application number: JP2016100732A
Authority: JP
Inventors: アブダラアブデラゼクベン; Ben Abdallah Abderazek
Original assignee: University of Aizu
Current assignee: University of Aizu
Priority date: 2016-05-19
Filing date: 2016-05-19
Publication date: 2017-11-24
Anticipated expiration: 2036-05-19
Also published as: JP6846027B2

Abstract

【課題】ＩＣに有する複数のコアのそれぞれに対応して配置される欠陥耐性ルータであって、パフォーマンスを劣化することなく、単一のクロスバーにおいて多重の欠陥に耐性する。【解決手段】欠陥耐性ルータは、フリットがそれぞれ対応するコアから入力される入力ポート部11-17と、フリットをそれぞれの到達先方向に接続するクロスバー4と、クロスバーのチャネルパスと異なる追加のチャネルパスと、欠陥マネジャーユニット8を有する。入力ポートユニットのそれぞれが、入力バッファ3と、エラー訂正回路７と、入力バッファに入力したフリットにおける欠陥スロットの記録を制御するランダムアクセスバッファ(RAB)を有する。欠陥マネジャーユニットは、エラー訂正回路により、フリットの欠陥が訂正されないとき、送信元ノードにフリットの再送を要求し、再送信によりエラーが訂正されないとき、ハードウエアを診断する。【選択図】図３

Description

本発明は、ネットワークオンチップ用の欠陥耐性ルータに関する。欠陥耐性ルータは、３Ｄネットワークオンチップ（３Ｄ−ＮｏＣ）に備えられる。少しの変更で、２Ｄ−ＮｏＣに備えることも可能である。

システムオンチップ(ＳｏＣｓ)デザインは、かなりシンプルな単一コア、単一メモリデザインから、単一の集積回路（ＩＣ）上のハードウエアアクセレータ、パワー管理回路、メモリ、Ｉ／Ｏ、プロセッサコア、及びＤＳＰといった沢山のＩＰ（intellectual property）ブロックを有する複雑なマルチコアＳｏＣｓに進化している。

一方で、チップマルチプロセッサ（ＣＭＰｓ）は、沢山な同種のプロセッサコア、メモリ、及びＩ／Ｏサブシステムと関係する。両システムにおいて、オンチップ通信ネットワークは、種々のコンポーネント間の高いパフォーマンス通信に主要な役割を果たす。

ＳｏＣデザインの主要な問題は、非拡張性（non-scalable）の配線遅延と、オンチップ通信の相互接続の電力消費である。特に、伝統的バスベースのシステムではコアの数の増加に伴い、まずい大きさがシステムに加わる、非効率の長いグローバルな接続を有する。

ＳｏＣデザインの抑制（市場デザインとモジュール化に対する厳しい時間）のため、又共用バスとクロスバー相互接続の大きさの問題のために、ネットワークオンチップ（ＮｏＣ）が解決策として提案されている。ＮｏＣは、互いにポイント対ポイントのリンクで相互接続される多くのルーチングノード（タイルとして知られる）を有するグローバルな共用通信相互接続である。メッセージは、ソースノードにより注入され、このソースノードから目的ノードまで多重の相互接続と物理リンクを通して送られる。

ノード間の通信単位は、パケット又がフリット(flits)であり、パケットが分割され、リンクの幅に等しいフリット、又はユニットに分割される。ＮｏＣ用のメッシュトポロジーは、うまくシリコン実行とよくマッチする、なぜなら従来の半導体プロセスを精密に立てるトポロジーの本質的な２次元構造であるからである。

従来の共有バスベースシステム上にＮｏＣシステムにより提供される高度の拡張可能性と並立性にかかわらず、将来の大きな複雑なＳｏＣシステムの対する理想の解決策にならない。これは、高消費電力及び低スループットといういくつかの制限があるからである。

ＮｏＣの３次元への統合（３Ｄ−ＮｏＣ）は、ルーティングとフロア計画における追加の柔軟性を与える。結果として、３Ｄ−ＮｏＣデザインは、小さなチップエリアと短い相互接続ワイヤを容易にする。それにより、従来の２Ｄ−ＮｏＣと比較してワイヤ遅延を減少し、電力消費を低減する。さらに、平面２Ｄ−ＮｏＣと比較して、３Ｄ集積技術は、大きなパッケージ密度と小さなチップ底面積(footprint)を与える。

しかし、特徴サイズ及び供給電圧が継続的に低下するので、２Ｄ又は３Ｄオンチップ相互接続を有して形成されるシステムは、ハードエラー（ハードウエア要素におけるエラー）とソフトエラー（送信されるデータ/ペイロードあるいは、ルータにおけるルーティング計算におけるエラー）に対し、より脆弱になる。

典型的には１クロックサイクルの短い時間周期（瞬間的とも呼ばれる）での回路の動作に影響を与えるソフト欠陥にはいくつかの原因がある。共通原因は、宇宙の放射、製造変動、及びアルファ粒子である。欠陥は、チップ全体のパフォーマンスにおいてデッドロック、データ衝突、パケットロス、パケット遅延の増大というような厳しい結果をもたらす。したがって、効果的な保護メカニズムが無いと、そうしたエラーがシステムの正しい機能及び信頼性を妥協することになる。

これまで提案された欠陥耐性３Ｄ−ＮｏＣの解決のいくつかは、スルーシリコンバイアス(Through Silicon Vias [TSVs])（非特許文献５）[Loi:2008]，（非特許文献１３）[Radetzik:2013]に生じる永久欠陥に焦点を当て、その生成を改善する。例えば、それらのいくつかは、予備ビア挿入(spare via insertion TSVs)、あるいは連続(serialization)（非特許文献６）[Patricha:2009]に基づいている。

他のものは、欠陥耐性ルーティングアルゴリズムの適用によってリンク欠陥のみに焦点を当てている。既に存在する解決策（非特許文献７，８，９[Feng:2011, Li:2005, Feng:2010, Xiang:2009]）の多くは、周囲の欠陥を囲むリンクの情報を記憶するルーティングテーブルに基づき，デッドロックの発生を避ける。それらは、仮想チャネル（VCs）（非特許文献１１）[Dally:1992]を用いている。その他は、VCsの使用を避け、その代わりに，ターンモデル（turn model）ルーティングを用いて、デッドロックを回避する(非特許文献１２)[ Pasricha:2011]。

ＮｏＣのルータにおいてソフトエラーを扱うために、複数の層を目標としたいくつかの研究がある。データ衝突の場合、最も効果的な解決は、誤り訂正コード/ 誤り検出コード(ECC/EDC)である。例えば、SEC(Single Error Correction), SECDED (Single Error Correction, Double Error Detection), ED (Error Detection), PAR (Parity Code), CRC-4 (Cyclic Redundancy Check) and CRC-8等（非特許文献１４）[Bertozzi:2005]である。

適用コードのため、Yu 他(非特許文献１５) [Yu:2010] は、接続の品質の基づき再構成される二つのハミングコードの動的ECCを提示している。論理変造(logic corruption)にのため、研究の多くは、クロスネットワーク層において実行される。端から端の流れ制御を有して、Shamshiri他（非特許文献１６）[Shamshiri:2011]は、誤り訂正、及び２Ｇ４Ｌと呼ばれる特殊コードを用いるオンライン診断を提示している。

ＮｏＣ警告(非特許文献１７) [Prodromou:2012]は、モジュールの束縛を実行して、ルータのサブモジュールから端と端の接続に対して計算の正確さを得る。

ここで本特許明細書、その他の記述では、“要素”(components)，”IP”，又は“コア”(core) の用語は、互換性をもってＮｏＣにおける種々のシステム要素を指すために使用される。また、”フリット(flit)” 若しくは”パケット(packet)”の用語も互換性をもって使用される。

特開2009-110512号公報特開2010-137572号公報特開2011-035906号公報特開2014-186509号公報特開2015-119387号公報米国特許No. 8,340,517B2 米国特許出願No. 2012/0155482 A1

[BenabPTN:2013] Abderazek Ben Abdallah, Pending Patent, ‘’3D Fault Tolerant Router Architecture’’, Ref. 51302665051-2013, Japan. [BenAhmed:2014] A. Ben Ahmed, A. Ben Abdallah. ‘’Graceful Deadlock-Free Fault-Tolerant Routing Algorithm for 3D Network-on-Chip Architectures’’. Journal of Parallel and Distributed Computing 74/4 (2014), pp. 2229-2240 [BenAhmed:2013] 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 Jnl. of Supercomputing, December 2013, Volume 66, Issue 3, pp 1507-1532. [BenabBook:2013] A. Ben Abdallah, Multicore Systems-on-Chip: Practical Hardware/Software Design, 2nd Edition, Publisher: Springer, (2013), ISBN-13: 978-9491216916. [Loi:2008] 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, pp. 598-602， 2008. [Patricha:2009] Pasricha, S., "Exploring serial vertical interconnects for 3D ICs," in Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE , vol., no., pp.581-586, 26-31 July 2009. doi: 10.1145/1629911.1630061 [Feng:2011] Chaochao Feng; Minxuan Zhang; Jinwen Li; Jiang Jiang; Zhonghai Lu; Jantsch, A., "A Low-Overhead Fault-Aware Deflection Routing Algorithm for 3D Network-on-Chip," in VLSI (ISVLSI), 2011 IEEE Computer Society Annual Symposium on , vol., no., pp.19-24, 4-6 July 2011. doi: 10.1109/ISVLSI.2011.42 [Li:2005] Yamin Li; Peng, S.; Wanming Chu, "Adaptive box-based efficient fault-tolerant routing in 3D torus," In Proceedings of the 11th International Conference on Parallel and Distributed Systems, vol.1, no., pp.71-77 Vol. 1, 20-22 July 2005. doi: 10.1109/ICPADS.2005.64. [Feng:2010] Chaochao Feng, Zhonghai Lu, Axel Jantsch, Jinwen Li, and Minxuan Zhang. 2010. ‘’A reconfigurable fault-tolerant deflection routing algorithm based on reinforcement learning for network-on-chip’’. In Proceedings of the Third International Workshop on Network on Chip Architectures(NoCArc '10). ACM, New York, NY, USA, pages 11-16. [Xiang:2009] 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. [Dally:1992] W. J. Dally. ‘’Virtual-channel flow control’’. IEEE Trans. on Parallel and Distributed Systems, 3(2): 194-205， March 1992. [Pasricha:2011] 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. [Radetzik:2013] M. Radetzki, C. Feng, X. Zhao, and A. Jantsch, "Methods for fault tolerance in networks-on-chip," ACM Computing Surveys (CSUR), vol. 46, no. 1, p. 8, 2013. [Bertozzi:2005]D. Bertozzi, L. Benini, and G. De Micheli, "Error control schemes for on-chip communication links: the energy-reliability tradeoff," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 24, pp. 818-831, June 2005 [Yu:2010] Q. Yu and P. Ampadu, "Transient and permanent error co-management method for reliable networks-on-chip," in Networks-on-Chip (NOCS), 2010 Fourth ACM/IEEE International Symposium on, pp. 145-154, IEEE, 2010. [Shamshiri:2011] S. Shamshiri, A.-A. Ghofrani, and K.-T. Cheng, "End-to-end error correction and online diagnosis for on-chip networks," in Test Conference (ITC), 2011 IEEE International, pp. 1-10, IEEE, 2011 [Prodromou:2012] A. Prodromou, A. Panteli, C. Nicopoulos, and Y. Sazeides, "Nocalert: An on-line and real-time fault detection mechanism for network-onchip architectures," in Microarchitecture (MICRO), 2012 45th Annual IEEE/ACM International Symposium on, pp. 60-71, Dec 2012

上記に述べた研究は、データにおけるソフトエラーとルーティングロジックを扱うための部分的（完全ではない）解決であるが、パイプラインステージ（即ち、ルート計算ステップ、スイッチ配置、その他）における欠陥が検討されていない。所与のパイプラインステージにおける計算誤りが計算の正確さに影響を与えるので、その様な欠陥の検知と回復のための低レーテンシーと低コスト（小さな危険度と低価格）の技術が必須である。

上記したように、３Ｄ−ＮｏＣシステムにおける欠陥耐性問題に言及した既存の解決策に関わらず、以下に述べるように依然として未だいくつかの課題がある。

第１に、所与のネットワークオンチップにおける欠陥は、瞬間的、永久的そして、断続的欠陥により引き起こされる。これら欠陥の全てに対する完全な（ソフトとハード）欠陥耐性を提供する研究はない。

第２に、瞬時的欠陥の最も普通の解決は、データ／ペイロードにおける欠陥のみの扱いに焦点を当てていた。しかし、ミスルーティングに繋がるルーティング計算における欠陥、パケットロスあるいはシステムクラッシュというようなパイプラインにおける欠陥は検討されていなかった。

第３に、全ての従来のアーキテクチャは、既存の検出方法と考えられる。しかし、検出方法は、大きな計算資源と高いレーテンシーの原因となる。検出が遅すぎると、システムの機能は、欠陥を回復出来ない。検出があまりしばしばであると、システムのパフォーマンスに大きなインパクトを与える。

第４に、デッドロックの発生は、仮想チャネル（ＶＣｓ）に基づき避けられる。ＶＣｓは、システムのデッドロックを補償するが、ハードウエアの複雑さという見地からすると、高価な調整者(arbiter)である。

図１は、大半のＮｏＣシステムにおいて使用される従来のルータのタイムチャート（パイプラインステージ）を示す。上記図に示されるように、５つのパイプラインステージがある。

第１のパイプラインステージは、現在提案のルータにおけるものと基本的に同じ機能を有するバッファ書き込みステージである。ＶＣｓは、デッドロックが起きない要件を満たすために用いられる。Ｖｓの数は、システム構成と、一般的に２から４個のＶＣｓで変えることが出来るルーティングアルゴリズムに依存する。

次のステージIIは、ルーティング演算であり、多くのシステムが、静的なXYZルーティングあるいは後の説明に基づく他のルーティングを用いる。先読みルーティングな無いため、次の二つのステージは、XYZモジュールから結果を受信しない限り動作することが出来ない。

第三のステージIIIは、仮想チャネル配置ステージである。ＶＣｓの採用は、追加のクロックサイクルを加える調停が必要である。したがって、全体のパイプラインステージは、異なるＶＣｓ間の調停に貢献する。

ＶＣが、許可を与えた後、スイッチ配置ステージＩＶに交代する。

最後に、最終ステージＶ、クロスバー通過(Crossbar-Traversal)において、スイッチアロケータから受信される調停結果に従って、隣接ノードへのフリッツの転送を扱う。

上記に照らし、本発明の目的の一つは、デッドロックの回避のために用いるＲＡＢメカニズム(後に説明)により上記ステージIIIをなくすことにある。上記スイッチ配置ステージIVは、本発明におけると同様である。しかし、異なる点は、ルーティングIIと独立し、本発明の様に並列に処理は出来ない。

さらに、本発明の目的は、ルータ／ＮｏＣにおけるソフトエラーを解決する欠陥耐性ルータを提案することにある。加えて、本発明は、従来のルータの他の欠点、例えば、ハード（ハードウエア部品）及びソフト（データ又はパイプライン計算ステージにおける）といった従来のルータの欠点を解決することにある。

ＩＣ上に備えられる複数のコアのそれぞれに対応する欠陥耐性ルータであって、上記問題を解決する本発明に従うＮｏＣ用の欠陥耐性ルータは、第１の側面として、フリットがそれぞれ対応するコアから入力される複数の入力ポート部（11-17）と、前記入力ポートユニット(11-17)から出力されるフリットをそれぞれの到達先方向に接続するクロスバー(4)と、前記クロスバー(4)のチャネルパスと異なる追加のチャネルパス(40)と、欠陥マネジャーユニット(8)を有し、前記複数の入力ポートユニット（11-17)のそれぞれが、入力バッファ(3)と、前記入力バッファ(3)に入力したフリットのエラーを訂正するエラー訂正回路（７）と、前記入力バッファ（３）に入力したフリットにおける欠陥スロットの記録を制御するランダムアクセスバッファ(RAB)を有し、更に前記欠陥マネジャーユニット(8)は、前記エラー訂正回路(7)により、前記フリットの欠陥が訂正されないとき、送信元ノードに前記フリットの再送を要求し、前記フリットにおけるエラーが前記再送信により訂正されないとき、ハードウエアを診断することを特徴とする。

前記問題を解決する本発明に従うＮｏＣ用の欠陥耐性ルータは、第１の側面における第一の態様として、前記欠陥マネジャーユニットは入力バッファ(3)、クロスバー(4)、及び隣接ルータ(R2)との接続リンク(RL)の順に欠陥を診断することを特徴とする。

前記問題を解決する本発明に従うＮｏＣ用の欠陥耐性ルータは、第１の側面における第二の態様として、前記入力バッファ(3)が、前記診断において、欠陥と判定される時、欠陥マネジャーユニット(8)が、前記ランダムアクセスバッファに入力バッファ(3)におけるスロットの欠陥状態をチェックさせ、前記スロットにおける欠陥をレジスタに記録させることを特徴とする。

前記問題を解決する本発明に従うＮｏＣ用の欠陥耐性ルータは、第１の側面における第三の態様として、前記マネジャーユニットは、入力バッファが正常なときは、追加のチャネルパスを選択して代替のパスを選択することを特徴とする。

先の研究と反対に、提案のシステムは、考慮する実行の低下を伴わずに、単一のクロスバーにおける複数の欠陥を許容する。加えて、使用されるＬＡＦＴルーティングアルゴリズムは、一つの最小パスがある限り、常に最小である。ＲＡＭメカニズムの助けを伴って、欠陥耐性及びデッドロック回避とともに、大きなエリア及びパワー費用を伴わずに保証される。

図１は、多くのＮｏＣシステムにおける従来のルータのタイムチャート(パイプラインステージ)である。図２は、本発明に従う提案のルータのタイムチャートである。図３は、本発明に従う提案のルータ構成のブロック図である。図４は、提案のルータ構成に採用されたランダムアクセスバッファ（ＲＡＢ）のブロック図である。図５は、提案のルータ構成に採用された要求メカニズム（ＢＬｏＤ）上のバイパスリンクの概要図である。図６は、本発明に従うハードエラー検出と回復アルゴリズムであるアルゴリズム１における欠陥検出位相のフローチャートである。図７は、アルゴリズム１における診断及び回復位相のフローチャートである。図８は、上流と下流のルータ間の相互接続の概要図を示す。図９は、本発明に従うアルゴリズム２としてソフトエラー回復処理方法のフローチャートである。図１０は、アルゴリズム３として先読み耐性ルーティングアルゴリズム（LAFT）のフローチャートである。

本発明の実施例を添付の図面に沿って説明する。実施例は、発明のよりよい理解のためのものであり、従って、発明の適用は、この実施例に限定されない。

いくつかのウエハを重ねて形成される３Ｄ-ＩＣに主として説明がなされるが、本発明は、単一のウエハに設けられる複数のコア及びこの複数のコアを接続するネットワークを有して構成される２Ｄ−ＩＣにも適用可能である。

[本発明のルータタイムチャート]
本発明の欠陥耐性ルータにおいて、前記した課題は３つのステップにより解決される。
（１）欠陥検出（一またはそれ以上の欠陥の検出）、（２）欠陥診断（欠陥の型の決定）、（３）欠陥の型に基づく回復（ソフトまたはハード）
図２は、提案の欠陥耐性ルータに対するタイムチャートを示す。図２において、ハードエラーの扱いのため、先読み欠陥耐性ルーティング（ＬＡＦＴ）アルゴリズムが欠陥リンクを扱う。二つの主たる要素がさらに欠陥耐性を支持する：（１）クロスバー２における欠陥に対するバイパスリンク要求（ＢＬｏＤ）と（２）入力ポートバッファ４における欠陥に対するランダムアクセスバッファ（ＲＡＢ）メカニズム。

図２に示すパイプラインステージにおけるソフトエラーを扱うために、ソフトウエア冗長に基づくソフトエラー回復(Soft Error Resilience: SER)メカニズムが使用される。ＥＣＣ（Error Correction Code）モジュールがデータ修正のために使用される。受信データが修正されない場合、データは、自動再送要求（Automatic-Retransmission Request: ARQ）を使用して再送され、再度エラーチェックされる。これは、データが修正されるまで繰り返される。欠陥マネジャーは、欠陥の診断および回復位相を管理する。

さらに、具体的に図２において説明すると、第１ステージIにおいて、入力バッファ３への入力データの書き込み及びＥＣＣブロック７におけるＥＣＣ復号化が入力ポートマネジャー２にあるＲＡＢメカニズム及びソフトエラー回復（ＳＥＲ）マネジャー６の制御のもとに実行される。

第２ステージIIにおいて、ＳＥＲマネジャー６において次のポートが計算される。そして、スイッチ配置がスイッチ配置部９において実行される。第３のステージIIIにおいて、クロスバー４におけるクロスバー通過及びＡＲＱバッファ１０におけるＡＲＱ方法が実行される。この方法は、データが訂正されるまで繰り返される。

[ルータ構成]
図３は、本発明に従う提案の欠陥耐性ルータのブロック図である。図３において、ＮｏＣルータは、複数の入力ポートユニット１１−１７、即ち、ローカル入力ポートユニット１１、ノース入力ポートユニット１２、イースト入力ノースポート１３、サウス入力ポートユニット１４、ウエスト入力ポートユニット１５、アップ入力ポートユニット１６、ダウン入力ポートユニット１７を有し、それぞれの入力ポートユニットは、積層ウェハの対応する方向からの入力１０を受信する。

入力ポートユニット１１−１７のそれぞれは、先読み欠陥耐性（ＬＡＦＴ）ルーティングアルゴリズムが実行されるＬＡＦＴルーティングユニット１を有し、欠陥リンクを処理する。ＬＡＦＴルーティングアルゴリズムに加え、三つの要素が用いられ、更に、本発明に従う欠陥耐性が保証される。すなわち、ランダム−アクセス−バッファ（ＲＡＢ）メカニズムが、入力ポートユニット１１-１７のそれぞれに備えられる入力バッファ３における欠陥に対して、入力ポートマネジャーユニット２が実行され、クロスバー４における欠陥に対してバイパスリンクオンデマンド（ＢＬｏＤ）がＢＬｏＤユニット５に備えられ、そして、ＳＥＲマネジャーユニット６においてソフトエラー柔軟ハンドリング方法が実行されて、ネットワークオンチップにおけるルータのパイプラインステージにおけるソフトエラーを解決する。

すなわち、二つの主たる要素が欠陥耐性を保証するために用いられる：（１）クロスバー４における欠陥に対するバイパス−リンク−オン−デマンド（ＢＬｏＤ）アルゴリズムと（２）入力ポートマネジャーユニット２における欠陥に対するランダム−アクセス−バッファー（ＲＡＢ）メカニズム。さらに、パイプラインステージにおけるソフトエラーを扱うために、ソフトウエア冗長性に基づくソフトエラー柔軟（ＳＥＲ）メカニズムがＳＥＲマネジャーユニット６において実行される。

フリットは、ローカル、ノース、イースト、サウス、ウエスト、アップ、ダウン入力ポートウニット１１−１７のそれぞれに備えられる入力バッファ３に入力される。そして、パイプラインステージのクロスバー通過ステージIIIの間、適切な隣接ノードに送られる。ＢＬｏＤユニット５がクロスバー４を再構成するために使用される。

欠陥マネジャーユニット８は、ルータの異なる要素間の通信を制御し確立するために使用される。欠陥があると、欠陥マネジャーユニット８は検出、診断、及び回復位相を扱う。

入力ポートマネジャーユニット２に位置するＲＡＢコントローラは、通常的に入力バッファ３における欠陥の状態をモニタする。ＲＡＢコントローラが、入力バッファ３における欠陥入力の存在を検知すると、ＲＡＢコントローラは、欠陥入力を隔離する。したがって、システムは、入力バッファ３における欠陥スロットの影響を緩和する。

欠陥マネジャーユニット８は、システムの主要要素の一つである。三つの主要要素の：ルータ相互間リンク、入力バッファ３、クロスバー４、及び隣接ルータを接続するルータ相互リンクにおけるあらゆる種類の欠陥の検出、診断、及び回復を管理する。

以下に、本発明に従うルータの主要要素の機能および構成について詳細に説明する。

[ランダムアクセスバッファ・コントローラ（RAB-cntrl)]
図４は、提案するランダムアクセスバッファ（ＲＡＢ）メカニズムのブロックダイヤグラムである。ＲＡＢメカニズムは、デッドロックさせないための効率的、低オーバヘッドの解法であり、ＲＡＢメカニズムは、又、入力バッファ３における瞬時的な，間欠的、及び永久的欠陥を検知し回復する。

ＲＡＢメカニズムでの欠陥検出及び回復は、二つの主要な並列位相に分配される。最初の位相は、局所的に実行され、欠陥の検出及び回復が、入力バッファ３において行われることを意味する。第２の位相は、全体的(即ち、ルータ全体)に行われる。

欠陥の検出に対しては、図４に示す欠陥検出回路３０が用いられ、入力バッファ３におけるバッファスロットの欠陥状態をチェックする。欠陥検出回路３０によりスロットの一つにおいて欠陥が検出される時、欠陥検出回路３０は、バッファコントローラ３２のＲＡＢマネジャーユニット３１に“欠陥スロット”信号を送る。バッファコントローラ（RAB-cntrl)３２は、破線で囲まれ、ＲＡＢコントローラ３２におけるＦＩＦＯ３３からの書き込みアドレス“Wr_adr” と読み出しアドレス“Rd_adr”を指定したとき、フラグされたスロットを考慮する。

欠陥スロットの記録を維持するため、ｎ２ビット項目（ｎは、バッファ深さ）を有するアレーを有するステータスレジスタ３４が用いられる。ステータスレジスタ３４に保持されるそれぞれの項目の値は、“００”として、対応するフリットがデッドロックを生じていず、バッファスロットが欠陥でないことを通知する。“０１”は、バッファスロットが欠陥でないけれど、ホストのフリットの要求がデッドロックを生じていることを示す。最後に、もし欠陥が対応するバッファスロットにおいて検出されると、ステータスレジスタ３４における要素(エレメント)は、“１１”に更新される。そして、スロットは、壊れたスロットを求めるための追加の遅延を避けるべく考慮されることも、入力するフリットを格納するために使用されることもない。

[バイパスリンクオンデマンド(BLoD)メカニズム]
バイパスリンクオンデマンド(BLoD)メカニズムが、図５で説明される。BLoDメカニズムは、７ｘ７基準のクロスバー４における欠陥の数が増加するたびに、追加の回避チャネルを与える。この場合、二つのバイパスリンク（(Bypass-1 と Bypass-2)が構成例として考えられる。この図に示すクロスバーサブコントローラ（cntrl unit)４１は、クロスバーリンクステータスのチェックを管理する。そして、欠陥が一つまたはいくつかのリンクで検出される場合、フラグ(faulty_Cross)を欠陥制御モジュール(ＦＣＭ)４２に送り、欠陥クロスバーリンクを不能にし、バイパスリンク４０において、適切な数のバイパスチャネルを可能にする。

最も容易なアプローチは、全てのクロスバーチャネルに対して特定のバイパスチャネルを備えることである。この方法では、入力ポート１０の要求がバイパスリンク４０を必要としないので、７ｘ７基準のクロスバーリンク４３全体が欠陥である場合であっても、欠陥耐性もパフォーマンスも保証される。しかし、この技術は、クロスバー４３全体を二重にするのと同じである。したがって、追加のエリアと電力オーバヘッドが必ず生じる。加えて、欠陥率が低いときは、３つ又は２つのバイパスリンク４０のみで欠陥クロスバーリンクの要求を処理するに十分である。

バイパスリンク４０の数は、の非常に重要である。エリアと電力オーバヘッドをできるだけ小さくするように最小化すべきである。したがって、発明者は、システムに既に存在する不使用のクロスバーリンクを利用するように決めた。これらのリンクは、基本的に、ネットワークの端部に位置し、隣接ノードがなく、従って対応するクロスバーリンクは不使用である、ネットワークの端に位置するものである。かかる最適化を備えて、パフォーマンスを最良にしながら重要なエリアと電力の低減が達成できる。

[ハードエラー検出、診断、及び回復アルゴリズム：アルゴリズム１]
図６及び図７は、欠陥検出、診断及び回復方法のフローチャーを示す。図８は、メカニズムの容易な理解のために、上流と下流のルータR1, R2間の接続を示す。

検出位相：図６は、アルゴリズムの検出位相を示す。フリットが入力バッファ３に入った時、エラー訂正コード（ＥＣＣ）メカニズム７が使用されて入力したフリットのエラーを検出、訂正を行う（ステップＳ１）。ＥＣＣメカニズム７により、データがチェックされ、訂正されると（ステップＳ２，Ｙｅｓ）、フリットは、次のパイプラインステージＩＩに続く（ステップＳ３）。

もし、データがＥＣＣメカニズム７により修正されないと(ステップＳ２, No)、欠陥マネジャー８が自動再送要求メカニズムを起動し（ステップＳ４）、送信側ノードに対し、上記のフリットの再送信を要求する。次いで、ＥＣＣメカニズム７によりデータがエラー修正のために再度処理される（ステップＳ５、Ｙｅｓ）。データが訂正されると（ステップＳ５，Ｙｅｓ）、フリットは、次のパイプラインステージに続く（ステップＳ３）。もしデータが訂正されないと（ステップＳ５、Ｎｏ）、欠陥マネジャー８は、更なる診断のために診断位相を起動する（ステップＳ６）。自動再送要求メカニズムが、最大２回のデータ再送の要求を（上流ルータに）送ると想定する。しかし、要求の回数は、２回以上に増やすことが可能である。これは、適用タイプと、電力余裕に依存する。

診断と回復位相：図７は、アルゴリズムの診断と回復の位相を示す。診断は、ルータの３つの主要要素：（１）入力バッファ、（２）クロスバー４、及び（３）リンクで実行される。

ルータの欠陥マネジャーモジュール８は、診断位相を起動する[診断開始]。次いで、入力バッファが、エラーチェックを受ける（ステップＳ０１）。

もし、入力バッファ３に欠陥があると（ステップＳ０１、Ｙｅｓ）、欠陥マネジャー８は、ランダムアクセスバッファ（ＲＡＢ）メカニズムに要求し（ステップＳ０２）、入力バッファ３における欠陥スロットを処理する。先のセクションはＲＡＢメカニズムがどのように動作するかを説明している。

入力バッファ３に欠陥がないと（ステップＳ０１，Ｎｏ）、欠陥がクロスバー４、又は二つのルータＲ１，Ｒ２間のリンクに属することを意味する。この段階で、欠陥マネジャー８は、第一にバイパスリンクオンデマンド[Bypass-Link-on-demand]を構築して、代替の接続パスを確立する（ステップＳ０３）。ついで、他のフリットが入力バッファ３からバイパスリンクオンデマンド５及びルータ対ルータ[router-to-router]リンクを通して下流のノードに送られる。もし、下流のノードで、（ＥＣＣもジュールにより）フリットが欠陥でないとされると欠陥マネジャー８は欠陥はクロスバー４にあると結論する。

もし、フリットが未だ欠陥であると（ステップＳ０４，Ｎｏ）、欠陥はルータ間リンク（ＲＬ）に属する。この場合、バイパスリンクオンデマンド[Bypass-Link-on-demand]は、更なる欠陥耐性のために開放され（ステップＳ０５）、先読み欠陥耐性 [Look-Ahead Fault-Tolerant: LAFT] ルーティングアルゴリズムが実行され、リンク欠陥を処理する（ステップＳ０６）。入力バッファ３にあるフリットは、次いで、次の章で説明するＬＡＦＴルーティングアルゴリズムユニット１によりルータの代替出力ポートを介して迂回される。

[ソフトエラー回復（ＳＥＲ）処理方法：アルゴリズム２]
図９は、アルゴリズム２としてソフトエラー回復方法を示す。図２に示したように、ルータはパイプラインステージ：バッファ書き込みステージＩ，ルーティング計算／スイッチ配置ステージII、及びクロスバー通過ステージIIIを有する。

先に説明した様に、バッファ書き込みステージIは、二つの主要素：１) 入力バッファ３のデッドロックと欠陥状態の監視のためのランダム-アクセス-バッファ（RAB）コントローラ（RAB-contr）と２）読出し／書込み動作と、制御信号を次のポート計算及びスイッチ配置に送るために使用される単純なバッファを有する。ＥＣＣ（エラー訂正コード）モジュール７は、入力フリット（またはパケット）における欠陥の検知と訂正に使用される。入力バッファメモリ３は、ＥＣＣの後、フリットの書き込み及び読み出しに使用される。

ルーティング計算／スイッチ配置ステージIIは、同時に実行される、二つの主要な動作を扱う。第１の動作は、次ノードの次のポートを計算することである（NPC）。これは、ＬＡＦＴ[Look Ahead Fault-Tolerant]ルーティングモジュール１により実行され、リンクステータスレジスタ３２（図４）から受信される信号に依存する。第２の動作は、スイッチ要求ユニット４１（図５）による異なる入力ポートからの異なる要求間のスケジューリングである。これは、入力として異なるスイッチ要求（sw-request）信号を有するスイッチアロケータ（ＳＡ）９により管理される。出力に対して、ＳＡ９は、要求された出力ポートの使用許可を与える、スイッチ許可sw-grant、及びスケジューリング結果についての情報を有するクロスバー４に対するクロスバー制御信号xbar-cntrlを発行する。

[ソフトエラー回復処理方法:アルゴリズム２]
ルーティング計算（ＮＰＣ）及びスイッチアロケーション（ＳＡ）は、図９のサイクル２に示すように同時に並行して走る。ここでは、ルーティングアルゴリズムにより達成され、２つのステージ間の従属性は無くされる。このステージにおいて使用される欠陥耐性方法は、アルゴリズム２としてソフトエラー回復処理（ＳＥＲ）と呼ばれる。図２におけるこれらパイプラインステージI, II, IIIにおいてソフト（または瞬間的な）エラーを処理するのみである。

ソフトエラー処理方法の原理は、一以上のクロックサイクルでパイプラインステージ計算の二重化（ソフト冗長）であり、検出は、計算結果の差に基づき行われる。もし、二つのクロックサイクルが類似の結果であれば、ソフトエラーは無い。二つの連続する欠陥が異なる場合、ソフトエラーが存在する。この場合、システムは、欠陥を訂正するために第３のクロックサイクルを要求する。欠陥は、三つの結果の多数決で訂正される。

図９のアルゴリズム２に示されるように、二重化は、ローカルルーティング計算、次ポート計算（ＮＰＣ）、及びスイッチアロケーション（ＳＡ）モジュールに対して行われる。（サイクル２における）第１の計算の後、三つのステージI. II. IIIの全てが追加的計算クロックを有する。ソフトエラーが検出されると、パイプライン全体が訂正のために停止する。図９において、細い線で囲われたブロックは、当初のパイプラインステージを示し、太線で囲われたブロックは冗長のパイプラインステージである。

さらに詳細に、それぞれのサイクルの動作を以下に説明する。

サイクル１において、バッファ書き込み（ＢＷ）ステージＩで入力バッファ３にフリットが書き込まれ、ＥＣＣ（エラー訂正コード）が使用され、ＥＣＣモジュール７で入力データがチェックされ、訂正される。

サイクル２において、ＮＰＣ（次ノードポート計算）とＳＡ（スイッチアロケーション）が並行してＬＡＦＴルーティングユニット１で計算される。

サイクル３において、冗長ＮＰＣ（ＲＮＰＣ）及び冗長ＳＡ（ＲＳＡ）が並行に計算される。次いで、冗長計算（ＲＮＰＣ）の出力がＮＰＣに等しく、且つＳＡがＲＳＡに等しい場合、計算クロスバー通過（ＣＴ）ステージIIIがサイクル３において実行され、フリットがサイクル４において、出力チャネルを介して次ルータに行く。もしＲＮＰＣがＮＰＣに等しくなければ、システムは後退し、ＮＰＣを再計算する。さらに、ＳＡがＲＳＡに等しくなければ、システムは後退し、サイクル４でＳＡステージを再計算する。

先読みルーティングの利益を維持するために、ＬＡＦＴルーティングユニット１における提案の先読み欠陥耐性（ＬＡＦＴ）がリンク状態を考慮して次ノードに対するルーティング決定を行い、そして図１０のアルゴリズム３に示されるように、最良の最短パスを選択する。

図１０において、欠陥制御モジュール（ＦＣＭ）８から受信した欠陥情報が、ＬＡＦＴがＬＡＦＴルーティングユニット１により実行されるそれぞれの入力ポートユニットにより読まれる。

このアルゴリズムの第１の位相は、次ノードのアドレスを計算する（ステップＰ１）。目的の到達策先にフリットの送信を望むノードに対して、それぞれＸ，Ｙ，Ｚの範囲を通して最大３つの可能な方向が存在する。

第２の位相において、ＬＡＦＴルーティングユニット１は、現在のノードと到達先ノードの両方を同時にＸ，Ｙ，Ｘ座標を比較してこれら三つの方向の計算を行う（ステップＰ２）。同時に、これらの方向が計算される際に、欠陥マネジャー８の欠陥コントロールモジュールが、フリットから次ポートの識別子を読んで、適切な欠陥情報を対応する入力ポートに送る（ステップＰ３）。この第２の位相の終了までに、ＬＡＦＴは次ノードの欠陥状態と最小ルーティングに対する３つの可能な方向の情報を有する。

次の位相において、ルーティング選択が実行される（ステップＰ４，Ｐ５）。この決定のために、本発明者は、優先的条件の組を使用して欠陥のある場合、無い場合のいずれの場合において、欠陥耐性と高いパフォーマンスを確実にする。
１．選択された方向は、最小パスを確実にし、ルーティング選択において、最優先を与える（ステップＰ６，Ｙｅｓ）。
２．最大の次ノードの多様性を有する望ましいパスを有する方向を選択する。
３．輻輳状態が最小確率となる。

これらの優先度に依存して、ＬＡＦＴは、欠陥制御モジュールから受信する次ノードの欠陥状態を読み、可能な非欠陥の最小方向の数をチェックする（ステップＰ７）。三つの可能な方向が最小であり、同じ多様性を有するとき（ステップＰ８，Ｙｅｓ）、ルーティング選択は、それぞれの出力ポートの輻輳に依存して行われる（ステップＰ９）。三つの可能な方向が最小であるが、同じ多様性を有しないとき、最小の輻輳パスが選択される（ステップＰ１０）。

Claims

ＩＣに有する複数のコアのそれぞれに対応して配置される欠陥耐性ルータであって、
フリットがそれぞれ対応するコアから入力される複数の入力ポート部（11-17）と、
前記入力ポートユニット(11-17)から出力されるフリットをそれぞれの到達先方向に接続するクロスバー(4)と、
前記クロスバー(4)のチャネルパスと異なる追加のチャネルパス(40)と、
欠陥マネジャーユニット(8)を有し、
前記複数の入力ポートユニット（11-17)のそれぞれが、
入力バッファ(3)と、
前記入力バッファ(3)に入力したフリットのエラーを訂正するエラー訂正回路（７）と、
前記入力バッファ（３）に入力したフリットにおける欠陥スロットの記録を制御するランダムアクセスバッファ(RAB)を有し、更に
前記欠陥マネジャーユニット(8)は、前記エラー訂正回路(7)により、前記フリットの欠陥が訂正されないとき、送信元ノードに前記フリットの再送を要求し、前記フリットにおけるエラーが前記再送信により訂正されないとき、ハードウエアを診断する、
ことを特徴とする欠陥耐性ルータ。
請求項１において、
前記欠陥マネジャーユニットは入力バッファ(3)、クロスバー(4)、及び隣接ルータ(R2)との接続リンク(RL)の順に欠陥を診断する、
ことを特徴とする欠陥耐性ルータ。
請求項２において、
前記入力バッファ(3)が、前記診断において、欠陥と判定される時、欠陥マネジャーユニット(8)が、前記ランダムアクセスバッファに入力バッファ(3)におけるスロットの欠陥状態をチェックさせ、前記スロットにおける欠陥をレジスタに記録させる、
ことを特徴とする欠陥耐性ルータ。
請求項２において、
前記欠陥マネジャーユニットは、入力バッファが正常なときは、追加のチャネルパスを選択して代替のパスを選択する、
ことを特徴とする欠陥耐性ルータ。