We discuss how stringsorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential stringsorting algorithms and successful parallelsorting algorithms for ...
详细信息
We discuss how stringsorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential stringsorting algorithms and successful parallelsorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. As base-case sorter for LCP-aware stringsorting we describe sequential LCP-insertion sort which calculates the LCP array and accelerates its insertions using it. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our parallel string sorting implementations scale very well on real-world inputs and modern machines.
The increase in the amount of data is evident in recent times. The amount of data stored and retrieved is increasing at a fast rate. Processing text data consumes large amount of memory in terms of storage and extract...
详细信息
ISBN:
(纸本)9781479959587
The increase in the amount of data is evident in recent times. The amount of data stored and retrieved is increasing at a fast rate. Processing text data consumes large amount of memory in terms of storage and extraction. sorting the stored data is one of the most favorable methods that can be used in order to increase the efficiency of extracting stored data. Graphic Processing Units (GPUs) have evolved from being used as dedicated graphic rendering modules to being used to exploit fast parallelism for large computational purposes. The use of GPUs for sortingstrings large in size has produced effective and fast results when compared to using CPUs. This paper produces a comparative study on the most popular and efficient stringsorting algorithms that have been implemented on CPU and GPU machines. This paper also proposes an efficient parallel multi-key quicksort implementation which uses ternary search tree in order to increase the speed up and efficiency of sorting large set of string data.
暂无评论