Processo parallelo sincrono in C#/C++

Question

Ho un array x [] contenente dati. Inoltre c'è una serie di "stati del sistema" c []. Il processo:

for(i = 1; i < N; i++) 
{ 
    a = f1(x[i] + c[i-1]); 
    b = f2(x[i] + c[i-1]); 
    c[i] = a + b; 
} 

Esiste un modo efficiente per trovare i valori di f1 e f2 nel sistema 2-nucleo usando 2 fili paralleli? Intendo i seguenti (in pseudo-codice):

thread_1 
{ 
    for(i = 1; i < N; i++) 
     a = f1(x[i] + c[i-1]);  
} 
thread_2 
{ 
    for(i = 1; i < N; i++) 
    { 
     b = f2(x[i] + c[i-1]); 
     c[i] = a + b; //here we somehow get a{i} from thread_1 
    } 
} 

f1 e f2 non sono tempo tisica, ma devono essere calcolati molte volte, quindi accelerazione desiderata è circa x2. Vedere lo schema per la rappresentazione grafica:

ricerca di esempi di codice per Windows.

Answer 1

Se ho capito bene,

• a[i] può essere calcolato solo quando c[i-1] è disponibile
• b[i] può essere calcolato solo quando c[i-1] è disponibile
• c[i] è disponibile solo quando a[i] e b[i] sono calcolati

Significa che l'unico processo che è possibile eseguire separatamente è il calcolo di a[i] e di b[i].

Ecco come la vedo io in C#:

for (int i = 1; i < N; i++) 
{ 
    Task<double> calcA = Task.Factory.StartNew(() => { return f1(x[i] + c[i-1]); }); 
    Task<double> calcB = Task.Factory.StartNew(() => { return f2(x[i] + c[i-1]); }); 

    // .Result will block the execution and wait for both calculations to complete 
    c[i] = calcA.Result + calcB.Result; 
} 

Questo farà eseguire due thread separati, che calcolerà f1 e f2 rispettivamente. Dopo aver calcolato sia f1 sia f2, verrà impostato il valore c[i] e verrà eseguita l'iterazione successiva.

Nota che:

• Io uso double, assumendo che il vostro f1 e f2 ritorno double
• Il ciclo parte da 1, a patto che abbiate alcune iniziali a[0] e b[0] valori. In caso contrario, c[i-1] getterebbe un'eccezione
• Questo sarà solo portare un miglioramento se il calcolo di f1 e f2 è davvero risorse di tempo e lungo, rispetto ad altri calcoli
• Task.Factory.StartNew (a differenza tramite Thread) utilizza ThreadPool che significa che doesn' t creare una nuova discussione ogni volta, ma riutilizza l'esistente dal pool. Riduce sensibilmente il sovraccarico.

Answer 2

Senza entrare in una soluzione di codice, si desidera utilizzare una sorta di barriera. Ciò consente di verificare se tutti i partecipanti hanno dichiarato di aver completato l'attività.Discussione 2 dovrà aspettare per la filettatura uno in questo esempio

https://en.wikipedia.org/wiki/Barrier_(computer_science) Example of C++ "Memory barrier"

Answer 3

L'unica parte in parallelo in questo algoritmo è il calcolo di f1 e f2, ma lei dice che F1 e F2 non sono tempo tisico, così potrebbe essere molto meglio usare la vettorizzazione SIMD (es. System.Numerics.Vectors in C#) ed eseguirlo su un core (che riduce anche i fallimenti della cache). O probabilmente potresti modificare il tuo algoritmo per essere parallelizzabile (ma potrebbe richiedere un duro lavoro).