Автоматизация распараллеливания алгоритмов функционирования многопроцессорных систем

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

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

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

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

1.2. Методы, используемые при планировании программного обеспечения многопроцессорных систем
1.3. Анализ и синтез параллельного программного обеспечения. Преимущества графового метода и метода ветвей и границ
1.4. Выводы

2. МОДЕЛЬ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА

2.1. Представление вычислительного алгоритма в виде решетчатого орграфа.

2.2. Модель параллельного вычислительного процесса.

2.3. Определение временных характеристик исследуемого алгоритма

2.4. Формализация оптимизационных критериев
2.5. Выводы
3. МЕТОДИКА ОПТИМАЛЬНОГО РАСПАРАЛЛЕЛИВАНИЯ АЛГОРИТМА ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ.
3.1. Сегментация алгоритма.
3.2. Распараллеливание алгоритма на основе системы ордеров.
3.3. Распараллеливание линейных алгоритмов на основе целочисленного линейного программирования.
3.4. Получение исходных данных о структуре и основных параметрах алгоритма
3.5. Исследование точности получаемых результатов
3.6. Выводы
4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДИК АНАЛИЗА И СИНТЕЗА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ.
4.1. Программный комплекс для автоматического распараллеливания алгоритмов
4.2. Пример синтеза программного обеспечения спецвычислителя.
4.3. Исследование точности полученных результатов и проведение практического эксперимента
4.4. Исследование времени поиска оптимального решения
4.5. Исследование эффективности распараллеливания при использовании разработанного подхода
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Но в определенные моменты времени, обусловленные алгоритмом вычисления, процессоры должны синхронизировать свои действия []. По типам процессоров многопроцессорные системы могут быть разделены на однородные и неоднородные: однородные содержат однотипные процессоры, неоднородные состоят из различных специализированных процессоров [, ]. Примером может служить система, содержащая центральный процессор и процессор ввода-вывода []. Специализированный процессор выполняет операции строго определенного класса, в связи с этим задача распараллеливания в неоднородных системах обычно сводится к распределению операций между процессорами в соответствии с их классами. В однородных системах любая операция может быть выполнена на любом из имеющихся процессоров, поэтому задача распараллеливания в однородных системах достаточно трудоемка. По количеству уровней многопроцессорные системы могут делиться на одноуровневые и иерархические (многоуровневые). В первом случае процессоры системы образуют один общий уровень обработки данных, во втором (рис. Обычно менее мощный процессор выполняет ввод-вывод информации с различных терминалов и ее предварительную обработку. Рис. Одноуровневые многопроцессорные системы могут быть классифицированы по типу связи процессоров с оперативной памятью данных. С общей (равнодоступной) памятью данных. С индивидуальной (раздельной) памятью данных. С индивидуальной основной и общей вспомогательной оперативной памятью данных. Наиболее распространенными представителями многопроцессорных систем с общей модульной оперативной памятью данных является общая магистральная архитектура (рис. Организация межпроцессорных связей на основе общей магистрали является одним из распространенных способов построения многопроцессорных систем. Такая система является наиболее простой, дешевой и легко наращиваемой. Рис. В соответствии с данной структурой строятся универсальные микро-ЭВМ, в частности, компьютеры типа 1ВМ РС [,]. Одновременно через общую магистраль информация передается между двумя устройствами, то есть магистраль используется подключенными к ней устройствами в режиме разделения времени. Это является причиной возникновения конфликтов, при которых несколько устройств одновременно претендуют на занятие магистрали, что вызывает простой оборудования и уменьшает производительность системы. Поэтому при анализе и проектировании подобных систем следует учитывать затраты времени на ожидание процессорами освобождения магистрали. Многопроцессорная система с индивидуальной (раздельной) памятью данных является эффективной для решения класса задач, где имеются четко разделимые подмножества данных, размещаемых в соответствующих модулях памяти. Структурная схема такой системы приведена на рис. Каждый процессор обращается к своему модулю оперативной памяти. В связи с этим учет затрат времени на межпроцессорный обмен ведется на основе объема передаваемых данных. Рис. Частным случаем подобного класса систем является многопроцессорная система с матричной структурой, которая представлена на рис. Рис. Каналы связи организованы по принципу близкодействия: жесткие связи между собой имеют только соседние процессоры, а между отдаленными процессорами каналы связи отсутствуют. Обмен информацией между ними возможен только через цепочку процессоров. Данная структура характерна для ЭВМ, построенных на базе транспьютеров []. Для организации связи с другими транспьютерами, каждый транспьютер имеет несколько последовательных двунаправленных канала связи (линков). Благодаря прямому доступу к памяти обмен данными по каналам связи может осуществляться одновременно с работой остальных устройств транспьютера. Современные сигнальные процессоры, предназначенные для цифровой обработки сигналов, например ADSP0 фирмы Analog Devices также оснащаются линками для объединения их в матричную схему [, ]. Многопроцессорная система с индивидуальной основной и общей вспомогательной оперативной памятью данных является эффективной для многопрограммной работы с коллективным использованием большого архива базовых данных. Ее схема изображена на рис. Рис.