Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003

Максимальное количество итераций = 1000.

Результаты:

Невязка N*= 0.079876315553973787

Максимальное отклонение = 0.14108326745504 Было проделано 1000 итераций. Заданная точность не была достигнута за данное количество итераций.

Полученные коэффициенты: a1=0.000017295694372152 a2=-0.014768003524118280 a3=-4.634255701566933 a4=-6562.3657356183876 a5=1.23540311720519 a6=-0.000237613339192939 b1=89.64996337890625 b2=-88.135528564453125 b3=-31.737518310546875 b4=1.56097412109375 b5=18.604278564453125

131

Рис.1

Литература

1.Стронгин Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). – М.: Наука, 1978, 240с.

2.Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. – М: Физматгиз, 1963, 400с.

3.Волков Е.А. Численные методы: Учеб. пособие для вузов. – М.:

Наука. 1987, – 248с.

4.Мешков А.В., Тихомиров Ю.В. Visual C++ и MFC: Пер. с англ. – СПб.: БХВ-Петербург, 2002. – 1040с.

5.Сергеев Я.Д., Стронгин Р.Г., Гришагин В.А. Введение в параллельную глобальную оптимизацию. Учебное пособие. Нижний Новгород: Изд-во Нижегородского университета, 1998. 87 с.

6.Бахвалов Н.С. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения). – М.: Наука, 1975.

ПРИМЕНЕНИЕ КЛАСТЕРНЫХ СИСТЕМ ДЛЯ МОДЕЛИРОВАНИЯ ДВИЖЕНИЯ КОСМИЧЕСКОГО АППАРАТА

Н.Д. Пиза, Р.К. Кудерметов

Запорожский национальный технический университет, Украина ndp@zntu.edu.ua, krk@zntu.edu.ua

Введение

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

132

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

Значительную долю вычислений при моделировании движения КА занимают вычисления, связанные с интегрированием уравнений движения. В данной статье приведены результаты исследования характеристик параллельных блочных методов интегрирования, реализованных на языке C с использованием функций библиотеки MPI (реализация mpich 1.2.4) при моделировании движения КА на кластерных вычислительных системах.

Параллельные блочные одношаговые методы интегрирования

Для задачи Коши для системы обыкновенных дифференциальных уравнений

параллельный блочный двухточечный одношаговый метод четвертого порядка точности O(h4) на равномерной сетке по переменной t с шагом h > 0 реализуется следующими рекуррентными формулами [1]:

yn+r,0 = yn + rhf n , r =1, 2

Как видно из структуры приведенных формул, вычисления

значений функций fn+1, s, fn+2, s и получаемых решений yn+1, s+1, yn+2, s+1, можно выполнять параллельно. Таким образом, решение в n-м блоке

получается сразу в двух точках: n1, n2 – это, соответственно, y1,3, y2,3, причем, значение y2,3 является начальным для следующей итерации, т.е. выступает в качестве y в n + 1-м блоке.

Рекуррентные формулы для параллельного блочного четырехточечного одношагового метода шестого порядка точности O(h6) имеют вид [1]:

yn+r,0 = yn + rhfn , r =1,4 ,

133

четырех точках: n1, n2, n3, n4 – это, соответственно, y1,5, y2,5, y3,5, y4,5, причем, значение y4,5 является начальным для вычислений в

следующем блоке.

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

Точность одношаговых параллельных блочных методов

В работе [2] показано, что для одношаговых блочных методов локальная ошибка в узлах блока имеет порядок O(h k+2), где k – число узлов блока. В работе [3] разработана методика оценки точности параллельного моделирования движения КА вокруг собственного центра масс с помощью блочных одношаговых методов. Смысл методики состоит в сравнении результатов численного интегрирования уравнений движения КА с аналитическим решением, полученным для случая конического движения КА. На рис.1 приведен пример оценки погрешности моделирования движения КА различными методами интегрирования.

134

Рис. 1

Программа моделирования реализована на языке С с использованием функций библиотеки MPI реализации mpich 1.2.4. Формат представления данных – double. Моделирование выполнялось на параллельной системе, состоящей из рабочих станций Pentium IV (1,76 ГГц), объединенных сетью Fast Ethernet. Погрешность определялась по результатам интегрирования движения КА в течение 1000 секунд полета с различными шагами дискретизации. Для сравнения на рис.1 показаны результаты оценки погрешности моделирования для последовательного метода Рунге-Кутта 4-го порядка.

Исследование быстродействия параллельных блочных методов для решения задачи моделирования движения КА

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

135

где T1 – время решения задачи на одном процессоре, Tp – время решения задачи на p процессорах.

Формулы для оценки T1 и Tp в случае двухточечного метода можно получить из анализа (1) (детально алгоритмы параллельных блочных методов представлены в работе [4]):

где n – размерность вектора неизвестных интегрируемой системы уравнений;

ts, tm – время, затрачиваемое на операции сложения и умножения, соответственно;

tc – время, необходимое для обмена данными между процессорами; tf – время вычисления правых частей уравнений.

Очевидно, что ускорение зависит от сложности моделируемой системы и характеристик вычислительной системы. Как правило, основные затраты времени при численном интегрировании уравнений, описывающих движение КА, составляют затраты на вычисления правых частей системы уравнений, т.е. tf в (4) и (5).

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

Эксперименты проводились на двух параллельных системах. В качестве первой параллельной системы использовалась компьютерная

136

телекоммуникационного центра3. SCI-кластер состоит из 20 двухпроцессорных узлов, тип процессоров – Intel Pentium III Copermine (933 MГц), oбъем ОЗУ на узле 512 Мб, способ соединения узлов – однонаправленные кольца SCI для передачи данных в системе MPI и сеть Fast Ethernet для управления машинами.

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

Результаты вычислительных экспериментов приведены в табл.1. Для ссылок на результаты экспериментов введены следующие обозначения: Net – результаты, полученные на первой параллельной системе, SCI-single и SCI-double – результаты, полученные на второй параллельной системе в вариантах single и double соответственно.

3Авторы выражают свою признательность доцентам кафедры вычислительной физики Санкт-Петербургского государственного университета Комолкину Андрею Владимировичу и Немнюгину Сергею Андреевичу за содействие в организации экспериментов на SCI-кластере Петродворцового телекоммуникационного центра.

137

Для измерения затрат на обмены между процессорами были применены тесты скорости обменов, разработанные в НИВЦ МГУ [5]. Общие затраты времени на выполнение обменов в двухточечном и четырехточечном методах для рассматриваемых вычислительных систем представлены в табл.2.

138

Рис. 2.

Рис. 3.

На рис. 2 и 3 показаны зависимости ускорения и эффективности параллельного решения задачи от принятой оценки вычислительной сложности правых частей системы уравнений. При этом используются введенные выше обозначения Net, SCI-single и SCI-double, а цифры 2 и 4 указывают, соответственно, на двухточечный и четырехточечный методы.

Полученные результаты можно интерпретировать следующим образом. Обозначим через m коэффициент в первой колонке табл.1. Тогда, используя оценки (4) и (5), общие затраты времени на вычисления на одном процессоре и параллельной системе для двухточечного метода интегрирования можно выразить как

где С1 и Cp – суммарные затраты времени на последовательную и параллельную реализации метода интегрирования, соответственно.

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

139

интегрирования. Подставляя (6) и (7) в формулу для ускорения (3) и учитывая, что применение параллельной системы становится эффективным при S > 1, получим:

Выводы

Таким образом, применение параллельных блочных методов становится эффективным при решении задачи моделирования движения КА на первой параллельной вычислительной системе, когда m > 2.43, т.е. оценка вычислительной сложности правых частей уравнений превышает 2.43 104. Для SCI–кластера значение m меньше нуля, это означает, что его применение эффективно уже для исходной постановки данной задачи, т.е. при оценке сложности меньше чем 104. Аналогичные условия можно получить и для четырехточечного метода.

Литература

1.Системы параллельной обработки / Под ред. Д. Ивенса. – М.: Мир, 1985. -416 с.

2.Фельдман Л.П., Дмитриева О.А. Разработка и обоснование параллельных блочных методов решения обыкновенных дифференциальных уравнений на SIMD-структурах // Наукові праці Донецького національного технічного університету. Вип. 29. – Донецьк, 2001. С. 70-79.

3.Пиза Н.Д., Кудерметов Р.К. Применение параллельных блочных методов для моделирования движения космического аппарата // Вiсник технологiчного унiверситету Подiлля. – 2003. – №3, T.1. –

С. 93-96.

4.Пиза Н.Д. Исследование эффективности применения параллельных вычислительных систем для моделирования движения космического аппарата // Радиоэлектроника. Информатика. Управление. – 2003. – №1. – С. 102-108.

5.Андреев А.Н., Воеводин В.В. Методика измерения основных характеристик программно-аппаратной среды www.dvo.ru/bbc/ benchmarks.html.

140