На правах рукописи

НЕЙ МИН ТУН

АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ

ОПТИМИЗАЦИИ ГРАФОВЫХ МОДЕЛЕЙ НА

КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Специальность 05.13.01.

Системный анализ, управление и обработка информации

(в приборостроении)

АВТОРЕФЕРАТ

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

МОСКВА

2008

Работа выполнена на кафедре Вычислительной техники при Московском государственном институте электронной техники (техническом университете).

Научный - кандидат технических наук, профессор руководитель Лупин Сергей Андреевич.

Официальные - доктор технических наук, оппоненты Щагин А.В.

кандидат технических наук, Шабанов Б.М.

Ведущее - Московский авиационный институт предприятие

Защита диссертации состоится "" _ года на заседании диссертационного совета Д212.134.02 при Московском государственном институте электронной техники (техническом университете).

124498, Москва, г. Зеленоград, проезд 4806, д.5 МИЭТ.

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

Автореферат разослан "_" _ 2008 года.

Ученый секретарь диссертационного совета д.т.н. Гуреев А.В.

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

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

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

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

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

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

Классические подходы к распределению нагрузки предполагают разделение кода или данных между узлами системы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту.

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов "Микроэлектроника и информатика - 2005", "Микроэлектроника и информатика - 2006", "Микроэлектроника и информатика - 2007", Международной школы-конференции "Информационно-телекоммуникационные системы - 2005" Всероссийской межвузовской научно-практической конференции "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007", научной сессии МИФИ "Компьютерные системы и технологии" Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.

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

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

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

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

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

Граф G задан, если определено:

где V = {vi },1 i n множество вершин, а R = {r j }1 j m множество дуг графа Граф может быть представлен при помощи матрицы смежности элементы которой соответствуют дугам графа Такой способ позволяет использовать различные матричные алгоритмы обработки данных.

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

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

Кратчайшим остовным графом неориентированного графа G называют подграф T, который является деревом минимального веса и содержит все вершины из G. На практике, эта модель широко используется при проектировании телекоммуникаций. Кроме того, обе задачи лежат в основе этапа топологического проектирования в САПР.

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

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

Большинство известных графовых алгоритмов реализованы в различных САПР электронной аппаратуры. Так задача построения кратчайших деревьев решается на этапе трассировки проводников.

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

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

• волновые алгоритмы трассировки, основанные на идее Lee, • ортогональные (лучевые) алгоритмы;

• эвристические алгоритмы;

• канальные трассировщики;

• гибкие (топологические) трассировщики.

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

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

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

Например, в задаче умножения матриц:

можно использовать ленточное или блочное разделение исходных данных. Если в системе имеется p процессоров, то общее количество данных, которые должны быть доступны в узле составляет n2/p+n2. Такое разделение позволяет получить практически р-кратное ускорение.

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

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

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

Рисунок 1. Способ распределения вычислений.

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

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

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

1. Определение множества вершин дерева.

2. Разбиваем матрицу на NM-подматриц и находим центры тяжести вершин фрагментов.

3. Построение скелета дерева.

4. Нахождение дополнительных вершин.

5. Построение локально-оптимальных фрагментов.

6. Построение кратчайшего дерева.

Разработанный параллельный алгоритм состоит из трех этапов:

• макро-трассировка;

• микро-трассировка;

• и синхронизация.

На этапе макро-трассировки формируются исходные данные для всех узлов системы. Каждый процессор определяет координаты центра тяжести вершин дерева, расположенных в его сегменте, и передает их на хост C = {ci}, который и строит предварительный центры тяжести отдельных фрагментов дерева. Для проведения макро-трассировки используется модифицированный однослойный волновой алгоритм.

Построенный скелет дерева позволяет определить граничные точки для каждого сегмента рабочего поля C = {ci. Это необходимо для соединения локальных фрагментов дерева в единое целое. Таким образом, исходными данными для микро-трассировки будут координаты вершин (контактов), расположенных внутри фрагмента, и координаты точек пересечения трассы дерева с гранями фрагмента. Очевидно, что этот этап алгоритма может быть полностью реализован и на одном узле для минимизации пересылок данных.

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

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

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

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

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

Для исследования масштабируемости алгоритма, т.е.

способности адаптироваться к размеру вычислительного пространства, необходимо провести решение тестовой задачи на разном количестве узлов. Поскольку на результат решения влияет вариант разбиения, исследования должны быть проведены при фиксированном разделении рабочего поля. В таблице 2 приведены данные для разбиения 4*6. Проведенное испытание показало, что алгоритм устойчиво работает при любом числе узлов в диапазоне от 1 до 24. Дальнейшее увеличение числа узлов для этого разбиения приведет к их простою, т.к. число параллельных процессов в алгоритме не превосходит числа фрагментов. Кроме того, отношение числа фрагментов разбиения к числу узлов должно быть целым для исключения простоя узлов.

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

Полученные результаты представлены в таблицах 3 и 4.

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

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

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

На рисунках 4-6 представлены результаты работы параллельной программы для различных разбиений. При решении тестовой задачи (1 проводник на двухслойном поле 600х600) решение было получено во всех случаях. Топологические отличия решений связаны с особенностью разработанного способа распределения нагрузки.

Рисунок 5. Пример решения задачи для разбиения 1x Рисунок 6. Пример решения задачи для разбиения 4x Рисунок 7. Пример решения задачи для разбиения 8x В заключении приведены основные результаты работы.

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

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

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

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

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

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

Основные результаты диссертации изложены в работах:

1. Ней Мин Тун. Исследование функциональных возможностей программы CAMtastic! 2000 Designer Edition для технологической подготовки производства печатных плат. // Микроэлектроника и информатика. 12-я Всероссийская межвузовская научнотехническая конференция студентов и аспирантов. - М.: МИЭТ, 2005, с. 108.

2. Ней Мин Тун. Расширение возможностей программы CAMtastic 2000 Designer Edition посредством разработки новых апертур. // Международная школа-конференция по направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ. – М.:

МИЭТ, 2005, с. 30.

3. Ней Мин Тун. Решение задач большой размерности на слабосвязанных кластерных вычислительных системах. // Микроэлектроника и информатика. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, 2006, с. 167.

4. Ней Мин Тун. Построение кратчайшего дерева из локальнооптимальных фрагментов. // Микроэлектроника и информатика. 14я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, 2007, с. 160.

5. Ней Мин Тун. Алгоритм двухслойной трассировки для параллельных вычислительных систем. // «Технологии разработки программных систем». Научная сессия МИФИ, 22-27 январь, 2007, с.133, секция И- 6. Ней Мин Тун. Программная реализация параллельной трассировки в среде mpC на кластере // «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем». Всероссийская межвузовская научнопрактическая конференция. - М.: МИЭТ, 2007, с. 133.

7. Ней Мин Тун. Реализация волнового алгоритма трассировки на кластерных вычислительных системах типа CoPC. // Системный анализ и информационно-управляющие системы: Сборник научных трудов под редакцией д.т.н., профессора В.А. Бархоткина – М.:

МИЭТ, 2006, с. 168-171.

многопроцессорных вычислителях. // Системный анализ и информационно-управляющие системы: Сборник научных трудов под редакцией д.т.н., профессора В.А. Бархоткина – М.: МИЭТ, 2008, с. 9. Зей Яр Вин, Ней Мин Тун, Тэй Зар Хтун. Исследование методов переноса последовательных алгоритмов на параллельные вычислительные платформы. //Вестник тульского государственного университета, серия «Радиотехника и радиооптика», Том IX, Тула.:

2007, с 199 – 207.

10. Лупин С. А., Ней Мин Тун, Милехина Т. В. Свидетельство РФ на программу для ЭВМ 2007 610703 от 11.12.2007 «Параллельная программа автоматического построения кратчайших связывающих деревьев ParTrace».

Подписано в печать:

Заказ №. Тираж экз. Уч.-изд.л. 1,35. Формат 60х84/16.

Отпечатано в типографии МИЭТ(ТУ) 124498, Москва, МИЭТ(ТУ)