Algebraic foundations and broadcasting algorithms for wormhole-routed all-port tori

San Yuan Wang, Yu-Chee Tseng

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 the 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 3D 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.

Original languageEnglish
Pages (from-to)246-258
Number of pages13
JournalIEEE Transactions on Computers
Volume49
Issue number3
DOIs
StatePublished - 3 Dec 2000

Fingerprint Dive into the research topics of 'Algebraic foundations and broadcasting algorithms for wormhole-routed all-port tori'. Together they form a unique fingerprint.

Cite this