平行处理应用程序

我正在构建一个网络分布式并行处理应用程序,它在许多机器上使用CPU和GPU资源的组合。

应用程序必须在数千次迭代中对非常大的数据集执行一些计算量非常大的操作:

for step = 0 to requested_iterations
  for i = 0 to width
    for j = 0 to height
      for k = 0 to depth
        matrix[i,j,k] = G*f(matrix[i,j,k])

另外,矩阵操作必须同步执行:即,每次迭代都取决于紧接之前的帧结果。

这个专用网格中包含专用服务器和闲置台式机的硬件在不同机器间的性能差别很大。 我想知道什么是平衡整个系统工作量的最佳方法。

一些特质:

  • 网格应尽可能健壮。 有些模拟需要数周才能运行,如果100台机器中有一台脱机,就不必取消运行。

  • 一些较低端的机器(闲置但在有人登录时不得不醒来的桌面)可能随时加入并离开电网。

  • 专用服务器也可以加入和离开电网,但这是可预测的。

  • 到目前为止,我能够想到的最好的想法是:

  • 让每个节点追踪处理矩阵中的一组n个单元(单位时间内处理的单元)所需的时间,并将其报告给中央存储库。
  • 根据模拟的帧(整个网格)和问题域的总大小的总时间加权。 因此,每个节点将获得每单位工作单位(矩阵单元)表示的分数,以及表示其与网格其余部分的性能的标量评分。
  • 在每个框架上,根据这些分数分配工作量,以便每台机器尽可能接近同一时间。 如果机器A比机器B快100倍,那么它将在给定帧中接收100倍的矩阵单元来处理(假设矩阵尺寸足够大以保证包括额外的机器)。
  • 离开网格的节点(登录到的桌面等)将在其余节点之间重新分配其工作负载。
  • 或者

    将节点排列在树结构中,其中每个节点都有一个“权重”分配。 树中较高的节点根据其能力与其子女的能力相结合而具有权重。 这个重量是每帧调整的。 当一个节点失去了与其子的通信时,它使用一个缓存树形图来联系孤儿,并重新平衡其分支。

    如果它有所作为,该应用程序就是C#和OpenCL的组合。

    欢迎链接论文,示例应用程序,尤其是教程。

    编辑

    这不是功课。 我将我作为论文的一部分编写的模拟器变成了一个更有用的产品。 目前,工作是均匀分布的,没有考虑到每台机器的性能,也没有设备可以从加入或离开电网的机器中恢复。

    感谢您的出色,详细的回复。


    对于异构集群,我喜欢让每个处理器在处理器变得可用时请求新的作业。 实施涉及一个轻量级的服务器,可以一次处理多个请求(但通常只返回一个作业编号)。 实现可能会像这样:

  • 将工作分解成最小的组件(我们知道现在有1000个任务)
  • 启动一个网络服务器(最好使用超时UDP来避免网络拥塞),该服务器向上计数
  • 启动您的群集进程。
  • 每个流程都会问:“我应该执行哪个职位?” 服务器回复一个数字
  • 当过程结束时,它会要求下一个工作号码。 当所有任务完成后,服务器向进程返回-1,以便它们关闭。
  • 这是一个较轻的重量替代你上面的建议。 您的快速处理器仍然比慢速机器做更多的工作,但是您不必计算任务需要多长时间。 如果处理器因任何原因退出,它将停止询问任务。 您的服务器可能会在一段时间后选择回收任务编号。

    这几乎是集群调度程序自己可以完成的工作,除了处理器没有启动和关闭成本之外,所以您的个人任务可以更小而不会受到任何惩罚。


    我会去分散的解决方案。

    每个节点从中心挑选(没有给出)相同数量的工作。 经过一段时间的运行后,每个节点都能够itself计算平均的计算能力,并与其他人进行交流。

    毕竟每个节点都有一个每个节点平均计算能力的表格。 有了这些信息(甚至可以持续下去,为什么不呢?),每个节点都可以通过签署合同来“请求”更多权力的其他节点来委托其他节点。

    在每个过程开始之前,每个节点都必须发出有关“我开始做X”的广播信号。 一次完成总是播出:“我完成了X”。

    好吧,这并不容易 ,因为在你开始工作时会遇到这种情况,在你的硬盘出现故障之后,你将永远无法完成它。 其他人,尤其是那些正在等待你的结果的人应该弄清楚这一点,并从篮子中挑选你的工作,并从头开始。 这里用计时器来“ping”技术。

    不好:第一个调整时间可能会花费无关紧要的时间。

    好的:你将拥有几乎容错的解决方案。 离开他们一个星期,即使一些节点失败,你的网格仍然活着并且完成它的工作。

    多年前,我做了这样的事情,并取得了不错的成绩。 但它并不像你所描述的那么大。 实际上,规模是有所作为的。

    所以选择取决于你。

    希望这可以帮助。


    我不打扰在服务器级别跟踪这些统计信息。 你会引入相当多的开销。

    相反,控制服务器应该只保留一个工作单元列表。 当客户变得可用时,让它抓住下一个单位并处理它。 冲洗,重复。

    一旦给定矩阵的工作单元清单用尽,请允许重新分配当前不完整的工作单元。

    基于包含10个工作单元和5个服务器的矩阵的示例。

    同样快速,全部可用:

    服务器1检入并抓取单元1.这将在接下来的4台机器上进行(即:服务器2获取单元2 ...)当单元1完成时,服务器1抓住单元6。 一旦最后一个服务器检入,矩阵完成。

    低性能差异,全部可用:
    你再次开始循环,前5个单位被服务器获取。 但是,服务器1比其他服务器长30%。 这意味着服务器2将抓住单元6.等等。在某点服务器1将检入单元1,同时单元2到5将被完成并且将被分配6到10。 服务器1被分配单元6,因为它尚未完成。 但是,服务器2将在服务器1完成之前检入它已完成的工作。 没什么大不了的,就扔掉最后的结果吧。

    巨大的不同表现,全部可用
    你再次开始循环,前5个单位被服务器获取。 假设服务器1比其他服务器多花费400%的时间。 这意味着服务器2将抓取单元6等。在服务器2在单元6中检查之后,它将看到单元#1仍在处理中。 继续并将其分配给服务器2; 这将在服务器1返回之前完成。

    在这种情况下,您应该监控那些一直在报告工作的机器,并且不要进一步考虑。 当然,由于关机或个人使用,你必须为那些下线的人提供一些补贴。 也许某种类型的加权评级一旦下降到某个阈值以下,你就会拒绝进一步的工作; 也许评级会每隔一段时间重新设定一次,以允许从稳定状态重新平衡。

    机器消失
    这与上面列出的“巨大的不同表现”具有完全相同的计划。 唯一的区别是机器要么不会报告,要么会在一段未知的时间后报告。

    如果由于某种原因,您拥有的机器比单位多,那么会发生一件有趣的事情:多台服务器将被分配相同的工作单位。 你可以通过放置某种类型的延迟来停止这一点(比如一个单位在重新分配之前必须进行x分钟的处理)或者简单地允许它发生。 这应该被认为通过。


    我们做了什么? 首先,我们缓解了追踪个人表现的需要。 其次,我们已经允许机器消失,同时确保工作仍然完成。 第三,我们确保工作尽可能在最短的时间内完成。

    它比简单地根据性能将多个单元的块分配给机器更有趣; 但是,这可以使快速机器从网络中拔出,同时确保完全可恢复性。 哎呀,你可以杀死所有的机器,然后打开其中的一些机器,从中取出你离开的地方。

    链接地址: http://www.djcxy.com/p/54609.html

    上一篇: balancing in parallel processing application

    下一篇: How can I debug an OpenCL kernel in Xcode 4.1?