Quelles sont les techniques pour faire du calcul rapide?

Bonjour,

j'aimerais connaître les techniques connues pour faire du calcul rapide, en particulier de l'algèbre linéaire.

Je connaissais les "expression templates" et les techniques de transformations de programme (promotion de scalaire, fusion/fission/blocage de boucles, etc) mais apparemment il y en a d'autres.

Dans une autre discussion, la bibliothèque Eigen a été évoquée.

En regardant les benchmarks, j'ai pensé que cette bibliothèque était générée en fonction de l'architecture (proc,cache,etc).

Or, après téléchargement et lecture de la documentation, j'ai l'impression que ce n'est pas le cas.
Elle rivalise pourtant avec les bibliothèques qui "s'auto-paramètrent" à leur génération.

Comment est-ce possible?

D'après ce que j'ai vu dans les librairies d'algèbre linéaire (Intel, BLAS, ...) de nombreuses optimisations sont très souvent utilisées.

L'ajout de SSE notamment change radicalement la donne. Ensuite la gestion des blocs mémoires de Eigen semble plus proche du fortran que des vector en C++ (je dis ça au feeling en voyant les résultat des benchs, ça me rappelle un bench entre C++ et fortran sur les vecteurs et matrices), ce qui accroit encore la rapidité des opérations visiblement.

Mais il est vrai que les bonnes routines d'algèbre sont rares et/ou payantes. Ensuite il y a aussi les astuces du multi-thread. Ils faudrait comparer toutes ces librairies en mono-thread, sur la même machine.

Quelqu'un a-t-il de l'expérience sur Eigen pour partager ses impressions en pratique ?

JolyLoic ;) ?

Merci pour ta réponse Asohan.

Je viens de retourner sur le site d'Eigen où on peut lire cela :

Citation:

---

Fast. (See benchmark).

• Expression templates allow to intelligently remove temporaries and enable lazy evaluation, when that is appropriate -- Eigen takes care of this automatically and handles aliasing too in most cases.

• Explicit vectorization is performed for the SSE (2 and later), AltiVec, and ARM NEON (new in Eigen 3) instruction sets, with graceful fallback to non-vectorized code. Expression templates allow to perform these optimizations globally for whole expressions.

• With fixed-size objects, dynamic memory allocation is avoided, and the loops are unrolled when that makes sense.

• For large matrices, special attention is paid to cache-friendliness.

---

Les deux premiers points ne me choquent pas et, comme tu l'écris, ils utilisent des instructions SSE (que je n'ai pas vues dans le code mais j'ai jeté un rapide coup d'oeil seulement).

J'ai un problème avec les deux derniers points.
Je ne vois pas comment on peut dérouler efficacement des boucles sans connaître l'architecture de calcul.
Je ne vois pas non plus comment bénéficier efficacement de la réutilisation des caches d'une machine sans connaître leur taille.

Pour la taille du cache c'est intéressant. Sur les benchs on voit nettement la diminution des perfs après certaines tailles d'éléments. C'est peut-être justement parce qu'ils se fichent de la taille propre du cache de l'architecture ? Du coup : plus efficace à faible taille, et retour à "la normale" à grande taille.

Pour les boucles ... là je ne vois pas. Effectivement il y a un problème. A moins que ce ne soit lié à l'architecture RISC et au x86 (il y a bien des prédicteur de branchement pour les calculs : pourquoi pas pour les allocations mémoire ?). Parce que personnellement j'ai toujours vu les machines spécialisées être entièrement remaniées du coté instructions processeur afin d'utiliser des librairies spécialement conçues pour cette architecture.

Dans l'ordre, choisir un bon algo, etre gentil avec son cache, utilisez le SIMD disponible, puis les cores ;)

Citation:

---

Envoyé par Aleph69

Je ne vois pas comment on peut dérouler efficacement des boucles sans connaître l'architecture de calcul.

---

On s'en moque. siu ton tabelau fait 10*10 et que tu sasi ça a l acompil, tu peut dérouler la boucle externe entièrement, tu auras pratiquement toujours du gain.

Citation:

---

Envoyé par Aleph69

Je ne vois pas non plus comment bénéficier efficacement de la réutilisation des caches d'une machine sans connaître leur taille.

---

C'est pas la taille qui compte mais le pattern d'utilisation.

Bonsoir,

sans remettre en cause ce que tu dis, je ne comprends pas bien ce que tu écris Joel.

Concernant la matrice 10x10, est-ce que tu parles de dérouler ta boucle (donc compiler ton code) en fonction de tes données?

L'argument "ce n'est pas la taille qui compte, c'est la manière dont on s'en sert", je le connais...
En pratique, finalement, on se rend compte que la taille joue quand même son rôle! ;)
Plus sérieusement, je ne vois pas du tout ce que tu veux dire.
Tu peux développer?

Citation:

---

Envoyé par Joel F

On s'en moque. siu ton tabelau fait 10*10 et que tu sasi ça a l acompil, tu peut dérouler la boucle externe entièrement, tu auras pratiquement toujours du gain.

---

Arrêtez moi si je me trompe, mais normalement si il est bien réglé, le compilo le fais a notre place

Citation:

---

Envoyé par Christuff

Arrêtez moi si je me trompe, mais normalement si il est bien réglé, le compilo le fais a notre place

---

si ets seulement la phase de propagation de constante permet au compilo de connaitre les bornes des boucles.

Citation:

---

Envoyé par Aleph69

sans remettre en cause ce que tu dis, je ne comprends pas bien ce que tu écris Joel.

---

J'ecris très mal il faut dire.

Ce que je veut dire en parlant du cache c'est que la taille n'est qu'un des facteurs importants. Il y a enormément de facteur basé sur le schéma d'accés temporel au donnée qui en fait sont bien plus important.

J'ai pas le papier sous la main mais j'uplaoderais ça sous peu.

Bonjour,

Citation:

---

Il y a enormément de facteur basé sur le schéma d'accés temporel au donnée qui en fait sont bien plus important.

---

Oui, je crois que c'est introduit dans le bouquin de Hennessy (en tous cas dans une ancienne version au moins).

N'oublie pas d'uploader ton papier, ça m'intéresse!