ABS2: A GPU QUBO Solver

Outline of ABS2

• ABS2 is a QUBO solver that utilizes GPUs for local search operations and multicore CPUs for GA-based (Genetic Algorithm-based) operations.

• The host CPU maintains a solution pool consisting of multiple solutions, typically around 100.

• To generate a target solution, ABS2 employs genetic operations, such as mutation and crossover, on the solutions within the solution pool.

• The GPU threads then execute batch searches using the target solution, which involve multiple greedy and local search operations.

• If the Host CPU is equipped with multiple GPUs, multiple solution pools are organized within it. Each GPU is assigned to a specific solution pool and is responsible for conducting batch searches for that pool.

• This distributed arrangement allows for parallel processing and increases the overall computational efficiency of ABS2. By utilizing multiple GPUs simultaneously, ABS2 can perform batch searches on multiple solution pools in parallel, significantly reducing the time required to find optimal or near-optimal solutions to QUBO problem instances.

• This multi-GPU setup enhances the scalability and performance of ABS2, enabling it to achieve faster solution times. The combination of GPU-based local search operations and GA-based operations on multicore CPUs makes ABS2 a powerful and versatile QUBO solver.

• ABS2 is OpenMP-free.