Оптимизация и матпрограммирование на GPU
Задача страницы. Дать инженерный каркас для задач оптимизации на облачных GPU: от выпуклых LP/QP/SOCP/SDP и крупных регрессий до комбинаторных MILP/VRP и эвристик. Разберём, где GPU даёт максимальный выигрыш (батчи и линал), как строить одно‑ и многоузловые пайплайны (ADMM/Primal‑Dual), какие метрики наблюдать, как считать экономику Cost_per_solve/Cost_per_1K_routes, и как безопасно эксплуатировать Interruptible режим.
TL;DR
- **Классы задач. Выпуклые: LP/QP/SOCP/SDP, крупные L1/L2‑регрессии, логистическая регрессия. Комбинаторные: MILP/VRP/RCPSP и др. (GPU полезен для батч‑релаксаций, эвристик и параллельных сценариев).
- **Где GPU выгоден.
- Большая линейная алгебра (cuBLAS/cuSPARSE/QR/SVD) — ядро IPM/PDHG/ADMM. См. https://cloudcompute.ru/solutions/hpc/linear-algebra/
- Батчи: сотни/тысячи независимых QP/LP (MPC/портфели/сценарии).
- Эвристики/локальный поиск — тысячи кандидатов/мутаций в параллели.
- **Алгоритмическая ориентация. — Первые порядки (PGD/FISTA/PDHG) — простые ядра + слабо зависят от сети. — ADMM/consensus — хорошо ложится на многоузловый all‑reduce. — Interior‑Point — «тяжёлая» линал (KKT) → выигрывает от много‑GPU.
- Архитектуры. Single‑node GPU‑resident; ADMM multi‑node с NCCL/UCX; пул воркеров для MILP/VRP (Interruptible). См. https://cloudcompute.ru/solutions/multi-gpu/
- Данные/I‑O. Входы/матрицы/сценарии — «тёплое», рабочее — NVMe‑scratch, публикация — «холодное». См. https://cloudcompute.ru/solutions/storage-data/
- Режимы. SLA‑критичное — On‑Demand; массовые свипы/эвристики — Interruptible с чанком ≤ 120 с и идемпотентностью. См. https://cloudcompute.ru/solutions/interruptible-patterns/
- Профили GPU. 24 ГБ (Compact) — батчи малых QP/эвристики; 48 ГБ (Balanced) — основной профиль; 80 ГБ (HQ) — KKT/SDP/многоузловые solve’ы; для плотности — MIG. См. https://cloudcompute.ru/solutions/mig/
- Метрики. iter_per_s, obj_value, primal_residual, dual_residual, kkt_violation, mip_gap, nodes_per_s, gpu_utilization, p50/p95 iter_time. См. https://cloudcompute.ru/solutions/monitoring-logging/
- Экономика. Cost_per_solve = (c_gpu * t_solve / 3600) / U * r + Storage_cost; для VRP — Cost_per_1K_routes. См. https://cloudcompute.ru/solutions/cost-planner/
Сценарии (когда это нужно)
- Финансы. QP/LP портфельные (минимизация дисперсии, риск‑паритет, трекинг‑эррор), стресс‑сценарии (батчи), XVA со вложенными оптимизациями. Связанные симуляции — см. https://cloudcompute.ru/solutions/hpc/monte-carlo/
- Операции/логистика. VRP/TSP/LNS, раскрой/пэккинг, планирование смен, MIP‑релаксации + эвристики на GPU.
- Энергетика/OPF. DC/AC‑приближения как QP/SOCP; много сценариев сетевых состояний.
- Управление/MPC. Тысячи малых QP онлайн/офлайн; идеальны для strided‑batched GEMM на GPU.
- ML‑оптимизация. LASSO/логистическая с L1/L2 на огромных фич‑матрицах; выпуклый ERM.
- Граф‑оптимизация. Min‑cost flow/assignment как Sp*‑ядра; смежная аналитика — https://cloudcompute.ru/solutions/hpc/graph-analytics/
Архитектуры/пайплайны A) Single‑node, выпуклая оптимизация (GPU‑resident)
[Warm: matrices (CSR/CSC/NPY)] -> [Prefetch -> NVMe] -> [cuBLAS/cuSPARSE ops] -> [PDHG/ADMM updates on GPU]
|
[Checkpoints (x, y, r_pr, r_du) -> warm/cold]
Ключи: вся линал на GPU, пул памяти RMM, проекции/soft‑threshold на GPU, чекпоинт каждые 60–120 с.
B) ADMM consensus, многоузловой (all‑reduce)
[Warm data shards] -> [NVMe per node]
|
+--------+-----------------------------+
| Node #1: GPUxN .... Node #M: GPUxN
| x_i update (local) -> all-reduce(z, u) <- x_j update (local)
+-------------------------------------------+
NCCL/UCX (RDMA) fabric
Ключи: 1 процесс = 1 GPU; локальные SpMV/GEMM; согласование z,u через NCCL all‑reduce; RDMA снижает RTT.
C) MILP/VRP — пул воркеров (Interruptible)
[Scenario pool] -> [Scheduler] -> [GPU Workers: heuristics/batched relaxations (≤120 s)] -> [Reducer -> incumbent/best]
Ключи: задачи идемпотентны; чанк ≤ 120 с; запись лучшего инкамбента при каждом улучшении; MIG для плотности.
Профили GPU/VRAM/ориентиры
| **Профиль** | **VRAM** | **Типовые кейсы** | **Режим** | **Отн. throughput (≈)** | **Примечания** |
| **24 ГБ (Compact)** | 24 ГБ | Батчи малых QP/MPC, эвристики VRP | Оба | 1.0 | Хорош для множества независимых solve’ов |
| **48 ГБ (Balanced)** | 48 ГБ | Крупные ERM/SpMV, IPM средних задач | Оба | 1.5–1.8 | База для продакшена |
| **80 ГБ (HQ)** | 80 ГБ | SDP/KKT крупные, ADMM multi‑node | Оба | 2.2–2.6 | Запас под KKT, много полей/параметров |
Отн. индексы зависят от форматов матриц и числа итераций.
Конфиги и скелеты
1) QP в стандартной форме и PDHG‑шаги (CuPy)
# min 0.5 x^T Q x + q^T x, s.t. Ax <= b, Ex = f
# PDHG (упрощённо): y^(k+1) = proj_{<=b,f}( y^k + σ K x^k ), x^(k+1) = prox_{τ g}( x^k - τ K^T y^(k+1) )
import cupy as cp
Q, A, E = ... # csr_matrix/cupy arrays на GPU
q, b, f = ... # вектора на GPU
tau, sigma = 1e-2, 1e-2
x = cp.zeros(Q.shape[0], cp.float32)
y_ineq = cp.zeros(A.shape[0], cp.float32)
y_eq = cp.zeros(E.shape[0], cp.float32)
def prox_g(z): # для квадратичного члена: (I + τQ)^{-1}(z - τq)
# решаем систему (I + τQ) x = z - τq (cg/pcg на cuSPARSE, либо факторы заранее)
return z # вставьте решатель
def proj_ineq(v): return cp.minimum(v, b) # проекция на полупространство (двойственная)
def proj_eq(v): return v + (f - v) # заглушка: обеспечьте равенство корректным оператором
for k in range(1000):
y_ineq = proj_ineq(y_ineq + sigma * (A @ x))
y_eq = proj_eq (y_eq + sigma * (E @ x))
grad = (A.T @ y_ineq) + (E.T @ y_eq)
x = prox_g(x - tau * grad)
# лог/метрики: obj, ||Ax-b||_+, ||Ex-f||
Реализуйте prox_g через решатель на GPU (см. https://cloudcompute.ru/solutions/hpc/linear-algebra/).
2) ADMM для LASSO (GPU, консенсус‑формулировка)
# min_x 0.5||Ax - y||_2^2 + λ||x||_1
# Обновления: x := solve( (A^T A + ρI) x = A^T y + ρ(z-u) ), z := S_{λ/ρ}(x+u), u := u + x - z
A, y = ... # на GPU
rho, lam = 1e-1, 1e-3
AtA = A.T @ A
rhs_const = A.T @ y
x = cp.zeros(A.shape[1], cp.float32); z = x.copy(); u = x.copy()
# Предфакторизация (например, Cholesky) на GPU для (AtA + ρI)
for k in range(200):
rhs = rhs_const + rho*(z - u)
x = solve_posdef(AtA + rho*I, rhs) # вставьте GPU-решатель
z = cp.sign(x+u) * cp.maximum(cp.abs(x+u)-lam/rho, 0) # soft-threshold
u += x - z
3) Эвристика VRP: массовая оценка 2‑opt мутаций (GPU)
import cupy as cp
def two_opt_batch(routes, dist): # routes: (B, L) индексы вершин, dist: (N,N)
B, L = routes.shape
i = cp.random.randint(1, L-2, size=B)
j = i + cp.random.randint(2, L - i, size=B)
# вычислить Δстоимость для обмена [i:j] -> reverse
a = routes[cp.arange(B), i-1]; b = routes[cp.arange(B), i]
c = routes[cp.arange(B), j]; d = routes[cp.arange(B), (j+1) % L]
delta = (dist[a, c] + dist[b, d]) - (dist[a, b] + dist[c, d])
improve = delta < 0
# применить выгодные обмены
for idx in cp.where(improve)[0]:
routes[idx, i[idx]:j[idx]+1] = routes[idx, i[idx]:j[idx]+1][::-1]
return routes, delta.mean()
4) Slurm (ADMM multi‑node, UCX/RDMA)
#!/bin/bash
#SBATCH -J admm_consensus
#SBATCH -N 2
#SBATCH --gpus-per-node=4
#SBATCH -t 04:00:00
#SBATCH -p gpu
#SBATCH --exclusive
module load cuda mpi
export UCX_TLS=rc,ud,sm,self,gdr,cuda_copy,cuda_ipc
export NCCL_SOCKET_IFNAME=eth0 # или ib0
export OMP_NUM_THREADS=1
# Каждый процесс: локальный шаг x_i; затем NCCL all-reduce для усреднения z и u
srun --mpi=pmix_v3 python3 run_admm_consensus.py --rho 0.1 --iters 200 --ckpt /nvme/ckpt
5) YAML задания (универсально)
job:
name: "opt_convex_admm_v1"
mode: "interruptible" # on-demand | interruptible
nodes: 2
gpus_per_node: 4
gpu_profile: "48GB-Balanced"
network: "rdma"
io:
prefetch: ["/warm/matrices/","/warm/scenarios/"]
scratch: "/nvme"
checkpoint: "/nvme/ckpt"
interval_seconds: 120
run:
entrypoint: "python"
args: ["/opt/opt/run.py","--algo","admm","--rho","0.1","--max-iters","200"]
hooks:
on_start: ["python /scripts/prefetch.py"]
on_checkpoint: ["python /scripts/register_ckpt.py"]
on_failure: ["python /scripts/requeue.py --backoff"]
6) SSE‑прогресс (панель метрик)
from fastapi import FastAPI
from fastapi.responses import StreamingResponse
import json, time, random
app = FastAPI()
def stream():
it, obj, gap = 0, 0.0, 1.0
while True:
it += 5; obj -= random.random()*1e-3; gap *= 0.95
payload = {"iter": it, "obj_value": obj, "primal_residual": gap, "gpu_utilization": 0.82}
yield f"data: {json.dumps(payload)}nn"; time.sleep(1)
@app.get("/events")
def events(): return StreamingResponse(stream(), media_type="text/event-stream")
``` **Наблюдаемость/метрики/алерты**
Базовые хабы:[ https://cloudcompute.ru/solutions/monitoring-logging/](https://cloudcompute.ru/solutions/monitoring-logging/?utm_source=chatgpt.com) •[ https://cloudcompute.ru/solutions/llm-inference/observability/](https://cloudcompute.ru/solutions/llm-inference/observability/?utm_source=chatgpt.com)
**Выпуклые (IPM/PDHG/ADMM):**
- Производительность: iter\_per\_s, p50/p95 iter\_time\_seconds.
- Качество: obj\_value, primal\_residual, dual\_residual, kkt\_violation, relative\_gap.
- Память/линал: GBps\_dram, spmv\_time\_ms, gemm\_time\_ms.
**MILP/VRP:**
- mip\_gap, best\_bound, incumbent\_cost, nodes\_explored, nodes\_per\_s.
- Эвристики: candidates\_per\_s, best\_cost\_over\_time.
**GPU/кластер:**
- gpu\_utilization, gpu\_memory\_used\_bytes, sm\_occupancy, rdma\_rx/tx\_mb\_s, mpi\_wait\_ratio, allreduce\_time\_ms.
- I/O: io\_read/write\_mb\_s, nvme\_usage\_bytes.
**Алерты:**
- p95 iter\_time\_seconds ↑ > X% к эталону.
- Застой primal/dual\_residual и нулевая динамика obj\_value N итераций.
- gpu\_memory\_used\_bytes → потолок / nvme\_usage\_bytes > 85%.
- mpi\_wait\_ratio высокий при низком gpu\_utilization — сеть/распиновка.
## **Экономика и формулы**
См.[ https://cloudcompute.ru/solutions/cost-planner/](https://cloudcompute.ru/solutions/cost-planner/?utm_source=chatgpt.com) и <https://cloudcompute.ru/solutions/throughput-vs-latency/>
**Стоимость solve’а:**
Cost\_per\_solve = ((c\_gpu \* N\_gpu \* t\_solve\_hours) / U) \* r + Storage\_cost
t\_solve\_hours ≈ (N\_iter / iter\_per\_s) / 3600
**Батчи (K независимых QP):**
Solves\_per\_hour ≈ N\_gpu \* iter\_per\_s / (N\_iter\_per\_solve)
Cost\_per\_1K\_solves = (c\_gpu \* 1000 / Solves\_per\_hour)
**VRP/эвристики:**
Cost\_per\_1K\_routes = (c\_gpu \* t\_1K\_routes / 3600) / U \* r
**Масштабирование ADMM:**
Speedup(N) = T1 / TN
Scale\_eff(N) = Speedup(N) / N
Выбирайте N, где Scale\_eff и Cost\_per\_solve оптимальны при допустимых allreduce\_time\_ms.
**Точность/форматы:**
- Для устойчивости: FP32/FP64; смешанная точность с аккумулированием в FP32 — там, где сходится. См. <https://cloudcompute.ru/solutions/fp8-bf16/> и[ https://cloudcompute.ru/solutions/performance-tuning/](https://cloudcompute.ru/solutions/performance-tuning/?utm_source=chatgpt.com)
## **Практики производительности**
- **Линал на GPU.** Вынесите SpMV/GEMM/QR/SVD в GPU‑ядра; избегайте CPU «горячих» циклов. См. <https://cloudcompute.ru/solutions/hpc/linear-algebra/>
- **Форматы матриц.** CSR/CSC + сортированные индексы (int32, где можно), батчи SpMM для нескольких правых частей.
- **Overlapping.** H2D/D2H перекрывать вычислениями; двойная/тройная буферизация; pinned memory.
- **ADMM/PDHG.** Простые операции → высокая iter\_per\_s; подбирайте шаги/ρ адаптивно.
- **IPM.** Предфакторизация/переиспользование структур KKT; много‑GPU для крупных систем.
- **MILP/VRP.** Разнести branch&bound (CPU) и оценку кандидатов/релаксаций (GPU); пул воркеров, MIG.
- **Interruptible.** Чекпоинты состояния (x,z,u,итерация,лучший инкамбент), интервалы ≤ 120 с, идемпотентность. См. <https://cloudcompute.ru/solutions/interruptible-patterns/>
- **Контейнеры/версии.** Фиксировать CUDA/библиотеки; smoke‑бенчи. См. <https://cloudcompute.ru/solutions/containers-ci-cd/>
## **Безопасность/политики**
См.[ https://cloudcompute.ru/solutions/security/](https://cloudcompute.ru/solutions/security/?utm_source=chatgpt.com)
- **Данные.** Коммерчески чувствительные входы (прайсы, графы поставок, расписания) — изолированные проекты, шифрование «на покое», ограниченный egress.
- **Секреты.** Ключи бакетов/лицензии — только секрет‑хранилище; запрет логирования.
- **Аудит.** Версии контейнеров/параметров, кто запускал, какие результаты публиковал.
- **Ретеншн.** Хранить итоговые решения/инкамбенты; временные состояния solver’ов — автоочистка.
**Траблшутинг (симптом → причина → решение)**
<table><tbody><tr><td>**Симптом**
</td><td>**Причина**
</td><td>**Решение**
</td></tr><tr><td>primal/dual\_residual не падают
</td><td>Неверные шаги/ρ, плохая нормализация
</td><td>Нормировать данные; адаптивные шаги; line‑search; пересмотреть ρ
</td></tr><tr><td>Взрыв kkt\_violation в IPM
</td><td>Плохая обусловленность KKT
</td><td>Регуляризация, масштабирование, предобуславливание, FP64
</td></tr><tr><td>Низкий iter\_per\_s
</td><td>CPU узкие места/I‑O
</td><td>Вынести всё на GPU, NVMe‑prefetch, перекрыть H2D/D2H
</td></tr><tr><td>OOM VRAM на KKT
</td><td>Слишком большая система/формат
</td><td>int32 индексы, блочная структура, 48–80 ГБ профиль, out‑of‑core тайлинг
</td></tr><tr><td>Высокий mpi\_wait\_ratio в ADMM
</td><td>Сеть/пиннинг
</td><td>RDMA/UCX, NUMA‑пиннинг, уменьшить частоту all‑reduce
</td></tr><tr><td>mip\_gap не сжимается
</td><td>Слабые релаксации/ограниченные эвристики
</td><td>Усилить релаксации, добавить LNS/2‑opt батчи на GPU
</td></tr><tr><td>Нестабильная точность в FP16
</td><td>Аккумулирование с потерями
</td><td>Перейти на FP32/FP64 или смешанную с acc=FP32
</td></tr><tr><td>«Пилит» iter\_time
</td><td>Холодный кэш/конкуренция диска
</td><td>NVMe‑scratch, write‑behind, выделенный диск
</td></tr></tbody></table>
## **Как запустить в cloudcompute.ru**
1. **Шаблоны:**[ https://cloudcompute.ru/solutions/templates/](https://cloudcompute.ru/solutions/templates/?utm_source=chatgpt.com)
- «Convex Opt (ADMM/PDHG, cuSPARSE)» — для LP/QP/SOCP/регрессий.
- «VRP/MILP Heuristics (GPU workers)» — пул воркеров/эвристик.
- «HPC MPI (Slurm/K8S)» — многоузловой ADMM/IPM с UCX/RDMA.
2. **Профиль GPU:** 24/48/80 ГБ по таблице; KKT/SDP/ADMM multi‑node — 80 ГБ; батчи QP/эвристики — 24/48 ГБ, **MIG** для плотности.
3. **Режим:** SLA‑критичное — **On‑Demand**; массовые сценарии/эвристики — **Interruptible** (чанк ≤ 120 с, ретраи). См. <https://cloudcompute.ru/solutions/interruptible-patterns/>
4. **Хранилище:** матрицы/сценарии — «тёплое»; рабочие факторы/стейты — **NVMe**; публикация — «холодное». См.[ https://cloudcompute.ru/solutions/storage-data/](https://cloudcompute.ru/solutions/storage-data/?utm_source=chatgpt.com)
5. **Оркестрация/CI:** зафиксированные версии CUDA/библиотек; smoke‑бенчи (малый QP, мини‑ADMM, VRP‑игрушка). См. <https://cloudcompute.ru/solutions/containers-ci-cd/>
6. **Наблюдаемость:** дашборды solver‑метрик + GPU/сеть/I‑O; алерты p95, застой резидуалов, рост mip\_gap. См.[ https://cloudcompute.ru/solutions/monitoring-logging/](https://cloudcompute.ru/solutions/monitoring-logging/?utm_source=chatgpt.com)
7. **Сквозные оптимизации:** смешанная точность/roofline/линал. См.[ https://cloudcompute.ru/solutions/performance-tuning/](https://cloudcompute.ru/solutions/performance-tuning/?utm_source=chatgpt.com) • <https://cloudcompute.ru/solutions/fp8-bf16/> • <https://cloudcompute.ru/solutions/throughput-vs-latency/>
**Чек‑лист перед продом**
- Данные нормированы; форматы матриц (CSR/CSC) и индексы (int32) согласованы.
- Вся линал перенесена на GPU; overlap H2D/compute/D2H включён; NVMe‑scratch активен.
- Для ADMM/IPM: параметры (шаги/ρ/толерансы) калиброваны; checkpoint ≤ 120 с.
- Для MILP/VRP: пул воркеров, эвристики/релаксации на GPU, идемпотентные задачи.
- Метрики и алерты заведены: iter\_per\_s, obj\_value, primal/dual\_residual, mip\_gap, gpu\_utilization, io\_\*.
- Экономика посчитана: Cost\_per\_solve, Cost\_per\_1K\_routes; выбран профиль 24/48/80 ГБ и режим.
- Политики безопасности/ретенции применены; логи без секретов; аудит версий/параметров.
**Навигация**
- Хаб HPC: <https://cloudcompute.ru/solutions/hpc/>
- Родственные разделы:
- Линал (cuBLAS/cuSPARSE): <https://cloudcompute.ru/solutions/hpc/linear-algebra/>
- Граф‑аналитика: <https://cloudcompute.ru/solutions/hpc/graph-analytics/>
- Монте‑Карло: <https://cloudcompute.ru/solutions/hpc/monte-carlo/>
- Сквозные:
- Multi‑GPU/топологии:[ https://cloudcompute.ru/solutions/multi-gpu/](https://cloudcompute.ru/solutions/multi-gpu/?utm_source=chatgpt.com) • MIG: <https://cloudcompute.ru/solutions/mig/>
- Данные/хранилище:[ https://cloudcompute.ru/solutions/storage-data/](https://cloudcompute.ru/solutions/storage-data/?utm_source=chatgpt.com)
- Контейнеры/CI/CD: <https://cloudcompute.ru/solutions/containers-ci-cd/>
- Мониторинг/логи:[ https://cloudcompute.ru/solutions/monitoring-logging/](https://cloudcompute.ru/solutions/monitoring-logging/?utm_source=chatgpt.com)
- Наблюдаемость:[ https://cloudcompute.ru/solutions/llm-inference/observability/](https://cloudcompute.ru/solutions/llm-inference/observability/?utm_source=chatgpt.com)
- Оптимизация вычислений:[ https://cloudcompute.ru/solutions/performance-tuning/](https://cloudcompute.ru/solutions/performance-tuning/?utm_source=chatgpt.com) • <https://cloudcompute.ru/solutions/fp8-bf16/> • <https://cloudcompute.ru/solutions/throughput-vs-latency/>
- Interruptible‑паттерны: <https://cloudcompute.ru/solutions/interruptible-patterns/>
Готовы запустить?
Запустить GPU-сервер