找回密码
 欢迎注册
楼主: gxqcn

[讨论] 重启大整数库 HugeCalc 的研发工作

 火.. [复制链接]
发表于 2020-2-27 21:06:06 | 显示全部楼层
关于大数核心运算(对于应GMP的mpn目录下的底层函数)的进制。我仍然认为我的设计是最好的。
即32位下使用$2^30$进制,64位下使用$2^60$(其实单从大数乘法上看,$2^62$更好,但60的因数众多,更好拆分)进制。
非满进制格式的大数,存储开销稍大些,但可实现以列为主的乘法,可对双倍精度的乘积做多次累加而不溢出。
而满进制格式的大数,只能实现以行为主的大数乘法,无法充分利用SIMD指令的优势。

一个精心设计的乘法结构可充分利用SIMD的优势,加速大数运算的速度。
若每条指令的执行时间相当,则使用AVX512指令的$2^30$进制的大数乘法,极有可能比GMP64位的版本更快。

分析
一次64位×64位的乘法,等价于4次32位×32位的乘法. 故若4个32位×32位的乘法的实现快于一个64位×64位的乘法,则32位版本的乘法可快于64位乘法。
最近完成一个示范程序,核心是做s = sum( a[ i ] * b[ j ]),实现了4个版本,包括c语言版,sse2版, avx2版,avx512版, 计算4096对儿uint32乘法的积的累加,不考虑溢出,用时为6.3至0.25微秒。

|C版本|sse2|avx2|avx512|
|6.3us|0.92us|0.41us|0.25us|

下面比较一下各个版本的执行的指令数
对说32位C版本,典型的需要5条指令,大体是这个样子。

  1. mov eax, s1
  2. mov edx, s2
  3. mul edx
  4. add ecx, eax
  5. add ebx, edx
复制代码


而我写的SSE2版本,每4次uint32乘uint32需要9条指令,平均每次乘法需要2.25条指令
AVX2版本,每8次uint32乘uint32需要7条指令,平均每次乘法需要0.88条指令。
AVX512版本,每16次uint32乘uint32需要7条指令,平均每次乘法需要0.44条指令。

附以列为主的乘法和以行为主的乘法
1.以列为主的乘法
若被乘数是s1[], 其长度是len1, 乘数是s2[], 其长度是len2
该算法计算过程为,先固定k,则p[k]= sum(s1[ i ]*s2[k-i], 0<= i< len1, 0 <= k-i<len2).

2.以行为主的乘法
若被乘数是s1[], 其长度是len1, 乘数是s2[], 其长度是len2
计算过程为,先固定k,0<=k<len2, n=s2[k], 计算p[ i+k ]=sum(s1[ i ]*n,0<= i< len1)

点评

主要的内存(cache)的"写”比“读”耗时多。另外,许多网友(忘了出处了)表示,movdqu指令用于读取内存时和movdqa没有多大区别,因此,对齐的需求可能也没有那么大。  发表于 2020-2-28 11:07
寄存器的“写”远比“读”耗时多,以列为主的同时也是利用了这一点。  发表于 2020-2-28 08:52
注,GCC的编译器很强大.我检查了下编译后的指令和直接使用汇编编程的版本相差无己。  发表于 2020-2-27 21:12
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-27 21:13:26 | 显示全部楼层
c语言版本的源程序。

  1. //假定s_len总是32的倍数
  2. uint64_t muladd_c (uint32_t *s1, int s1_len,  uint32_t *s2)
  3. {
  4.    int pass= s1_len/32;
  5.    uint64_t sum=0;
  6.    uint32_t *base;

  7.    for (int i=0;i<pass;i++)
  8.    {
  9.         base= s1 + (i*32);
  10.         for (int j=0;j<32;j++)
  11.         {
  12.              sum+= (uint64_t)base[j] * (uint64_t)s2[i];       
  13.         }       
  14.    }
  15.    return sum;   
  16. }

复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-17 11:57:25 | 显示全部楼层
写个椭圆曲线整数分解的吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-3-17 14:01:39 | 显示全部楼层
这个要待基础模块完成后,才能进行下一步。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-3-29 12:06:16 | 显示全部楼层
为了方便开发测试,我先把 dll 导出框架搭好,测试 app 写好。

hugecalc v9.0

hugecalc v9.0

"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出函数的 ID 号;其中 @ 代表 1 或 2,对应于 bin 或 dec 内核

上图即为当前的测试 app 的截图,
相比之前的,功能更强大,扩展性更强,
其中 "Arbitrary-precision arithmetic" 区按函数入参类型分类,具有更灵活的扩展性
几乎所有的导出函数都可在此框架中得以测试。

当然,该界面只是做了些基本的对齐排版,
谈不上什么美学,可能会遭到一些吐槽,
限于个人能力,就由他去吧。。。


之前一些美妙的想法,已逐步实现,比如输出模式,有
  1. // 输出格式:进制模式
  2. enum class basemode
  3. {
  4.     smart,          // 以最快的进制输出:当对象为十进制内核时,相当于 dec;否则,相当于 hex
  5.     bin,            // 强制以二进制输出
  6.     oct,            // 强制以八进制输出
  7.     dec,            // 强制以十进制输出
  8.     hex,            // 强制以16进制输出
  9.     huge,           // 带空格换行符输出(default):基于 smart,但更适合超长大数输出
  10. };
复制代码
截图上的即为 huge 模式输出的:从末尾起向前,每十位成一块加一空格(也可指定为逗号,或撇号')分隔;每十块将空格符替换成换行符,
这样的格式化输出,更利于阅读或存储。

  1. // 输出格式:分隔符
  2. enum class separator
  3. {
  4.     none,           // 不 用 分隔符
  5.     space,          // 用空格分隔符(default)
  6.     accent,         // 用撇号分隔符(单引号)
  7.     comma,          // 用逗号分隔符
  8. };
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-3-29 12:17:17 | 显示全部楼层
明天,我们要正式复工啦!

之前一直在家远程办公,抽空可以开发一下这个算法库,
通过阅读相关标准,再加上自己的实践,
很快掌握了相关知识,这就是最大的收获。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-29 13:27:18 | 显示全部楼层
gxqcn 发表于 2020-3-29 12:06
为了方便开发测试,我先把 dll 导出框架搭好,测试 app 写好。

"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出 ...


软件看起来不错,

不过我现在习惯了mathematica软件的方式,
代码能够粘贴很爽,
你的软件需要点鼠标给软件赋值(旧版本是这样,新版本不知道如何),
这点鼠标其实操作起来很麻烦的,

以前用你的软件的input窗口来过滤掉窗口里面的非数字,
现在我自己学会了正则表达式,你的软件对我来说没帮助了。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-4-9 23:05:37 | 显示全部楼层
期待新突破
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-4-14 17:51:26 | 显示全部楼层
gxqcn 发表于 2020-2-24 09:11
谢谢!非常感谢!这样,我对 x64 平台的性能有个预期目标了。

指令执行周期,64位乘法6周期,32位乘法5周期,这是基本指令差异,非常显著的了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-4-15 08:08:40 | 显示全部楼层
64位相比32位,一次乘法可获得双倍的bit数,即便周期数是 6:5,实效则为 5:3,
64位系统还有:可用寄存器丰富,传参快等优点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 04:53 , Processed in 0.049882 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表