High performance scalable Ising optimization with GraphBLAS

Abstract

We present a fast and scalable implementation of two general optimization algorithms: Simulated Annealing-Replica Exchange (SARE) and Simulated Bifurcation (SB). We particularly focus on the large-scale sparse Ising and Quadratic Unconstrained Binary Optimization (QUBO) problems, which are common formulations for many combinatorial optimization problems. The implementation of both algorithms is expressed as matrix and vector primitives using GraphBLAS. This enables nonblocking and multithreaded operations through the use of different backends. The SARE algorithm is also naturally expressed in an SPMD (Single Program Multiple Data) paradigm, so our implementation is expressed in this way. The multiprocess algorithm can run in a hybrid fashion by simply selecting a multithreaded backend.A big advantage of our approach is portability: it runs without change on different architectures. We compare our implementations with state-of-the-art general solvers from MQLib and dwave on Max-Cut graphs G22 and G81 from the Gset collection. In single-threaded operation, we observe runtime comparable to (SARE) or better than (SB) the reference, while achieving similar solution quality. Both algorithms show good performance and scalability across different architectures: we tested on both ARM and x86 nodes with similar results.We show that the SARE implementation scales well with consistent speedup using many concurrent processes and across multiple nodes.Also the hybrid approach achieves a measurable speedup compared to the single-threaded operation. Also SB shows almost linear speedup using the multithreaded backends, though its scalability is highly dependent on the size of the problem. In both cases the nonblocking backend achieves limited speedup.