close

Вход

Забыли?

вход по аккаунту

?

uploaded 07305B7041

код для вставкиСкачать
На правах рукописи
Федотова Ирина Сергеевна
ПОВЫШЕНИЕ ТОЧНОСТИ ТАЙМЕРОВ ДЛЯ ВСТРОЕННЫХ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ПРОМЫШЛЕННОГО УПРАВЛЕНИЯ НА
ОСНОВЕ OC LINUX
Специальность: 05.13.15 — Вычислительные машины,
комплексы и компьютерные сети
Автореферат
диссертации на соискание учёной степени
кандидата технических наук
Новосибирск — 2017
2
Работа выполнена в Федеральном государственном бюджетном образовательном
учреждении высшего образования «Сибирский государственный университет
телекоммуникаций и информатики» (СибГУТИ)
Научный руководитель:
Фионов Андрей Николаевич
доктор технических наук, профессор
Официальные оппоненты:
Окольнишников Виктор Васильевич
доктор технических наук, ведущий научный
сотрудник; Федеральное государственное
бюджетное учреждение науки Институт
вычислительных технологий Сибирского отделения
Российской академии наук (ИВТ СО РАН)
Достовалов Дмитрий Николаевич
кандидат технических наук, доцент кафедры
автоматизированных систем управления;
Федеральное государственное бюджетное
образовательное учреждение высшего образования
«Новосибирский государственный технический
университет» (НГТУ)
Ведущая организация:
Федеральное государственное автономное
образовательное учреждение высшего образования
«Национальный исследовательский Томский
государственный университет»
Защита состоится 15.02.2018 г. в 15 часов на заседании диссертационного совета
Д 219.005.02 при СибГУТИ по адресу: 630102, г. Новосибирск, ул. Кирова, 86, ауд.
625.
С диссертацией можно ознакомиться в библиотеке СибГУТИ, а также на сайте
https://www.sibsutis.ru/science/postgraduate/dis_sovets/
Автореферат разослан «___»_______________2017 г.
Ученый секретарь
диссертационного совета
к.т.н., доцент
Нечта Иван Васильевич
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследования. Многие современные встроенные
системы реального времени состоят из нескольких приложений управления.
Большинство таких приложений разработано как программные блоки для
микропроцессоров, основная задача которых – управление соответствующими
промышленными установками. Разработка встроенной системы управления
состоит из двух главных этапов: синтез контроллеров и разработка приложений
управления на исполнительной платформе. Синтез контроллера включает в себя
задание правил управления, значений периода, задержки, крайнего срока
выполнения задач. На этапе разработки, в свою очередь, происходит
распределение и планирование вычислительных ресурсов приложения. Данная
работа решает задачи предоставления высокой производительности и
гарантированной безопасности работы приложения и фокусируется на проблемах
эффективности таймерной поддержки встроенных микропроцессоров и оценки
временных характеристик системы.
На сегодняшний день доля использования операционной системы GNU/Linux
в таких областях промышленности как потребительская электроника, управление
промышленным оборудованием, авиационная робототехника, достигает более
50%. Особенно это актуально для встраиваемых устройств с их ограниченными
ресурсами. Для подобных систем GNU/Linux является идеальной операционной
системой, благодаря своим скромным системным требованиям, открытому
исходному коду и возможности использования любых существующих на рынке
встраиваемых процессоров. Однако, при использовании такой ОС в процессе
разработки могут возникать определённые сложности. Во-первых, известные
недостатки временной поддержки стандартной библиотеки Си GNU усугубляются
на встроенной версии Linux. Например, если в рамках архитектуры x86 издержки
на переход контекста будут составлять десятки наносекунд, то для встроенных
архитектур стоимость такого вызова может достигать уровня миллисекунд. Вовторых, для встроенных платформ используется более широкий спектр архитектур
и менее стандартизованных сред, что также создаёт определённые сложности.
Так, например, на каждой встроенной архитектуре присутствуют уникальные
регистры основного счётчика времени, которые отличаются своими
характеристиками и возможностями, что затрудняет использование одного
универсального интерфейса для измерений. В-третьих, доступ ко всем регистрам
на встроенных платформах осуществляется через защищённое пространство ядра.
Несмотря на выше упомянутые сложности встроенных микрокомпьютеров, к
их применению накладываются дополнительные требования надёжности,
безопасности и возможности работы в режиме реального времени, особенно в
области управления промышленными установками. В таких системах управления
каждый
компонент
обладает
определёнными
функциональными
4
характеристиками, при этом временные ограничения должны быть соблюдены как
на локальном уровне каждого компонента, так и в контексте всей системы.
Современные подходы временного анализа в некоторых условиях уже могут быть
применены на уровне компонентов, согласно модели «чёрного ящика».
Значительный вклад в развитие теории и практики временного анализа
вычислительных систем и систем реального времени внесли известные учёные,
среди которых: R. Wilhelm, G. Buttazzo, G. Lipari, A. Burns, S. Edgar, L. Santinelli, J.
Abella, L. Cucu-Grosjean, T. Nolte, I. Bate, F. Cazorla, E. Quiñones, G. Bernat, E.
Mezzeti, T. Vardanega, S. Altmeyer, S. Hissam, J. Hansen, G. Moreno, A. Colin, I.
Puaut, P. Puschner, E. Bini, G. Lipari, L. Abeni, H. Falk, С. Сорокин, B. Brandenburg и
др. На основе их работ предлагаются различные решения главной задачи теории
реального времени и временного анализа — задачи предсказания временных
характеристик, а именно, нахождения значения наихудшего времени выполнения
системы, т.н. WCET (Worst Сase Execution Time). Новый перспективный подход
вероятностного анализа временных характеристик системы был предложен в 2001
году и носит название MBPTA (Measurement-Based Probabilistic Timing Analysis).
Однако, только с 2013 года начались активные исследования способов его
применения, поиск недостатков и методов усовершенствования. При этом данный
подход до сих пор применялся только к локальным компонентам приложения или
в условиях т.н. бенчмарков. Другими словами, обеспечение временных гарантий
системы в целом нуждается либо в новых подходах, либо в рассмотрении
совокупности свойств так, чтобы гарантии, получаемые на уровне каждого
компонента, могли быть объединены в глобальную оценку.
Цель работы и задачи исследования. Целью работы является
экспериментальное исследование эффективности таймерной поддержки
встроенных микропроцессоров архитектуры ARM Cortex A, разработка методов
повышения точности таймеров и методологии оценки временных характеристик
систем управления на базе микропроцессоров.
В соответствии с целью определены следующие задачи исследования:
1. Теоретический анализ таймерной поддержки как на уровне аппаратного
обеспечения, так и на уровне операционной системы GNU/Linux для встроенных
микропроцессоров архитектуры ARM Cortex-A, и разработка подходов по
увеличению точности и эффективности работы таймеров в различных условиях.
2. Экспериментальные
исследования
по
оценке
эффективности
существующих методов в рамках временного анализа MBPTA для
прогнозирования времени выполнения исходного кода и разработка подходов по
улучшению оценки прогнозирования времени и получения значения наихудшего
времени выполнения WCET.
3. Разработка на основе временного анализа MBPTA метода оценки
временных характеристик по отношению к системе управления в целом, а именно,
кластеризация на компоненты и сложение оценок для каждого блока.
5
4. Применение разработанного метода на реально существующих системах
управления при различных детерминированных и недетерминированных
сценариях в целях экспериментального исследования и анализа полученных
результатов.
Методы исследования. Для решения поставленных задач использовались
методы временного анализа MBPTA, а также методы теории вычислительных
систем, теории алгоритмов, теории вероятностей и математической статистики,
теории экстремальных значений, функционального анализа и методов
математического анализа.
Положения и результаты, выносимые на защиту, соответствуют
следующим пунктам паспорта специальности 05.13.15 – «Вычислительные
машины, комплексы и компьютерные сети»:
1. Пункт 2 «Теоретический анализ и экспериментальное исследование
функционирования вычислительных машин, комплексов и компьютерных сетей с
целью
улучшения
их
технико-экономических
и
эксплуатационных
характеристик». Произведён теоретический анализ и экспериментальное
исследование временных характеристик встроенных вычислительных машин.
Создан инструмент, повышающий эффективность работы и точность
современных аппаратных таймеров для встроенных вычислительных систем
высокой производительности. Произведено экспериментальное исследование
влияния виртуализации аппаратных таймеров на их точность. В условиях
виртуализации предлагаемые методы таймерной поддержки показывают до двух
раз более низкую временную стоимость чтения таймера и более 1000 раз, с уровня
миллисекунд до микросекунд, меньшее значение времени промаха сна, чем
функции из стандартной библиотеки Cи GNU для версии ядра Linux 4.2.
2. Пункт 6 «Разработка научных методов, алгоритмов и программ,
обеспечивающих надёжность, контроль и диагностику функционирования
вычислительных машин, комплексов и компьютерных сетей». Экспериментально
обоснован выбор вероятностного подхода для прогнозирования временных
характеристик аппаратных таймеров. Метод впервые применён для предсказания
времени чтения аппаратного таймера. Предложена методика кластеризации и
сложения вероятностных оценок для отдельных блоков системы управления. С
помощью модельных экспериментов показана согласованность и эффективность
методики на работающих системах. Прогнозирование времени с помощью данной
методики находится ближе в несколько десятков раз к реальным значениям,
полученным на базе многочисленных эмпирических наблюдений, чем
прогнозирование времени, основанное на модели «чёрного ящика».
Научная новизна результатов работы заключается в том, что в ней
впервые:
1. Разработан механизм повышения точности таймеров для встроенных
систем на базе процессора ARM Cortex-A до 4 раз при получении значения
6
времени и более чем в 1000 раз при вызове функции ожидания процесса при
сохранении ресурсов ЦПУ по сравнению с системными вызовами стандартной
библиотеки Cи GNU для версии ядра Linux до 4.2.
2. Впервые показаны особенности применения метода MBPTA к отдельным
элементам системы управления вместо модели «чёрного ящика».
3. Разработан метод кластеризации системы управления для оценки точности,
впервые предложен математический метод сложения вероятностных оценок
отдельных блоков системы.
4. Показана применимость предложенных методов на существующих
промышленных системах реального времени. Произведена оценка эффективности
метода сложения вероятностных оценок блоков при различных сценариях
выполнения, которая в большей степени соответствует эмпирическим
наблюдениям, чем другие известные оценки.
Теоретическая и практическая значимость работы.
1. Разработана программная библиотека HighPerTimer, предоставляющая
унифицированный интерфейс доступа к известным аппаратным счётчикам
времени встроенных процессоров на базе ARM Cortex-A через пользовательское
пространство операционной системы GNU/Linux.
2. Произведена оценка производительности виртуальных таймеров для
современных моделей виртуализации компьютеров на базе процессоров Intel при
помощи разработанного интерфейса библиотеки HighPerTimer. Полученные
результаты позволяют говорить о возможности использования библиотеки в
приложениях, разрабатываемых для виртуальных машин.
3. Полученные результаты применения анализа MBPTA и подхода сложения
оценок временных характеристик для систем управления промышленными
установками позволяют оптимизировать дальнейшую разработку приложений и
повысить предсказуемость поведения системы.
Внедрение результатов работы. Разработанные в диссертации методы и
алгоритмы были успешно внедрены в следующие проекты, что подтверждается
соответствующими актами:
• Программная библиотека HighPerTimer была успешно интегрирована в
коммерческий протокол для высокоскоростной передачи данных Reliable MultiDestination Transport (RMDT) компании Dexor GmbH. Кроме того, библиотека
интегрирована в коммерческие решения компании Axxeo GmbH в рамках
приложения управления действующих ветрогенераторов.
• Алгоритмы оценки прогнозирования временных характеристик и метод
сложения оценок блоков временных характеристик, представленные в работе,
используются Институтом Медицины и Техники IMT (Institut für Medizin und
Technik e.V., Koethen, Germany) для проектов BitBooster и CloudBDT, а также в
транспортных решениях лаборатории Future Intenet Lab Anhalt (FILA) и Dexor
GmbH.
7
• Представленные в диссертации материалы используются в курсе лекций
«Системное программирование» и «Системы реального времени» в Университете
Прикладных Наук Анхальт, Кётен, Германия (Anhalt University of Applied
Sciences).
Личный вклад. Выносимые на защиту результаты получены соискателем
лично. В совместных работах постановки задач и разработка методов их решения
осуществлялись при непосредственном участии соискателя.
Степень достоверности и апробация результатов подтверждаются
проведёнными экспериментами и моделированием, согласованностью с данными,
имеющимися в отечественной и зарубежной литературе. Результаты работы
докладывались и обсуждались на международных и российских научных
конференциях, в их числе: the International Conference on Networking and Services
(ICNS-2013, Португалия), международная суперкомпьютерная конференция и
конференция молодых учёных «Научный сервис в сети интернет» (2013, г.
Новороссийск), the Scientific and Practical Conference «Information and Measuring
Equipment and Technology» (2013, г. Томск), the International Conference on Applied
Innovations in IT (ICAIT-2014, ICAIT-2017, Германия), Российская научнотехническая конференция «Современные проблемы телекоммуникаций», (2015, г.
Новосибирск), Networking Day at Open Source Automation Development Lab
(OSADL, 2015, 2016, Германия), the Advanced Doctoral Conference on Computing,
Electrical and Industrial Systems (DoCEIS-2017, Португалия), the International
Conference on Measurement Instrumentation and Electronics, (ICMIE-2017, Чехия),
the IEEE International Conference on Smart Technologies (EUROCON-2017,
Македония), а также на научных семинарах в Сибирском государственном
университете телекоммуникаций и информатики и Институте физики
полупроводников СО РАН.
Публикации. Автором по теме диссертации опубликовано 12 работ, в числе
которых 4 статьи в журналах, из которых 2 входят в список ВАК и 2 журнала
индексируются в Scopus, Web of Science и публикуются в издательстве Springer.
Структура и объем работы Диссертация состоит из введения, четырёх глав,
заключения, списка литературы из 99 наименований. Общий объем диссертации –
113 страниц. Работа содержит 50 рисунков и 26 таблицы.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы исследования и степень её
разработанности, сформулированы цели и задачи работы, отражена её научная
новизна, теоретическая и практическая значимость; представлены положения,
выносимые на защиту, а также степень достоверности и апробация результатов.
Первая глава посвящена проблематике измерения времени и получения
временных
интервалов
на
современных
вычислительных
системах.
Рассматриваются особенности работы аппаратных таймеров на встроенных
8
системах и проводится анализ факторов, влияющих на итоговую точность. Кроме
того, рассматриваются модели прогнозирования времени выполнения исходного
кода и, в частности, применение вероятностного подхода.
В отличие от универсального компьютера, встроенная система выполняет
одну или несколько предопределённых задач с конкретными требованиями,
непосредственно взаимодействует с объектом управления и объединена с ним
единой конструкцией. Элементы подобной системы практически всегда
ограничены по ресурсам. Однако при этом особенностью их функционирования
является необходимость работы в реальном времени, что подразумевает
соблюдение принципов надёжности, безопасности и гарантированного времени
реакции. В этом контексте задача системы реального времени – это отправка
управляющих сигналов в ответ на информацию, поступающую от датчиков в
гарантированные промежутки времени. К главным механизмам системы
реального времени относится основной аппаратный таймер, сторожевой таймер,
система прерываний, часы реального времени, система контроля питания и
средства понижения энергопотребления, встроенная FLASH-память и контроллер
прямого доступа к ней. Все перечисленные компоненты по-своему оказывают
влияние на результирующее время реакции.
Типичный анализ временных свойств системы на уровне кода – это анализ
наихудшего времени выполнения (WCET). Классический способ, который до сих
пор используется в некоторых областях промышленности, это т.н. непрерывные
измерения. Метод заключается в создании большого набора данных времени
исполнения программы с различными входными параметрами. Такие измерения
полезны, когда именно среднее значение представляет наибольший интерес.
Однако такой подход может быть выполним только для программ с малым
количество ветвлений. При этом, для большинства современных приложений
количество ветвлений в исполняемом коде слишком велико для исчерпывающих
измерений. Это означает, что полученное путём измерений время будет часто
недостаточно точным для надёжной оценки WCET, поэтому в таких случаях часто
к пороговому значению добавляют дополнительный коэффициент. При этом
слишком высокое значение коэффициента введёт к неэффективному расходу
ресурсов, а при слишком низком его значении понижается надёжность системы.
Следовательно, при данном подходе WCETmeasured <= WCETexact (рисунок 1).
Альтернативный способ оценки WCET – это статический анализ, который
получает временные характеристики путём статического анализа свойств
программы с использованием симулятора. Учитывая эти параметры и корректный
анализ системы, данный подход позволяет получить достаточно надёжную оценку,
которая больше или равна реальному WCET. Таким образом, определённый
уровень абстракции влияет на результирующее значение и в результате
рассчитывается более пессимистичная оценка WCETexact <= WCETstatic..
9
Рисунок 1 – Представление проблемы расчёта значения наихудшего выполнения WCET
Вышеописанные проблемы статического подхода и метода, основанного на
измерениях, решаются с помощью вероятностных моделей, которые гарантируют
наиболее точную оценку WCETpredicted или pWCET, учитывающую сложность
программной и аппаратной части. Вероятностный метод основан на теории
экстремальных значений (ТЭЗ), которая занимается прогнозированием
максимальных (или минимальных) значений случайных переменных. Теория
экстремальных значений утверждает, что любое возможное событие имеет
вероятность свершиться отличную от нуля. Данная теория хорошо
зарекомендовала себя при прогнозировании событий, сила воздействия которых
значительно превышает ранее наблюдаемые величины. Значение вероятности
этого события определяется на основе теоремы экстремальных значений, так же
известной как теорема Фишера–Типпета–Гнеденко. Теория характеризует
максимально стабильную функцию распределения, где {X1, X2, ..., Xn} –
совокупность n независимых одинаково распределённых случайных величин и Mn
= max{X1, X2, ..., Xn}. Согласно этой теореме, если F – функция невырожденного
предельного распределения и существуют такие числовые последовательности
(an, bn), что an > 0 и limn→∞P([Mn− bn] / an ≤ x) = F(x), то F называется функцией
экстремальных значений и принадлежит к одному из трёх экстремальных типов:
Фреше, Ве́йбулла или Гумбеля. Bсе эти три распределения объединяются в
семейство распределений дополнительной кумулятивной функции (CCDF),
известное как обобщённое распределение экстремальных значений (GEV), и
характеризуются следующими параметрами: µ ∈ R – размещения, σ > 0 –
масштаба и ξ ∈ R – формы. В зависимости от параметра формы ξ GEV имеет три
вида распределений, описываемых следующими CDF: Тип I – распределение
Гумбеля (ξ = 0) с экспоненциальным и более быстро убывающим правым
хвостом:
(1)
10
Тип II – Фреше (ξ = 1/α > 0) характеризуется степенным «хвостом»:
;
(2)
Тип III – Вейбулла (ξ = –1/α > 0), базовое распределение имеет невесомый
верхний «хвост»:
;
(3)
где x – это общее количество исходов, y – количество экстремумов, превышающих
некое пороговое значение u c y = x – u.
Оценивая параметры µ, σ и ξ, получаем итоговое обобщённое распределение
экстремальных значений. Например, если параметр формы ξ = 0, то значения в
исходном наборе данных принадлежат распределению Гумбеля, что в
большинстве предыдущих работ применялось для решения задачи нахождения
pWCET. Однако, поскольку фактически ограничений на принимаемые значения
параметром ξ нет, предлагается проверять все три возможные варианта
распределения, что позволит получить более корректную оценку параметра.
Во время эксперимента создаётся набор данных из n = 106 значений времени
доступа и чтения аппаратного таймера. Алгоритм доступа к счётчику использует
библиотеку HighPerTimer, описанную в главе 2. В качестве примера встроенной
платформы рассматривается Atmel SamaA5D4 на базе одноядерного процессора
ARM Cortex A5 с использованием ядра Linux версии 4.4.11. Данный процессор
имеет 32-битный счётчик, работающий с частотой 11 MГц. В ходе эксперимента
были получены следующие данные, представленные в виде распределения
дополнительной функции (CCDF) на рисунке 2, а также основные статистические
свойства в таблице 1.
Рисунок 2 - Графическое представление значений времени чтения таймера
а) основные статистические свойства; б) распределение функции CCDF
11
Таблица 1 - Статистические свойства исходного набора данных
Количество измерений
30*106
Время выполнения эксперимента
27 мин
Среднее время выполнения
5.71 тактов = 0.519 мксек
Стандартное отклонение
24.384 тактов = 2.217 мксек
Максимальное значение
65943 тактов = 5994.7 мксек
Минимальное значение
5 тактов = 0.455 мксек
Таким образом, для решения задачи оценки наихудшего значения времени
исполнения программного кода предлагается использовать следующий алгоритм:
Шаг 1. Выборка экстремальных значений из исходного набора данных. В
данной работе применяется метод The Peak over Threshold (POT), который в
сравнении с альтернативным методом Block Maxima (BM) позволяет использовать
данные более эффективно. Однако, вопрос о выборе порогового значения в
методе POT является одной из центральных задач практического применения ТЭЗ.
Метод основан на второй важной теореме теории экстремальных значений
Пикандса–Балкема–деХаана. Согласно данной теореме, функция распределения
случайной величины (которая удовлетворяет условиям теоремы Фишера–
Типпета–Гнеденко) превышений данного порога называется условной функцией
распределения превышений
; (4)
и должна стремиться к обобщённому распределению Парето
;
;
:
(5)
(6)
где x0 – супремум области определения исходной функции F; y ≥ 0 при ξ ≥ 0, и
0 ≤ y ≤ –σu/ξ при ξ < 0; и σu = σu0 + ξ(u − u0).
Шаг 1.1. Выбор порогового значения. На данном этапе применяется метод
графической диагностики с использованием графиков стабилизации параметров
Mean Residual Life Plot и Parameter Stability Plot.
Шаг 1.2. Фильтрация исходного набора данных согласно выбранному порогу.
Шаг 2. Проверка обобщённых экстремальных распределений типа Фреше,
Ве́йбулла и Гумбеля. Для наиболее корректной проверки собирается тестовая
статистика на основе критериев согласия X-квадрата, информационного критерия
Акаике (AIC), Байесовского информационного критерия (BIC), а также QQграфика. Если ни одно из проверяемых распределений не подходит, то необходимо
вернуться к шагу 1.1 и увеличить пороговое значение.
Шаг 3. Оценка параметров подходящих распределений µ, σ и ξ.
12
Шаг 4. Проверка гипотез теории экстремальных значений на независимость и
однородность распределённых случайных величин. Если обе гипотезы
подтверждаются, то проекция хвоста распределения ТЭЗ может считаться
безопасной для корректной оценки pWCET.
Шаг 4.1. Проверка гипотезы на независимость.
Шаг 4.2. Проверка гипотезы однородности распределений. Это свойство
реализуется комбинацией аппаратного обеспечения с подходящими методами
рандомизации.
Шаг 5. Вернуть значение WCET на основе параметров µ, σ, ξ и вероятности
риска p = P(WCETsafe > WCETexact). Количественная оценка WCET на языке
классической статистики, например, в области финансов, часто упоминается как
термин значения риска (Value-at-Risk, VaR) для измерения рыночного риска.
Соответственно, для применяемого случая, значение WCET выводится на основе
оценочных параметров следующим образом:
(7)
где k – это общее количество экстремальных значений, превышающих пороговое
значение u и принадлежащих хвосту распределения. Исходная вероятность риска
p определяется как вероятность того, что исполнение конкретной задачи превысит
её значение WCET для текущего состояния, при том что предыдущие задачи
оставались в пределах этой границы. Для данной работы была выбрана
вероятность риска уровня 10-9 < p < 10-7 на основе стандартизации о портативных
электронных устройствах (Portable Electronic Devices standarts, PED),
используемой в системах управления летательными аппаратами. Таким образом,
последовательно применяя выше описанный алгоритм к операции чтения
значения счётчика на платформе Atmel SAMA5D4, базируемой на платформе
ARM Cortex A5, были получены следующие данные итоговой оценки WCET
(таблица 2):
Таблица 2 - Результаты применения ТЭЗ к блоку get_time для ARM Cortex A5
σ
µ
Гумбель 12247.56 12968.35
Фреше
10542.5
-1539.6
ξ
0
(WCET ; 10−7)
(WCET ; 10−8)
(WCET ; 10−9)
27968.09 тактов = 56169.13 тактов =
0.002542 сек
0.005106 сек
84370.18 тактов =
0.007670 сек
1.351 124185.2 тактов = 2898825 тактов =
0.011289 сек
0.263530 сек
65126941 тактов =
5.921 сек
Основная проблема задачи оценки риска – это задача определить значения
той или иной активности, которые практически не могут быть измерены
экспериментальным путём. Поэтому, чтобы предсказать потенциальные значения,
используется дополнительная кумулятивная функция CCDF обобщённого
13
распределения Парето. На рисунке 3 представлена сходимость распределений
статистики Гумбеля и Фреше к прогнозируемым значениям. По оси x находится
значение pWCET выраженное в тактах процессора, а ось y демонстрирует
соответствующую вероятность.
Рисунок 3 – Оценка верхней границы распределений Гумбеля и Фреше
Согласно таблице 2, оценки WCET для обоих распределений существенно
различаются. Слишком пессимистические результаты Фреше практически менее
полезны: для вероятности отказа p = 10-9 граница равна 5.921 сек. Распределение
Гумбеля сходится к 0 быстрее, чем Фреше, и уменьшает пессимизм порогов
WCET. Кроме того, график стабильности параметров формы оценивает
максимальную вероятность ξ в диапазоне пороговых значений и подтверждает
гипотезу о том, что данные соответствуют распределению Гумбеля с ξ = 0 c
большей вероятностью.
Во второй главе предлагаются методы повышения точности и
эффективности измерений времени, в частности предлагается библиотека
поддержки высокой точности HighPerTimer. Оптимизация временных
характеристик обосновывается на эмпирических данных, полученных на
примерах встроенных систем на базе процессора ARM.
Современные ПК-платформы поставляются с различными аппаратными
таймерами, имеющими различные характеристики. Самым популярным в домене
ПК является 64-разрядный счётчик TSC, считывающий тактовые циклы
процессора с момента последнего включения. Как правило, к таймерам на ПКплатформах можно обращаться и из пространства ядра и из пользовательского
пространства. Между тем, механизм тайминга на ARM архитектурах выглядит
более сложным. Производительность времени на ARM ограничена 32-разрядными
регистрами с относительно низкой частотой. Например, на ядре микропроцессора
AM335x ARM Cortex A8 счётчик работает с частотой 25 MГц и разрешением 41
нсек. Следовательно, его переполнение происходит чаще чем каждые 3 минуты.
Это означает, что без дополнительной обработки переполнений таймера
14
приложение, работающие на подобных платформах, не может считаться
надёжным. Более того, в случае процессора ARM Cortex A9 системный таймер
имеет частоту 32.768 КГц с разрешением 30.518 мксек соответственно, что
фактически ограничивает измерения до интервалов точностью более 30 мксек.
Кроме того, определённые ограничения управления памятью ARM позволяют
обращаться к регистрам только из защищённого пространства ядра.
Библиотека поддержки высокой точности HighPerTimer представляет собой
С++ интерфейс для сбора значений времени из пользовательского пространства
Linux. На этапе инициализации библиотеки наиболее быстрый и надёжный
источник времени, доступный на данной платформе, присваивается к объекту
библиотеки. При этом, обходя сложность разнообразия аппаратных таймеров для
различных архитектур, библиотека берёт на себя идентификацию платформы и
соответственно источника таймера. Дальнейшее взаимодействие объекта HPTimer
происходит напрямую с регистрами времени, избегая стандартных системных
вызовов GNU/Linux (как clock_gettime()). На встроенных процессорах для доступа
к регистрам таймера разработан дополнительный драйвер устройства, который
загружается заранее как модуль, открывая доступ из пространство ядра.
Библиотека также обрабатывает возможные переполнения счётчика, предоставляя
максимально точное значение времени. Краткое сравнение результатов стоимости
обращения к таймеру и получения времени приведено в таблице 3. В контексте
работы,
был
использован
вызов
clock_gettime()
с
параметром
CLOCK_MONOTONIC – часы, которые представляют собой абсолютное
истекшее время некоторой точки в прошлом.
Таблица 3 - Примеры использования системного вызова и вызова библиотеки
HighPerTimer для чтения счётчика
ЦПУ
Частота
программных
часов
Стоимость системного
вызова, мксек
Стоимость
вызова HPTimer,
мксек
Intel® Core™ i7-2600
1600 MГц
0.031
0.017
Intel® Core™ i5-3337U
1800 MГц
0.044
0.019
AMD Opteron™ 4238
3300 MГц
0.061
0.031
AMD Athlon™ X2 BE-2350
1000 MГц
1.117
1.063
VIA Nano X2 U4025
1067 MГц
0.102
0.038
ARM Cortex A8
24 MГц
0.923
0.294
ARM Cortex A9
32.768 KГц1
–
0.508
ARM Cortex A5
11 MГц
1.280
0.479
Ещё одним важным преимуществом использования библиотеки HighPerTimer
1 Библиотека HighPerTimer в данном случае обращается к альтернативу счётчику с частотой 19 MГц
15
является значительно улучшенная точность функции сна sleep(). В контексте этой
работы используется термин «промах» времени сна, который обозначает задержку
пробуждения от синхронного сна, а его значение – это разность во времени между
фактическим моментом возврата после сна и ожидаемым моментом пробуждения.
Хотя в версии ядра Linux 2.6 произошли значительные изменения дизайна
таймеров, тем не менее, даже в версиях ядра 4.x промах все ещё находится в
диапазоне 50 мксек (для платформы ПК) и на уровне 9000–100 мксек (для
процессоров на ядре ARM, см. таблицу 4). В связи с этим для реализации точного
сна в приложениях управления часто вставляют имплементацию ожидания
процесса прямо на ЦПУ и за счёт 100% использования ресурсов системы
достигается снижение значения промаха.
Таблица 4 – Сравнение значений промахов при ожидании процесса на 10 мксек
на встроенных микроконтроллерах
ЦПУ
Системный вызов usleep, мксек
Сон библиотеки HPTSleep, мксек
ARM Cortex A8
91.536
0.884
ARM Cortex A9
85.086
1.131
ARM Cortex A5
40.820
1.268
Библиотека HighPerTimer, в свою очередь, предоставляет собственные
функции сна, где накладные расходы процессора во время ожидания остаются на
уровне 1 – 1.89%, а преимущества точного времени возобновления процесса при
длительных ожиданиях сохраняются. В таблице 4 приведены значения промахов.
Поскольку GNU/Linux – это также родная операционная среда для любых
возможных решений виртуализации, крайне важно также рассмотреть влияние
виртуализации аппаратных таймеров на измерения времени и выполнение
задержек процесса. Во второй главе дополнительно описано исследование этой
области в том числе и на стандартных ПК-платформах. Исследование было
произведено под различными нагрузками виртуальной и главной машины:
нагрузкой на ЦПУ, на модуль ввода-вывода (далее упоминается как сценарий
diskmemload) и в холостом режиме. В качестве виртуальных модулей были
выбраны VMware ESXi, когда встроенный гипервизор работает непосредственно
на аппаратуре серверов, и QEMU / KVM, когда гипервизор работает поверх
базовой операционной системы. Также были рассмотрены случаи виртуализации
(i) в масштабах хостинга, когда со стороны провайдеров выделяются серверные
ресурсы на несколько виртуальных машин, и (ii) в масштабах предприятия, когда
используется выделенный сервер и критически важное приложение, работает под
управлением собственного экземпляра ОС. Все тесты выполнялись на платформе
с требованием к процессору поддержки технологии аппаратной виртуализации
Intel VT/AMD-V. Для тестирования использовался процессор Intel® Core™ i7-860
16
@ 2,80 ГГц, обладающий 4 физическими ядрами вместе с 8 ГБ ОЗУ. Все
измерения на хостах и гостевых операционных системах были выполнены на
Ubuntu 14.04.4 LTS, версия ядра 4.2.0-34-generic со стандартными
конфигурациями планирования. Измерения проводились в системе с
инвариантным счётчиком TSC с постоянной скоростью. Режим Hyper-threading
был отключён, чтобы добиться сериализованного исполнения инструкций. В
результате измерений и анализа данных были сделаны различные выводы,
наиболее важные из них следующие: (i) для всех видов нагрузок, независимо от
количества виртуальных экземпляров, вызов чтения времени с использованием
библиотеки HighPerTimer показывает как минимум в два раза меньшее значение
среднего и медианы, чем системный вызов clock_gettime() при настройке часов
CLOCK_MONOTONIC. (ii) Средние значения данных, полученных в ходе
экспериментов при загрузке ЦПУ, растут с количеством виртуальных машин. Это
доказывается значительным ростом высоких и редких выбросов. Для любых
остальных нагрузок диапазон 99 % результатов остаётся стабильным с
соответствующим методом учёта времени. (iii) Средние значения данных из
экспериментов с HPTSleep имеют примерно в тысячу раз меньшее время простоя,
чем функция usleep() для любого типа нагрузки. Кроме того, для случая, когда
один виртуальный экземпляр находится на аппаратном обеспечении в режиме
хостинга, эксперименты с функцией usleep() показали очень неустойчивое
поведение: виртуальные машины начинают одновременно «падать» после
примерно 24–30-ого экземпляра. Это поведение хорошо прослеживается на
рисунке 4, где графически рассмотрено влияние типа нагрузки на значение
промаха в зависимости от метода ожидания процесса.
Рисунок 4 – Средние значения промаха при системном вызове usleep() и при вызове HPTSleep()
для различных видов нагрузок в режиме хостинга
17
Hапример, чёрная линия на рисунке 4, которая соответствует средним значениям
промаха в холостом режиме при методе usleep(), достигает номера 29
виртуального экземпляра и находится в диапазоне десятков микросекунд. Тёмнокрасная линия, показывающая зависимость средних значений промахов от
количества виртуальных машин, находится на уровне 100 нсек и демонстрирует
работоспособность даже при 50 работающих виртуальных экземплярах. Данная
ситуация повторяется под нагрузкой на интерфейс ввода/вывода (голубая и
фиолетовая линия). Соответственно, полученные результаты указывают на то, что
настоятельно не рекомендуется использовать функцию usleep() в критически
важных приложениях в облачной среде.
Третья глава посвящена разработанной методике сложения оценок
временных характеристик для отдельных блоков системы управления. Рассмотрим
простейшую систему управления, задача которой состоит в периодическом
отправлении сигнала управляющему устройству. Представим условно всю
систему в виде трёх компонентов, где get_time() – получение времени или чтение
значения с аппаратного таймера, do_control() – отправка сигнала, get_time() –
повторное получение времени. Как правило, операция отправки сигнала
do_control() вызывается периодически в цикле вместе с функцией ожидания. Идея
предлагаемого метода состоит в кластеризации системы на отдельные блоки,
оценивании вероятности возникновения выброса в каждом блоке, «сложении»
полученных оценок и расчёта итогового значения WCET всей системы.
Пусть каждое измерение Xi в дискретный момент времени i записывается в
массив τ так, чтобы ∀i, τ(i) = Xi. Длина массива τ обозначается n. Для X
используются три эквивалентных представления, каждое из которых является
функцией распределения вероятности. Для всего возможного времени выполнения
x ∈ Ω существует кумулятивная функция распределения (CDF) FX(x) =P(X ≤ x),
дополнительная кумулятивная функция распределения (CCDF) FX(x) = P(X > x) =
1 – FX(x) и функция вероятности (PMF) fX(x) = P(X = x) (для непрерывной
случайной величины fX(x) = FX(x)). Тогда дискретная случайная величина X,
основанная на измерениях времени, называется профилем времени выполнения
задачи τ и выражается парой <временной вектор, вероятностный вектор>.
Временной вектор содержит все возможные задержки запроса и соответственно
для каждой задержки вектор вероятности содержит связанную с ним вероятность
появления. Тогда для Xi имеется ETP(Xi) =
, где
,
, вместе с
.
Таким образом для получения оценки времени выполнения всей системы
предлагается воспользоваться следующим алгоритмом:
Шаг 1. Разбить профиль выполнения на компоненты – последовательно
выполняемые задачи по признаку независимых источников их задержек.
Шаг 2. Для каждого блока подготовить профиль выполнения ETP(Xi) =
.
Шаг 2.1. Создание исходного набора данных в массиве τ длиной по крайней
18
мере до n=105 путём измерений времени выполнения каждого блока отдельно.
Шаг 2.2. Построение гистограммы времени выполнения и подготовка
функции плотности вероятности.
Шаг 3. Рассчитать комбинированный профиль путём дискретной свёртки (⊗)
PDF функций каждого блока. Так, например, для двух блоков Ri = {1,2} с ETP
,
свёрнутый профиль определяется как , где
.
Шаг 4. На основе полученного комбинированного профиля создать массив
значений из τ(j) = Xj возможных исходов.
Шаг 5. Применение вероятностного подхода к элементам массива τ(j) и
расчёт значения WCET(tj, pj).
Дополнительно предлагается сравнить итоговую оценку WCET(tj, pj) с
элементарным сложением WCET(ti, pi) для каждого блока отдельно, а именно,
например, при общей вероятности риска p = 10-9 должно выполняться равенство
WCET(tj, p) ≤ max(WCET(t1, p) + WCET(t2, p) + WCET(t3, p)). Следует учесть
трудоёмкость операции свёртки и её некоторые свойства: операция ассоциативна,
коммутативна и может быть обобщена на любое число переменных.
Четвёртая глава посвящена описанию экспериментальной оценки
применения предложенной методики сложения вероятностных характеристик к
прогнозированию времени работы приложения управления. Рассматриваются три
возможных сценария: (i) система управления, построенная на основе
интегральной схемы Timer NE555; (ii) электромеханического реле Songle SRD05VDC-SL-C; и (iii) система мониторинга работы ветрогенератора. Для каждого
сценария процесс управления происходит непосредственно с платформы
Beaglebone, которая соединяется с каждым из устройств либо по интерфейсу
GPIO, либо через последовательный порт. Далее с помощью библиотеки
HighPerTimer измеряется длительность отправки сигнала с устройства
мониторинга непосредственно на систему управления. Таким образом, за счёт
повторений измерений в цикле собирается исходный набор данных для оценки
максимально возможных задержек и прогнозирования наихудшего времени
исполнения WCET в целом для системы. Во всех экспериментах использовался
одноядерный процессор AM335x ARM® Cortex-A8 с частотой 1 ГГц, 512 MБ ОЗУ
и версией ядра Linux 3.8.X-boneX.
В первом сценарии была использована интегральная схема Timer NE555 устройство для генерации одиночных и повторяющихся импульсов со
стабильными временными характеристиками. В рассматриваемом сценарии
таймер работает генератором одиночных импульсов в ждущем режиме с периодом
повторения 575 мксек. На рисунке 5(a) представлена CCDF функция вероятности
длительности сигнала, генерируемого микросхемой. Около 99.9% значений имеют
длительность около 367 мксек, однако распределение имеет ярко выраженный
тяжёлый хвост, где максимальное значение для набора данных n = 106 будет
достигать 6.426 мсек. Во втором сценарии измеряется время включения
19
электромеханического реле модели Songle SRD-05VDC-SL-C. Данный вид
устройств применяется для коммутации электрических цепей в устройствах
автоматики, сигнализации и связи, в частности, там, где необходимо
контролировать цепи, обладающие сигналом малой мощности. Графическое
представление функции CCDF полученных значений на рисунке 5(б) показывает
относительно плавное увеличение с 4.943 мсек до максимального значения в
13.210 мсек. В третьем сценарии отслеживается состояние системы
ветроустановки: направление и скорость ветра, направление челнока, количество
вырабатываемой энергии. Главным элементом подобной системы управления
является микроконтроллер, который соединяется через последовательные порты с
сенсорами на башне. В данном сценарии анализируются возможные задержки при
чтении данных для оптимальной эксплуатации установки. На рисунке 5(в)
прослеживается их поведение, где при n = 105 достигается максимум 3.209 мсек
относительно среднего значения отклика программы в 17.924 мксек.
Рисунок 5 – Дополнительная кумулятивная функция вероятности для сценария на основе
a) интегральной схемы NE555 б) электромеханического реле в) ветровой турбины
Далее применяется алгоритм вероятностного метода расчёта значения
WCET(ti, pi) для каждого сценария. В результате было установлено, что
экстремальные значения блока контроля при сценарии на интегральной схеме
NE555 следуют распределению Гумбеля, все остальные блоки – распределению
Фреше. Этот факт предсказывает достаточно пессимистичную оценку возможных
выбросов. Например, для сценария, основанного на реле, при p = 10-9, ожидается
задержка до 96.240 сек. Подробно параметры экстремальных распределений и
значения WCET представлены в таблице 5.
Таблица 5 - Результаты расчёта WCET для каждого блока сценариев систем управления
get_time
control_NE555
control_relay
control_turbine
Кол-во экстремумов, k
19
21
28
22
Исходный набор, n
1e+06
1e+06
1e+05
1e+0
σ
60.303
64.150
4793.132
640.708
µ
403.346
153717.1
248183.9
32893.4
ξ
0.685
0
1.046
0.512
20
(WCET ; 10−7)
6.257 мсек
34.247 мсек
0.785 сек
4.015 мсек
(WCET ; 10−8)
31.037 мсек
48.995 мсек
8.647 сек
10.101 мсек
(WCET ; 10−9)
151.249 мсек
63.743 мсек
96.240 сек
29.923 мсек
Рисунок 6 – Функция плотности вероятности PDF обобщённого распределения Парето для
экстремумов при сценариях на основе a) интегральной схемы NE555
б) электромеханического реле в) ветровой турбины
Таким образов, применяя подход сложения вероятностных оценок и метод
свёртки, была получена оценка времени выполнения работы всей системы. На
рисунке 6 графически представлена функция плотности обобщённого
распределения Парето (фиолетовая линия), показывающая зависимость
потенциального времени выполнения системы с заданной вероятностью. Таким
образом, анализируя результаты, представленные в таблице 6 при p = 10-9, можно
заключить следующее: (i) для сценария, основанного на интегральной схеме
NE555, потенциальный выброс составляет около 120 мсек, что в 3 раза
оптимистичнее, если применять вероятностный подход к каждому блоку
отдельно; (ii) для сценария, основанного на электромеханическом реле, при
элементарном сложении значений WCET итоговый прогноз составляет 96 сек, что
фактически является неприемлемым для реально работающей системы
управления, применение методики сложения блоков снижает оценку более чем в
500 раз и даёт более применимый результат - 179 мсек; (iii) для сценария,
основанного на управлении ветровой турбины, применение методики также
снижает пессимизм в 6 раз и соответствует в большей степени эмпирическим
наблюдениям. Данные эксперименты демонстрируют применимость методики на
этапе разработки системы управления при прогнозировании её временных
характеристик.
Таблица 6 – Результаты применения методики сложения для оценки системы в целом
WCET ; 10−9
control_NE555
Элементарное сложение значений WCET
366.241 мсек
96542.5 мсек
332.421 мсек
Применение предложенной методики
119.650 мсек
178.715 мсек
51.941 мсек
control_relay control_turbine
21
Заключение
В диссертации реализованы методы исследования вычислительных
процессов в высокопроизводительных вычислительных системах, основанных на
встроенных микропроцессорах, реализованы модели повышения точности и
эффективности работы приложений управления, показана эффективность
вероятностного подхода для оценки точности системы управления на заданной
архитектуре реальных систем.
Основные выводы:
1. Исследована работа аппаратных таймеров на встроенных вычислительных
системах и предложены методы повышения их точности и эффективности.
Разработана библиотека HighPerTimer, в рамках которой предлагаемые методы
показывают в 4 раза более низкую временную стоимость, и до 1000 раз меньшее
значение времени промаха при выполнении задержек процесса, в сравнения со
стандартными вызовами библиотеки Си GNU на базе процессоров ARM Cortex-A.
2. Модельными
экспериментами
произведена
оценка
надёжности
использования методов точности, в частности, в условиях виртуализации
аппаратных таймеров на базе процессора Intel. Предлагаемые методы
синхронизации показывают до двух раз более низкую временную стоимость
чтения таймера, и до 1000 раз меньшее значение времени промаха, чем функция
сна стандартной библиотеки Cи GNU.
3. Экспериментально показаны особенности применения вероятностного
метода временного анализа к отдельным элементам системы вместо модели
«чёрного ящика». На основе данного метода рассчитывается вероятность
нарушения крайнего срока и оценивается время отклика задачи, реализованной на
базе процессоров ARM Cortex A.
4. Разработана методика разбиения системы на компоненты и сложения
отдельных оценок их временных характеристик с целью получения итоговой
оценки времени работы всей системы управления. Результаты экспериментальной
оценки показали значительно менее пессимистичные и более реалистичные
значения в сравнении с эмпирическими наблюдениями, что доказывает их более
высокую практическую применимость при разработке реальных систем.
ОПУБЛИКОВАННЫЕ РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи в изданиях, рекомендованных ВАК:
1. Fedotova, I. Self-configurable time source initialization for obtaining highprecision user-space timing / I. Fedotova, E. Siemens // Вестник СибГУТИ - 2012. №4. - P. 22-30.
2. Dugaev, D. Concept of traffic routing in mobile ad-hoc networks based on
highly accurate available bandwidth estimations / D. Dugaev, D. Kachan, I. Fedotova //
Вестник СибГУТИ. - 2015. - №4., P. 90-98.
22
Публикации в изданиях, индексируемых в Scopus, Web of Science и в
издательстве Springer:
1. Fedotova, I. A high-precision time handling library / I. Fedotova, E. Siemens,
H. Hu // JCC Journal, USA, David publishing, 2013. - Vol. 10, Issue 8. – P. 1076-1086.
2. Fedotova, I. Applicability of extreme value theory to the execution time
prediction of programs on SoCs / I. Fedotova, B. Krause, E. Siemens // Proc. of The
Fifth International Conference on Applied Innovations in IT (ICAIT), Köthen, Germany,
2017. - Vol.1. Issue 5 - P. 71-80.
3. Fedotova, I. Upper bounds prediction of the execution time of programs
running on ARM Cortex-A systems / I. Fedotova, B. Krause, E. Siemens //
Technological Innovation for Smart Systems. DoCEIS 2017. IFIP Advances in
Information and Communication Technology. - Springer Cham, 2017. - Vol. 499. - P.
220-229.
4. Karpov, K. Impact of machine virtualization on timing precision for
performance-critical tasks / K. Karpov, I. Fedotova, E. Siemens // Journal of Physics:
Conference Series (JPCS), ICMIE 2017. - Vol. 870. Issue 1. - P. 52-60.
5. Karpov, K. Impact of virtualization on timing precision under stressful network
conditions / K. Karpov, I. Fedotova, E. Siemens, D. Kachan // Proc. of the 17th IEEE
International Conference on Smart Technologies. - IEEE Press, 2017 - P. 157-163.
Статьи в прочих изданиях:
1. Fedotova, I. High-precision process sleeping aspects in the handling library
HighPerTimer for Linux OS / I. Fedotova, E. Siemens // Proc. of: The Forth Scientific
and Practical Conference “Information and Measuring Equipment and Technology”,
Tomsk, Russia. - 2013. - P. 45-54.
2. Fedotova, I. The implementation of new methods of high-precision sleeps for
the Linux OS / I. Fedotova, E. Siemens // Proc. of: The Fifteenth International
Supercomputer Conference Scientific Services in the Internet: All Facets of Parallelism,
Novorossiysk, Russia. - 2013 - P. 567-572.
3. Fedotova, I. Usage of high-precision timers in the wind turbines control
systems / I. Fedotova, E. Siemens // Supercomputers Journal. - Moscow, Russia, VivaStar, 2013. - Vol. 16. - P. 38-42.
4. Fedotova, I. System Time Issues for the ARM Cortex A8 Processor/ I.
Fedotova, E. Siemens // Proc. of: The Second International Conference on Applied
Innovations in IT (ICAIT), Köthen, Germany, 2014. - Vol.1, Issue 2. - P. 7-9.
5. Исследования в Лаборатории Интернета Будущего Анхальт – FILA / Качан
Д.С., Бахарев А.В., Федотова И. С., Сименс Э // Материалы Российской научнотехнической конференции “Современные проблемы телекоммуникаций”,
Новосибирск, Россия, 2015. - C. 16-20.
Документ
Категория
Без категории
Просмотров
2
Размер файла
1 080 Кб
Теги
07305b7041, uploaded
1/--страниц
Пожаловаться на содержимое документа