るPEのみでいい。そのため3次元階層型ネットワークの最大値は以下のようにして求める。
Maximum;
CONVERGE BM();
for j=2:L
if(a [j01:0]
x
=0 and a [j01:0]
y
=0 and a [j01:0]
z
=0),OPERATION(m,m+2 j
);endif;
CONVERGE network-j();
endif;
endfor;
g
= 4( N01) (4.1)
S
max
= 2(
p
N01) (4.2)
3Dトーラス：
S
bitonic
= 6 N
1
3
01
X
j=0 N
1
3
2 j
= 6(N 1
3
01) (4.3)
S
max
= 3(N 1
3
01) (4.4)
最大値問題では値を返す必要がないため、通信ステップ数がバイトニックマージの半分 になっているのが非階層型ネットワークの特徴である。これに対して、3次元階層型ネッ トワークの総通信ステップ数は以下のようになる。
3次元階層型トーラス：
S
bitonic
= (L01)3(4+2)64+18
= 1152(L01)+18 (4.5)
S
max
= 18L (4.6)
3次元階層型メッシュ：
S
bitonic
= (L01)2(4+2)64=4+12
= 192(L01)+18 (4.7)
S
max
= 12(L01)+18 (4.8)
(4.9)
階層型ネットワークでは、O(logN)の通信ステップ数でアプリケーションの実行が可 能である。しかし、バイトニックマージのように全PE間の通信が必要なアプリケーショ ンではオーダーにかかる係数が大きくなっている。これは基本モジュール間のリンクに通 信の集中が起こるためである。図 4.2と図 4.3はバイトニックソートと最大値問題の実行 に必要な総通信ステップ数である。基本モジュールを用いた結合方式ではレベルが上がる につれ階層間のネットワーク数が増加する。例えば 次元階層型トーラスのレベル 階層
表4.1: 総通信ステップ数
バイトニックマージ 最大値問題
総通信ステップ数 オーダー 総通信ステップ数 オーダー
2Dトーラス 4(
p
N 01) O(
p
N) 2(
p
N 01) O(
p
N)
3Dトーラス 6(N13 01) O(
p
N) 3(N
1
3
01) O(
p
N)
3次元階層型トーラス 1152(L01)+18 O(logN) 18L O(logN)
3次元階層型メッシュ 12(L-1)+18 O(logN) 12(L-1)+18 O(logN)
ル数に等しい64の3Dトーラスで階層間の結合が行なわれる。つまりレベルが増すにつ れ階層の並列化が進む。3次元階層型トーラスは基本モジュールのPE数(64)に対して、
基本モジュール間の結合は1本で行なわれているため、基本モジュール間のリンクに通信 の集中が起こり、更に階層化の規模が大きくPE数に対しレベルの上昇が遅いため、2D メッシュよりも高速な演算を行なうには数十万PEが必要であるという結果が得られた。
それに対して、3次元階層型メッシュは基本モジュールのPE数(64)に対して、基本モ ジュール間の結合を4本で行ない、階層化の規模も小さいため3次元階層型トーラスと 比較して数万PEで十分な性能を得ることができている。数十万PEでは3Dトーラスよ りも高速な演算が可能であるという結果が得られた。最大値のように必要とするデータが 少ない演算では階層型ネットワークのリンクの少なさが影響しないため、非常に少ないス テップ数で演算が可能であった。