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.
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:
- Addition / Subtraction.
- Multiplication of large numbers by small numbers.
- Division of large numbers by very small numbers (e.g. 2).
- Base 2 Log.
- Base 2 Power.
- Comparison of two or more large numbers (Min/Max).
- No involvement whatsoever of prime numbers.
- The algorithm is specifically designed not to be memory intensive since the performance hit of memory access is more than that of some smart on-the-fly calculations. Nevertheless, if memory access were to improve, the algorithm could benefit reasonably.
I have optimized the code as much as possible and profiling now shows only two bottlenecks:
- Calculating base 2 Log for such large numbers.
- Checking for pre-defined patterns of binary digits in these numbers. This is because the only way to access the BigInteger underlying data is by first using ToByteArray rather than in-place operations. Also, operating on byte-sized chunks does not help performance.
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.
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.