Mapping Gaussian belief propagation on the graphics processing unit

With the introduction of programmable graphical processing units (GPU) in the last decade, Heterogeneous computing systems have become more popular. It has been predicted that by leveraging the power of the GPU's many cores, many applications can experience improved performance in the near future. However porting applications to the GPU in most cases cannot be automated due to the GPU's unique architecture. Mapping problems on the GPU has been researched in many diverse fields. Many problems in science and engineering come down to solving sparse systems of linear equations. Nevertheless conventional iterative solvers are not feasible tools for large sparse systems. One of the novel iterative solvers proposed in recent literature is the Gaussian belief propagation (GaBP) method. This method uses recursive message updates on a graphical model. In this work a variant of GaBP algorithm was implemented on the GPU. The implementation was successfully tested with FEM (finite element method) data. The parallel implementations achieved up to 4× improvement in execution time, compared to the serial CPU implementation.Avec l'introduction d'unités de traitement graphiques programmables (GPU) durant la dernière décennie, les systèmes informatiques hétérogènes sont devenus plus populaires. On pense qu'en exploitant la puissance des nombreux cœurs du GPU, de nombreuses applications pourront bénéficier de meilleures performances dans un avenir rapproché. Cependant, dans la plupart des cas le fait de porter des applications vers le GPU ne peut pas être automatisé à cause de l'architecture unique du GPU. Les problèmes de mappage sur le GPU ont été l'objet de recherches dans de nombreux domaines. Beaucoup de problèmes en science et en ingénierie consistent simplement à résoudre systèmes d'équations linéaires creux. Étant donné que les systèmes creux qui croissent à l'aide de solveurs itératifs classiques ne seront pas réalisables, un des nouveaux solveurs itératifs proposés dans la littérature récente est la méthode de croyance des propagations gaussiennes (GABP). Cette méthode utilise des messages de mise à jour récursifs sur un modèle graphique. Dans ce travail, une variante de l'algorithme GABP fut mise en place sur le GPU. La mise en œuvre a été testée avec succès avec des données FEM (méthode des éléments finis). Les implémentations parallèles ont atteint une amélioration du temps d'exécution jusqu'à 4 × par rapport à l'implémentation de série du CPU