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

Optimized Implementation of Sorting Algorithm on Loongson 3A

作　　者：翁玉萍[1] 顾乃杰[1] 李恺[1] 陈强[1] 

机构地区：[1]中国科学技术大学计算机科学与技术学院安徽省计算与通讯软件重点实验室,合肥230027

出　　处：《计算机工程》2011年第20期255-257,270,共4页Computer Engineering

基　　金：国家"863"计划基金资助项目(2008AA010902);国家自然科学基金资助项目(60803066)

摘　　要：分析归并排序算法和快速排序算法,根据国产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.

关 键 词：龙芯3A 归并排序 快速排序 优化算法 循环展开 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]