Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005).pdf), страница 3

Sergey Gaissaryan, Arutyun Avetisyan, Oleg Samovarov, DmitryGrushin. Comparative Analysis of High-Performance Clusters' CommunicationEnvironments Using HPL Test. // High Performance Computing and Grid inAsia Pacific Region, Seventh International Conference on (HPCAsia'04), July20-22, IEEE Computer Society, 2004. Omiya Sonic City, Tokyo, Japan, pp.473-476.2. Arutyun Avetisyan, Oleg Samovarov, Dmitry Grushin, Andrey Ryzhov.«Clusterweb – a WEB-based cluster management interface».

M. Estrada, A.Gelbukh (Eds.) // Avances en la Ciencia de la Computacion, ENC'04, Colima,Mexico, pp. 489-495.3. OSCAR. http://www.gelato.org/software/view.php?id=1_184. Gelato. http://www.gelato.org/5. ИСП РАН. http://www.ispras.ru/news/armcluster.htmlОРГАНИЗАЦИЯ ОБМЕНА ДАННЫМИ НА ПАРАЛЛЕЛЬНЫХКОМПЬЮТЕРАХ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮЕ.В. АдуцкевичИнститут математики НАН Беларуси, Минск (Беларусь)ВведениеДля отображения алгоритмов, заданных последовательными программами, на параллельные компьютеры с распределенной памятьютребуется распределить операции и данные алгоритма между процессорами, а также установить порядок выполнения операций и обменаданными.

При выполнении алгоритмов на таких компьютерах реализация коммуникаций между процессорами имеет, как правило, большиенакладные расходы. Поэтому распределение операций и данных междупроцессорами следует производить таким образом, чтобы уменьшитьколичество и объем коммуникаций; кроме того, следует оптимизировать структуру коммуникаций.Задаче уменьшения коммуникационных затрат посвящено многоисследований. Самый очевидный подход – разбиение на блоки независимых вычислений [1, 2]. Заметим, что на практике алгоритм далеко невсегда допускает декомпозицию на независимые части. Другой подходнаправлен на минимизацию обменов данными. Этого можно добитьсячерез построение блочных версий алгоритма, при разбиении специальным образом пространства итераций гнезд циклов [1, 3]; в этом случаене затрагивается проблема размещения массивов данных и ее нужно12решать отдельно.

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

Известно, что на параллельных компьютерах с распределеннойпамятью структурированные коммуникации, такие как бродкаст(broadcast), разброс (scatter), сборка (gather), редукция (reduction), атакже трансляция (translation) данных выполняются быстрее, чембольшое количество коммуникаций точка-точка (point-to-point) междупроцессором, в локальной памяти которого хранится данное, и каждымпроцессором, который использует или переопределяет это данное. Поэтому желательно выявлять возможность организации таких коммуникаций. Некоторые пути решения этой задачи намечены в работе [6].В настоящей работе развиваются идеи, предложенные в работе [6].Сформулированы условия, позволяющие определять возможность организации часто используемых быстрых коммуникаций – бродкаста итрансляции данных, а также описан способ установления схемы обменов данными.

Проведенные исследования могут быть использованыпри автоматизированном распараллеливании программ.Постановка задачиБудем рассматривать аффинные гнезда циклов; в этом случае выражения индексов элементов массивов и границы изменения параметров циклов являются аффинными функциями от параметров циклов ивнешних переменных.Пусть в гнезде циклов имеется K операторов Sβ и используется Lмассивов al. Область изменения параметров гнезда циклов для оператора Sβ будем обозначать Vβ; область изменения индексов l-го массивабудем обозначать Wl . Обозначим nβ – число циклов, окружающих опеnβvlратор Sβ , vl – размерность l-го массива; тогда Vβ ⊂ Z , Wl ⊂ Z . Векnβтор параметров цикла будем обозначать J ∈ Z , вектор внешних пеeременных алгоритма – N ∈ Z , e – число внешних переменных.13Реализацию (выполнение) оператора Sβ при конкретных значенияхβ и вектора параметров цикла J будем называть операцией и обозначать Sβ(J).Для упрощения обозначений будем считать, что все рассматриваеmgмые далее аффинные функции имеют вид f : V → G, V ⊂ Z , G ⊂ Z ,g×mg×egf (J) = AJ + BN + C, где A ∈ Z , B ∈ Z , C ∈ Z .

Пусть ∆ – элемент∆множества G. Будем рассматривать множество V = {J ∈ V | f (J) = ∆}.∆Множество V будем называть невырожденным, если dim(ker A) ≠ 0 и∆существует вектор J0 ∈ V такой, что J0 + ui ∈ V, где ui – любой баmзисный вектор пересечения ker A ∩ Z . Пусть заданы две аффинныефункции f1 : V → G1 и f2 : V → G2, которые имеют вид f1 (J ) = A1J ++ B1N + C1 и f2 (J) = A2 J + B2 N + C2; ∆1 и ∆2 – элементы множества G1и G2 соответственно. Множество V∆1∩V∆2будем называть невырож-денным, если dim(ker A1 ∩ ker A2 ≠ 0 и существует вектор J0 ∈ V∆2∆1∩∩ V такой, что J0 + ui ∈ V где ui – любой базисный вектор пересечеmния ker A1 ∩ ker A2 ∩ Z .Пусть индексы элементов l-го массива, встречающегося в операторе Sβ и относящегося к q-му входу элементов этого массива в оператор, выражаются аффинной функцией Fl ,β,q : Vβ → Wl ; зависимостьоперации Sβ(J) от операции Sα(I) задается аффинной функциейΦ α ,β : Vα ,β → Vα , Vα,β ⊆ Vβ.Распределение операций и массивов данных в r-мерном пространстве виртуальных процессоров зададим соответственно аффиннымифункциями cξ(β ) : Vβ → Z, 1 ≤ β ≤ K и d ξ( l ) : Wl → Z, 1 ≤ l ≤ L, 1 ≤ ξ ≤ r.Порядок выполнения операций процессорами (таймирование) зададимаффиннымифункциямиt ξ(β) : Vβ → Z, 1 ≤ β ≤ K , 1 ≤ ξ ≤ n − r ,гдеn = max max nβ .

Векторы (c1(β ) ( J ), ..., cr(β ) ( J )), ( d1(l ) ( F ), ..., d r(l ) ( F )) и1≤β≤ K(t1(β) ( J ), ...,cn(β−)r ( J )) будем обозначать (c (β ) ( J ), (d (l ) ( F ) и (t (β) ( J ) соответственно.Функции cξ(β ) , d ξ(l ) и t ξ(β) являются одним из основных инструмен14тов исследований в методах статического распараллеливания программ[1–6].Условия отсутствия коммуникаций между процессорами можно вобщем виде выразить равенствами cξ(β ) ( J ) − d ξ( l ) ( Fl ,β, q ( J )) = 0, J ∈ Vβ .Выполнение этих условий для всех l, β, q, ξ означает, что для любогозначения вектора параметров цикла J расстояние между процессором,в котором выполняется операция, и процессором, в локальной памятикоторого хранится необходимый для выполнения операции элементмассива, равно нулю.

Следовательно, нет необходимости в обменахданными между процессорами. Если условия выполняются не для всехl, β, q, ξ, то требуется обмен данными в процессе выполнения программы.Рассмотрим часто встречающиеся виды коммуникаций: точкаточка, бродкаст, трансляция. Коммуникация точка-точка – это обменданными между двумя процессорами, в одном из которых данное хранится, а в другом используется как аргумент или вычисляется. Бродкаст (одновременное распространение) – это обмен данными междугруппой процессоров, в одном из которых данное хранится, а в другиходновременно (на одной итерации) используется как аргумент.

Трансляция – это передача данного от процессора к процессору в случае,если данное используется в разных процессорах по очереди.На параллельных компьютерах с распределенной памятью желательно вместо большого количества коммуникаций точка-точка организовывать более быстрые коммуникации, такие как бродкаст и трансляция данных. Задачей данной работы является получение условий длявыявления возможности организации таких коммуникаций и установление схемы обмена данными между процессорами.2. Организация бродкаста и трансляции данныхОбозначим через P(z1, …, zr) процессор, размещенный в точке (z1,…, zr) пространства виртуальных процессоров. Согласно функциямd ξ(l ) , cξ(β ) и t ξ(β) данные al ( Fl ,β,q ( J )) хранятся в локальной памятипроцессоров P (d ( l ) ( Fl ,β,q ( J ))) и используются на итерациях t (β ) ( J ) впроцессорах P (c (β ) ( J )).Будем обозначать матрицу A в аффинных функциях Fl ,β,q , Φ α ,β ,15(β, ξ)cξ(β) и t ξ(β) через Fl,β,q, Φα,β, πиτ(β, ξ)соответственно.

Обозначим(β)(β, ξ),через Π – матрицу, строки которой составлены из векторов π(β)1 ≤ ξ ≤ r, через T – матрицу, строки которой составлены из векторов(β, ξ)τ , 1 ≤ ξ ≤ n – r.ПустьF–элементмножестваWl .ОбозначимVl (,βF, q) == {J ∈Vβ | Fl ,β,q ( J ) = F } – множество итераций исходного гнезда циклов, на которых на q-м входе массива al в оператор Sβ используетсяодно и то же данное al(F). Пусть T – элемент множества значений вектора t (β ) ( J ). Обозначим Vβ(T ) = {J ∈ Vβ | t (β ) ( J ) = T } – множество итераций исходного гнезда циклов, на которых выполняется оператор Sβ икоторые реализуются в пространстве виртуальных процессоров на итерации T. Будем еще рассматривать множество Vl (,βF,q) ∩ Vβ(T ) .Обозначим через U l(,ββ),q матрицу, столбцы которой составлены из(β)nбазисных векторов пересечения ker Fl,β,q ∩ ker T ∩ Z β.В следующем утверждении сформулированы условия, определяющие возможность организации бродкаста данных.Утверждение 1.

На итерации T можно организовать бродкаст данного al(F) от процессора P (d ( l ) ( F )) к процессорам P(c (β) ( J )),J ∈ Vl (,βF,q) ∩ Vβ(T ) , если функция Fl ,β,q встречается в правой части оператора Sβ, множество P (c (β ) ( J )), J ∈ Vl (,βF,q) ∩ Vβ(T ) , является невырожденным, и выполняется одно из следующих условий:а) массив al встречается только в правых частях операторов алгоритма,б) для истинной зависимости, порожденной q-м входом массива alв оператор Sβ и задаваемой функцией зависимостей Φ α ,β выполняетсяусловие Φ α ,βU l(,ββ),q = 0.Обозначим через Ul,β,q матрицу, столбцы которой составлены изn(β)базисных векторов пересечения ker Fl,β,q ∩ Z β; через U матрицу,столбцы которой составлены из базисных векторов пересечения ker16(β)Tn∩ Z β; через Ti различные значения t (β) ( J ), J ∈ Vl (,βF,q) .В следующих утверждениях сформулированы условия, определяющие возможность организации трансляции данного.

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

Передача данного осуществляется наодной итерации, но со сдвигом по времени при выполнении программы.Утверждение 2. На итерациях Ti можно организовать трансляциюданного al(F) между процессорами P (c (β ) ( J )), J ∈ Vl (,βF,q) ∩ Vβ(T ) , еслифункция Fl ,β, q встречается в правой части оператора Sβ, множество(β)Vl (,βF,q) является невырожденным, выполняются условия TUl,β,q ≠ 0,⎛ Fl ,β, q ⎞(β)Π Ul,β,q ≠ 0, rank ⎜⎜ (β ) ⎟⎟ = nβ и одно из следующих условий:⎝T ⎠а) массив al встречается только в правых частях операторов алгоритма,б) для истинной зависимости, порожденной q-м входом массива alв оператор Sβ, и задаваемой функцией зависимостей Φ α ,β выполняетсяусловие Φ α ,βU l(,ββ),q = 0.Утверждение 3.