Топология ВС
Структура связи между элементами системы называется топологией системы.
Состоит из: каналов и узлов
Смежные узлы – узлы, которые связаны при помощи канала.
(Как правило, рассматривают как однонаправленный, т.е. есть «узел-приёмник» и «узел-источник». Если узел – приёмо-источник, то связь осуществляется посредством 2х каналов)
Рассматривают 2 конфигурации связи:
-
Статическую (связи фиксированные, заданные до начала вычислений) -
Динамическую (структура связи может меняться в процессе работы)
Статические топологии
К статическим топологиям CMC относят такие, где между двумя узлами возможен только один прямой фиксированный путь, то есть статические топологии не предполагают наличия в сети коммутирующих устройств. Если же такие устройства имеются, то используются они только перед выполнением конкретной задачи, а в процессе всего времени вычислений топология CMC остается неизменной.
Из возможных критериев классификации статических сетей чаще всего выбирают их размерность. С этих позиций различают:
- одномерные топологии (линейный массив);
- двумерные топологии (кольцо, звезда, дерево, решетка, систолический массив);
- трехмерные топологии (полносвязная топология, хордальное кольцо);
- гиперкубическую топологию.
Ниже рассматриваются основные виды статических топологий CMC без акцентирования внимания на какой-либо их классификации, поскольку этот момент для поставленных в учебнике целей несущественен.
Линейная топология
В простейшей линейной топологии узлы сети образуют одномерный массив и соединены в цепочки (рис. 12.9). Линейная топология характеризуется следующими параметрами: D - N - 1; d =2; I = N-1; В = 1.
Рис. 12.9. Линейная топология
Линейная топология не обладает свойством полной симметричности, поскольку узлы на концах цепочки имеют только одну коммуникационную линию, то есть их порядок равен 1, в то время как порядок остальных узлов равен 2. Время пересылки сообщения зависит от расстояния между узлами, а отказ одного из них способен привести к невозможности пересылки сообщения. По этой причине в линейных CMC используют отказоустойчивые узлы, которые при отказе изолируют себя от сети, позволяя сообщению миновать неисправный узел.
Кольцевые топологии
Стандартная кольцевая топология представляет собой линейную цепочку, концы которой соединены между собой (рис, 12.10, а). В зависимости от числа каналов между соседними узлами (один или два) различают однонаправленные и двунаправленные кольца. Кольцевая топология характеризуется следующими параметрами:
Кольцевая топология, по сравнению с линейной, традиционно была менее популярной, поскольку добавление или удаление узла требует демонтажа сети.
Один из способов разрешения проблемы большого диаметра кольцевой сети -добавление линий связи в виде хорд, соединяющих определенные узлы кольца. Подобная топология носит название хордальной. Если хорды соединяют узлы с
шагом 1 или N/2-1,диаметр сети уменьшается вдвое. На рис. 12.10,6 показана хор-
дольная кольцевая сеть с шагом 3.
В качестве практических примеров для топологии кольца следует назвать сети Token Ring, разработанные фирмой IBM, а также вычислительные системы KSR1 и SCI.
Дальнейшее увеличение порядка узлов позволяет добиться еще большего сокращения тракта передачи сообщения. Примером такой топологии может служить показанная на рис. 12.10, в топология с циклическим сдвигом связей. Здесь стандартная кольцевая топология с N узлами дополнена соединениями между всеми узлами i и j, для которых |i-j\ совпадает с целой степенью числа 2. Алгоритмы маршрутизации для подобной сети чрезвычайно эффективны, однако порядок узлов по мере разрастания сети увеличивается.
Звездообразная топология
Звездообразная сеть объединяет множество узлов первого порядка посредством специализированного центрального узла - концентратора (рис. 12.11). Топология характеризуется такими параметрами: 
Рис. 12.11. Звездообразная топология
Звездообразная организация узлов и соединений редко используется для объединения процессоров многопроцессорной ВС, но хорошо работает, когда поток информации идет от нескольких вторичных узлов, соединенных с одним первичным узлом, например при подключении терминалов. Общая пропускная способность сети обычно ограничивается быстродействием концентратора, аналогично тому, как сдерживающим элементом в одношинной топологии выступает шина. По производительности эти топологии также идентичны. Основное преимущество звездообразной, схемы в том, что конструктивное исполнение узлов на концах сети может быть очень простым.
Древовидные топологии
Еще одним вариантом структуры CMC является древовидная топология (рис. 12.12, а). Сеть строится по схеме так называемого строго двоичного дерева, где каждый узел более высокого уровня связан с двумя узлами следующего по порядку более низкого уровня. Узел, находящийся на более высоком уровне, принято называть родительским, а два подключенных к нему нижерасположенных узла — дочерними. В свою очередь, каждый дочерний узел выступает в качестве родительского для двух узлов следующего более низкого уровня. Отметим, что каждый узел связан только с двумя дочерними и одним родительским. Если h — высота дерева (количество уровней в древовидной сети), определяемая как max [log2 N], то такую сеть можно охарактеризовать следующими параметрами: D=2(h- 1);d=3;l=N- 1; В = 1. Так, вычислительная система из 262 144 узлов при решетчатой топологии (немного забегаем вперед) будет иметь диаметр 512, а в случае строго бинарного дерева — только 36. Топология двоичного дерева была использована в мультипроцессорной системе DADO из 1023 узлов, разработанной в Колумбийском университете.
Рис. 12.12. Древовидная топология: a - стандартное дерево; б - "толстое" дерево
При больших объемах пересылок между несмежными узлами древовидная топология оказывается недостаточно эффективной, поскольку сообщения должны проходить через один или несколько промежуточных звеньев. Очевидно, что на более высоких уровнях сети вероятность затора из-за недостаточно высокой пропускной способности линий связи выше. Этот недостаток устраняют с помощью топологии, называемой "толстым" деревом (рис. 12.12, б).
Идея "толстого" дерева состоит в увеличении пропускной способности коммуникационных линий на прикорневых уровнях сети. С этой целью на верхних уровнях сети родительские и дочерние узлы связывают не одним, а несколькими каналами, причем чем выше уровень, тем больше число каналов. На рисунке это отображено в виде множественных линий между узлами верхних уровней. Топология «толстого» дерева реализована в вычислительной системе СМ-5.
Решетчатые топологии
Поскольку значительная часть научно-технических задач связана с обработкой массивов, вполне естественным представляется стремление учесть это и в топологии ВС, ориентированных на подобные задачи. Такие топологии относят к решетчатым (mesh), а их конфигурация определяется видом и размерностью массива
Рис. 12.13. Решётчатые топологии: а — плоская; б — цилиндрическая; а-г — тороидальная; д — витая тороидальная
(г) выкинул. Это было просто чёрное пятно
Простейшими примерами для одномерных массивов могут служить цепочка и кольцо. Для двумерных массивов данных наиболее подходит топология плоской прямоугольной матрицы узлов, каждый из которых соединен с ближайшим соседом (рис. 12.13, а). Такая сеть размерности 
имеет следующие характеристики; 
Если провести операцию свертывания (wraparound) плоской матрицы, соединив информационными трактами одноименные узлы левого и правого столбцов или одноименные узлы верхней и нижней строк плоской матрицы, то из плоской конструкции получаем топологию типа цилиндра (рис. 12.13,6). В топологии цилиндра каждый ряд (или столбец) матрицы представляет собой кольцо. Если одновременно произвести свертывание плоской матрицы в обоих направлениях, получим тороидальную топологию сети (рис. 12.13, в). Двумерный тор на базе решетки обладает следующими параметрами:
Объемный вид тороидальной топологии для массива размерности 4x8 показан на рис. 12.13, г.
Помимо свертывания к плоской решетке может быть применена операция скручивания (twisting). Суть этой операции состоит в том, что вместо колец все узлы объединяются в разомкнутую или замкнутую спираль, то есть узлы, расположенные с противоположных краев плоской решетки, соединяются с некоторым сдвигом. Если горизонтальные петли объединены в виде спирали, образуется так называемая сеть типа ILLI АС. На рис. 12.13, д показана подобная конфигурация CMC, соответствующая хордальной сети четвертого порядка и характеризуемая следующими метриками: D = т- 1; d = 4; / = 2N; В = 2т.
Следует упомянуть и трехмерные сети. Один из вариантов, реализованный в архитектуре суперЭВМ Cray T3D, представляет собой трехмерный тор, образованный объединением процессоров в кольца по трем координатам: х,у и z.
Примерами ВС, где реализованы различные варианты решетчатых топологий, могут служить: ILLIAC IV, МРР, DAP, CM-2, Paragon и др.
Полносвязная топология
В полносвязной топологии (рис. 12.14), известной также под названием топологии «максимальной гр у ппировки » или «топологии клика» (clique - полный подграф [ма-тем.]), каждый узел напрямую соединен со всеми остальными узлами сети. Сеть, состоящая из N узлов, имеет следующие параметры:
Если размер сети велик, топология становится дорогостоящей и трудно реализуемой. Более того, топология максимальной группировки не дает существенного улучшения производительности, поскольку каждая операция пересылки требует, чтобы узел проанализировал состояние всех своих N— 1 входов. Для ускорения этой операции необходимо, чтобы все входы анализировались параллельно, что, в свою очередь, усложняет конструкцию узлов.
Топология гиперкуба
При объединении параллельных процессоров весьма популярна топология гиперкуба, показанная на рис. 12.15. Линия, соединяющая два узла (рис. 12.15, а).
Тут (в Цилькере, страница 525 файла .pdf) ещё «Топология k-ичного п-куба», но на лекции об этом речь не заходила
Рисунок 12.17, а явно кривой, но я скопировал из учебника
