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

• Автор: Антонов, Александр Викторович
• Шифр специальности: 05.13.15, 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Пенза
• Количество страниц: 171 с. : ил.

СОДЕРЖАНИЕ
Введение

Глава 1. Анализ моделей вычислений, вычислительных систем и способов

повышения их эффективности

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

1.1.1. Классификация Флинна

1.1.2. Классификация Хокни.

1.1.3. Классификация БМРМРР.

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

1.2.1. Технология построения кластерных вычислительных систем

1.2.2. Организация параллельных вычислений.

1.3. Распараллеливание программ.
1.4. Модели параллельных вычислительных процессов.
1.4.1. Использование модели на основе теории сетей Петри.
1.4.2. Использование логической модели параллельных программ.
1.4.3. Использование модели конечных недетерминированных цифровых автоматов.
1.4.4. Использование модели марковских процессов.
1.5. Эффективность параллельных вычислений
1.6. Выводы по главе
Глава 2. Модели параллельного вычислительного процесса
2.1. Основные понятия.
2.2. Алгоритм параллельной программы
2.3. Автоматная модель параллельной программы.
2.4. Марковская модель параллельного алгоритма на основе цифрового
автомата.
2.4.1. Применимость марковской модели для описания параллельного алгоритма.
2.4.2. Переход от модели недетерминированного цифрового автомата к модели марковских процессов.
2.5. Марковская модель работы параллельного алгоритма
2.5.1. Анализ непараллельной основной части программы
2.5.2. Анализ параллельных ветвей
2.5.3. Анализ трудоемкости.
2.6. Выводы по главе.
Глава 3. Повышение эффективности параллельных вычислений и параллельное
программирование.
3.1. Эффективность параллельных вычислений.
3.1.1. Методики построения моделей параллельного алгоритма.
3.1.2. Эффективность параллельного алгоритма.
3.1.3. Эффективная организация вычислительной системы
3.1.4. Повышение эффективности параллельных вычислений.
3.2. Построение высокопроизводительной вычислительной системы на
основе кластерной технологии.
3.2.1. Программный комплекс Распределенная вычислительная система
3.2.2. Организация доступа к кластеру
3.3. Технология параллельного программирования.
3.3.1. Технология написания параллельной программы для ПК РВС
3.3.2. Алгоритм параллельной программы для ПК РВС
3.4. Выводы по главе.
Глава 4. Анализ параллельных алгоритмов
4.1. Аналитический анализ алгоритмов.
4.1.1. Анализ алгоритма программы вычисления интеграла методом Симпсона для I.
4.1.2. Анализ алгоритма программы вычисления интеграла методом Симпсона для ПК РВС .
4.1.3. Анализ алгоритм программы умножения матриц для I
4.1.4. Анализ алгоритма программы умножения матриц для ПК РВС
МаШЫеЬ
4.2. Анализ полученных результатов.
4.2.1. Результаты тестирования программы вычисления интеграла методом Симпсона
4.2.2. Результаты тестирования программы умножение матриц.
4.3. Выводы по главе
Заключение
Литература


Выбрав конкретный класс ВС, можно также говорить о конкретных видах алгоритмов с присущими им особенностями и ограничениями, которые будут реализовываться на машинах выбранной архитектуры. Для этого надо рассмотреть несколько вариантов классификаций, начиная с классификации Флинна - первого опубликованного варианта. Классификация ВС впервые была предложена в конце -х годов XX века Флинном. МКМД (MIMD) (multiple instruction stream / multiple data stream) — множественный поток команд и множественный поток данных. Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике того или иного компьютера. У данной классификации есть явные недостатки. В частности, некоторые заслуживающие внимания архитектуры, например типа dataflow и векторно-конвейерных машин, четко не вписываются в данную классификацию. Другой недостаток - это чрезмерная заполненность класса МКМД (MIMD). Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попадают в один класс, но различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования. Р. Хокни - известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна [,]. Как отмечалось выше, класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рис. Рис. Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Как видно из данной классификации, параллельная программа в зависимости от алгоритма работы будет лучше реализовываться на той или иной архитектуре. Данная работа в основном ориентирована на программы для неконвейерных архитектур, т. Еще одним вариантом детализации класса М1МБ является классификация ЭМР/МРР. Данная классификация рассмотрена в [, ]. Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая - на использовании общей памяти. Существующие MIMD-системы распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти, и методику их межсоединений. К первому классу относятся системы с разделяемой (общей) основной памятью (Shared Memory multiprocessing, SMP), объединяющие до нескольких (2-) процессоров, число которых зависит от типа применяемой коммуникационной среды. Сравнительно небольшое количество процессоров в таких системах позволяет иметь одну централизованную общую память и зачастую объединить процессоры и память с помощью лишь одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров []. Второй класс составляют крупномасштабные вычислительные системы с распределенной памятью. Подобные ВС получили название систем с массовым параллелизмом (Mass-Parallel Processing, МРР). Для того чтобы подключать в систему большое количество процессоров, необходимо физически разделять основную память и распределять её между ними. В противном случае пропускной способности памяти просто может не хватить для удовлетворения запросов, поступающих от очень большого числа процессоров. Естественно при таком подходе также требуется реализовать связь процессоров между собой []. Так данные два класса SMP и МРР архитектур позволяют решать практически любые задачи, реализованные параллельными алгоритмами. Одним из вариантов реализации МРР систем являются кластеры рабочих станций, не требующие специальных технических средств и потому самые доступные.