space vs time

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
choices.
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,
polynomial time.


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 comp.compilers page.
Search the comp.compilers archives again.