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

  • автор:
  • специальность ВАК РФ: 05.13.11
  • научная степень: Кандидатская
  • год защиты: 2001
  • место защиты: Москва
  • количество страниц: 157 с. : ил
  • стоимость: 230 руб.
  • нашли дешевле: сделаем скидку

действует скидка от количества
2 работы по 214 руб.
3, 4 работы по 207 руб.
5, 6 работ по 196 руб.
7 и более работ по 184 руб.
Титульный лист Исследование динамических характеристик программ на масштабируемых ресурсах
Оглавление Исследование динамических характеристик программ на масштабируемых ресурсах
Содержание Исследование динамических характеристик программ на масштабируемых ресурсах
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления
ОГЛАВЛЕНИЕ
Введение.
Глава 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. Рис. Списочное планирование (рис. В противном случае операция сдвигается на следующий шаг. Когда все операции на текущем шаге спланированы, осуществляется переход к следующему шагу. Этот способ планирования аналогичен использованию метода ветвей и границ при оптимизации микрокода в горизонтальном микропрограммировании []. Критерии планирования, назначения и привязки зависят от того, в какой связи или независимо рассматриваются соответствующие задачи. Так, при заданных ограничениях на ресурсы цель планирования минимизировать длину расписания (число тактов) [, ]. При ограничении на длину расписания, цель планирования - минимизировать уровень использования ресурсов [, ]. Ряд работ посвящен поиску верхней [] и нижней границ [] диапазона, в котором находится расписание минимальной длины. В первой из упомянутых работ предлагается эвристика для оценки верхней границы, во второй - алгоритм целочисленного линейного программирования (ЦЛП) для отыскания нижней границы диапазона. В большинстве алгоритмов назначения единственный критерий -минимизация уровня использования ресурсов. При этом назначение выполняется чаще всего отдельно для модулей, памяти и связующих элементов. Итак, задача планирования в высокоуровневом синтезе может быть поставлена в терминах основной модели составления детерминированного расписания. Алгоритмы планирования можно разделить на два основных класса -преобразовательные и итеративные [, ]. Алгоритмы первого типа используют некоторый изначально заданный план, который представляет либо максимально распараллеленные операции, либо последовательное их исполнение. Затем преобразованиями стремятся последовательно выполняемые операции реализовать параллельно и, с учетом ограничений на ресурсы, часть параллельно выполняемых операций реализовать последовательно. Для сокращения перебора используют методы ветвей и границ, эвристики для управления процессом преобразований. Подобный подход использован в [, , ]. Итеративные алгоритмы планируют операции, последовательно добавляя к множеству уже спланированных операций по одной, и различаются тем, какая операция выбирается следующей и как она планируется.
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления

Рекомендуемые диссертации данного раздела