Bộ xử lý đồ họa (GPU) đã đạt được những thành công vượt bậc trong việc tăng tốc các tác vụ học máy, đặc biệt là trong huấn luyện và suy luận. Tuy nhiên, những cải thiện hiệu năng tương tự vẫn chưa được hiện thực hóa đầy đủ trong lĩnh vực tối ưu tổ hợp tổng quát và chính xác. Các nghiên cứu hiện tại về tối ưu tổ hợp trên GPU chủ yếu tập trung vào các thuật toán metaheuristic hoặc các bộ giải chính xác nhưng chỉ áp dụng cho những lớp bài toán đặc thù. Một bước tiến đáng chú ý gần đây xuất hiện trong lập trình tuyến tính, khi các thuật toán như phương pháp gradient lai nguyên–đối ngẫu cho phép khai thác hiệu quả GPU thông qua các phép toán ma trận, và đã được ứng dụng thành công cho bài toán lập trình tuyến tính nguyên hỗn hợp.
Ngược lại, lập trình ràng buộc (constraint programming – CP), một phương pháp tổng quát và chính xác hỗ trợ các ràng buộc phi tuyến thông qua cơ chế lan truyền ràng buộc và tìm kiếm quay lui, vẫn còn gặp nhiều hạn chế khi triển khai trên kiến trúc GPU. Các nỗ lực trước đây hoặc giới hạn ngôn ngữ ràng buộc, hoặc chỉ tăng tốc một phần quá trình tính toán trên GPU, hoặc chỉ xử lý một số loại ràng buộc cụ thể. Do đó, vẫn chưa có một bộ giải CP tổng quát nào được triển khai hoàn toàn trên GPU.
Dựa trên những tiến bộ gần đây trong lập trình ràng buộc đồng thời, bài báo này giới thiệu Turbo, một bộ giải lập trình ràng buộc rời rạc tổng quát và chính xác, được thiết kế tối ưu cho GPU. Turbo triển khai toàn bộ quá trình lan truyền ràng buộc và tìm kiếm quay lui trực tiếp trên GPU, sử dụng lan truyền biên khoảng số nguyên và phân rã mạng ràng buộc thành các mạng ràng buộc bậc ba (ternary constraint networks – TCN). Cách biểu diễn này cho phép thực hiện lan truyền song song hiệu quả theo mô hình parallel CCP, đồng thời cải thiện khả năng truy cập bộ nhớ và hiệu suất tính toán trên GPU.
Do các hạn chế phần cứng, Turbo sử dụng kiến trúc đơn giản hơn so với các bộ giải CP tối ưu trên CPU và không bao gồm các kỹ thuật nâng cao như ràng buộc toàn cục, học nogood, chiến lược khởi động lại hay đảm bảo tính nhất quán miền. Mặc dù vậy, Turbo vẫn đạt được hiệu năng cạnh tranh. Kết quả thực nghiệm trên bộ bài toán MiniZinc Challenge 2024 cho thấy Turbo có thể đạt kết quả tương đương hoặc vượt trội so với các bộ giải tuần tự hiện đại trên một tỷ lệ đáng kể các bài toán. Đánh giá thực nghiệm chi tiết được trình bày nhằm phân tích hiệu quả và khả năng mở rộng của phương pháp đề xuất.
TY - BOOKAU - Talbot, PierrePY - 2026/01/22SP - T1 - A GPU-based Constraint Programming SolverVL - ER -
Toàn bộ bài nghiên cứu:
https://www.researchgate.net/publication/399606771_A_GPU-based_Constraint_Programming_Solver
