CGM-based parallel solutions for a class of non-serial polyadic dynamic-programming problems

Résumé

We are interested in the parallelization of a class of non-serial polyadic dynamic-programming problems in this thesis. These problems are characterized by a strong dependency between subproblems. To design efficient and portable parallel solutions to solve these problems, the CGM (coarse-grained multicomputer) model is the suitable choice because of its simplicity and its compatibility with most supercomputers. A CGM-based parallel algorithm is a succession of computation and communication rounds. The solutions proposed in the literature give the end-user the possibility of minimizing the number of communication rounds or balancing the load between processors because both objectives are conflicting. Moreover, their main drawback is to foster the latency time of processors, which accounts for most of the global communication time. In this work, we propose an irregular partitioning technique of the dependency graph to tackle these conflicting objectives. It consists in subdividing the dependency graph into subgraphs (or blocks) of variable size. It ensures that the blocks of the first steps (or diagonals) are of large sizes to minimize the number of communication rounds. Thereafter, it decreases these sizes along the diagonals to increase the number of blocks in these diagonals and allow processors to stay active as long as possible. These blocks are fairly distributed among processors to minimize their idle time and balance the load between them. Nevertheless, this strategy induces a high latency time of processors. Indeed, varying the blocks' sizes does not enable them to start evaluating some blocks as soon as the data they need are available. To get over this shortcoming, we propose strategies to evaluate a block as a sequence of computation and communication steps of a set of small-size blocks. The experimental results obtained show a significant performance gain compared to the most efficient solutions proposed in the literature.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 3

Téléchargements : 0