Применение OpenMP для распараллеливания задачи с использованием сеточных методов

Создать новую статью

04.10.2009 14:00


Аннотация

Целью проекта TBB являлось изучение применения библиотеки TBB при разработке параллельных программ на общей памяти. Для сравнения использовалась библиотека OpenMP. Сравнение проводилось по следующим параметрам: трудоемкость и сложность разработки программы, затраченное время, производительность и ускорение полученного программного продукта. В качестве задачи была взята модель работы сердца человека, представляющая собой систему дифференциальных уравнений. Результатом проекта стало сравнение используемых технологий и рекомендации по применению TBB и реализованных в ней алгоритмов.

Введение

Проект TBB был нацелен на сравнение возможностей библиотеки TBB с OpenMP по таким критериям, как время, потраченное на разработку программного кода; трудоемкость и сложность разработки; производительность полученного программного продукта. В качестве задачи для распараллеливания была взята модель работы человеческого сердца. В терминах математического описания данная модель представляет собой систему дифференциальных уравнений (ДУ), которые характеризуют состояние клеток сердца человека. Моей задачей было решение данной системы в общем виде, а также разработка программы решения системы ДУ с использованием OpenMP. В результате полученное общее решение системы ДУ позволило сгенерировать наборы начальных данных и конечных состояний для них, на основании которых можно сделать вывод о правильности реализации программы. Реализованные мной алгоритмы на OpenMP позволили сделать сравнение алгоритмов, представленных другими участниками проекта на TBB. Таким образом, были достигнуты ключевые цели проекта.

Основная часть

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

Модель работы сердца человека

Переменные u и v представляют собой параметры, характеризующие состояние клетки человеческого сердца, а коэффициенты D1 и D2 - связь клеток друг с другом (в культуре клеток). Соответственно возникла необходимость нахождения общего решения данной системы, что позволило в дальнейшем составить набор тестовых данных для проверки правильности работы программы. На рисунках 1 и 2 показано качественное поведение системы для упрощенного случая с отсутствующими связями:

Состояние равновесия

Рис.1 Состояние равновесия

Цикл

Рис.2 Цикл

Существует два состояния клеток сердца человека:

  1. Устойчивое (или состояние равновесия) (рис.1)
  2. Постоянного сокращения (или цикл) (рис.2)

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

Полученное общее решение и выведенные из него частные, позволили составить наборы данных для тестирования правильности вычислений параллельной программы. В ходе решения был изучен и задействован математический пакет Waterloo Maple.

Для численного решения системы ДУ была составлена разностная схема следующего вида:

Разностная схема

Следующей задачей была разработка параллельной программы решения данной системы ДУ с использованием библиотеки OpenMP. Для решения системы ДУ был выбран сеточный метод, в котором при вычислении параметров клетки на текущем временном шаге требуются параметры четырех ее геометрических соседей (рис. 3 иллюстрирует сказанное).

Схема зависимости данных

Рис.3 Схема зависимости данных

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

#pragma omp parallel shared(init_val,next_val,param), private(x,y)
{
#pragma omp for schedule(dynamic,chunk) nowait
	for(y=1; y <= static_cast<long>(init_val->height()); ++y)
	{
		for(x=1; x <= static_cast<long>(init_val->row_width(y)); ++x)
		{
			uv_pair<T> init_x_1y = init_val->at(x-1,y);
			uv_pair<T> init_x1y = init_val->at(x+1,y);
			uv_pair<T> init_xy_1 = init_val->at(x,y-1);
			uv_pair<T> init_xy1 = init_val->at(x,y+1);
			uv_pair<T> init_xy = init_val->at(x,y);
			T init_u = init_xy.u;
			
			next_val->at(x,y).u = init_u + tau*(init_u - pow(init_u,3.0)/3.0 -
				init_xy.v) + tau*(param->u_D->at(x,y)/h) * 
					(init_x_1y.u + init_x1y.u + init_xy_1.u + init_xy1.u - 4.0*init_u);
			
			next_val->at(x,y).v = init_xy.v + tau*param->v_eps*(init_u-param->v_a->at(x,y)) + 
				tau*(param->v_D->at(x,y)/h) * 
				(init_x_1y.v + init_x1y.v + init_xy_1.v + init_xy1.v - 4.0*init_xy.v);
		}
	}
}

В данном листинге приведена ключевая часть кода счетного шага по времени. При помощи директивы OpenMP структуры параметров U и V объявляются доступными для всех потоков. После этого в директиве распараллеливания внешнего цикла указывается динамический режим планирования работы потоков. Управление планированием осуществляется при помощи указания размера итераций цикла, выполняющихся внутри каждого потока. Изменяя данный параметр, можно добиться оптимальной загруженности процессора во время счета задачи. Так же вместо schedule (dynamic, chunk) можно использовать schedule (guided, chunk), что также дает хороший результат. Тестовые запуски показали, что для данной задачи schedule (dynamic,chunk) дает лучший результат (переменная chunk вычисляется после каждого счетного шага).

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

Схема распараллеливания по времени

Рис.4 Схема распараллеливания по времени

Приведена схема разбиения матриц параметров для 4-х потоков и 3-х временных шагов (красные линии – актуальные данные, оранжевые пунктирные – дополнения для пересчета параметров). Рассмотрим детально схему распределения данных на примере 0-го потока. Светлый квадрат в левом верхнем углу рисунка, актуальные данные для потока. Для того чтобы можно было рассчитывать значения параметров независимо от других потоков (без обменов после каждой итерации по времени), актуальные данные нужно дополнить соседними. Эти дополняющие данные (темное окаймление), которые получил бы поток после 3-х шагов по времени от своих соседей в случае постоянных обменов данными, будут устаревать по одной линии после каждого временного шага. Основная сложность при этом заключается в сохранении целостности данных при «обрезке» границ исходных матриц, разработке специальных структур хранения данных для этих целей, а так же создании нового оптимизированного алгоритма расчета одного счетного шага по пространству и времени. Требования к структурам заключаются в быстроте работы с ними, так как очевидно, что при большом объеме входных данных операции изменения размеров матриц будут довольно частыми. Так же требуется дополнительное введение переменных, в которых хранятся данные о количестве итераций до синхронизации данных всей задачи вцелом. Отсюда возникает вопрос о равномерной загруженности всех потоков, так как операция синхронизации требует, чтобы синхронизируемые данные были достоверными и правильными (с одного и того же временного шага). Решение данного вопроса напрямую связанно с разработкой алгоритма расчета одного счетного шага, т.е. переходе от многомерных вложенных циклов к одномерному с сохранением правильности вычислений и использовании алгоритмов планирования, предоставляемых библиотекой OpenMP. Данные задачи были успешно решены, и получен оптимизированный алгоритм, показавший заметно лучшие результаты по сравнению с первоначальным.

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

Рис.5 График времени выполнения первого алгоритма на малых объемах данных

Рис.6 График времени выполнения первого алгоритма на больших объемах данных

Следующие графики замеров времени выполнения оптимизированного алгоритма:

Рис.7 График времени выполнения оптимизированного алгоритма на малых объемах данных

Рис.8 График времени выполнения оптимизированного алгоритма на больших объемах данных

Рис.9 Сравнительный график времени выполнения оптимизированного и не оптимизированного алгоритмов при малых объемах данных

Рис.10 Сравнительный график времени выполнения оптимизированного и не оптимизированного алгоритмов при больших объемах данных

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

Заключение

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

Об авторе

Раткевич Ирина Сергеевна, студентка 3 курса экономико-математического факультета, кафедры «Информационные системы в экономике» Саровского Физико-Технического Института (в настоящее время Национального Исследовательского Ядерного Университета). Участница проекта MPI и менеджер проекта ISPS4U совместной лаборатории СарФТИ и Интел BiPro. Участница конференций:

  • Математика и математическое моделирование 2008 «Разработка параллельной программы численного интегрирования функции 2-х переменных на заданной области с заданной точностью» - 3е место;
  • Молодежь в науке 2008 «Разработка параллельной программы численного интегрирования функции 2-х переменных на заданной области с заданной точностью и заданным методом»;
  • Научная сессия МИФИ 2009 «Разработка параллельной программы численного интегрирования функции 2-х переменных на заданной области с заданной точностью и заданным методом (с постановкой проблемы балансировки вычислительной нагрузки на счетные узлы)»;
  • Научная сессия МИФИ 2009 «Основные проблемы Закрытых Административно-Территориальных Образований»;
  • Математика и математическое моделирование 2009 «Исследование алгоритмов балансировки применимых к параллельному алгоритму численного интегрирования функции двух переменных» - 3е место;
  • Математика и математическое моделирование 2009 «Анализ современных социальных сетей и сервисов» - 2е место;
  • Математика и математическое моделирование 2009 «Основные противоречия и возможные пути развития Закрытых Административно-Территориальных Образований»;
  • «Нижегородская сессия молодых ученых».

Список литературы

  1. Осипов Г.В. «Моделирование сердечной активности»