Path: utzoo!utgpu!water!watmath!clyde!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsp!johnson
From: johnson@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.arch
Subject: Re: Single tasking the wave of the futu
Message-ID: <76700007@uiucdcsp>
Date: 18 Dec 87 16:35:00 GMT
References: <3445@hoptoad.uucp>
Lines: 35
Nf-ID: #R:hoptoad.uucp:3445:uiucdcsp:76700007:000:1557
Nf-From: uiucdcsp.cs.uiuc.edu!johnson    Dec 18 10:35:00 1987


/* Written  1:04 pm  Dec 16, 1987 by fouts@orville.nas.nasa.gov in uiucdcsp:comp.arch */

As an example of a class of algorithms which is difficult to vectorize
or parallelize, let me pull out the ancient prime finder algorithm:

...

Although there are different algorithms for finding primes, I use this
one to illustrate a class of problems which comes up frequently in my
work.

/* End of text from uiucdcsp:comp.arch */

The algorithm presented by fouts@orville is not parallizable.  As he
mentioned, there exist prime finder algorithms that are.  In fact,
there is a prime finder algorithm that should have linear speedup
on a multiprocessor, e.g. the probabilistic one.  I would be interested
in knowing more about the real problems that come up frequently.

Even though this is comp.arch, I will argue that the real problem in
building parallel systems is finding the parallel algorithms to run on them.
This problem is caused by the fact that we don't have many parallel machines,
so we don't spend much time looking for parallel algorithms.  The few
people who do have those machines are more interested in solving their 
day-to-day problems then they are in doing research into the fundamentals
of algorithms.  If we want to make a lot of progress in this area then we
will have to fund those people who are doing research in fundamental
computer science.  This area is woefully underfunded, contrary to
popular opinion.

By the way, I don't work in inventing algorithms, but I enjoy using
the algorithms invented by those who do.

Ralph Johnson