8

我最近写了很多关于并行计算和编程的文章，我确实注意到在并行计算方面出现了很多模式。注意到 Microsoft 已经发布了一个库以及 Microsoft Visual C++ 2010 社区技术预览版（名为 Parallel Patterns Library），我想知道您一直在使用和遇到哪些常见的并行编程模式可能值得记住？当您使用 C++ 编写并行程序时，您是否有任何遵循的习语和似乎不断出现的模式？

4

4 回答 4

17

图案：

  • 生产/消费者

    • 一个线程产生数据
    • 一个线程消费数据

  • 循环并行

    • 如果你能证明每个循环是独立的，那么
      每次迭代都可以在一个单独的线程中完成

  • 重新绘制线程

    • 其他线程确实工作并更新数据结构，但一个线程重新绘制屏幕。

  • 主事件线程

    • 多个线程可以生成事件
    • 一个线程必须处理事件（因为顺序很重要）
    • 应该尝试分离事件线程/重绘线程
      这（有助于）防止 UI 冻结
      但如果不小心可能会导致过度重绘。

  • 工作组

    • 一组线程等待队列上的作业。
    • 线程从队列中提取一个工作项（如果没有可用则等待）。
      线程在一个工作项上工作，直到完成
      一旦完成，线程将返回队列。
于 2008-11-01T18:38:14.647 回答
2

首先，您必须在共享内存计算和无共享计算之间做出选择。共享内存更容易，但不能很好地扩展 - 如果你要么使用 shared-nothing

a) 有一个集群，而不是一个多处理器系统，或者

b) 如果您有很多 CPU（例如 > 60），并且内存高度不均匀

对于共享内存，常见的解决方案是使用线程；它们作为一个概念很容易理解，并且在 API 中易于使用（但难以调试）。

对于无共享，您使用某种消息传递。在高性能计算中，MPI 被建立为消息传递中间件。

然后，您还需要为并行活动设计架构。最常见的方法（同样因为它很容易理解）是农夫模式（又名主从）。

于 2008-11-01T18:26:41.583 回答
2

并行执行模式

具有确定性模式的结构化并行编程是一种高级方法，主要基于循环并行执行模式的集合，通常称为算法骨架或并行构造，它抽象程序描述并隐藏低级多线程细节和并行性固有的许多复杂性来自程序员。

这些可重用的模式自动化了许多与范式相关的并行例程，例如同步、通信、数据分区或任务调度，并在内部处理它们。这种高级方法尝试使用更多抽象和更简单的方式来表达并行性并关注生产力和可编程性而不是性能的传统低级线程锁模型。

有许多常用的模式，例如：Map-Reduce、Fork-Join、Pipeline 或 Parallel Loop...

文件

“Structured Parallel Programming with Deterministic Patterns”是一篇讨论这些模式的论文。您还可以看到“MHPM：多尺度混合编程模型：灵活的并行化方法”，它描述了这种名为 XPU 的方法的 C++ 实现。

图书馆

XPU是一个基于任务的 C++ 库，由一组可重用的执行模式组成。它允许在单个同构编程模型内以多个粒度级别表达多种类型的并行性。它易于使用并说明了使用模式设计并行程序的兴趣。

例如，它允许表达：

  1. 任务并行模式：

    简单或分层的 Fork/Join 执行模式，具有自动检测和保护共享数据等功能。

  2. 数据并行模式：

    具有可扩展数据分区的并行循环模式。

  3. 时间并行模式：

    管道执行模式。

于 2012-12-12T15:06:39.350 回答
1

您拥有将并行性固定到程序部分的基础知识。C++17 得到了很多（例如 foreach、sort、find 和friends、map_reduce、map、reduce、prefix_sum 的并行版本......）请参阅C++ Extensions for Parallelism

然后你有像延续这样的项目。想想std::future但继续。实现这些的方法很少（boost现在有一个很好的方法，因为 std 没有 next(...) 或 then(...) 方法，但最大的好处是不必等待它做下一个任务

auto fut = async([]( ){..some work...} ).then( [](result_of_prev ){...more work} ).then... ;
fut.wait( );

后续任务之间缺乏同步很重要，因为任务/线程/...之间的通信会减慢并行程序的速度。

因此，基于任务的并行性非常好。使用任务调度程序，您只需传递任务并走开。他们可能有一些方法，比如信号量，来回传信息，但这不是强制性的。Intel Thread Building Blocks和Microsoft Parallel Pattern Library都有这方面的功能。

之后，我们就有了 fork/join 模式。它并不意味着为每个任务创建 N 个线程。只是你有这些 N 件，理想情况下是独立的，要做的事情（fork），并且当它们完成时在某处有一个同步点（join）。

auto semaphore = make_semaphore( num_tasks );
add_task( [&semaphore]( ) {...task1...; semaphore.notify( ); } );
add_task( [&semaphore]( ) {...task2...; semaphore.notify( ); } );
...
add_task( [&semaphore]( ) {...taskN...; semaphore.notify( ); } );
semaphore.wait( );

从上面你可以开始看到这是一个流程图的模式。未来是（A >> B >> C >> D），分叉连接是（A|B|C|D）。有了它，您可以将它们组合成一个图表。(A1>>A2|B1>>B2>>B3|C1|D1>>D2>>(E1>>E2|F1)) 其中 A1>>A2 表示 A1 必须先于 A2 而 A|B 表示 A 和 B可以同时运行。缓慢的部分位于事物相遇的图/子图的末尾。

目标是找到系统中不需要通信的独立部分。如上所述，并行算法几乎在所有情况下都比它们的顺序算法慢，直到工作负载变得足够高或大小变得足够大（假设通信不太健谈）。例如排序。在 4 核计算机上，您将获得大约 2.5 倍的性能，因为合并很繁琐，需要大量同步，并且在第一轮合并后无法使用所有核心。在 N 非常大的 GPU 上，可以使用效率较低的排序，比如 Bitonic，它最终会非常快，因为你有很多工作人员要为工作提供动力，每个人都安静地做自己的事情。

减少通信的一些技巧包括，使用数组作为结果，这样每个任务就不会尝试锁定对象以推送值。通常以后这些结果的减少会非常快。

但是对于所有类型的并行，缓慢来自于通信。减少它。

于 2017-10-12T02:48:28.397 回答