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

• Автор: Во Минь Тунг
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 218 с. : ил.

1.1.2. Обзор современных супсркомпьютерных систем СИГ.

1.2. Особенности организация кластерных вычислительных систем.

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

1.4. Структуры кластеров, построенных на разных аппаратных платформах на примере кластеров МЭИ И ХТУ.

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

системы на примере кластера МЭИ И ХТУ.

1.6. Коммутационные среды кластерной вычислительной системы.

1.7. Анализ современных методов распределения задач

1.7.1. Режимы функционирования кластерных вычислительных систем.

1.7.2. Управление ресурсами в распределенных вычислительных системах

1.7.3. Планировщики кластерных вычислительных систем

1.8. Модели и алгоритмы назначения задач на КВС.
1.8.1. Понятие назначения задач на КВС
1.8.2. Обзор моделей распределения ресурсов и алгоритмов назначения.
1.9. Постановка задачи решаемой в диссертации.
1.9.1. Формальное описание модели кластерной вычислительной системы.
1.9.2. Формализованное описание класса задач
1.9.3. Задача эффективного назначения фрагментов параллельных программ на вычислители КВС.
1.9.4. Постановка задачи
Основные результаты и выводы
Глава 2. Экспериментальное исследование характеристик кластерных вычислительных систем, построенных на разных аппаратных платформах
2.1. Предложенные тестовые программы для исследования факторов, влияющих на время выполнения параллельных программ.
2.2. Результаты выполнения тестовых программ.
2.3. Разработка тестовых МР1программ для исследования
коммуникационной среды кластера
Основные результаты и выводы.
Глава 3. Модель и алгоритм назначения фрагментов
параллельных программ на вычислители КВС.
3.1. Оценка ожидаемого результата времени выполнения параллельных программ на КВС
3.2. Оптимизационная модель назначения фрагментов параллельных программ на вычислители КВС
3.2.1. Словесное описание математической модели, используемой в диссертации для моделирования процесса выполнения
параллельных программ на КВС в зависимости от варианта назначения
3.2.2. Аналитическая зависимость времени выполнения параллельных программ от характеристик КВС и варианта назначения фрагментов параллельных программ на вычислители КВС.
3.2.3 Оптимизационная модель обобщенного вида задачи назначения
3.2.4 Имитационная модель по интервалам времени для задач назначения.
3.3 Генетический алгоритм назначения вершим графа алгоритма на КВС.
Основные результаты и выводы
Глава 4. Анализ эффективности разработанного алгоритма назначения.
4.1 Критерии эффективности алгоритма назначения.
4.2. Анализ критерии эффективности от количества
вычислителей и алгоритма назначения.
4.3. Экспериментальные исследования эффективности выполнения параллельных программ при разных вариантах назначения на КВС
4.4. Методика назначения фрагментов параллельных программ на вычислители КВС.
4.4.1. Предварительная оценка эффективности
выполнения параллельных программ
4.4.2. Формальное представление класс решаемой задачи и КВС.
4.4.3. Тестирования КВС для получения характеристик
необходимых для имитационной модели.
4.4.4. Назначения фрагментов 1 1 на вычислители КВС.
4.4.5. Оценка результатов выполнения ПП на КВС
Основные выводы и результаты
Заключение
Приложение 1 Графы параллельных алгоритмов задач
Приложение 2 Основные характеристики кластера МЭИ ТУ
Приложение 3. Основные технические характеристики
технологии Iii.
Приложение 4 Основные технические характеристики
технологии
Приложение 5 Листинг программы для тестирования иерархической неоднородной организации памяти и коммутационных
сред кластеров МЭИ, ХТУ.
Приложение 6 Листинг программы перемножения матриц
Приложение 7 Листинг параллельной программы освещенности виртуальных экранов 3рефрактограмм и визуализации освещенности экрана в интерференционной схеме для модели
сферически неоднородной среды.
Приложение 8 Листинг прорамма, реализующей имитационную
модель с генетическим алгоритмом для задачи назначения
Приложение 9 Акты о внедрении.
Сокращение
1. МВС многомашинная вычислительная система
2. ГА генетический алгоритм
3. ПП параллельная программа
4. ПЗ прикладная задача
5. К ВС кластерная вычислительная система
6. ВУ вычислительный узел
7. ФПП фрагмент параллельной программы
8. КС коммутационная сеть
9. ВС вычислительная система
. ОН оперативная память
1 1. РГ1 распределенная память
. МПС многопроцессорные вычислительные системы
. i
. I i I
. I Iii
. 1
. ОС операционная система
. СУР система управления ресурсами
. СПОЗ система пакетной обработки заданий
. I параллельный алгоритм
. МЭИ Московский энергетический институт
. ХТУ Ханойский технологический университет
. МГУ Московский государственный университет
Аннотация работы
В диссертационной работе исследуется влияние характеристик современных кластерных вычислительных систем КВС, построенных на разных аппаратных платформах, на время выполнения прикладных задач с целью оценки коэффициентов накладных расходов, отражающих замедление этого времени. Рассмотрен способ повышения эффективности использования КВС, основанный на решении задачи назначения с помощью генетического алгоритма ГА, учитывающий характеристики КВС, параметры выполняемой задачи и коэффициенты накладных расходов.
В практической части работы излагаются результаты исследования эффективности решения прикладных задач при различных вариантах назначения фрагментов параллельных программ на кластерах МЭИ ТУ, МГУ и Ханойского технологического университета ХТУ.
Работа состоит из введения, четырех глав, заключения, списка литературы, девяти приложений, включающих в себя основной код реализации предложенных задач на кластерах.
Введение


Факультет Вычислительной математики и кибернетики Московский государственный университет имени М. В. Ломоносова Москва г. Кластерная система УГАТУ УГАТУ Уфа г. Кластерная система Таганрогского Технологического Института РОЦ НИТ Таганрогский Технологический Институт Южного Федерального Университета Таганрог г. Суперкомпьютер НРС i Х0 Междисциплинарный центр компетенций в области аэробиологии, микробиологии и нанотехнологий ГОУ ВПО Вятский государственный университет Киров г. I ix I Росгидромет Москва г. Кластерная система СФУ СФУ Красноярск г. СКИФ Урал ЮжноУральский государственный университет. Челябинск г. Таблица 1. Гфлопс 0 8 0 8. ПронЭБОДытвлыюсть по тесту Галопе 0 1ЛЧП 0 0 5 8. О 8 7. Частого ГГц 3 3 2. Транспортная сеть 2x . Операционная система i 6. Материалы, приведенные в таблице 2, свидетельствуют о том, что большинство суперкомпьютеров относятся к кластерным вычислительным системам КВС. Такая популярность связана с невысокой стоимостью таких систем и их высокой производительностью и следовательно хорошим соотношением производительностьстоимость, а также возможностью масштабирования. Все КВС построены по одному принципу иерархия вычислителей, памяти, коммутационных сред. Однако, каждый уровень иерархии вычислителей может использовать свой способ организации обработки, обращения к памяти, передачи данных. В этом смысле такие системы называют мультиархитектурными. Кроме того, каждая КВС отличается друг от друга применением различных технологий построения вычислителей, памяти, КС. Рассмотрим эти особенности на примере КС КВС 1 и 2 из таблицы 2. КВС 1 использует КС Iii 4x, пропускная способность которой в четыре раза больше, чем КС КВС 2. Таким образом, время на межузловые передачи для КВС 1 будет меньше, чем у КВС 2, следовательно, эффективность при выполнении задач будет выше. Также из таблицы можно заметить, что КВС используют разные процессорные шины, которые в свою очередь тоже вносят свое влияние на эффективность КВС. Рассмотрим особенности процессорных шин I и НТ. Шина i I I последовательная кэшкогерентная шина типа точкаточка для соединения процессоров между собой и с чипсетом, I является обновленной версией шины i ,. Каждое соединение шины I состоит из пары односторонних каналов. Данные передаются в виде пакетов, где пропускная способность одного канала составляет от до миллионов посылок в секунду. Следовательно, теоретическая суммарная пропускная способность одного соединения от ,2 до ,6 гигабайт в секунду то есть от 9,6 до ,8 ГБс в каждую сторону, при этом один процессор может иметь несколько соединений,,,. ГГц. Полноразмерная, полноскоростная, битная шина в двунаправленном режиме способна обеспечить пропускную способность до 0 Мбайтс 2 х 2 х 8 байт х МГц максимум в одном направлении 0 Мбайтс , ,,. Таким образом, при выборе тех или иных технологий построения КВС может существенно варьироваться производительность системы в целом. Таким образом, при выборе разных технологий КВС, по сути, остаются одинаковыми по типу построения ВС, но разные по структуре отдельных компонентов. Другими словами с одной стороны КВС имеют общие особенности построения иерархических структур, но с другой стороны являются уникальными объектами по способам реализации. Поэтому, получая удовлетворительный результат решения задачи на одном КВС, не означает что, перенося его на другой КВС результат, останется прежним. Во второй главе будут подробно рассмотрены результаты экспериментальных исследований характеристик конкретных КВС, которые надо учитывать при решении прикладных задач на КВС. Особенности организация кластерных вычислительных систем. Кластерная вычислительная система является одним из представителей многомашинных вычислительных систем. В качестве ВУ для кластеров некоторое время назад использовались доступные на рынке однопроцессорные компьютеры, в настоящее время используются 2х или 4х процессорные платформы. Каждый ВУ имеет свою локальную память и может содержать несколько процессоров, каждый из которых содержит несколько ядер.