Лекция 6.б. WCET 2 (1185231)

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

Текст из файла

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 6:Оценка наихудшего времени выполненияпрограмм (WCET) - 2Кафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.Почему важен WCET• Время выполнения программ играет ключевуюроль при анализе систем реального времени• Это время, например, встречается в формуле:Наихудшеевремя откликаПериодНаихудшее времявыполненияОткуда берутся значения , ?2Простейшая вычислительная задача• Входные данные доступны в моментстарта• Выходные данные готовы в моментзавершения• Нет блокировок в процессе выполнения• Нет синхронизации или обменаданными в процессе выполнения• Время выполнения зависит только от:– входных данных– состояния задачи в момент старта(внешние воздействия отсутствуют)ВходныеданныеСостояниеЗадачаСостояниеВыходныеданные3Наихудшее (максимальное) времявыполненияНаихудшее время выполнения программного кода (worstcase execution time, WCET) – это максимальное время,которое требуется для выполнения• данного фрагмента кода• в данном контексте (входные данные, состояние)• на заданном аппаратном вычислителе4Чем определяется WCETЗадача• Возможныепоследовательностидействий задачи (путивыполнения)• Длительность выполнениякаждого действия накаждом допустимом (т.е.практически возможном)пути выполнения5частотаРаспределение времён выполненияBCETМакс.наблюдаемоевремявыполненияWCETВерхняяоценкаWCETМножество различных времён выполненияНетривиальный анализ путей выполненияСложное моделирование задержек от аппаратуры6Оптимизация программногокода для временно́йпредсказуемостиЧто важнее всего в таймингахработы РВ-систем?• В первую очередь – предсказуемость– Предсказуемый WCET– Также – предсказуемый BCET• Производительность – во вторую очередь• => потребность во временно́ йпредсказуемости:– Аппаратура– Программное обеспечение21Почему важен BCETЖелтая задача: BCET << WCET красная задача нарушает директивный срок23Традиционное программирование• Цель: хорошая производительность в среднем• Стратегия: профилировать и оптимизироватьпроизводительность на наиболее часто встречающихсянаборах входных данных => возможное ухудшениеWCETПричина: сложность неравномерно распределена междунаборами входных данных; оптимизация частыхсценариев приводит к ухудшению производительностина редких сценариях24WCET-ориентированноепрограммированиеСтремимся освободить код от ветвленийв зависимости от входных данныхМинимизируем число действий,выполняемых только для отдельныхнаборов входных данных25Традиционное vs.

WCETориентированное программирование26Алгоритм №1Критерий производительностиТрадиционныйподходАлгоритм №2среднееWCETWCETориентированныйподход27Эксперименты• Традиционный vs. WCET-ориентированный код• Ветвящийся vs. линейный кодРеализованные алгоритмы:• Пузырьковая сортировка• Поиск первого вхождения• Двоичный поиск– одно/два сравнения на каждой итерации2829Эксперименты• Традиционное vs.

WCET-ориентированноепрограммированиеАлгоритмТрадиционноеСреднее WCETWCET-ориентированноеСреднее WCET* В традиционном варианте: без goto; используетсяпризнак раннего завершения30Свойства WCET-ориентированныхпрограмм• WCET меньше, чем у традиционных программ• Анализ путей проще в связи с устранением/сокращениемзависимостей от входных данных• Оценка WCET проще из-за меньшего числа путей выполнения (илиединственного пути)• Меньше разброс времен выполнения => более стабильна работасистемы в целом• Низкая сложность потока управления => хорошо подходит дляуправляющих программ, критичных для безопасности• Нетрадиционные алгоритмы31Стремимся к временно́йпредсказуемостиСокращаем зависимость порядка действий отвнешних факторов Линейный (single-path) код• Нет ветвлений по входным данным• Предикатное выполнение• Акцент на потоке данных (а не на потокеуправления)32WCET-ориентированное программирование +линеаризация кода••••Константное время выполненияНизкий WCETТривиальный анализ путейПростой анализ WCET Полная временна́ я предсказуемость Приемлемая производительность33Линеаризация: код, оптимизированный подсредний случай, замедляется сильнееTavg: 4,1  8(x1,95)Tavg: 5  8(x1,6)34Времена выполненияВременавыполнения кода дои после перехода наWCETориентированноепрограммирование+ линеаризации35Как получить линейный код?Устранить зависимости по данным изпотока управления Аппаратура с константными задержками Линеаризованный кодПредикатное выполнение37Предикатное выполнение…это условное выполнение или невыполнениекоманды в зависимости от значения булевойпеременой, называемой предикатом[Hsu et al.

1986]Выполнение предикатной команды:• Безусловная выборка команды из памяти• Предикат истинен => нормальное выполнение команды• Предикат ложен => команда не изменяет состояниепроцессора38Ветвящийся vs. предикатный кодПример кода:Ветвящийся кодПредикатный код39Аппаратная поддержка предикатноговыполненияПредикатные регистрыКоманды для работы с предикатами (определить,установить, сбросить, загрузить, сохранить)• Предикатные команды– Поддержка полной предикатности: выполнение любых командуправляется предикатами– Поддержка частичной предикатности: лишь некоторое подмножествокоманд могут быть предикатными (например, копирование данных,присваивание значений)40Специфика частичной предикатностиОпережающее выполнение вычислений• Команды, не являющиеся предикатными, выполняютсябезусловно• Их результаты сохраняются во временных переменных• В дальнейшем предикат определят, содержание какой извременных переменных следует использоватьПример:Внимание: команды, вычисляющие значения временныхпеременных, не должны генерировать исключения (пример:деление на ноль, обращение к недопустимому адресу памяти).41Полностью vs.

частично предикатный кодОригинальный кодПолностьюпредикатный код:424344Минимальная поддержка предикатности• Команда условного копирования:Семантика:45If-преобразование с условнымкопированиемИзбегатьпобочныхэффектов46Эмуляция условного копирования• В архитектурах без поддержки предикатности,условное копирование можно эмулировать припомощи операций с битовыми масками.Пример:Допущение: переменные всехиспользуемых типов имеютодинаковый размер47Пример:Пузырьковая сортировка: на входемассив а[SIZE]48Пример:Пузырьковая сортировка: на входемассив а[SIZE]49Пример:Пузырьковая сортировка: на входемассив а[SIZE]50Свойства линейного кода• Каждое выполнение порождает одну и ту же трассукоманд, т.е.

одну и ту же последовательностьобращений к памяти команд.• Анализ путей тривиален – существует единственныйпуть.• Два выполнения, начинающиеся с одинаковогосостояния кэша команд, порождают одинаковыепоследовательности промахов/попаданий в кэшкоманд.51Линейный код и задержкиКаждое выполнение порождает одну и ту же последовательность (атакже количество) выполненных инструкций -> хорошаяоснова для получения фиксированного времени выполнения.Команды с неконстантным, зависящим от данных, временемвыполнения вызывают флуктуации времени выполнениякода.Разные начальные состояния памяти (в т.ч. кэша) могут привести кразличным задержкам при доступе к памяти команд иданных, а значит к различным временам выполнения кода.52Обеспечение константного времени выполненияНе позволяем внешним факторам влиять на:• Последовательность выполняемых команд• Длительность команд Всегда начинать с одного и того же состояния кэша команд,конвейера, логики предсказания ветвлений и т.п. Обеспечивать константные задержки при доступе к данным Обеспечивать константные длительности всех операцийпроцессора Все внешние воздействия (в т.ч.

вытеснение задач) должны бытьпредсказуемымиЧто делать:• Сбрасывать кэши при старте задач• Размещать данные по фиксированным адресам• Избегать сложного вычисления адресов53Константные длительности операцийпроцессора•Все операции процессора должны быть реализованы так, чтобывыполняться за константное время, независимо от значений операндов(пример: целочисленный сумматор всегда отрабатывает за 1 такт)•В частности, предикатные команды должны выполняться за константноевремя. Если предикат ложен, команда выполняется, но её результатыотбрасываются и не изменяют состояние процессора.•У циклически выполняемых команд в коде должны быть константныезначения числа итераций.54Производительность линейногокодаВремена выполнения ветвей, выбираемых в зависимости от входныхданных, суммируются в связи с линеаризацией. Время выполнения линейного кода довольно велико (посравнению с оригинальным), если путь выполнения оригинальногокода существенно зависит от входных данных55Производительность линейного кода(2)Процессоры с длинными конвейерами тратят многотактов на перезаполнение конвейера при ошибочномпредсказании ветвления. Предикатное выполнение может быть «дешевле»ветвления Современные компиляторы и процессоры могутиспользовать предикатное выполнение для улучшенияпроизводительности56Пример: ускорение за счет ifпреобразованияПредикатный кодВетвящийся кодВыполнение в трёхступенчатом конвейере:5 тактов6 тактов4 такта57Свойства процедуры линеаризации кода• Полнота: любой участок кода с ограниченным WCETможет быть линеаризован• В линеаризованном коде путь выполнения –единственный• Анализ WCET тривиален: запустить код и измеритьвремя (при «наихудшем» начальном состояниисистемы)• Код выполняется заметно дольше ветвящегося кода58Времена выполненияВремена выполнениядо и послелинеаризации59Оптимизация WCET на этапекомпиляции6162Наихудший путь• Внимание: в результате оптимизации другой путьможет стать наихудшим63Наихудший путь• Внимание: новый наихудший путь может выполнятьсядольше, чем первоначальный64Или всё-таки замерять?Почему нельзя просто измеритьWCET? Замер времени выполнения на всех путях выполненияреалистичной программы – на практике невозможен При определении тестовой выборки могут быть упущены редкиесценарии выполнения (обработка ошибочных ситуаций и т.п.) Выбранные тестовые данные могут не породить самую длинную(по времени) трассу выполнения Внутреннее состояние процессора на момент старта измеренийможет не быть наихудшимПростые замеры могут послужить источником первоначальной(грубой) нижней оценки WCET66С другой стороны…Не во всех случаях строго необходима безопасная (не заниженная) оценкаWCET• Системы мягкого реального времени (например, мультимедиа)• Системы, устойчивые к редким превышениям директивных сроковДля новой аппаратной платформы быстрее всего можно начать именно замерывремени выполнения (а статические методы анализа аппаратных задержекадаптировать долго)Низкие затраты на аннотирование кода => быстрое получение грубой оценки временивыполненияЗамеры дополняют статический анализ, предоставляя реальные значения задержекЗамеры могут использоваться для уточнения результатов статического анализа WCET• Моделировать некоторые современные процессоры действительно сложно• Для некоторых задач зависимость времени выполнения от входных данных понастоящему сложна (вещественные числа, массивы и т.п.)• Люди из промышленности требуют подтверждения теоретических оценок WCETданными «из жизни»67Оценка WCET с помощью измерений• Информация о таймингах получаетсяпутём измерения времени выполнениякода на реальной целевой аппаратуре• Точки инструментирования кодаформируют наблюдаемые извнесобытия, используемые для старта иТрассазавершения измерений• Трасса выполнения содержитсобираемую совместно информацию опутях в программе и временах ихвыполнения (путь = последовательностьлинейных участков)ВходныеданныеСостояниеКод +аппаратураСостояниеВыходныеданные 68••Необходимо СБРОСИТЬ состояние процессора (кэш, конвейер и т.п.) перед каждым прогономНО: для измерения WCET конкретного пути необходимо специфическое начальное состояниекэша (например, если путь входит в состав второй или более поздней итерации цикла, команды69должны находиться в кэше)Методы инструментирования• Чисто аппаратноеинструментирование• Внешние замерывремени выполненияпри помощипрограммноформируемыхсигналов вовне• Чисто программное(внутреннее)инструментирование70Важные соображения по замерамКак измерить именно то, что нужно:• Инструментирование кода не должно изменять путьвыполнения или время выполнения программынепредсказуемым или неизвестным способом.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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