TLDR: This paper introduces GPU-accelerated versions of the Compact-Table (CT) algorithm for solving large table constraints in Constraint Programming. By offloading computationally intensive update and filtering procedures to GPUs, the researchers achieved significant speedups (up to 4.35x) compared to CPU-only methods and state-of-the-art solvers like Gecode. This advancement enables more efficient handling of complex combinatorial problems, despite data transfer overheads.
Constraint Programming (CP) is a powerful approach to solving complex problems by defining conditions, known as constraints, that variables must satisfy. Among these, the “table constraint” plays a crucial role. It explicitly lists all the permissible combinations of values for a set of variables, acting like a comprehensive lookup table for valid solutions. This flexibility makes table constraints widely applicable in various fields, including scheduling and configuration problems.
However, a significant challenge arises when these table constraints become very large, potentially containing hundreds or thousands of valid cases. Traditional CPU-based methods often struggle to process such extensive tables efficiently, leading to considerable slowdowns in problem-solving.
A recent research paper, titled “GPU Accelerated Compact-Table Propagation,” addresses this challenge by proposing a novel solution: leveraging the massive computational power of modern Graphics Processing Units (GPUs). GPUs are designed for parallel processing, allowing them to execute numerous calculations simultaneously, which is highly beneficial for tasks involving large-scale data manipulation.
The paper focuses on the Compact-Table (CT) algorithm, which is considered a state-of-the-art method for enforcing generalized arc consistency (GAC) on table constraints. GAC is a technique that prunes the possible values for variables, ensuring that only values that can lead to a valid solution remain. The researchers describe how the CT algorithm can be significantly enhanced by offloading its computationally intensive parts to the GPU.
They developed three variants of GPU-accelerated propagators, integrating them into MINI CP, a lightweight and extensible constraint solver. These variants included: one where only the table update procedure was GPU-accelerated (CTuCU), another where only the domain filtering procedure was accelerated (CTfCU), and a third where both procedures were accelerated (CTufCU).
Extensive experimental validation was performed on a significant set of instances, including synthetic benchmarks based on the bounded knapsack problem and real-world instances of the Orienteering problem. The results demonstrated that the CTufCU implementation consistently outperformed its serial (CPU-only) counterpart. For sufficiently large instances, CTufCU achieved impressive speedups, averaging between 2.88x and 4.35x compared to CTfCU on different test sets. The GPU-accelerated approach also showed significant performance gains when compared against Gecode, another leading constraint solver.
Also Read:
- Optimizing Answer Set Programming with Automated Hybrid Grounding
- Advancing Constraint Logic Programming: A Unified Approach to Negation with Semirings
While the experiments showed that the GPU capabilities were not always fully saturated (averaging around 45% utilization on an NVIDIA GeForce RTX 4090), the observed speedups were substantial. This suggests that even GPUs with fewer processing units could still provide significant benefits. The primary bottleneck identified was the time required for data transfers between the host (CPU) and the device (GPU), highlighting an area for future optimization. This research marks a significant step towards more exhaustive parallel implementations in constraint logic programming, enabling the efficient solution of larger and more complex combinatorial problems.
