Z-routing：イレギュラーネットワークにおける適応型ルーティングに関する研究
10
0
0
全文
(2) Vol. 43. No. 3. Z-routing：イレギュラーネットワークにおける適応型ルーティング. 755. ド ロックの除去を困難なものとしている． 多数の PC や WS によって構成される LAN（ Local. Area Network ） ，WAN（ Wide AreaNetwork ）がイ. 2. レギュラーネットワークの例としてあげられる．また，. 1. 1)∼4) Network of workstations（ NOWs ） など の高速. なネットワークで接続された PC や WS で並列処理を. 3. 行う場合，そのネットワークには高い柔軟性や接続の スケーラビリティの要求からイレギュラーネットワー 5. クが用いられる． 4. 2.1 ネット ワークモデル イレギュラーネットワークのルーティングはプロセッ シングエレ メントとスイッチの接続，スイッチど うし の接続など ，様々な接続ケースを考えなければならな い．しかし，接続ケースに応じてルーティングアルゴ. 図 1 PC クラスタにおける結合網の概略図 Fig. 1 Switch-based interconnection network.. リズムを考えるのは得策ではない．そこで，それらの 差を隠蔽するネットワークモデルへの抽象化の例とし. 2. て NOWs を取り上げ簡単に説明する．. 1. NOWs は一般的に switch-based network であるが， 各スイッチはプロセッシングエレ メントと個々に直結 しているため，パケットを目的地のプロセッサのある. 3. スイッチにルーティングできれば，短時間でデッドロッ クせずに各プロセッサに到着させることができる．よっ. 5. て，ルーティングアルゴリズムはスイッチ間のルーティ. 4. ングに焦点を当て，検討することができる． スイッチ間の内部接続ネットワーク I は有向グラフ. G で以下のように表せる． I = G(N, C).. Fig. 2. 図 2 有向グラフ G Corresponding graph G.. まず初めに，ネットワークを以下の規則に基づきツ. ここで，N はスイッチの集合，C はスイッチ間の双. リー（ スパニングツリー）に見立て，その後ツリーの. 方向リンクを表している．. 階層構造を利用したルーティングを行う．. これにより，図 1 のようなイレギュラーネットワー クは図 2 のように表すことができる． 図 2 のようにネットワークを一般化し，ルーティン グアルゴ リズムを検討していくことにより，ルーティ ングアルゴ リズムはスイッチ間接続にとどまらず，直 接網にも適用することができる．. 2.2 既存のルーティングアルゴリズム イレギュラーネットワークにおけるルーティングア. 1. ネットワークの中から任意にツリーのルートノー ド を選ぶ． 2. ルートノードと隣接するノードをツリーに付け加 える． 3. ツリーの各ノードから隣接する，まだツリーに加 えられていないノードをツリーに付け加えていく． 4. 全ノードがツリーに入るまで 3. の作業を繰り返す． 上記のルールにより，ツリー上のルートノード を除. ルゴ リズムはここ数年来，様々な提案がなされており，. くすべてのノード は親ノード を唯一持つようになる．. up/down routing 1)などはすでに実装されている3) ．. このツリーが作成される際，親ノードと子ノード 以外. 本章ではイレギュラーネットワークにおける代表的. へ接続されているリンクは無視される．たとえば，図 3. な 4 つのルーティングアルゴリズムについて説明する．. における破線のリンクは実際には存在するが，ツリー. 2.2.1 Primitive up/down routing. 上では無視される．. Primitive up/down routing はイレギュラーネット ワークにおける様々なルーティングアルゴ リズムの基. Primitive up/down routing のスパニングツリーに は一般的に幅優先のスパニングツリー（ Breadth-First. 礎となるもので，単純なルーティングアルゴ リズムと. Spanning Tree, BFST ）が用いられている．よって， ツリーの生成の時間計算量は O(n + m)（ n はグラフ. して知られている．.
(3) 756. 情報処理学会論文誌. 図3 Fig. 3. イレギュラーネットワークのツリー表現 Tree expression of irregular network.. の頂点数，m は辺の本数）となり，低く抑えられて いる．. Mar. 2002. 図 4 Prefix routing に用いられる directed-graph Fig. 4 Directed-graph for prefix routing.. ラベルである（ 図 4 ） ．. Prefix routing の スパニング ツリーは Primitive. を使用してそのノード の方向へパケットを転送する．. up/down routing と同様に BFST が用いられている ため，ツリーの生成の時間計算量は O(n + m) であ る．また，ノード とチャネルへのラベル付けはツリー. 目的地ノードが現ノードの子，孫ノードではない場合， up channel を使用して親ノード へパケットを転送. とになるため，時間計算量は O(n + m) である．よっ. する．. て全体の時間計算量も O(n + m) となり，低く抑えら. ルーティングアルゴリズムは単純である．目的地ノー ドが現ノードの子，孫ノードの場合，down channel. つまり，ルーティングは非最短型の固定ルーティン グであり，一部の実在するリンクを利用することがで きない．. の頂点を 1 回ずつ割り振り，辺を 2 回ずつ割り振るこ. れている． ルーティングは，目的地ノード のラベルの “prefix” を持つチャネルがあればそのチャネルを選択し，なけ. たとえば，図 3 においてノード b からノード f にパ. れば，ラベル ‘e’ のチャネル（ up channel ）を選択す. ケットを転送する場合，パケットは b→a→c→f とい. る．これにより，各パケットは Primitive up/down. うルートに沿って転送されることになる． デッドロックを防ぐために，パケットは up channel によってルートノード 方向に必要数移動した後，down. routing の経路をたかだか 1 回ショートカットするこ とが可能である．これは，パケットがショートカット を行うことが可能となる条件が，. channel によってルートノードから遠ざかる方向へ必. 1. 現在地ノードが目的地ノード と子孫関係にない，. 要数移動する．その結果，up channel と down chan-. 2. ショートカット先のノードが目的地ノード または 目的地ノード の先祖ノード となる，. nel の間に環状構造がなくなるため，デッド ロックフ リーが保証される．. 2.2.2 Prefix routing Wu ら 6)によって提案された Prefix routing は Prim-. の 2 つであるため，1 度ショートカットを行うと 1. の 条件が 2 度と成立しなくなるからである． たとえば ，図 4 に おいて ノード b(11) から ノ. itive up/down routing で利用することができなかっ. ード f(121) にパケットを転送する場合，Primitive. たリンクの一部を利用できるようにしたものである．. up/down routing では b(11)→a(1)→c(12)→f(121). Prefix routing ではツリーを作成する際，各ノード. と 3 ホップ 必要だが，Prefix routing では b(11)→. とチャネルにラベルを付け，すべてのチャネルを有向 グラフに組み込み，ルーティングに利用する．ノード. c(12)→f(121) と 2 ホップで到着することができる． Prefix routing はラベルを調べるだけでルーティン. とチャネルへのラベル付けの方法は以下のとおりで. グをできるので，他の up/down based routing に比. ある．. べルーティングテーブルが小さいという特徴を持つ．. ルートノード のラベルを Ln (r) = 1 とし ，ノード. また，Prefix routing は cross channel を使用した場. Ln (v) の k 番目の子ノード u のラベルを Ln (u) = Ln (v) k とする．なお， は連結命令である．ツリー. 送するため，up channel と down channel の間に循. に含まれるチャネルに対しては，ノード v がノード u. 環構造をとることがなく，したがってデッド ロックフ. に比べてルートノードに近い場合，Lc (v, u) = Ln (u)，. リーが保証されている．. Lc (u, v) = e とし ，それ以外のチャネルに対しては， Lc (v, u) = Ln (u)，Lc (u, v) = Ln (v) とする．e は空. 合でも以後 down channel のみを用いてパケットを転. 2.2.3 Minimal routing Primitive up/down routing と Prefix routing は.
(4) Vol. 43. No. 3. Z-routing：イレギュラーネットワークにおける適応型ルーティング. 757. down channel を使用した後，up channel の使用を禁 止することにより cyclic dependency を排除し，デッ ド ロックフリーを実現した．しかし，Silla らは既存の ルーティングアルゴ リズムをエスケープパスに使い， 各リンクに fully adaptive なバーチャルチャネルを追 加する Minimal routing を提案し 3),5) cyclic depen-. dency を除去することなしに，デッド ロックフリーを 実現した．以下にルーティングアルゴ リズムを簡単に 述べる． まず初めに，各リンク間に 2 本のバーチャルチャネ ル（ original channel，new channel ）を用意する．そ. Fig. 5. 図 5 L-R tree の例（ ノード 数 9 ） An example of L-R tree (9 nodes).. して，パケットは原則として new channel を用いて 転送され，最短経路を選択する．しかし，選択可能な. において，ノード e からノード b へのリンクは. new channel がすべて使用されている場合，パケット. left path である． • right path：L-R tree において，現在のノード. は original channel に切り替えられて転送され，Prim-. itive up/down routing，Prefix routing などの既存の. よりも右側に存在するノード へのリンクのこと．. ルーティングアルゴ リズムを用いて経路を選択する．. 図 5 において，ノード e からノード c へのリン. なお，1 度 original channel を使用したパケットは 2. クは right path である．. 度と new channel を使用することはできない．. original channel は，既存のルーティングアルゴ リ ズムを用いているためデッド ロックフリーが保証され ており，ネットワーク全体にわたるエスケープパスに なるため，デッド ロックフリーが保証される．. Minimal routing はパケットが new channel を使用 した場合，最短経路をとるため効率が良く，既存の非 最短型のルーティングアルゴ リズムの性能を大きく向 上させることができる．. 以下に，L-R tree の構成法を述べる． 1. ネットワークの中から任意に L-R tree のルート ノード を選ぶ．. 2. ルートノードに隣接したノードの 1 つを left node， 他を right node として L-R tree に追加する．た とえば図 5 ではルート ノード は a，left node は. b，right node は c である． 3. L-R tree の left node，right node について以下 の作業を行う．. 2.2.4 L-turn routing Left-first turn routing（ L-turn routing ）は慶応義. (a) right node において，まだ L-R tree に組み 込まれていない隣接ノード を right node と. 塾大学によって提案されたルーティングアルゴ リズム. して L-R tree に追加する． (b) left node において，まだ L-R tree に組み込 まれていない隣接ノード のうち，1 つを left. である7) ．L-turn routing はイレギュラーネットワー クを L-R tree☆ というスパニングツリーに見立て，ルー ティングを行う．. L-turn routing を説明するに際し，ここで以下のよ. node，他を right node として L-R tree に追 加する．たとえば図 5 ではノード b の隣接. • left node：L-R tree において，各階層の一番左 側のノード．図 5 においては a，b，d がこれに. ノードのうち，left node は d，right node は e，f である． 4. 3. の手順を全ノードが L-R tree に組み込まれる. あたる． • right node：L-R tree において，left node 以外. まで繰り返す． 5. L-R tree に漏れているイレギュラーネットワーク. うに語を定義する．. のノードのこと．図 5 においては c，e，f，g，h，. i がこれにあたる． • left path：L-R tree において，現在のノード よ. ☆. のリンクを追加する． 図 5 における破線のリンクは，L-R tree の構成法 の手順 5. で追加したリンクである．. りも左側に存在するノードへのリンクのこと．図 5. L-R tree の生成において，left node，right node の 割振りは頂点をちょうど 1 度ずつ定義していくため，. 実際はツリー構造ではなくグラフ構造であるためこの名称は適 切ではないが，本論文では参考文献において定義されている単 語をそのまま使用する．. 時間計算量は O(n + m) である．しかし，left path，. right path の割振りにはアルゴ リズムが存在せず，最.
(5) 758. Mar. 2002. 情報処理学会論文誌. 適なパフォーマンスを得るため手作業で行われている. な状態を求めているため，L-R tree の生成にかかる全. ため，現時点での全体の時間計算量は O(n + m) よ. 体の時間計算量は O(n + m) より大きくなる．. り大きくなっている．. L-turn routing のルーティングは， “right path を使用した後，left path を使用しては. 3. Z-routing 既存の up/down based routing algorithm におい. ” ならない．. てあげられるルートノード 付近へのトラフィックの偏. という条件を守ればいかなる経路も選択可能である．. り，および最短経路のとりにくさなどによって生じる. よって，出発地ノードと目的地ノード の間には複数の. パフォーマンスの低下は，イレギュラーネットワークに. 経路が存在することになるため，L-turn routing は. おいてデッド ロックフリーを保証するためにルーティ. 適応型ルーティングである．また，L-turn routing は. ングアルゴ リズムの自由度を低下させたことが原因で. Turn モデル 8)を用いることにより，上記の条件から デッド ロックフリーが保証されている．. ある．. 図 5 においてノード d からノード i にパケットを 転送する場合，Primitive up/down routing や Prefix routing では d→b→a→c→g→i と 5 ホップ必要だが，. そこで我々は性能の向上を図るために，より多くの 最短路と高い自由度を提供する新しいルーティングア ルゴ リズムである Z-routing を提案する． 以降，まず イレギュラーネットワークを red/blue. L-turn routing では d→h→g→i と 3 ホップでパケッ. graph に見立てる手順を説明し，その後 Z-routing の. トを転送することができる．さらに L-turn routing で. ルーティングアルゴ リズムを提案する．. は d→b→a→c→g→i の経路も選択可能である． ルゴ リズムであるが，自由度が高いため全体のチャネ. 3.1 red/blue graph の作成法 Primitive up/down routing や Prefix routing で使 用されているツリーでは，ルートノードに向かうチャ. ル利用率が向上し，トラフィックが分散される．また，. ネルを up channel，ルート ノード から遠ざかるチャ. パケットの平均ホップ数を抑えることができる．. ネルを down channel と分類した．そして，Primitive. 2.2.5 既存のルーティングアルゴリズムの問題点 Primitive up/down routing や Prefix routing では スパニングツリーの生成の時間計算量は O(n + m) と. up/down routing と Prefix routing は up/down とい う階層構造を下にデッド ロックフリーを実現した． しかし，我々はより自由度の高いルーティングを実. 低く抑えられてはいるが，up channel と down chan-. 現するために up/down の概念を捨て，red/blue とい. L-turn routing は非最短型の適応型ルーティングア. nel の間に厳しい制限を設けデッド ロックフリーを実. う概念を導入した red/blue graph を提案する．以. 現したためすべてのリンクを効果的に使うことが難し. 下に，red/blue graph の構成方法を述べる．. く，ルートノード にトラフィックが偏る，チャネルが. 1. ネットワークの中から任意にノードを選択し，その. 空いていても最短経路をとりにくい，などの問題点が. ノードをルートノードとする深さ優先のスパニン. 存在する．. グツリー（ Depth-First Spanning Tree，DFST ）. Minimal routing は new channel より original channel の方が使用される割合が大きい傾向にあり， 結局 original channel で用いられるルーティングアル. の構築を行う．なお，同時に関節点9),10)を求めて おく． 2. 1. で構築した DFST に含まれる辺（木の辺，tree. ゴ リズムの性能がパフォーマンスを左右することに. edge ）を blue edge と定義する．また，ネット. なる．また，スパニングツリーの生成の時間計算量も. ワークにおけるそれ以外の辺（逆辺，back edge ）. original channel で用いられるルーティングアルゴ リ. を red edge と定義して DFST に組み込む．この. ズムに依存する．. 時点でネットワークに含まれるすべての辺が blue. L-turn routing は L-R tree の作成方法が曖昧であ る．たとえば，図 5 においてノード h はノード g に対 して位置的に左にも右にもなりうるため，パス h→g は left path にも right path にもなりうる．その結果， 場合によっては使えない経路が存在することになり，. edge か red edge のど ちらかに割り当てられたこ とになる．. 3. 幅優先探索の応用で辺に番号付けをする．以下， blue edge と red edge の番号付けを，各々 nb ，nr という表現法で定義する．. そのことがパフォーマンスに影響を与える．また，left. (i) ルートノードに接続している blue edge の辺. node，right node の割振りの時間計算量は O(n + m) だが，left path，right path の割振りは手作業で最適. 番号を 1（ nb = 1 ）とする．ここで，nb と. nr との関係を，nr = nb + 1 と定義する．.
(6) Vol. 43. No. 3. Z-routing：イレギュラーネットワークにおける適応型ルーティング. 759. リーは保証される．しかし，red edge を取り除くこと a. blue edge. 1 b 3 d. 2 4. 3. c. では辺に番号付けをし red edge も使用することによっ て自由度の高いルーティングを実現している．. 3. 4. 3.2 Z-routing algorithm e. 5 5. Fig. 6. red edge. は自由度の低下を招いてしまうため，red/blue graph. f 8 7 h. g 8 9. i. 図 6 red/blue graph（ 9 ノード ）の例 An example of red/blue graph (9 nodes).. 本節では前節で述べた red/blue graph を利用する “Z-routing” と呼ばれる新しいルーティングアルゴ リ ズムの提案を行う． 前章で述べたように，up/down based routing algorithm はツリーの階層間の移動に up/down などの 厳しい制約があり，それが自由度を低下させる原因と. この定義により，ルートノードに接続されて. なっている．そこで Z-routing はグラフの階層間の移. いる red edge の辺番号は 2 となる．これら. 動の制限を緩くすることで性能向上を図る．. の辺番号の組みを，クラス E(nb , nr )（ここ では E(1, 2) となる）と定義する．さらに，. Z-routing は以下のように定義される． ( 1 ) 2 本のバーチャルチャネル Ci（ increment ） ，Cd. E(nb , nr ) に接続しているノード のクラスを N (nb , nr ) と定義する．たとえば，N (1, 2) に. (2). （ decrement ）を使用する． 出発地ノード S から目的地ノード D へのパス. 含まれるノード は図 6 よりノード b とノー. を検出する際，前節で定義した辺番号（ nb , nr ）. ド c となる． (ii) N (nb , nr ) に属するノードにつながっている. を使用する．S → D 間の辺番号を並べたとき， 以下の番号の並びのみを許すものとする．. blue edge と red edge を各々 nr + 1，nr + 2 と番号付けすることにより，残りの blue edge. (a). と red edge に帰納的に番号付けしていく．た. (b). 降順：図 6 において h→f→b→a という. c につながっているまだ番号付けされていな. (c). 経路の場合，辺番号の並びは 7，4，1． 1 回のみの切替え：バーチャルチャネル. い blue edge と red edge は，各々3，4 と番. Cd から Ci への 1 回のみの切替えを許す． ( 2 ) により S → D 間の最短パスが検出された. 経路の場合，辺番号の並びは 1，4，7．. とえば ，図 6 において，ノード b とノード. 号付けされ，E(3, 4) と定義される．. (iii) (ii) で E(pb , pr )，E(qb , qr ) (p = q) のよう にすでに定義された複数の辺のクラスが，あ. 昇順：図 6 において a→b→f→h という. (3). 後，以下のようにしてパケットを転送する．も し辺番号の並びが昇順だった場合はバーチャル. るノードに接続されている場合，そのノード. チャネル Ci を使用し ，降順だった場合は Cd. に接続されているまだ番号付けされていない. を使用する．もし “1 回のみの切替え ” が可能. 辺には次のように番号付けする．まず，番号. なら，バーチャルチャネルを Cd から Ci へ切. pr と 番号 qr を比較する．その結果，大き い方の番号のクラスを N として選択する．. り替える． 上記の条件を守れば，Z-routing はいかなる経路も選. たとえば ，図 6 におけるノード f がすでに. 択可能であり，自由度の高い非最短型ルーティングを. E(3, 4) と E(5, 6) に接続されているとき， ノード f→h 間の blue edge の辺番号は 7 と. 作成の時間計算量が O(n + m)（ n はグラフの頂点数，. なり，ノード f→i 間の red edge は 8 となる． (iv) (ii)，(iii) をすべてのノード がクラスに定義. の応用でできるため時間計算量が O(n + m)，よって，. されるまで繰り返す． 図 6 は上記の方法により構成された 9 ノード の red/blue graph の例である． 辺を blue edge と red edge に分類することにより， グラフ内の環状構造をすべて検出することができる．. red edge はグラフ内の環状構造の一辺を担う辺であ り，もし，この red edge を取り除けばデッドロックフ. 実現する．また，red/blue graph の作成は，DFST の. m は辺の本数） ，辺の番号付けは幅優先探索（ BFS ） red/blue graph の製作の時間計算量は O(n + m) に 抑えられる．よって，グラフの構築，および再構築に かかる時間を低く抑えることが可能である． 定理 1 Z-routing はデッド ロックフリーである． 証明：red/blue graph は DFST を基に作られてい る．DFST は閉路を含まない木であり，ネットワークを. DFST に含まれる辺（ 木の辺，tree edge，red/blue.
(7) 760. Mar. 2002. 情報処理学会論文誌 root node. graph における blue edge ）とそれ以外の辺（ 逆辺， 9),10) back edge，red/blue graph における red edge ）. : articulation point : node. に分けることによりネットワーク内に存在する全閉. : biconnected component. 路を検出することができる．そして，ネットワークの 同じ 深さにおける blue edge と red edge に異なる番. v3. 号付けをし，ネットワークの深さに応じて番号を増加 させることにより，閉路をなす辺に異なる番号付けを. v2. することができる．したがって，辺の番号の並びの昇. v4. 順，および降順に応じてバーチャルチャネルを使い分. v1. けることにより循環構造を断ち切ることができるため，. Z-routing はデッド ロックフリーであることが証明さ れる． Z-routing における全ノード への経路は • 辺に付けられた番号を降順にたど ることにより， どのノードからもルートノードにたどり着くこと. Fig. 7. 図 7 関節点と 2 連結成分 Articulation point and biconnected component.. ないため，図 6 においてノード b からノード i へパケッ トを転送するような場合，Prefix routing や Primitive. up/down routing では b→a→c→g→i と 4 ホップ必. ができる， • ルートノードから辺に付けられた番号を昇順にた. 要だが，Z-routing では b→f→i と 2 ホップのみで到. どることにより，どのノード へもたどり着くこと. Z-routing は自由度が高いため全体のチャネル利用 率が向上し，トラフィックが分散される．また，パケッ トの平均ホップ数を抑えることもできる．. ができる， • バーチャルチャネル Cd から Ci への 1 回のみの 切替えを許すものとする， ことにより，保証される．. Z-routing において全ノード への経路を保証するた めに，以下のようにルーティングテーブルを作成する． 図 7 はネットワークを 2 連結成分9),10) の視点で表し たものである．. • 出発地ノードと目的地ノードが同一の極大な 2 連. 着させることができる．. 4. 評. 価. 今回提案した Z-routing，そして既存の Primitive. up/down routing，Prefix routing，L-turn routing （ Z-routing 以外はそれぞれ Minimal routing を併用） の各ルーティングアルゴ リズムを C++で記述したフ リットレベルシミュレータを用いて評価を行った．. 結成分内に存在する場合は，出発地ノードから目. 今回のシミュレーションにおいて，ネットワークサ. 的地ノード への最短路を直接求める（例：図 7 に. イズ，バーチャルチャネルの本数，そしてパケット長. ． おいて v1 から v2 へパケットを転送する場合） • 出発地ノードと目的地ノードが異なる極大な 2 連 結成分に存在し，通過する間接点が 1 つのみの場. はパラメータを変化させることによって選択した．各 ノードはプロセッサ，リクエストキュー，そして双方 向チャネルを提供するルータからなり，近隣ノードに. 合は，出発地ノードから間接点までの最短路と間. 接続した．ルータはチャネルバッファ，クロスバ，リ. 接点から目的地ノード までの最短路を求め，バー. ンクコントローラ，バーチャルチャネルコントローラ，. チャルチャネル Cd から Ci への切替えが 1 回以. そしてコントロールサーキットからなる単純なルータ. 内になるようにそれらを組み合わせる（ 例：図 7. モデルを使用した．. において v1 から v3 へパケットを転送する場合） ．. • 出発地ノードと目的地ノードが異なる極大な 2 連 結成分に存在し ，通過する間接点が 2 つ以上の 場合は，出発地ノードから間接点までの最短路と 間接点から間接点までの最短路，そして間接点か ら目的地ノード までの最短路を求め，バーチャル チャネル Cd から Ci への切替えが 1 回以内にな. 4.1 シミュレーション条件 今回の評価では，パケットの目的地を決定する際 に，すべての目的地ノード がランダ ムに選択される. uniform トラフィックを採用した． また，以下の 2 つの指標により評価を行った． 4.1.1 ネット ワークレ イテンシ： あるノード p がパケットの最初のフリットを入力. るようにそれらを組み合わせる（例：図 7 におい. バッファに挿入した時刻を t0 ，目的地ノードである q. て v1 から v4 へパケットを転送する場合） ．. がパケットの最後のフリットを受け取った時刻を t1. Z-routing は up channel，down channel の概念が. とする．ここで Tlat (p, q) = t1 − t0 をネットワーク.
(8) Vol. 43. No. 3. Z-routing：イレギュラーネットワークにおける適応型ルーティング. 表1 Table 1. シミュレーション条件 Simulation parameters.. a. blue edge. 1. 50,000 clks Irregular or 2D torus 9 or 16 nodes 128 flits（固定） 2 Wormhole uniform. 実行時間 ネットワーク ネットワークサイズ パケット長 バーチャルチャネル数 ルーティング方法 トラフィックパターン. b 3. 2 4. 3. 4. d. e. 図9 Fig. 9. a. d. red edge. c. 3. 5. f 8 7. 5. b. 761. h. g 8 9. i. 9 ノード red/blue graph 9 nodes red/blue graph.. c. e. f. g. h. i. 図 8 9 ノード イレギュラーネットワーク Fig. 8 9 nodes irregular network.. レイテンシと呼び，ネットワークの性能を測る指標と する．. 4.1.2 スループット ： ここでは，ネットワークのスループットを各ノード のルータがパケット中のフリットを次のノード のルー タ，もしくは各ノード のプロセッサに転送する確率と. 図 10 Fig. 10. 定義する．すなわち，各ルータが毎クロック，フリッ. 16 ノード red/blue graph 16 nodes red/blue graph.. トを転送するならば，スループットは 1.00 である． シミュレーションに用いた条件を，表 1 に示す．. 1000. シミュレーションで初めの 5,000 クロックはネット. 900. ワークが安定せず，想定した負荷に達していないと考. 800. 1 プロセッシングエレ メントと仮定した．ネットワー クのトポロジについては，イレギュラーネットワーク. 700 Latency[clk]. えられるため無視して評価を行った．1 ノードにつき. 600 500 400. での性能評価としてランダ ムに 9 ノード を接続した. 300. もの（ 図 8 ）と 4×4 2D torus を用いた．Z-routing. 200. はバーチャルチャネルを 2 本必要とするので，シミュ. 100. レーション条件におけるバーチャルチャネル数を 2 本 （ Z-routing 以外は Minimal routing を併用）として 評価を行った．. up/down 9-node prefix 9-node L-turn 9-node 9-node Z. 0 0. 0.1. 0.2 0.3 Throughput[flit/clk/node]. 0.4. 0.5. 図 11 9 ノード イレギュラーネットワーク Fig. 11 9 nodes irregular network.. 図 9，図 10 は 9 ノード，および 16 ノードにおける. Z-routing の red/blue graph である． 4.2 9 ノード イレギュラーネット ワーク 9 ノード イレギュラーネットワークにおける評価を，. し た既存のルーティングアルゴ リズムに比べ，高い. 図 11 に示す．これらの評価はリンク間の双方向チャ. 性能を示していることが分かる．ルーティングの際，. イテンシを表している． 図 11 より，Z-routing は Minimal routing を併用. ネルが 2 本で，Z-routing 以外の各ルーティングアル. Minimai routing を併用している既存のルーティング. ゴ リズムに Minimal routing を併用したときのもので. アルゴリズムは，Primitive up/down routing，Prefix. ある．なお，グラフの x 軸はスループット，y 軸はレ. routing，L-turn routing を original channel で使用.
(9) 762. Mar. 2002. 情報処理学会論文誌. 1000 up/down 16-node prefix 16-node L-turn 16-node Z 16-node. 900 800. Table 2. Latency[clk]. 700. 表 2 平均ホップ数 Average hops of packets.. up/down + minimal routing prefix + minimal routing L-turn + minimal routing Z-routing. 600 500 400 300 200 100 0 0. 0.1. 0.2 0.3 Throughput[flit/clk/node]. 0.4. 0.5. 図 12 16 ノード 2 次元トーラス Fig. 12 16 nodes 2D torus.. up/down + minimal routing prefix + minimal routing L-turn + minimal routing Z-routing. 9 nodes 1.94 1.85 1.83 1.73 16 nodes 2.28 2.18 2.15 2.14. Z-routing に必要な “red/blue graph” を提案し ，評 価を行った．. し，Minimal routing を new channel で使用する．new. red/blue graph の作成の時間計算量は O(n+m) と. channel を使用することによってパケットは最短経路. なり，既存のルーティングアルゴ リズムの中でスパニ. を選択することになり，自由度が増す．一方，original. ングツリーの生成の時間計算量が最も低い up/down. channel はエスケープパスとなっているため，デッド. based routing と同じ時間計算量でグラフを生成する. ロックフリーを保証する．図 11 における，Primitive. ことが可能となった．. up/down routing，Prefix routing，L-turn routing. Z-routing は辺番号を使用する際，3 つのルールの. の性能の差は，original channel での性能の差によっ. みが存在する単純なデッド ロックフリーなルーティ. て引き起こされたものである．しかし，Z-routing は. ングアルゴ リズムである．シミュレ ーション結果か. チャネルに original，new の違いがなく，2 本を Ci ，. ら ，Z-routing は既存のルーティングアルゴ リズム. Cd という自由度の高いエスケープパスとして使用す るため，最も高い性能を示したと考えられる． 4.3 16 ノード 2 次元ト ーラス. （ Primitive up/down routing，Prefix routing，L-. 4×4 2 次元トーラスでの評価を図 12 に示す．ネット ワークサイズとトポロジを除くシミュレーション条件. 法の提案，Z-routing の出力チャネルの選択法（ output. は，9 ノード イレギュラーネットワークと同様である． 図 12 から分かるように ，Z-routing は Minimal. routing を併用した既存のルーティングアルゴ リズム に比べ，高い性能を示した．今回，16 ノード の評価は イレギュラーネットワークではなく，2 次元トーラス というレギュラーネットワークにおいて行った．しか し，図 12 より，Z-routing は高い性能を示し，レギュ ラーネットワークにおいても他のルーティングアルゴ リズムに比べ高い性能を示すことが分かった． 最後に平均ホップ 数の結果を表 2 に示す．表 2 に 示すとおり，Z-routing は既存のルーティングアルゴ リズムと比べ，最も平均ホップ数が少ないという結果 を得た．これは，Z-routing が既存のルーティングア ルゴ リズムに比べて自由度が高く，そのため選択可能 な最短経路数がより多いためであると考えられる．. 5. ま と め “Z-routing” と呼ばれるイレギュラーネットワーク における新し いルーティングアルゴ リズム，および. turn routing ）に比べ，高い性能を示すことが分かった． 今後は，より自由度が高まるような辺の番号付けの方 selection function ），Z-routing での最短路をより多 く確保するアルゴ リズムの考案，およびより多いノー ド 数での評価を行う予定である． 謝辞 本研究の一部は，科学研究費補助金奨励研究 （ A ）課題番号 13780226 の支援により行った．. 参 考 文 献 1) Schroeder, et al.: Autonet: A high-speed, selfconfiguring local area network using point-topoint links, Technical Report SRC research report 59, DEC (1990). 2) Horst, R.W.: Tnet: A reliable system area network, IEEE Micro (1995). 3) Silla, F. and Duato, J.: Efficient Adaptive Routing in Networks of Workstations with Irregular Topology, Proc. CANPC’97 (1997). 4) 西 宏章，多昌鷹治，工藤知宏，天野英晴：仮 想チャネルキャッシュを持つネットワークルータ の構成と性能，JSPP’99 論文集 (1999). 5) Silla, F. and Duato, J.: Is it worth the flexibility provided by irregular topologies in networks of workstations?, Proc. CANPC’99 (1999)..
(10) Vol. 43. No. 3. Z-routing：イレギュラーネットワークにおける適応型ルーティング. 6) Wu, J. and Sheng, L.: Deadlock-Free Routing in Irregular Networks Using Prefix Routing, DIMACS Technical Report 99-19 (1999). 7) 鯉 渕 道 紘 ，舟 橋 啓 ，上 樂 明 也 ，天 野 英 晴： Irregular Network における Adaptive Routing の提案，SWoPP2000 予稿集，pp.33–40 (2000). 8) Glass, C.J. and Ni, L.M.: Maximally Fully Adaptive Routing in 2D Meshes, ISCA92, pp.278–287 (1992). 9) Even, S.: Graph Algorithms, Computer Science Press (1979). 10) Tarjan, R.E.: Data Structures and Network Algorithms, SIAM (1983).. 763. 井川 郁哉 昭和 52 年生．平成 13 年三重大学 工学部情報工学科卒業．現在，神戸 大学大学院自然科学研究科情報知能 工学専攻修士課程 1 年．並列計算機 における相互結合網，ルーティング アルゴ リズムに関する研究に従事． 舟橋. 啓（ 正会員）. 昭和 46 年生．平成 7 年慶應義塾 大学理工学部電気工学科卒業．平成. 12 年同大学大学院理工学研究科計 (平成 13 年 3 月 27 日受付) (平成 13 年 12 月 18 日採録). 算機科学専攻後期博士課程修了．工 学博士．現在，三重大学工学部助手． 並列計算機における相互結合網，ルーティングアルゴ リズムに関する研究に従事．IEEE，IEEE-CS 各会員．.
(11)
図
+2
関連したドキュメント
・取締役は、ルネサス エレクトロニクスグルー プにおけるコンプライアンス違反またはそのお
こうした背景を元に，本論文ではモータ駆動系のパラメータ同定に関する基礎的及び応用的研究を
このように資本主義経済における競争の作用を二つに分けたうえで， 『資本
Corollary 1 If G is a directed tree, in which the orientation is either towards the root or away from the root, and if there is a directed path from each source to each
For graphs of tree-length bounded by δ , we obtain a routing scheme of deviation 6 δ −2 with addresses and local memories of size O ( δ log 2 n ) bits per node, moreover
13 proposed a hybrid multiobjective evolutionary algorithm HMOEA that incorporates various heuristics for local exploitation in the evolutionary search and the concept of
VRP is an NP-hard problem [7]; heuristics and evolu- tionary algorithms are used to solve VRP. In this paper, mutation ant colony algorithm is used to solve MRVRP with
次に我々の結果を述べるために Kronheimer の ALE gravitational instanton の構成 [Kronheimer] を復習する。なお，これ以降の section では dual space に induce され
