Treffer: Partial Evaluation of Dense Code on Sparse Structures

Most HPC computations process sparse tensors. The resulting code ishighly dynamic, which makes code optimization quite challenging. Oneway is to start from the original dense specification, which isusually much more regular and ready to be optimized thanks tostate-of-the-art program optimization algorithms. Then, to specializethat code on the sparse input structure. In this paper, we propose anovel approach to apply that specialization. The key ingredient of ouralgorithm is the transitive closure of affine relation, for whichefficient and accurate heuristics exist. Experimental evaluation showsthe effectiveness of our approach.
La plupart des calculs HPC manipulent des tenseurs creux. Le code résultant est très dynamique, ce qui rend l'optimisation du code assez difficile. Une méthode est de partir de la spécification dense originale, qui est généralement beaucoup plus régulière et se prête bien mieux à l'optimisation de code; et ensuite, de spécialiser le code sur la structure d'entrée. Dans ce rapport, nous proposons une nouvelle approche pour appliquer cette spécialisation. L'ingrédient clé de notre algorithme est la fermeture transitive d'une relation affine, pour laquelle des heuristiques efficaces et précises existent. L'évaluation expérimentale confirme l'efficacité de notre approche.