Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. As many NP-hard problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. This paper presents a framework called Diverse Adaptive Bulk Search (DABS), which has the potential to find optimal solutions of many types of QUBO problems. Our DABS solver employs a genetic algorithm-based search algorithm featuring three diverse strategies: multiple search algorithms, multiple genetic operations, and multiple solution pools. During the execution of the solver, search algorithms and genetic operations that succeeded in finding good solutions are automatically selected to obtain better solutions. Moreover, search algorithms traverse between different solution pools to find good solutions. We have implemented our DABS solver to run on multiple GPUs. Experimental evaluations using eight NVIDIA A100 GPUs confirm that our DABS solver succeeds in finding optimal or potentially optimal solutions for three types of QUBO problems.
19 August 2021 in Concurrency and Computation: Practice and Experience
Recent graphics processing units (GPUs), which have many processing units, can be used for general purpose parallel computation. To utilise the powerful computing ability, GPUs are widely used for general purpose processing. Since GPUs have very high memory bandwidth, the performance of GPUs greatly depends on memory access. The main contribution of this paper is to present a GPU implementation of computing Euclidean distance map (EDM) with efficient memory access. Given a two-dimensional (2D) binary image, EDM is a 2D array of the same size such that each element stores the Euclidean distance to the nearest black pixel. In the proposed GPU implementation, we have considered many programming issues of the GPU system such as coalesced access of global memory and shared memory bank conflicts, and so on. To be concrete, by transposing 2D arrays, which are temporal data stored in the global memory, with the shared memory, the main access from/to the global memory enables to be performed by coalesced access. In practice, we have implemented our parallel algorithm in the following three modern GPU systems: Tesla C1060, GTX 480 and GTX 580. The experimental results have shown that, for an input binary image with size of 9216 × 9216, our implementation can achieve a speedup factor of 54 over the sequential algorithm implementation.
This paper presents an FPGA implementation of a Support Vector Machine (SVM) classification using the DSP slices and block RAMs in the Xilinx Virtex-6 family FPGA. In our approach, the SVM classification is performed by the multiple DSPs. Our implementation supports 3 types of kernel functions, the sigmoid kernel, the polynomial kernel, and the RBF kernel. We connect DSPs with the built-in cascade logic in a DSP slice. Thus, our architecture consists of a cascaded DSP pipeline and process the input data with this pipeline. The number of DSP slices included in this cascade connection is equal to the number of the support vectors in the SVM. We have implemented the processor core which includes 768 DSPs for SVM classification in a Xilinx Virtex-6 FPGA XC6VLX240T-FF1156. The implementation results show that it can be implemented in the FPGA with 768 DSP48E1 slices, 800 block RAMs and 17680 slices. It runs in 370.096MHz clock frequency and can evaluate the SVM classification for 128-dimensional feature space data 2.89×10 6 times per second.