Low Expansion Packings and Embeddings of Hypercubes into Star Graphs: A Performance-oriented Approach

Authors

Marcelo Moraes de Azevedo, Tandem Computers, Inc.
Nader Bagherzadeh, University of California, IrvineFollow
Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

3-1998

Publication Title

Transactions on Parallel and Distributed Systems

Volume

9

First page number:

261

Last page number:

274

Abstract

We discuss the problem of packing hypercubes into an n-dimensional star graph S(n), which consists of embedding a disjoint union of hypercubes U into S(n) with load one. Hypercubes in U have from [n/2] to (n+1)·[log₂ n]-2([lod₂n]+1)+2 dimensions, i.e., they can be as large as any hypercube which can be embedded with dilation at most four into S(n). We show that U can be embedded into S(n) with optimal expansion, which contrasts with the growing expansion ratios of previously known techniques. We employ several performance metrics to show that, with our techniques, a star graph can efficiently execute heterogeneous workloads containing hypercube, mesh, and star graph algorithms. The characterization of our packings includes some important metrics which have not been addressed by previous research (namely, average dilation, average congestion, and congestion). Our packings consistently produce small average congestion and average dilation, which indicates that the induced communication slowdown is also small. We consider several combinations of node mapping functions and routing algorithms in S(n), and obtain their corresponding performance metrics using either mathematical analysis or computer simulation

Keywords

Computer algorithms; Computer networks; Hypercube networks (Computer networks); Routing protocols (Computer network protocols)

Disciplines

Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Moraes de Azevedo, M., Bagherzadeh, N., Latifi, S. (1998). Low Expansion Packings and Embeddings of Hypercubes into Star Graphs: A Performance-oriented Approach. Transactions on Parallel and Distributed Systems, 9 261-274.