17
在x86_64上使用gcc 4.4.5（是的......我知道這是舊的）。由於兼容性原因，限於SSE2（或更早版本）的說明。我如何從預取內在函數中獲得可測量的好處？
我有什麼我認爲應該是一個教科書的情況下從預取獲得巨大的好處。我有一個32位元素的數組（「A」），它們不是（也不是）按順序排列。這些32位元素是指向__m128i數據的較大數據數組（「D」）的索引。對於「A」的每個元素，我需要從「D」中的相應位置獲取__m128i數據，對其執行操作，並將其存儲回「D」中的相同位置。其實D中的每個「入口」都是「SOME_CONST」__m128i的大。所以如果A中的值是「1」，那麼進入D的索引就是D [1 * SOME_CONST]。
因爲「A」中的連續元素幾乎不會指向「D」中的連續位置，所以我傾向於認爲硬件預取器將會努力或無法完成任何有用的事情。
但是，我可以很容易地預測下一個我將訪問的位置，只需向前看「A」即可。足夠的措辭......這裏有一些代碼。我對數據執行的操作是取__m128i的低64位，並將其克隆到同一高位的64位。首先，基本的循環，沒有多餘的裝飾...
// SOME_CONST is either 3 or 4, but this "operation" only needs to happen for 3
for (i=0; i<arraySize; ++i)
{
register __m128i *dPtr = D + (A[i] * SOME_CONST);
dPtr[0] = _mm_shuffle_epi32(dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr[1] = _mm_shuffle_epi32(dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr[2] = _mm_shuffle_epi32(dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6));
// The immediate operand selects:
// Bits 0-31 = bits 0-31
// Bits 32-63 = bits 32-63
// Bits 64-95 = bits 0-31
// Bits 96-127 = bits 32-63
// If anyone is more clever than me and knows of a better way to do this in SSE2,
// bonus points. ;-)
}
我已經嘗試了許多不同的方式來灑預取instrinsics在那裏，並沒有導致任何一種加速的呢。例如，我想展開循環，有2個或甚至4元一大步，但它並沒有幫助...
// Assume the "A" array size is appropriately padded so that overruns don't
// result in SIGSEGV accessing uninitialized memory in D.
register __m128i *dPtr0, *dPtr1, *dPtr2, *dPtr3, *dPtr4, *dPtr5, *dPtr6, *dPtr7;
dPtr4 = D + (A[0] * SOME_CONST);
dPtr5 = D + (A[1] * SOME_CONST);
dPtr6 = D + (A[2] * SOME_CONST);
dPtr7 = D + (A[3] * SOME_CONST);
for (i=0; i<arraySize; i+=4)
{
dPtr0 = dPtr4;
dPtr1 = dPtr5;
dPtr2 = dPtr6;
dPtr3 = dPtr7;
dPtr4 = D + (A[i+4] * SOME_CONST);
_mm_prefetch(dPtr4, _MM_HINT_NTA);
_mm_prefetch(dPtr4+1, _MM_HINT_NTA); // Is it needed? Tried both ways
dPtr5 = D + (A[i+5] * SOME_CONST);
_mm_prefetch(dPtr5, _MM_HINT_NTA);
_mm_prefetch(dPtr5+1, _MM_HINT_NTA); // Is it needed? Tried both ways
dPtr6 = D + (A[i+6] * SOME_CONST);
_mm_prefetch(dPtr6, _MM_HINT_NTA);
_mm_prefetch(dPtr6+1, _MM_HINT_NTA); // Is it needed? Tried both ways
dPtr7 = D + (A[i+7] * SOME_CONST);
_mm_prefetch(dPtr7, _MM_HINT_NTA);
_mm_prefetch(dPtr7+1, _MM_HINT_NTA); // Is it needed? Tried both ways
dPtr0[0] = _mm_shuffle_epi32(dPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr0[1] = _mm_shuffle_epi32(dPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr0[2] = _mm_shuffle_epi32(dPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr1[0] = _mm_shuffle_epi32(dPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr1[1] = _mm_shuffle_epi32(dPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr1[2] = _mm_shuffle_epi32(dPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr2[0] = _mm_shuffle_epi32(dPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr2[1] = _mm_shuffle_epi32(dPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr2[2] = _mm_shuffle_epi32(dPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr3[0] = _mm_shuffle_epi32(dPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr3[1] = _mm_shuffle_epi32(dPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr3[2] = _mm_shuffle_epi32(dPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6));
}
這是4元的版本，但我也試圖與只有2這種情況太多，數據無法擺動。另外我嘗試使用_MM_HINT_NTA和_MM_HINT_T0。不知何故，沒有明顯的區別。
我也試過一個簡單的變型，這只是嘗試把儘可能多的空間，似乎預取之間的合理，以及何時使用：
#define PREFETCH_DISTANCE 10
// trying 5 overnight, will see results tomorrow...
for (i=0; i<arraySize; ++i)
{
register __m128i *dPtrFuture, *dPtr;
dPtrFuture = D + (A[i + PREFETCH_DISTANCE] * SOME_CONST);
_mm_prefetch(dPtrFuture, _MM_HINT_NTA); // tried _MM_HINT_T0 too
_mm_prefetch(dPtrFuture + 1, _MM_HINT_NTA); // tried _MM_HINT_T0 too
dPtr = D + (A[i] * SOME_CONST);
dPtr[0] = _mm_shuffle_epi32(dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr[1] = _mm_shuffle_epi32(dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6));
dPtr[2] = _mm_shuffle_epi32(dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6));
}
起初，我希望這個代碼來搪塞，但一旦得到「PREFETCH_DISTANCE」到循環中，我希望它會看到足夠的速度提升。這些變體中的大多數在每百萬次迭代中運行時間差異不超過0.2秒，這需要4m的總CPU時間：在特定機器上（這是除我以外的石頭閒置）的30秒。差異似乎與數據中的「噪音」沒有區別。
我正確的假設預取應該能夠幫助我嗎？如果是這樣，我做錯了什麼？
所有有用的和有趣的想法，讚賞。
編輯：
我創建的真正隨機化在A.我從64MB到6400MB緩衝器大小播放的數據一個人爲的例子。我發現，當我在當前4上執行我的操作時，我展開展開循環並預先計算接下來的4個元素的地址，但我的運行時間坦克的係數大於10倍，如果我嘗試預取我預先計算的任何地址。我真的在這個問題上撓頭。我的獨立做作的代碼是：
#include <xmmintrin.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define QUEUE_ELEMENTS 1048576
#define DATA_ELEMENT_SIZE 4 * sizeof(__m128i)
#define DATA_ELEMENTS QUEUE_ELEMENTS
#define QUEUE_ITERATIONS 100000
#define LOOP_UNROLL_4
#define LOOP_UNROLL_2
#ifdef LOOP_UNROLL_4
#define UNROLL_CONST 4
#else
#ifdef LOOP_UNROLL_2
#define UNROLL_CONST 2
#else
#define UNROLL_CONST 1
#endif
#endif
int main(void)
{
unsigned long long randTemp;
unsigned long i, outerLoop;
unsigned long *workQueue;
__m128i *data, *dataOrig;
clock_t timeStamp;
workQueue = malloc(QUEUE_ELEMENTS * sizeof(unsigned long));
dataOrig = malloc((DATA_ELEMENTS * DATA_ELEMENT_SIZE) + 2);
if ((unsigned long long) dataOrig & 0xf)
{
data = (__m128i *) (((unsigned long long) dataOrig & ~0xf) + 0x10);
// force 16-byte (128-bit) alignment
} else data = dataOrig;
// Not initializing data, because its contents isn't important.
for (i=0; i<QUEUE_ELEMENTS; ++i)
{
randTemp = (unsigned long long)rand() *
(unsigned long long) QUEUE_ELEMENTS/(unsigned long long) RAND_MAX;
workQueue[i] = (unsigned long) randTemp;
}
printf("Starting work...\n");
// Actual work happening below... start counting.
timeStamp = clock();
for (outerLoop = 0; outerLoop < QUEUE_ITERATIONS; ++outerLoop)
{
register __m128i *dataPtr0, *dataPtr1, *dataPtr2, *dataPtr3;
register __m128i *dataPtr4, *dataPtr5, *dataPtr6, *dataPtr7;
#ifdef LOOP_UNROLL_2
dataPtr4 = data + (workQueue[0] * DATA_ELEMENT_SIZE);
dataPtr5 = data + (workQueue[1] * DATA_ELEMENT_SIZE);
#endif
#ifdef LOOP_UNROLL_4
dataPtr6 = data + (workQueue[2] * DATA_ELEMENT_SIZE);
dataPtr7 = data + (workQueue[3] * DATA_ELEMENT_SIZE);
#endif
for (i=0; i<QUEUE_ELEMENTS; i+=UNROLL_CONST)
{
#ifdef LOOP_UNROLL_2
dataPtr0 = dataPtr4;
dataPtr4 = data + (workQueue[i+4] * DATA_ELEMENT_SIZE);
// _mm_prefetch(dataPtr4, _MM_HINT_T0);
dataPtr1 = dataPtr5;
dataPtr5 = data + (workQueue[i+5] * DATA_ELEMENT_SIZE);
// _mm_prefetch(dataPtr5, _MM_HINT_T0);
#endif
#ifdef LOOP_UNROLL_4
dataPtr2 = dataPtr6;
dataPtr6 = data + (workQueue[i+6] * DATA_ELEMENT_SIZE);
// _mm_prefetch(dataPtr6, _MM_HINT_T0);
dataPtr3 = dataPtr7;
dataPtr7 = data + (workQueue[i+7] * DATA_ELEMENT_SIZE);
// _mm_prefetch(dataPtr7, _MM_HINT_T0);
#endif
#if !defined(LOOP_UNROLL_2) && !defined(LOOP_UNROLL_4)
dataPtr0 = data + (workQueue[i] * DATA_ELEMENT_SIZE);
#endif
_mm_shuffle_epi32(dataPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6));
// Per original code, no need to perform operation on dataPtrx[3]
#ifdef LOOP_UNROLL_2
_mm_shuffle_epi32(dataPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6));
#endif
#ifdef LOOP_UNROLL_4
_mm_shuffle_epi32(dataPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6));
_mm_shuffle_epi32(dataPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6));
#endif
}
if ((outerLoop % 1000) == 0) { putchar('.'); fflush(stdout); }
}
timeStamp = clock() - timeStamp;
printf("\nRun was %lu seconds.\n", timeStamp/CLOCKS_PER_SEC);
free(dataOrig);
free(workQueue);
return 0;
}
- 我與LOOP_UNROLL_2運行時間爲40秒。
- 我的運行時LOOP_UNROLL_4是20秒。
- 沒有任何展開的我的運行時間是80秒。
- 當我啓用預取時，運行時間很長，我只是殺死進程而不是等待它。
我甚至寫了一個8倍展開循環，它仍然完美地縮放到10秒的運行時間。我很驚訝它沒有飽和，因爲那時我肯定會用盡寄存器，持有16個獨特的指針。那麼我能從中學到什麼？我的內部循環代碼是如此之緊以至於它被循環構造本身的開銷所掩蓋？這段代碼中有沒有錯誤，我沒有看到？所有版本都與gcc -O2。
一般來說，除了一些非常特殊的情況外，顯式預取並不能幫助您理解現代CPU，即使如此，確保正確預取也是非常棘手的。如果你弄錯了，它甚至會造成更多的傷害。還要注意，在這裏已經有很多非常相似（可能重複）的問題和答案，您可能想閱讀。見例如http://stackoverflow.com/questions/23741246/why-is-prefetch-speedup-not-greater-in-this-example – 2014-09-20 08:59:45
瞭解，保羅。我在這裏搜索了這些問題，大部分答案是「不要這樣做，因爲硬件會做得更好」（在這種情況下也是如此）。但是我想明白爲什麼這個特定的案例不能從中受益，因爲它需要對更大的陣列進行相當「隨機的」（但完全是人類可預測的）訪問。我確定硬件無法自行理解訪問模式。 – Marty 2014-09-20 09:08:42
數據轉置是我從手動預取中獲得明顯加速的唯一時間之一：http://stackoverflow.com/questions/7327994/prefetching-examples – Mysticial 2014-09-20 09:11:38