Les unités de traitement parallèle massives d'aujourd'hui sont-elles capables d'exécuter efficacement les automates cellulaires?

Je me demande si les unités de calcul massivement parallèles fournies dans les cartes graphiques de nos jours (celle qui est programmable dans OpenCL , par exemple) sont assez bonnes pour simuler efficacement les automates cellulaires 1D (ou peut-être les automates cellulaires 2D?).

Si nous choisissons la grille finie qui rentrerait dans la mémoire de la puce, pouvons-nous nous attendre à ce qu'une transition d'un automate cellulaire définie sur cette grille soit calculée en temps (quasi) constant?

Je suppose que les automates cellulaires 2D nécessiteraient plus de bande passante pour la communication entre les différentes parties des puces que les automates 1D.

Je serais également intéressé par la même question dans le cas de la programmation FPGA ou des puces personnalisées.

Excellente question. Je crois que la réponse est oui.

Faire évoluer un automate cellulaire équivaut essentiellement à effectuer un calcul au pochoir. Sur une grille 1D, 2D ou 3D, les valeurs successives des points (ou cellules) sont calculées en fonction de la dernière valeur du voisinage du point. Dans une CA 1D simple, ce voisinage pourrait être la cellule et les deux cellules à gauche et à droite. Il existe de nombreux exemples de calculs au pochoir effectués sur des GPU; La suite de référence SHOC d'ORNL pour OpenCL / CUDA contient un exemple de gabarit 2D, par exemple.

L'idée de base est que chaque thread obtienne une copie locale du voisinage pour plusieurs points, puis calcule les valeurs suivantes pour les points déterminés par ce voisinage. En utilisant de manière appropriée la hiérarchie de la mémoire dans, par exemple, CUDA (registres, partagés, constants, texture et mémoires globales) et le modèle de traitement SIMT (par exemple, en calculant correctement la fonction de transition sans introduire de divergence de chaîne excessive), de bonnes performances peuvent être obtenues.

Cette réponse serait bien meilleure si je devais donner un exemple, mais je suis trop occupé pour écrire un code en ce moment ... Mais en théorie, je pense qu'il devrait être possible de simuler efficacement les autorités de certification sur les GPU en les modélisant après le pochoir calculs. Beaucoup de considérations entrent cependant dans l'écriture d'un bon calcul au pochoir pour les GPU.

Quoi que vous fassiez, le calcul de l'état suivant pour un automate cellulaire demande autant de calculs qu'il y a de cellules dans l'automate. Ainsi, pour obtenir un temps constant, vous avez besoin d'autant de cœur de calcul qu'il y a de cellules.

Le nombre de ceux-ci dans le GPU est actuellement au plus de quelques milliers, tandis que le calcul de l'état suivant est si simple que je m'attends à ce que le résultat soit lié à IO, c'est-à-dire que vous pouvez obtenir une très bonne approximation du temps nécessaire en considérant simplement le le déplacement des données est nécessaire (et si ce n'est pas une bonne approximation, soit l'implémentation a une inefficacité, soit l'architecture n'est pas appropriée, mais ce serait très surprenant).

Pour FPGA, la question est plus difficile et dépendra probablement du mélange de mémoire et d'unités de calcul disponibles. Si je ne suis pas trop loin, vous n'aurez pas assez de mémoire pour occuper toutes les unités et si vous comptez sur la mémoire externe, vous êtes au même siège que le GPU, la bande passante mémoire sera le facteur limitant et je ne le ferais pas soyez surpris si la conclusion est qu'il n'y a aucun avantage sur le GPU. (Notez que bien que j'ai travaillé avec FPGA, c'était il y a des années, il peut maintenant y avoir des modèles FPGA avec un bon mélange).

ASIC offre plus de flexibilité. Vous pouvez facilement avoir une implémentation de type systolique (mais avec un flux de données bidirectionnel, une partie systolique est généralement limitée à un flux de données unidirectionnel), chaque cellule physique est une logique: un bit de mémoire et la logique nécessaire pour calculer son état suivant et est disposée de sorte que son voisin physique soit logique. Vous êtes évidemment dans le domaine du temps constant. Selon les macros dures que vous avez, il vaut peut-être mieux être un peu moins évident et avoir des cellules physiques qui en regroupent plusieurs logiques. L'objectif est de maximiser ce qui se fait dans une puce, c'est-à-dire de minimiser la communication avec l'extérieur de la puce dès que vos besoins de communication sont proportionnels au nombre de cellules, vous aurez une bande passante limitée. Oui, cela signifie que si vous avez besoin de regarder toutes les cellules pour chaque étape, vous n'êtes probablement pas beaucoup mieux qu'avec le GPU. (Une personnalisation complète ne fournirait qu'une meilleure intégration, c'est-à-dire plus de cellules par puce).

Résumé: - si vous voulez regarder tous les états intermédiaires, le GPU est l'approche la plus efficace - si vous n'en avez pas, vous avez besoin du volume pour justifier un ASIC pour avoir quelque chose de mieux, le FPGA n'offrira probablement pas assez d'avantages s'il en avoir.

Je me demande si les unités de calcul massivement parallèles fournies dans les cartes graphiques de nos jours sont assez bonnes pour simuler efficacement les automates cellulaires 1D (ou peut-être les automates cellulaires 2D?).

étant très général, oui l'informatique GPU est la meilleure alternative dans le matériel standard disponible pour tout le monde.

Plus en détail; en théorie, sous le modèle PRAM, le coût par pas de temps est bien , vous le savez déjà. Cependant, le GPU diffère un peu de la PRAM car les accès mémoire coûtent plus cher et sont divisés en différentes hiérarchies (il faut considérer le modèle PMH pour une analyse théorique plus fine). De plus, les threads fonctionnent en groupe ou en chaîne , ce sont des calculs au pas-à-pas qui progressent de manière SIMD. Le modèle de programmation du GPU fonctionne avec le concept de grille (CUDA) ou espace de travail$O(1)$(OpenCL) qui est pratiquement une mise en correspondance 1-à-1 avec l'espace de calcul des automates cellulaires. Il s'agit de la fonctionnalité clé pour identifier et réaliser que les GPU sont compatibles avec l'AC. Détails techniques: Si la divergence de distorsion est traitée correctement (en remplaçant les conditionnelles if-else par des expressions mathématiques fermées), les accès mémoire sont fusionnés et ( nombre de cellules et nombre de processeurs), alors on pourrait dire que le calcul la complexité est en quelque sorte .$n \le P$$n$$P$$O(1)$

du côté FPGA et ASIC, je sais qu'il y a des recherches sur la construction d'une CA physique comme une grille de portes logiques avec des états, tous connectés par leurs voisins; c'est-à-dire des tableaux systoliques . L'idée serait de ne plus utiliser de mémoire globale mais plutôt de s'appuyer sur les états de chaque nœud de la grille. Une machine de ce type serait révolutionnaire puisque nous pourrions alors arrêter de parler d'un ordinateur simulant une CA et commencer à parler d'une CA fonctionnant comme un ordinateur (certaines CA sont en cours de réalisation).