🚀 go-pugleaf

In article <1991Jun3.130104.15667@hubcap.clemson.edu> baugh%ssd.intel.com@RELAY.
CS.NET (Jerry Baugh) writes:
>
>The LINPACK benchmark has often been used as one measure of comparison between
>machines, and most recently, a new section of the report, entitled 'Massively
>Parallel Computing' defines the same test, solve a dense set of linear
>equations, but allows for the problem sizes to scale with the size of the
>machine.  With the unveiling of the Touchstone Delta machine, Intel can now
>publish the following double precision performance numbers for massively
>parallel LINPACK:
[numbers deleted]

At first, I started to read this thinking "what the heck does LINPACK
have to do with the performance of a parallel computer other than
measuring the power of individual nodes?"  Then I started reading more
closely, and it appears that there's more to it than that.

Can someone explain how "massively parallel LINPACK" is different from
regular LINPACK?  What considerations for communication are made
in this benchmark?  Since LINPACK is normally used as a measure of number
crunching, I'm curious how this benchmark translates to parallel
computers.  As we all know (or we all should know), the performance
of a parallel computer is usually NOT the same as the performance of an
individual node multiplied by the number of nodes in the computer
(although we'd just love that to always be the case).
The obvious misapplication of this kind of benchmark would
be to multiply a single node's LINPACK performance by the number of nodes in
the machine.  I notice that the numbers posted in the above-referenced
article do not scale linearly with the number of nodes used, so there
is some efficiency loss from the single node case.  I'm itching to
find out what the source of this loss is.  This is of particular interest
as I am currently porting some existing parallel code to the Delta, and I'd
like to be able to handle the inevitable queries about "well, they say
the Delta does such-and-such LINPACK GFLOPS...".

Any explanation or references would be welcome.
-- 
Steve Groom, Jet Propulsion Laboratory, Pasadena, CA
stevo@elroy.jpl.nasa.gov  {ames,usc}!elroy!stevo
"... and the babe, she needs a chaaaa--nging..." (apologies to Bob Dylan)

-- 
=========================== MODERATOR ==============================
Steve Stevenson                            {steve,fpst}@hubcap.clemson.edu
Department of Computer Science,            comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell

In article <1991Jun3.233741.8570@elroy.jpl.nasa.gov> stevo@elroy.jpl.nasa.gov (Steve Groom) writes:
>[original post deleted ... Jerry Baugh]
>
>At first, I started to read this thinking "what the heck does LINPACK
>have to do with the performance of a parallel computer other than
>measuring the power of individual nodes?"  Then I started reading more
>closely, and it appears that there's more to it than that.
>
>Can someone explain how "massively parallel LINPACK" is different from
>regular LINPACK?  

Since I started this, I guess I ought to take a stab at explaining this
as well.  The standard LINPACK benchmark is constrained to 100x100 and
1000x1000.  These problem sizes are relatively small when compared with
the capabilites of todays supercomputers.  And they are small compared
to the size problems people are solving today (a production code at
one of our customer sites does a 20k x 20k matrix multiply).  Recently,
Jack Dongarra extended his standard LINPACK benchmark suite to include
a new catagory "Massively Parallel Computing".  This new catagory allows
the problem size to increase up to and including the limit of physical
memory.  Since the problem size can vary, it is important to note the
size (presented as order of the matrix) as well as the FLOP numbers presented.
One of the reasons we are proud of our numbers here at Intel is that
we got a high GFLOP number with a relatively small problem size (we can
still increase the problem size as we have not yet run out of physical
memory).

>What considerations for communication are made in this benchmark?  

Both data decomposition and data communication are critical.  The
method of parallelizing a program that is chosen must take both into
account. Selecting one method of data decomposition may dictate the
data communication strategy.  The strategy used in this case involved
a 2D data decomposition that does both column and row mapping.  This
takes advantage of the Touchstone Delta's mesh architecture by allowing
messages to flow to all nearest neighbors.  And this leads to
higher performance than a 1D decomposition scheme.

>Since LINPACK is normally used as a measure of number crunching,
>I'm curious how this benchmark translates to parallel computers.  

This particular version was designed for parallel computers.

>As we all know (or we all should know), the performance
>of a parallel computer is usually NOT the same as the performance of an
>individual node multiplied by the number of nodes in the computer
>(although we'd just love that to always be the case).
>The obvious misapplication of this kind of benchmark would
>be to multiply a single node's LINPACK performance by the number of nodes in
>the machine.  I notice that the numbers posted in the above-referenced
>article do not scale linearly with the number of nodes used, so there
>is some efficiency loss from the single node case.  I'm itching to
>find out what the source of this loss is.  
 
Since the data values are distributed across multiple nodes, data must be
passed from one node (where it resides) to another node (where it is needed
for the calculation).  This communication cost is a major part of the
difference you see between the single node numbers and the 512 node
numbers.
 
>This is of particular interest
>as I am currently porting some existing parallel code to the Delta, and I'd
>like to be able to handle the inevitable queries about "well, they say
>the Delta does such-and-such LINPACK GFLOPS...".

Personally, I have always said that performance on real codes is important.
The "Massively Parallel LINPACK" benchmark provides one measure that is
meaningful for some classes of codes.  For other classes of programs
(database for example), it is meaningless.
 
>Any explanation or references would be welcome.

Hope what I've written helps.  For more information on LINPACK and the
"Massively Parallel LINPACK", I suggest you get Jack Dongarra's paper
'Performance of Various Computers Using Standard Linear Equations Software'.
For an explaination of a parallel 1D decomposition, try 'LAPACK Block
Factorization Algorithms on the Intel iPSC/860', LAPACK Working Report 24,
University of Tenessee, Oct. 1990 by Dongarra and Ostrouchov.

>Steve Groom, Jet Propulsion Laboratory, Pasadena, CA
>stevo@elroy.jpl.nasa.gov  {ames,usc}!elroy!stevo

Jerry Baugh
Intel SSD - baugh@SSD.intel.com

In article <1991Jun5.120653.7852@hubcap.clemson.edu> baugh%ssd.intel.com@RELAY.CS.NET (Jerry Baugh) writes:
>
>One of the reasons we are proud of our numbers here at Intel is that
>we got a high GFLOP number with a relatively small problem size (we can
>still increase the problem size as we have not yet run out of physical
>memory).
>
And rightfully so.  It's relatively easy to get a high GFLOP number
(assuming the raw machine power exists) for a sufficiently large
problem, assuming you can hook enough machines together and wait the
necessary days for the final solution.  There are effective linear equation
solver techniques with communication times proportional to the square
of the problem size, while the computation time is proportion to the
cube of the problem size.  So for sufficiently large problems, a gaggle
of workstations on a cluster of Ethernets could give GFLOP numbers
if someone wanted to take the trouble to run the test (say at one of
the universities with lots of workstations, like Carnegie Mellon over a
holiday weekend).

Another challenge I would like to see would be one which uses an efficent,
portable algorithm for linear equation solving written in a high level
language such as Fortran.  Then we could get some idea of what is achievable
on a machine without resorting to assembly language.

I know that what's most efficent on each machine varies with the
architecture, so maybe the rules could be that the portability requirement
is met by requiring that program be "standard" which could be determined
by running it on some commonly available workstations (with different
instruction sets from the target machine), but the supercomputer vendor
could select and implement the algorithm of their choice.  This approach
would provide some information about the ability of a compiler to get
the most out of a machine under ideal circumstances.  The requirement
that it also run on some other machine is intended to avoid machine
specific system calls.  Does this benchmark idea sound interesting to
anyone else?

In article <1991Jun3.233741.8570@elroy.jpl.nasa.gov> stevo@elroy.jpl.nasa.gov (Steve Groom) writes:
>Can someone explain how "massively parallel LINPACK" is different from
>regular LINPACK?  What considerations for communication are made

Here's my guess, based on working with these machines, going to Intel
iPSC/860 class, etc etc.  I'm not a numerical analyst, I'm a system
geek, so take this with a grain or two of salt.

If "parallel LINPACK" means the problem size is too large to fit
in the memory of a single node, then it carries a lot of meaning.
The problem becomes not just "how fast can I do LINPACK", but "how fast
can I do some part of LINPACK, shuffle some data from processor to
processor, and do some more LINPACK", etc etc..

Intel has a product (that used to be) called "LOOCS", which stands
for "Large Out Of Core Solver".  This package solves not only systems
which are too large for a single node, but systems that are too
large for the *total ram of the system*.  David Scott claims about
38 MFLOPS per node in double precision, which is pretty amazing
since the theorhetical peak is 40 MFLOPS double precision. (Of
course, this speed is achieved by use of hand-coding i860
assmebly.  Ouch.)

On a similar vein, a researcher here at UH doing work on molecular
dynamics has a 16 node iPSC/860 going faster than a Cray-2 using
the stock fortran compiler.  (Look for a paper coming soon to a
journal near you. :-)

--
J. Eric Townsend - jet@uh.edu - bitnet: jet@UHOU - vox: (713) 749-2126
Skate UNIX! (curb fault: skater dumped)

   --  If you're hacking PowerGloves and Amigas, drop me a line. --

In article <1991Jun3.233741.8570@elroy.jpl.nasa.gov> 
	stevo@elroy.jpl.nasa.gov (Steve Groom) writes:
>Can someone explain how "massively parallel LINPACK" is different from
>regular LINPACK?

Dongarra's latest Linpack report states that a fixed-size problem is
inappropriate for a scalable ensemble machine. So, instead, the
matrix size is allowed to vary. The solution method is considered
irrelevant: FLOPS is defined as  (2/3 N^3 + 2 N^2) / elapsed-time.

The Linpack reports wants the following numbers:
 - Accuracy residual.
 - GFLOPS and N for the largest problem run.
 - N-HALF, the problem size that achieved half the GFLOPS.
 - Theoretical peak GFLOPS.
 - Number of processors.

In the following, it's interesting to see the ratio of N^2 to N-HALF^2:

N	N-HALF	  ratio
------	------    -----
26,624	11,000	    6		CM-2	   64 K PE (or, 2 K FPU)
21,376	 3,193	   45		nCUBE 2	    1 K PE
 5,504   1,180     22		MasPar	   16 K PE
14,000	 5,500?     6		Touchstone, 512 PE, as just reported
-- 
Don		D.C.Lindsay 	Carnegie Mellon Robotics Institute

i'd appreciate some rationale on
   "FLOPS is defined as  (2/3 N^3 + 2 N^2) / elapsed-time",
where, i assume, N == number of processors used in the computation.

Thanks,
doug
#  ____    |Internet:   elias@theory.tn.cornell.edu
#dr _|_)oug|USmail:     Mgr., Adv. Comp. Res. Inst./Cornell Theory Center
#  (_|     |            704A TheoryCtrBldg/C.U./Ithaca/N.Y./14853-3801
#  (_|__   |MaBelle:    607-254-8826   Fax: 607-254-8888

In article <1991Jun5.120653.7852@hubcap.clemson.edu> baugh%ssd.intel.com@RELAY.CS.NET (Jerry Baugh) writes:

>
>One of the reasons we are proud of our numbers here at Intel is that
>we got a high GFLOP number with a relatively small problem size (we can
>still increase the problem size as we have not yet run out of physical
>memory).
>
Fine.  Scale it to the physical memory limit and tell us how long it takes.
Worley has written a marvelous paper, "The Effect of Time Constraints on
Scaled Speed-Up" (ORNL/TM-11031) wherein he shows that a meaningful inter-
pretation of speed-up depends on constraints on execution time.  Why don't
advocates of the promise of massive parallelism acknowledge such issues?

john@spectre.unm.edu (John Prentice) replies to the above article:

>>Allowing the
>>benchmarker to scale the problem to his or her physical memory would
>>seem to me to be a prescription for getting alot of results that can't be
>>compared to each other.  What I would prefer is to just fix the 
>>dimension, but fix it big.

Another important paper, "Type Architectures, Shared Memory, and the
Corollary of Modest Potential" should be read by john@spectre.unm.edu
and most other advocates of the promise of massive parallelism.  To para-
phrase Lawrence Snyder (author of paper - Annual Reviews of Computer
Science, 1986), it's certainly still premature to be pessimistic regarding
ultimate success of achieving the benefits of massive parallelism, yet
THERE IS REASON TO BE EXTREMELY CAUTIOUS.

Continuing to paraphrase Snyder: The frequent challenge with physical
phemomena models is not to solve a fixed-size problem faster, but to
solve larger instances within a fixed time budget.  Simple rationale:
Solutions are so computationally intensive that problem instances of an
"interesting" size do not complete execution in a tolerable amount of
time.  What is the effect of parallelism on problem size?  Keeping time
fixed and UNREALISTICALLY assuming the best possible speedup, it follows
that superlinear problems (the interesting, realistic ones) can only be
improved sublineraly by parallel computation.  Specifically, if a problem
takes t = c*n^x sequential steps, and if the application of p processors
permits an increase in the problem size by a factor of m, t = c*(m*n)^x/p,
then the problem size can increase by at most a factor of m = p^(1/x).
For example, to increase by two orders of magnitude the size of a problem
whose sequential performance is given by t = cn^4 (three spacial, one time
demension) requires, WITH UNREALISTIC OPTIMISM, 100,000,000 processors!

Again, it's time for the advocates of the promise of massive parallelism
to acknowledge Synder's "corollary of modest potential."

Randolph Gary Smith                       Internet: gary@chpc.utexas.edu
Systems Group                             Phonenet: (512) 471-2411
Center for High Performance Computing     Snailnet: 10100 Burnet Road
The University of Texas System                      Austin, Texas 78758-4497

Some questions?

At what size N for massive linpack does the accumulated numerical fuzz
swamp the precision available in a double precision number?

Aren't really large problems of interest sparse matrices anyway?  Who
holds the record for massive sparse matrix solves?

Perhaps some of the numerical experts out there could tell us
something about the characteristics of these massive numerical
problems. 

In article <1991Jun6.144903.20456@chpc.utexas.edu> gary@chpc.utexas.edu (Gary Smith) writes:
<
<To paraphrase Snyder: The frequent challenge with physical
<phemomena models is not to solve a fixed-size problem faster, but to
<solve larger instances within a fixed time budget.  Simple rationale:
<Solutions are so computationally intensive that problem instances of an
<"interesting" size do not complete execution in a tolerable amount of
<time.  What is the effect of parallelism on problem size?  Keeping time
<fixed and UNREALISTICALLY assuming the best possible speedup, it follows
<that superlinear problems (the interesting, realistic ones) can only be
<improved sublineraly by parallel computation.  Specifically, if a problem
<takes t = c*n^x sequential steps, and if the application of p processors
<permits an increase in the problem size by a factor of m, t = c*(m*n)^x/p,
<then the problem size can increase by at most a factor of m = p^(1/x).
<For example, to increase by two orders of magnitude the size of a problem
<whose sequential performance is given by t = cn^4 (three spacial, one time
<demension) requires, WITH UNREALISTIC OPTIMISM, 100,000,000 processors!

Well, if your problem really is quartic in n, yes, you are going to have
difficulty.  But I suspect most "real" problems tend more towards more linear
or quadratic behavior.  Physical simulations that at first appear to demand
higher order complexity often yield themselves to a more efficient approach
given a re-examination of the problem.

--
Alan E. Klietz
Minnesota Supercomputer Center, Inc.
1200 Washington Avenue South
Minneapolis, MN  55415
Ph: +1 612 626 1737	       Internet: alan@msc.edu