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

ИНСТИТУТ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ РАН

ОД

На правах рукописи

ЗЫБИН Сергей Владимирович

Разработка и исследование параллельных итерационно - сверточных алгоритмов интегрирования обыкновенных дифференциальных уравнений

05.13.18. Теоретические основы математического моделирования, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук -

Москва - 1991

Работа выполнена в отделе вычислительной техники и информатики Ин-• титута высоких температур РАН и на кафедре математического моделирования Московского энергетического института (технического универсанта).

Научный руководитель: доктор физ.-мат. йаук, профессор

Ю.П. Боглаев

Официальные оппоненты: доктор физ.-мат. наук, профессор

Б.Н. Четвсрушкин кандидат фнз.-мат. наук, ст.н.с. Сухов Е.Г.

Ведущая организация - Московский физико-технический институт.

Защита диссертация состоится '*_" __ 1994 г. в

_____часов на заседании Специализированного совета К 003.91.01 при

Институте математического моделирования РАН по адресу: 125047, Моск-

ял, Мпусхкая илощадь, 4.

' - диссертацией можно ознакомиться в библиотеке ИММ РАН. Автореферат разослан "____"___1994 г.

Ученый секретарь

Специализированного совета К 003.91.01 к.ф.-м.н.

Свирщевсквй С.Р.

С)Объединенный институт высоких температур РАН,1994 г.

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

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

Можно выделить следующие основные типы параллелизма при решении задачи Коши для ОДУ (C.Gear, Calcolo, v.25, 1988): параллелизм по пространству, и параллелизм по времени. Реализация первого не вызывает больших затруднений, однако он эффективен лишь при решении слабосвязанных систем ОДУ большой размерности.

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

Для решения m добных задач на многопроцессорных ВС следует использовать алгоритмы, обладающие крупномасштабным параллелизмом по времени. Однако обычные последовательные методы, такие как многошаговы' методы или методы Рунге - Кутта, не могут служить адекватной основой для ра:,^аботт'п новых параллельных алгоритмов. Дело в том, чти при распараллеливании пошаговых алгоритмов достиг» ется лишь мало масштабный параллелизм, прп котором число г .пользуемых п^оцтч рои не превышает порядка метода.

Поэтому для реализации крупномасштабного параллелизма П" ирсменп были предприняты поиски новых подходов при разработке пара, ¡лельныл

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

Однако разработанные на основе этого подхода параллельные итерационные алгоритмы, называемые также "waveform relaxation methods" (A.Newton et al., IEEE TVans.CAD, v.3, 1984; C.Gear, J.Comp.Appl.Math., v.38, 1991) используют в основном итерации типа Пикара и только лишь квадратурный параллелизм. Кроме того, во многих из этих работ пока недостаточно внимания уделяется исследованию проблем, которые встают при численной реализации подобных алгоритмов и при их отображении на. архитектуру ВС, а также изучению их вычислительных свойств в приложениях.

Поэтому представляется весьма актуальной задачи исследования методов, использующих другие итерационные процессы, в частности, итерации типа Ньютона (позволяющие получить дополнительный параллелизм за счет свертки), и задача разработки на их основе параллельных алгоритмов, реализующих крупномасштабный параллелизм при отображении на архитектуру.многопроцессорных ЗС. Кроме того, представляет интерес их приложение к задаче исследования движении сверхпроводящей частицы магнитной жидкости во внешнем магнитном поле.

Целью работы является исследование и разработка параллельных алгоритмов и программ численного решения задачи К опт для ОДУ на основе итерационно - сверточного подхода, а также проведение вычислительных экспериментов п численного моделирования с использованием этих алгоритмов.

Это потребовало решения следующих задач:

- разработка численных итерационно - сверточных алгоритмов, позволя-

. ющих использовать дискретную свертку в качестве базовой операции,

и исследование их формальных свойств (сходимости, устойчивости, аппроксимации),

- выявление в разрабатываемых алгоритмах парал тельных структур и

уровней параллелизма и тучение вопросов их согласования с архитектурой ВС с эффективным вычислением дискретной свертки,

- реализация на основе разработанных параллельных алгоритмов комплекса программ решения задачи Коши для ОДУ и исследование их вычислительных свойств на наборе тестовых ОДУ,

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

Научная новизна.

1. Разработаны параллельные итерационно - сверточные алгоритмы интегрирования задачи Коши для ОДУ на основе квадратурных формул Грегори.

2. Доказаны свойства сходимости используемых итерационных процессоь и получены оценки скорости сходимости, доказаны свойства аппроксимации и устойчивости разработанных алгоритмов.

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

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

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

Использование предложенных в работе алгоритмов позволяем ризр.шл-тывать параллельные программы для ВС с векторными/конвейерными шп>

о

сигнальными процессорами1, а также создавать специальные процессоры-интеграторы ОДУ (по типу систолических или сигнальных) для применения их в устройствах управления в реальном времени.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на советско-британском семинаре по транспьютерным системам (г. Москва, 1990), 1-й Всесоюзной конференции "Транспьютерные, системы и их применение" (г. Звенигород, 1991), 9-й Международной школе "Вычислительные методы в физике" (г. Скальский двор, 1991), 5-й Международной школе-семинаре "Численные методы и автоматизация в ядерной физике и астрофизике" (г. Сотш, 1992), российско-французском семинаре по новым информационным технологиям и параллельным вычислениям (г. Москва, 1993), 6-й Международной конференция NATUG-6 "Транспьютерные системы и их применения" (г. Ванкувер, 1993).

Публикации.

По результатам работы имеется 7 опубликованных работ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения, 33 рисунков и таблиц, списка литературы из 196 наименований и двух приложений, изложенных на 155 страницах машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

Во введении дается обоснование актуальности темы и излагается краткое содержание диссертации. Также дан обзор основных подходов к построению параллельных методов интегрирования ОДУ и обсуждаются вопросы разработки алгоритмов с крупномасштабным параллелизмом.

В первой главе описывается итерационно - сверточный temod (MCiA) решения задачи Копш для системы ОДУ

§=/(<,</), 'te[h,T), y(t0)=y0,y = (yu...,ym)T, / = (/,,...,/m)T, (1)

основанный на приближенном итерационном процессе Ньютона, и исследуются вопросы сходимости используемых итерационных процессов.

В §1.1 вводятся приближенные основной и модифицированный итерационные процессы следующего вида

= f(t,yk) + - У% к = 0,1,..., t € (2)

где ;/(0) = .vo, yk{tj - 0) = yk(tj + 0), j = 1,..., N - 1, t0 =-- 0, tK = T.

Основная идея за£ДК>чается в приближенной аппроксимации якобиана А1(<) = л*) постоянными матрицами А* на каждом подынтервале } = 0,...; N—1,11 последующим вычислением интеграла свертки на каждой к-ц итерации, что позволяет использовать параллелизм дискретной свертки за счет применения для ее вычисления параллельных алгоритмов или специальных процессоров.

Приближенный ыч'оьной итерационный процесс использует пересчет кусочно - постоянной аппроксимации якобиана на каждой итерации, а в приближенном модифицированном аппроксимация вычисляется только на начальной итерации (Л* = Л° для всех к = 0,1,...).

В §1.2 исследуется сходимость итерационных процессов в банаховом пространстве непрерывных кусочно - дифференцируемых на интервале I 6 [0,Т] функций»(0 = (УМ,...,УГпЦ))т 6 С1[0,Т].

Доказывается сходимость и получены оценки скорости сходимости рассматриваемых итерационных процессов при устанавливаемых достаток ных условиях относительно правой части и кусочно-постоянной аплрок симации якобиана системы (1), а также начального приближения В

частности, относительно аппроксимаций А0, А якобианов Л°(<), .4(0 предполагается, что выполнено условие

I\А-А° ||< м II У -У° ||,V» 6 с'[о,т], г 6 [0,Г].

Оба приближенных итерационных процесса являются процессами первого порядка сходимости, однако они имеют различные С^-множнтели сходимости, а именно: приближенный основной процесс "ф-быстрее" приближенного модифицированного. Поэтому, хотя пересчет якобиана, влечет за собой дополнительные вычисления (которые, впрочем, можно также выполнять параллельно), это ускоряет сходимость итерации.

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

II Л(0 - Л II < ¿0 + ¿1 II у - у0 II, V?/ € С"|0,Т}, « 6 (О.Т|. Это позволило доказать сходимость приближенных итерационных ироцп сов при несколько более лучших условиях и оценках, но порядок счодимоп .1 остается неизменным.

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

ь- - /II < - .'/-'II < - .«/'II,

- П- 1 7|

где y*(t) - точное решение, а последовательность {г*} удовлетворяет полученному реккурентному соотношению второго порядка следующего типа

ГШ -4 = --T^hñ-^ ~ 4-1'

Эги оценки могут найти применение при разработке алгоритмов и программ на основе данных итерационных процессов.

В §1.3 рассмотрены способы ускорения сходимости приближенного основного итерационного процесса. Для повышения порядка сходимости требуется на каждой итерации увеличивать точность аппроксимации якобиана Л*(<). В частности, предлагается на к-й итерации процесса (2) выполнять Vk число внутренних итераций с одной и той же кусочно-постоянной аппроксимацией Ак для Ak(t)

jj.f+i

^ = " = 0,1,...,^, к = 0,1,... (3)

/+1(0) = yo, yvM(tj - 0) = f+1(tj + 0), j = 1,.... N- 1,

где y"{t) |„=o= yk(t) - начальное приближение для внутреннего итерационного процесса (3) на к-й внешней итерации процесса (2).

Доказывается сходимость приближенного основного итерационного процесса (2) с внутренними итерациями (3), которая является:

• сверхлинейной, если число внутренних итераций увеличивается на единицу на каждой к й внешней итерации, f¿+i = i/* + 1,

• порядка 1 +р, р < 1, если выполняется условие = (1 +

При этом оказывается, что внутренние итерации можно дополнительно ра -параллелить, используя принцип циклической редукции и получая вместо щ последовательных итераций O(log i/*) параллельных итераций на i>i¡ процессорах.

Общей проблемой для всех параллельных итерационных алгоритмов является получение начального приближения ¡/°(<). В простейшем случае полагается ,j°{t) = уч — consí, однако, как показывается в главе 4, имеет смысл использовать для нахождения y°(í) пошаговые алгоритмы с малой точностью (е ~ КГ1 Ч- Ю-2), применяя затем для повышения точности параллельные итерационно - сверточные алгоритмы.

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

Основным вычислительным процессом на каждом шаге итераций (2) и на каждом подынтервале (блоке) + является вычисление интеграла свертки в

yk+\t) = y(to)ехр((< - to)Âl] + /'g(t- з)ф(з,г/)Нз, к = 0,1, ...,t € [<о, to + H],

■"о

(4)

g(t - s) = ехр[(< s)Ak\, ф(а, ук) = f(s, ук) - Akyk(s).

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

Исходя из этого, были выбраны принадлежащие к классу ('/?, <7)-еводимых квадратурные формулы Грегори, которые обладают хорошими свойствами аппроксимации и устойчивости, а также позволяют записать в (4) дискретную свертку в явном виде (чему, в частности, не удовлетворяют (р, <т)-сводимые формулы дифференцирования назад)

I

Ci = - j)/i)^*(*0 + j/i), i = ?,..., тг, (5)

J=0

где u>i - веса формулы Грегори порядка р — q +1. (о>,- = \ ,i > q). Это делает указанные формулы особенно удобными для распараллеливания.

Кроме того, формулы Грегори дозволяют достаточно легко менять порядок аппроксимации посредством простого изменения весов и добаиле-ния стартовь/л; значений г = 0,q. Подчеркнем, что размеры Mai, ппов {<7,} и при этом не изменяются, поэтому не возник teT потребности в дополнительных пересылках между процессорами.

Основным преимуществом использования свертки (5) является возможность дополнительного распараллеливания итерационно - сверточных ¿^го-ритмов по сравнению с другими параллельными итерационными методами, а которых главное внимание уделяется одновременному пычислегопо значений функций g(t) и <^>(£) в узлах квадратурных формул. Как доказывают результаты тестов, после вычисления массивов и {<;>,} ил сборку решения" посредств< .1 их свертки уходит от 20% до 90% от общего времени счета; поэтому можно получить заметное ускорение за счет использования параллельных алгоритмов или специальных устройств для ее в&чис.логия В §2.2 доказывается устойчивость и сходимость итерационно - овергич ных алгоритмов, использующих (р,<г)-еводцмые квадратурные формулм.

В частности, свойства аппроксимации и нуль-устойчивости рассматриваемых алгоритмов определяются свойствами численной аппроксимации E[hA\ матричной экспоненты ехр(ЛЛ] п характеристическими полиномами р((), а(() методов Адамса-Моултона, к которым формулы Грегори являются (р, (г)-сводимыми. При этом, как оказалось, формулы Грегори с центральными разностями (использующие узлы вне отрезки интегрирования), которые обладают меньшими константами погрешности по сравнению с формулами с односторонними разностями, являются неустойчивыми при |/(Д| —» 0 на линейной модельной задаче у' — А у, А 6 С.

Что касается устойчивости разрабатываемых алгоритмов на классе задач с асимптотически устойчивыми решениями, то здесь, в отличие от пошаговых методов, существенное влияние оказывает итерационная погрешность. Это объясняется тем, что в процессе итераций аппроксимация якобиана Ак (<) = j£j(t,yk) осуществляется не на точном, а на приближенном решении yk(t), и, кроме того, не на малом шаге Л < Я, а на всем подынтервале [ío, *о + Я]. Для исследования этого вопроса в качестве модельного было выбрано следующее, нелинейное логистическое уравнение

§ = «2/(1 - У), 2/(0) = 2/о, « € С, (6)

обладающее при Re(á) ф 0 двумя асимптотиками у ■■= lim^r» y(t) = {0,1}.

Доказывается, что итерационно - сверточные алгоритмы на основе (р, (т)-сводимых квадратурных формул являются регулярными по Изерлесу (A.Iserles, IMA J.Numer.Anal., v.10, 1990) в предположении, что E[hA\ удовлетворяет определяемому полиномами р(£) и <х(£) линейному многошаговому методу (JIMM). Для определения влияния итерационной погрешности fb =|| у* — ук И на устойчивость рассматриваемых алгоритмов вводятся понятие области асимптотической устойчивости на задаче (С) в предположении, что аппроксимация якобиана вычисляется на приближенной асимптотике у = у+'е/2, от погрешности которой явно зависит размер области устойчивости (на каждой к-й итерации он будет тем больше, чем меньше погрешность е*).

Таким образом, выбор начального приближения определяет не только сходимость итераций, но и допустимую величину шага сеткц h используемой квадратурной формулы. В частности, чем дальше начальное приближение y°(t) от асимптотики, тем меньше размер области устойчивости и, соответственно, допустимый шаг h при данном а. Это нежелательное явление, так как именно на начальных итерациях, когда еще велика итерационная погрешность, целесообразно было бы использовать грубую сетку.

В §2.3 рассматривается использование параметрического преобразования переменных при интегрировании ОДУ, заключающегося во вращении координат {у, t) на некоторый угол <р, являющийся параметром преобразования.

Показано, что можно минимизировать норму дифференциального оператора, входящего в оценку главного члена асимптотического разложения локальной погрешности численного метода пли в оценку скорости сходимости итерационных процессов. Это позволяет увеличить длин)' шага интегрирования, понизить порядок метода или ускорить сходимость итераций, но требует предварительной информации о решении »/*(<) пли многократного интегрирования с разными ф. Однако при использовании многопроцессорных ВС можно получить ускорение за счет параллельной оптимизации по параметру (одновременно решая на на разных процессорах уравнения с различными значениями ф).

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

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

Блочный уровень: интервал интегрирования разбивается на N подынтервалов [tj,tj + Hj],j = 0, ...,iV — 1. На каждом из подынтервалов вводится сетка с постоянным шагом hj —, Hj/nj, и вычисляется начальное приближение y°(t),t 6 [fj,(; + Hj}. Затем параллельно на всех подынтервалах начинается итерационный процесс (2), причем на каждой нтерашга осуществляется "сшивка" решений на границах подынтервалов yk(tj — 0) =

Квадратурный уровень: на каждом подынтервале сетка tj < tj + hj < ... < tj + (iij — 1 )hj < tj + Hj разбивается на совокупности узлов {<"•},? = 1,.... v, в которых затем параллельно вычисляются значения подынтегралъ- ч ной функции ехр;^ - tj < s < t < tj + Hj, т.е. элементы

массивов {a,} и {6,}, где a,- = /ijW, exp[i7»/l*], 6,- = u>iç(tj -f ih, yl(tj -f ih)), w,- веса квадратурных формул Грегори. Заметим, что вычисление элементов массива {а,} можно дополнительно распараллелить за счет использования

циклической редукции.

Сиерточный уроотъ: дискретная свертка с; = Ц=0 а»-А'>1 = 9> •••>п массивов {а,} и {();}, используемая на каждом подынтервале для "сборки" решены* {1/,}, вычисляется параллельно ирп помощи специальных процессоров или пар ллелышх алгоритмов. Получаемое при этом ускорение зависит от способа вычисления свертки. Следует также отметить, что свертка позволяет использовать "внутренний параллелизм" ОДУ, связанный с передачей возмущений вдоль траекторий ОДУ, приближенно описываемой функцией гД* - й) = ехр[(< - В частности, если для собственных чисел матрицы Л имеем Яе(А,) < 0,1 = 1,..., 7п, л интервал интегрирования достаточно большой, то исходная свертка распадается на ряд параллельно вычисляемых коротких циклических сверток. Заметим, что на большой внутренний параллелизм жестких уравнений впервые обратил внимание С.веаг (Са1со1о,у.25,1988).

В результате определяется множество параметризованных итерационно - сверточных алгоритмов, задаваемых вектором параметров р — р] „),

где р1 - количество подынтервалов на первом (блочном) уровне, - количество совокупностей узлов сетки .7-го подынтервала на втором (квадратурном) уровне, и „ - количество параллельных ветвей алгоритма вычисления свертки массивов {а,},{Ь,}, разбитых на V совокупностей.

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

§3.2 посвящ.ж изучению архитектуры /ьичного гиперкуба, являющегося обобщением двоичного п-куба. Его можно представить в виде декартовой п- мерной матрицы с р узлами (процессорами) в каждом координатном направлении и замыкающими крайние вершины ребрами, с общим числом узлов N — рп (иногда так^ю архитектуру называют гипертором).

Исследованле р-ичного гиперкуба было вызвано возможностью вычисления на нем дискретной свертки посредством параллельного алгоритма Кули-Тыоки быстрого преобразования Фурье (БПФ). Дело в том, что на двоичном п-кубе с числом процессоров N — 2" эффективная реализация параллельного БПФ возможна только для последовательностей с числом элементов М = 2т, т > V. Кроме того, затруднено эффективное отображение в двоичный гиперкуб регулярных геометрических структур (например, разностных г-еток) с числом узлов не равным степени двойки.

Доказываются некоторые топологические свойства свойства графа р-ичного гиперкуба HPi„. В частности, определяется число вершин, отстоящих на заданное расстояние r(wi,w,-) = t от выбранной вершины i/i, а также число параллельных не пересекающихся между собой йаршрутов минимальной длины è = r(fj,^) между любыми двумя вершинами t'i, v-^. Заметим, что эти числа определяются по-разному для четных и нечетных р. Так, например, для любой v € Нр п при четном р существует единственная вершина « € Ярп, такая, что Nt(v, и) = 2h(v, и), где h(v, и) - расстояние Хэмминга. Кроме того, определяется число параллельных путей различной длины, в том числе на единицу и на двойку больше минимальной длины.

Далее изучаются коммуникационные и отображающие свойства архитектуры р-пчного гиперкуба. Определяются следующие его характерис тики: диаметр сети D, среднее расстояние г, средняя загруженность связей р, степень регулярной сети d, отношение стоимость/эффективность С/Р = d ■ D, несвязность (узость) сети, время рассылки (broiulcasting) по с ети. По критерию стоимость/эффективность, а такж« и по другим характеристикам, р-пчный гиперкуб занимает промежуточное положение между "дешевым" по числу связей на узел, но малоэффективным двоичным п-кубом, и очень эффективным, но дорогостоящим обобщенным гиперкубом.

Также рассматривается отображение линейки, кольца и двумерного тора в />-ичный гиперкуб и построение в нем гамильтонова цикла для чего предлагается использовать, по аналогии с двоичным п-кубом, ;»-ичный код Грея. Однако известный алгоритм генерирования симметричного кода Грея в случае р-ичных чисел не сохраняет свойства цикличности кода при нечетном р. Поэтому разрабатывается алгоритм, который строит циклический р-ичный код Грея (но не сохраняет его симметричности). Далее рассматривается отображение в р-пчный гиперкуб графа параллельного алгоритма Кули-Тыокп для БПФ последовательности с числом элементов M = q\1î- - ■ qr-где <7; < p,i — 1,..., г, что представляет интерес при реализации на нем итерацпонно-сверточных алгоритмов.

Четвертая глава посвящена исследованию вычислительных свойств разработанных алгоритмов и программ на наборе различных тестовых ОДУ, а также исследованию движения сверхпроводящей частицы магнитной жидкости с п>: использованием.

В §4.1 приводятся результаты тестирования итерационно - сверточных алгоритмов на н.Лоре ОДУ с точными решениями. Реализация разработанных алгоритмов была выполнена в виде комплекса программ интегрирования задачи Коши для ОДУ на языке OCCAM для транспьютерной ВС IMS В012. Пакет имеет структуру, соответствующую выделенным выше

jTbNV

сбертка uaccubob подымтеграл,

fyHKUUQ

Fnc. 1: Блочный уровень комплекса программ для транспьютерной ВС.

уровням параллелизма.

В частности, на первом уровне используется блочный параллелизм (Рис.1), которому соответствует архитектура типа кольца. На каждом j-м блоке Node, выполняются итерации на j-м временном подынтервале ['j> O+i)> 3 = ••■, М — 1, причем для сшивки граничных значений используются асинхронные коммуникации через программные буферы, приводящие в результате к асинхронным и герациям на различных подынтервалах. Это позволяет несколько уменьшить разбалаисировку транспьютеров, вызванную том, что при использовании в качестве начального приближена* уи(() = у0 = const число итераций на последних подынтервалах больше, чем на первых.

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

Для тестирования разработанных алгоритмов и программ использовалась транспьютерная ВС, имеющая архитектуру типа кольца с М транспьютерами (М = 1,... ,4). Целью проводимого тестирования было получение оценок возможного ускорения и эффективности на квадратурном уровне итерационно - сверточных алгоритмов 2-го и 4-го порядка по отношению к стандартным пос ледовательным методам RK-2, RK-4 или RKF45. Другая цель - определить относительную "стоимость" дискретной оперши л

процентах от общего времени счета и характеризующую ускорение, которое можно получить на сверточном уровне (в проведенных тестах процент свертки изменялся от 20% до 90% в зависимости от погрешности решения).

Результаты тестирования показывают, что получаемое ускорение экспоненциально растет с увеличением задаваемой точности решения. Это наводит на мысль, что начальное приближение y°(t) может быть получено посредством применения при малой точности (е ~ Ю-1 4- Ю-2) последовательного (или параллельного) пошагового метода.

Следует заметить, что выбор начального приближения y°(t) заметно влияет па ускорение и эффективность. Плохое начальное приближение заставляет ограничивать длину блока Я (чтобы обеспечить сходимость итераций), я, соответственно, уменьшает возможное ускорение при распа-. раллеливании вычислений на нем. Другой выявленной проблемой является сужение области асимптотической устойчивости итерационно - сверточных алгоритмов при увеличении итерационной погрешности. В частности, для уравнений, сочетающих сильную нелинейность п жесткость, ограничения на размер блока Н и шаг сетки h делают применение этих алгоритмов неце лесообразным.

Сравнение с наиболее близкими по характер}- параллельными итерационными алгоритмами типа "shifted Picard splitting" (R.Skeel, J. Conip. Appl. Math., v.38, 1991), показывает, что скорость сходимости итераций (определяющая возможное ускорение при распараллеливании) у итерационно - сверточных алгоритмов пыше, чем у обычных итераций Ппкара, и примерно совпадает со сходимостью итераций типа "shifted Picard".

В §4.2 рассматривается интегрирование уравнений Лоренца посредством итерационно - свер -очного метода с использованием аналитических итераций.

Исследование поведения фазовых траекторий подобного рода систем проводится, в основном, посредством построения бтображенпя Пуанкаре, что требует численного интегрирования на больших временных интервалах. Система Лоренца и другие подобные гидродинамические системы отличаются тем, что имеют правые части, полиномиальные по у, поэтому интеграл свертки берется в элементарных функциях. В результате оказалось возможным применить не только численные, но и аналитические итерации (что, в частности, позволяет строить параллельные аналитические алгоритмы). Для выполнения аналитического интегрирования использовалась система DERIVE (модифицированная версия REDUCE).

В §4.3 представлены результаты исследования движения сверхпроводящей частицы магнитной жидкости в переменном магнитном поле. Такая

жидкость представляет собой суспензию сверхпроводящих частиц (ССЧ) диаметром ^ 1/»ш, диспергированных в растворителе при температуре

Во внешнем магнитном поле сверхпроводящие частицы ССЧ приобретают магнитный момент благодаря эффекту Мейсснера, величина которого зависит от приложенного поля Нс. Если частицы дисперсной фазы приготовлены из монокристаллических образцов сверхпроводника, то их особенностью будет большая анизотропия параметров сверхпроводящего состояния. В результате магнитный момент каждой частицы не является антипараллельным приложенному внешнему ьолю Нс > Нс\, (как в изотропном случае), и его абсолютное значение зависит от угла 0 между Яс и одной из осей кристалла. Это приводит к тому, что в переменном магнитном поле Нс — /focos(w7-), ЯС1 < Яо < Я^, возникают колебания частиц вблизи равновесного значения 9о- При определенных условиях состояние равновесия может быть неустойчивым, и возможно возникновение возникновение хаоса, то есть нерегулярных колебаний сверхпроводящих частиц в переменном магнитном поле.

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

где 72 = тз/ш| - коэффициент анизотропии (20 < 72 < 90), R - радиус частицы, pt - ее плотность, г/ - вязкость растворителя. Используя метод Ляпунова, обобщенный нг. случай знакопеременного коэффициента (го cos f) при f(0), пос~;>оена область устойчивости на плоскости параметров (а, го) уравнения (7), существование которой подтверждается численным моделированием движения частицы с использованием итерационно - сверточного! алгоритма с формулами Грегори 4-го порядка и контрольного метода 4-го порядка RKF45.

Т<ТС.

sin 26»

ршЮи\ Г° 16л- р,RW

15т/ _ 5 Я'Я0-у-'/а(72 ~ 1)

В приложения вынесепы тексты комплекса программ итерационно -сверточных алгоритмов интегрирования ОДУ на основе формул Грегори для транспьютерной ВС IMS ¡3012, а также текст программы аналитического интегрирования уравнений Лоренца на входном языке системы DERIVE.

Основные результаты работы.

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

2. Разработаны и исследованы итерационно - сверточные алгоритмы на основе (р, (т)-сводимых квадратурных формул Грегори. Доказаны свойства их устойчивости и аппроксимации, регулярности по Изерлссу, проведено исследование их асимптотической устойчивости на нелинейном модельном логистическом уравнении.

3. Построено семейство параметризованных алгоритмов с иерархией уровней параллелизма, что позволяет упростить их согласование с архитектурой ВС с эффективным вычислением свертки.

4. Исследована архитектура ВС тила ричного гиперкуба. Доказаны некоторые его топологические п коммуникационные свойства. Разработан алгоритм отобр;икенпя в него кольца и тора, а также графа алгоритма Кули-Тьюкп р ичного быстрого преобразования Фурье.

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

6. Исследовано движение сверхпроводящей анизотропной частицы магнитной жидкости в переменном магнитном поле. Построена область его устойчивости в плоскости параметров уравнения движения и проведено чпеле^ое моделирование с использованием разработанных алгоритмов.

По теме диссертации опубликованы следующие работы:

1. Боглаев Ю.П., Зыбин С.В., Карпенко А.П. Применение транспьютерной системы для интегрирования обыкновенных дифференциальных уравнен.1Й // Транспьютерные системы а их применение: Тез. докл. 1-й конф. Сов. Транш. Ассоц. - Звенигород. - 1991. • с.74.

2. Zybiu S.V. A parametric transformation at numerical integration of ODE // Appl. Math. Lett. - v.4., No.6. - 1991. - pp.45-50.

3. Berzigijarov P.K., Boglaev Yu.P., Karpenko A.P., Zybiu S.V. Block . representation of computing algorithms adapting with architectures of transputer systems // SERC/DTI Transputer Initiative Mailshot. - No.2., Feb. - 1991. .-pp.27-32.

4. Zybin S.V. Topological properties of p-ary hypercubes // Computing techniques in physics: Abstracts of 9-th Europ. summer school. - Skalsky. dvur, 1991.

r

5. Zybin S.V. Piirailel com'olution-based ODE solver on transputers // Computing and Automation in Nuclear Physics and Astrophysics: Abstracts of 5-th Int. school-seminar. - Sochi, 1992. p.40.

6. Kalikmanov V.I., Scliram P.P.J.M., Zybin S.V. Parametric resonance in suspensions of superconducting particles // J.Magn.Magn.Mater. - v.110. - 1992. - pp.91-98.

7. Boglaev Yu.P., Zybiu S.V. Parallel ODE solver based on convolution in a transputer/DSP environment // Transputer Research and Applications: Proc. of Int. Conf. NATUG-6. - Vancouver, 1993. 15 pp.

Г6