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