Uso de la GPU para acelerar los cálculos de BigInteger

Question

Casi he terminado con un algoritmo que procesa algunos enteros muy grandes (alrededor del orden de 2 elevado a la potencia de 100,000,000). Esto lleva un par de horas de código altamente paralelo en un servidor de 16 núcleos con memoria más que adecuada ya que el algoritmo no consume mucha memoria. Hago uso de la clase BigInteger en .NET 4.

Los detalles del algoritmo no son importantes, pero para el contexto, que sigue es una lista bastante exhaustiva de las operaciones realizadas en estos enteros y algunas características más destacadas del algoritmo:

• Adición/Resta.
• Multiplicación de números grandes por números pequeños.
• División de números grandes por números muy pequeños (por ejemplo, 2).
• Base 2 Log.
• Base 2 Potencia.
• Comparación de dos o más números grandes (Min/Max).
• Sin implicación alguna de los números primos.
• El algoritmo está específicamente diseñado para no consumir mucha memoria ya que el acceso al rendimiento de acceso a la memoria es más que el de algunos cálculos inteligentes sobre la marcha. Sin embargo, si el acceso a la memoria mejorara, el algoritmo podría beneficiarse razonablemente.

He optimizado el código tanto como sea posible y perfilado ahora muestra sólo dos cuellos de botella:

• Cálculo de base 2 del registro por un número tan grande.
• Comprobación de patrones predefinidos de dígitos binarios en estos números. Esto se debe a que la única forma de acceder a los datos subyacentes de BigInteger es primero usando ToByteArray en lugar de operaciones in situ. Además, operar en fragmentos de tamaño byte no ayuda al rendimiento.

Considerando el acceso a la memoria y las operaciones de registro, comencé a pensar en las GPU y si podría descargar parte del trabajo de manera efectiva. Sé muy poco sobre las GPU, excepto que están optimizadas para operaciones de coma flotante.

Mi pregunta es, usando una biblioteca como GPU .NET, ¿cómo puedo procesar números tan grandes en la GPU? ¿Puedo de alguna manera hacer uso de las optimizaciones de punto flotante para calcular el registro de tales números grandes?

Buscando un punto de partida para formar una estrategia.

Answer 1

Estoy buscando trabajo de GPU en C# y estoy considerando Tidepowerd.com GPU.NET y CUDAfy.NET. Tanto Nvidia specific como CUDAfy no (todavía) admiten mono la última vez que lo verifiqué. Pero ambos permiten un código razonablemente normal dentro de C# que se ejecuta en la GPU.

Además, ¿consideró utilizar una biblioteca de terceros? Hay varias bibliotecas BigInteger muy buenas, también de código abierto. GMP es muy bueno y gratis; http://gmplib.org/, hay al menos un contenedor C# (con el que no tengo experiencia) http://www.emilstefanov.net/Projects/GnuMpDotNet/

La clase BigInteger en .NET es inmutable y en mi experiencia eso no es práctico. Si tiene 2 entradas de su tamaño (alrededor de 100 MB), la operación Agregar da como resultado un tercer BigInt de 100 MB. Se puede hacer mucho más rápido si, por ejemplo, modifica uno de los dos originales.

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 

Answer 2

Si alguien le resulta útil, aquí hay una aplicación de registro de base 2 para BigInteger que es mucho más rápido que el uso de funciones integradas.

private static BigInteger LogBase2(BigInteger num) { 
    if (num <= Zero) 
     return MinusOne; //does not support negative values. 
    BigInteger i = Zero; 
    while (!(num >>= 1).IsZero) 
     i++; 
    return i; 
}