Optimization And Implemetation Of Parallel Join Algorithm

With the development of integrated semiconductor and computer sciences, plenty of multi-cores processors/many-cores processors arose in the past few years.MIC(Many Integrated Core),the product released by Intel,based on X86 outperforms others.Compared with other multi-cores CPU,MIC has more cores and a wider memory bandwidth,and supports SIMD,which makes it more suitable for High Performance Computing.Meanwhile,the operation of join in parallel database has always been the spot of HPC researches,which is the base of query optimization of database.Our contribution in this paper is as follow:based on the feature of MIC,we improve the performace of the traditional parallel join algorithms including Nestloop Join, Sort Merge Join and Hash Join.Using SIMD and the asynchronous offloaded computation model,we make our program running both on MIC and CPU,which offers a better performance in join operation in databse.What we focus in our paper is to improve multi-thread level parallelism and data level parallelism of parallel join algorithm. First of all, all the common parallel join algorithms: Nest Loop Join, Sort Merge Join, Hash Join, were presented and analysized. Many optimization strategies based on the three algorithms were discussed.Afterwards, based on the feature of MIC, each of the algorithms is optimized and improved. We try to run our program on MIC with over 200 threads and realize data level parallelism using SIMD.Lastly, asynchronous offloaded computation model was applied in our program both running on MIC and CPU, offering a favorable performance.All the data needed to be divided into blocks when it was asynchronous offloaded.At the end of our paper, we gave out our experiment results and presented our analysis about it.From different parts, inluding data size, threading scalability, and data skew, we compared our result with those which is declared best running on CPU. It clearly shows that we got a better performace with our algorithms. MIC provides a favorable acceleration, which makes the three join algorithms faster with a speed-up ratio of 52,18 and 35.