Study Of Multicore-based Algorithms For Computing Ramsey Numbers

With the arrival of the era of big data, the traditional data processing methods have been unable to cope with the increasing amount of computation.In accordance with the development trends of hyper-threading and multi-core processor, distributed programming based on cluster and multithread concurrency programming based on multicore have become two most important ways to promote the computing performance. A parallel programming model MapReduce proposed by Google for processing the data intensive tasks, by which massive data can be processed concurrently. At present, there are many different implementations of MapReduce model, in which Phoenix++is a system based on multi-core shared-memory with high execution efficiency.Graph Ramsey numbers have been applied in information theory and theoretical computer science. However, determining their exact values is NP-hard. In the study of Ramsey numbers, the computational complexity will increase at an exponential rate with the increase of the number of vertices. Due to sharp increase in the amount of computation, it is difficult to solve the problem in a relatively short period of time by a single-core computer. Therefore, the algorithms based on multi-core for computing Ramsey numbers are studied in this paper.Firstly, the principle and process of MapReduce model, different implements of MapReduce model, and Phoenix++system based on multi-core are introduced in detail. Then an algorithm based on single-core CPU for sloving Ramsey numbers of cycle-sets and complete graphs is proposed. By this algorithm, the multi-core parallel algorithm based on Phoenix++system is designed through several measures, such as data preprocessing, proper task partion and design of key/value pairs. The experiments are carried out to verify the correctness of the parallel algorithm, and to evaluate its performance. The experimental results show that, with the increase of number of vertices, the maximum speedup of the parallel algorithm is3.70, and the executing efficiency increases to92.50%accordingly on the platform of four-core CPU. Finally, employing the parallel algorithm, the exact values of R(C≤n, Kn+1) for4≤n≤13, and R(C≤n, Kn+2) for4≤n≤12are obtained.