大数运算基选择测试

liangbch

采用2种不同的基,计算大数乘法的速度测试到此应该告一段落了。对计算大数乘法来说，何种表示法更优，答案已经水落石出。这里我将对所有7个版本，2种不同的CPU的运行速度给出一个总结，以利于日后参靠。

1) 先给出这9个版本在PIV2.6G 和 PM1.7G的运行速度：

函数                         PIV2.6                         PM1.7
UInt480x480_ALU                1244.900ms                788.635 ms
UInt480x480_ALU2                1216.185ms                 889.310 ms
UInt480x480_MMX                 481.395ms                 761.610 ms
UInt480x480_base30_ALU        1222.585ms                681.810 ms
UInt480x480_base30_MMX        385.310ms                        568.430 ms
UInt480x480_base30_SSE2        524.795ms                        840.360 ms

UInt480x480_yaos                683.235ms                        1053.610 ms
UInt480x480_MMX2                693.265ms                        863.055 ms
UInt480x480_MMX3                585.590ms                        798.775 ms

2.这几个函数的简要说明：
   前6个函数均为使用完全循环展开的版本，代码量较大，源代码采用程序生成。
其中以包含ALU字样的函数不是用任何MMX，SSE2指令。包含MMX字样的使用SSE2指令，
累加部分使用MMX64bit寄存器。包含SSE2只用的主要使用SSE2 128bit 计算乘法何累加。
  1) UInt480x480_ALU2是最普通的版本，使用传统的乘法，逻辑类似于GMP种的basecase乘法
  2) UInt480x480_base30_MMX 采用和UInt480x480_ALU2同样的逻辑结构，只是使用SSE2指令
做乘法和累加。
  3) UInt480x480_ALU 用的我自创的另一种乘法结构，相对于UInt480x480_ALU2，
平均每次乘法少了一次ADD指令，较UInt480x480_ALU 具有更少的内存写，而增加了相应
的内存读指令。
  4) UInt480x480_base30_ALU的逻辑结构和UInt480x480_ALU 类似。
  5) UInt480x480_base30_MMX 是UInt480x480_base30_ALU 的MMX寄存器版本的实现。
  6) UInt480x480_base30_SSE2是UInt480x480_base30_ALU的使用128bit寄存器的SSE2版本的实现。
  7) UInt480x480_yaos，UInt480x480_MMX2，UInt480x480_MMX3 有的是没有使用任何循环展
开技术的版本，这几个函数的在计算乘法时的逻辑结构基本相同。相对而言UInt480x480_yaos
不够优化且需要实现对目标buffer清零。UInt480x480_MMX3 是在UInt480x480_MMX2 基础上进
一步优化而成，内循环部分比UInt480x480_MMX2 少了一条指令。

3.在同一台计算机上不同版本的性能对比。
  在PIV电脑上，很显然，所有 MMX或者SSE2的版本大幅领先于ALU版本。UInt480x480_MMX 相
对于它的ALU版本，速度竟然提升至%250左右。提速效果煞是惊人.
  基为$2^30$的版本UInt480x480_base30_MMX比基为$2^32$的版本 快了25%左右，说明$2^30$为基的
MMX版本比$2^32$为基的版本更有优势。
  基为$2^30$的版本 和 相应的基为$2^32$的版本UInt480x480_base30_ALU相比，速度基本相同，
几乎没有效果。

   在PM电脑上，很显然，所有MMX均领先于ALU版本，但提速效果不太明显。UInt480x480_MMX
相对于 UInt480x480_ALU2，仅仅提速1/6左右。SSE2的版本速度最慢，慢于其他所有使用循环
展开的的版本，看来PM 上的SSE2指令确实性能很差。
  同为MMX版本，基为2^30的版本比基为2^32的版本提速大约1/3。在PM上。两种不同逻辑结构
的ALU版本，我的做法比传统的做法快了大约1/8左右。原因可能是(1) 我的PM电脑内存子系统
速度较慢，减少内存写具有明显的效果。2)每个循环步骤较少了1条ADC指令。
  基为2^30的ALU版本(UInt480x480_base30_ALU)，又比同样逻辑结构的ALU版本(UInt480x480_ALU)
快了大约1/6。这和ADC指令的减少有密切关系。

4.同一段代码在不同CPU上的性能对比
  由于PM和PIV架构不同，故虽PM 1.7的主频低于PIV2.6，但对于ALU版本要快于PIV，以UInt480x480_ALU
为例，PM的ALU版本要比PIV快57%。而对于MMX版本则慢于PIV，以UInt480x480_MMX 为例，PM的
MMX版本的速度只及PIV的63%。

5.使用普通的循环的版本的速度对比：
  对于 UInt480x480_yaos，UInt480x480_MMX2，UInt480x480_MMX3 这三个使用普通循环形式的版本，
UInt480x480_MMX3 速度最快，这与这个版本的内循环中指令数较少有关。值得注意的是UInt480x480_yaos
这个版本在PM上的表现极差，比普通的ALU版本还慢，这可能与这个版本内存写指令较多有关，因为我
的PM内存子系统相对较差。

无心人

有一个比较你没公布吧
就是基$2^30$的非展开版本和基$2^32$的非展开版本的比较

还有，俺也说了，乘法存在四路并行算法

无心人

GMP4.2.2 P4目录中的参数
#define MUL_KARATSUBA_THRESHOLD          23
#define MUL_TOOM3_THRESHOLD             137


=======================================
可以看到基础运算能计算的双字（23个）是很大的
你认为基础运算都展开么？

liangbch

我没有给出基为$2^30$可计算 乘数/被乘数长度为任意值的版本。当乘数长度大于480bit时，我现有的逻辑不能解决这个问题，逻辑上需要做一些变动。但是，采用我自创的优化算法，这种改动引起的性能的降低极为有限，估计性能下降最多不超过3%，在PIV CPU，基为$2^30$的ALU版本可能稍稍慢于基为$2^32$ ALU版本。但MMX的版本一定可以快于基为$2^32$的版本。如果在PM上，这种优势就更加明些了。
   一个充分优化的基为$2^30$的版本代码很复杂，我暂时不想实现它，基于我以前的经验，他一定可以胜出。

liangbch

关于下一阶段的任务，我想我们可以对二进制大整数加法做一个测试。看看基为 $2^30$的版本相对于 基为 $ 2^32$的版本速度如何。这次我准备公开所有源代码。

无心人

那怎么能说这个题目已经得到结论了呢?

循环状态下，不存在跨乘法循环的加法的优化了
或者说，展开下，你一次能加16个2^30的乘法结果
循环下，你做不到了啊

所以我并不认为，是稍微快点的结论
如果不改变循环结构，则应该是慢点
如果改变循环结构，则程序应该很复杂很复杂
会遇到寄存器极度缺乏问题
如果是64位状态下，也许你能做到一次加16个结果
但32位状态下，很不好做吧

无心人

加法的那个测试请你转移到我开的加法帖子上去做
那里有我的四路优化代码

liangbch

原帖由 无心人 于 2008-4-14 13:15 发表


那怎么能说这个题目已经得到结论了呢?

循环状态下，不存在跨乘法循环的加法的优化了
或者说，展开下，你一次能加16个2^30的乘法结果
循环下，你做不到了啊

所以我并不认为，是稍微快点的结论
如果不 ...

   解决这些问题并不会很复杂，只是你现在想不到而已，实际上，这些问题已经在我的基于10^9的大数乘法中实现，当乘数长度较大时，较乘数长度为480bit，而额外付出的代价也非常小。

无心人

那期待看到你的测试结果

gxqcn

今天终于完成了计划中的两个教程的编辑工作，对论坛发帖具有指导意义，也算得上是功德无量啊。。。

刚下载了 liangbch 在 38# 的附件（可能是为了管理需要，管理员等无须购买即可下载），
帮着测试一下，这是在我家里电脑上运行的数据如下：

原 binMulTest.exe 6个版本的速度对比：
Test function: UInt480x480_ALU(..) 1000000 times...
Elapsed time: 838.995 ms

Test function: UInt480x480_ALU2(..) 1000000 times...
Elapsed time: 1160.110 ms

Test function: UInt480x480_MMX(..) 1000000 times...
Elapsed time: 447.220 ms

Test function: UInt480x480_base30_ALU(..) 1000000 times...
Elapsed time: 643.535 ms

Test function: UInt480x480_base30_MMX(..) 1000000 times...
Elapsed time: 343.965 ms

Test function: UInt480x480_base30_SSE2(..) 1000000 times...
Elapsed time: 386.780 ms


重新编译 binMulTest.exe，5个基同为2³²的版本的速度对比：
Test function: UInt480x480_ALU(..) 1000000 times...
Elapsed time: 797.570 ms

Test function: UInt480x480_ALU2(..) 1000000 times...
Elapsed time: 1116.610 ms

Test function: UInt480x480_MMX(..) 1000000 times...
Elapsed time: 446.370 ms

Test function: UInt480x480_MMX2(..) 1000000 times...
Elapsed time: 780.240 ms

Test function: UInt480x480_yaos(..) 1000000 times...
Elapsed time: 599.450 ms

本想将自己的代码加进去同台竞技，想看看与各位有多大的差距；
怎奈有太多的地方需修改，只好作罢。。。