ЯПФ, конвейер, автоматные вычисления и опять… корутины

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

1. Вновь о корутинах


В предыдущей моей статье, уважаемый Хабр, я только лишь прикоснулся к проблемам познания современного программирования. Последовавшая дискуссия только подтвердила спонтанно возникшие опасения: источником разногласий сразу же стали пресловутые «теоретические основы». То, что их (разногласий) могло бы не быть или они носили бы другой характер основную массу «настоящих» программистов похоже не тревожит. Более того, возможно, особо и не интересует, т.к. у программистов стимулируется в основном один интерес — код, код и только код. Ну, почти «как доктор прописал» [1]…

Затрагивая в своих статья и комментариях тему корутин, я ни сном ни духом не предполагал насколько они в «нонешнем» тренде. Поражали, правда, «минусовки» моих комментов по поводу и без. За что, мол, ребята-программисты? Однако, как мне представляется, все прояснилось после прочтения статьи о только что утвержденном С++20 и перспективах его дальнейшего развития [2]. К моему изумлению, выяснилось, что корутины находятся в первых рядах настоящих и будущих новшеств моего любимого С++ (см. также библиотеку CppCoro).

Ну, скажите, можно ли серьезно и/или спокойно воспринимать чела, который, похоже, возомнил себя невесть кем? Попал, что называется! :(

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

Описание, к чему я пришел в конечном итоге, дано в моих предыдущих статьях на Хабре. Разговор этот далеко не закончен, а пока чем запомнились сопрограммы, коли уж они стали предметом столь острого обсуждения? Единственным — «точками» остановки/переключения процессов. В отличие от потоков они позволяли предсказуемо определять поведение процессов, имитирующих параллельную работу. По идее это уменьшало и системные потери на реализацию параллелизма. Но, тем не менее, в сумме все это принципиально что-то не меняло. А поскольку «точки» просто имитировались состояниями модели автоматного программирования (АП), то на сем мое знакомство с сопрограммами было закончено.

Но я не мог предположить, что инкарнация сопрограмм, названных теперь корутинами, столь неожиданно настигнет меня. От этого и мои, возможно, неоправданные «наскоки» на них, за которые я совершенно искренне прошу прощения у апологетов корутин. Наверное, поспешил. Тем не менее, вновь открывшиеся обстоятельства не повлияли на мое отношение к сопрограммам. За новым кодом, за рассуждениями в их пользу я так и не увидел чего-то принципиально нового. Правда, хочу отметить, что сопрограммы мне все же ближе и понятнее потоков, т.к. содержат, как я уже сказал выше, аналог множества внутренних состояний конечных автоматов (КА).

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

2. Ярусно-параллельная и конвейерная формы алгоритмов


Предположим необходимо вычислить выражение:

y = (((a+b)*(c+d))+((e*f)+(q+h))).

Также пусть определено время выполнения операций, задаваемое в условных единицах дискретного времени — тактах, где сложение занимает 1 такт, умножение — 5 тактов.
Исходя из логики вычисления выражения, времени исполнения операций и количества промежуточных переменных, в одном из вариантов распределение операций по ярусам и само число ярусов может выглядеть, например, следующим образом:

t1 = a+b; t2 = c+d; t3 = e*f; t4 = q+h;
Ярус0: t1; t2; t3; t4;
Ярус1: t5 = t1*t2; t6 = t3+t4;
Ярус2: t7 = t5+t6;

Графически это демонстрирует рис. 1, где приведено два варианта распределения вычислений по ярусам и проставлено время вычисления в тактах. Их сравнение показывает, что в общем случае уменьшение числа ярусов отнюдь не означает автоматически сокращение времени вычислений.

image
Рис. 1. Ярусно-параллельная форма вычисления выражения

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

image
Рис. 2. Параллельная ЯПФ

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

image
Рис. 3. Конвейерная модель

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

3. Автоматная модель вычисления выражений


Если снять ограничения на синхронизацию операций, то ЯПФ можно превратить в схему, которая будет генерировать результат, как конвейер, но не иметь ограничений, связанных с последовательностью и временем выполнения операций. Такая логическая сеть схема с демонстрацией операции сложения (реализация умножения аналогична) в форме модели сети КА показана на рис. 4.

image
Рис. 4. Вычисления выражений на базе сети конечных автоматов

Можно видеть, что сеть будет постоянно выдавать результат с задержкой, равной 7 тактам, т.е. как и самая быстрая модель ЯПФ (рис. 7). К ее недостаткам можно отнести нестабильность выхода, связанную с гонками данных. Например, одновременное изменение значения переменных в парах переменных g, h и e, f приведет к изменению t4 на следующем такте, через один такт к изменению переменной t6 и еще через такт — выходной переменной t7 (см. рис. 1 и рис. 4). В то же время через 5 тактов изменится переменная t3, что приведет к изменению и выдаче уже окончательно установившихся значений переменных t6, t7.

image
Рис. 5. Моделирование ЯПФ сетью автоматов

На рис. 5 показано, как введение дополнительного блока позволяет смоделировать вычисления ЯПФ. Аналогично можно сымитировать модель конвейерных вычислений, а также заблокировать изменение выхода, связанное с гонками данных.

3. Выводы


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

Не устану повторять, что меня привлекает концепция визуального программирования, реализованная в пакете Stateflow в MATLAB. Здесь также можно создать нужные автоматы-операции, а затем, используя их, как стандартные блоки, «нарисовать» схему вычисления любого выражения, которая после компиляции превратится в работающую программу (например, на том же С++). При этом в процессе проектирования будут доступны средства визуализации и отладки, характерные именно для технологии автоматного программирования.

Правда, может возникнуть вопрос — зачем постоянные ссылки на некую неизвестную среду ВКПа, если есть Stateflow? А вот об этом мы поговорим еще отдельно…

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

Литература

1. Программисты, давайте изучать исходники классических программ. [Электронный ресурс], Режим доступа: habr.com/ru/post/488808 свободный. Яз. рус. (дата обращения 22.02.2020).
2. С++20 утвержден! Чего ждать и к чему готовиться разработчикам С++23. [Электронный ресурс], Режим доступа: habr.com/ru/company/yandex/blog/488588 свободный. Яз. рус. (дата обращения 20.02.2020).
Источник: https://habr.com/ru/post/489664/


Интересные статьи

Интересные статьи

Возможность интеграции с «1С» — это ключевое преимущество «1С-Битрикс» для всех, кто профессионально занимается продажами в интернете, особенно для масштабных интернет-магазинов.
Как широко известно, с 1 января 2017 года наступает три важных события в жизни интернет-магазинов.
От скорости сайта зависит многое: количество отказов, брошенных корзин. Согласно исследованию Google, большинство посетителей не ждёт загрузки больше 3 секунд и уходит к конкурентам. Бывает, что сайт ...
Реализация ORM в ядре D7 — очередная интересная, перспективная, но как обычно плохо документированная разработка от 1с-Битрикс :) Призвана она абстрагировать разработчика от механики работы с табл...
Один из самых острых вопросов при разработке на Битрикс - это миграции базы данных. Какие же способы облегчить эту задачу есть на данный момент?