serge_sans_paille a écrit 257 commentaires

Salut,
super rretour! Pas plus tard qu'hier je me décidais à écrire la version OpenMP d'un matrix mutliply en pythran, que je vous livre ci-dessous:

#pythran export matrix_multiply(float list list, float list list)
def zero(n,m): return [[0 for row in xrange(n)] for col in xrange(m)]
def matrix_multiply(m0, m1):
    new_matrix = zero(len(m0),len(m1[0]))
    "omp parallel for private(i,j,k)"
    for i in xrange(len(m0)):
        for j in xrange(len(m1[0])):
            for k in xrange(len(m1)):
                new_matrix[i][j] += m0[i][k]*m1[k][j]
    return new_matrix

Pythran ne fait pas de privatisation de variable, elles sont toutes déclarées à l'entrée de la fonction (comme en FORTRAN :p), donc mettre le mode defauls(none) me semble tout particulièrement indiqué !

1000 fois merci :-)

[print(x) for x in ["merci"]*1000]

Ça veut dire que toute les variables référencée dans la boucle doivent avoir une visibilité spécifiée dans la directive, sinon erreur de compilation.

int i1,i2,i3,...;
...
#pragma omp parallel for
for (i1 = 0; i1 < N1; ++i1)
 for (i2 = 0; i2 < N2; ++i2)
   for (i3 = 0; i3 < N3; ++i3)
     code(i1,i2,i3);

Le problème ici est que le mode par défaut est shared, sauf pour l'indice de la boucle sur laquelle porte la directive et donc les variables i2 et i3 seront mises en mémoire partagées et là c'est le drame.

Quand on fait du C++/C99 un peu propre, on préfère la forme

#pragma omp parallel for
for (int i1 = 0; i1 < N1; ++i1)
  for (int i2 = 0; i2 < N2; ++i2)
    for (int i3 = 0; i3 < N3; ++i3)
      code(i1,i2,i3);

qui ne pose pas de soucis car les variables locales sont considérées comme private

La lecture de http://en.wikipedia.org/wiki/OpenMP#Data_sharing_attribute_clauses est un bon point de départ pour comprendre ça.

C'est un détournement assez amusant et intéressant du with ça. J'aime !

C'est peut être ce que tu ne veux pas dans la mesure où ça pollue l'interprétation du code ?

Plus ou moins. ça force à ajouter un import pythran.Pragma dans le module, et ce n'est pas trop dans l'esprit…

Sinon on pourrait raffiner ta proposition et avoir un manager pour parallel ou pour task et ainsi de suite. Mais ça commence à être verbeux.

J'y avais pensé, mais sans le @, donc un truc du genre

def saxpy(x,y,a):
    #omp parallel for private(i,b)
    for i in range(len(x)):
        b = a* x[i] # laid mais utile pour l'exemple
        y[i]+= b

Le problème c'est que les commentaires sont jetés par le parseur python (du moins celui fourni dans le module standard: ast), ce qui n'est pas le cas des chaîne de caractère.

Dans la famille hack sympathique il suffirait d'un bon vieux

sed -r -e 's/^(\s*)#omp( .*)$/\1"omp\2"/g' 

pour s'en sortir, ou l'équivalent en utilisant re.sub. Mais c'est pas très robuste.

pour les fins de lignes, j'ai l'habitude de formater mon post dans un vim externe, qui m'aligne tout (enfin pas tout justement…) à +/- 80 caractère par colonne. Et ce billet montre que je me suis lourdé royal :-)

Pour les débuts/fins de bloc, c'est effectivement la convention adoptée par OpenMP pour le Fortran, c'est très roleplay de faire comme ça en effet.

En tout cas c'est dans le tutoriel officiel.

Comme quoi l'apprentissage par induction dont je suis friand a ses limites :-).

Oui, j'ai vu cet idiome de nombreuses fois. Ça ressemble furieusement à ça http://en.wikipedia.org/wiki/Option_type.

On dirait que les softeux ont toujours autant de mal avec le hardware.

Ça c'est sûr :-) trois années passées à m'y frotter (le moins possible) n'ont malheureusement pas apportées de grands changements :-(

le nombre de transistors d'une puce double tous les 18 mois/ 2 ans pour le même prix.

Il me semblait que c'était à surface constante, d'où problème de « mur de la chaleur » etc. Pareillement les moulti-cœurs ne changent rien au problème d'intégration.

C'est surtout une histoire de cout de développement qui explose.

Oui. La difficulté de programmation de l'archi n'y est pas étrangère, puisqu'il faut embaucher des développeurs spécialisés au lieu de développeurs généralistes.

Pour le moment, j'ai des compteurs de références sur chacun des conteneurs (liste / ensemble uniquement donc). Comme il n'y a pas de classes utilisateur, je ne pense pas qu'il soit possible de créer des références croisées.

Ça suffit, non ?

Dans ce cas, on peut quand même s'en sortir en déléguant l'évaluation de la condition à l'exécution, ce qui a quelques défauts (dont augmentation de la taille du code) mais pas mal d'avantages aussi.

Un cas classique pour gérer l'aliasing:

#include <stdint.h>
void foo(size_t n,   float a[n], float b[n]) {
  // aucune garantie que a et b ne se chevauchent pas partiellement ou totalement
  for(size_t i=1;i< n ; i++) { // cette boucle n'est parallèle que si a et b ne se chevauchent pas
    a[i] = 2*b[i-1];
  }

Dans ce cas un petit test dynamique permet de suppléer aux carences de l'analyse statique

void foo(size_t n,   float a[n], float b[n]) {
  if( &a[n]<=&b[0] || &b[n] <= &a[0] ) foo_parallel(n,a,b);
  else foo_sequential(n,a,b);
}

icc fait ça à fond !

Il y a déjà pymothoa qui vise à faire ça.

Deux arguments pour la génération de C++:

1. Cela simplifie grandement la génération de code, le debug etc. D'après les test faits jusqu'à présent, c'est pas dégueux niveaui perf non plus :-)

2. pythran vise à être compatible OpenMP (à faire à faire, ça devrait être prêt pour les PyconFR). Et là encore c'est plus facile à faire au niveau source qu'au niveau bytecode

Sinon lire l'excellente thèse de Serge Guelton sur les atouts de la compilation source-à-source ;-)

D'après la doc pypy tu as raison.

Tu ne peux vraiment pas présager la durée de vie de tes variables, ni comment elles vont être utilisées. Tu peux juste faire des suppositions en l'air…

Curieux, j'aurais dit tout le contraire. Prenons un exemple

def higher_frequency(l,n):
  """Assumes l contains n kind of values."""
  histo= [0]*n
  for v in l:
    histo[v]+=1
  return max(histo)

Le compilateur a toutes les informations pour décider que histo est un tableau avec une durée de vie faible, qu'il n'est jamais aliasé et que sa taille ne change pas après sa définition. Au lieu d'utiliser une classe tableau générique (implémentant un compteur de référence etc) on peut basculer sur un tableau natif.

Pythran ne le fait pas …

Oui. Contrairement à ce que le nom laisse penser d'ailleurs :-(. Mais le source est sans appel.

Je ne pense pas :-)
C'est juste que ce benchmark mettait en avant le mauvais comportement de pythran en cas de création de nombreux tableaux.

mouarf l'aut'

Bah non j'ai sorti l'huile de coude et j'ai optimisé le générateur de code, avec optim' mises dans le journal :-)

Merci!
Je viens de tester la version dans debian sid pour les deux exemples précédents et c'est pas GG

quicksort: 8.64s
matmul:2.06s

Et en regardant le code généré, c'est assez proche d'un cython sans annotations de types…

il n'y a pas de repas gratuits !

Alors deuxième partie, mais j'ai eu la flemme d'écrire le code cython

Le code d'entrée est le suivant

def zero(n,m): return [[0 for row in xrange(n)] for col in xrange(m)]
def matrix_multiply(m0, m1):
    new_matrix = zero(len(m0),len(m1[0]))
    for i in xrange(len(m0)):
        for j in xrange(len(m1[0])):
            for k in xrange(len(m1)):
                new_matrix[i][j] += m0[i][k]*m1[k][j]
    return new_matrix

Et j'utilise des list et pas de numpy.* en entrée.

python: 1.97s
pypy: 0.200s
shedskin: 0.103s
pythran: 0.06s

ce qui confirme le classement précédent

merci pour les remarques, constructives à défaut d'être encourageantes ;-)

Par acquit de conscience, j'ai lancé un petit bench (un quicksort dont le code cython est donné là et dont le code python est identique aux cdef prêts.

J'ai fait mouliné ça sur des tableaux de flottants numpy.array (sauf pour shedskin qui supporte pas) de taille 10000, à l'aide du module timeit et en prenant la médiane sur 11 runs. Tout ce qui peut être compilé est compilé en -O2.

python: 11.802s
pypy: 0.120s
shedskin: 0.096
pythran: 0.092
cython: 0.060

le classement est au final assez représentatif de ce que l'on pouvait attendre: plus on met d'effort / de contraintes plus on obtient de perfs. 0 efforts pour pypy et de sacré bonnes perfs, pas mal d'annotations avec cython et de très bonnes perfs.

/me va rejouer le même jeu sur un matrix multiply pour voir.

By Jove
Bien sûr Cython devrait être dans le haut de la liste. Et puis le côté incrémental est vraiment chouette :-)

Merci ;-)

tu peux même dire ultra moche :(

bon, j'ai pas l'impression d'avoir le droit de modifier ça…

Approuvé && corrigé !

Initialement je voulais avoir une grosse pastille à chaque section, mais je m'en suis pas sorti…

Bonne idée le _easter egg, il pourrait par exemple changer de couleur, ou grossir un peu (dur à digérer les grosses pastilles).

On pourrait mettre un fantôme sur la dernière page avec un regard qui changerait en fonction de la pastille croquée…

Bon, ce sera pas pour tout de suite non plus hein ;-)