Реферат по теме выпускной работы

Разработка и исследование подсистемы топологического анализа сетевых динамических систем как объектов моделирования

Введение

Актуальность темы

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

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

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

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

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

Целью работы является разработка подсистемы топологического анализа для сетевых динамических систем в виде отдельного независимого программного модуля РПМС. Основной ресурс, на который будет нацелена работа, – кластер ДонНТУ – MIMD-система с распределенной памятью.

Задачи работы

В рамках разработки подсистемы топологического анализа должны быть решены следующие задачи:

1. Разработаны структуры данных для описания топологий и характеристик СДО.
2. Разработаны алгоритмы для анализа первичной топологии, ее аппроксимации, разбиения исходного графа на дерево/антидерево.
3. Определены принципы взаимодействия с другими подсистемами и функционирования в качестве составной части РПМС.

Научная новизна работы:

1. Разработаны новые оптимизированные структуры данных для описания топологии и алгоритмы их обработки.
2. Разработаны специальные алгоритмы для реализации разбиения графа на дерево / антидерево и его аппроксимации.
3. Разработаны структуры данных и специальные методы для реализации обмена информацией с другими подсистемами РПМС.
4. Впервые реализован и исследован топологический анализатор для сетевых динамических систем как независимый программный модуль в составе РПМС.

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

1. Реализован топологический анализатор в составе РПМС для сетевых динамических систем с распределенными параметрами.
2. Разработана программная реализация алгоритмов для работы с предлагаемым новым подходом к кодированию топологии.
3. Разработаны алгоритмы для оптимального разбиения графа топологии на дерево/антидерево и его аппроксимации.
4. Разработаны структуры данных для кодирования графов топологии, алгоритмы и программные реализации используются в научно-исследовательской работе кафедры КИ факультета КНТ.

↑ Вверх

Анализ современных РПМС

Распределенная параллельная моделирующая среда (РПМС) – это совокупность аппаратных средств, системного и прикладного программного обеспечения (ПО), совместное функционирование которых направлено на выполнение моделирования работы СДС.

Характерной особенностью РПМС является способность выполнять вычисления отдельных частей объекта одновременно и независимо друг от друга, т.е. параллельно. Распараллеливание позволяет значительно ускорить процесс моделирования. Аппаратными средствами для этого выступают распределенные системы: компьютерные кластеры, Grid, параллельные структуры с использованием GPU.

На данный момент можно выделить следующие популярные РПМС:

1. Mathworks Simulink – дополнение к среде Mathworks MatLab для выполнения моделирования, симуляции и анализа СДС. Simulink имеет библиотеку с богатым набором элементов и возможностью их модификации и расширения. [1]
2. MSC Software EASY5 – среда для моделирования динамических физических систем, которая используется многими крупными компаниями для разработок в технической авиации, транспортных средствах, сельскохозяйственном оборудовании и других сложных системах, поведение которых описывается дифференциальными функциями первого порядка. [2]
3. Visual Solutions VisSim – визуальный язык программирования для встроенных микропроцессоров, предназначенный для моделирования и проектирования динамических систем, базирующийся на моделях. VisSim предлагает интуитивный интерфейс для создания блочных диаграмм и мощное моделирующее ядро. [3]
4. Modelica – объектно-ориентированный, декларативный моделирующий язык программирования для компонентно-ориентированного моделирования СДС. Для его использования разработано несколько коммерческих сред, наиболее известной из которых является Dassault Systemes Dymola. [4]

Среды Simulink, EASY5 и VisSim относятся к блочно-ориентированным языкам моделирования. Описание объекта моделирования осуществляется построением уравнений, определяющих его поведение, в виде визуальной схемы. Элементами схемы являются блоки, которые выполняют различные операции: сложение, умножение, дифференцирование и т.д. Положительным качеством блочного подхода является то, что специалисту предметной области не нужно иметь знаний программирования для использования этих пакетов. Но этот подход хорошо использовать только тогда, когда исходная задача имеет небольшое количество уравнений. Однако, в ряде случаев, например, при моделировании шахтной вентиляционной системы, возникают проблемы уже другого характера: необходимость в создании блочной схемы, количество элементов которой может достигать нескольких сотен тысяч.

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

Язык Modelica предусматривает иной подход – задача моделирования описывается, фактически, на специальном языке программирования. Его действительно можно использовать для решения СДО, подобных шахтным вентиляциям. Однако, есть другая отрицательная черта, которой были лишены предыдущие пакеты: пользователь должен сначала изучить этот язык, что в большинстве случаев является проблемой для людей, не связанных с компьютерной техникой.

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

Таким образом, несмотря на существование мощных пакетов моделирования, по-прежнему требуется создание компьютерной поддержки ввода топологии и всех связанных с СДО параметров. Эту задачу, а также проблему подготовки введенных данных для дальнейшего генерирования уравнений и их решения, должна решать ПТА. Целью всей разрабатываемой РПМС в целом является полная автоматизация процесса моделирования, начиная с описания модели и заканчивая визуализацией результатов.

↑ Вверх

Принцип декомпозиции РПМС на подсистемы

Факультет компьютерных наук и технологий Донецкого национального технического университета имеет практический опыт реализации параллельных моделей для таких вычислительных систем как MasPar, Intel Paragon, CRAY T3E, NEC SX8, что стало возможным благодаря длительному сотрудничеству со Штутгартским университетом Германии. Используя выработанные и развитые концепции, в основе которых лежит структура организации РПМС [5], была проведена декомпозиция всей РПМС на 10 подсистем, UML-диаграмма взаимодействия которых изображена на рис. 1.

Рисунок 1. Декомпозиция на подсистемы

Предполагается декомпозиция программного обеспечения (ПО) РПМС на следующие подсистемы:

1. Подсистема информационных технологий (ПИТ) – обеспечение взаимодействия пользователя с РПМС (ввод топологии СДС, задания параметров и т.д.) и возможности использования «внешних» вычислительных ресурсов, набор примеров и учебного материала.
2. Подсистема визуализации (ПВ) – предоставление возможности ПИТ выводить графические результаты работы пользователю (отображение топологии и графиков результатов моделирования).
3. Подсистема управления (ПУ) – управление последовательностью действий РПМС, реакция на результаты выполнения каждой подсистемы, обеспечение поддержки запросов подсистем относительно необходимой для работы информации.
4. База данных (БД) – сохранение данных каждого этапа моделирования (промежуточных результатов подсистем) и информации относительно пользователей, их запросов и задач.
5. Подсистема топологического анализа (ПТА) – ввод топологии СДС, ее кодирование, аппроксимация, получение вторичной топологии, преобразование топологических единиц информации в удобный для генерирования уравнений вид, вывод результатов анализа.
6. Подсистема генерирования уравнений (ПГУ) – преобразование исходных аппроксимированных уравнений (моделей) в векторно-матричную форму, генерирование дискретных симуляционных моделей для заданного численного метода решения.
7. Подсистема параллельных виртуальных симуляционных моделей (ППВСМ) – представление возможных иерархий виртуальных параллельных симуляционных моделей (ВПСМ) в зависимости от уровня распараллеливания, априорный анализ ВПСМ.
8. Подсистема решателя уравнений (ПРУ) – решение алгебраических, обыкновенных дифференциальных уравнений и уравнений частной производной с помощью параллельных численных методов, анализ сходимости, устойчивости и точности решения уравнений, оценка и оптимизация показателей эффективности, формирование результатов в удобной для визуализации форме.
9. Подсистема балансировки нагрузки (ПБН) – оценка нагрузки виртуальных процессов по уровням ВПСМ, статическое выравнивание нагрузки всех уровней, спецификация заявок на ресурсы РПМС, получение и анализ нагрузки между процессами и ресурсами целевой вычислительной системы, сравнительный анализ способов распараллеливания по критерию равномерной нагрузки ресурсов.
10. Подсистема обмена данными (ПОД) – взаимодействие и передача данных от основного ПО РПМС к локальному сервису, расположенного на кластере; спецификация структур данных и поддержка обмена информацией между подсистемами.

Только ПИТ и ПОД обеспечивают взаимодействие с внешней средой (пользователем и кластерами) и представляют собой «интерфейс» РПМС. При этом любое количество пользователей может обращаться к РПМС.

Данный подход позволит ускорить разработку РПМС и предоставить «гибкость» системе: возможность подстраиваться для работы с различными видами СДС путем переключения всего нескольких подсистем.

На диаграмме рис. 1 также обращено внимание на то, что ПО РПМС требует для всех вычислительных операций наличие аппаратных средств, которыми может выступать кластер ДонНТУ или кластер Штутгартского университета. Для работы с первым используется специальный локальный сервис, который будет регулировать нагрузку и процесс обмена данными. За эту связь отвечает ПОД. Во втором случае отсутствует возможность запуска своих сервисов на кластере, поэтому взаимодействие обеспечивает ПИТ.

ПТА выполняет следующие функции:

1. Ввод исходных данных, описывающих топологию СДО и физические характеристики его компонент:
   • Получение топологии СДО в виде подготовленной структуры данных.
   • Чтение топологии из специализированного файла.
2. Процесс топологического анализа:
   • Разбиение первичной топологии на дерево и антидерево.
   • Построение матриц инцидентности A и независимых контуров S.
   • Аппроксимация ветвей графа и формирование вторичной топологии.
   • Топологический анализ по уровням распараллеливания.
   • Преобразование топологических единиц информации в удобный для генерирования уравнений вид.
   • Формирование итоговой информации.
3. Взаимодействие с другими подсистемами (представлено на UML-диаграмме рис. 2):
   • Получение исходных данных из БД посредством ПОД.
   • Выполнение функций с заданными параметрами, которые определяет ПУ на различных этапах работы РПМС.
   • Передача данных в ПГУ.
   • Сохранение результатов работы в БД посредством ПОД.

Рисунок 2. Диаграмма взаимодействия ПТА с другими подсистемами

Анимация Silverlight: объем - 56,1 КБ, размер - 477х222, длительность - 15 с, количество ключевых кадров - 67, многоязычная, запуск проигрывания по нажатию пользователя.

↑ Вверх

Анализ существующих работ

Поиск работ, рассматривающих вопросы разработки топологического анализатора СДО в рамках РПМС, осуществляется на нескольких уровнях.

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

• Поисковые системы Google, Bing, Yandex, Rambler, Meta и Yahoo! с использованием региональной фильтрации результатов;
• Сообщество Макса Планка (Max-Planck-Gesellschaft, Мюнхен, Германия);
• Библиография компьютерных наук (The Computer Science Bibliography);
• Сеть знаний (Web of Knowledge);
• Инженерная информация (Engineering Information);
• Система ПроКвест (ProQuest).

Запрос работ по теме топологического анализа дал достаточно большое количество результатов, но более подробное рассмотрение показало, что эти работы не касаются СДС или непосредственной разработки ПТА. По конкретной теме результатов не было найдено.

Поиск на национальном уровне дал лишь некоторые результаты касательно использования таких средств, как Simulink, UML и т.д. Данная тематика не относится непосредственно к разработке топологического анализатора.

Локальный поиск по работам ДонНТУ выдал достаточное количество работ и опубликованных статей по разработке подсистемы топологического анализа СДС:

• В работе [6] предложены алгоритмы работы топологического анализатора для формирования и решения уравнений СДО с сосредоточенными параметрами для MIMD-систем, особенностью которых пошаговое преобразование таблицы графа.
• В работе [7] разработаны алгоритмы обработки графов топологии и реализован параллельный топологический анализатор СДО с сосредоточенными параметрами.
• Подробно рассмотрен топологический анализатор параллельной модели СДО в работе [8].
• В работе [9] и [10] определены основные функции топологического анализатора, его модификация для СДО с распределенными параметрами, алгоритмы построения матрицы инцидентности и возможные методы аппроксимации ветвей графа.

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

При вводе данных СДО нужен способ их представления в такой форме, которая бы объединяла формализацию связей, задания параметров и вербальное описание важных для данной предметной области компонент. Предложенный в работе [9] вид таблицы (табл. 1) подходит для решения данной проблемы, однако с учетом алгоритмов ПГУ возможна некоторая оптимизация представленных в ней данных.

Таблица 1 – Таблица описания топологии СДО

Начальный узел	Конечный узел	Номер ветви	Физические параметры ветви	Активный элемент	Комментарий

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

Таблица 2 – Модифицированная таблица инцидентности

	Q1		Q2		...		Qm
	Q11	Q1M1	Q21	Q2M2	...	...	Qm1	QmMm
Ui	...	...	...	...	...	...	...	...

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

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

↑ Вверх

Выводы

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

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2011 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

↑ Вверх

Литература

1. Simulation and Model-Based Design [Electronic resource] / Интернет-ресурс. – Режим доступа : www/ URL: http://www.mathworks.com/products/simulink/. – Загл. с экрана.
2. Easy5 for Controls and Systems Simulation [Electronic resource] / Интернет-ресурс. – Режим доступа : www/ URL: http://www.mscsoftware.com/Products/CAE-Tools/Easy5.aspx. – Загл. с экрана.
3. VisSim [Electronic resource] / Интернет-ресурс. – Режим доступа : www/ URL: http://www.vissim.com/. – Загл. с экрана.
4. Modelica and Modelica Association [Electronic resource] / Интернет-ресурс. – Режим доступа : www/ URL: http://www.modelica.org/. – Загл. с экрана.
5. Святний В. А. Стан розробок та перспектива інтеграції паралельних моделюючих середовищ з Grid-технологіями [Текст] / В. А. Святний, О. В. Молдованова, А. М. Чут // Наукові праці Донецького національного технічного університету. Серія “Інформатика, кібернетика та обчислювальна техніка” (ІКОТ-2008). Випуск 9 (132). – Донецьк : ДонНТУ, 2008. – С. 103-110.
6. Dissertation (Master: Alexey Smagin, Group: VT-97-v) [Электронный ресурс] / Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2002/fvti/smagin/diss/index.html. – Загл. с экрана.
7. Давлетханов ДВ Моделирование сетевых динамических объектов Реферат [Электронный ресурс] / Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2006/fvti/davlethanov/diss/diss.htm. – Загл. с экрана.
8. Топологический анализатор [Электронный ресурс] / Интернет-ресурс. – Режим доступа : www/ URL: http://www.students.cs.donntu.ru/vt95/vt95g/pererva/topan.html. – Загл. с экрана.
9. Молдованова О. В. Способи організації паралельних обчислень в задачах математичного моделювання шахтних вентиляційних мереж [Текст] : дис. … канд. наук : 01.05.02 / Молдованова Ольга Володимирівна. – К., 2008. – 152 с.
10. Чайка МА Автореферат [Электронный ресурс] / Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2007/fvti/chayka/diss/index.htm. – Загл. с экрана.

↑ Вверх