J'ai beaucoup appris des excellentes réponses fournies par @JamesScriven et @Mystical. Cependant, leurs exemples ne donnent qu'une impulsion modeste - l'objectif de cette réponse est de présenter un exemple (je dois avouer qu'il est quelque peu artificiel), où le prefetching a un impact plus important (environ facteur 4 sur ma machine).
Il existe trois goulets d'étranglement possibles pour les architectures modernes : la vitesse du processeur, la largeur de bande de la mémoire et la latence de la mémoire. Le préemption consiste à réduire la latence des accès à la mémoire.
Dans un scénario parfait, où la latence correspond à X étapes de calcul, nous disposerions d'un oracle qui nous indiquerait à quelle mémoire nous devons accéder en X étapes de calcul, la préextraction de ces données serait lancée et elles arriveraient juste à temps X étapes de calcul plus tard.
Pour beaucoup d'algorithmes, nous sommes (presque) dans ce monde parfait. Pour une simple boucle for, il est facile de prévoir quelles données seront nécessaires X étapes plus tard. L'exécution hors ordre et d'autres astuces matérielles font un très bon travail ici, en dissimulant presque complètement la latence.
C'est la raison pour laquelle l'amélioration est si modeste dans l'exemple de @Mystical : Le préempteur est déjà assez bon - il n'y a tout simplement pas beaucoup de place pour l'amélioration. La tâche est également liée à la mémoire, donc il ne reste probablement pas beaucoup de bande passante - cela pourrait devenir le facteur limitant. Je pourrais voir au mieux environ 8% d'amélioration sur ma machine.
Le point crucial de l'exemple de @JamesScriven : ni nous ni le CPU ne connaissons l'adresse d'accès suivante avant que les données actuelles ne soient extraites de la mémoire - cette dépendance est assez importante, sinon l'exécution hors ordre conduirait à un look-forward et le matériel serait capable de prélever les données. Cependant, comme nous ne pouvons spéculer que sur une seule étape, il n'y a pas beaucoup de potentiel. Je n'ai pas été capable d'obtenir plus de 40% sur ma machine.
Nous allons donc truquer la compétition et préparer les données de telle sorte que nous sachions quelle adresse est accédée en X étapes, mais qu'il soit impossible pour le matériel de la découvrir en raison de dépendances sur des données non encore accédées (voir le programme complet à la fin de la réponse) :
//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
}
}
Quelques remarques :
- Les données sont préparées de manière à ce que l'oracle ait toujours raison.
- Il est peut-être surprenant de constater que plus la tâche est limitée par le processeur, plus l'accélération est importante : nous sommes en mesure de masquer presque complètement la latence, ce qui fait que l'accélération est de 1,5 million d'euros.
CPU-time+original-latency-time/CPU-time .
Compilation et exécution des pistes :
>>> 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
....
à une accélération entre 4 et 5.
Liste des 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";
}
}
