46

如果您今天从头开始编写一个新应用程序,并希望它扩展到您明天可以投入使用的所有内核,您会选择哪种并行编程模型/系统/语言/库?为什么?

我对这些轴上的答案特别感兴趣:

  1. 程序员生产力/易用性(凡人能成功使用吗?)
  2. 目标应用领域(它(不)擅长什么问题?)
  3. 并发风格(它是否支持任务、管道、数据并行、消息......?)
  4. 可维护性/面向未来(20 年后还会有人使用它吗?)
  5. 性能(它如何在什么样的硬件上扩展?)

我故意模糊应用程序的性质,以期获得对各种应用程序有用的良好一般答案。

4

22 回答 22

27

多核编程实际上可能需要不止一种范式。目前的一些竞争者是:

  1. 映射减少。这在问题可以很容易地分解为并行块的情况下效果很好。
  2. 嵌套数据并行。这类似于 MapReduce,但实际上支持问题的递归分解,即使递归块的大小不规则。期待 NDP 在运行在大规模并行但有限的硬件(如 GPU)上的纯函数式语言中大获全胜。
  3. 软件事务内存。如果您需要传统线程,STM 可以让它们变得可以忍受。您在关键部分付出了 50% 的性能损失,但您可以轻松地将复杂的锁定方案扩展到 100 多个处理器。但是,这不适用于分布式系统。
  4. 带有消息传递的并行对象线程。Erlang 使用了这个非常聪明的模型。每个“对象”都成为一个轻量级线程,对象通过异步消息和模式匹配进行通信。它基本上是真正的并行 OO。这在几个现实世界的应用程序中取得了很好的成功,并且对于不可靠的分布式系统非常有效。

其中一些范例可以为您提供最大的性能,但只有在问题完全分解时才有效。其他人牺牲了一些性能,但允许更广泛的算法。我怀疑以上的某种组合最终将成为标准工具包。

于 2008-09-17T15:10:10.417 回答
14

我真正喜欢的两个解决方案是加入微积分JoCamlPolyphonic C#)和演员模型ErlangScalaEIo)。

我对Software Transactional Memory没有特别的印象。只是感觉它的存在只是为了让线程能够再坚持一段时间,即使它们应该在几十年前就死了。但是,它确实具有三个主要优点:

  1. 人们了解数据库中的事务
  2. 已经有关于事务性 RAM 硬件的讨论
  3. 尽管我们都希望它们消失,但线程可能会在接下来的几十年中成为主要的并发模型,尽管这可能是可悲的。STM可以显着减轻疼痛。
于 2008-09-17T05:04:04.133 回答
11

mapreduce/hadoop 范式很有用且相关。特别是对于那些习惯于 perl 之类的语言的人来说,映射数组并对每个元素执行一些操作的想法应该非常流畅和自然,而 mapreduce/hadoop 只是将它带到下一个阶段并说没有理由数组的每个元素都需要在同一台机器上处理。

从某种意义上说,它经受了更多的考验,因为谷歌正在使用 mapreduce,而且很多人一直在使用 hadoop,并且已经证明它可以很好地通过网络在多台机器上扩展应用程序。如果您可以跨网络扩展多台机器,则可以扩展单台机器中的多个内核。

于 2008-09-17T04:35:18.667 回答
10

对于 .NET 应用程序,我选择“ .NET Parallel Extensions (PLINQ) ”,它非常易于使用,并且允许我在几分钟内并行化现有代码。

  1. 学习很简单
  2. 用于对大型对象数组执行复杂操作,因此无法评论其他应用程序
  3. 支持任务和管道
  4. 应该在未来几年内得到支持,但谁知道呢?
  5. CTP 版本有一些性能问题,但看起来已经很有希望了。

Mono可能会获得对 PLINQ 的支持,因此它也可能是一个跨平台的解决方案。

于 2008-09-17T04:33:07.220 回答
6

对于繁重的计算等,像Haskell这样的纯函数式语言很容易并行化,而不需要程序员的任何努力。除了学习 Haskell,就是这样。

但是,我不认为这是(不远的)未来的方式,仅仅是因为太多的程序员太习惯于命令式编程范式。

于 2008-09-17T04:46:01.103 回答
5

kamaelia是一个python 框架,用于构建具有大量通信进程的应用程序。

Kamaelia - 并发变得有用、有趣

在 Kamaelia 中,您可以使用相互通信的简单组件构建系统。这加快了开发速度,极大地帮助了维护,还意味着您可以构建自然并发的软件。它旨在供任何开发人员访问,包括新手。它也让它变得有趣:)

什么样的系统?网络服务器、客户端、桌面应用程序、基于 pygame 的游戏、转码系统和管道、数字电视系统、垃圾邮件根除器、教学工具等等 :)

另请参阅问题多核和并发 - 语言、库和开发技术

于 2008-09-18T01:20:15.630 回答
4

我打赌用承诺来传达事件循环,正如在TwistedEAmbientTalk等系统中实现的那样。它们保留了编写具有与非并发/并行应用程序相同的执行模型假设的代码的能力,但可以扩展到分布式和并行系统。(这就是我在Ecru上工作的原因。)

于 2008-09-17T04:36:19.957 回答
2

看看二郎。谷歌它,并观看各种演示文稿和视频。我尊敬的许多程序员和架构师都非常喜欢它的可扩展性。我们在我工作量很大的地方使用它...

于 2008-09-17T04:40:56.483 回答
2

如前所述,纯函数式语言本质上是可并行的。然而,命令式语言对许多人来说更直观,而且我们深深植根于命令式遗留代码。基本问题是纯函数式语言显式表达副作用,而命令式语言通过语句顺序隐式表达副作用。

我相信以声明方式表达副作用的技术(例如,在面向对象的框架中)将允许编译器将命令式语句分解为它们的函数关系。这应该允许代码以与纯函数代码大致相同的方式自动并行化。

当然,就像今天仍然希望用汇编语言编写某些性能关键代码一样,明天仍然需要编写性能关键的显式并行代码。但是,我概述的技术应该有助于自动利用众核架构,而开发人员只需花费最少的精力。

于 2008-09-17T15:32:58.710 回答
2

我很惊讶没有人建议 MPI(消息传递接口)。虽然是为分布式内存设计的,但具有必要且频繁的全局耦合(求解具有数十亿未知数的线性和非线性方程)的 MPI 程序已被证明可以扩展到 200k 个内核。

于 2009-03-18T14:53:15.097 回答
2

这个问题似乎一直以不同的措辞出现——也许 StackOverflow 中有不同的选区。 基于流的编程(FBP) 是一种已经存在 30 多年的概念/方法,并被用于处理加拿大一家主要银行的大部分批处理。它在 Java 和 C# 中具有基于线程的实现,尽管早期的实现是基于光纤的(C++ 和大型机汇编器——银行使用的一种)。解决利用多核问题的大多数方法都涉及尝试采用传统的单线程程序并确定哪些部分可以并行运行。FBP 采用了不同的方法:应用程序从一开始就设计为多个异步运行的“黑盒”组件(想想制造装配线)。由于组件之间的接口是数据流,FBP本质上是语言无关的,因此支持混合语言应用,和特定领域的语言。出于同样的原因,副作用最小化。它也可以描述为“无共享”模型和 MOM(面向消息的中间件)。MapReduce 似乎是 FBP 的一个特例。FBP 与 Erlang 的主要区别在于 Erlang 在许多短寿命线程方面运行,因此绿色线程在那里更合适,而 FBP 使用较少(通常为几十到几百)寿命较长的线程。为一个 而 FBP 使用更少(通常是几十到几百)寿命更长的线程。为一个 而 FBP 使用更少(通常是几十到几百)寿命更长的线程。为一个已经使用了 30 多年的批处理网络的一部分,请参阅批处理网络的一部分。有关交互式应用程序的高级设计,请参阅经纪应用程序高级设计。已经发现 FBP 可以产生更多可维护的应用程序,并缩短运行时间 - 即使在单核机器上也是如此!

于 2009-06-02T15:55:15.020 回答
1

并行编程 IMO 分为三个部分:识别并行度和指定并行度。识别=将算法分解为并发的工作块,指定=进行实际的编码/调试。识别与您将使用哪个框架来指定并行性无关,我认为框架对此没有多大帮助。它对您的应用程序、目标平台、常见的并行编程权衡(硬件延迟等)以及最重要的经验有很好的理解。但是可以讨论指定,这就是我尝试在下面回答的内容:

我尝试了许多框架(在学校和工作中)。既然您询问了多核,它们都是共享内存,我将坚持使用我使用过的三个共享内存框架。

Pthreads(它不是​​一个真正的框架,但绝对适用):

优点:-Pthreads 非常通用。对我来说,pthread 就像是并行编程的集合。您可以在 pthread 中编写任何范例。- 它很灵活,因此您可以根据需要使其具有高性能。没有固有的限制可以减慢您的速度。您可以编写自己的构造和原语并获得尽可能快的速度。

缺点: - 要求您自己完成所有工作,例如管理工作队列、任务分配。- 实际的语法很丑陋,而且你的应用程序通常有很多额外的代码,这使得代码难以编写,然后又难以阅读。

开放式MP:

优点: - 代码看起来很干净,管道和任务拆分主要在引擎盖下 - 半灵活。它为您提供了几个有趣的工作安排选项

缺点: - 用于类似并行的简单 for 循环。(较新的英特尔版本也支持任务,但任务与 Cilk 相同)。- 底层结构可能会或可能不会为性能而精心编写。GNUs 的实现还可以。英特尔的 ICC 对我来说效果更好,但我宁愿自己写一些东西以获得更高的性能。

Cilk、英特尔 TBB、苹果 GCD:

优点: - 可证明是任务级并行的最佳底层算法 - 串行/并行任务的体面控制 - TBB 也有一个我使用的管道并行框架(坦率地说,这不是最好的) - 消除了大量编写的任务用于基于任务的系统的代码,如果您人手不足,这可能是一个很大的优势

缺点: - 对底层结构性能的控制较少。我知道英特尔 TBB 的底层数据结构性能很差,例如,工作队列很糟糕(我在 2008 年看到它时)。- 代码有时看起来很糟糕,包含他们希望你使用的所有关键字和流行语 - 需要阅读大量参考资料才能理解他们的“灵活”API

于 2011-05-10T00:27:31.000 回答
1

另请参阅问题多核和并发 - 语言、库和开发技术

于 2008-10-23T11:08:19.063 回答
1

具有多个工作人员系统的作业队列(不确定正确的术语 - 消息队列?)

为什么?

主要是因为这是一个非常简单的概念。你有一个需要处理的东西的列表,然后是一堆获取工作并处理它们的进程。

此外,与原因不同,例如,Haskell 或 Erlang 如此并发/可并行(?),它完全与语言无关 - 您可以用 C、Python 或任何其他语言(甚至使用 shell 脚本)轻松实现这样的系统,而我怀疑 bash 会很快获得软件事务内存或连接演算。

于 2009-06-02T16:48:07.447 回答
1

如果您的问题域允许尝试考虑无共享模型。您在进程和线程之间共享的越少,您设计复杂的并发模型就越少。

于 2008-09-17T04:59:33.350 回答
1

我真的很喜欢Clojure选择的模型。Clojure 使用不可变数据结构和软件事务内存的组合。

不可变的数据结构是永远不会改变的。可以使用修改后的数据创建新版本的结构,但如果您有一个指向数据结构的“指针”,它永远不会从您的下方改变。这很好,因为您可以访问该数据而不必担心并发问题。

软件事务内存在这些答案的其他地方进行了讨论,但足以说明它是一种机制,多个线程都可以对某些数据进行操作,如果它们发生冲突,则其中一个线程将回滚以重试。当存在碰撞风险但不太可能时,这允许更快的速度。

有一段来自作者 Rich Hickey 的视频,其中包含更多细节。

于 2009-08-28T04:18:16.660 回答
1

Qt concurrent 为多核提供了一个非常易于使用的 MapReduce 实现。它是多操作系统。

于 2008-09-17T04:34:36.763 回答
1

一条有价值的路径可能是OpenCL,它提供了一种跨异构计算资源分配某些类型的计算负载的方法,即相同的代码将在多核 CPU 和商品 GPU 上运行。ATI 最近发布了正是这样一个工具链。NVidia 的CUDA工具链与此类似,但更受限制。Nvidia似乎也正在开发一个OpenCL sdk

应该注意的是,在工作负载不具有数据并行性质的情况下,这可能无济于事,例如,它对典型的事务处理没有多大帮助。OpenCL 主要面向数学密集型计算类型,例如科学/工程模拟或金融建模。

于 2009-08-28T04:52:57.153 回答
1

在过去的十年中,我们一直在使用PARLANSE,一种具有显式并发偏序规范的并行编程语言,来实现可扩展的程序分析和转换系统(DMS Software Reengineering Toolkit) 主要进行符号计算而不是数字计算。PARLANSE 是一种编译的类 C 语言,具有传统的标量数据类型字符、整数、浮点数、动态数据类型字符串和数组、复合数据类型结构和联合以及词法范围的函数。虽然大多数语言都是 vanilla(操作数上的算术表达式、if-then-else 语句、do 循环、函数调用),但并行性不是。通过定义代码块(例如,a 之前 b、a 之前 c、d 之前 c)上的“在先”关系来表示并行性,写为

(|;  a  (... a's computation)
     (<< a) b ( ... b's computation ... )
     (<< a) c ( ....c's computation ...)
     (>> c) d ( ... d's computation...)
)|;

<< 和 >> 运算符指的是“时间顺序”。PARLANSE 编译器可以看到这些并行计算并预分配计算颗粒 a、b、c、d 所需的所有结构,并生成自定义代码来启动/停止每个结构,从而最大限度地减少启动和停止这些并行颗粒的开销。

请参阅此链接以并行迭代深化搜索 15-puzzle 的最优解,这是 8-puzzle 的 4x4 老大哥。它仅使用潜在的并行作为并行结构 (|| abcd ) ,表示计算a b c d没有偏序约束,但它也使用推测并异步中止无法找到解决方案的任务。它在一小段代码中包含了很多想法。

PARLANSE 在多核 PC 上运行。一个大的 PARLANSE 程序(我们已经构建了许多超过 100 万行或更多的程序)将有数千个这样的偏序,其中一些调用包含其他的函数。到目前为止,我们在最多 8 个 CPU 上取得了不错的成绩,在最多 16 个 CPU 上取得了不错的回报,我们仍在调整系统。(我们认为当前 PC 上大量内核的真正问题是内存带宽:16 个内核冲击内存子系统会产生巨大的带宽需求)。

大多数其他语言没有公开并行性,因此很难找到,并且运行时系统通过使用通用调度原语来调度计算粒度付出了高昂的代价。我们认为这是灾难的根源,或者至少由于阿姆达尔定律而导致性能不佳:如果与工作相比,调度谷物的机器指令数量很大,那么您就不会高效。OTOH,如果您坚持使用具有许多机器指令的计算粒度来保持相对较低的调度成本,那么您将找不到独立的计算粒度,因此您没有任何有用的并行性来调度。所以 PARLANSE 背后的关键思想是最小化调度 grain 的成本,使 grain 可以很小,以便在实际代码中可以找到很多。

十年来,我们一直在研究这个问题。很难做到这一点。我看不出那些没有在这个时间框架内构建并行语言并使用/调整它们的人如何有很大的机会构建有效的并行系统。

于 2009-08-28T03:53:56.553 回答
1

如果您今天从头开始编写一个新应用程序,并希望它扩展到您明天可以投入使用的所有内核,您会选择哪种并行编程模型/系统/语言/库?

也许今天最广泛适用的是 Cilk 样式的任务队列(现在在 .NET 4 中可用)。它们非常适合使用分而治之的问题来解决,并且具有可预测的子任务复杂性(例如已知函数参数复杂性的并行mapreduce数组以及快速排序等算法),并且涵盖了许多实际问题。

此外,这仅适用于像今天的多核这样的共享内存架构。虽然我不相信这种基本架构会很快消失,但我确实相信它必须在某个时候与分布式并行性相结合。这可以是多核 CPU 上的多核集群的形式,在多核之间传递消息,或者是内核层次结构的形式,它们之间具有可预测的通信时间。这些将需要完全不同的编程模型才能获得最大效率,我相信对它们知之甚少。

于 2010-05-23T19:23:46.870 回答
0

Erlang 是更“成熟的解决方案”,并且是可移植和开源的。我摆弄着 Polyphonic C# ,我不知道每天用它编程会怎样。

几乎所有语言/操作系统都有库和扩展,谷歌事务内存。这是 MS 的一个有趣的方法。

于 2008-10-23T11:18:27.063 回答
0

我会使用 Java——它是可移植的,所以未来的处理器不会成为问题。我还将使用标准互斥例程作为库(减少并行代码的调试)对我的应用程序进行编码,将接口/逻辑和数据(更像是 3 层 Web 应用程序)的层分开。请记住,Web 服务器可以很好地扩展到许多处理器,并且是通往多核的最不痛苦的途径。或者查看旧的连接机器模型,它带有一个与数据绑定的虚拟处理器。

于 2008-09-17T04:34:56.793 回答