C++ exp LUT (tabella di ricerca)

Question

In una simulazione legata alla CPU C++ che sto scrivendo, ho tracciato un collo di bottiglia tramite valgrind nel mio programma su cmath::exp. Attualmente mangia oltre il 40% del mio tempo di simulazione. Posso vincolare l'input a un dominio relativamente piccolo, ma mi piacerebbe controllare l'accuratezza. Stavo considerando di passare a una LUT (tabella di ricerca) per sostituire exp ma non sono abbastanza sicuro di come fare questa "strada giusta" (tm). Preoccupazioni che ho:

1. grandi tabelle di ricerca non si adatteranno nella cache rallentando così l'accesso
2. modo migliore per convertire un doppio ingresso per un numero intero per l'accesso in tabella di ricerca
3. Se la soluzione (2) dipende dalla pendenza della funzione di input?
4. Sto reinventando la ruota - è già stato fatto prima?

Qual è il modo migliore per implementare/(includere da una libreria) un LUT per exp?

Answer 1

Una domanda molto simile è stata posta prima. Ecco la mia risposta:

• Fast Exp calculation: possible to improve accuracy without losing too much performance?

L'approccio è stato suggerito dall'autore di tale questione, e sono stato in grado di attuare in modo efficiente (tavolino di ricerca e minimale lavoro extra dopo la ricerca). È in C#, ma la traduzione in C++ dovrebbe essere semplice e posso aiutarti se ti trovi nei guai.

Answer 2

1. La dimensione ottimale della tabella di ricerca è determinata dal compromesso tra prestazioni, accuratezza e complessità di implementazione. Dovrai profilare il profilo, non possiamo dirti la risposta (non conosciamo la risposta).

2. Utilizzare lrint da <math.h> per convertire double a long int. Non sono sicuro che sia in <cmath>.

3. Non sono sicuro di quale pendenza abbia a che fare con la conversione di numeri in virgola mobile in numeri interi. Potresti approfondire su cosa ti preoccupa?

4. Sì, stai reinventando la ruota. Quello che stai facendo è stato fatto più e più volte da chiunque abbia mai implementato una biblioteca matematica. C'è molta letteratura sull'argomento.

Una tabella di ricerca diretta è tutt'altro che ottimale. Dovrai utilizzare una sorta di approssimazione polinomiale, forse a tratti con coefficienti selezionati da una tabella di ricerca. Per una funzione liscia e prevedibile come exp, un polinomio ti darà una precisione molto più elevata a parità di sforzo computazionale. I polinomi richiesti dipenderanno dal compromesso tra complessità e accuratezza, nonché dal fatto che si desideri minimizzare l'errore previsto, minimizzare l'errore massimo o utilizzare qualche altra funzione di perdita.

Limitare il dominio di exp in realtà non aiuta molto, dal momento che è così facile espandersi all'intero dominio.

// only works for x in [0, 1] 
double exp2_limited(double x); 

// works for all x, but doesn't handle overflow properly 
double exp2(double x) 
{ 
    return scalbn(exp2_limited(fmod(x, 1.0)), (long) floor(x)); 
} 

Sommario:

• Devi conoscere la precisione richiesta prima di poter progettare una tale funzione.

• È inoltre necessario conoscere la funzione di perdita (ad esempio, scegliere la funzione di perdita).

• Devi profilare prima di sapere quanto è veloce.

• Utilizzare polinomi.

Answer 3

Ho avuto questo problema e ho preso alcuni campioni di stack per diagnosticare. Quello che fa è dire da dove provengono le chiamate e qual è il valore dell'argomento. Ho scoperto che quando exp veniva chiamato da determinati luoghi, il valore dell'argomento era altamente ripetibile.

Questo suggeriva un approccio di memoizzazione, che ha fatto un'enorme differenza.

aveva bisogno di una semplice funzione "wrapper":

double exp_cached(double arg, double* old_arg, double* old_result){ 
    if (arg== *old_arg) return *old_result; 
    *old_arg = arg; 
    *old_result = exp(arg); 
    return *old_result; 
} 

e ovunque exp(foo) una volta si chiamava, lo fanno:

static double old_arg = -999999999, old_result; 
... 
... exp_cached(foo, &old_arg, &old_result)... 

In questo modo, exp non viene chiamato se il suo argomento a quel luogo da cui è chiamato ha lo stesso valore di argomento di prima.