Exercices
Écrivez une implémentation en virgule fixe du générateur de Mandelbrot.
a.
Vous remarquerez que les performances sont incohérentes entre différents pixels et différentes images. Pourquoi cela ?
b.
Quelle est l’intensité arithmétique du corps de boucle le plus interne, en opérations par octet accédé à la mémoire ? Quelle est la limite de performance correspondante pour votre CPU ARM ? Comment se compare-t-elle à vos performances observées ?
c.
Mesurez les métriques de performance suivantes pour le corps de boucle le plus interne :
▪
instructions par itération
▪
instructions par opération
▪
CPI
▪
taux d’échec de cache
d.
Utilisez l’assemblage en ligne pour mettre en œuvre le corps de boucle le plus interne et mesurez l’impact sur les performances par rapport aux métriques de la partie c. Quelle est la rapidité par rapport au code généré par le compilateur ?
Parallélisez le générateur d’ensemble de Mandelbrot en utilisant OpenMP. Appliquez la directive parallel-for à la boucle la plus externe (ligne).
a.
Mesurez le nombre moyen de cycles requis pour chaque itération de la boucle la plus interne (pour évaluer le polynôme) pour un thread et deux threads pour la trame initiale. Utilisez ces mesures pour calculer l’accélération, en termes de pixels par seconde, de deux threads par rapport à un thread.
b.
Mesurez le temps de calcul de tous les pixels de la première image lorsque vous utilisez l’ordonnancement dynamique par rapport à l’ordonnancement statique.
Qu’est-ce qui rend difficile l’application de l’opération SIMD pour le générateur d’ensembles de Mandelbrot ? Quelle est la méthode la plus efficace pour appliquer l’opération SIMD pour le générateur d’ensembles de Mandelbrot ?
Mesurez le débit d’écriture effectif pour le Framebuffer Linux. Est-il équivalent au débit d’écriture pour un tableau de mémoire alloué depuis le tas ?
Calculez l’intensité arithmétique du programme de transformation d’image en opérations par pixel. Quelle est sa limite de performance étant donné le débit mémoire effectif de votre CPU ARM ? Comment se compare-t-elle à vos performances observées ?
Utilisez OpenMP pour ajouter le support multicore au programme de transformation d’image en virgule fixe. Pour ce faire, appliquez le pragma for parallèle à la boucle la plus extérieure (ligne).
Mesurez ses performances sur un CPU ARM à quatre cœurs. Comment ses performances évoluent-elles lorsqu’il est exécuté avec un, deux, trois et quatre threads ?
Utiliser des intrinsèques pour ajouter le support NEON SIMD à la version en virgule fixe du programme de transformation d’image. Utilisez des opérations à quatre voies pour effectuer les calculs suivants pour un groupe de quatre pixels : localisation du pixel source, extraction de la fraction et calcul du poids. Dans quelle mesure cela améliore-t-il les performances ?
Nous ne pouvons pas facilement optimiser le programme du générateur de Mandelbrot en utilisant des instructions SIMD, car les pixels voisins peuvent nécessiter un nombre différent d’évaluations polynomiales et chaque itération du polynôme dépend de l’évaluation précédente. Une autre approche consiste à implémenter la boucle en assemblage en ligne, à la dérouler par au moins quatre, puis à utiliser le pipelining logiciel pour améliorer le CPI de la boucle. Dans ce cas, nous devrions éviter les branchements conditionnels à l’intérieur de la boucle déroulée. Puisque les valeurs c divergentes continueront à diverger avec les évaluations suivantes, nous pouvons attendre de vérifier la condition de sortie de la boucle après chaque groupe de quatre itérations. Cependant, l’exécution d’évaluations polynomiales supplémentaires après qu’un Pc() diverge potentiellement en dehors du cercle de rayon 2 nous obligera à prendre en compte les exigences de plage supplémentaires pour notre format à virgule fixe. Recalculez les exigences de plage en virgule fixe pour cette optimisation et déterminez dans quelle mesure cela réduira le niveau de zoom maximal.
Les principaux avantages de la virgule fixe sont la réduction de la latence des opérations et la possibilité d’éviter les conversions de type dans certains types de codes graphiques. Le chapitre 2 met en évidence un exemple de programme dont les performances sont sensibles à la latence des opérations, la méthode de Horner. En supposant que nous puissions tolérer les limitations de plage de la virgule fixe dans notre code de la méthode de Horner, sa conversion en virgule fixe améliorerait-elle les performances ? Expliquez votre réponse.
La section 3.6.5 a montré deux implémentations différentes d’une macro de préprocesseur d’addition en virgule fixe généralisée. La première a été générée par gcc sous optimisation maximale, la seconde a été codée à la main en utilisant le langage d’assemblage en ligne. Les deux implémentations ont nécessité approximativement le même nombre d’instructions.
a.
Démontrez les dépendances de données en lecture après écriture dans les deux implémentations. En supposant que le processeur utilise une instruction unique, dans l’ordre d’émission, et en supposant que la latence de toutes les opérations arithmétiques entières est de quatre cycles, combien comparer le nombre de cycles de décrochage de données nécessaires pour les deux implémentations.
b.
Réécrire la version d’assemblage en ligne de la macro d’addition à virgule fixe pour planifier les instructions de sorte que les instructions dépendantes soient séparées autant que possible. Dans quelle mesure les décrochages sont-ils réduits, en supposant la latence donnée dans la partie a ?
c.
Écrire un code qui démontre comment les trois implémentations (générées par le compilateur, en assemblage inline, et en assemblage inline programmé) peuvent être caractérisées pour la performance.
Dans cette question, nous examinons l’implémentation d’assemblage en ligne de la multiplication généralisée à virgule fixe décrite dans la section 3.6.6.
a.
Comment se compare-t-elle, en termes de nombre d’instructions et de performances d’exécution, par rapport au code équivalent généré par le compilateur pour :
res = (((long long long)op1 * (long long long)op2) >> (rp1>rp2?rp1:rp2)). +(rp1>rp2 ? ((((long long)op1 * (long long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long long)op2) >> (rp2-1))&1));
Veillez à utiliser les commutateurs « -O3 » et « -marm » lors de la compilation avec gcc.
b.
Planifiez les instructions de la version d’assemblage en ligne de la macro multiplier pour minimiser les décrochages de dépendance de données. Mesurez sa performance par rapport à la version donnée dans la section 3.6.6.
c.
Pour l’implémentation de l’assemblage en ligne, combien de plus tout au long est obtenu si modifié de telle sorte que les positions de point de radix sont fixes au lieu de variables comme dans le code ? Pour cette question, utilisez à la fois le nombre d’instructions et le comportement réel d’exécution.
Le calcul des valeurs de pixels pour un ensemble de Mandelbrot nécessite une fonction pour convertir le nombre d’itérations dans les canaux de couleur R, G et B. Le réglage des trois canaux à la même valeur générera une image grise, donc la pente de chaque fonction de canal de couleur doit être unique, et celle qui est la plus grande déterminera la teinte de l’image.
Comme décrit dans la section 3.8.1, le nombre d’évaluations polynomiales peut dépasser la valeur qui dépasse la plage d’un canal de couleur. Pour éviter un débordement potentiel, vous devez utiliser l’arithmétique saturante lors du calcul de chaque valeur de pixel. De cette façon, si la valeur calculée dépasse la valeur maximale autorisée, réglez-la sur la valeur maximale.
Écrivez une macro C qui effectue une multiplication saturante non signée de 8 bits. La fonction prendra deux opérandes de 8 bits et produira un produit de 8 bits réglé sur 255 si le produit dépasse 255. La macro ne doit pas inclure d’instructions de branchement et être programmée pour les dépendances de données.
Cet exercice explorera l’augmentation de la précision des types à virgule fixe pour le générateur de Mandelbrot à 64 bits.
a.
En utilisant un taux de zoom de 1,5zoom, à quel niveau peut-on zoomer sur l’image avant de dépasser cette précision ?
b.
Définir une macro en C pour ajouter deux (64,56) valeurs à virgule fixe. La macro peut effectuer l’addition de 128 bits en utilisant quatre additions de 32 bits et utiliser le drapeau de report pour mettre en œuvre les reports de chaque groupe de 32 bits vers le groupe de 32 bits le plus significatif suivant.
c.
Définir une macro en C pour multiplier deux (64,56) valeurs à virgule fixe. Construisez cette macro au-dessus de la macro d’addition de 64 bits de la partie b.
Comme le montre la figure 3.6, une façon simple d’effectuer une multiplication de 64 bits est d’effectuer une série de quatre opérations de multiplication/mutation/accumulation de 32 bits qui produisent chacune un résultat de 64 bits.
Figure 3.6. Un multiplicateur de 8 bits implémenté avec des multiplicateurs de 4 bits.
Dans la figure, deux valeurs de 4 bits A et B contenant les valeurs 1110 et 1410 sont chacune séparées en deux portions supérieure et inférieure de 2 bits, nommées A1, A0 et B1 et B0. En supposant que les produits sont de 4 bits, le produit de 8 bits est calculé comme (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Pour appliquer cela à une multiplication de 64 bits, chacune des deux valeurs de 64 bits doit être maintenue dans deux registres de 32 bits. Chaque multiplication génère un résultat de 64 bits, ce qui permet d’obtenir un produit final de 128 bits.
d.
En utilisant ces macros, implémentez un générateur d’ensemble Mandelbrot de 64 bits et mesurez la différence de performance qui en résulte.
e.
Implémentez les deux macros en langage d’assemblage en ligne et mesurez l’accélération du résultat du générateur Mandelbrot par rapport à celui de la partie d.
.