Введение
Задачи комбинаторной оптимизации широко применяются в различных прикладных областях, таких как логистика, распределение ресурсов, проектирование коммуникационных сетей, финансовые и транспортные системы, а также вопросы вычислительной химии и фармакологии. Значительная часть этих проблемных аспектов относится к классу NP-трудных [1]. Как демонстрируют данные, приведенные в табл. 1, применение традиционных вычислительных архитектур на базе универсальных микропроцессоров (CPU) становится ограничивающим фактором при решении таких задач в реальном времени. Для целей оперативного управления, где период дискретизации составляет миллисекунды (например, управление быстропротекающими электромеханическими процессами или MPC-регулирование с дискретными ограничениями), время поиска оптимального решения на CPU многократно превышает допустимое критическое время цикла [2]. При увеличении времени вычисления управляющего воздействия в системе возникает дополнительная задержка формирования окончательного решения. В замкнутом контуре это приводит к ухудшению динамических свойств системы и снижению запасов устойчивости, а при превышении допустимых значений может вызвать нарушение технологического режима.
Как известно, решение задач комбинаторной оптимизации с помощью цифровых компьютеров, основанных на архитектуре фон Неймана, сопряжено с трудностями, учитывая экспоненциальный рост требуемых ресурсов в отношении вычислительной мощности и задержки по мере увеличения масштаба задач [3, 4]. Поэтому существует острая необходимость в изучении новых аппаратных конструкций с альтернативными архитектурами и алгоритмами, которые позволят эффективно преодолеть отмеченные проблемы.
Таким образом, изучение возможностей использования различных ускорителей, которые могут стать мощной основой для эффективного моделирования и решения широкого спектра задач оптимизации с переменными параметрами, является актуальным направлением научного поиска, которое и обусловило выбор темы данной статьи.
Особенности применения ускорителей на основе машин Изинга для эффективного поиска решений сложных оптимизационных задач с использованием различных технологий и аппаратных архитектур, включая квантовый отжиг со сверхпроводящими кубитами, классический отжиг в мемристоре, когерентные машины Изинга с оптическим осциллятором, рассматривают М. А. Аханова, С. В. Овчинникова, Н. В. Терехова [5], С. Л. Подвальный, Е. М. Васильев [6], Bruno Silva, Luiz Guerreiro Lopes [7].
Таблица 1
Сравнительный анализ временной эффективности решения задач комбинаторной оптимизации в контуре управления АСУ ТП
|
Тип задачи в АСУ ТП |
Характеристика пространства поиска (N) |
Критическое время цикла управления |
Время решения на CPU (Intel i7/ Xeon), |
Время решения на ускорителе (FPGA/ ASIC) |
Коэффициент ускорения |
Статус (CPU) |
|
MPC-управление с дискретными ограничениями |
20–30 бинарных переменных |
≤ 10 мс |
150÷300 мс |
0,5÷1,2 мс |
250 |
Срыв цикла |
|
Планирование загрузки агрегатов |
50–100 технологических единиц |
≤ 1 с |
15÷45 с |
0,08÷0,2 с |
200 |
Недопустимая задержка |
|
Маршрутизация транспортных потоков |
30–50 узлов графа (транспортная сеть цеха) |
≤ 100 мс |
1,5÷5,0 с |
5÷15 мс |
300 |
Остановка линии |
|
Динамическая балансировка энергоресурсов |
200+ узлов нагрузки |
≤ 5 с |
> 5 мин |
0,8÷1,5 с |
> 300 |
Потеря устойчивости |
Примечание: составлена автором на основе сравнительного анализа технической документации Intel FPGA (Altera) и AMD Xilinx, аналитических отчетов IEEE Industrial Electronics Society, а также материалов Gartner “Hype Cycle for Real-Time Infrastructure” и International Energy Agency (IEA) “Digitalization and Energy”
Типы задач комбинаторной оптимизации, которые могут быть решены с помощью аппаратного обеспечения квантового отжига, а также сравнение его эффективности с широким спектром эвристических алгоритмов детально описывают Jiangwei Shang, Zhan Zhang, Kun Zhang, Chuanyou Li, Lei Qian, Hongwei Liu [8], А. И. Лоскутов, В. А. Клыков, А. В. Столяров, Ю. В. Перелыгин [9], Н. Р. Трошкин, Т. И. Вишневская [10].
Над разработкой многоуровневой таксономии аппаратных ускорителей, которая учитывает общие аспекты, связь с хостом, архитектуру и программные характеристики, трудятся А. П. Солодовников, А. Л. Переверзев, А. М. Силантьев [11], Sheng-Yao Wu, Yan-Qi Song, Run-Ze Li, Su-Juan Qin, Qiao-Yan Wen, Fei Gao [12], Ehsan Ali [13].
Несмотря на достигнутые результаты, существенной проблемой остается обеспечение устойчивой работы замкнутых систем управления при использовании аппаратно ускоренных вычислений в условиях изменяющихся ограничений и параметров технологического процесса. Также требует дальнейшего исследования унификация аппаратных решений с типовыми архитектурами АСУ ТП.
Цель исследования – разработать гетерогенную архитектуру специализированного аппаратного ускорителя, объединяющую гибкость программного управления и быстродействие аппаратной логики, для улучшения производительности и сокращения временных затрат при решении задач комбинаторной оптимизации в АСУ ТП.
Материалы и методы исследования
В качестве материалов исследования использовались модели типовых задач комбинаторной оптимизации, возникающих в контурах управления АСУ ТП, включая задачи управления с дискретными ограничениями, планирования загрузки оборудования, маршрутизации и распределения ресурсов. Методологической основой исследования является системный анализ вычислительных процессов, реализуемых в контуре управления АСУ ТП, с последующим сопоставлением последовательной программной реализации алгоритмов комбинаторной оптимизации на универсальных микропроцессорных архитектурах и специализированной аппаратной реализации на основе ускорителей. В работе применяется метод структурно-функциональной декомпозиции, позволяющий разделить задачи верхнего уровня (постановка оптимизационной задачи, формирование критериев и ограничений) и задачи нижнего уровня, связанные с перебором дискретного множества решений и поиском глобального оптимума.
Результаты исследования и их обсуждение
Аппаратный ускоритель в научно-экспертной литературе определяется как отдельная архитектурная подструктура, которая спроектирована с использованием другого набора целей, чем базовый процессор, где эти цели вытекают из потребностей особого класса приложений [14]. В то же время отмечается, что аппаратный ускоритель не предназначен для замены базового процессора: ЦП в системе по-прежнему необходим для выполнения задач ОС и координации выполнения на самом ускорителе [15].
Вместе с тем анализ существующих архитектурных решений показывает, что прямое использование универсальных ускорителей или квантовых вычислителей в промышленных контурах управления затруднено из-за высоких накладных расходов на интерфейсное взаимодействие и отсутствия гарантий детерминированного времени отклика. Для эффективного решения задач комбинаторной оптимизации в условиях реального времени требуется не просто повышение тактовой частоты вычислений, а глубокая структурная интеграция логики перебора с потоками данных системы управления. Необходимо обеспечить такую организацию вычислительного процесса, при которой латентность передачи данных между управляющим контроллером и ядром оптимизации была бы минимизирована, а процесс проверки ограничений выполнялся бы аппаратно, параллельно с генерацией вариантов. Реализация данного подхода предопределяет необходимость синтеза оригинальной гетерогенной архитектуры, объединяющей гибкость программного управления и быстродействие аппаратной логики. Авторский подход к решению данной задачи представлен на рисунке.
Изображенная на рисунке структурно-функциональная схема иллюстрирует концепцию построения гетерогенной вычислительной системы, спроектированной для реализации методов аппаратного ускорения при решении NP-трудных задач комбинаторной оптимизации в контурах управления технологическими объектами. Основополагающим принципом данной архитектуры является физическая декомпозиция вычислительного процесса, при которой рутинные операции перебора дискретного множества вариантов, составляющие суть комбинаторной задачи, делегируются специализированному аппаратному ускорителю, в то время как задачи верхнего уровня по формированию критериев оптимизации остаются за универсальным процессором.
Структурно-функциональная схема системы управления с аппаратным ускорителем для решения задач комбинаторной оптимизации Примечание: составлен автором по результатам исследования
Правый сегмент схемы, описывающий уровень технологического процесса, представляет собой источник данных для задачи оптимизации. Многопараметрический объект управления характеризуется непрерывной динамикой, однако управляющие воздействия формируются на основе дискретного выбора из конечного множества альтернатив, что и порождает задачу комбинаторной оптимизации. Подсистема сбора данных осуществляет формирование вектора состояния, который определяет начальные условия для запуска процедуры оптимизации. Исполнительные механизмы, являясь конечными получателями результата, реализуют физическое переключение режимов работы оборудования на основе найденного оптимального комбинаторного решения.
Центральный сегмент схемы – управляющая вычислительная система – выполняет функцию подготовки задачи к аппаратному ускорению. Центральный процессор в данной архитектуре не занимается непосредственным решением комбинаторной задачи, что позволяет избежать экспоненциального роста времени вычислений. Вместо этого он формулирует математическую модель задачи: рассчитывает коэффициенты целевой функции и определяет границы допустимой области. Ключевым элементом, обеспечивающим эффективность ускорения, является контроллер прямого доступа к памяти (DMA). Он организует высокоскоростной поток данных с параметрами задачи в интерфейс ускорителя, минимизируя коммуникационные задержки, которые могли бы нивелировать выигрыш от аппаратной реализации вычислений.
Для систематизации предложенного подхода к разделению вычислительной нагрузки и обоснования преимуществ гетерогенной архитектуры, основные функции и характеристики подсистем сведены в табл. 2.
Аппаратный ускоритель является ядром системы, реализующим потоковый метод решения задачи комбинаторной оптимизации. Интерфейсный модуль обеспечивает загрузку конфигурации задачи в локальную память, выполняющую роль сверхбыстрого кэша. Конечный автомат управления синхронизирует работу вычислительного конвейера, обеспечивая темп поступления данных, необходимый для поддержания максимальной производительности. Вычислительное ядро ускорителя структурно повторяет логику алгоритма комбинаторного поиска, но реализует ее на аппаратном уровне с использованием пространственного параллелизма. Блок «Генератор комбинаторных вариантов» аппаратно реализует сканирование дискретного пространства решений (пространства поиска), формируя на каждом такте новый вектор-кандидат. Это дает возможность заменить программные циклы перебора на аппаратную генерацию, что является первым фактором ускорения.
Вторым и ключевым фактором аппаратного ускорения является блок проверки ограничений. В задачах комбинаторной оптимизации проверка допустимости решения часто занимает значительное время. В предложенной схеме этот блок функционирует как аппаратный фильтр, отсеивающий недопустимые комбинаторные варианты за один такт тактовой частоты, не пропуская их на этап вычисления целевой функции. Это позволяет радикально сократить вычислительную сложность задачи за счет раннего отсечения ветвей перебора. Блок вычисления целевой функции производит оценку качества только для валидных комбинаторных вариантов.
Таблица 2
Структурно-функциональная декомпозиция вычислительных процессов в гетерогенной системе
|
Структурный сегмент |
Выполняемые функции (задачи) |
Характер вычислений |
Механизм реализации / фактор эффективности |
|
Уровень объекта |
Сбор данных (S(t)), исполнение управляющих воздействийт |
Непрерывное время, физическая динамика |
Дискретизация параметров, физическое переключение режимов |
|
Хост-система |
Постановка задачи: расчет матриц критерия (H,f), обновление ограничений (G,h) |
Последовательная обработка, плавающая точка |
Использование DMA для прямого доступа к памяти ускорителя (разгрузка CPU) |
|
Аппаратный ускоритель |
Генерация вариантов u ∈ D, проверка ограничений, поиск глобального минимума |
Массово-параллельная потоковая обработка |
1. Аппаратная генерация вместо циклов. 2. Параллельная проверка ограничений за 1 такт. 3. Конвейерное вычисление целевой функции |
Примечание: составлена автором на основе полученных данных в ходе исследования
Завершает процесс регистр лучшего решения, который аппаратно реализует операцию минимизации. Линия обратной связи от регистра к генератору позволяет внедрить эвристики (например, метод ветвей и границ), динамически сужая пространство поиска на основе текущего найденного оптимума, что является третьим фактором ускорения процесса комбинаторной оптимизации.
Теперь рассмотрим более подробно математическое описание решаемой задачи.
Итак, формализация процесса аппаратного ускорения базируется на сопоставлении временной сложности решения задачи комбинаторной оптимизации на универсальной и специализированной архитектурах. Предположим, что задача управления сводится к поиску вектора u из дискретного конечного множества D (комбинаторное множество), мощность которого |D| = N. Задача оптимизации формулируется как поиск
,
где F(u) – целевая функция, а G(u) – система ограничений.
В классической архитектуре (без ускорения) время решения задачи Tseq определяется последовательным выполнением операций генерации, проверки и вычисления для каждого из N вариантов. Если τgen, τcheck и τcalc – время выполнения соответствующих операций в тактах процессора, то
.
Модель функционирования аппаратного ускорителя описывается системой разностных уравнений, характеризующих состояние конвейера. Генерация вариантов в ускорителе определяется оператором Ψ(τ,Rτ–1), который формирует вектор vτ на каждом такте τ. Эффект аппаратного ускорения достигается за счет конвейеризации, где время обработки одного варианта амортизируется и стремится к единице, деленной на тактовую частоту fclk и степень параллелизма P. Время решения задачи на ускорителе Tacc определяется формулой
,
где Tsetup – время инициализации, а Λ – латентность конвейера.
Математическая модель блока проверки ограничений вводит индикаторную функцию χ(vτ), которая принимает значение 1 для допустимых вариантов и 0 для недопустимых. Аппаратное ускорение здесь заключается в том, что вычисление χ(vτ) выполняется параллельно для всех ограничений за время O(1), в то время как программная реализация требует O(M) операций, где M – количество ограничений. Целевая функция
.
Это уравнение моделирует механизм аппаратной фильтрации: недопустимые варианты исключаются из процесса сравнения, не затрачивая ресурсы компаратора.
Коэффициент аппаратного ускорения S, являющийся ключевой метрикой эффективности системы для задач комбинаторной оптимизации, определяется пределом отношения времени выполнения:
Данное выражение доказывает, что предложенная архитектура обеспечивает линейный рост производительности пропорционально степени параллелизма P и тактовой частоте. Кроме того, использование обратной связи в генераторе позволяет уменьшить эффективное значение N до Neff ≪ N за счет отсечения ветвей, что обеспечивает дополнительное ускорение комбинаторного поиска, недостижимое при последовательном программном переборе.
Время решения на ЦП определяется суммой элементарных операций для каждого из N вариантов. Сложность проверки L ограничений составляет O(L), вычисления квадратичной формы – O(m2).
где α,β,γ – коэффициенты, зависящие от архитектуры набора команд (ISA).
Время решения на ускорителе определяется латентностью конвейера Λ (число ступеней) и пропускной способностью, зависящей от тактовой частоты fFPGA и степени параллелизма P (количество параллельных вычислительных ядер). Благодаря конвейеризации и аппаратной параллельной проверке ограничений:
где TDMA – время инициализации транзакции прямого доступа к памяти.
Асимптотический коэффициент ускорения при N → ∞ (для задач большой размерности) выражается пределом:
,
где Ccycles – среднее число циклов на результат в конвейере (в идеальном случае Ccycles → 1).
Из полученного выражения следует, что коэффициент ускорения линейно зависит от числа ограничений L и квадратично от размерности вектора управления m. Это доказывает, что предложенная концепция аппаратного ускорения наиболее эффективна именно для сложных многопараметрических задач комбинаторной оптимизации с большим количеством технологических ограничений, где программная последовательная проверка вносит неприемлемые задержки в контур управления реального времени.
Заключение
В процессе исследования рассмотрены особенности использования аппаратного ускорения в задачах комбинаторной оптимизации в АСУ ТП.
Ключевым научным результатом работы является предложенная структурно-функциональная организация комплекса, в которой реализован принцип физической декомпозиции вычислительного процесса: рутинные операции перебора делегированы специализированному аппаратному ускорителю с конвейерной архитектурой, тогда как функции интеллектуальной поддержки и взаимодействия с оператором сохранены за хост-системой. Установлено, что такой подход устраняет стохастическую составляющую вычислительного запаздывания, обеспечивая детерминированность цикла управления и гарантируя устойчивость системы при высоких темпах дискретизации технологических процессов.
Также в статье разработана математическая модель функционирования аппаратного конвейера, которая формализует процессы параллельной аппаратной фильтрации недопустимых вариантов и динамического сужения пространства поиска через механизм обратной связи.