共享内存与数据并行

共享内存并行允许多个线程在共同的地址空间上操作，而数据并行则同时对许多数据元素应用相同的操作。

Definition

在共享内存模型中，并行执行线程通过读写公共内存进行隐式通信，并通过同步原语进行协调；数据并行是一种特殊情况，即对数据结构的元素独立应用相同的计算。

Scope

本主题涵盖共享地址空间模型及其编程接口（线程、OpenMP）、协调线程的同步原语（锁、屏障、原子操作）以及它们所管理的危害（数据竞争、死锁、伪共享）、数据并行和循环并行构造，以及带有工作窃取调度器的基于任务的运行时。它处理编程方面，其理论基础出现在共享内存模型之下。

Core questions

• 线程如何在没有竞争或死锁的情况下协调对共享数据的访问？
• 如何表达循环和数组操作以实现并行执行？
• 如何有效地在多个核心之间平衡动态生成的任务？

Key theories

同步与内存一致性

正确的共享内存程序依赖于同步原语和对内存模型的理解，该模型规定了一个线程的写入何时对另一个线程可见，管理不当会导致竞争或死锁。

基于指令的数据并行

OpenMP允许程序员使用指令注释顺序代码，这些指令可以在共享地址空间上并行化循环和区域，为共享内存并行提供了一条可移植、增量式的路径。

工作窃取任务调度

基于任务的运行时通过让空闲处理器从繁忙处理器窃取工作来调度动态创建的任务，从而为不规则的并行计算实现可证明的良好负载平衡和有限的开销。

Clinical relevance

共享内存和数据并行编程是日常软件利用多核CPU以及科学内核、模拟和大量数组工作负载在单个节点上实现加速的方式，使其成为最广泛遇到的并行编程形式。

History

共享内存多处理技术随着线程模型和1998年OpenMP标准（用于可移植的基于指令的并行）而成熟；Cilk项目（1996年至今）的工作窃取调度器提供了高效的基于任务的并行，这些思想现在是跨语言多核编程的基础。

Key figures

• Maurice Herlihy
• Nir Shavit
• Charles Leiserson
• Vipin Kumar

Seminal works

• herlihy2008
• grama2003
• blumofe1996

Frequently asked questions

什么是数据竞争，为什么它很危险？

当两个线程在没有同步的情况下并发访问同一内存位置且至少一个线程进行写入时，就会发生数据竞争。结果是未定义的，并且可能在不同运行之间变化，产生间歇性、难以重现的错误，这就是为什么同步在共享内存程序中至关重要。