Организация вычислений в компонентах. 4 страница

2.7.3. Оценка производительности

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

2.7.3.1. Оценка WCET

Оценивание WCET [37]. Это техники формальной оценки производительности требуют некоторых знаний архитектуры. Они меньше подходят для очень ранней стадии проектирования, но некоторые из них могут быть использованы без знаний всех деталей целевой архитектуры. Эти подходы моделируют реальность, физическое время. Планирование задач требует некоторых знаний о длительности их выполнения, особенно если требуются гарантии удовлетворения временных ограничений, таких как в системах реального времени. WCET (worst case execution time – наихудший случай времени выполнения) является базой для большинства алгоритмов планирования задач. Некоторые определения, относящиеся к WCET, показаны на рис. 95.

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

Распределение времени выполнения

Рис. 95. Терминология WCET

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

– должны быть надежными (WCET EST ≥ WCET);

– должны быть впритирку (WCET EST -WCET <<WCET).

Заметим, что термин «ожидаемый» не означает, что результирующее время ненадежно.

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

Величина BCET (best -case execution time – наилучший случай времени выполнения) и соответственная ожидаемая BCET EST определяются в аналогичной манере. Величина BCET EST является надежной нижней границей впритирку времени выполнения.

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

На рис. 96 представлена архитектура инструмента aiT [42]. aiT начинает с исполнительного объектного файла, содержащего требуемый для анализа кода. На основании этого кода строится граф потока управления (CFG - Control Flow Graph) – представление в виде графа всех путей, по которым может пройти программа во время своего выполнения. Затем выполняется преобразование циклов. Оно включает преобразование вызовов рекурсивных функций в циклы, а также виртуальное разворачивания цикла. Разворачивание называют виртуальным, так как оно выполняется без реального модифицирования кода. Результат представляется в CRL формате (control flow representation language – язык представления потока управления). На следующем этапе выполняется различный статический анализ. В процессе статического анализа читается AIP-файл, содержащий пояснения разработчика. Эти пояснения включают информацию, которую трудно или невозможно извлечь из программы автоматически (например, границы сложных циклов). Статический анализ включает анализ значений, стека и конвейера.

Рис. 96. Архитектура aiT инструмента для анализа времени

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

Следующий шаг это анализ кэш и конвейера. Предположим, что используется n-входовая ассоциативная по множеству кэш (рис. 97). Рассмотрим часть (строку) кэш соответствующую отдельному индексу (выделена жирной линией). Предположим, что замещение этой части кэш выполняется по алгоритму LRU (замещения наиболее давней по использованию страницы). Это означает, что среди всех ссылок на ячейки памяти для отдельного индекса в адресе последние n из них отсылали к блокам памяти, запомненным в этой части кэш. Блок памяти ‘b’, получивший доступ перемещается в позицию кэш, становящуюся самой «молодой», а все остальные блоки кэш «стареют» на 1.

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

Рис. 97. Ассоциативная по множеству кэш (n=4)

Представим часть кэш и отдельный индекс. Предположим, что имеется информация о возможных записях для каждого из n входов (колонок) кэш. Кроме того рассмотрим сходящийся поток управления. Что известно о содержимом части кэш в точке схождения путей? Необходимо сделать различие между анализом возможной и обязательной информацией. Анализ обязательности показывает записи, которые должны быть в кэш. Эта информация полезна для вычисления WCET. Анализ возможности идентифицирует записи, которые могут быть в кэш. Эта информация обычно используется для заключения о том, что определенная информация точно не будет в кэш, а это необходимо для вычисления BCET. В качестве примера анализа обязательности и возможности рассмотрим обязательную информацию в сходящемся потоке управления. Рис. 98 показывает соответствующую ситуацию: содержимое строки 4-входовой кэш для одного и другого пути в CFG до схождения. Элементы, расположенные слева, предполагаются «моложе» элементов, расположенных правее.

	Результат: пересечение + максимальный возраст

Рис. 98. Анализ обязательности в программе соединения данных для LRU кэш

Объект памяти ‘c’ предполагается самым «молодым» для одного сходящегося пути, а объект ‘a’ – для другого. «Возраст» остальных элементов определяется таким же образом. Что известно о наихудшем случае в точке схождения путей? Определенный элемент гарантированно будет в кэш, только если он гарантированно был в обоих путях. Это означает, что пересечение объектов памяти определяет результат анализа обязательности после схождения. За наихудший случай необходимо принять максимальный возраст среди двух путей. Очевидно, что этот анализ должен использовать множества элементов для каждого входа кэш.

Рис. 99 показывает анализ возможности для сходящегося потока управления. Множество объектов, которые может содержать кэш в точке схождения путей, состоит из объединения объектов, которые были в кэш перед схождением путей. В качестве наилучшего случая используется минимальный возраст перед схождением.

	Результат: объединение + минимальный возраст

Рис. 99. Анализ возможности в программе соединения данных для LRU кэш

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

Суммарный результат статического анализа содержит границы времени выполнения для каждого из базовых блоков программы. Результаты записываются в PER-файл (рис. 91).

На следующем этапе aiT использует эти границы для получения WCET для всей программы. Этот шаг базируется на модели целочисленного линейного программирования (ILP). В этой модели суммарное время выполнения используется как целевая функция. Суммарное время выполнения вычисляется как сумма по всем оценкам базовых блоков умноженных на их частоту выполнения. Время выполнения базовых блоков определяется как время WCET однократного выполнения блока (как вычислено при статическом анализе) умноженное на количество наихудших случаев выполнения. Только некоторое количество выполнений блоков может быть определено автоматически. Поэтому построение ILP модели полагается на дополнительную информацию разработчика, например о границах цикла. Эта информация считается из AIP-файла. Ограничения моделируют отношения между блоками. Эту технику для моделирования времени выполнения называют нумерацией подразумеваемого пути. Так удается избежать нумерации потенциально большего числа путей вычислений. Оговоренная задача ILP может быть решена стандартной программой ILP для максимизации, целевой функции. Полученный максимум дает верную верхнюю границу суммарного времени выполнения. aiT также обеспечивает визуализацию результатов в форме аннотированных графов потока управления. Эти графы анализируются разработчиками для оптимизации проектов.

.

2.7.3.2. Исчисление реального времени

Исчисление реального времени (RTC – Real -time calculus) [38] базируется на описании интенсивности входящих событий. Это описание также включает отклонения от этой интенсивности. С этой целью временные характеристики последовательности событий представляются кортежем кривых (графиков) поступления: ^u (Δ), ^l (Δ) ∈IR ≥ 0, Δ ∈IR ≥ 0.

Эти кривые представляют максимальное соответственно минимальное число событий поступающих внутри интервала времени Δ. Существуют наибольшее ^u (Δ) и наименьшее ^l (Δ) число событий поступающих в интервале (t, t+Δ) для всех t ≥ 0. На рис. 100 показан ряд возможных поступлений событий для некоторых возможных моделей поступления.

Рис. 100. Кривые поступления: периодический поток (слева),

периодический поток с джиттером J (справа)

Например, в случае периодического потока событий с периодом p существует максимум простого события происходящего на интервале времени (0, p). Аналогично существует верхняя граница двух событий внутри временного интервала (p, 2 p). Теперь рассмотрим нижнюю границу для интервала (0, p). Возможно не существует единичного события в этом интервале. Следовательно, граница равна 0. Так для Δ=0. 5 p будет существовать минимум 0 и максимум одно входное событие. В случае периодического потока события с джиттером J эти кривые сдвигаются на эту величину. Верхняя граница смещается влево, нижняя граница смещается вправо. Предполагается, что джиттер не накапливается. Верхнее подчеркивание в обозначении символизирует входящее событие.

Полезная вычислительная и коммуникационная пропускная способность может быть описана функциями обслуживания:

β ^u (Δ), β ^l (Δ) ∈ IR ≥ 0, Δ ∈ IR ≥ 0.

Эти функции позволяют моделировать ситуации, в которых изменяется полезная пропускная способность. На рис. 101 показана коммуникационная пропускная способность TDMA шины (time division multiple access – множественный доступ с временным разделением).

Рис. 101. Функции обслуживания для TDMA шины

Распределение выполняется периодически с периодом p. Арбитр выделяет шину на время s (окно). Во время этого окна шина достигает ширины полосы в b единиц.

Верхняя граница достигается, если шина выделяется точно во время, когда начинается отсчет. Количество переданных данных тогда увеличивается линейно. Нижняя граница достигается, если шина была только что освобождена, когда начался отсчет Δ. Затем необходимо ждать p−s единиц времени пока шина не будет выделена снова.

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

До сих пор не было информации об объеме работы требуемой для каждого входящего события. Этот объем работы представляется отдельными функциями γ ^u (e), γ ^l (e) ∈ IR≥0 для каждой последовательности e входящих событий. Эта информация может быть получена из границ времени выполнения кода для обработки каждого из событий. На рис. 102 приведен пример таких функций. Этот пример базируется на предположении, что для обработки одиночного события требуется от трех до четырех единиц времени.

1 2 3 e

Рис. 102. Характеристика объема работы

Соответственно объем работы для одиночного события варьируется между 3 и 4 единицами времени, объем работы для двух событий варьируется между 6 и 8 единицами времени и т.д. Пунктирные линии не являются частью функции, т.к. она определена только для целого числа событий. Объем работы получающийся из входного потока событий теперь может быть легко вычислен. Верхняя и нижняя границы характеризуются функциями:

α ^u (Δ) = γ ^u (^u (Δ)) (1)

α ^l (Δ) = γ ^l (^l (Δ)) (2)

Должно быть достаточной вычислительная или коммуникационная пропускная способность для обработки этого объема. Число событий, которое может быть обработано с полезной вычислительной пропускной способностью может быть вычислено как

^u (Δ) = (γ ^l) ^{− 1}(β ^u (Δ)) (3)

^l (Δ) = (γ ^u) ^{− 1}(β ^l (Δ)) (4)

Равенства 3 и 4 используют обратные функции γ ^u ( (γ ^u) ^{− 1}) и γ ^l ((γ ^l) ^{− 1}) для конвертирования границ полезной пропускной способности (измеряется действительными значениями времени) в границы, измеряемые в терминах числа событий которые могут быть обработаны.

Основываясь на этой информации, можно получить свойства выходных потоков событий из входных потоков событий. Предположим, что входной поток характеризуется границами [ ^l, ^u ]. Затем вычисляем характеристики выходных потоков как, например соответствующие границам

[ ^l’, ^u’ ] исходящего потока событий и оставшейся пропускной способности полезной для других задач. Эту оставшуюся пропускную способность получают преобразованием кривых обслуживания [ ^l, ^u ] в кривые обслуживания [ ^l’,^u’ ] (рис. 103). Эта оставшаяся пропускная способность может быть использована для низкоприоритетных задач для выполнения на том же процессоре.

Рис. 103. Преобразование потока событий и пропускной способности

компонентами реального времени

Исходящие потоки и оставшаяся пропускная способность ограничиваются следующими функциями:

^u’ = [(^u ⊗ ^u) ^l ]∧ ^u (5)

^l’ = [(^{l u}) ⊗ ^l ]∧ ^l (6)

^u’ = (^u−^l) ∅ 0 (7)

^l’ = (^l −^u)0 (8)

Операции, используемые в этих равенствах, определяются следующим образом:

(f ∅ g)(t) = inf 0≤u≤t{ f (t −u)+g(u)} (9)

(fg)(t) = sup 0≤u≤t{ f (t −u)+g(u)} (10)

(fg)(t) = sup u≥0{ f (t +u)−g(u)} (11)

(f ∅ g)(t) = inf u≥0{ f (t +u)−g(u)} (12)

∧ обозначает оператор минимума;

inf – точная нижняя граница;

sup – точная верхняя граница.

По существу эти равенства характеризуют исходящие потоки и пропускную способность. Эти равенства были адоптированы из теории связи. Для работы с этими равенствами можно просто использовать инструментарий Matlab.

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

2.7.4. Модели энергии и мощности

Модели энергии и модели мощности необходимы для оценки соответствующих технических требований. Обе модели тесно связаны, как следует из выражения: E =integral(P*dt), где E – энергия, а P – мощность. Эти модели необходимы для оптимизации, нацеленной на снижение потребления энергии и мощности. Они также необходимы для оптимизации, нацеленной на уменьшить температуру при работе системы.

Первая модель мощности была предложена в [39]. Она опирается на результаты измерения в реальной системе. Измеренная величина затем ассоциируется с выполненными командами. Модель включает так называемые базовые затраты и меж-командные затраты. Базовые затраты команды соответствуют потребляемой энергии из расчёта на команду при выполнении бесконечной последовательности экземпляров такой команды. Меж-командные затраты моделируют дополнительно потребляемую энергию процессором при переключении на выполнение другой команды. Дополнительная энергия потребляется, например, из-за переключения функциональных узлов между “включено” и “выключено”. Эта модель мощности фокусируется на потреблении процессора и не рассматривает потребляемую мощность памятью или другими частями системы.

В [40] предложена другая модель. Она базируется на документах, представляющих технические данные (data sheets) компонент. Преимущество этого подхода в том, что при подсчете потребляемой мощности учитывается вклад всех компонент встроенной системы. Однако информация в технической документации о средних значениях величин может быть менее точной, чем информация о максимальных и минимальных значениях.

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

Другая модель основывается на точных измерениях с использованием реальной аппаратуры. Учитывается потребление процессора и памяти. Эта модель была интегрирована в компилятор энергии.

Еще одна оценка потребляемой мощности микропроцессорной системы выполняется на основе знаний уровня архитектуры без привлечения детальной информации на уровне электрической схемы или схемы размещения.

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

2.7.5. Тепловая модель

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

Тепловое поведение встроенных систем тесно связано с преобразованием электрической энергии в тепловую энергию. Следовательно, тепловая модель обычно связана с моделью энергии. Тепловая модель базируется на законах физики. Теплопроводность есть ключевая величина, рассматриваемая в тепловой модели. Теплопроводность определенного материала отражает количество тепла передаваемого через покрытие из этого материала площадью A и толщиной L, когда температура на противоположной стороне отличается на один Кельвин. Обратную величину называют тепловым сопротивлением. Для плотно контактирующих покрытий эффективное общее тепловое сопротивление является суммой их индивидуальных тепловых сопротивлений. Это означает, что тепловое сопротивление суммируется как и электрическое сопротивление в электрических цепях. Это соответствие также распространяется массу аккумулированного тепла: масса соответствует емкости в электрических цепях. В результате тепловое моделирование обычно использует эквивалентную электрическую модель и использует хорошо известные приемы для решения уравнений электрических цепей (например, [41]).

Вопросы для самоконтроля

1. В чем суть проектирования программного обеспечения встроенных систем, основанного на модели?

2. Из каких элементов состоит модель вычислений?

3. Как в модели потока данных организованы вычисления?

4. Является ли временной автомат подмножеством расширенного автомата, если да, то почему?

5. Какого рода встроенные системы хорошо описывать на SDL и почему?

6. В чем суть различия синхронных и асинхронных языков для проектирования встроенных систем?

7. Как в SCADE выполняется формальная верификация?

8. Какие механизмы используются на среднем уровне программного обеспечения для реализации одновременного исполнения последовательного кода?

9. Для чего необходим механизм взаимного исключения?

10. Что гарантирует последовательная непротиворечивость памяти?

11.В чем различие между процессами и потоками?

12. Какие средства используют для валидации проектов прикладного ПО?