Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!ll-xn!adelie!necntc!linus!bs From: bs@linus.UUCP (Robert D. Silverman) Newsgroups: comp.arch Subject: Re: chewing up mips with graphics Message-ID: <8286@linus.UUCP> Date: Wed, 1-Jul-87 22:55:58 EDT Article-I.D.: linus.8286 Posted: Wed Jul 1 22:55:58 1987 Date-Received: Fri, 3-Jul-87 05:42:33 EDT References: <8270@amdahl.amdahl.com> <359@rocky2.UUCP> Reply-To: bs@linus.UUCP (Robert D. Silverman) Organization: The MITRE Corporation, Bedford MA Lines: 52 In article <343@astroatc.UUCP> johnw@astroatc.UUCP (John F. Wardale) writes: >In article <1323@ogcvax.UUCP> pase@ogcvax.UUCP (Douglas M. Pase) writes: >> to make 100 compiles go 100 times faster by using 100 machines than it > >> In article (ME) johnw@astroatc.UUCP (John F. Wardale) writes: >> >> This and other related studys show that a large fraction of >> problems that have no, or very limited parrallelism. >> >>As you have stated the study, it does *not* support your conclusion. Tight >>loops in FORTRAN (shudder) programs may often be parallelized, by pipelining >>instructions. Kuck's work on parallelizing compilers have shown amazing >>improvements can be gained by pipelining and vectorizing DO loops. (Yes, >>both are a form of parallelism.) It is the data dependencies which determine >>the available parallelism, not the size of the code. > >Right, and *MOST* programs have dependencies that limit the paralleliam to >one or two digits worth. Tom's original posting was looking for three >digits worth. To get that, you need a problem that is "embarrassingly >parallel" or an amazing system (hw+sw). Interestingly enough, I have an algorithm (actually two separate algorithms) which can take FULL advantage of ALL the parallelism available. These algorithms are the Quadratic Sieve and the Elliptic Curve Method for factoring integers. I have demonstrated that N MIMD processors yield an N-fold speed-up for both of these algorithms running on a distributed network of SUN-3's. I have a paper describing the Quadratic Sieve work that will appear this fall in the Journal of Supercomputing. My current set of hardware consists of about 22 SUN's and they quite definitely yield a 22-fold speedup. If I could get hold of 100 SUN-3's on a single network file system I could meet the conditions of the Karp challenge. The Elliptic Curve Method is a random algorithm that does some group (ring) computations on a random elliptic curve. If the order of the group of that curve is divisible by ONLY small primes then the algorithm will succeed in factoring a very large number. If the group isn't divisible by only small primes, one gives up and tries another random curve. By giving separate, random curves to each processor N processors will run N curves at once rather than one after another. A consequence is that during the computations the processors need NOT communicate with one another. If one processor succeeds it simply halts the others. This sort of thing would also run very nicely on a SIMD machine. I suspect, however, that Karp would consider this sort of thing in the category of 'trivially parallelizable'. Comments Please? Bob Silverman