Study Of Multicore-based Parallel Algorithm For Constructing Extremal Graphs

With the development of computer science, many computer research fields need enough computing power to analyze large data set. In many cases, it is difficult to solve the problem in a relatively short period of time by a single-core computer. So the study of parallel algorithms based on multi-core processors has become one of the most popular directions. The extremal graph is a graph with the maximum number of edges such that it does not contain some given subgraphs. The extremal graphs with small order can be constructed by an algorithm efficiently. However, the execution time of the algorithms grows exponentially with the increase of the orders of extremal graphs. It seems to be difficult to solve this problem by a single-core computer in a short period of time.By analyzing and studying the serial algorithm FCG and the parallel programming models systematically, a parallel algorithm FCG-MP for constructing extremal graphs is implemented on OpenMP. On the basis of in-depth study on the MapReduce parallel programming model, a parallel algorithm FCG_Phoenix for constructing extremal graphs is implemented on the Phoenix system. Besides, the performance of FCG_Phoenix is optimized as follows:setting identifiers to distinguish different tasks in order to avoid results conflicted; allocating the data of tasks appropriately to achive a good load balance. In addition, the experimental results of constructing the extremal graphs of small order show that the efficiency of FCG_Phoenix is better than FCG-MP.In order to verify the effectiveness and efficiency of algorithm FCG_Phoenix, several experiments are made for constructing the extremal graphs without hexagon and with no more than28vertices. It is shown that, compared with the serial algorithm, the average speedup of FCG_Phoenix is7.043, and its average efficiency is88.04%on8-core CPU. Especially, there are7,856,799graphs in the result set including when the order is21, and the performance of FCG_Phoenix is reached the peak, its efficiency is88.92%.Finally, the extremal graphs without hexagon and no more than29vertices are constructed by employing the algorithm FCG_Phoenix. The results show that the size of such extremal graphs is72, and there are three extremal graphs in total.