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

Модель фон Неймана. Эта модель основана на последовательном выполнении цепочек примитивных вычислений.

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

Машина с конечным числом состояний (FSM, конечный автомат). Эта модель основана на понятии конечного множества состояний, входов, выходов и переходах между состояниями. Несколько таких машин могут взаимодействовать между собой, образуя взаимодействующие машины с конечным числом состояний (CFSM).

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

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

Комбинированные модели. Реальные языки программирования обычно объединяют определенные модели взаимодействия с организацией вычислений в компонентах. Например, SDL объединяет машины с конечным числом состояний с асинхронной передачей сообщений. Языки ADA и CSP объединяют модель фон Неймана с синхронной передачей сообщений.

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

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

Примеры использования (use cases). Для многих приложений целесообразно представлять потенциальные применения проектируемой системы. Такие применения фиксируются как use cases. Use cases описывают возможные применения системы и могут использовать разные способы обозначения. Для поддержки ранних стадий проектирования был разработан стандарт UML (Unified Modeling Language), содержащий стандартизованную форму для use cases [23]. На рис. 65 приведен пример нескольких use cases для устройства Автоответчик.

Рис. 65. Пример use cases

Use cases идентифицируют различные классы пользователей и приложений проектируемой системы. Есть возможность зафиксировать на самом высоком уровне проектирования то, что ожидается от системы.

Диаграмма взаимодействия (MSC – Message Sequence Charts). Это чуть более детальный уровень представления, позволяющий подробно задавать последовательность сообщений между компонентами для реализации некоторого применения проектируемой системы. В MSC одно измерение (вертикальное) используется для представления последовательностей, а другое (горизонтальное) отражает взаимодействие компонент. MSC описывает частичный порядок между передачами сообщений и показывает возможное поведение проектируемой системы. MSC стандартизовано в UML. На рис. 66 показана MSC одного из use cases Автоответчика.

2.2 Автомат с конечным числом состояний

Начальное представление проектируемой системы на более детальном уровне требует более точной модели, основанной на представлении поведения с помощью состояний. Граф переходов, представляющий автомат с конечным числом состояния (FSM), является классическим способом представления состояний. Будем рассматривать детерминированные FSM, в которых в каждый момент активным является только одно состояние. Узлы графа представляют состояния. Ребра представляют переходы между состояниями. Метки ребер представляют события. Предположим, что некоторое состояние FSM активно, происходит событие, которое соответствует одному из исходящих ребер. FSM изменит свое текущее активное состояние на состояние указанное этим ребром. Если FSM полностью тактируема, то ее называют синхронной. FSM может также генерировать выход.

Рис. 66. Пример MSC Автоответчика для случая вызова

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

Расширенный конечный автомат (ЕFSM) – автомат, пополненный переменными, которые могут быть прочитаны и записаны как часть перехода между состояниями. Введение переменных решает проблему быстрого увеличения числа состояний классического автомата для моделирования реальных объектов.

Для моделирования времени в ЕFSM ввели действительные переменные, которые моделируют логические часы системы. Переменные времени инициализируются значением 0 при старте системы, а затем синхронно увеличиваются с одной и той же скоростью. Автоматы с такими переменными называют временными автоматами (timed automata ТА). Переменные времени являются элементами охранных условий ребер. Переходы будут выполняться, когда значения часов удовлетворят охранным условиям ребер. Часы могут быть сброшены в 0 во время перехода [24]. На рис. 67 приведен пример модели Автоответчика в виде временного автомата.

Автоответчик обычно находится в начальном состоянии «Старт». При поступлении вызова часы Х устанавливаются в 0 и выполняется переход в состояние «Ожидание». Если вызываемый абонент поднимает трубку, то происходит разговор до опускания трубки. В противном случае выполняется переход в состояние «Проигрывание текста», если время достигнет значения 4. По завершению проигрывания текста выполняется переход в состояние «Бип-сигнал». Часы Y обеспечивают однократную генерацию бип-сигнала. После бип-сигнала часы Х сбрасываются снова в 0 и автоответчик готов к записи сообщения. Когда время достигает величины 8 или вызывающий абонент замолчал, генерируется следующий однократный бип-сигнала. После второго бип-сигнала выполняется переход в состояние «Отключено».

Рис. 67. Модель обслуживания входящих вызовов Автоответчиком

в виде временного автомата

В этом примере переходы выполняются или под воздействием входов (таких как «Трубка поднята») или так называемых временных ограничений (clock constraints). Временные ограничения описывают переходы, которые могут, но не обязаны быть. Для того чтобы обеспечить реальный переход по этим условиям дополнительно определяются инварианты местоположения (location invariants). Инварианты местоположенияX <= 5, X <= 9 и Y <= 2 используются в примере для того чтобы переходы выполнялись не позже чем через время при котором условия инвариант становятся истинными.

Формально временной автомат определяется следующим образом [24].

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

Определение. Временное ограничение есть коньюктивная формула элементарных ограничивающих условий в форме:

x ◦ n или (x−y) ◦ n для x, y ∈ C, ◦ ∈ {≤,<,=,>,≥} и n ∈ N.

Пусть B(C) есть множество временных ограничений.

Определение. Временной автомат есть кортеж (S, s0,E, I), где

S– конечное множество состояний.

s0 – начальное состояние.

E ∈ S×B(C) ×Σ×2^C×S– множество ребер. B(C) представляет конъюнктивное условие, которое должно иметь место и Σ – входы необходимые для перехода. 2^C выражает множество временных переменных, которые сбрасываются во время перехода. I: S→B(C) – множество инвариант для каждого состояния. B(C) представляет инварианту, которая должна иметь место для определенного состояния. Эта инварианта описывается коньюктивной формулой.

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

2.3. Асинхронный язык проектирования SDL

В качестве примера рассмотрим язык SDL (Specification and Description Language, стандартизован ITU) основанный на CFSM с асинхронной передачей сообщений. Наряду с текстовым представлением SDL поддерживает и графическое представление проектов. Базовыми элементами SDL являются процессы, представляющие компоненты MoC как EFSM. На рис. 68 показаны графические символы, используемые для представления EFSM.

На рис.69 приведено графическое представление в виде процесса (Process P) на SDL временного автомата Автоответчика из примера на рис. 67. Временные переменные (часы) X и Y на SDL представляют два таймера X и Y.

Рис. 68. Символы графической формы SDL

Рис. 69. Модель Автоответчика на SDL

Оператор SET (NOW+4, X), например, запускает таймер X на интервал равный 4, а оператор RESET(X) останавливает таймер X. Процессы SDL представляют EFSM, поэтому они могут выполнять преобразования над данными. Переменные могут быть объявлены локально в процессах. Многие типы данных предопределены, так же они могут быть определены

пользователем. Синтаксис для объявлений и операций подобен другим языкам. На рис. 70 показаны объявления, оператор присвоения и условный оператор.

Рис. 70. Объявление, присвоение и условный оператор SDL

В общем, описание на SDL состоит из взаимодействующих процессов или EFSM. Процессы могут посылать сигналы другим процессам, образуя CFSM. Семантика взаимодействия процессов основана на асинхронной передаче сообщений и реализована в виде очередей типа FIFO (first-in first-out), ассоциированных с процессами (на каждый процесс своя очередь). Сигналы, посылаемые определенному процессу, поступают в соответствующую очередь как на рис. 71.

Рис. 71. Взаимодействие процессов SDL

Каждый процесс выбирает из очереди запись и проверяет, совпадает ли она с одним из входов назначенных текущему состоянию. Если да, то выполняется соответствующий переход и генерируется выход. Выбранная запись игнорируется, если нет совпадения ни с одним из назначенных входов. Запись при этом может остаться в очереди, если используется механизм запоминания SAVE.

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

На практике это не реализуемо и это одна из проблем реализаций проектов на SDL.

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

2.4. Синхронный язык проектирования Lustre

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

Синхронный язык объединяет конечный автомат и язык программирования в одну модель. Синхронный язык может выражать сложные вычисления, но исполнительной моделью является конечный автомат. Такой язык описывает одновременно действующие автоматы. Детерминированное поведение достигается за счет того, что параллельно работающие автоматы одновременно выполняют переходы между состояниями. Это предполагает наличие единого глобального «тактового сигнала», а не своего «тактового сигналов» для каждого из автоматов. В каждом такте принимаются во внимание все входы, вычисляются выходы и следующие состояния, что требует быстрого широковещательного механизма для всех частей модели. Такой идеалистический взгляд на одновременность гарантирует детерминированное поведение. Это является ограничением, если сравнивать с моделью CFSM, в которой каждая FSM имеет свой собственный «тактовый сигнал». Синхронный язык, по сути, отражает принцип работы синхронных схем.

Пусть даны две переменные d и x. Каждый тик в синхронной модели они обновляются следующим образом (d’ и x’ – значения в следующий момент времени):

d’ = -d если x=0; d иначе

x’ = x + d

x: 0 -1 0 1 0 -1 0 1

d: -1 1 1 -1 -1 1 1 1

В 80-х годах прошлого века был предложен синхронный язык Lustre [25] для разработки надежных систем в таких критических областях как аэрокосмическая, ядерная энергетика, поезда без водителей.

Lustre базируется на парадигме программирования, которая представляет преобразования в виде модели синхронного потока данных. Эта парадигма полагается на следующие моменты:

• Модель встроена в цикл, состоящий из трех фаз: прием множества текущих входных данных, вычисление выходных данных и их выдача.

• Входы и выходы, таким образом, являются потоками бесконечных последовательностей значений некоторого типа.

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

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

Вычисления выходов могут потребовать предыдущих входных значений входов и выходов. В этом случае отношение между входами и выходами не являются функциональными, а зависят от истории сигналов. Если v есть выражение потока, то последовательность обозначается как v1, v2, v3,....

• 3 означает поток констант 3, 3, 3,....

• a+b означает поток a1+b1, a2+b2, a3+b3,....

• Пусть v = expr есть выражение для потока v. Тогда в других выражениях v может быть безопасно заменен на exprвсоответствии с принципом замещения.

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

ESTEREL Technologies разработала коммерческий инструмент SCADE для моделирования, тестирования и верификации синхронных систем использующих Lustre. SCADE де-факто стала европейским стандартом. Она используется в Airbus, Merlin-Gerin, «Сухой»,.... SCADE является комплектом программ, работающих под Windows и Linux, и состоит из следующих программных компонент:

• GUI интерфейс для графической манипуляции с моделями Lustre;

• симулятор;

• инструмент для верификации;

• генератор исполняемого кода;

• инструмент генерации отчетов.

Lustre опирается на 3 базовые концепции.

• flow(поток) – последовательность значений данных. Все значения потока принадлежат к одному типу, например, integer flow: 0,1,2,3,....

• node(узел) – базовый кирпич любой программы. Lustre является функциональным языком: каждый узел определяет функцию, которая получает входные потоки и производит выходные потоки, например:

Оператор pre (предыдущее значение): если A = (a1,a2,a3,...,an,...) тогда pre(A) = (nil,a1,a2,a3,...,an-1,...). Оператор -> (инициализация flow): если A = (a1,a2,a3,...,an,...) и B = (b1,b2,b3,...,bn,...), то A->B = (a1,b2,b3,...,bn,...).

Функция rising примера обнаруживает моменты изменения символов входного потока Х с 0 на 1 и формирует соответствующий выходной поток Y. Однажды определенный узел становится оператором и может быть вызван в другом узле. На рис. 72 приведено графическое представление rising в SCADE.

Рис. 72. Графическое представление rising в SCADE

• cycle (цикл) – один шаг выполнения программы. В каждом цикле вычисляются новые значения и добавляются в каждый поток. Каждый цикл соответствует тику.

Модели систем могут быть смоделированы в SCADE. Симулятор вычисляет значения каждого потока в каждом цикле. Разработчик может ввести значения для входных потоков и наблюдать выходные потоки. На рис. 73 приведены результаты моделирования узла rising.

	X: F T T F F T T Y: F F F F F T F re(X): nil T T T F F T not pre(X): nil T F F F T T F X and not pre(X): nil T F F F F T F False: F F F F F F F F false -> X and not pre(X): F T F F F F T F Cycle: 0 1 2 3 4 5 6 7

.

Рис. 73. Временная диаграмма rising

Для модели, которая была отлажена с помощью симулятора, SCADE может выполнить формальную валидацию (верификацию). Для этого необходимо спроектировать поток (называемый монитором), который принимает истинное значение тогда и только тогда, когда интересуемое свойство обнаруживается. Если такой поток всегда принимает истинное значение, то свойство подтверждается. Например, для узла rising мы хотим убедиться, что выходной поток никогда не будет иметь значение true во время двух соседних циклов. На рис. 74 приведен узел Monitor, формирующий потока Prop, для доказательства этого свойства.

Рис. 74. Узел Monitor для верификации rising

Monitor затем подключают к узлу rising (рис. 75) и убеждаются, что выход Monitor всегда принимает значение true.

Рис. 75. Верификации rising

Преобразование линейных систем после дискретизации в программы на Lustre является очевидной задачей. Если система выражена в форме z-преобразований, то оператор 1/z транслируется в 0.0 -> pre(). Пусть например передаточная функция второго порядка имеет вид:

H(z)= (a*z^2 + b*z +c)/(z^2 + d*z +e),

y= H(z)*x,

у=a*x+(b*x-d*y)*1/z+(c*x-e*y)*1/z^2, отсюда программа:

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

• Как и модель является детерминированным.

• Не содержит динамически выделяемой памяти.

• Чистое отображение между кодом и моделью.

• Последнее позволяет производить трассировку программы при отладке.

Рассмотрим простой пример проектирования контроллера «Газовая горелка» (рис. 76) [26]. Контроллер должен сохранять температуру внутри заданного интервала (например, между 50 и 60 градусами включительно). Изначально температура находится в заданном интервале. Контроллер преобразует входной поток Т (значения температуры) в выходной булев поток В.

Рис. 76. «Газовая горелка»

Предлагается следующий алгоритм работы: когда температура достигает 50 °С горелка включается, когда температура достигает 60 °С, горелка выключается. На Lustre это выглядит так:

На рис. 77 представлена модель контроллера газовой горелки в SCADE.

Рис. 77 Модель газовой горелки в SCADE

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

– когда горелка включается, температура повышается;

– когда горелка выключается, температура понижается.

– горелка переключается мгновенно;

– когда нагрева нет температура в баке уменьшается со скоростью 1°С в единицу времени;

– когда происходит нагрев температура в баке повышается со скоростью 3°С в единицу времени;

– датчик температуры точный.

Описание датчика температуры:

• вход temp – температура в баке, действительная величина (real);

• выход reading – отсчет;

• преобразование – temp = reading.

Описание горелки:

• вход switch – команда контроллера

• выход heating – the «пламя», булева величина (Boolean);

• преобразование – heating = switch.

Описание бака:

• вход heated – булева величина, индицирующая нагрев или его отсутствие;

• выход temp – температура;

• преобразование – temp = 55 -> (if heated then pre(temp)+3 else pre(temp)-1).

Моделирование в SCADE позволяет найти ошибку: для некоторой начальной температуры никогда не достигается температура точно в 60 °С и горелка никогда не выключится. Это связано с ограничениями на частоту дискретизации CPU. Поэтому необходимо вместо ‘if T=60 then false’ перейти к нестрогому неравенству: ‘if T >= 57 then false’, где Т – температура, вычисленная в предыдущем цикле.

2.5. Многозадачность.

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

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

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

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

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

2.5.1. Язык программирования Си

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

Языки программирования, которые выражают вычисления как последовательность операций, называют императивными. Язык Си является таким языком.

Рассмотрим модель памяти в Си. Си-программы сохраняют данные в стеке, «куче» (heap) и фиксированных ячейках памяти, назначаемых компилятором. Рассмотрим пример Си-программы:

Переменная ‘a’ является глобальной переменной, т.к. объявлена вне определений функций. Компилятор назначит ее на определенное место в памяти. Переменные ‘b’ и ‘c’ являются параметрами. Им выделяется место в стеке, когда вызывается функция foo (компилятор может также назначить их на регистры). Переменные ‘d’ и ‘e’ локальные переменные. Они объявляются внутри тела функции (в примере в main). Компилятор зарезервирует для них место в стеке.

Когда в строке 11 вызывается функция foo, ячейка стека, назначенная для ‘b’, получает копию переменной ‘d’, установленной в строке 8. Это является примером передачи параметров в функцию. Данные передаваемые указателем ‘e’ наоборот запоминаются в памяти, выделенной под кучу и проходят через ссылку (указатель на ‘e’ проходит как величина). Адрес запоминается в ячейке стека для ‘c’. Если foo содержит оператор присвоения для *c, то после возврата из foo это значение может бать прочитано разименованием ‘e’.

Рассмотрим некоторые ключевые моменты Си на примере программы на рис. 78. Эта программа реализует часто используемый шаблон, называемый «observer» (наблюдатель). В этом шаблоне функция update изменяет величину переменной ‘х’. Наблюдатели (другие программы или части программы) будут оповещаться (notify) функций обратного вызова (callback) всякий раз, когда изменяется ‘х’. В программе используется связанный список – структура данных для хранения списка элементов, длина которого может изменяться во время выполнения программы. Каждый элемент списка содержит полезную нагрузку (значение элемента) и указатель на следующий элемент в списке (или нуль-указатель, если элемент последний).

typedef structelement element_t; // Тип элемента списка функций оповещения. element_t* head = 0; // Указатель на начало списка. element_t* tail = 0; // Указатель на конец списка. voidaddListener(notifyProcedure* listener) { // Функция регистрации слушателей. if(head == 0) { head = malloc(sizeof(element_t));//Динамическое выделение памяти под пере head->listener = listener; // менную типа element_t. head->next = 0; tail = head; } else{ tail->next = malloc(sizeof(element_t)); tail = tail->next; tail->listener = listener; tail->next = 0; } } voidupdate(intnewx) { // Функция обновления x x = newx; element_t* element = head; while(element!= 0) { // Оповещение всех зарегистрированных слушателей (*(element->listener))(newx); element = element->next; } } voidprint(intarg) {// Пример callback-функции оповещения. printf("%d ", arg); }

Рис. 78. Пример программы-шаблона «observer» на Си

Для программы на рис. 78 структура данных связанного списка определяется так:

Первая строка декларирует, что notifyProcedure принадлежит к типу Си-функций с аргументом типа int, функция ничего не возвращает. Строки 2 – 5 декларируют struct (структура) – составной тип данных в С. Эта структура состоит из двух элементов: listener типа notifyProcedure* (указатель на функцию) и next – указатель на экземпляр этой же структуры. Строка 7 декларирует, что element_t является типом, относящимся к экземпляру структуры element. Строка 7 декларирует указатель head на список element. head инициализируется значением 0, индицирующим пустой список. Функция addListener создает первый элемент списка, используя следующий код:

В первой строке выделяется память из кучи с использованием стандартной С-функции malloc для сохранения списка element и запоминается в head указатель на element. heap – это структура данных, которая помогает сохранять сведения об областях памяти, используемыми приложениями. В строке 2 запоминается нагрузка, в строке 3 индицируется, что это последний элемент списка. В строке 4 устанавливается значение в tail – указатель на последний элемент списка. Когда список не пуст функция addListener будет использовать tail для добавления элемента к списку.