Intégration du calcul sur GPU dans la plate-forme desimulation multi-agent générique TurtleKit 3

Fabien Michelfmichel@lirmm.fr

Laboratoire d’Informatique, de Microélectronique, et de Robotique MontpellierUniversité Montpellier II - CNRS

161 rue Ada, Montpellier Cedex 2, France

RésuméLa simulation multi-agent de systèmes com-plexes peut nécessiter de considérer un grandnombre d’entités, ce qui pose des problèmes deperformance et de passage à l’échelle. Dans cecadre, la programmation sur carte graphique(General-Purpose Computing on Graphics Pro-cessing Units GPGPU) est une solution at-trayante : elle permet des gains de perfor-mances très conséquents sur des ordinateurspersonnels. Le GPGPU nécessite cependant uneprogrammation extrêmement spécifique et cettespécificité limite à la fois son accessibilité et lapossibilité de réutiliser les développements quisont réalisés par différents acteurs. Nous pré-sentons ici l’approche que nous avons utiliséepour intégrer du calcul sur GPU dans la plate-forme TurtleKit. L’objectif de cette approche estde conserver l’accessibilité de la plate-forme,en termes de simplicité de programmation, touten tirant parti des avantages offerts par leGPGPU. Nous montrons ensuite que cette ap-proche peut être généralisée sous la forme d’unprincipe de conception de SMA spécifiquementdédié au contexte GPGPU.Mots-clés : Calcul haute performance, GPGPU,simulation multi-agent

AbstractSimulating complex systems may require tohandle a huge number of entities, raising sca-lability issues. In this respect, GPGPU is a re-levant approach. However, GPU programmingis a very specific approach that limits both ac-cessibility and re-usability of developed frame-works. We here present our approach for inte-grating GPU in TurtleKit, a multi-agent basedsimulation platform. Especially, we show howwe keep the programming accessibility whilegaining advantages of the GPU power. The pa-per also presents how this approach could begeneralized and proposes a MABS design gui-deline dedicated to the GPU context.Keywords: HPC, GPGPU, MABS

1 Introduction

Parce qu’ils sont parfois composés d’un trèsgrand nombre d’entités en interaction, étudierles propriétés des systèmes complexes à l’aidede simulations multi-agents [8] peut nécessiterbeaucoup de puissance de calcul. De fait, lesperformances d’exécution représentent souventun obstacle qui limite fortement le cadre danslequel un modèle peut être étudié, notammentce qui concerne le nombre d’entités et la taillede leur environnement.

Parallèlement, dans le cadre du calcul haute per-formance, la programmation sur carte graphique(General-Purpose Computing on Graphics Pro-cessing Units GPGPU) possède une place à partcar elle permet d’obtenir des gains de perfor-mances considérables pour un coût financier trèsfaible [3]. La majorité des cartes graphiques 3Dactuelles sont équipées de capacités GPGPU.

Cependant la programmation sur GPU n’est paschose aisée car elle repose sur une architecturematérielle spécifique qui définit un contexte deprogrammation très particulier. Ce contexte ar-chitectural nécessite notamment de suivre lesprincipes de la programmation par traitement deflot de données (stream processing paradigm 1)[10]. En particulier, il n’est pas possible d’adop-ter une démarche orientée objet classique. Defait, les modèles de simulation multi-agent cou-ramment utilisés, parce qu’ils reposent sur desimplémentations orientées objet, ne peuvent êtreutilisés sur une architecture GPU sans un effortde traduction conséquent et non trivial. Un mo-dèle multi-agent classique doit en effet être re-pensé intégralement pour pouvoir être exécutésur GPU, ce qui nécessite des connaissancesparticulièrement pointues [6].

Ainsi, malgré l’existence de travaux démon-trant les possibilités de gains offertes par la

1. Étant donné un flot de données, une série d’opérations (des fonc-tions kernel) est appliquée à chaque élément du flot.

programmation sur GPU (jusqu’à des centainesde fois plus rapide qu’avec des plates-formesclassiques [6]), les spécificités de cette dernièreposent de nombreux problèmes qui limitent for-tement l’accessibilité et la réutilisabilité des al-gorithmes et des implémentations développésdans différents contextes. Il est donc compré-hensible que peu de travaux soient enclins à in-vestir du temps dans l’utilisation de cette tech-nologie car la pérennité du code produit est diffi-cile à obtenir. La programmation sur GPU n’estainsi pas encore très répandue dans la com-munauté et pour l’instant les travaux mêlantGPU et simulation multi-agent sont majoritai-rement liés à des expérimentations très spéci-fiques effectuées dans des contextes ponctuels,ce qui ne permet pas leur réutilisation. Ainsiaucune plate-forme générique, notamment Net-Logo [13] et RePast [9], n’intègre aujourd’huide GPGPU.

Nous décrivons dans cet article comment nousavons réalisé l’intégration de calcul GPU dansTurtleKit, une plate-forme de simulation multi-agent générique [7]. Dans ce travail, nous avonsdeux objectifs. Premièrement, il s’agit d’obtenirdes gains de performances grâce au GPU, ceciafin d’être capable de réaliser des simulationslarges échelle sur TurtleKit, c’est-à-dire avec ungrand nombre d’agents et des environnementsde grande taille. Deuxièmement, pour éviter lesécueils que nous avons cités, il s’agit de conser-ver l’accessibilité et la facilité de réutilisationde la plate-forme, et plus particulièrement soninterface de programmation orientée objet.

La section 2 présente des travaux qui utilisent laprogrammation GPU pour développer des simu-lations multi-agents et identifient leurs limitespar rapport à nos objectifs. La section 3 pré-sente TurtleKit et le modèle de simulation multi-agent que nous avons utilisé pour tester l’in-tégration de modules GPU dans la future ver-sion 3 de cette plate-forme. La section 4 dé-crit comment nous avons conçu un premier mo-dule GPU en traduisant deux dynamiques en-vironnementales : la diffusion et l’évaporationde phéromones digitales. La section 5 présenteun second module GPU obtenu en transformantcertains calculs réalisés par les agents en dy-namiques environnementales calculées par leGPU. La section 6 présente une généralisationde notre approche et propose le principe de délé-gation GPU des perceptions agents. La section7 conclut l’article et discute des perspectives quilui sont associées.

2 GPGPU et simulation multi-agent

Grâce aux centaines de cœurs aujourd’hui dis-ponibles sur les cartes graphiques, la program-mation GPU permet de réaliser un très grandnombre de calculs similaires en parallèle. Cettecaractéristique est particulièrement intéressantelorsqu’on considère les systèmes complexesmodélisés à l’aide du paradigme multi-agent.Dans de tels systèmes, des calculs similairessont souvent réalisés des millions, voire des mil-liards de fois au cours d’une même simulation.Les modèles multi-agents ont donc un fort po-tentiel en termes de gains de performances. Ilexiste ainsi de nombreux travaux qui décriventdes simulations multi-agents utilisant le GPUavec succès dans différents domaines d’applica-tion tels que la simulation de foule large échelle(e.g. [4]), la biologie (e.g. [5]) ou encore la si-mulation de mouvements collectifs complexescomme le flocking (e.g. [12]).

Dans [11], des gains de performances impres-sionnants sont obtenus sur le logiciel FLAME(cellular level agent-based simulation frame-work) grâce au GPU. En particulier, ceux-cis’avèrent même plus importants qu’avec l’uti-lisation d’un cluster de CPU. Comme le sou-lignent les auteurs, de tels gains de perfor-mances sont extrêmement appréciables car ilsfacilitent le développement rapide de modèlescomplexes. Notamment, cela permet une visua-lisation en temps réel des dynamiques d’un mo-dèle, ce qui facilite l’interaction que l’utilisateurpeut avoir avec ce dernier, permettant ainsi unecompréhension accrue de son fonctionnement.

Pour obtenir ces résultats, le modèle multi-agentFLAME a été entièrement traduit en code GPU,soulevant ainsi le problème de l’accessibilité dulogiciel. Pour atténuer ce problème et ne pasobliger l’utilisateur à avoir des connaissancesen programmation GPU, les auteurs proposentun formalisme basé sur XML qui permet despécifier le comportement des agents. Bien quecela soit une bonne solution au regard des uti-lisateurs finaux, modifier ou étendre le modèlemulti-agent lui-même requiert tout de mêmedes connaissances en programmation GPU et laréutilisation du logiciel dans un autre contextereste problématique.

En ce qui concerne la généricité, [6] proposede considérer la reprogrammation GPU de touteune classe de modèles multi-agents en s’at-taquant aux simulations multi-agents utilisantune grille en deux dimensions pour environne-ment. Dans ce type de modèles, parfois quali-

fiés de spatialisés, un environnement 2D est dis-crétisé en cellules sur lesquelles se déplacentdes agents. La très utilisée plate-forme NetLogo[13] possède un tel modèle. [6] explique clai-rement que la difficulté majeure de ce travail aété de reformuler ce modèle multi-agent géné-rique en fonction des contraintes imposées parla programmation GPU, et que par conséquenttout doit être repensé. En résumé, les auteursproposent une solution qui consiste à faire cor-respondre l’état des agents avec une texture gé-rée par la carte graphique, de telle sorte quel’ensemble des dynamiques est calculé grâceau GPU. Les résultats obtenus sur des modèlesstandards comme SugarScape sont impression-nants et démontrent l’intérêt du GPU pour la si-mulation multi-agent, à la fois en termes de vi-tesse d’exécution et de scalabilité des modèles.

Néanmoins, comme le remarquent eux-mêmesles auteurs de ce travail, appliquer une telle ap-proche, que nous qualifions de tout-sur-GPU,ne se fait pas sans perdre les avantages de laprogrammation orientée objet. Par conséquent,créer un nouveau modèle de simulation requiertde manipuler du code GPU, et donc d’avoir desconnaissances dans ce domaine. Ce qui pose ànouveau le problème de l’accessibilité de l’in-terface de programmation sous-jacente. Un telmanque d’accessibilité est sans nul doute leprincipal frein au développement du GPU dansles plates-formes multi-agents génériques.

D’une manière générale, la littérature montreclairement que les difficultés techniques liéesà l’utilisation de la programmation GPU ontdeux conséquences majeures : elles limitent for-tement (1) le champ d’application des logicielsdéveloppés de par une réutilisabilité faible et (2)l’accessibilité des programmes réalisés du faitdes connaissances requises pour pouvoir faireévoluer le modèle multi-agent, celui-ci étant for-tement influencé par son implémentation surGPU. Ainsi, les approches tout-sur-GPU sontrestreintes à un domaine d’application spéci-fique et/ou nécessitent des connaissances avan-cées en programmation GPU.

3 Intégration du calcul sur GPUdans TurtleKit 3

3.1 TurtleKit et le modèle MLE

À l’instar de NetLogo, TurtleKit 2 [7] est uneplate-forme qui utilise un modèle multi-agent

2. http ://www.turtlekit.org

spatialisé. TurtleKit est implémentée en Java etrepose sur un modèle agent inspiré par le lan-gage de programmation Logo. En particulier, lesagents peuvent émettre et percevoir des phéro-mones digitales possédant des dynamiques dediffusion et d’évaporation. Ces dynamiques per-mettent de créer des champs de gradients quisont utilisés par les agents pour modéliser di-vers comportements, comme le suivi de tracespar une fourmi. Calculer de telles dynamiquesdemande énormément de ressources de calcul,ce qui limite à la fois les performances et lascalabilité des modèles qui les utilisent, mêmelorsque peu de phéromones sont mises en jeu.

L’un des objectifs principaux de TurtleKit estde fournir aux utilisateurs finaux une interfacede programmation (API) facilement accessibleet extensible. En particulier, l’API de TurtleKitest orientée objet et son utilisation repose surl’héritage de classes prédéfinies. Nous ne pou-vons donc pas adopter une stratégie de concep-tion Tout-sur-GPU qui va à l’encontre de nosobjectifs. C’est pourquoi nous avons adopté uneapproche intermédiaire qui consiste à intégrerde manière itérative des modules utilisant de laprogrammation GPU tout en conservant inchan-gée l’API de TurtleKit.

Pour atteindre cet objectif, nous avons choisi deréaliser un premier prototype que nous avonstesté en réalisant une nouvelle implémenta-tion du modèle proposé dans [1]. Dans cetteréférence, un modèle multi-agent est proposépour étudier un phénomène d’émergence multi-niveaux (MLE). Ce modèle très simple reposesur un unique comportement qui permet de gé-nérer des structures complexes qui se répètentde manière fractale. Plus précisément, à partird’un unique ensemble d’agents non structuré deniveau 0, les agents évoluent pour former desstructures de niveau 1 (des cercles) qui serventensuite à former des structures de niveau 2 etainsi de suite. Autrement dit, les agents de ni-veau 0 forment des cercles autour des agents deniveau 1 qui forment eux-mêmes des cercles au-tour des agents de niveau 2, etc.

Le comportement agent correspondant est extrê-mement simple et repose uniquement sur la per-ception, l’émission et la réaction à trois typesde phéromones différents : (1) présence, (2) ré-pulsion et (3) attraction. La phéromone de pré-sence est utilisée par un agent pour évaluer com-bien d’agents d’un certain niveau se trouventà proximité. Cette phéromone sert ainsi à fairemuter un agent vers un niveau supérieur ou in-férieur. Dit de manière simplifiée, une mutation

peut se produire lorsqu’une zone est surpeupléeou au contraire vide. Les phéromones de répul-sion et d’attraction sont utilisées par les agentspour créer une zone d’attraction circulaire au-tour d’eux, grâce à des taux d’évaporation etde diffusion différents. La phéromone d’attrac-tion est émise en faible quantité mais s’évaporedoucement, au contraire de la phéromone de ré-pulsion, ce qui permet de créer un zone d’at-traction circulaire autour d’un agent. Le com-portement d’un agent est décomposé en quatreétapes : Perception, Émission, Mutation et Mou-vement. Le comportement des agents est iden-tique pour tous les niveaux. L’état d’un agent estainsi entièrement défini par un seul entier quispécifie son niveau. Pour un niveau déterminé,un agent considère uniquement les phéromonesde niveaux adjacents.

3.2 Scalabilité du modèle MLE

Sur le papier, le plus haut niveau d’émergencequi peut être atteint grâce au modèle MLE estuniquement lié à deux paramètres : (1) la taillede l’environnement, car un niveau ne peut ap-paraître que si suffisamment de place est dispo-nible et (2) le nombre initial d’agents : il faut unnombre minimum d’agents de niveau i-1 pourvoir apparaître des structures de niveau i.

Par rapport aux objectifs que nous poursuivons,créer une nouvelle implémentation du modèleMLE constitue un test parfait car, pour voir ap-paraître des niveaux d’émergence plus élevés, ilest rapidement nécessaire d’accroître à la foisla taille de l’environnement et le nombre desagents. De plus, chaque niveau supplémentairenécessite de gérer trois nouvelles phéromones,ce qui augmente significativement le besoin enressources de calcul du modèle et rend particu-lièrement difficile le passage à l’échelle.

Dans un premier temps, notre attention s’estdonc focalisée sur le calcul des dynamiquesde diffusion et d’évaporation. En effet, ces dy-namiques nécessitent d’effectuer des calculspour chaque cellule de la grille à chaque pasde temps. Ainsi, bien que ces calculs soientsimples, la complexité associée évolue de ma-nière quadratique avec la taille de l’environne-ment. Nous avons donc décidé de traduire cesdynamiques en code GPU.

Par rapport à nos objectifs, ce choix était aussinaturel car ces dynamiques sont complètementdécouplées du modèle comportemental d’unagent. Il est donc possible de créer un module

GPU correspondant sans avoir à modifier quoique ce soit de l’API du modèle agent. De plus,comme nous allons le voir, elles sont aussi rela-tivement faciles à traduire car les calculs corres-pondants sont naturellement spatialement distri-bués, ce qui convient bien au calcul sur GPU.

4 Le module de diffusion GPU

4.1 Traduction GPU de l’évaporation

Pour expliquer simplement la traduction des dy-namiques d’évaporation et de diffusion en codeGPU, nous présentons ici le mécanisme d’éva-poration car il est extrêmement simple. L’éva-poration d’une phéromone sur la grille consistesimplement à multiplier la quantité présentedans une cellule par un coefficient compris entre0 et 1 (le taux d’évaporation, evapCoef ). L’im-plémentation séquentielle de cette dynamiquepeut être définie de la manière suivante :

Pour i de 0 à largeur fairePour j de 0 à hauteur faire

grille[i][j]←grille[i][j]× evapCoef ;

Fin PourFin Pour

Algorithme 1: évaporation en séquentiel

Voyons maintenant quelques principes de pro-grammation GPU. Une carte graphique équi-pée de capacités GPGPU est capable de réali-ser l’exécution d’une même procédure, appeléekernel, sur de très nombreux threads s’exécutantde manière concurrente. Ces threads sont orga-nisées en blocs (block), eux-mêmes organisésen grille de blocs. Chaque thread possède parailleurs des coordonnées en trois dimensions, x,y et z qui le localisent dans son bloc, chaquebloc étant lui-même localisé de la même ma-nière dans la grille.

Ainsi, il est possible de considérer unique-ment les coordonnées en deux dimensions desblocs et des threads pour définir une grille dethreads correspondant à une grille de données.Par exemple, si la capacité d’un bloc est de 1024threads (celle-ci dépend du matériel), il est pos-sible de définir une grille de 1000×1000 en al-louant une grille de blocs d’une taille de 32×32,avec chaque bloc ayant lui-même une taille de

32×32. Ce qui produit une matrice surdimen-sionnée contenant 1024×1024 threads. Cettetaille trop large par rapport aux données consi-dérées est habituelle et ne pose pas de problèmecar elle est gérée au niveau du code GPU. Ainsi,la taille d’une grille de blocs et la dimension desblocs sont des paramètres fondamentaux utiliséspour l’exécution d’un kernel sur le GPU. Dansnotre cas, cela va nous permettre de faire corres-pondre chaque cellule de la grille de l’environ-nement des agents avec un unique thread.

Le kernel correspondant au processus d’évapo-ration peut ainsi être programmé en GPU de lamanière suivante :

i← blockIdx.x × blockDim.x + threadIdx.x ;j← blockIdx.y × blockDim.y + threadIdx.y ;Si (i < largeur ET j < hauteur) Alors

grille[i][j]← grille[i][j] × evapCoef ;Fin Si

Algorithme 2: évaporation en GPU

Lorsque l’exécution de ce kernel est appelée surle GPU, tous les threads alloués exécutent l’al-gorithme 2 simultanément. Les deux premièreslignes de cette procédure déterminent les coor-données du thread qui est en train de s’exécu-ter. Ensuite, un test est effectué pour savoir si cethread n’est pas en dehors des limites de la grillede données. Si c’est le cas, la valeur de la cellulecorrespondante est mise à jour.

Le kernel correspondant à la dynamique de dif-fusion est un peu plus complexe car il néces-site l’utilisation d’une grille de données tempo-raire. Sa traduction a été cependant relativementsimple et repose sur un principe similaire. Nousavons ainsi développé un module GPU pourl’évaporation et la diffusion que nous appelle-rons par la suite le module de diffusion GPU parsimplicité.

Étant donné nos objectifs en termes d’accessibi-lité, il était fondamental de conserver le langageJava. C’est pourquoi nous avons utilisé la librai-rie JCuda (Java bindings for Cuda 3) qui per-met de commander l’exécution de kernels GPU,écrits en langage Cuda, directement depuis Java.

3. Compute Unified Device Architecture, Cuda est une plate-formede programmation développée par Nvidia pour les cartes graphiques decette marque. Elle possède actuellement le plus grand nombre de fonc-tionnalités par rapport aux autres solutions comme OpenCL.

TurtleKit 3

Turtle

CudaPheromone

JCuda

Pheromone

+diffusion()+evaporation()

JavaPheromone

manipule *

MaDKit 5Cuda

GPU diffusion

pheromones.cu

{exécution du kernel}

FIGURE 1 – Intégration de la diffusion GPUdans TurtleKit 3

La figure 1 illustre l’intégration du module dediffusion GPU dans le prototype de Turtle-Kit 3. En particulier, on peut voir qu’un agent(une turtle) manipule indifféremment, suivantle contexte matériel, des phéromones utilisantune implémentation classique de la diffusion oule module de diffusion GPU. Le modèle agentn’a donc pas besoin d’être modifié. Si le ma-tériel le permet, les phéromones créées lors del’exécution sont donc des instances de la classeCudaPheromone. Pour calculer la diffusion etl’évaporation, celles-ci interagissent avec le mo-dule de diffusion GPU qui accède aux fonctionsCuda grâce à JCuda. Les kernels eux-mêmessont codés dans le fichier Cuda pheromones.cu.

4.2 Résultats obtenus par le module de dif-fusion GPU

FIGURE 2 – Temps d’exécution de la diffusion :séquentiel et GPU avec JCuda

La figure 2 compare les résultats obtenus avecle module de diffusion GPU et avec une im-plémentation séquentielle du processus de diffu-sion. Ces tests ont été réalisés en dehors de touteautre simulation afin d’éviter les bruits prove-nant d’autres traitements. Ces tests ont été réa-lisés à l’aide d’un Xeon @ 2.67GHz et d’unecarte graphique Nvidia Quadro 4000 dotée de256 cœurs, ce qui constitue une valeur moyenne

à l’heure actuelle.

La figure 2 montre les résultats obtenus avecdifférentes tailles d’environnement pour uneunique phéromone. Comme attendu, les résul-tats montrent que même pour la plus petite grille(100×100) , la version utilisant JCuda s’exé-cute avec de meilleures performances. Au furet à mesure que la taille de l’environnement estaugmentée, le module GPU surpasse la versionséquentielle jusqu’à obtenir des performancesplus de 20 fois supérieures pour un environne-ment de 2000×2000.

Pour que ce test soit significatif par rapport ànos objectifs, il faut noter que nous avons pris encompte le fait que le résultat d’une itération doitêtre rendu disponible pour une utilisation sur leCPU. En effet, dans une simulation classique,les agents devront avoir accès aux résultats àchaque pas de simulation pour pouvoir calcu-ler leur comportement. Cette contrainte requiertd’appeler à chaque pas de temps des primitivesqui permettent la synchronisation entre les exé-cutions du CPU et du GPU. Ces primitives sontcoûteuses : si on laisse le GPU exécuter tous sestraitements sans être interrompu, on obtient desrésultats encore 20 fois supérieurs, environ 200fois plus rapide que le séquentiel.

Par ailleurs, il faut savoir qu’il existe de nom-breux paramètres qui peuvent être pris encompte pour l’exécution d’un kernel avec Cuda.Certains d’entre eux peuvent influencer lesperformances dans des proportions significa-tives. Par exemple, une astuce peu documentéeconsiste à systématiquement définir au moinsautant de blocs qu’il existe de cœurs sur la cartegraphique. Loin d’être une règle clairement éta-blie, nous avons pu constater un impact impor-tant sur les résultats.

Dans l’analyse de ces résultats, il est donc im-portant de garder à l’esprit qu’ils ont été obtenusdans le contexte particulier formé par le logi-ciel et le matériel utilisés pour cette expérience.Il est possible d’obtenir des résultats très diffé-rents en termes de ratio en fonction des configu-rations. Par contre, ces résultats montrent claire-ment que le module de diffusion GPU permet lepassage à l’échelle alors que ce n’est pas le casavec la version séquentielle.

5 Le module GPU perception degradients

5.1 Prochaine étape : les agents

L’intégration du module de diffusion GPU dansTurtleKit n’a pas posé de problème grâce à samodularité. Le gain de performance associé aété immédiatement significatif. Nous avons puainsi augmenter la taille de l’environnement àdes valeurs que nous n’avions jamais pu testerauparavant dans des conditions d’exécution as-sez bonnes pour travailler avec le modèle.

Cependant, atteindre des niveaux d’émergencesupérieurs avec le modèle MLE nécessite d’aug-menter non seulement la taille de l’environne-ment mais aussi le nombre total d’agents ini-tial. En augmentant progressivement le nombred’agents, il nous est alors apparu évident quela majorité du temps d’exécution de la simula-tion était maintenant utilisée par les agents pourcalculer leur comportement. En fait, les agentspassaient la plupart de leur temps (i.e. du tempsCPU) à analyser les différents gradients de phé-romone pour calculer leur mouvement.

En effet, chaque agent réalise un calcul pourconnaître la cellule voisine qui possède leplus, ou le moins, de phéromone d’un certaintype pour décider l’orientation de son mou-vement futur. Des méthodes telles que get-MaxDirection(attractionField) ou getMinDirec-tion(repulsionField) sont intensivement utili-sées par les agents du modèle. De tels calculsnécessitent de sonder l’ensemble des cellulesqui se trouvent autour de l’agent pour chaquephéromone d’intérêt, puis de calculer la direc-tion à prendre en fonction des valeurs minimalesou maximales trouvées. La figure 3 illustre cecalcul pour une cellule.

Dans le modèle MLE, les processus de diffusionet d’évaporation sont les seules dynamiques en-vironnementales existantes. De fait, pour amé-liorer plus avant les performances, il était clairque nous n’avions d’autre choix que de réaliserun module GPU chargé d’optimiser l’exécutiondes agents. Cependant, afin de ne pas renier surnos objectifs, il était crucial de ne pas adopterune approche qui aurait pu nous conduire versdu tout-sur-GPU. La section suivante présentela solution que nous utilisons et montre com-ment nous tirons parti du GPU pour les agentssans pour autant modifier leur API.

FIGURE 3 – Exemple du calcul des directionsmin et max pour un gradient de phéromone

5.2 Délégation GPU de la perception desagents

En ce qui concerne la manière dont les agentsdu modèle MLE perçoivent et analysent les gra-dients de phéromones, il faut remarquer que lescalculs correspondants n’impliquent pas l’étatde l’agent qui les réalise. Calculer la directiond’un gradient n’a rien à voir avec l’état dans le-quel se trouve l’agent. L’idée est donc d’utiliserà nouveau cette indépendance pour pouvoir ef-fectuer ces calculs à l’aide d’un module GPUsans modifier le modèle agent.

À première vue, il reste cependant un pro-blème de dépendance car c’est les agents quidéclenchent ces perceptions, et non l’environne-ment comme c’était le cas pour le processus dediffusion. Ce qui pourrait amener à penser qu’ilest nécessaire de passer une partie du comporte-ment des agents dans le module GPU.

Pour surmonter cette difficulté, la solution quenous avons employée consiste à calculer cesperceptions directement dans l’environnementpartout et tout le temps. Dit autrement, il s’agitde réifier l’ensemble de ces perceptions dansune unique dynamique environnementale calcu-lée par le GPU.

Cette solution peut sembler contre intuitive dansla mesure où un grand nombre de calculs seronteffectués pour rien car ils ne seront pas utiliséspar les agents. Mais nous bénéficions en fait icides spécificités de la programmation GPU. Eneffet, effectuer un calcul sur le GPU pour unecellule prend, en ordre de grandeur, à peu prèsle même temps que si on le réalise sur toutes lescellules à la fois.

Nous avons donc défini un second moduleGPU qui implémente cette dynamique environ-nementale et calcule l’ensemble des perceptions

possibles pour les agents. Nous l’appellerons icile module perception de gradient GPU. La par-ticularité du kernel associé repose sur l’utilisa-tion de deux tableaux de données supplémen-taires qui sont utilisés pour stocker les directionsminimales et maximales pour un gradient danschaque cellule.

5.3 Analyse des résultats obtenus grâce aumodule de perception de gradient GPU

Cette analyse repose sur des tests réalisés surle modèle MLE avec uniquement le module dediffusion GPU, puis avec les deux modules. Lematériel utilisé pour obtenir ces résultats est lemême que dans la section 4.2. Très peu docu-mentées, les sources de ce projet sont cepen-dant disponibles sur www.turtlekit.org. Elles ontété testées sous Linux avec Cuda 4 et JCuda-0.4.1. Par ailleurs, pour ces simulations, le ni-veau maximum d’un agent a été fixé à 5, de tellesorte qu’il existe 15 phéromones à gérer.

La figure 4 compare la vitesse d’exécution pourdifférentes tailles d’environnement et popula-tions d’agents. Par exemple, pour une densité de140% dans un environnement de 2000 × 2000,il y a 5.6 millions d’agents interagissant sur unegrille de 4 millions de cellules.

La figure 4 montre que l’ajout du module de per-ception de gradient GPU n’améliore pas la vi-tesse pour la plus faible densité d’agents testée.Ce résultat négatif peut être expliqué par le coûtsupplémentaire induit par les synchronisationsadditionnelles, entre CPU et GPU, requises parles tableaux de données supplémentaires. Celamontre aussi que, dans le cadre de la configu-ration que nous avons utilisée, il existe un seuilde population en deçà duquel il n’est pas ren-table de déclencher un calcul sur GPU pour laperception des gradients. Le pire cas étant ce-lui où un seul agent se trouve dans un large en-vironnement. Et en effet, ce pire cas est tou-jours plus lent lorsqu’on utilise les deux mo-dules. Cependant, les tests que nous avons effec-tués montrent que le surcoût engendré par l’uti-lisation du deuxième module n’est pas très élevépour des densités avoisinant les 5%, et qu’il de-vient quasiment négligeable pour une densité de10%, valeur basse pour le modèle MLE.

Ainsi, même avec le surcoût induit par les ap-pels GPU supplémentaires, le module de per-ception de gradient GPU devient efficace dèsqu’on considère une densité de population de20% et des environnements larges. Pour les va-leurs supérieures, la simulation est toujours plus

FIGURE 4 – Comparaison des temps d’exécution obtenus sur le modèle MLE avec et sans le modulede perception de gradient GPU

rapide avec les deux modules, jusqu’à presquedeux fois pour le plus gros cas que nous avonstesté. Si on prend en compte que nous avons uti-lisé une carte graphique moyenne, ces résultatssont très encourageants et montrent la faisabilitéet l’intérêt de l’approche que nous proposons,surtout en ce qui concerne le passage à l’échelle.

6 Généralisation de l’approche

6.1 L’environnement comme abstraction depremier ordre dans les SMA

L’approche que nous avons utilisée consistedonc à transformer des perceptions agents endynamique environnementale. L’environnementprend donc un peu plus d’importance dans l’ar-chitecture de la plate-forme TurtleKit. En fait,pour généraliser notre démarche, il convientde la rapprocher des travaux de recherche quiconsidèrent l’environnement comme un conceptfondamental des SMA.

Considérer l’environnement comme une abs-traction de premier ordre est aujourd’hui uneidée bien acceptée et son intérêt pour la mo-délisation et le développement de SMA n’estplus à prouver [15]. En particulier, elle permetd’augmenter l’efficacité des interactions entreagents. Par exemple, dans [14], de véritablesvéhicules automatisés (Automated Guided Ve-hicles AGV) utilise un environnement virtuelchargé de calculer la validité de leurs mouve-ments futurs. Lorsque l’environnement détecte

une possible collision future, il établit un ordrede priorité entre les mouvements afin de ré-soudre automatiquement les conflits spatiaux,sans que les agents aient besoin d’intervenir.Ainsi, les agents n’ont pas besoin de traiter ceproblème. Ce qui permet de (1) diminuer lacomplexité du comportement des agents et ainsi(2) faire en sorte que les agents se focalisent surleur tâche principale qui est d’aller d’un point Aà un point B.

Plus généralement, utiliser l’environnementcomme une entité active est une approche trèsintéressante pour la simplification du processuscomportemental des agents. L’idée sous-jacenteest que les agents ont finalement besoin de ma-nipuler des percepts de haut niveau pour calcu-ler leur comportement : ils ne sont pas intéresséspar les données environnementales de bas ni-veau qui nécessitent un traitement pour être in-telligibles. Il est donc intéressant de soulager lesagents de ces traitements et de déléguer à l’en-vironnement le soin de produire des données deperception haut niveau à partir de données envi-ronnementales brutes [2].

6.2 Délégation GPU des perceptions agents

Dans le cadre de notre expérience, considérerl’environnement comme une partie fondamen-tale du système est au cœur de notre solution.Cela nous a permis d’atteindre nos deux objec-tifs : (1) conserver l’accessibilité de notre mo-dèle agent dans un contexte GPU et (2) passerà l’échelle et travailler avec un grand nombre

d’agents sur de grandes tailles d’environnement.

Pour généraliser notre expérience, nous propo-sons un principe de conception qui repose surdeux piliers : (1) l’utilisation de l’environne-ment comme une entité active et (2) la prise encompte du contexte particulier que représente laprogrammation GPU. Ce principe de concep-tion, que nous appelons délégation GPU desperceptions agents, peut-être énoncé de la ma-nière suivante :

Tout calcul de perception agent quin’implique pas l’état de l’agent peutêtre transformé dans une dynamiqueendogène de l’environnement, et ainsiconsidéré pour une implémentationdans un module GPU indépendant.

Le principal intérêt de ce principe est de pro-mouvoir une réutilisation simplifiée des mo-dules GPU qui seront développés selon celui-ci, car ils n’auront aucun lien avec le modèled’agent qui les utilisera. Par exemple nous avonspu réutiliser dans TurtleKit les modules GPUprésentés avec d’autres modèles agents qui uti-lisent des phéromones (e.g. les modèles à basede fourmis).

Plus généralement, nous pensons que son in-térêt ne se limite pas aux objectifs que nousavons ici poursuivis. Celui-ci peut être appli-qué non seulement sur d’autres plates-formessimilaires (e.g. NetLogo), mais aussi en dehorsdu contexte d’une simulation spatialisée. Il peutmême être utilisé dans le cadre d’une approchetout-sur-GPU. Tout son intérêt est de promou-voir la réutilisabilité des modules GPU dévelop-pés dans différents contextes, ceci grâce à uneséparation claire entre le modèle agent et le mo-dèle environnemental.

7 Conclusion et perspectives

il est évident que le GPU est une technologied’avenir pour l’étude des systèmes complexesmodélisés à l’aide du paradigme multi-agent.Mais la programmation GPU est si spécifiqueque de nombreux efforts de développement mê-lant SMA et GPU sont tout simplement perdus :les programmes obtenus sont trop complexes.Dans ce contexte, notre travail a un objectif :profiter de la puissance du GPU dans Turtle-Kit tout en conservant inchangée l’API de sonmodèle agent. Dans cet article, nous avons toutd’abord présenté comment nous avons réaliséle module de diffusion GPU en appliquant une

approche centrée environnement qui consiste àtraduire des dynamiques environnementales encode GPU.

Les gains de performances que nous avons ob-tenus sont sans doute encore bien inférieurs àceux que nous aurions pu obtenir en appliquantune approche tout-sur-GPU. Pour l’instant, lescontraintes que nous nous sommes imposés enterme d’accessibilité sont bien sûr un facteur li-mitant mais, même avec cette limite, les résul-tats obtenus par ce premier module sont déjà trèssignificatifs.

De plus, il faut rappeler ici que ces résultats sontfortement liés à notre configuration. En parti-culier, nous avons utilisé une carte graphiqueNVidia Quadro 4000 contenant 256 cœurs alorsque la récente Tesla K10 contient 2 GPU équi-pés chacun de 1536 cœurs : un total de 3072cœurs sur une seule carte. Les perspectives of-fertes par la programmation GPU sont donc ex-trêmement prometteuses et nous encouragent àcontinuer d’intégrer progressivement de nou-veaux modules GPU dans TurtleKit.

Nous avons ensuite proposé le principe de dé-légation GPU des perceptions agents et mon-tré comment celui-ci nous a permis d’aller plusloin dans notre objectif. D’une manière géné-rale, nous pensons que ce principe de concep-tion constitue un moyen intéressant d’adresserle problème de la réutilisabilité dans le cadre dela programmation GPU pour les SMA. En effet,les modules ainsi développés ne reposent passur un modèle d’agent particulier, ce qui permetd’envisager l’intégration de code GPU dans uneplate-forme classique de manière simplifiée etitérative.

Nous comptons notamment travailler avecd’autres modèles afin d’identifier de nouveauxmodules en appliquant le principe de délégationGPU. À long terme notre objectif est donc dedévelopper une librairie de modules GPU dé-diée à la simulation de systèmes multi-agents.Aujourd’hui, plusieurs librairies GPU géné-riques ont déjà été implémentés dans d’autresdomaines : Nvidia CuBLAS (Compute UnifiedBasic Linear Algebra Subprograms), NPP (Nvi-dia Performance Primitives) pour le traitementdu signal, l’image et la vidéo, GPU AI path fin-ding, etc. Nous pensons qu’il est aujourd’hui in-téressant d’adopter une démarche similaire dansle cadre des SMA.

Références[1] Grégory Beurier, Olivier Simonin, and

Jacques Ferber. Model and simulation ofmulti-level emergence. In 2nd IEEE Inter-national Symposium on Signal Processingand Information Technology, ISSPIT’02,pages 231–236, Marrakesh, Morocco, De-cember 2002.

[2] Paul H. Chang, Kuang-Tai Chen, Yu-Hung Chien, Edward Kao, and Von-WunSoo. From reality to mind : A cogni-tive middle layer of environment conceptsfor believable agents. In Danny Weyns,H. Van Dyke Parunak, and Fabien Mi-chel, editors, Environments for Multi-Agent Systems, First International Work-shop, E4MAS 2004, New York, NY, USA,July 19, 2004, Revised Selected Papers, vo-lume 3374 of LNAI, pages 57–73. Sprin-ger, 2005.

[3] Shuai Che, Michael Boyer, Jiayuan Meng,David Tarjan, Jeremy W. Sheaffer, and Ke-vin Skadron. A performance study ofgeneral-purpose applications on graphicsprocessors using cuda. Journal of Paralleland Distributed Computing, 68(10) :1370– 1380, 2008. General-Purpose Processingusing Graphics Processing Units.

[4] Aljosha Demeulemeester, Charles-Frederik Hollemeersch, Pieter Mees,Bart Pieters, Peter Lambert, and RikVan de Walle. Hybrid path planning formassive crowd simulation on the gpu.In Proceedings of the 4th internationalconference on Motion in Games, MIG’11,pages 304–315, Berlin, Heidelberg, 2011.Springer-Verlag.

[5] Roshan M. D’Souza, Mikola Lysenko,Simeone Marino, and Denise Kirschner.Data-parallel algorithms for agent-basedmodel simulation of tuberculosis on gra-phics processing units. In Proceedingsof the 2009 Spring Simulation Multiconfe-rence, SpringSim ’09, pages 21 :1–21 :12,San Diego, CA, USA, 2009. Society forComputer Simulation International.

[6] Mikola Lysenko and Roshan M. D’Souza.A framework for megascale agent basedmodel simulations on graphics processingunits. Journal of Artificial Societies andSocial Simulation, 11(4) :10, 2008.

[7] Fabien Michel, Grégory Beurier, andJacques Ferber. The TurtleKit simula-tion platform : Application to complex sys-tems. In Alain Akono, Emmanuel Tonyé,

Albert Dipanda, and Kokou Yétongnon,editors, Workshops Sessions, First Inter-national Conference on Signal & ImageTechnology and Internet-Based SystemsSITIS’ 05, pages 122–128. IEEE, novem-ber 2005.

[8] Fabien Michel, Jacques Ferber, and AlexisDrogoul. Multi-Agent Systems and Simu-lation : a Survey From the Agents Com-munity’s Perspective. In Danny Weynsand Adelinde Uhrmacher, editors, Multi-Agent Systems : Simulation and Applica-tions, Computational Analysis, Synthesis,and Design of Dynamic Systems, pages3–52. CRC Press - Taylor & Francis, 052009.

[9] M.J. North, E. Tatara, N. Collier, andJ. Ozik. Visual agent-based model deve-lopment with Repast Simphony. In Agent2007 Conference on Complex Interactionand Social Emergence, pages 173–192,Argonne, IL, USA, November 2007. Ar-gonne National Laboratory.

[10] John D. Owens, David Luebke, Naga Go-vindaraju, Mark Harris, Jens Krüger, Aa-ron E. Lefohn, and Timothy J. Purcell. Asurvey of general-purpose computation ongraphics hardware. Computer GraphicsForum, 26(1) :80–113, 2007.

[11] Paul Richmond, Dawn Walker, SimonCoakley, and Daniela Romano. High per-formance cellular level agent-based simu-lation with FLAME for the GPU. Briefingsin Bioinformatics, 11(3) :334–347, 2010.

[12] Alessandro Ribeiro Da Silva, Wallace San-tos Lages, and Luiz Chaimowicz. Boidsthat see : Using self-occlusion for simula-ting large groups on gpus. Comput. Enter-tain., 7(4) :51 :1–51 :20, January 2010.

[13] Elizabeth Sklar. Netlogo, a multi-agentsimulation environment. Artificial Life,13(3) :303–311, 2007.

[14] Danny Weyns, Nelis Boucké, and TomHolvoet. Gradient field-based task as-signment in an agv transportation sys-tem. In Proceedings of the fifth inter-national joint conference on Autonomousagents and multiagent systems, AAMAS’06, pages 842–849, New York, NY, USA,2006. ACM.

[15] Danny Weyns, Andrea Omicini, and JamesOdell. Environment as a first class abstrac-tion in multiagent systems. AutonomousAgents and Multi-Agent Systems, 14 :5–30,2007. 10.1007/s10458-006-0012-0.