Время многопоточного выполнения медленное в Ubuntu и быстрое в Windows ⇐ C++

[Anonymous]

Я работаю над проектом, ускоряющим выполнение генетического алгоритма как на нескольких ядрах, так и на графическом процессоре. Алгоритм специально подходит для решения задачи коммивояжера в двумерном симметричном евклидовом пространстве.
Я разместил все функции, начиная с разработки Версия CUDA для графического процессора и последующая с простой реализацией одноядерного, и поскольку там, как и ожидалось, ускорение было заметным и последовательным, масштабирование действительно хорошее в зависимости от общего числа задействованных пользователей. в естественном отборе.
Затем я решил сравнить обе версии с многоядерной реализацией.
РЕДАКТИРОВАТЬ:
Короче говоря, мои многопоточные версии работают очень медленно в Ubuntu 22.04.4, но в Windows 10 тот же код почти идеален и на удивление хорошо масштабируется с увеличением потоки. Вот воспроизводимый фрагмент кода (необходим файл 48_cities.txt):

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 

#define pathSize 48
#define popSize 64000
#define subPopSize 32
#define threads 4

void random_shuffle(int *population, int sub_pop_num){
for (int i = 0; i < sub_pop_num * subPopSize; i++){
// Avoid last thread to overflow the islands (sub-populations)
if (i >= popSize) break;
// shuffle the ith chromosome
int gene;
for (int j = 0; j < pathSize; j++){
int idx1 = (int)((rand()/(RAND_MAX+1.0)) * pathSize);
int idx2 = (int)((rand()/(RAND_MAX+1.0)) * pathSize);
gene = population[i*pathSize + idx1];
population[i*pathSize + idx1] = population[i*pathSize + idx2];
population[i*pathSize + idx2] = gene;
}
}
}

double calculate_distance(int *chromosome, double *distance_matrix){
double distance = 0.0;
for (int i = 0; i < pathSize-1; i++){
distance += distance_matrix[chromosome[i]*pathSize + chromosome[i+1]];
}
distance += distance_matrix[chromosome[pathSize-1]*pathSize + chromosome[0]];
return distance;
}

void calculate_scores(int *population, double *distance_matrix, double *population_fitness, double *population_distances, int sub_pop_num){
for (int i = 0; i < sub_pop_num * subPopSize; i++){
// Avoid last thread to overflow the islands (sub-populations)
if (i >= popSize) break;
population_distances[i] = calculate_distance(population + i * pathSize, distance_matrix);
population_fitness[i] = 1000/population_distances[i];
}
}

void load_data(int *coordinates, const char *filename){
// read filename
FILE *file = fopen(filename, "r");
if (file == NULL){
printf("Error opening file %s\n", filename);
exit(1);
}
int i = 0;
while (fscanf(file, "%d %d", &coordinates[i*2], &coordinates[i*2+1]) != EOF){
i++;
}
}

int main(){
auto start = std::chrono::high_resolution_clock::now();

//-------------------------------------------------
// Load the coordinates of the cities from file
//-------------------------------------------------
int *path_coordinates = (int*)malloc(pathSize * 2 * sizeof(int));   //[pathSize][2];
load_data(path_coordinates, "48_cities.txt");

//-----------------------------------------
// Allocate and fill the distance matrix
//-----------------------------------------
double *distance_matrix = (double*)malloc(pathSize*pathSize*sizeof(double));    //[pathSize][pathSize];
for(int i = 0; i < pathSize; i++){
for(int j = 0; j < pathSize; j++){
distance_matrix[i*pathSize+j] = sqrt(pow(path_coordinates[i*2]-path_coordinates[j*2],2) + pow(path_coordinates[i*2+1]-path_coordinates[j*2+1],2));
}
}

int *population = (int*)malloc(popSize * pathSize * sizeof(int));   //[popSize][pathSize]; - This represents the order of the cities for each chromosome in the population
for (int i = 0; i < pathSize * popSize; i++){
population[i] = i % pathSize;

}

auto load_checkpoint = std::chrono::high_resolution_clock::now();
printf("Data loaded in %.2ld ms\n", std::chrono::duration_cast(load_checkpoint - start).count());

//---------------------------------------------------------------
// Random shuffle the population for the first time
//---------------------------------------------------------------
srand(time(NULL));  // seed the random number generator

// measure time to shuffle the population
auto shuffle_start = std::chrono::high_resolution_clock::now();

std::thread t[threads];
int sub_pop_num = std::ceil((popSize/subPopSize)/threads);  // number of subpopulations/islands per thread

//-----------------------------------------------------------------------
// Allocate fitness and distances for each individual and calculate them
//-----------------------------------------------------------------------
double *population_fitness = (double*)malloc(popSize*sizeof(double));   //[popSize];
double *population_distances = (double*)malloc(popSize*sizeof(double)); //[popSize];

for (int i = 0;  i < threads; i++){
int *pop_start = population + i * sub_pop_num * subPopSize * pathSize;
double *pop_fit_start = population_fitness + i * subPopSize;
t[i] = std::thread([pop_start, pop_fit_start, distance_matrix, population_distances, sub_pop_num](){
random_shuffle(pop_start, sub_pop_num);
calculate_scores(pop_start, distance_matrix, pop_fit_start, population_distances, sub_pop_num);
});
}
// join the threads
for (int i = 0; i < threads; i++){
t[i].join();
}
printf("Scores calculated\n");

auto shuffle_end = std::chrono::high_resolution_clock::now();
printf("Population shuffled in %.2ld ms\n", std::chrono::duration_cast(shuffle_end - shuffle_start).count());

// do the same in a single thread
shuffle_start = std::chrono::high_resolution_clock::now();
random_shuffle(population, popSize/subPopSize);
calculate_scores(population, distance_matrix, population_fitness, population_distances, popSize/subPopSize);
shuffle_end = std::chrono::high_resolution_clock::now();
printf("Population shuffled in %.2ld ms\n", std::chrono::duration_cast(shuffle_end - shuffle_start).count());

}

И файл 48_cities.txt

Код: Выделить всё

6734 1453
2233   10
5530 1424
401  841
3082 1644
7608 4458
7573 3716
7265 1268
6898 1885
1112 2049
5468 2606
5989 2873
4706 2674
4612 2035
6347 2683
6107  669
7611 5184
7462 3590
7732 4723
5900 3561
4483 3369
6101 1110
5199 2182
1633 2809
4307 2322
675 1006
7555 4819
7541 3981
3177  756
7352 4506
7545 2801
3245 3305
6426 3173
4608 1198
23 2216
7248 3779
7762 4595
7392 2244
3484 2829
6271 2135
4985  140
1916 1569
7280 4899
7509 3239
10 2676
6807 2993
5185 3258
3023 1942

Я ожидал, что с увеличением количества потоков время уменьшится, вплоть до максимально доступного в системе, но происходит обратное, в следующей части поста подробно объясняется, что я пробовал .

1)
Моя первая итерация создала фиксированное количество потоков std::threads и предложила им задачи в виде лямбда-функций на каждой итерации генетического алгоритма.
(Обратите внимание, что, учитывая структуру кода и модель генетического алгоритма, точки синхронизации распределяются на каждой итерации, что позволяет осуществлять последовательные мутации и периодически миграции особей)
Здесь часть цикла while, который управляет эволюцией

Код: Выделить всё

int generation = 1;
printf("Starting the GA...\n");
while (generation 

Подробнее здесь: [url]https://stackoverflow.com/questions/78349570/multithread-execution-times-are-slow-on-ubuntu-and-fast-on-windows[/url]