并行程序设计与C++

模式:

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

• 循环并行性

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

• • 多个线程可以生成事件
  • 应尝试分离事件线程/重新绘制线程
    这有助于防止UI冻结
    但如果不小心操作,可能会导致过度重新拉伸。

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

a) 拥有群集,而不是多处理器系统,或

b) 如果您有许多CPU(例如,>60),并且内存高度不一致

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

然后还需要为并行活动设计一个体系结构。最常见的方法(也是因为它很容易理解)是农民工模式(又称主从模式)。

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

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

有许多常用的模式,如:映射减少、Fork-Join、管道或并行循环。。。

“具有确定性模式的结构化并行编程”是一篇讨论这些模式的论文。你也可以看到“MHPM:多尺度混合编程模型:一种灵活的并行化方法”,它描述了这种方法的C++实现XPU。

图书馆

XPU

例如,它允许以下表达式:

1. 任务并行模式:

   简单或分层的Fork/Join执行模式,具有以下特性

2. 数据并行模式:

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

3. 时间并行模式:

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 我们有这方面的设施。

之后,我们有了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( );

目标是找到系统中不需要通信的独立部分。如上所述,在工作负载足够高或规模足够大(假设通信不太频繁)之前,并行算法几乎在所有情况下都比顺序算法慢。例如排序。在一台4核计算机上,您将获得大约2.5倍的性能,因为合并非常繁忙,需要大量的同步,并且在第一轮合并后无法使用所有的核心。在N非常大的GPU上,可以使用效率较低的排序,比如Bitonic,结果速度非常快,因为你有很多工人在工作中工作,每个人都安静地做自己的事情。

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