Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!mordor!lll-tis!ames!ucbcad!ucbvax!umnd-cs!umn-cs!herndon
From: herndon@umn-cs.UUCP (Robert Herndon)
Newsgroups: comp.arch
Subject: Re: chewing up mips with graphics [parallel computing]
Message-ID: <1683@umn-cs.UUCP>
Date: Sat, 27-Jun-87 16:00:46 EDT
Article-I.D.: umn-cs.1683
Posted: Sat Jun 27 16:00:46 1987
Date-Received: Thu, 2-Jul-87 00:47:33 EDT
References: <8270@amdahl.amdahl.com> <359@rocky2.UUCP> <338@astroatc.UUCP>
Organization: University of Minnesota, Minneapolis
Lines: 66
Keywords: parrallel computing; performance; vector computing
Summary: Parallization of conventional codes?

In article <338@astroatc.UUCP>, johnw@astroatc.UUCP (John F. Wardale) writes:
> In article <5793@think.UUCP> bradley@godot.think.com.UUCP (Bradley Kuszmaul) writes:
> Codes blocks can be classes as:
> 1: parallelizable and vectorizable [example: zero an array]
> 2: parallelizable    [example: a=5; b=6]
> 3: vectorizable      
> 4: neither
> An example of #4 is an orbital dif-eq-shooting problem
> you have initial conditions, and a set of differential equations.
> In a loop you;
>     increment time a little bit, calculate [sequentially dependent]
>     values for acceleration, velocity, and position
> end-loop
> 
> If anyone can vectorize or parallelize this, call me, I'll split
> the profits with you.  :-)
  Parallelize that, no.  Parallelize the same problem, which presumably
is "tell me how projectile X under conditions Y will fall", is
entirely a different question, and may be parallelizable,
depending on the differential equation involved.  Just as
In a loop you:
     read the next character
	(c = read)
     if the output table entry indexed by the character is non-zero, output
       the token numbered there.
	( if output[current_state][c] != 0 
		write(output[current_state][c])  )
     index the state-transition-table by the current-state and the input
     character, and make the resulting state the new current state.
	( current_state = state_trans[current_state][c] )
end-loop
  describes a serial lexical scanner of the garden variety,
it is not trivially parallelizable.  However, a different,
parallel algorithm IS capable of solving the same problem
("Given an input string and a Mealy machine, tell me what
tokens are transduced when the Mealy machine is given the
input string.") in time logarithmic to the length of the
input string.  (See Hillis and Steele in CACM, December 1986
for a solution.)
  This is why the Connection Machine people think that parallelism
is likely to be a big win for many problems -- and why they are
probably right.
> 
> There are also enuf "embarrassingly parallel" problems that such
> machines will have a good market, tho not as wide a market as
> the real and small "Cray-like" machines.
> 
> BTW:  It would be wonderful if I'm wrong, and someone finds a way
> to effectively split *ANY* problem to run on >100 processors in
> parallel, but I won't believe it until I see it.
>
  I wouldn't call the above problem "embarassingly parallel",
but depending on the complexity of the scanner, several thousand
processors on a connection machine should easily break the X100
performance barrier of any machine you care to name.
  If you mean "ALL" problems, then I'd have to agree with you.
There certainly are problems that seem to require a serial
solution strategy.  BUT:  you must differentiate between
"a problem" and "code to solve a problem".  They are NOT identical,
and an algorithm change makes it a whole new ball game.

-- 
Robert Herndon				Dept. of Computer Science,
...!ihnp4!umn-cs!herndon		Univ. of Minnesota,
herndon@umn-cs.ARPA			136 Lind Hall, 207 Church St. SE
herndon.umn-cs@csnet-relay.ARPA		Minneapolis, MN  55455