无心人 发表于 2008-4-2 11:57:47

还没测试呢
别说这么多话
我只是猜测

liangbch 发表于 2008-4-3 09:06:35

我的建议:

我的打算,编写一个程序,给出 基为 2^30 与基为 2^32 的速度对比,具体方法如下。

1.数的长度采用15×32=480bit。
2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序,写一个480 bit * 480 bit的 SSE2指令 MM 寄存器版,完全循环展开,无循环,无跳转指令,共需15×15共225次 32bit 的乘法。(已经证明,这种算法是最快的版本SSE2指令中最快的版本。

3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序,写一个480 bit * 480 bit的 ALU版,完全循环展开,无循环,无跳转指令,共需15×15共225次 32bit 的乘法。(已经证明,这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。

4.将480bit展开为16个DWORD,每个DWORD表示30bit(即基为2^30),写一个ALU版本的程序,共需16×16=256次乘法。
5.将480bit展开为16个DWORD,每个DWORD表示30bit(即基为2^30),写一个SSE2指令MM寄存器版本(采用32bit乘,64bit加)。共需16×16=256次乘法。
6.将480bit展开为16个DWORD,每个DWORD表示30bit(即基为2^30),写一个SSE2指令XMM寄存器版本(采用128位寄存器,充分发挥SSE2指令优势)。

至于和基为2^28的速度对比,如果gxq愿意的话,可参照如下形式。
1.数的长度采用14×32=448bit。
2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序,写一个448 bit * 448 bit的 SSE2指令 MM 寄存器版,完全循环展开,无循环,无跳转指令,共需15×15共225次 32bit 的乘法。(已经证明,这种算法是最快的版本SSE2指令中最快的版本。

3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序,写一个448 bit * 448 bit的 ALU版,完全循环展开,无循环,无跳转指令,共需14×14共196次 32bit 的乘法。(已经证明,这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。

4.将448bit展开为16个DWORD,每个DWORD表示28bit(即基为2^28),写一个ALU版本的程序,共需16×16=256次乘法。
5.可根据需要写1个或者几个SSE2 指令的版本。

几点说明,基准程序(采用基为2^32的版本),公开源代码。其他 基为2^30或者2^28的程序,可不公布源代码。

无心人 发表于 2008-4-3 09:14:22

不行的
不能完全循环展开
那只是用于小数字的算法
如果你想基于真实环境
请写一个能用于从1-4096bit都能正确工作的版本
可不考虑结果清零过程
结果清零由外部函数完成
我可提供个高于4GB / s的结果清零函数

gxqcn 发表于 2008-4-3 09:23:51

为了达到实用之目的,
还是不固定乘数的bit长度的好,但可事先约定其上限,以方便算法优化。

无心人 发表于 2008-4-3 09:29:21

//双字串清零,提高了速度,达到< 2 Clock / DWORD
void AsmMemZero(unsigned long * p, unsigned long t)
{
    __asm
    {
    mov ecx, t
    cmp ecx, 0
    jeAsmMemZero3
    mov eax, dword ptr
    mov ebx, 0
    test eax, 15 //不是16字节对齐的执行下面的语句
jeAsmMemZero4
    mov edx, eax
    shr edx, 4
    shl edx, 4
    cmp edx, eax
    jeAsmMemZero4
    add edx, 16
    sub edx, eax
    shr edx, 2
    sub ecx, edx
AsmMemZero7:
    mov , ebx
    add eax, 4
    sub edx, 1
    jne AsmMemZero7
    cmp ecx, 0
    jeAsmMemZero3
AsmMemZero4:
    mov ebx, ecx
    shr ebx, 2
    mov edx, ebx
    shl ebx, 2
    cmp ebx, 0 //是否不足16字节
je AsmMemZero6
    sub ecx, ebx
    mov ebx, ecx//保留末尾的不足16字节的部分
mov ecx, edx //循环的次数
pxor xmm0, xmm0
AsmMemZero1:
    movntdq , xmm0 //t较小用movdqa
    add eax, 16
    loop AsmMemZero1
    cmp ebx, 0
    je AsmMemZero3
    mov ecx, ebx
AsmMemZero6:
    mov ebx, 0
AsmMemZero2:
    mov , ebx
    add eax, 4
    loop AsmMemZero2
AsmMemZero3:
    sfence
    emms
    }
}

liangbch 发表于 2008-4-3 10:09:26

to gxq 就其应用而言,不固定长度是必须的。但这里我 主要想测试/展示一下这几种做法的速度之比,及理论最佳速度。如果采用不固定长度,可能会使用许多技巧,如循环展开等,使得比较不公平。

to 无心人,清0不是必须的,这样反而浪费时间。

   看可一下你的代码,伪代码大抵是这样的。
   for (i=0;i<n;i++)
   {
   UINT64 c=0;               
   UINT64 p;
   for (j=0;j<n;j++)
      {
         p=left[ i ] * right;
         p+=c;
         p+=result;
         result=p 的低32bit;
         c= (p>>32);      
               
      }
   }
    总共需要n*n次操作,每次操作包括,一次32bit * 32bit 乘法,2次 64bit和 32bit 的加法。这种做法,需要事先清空result.

    将算法作如下修改,就不需要清空result,而且在第一趟计算中,不需对result[ i ]累加,这样节省了不少运行时间。
   其实,我的96楼的程序就是这么做的,不知你为什么没有采用这种做法。

   //第一趟,不需和result[ i ]累加      
   c=0;
   for (j=0;j<n;j++)
   {
         p=left * right;
         p+=c;
          result= p的低32bit;
            c= (p>>32);      
}
   result=c;


   for (i=1;i<n;i++)
   {
   DWORD c=0;               
   UINT64 p;
   for (j=0;j<n;j++)
   {
         p=left[ i ] * right;
         p+=c;
          p+=result;
          result= p 的低32bit;
             c= (p>>32);      
   }
   result=c;
   }

}

无心人 发表于 2008-4-3 11:45:41

//双字串清零函数最新版本
//已测试比前版速度快
//已测试长度越大,比ALU指令越快
//应该总假定是双字串
void AsmMemZero(unsigned long * p, unsigned long t)
{
    __asm
    {
    xor eax, eax
        cld
        mov edi, dword ptr
        mov edx, t
        test edx, 0xFFFFFFFF
        je exit0
        test edi, 15//是否16字节对齐
        jeAsmZero1
    mov ecx, edi
        and ecx, 0xFFFFFFF0
        add ecx, 16
        sub ecx, edi//得到需要双字复制部分,要和edx比较谁大
    shr ecx, 2 //转换为双字长度
        mov ebx, ecx
        cmp ecx, edx
    jaAsmZero2//不足,转尾处理
        rep stosd
    sub edx, ebx
        je exit0//是否刚好
AsmZero1: //16字节对齐
        mov ecx, edx
        shr ecx, 4
        je AsmZero2//是否不足16字节
    pxor xmm0, xmm0
AsmZero11:
        movdqa , xmm0
        add edi, 16
        sub ecx, 1
        jne AsmZero11
AsmZero2:
        mov ecx, edx
        and ecx, 15
        rep stosd
exit0:
        sfence
        }
}

无心人 发表于 2008-4-3 11:47:23

谢谢你的提醒
我会修改的
========
顺上刚测试的清零函数共享

无心人 发表于 2008-4-8 20:43:46

考虑一次乘4个的可能性
如果有效率提高
是否说明比你们算法好?
至少那个长加你们可能就无法超越吧
毕竟32位是系统自动规整的

liangbch 发表于 2008-4-8 22:16:53

原帖由 无心人 于 2008-4-8 20:43 发表 http://images.5d6d.net/dz60/common/back.gif
考虑一次乘4个的可能性
如果有效率提高
是否说明比你们算法好?
至少那个长加你们可能就无法超越吧
毕竟32位是系统自动规整的

   我准备写3个基为 2^32 的版本, 3个基为 2^30的版本, 总体说来,后三者一定比前三者快,并且公布前三者的代码(后3者的代码将在适当的时候公开)。
   你等着看好消息吧,看看我的版本可比你的版本快多少。
页: 1 [2] 3 4 5 6 7
查看完整版本: 大数运算基选择测试