排序算法在龙芯3A上的优化实现

Optimized Implementation of Sorting Algorithm on Loongson 3A

分析归并排序算法和快速排序算法,根据国产CPU龙芯3A的体系结构特性,提出2种优化算法并进行实现。综合利用访存特性,引入拷贝优化、循环展开、交换操作优化和不同基本排序混用等优化技术。测试结果表明,在不影响排序稳定性的前提下,与Glibc 2.11库中的排序函数相比,2种优化算法均能提升16.9%～90.5%的排序性能。

Through analysis of the characteristics of merging sorting and quick sorting,this paper presents two optimized algorithms specially for Loongson 3A CPU＇s features.To boost the performance,it adapts various optimizing techniques including utilize the characteristic of memory access,copy optimization,loop unrolling,operation exchanging and compounding different basic sorting algorithms.Without losing the robustness,sorting performance on Loongson 3A is improved by about 16.9% to 90.5% in different situations,compared to the sorting function in Glibc 2.11.