multithreading - 是否有最小化线程数的搜索算法？

Question

我使用的是 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 个线程作为搜索结果。但是，对于只有一个最小值的其他情况，该算法找到了一个非常接近预期值的值。

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

Answer 1

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

看起来您应该尝试做的只是找到获得性能限制所需的最小线程数。不要查看 1-240 个线程，而是从 240 个线程开始并减少线程数，直到您可以为性能限制设置一个下限。然后，您可以从下限开始计算，这样您就可以找到最小值而无需越过它。如果您没有预定义的性能限制，则可以根据 yield 递减动态计算一个。

1. 只要不超过性能限制，线程数减半(从最大线程数开始)。超出性能限制的数字是所需线程数的下限。
2. 从线程数 Z 的下限开始，如果可以在不超出性能限制的情况下添加 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.

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