Коммуникационные системы

Коммуникационная система – важнейший компонент параллельной системы, обеспечивающий передачу сообщений (или слов) между любой парой устройств системы: парой процессоров, процессором и памятью, памятью и накопителем на магнитных дисках и т.д.

Главный параметр коммуникационной системы – топология коммуникаций, т.е. структура (схема) связей между основными элементами параллельной системы: процессорами, модулями памяти, накопителями на магнитных дисках, устройствами ввода-вывода данных и т.д., определяемая графом, который состоит из точек, соответствующих коммутаторам, и каналов (шин), связывающих коммутаторы между собой и основными элементами параллельной системы. Коммутатор – это электронная схема, содержащая несколько входов и несколько выходов и обеспечивающая передачу некоторого сообщения с одного направления на другое направление. Когда на вход коммутатора приходит сообщение, определенные биты в этом сообщении используются для выбора выхода коммутатора, в который и будет отправлено сообщение. Размер сообщения может составлять 2 или 4 байта, но может быть значительно больше, например 8 Кбайт. Любой коммутатор вносит определенную задержку в передачу сообщения и имеет ограниченную пропускную способность. Каналы связи служат для передачи сообщений. Каналы могут быть электрическими и оптоволоконными, последовательными и параллельными, симплексными (передавать биты только в одном направлении), полудуплексными (передавать биты в обоих направлениях, но не одновременно) и дуплексными (передавать биты в обоих направлениях одновременно). Любой канал связи имеет ограниченную пропускную способность, зависящую от способа кодирования битов и длины канала.

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

Топология коммуникационной системы. Топология определяет, как расположены каналы связи и коммутаторы. Топологию можно изображать в виде графов, в которых дуги соответствуют каналам связи, а узлы – коммутаторам. С каждым узлом в сети (или в соответствующем графе) связан определенный ряд каналов связи. Математики называют число каналов степенью узла, инженеры – коэффициентом разветвления. Чем больше степень, тем больше вариантов маршрута и тем выше отказоустойчивость. Если каждый узел содержит k дуг, то можно построить сеть сообщений так, чтобы она оставалась полносвязной, даже если k -1 каналов повреждены.

Следующее свойство сети межсоединений – это ее диаметр. Если расстоянием между двумя узлами мы будем считать число дуг, которые нужно пройти, чтобы попасть из одного узла в другой, то диаметром графа будет расстояние между двумя узлами, которые расположены дальше всех друг от друга. Диаметр сети определяет самую большую задержку при передаче от одного процессора к другому или от процессора к памяти, поскольку каждая пересылка через канал связи занимает определенное количество времени. Чем меньше диаметр, тем выше производительность. Также имеет большое значение среднее расстояние между двумя узлами, поскольку от него зависит среднее время передачи.

Еще одно важное свойство сети соединений – это ее производительность, т.е. количество данных, которое она способна передавать в секунду. Очень важная характеристика – бисекционная пропускная способность. Чтобы вычислить это число, нужно разделить сеть межсоединений на две равные (с точки зрения узлов) несвязанные части путем удаления ряда дуг из графа. Затем нужно вычислить общую пропускную способность дуг, которые мы удалили. Существует множество способов разделить сети межсоединений на две равные части. Бисекционная пропускная способность – минимальная из всех возможных. По мнению разработчиков, бисекционная пропускная способность – это самая важная характеристика сети. Часто основная цель при разработке сети – сделать бисекционную пропускную способность максимальной.

Сети можно характеризовать по их размерности. Размерность определяется по числу возможных вариантов перехода из исходного пункта в пункт назначения. Если выбора нет (т.е. существует только один путь из каждого исходного пункта в каждый конечный пункт), то сеть нульмерная. Если есть два возможных варианта (например, если можно пойти либо направо, либо налево), то сеть одномерна. Если есть две оси и пакет может направиться направо или налево, либо вверх или вниз, то такая сеть двумерна и т.д.

На рис.1.5 показано несколько топологий. Здесь изображены только каналы связи (это линии) и коммутаторы (это точки). Модули памяти и процессоры (они на рисунке не показаны) подсоединяются к коммутаторам через интерфейсы. На рис.1.5,a изображена нульмерная топология – полное межсоединение. Здесь каждый узел непосредственно связан с каждым имеющимся узлом. В такой разработке пропускная способность между двумя секторами максимальна, диаметр минимален, а отказоустойчивость очень высока (даже при утрате шести каналов связи система все равно будет полностью взаимосвязана). Однако для k узлов требуется k (k -1)/2 каналов, а это совершенно неприемлемо для больших значений k. Кольцо (рис.1.5,б) – это одномерная топология, поскольку каждый отправленный пакет может пойти направо или налево. Решетка или сетка (рис.1.5,в) – это двумерная топология, которая применяется во многих коммерческих системах. Она отличается регулярностью и применима к системам большого размера, а диаметр составляет квадратный корень от числа узлов (т.е. при расширении системы диаметр увеличивается незначительно). Двойной тор (рис.1.5,г) является разновидностью решетки. Эта решетка, у которой соединены края. Она характеризуется большей отказоустойчивостью и меньшим диаметром, чем обычная решетка, поскольку теперь между двумя противоположными узлами всего один транзитный участок. Куб (рис. 1.5,д)- это правильная трехмерная топология. На рисунке изображен куб 2×2×2, но в общем случае он может быть k × k × k. На рис. 1.5,ж показан четырехмерный куб, полученный из двух трехмерных кубов, которые связаны между собой. Можно сделать пятимерный куб, соединив вместе 4 четырехмерных куба. Чтобы получить 6 измерений, нужно продублировать блок из 4 кубов и соединить соответствующие узлы и т.д.; n -мерный куб называется гиперкубом. Эта топология используется во многих компьютерах параллельного действия, поскольку ее диаметр находится в линейной зависимости от размерности. Другими словами диаметр - это логарифм по основанию 2 от числа узлов, поэтому 10-мерный гиперкуб имеет 1024 узла, но диаметр равен всего 10, что дает очень незначительные задержки при передаче данных. Отметим, что решетка 32×32, которая также содержит 1024 узла, имеет диаметр 62, что более чем в шесть раз превышает диаметр гиперкуба. Однако, чем меньше диаметр гиперкуба, тем больше разветвлений и число каналов (и, следовательно, тем выше стоимость). Тем не менее, в системах с высокой производительностью чаще всего используется именно гиперкуб.

Способы коммутации. Сеть состоит из коммутаторов и шин, соединяющих их. На рис. 1.6 изображена небольшая сеть межсоединений с четырьмя коммутаторами. В данном случае каждый коммутатор имеет 4 входных порта и 4 выходных порта. Кроме того, каждый коммутатор содержит несколько процессоров и схемы соединения (на рисунке они показаны не полностью). Задача коммутатора – принимать пакеты, которые приходят на любой входной порт, и отправлять пакеты из соответствующих выходных портов. Каждый выходной порт связан с входным портом другого коммутатора через последовательный или параллельный канал (см. рис. 1.6). Существуют специальные сигналы для управления каналом.

Существует несколько стратегий переключения коммутаторов. Первая из них - коммутация каналов. Перед тем как послать сообщение, весь путь от начального до конечного пункта резервируется заранее. Все порты затребованы заранее, поэтому, когда начинается процесс передачи, все необходимые ресурсы гарантированно доступны, и биты могут на полной скорости перемещаться от исходного пункта через все коммутаторы к пункту назначения. На рис. 1.6 показана коммутация каналов, где резервируется канал от процессора 1 к процессору 2 (черная жирная линия). Здесь резервируются три входных и три выходных порта. Недостаток такого метода состоит в том, что требуется предварительное планирование и любая передача по этому каналу запрещена, даже если сообщение еще не передавалось.

Вторая стратегия - коммутация с промежуточным хранением. Здесь не требуется предварительного резервирования. Из исходного пункта посылается сообщение к первому коммутатору, где оно хранится целиком. Ясно, что емкость буфера любого коммутатора ограничена, поэтому любое сообщение принято разделять на пакеты. Каждый из пакетов имеет адрес конечного пункта назначения и часть сообщения, не превышающую емкости буфера. При этом каждый пакет занимает не более одного буфера в коммутаторе и, если сообщение не может разместиться в буферах коммутатора, то процессор приостанавливает передачу сообщения до момента освобождения буфера. На рис. 1.7 исходным пунктом является процессор 1, а весь пакет, который направляется в процессор 2, сначала сохраняется внутри коммутатора А. Затем этот пакет перемещается в коммутатор С, как показано на рис. 1.7,б. Затем весь пакет целиком перемещается в коммутатор D (рис. 1.7,в). Наконец, пакет доходит до пункта назначения - до процессора 2. Отметим, что никакого предварительного резервирования канала не требуется.

Коммутаторы с промежуточным хранением должны отправлять пакеты в буфер, поскольку, когда исходный пункт (например процессор, память или коммутатор) выдает пакет, требующийся выходной порт может быть в данный момент занят передачей другого пакета. Если бы не было буферизации, входящие пакеты, которым нужен занятый в данный момент выходной порт, пропадали бы. Применяется три метода буферизации. При буферизации на входе один или несколько буферов связываются с каждым входным портом в форме очереди типа FIFO (первым вошел, первым вышел). Если пакет в начале очереди нельзя передать по причине занятости нужного выходного порта, этот пакет просто ждет своей очереди. Однако если пакет ожидает, когда освободится выходной порт, то пакет, идущий за ним, тоже не может передаваться, даже если нужный ему порт свободен. Ситуация называется блокировкой начала очереди. Проиллюстрируем ситуацию на примере. Представим дорогу из двух рядов. Вереница машин в одном из рядов не может двигаться дальше, поскольку первая машина в этом ряду хочет повернуть налево, но не может из-за движения машин другого ряда. Даже если второй и всем следующим за ней машинам нужно ехать прямо, первая машина в ряду препятствует их движению. Проблему можно устранить с помощью буферизации на выходе. В этой системе буферы связаны с выходными портами. Биты пакета по мере прибытия сохраняются в буфере, который связан уже с нужным выходным портом. Поэтому пакеты, направленные в порт m, не могут блокировать пакеты, направленные в порт n.

И при буферизации на входе, и при буферизации на выходе с каждым портом связано определенное количество буферов. Если места недостаточно для хранения всех пакетов, то какие-то пакеты придется выбрасывать. Чтобы разрешить эту проблему, можно использовать общую буферизацию, при которой один буферный пул динамически распределяется по портам по мере необходимости. Однако такая схема требует сложного управления, чтобы следить за буферами, и позволяет одному занятому соединению захватить все буферы, оставив другие соединения ни с чем. Кроме того, каждый коммутатор должен вмещать самый большой пакет и даже несколько пакетов максимального размера, а для этого потребуется снизить максимальный размер пакета.

Хотя метод коммутации с промежуточным хранением гибок и эффективен, здесь возникает проблемы возрастающей задержки при передаче данных по сети межсоединений. Предположим, что время, необходимое для перемещения пакета по одному участку занимает T нс. Чтобы переместить пакет из процессора 1 в процессор 2, нужно скопировать его 4 раза (в A, в C, в D и в процессор 2), поэтому задержка по сети составляет 4 T. Чтобы выйти из этой ситуации, нужно каждый пакет разделить на части и передавать короткие пакеты. Ясно, что чем меньше длина пакета, тем меньше задержка пакета в сети. Однако из-за наличия затрат на адресацию пакетов эффективная производительность сети всегда уменьшается с уменьшением длины пакета.

Алгоритмы выбора маршрута. В любой сети межсоединений размерностью один и выше можно выбирать, по какому пути передавать пакеты от одного узла к другому. Часто существует множество возможных маршрутов. Правило, определяющее, какую последовательность узлов должен пройти пакет при движении от исходного пункта к пункту назначения, называется алгоритмом выбора маршрута.

Хорошие алгоритмы выбора маршрута необходимы, поскольку часто свободными оказываются несколько путей. Хороший алгоритм поможет равномерно распределить нагрузку по каналам связи, чтобы полностью использовать имеющуюся в наличии пропускную способность. Кроме того, алгоритм выбора маршрута помогает избегать взаимоблокировки в сети межсоединений. Взаимоблокировка возникает в том случае, если при одновременной передаче нескольких пакетов ресурсы затребованы таким образом, что ни один из пакетов не может продвигаться дальше, и все они блокируются навечно. Пример тупиковой ситуации в сети с коммутацией каналов приведен на рис. 1.8.Тупиковая ситуация может возникать и в сети с пакетной коммутацией, но ее легче представить графически в сети с коммутацией каналов. Здесь каждый процессор пытается послать пакет процессору, находящемуся напротив него по диагонали. Каждый из них смог зарезервировать входной и выходной порты своего локального коммутатора, а также один входной порт следующего коммутатора, но он уже не может получить необходимый выходной порт на втором коммутаторе, поэтому он просто ждет, пока не освободится этот порт. Если все четыре процессора начинают этот процесс одновременно, то все они блокируются и сеть зависает.

Алгоритмы выбора маршрута можно разделить на две категории: маршрутизация от источника и распределенная маршрутизация. При маршрутизации от источника источник определяет весь путь по сети заранее. Этот путь выражается списком из номеров портов, которые нужно будет использовать в каждом коммутаторе по пути к пункту назначения. Если путь проходит через k коммутаторов, то первые k байтов в каждом пакете будут содержать k номеров выходных портов, 1 байт на каждый порт. Когда пакет доходит до коммутатора, первый байт отсекается и используется для определенного выходного порта. Оставшаяся часть пакета затем направляется в соответствующий порт. После каждого транзитного участка пакет становится на 1 байт короче, показывая новый номер порта, который нужно выбрать в следующий раз.

При распределенной маршрутизации каждый коммутатор сам решает, в какой порт отправить каждый приходящий пакет. Если выбор одинаков для каждого пакета, направленного к одному и тому же конечному пункту, то маршрутизация является статической. Если коммутатор при выборе принимает во внимание текущий трафик, то маршрутизация является адаптивной.

Популярным алгоритмом маршрутизации, который применяется для прямоугольных решеток с любым числом измерений и в котором никогда не возникает тупиковых ситуаций, является пространственная маршрутизация. В соответствии с этим алгоритмом пакет сначала перемещается вдоль оси x до нужной координаты, затем вдоль оси y до нужной координаты и т.д. Например, чтобы перейти из (3, 7, 5) в (6, 9, 8), пакет сначала должен переместиться из точки x =3 в точку x =6 через (4, 7, 5), (5, 7, 5) и (6, 7, 5). Затем он должен переместиться по оси y через (6, 8, 5) и (6, 9, 5). Наконец, он должен переместиться по оси z в (6, 9, 6), (6, 9, 7) и (6, 9, 8). Такой алгоритм предотвращает тупиковые ситуации.

Координатные коммутаторы. Самая простая схема соединения n процессоров с k блоками памяти – координатный коммутатор (рис.1.9).

Координатные коммутаторы используются на протяжении многих десятилетий для соединения группы входящих линий с рядом выходящих линий. В каждом пересечении горизонтальной (входящей) и вертикальной (исходящей) линии находится точка, которую можно открыть или закрыть в зависимости от того, нужно соединять горизонтальную и вертикальную линии или нет. На рис.1.9,а мы видим, что три узла закрыты, благодаря чему устанавливается связь между парами (процессор, память) (010, 000), (101, 101) и (110, 010) одновременно. Возможны другие комбинации.

Не лучшим свойством координатного коммутатора является то, что число узлов растет как n ² , При наличии 100 процессоров и 100 блоков памяти понадобится 10000 узлов. Это неприемлемо. Координатные коммутаторы применимы для систем небольшого размера. Основное достоинство координатного коммутатора – минимальное время чтения и записи слова.

Омега – коммутаторы. В основе омега-коммутатора лежит небольшой коммутатор 2x2 (рис.1.9,а). Этот коммутатор содержит два входа и два выхода. Сообщения, приходящие на любую из входных линий, могут переключаться на любую выходную линию. В нашем примере сообщения могут содержать четыре части (рис.1.9, б). Поле модуль М сообщает, какую память использовать. Поле адрес А определяет адрес в этом модуле памяти. В поле код операции КО содержится операция, например, READ или WRITE. Наконец, дополнительное поле значение С может содержать операнд, например, 32-битное слово, которое нужно записать при выполнении операции WRITE. Коммутатор анализирует поле модуль М и использует его для определения, через какую выходную линию нужно отправить сообщение: через X или через Y.

Коммутаторы 2x2 можно компоновать различными способами и получать многоступенчатые сети. Один из возможных вариантов – сеть омега (рис.1.10) Здесь соединены 8 процессоров с 8 модулями памяти, используя 12 коммутаторов. Для n процессоров и n модулей памятипонадобится (n /2)log₂ n коммутаторов, что намного меньше, чем n ² узлов.

Чтобы понять, как работает данная сеть, предположим, что процессору 011 нужно считать слово из модуля памяти 110. Процессор посылает сообщение READ, чтобы переключить коммутатор 1D, который содержит 110 в полемодуль М. Коммутатор берет первый (то есть крайний левый) бит от 110 и по нему узнает направление: 0 указывает на верхний выход, а 1 – на нижний. Поскольку в данном случае этот бит равен 1, сообщение отправляется через нижний выход в 2D. Все коммутаторы второй ступени, включая 2D, для определения направления используют второй бит. В данном случае он равен 1, поэтому сообщение отправляется через нижний выход в 3D, Затем проверяется третий бит. Он равен 0. Следовательно, сообщение переходит в верхний выход и прибывает в память 110, чего мы и добивались. Путь, пройденный данным сообщением, обозначен на рис.1.10 буквой а.

Как только сообщение пройдет через сеть, крайние левые биты номера модуля больше не требуются. Их можно использовать, записав туда номер входной линии, чтобы было известно, по какому пути посылать ответ. Для пути а входные линии – это 0 (верхний вход в 1D), 1 (нижний вход в 2D) и 1 (нижний вход в 3D) соответственно. При отправке ответа тоже используется 011, только теперь число читается справа налево.

В то время, как это все происходит, процессору 001 нужно записать слово в модуль памяти 001. Здесь происходит аналогичный процесс. Сообщение отправляется через верхний, верхний и нижний выходы соответственно. На рис.1.10 этот путь отмечен буквой b. Когда сообщение пребывает в пункт назначения, в поле модульсодержится 001. Это число показывает путь, который прошло сообщение. Поскольку эти два запроса используют совершенно разные коммутаторы, линии и модули памяти, они могут протекать параллельно.

Теперь рассмотрим, что произойдет, если процессору 000 одновременно с этим понадобился доступ к модулю памяти 110. Его запрос вступит в конфликт с запросом процессора 011 на коммутаторе 3D. Одному из них придется подождать. В отличие от координатного коммутатора, данная сеть – это блокируемая сеть. Не всякий набор запросов может передаваться одновременно. Конфликты могут возникать при использовании одного и того же коммутатора, а также между запросами, направленными к памяти, и ответами, исходящими из памяти.

Желательно равномерно распределить обращение к памяти по модулям. Один из возможных способов – использовать младшие биты в качестве номера модуля памяти. Рассмотрим адресное пространство с побайтовой адресацией для компьютера, который получает доступ к 32-битным словам. Два младших бита будут 00, но следующие три бита будут равномерно распределены. Если использовать эти три бита в качестве номера модуля памяти, последовательно адресуемые слова будут находиться в последовательных модулях. Система памяти, в которой последовательные слова находятся в разных модулях, называется расслоенной. Расслоенная система памяти доводит параллелизм до максимума, поскольку большая часть обращений к памяти – это обращения к последовательным адресам.

Можно разработать и неблокируемые сети, в которых существует несколько путей

от каждого процессора к каждому модулю памяти.

Дата добавления: 2015-07-20