Efficient and Scalable Thread-level Parallel Algorithms for Sorting Multisets on Multi-core Systems

By distributing adaptively the data blocks to the processing cores to balance their computation loads and applying the strategy of "The extremum of the extremums" to select the data with the same keys, a cache-efficient and thread-level parallel algorithm for sorting Multisets on the multi-core computers is proposed. For the sorting Multisets problem, an aperiodic multi-round data distribution model is presented, which the first round scheduling assigns data blocks into the slave multi-core nodes according to the given distribution order and the other rounds scheduling will distribute data blocks into the slave multi-core nodes by first request first distribution strategy.