logo标签列表

优化计算中线程数量的算法

multithreadingalgorithmgenetic-algorithmmathematical-optimizationevolutionary-algorithm
4
我正在执行一个操作，我们称之为CalculateSomeData。CalculateSomeData在连续的“代”中运行，编号为1..x。整个运行中的代数由CalculateSomeData的输入参数固定，并且是先验已知的。单个代需要30分钟到2小时不等的时间才能完成。其中一部分可变性是由于输入参数引起的，这是无法控制的。但是，其中一部分可变性是由于硬件容量、其他进程的CPU负载、网络带宽负载等原因引起的。每个代可以控制使用CalculateSomeData的线程数。现在这是固定的，可能不是最优的。我想跟踪每个代所需的时间，然后有一些算法，通过该算法我可以调整线程数，以便每个连续的代都可以改善上一个代的计算时间（最小化时间）。我应该使用什么方法？遗传算法有多适用？直觉告诉我范围会相当紧密-在双四核处理器机器上可能是1到16个线程。
非常感谢任何指针，伪代码等。
我猜你没有使用 C# 或者 Microsoft C++，那么可以使用 TPL（http://msdn.microsoft.com/en-us/library/dd460717.aspx），它可以协调线程核心。 - Iain
我实际上正在使用C# / TPL。CalculateSomeData并不完全在.NET中发生。我使用一些.NET与Excel的互操作。我发现TPL是添加并行处理的便捷方式，但对于我的特定计算，我发现它在选择正确数量的线程方面做得很糟糕。它通常尝试太多。我更喜欢指定线程数，并有一个调整线程数直到优化的算法。 - Suraj
TPL内置了调整功能，但它针对的是CPU密集型活动。我猜想，如果您有网络密集型活动或随时间改变其工作负载特性的活动，则内置的调整可能效果不佳。 - Albin Sunnanbo
对我来说，这个问题不太清楚：你只是想让每一代的运行速度比上一代更快吗？此外，据我所了解，你所提到的“generations”与进化编程没有任何关系，你使用相同的术语可能会引起困惑，因为这确实是遗传算法术语中使用的一个词。 - JohnIdol
@Johnldol - 我正在尝试通过优化线程参数来最小化每个生成所需的时间。因此，是的，每个生成应该理想情况下比之前更快地运行，直到我找到最佳设置为止。我在GA上发布了帖子，因为我认为GA算法可能会解决这个问题。你是对的，可能会有一些混淆，关于我在生成方面的意思和GA定义。最广泛地说，一个生成不就是一组计算被聚集在一起吗？ - Suraj
3个回答
2

如果计算完全受限于 CPU，线程数应该等于机器上的核心数。这样可以最小化上下文切换的数量。

如果您的计算涉及 I/O、网络、同步或其他阻塞执行的内容，您必须找到限制资源并测量利用率。您需要监视利用率，并逐渐添加更多线程，直到利用率接近100%。您应该尽可能少地使用线程来饱和您的限制资源。

1
嗨，阿尔宾 - 相比于仅测量一代所需的时间并通过优化算法将其最小化，这似乎相当复杂。计算受CPU、磁盘、网络的限制，很难说比例是多少以及随着时间的推移如何变化。但我知道一件事情 - 一代运行得越快，就越好...那么解决方案不应该简单地与一代时间相关联吗？ - Suraj
@SFun28 - 如果你为每个核心运行2个线程，那么会发生什么？你会得到接近100%的CPU利用率吗？ - Albin Sunnanbo
@Donal Fellows - 我更倾向于避免手动调整。我可能会坐在那里数小时或数天来微调它。肯定有一个简单的算法比我更有效地选择正确的线程数量。 - Suraj
@SFun28：自动调优比看起来更难，通常可以通过草稿计算手动进行第一次调优尝试。然后测量，看它是否足够好，如果是的话，停止调整。最优性很难实现，但通常在一两次尝试中就可以达到足够的水平（特别是有一点经验的情况下）。 - Donal Fellows
2
如何使用进化算法。
首先猜一个答案。每个CPU核心1个线程似乎不错，但这取决于手头的任务。
测量每一代中每个任务的平均时间。将其与上一代所用的时间进行比较。（假设第0代的时间无限长且没有线程）。
如果最近一代的任务平均时间比前一代好，则继续以与上一步相同的方向更改线程数（因此，如果上一代比前一代有更多线程，则为新一代添加一个线程，但如果它少了一个，则使用一个较少的线程（显然有一个下限为1个线程）。
如果最近一代的任务平均时间比前一代长，则以相反的方向更改线程数（因此，如果增加线程数量导致时间变差，则下次使用一个较少的线程）。
只要最佳线程数不太接近1，那么您可能会在3个值之间振荡，这些值都相当接近最佳值。如果您需要处理大量的代，请明确检测此情况并将自己锁定在中央值上。
Mitchell - 这正是我在寻找的！由于我们正在最小化时间，我认为我们可以假设 gen 0 的时间是无限的。gen 0 的线程数不是严格必要的，因为 gen 1 总是比 gen 0 好（< 无穷大）。当然，由于您最初设置了 # 线程 = # 核心，所以系统必须随机决定是否增加或减少 gen 2 的线程数（因为在完成 2 代之前没有“与上一步相同方向”的概念）。这听起来正确吗？ - Suraj
是的，你说得对。对于 G0 来说，无限时间效果更好。我表达的意思是，我们应该始终将线程增加 1 个来处理 G2。 - Bill Michell
你所描述的算法更像是贪心爬山法，而不是进化算法。在这种情况下，它可能是一个好的解决方案，但我不明白这种方法如何是进化的。 - JohnIdol
@JohnIdol 我猜每一代只有一次试验，所以"进化"可能不是一个好词。 - Bill Michell
1
你应该将你的世代分成许多小任务并将它们放入队列中。每个核心生成一个线程，让每个线程获取一个任务来完成，并重复执行。
你需要比核心更多的任务，以确保在一代结束时不会只有一个任务在运行，而其他所有线程都处于空闲状态。这就是如果像Albin建议的那样设置#tasks = #threads = #cores，可能会发生的情况（除非你可以确保所有任务花费的时间完全相同）。
你也可能不希望拥有比核心更多的线程。上下文切换并不是非常昂贵，但同时活动的任务超过#cores所带来的更大的缓存占用可能会对你造成影响（除非你的任务使用非常少的内存）。
嗨，Keith - 请查看我的问题和回复Albin的评论。每个核心产生一个线程很简单（我现在实际上正在这样做），但我认为这是非最优的。 - Suraj
如果你的计算中有部分是IO绑定的，那么你可能需要使用更多的线程。但你不需要太多，像#cores + #disk heads这样的数量就足够了。 - Keith Randall
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接