Bonjour,

Je suis actuellement en train d'essayer de coder un jeu de la vie et il s'avère que le traitement matriciel c'est pas mon fort. Ce qui fait que même pour un tableau 100x100 la double boucle est assez violente à exécuter. C'est pourquoi je voulais savoir si python pouvait permettre un rendu GPU plutôt que CPU afin que (je pense) les calculs se font plus rapidement et par conséquent moins de bug. 

Je sais très bien qu'il est possible de passer sans doubles boucles (merci numpy) mais cela n'empêche pas ma question.

Et je sais pas s'il y'a une importance mais j'utilise pyzo comme IDE

Merci de votre aide.

L'usage du GPU ne t'apportera rien ici car, même si tu utilises un tableau pour stocker l'état et la position des cellules, tu ne fais aucun calcul matriciel pour autant.

Par ailleurs, même avec l'algorithme de base tu ne devrais pas avoir de problème pour un tableau en seulement 100x100.
Ceci étant dit, l'algorithme optimal pour le Jeu de la Vie s'appelle HashLife. L'apprendre est très formateur, mais ça nécessite d'avoir déjà de la pratique et des bonnes bases en programmation.

import os
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as img

os.chdir(r'D:\Programmes Python\Contenu')
L = img.imread('test.png')

def changeMatrice(L):
    """....."""
    n=len(L)
    Copie = np.copy(L)
    for i in range(1,n-1):
        for j in range(1,n-1):
            somme = np.sum(L[i-1:i+2,j-1:j+2,0])-L[i,j,0]
            if L[i,j,0]==1:
                if somme == 5:
                    Copie[i,j,:]=0
            else:
                if somme < 5 or somme > 6:
                    Copie[i,j,:]=1

    return(Copie)
    
L1 = np.copy(L)
for i in range(100):
    plt.imshow(L1,interpolation='none')
    L1 = changeMatrice(L1)
    plt.title(i)
    plt.pause(0.001)
    

Voilà le programme que j'utilise. Juste en import c'est une image blanche jpg avec quelques pixels noir (cellules vivantes). Mais le problème c'est que le programme à quand même des lags lors de l’exécution. Soit trop de calculs je pense. Je vais quand même aller voir le programme voir comment il est fait ça pourras toujours m'aider :D 

Le plus simple serait de passer par pycuda ou pyopencl, avec un micro code executé sur gpu. Une autre alternative c'est de passer par opengl (glumpy) au travers des shaders et d'un render to texture. Pour le coup tu auras du temps réel avec des tailles de matrice largement plus grand

Dans ton code présent, je ne voie rien qui pourrais ralentir beaucoup ton execution, à l'exeception des copy de tableau que tu fait. Tu pourrais faire un double buffering et swaper les references.

-
Edité par Gaia 25 octobre 2018 à 21:42:03

Bonjour,

Attention avec l'utilisation du GPU. Beaucoup de calcul sont plus lent justement à cause de tout ce qui se passe pour envoyer les instruction au GPU. Par exemple en machine learning. Un modèle avec que quelques petites matrices sont beaucoup beaucoup plus rapide sur CPU que GPU( c'est ton cas avec une mini matrice de 100 x 100). Je m'étais amusé à faire la comparaison de multiplications de matrices dont voici les résultats (avec pyCUDA) :

Le pic que tu vois au début est constant peu importe la taille de la matrice. Tu ne l'a plus ensuite car c'est fait dans une boucle FOR mais en réalité tu l'as pour tous. Dans mon cas, le GPU > CPU pour une multiplication de matrices de environ 3200x3200. C'est devenu encore plus simple à évaluer avec tensorflow BTW.

De plus, comme dit precedemment, tu ne profitera pas non plus du calcul matriciel comme tu dois boucler avec des boucles FOR pour le jeu de la vie.

Pour ce qui est de l'itération "for", non, c'est justement l'interets du GPU d'utiliser la grille de calcule. Et en l'occurance il n'a peut-être pas besoin de faire des chunks et de clusteriser son espace pour traiter des tailles de matrice gigantesque >65535, pour l'instant Après effectivement il y a un cout de transaction mémoire, 1 upload long (initial), puis 1 download rapide et asynchrone à chaque boucle de "vie" pour l'afficher. En plus c'est particulièrement adapter au calcule GPU puisque le code peut être rédigé sans condition ! Mais effectivement c'était un point important à relever s'il reste sûr de petites tailles de matrice.

Cela dit, je viens de voir une opération douteuse, tu réalises un "slice" L[i-1:i+2,j-1:j+2,0] pour récupérer le voisinage et faire ta somme, ce qui implique l'allocation d'un nouveau tableau pour calculer la somme des voisins à chaque itération de ton espace. Ça c'est coûteux, et puis tu doit peut-être vérifier le type de donnée que tu manipule (type de L[i,j] char/int/float,...)

-
Edité par Gaia 25 octobre 2018 à 21:52:49

Bonjour,

Gaia a écrit:

Pour ce qui est de l'itération "for", non, c'est justement l'interets du GPU d'utiliser la grille de calcule. 

-
Edité par Gaia il y a environ 18 heures

Le GPU fait très bien le calcul de matrice car il utilise tous ses coeurs pour diviser le travail et ensuite joindre les resultats (un peu comme du map-reduce). C'est en cela que sa vitesse est très interessante pour par exemple du calcul de produit de matrices. Cependant, iterer sur toute la matrice pour vérifier 1 par 1 chaque élément me semble être une mauvaise approche pour un GPU car au final tu n'as plus la bénéfice du calcul de matrice. La matrice n'est qu'un support. 

 Pour ce qui est du jeu en lui même, tu peux surement l'accelérer en mappant des sous matrices au lieu de vérifier chaque conditions. Par exemple tu map :

[[X 0 0]      [[X 0 0]

[0 0 X]    à  [0 X X] 

[0 0 0]]       [0 0 0]]

Ensuite il te reste à itérer sur chaque sous matrices de 3x3 dans ta matrice de 100x100 pour voir si ta sous matrice match avec un de tes mapping. Bon ca t'oblige a coder ca manuellement mais bon. Apres tu peux aussi faire des convolutions avec comme filtre :

[[1 1 1]

[1 0 1]

[1 1 1]

Et si le resultat de la convolution fait 2 ou 3, tu mets un 1 dans la cellule en question. Bref il y a des solutions plus rapide sans passer par le GPU à mon avis

code talk itself.

#define get(i, j, size) grid[((i+size)%size)*size + (j+size)%size]

__global__ void isAlive(unsigned char *buff,unsigned char *grid,int size)
{
  int i, j;
  i = blockIdx.x*blockDim.x+threadIdx.x;
  j = blockIdx.y*blockDim.y+threadIdx.y;
  int current_cell = grid[i*size+j];
  int neighbors = 0;
  
  neighbors += get(i+1, j ,size);
  neighbors += get(i+1, j+1 ,size);
  neighbors += get(i, j+1,size);
  
  neighbors += get(i-1, j,size);
  neighbors += get(i-1, j+1,size);
  neighbors += get(i-1, j-1%size,size);
  
  neighbors += get(i, j-1,size);
  neighbors += get(i+1, j-1,size);
  
  buff[i*size+j] = (current_cell && (neighbors == 3 || neighbors == 2)) ||
                   (!current_cell && neighbors == 3);
}

// compute one steep
isAlive<<<1, dim3(size,size,1)>>>(buff, grid, size);
unsigned char*tmp = buff;
buff = grid;
grid = tmp;

Comme je disais,
Besoin d'une boucle pour itéré 1 à 1 ? non
Besoin de condition ? non
Tien c'est justement et précisément une opération matricielle

Le jeu de la vie est précisément, le meilleur cas de figure pour une utilisation GPU, puisque le code est totalement prédictible, sans condition, sans synchro, chaque coeur calcule a la même vitesse chaque exécution local, donc la répartition de la charge de calcul ce fait automatiquement. Et encore il y a moyen de l'améliorer très large par l'utilisation d'un bitset et de cluster.

http://www.marekfiser.com/Projects/Conways-Game-of-Life-on-GPU-using-CUDA/2-Basic-implementation#2-6-CPU-vs-GPU

Je ne rentre pas trop dans les détails, il aura toute l'occasion de trouver des améliorations possibles.

-
Edité par Gaia 26 octobre 2018 à 22:51:29

Wow ca me donne envie de tester maintenant Mais tout de même, on parle de cas beaucoup plus grand ici (je cite):

"CPU is very stable at 50 millions of evaluated cells per second", la on parle de 10 000 cellules "uniquement". Leur benchmark va jusqu'a 500 milions cells XD

Quand j'aurais le temps, je vais voir pour faire essayer de générer une video de 1920x1080@60fps (124millions cells/seconds) ou chaque pixel est une cell du jeu de la vie Nouveau projet dans ma TODO list XD

EDIT : Je viens de comparer le meme algo en version CPU mono-thread et GPU. Pour eviter l'impact du rendu sur le temps de calcul j'ai utilisé OPENGL en générant une texture de la matrice et le résultat est impressionnant. 

CPU :

384 x 216 => 2 fps

480 x 270 => 1.2 fps

1920 x 1080 => 0.07 fps

GPU (block de 32x32) :

384 x 216 => 70/75 fps

480 x 270 => 70 fps

1920 x 1080 => 60/65 fps

Mea Culpa, je n'aurais pas pensé le GPU utile pour ce genre de taches

-
Edité par coni63 27 octobre 2018 à 16:15:21