Наихудшее время выполнения

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

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

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

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

Хотя WCET потенциально применим ко многим системам реального времени, на практике гарантия WCET в основном используется системами реального времени, которые связаны с высокой надежностью или безопасностью. Например, в бортовом программном обеспечении определенное внимание требуется в соответствии с разделом 6.3.4 DO178C . Растущее использование программного обеспечения в автомобильных системах также приводит к необходимости использования анализа программного обеспечения 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 будет намного больше, чем все, что достигается во время выполнения.

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

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

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

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

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

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

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

Исследовать

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

Инструментальный вызов WCET

Осенью 2006 года состоялся первый международный конкурс WCET Tool Challenge. Он был организован Университетом Мелардалена при финансовой поддержке сети передового опыта ARTIST2 в области проектирования встраиваемых систем. Целью конкурса было проверить и сравнить различные подходы к анализу времени выполнения в наихудшем случае. Участвовали все доступные инструменты и прототипы, способные определить безопасные верхние границы задач WCET. Окончательные результаты ^{[ 2 ]} были представлены в ноябре 2006 года на Международном симпозиуме ISoLA 2006 в Пафосе , Кипр.

Второй вызов состоялся в 2008 году. ^{[ 3 ]}

См. также

Ссылки

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

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

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

[1] « Проблема времени выполнения в наихудшем случае - обзор методов и обзор инструментов », Вильгельм, Рейнхард и др., Транзакции ACM в встроенных вычислительных системах (TECS), Vol. 7, № 3, 2008.

[2] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 1 октября 2011 г. Проверено 15 августа 2010 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[3] «Вызов WCET 2008» . Архивировано из оригинала 16 февраля 2012 г. Проверено 16 августа 2008 г.

[ 1 ]

[ 2 ]

[ 3 ]