A dilated-diagonal-based scheme for broadcast in a wormhole-routed 2D torus

Yu-Chee Tseng*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    17 Scopus citations

    Abstract

    The one-to-all broadcast is the most primary operation in a multicomputer network. In this paper, we consider this problem in a wormhole-routed 2D torus network which provides the dimension-ordered routing and all-port communication capability. With the distance-insensitive characteristic of wormhole routing, we model the broadcast as a sequence of communication phases. We propose a novel scheme to solve this problem. The scheme requires at most two communication phases more than the optimal number of phases when the torus is square, or at most four or five communication phases more than optimum when the torus is nonsquare. The best known results, as compared to ours, can only be applied to square tori of very restricted network sizes and either rely on an undesirable non-dimension-ordered routing or require more numbers of phases.

    Original languageEnglish
    Pages (from-to)947-952
    Number of pages6
    JournalIEEE Transactions on Computers
    Volume46
    Issue number8
    DOIs
    StatePublished - 1 Dec 1997

    Keywords

    • Collective communication
    • Dimension-ordered (or e-cube) routing
    • Interconnection network
    • One-to-all broadcast
    • Parallel computing
    • Torus
    • Wormhole routing

    Fingerprint

    Dive into the research topics of 'A dilated-diagonal-based scheme for broadcast in a wormhole-routed 2D torus'. Together they form a unique fingerprint.

    Cite this