Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Применение параллельных вычислительных систем для оптимального выбора технологического оборудования

Бесплатно
Новинка
Основная коллекция
Артикул: 897044.01.99
Монография посвящена разработке и исследованию параллельных алгоритмов решения задачи оптимального выбора аппаратурного оформления химико-технологических систем многоассортиментных химических производств - NP-трудной задачи дискретной оптимизации большой размерности. Рассмотрены математическая модель функционирования химико-технологической системы, последовательный и параллельные варианты метода ветвей и границ для вычислительных систем с общей и распределённой памятью (OpenMP, MPI) и для графических ускорителей (CUDA), гибридный метаэвристический алгоритм на основе алгоритмов муравьиной колонии (Ant Colony Optimization) и имитации отжига (Simulated Annealing), а также методы настройки его параметров с использованием как одного, так и нескольких GPU. Приведены результаты вычислительных экспериментов на многоядерных процессорах, вычислительных кластерах и графических ускорителях различных архитектур. Для научных работников, инженеров и разработчиков программного обеспечения в области параллельных и высокопроизводительных вычислений, а также аспирантов и студентов старших курсов соответствующих направлений подготовки.

Оптимизация химико-технологических систем: от теории к высокопроизводительным вычислениям

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

Математическое моделирование и сложность задачи

Автор начинает с постановки задачи, где критерием оптимальности выступают суммарные капитальные затраты, а ограничения накладываются на работоспособность системы и время выпуска продукции. Математическая модель, детально описанная в работе, учитывает периодический характер работы оборудования, материальные индексы и временные параметры циклов. Из-за «комбинаторного взрыва» классические методы перебора становятся неэффективными при увеличении числа доступных типоразмеров оборудования, что диктует необходимость использования методов ветвей и границ и метаэвристических подходов.

Параллельные алгоритмы и гетерогенные системы

Центральная часть исследования посвящена распараллеливанию алгоритмов. Автор последовательно рассматривает реализацию метода ветвей и границ для систем с общей памятью (OpenMP) и распределенной памятью (MPI). Особое внимание уделено гетерогенным вычислительным системам, оснащенным графическими ускорителями (GPU). Использование CUDA позволяет перенести наиболее трудоемкие вычисления на тысячи ядер графического процессора. В работе предложены методы оптимизации кода для GPU, включая эффективное использование разделяемой памяти и минимизацию дивергенции ветвлений, что позволяет существенно сократить время поиска решения.

Гибридные метаэвристики и настройка параметров

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

Ключевым вкладом работы является разработка метода настройки параметров алгоритма (α, β, ρ). Автор предлагает три подхода: случайный, константный и мультиконстантный. Использование статистического анализа результатов многократных запусков на GPU позволило найти оптимальные диапазоны параметров, которые сократили время поиска допустимого решения в десятки раз. Исследование показало, что предложенный алгоритм хорошо масштабируется на несколько графических ускорителей, обеспечивая ускорение, близкое к линейному, и позволяя решать задачи, недоступные для классических методов.

Практическая значимость

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

Текст подготовлен языковой моделью и может содержать неточности.

43
Борисенко, А. Б. Применение параллельных вычислительных систем для оптимального выбора технологического оборудования : монография / А.Б. Борисенко. — Москва : ИНФРА-М, 2026. — 174 с. - ISBN 978-5-16-115455-7. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2287903 (дата обращения: 18.11.2026)
Фрагмент текстового слоя документа размещен для индексирующих роботов
ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ 
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 
ДЛЯ ОПТИМАЛЬНОГО ВЫБОРА 
ТЕХНОЛОГИЧЕСКОГО 
ОБОРУДОВАНИЯ
А.Б. БОРИСЕНКО
Москва
ИНФРА-М
МОНОГРАФИЯ


УДК  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