Simulations Physiques Interactives sur des Architectures Multi-Core et Multi-GPU

Interactive physical simulation is a key component of realistic virtual environments. However, the amount of computations as well as the code complexity grow quickly with the variety, number and size of the simulated objects. During this thesis we studied the different ways to improve interactivity, with the constraint of minimizing the impact in the simulation code. We started by developing a new approach to collision detection between deformable bodies that allows deep intersections. Experiments show that this approach is fast and more robust than traditional proximity-based collisions, allowing physical simulations to employ large time steps. To take profit of multi-core machines, we propose a parallelization approach that relies on a task parallelism. Prior to running a simulation step, we extract a task dependency graph that is partitioned to define the task distribution between processors. This approach has a low impact on physics algorithms as parallelism is mainly extracted from the coordination code. Finally we extended our works multi-CPU and multi-GPU architectures. Using these resources efficiently in a seamless way is a challenging issue. We propose a parallelization scheme for dynamically balancing work load between multiple CPUs and GPUs. We rely on a two level scheduling associating a traditional task graph partitioning and a work stealing guided by processor affinity and heterogeneity. These criteria are intended to limit inefficient task migrations between GPUs, the cost of memory transfers being high, and to favor mapping small tasks on CPUs and large ones on GPUs to take advantage of heterogeneity.La simulation physique interactive est une composante clé pour les environnements virtuels. Toutefois, la quantité de calcul ainsi que la complexité du code augmente rapidement avec la variété, le nombre et la taille des objets simulés. Au cours de cette thèse nous avons étudié les différents moyens d'améliorer l'interactivité, et en même temps de minimiser l'impact sur le code de simulation. En premier lieu nous avons développé une nouvelle approche de détection de collisions pour les objets déformables qui est rapide et plus robuste que les approches traditionnelles de détection par proximité. Pour tirer profit des machines multi-core, nous proposons une approche de parallélisation qui repose sur un parallélisme des tâches. Avant l'éxecution d'un pas de temps nous extrayons un graphe de dépendance de tâche qui est partitionné pour définir la répartition des tâches entre les processeurs. Cette approche a un faible impact sur les algorithmes de simulation physique étant donné que le parallélisme est obtenu en changeant uniquement le code d'orchestration du lancement des tâches. Finalement, nous avons étendu nos travaux aux architectures multi-CPU et multi-GPU. L'utilisation de ces ressources de manière efficace et transparente est un enjeu de taille. Nous proposons un schéma de parallélisation pour l'équilibrage dynamique de charge entre plusieurs CPUs et GPUs. Nous nous appuyons sur une approche à deux niveaux associant un partitionement du graphe de tâches et l'équilibrage de charge par l'utilisation du vol de travail guidé par des critères d'affinité entre processeurs. Ces critères visent à limiter les migrations de taches entre les unités de calcul, et de favoriser l' association de petites tâches sur les processeurs et des grandes sur les GPU pour tirer parti de l'hétérogénéité