描述

數(shù)學(xué)很難。當(dāng)你的老師不喜歡教它時(shí)。

根據(jù)維基百科，

CUDA （Compute Unified Device Architecture）是由Nvidia創(chuàng)建的并行計(jì)算平臺和應(yīng)用程序編程接口（API）模型。它允許軟件開發(fā)人員和軟件工程師使用支持 CUDA 的圖形處理單元 (GPU) 進(jìn)行通用處理——一種稱為 GPGPU（圖形處理單元上的通用計(jì)算）的方法。CUDA平臺是一個軟件層，可直接訪問 GPU 的虛擬指令集和并行計(jì)算元素，以執(zhí)行計(jì)算內(nèi)核。

CUDA （Compute Unified Device Architecture）是由Nvidia創(chuàng)建的并行計(jì)算平臺和應(yīng)用程序編程接口（API）模型。它允許軟件開發(fā)人員和軟件工程師使用支持 CUDA 的圖形處理單元 (GPU) 進(jìn)行通用處理——一種稱為 GPGPU（圖形處理單元上的通用計(jì)算）的方法。CUDA平臺是一個軟件層，可直接訪問 GPU 的虛擬指令集和并行計(jì)算元素，以執(zhí)行計(jì)算內(nèi)核。

換句話說，英偉達(dá)提供了一個新的開發(fā)框架，由硬件和軟件組成，用于并行計(jì)算任務(wù)，從而減少完成時(shí)間。

CUDA 范例由具有多個處理器的專用硬件和 C/C++ 語言的巧妙擴(kuò)展組成，能夠通過簡單的任務(wù)來處理每個處理器的功能。當(dāng)您必須執(zhí)行搜索、查詢、排序和卷積等重復(fù)性任務(wù)時(shí)，您可以（部分）擺脫繁重的循環(huán)，并將一小部分操作安排給不同的工作人員。由于數(shù)千個工作線程并行運(yùn)行，完成任務(wù)的時(shí)間大大減少。

當(dāng)然也有一些注意事項(xiàng)：雖然串行馮諾依曼調(diào)度只需要一個輸入、一個在指令后完成詳細(xì)說明的黑盒和一個輸出，但并行架構(gòu)需要考慮數(shù)據(jù)存儲在哪里，誰在處理它（以及如何），一些數(shù)據(jù)何時(shí)可以免費(fèi)用于下一次評估。并發(fā)分析并不容易，但是一旦你知道了基礎(chǔ)，它就變得簡單了。

CUDA 硬件 – Jetson Nano

CUDA 迎來了它的第 10 個化身，展示了作為一個強(qiáng)大而穩(wěn)定的開發(fā)工具。CUDA 作為一種圖形架構(gòu)誕生，能夠在顯示器上快速處理像素并驅(qū)動其顏色，如今已成為一個完整的并行開發(fā)系統(tǒng)。雖然它的名氣仍然存在于圖形數(shù)據(jù)處理和成像領(lǐng)域，但越來越多的開發(fā)人員投入時(shí)間和精力來揭示和利用隱藏在裸機(jī)中的并行能力。工程師和數(shù)學(xué)研究人員重構(gòu)了眾所周知的串行算法，以利用多處理的驚人速度。

沒錯。我們開發(fā)了一種帶有 CUDA GPU 的并行分解算法，比原始 CPU 方法快 1,000 倍。只需將一個線程專用于 960 個殘差類（共 4620 個）中的每一個，我們就有了如此巨大的加速。但是Jetson Nano沒有 960 個備用計(jì)算單元，雖然它仍然可以從 128 個 CUDA 內(nèi)核中受益，但我們將在其上測試不同的分解算法。

我們將嘗試一種完全不同的方法，而不是使用 125 cu 將工作細(xì)分為 8 個塊，但確定性稍差，但這將利用Jetson Nano使用統(tǒng)計(jì)模擬的有限 CUDA。

?

分解——Pollard Rho 算法

來自維基百科：

假設(shè)我們需要分解一個數(shù) n = p*q，其中 p 是一個非平凡的因子。一個多項(xiàng)式模 n，稱為 g(x)（例如，g(x) = (x2 + 1) mod n，用于生成偽隨機(jī)序列。選擇一個起始值，比如 2，序列繼續(xù)為 x1 =g(2), x2=g(g(2)), x3=g(g(g(2))) 等。該序列與另一個序列{xk mod p}有關(guān)。由于事先不知道p ，這個序列在算法中是無法明確計(jì)算的，但算法的核心思想就在其中。

因?yàn)檫@些序列的可能值的數(shù)量是有限的（模運(yùn)算保證了它），所以 {xk} 序列（即 mod n）和 {xk mod p} 序列最終都會重復(fù)，即使我們不知道后者. 假設(shè)序列表現(xiàn)得像隨機(jī)數(shù)。由于生日悖論（我們將在另一篇文章中分析），重復(fù)發(fā)生之前的 xk 的數(shù)量預(yù)計(jì)為 O(√N(yùn))，其中 N 是可能值的數(shù)量。所以序列 {xk mod p} 可能會比序列 {xk} 更早地重復(fù)。一旦一個序列有一個重復(fù)的值，這個序列就會循環(huán)，因?yàn)槊總€值只依賴于它之前的值。這種最終循環(huán)的結(jié)構(gòu)產(chǎn)生了“Rho 算法”的名稱，因?yàn)楫?dāng)值 x1 mod p、x2 mod p 等時(shí)，它與希臘字符 ρ 的形狀相似。

假設(shè)我們需要分解一個數(shù) n = p*q，其中 p 是一個非平凡的因子。一個多項(xiàng)式模 n，稱為 g(x)（例如，g(x) = (x2 + 1) mod n，用于生成偽隨機(jī)序列。選擇一個起始值，比如 2，序列繼續(xù)為 x1 =g(2), x2=g(g(2)), x3=g(g(g(2))) 等。該序列與另一個序列{xk mod p}有關(guān)。由于事先不知道p ，這個序列在算法中是無法明確計(jì)算的，但算法的核心思想就在其中。
因?yàn)檫@些序列的可能值的數(shù)量是有限的（模運(yùn)算保證了它），所以 {xk} 序列（即 mod n）和 {xk mod p} 序列最終都會重復(fù)，即使我們不知道后者. 假設(shè)序列表現(xiàn)得像隨機(jī)數(shù)。由于生日悖論（我們將在另一篇文章中分析），重復(fù)發(fā)生之前的 xk 的數(shù)量預(yù)計(jì)為 O(√N(yùn))，其中 N 是可能值的數(shù)量。所以序列 {xk mod p} 可能會比序列 {xk} 更早地重復(fù)。一旦一個序列有一個重復(fù)的值，這個序列就會循環(huán)，因?yàn)槊總€值只依賴于它之前的值。這種最終循環(huán)的結(jié)構(gòu)產(chǎn)生了“Rho 算法”的名稱，因?yàn)楫?dāng)值 x1 mod p、x2 mod p 等時(shí)，它與希臘字符 ρ 的形狀相似。

好的。現(xiàn)在讓我們深吸一口氣，看看上一段的真正含義。

假設(shè)我們在一條長長的圓形賽道上跑步。我們怎么知道我們已經(jīng)完成了一個周期？一個聰明的解決方案是讓兩個跑步者 A 和 B 跑得比 A 快兩倍。他們從同一個位置開始，當(dāng) B 超過 A 時(shí)，我們知道 B 至少循環(huán)了一次。

我們有以下算法：

x = 2; y = 2; d = 1
while d == 1:
x = g(x)
y = g(g(y))
d = gcd(|x - y|, n)
if d == n:
return failure
else:
return d

假設(shè)我們想分解數(shù)字 8051。我們有

n = 8051
x = 2
y = 2
g(x) = (x^2 + 1)
g(g(x)) = g(x^2 + 1)

應(yīng)用該算法，我們得到以下解決步驟：

迭代示例

?

從不同的 x 和/或 y 開始，我們可以找到 8051、83 的另一個除數(shù)

如果我們使用樸素的試因式分解算法，我們應(yīng)該測試 N 的平方根以下的所有質(zhì)因數(shù)。試制因式算法隨著數(shù)字 (2n/2) 的位數(shù)呈指數(shù)增長。

Pollard Rho 算法在其運(yùn)行時(shí)間和它找到一個因子的概率之間提供了一種權(quán)衡。在 O(√d) <= O(n1/4) 次迭代中，可以以大約 0.5 的概率實(shí)現(xiàn)素?cái)?shù)除數(shù)。這是一個啟發(fā)式的主張，對算法的嚴(yán)格分析仍然是開放的。

從理論到實(shí)踐

為了展示實(shí)際的算法（以及并行實(shí)現(xiàn)如何加速結(jié)果），我們準(zhǔn)備了一個簡短的源代碼，使用一個 CPU、通過 OpenMP 的多個 CPU 和 GPU 運(yùn)行 Pollard Rho 分解。提供了要分解的候選者列表，以顯示：

• 隨著因子的增長，算法如何變慢
• 放緩是如何歸因于因子大小，而不是因子數(shù)量
• GPU 開銷如何使并行算法在較小的因素上比 CPU 慢
• 正確選擇 GPU 的塊大小和塊數(shù)如何帶來更好的結(jié)果
• 并行算法的整體增益是多少。

?

我們提出的算法僅限于 64 位數(shù)字，但很容易將其擴(kuò)展到多精度算術(shù)。無論如何，眾所周知，Pollard Rho 的效率隨著因子的長度而降低：一般情況下，當(dāng) N 超過 40 位時(shí)，應(yīng)選擇其他方法（如 P-1 和 ECM）。

該算法對于具有小因子的數(shù)字非常快，但在所有因子都很大的情況下較慢。The ρ algorithm's most remarkable success was the factorization of the eighth Fermat number , F 8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321. The ρ algorithm was a good choice for F 8 because the prime factor p = 1238926361552897 is much smaller than the other factor. UNIVAC 1100/42 的分解耗時(shí) 2 小時(shí)。

您可以在我的FermatSearch網(wǎng)站上找到有關(guān)費(fèi)馬分解和素?cái)?shù)證明的更多信息。

CPU和GPU實(shí)現(xiàn)的區(qū)別

我們有兩個不同的內(nèi)核作為主機(jī)和設(shè)備運(yùn)行。

主機(jī)內(nèi)核在 CPU（或啟用 OpenMP 時(shí)的 CPU）上運(yùn)行。它需要對數(shù)字進(jìn)行分解，然后循環(huán)直到找到解決方案。

設(shè)備內(nèi)核在 GPU 上運(yùn)行。x 和 y 的（隨機(jī)）值被預(yù)先計(jì)算、索引并存儲在數(shù)組中。數(shù)組在要分解的數(shù)字之后異步復(fù)制。然后啟動塊。設(shè)備代碼的每個線程同時(shí)訪問數(shù)組的一部分，計(jì)算其步長 (g(x), g(g(x)), 和的絕對值和 gcd)，然后將結(jié)果存儲回?cái)?shù)組中，然后檢查 GCD 是否大于 1。如果是，我們有一個因子。該值保存在結(jié)果位置。一旦這個單程循環(huán)完成，結(jié)果就會被傳送回主機(jī)內(nèi)存，并返回給調(diào)用主程序。

它的表現(xiàn)如何？

我們使用了 19 個數(shù)字的列表，并在 2 個不同的平臺上對它們進(jìn)行了測試：一臺配備Intel Core i7 9800X處理器和Nvidia RTX 2060 GPU的 PC ，以及 Nvidia Jetson Nano板。

PC給出了以下結(jié)果：

Overall results:
Host?? Time = 503.134 s
Device Time =?? 1.576 s
Speedup???? = 319.2

換句話說，即使是 CUDA 中算法的簡單實(shí)現(xiàn)也顯示出 320 倍的加速。當(dāng)我們有 1920 個計(jì)算單元時(shí)，我們在 GPU 上運(yùn)行 256×256 網(wǎng)格，并且沒有利用共享內(nèi)存加速或寄存器優(yōu)化。

在 Nano 上，我們實(shí)現(xiàn)了以下時(shí)序：

Overall results:
Host?? Time = 1893.795 s
Device Time =?? 39.448 s
Speedup???? =?? 48.0

Nano 上的 GPU 是 Maxwell，具有少量內(nèi)核和低于 1 GHz 的時(shí)鐘，但相對于 CPU，我們實(shí)現(xiàn)了 48 倍的加速。

我們還注意到，使用并行算法的 Jetson Nano 的 CUDA 比Intel 9800X 快 12 倍以上。對于成本比 PC 系統(tǒng)低 15 倍的電路板來說還不錯。

Github上提供了使用 Jetson Nano 試驗(yàn) CUDA 的源代碼。我們將很快測試其他背靠背 CPU vs GPU 算法，不僅展示并行計(jì)算的樂趣，也展示 CUDA 圖形加速的驚人之處。

?