利用GPU来加速BigInteger的计算 [英] Using GPU to speed up BigInteger calculations
问题描述
我几乎与一种算法,处理一些非常大的整数(左右的2次幂亿的顺序)进行。这需要一个16核心服务器上的一对夫妇的高度并行code小时绰绰有余内存,因为该算法是不占用大量内存。我使.NET 4中使用BigInteger类的。
I am almost done with an algorithm that processes some very large integers (around the order of 2 raised to the power 100,000,000). This takes a couple of hours of highly-parallel code on a 16 core server with more than adequate memory since the algorithm is not memory intensive. I make use of the BigInteger class in .NET 4.
该算法的细节不是重要的,但对于上下文,下面是对这些整数执行的操作和算法的某些显着特征的pretty的详尽列表:
The specifics of the algorithm are not important but for context, following is a pretty exhaustive list of operations performed on these integers and some salient features of the algorithm:
- 在加法/减法。
- 大量小的数字相乘。
- 大量由非常小的数字(例如2)。 司
- 在基地2登录。
- 在基地2电源。
- 在两个或更多的大量的比较(最小值/最大值)。
- 素数没有参与任何责任。
- 该算法被专门设计应不存储器密集型的,因为存储器访问的性能命中多于一些聪明上即时计算。然而,如果存储器存取是提高,该算法可以合理受益。
我已经优化了code尽可能和分析现在显示只有两个瓶颈:
I have optimized the code as much as possible and profiling now shows only two bottlenecks:
- 在计算基地2日志中这样大的数字。
- 检查二进制这些数字位数pre-定义的模式。这是因为访问的BigInteger底层数据的唯一途径是通过首先使用的toByteArray而不是就地操作。此外,在字节大小的块操作不会帮助提高性能。
考虑到内存访问和登录操作,我开始思考GPU和我是否可以分担一些工作有效。我不是很了解GPU的不同之处在于它们的浮点运算进行了优化。
Considering memory access and Log operations, I started thinking about GPUs and whether I could offload some of the work effectively. I know very little about GPUs except that they are optimized for floating point operations.
我的问题是,使用像GPU .NET库,我该怎么处理这样大量的GPU?我能以某种方式利用浮点优化的计算日志中如此大量的?
My question is, using a library like GPU .NET, how can I process such large numbers on the GPU? Can I somehow make use of the floating point optimizations to calculate Log for such large numbers?
寻找一个起点,形成一个战略。
Looking for a starting point to form a strategy.
推荐答案
我四处寻找在C#中的GPU工作,正在考虑Tidepowerd.com GPU.NET和CUDAfy.NET。无论Nvidia的具体CUDAfy没有(还)支持单声道,当我最后一次检查。但它们都允许的范围内,关于GPU上运行的C#合理正常看code。
I am looking around for GPU work in C# and am considering Tidepowerd.com GPU.NET and CUDAfy.NET. Both Nvidia specific and CUDAfy did not (yet) support mono when I last checked. But they both allow for for reasonably normal looking code within C# that runs on the GPU.
另外,你有没有考虑使用3D党库?有几个很不错的BigInteger库,也是开源的。 GMP是非常优秀且免费的; http://gmplib.org/ ,有至少一个C#包装(这是我所没有的经验)<一HREF =http://www.emilstefanov.net/Projects/GnuMpDotNet/相对=nofollow> http://www.emilstefanov.net/Projects/GnuMpDotNet/
Also, did you consider using a 3d party library?. There are several very good BigInteger libraries, also open source. GMP is very good and free; http://gmplib.org/, there is at least one C# wrapper (which I have no experience with) http://www.emilstefanov.net/Projects/GnuMpDotNet/
在.NET BigInteger类是不可变的。在我看来,是不是很方便。如果你有2个整数的大小(约100MB),在第三100MB BigInt有添加操作的结果。这是可以做到的方法更快,如果将例如修改两张原稿中的一个。
The BigInteger class in .NET is immutable and in my experience that is not handy. If you have 2 ints of your size (around 100MB) the Add operation results in a third 100MB BigInt. It can be done way faster if would for instance modify one of the two originals.
C = A + B means allocating 100MB for C (this is what BigInt does)
A = A + B means you no longer have the original A, but a much faster calculation
这篇关于利用GPU来加速BigInteger的计算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!