Лекция 6.а. WCET 1 (Лекции 2015-2016)

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 6:Оценка наихудшего времени выполненияпрограмм (WCET)Кафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.Почему важен WCET• Время выполнения программ играет ключевуюроль при анализе систем реального времени• Это время, например, встречается в формуле:Наихудшеевремя откликаПериодНаихудшее времявыполненияОткуда берутся значения , ?2Простейшая вычислительная задача• Входные данные доступны в моментстарта• Выходные данные готовы в моментзавершения• Нет блокировок в процессе выполнения• Нет синхронизации или обменаданными в процессе выполнения• Время выполнения зависит только от:– входных данных– состояния задачи в момент старта(внешние воздействия отсутствуют)ВходныеданныеСостояниеЗадачаСостояниеВыходныеданные3Наихудшее (максимальное) времявыполненияНаихудшее время выполнения программного кода(worst case execution time, WCET) – этомаксимальное время, которое требуется длявыполнения• данного фрагмента кода• в данном контексте (входные данные, состояние)• на заданном аппаратном вычислителе4частотаВремя выполнения: терминологияBCETМакс.наблюдаемоевремявыполненияWCETВерхняяоценкаWCETBCET – best-case execution time (минимальное время выполнения)WCET – worst-case execution time (максимальное время выполнения)5Анализ WCETЦель анализа WCET: оценить сверху времявыполнения фрагмента кода оценка WCET должна быть безопасной(недопустимо ошибаться в меньшую сторону) оценка WCET должна быть достаточно точной (еёзавышенность приведет к излишнемурезервированию ресурсов системы) затраты вычислительных ресурсов на анализдолжны быть разумными6Измерение WCETНачать отсчёт времениЗапустить задачу на целевом оборудованииОстановить отсчёт времениХронометр,Анализатор шиныи т.п.Оценка WCET7Почему нельзя просто измеритьWCET? Замер времени выполнения на всех путях выполненияреалистичной программы – на практике невозможен При определении тестовой выборки могут быть упущеныредкие сценарии выполнения (обработка ошибочныхситуаций и т.п.) Выбранные тестовые данные могут не породить самуюдлинную (по времени) трассу выполнения Внутреннее состояние процессора на момент стартаизмерений может не быть наихудшимПростые замеры могут послужить источникомпервоначальной (грубой) нижней оценки WCET8Статический анализ WCET• При статическом анализе WCET вычисляется верхняя оценкавремени выполнения фрагментов кода• Моделируются аппаратные и программные средства, атакже контекст выполнения– Программные средства: исходный код, двоичный код (спривязкой к физическим адресам)– Аппаратные средства: процессор (в т.ч.

конвейер), память (вт.ч. кэш-память)– Контекст: начальное состояние аппаратных и программныхсредств9Чем определяется WCETЗадача• Возможныепоследовательностидействий задачи (путивыполнения)• Длительность выполнениякаждого действия накаждом допустимом (т.е.практически возможном)пути выполнения10Чем определяется WCETПоследовательности действия определяются:• Семантикой программного кода (спецификойреализации, в т.ч. аппаратно-зависимой семантикой)• Входными данными, возможными в данномконтексте вызова программыДлительность действий определяется:• Аппаратной реализацией команд процессора• Состоянием аппаратных средств, влияющих натайминги (кэш-память, конвейер и т.п.)– Факторы, внутренние для задачи– Внешние факторы – состояние на момент старта;состояние после вытеснения задачи11Длительность выполнения путей –простой и сложный случаиДлительность выполнения пути k : ( )Простейшая архитектура:длительность каждого действия ai – константа: = ∑, ( )Реалистичная архитектура:длительности действия варьируются: = ∑(,() )Причины: конвейер, кэш-память, параллелизм впроцессоре, …12Фазы анализа WCET1.Анализ потоков.ПрограммаКомпиляторАнализпотоковОбъектныйкодНизкоуровневый анализЦелеваяаппаратураВычислениеФактическийWCET• Ограничить (сверху) числовыполнений различныхфрагментов программы (восновном, анализ программнойсоставляющей)2.

Низкоуровневый анализ• Ограничить (сверху) времявыполнения различныхфрагментов программы (сочетаниеанализа программной иаппаратной составляющих)3. ВычислениеОценкаWCET• Объединить результаты анализапотоков и низкоуровневогоанализ, чтобы получить верхнююоценку WCET13ПрограммаАнализ потоковНизкоуровневый анализВычислениеАнализ потоков• Ограничивает число выполнений различныхфрагментов программы (вычисляет верхнююоценку)– оценка корректна для всех возможных трассвыполнения• Примеры предоставляемой информации:– Ограничение на число итераций цикла– Ограничение на глубину рекурсии– Недопустимые пути выполнения• Источники информации:– Статический анализ программы– Ручные аннотации кодаОценкаWCET14Граф потока управленияКаждый блоквыполняетсяцеликомРёбрапередачауправления15Потоковая информация инедопустимые пути1 ≤ i ≤ 100-22 ≤ x ≤ 20Число итераций <100Структурнодопустимые пути(бесконечно много)БазоваяограниченностьСтатически допустимыеФактическивозможныеОценка WCETзавышенаПример программыГраф потокауправленияОценкаWCET точнаяВзаимосвязь между возможнымипутями выполнения и потоковойинформацией16Пример: ограничение числаитерацийОграничение числа итераций:•Зависит от возможных значенийвходной переменной I– например, если 1 ≤ ≤ 100, точисло итераций не превышает100••В общем случае – очень сложнаязадачаИмеет решение для многихчастных случаев (типов циклов)Требование базовойограниченности:•Для каждого цикла должно бытьизвестно (вычислено или задано)ограничение на число итераций17Пример: недопустимыйпутьНедопустимый путь:••Путь A-B-C-E-F-G не можетбыть выполнен, т.к.выполнение C исключаетвыполнение FЕсли (x > 5), то невозможно,чтобы (x * 2) < 0Недопустимые путиисключаются из множествастатически допустимых путей•Это может уточнить оценкуWCET18Абстрактная интерпретация•Ограничивает число итераций циклов и выявляет недопустимыепути– Вычисляет безопасную (расширенную) оценку множества значенийкаждой переменной для различных точек выполнения программы– В ходе АИ, переменной сопоставляется не конкретное значение, амножество значений («абстрактное» значение)••Программа «выполняется» с использованием абстрактныхзначений переменныхРезультат выполнения: безопасная (расширенная) оценкамножества допустимых путей выполнения– Все фактически допустимые пути входят в полученное множество– Также в него могут входить некоторые фактически НЕдопустимые пути– Пути, не вошедшие в полученное множество, гарантированно недопустимы19Ограничение числа итераций цикла спомощью АИАбстрактноеИтерация состояние в Абстрактноесостояние в qциклаpточка pточка qРезультат:Мин.

число итераций: 3Макс. число итераций: 5• Анализируются все возможные пути выполнения цикла• В точке q система может находиться в одном из трёхабстрактных состояний– Они могут быть объединены в одно абстрактное состояние20Выявление недопустимого пути с помощью АИX= -10..10X>5X= -10..5X=6..10A: X = X + 2B: X = X * 2X=12..20X= -8..7X<0Путь BCнедопустимC: ……21Треугольный цикл• Два вложенных цикла– Итераций в цикле А: неболее 100– Итераций в цикле В: неболее 100• Число выполнений блокаС:– Исходя из ограничений начисло итераций циклов:100 * 100 = 10 000– Фактически: 100 + … + 1= 5 050=> Аннотации кода22Виды аннотаций кодаПростейшая архитектура• Сведения о частоте выполнения действий– Границы и соотношения для частот выполнения– Нотация: метки (marker), соотношения (relation), области(scope)Сложная (реалистичная) архитектура• Сведения о частоте выполнения последовательностейдействий– Информация о (не)допустимых путях– Нотация: на основе регулярных выражений, например IDL(path Information Description Language)23Пример аннотации путейВыражение для путиСложная архитектура:N= 3*kN= 3*k+1N= 3*k+2Простая архитектура:24Маркеры, соотношения и области25Проблема соответствия междуисходным и двоичным кодом•Анализ потоков проще проводить на уровне исходного кода– Более ясная семантика кода– Проще получить потоковую информацию (и для программиста, и дляавтоматических инструментов)••Низкоуровневый анализ работает с двоичным кодом, фактическивыполняемым на процессореКак отобразить потоковую информацию с уровня исходного кодана двоичный код?Где цикл вдвоичномкоде?Числопроверок: 101Исходный кодДвоичный код26Проблема соответствия между исходным идвоичным кодом•Компиляторы для встроенных систем реального времени выполняют глубокуюоптимизацию кода–•Оптимизации могут существенно изменить размещение кода и данных–•Нужно уложиться в ограничения по времени и объему памятиВ результате оптимизаций потоковая информация с уровня исходного кода становитсянеприменимойРешения:––––Реализовать в компиляторе средства отображения потоковой информации (недостижимыйидеал)Использовать компиляцию с отладочной информацией (работает только при отсутствии илис минимумом оптимизаций)Для систем с большим объемом памяти – не производить оптимизации кода с цельюсокращения объемаПроводить потоковый анализ на двоичном коде (так чаще всего и делают)Анализ потоков:проверкавыполняется 101разКомпилятор: вначале циклагарантированоi=0Проверкавыполняется 100раз27До оптимизацииПосле оптимизацииПрограммаАнализ потоковНизкоуровневый анализВычислениеОценкаWCETНизкоуровневыйанализ Ограничить время выполнения различныхфрагментов программы Основная задача большей части исследований поWCET Использовать модель целевой аппаратуры Не требуется моделировать все подробностиработы аппаратуры При этом необходимо безопасно (сверху) оценитьвсе задержки при работе аппаратуры Применяется к скомпонованному двоичному коду(исполняемой программе)28Проблемы моделирования аппаратуры Высокая сложность моделирования внутренней работы процессора– Конвейер, предсказание ветвлений, суперскалярность, внеочередноевыполнение… Высокая сложность моделирования иерархической памяти– Необходимо детальное моделирование кэш-памяти– Другие виды памяти также являются источником задержек Многие аспекты функционирования сложных процессоров должнымоделироваться совместно– Тайминги выполнения команд процессора зависят от предыстории Разработка безопасной временной модели функционированияпроцессора – сложная задача– Занимает месяцы и даже годы работы– Необходимо учесть все факторы, влияющие на время выполнения (какминимум, оценить сверху их влияние)=> Аппаратура с предсказуемым временем работыважнее, чем очень быстрая аппаратура29Простой конвейер• Большинство команд проходят в процессоре черезодни и те же этапы выполнения• Пример: классический 5-ступенчатый конвейерRISC-процессораДекодирование команды(instruction decode) Определить,какую операцию необходимовыполнить: выделить её код иаргументыВыборка команды (instructionfetch) Получить очереднуюкоманду из памяти (адрес — врегистре-счётчике команд).Выполнение (execution)Выполнить требуемоедействие (например,сложение)Доступ к памяти(memory access)Загрузить/сохранитьзначения из/в памятьЗапись результата (writeback) Записать результатоперации в целевойрегистр30Работа конвейера••Параллельная работа различных стадийконвейера для различных команд (=>ускорение)Нет конвейера:– следующая команда не может начатьвыполнение, пока текущая команда незавершит последнюю стадию выполнения•Конвейер:– В идеале: коэффициент ускорения равенчислу ступеней конвейера– Фактически: между командами естьзависимости по данным; «слом» конвейерапри неверном предсказании ветвления;ожидание данных из памятиНепосредственнаязависимость поданнымI2 ждётвычислениярезультата I1Может возникнутьзадержка в31конвейереВиды конвейеров• Отсутствует: простейшие процессоры (68HC11, 8051, …)• Скалярный: единственный конвейер (ARM7, ARM9, V850, …)• VLIW: несколько конвейеров, статическое планирование их загрузкина уровне компилятора (DSPs, Itanium, Crusoe, …)• Суперскалярный: несколько конвейеров, внеочередное выполнениекоманд (PowerPC 7xx, Pentium, UltraSPARC, …)Голубая команданаходится на этапе ЕХдва дополнительныхтактаЭто приводит кзадержке выполнениявсех последующихкоманд32Задержки: нет конвейера• Фиксированноевремя длякаждогофрагмента кода• Двоичный кодне показан33Задержки: нет конвейера34Задержки: простой конвейер35Задержки: простой конвейер36Иерархическая памятьПроцессор обращаетсяв память за командамии даннымиЧасто используемыекоманды и данныехранятся в быстройкэш-памятиОсновная память имеетбольшой объём, нозадержки на доступ к нейгораздо выше, чем у кэшпамятиCPUКэш-память увеличиваетсреднюю скорость работысистемы ценой сниженияпредсказуемости задержекМеньшезадержкипри доступеКэш-памятьВарианты организациикэша: кэш команд, кэшданных, объединённыйкэш.