Title

Optimal embedding of honeycomb networks into hypercubes

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.

Identifier

DOI: 10.1142/S0129626404001957

UNLV article access

Search your library

Share

COinS