スイッチとMIN コンピュータアーキテクチャ特論テキスト９２ページ～１３0 ページバス結合型の問題点  メモリへのパスが単一一度に１つのプロセッサしかアクセスできない接続可能なプロセッサ数は最近の情勢では４スイッチ結合型UMA ．．．． Local Memory CPU Interface Switch …． Main Memory Local Memoryは持たない場合もある．．．．スイッチ結合型UMA CPU Interface Switch …． Main Memory CPUに直結しているMain MemoryをHome Memoryと呼ぶ場合があるスイッチ結合型UMAの特徴複数のメモリモジュールが同時にアクセス可能  行列のアクセス等科学技術計算に向いている  キャッシュのコンシステンシィを取ることが難しい  クロスバスイッチｎ交点がスイッチスイッチ数（クロスポイント数）がｎｘｍｍノンブロッキング性行き先が異なれば衝突しないｎｍ出線競合ｎ各バスにはアービタが必要入力にはバッファも必要 X クロスバのハードウェア量はクロスポイント数だけでは決まらないｍクロスバの利点欠点ノンブロッキング性  単純な構造、制御  ハードウェア量が大きすぎるというのはある意味では嘘  １チップで閉じる性質があり、チップのピン数ネックとなり、拡張が困難  MIN（Multistage Interconnection Network) 多段接続網小規模なクロスバを多段に接続することにより、大規模なスイッチを構成  等距離間接網に属する  クロスポイント数はクロスバより有利  バンド幅、レイテンシィともに不利になる  分類ブロッキング網：あて先が違っても衝突する：ＮｌｏｇＮタイプ、π網他  リアレンジブル網：衝突なしにスケジュールすることができる：Benes網、Clos網（構成による）  ノンブロッキング網：衝突なしが保証される：Clos網、Batcher-Banyan網  MINの性質ランダム転送における通過率  並び替え（ｐｅｒｍｕｔａｔｉｏｎ）能力  ブロック化能力（ｐａｒｔｉｔｉｏｎ）  耐故障性（ｆａｕｌｔｔｏｒｅｌａｎｃｅ）  制御法  ブロッキング網  NlogN網 – Omega網 – Generalized Cube網 – Baseline網  ランダム転送における通過率はまったく同じ  π網 Omega網 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111  スイッチングエレメント（この場合２ｘ２のクロスバ）数は、１／２NｘLogN Perfect Shuffle  １ビット左にローテーションする０００００１０１００１１１００１０１１１０１１１００００１０１００１１０００１０１１１０１１１１ Inverse Shuffle 右ローテーション Destination Routing あて先の番号を上の桁からチェック０ならば上、１ならば下に進む 000 001 010 011 100 101 110 111 1→３５→６ 000 001 ０１ 010 011 １１ 100 101 １０ 110 111 ０→０４→２ Blocking 000 001 X 000 001 010 011 010 011 100 101 100 101 110 111 110 111  行き先が違っていても同一リンクを使う Omega網の一般化（Delta網）接続も同様のシャッフル  ０００１１０１１０１２３２０２１３０３１０１２３２０００１１０１１１２０２１３０３１スイッチングエレメントはサイズの大きいクロスバを利用するのが有利 Omega網の特徴結線パタンが全て同じ  ｄｅｓｔｉｎａｔｉｏｎｒｏｕｔｉｎｇが可能  有用なｐｅｒｍｕｔａｔｉｏｎが多い  ｐａｒｔｉｔｉｏｎｉｎｇ，拡張性はダメ  Generalized Cube 000 001 000 100 000 010 000 001 010 011 100 101 000 001 010 011 100 100 110 101 110 111 100 101 110 111 1bit違ったもの同士を同一スイッチに繋ぐ Generalized Cubeのルーティング 000 001 000 001 010 011 010 011 0 1 0 100 101 100 101 110 111 110 111 出発地と目的地のビットを比較(Ex-Or）：一致(0)：まっすぐ不一致(1)：クロス方向 001→011 010 Partitioning 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 互いに他の交信を妨害しないブロック拡張性 Generalized Cube網の特徴ルーティングはｓｏｕｒｃｅとｄｅｓｔｉｎａｔｉｏｎの差を見る  ｐａｒｔｉｔｉｏｎｉｎｇ，拡張性に優れる  ｄｅｓｔｉｎａｔｉｏｎｒｏｕｔｉｎｇはできない  Baseline網最初のシャッフルはない 000 001 001 001 010 011 100 101 010 100 110 111 逆シャッフルする範囲を狭くしていく 000 001 010 011 100 101 110 111 Baseline網のDestination Routing 000 001 000 001 1 010 011 100 101 010 011 1 110 111 Omega網同様のDestination Routingが可能 0 100 101 110 111 Baseline網のPartitioning 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 Baseline網  Omega網とGeneralized Cube網の利点を併せ持つ – Destination Routing – Partitioning – 拡張性  NECのCenjuシリーズに用いられている π網  000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 Omega網を２つ接続ビット逆順並べ替え０１２３４５６７  ０４２６１５３７ 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 Omega網では衝突が起きるビット逆順並べ替え 000 001 010 011 100 101 110 111 ０５２７ 000 ０ 001 ４ 010 ２６ 011 １４３６ 100 101 １５ 110 ３ 111 ７最初の網：上からの入力を優先次の網：通常のDestination Routing 衝突しない並び替え能力の強化すべてのパタンの並び替えが可能＝リアレンジブル網  シャッフル接続ではOmega網３段で可能  シャッフル接続と逆シャッフル接続だと２段で可能：Benes網  Ｂｅｎｅｓ網 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111  最もハードウェアの少ないリアレンジブル網ノンブロッキング網  Ｃｌｏｓ網 – ｍ＞ｎ１＋ｎ２－１でノンブロッキング – ｍ＞＝ｎ２でリアレンジブル – そうでなければブロッキング Clos網ｎ１ｘｍｒ１ｘｒ２ｍ m=n1+n2-1：ノンブロッキング m=n2：リアレンジブルｍ＜ｎ２：ブロッキング ... ... ｒ１ｍｘｎ２ｒ２ Batcher網５７０４５７４００４５７２１３６１２６３６３２１０１２３４５６７ Batcher－ｂａｎｙａｎ網５７０４５７４００４５７２１３６１２６３６３２１０１２３４５６７Ｂａｔｃｈｅｒ-ｂａｎｙａｎ網の問題点同一あて先のパケットが複数あると衝突が防げない。  ｂａｎｙａｎ網の拡張等の方法で解決可能  Banyan網出発地と目的地間にパスが１本のみ存在  途中ステージ数等は問わない  グラフ理論的アプローチ  SＷ-Banyan，CC-Banyan，Barrel Shifter  不規則でもかまわない分類 Clos網 Omega網 Banyan Benes網 π網 Baseline網 Generalized Cube網Ｂｌｏｃｋｉｎｇ Batcher Ｎｏｎｂｌｏｃｋｉｎｇ Banyan網Ｒｅａｒｒａｇｅｂｌｅ耐故障性を持つ網複数の経路を持たせる。  冗長性が必要。  実際は制御が困難  最近はチップ歩留まりの向上を狙う場合も多い。  Extra Stage Cube (ESC) 000 001 000 001 010 011 010 011 Ｘ 100 101 100 101 110 111 110 111  １段余計に接続＋Ｂｙｐａｓｓ故障があれば、もう一つのパスがあるバッファの構造 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111  混雑した場合は、バッファに溜めておくＨｏｔｓｐｏｔＣｏｎｔｅｎｔｉｏｎ 000 001 混雑 010 011 100 101 110 111  Ｔｒｅｅ状にバッファが飽和していく(ＴｒｅｅＳａｔｕｒａｔｉｏｎ） Hot Ｓｐｏｔの緩和のために  Message Combining – 複数のパケットをひとまとめにする – 実装が難しい  仮想チャネル – NORAのところで詳説  コンパイラで調節本日の課題  ８入出力のOmega網について、 Destination Routingが可能なことを証明（説明）せよ