Лекции. Системы реального времени (2015) (all in one) (1185224), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Низкоуровневый анализ• Ограничить (сверху) времявыполнения различныхфрагментов программы (сочетаниеанализа программной иаппаратной составляющих)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Кэш-память увеличиваетсреднюю скорость работысистемы ценой сниженияпредсказуемости задержекМеньшезадержкипри доступеКэш-памятьВарианты организациикэша: кэш команд, кэшданных, объединённыйкэш.

Кэш-памятьиерархичнаОсновная памятьБольшеобъём37Анализ влияния кэш-памятиКакие команды приведутк промахам в кэш?Промахи в кэш приводят кзначительно большимзадержкам, чем попаданияCPUКэшпамятьОсновная память Анализируется двоичный код В данном примере – только кэшс прямым отображением(каждому адресу в основнойпамяти соответствуетединственный адрес в кэшпамяти)38Анализ влияния кэш-памятиРазмеркомандыНачальный адрес• Информациядля анализавлияния кэшакоманд39Анализ влияния кэш-памяти• Отображение вкэш команд40Анализ влияния кэш-памяти41Анализ влияния кэш-памятиПерваяитерацияциклаОстальныеитерации42Учет совместного влияния кэша иконвейера• Анализ влияния конвейера долженбрать на вход результаты анализавлияния кэш-памятиo Команды помечаютсяпопаданием/промахом в кэшo Попадания/промахи влияют назадержки в конвейере• Сложная аппаратура требуетсовместного анализа влияния кэшаи конвейера43ПрограммаАнализ потоковНизкоуровневый анализВычисление WCET• Вычислить верхнюю оценкуWCET программы– Исходные данные: информация озадержках и потоковаяинформация• Примеры подходов:ВычислениеОценкаWCET– Расчёт по синтаксическомудереву– Расчёт по путям выполнения– Неявный перебор путей (IPET)44Расчёт WCET по деревуАнализируетсясинтаксическоедерево программыОбход дерева снизувверхциклзаголовок45Расчёт WCET по дереву Фиксированныевремена выполненияузлов Времена выполнениялистьев известны Времена выполнениявнутренних узловрассчитываются поформулам для типовузловцикл: 100заголовок46Правило для оператора ветвления• Ветвление:• берем максимум иззначений дляузлов-потомков• добавляем времяна проверкуцикл: 100условиязаголовок47Правило для оператора цикла•Цикл:1.

Характеристики

Список файлов лекций