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

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

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

1 Методы прогнозирования времени выполнения программ

1.1 Время как мера производительности

1.2 Подходы к оценке времени выполнения программы

1.3 Прогнозирование на множестве историй выполнения программы

1.4 Оценка времени выполнения линейного участка программы . .

1.5 Инструментальные средства оценки времени выполнения программ

2 Статикодинамический метод оценки времени выполнения программы

2.1 Общая задача оценки времени выполнения программы

2.2 Статикодинамический подход.

3 Решение задачи на классе последовательных вычислителей
3.1 Сведение задачи оценки времени к задаче о построении кода
минимальной длины.
3.2 Генерация оптимального кода для линейного участка
3.3 Модель последовательного вычислителя
3.3.1 Алгоритмы генерации кода и свойства программ, вычисляющих дерево выражения
3.3.2 Модель регистрового вычислителя
3.3.3 Модель стекового вычислителя .
3.3.4 Обощенная модель регистростекового вычислителя . .
3.4 Инструментальная система оценки времени для вычислителей
с регистростековой архитектурой
3.4.1 Описание архитектуры целевого вычислителя.
3.4.2 Структура инструментальной системы
3.4.3 Результаты тестирования системы.
4 Решение задачи на классе векторноконвейерных вычислителей
4.1 Особенности векторноконвейерных вычислителей.
4.2 Временные особенности выполнения векторных операций .
4.3 Свойства программ, выполняемых на векторноконвейерных вычислителях .
4.4 Модель векторноконвейерного вычислителя
4.5 Определение времени выполнения векторизуемых программ . .
4.5.1 Алгоритм динамического программирования на классе
векторных вычислителей
4.5.2 Алгоритм циклического планирования.
4.6 Формальное описание векторноконвейерного вычислителя . .
4.7 Инструментальная система прогнозирования времени для векторноконвейерных вычислителей.
5 Решение задачи на классе ШЭС вычислителей
5.1 Моделирование поведения конвейеров.
5.2 Моделирование поведения кэшпамяти.
5.2.1 Особенности кэшпамяти
5.2.2 Методы статического моделирования кэшпамяти
5.3 Средства описания архитектуры процессора.
5.4 Архитектура системы оценки времени для ШЭС процессоров .
Заключение
Приложения
I. Описание алгоритмов генерации кода
И. Разметка операторов языка Си
III. Параметрическое описание регистростскового вычислителя.
IV. Параметрическое описание вычислителя с ШЭС архитектурой
V. Пример статических предсказаний для ШБС вычислителей
Литература


В одной из них [9] при оценке времени программы учитываются также затраты на обработку некоторых прерываний. В другой работе [] предпринята попытка оценить влияние переключения контекстов на время выполнения программ в многозадачной среде. Предлагаемая в данной работе методика предназначена для оценки времени выполнения действий из программы пользователя. Следовательно, в данной работе прогнозироваться будет значение времени Ти5вг. Далее в этой главе будет сделан обзор методов оценки времени выполнения последовательных программ. Для оценки новых архитектурных решений и проверки правильности функционирования программного обеспечения необходимо знание динамических характеристик программ. Динамическими будем называть характеристики, проявляющиеся лишь на этапе выполнения программы. Долгое время для подобных пелей использовались такие методы, как наблюдение за выполнением программы, сбор и исследование трасс. Ранее мы пояснили, что наблюдение не всегда возможно. Исследование же трасс подразумевает обработку огромного объема информации, что также не всегда приемлемо. А это может быть или слишком дорого (например, для сложных '’параллельных'’ вычислительных систем), или практически недоступно (при наличии только проекта архитектуры). В силу указанных выше особенностей становится актуальной задача разработки методики прогнозирования времени выполнения программ на различных вычислительных системах. В данной работе мы будем рассматривать задачу прогнозирования времени только для однопроцессорных вычислителей, допускающих внутренний параллелизм при работе устройств процессора. Таким образом мы не касаемся систем, традиционно называемых ’’параллельными”. Под внутренним параллелизмом понимаем такие особенности современных вычислителей, как наличие конвейеров и множественность функциональных устройств. Оцениваться будут последовательные программы (или последовательные фрагменты вычислений). Рассмотрим, из каких составляющих может складываться время выполнения программы, и уточним, какие из них могут быть предсказаны предлагаемой в данной работе методикой. Определение. Назовем рабочей нагрузкой вычислительной системы совокупность всей входной информации (программ, данных, команд), поступающих в систему извне [1]. Сегодня стало особенно актуально иметь методику получения данных о выполнении программы на различных вычислителях, используя лишь описание этих вычислителей. При этом одной из наиболее сложных и еще недостаточно исследованных задач является проблема прогнозирования времени выполнения программ. Первыми работами, посвященными проблеме прогнозирования времени по описанию архитектуры вычислителя можно, по-видимому, считать две публикации, появившиеся в году [, ]. До последнего времени существует незначительного количество научных работ и исследовательских групп, занятых разработкой методик прогнозирования. Большинство из них уделяют внимание исключительно процессорам с Ш8С архитектурой и решают поставленную задачу методами статической имитации. Определение. Статической имитацией мы будем называть такой метод анализа программы, который позволяет без эмуляции выполнения действий программы построить временную диаграмму занятости устройств вычислителя, используя лишь описание этого вычислителя. Укажем основные трудности при получении временных оценок и дадим краткий обзор существующих инструментальных систем оценки времени. На данном этапе изложения мы не будем строго конкретизировать понятия программы, действия, вычислителя и т. Напомним только, что речь идет о последовательных программах. Более строго все понятия будут введены при постановке задачи (см. Решение первой задачи заключается в эффективном отображении действия программы на ресурсы заданного вычислителя. Вторая задача связана с исследованием различных историй выполнения программы. Рассмотрим подробнее задачу оценки времени для программы. Линейная структура всей программы — довольно редкий случай. Как правило, программа содержит циклы, условные и безусловные переходы, вызовы функций.