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

• Автор: Жидченко, Виктор Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Самара
• Количество страниц: 189 с. : ил.

СОДЕРЖАНИЕ

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

1 ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ НА ЭВМ

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

1.2 Явный параллелизм и автоматическое распараллеливание

1.3 Графические модели параллельных процессов.

1.4 Взаимодействие параллельных процессов.

1.4.1 Механизмы синхронизации параллельных процессов

1.4.2 Проблема тупиков в параллельных алгоритмах

Выводы и основные результаты

2 ГРАФИЧЕСКАЯ МОДЕЛЬ АЛГОРИТМОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
2.1 Концептуальное описание графмодели.
2.2 Синхронизация между параллельными ветвями графмодели.
2.3 Создание графмоделей параллельных вычислений.
2.4 Реализация вычислений, описанных графмоделью.
Выводы и основные результаты
3 СИНХРОНИЗАЦИЯ В МОДЕЛИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА
3.1 Простейший метод поиска критических данных в модели параллельного алгоритма.
3.2 Метод поиска критических данных на основе алгебры над способами использования данных
3.3 Пример применения формулы над способами использования данных для поиска критических данных.
3.4 Алгоритм построения и вычисления формул над способами использования данных
3.5 Проверка корректности синхронизации графмодели.
3.5.1 Метод проверки корректности синхронизации графмодели.
3.5.2 Метод поиска тупиков.
3.6 Пример использования методов поиска критических данных и проверки корректности синхронизации
3.6.1 Параллельная модель Я8триггера
3.6.2 Модель ИЯтриггера без синхронизации.
Выводы и основные результаты.
4 ПРОГРАММНЫЙ КОМПЛЕКС МОДЕЛИРОВАНИЯ И АНАЛИЗА АЛГОРИТМОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ.
4.1 Архитектура программного комплекса моделирования и анализа алгоритмов параллельных вычислений
4.2 Программный комплекс моделирования и анализа алгоритмов параллельных вычислений РСЯАРН 1.0
4.2.1 Создание моделей параллельных алгоритмов в программном комплексе РСАРН 1.0.
4.2.2 Генерация исходных текстов параллельных программ на языке С.
4.2.3 Межмодульный информационный интерфейс.
4.2.4 Обмен данными между параллельными процессами
4.2.5 Модуль передачи сообщений.
Выводы и основные результаты
5 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРАКТИЧЕСКОЙ ЗНАЧИМОСТИ МОДЕЛИ
5.1 Решение уравнения Лапласа.
5.1.1 Постановка задачи и последовательный алгоритм решения уравнения Лапласа.
5.1.2 Параллельный алгоритм решения уравнения Лапласа.
5.1.3 Экспериментальная проверка эффективности параллельного алгоритма.
5.2 Распараллеливание алгоритма решения системы дифференциальных уравнений НавьеСтокса
5.3 Распараллеливание многосеточных методов.
Выводы и основные результаты
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


В зависимости от числа потоков команд и потоков данных, архитектуры ВС делятся на 4 класса (рисунок 1. Рисунок 1. Классификация вычислительных систем по М. SISD (Single Instruction stream / Single Data stream) - единственный поток команд и единственный поток данных. К этому классу относятся классические последовательные ВС (ВС фон-неймановского типа), например, PDP- или VAX /0. В таких ВС только один поток команд, все команды выполняются последовательно друг за другом, и каждая команда инициирует одну скалярную операцию. SIMD (Single Instruction stream / Multiple Data stream) - одиночный поток команд и множественный поток данных. Команды выдаются одним управляющим процессором, а выполняются одновременно на всех обрабатывающих процессорах над локальными данными этих процессоров. Подобную архитектуру имеют ILLIACIV и ICL DAP. MISD (Multiple Instruction stream / Single Data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако до сих пор специалистам в области архитектуры компьютеров не удалось представить убедительный пример реально существующей ВС, построенной на данном принципе. MIMD (Multiple Instruction stream / Multiple Data stream) -множественный поток команд и данных. ВС содержит несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Существующие параллельные ВС класса MIMD образуют три подкласса: симметричные мультипроцессоры (SMP-системы), кластеры и массово параллельные системы (МРР-системы). В основе этой классификации лежит структурно-фу нкциональный подход. Симметричные мультипроцессоры состоят из совокупности процессоров, обладающих одинаковыми возможностями доступа к памяти и внешним устройствам и функционирующих под управлением одной операционной системы (ОС). Частным случаем SMP-систем служат однопроцессорные компьютеры. Примером SMP-систем могут служить компьютеры HP Superdome и Sun StarFire. Однако степень масштабируемости SMP-систем ограничена в пределах технической реализуемости одинакового для всех процессоров доступа в память со скоростью, характерной для однопроцессорных компьютеров. Как правило, количество процессоров в SMP-системе не превышает . Для построения систем с большим числом процессоров применяются кластерный или МРР подходы. Оба эти направления используют SMP-системы как системообразующий вычислительный модуль (ВМ). Кластерная система образуется из модулей, объединенных системой связи или разделяемыми устройствами внешней памяти, например дисковыми массивами. В настоящее время для образования кластерных систем используются либо специализированные фирменные средства (например, MEMORY CHANNEL фирмы DEC, AWS фирмы NCR), либо универсальные локальные и глобальные сети такие, как Ethernet, FDDI (Fiber Distributed Data Interface), и другие сети, например, с протоколами TCP/IP (Transmission Control Protocol / Internet Protocol), либо дисковые массивы с высокоскоростными широкими двойными (Wide/Fast) и квадро PCI SCSI контроллерами. Размер кластера варьируется от нескольких модулей до нескольких десятков модулей. ВМ. По кластерному принципу построены CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, последние модели IBM SP2 и другие. Именно это направление является в настоящее время наиболее перспективным для конструирования компьютеров с рекордными показателями производительности. Массово параллельные системы, в отличие от кластеров, имеют более скоростные, как правило, специализированные, каналы связи между ВМ, а также широкие возможности по масштабированию. Кроме того, в МРР-системах фиксируется некоторый достаточно высокий уровень интерфейса прикладных программ (API), поддерживаемый распределенной ОС. Однако поддержка работоспособности и оптимизация загрузки процессоров в МРР-системах менее развита по сравнению с кластерами в силу разнообразности исполняемых программ и отсутствия функциональных связей между программами.