Иерархический подход к созданию параллельных алгоритмов для задачи идентификации параметров объектов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Р Г Б ОД

- 2 ОКТ 1995

На правах рукописи УДК 519.687

ЯСТРЕБОВА Елена Владимировна

ИЕРАРХИЧЕСКИЙ ПОДХОД К СОЗДАНИЮ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ЗАДАЧ ИДЕНТИФИКАЦИИ ПАРАМЕТРОВ

ОБЪЕКТОВ

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

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

Москва - 1995

Работа выполнена в Институте высокопроизводительных вычислительных систем РАН .

доктор физико математических наук, профессор A.M. Попов, доктор технических наук, профессор, член-корреспондент РАН, директор НИИ "Квант" В. К. Левин; кандидат физико-математических наук, доцент В.Г. Никонов.

Научный руководитель-Официальные оппоненты

Ведущее предприятие:

Московский Инженерно - Физический институт.

Защита диссертации состоится "'¿^ " 995 г. в

■/^З^часов на заседании диссертационного совета К 200.45.01 Института Высокопроизводительных Вычислительных систем РАН по адресу: г. Москва, ул. Вавилова, д.37.

С диссертацией можно ознакомиться в библиотеке ИВВС

РАН.

Автореферат разослан "<¿3- " ¿¿^^.<4^.1995 г.

Ученый секретарь диссертационного совета ИВВС РАН Кандидат физико-'

-математических наук [/!/Миронов С.В./

Общая характеристика работы.

Актуальность темы диссертации. Описание поведения сложной динамической системы связано с необходимостью определения большого количества параметров. Применение точных методов в таких ситуациях сопряжено с большим объемом математических расчетов, что не всегда бывает оправданно, тем более что параметры любой сложной системы известны как правило достаточно грубо. Поэтому одним из подходов к описанию и управлению сложными системами является определение параметров объектов по его реакциям на возмущения. Такой подход используется в теории идентификации систем и состоит в построении математической модели объекта по данным, полученным в результате эксперимента. В настоящее время широкое распространение методы идентификации нелинейных динамических систем получили в задачах управления сложными объектами. Систематизация результатов по методам идентификации систем приведена в трудах В.В. Солодовникова, К.А. Пупкова, В.М. Глушкова, В.И. Капалина, K.-U.Crusa и др. Одним из путей решения задач идентификации в реальном времени является использование вычислительных систем параллельной архитектуры.

Поэтому актуальным является создание и исследование параллельных алгоритмов решения задач идентификации параметров объектов.

Методы идентификации позволяют перейти к решению задач управления. Решение сложных задач оптимального управления в реальном времени требует создания параллельных алгоритмов для данного круга задач. Достаточно полное исследование известных численных методов оптимизации с точки зрения создания соответствующих им параллельных алгоритмов приводится, например, в книге D.P. Bertsekas, J.N. Tsitsiklis (Parallel and distributed computation: Numerical methods.-Englewood Cliffs: Prentice - Hall, 19Й9).

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

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

- отсутствие алгоритмических ограничений на максимально допустимое число процессоров;

- крупноблочная организация задачи.

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

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

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

Целями диссертации являются:

1) разработка и теоретическое исследование параллельных алгоритмов для решения задач идентификации параметров и управления объектом;

2) построение интерактивных алгоритмов организации эффективных параллельных вычислений для различных топологий межпроцессорных связей в параллельных вычислительных системах на основе иерархического представления структуры задача:

3) реализация на мультитранспьютерной системе комплекса программ решения задачи идентификации параметров и управления нелинейной динамической системы.

Научная новизна работы заключается в следующем:

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

2. Разработана иерархическая схема решения поставленной задачи и обоснована ее сходимость;

3. Предложены и исследованы параллельные реализации методов решения ряда задач идентификации и управления нелиненых динамических систем;

4. Разработанные алгоритмы для рассмотренных задач реализованы на мультитранспьютерной системе;

Практическая ценность работы:

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

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

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

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

Апробация. Результаты диссертационной работы докладывались на Второй Международной научно-технической конференции "Актуальные проблемы фундаментальных наук", проходившей в рамках симпозиума "Информационные технологии автоматизации и управления в современной техносфере" (Россия,г. Москва,24-28 янв, 1994), на Первом международном симпозиуме "Интеллектуальные системы", (Россия, г. Махачкала, Дагестан, 22-27 июня, 1994), а также на научных семинарах: кафедры АСВК МГУ, кафедры Системы автоматического управления МГТУ им. Н.Э.Баумана, математического отделения ИВВС РАН.

Публикации. По теме диссертации опубликовано 9 научных работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и двух приложений. Объем диссертации без приложений - 140 стр. Список литературы содержит - 85 наименований.

СОДЕРЖАНИЕ РАБОТЫ.

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

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

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

В ' первом параграфе приводится математическая постановка задачи идентификации нелинейной динамической-' системы и описывается метод ортогональных моментов ( Пупков К.А.,Капалин В.И.,Ющенко A.C., Функциональные ряды- в теории нелинейных систем.-М.:Наука,1976. ) решения поставленной задачи с внесенными в него изменениями.

Во втором параграфе предложены параллельные

алгоритмы, реализующие метод ортогональных моментов.

*

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

В третьем параграфе рассмотрен метод локальных вариаций ( Черноусько Ф.Л., Баничук Н.В., Вариационные

задачи механики и управления.- М.: Наука, 1973. ) решения задач оптимального управления. '

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

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

(

: - отсутствие алгоритмических ограничении на максимально допустимое число процессоров;

- малые потери на коммуникацию процессоров через каналы связи;

- равная загруженность параллельно работающих процессоров;

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

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

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

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

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

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

Обозначим граф алгоритма с максимальным числом

вершин на ярусе равном N как Г1^ . Множество различных топологий межпроцессорных связей в N - процессорных

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

выполнения для каждого конкретного графа алгоритма Г1^. 1

Элементы х^ е Xм описывают альтернативную топологию связей N процессоров. Сравнительная эффективность

альтернатив хМ определяется бинарным отношением Ф на Х1^.

Введенное бинарное отношение представляет систему из двух критериев:

1. Время работы многопроцессорной системы по выполнению операций алгоритма;

2. Время простоев, возникающее вследствие потерь на синхронизацию обменов, непосредственные обмены и накладные расходы на реконфигурацию сети.

Минимизация первого критерия эффективности позволит уменьшить общее время работы параллельного алгоритма.

' Минимизация второго критерия эффективности преследует цель максимизировать загруженность процессоров.

Вводится отображение ör(rN,xN) графа алгоритма rN на топологию межпроцессорных связей параллельной

N

вычислительной системы х , результатом которого является граф параллельного алгоритма ГПАМ .

Задача проектирования графа параллельного алгоритма

IT1AN состоит в выделении из XN какой-либо минимальной с

точки зрения бинарного отношения Ф альтернативы xNb модели:

xNeX+N = Min (a(rN,xN) ,Ф) (1)

.N „ „N

х е X

В современных задачах число N. равное максимальному

числу вершин на ярусе в графе Г1^ , как правило, много больше числа транспьютеров в сети.

Поэтому предлагается использовать возможности построения иерархии задач.

( Для этого введем иерархическую цепочку представления

грйфа алгоритма. Г1^ в виде последовательности

дезагрегируемых графов Г 1 1 , где

. ' N С-1 N Л

г '-1 = (г 1 ), 1

N' ,s

Г s - граф с наименьшей^степенью детализации, N_, О

Г и - граф с наибольшей степенью детализации,

-1 "V

f (Г ) - функция дезагрегирования, задающая закон

- функ!.

раскрытия вершин графа Г ^ . s - число уровней иерархии.

Каждому уровню иерархии сопоставим свое бинарное отношение Ф^ , определяющее сравнительную эффективность

альтернатив х 1 .

Тогда задачу (1) будем решать по следующей декомпозиционной схеме:

N N .£ N

X = Min (a(f7 (Г 1 ),х )

* N N е г-1 '

х

i=s.....1 (2)

с начальным условием:

N ,s N

X о = Min (а( Г s ,х s) ,Ф ) . * N N 3

х s е X s

В качестве решения принимается произвольный элемент

множества X®.

*

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

графа Г^1 , и некоторых ограничениях на граф rN . Однако на практике возможно нарушение данных условий. Поэтому в схему проектирования (2) вводится диалог пользователя, моделирующего структуру параллельных вычислений, и ЭВМ.

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

Далее формулируется иерархический интерактивный алгоритм типа "ветвей и границ" моделирования параллельных вычислений, реализующий схему проектирования (2). Рассмотрен частный случай графов алгоритмов, заданных бинарными деревьями. Для выделенного класса задач на основе разработанной схемы проектирования параллельных вычислений построен и реализован в виде системы программ алгоритм типа "ветвей и границ", предназначенный для распределения параллельных вычислений в рассматриваемых задачах. Приводятся результаты численного тестирования данного алгоритма для различных графов и сравнение с алгоритмом, не использующим иерархическое представление графа алгоритма. Численное исследование позволило сделать следующие выводы:

I

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

2) Зависимость времени работы иерархического алгоритма от числа вершин в графе алгоритма близка к квадратичной.

В третьем параграфе разработан детерминированный ■»метод "конденсации", позволяющий создать иерархическую структуру графов алгоритмов на основе сведений о существующей информационной зависимости вершин графа алгоритма. В основу выбора вариантов объединения операций алгоритма положена оптимизационная задача. Предложенный метод может быть эффективно использован в интерактивном алгоритме иерархического проектирования, сформулированном в §2 главы 2. Положительным свойством данного метода является способность выявления топологии межпроцессорных связей в

параллельной вычислительной системе наиболее эффективной с точки зрения вычислительных затрат для конкретного графа алгоритма. _ • '

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

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

л

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

I \ п -1 з

а -у(п,(Ь)+ Е а, (Ь)-у(Х) (О = х(Ь). п к = 0 к

Исследования показали, что для параллельного алгоритма,

не использующего иерархическое агрегирование вершин графа

алгоритма, было обнаружено падение ускорения вычислений на

20 процентов на 4-х транспьютерах. Обнаруженное падение

ускорения по сравнению с линейным возникает вследствие

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

Способом повышения эффективности вычислений явилось

увеличение загрузки процессоров за счет иерархического

объединения операций параллельного алгоритма. В результате

было получено значение эффективности вычислений равное 95 %*.

при идентификации нелинейной системы 3-го порядка.

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

В третьем параграфе рассмотрена задача управления плазменным разрядом в токамаке и приводится сравнение результатов тестирования данной задачи, решаемой модифицированным методом локальных вариаций, с решением этой же задачи методом последовательных приближений без использования параллельных вычислений. Применение 4-х транспьютерной системы для решения рассмотренной задачи I позволило снизить время работы программы минимум на порядок. Полученные практические результаты согласуются с теоретическими оценками. Применение крупноблочного представления структуры задачи позволило получить значение эффективности вычислений параллельного алгоритма модифицированного метода локальных вариаций порядка 93% на 4-х транспьютерной системе. Проведенное численное исследование позволило выделить круг задач, для решения ■ которых целесообразно использовать модифицированный метод локальных вариаций:

- задачи, в которых вычисление производных сопряжено со значительными трудностями;

задачи, где требуется быстрое нахождение грубого приближения решения, после чего вычисления могут быть продолжены другими методами.

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

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

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

ЗАКЛЮЧЕНИЕ. (Основные результаты)

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

Предложенные параллельные алгоритмы были написаны на языке Оккат-2 и тестированы на мультитранспьютерной системе фирмы ^МОЭ серии Т800. Теоретические исследования подтверждены результатами численных экспериментов.

Теоретические и прикладные результаты состоят в следующем:

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

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

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

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

Основное содержание диссертации отражено в следующих публикациях.

1. Федоров В.В., Чистякова Е.В. Об одной схеме диалога в иерархических системах проектирования. - Вопросы радиоэлектроники. Сер.Электронная вычислительная техника.Вып.6.: 1992, с.45-53.

2. Федоров В.В., Чистякова Е.В. Возможности иерархического диалога в системах проектирования.- Программно-аппаратные средства и мат. обеспечение вычислительных систем: Сборник /под ред. Л.Н. Королева, П.С. Краснощекова. - М.: Изд-во МГУ. 1994.,-с.128-135.

3. Ястребова Е.В. Моделирование распараллеливания вычислений в алгоритмах с иерархической структурой. - Вопросы радиоэлектроники. Сер.Электронная вычислительная техника.Вып.4.: 1993, С.3-14.

4. Ястребова Е.В..Иерархический подход к решению задачи о распараллеливании алгоритмов на многопроцессорных системах. - Вопросы радиоэлектроники. Сер.Электронная вычислительная техника. Вып.2.: 1994, С.24-34.

5. Ястребова Е.В., Применение мультитранспьютерных систем при решении задач идентификации нелинейных динамических

систем ' в реальном масштабе времени,- Вопросы радиоэлектроники. Сер. Электронная вычислительная техника. Вып.2.: 1994, С.35-42.

6. Ястребова Е.В.,Распараллеливание вычислений в одном методе решения задачи идентификации параметров нелинейных систем. - Изв. вузов. - Приборостроение, т. 37, N 9-10, 1994, стр. 37-45.

7. Ястребова Е.В..Решение задачи идентификации нелинейных динамических систем на основе функциональных рядов Вольтерра на мультитранспьютерных комплексах. -Труды Второй Межд. научн.-технич. конференции "Актуальные вопросы фундаментальных наук", В 7-ми т. / под. ред. И.Б. Федорова, К.С. Колесникова, А.О. Карпова. Том 6. Симпозиум "Информац. технологии автоматиз. и управл. в соврем, техносфере". -М.: Техносфера - информ, 1994, с. 57-60.

8. Ястребова Е.В., Исследование возможностей применимости мультитранспьютерных систем для решения задач идентификации нелинейных динамических систем в реальном времени., Первый межд. симпозиум "Интеллектуальные истемы", Россия, г. Махачкала, Дагестан, 22-27 июня, 1994. с. 144-146.

9. Ястребова Е.В., Исследование параллельных алгоритмов для метода локальных вариаций,- ЖВМ и МФ, т.35, N10, 1995. ( в печати)