Как стать автором
Обновить

Взгляд на раздел «вычислительный граф» библиотеки Intel Threading Building Blocks с точки зрения разработчика BPMS системы

Время на прочтение7 мин
Количество просмотров1.8K
Мы разрабатываем систему управления бизнес-процессами и административными регламентами. Нас заинтересовал раздел tbb::flow библиотеки С++ шаблонов Intel Threading Building Blocks (TBB), так картинки, которые мы увидели в описании библиотеки, показались нам очень похожими на картинки графа бизнес-процесса систем процессной автоматизации.

При более подробном изучении TBB оказалось, что объект, с которым работает раздел tbb::flow, сильно отличается от классических бизнес-процессов, однако он оказался настолько интересным, что мы решили написать, как он воспринимается BPMS разработчиками.

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

Все операции в библиотеке трактуются как «задачи», которые динамически распределяются между ядрами процессора. Программа, написанная с использованием TBB, создаёт, синхронизирует и разрушает графы зависимостей задач в соответствии с алгоритмом. Затем задачи исполняются в соответствии с зависимостями. Этот подход позволяет программировать параллельные алгоритмы на высоком уровне, абстрагируясь от деталей архитектуры конкретной машины.

Структура библиотеки

Библиотека является коллекцией шаблонов классов и функций для параллельного программирования. В библиотеке реализованы:
  • параллельные алгоритмы: for, reduce, do, scan, while, pipeline, sort
  • потокобезопасные контейнеры: вектор, очередь, хеш-таблица
  • масштабируемые распределители памяти
  • мьютексы
  • атомарные операции
  • глобальная временная метка
  • планировщик задач
  • вычислительный граф

В библиотеке надо указать задачи. Далее сама библиотека отобразит задачи на потоки оптимальным образом.

Описание вычислительного графа

Этой конструкции посвящен раздел библиотеки — tbb::flow. Зависимости многих приложений, работающих в операционной системе, хорошо описываются в виде сообщений, перемещающихся между узлами графа потоков сообщений. Эти сообщения могут содержать данные, или просто быть сигналами того, что «предшественник» закончился. Данные сообщения в чем-то аналогичны точкам управления BPM-систем.
Узлы графа ассоциируются с приложениями — исполнителями задач. (В BPMS в узлах графа тоже исполняются задачи, но узлы ассоциируются не с исполнителями заданий, а только с самими заданиями).

Основные компоненты раздела tbb::flow

В разделе три основных компонента:
  • Граф (A graph object)
  • Узел (Nodes)
  • Ребро (Edges)

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

Объекты Узлы инициируют пользовательские функциональные объекты или управляют сообщениями как входящими/исходящими относительно других узлов.
Ребра являются связями между узлами (аналогичны переходам в BPMS).

Протокол передачи сообщений

Ребра динамически переключаются между Pull и Push протоколами. Граф можно представить в виде конструкции G = ( V, S, L ), в которой V – множество узлов, S – множество ребер, использующих Push — протокол, L – множество ребер, использующих Pull – протокол.

Для каждого ребра (Vi, Vj), Vi является предшественником (predecessor, или sender) and Vj является последователем (successor, или receiver). в случае push протокола (S) сообщения, пересылаемые по ребру, инициируются предшественником, который пытается передать их получателю. В случае pull протокола (L) сообщения инициируются последователем (получателем), который пытается получить их от предшественника (отправителя).

Если попытка передачи сообщения по ребру не удалась, то ребро переключается в режим другого протокола. Это очень интересная конструкция, в BPMS ничего подобного нет, там узел не может «отразить» точку управления.

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

Объекты — Body Objects

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

Body объекты, передаваемые между узлами, копируются. Поэтому изменение Body объекта в узле-receiver не изменяет соответствующего Body объекта в узле-sender. Это также сильно отличается от BPMS, т.к в них в точках управления не содержится данных, точки управления являются только маркерами, указывающими на активные узлы бизнес-процесса, а данные находятся в переменных, относящихся ко всему экземпляру бизнес-процесса.

Типы вершин (типы узлов графа) и описание того, как они работают


Блок узлов Buffering

image

Узел buffer_node. У узла есть неограниченный буфер для сообщений типа «Т». Узел «прокидывает» сообщения своим successor’ам (какому-то одному из successor’ов) в случайном порядке. Если successor отражает сообщение, то узел пытается направить это сообщение другому successor’у

Узел queue_node. У узла есть неограниченный буфер для сообщений типа «Т». Узел «прокидывает» сообщения в порядке FIFO (какому-то одному из successor’ов). При этом successor’ы перебираются в том порядке, в котором они зарегистрированы в узле. Если successor отражает сообщение, то узел посылает это сообщение следующему в списке successor’у

Узел priority_queue_node. Узел «прокидывает» сообщения в порядке приоритета. (То есть, из всех имеющихся сообщений узел сначала пытается прокинуть сообщение с наибольшим приоритетом). Попытки отправить сообщение продолжаются пока какой-либо из successor’ов не примет сообщение, либо будут перебраны все successor’ы. Если какой-либо из successor’ов принял сообщение, то оно удаляется из буфера.

Узел sequencer_node. У узла есть неограниченный буфер для сообщений типа «Т». Узел «прокидывает» сообщения в последовательном порядке… Если successor отражает сообщение, то узел посылает это сообщение следующему successor’у

Блок узлов Split / Join

image

Узел join_node. Узел создает кортеж (вектор) из сообщений, пришедших по всем входящим ребрам, размножает и «прокидывает» этот кортеж всем своим successor’ам. Узел поддерживает три политики буферизации сообщений: резервирование, очередь и tag_matching.

Политика queueing: Все входящие сообщения на каждом ребре выстраиваются по принципу first-in first-out. Если на каждом ребре есть хотя бы одно сообщение, то все first-out сообщения снимаются с ребер и кортеж отправляется всем successor’ам

Политика reserving: На каждом ребре допускается только 1, или 0 сообщений. Пришедшие сообщения по ребру, на котором уже есть сообщение, отражаются. Дальше предпринимаются попытки сделать pull у predecessor’ов, от которых на ребрах нет сообщений. Если по каждому ребру удалось получить сообщение, то все сообщения снимаются с ребер и кортеж отправляется successor’ам

Политика tag_matching: Для каждого входящего сообщения на каждом ребре выполняется специальный подготовленный пользователем функциональный объект, который ставит в соответствие сообщению tag. Затем сообщения на каждом ребре группируются в hash table в соответствии со своими tag’ами. Если на каждом ребре есть хотя бы одно сообщение с данным tag’ом, то все такие сообщения снимаются с ребер и кортеж отправляется всем successor’ам

Узел or_node. Узел размножает и «прокидывает» сообщение всем своим successor’ам, независимо от того, по какому входящему ребру это сообщение пришло.

Узел split_node. Узел, у которого есть одно входящее ребро и более одного исходящего. По входящему переходу узел получает кортежи сообщений. Узел является вариантом multifunction_output_node, у которого body посылает каждый элемент входящего кортежа по выходящему ребру в соответствии с индексом элемента в кортеже.

Блок узлов Functional

image

Узел source_node. У этого узла может отсутствовать predecessor. Узел никогда не выполняется параллельно. Узел выполняет свой body function и рассылает результат одновременно всем своим successor’ам.

Узел continue_node. После того, как узел получает message от predecessor, он выполняет свой body objects. Только после этого он перенаправляет continue_msg своему successor’у

Узел function_node. У узла есть ограничение на одновременно выполняемые действия. Если узел не может обработать сообщение сразу, то он кладет сообщение в FIFO buffer. Можно сделать такую настройку, что если FIFO buffer переполнен, то входящему сообщению узел отказывает в обработке.

Узел multioutput_function_node. Узел, у которого есть только одно входящее ребро и более одного исходящего. У узла предусмотрено ограничение на количество одновременно обрабатываемых входящих сообщений. Когда ограничение превышено, узел выполняет для входящих сообщений body, которые были заданы пользователем. Эти body создают сообщения, которые отправляются successor’ам.

Блок узлов Other

image

Узел broadcast_node. Узел размножает и «прокидывает» входящее сообщение всем своим successor’ам

Узел write_once_node. У этого узла есть буфер только с одним элементом, который не может быть динамически заменен. Только после явной команды очистки буфер может принять новое сообщение.

Узел overwrite_node. У этого узла есть буфер только с одним элементом, который может быть динамически заменен (overwrite).

Узел limiter_node. Узел, который считает и ограничивает количество сообщений, которые через него проходят. Узел размножает и «прокидывает» входящее сообщение всем своим successor’ам, но перестает принимать новые сообщения в случае превышения лимита сообщений

Мы видим, что функциональность этих узлов существенно богаче функциональности узлов BPMS. Аналогично узлам раздела tbb::flow, в BPMS существует возможность размножения точек управления для всех исходящих из узла переходов, также есть возможность слияния точек управления, пришедших в узел по всем входящим переходам, есть возможность «прокидывания» точек управления, пришедших из любого входящего перехода по единственному исходящему переходу. Однако в BPMS полностью отсутствует такое понятие, как буфер, нет «прокидывания» сообщения в случайном порядке, у точек управления BPMS отсутствуют приоритеты, нет понятия кортежа точек управления, отсутствуют такие понятия, как толкание и вытягивание точки управления.

Выводы


Таким образом, знакомство с разделом tbb::flow библиотеки TBB показывает разработчику BPMS с каким на самом деле простым объектом он работает и как сильно этот объект можно усложнить, расширив поведение элементов графа. Также становится понятно, насколько сильно можно увеличить функциональность BPMS, добавив в его схему дополнительные элементы, аналогичные элементам раздела tbb::flow TBB.

Ссылка на описание библиотеки TBB
Теги:
Хабы:
Всего голосов 6: ↑6 и ↓0+6
Комментарии0

Публикации