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 Algebraic Specification of Interconnection Network Relationships



next up previous contents
Next: Algebraic Specification of Up: Jonathan L. Gross Previous: Jonathan L. Gross

Algebraic Specification of Interconnection Network Relationships

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.



Sabah S. al-Binali
Fri Sep 22 16:39:42 EDT 1995