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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Г 8 ОД _

О ,-Ц!"^ »ЯТ1

о Qr.il

Факультет вычислительной математики и кибернетики

На правах рукописи УДК 681.3.012

КАПИТОНОВА Алла Петровна

МЕТОДЫ И СРЕДСТВА ПРОГНОЗИРОВАНИЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПОСЛЕДОВАТЕЛЬНЫХ ФРАГМЕНТОВ ПРОГРАММ НА ВЫЧИСЛИТЕЛЯХ С РАЗЛИЧНОЙ АРХИТЕКТУРОЙ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1997

Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова

Научный руководитель:

доктор физико-математических наук,

профессор РЛ.Смелянский

Официальные оппоненты: доктор физико-математических наук, профессор А.Н.Томилин

кандидат физико-математических наук Вл.В.Воеводин

Ведущая организация

Институт Прикладной Математики РАН им. В.М.Келдыша

Защита состоится февраля 1997 года в Ц часов на заседании

Специализированного совета Д.053.05.38 N4 по математике при МГУ им. М.В.Ломоносова по адресу: 119899, ГСП, Москва В-234, Воробьевы горы, МГУ, факультет вычислительной математики н кибернетики, аудитория

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

685.

Автореферат разослан января 1997 г.

Ученый секретарь Специализированного совета МГУ Д.053.05.38 по математ!— профессор

п

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

При выборе той или иной вычислительной системы для решения прикладных задач пользователи неизбежно сталкиваются с вопросом: насколько данная система удовлетворяет классу решаемых задач. Основой при ответе на этот вопрос служат различные характеристики производительности. Как показывает накопленный опыт, многообразие вычислительных систем, отличных по архитектуре, чрезвычайно затрудняет использование в качестве средства сравнения единой меры производительности.

Время выполнения программы на вычислителе — это мера, естественная с точки зрения восприятия человеком и универсальная при сравнении вычислителей любой архитектуры. Однако трудность получения значения времени, затрачиваемого на выполнение некоторой вычислительной работы, состоит в том, что необходимо выполнить программу (набор программ) на каждой из сравниваемых вычислительных систем. А это может быть или слишком дорого (например, для сложных "параллельных" вычислительных систем), или практически недоступно (при наличии только проекта архитектуры).

В силу указанных выше особенностей становится актуальной задача разработки методики прогнозирования времени выполнения программ на различных вычислительных системах.

Возможность решения этой задачи представляет интерес как для обычных пользователей, так и для разработчиков новых архитектурных решений в области вычислительных систем. Выбор подходящей вычислительной системы для реализации набора алгоритмов, проблемы эффективного распараллеливания программ, изучение поведения программ, разработка и оценка новых архитектур — все эти задачи связаны с оценкой времени выполнения.

Особый интерес к проблеме прогнозирования времени связан с применением вычислительных систем реального времени. Такие системы, как правило, участвуют в управлении некоторым реальным

процессом и должны обладать одним чрезвычайно важным свойством — вычислитель должен не только правильно реализовывать алгоритм, но обязан делать это в заданный отрезок времени. Поэтому для разработчиков таких систем возможность получения данных о времени выполнения программ стала не желательным, а необходимым условием на этапе проектирования.

Основные пели работы.

• анализ существующих подходов и методов, применяющихся в теории и практике прогнозирования времени выполнения последовательных фрагментов программ;

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

• разработка методики, пригодной для прогнозирования времени выполнения последовательных фрагментов программ на вычислителях, принадлежащих различным ¡слассам современных архитектур;

• на основе предложенной методики прогнозирования создание инструментальной системы оценки времени, которая позволяла бы по описанию вычислителя, тексту исследуемой программы и набору исходных данных получать предполагаемое время выполнения.

Научная новизна.

В диссертации предложен комплексный статико-динамический подход для решения задачи прогнозирования времени выполнения последовательных вычислений. Новизна подхода заключается в том, что метод использует статический анализ текста программы с целью получения временных оценок для линейных фрагментов вычислений, которые затем корректируются динамически в ходе прогона программы.

Исследованы несколько классов целевых вычислителей и построены соответствующие модели. Для каждого класса вычислителей предложены средства для параметричесокою описания архитектуры вычислителя, что позволяет реализовать многоцелевую

инструментальную систему прогнозирования времени выполнения вычислений.

Практическая значимость.

Работа выполнена на кафедре автоматизации систем вычислительных комплексов, в Лаборатории вычислительных комплексов в рамках проекта по созданию интегрированной среды разработки и анализа распределенного программного обеспечения DYANA и поддержана грантом РФФИ N95-01-01590а. В рамках среды DYANA реализована подсистема прогнозирования времени выполнения последовательных фрагментов вычислений.

Подсистема предоставляет пользователю средства для описания вычислителя, на котором предполагается выполнение программы. Используя созданное описание, подсистема осуществляет прогнозирование времени выполнения указываемых пользователем фрагментов вычислений. Таким образом, данное инструментальное средство обеспечивает автоматическую оценку временной сложности внутренних действий последовательных процессов, работающих в распределенной вычислительной среде. Среда DYANA с реализованной подсистемой прогнозирования времени демонстрировалась на международной выставке CeBIT в Ганновере (Германия) в 1995 и 1996 годах. Внедрение работы планируется продолжить в 1997 году.

Полученные результаты показали, что построенная на базе статико-динамического подхода инструментальная система прогнозирования времени дает высокую точность получаемых оценок (средняя погрешность 20%) и позволяет качественно улучшить процесс создания программного обеспечения при использовании среды DYANA. Динамический этап прогнозировать замедляет выполнение программы не более, чем на порядок. В сравнении со скоростью работы эмуляторов целевых вычислителей построенная нами инструментальная система даст выигрыш не менее, чем на два порядка.

Достоверность результатов подтверждается успешным прогоном тестовых примеров, которые были разработаны для проверки системы оценки времени.

Апробация и публикации.

Результаты работы докладывались на межкафедральном семинаре на факультете вычислительной математики и кибернетики, на VI конференции "Транспьютерные системы и их применение". По теме диссертации опубликованы три работы, полно отражающие основные научные результаты диссертации. Прикладные результаты представлены также в ряде научных отчетов по НИР, ведущимся в Лаборатории вычислительных комплексов ВМК МГУ.

Структура и объем диссертационной работы.

Диссертация состоит из введения, пяти глав, заключения, пяти приложений и списка литературы (включающего 57 названий) и занимает 118 машинописных страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении перечислены проблемы, для решения которых важно уметь оценивать время выполнения вычислений. Указано на существование двух взглядов на проблему оценки времени: измерение и прогнозирование. Дается неформальная постановка задачи прогнозирования времени выполнения программы, рассматриваемой в данной диссертации.

В первой главе подробно рассмотрены существующие методики прогнозирования времени. В пункте 1.1 указано на взаимосвязь задачи оценки времени и выбора универсальной меры производительности вычислительной работы. Конкретизируются классы программ п

вычислителей, рассматриваемых при прогнозировании времени в рамках предлагаемой диссертационной работы. В данном пункте также оговаривается, что методика прогнозирования разрабатывается для предсказания времени выполнения только тех действий, которые задаются программой пользователя. Влияние операционной системы, а также оценка времени выполнения операций ввода/вывода не рассматриваются.

В пункте 1.2 показано, что при прогнозировании времени выполнения последовательной программы всегда требуется решать две взаимосвязанных проблемы:

• оценка времени выполнения действия программы:

• оценка времени выполнения последовательности действий программы при фиксированном наборе исходных данных.

Существующие методы прогнозирования времени на множестве историй выполнения программы подробно исследуются в пункте 1.3. Особое внимание уделяется наиболее распространенному методу статического анализа текста программы с целью получения наихудшего и наилучшего значений времени выполнения программы. Показано, что независимо от выбранного подмножества историй выполнения программы, точность получаемых оценок зависит от способа отображения действий программы на устройства исследуемого вычислителя.

Пункт 1.4 посвящен анализу различных способов оценки времени выполнения линейного фрагмента вычислений. Указано, что наиболее точный метод — это метод имитации работы устройств процессора. Под имитацией подразумевается построение временной диаграммы занятости устройств вычислителя без эмуляции выполнения действий программы.

Обобщая изложенные в предыдущих двух пунктах факты, в пункте 1.5 выдвигаются требования к инструментальным системам прогнозирования времени выполнения программ. Дается краткий обзор особенностей известных систем прогнозирования.

Во второй главе рассмотрены основные особенности предлагаемого в данной работе статико-динамического метода прогнозирования времени выполнения последовательных программ.

В пункте 2.1 вводятся необходимые понятия и определения. Затем формулируется общая задача прогнозирования времени: имея текст программы, информацию о поведении программы, описание архитектуры вычислителя, определить время выполнения действий программы на исследуемом вычислителе для произвольной истории выполнения программы.

Пункт 2.2 целиком посвящен описанию статико-динамического метода прогнозирования времени. Формулируется важное свойство инвариантности поведения программы относительно класса вычислителей и указывается, что при решении задачи прогнозирования будут рассматриваться вычислители и программы, поддерживающие инвариантность поведения программы. Далее анализируются полностью статические и динамические методы прогнозирования времени, после чего формулируется цель — разработать подход, который совмещает достоинства обоих методов, минимизируя их недостатки.

Идея статико-динамического подхода заключается в следующем. Для прогнозирования времени выполнения программы необходимо знать, сколько раз выполнилось каждое из действий программы. Свойство инвариантности поведения исследуемых программ дает нам возможность получить эти данные, выполнив программу на инструментальном вычислителе. Затем, используя полученную информацию, описание целевого вычислителя и информацию о времени выполнения каждого действия программы, можно дать оценку времени выполнения программы на данном вычислителе. Время выполнения действия программы определяется стат!гческими методами. На динамическом этапе мы получаем информацию о том, какие действия программы и сколько раз выполняются при фиксированном наборе исходных данных.

В этом же пункте указывается, что эффективнее проводить прогнозирование не на уровне отдельных операторов программы, а на уровне линейных участков. В последующих главах подробно рассматриваются особенности прогнозирования времени выполнения

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

В главе 3 показано, что задача оценки времени выполнения линейного участка на вычислителях фон-неймановского типа близка задаче генерации кода.

В пункте 3.1 осуществляется переход от задачи прогнозирования времени к задаче построения кода минимальной длины для последовательности деревьев выражений.

Следующий пункт конкретизирует процесс получения оценки времени выполнения линейного участка на выбранном массе вычислителей.

В пункте 3.3 на базе стековой и регистровой моделей строится модель обобщенного последовательного регистро-стекового вычислителя. Подробно рассматриваются особенности алгоритмов генерации кода для дерева выражения. Для генерации кода в терминах команд модельного вычислителя используются оптимальные алгоритмы генерации кода, предложенные Лхо-Джонсоном, а также Бруно-Лессиджем. После генерации кода возможно вычисление времени выполнения линейного участка на основе данных, получаемых из описания целевого вычислителя.

Пункт 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.4 модели.

В последнем пункте данной главы описана возможная реализация инструментальной системы прогнозирования времени выполнения программы на векторно-конвейерном вычислителе.

Глава 5 посвящена классу RISC вычислителей. Во введении к этой главе еще раз отмечается практическая необходимость решения задачи

л

прогнозирования времени в контексте применения систем реального времени. Рассматривается отличие предлагаемого нами метода статико-динамического прогнозирования от традиционно применяемых подходов, являющихся статическими. Указывается, что усложнение архитектуры процессора приводит к необходимости статической имитации работы устройств вычислителя с учетом анализа зависимостей между инструкциями программы.

В пункте 5.1 рассмотрены проблемы моделирования поведения конвейеров команд с учетом различных типов задержек.

Задача статической имитации кэш-памяти достаточно подробно анализируется в пункте 5.2. Указано на трудности статических за1слючений о поведении объектов такого рода. Затем изложена идея алгоритма Ф.Мюллера для статического анализа поведения кэш-памяти инструкций, который в модифицированном виде был использован при построении инструментальной системы оценки времени для it.nacca RISC вычислителей.

Аналогично предыдущим двум главам последние пункты данной главы содержат параметрическое описание вычислителя и описание архитектуры инструментальной системы оценки времени. Приводятся результаты экспериментов.

В заключении приведены основные результаты работы:

• Разработаны параметрические модели различных 1;лассов современных вычислителей, актуальных с точки зрения прогнозирования времени последовательных вычислений. На основе предложенных моделей разработаны средства описания архитектуры вычислителей.

• Разработан комбинированный статико-динамическнй подход к анализу последовательных программ, позволяющий получить хорошую точность прогнозирования времени выполнения программ для исследуемого вычислителя.

* Предлагаемая методика прогнозирования реализована в виде многоцелевой инструментальной системы оценки времени выполнения последовательных фрагментов программ.

Приложения диссертации содержат следующие материалы. Приложение 1 посвящено описанию алгоритмов генерации оптимального кода для регистровой и стековой моделей последовательного вычислителя.

В приложении 2 приводится пример разметки конструкций языка Си на линейные участки.

Приложение 3 дает представление об используемом в инструментальной системе оценки времени языке для параметрического описания регистро-стекового вычислителя.

Приложение 4 — это пример параметрического описания RISC вычислителя.

Приложение 5 дает представление о результатах статического этапа прогнозирования времени для RISC вычислителя на примере процессора с архитектурой SPARC.

Публикации по теме диссертационной работы:

1. Капитонова А.П., Смелянский P.JI., Терехов Н.В. Инструментальная система оценки трудоемкости вычислений в программах. // Сб. Системное программирование и модели исследования операций. С. 57-72. М„ МГУ. 1993.

2. Капитонова А.П., Смелянский P.JL, Терехов И.В. Система для оценки временных характеристик программ: архитектура и реализация. // Сб. Программно-аппаратные средства и математическое обеспечение вычислительных систем. С.92-103. М., МГУ. 1994.

3. Капитонова А.П. Методы и средства оценки времени выполнения программ. // Материалы VI конференции "Транспьютерные системы и их применение". 1996.

Введение

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 Определение времени выполнения векторизуемых программ . . 61 4.5.1 Алгоритм динамического программирования на классе векторных вычислителей.

4.5.2 Алгоритм циклического планирования.

4.6 Формальное описание векторно-конвейерного вычислителя

4.7 Инструментальная система прогнозирования времени для векторно-конвейерных вычислителей.

5 Решение задачи на классе RISC вычислителей

5.1 Моделирование поведения конвейеров.

5.2 Моделирование поведения кэш-памяти.

5.2.1 Особенности кэш-памяти.

5.2.2 Методы статического моделирования кэш-памяти

5.3 Средства описания архитектуры процессора.

5.4 Архитектура системы оценки времени для RISC процессоров . 87 Заключение 92 Приложения

I. Описание алгоритмов генерации кода.

II. Разметка операторов языка Си.

Ш. Параметрическое описание регистро-стекового вычислителя.

IV. Параметрическое описание вычислителя с RISC архитектурой.

V. Пример статических предсказаний для RISC вычислителей.

Данная работа посвящена вопросу оценки времени выполнения последовательных программ.

Возможность решения этой задачи представляет интерес как для обычных пользователей, так и для разработчиков новых архитектурных решений в области вычислительных систем. Выбор подходящей вычислительной системы для реализации набора алгоритмов, проблемы эффективного распараллеливания программ, изучение поведения программ, разработка и оценка новых архитектур — все эти задачи связаны с оценкой времени выполнения.

Особый интерес к проблеме оценки времени возник в последнее десятилетие в связи с широким применением вычислительных систем реального времени. Такие системы, как правило, участвуют в управлении некоторым реальным процессом и должны обладать одним чрезвычайно важным свойством — вычислитель должен не только правильно реализовывать алгоритм, но обязан делать это в заданный отрезок времени. Система, которая выполняет задачу позже указанного директивного времени считается работающей неверно. Поэтому для разработчиков таких систем возможность получения данных о времени выполнения программ стала не желательным, а необходимым условием на этапе проектирования.

Под оценкой времени выполнения обычно понимается одна из альтернатив:

• измерение определенных параметров функционирования вычислительной системы на этапе ее работы;

• предсказание времени выполнения программ без выполнения на исследуемом вычислителе.

Первый подход обычно подразумевает наблюдение за выполнением программы, сбор трасс, построение программных и аппаратных эмуляторов [1, 2, 3]. Таким образом, он всегда связан с исследованием динамики программы. Достоинство динамических методов — в точности получаемых оценок. Однако их применение не всегда возможно по следующим причинам:

• отсутствие реального вычислителя;

• реализация эмулятора исследуемого вычислителя является дорогостоящим и трудоемким процессом;

• значительное замедление ( 10-1000 раз) выполнения программы из-за накладных расходов при измерении.

Предсказание (или прогнозирование) времени выполнения программы чаще всего предполагает использование разнообразных статических методов, а также имитационное моделирование работы устройств исследуемой вычислительной системы.

В данной работе оценка времени выполнения будет пониматься именно в смысле прогнозирования. Исследование динамических свойств программы методом измерений рассматриваться не будет.

Более конкретно, в предлагаемой работе исследуется следующая проблема: по тексту программы, информации о поведении программы, описанию архитектуры вычислителя определить время выполнения программы на этом вычислителе.

Для решения задачи разработана методика комплексного статико-динамического прогнозирования.

В работе будет показано, как меняется специфика задачи при изменении класса вычислителей. Решение рассматривается на трех классах вычислителей:

• последовательные вычислители фон-неймановского типа;

• векторно-конвейерные вычислители;

• вычислители с RISC архитектурой.

Для каждого из этих классов также предлагаются средства формального описания архитектуры вычислителя.

Предложенная методика прогнозирования реализована в виде инструментальной системы оценки времени выполнения программы в рамках проекта DYANA.

Данная работа организована следующим образом. В главе 1 проводится сравнительный анализ существующих методик оценки времени. В главе 2 излагаются основы предлагаемой нами методики. В главах 3, 4, 5 рассматривается решение задачи прогнозирования на разных классах вычислителей.

Основные результаты данной работы заключаются в следующем:

• Разработаны параметрические модели различных классов современных вычислителей, актуальных с точки зрения прогнозирования времени последовательных вычислений. На основе предложенных моделей разработаны средства описания архитектуры вычислителя.

• Разработан комбинированный статико-динамический подход к анализу последовательных программ, позволяющий получать хорошую точность прогнозирования времени выполнения программ для исследуемого вычислителя.

• Предлагаемая методика прогнозирования реализована в виде многоцелевой инструментальной системы оценки времени выполнения последовательных фрагментов программ.

Инструментальная система прогнозирования времени может быть использована автономно или в комплексе с другими инструментами анализа свойств программ и/или функционирования вычислительных систем.

Статико-динамический подход был применен при реализации подсистемы временной сложности в рамках среды БУАКА [56], предназначенной для анализа функционирования распределенных вычислительных систем. Методика прогнозирования времени использовалась для оценки сложности внутренних действий последовательных процессов. Поскольку среда БУАКА анализирует поведение распределенных программ путем имитационного моделирования работы исследуемой вычислительной системы, статико-динамическая методика органично вписывается в работу такой среды.

Заключение

1. Смелянский P.JI. Методы анализа и оценки производительности вычислительных систем. М.: МГУ. 1990.

2. Davidson J.W., Rabung J.R., Whalley D.B. Relating Static and Dyanamic Machine Code Measurements. // IEEE Trans, on Computers, V.41, N4, Apr. 1992, pp.444-454.

3. Rozwadowski R.T. A measure for the quantity of computation. // Proc. ACM SIGME Symp. on Measuremant and Evaluation, 1973, pp. 100-111.

4. Hellerman L. A measure of computational work. // IEEE Trans, on Computers. V.C-21, N5, 1972, pp. 439-446.

5. Hennessy J.L., Patterson D.A. Computer Architecture: a Quantitative Approach. California. 1990.

6. Смелянский P.JI. Взаимодействие программы и вычислительной среды. // Сб. Вычислительные комплексы и моделирование сложных систем. М., МГУ, 1990.

7. Капитонова А.П., Смелянский P.JI., Терехов И.В. Система для оценки временных характеристик программ: архитектура и реализация. // Сб. Программно-аппаратные средства и математическое обеспечение вычислительных систем. С.92-103. М., МГУ. 1994

8. Bharrat S.J., Jeffay К. Predicting Worst Case Execution Times on a Pipelined RISC Processor. // Technical Report, University of North Carolina, 1994.

9. Busquets J.V., Serano J.J., Ors R., Gil P., Wellings A., Adding Instruction Cache Effect to an Exact Schedulability Analysis of Preemptive Real-Time Systems.// Euromicro Workshop on Real-Time Systems, June 1996.

10. Busquets J.V, Serano J.J., The Impact of Extrinsic Cache Performance on Predictiability of real-Time Systems. // Proc. of 2nd International Workshop on real-Time Computing Systems and Applications (RTCSA'95).

11. Park C.Y., Shaw A.C., A Source-Level Tool for Predicting Deterministic Execution Time of Programs. // T.R. 89-09-12, Dpt. of Computer Science and Engineering, University of Washington. 1989.

12. Puschner P., Koza C.H. Calculating the Maximum Execution Time of Real-Time Programs. // The International Jornal of Time-Critical Computer Systems, 1(2), 1989, pp.159-176.

13. Ершов А.П. Современное состояние теории схем программ. // Проблемы кибернетики. Вып. 27. М., 1973. С.87-111.

14. Nilsen K.D., Rygg В., Worst-Case Execution Time Analysis on Modern Processors. // Second ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems, June, 1995.

15. Ко L., Whalley D.W., Harmon M.G., Suppoting User-Friendly Analysis of Timing Constraints. // Proc. ACM SIGPLAN Workshop on Language, Compilers and Tools for Real-Time Systems, June 1995, pp.107-115.

16. Harmon M.G., Baker T.P, Whalley D.B., A Retargetable Technique for Predicting Execution Time of Code Segments. // Real-Time Systems, September 1994, pp.159-182.

17. Narasimhan K., Nilsen K.D., Portable Execution Time Analysis for RISC Processors. // ACM SIGPLAN Workshop on Language, Compiler and Tools for Real-Time Systems, June 1994.

18. Lim S.S., Bae J.H., Jang G.T., An Accurate Worst Case Timing Analysis Technique for RISC Processors. // Proc. Fifteenth IEEE Real-Time Systems Symposium, Dec. 1994, pp.97-108.

19. Shaw A.C., Reasoning About Time in High-Level Language Software. // Research Report, Laboratory MASI, University of Paris 6.

20. Мок A.K., Evaluating Tight Execution Time Bounds of Programs by Annotations. // Sixth IEEE Workshop on Real-Time Operating Systems and Software. Pittsburg, PA, pp.74-80.

21. Stoenko A.D., A Real-Time Language With a Schedualability Analyser. // PhD Thesis, Department of Computer Science, University of Toronto, 1987, Toronto.

22. Healy C.A., Whalley D.B., Harmon M.G., Integrating the Timing Analysis of Pipelining and Instruction Caching. // Proceedings of the IEEE Real-Time Systems Symposium, December, 1995, pp.288-297.

23. Aho A.V., Sethi R., Ullman J.D. Compiling Principles, Techniques, and Tools. Addison-Wesley Publishing Company. 1988.

24. Mueller F., Static Cache Simulation and its Applications. // PhD Dissertation, Florida State University, Tallahassee, Fl, August, 1994.

25. Y-T. S., Malik S., Wolfe A., Efficient Microarchitecture Modeling and Path Analysis for Real-Time Systems. // Proc. of 16th IEEE Real-Time Systems Symposium, Dec. 1995, pp.298-307.

26. Y-T. S., Malik S., Wolfe A., Performance Estimation of Embedded Software with Instruction Cache Modeling // Proc. of ACM/IEEE International Conference on Computer Aided Design. November 1995.

27. Choi J.-Y., Lee I., Kang I. Timing Analysis of Superscalar Processor Programs using ACSR. // 1993.

28. Diep T.A., Shen J.P. Systematic Validation of Pipeline Interlock for Superscalar Microarchitectures. // Proc. of the International Symposium on Fault-Tolerant Computing, 1995.

29. Diep T.A. A Visualization-based Microarchitecture Workbench. // PhD Dissertation. Carnegie Mellon University. 1995.

30. Aho A.V., Johnson S.C. Optimal Code Generation for Expression Trees. // J. ACM, V.23, N3, 1976, pp.488-501.

31. Уокерли Дж. Архитектура и программирование микро-ЭВМ. — М., кн. 1, гл. 5.

32. Bruno J.L., Lassagne Т. The Generation of Optimal Code for Stack Machines. // J. ACM, V.22, N3, 1975, pp.382-396.

33. Aho A.V., Johnson S.C., Ullman J.D. Code Generation for Expression with Common Subexpression. //J. ACM, V.24, N1, 1977, pp. 146-160.

34. Aho A.V., Ganapathi, Tjiang W.K. Code Generation Using Tree Matching and Dynamic Programming. // ACM Trans. Program. Lang. Syst., V.ll, N4, 1989, pp.491-516.

35. Knuth D.E. The Art of Computer Programming, V. 1, Fundamental Algorithms, 2nd Ed. 1973.

36. Aho A.V., Johnson S.C. Optimal Code Generation for Expression Trees. // J. ACM, V.23, N3, 1976, pp.488-501.

37. Капитонова А.П., Смелянский P.JI., Терехов И.В. Инструментальная системы оценки трудоемкости вычислений в программах. // Сб. Системное программирование и модели исследования операций. С. 57-72. М., МГУ. 1993.

38. Морс С.П., Алберт Д.Д. Архитектура микропроцессора 80286. М., Радио и связь. 1990.

39. Воеводин В л. В., Капитонова А. П. Методы описания и классификации вычислительных систем. М., МГУ, 1994.

40. Хокни Р., Джесхоуп К. Параллельные ЭВМ. М., Радио и связь. 1986.

41. Воеводин В.В., Воеводин Вл.В., Еремин А.Ю., Тыртышников Е.Е. Комплексное изучение параллелизма — ключ к эффективному использованию супер-ЭВМ. М., МГУ. 1994.

42. Padua D.A., Wolfe M.J. Advanced Compiler Optimizations for Supercom-puting. // Com. of the ACM, V,29, N12, pp.1184-1201.

43. Eisenbeis C., Jalby W., Lichnevsky A. Squeezing More CPU Performance Out of a Cray-2 by Nector Block Sheduling. INRIA. Report N 841. 1988.

44. Bernstein D., Boral H., Pinter R. Optimal Chaining in Expression Trees. // J. ACM. 1986. pp.1-10.

45. Eisenbeis C., Jalby VV. Static Dependence Analysis and Control for Loop Scheduling. INRIA. Report N 1296. 1990.

46. Y-T. S., Malik S., Performance Analysis of Embedded Software Using Implicit Path Enumeration. // Proc. of ACM Design Automation Conference, June 1995.

47. The SPARC Technical Papers, Ed. Catanzaro B.J., Springer-Verlag, 1991.

48. Петрова Ю. RISC процессоры третьего поколения. // Computer Week Moscow. N22,23. 1995.

49. Калиниченко Д.В., Капитонова А.П., Ющенко Н.В. Методы и средства прогнозирования времени выполнения последовательных программ. // Сб. Методы математического моделирования. В печати.

50. Kim S., Min S., На R., Efficient Worst Case Timing Analysing of data Caching. // Proc. of IEEE RTAS'96.

51. Groves R.D., Oehler R.R. IBM RISC System/6000 Processor Architecture. // IBM J. Res. Develop., V.34, N.l, 1990, pp.23-36.

52. Аваков В. Микропроцессор MIPS R10000. // Открытые системы, N6, 1995. С.62-69.

53. Kane J., Heinrich J., MIPS RISC Architecture. Prentice Hall. 1992.

54. Rawat J., Static Analysis of Cache Performance for Real-Time Programming. // Master's thesis, Iowa State University, 1993.

55. Bakhmurov A.G., Smeliansky R.L. DYANA: An Environment for Distributed System Design and Analysis. // Proc. of the VII Int. Workshop on Parellel Processing by Cellular Automata and arrays. 1996. pp.85-92.

56. The SPARC Architecture Manual. Version 8. Prentice Hall. 1992.