二分バンド幅

二分バンド幅^[1]（Bisection Bandwidth）とは、コンピュータネットワークでは、ネットワークがもっとも転送帯域の狭い場所で2つのパーティションに分割されている場合、ネットワークトポロジの断面の転送容量。

2つのパーティション間で使用可能な帯域幅^[2]。

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

したがって二等分は、2つのパーティション間の帯域幅が最小になるように実行する必要がある^[3]。

帯域幅とは、ネットワークの2つの部分を半分に等分した場合に、その間を通過できる最大双方向データレートのこと^[4]。

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

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

二分バンド幅の計算

nノードの線形アレイの場合、二分バンド幅は1つのリンク帯域幅である。リニアアレイの場合、ネットワークを2つのパーティションに分割するには、1つのリンクのみを切断する必要がある。

線形アレイネットワークの二等分線

nノードのリングトポロジの場合、ネットワークを二等分するために2つのリンクを切断する必要があるため、二分バンド幅は2つのリンクの帯域幅になる。

リングネットワークの二等分

nノードのツリートポロジの場合、1つのリンクを切断することでルートで二等分できるため、二分バンド幅は1つのリンク帯域幅になる。

ツリーネットワークの二等分線

nノードのメッシュトポロジの場合、 ${\sqrt {n}}$ ネットワークを二等分するためにリンクを切断する必要があるため、二分バンド幅は ${\sqrt {n}}$ リンク。

2Dメッシュネットワークの二等分線

nノードのハイパーキューブトポロジの場合、ネットワークを二等分するためにn / 2リンクを切断する必要があるため、二分バンド幅はn / 2リンクの帯域幅になる。

ハイパーキューブネットワークの二等分

二分バンド幅の重要性

ネットワークパフォーマンスのこの測定の重要性に対する理論的サポートは、Clark Thomborson ^[5]（旧Clark Thompson）の博士課程の研究段階で開発された。Thomborsonは、ソート、高速フーリエ変換、行列-行列乗算の重要なアルゴリズムが、二分幅が不十分なコンピューターではCPU制限またはメモリー制限ではなく、通信制限になることを証明した。

F.トムソンレイトンは博士課程の研究で^[6]、シャッフル交換ネットワークとして知られるDeBruijnグラフの計算上重要な変形二等分幅に関するThomborsonの緩い限界を強化している^[7]。

Bill Dallyによると遅延、平均ケースのスループット、ホットスポットスループットの分析に基づいて、高次元ネットワークと比較して低次元ネットワーク（同じ二分幅（たとえば、 tori ）を持つバイナリn-cubes）は^[3]、待ち時間が短縮され、ホットスポットのスループットが高くなるとしている^[8]。

出典

^ 天野英晴『並列コンピュータ非定量的アプローチ』株式会社オーム社、2020年9月26日。ISBN 978-4-274-22571-0。
^ John L. Hennessy and David A. Patterson (2003). Computer Architecture: A Quantitative Approach (Third ed.). Morgan Kaufmann Publishers, Inc. p. 789. ISBN 978-1-55860-596-1
^ ^a ^b Solihin, Yan (2016). Fundamentals of parallel multicore architecture. CRC Press. pp. 371–381. ISBN 9781482211191
^ Stallings, William (2016). Foundations of modern networking : SDN, NFV, QoE, IoT, and Cloud. Florence Agboma, Sofiene Jelassi. Indianapolis, Indiana. ISBN 978-0-13-417547-8. OCLC 927715441
^ Clark Thomborson
^ F. Thomson Leighton [in 英語] (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis). MIT Press. ISBN 0-262-12104-2。
^ Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations. pp. 81–88.
^ Bill Dally (1990). “Performance analysis of k-ary n-cube interconnection networks”. IEEE Transactions on Computers 39 (6): 775–785. doi:10.1109/12.53599.

[1] 天野英晴『並列コンピュータ非定量的アプローチ』株式会社オーム社、2020年9月26日。ISBN 978-4-274-22571-0。

[2] John L. Hennessy and David A. Patterson (2003). Computer Architecture: A Quantitative Approach (Third ed.). Morgan Kaufmann Publishers, Inc. p. 789. ISBN 978-1-55860-596-1

[:0-3] Solihin, Yan (2016). Fundamentals of parallel multicore architecture. CRC Press. pp. 371–381. ISBN 9781482211191

[4] Stallings, William (2016). Foundations of modern networking : SDN, NFV, QoE, IoT, and Cloud. Florence Agboma, Sofiene Jelassi. Indianapolis, Indiana. ISBN 978-0-13-417547-8. OCLC 927715441

[5] Clark Thomborson

[6] F. Thomson Leighton [in 英語] (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis). MIT Press. ISBN 0-262-12104-2。

[7] Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations. pp. 81–88.

[8] Bill Dally (1990). “Performance analysis of k-ary n-cube interconnection networks”. IEEE Transactions on Computers 39 (6): 775–785. doi:10.1109/12.53599.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]