Применение параллельных вычислительных систем для оптимального выбора технологического оборудования
Оптимизация химико-технологических систем: от теории к высокопроизводительным вычислениям
В современной химической промышленности проектирование многоассортиментных производств представляет собой сложную инженерную задачу. Выбор оптимального аппаратурного оформления (АО) — определение числа и типоразмеров оборудования для каждой технологической стадии — является NP-трудной задачей дискретной оптимизации. В монографии А.Б. Борисенко «Применение параллельных вычислительных систем для оптимального выбора технологического оборудования» представлен комплексный подход к решению этой проблемы с использованием современных методов высокопроизводительных вычислений.
Математическое моделирование и сложность задачи
Автор начинает с постановки задачи, где критерием оптимальности выступают суммарные капитальные затраты, а ограничения накладываются на работоспособность системы и время выпуска продукции. Математическая модель, детально описанная в работе, учитывает периодический характер работы оборудования, материальные индексы и временные параметры циклов. Из-за «комбинаторного взрыва» классические методы перебора становятся неэффективными при увеличении числа доступных типоразмеров оборудования, что диктует необходимость использования методов ветвей и границ и метаэвристических подходов.
Параллельные алгоритмы и гетерогенные системы
Центральная часть исследования посвящена распараллеливанию алгоритмов. Автор последовательно рассматривает реализацию метода ветвей и границ для систем с общей памятью (OpenMP) и распределенной памятью (MPI). Особое внимание уделено гетерогенным вычислительным системам, оснащенным графическими ускорителями (GPU). Использование CUDA позволяет перенести наиболее трудоемкие вычисления на тысячи ядер графического процессора. В работе предложены методы оптимизации кода для GPU, включая эффективное использование разделяемой памяти и минимизацию дивергенции ветвлений, что позволяет существенно сократить время поиска решения.
Гибридные метаэвристики и настройка параметров
Поскольку детерминированные методы при решении задач сверхвысокой размерности требуют значительных временных затрат, автор предлагает гибридный метаэвристический алгоритм, сочетающий алгоритм муравьиной колонии (ACO) и имитацию отжига (SA). ACO используется для поиска допустимого начального решения, а SA — для его последующей оптимизации.
Ключевым вкладом работы является разработка метода настройки параметров алгоритма (α, β, ρ). Автор предлагает три подхода: случайный, константный и мультиконстантный. Использование статистического анализа результатов многократных запусков на GPU позволило найти оптимальные диапазоны параметров, которые сократили время поиска допустимого решения в десятки раз. Исследование показало, что предложенный алгоритм хорошо масштабируется на несколько графических ускорителей, обеспечивая ускорение, близкое к линейному, и позволяя решать задачи, недоступные для классических методов.
Практическая значимость
Монография демонстрирует, что интеграция методов математического программирования, параллельного программирования и метаэвристической оптимизации позволяет решать задачи проектирования химических производств на качественно новом уровне. Предложенные методы настройки параметров и стратегии использования GPU делают возможным получение квазиоптимальных решений за считанные секунды, что критически важно для оперативного проектирования и модернизации современных химико-технологических систем. Работа будет полезна как специалистам в области высокопроизводительных вычислений, так и инженерам-технологам, занимающимся автоматизацией проектирования.
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
- 02.03.02: Фундаментальная информатика и информационные технологии
- 02.03.03: Механика и математическое моделирование
- 03.03.02: Прикладная математика и информатика
- ВО - Магистратура
- 09.04.01: Информатика и вычислительная техника
- 27.04.07: Наукоемкие технологии и экономика инноваций
- ВО - Специалитет
- 09.05.01: Применение и эксплуатация автоматизированных систем специального назначения
- Аспирантура
- 09.06.01: Информатика и вычислительная техника
ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ДЛЯ ОПТИМАЛЬНОГО ВЫБОРА ТЕХНОЛОГИЧЕСКОГО ОБОРУДОВАНИЯ А.Б. БОРИСЕНКО Москва ИНФРА-М МОНОГРАФИЯ
УДК 004.272.2+519.854+66.011(075.4) ББК 32.973 Б82 Рекомендовано Научно-техническим советом Федерального государственного бюджетного образовательного учреждения высшего образования «Тамбовский государственный технический университет» Р е ц е н з е н т ы: Туголуков Е.Н., доктор технических наук, профессор, профессор кафедры «Техника и технологии производств нанопродуктов» Тамбовского государственного технического университета; Обухов А.Д., доктор технических наук, доцент, профессор кафедры «Системы автоматизированной поддержки принятия решений» Тамбовского государственного технического университета; Соловьев Д.С., доктор технических наук, доцент, профессор кафедры «Математическое моделирование и информационные технологии» Тамбовского государственного университета имени Г.Р. Державина ISBN 978-5-16-115455-7 (online) © Борисенко А.Б., 2026 Борисенко А.Б. Б82 Применение параллельных вычислительных систем для оптимального выбора технологического оборудования : монография / А.Б. Борисенко. — Москва : ИНФРА-М, 2026. — 174 с. — DOI 10.12737/2287903. ISBN 978-5-16-115455-7 (online) Монография посвящена разработке и исследованию параллельных алгоритмов решения задачи оптимального выбора аппаратурного оформления химико-технологических систем многоассортиментных химических производств — NP-трудной задачи дискретной оптимизации большой размерности. Рассмотрены математическая модель функционирования химико-технологической системы, последовательный и параллельные варианты метода ветвей и границ для вычислительных систем с общей и распределенной памятью (OpenMP, MPI) и для графических ускорителей (CUDA), гибридный метаэвристический алгоритм на основе алгоритмов муравьиной колонии (Ant Colony Optimization) и имитации отжига (Simulated Annealing), а также методы настройки его параметров с использованием как одного, так и нескольких GPU. Приведены результаты вычислительных экспериментов на многоядерных процессорах, вычислительных кластерах и графических ускорителях различных архитектур. Для научных работников, инженеров и разработчиков программного обеспечения в области параллельных и высокопроизводительных вычислений, а также аспирантов и студентов старших курсов соответствующих направлений подготовки. УДК 004.272.2+519.854+66.011(075.4) ББК 32.973 ФЗ № 436-ФЗ Издание не подлежит маркировке в соответствии с п. 1 ч. 2 ст. 1
Содержание Обозначения и сокращения 6 Введение 9 1. Постановка задачи оптимального выбора аппаратурного оформления химико-технологических систем 13 1.1. Математическая формулировка задачи . . . . . . . . . . . . 16 1.2. Математическая модель функционирования ХТС . . . . . . 19 1.2.1. Исходные данные и допущения . . . . . . . . . . . . . 20 1.2.2. Размер партии и ограничение на работоспособность . 22 1.2.3. Длительности операций . . . . . . . . . . . . . . . . . 25 1.2.4. Расписание цикла работы системы . . . . . . . . . . . 26 1.2.5. Продолжительность выпуска продукции и ограничение по времени . . . . . . . . . . . . . . . . . . . . . . 30 1.2.6. Критерий оптимальности . . . . . . . . . . . . . . . . 31 1.2.7. Вычислительные аспекты модели . . . . . . . . . . . . 32 1.3. Тестовый пример . . . . . . . . . . . . . . . . . . . . . . . . . 33 2. Последовательный алгоритм на основе метода ветвей и границ 36 2.1. Базовый вариант алгоритма . . . . . . . . . . . . . . . . . . . 37 2.2. Оценка времени выполнения отдельных частей алгоритма . 40 2.3. Оптимизация последовательного алгоритма . . . . . . . . . . 41 3. Параллельный метод ветвей и границ для многоядерных и кластерных вычислительных систем 43 3.1. Методы распараллеливания обхода дерева поиска . . . . . .
3.1.1. Особенности параллельного обхода дерева поиска . . 44 3.1.2. Статическое и динамическое разбиение дерева . . . . 45 3.1.3. Классификация методов динамической балансировки 46 3.1.4. Алгоритмические аспекты динамической балансировки загрузки . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.5. Аномалии ускорения и фактор избыточности поиска . 50 3.1.6. Методы назначаемых и выделяемых поддеревьев . . . 51 3.1.7. Распараллеливание метода ветвей и границ на графических ускорителях . . . . . . . . . . . . . . . . . . . 52 3.1.8. Методы, используемые в данной работе . . . . . . . . 53 3.2. Вычислительные системы с общей памятью (OpenMP) . . . 54 3.2.1. Разработка программы . . . . . . . . . . . . . . . . . 54 3.2.2. Результаты численных экспериментов . . . . . . . . . 55 3.3. Вычислительные системы с распределённой памятью (MPI) 58 3.3.1. Управляющий процесс (Master) . . . . . . . . . . . . . 59 3.3.2. Рабочий процесс (Worker) . . . . . . . . . . . . . . . . 60 3.3.3. Результаты численных экспериментов . . . . . . . . . 62 4. Метод ветвей и границ на графических ускорителях 65 4.1. Общие принципы и особенности программирования GPU . . 67 4.2. Разработка параллельной программы . . . . . . . . . . . . . 71 4.3. Оптимизация кода программы . . . . . . . . . . . . . . . . . 80 4.4. Результаты численных экспериментов . . . . . . . . . . . . . 84 5. Параллельный гибридный метаэвристический алгоритм на графических ускорителях 89 5.1. Краткий обзор метаэвристических алгоритмов для решения задач комбинаторной оптимизации . . . . . . . . . . . . . . . 91 5.2. Алгоритм имитации отжига (SA) . . . . . . . . . . . . . . . . 93 5.3. Алгоритм муравьиной колонии (ACO) . . . . . . . . . . . . . 99 5.4. Реализация гибридного алгоритма (ACO+SA) на GPU . . . 103 5.5. Результаты численных экспериментов . . . . . . . . . . . . . 113 6. Настройка параметров алгоритма муравьиной колонии
6.1. Подходы к настройке параметров метаэвристических алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.2. Параметры алгоритма муравьиной колонии . . . . . . . . . . 124 6.3. Предлагаемый метод настройки параметров . . . . . . . . . 126 6.4. Результаты численных экспериментов . . . . . . . . . . . . . 129 6.5. Исследование на графических ускорителях различных архитектур и на нескольких GPU . . . . . . . . . . . . . . . . . . 138 6.5.1. Организация вычислений на нескольких GPU . . . . 138 6.5.2. Экспериментальные платформы . . . . . . . . . . . . 140 6.5.3. Сравнение архитектур GPU . . . . . . . . . . . . . . . 140 6.5.4. Масштабирование параллельной программы на несколько GPU . . . . . . . . . . . . . . . . . . . . . . 142 Заключение 146 Список использованной литературы
Обозначения и сокращения АО – аппаратурное оформление КО – комбинаторная оптимизация МА – метаэвристические алгоритмы МВП – метод выделяемых поддеревьев МНП – метод назначаемых поддеревьев ММ – математическая модель МХП – многоассортиментные химические производства ОЗУ – оперативное запоминающее устройство УО – удовлетворение ограничений ФХП – физико-химические превращения ХТС – химико-технологическая система ACO – англ. Ant Colony Optimization (алгоритм муравьиной колонии) AP – англ. Assignment Problem (задача о назначениях) API – англ. Application Programming Interface (интерфейс прикладного программирования) B&B – англ. Branch-and-bound (метод ветвей и границ) BFS – англ. Breadth First Search (поиск (обход) в ширину) CES – англ. Chemical Engineering System (химико-технологическая система) CC – англ. Compute Capability (вычислительные возможности) CPU – англ. Central Processing Unit (центральный процессор) CSP – англ. Constraint Satisfaction Problem (задача удовлетворения ограничений) CUDA – англ. Compute Unified Device Architecture (унифицированная вычислительная архитектура устройств) DFS – англ. Depth-First Search (поиск (обход) в глубину) DOE – англ. Design of Experiments (планирование эксперимента)
DOP – англ. Discrete Optimization Problem (задача дискретной оптимизации) DRAM – англ. Dynamic Random Access Memory (динамическая память с произвольным доступом) DSP – англ. Digital Signal Processor (цифровой сигнальный процессор) FIFO – англ. First-In, First-Out (первым пришёл – первым вышел) FP32 – англ. 32-bit Floating Point (числа с плавающей точкой одинарной точности) FPGA – англ. Field-Programmable Gate Array (программируемая пользователем вентильная матрица) GPU – англ. Graphics Processing Unit (графический процессор) GPGPU – англ. General-Purpose Graphics Processing Units (графический процессор общего назначения) HLSL – англ. High-Level Shading Language (язык шейдеров высокого уровня) KP – англ. Knapsack Problem (задача о рюкзаке) LIFO – англ. Last-In, First-Out (последним пришёл – первым вышел) MAC – англ. Multiple Ant Colonies (множественные муравьиные колонии) MILP – англ. Mixed Integer Linear Programming (частичноцелочисленное линейное программирование) MINLP – англ. Mixed Integer Nonlinear Programming (частичноцелочисленное нелинейное программирование) MIR – англ. Multiple Independent Runs (многократный независимый запуск) MPI – англ. Message Passing Interface (интерфейс передачи сообщений) NP – англ. Non-deterministic Polynomial (недетерминированная полиномиальная) NVCC – англ. NVIDIA CUDA Compiler (компилятор CUDA) OFAT – англ. One-Factor-At-a-Time (раздельное исследование факторов) OpenCL – англ. Open Computing Language (открытый язык вычисле7
ний) OpenMP – англ. Open Multi-Processing (открытый стандарт для распараллеливания программ) SIMD – англ. Single Instruction, Multiple Data (одна инструкция, множество данных) SIMT – англ. Single Instruction, Multiple Thread (одна инструкция, множество потоков) SA – англ. Simulated Annealing (алгоритм имитации отжига) SM – англ. Streaming Multiprocessor (потоковый мультипроцессор) SMP – англ. Symmetric MultiProcessing (симметричные мультипроцессорные системы) STL – англ. Standard Template Library (библиотека стандартных шаблонов) TSP – англ. Travelling Salesman Problem (задача коммивояжёра)
Введение Одними из наиболее сложных для практического решения вычислительных задач являются NP-трудные (NP-hard) задачи комбинаторной оптимизации (КО). Задачей КО называется задача оптимизации, в которой задано конечное множество объектов и целевая функция, которая позволяет определить значение стоимости для каждого из объектов. Цель состоит в том, чтобы найти объект с минимальным (или максимальным) значением целевой функции. Объектами, как правило, являются целые числа, подмножества множества элементов, перестановки множества элементов и пр. Примером задачи КО может служить задача коммивояжёра (Travelling Salesman Problem) [1], задача о назначениях (Assignment Problem) [2], задача о рюкзаке (Knapsack Problem) [3], а также задачи планирования [4] и др. Особенностью решения таких NP-трудных задач является то, что при использовании точных (детерминированных) алгоритмов, например, полного перебора, время поиска оптимального решения NP-трудных задач растёт экспоненциально в зависимости от размера пространства поиска, наблюдается эффект т.н. «комбинаторного взрыва» (Combinatorial Explosion) [5]. В качестве основных способов повышения скорости вычислений следует отметить следующие: использование более совершенных алгоритмов; настройка параметров используемых алгоритмов; оптимизация разрабатываемых программ средствами компилятора; оптимизация программ с использованием профилировщиков (Profiling); использование более производительного аппаратного обеспечения (Hardware), в том числе, развитие технологий параллельных вычислений. При этом следует отметить, что наиболее значительно на скорость вычислений влияет выбор алгоритма решения задачи с оптимальной настройкой его параметров, а также ис9
пользуемое аппаратное обеспечение. Все известные алгоритмы решения NP-трудных задач, в том числе задач КО, можно условно разделить на три категории: точные (Exact Algorithms) [6], эвристические (Heuristic) [7] и метаэвристические (Metaheuristic) [8]. К точным алгоритмам относятся, например, такие алгоритмы, как перебор (Exhaustive Search) [9], метод ветвей и границ (Branch-andBound) [10], венгерский алгоритм (Hungarian Algorithm) [11], динамическое программирование (Dynamic Programming) [12]. Эвристические подходы основаны на правдоподобных, но никак математически не обоснованных предположениях о свойствах оптимального решения задачи [13]. Известно, что такой алгоритм позволяет получить достаточно хорошие практические решения в большинстве случаев, но при этом никак не гарантирует нахождение наилучшего результата. Также стоит отметить, что эвристики строятся исходя из «здравого смысла», и потому сильно зависят от конкретной задачи. Метаэвристики объединяют основные эвристические методы в рамках алгоритмических схем более высокого уровня, направленных на эффективное использование пространства поиска [14–16]. Среди метаэвристических алгоритмов можно выделить, в частности, поиск с запретами (Tabu Search) [17], имитация отжига (Simulated Annealing) [18], алгоритм муравьиной колонии (Ant Colony Optimization) [19], генетические алгоритмы (Genetic Algorithms) [20], метод роя частиц (Particle Swarm Optimization) [21], алгоритм пчелиной колонии (Artificial Bee Colony Optimization) [22] и др. Преимущество данных методов перед классическими эвристическими методами, основанными на методе локального поиска, в том, что они позволяют исследовать б´ольшее пространство поиска для нахождения решения, близкого к оптимальному, тогда как методы локального поиска останавливаются после нахождения локального решения в выбранной окрестности. Также следует отметить, что в настоящее время одним из перспективных методов конструирования новых высокоэффективных алгоритмов является гибридизация (hybridization) метаэвристических алгоритмов [23,24]. Одной из особенностей метаэвристических алгоритмов является на10