РАЗДЕЛ 2
ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РАЗЛИЧНЫХ ТОПОЛОГИЙ ПРИ РЕШЕНИИ НЕЛИНЕЙНОЙ ЗАДАЧИ КОШИ ЯВНЫМИ ОДНОШАГОВЫМИ МЕТОДАМИ
Современные исследования и вычислительные эксперименты в области высокопроизводительных вычислений показывают, что практически все новые параллельные методы, даже те из них, которые эффективны в теоретическом отношении, на практике не конкурентно способны. Поэтому на текущий момент единственно надежным источником создания параллельных методов является подходящая реструктуризация проверенных временем последовательных алгоритмов [3].
Численно решается задача Коши для системы обыкновенных дифференциальных уравнений (СОДУ) первого порядка с известными начальными условиями:
(2.1)
Явный s-стадийный одношаговый метод Рунге-Кутты может быть определен следующим образом:
(2.2)
Рассмотрим различные вычислительные схемы параллельных алгоритмов на базе ЯМРК для СОДУ общего типа с учетом встроенных методов оценки локальной апостериорной погрешности.
2.1. Эффективность распараллеливания явных одношаговых численных схем с дублированием шага по правилу Рунге
При распараллеливании алгоритма решения нелинейной задачи Коши на основе ЯМРК с использованием правила Рунге, воспользуемся иерархической декомпозиционной методикой. Первоначально вычислительная задача разбивается на подзадачи, анализируются информационные взаимосвязи между ними, биективно к множеству подзадач определяется множество макроопераций, оценивается эффективность потенциального крупно или среднеблочного параллелизма. Затем методика применяется для распараллеливания каждой из макроопераций, то есть используется мелкозернистый параллелизм. Для разработки параллельного алгоритма и проверки корректности его построения на каждом из уровней используется математический аппарат графов влияния [3-5].
Один шаг интегрирования СОДУ на основе ЯМРК с встроенным способом оценки локальной погрешности по правилу Рунге имеет вид:
(2.3)
Последовательный алгоритм, описываемый вычислительной схемой (2.3), можно представить, как решение трех подзадач вычисления аппроксимаций решения: , , . Все эти задачи являются применением явной одношаговой схемы, что позволяет ввести в качестве основной макрооперации - однократное вычисление аппроксимации решения в некоторой точке сетки с заданным шагом интегрирования. Рассмотрим три различные макрооперационные схемы исследуемого алгоритма (рис. 2.1). Первый вариант макрооперационной схемы конструируемого параллельного алгоритма представлен на рисунке 2.1а). Все три подзадачи выполняются последовательно, данные между процессорами распределены равномерно, .
Рис. 2.1. Графы влияния макрооперационных вычислительных схем параллельного ЯМРК в сочетании с правилом Рунге, а) схема № 1, б) схема № 2 (равномерное разбиение), в) схема № 3 (пропорциональное разбиение)
Второй вариант представлен на рисунке 2.1б). Первая и вторая подзадачи выполняются параллельно, множество процессоров разделено на две равные части: . Третий вариант (рис. 2.1в) предполагает параллельное выполнение первой подзадачи на меньшем числе процессоров, второй и третьей - на большем числе процессоров. Множество процессоров делится на две пропорциональные части: . На этом уровне детализации очевидно, что вторая схема хуже, чем первая, хотя для нее . Перейдем к исследованию параллелизма на уровне отдельных операций, т.е. к мелкозернистому параллелизму. Параллельное решение СОДУ на базе ЯМРК концентрируется на выполнении одного шага интегрирования. В качестве первой макрооперации выделяется вычисление -того стадийного коэффициента, а в качестве второй - вычисление численной аппроксимации решения в некоторой точке. На рисунке 2.2 приведен граф влияния первой макрооперации [38-39].
Рис. 2.2. Граф влияния для вычисления того стадийного
коэффициента ЯМРК для СОДУ ,
Вторая макрооперация определяет вычисление приближенного решения на некотором шаге интегрирования и при имеющемся разбиении данных представлена графом влияния, изображенным на рис. 2.3. Обе макроперации являются базовыми для всех явных схем и будут использованы в дальнейшем при рассмотрении альтернативных способов определения локальной погрешности.
Рис. 2.3. Граф влияния второй макрооперации: вычисление
численной аппроксимации решения в точке
Чтобы задача построения параллельных алгоритмов стала математически корректной, необходимо сделать предположения относительно свойств параллельной вычислительной системы. Применим концепцию неограниченного параллелизма [4]. В качестве идеализированной модели параллельной ВС используется мультикомпьютер с распределенной памятью и коммутационной схемой произвольной топологии.
Рис. 2.4 представляет отображение первой макрооперационной схемы параллельного алгоритма ЯМРК c правилом Рунге на мультикомпьютер из p процессоров. Для СОДУ, состоящей из уравнений, на одном временном шаге компонент векторов и, соответственно, стадийных коэффициентов могут быть вычислены параллельно. Причем: 1) при ; 2) при . Определение аппроксимаций решения и переход к следующему шагу не требуют дополнительных передач данных.
Рис. 2.4. Параллельный алгоритм ЯМРК + правило Рунге для
численного решения нелинейной задачи Коши (вариант 1)
Рисунок 2.5 описывает алгоритм решения той же задачи Коши для третьей макрооперационной схемы. Здесь разбиение процессоров произведено пропорционально объему вычислений. Базовая макрооперация описана графом влияния на рисунке 2.2. Первая группа процессоров вычисляет две аппроксимации решения: и и имеет размер процессорного поля в два раза больше, чем вторая группа. Вторая группа процессоров вычисляет одну аппроксимацию решения с удвоенным шагом: .
Рис. 2.5. Параллельный алгоритм ЯМРК+ правило Рунге
(пропорциональное распределение данных по процессорам)
Каждый процессор первой гр