Dev Faq
8
votes

Programme Java multithreaded pour le jeu de la vie de Conway à la frontière

J'apprends une programmation simultanée en Java et j'écris une simulation pour le jeu de la vie.

Voici ce que je pense:

  • Utilisez INT [] [] pour stocker les états des cellules
  • partitionner l'int [] [] dans les segments T et utiliser les threads de travailleur T
  • Les threads T lireont à partir de leur segment, calculent de nouvelles valeurs pour toutes les cellules de leur segment et mettent à jour les cellules.
  • Une fois qu'ils ont fini de calcul, ils attendent à une barrière pour les autres travailleurs de terminer
  • Lorsque la barrière est franchie, le thread principal mettra à jour l'interface utilisateur.
  • Les travailleurs procèdent à calculer l'état suivant.

    Maintenant, il y aura de la conflit aux frontières communes des segments. Si un fil écrit l'état d'une cellule à bordure avant que son voisin ait lu la valeur précédente, le calcul du voisin va être faux.

    Quelles sont mes options?

    • Utilisez appelable à la place des fils runnable et demandez aux threads de travailleur de renvoyer la nouvelle valeur (au lieu de mettre à jour les segments eux-mêmes). Le thread principal peut mettre à jour la matrice après la traversée de la barrière. Cette option consiste à copier les résultats renvoyés par les threads de travailleur dans la matrice.
    • Utilisez deux barrières. Les travailleurs firent une copie des cellules frontalières des segments de leurs voisins et attendent à la première barrière. Une fois que cette barrière est passée, ils procèdent à calculer les prochains États et à mettre à jour les segments en place. Ensuite, ils attendent à la 2e barrière. Le fil principal met à jour l'UI.

      Ma question est là, y a-t-il une autre façon de faire face à la conflit dans les cellules frontalières qui n'implique pas de copier des données ou est plus efficace que les deux options ci-dessus? Peut utiliser ReaderWraterlock, une variable volatil ou un autre mécanisme de synchronisation?

      Mise à jour: Jusqu'à présent, le Une double solution tampon de Peter est la plus propre. Mais j'ai une question. Étant donné que les deux tableaux sont des données partagées et que nous n'utilisons aucune synchronisation (accès synchronisé ou variable volatile), ne créera-t-il pas de problème de visibilité ? Les processeurs multiples pourraient-elles mettre en cache des valeurs de matrice et mettre à jour seulement une partie de la matrice avec chaque itération? Ensuite, les threads obtiendront des valeurs obsolètes pour les cellules frontalières. Est-ce possible? Sinon, pourquoi. Si oui, comment puis-je le résoudre? Il semble Déclaration de deux tableaux volatils ne rendra pas leurs éléments individuels volatils .

4 commentaires

quelque chose à considérer consiste à utiliser atomicint au lieu d'int

Avantage? Cela ne sera-t-il pas trop synchronisé?

Pourquoi avez-vous besoin d'utiliser INT, ne serait-il pas plus logique et efficace de stocker à l'aide de booléens?

Je ne. Dans mon code actuel, j'utilise Enum [] [].

5 Réponses :

1
votes

Cela ne répond pas à votre question actuelle, mais ma recommandation serait votre première option ... avoir renvoyé les nouvelles valeurs plutôt que de les mettre à jour les threads de travailleur. Je prendrais une étape plus loin et que "Aggregator" combine les résultats des threads de travailleur dans un nouveau tableau d'état du tableau, puis jetez le premier. Mon raisonnement est qu'il améliorera la lisibilité globale de la logique, car il n'y aura que peu de "interactions mondiales", vous devez vous inquiéter.

Cela étant dit, je suis un peu biaisé parce que je préfère programmer de manière fonctionnelle sauf quand il y a une raison forte de ne pas.

0 commentaires
1
votes

Je voudrais essayer l'approche suivante:

  • Demandez aux travailleurs effectuer les calculs, mais n'écrivez que les valeurs des cellules internes.
  • pour les cellules frontalières, stockez les résultats.
  • Lorsque les calculs sont terminés, attendez une barrière.
  • Lorsque tous les travailleurs sont à la première barrière, libèrent ensuite et permettent à chacun d'écrire les cellules frontalières.
  • attendez une deuxième barrière pendant que l'interface utilisateur est mises à jour

    Stockage requis pour un NXM TILE est 2 * (N + M - 1) , de manière générale des tuiles plus grandes (8x8 ou plus) nécessitent une mémoire moindre de manière proportionnelle pour la mise en cache valeurs.

0 commentaires
5
votes

Je suggère d'avoir 2 matrices d'int [] []. Appelons-les a et B. A contenir les valeurs de toutes les "ticks" impairs et B contiendront les tiques numérotées.

Initialiser A à quel que soit votre état initial ressemble. Ensuite, laissez vos discussions pour calculer l'état suivant de chaque cellule et placer les résultats dans la cellule correspondante en B. Une fois que tous vos threads sont terminés, vous avez votre nouvel état dans B. Maintenant, utilisez B pour calculer l'état suivant de chaque cellule et stocker les résultats dans A. À une heure donnée, un tableau sera en lecture seule et l'autre. écrire seulement, donc il n'y aura jamais de contention.

Avantages:

  • pas de copie de données par rapport à ce que vous faites maintenant. Une seule écrite se produit par cellule.
  • NON ayant à vous soucier des caisses EDGE / Coin, car l'algorithme est simple.
  • Pas d'allocation de mémoire en cours. Il suffit d'attribuer les deux tableaux lorsque vous commencez.

    Inconvénients:

    • Vous devez attribuer deux fois plus de mémoire.
1 commentaires

Ça semble bon. Mais j'ai une question sur la visibilité des données partagées. Voir la mise à jour.

0
votes

Je viens de sotter sur java.util.concurrent.exchanger . Il agit comme un point de change. Je peux probablement l'utiliser pour échanger des listes d'états cellulaires entre des threads adjacents. Ce serait mieux que la barrière car je dois me synchroniser uniquement entre les travailleurs adjacents.

0 commentaires
0
votes

Pour répondre à votre mise à jour sur le problème de la mise en cache avec double tampon, ce n'est pas un problème. Les CPU ont un cache cohérent et ils savent que les données ont été modifiées dans un autre cache de la CPU.

3 commentaires

D'accord. Mais la visibilité est toujours une question due au modèle de mémoire Java. Lorsque le lien dans la mise à jour montre, déclarant que les références de matrices volatile et écrasent les références s'occuperont de cela. Cela signifie également que les processeurs ne peuvent pas mettre en cache les valeurs (ou jeter une fois que les références volatiles sont modifiées).

Bien lire ce lien, vous n'avez besoin que de la référence de la matrice pour être volatile, et non les données de la matrice. Vous pouvez simplement avoir un frontbuffer et une référence de retombeur, et de les échanger chaque itération. De cette façon, le contenu des tampons peut toujours passer par le cache de la CPU, les articles ne sont pas volatils, vous permettez donc d'utiliser une bonne utilisation des registres de la CPU, et vous n'avez aucune question de travail sur les anciennes données.

En réalité, l'utilisation d'une référence de matrice volatile pourrait vous ralentir en regardant l'adresse de la mémoire de la mémoire chaque utilisation, au lieu de le garder dans un registre de la CPU. Au début de chaque itération, vous pouvez copier les références volatiles en références temporaires non volatile, car vous ne les modifierez de toute façon pas pendant une itération.

Articles qui pourrait vous intéresser :

Comment envoyer une liste vide à la clause IN
Code de réponse 403 inattendu lors de la récupération des données des API
Impossible de trouver la classe UnityPlayerActivity dans com.unity3d.player
Comment définir un tableau dans jsonobject