danl@cbnewsc.ATT.COM (daniel.r.levy) (05/20/89)
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? I wonder why the ILLIAC-IV bothered to put in the end-around connections, if they aren't of any practical use (prof says they were never used). -- Dan'l Levy UNIX(R) mail: att!ttbcad!levy, att!cbnewsc!danl AT&T Bell Laboratories 5555 West Touhy Avenue Any opinions expressed in the message above are Skokie, Illinois 60077 mine, and not necessarily AT&T's.
josh@klaatu.rutgers.edu (J Storrs Hall) (05/20/89)
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...
Dan'l Levy UNIX(R) mail: att!ttbcad!levy, att!cbnewsc!danl
Assuming we're talking about the same thing, we use these connections
on the DAP regularly. To be specific: consider one row or column of
the mesh as a shift register; the connections which allow you to do a
recirculating shift.
If you have a mesh-shaped problem bigger than the machine, there are
two major ways to cut it up:
(P[i,j]=processor, D[i,j]=datum, kxk processors, nxn data)
A: P[i%k,j%k] gets D[i,j]
B: P[i/k,j/k] gets D[i,j]
The DAP's hardware mapping to the frame buffer "encourages" you to use
A. In this case the end-around connections are extremely useful.
--JoSHdominic@etive.edinburgh.ac.uk (D Prior) (05/22/89)
In article <5528@hubcap.clemson.edu> danl@cbnewsc.ATT.COM (daniel.r.levy) writes: >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? The `scatter decomposition' requires meshes to have wrap-around. In a physical simulation, the responsibility for updating data is often divided between the processors (`geometric parallelism') but giving one chunk out to each processor can give bad load-balancing. A popular way round this is `scatter decomposition' in which each processor is given responsibility for several smaller chunks. Clearly processors will need to talk to all processors which control chunks adjacent to their own chunks. For example, the nine processors A,B,C,D,E,F,G,H,I could split 2-D space like this: ABCABCABCABC ... DEFDEFDEFDEF ... GHIGHIGHIGHI ... ABCABCABCABC ... DEFDEFDEFDEF ... GHIGHIGHIGHI ... ... and then each processor will need to be connected to four others. A 3 by 3 torus.
bjornl@tds.kth.se (Bj|rn Lisper) (05/23/89)
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