научная статья по теме ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ТОЧЕК ГИПЕРПЛОСКОСТИ ФРОНТА ВЫЧИСЛЕНИЙ Математика

Текст научной статьи на тему «ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ТОЧЕК ГИПЕРПЛОСКОСТИ ФРОНТА ВЫЧИСЛЕНИЙ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 1, с. 145-152

УДК 519.7

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ТОЧЕК ГИПЕРПЛОСКОСТИ ФРОНТА ВЫЧИСЛЕНИЙ

© 2015 г. М. М. Краснов

(125047Москва, Миусская пл., 4 ИПМ РАН) e-mail: kmm@kiam.ru Поступила в редакцию 18.03.2014 г.

Рассматривается параллельный алгоритм вычисления точек гиперплоскости фронта вычислений. Такая необходимость возникает при вычислении значений некоторой величины, определенной на многомерной прямоугольной области. Обычно речь идет о трехмерных областях, но материал изложен в общем виде, когда число измерений не меньше двух. Часто величина не имеет внутренних зависимостей между точками области, в этом случае вычисления в разных точках области производятся независимо, и их можно производить параллельно. Однако иногда внутренние зависимости имеются (например в методе Гаусса—Зейделя решения системы линейных уравнений), в этом случае последовательность обхода точек области важна. Общепринятый подход в этом случае состоит в формировании некоторой гиперплоскости (в трехмерном случае — обычной плоскости, в двумерном случае — прямой) фронта вычислений, которая линейно движется по области под некоторым углом. На каждом шаге движения этой гиперплоскости точки ее пересечения с областью можно обрабатывать независимо, и, следовательно, параллельно, но сами шаги движения гиперплоскости выполняются последовательно. Область пересечения гиперплоскости со всей областью на разных шагах движения гиперплоскости может представлять собой весьма сложную фигуру, а поиск всех точек области, лежащих на гиперплоскости на данном шаге, — нетривиальную задачу. Именно решению этой задачи (вычислению координат точек области, лежащих на пересечении с гиперплоскостью на данном шаге движения этой гиперплоскости) посвящена данная статья. При этом само вычисление можно производить параллельно по точкам гиперплоскости. Библ. 14.

Ключевые слова: фронт вычислений, гиперплоскость, CUDA.

DOI: 10.7868/S0044466915010135

1. ВВЕДЕНИЕ

В настоящее время все большее распространение получают компьютеры с нетрадиционной (не фоннеймановской) архитектурой, содержащие большое количество вычислительных элементов (вычислительных ядер), которое может исчисляться сотнями. Например, современные графические ускорители от компании Nvidia с архитектурой CUDA (см. [1]) содержат около 1.5 тысяч ядер, а в новейших ускорителях XeonPhi от компании Intel (см. [2]) их 240. Для того чтобы более полно использовать эту вычислительную мощность, требуется распараллеливание выполнения программ. С другой стороны, освоение этих новых вычислительных архитектур (особенно CUDA) требует освоения весьма специфических знаний и для математиков, занимающихся разработкой алгоритмов численного моделирования, является весьма непрофильным занятием. Для облегчения освоения новых архитектур разрабатываются программные средства, облегчающие для математиков переход к программированию на новых вычислительных архитектурах. Такие работы ведутся в том числе и в институте прикладной математики им. М.В. Келдыша РАН. Среди таких работ следует упомянуть язык Норма (см. [3]—[7]) и DVM-систему (см. [8]). Автором настоящей статьи также разработана операторная библиотека (см. [9]), предназначенная для решения трехмерных задач математической физики на прямоугольных индексных сетках, работающая в том числе и на графических ускорителях с архитектурой CUDA.

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

10

145

на многомерной сетке, в одних точках зависят, например, от значении той же самой величины в других точках. Зависимости могут быть и более сложными, например, одна величина зависит от другой, а та, в свою очередь, зависит от первой, но в других точках. В качестве примера можно привести метод Гаусса—Зейделя (см. [10]) решения системы линейных уравнений. Общепринятый подход при решении таких задач состоит в формировании некоторой гиперплоскости (в трехмерном случае — обычной плоскости, в двумерном — прямой), ориентированной под некоторым углом по отношению к прямоугольной области и проходящей сквозь область (так называемый "фронт вычислений"). Большое внимание сильно связанным компонентам уделено в языке Норма (см. [6], [7]). В нем, в частности, также реализован алгоритм обхода точек гиперплоскости на каждом шаге ее движения. Данная работа в большой степени основывается на этих результатах. Основное отличие описываемого алгоритма от алгоритма, реализованного в языке Норма, состоит в том, что число рассматриваемых на каждом шаге точек гиперплоскости в описываемом алгоритме определяется до начала движения гиперплоскости, а в языке Норма — на каждом шаге ее движения. Следствием этого является возможная избыточность вычислений на каждом шаге за счет упрощения алгоритма. Избыточность вычислений в случае большого количества процессорных элементов не является критичной. Кроме того, в языке Норма параметры гиперплоскости определяются исходя из отношений между величинами, данный же алгоритм полагает их известными.

2. ПОСТАНОВКА ЗАДАЧИ

Пусть исходная «-мерная область, на которой проводятся вычисления, задана неравенствами

Мк < 4 < Мк, к = 1,..., п. (1)

Пусть имеется несколько (больше нуля) величин, образующих так называемый максимально сильно связанный граф (МССГ), для которых проводятся вычисления на этой области. Пусть и — одна из этих величин. Рассмотрим следующую схему вычислений. Пусть вычисления проводятся в несколько этапов. На первом этапе вычисляются величины в точках, зависящих только от внешних данных. Множество точек, в которых вычисляется величина и на первом этапе, обозначим через 81и. На втором этапе вычисляются величины, зависящие как от внешних данных, так и от значений, вычисленных на первом этапе. Множество точек, в которых вычисляется величина и на

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

областей вычисления величины и: 81и,..., sUk. Вычисление величины и во всех точках области 8'и проводится параллельно, переход от одной области к следующей последовательный. Такие же системы областей строятся для всех других величин, входящих в МССГ.

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

всех точек областей 8'и.

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

Жи(К): лЧ +... + рПп + Ди = К, (2)

где р'и, Ди, К — целые. Будем считать, что коэффициенты р'и гиперплоскости нам известны заранее.

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

Р1и 11 + ... + р"п1п + А и = Ко.

Множество Ж и (2) состоит из точек, в которых вычисление значений величины и зависит только от внешних данных и от значений, вычисленных в точках множества Жи (1) и удовлетворяющих условию

Ри^1 + ... + р"п1п + А и = Ко + 1.

Далее этот процесс продолжим до тех пор, пока не будут вычислены все значения величины и в исходной области. Здесь К0 — начальное значение уравнения гиперплоскости, которое определяется по коэффициентамр 1 и параметрам М, N заданной области.

Пример. Рассмотрим соотношения

Хг,7 = АМ-и+1;Уг-1,7+2), (*)

Х1,7 = /2(Х1+2,7-1; У+3,7-2),

заданные на области 1 < 1 < 7,1 < 7 < 7.

В приведенных ниже таблицах значение в клетке (/, у) указывает номер К соответствующего множества 3К. Например, значение в клетке (4, 4) таблицы величины X, равное 7, означает, что величина X в точке (4, 4) вычисляется на 7 шаге работы модели.

л ^х

1 1 1 1 1 1 1 7 6 5 3 3 3 1 1

1 2 2 2 2 2 2 6 7 7 5 5 4 1 1

1 7 6 4 4 4 3 5 9 8 7 6 6 1 1

1 8 8 7 6 5 5 4 11 10 9 8 7 1 1

1 10 9 9 8 7 6 3 13 12 11 10 9 1 1

1 12 11 10 10 9 8 2 14 13 13 12 11 1 1

1 14 13 12 11 11 10 1 1 1 1 1 1 1 1

1 2 3 4 5 6 7 1 2 3 4 5 6 7

4

Очевидно, что построить систему циклов для эффективного обхода точек множеств 8К очень трудно.

Построим систему множеств с использованием условия принадлежности плоскости, задаваемой уравнением вида

Ж х (К): -I - 2] = К, Ж у (К) : - - 2 7 + 1 = К.

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

Жх(К)

7 6 5 4 3 2 1 7 8 7 6 5 4 3 2

9 8 7 6 5 4 3 6 10 9 8 7 6 5 4

11 10 9 8 7 6 5 5 12 11 10 9 8 7 6

13 12 11 10 9 8 7 4 14 13 12 11 10 9 8

15 14 13 12 11 10 9 3 16 15 14 13 12 11 10

17 16 15 14 13 12 11 2 18 17 16 15 14 13 12

19 18 17 16 15 14 13 1 20 19 18 17 16 15 14

1 2 3 4 5 6 7 1 2 3 4 5 6 7

Ж^К)

В отличие от элементов множеств 8К множества Ж(К) имеют регулярную структуру, что позволяет надеяться на возможность записи последовательности вычислений в виде циклической структуры.

Из приведенных таблиц видно, что на каждом шаге вычислений существует множество точек, в которых величины вычисляются параллельно. Например, значения величины У в точках (1, 7), (3, 6), (5, 5), (7, 4) и значения величины X в точках (2, 6), (4, 5), (6, 4) вычисляются параллельно на шаге К = 8. Все точки, в которых величина X вычисляется параллельно, лежат на одной прямой.

На следующем шаге (при К = 9) вычисляются значения величины Ув точках (2, 6), (4, 5), (6, 4) и Xв точках (1, 6), (3, 5), (5, 4), (7, 3). Все точки, в которых вычисляется величина У(Х) на этом шаге, также лежат на одной прямой.

Предположим, что существует такая гиперплоскость, что можно организовать вычисления, как это показано выше. Введем

Определение. Фронтом вычислений величины и на шаге К назове

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком