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

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

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

Рассматриваемая вычислительная программа моделирует двухмерное нестационарное движение газа через пористый тепловыделяющий элемент, имеющее практическое применение в решении проблемы газового нестационарного охлаждения тепловыделяющих элементов, таких как аварийный энергоблок Чернобыльской АЭС. Отметим некоторые особенности реализации математической модели, используемой в программе [1]. Входные и выходные данные хранятся в шести трехмерных статических массивах, отвечающих за значения температуры, давления и плотности газа, температуры твердой фазы, горизонтальной и вертикальной скоростей фильтрации. Сетка имеет прямоугольную форму, внутри ее располагаются три зоны вычислений, совокупная область которых имеет т-образную форму. Размерность сетки вычислений и количество шагов по времени зависят от значения шага по пространству, который задается в начале программы. В реализованном в программе численном методе значения в узлах сетки текущего временного слоя рассчитываются с использованием значений предыдущего временного слоя. В начале каждой итерации слои меняются местами. Для вычисления значений в узле сетки используются значения соседних узлов. На рисунке 1 изображены шаблоны связей узлов в вычислениях (серым цветом помечена ячейка с вычисляемыми значениями). Шаблон для вычисления значений температуры газа, горизонтальной и вертикальной скоростей фильтрации представлен на рисунке 1а, значений температуры твердой фазы – на рисунке 1б, порядок обхода ячеек узлов сетки изображен на рисунке 1в.

а)                      б)                      в)

Рис. 1. Шаблоны вычислений

Этапы распараллеливания

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

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

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

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

Разделение области расчета. Эффективность работы программы зависит от равномерности загрузки вычислительных узлов. В программе вычислительная нагрузка практически пропорциональна площади области, поэтому для оценки нагрузки использовалась функция S(n) площади области от координаты n. Простой итерационный алгоритм позволяет вычислить область для j-го узла (значение nj), зная значение nj-1, начиная с j=1 до j=k, из условия: S(nj)-S(nj-1)

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

Рис. 2. Схема расчетной области: I – внутренняя область, II – граничная область, III – теневая область

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

Литература

1.        Левин В.А., Луценко Н.А. Течение газа через пористую тепловыделяющую среду при учете температурной зависимости вязкости газа. // Инженерно-физический журнал. – 2006. – Т. 79. – № 1. – С. 35–40.

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

3.        DVM-система [Электрон. ресурс]. ИПМ им. М.В. Келдыша РАН. – Режим доступа: http://www.keldysh.ru/dvm/ dvmhtm1107/rus/index.html