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

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

Оглавление
Введение

1 Планирование в системах динамического распараллеливания программ

1.1 Задача динамического планирования

1.2 Локальность исполнения.

1.3 Методы планирования

1.4 Автоматизированное динамическое распараллеливание программ .

1.4.1 I.
1.4.2 i
1.4.3 .
1.4.4
1.4.5 подход.
1.4.6 Программный комплекс .
2 Планирование исполнения параллельных программ
2.1 Модель процесса исполнения Тпрограммы
2.2 Жадные планы исполнения .
2.3 Модель с различной производительностью узлов.
2.4 Распределенное планирование
2.5 Балансирующий планировщик
2.6 Планировщик ii
2.6.1 Алгоритм планировщика ii
2.6.2 Выбор узла для запроса задачи
2.6.3 Выбор узла для запроса задачи в распределенной системе
2.7 Режим неблокирующего исполнения
ОГЛАВЛЕНИЕ
2.8 Выводы
3 Включение задач
3.1 Пример мелкозернистой программы.
3.2 Методы включения задач
3.2.1 Ленивое порождение задач
3.2.2 Ленивый НРС.
3.2.3 Метод включения, основанный на анализе загрузки
3.3 Механизмы включения задач в .
3.3.1 Корректность включения задач
3.4 Реализация включения задач в
3.4.1 Препроцессор
3.4.2 Включение задач
3.4.3 Корректное включение задач
3.4.4 Оптимизация включения задач.
3.4.5 Дальнейшая оптимизация .
3.4.6 Автоматический выбор гранулы параллелизма.
4 Программная реализация планировщиков
4.1 Очередь задач.
4.2 Интерфейс планировщика
4.3 Интерфейс модуля планирования
4.4 Реализация балансирующего планировщика.
4.5 Реализация планировщика ii
5 Практические испытания планировщиков
5.1 Тестовая программа ЕР
5.2 Программа ЕТ.
5.3 Программный комплекс Vx I
5.4 Модельная программа .
5.5 Зависимость от числа задач
5. Параметры планировщика ii.
5.7 Режим неблокирующего исполнения .
5.8 Испытания на неоднородной системе
5.9 Выводы.
ОГЛАВЛЕНИЕ
Заключение
Введение
Актуальность


Проблемы современных информационно-вычислительных систем» под руководством д. В. А. Васенина (два доклада в течении 0. По материалам диссертации опубликовано семь работ [, , , , , , ], две из которых — в журналах, рекомендованных ВАК. В работе [], опубликованной совместно с И. М. Коневым, автору настоящей диссертации принадлежат разделы «Введение», «Планирование исполнения программ» и «Включение задач». Работа состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации — 6 страниц. Список литературы включает наименований. В первой главе содержится краткий обзор существующих на настоящее время методов планирования в системах динамического распараллеливания программ, рассматриваются их преимущества и недостатки. Приведена постановка задачи динамического планирования в такого сорта системах. Описывается Т-подход — один из методов автоматизированного динамического распараллеливания приложений, и его программная реализация Иел/ГБ, как объект апробации предлагаемых автором решений. Анализируются особенности планирования исполнения программ в ранних версиях Ке\,гГ8. Во второй главе представлена разработанная автором математическая модель исполнения параллельных программ в системах динамического распараллеливании приложений и алгоритмы планирования в таких системах. Приводится модель исполнения программ на вы чистительной установке с общей памятью, а также расширения этой модели на установки с узлами различной мощности и на распределенные вычислительные комплексы. Доказывается эффективность исполнения программ в рамках построенных моделей. Описываются предложенные автором алгоритмы планирования. МеиТЭ. В третьей главе рассматриваются вопросы эффективного исполнения в мелкозернистых [] программ посредством использования метода включения задач, основанного на объединении нескольких задач в одну во время исполнения программы. Представлены и анализируются способы эффективного исполнения таких программ в других системах динамического распараллеливания. Описываются детали реализации метода включения задач в программном комплексе Ме\гТ8, а также шаги, предпринятые для ее оптимизации. Особое внимание уделяется вопросам корректности включения задач. В четвертой главе описываются детали реализации планировщиков Пе\гТЗ. Показаны особенности реализации очереди готовых к исполнению задач, взаимодействия планировщика и других модулей *те\гТ8. Пятая глава содержит результаты испытаний разработанных и реализованных автором планировщиков в составе >4е\*Т8 с использованием как тестовых, так и практически значимых прикладных программ. Испытания проводятся на однородном кластере с большим числом вычислительных узлов, а также на распределенной гетерогенной вычислительной системе. В заключении перечисляются основные результаты работы. В настоящее время для решения многих практически важных и вычислительно сложных задач применяются параллельные программы, исполняемые на многопроцессорных установках. Локальные, как правило, однородные и силыюсвязанные вычислительные кластеры, а также распределенные, в том числе гетерогенные вычислительные системы широко используются для запуска на них параллельных программ. Активное развитие многоядерных процессоров приводит к повсеместному применению средств параллельного программирования. В последние годы приобретают популярность вычислительные среды, построенные но архитектуре GRID ||. Такие среды характеризуются отсутствием централизованного управления, территориальной распределенностью и неоднородностью входящих в их состав вычислительных узлов. Создание параллельных программ, предназначенных для исполнения в среде GRID, должно производиться с учетом различной производительности, программно-аппаратной архитектуры вычислительных узлов и неоднородной коммуникационной сети. При разработке параллельных программ возникает ряд сложностей, таких как обеспечение синхронизации вычислительных узлов, распределение между ними данных и вычислительной нагрузки. Существует большое число средств, частично автоматизирующих разработку параллельных программ, например MPI, mpC.