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

003454391

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

НЕЙ МИН ТУН

/

АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ГРАФОВЫХ МОДЕЛЕЙ НА КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

о 5 ДЕК 2008

МОСКВА 2008

003454991

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

Научный руководитель

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

Официальные оппоненты

доктор технических наук, Щагин А.В.

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

Ведущее предприятие

- Московский авиационный институт

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

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

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан "/4-" X/,_2008 года.

Ученый секретарь диссертационного совета

д.т.н. />)у Гуреев А.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

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

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

о = (г,л),

где V = {у( },1 <1 <п множество вершин,

а. Я = [гJ },1 < у < т множество дуг графа

Граф может быть представлен при помощи матрицы смежности

Л = (а0.\ 1</,7<и,

элементы которой соответствуют дугам графа

Чф^уДеош О^ОеД, О, если / = _/,

со, иначе.

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

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

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

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

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

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

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

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

• волновые алгоритмы трассировки, основанные на идее Lee, и его модификации;

• ортогональные (лучевые) алгоритмы;

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

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

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

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

платформы приведен в таблице I.

__Таблица 1. Сравнение трассировщиков

Класс алгоритмов Характеристика Переносимость

Волновые - гарантируют построение трассы, если путь для нее в принципе существует; - высокое качество решений; - низкое быстродействие. Да

Канальные - используются при проектировании БИС и СБИС; - имеют высокие требования к качеству получаемых решений. Да

Топологические - не требуют дискретного описания рабочего поля; - ориентированы на однослойную коммутацию. Нет

Ортогональные - высокое быстродействие; - ориентированы на ортогонально-двухслойную коммутацию Частично

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

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

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

п

ы\

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

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

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

О

Последовательная схема решения

Параллельная схема решения

Подзадача Подзадача

Подзадача Подзадача

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

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

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

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

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

С = {с,}

! С2" ; ■ ■ Оз

с 5

1 ; ' ! | ■

■ - 1 ! ■ ■

.... ^ 1 , ; ■ С4

^ 1 1 | . ! ' : : ■ 1 . 1.

; ! ^е ! {

(......; г' ...... •с; :■•■ " 1

..... - ■: | ■

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

-И' .. 1 . .1.. ■ п ■ сЭГ

- •} 1 - 1 -( ' : I ! |

! 1 1 I! "и. ' я ч •

Построение скелета дерева. Г = Tree (С)

ТО

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

с"={с;}

тт

-J-

t-i-r

в

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

'Л

5

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

М ^=1

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

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

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

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

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

передает их на хост С' = {с,'} , который и строит предварительный

скелет. Найденный скелет Т' = Тгее(С'^ соединяет только

центры тяжести отдельных фрагментов дерева. Для проведения макро-трассировки используется модифицированный однослойный волновой алгоритм.

Построенный скелет дерева позволяет определить граничные

точки для каждого сегмента рабочего поля С' = {с*} . Это

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

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

в каждом сегменте коммутационной платы Tjk = {с"}д к ■ Решение задачи осуществляется

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

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

N М

фрагментов дерева Т = ^ Тк и формирование его

j=1 /Ы

окончательной топологии.

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

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

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

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

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

Число узлов Время (сек)

1 80.93

2 73.65

3 71.47

4 69.63

6 64.25

8 63.44

12 61.17

24 59.45

о

е 50-.......................................

«

3 40-.......................................

о,

т 30-.......................................

20........................................

10 -.......................................

0 Н-1-1-1-1-1-1-1-

1 2 3 4 6 8 12 24 Число узлов

Рисунок 2. Исследование масштабируемости для разбиения 4*6

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

Таблица 3. Исследование линейных разбиений.

Разбиения Время вычисления Время передачи данных Длина

1x1 242.44 1.56 5393

2x1 96.12 7.90 5450

3x1 61.79 10.42 5653

4x1 45.48 12.76 5843

5x1 41.61 12.76 5983

6x1 36.29 14.04 6085

8x1 41.78 14.15 6750

10x1 41.42 14.57 7263

12x1 41.71 15.90 7937

15x1 57.25 15.85 8394

24x1 62.10 18.02 10516

■Время вычисления

"Время передачи данных

300

Вариант разбиения узлов

Рисунок 3. Исследование линейных разбиений

Таблица 4. Исследование матричных разбиений.

Разбиения Время вычисления Время передачи данных Длина

1x1 242.44 1.56 5393

2x2 45.05 12.44 5642

2x3 36.29 13.91 5547

3x2 37.53 13.97 5923

3x3 34.59 16.50 5839

3x4 33.92 16.35 5995

4x3 35.72 16.53 5937

3x5 35.97 16.23 5757

5x3 40.21 18.09 5930

4x4 37.58 16.11 6106

4x5 40.01 16.75 5916

5x4 42.02 17.48 5988

4x6 51.60 18.82 6252

6x4 43.25 17.27 5947

♦ Время Вычисления • 'Время передачи данных

300 250 Я 200

О

^ 150

50 0

iNnlNM'imvitOtHlt«^ ХХХХХХХХХХХХХХ

Вариант разбиения узлов

Вариант разбиения узлов

Рисунок 4. Исследование матричных разбиений

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

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

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

Рисунок 5. Пример решения задачи для разбиения 1x24

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

Основные результаты работы

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

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

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

4. Создан программный модуль, реализующий предложенный алгоритм на кластерной системе и получено свидетельство на программу. Программный модуль реализован в среде трС 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, секция И-5

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

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

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

9. Зей Яр Вин, Ней Мин Тун, Тэй Зар Хтун. Исследование методов переноса последовательных алгоритмов на параллельные вычислительные платформы. //Вестник тульского государственного университета, серия «Радиотехника и радиооптика», Том IX, Тула.: 2007, с 199-207.

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

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

Заказ №/3^- ТиражЛ.Гэкз. Уч.-изд.л. 1,35. Формат 60x84/16. Отпечатано в типографии МИЭТ(ТУ) 124498, Москва, МИЭТ(ТУ)

Введение

Глава 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.

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