Study On Parallel List Intersection Algorithm On CPU/GPU Hybrid Platform

Modern web search engines are facing challenges brought by information explosion,trillions of queries need to be processed every day. At the same time CPU is developingtowards a kind of processor that has more and more cores. And driven by gaming market,GPU has been developed into a general purpose computing device. This new CPU/GPUhybrid computing architecture has been a hot spot for researchers and developers.To address this problem, in this paper, we put forward a CPU-GPU cooperative ap-proach to speed up search engines the process of answering user queries. Our work focuson improving the operation of list intersection, which is one of the most time consumingparts of the whole query processing routine and a most frequently presented form of userqueries. We test on a real word data set supplied by Sogou Lab and experimental result-s show our approaches achieve significant performance improvement. Our work includesfollowing several parts:First, we study on several fast search algorithms and list intersection algorithms andput forward a combination list intersection algorithm that suitable for CPU architecture.Second, based on CUDA computing model, we divide search ranges for each CUDAblock. The total computing time is reduced sharply for the resulting average search range ofeach CUDA block is very small.Third, we hide communication time between CPU and GPU and CPU calculation timeby pipeline method. This amount of time reduction gives significant performance gains.And the last, since one CPU core is enough for manipulation a GPU device, there arespare CPU cores left unused. In this paper, we take full use of these spare cores and have angreat overall performance improvement.