Применение языка НОРМА для интегрирования уравнения Пуассона с переменными коэффициэнтами на параллельных ЭВМ

Андрианов А. Н., Ефимкин К. Н., Зыбин С. В.
Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. Тезисы докл. Междунар. математич. конф 1997. Вып.1. С. 3-4.

      Рассматриваются вопросы применения декларативного (непроцедурного) языка НОРМА для решения двумерного уравнения Пуансона в цилиндрических координатах на неравномерной сетке, возникающего в задаче 6 распространении стримера в катодном слое.
      Язык НОРМА является средством, предназначенным для спецификации численных методов решения задач математической физики на вычислительных системах (ВС) с параллельной архитектурой. Он фактически позволяет автоматизировать фазу программирования, которая необходима при переходе от расчетных формул, заданных прикладным специалистом, к программе для конкретной ЭВМ.
      Между расчетными формулами и записью алгоритма на НОРМЕ нет существенной разницы — эти формулы являются исходной информацией для транслирующей системы. Такое описание сохраняет естественный параллелизм задачи, оно не содержит никаких ограничений, связанных с желанием приспособить программу к той или иной параллельной архитектуре ВС или особенностями языка программирования. В записи на НОРМЕ не требуется никакой информации о порядке счета, способах организации вычислительных (циклических) процессов. Порядок предложения языка может быть произвольным — информационные взаимосвязи выявляются и учитываются транслятором при организации вычислительного процесса. В результате достигаются следующие цели:
      — высокая автоматизация разработки прикладных программ (разработчик работает преимущественно в терминах расчетных формул прикладной области);
      — создание надежных прикладных программ (если правильно записаны расчетные формулы, то гарантируется получение правильной выходной программы);
      — обеспечение мобильности записи алгоритмов на НОРМЕ (учет особенностей архитектуры ВС осуществляется синтезирующим транслятором для языка НОРМА).
      В данной работе язык НОРМА применяется для записи параллельного алгоритма решения двумерного уравнения Пуассона в цилиндрических координатах методом верхней релаксации с красно-черным разбиением. Использование языка НОРМА позволило автоматически получить выходную программу на Фортране для IBM PC, для одного узла (с общей памятью) параллельной вычислительной системы CONVEX SPP1000 и программу на Фортране GNS для параллельной системы на процессорах 186ОХР с распределенной памятью и системой передачи сообщений (message passing). При этом исходная программа на НОРМЕ фактически не менялась; в последнем случае в текст программы достаточно добавить задание числа процессорных элементов, на которых желательно выполнить программу. Программирование на НОРМЕ не требует от прикладного специалиста знания сложного механизма передачи сообщений — организация вычислений и взаимодействия между параллельными задачами автоматически выполняется транслятором НОРМЫ.
      Полученные результаты дают основание полагать, что применение языка НОРМА при решении задач вычислительной физики позволит значительно снизить затраты на разработку высокоэффективных алгоритмов их решения, в особенности на параллельных ЭВМ.

      Рассмотрены параллельные алгоритмы интегрирования задачи Коши для системы обыкновенных дифференциальных уравнений (ОДУ), реализуюшие крупномасштабный параллелизм по времени за счет применения итерационных процессов, и в частности, алгоритмы на основе дискретной свертки.
      Параллелизм этих алгоритмов основан на преобразовании исходного ОДУ к эквивалентному интегральному уравнению и последующем его решении посредством итераций на подинтервалах по времени, называемых блоками. Длина этих подинтервалов обычно значительно больше шага сетки, используемой при вычислении интеграла, благодаря чему достигается крупномасштабный параллелизм, состоящий в одновременном вычислении на каждой итерации значений подинтегральной функции в узлах сетки. Такие методы ранее не использовались на однопроцессорных ЭВМ, так как требуют O(n²) операций, где n — количество узлов сетки. С появлением параллельных ЭВМ ситуация изменилась, так как на п процессорах итерационные методы требуют лишь O(logn) операций.
      В большинстве параллельных алгоритмов итерационного типа, называемых также waveform relaxation methods, основное внимание уделяется распараллеливанию по блокам или при вычислении подинтегрльной функции. В данной работе преимущественно рассматриваются алгоритмы, позволяющие дополнительно использовать потенциальный параллелизм дискретной свертки. Эти алгоритмы основаны на приближенном итерационном методе Ньютона-Канторовича и являются подобными алгоритмам типа shifted Picard splitting. Основная идея заключается в решении линейных ОДУ на каждой итерации посредством вычисления интеграла свёртки. После дискретизации по формулам Грегори интеграл свертки может быть вычислен при помощи параллельных алгоритмов дискретной свертки или же специальных процессоров (сигнальных или конвейерных).
      Полученные теоретические результаты включают исследование свойств сходимости, аппроксимации и устойчивости используемых алгоритмов, получение оценок скорости сходимости применяемых итерационных процессов. Исследованы итерационные процессы с кусочно-постоянной аппроксимацией якобиана (основной и модифицированный) и процесс с внутренними итерациями. Также разработана структура их параллельной реализации и построено семейство параметризованных алгоритмов с иерархией уровней параллелизма. Эти результаты позволяют разрабатывать эффективные параллельные алгоритмы интегрирования ОДУ на основе итераций Пикара и приближенных итераций Ньютона.
      В настоящее время создана программа на языке OCCAM для транспьютерной системы, реализующая алгоритмы интегрирования ОДУ на основе итераций Пикара (без свертки) и приближенных итераций Ньютона-Канторовича (с возможностью использования свертки). Выполнено исследование их вычислительных свойств на наборе различных тестовых ОДУ, получены оценки ускорения и эффективности при распараллеливании. Практическая реализация разрабатываемых алгоритмов также была выполнена в виде программы на языке НОРМА с последующей трансляцией в параллельный язык Фортран GNS. Проведено предварительное тестирование сгенерированной программы с распределением задач по процессорам и поддержкой коммуникаций на параллельной ЭВМ с процессорами i860XP.