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

• Автор: Талалаев, Александр Анатольевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Переславль-Залесский
• Количество страниц: 112 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА I. ОБЗОР ТЕХНОЛОГИЙ ОРГАНИЗАЦИИ
ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ
1.1. Обзор аппаратных платформ
1.2. Обзор программных библиотек поддержки высокопроизводительных
ВЫЧИСЛЕНИЙ НА МВУ
1.3. Обзор программно-инструментальных средств для организации вычислений
наМВС
1.4. Сравнение основных характеристик программно-инструментальных
комплексов
1.5. Выводы И ПОСТАНОВКА ЗАДАЧИ
ГЛАВА 2. ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ КОМПЛЕКСА ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ
2.1. Общая архитектура программного комплекса
2.2. Структурная модель ядра программного комплекса
2.3. Модель системы диспетчеризации
2.4. Модель представления прикладной задачи
2.5. Пользовательский интерфейс системы
2.6. Принципы расширения функциональных возможностей ПС для решения
прикладных задач
2.7. Основные выводы
ГЛАВА 3. РАЗРАБОТКА И ИССЛЕДОВАНИЕ СИСТЕМЫ ДИСПЕТЧЕРИЗАЦИИ И МОДЕЛИ ВЫЧИСЛИТЕЛЯ
3.1. Разработка и исследование системы диспетчеризации
3.2. Разработка, и исследование модели вычислителей
3.3. Основные выводы
ГЛАВА 4. РЕАЛИЗАЦИЯ ПРИКЛАДНЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ И ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ КОМПЛЕКСА
4.1. Библиотека модулей для решения прикладных задач
4.2. Тестирование на задаче поиска и распознавания объектов
4.3. Тестирование на задаче обработки изображений ДЗЗ
4.4. Тестирование на задаче контроля и диагностики подсистем КА
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Введение
При решении сложных прикладных задач, оперирующими большими объемами данных, возникает необходимость максимально эффективно использовать аппаратные ресурсы современной компьютерной техники, например, многопроцессорных вычислительных систем (МВС). Задача разработки параллельных алгоритмов для повышения эффективности вычислений может быть сравнима по сложности с решением самой прикладной задачи.
Для разработки прикладных систем необходим удобный инструмент, обладающий достаточной гибкостью и расширяемостью, обеспечивающий масштабируемое решение прикладной задачи и при этом не обременяющий разработчика вопросами эффективной параллельной реализации. При этом инструментальная система не должна ограничивать разработчика, позволяя ему при необходимости применять имеющиеся знания и расширять функциональные возможности системы. Подобная система должна также функционировать на различных аппаратных платформах или иметь возможность легкой адаптации под них, позволяя разработчику полностью сконцентрироваться на решении прикладной задачи и в короткие сроки, без привлечения высококвалифицированных специалистов в области параллельных вычислений, построить законченное решение, обеспечивающее преимущество от использования МВС.
В настоящее время имеется несколько универсальных систем, которые можно рассматривать как комплекс инструментальных средств для разработки прикладных систем. К ним можно отнести такие системы как: HeNCE, GRADE, CODE, Triana, технологию Microsoft Workflow Foundation, ANSYS EKM, Kepler.
Однако тщательный анализ показывает, что каждая из них, обладая определенными преимуществами, тем не менее, по ряду причин не позволяет достаточно простыми средствами достигать одновременно требуемых показателей по скорости обработки, гибкости, масштабируемости вычислений, возможности адаптации к прикладной области и т.д.
Вопросами организации высокопроизводительных вычислений занимались различные исследователи: Е. Валях [1], Прангишвили И.В. [2] и Трахтенгерц Э.А. [3,4] (распараллеливание в процессе трансляции), Гергель В.П. [5,6], Воеводин В.В. [7,8], Карцев М.А. [9], Абрамов С.М. [10-12] (динамическое распараллеливание T-система) и др.

В рамках многих из этих работ построены специальные языки и программные средства для параллельного программирования. Однако большинство существующих в настоящий момент решений для организации высокопроизводительных вычислений либо представляют собой низкоуровневые библиотеки или языки программирования, требующие от разработчика глубокого понимания парадигм параллельного программирования, либо не обладают достаточной гибкостью и, как правило, адаптированы лишь под конкретную аппаратную платформу.
Предлагаемое в рамках диссертационной работы алгоритмическое и программное обеспечение направлено на создание программно-инструментальной среды, позволяющей при разработке прикладных систем абстрагироваться от деталей низкоуровневой реализации параллельных алгоритмов. Основной целью работы является обеспечение достаточно высоких показателей алгоритмов конвейерно-параллельных вычислений по быстродействию при минимальных временных затратах на их разработку с использованием инструментальных средств. При этом учитывается возможность кроссплатформенной реализации с сохранением принципов универсализма, гибкости и расширяемости программного комплекса.
Целью диссертационной работы является разработка и исследование моделей, алгоритмов и программно-инструментальных средств, предназначенных для организации конвейерно-параллельных вычислений на мультипроцессорных системах. Для достижения поставленной цели в работе решаются следующие задачи:
1. Исследование существующих методов организации конвейернопараллельных вычислений на мультипроцессорных вычислительных системах;
2. Разработка структурной модели комплекса инструментальных средств, удовлетворяющей принципам гибкости и расширяемости и позволяющей адаптировать разрабатываемое ПО к ряду аппаратных архитектур;
3. Разработка алгоритма диспетчеризации, позволяющего эффективно использовать ресурсы МВС с учетом требований универсализма разрабатываемых инструментальных средств и наложенных постановкой задачи ограничений;
4. Разработка математического и программного обеспечения МВС для решения задач конвейерно-параллельной обработки данных и проведение

о завершении обработки того или иного пакета данных или создании нового ресурса подлежащего обработке, переводят систему в новое состояние.
В ходе работы системы могут возникать ситуации, в которых запуск модуля невозможен в текущий момент времени, управляющие команды при этом буферизуются системой диспетчеризации (их выполнение откладывается) до момента, когда необходимые ресурсы будут доступны.
Предложенный подход, к диспетчеризации работы, основанный на «жадном» алгоритме локально оптимального выбора применимых команд, несмотря на его простоту, является достаточно эффективным решением, позволяющим задать ограничения на количество используемых аппаратных ресурсов МВС. Говоря об аналогичных системах, следует указать, что используемые в них принципы диспетчеризации, по мнению автора, уступают предложенному. Система CODE не имеет диспетчера нагрузки, поскольку является, по своей сути, системой кодогенерации. Технология Microsoft Workflow Foundation использует принцип очереди заданий без приоритетов, последовательно запуская компоненты входящие в схему решения задачи в рамках одного потока исполнения, однако, позволяет задать пул потоков для исполнения, либо реализовать многопоточный сервис, что может обеспечить параллелизм, но требует от прикладного программиста большей квалификации. Система Kepler, в конвейернопараллельном режиме работы, исполняет каждый модуль входящий в схему решения задачи в независимом потоке, что при увеличении сложности решаемых прикладных задач (включающих большое количество модулей) приведет к излишним затратам вызванным конкуренцией потоков.
Принцип работы системы диспетчеризации может быть представлен в виде конечного автомата (рисунок 10), описывающего основные состояния работы системы диспетчеризации, и может быть формально определен как S = (Q, X, 5, qo, F) где:
Q= {Start, Init, Update, Select, Apply, Wait, End} - конечное множество состояний автомата, описывающих фазы функционирования диспетчера задач;
Х= {I, CMD_SENDED, EVENT_RECEIVED, CMD_SELECTED, NO_APPLICABLE_C MDS, CMDS_NOT_AVAILABLE} - входной алфавит КА, указанные входные символы подаются на вход КА после вычисления предикатов, оценивающих внутреннее состояние системы диспетчеризации (описываемое таблицами занятости вычислителей, списками доступных и применяемых в настоящий момент команд)
• X - лямбда-переход, оценка внутреннего состояния системы диспетчеризации не производится;