View Full Version : [C] Ottimizzazione spinta
Ciao ragazzi,
avrei bisogno di ultraottimizzare questo spezzone di codice:
register float32 * punt;
register float32 sample_r,sample_i;
punt = &trdiff[4*i_idx1];
for(m = 0; m < *ntot; m++)
for( k = 0; k < i_idx2-i_idx1+1 ; k++) {
sample_r = *punt + up_interp* *(punt+1);
sample_i = *(punt + 2) +up_interp* *(punt + 3);
punt +=4;
numm[ m][k].r += sample_r;
numm[ m][k].i += sample_i;
denom[m] += sample_r * sample_r + sample_i * sample_i;
}
Secondo voi si può migliorare utilizzando l'aritmetica dei puntatori o richiamando direttamenre istruzioni assembly?( denom e trdiff sono float32, numm è complex32)
Grazie :)
Ikon O'Cluster
30-06-2009, 01:52
Secondo me oltre un certo punto ogni ottimizzazione "sintattica" apporta vantaggi trascurabili... ad un certo punto bisogna considerare l'ottimizzazione "semantica". Ad esempio il tuo codice ha complessità O(N*M) dove:
N = max(*ntot)
M = max(i_idx2-i_idx1+1)
Puoi fare di meglio?
P.S.: Se vuoi ottimizzare (sintatticamente) al max devi avere una grande conoscenza del compilatore. Non so quale usi, ma cmq non sono espertissimo in questo campo. Prova a studiare le tecniche di ottimizzazione che usa il tuo compilatore e cerca di scrivere il codice che le sfrutti al meglio. Ma il gioco non vale la candela... almeno per la maggior parte delle applicazioni che riesco ad immaginare!
Ciao,
grazie per la risposta. Dunque, sto utilizzando il compilatore Intel. Diciamo che questa applicazione non dove girare su molte macchine ma più o meno sempre sulla stessa ( AMD Opteron)
Riguardo il tuo consiglio, purtroppo non posso eliminare il doppio ciclo.
Ikon O'Cluster
30-06-2009, 10:37
Eh... su quello non avevo dubbi! :D Non intendevo eliminarlo, ma se per esempio da O(N*M) riesci a passare a O(N*log(M)) soprattutto se M >> N allora può essere conveniente... se poi quella è già la soluzione più efficiente pace! Cmq io penso che una ottimizzazione spinta del codice non ti permetta di guadagnare poi tanto... voglio esagerare e dico un 7% (sul tempo di esecuzione).
Ikon O'Cluster
30-06-2009, 10:40
Ma forse ho esagerato troppo... :sofico:
^TiGeRShArK^
30-06-2009, 12:37
se hai + di un core a disposizione sulla tua macchina puoi usare i thread, altrimenti credo che la cosa migliore sarebbe ottimizzare l'algoritmo come ha già detto ikon'cluster....
cmq è una matrice completa?
o magari è sparsa o diagonale?
Negli ultimi due casi dovresti poter guadagnare molto a livello algoritmico.....
Dato che lo stride di punt è 4 elementi, dovrebbe essere possibile usare le SIMD... forse :stordita:
Oppure potresti spezzare il for interno su tutti i cores con threads che lo eseguirebbero più o meno parallelamente.
L'unica ottimizzazione che mi viene in mente in quel codice è salvarsi i_idx2-i_idx1+1 invece che ricalcolarlo N*M volte... ed anche usare ++k e ++m invece che k++ e m++... dovrebbe risparmiare un paio di istruzioni asm.:stordita:
banryu79
30-06-2009, 13:21
ed anche usare ++k e ++m invece che k++ e m++... dovrebbe risparmiare un paio di istruzioni asm.:stordita:
Il preincremento è più "economico" del postincremento in termini di assembly? Nel senso, lo è sempre? Non conosco niente di assembly...
^TiGeRShArK^
30-06-2009, 13:59
con i compilatori moderni utilizzare a++ o ++a dovrebbe essere la stessa cosa.
Anche il fatto di salvarsi la sottrazione in una variabile locale *dovrebbe* essere già fatto dal compilatore...
Il preincremento è più "economico" del postincremento in termini di assembly? Nel senso, lo è sempre? Non conosco niente di assembly...
teoricamente (da quello che mi hanno detto) il posticremento prende il valore dell'espressione ci aggiunge 1 e lo rimette al suo posto... invece il preincremento aggiunge direttamente 1 al valore.
quindi si dovrebbe risparmiare una creazione ed un'assegnazione.
Ma non so niente di assembly :D
Cmq io lo uso sempre perchè non costa niente, se funziona meglio :asd:
In ogni caso il compilatore *dovrebbe* farle da solo ste cose, ma dato che qua si parla di ottimizzazione massima il *dovrebbe* non è ammesso...
Ikon O'Cluster
30-06-2009, 14:48
se hai + di un core a disposizione sulla tua macchina puoi usare i thread, altrimenti credo che la cosa migliore sarebbe ottimizzare l'algoritmo come ha già detto ikon'cluster....
cmq è una matrice completa?
o magari è sparsa o diagonale?
Negli ultimi due casi dovresti poter guadagnare molto a livello algoritmico.....
C'è da dire che ottimizzare in sè x sè non dice niente... bisogna sapere se uno ha vincoli stretti su memoria o processore e in quale proporzione...
C'è da dire che ottimizzare in sè x sè non dice niente... bisogna sapere se uno ha vincoli stretti su memoria o processore e in quale proporzione...
Intendo ottimizzare il tempo di esecuzione.
wingman87
30-06-2009, 15:18
Potresti anche salvare il valore di *ntot in una variabile per evitare la dereferenziazione, risparmieresti un accesso alla memoria. Ma temo che tutte le ottimizzazioni che stiamo proponendo siano già attuate dal compilatore...
Allora...io proverei così:
sample_r = A + K * B;
sample_i = C + K * D;
Quindi
denom[m] += A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB
N = i_idx2 - i_idx1
denom[m] = somma per K che va da 0 a N(A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB) = NA^2 + NC^2 + (B^2 + D^2)*somma(K^2) + (AB + CD)*somma(K)
somma(K) = (N*(N+1))/2
somma(K^2) = N(N+1)(2N+1)/6
Da numm[m][k] ci passi solo una volta, cosa c'è prima dentro la struct ?
Allora...io proverei così:
sample_r = A + K * B;
sample_i = C + K * D;
Quindi
denom[m] += A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB
N = i_idx2 - i_idx1
denom[m] = somma per K che va da 0 a N(A^2 + K^2*B^2 + AKB + C^2 + K^2*D^2 + CKB) = NA^2 + NC^2 + (B^2 + D^2)*somma(K^2) + (AB + CD)*somma(K)
somma(K) = (N*(N+1))/2
somma(K^2) = N(N+1)(2N+1)/6
Da numm[m][k] ci passi solo una volta, cosa c'è prima dentro la struct ?
Ciao cionci. In numm[m][k] non c'è nulla prima, sono inizializzate a 0.0.
Aspetta, non avevo visto che punt viene incrementato di 4...cancella tutto quello che ho scritto :D
Ikon O'Cluster
30-06-2009, 19:40
Aspetta, non avevo visto che punt viene incrementato di 4...cancella tutto quello che ho scritto :D
AUAUHAUHAUH :D :D :D Grandissima sola...
fracarro
01-07-2009, 20:53
Intendo ottimizzare il tempo di esecuzione.
Potresti provare a compilare con il gcc insieme all'opzione -O3 e vedere come va l'eseguibile rispetto a quello compilato con l'intel.
Da quello che ho letto in giro il compilatore intel dovrebbe generare codici più performanti a patto di compilare con i flag giusti che sfruttano l'architettura. Fai il confronto tra i due eseguibili e se va meglio quello prodotto dal gcc allora forse devi usare qualche altro flag sul compilatore intel.
P.S. Anche se sono poche righe di codice, potresti analizzarle sfruttando il valgrind come profiler e il kcachegrind per vedere ogni istruzione e ogni ciclo quando tempo di cpu impiega (è il modo migliore per trovare i colli di bottiglia).
Ikon O'Cluster
01-07-2009, 21:30
fracarro x esempio è uno furbo...
banryu79
02-07-2009, 09:25
Magari può interessarti Acovea (http://www.coyotegulch.com/products/acovea/index.html)
fracarro
02-07-2009, 09:52
Magari può interessarti Acovea (http://www.coyotegulch.com/products/acovea/index.html)
Molto interessante. Lo proverò prima possibile. Grazie del suggerimento.
!k-0t1c!
02-07-2009, 13:15
Rapidamente:
rimuovi immediatamente register dalle dichiarazioni delle variabili. I complatori, da 5anni a questa parte, usano i registri meglio di come tu farai mai e forzarli a usare registri è spesso *controproducente*.
se N e M sono decentemente grandi, parallelizzare è d'obbligo. In questo modo dovresti avere un risparmio enorme in termini di tempo (questo codice dovrebbe scalare in maniera quasi lineare rispetto al numero di core).
se non consideri l'opzione parallelismo allora l'aritmetica dei puntatori potrebbe effettivamente essere d'aiuto, ma dipende dal compilatore
usa l'Intel C/C++ compiler e abilita tutte le ottimizzazioni (incluse SSE4.1), e non scordarti di specificare come processore minimo uno che supporti tutte le caratteristiche che hai scelto in maniera tale da evitare che il compilatore aggiunga controlli sulle caratteristiche della cpu e versioni di fallback dei metodi
se ancora tutto questo non basta e devi effettuare una quantità enorme di questi calcoli, CUDA o OpenCL sono "the way to go"
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.