2015-04-24 16 views
5

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.

+0

Nie mogę powiedzieć bez użycia profilera, ale gdybym zgadywał, twoje wątki są nawijane na pamięć podręczną. – Mgetz

+0

@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

+0

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

Odpowiedz

3

Moim najlepszym przypuszczeniem byłoby, że jesteś cache ping-pingu na wektorach wyników. Zakładam, że twoja funkcja "wyszukiwania" wykorzystuje wektor wyników przekazywanych jako miejsce do umieszczania punktów i że używasz go w całym algorytmie do wstawiania sąsiadów, gdy napotykasz je w drzewie wyszukiwania. Za każdym razem, gdy dodasz punkt do tego wektora wyników, wewnętrzne dane tego obiektu wektorowego zostaną zmodyfikowane. A ponieważ wszystkie wektory wyników są spakowane razem w ciągłej pamięci, prawdopodobne jest, że różne wektory wyników zajmują te same linie pamięci podręcznej. Tak więc, gdy procesor zachowuje spójność pamięci podręcznej, stale blokuje odpowiednie linie pamięci podręcznej.

Sposób na rozwiązanie tego problemu polega na użyciu wewnętrznego wektora tymczasowego, który można przypisać do wektora wyników tylko raz na końcu (co można zrobić tanio, jeśli używa się semantyki ruchu). Coś takiego:

void VPTree::search(const Point& p, double radius, vector<Point>& result) const { 
    vector<Point> tmp_result; 
    // ... add results to "tmp_result" 
    result = std::move(tmp_result); 
    return; 
} 

Albo można też po prostu zwrócić wektor o wartość (która jest niejawnie przy użyciu ruchu):

vector<Point> VPTree::search(const Point& p, double radius) const { 
    vector<Point> result; 
    // ... add results to "result" 
    return result; 
} 

Witamy w radosnym światem move-semantyki i jak niesamowite może to być rozwiązanie tych problemów związanych z współbieżnością/pamięcią podręczną.

Możliwe jest również, że występują problemy związane z dostępem do tego samego drzewa ze wszystkich wątków, ale ponieważ są to operacje tylko do odczytu, jestem prawie pewien, że nawet w konserwatywnej architekturze, takiej jak x86 (i innych procesorach Intel)/Procesory AMD), że nie powinno to stanowić znaczącego problemu, ale mogę się mylić (być może jest to problem "nadmiernej subskrypcji", ale jest wątpliwy). Inne problemy mogą obejmować fakt, że OpenMP niesie ze sobą spore obciążenie (wątki spawnowania, synchronizowanie itp.), Które musi być obciążone kosztami obliczeniowymi rzeczywistych operacji wykonywanych w tych równoległych pętlach (i nie zawsze jest to korzystny kompromis). A także, jeśli twój VPTree (wyobrażam sobie, że oznacza "drzewo punktów obserwacyjnych") nie ma dobrej lokalizacji referencji (np. Zaimplementowałeś to jako drzewo połączone), wtedy wydajność będzie straszna, niezależnie od tego, w jaki sposób używasz to (jak wyjaśniam here).

+0

jedyną operacją do 'wyniku' jest jak' Point * _p = getP(), result.push_back (* _ p) ' – Alaya

+0

I refactored my code i użyłem 'std :: vector' do przechowywania węzłów, dostaję trochę przyspieszenia, ale nie jest to naprawdę znaczące. – Alaya

+0

Cześć, wygląda na to, że zaimplementowałeś "drzewo punktów obserwacyjnych", po pewnym optymalizowaniu (poprzez spłaszczenie drzewa w szeroką pierwszą tablicę traversal), procedura wyszukiwania mogłaby osiągnąć liniowe przyspieszenie, jednak w mojej aplikacji muszę zająć się z ruchomymi punktami, więc w każdej rundzie muszę ponownie skonstruować drzewo, czy macie jakieś sugestie dotyczące równoległego konstruowania drzewa VP? – Alaya

Powiązane problemy