Я пытаюсь оптимизировать closest pair brute force algorithm и сравнивать его с не кэшированной программой, но я застрял.Реализация метода кэширования в алгоритме ближайших пар
Основная проблема заключается в том, что я получаю худшую производительность, когда я кэширую вычисления с помощью циклов for, почти cached time = 2 x non-cached time. Его как будто ничего не происходит, если я изменить размер блока ... Я использую точку массива структура Р для х, у cordinates
Вот без кеширования код:
void compare_points_BF(int *N, point *P){
int i, j, p1, p2;
float dx, dy, distance=0, min_dist=inf();
long calc = 0;
for (i=0; i<(*N-1) ; i++){
for (j=i+1; j<*N; j++){
dx = P[i].x - P[j].x;
dy = P[i].y - P[j].y;
//calculate distance of current points
distance = (dx * dx) + (dy * dy);
calc++;
if (distance < min_dist){
min_dist = distance;
p1 = i;
p2 = j;
}
}
}
printf("%ld calculations\t", calc);
}
И вот кэшируются версия:
void compare_points_BF(int *N, int *B, point *P){
int i, j, ib, jb, p1, p2, num_blocks = (*N + (*B-1))/(*B);
float dist=0, min_dist=inf();
long calc=0;
//break array data in N/B blocks
for (i = 0; i < num_blocks; i++){
for (j = i; j < num_blocks; j++){
for (jb = j * (*B); jb < min((j+1) * (*B), *N); jb++){
//avoid double comparisons that occur when i block = j block
for (i == j ? (ib = jb + 1) : (ib = i*(*B)); ib < min((i+1) * (*B), *N); ib++){
calc++;
//calculate distance of current points
if((dist = (P[ib].x - P[jb].x) * (P[ib].x - P[jb].x) +
(P[ib].y - P[jb].y) * (P[ib].y - P[jb].y)) < min_dist){
min_dist = dist;
p1 = ib;
p2 = jb;
}
}
}
}
}
printf("%ld calculations\t", calc);
}
Например выход некэшируемых программ:
N = 8192 Run time: 0,080 sec
N = 16384 Run time: 0,330 sec
N = 32768 Run time: 1,280 sec
N = 65.536 Run time: 5,290 sec
N = 131.072 Run time: 21,290sec
N = 262.144 Run time: 81,880sec
N = 524.288 Run time: 327,460 sec
Но с КК hed пример:
33550336 calculations Block_size = 128 N = 8192 Run time: 0.402 sec
33550336 calculations Block_size = 256 N = 8192 Run time: 0.383 sec
33550336 calculations Block_size = 512 N = 8192 Run time: 0.384 sec
33550336 calculations Block_size = 1024 N = 8192 Run time: 0.381 sec
33550336 calculations Block_size = 2048 N = 8192 Run time: 0.398 sec
33550336 calculations Block_size = 4096 N = 8192 Run time: 0.400 sec
33550336 calculations Block_size = 8192 N = 8192 Run time: 0.401 sec
33550336 calculations Block_size = 16384 N = 8192 Run time: 0.383 sec
134209536 calculations Block_size = 128 N = 16384 Run time: 1.579 sec
134209536 calculations Block_size = 256 N = 16384 Run time: 1.610 sec
134209536 calculations Block_size = 512 N = 16384 Run time: 1.630 sec
134209536 calculations Block_size = 1024 N = 16384 Run time: 1.530 sec
134209536 calculations Block_size = 2048 N = 16384 Run time: 1.537 sec
134209536 calculations Block_size = 4096 N = 16384 Run time: 1.562 sec
134209536 calculations Block_size = 8192 N = 16384 Run time: 1.520 sec
134209536 calculations Block_size = 16384 N = 16384 Run time: 1.626 sec
536854528 calculations Block_size = 128 N = 32768 Run time: 6.170 sec
536854528 calculations Block_size = 256 N = 32768 Run time: 6.207 sec
536854528 calculations Block_size = 512 N = 32768 Run time: 6.219 sec
536854528 calculations Block_size = 1024 N = 32768 Run time: 6.131 sec
536854528 calculations Block_size = 2048 N = 32768 Run time: 6.077 sec
536854528 calculations Block_size = 4096 N = 32768 Run time: 6.216 sec
536854528 calculations Block_size = 8192 N = 32768 Run time: 6.130 sec
536854528 calculations Block_size = 16384 N = 32768 Run time: 6.181 sec
Я проверял код заново, и это кажется правильным. Что мне здесь не хватает? Компилятор оптимизирует код для реализации лучшего использования кеша, чем я пытаюсь достичь? Спасибо заранее!
Четыре вложенных цикла по сравнению с двумя, и, похоже, больше выражений для оценки в вашей «кешированной» версии. Нет, это не будет быстрее. –
@JoachimPileborg Но как я должен ломать данные в блоках, не используя дополнительные для циклов? Хотя, вычисления одинаковы. – BugShotGG
Вы считаете количество вложенных циклов как «вычисление», но в вашей «кешированной» версии есть еще много выражений. Ваша «нераскрытая» версия проста, простая часто бывает хорошей. И даже если вам удастся сжать на один или два процента лучшее время исполнения, часто это делается с усложнением алгоритмов и, следовательно, гораздо труднее понять. –