Optimal Deadlock-free Path-based Multicast Algorithms in Meshes

Multicasting is an information dissemination problem which consists, for a node of a distributed memory parallel computer, of sending the same message to an arbitrary subset of nodes. The two major criteria to be considered in multicast communication are \textsl{traffic} (number of channels used) and \textsl{latency} (time required). In this paper, we proposed new polynomial algorithms giving optimal solutions in terms of traffic or latency for a mesh network using \textsl{wormhole} routing and \textsl{path-based} facility. All the algorithms are shown to be deadlock-free. Moreover, we generalize our algorithms to arbitrary Hamiltonian graphs.Une diffusion partielle est une opération de communication sur une machine parallèle à mémoire distribuée dans laquelle un processeur veut envoyer un même message à un sous groupe de processeurs. Les deux critères dévaluation couramment employés sont le traffic (nombre de canaux utilisés) et la latence (temps requis). Dans ce rapport, nous proposons de nouveaux algorithmes polynomiaux calculant une solution optimale soit en terme de traffic, soit en terme de latence. Nous présentons ces algorithmes dans le cas d'une grille avec comme hypothèse que le mode de routage mis en {\oe}uvre est wormhole et utilise une facilité de routage nommée path-based. Tous les algorithmes sont sans interblocage. Nous généralisons nos algorithmes à la classe des graphes hamiltoniens