Prédire les temps d'exécution pour l'algèbre linéaire dense

9

Je voudrais prédire les temps d'exécution des opérations d'algèbre linéaire dense sur une architecture spécifique en utilisant une bibliothèque spécifique. Je voudrais apprendre un modèle qui se rapproche de la fonction

Fop::tailles d'entrée runtime

pour des opérations telles que multiplication matricielle, ajout par élément, résolution triangulaire, etc.

Je soupçonne que ces temps d'exécution sont généralement prévisibles en raison de la régularité des opérations une fois que vous avez dépassé les tailles de problème qui tiennent confortablement dans le cache.

Des questions:

  1. Cette hypothèse est-elle réaliste? La fonction d'exécution est-elle susceptible d'être presque déterministe?
  2. Puis-je supposer que cette fonction sera polynomiale dans les tailles des entrées? (c'est-à-dire que je m'attends à ce que la matrice dense se multiplie pour ressembler à pour et certain coefficient scalaire)αn×k×mUNEnk×Bkmα
  3. Y a-t-il un travail préexistant quelque part?
  4. Mon plan actuel est de faire une régression des moindres carrés avec un régularisateur . D'autres suggestions?L1

Edit: pour être clair, je recherche des temps d'exécution, pas des FLOP ou toute autre mesure de performance courante. Je suis prêt à me limiter à une architecture particulière.

MRocklin
la source

Réponses:

10

J'ai récemment travaillé exactement sur ce sujet. Vous pouvez consulter notre article: http://arxiv.org/abs/1209.2364 .

Pourquoi êtes-vous intéressé par la prédiction d'exécution des routines d'algèbre linéaire? Avez-vous l'intention d'utiliser le modèle dans un certain but?

Elmar Peise
la source
Merci pour le lien. Je regarderai. Cela m'intéresse car je soupçonne la même raison que vous. Sélection et planification automatisées d'algorithmes pour les expressions matricielles. De nombreux problèmes autrement impossibles devraient être possibles dans ce domaine très régulier et prévisible.
MRocklin
6

Il y a beaucoup de travaux préexistants. La plupart des développeurs de bibliothèques d'algèbre linéaire publient des résultats de performances en termes de performances en virgule flottante qui peuvent être converties en temps d'exécution.

La recherche de «performances DGEMM» par exemple, donne les résultats suivants: http://math-atlas.sourceforge.net/timing/3_5_10/index.html .

En règle générale, vous pouvez vous attendre à ce que les réponses ne soient pas fluides. Il y aura des sauts ou des pics à proximité de certaines tailles de problèmes (qui concernent les tailles de cache). Vous devez également vous attendre à des plateaux de taux et, par conséquent, à des régions linéaires pour un large éventail de tailles de problèmes. Je ne m'attends pas à ce que les ajustements polynomiaux soient très utiles.

Étant donné un vaste effort d'analyse comparative, il pourrait être plus facile de tabuler les résultats et d'interpoler si nécessaire. Quel est ton but?

Bill Barth
la source
1
DGEMMn3
La conversion des flops en runtimes est, selon mon expérience, difficile. Je ne me soucie vraiment que des temps d'exécution dans mon cas. Je teste la faisabilité d'une planification statique.
MRocklin
D'après mon expérience, les pics / plateaux ne se produisent que pour les petits problèmes. Une fois que vous sortez du cache, les choses se passent assez bien. Je suis d'accord que l'ajout de fonctions par morceaux améliorerait probablement l'ajustement.
MRocklin