Utilizzo della GPU per accelerare i calcoli BigInteger

Question

Ho quasi finito con un algoritmo che elabora alcuni interi molto grandi (dell'ordine di 2 elevato alla potenza di 100.000.000). Ciò richiede un paio di ore di codice altamente parallelo su un server 16 core con una memoria più che sufficiente poiché l'algoritmo non richiede molta memoria. Faccio uso della classe BigInteger in .NET 4.

Le specifiche del algoritmo non sono importanti, ma per il contesto, che segue è una lista abbastanza esaustivo di operazioni eseguite su questi numeri interi e alcune caratteristiche salienti dell'algoritmo:

• Addizione/sottrazione.
• Moltiplicazione di un gran numero di piccoli numeri.
• Divisione di numeri grandi in base a numeri molto piccoli (ad esempio 2).
• Base 2 Log.
• Base 2 Potenza.
• Confronto di due o più numeri grandi (Min/Max).
• Nessun coinvolgimento di sorta dei numeri primi.
• L'algoritmo è progettato in modo specifico per non richiedere un uso intensivo della memoria poiché il calo delle prestazioni dell'accesso alla memoria è superiore a quello di alcuni calcoli intelligenti al volo. Tuttavia, se l'accesso alla memoria dovesse migliorare, l'algoritmo potrebbe essere vantaggioso.

Ho ottimizzato il codice il più possibile e profilatura ora mostra solo due strozzature:

• Calculating base 2 log per tali grandi numeri.
• Verifica di modelli predefiniti di cifre binarie in questi numeri. Questo perché l'unico modo per accedere ai dati sottostanti di BigInteger è utilizzando innanzitutto ToByteArray piuttosto che le operazioni sul posto. Inoltre, il funzionamento su blocchi di dimensioni in byte non aiuta le prestazioni.

Considerando l'accesso alla memoria e le operazioni di registro, ho iniziato a pensare alle GPU e se potevo scaricare parte del lavoro in modo efficace. So molto poco delle GPU, tranne per il fatto che sono ottimizzate per le operazioni in virgola mobile.

La mia domanda è, utilizzando una libreria come GPU .NET, come posso elaborare numeri così grandi sulla GPU? Posso in qualche modo utilizzare le ottimizzazioni in virgola mobile per calcolare Log per numeri così grandi?

Alla ricerca di un punto di partenza per formare una strategia.

Answer 1

Sto cercando lavoro GPU in C# e sto considerando Tidepowerd.com GPU.NET e CUDAfy.NET. Sia Nvidia specifico che CUDAfy non hanno (ancora) supportato mono quando l'ho controllato per l'ultima volta. Ma entrambi consentono un codice dall'aspetto abbastanza normale all'interno di C# che gira sulla GPU.

Inoltre, hai preso in considerazione l'utilizzo di una libreria di party 3d ?. Ci sono molte ottime librerie BigInteger, anche open source. GMP è molto buono e gratuito; http://gmplib.org/, c'è almeno un wrapper C# (di cui non ho esperienza) http://www.emilstefanov.net/Projects/GnuMpDotNet/

La classe BigInteger in .NET è immutabile e nella mia esperienza non è utile. Se si dispone di 2 pollici della propria dimensione (circa 100 MB), l'operazione Aggiungi produce un terzo BigInt da 100 MB. Può essere fatto molto più velocemente se, ad esempio, si modificasse uno dei due originali.

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

Se qualcuno trova utile, ecco un implementazione registro Base 2 per BigInteger che è molto più veloce rispetto all'utilizzo di funzioni integrate.

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; 
}