Mapping semigroup array operations onto computer system with toroidalstructure.pdf Распределенная вычислительная система представляет собой совокупность парпроцессор - память, называемых процессорными элементами (или просто процес-сорами) и связанных друг с другом сетью линий связи, где каждая линия соединя-ет два процессора. Такая сеть межпроцессорных соединений описывается графом.В современных суперкомпьютерных распределенных системах в качестве графасети связи обычно используется трехмерный тор [1 - 4].Основу многомерного (k-мерного) тора образует многомерная «решетка» изp1p2...pk вершин, где каждая вершина имеет метку (a1,a2,...,ak),ai{0,1,...,pi−1}, i= 1, 2,...,k. Две вершины (a1,a2,...,ak) и (b1,b2,...,bk) явля-ются соседними в решетке, если для некоторого i выполнено ai=bi1 и для всехji выполнено aj = bj. Многомерный тор образуется «зацикливанием» строк истолбцов решетки. Он описывается графом из p1p2...pk вершин, где верши-ны (a1,a2,...,ak) и (b1,b2,...,bk) являются соседними, если для некоторого i вы-полнено ai=bi1 modpi и для всех ji выполнено aj = bj.Полугрупповой операцией называют бинарную ассоциативную операцию ⊗[5]. Примерами таких операций могут служить сумма, произведение, конъюнкция,дизъюнкция, исключающее ИЛИ, а также вычисление максимума или минимума.В [5] предложен параллельный алгоритм выполнения такой операции над масси-вом данных, распределенных по процессорам матричной сети («решетки»), при-чем результат операции должен получить каждый процессор. Алгоритм сводитсяк выполнению последовательности циклических сдвигов в линейной сети («ли-нейке») процессоров с выполнением операции ⊗ при каждом сдвиге. Такие сдви-ги выполняются для всех измерений решетки. Этот алгоритм легко переноситсяна тороидальную сеть процессоров.В данной работе предлагается альтернативный подход к отображению полу-групповых операций на вычислительные системы с тороидальной структурой, ос-нованный на использовании в полугрупповых операциях схемы «бабочка» [4, 6],отображении этой схемы на гиперкуб с последующим XOR-отображением гипер-куба на тор [2, 4]. Показано, что такой подход при использовании отображения [2]дает меньшее время параллельного выполнения полугрупповой операции на торе,чем подход, предложенный в [5].1. Выполнение полугрупповой операции на решетке и торес использованием циклических сдвигов данныхПусть массив x =(x1,...,xn) изначально распределен по одному элементу дан-ных в каждом процессоре двумерной решетки из n n процессоров, то естькаждый процессор Pij изначально содержит соответствующий элемент i n j x + ,i, j{1,..., n} . Требуется применить полугрупповую операцию ⊗ ко всем ис-ходным значениям массива x так, чтобы каждый процессор получил результатприменения операции.В [5] предложен алгоритм выполнения полугрупповых операций на решеткепроцессоров, состоящий в выполнении последовательности циклических сдвиговс выполнением операции ⊗ при каждом сдвиге:1. Параллельно в каждой строке i выполнить циклический сдвиг данных так,что каждый процессор в строке получает результат 1/ 21ni j i n j r x = + = ⊗ .2. Параллельно в каждом столбце j выполняется циклический сдвиг данныхтак, что каждый процессор в столбце получает результат 1/ 2' n 1s = ⊗i= ri, равный же-лаемому результату 1/ 2 1/ 21 1n ni j i n j s = =x + = ⊗ ⊗ .Циклический сдвиг в строке (или столбце) решетки процессоров выполняетсятак: каждый элемент перемещается от процессора к процессору вправо, пока непопадет в самый правый процессор, далее направление его сдвигов меняется напротивоположное (гусеничный алгоритм [5]). Сдвиги в торе отличаются от сдви-гов в решетке тем, что, благодаря зацикливанию строк и столбцов, направлениесдвига не меняется.2. Выполнение полугрупповой операции на гиперкубес использованием схемы сдваиванияПриведенные в предыдущем разделе алгоритмы выполнения полугрупповойоперации над массивом данных в торе не являются оптимальными. Эту операциюможно выполнить быстрее, если использовать систему параллельных процессов,структура которой называется «бабочкой» (рис. 1). В этой структуре схема сдваи-вания [6], являющаяся оптимальной для реализации полугрупповых операций,реализует размножение вычислений с максимальным количеством одновременновыполняемых операций над разными парами аргументов.Бабочка легко отображается в гиперкуб. Для этого достаточно объединитьоперации тех процессов, которые не могут выполняться одновременно. На рис. 1объединяемые процессы (операции) лежат на одной вертикальной линии. Нарис. 2 показан полученный в результате слияния процессов гиперкуб. Здесь числав скобках показывают номер шага взаимодействий между узлами структуры.(1)(2)(3)x0 x1 x2 x3 x4 x5 x6 x7Рис. 1. Бабочка4 530 16 7(2)(3)(3)(2)(2)(2)(3)(3)2(1)(1)(1)(1)Рис. 2. Гиперкуб, полученный слиянием процессовдвоичного дерева или бабочки3. Вложение гиперкуба в торПолученный слиянием процессов бабочки гиперкуб может быть вложен в тор[2, 4]. Способ отображения гиперкуба в тор (XOR-вложение) предложен в [2].Вложение графа G в граф H является инъекцией f вершин G в вершины H. Еслиграф G не изоморфен подграфу H, то неизбежны растяжения ребер графа G. Рас-тяжением ребра (a,b) графа G на графе H называется расстояние (длина крат-чайшего пути) между вершинами f (a) и f (b) .XOR-вложение гиперкуба Hd в k -мерный тор (2d1 ,...,2dk )Ek ,1kiid d=ƒ = реа-лизуется следующим образом. Сначала определяются Kj:1110,, 1 1.jj iiKK d j k−===ƒ < ≤ +Если граф G является гиперкубом Hd , а граф T - тором, то вершина v графа Gотображается в вершину (m1,...,mk)=fXOR(v) графа T следующим образом [2]:(( ) ( )) 1 1( ) ( ), 0, 1 , 2,( 2) 1, 2 .j j j jj j j jm i v i K i d i dm d XOR v K + v K += + ⎡⎣ − ⎤⎦  −− = − −Здесь x(i) − i-й бит двоичного представления x. Показано [2], что гиперкуб Hdможет быть вложен в тор (2d1 ,...,2dk )Ek , где1kiid d=ƒ = , со средним растяжением213 2 ikdikDd−=⎛ ⎞⎜ ⋅ ⎟−=⎝ ⎠ƒ. (1)В табл. 1 и 2 приведены вычисленные по формуле (1) средние значения растя-жения D для нескольких значений числа машин n = 2d при k = 2,3 соответст-венно, i , 1,...,d d i kk= = .Т а б л и ц а 1Среднее растяжение ребер гиперкуба на двумерном тореn 16 64 256 1024 4096 16384 65536D 1 1,667 2,75 4,6 7,833 13,5714 23,8750Т а б л и ц а 2Среднее растяжение ребер гиперкуба на трехмерном тореn 64 512 4096D 1 1.667 2.75В общем случае результатом отображения гиперкуба в тор являются пути наторе вместо ребер в гиперкубе. При вложении одного графа в другой возникаю-щие при этом пути могут пересекаться, поэтому кроме растяжений ребер могутвозникать конфликты путей (перегрузки каналов связи) на ребрах тора. Эти пере-грузки могут привести к увеличению продолжительности межмашинных обменовданными.Например (рис. 3), пусть вершины A и B одновременно посылаютРис. 3. Конфликт сообщений из вершин A и B на дуге (C,D)Утверждение 1. XOR-вложение гиперкуба в тор не создает перегрузок.Доказательство. 1. Сначала рассмотрим одномерный тор (кольцо) и произ-вольное отображение гиперкуба в тор, то есть произвольную нумерацию вершин.Пусть два произвольных пути с различными вершинами-источниками и верши-нами-приемниками пересекаются на кольце (т.е. имеют общие ребра) и оба со-общения начинают передаваться одновременно.Если эти пути направлены противоположно, то перегрузок нет, поскольку ка-ждое ребро используется для одновременной передачи сообщений по двум проти-воположно направленным дугам (каналам).Если два пути ориентированы одинаково, как на рис. 4, то перегрузок также нет,поскольку передачи начинаются одновременно. Когда некоторое сообщение посту-пает в вершину для последующей трансляции, то соответствующая выходная дугауже свободна, поскольку передача выходного сообщения по ней завершена.Например, на рис. 4 передача сообщения из вершины B в вершину D не задер-живает передачу сообщения из вершины A в вершину C , так как сообщения из Aв B и из B в C передаются одновременно.A B C D EB C DРис. 4. Одинаково направленные пути (A,B,C,D,E) и (B,C,D)2. Рассмотрим общий случай XOR-вложения. Взаимодействия между процес-сами в структуре «бабочка» на d-мерном гиперкубе выполняются за d шагов. Нашагеs {1,..., d} (2)вершина v взаимодействует с вершиной v ' , если v−v' =2s−1 .Рассмотрим стандартное отображение d-мерного гиперкуба в k-мерный торEk(n1,...,nk)12 i, 2kd di iin n== ƒ = (3)в виде f (v) =(p1,...,pk), где11 1mod div , 1,..., ,i ii j jj jp v n n i k−= =⎛ ⎞=⎜⎜ ⎟⎟ =⎝ ⎠ƒ ƒ (4)где div обозначает деление нацело.Две различных вершины v и v' лежат в m-м одномерном торе (кольце), если( )

Скачать электронную версию публикации