大数运算基选择测试

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