Ускорьте случайную цепь Маркова в R с помощью data.table или парелелизации

Я пытаюсь ускорить моделирование методом Монте-Карло дискретной неоднородной по времени цепи Маркова с помощью data.table или некоторой формы распараллеливания. Используя случайные фиктивные матрицы перехода TM, я имитирую временные шаги nSteps в каждом из N симуляций и, начиная с вектора начального состояния initialState, записываю следующее обновленное состояние в currentState. На каждом временном шаге матрица I умножает текущее состояние на матрицу перехода TM.

Код 1 с петлей

nStates <- 5 #number of states
initialState <- c(rep(1/nStates, nStates)) #vector with uniform initial states
nSteps <- 10 #number of time steps
N <- 10000 #number of simulations

ind.arr <- matrix(1:(N*nSteps),ncol=nSteps, byrow=TRUE)
currentState <- vector("list",(N*(nSteps))) #collects the nSteps state vectors for each simulation

system.time(
  for (i in 1:N) {
    TM <- matrix(runif(nStates^2), ncol=nStates) #random transition matrix for each time step and each simulation
    currentState[[(ind.arr[i,1])]] <- initialState %*% (TM / rowSums(TM)) #/rowSums(TM) ensures that TM is a transition matrix
    for (t in 2:nSteps){
      TM <- matrix(runif(nStates^2), ncol=nStates)
      currentState[[(ind.arr[i,t])]] <- currentState[[(ind.arr[i,t-1])]] %*% (TM / rowSums(TM))
    }
  })

Код не очень медленный, но мне интересно, может ли отказ от N-цикла ускорить код. Если я помещу тело N-цикла в функцию

statefun <- function(initialState, nSteps, nStates){
  TM <- matrix(runif(nStates^2), ncol=nStates) #random transition matrix for each time step and each simulation
  currentState <- matrix(rep(NA, nSteps*nStates), ncol=nStates)
  currentState[1,] <- initialState %*% (TM / rowSums(TM)) #/rowSums(TM) ensures that TM is a transition matrix
  for (t in 2:nSteps){
    TM <- matrix(runif(nStates^2), ncol=nStates)
    currentState[t,] <- currentState[t-1,] %*% (TM / rowSums(TM))
  }
  return(currentState)
}

и использую data.table, я получаю ошибку, а не желаемый результат

library(data.table)
system.time(dt <- data.table(i=1:N)[, c("s1", "s2", "s3", "s4", "s5") := list(statefun(initialState, nSteps, nStates)), by=i])

#As each simulation run is independent and the call of statefun is expensive, I was hoping that parallelisation helps to accelerate the code, but trying foreach is actually slower than where I started.  

library(foreach)
system.time(res <- foreach(i=1:N, .combine='c') %do% statefun(initialState, nSteps, nStates))

Я ценю любые комментарии о том, как заставить data.table работать или использовать распараллеливание в этом случае. Большое спасибо, Тим

@ РЕДАКТИРОВАТЬ: этот не принимает десятистрочный вывод вызова функции ...

system.time( #does not work 
  dt <- data.table(i=1:N)[,c("s1", "s2", "s3", "s4", "s5"):=as.list(statefun(initialState, nSteps, nStates)),by=i]
)

person Tim_Utrecht    schedule 22.05.2015    source источник
comment
вы можете попробовать использовать RCUDA или что-то в этом роде для выполнения вычислений с помощью графического процессора, а не процессора. На больших матричных операциях дает великолепный прирост скорости   -  person inscaven    schedule 22.05.2015
comment
Мне нравится foreach, хотя .combine=c дает вектор, так что, возможно, вы захотите rbind или list (а затем выполнить привязку). data.table с by не превзойдет распараллеливание и хранение в таблице данных. Таблица лучше всего подходит для смешанных форматов данных с некоторыми группирующими переменными; в то время как использование матриц имеет больше смысла для вашего случая. Если вы хотите назначить data.table, возможно, сделайте это после завершения моделирования.   -  person Frank    schedule 22.05.2015


Ответы (2)


Если вы преобразуете внешний цикл for в цикл foreach с 10 000 задач, производительность будет невысокой, потому что задачи слишком малы. Часто лучше сделать количество задач равным количеству рабочих. Вот простой способ сделать это с помощью функции idiv из пакета iterators:

library(doParallel)
nw <- 4
cl <- makePSOCKcluster(nw)
registerDoParallel(cl)
nStates <- 5
initialState <- c(rep(1/nStates, nStates))
nSteps <- 10
N <- 10000

currentState <- foreach(n=idiv(N, chunks=nw), .combine='c') %dopar% {
  ind.arr <- matrix(1:(n * nSteps), ncol=nSteps, byrow=TRUE)
  cur <- vector("list", n * nSteps)
  for (i in 1:n) {
    TM <- matrix(runif(nStates^2), ncol=nStates)
    cur[[ind.arr[i,1]]] <- initialState %*% (TM / rowSums(TM))
    for (t in 2:nSteps) {
      TM <- matrix(runif(nStates^2), ncol=nStates)
      cur[[(ind.arr[i,t])]] <-
          cur[[(ind.arr[i,t-1])]] %*% (TM / rowSums(TM))
    }
  }
  cur
}

Вместо простого распараллеливания внешнего цикла for это добавляет цикл foreach вокруг уменьшенной версии последовательного кода. Итак, если вы найдете способ улучшить последовательный код, вы можете легко использовать его в параллельной версии. Вы также можете повысить производительность, не возвращая все промежуточные состояния.

person Steve Weston    schedule 24.05.2015
comment
Это здорово, спасибо. Ускорение на моем ноутбуке примерно на 60%, а на другом ПК даже на 300%! Очень ценится - person Tim_Utrecht; 29.05.2015

Пример есть в эту ветку, которая может удовлетворить ваши потребности. Вам нужно будет использовать replicate из функции lapply в base.

 replicate(N, statefun(initialState, nSteps, nStates))
person erasmortg    schedule 22.05.2015
comment
Думаю, у вас еще нет прав на комментирование, но, к сожалению, это больше подходит для комментария, чем для ответа. - person Frank; 22.05.2015
comment
Да, это была именно моя проблема, но я решил, что это лучший способ привлечь внимание к этой теме (похоже, это очень похожая проблема). - person erasmortg; 22.05.2015