Deadlock-Free Broadcast Routing in Dragonfly Networks without Virtual Channels

Abstract

A new deadlock-free unicast-based broadcast scheme is proposed based on a new routing scheme called minus-first routing. Minus-first routing is a partially adaptive routing scheme in dragonfly networks without any virtual channels. The main goals of the broadcast schemes are to minimize the total delivery time, and any router does not receive any message more than once. No channel competition is introduced. Two different broadcast schemes are proposed: (1) the group-first, and (2) the router-first. It is shown that unicast-based broadcast schemes are necessary to avoid deadlocks at the consumption channels. The group-first broadcast scheme delivers a message to all groups as early as possible; and the router-first scheme minimizes the number of unicast steps to traverse global links. To our knowledge, the method in this paper is the first collective communication work for dragonfly networks in the literature. Simulation results are presented to evaluate the proposed unicast-based broadcast schemes.