Пропускная способность бисекции

Пропускная способность бисекции — это мера пропускной способности вычислительной сети, определяемая как минимальная пропускная способность между двумя равными частями (бисекциями) сети^[1]. Пусть задан граф $G$ с вершинами $V$ , рёбрами $E$ и весами рёбер $w$ . Пропускная способность бисекции $G$ выражается следующим образом:

$BB(G)=\min _{S\subset V:|S|={\frac {1}{2}}|V|}\quad \sum _{u\in S,v\not \in S}w(u,v)$ .

Сеть разбивается (бисектируется) так, что пропускная способность между двумя подмножествами минимальна^[2]. Для сети считается, что она обладает полной пропускной способностью бисекции, если $BB(G)\geq {\frac {1}{2}}|V|$ ^[3]. Интуитивно полная пропускная способность бисекции означает, что если все вершины сети разбиты на пары источник-приёмник и каждая пара одновременно передаёт поток со скоростью 1, то в таком случае в бисекции сети не возникает узких мест. Таким образом, пропускная способность бисекции отражает пропускную способность самого узкого места, возникающего при разделении (бисекции) сети.

Мера пропускной способности бисекции используется и в российской практике (при проектировании высокопроизводительных вычислительных комплексов, сетей ЦОД и магистральных сетей). Данный показатель учитывается в отечественных образовательных курсах по архитектуре ЭВМ и сетей (например, в программах российских технических вузов), как часть стандартного набора метрик производительности сетей.

Для линейной последовательности (linear array) из n узлов пропускная способность бисекции равна пропускной способности одного канала, так как для разрезания сети на две части необходимо разорвать только одно соединение.

Для кольцевой топологии (ring) из n узлов, чтобы разделить сеть на две части, нужно разорвать два соединения, поэтому пропускная способность бисекции равна пропускной способности двух каналов.

Для древовидной топологии (tree) из n узлов сеть можно разрезать в корне, разорвав одно соединение, поэтому пропускная способность бисекции также равна одному каналу.

Для топологии «сетка» (mesh) из n вершин для бисекции необходимо разорвать ${\sqrt {n}}$ соединений, поэтому пропускная способность бисекции соответствует пропускной способности ${\sqrt {n}}$ каналов.

Для топологии гиперкуб (hyper-cube) из n узлов, для бисекции требуется разорвать n/2 соединений, соответственно пропускная способность бисекции равна пропускной способности n/2 каналов.

Теоретические основания важности данной меры производительности сети были разработаны в исследовании Кларка Томборсона (ранее Кларк Томпсон), выполненном для докторской диссертации^[4]. Томборсон доказал, что важные алгоритмы для сортировки, быстрого преобразования Фурье и умножения матриц начинают ограничиваться именно пропускной способностью соединений (а не вычислительной мощностью ЦП или скоростью памяти) на компьютерах с недостаточной пропускной способностью бисекции. Диссертация Ф. Томсона Лейтона^[5] уточнила и усилила нестрогое ограничение Томборсона^[6] с точки зрения пропускной способности бисекции вычислительно важных вариантов графов Де Брюна, известных как сети shuffle-exchange. Согласно анализу латентности, средней и максимальной (hot-spot) пропускной способности m-арных n-мерных кубических сетей, выполненному Биллом Дэлли^[2], можно сделать вывод, что низкоразмерные сети, по сравнению с высокоразмерными (например, двоичными n-кубами), при прочей равной пропускной способности бисекции (например, тор) обладают меньшей задержкой и большей пиковой пропускной способностью^[7].

Кроме того, имеются теоретические обоснования того, что пропускная способность бисекции и общая пропускная способность сети (network throughput) могут асимптотически различаться и возрастать с различными скоростями в зависимости от топологии сети^[3]^[8].

↑ John L. Hennessy и David A. Patterson. Computer Architecture: A Quantitative Approach. — Третье. — Morgan Kaufmann Publishers, Inc, 2003. — P. 789. — ISBN 978-1-55860-596-1.
↑ ¹ ² Solihin, Yan. Fundamentals of parallel multicore architecture : [англ.]. — CRC Press, 2016. — P. 371–381. — ISBN 9781482211191.
↑ ¹ ² Namyar, Pooria. Сквозная производительность топологий дата-центров // Proceedings of the 2021 ACM SIGCOMM 2021 Conference : [англ.] / Pooria Namyar, Sucha Supittayapornpong, Mingyang Zhang … [et al.]. — New York, NY, USA : Association for Computing Machinery, 9 августа 2021. — P. 349–369. — ISBN 978-1-4503-8383-7.
↑ C. D. Thompson (1980). A complexity theory for VLSI (PDF) (Thesis) [англ.]. Carnegie-Mellon University. Дата обращения 2024-06-01.
↑ F. Thomson Leighton (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis) [англ.]. MIT Press. ISBN 0-262-12104-2. Дата обращения 2024-06-01.
↑ Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations [англ.]. pp. 81—88. Дата обращения 2024-06-01. |access-date= требует |url= (справка)
↑ 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. Дата обращения 2024-06-01. |access-date= требует |url= (справка)
↑ Jyothi, Sangeetha Abdu. Измерение пропускной способности топологий сетей дата-центров // The 2014 ACM international conference on Measurement and modeling of computer systems : [англ.] / Sangeetha Abdu Jyothi, Ankit Singla, P. Brighten Godfrey … [et al.]. — New York, NY, USA : Association for Computing Machinery, 16 июня 2014. — P. 597–598. — ISBN 978-1-4503-2789-3. — doi:10.1145/2591971.2592040.

[1] John L. Hennessy и David A. Patterson. Computer Architecture: A Quantitative Approach. — Третье. — Morgan Kaufmann Publishers, Inc, 2003. — P. 789. — ISBN 978-1-55860-596-1.

[solihin2016-2] ¹ ² Solihin, Yan. Fundamentals of parallel multicore architecture : [англ.]. — CRC Press, 2016. — P. 371–381. — ISBN 9781482211191.

[namyar2021-3] ¹ ² Namyar, Pooria. Сквозная производительность топологий дата-центров // Proceedings of the 2021 ACM SIGCOMM 2021 Conference : [англ.] / Pooria Namyar, Sucha Supittayapornpong, Mingyang Zhang … [et al.]. — New York, NY, USA : Association for Computing Machinery, 9 августа 2021. — P. 349–369. — ISBN 978-1-4503-8383-7.

[4] C. D. Thompson (1980). A complexity theory for VLSI (PDF) (Thesis) [англ.]. Carnegie-Mellon University. Дата обращения 2024-06-01.

[5] F. Thomson Leighton (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis) [англ.]. MIT Press. ISBN 0-262-12104-2. Дата обращения 2024-06-01.

[6] Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations [англ.]. pp. 81—88. Дата обращения 2024-06-01. |access-date= требует |url= (справка)

[7] 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. Дата обращения 2024-06-01. |access-date= требует |url= (справка)

[8] Jyothi, Sangeetha Abdu. Измерение пропускной способности топологий сетей дата-центров // The 2014 ACM international conference on Measurement and modeling of computer systems : [англ.] / Sangeetha Abdu Jyothi, Ankit Singla, P. Brighten Godfrey … [et al.]. — New York, NY, USA : Association for Computing Machinery, 16 июня 2014. — P. 597–598. — ISBN 978-1-4503-2789-3. — doi:10.1145/2591971.2592040.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Пропускная способность бисекции

Расчёт пропускной способности бисекции

Значение пропускной способности бисекции

Примечания

Категории