并行编程和C++

Question

最近我写了很多关于并行计算和编程的书，我注意到在并行计算方面出现了很多模式。注意到微软已经发布了一个库以及Microsoft Visual C++ 2010社区技术预览版（命名为并行模式库），我想知道你使用和遇到的常见并行编程模式可能值得记住吗？你有没有遵循的习惯用法，以及你在用C++编写并行程序时似乎一直弹出的模式？

Answer 1

模式：

• 农产品/消费

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

• 循环并行

  • 如果你能证明每个回路是独立
    每次迭代可以在sperate线程来完成

• 重新拉线

  • 其他线程做的工作和更新数据结构，但一个线程重新绘制屏幕。

• 主事件线程

  • 多个线程可产生事件
  • 一个线程必须处理该事件（如顺序很重要）
  • 应尽量分开事件线程/ RE - 线程
    这（帮助）可以防止用户界面冻结
    但如果不仔细做，可能会导致过度的重新绘制。

• 工作组

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

Answer 2

首先，您必须在共享内存计算和无共享计算之间进行选择。共享内存是比较容易的，但没有规模那么好 - 你会使用共享什么，如果你要么

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

B）如果你有多个CPU （比如说> 60）和高度的非均匀内存

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

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

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

Answer 3

并行执行模式

具有确定性图案结构化并行编程主要是基于反复并行执行模式的集合的高层次的方法，通常被称为算法骨架或并行结构，这些抽象的程序描述和隐藏低级多线程细节以及许多程序员并行的固有复杂性。

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

有很多常用的模式，如：地图，减少，的fork-join，管道或并行循环...

论文

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

库

XPU是基于任务的C++库从一组可复用的执行模式组成。它允许在单个齐次编程模型中以几个粒度级别表达几种类型的并行性。它很容易使用，并说明使用模式设计并行程序的重要性。

例如它允许的表达：

1. 任务并行模式：

   简单或分层叉/加入执行一些功能，例如如 自动检测和共享数据的保护图案。

2. 数据并行模式：

   具有可缩放数据分区

   并行回路图案。

3. 颞平行图案：

   管道执行模式。

Answer 4

您必须对螺栓并行的程序的一部分的基本知识。 C++ 17中有很多（例如foreach，排序，查找和朋友，map_reduce，map，reduce，prefix_sum ...的并行版本）请参阅C++ Extensions for Parallelism

然后，您将获得像continuations这样的项目。认为std::future但继续。有很少的方法来实现这些（boost有一个很好的现在，因为标准没有下一个（...）或然后（...）方法，但最大的好处是，一个人不必等待它做下一个任务

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

缺乏后续任务之间的同步是作为任务/线程间通信重要/ ...是什么减慢并行程序。

因此，与基于任务并行有一个任务调度程序，你只需将任务关闭然后走开，它们可能有方法（如信号量）来进行通信，但这不是强制性的。Intel Thread Building Blocks和Microsoft Parallel Pattern Library都有fa这个功能。

之后，我们有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，而且速度非常快，因为你有很多工作人员来完成工作，每个人都很安静地做自己的事情。

一些技巧，以减少commmunication包括，使用阵列对的结果，使得每个任务是不是想以推动一个值，以锁定对象。通常以后减少这些结果可能会非常快。

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