数学研发论坛

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

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

  [复制链接]
 楼主| 发表于 2020-2-15 11:56:37 | 显示全部楼层
关于汇编,我决定还是采用 MASM,主要受这个影响:http://tieba.baidu.com/p/4827889049

经过几天的测试,终于在 VS2019 里编译通过了一小段 x64 汇编。

可以单步调试,
可以实时观察寄存器值的变化,状态标识符状态的变化,内存变量的值,
可以实时查看反汇编代码,实时的完整的内存数据变化,

这些对于开发都是非常有帮助的(不知道 nasm 是否具备上述特点),是我所看重的。

如果大家有关于 MASM 汇编的资料(pdf 学习文档,或含 asm 代码的参考文档),欢迎提供,谢谢!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-15 14:28:13 | 显示全部楼层
关于cmake和nasm用法,你看看这篇文章。https://blog.csdn.net/sxc1989/article/details/80637245,如方便的话,可以windows + cmake + nasm
试一下。我先试一试linux环境。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-15 16:34:26 | 显示全部楼层
刚刚搜索了一些 MASM 的资料,
又发现一个严重的问题:
似乎 MASM 的 simdRegister 支持 XMMWORDYMMWORD 类型,但却没提到 ZMMWORD 类型,
参见:https://docs.microsoft.com/zh-cn ... erence?view=vs-2019
是不是说,MASM 暂不支持 AVX512 指令?

点评

我在测试的 .asm 文件里加了一行:VPMULLQ zmm17, zmm18, zmm19,结果编译成功,说明 MASM 是支持 AVX512 指令的,这是一个好消息!  发表于 2020-2-16 10:39
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-15 17:07:02 | 显示全部楼层
建议使用nasm,便于将来发布Linux版本,nasm是支持AVX512指令的。vc是支持nasm的。至少,从vs2005就支持了,见《将NASM汇编器集成到Visual Studio中》https://blog.csdn.net/dj0379/article/details/17243407
《关于VS2019使用NASM编译汇编文件》,见 https://blog.csdn.net/mmmsss987/article/details/103567092
单独的汇编文件,一样可以调试。在VC中,release模式和debug模式下调用nasm的命令参数可以是不同的,在Debug方式,需要调试程序,需要加上-g选项。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-15 22:40:29 | 显示全部楼层
试了试在linux下用nasm编译后的调试问题。我发现,如果编译一个单独的asm文件,使用"-gdwarf" 或者 "-g -F dwarf", 可以使用gdb调试,可以在汇编文件中打断点。如果asm和c文件分别编译,最后链接在一起,则不能在汇编文件中打断点,单步命令不能进入到汇编编写的函数内部。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-16 10:45:28 | 显示全部楼层
谢谢 liangbch!

我刚刚在测试的 .asm 文件中,加了一行代码:VPMULLQ zmm17, zmm18, zmm19,编译通过了,
说明 MASM 是支持 AVX512 指令的(我的 CPU 还不支持,所以无法运行测试),这是一个好消息!

当前的首要目标是希望能加快开发进度,能单步调试是我所看重的,
所以,会优先选择用 MASM 写汇编。

点评

AVX512好象没有64位乘64位且得到128位结果的指令  发表于 2020-2-16 11:31
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-16 11:07:08 | 显示全部楼层
看了下nasm的文档,NASM和MASM语法差别不太大,如果代码量不大的话,将masm的代码修改为nasm,代价并不大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-16 11:33:12 | 显示全部楼层
64位 * 64位 的 整数乘法指令实在是匮乏!

翻遍指令集表,SIMD 除了上述提到的 VPMULLQ 指令,再无其它!
而 VPMULLQ 只能保存 128-bit integers 中的低 64 bits,
因无法获得结果的高位数据,所以并不太适合大整数运算。
即便是这么半残的指令,还是需 AVX512DQ 支持才行(配置低的就不用指望了)。

这也是我一直想开发 x64 版的 HugeCalc,但迟迟未动的原因。

好消息是 SIMD 系列还有一组指令可能有助于大整数运算,
这就是 AVX512IFMA52,不过它是 52-bit * 52-bit --> 104-bit 的,
要想用到它,需要点额外技巧。


既然已说到这里,我就提一下 HugeCalc 的核心部分。

在之前的 x86 版里,十进制内核采用 \(10^9\)、十六进制内核采用 \(16^7\) 的基数,
这是兼顾空间效率与输出效率的结果。

在新的 x64 版中,大致框架为:
  1. namespace hugecalc
  2. {
  3.     // 二进制内核
  4.     namespace bin
  5.     {
  6.         class int_t;   
  7.     }
  8.    
  9.     // 十进制内核
  10.     namespace dec
  11.     {
  12.         class int_t;
  13.     }

  14.     // 可能不再提供:高精度计时器、任意进制转换器
  15. }
复制代码


建议用户用如下代码简化:
  1. namespace hc    = hugecalc;

  2. namespace hb    = hc::bin;
  3. namespace hd    = hc::dec;

  4. using hb_int_t  = hb::int_t;
  5. using hd_int_t  = hd::int_t;
复制代码


其中,hb::int_t  内部采用 48 位(基数=\(2^{48}\)),hd::int_t  内部采用 15 位(基数=\(10^{15}\)),
这里的“位”(digit)是与进制相关的,不再是无法统一的慨念“bit”
(它们现在可以拥有相同的函数 digits() 来获取大整数的“位”),
之所以采用上述大小的 radix,也是在指令集适配、空间效率,及输入输出转换效率上平衡的结果。

输出支持:bin(二进制)、oct(八进制)、hex(16进制)、dec(十进制)
分节长度:十进制,3位、10位或不分节;其它,2位、4位或不分节
(其中10位一分节,是为了格式化输出超长字串,比如大数阶乘、\(\pi\) 等)

点评

因为,dec 内核下无法做到满进制,为了让 bin 内核与之相近,所以也采用了非满进制的形式。之所以抛出这个话题,也是想进一步评估。也许,我的 bin 内核也应该直接做到满进制的。  发表于 2020-2-24 10:07
GMP内部格式是满进制,32位模式,进制为$2^32$, 64位模式,进制为$2^64$. 如果核心部分使用$2^48$,则效能不占优势。不考虑其他因素,乘法性能只有$2^64$进制的56%.  发表于 2020-2-24 09:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-18 11:41:06 | 显示全部楼层
有两个问题请教大家:

  • gmp 的 x86 与 x64,内部的基数分别是多少 bits?
    相同的计算量(比如算同一个数的 Fibonacci), 两者的速度比大约是多少?

  • 迁就于一些指令集,可能需要数据进行 16、32 甚至 64 字节对齐,
    在 C++ 中,可有什么优雅的写法,new(或用智能指针) 出一组对象,并使之地址 64 字节对齐?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-18 13:45:06 | 显示全部楼层
C++11里面添加了alignas可以试用一下:
https://zh.cppreference.com/w/cpp/language/alignas
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-10-21 18:27 , Processed in 0.124808 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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