Параллельная рекурсивная функция в R?

Question

Я всю неделю разбирался с этой проблемой и мог действительно использовать внешнюю перспективу. По сути, я построил рекурсивную функцию дерева, в которой выходные данные каждого узла в одном слое используются в качестве входных данных для узла в следующем слое. Я создал игрушечный пример, где каждый вызов генерирует большую матрицу, разбивает ее на подматрицы и затем передает эти подматрицы последующим вызовам. Основное отличие от аналогичных вопросов в стеке состоит в том, что каждый вызов tree_search фактически ничего не возвращает, он просто добавляет результаты в файл CSV.

Теперь я хотел бы распараллелить эту функцию. Однако, когда я запускаю его с mclapply и mc.cores=2, время выполнения увеличивается! То же самое происходит, когда я запускаю его на многоядерном кластере с mc.cores=12. Что тут происходит? Родительские узлы ждут, пока дочерние узлы вернут какой-нибудь вывод? Это как-то связано с распараллеливанием вилки / сокета?

Для справки: это часть алгоритма, который моделирует активацию генов в лейкоцитах в ответ на вирусную инфекцию. Я биолог и программист-самоучка, так что я немного не в себе - любая помощь или рекомендации будут очень благодарны!

# Load libraries.
library(data.table)
library(parallel)

# Recursive tree search function.
tree_search <- function(submx = NA, loop = 0) {

  # Terminate on fifth loop.
  message(paste("Started loop", loop))
  if(loop == 5) {return(TRUE)}

  # Create large matrix and do some operation.
  bigmx <- matrix(rnorm(10), 50000, 250)
  bigmx <- sin(bigmx^2)

  # Aggregate matrix and save output.
  agg <- colMeans(bigmx)
  append <- file.exists("output.csv")
  fwrite(t(agg), file = "output.csv", append = append, row.names = F)

  # Split matrix in submatrices with 100 columns each.
  ind <- ceiling(seq_along(1:ncol(bigmx)) / 100)

  lapply(unique(ind), function(i) {

    submx <- bigmx[, ind == i]

    # Pass each submatrix to subsequent call.
    loop <- loop + 1
    tree_search(submx, loop) # sub matrix is used to generate big matrix in subsequent call (not shown)

  })

}

# Initiate tree search.
tree_search()

Answer 1

После долгих размышлений и экспериментов я ответил на свой вопрос. Я не буду ссылаться на оригинальный пример, так как я немного изменил свой подход. Вместо этого я поделюсь некоторыми общими наблюдениями, которые могут помочь людям в подобных ситуациях.

1.) For циклы более эффективны по памяти, чем lapply и рекурсивные функции

Когда вы используете lapply, каждый вызов создает копию вашей текущей среды. Вот почему вы можете сделать это:

x <- 5
lapply(1:10, function(i) {
   x <- x + 1
   x == 6 # TRUE
})
x == 5 # ALSO TRUE

В конце x по-прежнему равен 5, что означает, что каждый вызов lapply манипулировал отдельной копией x. Это не хорошо, если, скажем, x был на самом деле большим фреймом данных с 10 000 переменных. Циклы for, с другой стороны, позволяют переопределять переменные в каждом l oop.

x <- 5
for(i in 1:10) {x <- x + 1}
x == 5 # FALSE

2.) Распараллеливать один раз

Распределение Задачи для разных узлов занимают много вычислительных ресурсов и могут свести на нет любые выгоды, которые вы получаете от распараллеливания вашего скрипта. Поэтому вы должны использовать mclapply по своему усмотрению. В моем случае это означало НЕ помещать mclapply внутри рекурсивной функции, где ее вызывали от десятков до сотен раз. Вместо этого я разделил начальную точку на 16 частей и выполнил 16 различных операций поиска по дереву на отдельных узлах.

3.) Вы можете использовать mclapply, чтобы ограничить использование памяти

Если вы разделите работу на 10 частей и обработаете их с помощью mclapply и mc.preschedule=F, каждое ядро ​​будет обрабатывать только 10% вашей работы за раз. Например, если для mc.cores установлено значение два, остальные 8 «узлов» будут ждать завершения одной части, прежде чем начинать новую. Это полезно, если вы сталкиваетесь с проблемами с памятью и хотите, чтобы каждый l oop не брал больше, чем может обработать.

Заключительное примечание

Это одна из наиболее интересных проблем, над которыми я работал до сих пор. Однако рекурсивные древовидные функции являются сложными. Вытяните алгоритм и заставьте себя провести несколько дней вдали от своего кода, чтобы вы могли вернуться с перспективой sh.