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

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

Сетевые объекты распространены в различных отраслях техники как класс объектов исследования, проектирования и управления. Реальные сети, будь то шахтные вентиляционные сети или же подземные коммунальные коммуникации, имеют большое количество элементов, сильное взаимодействие управляющих элементов, нелинейность и распределение параметров. Большой размер сетей (узлов более 100), вызывает значительные трудности и возможные ошибки во время их формального описания, решения задач расчета, проектирования систем управления, оптимизации динамических процессов. Моделирование сетевых объектов является мощным фактором получения современных технических и технологических решений и осуществляется в рамках проблемно ориентированных параллельных моделирующих сред (ПОПМС). Будучи новой формой системной организации работы параллельных вычислительных ресурсов, ПОПМС являются актуальным объектом исследований и разработок в современном моделировании [3]. Уровень автоматизации формирования моделей определяет качество моделирующей среды и зависит от функциональных возможностей средств, объединяемых в топологический анализатор (ТА) сложных динамических объектов моделирования. Последовательные алгоритмы получения условных топологических матриц предложены в [1, 2] при построении аналоговых, аналого-цифровых и цифровых моделей сетевых объектов. В статье предлагается таблично ориентированный подход к полнофункциональной разработке и реализации топологического анализатора параллельной модели сетевого объекта. Создание эффективного ТА позволит ускорить решение проблемы построения параллельных моделирующих средств для сетевых объектов с сосредоточенными и распределенными параметрами. Средства моделирования интенсивно используются в реальных проектах для проверки правильности проектных решений и выступают тем самым как важнейший фактор, гарантирующий качество проектирования, сокращение сроков внедрения проектов и освоения управляемых динамических систем обслуживающим персоналом. Играя столь важную роль в техническом и технологическом прогрессе, моделирование как метод исследования выдвигает ряд требований к вычислительным системам и их программному обеспечению как средствам реализации моделей.

Цель и задачи исследования:

Целью данной работы является разработка, отладка и экспериментальные исследования объекта, ориентированного для проверки новых методов моделирования динамических объектов с сосредоточенными параметрами, балансировки загрузки процессов. В работе решаются следующие задачи: Рассмотрение современных методов моделирования динамических систем. Разработка алгоритмов топологического анализатора, генератора и решателя уравнений. Параллельное моделирование СО с применением библиотеки MPI. В процессе создания модели СО предусмотрено использование теории графов, численных методов решения дифференциальных уравнений, методы параллельного программирования, экспериментальная проверка программ последовательных и параллельных алгоритмов моделирования на тестовых объектах.

Рассмотрение имеющихся решений:

Было найдено несколько программ для построения графов, в том числе и ориентированных. Наиболее интересная - это библиотека для работы с графами разработанная Алексеем Черобаевым (http://www.caravan.ru/~alexch/AGraph/algorithms.htm). Библиотека представляет широкие возможности по работе с графами различной структуры и сложности, однако невозможности использовать эту библиотеку заключается в несовпадении представления графа, так как для топологического анализатора необходимы 2 матрицы определенной структуры (приведены ниже) рис 1. Cтруктура матриц описывающих объект и поэтому принято решение разработать специализированный генератор для получения необходимых результатов. Однако сушествуют разработки не менее интересные с точки зрения методик решения поставленной задачи. Так на данный момент существует довольно много последовательных и параллельных алгоритмов (геометрические, спектральные, многоуровневые) разбиения графов, которые были реализованы в конкретных программных продуктах. Самыми распространенными программными продуктами из этой серии являются METIS и ParMETIS, которые были разработаны в университете Миннесоты в 1998-2003 годах. В этих программных продуктах реализован класс так называемых многоуровневых алгоритмов, которые показали довольно хорошие результаты по скорости работы и качеству создаваемых разделов. Рассмотрим их подробнее. Многоуровневый алгоритм разбиения состоит из трех этапов: Минимизация графа до нескольких сотен вершин (coarsening-стадия); Разбиение графа на заданной количество частей; Развертывание разбитого графа до первоначального размера (uncoarsening - стадия) с одновременной минимизацией связей между разделами.   Минимизация графа. Во время минимизации графа последовательно получают из графа Gi=(Vi-1,Ei-1) меньший производный граф Gi=(Vi,Ei), причем |Vi|<|Vi-1|, где i – уровень минимизации, а |Vi| и |Vi-1| - множество вершин графа на одном из этапов минимизации. Принцип минимизации графа заключается в следующему: набор инцидентных вершин объединяется в одну при следующем уровне минимизации. Причем вес минимизированной вершины равняется сумме весов вершин, которые объединились в минимизированную. Связность минимизированной вершины тоже равняется сумме связностей первоначальных вершин. Минимизация графа завершается, когда количество вершин |Vi| в производном графе достигает значения, меньше 100.   Разбиение графа. Для разбиения минимизированного графа разработчиками предусмотрено четыре различных алгоритма разбиения на части: спектрального деления пополам (spectral bisection), деления пополам Кернигана-Лина (Kernighan-Lin bisection), роста регионов в ширину (breadth-first region growing) и "жадного" роста регионов (greedy region growing).   Развертывание графа. В процессе данного этапа выполняется последовательное развертывание вершин в разделах до первоначальных размеров. При этом на каждом этапе увеличения используется один из алгоритмов локального улучшения, которые базируются на алгоритме Кернигана-Лина (Kernighan-Lin Refinement). Пары вершин, которые имеют больше внешних связей с противоположным разделом, чем внутренних (внутри раздела), обмениваются местами. На этом улучшение на i-м уровне заканчивается, и выполняется переход на следующий i-1 уровень, и т.д. Найдена программа Dot которая , выполняет построение графа по заданному шаблону. Dot - свободно распространяемая программа компании Graphviz, которая служит для построения графов, используя информацию про топологию графа [4]. В качестве выходных данных программы могут быть разные файлы, как рисунки в форматах *.jpg, *.bmp, *.gif, *.png, так и в файлах формата PostScript и др. Выходные рисунки исходного графа и полученного из него графа алгоритма приведены ниже. рис 2. Исходный граф. рис 3. Полученный граф

Результаты на данный момент:

На данный момент решена задача построения генератора объектов и топологического анализатора. Генератор объекта должен создавать граф, который и является сетевым динамическим объектом, результатом его работы являются матрицы формального описания графа - это матрица инцидентности и матрица смежности. Второй ступенью разработки являлась создание топологического анализатора, который по результатам генератора должен создать представление объекта удобное для его анализа и численного решения. Ниже представлена иллюстрация работы алгоритма генератора объекта. рис 5. Работы генератора объектов Краткий алгоритм действий по построению ориентированного графа. Выбор количества узлов графа. Случайное распределение количества подсоединяемых ветвей к каждой вершине. Построение цепи охватывающей все узлы. Переход на вершину, и просмотр имеется ли у нее свободный "порт"для подсоединения очередного ребра, если да то подсоединяем эту вершину к другой со свободным портом. Остались свободные "порты"? ДА то переход на 4. НЕТ, переход на 6. Выход. Для последующей работы необходимо разбить граф на дерево и антидерево. Пусть ветви относящиеся к дереву будут входитьт в вектор X, а верви антидерева в Y. И после этого необходимо получить матрицы A и S в таком виде A = (Ax Ay), S = (Sx Sy). Для этой цели разработан топологический анализатор. Топологический анализатор – это составная часть проблемно ориентированной параллельной моделирующей среды, которая должна выполнять следующие функции : дружественное к пользователю графическое представление топологии исследуемого сетевого объекта с возможностью выделения фрагментов и оперативного изменения состава и связей между элементами фрагментов; кодирование топологии сетевого объекта в форме, сочетающей формализацию связей, задание параметров и вербальное описание существенных для данной предметной области компонент; автоматизированное построение дерева и антидерева графа сетевого объекта с возможностью выбора вариантов, предпочтительных для разработчика параллельной модели; автоматическая перекодировка топологии в соответствии с выбранным вариантом дерева и антидерева; автоматическое генерирование топологических матриц инциденций А и независимых контуров, соответствующих выбранному дереву и антидереву графа сети; диалоговая поддержка всех функций, исчерпывающая визуализация и документирование результатов топологического анализа, интеграция со всеми компонентами моделирующей среды. рис 6. Структура ТА. Сетевой объект рассматривается как граф G(U, Q) с n = |U| узлами и m = |Q| ветвями и кодируется следующей таблицей TABUR Предлагаются таблично ориентированные алгоритмы построения дерева (антидерева), матриц инциденций А и контуров S. Они ориентированы на возможное распараллеливание при реализации в ПОПМС [3] и являются модификациями алгоритмов, описанных в [1, 2]. Алгоритм построения дерева включает следующие операции : ввод и инициализация исходных данных; определение части дерева относительно первой строки. Из таблицы TABUR выполняется анализ строк (строка – элемент данных, хранящий в себе начальный узел, конечный узел и номер ветви), у которых совпадают начальные узлы и не совпадают конечные. Эти строки заносятся в таблицу дерева BAUMTAB; основной этап формирования дерева. Выбирается первая строка из BAUMTAB. Затем в BAUMTAB включаются те строки, у которых начальный узел совпадает с конечным узлом строк, уже занесенных в BAUMTAB и не совпадает конечный узел с начальным соответственно; анализ конца построения дерева. Если число строк BAUMTAB станет равным n-1, то на этом процесс построения закончен, иначе повторяется предыдущий пункт относительно следующей строки BAUMTAB. Для поиска таблицы антидерева ANTIBAUMTAB необходимо из таблицы TABUR выбрать те строки, которые не входят в BAUMTAB. Имеющиеся такие результаты: Файлы с матрицами A, S, Ax, Ay, Sx, Sy, A_arch, Ax_arch, Ay_arch, Sx_arch, Sy_arch. Файлы в именах, которых присутствует - "_arch" являются оптимизированными копиями больших матриц, потому как для большего объекта с параметрами 1000 узлов, 8000 ребер, размер файлов примерно такой: А-15Мб, Ах-1,9Мб, S-109Mb, Sx - 19Mb, Sy - 90Mb, а упакованные они составляют: A_arch - 650Kb, Sx_arch - 750Kb, Sy_arch - 1.4Kb соответственно. Общие время работы ГО и ТА составляет около 3 минут (большой СО), для небольших объектов время генерации не превышает 1 секунды.

Направления продолжения работы:

Направления для продолжения работы это разработка генератора уравнений, решателя уравнений и непосредственное параллельное моделирование сетевого объекта. Решатель уравнений должен представлять собой программу, реализующую циклический алгоритм численного решения матрично-векторных систем уравнений. Воспользуемся численным методом Адамса-Бошфорта, который реализован в существующих последовательных языках моделирования. Сделаем попытку унифицировать процессы решателя уравнений в дополнение к тому, что они структурированы матрично-векторной формой записи. По-видимому, есть смысл этот этап делать в таком порядке: схема решателя анализ подходов к распараллеливанию программы РУ расcмотрение SPMD - принципа организация связи между процессами

Заключение:

В этой работе было выполнено исследование способов построения динамических объектов, которые моделируються на параллельных системах. Также на основе предыдущего опыта моделирования СДО, изучения языков моделирования, рассмотрения языков параллельного моделирования и основных архитектур параллельных ЭВМ было создана объектно-ориентированная программа создания СДО со связанными параметрами. Во время написания данного автореферата работа ещё не завершена и поэтому многое пока не сделано. Срок написания работы - январь 2007 года, после этой даты можно будет получить материалы относящиеся к работе у руководителя или у автора.

Список литературы:

Святний В.А. Проблемы параллельного моделирования сложных динамических систем. Випуск 29:-Донецк, ДонНТУ, 2001. - С.229 - 234. Цой С., Цхай С.М. Прикладная теория графов. - Алма-Ата: Наука, 1971, 500 с. Svjatnyj V.A., Rasinkov V.V., Braeunl T., Reuter A., Zeitz M. Problemorientierte massiv parallele Simulationsumgebung fuer dynamische Netzobjekte. Simulationstechnik, 10. Symposium, Dresden, 1996, S.515-518. Gansner E., Koutsofious E., North S. "Drawing graphs with dot" 2002. [1-40]

Наверх