優化索引陣列求和

我有以下C++代碼：優化索引陣列求和

const int N = 1000000 
int id[N]; //Value can range from 0 to 9 
float value[N]; 

// load id and value from an external source... 

int size[10] = { 0 }; 
float sum[10] = { 0 }; 
for (int i = 0; i < N; ++i) 
{ 
    ++size[id[i]]; 
    sum[id[i]] += value[i]; 
}

我應該如何優化循環？

我考慮使用SSE將每4個浮點數加到一個總和上，然後在N次迭代之後，總和只是xmm寄存器中4個浮點數的總和，但是當源索引像這樣時這不起作用，需要寫出10個不同的陣列。

來源

2010-12-04 Dmi

只是爲了確保，在重新al代碼是`size`和`sum`自動變量在這裏？如果它們不是（例如，如果它們是通過指針或引用傳入到實際例程中的話），那麼可能會由於sum和value之間出現混疊的可能性而導致人爲的低效率和/大小`和`id`。 – 2010-12-04 20:28:01

這裏將並行化算作一個優化嗎？即將數組分割成多個子數組，然後將每個子數組傳遞給一個單獨的線程進行迭代，然後在最後組合結果。對於足夠大的陣列，至少在多核機器上可以提供很好的加速。 – 2010-12-04 20:32:02

是的，大小和總和是這樣的變量。分區聽起來像是一個好主意，我會嘗試memcpy將它們分解成四個宿區並且並行運行它們。 – Dmi 2010-12-04 20:35:10

這種循環很難使用SIMD指令進行優化。在大多數SIMD指令集中，不僅沒有一種簡單的方法來進行這種索引讀取（「聚集」）或寫入（「分散」），即使存在，這個特定的循環仍然存在您可能遇到的問題兩個值在一個SIMD寄存器中映射到相同的id，例如當

id[0] == 0 
id[1] == 1 
id[2] == 2 
id[3] == 0

在這種情況下

，明顯的方法（這裏的僞代碼）

x = gather(size, id[i]); 
y = gather(sum, id[i]); 
x += 1; // componentwise 
y += value[i]; 
scatter(x, size, id[i]); 
scatter(y, sum, id[i]);

不會工作！

你可以通過，如果有一個非常小的一些可能的情況下（例如，假設sum和size只有各3片）通過只是在做蠻力相比，但並沒有真正規模。不使用SIMD稍快得到這個

一種方式是通過破壞指令之間的依賴關係使用展開了一下：

int size[10] = { 0 }, size2[10] = { 0 }; 
int sum[10] = { 0 }, sum2[10] = { 0 }; 
for (int i = 0; i < N/2; i++) { 
    int id0 = id[i*2+0], id1 = id[i*2+1]; 
    ++size[id0]; 
    ++size2[id1]; 
    sum[id0] += value[i*2+0]; 
    sum2[id1] += value[i*2+1]; 
} 

// if N was odd, process last element 
if (N & 1) { 
    ++size[id[N]]; 
    sum[id[N]] += value[N]; 
} 

// add partial sums together 
for (int i = 0; i < 10; i++) { 
    size[i] += size2[i]; 
    sum[i] += sum2[i]; 
}

這是否有助於與否雖然取決於目標CPU上。

來源

2010-12-04 20:24:54

那麼，你在你的循環中調用id [i]兩次。如果你願意，你可以將它存儲在一個變量或一個寄存器int中。

register int index; 
for(int i = 0; i < N; ++i) 
{ 
index = id[i]; 
++size[index]; 
sum[index] += value[i]; 
}

MSDN文檔說明這大約寄存器：

寄存器關鍵字指定變量是要被存儲在一機寄存器。微軟具體

編譯器不接受用戶請求寄存器變量; 取而代之的是，當全局寄存器分配優化（/ Oe 選項）打開時，它自己的寄存器選項。但是，與寄存器關鍵字相關聯的所有其他語義都是可以接受的。

來源

2010-12-04 20:22:51

東西你能做的就是用-S標誌（或者，如果你不使用gcc當量）進行編譯和比較使用-O，-O2和-O3標誌的各種組件的輸出。優化循環的一種常見方法是做某種程度的展開，對於（一個非常簡單的，天真的）例子：

int end = N/2; 
int index = 0; 
for (int i = 0; i < end; ++i) 
{ 
    index = 2 * i; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
    index++; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
}

這將減少一半的cmp指令數。但是，任何半體面優化編譯器都會爲您做到這一點。

來源

2010-12-04 20:23:10 Tristan

你確定它會有很大的區別嗎？可能性是加載「來自外部來源的ID」將花費比合計值更長的時間。

不要優化，直到你知道瓶頸在哪裏。

編輯回答評論：你誤會了我。如果從硬盤加載ID需要10秒鐘，那麼在處理列表時花費的秒數是非常重要的。可以說加載需要10秒，處理需要1秒：

您優化了處理循環，所以它需要0秒（幾乎不可能，但它說明一個點），那麼它仍然需要10秒鐘。 11秒真的不是性能受到影響，你最好把你的優化時間集中在實際的數據負載上，因爲這很可能是緩慢的部分。

事實上，雙緩衝數據加載可能是非常理想的。即加載緩衝區0，然後啓動緩衝區1的加載。當緩衝區1正在加載進程緩衝區0.完成時，啓動下一個緩衝區的處理，同時處理緩衝區1，等等。這樣你可以完全分攤處理成本。

進一步編輯：事實上，您的最佳優化可能來自加載到一組桶中，消除了te計算的「id [i]」部分。然後您可以簡單地卸載到3個線程，每個線程使用SSE添加。通過這種方式，你可以讓它們全部同時進行，並且，如果你至少有一臺三核機器，則可以在10秒內處理整個數據。組織數據以獲得最佳處理將始終允許進行最佳優化，IMO。

來源

2010-12-04 20:24:18 Goz

根據你的目標機器和編譯器，看看你是否有_mm_prefetch內在屬性並給它一個鏡頭。回到Pentium D時代，只要您在需要數據之前預取幾次循環迭代，使用該內在函數的asm指令預取數據是真正的速度勝利。

請參閱here（第95頁，在PDF中）瞭解更多英特爾信息。

來源

2010-12-04 20:41:24 JimR

這個計算是平行的;只需添加

的#pragma OMP parallel_for時減少（+：大小，+：總和）（-fopenmp在GCC）時間表（靜態）

立即上述循環，如果您有支持OpenMP不過，我不希望在典型的多核臺式機上加快速度;你所做的每個項目的計算量很小，幾乎肯定會受到內存帶寬的限制。

如果您需要對給定的id映射執行多次求和（即值[]數組的更改頻率比id []更頻繁），則可以通過預先對值[]元素進行排序來減少內存帶寬需求入ID順序和消除每個元件從ID []取：

爲（I = 0，J = 0，K = 0;Ĵ< 10;和[J] + = TMP，J ++）

用於第（k + =大小[J]，TMP = 0;我< K表;我++）

tmp += value[i];

來源

2010-12-05 16:08:30 spillner

優化索引陣列求和

回答

相關問題