🚀 go-pugleaf

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