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
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.