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

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

ЗЕЙ ЯР ВИН

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

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

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

Москва 2008

003451581

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

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

Лупин Сергей Андреевич.

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

оппоненты Гагарина Лариса Геннадьевна

кандидат, физико-математических наук Посыпкин Михаил Анатольевич

Ведущее предприятие - Южный научный центр Российской

академии наук (ЮНЦ РАН).

Защита состоится " ^ 5 "__^_______ 2008 года на заседании

диссертационного совета Д212.134.02 при Московском государственном институте электронной техники (техническом университете). ¡24498, Москва, Зеленоград, прое'д 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан " Ю " >Р__2008 года.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Итерационный параллельный алгоритм решения задачи квадратичного назначения.

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

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

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

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

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

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

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

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

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

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

позволяет использовать их уже при N>20. Известны алгоритмы, основанные на методе ветвей и границ, которые позволяют сократить в некоторых случаях объем вычислений и несколько увеличить размерность решаемых задач до N<25. Однако когда мы рассматриваем крупномасштабные проблемы, мы вынуждены опираться на итерационные алгоритмы, которые дают хорошее приближение, зависящее от количества итераций. При этом именно параллельные системы могут быть с успехом использованы для повышения точности расчетов.

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

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

-время-►

1 2 3 4 5

I I вычисления <-> коммуникации

Рис. 1. Синхронный итерационный алгоритм

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

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

-время-►

♦се к :1 >: ;< и-к>

1 2 3 4 5

( '» вычисления

О-^ коммуникации

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

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

■время-

4-И-И—И—И-И-►<-И—

' ] 2 ' 3 ' 4 ' 5 ' 6 ' 7 8 < > вычисления и коммуникации

Рис. 3. Асинхронный итерационный алгоритм

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

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

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

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

• ручное распараллеливание — программист самостоятельно выделяет блоки параллелизма, организует синхронизацию вычислений и обработку критических ситуаций;

• полуавтоматическое распараллеливание — компилятор при трансляции кода руководствуется директивами программиста, но вопросы синхронизации решаются автоматически;

• автоматическое распараллеливание — компилятор выполняет все этапы распараллеливания самостоятельно, учитывая конфигурацию аппаратных ресурсов системы.

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

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

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

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

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

Методы полного автоматического распараллеливания включают компиляторы распараллеливания, которые преобразовывают стандартные последовательные программы в параллельные. Преимуществом компиляторов распараллеливания, таких как Paradigm, SUIF и RHODOS

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

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

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

> минимизировать межпроцессорные обмены,

> балансировать нагрузку узлов.

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

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

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

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

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

В общем виде задача размещения элементов на коммутационной плате формулируется следующим образом. Задано множество элементов

е,,е2,...,е„ и две матрицы: Я= г,7 , где для каждой пары элементов

II Илхя

заданы весовые коэффициенты = 1,2,...,«), определяющие связи

элементов друг с другом, и Э = , элементы которой определяют

И 1 ппхп

расстояние между посадочными местами на коммутационной плате.

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

где /?(() задает номер позиции, присвоенный /-му элементу.

Для нахождения точного решения необходимо произвести перебор п\ различных вариантов размещения элементов, что при п > 20 становится трудновыполнимой задачей.

В качестве тестовой задачи в работе используется тест-задача Штейнберга (36 элементов, размещаемых на поле размером 4x9). Покажем, что перебор вариантов для такой размерности практически не реализуем. Общее число вариантов размещения составляет 36!,

трудоемкость вычисления оптимизируемой функции 0(п)^п2= 362 операций умножения и сложения. Итого 4.8Е+44 операций. Даже для петафлопных вычислителей время решения задачи во много раз превышает время существования Земли.

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

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

Пусть у нас есть последовательная программа, состоящая из набора процедур. Для нахождения решения необходимо выполнить ее К раз.

(=1 ;=/+!

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

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

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

выполняет программу М = ^ раз. Таким образом, мы сможем сократить

время расчетов, но не повысить их точность.

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

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

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

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

состоит в равномерном ее распределении между узлами load ='

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

Parallel Iterative Placement algorithm:

Initialization of MPI (MPIJnit) Initialization of minjength

receive R[36][36], D[36][36] from server receive number of iterationsQoad)

repeat Setting array p[] to 1-36

Find 2 random numbers to change placement between the elements first~rand()/(rank+1)%36; $econd=rand()/(rank+l)%36;

Store array p[36] in temporary array pp[36]

Change placement of 2 elements (p[first] and pfsecond])

Compute total length of f (X)

length += *[«][/] x D[p[i]}{p[j]]

if minimumJength>lenglh then

Update minjength (min_length=length)

else

Restore array p[] from temporary array pp[] until termination condition(coim/ <= load)

send m in_ /ength,, min_ lengtht+min_ lengthn _x to server

Server:

Compare the results and choice the minimum length Get the placement order by array p[]

Рис. 4. Асинхронный итерационный алгоритм

Здесь операторы пересылок send и receive, являются асинхронными.

Заметим, что периоды асинхронности узлов в этом алгоритме могут

изменяться. Пусть узел должен выполнить load = итераций.

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

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

36 1

Г = Зб£-»Зб(1пЗб + 0.557)»150

к=1 к

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

что снижает вероятность повторов. Представим набор чисел, которыми заполняется вектор, в виде упорядоченной последовательности - от 1 до 36. Тогда одно из чисел будет отражать номер раздела этой последовательности, а второе - смещение в нем. Принцип заполнения вектора для разбиения 4*9 иллюстрируется на рисунке 5.

LiiliLiliiiiil-8.!.?. 1ft|20 [21122 ]» [2В]27

row - 0 row -1 row - 2 row - .1

Г

row ~ 2 position -- 5 —Iplacemen! - J *9-*5 - 23)

row = randQ % 4; position ! f randQ % 9; placement row * 9 ■ position;

i i,l

---3|No

row = rand()%4; ;

Yes

-"-'.row_cnt[rov*]==97

~7jNo

position = 1+ rand()%9; ;

[placement = row x (9) + position,J

-<Cused[placemerit-l] == (D

p[count] = placement !

count++; !

row-cnt[row]++; j

jjjsed[placement-1]= 1

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

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

Разбиение Число бросков Время заполнения вектора (сек)

1*36 150 1.2566Е-05

2*18 127 1.0438Е-05

3*12 113 1.0067Е-05

4*9 100 9.3560Е-06

6*6 88 9.2190Е-06

9*4 75 9.1690Е-06

12*3 67 8.8560Е-06

18*2 54 8.7260Е-06

1.4000Е-03

1.2000Е-05

0 1.0000Е-05 s

^ 8.0000Е-06 ■ -

0

1 6.0000Е-06 u

CX

И

4.0000Е-Об 2.0000E-06 O.OOOOE+OO

1*36

2x18

4x9 6x6

Разбиение

Рис. 6. Зависимость времени генерации вектора от разбиения Для практических исследований эффективности предложенного подхода была разработана параллельная MPI программа.

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

Параллельная программа решения задачи квадратичного назначения использует библиотеку MPI. Ее исследования проводились на 32-х процессорном кластере МИЭТ-2005 и 3-х процессорной кластерной системе типа СоРС. В качестве коммуникационной среды в обоих вычислителях используется Ethernet 100.

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

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

Некоторые результаты исследований приведены на рисунках 7-10.

6400

1.Е+08

5.Е+08 Число итераций

Рис. 7. Экспериментальные результаты вычислений (НРС - Cluster) - 1 На рис. 7 представлены результаты исследований алгоритма случайного поиска. Полученные данные подтверждают эффективность предложенного метода получения случайного вектора. При увеличении числа итераций результаты улучшаются для всех видов разбиения.

—♦—Вариант 1 (7836) -«— Вариант 2 (6963) —^-ВариантЗ(б801) -*— Вариант4 (6847) Вариант5(7176)

4500

1.Е+08

5.Е+08 Число итераций

1.Е+09

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

возможность практического использования параллельной реализации алгоритма.

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

—•— Вариакг1 (7836) --«--Вариант2 (7176) -л— Вариант 3 (6801) ■• к ~ Вариант4 (6692) Вариант 5 (7092)

4800

5.Е+08 Число итераций

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

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

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

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

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

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

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

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

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

6. Исследования разработанных программ проводились на двух вычислительных системах - 16*(2*P-III 550) и 3*Dual Core 2400. Проведенные исследования подтвердили эффективность предложенного способа распределения нагрузки и алгоритмов.

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

1. Зей Яр Вин. Исследование архитектур высокопроизводительных вычислительных систем.// Международная школа-конференция по направлению «Информационно-телекоммуникационные

системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ. Тезисы докладов - М.: МИЭТ, 2005 - с. 19.

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

3. Лупин С.А., Зей Яр Вин. Исследование эффективности алгоритма случайного поиска для многопроцессорных вычислительных систем. // Системный анализ и информационно-управляющие системы: Сборник научных трудов под редакцией д.т.н., профессора В.А. Бархоткина-М.: МИЭТ, 2006 г., с. 149-154.

4. Зей Яр Вин. Реализация итерационных алгоритмов размещения на многопроцессорных вычислительных системах.// «Технологии разработки программных систем». Научная сессия МИФИ, 22-27 январь, 2007. — с. 132, секция И-5

5. Зей Яр Вин. Эффективность реализации итерационных алгоритмов размещения на многопроцессорных вычислительных системах.// Микроэлектроника и информатика. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, 2007 .-С. 210.

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

2007 .-С. 102.

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

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

2008 г., с 164-168.

9. Зей Яр Вин. Эффективность распараллеливания итерационных алгоритмов размещения на многопроцессорных вычислительных системах с распределенной памятью.// Микроэлектроника и информатика. 15-я Всероссийская межвузовская научно-

техническая конференция студентов и аспирантов. - М.: МИЭТ, 2008 г .-С. 193

10. Зей Яр Вин., Пущин М.Н., Шкарупа К.В. Свидетельство РФ на программу для ЭВМ 2007614893 от 6.12.2007 "Параллельная программа автоматического решения задачи квадратичного назначения - «РагС)иа(1» " 2008 г.

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

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

Обозначения и сокращения.

Введение.

ГЛАВА 1. АНАЛИЗ РЕАЛИЗУЕМОСТИ ИТЕРАЦИОННЫХ АЛГОРИТМОВ НА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.

1.1 Понятие итерационных алгоритмов.

1.2 Анализ параллельных алгоритмов.

1.3 Классификация параллельных итерационных алгоритмов.

1.3.1 Алгоритм с синхронными итерациями и коммуникациями.

1.3.2 Алгоритм с синхронными итерациями и асинхронными коммуникациями

1.3.3 'Алгоритм с асинхронными итерациями и коммуникациями.

1.4 Параллельные асинхронные итерационные алгоритмы.

1.5 Проблема переносимости прикладных программ в среде параллельных ЭВМ

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

1.5.2 Основные виды суперкомпьютерных сред.

1.5.3 Стандартизованное описание супер-ЭВМ среды.

1.5.4 Особенности функционирования программ на аппаратных платформах MIMD

1.6 Современные среды параллельного программирования.

1.6.1 Средства коммуникации для систем с распределенной памятью.

1.6.2 MPI.

1.6.3 PVM.

1.7 Выводы.

ГЛАВА 2. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ.

2.1 Архитектура высокопроизводительных ЭВМ.

2.1.1 SIMD - суперЭВМ.

2.1.2 Многопроцессорные ЭВМ.

2.1.2.1 Массивно-параллельные ЭВМ с распределенной памятью.

2.1.2.2 Параллельные компьютеры с общей памятью.

2.1.2.3 Векторно-конвейерные ЭВМ.

2.1.2.4 Многопроцессорные ЭВМ с архитектурой комбинированного типа.

2.2 Методы распараллеливания программ.

2.2.1 Ручное распараллеливание.

2.2.2 Полуавтоматическое распараллеливание.

2.2.3 Автоматическое распараллеливание.

2.3 Основные проблемы управления параллелизмом на кластере.

2.3.1 Параллельные программы на основе SPMD.

2.3.2 Кластеры рабочих станции.

2.3.3 Выполнение параллельных SPMD программ на кластерах.

2.3.4 Проблемы управления параллелизмом.

2.4 Высокая производительность коммуникаций.

2.4.1 Myrinet.

2.4.2 SCI.

2.4.3 QSNET.

2.5 Отношение стоимости вычислений и коммуникаций.

2.6 Накладные расходы на поддержание параллелизма.

2.6.1 Накладные расходы на коммуникацию.

2.6.2 Накладные расходы на синхронизацию.

2.7 Выводы.

ГЛАВА 3. АНАЛИЗ МЕТОДОВ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ.

3.1 Распределение задач при параллельных вычислениях.

3.1.1 Количество подзадач.

3.1.2 Количество процессоров и время вычисления.

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

3.2.1 Порядок распределения нагрузки.

3.3 Постановка задачи квадратичного назначения.

3.3.1 Классификация алгоритмов размещения.

3.3.2 Итерационные алгоритмы улучшения размещения.

3.4 Решение задачи квадратичного назначения на параллельной платформе

3.4.1 Методы распределения нагрузки при решении задачи квадратичного назначения.

3.4.2 Ускорение генерации случайного вектора.

3.5 Выводы.

ГЛАВА 4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ И ИСПЫТАНИЙ

4.1 Решение задачи квадратичного назначения на кластере.

4.1.1 Архитектура экспериментальных систем.

4.1.2 Параметры системы.

4.1.3 Механизм распределения нагрузки для задачи квадратичного назначения

4.2 Результаты последовательного решения тестовой задачи.

4.2.1 Алгоритм случайного поиска.

4.2.2 Алгоритмы парных перестановок.

4.2.3 Алгоритмы групповых перестановок.

4.3 Параллельные алгоритмы решения оптимизационных задач.

4.3.1 Параллельная реализация алгоритмов случайного поиска.

4.3.2 Параллельная реализация алгоритма парных перестановок.

4.3.3 Параллельная реализация алгоритма групповых перестановок.

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

4.4 Выводы.

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

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

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

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

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

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

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

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

- Разработка параллельного алгоритма решения задачи квадратичного назначения.

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

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

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

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

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

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

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

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

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

- Итерационный параллельный алгоритм решения задачи квадратичного назначения.

- Параллельная программа автоматического решения задачи квадратичного назначения.

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

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

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

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

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

4.4 Выводы

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

- выбранные для исследования варианты итерационных алгоритмов показывают эффективность, как при последовательной, так и при параллельной реализации;

- предложенный метод распараллеливания обеспечивает масштабируемость всех исследованных вариантов алгоритмов;

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

Заключение

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

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

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

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

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

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

6. Исследования разработанных программ проводились на двух вычислительных системах - 16*(2*P-III 550) и 3*Dual Core 2400. Проведенные исследования подтвердили эффективность предложенного метода распределения нагрузки и алгоритмов.