Construction efficace de la table de surface totale

J’essaie de construire une table de zones sommées pour une utilisation ultérieure dans une routine de seuillage adaptatif. Comme ce code va être utilisé dans des logiciels critiques, j’essaie d’en tirer le plus de cycles possible.

Pour la performance, la table est des entiers non signés pour chaque pixel.

Lorsque j’attache mon profileur, je montre que le plus gros goulot d’étranglement lié aux performances se produit lors de l’exécution de la passe x.

L’expression mathématique simple pour le calcul est:

sat_[y * width + x] = sat_[y * width + x - 1] + buff_[y * width + x] where the running sum resets at every new y position.

Dans ce cas, sat_ est un pointeur 1-D d’entiers non signés représentant le SAT et buff_ est un tampon monochrome non signé de 8 bits.

Mon implémentation ressemble à ceci:

 uint *pSat = sat_; char *pBuff = buff_; for (size_t y = 0; y < height; ++y, pSat += width, pBuff += width) { uint curr = 0; for (uint x = 0; x < width; x += 4) { pSat[x + 0] = curr += pBuff[x + 0]; pSat[x + 1] = curr += pBuff[x + 1]; pSat[x + 2] = curr += pBuff[x + 2]; pSat[x + 3] = curr += pBuff[x + 3]; } }

La boucle est déroulée manuellement car mon compilateur (VC11) ne l’a pas fait pour moi. Le problème que j’ai, c’est que toute la routine de segmentation prend énormément de temps à parcourir cette boucle, et je me demande si quelqu’un a des idées sur ce qui pourrait l’accélérer. J’ai access à tous les ensembles de SSE et à AVX pour toutes les machines sur lesquelles cette routine s’exécute. Par conséquent, si quelque chose se trouve là, ce serait extrêmement utile.

De plus, une fois les derniers cycles compressés, je prévois d’étendre ce processus au multi-cœur, mais je souhaite que le calcul à fil unique soit aussi précis que possible avant de complexifier davantage le modèle.

Vous avez une chaîne de dépendance le long de chaque ligne; chaque résultat dépend du précédent. Donc, vous ne pouvez pas vectoriser / paralléliser dans cette direction.

Toutefois, il semble que chaque ligne est indépendante de toutes les autres. Vous pouvez donc vectoriser / paraléliser en calculant plusieurs lignes simultanément. Vous devez transposer vos tableaux afin de permettre aux instructions vectorielles d’accéder aux éléments voisins en mémoire. ^*

Cependant, cela crée un problème. Marcher le long des rangées serait maintenant absolument épouvantable du sharepoint vue du cache (chaque itération serait un échec du cache). La solution consiste à échanger l’ordre des boucles.

Notez cependant que chaque élément est lu avec précision une fois. Et vous faites très peu de calculs par élément. Vous serez donc fondamentalement limité par la bande passante de la mémoire principale bien avant d’atteindre 100% d’utilisation du processeur.

_{* Cette ressortingction peut être levée dans AVX2, je ne suis pas sûr …}

Algorithmiquement, je ne pense pas que vous puissiez faire pour optimiser cela davantage. Même si vous n’avez pas utilisé le terme cube OLAP dans votre description, vous ne créez en réalité qu’un cube OLAP. Le code que vous avez est l’approche standard pour créer un cube OLAP.

Si vous donnez des détails sur le matériel avec lequel vous travaillez, il se peut que certaines optimisations soient disponibles. Par exemple, il existe une approche de programmation GPU qui peut ou non être plus rapide. Note: Un autre post sur ce fil a mentionné que la parallélisation n’est pas possible. Ce n’est pas nécessairement vrai … Votre algorithme ne peut pas être implémenté en parallèle, mais il existe des algorithmes qui conservent un parallélisme au niveau des données, qui pourraient être exploités avec une approche GPU.