Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!spool.mu.edu!cs.umn.edu!uc!uh!alan
From: alan@uh.msc.umn.edu (Alan Klietz)
Newsgroups: comp.sys.super
Subject: Re: Massively Parallel LINPACK on the Intel Touchstone Delta machine
Message-ID: <4231@uc.msc.umn.edu>
Date: 7 Jun 91 05:37:20 GMT
References: <1991Jun3.130104.15667@hubcap.clemson.edu> <1991Jun3.233741.8570@elroy.jpl.nasa.gov> <1991Jun5.120653.7852@hubcap.clemson.edu> <1991Jun05.185818.1071@convex.com> <1991Jun6.144903.20456@chpc.utexas.edu>
Sender: news@uc.msc.umn.edu
Reply-To: alan@msc.edu (Alan Klietz)
Organization: Minnesota Supercomputer Center, Minneapolis, MN
Lines: 30

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