Parallelize per ciclo annidato rispetto alla simmetria di tutto confronto con tutti -in contrario a C++/OpenMP

Question

Ho il semplice problema di confrontare tutti gli elementi l'uno con l'altro. Il confronto stesso è simmetrico, quindi, non deve essere fatto due volte.

Il seguente esempio di codice illustra quello che sto cercando, mostrando gli indici degli elementi a cui si accede:

int n = 5; 
for (int i = 0; i < n; i++) 
{ 
    for (int j = i + 1; j < n; j++) 
    { 
     printf("%d %d\n", i,j); 
    } 
} 

l'output è:

0 1 
0 2 
0 3 
0 4 
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 

Così ogni elemento viene confrontato con l'altro una volta . Quando voglio parallelizzare questo codice ho il problema che prima devo attenermi alla programmazione dinamica perché il tempo di calcolo di ogni iterazione varia enormemente E NON posso usare collasso perché le iterazioni nidificate sono index- dipende dal ciclo esterno.

L'utilizzo di #pragma omp parallel for schedule(dynamic, 3) per l'anello esterno può portare all'estremità single core all'estremità, mentre l'utilizzo di questo per l'anello interno può portare a tali esecuzioni all'interno di ciascuna iterazione del ciclo esterno.

C'è un modo più sofisticato di fare/parallelizzare quello?

Answer 1

Non l'ho pensato a fondo, ma tu può provare qualche approccio simile anche questo:

int total = n * (n-1)/2; // total number of combinations 
#pragma omp parallel for 
for (int k = 0; k < total; ++k) { 
    int i = first(k, n); 
    int j = second(k, n, i); 
    printf("%d %d\n", i,j); 
} 

int first(int k, int n) { 
    int i = 0; 
    for (; k >= n - 1; ++i) { 
    k -= n - 1; 
    n -= 1; 
    } 
    return i; 
} 

int second(int k, int n, int i) { 
    int t = i * (2*n - i - 1)/2; 
    return (t == 0 ? k + i + 1 : (k % t) + i + 1); 
} 

Answer 2

Infatti, lo standard OpenMP dice il collasso che:

Numero iterazione per ogni ciclo associato viene calcolato prima dell'entrata al ciclo più esterno. Se l'esecuzione di un loop associato modifica uno qualsiasi dei valori utilizzati per calcolare uno dei conteggi di iterazione, quindi il comportamento non è specificato.

Quindi non è possibile comprimere i loop, che sarebbe stato il modo più semplice. Tuttavia, dal momento che non si è particolarmente interessato nell'ordine in cui le coppie di indici sono calcolati, è possibile modificare un po 'i loop come segue:

for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n/2; j++) { 
     int ii, jj; 
     if (j < i) { 
      ii = n - 1 - i; 
      jj = n - 1 - j; 
     } 
     else { 
      ii = i; 
      jj = j + 1; 
     } 
     printf("%d %d\n", ii, jj); 
    } 
} 

Questo dovrebbe dare tutte le coppie che si desidera, in maniera un po ordine storpiato, ma con limiti di iterazione fissi che consentono una parallelizzazione bilanciata e persino il collasso del loop, se lo si desidera. Semplicemente, se n è pari, la colonna corrispondente a n/2 verrà visualizzata due volte così o vivrai con essa o modificherai leggermente l'algoritmo per evitare che ...

Answer 3

ho già avuto buoni risultati con il seguente:

#pragma omp parallel for collapse(2) 
for (int i = 0; i < n; ++i) { 
     for (int j = 0; j < n; ++j) { 
       if (j <= i) 
         continue; 
       printf("%d %d\n", i, j); 
     } 
} 

ricordo che printf non fa alcun carico di lavoro in parallelo solo, quindi sarebbe meglio se l'hai profilato sul tuo lavoro specifico. Potresti provare ad aggiungere schedule(dynamic, 10) o qualcosa di maggiore di 10 a seconda del numero di iterazioni che stai eseguendo.