Prefetching Beispiele?

Hier ist ein tatsächlicher code, ich habe gezogen aus einem größeren Projekt. (Sorry, es ist das kürzeste, das ich finden kann, hatte eine deutliche Beschleunigung von prefetching.)
Dieser code führt eine sehr große Daten transponieren.

In diesem Beispiel verwendet die SSE-prefetch-Anweisungen, die möglicherweise das gleiche wie die, die der GCC emittiert.

Um dieses Beispiel auszuführen, müssen Sie zum kompilieren dieses für x64 und mehr als 4 GB Speicher. Sie können es mit einem kleineren datasize, aber es wird zu schnell, zu Zeit.

#include <iostream>
using std::cout;
using std::endl;

#include <emmintrin.h>
#include <malloc.h>
#include <time.h>
#include <string.h>

#define ENABLE_PREFETCH


#define f_vector    __m128d
#define i_ptr       size_t
inline void swap_block(f_vector *A,f_vector *B,i_ptr L){
    // To be super-optimized later.

    f_vector *stop = A + L;

    do{
        f_vector tmpA = *A;
        f_vector tmpB = *B;
        *A++ = tmpB;
        *B++ = tmpA;
    }while (A < stop);
}
void transpose_even(f_vector *T,i_ptr block,i_ptr x){
    // Transposes T.
    // T contains x columns and x rows.
    // Each unit is of size (block * sizeof(f_vector)) bytes.

    //Conditions:
    // - 0 < block
    // - 1 < x

    i_ptr row_size = block * x;
    i_ptr iter_size = row_size + block;

    // End of entire matrix.
    f_vector *stop_T = T + row_size * x;
    f_vector *end = stop_T - row_size;

    // Iterate each row.
    f_vector *y_iter = T;
    do{
        // Iterate each column.
        f_vector *ptr_x = y_iter + block;
        f_vector *ptr_y = y_iter + row_size;

        do{

#ifdef ENABLE_PREFETCH
            _mm_prefetch((char*)(ptr_y + row_size),_MM_HINT_T0);
#endif

            swap_block(ptr_x,ptr_y,block);

            ptr_x += block;
            ptr_y += row_size;
        }while (ptr_y < stop_T);

        y_iter += iter_size;
    }while (y_iter < end);
}
int main(){

    i_ptr dimension = 4096;
    i_ptr block = 16;

    i_ptr words = block * dimension * dimension;
    i_ptr bytes = words * sizeof(f_vector);

    cout << "bytes = " << bytes << endl;
//   system("pause");

    f_vector *T = (f_vector*)_mm_malloc(bytes,16);
    if (T == NULL){
        cout << "Memory Allocation Failure" << endl;
        system("pause");
        exit(1);
    }
    memset(T,0,bytes);

    // Perform in-place data transpose
    cout << "Starting Data Transpose...   ";
    clock_t start = clock();
    transpose_even(T,block,dimension);
    clock_t end = clock();

    cout << "Done" << endl;
    cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    _mm_free(T);
    system("pause");
}

Wenn ich es mit ENABLE_PREFETCH aktiviert, dies ist die Ausgabe:

bytes = 4294967296
Starting Data Transpose...   Done
Time: 0.725 seconds
Press any key to continue . . .

Wenn ich es mit ENABLE_PREFETCH deaktiviert, das ist die Ausgabe:

bytes = 4294967296
Starting Data Transpose...   Done
Time: 0.822 seconds
Press any key to continue . . .

So gibt es eine 13% speedup von prefetching.

EDIT:

Hier einige weitere Ergebnisse:

Operating System: Windows 7 Professional/Ultimate
Compiler: Visual Studio 2010 SP1
Compile Mode: x64 Release

Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz
Prefetch   : 0.868
No Prefetch: 0.960

Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz
Prefetch   : 0.725
No Prefetch: 0.822

Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz
Prefetch   : 0.718
No Prefetch: 0.796

2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz
Prefetch   : 2.273
No Prefetch: 2.666

InformationsquelleAutor Mysticial

Habe ich gelernt, eine Menge von der ausgezeichnete Antworten @JamesScriven und @Mystisch. Aber Ihre Beispiele geben nur einen bescheidenen Schub - das Ziel dieser Antwort ist ein (ich muss gestehen, etwas künstlichen) Beispiel, wo dieses Verfahren hat eine größere Wirkung (etwa Faktor 4 auf meinem Rechner).

Gibt es drei mögliche bottle-necks für den modernen Architekturen: CPU-Geschwindigkeit, Speicher-Bandbreite und Speicher-Latenz. Dieses Verfahren wird alle über die Verringerung der Latenzzeiten des Speicher-Zugriffe.

In ein perfektes Szenario, wo die Latenz entspricht X Berechnungs-Schritte, hätten wir einen oracle -, was würden Sie uns sagen, welchen Speicher wir würden in X-Berechnungs-Schritte, die prefetching der Daten veröffentlicht werden sollen, und es würde kommen nur in-time-X Kalkulation-Schritte später.

Für eine Menge von algorithmen, die wir sind (fast) in dieser perfekten Welt. Für eine einfache for-Schleife ist es einfach vorauszusagen, welche Daten werden benötigt, X-Schritte weiter. Out-of-order-Ausführung und andere hardware-tricks machen einen sehr guten job hier, das verbergen der Latenzzeiten fast vollständig.

Das ist der Grund, warum es ist solch eine bescheidene Verbesserung für @Mystischen Beispiel: Der prefetcher ist schon ziemlich gut - es gibt einfach nicht viel Raum für Verbesserung. Die Aufgabe ist auch Speicher-gebunden ist, also wohl nicht viel Bandbreite übrig ist - es könnte immer der limitierende Faktor. Ich konnte sehen, am besten um 8% Verbesserung auf meinem Rechner.

Die entscheidende Erkenntnis aus der @JamesScriven Beispiel: weder wir, noch die CPU weiß, den nächsten access-Adresse, bevor die die aktuellen Daten aus dem Speicher geholt - diese Abhängigkeit ist ziemlich wichtig, ansonsten out-of-order-Ausführung würde dazu führen, dass Sie einen Blick vorwärts, und wäre die hardware in der Lage sein, um die prefetch-Daten. Allerdings, denn wir können darüber spekulieren, nur ein Schritt, es ist nicht viel potential. Ich war nicht in der Lage, mehr als 40% auf meinem Rechner.

Also lasst rig den Wettbewerb und bereiten die Daten in einer Weise, dass wir wissen, welche Adresse zugegriffen wird, die in X Schritten, aber es unmöglich machen, für die hardware zu finden, die es sich aufgrund von Abhängigkeiten auf noch nicht abgerufene Daten (siehe das gesamte Programm am Ende der Antwort):

//making random accesses to memory:
unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}

//the actual work is happening here
void operator()(){

    //set up the oracle - let see it in the future oracle_offset steps
    unsigned int prefetch_index=0;
    for(int i=0;i<oracle_offset;i++)
        prefetch_index=next(prefetch_index);

    unsigned int index=0;
    for(int i=0;i<STEP_CNT;i++){
        //use oracle and prefetch memory block used in a future iteration
        if(prefetch){
            __builtin_prefetch(mem.data()+prefetch_index,0,1);    
        }

        //actual work, the less the better
        result+=mem[index];

        //prepare next iteration
        prefetch_index=next(prefetch_index);  #update oracle
        index=next(mem[index]);               #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
    }
}

Einige Bemerkungen:

1. Daten so aufbereitet, dass das Orakel immer Recht.
2. vielleicht überraschend, die weniger CPU-gebundene Aufgabe, desto größer ist der speed-up: wir sind in der Lage sich zu verstecken die Latenz fast vollständig, wodurch der speed-up ist CPU-time+original-latency-time/CPU-time.

Kompilieren und ausführen führt:

>>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
>>> ./prefetch_demo
#preloops   time no prefetch    time prefetch   factor
...
7   1.0711102260000001  0.230566831 4.6455521002498408
8   1.0511602149999999  0.22651144600000001 4.6406494398521474
9   1.049024333 0.22841439299999999 4.5926367389641687
....

einer Geschwindigkeit zwischen 4 und 5.

Auflistung der prefetch_demp.cpp:

//prefetch_demo.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>

const int SIZE=1024*1024*1;
const int STEP_CNT=1024*1024*10;

unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}


template<bool prefetch>
struct Worker{
   std::vector<int> mem;

   double result;
   int oracle_offset;

   void operator()(){
        unsigned int prefetch_index=0;
        for(int i=0;i<oracle_offset;i++)
            prefetch_index=next(prefetch_index);

        unsigned int index=0;
        for(int i=0;i<STEP_CNT;i++){
            //prefetch memory block used in a future iteration
            if(prefetch){
                __builtin_prefetch(mem.data()+prefetch_index,0,1);    
            }
            //actual work:
            result+=mem[index];

            //prepare next iteration
            prefetch_index=next(prefetch_index);
            index=next(mem[index]);
        }
   }

   Worker(std::vector<int> &mem_):
       mem(mem_), result(0.0), oracle_offset(0)
   {}
};

template <typename Worker>
    double timeit(Worker &worker){
    auto begin = std::chrono::high_resolution_clock::now();
    worker();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
}


 int main() {
     //set up the data in special way!
     std::vector<int> keys(SIZE);
     for (int i=0;i<SIZE;i++){
       keys[i] = i;
     }

     Worker<false> without_prefetch(keys);
     Worker<true> with_prefetch(keys);

     std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
     std::cout<<std::setprecision(17);

     for(int i=0;i<20;i++){
         //let oracle see i steps in the future:
         without_prefetch.oracle_offset=i;
         with_prefetch.oracle_offset=i;

         //calculate:
         double time_with_prefetch=timeit(with_prefetch);
         double time_no_prefetch=timeit(without_prefetch);

         std::cout<<i<<"\t"
                  <<time_no_prefetch<<"\t"
                  <<time_with_prefetch<<"\t"
                  <<(time_no_prefetch/time_with_prefetch)<<"\n";
     }

 }

InformationsquelleAutor ead

Prefetching-Daten optimiert werden kann, um die Cache-Line-Größe, die für die meisten modernen 64-bit-Prozessoren, 64 bytes, zum Beispiel pre-load ein uint32_t[16] mit einer Anweisung.

Beispielsweise auf ArmV8 ich entdeckte durch Experimente casting der Speicher Zeiger auf einen uint32_t 4x4-matrix Vektor (das ist 64 bytes groß) halbiert die erforderlichen Anweisungen erforderlich, wie zuvor musste ich erhöhen um 8, wie es war, lade nur die Hälfte der Daten, auch wenn mein Verständnis war, dass es holt eine volle cache-Zeile.

Prefetching-eine uint32_t[32] original-code Beispiel...

int addrindex = &B[0];
    __builtin_prefetch(&V[addrindex]);
    __builtin_prefetch(&V[addrindex + 8]);
    __builtin_prefetch(&V[addrindex + 16]);
    __builtin_prefetch(&V[addrindex + 24]);

Nach...

int addrindex = &B[0];
__builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
__builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);

Aus irgendeinem Grund der Datentyp int für die Adresse index/offset Gaben bessere Leistung. Getestet mit GCC-8 auf Cortex-a53. Mit einem gleichwertig 64-byte-Vektor auf andere Architekturen werden möglicherweise geben die gleiche Leistungsverbesserung, wenn Sie finden, dass es nicht pre-fetching alle Daten, wie in meinem Fall. In meiner Anwendung mit einer million iteration Schleife Leistungssteigerung von 5%, gerade dies zu tun. Es wurden weitere Voraussetzungen für die Verbesserung.

den 128 megabyte "V" memory allocation werden musste, ausgerichtet auf 64 bytes.

uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));

Ich hatte auch die C-Operatoren anstelle von Neon-Interna, da Sie erfordern regelmäßige Datentyp Zeiger (in meinem Fall war es uint32_t *), da ansonsten der neue gebaut in den prefetch-Methode hatte einen performance-regression.

Mein reales Beispiel finden Sie unter https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c in der scrypt_core() und seine interne Funktion, die alle leicht zu Lesen. Die harte Arbeit erfolgt durch GCC8. Allgemeine Verbesserung der Leistung auf 25%.

InformationsquelleAutor Rauli Kumpulainen