Вопрос 34

Многомашинные вычислительны системы (ММС) обеспечивают: повышения производительности, надежности и достоверности вычислений. Для этих целей использовали комплекс машин, схематически показанный на рис.

Положения 1 и 3 электронного ключа (ЭК) обеспечивало режим повышенной надежности. При этом одна из машин выполняла вычисления, а другая находилась в "горячем" или "холодном" резерве, т.е. в готовности заменить основную ЭВМ. Положение 2 электронного ключа соответствовало случаю, когда обе машины обеспечивали параллельный режим вычислений. Здесь возможны две ситуации:

обе машины решают одну и ту же задачу и периодически сверяют результаты решения. Тем самым обеспечивался режим повышенной достоверности, уменьшалась вероятность появления ошибок в результатах вычислений;

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

Основные отличия ММС разных модификаций заключаются, как правило, в организации связи и обмена информацией между ЭВМ комплекса. Каждая из них сохраняет возможность автономной работы и управляется собственной ОС. Любая другая подключаемая ЭВМ комплекса рассматривается как специальное периферийное оборудование. В зависимости от территориальной разобщенности ЭВМ и используемых средств сопряжения обеспечивается различная оперативность их информационного воздействия.

Вопрос 35

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

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

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

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

1) p-мерные конвейерные соединители;

2) матричные коммутаторы:

3) многоярусные сети (они являются более перспективными для упорядочения данных в параллельной памяти).

1) p-мерные конвейерные соединители.

В конвейерном соединителе p-мерная структура узлов связывается в каждом измерении таким образом, чтобы обеспечивалась последовательная конвейерная передача данных между ними. Продвижение данных происходит, как правило, синхронно. При передаче данных в 1-м измерении от узла i к узлу i+v данные последовательно проходят через все i1 узлов.

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

Примером одномерного конвейерного соединителя могут служить соединительная сеть мультипроцессора «ZMOB» и «Кембриджское кольцо», а двухмерного—система связи в матрице процессорных элементов вычислительной системы «ILLIAC-IV».

К достоинствам конвейерных соединителей можно отнести их простоту и регулярность, к существенным недостаткам - зависимость времени передачи данных от расстояния между узлами. Так, например, в системе ZMOB это время колеблется от 100 нс до 25.6 мкс. Кроме того, существуют проблемы с обеспечением надежности таких структур, так как сбой в одном узле может привести к искажению множества сообщений.

Рассматривая применимость p-мерных конвейерных структур для упорядочения данных в параллельной памяти, можно отметить, что они достаточно просто позволяют производить необходимые перестановки данных в тех случаях, когда при формировании запоминающей среды используются линейные периодические размещения. Известно, что соответствующие таблицы размещения строятся с использованием линейных сдвигов, которые и составляют основу алгоритмов упорядочения данных. Однако при этом приходится считаться с отмеченной выше зависимостью времени сдвига (упорядочения данных) от величины сдвига. В памяти это приводит к зависимости времени доступа от вида обращения, что нежелательно. Дополнительные трудности возникают, когда число модулей памяти в многоблочной запоминающей среде больше ширины доступа (M>L). В таком случае, приходится решать задачу маскирования «лишних» узлов конвейерного соединителя.

2). Матричные коммутаторы

Матричные коммутаторы (crossbar network) являются одним из наиболее гибких типов соединительных сетей. Обобщенная структура матричного коммутатора, обеспечивающего соединение М на L портов.

Сеть коммутации представляет собой множество связей между двумя наборами узлов, которые называются входами и выходами. Всего между M входами и L выходами существует ML раз личных связей, включая парные связи («один — одному»), связи «один—многим», смешанные связи.

Сеть, осуществляющая ML соединений, называется обобщенной соединительной сетью. Если сеть осуществляет только парные связи, она называется соединительной, в ней возможно M! Соединений. В соединительных сетях любой допустимый набор связей (перестановка) выполняется за один такт и без конфликтов.

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

Одной из разновидностей матричного коммутатора является сеть, называемая «полное соединение» (complete connection). В ней для установления связи каждого из М портов с L портами используются собственные L линий связи. Легко заметить, что число узлов коммутации в этом случае остается прежним.

Так как число узлов коммутации растет пропорционально произведению ML, то стоимость матричных коммутационных сетей при большом количестве портов весьма высока. Однако при малом числе соединяемых блоков они эффективно используются, в частности, и для упорядочения данных в параллельной памяти.

3). Многоярусные коммутационные сети

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

Выделяют три основных вида многоярусных сетей: неблокируемые сети, перестраиваемые и блокируемые сети.

Неблокируемые сети.

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

Неблокируемые структуры получаются путем введения дополнительных ярусов коммутации. Несмотря на это многоярусные неблокируемые сети часто более экономичны, чем матричные коммутаторы. Так, например, число КЭ в матричном коммутаторе для М = L = 25 (двадцать пять входов соединяются с двадцатью пятью выходами) равно 625, в трехярусной схеме Клоза - 675, но при М = L = 100 для матричного коммутатора число КЭ уже 10000, a в схеме Клоза - 5700.

Перестраиваемые сети.

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

портами, перестраивая существующие связи так, как этого требует установление незаблокированного пути для новой заданной пары портов. Структурная схема такой сети, называемой сетью Бенеша.

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

Блокируемые сети.

Одним из обобщений блокируемых сетей являются Бэнян-сети, которые введены Р. Гоуком и К. Липовским и использовались для построения мультипроцессорной архитектуры. Свое название они получили oт фигового дерева (banyan-tree). Авторы, очевидно, имели в виду определенное топологическое сходство индийской смоковницы и соответствующего графа.

Граф, описывающий структуру Бэнян-сети, содержит три типа вершин: начальные, не имеющие входящих ребер, конечные, не имеющие исходящих ребер, и промежуточные. Последние имеют и входящие, и выходящие ребра. Отметим некоторые топологические особенности Бэнян-сетей. Сеть, в которой каждый путь, от начальной вершины к конечной имеет длину l и для каждой пары <начальная вершина—конечная вершина> этот путь является единственным называется l-уровневой Бэнян-сетью. В такой сети имеется l уровней (ярусов) ребер и l + 1 уровней вершин. В l -уровневых Бэнян-сетях ребра связывают только вершины соседних уровней. Примем, что начальные вершины размещаются на уровне 0, а конечные - на уровне l. В дальнейшем рассматриваются только однородные Бэнян-сети, в которых для всех вершин одного уровня число входящих и число выходящих ребер есть величины постоянные. Структуру однородной Бэнян-сети можно охарактеризовать, если указать число вершин на каждом уровне L0, L1, …,Ll и для вершин каждого уровня число входящих (c) и выходящих (0) ребер. Так как в l-уровневой сети l ярусов ребер, то соответствующее описание всей сети задается l-компонентными векторами с= (с1, с2, ..., сl), о= (o1, o2, ..., ol) и вектором L= (L0, L1, ..., Ll).

Бэнян-сеть называется регулярной, если с1= с2= ...= сl и o1= o2= ...= ol, в противном случае сеть нерегулярна . Важное место в классе Бэнян-сетей занимают прямоугольные сети. Сеть является прямоугольной, если L0= L1= ...= Ll и с = о. Нерегулярные прямоугольные Бэнян-сети называются слабо прямоугольными, регулярные - строго прямоугольными.

Еще одним обобщенным видом блокируемых многоярусных систем являются Дельта-сети.

Строго прямоугольные Бэнян-сети с числом узлов на каждом уровне L = 21, построенные на 2 X 2-матричных переключателях, составляют особый подкласс сетей. Эти сети называются двоичными перестановочными (или просто перестановочными) сетями. К ним можно отнести такие широко известные сети как Омега-сеть, сеть типа двоичный n-Куб, модифицируемый манипулятор данных, базисная сеть.

Обобщенная двоичная перестановочная сеть может быть представлена log2L = l ярусами коммутационных элементов, соединенных между собой по определенному закону. Сеть, рассматриваемая как однонаправленная, осуществляет передачу данных от входа к выходу. Каждый ярус сети может быть представлен как два устройства, выполняющих последовательно две перестановки (рис. 6). Одна из них - статическая (St) осуществляется за счет того, что линии связи между ярусами могут изменять позицию при входе в следующий ярус. Статическая перестановка определяется выбранным законом межярусных соединений, она зафиксирована для конкретного вида сети. Вторая, динамическая перестановка (Di), осуществляется коммутационными элементами, и ее содержание определяется выбранным способом управления сетью, а также видом КЭ.

В двоичных перестановочных сетях в качестве КЭ используются 2 Х 2-переключатели двух типов. Модель КЭ первого типа составлена из двух мультиплексоров 2 X 1, управляемых независимо. Такой КЭ может находиться в четырех различных состояниях, определяемых управляющим сигналами c1, c0. Коммутационные элементы второго типа имеют только два состояния включения и управляются единственным управляющим сигналом с. Мы рассматриваем двоичные перестановочные сети как устройства упорядочения данных в параллельной памяти.

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

Рассмотрим и сравним между собой несколько конструкций сетей.

Рассмотрим двумерный коммутатор. Каждый процессорный элемент (ПЭ) соединен двусторонними связями с четырьмя соседними (справа, слева, снизу, сверху). Внешние связи МОГУТ в зависимости от решаемой задачи программно замыкаться по-разному: вытягиваться в цепочку , замыкаться в виде вертикально и горизонтально расположенных цилиндров, в виде тороида. Коммутационный элемент (КЭ) здесь обычно соединен с оборудованием ПЭ, и объем оборудования всего коммутатора растет пропорционально числу процессоров M.

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

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

В общем случае все среды можно назвать n-мерными кубами, тогда кольцевой коммутатор имеет размерность п=1, а матрица - п=2 и т. д. Большое распространение в параллельной вычислительной технике получили среды с размерностями 2 и 3. Чем больше п при неизменном числе процессоров, тем больше радиус связей и тем меньше D. Под радиусом связи понимается число процессоров, напрямую связанных с данным ПЭ.

Величина п может быть и больше трех. Покажем общий прием построения n-кубов произвольной размерности.

Для примера рассмотрим возможные связи элемента 9 матрицы, изображенной на рис. 11, а. Этот элемент в своей строке связан с элементами 8 и 10, адреса которых отличаются на -1 и +1. Если бы данная строка составляла независимый коммутатор с размерностью 4 (n=1, M=4), то связи любого ПЭi такого коммутатора описывались бы рангом 1. Если элемент 9 находится в матрице, то его связи с элементом 5 верхней строки и элементом 13 нижней строки отличаются на +M и -M, где M=4 - размер строки. Следовательно, связи элемента ПЭi матричного коммутатора описываются рангом 2.

Если бы элемент 9 находился в кубе, то номера смежных элементов соседних плоскостей отличались бы на ±M2, в кубе степени 4 - на ±M3 и т. д. Такая методика позволяет построить куб любой степени и вычислить величину D.

Многокаскадные коммутаторы помогают создать более дешевые варианты соединительных и обобщенных соединительных сетей. Координатный переключатель NXN можно свести к двум (N/2XN/2) переключателям с замещением . В свою очередь переключатели N/2XN/2 могут быть разложены на более мелкие подобным же образом. Пример сети, приведенной до уровня стандартных 1<Э размерностью 2х2, дан на рис. 13, б. По определению, это полная соединительная сеть (сеть Бенеша), обеспечивающая N! возможных перестановок, каждая из которых выполняется за один такт работы сети. В такой сети отсутствуют конфликты для любых парных соединений.

Стандартный КЭ размерностью 2Х2 и возможные в нем соединения. Иногда для построения больших сетей применяются элементы 4Х4 или 8Х8. Основной недостаток сети Бенеша - большое количество элементов, необходимых для ее построения.

Широко используются неполные соединительные сети: омега-сеть, сеть Бенеша, R-сеть и др. Омега-сеть относится к типу сетей тасовки с замещением.

Коммутационные сети могут работать в двух режимах: коммутация каналов и коммутация сообщений. В первом случае сначала с помощью адресной системы устанавливается прямой электрический тракт между парой соединяемых точек, а затем по этому тракту передастся информация. Такой вид связи используется, например, в телефонных сетях. Во втором случае каждая передаваемая единица информации снабжается адресом требуемого выхода и перемещается от узла ni, к узлу ni+1, где i - номер каскада; п и т - номера коммутационных узлов в каскадах. После того как информация принята узлом mi+1, линия, соединявшая ni и mi+1, становится доступной для других соединении. Узел mi+1 по адресной части сообщения определяет дальнейший маршрут сообщения. В матрицах процессоров используется как коммутация каналов, так и коммутация сообщений.