Конфигурирование память-ориентированной системы управления движением

Зеленский Александр Александрович ORCID: 0000-0002-3464-538X кандидат технических наук ведущий научный сотрудник; Научно-производственный комплекс "Технологический центр" 124498, Россия, г. Москва, пл. Шокина, 1, строение 7 Zelenskii Aleksandr Aleksandrovich PhD in Technical Science Leading researcher; Scientific and production complex 'Technological Center' 124498, Russia, Moscow, Shokin square, 1, building 7 zelenskyaa@gmail.com Другие публикации этого автора

Грибков Андрей Армович ORCID: 0000-0002-9734-105X доктор технических наук ведущий научный сотрудник; Научно-производственный комплекс "Технологический центр" 124498, Россия, г. Москва, пл. Шокина, 1, строение 7 Gribkov Andrei Armovich Doctor of Technical Science Leading researcher; Scientific and production complex 'Technological Center' 124498, Russia, Moscow, Shokin square, 1, building 7 andarmo@yandex.ru Другие публикации этого автора

Исследование выполнено при поддержке Российского научного фонда по гранту No 24-19-00692, http://rscf.ru/project/24-19-00692/

Введение

Проблематика управления движением в реальном времени, необходимого для современных промышленных роботов, станков и другого технологического оборудования, складывается из нескольких взаимосвязанных составляющих. Центральной из них является проблема реализуемости управления, заключающаяся в определении (и обеспечении) возможности управления движением с быстродействием, необходимым для обеспечения заданной точности воспроизводства скорости и траектории движения. Исследования, проведенные авторами, показали ^{[1, 2]}, что проблема реализуемости управления обуславливает крайне жесткие требования к быстродействию систем управления сложными объектами. К таким сложным объектам управления, в частности, относятся прецизионное технологическое оборудования с большим числом одновременно управляемых осей (пять осей и более).

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

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

Согласно методологии, разработанной авторами с соавторами, сложность объекта управления зависит от числа типов элементов и среднего количества элементов одного типа в системе, числа типов связей и среднего количества связей одного типа в системе, числа контролируемых параметров, посредством которых описывается состояние отдельного элемента системы, а также числа отслеживаемых состояний контролируемого параметра ^[1].

Быстродействие системы управления движением сложным объектом ограничено действием трех групп факторов, получивших образные названия стена мощности (the power wall), стена памяти (the memory wall) и стена частоты (the frequency wall) ^[3]. Для практического преодоления этих трех «стен» и повышения в результате быстродействия системы управления движения должны быть решены три задачи, имеющие решение за счет совершенствования архитектуры вычислительных машин: во-первых, необходимо уменьшить объем обрабатываемого потока данных за счет использования параллельных вычислений; во-вторых, необходимо увеличить скорость передачи данных между элементами вычислительной машины за счет применения технологий обработки в памяти (PIM) ^[4] или обработки вблизи памяти (NMC) ^[5]; в-третьих, необходимо устранить очереди при одновременном обращении к одной памяти нескольких вычислительных устройств за счет физического разделения памяти между устройствами.

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

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

Практическое решение проблемы реализуемости управления движением сложного объекта сводится к распараллеливанию выполнения операций управления и, соответственно, к определению оптимального взаимного распределения затрат времени на отдельные операции с учетом установленных алгоритмических ограничений по последовательности их выполнения. Заметим, что именно с наличием таких ограничений связано существование закона Амдала ^[7].

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

Подходы к конфигурированию цикла системы управления

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

Рисунок 1. Диаграмма оптимизированного цикла СУ промышленного робота:

t₁₁₁, t₁₂₁, t₁₃₁, t₁₄₁, t₁₅₁ — задержки коммуникационной сети при передаче данных от датчиков и сенсоров в модули очувствления; t₁₁₂ — задержка системы технического зрения, СТЗ (без ИНС); t₁₁₃ — задержка искусственной нейронной сети (ИНС) при обработки данных для СТЗ; t₁₂₂ — задержка системы распознавания речи, СРР (без ИНС); t₁₂₃ — задержка ИНС при обработки данных для СРР; t₁₃₂, t₁₄₂, t₁₅₂ — задержки модулей обработки данных от датчиков положения, скорости и др.; t₂₁₁, t₂₂₁ — задержки ядра: интерпретатора (не в каждом цикле) и задержка при обработке данных от модулей очувствления; t₃₁₁ — задержка модуля трансформации; t₃₁₂ — задержка модуля интерполяции; t₃₁₃ — задержка модуля эквидистантной коррекции; t₃₂₁ — задержка модуля предварительного просмотра; t₄₁₁ — задержка модуля разгона-торможения; t₅₁₁, t₅₂₁, t₅₃₁, t₅₄₁ — задержки регуляторов исполнительных устройств; | | — задержка записи/чтения данных в общей памяти.

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

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

(1)

где u_max — число групп операций в цикле управления; p_umax — количество параллельных потоков обработки данных в u-ой группе; m_up — количество элементов в p-ом параллельном потоков обработки данных в u-ой группе.

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

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

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

u-я группа операций формируется из множества элементов A_u = {a_u1,a_u2,…a_uj,…a_un(u)}, каждый из которых a_ui = {t_ui,w_ui} характеризуется временем t_ui, необходимым для выполнения операции управления, соответствующей данному элементу, и ресурсами w_ui, необходимыми для реализации данного элемента. В качестве ресурсов элемента может рассматриваться потребный объем памяти и/или вычислительная мощность (число элементарных операций, необходимых для выполнения рассматриваемой операции управления, за единицу времени ее выполнения).

Элементы a_ui не могут быть задействованы в произвольном порядке. Попарное определение порядка задействования элементов задается в виде матрицы отношений

(2)

в которой каждый элемент k_ij ∊ {–1,0,1} определяет последовательность элементов i и j: «–1» – j потом i, «0» – порядок не имеет значения, «1» – i потом j.

Из элементов u-ой группы формируется выборка для отдельного p-го потока, в которой каждый ее элемент отожествляется с элементом из множества u-й группы:

(3)

причем элементы не повторяются

(4)

и реализуются в правильном порядке относительно всех предшествующих по времени элементов во всех (ранее определенных) потоках, включая свой,

(5)

где величина j_d для потока d определяется исходя из условия

i(a_uj^(p)) – значение номера элемента в исходном множестве u-ой группы, соответствующее элементу a_uj^(p) в выборке для p-го потока.

Если K_u = –1, то все элементы, уже включенные в выборку (от 1 до j), переставляются исходя из условия (5).

Каждый элемент в выборке для p-го потока, как и в исходном множестве u-ой группы, определяется потребными временем и ресурсами:

(6)

Состав выборки для p-го потока u-ой группы представляет собой множество из m_up элементов

(7)

причем сумма элементов всех потоков равна числу элементов nu в исходном множестве u-ой группы и элементы в различных потоках (множествах) не повторяются:

(8)

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

Для реализации дальнейшей оптимизации необходимо задать функцию суммарных ресурсов, задействованных элементами во всех потоках u-ой группы в заданный момент времени:

(9)

где номер соответствующего элемента j определяется из выражения

Теперь можно определить длительность части цикла управления, соответствующей выполнению операций u-ой группы в виде множества A_u с заданной последовательностью элементов:

(10)

причем должно выполняться условие

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

Для получения минимального времени отработки операций u-ой группы необходимо провести аналогичный анализ для множества A_u с другими последовательностями элементов (число вариантов перестановок N_u = n_u!) и другими значениями числа элементов в потоках.

Число вариантов перестановок быстро растет по мере роста числа элементов в множестве. Например, если при n_u = 10 (реализуемом при объединении некоторых связанных элементов, см. рис. 1) имеем приемлемое значение N_u = n_u! = 3.6 × 10⁶, то при n_u = 15 имеем N_u = n_u! = 1.3 × 10¹², а при n_u = 20 имеем N_u = n_u! = 2.4 × 10¹⁸.

Значения числа элементов в потоках для группы u могут быть заданы в виде множества

(11)

где p_max – число потоков в u-ой группе, причем

Число вариантов множества M_uj представляет собой количество упорядоченных разбиений числа n_u элементов в исходном множестве u-ой группы и равно j_max = 2^n_u-1, что в случае n_u = 10 дает j_max = 512, в случае n_u = 15 – j_max = 1.6 × 10⁴, а в случае n_u = 20 – j_max = 5.2 × 10⁵.

Минимальное время отработки операций u-ой группы:

(12)

где M_uj – j-й (из j_max) вариант множества M_uj, A_uj – i-я (из N_u) перестановка исходного множества A_u.

Исходя из приведенных выше зависимостей, число вариантов, задаваемых τ_u(A_ui,M_ui), равно N_u · j_max = n_u! · 2^n_u-1 и составляет в зависимости от числа элементов в исходном множестве u-ой группы от 1.8 × 10⁹ при n_u = 10 до 2.1 × 10¹⁶ при n_u = 15 и 1.2 × 10²⁴ при n_u = 20. Последние числа вариантов слишком велики и не могут быть на практике проанализированы.

Максимальная сложность данного оптимизационного алгоритма соответствует нотации O(n!∙2^n–1∙n²), где n² – сомножитель, связанный с сортировкой выборки перебором из исходного множества u-ой группы. Данный характер сложности оказывает критическое негативное влияние на практическую реализуемость полного перебора всех возможных вариантов. Такая ситуация является типичной для задач комбинаторной оптимизации.

Средством решения данной задачи комбинаторной оптимизации при большом числе элементов в группе является использование стохастических методов со случайной генерацией последовательности элементов в исходном множестве A_u для u-ой группы и множества M_uj значений числа элементов в потоках этой группы. Для повышения эффективности случайной выборки можно целенаправленно обеспечивать существенное различие последовательностей элементов, разбиение групп на потоки с сопоставимым числом элементов, ограничивать вариативность числа потоков исходя из доступных ресурсов для всей группы и средних значений ресурсов отдельных элементов, собирать потоки из элементов исходного множества не последовательно, а параллельно (поочередно добавляя элементы в разные потоки) и т.д. В результате N_u и j_max не будут зависеть от n_u (будут примерно постоянными, устанавливаемыми исходя из экспертной оценки разработчика), сложность алгоритма существенно снизится и может соответствовать сложности сортировки, имеющей в случае простого перебора нотацию O(n²).

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

Длительность цикла управления определяется следующим образом:

(13)

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

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

Для данного варианта оптимизации справедливы формулы (2-10), полученные нами ранее для варианта оптимизации по времени.

Ресурсы, потребные для реализации всех операций u-ой группы цикла управления:

(14)

При реализации оптимальной по ресурсам конфигурации цикла управления (минимальные) потребные ресурсы составят

(15)

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

Конфигурация цикла управления с оптимизацией по времени или ресурсам – оптимизационные задачи, относящаяся к группе NP-полных задач. Ограничениями задачи конфигурирования цикла управления с комбинаторной оптимизацией являются, соответственно, допустимые (вычислительные) ресурсы системы управления или длительность цикла управления.

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

Существующие алгоритмы оптимизации, однако, могут быть использованы для решения локальных задач в рамках комбинаторной оптимизации. В частности, использование алгоритмов сравнения при упорядочивании выборки для p-го потока u-ой группы позволяет снизить время выполнения алгоритма сортировки с O(n²) до O(n log n) ^{[8, с. 206-207]}.

К числу лучших по времени и памяти алгоритмов сортировки относятся ^[9]: merge sort (сортировка слиянием ^{[8, с. 181-192]}), heapify и heap sort (пирамидальная сортировка ^[10]) – лучшее, среднее и худшее время O(n log n), память O(n); quik sort (сортировка Хоара) — лучшее и среднее время O(n log n), худшее время O(n²), память O(log n); tree sort (сортировка с помощью двоичного дерева) – лучшее время O(n), среднее и худшее время O(n log n), память O(n); timsort (гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием) и binary insertion sort (гибридный алгоритм сортировки, сочетающий сортировку вставками с бинарным поиском места вставки ^[11]) – лучшее время O(n), среднее и худшее время O(n log n), память O(n).

Адаптивное конфигурирование цикла системы управления

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

В каждый момент времени нам известны элементы, реализуемые на каждом потоке u-ой группы {a_u⁽¹⁾,a_u⁽²⁾,...a_u^(p),...a_u^(p_max)}, причем каждый элемент взят из исходного множества элементов u-ой группы, после чего в исходном множестве он помечается как использованный. Это реализуется заданием для элементов a_ui в исходном множестве, наряду со временем и ресурсами, параметра z_ui ∊ {1,0} «использован» / «не использован».

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

(16)

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

(17)

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

После завершения выполнения элементов 1-ой группы запускается выполнение элементов 2-ой группы и т.д. Цикл управления завершается тогда, когда заканчиваются элементы во множествах всех групп.

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

Для реализации адаптивного конфигурирования, которое в общем случае не гарантирует минимизации длительности цикла управления, могут быть использованы указанные выше алгоритмы оптимизации сортировки. Они применимы как для реализации условия (16), так и (17).

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

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

Многократное адаптивное конфигурирование цикла управления предполагает его выполнение с разными перестановками исходного множества элементов заданной группы.

По результатам j-го адаптивного конфигурирования формируется множество

(18)

образованное элементами b_ujn = {u, i, p}, где {u, i, p} – номер группы, номер элемента в исходном множестве элементов u-ой группы и номер потока для n-го элемента множества B_uj.

Интервал времени, необходимый для выполнения элементов p-го потока u-ой группы, определяется из условия

(19)

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

(20)

Наименьшая длительность части цикла управления, за которую выполняются все элементы u-ой группы, из всех j_max реализаций адаптивного конфигурирования:

(21)

Наименьшая длительность цикла управления, получаемая по результатам многократного адаптивного конфигурирования:

(22)

Выводы

Резюмируем проведенное в статье исследование:

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

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

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

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

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