liangbch
发表于 2008-4-10 20:39:56
在38楼给出几个 以2^32为基,使用 MMX寄存器,可计算480bit ×480bit 的函数。其中
UInt480x480_MMX是一个使用完全循环展开,仅能计算480bit的数的版本;而UIntMul_basecase_MMX2是一个不使用循环展开,可计算任意长度的数的版本。
现在,楼主又给出一个使用4路循环展开的版本,理论上这个版本在 计算480bit × 480 bit,应该比 UIntMul_basecase_MMX2 快一些,但慢于UInt480x480_MMX
38#给出的这两个函数的原型是:
void UInt480x480_MMX( unsigned long * result, const unsigned long *left, const unsigned long *right );
void UIntMul_basecase_MMX2( unsigned long * result, const unsigned long *left, const unsigned long *right,
unsigned long leftLen,unsigned long rightLen );
无心人
发表于 2008-4-10 20:44:30
对, 你的分析很对
看并行4路的效率了
在加法是1/6的增幅
乘法估计要更多
liangbch
发表于 2008-4-10 21:11:02
乘法肯定是比1/6少。
循环展开能够提高速度的原因在于:
1.减少了数组指针的递增指令的执行次数,如下面代码中的“lea edi, ”,“lea ebx, ”,
2.减少了比较和条件跳转指令的执行次数。如下面代码中的“sub ecx, 1“,"jnz mbinmul3".
而其他用来工作的指令则无法减少,另一个好处是,循环展开便于合适的安排指令,使指令间的依赖很小,但这种影响一般很小。
如果循环体很小,其中几条指令不是很耗时,则减少的这些指令占用的时间比例较大,提速明显。反之则提速不明显。对于加法,真正干活的指令占用时间少,故提升比例较高。而对于乘法,真正用来干活的指令(如pmuludq)占用的时间比例很大。故提升的比例应该很有限。movd mm2, dword ptr
lea edi,
movd mm3, dword ptr
pmuludq mm2, mm1
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr , mm0
psrlq mm0, 32
lea ebx,
sub ecx, 1
jnz mbinmul3
无心人
发表于 2008-4-10 21:30:14
可是乘法存在延迟长的问题啊
如果单循环,可能造成整个循环都在等乘法结果
而4个一起,只要一个好了
就能做部分工作,
处理完一个
也许剩下的乘法都不会再产生多余的延迟了
所以到底是你说的情况
还是我说的情况
要测试了才说的清
无心人
发表于 2008-4-10 21:32:57
所以我分析下面的彩色指令都应该不占CPU额外时间
movd mm2, dword ptr
lea edi,
movd mm3, dword ptr
pmuludq mm2, mm1
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr , mm0
psrlq mm0, 32
lea ebx,
sub ecx, 1
jnz mbinmul3
无心人
发表于 2008-4-10 21:36:11
执行顺序可能是
1、movd mm2, dword ptr
1、lea edi,
1、movd mm3, dword ptr
2、pmuludq mm2, mm1
2、paddq mm0, mm3
3、paddq mm0, mm2
4、movd dword ptr , mm0
4、psrlq mm0, 32
4、lea ebx,
2、sub ecx, 1
5、jnz mbinmul3
liangbch
发表于 2008-4-11 10:41:45
理论上,CPU存在多个执行单元,调整指令顺序,减少指令依赖可以提升速度。然而我之前的种种实验表明,这种调整指令顺序,提高并行度的做法并无多大效果,不知何故。
另一种行之有效的优化循环的办法是减少控制指令,这种做法在某些CPU效果相当明显,我们以本贴子中出现过的程序为例给予说明。
UInt480x480_yaos,UInt480x480_MMX2,UInt480x480_MMX3 这三个函数均为以普通方式计算大数乘法的函数,
程序的逻辑也相同,不过 UInt480x480_yaos多做了一些额外的工作,即需要先将目标buffer清零。
先看看他们在2种CPU的速度表现,计算2个长为15个DWORD的乘积,运行100万次
PIV 2.6 PM1.7
UInt480x480_yaos698.655 ms 1053.610 ms
UInt480x480_MMX2671.515 ms 863.055 ms
UInt480x480_MMX3585.015 ms 798.775 ms
再分析一下这几个程序的差异,这几个程序均为2重循环,在循环体中,包括真正干活的指令和循环控制的指令,循环控制的指令又分调整数组指针或计数器的指令 和 比较/跳转指令.这3个程序中内循环指令条数分别为11,10,9,其中循环控制指令分别为4,3,2条。
第一个程序,循环控制指令是 “lea edi, ”,“lea ebx, ”,“sub ecx, 1”,“jnz mbinmul3”,共4条。第一个程序,循环控制指令是“inc eax”,“cmp eax,dword ptr ”,“jbinnerLoop”。第三个程序循环控制指令是“inc eax”,“jnz innerLoop”。
第三个程序的速度已经非常逼近完全循环展开的版本,尤其是在PM CPU。在PIV/PM,速度分别达到完全循环展开程序的82%/%95.
下面给出这三个程序调用到的子程序的完整的代码。程序UInt480x480_yaos 调用到的子程序的代码
voidlMul_yaos(uint32*result,
const uint32*left,
const uint32*right,
uint32 sLeft,
uint32 sRight)
{
__asm {
mov edx, sLeft
movesi, dword ptr
movedi, dword ptr
movebx, dword ptr
mbinmul2:
mov eax, ebx
pxor mm0, mm0
mov ecx, sRight
movd mm1, dword ptr
movd mm4, edi
mbinmul3:
movd mm2, dword ptr
lea edi,
movd mm3, dword ptr
pmuludq mm2, mm1
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr , mm0
psrlq mm0, 32
lea ebx,
sub ecx, 1
jnz mbinmul3
movd edi, mm4
movd dword ptr , mm0
mov ebx, eax
lea esi,
lea ebx,
sub edx, 1
jnz mbinmul2
emms
}
}程序UInt480x480_MMX2 调用到的子程序的代码
_declspec(naked)
void UIntMul_basecase_MMX2( unsigned long * result,
const unsigned long *left,
const unsigned long *right,
unsigned long leftLen,
unsigned long rightLen )
{
#define STACK_BASE 12
__asm
{
push esi
push edi
push ebp
mov ebp,dword ptr ; result
movesi,dword ptr ; left
movedi,dword ptr ; right
mov ecx,dword ptr ; rightLen
//next10:
cmp ecx,0
jz thisExit
//loop1_Init:
xor eax,eax // j=0;i<leftLen
pxor mm0,mm0
movd mm2,
jmp loop1_Cmp
loop1:
movd mm1,
pmuludq mm1,mm2
paddq mm0, mm1
movd ,mm0
inc eax
psrlq mm0, 32 //carry
loop1_Cmp:
cmp eax,dword ptr //leftLen
jb loop1
movd ,mm0
//outLoopInit:
mov ecx,1 // i=1;i<rightLen
jmp outLoopCmp
outLoop:
add ebp,4
pxor mm0,mm0
movd mm2,
xor eax,eax
jmp innerLoopCmp
innerLoop:
movd mm1,
movd mm3,
pmuludq mm1,mm2
paddq mm0, mm1
paddq mm0, mm3
movd ,mm0
inc eax
psrlq mm0, 32 //carry
innerLoopCmp:
cmp eax,dword ptr //leftLen
jb innerLoop
movd ,mm0
inc ecx
outLoopCmp:
cmp ecx,dword ptr //rightLen
jb outLoop
thisExit:
pop ebp
pop edi
pop esi
emms
ret
}
}程序UInt480x480_MMX3 调用到的子程序的代码:
_declspec(naked)
void UIntMul_basecase_MMX3( unsigned long * result,
const unsigned long *left,
const unsigned long *right,
unsigned long leftLen,
unsigned long rightLen )
{
#define STACK_BASE 12
__asm
{
push esi
push edi
push ebp
mov ebp,dword ptr ; result
movesi,dword ptr ; left
movedi,dword ptr ; right
mov ecx,dword ptr ; rightLen
//next10:
cmp ecx,0
jz thisExit
//loop1_Init:
xor eax,eax // j=0;i<leftLen
pxor mm0,mm0
movd mm2,
jmp loop1_Cmp
loop1:
movd mm1,
pmuludq mm1,mm2
paddq mm0, mm1
movd ,mm0
inc eax
psrlq mm0, 32 //carry
loop1_Cmp:
cmp eax,dword ptr //leftLen
jb loop1
movd ,mm0
//outLoopInit:
mov ecx,1 // i=1;i<rightLen
mov eax,dword ptr //leftLen
lea esi,
lea ebp,
jmp outLoopCmp
outLoop:
add ebp,4
pxor mm0,mm0
movd mm2,
mov eax,dword ptr //leftLen
neg eax
jmp innerLoopCmp
innerLoop:
movd mm1,
movd mm3,
pmuludq mm1,mm2
paddq mm0, mm1
paddq mm0, mm3
movd ,mm0
psrlq mm0, 32 //carry
inc eax
innerLoopCmp:
jnz innerLoop
movd ,mm0
inc ecx
outLoopCmp:
cmp ecx,dword ptr //rightLen
jb outLoop
thisExit:
pop ebp
pop edi
pop esi
emms
ret
}
}
无心人
发表于 2008-4-11 11:27:59
不起作用的原因是现代CPU乃乱序执行的
liangbch
发表于 2008-4-11 11:50:10
我有2台电脑,PIV 和 PM,我在优化程序的时候总是要在2台电脑上测试。某些优化手段在一台电脑上效果很明显,但在另外型号的电脑上可能不明显。现在总结一下这2台电脑的差异。
PM ADC指令相对较慢,减少ADC指令,提速效果明显,而PIV 则不明显。
PM 内存子系统相对较慢,减少内存写提速效果明显,而PIV 则不明显。
PM 指令并行执行的较差,减少指令条数提速效果明显,而PIV 则不明显。
PIV SSE2 指令中访问 128bit寄存器的指令速度很快,而PM则非常慢,用128bit寄存器优化大数乘法,速度不升反降。
无心人
发表于 2008-4-11 11:53:59
PM类似现在Core核心
但属于Core一代
PM的SSE2执行单元少
且其他执行单元少
但解码单元多