Path: utzoo!attcan!uunet!lll-winken!xanth!ukma!gatech!hubcap!D
From: dominic@etive.edinburgh.ac.uk (D Prior)
Newsgroups: comp.parallel
Subject: Re: any mesh algorithms use end-around connections?
Message-ID: <5553@hubcap.clemson.edu>
Date: 21 May 89 23:45:59 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 27
Approved: parallel@hubcap.clemson.edu

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.