Abstract | ||
---|---|---|
The one-to-all broadcast is the most primary collective communication pattern in a multicomputer network. We consider this problem in a wormhole-routed torus which uses all-port and dimension-ordered routing model. We derive our routing algorithms based on the concept of “span of vector spaces” in linear algebra. For instance, in a 3-D torus, the nodes receiving the broadcast message will be “spanned” from the source node to a line of nodes, to a plane of nodes, and then to a cube of nodes. Our results require at most 2(k-1) steps more than the optimal number of steps for any square k-D torus. Existing results, as compared to ours, can only be applied to tori of very restricted dimensions or sizes, and either rely on an undesirable non-dimension-ordered routing or require more numbers of steps |
Year | DOI | Venue |
---|---|---|
2000 | 10.1109/12.841128 | IEEE Transactions on Computers |
Keywords | DocType | Volume |
broadcasting algorithms,primary collective communication pattern,wormhole-routed all-port tori,broadcast message,3-d torus,scheduling,multiprocessor interconnection networks,primary collective,one-to-all broadcast,undesirable non-dimension-ordered routing,linear algebra,wormhole-routed torus,dimension-ordered routing model,algebraic foundations,multicomputer network,communication pattern,performance evaluation,d torus,all-port,dimension-ordered routing,optimal number,vector space,routing,vectors,computer science,broadcasting | Journal | 49 |
Issue | ISSN | Citations |
3 | 0018-9340 | 14 |
PageRank | References | Authors |
0.80 | 16 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
San-Yuan Wang | 1 | 100 | 7.99 |
Yu-Chee Tseng | 2 | 6603 | 639.67 |