СКИПОДы 2007 полная версия (1127795), страница 29
Текст из файла (страница 29)
Проводится аналогия с n-мерным пространством.Возьмем единичный квадрат в двухмерном пространстве с вершиной в начале координат(рис. 9.3,а). Пусть его вершины соответствуют процессорным элементам (ПЭ), а ребра —связям между ними. Пусть код, образованный координатами вершин, — адрес ПЭ. Тогдавидно, что связи между ПЭ существуют тогда, когда адреса отличаются не более чем водном разряде. То же самое можно обнаружить для n = 3, n = 4 и т.д.Значит, в общем случае ВС типа "гиперкуб" формируется следующим образом. Ее образуют2n ПЭ, каждый ПЭ соединен ровно с n ПЭ. При длине адреса ПЭ, равной n,непосредственно связаны ПЭ, у которых адреса разнятся не более чем в одном разряде.Структура типа "гиперкуб" обладает важными свойствами.
Из структуры "гиперкуб" легкополучаются более простые структуры. Например, при n = 3 легко получается матричная ВС,на которой, в частности, хорошо решать задачи в конечных разностях. Как мы видели ранее,для этого удобна плоская решетка, где существуют непосредственные (не транзитные)связи между тремя ПЭ (столбец составляют только два ПЭ, поэтому нет необходимости в94связях в двух направлениях), как показано на рис. 9.4. Здесь можно в дополнение к адресамввести (временно) нумерацию ПЭ и поставить эти номера в соответствие адресам.Процессоры образовали фрагмент плоской решетки для реализации конечно-разностногометода (метода сеток).
Процессоры "прокатываются" по области, на которой строитсярешение, например, задачи численного интегрирования.Второе важное свойство "гиперкуба" — возможность выделения задаче необходимыхсвязных областей вычислительных ресурсов. Эти области соответствуют пространствамменьшей размерности, чем размерность всего "гиперкуба". Это означает, что т.к.процессоры адресуемы внутри некоторого адресного пространства, то каждой решаемойзадаче может быть выделен вычислительный ресурс в пределах какого-то массива сосквозной нумерацией процессоров. В n-мерном пространстве этот массив принадлежитподпространству меньшего измерения. Т.е.
значительная часть разрядов адреса длины n длявсех процессоров, образующих ресурс данной задачи, совпадает, а меняются тольконесколько последних разрядов.Например, предположим, что в предыдущем примере мы располагали не 3-мерным, а 6мерным "гиперкубом". Пусть планирующая система в составе ОС из всего адресногопространства ПЭ 000000 ÷ 111111 выделила нам массив 101000 ÷ 101111, т.е. определенное3-хмерное подпространство всего пространства процессоров.
В это же время пусть другойзадаче выделен массив 000000 ÷ 001111, т.е. четырехмерное подпространство и т.д.Как и для других ОВС, здесь предполагается наличие распределенной памяти. Приформировании общего адресного пространства примем, что старшие разряды адреса памятисовпадают с адресом ПЭ.Согласование сеточных топологий со структурой гиперкуба.Методы логического представления топологии коммуникационной средыКак показало рассмотрение основных коммуникационных операций в п.
3.3, ряд алгоритмовпередачи данных допускает более простое изложение при использовании вполнеопределенных топологий сети межпроцессорных соединений. Кроме того, многие методыкоммуникации могут быть получены при помощи того или иного логическогопредставления исследуемой топологии. Как результат, важным моментом является приорганизации параллельных вычислений умение логического представления разнообразныхтопологий на основе конкретных (физических) межпроцессорных структур.Способы логического представления (отображения) топологий характеризуютсяследующими тремя основными характеристиками:уплотнение дуг (congestion), выражаемое как максимальное количество дуг логическойтопологии, отображаемых в одну линию передачи физической топологии;удлинение дуг (dilation), определяемое как путь максимальной длины физическойтопологии, на который отображаемая дуга логической топологии;увеличение вершин (expansion), вычисляемое как отношение количества вершин вфизической и логической топологиях.Для рассматриваемых в рамках пособия топологий ограничимся изложением вопросовотображения топологий кольца и решетки на гиперкуб ; предлагаемые ниже подходы длялогического представления топологий характеризуются единичными показателямиуплотнения и удлинения дуг.95Представление кольцевой топологии в виде гиперкубаУстановление соответствия между кольцевой топологией и гиперкубом может бытьвыполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Graycode), Код Грея для N = 1 Код Грея для N = 2 Код Грея для N = 3 Номера процессоровгиперкубакольца000000 00101001 1111011 3210010 23110 64111 75101 56100 47Рис.
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),где операция || означает конкатенацию кодов ГреяПерекрестный коммутатор.Полностью лишены недостатков, присущих МПВК с общей шиной, МПВК с перекрестнойкоммутацией.
Идея структурной организации таких ВК заключается в том, что все связимежду устройствами осуществляются с помощью специального устройства коммутационной матрицы. Коммутационная матрица (КМ) позволяет связывать друг сдругом любую пару устройств, причем таких пар может быть сколько угодно: связи независят друг от друга.В МПВК с перекрестной коммутацией нет конфликтов из-за связей, остаются толькоконфликты из-за ресурсов. Возможность одновременной связи нескольких пар устройствпозволяет добиваться очень высокой производительности комплекса. Важно отметить итакое обстоятельство, как возможность установления связи между устройствами на любое,96даже на длительное время, так как это совершенно не мешает работе других устройств, затопозволяет передавать любые массивы информации с высокой скоростью, что такжеспособствует повышению производительности комплекса.
Заметим, что в МПВК с общейшиной передача информации массивами, т.е, занятие шины одной парой устройств надлительный отрезок времени, обычно допускается лишь в крайних случаях, так как этоприводит к длительным простоям остальных устройств.Кроме того, к достоинствам структуры с перекрестной коммутацией можно отнестипростоту и унифицированность интерфейсов всех устройств, а также возможностьразрешения всех конфликтов в коммутационной матрице. Важно отметить и то, чтонарушение какой-то связи приводит не к выходу из строя всего комплекса, а лишь котключению какого-либо устройства, т.е.
надежность таких комплексов достаточно высока.Однако и организация МПВК с перекрестной коммутацией не свободна от недостатков.Прежде всего - сложность наращивания ВК. Если в коммутационной матрице заранее непредусмотреть большого числа входов, то введение дополнительных устройств в комплекспотребует установки новой коммутационной матрицы. Существенным недостаткомявляется и то, что коммутационная матрица при большом числе устройств в комплексестановится сложной, громоздкой и достаточно дорогостоящей. (Надо учитывать тообстоятельство, что коммутационные матрицы строятся обычно на схемах, быстродействиекоторых существенно выше быстродействия схем и элементов основных устройств, только при этом условии реализуются все преимущества коммутационной матрицы.) Этообстоятельство в значительной степени усложняет и удорожает комплексы.Для того чтобы упростить и удешевить ВК, коммутацию устройств осуществляют спомощью двух и даже более коммутационных матриц.
Перекрестная коммутация довольношироко используется при построении ВК, в частности практически всех МПВК фирмы"Барроуз" (в том числе и упомянутого выше комплекса D-825).В МПВК с многовходовыми ОЗУ все, что связано с коммутацией устройств,осуществляется в ОЗУ. В этом случае модули ОЗУ имеют число входов, равное числуустройств, которые к ним подключаются, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
