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é.

Initialement con¸cu pour d'echarger le CPU des tˆaches de rendu graphique, le GPU estdevenu une architecture massivement parall'ele adapt'ee au traitement de donn'ees volumineuses.Alors qu'il occupe une part de march'e importante dans le Calcul Haute Performance, uned'emarche d'Ad'equation Algorithme Architecture est n'eanmoins requise pour impl'ementerefficacement un algorithme sur GPU.La contribution de cette th'ese est double. Dans un premier temps, nous pr'esentons legain significatif apport'e par l'impl'ementation optimis'ee d'un algorithme de granulom'etrie(l'ordre de grandeur passe de l'heure 'a la minute pour un volume de 10243 voxels). Un mod'eleanalytique permettant d''etablir les variations de performance de l'application de granulom'etriesur GPU a 'egalement 'et'e d'efini et pourrait ˆetre 'etendu 'a d'autres algorithmes r'eguliers.Dans un second temps, un outil facilitant le d'eploiement d'applications de Traitementdu Signal et de l'Image sur cluster multi-GPU a 'et'e d'evelopp'e. Pour cela, le champ d'actiondu programmeur est r'eduit au d'ecoupage du programme en tˆaches et 'a leur mapping sur les'el'ements de calcul (GPP ou GPU). L'am'elioration notable du d'ebit sortant d'une applicationstreaming de calcul de carte de saillence visuelle a d'emontr'e l'efficacit'e de notre outil pourl'impl'ementation d'une solution sur cluster multi-GPU. Afin de permettre un 'equilibrage decharge dynamique, une m'ethode de migration de tˆaches a 'egalement 'et'e incorpor'ee 'a l'outil.

El presente trabajo se inscribe en el campo de la computación paralela y, más en concreto, en el desarrollo y utilización de modelos computacionales en arquitecturas paralelas heterogéneas para la resolución de problemas aplicados. En la tesis abordamos una serie de problemas que están relacionados con la aplicación de la tecnología en el ámbito de las explotaciones agrícolas y comprenden: la representación del relieve, el manejo de información climática como la temperatura, y la gestión de recursos hídricos. El estudio y la solución a estos problemas en el área en la que se han estudiado tienen un amplio impacto económico y medioambiental. Los problemas basan su formulación en un modelo matemático cuya solución es costosa desde el punto de vista computacional, siendo incluso a veces inviable. La tesis consiste en implementar algoritmos paralelos rápidos y eficientes que resuelven el problema matemático asociado a estos problemas en nodos multicore y multi-GPU. También se estudia, propone y aplican técnicas que permiten a las rutinas diseñadas adaptarse automáticamente a las características del sistema paralelo donde van a ser instaladas y ejecutadas con el objeto de obtener la versión más cercana posible a la óptima a un bajo coste. El objetivo es proporcionar un software a los usuarios que sea portable, pero a la vez, capaz de ejecutarse eficientemente en la ordenador donde se esté trabajando, independientemente de las características de la arquitectura y de los conocimientos que el usuario pueda tener sobre dicha arquitectura. / Do Carmo Boratto, M. (2015). Modelos Paralelos para la Resolución de Problemas de Ingeniería Agrícola [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48529 / TESIS

The main focus of this project is usage of multi - GPU systems and usage of CUDA unified memory . Its goal is to accelerate computation of 2D and 3D FFT, which is the main part of simulations in k- Wave library .K- Wave is a C++/ Matlab library used for simulations of propagation of ultrasonic waves in 1D , 2D or 3D space . Acceleration of these functions is necessary , because the simulations are computationally intensive .

Multi-GPU machines are being increasingly used in high performance computing. These machines are being used both as standalone work stations to run computations on medium to large data sizes (tens of gigabytes) and as a node in a CPU-Multi GPU cluster handling very large data sizes (hundreds of gigabytes to a few terabytes). Each GPU in such a machine has its own memory and does not share the address space either with the host CPU or other GPUs. Hence, applications utilizing multiple GPUs have to manually allocate and managed at a on each GPU. A significant body of scientific applications that utilize multi-GPU machines contain computations inside affine loop nests, i.e., loop nests that have affine bounds and affine array access functions. These include stencils, linear-algebra kernels, dynamic programming codes and data-mining applications. Data allocation, buffer management, and coherency handling are critical steps that need to be performed to run affine applications on multi-GPU machines. Existing works that propose to automate these steps have limitations and in efficiencies in terms of allocation sizes, exploiting reuse, transfer costs and scalability. An automatic multi-GPU memory manager that can overcome these limitations and enable applications to achieve salable performance is highly desired. One technique that has been used in certain memory management contexts in the literature is that of bounding boxes. The bounding box of an array, for a given tile, is the smallest hyper-rectangle that encapsulates all the array elements accessed by that tile. In this thesis, we exploit the potential of bounding boxes for memory management far beyond their current usage in the literature. In this thesis, we propose a scalable and fully automatic data allocation and buffer management scheme for affine loop nests on multi-GPU machines. We call it the Bounding Box based Memory Manager (BBMM). BBMM is a compiler-assisted runtime memory manager. At compile time, it use static analysis techniques to identify a set of bounding boxes accessed by a computation tile. At run time, it uses the bounding box set operations such as union, intersection, difference, finding subset and superset relation to compute a set of disjoint bounding boxes from the set of bounding boxes identified at compile time. It also exploits the architectural capability provided by GPUs to perform fast transfers of rectangular (strided) regions of memory and hence performs all data transfers in terms of bounding boxes. BBMM uses these techniques to automatically allocate, and manage data required by applications (suitably tiled and parallelized for GPUs). This allows It to (1) allocate only as much data (or close to) as is required by computations running on each GPU, (2) efficiently track buffer allocations and hence, maximize data reuse across tiles and minimize the data transfer overhead, (3) and as a result, enable applications to maximize the utilization of the combined memory on multi-GPU machines. BBMM can work with any choice of parallelizing transformations, computation placement, and scheduling schemes, whether static or dynamic. Experiments run on a system with four GPUs with various scientific programs showed that BBMM is able to reduce data allocations on each GPU by up to 75% compared to current allocation schemes, yield at least 88% of the performance of hand-optimized Open CL codes and allows excellent weak scaling.

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-coeur 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-coeur, GPU et multi-GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des techniques d'équilibrage de charge basées sur le vol de données. Notre solution hybride 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-coeur. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes.