Perché questo metodo di ricerca non è scalabile?

Question

Desidero parallelamente il mio algoritmo di ricerca utilizzando openMP, vTree è un albero di ricerca binario e voglio applicare il mio algoritmo di ricerca per ciascun set di punti. di seguito è riportato uno snippet del mio codice. la procedura di ricerca per due punti è totalmente irrilevante e quindi può essere parallela. anche se hanno bisogno di leggere uno stesso albero, ma una volta costruito, l'albero non verrà più modificato. quindi è di sola lettura.

Tuttavia, il codice riportato di seguito mostra una scalabilità terribile, sulla mia piattaforma a 32 core, viene raggiunta solo una velocità doppia. è perché quello vTree viene letto da tutti i thread? se sì, come posso ottimizzare ulteriormente il codice?

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(); 

la firma tipo per search è

void VPTree::search(const Point& p, double radius, vector<Point>& result) const 

risultato di ricerca per essere messa in result.

Answer 1

La mia ipotesi migliore sarebbe quella di eseguire il ping-ping della cache sui vettori di risultato. Suppongo che la funzione "cerca" utilizzi il vettore dei risultati passati come un luogo in cui inserire i punti e che lo si usi in tutto l'algoritmo per inserire i vicini quando li si incontra nell'albero di ricerca. Ogni volta che aggiungi un punto a quel vettore risultato, i dati interni di tale oggetto vettoriale verranno modificati. E poiché tutti i vettori dei risultati sono raggruppati in una memoria contigua, è probabile che i diversi vettori di risultato occupino le stesse linee della cache. Quindi, quando la CPU mantiene la coerenza della cache, bloccherà costantemente le linee della cache pertinenti.

Il modo per risolverlo è utilizzare un vettore interno temporaneo che si assegna al vettore dei risultati solo una volta alla fine (operazione che può essere eseguita a basso costo se si utilizza la semantica del movimento). Qualcosa di simile a questo:

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; 
} 

Oppure, si potrebbe anche solo restituire il vettore per valore (che è implicitamente utilizza una mossa):

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

Benvenuti nel mondo gioioso di spostare-semantica e come impressionante può essere alla risoluzione di questi tipi di problemi di concorrenza/cache-coerenza.

È anche possibile che si verifichino problemi relativi all'accesso allo stesso albero da tutti i thread, ma dal momento che sono tutte operazioni di sola lettura, sono abbastanza sicuro che anche su un'architettura conservativa come x86 (e altri Intel/CPU AMD) che questo non dovrebbe rappresentare un problema significativo, ma potrei sbagliarmi (forse una sorta di problema di "sovraabbonamento" potrebbe essere in gioco, ma è dubbio). E altri problemi potrebbero includere il fatto che OpenMP comporta un po 'di overhead (generazione di thread, sincronizzazione, ecc.) Che deve essere ponderato rispetto al costo computazionale delle operazioni effettive che stai facendo all'interno di questi loop paralleli (e non è sempre un trade-off favorevole). Inoltre, se il tuo VPTree (immagino acronimo di "Vantage-point Tree") non ha una buona localizzazione di riferimenti (ad esempio, l'hai implementato come un albero collegato), allora le prestazioni saranno terribili in qualsiasi modo tu usi (come ho spiegato here).