openMP замедляется при передаче от 2 до 4 потоков, выполняющих бинарный поиск в пользовательском контейнере

В настоящее время у меня проблема с распараллеливанием программы на c ++ с использованием openMP. Я внедряю систему рекомендаций с пользовательским методом совместной фильтрации. Для этого я реализовал класс sparse_matrix в качестве словаря словарей (где я имею в виду своего рода словарь Python). В моем случае, поскольку вставка выполняется только в начале алгоритма, когда данные считываются из файла, я реализовал словарь как вектор библиотеки std пары объектов (ключ, значение) с флагом, указывающим, отсортирован ли вектор. если вектор отсортирован, ключ ищется с помощью бинарного поиска. в противном случае вектор сначала сортируется, а затем ищется. Альтернативно, можно сканировать записи словаря линейно, например, в циклах по всем ключам словаря. Соответствующая часть кода, которая вызывает проблемы, заключается в следующем

void compute_predicted_ratings_omp (sparse_matrix &targets,
sparse_matrix &user_item_rating_matrix,
sparse_matrix &similarity_matrix,
int k_neighbors)
{
// Auxiliary private variables
int user, item;
double predicted_rating;
dictionary<int,double> target_vector, item_rating_vector, item_similarity_vector;

#pragma omp parallel shared(targets, user_item_rating_matrix, similarity_matrix)\
private(user, item, predicted_rating, target_vector, item_rating_vector, item_similarity_vector)
{
if (omp_get_thread_num() == 0)
std::cout << " - parallelized on " << omp_get_num_threads() << " threads: " << std::endl;

#pragma omp for schedule(dynamic, 1)
for (size_t iter_row = 0; iter_row < targets.nb_of_rows(); ++iter_row)
{
// Retrieve target user
user = targets.row(iter_row).get_key();

// Retrieve the user rating vector.
item_rating_vector = user_item_rating_matrix[user];

for (size_t iter_col = 0; iter_col < targets.row(iter_row).value().size(); ++iter_col)
{
// Retrieve target item
item = targets.row(iter_row).value().entry(iter_col).get_key();

// retrieve similarity vector associated to the target item
item_similarity_vector = similarity_matrix[item];

// Compute predicted rating
predicted_rating = predict_rating(item_rating_vector,
item_similarity_vector,
k_neighbors);

// Set result in targets
targets.row(iter_row).value().entry(iter_col).set_value(predicted_rating);
}
}
}
}

В этой функции я вычисляю прогнозируемый рейтинг для ряда целевых пар (пользователь, элемент) (это просто средневзвешенное значение). Для этого я выполняю внешний цикл для целевых пользователей (которые находятся в строках разреженной матрицы целей) и извлекаю вектор рейтинга для текущего пользователя, выполняя двоичный поиск по строкам user_item_rating_matrix. Затем для каждого столбца в текущей строке (т. Е. Для каждого элемента) я извлекаю другой вектор, связанный с текущим элементом, из разреженной матрицы Similarity_matrix. С этими двумя векторами я вычисляю прогноз как средневзвешенное значение их элементов (для подмножества элементов, общих для двух векторов).

Моя проблема заключается в следующем: я хочу распараллелить внешний цикл с использованием openMP. В серийной версии эта функция занимает около 3 секунд. С openMP в 2 потоках это занимает около 2 секунд (что неплохо, так как у меня все еще есть некоторые рабочие дисбалансы во externalloop). При использовании 4 потоков это занимает 7 секунд. Я не могу понять, что является причиной этого замедления. Есть ли у вас какие-либо идеи?

Я уже думал о проблеме и делюсь своими соображениями с вами:

• Я получаю доступ к sparse_matrices только в режиме чтения. Так как матрицы
  предварительно отсортированы, все двоичные поиски не должны изменять
  Матрицы и никакие условия гонки не должны быть выведены.
• Различные потоки могут одновременно обращаться к одному и тому же вектору разреженной матрицы. Я читал кое-что о ложном обмене, но так как я не пишу в этих векторах, я думаю, что это не должно быть причиной замедления.
• Параллельная версия, кажется, прекрасно работает с двумя потоками (даже если скорость ниже ожидаемой).
• Никаких проблем не наблюдается с 4 потоками для других вариантов выбора параметров. В частности (см. «Дополнительные сведения о функции предиката» ниже), когда я рассматриваю все подобные элементы для взвешенного среднего и сканирую вектор рейтинга и выполняю поиск по вектору сходства (противоположность того, что я обычно делаю), выполнение время хорошо масштабируется на 4 темы.

Более подробная информация о функции предиката: Эта функция работает следующим образом. Наименьшее между item_rating_vector и item_simility_vector сканируется линейно, и я выполняю двоичный поиск по самому длинному из двух. Если рейтинг / сходство является положительным, оно считается средневзвешенным.

double predict_rating (dictionary<int, double> &item_rating_vector,
dictionary<int, double> &item_similarity_vector)

{
size_t size_item_rating_vector = item_rating_vector.size();
size_t size_item_similarity_vector = item_similarity_vector.size();

if (size_item_rating_vector == 0 || size_item_similarity_vector == 0)
return 0.0;
else
{
double s, r, sum_s = 0.0, sum_sr = 0.0;
int temp_item = 0;

if (size_item_rating_vector < size_item_similarity_vector)
{
// Scan item_rating_vector and search in item_similarity_vector
for (dictionary<int,double>::const_iterator iter = item_rating_vector.begin();
iter != item_rating_vector.end();
++iter)
{
// scan the rating vector forwards: iterate until the whole vector has
// been scanned.
temp_item = (*iter).get_key();

// Retrieve rating that user gave to temp_item (0.0 if not given)
try { s = item_similarity_vector[temp_item]; }
catch (const std::out_of_range &e) { s = 0.0; }

if (s > 0.0)
{
// temp_item is positively similar to the target item. consider it in the average

// Retrieve rating that the user gave to temp_item
r = (*iter).get_value();

// increment the sums
sum_s += s;
sum_sr += s * r;
}
}
}
else
{
// Scan item_similarity_vector and search in item_rating_vector
for (dictionary<int,double>::const_iterator iter = item_similarity_vector.begin();
iter != item_similarity_vector.end();
++iter)
{
// scan the rating vector forwards: iterate until the whole vector has
// been scanned.
temp_item = (*iter).get_key();

s = (*iter).get_value();

if (!(s > 0.0))
continue;

// Retrieve rating that user gave to temp_item (0.0 if not given)
try { r = item_rating_vector[temp_item]; }
catch (const std::out_of_range &e) { r = 0.0; }

if (r > 0.0)
{
// temp_item is positively similar to the target item: increment the sums
sum_s += s;
sum_sr += s * r;
}
}
}

if (sum_s > 0.0)
return sum_sr / sum_s;
else
return 0.0;
}

}

Более подробная информация об оборудовании: Я запускаю эту программу на Dell XPS15 с четырехъядерным процессором i7 и 16 ГБ ОЗУ. Я выполняю код на виртуальной коробке Linux (я устанавливаю виртуальную машину на использование 4 процессоров и 4 ГБ ОЗУ).

Заранее спасибо,

Pierpaolo