Параллелизм, корутины, событийные автоматы,… живая математика

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

Хотя есть и другой вариант. Не надо ничего пока менять и/или на что-то влиять. Пусть будет многопоточность и корутины, пусть будет… и параллельное автоматное программирование (АП). Пусть соревнуются и, когда это необходимо и возможно, дополняют друг друга. В этом смысле у современного параллелизма есть, как минимум, один плюс — он позволяет это делать.

Ну, так что, посоревнуемся!?

1. От последовательных вычислений к параллельным

Рассмотрим программирование простейшего арифметического уравнения:

С2 = A + B + A1 + B1; (1)

Пусть есть блоки, реализующие простые арифметические операции. В данном случае достаточно блоков суммирования. Наглядное и точное представление о числе блоков, их структуре и связях между ними дает рис. 1. А на рис.2. приведена конфигурация среды ВКП(а) для решения уравнения (1).


Рис.1. Структурная модель процессов

Но структурно схеме на рис.1 соответствует система из трех уравнений:

С = A + B;
C1 = A1 + B; (2)
C2 = C + C1;

Одновременно (2) это и параллельная реализация уравнения (1), представляющая алгоритм суммирования массива чисел, известный также под именем алгоритма сдваивания. Здесь массив представлен четырьмя числами A, B, A1, B1, переменные С и С1 — промежуточные результаты, а С2 результат — сумма массива.


Рис.2. Вид диалогов для конфигурации трех параллельных процессов

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

2. Параллелизм как проблема

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

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

Пусть имеется два параллельных процесса, которые соответствуют следующей системе уравнений:

с = a + b; (3)
a = b + c;

Предположим, переменным a, b, c присвоены начальные значения 1, 1, 0. Можно ожидать, что протокол вычислений для пяти шагов будет следующим:

a              b               c
1.000       1.000       0.000      
1.000       1.000       2.000       
3.000       1.000       2.000       
3.000       1.000       4.000       
5.000       1.000       4.000        
5.000       1.000       6.000   

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

Но, скорее всего, вы получите примерно такой протокол:

   a              b               c
1.000       1.000       0.000      
3.000       1.000       2.000       
5.000       1.000       4.000       
7.000       1.000       6.000       
9.000       1.000       8.000       
11.000     1.000     10.000       

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

с = a + b; a = b + c; (4)

Но может случиться, что исполнение операторов будет ровно обратным, и тогда протокол будет следующим:

   a              b               c
1.000       1.000       0.000      
1.000       1.000       2.000       
3.000       1.000       4.000       
5.000       1.000       6.000       
7.000       1.000       8.000       
9.000       1.000     10.000       

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

В рамках технологии АП работа с общими переменными процессов разрешается просто и корректно. Здесь чаще всего не требуется особых усилий на синхронизацию процессов и работу с данными. Но нужно будет выделить действия, которые будут считаться условно мгновенными и неделимыми, а также создать автоматные модели процессов. В нашем случае действиями будут операторы суммирования, а за их запуск будут отвечать автоматы с циклическими переходами.
Листинг 1 демонстрирует код процесса, реализующего операцию суммирования. Его моделью является конечный автомат (см. рис. 3) с одним состоянием и безусловным переходом в форме петли, у которого единственное действие y1, выполнив операцию суммирования двух переменных, помещает результат в третью.


Рис.3. Автоматная модель операции суммирования


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

3. А корутины?...

Хорошо бы знать, как с поставленным заданием справятся корутины, представленные языком Kotlin. Возьмем в качестве шаблона решения программу, рассмотренную при обсуждении статьи [1]. Она имеет структуру, которая легко приводится к необходимому виду. Для этого заменим в ней логические переменные на числовой тип и добавим еще одну переменную, а вместо логических операций будем использовать операции суммирования. Соответствующий код приведен в листинге 2.


К результату работы данной программы вопросов нет, т.к. он в точности совпадает с первым из вышеприведенных протоколов.

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

listOf(async { с = a+b }, async{ а = b+c })

Как показало тестирование (это можно сделать в online-режиме на сайте Kotlin — kotlinlang.org/#try-kotlin), его применение приводит к совершенно непредсказуемому результату, который к тому же меняется от запуска к запуску. И лишь более внимательный анализ исходной программы привел к правильному коду.

Код, который содержит ошибку с точки зрения функционирования программы, но легитимен с точки зрения языка, заставляет опасаться за надежность программ на нем. Это мнение, наверное, может быть оспорено знатоками языка Kotlin. Тем не менее, легкость совершения ошибки, которую нельзя объяснить только лишь недостаточным пониманием «корутинного программирования», к подобным выводам все же настойчиво подталкивает.

4. Событийные автоматы в Qt

Ранее мы установили, что событийный автомат — это не автомат в классическом его определении. Хорош он или плох, но в какой-то мере событийный автомат все же родственник классических автоматов. Дальний ли, ближний, но говорить об этом надо прямо, чтобы не возникало заблуждений на этот счет. Об этом мы начали разговор в [2], но все за то, чтобы его продолжить. Сейчас мы это и сделаем, рассмотрев другие примеры использования событийных автоматов в Qt.

Безусловно, событийный автомат можно рассматривать как вырожденный случай классического автомата с неопределенной и/или переменной длительностью такта, привязанного к событию. Возможность подобной интерпретации показана в предыдущей статье при решении только лишь одного и, притом, достаточно специфического примера (см. подробнее [2]). Далее мы этот пробел постараемся устранить.

Библиотека Qt связывает переходы автомата только лишь с событиями, что является серьезным ограничением. Например, в том же языке UML переход ассоциируется не только с событием, названным инициирующим событием, но и с защитным условием — логическим выражением, вычисляемым после получения события [3]. В MATLAB ситуация смягчена больше и звучит так: «если имя события не указано, то переход произойдет при наступлении любого события» [4]. Но и там и там первопричиной запуска перехода остается событие/события. А как быть, если событий нет?

Если событий нет, то… их можно попробовать создать. Листинг 3 и Рис. 4 демонстрируют, как это сделать, используя в качестве «обертки» событийного Qt-класса потомок автоматного класса LFsaAppl среды ВКПа. Здесь действие y2 с периодичностью дискретного времени автоматного пространства посылает сигнал, инициирующий запуск перехода Qt-шного автомата. Последний с помощью метода s0Exited запускает действие y1, реализующее операцию суммирования. Заметим, что событийный автомат создается действием y3 строго после проверки инициализации локальных переменных класса LFsaAppl.


Рис.4. Комбинация классического и событийного автоматов


Выше мы реализовали совсем простой автомат. Или, что точнее, комбинацию классического и событийного автоматов. Если предыдущую реализацию класса FSumABC заменить на созданную, то отличий в работе приложения просто не будет. Но для более сложных моделей ограниченные свойства событийных автоматов начинают проявляться в полной мере. Как минимум, уже в процессе создания модели. На листинге 4 представлена реализация модели элемента И-НЕ в форме событийного автомата (подробнее об используемой автоматной модели элемента И-НЕ см. [2]).


Становится понятно, что событийные автоматы в Qt базируются строго на автоматах Мура. Это ограничивает возможности и гибкость модели, т.к. действия связываются только с состояниями. В результате, например, невозможно различить два перехода из состояния 0 в 1 для автомата, приведенного на рис. 4 в [2].

Безусловно, для реализации автоматов Мили можно использовать известную процедуру перехода к автоматам Мура. Но это приводит к увеличению числа состояний и устраняет простую, наглядную и полезную ассоциацию состояний модели с результатом ее действий. К примеру, после подобных преобразований единичному состоянию выхода 1 модели из [2] необходимо сопоставить уже два состояния автомата Мура.

На более сложной модели с очевидностью начинают проявляться проблемы с условиями переходов. Чтобы их обойти для рассматриваемой программной реализации элемента И-НЕ анализ состояния входных каналов был встроен в диалог управления моделью, что и демонстрирует листинг 5.


В сумме все отмеченное явно усложняет модель и создает проблемы с пониманием ее работы. Кроме того, подобные локальные решения могут не работать при рассмотрении композиций из них. Хорошим примером в данном случае может быть попытка создания модели RS-триггера (подробнее о двухкомпонентной автоматной модели RS-триггера см. [5]). Однако удовольствие от достигнутого результата доставим испытать поклонникам событийных автоматов. Если… если, конечно, это у них получится ;)

5. Квадратичная функция и … бабочка?

Удобно изменение входных данных представлять как внешний параллельный процесс. Выше это был диалог управления моделью элемента И-НЕ. При этом скорость изменения данных может заметно повлиять на результат. Для подтверждения этого рассмотрим вычисление квадратичной функции y = ax² + bx + с, которую реализуем в форме множества параллельно функционирующих и взаимодействующих между собой блоков.

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

Итак, добавим к блоку суммирования блоки умножения, деления и возведение в степень. Имея такой набор, мы сможем «собирать» математические выражения любой сложности. Но мы можем иметь также «кубики», реализующие более сложные функции. На рис.5. показана реализация квадратичной функции в двух вариантах – многоблочном (см. стрелку с меткой – 1, а также рис. 6) и варианте из одного блока (на рис. 5 стрелка с меткой 2).


Рис.5. Два варианта реализации квадратичной функции


Рис.6. Структурная модель вычисления квадратичной функции

То, что на рис.5. кажется «размытым» (см. стрелку с меткой 3), при надлежащем увеличении (см. графики (тренды), помеченные 4) убеждает, что дело не в свойствах графики. Это результат влияния времени на вычисление переменных: переменной y1 – выходного значения многоблочного варианта (красный цвет графика) и переменной y2 – выходного значения одноблочного варианта (черный цвет). Но и тот и другой графики отличаются от «абстрактного графика» [y2(t), x(t-1)] (зеленый цвет). Последний построен для значения переменной y2 и задержанного на один такт значения входной переменной (см. переменную с именем x[t-1]).

Таким образом, чем выше скорость изменения входной функции x(t), тем сильнее будет «эффект размывания» и тем дальше будут отстоять графики y1, y2 от графика [y2(t), x(t-1)]. Обнаруженный «дефект» можно использовать в своих целях. Например, нам ни что не мешает подать на вход синусоидальный сигнал. Мы рассмотрим даже более сложный вариант, когда аналогично будет меняться также первый коэффициент уравнения. Результат эксперимента демонстрирует скрин среды ВКПа, показанный на рис. 7.


Рис.7. Результаты моделирования при синусоидальном входном сигнале

На скрине слева внизу показан сигнал, подаваемый на входы реализаций квадратичной функции. Выше него – графики выходных значений y1 и y2. Графики в виде «крылышек» — значения, построенные в двух координатах. Так, с помощью различных реализаций квадратичной функции мы нарисовали половинку «бабочки». Нарисовать целую – дело техники…

Но парадоксы параллелизма на этом не заканчиваются. На рис. 8 приведены тренды при «обратном» изменении независимой переменной x. Они проходят уже левее «абстрактного» графика (последний, отметим, не изменил своего положения!).


Рис. 8. Вид графиков при прямом и обратном линейном изменении входного сигнала

На данном примере становится очевидной «двойная» погрешность выходного сигнала по отношению к его «мгновенному» значению. И чем медленнее будет вычислительная система или выше частота сигнала, тем больше будет погрешность. Синусоидальный сигнал — пример прямого и обратного изменения входного сигнала. Именно в силу этого «крылышки» на рис.4 приняли такой вид. Без эффекта «обратной погрешности» они были бы в два раза уже.

6. Адаптивный ПИД-регулятор

Рассмотрим еще один пример, на котором проявляются рассмотренные проблемы. На рис. 9 приведена конфигурация среды ВКП(а) при моделировании адаптивного ПИД-регулятора. Приведена и структурная схема, на которой ПИД-регулятор представлен блоком с именем PID. На уровне «черного ящика» он аналогичен рассмотренной ранее одноблочной реализации квадратичной функции.

Результат сравнения результатов расчета модели ПИД-регулятора в рамках некоторого математического пакета и протокола, полученного по результатам моделирования в среде ВКП(а), представлен на рис.10, где красный график – расчетные значения, а синий — протокол. Причина их несовпадения в том, что расчет в рамках математического пакета, как показал дальнейший анализ, соответствует последовательной работе объектов, когда сначала отрабатывает ПИД-регулятор и останавливается, а затем – модель объекта и т.д. в цикле. Среда же ВКПа реализует/моделирует параллельную работу объектов соответственно реальной ситуации, когда модель и объект работают параллельно.


Рис.9. Реализация ПИД-регулятора


Рис.10. Сравнение расчетных значений с результатами моделирования ПИД-регулятора

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


Рис.11. Последовательный режим работы ПИД-регулятора и объекта управления

7. Выводы

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

Невозможно бороться с тем, что нельзя победить. Речь о времени. Такое возможно разве что только в сказке. Но есть смысл в том, чтобы его учитывать и/или даже использовать в своих целях. В современном параллельном программировании игнорирование времени приводит к множеству сложно контролируемых и выявляемых проблем — гонкам сигналов, тупикам процессов, проблемам с синхронизацией и т.д. и т.п. Технология ВКП(а) во многом свободна от подобных проблем просто потому, что включает модель реального времени и учитывает свойство конечности вычислительных процессов. Она содержит то, что ее аналоги в своем большинстве просто-напросто игнорируют.

И в заключение. Бабочки бабочками, но можно, к примеру, рассмотреть систему уравнений из квадратичной и линейной функций. Для этого достаточно к уже созданной модели добавить модель линейной функции и процесс, контролирующий их совпадение. Так решение будет найдено путем моделирования. Оно будет, скорее всего, не столь точным, как аналитическое, но получено проще и быстрее. А во многих случаях этого более чем достаточно. Да и нахождение аналитического решения — это, как правило, часто открытый вопрос.
В связи с последним вспомнились АВМ. Для тех, кто не в курсе или подзабыл, — аналоговые вычислительные машины. Структурные принципы во много общие, да и подход к нахождению решения.

Приложение

1) Видео: youtu.be/vf9gNBAmOWQ

2) Архив примеров: github.com/lvs628/FsaHabr/blob/master/FsaHabr.zip.

3) Архив необходимых dll-библиотек Qt версии 5.11.2: github.com/lvs628/FsaHabr/blob/master/QtDLLs.zip

Примеры разработаны в среде Windows 7. Для их установки раскрыть архив примеров и, если у вас не установлен Qt или текущая версия Qt отлична от версии 5.11.2, то дополнительно раскрыть также архив Qt и прописать путь к библиотекам в переменную среды Path. Далее запустить \FsaHabr\VCPaMain\release\FsaHabr.exe и с помощью диалога выбрать каталог конфигурации того или иного примера, например, \FsaHabr\9.ParallelOperators\Heading1\Pict1.C2=A+B+A1+B1\ (см. также видео).

Замечание. При первом запуске вместо диалога выбора каталога может появиться диалог выбора файла. Также выбираем каталог конфигурации и в нем какой-нибудь файл, например, vSetting.txt. Если вообще не появляется диалог выбора конфигурации, то перед запуском удалить файл ConfigFsaHabr.txt в каталоге, где находится файл FsaHabr.exe.

Чтобы не повторять выбор конфигурации в диалоге «ядро: автоматные пространства» (его можно открыть с помощью пункта меню: FSA-инструменты/Управление/Управление Пространствами), нажать кнопку «запомнить путь к каталогу» и снять выбор «вывести диалог выбора конфигурации при запуске». В дальнейшем для выбора другой конфигурации этот выбор необходимо будет установить вновь.

Литература

1. ЯПФ, конвейер, автоматные вычисления и опять… корутины. [Электронный ресурс], Режим доступа: habr.com/ru/post/488808 свободный. Яз. рус. (дата обращения 22.02.2020).
2. Автоматы — вещь событийная? [Электронный ресурс], Режим доступа: habr.com/ru/post/483610 свободный. Яз. рус. (дата обращения 22.02.2020).
3. БУЧ Г., РАМБО ДЖ., ЯКОБСОН И. Язык UML. Руководство пользователя. Второе издание. Академия АЙТИ: Москва, 2007. – 493 с.
4. Рогачев Г.Н. Stateflow V5. Руководство пользователя. [Электронный ресурс], Режим доступа: bourabai.kz/cm/stateflow.htm свободный. Яз. рус. (дата обращения 10.04.2020).
5. Модель параллельных вычислений. [Электронный ресурс], Режим доступа: habr.com/ru/post/486622 свободный. Яз. рус. (дата обращения 11.04.2020).