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

• Автор: Ней Мин Тун
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 143 с. : ил.

ОГЛАВЛЕНИЕ
Введение .

Глава 1. Графовые модели в задачах системного анализа

1.1. Классификации систем.

1.1.1. Классификация методов формализованного представления систем .

1.1.2. Понятие о методике системного анализа.

1.1.3. Графические методы

1.2. Применение элементов теории графов в системном анализе.

1.2.1. Основные понятия

1.2.2. Некоторые специальные графы.

1.2.3. Взвешенные 1рафы

1.2.4. Изоморфизм
1.2.5. Инварианты
1.2.6. Связность графа.
1.3. Анализ графовых моделей
1.3.1. Задача поиска всех кратчайших путей.
1.3.2. Задача нахождения кратчайшего связывающего дерева.
1.3.3. Задача оптимального разделения графов.
1.4. Перспективы перехода автоматизированных систем на параллельные платформы.
1.5. Выводы.
Глава 2. Анализ алгоритмов построения кратчайших связывающих
деревьев.
2.1. Классификация алгоритмов.
2.1.1. Волновые алгоритмы трассировки
2.1.2. Ортогональные алгоритмы трассировки.
2.1.3. Эвристические алгоритмы трассировки.
2.1.4. Канальные трассировщики.
2.1.5. Гибкие трассировщики
2.2. Бессеточные трассировщики
2.2.1. Топологические методы.
2.2.2. Программа ОшскЯоЩе
2.2.3. Автотрассировщик
2.2.4. Автоматический трассировщик .
2.2.5. .
2.3. Волновой алгоритм
2.3.1. Основные положения.
2.3.2. Минимизация длины соединений.
2.3.3. Трассировка многослойных соединении
2.4. Распределение нагрузки при операциях с матрицами.
2.4.1. Ленточное разбиение матрицы
2.4.2. Блочное разбиение матрицы
2.4.3. Оценка возможности параллельной реализации алгоритмов
построения кратчайших деревьев и путей
2.5. Подход к распараллеливанию волнового алгоритма.
2.6. Выводы.
Глава 3. Метод распределения нагрузки для алгоритма построения
кратчайших связывающих деревьев на кластерной ВВС
3.1. Кластерные ВВС как ядро автоматизированных систем
3.2. Задача построения топологии локальной сети.
3.3. Особенности программного обеспечения для кластерных
вычислительных систем.
3.4. Параллельный алгоритм построения связывающих деревьев
3.5. Особенности программной реализации метода
3.5.1. Интерфейс передачи сообщений.
3.5.2. Язык программирования трС
3.6. Выводы.
Глава 4. Исследование эффективности параллельного алгоритма.
4.1. Исследование масштабируемости метода.
4.1.1. Решение тестовой задачи 1.
4.1.2. Решение тестовой задачи Ха2
4.1.3. Решение тестовой задачи 3.
4.2. Исследование функциональности модели.
4.2.1. Решение тестовой задачи 1
4.2.2. Решение тестовой задачи 2.
4.2.3. Решение тестовой задачи 3.
4.3. Выводы.
Заключение.
Литература


Практическая значимость разработанного метода повышения эффективности кластерных вычислительных систем подтверждается его реализацией в виде программного модуля автоматического построения кратчайших связывающих деревьев. Найденные решения позволяют расширить класс решаемых задач системного анализа за счет увеличения размерности графовых моделей. Способ распределения нагрузки вычислительных узлов кластеров, основанный на разбиении задачи на связанные фрагменты, может быть применен и для других классов задач системного анализа. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы». Анализ переносимости алгоритмов построения кратчайших связывающих деревьев на кластерные вычислительные системы. Метод повышения эффективности кластерных вычислительных систем при решении задачи построения кратчайших связывающих деревьев. Параллельный алгоритм построения кратчайших связывающих деревьев из локально-оптимальных фрагментов. Параллельная программа автоматического построения кратчайших связывающих деревьев. Анализ результатов исследований эффективности кластерных вычислителей при использовании предложенного алгоритма. Апробация работы. Москва, г. Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ, г. Москва, г. Москва, г. Научная сессия «МИФИ-» г. Москва, г. Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Микроэлектроника и информатика-», г. Москва, г. Всероссийская межвузовская научно-практическая конференция молодых ученых, специалистов, преподавателей, аспирантов и студентов «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем», г. Москва, г. Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ. Структура и объём диссертационной работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и приложения. Глава 1. Системы разделают на классы по различным признакам, и в зависимости от решаемой задачи можно выбирать разные принципы классификации. Различные виды классификаций систем всегда относительны. Так, в стохастической системе можно найти элементы детерминированности, и, напротив, детерминированную систему можно считать частным случаем стохастической (при вероятности равной единице). Аналогично, если принять во внимание диалектику субъективного и объективного в системе, то станет понятной относительность разделения систем на абстрактные и объективно существующие: это могут быть стадии развития одной и той же системы. Однако относительность классификации не должна препятствовать исследователям в выборе методов анализа. При этом система, в принципе, может быть одновременно охарактеризована несколькими признаками, т. Открытые и закрытые системы. Основные отличительные черты открытых систем - способность обмениваться со средой массой, энергией и информацией. В отличие от них закрытые или замкнутые системы предполагаются полностью лишенными этой способности, т. Целенаправленные, целеустремленные системы. В этом классе, в свою очередь, можно выделить системы, в которых цели задаются извне (обычно это имеет место в закрытых системах), и системы, в которых цели формируются внутри системы [3]. Математика непрерывно развивается. Возникают новые области и математические теории, отмирают или вливаются в другие устаревающие разделы. Несмотря на то, что в практике анализа широко используют теорию множеств, математическую логику, математическую лингвистику и другие направления современной математики, до сих пор еще не все ученые-математики склонны включать в число математических некоторые из этих направлений. Благодаря работам французских ученых теорию множеств и математическую логику стали признавать разделами математики, а математическую лингвистику и семиотику часто еще не относят к ней [4].