基于双核系统的快速排序效率分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于双核系统的快速排序效率分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：随着多核技术的不断发展，多核CPU已经成为处理器市场的主流。如何充分利用多核的优势提高应用程序的性能是开发人员不得不面对的课题。多核系统为开发人员提供了一个实现并行计算的重要平台。文中探讨了基于双核系统的快速排序的效率，介绍了C#线程编程的相关知识，并在此基础上实现了基于双核系统的多线程的快速排序算法，实验结果表明该算法较传统快速排序算法而言，算法执行效率得到了很大的提升。
关键词：多核编程；并行计算；多线程；快速排序
中图分类号：TP332文献标识码：A文章编号：1009-3044(2008)22-705-03
The Efficiency Analysis of the Quick Sort Based On The Dual-core Systems
ZHANG Huo-lin, LI Guo-qing, ZHANG Jiang-wei
(Xuchang University,Xuchang 461000,China)
Abstract: With the rapid development of multi-core technology, the multi-core CPU processors have become the mainstream of CPU market. how to make full use of the advantages of multi-core to improve the performance of the application has become a new issue that the developers have to face. Multi-core system provide an important paltform of parallel computing developers. In this paper,we discussed the efficiency of the quick sort based on the dual-core systems, introduced the C # thread programming, and based on this we developped the multi-threading version of the quick sort algorithm based on the dual-core system, the results showed that the efficiency of new algorithm has been greatly improved compared with the sequence.
Key words: multi-core programming; parallel computing; multi-threading; quick sort
1 引言
在现有生产工艺条件下，CPU主频升级之路已经走到了拐点。桌面的主频在2000年达到了1GHz，2001年达到2GHz，2002年达到了3GHz。但至今仍然没有看到4GHz处理器的出现，电压和发热量成为最主要的障碍。Intel和AMD开始寻找其它方式提升处理器的能效，而最具实际意义的方式是增加CPU内处理核心的数量。多核时代开创于2005年春季，其标志是Intel的Pentium D处理器800系列的。近两年来随着Intel和AMD双核、四核CPU的陆续推出，由于其优良的性价比，多核处理器已经成为处理器市场的主流。
多核时代的到来，给传统的基于单核的编程思想带来了巨大的冲击。常见的串行程序在单核CPU上是顺序执行的，在多核系统上运行只能利用其中的一个核心，因此不能获得性能的提升。为了能够充分地利用多核CPU的性能，程序开发员必须学习新的程序设计模式。在新的设计模式中，软件开发人员面临的任务就是如何充分利用多核，避免性能闲置。对应用程序可以并行的部分线程化，并将这些线程有效地分配到不同的内核中去，多个核心同时执行，软件的性能与效率必将得到大幅的提升。
目前有多种可选择的多核多线程开发工具。相对于C/C++/Fortran等编译型语言，C#/java/Python等新型语言也许是更好的选择[1]。原因C#/java/Python等语言一般都提供了对多线程的原生支持；如C#的System.Threading.Thread、Java的java.lang.Thread及Python的Threading.Thread。相形之下，编译型语言往往都是通过平台相关的库来提供多线程支持，如Win32 SDK、POSIX threads等，由于没有统一的标准，造成使用C/C++编写多线程程序需要考虑更多的细节，提高了项目成本。
2 C#多线程简介
2.1 线程简述
线程可以被描述为一个微进程，它拥有起点，执行的顺序系列和一个终点。它负责维护自己的堆栈，这些堆栈用于异常处理，优先级调度和其他一些系统重新恢复线程执行时需要的信息[2，4]。从这个概念看来，好像线程与进程没有任何的区别，实际上线程与进程之间区别在于：一个完整的进程拥有自己独立的内存空间和数据，但是同一个进程内的线程是共享内存空间和数据的。一个进程对应着一段程序，它是由一些在同一个程序里面独立的同时的运行的线程组成的。
线程有时也被称为并行运行在程序里的轻量级进程，并且大多数现代操作系统把线程作为时序调度的基本单元。在没有明确协调的情况下，线程相互同或异步地执行。因为线程共享其所属进程的内存地址空间，因此所有同一进程中的线程访问相同的变量，并从同一个堆中分配对象，这相对于进程间通信机制而言实现了良好的数据共享，但同时也会产生意外的后果。C#对多线程提供语言和类库级的支持，简化了并行的多线程应用程序的开发。
2.2 C#多线程状态及状态之间的转换过程
System.Threading.ThreadState枚举指定Thread的执行状态，此枚举有一个FlagsAttribute属性，允许其成员值按位组合。下面是ThreadState定义的枚举常数[3]。
表1 ThreadState定义的枚举常数
■
Thread对象的ThreadState属性提供一个由ThreadState定义的位掩码，它指示线程的当前状态。一个线程至少总是处于ThreadState枚举中定义的一个可能状态，并且可以同时处于多个状态。注意，只能在一些调试方案中使用线程状态，而不应该在代码中使用线程状态来同步线程活动。在创建托管线程时，该线程处于Unstarted状态。线程会保持Unstarted状态，直到作系统调度到已启动状态。调用Start方法使操作系统知道该线程可启动，但是它并不直接更改线程的状态。一旦线程处于已启动的状态中，就可以执行许多操作来使线程更改状态。表2列出了使状态发生更改的操作，以及相应的新状态。
表2 使线程状态发生更改的操作及相应的新状态
■
在任何时间内，线程通常都处于多个状态中。例如，如果当某个线程因调用Monitor.Wait方法而被阻止时，另一个线程调用该线程的Abort方法，那么该线程将同时处于WaitSleepJoin和AbortRequested状态。在这种情况下，一旦该线程从对Wait方法的调用中返回或被中断，它就会收到ThreadAbortException异常。
一旦线程因调用Start方法而离开Unstarted状态，它就无法再返回到Unstarted状态。同样，线程也永远无法从Stopped状态转移到其他状态。
Thread类还有两个属性值与线程的状态相关，即IsAlive和IsBackground。IsAlive是只读属性，说明线程是否已经启动并且没有结束。IsBackground用于了解线程是否是后台线程，以及将线程设置为后台或者前台线程。如果IsBackground为true，则说明线程是后台线程，Thread对象的ThreadState值包含Background。否则，线程为前台台进程，Thread对象的ThreadState值不包含Background。托管线程不是后台线程，就是前台线程。后台线程不会使托管执行环境处于运行状态，除此之外，后台线程与前台线程是一样的。一旦所有前台线程在托管进程中被停止，系统将停止所有后台线程并关闭。直到所有前台线程都终止了，应用程序才会结束。当应用程序结束时，所有的后台线程也会自动终止。通过将IsBackground设置为true，可以将线程设置为后台线程；通过将IsBackground设置为false，可以将线程设置为前台线程。
3 基于双核系统的快速排序
3.1 传统的快速排序算法
快速排序算法由C.R.A.Hoare于1962年首次提出。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。
快速排序的基本思想是：选取一个划分基准将待排序序列分为两个子序列，一个子序列所有元素小于这个标准，另一个子序列大于这个标准。不断进行这样的划分，最后构成n个子序列，此时，它们已经按照递增顺序排列，算法结束[5]。下面是快速排序算法代码。
快速排序算法：
输入：数组list，数组起始位置low，结束位置high
输出：按递增顺序排列的数组list[]
public void myQuickSort(int[] list, int low, int high)
{
if (low < high)
{
int pivot = Partition(list, low, high); // Partition返回枢纽元素的数组下标
myQuickSort(list, low, pivot - 1); //对左半段快速排序
myQuickSort(list, pivot + 1, high);//对右半段快速排序
} }
上述算法中的Partition函数，将数组list[low,high]划分为小于基准list[low]的list[low,pivot]与大于基准的list[pivot+1,high]两个子序列。
快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础[6]。分治策略分为三步：
1)将问题分成若干大小基本相等的子问题；
2)独立地解决这些子问题；
3)将子问题归并成原问题的解。
由分治技术设计思想可知，在多核系统上，分解而成的各个子问题可以并行求解，问题的求解效率必然得到大幅提升。因此，相较于单核系统，多核系统具有天然的优势。
3.2 基于双核系统的快速排序
传统快速排序在多核系统如何才能获得较好的性能，一个直接的思路是：将待排序序列划分为大小基本相等的子序列，由多个线程分别在各个核心上并行执行快速排序，排序完后再使用归并算法将排好的几个子序列归并成一个递增有序序列。实验环境双核Dell系统，2个线程并行排序的代码如下：
threadPara threadPara1 = new threadPara(list1,low,high);//定义类threadPara的实例
threadPara threadPara1 = new threadPara(list2,low,high);//定义类threadPara的实例
Thread Thread1 = new Thread(new ThreadStart(threadPara1.doSort)); //定义线程1及其执行方法
Thread Thread2 = new Thread(new ThreadStart(threadPara2.doSort)); //定义线程2及其执行方法
Thread1.Start(); //线程1开始执行
Thread1.Start(); //线程2开始执行
Thread1.Join(); //线程1完成返回主线程
Thread1.Join(); //线程1完成返回主线程
Merge(list1, list2, resultArray1); //归并已排好序的子序列
将待排序序列分为大小相等的两个子序列list1、list2，Thread1、Thread2的入口方法doSort调用myQuickSort分别进行快速排序，myQuickSort的参数在定义threadPara1、threadPara2时由类threadPara的构造函数传入，子线程完成后返回主线程，调用静态函数Merge进行归并排序得到最终序列resultArray1。
3.3 基于双核系统的快速排序效率分析
为了试验一下多核CPU上排序算法的效率，比较单任务串行算法和多任务并行算法的差距，我们测试了在1线程、2线程、4线程条件下，对1,000,000个随机整数进行快速排序算法所花的时间。
实验平台为Dell Latitude D630系列双核笔记本电脑。采用Intel 965GM芯片组，Intel Core 2 Duo 2.0G，高速缓存2MB，前端总线800MHz，内存DDR2 SDRAM 2G。操作系统Microsoft Windows XP Professional 5. 1. 2600(WinXP Retail )，编译器为Microsoft Visual Studio2005。
表3 算法在三种情况下10次运行时间
■
实验结果表明，对相同的1，000，000个随机整数排序，单线程需要342ms，2线程需要202ms，4线程需要223ms。与单线程排序相比较，多线程并行快速排序算法效率有了很大的提高，2线程运行速度比单线程提高了近69%。由于4线程分配到2个核心，存在着线程的上下文切换，因此在双核平台2线程排序要优于4线程。
4 结束语
多核技术的发展必将引领软件研发发生基础性变化，特别对那些面向一般应用、运行在PC 和低端服务器上的应用软件更有非同一般的意义[7]。多核平台为开发人员提供了一种优化应用程序的渠道，那就是通过仔细分配加载到各线程（或者各处理器核）上的工作负载（也就是实现各线程的负载均衡）就能够得到性能上的提升。并且，开发人员也可以对应用程序代码加以优化，使其能够更加充分地使用多个处理器资源，进而达到提升应用程序性能的目的[2]。但是，多线程也存在它的不足，线程的使用（滥用）会给系统带来上下文切换（Context switches）的额外负担，并且避免线程间共享数据的竞争而采取的同步机制，也会影响其运行效率[8]。
参考文献：
[1] 赖勇浩.积极准备、谨慎行动――应对多核编程革命[J].程序员,2007(4):65-67.
[2] Akhter S., Roberts J.多核程序设计技术:通过软件多线提升性能[M].北京:电子工业出版社,2007.
[3] Nagel C., Evjen B., Glynn J., et al.C#高级编程[M].4版.北京:清华大学出版社,2006.
[4] 多核系列教材编写组.多核程序设计[M].北京:清华大学出版社,2007.
[5] Cormen T H., Leiserson C E.,et al. 算法导论[M].2版.北京:机械工业出版社,2006.
[6] 郑宗汉,郑晓明.算法设计与分析[M].北京:清华大学出版社,2007.
[7] 蔡佳佳,李名世,郑锋.多核微机基于OpenMP的并行计算[J].计算机技术与发展,2007(10):87-91.
[8] Goetz B.,Peierls T., Bloch J.,et al.JAVA并发编程实践[M].北京:电子工业出版社,2007.