Масштабирование оптимизации решений до 100 млн переменных с NVIDIA cuOpt mPDLP

В современном мире бизнес-решения всё чаще опираются на сложные математические модели. От управления глобальными цепочками поставок до балансировки энергосетей с распределёнными источниками — объемы данных растут экспоненциально. Традиционные процессоры (CPU) часто не справляются с необходимостью оценивать всё большие модели в рамках практического временного окна планирования. Здесь на сцену выходит GPU-ускоренное принятие решений, и NVIDIA cuOpt становится одним из лидеров в этой области. Но что происходит, когда даже один мощный GPU достигает предела своей памяти или вычислительной мощности? Ответ лежит в области распределенных вычислений на нескольких GPU, соединенных высокоскоростными шинами.

В этой статье мы подробно разберем новую технологию NVIDIA — mPDLP (Multi-GPU Primal-Dual hybrid gradient for Linear Programming). Это не просто обновление, а фундаментальный сдвиг в подходе к решению задач линейного программирования (LP) с десятками и сотнями миллионов переменных. Мы рассмотрим архитектуру алгоритма, преимущества минимизации коммуникаций между GPU, реальные кейсы от партнеров NVIDIA и практические результаты бенчмарков, которые показывают ускорение до 11.4 раз на ключевых этапах вычислений.

01Почему масштабирование критически важно?

Задачи оптимизации, такие как линейное программирование (LP), лежат в основе многих промышленных процессов. Классическая задача LP формулируется как поиск вектора $x$, который минимизирует целевую функцию $c^\top x$ при соблюдении ограничений $Ax = b$ и границ переменных $l \leq x \leq u$. Чем больше переменных и ограничений, тем сложнее задача. В прошлом такие задачи решались часами, что делало их непригодными для оперативного планирования.

Одним из известных бенчмарков в этой области является задача zib03, представленная Торстеном Кохом в 2008 году. Она содержит более 104 миллионов ненулевых элементов. На протяжении многих лет эта задача служила эталоном для тестирования новых алгоритмов. Как видно из исторических данных, прогресс в алгоритмах и аппаратном обеспечении позволил значительно сократить время решения. Однако, когда количество переменных приближается к сотням миллионов, а количество ненулевых элементов превышает 10^7, даже самые оптимизированные однопроцессорные решения упираются в «потолок» памяти одного GPU или времени вычислений.

Именно здесь вступает в игру NVIDIA cuOpt. Технология позволяет не просто ускорить вычисления на одном устройстве, но и распределить огромную задачу между несколькими GPU, соединенными через NVLink. Это открывает путь к решению задач с числом ненулевых элементов до 2.1 миллиарда, что ранее было невозможно в рамках одного узла.

02Как работает алгоритм PDLP?

Чтобы понять инновационность mPDLP, нужно разобраться в базовом алгоритме PDLP (Primal-Dual hybrid gradient). Это метод первого порядка, основанный на градиентном спуске, который идеально подходит для параллельных вычислений на GPU благодаря своей структуре.

Алгоритм итеративно обновляет два вектора:

• Прямое решение ($x$): Искомые переменные задачи.
• Двойное решение ($y$): Вектор двойственных переменных, связанных с ограничениями.

Ключевым «горячим циклом» (hot loop) алгоритма является операция умножения разреженной матрицы на вектор (Sparse Matrix-Vector Multiplication, SpMV). Именно эта операция потребляет больше всего ресурсов, так как она ограничена пропускной способностью памяти (memory-bound). Остальные операции — проекции на границы переменных и базовая арифметика — легко распределяются между потоками GPU.

Упрощенно, итерация алгоритма выглядит так:

x^{k+1} = A^\top y^k
y^{k+1} = A x^{k+1}

Здесь $A$ — это матрица ограничений, а $A^\top$ — её транспонированная версия. Основная сложность при распределении этого алгоритма на несколько GPU заключается именно в SpMV, так как она требует обмена данными между устройствами. Если мы просто разделим задачу, нам придется постоянно синхронизировать данные, что может нивелировать выигрыш от параллелизма.

03Проблемы распределения: D-PDLP и его ограничения

До появления mPDLP существовал подход D-PDLP (Distributed PDLP). Он использовал 2D-разбиение матрицы. Матрица $A$ переупорядочивалась для лучшего балансировки нагрузки, а затем разрезалась на подблоки, которые распределялись по разным GPU. Для вычисления результата SpMV каждый GPU выполнял умножение своего подблока, а затем результаты суммировались с помощью коммуникационных операций.

Хотя этот метод показал потенциал многопроцессорного ускорения, у него есть существенный недостаток. D-PDLP рассматривает каждое умножение матрицы на вектор независимо. Он не учитывает, что результаты одного шага (вектор $x$) становятся входными данными для следующего шага (вычисление $y$). Это приводит к избыточным коммуникациям, так как данные передаются между GPU чаще, чем это необходимо.

Кроме того, при 2D-разбиении нагрузка может распределяться неравномерно, если структура матрицы не симметрична. Это создает «узкие места», где некоторые GPU простаивают в ожидании данных от других. NVIDIA решила эту проблему, разработав новый подход к разбиению графа зависимостей.

04Инновация mPDLP: Min-cut partitioning

mPDLP использует принципиально иной подход к распределению данных — минимизацию разреза графа (min-cut partitioning). Вместо того чтобы просто делить матрицу на прямоугольные блоки, mPDLP рассматривает задачу как двудольный граф зависимостей.

Представьте себе матрицу $A$ как граф, где узлы — это переменные $x$ и $y$, а ребра — это ненулевые элементы, связывающие их. Задача mPDLP — разделить этот граф на $k$ частей (для $k$ GPU) так, чтобы количество ребер, пересекающих границы между частями (edge cuts), было минимальным.

Почему это важно? Если два связанных узла (например, $x_1$ и $y_1$) находятся на одном GPU, то вычисление не требует передачи данных по сети. Передача данных нужна только тогда, когда узлы, связанные ненулевым элементом, оказываются на разных GPU. Таким образом, минимизация разреза графа напрямую снижает объем коммуникаций между GPU.

Процесс выглядит следующим образом:

1. Матрица ограничений $A$ преобразуется в двудольный граф зависимостей.
2. Граф разбивается на $k$ частей (где $k$ — количество GPU) с целью минимизации количества ребер, соединяющих разные части.
3. Каждому GPU назначается подмножество строк и столбцов, соответствующих узлам в его части графа.
4. Во время итераций PDLP большая часть вычислений происходит локально на GPU. Обмен данными происходит только для тех элементов, которые были «разрезаны» при разбиении графа.

Это позволяет достичь высокой локальности данных. Например, если GPU 1 отвечает за вычисление $y_1$, и ему нужны данные из $x_1$ и $x_2$, которые также хранятся на GPU 1, то обмен данными не требуется. Если же нужен $x_3$, который находится на GPU 2, то передается только этот один вектор, а не вся матрица.

05Аппаратная и программная инфраструктура

Успех mPDLP невозможен без мощной аппаратной и программной базы NVIDIA. Ключевыми компонентами являются:

• NVLink и NVSwitch: Аппаратные технологии, обеспечивающие высокоскоростное соединение между GPU. NVLink позволяет GPU обмениваться данными с пропускной способностью, значительно превышающей возможности PCIe. NVSwitch масштабирует это соединение для систем с множеством GPU (например, DGX B200), создавая единое пространство памяти с низкой задержкой.
• NCCL (NVIDIA Collective Communications Library): Программная библиотека, которая предоставляет эффективные примитивы для коллективных операций (AllReduce, AllGather, Broadcast) между GPU. NCCL оптимизирована для использования NVLink и NVSwitch, что позволяет максимизировать пропускную способность канала.

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

06Результаты бенчмарков: от теории к цифрам

Для оценки эффективности mPDLP были проведены обширные тесты на более чем 100 экземплярах задач линейного программирования. Тестирование проводилось на узлах NVIDIA DGX B200, где GPU соединены через топологию NVLink «все-со-всеми» (all-to-all). Результаты сравнивались с однопроцессорным cuOpt PDLP и многопроцессорным D-PDLP.

Сравнение с однопроцессорным решением

Как показано на графиках, ускорение mPDLP сильно коррелирует с размером задачи. При количестве ненулевых элементов (nnz) менее 10^7 ускорение незначительно или отсутствует из-за накладных расходов на синхронизацию. Однако, как только nnz превышает 10^7, mPDLP начинает показывать заметное преимущество.

Для самых крупных задач ускорение на этапе PDLP (без учета предварительной обработки и постобработки) достигает 11.4 раз (на задаче tsp-gaia-10m). Это означает, то, что задача, которая занимала бы часы на одном GPU, решается за минуты на нескольких GPU.

Сравнение с D-PDLP

При сравнении с предыдущим многопроцессорным решением D-PDLP, mPDLP демонстрирует ускорение в диапазоне 1.2x – 2.5x на большинстве крупных задач. Это существенный прогресс, который объясняется более эффективным управлением коммуникациями благодаря min-cut partitioning.

Интересно отметить, что на трех ультра-крупных задачах mPDLP показал несколько меньшую скорость, чем D-PDLP. Авторы исследования отмечают, что эти задачи взяты из академических бенчмарков и могут иметь специфическую структуру разреженности, которая не типична для реальных промышленных задач. Для большинства реальных сценариев, на которые оптимизирован cuOpt, mPDLP работает стабильно быстрее.

07Реальные кейсы: Kinaxis и PSR

Теория подтверждается практикой. Партнеры NVIDIA уже внедрили mPDLP в свои решения, демонстрируя впечатляющие результаты.

Kinaxis: Цепочки поставок

Kinaxis, лидер в области управления цепочками поставок, использовала cuOpt mPDLP на своей платформе Maestro. Они решили модель линейного программирования для глобального планирования производства и поставок (CPG) с более чем 135 миллионами переменных. Используя восемь GPU NVIDIA H100, соединенных через NVLink, Kinaxis достигла ускорения в 3.3 раза по сравнению с предыдущими решениями. Это позволяет компаниям быстрее реагировать на изменения спроса и оптимизировать логистику в реальном времени.

PSR: Энергетические системы

Компания PSR применила mPDLP для моделирования расширения энергетических систем. Их модель стохастического расширения мощности содержала 185 миллионов переменных. Используя восемь GPU NVIDIA B200, PSR достигла ускорения более 5 раз. Это критически важно для энергетических компаний, которым необходимо оценивать множество сценариев развития энергосетей с учетом распределенных источников энергии (солнечных панелей, ветряков) и колебаний спроса.

08Что это значит на практике

Внедрение mPDLP в NVIDIA cuOpt открывает новые горизонты для отраслей, зависящих от сложной оптимизации. Вот ключевые выводы для разработчиков и инженеров:

1. Масштабируемость: Теперь задачи с сотнями миллионов переменных и миллиардами ненулевых элементов становятся решаемыми в рамках приемлемого времени. Это позволяет использовать более детальные и точные модели, которые ранее были слишком тяжелыми для вычислений.
2. Экономическая эффективность: Использование нескольких GPU, соединенных NVLink, часто более эффективно, чем покупка одного экстремально дорогого GPU с огромным объемом памяти. Вы можете масштабировать вычислительную мощность, добавляя стандартные GPU в кластер.
3. Гибкость: Алгоритм mPDLP интегрируется в существующие экосистемы оптимизации. Разработчики могут использовать API cuOpt для настройки параметров, таких как количество GPU, допустимая погрешность и время выполнения.

Для тех, кто хочет начать работу с mPDLP, NVIDIA предлагает обучающие материалы и открытый исходный код на GitHub. Вы можете установить cuOpt, настроить решатель и самостоятельно сравнить время решения задач на одном и нескольких GPU. Это отличный способ оценить потенциал технологии для ваших конкретных задач.

В заключение, mPDLP — это не просто еще одна оптимизация, а качественный скачок в области GPU-ускоренной оптимизации. Он демонстрирует, как правильный алгоритмический подход (min-cut partitioning) в сочетании с мощной аппаратной инфраструктурой (NVLink, B200) может преодолеть ограничения масштабируемости и решить задачи, которые ранее считались нерешаемыми в реальном времени.

Источник: NVIDIA Developer ↗