Implementation of histogram based sampling algorithm within an EDA scheme with CUDA

In this paper, we describe an implementation of Node Histogram Sampling Algorithm (NHBSA) on GPUs with CUDA and apply the algorithm to solve large scale QAP instances. To solve large scale QAP instances, we combined the taboo search with NHBSA. In this implementation, we used an efficient thread assignment method, Move-Cost Adjusted Thread Assignment (MATA), which is proposed in a previous study. Through these experiments, we show that MATA plays an important role for efficient parallel computation in NHBSA. We also show the effectiveness of running NHBSA on multiple GPUs using the island model in independent run mode.