間接網のいろいろ - Amano Lab | Dept. of Information

スイッチと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が可能なことを証明
(説明)せよ