Топоркова Анна Станиславовна. Исследование динамических характеристик программ на масштабируемых ресурсах

brief description

Топоркова Анна Станиславовна. Исследование динамических характеристик программ на масштабируемых ресурсах : диссертация ... кандидата технических наук : 05.13.11.- Москва, 2001.- 157 с.: ил. РГБ ОД, 61 02-5/891-9

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
На правах рукописи
ТОПОРКОВА АННА СТАНИСЛАВОВНА
ИССЛЕДОВАНИЕ ДИНАМИЧЕСКИХ ХАРАКТЕРИСТИК
ПРОГРАММ НА МАСШТАБИРУЕМЫХ РЕСУРСАХ
Специальность 05.13 Л1 Математическое и программное
обеспечение вычислительных машин, комплексов и компьютерных сетей
Диссертация на соискание ученой степени
кандидата технических наук
Научный руководитель доктор технических наук, профессор В.А. Кравченко

Москва - 2001 
Введение 4
Глава 1. Модели упорядочения и проблема масштабирования ресурсов для оптимизации динамики программ 7
1.1. Конфигурация вычислительной среды и планирование процессов 7
1.1.1. Априорное и динамическое планирование 7
1.1.2. Выявление структуры ресурсов при фиксированных
свойствах операций 8
1.1.3. Планирование с преобразованием отношения
предшествования 15
1.1.4. Циклическое планирование 19
1.1.5. Динамическое конфигурирование ресурсов 21
1.2. Общая модель упорядочения для детерминированных
расписаний и ее ограничения 21
1.3. Модели упорядочения с произвольными параметрами 28
1.4. Постановка задачи оптимизации выполнения программ
на масштабируемых ресурсах 30
1.5. Выводы по главе 1 34
Глава 2. Основные компоненты модели планирования и
назначения процессов программных приложений на
масштабируемых ресурсах .36
2.1. Условия допустимости масштаба процессов 36
2.2. Масштабируемые вычислительные ресурсы 38
2.3. Модель обработки 39
2.4. Ограничения при масштабировании процессов 44
2.5. Критерии масштабирования 45
2.6. Ключевые понятия в алгоритмах масштабирования 49
2.7. Методы динамического программирования и
алгоритмы масштабирования 57
2.8. Выводы по главе 2 62
Глава 3. Алгоритмы оптимизации динамики программ в масштабируемой среде 63
3.1. Алгоритмы масштабирования критических задач по частному
критерию 63
3.2. Алгоритмы поиска оптимальной стратегии выполнения программы
на масштабируемых ресурсах 75
3.3. Арбитраж конфликтов между конкурирующими процессами 89
3.4. Сложность алгоритмов и побочные эффекты оптимизации
характеристик программ для масштабируемой среды 94
3.5. Выводы по главе 3 99
Глава 4. Статико-динамический анализ программ и
тестирование алгоритмов масштабирования 101
4.1. Методика статико-динамического анализа априорных
характеристик программ 101
4.1.1. Задача статико-динамического анализа 101
4.1.2. Фрагментация кода программы 102
4.1.3. Оценка длительности и сложности выполнения фрагмента.... 103
4.1.4. Алгоритмы фрагментации и оценки сложности
в особых случаях 104
4.2. Экспериментальное исследование эффекта избыточности
стратегий и неоднозначности назначения процессов 110
4.3. Эвристики для снижения избыточности оптимальных стратегий.... 118
4.4. Особенности программной реализации алгоритмов арбитража 125
4.5. Выводы по главе 4 ...131
Заключение 132
Список литературы 134
Приложение 1. Тестирование алгоритмов масштабирования
П1.1. Текст программы тестового примера -
синтаксического анализатора ...143
П1.2. Входной файл программы масштабирования (data_sc 1 .txt) 146
П1.3. Входной файл программы арбитража конфликтов (Bdip_m.inp)...146
П1.4. Файл с описанием процессов программы (fl .net) 147
П1.5. Хранилище вариантов масштабирования 148
Приложение 2. Акты об использовании и реализации результатов диссертационной работы 152

bibliography

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