BigInteger hesaplamaları hızlandırmak için GPU kullanma

Question

Neredeyse çok büyük tamsayıları işleyen bir algoritma ile işim bitti (yaklaşık 100.000.000 değerine yükseltilen güç sırasıyla). Algoritmanın bellek yoğun olmadığı için bu, bir çift çekirdekli 16 çekirdekli sunucuda yeterli hafızaya sahip bir çift saat alır. Ben 4.

algoritmasının özelliklerini önemli olmayan ancak bağlam için aşağıdaki bu tamsayılar ve algoritmanın bazı belirgin özellikleri üzerinde gerçekleştirilen operasyonların oldukça ayrıntılı bir liste olduğu .NET BigInteger sınıfı faydalanmak:

• Toplama/Çıkarma.
• Büyük sayıların küçük sayılar ile çarpımı.
• Çok sayıda küçük sayılarla bölme (ör. 2).
• Taban 2 Günlük.
• Temel 2 Güç.
• İki veya daha fazla büyük sayının karşılaştırması (Min/Maks).
• Asal sayıların hiçbir katılımı yoktur.
• Algoritma, bellek erişiminin performans isabeti, bazı akıllı, anında yapılan hesaplamalarinkinden daha fazla olduğu için, özellikle bellek yoğun olarak tasarlanmamıştır. Bununla birlikte, eğer bellek erişimi gelişirse, algoritma makul fayda sağlayabilir.

Ben mümkün olduğunca kod optimize ve profilleme şimdi sadece iki darboğazları gösterir: Bu tür büyük sayılar için üs 2 Log hesaplama

• .
• Bu sayılardaki önceden tanımlı ikili sayı örüntülerinin kontrol edilmesi. Bunun nedeni, BigInteger temelli verilere erişmenin tek yolunun, ilk önce yerinde işlemler yerine ToByteArray kullanmasıdır. Ayrıca, bayt boyutlu parçalar üzerinde işlem yapmak performansa yardımcı olmaz.

bellek erişimi ve Log operasyonları göz önüne alındığında, ben GPU'ları hakkında ve ben etkili işin bazı yükünü olup olamayacağını düşünmeye başladım. Kayan nokta işlemleri için optimize edilmiş olmaları dışında GPU'lar hakkında çok az şey biliyorum.

Soruma göre, GPU .NET gibi bir kitaplık kullanarak, GPU'da bu kadar büyük sayıları nasıl işleyebilirim? Böyle büyük sayılarda Log hesaplamak için bir şekilde kayan nokta optimizasyonlarını kullanabilir miyim?

Strateji oluşturmak için bir başlangıç ​​noktası mı arıyorsunuz?

Answer 1

C# 'da GPU çalışması için etrafa bakıyorum ve Tidepowerd.com GPU.NET ve CUDAfy.NET'i düşünüyorum. Nvidia'ya özgü ve CUDAfy, en son kontrol ettiğimde mono (henüz) desteklemedi. Ancak ikisi de C# içinde GPU üzerinde çalışan makul derecede normal görünen bir kod için izin verir.

Ayrıca, bir 3 boyutlu parti kitaplığı kullanmayı düşündünüz mü? Açık kaynak kodlu birkaç tane de çok iyi BigInteger kütüphanesi var. GMP çok iyi ve özgürdür; http://gmplib.org/, en az bir C# sarmalayıcı (hangi deneyimim yok) var http://www.emilstefanov.net/Projects/GnuMpDotNet/

.NET'teki BigInteger sınıfı değişmez ve benim için kullanışlı olmayan bir deneyim. Boyutu 2 inç (yaklaşık 100MB) varsa, Ekle işlemi üçüncü bir 100 MB BigInt sonuçlanır. Örneğin, iki orijinalden birini değiştirirseniz daha hızlı yapılabilir.

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

kimse bulursa yararlı, burada yerleşik işlev kullanarak çok daha hızlı olduğunu BigInteger için bir Log Bankası 2 uygulamasıdır.

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