使用GPU加速BigInteger計算

我幾乎完成了一個處理一些非常大的整數（大約2次提高到100,000,000次）的算法。由於該算法不是內存密集型的，因此在16核心服務器上需要花費幾個小時的高度並行代碼才能獲得足夠的內存。我利用BigInteger類在.NET 4使用GPU加速BigInteger計算

算法的細節並不重要，但對於背景下，以下是對這些整數和算法的一些顯着特徵進行操作的一個非常詳盡的列表：

加法/減法。
大數乘以小數。
大數除以非常小的數字（例如2）。
Base 2 Log。
基地2電源。
比較兩個或更多的大數字（最小/最大）。
不涉及素數。
該算法的具體設計不是內存密集型，因爲內存訪問的性能高於一些智能即時計算。儘管如此，如果內存訪問得到改善，算法可以合理地受益。

我已經優化了代碼儘可能現在分析僅示出了兩個瓶頸：

計算基地2登錄用於這種大的數字。
檢查這些數字中預定義的二進制數字模式。這是因爲訪問BigInteger底層數據的唯一方法是首先使用ToByteArray而不是就地操作。此外，在字節大小的塊上操作不會有助於性能。

考慮到內存訪問和日誌操作，我開始考慮GPU和我是否可以有效地卸載一些工作。我對GPU的瞭解很少，只是它們針對浮點運算進行了優化。

我的問題是，使用類似GPU .NET的庫，我該如何在GPU上處理如此龐大的數字？我能以某種方式利用浮點優化來計算這麼大數量的Log嗎？

尋找一個起點來形成一個戰略。

來源

2012-08-17 Raheel Khan

您是否考慮過使用CUDAfy.NET？ http://cudafy.codeplex.com/（請注意，這是NVIDIA特定的，因此可能對您無用） – 2012-08-17 07:12:26

我正在四處尋找C＃中的GPU工作，並且正在考慮Tidepowerd.com GPU.NET和CUDAfy.NET。 Nvidia具體和CUDAfy在上次檢查時還沒有支持單聲道。但是它們都允許在GPU上運行的C＃中的相當正常的代碼。

另外，你有沒有考慮使用3D方庫？有幾個非常好的BigInteger庫，也是開源的。 GMP非常好，免費; http://gmplib.org/，至少有一個C＃包裝（我沒有經驗）http://www.emilstefanov.net/Projects/GnuMpDotNet/

.NET中的BigInteger類是不可變的，根據我的經驗，這是不方便的。如果你的尺寸有兩個整數（大約100MB），那麼Add操作會產生第三個100MB的BigInt。例如，如果修改兩個原件中的一個，它可以更快地完成。

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

來源

2012-08-17 07:49:16 IvoTops

謝謝。下載三個包括你建議的庫後，我似乎沒有找到任何地方的日誌功能。這是有意而且難以實施的嗎？ – 2012-08-17 09:34:08

@RaheelKhan你需要一個浮點記錄還是最高位置的位？ – harold 2012-08-17 10:42:07

我需要兩個都取決於情況。無論如何BigInteger最高位設置是微不足道的。浮點花費我太多時間。 – 2012-08-19 18:42:36

如果有人發現它有幫助，這裏是BigInteger的Log Base 2實現，它比使用內置函數快得多。

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

來源

2017-07-04 17:16:19

謝謝。非常古老的問題，但我仍然想回去做一個性能比較。 – 2018-01-17 14:07:22

使用GPU加速BigInteger計算

回答

相關問題