Данная статья предназначена для публикации в сборнике трудов магистрантов

АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ЧИСЛЕННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ ОДУ И ИХ ОТОБРАЖЕНИЕ НА ПАРАЛЛЕЛЬНЫЕ СТРУКТУРЫ

Панченко О.Г.
Донецкий национальный технический университет
E-mail po@donapex.net

Abstract
Panchenko O. Analysis of the parallel numerical methods for decision Cauchy problem for ODE and their reflection on parallel structure. In represented article the analysis of parallel algorithms for the decision of ordinary differential equations on computing structures with SIMD by architecture is considered. Reflection of extra-exact multistep block algorithms on parallel calculable structures SIMD types with lattice and gipercub topology is showed. Parallelizm estimations are considered: acceleration and effectiveness for offered decision reflection methods.

Введение

С развитием техники перед учеными ставятся все более сложные цели, достижение которых требует оригинального мышления и повышенной внимательности. Постоянные исследования в области разработки и создания высокопроизводительных вычислительных средств позволяют решать фундаментальные и прикладные задачи. Производительности современных ЭВМ недостаточно для обеспечения нужного решения многих задач. Один из наиболее эффективных способов повышения производительности заключается в распараллеливании вычислений в многопроцессорных и параллельных структурах, создание новых методов и алгоритмов, ориентированных на эффективное использование в многопроцессорных системах, а также модернизация существующих методов. [6] Многие численные методы не подходят для распараллеливания и их приходится перестраивать либо совсем от них отказываться. Некоторые же параллельные методы обладают численной неустойчивостью или имеют очень сложную структуру, которая приводит к потере эффективности.
К методам, которые не обладают указанными недостатками, можно отнести блочные [1]. Идея этих методов состоит в том, что, имея k точек блока, новые k значений можно вычислить одновременно. Данная особенность методов согласуется с архитектурой параллельных ВС и позволяет вычислять коэффициенты разностных формул не в процессе интегрирования, а на этапе разработки метода, что значительно увеличивает эффективность счета. Данная работа опирается на исследования, результаты которых ранее опубликованы авторами в [2,3,4,5] и посвящена анализу параллельных методов решения задачи Коши для ОДУ и СОДУ и их отображению на параллельные структуры.

1. Алгоритмы параллельного решения задачи Коши для ОДУ

Рассмотрим решение задачи Коши

(1)

При численном решении задачи Коши для сравнительной характеристики методов можно рассматривать различные показатели. В случае произвольной правой части уравнения о трудоемкости метода естественно судить по числу обращений для вычисления значений правой части уравнения на каждый узел сетки. В качестве одной из оценок степени параллелизма алгоритма используется коэффициент ускорения [4]: W(k)=T₁/T_k, где T₁ – время выполнения алгоритма на однопроцессорной ЭВМ и T_k – время выполнения алгоритма на параллельной ВС. Можно получить оценки времени алгоритма, определяемого формулами (10) и (11) на одном процессоре. Если t_f – время вычисления значения функции f(t,x), t_ad, t_mul – время выполнения операции сложения и умножения соответственно, то время вычисления по формулам (10) с заданной локальной точностью составит:
T_{1, многошаг.}=k(2k+1) t_f +4k³ t_ad+ 2k²(2k+1) t_mul.
А время вычисления с заданной локальной точностью во всех k узлах блока по формулам (11) составит:
T_{1, одношаг.}=(k²+1) t_f +k[k(k-1)+2] t_ad+ (k³+2k+1) t_mul
Для определения T_k возьмем ВС SIMD структуры с топологией кольцо. Каждый процессорный элемент может выполнить любую арифметическую операцию за один такт; временные затраты, связанные с обращением к запоминающему устройству, отсутствуют. Закрепим за каждым узлом блока процессор. На k процессорах можно одновременно вычислять значения F^(s)_n,i, а затем также одновременно получить по формулам значения u^(s)_n,i для каждого фиксированного s. Если t_ta – время передачи числа соседнему процессору, то время параллельного вычисления приближенных значений решения с той же точностью для всех узлов блока составит:
T_{k, многошаг.}=2(k+1) t_f +2[k(2k+1)+1] t_ad+3[k(2k+1)+1] t_mul+k(2k+1) t_ta.
T_{k, одношаг.} =(k+1) t_f +(k²-k+3) t_ad+(k²+3) t_mul+k(k-1) t_ta.
Если учитывать только время вычислений правой части уравнений, то ускорение k точечного многошагового параллельного алгоритма можно считать приближенно равным:
W(k)_{многошаг.}=k(2k+1)/(2k+1).
Ускорение параллельного одношагового k точечного алгоритма можно будет теперь считать приближенно равным:
W(k)_{одношаг.}=(k²+1)/(k+1).
В качестве еще одной оценки степени параллелизма алгоритма используется коэффициент эффективности, который определяется отношением ускорения к числу используемых процессорных элементов, т. е. E(k)= W(k)/k. Для рассматриваемого случая: Е(k)=1.
Как можно видеть из представленных выражений, многошаговые методы эффективнее, чем одношаговые. Однако, в сравнении с последовательными методами, разностные методы значительно выигрывают.

2. Реализация многошагового блочного метода на решетке процессоров

В общем случае алгоритм решения задачи Коши для СОДУ

(12)

многошаговым многоточечным блочным методом [2]

(13)

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

(14)

который позволяет проводить вычисления параллельно для каждого узла блока.
Пусть начальные приближения для нового блока находятся с помощью метода Адамса-Башфорта. К началу выполнения расчетов матрицы коэффициентов уже сформированы.[2]. В качестве модели, на которую ориентируется решение, используется вычислительная система SIMD структуры c вычислительным полем 2D-тор, размерностью kxm процессорных элементов (k – размерность блока, m – размерность системы обыкновенных дифференциальных уравнений). Каждый процессорный элемент может выполнить любую арифметическую операцию за один такт; временные затраты, связанные с обращением к запоминающему устройству, отсутствуют.
Время, определяющее начальную итерацию, будет выражаться как [2]
T_{нач.итер.}=k*(2t_умн+(log₂k+1)t_сл+(mk-1)t_сдв+t_p)
Общее время, необходимое на выполнение начального приближения и на подготовку очередной итерации:
T_{нач.итер.+подг.}=k*(4t_умн+(2log₂k+1)t_сл+(mk+k-2)t_сдв+t_p)
Для достижения предельной точности методов необходимо выполнить k итераций. Поскольку во второй итерационной формуле (14) изменяется только одно из слагаемых, будем учитывать время, необходимое для пересчета только этого значения.
Время, которое потребуется для выполнения итераций составит:
T_итер.=k²*(2t_умн+(log₂k+1)t_сл+(mk+k-2)t_сдв+t_p)
Общее время, за которое может быть получено решение системы уравнений (14) в одном блоке будет определяться
T_блока=T_{нач.итер.+подг.}+Т_итер..
Для оценок качества рассмотренного алгоритма используются наиболее распространенные критерии [1]: коэффициент ускорения и коэффициент эффективности. При расчете значений вектора x_n на однопроцессорной ЭВМ потребуется время, равное:
T_посл.=mk(2(k+2)t_умн+2(k+1)t_сл+t_p)+mk²((k+2)t_умн+2(k+1)t_сл+t_p)
Если учитывать только время вычислений правой части уравнений, т.к. времена выполнения арифметических операций и обмена значительно меньше времени вычисления правой части, то ускорение k точечного многошагового параллельного алгоритма можно считать приближенно равным:

Эффективность k-точечных многошаговых блочных методов при реализации на SIMD структуре

Рисунок 1 – Зависимость эффективности от размерности блока (m=100)

Рисунок 2 – Зависимость ускорения от размерности блока (m=100)

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

3. Реализация многошагового многоточечного блочного метода в SIMD-системах с топологией гиперкуб

В общем случае алгоритм решения задачи Коши для СОДУ, как уже рассматривалось, многошаговым многоточечным блочным методом [2] разбивается на следующие подзадачи:

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

Вычисление начальных приближений в точках нового блока выполняется для каждого блока только один раз и элементарно распараллеливается, т.к. эти вычисления для каждой точки производятся независимо, а время вычисления одинаково. Далее производится обмен вновь полученными значениями, т.е. каждый процессор должен получить информацию от всех оставшихся, в которых были вычислены значения элементов вектора начального приближения для блока и, в то же время, переслать всем процессорным элементам "свое" значение элемента вектора.[5]
После рассылки "все-всем" вычисляются правые части системы уравнений в каждой точке блока. Относительное время работы этой части алгоритма сильно варьируется в зависимости от однородности правых частей системы обыкновенных дифференциальных уравнений и их сложности.
Подготовка и проведение итерационного процесса в блоке является самой трудоемкой задачей. Каждый следующий цикл требует некоторого переупорядочения данных для подготовки систолического умножения матрицы на вектор, что несет с собой дополнительные временные затраты. Время работы этой части алгоритма составляет 85 – 90% от общего. Можно определить необходимые коммуникационные примитивы:

1. умножение матрицы на вектор. Для этого достаточно "размножить" значения каждого элемента вектора k раз (в соответствии с размерностью блока);
2. обмен по типу "все-всем", операции вычисления суммы путем комбинирования операций сдвига и сдваивания произведений правых частей и вспомогательных коэффициентов, распределенных по процессорам.

Время передачи данных между процессорами для используемой модели можно выразить в виде: [5]

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

В качестве SIMD-системы была использована разработка фирмы FPS серии T в области архитектур с массовым параллелизмом. [5] Для первого способа под каждое уравнение системы будет выделяться k² процессорных элементов. При втором способе размещения данных за каждой точкой блока закрепляется только один процессор.
Тогда для первого алгоритма величина или m/p/k² – количество "тактов", за которые можно рассчитать всю систему для блока из k точек. Поскольку для нормального функционирования в алгоритме не предусмотрено обращение к внешней машине, можно принять, что время выполнения одной операции соизмеримо с временами t_сл=t_умн=t_сдв. Тогда время, необходимое для расчета значений в одном блоке можно будет оценить как

Для второго способа расположения данных, а именно, когда для расчета каждой точки блока выделяется только один процессор, а на каждое уравнение системы k процессоров, общее время будет определяться как:

Для таких способов размещения данных характеристики параллелизма можно представить с помощью графиков. [5]
Значения предельных показателей ускорения (W) и эффективности (E) приведены в таблице 1.[5] Таблица 1 – Основные показатели параллелизма реализованных методов для SIMD систем

№	Топологическое соединение	Нелинейные системы W	Нелинейные системы E	Линейные системы W	Линейные системы E
1.	1D- тор (p>=k)	~k	~1	~k	~1
2.	1D- тор (p>=m)	~k	~k/m (m>=k)	~m	~1
3.	2D- тор (p>=kxk)	~k	~1/k	~kxk/log2k	~1/log2k
4.	2D- тор (p>=mxk)	~k	~1/m	~mxk/log2m	~1/log2m
5.	3D-тор (p>=kxkxm)	~k	~1/(mxk)	~kxkxm/log2(k+m)	~1/log2(k+m)
6.	Гиперкуб (p>=kxk)	~k	~1/k	~kxk/log2(k-1)	~1/log2(k-1)

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

Заключение

В представляемой статье проведен анализ существующих параллельных блочных алгоритмов решения задачи Коши для обыкновенных дифференциальных уравнений. Данные методы не требуют вычисления значений в промежуточных точках, что значительно повышает эффективность счета. Приведены оценки параллелизма предлагаемых методов: ускорение и эффективность для различных типов решаемых систем обыкновенных дифференциальных уравнений.
Также проведен анализ реализации многошагового многоточечного блочного метода решения задачи Коши для СОДУ в SIMD-системах с топологией решетка и гиперкуб. Приведены основные показатели параллелизма рассматриваемых методов для SIMD систем.
Разностные методы являются гораздо более эффективными в сравнении с известными последовательными методами, отображенными на параллельные структуры. Коэффициент эффективности рассматриваемых методов приблизительно равен 1.
Показано, что нужно при решении задачи разностными методами необходимо выбирать оптимальную размерность блока и структуру параллельной ВС, иначе эффективность метода падает и увеличивается общее время вычислений.

Литература

1. Системы параллельной обработки: Пер. с англ./ Под. ред. Ивенса Д.– М.: Мир,1985–416с.
2. Дмитриева О.А. Параллельные блочные многошаговые алгоритмы численного решения систем обыкновенных дифференциальных уравнений большой размерности. //Науковi працi Донецького державного технiчного університету. Серiя: Проблеми моделювання та автоматизації проектування динамічних систем, випуск 15: – Донецк:, 2000. С. 53–58.
3. Фельдман Л. П. Сходимость и оценка погрешности параллельных одношаговых блочных методов моделирования динамических систем с сосредоточенными параметрами //Науковi працi Донецького державного технiчного унiверситету. Серiя: Проблеми моделювання та автоматизації проектування динамічних систем, випуск 15: – Донецк:, 2000. С. 12–16.
4. Фельдман Л.П., Дмитриева О.А. Разработка и обоснование параллельных блочных методов решения обыкновенных дифференциальных уравнений на SIMD-структурах. //Научн. тр. Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. – Севастополь: "Вебер", 2001. – С. 70–79.
5. Дмитриева О.А. Модели отображения многошаговых алгоритмов на параллельные вычислительные системы с топологией гиперкуб//Науковi працi Донецького державного технiчного унiверситету. Серiя: Проблеми моделювання та автоматизації проектування динамічних систем, випуск 15: – Донецк:, 2000. С. 23–26.
6. www.parallel.ru Информационно-аналитический центр по параллельным вычислениям.