Détection de Collision pour environnements large échelle : modèle unifié et adaptatif sur architectures multi-coeur et multi-GPU
Institution:
Rennes, INSADisciplines:
Directors:
Abstract EN:
Virtual reality environments are becoming increasingly large and complex, a real-time interaction level is becoming impossible to insure. Indeed, because of their complexity, due to a detailed geometry and specific physical properties, these large scale environments create a critical computational bottleneck on the physical algorithms. We focused our work on the first step of these algorithms concerning the collision detection process because the issues are an integral part of this bottleneck and their complexity can sometimes be quadratic in few situations. The deep upheaval that suffer hardware architectures those last years has opened a new way to reduce this bottleneck. Multiplying the number of cores offers the ability to execute these algorithms in parallel on one single processor. At the same time, the graphics cards have gone from being a simple graphical display device to a supercomputer. They now enjoy special attention from the community dealing with physical simulation. To perform large scale simulation and be generic on the runtime architecture, we proposed unified and adaptive mapping models between collision detection algorithms and the runtime architecture using multi-core and multi-GPU. We have developed innovative and effective solutions to significantly reduce the computation time in large scale environments while ensuring the sustainability of results. Our models cover the global collision detection pipeline, focusing both on algorithms of low or high level. Our models based on single computational unit such as multi-core and GPU combine different techniques of spatial subdivision algorithms based on topology and load balancing techniques based on data stealing. Our hybrid solution enables to increase space and computing time within large scale virtual environments. The coupling of these new algorithms enabled us to develop two models of dynamic algorithmic adaptation based (or not) on off-line precomputations scenarios. Finally, it became necessary to add to the collision detection pipeline a new dimension representing the taking account of the architecture for optimal execution. With this formalism, we proposed a new pipeline collision detection with a granularity of parallelism on multicore processors or multi-GPU platforms. It enables simultaneous execution of different stages of the pipeline and a parallel internal to each of these steps.
Abstract FR:
Les environnements de réalité virtuelle devenant de plus en plus complexes et de très grandes dimensions, un niveau d'interaction temps-réel devient impossible à garantir. En effet, de par leur complexité, due à une géométrie détaillée et aux propriétés physiques spécifiques, ces environnements large échelle engendrent un goulet d'étranglement calculatoire critique sur les algorithmes de simulation physique. Nous avons focalisé nos travaux sur la première étape de ces algorithmes qui concerne la détection de collision car les problématiques font partie intégrante de ce goulet d'étranglement et leur complexité peut parfois se révéler quadratique dans certaines situations. Le profond bouleversement que subissent les architectures machines depuis quelques années ouvre une nouvelle voie pour réduire le goulet d'étranglement. La multiplication du nombre de cœurs offre ainsi la possibilité d'exécuter ces algorithmes en parallèle sur un même processeur. Dans le même temps, les cartes graphiques sont passées d'un statut de simple périphérique d'affichage graphique à celui de supercalculateur. Elles jouissent désormais d'une attention toute particulière de la part de la communauté traitant de la simulation physique. Afin de passer au large échelle et d'être générique sur la machine d'exécution, nous avons proposé des modèles unifiés et adaptatifs de correspondance entre les algorithmes de détection de collision et les architectures machines de type multi-cœur et multi-GPU. Nous avons ainsi défini des solutions innovantes et performantes permettant de réduire significativement le temps de calcul au sein d'environnements large échelle tout en assurant la pérennité des résultats. Nos modèles couvrent l'intégralité du pipeline de détection de collision en se focalisant aussi bien sur des algorithmes de bas ou de haut niveau. Nos modèles multi-cœur et simple GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des technique d'équilibrage de charge basées sur le vol de données. Notre solution hybrides permet d'accroitre l'espace et le temps de calcul ainsi que le passage au large échelle. L'association de ces nouveaux algorithmes nous a permis de concevoir deux modèles d'adaptation algorithmique dynamique basés, ou non, sur des scénarios de pré-calcul hors-ligne. Enfin, il nous est apparu indispensable d'ajouter au pipeline de détection de collision une nouvelle dimension révélant la prise en compte des architectures pour une exécution optimale. Grâce à ce formalisme, nous avons proposé un nouveau pipeline de détection de collision offrant une granularité de parallélisme sur processeurs multi-cœur ou plateformes multi-GPU. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes.