Abs-max più veloce dell'array float

StackOverflow https://stackoverflow.com/questions/817604

Domanda

Devo disegnare i misuratori di picco per l'audio in tempo reale. Minimo 44100 campioni al secondo per un minimo di 40 flussi. Ogni buffer è compreso tra 64 e 1024 campioni. Devo prendere gli addominali massimi da ogni buffer. (Questi vengono quindi inviati attraverso una sorta di filtro passa-basso e disegnati a intervalli di circa 20 ms.) 

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

Ecco come lo faccio ora. Mi piacerebbe farlo molto più velocemente. I buffer hanno float nell'intervallo da -1 a 1, quindi i fab.

Domanda, c'è un modo complicato per fare questo in modo rapido e veloce?

In caso contrario, esistono ABS senza rami e funzioni MAX per i galleggianti?

modifica: La piattaforma principale è Linux / gcc ma è prevista una porta di Windows (probabilmente con mingw).

modifica, il secondo:
Ho dato l'accettazione a qualcuno a causa della parte riguardante l'attuale struttura algo che era centrale nella domanda.
Proverò a srotolare il ciclo a quattro alla volta, azzerando i segni e quindi ottenendo il massimo con SSE (istruzione maxps) e vedrò se questo non sbuccia la banana. Grazie per i suggerimenti, ho votato alcuni di voi come secondi. :)

È stato utile?

Soluzione

I fab e il confronto sono entrambi molto veloci per i float IEEE (come, in linea di principio, il numero intero singolo-op veloce).

Se il compilatore non sta incorporando entrambe le operazioni, allora premilo fino a quando non lo fa, oppure trova l'implementazione per la tua architettura e incorporala da solo.

Forse potresti ricavare qualcosa dal fatto che i float IEEE positivi vanno nello stesso ordine degli interi con gli stessi schemi di bit. Cioè, 

f > g   iff   *(int*)&f > *(int*)&g

Quindi, una volta che hai fabs, penso che un max senza branch per int funzionerà anche per float (supponendo che abbiano le stesse dimensioni ovviamente). C'è una spiegazione del perché funziona qui: http: //www.cygnus-software .com / documenti / comparingfloats / comparingfloats.htm . Ma il tuo compilatore conosce già tutto questo, così come la tua CPU, quindi potrebbe non fare alcuna differenza.

Non esiste un modo più rapido di complessità per farlo. Il tuo algoritmo è già O (n), e non puoi batterlo e guardare ancora ogni campione.

Suppongo che probabilmente ci sia qualcosa nel SIMD del tuo processore (ovvero SSE2 su Intel) che potrebbe aiutare, elaborando più dati per ciclo di clock rispetto al tuo codice. Ma non so cosa. In tal caso, molto probabilmente sarà più volte più veloce.

Probabilmente potresti parallelizzare su una CPU multi-core, soprattutto perché hai comunque a che fare con 40 flussi indipendenti. Nella migliore delle ipotesi, alcuni fattori saranno più veloci. & Quot; Basta quot &; avvia il numero appropriato di fili extra, dividi il lavoro tra di loro e usa la primitiva più leggera che puoi per indicare quando sono tutti completi (forse una barriera di filo). Non sono del tutto chiaro se stai pianificando il massimo di tutti e 40 i flussi o il massimo di ciascuno separatamente, quindi forse non è necessario sincronizzare i thread di lavoro, oltre a garantire che i risultati vengano consegnati alla fase successiva senza corruzione dei dati.

Probabilmente vale la pena dare un'occhiata allo smontaggio per vedere quanto il compilatore ha srotolato il loop. Prova a srotolarlo un po 'di più, vedi se questo fa la differenza.

Un'altra cosa a cui pensare è il numero di mancati riscontri nella cache e se è possibile ridurre il numero fornendo alla cache alcuni indizi in modo che possa caricare le pagine giuste in anticipo. Ma non ho esperienza con questo, e non darei molte speranze. __builtin_prefetch è l'incantesimo magico su gcc, e immagino che il primo esperimento sarebbe qualcosa come " precarica l'inizio del blocco successivo prima di entrare nel ciclo per questo blocco " ;.

A quale percentuale della velocità richiesta sei attualmente? O è un caso di & Quot; il più velocemente possibile & Quot ;?

Altri suggerimenti

Esistono fab senza filiali documentate su http: // www. scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

Tieni inoltre presente che le versioni recenti di GCC includeranno un ramo fabs per te, usando le istruzioni MMX. Ci sono anche fmin e fmax, ma GCC non li incorporerà (otterrai call fmin).

Cose da provare:

  • fabs () potrebbe non essere una funzione incorporata.
  • Le istruzioni speciali di assemblaggio potrebbero essere di aiuto. Su Intel, SSE ha un'istruzione per calcolare il massimo di quattro float contemporaneamente.
  • In mancanza, la specifica IEEE 754 è tale che se aeb sono non negativi , allora a < b è equivalente a * (int *) & amp; a < * (int *) & amp; b. Inoltre, per qualsiasi a, puoi calcolare -a da a lanciando MSB. Insieme, queste proprietà potrebbero abilitare alcuni hack bit-twiddling.
  • Hai davvero bisogno del massimo di ogni campione? Forse il massimo potrebbe verificarsi più di una volta, aprendo la possibilità di non esaminare ogni input.
  • Puoi calcolare il massimo in modo streaming?

Potresti voler guardare Eigen .

È una libreria di modelli C ++ che utilizza set di istruzioni SSE (2 e successive) e AltiVec con grazioso fallback a codice non vettoriale .

  

veloce. (Vedi benchmark).
   I modelli di espressione consentono di rimuovere in modo intelligente i provvisori e abilitare la valutazione pigra, quando ciò è appropriato: Eigen si occupa di questo automaticamente e gestisce anche l'aliasing nella maggior parte dei casi.
  La vettorializzazione esplicita viene eseguita per i set di istruzioni SSE (2 e successive) e AltiVec, con un grazioso fallback a codice non vettoriale. I modelli di espressione consentono di eseguire queste ottimizzazioni a livello globale per espressioni intere.
   Con oggetti di dimensioni fisse, l'allocazione dinamica della memoria viene evitata e i loop vengono srotolati quando ciò ha senso.
   Per le matrici di grandi dimensioni, viene prestata particolare attenzione alla compatibilità con la cache.

rispondere a una domanda con un'altra domanda non è esattamente rispondere, ma ehi ... Neanche io sono uno sviluppatore C ++.

Dato che lo stai sviluppando in C ++ e stai facendo dsp, non riesci a connetterti a Matlab o Ottava (che è opensource) alla matematica per te e ottenere il risultato?

ci sono già funzioni (come conv, fft, ifft, fir e plotting util funzioni come freqz, stem, graph, plot, mesh, ecc.) implementate in quei software. Ho dato un'occhiata a Photoshop e c'è una grande cartella chiamata MATLAB ... con alcuni file .m che ricevono chiamate dall'applicazione, lo inviano a una cosa dinamica matlab quindi restituiscono il risultato all'applicazione.

Spero che sia d'aiuto.

Ottimizzazioni facili che vedo:

  • traduci il ciclo in una versione aritmetica del puntatore (supponendo che il tuo compilatore non lo veda)
  • lo standard IEEE 754 definisce la sua rappresentazione come grandezza del segno. Quindi, impostare il bit più significativo su 0 sarà lo stesso di chiamare fabs (). Forse questa funzione utilizza già questo trucco.

Per il tuo scopo potresti quadrarlo invece di prendere il valore assoluto; come matematicamente | a | lt &; | B | se a ^ 2 < b ^ 2 e viceversa. La moltiplicazione potrebbe essere più veloce di fabs () su alcune macchine (?), Non lo so.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top