|
[分享]具偵錯能力的帶符號快速加法電路之設計
好的,我去找来看看先。 不是倍数也没有关系,比如512个线程计算一个300位的加法,那么让多出的212线程闲着好了,虽然没有最大限度利用GPU性能 用原始数据自行对齐?这个怎么做?刚学CUDA... |
|
[分享]具偵錯能力的帶符號快速加法電路之設計
并行加法上,借鉴Comba这个保留进位的思路,我想出一种不太完美的解决办法。 其实并行加法需要解决的问题就是carry往哪放的问题,高位计算是需要低位的进位才导致了无法并行。那么如果能把进位结果保存在当前位上,这个问题就解决了。比如计算 999 + 1: 9 9 9 + 0 0 1 ======== 9 9 0 + 1_0 <= 加上进位 ======== 9 0 0 + 1_0 <= 又进位了,这是最棘手的问题 解决办法,进位后把结果直接保留在该位上: 9 9 9 + 0 0 1 ========== 9 9 10 其结果上 9×100 + 9×10 + 10 = 1000 是一样的。 这个理论很简单,放到GPU中就是(假设计算 c[n] = a[n] + b[n] ): 1. 并行计算 c = a + b,将进位结果存入u 当然这样c[i]保存数的范围会变成一个可变值,这会带来很多不方便的地方,我在考虑是否运用超前进位加法器的思路,当需要统一范围的c[i]时,有选择的在尽可能少的循环次数内把c[i] = c[i] + u[i-1]这里的进位给消除掉。这样兼顾了运算速度并且其他算法实现也会简单点(至少考虑乘法计算的溢出时少了一个不确定因素)。 再次感谢R大的资料,顺着参考资料、关键词搜索容易很多 |
|
[分享]具偵錯能力的帶符號快速加法電路之設計
顺着这个 L2_Notes.pdf 說的找了一下,收获还不错。虽然并行加法上思路还不是很清晰(看了几个方法,里面讲的Carry-Save Addition、carry look-ahead addition似乎都是针对有限位数计算时进位的优化,感觉这么复杂的逻辑拿到GPU上不一定特别有用),不过找到个不错的并行乘法 原文链接:Comba multiplication By Paul G. Comba 原理如下,设下划线表进位,我们一般做乘法: 2 3 x 8 9 ======= 2_0_7 1_8_4 ======= 2_0 4 7 Comba的计算方式:(保留进位,算完再加) 2 3 x 8 9 =========== 18 27 16 24 =========== 2 _0 _4 _7 这个方法提出已经是20多年前了,后人还做了一个更好的改进。首先把两个数写在两张纸的角落,倒转其中一张纸和写个另一张纸对接,比如23倒转后是32,然后如下操作: | |3 2 `---- ----. => 3*9 = 27 => 2047 8 9| / | | / | <________/ | | / carry 2 | |3 2 / | `---- / | ----. => 2 + 3*8 + 2*9 = 44 8 9| / | | / | <________/ | | / carry 4 | |3 2 / | `---- / | ----. => 4 + 2*8 = 20 8 9| | 这样做的话可以减少乘法次数,对于两个大数相乘优势很大 顺便贴两个我找到的资料,都在这里汇总一下好了: Carry-Save Addition www.ece.tamu.edu/~sshakkot/courses/ecen248/csa-notes.pdf Conditional-Sum Addition Chap8 - Conditional Sum Adders |
|
[分享]具偵錯能力的帶符號快速加法電路之設計
这个运算上,很多大数库也是如此处理的。比如libtommath中,用一个单独的变量 sign 表示大数的符号位,假设a,b大于0,这样一来: (a + b) or (-a + -b),调用原子级加法(不管符号位,直接相加两个数的数字部分),计算结果c的符号与a相同, (-a + b) or (a + -b),调用原子级减法,c符号设为 |a|, |b| 中较大数的符号。 这样的优势在于求负数只需换一下 sign 就行了,而不用把整个数组给跑一遍。 |
|
|
|
[讨论]关于并行大数加法的,遇到困境了...
这个实现起来可能不是很方便,因为要是为了进位去操作别的线程负责的数据块(比如线程i为了进位,按你这个思路可能会去修改i+1、i+2、i+3...这些数据块),这个需要涉及读写同步的问题,因为可能 i+1 的线程刚计算出结果,还没写入 c[i+1] 里面,而低位线程i负责计算的 c[i] 发生进位,提前 c[i+1]++,这样数据就乱套了。 多线程限制其实也很多 |
|
[公告]试办看雪学院密码学版期刊 (杂志)
同上 比如XX加密算法为什么要如此设计,如何破解、攻击XX算法这样的文章(直接看RSA攻击的文章感觉还是太吃力了,想从前人破解其他算法的方法中吸取经验又不知如何下手,所以可否弄点针对简单的常用算法破解文章给我们科普一下) |
|
[讨论]关于并行大数加法的,遇到困境了...
感谢回复。这个方法我也想过,首先每个线程分别计算 a[i] + b[i],结果存入c[i],然后保存每一位的进位情况,再把进位并行的加回去(如果进位部分用串行从低位循环加上去,第一步的拆分就没有意义了)。 问题是不一定刚好结果是 8888888888 + 11111111110 这样不会出现二次进位的结果,最糟糕的莫过于: 假设每个线程负责竖着将每一位相加: 嗯,分段计算可能是没有办法的办法。主要是怎么分段的问题,分过细了没有意义(比如一个n=2048的a[n],按4分段计算的话,段间还是需要循环512次),但是分太粗了又没有有效利用起GPU的计算能力(比如按64分段的话,只有32个线程在同时工作,在一些高档显卡上能并行的线程数远远大于这个) 而且本来设计上就利用了32位处理器计算的特点,a[n] 数组使用4字节的DWORD类型,这样计算 c[i] = a[i] + b[i] 的速度有所提升不说,进位处理的次数也会减少到1/4(相对于用BYTE存储来说)。 我对这个并行加法比较纠结的原因是因为加法是后面大多数计算的基础,这个速度上有细微提升都会对整个大数计算带来很大帮助。 希望大家畅所欲言 |
|
[讨论]有人研究过用GPU做大数因式分解的课题吗?
感谢提供资料。正愁没有并行大数乘法的资料,这个可以参考下 看样子他们也刚开始往CUDA上移植,1.43中都还没有cuda的代码。 1.44代码还未正式发布,需要Nvidia's CUDA runtime (version 2.3),rockinuk版主那个错误可能是cuda版本过低引起的。传份svn上拖的源码到本地 |
|
[讨论]有人研究过用GPU做大数因式分解的课题吗?
嗯,你说的这个方法也可以考虑,先做U32范围内的计算。 GPU上的大数计算我来想办法,实再不行我打算把libtommath移植到CUDA上,这个库比GNU MP简单些,而且没有类似于GPL这样的License。 |
|
[讨论]有人研究过用GPU做大数因式分解的课题吗?
Parallel LDPC Decoding on GPUs Using a Stream-Based Computing Approach 这个好像Google就能下到,不用刻意去花$34... |
|
[原创]Merry Christmas and Happy New Year!
Merry Christmas! |
|
[求助]求助,这个应该是什么算法?[解决 ]
看0x61C88647这个,有点像QQ的东西,移位稍微有点变化。具体可以看这个帖子的2楼: http://bbs.pediy.com/showthread.php?t=2916 或者 http://www.linuxboy.net/wordpress/?p=36 |
|
[讨论]有人研究过用GPU做大数因式分解的课题吗?
我也觉得效率的好坏在于算法。 CUDA虽然能一定程度上提升计算性能,不过如果不是用的NV的Tesla,对于那种天文数字般的计算量还是难以承受的。 目前还只能熟悉下CUDA的环境,对算法的改进还要等高人分析分析再说 |
|
[求助]哪位大侠知道如下密码的加密方式或有什么方法识别?
是的。第一种确实是Linux中shadow的MD5,以$1前缀开头的使用这种方式。salt是从$1到最后一个$之间的字符,比如这个是 $1$xNeXk5jE$rLkEwte2.sFTGlsqQox/g1 后面黑色部分就是crypt()的结果。 这种密码可以用穷举来破解(当然有个好字典也行),具体方法是调用Linux自身的libcrypt库来正向计算加密结果,然后比对计算结果是否为你需要的散列值。例如要破解 $1$4rIWwSl1$29U2moXvLlESsRoLSUTOA0 - 654321 这个简单的密码: #include <crypt.h> 第二个不像des的。也许是变种,我只见过类似 a44L3wQdaePiI 这样的,以前两个字符为salt,整个字符串为crypt()结果,这个早期的Linux中用得比较广泛。虽然长度满足,但你这个$1开头的,还真不好说。 无论哪种加密都可以用穷举来攻击,只不过速度很慢。DES的还好点,我在一台Xeon 4核(2.0GHz)的服务器上,每秒能算近10W个密码。不过MD5密码能跑到3000个每秒就已经是极限了,我完全没有耐心等他跑完... |
|
[讨论]有人研究过用GPU做大数因式分解的课题吗?
说是讨论其实是LS版主发的一篇论文,不过大家都被这篇论文吓着了,看目录都觉得很吓人... 大整数因子分解问题的研究 这个太高深了,有兴趣你可以搜一份论文下来看看... |
|
|
|
|
|
[分享]Algorithmic Number Theory--Lattices, Number Fields, Curves and Cryptography
RAR最大5M,打包下载也不是很方便。 反正文章也不是都要一次下完,挑自己感兴趣的先下一两个就好。这样下载总比到EI上搜来得方便 这是本书啊,确实要从头到尾下一遍了... |
操作理由
RANk
{{ user_info.golds == '' ? 0 : user_info.golds }}
雪币
{{ experience }}
课程经验
{{ score }}
学习收益
{{study_duration_fmt}}
学习时长
基本信息
荣誉称号:
{{ honorary_title }}
能力排名:
No.{{ rank_num }}
等 级:
LV{{ rank_lv-100 }}
活跃值:
在线值:
浏览人数:{{ visits }}
最近活跃:{{ last_active_time }}
注册时间:{{ user_info.create_date_jsonfmt }}
勋章
兑换勋章
证书
证书查询 >
能力值