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

• Зей Яр Вин
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Зей Яр Вин

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

Введение.

ГЛАВА 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. Проведенные исследования подтвердили эффективность предложенного метода распределения нагрузки и алгоритмов.