Chcę równolegle mój algorytm wyszukiwania przy użyciu openMP, vTree
jest drzewem binarnym wyszukiwania i chcę zastosować mój algorytm wyszukiwania dla każdego zestawu punktów. poniżej znajduje się fragment mojego kodu. procedura wyszukiwania dla dwóch punktów jest całkowicie nieistotna i może być równoległa. chociaż muszą czytać to samo drzewo, ale po skonstruowaniu drzewo nie będzie już modyfikowane. dlatego jest on tylko do odczytu.Dlaczego ta metoda wyszukiwania nie może być skalowalna?
Jednak poniższy kod pokazuje straszną skalowalność, na mojej 32-rdzeniowej platformie osiągnięto tylko 2-krotne przyspieszenie. czy to dlatego, że ten vTree
jest czytany przez wszystkie wątki? jeśli tak, to w jaki sposób mogę zoptymalizować kod?
auto results = vector<vector<Point>>(particleNum);
auto t3 = high_resolution_clock::now();
double radius = 1.6;
#pragma omp parallel for
for (decltype(points.size()) i = 0; i < points.size(); i++)
{
vTree.search(points[i], radius, results[i]);
}
auto t4 = high_resolution_clock::now();
double searchTime = duration_cast<duration<double>>(t4 - t3).count();
podpis typu dla search
jest
void VPTree::search(const Point& p, double radius, vector<Point>& result) const
wynik wyszukiwania zostanie oddany do result
.
Nie mogę powiedzieć bez użycia profilera, ale gdybym zgadywał, twoje wątki są nawijane na pamięć podręczną. – Mgetz
@Mgetz, myślę, że na maszynie wielordzeniowej, każdy rdzeń ma własną pamięć podręczną, więc kod wielowątkowy powinien być w stanie używać większej pamięci podręcznej, czy tak? – Alaya
Platforma zależna. Można rozsądnie oczekiwać, że każdy rdzeń ma własny L1, ale współdzielony L3 (chyba, że masz włączoną hyperthreading) i zakładając, że są to rdzenie na tym samym pakiecie, i ... – Useless