next up previous contents
Next: Nested loops Up: Parallelization Previous: Overview   Contents

Instruction expansion

Consider the operation $A[0:9] \gets f(A[0:9])$. This code should be fairly easy to translate into the sequence:

$A[0:4] \gets f(A[0:4])$
$A[5:9] \gets f(A[5:9])$

if we know that $f(\{A_0,A_1,\ldots\})_i$ depends only on $A_i$. The code is the equivalent of $\forall i: A_i \gets f(A_i)$.

Since $f(\cdot)$ will be some combination of the instructions provided by the virtual machine, we should be able to actually determine if $f(\cdot)$ has that desired property.

This is not currently implemented, but I fail to see why it should not be possible. We may not be able to spot every special case of instruction combinations, but it is often the simple cases that are the interesting ones, since the majority of computing code spends it's time in fairly simple loop constructs. If we can just catch enough cases to benefit in most situations, it will be good enough. But I'm not yet sure if there would be any problem in detecting all cases.

The resulting code will lend itself very well to the sequence parallelizer.