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

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

ОГЛАВЛЕНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1. АНАЛИЗ ПРОБЛЕМЫ ОРГАНИЗАЦИИ МОБИЛЬНЫХ ПАРАЛ ЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

1.1. Анализ существующих языков и систем параллельного программиро вания

1.2. Анализ существующих систем автоматического и полуавтоматическо го распараллеливания последовательных профамм

1.3. Анализ формальных моделей данных, алгоритмов и профамм

1.3.1. Модель алгоритма

1.3.2. Модель профаммы

1.4. Анализ существующих алгоритмов и методов распараллеливания по следовательных профамм
1.4.1. Методы и алгоритмы, используемые на стадии анализа иоследова тельной программы
1.4.2. Методы и алгоритмы, используемые на стадии синтеза параллель ной версии профаммы
1.5. Анализ существующих способов организации мобильных вычислений
1.5.1. Достижение переносимости па уровне ЯВУ
1.5.2. Переносимость в пределах заданной ОС
1.5.3. Архитектура ВС и обеспечение переносимости ПО
1.5.4. Использование промежуточного представления и абстрактной вы числительной машины
2. модель параллельного промежуточного коде И
АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ИСХОДНЫХ ТЕКСТОВ
ПОСЛЕДОВАТЕЛЬНЫХ программ в промежуточный код
2.1. Модель типов данных
2.1.1. Элементарный тип данных
2.1.2. Составной тип данных
2.2. Модель операций
2.2.1. Семантика операций над данными
2.2.2. Семантика управляющих операций
2.3. Модель параллельного промежуточного представления
2.3.1. Разработка алгоритма исключения оператора из профаммы
2.3.2. Разработка алгоритма исключения оператора i из профам мы
2.3.3. Разработка алгоритма выделения регионов на основе управляю щей структуры профаммы
2.4. Модель параллельного промежуточного кода
2.4.1. Выявление параллелизма между регионами параллельного про 1 межуточного кода

3. СИНТЕЗ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ 7 ПАРАЛЛЕЛЬНОГО ПРОМЕЖУТОЧНОГО КОДА
3.1. Модель операционной системы как среды функционирования парал 8 дельных процессов
3.1.1. Алгебраическая модель подсистемы управления процессами ОС
3.1.2. Автоматная сеть как модель параллельного вычислительного про 2 цесса
3.2. Статический синтез параллельной реализации последовательной про 6 граммы для мультипроцессорной вычислительной системы с общей памятью
3.2.1. Разработка алгоритма статического синтеза параллельной про 1 граммы
3.2.2. Разработка алгоритма отображения параллельной программы на 5 модель операционной среды
3.2.3. Уточнение длительности исполнения параллельных регионов про 7 граммы в условиях неопределенности
3.2.4. Расчет величины уточняющей задержки на основе иредваритель 9 ных статистических испытаний
3.3. Динамический синтез параллельной реализации последовательной про 4 граммы для мультипроцессорной вычислительной системы с общей памятью
3.3.1. Использование метода спекулятивной многопоточности 5 для динамического распараллеливания последовательных программ
3.3.2. Расчет характеристик использования метода спекулятивной мно 3 гопогочности для динамического распараллеливания циклов
3.3.3. Выделение спекулятивных регионов и эпох на основе параллель 8 ного промежуточного кода
4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ 4 АЛГОРИТМОВ
4.1. Экспериментальное исследование характеристик разработанных алго 4 ритмов
4.1.1. Экспериментальное исследование алгоритма исключения опера 5 тора Ьгеак
4.1.2. Исследование алгоритма исключения оператора i
4.1.3. Экспериментальное исследование алгоритма выделения регионов
4.1.4. Экспериментальное исследование алгоритма статического синтеза 0 параллельной программы
4.2. Области практического применения полученных результатов
4.2.1. Программные средства поддержки этапа преобразования последо
вательных программ в мобильный параллельный промежуточный код
4.2.2. Программные средства поддержки этапа исполнения параллель 3 ного промежуточного кода
4.3. Результата внедрения
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Рязань, а также представляют часть НИР 7 Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе соврс менной вычислительной базы, ПИР Модели, методы, инструментальные средства и научнометодическое обеспечение процесса проектирования параллельных систем с использованием СА8Етехнологии, выполненных в Рязанском государственном радиотехническом университете. Структура и объем диссертации. Диссертация состоит из введения, че . В приложении на 3 страницах приведены акты внедрения результатов и свидетельство о регистрации программы для ЭВМ. Основная задача параллельного программирования сокращение времени выполнения программы путем повышения степени загрузки всех функциональных узлов реализующей е параллельной ВС. Практика же последовательного программирования, исторически предшествовавшая возникновению параллельных вычислений, ставила две противоречивые задачи оптимальную реализацию вычислительного алгоритма с точки зрения минимизации времени е выполнения и экономии использования памяти. Достигалось это путм обеспечения максимальной связности с сильной зависимостью отдельных частей операторов, переменных программы посредством общей памяти. Для этого требовалось организовывать вычисления по возможности в одном цикле, использовать минимальное число переменных величин в программе и т. Подобный подход потенциально противоречит задачам параллельного программирования, так как минимизация времени выполнения программы может быть достигнута только за счет дополнительного расхода памяти. Следовательно, необходимо организовывать независимые вычисления в независимых циклах, использовать для всех независимых результатов разные переменные, т. Особенности последовательного программирования сделали невозможным непосредственное использование наработанного за долгие годы ПО и алгоритмов в рамках ВС, построенных на базе многоядерных процессоров. Кроме того, большое разнообразие архитектур и типов параллельных ВС, сильно отличающихся способами организации параллелизма и вычислительными возможностями, неизбежно требует учета этих специфических особенностей. Остро встат проблема переносимости параллельного ПО между различными тинами высокопроизводительных ВС. Специализированные же процессоры, например графические вРЦ, уже сейчас содержат сотни параллельно работающих вычислительных ядер. Для того, чтобы сделать выбор способа организации мобильных параллельных вычислений обоснованным, рассмотрим существующие подходы к решению вышеназванных проблем. Решение проблемы организации параллельного программирования лежит в области создания новых параллельных языков высокого уровня ЯВУ, либо в модификации наиболее популярных последовательных ЯВУ путм добавления параллельной парадигмы. Создание принципиально новых ЯВУ обычно оправдано лишь при невозможности использования модификаций ни одного из распространенных ЯВУ, например, для нетрадиционных архитектур ВС машина потока данных или при разработке проблемно ориентированных ЯВУ. Модификация последовательных ЯВУ производится на основе следующих подходов. Использование макрорасширений или специальных директив компилятору . Директивы макрорасширения позволяют специфицировать некоторые виды параллельности. Макрорасширения обычно оформляются в тексте программы в виде специальных комментариев и транслируются препроцессором в операторы языка с вызовами специальных подпрограмм, реализующих параллельную обработку. Пример подобного пакета макрорасширений пакет АоппеЮМВ разработанный в Аргоннской национальной лаборатории для языков Си и Фортран 1, а также О УМсистем а, созданная в Институте прикладной математики им. М.В. Келдыша РАН, с расширениями для языков Си и Фортран . Однако подобный подход не очень удобен при программировании на языке высокого уровня, так как исключает возможность своевременного контроля со стороны компилятора , а неявное добавление промежуточного кода осложняет отладку программ. Более удобным и естественным является подход, основанный на введении расширений непосредственно в язык. Одновременно это позволяет компилятору производить некоторые дополнительные виды оптимизации.