首页 文章

是否有用于最小化线程数的搜索算法？

提问于
浏览 次
0

我正在使用Intel Xeon Phi协处理器，它具有多达240个线程，我正在努力减少用于特定应用程序的线程数（或最大化性能），同时在最佳执行时间的百分比内 . 例如，如果我有以下测量：

  • 主题|执行时间处理时间

  • 240 100 s

  • 200 105 s

  • 150 107 s

  • 120 109 s

  • 100 120 s

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

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

该算法的问题在于，首先这不一定是执行时间的排序数组，并且对于某些问题大小，穷举搜索结果显示两个不同的最小值，因此例如在一个中我获得80个线程处的最佳性能170，我希望能够返回80，而不是170个线程作为搜索的结果 . 但是，对于只有一个最小值的其他情况，算法会发现一个非常接近预期值的值 .

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

multithreading algorithm search execution-time xeon-phi

1 回答

  • 1

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

    看起来你应该尝试做的只是找到获得性能限制所需的最小线程数 . 而不是查看1-240个线程，从240个线程开始并减少线程数，直到您可以在性能限制上设置下限 . 然后，您可以从下限进行处理，以便您可以在不经过它的情况下找到min . 如果您没有预定义的性能限制，那么您可以根据收益递减计算一个 .

    • 只要尚未超出性能限制，即线程数的一半（以最大线程数开始） . 超出性能限制的数字是所需线程数的下限 .

    • 从线程数的下限开始，Z，如果可以在不超出性能限制的情况下添加m个线程 . 将添加的线程数重复加倍，直到达到性能限制 . 如果添加线程在性能限制范围内，则减去最后一次添加并重置要添加到m的线程数 . 如果即使只是添加m都在限制范围内，那么添加最后m个线程并返回线程数 .

    可以更清楚地给出一个过程看起来像是一步一步的例子 . 其中Passed意味着线程数超出性能限制，失败意味着它们处于性能限制或内部 .

    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.

    它's a bit inefficient, but it does find the minimium number of threads (>= Z) required to obtain the performance bound to within an error of m-1 threads and requiring only O(log (N-Z)) tests. This should be enough in most cases, but if it isn' t只是跳过步骤1并使用Z = m . 除非增加线程数量，否则当Z非常小时，运行时间会导致非常慢的运行时间 . 在这种情况下，执行步骤1并使用interpolation可以了解运行时间随着线程数量的减少而增加的速度，这对于确定良好的性能限制（如果没有给出）也很有用 .

    回复于

相关问题