Question Pourquoi for% dopar% est-il plus lent avec chaque nœud supplémentaire?


J'ai écrit une simple multiplication matricielle pour tester les capacités de multithreading / parallélisation de mon réseau et j'ai remarqué que le calcul était beaucoup plus lent que prévu.

Le test est simple: multipliez 2 matrices (4096x4096) et retournez le temps de calcul. Ni les matrices ni les résultats ne sont stockés. Le temps de calcul n'est pas trivial (50 à 90 secondes selon votre processeur).

Les conditions : J'ai répété ce calcul 10 fois en utilisant 1 processeur, scindé ces 10 calculs en 2 processeurs (5 chacun), puis 3 processeurs, ... jusqu'à 10 processeurs (1 calcul à chaque processeur). Je m'attendais à ce que le temps de calcul total diminue par étapes et je m'attendais à ce que 10 processeurs effectuent les calculs 10 fois aussi vite qu'il faut à un processeur pour faire la même chose.

Les resultats : Au lieu de cela, j'ai obtenu seulement une réduction de 2 fois le temps de calcul, soit 5 fois RALENTISSEZ que prévu.

enter image description here

Lorsque j'ai calculé le temps de calcul moyen par nœud, je m'attendais à ce que chaque processeur calcule le test dans le même laps de temps (en moyenne) quel que soit le nombre de processeurs affectés. J'ai été surpris de voir que le simple fait d'envoyer la même opération à plusieurs processeurs ralentissait le temps de calcul moyen de chaque processeur.

enter image description here

Quelqu'un peut-il expliquer pourquoi ceci est en train de se passer?

Notez que c'est la question est NE PAS une copie de ces questions:

% de dopar% plus lent que pour boucle

ou

Pourquoi le paquet parallèle est-il plus lent que la simple utilisation?

Parce que le calcul de test n'est pas trivial (c.-à-d. 50-90 secondes, pas 1-2 secondes), et parce qu'il n'y a pas de communication entre les processeurs que je puisse voir (c'est-à-dire qu'aucun résultat n'est renvoyé ou stocké).

J'ai joint les scripts et fonctions ci-dessous pour la réplication.

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()

EDIT: le commentaire de Response @Hong Ooi

j'ai utilisé lscpu sous UNIX pour obtenir;

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

EDIT: Réponse au commentaire de @Steve Weston.

J'utilise un réseau de machines virtuelles (mais je ne suis pas l'administrateur) avec un accès à 30 grappes. J'ai couru le test que vous avez suggéré. Ouverture de 5 sessions R et exécution simultanée de la multiplication matricielle sur 1,2 ... 5 (ou aussi rapidement que possible). Vous obtenez des résultats très similaires à avant (re: chaque processus supplémentaire ralentit toutes les sessions individuelles). Remarque j'ai vérifié l'utilisation de la mémoire en utilisant top et htop et l'utilisation n'a jamais dépassé 5% de la capacité du réseau (~ 2,5 / 64 Go).

enter image description here

CONCLUSIONS:

Le problème semble être spécifique à R. Lorsque j'exécute d'autres commandes multithread avec d'autres logiciels (par ex. PLINK) Je ne rencontre pas ce problème et le processus parallèle est exécuté comme prévu. J'ai aussi essayé d'exécuter ce qui précède avec Rmpi et doMPI avec les mêmes résultats (plus lents). Le problème semble être lié R sessions / commandes parallélisées sur le réseau de machines virtuelles. Ce dont j'ai vraiment besoin d'aide, c'est comment identifier le problème. Un problème similaire semble être signalé ici


18
2018-01-29 20:40


origine


Réponses:


Je trouve le temps de multiplication par nœud très intéressant car les timings n'incluent aucun des frais généraux associés à la boucle parallèle, mais seulement le temps nécessaire à la multiplication de la matrice, et montrent que le temps augmente avec le nombre de multiplications matricielles s'exécutant en parallèle sur la même machine.

Je peux penser à deux raisons pour lesquelles cela pourrait arriver:

  1. La bande passante mémoire de la machine est saturée par les multiplications de la matrice avant de manquer de cœurs;
  2. La multiplication de la matrice est multithread.

Vous pouvez tester la première situation en démarrant plusieurs sessions R (je l'ai fait dans plusieurs terminaux), en créant deux matrices dans chaque session:

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

puis exécuter une multiplication matricielle dans chacune de ces sessions à peu près au même moment:

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

Idéalement, ce temps sera le même quel que soit le nombre de sessions R utilisées (jusqu’au nombre de cœurs), mais comme la multiplication par matrice est une opération plutôt gourmande en mémoire, de nombreuses machines manqueront de bande passante mémoire avant de manquer de mémoire. noyaux, provoquant une augmentation des temps.

Si votre installation R a été construite avec une bibliothèque mathématique multithread, telle que MKL ou ATLAS, vous pouvez utiliser tous vos cœurs avec une seule multiplication de matrice, vous ne pouvez donc pas vous attendre à de meilleures performances en utilisant plusieurs processus, sauf si vous utilisez plusieurs ordinateurs.

Vous pouvez utiliser un outil tel que "top" pour voir si vous utilisez une bibliothèque mathématique multi-thread.

Enfin, la sortie de lscpu suggère que vous utilisez une machine virtuelle. Je n'ai jamais fait de test de performance sur des machines virtuelles multi-cœurs, mais cela pourrait aussi être une source de problèmes.


Mettre à jour

Je crois que la raison pour laquelle vos multiplications de matrices parallèles s'exécutent plus lentement qu'une multiplication par matrice unique est que votre processeur n'est pas capable de lire la mémoire assez rapidement pour alimenter plus de deux cœurs à pleine vitesse. . Si votre processeur avait suffisamment de caches, vous pourriez être en mesure d’éviter ce problème, mais cela n’a rien à voir avec la quantité de mémoire que vous avez sur votre carte mère.

Je pense que c'est juste une limitation de l'utilisation d'un seul ordinateur pour des calculs parallèles. L'un des avantages de l'utilisation d'un cluster réside dans le fait que votre bande passante mémoire augmente ainsi que votre mémoire agrégée totale. Donc, si vous exécutiez une ou deux multiplications matricielles sur chaque nœud d'un programme parallèle multi-nœuds, vous ne rencontreriez pas ce problème particulier.

En supposant que vous n’ayez pas accès à un cluster, vous pouvez essayer de comparer une bibliothèque mathématique multithread telle que MKL ou ATLAS sur votre ordinateur. Il est fort possible que vous obteniez de meilleures performances en utilisant une matrice multithread plutôt que de les exécuter en parallèle dans plusieurs processus. Mais soyez prudent lorsque vous utilisez à la fois une bibliothèque mathématique multi-thread et un package de programmation parallèle.

Vous pouvez également essayer d'utiliser un GPU. Ils sont évidemment bons pour effectuer des multiplications matricielles.


Mise à jour 2

Pour voir si le problème est spécifique à R, je suggère que vous compariez le dgemm function, qui est la fonction BLAS utilisée par R pour implémenter la multiplication matricielle.

Voici un simple programme Fortran à évaluer dgemm. Je suggère de l'exécuter à partir de plusieurs terminaux de la même manière que j'ai décrit pour l'analyse comparative %*% 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

Sur ma machine Linux, une instance s'exécute en 82 secondes, tandis que quatre instances s'exécutent en 116 secondes. Ceci est cohérent avec les résultats que je vois dans R et avec mon hypothèse qu'il s'agit d'un problème de bande passante mémoire.

Vous pouvez également lier ceci à différentes bibliothèques BLAS pour voir quelle implémentation fonctionne mieux sur votre machine.

Vous pouvez également obtenir des informations utiles sur la bande passante mémoire de votre réseau de machines virtuelles en utilisant pmbw - Benchmark de la bande passante de la mémoire parallèle, même si je ne l'ai jamais utilisé.


11
2018-01-30 20:04



Je pense que la réponse évidente ici est la bonne. La multiplication matricielle n'est pas trop parallèle. Et vous ne semblez pas avoir modifié le code de multiplication série pour le paralléliser.

Au lieu de cela, vous multipliez deux matrices. Étant donné que la multiplication de chaque matrice est probablement gérée par un seul cœur, chaque cœur dépassant deux est simplement inactif. Le résultat est que vous ne voyez qu'une amélioration de la vitesse de 2x.

Vous pouvez tester cela en exécutant plus de 2 multiplications de matrice. Mais je ne suis pas familier avec le foreach, doParallel framework (j'utilise parallel framework) et je ne vois pas non plus où dans votre code modifier cela pour le tester.

Un autre test consiste à faire une version parallélisée de la multiplication matricielle, que j'emprunte directement auprès de Matloff. Informatique parallèle pour la science des données. Projet disponible ici, voir page 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  

Comme prévu, en parallélisant la multiplication matricielle, nous voyons l’amélioration des dépenses que nous souhaitions, bien que les frais généraux parallèles soient clairement étendus.


2
2018-02-14 15:50



Je suppose que cela a déjà été répondu ici? % de dopar% plus lent que pour boucle

Je parle de l'extrapolation de la même réponse. Donc, fondamentalement, le concept reste constant.

Voici un autre exemple où le processus se déroule en parallèle (séquentiel ou hors séquence). La réponse ne s'attend pas à être combinée. Il est simple de réutiliser le même résultat en rejetant la même variable. (Exactement comme simple pour la boucle). Mais la boucle ralentit quand même Pourquoi foreach ()%% est-il parfois plus lent que pour?


0
2018-01-29 22:45