Время исполнения в наихудшем случае - Worst-case execution time

Наихудший время выполнения ( WCET ) из вычислительной задачи является максимальная продолжительность времени , задача может предпринять , чтобы выполнить на конкретных аппаратных платформ.

Для чего это используется

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

Например, компьютерной системе, которая контролирует поведение двигателя в транспортном средстве, может потребоваться реагировать на входные данные в течение определенного периода времени. Одним из компонентов, составляющих время отклика, является время, затрачиваемое на выполнение программного обеспечения - следовательно, если время выполнения программного обеспечения наихудшего случая может быть определено, то разработчик системы может использовать его с другими методами, такими как анализ планируемости, чтобы гарантировать, что система реагирует. достаточно быстро.

Хотя WCET потенциально применим ко многим системам реального времени, на практике гарантия WCET в основном используется системами реального времени, которые связаны с высокой надежностью или безопасностью. Например, в бортовом программном обеспечении некоторое внимание к программному обеспечению требуется согласно DO178B, раздел 6.3.4. Все более широкое использование программного обеспечения в автомобильных системах также вызывает необходимость использования WCET-анализа программного обеспечения.

При проектировании некоторых систем WCET часто используется в качестве входных данных для анализа планируемости , хотя гораздо более распространенное использование WCET в критических системах заключается в том, чтобы гарантировать, что предварительно выделенные временные бюджеты в системе с планированием разделов, такой как ARINC 653, являются не нарушено.

Расчет

С первых дней развития встраиваемых вычислений разработчики встраиваемого программного обеспечения использовали:

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

У обоих этих методов есть ограничения. Сквозные измерения ложатся тяжелым бременем на тестирование программного обеспечения для достижения максимально длинного пути; Инструкции по подсчету применимы только к простому программному и аппаратному обеспечению. В обоих случаях запас на ошибку часто используется для учета непроверенного кода, приближения производительности оборудования или ошибок. Часто используется маржа в 20%, хотя для этой цифры используется очень мало обоснований, за исключением исторической достоверности («это сработало в прошлый раз»).

По мере роста сложности программного и аппаратного обеспечения возникла потребность в поддержке инструментов. Сложность становится все более серьезной проблемой как при статическом анализе, так и при измерениях. Трудно судить, какой должна быть допустимая погрешность и насколько хорошо протестирована программная система. Аргументы системной безопасности, основанные на высокой отметке, достигнутой во время тестирования, широко используются, но их становится труднее обосновать, поскольку программное обеспечение и оборудование становятся менее предсказуемыми.

В будущем вполне вероятно, что требование к системам, критически важным для безопасности, будет заключаться в том, чтобы они анализировались с использованием как статических, так и основанных на измерениях подходов.

Соображения

Проблема поиска WCET с помощью анализа эквивалентна проблеме остановки и, следовательно, в общем случае не разрешима. К счастью, для систем, для которых инженеры обычно хотят найти WCET, программное обеспечение обычно хорошо структурировано, всегда завершается и его можно анализировать.

Большинство методов поиска WCET включают приближения (обычно округление в сторону увеличения при наличии неопределенностей), и, следовательно, на практике сам точный WCET часто считается недостижимым. Вместо этого различные методы нахождения WCET дают оценки WCET. Эти оценки обычно пессимистичны, что означает, что предполагаемый WCET, как известно, выше, чем реальный WCET (что обычно является желаемым). Большая часть работы по анализу WCET направлена ​​на снижение пессимизма в анализе, чтобы расчетное значение было достаточно низким, чтобы быть ценным для разработчика системы.

Анализ WCET обычно относится ко времени выполнения отдельного потока, задачи или процесса. Однако на современном оборудовании, особенно многоядерном, другие задачи в системе будут влиять на WCET данной задачи, если они совместно используют кэш, линии памяти и другие аппаратные функции. Кроме того, в анализе WCET следует учитывать такие события планирования задач, как блокирование или прерывание, если они могут произойти в конкретной системе. Следовательно, важно учитывать контекст, в котором применяется анализ WCET.

Автоматизированные подходы

Существует множество автоматизированных подходов к вычислению WCET, помимо описанных выше ручных методов. Это включает:

  • аналитические методы для улучшения тестовых примеров для повышения уверенности при сквозных измерениях
  • статический анализ программного обеспечения («статический» смысл без выполнения программного обеспечения).
  • комбинированные подходы, часто называемые «гибридным» анализом, представляющие собой комбинацию измерений и структурного анализа

Методы статического анализа

Статический инструмент WCET пытается оценить WCET, исследуя компьютерное программное обеспечение, не выполняя его непосредственно на оборудовании. Методы статического анализа преобладали в исследованиях в этой области с конца 1980-х годов, хотя в промышленных условиях сквозные измерения были стандартной практикой.

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

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

Поэтому сертификационные органы, такие как Европейское агентство по авиационной безопасности , полагаются на комплекты для проверки моделей.

Статический анализ дал хорошие результаты для более простого оборудования, однако возможное ограничение статического анализа состоит в том, что оборудование (в частности, ЦП) достигло сложности, которую чрезвычайно трудно смоделировать. В частности, в процессе моделирования могут возникать ошибки из нескольких источников: ошибки в конструкции микросхемы, отсутствие документации, ошибки в документации, ошибки при создании модели; все приводит к случаям, когда модель предсказывает поведение, отличное от наблюдаемого на реальном оборудовании. Обычно, когда невозможно точно предсказать поведение, используется пессимистический результат, который может привести к тому, что оценка WCET будет намного больше, чем все, что было достигнуто во время выполнения.

Получить точную статическую оценку WCET особенно сложно на многоядерных процессорах.

Существует ряд коммерческих и академических инструментов, реализующих различные формы статического анализа.

Измерения и гибридные методы

Основанные на измерениях и гибридные подходы обычно пытаются измерить время выполнения сегментов короткого кода на реальном оборудовании, которые затем объединяются в анализе более высокого уровня. Инструменты учитывают структуру программного обеспечения (например, циклы, ветви), чтобы произвести оценку WCET более крупной программы. Причина в том, что в сложном программном обеспечении сложно протестировать самый длинный путь, но легче протестировать самый длинный путь во многих более мелких его компонентах. Эффект наихудшего случая необходимо увидеть только один раз во время тестирования, чтобы анализ мог объединить его с другими событиями наихудшего случая в своем анализе.

Как правило, небольшие участки программного обеспечения можно измерить автоматически, используя такие методы, как инструментарий (добавление маркеров в программное обеспечение) или с помощью аппаратной поддержки, такой как отладчики и модули трассировки оборудования ЦП. Эти маркеры приводят к трассировке выполнения, которая включает как путь, пройденный через программу, так и время, в которое были выполнены различные точки. Затем трассировка анализируется, чтобы определить максимальное время, которое когда-либо потребовалось для выполнения каждой части программы, каково максимальное наблюдаемое время итерации каждого цикла и есть ли какие-либо части программного обеспечения, которые не были протестированы ( покрытие кода ).

Анализ WCET на основе измерений дал хорошие результаты как для простого, так и для сложного оборудования, хотя, как и статический анализ, он может страдать излишним пессимизмом в многоядерных ситуациях, когда трудно определить влияние одного ядра на другое. Ограничение измерения состоит в том, что оно основано на наблюдении наихудших эффектов во время тестирования (хотя и не обязательно в одно и то же время). Может быть трудно определить, обязательно ли проверялись эффекты наихудшего случая.

Существует ряд коммерческих и академических инструментов, которые реализуют различные формы анализа, основанного на измерениях.

Исследовать

Наиболее активные исследовательские группы находятся в Швеции (Мелардален, Линчёпинг), Германии (Саарбрюккен, Дортмунд, Брауншвейг), Франции (Тулуза, Сакле, Ренн), Австрии (Вена), Великобритании (Йоркский университет и Rapita Systems Ltd), Италии ( Болонья), Испании (Кантабрия, Валенсия) и Швейцарии (Цюрих). В последнее время тема временного анализа на уровне кода привлекла больше внимания за пределами Европы исследовательскими группами в США (Северная Каролина, Флорида), Канаде, Австралии, Бангладеш (MBI LAB и RDS), Королевстве Саудовская Аравия-UQU (HISE LAB) и Сингапур.

Вызов инструмента WCET

Первый международный конкурс инструментов WCET прошел осенью 2006 года. Он был организован Университетом Мелардален и спонсирован ARTIST2 Network of Excellence on Embedded Systems Design. Целью конкурса было изучить и сравнить различные подходы к анализу наихудшего времени выполнения. Участвовали все доступные инструменты и прототипы, способные определять безопасные верхние границы WCET задач. Окончательные результаты были представлены в ноябре 2006 г. на международном симпозиуме ISoLA 2006 в Пафосе , Кипр.

Второй вызов прошел в 2008 году.

Смотрите также

использованная литература

  1. ^ «Наихудшая проблема времени выполнения - обзор методов и обзор инструментов », Вильгельм, Рейнхард и др., Транзакции ACM на встроенных вычислительных системах (TECS), Vol. 7, № 3, 2008.
  2. ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 01.10.2011 . Проверено 15 августа 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка )
  3. ^ "Архивная копия" . Архивировано из оригинала на 2012-02-16 . Проверено 16 августа 2008 .CS1 maint: заархивированная копия как заголовок ( ссылка )

Статьи и официальные документы

внешние ссылки