優化x64彙編器MUL循環

我在寫數學代碼，它需要快速乘以大數。它分解爲整數數組與單個整數的乘法運算。在C++中，這看起來像這樣（在無符號的）：優化x64彙編器MUL循環

void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) { 
    unsigned __int64 of = 0; // overflow 
    unsigned i = 0; // loop variable 
    while (i < len) { 
     of += (unsigned __int64)a[i] * b + r[i]; 
     r[i] = (unsigned)of; 
     of >>= 32; 
     ++i; 
    } 
    r[i] = (unsigned)of; // save overflow 
}

我手動展開這個循環中，它轉換爲64位和製作的.ASM編譯器輸出，以進一步優化它。主要.ASM循環現在看起來是這樣的：

mov rax, rdi        ; rdi = b 
mul QWORD PTR [rbx+r10*8-64]    ; rdx:rax = a[i] * b; r10 = i 
mov rsi, QWORD PTR [r14+r10*8-64]  ; r14 = r; rsi = r[i] 
add rax, rsi 
adc rdx, 0 
add rax, r11        ; r11 = of (low part) 
adc rdx, 0 
mov QWORD PTR [r14+r10*8-64], rax  ; save result 
mov r11, rdx 

; this repeats itself 8 times with different offsets

當我這個標杆，我覺得這需要大約6.3個週期上avarage每個增殖我的酷睿2四核。

我的問題是：我能以某種方式加快速度嗎？不幸的是，我看不到任何方法來避免其中的一個增加，並且乘法總是需要RDX：RAX，所以我需要移動數據並且不能排序「並行乘法」。

任何想法的人？

更新： 一些測試後，我已經成功地把速度可達約5.4個週期每64位MUL（包括所有添加，移動和循環開銷）。我想這是關於Core2的最佳選擇，因爲Core2沒有非常快速的MUL指令：吞吐量爲3，延遲爲6（7）個週期。吞吐量爲1，等待時間爲3（4）個週期，桑迪橋將會更好。

關於GMP的少得多的數字：我從他們的源代碼中得到了這一點，在我看來這是一個理論數字。但可以肯定的是，這是一個計算AMD K9 CPU的數字。從我讀過的內容來看，AMD收集的MUL單元比（舊的）英特爾芯片更快。

來源

2011-11-14 cxxl

您可能想看看GMP中的一些裝配例程。他們有一個功能可以完成這個功能，並且可以彙編到大多數處理器（包括x64）中。 – Mysticial

GMP確實對快速mul_basecase有很好的支持，而且它的每MUL需要2.35個週期，非常好。如果我正確地理解了它們，它們會交錯地插入兩個向量，這似乎保持低依賴性並改善溢出處理。 – cxxl

看起來你的日常工作可以從SSE中受益。 PMULLD和PADDD看起來像是相關的說明。不知道爲什麼你的編譯器不能從中產生SSE。

來源

2011-11-14 16:41:01

適用於32位x 32位乘法。但不適用於64位x 64位乘法。 – Mysticial

當你只保留最重要的雙字時，你真的需要qword乘法嗎？ –

我將RAX保存回內存，RDX用作進位（通過R11）並被添加到下一個元素中。不幸的是，我需要QWORD MUL。 – cxxl

我只想指出，循環計數是沒有用的，因爲您的指令將被轉換爲微代碼，將根據cpu正在執行的其他任何事情按順序執行或暫停執行。如果你有一個快速的例程，你可以嘗試去除一個理論週期，除非你知道你的例程將始終完全隔離。

來源

2012-02-18 12:04:50 Tobias

OP對他的代碼進行了基準測試，顯然得到了可重複的結果。他沒有計算理論週期，他確實測量了實際週期。指令被翻譯成微碼並重新排序的方式是可預測的，也是相當不錯的（見www.agner.org）。此外，優化時不需要_complete_隔離，運行代碼的後臺操作系統通常不會削減超過百分之幾的數據（如果有的話）。 – hirschhornsalz

對不起，我錯過了他的個人資料:) – Tobias

這應該是一個評論，而不是回覆。 –

我曾經寫過一個看起來非常像這樣的循環，對大量數據進行最少量的處理，導致循環受內存速度的限制。

我想嘗試用gcc使用功能__builtin_prefetch（）或PREFETCHT0指令彙編

http://gcc.gnu.org/onlinedocs/gcc-3.3.6/gcc/Other-Builtins.html

預取[I]和r [I]

如果在這工作的結果可以是戲劇性的。只要循環長達一千次左右，我就會預取[i + 64]和r [i + 64]作爲起點，看看它在CPU上的差異。您可能需要嘗試更大的預取距離。

來源

2012-02-28 00:46:26 camelccc

我試過了。結果是它在我的Core2 Quad上沒有任何區別。通過閱讀CPU手冊和Agner Fog的指南，我發現今天的處理器具有良好的預取邏輯，能夠很好地檢測簡單的循環，因此不需要手動預取。 – cxxl

在調用之前，r是否包含任何重要的東西？

如果確實如此，並且您正在積累它，請立即停止閱讀。

如果它不存在（即你總是積累到零），並且假設你在比緩存大小大得多的數組上調用這個函數，那麼我會尋找一種方法來消除從r中讀取並將「保存結果」MOV轉換爲MOVNT（內部函數中的_mm_stream_ps）。

這可以顯着提高性能。怎麼樣？目前，您的緩存正在從緩存行中獲取緩存行，從r中獲取緩存行並將緩存行寫回r。有了這麼一個叫做流媒體的商店，你只需要從緩存中讀取緩存行，並直接寫入r：更少的總線流量。如果您查看任何現代CRT的memcpy實現，它將切換到使用高於某個緩存大小相關閾值的流存儲（並使用傳統移動將almost twice as fast作爲memcpy運行）。

來源

2012-02-28 22:34:22 timday

這非常有趣。函數調用時'r'是空的，但緩慢填滿。此外，功能完成後，我期望它將用於某些東西（因爲它的結果:)）。我期望MOVNT不是有利的，因爲我們正在按順序填寫'r'。 Agner Fog寫道：「如果並且只有在預期二級高速緩存未命中的情況下，沒有高速緩存的數據存儲方法纔有優勢」（http://www.agner.org/optimize/optimizing_cpp.pdf）。我認爲可以排除99％的二級緩存未命中。 – cxxl

優化x64彙編器MUL循環

回答

相關問題