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

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

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

Суммируем оценкидля узлов-потомков2. Умножаем наоценку числаитерацийцикл: 100заголовок48Результат расчёта по дереву• WCET функции foo() равен3800 тактамцикл: 100заголовок49Расчёт WCET по путям• Найти самый длинный путь• Рассматриваем итерации цикла поодной• Подготовить цикл• Убрать обратные дуги• Перенаправить их на50специальные узлы «continue»Расчёт WCET по путям• Самый длинный путь:–A-B-C-E-F-G–7 + 5 + 12 + 4 + 8 + 2 =38 тактов• Суммарное время:– 100 итераций– 38 тактов на итерацию– Итого: 3800 тактов51Расчёт WCET по путямC и F никогда невыполняютсясовместно• Недопустимый путь:• A-B-C-E-F-G• Отбрасываем, ищем следующийпо длине52Расчёт WCET по путямC и F никогда невыполняютсясовместно• Недопустимый путь:• A-B-C-E-F-G• Отбрасываем, ищем следующийпо длине• Новый самый длинный путь:• A-B-C-E-G• 30 тактов• Итого: 3000 тактов53Расчёт WCET по путям:учёт конвейера• Упорядочиваем допустимые путипо убыванию грубой оценки WCET(сумма оценок WCET для участковпутей)• для х из {допустимые_пути}– Вычислить WCETPL(x) с учётом«экономии» δXY от конвейерноговыполнения последовательныхучастков– Если WCETPL(x) больше, чемнаибольшая из грубых оценокWCET для оставшихся путей, илиесли других путей не осталось, тоx – самый длинный (наихудший)путь; стопиначе продолжить цикл54Неявный перебор путей• Implicit path enumerationtechnique (IPET)– Пути выполнения необрабатываются в явном виде• Представление программы– Информация о задержках( )• Значения в узлах: выполнениеучастков• Значение на дугах: экономия засчёт конвейера– Число выполнений ( )55Неявный перебор путейгде совокупность удовлетворяетограничениям:• начальные и конечные условия• структура программы• ограничения на число итераций• прочая потоковая информация56Неявный перебор путей• Методы решения системыограничений:• Целочисленное линейноепрограммирование• Разрешение ограничений(constraint satisfaction)• Результат• Число выполнений дляузлов и дуг• Оценка WCET57Спасибо за внимание!58ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 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Обеспечение константного времени выполненияНе позволяем внешним факторам влиять на:• Последовательность выполняемых команд• Длительность команд Всегда начинать с одного и того же состояния кэша команд,конвейера, логики предсказания ветвлений и т.п. Обеспечивать константные задержки при доступе к данным Обеспечивать константные длительности всех операцийпроцессора Все внешние воздействия (в т.ч.

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

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