|space vs time budd@mist.CS.ORST.EDU (Tim Budd) (1988-08-18)|
|Date:||Thu, 18 Aug 88 16:34:29 pdt|
|From:||Tim Budd <budd@mist.CS.ORST.EDU>|
Recently I've been thinking about code generation for APL (yes, APL), for
parallel processors, such as the Cray or the Connection Machine.
In this situation time/space tradeoffs become more obvious.
Consider inner-product, which is a generalized matrix multiplication (a
built-in operation in APL). If we are multiplying a n-by-m matrix with a
m-by-r matrix, resulting in a n-by-r result, there are quite a number of
1) If we want to optimize for speed, there is a simple log(m) algorithm
which takes n*m*r space. (That is, an algorithm which takes O(log(m))
vector operations, the largest of which operate on vectors of length n*m*r.
My analysis assumes vector operations work in constant time regardless of
the size of the vector).
2) On the other hand, if we don't have n*m*r space there is a slightly
slower algorithm which requires only the minimum n*r space (enough for the
output), but which takes O(m) time.
3) If the results are being further compressed (such as by a reduction
surrounding the inner product), then there are even slower algorithms which
will generate the values one by one, using only O(1) space but, of course,
Which is the ``correct'' algorithm to generate for the inner product
operator? it depends. sometimes one and sometimes the other.
I'm now trying to find heuristics and/or what hints the programmer might
provide which would help in determining the kind of code to put out.
--tim budd, oregon state university
[For people interested in APL compilation in general, see Tim's recent book
"An APL Compiler" published by Springer. I reviewed it for Computing
Surveys and found it pretty interesting. -John]
Return to the
Search the comp.compilers archives again.