🚀 go-pugleaf

Reprinted without permission from the November 1986 SIAM News.  SIAM
is the Society for Industrial and Applied Mathematics.


WILL THE KARP PROBLEM BE SOLVED?

The following item has been circulating for almost a year on various
computer networks.  Because the author of the challenge is quite
confident about not having to pay any winner, SIAM News decided that
to really test the problem we should help to give the challenge wider
circulation.  The challenger is Alan Karp, IBM Scientific Research
Center 1530 Page Mill Road, Palo Alto, CA  94304

---

  I attended in 1985 the Second SIAM Conference on Parallel Processing
for Scientific Computing in Norfolk, Virginia, where I heard about
1,000 processor systems, 4,000 processor systems, and even a proposed
1,000,000 processor system.  Since I wonder if such systems are the
best way to do general-purpose, scientific computing, I am making the
following offer:

  I will pay $100 to the first person to demonstrate a speed-up of at
least 200 on a general purpose, MIMD computer used for scientific
computing.  This offer will be withdrawn at 11:59 PM on 31 December
1995.

  Some definitions are in order.
  SPEED-UP:  By speed-up I mean the time taken to run an application
on one processor using the best sequential algorithm divided by the
time to run the same application on N processors using the best
parallel algorithm.
  GENERAL PURPOSE:  The parallel system should be able to run a wide
variety of applications.  For the purposes of this test, the machine
must run three different programs that demonstrate its ability to
solve different problems.  I suggest a large, dynamic structures
calculation, a trans-sonic fluid flow past a complex barrier, and a
large problem in econometric modeling.  These are only suggestions;  I
will be quite flexible in the choice of the problems.  Several people
have volunteered to adjudicate disputes in the selection of the
applications.
  APPLICATIONS:  The problems run for this test must be complete
applications--no computational kernels are allowed.  They must contain
all input, data-transfers from host to parallel processors, and all
output.  The problems chosen should be the kind of job that a working
scientist or engineer would submit as a batch job to a large
supercomputer.  In addition, I am arbitrarily disqualifying all
problems that Cleve Moler calls ``embarrassingly parallel.''  These
include signal processing with multiple independent data streams, the
computation of the Mandelbrot set, etc.
  There are some rather obvious ground rules.
  1. Simulations of the hardware are not permitted.  I am looking for
a demonstration on a running piece of hardware.
  2. The same problem should be run on the sequential and parallel
processors.
  3. It is not fair to cripple the sequential processor.  For example,
if your operating system uses 99% of one processor, the single
processor run will spend all its time in the operating system.
Super-linear speed-up as the number of processors is increased is
evidence of this problem.
  4. It is not fair to memory starve the single processor run.  If you
have 100K words of memory on each of 1,000 processors, and you run a
10 MW problem, it is not fair for the sequential run to be made on a
100 KW processor.  After all, we are not interested in seeing the
impact of additional memory; we want to see how much the extra CPUs
help.

  It may not be possible to follow all these additional rules.  For
example, you can't be expected to build a single processor with lots
of extra memory or write a new operating system just for this test.
However, you should do your best to make the demonstration fair.  A
third party has agreed to adjudicate any scaling disputes.
  Anyone claiming this prize will be expected to present his or her
results at a suitable conference.  At the end of the presentation, I
will have the audience vote on whether the demonstration was
successful.  Remember, the purpose of the bet is to force developers
to demonstrate the utility of massively parallel systems, not to show
they can find holes in the rules.

Alan Karp is on the staff of IBM's Scientific Center in Palo Alto.
His challenge is a personal one, and does not reflect the position of
his employer.

----

While I can think of easier ways to earn a cool hundred, the challenge
seems to involve all sorts of people, so I thought I would pass it on
to you.

Well, Computer Scientists ...

  (hands on hips, looking down, frowning, tapping foot)

... why HAVEN'T we gotten the hundred bucks yet?


 _D_a_n_ _G_r_e_e_n_i_n_g     _A_R_P_A-  dgreen@CS.UCLA.EDU
                  _U_U_C_P- ..!{sdcrdcf,ihnp4,trwspp,ucbvax}!ucla-cs!dgreen