第 5 章 評価
5.2 分散ルーティング方式における評価結果
第5章 評価
経路分散の度合いを示す静的な評価指標
• CP U P(Crossing routing Paths on UP channel)
up方向に向かう各チャネルを通過する経路数 (crossing routing path) の平均値を
CP U P とした．CP U P は，ルートスイッチ方向へのトラフィック量の目安となる．
• CP DW(Crossing routing Paths on DoWn channel)
down方向に向かう各チャネル上の crossing routing pathの平均値をCP DW とし
た．CP DW は，葉スイッチ方向へのトラフィック量の目安となる．
第5章 評価
表5.2: イレギュラーネットワークにおける平均スループット
16スイッチ 64スイッチ
Uniform Bit-reversal Uniform Bit-reversal BFS Up*/Down* 0.1050 0.1332 0.0357 0.0389 DFS Up*/Down* 0.1090 0.1334 0.0383 0.0451
L-turn/α 0.1124 0.1435 0.0434 0.0486
L-turn/β 0.1122 0.1450 0.0438 0.0500
R-turn/α 0.1053 0.1343 0.0331 0.0336
R-turn/β 0.1032 0.1347 0.0340 0.0338
(2) レイテンシの評価
次に，16 および64 スイッチのイレギュラーネットワークにおける各ルーティングアル ゴリズムの uniformおよび bit-reversal トラフィックにおける受信トラフィックとレイテ ンシの関係を示したグラフを，図 5.1および図 5.2にそれぞれ示す．図5.1および図 5.2 は，ランダムに生成した20のトポロジのうち，各 L-turn ルーティングと R-turn ルー ティングのレイテンシが平均に近いトポロジにおける結果を示している．図において，各 ルーティングアルゴリズムのレイテンシの優劣の傾向はスループットとほぼ同様であり，
L-turnルーティングがすべての条件でもっとも低いレイテンシを実現する一方で，R-turn
ルーティングがもっとも高いレイテンシとなっている．
(3) 静的な評価指標の評価
次に，16および 64スイッチのイレギュラーネットワークにおける，各ルーティングア ルゴリズムの静的な評価指標について，表5.3および表5.4にそれぞれ示す．まず，表5.3 において，経路制限の度合いを示す M P RとP T については，DFS Up*/Down*ルーティ ングが若干優れた値を示し，その他のルーティングについては，ほぼ同等であることがわ かる．これより，DFS Up*/Down* ルーティングは，禁止ターン数を減らすことにより，
他のルーティングよりも多くの最短経路を確保していると考えられる．これに対し，禁止 ターン分散の度合いを示す SDP T とP P T については，各L-turn および R-turnルー ティングが，各Up*/Down*ルーティングに比べて大幅に小さな値を実現していることが わかる．各 L-turnおよび R-turnルーティングの SDP T とP P T は，ほぼ同等であり，
BFS Up*/Down* ルーティングに対して，SDP T については約40%，P P T については 約80%の減少を実現し，同様に，DFS Up*/Down* ルーティングに対しては，それぞれ 約25%，約75%の減少を実現している．これより，L-turn および R-turn ルーティング
は，Up*/Down*ルーティングに比べて，より均等な禁止ターン分散を実現しているとい
える．
しかし，ほぼ同等の SDP T と P P T を実現しているにもかかわらず，表 5.2におい
て，L-turnルーティングがスループット向上を実現する一方で，R-turnルーティングは，
Up*/Down* ルーティングと同程度のスループットの実現にとどまっている．この原因は，
経路分散の度合いを示す CP U P と CP DW の違いによるものと考えられる．表 5.3に
第5章 評価
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000
0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12
Latency (clocks)
Accepted Traffic (flits/clock/PC) BFS Up*/Down*
DFS Up*/Down*
L-turn/α L-turn/β R-turn/α R-turn/β
(a) Uniform
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000
0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18 0.19
Latency (clocks)
Accepted Traffic (flits/clock/PC) BFS Up*/Down*
DFS Up*/Down*
L-turn/α L-turn/β R-turn/α R-turn/β
(b) Bit-reversal
図 5.1: イレギュラーネットワーク(16スイッチ)における受信トラフィックと 平均レイテンシ
第5章 評価
0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000
0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05
Latency (clocks)
Accepted Traffic (flits/clock/PC) BFS Up*/Down*
DFS Up*/Down*
L-turn/α L-turn/β R-turn/α R-turn/β
(a) Uniform
0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000
0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 0.055 0.06
Latency (clocks)
Accepted Traffic (flits/clock/PC) BFS Up*/Down*
DFS Up*/Down*
L-turn/α L-turn/β R-turn/α R-turn/β
(b) Bit-reversal
図 5.2: イレギュラーネットワーク(64スイッチ)における受信トラフィックと 平均レイテンシ
第5章 評価
おいて，L-turn ルーティングでは，CP U P より CP DW の値が大きくなっていること
から，ルートスイッチ方向よりも葉スイッチ方向により多くのトラフィックが流れやすく なっていると考えられる．これにより，L-turnルーティングでは，ルートスイッチ周辺の ホットスポット発生が緩和され，葉スイッチ周辺により多くのトラフィックが分散された ことにより，スループットの向上を実現したものと考えられる．一方，R-turnルーティン
グでは，CP DW より CP U P の値が大きくなっていることから，L-turn ルーティング
と対照的に，ルートスイッチ方向にトラフィックが流れやすくなり，ルートスイッチ周辺 のホットスポットがより発生しやすくなっているものと考えられる．この原因として，次
のような R-turnルーティングの禁止ターンの特性が考えられる．R-turnルーティングで
は，ターン TRD,LU を除く LU 方向へのターンをすべて許可しているため，これにより パケットがルートスイッチ方向に集中しやすくなるものと考えられる．一方，RD 方向か らその他の方向へのターンは禁止されているため，対照的に葉方向にはパケットが転送さ れにくくなっているものと考えられる．これらの特性により，R-turnルーティングでは，
L-turn ルーティングと異なり，スループット向上が実現できなかったものと考えられる．
なお，各 Up*/Down* ルーティングにおける CP U P と CP DW は等しくなっている
が，これは， Up*/Down*ルーティングでは，(1) upと downの2つの方向しか存在し ない，(2) 任意のスイッチ間には，互いに反対方向に向かう対照的な 2つの経路が存在す る，という特性のためである．スパニングツリーベースの有向グラフでは，葉スイッチ周 辺よりもルートスイッチ周辺に近づくにつれ利用可能な経路が少なくなるため，CP U P
とCP DW が等しい場合，ルートスイッチ方向にトラフィックが偏りやすくなると考えら
れる．
表 5.3: イレギュラーネットワーク(16スイッチ)における静的な評価指標
M P R P T SDP T P P T CP U P CP DW
BFS Up*/Down* 89.6 3.181 3.723 1.591 11.40 11.40 DFS Up*/Down* 92.9 2.863 3.061 1.431 11.73 11.73 L-turn/α 88.9 3.175 2.264 0.366 10.76 12.54 L-turn/β 88.8 3.172 2.379 0.388 10.66 12.78 R-turn/α 88.8 3.184 2.300 0.375 12.54 10.78 R-turn/β 88.6 3.163 2.328 0.369 12.64 10.74
次に，表5.4についてみると，64スイッチの場合の各ルーティングアルゴリズムの優劣 の傾向は，16スイッチの場合の表5.3と同様であり，各 L-turnおよびR-turnルーティン グがもっとも均等な禁止ターンの分散を実現していることがわかる．ただし，64スイッチ の場合には，各ルーティングアルゴリズムの M P Rが16スイッチの場合に比べて約20〜 25% 減少していることから，トポロジ的な最短経路が確保しにくくなっているといえる．
これにより，スイッチ数が増加した場合には，禁止ターンのより均等な分散と葉スイッチ 方向へのトラフィックの分散が，スループット向上のためにより重要となるものと考えら れる．表 5.2において，64スイッチの場合に，L-turnルーティングのスループット向上 の割合が増加する一方で，R-turnルーティングのスループット低下の割合が増加した原 因は，このためであると考えられる．
第5章 評価
表 5.4: イレギュラーネットワーク(64スイッチ)における静的な評価指標
M P R P T SDP T P P T CP U P CP DW
BFS Up*/Down* 64.2 2.994 3.626 1.497 86.16 86.16 DFS Up*/Down* 72.9 2.602 2.454 1.301 85.54 85.54 L-turn/α 66.9 2.890 2.288 0.316 82.94 91.63 L-turn/β 67.1 2.866 2.271 0.306 82.47 91.69 R-turn/α 67.0 2.886 2.281 0.316 91.14 82.38 R-turn/β 67.0 2.863 2.269 0.302 91.96 82.74
以上より，表5.2において，L-turnルーティングがDFS Up*/Down* ルーティングよ りも高いスループットを実現していることから，スループットの向上には，禁止ターン数 の削減よりも禁止ターンのより均等な分散による効果の方が大きいと考えられる．ただし，
先に述べたL-turnルーティングとR-turnルーティングの性能差の原因から，スループッ ト向上のためには，より均等な禁止ターンの分散と葉スイッチ方向へのトラフィック分散 の両立が重要であると考えられる．
5.2.2 2次元メッシュにおける評価 (1) スループットの評価
4×4 および8×8 スイッチの2次元メッシュにおける各ルーティングアルゴリズムの uniform および bit-reversal トラフィックにおけるスループットを，表 5.5に示す．イレ ギュラーネットワークにおける結果と同様に，すべての条件において，L-turnルーティン グがもっとも高いスループットを実現しており，スループット向上はスイッチ数が大きい ほどより大きくなっている．BFS Up*/Down*ルーティングに対するスループット向上は，
イレギュラーネットワークの場合よりも大きく，約10〜 50%の向上となっている．同様に，
R-turnルーティングは，すべての条件において，BFS Up*/Down* ルーティングに対し
てスループットが低下しており，スループット低下はスイッチ数が大きいほどより大きく なっている．BFS Up*/Down* ルーティングに対するスループット低下は，同様に，イ レギュラーネットワークの場合よりも大きく，約10〜 30%の低下となっている．L-turn/α と L-turn/β および R-turn/α とR-turn/β のスループットがそれぞれ同じ値となってい るが，これは，4×4 および 8×8スイッチ構成の 2次元メッシュにおいて，これらによ る全スイッチ間の経路(禁止ターン分布)がそれぞれまったく同じものとなっているためで ある．
イレギュラーネットワークにおける結果と異なり，2次元メッシュでは，DFS Up*/Down*
ルーティングのスループット低下が顕著となっている．16スイッチのuniformトラフィック の場合を除いたすべての条件で，もっとも低いスループットを示し，特に，BFS Up*/Down*
ルーティングに対しては，最大で約40%，L-turnルーティングに対しては，最大で約60%
の低下となっている．
第5章 評価
表5.5: 2次元メッシュにおけるスループット
4×4スイッチ 8×8スイッチ
Uniform Bit-reversal Uniform Bit-reversal BFS Up*/Down* 0.0863 0.0877 0.0357 0.0380 DFS Up*/Down* 0.0796 0.0601 0.0215 0.0226
L-turn/α 0.0963 0.1069 0.0510 0.0575
L-turn/β 0.0963 0.1069 0.0510 0.0575
R-turn/α 0.0791 0.0769 0.0257 0.0300
R-turn/β 0.0791 0.0769 0.0257 0.0300
(2) レイテンシの評価
次に，4×4 および 8×8スイッチの2次元メッシュにおける各ルーティングアルゴリ ズムの uniform および bit-reversal トラフィックにおける受信トラフィックとレイテンシ の関係を示したグラフを，図 5.3および図 5.4にそれぞれ示す．図より，各ルーティング アルゴリズムのレイテンシの優劣の傾向は，イレギュラーネットワークと同様に，スルー プットとほぼ同様であり，L-turnルーティングが，すべての条件でもっとも低いレイテン シを実現している．R-turnルーティングは，DFS Up*/Down* ルーティングに比べると，
ほぼ同等またはより低いレイテンシを実現しているが，BFS Up*/Down* ルーティングに 対しては，より高いレイテンシとなっている．
(3) 静的な評価指標の評価
次に，4×4 および 8×8 スイッチの 2次元メッシュにおける，各ルーティングアル ゴリズムの静的な評価指標について，表5.6および表5.7にそれぞれ示す．表5.6および 表 5.7より，経路制限に関する M P R とP T については，8×8 スイッチにおける DFS
Up*/Down* ルーティングをのぞいて，各ルーティングアルゴリズムは，ほぼ同等の値を
示すことがわかる．特に，M P R の値から，2次元メッシュにおける経路のほとんどは，
トポロジ的な最短経路となることがわかる．これに対し，禁止ターン分散の度合いを示す
SDP T と P P T については，8×8 スイッチにおける BFS Up*/Down* ルーティングの
SDP T をのぞいて，イレギュラーネットワークの場合と同様に，各L-turnおよび R-turn
ルーティングが，もっとも小さい値を実現しており，特にP P T については，4×4スイッ チで 0，8×8スイッチで Up*/Down*ルーティングに対して 約92%の減少となり，大幅 に禁止ターンのペアを削減していることがわかる．これより，イレギュラーネットワーク の場合と同様に，L-turnルーティングと R-turnルーティングが，より均等な禁止ターン の分散を実現しているといえる．また，経路分散に関する各ルーティングアルゴリズムの
CP U P とCP DW の差についても，イレギュラーネットワークと同様の傾向となってい
ることがわかる．このため，同様に，L-turnルーティングにおいてはスループットが向上
し，R-turnルーティングにおいてはスループットが低下したものと考えられる．