Title
Optimal embedding of honeycomb networks into hypercubes
Document Type
Article
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
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.
Citation Information
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.