Parallel Sorting for Multisets on Multi-core Computers
Multi-core processors have been becoming the mainstream processors. To study design and analysis of parallel sorting algorithm on multi-core computers has important theoretical significance and ap plication value. In this paper, an efficient parallel sorting algorithm for Multisets on multi-core computers is presented. When the sorting algo rithm is executed in parallel recursively, some data with the same keys are picked out by applying the idea of the extremum of the extremums and the subtasks are assigned to the processing cores adaptively and dy namicaUy in order to balance their computing loads. Besides, the num ber of access the main memory is minimized by efficiently the shared L2 cache on the multi-core computers. Meanwhile, the sorted sub-sequences are merged in parallel by using multiple threads. The experiment results on multi-core computer with different number of processing cores and distinct number of parallel threads and different size of input data show that the presented algorithm obtains good speedup and scalability, the performance of the presented algorithm with blocking data technique is superior to that of the one with non-blocking data technique, and the performance of the presented algorithm is better than that of the parallel Quicksort algorithm using selecting median.
Multi-core Multisets Parallel sorting Multiple threads Multi-level caches Shared L2 cache
Zengyan Qu Cheng Zhong Xia Li
School of Computer and Electronics and Information,Guangxi University,Nanning,China
国际会议
南宁
英文
135-162
2009-12-04（万方平台首次上网日期，不代表论文的发表时间）