A Work-Time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation
A Work-Time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation
复制标题
QUBO 和 Ising 模型的工作时间最优并行穷举搜索算法（带 GPU 实现）
DOI：
10.1109/ipdpsw50202.2020.00098
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yoko Inaba
中科院分区：
文献类型：
--
作者：
Masaki Tao;K. Nakano;Yasuaki Ito;Ryota Yasudo;Masaru Tatekawa;Ryota Katsuki;Takashi Yazane;Yoko Inaba
本文的主要贡献是针对二次无约束二元优化（QUBO）问题提出了一种简单的穷举搜索算法。它在 $O(2^{n})$ 时间内计算所有 n 位输入向量 X 的目标函数 $E(X)$ 的值。由于为所有 2n 个向量 X 输出 $E(X)$ 需要 $\Omega(2^{n})$ 时间，因此该顺序算法是最佳的。我们还提出了一种工作时间最优并行算法，使用 CREW-PRAM 上的 $2^{n}/\log n$ 处理器运行 $O(\log n)$ 时间。这种并行算法是工作最优的，因为计算操作的总数等于最优顺序算法的运行时间。此外，它是时间最优的，因为任何使用大量处理器的并行算法至少需要 $\Omega(\log n)$ 时间来评估 E(X)。此外，我们还实现了在 GPU 上运行的并行算法。在 NVIDIA GeForce RTX 2080Ti GPU 上的实验结果表明，每当 n$\geq$33 时，对于具有 n 位向量的 QUBO，我们的 GPU 实现比在 Intel Corei7-8700K CPU（3.70GHz）上运行的顺序算法快 1000 倍以上。我们还将穷举搜索并行算法与解决 QUBO 的几种非穷举搜索方法进行了比较，包括 D-Wave 2000Q 量子退火器、模拟退火算法和 Gurobi 优化器。
The main contribution of this paper is to present a simple exhaustive search algorithm for the quadratic un-constraint binary optimization (QUBO) problem. It computes the values of the objective function $E(X)$ for all n-bit input vector X in $O(2^{n})$ time. Since $\Omega(2^{n})$ time is necessary to output $E(X)$ for all 2n vectors X, this sequential algorithm is optimal. We also present a work-time optimal parallel algorithm running $O(\log n)$ time using $2^{n}/\log n$ processors on the CREW-PRAM. This parallel algorithm is work optimal, because the total number of computational operations is equal to the running time of the optimal sequential algorithm. Also, it is time optimal because any parallel algorithm using any large number of processors takes at least $\Omega(\log n)$ time for evaluating E(X). Further, we have implemented this parallel algorithm to run on the GPU. The experimental results on NVIDIA GeForce RTX 2080Ti GPU show that our GPU implementation runs more than 1000 times faster than the sequential algorithm running on Intel Corei7-8700K CPU(3.70GHz) for the QUBO with n-bit vector whenever n$\geq$33. We also compare our exhaustive search parallel algorithm with several non-exhaustive search approaches for solving the QUBO including D-Wave 2000Q quantum annealer, simulated annealing algorithm, and Gurobi optimizer.