パケット転送方式コンピュータアーキテクチャ特論テキスト１６６－１８５ページパケットとは？Ｆｌｉｔ送り元から目的地にパスを張る方法サーキットスイッチング 8bit~64bit Header 情報を細かいかたまり（パケット）に分けて送るパケットスイッチング destination length，source，etc．Ｂｏｄｙパケット転送法  Store and Forward方式 – 各ノードで一度パケット全体を溜める – TCP/IPではこれを使わざるを得ない  Wormhole方式 – パケットは次々に先に進める – ブロックされると全体が止まる  Virtual Cut Through方式 – ブロックされるとバッファに溜める Store and Forward方式一度バッファにパケット全体を格納してから進むレイテンシィが大きい D(h+b) 必要なバッファ容量が大きいソフトウェアで制御可能 Wormhole方式パケットはブロックされない限り先に進めるレイテンシィは小さいｈD+ｂ必要なバッファ容量が小さい専用ルータが必要 Virtual Cut Through方式ブロックされた時のみにバッファに格納レイテンシィはWormholeと同じ必要なバッファ容量もStore and Forward 専用ルータが必要実際はどうか？    Store and Forwardはソフトウェアでパケットを送っていた第１世代のNORAのみパケット長が長い場合はWormhole方式 Multicastを行う場合はVirtual Cut Through方式 Wormhole方式の問題点迂回車線を設ける Virtual Channel Virtual Channelの実装 Handshake line Ｂｕｆｆｅｒ NODE Link Handshake line Ｂｕｆｆｅｒ MUX Crossbar デッドロックとその回避ループを作らないようにする構造化バッファ法バッファ番号＋１に対してパケットを送る Wormhole対応には構造化チャネル法 e-cube routing 各方向に専用のバッファを確保 (入力リンクが普通）ＷＳＮＥ W→S→E→Ｎの順番に送るループは形成されない e-cube routing ループ構造がある場合００１１１フィードバックループで、チャネル番号を切り替える適応型（Adaptive)ルーティング  経路があらかじめひとつに固定されている – 固定型ルーティング  混雑や故障を迂回するために、経路を動的に選択して用いる – 適応型ルーティング – しかし、デッドロックを起こしてはまずい、、様々な適応型ルーティング  サブネットを用いる方法 – double-Y routing – Planner Adaptive routing  チャネルを用いる方法 – 次元逆転ルーティング – ＊channel （Duato’s Ｐｒｏｔｏｃｏｌ）  確率的な方法 – Chaos routing  方向転換に制限を設ける方法 – Turn モデルＴｕｒｎｍｏｄｅｌＸＸＷｅｓｔＦｉｒｓｔ法ＸＮｏｒｔｈＬａｓｔ法ＸＷｅｓｔＦｉｒｓｔ法による混雑回避ＸＮＷ一度Ｗに行ったら二度とＷには行けないＥＳＤｕａｔｏ‘ｓＰｒｏｔｏｃｏｌ（*-channel）ＣＡ０ＥｓｃａｐｅＰａｔｈＣＡ１ＣＡ３ＣＡ２ Minimal routing(1) [F.Silla,1997] Escape Paths Src Dst Adaptive Paths • 結合網全体に渡る循環の無い論理的な逃げ道 (Escape path)を用意 • 逃げ道と、逃げ道により循環が切断された論理的経路(Adaptive path)によってどのノード間でもパケットを転送可能 • Escape path からAdaptive path への切り替えを禁止 Minimal routing(2) 1. パケットは adaptive path(最短型)で移動できるところまで移動 2. 空いている adaptive path が無い場合 escape path を利用 3. その後は escape path のみを利用して目的t地へ Adaptive path Escape path (up/down routing) S D 適応型ルーティングの研究    ＤｕａｔｏのＰｒｏｔｏｃｏｌで一区切りついた実装と試行の時代無理にデッドロックフリーにしないで、デッドロックする確率を低くし、デッドロックしたら再送する方法も用いられているまとめ  第一世代のＮＯＲＡマシン – ルータ無し、Store and Forward，Hypercube – iPSC，NCUBE，ＦＰＳ－Ｔ  第２世代のNORAマシン – ルータの登場、Wormhole，Virtual Channel – AP1000，Delta，Ｔ３Ｄ   適応型ルーティングの確立不規則ネットワークへの展開演習  4-ary 2-cube上でヘッダ1flit、ボディ15flit のパケットを転送した場合、Store-andForward方式とWarmhole方式のそれぞれについて、最も時間がかかる転送時間を計算せよ。ただし衝突は起こらないと仮定する。