加快x64彙編程序ADD循環

我正在處理非常長整數（約100,000十進制數字）的乘法運算。作爲我的圖書館的一部分，我添加兩個長號碼。加快x64彙編程序ADD循環

分析顯示我的代碼在add（）和sub（）例程中的運行時間高達25％，所以重要的是它們儘可能快。但是我看不到太多的潛力。也許你可以給我一些幫助，建議，見解或想法。我會測試他們並回復你。

到目前爲止，我的外接程序做一些設置，然後使用8次展開的循環：

mov rax, QWORD PTR [rdx+r11*8-64] 
mov r10, QWORD PTR [r8+r11*8-64] 
adc rax, r10 
mov QWORD PTR [rcx+r11*8-64], rax

7更多塊不同的偏移跟隨，然後循環。

我嘗試加載內存中的值，但沒有幫助。我想這是因爲預取良好。我使用英特爾i7-3770 Ivy Bridge 4核CPU。但我想寫一些適用於任何現代CPU的代碼。

編輯：我做了一些時間安排：它增加了1k字，約2.25個週期/字。如果我移除ADC，那麼只剩下MOV，它仍然需要大約1.95個週期/字。所以主要的瓶頸似乎是內存訪問。庫memcpy()以大約0.65個週期/字運行，但只有一個輸入，而不是兩個。不過，我猜，由於使用了SSE寄存器，速度要快得多。

一些問題：

是否有用使用「負載，負載，加，存儲」結構或將「負載，加入到內存的」幫助？到目前爲止，我的測試沒有顯示出任何優勢。
像往常一樣，上證所（2,3,4）沒有幫助可以預計？
尋址（縮放索引加基數加偏移）影響嚴重嗎？我可以用ADD r11, 8代替。
循環展開呢？我讀取展開對桑迪橋架構（Agner Fog http://www.agner.org/optimize/）不利。它是首選還是避免？
（編輯）我可以使用SSE寄存器從存儲器中加載和存儲更大的塊中的單詞，並有效地與通用寄存器和SSE寄存器交換單詞嗎？

我很欣賞任何意見。

來源

2012-12-20 cxxl

最快的方法（我知道）乘以非常大的數字是一個快速傅立葉變換http://en.wikipedia.org/wiki/Multiplication_algorithm 我從來沒有試圖在彙編中實現它的邏輯。 Appetintly Prime95在x86彙編邏輯中包含了一個快速傅里葉變換，您可以從中自由地（自由地）從這裏獲取 –

謝謝，我知道這一點。現在我只想加快速度。 – cxxl

您可以查看GMP來源。 – zch

嘗試先預取數據（您可以嘗試先讀取更多數據塊到x64寄存器，然後進行計算），檢查數據是否在內存中正確對齊，將循環代碼放在標籤對齊爲16的位置，嘗試除去SIB解決

您也可以嘗試縮短您的代碼：

mov rax, QWORD PTR [rdx+r11*8-64] 
adc rax, QWORD PTR [r8+r11*8-64] 
mov QWORD PTR [rcx+r11*8-64], rax

來源

2012-12-20 14:18:18

我嘗試了所有這一切，沒有得到任何好處，有時甚至更糟糕的時機。主要時間似乎在內存訪問中丟失。 – cxxl

最困難的依賴關係是每一個內存塊之間利差的傳播;我會嘗試首先設置一個處理這個問題的方法。

以下片段模擬進位傳播，但帶有不使用進位標誌的「優點」。這個可以並行處理三個或四個單獨的線程，每個線程產生一半分別攜帶大約25000個十進制數字（或10000個字節）。那麼影響只有一個字節，字，雙字等的那些載體的概率將漸近地達到零。

long long carry=0; 
for (int i=0;i<N;i++) { 
    carry += (long long)*a++ + (long long)*b++; 
    *c++ = carry; carry>>=32; 
}

根據我的分析，使用XMM carryless除了將用時約550ms（1E9的話），模擬套利將採取〜1020ms和4路並行版本將用時約820ms（不帶任何彙編優化）。

架構優化可能包括使用冗餘數字系統，其中進不必進行傳播，其中攜帶的評價可以推遲幾乎循環往復所有的時間和。

來源

2012-12-20 15:07:46

我敢肯定的memcpy是更快，因爲它不會對獲取的數據的依賴，纔可以進行下一步操作。

如果是這樣，它確實是這樣的，你可以安排你的代碼：

mov rax, QWORD PTR [rdx+r11*8-64] 
mov rbx, QWORD PTR [rdx+r11*8-56] 
mov r10, QWORD PTR [r8+r11*8-64] 
mov r12, QWORD PTR [r8+r11*8-56] 
adc rax, r10 
adc rbx, r12 
mov QWORD PTR [rcx+r11*8-64], rax 
mov QWORD PTR [rcx+r11*8-56], rbx

我不是100％肯定-56的偏移是你的代碼的權利，但概念是「對」。

我也會考慮緩存命中/緩存衝突。例如。如果你有三塊數據[看起來你是這樣做的]，那麼你要確保它們不與緩存中的相同偏移對齊。一個不好的例子是，如果你從緩存中的相同位置以緩存大小的倍數分配所有的塊。過度分配，並確保您的不同的數據塊由至少512字節的偏移，以便分配4K特大型，並舍入到4K邊界的起始地址，然後添加512到第二緩衝器，和1024到第三緩衝器]

如果您的數據足夠大（大於L2緩存），則可能需要使用MOVNT來獲取/存儲數據。這樣可以避免讀入緩存 - 只有在數據量非常大的情況下，這樣做纔是有益的，下一次讀取只會導致其他可能會發現「有用」的其他內容被踢出緩存，並且您不會獲得回到它之前，你已經將它踢出緩存無論如何 - 所以存儲在緩存中的值將不會實際上幫助...

編輯：使用SSE或類似將不會幫助，因爲覆蓋在這裏： Can long integer routines benefit from SSE?

來源

2012-12-20 15:29:20

加快x64彙編程序ADD循環

回答

相關問題