Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!tut.cis.ohio-state.edu!att!emory!hubcap!alan
From: alan@msc.edu (Alan Klietz)
Newsgroups: comp.parallel
Subject: Re: CM-2 SIMD question
Message-ID: <12530@hubcap.clemson.edu>
Date: 9 Jan 91 12:44:02 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 46
Approved: parallel@hubcap.clemson.edu

>From: john%ghostwheel.unm.edu@ariel.unm.edu (John Prentice)
>
>I have a SIMD question motivated by the CM-2.  We are doing finite
>difference calculations on a simple structured grid.  It is trivial to
>port our code to the CM-2 to do the difference stencil since it is
>inherently a SIMD type problem.  However, different nodes in our mesh
>use different equations of state.  Some are tabular, some are
>analytic, some are iterative.  Clearly you can't perform all these
>calculations in lock step.  So, I assume we have to turn off all processors
>except those using a specific equation of state, do the EOS calculations for 
>those nodes, and then turn those processors off and turn on those for the next
>EOS, etc... until we have exhausted all the types of EOS we need.  Is there
>a better way to do this?

There a few of approaches you can take, depending on how much rewriting of 
your code you willing to do.

First, you could use a more general solution method which may be
more expensive to solve but is applicable to all nodes.  For example,
I wrote a ray tracer on the CM-2 that originally iterated over each type of
surface (cone, sphere, plane, etc.)  I discovered that it was faster
to just solve the general 3-D quartic equation for all surfaces rather than
using a n equations for each special surface.  In general, you could
start from physical principles and derive a new equation or you could do
it the brute force way: collect all terms in each (original) expression 
into a single large polynomial where various coefficients are zero
on different processors.

Second, you could use the voting trick that Frye and Myczkowski
used to solve Conway's blocks-in-a-box puzzle.  It only works
if your states are dynamic (perhaps not suitable in your case,
but it's a neat concept anyway :-).  Each processor 'votes' for the state
it would like to see executed and whichever state wins a plurality
of votes wins.  Some of the winning processors change state as a
result, and the cycle is repeated.  Watch out for deadlocks, though.

Third, you could wait a couple years for MSIMD machines to come out :-).

--
Alan E. Klietz
Minnesota Supercomputer Center, Inc.
1200 Washington Avenue South
Minneapolis, MN  55415
Ph: +1 612 626 1734    Internet: alan@msc.edu
				"If only the CM-2 acted more like a Cray 
				 and a Cray acted more like the CM-2."