Embedding Criterion for e-Cube Routing
In preparation - results first announced Spring 1991

Quentin F. Stout
EECS Department, University of Michigan

Abstract: 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

1. For every cycle C of G, the smallest label that occurs on C appears an even number of times.
2. 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

 Graph Theory: overview of my work papers Parallel Computing: overview of my work papers