叉/加入：最佳的线程数

Question

任务定义：我需要映射一个非常大的阵列。例如，让我们来看一个findMax()函数。所以任务是尽可能快地完成这个任务（这意味着并行）。

HW：我有8个内核他们每个人都有2个超级线程

public static void main(String... args) { 
    int maxThreadAmount = Runtime.getRuntime().availableProcessors(); // GET 8 
} 

解决方案＃1：只需运行任务分成N个线程。其中N应该是一些最佳数字。

Question＃1： Next right：int optimalThreadAmount = maxThreadAmount - 1？

解决方案＃2：我想通过Fork/Join框架解决这个问题。如果输入过大，每个任务都会分成两个并行子任务。所以，我会得到这样的

    Find Max 
        [array] <---- +1 pending thread 
       /  \ 
       /  \ 
      Find Max  Find Max 
      [1/2 array]  [1/2 array] <-------- +2 pending threads 
      / \  / \ 
     /  \  .. .. 
     Find Max  Find Max 
    [1/4 array] [1/4 array]  <-------- +4 four pending threads 
    /  \  /\ 
    /  \  .. .. 
    Find Max Find Max 
    [1/8 array] [1/8 array] <----------- +8 active threads 

问题2：考虑到与叉/加入算法，我们会得到一堆待处理的线程这将是最佳线程数？

Answer 1

OK，我想你要映射x到，说的sqrt（x）的。你可以同时获得平方根，并将它们放入相应的数组中。但是，根据sqrt和阅读/写作menory所需的时间，您可能会使用两个线程使您的mem访问饱和。确保每个并发作业至少运行一个μs或分叉/连接开销变得过大。

Answer 2

线程的最佳数量应围绕核心机器具有的数量。但是，请记住，当你在两个子任务分解你的工作量，一个任务应该计算，另一个应该是分叉。这意味着你只在分割时创建一个额外的线程。

大多数分叉/连接算法伴随着一个顺序切断。当您达到某个条件时（例如，确定最大值为1000的数组），您切换到顺序算法（即逐个检查元素）。所以，如果我想猜最佳情况来计算你的问题我会说，此刻你已经分裂了14次，产生了16个线程，然后切换到顺序算法。这意味着每个内核都有一个线程正在运行，因此将保持忙碌状态。 （这个猜测假设你的内核有像超线程这样的东西，如果没有的话我会说8个线程）。

此外，不建议硬性化您给出的公式（int optimalThreadAmount = maxThreadAmount - 1），因为这意味着您认为该机器无所事事，并且可以使用所有线程。

我的猜测是，使用顺序截止的时候，你的最佳性能将围绕16个线程（在没有其他进程正在使用你的机器）。你可以为自己测试，总是最好的方法。你想调查的问题是，当你开始产生大量的线程时，每个线程的开销将变得明显。

Ps：使用fork/join的优点是您的代码将可以根据机器的内核数量进行扩展。更多的内核意味着更多的线程将并行运行。这意味着你的线程调度器可以让更多的线程工作。

编辑 那么，有什么是我应该为内核的给定数量的使用最好的截止？

那么，我的猜测会是你实现一个分叉/连接算法。你有一个顺序切断（即，一旦我的输入数组的大小为x，停止分叉和连接）。

当您知道在哪个系统上运行算法时，您可以运行基准测试。

对于连续截止x到y您运行您的代码。每次迭代您测量应用您的算法需要多长时间。这样做，你会看到哪种配置最适合你。

再说，如果你想快速和肮脏的方法，你可以做到以下几点：与p核心

机，输入数组的大小为s：

Sequential cutoff = s/8 

不过，我强烈建议如前所述，反对这一点。