我目前在使用 openMP 并行化 c++ 中的程序时遇到问题。我正在实施一个具有基于用户的协作过滤方法的推荐系统。为此，我实现了一个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 秒。在 2 个线程上使用 openMP，大约需要 2 秒（这还不错，因为我在外循环中仍然有一些工作不平衡）。使用 4 个线程时，需要 7 秒。我不明白这种放缓的原因是什么。你有什么想法吗？
我已经考虑过这个问题，我与您分享我的考虑：
- 我仅在阅读模式下访问sparse_matrices。由于矩阵是预排序的，所有二进制搜索都不应修改矩阵和没有种族条件应该派生。
- 各种线程可以同时访问稀疏矩阵的同一向量。我读过一些关于虚假共享的内容，但由于我不在这些向量中写作，我认为这不应该是速度变慢的原因。
- 并行版本似乎在两个线程下工作正常（即使加速比低于预期）。 对于
- 其他参数选择，4 个线程没有问题。特别是（参见下面的"关于predict_rating函数的更多详细信息"），当我考虑加权平均值的所有相似项目并扫描评级向量并在相似性向量中搜索（与我通常所做的相反）时，执行时间在 4 个线程上缩放良好。
有关predict_rating函数的更多详细信息：此函数的工作方式如下。item_rating_vector 和 item_similarity_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;
}
}
有关硬件的更多详细信息：我在带有四核i7处理器和16Gb RAM的戴尔XPS15上运行此程序。我在 linux 虚拟盒子上执行代码（我将 VM 设置为使用 4 个处理器和 4Gb RAM）。
提前感谢，
皮尔保罗
您的目标变量似乎可能存在错误的共享问题。错误共享是指不同的线程频繁写入彼此靠近的位置（同一缓存行）。通过将计划显式设置为块大小为 1 的动态，您告诉 OpenMP 一次只执行一个元素的任务，从而允许不同的线程处理目标中可能彼此接近的数据。
我建议删除调度指令，只是为了看看默认调度程序和块大小是如何做的。然后我会尝试静态和动态计划，同时大幅改变块大小。如果您的工作负载或硬件平台不平衡，动态可能会获胜，但我仍然会尝试静态。
好吧，我自己找到了问题的解决方案：我为社区发布了解释。在predict_rating函数中，我使用 try/catch 来处理搜索字典中未包含的键时字典结构引发out_of_range错误。我继续阅读异常C++真的很慢吗，在抛出异常的情况下，异常处理在计算上很重。就我而言，对于每次调用predict_rating，我都会抛出并处理多个out_of_range错误。我只是删除了try/catch块并编写了一个函数，该函数在字典中搜索，如果该键不存在，则返回默认值。此修改产生了大约 2000 倍的加速，现在该程序即使在 VM 上的线程数方面也能很好地扩展。
感谢大家，如果您有其他建议，请不要犹豫！
皮尔保罗