Введение к работе
Актуальность темы. В последнее время происходит интенсивное развитие многопроцессорных вычислительных систем (ВС) высокой производительности (от сотен ме-гафлоп до терафлоп), использующих принципы параллельной и векторной/конвейерной обработки данных, которые позволяют существенно расширить возможности и области применения вычислительного эксперимента.
Однако широкое применение многопроцессорных ВС сдерживается трудностями разработки для них параллельных алгоритмов и программного обеспечения. Практика показывает, что многие численные алгоритмы, разработанные для обычных однопроцессорных ЭВМ, зачастую оказываются малоэффективными на многопроцессорных системах. В частности, такая ситуация возникает при численном решении задачи Коши для обыкновенных дифференциальных уравнений (ОДУ), к которой приводит большое число задач математического моделирования, таких как задачи небесной механики и управляемого полета, моделирования электронных интегральных схем, химической кинетики, управления динамическими объектами, в том числе в атомной энергетике.
Можно выделить следующие основные типы параллелизма при решении задачи Коши для ОДУ (C.Gear, Calcolo, v.25, 1988): параллелизм по пространству, и параллелизм по времени. Реализация первого не вызывает больших затруднений, однако он эффективен лишь при решении слабосвязанных систем ОДУ большой размерности.
В то же время существуют задачи небольшой размерности, такие как автоматическое управление в реальном времени или численное моделирование динамических систем, где скорость вычислений является крить іескп значимой. Например в задаче численного моделирования движения сверхпроводящей частицы магнитной жидкости во внешнем магнитном поле требуется длительное интегрирование по времени уравнений движения.
Для решения пі /юбных задач на многопроцессорных ВС следует использовать алгоритмы, обладающие крупномасштабным параллелизмом по времени. Однако обычные последовательные методы, такие как многошаговы' методы или методы Рунге - Кутта, не могут служить адекватной основой для раг,|>аботтп новых параллельных алгоритмов. Дело в том, что прн распараллеливании пошаговых алгоритмов достиг» ется лишь мало масштабный параллелизм, прп котором число г .пользуемых'процессами не превышает порядка метода.
Поэтому для реализации крупномасштабного параллелизма П" примени былп предприняты поиски новых подходов прн разработке параллельны:-:
алгоритмов, большинство из которых используют итерационные методы. Одним из таких подходов является преобразовании исходного ОДУ к эквивалентному интегральному уравнению с последующим его решением посредством итерационного процесса на подынтервалах, называемых блоками. Длина этих подынтервалов обычно значительно больше шага сетки, использующейся при дискретизации интеграла, благодаря чему достигается крупномасштабный параллелизм, состоящий в одновременном вычислении па каждой итерации значений подынтегральной функции в узлах сетки (квадратурный параллелизм).
Однако разработанные на основе этого подхода параллельные итерационные алгоритмы, называемые также "waveform relaxation methods" (A.Newton et al., IEEE Trans.CAD, v.3, 1984; C.Gear, J.Comp.Appl.Math., v.38, 1991) используют в основном итерации типа Пикара и только лишь квадратурный параллелизм. Кроме того, во многих из этих работ пока недостаточно внимания уделяется исследованию проблем, которые встают при численной реализации подобных алгоритмов и при их отображении на архитектуру ВС, а также изучению их вычислительных свойств в приложениях.
Поэтому представляется весьма актуальной задачи исследования методов, использующих другие итерационные процессы, в частности, итерации типа Ньютона (позволяющие получить дополнительный параллелизм за счет свертки), п задача разработки на их основе параллельных алгоритмов, реализующих крупномасштабный параллелизм при отображении на архитектуру.многопроцессорных ЗС. Кроме того, представляет интерес их приложение к задаче исследования движения сверхпроводящей частицы магнитной жидкости во внешнем магнитном поле.
Целью работы является исследование и разработка параллельных алгоритмов и программ численного решения задачи Копт для ОДУ на основе итерационно - сверточного подхода, а также проведение вычислительных экспериментов и численного моделирования с использованием этих алгоритмов.
Это потребовало решения следующих задач:
- разработка численных итерационно - сверточных алгоритмов, позволя-
. ющих использовать дискретную свертку в качестве базовой операции,
и исследование их формальных свойств (сходимости, устойчивости, аппроксимации),
- выявление в разрабатываемых алгоритмах парал тельных структур и
уровней параллелизма и изучение вопросов их согласования с архитектурой ВС с эффективным вычислением дискретной свертки,
реализация на основе разработанных параллельных алгоритмов комплекса программ решения задачи Коши для ОДУ и исследование их вычислительных свойств на паборе тестовых ОДУ,
проведение с использованием разработанных алгоритмов и программ вычислительного эксперимента по исследованию движения сверхпроводящей частицы магнитной жидкости.
Научная новизна.
-
Разработаны параллельные итерационно - сверточные алгоритмы интегрирования задачи Коши для ОДУ на основе квадратурных формул Грегори.
-
Доказаны свойства сходимости используемых итерационных процессоь и получены оценки скорости сходимости, доказаны свойства аппроксимации и устойчивости разработанных алгоритмов.
-
Разработана структура их параллельной реализации и построено семейство параметризованных алгоритмов с иерархией уровней параллелизма. Проведено исследование топологических и коммуникационных свойств архиг'ектуры р-ичного гиперкуба, позволяющего эффектшшо реализовать разработанные параллельные алгоритмы с использованием быстрого преобразования Фурье.
-
Выполнено исследование их вычислительных свойств на набор., различных тестовых ОДУ, получены оценки ускорения и эффективности. Проведено исследование движения сверхпроводящей анизотропной ча стицы магнитной жидкости во внешнем переменном магнитном поле с использованием предложенных в работе алгоритмов.
Практическое значение. На основе разработанных в диссертационной работе параллельных алго ритмов, создац комплекс программ интегрирования задачи К>нш для систем ОДУ на траї- пьютерпых ВС, испольховавшийся для численного мо делированпя дин мпческон системы, описывающей колеСания сверхпроводящей частицы магнитной жидкости.
Использование предложенных в работе алгоритмов потоляеі разр.ша-тывать параллельные программы для ВС с векторными/конвейерными шп>
сигнальными процессорам!1, а также создавать специальные процессоры-интеграторы ОДУ (по типу систолических или сигнальных) для применения их в устройствах управления в реальном времени.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на советско-британском семинаре по транспьютерным системам (г. Москва, 1990), 1-й Всесоюзной конференции "Транспьютерные, системы и их применение" (г. Звенигород, 1991), 9-й Международной школе "Вычислительные методы в физике" (г. Скальский двор, 1991), 5-й Международной школе-семинаре "Численные методы и автоматизация в ядерной физике и астрофизике" (г. Сочи, 1992), российско-французском семинаре по новым информационным технологиям и параллельным лычисленпям (г. Москва, 1993), 6-й Международной конференция NATUG-6 "Транспьютерные системы и их применения" (г. Ванкувер, 1993).
Публикации. По результатам работы имеется 7 опубликованных работ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения, 33 рисунков и таблиц, списка литературы из 196 наименований и двух приложений, изложенных на 155 страницах машинописного текста.
