NoC(オンチップネットワーク)の原理 ─ ルーティングとフロー制御

なぜバスではなくネットワークなのか

数コアの時代、コアやキャッシュは1本の共有バスやクロスバで繋がっていました。しかしコア数が数十・数百に増えると、この方式は二つの壁に当たります。第一に配線の物理です。全ノードを1点へ集める共有媒体は配線長が伸び、容量負荷が増え、クロックを上げられません。第二に競合です。共有バスは同時に1組の通信しか流せず、帯域がコア数で割り算され、調停（アービトレーション）も全体を巻き込みます。クロスバは全対全を同時に繋げますが、ポート数のN×Nに比例して面積が膨らみ、やはりスケールしません。

そこで発想を変え、チップ内に小さなパケット交換ネットワークを敷くのがNoC（Network on Chip）です。各コア（やキャッシュ、メモリコントローラ）にルーターを1つ付け、ルーター同士を短いリンクで隣接接続します。データはパケットに分割され、ルーターからルーターへ多段ホップで目的地へ運ばれます。配線は隣接間の短い線だけで済み、複数の通信が異なるリンク上で同時並行に流れます。これがインターネットの考え方をチップ内へ持ち込んだものです。

トポロジ ─ メッシュ・リング・トーラス

ルーターをどう繋ぐかがトポロジです。代表的な3つを比較します。重要な指標は直径（最遠ノード間の最大ホップ数。レイテンシの上限を決める）、二分割帯域（ネットワークを半分に割ったとき横切るリンク数。総スループットの上限を決める）、そして次数（1ルーターのポート数。面積コスト）です。

2DメッシュがメニーコアCPUで最も広く使われます。理由はレイアウトの素直さです。コアをタイルとして格子に並べ、各ルーターを上下左右の隣＋自コアの計5ポートで結べば、二次元平面にそのまま敷けます。直径が縦横の和に比例するため、コア数の平方根オーダーでしか伸びず、バスのように線形悪化しません。

トーラスはメッシュの端のノード同士を巻き戻して環状に繋ぎ、直径をほぼ半分に縮めます。ただし端から端への折り返し配線が長くなる弱点があり、実装ではこれをフォールデッドトーラスとして配線長を均一化します。リングは最も安価ですが直径が大きく、ノード数が増えるとレイテンシが線形に悪化するため、数コア〜十数コア規模に向きます。

2Dメッシュ（各ノードにルーターR、隣接5ポート）

   R--R--R--R
   |  |  |  |
   R--R--R--R      各Rは {North,South,East,West,Local} の
   |  |  |  |      最大5ポートを持つ。パケットは隣接Rへ
   R--R--R--R      1ホップずつ進み、平面上を縦横に移動する

ルーティング ─ 経路をどう決めるか

ルーティングは「宛先までどのリンクを辿るか」を決める層です。設計軸は決定性か適応性かです。

次元順ルーティング（DOR, Dimension-Order Routing）は最も基本的な決定的方式です。2Dメッシュでの代表がXYルーティングで、まずX方向（東西）へ目的列まで進み、列が合ってからY方向（南北）へ進む、と次元を固定順で消化します。経路が一意に決まり実装が極小で、後述するデッドロックも構造的に起きません。弱点は混雑への無力さで、進路上が詰まっていても迂回できません。

適応ルーティングは各ホップで複数の候補から空いている方向を選びます。混雑や故障を避けて回り込めるため、負荷が偏るトラフィックで有利です。代償として、許される旋回（ターン）を制約しないとデッドロックを招きます。経路選択の自由は、循環依存という危険と背中合わせなのです。

XYルーティング（決定的）        適応ルーティング（混雑回避）
 S......                         S--+
 .     :                         :  |（東が混雑→南へ迂回）
 .     :  まずX、次にY           :  +--+
 +----D  の順で一意に進む        :     D  空き方向を動的選択

デッドロック回避 ─ ターンモデルという発明

デッドロックは、複数のパケットが互いに相手の保持するバッファを待ち合う循環ができたときに発生します。AがBの占めるリンクを、BがCを、CがAを待つと、全員が永久に進めません。NoCはバッファが小さく、一度詰まると上流へ波及するため、これは致命的です。

回避の核心はチャネル依存グラフから循環を消すことです。各旋回（例：東から北へ曲がる）が生む依存関係をグラフ化し、サイクルが残らないよう一部の旋回を禁止します。これがターンモデルです。2Dメッシュには時計回り・反時計回りで計8通りの旋回があり、XYルーティングは「Y方向へ曲がった後にX方向へ曲がる」旋回をすべて禁じることで循環を断ち切っています（だからXYは無条件にデッドロックフリー）。

ターン制約のほかに、仮想チャネルを使った回避もあります。物理リンクを論理的に複数のチャネルへ分け、依存グラフ上で「番号の小さいVCから大きいVCへしか移れない」といった順序を課すと、循環が物理的に作れなくなります。トーラスの折り返しリンクが生む循環は、まさにこのVC順序付けで解かれます。

フロー制御と仮想チャネル ─ スループットの核心

ルーティングが「どこへ」なら、フロー制御は「いつ進めるか」を司る層です。下流のバッファが空いていなければ、フリットを送ってはいけません。あふれればフリットが失われるか、上流が無秩序に詰まるからです。

主流はクレジットベースフロー制御です。下流ルーターは自分の空きバッファ数（クレジット）を上流へ常に通知し、上流はクレジットがある分だけフリットを送ります。1フリット送るごとに手元のクレジットを1減らし、下流がバッファを解放するとクレジットが1返ってきます。これによりバッファオーバーフローが原理的に起きません。

転送の粒度にも方式があります。ストアアンドフォワードはパケット全体を受け切ってから次へ送るためレイテンシが大きく、**ワームホール（wormhole）**はヘッダフリットが届いた時点で先へ進み始め、後続フリットが列車のように後を追います。ワームホールは小バッファで低レイテンシですが、1パケットが複数リンクにまたがって居座ると詰まりやすく、ここでもVCが効きます。

クレジットベース＋ワームホール（VCで多重化）

 上流R ──[VC0]──▶ 下流R   下流は空きバッファ数=クレジットを返す
       ──[VC1]──▶         VC0が詰まってもVC1のフリットは前進
                          → HoLを避け、物理リンクを遊ばせない

レイテンシとスループットの原理

NoCの性能は二つの量で測ります。ゼロ負荷レイテンシは混雑がないときの片道時間で、おおよそ「ホップ数 × ルーター段あたりの遅延 ＋ パケット長 ÷ リンク幅」で決まります。ホップ数はトポロジの直径と経路長に、ルーター遅延はパイプライン段数（ルーティング計算・VC割当・スイッチ割当・スイッチ通過）に依存します。ここでルーターの内部処理はCPUのパイプラインと同じく段に分けて高クロック化されており、考え方はアウトオブオーダー実行の資源割当とも通じます。

スループットは単位時間あたり運べるフリット量で、上限を決めるのが二分割帯域です。負荷を上げていくと、ある**飽和点（saturation throughput）**までレイテンシはほぼ平坦に保たれ、飽和点を超えると待ち行列が発散してレイテンシが急上昇します。NoCの設計目標は、現実のトラフィックがこの飽和点に達しないよう、トポロジ・経路選択・VC数のバランスを取ることです。

ECCによる誤り訂正がメモリ転送を守るのと同様、NoCのリンクにもCRCや再送が組まれますが、性能の主役はあくまでトポロジ・ルーティング・フロー制御の三層です。

まとめ

• 共有バスやクロスバは競合と配線でメニーコアに耐えられないため、NoCは各ノードにルーターを付けてリンクで網状に結び、データをフリットに分けて多段ホップで運ぶパケット交換を採る。
• トポロジはメッシュ／リング／トーラスが基本で、直径がレイテンシの、二分割帯域がスループットの天井を決める。VLSIに素直なメッシュが主流。
• ルーティングの**XY（次元順）**は決定的でデッドロックフリー、適応は混雑を迂回するが、ターンモデルで旋回を制約し循環依存を断たないとデッドロックする。
• フロー制御はクレジットベースでバッファあふれを防ぎ、仮想チャネルが物理リンクを多重化してHoLブロッキングを緩和し、デッドロック回避も兼ねる。この三層の協調がNoCの性能を作る。

ルーターのパイプライン化はCPUパイプラインの考え方と、待ち時間を隠す資源割当はアウトオブオーダー実行と、リンクの誤り対策はECCによる誤り訂正と地続きです。