Fetch-and-add utilizzando operazioni atomiche OpenMP

Question

Sto usando OpenMP e necessità di utilizzare l'operazione fetch-and-add. Tuttavia, OpenMP non fornisce un adeguato direttiva / call. Mi piacerebbe conservare la massima portabilità, quindi io non voglio fare affidamento su intrinseci compilatore.

Piuttosto, sto cercando un modo per sfruttare operazioni atomiche di OpenMP per attuare questo, ma ho colpito un vicolo cieco. Può questo anche essere fatto? N.B., il seguente codice quasi Fa quello che voglio:

#pragma omp atomic
x += a

Quasi - ma non del tutto, dal momento che ho davvero bisogno il vecchio valore di x. fetch_and_add dovrebbe essere definito per produrre lo stesso risultato come la seguente (solo non bloccabile):

template <typename T>
T fetch_and_add(volatile T& value, T increment) {
    T old;
    #pragma omp critical
    {
        old = value;
        value += increment;
    }
    return old;
}

(Una domanda equivalente potrebbe essere chiesto di confrontare-e-swap, ma uno può essere implementato in termini di l'altro, se non sbaglio.)

Answer 1

A partire dal OpenMP 3.1 c'è il supporto per la cattura aggiornamenti atomiche, è possibile catturare sia il valore vecchio o il nuovo valore. Dal momento che abbiamo per portare il valore in dalla memoria per incrementare in ogni modo, ha senso solo che dovremmo essere in grado di accedervi da dire, un registro della CPU e metterlo in una variabile thread-privato.

C'è un bel lavoro intorno se si sta utilizzando GCC (o g ++), cercare builtins atomiche: http://gcc.gnu.org/onlinedocs/gcc -4.1.2 / gcc / Atomic-Builtins.html

Si pensa Intel C / C ++ ha anche il supporto per questo, ma io non l'ho provato.

Per ora (fino a quando viene implementato OpenMP 3.1), ho usato le funzioni inline involucro in C ++, dove è possibile scegliere la versione da utilizzare in fase di compilazione:

template <class T>
inline T my_fetch_add(T *ptr, T val) {
  #ifdef GCC_EXTENSION
  return __sync_fetch_and_add(ptr, val);
  #endif
  #ifdef OPENMP_3_1
  T t;
  #pragma omp atomic capture
  { t = *ptr; *ptr += val; }
  return t;
  #endif
}

Aggiornamento: Ho appena provato il compilatore Intel C ++, che attualmente ha il supporto per OpenMP 3.1 (cattura atomica è implementato). Intel offre l'uso gratuito dei suoi compilatori in linux per scopi non commerciali:

http://software.intel.com/en -USA / articoli / non commerciale-software-download /

GCC 4.7 supporterà OpenMP 3.1, quando alla fine viene rilasciato ... speriamo presto:)

Answer 2

Se si desidera ottenere vecchio valore di x e una non è cambiato, (X-A) come vecchio valore:

fetch_and_add(int *x, int a) {
 #pragma omp atomic
 *x += a;

 return (*x-a);
}

UPDATE: non era proprio una risposta, perché x possono essere modificati dopo l'atomica da un altro thread. Quindi è sembra essere impossibile fare universale "Fetch-and-add" utilizzando OMP Pragma. Come ho universale funzionamento media, che può essere facilmente utilizzato da qualsiasi luogo del codice di OMP.

È possibile utilizzare le funzioni omp_*_lock per simulare un Atomics:

typedef struct {omp_lock_t serratura; int value;} atomic_simulated_t;

fetch_and_add(atomic_simulated_t *x, int a)
{
  int ret;
  omp_set_lock(x->lock);
  x->value +=a;
  ret = x->value;
  omp_unset_lock(x->lock);
}

Questo è brutto e lento (facendo un 2 ops atomiche invece di 1). Ma se si desidera che il codice sia molto portatile, sarà non il più veloce in tutti i casi.

Si dice "nel modo seguente (solo non bloccabile)". Ma qual è la differenza tra "non-bloccaggio" operazioni (usando il prefisso di CPU "LOCK", o LL / SC o, ecc) e le operazioni di blocco (che di per sé sono implementati con diverse istruzioni atomiche, ciclo occupato per breve attesa di sblocco e OS sonno per lunghe attese)?