Efficient Load-balancing and Communication Overlap in Parallel Shear-Warp Algorithm on a Cluster of PCs

(eng) In the medical field, volume rendering provides good quality 3D visualizations but is still not enough interactive for a day-to-day practice. The most efficient sequential algorithm is the shear-warp algorithm. It renders up to 10 images per second for a small dataset. The goal of this report is to present an efficient parallel implementation of the shear-warp algorithm for a distributed memory architecture, a cluster of PCs connected with a high speed network. This highly irregular algorithm led us to implement a dynamic load balancing algorithm. Furthermore, to reduce the overhead due to data redistribution, we overlap communications with computations using MPI's asynchronous communications. Using a good load-balancing and communication overlap, our implementation generates real-time 3D medical images with a good quality and a high resolution.(fre) Dans le domaine médical, le rendu volumique offre des visualisations 3D de bonne qualité mais il n'est pas suffisement intéractif pour une utilisation quotidienne. L'algorithme séquentiel le plus efficace est l'algorithme du Shear-Warp. Il peut rendre jusqu'à 10 images par seconde pour un petit jeu de données. Le but de ce rapport est de présenter une implémentation parallèle efficace de l'algorithme du Shear-Warp pour une architecture à mémoire distribuée, un cluster de PC connectés avec un réseau rapide. Cet algorithme très irrégulier nous a conduit à implémenter un algorithme d'équilibrage des charges dynamique. De plus, afin de réduire le surcoût des redistributions, nous recouvrons les communications avec les calculs en utilisant les communications asynchrones de MPI. Avec l'équilibrage des charges dynamique et le recouvrement des communications, notre implémentation génère des images médicales 3D en temps réel avec une bonne qualité et une haute résolution