勉強会資料−相互結合網 竹村尚大 平成 14 年 5 月 8 日^{1 相互結合網の分類 ; • タイミング方式 ; – 同期方式結合網がグロ−バル・クロックに ; よって一斉に動作しリンクされる。 ; – 非同期方式個々の転送要求がランダムに生起 ; し、要求に応じて非同期的にリンクされる。 ; • 制御方式 ; – 集中制御中央の一つの演算装置によって、全 ; てのスイッチなどの動作が制御される。 ; – 分散制御スイッチなど自体に制御装置が内 ; 蔵されており、各スイッチなどは自律的に動 ; 作する。 ; • 交換方式 ; – 回線交換入力から出力へ至る経路が同時に ; 生成されるもので、大量のデ−タ転送に適 ; する。 ; – パケット交換デ−タがパケット化されて送 ; り出され順次経路が生成されるもので、小 ; 量のデ−タ転送に適する。三種類の方式があ ; り、図 1 に示す。 ; ∗ 蓄積交換：ルータに到達したパケットは ; 一旦バッファに蓄積され、出力リンクが ; 空いていれば、そこから出力される。耐 ; 故障性に優れており、網全体としての転 ; 送能力が高い。また、デッドロック発生 ; 確率が低い。 ; ∗ ワームホール：スイッチ内にフリットと ; 呼ばれるバッファがあり、出力リンクが ; 空いていれば、パケットはフリットごと ; に直ちに出力リンクにスイッチされる。}^{通信時間 (レイテンシ) は蓄積交換に比べ ; て短いが、輻輳を加速させ、デッドロッ ; クの確率も高い。 ; ∗ バーチャルカットスルー：蓄積交換とワー ; ムホールの中間的存在で、ワームホー ; ルで出力リンクが閉鎖されている場合 ; は、パケット全体を一旦バッファに退避 ; させる。 ; • トポロジ (幾何学的形状) ; トポロジによる分類を図 2 に示す。静的網は直 ; 接結合網とも呼ばれ、ノ−ドから直接通信できる ; ノ−ドが限定されており、ノ−ド間の結合は静的 ; に固定されている。動的網は間接結合網とも呼ば ; れ、送受信ノ−ド間にはスイッチ群が置かれてお ; り、これらを制御することによって、任意の送受 ; 信ノ−ド間の通信ができる。 ; 2 評価項目 ; • 距離静的網における二つのノ−ド間の最小中継 ; ノ−ド数＋１。距離のうちで最大のものを直径と ; いう。動的網においては、送受信ノ−ド間でのス ; イッチ段数が距離となる。 ; • 次数静的網のノ−ド一つあたりに直接結合され ; るノ−ド数。 ; • 総スイッチ数／総リンク数 ; • 拡張性 ; • ３次元実装の容易性 ; • 耐故障性 ; • 多様な網の埋め込み能力}

1

• ル−ティングの容易性 ; 3 基本通信パタ−ン ; 送信ノ−ド番号 x の２進表示を (a_{n}, ⋯, a_{2}, a_{1}) と ; したときの受信ノ−ド番号を送信ノ−ド番号の置換で ; 表す。 ; • エクスチェンジ置換 ; E_{i}(x) = (a_{n}, ⋯, \overline{a_{i}}, ⋯, a_{1}) ; • シャフル置換 ; σ(x) = (a_{n−1}, a_{n−2}, ⋯, a_{1}, a_{n}) ; σ_{k}(x) = (a_{n}, ⋯, a_{k+1}, a_{k−1}, ⋯, a_{1}, a_{k}) ; σ^{k}(x) = (a_{n−1}, ⋯, a_{n−k+1}, a_{n}, a_{n−k}, ⋯, a_{1}) ; • バタフライ置換 ; β(x) = (a_{1}, a_{n−1}, ⋯, a_{2}, a_{n}) ; β_{k}(x) = (a_{n}, ⋯, a_{k+1}, a_{1}, a_{k−1}, ⋯, a_{2}, a_{k}) ; β^{k}(x) = (a_{n−k+1}, a_{n−1}, ⋯, a_{n−k+2}, a_{n}, a_{n−k}, ⋯, a_{1}) ; • ビット逆転置換 ; ρ(x) = (a_{1}, a_{2}, ⋯, a_{n}) ; ρ_{k}(x) = (a_{n}, ⋯, a_{k+1}, a_{1}, a_{2}, ⋯, a_{k−1}, a_{k}) ; ρ^{k}(x) = (a_{n−k+1}, a_{n−k+2}, ⋯, a_{n−1}, a_{n}, a_{n−k}, ⋯, a_{1}) ; • シフト置換 ; α(x) = |x + 1|_{2^{n}} ; α_{k}(x) = |x + 1|_{2^{k}} + ⌊x/2^{k}⌋2^{k} ; α^{k}(x) = |x + 2^{n−k}|_{2^{n}} ; 但し、 | |_{a} は a を法とするモジュロ計算を表す。 ; それぞれの通信パターンを図 3 に示す。 ; 4 静的網 ; • 完全網 ; 図 4 に示す。直径は 1。次数は N − 1。 ; • スター網 ; 図 5 に示す。直径は 2。次数は中央ノードが N −1、 ; その他のノードが 1。 ; • リング網系 ; 図 6 に示す。単純リングの直径は N/2。次数は 2。 • トーラス網系

図 7 に示す。偏微分方程式の解法などに向いている。

– ２次元メッシュ網：直径は 2\sqrt{N}。次数は 4。 – ２次元トーラス網：直径は\sqrt{N}。次数は 4。 – ３次元トーラス網：直径は^{3} \sqrt{N}。次数は 6。 – ピラミッド網：最上位層が 0、最下位層が h

とし、第 i 層が 2^{i} × 2^{i} メッシュで構成されているとすると、 N = (4^{h+1} − 1)/3 で次数は 7。直径は 2h = log(3N) − 2。

– 再帰トーラス網 (RDT) ：次数は 8。直径は N = 1024 で 7、 N = 4096 で 10 程度。

• トリー網系図 8 に示す。

– 単純トリー網：次数は 3。直径は 2 log N。 – X トリー：次数 4。

– ファットトリー

• ハイパキューブ網系図 9 に示す。

– ハイパキューブ網：超立方体、２進 n-キューブとも呼ぶ。 N = 2^{n} 個のノードからなり、次数は log N。直径は log N。トリー、リング、トーラス網を包含できる。

– ベース mn-キューブ：２進キューブを拡張した網であり、 N = m^{n} のとき、次数、直径ともに log_{m} N である。

– 環立方体網 (CCC) ：２進 n-キューブの各ノードを n 個のノードからなるリングに置き換えたもの。 N = n2^{n} で、次数は 3、直径は 3n/2。

– CCT cube 網：２進 m キューブをサブネットとして、それらを完全網で結合したもの。 N = 2^{2m} で、次数は m + 2、直径は m + 1。図 10 に示す。

– ハイパクロス網：ノード番号を N_{i,j} としたとき、 N_{i,j} と N_{j,k} および N_{j,k} と N_{i,j} が直接通信できる構造となっている。。図 11 に示す。リング、トリー、２/３次元トーラス、ハイパキューブを包含できる。 • シャフル網系

図 12 に示す。

– シャフルエクスチェンジ網：次数 3。直径 2 log N。

– de Bruijn 網：次数 4。直径 log N。

– 循環オメガ網：動的網で述べるオメガ網の各スイッチ部分をノードで置き換え、両端をループで連結したもの。各ステージのノード数を n = 2^{m}、ステージ数を log 2n、 N = n log 2n とすると、次数は 4、直径は 2m+1 = 2 log n + 1 となる。

– スターグラフ網： n 個の記号の並びでノード番号とし、各ノードはノード番号の最初の文字と他の文字を入れ換えた番号のノードとリンクされる。 N = n!。次数 n − 1。直径は ⌊3(n − 1)/2⌋。

5 静的網におけるデッドロックとルーティング

5.1 リング網でのデッドロック防止

ワームホール方式のパケット交換の網の場合、出力リンクが空いてないと、それまで獲得したリンクを開放しないので、デッドロックが発生しやすい。これを解消するために、リンク (チャネル) を時分割して多重化する仮想チャネルという方法を用いる。さらに、ノード数 N のときに各ルータに N-1 個の仮想チャネル、 N 個のバッファを用意する構造化バッファプールを用いることによって、デッドロックを防止し、かつスループットの低下なしに通信が可能となる。

5.2 トーラス網、ハイパキューブ網におけるデッドロック防止

これらの網は多次元構造であり、全てのチャネルを低次元から昇順に番号を付け、必ず小さい番号からルーティングすることによって、デッドロックが防止できる。これを順次元ルーティングと呼ぶ。しかし、これではトラフィックに偏りがある場合に問題あるので、チャネルを仮想チャネルによって階層化し、クラスを移動するときに逆次元へのルーティングを許す次元逆行ルーティングや、ある方向への曲がりを制限することによってサイクルをなくす曲がり制限法などがある。

6 動的網

• クロスバ網：閉塞^{1} なしで任意の時刻に任意の送受信ノードを高速に結合できる。図 13 に示す。スイッチ段数は 1。スイッチ総数は N^{2}。使用する通信パターンに対応した各スイッチの制御パターンをメモリに記憶して、選択するなどの方式がある集中制御方式と、受信ノード番号などの制御情報が送信されたときに、各列にある制御回路が行と列のクロスポイントにあるスイッチの開閉を行う方式などがある分散制御方式がある。

• 多段結合網

– 非閉塞網任意の送受信ノード間に新たな通信要求や通信変更があった際に、既に接続中の他の送受信ノード間通信のためのスイッチ設定を変更しないで常に要求が満たされる。

∗ クロスバ網：クロスバ網は１段の非閉塞網である。

∗ 3 ステージ Clos 網：図 14 に示す。各ボックスはクロスバ網である。この網が非閉塞網となるためには、 m ≥ 2n − 1 を満たす必要がある。

– 再構成型非閉塞網任意の送受信ノード間の結合要求を満たすが、新しい接続要求や接続変更があった場合、接続中の他の送受信ノード間のスイッチ設定を変更する必要が生じる。

∗ Beneš網：図 15 に示す。スイッチ段数は 2 log N −1。スイッチ総数は N(2 log N − 1)/2。

∗ バイトニックソータ網：図 16 に示す。受信ノード番号に基づいてソーティングすることによって所定の送受信ノード間の通信を実現する。送信ノードのいく

1二つ以上の要求が同一スイッチで衝突する現象

つかで通信要求がない場合はバイトニックソータの後段にオメガ網を接続する。スイッチ段数は log N(log N + 1)/2。スイッチ総数は N log N(log N + 1)/4。

∗ 3 ステージ Clos 網： 2n − 1 > m ≥ n

のとき再構成型閉塞網となる。

– 閉塞網可能な通信パターン総数 N! のうちごく一部の結合を実現するもの。以下に述べる閉塞網では、 N/2 個の 2 入力 2 出力変換スイッチを log N 段連結して実現し、可能な通信パターン数は (\sqrt{N})^{N} = 2^{(NlogN)/2} である。

∗ オメガ網：図 17 に示す。シャフルエクスチェンジを log N 段連結して得られる。

∗ 間接２進 n-キューブ：図 18 に示す。２進 n-キューブをシミュレートしたもので、 C = Eβ_{2}Eβ_{3}, ⋯, Eβ_{n}Eσ^{−1} で表される。

∗ バンヤン網： Y = Eβ_{2}Eβ_{3}, ⋯, Eβ_{n}E で表される。

∗ ベースライン網：図 19 に示す。 B = Eσ_{n}^{−1}Eσ_{n−1}^{−1}, ⋯, Eσ_{2}^{−1}E で表され、 Beneš網の前半部分に相当する。また、ベースライン網の最終段に ρ を付加したものを R 網と呼ぶ。

オメガ網 (Ω)、間接２進 n-キューブ網 (C)、バンヤン網 (Y) には、 Ω^{−1} = C = Y σ の関係がある。

– 単一段結合網多段結合網の 1 ステージ分のスイッチからなる。

参考文献

[1] 富田眞治『並列コンピュータ工学』 (昭晃堂、 1996)

[2] 奥川峻史『並列計算機アーキテクチャ』 (コロナ社、 1991)

q