<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
双核CPU上的快速排序效率
为了试验一下多核CPU上排序算法的效率,得比较单任务情况下和多任务并行排序算法的差距,因此选用快速排序算法来进行比较。
测试环境:双核CPU 2.66GHZ
单核CPU 2.4GHZ
以下是一个快速排序算法的源代码:
UINTSplit(void **ppData, UINTuStart, UINTuEnd,
COMPAREFUNCCompareFunc)
{
void *pSelData;
UINTuLow;
UINTuHigh;
uLow = uStart;
uHigh = uEnd;
pSelData = ppData[uLow];
while ( uLow uHigh )
{
while ( (*CompareFunc)(ppData[uHigh], pSelData) > 0
&& uLow != uHigh )
{
--uHigh;
}
if ( uHigh != uLow )
{
ppData[uLow] = ppData[uHigh];
++uLow;
}
while ( (*CompareFunc)( ppData[uLow], pSelData )
&& uLow != uHigh )
{
++uLow;
}
if ( uLow != uHigh )
{
ppData[uHigh] = ppData[uLow];
--uHigh;
}
}
ppData[uLow] = pSelData;
returnuLow;
}
voidQuickSort(void **ppData, UINTuStart, UINTuEnd,
COMPAREFUNCCompareFunc)
{
UINTuMid = Split(ppData, uStart, uEnd, CompareFunc );
if ( uMid > uStart )
{
QuickSort(ppData, uStart, uMid - 1, CompareFunc);
}
if ( uEnd > uMid )
{
QuickSort(ppData, uMid + 1, uEnd, CompareFunc);
}
}
先测试一下这个快速排序算法排一百万个随机整数所花的时间:
voidTest_QuickSort(void)
{
UINTi;
UINTuCount = 1000000; //1000000个
srand(time(NULL));
void **pp = (void **)malloc(uCount * sizeof(void *));
for ( i = 0; i uCount; i++ )
{
pp[i] = (void *)(rand() % uCount);
}
clock_tt1 = clock();
QuickSort(pp, 0, uCount-1, UIntCompare);
clock_tt2 = clock();
printf("QuickSort 1000000 Time %ld\n", t2-t1);
free(pp);
}
在双核CPU2.66GHZ机器上运行测试程序,打印出花费的时间约为406 ms
在单核CPU2.4GHZ机器上运行测试程序,打印出花费时间约为484ms
可见在双核CPU上运行单任务程序和单核CPU基本是一样的,效率没有任何提高。
下面再来把上面的快速排序程序变成并行的,一个简单的方法就是将要排序的区间分成相同的几个段,然后对每个段进行快速排序,排序完后再使用归并算法将排好的几个区间归并成一个排好序的表,我们先四个线程来进行排序,代码如下:
void ** Merge(void **ppData, UINTuStart, UINTuEnd,
void **ppData2, UINTuStart2, UINTuEnd2, COMPAREFUNCcfunc)
{
UINTi, j, k;
UINTu1, u2, v1,v2;
void **pp1;
void **pp2;
void **pp = (void **)malloc( (uEnd-uStart+1+uEnd2-uStart2+1) * sizeof(void *));
if ( pp == NULL )
{
returnNULL;
}
if ( (*cfunc)(ppData2[uStart2], ppData[uStart]) > 0 )
{
u1 = uStart;
u2 = uEnd;
v1 = uStart2;
v2 = uEnd2;
pp1 = ppData;
pp2 = ppData2;
}
else
{
u1 = uStart2;
u2 = uEnd2;
v1 = uStart;
v2 = uEnd;
pp1 = ppData2;
pp2 = ppData;
}
k = 0;
pp[k] = pp1[u1];
j = v1;
for (i = u1+1; i u2; i++ )
{
while ( j v2 )
{
if ( (*cfunc)(pp2[j], pp1[i])
{
++k;
pp[k] = pp2[j];
j++;
}
else
{
break;
}
}
++k;
pp[k] = pp1[i];
}
if ( j v2 )
{
for ( i = j; i v2; i++)
{
++k;
pp[k] = pp2[i];
}
}
returnpp;
}
typedefstructSORTNODE_st {
void ** ppData;
UINT uStart;
UINT uEnd;
COMPAREFUNCfunc;
} SORTNODE;
DWORDWINAPIQuickSort_Thread(void *arg)
{
SORTNODE *pNode = (SORTNODE *)arg;
QuickSort(pNode->ppData, pNode->uStart, pNode->uEnd, pNode->func);
return 1;
}
#define THREAD_COUNT 4
INTMQuickSort(void **ppData, UINTuStart, UINTuEnd,
COMPAREFUNCCompareFunc)
{
void **pp1;
void **pp2;
void **pp3;
INT i;
SORTNODE Node[THREAD_COUNT];
HANDLE hThread[THREAD_COUNT];
INT nRet = CAPI_FAILED;
for ( i = 0; i THREAD_COUNT; i++)
{
Node[i].ppData = ppData;
if ( i == 0 )
{
Node[i].uStart = uStart;
}
else
{
Node[i].uStart = uEnd * i /THREAD_COUNT + 1;
}
Node[i].uEnd = uEnd *(i+1) / THREAD_COUNT;
Node[i].func = CompareFunc;
hThread[i] = CreateThread(NULL, 0, QuickSort_Thread, &(Node[i]), 0, NULL);
}
for ( i = 0; i THREAD_COUNT; i++ )
{
WaitForSingleObject(hThread[i], INFINITE);
}
pp1 = Merge(ppData, uStart, uEnd/4, ppData, uEnd/4+1, uEnd/2, CompareFunc);
pp2 = Merge(ppData, uEnd/2+1, uEnd*3/4, ppData, uEnd*3/4+1, uEnd, CompareFunc);
if ( pp1 != NULL && pp2 != NULL )
{
pp3 = Merge(pp1, 0, uEnd/2-uStart, pp2, 0, uEnd - uEnd/2 - 1, CompareFunc);
if ( pp3 != NULL )
{
UINTi;
for ( i = uStart; i uEnd; i++)
{
ppData[i] = pp3[i-uStart];
}
free(pp3);
nRet = CAPI_SUCCESS;
}
}
if( pp1 != NULL)
{
free( pp1 );
}
if ( pp2 != NULL )
{
free( pp2 );
}
returnnRet;
}
用下面程序来测试一下排1百万个随机整数的花费时间:
voidTest_MQuickSort (void)
{
UINTi;
UINTuCount = 1000000; //1000个
srand(time(NULL));
void **pp = (void **)malloc(uCount * sizeof(void *));
for ( i = 0; i uCount; i++ )
{
pp[i] = (void *)(rand() % uCount);
}
clock_tt1 = clock();
INTnRet = MQuickSort(pp, 0, uCount-1, UIntCompare);
clock_tt2 = clock();
printf("MQuickSort 1000000 Time %ld\n", t2-t1);
free(pp);
}
在双核CPU上运行后,打印出花费的时间为234 ms , 单任务版的快速排序函数约需406ms左右,并行运行效率为:406/(2×234) = 86.7% 左右。运行速度快了172ms。
可见双核CPU中,多任务程序速度还是有很大提高的。
当然上面的多任务版的快速排序程序还有很大的改进余地,当对4个区间排好序后,后面的归并操作都是在一个任务里运行的,对整体效率会产生影响。估计将程序继续优化后,速度还能再快一些。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1109499
相关推荐
AMD双核CPU优化程序.exeAMD双核CPU优化程序.exe
而随着硬件发展速度日益加快,等微软出补丁得经过完整的兼容测试会耗费许多时间,GPU就经常有官方未通过微软的认证提前发布的官方驱动,而AMD 也在今天发布了Athlon 64 X2双核处理器的驱动程序。 最新版的1.3....
一个简单双核CPU的verilog实现(加中断、异常处理已通过实验箱验证)可以实现双核交替访存,提高访问存储器效率,同时可以通过内存数据区实现双核数据的共享。
AMD双核CPU的性能
如果使用注册表编辑器或其他方法错误地修改了注册表,则可能会出现严重问题。这些问题可能需要重新安装操作系统才能解决。Microsoft 不能保证您可以解决这些问题。修改注册表需要您自担风险。
为了充分利用双核CPU性能,本工具可以让程序指定在不同的CPU内核上运行。
AMD双核CPU驱动卸载工具.。。。。AMD双核CPU驱动卸载工具.。。。。
1.AMD官方双核CPU驱动(AMD Athlon™ 64 X2 Dual Core Processor Driver for Windows XP and Windows Server 2003 Version (x86 and x64 exe) 1.3.2.16 ) 2.AMD官方双核CPU优化(AMD Dual-Core Optimizer) 3.微软...
用MagicSpeed给双核CPU降温.pdf
让双核物尽其用 双核CPU使用指南.pdf
让双核cpu利用率100%的代码,增加多线程就可以,如果想要内存满了,就不断开辟内存,仅仅是eclipse内存。 资源利用率 java 100% cpu 死机 资源利用率 java 100% cpu 死机 资源利用率 java 100% cpu 死机 资源利用率 ...
AMD双核CPU最新优化(驱动更新),优化玩大型3D游戏的效果 精品飞车 魔兽。。。
体验最超值双核CPU.pdf
双核CPU工作原理及使用方法.pdf
AMD双核CPU优化程序AMD Dual-Core Optimizer最新1.14版
AMDx2双核CPU优化.docx
POWERPC 双核CPU 8572芯片手册
win7边栏双核cpu温度小工具。如果要整桌面正适合。
在用了双核CPU或双CPU的朋友是不是在用CD9会出现有时导入或打开文件时停止响应的现象呢,暂时的解决方法,那就是打开COREDRAW9后,按CTRL+ALT+DEL三键调出任务管理器,在进程里选中coredraw.exe进程,点右键,设置...
基于开放式CPU设计系统的双核CPU设计.pdf