Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, Mathematica, Matlab, or seek clarification.

Are there situations when a vectorized (aka element-wise application of a function or array programming (AP)) computation cannot be parallelized?

When coding, I frequently replace loops with a vectorized computation, if possible. At times, it's an interesting exercise or (arguably) makes the code more readable. Other times, in hopes of parallelizing it in the future, if need be.

Is there a constraint that would prevent me from parallelizing a vectorized code.

Vectorization example Note that even seemingly tight loop can be vectorized. For example, cumulative sum of vector elements (1, 2, 3) can be transformed to a matrix form ((1,1,1),(0,2,2),(0,0,3)) and then vectorization is done as column sums producing the desired (1,3,6) cumulative sum. However, vectorization of fibonacci sequence is unlikely(?).

Many thanks for your explanations and references.

• Can you define what you mean by vectorized? For instance, do you assume that a vectorized computation has no dependencies between loop iterations? – D.W. Nov 14 '15 at 6:04
• Good point. I updated the question with Wikipedia's definition of array programming (as vectorization). – Oleg Melnikov Nov 14 '15 at 14:53
• Depends on the function you apply element-wise. As soon as it depends on "global" state or performs any kind of I/O, you may not be able to parallelize. If it's a "pure" function, I don't see any reason why not. – Raphael Nov 14 '15 at 15:34
• @Raphael: interesting point. If AP is allowed to (randomly, i.e. non-sequentially) access/update global state, what prevents a forked worker to do the same? – Oleg Melnikov Nov 14 '15 at 15:47
• I still don't see the answer to whether you assume that a vectorized computation must, by definition, have no dependencies between loop iterations. – D.W. Nov 14 '15 at 21:08

If there are dependencies between loop iterations, then the loop cannot be parallelized. Depending upon the precise definition of "vectorized" you have in mind, your definition might imply that there are no dependencies -- or it might not.

Some examples:

foreach i in S:
B[i] = f(A[i])

is parallelizable if f is a pure function and A,B don't alias (have no overlap). (But it is in general not parallelizable if f writes to global state or performs any kind of I/O.) More generally

foreach i in S:
B[i] = f(i, x, y, ..)

is parallelizable if f is pure and does not access B (for reading or writing) and none of the arguments alias B. However,

foreach i in S:
B[i] = B[A[i]]

is not parallelizable, as there are dependencies between loop iterations. (At least, it is not trivially parallelizable, if A is not known at compile time.)

I've written using foreach syntax but you can translate each example to map or apply and the same comments apply.