NORAマシン
コンピュータアーキテクチャ特論
テキスト140-147ページ
NORA(No Remote Access
Memory Model)




共有メモリを持たない
データの交換はメッセージ(パケット)のや
り取りで行う
同期用のハードウェアを持つ場合が多い
最も簡単にピーク性能を得ることができる
– ギネスブックに載っているのは常にNORA

メッセージ交換の方法は共通ライブラリ化
(MPI,PVM)されている
メッセージ転送の方法
(ブロック型:ランデヴ)
Send
Receive
Send
Receive
メッセージ転送の方法
(送信ノンブロッキング型)
Send
Receive
Send
Receive
PVM(Parallel Virtual Machine)



基本的に送信バッファ方式
受信はバッファにパケットが到着している
かどうかをチェックする機能とブロッキング
受信が用意されている
バリア同期が用意されている
MPI
(Message Passing Interface)




1対1通信でPVMの範囲をカバー
グループ通信の導入
送信側、受信側でさまざまなメッセージの
待ち方をサポート
通信の条件指定タグによるエラーのチェッ
ク
共有メモリvs.
メッセージパッシング

共有メモリ支持
– 分散OSの構築が容易
– コンパイラによる並列化が容易
– Smalltalkの実装だって実は共有メモリが必要
– GHC → KL/Iの流れを見よ

メッセージパッシング支持
– プログラム正当性の証明が楽(ブロック型)
– 共有変数は所詮副作用に基づく
– 共有メモリ実現のコストが大
NORAマシンの結合網

直接網(不等距離間接網)が用いられる
– ノード同士が直接リンクで接続される


交信の局所性を利用する
大規模なサイズに適応
基本的な直接網
直線
スター
リング
ツリー
つ
り
x
完全結合
メッシュ
直接網の性能指標(Dとd)

直径(Diameter:D)
– 回り道をせずに最も遠い2ノード間でメッセー
ジを送った場合の転送回数

次元(degree:d)
– あるノードに接続されているリンク数

Dは性能、dはコストの目安
– 最近は性能は転送容量、コストは長距離リン
クの数を重要視する傾向がある
直径 Diameter
2(n-1)
その他の要求事項





均一性(Uniformity):ネットワークがどこで
も同質である
拡張性(Extendability):サイズを容易に拡
張できる(解釈の相違あり)
耐故障性(Fault Torelance):リンク、ノー
ドの故障によるネットワークのダメージ
エンベダビリティ(Embeddability):他の網
のエミュレーションの能力
Bisection Bandwidth
bi-section bandwidth
2つ切った場合の転送量
ハイパーキューブ
0000
0100
1000
1100
0001
0101
1001
1101
0010
0110
1010
1110
0011
0111
1011
1111
ハイパーキューブの
ルーティング
0101→1100
0000
0001
0010
0011
違っているビットは
0100
1000
1100
0101
1001
1101
0110
1010
1110
0111
1011
1111
ハイパーキューブの直径
0101→1010
全ビット違っている
のが最も遠い
0000
0100
1000
1100
0001
0101
1001
1101
0010
0110
1010
1110
0011
0111
1011
1111
ハイパーキューブの特徴





D,dともにlogN
高い転送能力、Bisection Bandwidth
高いエンベダビリティ
基本的な性質を全て満足(拡張性は異論
があるが、、)
第一世代のNORAはハイパーキューブマ
シンが主流(iPSC,NCUBE,FPS-T)
ハイパーキューブの問題点





リンク数が多い
長距離リンクが多い
プロセッサの性能が上がると共に実現が
困難
パケット転送方式の革新により小さいDと
いうメリットがなくなってきている
プログラミングはハイパーキューブのジレ
ンマがある
ハイパーキューブは拡張性があ
るか?

ある(理論やが多い)
– スケールに応じてリンク数すなわち転送容量
が確保できる。したがって、転送容量の点では
拡張性がある

ない(実装やが多い)
– ノードのリンク数で、最大に構築できるシステ
ムサイズが制限される
ハイパーキューブのジレンマ


2次元・3次元メッシュと違ってトポロジを考
慮したプログラムは難しい
トポロジを無視して任意の交信をサポート
しようとすると性能が落ちてしまう
2次元、3次元メッシュは、
トポロジに適合したキラーアプリケーション
(偏微分方程式陽解法など)がある
近くに配置すれば性能は維持できる
k-ary n-cube




2次元、3次元メッシュ・トーラスの一般化
各ノードは、k進数n桁の番号を振る
各桁について、残りの桁が全て等しいノー
ドとの間に、0→1→…n-1の順にリンクで
結ぶ
n-1→0のリンクを入れればトーラス、なけ
ればメッシュ
k-ary n-cube
00
01
02
3-ary 1-cube
10
11
12
20
21
22
3-ary 2-cube
k-ary n-cube
2 00
0 00
010
0 20
1 00
101
001
00 2
10
11 0
1 11
0 11
012
120
120
121
0 21
0 22
201
20 2
10 2
11
212
3-ary 1-cube
112
221
2 22
3-ary 2-cube
122
3-ary 3-cube
3-ary 4-cube
0***
1***
2***
400
k-ary n-cube
300
200
100
000
001
002
003
004
010
014
020
024
030
034
040
044
444
n桁 k進数: 5-ary 3-cube
1桁のみ異なるノードを直線またはループで接続
5-ary 4-cube
0***
1***
2***
4***
3***
k-ary n-cubeの特徴




2次元、3次元メッシュ、トーラス、ハイパー
キューブ(binary n-cube)を含む
d=2nで小さい、Dは大きめ(n乗根のオー
ダ)
近接線が多い
NORAは一貫してk-ary n-cubeが主流で、
nを小さく、kを大きくの方向に移っている
課題

6-ary 4-cubeの直径(D)と次数(d)を求
めよ
ダウンロード

NUMAの構成