Efficient broadcast on hypercubes with wormhole and e-cube routings

Ching Tien Ho; Ming Yang Kao

doi:10.1142/S0129626495000199

Efficient broadcast on hypercubes with wormhole and e-cube routings

Ching Tien Ho^*, Ming Yang Kao

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We consider the problem of broadcasting on an n-dimensional hypercube with worm-hole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log₂(n + 1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.

Original language	English (US)
Pages (from-to)	213-222
Number of pages	10
Journal	Parallel Processing Letters
Volume	5
Issue number	2
DOIs	https://doi.org/10.1142/S0129626495000199
State	Published - Jan 1 1995

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1142/S0129626495000199

Cite this

@article{cddc3ebd90d945a7a60a3a91538e6e47,

title = "Efficient broadcast on hypercubes with wormhole and e-cube routings",

abstract = "We consider the problem of broadcasting on an n-dimensional hypercube with worm-hole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log2(n + 1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.",

author = "Ho, {Ching Tien} and Kao, {Ming Yang}",

year = "1995",

month = jan,

day = "1",

doi = "10.1142/S0129626495000199",

language = "English (US)",

volume = "5",

pages = "213--222",

journal = "Parallel Processing Letters",

issn = "0129-6264",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "2",

}

TY - JOUR

T1 - Efficient broadcast on hypercubes with wormhole and e-cube routings

AU - Ho, Ching Tien

AU - Kao, Ming Yang

PY - 1995/1/1

Y1 - 1995/1/1

N2 - We consider the problem of broadcasting on an n-dimensional hypercube with worm-hole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log2(n + 1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.

AB - We consider the problem of broadcasting on an n-dimensional hypercube with worm-hole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log2(n + 1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.

UR - http://www.scopus.com/inward/record.url?scp=0029312005&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029312005&partnerID=8YFLogxK

U2 - 10.1142/S0129626495000199

DO - 10.1142/S0129626495000199

M3 - Article

AN - SCOPUS:0029312005

SN - 0129-6264

VL - 5

SP - 213

EP - 222

JO - Parallel Processing Letters

JF - Parallel Processing Letters

IS - 2

ER -

Efficient broadcast on hypercubes with wormhole and e-cube routings

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this