[net.arch] Current Status of Karp Challenge

eugene@ames.UUCP (Eugene Miya) (07/21/86)

I gave my performance measurement talk at the IBM Palo Alto Scientific
Center last week at the invitation of Alan Karp.  I thought I might relay
the current status of the challenge since it was mentioned in net.arch.

First, there is some misunderstanding about the challenge.  The challenge
was to demonstrate some factor of 100 simple speedup of some program
running on a computer.  So, the Connection Machine with 64K processors
falls down in two areas: 1) the computer must be an MIMD rather than
SIMD type (Multiple Instruction Stream Multiple Data Stream from
Flynn's [1966] classification scheme).  2) The program must be capable of
running on a single CPU of said computer.

Second, the only person to even suggest a possible challenge had an ICL DAP.
The DAP fails for the same reasons the CM does: SIMD and non-single CPU
execution.  If you are unfamiliar with the DAP, better do some homework,
they've been around a few years.  And if you don't know who ICL is, your
DEC/IBM/or other American bias is showing.

Third the Karp prize is strictly intended to be token.  This prize is
like the prizes offered by guys like Adleman for breaking the RSA
public key encryption algorithm or Hellman (who paid Adleman for breaking
his algorithm).

From the Rock of Ages Home for Retired Hackers:
--eugene miya
  NASA Ames Research Center
  com'on do you trust Reply commands with all these different mailers?
  {hplabs,ihnp4,dual,hao,decwrl,tektronix,allegra}!ames!aurora!eugene
  eugene@ames-aurora.ARPA

cdshaw@watrose.UUCP (Chris Shaw) (07/28/86)

In article <1578@ames.UUCP> eugene@ames.UUCP (Eugene Miya) writes:
>First, there is some misunderstanding about the challenge.  The challenge
>was to demonstrate some factor of 100 simple speedup of some program
>running on a computer.  So, the Connection Machine with 64K processors
>falls down in two areas: 1) the computer must be an MIMD rather than
>SIMD type (Multiple Instruction Stream Multiple Data Stream from
>Flynn's [1966] classification scheme).  2) The program must be capable of
>running on a single CPU of said computer.
>
>Second, the only person to even suggest a possible challenge had an ICL DAP.
>
>--eugene miya
>  NASA Ames Research Center

Actually, someone with a 128-node hypercube machine could probably do this.
Finding eigenvalues from a tridiagonal matrix using Bisection is very parallel.
Cleve Moler has a routine which does this. We have run it here at Waterloo on 
our 64-node Intel hypercube, and the speedup attained by simply throwing 
processors at the problem is remarkable. Unfortunately, I can't remember the
numbers.

Also, a local user has a Ray Tracing program which is almost entirely without 
communication, and could therefore run above the required speedup number.
A local copy of the scene is kept on each node, and each processor is 
responsible for a scan line. The results are then sent back, and a new scan 
line is assigned. Given a 128-node hypercube, I would fully expect 126-127
or so speedup. 

Both applications fit the two requirements: The iPSC is MIMD, and they can both 
run on 1 node.

So. Anyone got a spare iPSC-d6 (64 nodes) they could lend us?

Also, since I can name two, would we get $200 ??   B-)

Chris Shaw    watmath!watcal!cdshaw  or  cdshaw@watmath
University of Waterloo
Bogus as HELL!!