森/2010/Routing Algorithms
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[森/2010]]
*Network on Chip Routing Algorithms :TUCS Technical Report [#e0bc5958]
-読んでまとめたが、レベル分けが若干おかしい。
***Oblivious Routing Algorithms [#c5215670]
--pseudo adaptive XY routing
---このルーティングは、静的もしくはネットワークの状態によっては動的に動作する。ネットワークが全くまたは、少ししか混雑していない時に静的に動作する。ネットワークがブロックされると、このアルゴリズムはadaptiveモードに切り替わり混雑していないルートを探し始める。
---pseudo adaptive XY routingは、メッシュネットワークで使われる。どのルータにもテンポラリの記憶容量があり、通信が混雑しているかどうかを判定する識別子が保存される。混雑しているときは、データを受け取らないようにしている。
---このルータは、同時に入ってきたパケットに対して優先付けを行っている。優先順としては、北、南、東、最後が西となっている。
---従来のXYroutingでは、ネットワークロード時間を外側のルータより、内側のルータのほうが多くなっていたが、このルーティングでは、ネット―ワーク全体に平等に分けられている。
--Surrounding XY Routing
---Surrounding XY Routingは、3つの異なるルーティングのモードがある。N-XY(Normal XY)モードは、基本的なXYルーティングとして動く。これは、パケットをX方向、つぎにY方向にルーティングを行う。ネットワークがブロックされるか、停止しているルータに行きあうまで、このモードを持続する。SH-XY(Surround horizontal XY)モードは、左か右隣のルータの動作が停止したときに使われる。3つめのモードは、SV-XY(Surround vertical XY)モードで、上か下のルータが停止しているときに使われる。
---SH-XYモードは、パケットを目的先の座標の正しい列の場所にルーティングを行う。このアルゴリズムはパケットを最も短いパスのなで停止しているルータを迂回する。この状況では、パケットは既に正しい列にあるので、SV-XYモードとは少々異なる部分がある。パケットは左か右にルーティングすることができる。SH-XYとSV-XYモードの動作モードは、図10.ルータは、パケットがどちらのモードを使ってルーティングされたのかを知るために各モード内で識別子をつけている。
***Turn Models [#c4e07e18]
---ターンモデルアルゴリズムは、ライブロックフリー。
--West-first Routing
---West-firstルーティングでは、全ての西へのターンを防ぐ。西に行くパケットは必要な分だけ最初に西に進む。後で西に進むことはできない。
--North-last Routing
---このルーティングでは、北から目をそむけることはできない。パケットは、北へのルーティングを最後に行わなければならない。
--Negative-first Routing
---このアルゴリズムは、正方向から負方向へのターンを除いてすべてのターンを許可する。パケットは、何をするよりまず、負方向へルーティングを行わなければならない。
***Deterministic Routing Algorithms [#vb29bdba]
--静的ルーティングはパケットを毎回決められたパスにルーティングを行う。このアルゴリズムは、レギュラーとアンレギュラーなネットワーク両方で使われる。混雑の無いネットワークでは、信頼性が高く、少ない遅延が得られる。また、これはパケットはいつも正しい順番で各目的先に着くのでリアルタイムシステムに向いている。簡単なものでは、各ルータが他のルータへのルーティングの情報を持っているルーティングテーブルがある。ネットワークの構造が変更されると、各ルータもアップデートする必要がある。
--Shortest Path Routing
---最短経路ルーティングは、最も簡単な静的ルーティングのアルゴリズムである。パケットは、常に可能な限り最短経路にルーティングされる。distance vector routingとlink state routing が最短経路アルゴリズムである。
>
--[[Distance Vector Routing>Wikipedia:Distance-vector_routing_protocol]]
---それぞれのルータが、隣あうルータと受け入れ先の情報を持ったルーティングテーブルを持っている。ルータは、他のルータとルーティングテーブルの情報を交換し、最新の状態に保つようにしている。ルータはパケットをルーティングテーブルより最短経路を導き、パケットを転送している。このルーティングはネットワーク全体の構造を各ルータが知らなくてもよいので、簡単な方法となっている。
<
>
--Link State Routing
---このルーティングは、distance Vector Routingを改良したものである。基本的なアイディアは、distance Vector Routingと同じであるが、このルーティングでは、各ルータがルーティングテーブルを共有している。NoCでのLink State Routingは既存のものに少しNoC用のカスタマイズが加えられている。生成ステージ(NoCを作るとき?)にて、ネットワーク全体をカバーしているルーティングテーブルは、ルータのメモリに保存されている。ルータは、ネットワーク構成が変更されたり、ミスが起こったりするときに、ルーティングテーブルをアップデートする。
<
--Source Routing
---このルーティングでは、送り側がパケットの全てのパスを決定する。全てのルーティング情報は転送前にパケットのヘッダに保存され、送り側が決めたルート通りに転送を行う。
---vector routingは基本的にソースルーティングライクである。vector routingでルーティングされるパスは鎖型に表される。どのunitも2つのルータ間を1ホップで表す。ルーティングされるパスは、必ずしも最短経路にする必要はない。
---Arbitration look ahead scheme(ALOAS)はソースルーティングよりも早いルーティングである。ルーティングの経路の情報は、パケットが転送される前にルータに与えられる。ルートの情報は特別なチャンネルを使って転送される。
---contention-free routingは基本的に、ルーティングテーブルと[[TDM(time division multiplexing)>wikipedia:時分割多重化]]のアルゴリズムで出来ている。どのルータも正しいアウトプットと時間割り当てを、受信、送信のペアで持っているルーティングテーブルがある。このアルゴリズムはPhilips AEthereal NoCやclockworkルーティングで使われる。
--Destination-tag Routing
---目的先タグルーティングは、ソースルーティングの逆バージョンに似ている。送り側は、目的先タグとして受信側のアドレスをルーティングの初めにパケットのヘッダーに保存する。どのルータも受信側のアドレスによって、個別にルーティングを行う。
--Topology Adaptive Routing
---静的ルーティングで`アルゴリズムは、いくつかのadaptiveな特徴を加えることで改善することができる。トポロジー適応ルーティングは少しだけ動的な要素を持つ。このアルゴリズムは、基礎的な静的ルーティングのように動作するが、動的なネットワークに適応するような特徴がある。もしルーティングテーブルの更新が必要なら、システムの管理者が行うことができる。このアルゴリズムに一致するのは、知っているように、online oblivious routingである。topology adaptive routingのコストと遅延は、静的なルーティングなアルゴリズムのものと近い。トポロジーの動的性で便宜的なのは、イレギュラーで動的なネットワークに適している。
--Stochastic Routing Algorithms
---このアルゴリズムでのルーティングは、パケットが目的先にすぐ、若しくは遅く到着するのを予測し、一致することを基礎としている。確率論的アルゴリズムは、単純でミスに寛容である典型的なモデルである。データのスループットは高いが、欠点として、遅くたくさんのネットワークリソースを使う。
---確率論的ルーティングアルゴリズムは、パケットの[[TTL(time to live)>http://e-words.jp/w/TTL-2.html]]をけっていする。これは、ネットワークの中をパケットがどれくらいの間移動を可能にするかということ。この時間が来ると、パケットはネットワーク上から削除される。
--3.4.1 Flooding Algorithms
---最も有名な確率論的ルーティングとして、floodingアルゴリズムがある。これから3つの異なるfloodingのアルゴリズムを紹介する。
>
--Probabilistic Flood
---このProbabilistic Floodが一番簡単なモデルである。ルータは、パケットの目的先を知ることなく、ルータに入ってきたパケットをコピーし、送れるルータ全てに送る。パケットのコピーは、ネットワーク全体に広がる。最後に少なくとも1つのコピーが受信側に到着し、重複したコピーは削除される。
<
>
--Directed Flood
---directed floodルーティングアルゴリズムは、probabilistic floodアルゴリズムを改良したものである。これは、目的先の近くの方向へパケットを送る。このルーティングは、probabilistic floodよりミスに寛容で、ネット―ワークのリソースも少なくて済む。
<
>
--Random Walk
---ランダムウォークアルゴリズムは、ネットワークに送るパケットのコピー量を予想する。ルーティングパスにある全てのルータは、入力されたパケットをいくつかのアウトプットを通って送信される。パケットはdirected flood同様の方法で送られる。ランダムウォークは、directed floodと同じくらいミスに寛容であるが、エネルギーとバス幅は少なくて済む。
<
>
--Valiant's Random Algorithms
---優れたランダムアルゴリズムは、部分的に確率論的なアルゴリズムである。oblivious routingの1つの大きな問題として、ネットワークでのイレギュラーなロードに対する影響である。ロードはネットワークの中心で特に高くなる。優れた(valiant)ランダムアルゴリズムは、様々な種類のあるネットワーク上のトラフィックロードを均一にする。このアルゴリズムはまず、無作為にネットワークの中心にあるノードを抽出し、そこにパケットを転送する。それからパケットは、単にそこにルーティングされる。これらの手法は、いくつかのobilivious routingで使われている。
<
***Adaptive Routing Algorithms [#u7519efe]
-4.1 Minimal Adaptive Routing
--動的最短ルーティングアルゴリズムは常に最も短い経路を使う。このアルゴリズムは、1つ以上の最短、若しくは可能な限り短いルーティングがあるときに有効的である。このアルゴリズムは、混雑の少ないルートで使われる。
-4.2 Fully Adaptive Routing
--完全動的アルゴリズムは混雑が起こっていないルートのときは、いつも使われる。このアルゴリズムは、最短経路を全く気にしない。典型的に、このルーティングは、ルートに優先付けを行うことで、ルータが一方的に使われて混雑することがない。
>
-4.2.1 Congestion Look Ahead
--混雑先見アルゴリズムは他のルータからブロックの情報を受け取る。この情報を受け取ることで、混雑を回避することができる。
<
-4.3 Turnaround Routing
--転換ルーティングは、バタフライやファットツリーネットワークのルーティングである。送り側と受信側のパケットは、全てネットワークの同じ側にある。まずパケットは、送り側から無作為に反対側への中間ノードに送られる。このノードでは、パケットは転換され、それから同じ側のネットワークにある目的先に送られる。そこですべてのルーティングが始められる。ルーティングは中間ノードから受信先を決めるためにdestination-tagルーティングが行われる。
--転換ルーティングアルゴリズム上のルータは、前向きと後ろ向きにどちらの方向にもデータを流すことができる。このアルゴリズムは、前向きから後ろ向きに1度のみ転換を行うので、デットロック無しに動作できる。
--SPIN(Scalable Programmable Interconnect Network)は、転換ルーティングを用いたファットツリー型のものである。ミスに寛大なXGFT(eXtended Generalized Fat Tree)でTurnaround Routingはターンバックルーティングと呼ばれている。このXGFTシステムのネットワークトポロジーもまたfat-treeである。今までのturnaround routnigはランダムに中間のノードを選んでいたが、このXGFT's turnback routnigは、すこし基本的な転換ルーティングとは異なり、自分で選べるようになっている。これは、ネットワークが混雑しているときに役に立つ。
>
-Turn-Back-When-Possible
--TBWPは、ツリーネットワークのアルゴリズムである。これは、転換ルーティングを改良したバージョンである。turn-backチャンネルがビジーだと、このアルゴリズムは高いレベルのスイッチの中でフリーなルートを探す。このチャンネルは、前と後ろ方向のどちらでも考えられる。これは、ネットワークで、ルーティングの進行方向を変えるために使われる。
<
-4.4 Other Adaptive Routing Algorithms
>
-IVAL(Improved VALiant's randomized routing)
--IVALは oblivious Valiant's アルゴリズムを改良したバージョンである。これは、turn around ルーティングに少し似ている。このアルゴリズム上の最初のステージでは、パケットは、oblivious dimension orderルーティングを送り側から受信側までの中からランダムに選択します。次のステージでは、アルゴリズムは平等に動作します、しかし、このときにこのネットワークはオーダーを入れ替えます。IVALでデッドロックを回避するためには、ルータのチャンネルをバーチャルチャンネルにする必要があり、完全にデッドロックフリーなものにするためには、4つのバーチャルチャンネルが必要となる。
<
>
-2TURN
--このアルゴリズムは、アルゴリズム的な記述が存在しない。このアルゴリズムは、密閉形式でのみルーティングパスが決められる。送信側から受信側までこのアルゴリズムでは、常にUターンと方向を変えることの2つをしない物で構成されている。IVALルーティングだけで2turnルータは、もし全てのルータがバーチャルチャンネルを持っていればデッドロックを回避できる。
--ローカリティはルーティングアルゴリズムの基準で、パケットが平均的に転送される距離で決まる。この基準は、パケットの低いロードの端から端までの遅延によってきまる。IVALと2TURNアルゴリズムはValiantルーティングのおおよそ20%〜25%以上改善されている。2TURNのローカリティは最適なものにかなり近いものとなっている。
<
>
-Q-routing
--Q-routingの機能は、ネットワーク通信の統計がベースとなっている。このアルゴリズムは、遅延と混雑の情報を集め、ネットワーク通信の統計を維持している。このアルゴリズムは、統計を元にルーティングを決定する。
<
>
-Odd-Even Routing
--奇数偶数ルーティングは、adaptiveアルゴリズムで、DyAD(dynamically adaptive and deterministic)NoCシステムで使われる。このルーティングは、デッドロックフリーで、偶数の列にあるとき東から北と東から南へのターンを禁止、奇数列では、北から西と南から西へのターンを禁止している。このDyADでは、エネルギー消費を減らし、ライブロックの可能性を減らす最短奇数偶数を使っている。
<
>
-Slack-Time Aware
--殆どの動的ルーティングはリアルタイム命令に適していない。動的ルーティングの遅延はとても大きい。パケットは違う経路を通り、それ故パケットは、間違った順番で受信される。遅れてきたパケットはオーディオやビデオストリームのような干渉を引き起こす。
<
>
-Hot-Potato Routing
--hot-potatoルーティングアルゴリズムは、パケットはルータのバッファに一時的に保存されることなく、いつでも転送される。パケットがルータに着いた時、ルータはパケットの正しい受信先に転送されるが、もし2つのパケットが同時に同じ方向へ転送されようとしたら、片方のパケットを他の方向へ転送する。このパケットは目的先からはなされる。この事をミスルーティングという。最悪の場合、ミスルーティングされたバケットは、目的先から遠くへ転送され、他のパケットの邪魔をするかもしれない。ミスルーティングのリスクは、パケットを転送する前に、ランダムに少しの間待たせることで減らすことができる。ルータは、パケットを保存する必要が無いので、hot-potatoルーティングを作るコストは、極めて低い。
<
----
#comment
終了行:
[[森/2010]]
*Network on Chip Routing Algorithms :TUCS Technical Report [#e0bc5958]
-読んでまとめたが、レベル分けが若干おかしい。
***Oblivious Routing Algorithms [#c5215670]
--pseudo adaptive XY routing
---このルーティングは、静的もしくはネットワークの状態によっては動的に動作する。ネットワークが全くまたは、少ししか混雑していない時に静的に動作する。ネットワークがブロックされると、このアルゴリズムはadaptiveモードに切り替わり混雑していないルートを探し始める。
---pseudo adaptive XY routingは、メッシュネットワークで使われる。どのルータにもテンポラリの記憶容量があり、通信が混雑しているかどうかを判定する識別子が保存される。混雑しているときは、データを受け取らないようにしている。
---このルータは、同時に入ってきたパケットに対して優先付けを行っている。優先順としては、北、南、東、最後が西となっている。
---従来のXYroutingでは、ネットワークロード時間を外側のルータより、内側のルータのほうが多くなっていたが、このルーティングでは、ネット―ワーク全体に平等に分けられている。
--Surrounding XY Routing
---Surrounding XY Routingは、3つの異なるルーティングのモードがある。N-XY(Normal XY)モードは、基本的なXYルーティングとして動く。これは、パケットをX方向、つぎにY方向にルーティングを行う。ネットワークがブロックされるか、停止しているルータに行きあうまで、このモードを持続する。SH-XY(Surround horizontal XY)モードは、左か右隣のルータの動作が停止したときに使われる。3つめのモードは、SV-XY(Surround vertical XY)モードで、上か下のルータが停止しているときに使われる。
---SH-XYモードは、パケットを目的先の座標の正しい列の場所にルーティングを行う。このアルゴリズムはパケットを最も短いパスのなで停止しているルータを迂回する。この状況では、パケットは既に正しい列にあるので、SV-XYモードとは少々異なる部分がある。パケットは左か右にルーティングすることができる。SH-XYとSV-XYモードの動作モードは、図10.ルータは、パケットがどちらのモードを使ってルーティングされたのかを知るために各モード内で識別子をつけている。
***Turn Models [#c4e07e18]
---ターンモデルアルゴリズムは、ライブロックフリー。
--West-first Routing
---West-firstルーティングでは、全ての西へのターンを防ぐ。西に行くパケットは必要な分だけ最初に西に進む。後で西に進むことはできない。
--North-last Routing
---このルーティングでは、北から目をそむけることはできない。パケットは、北へのルーティングを最後に行わなければならない。
--Negative-first Routing
---このアルゴリズムは、正方向から負方向へのターンを除いてすべてのターンを許可する。パケットは、何をするよりまず、負方向へルーティングを行わなければならない。
***Deterministic Routing Algorithms [#vb29bdba]
--静的ルーティングはパケットを毎回決められたパスにルーティングを行う。このアルゴリズムは、レギュラーとアンレギュラーなネットワーク両方で使われる。混雑の無いネットワークでは、信頼性が高く、少ない遅延が得られる。また、これはパケットはいつも正しい順番で各目的先に着くのでリアルタイムシステムに向いている。簡単なものでは、各ルータが他のルータへのルーティングの情報を持っているルーティングテーブルがある。ネットワークの構造が変更されると、各ルータもアップデートする必要がある。
--Shortest Path Routing
---最短経路ルーティングは、最も簡単な静的ルーティングのアルゴリズムである。パケットは、常に可能な限り最短経路にルーティングされる。distance vector routingとlink state routing が最短経路アルゴリズムである。
>
--[[Distance Vector Routing>Wikipedia:Distance-vector_routing_protocol]]
---それぞれのルータが、隣あうルータと受け入れ先の情報を持ったルーティングテーブルを持っている。ルータは、他のルータとルーティングテーブルの情報を交換し、最新の状態に保つようにしている。ルータはパケットをルーティングテーブルより最短経路を導き、パケットを転送している。このルーティングはネットワーク全体の構造を各ルータが知らなくてもよいので、簡単な方法となっている。
<
>
--Link State Routing
---このルーティングは、distance Vector Routingを改良したものである。基本的なアイディアは、distance Vector Routingと同じであるが、このルーティングでは、各ルータがルーティングテーブルを共有している。NoCでのLink State Routingは既存のものに少しNoC用のカスタマイズが加えられている。生成ステージ(NoCを作るとき?)にて、ネットワーク全体をカバーしているルーティングテーブルは、ルータのメモリに保存されている。ルータは、ネットワーク構成が変更されたり、ミスが起こったりするときに、ルーティングテーブルをアップデートする。
<
--Source Routing
---このルーティングでは、送り側がパケットの全てのパスを決定する。全てのルーティング情報は転送前にパケットのヘッダに保存され、送り側が決めたルート通りに転送を行う。
---vector routingは基本的にソースルーティングライクである。vector routingでルーティングされるパスは鎖型に表される。どのunitも2つのルータ間を1ホップで表す。ルーティングされるパスは、必ずしも最短経路にする必要はない。
---Arbitration look ahead scheme(ALOAS)はソースルーティングよりも早いルーティングである。ルーティングの経路の情報は、パケットが転送される前にルータに与えられる。ルートの情報は特別なチャンネルを使って転送される。
---contention-free routingは基本的に、ルーティングテーブルと[[TDM(time division multiplexing)>wikipedia:時分割多重化]]のアルゴリズムで出来ている。どのルータも正しいアウトプットと時間割り当てを、受信、送信のペアで持っているルーティングテーブルがある。このアルゴリズムはPhilips AEthereal NoCやclockworkルーティングで使われる。
--Destination-tag Routing
---目的先タグルーティングは、ソースルーティングの逆バージョンに似ている。送り側は、目的先タグとして受信側のアドレスをルーティングの初めにパケットのヘッダーに保存する。どのルータも受信側のアドレスによって、個別にルーティングを行う。
--Topology Adaptive Routing
---静的ルーティングで`アルゴリズムは、いくつかのadaptiveな特徴を加えることで改善することができる。トポロジー適応ルーティングは少しだけ動的な要素を持つ。このアルゴリズムは、基礎的な静的ルーティングのように動作するが、動的なネットワークに適応するような特徴がある。もしルーティングテーブルの更新が必要なら、システムの管理者が行うことができる。このアルゴリズムに一致するのは、知っているように、online oblivious routingである。topology adaptive routingのコストと遅延は、静的なルーティングなアルゴリズムのものと近い。トポロジーの動的性で便宜的なのは、イレギュラーで動的なネットワークに適している。
--Stochastic Routing Algorithms
---このアルゴリズムでのルーティングは、パケットが目的先にすぐ、若しくは遅く到着するのを予測し、一致することを基礎としている。確率論的アルゴリズムは、単純でミスに寛容である典型的なモデルである。データのスループットは高いが、欠点として、遅くたくさんのネットワークリソースを使う。
---確率論的ルーティングアルゴリズムは、パケットの[[TTL(time to live)>http://e-words.jp/w/TTL-2.html]]をけっていする。これは、ネットワークの中をパケットがどれくらいの間移動を可能にするかということ。この時間が来ると、パケットはネットワーク上から削除される。
--3.4.1 Flooding Algorithms
---最も有名な確率論的ルーティングとして、floodingアルゴリズムがある。これから3つの異なるfloodingのアルゴリズムを紹介する。
>
--Probabilistic Flood
---このProbabilistic Floodが一番簡単なモデルである。ルータは、パケットの目的先を知ることなく、ルータに入ってきたパケットをコピーし、送れるルータ全てに送る。パケットのコピーは、ネットワーク全体に広がる。最後に少なくとも1つのコピーが受信側に到着し、重複したコピーは削除される。
<
>
--Directed Flood
---directed floodルーティングアルゴリズムは、probabilistic floodアルゴリズムを改良したものである。これは、目的先の近くの方向へパケットを送る。このルーティングは、probabilistic floodよりミスに寛容で、ネット―ワークのリソースも少なくて済む。
<
>
--Random Walk
---ランダムウォークアルゴリズムは、ネットワークに送るパケットのコピー量を予想する。ルーティングパスにある全てのルータは、入力されたパケットをいくつかのアウトプットを通って送信される。パケットはdirected flood同様の方法で送られる。ランダムウォークは、directed floodと同じくらいミスに寛容であるが、エネルギーとバス幅は少なくて済む。
<
>
--Valiant's Random Algorithms
---優れたランダムアルゴリズムは、部分的に確率論的なアルゴリズムである。oblivious routingの1つの大きな問題として、ネットワークでのイレギュラーなロードに対する影響である。ロードはネットワークの中心で特に高くなる。優れた(valiant)ランダムアルゴリズムは、様々な種類のあるネットワーク上のトラフィックロードを均一にする。このアルゴリズムはまず、無作為にネットワークの中心にあるノードを抽出し、そこにパケットを転送する。それからパケットは、単にそこにルーティングされる。これらの手法は、いくつかのobilivious routingで使われている。
<
***Adaptive Routing Algorithms [#u7519efe]
-4.1 Minimal Adaptive Routing
--動的最短ルーティングアルゴリズムは常に最も短い経路を使う。このアルゴリズムは、1つ以上の最短、若しくは可能な限り短いルーティングがあるときに有効的である。このアルゴリズムは、混雑の少ないルートで使われる。
-4.2 Fully Adaptive Routing
--完全動的アルゴリズムは混雑が起こっていないルートのときは、いつも使われる。このアルゴリズムは、最短経路を全く気にしない。典型的に、このルーティングは、ルートに優先付けを行うことで、ルータが一方的に使われて混雑することがない。
>
-4.2.1 Congestion Look Ahead
--混雑先見アルゴリズムは他のルータからブロックの情報を受け取る。この情報を受け取ることで、混雑を回避することができる。
<
-4.3 Turnaround Routing
--転換ルーティングは、バタフライやファットツリーネットワークのルーティングである。送り側と受信側のパケットは、全てネットワークの同じ側にある。まずパケットは、送り側から無作為に反対側への中間ノードに送られる。このノードでは、パケットは転換され、それから同じ側のネットワークにある目的先に送られる。そこですべてのルーティングが始められる。ルーティングは中間ノードから受信先を決めるためにdestination-tagルーティングが行われる。
--転換ルーティングアルゴリズム上のルータは、前向きと後ろ向きにどちらの方向にもデータを流すことができる。このアルゴリズムは、前向きから後ろ向きに1度のみ転換を行うので、デットロック無しに動作できる。
--SPIN(Scalable Programmable Interconnect Network)は、転換ルーティングを用いたファットツリー型のものである。ミスに寛大なXGFT(eXtended Generalized Fat Tree)でTurnaround Routingはターンバックルーティングと呼ばれている。このXGFTシステムのネットワークトポロジーもまたfat-treeである。今までのturnaround routnigはランダムに中間のノードを選んでいたが、このXGFT's turnback routnigは、すこし基本的な転換ルーティングとは異なり、自分で選べるようになっている。これは、ネットワークが混雑しているときに役に立つ。
>
-Turn-Back-When-Possible
--TBWPは、ツリーネットワークのアルゴリズムである。これは、転換ルーティングを改良したバージョンである。turn-backチャンネルがビジーだと、このアルゴリズムは高いレベルのスイッチの中でフリーなルートを探す。このチャンネルは、前と後ろ方向のどちらでも考えられる。これは、ネットワークで、ルーティングの進行方向を変えるために使われる。
<
-4.4 Other Adaptive Routing Algorithms
>
-IVAL(Improved VALiant's randomized routing)
--IVALは oblivious Valiant's アルゴリズムを改良したバージョンである。これは、turn around ルーティングに少し似ている。このアルゴリズム上の最初のステージでは、パケットは、oblivious dimension orderルーティングを送り側から受信側までの中からランダムに選択します。次のステージでは、アルゴリズムは平等に動作します、しかし、このときにこのネットワークはオーダーを入れ替えます。IVALでデッドロックを回避するためには、ルータのチャンネルをバーチャルチャンネルにする必要があり、完全にデッドロックフリーなものにするためには、4つのバーチャルチャンネルが必要となる。
<
>
-2TURN
--このアルゴリズムは、アルゴリズム的な記述が存在しない。このアルゴリズムは、密閉形式でのみルーティングパスが決められる。送信側から受信側までこのアルゴリズムでは、常にUターンと方向を変えることの2つをしない物で構成されている。IVALルーティングだけで2turnルータは、もし全てのルータがバーチャルチャンネルを持っていればデッドロックを回避できる。
--ローカリティはルーティングアルゴリズムの基準で、パケットが平均的に転送される距離で決まる。この基準は、パケットの低いロードの端から端までの遅延によってきまる。IVALと2TURNアルゴリズムはValiantルーティングのおおよそ20%〜25%以上改善されている。2TURNのローカリティは最適なものにかなり近いものとなっている。
<
>
-Q-routing
--Q-routingの機能は、ネットワーク通信の統計がベースとなっている。このアルゴリズムは、遅延と混雑の情報を集め、ネットワーク通信の統計を維持している。このアルゴリズムは、統計を元にルーティングを決定する。
<
>
-Odd-Even Routing
--奇数偶数ルーティングは、adaptiveアルゴリズムで、DyAD(dynamically adaptive and deterministic)NoCシステムで使われる。このルーティングは、デッドロックフリーで、偶数の列にあるとき東から北と東から南へのターンを禁止、奇数列では、北から西と南から西へのターンを禁止している。このDyADでは、エネルギー消費を減らし、ライブロックの可能性を減らす最短奇数偶数を使っている。
<
>
-Slack-Time Aware
--殆どの動的ルーティングはリアルタイム命令に適していない。動的ルーティングの遅延はとても大きい。パケットは違う経路を通り、それ故パケットは、間違った順番で受信される。遅れてきたパケットはオーディオやビデオストリームのような干渉を引き起こす。
<
>
-Hot-Potato Routing
--hot-potatoルーティングアルゴリズムは、パケットはルータのバッファに一時的に保存されることなく、いつでも転送される。パケットがルータに着いた時、ルータはパケットの正しい受信先に転送されるが、もし2つのパケットが同時に同じ方向へ転送されようとしたら、片方のパケットを他の方向へ転送する。このパケットは目的先からはなされる。この事をミスルーティングという。最悪の場合、ミスルーティングされたバケットは、目的先から遠くへ転送され、他のパケットの邪魔をするかもしれない。ミスルーティングのリスクは、パケットを転送する前に、ランダムに少しの間待たせることで減らすことができる。ルータは、パケットを保存する必要が無いので、hot-potatoルーティングを作るコストは、極めて低い。
<
----
#comment
ページ名: