2

我将设计一个简单的数据分析工具,通过有向图处理不同类型的数据。有向图在某种程度上可以由用户定制。每个节点将包括对通过的数据的日志记录、分析和数学运算。该图在许多方面与神经网络相似,只是在每个节点都有额外的处理。一些节点对通过的数据元素进行简单的操作,而其他节点具有复杂的算法。

如何在这个有向图中对处理进行多线程处理,以便以最快和最有效的方式从图中得到结果?内存在这里不是问题,初始化此任务所需的时间也不是问题。

我想到了几种不同的方法来多线程工作:

  • 每个线程实例都“跟随”进入此图中开始节点的每个数据元素。线程在通过每个节点时将保留此数据元素,并在每个节点上调用处理方法,一直沿树向下。这基本上需要每个进入系统的数据元素一个线程。当然,一旦数据元素通过了整个系统,线程就会被回收。这里的问题是当一个节点上存在两个传出边时——线程需要同时跟随两者(这是否意味着从线程池中拉出一个新线程?)。

  • 每个节点创建一个线程,并在每个图形边缘上创建一个数据缓冲区。节点上的工作线程将不断检查以在一个线程需要更长的时间处理数据的实例中保存数据。这种方法的问题是缓冲区固有的“轮询”以获得足够的数据来开始处理它——也许为简化任何图形配置的数据流付出了很小的代价。

谁能想到更好的方法,或者你推荐哪一个?我正在寻找通过系统的最小延迟以及不断处理传入数据流的能力。

谢谢!布雷特

4

1 回答 1

3

首先,产生无限数量的线程(例如每个节点的线程)不是一个好主意。通常,您最多希望拥有比 CPU 内核多 1.5-3 倍的线程(例如,对于四核来说,6-12 个线程)。

我建议使用线程池和任务。在这种情况下,您的问题可以重新表述为您的任务应该具有的大小。

您提到的两种方法都是有效的,并且各有利弊。

每个数据输入一个任务应该很容易实现,因为图形处理算法将保持单线程。线程之间的上下文切换、同步和数据传递的开销几乎为零。

当一个节点上有两条出边时,这个单一的任务必须同时跟随它们。这是所有图遍历算法的标准部分,例如深度优先搜索广度优先搜索

如果您的图有许多可以并行处理的“分支”,每个图节点一个任务可以改善延迟。然而,这种方法需要更复杂的图形处理设计,并且线程同步的开销会更高。实际上,多线程的成本可能高于并行处理图所获得的好处。

当一个节点上有两个出边时,您可以在线程池上创建两个新任务和队列。(或将一项任务排队并继续处理另一项。)

更困难的问题是当一个节点上有两个传入边时。处理节点的任务必须等到两条边的数据都可用。

结论:我个人会从第一个选项(每个数据输入一个任务)开始,看看你能用它走多远。

于 2012-03-04T09:36:18.220 回答