Выбор архитектуры, состава и топологии вычислительной системы и сети
Сама идея многопроцессорной вычислительной системы предполагает обмен данными между компонентами этой ВС. Коммуникационная система ВС представляет собой сеть, узлы которой связаны трактами передачи данных — каналами. В роли узлов сети могут выступать процессоры, банки памяти, устройства ввода/вывода, коммутаторы либо несколько перечисленных элементов, объединенных в группу. Организация внутренних коммуникаций вычислительной системы называется топологией.
Топологию сети определяет множество узлов N, объединенных множеством каналов C. Связь между узлами обычно реализуется по двухточечной схеме (point-to-point). Любые два узла, связанные каналом связи, называют смежными узлами или соседями. Каждый канал c = (x, y) ∈C соединяет один узел-источник (sourcenode) x с одним узлом-получателем (recipientnode) y, где x, y ∈ N. Часто пары узлов соединяют два канала — по одному в каждом направлении. Канал характеризуют шириной wc — числом сигнальных линий; частотой fc — скоростью передачи битов по каждой сигнальной линии; задержкой tc — временем пересылки бита из узла x в узел y. Для большинства каналов задержка находится в прямой зависимости от физической длины линии связи l c и скорости распространения сигнала v: l c = v tc. Полоса пропускания канала bc определяется выражением bc = wcfc. Классификация коммуникационных сетей
Классификацию сетей обычно производят по следующим признакам:
|
|
|
-стратегия синхронизации;
-стратегия коммутации;
-стратегия управления;
-топология.
Классификация по стратегии синхронизации. Две возможных стратегии синхронизации операций в сети — это синхронная и асинхронная. В синхронных сетях все действия жестко согласованы во времени, что обеспечивается за счет единого генератора тактовых импульсов (ГТИ), сигналы которого одновременно транслируются во все узлы. В асинхронных сетях единого генератора нет, а функции синхронизации распределены по всей системе, причем в разных частях сети часто используются локальные ГТИ. Синхронные сети по сравнению с асинхронными обычно медленнее, но в них легче предотвращаются конфликтные ситуации.
По стратегии коммутации различают сети с коммутацией соединений и сети с коммутацией пакетов. Как в первом, так и во втором варианте информация пересылается в виде пакета. Пакет представляет собой группу битов, для обозначения которой применяют также термин сообщение.
В сетях с коммутацией соединений еще до начала пересылки сообщения формируется тракт от узла-источника до узла-получателя (путем соответствующей установки коммутирующих элементов сети). Этот тракт сохраняется вплоть до доставки пакета в пункт назначения. Пересылка сообщений между определенной парой узлов производится всегда по одному и тому же маршруту.
|
|
|
Сети с коммутацией пакетов предполагают, что сообщение самостоятельно находит свой путь к месту назначения. В отличие от сетей с коммутацией соединений, маршрут от исходного пункта к пункту назначения каждый раз может быть иным. Пакет последовательно проходит через узлы сети. Очередной узел запоминает принятый пакет в своем буфере временного хранения, анализирует его и решает, что с ним делать дальше. В зависимости от загруженности сети принимается решение о возможности немедленной пересылки пакета к следующему узлу и о дальнейшем маршруте следования пакета на пути к цели. Если все возможные тракты для перемещения пакета к очередному узлу заняты, в буфере узла формируется очередь пакетов, которая «рассасывается» по мере освобождения линий связи между узлами (при насыщении очереди, согласно одной из стратегий маршрутизации, может произойти так называемый «сброс хвоста» (taildrop) — отказ от вновь поступающих пакетов). Хотя сети с коммутацией пакетов по сравнению с сетями на базе коммутации соединений более эффективно используют ресурсы сети, время доставки сообщения в них сильно зависит от переменных задержек в перемещении пакетов.
|
|
|
Коммуникационные сети можно также классифицировать по тому, как в них организовано управление. В некоторых сетях, особенно с коммутацией соединений, принято централизованное управление (рисунок 9). Процессоры посылают запрос на обслуживание в единый контроллер сети, который производит арбитраж запросов с учетом заданных приоритетов и устанавливает нужный маршрут. К данному типу следует отнести сети с шинной топологией. Процессорные матрицы также строятся как сети с централизованным управлением, которое осуществляется сигналами от центрального процессора. Приведенная схема применима и к сетям с коммутацией пакетов. Здесь маршрут определяется адресом узла назначения, хранящимся в заголовке пакета. Большинство из серийно выпускаемых ВС имеют именно этот тип управления.
|
Рисунок 9. Структура сети с централизованным управлением
В схемах с децентрализованным управлением функции управления распределены по узлам сети. Вариант с централизацией проще реализуется, но расширение сети в этом случае связано со значительными трудностями. Децентрализованные сети в плане подключения дополнительных узлов значительно гибче, однако взаимодействие узлов в таких сетях существенно сложнее.
|
|
|
В ряде сетей связь между узлами обеспечивается посредством множества коммутаторов, но существуют также сети с одним коммутатором. Наличие большого числа коммутаторов ведет к увеличению времени передачи сообщения, но позволяет использовать простые переключающие элементы. Подобные сети обычно строятся как многоступенчатые.
Топологию коммуникационной сети (организацию внутренних коммуникаций многопроцессорной вычислительной системы) можно рассматривать как функцию отображения множества процессоров (ПР) и банков памяти (БП) на то же самое множество ПР и БП. Иными словами, топология описывает, каким образом процессоры и банки памяти могут быть соединены с другими процессорами и банками памяти.
В основу системы классификации обычно кладут разбиение всех возможных топологий на статические и динамические. В сетях со статическими топологиями структура связей фиксирована. В сетях с динамической топологией конфигурация соединений в процессе вычислений может быть оперативно изменена (с помощью программных средств).
Узел в сети может быть терминальным, то есть источником или приемником данных, коммутатором, пересылающим информацию с входного порта на выходной, или совмещать обе роли. В сетях с непосредственными связями (directnetworks) каждый узел одновременно является как терминальным узлом, так и коммутатором, и сообщения пересылаются между терминальными узлами напрямую. В сетях с косвенными связями (indirectnetworks) узел может быть либо терминальным, либо коммутатором, но не одновременно, поэтому сообщения передаются опосредовано, с помощью выделенных коммутирующих узлов. (В дальнейшем условимся называть оба варианта «прямыми» и «косвенными» сетями, а терминальный узел будем называть «терминалом».) Существуют также такие топологии, которые нельзя однозначно причислить ни к прямым, ни к косвенным. Любую прямую сеть можно изобразить в виде косвенной, разделив каждый узел на два — терминальный узел и узел коммутации. Современные прямые сети реализуются именно таким образом — коммутатор отделяется от терминального узла и помещается в выделенный маршрутизатор. Основное преимущество прямых сетей в том, что коммутатор может использовать ресурсы терминальной части своего узла. Это становится существенным, если учесть, что, как правило, последний включает в себя вычислительную машину или процессор.
Схема классификации коммуникационных сетей на основе их топологии показана на рисунке 10.
|
Рисунок 10. Классификация коммуникационных сетей по топологии
Чтобы охарактеризовать сеть, обычно используют следующие параметры:
-размер сети;
-число связей;
-диаметр сети;
-степень узла;
-пропускная способность сети;
-задержка сети;
-связность сети;
-ширина бисекции сети;
-полоса бисекции сети.
Размер сети (N) численно равен количеству узлов, объединяемых сетью. Число связей (I) — это суммарное количество каналов между всеми узлами сети. Иногда этот параметр называют стоимостью сети. В плане стоимости лучшей следует признать ту сеть, которая требует меньшего числа связей.
Диаметр сети (D), называемый также коммуникационным расстоянием, определяет минимальный путь, по которому проходит сообщение между двумя наиболее удаленными друг от друга узлами сети. Путь в сети — это упорядоченное множество каналов P = {c1, c2, ..., cn}, по которым данные от узла-источника, последовательно переходя от одного промежуточного узла к другому, поступают на узел-получатель. Для обозначения отрезка пути между парой смежных узлов применяют термин переход (в живой речи также «транзит» и «хоп»). Минимальный путь от узла x до узла y — это путь с минимальным числом переходов. Если обозначить число переходов в минимальном пути от узла x до узла y через H(x, y), то диаметр сети D — это наибольшее значение H(x, y) среди всех возможных комбинаций x и y. Так, в цепочке из четырех узлов наибольшее число переходов будет между крайними узлами, и «диаметр» такой цепочки равен трем. С возрастанием диаметра сети увеличивается общее время прохождения сообщения, поэтому разработчики ВС стремятся по возможности обходиться меньшим диаметром. Степень узла (d). Каждый узел сети x связан с прочими узлами множеством каналов Cx=CIx∪COx, где CIx — множество входных каналов, а COx — множество выходных каналов.
Степень узла x представляет собой сумму числа входных и выходных каналов узла, то есть она равна числу узлов сети, с которыми данный узел связан напрямую. Например, в сети, организованной в виде матрицы, где каждый узел связан только с ближайшими соседями (слева, справа, сверху и снизу), степень узла равна четырем. Увеличение степени узлов ведет к усложнению коммутационных устройств сети и, как следствие, к дополнительным задержкам в передаче сообщений. С другой стороны, повышение степени узлов позволяет реализовать топологии, имеющие меньший диаметр сети, и тем самым сократить время прохождения сообщения. Разработчики ВС обычно отдают предпочтение таким топологиям, где степень всех узлов одинакова, что позволяет строить сети по модульному принципу.
Пропускная способность сети (W) характеризуется количеством информации, которое может быть передано по сети в единицу времени. Обычно измеряется в мегабайтах в секунду или гигабайтах в секунду без учета издержек на передачу избыточной информации, например, битов паритета.
Задержка сети (T) — это время, требуемое на прохождение сообщения через сеть. В сетях, где время передачи сообщений зависит от маршрута, говорят о минимальной, средней и максимальной задержках сети.
Связность сети (Q) можно определить, как минимальное число параллельных трактов между любой парой узлов. Связность сети характеризует устойчивостьсети к повреждениям, то есть ее способность обеспечивать функционирование ВС при отказе компонентов сети.
Ширина бисекции сети (B). Для начала определим понятие среза сети С(N1, N2) как множество каналов, разрыв которых разделяет множество узлов сети N на два непересекающихся подмножества узлов N1 и N2. Каждый элемент С(N1, N2) — это канал, соединяющий узел из N1 с узлом из N2. Бисекция сети — это срез сети, разделяющий примерно пополам, то есть так, что |N2|≤|N1|≤|N2|+1. Ширину бисекции B характеризуют минимальным числом каналов, разрываемых при всех возможных бисекциях сети:
Ширина бисекции позволяет оценить число сообщений, которые могут быть переданы по сети одновременно, при условии, что это не вызовет конфликтов из-за попытки использования одних и тех же узлов или линий связи.
Полоса бисекции сети (b) — это наименьшая полоса пропускания по всем возможным бисекциям сети. Она характеризует пропускную способность тех линий связи, которые разрываются при бисекции сети, и позволяет оценить наихудшую пропускную способность сети при попытке одномоментной передачи нескольких сообщений, если эти сообщения должны проходить из одной половины сети в другую. Для сетей с одинаковой шириной полосы bc во всех каналах справедливо: b = bc × B. Малое значение полосы бисекции свидетельствует о возможности конфликтов при одновременной пересылке нескольких сообщений.
К статическим топологиям относят такие, где между двумя узлами возможен только один прямой фиксированный путь, то есть статические топологии не предполагают наличия в сети коммутирующих устройств. Если же такие устройства имеются, то используются они только перед выполнением конкретной задачи, а в процессе всего времени вычислений топология остается неизменной. Из возможных показателей классификации статических сетей чаще всего выбирают их размерность. С этих позиций различают: „ одномерные топологии (линейный массив);
-двумерные топологии (кольцо, звезда, дерево, решетка, систолический массив);
-трехмерные топологии (полносвязная топология, хордальное кольцо);
-гиперкубическую топологию.
Ниже рассматриваются основные виды статических топологий.
Линейная топология В линейной топологии узлы сети образуют одномерный массив и соединены в цепочку (рисунок 11). Линейная топология характеризуется следующими параметрами: D = N – 1; d = 1 (для крайних узлов) и d = 2 (для всех остальных узлов); I = N − 1; B = 1.
|
Рисунок 11. Линейная топология
Линейная топология не обладает свойством полной симметричности, поскольку узлы на концах цепочки имеют только одну коммуникационную линию, то есть их степень равна 1, в то время как степень остальных узлов равна 2. Время пересылки сообщения зависит от расстояния между узлами, а отказ одного из них способен привести к невозможности пересылки сообщения. По этой причине в линейных сетях используют отказоустойчивые узлы, которые при отказе изолируют себя от сети, позволяя сообщению миновать неисправный узел. Данный вид топологии наибольшее распространение нашел в системах класса SIMD.
Кольцевые топологии Стандартная кольцевая топология представляет собой линейную цепочку, концы которой соединены между собой (рисунок 12). В зависимости от числа каналов между соседними узлами (один или два) различают однонаправленные и двунаправленные кольца. Кольцевая топология характеризуется следующими параметрами: (для двунаправленного кольца) и D = N – 1 (для однонаправленного кольца); d = 2; I = N; B = 2. Введение одного дополнительного канала вдвое уменьшает диаметр и увеличивает ширину бисекции. Кольцевая топология, по сравнению с линейной, менее популярна, поскольку добавление или удаление узла требует демонтажа сети. Тем не менее она нашла применение в ряде ВС, например, в вычислительных системах KSR-1 и SCI.
1. 
|
Рисунок 12. Кольцевая топология: а — стандартное представление; б — альтернативное представление
Дата добавления: 2019-08-31; просмотров: 328; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!