AVX2中排序數組的高效穩定和

考慮double數字的排序（升序）數組。爲了數值穩定性，數組應該總結起來，就好像從開始到結束迭代它一樣，將總和累加到一些變量中。AVX2中排序數組的高效穩定和

如何使用AVX2高效地進行矢量化？

我已經研究過這種方法Fastest way to do horizontal vector sum with AVX instructions，但它似乎相當棘手的它擴展到一個數組（可能需要一些鴻溝&治之的方法），同時通過確保小的數字相加保持浮點精度然後再將它們添加到更大的數字中。

說明1：我認爲應該可以，例如，總結前4項，然後將它們添加到下4項的總和中，等等。我願意交易一些穩定的表現。但我更喜歡一種不會完全破壞穩定性的方法。

說明性2：由於陣列位於L3緩存（但不在L1/L2緩存中，因爲陣列中的塊由不同線程填充），因此內存不應該成爲瓶頸。我不想求助於卡漢求和，因爲我認爲這確實是重要的操作次數，而卡漢求和會增加大約4次。

來源

2017-09-08 Serge Rogatch

不按升序求和殺死每個房間並行？由於FP算術不是聯想性的，而且您正在明確談論數字穩定性，所以我相信您需要從第一個項目到最後一個項目的序列總和。不是我的DV btw。 –

@MargaretBloom，我已經更新了這個問題並加以澄清。 –

嗯，如果你願意交易一些穩定性，那麼一個簡單的並行總和的作品，不是嗎？你總結了d [0] + d [4] + d [8] + ..，d [1] + d [5] + d [9] + ...等等 – geza

如果您需要精度和並行性，請使用Kahan求和或其他誤差補償技術讓您對總和進行重新排序（進入帶有多個累加器的SIMD向量元素步長）。

由於Twofold fast summation - Evgeny Latkin指出，如果你在內存帶寬上遇到瓶頸，錯誤補償總和不會比最大性能總和慢得多，因爲CPU有很多計算吞吐量在簡單並行化總和中未被使用上存儲器帶寬

參見瓶頸（谷歌kahan summation avx結果）

回覆：你的想法：4個數字的總結組訂單將讓你隱藏FP-增加延遲，和瓶頸上標加吞吐量。

在矢量內進行橫向累加需要大量的洗牌，所以這是一個潛在的瓶頸。你可能會考慮加載a0 a1 a2 a3，然後洗牌得到a0+a1 x a2+a3 x，然後(a0+a1) + (a2+a3)。你有Ryzen，對吧？最後一步是從012b到128b。這仍然是總共3個ADD uops和3個shuffle uops，但使用的指令比標量或128b向量更少。

我建議看看卡農總結之前搞亂這個太多。

來源

2017-09-08 17:11:57

請參閱問題中的澄清2。 –

@SergeRogatch：看看我先鏈接的論文。可能有比Kahan更快的選項，但在數字上比普通的多累加器SIMD更好。 Ryzen只有英特爾CPU的FP吞吐量的一半左右，所以可以很容易地受到來自L3的數據的FP吞吐量的限制。某種成對求和可能是好的。通過精心挑選的洗牌，您可能會獲得好的結果。 –

這裏是我的解決方案迄今：

double SumVects(const __m256d* pv, size_t n) { 
    if(n == 0) return 0.0; 
    __m256d sum = pv[0]; 
    if(n == 1) { 
    sum = _mm256_permute4x64_pd(sum, _MM_SHUFFLE(3, 1, 2, 0)); 
    } else { 
    for(size_t i=1; i+1 < n; i++) { 
     sum = _mm256_hadd_pd(sum, pv[i]); 
     sum = _mm256_permute4x64_pd(sum, _MM_SHUFFLE(3, 1, 2, 0)); 
    } 
    sum = _mm256_hadd_pd(sum, pv[n-1]); 
    } 
    const __m128d laneSums = _mm_hadd_pd(_mm256_extractf128_pd(sum, 1), 
    _mm256_castpd256_pd128(sum)); 
    return laneSums.m128d_f64[0] + laneSums.m128d_f64[1]; 
}

一些解釋：它增加了第一相鄰double陣列的物品，如a[0]+a[1]，a[2]+a[3]等。然後它添加相鄰項目的總和。

來源

2017-09-09 10:01:10

我搜索的一些內容提到了「兩兩相加」。這可能與你在這裏做的事情是一回事。由於'hadd'後面需要另一個shuffle，你可以通過手動混洗來完成一個垂直的'add'按不同的順序嗎？也許做一個Ryzen版本，可以做更多128b-vector的東西，但仍然有256b的空間，以獲得更多的前端uop吞吐量？ –

你想玩的遊戲可能適得其反。嘗試通過從您最喜歡的發行版中生成一堆iid樣本進行試驗，對它們進行排序，然後將「按升序排列的總數」與「按照遞增順序對每條車道進行求和，然後求和車道總和」進行比較。

對於4條車道和16條數據，加總分數爲28％的時間帶來更小的誤差，而按遞增順序相加給出的誤差約小17％;對於4車道和256數據，加總分數在68％的時間內給出了較小的誤差，而按遞增次序求和給出的誤差約爲12％。加分lanewise也會擊敗您在自我回答中提供的算法。爲此，我在[0,1]上使用了均勻分佈。

來源

2017-09-09 22:06:06 tmyklebu

這是一個有趣的觀察，但你可以發佈這個源代碼。目前還不清楚你如何計算錯誤。 –

您是否與Kahan summation比較或找到錯誤？或者你爲'float'做了這個，並用'double'或者extended-precision取得了無錯誤的總和？或者是其他東西？ –

@SergeRogatch：總結一堆'double's的錯誤是計算結果和確切結果之間的差異。使用像mpfr這樣的庫來計算確切的結果非常簡單。 – tmyklebu

AVX2中排序數組的高效穩定和

回答

相關問題