Sufficient Conditions for Optimal Multicast Communication

In this paper, we give a general technique for computing optimal multicast calling schedules in any multiprocessor system that utilizes a direct network interconnection structure as long as a few simple conditions are satisfied. Since almost any real system will satisfy these conditions, this result essentially means that multicast can always be performed in dlog(d+1)e phases where d is the number of multicast destinations. In particular, previous results on optimal multicast algorithms in specific direct network topologies [1, 2, 3] are simply corollaries of our result. 1 Introduction Multicast communication has been studied under a wide variety of models for parallel and distributed computing [1, 2, 3, 4, 5, 6, 7, 8]. In this paper, we present sufficient conditions that allow optimal time unicast-based multicast in direct network systems that employ a cut-through routing technique such as wormhole routing. This result provides a general technique for constructing optimal time mu..