Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!hubcap!bjornl
From: bjornl@tds.kth.se (Bj|rn Lisper)
Newsgroups: comp.parallel
Subject: Re: any mesh algorithms use end-around connections?
Message-ID: <5560@hubcap.clemson.edu>
Date: 22 May 89 20:44:43 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 17
Approved: parallel@hubcap.clemson.edu

In article <5528@hubcap.clemson.edu> danl@cbnewsc.ATT.COM (daniel.r.levy)
writes:
   Recently I discussed 2-D and 3-D mesh architectures with a professor of a
   class in advanced computer architecture that I am taking.  Prof says that
   end-around connections (outer edge to outer edge, face plane to face plane)
   aren't used in the solution algorithms of any problem he knows of which are
   suited to solution on such meshes.  Can anyone suggest any examples to the
   contrary?

Some systolic implementations of Warshall's algorithm for computing the
transitive closure of a binary relation use wraparound connections. Note,
however, that the original Warshall's algorithm can be modified as to remove
the need for these connections: see for instance Kung, Lo, Lewis: "Optimal
Systolic Design for the Transitive Closure and the Shortest Path Problems",
IEEE Trans. Comput. vol C-36, no 5, May 1987, pp. 603-614.

Bjorn Lisper