我正在生成類物件并將它們放入 std::vector 中。在添加之前，我需要檢查它們是否與已經生成的物件相交。由于我計劃擁有數百萬個物件，因此我需要并行化此函式，因為它需要大量時間（該函式必須檢查每個新物件與所有先前生成的物件）。
不幸的是，速度提升并不顯著。分析器還顯示出非常低的效率（所有開銷）。任何建議將不勝感激。
bool
Generator::_check_cube (std::vector<Cube> &cubes, const cube &cube)
{
auto ptr_cube = &cube;
auto npol = cubes.size();
auto ptr_cubes = cubes.data();
const auto nthreads = omp_get_max_threads();
bool check = false;
#pragma omp parallel shared (ptr_cube, ptr_cubes, npol, check)
{
#pragma omp single nowait
{
const auto batch_size = npol / nthreads;
for (int32_t i = 0; i < nthreads; i )
{
const auto bstart = batch_size * i;
const auto bend = ((bstart batch_size) > npol) ? npol : bstart batch_size;
#pragma omp task firstprivate(i, bstart, bend) shared (check)
{
struct bd bd1{}, bd2{};
bd1 = allocate_bd();
bd2 = allocate_bd();
for (auto j = bstart; j < bend; j )
{
bool loc_check;
#pragma omp atomic read
loc_check = check;
if (loc_check) break;
if (ptr_cube->cube_intersecting(ptr_cubes[j], &bd1, &bd2))
{
#pragma omp atomic write
check = true;
break;
}
}
free_bd(&bd1);
free_bd(&bd2);
}
}
}
}
return check;
}
更新：立方體實際上是由更小的長方體組成的，每個長方體都有大小（L、W、H）、位置坐標和旋轉。相交函式：
bool
Cube::cube_intersecting(Cube &other, struct bd *bd1, struct bd *bd2) const
{
const auto nom = number_of_cuboids();
const auto onom = other.number_of_cuboids();
for (int32_t i = 0; i < nom; i )
{
get_mcoord(i, bd1);
for (int32_t j = 0; j < onom; j )
{
other.get_mcoord(j, bd2);
if (check_gjk_intersection(bd1, bd2))
{
return true;
}
}
}
return false;
}
//get_mcoord 計算長方體的頂點
void
Cube::get_mcoord(int32_t index, struct bd *bd) const
{
for (int32_t i = 0; i < 8; i )
{
for (int32_t j = 0; j < 3; j )
{
bd->coord[i][j] = _cuboids[index].get_coord(i)[j];
}
}
}
inline struct bd
allocate_bd()
{
struct bd bd{};
bd.numpoints = 8;
bd.coord = (double **) malloc(8 * sizeof(double *));
for (int32_t i = 0; i < 8; i )
{
bd.coord[i] = (double *) malloc(3 * sizeof(double));
}
return bd;
}
uj5u.com熱心網友回復：
您搜索的問題是 OpenMP 真的很喜歡靜態回圈，其中迭代次數是預先確定的。因此，也許一項任務會break提早，但所有其他任務都會經過他們的全面搜索。
對于 OpenMP 的最新版本（我認為是 5），有一個解決方案。
- （不確定這一點：使您的任務更加細粒度，例如每個交叉測驗一個）；
taskloop在;中生成你的任務- 一旦你找到你的交叉點（或任何導致你打破的條件），做
cancel taskloop。 - 小問題：默認禁用取消。將環境變數設定
OMP_CANCELLATION為 true。
uj5u.com熱心網友回復：
你有更多的交叉點是真的還是更多的是假的？如果大多數情況屬實，那么您的硬體就會充斥著寫入共享資源的請求，而您所做的事情本質上是順序的。解決此問題的一種方法是避免使用共享資源，因此沒有互斥鎖，您讓所有執行緒運行，最后您根據結果做出決定；這可能會運行得更快，但好處也取決于任意選擇，例如很少的指標（例如，nthreads、ncuboids）。
在另一種架構（例如，gpu）上，您的演算法可能運行良好。考慮到生產規模（數百萬個長方體，24 個維度），我可能值得在 gpu 上對其進行基準測驗，看看您是否會從這種遷移中受益。
您還有一個復雜性問題，即對于每個新長方體，您都將其與整個現有長方體集進行比較。解決這個問題的一種方法是按維度收集所有長方體大小（范圍）并對它們進行排序，然后添加新的長方體范圍。如果一個維度存在交叉點，則測驗下一個維度等。您也可以并行運行它們。在運行范圍之前，您測驗您是否在全域范圍內擊中，如果不是，則在本地測驗交叉點是沒有用的。
在這里和一般情況下，您希望以最小的依賴性（共享資源、互斥鎖）進行并行化。所以你想嘗試找到一個觀點，這會發生。在有序范圍（段）上并行化維度可能比在長方體上并行化更好。
并行性的演算法和好處還取決于物件的值。這并不意味著復雜性預測不相關，而是在給定這些值的情況下，人們可能會找到一種更聰明的方法。
uj5u.com熱心網友回復：
我認為您的代碼受記憶體限制，因此其瓶頸是記憶體讀/寫而不是計算。這可能是速度提升不佳的主要原因。正如@Soleil 已經提到的那樣，不同的硬體（GPU）在這里可能是有益的。
Generator::_check_cub您在多次呼叫的評論中提到。為了減少 OpenMP 開銷，我的建議是將并行區域移出這個函式，你甚至可以在你的main函式中使用它：
main(){
#pragma omp parallel
#pragma omp single nowait
{
//your code
}
}
在這種情況下，您必須使用#pragma omp taskwait等待任務完成。
for (int32_t i = 0; i < nthreads; i )
{
#pragma omp task default(none) firstprivate(...) shared (..)
{
//your code comes here
}
}
#pragma omp taskwait
我還建議default(none)在指令中使用子句，#pragma omp task因此您必須明確告知所有變數的共享屬性。
你真的需要功能get_mcoord嗎？對我來說，這似乎是一個冗余的記憶體副本。我認為撰寫一個將其或其索引作為引數的check_gjk_intersection函式可能會更好。_cuboids在這種情況下，您可以擺脫 and 的許多記憶體分配/釋放，bd1正如bd2@Victor 指出的那樣，這也可能很耗時。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/436457.html
上一篇：雙回圈的Pythonic方式