Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: Complex Instructions
Message-ID: <1290@l.cc.purdue.edu>
Date: 7 May 89 12:05:00 GMT
References: <57252@yale-celray.yale.UUCP> <4101@tolerant.UUCP> <134@dg.dg.com> <13396@pasteur.Berkeley.EDU>
Organization: Purdue University Statistics Department
Lines: 66

In article <13396@pasteur.Berkeley.EDU>, dean@columbine.Berkeley.EDU (R. Drew Dean) writes:
> In article <1287@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
< <I agree.  But semi-portable and close to efficient is not impossible.  You 
< <may have to abandon an algorithm completely on some machines.  In some cases
< <the algorithm may have to be entirely abandoned.  This is especially the case
< <in generating random variables, where it is the method which must be correct,
< <NOT the answer.  The CRAY-1 is so bad I consider it a basket case for
< <vectorization.  I would suggest connecting a mini, or even a micro, to
< <do this part of the job.  The algorithm I would use on the 205 differs 
< <from what I would use on the IBM 3090; the 205 algorithm could be implemented
< <on the 3090, but would be decidedly more costly.  Implementing the 3090
< <algorithm on the 205 would require breaking up the vector into short pieces,
< <which is required on vector register machines such as the 3090 and CRAY, but
< <is not required on vector stream machines such as the 205.  But to me, these
< <considerations are immediate and obvious.

> Can you please provide examples of the different algorithms you use on these
> different machines ?

I am in the process of producing a report on this.  I will send a copy to
anyone who requests it.  It is possible I may post (not to this group) an
abbreviated source form.  

> I refer you to the ACM Turing Lecture book, where I paraphrase from (I forget
> whose lecture this was, the book is in the library where I'm not, but if
> my memory hasn't dropped too many refresh cycles it's McCarthy's...)
> 	Look at generating Fibonacci numbers.  The obvious algorithm
> 	F(n) = F(n-1) + F(n-2) generates a process with exponential
> 	running time, but this can be transformed into a process with
> 	linear running time...[new algorithm omitted]  I don't care
> 	how great your "optimizing" compiler is -- a compiler which
> 	sees this transformation (reducing the order of growth), generating
> 	not necessarily perfect code, will trounce your compiler....
> Note: Ok, this would be a really difficult compiler to write....I don't know
> of anybody doing it yet.  But it's the principle that matters here:
> It's _not_ how micro-efficient your code is that matters.  If it's
> too slow, rethink the algorithm.  That's where the real difference is --
> if you reduce the order of growth, wonderful things start happening.

This is definitely the case if you want only F(1384257).  I am not sure
if you want F(100).  But if you want F(1), ..., F(100), I suggest you
might want to use the obvious algorithm.  Vector machines are another
problem; I have no idea how to vectorize this algorithm.  On some vector
machines, I can come up with a safe way to do it, but I do not know how
good it is.

> If your random variable generator uses an algorithm that executes in the
> least known time, then please forgive this posting....

Given sufficient resources, I can come arbitrarily close to the algorithm
which uses the least possible expected number of bits.  Possibly even the
"arbitrarily close" can be removed in an algorithm with a finite expected
time.  The algorithms which are bit efficient are not likely to be time
efficient, although I have some hope for some being able to do a fair job
of both..  Technical reports on this are available.
available, although incomplete.
> Drew Dean
> Internet: dean@xcssun.berkeley.edu
> UUCP: ...!ucbvax!xcssun!dean
> FROM Disclaimers IMPORT StandardDisclaimer;


-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)