Анализ и разработка методов и алгоритмов оптимизации графовых моделей на кластерных вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Ней Мин Тун

• Ней Мин Тун
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Ней Мин Тун

Введение

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

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

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

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

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

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

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

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

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

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. Автотрассировщик ProRoute.

2.2.4. Автоматический трассировщик Shape-Based Router.

2.2.5. FreeStyle Router.

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. Выводы.

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

Актуальность проблемы. В последние годы многопроцессорные вычислительные системы стали доступны широкому кругу исследователей именно благодаря развитию кластерных технологий. Кластерные системы занимают более 75% в списке ТОР500 высокопроизводительных вычислительных систем. Ключевыми особенностями кластеров можно считать отсутствие общей памяти и межузловое взаимодействие через сеть. Эффективность параллельных программ, разработанных для кластеров, во многом зависит от того, как будет распределена нагрузка между узлами вычислительной системы. Одной из наиболее актуальных задач в этой области является разработка эффективных, масштабируемых сбалансированных параллельных алгоритмов для широкого круга приложений.

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

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

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

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

Кластеры, построенные из унифицированных узлов, а сегодня это компьютеры с многоядерными процессорами, и использующие стандартное программное обеспечение, наиболее доступны широкому кругу пользователей и могут вполне составить конкуренцию промышленным системам. Архитектурно, кластеры такого типа можно отнести к СоРС, CoWS или Беовульф системам. Они обеспечивают высокую производительность для распределенных приложений, однако слабость коммуникаций, основанных на Gigabit Ethernet или даже Myrinet, не позволяет реализовывать параллельные процессы, требующие интенсивных обменов между узлами. Для повышения производительности таких параллельных систем необходимо разрабатывать алгоритмы, обеспечивающие:

• минимизацию межпроцессорных обменов;

• балансировку нагрузки узлов.

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

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

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

1. Анализ особенностей аппаратных платформ, применяемых в автоматизированных системах.

2. Анализ переносимости алгоритмов обработки графов на параллельную платформу.

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

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

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

6. Экспериментальное исследование эффективности предложенного алгоритма.

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

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

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

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

Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы». На защиту выносятся следующие положения:

1. Анализ переносимости алгоритмов построения кратчайших связывающих деревьев на кластерные вычислительные системы.

2. Метод повышения эффективности кластерных вычислительных систем при решении задачи построения кратчайших связывающих деревьев.

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

4. Параллельная программа автоматического построения кратчайших связывающих деревьев.

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

1. Двенадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2005», г. Москва, 2005г.

2. Международная школа-конференция по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ, г. Москва, 2005г.

3. Тринадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2006», г. Москва, 2006г.

4. Научная сессия «МИФИ-2007» г. Москва, 2007г.

5. Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов. «Микроэлектроника и информатика-2007», г. Москва, 2007г.

6. Всероссийская межвузовская научно-практическая конференция молодых ученых, специалистов, преподавателей, аспирантов и студентов «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем», г. Москва, 2007г.

Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Ней Мин Тун

4.3. Выводы

Проведенные испытания параллельной программы позволяют сделать следующие выводы:

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

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

103

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

4. Разработанный параллельный алгоритм позволяет решать задачи оптимизации графовых моделей большой размерности (в тестовых примерах это 3,6*105 ), что позволяет повышать точность решения задач системного анализа в различных приложениях.

Заключение

В результате работы получены следующие основные выводы:

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

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

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

4. Создан программный модуль, реализующий предложенный алгоритм на кластерной системе и получено свидетельство на программу. Программный модуль реализован в среде mpC Workshop.

5. Исследования, проведенные на вычислительном кластере 25*(PIV-2400), подтвердили практическую эффективность предложенного алгоритма при его реализации на кластерных системах использующих коммутацию узлов с помощью Gigabit Ethernet.

Список литературы диссертационного исследования кандидат технических наук Ней Мин Тун, 2008 год

1. Волкова В.Н., Денисов A.A. Теория систем. Классификации систем. / -М.: Высш. шк., 2006.

2. Берталанфи JT. Фон. История и статус общей теории систем. Системные исследования. / М.: Наука, 1973.

3. Черняк Ю.И. Анализ и синтез систем в экономике. / М.: Экономика, 1970.

4. Волкова В.Н. и др., Методы формализованного представления систем. / -М.: ИПКИР, 1974.

5. Кухтенко А.И. Об аксиоматическом построении математической теории систем. Кибернетика и вычислительная техника. / Киев: Наукова думка, 1976.

6. Черняк Ю.И. Системный анализ в управлении экономикой / М: Экономика, 1975.

7. Алексеев В.Е., Таланов В.А., Графы и алгоритмы. Электронный ресурс. / Режим доступа: http://www.intuit.ru/department/algorithms/gaa/

8. Вагнер Г. Основы исследования операций. / М.: Мир, 1972

9. Бурков В.Н., Горгидзе И.А. Ловецкий С.Е. Прикладные задачи теории графов. / Тбилиси: Мецниереба, 1974.

10. Бурков В.Н., Багатурова О.С., Иванова С.И. Оптимизация обменных производ- ственных схем в условиях нестабильной экономики. / М.: ИПУ РАН, 1996.

11. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. / М.: Советское радио, 1967.

12. Новиков Д.А. Сетевые структуры и организационные системы. / М.: ИПУ РАН, 2003.

13. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. / М.: Энергоатомиздат, 1988.

14. Нефедов В.Н., Осипова В.А. Курс дискретной математики. / М.: Издательство МАИ, 1992.

15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. / -М.: МЦНТО, 1999.

16. Schloegel К., Karypis G., Kumar V. Graph Partitioning for High Performance Scientific Simulations. / 2000.

17. Курилов JI.C. Прогностическая стратегия балансировки загрузки для невыделенных кластерных систем. Электронный ресурс. / Режим доступа: http://zigzag.lvk.cs.msu.su/xaraYa/files/mco2003/kurilov.pdf

18. Селютин В.А. Машинное конструирование электронных устройств. Общая характеристика методов трассировки и их классификация / М.: Сов. радио, 1977.

19. Морзов К.К., Одиноков В.Г, Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры / М.: Радио и связь, 1983.

20. Мустафаев Г.А. Системы проектирования топологии интегральных схем и печатных плат. Электронный ресурс. / — Режим доступа: http://ktims.kbsu.ru/ebook/di/met kaf/must/must 001/must 001.htm

21. Деньдобренко Б.Н., Малика A.C. Автоматизация Конструирования РЭА, / М.: Высш.школа, 1980.

22. Шутова O.A., Сравнение Методов Трассировки. Электронный ресурс. / Режим доступа: http://nit.miem.edu.ru/2006/sb/sectionl/secl. 18/18.htm

23. Лузин С., Полубасов О., Топологическая трассировка: реальность или миф? Электронный ресурс. / Режим доступа: http://www.chip-news.ru/archive/chipnews/200205/9.html

24. Лопаткин A.B. P-CAD 2001 для начинающих. Электронный ресурс. / Режим доступа: http://www.eltm.ru/index.sema?a=pages&id-386

25. Разевиг В. Д. Система проектирования печатных плат ACCEL EDA 15 (P-CAD 2000). / М.:Солон-Р. - 2000.

26. Поляков Ю. В. Новый бессеточный автотрассировщик для P-CAD 2000. / EDA Express. 2000. Октябрь. №2.

27. Сухарев А.В. FreeStyleRoute Трассировка печатных плат. / СПб.: 1999.

28. Гергель В.П. Введение в методы параллельного программирования. Параллельные методы матричного умножения. / Н.Новгород. 2005.

29. Налетова М.В. Кластер информационной безопасности. Электронный ресурс. / Режим доступа: http://www.npo-rtc.ru/product/cluster/

30. Кластеры. Электронный ресурс. / — Режим доступа: http://si.nnz.ru/decide/servers/klasters/

31. Ней Мин Тун. Системный анализ и информационно-управляющие системы. Параллельная трассировка на многопроцессорных вычислителях. /- М.: МИЭТ, 2008

32. MPI: A Message-Passing Interface Standard. Электронный ресурс. / -Режим доступа: http://parallel.ru/docs/Parallel/mpil. 1/mpi-report.html

33. Антонов А.С. Параллельное программирование с использованием технологии MPI. Передача/прием сообщений между отдельными процессами. / М.: Изд-во МГУ, 2004.

34. Ластовецкий A.JI. Технологии параллельного программирования шрС. Электронный ресурс. / Режим доступа: http://www.parallel.ru/tech/mpc/mpC-rus.html