当从 2 个线程传递到 4 个线程时，openMP 在自定义容器中进行二进制搜索时速度变慢
openMP slows down when passing from 2 to 4 threads doing binary searches in a custom container
我目前在使用 openMP 并行化 c++ 程序时遇到问题。我正在使用基于用户的协同过滤方法实现推荐系统。为此，我实现了一个 sparse_matrix class 作为字典的字典（这里我指的是一种 python 字典）。在我的例子中，由于插入仅在算法开始时从文件中读取数据时完成，因此我将字典实现为成对对象（键、值）的标准库向量，并带有一个标志，指示向量是否已排序。如果向量已排序，则使用二进制搜索来搜索键。否则首先对向量进行排序然后搜索。或者，可以线性扫描字典的条目，例如在字典的所有键上循环。导致问题的代码的相关部分如下
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线程没问题。特别是（参见下面的 "Further details on predict_rating function"），当我考虑加权平均的所有相似项目并扫描评分向量并在相似性向量中搜索时（与我通常所做的相反），执行时间尺度在 4 个线程上很好。
有关 predict_rating 函数的更多详细信息：此函数的工作方式如下。 item_rating_vector 和 item_similarity_vector 之间的最小值被线性扫描，我对两者中最长的进行二分查找。如果 rating/similarity 为正，则在加权平均中考虑。
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 virtualbox 上执行代码（我将 VM 设置为使用 4 个处理器和 4Gb RAM）。
提前致谢，
皮尔保罗
看来您的目标变量可能存在错误的共享问题。错误共享是指不同的线程频繁写入彼此靠近的位置（相同的缓存行）。通过将调度显式设置为块大小为 1 的动态，您告诉 OpenMP 一次只让每个线程处理一个元素的任务，从而允许不同的线程处理目标中可能彼此靠近的数据。
我建议删除 schedule 指令只是为了看看默认调度程序和块大小如何工作。然后我会尝试静态和动态计划，同时大幅改变块大小。如果您的工作负载或硬件平台不平衡，动态可能会获胜，但我仍然会尝试静态。
好吧，我自己找到了问题的解决方案：我 post 对社区的解释。在 predict_rating 函数中，我使用 try/catch 来处理当搜索字典中不包含的键时由我的字典结构抛出的 out_of_range 错误。我在 Are exceptions in C++ really slow 上读到，在抛出异常的情况下，异常处理的计算量很大。就我而言，对于 predict_rating 的每次调用，我都会抛出并处理多个 out_of_range 错误。我只是删除了 try/catch 块并编写了一个在字典中搜索的函数，如果该键不存在，则 return 一个默认值。此修改产生了大约 2000 倍的加速，现在该程序甚至在 VM 上的线程数量方面也能很好地扩展。
感谢大家，如果您有其他建议，请不要犹豫！
皮尔保罗
我目前在使用 openMP 并行化 c++ 程序时遇到问题。我正在使用基于用户的协同过滤方法实现推荐系统。为此，我实现了一个 sparse_matrix class 作为字典的字典（这里我指的是一种 python 字典）。在我的例子中，由于插入仅在算法开始时从文件中读取数据时完成，因此我将字典实现为成对对象（键、值）的标准库向量，并带有一个标志，指示向量是否已排序。如果向量已排序，则使用二进制搜索来搜索键。否则首先对向量进行排序然后搜索。或者，可以线性扫描字典的条目，例如在字典的所有键上循环。导致问题的代码的相关部分如下
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线程没问题。特别是（参见下面的 "Further details on predict_rating function"），当我考虑加权平均的所有相似项目并扫描评分向量并在相似性向量中搜索时（与我通常所做的相反），执行时间尺度在 4 个线程上很好。
有关 predict_rating 函数的更多详细信息：此函数的工作方式如下。 item_rating_vector 和 item_similarity_vector 之间的最小值被线性扫描，我对两者中最长的进行二分查找。如果 rating/similarity 为正，则在加权平均中考虑。
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 virtualbox 上执行代码（我将 VM 设置为使用 4 个处理器和 4Gb RAM）。
提前致谢，
皮尔保罗
看来您的目标变量可能存在错误的共享问题。错误共享是指不同的线程频繁写入彼此靠近的位置（相同的缓存行）。通过将调度显式设置为块大小为 1 的动态，您告诉 OpenMP 一次只让每个线程处理一个元素的任务，从而允许不同的线程处理目标中可能彼此靠近的数据。
我建议删除 schedule 指令只是为了看看默认调度程序和块大小如何工作。然后我会尝试静态和动态计划，同时大幅改变块大小。如果您的工作负载或硬件平台不平衡，动态可能会获胜，但我仍然会尝试静态。
好吧，我自己找到了问题的解决方案：我 post 对社区的解释。在 predict_rating 函数中，我使用 try/catch 来处理当搜索字典中不包含的键时由我的字典结构抛出的 out_of_range 错误。我在 Are exceptions in C++ really slow 上读到，在抛出异常的情况下，异常处理的计算量很大。就我而言，对于 predict_rating 的每次调用，我都会抛出并处理多个 out_of_range 错误。我只是删除了 try/catch 块并编写了一个在字典中搜索的函数，如果该键不存在，则 return 一个默认值。此修改产生了大约 2000 倍的加速，现在该程序甚至在 VM 上的线程数量方面也能很好地扩展。
感谢大家，如果您有其他建议，请不要犹豫！
皮尔保罗