這段代碼的瓶頸在哪裏？

我有以下緊密的循環組成我的代碼的系列瓶頸。理想情況下，我會平行調用這個函數，但這是不可能的。這段代碼的瓶頸在哪裏？

//n is about 60 
for (int k = 0;k < n;k++) 
{ 
    double fone = z[k*n+i+1]; 
    double fzer = z[k*n+i]; 
    z[k*n+i+1]= s*fzer+c*fone; 
    z[k*n+i] = c*fzer-s*fone; 
}

是否有可製成如矢量或一些邪惡的內聯，可以幫助這個代碼的優化？

我正在尋找尋找三對角矩陣的本徵解。 http://www.cimat.mx/~posada/OptDoglegGraph/DocLogisticDogleg/projects/adjustedrecipes/tqli.cpp.html

來源

2012-12-16 Mikhail

非順序存儲器訪問。期。 – Mysticial

'我'是什麼？是否有涉及它的循環？ – NPE

你有'i'外環嗎？ – chill

簡短回答：將矩陣的內存佈局從行優先級更改爲列主優先級。

龍回答：看來你訪問的第（i）及（i + 1）個存儲在行優先順序矩陣的列 - 可能是一個大的矩陣沒有整體配合進入CPU緩存。基本上，在每次循環迭代時，CPU必須等待RAM（大約數百個週期）。經過一些迭代後，理論上，地址預測應該啓動並且CPU應該在循環執行之前投機性加載數據項。這應該有助於延遲RAM。但是，這仍然會導致代碼使用內存總線效率低下的問題：CPU和內存永遠不會交換單個字節，而只會交換緩存行（當前處理器上的64字節）。在加載和存儲的每64個字節的緩存行中，您的代碼只能觸及16個字節（或四分之一）。

轉置矩陣並以本地主要順序訪問它會增加內存總線利用率四倍。既然這可能是你的代碼的瓶頸，那麼你可以期望加速大約相同的順序。

是否值得，取決於算法的其餘部分。由於改變了內存佈局，其他部分當然可能會受到影響。

來源

2012-12-16 11:13:19

你能擴展一點嗎？「在每64個字節的緩存行加載和存儲你的代碼只接觸16個字節（或四分之一）。」我不明白爲什麼只有16個字節觸及內存總線...... – Mikhail

那麼，在內存事務期間，CPU從不加載或存儲小於緩存行（64字節）的內容。您的代碼加載並存儲16個連續字節：z [k * n + i]，z [k * n + i + 1]。但是，CPU不會加載16個字節，它會加載64個字節 - 包含數據的特定緩存行。在這64個字節中，48個被加載並靜態存儲。他們佔用寶貴的總線資源，但是你的代碼無法利用。 –

我認爲你正在旋轉某些東西（或者說，很多東西，以相同的角度（s是罪，c是cos））？

向後計數總是很好玩，並刪除每次迭代的變量比較，並應在這裏工作。使計數器成爲索引也可以節省一些時間（如其他人所說的那樣，可以省略一點算術）。

for (int k = (n-1) * n + i; k >= 0; k -= n) 
{ 
    double fone=z[k+1]; 
    double fzer=z[k]; 
    z[k+1]=s*fzer+c*fone; 
    z[k] =c*fzer-s*fone; 
}

這裏沒有什麼戲劇性，但看起來，如果沒有別的整潔。

來源

2012-12-16 10:32:24 VisualMelon

我試過運行，我沒有注意到很大的區別。順便說一句，我正在尋找三對角矩陣系統的特徵值。 – Mikhail

作爲第一個舉動我想緩存指針在這個循環：

//n is about 60 
double *cur_z = &z[0*n+i] 
for (int k = 0;k < n;k++) 
{ 
    double fone = *(cur_z+1); 
    double fzer = *cur_z; 
    *(cur_z+1)= s*fzer+c*fone; 
    *cur_z = c*fzer-s*fone; 
    cur_z += n; 
}

其次，我認爲它能夠更好地使該功能的模板化版本。因此，如果矩陣包含整數值（因爲FPU操作較慢），您可以獲得良好的性能優勢。

來源

2012-12-16 11:03:04 PSIAlt

你是什麼意思的模板版本，你的意思是我應該展開整個for循環（我可以做到這一點...）？另外你是什麼意思整數。 – Mikhail

你的矩陣包含** double **值。如果你可以設法處理沒有**雙** - s它將工作得更快 – PSIAlt

這段代碼的瓶頸在哪裏？

回答

相關問題