搜档网
当前位置:搜档网 › 多核编程入门

多核编程入门

多核编程入门
多核编程入门

多核编程入门

作者: chengjia4574@https://www.sodocs.net/doc/ce13671294.html, sinaweibo: jiayy

时间:2012-8-8

说明:本文是多核编程的入门资料汇总,来源主要是国外国内的一些网站及自己使用过程中一些记录,写作目的主要是内部分享用(@NSFOCUS)。在多核使用过程中,得益于很多网络资源,所以也把自己整理的产品无关的东西共享出来,希望对多核感兴趣的同学可以入门用。

目录

一. 并发与并行的区别? (1)

1.1串行 (1)

1.2并发 (1)

1.3并行 (1)

1.4多核编程的难点 (2)

二. 多核体系架构 (3)

2.1多核处理器定义 (3)

2.2多核发展趋势 (3)

2.3一个多核处理器架构例子 (5)

2.4L INUX 线程核绑定 (6)

2.4.1 核亲和性绑定 (6)

2.4.2 资源控制cgroup (8)

三. 内存模型 (8)

3.1操作原子性 (9)

3.1.1 原子性的3种保证机制 (9)

3.1.2 硬件原子操作 (9)

3.1.3 总线锁-原子操作原语 (12)

3.2缓存一致性 (16)

3.2.1 定义 (16)

3.2.2 CC协议 (17)

3.2.3 伪共享 (21)

3.3顺序一致性 (24)

3.3.1 定义 (24)

3.3.2 几种顺序约束 (25)

3.3.3 乱序执行和内存屏障 (28)

四. 并发级别 (31)

4.1W AIT-FREEDOM 无等待并发 (32)

4.2L OCK-FREEDOM 无锁并发 (32)

4.3O BSTRUCTION-FREEDOM 无阻塞并发 (33)

4.4B LOCKING ALGOITHMS 阻塞并发 (33)

五. 锁 (34)

5.1信号量 (34)

5.2自旋锁 (35)

5.3读写锁 (35)

5.4顺序锁 (37)

5.5RCU (38)

六. 无锁编程 (38)

6.1定义 (39)

七. 并发数据结构、开源库 (41)

7.1一些开源的并发库 (41)

7.2一次无锁哈希表跟基于锁的哈希表性能对比测试 (41)

7.2.1 测试平台 (41)

7.2.2 测试过程 (42)

7.2.3 哈希算法 (43)

7.2.4 测试结果 (44)

八. 多核工程实践 (44)

8.1网络设备:I NTEL DPDK (44)

8.2网络游戏 (44)

8.3手机开发 (45)

九. 参考 (45)

表格索引

表 3.1 CC 示意图 (24)

表 3.2 CC示意图2 (24)

插图索引

图 1.1 并发和并行的区别 (2)

图 2.1 PC和手机核心增长趋势图 (4)

图 2.2 最新的MAC PRO 已经配备12个核心 (4)

图 2.3 三星推出了8核心的手机处理器 (4)

图 2.4 共享缓存多核处理器体系架构图实例 (5)

图 2.5 处理器各组件功能说明 (5)

图 2.6 共享缓存多核处理器架构缓存示意图 (6)

图 3.1 DPDK, CAS 实现代码 (14)

图 3.2 DPDK: 原子ADD实现代码 (15)

图 3.3 DPDK: 原子自增实现代码 (15)

图 3.4 MESI 协议 (17)

图 3.5 MOESI 状态机 (18)

图 3.6 CC协议示例代码 (18)

图 3.7 初始状态 (19)

图 3.8 X已经写入缓存 (20)

图 3.9 X增加了10010 (20)

图 3.10 CORE1从CORE0的缓存里读走数据 (21)

图 3.11 伪共享 (22)

图 3.12 缓存行伪共享 (23)

图 3.13 缓存行填充 (23)

图 3.14 一些体系架构的内存顺序标准 (27)

图 3.15 强内存顺序模型和弱内存顺序模型一些例子 (27)

图 3.16 编译乱序和运行乱序 (28)

图 3.17 乱序执行 (30)

图 3.18 内存屏障 (31)

图 4.1 几种并发级别的对比 (34)

图 5.1 读写锁 (35)

图 5.2 申请读锁 (36)

图 5.3 释放读锁 (36)

图 5.4 申请写锁 (37)

图 5.5 释放写锁 (37)

图 6.1 什么是无锁编程 (39)

图 6.2 无锁编程涉及的技术 (40)

图7.1 INTEL E5-2658 (42)

图7.2 E5-2658 核分布 (42)

一. 并发与并行的区别?

首先了解几个概念:

1.1 串行

最基本的程序执行方式,串行程序的整个运行时,只有一个调用栈和一个运行时上下文.单进程/单线程程序可以认为是串行程序.

1.2 并发

多线程出现后比较常见的程序执行方式,多线程程序运行时,会有多个运行时上下文和对应的多个调用栈。逻辑上多个线程同时发生,物理上是由操作系统调度,CPU某一时刻依然只执行一个线程的任务,但是某个执行中的线程随时可能被OS调度走,而随后运行的线程操作的数据可能跟刚刚被调度走的线程造成冲突,所以有共享数据同步问题。

多进程如果有共享数据,也符合并发程序的特点.相对于多线程并发,多进程并发解耦更彻底, 数据分割更清晰。

另外,前述并发情况是从用户程序的角度,从内核的角度,还会有其他类似的场景,比如中断。中断处理程序和中断之前执行的程序也有可能有共享数据冲突的问题。

1.3 并行

多核处理器出现后会越来越常见的程序执行方式,物理上多个任务可以同时运行,这个概念介于操作系统和体系架构之间,从操作系统而言,依然是调度多个线程/进程去CPU执行,只不过有了多个CPU/核心,不同线程/进程可以绑定从而完全占用一颗核心,所以从体系架构的角度,同一时刻是有多个任务同时运行,另外一些说法,如‘多处理器程序’‘多核程序’都可以认为属于并行程序的范畴。

从概念的范围看,并行<并发,即并行的程序肯定是并发的,并发的程序不一定是并行的。但是,无论是逻辑上的并发(单处理器,多线程/多进程)还是物理上的并发(并行,多处理器),所面临的共享数据操作一致性问题是一样的,在很多情况下,多核编程可以近似认为

是多线程编程,所以本文对‘并发’‘多线程’‘多核’‘并行’等词汇没有做严格的区分,根据上下文可以自行理解。

图 1.1 并发和并行的区别

1.4 多核编程的难点

难点:同时从宏观和微观两种角度分析问题,并能灵活在两种角度之间切换。

在之前单处理器的世界里,计算机科学在编译器优化、处理器优化、多线程编程等方面有很深厚的积累,形成了对编程人员而言非常抽象的各种基础库,编程人员无须知道编译器、体系结构、OS的多线程互斥同步等的实现细节。

进入多处理器后,这一个高度抽象的基础库还没有形成,虽然有一些并行库或者开发套件,但抽象程度还不够,理想上OS和编译器应该能对应用开发人员完全屏蔽多核体系架构的特点,但目前无法做到。多核程序开发人员目前需要自己解决核绑定、cgroup划分、缓存对齐、跨物理CPU内存访问以及其他一些OS和体系结构层面需要考虑的问题(尤其是性能优化时)

本文的目的是为对多核编程感兴趣的同学提供入门级别的学习材料,主要包括两个方面:

1)尝试解释清楚几个最基本的概念,这些概念广泛存在于各种论文、技术文档甚至源代码注释里,如果不掌握这些概念,会对某些多核的关键代码不知其所以然。

2)提供收集到的比较好的源代码和博客目录,需要注意的是,多核编程目前属于比较冷门的领域(对比app,游戏开发),好的代码和资料还是比较难收集的。

二. 多核体系架构

2.1 多核处理器定义

多内核处理器架构是指:芯片设计工程师在单个处理器中集成两个或多个“执行内核(即计算引擎)”。多内核处理器可直接插入到单一处理器基座中。但是,操作系统会把它的每个执行内核作为独立的逻辑处理器,为其分配相应的执行资源。要利用多核处理器的运算能力,需要改写操作系统和编译器,广泛使用的vista, vin7 等都能支持多核体系架构。[百度百科]

2.2 多核发展趋势

首先思考一个问题:为什么微处理器要从单核转向多核?

答案是:功耗问题限制了单核不断提高性能的发展途径.

有几个简单的公式可以说明这个问题:

1) 处理器性能= 主频* IPC , 主频是指每秒时钟周期数,比如1Ghz,是每秒10亿个时钟周

期。IPC 是每个时钟周期可以执行的指令数。

2) 处理器功耗正比电流*电压^2*主频,而主频正比电压,所以

处理器功耗正比主频^3 ,通过主频提升性能,要面临功耗以3次方的指数增长问题。

所以主频发展到一定程度后,自然转到重点依靠提高ipc来提升性能,提升IPC可以通过提高指令的并行度实现,提高并行度,一是提高微处理器微架构的并行度,二是采用多核架构,(参考:https://www.sodocs.net/doc/ce13671294.html,/china/2007/06/03/post_5/)前者已经发展了很多年,提升空间和投入产出比明显不如后者,所有多核处理器是未来的方向。

下图是某公司对PC和手机核数的统计和预测,不管是PC端还是移动端,多核的趋势非常明显,到目前(2013)市面上4核的手机已经非常普遍。

图 2.1 PC和手机核心增长趋势图

下面两张图看出家庭版PC和手机核心数目也很快突破10个。

图 2.2 最新的mac pro 已经配备12个核心

图 2.3 三星推出了8核心的手机处理器

虽然商用多核(multicore)和众核(many-core)系统越来越普遍,成本也越来越低,游戏设备、手机等移动设备也具备越来越多的核心,并发和并行越来越成为必要的技术手段,但多核程序的发展依然没有跟上硬件的发展,很多游戏引擎和网络引擎都还是单线程的。原因就是第一章提到的多核编程的难度。

2.3 一个多核处理器架构例子

图 2.4 共享缓存多核处理器体系架构图实例

图 2.5 处理器各组件功能说明

这是基于共享缓存的多核体系架构的一个例子,一共有10个核心,不需要深入了解,这张图唯一的目的就是给大家一个概念,现代的处理器架构已经比几十年前的冯诺依曼体系复杂多了(各种box),里边稍微值得关注的是Cbox ,Bbox ,这两个组件是缓存控制器,负责非常核心的功能:缓存一致性。缓存一致性会在第三章描述。

图 2.6 共享缓存多核处理器架构缓存示意图

这张图是intel多核体系架构(双路)的缓存示意图,每个core拥有自己的L1和L2缓存,属于一个物理CPU的core共享L3缓存。不同cpu之间通过QPI交互L3数据。每个CPU 有自己的内存控制器。对多核编程而言,缓存是非常重要的底层概念。

2.4 Linux 线程核绑定

这么多核具体到编程时候是如何使用的?linux 目前提供了若干机制可以让用户程序使用多核,其中包括进程/线程的核亲和性绑定,以及cpuset的资源控制

2.4.1 核亲和性绑定

在linux平台提供了核亲和性机制,进程和线程都可以通过设置亲和性绑定到不同的核心上。

进程版本:

#include

void setProcessToCPU(int _cpuID)

{

cpu_set_t mask;

cpu_set_t get;

CPU_ZERO(&mask);

CPU_SET(_cpuID, &mask);

if (sched_setaffinity(0, sizeof(mask), &mask) < 0) {

cout << "set process affinity failed\n" << endl;

}

CPU_ZERO(&get);

if (sched_getaffinity(0, sizeof(get), &get) < 0) {

cout << "get process affinity failed\n" << endl;

}

}

线程版本:

#include

#include

void setThreadToCPU(int _cpuID)

{

cpu_set_t mask;

cpu_set_t get;

CPU_ZERO(&mask);

CPU_SET(_cpuID, &mask);

if (pthread_setaffinity_np(pthread_self(), sizeof(mask), &mask) < 0) { cout << "set thread affinity failed\n" << endl;

}

CPU_ZERO(&get);

if (pthread_getaffinity_np(pthread_self(), sizeof(get), &get) < 0) {

cout << "get thread affinity failed\n" << endl;

}

2.4.2 资源控制cgroup

Cgroups是control groups的缩写,是Linux内核提供的一种可以限制、记录、隔离进程组(process groups)所使用的物理资源(如:cpu,memory,IO等等)的机制。最初由google

的工程师提出,后来被整合进Linux内核。Cgroups也是LXC为实现虚拟化所使用的资源管理手段,可以说没有cgroups就没有LXC。

Cgroup 有一个子系统cpuset, 这个子系统为cgroup 中的任务分配独立CPU(在多核系统)和内存节点。

https://www.sodocs.net/doc/ce13671294.html,/lisperl/archive/2012/04/17/2453838.html linux cgroups 详解一至

三. 内存模型

问题1:内存模型是什么?

答案:CPU硬件有它自己的内存模型,不同的编程语言也有它自己的内存模型。如果用一句话来介绍什么是内存模型,我会说它就是程序员,编程语言和硬件之间的一个契约,它保证

了共享的内存地址里的值在需要的时候是可见的,它保证了机器执行代码的结果与程序员脑

子里的预期是一致的。它最大的作用是取得可编程性与性能优化之间的一个平衡。[https://www.sodocs.net/doc/ce13671294.html,]

问题2:多核并行编程为什么需要关注内存模型?

答案:目前缺少一个完整的支持并发的内存模型,使得开发多核程序的程序员不得不面对内存操作的一些细节。从语言来说,.net , java 基于虚拟机的语言其内存模型相对完整,c,c++

的内存模型在并发相关的领域上貌似还不是很完整(引自某个网友)

问题3:在多核并发环境里,需要关注内存模型的哪些方面?

答案:操作原子性、缓存一致性、顺序一致性。非常重要的一点思想是:你的代码不

一定向你想象中那样执行

3.1 操作原子性

原子性操作是指,在整个系统可见范围内,一个操作要不就没有发生,要不就执行完毕,没有中间状态出现。

3.1.1 原子性的3种保证机制

在多线程程序里,哪些操作具有天然的原子性?哪些操作需要原子操作原语的支持?原子操作原语底层机制是什么?

要回答这些问题,我们首先需要从硬件讲起。以常见的X86 CPU来说,根据Intel的参考手册,它基于以下三种机制保证了操作原子性(8.1节):

(1)Guaranteed atomic operations (注:8.1.1节有详细介绍)

(2)Bus locking, using the LOCK# signal and the LOCK instruction prefix

(3)Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

这三个机制相互独立,相辅相承。简单的理解起来就是

(1)一些基本的内存读写操作是本身已经被硬件提供了原子性保证(例如读写单个字节的操作);

(2)一些需要保证原子性但是没有被第(1)条机制提供支持的操作(例如read-modify-write)可以通过使用”LOCK#”来锁定总线,从而保证操作的原子性。原子操作原语是基于“LOCK#”总线锁实现的。

(3)因为很多内存数据是已经存放在L1/L2 cache中了,对这些数据的原子操作只需要与本地的cache打交道,而不需要与总线打交道,所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值。

下面分别对以上3点进行说明

3.1.2 硬件原子操作

那么CPU对哪些(1)中的基本的操作提供了原子性支持呢?根据Intel手册8.1.1节的介绍:从Intel486 processor开始,以下的基本内存操作是原子的:

?Reading or writing a byte(一个字节的读写)

?Reading or writing a word aligned on a 16-bit boundary(对齐到16位边界的字的读写)?Reading or writing a doubleword aligned on a 32-bit boundary(对齐到32位边界的双字的读写)

从Pentium processor开始,除了之前支持的原子操作外又新增了以下原子操作:?Reading or writing a quadword aligned on a 64-bit boundary(对齐到64位边界的四字的读写)

?16-bit accesses to uncached memory locations that fit within a 32-bit data bus(未缓存且在32位数据总线范围之内的内存地址的访问)

从P6 family processors开始,除了之前支持的原子操作又新增了以下原子操作:?Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line(对单个cache line中缓存地址的未对齐的16/32/64位访问)

那么哪些操作是非原子的呢?

Accesses to cacheable memory that are split across bus widths, cache lines, and

page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel?

Atom?, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and

Intel486 processors.(说点简单点,那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的,你如果想保证这些操作是原子的,你就得求助于机制(2),对总线发出相应的控制信号才行)。

需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障,但是非对齐访问是非常影响性能的,需要尽量避免。当然了,对于一般的程序员来说不需要太担心这个,因为大部分编译器会自动帮你完成内存对齐。

下面从一道题的分析充分理解硬件原子操作:

以下多线程对int型变量x的操作,哪几个需要进行同步:()

A. x=y;

B. x++;

C. ++x;

D. x=1;

我们先反汇编一下看看它们到底执行了什么操作:

x = y;

mov eax,dword ptr [y]

mov dword ptr [x],eax

x++;

mov eax,dword ptr [x]

add eax,1

mov dword ptr [x],eax

++x;

mov eax,dword ptr [x]

add eax,1

mov dword ptr [x],eax

x = 1;

mov dword ptr [x],1

(1)很显然,x=1是原子操作。

因为x是int类型,32位CPU上int占32位,在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句,x的值最终还是被赋的值(而不会出现例如某个线程只更新了x的低16位然后被阻塞,另一个线程紧接着又更新了x的低24位然后又被阻塞,从而出现x的值被损坏了的情况)。

(2)再来看x++和++x。

其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句:从内存中读x的值到寄存器中,对寄存器加1,再把新值写回x所处的内存地址(见上面的反汇编代码)。

例如有两个线程,它们按照如下顺序执行(注意读x和写回x是原子操作,两个线程不能同时执行):

time Thread 1 Thread 2

0 load eax, x

1 load eax, x

2 add eax, 1 add eax, 1

3 store x, eax

4 store x, eax

我们会发现最终x的值会是1而不是2,因为Thread 1的结果被覆盖掉了。这种情况需要借助概述中的机制2来实现操作原子性。

(3)最后来看看x=y。

在X86上它包含两个操作:读取y至寄存器,再把该值写入x。读y的值这个操作本身是原子的,把值写入x也是原子的,但是两者合起来是不是原子操作呢?我个人认为x=y不是原子操作,因为它不是不可再分的操作。但是它需要不需要同步呢?其实问题的关键在于程序的上下文。

例如有两个线程,线程1要执行{y = 1; x = y;},线程2要执行{y = 2; y = 3;},假设它们按如下时间顺序执行:

time Thread 1 Thread 2

0 store y, 1

1 store y, 2

2 load eax, y

3 store y, 3

4 store x, eax

那么最终线程1中x的值为2,而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行,但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步,也可以说x=y不需要同步,看你怎么理解题意了。

x=1是否需要同步也是一样的道理,虽然它本身是原子操作,但是如果有另一个线程要读x=1之后的值,那肯定也需要同步,否则另一个线程读到的就是x的旧值而不是1了。

[参考:https://www.sodocs.net/doc/ce13671294.html,并行实验室]

3.1.3 总线锁-原子操作原语

对于硬件无法保证的原子操作,可以通过原子操作原语来保证,原子操作原语一般要基于总线锁实现:

在x86 平台上,CPU提供了在指令执行期间对总线加锁的手段。CPU芯片上有一条引线#HLOCK pin,如果汇编语言的程序中在一条指令前面加上前缀"LOCK",经过汇编以后的机器代码就使CPU在执行这条指令的时候把#HLOCK pin的电位拉低,持续到这条指令结束时放开,从而把总线锁住,这样同一总线上别的CPU就暂时不能通过总线访问内存了,保证了这条指令在多处理器环境中的原子性

常见的原子操作原语如下

3.1.3.1 CAS

这是最常见的原子操作原语。在不同系统下可能有以下命名:

CAS, compare-and-exchange, compare-and-set, std::atomic_compare_exchange, InterlockedCompareExchange, __sync_val_compare_and_swap, LOСK CMPXCHG and other.

在某些论文里经常看到RMW (read-modify-write),CAS 就是一种RMW,其伪代码是

T compare-and-swap(T* location, T cmp, T xchg)

{

do atomically

{

T val = *location;

if (cmp == val)

*location = xchg;

return val;

}

}

这种RMW 会将一个新的值xchg 放入地址location 如果该地址是期望的值cmp。否则返回location的值。

下图是dpdk的CAS实现代码,第一句MPLOCKED其实是‘lock’指令,就是锁总线,确保同一时间只有一个CPU线程能写这块内存,然后是cmpxchgl指令,用于比较并交换操作数,这个指令是原子的。写完之后,通过cache一致性模型保证所有核心看到和操作的是同一块实际内存的值而不是自己缓存内的值。最后一句‘:”memory”’是内存屏障,内存屏障属于顺序一致性的内容,参考第三节。

从这里也可以看出,原子操作原语的‘锁’实际上被移到了CPU内部实现。另外一个需要注意的是,目标内存dst必须是volatile 修饰的,意思是编译器每次遇到这个变量都必须从内存读值,而不能从核心自己的缓存或寄存器读值。

总结起来就是:

volatile + lock指令+ cmpxchgl指令+ 缓存一致性模型+ memory指令= 原子操作原语CAS

其他原语的原理只需要将上面公式的cmpxchgl 替换成其他硬件指令即可

图 3.1 Dpdk, CAS 实现代码

3.1.3.2 fetch-and-add

也是一种RMW, 在不同系统下可能有以下命名:

atomic_fetch_add, InterlockedExchangeAdd, LOСK XADD

伪代码

T fetch-and-add(T* location, T x)

{

do atomically

{

T val = *location;

*location = val + x;

return val;

}

}

同一类型的原语还有fetch-and-sub, fetch-and-and, fetch-and-or, fetch-and-xor,下面是dpdk 的实现

相关主题