Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003

Сведение численной модели к методу прогонки, предварительно апроксимируя систему уравнений разностными схемами дает довольно существенный прирост в производительности, почти не сказываясь при этом на точности полученых результатов. Распареллеливание задач с использованием метода прогонки уже является достаточно изученой областью программирования [2]. В данное время рассматриваются варианты реализации схемы прогонки на распределенных вычислительных системах с использовапнием программного обеспечения MPI [3].

Литература

1.Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. Алгебродинамический подход. Киев: Наукова думка, 2000. 177 с.

2.Параллельные вычисления / Под ред. Г. Родрига: Пер. с англ. // Под ред. Ю.Г. Дадаева. – М.: Наука, 1986. 376 с.

3.Немнюгин С.А. Стесик О.Л. Параллельноге программирование для многопроцессорных вычислительных систем. СПб: БХВПетербург, 2002. 400 с.

4.Довгий С.А., Прусов В.А., Копейка О.В. Использование геоинформационных технологий в системах охраны окружающей среды и исследования природных ресурсов т. 4. К.: Наукова думка, 2000.

5.Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.

APT – СИСТЕМА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ ЯЗЫКА С ДИНАМИЧЕСКИМИ МАССИВАМИ.

КОНЦЕПЦИЯ И ЯЗЫК

А.Р. Уразов

Новосибирский государственный технический университет

1. Цели проекта

APT – Automatic Parallelization Tool или средство автоматического распараллеливания. Действительно, основной целью проекта является

221

обеспечение высокой степени автоматизации параллельного программирования численных алгоритмов. Система опирается на характерное свойство численных методов – регулярную обработку больших массивов данных. Именно для таких алгоритмов может быть произведено эффективное автоматическое распараллеливание по данным [1], [2].

Ключевыми при создании системы явились следующие требования:

•сохранение привычной парадигмы последовательного программирования, использование широко распространенного языка;

•неявное с точки зрения программиста использование ресурсов многопроцессорного вычислительного комплекса;

•обеспечение автоматической настройки на ресурсы вычислительной системы, в том числе и выполнение динамической балансировки нагрузки [1].

2. Основные проектные решения

В основу системы программирования положены широко используемые языки программирования С/С++, которые расширяются небольшим набором дополнительных средств, необходимых для генерации эффективных параллельных программ.

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

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

222

искусственного интеллекта LISP [7] и Prolog [8]. Многие языки сценариев, такие как Python [9], позволяют манипулировать динамическими контейнерами, динамические типы данных используются в проблемно-ориентированных языках, таких как SQL или MATLAB. Объединяет все разновидности динамических типов одно свойство – избавление программиста от забот по распределению памяти. В системе APT, ориентированной на применение в численных методах, наиболее используемый тип данных – массив. Понятие динамического массива здесь расширяется в соответствии с необходимостью использования параллельных вычислительных систем и скрывает от программиста особенности распределения элементов массива по узлам вычислительной системы. В этом смысле динамические (виртуальные) массивы APT сродни аппаратной поддержке виртуальной памяти. В обоих случаях реальное распределение данных маскируется, а доступ осуществляется по логическим адресам.

Наряду с концепцией виртуального массива возникает еще одной понятие – понятие редукционной переменной. Редукционные переменные используются для накопления значений, зависящих от набора элементов виртуальных массивов. Например, для суммирования элементов виртуального вектора нужно использовать редукционную переменную типа «сумма». Аналогично, редукционная переменная типа «сумма» потребуется при вычислении скалярного произведения, если хотя бы один из векторов объявлен как виртуальный.

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

3. Использование APT

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

223

параллельного программирования для архитектур с распределенной памятью.

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

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

1.внесение инструкций параллельной обработки:

•описание виртуальных массивов;

•описание редукционных переменных;

2.разбиение программы на секции:

•инициализация;

•вычисления;

•вывод результатов.

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

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

Следующий шаг после определения виртуальных массивов – описание редукционных переменных. Редукционные переменные помимо типа данных характеризуются еще и типом редукции, который может принимать одно из следующих значений: product, sum, min, max, and, or, xor. Операции, результат которых зависит от цепочек

224

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

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

Чтобы подробно не рассматривать все инструкции языка, использование системы поясняется примером. Для демонстрации на языке C была запрограммирована последовательная версия метода сопряженных градиентов [10] для плотных матриц. Метод широко применяется в современном численном моделировании и вместе с тем достаточно прост, чтобы служить в качестве примера. Исходными данными являются матрица системы A, вектор правой части b и произвольное начальное приближение вектора неизвестных x. Алгоритм вырабатывает приближенное решение x СЛАУ Ax = b. В ходе работы алгоритма используются вспомогательные векторы r, p, ap. Последовательный код приводится в следующем листинге:

//матрица СЛАУ double a[n][n];

//вектор правых частей и вектор неизвестных double b[n], x[n];

//невязка

double r[n];

//векторы, требуемые алгоритмом double p[n], ap[n];

//вычисление невязки

for (size_t i = 0; i<n; i++) { double t = b[i];

for (size_t j = 0; j<n; j++) t -= a[i][j]*x[j]; r[i] = t;

}

double rr = 0;

225

for (size_t i = 0; i<n; i++) rr += r[i]*r[i]; while (rr>threshold) {

//alpha = (r, r)/(Ap, p) double app = 0;

for (size_t i = 0; i<n; i++) { double t = 0;

for (size_t j = 0; j<n; j++) t += a[i][j]*p[j]; ap[i] = t;

app += t*p[i];

}

double alpha = rr/app;

//x = x+alpha*p

for (size_t i = 0; i<n; i++) x[i] += alpha*p[i]; // r = r-alpha*Ap

for (size_t i = 0; i<n; i++) r[i] -= alpha*ap[i];

//beta = (r_new, r_new)/(r_old, r_old) double rr_old = rr;

rr = 0;

for (size_t i = 0; i<n; i++) rr += r[i]*r[i]; double beta = rr/rr_old;

//p = r+beta*p

for (size_t i = 0; i<n; i++) p[i] = r[i]+beta*p[i];

};

Алгоритм представляется последовательностью операций линейного комбинирования векторов, вычислений матричновекторных произведений и скалярных произведений векторов. Все эти операции отвечают критериям регулярности обработки, и соответствующие массивы могут быть объявлены распределяемыми. При этом операции вычисления скалярного произведения превращаются в операции сборки значений редукционных переменных. Листинг соответствующей параллельной программы приводится ниже:

// матрица СЛАУ

dynamic double a[n:distributable][n];

// вектор правых частей и вектор неизвестных

226

dynamic double b[n:distributable], x[n:distributable]; // невязка

dynamic double r[n:distributable]; // векторы, требуемые алгоритмом

dynamic double p[n:distributable], ap[n:distributable];

// вычисление невязки

for (size_t i = 0; i<n; i++) { double t = b[i];

for (size_t j = 0; j<n; j++) t -= a[i][j]*x[j]; r[i] = t;

}

reduction sum double rr;

for (size_t i = 0; i<n; i++) rr = reduce(r[i]*r[i]);

while (rr>threshold) {

// alpha = (r, r)/(Ap, p) reduction sum double app = 0; for (size_t i = 0; i<n; i++) {

double t = 0;

for (size_t j = 0; j<n; j++) t += a[i][j]*p[j]; ap[i] = t;

app = reduce(t*p[i]);

}

double alpha = rr/app; // x = x+alpha*p

for (size_t i = 0; i<n; i++) x[i] += alpha*p[i]; // r = r-alpha*Ap

for (size_t i = 0; i<n; i++) r[i] -= alpha*ap[i]; // beta = (r_new, r_new)/(r_old, r_old)

double rr_old = rr; rr = 0;

for (size_t i = 0; i<n; i++) rr = reduce(r[i]*r[i]); double beta = rr/rr_old;

// p = r+beta*p

for (size_t i = 0; i<n; i++) p[i] = r[i]+beta*p[i];

227

};

4. Обзор архитектуры системы

Система состоит из двух компонентов: модуля сборки программ и библиотеки поддержки времени выполнения.

Вобязанности модуля сборки входят следующие функции:

1)предобработка программ на APT-C/C++:

•обработка специальных инструкций языка APT;

•анализ и распараллеливание циклов, переменные которых индексируют распределяемые измерения виртуальных массивов;

•генерация информации о некоторых аспектах размещения виртуальных массивов для более эффективной работы;

2)компилирование полученной программы на C++ и компоновка с библиотекой поддержки времени выполнения.

5. Текущее состояние проекта

На данный момент спроектирована базовая версия языка, определены требования к функциональности библиотеки поддержки и согласован ее интерфейс. Сейчас ведется разработка компилятора и модуля поддержки. Первую комплексную проверку системы планируется провести на задаче моделирования гравитационной динамики многих тел методом частиц в ячейках [2], [3].

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

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

228

структуры данных и алгоритмы так, чтобы было возможным распараллеливание по данным».

Литература

1.Вальковский В.А., Малышкин В.Э. Синтез параллельных программ и систем на вычислительных моделях. Новосибирск:

Наука, 1988.

2.Kraeva M.A., Malyshkin V.E. Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers. In the International Journal on Future Generation Computer Systems (Elsevier). Vol. 17, issue 6, p.755-765, 2001.

3.Вшивков В.А., Малышкин В.Э., Снытников А.В., Снытников В.Н. Численное моделирование гравитационной динамики многих тел методом частиц в ячейках: параллельная реализация // Сибирский журнал вычислительной математики, № 1, 2003. С. 25-36.

4.Коновалов Н., Крюков В. Параллельные программы для вычислительных кластеров и сетей // Открытые системы, #03/2002. http://www.osp.ru/os/2002/03/012.htm.

5.DVM система. http://dserv.keldysh.ru/dvm/.

6.OpenMP C and C++ Application Program Interface. Version 2.0 March 2002. http://www.openmp.org.

7.David S. Touretzky. Common Lisp: A Gentle Introduction to Symbolic Computation. http://www-2.cs.cmu.edu/~dst/LispBook/index.html.

8.Братко И. Программирование на языке Пролог для искусственного интеллекта / Пер. с англ. – М.: Мир, 1990.

9.Python Language Webpage. http://www.python.org/.

10.Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2000. – 70с.

229

ДЕКОМПОЗИЦИЯ ПО ДАННЫМ В ЗАДАЧАХ ИТЕРАЦИОННОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

В.А. Фурсов, М.А. Дроздов

Самарский государственный аэрокосмический университет им. С.П. Королева

Институт систем обработки изображений РАН, г.Самара

1. Введение

Ряд задач обработки изображений на многопроцессорных системах допускает распараллеливание по данным [1]. В частности, в работе [2] рассматривалась схема разбиения большого изображения на фрагменты при итерационной обработке изображения фильтром с бесконечной импульсной характеристикой (БИХ-фильтром).

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

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

При разбиении исходного изображения на квадраты одинаковых размеров для фрагментов, расположенных на границах декомпозируемого изображения, длина границ, сопряженных с соседними фрагментами, а, следовательно, и объем передаваемых данных будет меньше. Указанное различие во времени передачи данных может оказывать существенное влияние на эффективность использования процессоров однородного кластера, если скорость передачи данных низкая. Неэффективность использования

230