并行编程和C++

Question

最近我一直在写关于并行计算和编程的文章，我注意到在并行计算方面有很多模式。我注意到微软已经发布了一个库，名为Parallel Patterns Library，随同Microsoft Visual C++ 2010社区技术预览版一起发布。我想知道你使用过哪些常见的并行编程模式，并且这些模式值得记住吗？你是否有任何习惯用语和模式，在使用C++编写并行程序时不断出现？

- Dean Michael

---

你能澄清一下你对并行编程的具体兴趣吗？使用MPI进行分布式编程与使用OpenMP进行循环级别并行化有相当大的区别。 - mch

我特别关注并行编程中的通用模式和惯用语--无论是使用单台机器或多台机器上的分布式内存或共享内存模型。 - Dean Michael

Answer 1

模式：

• 生产者/消费者

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

• 循环并行

  • 如果可以证明每个循环是独立的
    则每次迭代可以在单独的线程中完成

• 重绘线程

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

• 主事件线程

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

• 工作组

  • 一组线程在队列上等待任务。
  • 线程从队列中提取一个工作项（如果没有可用，则等待）。
    线程对一个工作项进行处理，直到完成
    完成后，线程返回队列。

- Martin York

---

如果重新绘制线程在绘制时需要使用数据结构，那该怎么办？我的意思是，当其他线程正在更新它们时，它从中读取不会很危险吗？ - leod

除非重新绘制线程与Active Object相关联，其中更改被“序列化”，并且Active Object“拥有”修改的数据结构。 - Dean Michael

@leod：仅在您认为它很关键时，重新绘制线程才有可能在数据上获取读取锁定。大多数情况下，如果数据正在更新，则更新程序将很快发布更新事件以强制重新绘制，因此不需要过于担心。 - Martin York

这方面有来自伯克利的一些很棒的研究 http://parlab.eecs.berkeley.edu/wiki/patterns。PPL的一些模式在以下书籍和MSDN上有描述，http://parallelpatternscpp.codeplex.com/。 - Ade Miller

Answer 2

首先，您需要在共享内存计算和共享无内容计算之间进行选择。共享内存较为简单，但扩展性不佳——如果您：

a）拥有一个集群而非多处理器系统；或者

b）拥有许多 CPU（例如，大于 60），并且存在高度不均匀的内存

则应使用共享无内容。

对于共享内存，常见解决方案是使用线程；虽然概念易懂，在 API 中易于使用，但难以调试。

对于共享无内容，您需要使用某种形式的消息传递。在高性能计算中，MPI 已成为消息中间件。

此外，您还需要设计并行活动的架构。最常见的方法（因为易于理解）是 farmer-worker 模式（又称主从模式）。

- Martin v. Löwis

---

说实话，您不一定非得选择一个 -- 您可以创建支持两者的架构。但这些观点是有道理的-- 您需要清楚地了解在哪里支持哪个，因为需求（通常也包括设计）是非常不同的。 - Pat Notz

Answer 3

并行执行模式

确定性模式的结构化并行编程是一种高级方法，主要基于一组经常使用的并行执行模式，通常称为算法骨架或并行构造。这些模式抽象了程序描述并隐藏了程序员所需的低级多线程细节和许多与并行相关的复杂性。

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

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

论文

《带确定性模式的结构化并行编程》是一篇讨论这些模式的论文。您还可以查看“MHPM:多尺度混合编程模型：一种灵活的并行化方法”，该论文描述了一个名为XPU的C++实现。

库

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

例如，它允许表达：

1. 任务并行模式：

   具有一些特征的简单或分层Fork/Join执行模式，例如自动检测和保护共享数据。

2. 数据并行模式：

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

3. 时间并行模式：

   管道执行模式。

- Nader KHAMMASSI

---

你能否提供一段使用XPU库编写的代码示例？ - Jim Dagg

Answer 4

你已经掌握了将并行性添加到程序部分的基础知识。 C++17正在获得许多这样的功能（例如foreach、sort、find和friends的并行版本，map_reduce、map、reduce、prefix_sum等），请参见C++ Extensions for Parallelism。

然后你还有像continuations这样的项目。考虑std::future但带有continues。有几种实现方式（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( );

从上面可以看出，这是一个流程图的模式。Future 是 (A >> B >> C >> D)，而 Fork Join 是 (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），因为您有许多工人来完成工作，并且每个人都在安静地做自己的事情，因此速度非常快。

一些减少通信的技巧包括使用结果数组，以便每个任务不会尝试锁定对象以推送值。通常情况下，稍后减少这些结果可能非常快。

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

- Beached