From: Douglas Meyer <dougger@ERC.MsState.Edu>
Subject: Analysis of Parallel Algorithms/Programs (PVM vs Pablo vs ??)
Organization: Clemson University
Date: Wed, 26 Aug 1992 19:31:54 GMT

[We are having a hard time getting this particular item through
the network. It has been sent two previous times. If you've
seen this one before and your last name starts with L-N, please
do a quick follow-up to let me know. Steve]

I'm currently trying to find simulation/analysis tools which will
allow parallel algorithm/program developers cull through a number of
solution options without:

  1.  having to write codes for real machines
  2.  having to write complete codes (ie. to shorted the culling 
         process, it would be preferable to write skeletal codes
         which describe the general communications and computation
         behaviors)

The focus is intended to be a rough, qualitative analysis of
"skeletal" programs (programs that do not have the mathematical guts,
but rather approximate the guts with a library function call which
simply indicates how many floating point operations would be done in
critical sections, etc.).  These analyses are only required to account
for very basic, first-order effects, and would probably only permit
the engineer to eliminate those algorithms that are blatantly bad.
Metrics of interest would be things like CPU time, "Real" time, and
average message latency.  The focus is on the SPMD paradigm, with
message passing constrained to a family of "global" or "systematic"
communications patterns (eg. everybody send to the right, everybody
broadcast, global sum, etc. such as is found in the Intel iPSC
library).

As I'm sure you have determined, what we are talking about is modeling
a parallel machine in such a manner that the algorithm (in the form of
skeletal code) being analyzed can be "executed" on that model, and
performance information can then be extracted.  I suppose this would
fall into the broad catagory of synthetic modeling.

So you can see, that these answers are not terribly detailed, and the
people running this project don't want detailed answers.. just answers
that provide general guidance.

------------------ End of description---------------------

I am convinced, through the little bit of reading and research I've
done in the last week that there are a fair number of tools already
developed and reasonably mature.  PVM and HeNCE clearly are for
running complete parallel codes; Express is similar and some of its
analysis abilities are close.  As far as I can tell, they are more
complex (and less speicific) than what is needed.  It may be like
killing an ant with a ICBM.  (So motivating the use may be tough.)

Reading a paper on Pablo (The Pablo Performance Analysis Environment -
University of Illinois/NCSA) pointed out some important facts about
motivating the user, and providing extensibility and usefulness.  I am
convinced that tools exist which either already do what we need, or
that our need requires re-thinking.  There is a sensibility to the
Pablo approach which is very appealing.  I have a difficult time
justifying asking algorithm developers to learn to use a tool to write
very simple parallel algorithms for a "simulation tool" (which would
take as long to write for a real machine) only to learn qualitatively
about them (and that only roughly) so that they can eliminate a few
really awful choices (which would probably be intuitively obvious
after getting some experience) and then being forced to code all the
others for the real machine to figure out what's best.  It seems
superfluous right now.

Nonetheless, I'm trying to research the issue, and asking for any help
you're willing to offer.

  - Are you aware of any tools currently available which will
    perform the simple tasks we require?  

  - What about the Pablo/Picasso stuff - do you think that it has
    merit for us? 

Philosophically, can you add you $0.02 to the idea of an tool that
does this kind of algorithm analysis?  Talking with Geoffrey Fox, he
seemed to indicate that we were looking at a very large investment of
time and people.  (I also am starting to get the impression that a
project like this has so little "return on investment" compared to
things like Pablo, HeNCE, Express, etc. that it isn't worth it.)
Daniel Reed, at NCSA, says that he took the route that we're
considering for a time, and found it to be fruitless due to growing
disparity between the source and executable (due to compiler issues
and languages like Fortran90), loss of utility due to fast turnaround
of new architectures, etc.

Can you offer us any thoughts?


I will compile all the information that I get and post it.  It will
probably be at the end of this week or start of next.

Newsgroups: comp.parallel