Date: Wed, 15 Jan 1997 00:10:44 GMT Server: Apache/1.1.1 Content-type: text/html Content-length: 3671 Last-modified: Fri, 05 Apr 1996 18:19:03 GMT
When a distributed algorithm is designed for one parallel architecture (the ``guest'') and it is to be executed on another (the ``host''), the two architectures are modeled as interconnection networks, and the guest is mapped into the host. Trees, meshes, and hypercubes are readily specified and mapped by undergraduate-level mathematical methods. Hypercube variations, such as cube-connected-cycle graphs, wrapped butterfly graphs, shuffle-exchange graphs, and deBruijn graphs are specified as Cayley graphs and group-action graphs (``GAG's'') for wreath products of cyclic groups. (See Rosenberg [Ro90] and Leighton [Le92].)
The voltage graph construction (see Gross and Tucker [GrTu87]), which is my combinatorial abstraction of a Riemann surface, was originally introduced in order to simplify the specification of networks and their layouts on surfaces. More recently, my work has been concerned with extending the algebraic specification of the networks to the representation of guest-host relationships between two networks, by modeling it as a voltage graph morphism, that is, as a mapping from one voltage graph to another.
For one example of an application, my topological techniques and algebraic
formulas for measuring load, congestion, and dilation of guest-host
relationships readily reduce the representation of a cube-connected cycle
network into a wrapped butterfly network to specifying a graph function
from a circular ladder to a doubled cycle. For another, these techniques
and formulas reduce the representation of a shuffle exchange network in a
deBruijn network to specifying a graph function from the bouquet
to itself. The bouquet
is defined to
be the graph with one vertex and n self-loops.
I am presently working on voltage graph morphism lifting in collaboration with Jianer Chen (of Texas A&M). David Seidman (of IBM and EE Dept.) has also begun work with me on this topic.