スイッチとMIN コンピュータアーキテクチャ 特論 テキスト92ページ~130 ページ バス結合型の問題点 メモリへのパスが単一 一度に1つのプロセッサしかアクセスできない 接続可能なプロセッサ数は最近の情勢では4 スイッチ結合型UMA . . . . Local Memory CPU Interface Switch …. Main Memory Local Memoryは持たない場合もある . . . . スイッチ結合型UMA CPU Interface Switch …. Main Memory CPUに直結しているMain MemoryをHome Memoryと呼ぶ場合がある スイッチ結合型UMAの特徴 複数のメモリモジュールが同時にアクセス 可能 行列のアクセス等科学技術計算に向いて いる キャッシュのコンシステンシィを取ることが 難しい クロスバスイッチ n 交点がスイッチ スイッチ数 (クロスポイント数)が nxm m ノンブロッキング性 行き先が異なれば 衝突しない n m 出線競合 n 各バスにはアービタが必要 入力にはバッファも 必要 X クロスバのハードウェア 量はクロスポイント数 だけでは決まらない m クロスバの利点欠点 ノンブロッキング性 単純な構造、制御 ハードウェア量が大きすぎるというのはあ る意味では嘘 1チップで閉じる性質があり、チップのピン 数ネックとなり、拡張が困難 MIN(Multistage Interconnection Network) 多段接続網 小規模なクロスバを多段に接続することに より、大規模なスイッチを構成 等距離間接網に属する クロスポイント数はクロスバより有利 バンド幅、レイテンシィともに不利になる 分類 ブロッキング網:あて先が違っても衝突す る:NlogNタイプ、π網他 リアレンジブル網:衝突なしにスケジュール することができる:Benes網、Clos網(構成 による) ノンブロッキング網:衝突なしが保証され る:Clos網、Batcher-Banyan網 MINの性質 ランダム転送における通過率 並び替え(permutation)能力 ブロック化能力(partition) 耐故障性(fault torelance) 制御法 ブロッキング網 NlogN網 – Omega網 – Generalized Cube網 – Baseline網 ランダム転送における通過率はまったく同じ π網 Omega網 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 スイッチングエレメント(この場合2x2のクロス バ)数は、1/2NxLogN Perfect Shuffle 1ビット左にローテーションする 000 001 010 011 100 101 110 111 000 010 100 110 001 011 101 111 Inverse Shuffle 右ローテーション Destination Routing あて先の番号を上の桁からチェック 0ならば上、1ならば下に進む 000 001 010 011 100 101 110 111 1→3 5→6 000 001 0 1 010 011 1 1 100 101 1 0 110 111 0→0 4→2 Blocking 000 001 X 000 001 010 011 010 011 100 101 100 101 110 111 110 111 行き先が違っていても同一リンクを使う Omega網の一般化(Delta網) 接続も同様のシャッフル 00 01 10 11 0 1 2 3 20 21 30 31 0 1 2 3 2 00 01 10 11 1 20 21 30 31 スイッチングエレメントはサイズの大きいクロス バを利用するのが有利 Omega網の特徴 結線パタンが全て同じ destination routingが可能 有用なpermutationが多い partitioning,拡張性はダメ 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網の特徴 ルーティングはsourceとdestinationの差 を見る partitioning,拡張性に優れる destination routingはできない 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網を2つ接続 ビット逆順並べ替え 0 1 2 3 4 5 6 7 0 4 2 6 1 5 3 7 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 0 5 2 7 000 0 001 4 010 2 6 011 1 4 3 6 100 101 1 5 110 3 111 7 最初の網:上からの入力を優先 次の網:通常のDestination Routing 衝突しない 並び替え能力の強化 すべてのパタンの並び替えが可能= リアレンジブル網 シャッフル接続ではOmega網3段で可能 シャッフル接続と逆シャッフル接続だと2段 で可能:Benes網 Benes網 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 最もハードウェアの少ないリアレンジブル網 ノンブロッキング網 Clos網 – m>n1+n2-1でノンブロッキング – m>=n2でリアレンジブル – そうでなければブロッキング Clos網 n1xm r1xr2 m m=n1+n2-1:ノンブロッキング m=n2:リアレンジブル m<n2:ブロッキング ... ... r1 mxn2 r2 Batcher網 5 7 0 4 5 7 4 0 0 4 5 7 2 1 3 6 1 2 6 3 6 3 2 1 0 1 2 3 4 5 6 7 Batcher-banyan網 5 7 0 4 5 7 4 0 0 4 5 7 2 1 3 6 1 2 6 3 6 3 2 1 0 1 2 3 4 5 6 7 Batcher-banyan網の問題点 同一あて先のパケットが複数あると衝突が 防げない。 banyan網の拡張等の方法で解決可能 Banyan網 出発地と目的地間にパスが1本のみ存在 途中ステージ数等は問わない グラフ理論的アプローチ SW-Banyan,CC-Banyan,Barrel Shifter 不規則でもかまわない 分類 Clos網 Omega網 Banyan Benes網 π網 Baseline網 Generalized Cube網 Blocking Batcher Nonblocking Banyan網 Rearrageble 耐故障性を持つ網 複数の経路を持たせる。 冗長性が必要。 実際は制御が困難 最近はチップ歩留まりの向上を狙う場合も 多い。 Extra Stage Cube (ESC) 000 001 000 001 010 011 010 011 X 100 101 100 101 110 111 110 111 1段余計に接続+Bypass 故障があれば、もう一つのパスがある バッファの構造 000 001 000 001 010 011 010 011 100 101 100 101 110 111 110 111 混雑した場合は、バッファに溜めておく Hot spot Contention 000 001 混雑 010 011 100 101 110 111 Tree状にバッファが飽和していく(Tree Satur ation) Hot Spotの緩和のために Message Combining – 複数のパケットをひとまとめにする – 実装が難しい 仮想チャネル – NORAのところで詳説 コンパイラで調節 本日の課題 8入出力のOmega網について、 Destination Routingが可能なことを証明 (説明)せよ
© Copyright 2024 ExpyDoc