Task Ordering in Linear Tiles.

In this report we address the issue of loop tiling to minimize the completion time of the loop when executed on multicomputers. We remove the restriction of atomicity of tiles and internal parallelism within tiles is exploited by overlapping computation with communication. The effectiveness of tiling is then critically dependent on the execution order of tasks within a tile. In this paper we present a theoretical framework based on equivalence classes that provides an optimal task ordering under assumptions of constant and different permutations of tasks in individual tiles. Our framework is able to handle constant but compile-time unknown dependences by generating optimal task permutations at run-time and results in significantly lower loop completion times. Our solution is an improvement over previous approaches and is optimal for all problem instances. We also propose efficient algorithms that provide the optimal solution. The framework has been implemented as an optimization pass in the SUIF compiler and has been tested on distributed and shared memory systems using a message passing model. We show that the performance improvement over previous results is substantial.Étant donné un nid de boucles 1-dimensionnel avec des dépendances uniformes et une distribution regulière des tâches sur une chaîne de processeurs. Nous adressons ici le problème du réordonnancement des tâches à l'intérieur même de chaque tuile afin de pipeliner les communications. En fait, nous cherchons à utiliser le parallélisme interne à chaque tuile afin de réduire la latence dans une direction critique ; ces résultats pouvant s'appliquer à des nids de boucles multidirectionnels. Les approches précedantes se tenant à chercher une permutation constante des tâches à l'intérieur de chaque tuiles, nous avons d'abord résolu se problème de manière optimale (algorithme 3) puis comparé cet algorithme à un algorithme utilisant des permutations non constantes (algorithme 4). La construction de l'algorithme 3 à nécessité la mise en oeuvre d'une formalisation mathématiques du problème suivit de preuves substentielles. C'est ce qui constitue le corps de ce rapport. Si clairement dans le cas 1-directionnel nos résultats montrent la supériorité de l'algorithme 4, certains paramètres laissent à penser que dans les dimensions supérieures, un algorithme de type 3 serait peut être plus efficace...}