studio - parallel r

¿Por qué foreach% dopar% se vuelve más lento con cada nodo adicional?

Question

Escribí una simple multiplicación de matrices para probar las capacidades de multihilo / paralelización de mi red y noté que el cálculo era mucho más lento de lo esperado.

La prueba es simple: multiplica 2 matrices (4096x4096) y devuelve el tiempo de cálculo. Ni las matrices ni los resultados se almacenan. El tiempo de cálculo no es trivial (50-90 seg, dependiendo de su procesador).

Las Condiciones : Repetí este cálculo 10 veces usando 1 procesador, dividí estos 10 cálculos en 2 procesadores (5 cada uno), luego 3 procesadores, ... hasta 10 procesadores (1 cálculo para cada procesador). Esperaba que el tiempo total de cómputo disminuyera en etapas, y esperaba que 10 procesadores completaran los cálculos 10 veces más rápido de lo que se necesita para que un procesador haga lo mismo.

Los resultados : En lugar de eso, lo que obtuve fue solo una reducción de 2 veces en el tiempo de cálculo, que es 5 veces MÁS BAJO de lo esperado.

Cuando calculé el tiempo de cálculo promedio por nodo, esperaba que cada procesador computara la prueba en la misma cantidad de tiempo (en promedio) independientemente del número de procesadores asignados. Me sorprendió ver que el simple hecho de enviar la misma operación a un procesador múltiple estaba ralentizando el tiempo de cálculo promedio de cada procesador.

¿Puede alguien explicar por qué ocurre esto?

Tenga en cuenta que esta pregunta NO es un duplicado de estas preguntas:

foreach% dopar% más lento que para loop

o

¿Por qué el paquete paralelo es más lento que el simple uso?

Debido a que el cálculo de la prueba no es trivial (es decir, 50-90 segundos no 1-2segundos) y porque no hay comunicación entre los procesadores que puedo ver (es decir, no se devuelven ni almacenan resultados que no sean el tiempo de cálculo).

He adjuntado los scripts y funciones a continuación para la replicación.

library(foreach); library(doParallel);library(data.table)
# functions adapted from
# http://www.bios.unc.edu/research/genomic_software/Matrix_eQTL/BLAS_Testing.html

Matrix.Multiplier <- function(Dimensions=2^12){
  # Creates a matrix of dim=Dimensions and runs multiplication
  #Dimensions=2^12
  m1 <- Dimensions; m2 <- Dimensions; n <- Dimensions;
  z1 <- runif(m1*n); dim(z1) = c(m1,n)
  z2 <- runif(m2*n); dim(z2) = c(m2,n)
  a <- proc.time()[3]
  z3 <- z1 %*% t(z2)
  b <- proc.time()[3]
  c <- b-a
  names(c) <- NULL
  rm(z1,z2,z3,m1,m2,n,a,b);gc()
  return(c)
}

Nodes <- 10
Results <- NULL
for(i in 1:Nodes){
  cl <- makeCluster(i)
  registerDoParallel(cl)
  ptm <- proc.time()[3]
  i.Node.times <- foreach(z=1:Nodes,.combine="c",.multicombine=TRUE, 
                          .inorder=FALSE) %dopar% {
                            t <- Matrix.Multiplier(Dimensions=2^12)
                          }
  etm <- proc.time()[3]
  i.TotalTime <- etm-ptm
  i.Times <- cbind(Operations=Nodes,Node.No=i,Avr.Node.Time=mean(i.Node.times),
                   sd.Node.Time=sd(i.Node.times),
                   Total.Time=i.TotalTime)
  Results <- rbind(Results,i.Times)
  rm(ptm,etm,i.Node.times,i.TotalTime,i.Times)
  stopCluster(cl)
}
library(data.table)
Results <- data.table(Results)
Results[,lower:=Avr.Node.Time-1.96*sd.Node.Time]
Results[,upper:=Avr.Node.Time+1.96*sd.Node.Time]
Exp.Total <- c(Results[Node.No==1][,Avr.Node.Time]*10,
               Results[Node.No==1][,Avr.Node.Time]*5,
               Results[Node.No==1][,Avr.Node.Time]*4,
               Results[Node.No==1][,Avr.Node.Time]*3,
               Results[Node.No==1][,Avr.Node.Time]*2,
               Results[Node.No==1][,Avr.Node.Time]*2,
               Results[Node.No==1][,Avr.Node.Time]*2,
               Results[Node.No==1][,Avr.Node.Time]*2,
               Results[Node.No==1][,Avr.Node.Time]*2,
               Results[Node.No==1][,Avr.Node.Time]*1)
Results[,Exp.Total.Time:=Exp.Total]

jpeg("Multithread_Test_TotalTime_Results.jpeg")
par(oma=c(0,0,0,0)) # set outer margin to zero
par(mar=c(3.5,3.5,2.5,1.5)) # number of lines per margin (bottom,left,top,right)
plot(x=Results[,Node.No],y=Results[,Total.Time],  type="o", xlab="", ylab="",ylim=c(80,900),
     col="blue",xaxt="n", yaxt="n", bty="l")
title(main="Time to Complete 10 Multiplications", line=0,cex.lab=3)
title(xlab="Nodes",line=2,cex.lab=1.2,
      ylab="Total Computation Time (secs)")
axis(2, at=seq(80, 900, by=100), tick=TRUE, labels=FALSE)
axis(2, at=seq(80, 900, by=100), tick=FALSE, labels=TRUE, line=-0.5)
axis(1, at=Results[,Node.No], tick=TRUE, labels=FALSE)
axis(1, at=Results[,Node.No], tick=FALSE, labels=TRUE, line=-0.5)
lines(x=Results[,Node.No],y=Results[,Exp.Total.Time], type="o",col="red")
legend(''topright'',''groups'',
       legend=c("Measured", "Expected"), bty="n",lty=c(1,1),
       col=c("blue","red"))
dev.off()

jpeg("Multithread_Test_PerNode_Results.jpeg")
par(oma=c(0,0,0,0)) # set outer margin to zero
par(mar=c(3.5,3.5,2.5,1.5)) # number of lines per margin (bottom,left,top,right)
plot(x=Results[,Node.No],y=Results[,Avr.Node.Time],  type="o", xlab="", ylab="",
     ylim=c(50,500),col="blue",xaxt="n", yaxt="n", bty="l")
title(main="Per Node Multiplication Time", line=0,cex.lab=3)
title(xlab="Nodes",line=2,cex.lab=1.2,
      ylab="Computation Time (secs) per Node")
axis(2, at=seq(50,500, by=50), tick=TRUE, labels=FALSE)
axis(2, at=seq(50,500, by=50), tick=FALSE, labels=TRUE, line=-0.5)
axis(1, at=Results[,Node.No], tick=TRUE, labels=FALSE)
axis(1, at=Results[,Node.No], tick=FALSE, labels=TRUE, line=-0.5)
abline(h=Results[Node.No==1][,Avr.Node.Time], col="red")
epsilon = 0.2
segments(Results[,Node.No],Results[,lower],Results[,Node.No],Results[,upper])
segments(Results[,Node.No]-epsilon,Results[,upper],
         Results[,Node.No]+epsilon,Results[,upper])
segments(Results[,Node.No]-epsilon, Results[,lower],
         Results[,Node.No]+epsilon,Results[,lower])
legend(''topleft'',''groups'',
       legend=c("Measured", "Expected"), bty="n",lty=c(1,1),
       col=c("blue","red"))
dev.off()

EDITAR: Respuesta @Hong comentario de Ooi

Utilicé lscpu en UNIX para obtener;

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                30
On-line CPU(s) list:   0-29
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             30
NUMA node(s):          4
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 63
Model name:            Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz
Stepping:              2
CPU MHz:               2394.455
BogoMIPS:              4788.91
Hypervisor vendor:     VMware
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              20480K
NUMA node0 CPU(s):     0-7
NUMA node1 CPU(s):     8-15
NUMA node2 CPU(s):     16-23
NUMA node3 CPU(s):     24-29

EDITAR: Respuesta al comentario de @Steve Weston.

Estoy usando una red de máquina virtual (pero no soy el administrador) con acceso a hasta 30 clústeres. Corrí la prueba que sugeriste. Abrí 5 sesiones R y ejecuté la multiplicación de matrices en 1,2 ... 5 simultáneamente (o tan rápido como pude tabular y ejecutar). Obtuvo resultados muy similares a los anteriores (re: cada proceso adicional ralentiza todas las sesiones individuales). Tenga en cuenta que verifiqué el uso de la memoria usando top y htop y el uso nunca excedió el 5% de la capacidad de la red (~ 2.5 / 64Gb).

CONCLUSIONES:

El problema parece ser R específico. Cuando ejecuto otros comandos de subprocesos múltiples con otro software (por ejemplo, PLINK ) no me encuentro con este problema y el proceso paralelo se ejecuta como se esperaba. También he intentado ejecutar lo anterior con Rmpi y doMPI con los mismos resultados (más lentos). El problema parece estar relacionado con R sesiones / comandos paralelizados en la red de la máquina virtual. Lo que realmente necesito ayuda es cómo identificar el problema. Problema similar parece ser señalado here

Answer 1

Considero que el tiempo de multiplicación por nodo es muy interesante porque los tiempos no incluyen la sobrecarga asociada con el bucle paralelo, sino solo el tiempo para realizar la multiplicación de matrices, y muestran que el tiempo aumenta con el número de multiplicaciones de matrices. ejecutándose en paralelo en la misma máquina.

Puedo pensar en dos razones por las que eso podría suceder:

1. El ancho de banda de memoria de la máquina está saturado por las multiplicaciones de la matriz antes de que se agoten los núcleos;
2. La multiplicación de matrices es multihilo.

Puede probar la primera situación iniciando varias sesiones R (lo hice en varios terminales), creando dos matrices en cada sesión:

> x <- matrix(rnorm(4096*4096), 4096)
> y <- matrix(rnorm(4096*4096), 4096)

y luego ejecutando una multiplicación de matrices en cada una de esas sesiones aproximadamente al mismo tiempo:

> system.time(z <- x %*% t(y))

Idealmente, este tiempo será el mismo independientemente del número de sesiones R que utilice (hasta el número de núcleos), pero como la multiplicación de matrices es una operación que requiere bastante memoria, muchas máquinas se quedarán sin ancho de banda de memoria antes de que se agoten. Núcleos, haciendo que los tiempos aumenten.

Si su instalación R se construyó con una biblioteca matemática de múltiples subprocesos, como MKL o ATLAS, entonces podría estar usando todos sus núcleos con una sola multiplicación de matrices, por lo que no puede esperar un mejor rendimiento al usar varios procesos a menos que use múltiples computadoras

Puede usar una herramienta como "top" para ver si está usando una biblioteca matemática de múltiples subprocesos.

Finalmente, la salida de lscpu sugiere que está utilizando una máquina virtual. Nunca he realizado ninguna prueba de rendimiento en máquinas virtuales de varios núcleos, pero eso también podría ser una fuente de problemas.

Actualizar

Creo que la razón por la que las multiplicaciones de su matriz paralela se ejecutan más lentamente que una sola matriz de matriz es que su CPU no puede leer la memoria lo suficientemente rápido como para alimentar más de aproximadamente dos núcleos a toda velocidad, lo que me refiero como saturación del ancho de banda de su memoria . Si su CPU tiene suficientes cachés, puede evitar este problema, pero realmente no tiene nada que ver con la cantidad de memoria que tiene en su placa base.

Creo que esto es solo una limitación de usar una sola computadora para cálculos paralelos. Una de las ventajas de usar un clúster es que el ancho de banda de su memoria aumenta, al igual que su memoria total agregada. Entonces, si ejecutó una o dos multiplicaciones de matriz en cada nodo de un programa paralelo de múltiples nodos, no se encontraría con este problema en particular.

Suponiendo que no tenga acceso a un clúster, podría intentar realizar una evaluación comparativa de una biblioteca matemática de subprocesos múltiples como MKL o ATLAS en su computadora. Es muy posible que pueda obtener un mejor rendimiento al ejecutar una matriz de múltiples subprocesos en lugar de ejecutarlos en paralelo en varios procesos. Pero tenga cuidado al utilizar una biblioteca matemática de subprocesos múltiples y un paquete de programación paralelo.

También puedes intentar usar una GPU. Obviamente son buenos para realizar multiplicaciones de matrices.

Actualización 2

Para ver si el problema es específico de R, sugiero que haga una dgemm comparativa de la función dgemm , que es la función BLAS utilizada por R para implementar la multiplicación de matrices.

Aquí hay un programa de Fortran simple para comparar dgemm . Sugiero ejecutarlo desde múltiples terminales de la misma manera que describí para la evaluación comparativa de %*% en R:

      program main
      implicit none
      integer n, i, j
      integer*8 stime, etime
      parameter (n=4096)
      double precision a(n,n), b(n,n), c(n,n)
      do i = 1, n
        do j = 1, n
          a(i,j) = (i-1) * n + j
          b(i,j) = -((i-1) * n + j)
          c(i,j) = 0.0d0
        end do
      end do
      stime = time8()
      call dgemm(''N'',''N'',n,n,n,1.0d0,a,n,b,n,0.0d0,c,n)
      etime = time8()
      print *, etime - stime
      end

En mi máquina Linux, una instancia se ejecuta en 82 segundos, mientras que cuatro instancias se ejecutan en 116 segundos. Esto es consistente con los resultados que veo en R y con mi suposición de que esto es un problema de ancho de banda de memoria.

También puede vincular esto con diferentes bibliotecas BLAS para ver qué implementación funciona mejor en su máquina.

También puede obtener información útil sobre el ancho de banda de la memoria de la red de su máquina virtual utilizando pmbw - Paralelo de la memoria paralela de referencia , aunque nunca lo he usado.

Answer 2

Creo que la respuesta obvia aquí es la correcta. La multiplicación de matrices no es vergonzosamente paralela. Y no parece que hayas modificado el código de multiplicación en serie para paralelizarlo.

En cambio, estás multiplicando dos matrices. Debido a que la multiplicación de cada matriz es manejada por un solo núcleo, cada núcleo en exceso de dos simplemente está inactivo. El resultado es que solo se ve una mejora de velocidad de 2x.

Puedes probar esto ejecutando más de 2 multiplicaciones de matrices. Pero no estoy familiarizado con el marco foreach , doParallel (uso parallel framework parallel ) ni tampoco veo en su código para modificar esto para probarlo.

Una prueba alternativa es hacer una versión en paralelo de la multiplicación de matrices, que tomo prestada directamente de la computación paralela de Matloff para Data Science . Borrador disponible here , ver página 27

mmulthread <- function(u, v, w) {
  require(parallel)
  # determine which rows for this thread
  myidxs <- splitIndices(nrow(u), myinfo$nwrkrs ) [[ myinfo$id ]]
  # compute this thread''s portion of the result
  w[myidxs, ] <- u [myidxs, ] %*% v [ , ]
  0 # dont return result -- expensive
}
# t e s t on snow c l u s t e r c l s
test <- function (cls,  n = 2^5) {
  # i n i t Rdsm
  mgrinit(cls)
  # shared variables
  mgrmakevar(cls, "a", n, n)
  mgrmakevar(cls, "b", n, n)
  mgrmakevar(cls, "c", n, n)
  # f i l l i n some t e s t data
  a [ , ] <- 1:n
  b [ , ] <- rep (1 ,n)

  # export function
  clusterExport(cls , "mmulthread" )
  # run function
  clusterEvalQ(cls , mmulthread (a ,b ,c ))
  #print ( c[ , ] ) # not p ri n t ( c ) !
}


library(parallel)
library(Rdsm)

c1 <- makeCluster(1)
c2 <- makeCluster (2)
c4 <- makeCluster(4)
c8 <- makeCluster(8)

library(microbenchmark)

microbenchmark(node1= test(c1, n= 2^10),
           node2= test(c2, n= 2^10),
           node4= test(c4, n= 2^10),
           node8= test(c8, n= 2^10))



 Unit: milliseconds
  expr      min       lq     mean   median       uq      max neval  cld
 node1 715.8722 780.9861 818.0487 817.6826 847.5353 922.9746   100    d
 node2 404.9928 422.9330 450.9016 437.5942 458.9213 589.1708   100   c 
 node4 255.3105 285.8409 309.5924 303.6403 320.8424 481.6833   100 a   
 node8 304.6386 328.6318 365.5114 343.0939 373.8573 836.2771   100  b  

Como se esperaba, al paralelizar la multiplicación de matrices, sí vemos la mejora del gasto que queríamos, aunque la sobrecarga paralela es claramente extensa.

Answer 3

Supongo que ya ha sido respondida aquí? foreach% dopar% más lento que para loop

Quiero decir que es un poco de extrapolación de la misma respuesta. Así que básicamente el concepto se mantiene constante.

Aquí hay otro ejemplo donde el proceso ocurre en paralelo (secuencialmente o fuera de secuencia). La respuesta no tiene ninguna expectativa de ser combinada. Es simple reutilizar el mismo resultado al descartar la misma variable. (Exactamente como simple para bucle). Pero aún así el bucle se ralentiza en doParalelo. ¿ Por qué foreach ()% do% a veces es más lento que para?