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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика — 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. Проведенные исследования подтвердили эффективность предложенного метода распределения нагрузки и алгоритмов.