TIFO - Implementation

FASTER-FASTER-FASTER!!!

Introduction

• Efficacite
  • Taille des images
  • Contrainte sur le temps de reponse
  • Contrainte sur le materiel (telephone…)
• Solution
  1. Bien penser ses algorithmes (et ss structures de donnes)
  2. Revoir son implementation sur CPU
  3. Eventuellemnt envisager une implementation sur GPU

Bien penser ses algorithmes

• Representation des images
• …

Repenser les algorithmes

• FFT (Fast Fourier Transform)
• …

Representation des images

Comment representer une image

• Matrice
• Vecteur
• Arbre/grpah
  • Max Tree, Min Tree
  • Tree of Shapes…
• …

Matrice, vecteur: bien respecter le cache de la amchine !

Max Tree:
Image:

Max-Tree Correspondant

Racine de l'arbre: image entiere

• On part du
  $min$ de l'image
• Des que le
  $min$ separe 2 regions, on a 2 branches dans notre arbre

Une branche de l'arbre, c'est une region de l'image.

• Un noeud correspond a tous les pixels
• Les feuilles, si elles sont petites et nombreuses elles sont peut-etre que du bruit

Exemple

Calcul de l'ouverture ultime

• Long dans le cas general
• Solution: utilisation du max-tree

On enleve les petites regions et on fait la difference entre l'image d'origine et l'image obtenue. On continue sur les zones plus grosses et on regarde chaque fois le contraste obtenu.

On peut estimer quel est le motif le plus contraste et le garder.

On a des residus en coupant les branches.

On parcours l'image en profondeur avec le niveau de contraste:

UO(noe, parent_leve, max_contrast) {
    node.r=max(parent_level-node.level, max_contrasy)
    for all child c
        UO(c, node_level.r)
}

Resultats:

Format	Nb of pixels	Time (ms)
128x128	16384	0,18
256x256	65536	2,39
512x512	262144	12,01
1024x1024	1048576	52,04
2048x2048	4194304	235,53

Un probleme difficile a la base est rendu plus simple et plus rapide en changeant le codage de l'image

On calcule l'ouverture ultime et on recupere tous les objets saillants

Pour recuperer le texte, on relance l'ouverture ultime sur une partie de l'image

• Repenser les algorithmes
  • Exemple FFT
  • Implementation des filtres
  • L'image integrable

Calcul rapide

• FFT (1965 - Cooley et Tukey) (Gauss 1805??)
• The DFT:

$$x(l)=\sum _{k=0}^{N-1}x(k)e^{-\frac{2j\pi kl}{N}},l=0,...,N-1$$

avec

$N$ complexe mults,

$N-a$ complexe add pour chaque

$I$

• $O(N^2)$

Exploiter la symetrie:

$$\begin{array}{rl}{W}_N& =e^{-\frac{2j\pi }{N}}\\ W_N^{k(N-n)}& =W_n^{-kn}=(W_N^{kn}{)}^{\ast }& (W_N^{kN}=1)\\ W_N^{k(n)}& =W_N^{k(N+n)}=W_N^{(k+N)n}\end{array}$$

On suppose que

$N=2^m$

$$\begin{array}{rl}X(l)& =\sum _{k\text{ pair}}x(k)W_N^{lk}+\sum _{k\text{ impair}}x(k)W_N^{lk}\\ & =\sum _{k=0}^{\frac{N}{2}-1}x(2k)e^{-\frac{2j\pi 2kl}{N}}+\sum _{k=0}^{\frac{N}{2}-1}x(2k+1)e^{-\frac{2j\pi 2(k+1)l}{N}}\\ & =\sum _{k=0}^{\frac{N}{2}-1}x(2k)W_n^{2kl}+\sum _{k=0}^{\frac{N}{2}-1}x(2k+1)W_N^{(2k+1)l}\\ & =\sum _{k=0}^{\frac{N}{2}-1}x(2k)(W_n^2{)}^{kl}+W_n^l\sum _{k=0}^{\frac{N}{2}-1}x(2k+1)(W_N^2{)}^{kl}& W_n^2=W_{\frac{N}{2}}\end{array}$$

• $\frac{N}{2}$ DFT des echantillons pairs,
  $\frac{N}{2}$ DFT des echantilons imapairs

$$X(l)=X_p(l)+W_N^l{X}_i(l)$$

• Somme de 2 DFTs de
  $\frac{N}{2}$ echantillons

• $2{\frac{N}{2}}^2+N$ mutliplications
• Passe de
  $O(N^2)$ a
  $O(N\log N)$

L'image integrale

Souvent besoin de calculer des moyennes/ecart-types dans une image

On passe un masque sur une image

La valeur obtenue est la sommes des pixels

Si on veut calculer l'aire d'un rectangle aligne sur les axes:

$$Aire(ABCD)=C-B-D+A$$

Implementation des filtres

• Decomposition des convolutions (filtres separables)
  • $N\times N\to N+N$
  • La taille du filtre a un impact sur la vitesse d'execution
• Prise en compte des bordures?

Implementation sur CPU

• Utilisation du parallelisme
• Utilisation des instruction SIMD
  • Auto-vectorisation
  • Intrinsics SIMD
  • Boost::simd
• …

CPU

SIMD

Single instruction multiple data

• MMX, SSE, AVX, NEON…
• Registres sous formes de vecteurs

• Bien adapte a l'image

SIMD: un peu d'histoire

• 1997 jeu d'instruction MMX sur P166 (intel) L'ordinateur multimedia - Regsitre 64bits paratages avec le FPU
• 1997 jeu d'instrucutin - 3DNow ! (AMD)
• 1999 jeu d'instruction SSE - Registres 128bits
• SSE2, SSE3, SSE4 - Registres 128bits
• AVX - Registres 512 256bits
• AVX512 - Registres 512bits
• Neon sur ARM

SIMD Usage

• Par le compilateur:
  • Active sur GGC avec l'option -ftree-vectorize (par defaut active avec -O3)
  • Renseigner l'option -march=(corei7,native...)
  • On peut avoir plus d'info avec les options -fopt-info-vec-* (-fopt-info-vec-optimized -fopt-info-vec-missed)
• Sorties:
  • knn.cpp.229: note: LOOP VECTORIZED (attention: plusieurs passes)

Auto-vectorisation

for (std::size_t x = 0; x < l; ++x) {
    output_image[x] = input_image1[x] + input_image2[x];
} // en complet desaccord avec notre coding style

Entrees:

• -Wall -O3 -g -Wextra -Werror -m64 -march=native -ftree-vectorize -std=c++11 -fopt-info-vec-optimized #-fopt-info-vec-missed

Sorties:

• Par le compilateur (auto-vectorisation)
  • Pas toujours facile
  • s'assure que les donnees soient alignees (quasi impossible en cpp :-( )
    • __attribute__((aligned(TL_IMAGE_ALIGNEMENT)))
    • std::align
    • Alignas(.)
    • aligned_alloc
  • __restrict__
  • assume dans ICC
• Bonnes pratiques:
  • Utiliser des indices plutot que des pointeurs
  • Array of Structures vs Structure of Arrays
  • Ne pas interrompre une boucle

for (k = 0 ; k < size_vect; k++) {
    double t = v_example[k] - data[k_data++];
    res += t * t;
    // if (res > tresh) {
    //     breaks;
    // }
}
res *= -g;
return exp(res)

• SIMD - intrinsics
  • Possible de les utiliser en c/c++
• Exemple:

for (std::size_t x = 0; x < l; x+=16) {
    __m128i v_input_image1 = _mm_loadu_si128((const __m128i*)(input_image1 + x));
    __m128i v_input_image2 = _mm_loadu_si128((const __m128i*)(input_image2 + x));
     __m128i v_output1 = _mm_add_epi8(v_input_image1, v_input_image2);
     _mm_store_si128((__m128i*)(output_image+x), v_output1);
}

• Probleme d'alignement des donnees aligned_alloc
• Difficilement portable

• Function Multiversioning (GCC 4.8)
  • Utile pour la portabilite du programme

__attribute((target("default")))
int foo() {
    // The default version of foo
}
__attribute((target("sse4.2")))
int foo() {
    // foo version for SSE4.2
}
__attribute((target("arch=atom")))
int foo() {
    // foo version for the Intel ATOM processor
}

Boost::simd

• Permet d'ecrire de maniere agnostique vis-a-vis de la vectorisation
• Le code devient portable
• Vectorisation vers certains processeurs gratuite et pour d'autres non

Implementation sur GPU

Une fois qu'on a pousse nos algos a fond sur CPU…

• Implementation sur GPU
  • Cuda
  • OpenCL
  • Compute Shaders
  • …

Compute Shaders

• Glsl "portable" ou autre

On a plein de threads dans chaque work group

Conclusion

• Pas de points "incontournables"
• Reflechir a notre implem pour qu'elle soit la plus efficace possible