Вы не включили минимальный рабочий пример в свой вопрос, поэтому я не смог воспроизвести вашу проблему.
Я согласен с другими людьми, которые, вероятно, видят то, что вы видитев том, что использование слишком большого количества ядер для выполнения сортировки приводит к крушению кеша , хотя я не смог доказать это на основе своих собственных тестов.
Когда процессор считывает данные из памятион не просто читает один байт.Он читает много байтов.Они хранятся в кеше для быстрого доступа.Кэши являются иерархическими и в большей или меньшей степени распределяются между процессорами, например:
Как видите, все ядра совместно используют кэш L3.Если адреса памяти, на которых работают ядра, удалены друг от друга, ядра будут иметь ограниченное перекрытие кэша и будут конкурировать за использование кэша.
Проверить, происходит ли это в вашем коде, легко (по крайней мере,, если у вас есть Linux).Вы можете использовать команду perf для сбора данных о том, что делает ваша программа.
В нижней части этого вопроса я включаю MWE того, что я думаю, что выСпрашиваешь.Затем я собираю статистику о поведении MWE, используя следующую команду perf.
perf stat -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads,L1-dcache-stores,l2_rqsts.miss,LLC-load-misses,LLC-loads,LLC-prefetch-misses,LLC-store-misses,LLC-stores ./a.out m
Это приводит к следующему для однопоточной операции:
18,676,838 cache-misses # 69.492 % of all cache refs (27.28%)
26,876,349 cache-references (36.38%)
143,224,257 L1-dcache-load-misses # 1.65% of all L1-dcache hits (36.39%)
8,682,532,168 L1-dcache-loads (36.40%)
4,130,005,905 L1-dcache-stores (36.40%)
92,709,572 l2_rqsts.miss (36.40%)
2,409,977 LLC-load-misses # 34.83% of all LL-cache hits (36.39%)
6,919,668 LLC-loads (36.37%)
23,562,449 LLC-prefetch-misses (18.16%)
16,038,395 LLC-store-misses (18.19%)
79,580,399 LLC-stores (18.18%)
24.578381342 seconds time elapsed
И для выполненияс четырьмя потоками:
21,357,447 cache-misses # 74.720 % of all cache refs (23.99%)
28,583,269 cache-references (33.10%)
160,265,596 L1-dcache-load-misses # 1.85% of all L1-dcache hits (35.91%)
8,670,516,235 L1-dcache-loads (36.52%)
4,131,943,678 L1-dcache-stores (36.50%)
102,495,289 l2_rqsts.miss (36.50%)
2,768,956 LLC-load-misses # 38.05% of all LL-cache hits (32.91%)
7,277,568 LLC-loads (31.23%)
29,220,858 LLC-prefetch-misses (15.36%)
18,920,533 LLC-store-misses (15.26%)
104,834,221 LLC-stores (14.85%)
10.334248457 seconds time elapsed
Как видите, работа с четырьмя потоками привела к большему количеству промахов в кеше.Это не может быть статистически значимым увеличением;Я не запускался несколько раз, чтобы проверить.Однако, в отличие от вас, я вижу улучшение производительности благодаря большему количеству потоков.
Чтобы имитировать конкуренцию в кеше, я могу переподписать свой ЦП, используя больше потоков, чем ядер.Для этого я установил переменную окружения OMP_NUM_THREADS:
export OMP_NUM_THREADS=32
С 32 потоками, я вижу:
Статистика счетчика производительности для './a.out m':
24,222,105 cache-misses # 77.175 % of all cache refs (23.39%)
31,385,891 cache-references (32.47%)
161,353,805 L1-dcache-load-misses # 1.87% of all L1-dcache hits (35.27%)
8,618,074,931 L1-dcache-loads (36.70%)
4,131,633,620 L1-dcache-stores (36.28%)
107,094,632 l2_rqsts.miss (36.21%)
5,299,670 LLC-load-misses # 56.36% of all LL-cache hits (31.93%)
9,403,090 LLC-loads (29.02%)
46,500,188 LLC-prefetch-misses (15.09%)
20,131,861 LLC-store-misses (14.26%)
105,310,438 LLC-stores (14.15%)
10.379022550 seconds time elapsed
Обратите внимание, что количество пропущенных загрузок LLC (кэш последнего уровня) увеличилось с 34% до 38% до 56% с увеличением количества потоков.Скорость, однако, не сильно пострадала.Это может быть из-за того, что у данных нет хорошего расположения кеша.
В любом случае, это один из способов изучения вашей проблемы.Если вам нужна лучшая помощь, чем эта, вам придется создать собственный MWE.
Вы можете уменьшить некоторые конфликты в кеше, уменьшив количество используемых вами потоков и указав их сходство, чтобы потокине используйте одни и те же кэши L2 / L3 (в зависимости от вашего процессора).Более подробная информация здесь .
Минимальный рабочий пример
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
typedef std::vector< std::vector<int> > data_t;
data_t GenData(std::mt19937 &mt_rand, int vec_num, int vec_len){
data_t data;
data.reserve(vec_num);
for(unsigned int i=0;i<vec_num;i++){
data.emplace_back();
data.back().reserve(vec_len);
for(unsigned int i=0;i<vec_len;i++)
data.back().emplace_back(mt_rand());
}
return data;
}
void SortSingle(data_t &data){
for(auto &v: data)
std::sort(v.begin(),v.end());
}
void SortMulti(data_t &data){
#pragma omp parallel for default(none) shared(data)
for(unsigned int i=0;i<data.size();i++)
std::sort(data[i].begin(), data[i].end());
}
int main(int argc, char **argv){
std::mt19937 mt_rand;
typedef std::chrono::high_resolution_clock clock;
std::cout<<"Generating data..."<<std::endl;
auto data = GenData(mt_rand,1600,156250);
std::cout<<"Sorting data..."<<std::endl;
const auto start_time = clock::now();
if(argv[1][0]=='s')
SortSingle(data);
else if (argv[1][0]=='m')
SortMulti(data);
else
std::cout<<"Unknown sort type!"<<std::endl;
const auto end_time = clock::now();
const auto time_diff = std::chrono::duration_cast<std::chrono::duration<double>>(end_time - start_time).count();
std::cout<<"Time = "<<time_diff<<"s"<<std::endl;
return 0;
}