Пропускная способность пополам

В компьютерных сетях, если сеть разделенная пополам на два раздела, полоса пропускания пополам топологии сети - это полоса пропускания, доступная между двумя разделами. Деление пополам должно быть выполнено таким образом, чтобы полоса пропускания между двумя разделами была минимальной. Пропускная способность бисекции дает истинную пропускную способность, доступную для всей системы. Пропускная способность с разделением пополам составляет узкое место всей сети. Таким образом, полоса пропускания, разделенная пополам, представляет характеристики пропускной способности сети лучше, чем любой другой показатель.

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

Деление пополам сети линейного массива

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

Деление кольцевой сети пополам

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

Деление древовидной сети пополам

Для топологии Mesh с n узлами, $n\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{n\}\}\}$ссылки должны быть разбиты на разделите сеть пополам, так что пропускная способность пополам равна полосе пропускания $n\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{n\}\}\}$ссылок.

Деление двумерной ячеистой сети пополам

Для топологии Гиперкуб с n узлами, n / 2 ссылки должны быть разорваны, чтобы разделить сеть пополам, поэтому полоса пропускания пополам - это пропускная способность n / 2 ссылок.

Деление сети гиперкуба пополам

Теоретическое обоснование важности этого показателя производительности сети было разработано в исследовании доктора философии Кларка Томборсона (ранее Кларка Томпсона). Томборсон доказал, что важные алгоритмы сортировки, быстрое преобразование Фурье и умножение матрицы на матрицу становятся ограниченными по обмену данными - в отличие от ЦП или памяти - на компьютерах с недостаточной шириной деления пополам. Ф. Исследования Томсона Лейтона ужесточили слабые ограничения Томборсона на ширину деления пополам важного в вычислительном отношении варианта графа Де Брейна, известного как граф тасования-обмена. На основе анализа Билла Далли задержки, средней пропускной способности и пропускной способности активных точек m-арных n-кубических сетей для различных m, можно заметить, что низкоразмерные сети по сравнению с высокопроизводительными размерные сети (например, двоичные n-кубы) с одинаковой шириной биссекции (например, tori ) имеют меньшую задержку и более высокую пропускную способность горячих точек.

1. ^John L. Хеннесси и Дэвид А. Паттерсон (2003). Компьютерная архитектура: количественный подход (Третье изд.). Издательство Morgan Kaufmann Publishers, Inc. стр. 789. ISBN 978-1-55860-596-1.
2. ^ Солихин, Ян (2016). Основы параллельной многоядерной архитектуры. CRC Press. С. 371–381. ISBN 9781482211191.
3. ^C. Д. Томпсон (1980). Теория сложности для СБИС (PDF) (Диссертация). Университет Карнеги-Меллона.
4. ^Ф. Томсон Лейтон (1983). Проблемы сложности в СБИС: Оптимальные схемы для графа случайного обмена и других сетей (Диссертация). MIT Press. ISBN 0-262-12104-2.
5. ^Кларк Томпсон (1979). Площадь-время для СБИС. Proc. Caltech Conf. по системам СБИС и вычислениям. С. 81–88.
6. ^Билл Далли (1990). «Анализ производительности k-арных и n-кубических сетей межсоединений». Транзакции IEEE на компьютерах. 39 (6): 775–785. CiteSeerX 10.1.1.473.5096. doi :10.1109/12.53599.

.