Research On Algorithms Based On GPU For Four Color Ramsey Numbers

In recent years, with the rapid development of GPU technology, the general purpose computing based on GPU has become a hot topic around the world. Since the early GPU programming is based on low level graphics API, it is very costly, time-consuming and difficult. And it is also difficult to debug and maintain the code. CUDA (Compute Unified Device Architecture) is a parallel computing platform and programming model created by NVIDIA. It provides a programming environment similar to C language, and developers can use the massive parallel computing resources of GPU easily.Graph Ramsey numbers have been applied in information theory and theoretical computer science, however, their exact values are very difficult to obtain. For the multicolor Ramsey numbers, they are very difficult to prove by a mathematical way because there are many cases in their proof. Meanwhile, with the increasing of the coloring numbers, their calculations increase rapidly due to a large number of computation. So the application of GPU parallel computing technology for determining multicolor Ramsey numbers is studied in this paper.Firstly, the programming model, the thread organization and the memory architecture of CUDA are introduced in detail. Then an algorithm over CPU for computing four color Ramsey numbers is proposed, and it is improved by considering the symmetry of joining graphs. Based on the improved one, an algorithm over GPU is designed, the experimental results show that the parallel algorithm achieves up to40times speedups over the host CPU. Finally, employing the algorithm, an upper bound on is improved to19from20through a large number of calculation.