多核体系结构与并行编程模型计算机科学导论第八讲(1).ppt

多核体系结构与并行编程模型 计算机科学导论第八讲,计算机科学技术学院 陈意云 /yiyun/,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M，如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,2,本讲座概要介绍并行编程模型及一些相关概念,讲 座 提 纲,基本知识 多核体系结构、并行编程模型 内存一致性模型 严格一致性模型、顺序一致性模型、内存一致性模型的重要性 共享变量并行编程模型 同步、锁、临界区、条件变量、死锁、数据竞争 消息传递并行编程模型 消息传递、同步与异步,3,对称多处理器 对称多处理器的体系结构,基 本 知 识,必须在处理器的缓存中找到它操作的大部分数据，以保证性能,通过共 享内存来 进行通信,4,几个概念的粗略解释 任务：一般性的抽象术语，指由软件完成的一个活动。例如，矩阵分块乘就是把矩阵乘分成多个任务, 以便于在对称多处理器上并行执行这些任务 进程：任务在程序中的对应物，它有自己的数据和代码，需要在处理器上运行直至结束。进程是操作系统为其进行资源分配和调度的独立单位 线程：是把进程细分出现的实际运行单位，线程是进程中一段顺序执行的语句序列。把进程分成若干线程是为了提高进程执行过程中的并行性。线程是操作系统调度的基本单位 下面未严格区分进程和线程,基 本 知 识,5,几个概念的粗略解释 并行(parallel): 多个可以同时执行的任务，在多处理器上同时执行 并发(cuncorrent)：多个可以同时执行的任务，在单处理器上交错执行 并发是逻辑上同时发生，而并行是逻辑上和物理上都同时发生。下面不区分并行和并发,基 本 知 识,6,对称多处理器 对称多处理器的体系结构,基 本 知 识,多个高性能处理器可以集成在一块芯片上,7,基 本 知 识,单核结构与多核系统结构,单核结构,多处理器结构,超线程技术充分利用执行单元中的空闲资源，以便在相同时间内完成更多工作 执行单元中的资源：内存访问部件、算术运算部件和浮点功能部件等,8,基 本 知 识,单核结构与多核系统结构,单核结构,多处理器结构,超线程技术本质上就是多个线程共享一个执行核 两套CPU状态 +中断逻辑是为了适应两个线程同时执行的需要,9,基 本 知 识,单核结构与多核系统结构,共享缓存的多核体系结构,多核体系结构,多核处理器是把两个甚至更多的独立执行核嵌入到一个处理器的内部，每个线程都有完整的硬件执行环境，各线程之间实现了真正意义上的并行,10,基 本 知 识,单核结构与多核系统结构 体系结构越来越复杂，若这些复杂的特征都要反 映到编程语言中，才能写出较好利用体系结构优点 的程序，则编写程序将是很困难的工作 需要设计好的编程模型并通过编译器和操作系统 的帮助和支持来解决,11,基 本 知 识,并行编程模型 是底层体系结构与上层应用程序之间的桥梁 向上隐藏并行处理器的细节，并向程序员提供表达并行的方法 向下充分利用硬件资源，高效且正确地完成应用需求 任务划分、任务映射、数据分布、通信和同步是设计并行编程模型时需要考虑的五个关键要素 并行编程模型的另一种说法 并行编程模型是编写可被编译和运行的并行程序的一种抽象并行机器模型,12,基 本 知 识,并行编程模型的分类 1. 按进程交互的机制来分 共享变量模型：进程共享可以异步地读写的全局变量 消息传递模型: 进程通过相互传递消息来交换数据 隐式模型：进程之间交互是用户不可访问的 2. 按问题分解 任务并行：每个处理器执行不同的任务 数据并行：把大任务分解成若干个相同的子任务 3. ,13,内存一致性模型,并行计算给共享变量读写带来的问题 串行程序 并行程序 x的初值为0 x在共享存储中，初值为0 x = x + 1 x = x + 1 | x = x + 2 x = x + 2 （注：| 分隔两段并行代码） 结果 ：x = 3 x可能但并非一定是3 为什么？ 在一个进程执行x = x +1期间，共享的x有可能被 其它进程读写,14,内存一致性模型,并行计算给共享变量读写带来的问题 并行程序 x = x + 1 | x = x + 2 x结果不等于3的情况 x = R x = R x = R R+1 = R R+2 = R x = R R = x R+1 = R R = x R+2 = R R = x R = x 结果：x = 1 结果：x = 2 x = x +1的执行：取x到寄存器R, R增1, 把R存到x 各处理器有各自的R，不共享；x是共享的,15,t,内存一致性模型,内存一致性模型 内存一致性模型(memory consistency model)描述程序员和系统之间的一种协议。若程序员书写的软件遵循内存操作的专门规则，系统就保证内存表现得有规律并且内存操作的结果可预测 专门规则描述的是，在有共享内存的多处理器系统上，在它们读写共享内存操作的可能执行顺序中，哪些顺序是正确的 有些模型的专门规则对软件只有少量限制，而有些则使普通编程几乎成为不可能。规则限制少的模型没有限制多的模型执行效果好,16,内存一致性模型,内存一致性模型 内存一致性模型是理解并行程序语义的一个关键 为确保写出正确的并行程序，程序员必须准确理解并行程序的语义 随着多核处理器的广泛应用，并行程序设计已经由一种特殊的、只需少数高端技术人才掌握的技巧，变为一种大多数程序员都应该掌握的基本技能,17,内存一致性模型,严格一致性（原子一致性）模型 一个进程对任何内存位置x的读操作，得到的是 最近一次对x的写操作所写入的值 在下面的图示中, P1和P2是处理器, x的初值是0 W(x)1表示：把1写到x中；R(x)3表示：读取x， 得到值3 P1: W(x)1 P1: W(x)1 P2: R(x)1 R(x)1 P2: R(x)0 R(x)1 P1: W(x)1 P2: R(x)0 R(x)1,t,t,t,左下图不符合严格一致性,18,内存一致性模型,严格一致性（原子一致性）模型 一个进程对任何内存位置x的读操作，得到的是 最近一次对x的写操作所写入的值 单处理器遵守严格一致性 在多处理器+共享内存的系统中，要实现严格 一致性模型几乎是不可能的,19,顺序一致性模型 比严格一致性弱的模型 在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作 P1: W(x)1 P2: W(x)2 P3: R(x)2 R(x)1 P4: R(x)2 R(x)1,内存一致性模型,20,t,t,t,t,左图符合顺序一致性： W(x)2先于W(x)1发生,顺序一致性模型 比严格一致性弱的模型 在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作 P1: W(x)1 P2: W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2,内存一致性模型,21,t,t,t,t,左图不符合顺序一致性： 不论W(x)1和W(x)2谁先发生,顺序一致性模型 比严格一致性弱的模型 在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作 比顺序一致性还弱的有多种弱内存模型 大多数程序员假定并行程序的运行满足顺序一致 性，但现实中几乎所有的并行程序都在某种弱内存 模型下运行，而且不同的并行语言和处理器的内存 模型不同,内存一致性模型,22,顺序一致性模型 例：互斥使用临 界区的并行线程 若两个线程严格按照给出的语句顺序逐条执行， 则它们能实现互斥功能，因为r1和r2不可能同时为0 现实中，编译器和处理器内部进行的优化都会导 致内存操作的实际顺序和代码中的语句顺序不一致, 例：上述两线程的前两个语句被编译器交换次序, 使得两个条件判断都为真，两个线程都进入临界区,内存一致性模型,x和y: 共享变量, 初始:x = 0, y = 0 x = 1; y = 1; r1 = y; r2 = x; if (r1= 0) if (r2= 0) critical region critical region ,23,r1 = y; x = 1;,r2 = x; y = 1;,t,内存一致性模型的重要性 它作为系统实现和程序员之间的接口，对处理器体系结构的实现、并行语言的设计和实现、并行程序的开发和验证都有重要意义 以并行语言的设计和实现为例 编译器的优化算法会调整源程序中的内存操作顺序，使得目标程序和源程序的顺序不一致 目标程序的执行顺序又可能被处理器进一步改变 并行语言的设计和实现必须考虑到这两种情况及其效果的叠加，对源程序可能表现出的行为进行准确描述(并行语言的内存模型)，便于正确编程,内存一致性模型,24,编程语言内存一致性模型的现状 由于优化算法的多样性，编程语言内存模型比体 系结构的内存模型复杂 Gosling等为第一版Java语言给出的内存一致性模型, 无法支持常用的优化算法, 是一个失败的模型 Manson等给出的Java模型，虽被语言新标准所采纳，但模型十分晦涩，是Java语言中最复杂部分, 极少有人能正确理解其含义 Boehm和Adve试图为C+提供一个简单的模型，但很多地方有歧义或不清晰,内存一致性模型,25,共享变量并行编程模型,使用共享变量的错误例子 并行计算Fibonacci序列下一个元素的两个线程 对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序,prev和curr: 初值分为0和1的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,26,共享变量并行编程模型,使用共享变量的错误例子 并行计算Fibonacci序列下一个元素的两个线程 对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序,prev和curr: 初值分为0和1的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,1,1,1,1,1,1,27,共享变量并行编程模型,使用共享变量的错误例子 并行计算Fibonacci序列下一个元素的两个线程 对两个线程的执行没有任何约束 下面是两个线程某次并行时的语句执行顺序 结果应是 0 +1 = 1 1 +1 = 2 原因： 对共享变 量的访问缺 乏约束,prev和curr: 初值分为0和1的共享变量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,1,1,1,1,1,1,28,共享变量并行编程模型,同步 同步是对线程执行的顺序进行强行限制的一种机制，用来控制线程执行的相对顺序，可以有效解决任何线程之间的冲突，而这些冲突有可能会导致线程的执行出现异常行为 简言之，同步主要用于协调线程执行和管理共享数据 同步机制 信号量、锁（又可细分成多种）、条件变量、,29,共享变量并行编程模型,锁 用来体现一种互斥的并行控制策略 一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作： 1. acquire:,prev和curr: 初值分为0和1的共享变量 L是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,30,锁状态改为已加锁，若锁已被占用则等待，锁的状态保持未加锁,t,共享变量并行编程模型,锁 用来体现一种互斥的并行控制策略 一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作： 2. release: 将锁状态 由已加锁变 为未加锁,prev和curr: 初值分为0和1的共享变量 L是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; L-release(); L-release();,31,t,共享变量并行编程模型,锁 用来体现一种互斥的并行控制策略 一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作： 3. 问题 怎么等待? 忙等待： 不断尝试 睡眠： 等待唤醒,prev和curr: 初值分为0和1的共享变量 L是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; L-release(); L-release();,32,t,共享变量并行编程模型,临界区（critical section） 指包含有共享变量的一段代码，这些共享变量和 多个线程之间存在相关关系 多线程编程的主要挑战在于需要以多个线程执行 互斥操作的 方式实现临 界区，以保 证多个线程 不会同时访 问临界区,prev和curr: 初值分为0和1的共享变量 L是锁 int retval; int retval; L-acquire(); L-acquire(); retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; L-release(); L-release();,33,t,条件变量 共享变量的一种实现方式 例：生产者/消费者问题 一个典型的同步问题， 也称有限缓冲区问题 生产者向缓冲区中写入 数据 消费者从缓冲区取得数 据并对数据进行操作 生产者和消费者并行执行,共享变量并行编程模型,void producer() / 临界区开始 / 产生下一个数据 / 临界区结束 void consumer() / 临界区开始 / 消费下一个数据 / 临界区结束 ,34,条件变量 右边是生产者线程，条 件变量C使用锁L来完成 对共享数据的访问，可对 条件变量C执行3种原子 操作（LC 的初值为false） 1. wait(L): 释放自身持有 的锁并处于C的等待队列。 该执行完毕时，锁已经可 被其他线程获得,共享变量并行编程模型,void producer() while(1) L-acquire(); / 临界区开始 while(LC = true) C-wait(L); / 产生下一个数据 LC = true; C-signal(L); / 临界区结束 L-release(); ,35,Conditon C; Lock L; Bool LC = false;,条件变量 右边是生产者线程，条 件变量C使用锁L来完成 对共享数据的访问，可对 条件变量C执行3种原子 操作（LC 的初值为false） 2. signal(L): 发信号，允许 等待C的一个线程继续执 行。该操作完毕后，锁仍 然由发信号的线程持有,共享变量并行编程模型,void producer() while(1) L-acquire(); / 临界区开始 while(LC = true) C-wait(L); / 产生下一个数据 LC = true; C-signal(L); / 临界区结束 L-release(); ,36,Conditon C; Lock L; Bool LC = false;,条件变量 右边是生产者线程，条 件变量C使用锁L来完成 对共享数据的访问，可对 条件变量C执行3种原子 操作（LC 的初值为false） 3. broadcast(L): 发信号， 允许所有等待C的线程继续 执行。该操作完毕后, 锁 仍然由发信号的线程持有,共享变量并行编程模型,void producer() while(1) L-acquire(); / 临界区开始 while(LC = true) C-wait(L); / 产生下一个数据 LC = true; C-broadcast(L); / 临界区结束 L-release(); ,37,Conditon C; Lock L; Bool LC = false;,生产者/消费者问题 void producer() void consumer() while(1) while(1) L-acquire(); L-acquire(); / 临界区开始 / 临界区开始 while(LC = true) while(LC= false) C-wait(L); C-wait(L); / 产生下一个数据 / 消费下一个数据 LC = true; LC = false; C-signal(L); C-signal(L); / 临界区结束 / 临界区结束 L-release(); L-release() ,共享变量并行编程模型,Conditon C; Lock L; Bool LC = false;,38,条件变量 条件变量用于多线程之 间关于共享数据状态变化 的通信。当一个动作需要 等另一个动作(改变共享数 据状态)完成后才能进行， 就可以使用条件变量 当特定条件满足时，线 程等待或者唤醒其他合作 线程,共享变量并行编程模型,void producer() while(1) L-acquire(); / 临界区开始 while(LC = true) C-wait(L); / 产生下一个数据 LC = true; C-signal(L); / 临界区结束 L-release(); ,39,死锁 当一线程因等待另一线程占用的资源而阻塞，而 同时该资源永远不会被释放 自死锁或递归死锁：线程T试图获得一个锁，而该锁已被线程T自己拥有 错序死锁：线程T1占有资源r1并等待由线程T2占有资源r2；而线程T2占有资源r2并等待由线程T1占有资源r1 编程中的问题：怎样避免出现死锁,共享变量并行编程模型,40,数据竞争 多个并行线程都访问某个共享变量v，其中至少有 一个线程修改v ，并且这些线程没有使用锁来控制 它们对v的访问 在有数据竞争的场合，各线程对数据的访问次序是不确定的，计算结果依赖于这个次序 数据竞争有时是共享数据和通信的一种方式，但多数情况下属于程序错误 编程中的问题：怎样发现程序中的数据竞争,共享变量并行编程模型,41,消息传递 消息传递是进程之间交换信息的一种方式，使用共享变量是另一种方式 在消息传递场合下，由于一个消息在被接收者接收之前，必须由发送者发送，因此隐含了同步机制 消息传递可以在分布式系统、共享内存的多处理器系统和单处理器系统中实现。在分布式系统上实现共享变量有较大难度 实现消息传递依靠两个通信原语：send和receive,消息传递并行编程模型,42,用消息传递机制解决生产者/消费者问题 void producer() void consumer() message pmsg; message cmsg; while (1) while (1) receive(cbox, pmsg); receive(pbox, cmsg); pmsg = produce(); consume(cmsg); send(pbox, pmsg); send(cbox, NULL); /* 等待空消息、生产 /* 接收消息、消耗消 消息、发送消息 */ 息、发送空消息 */,消息传递并行编程模型,43,用消息传递机制解决生产者/消费者问题 void producer() void c