为什么 foreach %dopar% 每增加一个节点就会变慢？

我编写了一个简单的矩阵乘法来测试网络的多线程/并行化功能，我注意到计算速度比预期慢得多。

The Test很简单：乘以 2 个矩阵 (4096x4096) 并返回计算时间。矩阵和结果都不被存储。计算时间并非微不足道（50-90 秒，具体取决于您的处理器）。

条件：我使用 1 个处理器重复此计算 10 次，将这 10 个计算拆分为 2 个处理器（每个处理器 5 个），然后是 3 个处理器，...最多 10 个处理器（每个处理器 1 次计算）。我预计总计算时间会逐步减少，并且预计有 10 个处理器来完成计算10 times与一个处理器完成相同任务所需的速度一样快。

结果：相反，我得到的只是计算时间减少了 2 倍，即 5 倍SLOWER比预期的。

当我计算每个节点的平均计算时间时，我希望每个处理器以相同的时间（平均）计算测试，无论分配的处理器数量如何。我惊讶地发现，仅仅将相同的操作发送到多个处理器就会减慢每个处理器的平均计算时间。

谁能解释为什么会发生这种情况？

请注意，这是一个问题NOT这些问题的重复：

foreach %dopar% 比 for 循环慢 https://stackoverflow.com/questions/16963808/foreach-dopar-slower-than-for-loop/16964023#16964023

or

为什么并行包比仅使用 apply 慢？ https://stackoverflow.com/questions/14614306/why-is-the-parallel-package-slower-than-just-using-apply

因为测试计算并不简单（即 50-90 秒而不是 1-2 秒），并且因为我可以看到处理器之间没有通信（即除了计算时间之外没有返回或存储结果）。

我已附加以下脚本和函数以进行复制。

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

编辑：回复@Hong Ooi 的评论

I used lscpu在 UNIX 中获取；

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

编辑：回复@Steve Weston 的评论。

我正在使用一个虚拟机网络（但我不是管理员）最多可以访问 30 个集群。我运行了你建议的测试。打开 5 个 R 会话并同时在 1,2...5 上运行矩阵乘法（或者尽可能快地切换并执行）。得到与之前非常相似的结果（回复：每个额外的进程都会减慢所有单独的会话）。注意我使用检查内存使用情况top and htop并且使用量从未超过网络容量的 5% (~2.5/64Gb)。

结论：

这个问题似乎是 R 特有的。当我使用其他软件运行其他多线程命令时（例如PLINK https://www.cog-genomics.org/plink2）我没有遇到这个问题，并且并行进程按预期运行。我也尝试过运行上面的内容Rmpi and doMPI具有相同（较慢）的结果。问题似乎是相关的R虚拟机网络上的会话/并行命令。我真正需要帮助的是如何查明问题。似乎指出了类似的问题here https://stackoverflow.com/questions/41936951/r-foreach-dompi-reduced-speed-with-increased-iterations#comment71464282_41936951

我发现每个节点的乘法时间非常有趣，因为计时不包括与并行循环相关的任何开销，而仅包括执行矩阵乘法的时间，并且它们表明时间随着矩阵乘法的数量而增加在同一台机器上并行执行。

我可以想到可能发生这种情况的两个原因：

1. 在核心耗尽之前，机器的内存带宽会因矩阵乘法而饱和；
2. 矩阵乘法是多线程的。

您可以通过启动多个 R 会话（我在多个终端中执行此操作）来测试第一种情况，在每个会话中创建两个矩阵：

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

然后在每个会话中大约同时执行矩阵乘法：

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

理想情况下，无论您使用多少个 R 会话（最多核心数量），这个时间都是相同的，但由于矩阵乘法是一个相当内存密集型的操作，因此许多机器在耗尽内存带宽之前会耗尽内存带宽。核心，导致时间增加。

如果您的 R 安装是使用多线程数学库（例如 MKL 或 ATLAS）构建的，那么您可以使用所有内核进行单个矩阵乘法，因此您不能期望通过使用多个进程获得更好的性能，除非您使用多台计算机。

您可以使用“top”等工具来查看您是否正在使用多线程数学库。

最后，输出lscpu表明您正在使用虚拟机。我从未在多核虚拟机上进行过任何性能测试，但这也可能是问题的根源。

Update

我相信并行矩阵乘法比单个矩阵乘法运行得更慢的原因是你的 CPU 读取内存的速度不够快，无法全速为两个以上的内核提供数据，我将其称为内存带宽饱和。如果你的CPU有足够大的缓存，你也许能够避免这个问题，但它实际上与你主板上的内存量没有任何关系。

我认为这只是使用单台计算机进行并行计算的限制。使用集群的优点之一是内存带宽以及总聚合内存都会增加。因此，如果您在多节点并行程序的每个节点上运行一两次矩阵乘法，则不会遇到这个特定问题。

假设您无法访问集群，您可以尝试在计算机上对多线程数学库（例如 MKL 或 ATLAS）进行基准测试。运行一个多线程矩阵乘法很可能比在多个进程中并行运行它们获得更好的性能。但同时使用多线程数学库和并行编程包时要小心。

您也可以尝试使用 GPU。他们显然擅长执行矩阵乘法。

Update 2

要查看问题是否是 R 特定的，我建议您对dgemm函数，这是R用来实现矩阵乘法的BLAS函数。

这是一个简单的 Fortran 程序来进行基准测试dgemm。我建议按照我为基准测试描述的相同方式从多个终端执行它%*% in 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

在我的 Linux 机器上，一个实例运行需要 82 秒，而四个实例运行需要 116 秒。这与我在 R 中看到的结果一致，并且与我的猜测一致，这是一个内存带宽问题。

您还可以将其链接到不同的 BLAS 库，以查看哪种实现在您的计算机上效果更好。

您还可以使用以下命令获取有关虚拟机网络内存带宽的一些有用信息pmbw - 并行内存带宽基准 https://panthema.net/2013/pmbw/，虽然我从来没有用过它。