ネットワークコンピューティング論II課題 吉永研究室 1552013 多田 昂介 Exercises E. 10 • 問 図 E.11(31 ページ) に示した Omega ネットワークは 4 つの スイッチの 3 列で構成され、各スイッチは 2 入力 2 出力を持 つ。各スイッチは、上方のス イッチ入力から上方のスイッチ出 力、下方のスイッチ入力から下方のスイッチ出力をつな ぐスト レート (直進) と、上方のスイッチ入力から下方のスイッチ出力、 その逆をつなぐ エクスチェンジ (交差) に設定することができ る。各スイッチ列には、入力、出力に上から 下へ 0,1,...,7 のラ ベル付けをする。 Exercises E. 10 • Omegaネットワークの全体図とスイッチの設定 ストレート エクスチェンジ 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 10 • a) スイッチをエクスチェンジに設定した時、メッセージが使うスイッチ入出 力のラベル値の関係はどうなるか? – 例: 通るスイッチのすべての設定をエクスチェンジに設定（入力000→出力111） • すべてのビットが反転 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 10 • a) スイッチをエクスチェンジに設定した時、メッセージが使うスイッチ入出 力のラベル値の関係はどうなるか? – A. 3つの列がそれぞれのビットに対応し、エクスチェンジ設定では出力ビットが反転 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 2, 3ビット目 が反転 Exercises E. 10 • b) 隣接する列でつながっている 2 つのスイッチ間において、入力につなが る出力のラベル間にどのような関係があるのか? – A. 列（階層）を通過するごとにビットが左シフトしている • 例: 010→100, 110→101 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 010 011 011 100 100 100 101 101 101 110 111 110 110 111 Exercises E. 10 • c) (a), (b)の結果をもとに、Omega ネットワークの分散制御をする単純な ルーティングの仕組みを設計、記述せよ。メッセージは送信プロセッサに おいて計 算されたルーティングタグを含んでいる。プロセッサはどのよう にタグを計算する のか?各スイッチはどうやってルーティングタグのビット を検査して自身のスイッ チの設定をするのかを記述せよ。 – (a) エクスチェンジ設定では各ビットが反転 – (b) 各階層では1ビットずつ左シフト Exercises E. 10 • c) 例1: 入力 [010] • 出力 [100] ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 10 • c) 例2: 入力 [100] • 出力 [000] ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 10 • c) 2つの例から入力と出力の関係を求める – A. 各ビットのXORの結果によって設定が分かる • XORの結果が”1”→エクスチェンジ設定 • 〃 “0”→ストレート設定 入力 0 1 0 XOR ステージ2 ステージ2 1 0 0 0 0 0 1 0 0 XOR 1 0 0 1 1 0 エクスチェンジ エクスチェンジ ストレート 出力 入力 ステージ1 出力 Exercises E. 11 • 問 図 E.11(31 ページ) に示した 8 ノード Omega ネッ トワーク において以下の並び換え (すなわち、通信パターン) を実現で きるのか、証明 せよ。 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • a) ビット逆順並び換え (bit-reversal permutation): – 入力を1ビット右シフトした出力 – 以下の入力から出力への通信を行う 入力 出力 000 000 001 100 010 001 011 101 100 010 101 110 110 011 111 111 Exercises E. 11 • a) 通過するすべてのスイッチの通信が衝突するため不可 – 各スイッチに2つ以上の同じ出力が同時に存在 衝突＝通信不可 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • b) 完全シャッフル並 び 換 え (perfect shuffle permutation): – 入力を2ビット左シフトした出力 – 以下の入力から出力への通信を行う 入力 出力 000 000 001 010 010 100 011 110 100 001 101 011 110 011 111 101 Exercises E. 11 • b) いくつかのスイッチの通信の出力が衝突するため不可 衝突＝通信不可 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • c) ビット補足並び換 え (bit-complement permutation): – 入力の1の補数（全ビット反転）を行った出力 – 以下の入力から出力への通信を行う 入力 出力 000 111 001 110 010 101 011 100 100 011 101 010 110 001 111 000 Exercises E. 11 • c) 出力の衝突が起きないため通信可能 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • d) 行列置き換え並び換え (matrix transpose permutation): – 他のビットを中央のビットと入れ替えた出力 – 1ビット目と入れ替えたか、3ビット目と入れ替えたかで2種存在 A) 1ビット目入れ替え B) 3ビット目入れ替え 入力 出力 入力 出力 000 000 000 000 001 100 001 010 010 001 010 100 011 101 011 110 100 010 100 001 101 110 101 011 110 011 110 101 111 111 111 111 Exercises E. 11 • d) (A)の場合: いくつかのスイッチの通信が衝突するため不可 衝突＝通信不可 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • d) (B)の場合:スイッチの通信が衝突するため不可 衝突＝通信不可 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • e) バレルシフト並び換 え (barrel-shift permutation): – ノードiからノード(i+1) mod (n-1)へ通信を行う（nはノード数であり0≦i） – 以下の入力から出力への通信を行う 入力 出力 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 000 Exercises E. 11 • e) 出力の衝突が起きないため通信可能 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 Exercises E. 11 • f) Butterfly permutation(英語版F. 11 (d)として収録) – 入力の最上位ビットと最下位ビットを入れ替えた出力を持つ – 以下の入力から出力への通信を行う 入力 出力 000 000 001 100 010 010 011 110 100 001 101 101 110 011 111 111 Exercises E. 11 • f)いくつかのスイッチの通信が衝突するため不可 衝突＝通信不可 ステージ1 ステージ2 ステージ2 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111
© Copyright 2024 ExpyDoc
