使用預取加速隨機內存訪問

我想通過使用預取來加速單個程序。我的程序的目的只是爲了測試。這裏是做什麼的：使用預取加速隨機內存訪問

它同樣採用了尺寸

的兩個int緩衝區它讀取一個接一個的第一緩衝器的所有值

它的索引讀取值在第二緩衝

它總結從第一緩衝

它所有越做越大

前面的步驟最後，我打印自願和非自願CP的數量所採取的所有數值U

在第一次，第一次緩衝區中的值包含其索引的值（參見圖1）。功能createIndexBuffer在下面的代碼中）。

這將是我的程序的代碼更加清晰：

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
#include <sys/time.h> 

#define BUFFER_SIZE ((unsigned long) 4096 * 100000) 


unsigned int randomUint() 
{ 
    int value = rand() % UINT_MAX; 
    return value; 
} 


unsigned int * createValueBuffer() 
{ 
    unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    valueBuffer[i] = randomUint(); 
    } 

    return (valueBuffer); 
} 


unsigned int * createIndexBuffer() 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = i; 
    } 

    return (indexBuffer); 
} 


unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer) 
{ 
    unsigned long long sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    unsigned int index = indexBuffer[i]; 
    sum += valueBuffer[index]; 
    } 

    return (sum); 
} 


unsigned int computeTimeInMicroSeconds() 
{ 
    unsigned int * valueBuffer = createValueBuffer(); 
    unsigned int * indexBuffer = createIndexBuffer(); 

    struct timeval startTime, endTime; 
    gettimeofday(&startTime, NULL); 

    unsigned long long sum = computeSum(indexBuffer, valueBuffer); 

    gettimeofday(&endTime, NULL); 

    printf("Sum = %llu\n", sum); 
    free(indexBuffer); 
    free(valueBuffer); 

    return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec); 

} 


int main() 
{ 
    printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int)/(1024 * 1024)); 
    unsigned int timeInMicroSeconds = computeTimeInMicroSeconds(); 
    printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds/(1000 * 1000)); 
}

如果我啓動它，我得到以下的輸出：

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb 
Sum = 439813150288855829 
Time: 201172 micro-seconds = 0.201 seconds

快速，快捷！根據我的知識（我可能是錯的），有這樣一個快速程序的原因之一是，當我順序訪問我的兩個緩衝區時，可以在CPU緩存中預取數據。

我們可以使它更復雜，以便數據（幾乎）在CPU緩存中處於優先地位。例如，我們可以只改變createIndexBuffer功能：

unsigned int * createIndexBuffer() 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = rand() % BUFFER_SIZE; 
    } 

    return (indexBuffer); 
}

讓我們再次嘗試程序：慢

$ gcc TestPrefetch.c -O3 -o TestPrefetch && ./TestPrefetch 
sizeof buffers = 1562Mb 
Sum = 439835307963131237 
Time: 3730387 micro-seconds = 3.730 seconds

18倍以上！

我們現在到達我的問題。鑑於新createIndexBuffer功能，我想使用prefetch加快computeSum功能

unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer) 
{ 
    unsigned long long sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    __builtin_prefetch((char *) &indexBuffer[i + 1], 0, 0); 
    unsigned int index = indexBuffer[i]; 
    sum += valueBuffer[index]; 
    } 

    return (sum); 
}

當然我也不得不改變我createIndexBuffer爲了它分配有一個多元素

我重新啓動一個緩衝我的程序：不是更好！由於預取可能會慢於一個「for」循環迭代，我可以過，但兩個元素之前

__builtin_prefetch((char *) &indexBuffer[i + 2], 0, 0);

不是更好不預取一個元素！兩個循環迭代？ 不是更好？三？ **我嘗試了它直到50（!!!），但我無法提高我的功能computeSum的性能。

可我想幫助理解爲什麼非常感謝您的幫助

來源

2016-12-03 Philippe MESMEUR

我相信，上面的代碼是由CPU無需手動優化任何進一步的空間自動優化。

1.主要問題是indexBuffer被順序訪問。硬件預取器可以感知並自動預取更多值，而無需手動調用預取。因此，在迭代#i期間，值indexBuffer[i+1]，indexBuffer[i+2]，...已經在緩存中。（順便說一下，沒有必要在陣列末尾添加人爲元素：內存訪問錯誤被預取指令無聲地忽略）。

你真正需要做的是預取valueBuffer代替：

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + 1]], 0, 0);

2.但是上面添加一行代碼也不會在這種簡單的場景幫助。訪問內存的成本是數百個週期，而添加指令是〜1個週期。你的代碼已經花費了99％的時間訪問內存。添加手動預取將使其更快，而且不會更好。如果你的數學比較沉重（試一試），比如使用一個有大量未優化的外部表達式（每個20-30個週期）或者調用一些數學函數（log，罪）。

但是，即使這並不能保證提供幫助。循環迭代之間的依賴性非常弱，只能通過sum變量。這使得CPU來推測執行指令：它可能開始獲取valueBuffer[i+1]同時，同時仍然執行數學爲valueBuffer[i]。

來源

2016-12-03 19:09:18 gudok

我對你的'罪'建議的回答高於你的答案，而不是低於（我確實犯了一個錯誤...） –

對不起。我給你的是不是我的代碼的正確版本。正確的版本是，你說的話：

__builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0);

然而，即使有正確的版本，這是不幸的是沒有更好的

來源

2016-12-03 22:27:15

然後我適應我的程序中使用sin功能來試試你的建議。

我的適應程序是以下之一：

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 
#include <sys/time.h> 
#include <math.h> 

#define BUFFER_SIZE ((unsigned long) 4096 * 50000) 


unsigned int randomUint() 
{ 
    int value = rand() % UINT_MAX; 
    return value; 
} 


unsigned int * createValueBuffer() 
{ 
    unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    valueBuffer[i] = randomUint(); 
    } 

    return (valueBuffer); 
} 


unsigned int * createIndexBuffer(unsigned short prefetchStep) 
{ 
    unsigned int * indexBuffer = (unsigned int *) malloc((BUFFER_SIZE + prefetchStep) * sizeof(unsigned int)); 
    for (unsigned long i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    indexBuffer[i] = rand() % BUFFER_SIZE; 
    } 

    return (indexBuffer); 
} 


double computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer, unsigned short prefetchStep) 
{ 
    double sum = 0; 

    for (unsigned int i = 0 ; i < BUFFER_SIZE ; i++) 
    { 
    __builtin_prefetch((char *) &valueBuffer[indexBuffer[i + prefetchStep]], 0, 0); 
    unsigned int index = indexBuffer[i]; 
    sum += sin(valueBuffer[index]); 
    } 

    return (sum); 
} 


unsigned int computeTimeInMicroSeconds(unsigned short prefetchStep) 
{ 
    unsigned int * valueBuffer = createValueBuffer(); 
    unsigned int * indexBuffer = createIndexBuffer(prefetchStep); 

    struct timeval startTime, endTime; 
    gettimeofday(&startTime, NULL); 

    double sum = computeSum(indexBuffer, valueBuffer, prefetchStep); 

    gettimeofday(&endTime, NULL); 

    printf("prefetchStep = %d, Sum = %f - ", prefetchStep, sum); 
    free(indexBuffer); 
    free(valueBuffer); 

    return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec); 

} 


int main() 
{ 
    printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int)/(1024 * 1024)); 
    for (unsigned short prefetchStep = 0 ; prefetchStep < 250 ; prefetchStep++) 
    { 
    unsigned int timeInMicroSeconds = computeTimeInMicroSeconds(prefetchStep); 
    printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds/(1000 * 1000)); 
    } 
}

輸出是：

$ gcc TestPrefetch.c -O3 -o TestPrefetch -lm && taskset -c 7 ./TestPrefetch 
sizeof buffers = 781Mb 
prefetchStep = 0, Sum = -1107.523504 - Time: 20895326 micro-seconds = 20.895 seconds 
prefetchStep = 1, Sum = 13456.262424 - Time: 12706720 micro-seconds = 12.707 seconds 
prefetchStep = 2, Sum = -20179.289469 - Time: 12136174 micro-seconds = 12.136 seconds 
prefetchStep = 3, Sum = 12068.302534 - Time: 11233803 micro-seconds = 11.234 seconds 
prefetchStep = 4, Sum = 21071.238160 - Time: 10855348 micro-seconds = 10.855 seconds 
prefetchStep = 5, Sum = -22648.280105 - Time: 10517861 micro-seconds = 10.518 seconds 
prefetchStep = 6, Sum = 22665.381676 - Time: 9205809 micro-seconds = 9.206 seconds 
prefetchStep = 7, Sum = 2461.741268 - Time: 11391088 micro-seconds = 11.391 seconds 
...

所以在這裏，它工作得更好！坦率地說，我幾乎可以肯定它不會更好，因爲與存儲器訪問相比，數學函數的成本更高。

如果有人能給我爲什麼是現在好多了更多信息，我將不勝感激

非常感謝您

來源

2016-12-03 22:38:46

預取通常取一個完整的高速緩存行。這是typically 64 bytes。所以這個隨機的例子總是爲4個字節的int獲取64個字節。實際需要的數據量是您實際需要的數據量的16倍，非常適合緩慢下降18倍。因此，代碼僅受內存吞吐量的限制，而不是延遲。

來源

2016-12-04 13:52:34 FPK

使用預取加速隨機內存訪問

回答

相關問題