Spanning Graphs for Optimum Broadcasting and Personalized Communication in Hypercubes
1989 (English)In: I.E.E.E. transactions on computers (Print), ISSN 0018-9340, E-ISSN 1557-9956, Vol. 38, no 9, 1249-1268 p.Article in journal (Refereed) Published
Four different communication problems are addressed in Booleann-cube configured multiprocessors: (1) one-to-all broadcasting: distribution of common data from a single source to all other nodes; (2) one-to-all personalized communication: a single node sending unique data to all other nodes; (3) all-to-all broadcasting: distribution of common data from each node to all other nodes; and (4) all-to-all personalized communication: each node sending a unique piece of information to every other node. Three communication graphs (spanning trees) for the Booleann-cube are proposed for the routing, and scheduling disciplines provably optimum within a small constant factor are proposed. With appropriate scheduling and concurrent communication on all ports of every processor, routings based on these two communication graphs offer a speedup of up ton/2, and O(√n) over the routings based on the spanning binomial tree for cases (2)-(4) respectively. All three spanning trees offer optimal communication times for cases (2)-(4) and concurrent communication on all ports of every processor. Timing models and complexity analysis are verified by experiments on a Boolean-cube-configured multiprocessor
Place, publisher, year, edition, pages
1989. Vol. 38, no 9, 1249-1268 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-91063DOI: 10.1109/12.29465OAI: oai:DiVA.org:kth-91063DiVA: diva2:507915
NR 201408052012-03-062012-03-06Bibliographically approved