Исследование эффективности применения параллельных вычислительных систем для моделирования движения космического аппарата

Рисунок 3 - Главная экранная форма системы РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

ПЕРЕЧЕНЬ ССЫЛОК

1. Сахаров А.А. Концепция построения и реализации информационных систем, ориентированных на анализ данных.- Системы управления базами данных, 1996, №4. -С.55-70.

2. Сахаров А.А. Принципы проектирования и использования многомерных баз данных.- Системы управления базами данных, 1996, №3. - С.44-59.

3. Львов В. Создание систем поддержки принятия решений на основе хранилищ данных.- Системы управления базами данных, 1997, №3. - С.30-40.

4. Баженова И. Ю. Oracle 8/8i - М.: Диалог - МИФИ, 2000. -304с.

5. Пейдж, Вильям Дж. Использование Oracle 8/8i / Пер. с англ.-М.: Издательский дом Вильямс, 2000.-1024 с.

6. Гарнаев А.Ю. Использование MS Excel и VBA в экономике и финансах. - СПб.: БХВ - Санкт-Петербург, 2000. - 336 с.

7. Долженков В.А., Колесников Ю.В. Microsoft Excel 2000. -СПб.: БХВ -Петербург, 2000. - 1088 с.

8. Карлберг К. Бизнес-анализ с помощью Excel: Пер. с англ. -К.: Диалектика, 1997. - 439 с.

9. Карпов Б. Visual Basic 6: Специальный справочник. - СПб.: Питер, 2000. - 416 с.

УДК 681.3.06

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

Н.Д.Пиза

В cmammi досл1джуеться коефщ1ент прискорення та ефективтсть паралельних блочних однокрокових nemodie iнmeгрувaння для моделювання руху кocмiчнoгo апарата на паралельних обчислювальних системах з рoзпoдiлeнoю пам'яттю i рeaлiзaцieю oбмiну даними nix процесорами за допомогою функций бiблiomeки MPI.

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

In the article the acceleration coefficient and the efficiency of the parallel block one-step integration methods are investigated on the parallel computing systems with distributed memory and implementation of the data exchange among the processors with the help of MPI library functions.

ВВЕДЕНИЕ

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

Моделирование движения КА сводится к интегрированию обыкновенных дифференциальных уравнений (ОДУ). Как отмечают авторы работы [2], в последнее

время появилось большое количество численных методов интегрирования ОДУ, которые ориентированы на вычислительные системы с параллельной архитектурой, однако практическое использование большинства методов не всегда оправдано, поскольку многие из них либо обладают численной неустойчивостью, либо имеют очень сложную структуру, приводящую к потере эффективности. Блочные методы интегрирования обладают "внутренним" параллелизмом, поскольку допускают одновременное вычисление интегрируемых функций в нескольких точках временной оси моделирования. В работе [3] предложена методика экспериментальной оценки точности параллельных блочных методов для интегрирования дифференциальных уравнений, описывающих модель движения КА.

ПОСТАНОВКА ЗАДАЧИ

Модель движения КА состоит из уравнений, описывающих движение центра масс КА по орбите и движение КА относительно центра масс. Модель движения КА относительно центра масс представляется совокупностью динамических и кинематических дифференциальных уравнений [4, 5]:

+ ИХ Jю = М,

б = (бо - гоо°б),

у- ю2х + 2юзх = тз^ ,

дП ' ду

г = т

-дП д2 ,

радиус-вектор, задающий положение

где г = (х у г)3 КА в гринвичской системе координат;

т - гравитационная постоянная Земли, Ю3 - угловая скорость вращения Земли;

П - возмущающая часть гравитационного потенциала Земли.

Структурная схема моделирования движения КА представлена на рисунке 1. Здесь О , п , foГb , 'оГь , е ,

а - Кеплеровы элементы орбиты; ф( 0), Ф( 0), у( 0) -начальные значения углов Эйлера, определяющие положение КА относительно орбитальной системы координат; г и V - положение и скорость центра КА в гринвической системе координат; П - гравитационный потенциал Земли; Вв - вектор геомагнитной индукции Земли в проекциях на оси связанной системы координат; Ь - управляющий магнитный момент; Мв - сум марн ый возмущающий момент.

о , юп, гол

'„гк , е , а

Модель дес

1 >

Модель оо

ол ел

матрица моментов инерции

где J = \\JnmW (п, т = х, у, г) ;

И - вектор угловой скорости КА в связанной системе координат;

М - вектор главного момента сил, действующих на КА;

б = Чо + 1 + ' 2 + ?з' 3 - кватернион, составленный из действительных элементов и трех мнимых единиц, формально совпадающих с ортами базовой (орбитальной) системы координат; данный кватернион определяет взаимное положение орбитального и связанного базисов;

ю о - кватернионное отображение вектора орбитальной

скорости КА, заданного проекциями на оси орбитальной системы координат;

о - знак умножения кватернионов.

Математическая модель движения центра масс КА по орбите имеет вид [6]:

.. 2 „ . д и

х - ю2х - 2ю3У = ,

Б"

Модель ооо оел

Модель Модель

ле ос

о ое оео

£ ме

Модель д ео

Рисунок 1 - Структурная схема моделирования движения КА

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

ПАРАЛЛЕЛЬНЫЕ БЛОЧНЫЕ ОДНОШАГОВЫЕ

МЕТОДЫ

Будем рассматривать одношаговые двухточечный и четырехточечный параллельные блочные методы для решения задачи Коши: у) = f(х,у) , у(0) = Уо . Блочным

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

г , К

<2

лельных вычислительных систем. Метод является одношаговым, поскольку для расчета значений в новом блоке используется только последняя точка предшествующего блока. Пусть уп - приближенное значение решения задачи Коши с начальным условием в точке хп -начальной точке обрабатываемого блока. Предполагается, что в пределах одного блока точки сетки значений независимой переменной х находятся на равных расстояниях: хп + г = хп + гк , где г = 1, к, к - шаг сетки.

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

порядка точности О (к4) с двухточечным блоком реализуется формулами [7]:

полнять параллельно. В данном методе решение в п -м блоке получается сразу в четырех точках: п1, п2, п3, п4 -это, соответственно, у1 5, у25, у3 5, у4 5 причем, значение у 4 5 является начальным для следующей итерации, т.е. выступает в качестве у в п + 1-м блоке в приведенных выше формулах. Условная схема процесса итераций показана на рисунке 3.]

уп + г,0 = уп + гк/„, г = 12, уп + 1, я + 1 = уп+ 12 ( 5/п + 8/п + 1, я-/„ + 2 , я ^

уп + 2, я + 1 уп + 3

я =0,1,2 .

Как видно из структуры приведенных рекуррентных формул, вычисления значений функций /„ + 1 я, fn + 2 я ,

и получаемых решений уп + 1 я + 1, уп + 2 я + 1 , можно выполнять параллельно. Таким образом, решение в п -м блоке получается сразу в двух точках: п1 , п2 - это, соответственно у1 3, у2 3, причем, значение у2 3 является начальным для следующей итерации, т.е. выступает в качестве у в п + 1-м блоке в приведенных выше формулах. На рисунке 2 показана условная схема процесса итераций.

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

порядка точности О (к 6) с четырехточечным блоком реализуется формулами [7]:

уп + г, 0 = уп + гк/„,г = М,

Рисунок 2 - Схема процесса итераций двухточечного блочного метода

У1.5

У2.5

УЗ,5

У4,5

У2,5

п+1

Уз,5

vn+1 У4,5

ъ

п п,

п4 (п+1), (п+1)2 (п+1)з (п+1)4 п+1

Рисунок 3 - Схема процесса итераций четырехточечного блочного метода

ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВИЯ ПАРАЛЛЕЛЬНЫХ БЛОЧНЫХ МЕТОДОВ

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

5 =

я = 0,4.

уп + 1, я + 1 = уп+ 720(251/„ + 646/„ + 1, я -

-264/„ + 2, я +1°6/п + 3, я-1^ + 4, я ); уп + 2, я + 1= уп + 90(29/п + 124/п + 1, я + ;

+ 2/„ + 2, я +4/п + 3, я-/п + 4, я ) ^ 3к

уп + 3, я + 1= уп + £>0 ( 9/п + 34/п + 1, я + ;

+ 24/„ + 2, + 14/„ + 3, / + 4, я) : 2к

уп + 4, я + 1= уп + 45 (1/„ + 32/п + 1, я + .

+ 12/„ + 2, я+32/ + 3, я+7/п + 4, я ) '

Здесь также вычисления значений функций /п + 1, я, /п + 2, я, /п + 3, я, /п + 4, я и получаемых ре0ений у„ + 1, я + 1, у„ + 2, я + 1, у„ + 3, я + 1, у„ + 4, я + 1 можно вы-

где 31 - время выполнения программы одним процессором;

Тп - время выполнения программы процессорами. Эффективность параллельного алгоритма определяется как:

£ = 5

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

пространство и для обмена данными между параллельными процессорами используется модель передачи сообщений через коммуникационную среду. В качестве технологии параллельного программирования будем использовать известный интерфейс для организации обмена сообщениями в параллельных вычислительных системах - MPI [1]. Таким образом, будем исследовать ускорение и эффективность параллельных блочных одношаговых методов для моделирования движения КА на параллельных вычислительных системах с распределенной памятью и реализацией обмена данными между процессорами с помощью функций технологии MPI.

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

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

нить 7 обменов данными, а для четырехточечного - 63 обмена. Обмены вызывают дополнительные накладные расходы в параллельной вычислительной системе, отсутствующие при последовательном выполнении программы.

По нашей оценке, полученной экспериментально, вычислительная сложность правых частей приведенных выше уравнений модели движения КА эквивалентна

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

С

L

7

т Ут ¥ Тт

Г

/ У? !

ТТ т

У т У тТ т

т

1Г т

^ т

"""

У т

Т

к.-

г

"•У У

Рисунок 4 - Алгоритм итерации параллельного блочного двухточечного метода

У

Рисунок 5 - Алгоритм итерации параллельного блочного четырехточечного метода

m I I сс2

y-,h 7

L

У ,h

Zd

Выгчислить f

7 ! ] !

Вычислить

yn+10=yn+hfn

Выгчислить f .

] I

О слВ. f.

>4-

fn+2,s Hl"

I

я1

I

В^14ислить Уп+1 s+1 1 ' —,

I I

|РР1Пчитьуп+4,5(уп)| J

/ yn,h /

I Выгчислить f I

I n

Выгчислитъ

yn+2,0=yn+2hfn

Выгчислить f .

слВ, fn+2s

I

Ï?

Вычислить Уп+2 s+1 I -1-

I ^ ^л^читьУп+4,5(УП) I

ÇE

L

Выгчислить f

I

Выгчислить

yn+3,0=yn+3hfn

Выгчислить f .

О слй> f л

[

I Выгчислить Уп+3

[1РчитьУп+4,5(УП)|

L

У , h

Zd

7

Выгчислить f

Выгчислить

y =y +4hf n+4,0 n n

Выгчислить f .

Vc 1м

] ^ ЦЦЦУЛ1Ч.1п+),5

О слй> f ^

I .—И—

| | В^1числить Уп+4,,

I I

I____

с  )

s=0

s=0

s=0

s=0

n+2,s

n+2,s

n+3,s

n+3 ,S

n+3,s

n+4,s

n+4,s

Для моделирования движения КА и экспериментального исследования ускорения и эффективности параллельных блочных методов интегрирования разработана программа на языке С++ с использованием библиотеки MPI реализации MPICH (MPI CHammeleon) 1.2.4.

Эксперименты проводились на двух параллельных системах. В качестве первой параллельной системы использовалась компьютерная сеть типа Fast Ethernet с рабочими станциями Intel Pentium IV (1.76 ГГц) одной из компьютерных лабораторий Запорожского национального технического университета. В качестве второй параллельной системы был использован SCI-кластер Петродворцового телекоммуникационного центра1. SCI-кластер имеет следующие характеристики: число узлов -20, число процессоров на узле - 2, тип процессоров - Intel Pentium III (933 МГц), объем ОЗУ на узле 512 Мб; способ соединения узлов - однонаправленные кольца SCI для передачи данных в системе MPI и сеть Fast Ethernet для управления машинами.

Эксперименты заключались в измерении затрат времени на моделирование 10000 секунд полета КА с шагом

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

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

Результаты вычислительных экспериментов приведены в таблице 1 и позволяют определить условия, при которых моделирование движения КА эффективно на параллельных вычислительных системах таких классов.

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

Таблица 1 - Результаты вычислительных экспериментов

Количество вычислительных операций х 104 Время вычислений при применении блочного метода, секунды

двухточечный четырехточечный

последовательный параллельный последовательный параллельный

Net SCI-single/ SCI-double Net SCI-single SCI-double Net SCI-single/ SCI-double Net SCI-single SCI-double

1 3,23 3,80 5,11 3,46 3,11 4,86 7,84 8,83 2,93 2,83

2 6,34 4,54 6,93 3,87 3,55 9,48 8,97 10,14 3,26 3,10

2,5 8,02 4,93 7,92 4,11 3,77 11,82 9,54 10,80 3,43 3,29

3 9,48 5,30 8,69 4,32 3,98 14,13 10,09 11,50 3,59 3,44

5 15,62 6,81 12,25 5,20 4,85 23,46 12,36 14,18 4,24 4,16

7 21,84 8,30 15,80 6,09 5,71 32,73 14,31 16,89 4,92 4,82

10 31,16 10,55 21,15 7,42 7,03 46,70 17,72 20,88 5,90 5,83

26 80,98 22,62 49,59 14,47 13,92 121,37 35,82 42,06 11,22 11,06

51 158,27 41,44 93,65 25,54 24,75 237,40 64,05 75,35 19,55 19,56

76 236,19 60,25 137,75 36,55 35,56 354,50 92,32 108,67 27,87 27,90

101 313,90 79,10 181,71 47,62 46,35 471,18 120,59 141,76 36,15 36,26

151 469,18 116,80 269,64 69,21 68,06 704,40 177,04 208,23 52,79 52,87

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

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

Как видно из представленных результатов, применение параллельных блочных методов становится эффективным при решении задачи моделирования движения КА на первой параллельной системе, когда вычислительная сложность правых частей уравнений превышает 2,5 Х 104 вычислительных операций. Применение параллельных блочных методов для решения данной задачи на БС1-кластере эффективно уже в начальной постановке задачи, без усложнения правых частей уравнений. На рисунках 6 и 7 показаны зависимости коэффициента ускорения и

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

1 SCI-double 1

SCI-single

/

SCl-double 2\

SCI-single 2\ \  ' \ ---' ^ '

\ 4 ¿^ \-Net 4

\Net2 i

МО3 МО4 1 105 МО6

количество вычислительных операции

Рисунок 6

Таблица 2 - Затраты времени на обмен данными о"

Блочный метод Время, секунды

Net SCI-single SCI-double

двухточечный 2,113 0,208 0,043

четырехточечный 8,192 1,027 0,926

Рисунок 7

ВЫВОДЫ

Таким образом, моделирование движения КА на параллельных вычислительных системах с помощью параллельных блочных методов интегрирования может быть эффективным по точности [3] и эффективным по быстродействию при определенных значениях произво-

дительности процессоров, коммуникационных средств и сложности модели. Результаты исследований предполагается использовать при создании программно-аппаратных средств моделирования для наземной отработки и испытаний системы управления КА.

ПЕРЕЧЕНЬ ССЫЛОК

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.-СПб.: БХВ-Петербург, 2002. - 608 с.

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

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

4. Алексеев К.Б., Бебенин Г.Г. Управление космическими летательными аппаратами. - М.: Машиностроение, 1974. -300 с.

5. Бранец В.А., Шмыглевский И.П. Применение кватернионов в задачах ориентации твердого тела. - М.: Наука, 1973. -320 с.

6. Справочное руководство по небесной механике и астродинамике / Абалкин В.К., Аксенов Е.П., Гребенников Е.А. и др. Изд.2-е.-М.: Наука, 1971.-584 с.

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

8. Молчанов И.Н. Введение в алгоритмы параллельных вычислений / АН УССР, Институт кибернетики им. В.М. Глушко-ва. - К.: Наукова думка, 1990. -127 с.

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

УДК 514.1/8:519.8/71

КОНФИГУРАЦИЯ ОБЪЕКТА КАК ИНТЕРФЕЙС МЕЖДУ МАТЕМАТИЧЕСКИМ И ФИЗИЧЕСКИМ СОДЕРЖАНИЕМ МОДЕЛИ

В.П.Сизиков

Установлено, что конфигурация объекта или поля является физически значимой характеристикой, а для адекватного учета конфигурации объекта необходимо держать ориентир на ее 3-мерную пространственную протяженность. Картина развернута на примере движения объекта в физическом поле, в том числе, космического аппарата с тросой системой.

It is established that the configuration of an object or a field is a physically meaningful characteristic and to adequately consider the configuration of an object it is necessary to be orientated on it's 3-dimensional spatial extent. The picture is developed on the example of movement of an object in the physical field including the space apparatus with cable system.

ВВЕДЕНИЕ

В [1] М.М. Лаврентьев справедливо указывает, что в математической физике XX в. значительное место занимают модели с недостаточно осмысленным содержанием, а процедуры моделирования в основном сводятся к подгонке теоретических положений под эмпирический материал. Это же относится и к другим предметным

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

Потребности к формированию указанного интерфейса у автора возникли после получения и проработки им серии результатов по тематике управления [2-4]. Вначале традиционно главное внимание уделялось учету понятий полных управляемости и наблюдаемости для систем управления, вырабатывались соответствующие критерии в терминах полноты ранга подходящих матриц. Но когда такие критерии удалось обобщить на разные варианты систем и форм управления, выяснилось, что выпо-