Parallel computing with recursive function

Question

My challenge is to parallel compute a recursive function. However, the recursion is quite deep, and therefore (in my own novice words) there is an issue with allocating a worker when all the workers are busy. in short, it crushes.

Here is some reproducible code. The code is very stupid, but the structure is what counts. This is a simplified version of what is going on.

I work on a windows machine, if the solution is to go linux, just say the word. Because the real function can be quite deep, managing the number of workers that are called for in the upper level will not solve the issue. Is there perhaps a way to know in what level the recursion is?

  FUN <- function(optimizer,neighbors,considered,x){
    considered <- c(considered,optimizer)
    neighbors <- setdiff(x=neighbors,y=considered)

    if (length(neighbors)==0) {
      # this loop is STUPID, but it is just an example.
      z <- numeric(10)
      for (i in 1:100)
      {
        z[i] <- sample(x,1)
      } 
      return(max(z)) 
    } else {
      # Something embarrassingly parallel, 
      # but cannot be vectorized.
      z <- numeric(10)
      z <- foreach(i=1:10, .combine='c') %dopar%{
        FUN(optimizer=neighbors[1],neighbors=neighbors,
                  considered=considered,x=x)}
    return(max(z))
    }
}

require(doParallel,quietly=T)
cl <- makeCluster(3)
clusterExport(cl, c("FUN"))
registerDoParallel(cl)
getDoParWorkers()



>FUN(optimizer=1,neighbors=c(2),considered=c(),x=1:500)
[1] 500
>FUN(optimizer=1,neighbors=c(2,3),considered=c(),x=1:500)
Error in { : task 1 failed - "could not find function "%dopar%""

Spacedman Spacedman · Accepted Answer · 2013-12-26T09:11:17

>FUN(optimizer=1,neighbors=c(2,3),considered=c(),x=1:500)
Error in { : task 1 failed - "could not find function "%dopar%""

Is this error really because the recursion is too deep or is it just because you haven't got require(doParallel) in your FUN function? So that when FUN is called on the workers, that instance of R hasn't got that package in its list.

Your first example doesn't do this because its simple enough to not get to the inner %dopar% loop.

Parallel computing with recursive function

1 Answers