Optimal Embedding of Honeycomb networks into Hypercubes

Authors

Doina Bein, University of Nevada, Las VegasFollow
Wolfgang W. Bein, University of Nevada, Las VegasFollow
Natasa Brajkovska, University of Nevada, Las Vegas
Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

9-2004

Publication Title

Parallel Processing Letters

Volume

14

Issue

3/4

First page number:

367

Last page number:

375

Abstract

We present an optimal embedding of a honeycomb network (honeycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of when n is a power of two. When n is not a power of two, the expansion is , which we conjecture to be near optimal. For a honeycomb mesh, the dilation of the embedding is 1. For a honeycomb torus, the dilation can be as large as 2⌈log n⌉+3, because of the extra links connecting symmetric opposite nodes of degree two. A honeycomb network, built recursively using hexagon tessellation, is a multiprocessor interconnection network, and also a Cayley graph, and it is better than the planar mesh with the same number of nodes in terms of degree, diameter, number of links, and bisection width.

Keywords

Computer architecture; Computer networks; Hypercube networks (Computer networks); Parallel computers

Disciplines

Computer and Systems Architecture | Computer Engineering | Digital Circuits | Hardware Systems

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

Bein, D., Bein, W. W., Brajkovska, N., Latifi, S. (2004). Optimal Embedding of Honeycomb networks into Hypercubes. Parallel Processing Letters, 14(3/4), 367-375.