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

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

ОГЛАВЛЕНИЕ
Введение.
Глава 1. Модели упорядочения и проблема масштабирования ресурсов для оптимизации динамики программ

1.1. Конфигурация вычислительной среды и планирование процессов

1.1.1. Априорное и динамическое планирование

1.1.2. Выявление структуры ресурсов при фиксированных свойствах операций.

1.1.3. Планирование с преобразованием отношения предшествования.

1.1.4. Циклическое планирование.

1.1.5. Динамическое конфигурирование ресурсов.

1.2. Общая модель упорядочения для детерминированных расписаний и ее ограничения.

1.3. Модели упорядочения с произвольными параметрами.

1.4. Постановка задачи оптимизации выполнения программ
на масштабируемых ресурсах
1.5. Выводы по главе 1.
Глава 2. Основные компоненты модели планирования и
назначения процессов программных приложений на
масштабируемых ресурсах.
2.1. Условия допустимости масштаба процессов
2.2. Масштабируемые вычислительные ресурсы
2.3. Модель обработки.
2.4. Ограничения при масштабировании процессов
2.5. Критерии масштабирования.
2.6. Ключевые понятия в алгоритмах масштабирования
2.7. Методы динамического программирования и
алгоритмы масштабирования.
2.8. Выводы по главе 2
Глава 3. Алгоритмы оптимизации динамики программ в масштабируемой среде.
3.1. Алгоритмы масштабирования критических задач по частному критерию.
3.2. Алгоритмы поиска оптимальной стратегии выполнения программы на масштабируемых ресурсах..
3.3. Арбитраж конфликтов между конкурирующими процессами
3.4. Сложность алгоритмов и побочные эффекты оптимизации характеристик программ для масштабируемой среды
3.5. Выводы по главе 3
Глава 4. Статикодинамический анализ программ и
тестирование алгоритмов масштабирования
4.1. Методика статикодинамического анализа априорных характеристик программ
4.1.1. Задача статикодинамического анализа.
4.1.2. Фрагментация кода программы
4.1.3. Оценка длительности и сложности выполнения фрагмента
4.1.4. Алгоритмы фрагментации и оценки сложности
в особых случаях.
4.2. Экспериментальное исследование эффекта избыточности стратегий и неоднозначности назначения процессов
4.3. Эвристики для снижения избыточности оптимальных стратегий
4.4. Особенности программной реализации алгоритмов арбитража
4.5. Выводы по главе 4
Заключение.
Список литературы


При необходимости учитывается вес операции, зависящий от ее типа: так, в системах цифровой обработки сигналов, как правило, стремятся уменьшить число умножений []. Ограничения на свойства архитектуры определяются ресурсами (модулями, памятью, мультиплексорами), количеством их экземпляров, возможностью исполнения той или иной операции на соответствующем типе ресурса, задержкой выполнения и видом графовой модели. В этом смысле отношение предшествования может считаться произвольным параметром. Другие, наоборот, учитывают эту специфику. В частности, в работе [] предлагается алгоритм планирования на графе потоков данных с вложенными условными ветвлениями. Особенности организации потоков данных в некоторых задачах позволяют ввести специальный вид конфликтных графов и графов совместимости операций []. Задачи раскраски конфликтных графов и выделения клик в графах совместимости общего вида являются NP-полными. Хордовые графы допускают минимальную раскраску, а графы сравнимости выделение клик, за полиномиальное время, что позволяет их эффективно применять для построения алгоритмов назначения []. Ограничения на классы алгоритмов определяются тесной взаимосвязью планирования, привязки и назначения. При планировании в высокоуровневом синтезе не рассматриваются назначения с прерываниями и задержкой. Примером произвольного выбора операций из числа готовых к исполнению может служить простейший тип планирования - "как можно скорее" ("as soon as possible’VASAP) или "как можно позже" ("as late as possible"/ALAP). В алгоритмах ASAP предполагается, что число компонентов и их реализация уже определены. Положим, для примера на рис. Возможное планирование ASAP приведено на рис. Недостаток алгоритмов этого типа - отсутствие приоритета в планировании операций критического пути: операция 1 планируется раньше операции 2, принадлежащей критическому пути 2-5-6. Этот же недостаток присущ и алгоритмам ALAP. Рис. Списочное планирование (рис. В противном случае операция сдвигается на следующий шаг. Когда все операции на текущем шаге спланированы, осуществляется переход к следующему шагу. Этот способ планирования аналогичен использованию метода ветвей и границ при оптимизации микрокода в горизонтальном микропрограммировании []. Критерии планирования, назначения и привязки зависят от того, в какой связи или независимо рассматриваются соответствующие задачи. Так, при заданных ограничениях на ресурсы цель планирования минимизировать длину расписания (число тактов) [, ]. При ограничении на длину расписания, цель планирования - минимизировать уровень использования ресурсов [, ]. Ряд работ посвящен поиску верхней [] и нижней границ [] диапазона, в котором находится расписание минимальной длины. В первой из упомянутых работ предлагается эвристика для оценки верхней границы, во второй - алгоритм целочисленного линейного программирования (ЦЛП) для отыскания нижней границы диапазона. В большинстве алгоритмов назначения единственный критерий -минимизация уровня использования ресурсов. При этом назначение выполняется чаще всего отдельно для модулей, памяти и связующих элементов. Итак, задача планирования в высокоуровневом синтезе может быть поставлена в терминах основной модели составления детерминированного расписания. Алгоритмы планирования можно разделить на два основных класса -преобразовательные и итеративные [, ]. Алгоритмы первого типа используют некоторый изначально заданный план, который представляет либо максимально распараллеленные операции, либо последовательное их исполнение. Затем преобразованиями стремятся последовательно выполняемые операции реализовать параллельно и, с учетом ограничений на ресурсы, часть параллельно выполняемых операций реализовать последовательно. Для сокращения перебора используют методы ветвей и границ, эвристики для управления процессом преобразований. Подобный подход использован в [, , ]. Итеративные алгоритмы планируют операции, последовательно добавляя к множеству уже спланированных операций по одной, и различаются тем, какая операция выбирается следующей и как она планируется.