Наихудшее время выполнения ( 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 на основе измерений дал хорошие результаты как для простого, так и для сложного оборудования, хотя, как и статический анализ, он может страдать от чрезмерного пессимизма в многоядерных ситуациях, где влияние одного ядра на другое трудно определить. Ограничением измерения является то, что оно полагается на наблюдение за наихудшими эффектами во время тестирования (хотя и не обязательно в одно и то же время). Может быть сложно определить, были ли обязательно протестированы наихудшие эффекты.
Существует ряд коммерческих и академических инструментов, реализующих различные формы анализа на основе измерений.
Наиболее активные исследовательские группы находятся в США (American Michigan University), Швеции (Mälardalen, Linköping), Германии (Saarbrücken, Dortmund, Braunschweig), Франции (Toulouse, Saclay, Rennes), Австрии (Vienna), Великобритании (University of York и Rapita Systems Ltd), Италии (Bologna), Испании (Cantabria, Valencia) и Швейцарии (Zurich). В последнее время тема анализа времени на уровне кода привлекла больше внимания за пределами Европы исследовательскими группами в США (North Carolina, Florida), Канаде, Австралии, Бангладеш (MBI LAB и RDS), Королевстве Саудовская Аравия-UQU (HISE LAB), Сингапуре и Индии (IIT Madras, IISc Bangalore).
Первый международный конкурс инструментов WCET состоялся осенью 2006 года. Он был организован Университетом Мелардален и спонсирован ARTIST2 Network of Excellence on Embedded Systems Design. Целью конкурса было изучение и сравнение различных подходов к анализу наихудшего времени выполнения. Участвовали все доступные инструменты и прототипы, способные определять безопасные верхние границы для задач WCET. Окончательные результаты [2] были представлены в ноябре 2006 года на международном симпозиуме ISoLA 2006 в Пафосе , Кипр.
Второе соревнование состоялось в 2008 году. [3]
{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )