Graph Keywords
2017年1月13日
相互結合網
相互結合網とは，複数のデバイスを相互に結合し，デバイス間での通信を実現するためのネットワークのこと
http://www.ieice-hbkb.org/files/06/06gun_05hen_09.pdf
ネットワークトポロジー
相互結合網の形状のこと。
相互結合網は，そのネットワークトポロジーによって四つに分類できる．
- 共有媒体網は，初期の Ethernet（10 BASE-2 や 10 BASE-5）LAN などに用いられた方式で，1 本のバスを複数のデバイスが共有するネットワークを指す
ex.共有バス - 直接網は，個々のデバイス同士を直接リンクで結合するネットワークのことである．デバイスは通常，ルータを内蔵することで複数のリンクを結合することができるため，直接網では様々なトポロジー，ルーティングを採用することができる
- トポロジー：理想的なトポロジーは各デバイスがすべてのデバイスと直接つながっている完全結合であるが，実装面の点から実現することが困難である．そこで，性能面と実装面のトレードオフの議論から多数のトポロジーが提案されている．
- ルーティング：通信データは，パケットに分割され転送され，多くの場合，複数のデバイスを経由して目的地に到達することになる．ルーティングが，その中継するデバイス群を決定する．
無制限にパケットに対して非最短経路がとることを許すと，パケットが永久に宛先に到達できない状況であるライブロックを引き起こす．
デッドロックとは，ネットワークを通過中のパケットが，起こる可能性がない事象を待ち続けることにより，転送することが不可能となる状態のことをいう． - スイッチング：パケットがデバイス間を転送される場合に，スイッチングによって経路をパケットに割り当てる
- 間接網はデバイス間の通信を，それらとは独立に存在するスイッチにより行う方式において，スイッチ及びスイッチ間のリンクの集合を指す．演算ノード間，演算ノード・メモリモジュール間，演算ノード・入出力間（ファイルなど）を接続するものとして多く用いられる．通常，各デバイスは一対の双方向通信リンクにより結合網と接続される．個々のデバイスにおけるピーク通信性能はこのリンクの物理的転送速度により規定されるが，結合網全体の通信性能はトポロジーや通信方式により大きく変わる．
間接網におけるデバイス間の通信は，本質的に 1 以上のスイッチを経由する．間接網における距離は，経由スイッチの数により測られる．間接網では多くの場合，入力から出力に至る単方向性の接続を基本に考える．双方向性の通信は，単方向通信の重畳として考えることが多い．
ex.クロスバ（crossbar）,多段網（Multistage Interconnection Network：MIN）, 不等距離間接網 - ハイブリッド網は，上記三つの網に含まれる方式を組み合わせて実現されるもので，例えば直接網であるハイパーキューブの各次元をクロスバスイッチで接続するハイパクロスバ網などが提案されている
Wormhole switching,wormhole routing
It is a subset of flow control methods called Flit-Buffer Flow Control.
Graph Eccentricity
http://d.hatena.ne.jp/ryamada22/20051003/1128318198
permutation routing
oblivious routing
シェアソート
シェアソート（英: shear-sort）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した[1]。安定ではない内部ソートであり、最悪の場合の時間計算量はO(n1.5)である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。
Comments are closed.