Iteratori paralleli

Question

Sto progettando una struttura dati C++ (per grafici) che deve essere utilizzata dal codice parallelo (utilizzando OpenMP).

Supponiamo di voler avere un metodo che abiliti l'iterazione su tutti gli elementi (nodi). Naturalmente, questa iterazione sarà parallelizzata.

È possibile utilizzare un iteratore per questo scopo? Come dovrebbe apparire un iteratore che consenta l'accesso parallelo? Consiglieresti a favore o contro l'uso degli iteratori in questo caso?

Answer 1

I loop paralleli di OpenMP non funzionano bene con gli iteratori. Dovrai implementare un meccanismo di indicizzazione (operator[] prendendo un argomento integrale) sulla classe del tuo grafico.

Se si desidera utilizzare il supporto iteratore OpenMP 3.0, assicurarsi di disporre di un iteratore di accesso casuale. L'implementazione come puntatore a un nodo o a un bordo è la scelta più semplice.

Answer 2

Questa è una variazione del problema lettore/scrittore.

Dipende se tale struttura può essere modificata o meno. Se no, allora vai via, leggi in parallelo quanto vuoi.

Ma se sarà modificabile, gli iteratori probabilmente si scontreranno con le modifiche apportate alla struttura. Ad esempio, l'iteratore potrebbe arrivare su un elemento che viene attualmente eliminato. Una soluzione consiste nel creare una copia di sola lettura e immutabile della struttura per ciascun iteratore, ma in tal caso l'iteratore non registrerà alcuna modifica apportata alla struttura dopo la creazione dell'iteratore. La seconda soluzione consiste nel realizzare un'implementazione copy-on-write, che farà sì che tutte le scritture sulla struttura creino un nuovo oggetto, con gli iteratori attualmente in esecuzione che operano su quello vecchio.

È necessario decidere che cosa scrive in quella struttura per il programma, in base all'algoritmo, quindi implementare il blocco di lettura/scrittura in modo appropriato.

Answer 3

Lasciatemi espandere il mio commento. A meno che tu non abbia come target la compatibilità multipiattaforma e desideri che il tuo codice compili e lavori con MS Visual C++, puoi compensare la complessità della fornitura di iteratori "lineari" agli oggetti del grafico utilizzando attività OpenMP esplicite. L'incarico esplicito è stato introdotto in OpenMP 3.0 (quindi non è supportato da MSVC, che si conforma solo a una specifica molto precedente, anche nel 2012). Le attività sono blocchi di codice che possono essere eseguiti in parallelo. Essi sono creati dal task costrutto:

... other code ... 
#pragma omp task 
{ 
    ... task code ... 
} 
... other code ... 

Quando il flusso di esecuzione raggiunge la regione marcato, si crea un nuovo oggetto compito e messi in una coda compito. Quindi, in determinati momenti, i thread inattivi catturano un'attività dalla coda e iniziano ad eseguirla. Le attività sono molto simili alle sezioni OpenMP in quanto ereditano il loro ambiente e possono essere eseguite in un ordine diverso rispetto alla versione seriale del codice.

Con i task è possibile implementare algoritmi ricorsivi e anche lavorare con contenitori C++ che non forniscono iteratori casuali. Ad esempio attraversamento di un albero binario può essere eseguita come questo con compiti:

// Helper routine to traverse a tree and create one task for each node 
void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    // Create a task to process the node 
    #pragma omp task 
    { 
     very_long_computation(tn->value); 
    } 

    traverse_and_make_tasks(tn->left); 
    traverse_and_make_tasks(tn->right); 
} 

... main code ... 

// Disable dynamic teams 
omp_set_dynamic(0); 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     traverse_and_make_tasks(tree->root_node); 
    } 
} 

(disabilitando team dinamici è necessaria al fine di prevenire l'OpenMP runtime di essere troppo intelligente ed eseguendo la regione parallel singolo avvitamento)

Questo è uno schema di lavoro molto comune noto come produttore singolo/seriale.Ogni volta che l'esecuzione entra nella regione parallel, un singolo thread esegue il codice nel costrutto single. Chiama traverse_and_make_tasks con il nodo principale dei tre. traverse_and_make_tasks passa a tre e crea un'attività per ciascun nodo. Il costrutto task funziona solo se utilizzato all'interno di un'area parallel (ambito statico) o quando viene utilizzato nel codice chiamato (direttamente o indirettamente) all'interno di un'area parallel (ambito dinamico). Come traverse_and_make_tasks percorre l'albero, produce attività che vengono messe in coda. Alla fine della regione parallel è presente un punto di pianificazione dell'attività implicito, che indica approssimativamente che l'esecuzione non riprenderà oltre la fine dell'area fino a quando non sono state eseguite tutte le attività. Si possono anche inserire punti espliciti all'interno della regione parallela usando #pragma omp taskwait. Funziona in modo simile a barrier - "blocchi" di esecuzione fino a quando tutte le attività sono state elaborate.

Un altro schema comune è il produttore parallelo in cui le attività vengono generate in parallelo. Il codice di esempio precedente può essere facilmente trasformato in un produttore parallelo da una semplice modifica sulla traverse_and_make_tasks:

void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    #pragma omp task 
    traverse_and_make_tasks(tn->left); 
    #pragma omp task 
    traverse_and_make_tasks(tn->right); 

    // Create a task to process the node 
    very_long_computation(tn->value); 
} 

Questa versione del codice crea due compito ad ogni nodo - di processare il discendente sinistra e uno per elaborare destra discendente. Se questo fosse codice seriale, attraverserebbe l'albero dal basso verso l'alto. Tuttavia, nel caso parallelo, l'accodamento delle attività comporterebbe un maggiore o minore traversamento.

Ci sono molti altri possibili scenari di utilizzo delle attività. Si può anche utilizzare in un caso non ricorsivo per il trattamento di contenitori che non forniscono iteratori casuali, richieste dal worksharing costruire for:

typedef container_type::iterator citer; 

container_type container; 
... push some values in the container ... 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process(*it); 
    } 

    #pragma omp taskwait 

    // process more 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process_more(*it); 
    } 
} 

Questo esempio illustra anche l'uso di sincronizzazione compito esplicito all'interno della regione parallel.

Answer 4

Se sono alberi, probabilmente vorrai pensare di più in termini di scansioni su Euler Tour Traversals che "iteratori". http://en.wikipedia.org/wiki/Euler_tour_technique

Vorrei avere il libro di Stepanov di fronte a me. Ricordo che lo toccò brevemente.

Answer 5

Ho avuto esattamente lo stesso problema in Java. Una soluzione che ho implementato utilizza una "hashmap di hashmap". Io ancora non capisco perché le librerie standard non ci permettono di fare iteratori multi-filettati ... Potete leggere la mia domanda, insieme con la mia risposta (con link al codice Java) qui:

Scalable way to access every element of ConcurrentHashMap<Element, Boolean> exactly once