Введение к работе
Актуальность темы.
При выборе той или иной вычислительной системы для решения прикладных задач пользователи неизбежно сталкиваются с вопросом: насколько данная система удовлетворяет классу решаемых задач. Основой при ответе на этот вопрос служат различные характеристики производительности. Как показывает накопленный опыт, многообразие вычислительных систем, отличных по архитектуре, чрезвычайно затрудняет использование в качестве средства сравнения единой меры производительности.
Время выполнения программы на вычислителе — это мера, естественная с точки зрения восприятия человеком и универсальная при сравнении вычислителей любой архитектуры. Однако трудность получения значения времени, затрачиваемого на выполнение некоторой вычислительной работы, состоит в том, что необходимо выполнить программу (набор программ) на каждой из сравниваемых вычислительных систем. А это может быть или слишком дорого (например, для сложных "параллельных" вычислительных систем), или практически недоступно (при наличии только проекта архитектуры).
В силу указанных выше особенностей становится актуальной задача разработки методики прогнозирования времени выполнения программ на различных вычислительных системах.
Возможность решения этой задачи представляет интерес как для обычных пользователей, так и для разработчиков новых архитектурных решений в области вычислительных систем. Выбор подходящей вычислительной системы для реализации набора алгоритмов, проблемы эффективного распараллеливания программ, изучение поведения программ, разработка и оценка новых архитектур — все эти задачи связаны с оценкой времени выполнения.
Особый интерес к проблеме прогнозирования времени связан с применением вычислительных систем реального времени. Такие системы, как правило, участвуют в управлении некоторым реальным
процессом и должны обладать одним чрезвычайно важным свойством — вычислитель должен не только правильно реализовывать алгоритм, но обязан делать это в заданный отрезок времени. Поэтому для разработчиков таких систем возможность получения данных о времени выполнения программ стала не желательным, а необходимым условием на этапе проектирования.
Основные цели работы.
анализ существующих подходов и методов, применяющихся в
теории и практике прогнозирования времени выполнения
последовательных фрагментов программ;
исследование особенностей задачи прогнозирования времени выполнения вычислений на вычислителях с различной архитектурой;
разработка методики, пригодной для прогнозирования времени выполнения последовательных фрагментов программ на вычислителях, принадлежащих различным классам современных архитектур;
на основе предложенной методики прогнозирования создание инструментальной системы оценки времени, которая позволяла бы по описанию вычислителя, тексту исследуемой программы и набору исходных данных получать предполагаемое время выполнения.
Научная новизна.
В диссертации предложен комплексный статико-динамический подход для решения задачи прогнозирования времени выполнения последовательных вычислений. Новизна подхода заключается в том, что метод использует статический анализ текста программы с целью получения временных оценок для линейных фрагментов вычислений, которые затем корректируются динамически в ходе прогона программы.
Исследованы несколько классов целевых вычислителей и
построены соответствующие модели. Для каждого класса вычислителен
предложены средства для параметричесокою описания архитектуры
вычислителя, что позволяет реализовать многоцелевую
инструментальную систему прогнозирования времени выполнения вычислений.
Практическая значимость.
Работа выполнена на кафедре автоматизации систем вычислительных комплексов, в Лаборатории вычислительных комплексов в рамках проекта по созданию интегрированной среды разработки и анализа распределенного программного обеспечения DYANA и поддержана грантом РФФИ N95-01-01590а. В рамках среды DYANA реализована подсистема прогнозирования времени выполнения последовательных фрагментов вычислений.
Подсистема предоставляет пользователю средства для описания
вычислителя, на котором предполагается выполнение программы.
Используя созданное описание, подсистема осуществляет
прогнозирование времени выполнения указываемых пользователем фрагментов вычислений. Таким образом, данное инструментальное средство обеспечивает автоматическую оценку временной сложности внутренних действий последовательных процессов, работающих в распределенной вычислительной среде. Среда DYANA с реализованной подсистемой прогнозирования времени демонстрировалась на международной выставке CeBIT в Ганновере (Германия) в 1995 и 1996 годах. Внедрение работы планируется продолжить в 1997 году.
Полученные результаты показали, что построенная на базе
статико-динамического подхода инструментальная система
прогнозирования времени дает высокую точность получаемых оценок (средняя погрешность 20%) и позволяет качественно улучшить процесс создания программного обеспечения при использовании среды DYANA. Динамический этап прогнозироваїпія замедляет выполнение программы не более, чем на порядок. В сравнении со скоростью работы эмуляторов целевых вычислителей построенная нами инструментальная система даст выигрыш не менее, чем на два порядка.
Достоверность результатов подтверждается успешным прогоном тестовых примеров, которые были разработаны для проверки системы оценки времени.
Апробация и публикации.
Результаты работы докладывались на межкафедралыюм семинаре на факультете вычислительной математики и кибернетики, на VI конференции "Транспьютерные системы и их применение". По теме диссертации опубликованы три работы, полно отражающие основные научные результаты диссертации. Прикладные результаты представлены также в ряде научных отчетов по НИР, ведущимся в Лаборатории вычислительных комплексов ВМК МГУ.
Структура и объем диссертационной работы.
Диссертация состоит из введения, пяти глав, заключения, пяти приложений и списка литературы (віглючающего Г>7 названии) и занимает 118 машинописных страниц.
