Kavli Affiliate: Xiang Zhang
| First 5 Authors: Jincheng Zhou, Jin Zhang, Xiang Zhang, Tiaojie Xiao, Di Ma
| Summary:
Sorting algorithms are the most extensively researched topics in computer
science and serve for numerous practical applications. Although various sorts
have been proposed for efficiency, different architectures offer distinct
flavors to the implementation of parallel sorting. In this paper, we propose a
hybrid vectorized merge sort on ARM NEON, named NEON Merge Sort for short
(NEON-MS). In detail, according to the granted register functions, we first
identify the optimal register number to avoid the register-to-memory access,
due to the write-back of intermediate outcomes. More importantly, following the
generic merge sort framework that primarily uses sorting network for column
sort and merging networks for three types of vectorized merge, we further
improve their structures for high efficiency in an unified asymmetry way: 1) it
makes the optimal sorting networks with few comparators become possible; 2)
hybrid implementation of both serial and vectorized merges incurs the pipeline
with merge instructions highly interleaved. Experiments on a single FT2000+
core show that NEON-MS is 3.8 and 2.1 times faster than std::sort and
boost::block_sort, respectively, on average. Additionally, as compared to the
parallel version of the latter, NEON-MS gains an average speedup of 1.25.
| Search Query: ArXiv Query: search_query=au:”Xiang Zhang”&id_list=&start=0&max_results=3