Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!lll-crg!mordor!sri-spam!rutgers!ucla-cs!zeus!dgreen From: dgreen@zeus.cs.ucla.edu (Dan R. Greening) Newsgroups: comp.arch Subject: Will the Karp Problem Be Solved? Message-ID: <3302@curly.ucla-cs.UCLA.EDU> Date: Thu, 4-Dec-86 23:58:06 EST Article-I.D.: curly.3302 Posted: Thu Dec 4 23:58:06 1986 Date-Received: Fri, 5-Dec-86 06:24:57 EST Reply-To: dgreen@zeus (Dan R. Greening) Distribution: world Organization: UCLA Computer Science Department Lines: 99 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