Abs-max plus rapide du tableau float

Question

Je dois dessiner des compteurs de pics audio en temps réel. Un minimum de 44100 échantillons par seconde multiplié par un minimum de 40 flux. Chaque tampon contient entre 64 et 1024 échantillons. J'ai besoin de saisir le maximum d'abs de chaque tampon. (Ceux-ci sont ensuite alimentés à travers une sorte de filtre passe-bas et dessinés à des intervalles d'environ 20 ms.)

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

C'est comme ça que je le fais maintenant. J'aimerais le faire beaucoup plus vite. Les tampons ont des flotteurs dans la plage de -1 à 1, d’où les fabs.

Question, y a-t-il un moyen délicat comp-sci quicksort-esque de le faire plus rapidement?

À défaut, les fonctions ABS et MAX sans branchement pour les flotteurs existent-elles?

modifier: La plate-forme principale est Linux / gcc, mais un port Windows est prévu (probablement avec mingw).

modifier, le second:
J'ai donné l'acceptation à un par un à cause de la question de la structure réelle de l'algo qui était au centre de la question.
Je vais essayer de dérouler la boucle à quatre à la fois, de mettre à zéro les signes, puis d'obtenir le maximum avec SSE (instruction maxps) et de voir si cela ne pèle pas la banane. Merci pour les suggestions, j'ai voté pour quelques-uns d'entre vous, en tant que finalistes. :)

Answer 1

Les fabs et la comparaison sont très rapides pour les flottants IEEE (comme, en principe, l’opération sur un seul entier est rapide).

Si le compilateur n'aligne pas les deux opérations, indiquez-le jusqu'à ce qu'il le fasse ou recherchez l'implémentation de votre architecture et intégrez-la vous-même.

Vous pouvez peut-être tirer quelque chose du fait que les positifs flottants IEEE vont dans le même ordre que les entiers avec les mêmes modèles de bits. C'est-à-dire

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

Donc, une fois que vous avez fabriqué, je pense qu’un max sans branche pour int fonctionnera aussi pour float (en supposant qu’ils aient la même taille bien sûr). Il existe une explication de la raison pour laquelle cela fonctionne ici: http: //www.cygnus-software .com / papers / Comparisonfloats / Comparisonfloats.htm . Mais votre compilateur le sait déjà, de même que votre processeur, cela ne fera donc aucune différence.

Il n’existe pas de solution plus complexe et plus rapide. Votre algorithme est déjà O (n), et vous ne pouvez pas battre cela et regardez toujours chaque échantillon.

Je suppose que quelque chose dans le SIMD de votre processeur (c'est-à-dire SSE2 sur Intel) pourrait vous aider, en traitant plus de données par cycle d'horloge que votre code. Mais je ne sais pas quoi. Si tel est le cas, il sera probablement plusieurs fois plus rapide.

Vous pourriez probablement paralléliser sur un processeur multicœur, d’autant plus que vous utilisez 40 flux indépendants de toute façon. Ce sera au mieux quelques facteurs plus rapides. & "Juste &" lancez le nombre approprié de threads supplémentaires, répartissez le travail entre eux et utilisez la primitive la plus légère possible pour indiquer quand ils sont tous terminés (par exemple, une barrière de thread). Je ne sais pas très bien si vous tracez le maximum des 40 flux ou le maximum de chacun séparément. Vous n'avez donc peut-être pas besoin de synchroniser les threads de production, si ce n'est pour vous assurer que les résultats sont livrés à l'étape suivante sans corruption de données.

Cela vaut probablement la peine de jeter un coup d’œil au désassemblage pour voir combien le compilateur a déroulé la boucle. Essayez de le dérouler un peu plus, voyez si cela fait une différence.

Une autre chose à laquelle vous devez réfléchir est le nombre de cache manquants que vous obtenez et la possibilité de réduire ce nombre en donnant quelques indications au cache afin qu’il puisse charger les bonnes pages à l’avance. Mais je n’ai aucune expérience en la matière et je n’aurais pas beaucoup d’espoir. __builtin_prefetch est l'incantation magique sur gcc, et j'imagine que la première expérience ressemblerait à & "; pré-extraire le début du bloc suivant avant d'entrer dans la boucle de ce bloc &";.

Quel est le pourcentage de la vitesse requise en ce moment? Ou est-ce un cas de & Quot; aussi vite que possible & Quot;?

Answer 2

Il existe une documentation sur les installations sans branche répertoriée sur le http: // www. scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

Veuillez noter également que les versions récentes de GCC incorporeront pour vous fabs une agence à distance, en suivant les instructions de MMX. Il existe également fmin et fmax, mais GCC ne les insère pas en ligne (vous obtiendrez un call fmin).

Answer 3

Choses à essayer:

• fabs () n'est peut-être pas une fonction inline.
• Des instructions de montage spéciales peuvent vous aider. Sur Intel, SSE a pour instruction de calculer le maximum de quatre flottants à la fois.
• À défaut, la spécification IEEE 754 est telle que si a et b sont non négatifs , alors un < b est équivalent à * (int *) & et a < * (int *) & amp; b. De plus, pour tout a, vous pouvez calculer -a à partir de en retournant le MSB. Ensemble, ces propriétés pourraient permettre des bidouilles.
• Avez-vous vraiment besoin du maximum de chaque échantillon? Peut-être le maximum pourrait-il se produire plus d'une fois, ouvrant ainsi la possibilité de ne pas examiner chaque entrée.
• Pouvez-vous calculer le maximum en mode streaming?

Answer 4

Vous pouvez consulter Eigen .

C’est une bibliothèque de modèles C ++ qui utilise SSE (2 et versions ultérieures) et des jeux d’instructions AltiVec avec un repli en douceur sur du code non vectorisé .

  

Rapide. (Voir référence).
   Les modèles d'expression permettent de supprimer intelligemment les temporaires et de permettre une évaluation paresseuse, le cas échéant. Eigen s'en charge automatiquement et gère également le crénelage dans la plupart des cas.
  La vectorisation explicite est effectuée pour les jeux d'instructions SSE (2 et ultérieurs) et AltiVec, avec un repli harmonieux sur du code non vectorisé. Les modèles d'expression permettent d'effectuer ces optimisations globalement pour les expressions entières.
   Avec les objets de taille fixe, l’allocation dynamique de mémoire est évitée et les boucles sont déroulées lorsque cela a du sens.
   Pour les grandes matrices, une attention particulière est accordée à la convivialité du cache.

Answer 5

répondre à une question avec une autre question ne répond pas exactement, mais bon ... je ne suis pas non plus un développeur C ++.

Puisque vous développez cela en C ++ et que vous utilisez dsp, ne pouvez-vous pas vous connecter à matlab ou octave (qui est opensource) au calcul pour vous et obtenir le résultat?

il existe déjà des fonctions (telles que conv, fft, ifft, fir et graphes utilitaires telles que freqz, tige, graphe, tracé, maillage, etc.) implémentées dans ces logiciels. J’ai jeté un coup d’œil à Photoshop et il ya un gros dossier appelé MATLAB ... avec des fichiers .m qui reçoivent des appels de l’application, envoyez-le à un objet matlab dynamique puis renvoyez le résultat à l’application.

J'espère que ça aide.

Answer 6

Optimisations simples que je vois:

• traduit la boucle en une version arithmétique du pointeur (en supposant que votre compilateur ne le voit pas)
• la norme IEEE 754 définit sa représentation en tant que signe-magnitude. Ainsi, définir le bit le plus significatif sur 0 sera le même que d'appeler fabs (). Peut-être que cette fonction utilise déjà cette astuce.

Answer 7

Pour ce faire, vous pouvez régler le problème au lieu de prendre la valeur absolue. comme mathématiquement | a | < | b | si a ^ 2 < b ^ 2 et vice versa. La multiplication peut être plus rapide que fabs () sur certaines machines (?), Je ne sais pas.