Разработка и исследование методов синтеза параллельных алгоритмов для многопроцессорных систем со структурно-процедурной организацией вычислений

• Автор: Пономарев, Игорь Михайлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Таганрог
• Количество страниц: 248 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. СТРУКТУРНОРОЦЕДУРНАЯ ОРГАНИЗАЦИЯ

ВЫЧИСЛЕНИЙ.

1.1. Актуальность задачи организации эффективных параллельных вычислений.

1.2. Универсальные многопроцессорные вычислительные системы с массовым параллелизмом и программируемой архитектурой

1.3. Структурнопроцедурная организация вычислений.

1.4. Отображение кадровой структуры задачи на архитектуру МВС ПА.

1.5. Анализ структуры задач различных классов и классификация информационных графов

1.6. Выводы
2. ПРЕОБРАЗОВАНИЕ ИНФОРМАЦИОННОГО ГРАФА В КАДРОВУЮ ФОРМУ И ОПЕРАЦИИ НАД КАДРОВЫМИ СТРУКТУРАМИ
2.1. Отношения в информационных графах.
2.2. Информационноэквивалентные операции в информационных
графах.
2.3. Преобразование информационных подграфов в кадровые формы.
2.4. Отношения и операции в кадровых структурах
2.4.1. Операция соединения
2.4.2. Операция Тсоединения.
2.4.3. Операция Тразъединения
2.4.4. Операция Оразъединения
2.5. Формирование проблемноориентированных и специализированных макроопераций для их аппаратной реализации в макропроцессоре
2.6. Методы формирования структур данных и процедур параллельного бесконфликтного обращения к данным в каналах памяти многопроцессорной системы с программируемой архитектурой. ИЗ
2.7. Выводы
3. ЭФФЕКТИВНЫЕ КАДРОВЫЕ ФОРМЫ ФУНКЦИОНАЛЬНОРЕГУЛЯРНЫХ ЗАДАЧ
3.1. Общие принципы преобразования в структурнопроцедурную
форму функциональнорегулярных подграфов.
3.2. Структурнопроцедурная реализация задачи математической физики
3.3. Структурнопроцедурная реализация процедуры быстрого преобразования Фурье
3.4. Выводы
4. ПРЕОБРАЗОВАНИЕ В КАДРОВУЮ ФОРМУ ФУНКЦИОНАЛЬНО НЕРЕГУЛЯРНЫХ ЗАДАЧ.
4.1. Методы преобразования функциональнонерегулярных задач в структурнопроцедурную форму
4.2. Структурнопроцедурная реализация процедуры решения систем линейных уравнений
4.3. Структурнопроцедурная реализация волновой
трассировки
4.4. Структурнопроцедурная организация вычислений в задаче кластерной группировки данных.
4.5.Вывод ы
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Методы организации вычислений на МВС должны также обеспечить оперативность создания эффекгивных параллельных программ и сделать процесс программирования на многопроцессорной системе сопоставимым по сложности с программированием однопроцессорных ЭВМ. В настоящее время наиболее распространены универсальные МВС с массовым параллелизмом. Эти МВС используют мул ьти процедурную, организацию вычислений //. При мультипроцедурной организации распараллеливание осуществляется по элементам структуры данных, и в каждом процессоре обработка ведется по независимой последовательной программе. Программа и данные каждого процессора хранятся в его локальной памяти. Для обмена данными между процессорами в системе организуются специальные процедуры. Вычислительный процесс описывается совокупностью асинхронно выполняемых последовательных программ и процедурами обмена данными. Примерами современных многопроцессорных систем, в которых реализован данный принцип вычислений, являются системы IBM-SP1/SP2; Parsytec GC; Cray ТЗЕ; ASCI White, ASCI Red, ASCI Blue-Pacific SST. В // представлен ежегодный отчет, посвященный последним’ разработкам в области многопроцессорных вычислительных систем, и, в частности, в области многопроцессорных систем с массовым параллелизмом. В отчете отмечается, что класс MIMD компьютеров с распределенной памятью (DM-MIMD) является самым быстрорастущим в семействе высокопроизводительных суперкомпьютеров, хотя этот тип суперкомпьютеров гораздо более труден в обращении, чем системы с общей памятью (shared memory MIMD). Последним типом машин являются системы, содержащие массив процессорных элементов. Структуры данных, являющихся кандидатами на* распараллеливание: векторы и многомерные массивы данных, выделяются автоматически с помощью системных программных средств, в то время как для систем с общей памятью распределение данных является прерогативой пользователя. Для MIMD-систем с распределенной памятью, где пользователь должен распределить данные по процессорам и обмен данными между процессорами должен быть явно определен, подобную операцию очень трудно выполнить. MIMD-системы с распределенной памятью имеют определенное преимущество по сравнению с параллельными системами других классов:' снимается проблема коммуникаций, поскольку пропускная способность в этих системах автоматически масштабируется с ростом числа процессоров. ЭМ-МТМО-систем. Однако, как отмечают авторы доклада //, системы ЭМ-М1МО имеют* ряд недостатков. Обмен между процессорами гораздо более медленный, чем в системах с общей памятью, и поэтому время на выполнение процедур синхронизации при решении задач, требующих большого количества межпроцессорных обменов, значительно превосходит аналогичные показатели для систем с общей памятью. Более того, доступ к данным, которые не находятся в локальной памяти какого-либо процессора, должен производиться через общую память. По сравнению с процедурой обращения к локальной памяти подобная процедура выполняется гораздо более медленно. Когда структура задачи диктует частые обмены данными между * процессорами или требует синхронизации работы многих процессоров, реальная производительность вычислительной системы составляет лишь малую часть от ее пиковой производительности. Распределение данных и операций по процессорам системы является нетривиальной задачей. Как правило, существующие методы параллельных вычислений ориентированы на определенную архитектуру вычислительных систем и направлены на то, чтобы попытаться отобразить вычислительный алгоритм на структуру вычислительной системы, как можно более равномерно распределить задания по процессорам системы, распределить данные по • локальным устройствам оперативной памяти и минимизировать количество процедур обмена данными. При разработке программ для МВС с мультипроцедурным распараллеливанием исходной формой представления задачи является последовательный алгоритм, который распараллеливается по множеству локально-независимых участков. Высокая реальная производительность систем с мультипроцедурной организацией вычислений достигается при условии, что время обработки информации существенно превышает время выполнения процедур обмена данными.