2010-12-14 4 views
1

J'essaye de calculer le nombre de transitions qui seraient faites dans une course de GED de Conway pour une matrice pxq pour n itérations. Par exemple, étant donné 1 itération avec l'état initial étant 1 clignotant (comme ci-dessous). il y aurait 5 transitions (2 naissances, 1 survie, 2 décès de sous-population). Je l'ai déjà travaillé, mais je voudrais convertir cette logique pour courir en utilisant CUDA. Voici ce que je veux porter à CUDA.noyau de cuda pour le jeu de la vie de conway

alt text Code:

static void gol() // call this iterations x's 
    { 
     int[] tempGrid = new int[rows * cols]; // grid holds init conditions 
     for (int i = 0; i < rows; i++) 
     { 
      for (int j = 0; j < cols; j++) 
      { 
       tempGrid[i * cols + j] = grid[i * cols + j]; 
      } 
     } 

     for (int i = 0; i < rows; i++) 
     { 
      for (int j = 0; j < cols; j++) 
      { 
       int numNeighbors = neighbors(i, j); // finds # of neighbors 

       if (grid[i * cols + j] == 1 && numNeighbors > 3) 
       { 
        tempGrid[i * cols + j] = 0; 
        overcrowding++; 
       } 
       else if (grid[i * cols + j] == 1 && numNeighbors < 2) 
       { 
        tempGrid[i * cols + j] = 0; 
        underpopulation++; 
       } 
       else if (grid[i * cols + j] == 1 && numNeighbors > 1) 
       { 
        tempGrid[i * cols + j] = 1; 
        survival++; 
       } 
       else if (grid[i * cols + j] == 0 && numNeighbors == 3) 
       { 
        tempGrid[i * cols + j] = 1; 
        birth++; 
       } 
      } 
     } 

     grid = tempGrid; 
    } 
+0

Sur quoi exactement voulez-vous de l'aide - des idées sur la parallélisation, le stockage, la programmation CUDA, etc. .? – Rup

+0

Désolé, comment dois-je aborder le parallélisme? – dnbwise

Répondre

3

Votre ralentissement principal va être principal accès à la mémoire. Donc, je suggère que vous choisissez une taille de bloc de threads en fonction du matériel dont vous disposez. 256 (16x16) est un bon choix pour la compatibilité inter-matériel. Chacun de ces blocs va calculer les résultats pour une section légèrement plus petite du tableau - si vous avez utilisé 16x16, ils calculeront les résultats pour une section 14x14 du tableau, puisqu'il y a une bordure d'un élément. (La raison d'utiliser un bloc 16x16 pour calculer un bloc 14x14 plutôt qu'un bloc 16x16 est pour la coalescence en lecture de mémoire.)

Divisez la carte en blocs (disons) 14x14; qui est votre grille (organisé comme bon vous semble, mais probablement quelque chose comme board_width/14, board_height/14.

Dans les noyaux, ont chaque thread charger son élément dans la mémoire partagée. Ensuite syncthreads. Demandez ensuite les éléments du milieu de 14x14 calculer le nouveau valeur (en utilisant les valeurs stockées dans la mémoire partagée) et réécrivez-la dans la mémoire globale.L'utilisation de la mémoire partagée permet de minimiser les lectures et les écritures globales.C'est également la raison pour laquelle la taille de votre bloc de threads est la plus grande possible. les coins sont des "gaspillages" d'accès à la mémoire globale, puisque les valeurs extraites ne sont utilisées que 1 ou 3 fois, et non 9 fois

0

Voici une façon que vous pouvez procéder:

  1. Chaque thread fait le calcul pour 1 élément de la grille
  2. Chaque thread charge d'abord jusqu'à un élément de la grille principale dans la mémoire partagée
  3. Les fils sur le bord du bloc de fil doivent également charger l'élém nts
  4. Chaque thread peut alors faire leur calcul de survie en fonction du contenu de la mémoire partagée
  5. Chaque thread écrit ensuite leur résultat à la mémoire principale
Questions connexes