08/10/2026 · VietTechies · Biên tập
NVIDIA vừa công bố chi tiết về bộ giải mPDLP (Primal-Dual hybrid gradient đa GPU) trong giải pháp NVIDIA cuOpt. Bộ giải này được thiết kế nhằm mở rộng quy mô xử lý các bài toán tối ưu hóa quy hoạch tuyến tính (LP) trên nhiều GPU kết nối thông qua NVLink. Giải pháp thực hiện phân bổ các phép nhân ma trận thưa với vectơ (SpMV) bằng thuật toán phân chia đồ thị cắt tối thiểu (min-cut graph partitioning), cho phép giải quyết các mô hình toán học chứa hơn 100 triệu biến trong khoảng thời gian quy hoạch thực tế.
Phân chia đồ thị theo thuật toán cắt tối thiểu
Bộ giải mPDLP giải quyết rào cản về giới hạn bộ nhớ và thời gian hội tụ trong các bài toán tối ưu hóa quy mô lớn bằng cách phân chia khối lượng tính toán trên các GPU nối kết NVLink. Phương pháp Primal-Dual hybrid gradient bậc một phụ thuộc vào việc lặp lại các phép tính SpMV giữa ma trận ràng buộc tuyến tính và ma trận chuyển vị của nó. Để phân bổ các bước này mà không gây nghẽn cổ chai giao tiếp, cuOpt chuyển đổi ma trận ràng buộc thành một đồ thị hai phía (bipartite graph) và áp dụng thuật toán phân chia cắt tối thiểu.
Phương pháp phân chia này đảm bảo các biến và ràng buộc có liên kết chặt chẽ được giữ trên cùng một GPU vật lý. Nhờ đó, tính toán được thực hiện cục bộ tối đa, trong khi các đợt truyền dữ liệu giữa các thiết bị qua NVLink, NVSwitch và thư viện NCCL chỉ giới hạn ở các cạnh nối xuyên qua ranh giới phân chia.
Mức tăng tốc theo bài đo hiệu năng và tiết kiệm bộ nhớ
Việc phân chia ma trận ràng buộc giúp giảm tới 6 lần mức tiêu thụ bộ nhớ đỉnh trên mỗi GPU đối với các bài toán quy hoạch tuyến tính giới hạn ở mức 2,1 tỷ phần tử khác không (nonzeros) so với cấu hình đơn GPU. Đánh giá trên hơn 100 bộ dữ liệu bài đo hiệu năng cho thấy khả năng mở rộng hiệu năng tỷ lệ thuận với độ dày ma trận, mang lại tốc độ tăng đáng kể khi bài toán vượt ngưỡng 10 triệu phần tử khác không.
Trong các bước thực thi lặp riêng lẻ, mPDLP đạt mức tăng tốc lên tới 11,4 lần trên bài đo hiệu năng tsp-gaia-10m, tương ứng với mức giảm 4,2 lần tổng thời gian chạy thực tế. Khi so sánh với các bộ giải đa GPU phân chia 2D như D-PDLP, mPDLP đạt tốc độ cao hơn từ 1,2 đến 2,5 lần trên phần lớn các thể hiện bài toán quy mô lớn được kiểm thử.
Thử nghiệm thực tế và giới hạn khối lượng công việc
Trong ứng dụng doanh nghiệp, nhà cung cấp phần mềm chuỗi cung ứng Kinaxis ghi nhận mức tăng tốc 3,3 lần trên mô hình quy hoạch sản xuất chứa hơn 135 triệu biến khi vận hành trên hệ thống 8 GPU NVIDIA H100. Công ty mô hình hóa năng lượng PSR cũng đạt mức tăng tốc hơn 5 lần đối với mô hình mở rộng năng lực hệ thống năng lượng gồm 185 triệu biến sử dụng 8 GPU NVIDIA B200.
Mặc dù vậy, NVIDIA cũng đưa ra những ngưỡng giới hạn hiệu năng cụ thể. Các bài toán quy hoạch tuyến tính kích thước nhỏ sẽ chịu chi phí đồng bộ hóa giữa các GPU lớn hơn lợi ích thu được từ việc tính toán song song. Ngoài ra, các bài toán tối ưu hóa có cấu trúc thưa dẫn đến tỷ lệ cạnh bị cắt cao sau khi phân chia sẽ kích hoạt lưu lượng giao tiếp liên thiết bị lớn, làm giảm hoặc đảo ngược hiệu quả tăng tốc của cấu hình đa GPU.
Ảnh minh họa do AI tạo, không phải ảnh tư liệu.
Nguồn: Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt