[C/C++] Consigli ottimizzazione velocità

[Rossi88]

Originariamente inviato da _Claudio

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.

Purtroppo non ci sono limiti per per gli angoli quindi tabulare i risultati non può essere effettuato, ciò che mi servirebbe è riuscire ad utilizzare una libreria che sfrutti le nuove potenzialità dei processori come la KML o (meglio come suggerisce Unrue ) la ACML della AMD che è gratuita ma nell'utilizzare le librerie esterne e linkarle al programma non sono capace.

Se qualcuno può postarmi qualche guida e o suggerimento per utilizzare librerie gliene sarei grato

Attualmente non sono pratico nella creazione di una libreria, menche meno nella creazione di una libreria altamente ottimizzata per il calcolo del seno e coseno, non conosco così affondo l'assembly da poter sfruttare a basso livello le istruzioni processore ed ottenere un risultato migliore di quanto non faccia la funzione standard. Ho provato ad utilizzare qualche altra funzione trovata in rete, dei metodi di approssimazione del seno e del coseno, fra quei pochi che sono riusciti a far funzionare risultavano tutti più lenti.

[Rossi88]

Originariamente inviato da Unrue

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...




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




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



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

A quanto dice MSDN _restrict è analogo della keyword restrict definita dallo standard C99 ma è utilizzabile sia a codice C che C++, sono riuscito ad utilizzare la keyword, praticamente non può essere utilizzata per double dydx[] ma per double *dydx, ho provato ad utilizzarla ma nessun miglioramento probabilmente è legata alla mancata modificata effettuata al compilatore,stando a MSDN dovrei cambiare le runtime library ma la runtime library che mi serve non c'è nell'elenco.

Per l'unroll ho provato a fare un unroll di passo 2 per un'altra funzione che anch'essa richiamata svariate milioni di volte ma non prevede la necessità di utilizzare seno e coseno e quindi risulta ben più veloce ma anche in questo caso non ho riscontrato miglioramenti. Nel corpo di questa funzione vi sono vari prodotti e somme. Ho provato a fare un unroll di 64 semplicemente per fare una cosa più estrema e verificare se c'erano dei miglioramenti, non pensando ad eventuali riscontri negativi per quanto riguarda la cache.

Devo cercare di utilizzare quelle librerie che mi hai consigliato, ma sono un po' in alto mare, non capisco perchè non ci sia una guida facile facile su come utilizzare delle librerie non fornite direttamente con l'IDE

[Unrue]

Originariamente inviato da Rossi88

A quanto dice MSDN _restrict è analogo della keyword restrict definita dallo standard C99 ma è utilizzabile sia a codice C che C++, sono riuscito ad utilizzare la keyword, praticamente non può essere utilizzata per double dydx[] ma per double *dydx, ho provato ad utilizzarla ma nessun miglioramento probabilmente è legata alla mancata modificata effettuata al compilatore,stando a MSDN dovrei cambiare le runtime library ma la runtime library che mi serve non c'è nell'elenco.

Per l'unroll ho provato a fare un unroll di passo 2 per un'altra funzione che anch'essa richiamata svariate milioni di volte ma non prevede la necessità di utilizzare seno e coseno e quindi risulta ben più veloce ma anche in questo caso non ho riscontrato miglioramenti. Nel corpo di questa funzione vi sono vari prodotti e somme. Ho provato a fare un unroll di 64 semplicemente per fare una cosa più estrema e verificare se c'erano dei miglioramenti, non pensando ad eventuali riscontri negativi per quanto riguarda la cache.

Devo cercare di utilizzare quelle librerie che mi hai consigliato, ma sono un po' in alto mare, non capisco perchè non ci sia una guida facile facile su come utilizzare delle librerie non fornite direttamente con l'IDE

Scusa un attimo,ma questo errore:

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

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

Il cui comando hai preso da qua presumo:

http://biowulf.nih.gov/doc/acml/Link...2fWindows.html

Il file driver.c magari non va sostituito con il nome del tuo sorgente? Quello è solo un esempio presumo..

Riguardo il restrict, se non hai miglioramenti vuol dire che il compilatore non fa ottimizzazioni su quel loop, oppure che le fa ed è riuscito a capire che tale puntatore ha un utilizzo ristretto, quindi aggiungendola tu non cambia nulla. Io comunque la lascerei, non si sa mai..

[Tommo]

Originariamente inviato da Rossi88

Purtroppo non ci sono limiti per per gli angoli quindi tabulare i risultati non può essere effettuato.

Beh, non vedo il motivo: dato che seno e coseno sono funzioni periodiche la tabella deve coprire solo l'intervallo 0...pigreco.
Quindi basta riportare l'angolo in questo intervallo (una divisione) e regolare il segno di conseguenza.

Tutto sta a decidere la risoluzione dei valori della tabella, ma come dice _Claudio in 5-6 mb ci stanno milioni di valori... difficile notare la differenza in precisione.
Mentre quella in velocità sarebbe decisamente evidente

[Rossi88]

Originariamente inviato da Unrue

Scusa un attimo,ma questo errore:

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

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

Il cui comando hai preso da qua presumo:

http://biowulf.nih.gov/doc/acml/Link...2fWindows.html

Il file driver.c magari non va sostituito con il nome del tuo sorgente? Quello è solo un esempio presumo..

Riguardo il restrict, se non hai miglioramenti vuol dire che il compilatore non fa ottimizzazioni su quel loop, oppure che le fa ed è riuscito a capire che tale puntatore ha un utilizzo ristretto, quindi aggiungendola tu non cambia nulla. Io comunque la lascerei, non si sa mai..

Effettivamente..... si era solo un esempio comunque ho provato a quindi a mettere tutti i file del mio programma e mettere i percorsi corretti, non da alcun errore del tipo non riesco a trovare o aprire quel file o quella libreria, ma da lo stesso identico errore che mi da compilando direttamente dall'IDE ossia unresolved external linker, eppure ho provato sia con le librerie nella cartella win64 che in quela win64_mp, ho provato persino a mettere tutte le librerie ma mi da errore dicendo che alcune librerie vanno in conflitto chissà come mai

Comunque ho creato una stupida libreria, una libreria che come unica funzione ha questa

int SempliceSomma(int a,int b);

una libreria statica (.lib)

poi ho creato un semplice programma

#include <stdio.h>
#include <windows.h>
#include <IntestazioneLibreria.h>

int main()
{
	printf("Prova Compilazione\n");
	printf("%d \n",SempliceSomma(3,6));
	system("PAUSE");
	return 0;
}

e il tutto era compilato correttamente, ho ovviamente fatto le modifiche necessarie per far vedere file di intestaizone e libreira.
Poi ho fatto gli stessi identici passi nel programma vero e proprio ma l'unresolved link rimane

riporto l'errore esatto comunque:

error LNK2019: unresolved external symbol _fastsincos referenced in function _derivsU

Ma tu usi la stessa identica versione delle librerie? non vorrei che fosse una versione buggata.

[Rossi88]

Originariamente inviato da Tommo

Beh, non vedo il motivo: dato che seno e coseno sono funzioni periodiche la tabella deve coprire solo l'intervallo 0...pigreco.
Quindi basta riportare l'angolo in questo intervallo (una divisione) e regolare il segno di conseguenza.

Tutto sta a decidere la risoluzione dei valori della tabella, ma come dice _Claudio in 5-6 mb ci stanno milioni di valori... difficile notare la differenza in precisione.
Mentre quella in velocità sarebbe decisamente evidente

Creare i valori tabellati non sarebbe un grosso problema

int i;
double *ValoriTabellati;
ValoriTabellati=(double *)malloc(sizeof(double)*40000001);
for (i=0;i<=40000000;i++)
{
	ValoriTabellati[i]=sin(2*3.14*i/40000000);
}

Anche il tempo di calcolo non è eccessivo (istantaneo) il tempo di premere start... (inizio ad avere dei dubbi sull'analizzatore di performance di Visual Studio.... )

con fmod dovrei ottenere il resto della divisione fra esp e 2*pi, poi dovrei ottenere l'indice corrispondente all'angolo ed arrotondarlo con floor, e poi accedere a quell'indice.

Implemento il tutto e faccio sapere i risultati

[Rossi88]

Ho implementato il codice ed ho fatto qualche prova, innanzitutto riporto il codice:

int i;
	
ValoriTabellatiCos=(double *)malloc(sizeof(double)*(NTABELLATI+1));
ValoriTabellatiSin=(double *)malloc(sizeof(double)*(NTABELLATI+1));
for (i=0;i<=NTABELLATI;i++)
{
	ValoriTabellatiCos[i]=cos(DUEPERPISUNTABELLATI*i);
	ValoriTabellatiSin[i]=sin(DUEPERPISUNTABELLATI*i);
}

Nella funzione derivsU invece ho sostituito al posto di

q1=K*sin(esp);
q2=K*cos(esp);

le seguenti righe di codice

if (esp==0)
{
	q1=0;
	q2=K;
}
else
{
	ValoreAssoluto=fabs(esp);
	IndiceRicerca=(int) floor((fmod(ValoreAssoluto,DUEPERPI)*NTABELLATISUDUEPERPI)+0.5);

	q1=K*esp/ValoreAssoluto*ValoriTabellatiSin[IndiceRicerca];
	q2=K*ValoriTabellatiCos[IndiceRicerca];
}

Ho fatto qualche prova per valutare tempi di esecuzione e correttezza dell'algoritmo, ho preso in esame un caso in cui la funzione era richiamata circa 3.700.000 volte, ed N=26 per un totale di circa 190.000.000 chiamate alle due funzioni trigonometriche incriminate cos(esp) e sin(esp).

Senza Tabella 1.04
Con Tabella da 700000 valori 1.02
Con Tabella da 400000 valori 0.52
Con Tabella da 40000 valori 0.37
Con Tabella da 4000 valori 0.39

Quindi al di sotto di 40000 valori il tempo è praticamente identivo (il tempo lo rilevo a mano e poi avevo decine di pagine internet aperte e visual studio aperto quindi qualche secondo di differenza ci può stare comunque anche per un 4000 valori l'errore massimo relativo è dell'ordine dello 0.01% quindi del tutto trascurabile (farò alter prove per verificare tempi ed accuratezza dei risultati).

Nel caso questa dovesse risultare un'ottimo approccio penso di utilizzare una tabella da 40000 valori che mi da un errore relativo di due ordini di grandezza inferiore.

Se qualcuno ha suggerimenti per migliorare quella porzione di codice, in particolare per eliminare l'if che dovrebbe far perdere un bel po' di tempo o per ovviare a qualche chiamata a funzioni fmod e floor non esiti a postare

Qualsiasi commento e soluzione è ben accetta.

(Ovviamente i ringraziamenti a tutti coloro che stanno cercando e che cercheranno di aiutarmi sono scontati )

[Rossi88]

Comunque inizio ad avere dei forti dubbi sull'analizzatore di performace di Visual Studio 2010 beta 1, perchè il tempo per creare le due tabelle da 40.000.000 valori quindi 80.000.000 chiamate alle funzioni seno e coseno (e altrettante divisioni) risulta essere pressochè nullo 1-2 secondi

[Tommo]

Vedi che era più veloce

Cmq l'if lo puoi proprio togliere, dato che 0.0/0.0 coi float è definito come #inf e cos0 e' 1 (valore che puoi includere nella tabella).
Potresti anche togliere floor() che dato il minimo intervallo di angolo tra il valore approssimato per difetto e per eccesso non porta ad alcuna imprecisione.

Per il resto se vuoi misurare il tempo è meglio che usi GetQueryPerformanceCounter & co su windows che dà la massima precisione...

Inoltre dovresti considerare di ridurre le chiamate a funzione, che hanno si un peso irrisorio ma quando n fai 3.700.000 iniziano a farsi sentire come overhead
Prova a mettere quella che è derivsU all'interno di un ciclo while di una funzione più ampia, per esempio.

[Rossi88]

Originariamente inviato da Tommo

Vedi che era più veloce

Cmq l'if lo puoi proprio togliere, dato che 0.0/0.0 coi float è definito come #inf e cos0 e' 1 (valore che puoi includere nella tabella).
Potresti anche togliere floor() che dato il minimo intervallo di angolo tra il valore approssimato per difetto e per eccesso non porta ad alcuna imprecisione.

Per il resto se vuoi misurare il tempo è meglio che usi GetQueryPerformanceCounter & co su windows che dà la massima precisione...

Inoltre dovresti considerare di ridurre le chiamate a funzione, che hanno si un peso irrisorio ma quando n fai 3.700.000 iniziano a farsi sentire come overhead
Prova a mettere quella che è derivsU all'interno di un ciclo while di una funzione più ampia, per esempio.

il problema è che non è l'unica funzione che può essere chiamata, era solo un esempio, infatti è nominata come derivsU, ma ce ne sono anche altre derivsCR, derivsCH, derivsL, derivsUL ecc... per le quali ho comunque verificato che il collo di bottiglia era sempre cos(esp) e sin(esp), per evitare di fare degli if o degli switch utilizzo dei puntatori a funzione, ed è per questo che ho estrapolato la parte di codice in delle funzioni a sè stanti.

per quanto riguarda 0/0 si evvero da #inf, però poi quel valore lo utilizzo nelle successive due istruzioni di codice

dydx[i]-=q1*y[j]+q2*y[j+n];
dydx[i+n]+=q2*y[j]-q1*y[j+n];

e quindi dydx[i] anzichè essere pari a q2*y[j+n] diventa pari a #inf, compromettendo tutti i risultati perchè poi l'#inf è propagato a y[] e quindi per tutta l'esecuzione del programma

Utilizzerò GetQueryPerformanceCounter come mi hai suggerito per meglio misurare i tempi di esecuzione

[Tommo]

Uhm già allora l'if serve... comunque quanto pesa dipende dall'incidenza di casi true sul totale: cioè se esp è 0 pochissime volte il valutare l'if potrebbe diventare più pesante di fare il calcolo e basta.
Comunque non saprei come renderlo più leggero, probabilmente l'if non pesa poi tanto.

Cmq i puntatori a funzione pesano molto di più delle chiamate a funzione normali, secondo me potresti farci qualcosa.
Certo, perderesti tantissimo in mantenibilità e gestibilità...

[Unrue]

Originariamente inviato da Rossi88

Ma tu usi la stessa identica versione delle librerie? non vorrei che fosse una versione buggata.

Io utilizzo la versione Linux delle ACML. In pratica a te manca l'equivalente in Linux del flag -L e -l .. Non basta dargli l'header

[Rossi88]

Originariamente inviato da Unrue

Io utilizzo la versione Linux delle ACML. In pratica a te manca l'equivalente in Linux del flag -L e -l .. Non basta dargli l'header

Io gli do l'header e dico al linker dove andare a pescare le librerie, ho provato a fare la stessa cosa con le librerie SDL, (delle librerie multipiattaforma per creare applicazioni grafiche in C) e funziona. Tu che compilatore usi?? gcc immagino?

L'idea di utilizzare delle tabelle con i valori già precalcolati è interessante, però riuscire ad utilizzare delle librerie specificatamente pensate per sfruttare le nuove potenzialità dei processori, poter utilizzare in maniera più veloce i vettori mi piaceva ancor di più.

[Unrue]

Originariamente inviato da Rossi88

Io gli do l'header e dico al linker dove andare a pescare le librerie, ho provato a fare la stessa cosa con le librerie SDL, (delle librerie multipiattaforma per creare applicazioni grafiche in C) e funziona. Tu che compilatore usi?? gcc immagino?

Sto usando vari compilatori tra i quali Intel, PGI e GCC. Ma devi per forza usare Visual Studio? Prova con Gcc per Windows a vedere se ti funziona.

[Rossi88]

A distanza di tempo ed usando Visual studio 2010 beta 2 ho riprovato ad utilizzare le librerie ACML e (probabilmente sbagliavo qualcosa oppure Visual Studio 2010 beta 1 aveva qualche problema) la procedura per chi volesse utilizzare tali librerie con Visual studio è la seguente:

1) installare ACML
2) nel programma inserire gli header necessari, ad esempio

#include <acml.h>

3) poi inserire nel progetto i percorsi per gli header

Project->NomeProgetto Properties->Configuration Properties->VC++ Directories->Include Directories

ed inserire il percorso opportuno
4) indicare i file .lib necessari, ad esempio

Project->NomeProgetto Properties->Configuration Properties->VC++ Directories->Linker->Input->Additional Dependencies

ed inserire C:\AMD\acml4.3.0\win64_mp\lib\libacml_mp_dll.lib o i file .lib opportuni
5) copiare tutti i file .dll nella cartella di lavoro del progetto

(Testato con Windows 7)

[Unrue]

Ciao,
visto che lavori su processore Intel, forse sono più indicate le MKL ( Math Kernel Library), sviluppate da Intel stessa. A suo tempo ti indicai le ACML in quanto le MKL ancora non le conoscevo

Inoltre ti consiglio anche di utilizzare il compilatore Intel ( icc), versione free. In genere è più performante di gcc, sopratutto su architetture Intel.

[HyperText]

Dico una stupidaggine: hai provato ad utilizzare funzioni inline?

[Rossi88]

@HyperText

No non ho provato ad usare funzioni inline, devo approfondire dato che se definisco la funzione con la parola chiave __inline il compilatore mi da un unresolved link.

Utilizzando ACML sono riuscito ad ottenere oltre il 50% di riduzione dei tempi di calcolo (rispetto a prima dell'utilizzo di ACML, quindi complessivamente un codice 30 volte più veloce ), ho trasformato i calcoli in calcoli fra vettori e matrici. Il punto debole del programma rimane sempre il calcolo del seno e del coseno (che effettuo tramite la funzione fastsincos()) che stando a Visual Studio mi occupa il 70% del tempo.

@Unrue
Sai per caso di qualche buona guida per le funzioni BLAS?

Finora sono riuscito a trovare tutte le funzioni che mi servivano tranne una, il prodotto elemento per elemento (element-wise) fra due vettori (o matrici) tu conosci quale funzione devo usare? (ho letto che si parla anche di Hadamard product, ho trovato anche una funzione ma non c'è in ACML)
Attualmente faccio il prodotto elemento per elemento tramite il classico ciclo for e ciò mi comporta oltre il 15% di tempo, se potessi farlo tramite BLAS otterrei una ulteriore riduzione di tempo (tutte le funzioni BLAS che ho utilizzato comportano meno dello 0.1% del tempo ).

Comunque ho letto che le GPU consentono di effettuare il calcolo del seno e del coseno con 1 ciclo quindi se riuscissi ad utilizzare la GPU avrei un incremento prestazionale enorme. Purtroppo ACML-GPU non è thread-safe (quindi non potrei usare più thread) ed inoltre consente solo di effettuare prodotti fra matrici e non di usare sin e cos quindi non molto utile nel mio caso.

Per quanto riguarda MKL e il compilatore Intel non sono gratuiti per Windows mi sembra, anche se in MKL si ha la possibilità di fare operazioni direttamente con i numeri complessi, che mi eviterebbe di passare per le funzioni sin e cos, quindi potrebbe essere molto interessante.

[Unrue]

Originariamente inviato da Rossi88

@HyperText

Utilizzando ACML sono riuscito ad ottenere oltre il 50% di riduzione dei tempi di calcolo (rispetto a prima dell'utilizzo di ACML, quindi complessivamente un codice 30 volte più veloce ), ho trasformato i calcoli in calcoli fra vettori e matrici. Il punto debole del programma rimane sempre il calcolo del seno e del coseno (che effettuo tramite la funzione fastsincos()) che stando a Visual Studio mi occupa il 70% del tempo.

E' un ottimo risultato! Considera che quei calcoli li devi fare, quindi non puoi azzerare quel tempo E con MKL farai sicuramente meglio.

Originariamente inviato da Rossi88

@Unrue
Sai per caso di qualche buona guida per le funzioni BLAS?

La migliore guida è la guida ufficiale:

http://www.netlib.org/blas/

Originariamente inviato da Rossi88

Finora sono riuscito a trovare tutte le funzioni che mi servivano tranne una, il prodotto elemento per elemento (element-wise) fra due vettori (o matrici) tu conosci quale funzione devo usare? (ho letto che si parla anche di Hadamard product, ho trovato anche una funzione ma non c'è in ACML)
Attualmente faccio il prodotto elemento per elemento tramite il classico ciclo for e ciò mi comporta oltre il 15% di tempo, se potessi farlo tramite BLAS otterrei una ulteriore riduzione di tempo (tutte le funzioni BLAS che ho utilizzato comportano meno dello 0.1% del tempo ).

Non sono esperto di BLAS, ma sicuramente c'è la funzione di cui hai bisogno, Quelle che iniziano con DGEM mi pare.

Originariamente inviato da Rossi88

Comunque ho letto che le GPU consentono di effettuare il calcolo del seno e del coseno con 1 ciclo quindi se riuscissi ad utilizzare la GPU avrei un incremento prestazionale enorme. Purtroppo ACML-GPU non è thread-safe (quindi non potrei usare più thread) ed inoltre consente solo di effettuare prodotti fra matrici e non di usare sin e cos quindi non molto utile nel mio caso.

Non sempre le GPU ti danno benefici, dipende dai casi. E magari in questo caso potresti non "threadizzare" la parte di codice che passi alla GPU. Tanto poi ci pensa la GPU stessa a parallelizzarla.

Originariamente inviato da Rossi88

Per quanto riguarda MKL e il compilatore Intel non sono gratuiti per Windows mi sembra, anche se in MKL si ha la possibilità di fare operazioni direttamente con i numeri complessi, che mi eviterebbe di passare per le funzioni sin e cos, quindi potrebbe essere molto interessante.

Devi usare per forza Visual Studio e Windows? Passare al compilatore Intel ( e a Linux per la versione free) secondo me ti darebbe un grosso boost. C'è la versione gratuita che comprende anche le MKL.:

http://software.intel.com/en-us/arti...ware-download/

PS: Hai lasciato l'unroll dei loop come ti avevo suggerito a suo tempo?

Considera anche che non puoi ottimizzare all'infinito, arrivi ad un certo punto che più di lì non vai. 30 volte più veloce mi sembra già più che ottimo.

[The3DProgrammer]

in genere buona pratica è eliminare tutti i rapporti, calcolare prima il reciproco e poi fare il prodotto col divisore.

double rec = 1/x;
double z=y*x;

invece di

double z = y/x;

ora non ricordo bene l'assembly che viene generato nei due casi, ma se non mi sbaglio il primo caso è abbastanza + veloce (mi pare di ricordare che per il calcolo del reciproco c'è un'istruzione ad hoc o qualcosa del genere)

bye