0

我正在使用 Intel Xeon Phi 协处理器，它有多达 240 个线程，并且我正在努力将用于特定应用程序的线程数最小化（或最大限度地提高性能），同时保持在最佳执行时间的百分比范围内。例如，如果我有以下测量值：

  • 主题 | 执行时间处理时间
  • 240 100 秒
  • 200 105 秒
  • 150 107 秒
  • 120 109 秒
  • 100 120 秒

我想选择 120 到 150 之间的线程数，因为那里的“性能曲线”似乎稳定了，并且执行时间的减少并不那么显着（在这种情况下，大约是最佳测量时间的 15%。我这样做了使用详尽的搜索算法（测量从 1 到 240 个线程），但我的问题是线程数量较少（显然取决于问题的大小）需要很长时间。

为了尽量减少测量次数，我开发了一种“二分搜索”算法。基本上我有一个上限和下限（从 0 和 240 个线程开始），我取中间的值并在 240 处测量它。我得到两个值之间的百分比差异，如果它在 15% 以内（这个值是在分析详尽搜索的结果后选择）我分配了一个新的下限或上限。如果差异大于 15%，那么这是一个新的下限 (120-240)，如果它更小，那么它是一个新的上限 (0-120)，如果我得到更好的执行时间，我将其存储为最佳执行时间。

该算法的问题在于，首先这不一定是执行时间的排序数组，并且对于某些问题大小，详尽的搜索结果显示了两个不同的最小值，因此例如在一个中，我在 80 个线程和170，我希望能够返回 80，而不是 170 作为搜索结果的线程。然而，对于只有一个最小值的其他情况，该算法找到了一个非常接近预期值的值。

如果有人有更好的想法或知道可以帮助我的现有搜索算法或启发式方法，我将不胜感激。

4

1 回答 1

1

我认为您的目标是为最少的线程获得最佳的相对性能，同时仍然根据可能的最佳性能的系数 (<=1) 保持对性能的一些限制。IE：如果系数为 0.85，则性能应不低于使用所有线程的性能的 85%。

看起来您应该尝试做的只是找到获得性能限制所需的最小线程数。与其查看 1-240 个线程，不如从 240 个线程开始并减少线程数，直到您可以设置性能限制的下限。然后，您可以从下限开始向上计算，这样您就可以在不超过最小值的情况下找到最小值。如果您没有预定义的性能界限，那么您可以根据收益递减动态计算一个。

  1. 只要没有超过性能限制，线程数减半（从最大线程数开始）。超过性能限制的数字是所需线程数的下限。
  2. 从线程数的下限 Z 开始，如果可以在不超出性能限制的情况下添加 m 个线程，则添加 m 个线程。将添加的线程数重复加倍，直到在性能限制范围内。如果添加的线程在性能限制范围内，则减去最后的添加并将要添加的线程数重置为 m。如果即使只是添加 m 就在限制范围内，则添加最后的 m 个线程并返回线程数。

逐步举例说明该过程的外观可能会更清楚。其中 Passed 意味着线程数超出了性能限制，而 failed 意味着它们处于性能限制或在性能限制之内。

Try adding 1m (Z + 1m). Passed. Threads = Z + m.
Try adding 2m (Z + 3m). Passed. Threads = Z + 3m.
Try adding 4m (Z + 7m). Failed. Threads = Z + 3m. Reset.
Try adding 1m. Passed. Threads = Z + 4m.
Try adding 2m. Passed. Threads = Z + 6m.
Z + 7m failed earlier so reset. 
  Comparisons/lookups are cheap, use them to prevent duplication of work.
Try adding 1m. Failed. Threads = Z + 6m. Reset.
Cannot add less than 1m and still in outside of performance limit.
The solution is Z + 7m threads. 
  Since Z + 6m is m threads short of the performance limit.

它的效率有点低，但它确实找到了获得绑定在 m-1 个线程错误内的性能所需的最小线程数 (>= Z)，并且只需要 O(log (NZ)) 测试。在大多数情况下，这应该足够了，但如果不只是跳过步骤 1 并使用 Z=m。除非快速增加线程数会减少运行时间，否则当 Z 非常小时会导致运行时间非常慢。在这种情况下，执行步骤 1 并使用插值可以了解运行时间随着线程数量的减少而增加的速度，如果没有给出良好的性能限制，这对于确定良好的性能限制也很有用。

于 2014-05-27T00:33:01.260 回答