[C/C++] Consigli ottimizzazione velocità

[Rossi88]

Come da oggetto vorrei dei consigli per ottimizzare la velocità del mio programma, principalmente il "collo di bottiglia" del mio programma è la valutazione del seno e del coseno di una certa quantità, (quantità che varia volta per volta ovviamente),funzioni che occupano oltre l'80% del tempo processore. (Ovviamente le funzioni seno e coseno sono richiamate moooooooolte volte )

Il programma è già multithreaded, quindi sfrutta più core contemporaneamente.

Inoltre se possibile sono graditi dei consigli sull'allocazione e deallocazione rapida di vettori di dimensioni non particolarmente elevate qualche decina di elementi per intenderci, ma ciò apporterebbe solo marginali incrementi prestazionali.

Non so se è possibile utilizzare qualche libreria in maniera facile adatta allo scopo, per effettuare le operazioni trigonometriche.

SO Windows 7 RC Build 7100
IDE Visual Studio Team System 2010 Beta 1 (mi da un incremento di prestazioni rispetto a Visual Studio 2008 di circa il 20%)

[Tommo]

Sicuro che non puoi usare qualcosaltro?

Per esempio il coseno dell'angolo tra 2 vettori si trova col prodotto scalare, che è decisamente più veloce di qualsiasi funzione trigonometrica.
Altro non saprei proprio, senza sapere codice e algoritmo ci vorrebbe la palla di vetro

[Rossi88]

Originariamente inviato da Tommo

Sicuro che non puoi usare qualcosaltro?

Per esempio il coseno dell'angolo tra 2 vettori si trova col prodotto scalare, che è decisamente più veloce di qualsiasi funzione trigonometrica.
Altro non saprei proprio, senza sapere codice e algoritmo ci vorrebbe la palla di vetro

Innanzitutto grazie della risposta, comunque praticamente devo scindere un'esponente con argomento complesso nella parte reale ed immaginaria, quindi valuto il seno e coseno. Ad ogni modo posto la parte di codice di interesse che così è tutto più chiaro e non serve la palla di cristallo

void derivsU(double x ,double y[],double dydx[],double lam)
{
	/* La parte iniziale del vettore contiene i dati legati alla parte
	 * reale dell'ampiezza, mentre la seconda parte contiene la parte
	 * immaginaria.
	 */
	 int i,j;
	 int n=N;

	double q1,q2,esp;
	double K;double Kmod=(1+cos(2*pi/lam*x));
	for(i=1;i<=n;i++){
		dydx[i]=0;
		dydx[i+n]=0;
		for(j=1;j<=n;j++){
			K=Kmod*intePerParam[i][j];

			esp=x*beta[i][j];
			q1=K*sin(esp);
			q2=K*cos(esp);
			   
			dydx[i]-=q1*y[j]+q2*y[j+n];
			dydx[i+n]+=q2*y[j]-q1*y[j+n];

		}    
	}

}

Vorrei sottolineare come abbia provato anche altre soluzioni, ad esempio q1*=sin(esp) e q2*=cos(esp) ma i risultati sono analoghi, quindi il problema è proprio della valutazione del seno e del coseno e non del prodotto (che dovrebbe tra le funzioni più veloci per un processore dopo somma e sottrazione)

La funzione che ho riportato è richiamata anche oltre 3.000.000 di volte (è un dato indicativo), mentre N può assumere valore che spaziano fra qualche decina a 100-200

Ciò che mi lascia perplesso inoltre è che le funzioni che occupano la maggior parte del tempo processore sono sin(esp) e cos(esp) mentre cos(2*pi/lam*x) no, risulta trascurabile (almeno stando all'analizzatore di performance di Visual Studio)

[Tommo]

Dunque, mi sembra già ottimizzato a bestia
poi vista la complicatezza dei calcoli che svolgi, scommetto che non puoi scambiare imprecisione per velocità no?
Tipo che so, sostituire seno e coseno con una table di valori, calcolare meno valori e poi sfocarli ecc ecc.

L'unica cosa da fare sarebbe riorganizzare l'algoritmo in modo di svolgere meno volte la parte critica, comunque non capisco nemmeno che stai facendo (dannati numeri complessi ) quindi non saprei come...

Comunque stai facendo un filtro su un'immagine praticamente, quindi ti consiglierei CUDA, se ben usato queste robe se le mangia (a precisione singola però).

[Unrue]

Originariamente inviato da Rossi88

Ciò che mi lascia perplesso inoltre è che le funzioni che occupano la maggior parte del tempo processore sono sin(esp) e cos(esp) mentre cos(2*pi/lam*x) no, risulta trascurabile (almeno stando all'analizzatore di performance di Visual Studio)

Ciao,
io ti consiglio di introdurre nel tuo codice le liberie ACML, utilizzando la funzione vettoriale vrda_sincos. In pratica, raggruppi in un vettore tutti gli elementi su cui vuoi fare seni e coseni e con UNA SOLA chiamata li calcoli tutti di un botto, sfruttando anche le proprietà trigonometriche.

Nel tuo caso dei raggruppare i vari esp

Link utili:
http://developer.amd.com/cpu/Librari...s/default.aspx
http://developer.amd.com/cpu/Librari...rda_005fsincos

PS: Perchè nei cicli for parti da 1 e non da 0 ?

[Rossi88]

Originariamente inviato da Tommo

Dunque, mi sembra già ottimizzato a bestia
poi vista la complicatezza dei calcoli che svolgi, scommetto che non puoi scambiare imprecisione per velocità no?
Tipo che so, sostituire seno e coseno con una table di valori, calcolare meno valori e poi sfocarli ecc ecc.

L'unica cosa da fare sarebbe riorganizzare l'algoritmo in modo di svolgere meno volte la parte critica, comunque non capisco nemmeno che stai facendo (dannati numeri complessi ) quindi non saprei come...

Comunque stai facendo un filtro su un'immagine praticamente, quindi ti consiglierei CUDA, se ben usato queste robe se le mangia (a precisione singola però).

Si diciamo che l'ho ottimizzato per benino, quando ho avuto il programma ci impiegava 16 volte di più per fare le stesse cose, poi ho fatto qualche ottimizzazione...

Comunque non si tratta di un filtro su un'immagine, è l'applicazione di una teoria dei campi elettromagnetici.

La possibilità di utilizzare una look-up table non credo faccia al caso mio, comunque grazie per il suggerimento

[Rossi88]

Originariamente inviato da Unrue

Ciao,
io ti consiglio di introdurre nel tuo codice le liberie ACML, utilizzando la funzione vettoriale vrda_sincos. In pratica, raggruppi in un vettore tutti gli elementi su cui vuoi fare seni e coseni e con UNA SOLA chiamata li calcoli tutti di un botto, sfruttando anche le proprietà trigonometriche.

Nel tuo caso dei raggruppare i vari esp

Link utili:
http://developer.amd.com/cpu/Librari...s/default.aspx
http://developer.amd.com/cpu/Librari...rda_005fsincos

PS: Perchè nei cicli for parti da 1 e non da 0 ?

Ma il mio processore è Intel, non so se vadano bene ugualmente le librerie della AMD.

La domanda dell'indice di partenza è una bella domanda, praticamente il programma mi è stato dato e poi io l'ho ottimizzato (pesantemente, ma togliendo il collo di bottiglia del seno e coseno potrei aumentare la velocità di altre 4-5 volte immagino) e nel programma di partenza tutti gli array sono utilizzati con indice di partenza 1 (sprecando quindi la memoria per il primo elemento)

[Unrue]

Originariamente inviato da Rossi88

Ma il mio processore è Intel, non so se vadano bene ugualmente le librerie della AMD

Si, vanno benissimo Anche se perdi un pò di performance rispetto a processori AMD, guadagni comunque molto rispetto al codice originale. RIguardo l'indice, va bene anche se parti da 1,alla fine sprechi un elemento, va bè. Solo che è molto facile confondersi poi..

[Rossi88]

Originariamente inviato da Unrue

Si, vanno benissimo Anche se perdi un pò di performance rispetto a processori AMD, guadagni comunque molto rispetto al codice originale. RIguardo l'indice, va bene anche se parti da 1,alla fine sprechi un elemento, va bè. Solo che è molto facile confondersi poi..

Tu per caso le hai già sfruttate in qualche ambito? che miglioramenti hai ottenuto?

(Grazie comunque del suggerimento vedrò di utilizzare la libreria )

[Unrue]

Originariamente inviato da Rossi88

Tu per caso le hai già sfruttate in qualche ambito? che miglioramenti hai ottenuto?

(Grazie comunque del suggerimento vedrò di utilizzare la libreria )

Le sto utilizzando proprio in questo periodo ed i miglioramenti sono di un buon 25%. Ma tutto dipende dal numero di seni e coseni che devi calcolare. Nel tuo caso ad esempio, se n è molto piccolo, non avrai un grande vantaggio.

[Rossi88]

Originariamente inviato da Unrue

Le sto utilizzando proprio in questo periodo ed i miglioramenti sono di un buon 25%. Ma tutto dipende dal numero di seni e coseni che devi calcolare. Nel tuo caso ad esempio, se n è molto piccolo, non avrai un grande vantaggio.

Un 25% non si butta di certo via
Comunque N varia da qualche decina a 100-200, per molto piccolo su che ordine di grandezza siamo?

[Unrue]

Originariamente inviato da Rossi88

Un 25% non si butta di certo via
Comunque N varia da qualche decina a 100-200, per molto piccolo su che ordine di grandezza siamo?

Si va bene direi. Per i piccolo intendo intorno a 10. Comunque nel tuo caso, siccome dici che la funzione derivsU la chiami molte volte, devi fare N*M, dove M è il numero di volte che chiami tale funzione.

Un altro mio consiglio è di fare un unrolling del loop più interno con passo 2. Proprio in questi giorni ho a che fare con una funzione chiamata moltissime volte. Un unrolling con passo 2 mi ha fatto raddoppiare la velocità di esecuzione.

Esempio:

      for (i = 0; i < 100; i++)
        a += vect[i];

//Unroll passo 2:

      for (i = 0; i < 100; i += 2)
      {
        a += vect[i];
        a += vect[i+1];
      }

Ovviamente devi gestire il resto nel caso che il numero di cicli non sia divisibile per 2.
Fatto con il passo2, prova con 4, ed 8.

Ultimo consiglio, dichiara double dydx[] come restrict ( double* restrict dydx) e metti -restrict nei flags di compilazione.

[Torav]

anche io ultimamente mi sono sbattuto parecchio per l'ottimizzazione di qualche programmino numerico in ambito scientifico e ho notato che la miglior ottimizzazione si ottiene solamente utilizzando l'algoritmo migliore, ma immagino che tu sia già arrivato a questo punto
prima di tutto immagino che esp possa avere qualsiasi valore giusto? perchè se (come nel mio caso ad esempio) sai che può avere solo valori molto bassi puoi tranquillamente utilizzare gli sviluppi in serie di sin e cos. Se, come credo, questo non è il tuo caso puoi provare a calcolare solo il sin (o il cos) e poi usare sqrt(1- sin^2), io, prima di rendermi conto che effettivamente lo sviluppo era la cosa migliore da fare, avevo ottenuto un discreto miglioramento (con un test "sintetico" veniva fuori un 30% se non sbaglio).

[_Claudio]

Hai provato a cercare qualche libreria che calcola seno e coseno in tempi più rapidi? Immagino usi la math.h...

Altrimenti l'unica soluzione è rivedere le chiamate perchè chiamare 3000000 di volte una funzione è veramente pesante (e nelle ottimizzazioni si parte sempre dal numero maggiore, dannate derivate parziali)... che so magari con qualche stratagemma riesci a dimezzare, in fin dei conti i calcoli nel campo complesso derivano dalla circonferenza goniometrica che è simmetrica rispetto l'origine quindi in sostanza cambiano i segni ma le "forme" nei 4 pezzetti di piano sono sempre le stesse...

[Tommo]

Se beta viene aggiornato meno spesso di quanto tu calcoli derivsU, puoi salvarti il seno e coseno di beta dentro un'altro array (caching), avendo quindi un costo costante per ogni chiamata di derivsU.

Inoltre mi pare ci siano istruzioni vettoriali (SIMD) che calcolano 4 seni e coseni in una sola volta, potrebbero interessarti.

[Rossi88]

Ringrazio tutti delle risposte.

Ho provato ad effettuare l'unroll del ciclo più esterno (un unroll completo, ho fatto giusto una prova su un caso particolare, un unroll di 64) ma le prestazioni non miglioravano (anzi peggioravano leggermente, anche se ciò non ha molto senso)

per l'opzione restrict, in visual studio la parola chiave è __restrict ma se la uso da errore, inoltre su MSDN per utilizzare restrict è indicata la modifica da fare al compilatore ma tale opzione non è presente nel mio.... (eppure ho consultato la sezione della versione che utilizzo di Visual studio )

per quanto riguarda la possibilità di utilizzare cos(x)=sqrt(1-sin(x)^2) in questo caso perderei l'informazione legata al segno, oppure dovrei fare degli if, ma a quanto ho letto gli if rallentano l'esecuzione del codice.

Per quanto riguarda le librerie, in realtà avevo provato ad utilizzare Intel Compiler, che aveva Math kernel Library, avevo utilizzato su macchina virtuale. Il problema è che non è gratuito il compilatore dell'Intel nè le librerie, sarebbe un po' scocciante ogni tot giorni formattare e reinstallare oppure ricopiare un'immagine della partizione. Si potrebbe pensare di compilare su macchina virtuale ed eseguire sull'host ma il problema è che su macchina virtuale non posso fare l'analisi delle performance (non sono emulate delle cose che non ricordo esattamente).

Per quanto riguarda le librerie dell'AMD, le ho scaricate installate, l'istruzione che è riportata sulla guida

cl driver.c -Ic:/acml4.3.0/win64_mp/include
c:/acml4.3.0/win64_mp/lib/libacml_mp_dll.lib

non mi funziona da il seguente errore

driver.c
c1:  fatal error C1083: Cannot open source file: 'driver.c': No such file or directory

Ho provato a inserire gli header manualmente e le librerie ma purtroppo non sono molto pratico, e la compilazione termina (se uso una delle funzioni del file di intestazione) con un classico unresolved external symbol



Ho provato a seguire qualche guida per utilizzare le librerie ma niente da fare

Se qualcuno può indicarmi come utilizzare le librerie ACML, o indicarmi qualche link o guida

[_Claudio]

È chiaro che comunque c'è una discrepanza computazionale, la richiesta di 3000000 di chiamate a funzione non è eseguibile a bassa latenza su un normale computer.

O prevedi il fatto che quando si eseguono i calcoli vi è un tempo di attesa oppure non rimane che adottare tecnologie hardware più potenti o addirittura cluster di computer, se le finanze lo permettono.

Una domanda: i calcoli devono essere svolti per forza sequenzialmente?
Non è possibile dividere quei 3000000 di chiamate su più thread (core)?

[Unrue]

Originariamente inviato da Rossi88

Ringrazio tutti delle risposte.

Ho provato ad effettuare l'unroll del ciclo più esterno (un unroll completo, ho fatto giusto una prova su un caso particolare, un unroll di 64) ma le prestazioni non miglioravano (anzi peggioravano leggermente, anche se ciò non ha molto senso)

Ti avevo suggerito quello più interno Quando fai l'unroll le prestazioni possono peggiorare, tutto dipende dalla cache. Però in generale, siccome togli un sacco di if alla fine di ogni ciclo, si migliora. Inoltre un unroll di 64 è esagerato,( gestire i resti da 1 a 63 è pazzesco !) infatti ti avevo suggerito di partire con 2,4,8 ecc...

Originariamente inviato da Rossi88

l'opzione restrict, in visual studio la parola chiave è __restrict ma se la uso da errore, inoltre su MSDN per utilizzare restrict è indicata la modifica da fare al compilatore ma tale opzione non è presente nel mio.... (eppure ho consultato la sezione della versione che utilizzo di Visual studio )

Purtroppo non conosco Visual Studio,ma comunque restrict è presente nello standard C99, prova a guardare se è già configurato per tale standard.

Originariamente inviato da Rossi88

Per quanto riguarda le librerie, in realtà avevo provato ad utilizzare Intel Compiler, che aveva Math kernel Library, avevo utilizzato su macchina virtuale. Il problema è che non è gratuito il compilatore dell'Intel nè le librerie, sarebbe un po' scocciante ogni tot giorni formattare e reinstallare oppure ricopiare un'immagine della partizione. Si potrebbe pensare di compilare su macchina virtuale ed eseguire sull'host ma il problema è che su macchina virtuale non posso fare l'analisi delle performance (non sono emulate delle cose che non ricordo esattamente).

Si, infatti Tra ACML e MKL ti ho consigliato le prime proprio perché gratuite.

Originariamente inviato da Rossi88

Per quanto riguarda le librerie dell'AMD, le ho scaricate installate, l'istruzione che è riportata sulla guida

cl driver.c -Ic:/acml4.3.0/win64_mp/include
c:/acml4.3.0/win64_mp/lib/libacml_mp_dll.lib

non mi funziona da il seguente errore

driver.c
c1:  fatal error C1083: Cannot open source file: 'driver.c': No such file or directory

Ho provato a inserire gli header manualmente e le librerie ma purtroppo non sono molto pratico, e la compilazione termina (se uso una delle funzioni del file di intestazione) con un classico unresolved external symbol

L'errore è chiaro, avrai qualche path sbagliato. Ma anche su questo non posso aiutarti non essendo pratico di Visual Studio.

[Rossi88]

Originariamente inviato da _Claudio

È chiaro che comunque c'è una discrepanza computazionale, la richiesta di 3000000 di chiamate a funzione non è eseguibile a bassa latenza su un normale computer.

O prevedi il fatto che quando si eseguono i calcoli vi è un tempo di attesa oppure non rimane che adottare tecnologie hardware più potenti o addirittura cluster di computer, se le finanze lo permettono.

Una domanda: i calcoli devono essere svolti per forza sequenzialmente?
Non è possibile dividere quei 3000000 di chiamate su più thread (core)?

Il problema non è tanto la latenza fra una chiamata e l'altra quanto l'esecuzione del seno e del coseno, stando all'analizzatore di Perforance di Visual Studio oltre l'80% del tempo processore è occupato nell'esecuzione di queste due funzioni. Ho già previsto il programma della possibilità di sfruttare multithreading, che ovviamente dimezza esattamente il tempo di esecuzione (il mio processore è Dual Core) ma basta cambiare un parametro e può lanciare anche 3,4,5 .... thread tutti in parallelo e sincronizzati. Il mio obiettivo è quindi cercare di utilizzare dei metodi per ridurre il costo computazionale del calcolo del seno e del coseno, utilizzando magari qualche libreria.

[_Claudio]

Originariamente inviato da Rossi88

Il problema non è tanto la latenza fra una chiamata e l'altra quanto l'esecuzione del seno e del coseno, stando all'analizzatore di Perforance di Visual Studio oltre l'80% del tempo processore è occupato nell'esecuzione di queste due funzioni. Ho già previsto il programma della possibilità di sfruttare multithreading, che ovviamente dimezza esattamente il tempo di esecuzione (il mio processore è Dual Core) ma basta cambiare un parametro e può lanciare anche 3,4,5 .... thread tutti in parallelo e sincronizzati. Il mio obiettivo è quindi cercare di utilizzare dei metodi per ridurre il costo computazionale del calcolo del seno e del coseno, utilizzando magari qualche libreria.

Visto che è il calcolo del seno e del coseno "pesante"... hai provato a vedere se puoi costruirtela da te la libreria?
Se usi angoli entro una certa approssimazione puoi ad esempio tabularti... a costo di usare un buon 5-6MB di memoria però hai un accesso a costo costante senza calcoli, meglio di così non saprei proprio.