分叉连接优化

我想要的是

我想致力于 fork/join 算法的优化。我所说的优化只是指计算最佳线程数，或者如果您愿意的话 - 计算SEQUENTIAL_THRESHOLD（参见下面的代码）。

// PSEUDOCODE
Result solve(Problem problem) { 
    if (problem.size < SEQUENTIAL_THRESHOLD)
        return solveSequentially(problem);
    else {
        Result left, right;
        INVOKE-IN-PARALLEL { 
            left = solve(extractLeftHalf(problem));
            right = solve(extractRightHalf(problem));
        }
        return combine(left, right);
    }
}

我怎么想象

例如，我想计算大数组的乘积。然后我只评估所有组件并获得最佳线程数量：

SEQUENTIAL_THRESHOLD = PC * IS / MC（仅举例）

PC- 处理器核心数量；IS- 常量，表示一个处理器核心的最佳数组大小和对数据最简单的操作（例如读取）；MC- 运营成本成倍增加；

假设MC=15； PC = 4，IS = 10000；SEQUENTIAL_THRESHOLD = 2667。如果子任务数组大于 2667，我会分叉它。

广泛的问题

1. 是否有可能以这种方式制定顺序阈值公式？
2. 是否可以对更复杂的计算完成相同的操作：不仅适用于数组/集合和排序的操作？

狭义问题：

是否已经存在一些关于计算的调查SEQUENTIAL_THRESHOLD用于数组/集合/排序？他们是如何做到这一点的？

2014 年 3 月 7 日更新：

1. 如果无法编写用于阈值计算的单个公式，我可以编写一个实用程序来在 PC 上执行预定义的测试，然后获取最佳阈值吗？难道这也是不可能的吗？
2. Java 8 Streams API 可以做什么？它能帮助我吗？ Java 8 Streams API 是否消除了 Fork/Join 的需要？

除非您熟悉执行环境，否则绝对没有办法计算适当的阈值。我在 sourceforge.net 上维护一个 fork/join 项目，这是我在大多数内置函数中使用的代码：

private int calcThreshold(int nbr_elements, int passed_threshold) {

  // total threads in session
  // total elements in array
  int threads = getNbrThreads();
  int count   = nbr_elements + 1;

  // When only one thread, it doesn't pay to decompose the work,
  //   force the threshold over array length
  if  (threads == 1) return count;    

  /*
   * Whatever it takes
   * 
   */
  int threshold = passed_threshold;

  // When caller suggests a value
  if  (threshold > 0) {

      // just go with the caller's suggestion or do something with the suggestion

  } else {
      // do something usful such as using about 8 times as many tasks as threads or
      //   the default of 32k
      int temp = count / (threads << 3);
      threshold = (temp < 32768) ? 32768 : temp;

  } // endif    

  // whatever
  return threshold;

}

3月9日编辑：

您怎么可能拥有一个通用实用程序，不仅可以了解处理器速度、可用内存、处理器数量等（物理环境），还可以了解软件的意图？答案是你不能。这就是为什么您需要为每个环境制定一个例程。上面的方法是我用于基本数组（向量）的方法。我使用另一种方法进行大多数矩阵处理：

// When very small, just spread every row
if  (count < 6) return 1;

// When small, spread a little 
if  (count < 30) return ((count / (threads << 2) == 0)? threads : (count / (threads << 2)));  

// this works well for now
return ((count / (threads << 3) == 0)? threads : (count / (threads << 3))); 

就 Java8 流而言：它们在底层使用 F/J 框架，并且您无法指定阈值。