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

• Автор: Зей Яр Вин
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 146 с. : ил.

Оглавление

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

Введение.

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

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

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

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

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

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 Особенности функционирования программ на аппаратных платформах
1.6 Современные среды параллельного программирования.
1.6.1 Средства коммуникации для систем с распределенной памятью
1.6.2 I
1.6.3 V
1.7 Выводы.
ГЛАВА 2. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ
МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ
2.1 Архитектура высокопроизводительных ЭВМ.
2.1.1 1суперЭВМ
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 Параллельные программы на основе
2.3.2 Кластеры рабочих станции.
2.3.3 Выполнение параллельных программ на кластерах.
2.3.4 Проблемы управления параллелизмом
2.4 Высокая производительность коммуникаций
2.4.1 i
2.4.2 I
2.4.3
2.5 Отношение стоимости вычислений и коммуникаций
2.6 Накладные расходы на поддержание параллелизма
2.6.1 Накладные расходы на коммуникацию
2.6.2 Накладные расходы на синхронизацию.
2.7 Выводы.
ГЛАВА Э. АНАЛИЗ МЕТОДОВ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ
НАГРУЗКИ ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ.
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 Выводы
Заключение
Литература


Если присутствует хотя бы одно из перечисленных требований, то использования высокопроизводительных вычислений необходимо и оправдано. В вычислительной математике с помощью итерационного метода пытаются решить проблему (например, уравнение или систему уравнений) находя успешные аппроксимации решения, начиная от первоначальной догадки. Итерационные методы полезны для решения задач, в которых имеется большое количество переменных (иногда порядка миллионов), где применения прямых методов было бы слишком дорого и, в некоторых случаях, невозможно, даже при наличии самых мощных вычислительных ресурсов. Один из наиболее характерных примеров - предсказание прогноза погоды. Область решения (атмосфера) разбивается на отдельные пространственные ячейки, причем для расчета временных изменений вычисления в каждой ячейке итерируются много раз. Если объем ячейки равен 1 км, то для моделирования км слоя атмосферы потребуются 5x8 таких ячеек. Предположим, что вычисления в каждой ячейке потребуют 0 операций с плавающей точкой, тогда за один временной шаг потребуется выполнить м операций с плавающей точкой. МАорэ (К)8 операций с плавающей точкой в секунду) потребуется 7 секунд или свыше 0 дней. Для того чтобы произвести расчет за мин, потребуется компьютер с производительностью 1. ТПорз (1. В настоящее . Именно поэтому для такой большой задачи нам необходимо использовать параллельные системы, такие как вычислительные кластерные системы. В данной работе мы определяем и анализируем коммуникационные требования к крупномасштабным приложениям, к категории которых относится и задача квадратичного назначения, решаемая с помощью параллельных итерационных алгоритмов. В области прикладной науки, информационных систем и техники существует много проблем, решение которых требует значительных вычислительных ресурсов. Они, до недавнего времени, могли решаться только посредством параллельных вычислений на суперкомпьютерах или системах МРР. Уровень вычислительных возможностей кластера быстро возрастает за последние годы; приемлемое отношение стоимости к производительности таких систем делает параллельное вычисление на кластерах серьёзным конкурентом для традиционных параллельных вычислений на суперкомпьютерах и системах МРР. Кластеры, построенные на готовом оборудовании и использующие бесплатное программное обеспечение, играют большую роль при решении прикладных проблем в науке, технике и коммерции. ПО. Для параллельных применений с интенсивными межузловыми обменами максимальная достигаемая степень параллелизма ограничена пропускной способностью, имеющейся коммуникации. Хотя проблемы создания параллельных приложений и интенсивно изучались в последнее время, управление параллелизмом не принималось во внимание. Для того чтобы сделать кластер эффективной платформой для параллельных вычислений, необходимо тщательно изучить проблемы управления параллелизмом, такие как достижение высокой производительности выполнения параллельного применения, улучшение вычислительных возможностей и более простое программное окружение для пользователей []. Кластерное вычисление обеспечивает недорогие вычислительные ресурсы для учебных учреждений и научных работников. Her необходимости вкладывать миллионы долларов, чтобы покупать параллельные компьютеры. Для параллельных вычислений можно построить маленький кластер из нескольких отдельных компьютеров, получить бесплатное программное обеспечение и использовать этот кластер для параллельного вычисления. Многие страны во всем мире, включая и развитые страны, использовали кластеры в качестве платформы для высокопроизводительных вычислений. Мьянма принадлежит к группе развивающихся стран и пока не может тратить много средств на приобретение и разработку суперкомпьютеров, как это делают в России, Японии и Европейских странах []. Поэтому использование кластеров для параллельных вычислений является оптимальным способом для высокопроизводительных вычислений для Мьянмы. Сложность последовательного алгоритма обычно определяется его временной и пространственной сложностью. Временная сложность алгоритма связана со временем вычисления как функция размера проблемы.