📄 http:^^www.cs.columbia.edu^info^research-guide^html^node22.html

📁 This data set contains WWW-pages collected from computer science departments of various universities
💻 HTML
字号:
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

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HEAD><TITLE> Algebraic Specification of Interconnection NetworkRelationships</TITLE></HEAD><BODY><meta name="description" value=" Algebraic Specification of Interconnection NetworkRelationships"><meta name="keywords" value="main"><meta name="resource-type" value="document"><meta name="distribution" value="global"><P> <BR> <HR><!WA0><A NAME=tex2html337 HREF="http://www.cs.columbia.edu/info/research-guide/html/node23.html"><!WA1><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//next_motif.gif"></A>   <!WA2><A NAME=tex2html335 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"><!WA3><IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//up_motif.gif"></A>   <!WA4><A NAME=tex2html329 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"><!WA5><IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//previous_motif.gif"></A>   <!WA6><A NAME=tex2html339 HREF="http://www.cs.columbia.edu/info/research-guide/html/node1.html"><!WA7><IMG ALIGN=BOTTOM ALT="contents" SRC="http://www.cs.columbia.edu/info/research-guide/html/icons//contents_motif.gif"></A>      <BR><B> Next:</B> <!WA8><A NAME=tex2html338 HREF="http://www.cs.columbia.edu/info/research-guide/html/node23.html"> Algebraic Specification of </A><B>Up:</B> <!WA9><A NAME=tex2html336 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"> Jonathan L. Gross</A><B> Previous:</B> <!WA10><A NAME=tex2html330 HREF="http://www.cs.columbia.edu/info/research-guide/html/node21.html"> Jonathan L. Gross</A><BR> <HR> <P><H2><A NAME=SECTION000101000000000000000> Algebraic Specification of Interconnection NetworkRelationships</A></H2><P>When a distributed algorithm is designed for one parallel architecture (the``guest'') and it is to be executed on another (the ``host''), the twoarchitectures are modeled as interconnection networks, and the guest ismapped into the host.  Trees, meshes, and hypercubes are readily specifiedand mapped by undergraduate-level mathematical methods.  Hypercubevariations, such as cube-connected-cycle graphs, wrapped butterfly graphs,shuffle-exchange graphs, and deBruijn graphs are specified as Cayley graphsand group-action graphs (``GAG's'') for wreath products of cyclic groups.(See Rosenberg [Ro90] and Leighton [Le92].)<P>The <i> voltage graph</i> construction (see Gross and Tucker [GrTu87]), whichis my combinatorial abstraction of a Riemann surface, was originallyintroduced in order to simplify the specification of networks and theirlayouts on surfaces.  More recently, my work has been concerned withextending the algebraic specification of the networks to the representationof guest-host relationships between two networks, by modeling it as avoltage graph morphism, that is, as a mapping from one voltage graph toanother.<P>For one example of an application, my topological techniques and algebraicformulas for measuring load, congestion, and dilation of guest-hostrelationships readily reduce the representation of a cube-connected cyclenetwork into a wrapped butterfly network to specifying a graph functionfrom a circular ladder to a doubled cycle.  For another, these techniquesand formulas reduce the representation of a shuffle exchange network in adeBruijn network to specifying a graph function from the bouquet<!WA11><IMG  ALIGN=MIDDLE ALT="" SRC="http://www.cs.columbia.edu/info/research-guide/html/img5.gif"> to itself.  The <i> bouquet</i> <!WA12><IMG  ALIGN=MIDDLE ALT="" SRC="http://www.cs.columbia.edu/info/research-guide/html/img6.gif"> is defined tobe the graph with one vertex and <b>n</b> self-loops.<P>I am presently working on voltage graph morphism lifting in collaborationwith Jianer Chen (of Texas A&amp;M).  David Seidman (of IBM and EE Dept.) hasalso begun work with me on this topic.<P><P><P><BR> <HR><P><ADDRESS><I>Sabah S. al-Binali <BR>Fri Sep 22 16:39:42 EDT 1995</I></ADDRESS></BODY>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -