研究の過程と本論文の位置付けについて

L-turnおよびR-turnルーティングは，筆者と鯉渕の共同研究の成果であり，鯉渕の博

士論文[鯉渕02]の一部においても述べられている．以下，L-turnおよびR-turnルーティ ングに関する研究の過程と筆者が担当した作業内容について述べ，本論文の位置付けにつ いてまとめる．

まず，L-turnおよびR-turnルーティングの発端は，Up*/Down*ルーティングにおけ る2つの方向を4つに増加させた上で禁止ターン選択を行なうことにより，イレギュラー ネットワークにおいて，より効率的なルーティングを実現できるのではないか，という鯉

第4章 L-turn/R-turn ルーティング

2-D 1-D dimension of

directed graph (n > 2)

routing algorithm

BFS/DFS Up*/Down* L-turn/R-turn

Turn model channel dependency graph deadlock-free

strategy

Eulerian trail

Smart Adaptive-trail

n-D

routing algorithms for irregular networks

virtual channels

required ? no yes

spanning-tree

required ? yes no yes no

virtual channel

transitions ? yes no yes no

DL Minimal Multiple Spanning-tree Structured Buffer Pool LASH

図 4.28: イレギュラーネットワーク向けルーティングアルゴリズムの分類

渕の提案によるものである．そこでまず，筆者と鯉渕により，前順走査を利用した 2次元 有向グラフであるH/V グラフの構築手順が確立された．当初は，H/Vグラフにおける Turnモデルの適用手順が確立されておらず，まず，第4.2.1節で述べた 2次元メッシュに おける Turnモデルと同様の直観的な選択により， LU 方向へ向かうターン集合だけを禁 止ターンとして選択したルーティングアルゴリズム⁵が鯉渕により提案され，確率モデル シミュレーションによる予備評価が行なわれた．予備評価およびこれ以降の評価では，筆 者が実装したフリットレベルの相互結合網シミュレータが用いられた．

予備評価の結果，選択した禁止ターン集合だけではデッドロックが発生することが確認 されたため⁶，その後，筆者と鯉渕により，シミュレーションの結果を基にして，形成可能 な循環構造の識別とデッドロックフリー実現のために必要な 2つの禁止ターンの追加が行 なわれた．これにより，L-turn/α とほぼ同等の禁止ターンを課す(冗長禁止ターンの除去 は行なわれていない)1つのデッドロックフリールーティングアルゴリズムが導出された．

しかし，改めて予備評価を行なった結果，イレギュラーネットワークにおけるスループッ

5これがL-turnルーティングの原形となった

6図4.24で示されている通り，L-turnルーティングでは，LU方向へ向かうターン以外に更に2つのター ンを禁止する必要がある

第4章 L-turn/R-turn ルーティング

ト向上は予想よりも低い値となった．分析の結果，この原因は，冗長禁止ターンが存在す るためであることが確認された．そこで，更なる性能向上実現のために，筆者により冗長 禁止ターン除去のための循環構造検出アルゴリズムが提案された．これにより，L-turn/α に相当する 1つのデッドロックフリールーティングアルゴリズムが確立し，評価の結果，

高い性能向上が確認された[MAAH01]．

しかし，この時点ではまだ本論文で述べた H/V グラフにおける Turnモデルの適用手 順が確立されておらず，L-turn/β, R-turn/α およびR-turn/β ルーティングの定義がなさ れていなかった．そこで，その後筆者により，H/Vグラフにおけるシステマティックな 2 次元Turnモデルの適用手順が提案され，これにより本論文で提案した 4 つのデッドロッ クフリールーティングアルゴリズムの定義がなされた[AMAH02, 上樂03]．

以上より，主に筆者が担当した作業内容をまとめると次の通りとなる．

• H/Vグラフ構築手順の確立

• 循環構造検出アルゴリズムの確立

• H/Vグラフにおける2次元 Turnモデル適用手順の確立 (4つのルーティングアルゴリズムの導出)

• 評価用フリットレベル相互結合網シミュレータの実装

鯉渕の博士論文[鯉渕02]では，文献[AMAH02]時点の研究成果に関する内容をベース

として L-turnおよび R-turn ルーティングについての記述がなされているが，この中で

筆者が担当した作業内容は上記の通りである．本論文は，文献[AMAH02,上樂03]の内容 をベースとして，主に次の点を改善および補足した内容となっている．

• L-turn および R-turnルーティングの構築手順における 2次元Turnモデル適用手 順の具体化(第4.2節)

• より多くの評価指標を用いた性能評価(第5章)

– 禁止ターン分散の度合いを示す静的な評価指標の分析 – 経路分散の度合いを示す静的な評価指標の分析

• L-turnおよび R-turnルーティングの性能に影響する要素の評価 – ルートスイッチ選択ポリシー(第5.2.4節)

– H/Vグラフ構築時の前順走査における訪問スイッチ選択ポリシー(第4.2.5節，

第5.2.5節)

• L-turnおよび R-turnルーティング をソースルーティング方式(固定型ルーティン

グ)として実装した場合の評価(第5.3 節)

第4章 L-turn/R-turn ルーティング

4.4 まとめ

本章では，Up*/Down*ルーティングにおいて問題となるトラフィックの偏りを改善す るために，より均等なトラフィックの分散の実現を目的とする適応型ルーティングアルゴ リズムである L-turnルーティングおよびR-turnルーティングの提案を行なった．L-turn

および R-turnルーティングは，Up*/Down* ルーティングで利用されているスパニング

ツリーベースの 1次元有向グラフを拡張した H/Vグラフと呼ばれる 2次元有向グラフを 利用する．H/V グラフの導入により，形成可能なターンの数は従来の 6 倍である 12パ ターンに増加し，これによりトラフィックの分散を考慮したより柔軟な禁止ターンの選択 を行なってデッドロックフリーを実現することが可能となる．そして，H/Vグラフに対し て，禁止ターンの分散を考慮した 2次元 Turnモデルをシステマティックな手法で適用す ることにより，L-turnおよびR-turnルーティングが導出される．この際，循環構造検出 アルゴリズムを導入することにより，冗長な禁止ターンを削除し，更なる性能向上の実現 を図っている．L-turnおよびR-turnルーティングは，スパニングツリーの構築と 2次元 Turn モデルの適用をベースとすることにより，Up*/Down* ルーティングと同等の高い 汎用性を実現しており，任意の SANおよびトポロジに適用可能となっている．