In a hypercube, e-cube routing (or dimension-order routing) routes a message
from source to destination by traversing the differing dimensions in
right-to-left order (or left-to-right: the specific order is irrelevant, as long
as all routers use the same ordering). Thus if a message is going from 11001
to 10010, the differing dimensions are shown by the xor, 01011, and so the e-cube
routing path would be 11001 to 11000 to 11010 to 10010.
Since e-cube routing is the routing typically supplied in commercial hypercubes,
for optimal performance a user would prefer to embed a task graph so that
different communication links between tasks are not mapped onto the same
physical link.
An e-circuit embedding of a task graph G into a hypercube
Q is a
1-1 mapping of the vertices of G into the vertices of Q, such
that when the edges of G are mapped to the paths that the e-cube
router would use to route between the two endpoints, no two
paths share a link.
All edges of the hypercube are viewed as being 2 links, one in
each direction.
Each edge of G is mapped to 2 different paths of the hypercube,
corresponding to the two directions of the edge.
Note that in any path with distance greater than 1, the e-cube
router uses different edges of the hypercube for the two directions.
Theorem:
Let G=(V,E) be a connected undirected graph.
Then G can be e-cube embedded into a hypercube if and only if there
is a labeling L:E-> {1,2,...} such that
- For every cycle C of G, the smallest label that occurs
on C appears an even number of times.
- For every vertex v of G, no two edges incident on v
have the same label.
Further, if G has n vertices and labels {1,...,d} are
used, then G can be embedded into a hypercube of dimension
2d+2 ceiling(lg n)
Keywords:
hypercube computer, graph embedding, e-cube routing,
dimension order, link contention, graph theory, computer science,
parallel computing, parallel computer architecture
