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

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

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

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

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

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

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

Расчет

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

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

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

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

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

Соображения

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

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

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

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

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

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

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

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

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

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

Сертификационные органы, такие как Европейское агентство по авиационной безопасности, поэтому полагайтесь на наборы для проверки моделей.[нужна цитата ]

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

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

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

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

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

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

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

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

Исследование

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

WCET Tool Challenge

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

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

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

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

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

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

внешняя ссылка