parfor variable cannot be classified

as far as i can tell, the following code should be parallelizable, however I get a 'cannot be classified' error no matter how I twist it. This is paraphrased code . It is 'theoretically parallelizable' i blv., as the result is independent of execution order.

    a{1}=''
    a{2}='hi'
    a{3}=''
    a{4}='bye'
       parfor k = 1:10
          j=mod(k,5)
          b=a{j}
          if isempty(b)
            a{j} = j+3
          end
        end

along these lines, what can this possibly mean:

    "Notably, the assignments to the variables i, t, and u do not affect variables with the same name in the context of the parfor statement. "

http://www.mathworks.com/help/distcomp/parfor.html?searchHighlight=parfor%20using%20objects%20{}

a more concise statement of the problem is that the following, which is in principle parallelizable for arbitrary 'index' functions f,g (ie positive integer functions in range of the array in question), cannot in fact be compiled due to matlab compiler limitations.

    parfor k=1:10
        index=f(k)
        array(index)=g(index)
    end

however as walter roberson points out below this limitation can be somewhat avoided in this case by the following:

     parfor k=1:10 
           index=f(k)
           temparray(k)=g(index)
           indices(k)=index
     end
     for k=1:10
         array(indices(k)) = temparray(k)
     end

[Walter Roberson]

You do realize that you original code tries to index a{0} ?

[Jeremy Rutman]

yes, i took out a bunch of extranneous code in an attempt to make the question as clear as poss. and took out a '+1'

Answer 1

[Walter Roberson]

When k = 1 or k = 6 both times j = 1 so you have multiple iterations that would be accessing the same elements of a{}. That is not permitted

The indexing of the loop variable needs to be in-line in the access, not calculated in a previous statement and then used, so that parfor can verify that there is no possibility of overlap. mod() is not one of the permitted operations in the indexing for parfor.

[Jeremy Rutman]

is there a way to force a relaxation of the parfor compiler checker rules?

[Walter Roberson]

No.

parfor does not impose any interlocks to ensure that there are no race conditions due to data being accessed twice. It relies upon static analysis, upon being able to analyze the code ahead of time and prove that the same writable location is not being accessed in different iterations.

If you need to write to the same location in different iterations, then parfor is not the right directive for you to use.

If you need to write to locations in an order that is not obviously unique, but that you know will be unique, then write to an output in an obviously unique location and also keep a record of where the output needs to end up. Then after the parfor you can run a sequential process moving the data into the right place, possibly just using straight indexing:

RealOutputVariable(VectorOfWhereToPutOutput) = OutputsInParforIndexOrder;

[Walter Roberson]

    parfor k=1:10
        index=f(k)
        array(index)=g(index)
    end

Is not "in principle parallelizable for arbitrary 'index' functions f,g (ie positive integer functions in range of the array in question)". It is only in principle parallelizable for index functions for which f(k) is unique.

There are also some logistic problems if f(k) does not cover all of the indices of the array; and there can be difficulties with cache line conflicts which can slow the operation down in ways that might be prevented if the order was known ahead of time. However, those are practical difficulties rather than theoretic difficulties.

[Jeremy Rutman]

When I say 'in principle parallelizable' I am not referring to whether matlab knows how to parallelize, but rather whether the execution results are independent of loop execution order, which of course this snippet clearly satisfies (since even if f(k) is not unique, g(f(k)) will be the same for all the non-unique values of f). Some other compiler that takes care of atomic operations and with a less restrictive compiler preprocess would in principle be fine with this.

[Walter Roberson]

We do not inherently know that g(f(x)) will be the same for the non-unique values of f. g could be a function that returns different values at different times. You would need to know that g() is either an array that is invariant during the operation, or a function that has no side effects.

None of the parallelizing compilers I have ever seen have ever been happy with code of this form that might write the same location multiple times but with the same result each time.

[Jeremy Rutman]

ok if the function g changes with time then this would be trouble. In the meantime I adopted your solution and have run into another issue , maybe you can take a look