MATLAB Answers

0

How to build a table inside a parfor loop

Asked by Paolo Bocchini on 10 Mar 2011
I am trying to build a lookup table inside a for loop. A minimal example of what I would like to do is:
% I start with a lookup table, first column is input, second is output (2*input)
table= [ 1 2
3 6
5 10
2 4];
n = 30; % number of input values
inputs=ceil(unifrnd(0,100,n,1)); %inputs are random numbers from 1 to 100
doubles=zeros(n,1); % doubles collects the outputs... that are doubles
parfor ii=1:n
comparison= table(:,1)==inputs(ii); % check if already computed:
if any(comparison) % if already computed
doubles(ii)=table(comparison,2); % then, retrieve it from table;
else % if never computed before
twice=2*inputs(ii); % then, compute it ...
doubles(ii)=twice; % ... use it ...
table=[ table
inputs(ii) twice]; % ... and store it in the table.
end
end
Unfortunately, this doesn't work because table is seen as a temporary variable by the parfor loop. How can I solve this? Note, I cannot preallocate the vector doubles, because in the real problem n=1e40.
Thank you, Paolo

  0 Comments

Sign in to comment.

1 Answer

Answer by Edric Ellis
on 11 Mar 2011

PARFOR is designed for "embarassingly parallel" problems where each iteration of the loop is independent. Unfortunately, the problem here is that you are updating the variable "table" in the last line of the loop. This means that the iterations are not independent, because the value of "table(:,1)" can change as the loop progresses.
I can't immediately see how to refactor this algorithm. You may need to use SPMD to allow communication between the loop iterates to implement your algorithm.

  1 Comment

Thank you for your answer! I though this application was still "embarassingly parallel" since I am not "really" updating a variable, but only concatenating, adding new elements at the bottom. Since concatenation is handled correctly by parfor, I thought that this slightly different use of the concatenation could have been somehow handled by parfor too.
I will look into SPMD.
Thank you again and... isn't it always surprising how the the implementation of TRIVIAL algorithms (such as this one) can become complex and tricky?

Sign in to comment.