二分バンド幅のソースを表示

'''二分バンド幅<ref>{{Cite book|title=並列コンピュータ 非定量的アプローチ|url=https://books.google.pt/books?id=dLv9DwAAQBAJ&pg=PA94&lpg=PA94&dq=Bisection+bandwidth&source=bl&ots=lTdPkFaqKc&sig=ACfU3U0k8Ijfn8KGtNaJWUlxl81ROILI3g&hl=ja&sa=X&ved=2ahUKEwjFwLTO3Yb1AhU97uAKHR6_BXMQ6AF6BAgtEAM#v=onepage&q=Bisection%20bandwidth&f=false|publisher=株式会社 オーム社|date=2020-09-26|isbn=978-4-274-22571-0|language=ja|last=天野英晴}}</ref>'''（Bisection Bandwidth）とは、[[コンピュータネットワーク]]では、ネットワークがもっとも転送帯域の狭い場所で2つのパーティションに分割されている場合、ネットワークトポロジの断面の転送容量。

2つのパーティション間で使用可能な[[帯域幅]]<ref>{{Cite book|last=John L. Hennessy and David A. Patterson|title=Computer Architecture: A Quantitative Approach|edition=Third|publisher=Morgan Kaufmann Publishers, Inc|year=2003|isbn=978-1-55860-596-1|page=[https://archive.org/details/computerarchitec0003henn/page/789 789]|url=https://archive.org/details/computerarchitec0003henn/page/789}}</ref>。 

連結されたネットワークの転送能力を示す目安として使われている。

したがって二等分は、2つのパーティション間の帯域幅が最小になるように実行する必要がある<ref name=":0">{{Cite book|title=Fundamentals of parallel multicore architecture|last=Solihin|first=Yan|publisher=CRC Press|year=2016|isbn=9781482211191|pages=371–381}}</ref>。 


帯域幅とは、ネットワークの2つの部分を半分に等分した場合に、その間を通過できる最大双方向データレートのこと<ref>{{Cite book|title=Foundations of modern networking : SDN, NFV, QoE, IoT, and Cloud|url=https://www.worldcat.org/oclc/927715441|date=2016|location=Indianapolis, Indiana|isbn=978-0-13-417547-8|oclc=927715441|others=Florence Agboma, Sofiene Jelassi|first=William|last=Stallings}}</ref>。

バイセクション帯域幅は、システム全体で利用可能な真の帯域幅を提供し、ネットワーク全体のボトルネック帯域幅を占める。

したがって、二分バンド幅は、他のどのメトリックよりも優れたネットワークの帯域幅特性を表す。

== 二分バンド幅の計算 ==
[[ネットワーク・トポロジー|nノードの線形アレイの]]場合、二分バンド幅は1つのリンク帯域幅である。リニアアレイの場合、ネットワークを2つのパーティションに分割するには、1つのリンクのみを切断する必要がある。
[[ファイル:Bisected_linear_array.jpg|なし|サムネイル|173x173ピクセル|線形アレイネットワークの二等分線]]
nノードのリングトポロジの場合、ネットワークを二等分するために2つのリンクを切断する必要があるため、二分バンド幅は2つのリンクの帯域幅になる。
[[ファイル:Bisected_ring.jpg|なし|サムネイル|178x178ピクセル|リングネットワークの二等分]]
nノードのツリートポロジの場合、1つのリンクを切断することでルートで二等分できるため、二分バンド幅は1つのリンク帯域幅になる。
[[ファイル:Bisected_tree.jpg|なし|サムネイル|170x170ピクセル|ツリーネットワークの二等分線]]
[[メッシュネットワーク|nノードのメッシュ]]トポロジの場合、 <math>\sqrt{n}</math>ネットワークを二等分するためにリンクを切断する必要があるため、二分バンド幅は<math>\sqrt{n}</math>リンク。
[[ファイル:Bisected_mesh.jpg|なし|サムネイル|173x173ピクセル| 2Dメッシュネットワークの二等分線]]
nノードのハイパーキューブトポロジの場合、ネットワークを二等分するためにn / 2リンクを切断する必要があるため、二分バンド幅はn / 2リンクの帯域幅になる。
[[ファイル:Bisected_hypercube.jpg|なし|サムネイル|ハイパーキューブネットワークの二等分]]

== 二分バンド幅の重要性 ==
ネットワークパフォーマンスのこの測定の重要性に対する理論的サポートは、Clark Thomborson <ref>[http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Thomborson:Clark_D=.html Clark Thomborson]</ref>（旧Clark Thompson）の博士課程の研究段階で開発された。Thomborsonは、ソート、[[高速フーリエ変換]]、行列-行列乗算の重要なアルゴリズムが、二分幅が不十分なコンピューターではCPU制限またはメモリー制限ではなく、通信制限になることを証明した。

F.トムソンレイトンは博士課程の研究で<ref>{{cite thesis|author=F. Thomson Leighton|author-link=:en:F. Thomson Leighton|title=Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks|publisher=MIT Press|year=1983|ISBN=0-262-12104-2|url=http://mitpress.mit.edu/books/complexity-issues-vlsi}}</ref>、シャッフル交換ネットワークとして知られるDeBruijnグラフの計算上重要な変形二等分幅に関するThomborsonの緩い限界を強化している<ref>{{Cite conference|last=Clark Thompson|url=http://resolver.caltech.edu/CaltechCONF:20120504-143038397|title=Area-time complexity for VLSI|conference=Proc. Caltech Conf. on VLSI Systems and Computations|pages=81–88|year=1979}}</ref>。

Bill Dallyによると遅延、平均ケースのスループット、ホットスポットスループットの分析に基づいて、高次元ネットワークと比較して低次元ネットワーク（同じ二分幅（たとえば、 tori ）を持つバイナリn-cubes）は<ref name=":0">{{Cite book|title=Fundamentals of parallel multicore architecture|last=Solihin|first=Yan|publisher=CRC Press|year=2016|isbn=9781482211191|pages=371–381}}</ref>、待ち時間が短縮され、ホットスポットのスループットが高くなるとしている<ref>{{Cite journal|last=Bill Dally|author-link=:en:Bill Dally|year=1990|title=Performance analysis of k-ary n-cube interconnection networks|journal=IEEE Transactions on Computers|volume=39|issue=6|pages=775–785|DOI=10.1109/12.53599}}</ref>。

== 出典 ==
<references />

{{DEFAULTSORT:にふんはんとはは}}
[[Category:ネットワーク管理]]
[[Category:情報理論]]
[[Category:信号処理]]
[[Category:周波数]]
[[Category:データ転送]]