Ответы 190 страниц (1184228), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

Другой подход к решению той же проблемы прдоставляет „толстое дерево“ (рис. ). Это прямой способ решения, при котором связи поддеревьев более высокого уровня обладают более высокой производительностью.

Рис. 21: Толстое дерево (fat-tree).

Топология гиперкуба.

Для получения более компактной конфигурации необходимо решить задачу о нахождении фигуры, имеющей максимальный объем при минимальной площади поверхности. В трехмерном пространстве таким свойством обладает шар. Но поскольку нам необходимо построить узловую систему, вместо шара приходится использовать куб (если число процессоров равно 8) или гиперкуб, если число процессоров больше 8. Размерность гиперкуба будет определяться в зависимости от числа процессоров, которые необходимо соединить. Так, для соединения 16 процессоров потребуется четырехмерный гиперкуб. Для его построения следует взять обычный трехмерный куб, сдвинуть в нужном направлении и, соединив вершины, получить гиперкуб размером 4.

Рис. 4.4. Топология связи, 3-х мерный гиперкуб

Архитектура гиперкуба является второй по эффективности, но самой наглядной. Используются и другие топологии сетей связи: трехмерный тор, "кольцо", "звезда" и другие.

Рис. 4.5. Топология связи, 4-х мерный гиперкуб

Гиперкуб — пространственное обобщение рассмотренной плоской решетки, где адресация процессоров (и соответственно, блоков распределенной памяти) ставится в зависимость от структуры связей между ними. Проводится аналогия с n-мерным пространством.

Возьмем единичный квадрат в двухмерном пространстве с вершиной в начале координат (рис. 9.3,а). Пусть его вершины соответствуют процессорным элементам (ПЭ), а ребра — связям между ними. Пусть код, образованный координатами вершин, — адрес ПЭ. Тогда видно, что связи между ПЭ существуют тогда, когда адреса отличаются не более чем в одном разряде. То же самое можно обнаружить для n = 3, n = 4 и т.д.

Значит, в общем случае ВС типа "гиперкуб" формируется следующим образом. Ее образуют 2n ПЭ, каждый ПЭ соединен ровно с n ПЭ. При длине адреса ПЭ, равной n, непосредственно связаны ПЭ, у которых адреса разнятся не более чем в одном разряде.

Структура типа "гиперкуб" обладает важными свойствами. Из структуры "гиперкуб" легко получаются более простые структуры. Например, при n = 3 легко получается матричная ВС, на которой, в частности, хорошо решать задачи в конечных разностях. Как мы видели ранее, для этого удобна плоская решетка, где существуют непосредственные (не транзитные) связи между тремя ПЭ (столбец составляют только два ПЭ, поэтому нет необходимости в связях в двух направлениях), как показано на рис. 9.4. Здесь можно в дополнение к адресам ввести (временно) нумерацию ПЭ и поставить эти номера в соответствие адресам.

Процессоры образовали фрагмент плоской решетки для реализации конечно-разностного метода (метода сеток). Процессоры "прокатываются" по области, на которой строится решение, например, задачи численного интегрирования.

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

Например, предположим, что в предыдущем примере мы располагали не 3-мерным, а 6-мерным "гиперкубом". Пусть планирующая система в составе ОС из всего адресного пространства ПЭ 000000 ÷ 111111 выделила нам массив 101000 ÷ 101111, т.е. определенное 3-хмерное подпространство всего пространства процессоров. В это же время пусть другой задаче выделен массив 000000 ÷ 001111, т.е. четырехмерное подпространство и т.д.

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

Согласование сеточных топологий со структурой гиперкуба.

Методы логического представления топологии коммуникационной среды

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

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

уплотнение дуг (congestion), выражаемое как максимальное количество дуг логической топологии, отображаемых в одну линию передачи физической топологии;

удлинение дуг (dilation), определяемое как путь максимальной длины физической топологии, на который отображаемая дуга логической топологии;

увеличение вершин (expansion), вычисляемое как отношение количества вершин в физической и логической топологиях.

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

Представление кольцевой топологии в виде гиперкуба

Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Gray code), Код Грея для N = 1 Код Грея для N = 2 Код Грея для N = 3 Номера процессоров

гиперкуба кольца

0 0 0 0 0 0 0 0

1 0 1 0 0 1 1 1

1 1 0 1 1 3 2

1 0 0 1 0 2 3

1 1 0 6 4

1 1 1 7 5

1 0 1 5 6

1 0 0 4 7

Рис. 3.2. Отображение кольцевой топологии на гиперкуб при помощи кода Грея

определяемого в соответствии с выражениями:

G(0, 1) = 0, G(1, 1) = 1,

где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода на рис. 3.2 показывается отображение кольцевой топологии на гиперкуб для сети из p = 8 процессоров.

Важным свойством кода Грея является тот факт, что соседние значения G(i, N) и G(i + 1, N) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе .

Отображение топологии решетки на гиперкуб

Отображение топологии решетки на гиперкуб может быть выполнено в рамках подхода, использованного для кольцевой структуры сети. Тогда для отображения решетки 2r×2s на гиперкуб размерности N = r + s можно принять правило, что элементу решетки с координатами (i, j), будет соответствовать процессор гиперкуба с номером

G(i, r) || G(j, s),

где операция || означает конкатенацию кодов Грея

Перекрестный коммутатор.

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

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

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

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

Для того чтобы упростить и удешевить ВК, коммутацию устройств осуществляют с помощью двух и даже более коммутационных матриц. Перекрестная коммутация довольно широко используется при построении ВК, в частности практически всех МПВК фирмы "Барроуз" (в том числе и упомянутого выше комплекса D-825).

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

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

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

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

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

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

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

Для обеспечения большей гибкости и увеличения возможностей по расширению в системе может быть введена дополнительная коммутационная матрица устройств ввода-вывода. Такой коммутатор связывается с центральным через процессоры управления вводом-выводом (рис. 2.3), при этом устройства ввода- вывода могут подсоединяться к любому каналу. Рассмотренная структура мультипроцессорных систем используется в больших вычислительных системах фирмы "Burroughs" (США).

Оригинальный вариант организации мультипроцессорной конфигурации предложен для системы Multi-Interpreter фирмы "Burroughs", в которую введена группа однотипных процессорных блоков с микропрограммным управлением. Путем перезагрузки блоков микропрограммной памяти одни и те же модули используются в качестве центральных процессоров либо контроллеров ввода - вывода. Благодаря этому все процессоры, модули памяти и периферийные устройства подключены к общей коммутационной матрице (рис. 2.4).

Характеристики

Список файлов ответов (шпаргалок)