Improved Communication Schedules with Buffers
Abstract
We consider the multimessage multicasting over the n processor complete (or fully connected) static network when there are l incoming (message) buffers on every processor. We present an efficient algorithm to route the messages for every degree d problem instance in d2/l + l - 1 total communication rounds, where d is the maximum number of messages that each processor may send (or receive). Our algorithm takes linear time with respect to the input length, i.e. O(n + q) where q is the total number of messages that all processors must receive. For l = d we present a lower bound for the total communication time. The lower bound matches the upper bound for the schedules generated by our algorithm. For convenience we assume that the network is completely connected. However, it is important to note that each communication round can be automatically translated into one communication round for processors interconnected via a replication network followed by a permutation network (e.g., two adjacent Benes networks), because in these networks all possible one-to-many communications can be performed in a single communication round.
A preliminary version of this paper appeared in the Proceedings of the IASTED PDCS'05 Conference.
References
T. F. Gonzalez , MultiMessage Multicasting, Proceedings The Irregular'96 Workshop1117,LNCS (Springer, 1996) pp. 217–228. Google Scholar- J. of Parallel and Distributed Computing 55(2), 215 (1998), DOI: 10.1006/jpdc.1998.1500. Crossref, ISI, Google Scholar
- J. of Systems Architecture 43(9), (1997). Google Scholar
- Algorithmica 29, 511 (2001), DOI: 10.1007/s004530010072. Crossref, ISI, Google Scholar
- Journal of the ACM 23(4), 665 (1976), DOI: 10.1145/321978.321985. Crossref, ISI, Google Scholar
- SIAM J. on Computing 14(3), 744 (1985). Crossref, ISI, Google Scholar
- SIAM J. on Computing 19(2), 222 (1990), DOI: 10.1137/0219015. Crossref, ISI, Google Scholar
- Algorithmica 3, 223 (1988), DOI: 10.1007/BF01762116. Crossref, ISI, Google Scholar
- IEEE Transactions on Information Theory 34(5), 910 (1988), DOI: 10.1109/18.21215. Crossref, ISI, Google Scholar
- IEEE Transactions on Communications 30(11), 2475 (1982), DOI: 10.1109/TCOM.1982.1095433. Crossref, ISI, Google Scholar
- Networks 22, 563 (1992), DOI: 10.1002/net.3230220606. Crossref, ISI, Google Scholar
- Nordic Journal on Computing 5, 196 (1998). ISI, Google Scholar
- Journal of Interconnection Networks 1(4), 303 (2000), DOI: 10.1142/S0219265900000184. Link, Google Scholar
- International Journal of Foundations of Computer Science 12(6), 791 (2001), DOI: 10.1142/S0129054101000874. Link, Google Scholar
- Optical Networks 3(1), 34 (2002). Google Scholar


