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

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