多核体系结构与并行编程模型计算机科学导论件学习教案

《多核体系结构与并行编程模型计算机科学导论件学习教案》由会员分享，可在线阅读，更多相关《多核体系结构与并行编程模型计算机科学导论件学习教案（43页珍藏版）》请在金锄头文库上搜索。

1、会计学1多核体系结构与并行编程模型多核体系结构与并行编程模型(mxng)计计算机科学导论件算机科学导论件第一页，共43页。课课 程程 内内 容容n n课程内容课程内容n n围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论,程序理论和计算理论程序理论和计算理论n n1.1.模型理论关心的问题模型理论关心的问题n n 给定给定(idn)(idn)模型模型M M，哪些问，哪些问题可以由模型题可以由模型M M解决；如何比较模解决；如何比较模型的表达能力型的表达能力n n2.2.程序理论关心的问题程序理论关心的问题n n给定给定(idn)(idn)模型模型M M，如何用模，如何用模型型M M解决

2、问题解决问题n n包括程序设计范型、程序设计语包括程序设计范型、程序设计语言、程序设计、形式语义、类型言、程序设计、形式语义、类型论、程序验证、程序分析等论、程序验证、程序分析等n n3.3.计算理论关心的问题计算理论关心的问题n n给定给定(idn)(idn)模型模型M M和一类问和一类问题题,解决该类问题需多少资源解决该类问题需多少资源第1页/共42页第二页，共43页。讲讲 座座 提提 纲纲n n基本知识基本知识n n多核体系结构、并行编程模型多核体系结构、并行编程模型(mxng)(mxng)n n内存一致性模型内存一致性模型(mxng)(mxng)n n严格一致性模型严格一致性模型(mx

3、ng)(mxng)、顺序、顺序一致性模型一致性模型(mxng)(mxng)、内存一致、内存一致性模型性模型(mxng)(mxng)的重要性的重要性n n共享内存并行编程模型共享内存并行编程模型(mxng)(mxng)n n同步、锁、临界区、条件变量、同步、锁、临界区、条件变量、死锁、数据竞争死锁、数据竞争n n消息传递并行编程模型消息传递并行编程模型(mxng)(mxng)n n消息传递、同步与异步消息传递、同步与异步第2页/共42页第三页，共43页。n n对称对称(duchn)(duchn)多处理器多处理器n n对对称称(duchn)(duchn)多多处处理理器器的的体体系系结结构构二级二级

4、缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器基基 本本 知知 识识 必须在必须在处理器的处理器的缓存中找缓存中找到它操作到它操作的大部分的大部分数据，以数据，以保证保证(bozhng)性能性能 通过共享内存(ni cn)来进行通信第3页/共42页第四页，共43页。n n几个概念的粗略解释几个概念的粗略解释n n任任务务：一一般般性性的的抽抽象象术术语语，指指由由软软件件完完成成的的一一个个活活动动(hu(hudng)dng)。例例如如，矩矩阵阵分分块块乘乘

5、就就是是把把矩矩阵阵乘乘分分成成多多个个任任务务,以以便便于于在在对对称称多多处处理器上并行执行这些任务理器上并行执行这些任务n n进进程程：任任务务在在程程序序中中的的对对应应物物，它它有有自自己己的的数数据据和和代代码码，需需要要在在处处理理器器上上运运行行直直至至结结束束。进进程程是是操操作作系系统统进进行行资资源源分分配配和和调调度度的的独立单位独立单位n n线线程程：是是把把进进程程细细分分出出现现的的实实际际运运行行单单位位，线线程程是是进进程程中中一一段段顺顺序序执执行行的的语语句句序序列列。把把进进程程分分成成若若干干线线程程是是为为了了提提高高进进程程执执行行过过程程中中的的

6、并并行行性性。线线程程是是操操作作系系统统调度的基本单位调度的基本单位n n下面未严格区分进程和线程下面未严格区分进程和线程基基 本本 知知 识识第4页/共42页第五页，共43页。n n几个概念的粗略几个概念的粗略(cl)(cl)解释解释n n并并行行(parallel):(parallel):多多个个可可以以同同时时执执行行的的任任务务，在在多多处处理理器器上上同同时时执执行行n n并并发发(cuncorrent)(cuncorrent)：多多个个可可以以同同时时执执行行的的任任务务，在在单单处处理理器器上上交交错执行错执行n n并并发发是是逻逻辑辑上上同同时时发发生生，而而并并行是物理上同

7、时发行是物理上同时发n n生。下面不区分并行和并发生。下面不区分并行和并发基基 本本 知知 识识tABtAB第5页/共42页第六页，共43页。n n对称对称(duchn)(duchn)多处理器多处理器n n对对称称(duchn)(duchn)多多处处理理器器的的体体系系结结构构二级二级缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器基基 本本 知知 识识 多个多个(du )高性高性能处理器可以集成在能处理器可以集成在一块芯片上一块芯片上第6页/共42页第七页，

8、共43页。基基 本本 知知 识识n n单单核核结结构构(jigu)(jigu)与与多多核核系系统统结结构构(jigu)(jigu)执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑单核结构单核结构(jigu)多处理器结构多处理器结构(jigu)执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑CPU状态状态中断逻辑中断逻辑超线程结构超线程结构 超线程技术充分利用执行超线程技术充分利用执行单元中的空闲资源，以便在单元中的空闲资源，以便在相同时间内完成更多工作相同时间内完成更

9、多工作 执行单元中的资源：内存执行单元中的资源：内存访问部件、算术运算部件和访问部件、算术运算部件和浮点功能部件等浮点功能部件等第7页/共42页第八页，共43页。基基 本本 知知 识识n n单单核核结结构构(jigu)(jigu)与与多多核核系系统统结结构构(jigu)(jigu)执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑单核结构单核结构(jigu)多处理器结构多处理器结构(jigu)执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑CPU状态状态中断逻辑中断逻辑

10、超线程结构超线程结构 超线程技术本质上就是多超线程技术本质上就是多个线程共享一个执行核个线程共享一个执行核 两套两套CPU状态状态 +中断逻辑中断逻辑是为了适应两个线程同时执是为了适应两个线程同时执行的需要行的需要第8页/共42页第九页，共43页。基基 本本 知知 识识n n单单核核结结构构(jigu)(jigu)与与多多核核系系统统结结构构(jigu)(jigu)共享缓存的多核体系结构共享缓存的多核体系结构执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑执行单元执行单元 缓存缓存CPU状态状态中断逻辑中断逻辑多核体系结构多核体系结构执行单元执行单元缓缓 存存CPU状态状态中断逻辑中断

11、逻辑执行单元执行单元CPU状态状态中断逻辑中断逻辑 多核处理器是把两个甚至更多的独立执行核嵌入到一个处理器的内部(nib)，每个线程都有完整的硬件执行环境，各线程之间实现了真正意义上的并行第9页/共42页第十页，共43页。基基 本本 知知 识识n n单核结构与多核系统结构单核结构与多核系统结构n n体体系系结结构构越越来来越越复复杂杂，若若这这些些复杂的特征都要反复杂的特征都要反n n映映到到编编程程语语言言中中，才才能能写写出出较较好好利用体系结构优点利用体系结构优点n n的的程程序序，则则编编写写程程序序将将是是很很困困难难(knnn)(knnn)的工作的工作n n需需要要设设计计好好的的

12、编编程程模模型型并并通通过过编译器和操作系统编译器和操作系统n n的帮助和支持来解决的帮助和支持来解决采用超线程技术的多核体系结构采用超线程技术的多核体系结构执行单元执行单元缓存缓存CPU状态状态中断逻辑中断逻辑CPU状态状态中断逻辑中断逻辑执行单元执行单元缓存缓存CPU状态状态中断逻辑中断逻辑CPU状态状态中断逻辑中断逻辑第10页/共42页第十一页，共43页。基基 本本 知知 识识n n并行编程模型并行编程模型n n是是底底层层体体系系结结构构与与上上层层应应用用程程序序之间的桥梁之间的桥梁n n向向上上隐隐藏藏并并行行处处理理器器的的细细节节，并并向程序员提供表达并行的方法向程序员提供表达

13、并行的方法n n向向下下充充分分利利用用硬硬件件资资源源，高高效效且且正确地完成应用需求正确地完成应用需求n n任任务务划划分分(hu(hufn)fn)、任任务务映映射射、数数据据分分布布、通通信信和和同同步步是是设设计计并并行行编编程程模模型型时时需需要要考考虑虑的的五五个个关关键要素键要素n n并行编程模型的另一种说法并行编程模型的另一种说法n n并并行行编编程程模模型型是是编编写写可可被被编编译译和和运行的并行程序的一种模型运行的并行程序的一种模型第11页/共42页第十二页，共43页。基基 本本 知知 识识n n并行编程模型的分类并行编程模型的分类n n1.1.按进程交互的机制来分按进程

14、交互的机制来分n n共共享享内内存存模模型型：进进程程共共享享可可以以异异步地读写的全局数据空间步地读写的全局数据空间n n消消息息传传递递模模型型:进进程程通通过过相相互互传传递递消息来交换数据消息来交换数据n n隐隐式式模模型型：进进程程之之间间交交互互是是用用户户不可访问的不可访问的n n2.2.按问题分解按问题分解n n任任务务并并行行：每每个个处处理理器器执执行行不不同同的任务的任务n n数数 据据 并并 行行 ： 把把 大大 任任 务务 分分 别别(fnbi)(fnbi)成若干个相同的子任务成若干个相同的子任务n n3.3.第12页/共42页第十三页，共43页。内存内存(nicn)

15、(nicn)一致性模型一致性模型n n内存一致性模型内存一致性模型n n描描述述的的是是，在在有有共共享享内内存存的的多多处处理理器器系系统统上上，在在它它们们读读写写共共享享内内存存操操作作的的可可能能执执行行顺顺序序中中，哪哪些些顺序是正确的顺序是正确的n n内内存存一一致致性性模模型型是是理理解解并并行行程程序序语义的一个关键语义的一个关键n n为为确确保保写写出出正正确确的的并并行行程程序序，程程序序员员必必须须准准确确理理解解并并行行程程序序的的语语义义n n随随着着多多核核处处理理器器的的广广泛泛应应用用，并并行行程程序序设设计计已已经经由由一一种种特特殊殊的的、只只需需少少数数高

16、高端端技技术术人人才才(rnci)(rnci)掌掌握握的的技技巧巧，变变为为一一种种大大多多数数程程序员都应该掌握的基本技能序员都应该掌握的基本技能第13页/共42页第十四页，共43页。内存内存(nicn)(nicn)一致性模型一致性模型n n严格一致性（原子一致性）模型严格一致性（原子一致性）模型(mxng)(mxng)n n任何对内存位置任何对内存位置x x的读操作，的读操作，得到的是最近一次对得到的是最近一次对n nx x的写操作所写入的值的写操作所写入的值n n 单处理器遵守严格一致性单处理器遵守严格一致性n n下面下面,P1,P1和和P2P2是处理器是处理器,x,x是共是共享变量享变

17、量,初值是初值是0 0。n nW(x)1W(x)1表示表示:把把1 1写到写到x x中；中；R(x)3R(x)3表表示示:读取读取x,x,得值得值3 3n nP1:W(x)1P1:W(x)1P1:P1:W(x)1W(x)1n nP2:R(x)1R(x)1P2:R(x)1R(x)1P2:R(x)0P2:R(x)0R(x)1R(x)1n nP1:W(x)1P1:W(x)1n nP2:R(x)0R(x)1P2:R(x)0R(x)1ttt 左边不符合严格(yng)一致性 多处理器+共享内存时, 会出现读写或写写操作的冲突第14页/共42页第十五页，共43页。n n顺序一致性模型顺序一致性模型n n比严

18、格比严格(yng)(yng)一致性弱的模型一致性弱的模型n n在在多多处处理理器器共共享享内内存存情情况况下下，每每个个处处理理器器执执行行的的单单个个线线程程严严格格(yng)(yng)按按照照程程序序规规定定的的顺顺序序逐逐语语句地进行内存访问操作句地进行内存访问操作n n比比顺顺序序一一致致性性还还弱弱的的统统称称为为弱弱内内存模型（不同情况有不同名称）存模型（不同情况有不同名称）n n大大多多数数程程序序员员假假定定并并行行程程序序的的运运行满足顺序一致行满足顺序一致n n性性，但但现现实实中中几几乎乎所所有有的的并并行行程程序都在某种弱内存序都在某种弱内存n n模模型型下下运运行行，

19、而而且且不不同同的的并并行行语语言和处理器的内存言和处理器的内存n n模型不同模型不同内存内存(ni cn)一致性模型一致性模型第15页/共42页第十六页，共43页。n n顺序一致性模型顺序一致性模型n n例：互斥使用临例：互斥使用临n n界区的并行线程界区的并行线程n n 若若两两个个线线程程严严格格按按照照给给出出的的语句顺序逐条执行，语句顺序逐条执行，n n则则它它们们能能实实现现互互斥斥功功能能，因因为为(ynwi)r1(ynwi)r1和和r2r2不可能同时为不可能同时为0 0n n现现实实中中，编编译译器器和和处处理理器器内部进行的优化都会导内部进行的优化都会导n n致致内内存存操操

20、作作的的实实际际顺顺序序和和代代码码中中的语句顺序不一致的语句顺序不一致, ,n n使使得得两两个个条条件件判判断断都都为为真真，两两个个线程都进入临界区线程都进入临界区内存内存(ni cn)一致性模型一致性模型x和和y: 共享变量共享变量, 初始初始:x = 0, y = 0x = 1;y = 1;r1 = y;r2 = x;if (r1= 0)if (r2= 0) critical region critical region第16页/共42页第十七页，共43页。n n内存一致性模型的重要性内存一致性模型的重要性n n它它作作为为系系统统实实现现和和程程序序员员之之间间的的接接口口，对对处

21、处理理器器体体系系结结构构的的实实现现、并并行行语语言言的的实实现现、并并行行程程序序的的开开发和验证都有重要意义发和验证都有重要意义n n以并行语言的设计和实现为例以并行语言的设计和实现为例n n编编译译器器的的优优化化算算法法会会调调整整源源程程序序中中的的内内存存操操作作(cozu)(cozu)顺顺序序，使使得得目目标标程程序序和和源源程程序序的的顺顺序序不不一一致致n n目目标标程程序序的的执执行行顺顺序序又又可可能能被被处处理器进一步改变理器进一步改变n n并并行行语语言言的的设设计计和和实实现现必必须须考考虑虑到到这这两两种种情情况况及及其其效效果果的的叠叠加加，对对源源程程序序可

22、可能能表表现现出出的的行行为为进进行行准准确确描描述述( (并并行行语语言言的的内内存存模模型型) )，便于正确编程，便于正确编程内存内存(ni cn)一致性模型一致性模型第17页/共42页第十八页，共43页。n n编编程程语语言言内内存存一一致致性性模模型型的的现现状状(xinzhung)(xinzhung)n n由由于于优优化化算算法法的的多多样样性性，编编程程语言内存模型比体语言内存模型比体n n系结构的内存模型复杂系结构的内存模型复杂n nGoslingGosling等等为为第第一一版版JavaJava语语言言给给出出的的内内存存一一致致性性模模型型,无无法法支支持持常常用用的优化算法

23、的优化算法,是一个失败的模型是一个失败的模型n nMansonManson等等给给出出的的JavaJava模模型型，虽虽被被语语言言新新标标准准所所采采纳纳，但但模模型型十十分分晦晦涩涩，是是JavaJava语语言言中中最最复复杂杂部部分分,极少有人能正确理解其含义极少有人能正确理解其含义n nBoehmBoehm和和AdveAdve试试图图为为C+C+提提供供一一个个简简单单的的模模型型，但但很很多多地地方方有有歧歧义义或不清晰或不清晰内存内存(ni cn)一致性模型一致性模型第18页/共42页第十九页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n

24、使用共享内存的错误例子使用共享内存的错误例子n n并并行行(bngxng)(bngxng)计计算算FibonacciFibonacci序序列下一个元素的两个线程列下一个元素的两个线程n n对两个线程的执行没有任何约束对两个线程的执行没有任何约束n n下下 面面 是是 两两 个个 线线 程程 某某 次次 并并 行行(bngxng)(bngxng)时的语句执行顺序时的语句执行顺序prev和和curr: 初值分为初值分为(fn wi)0和和1的的共享变量共享变量int retval; int retval;retval = curr; retval = curr; curr = curr+prev;

25、 curr = curr+prev; prev = retval; prev = retval; t第19页/共42页第二十页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n使用共享内存的错误例子使用共享内存的错误例子n n并并行行(bngxng)(bngxng)计计算算FibonacciFibonacci序序列下一个元素的两个线程列下一个元素的两个线程n n对两个线程的执行没有任何约束对两个线程的执行没有任何约束n n下下 面面 是是 两两 个个 线线 程程 某某 次次 并并 行行(bngxng)(bngxng)时的语句执行顺序时的语句执行顺序pre

26、v和和curr: 初值分为初值分为(fn wi)0和和1的共的共享变量享变量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t111111第20页/共42页第二十一页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n使用共享内存的错误例子使用共享内存的错误例子n n并并行行计计算算FibonacciFibonacci序序列列下下一一个个元元素的两个线程素的两个线程n

27、n对对两两个个线线程程的的执执行行没没有有(mi(miyu)yu)任何约束任何约束n n下下面面是是两两个个线线程程某某次次并并行行时时的的语语句执行顺序句执行顺序n n显然结果显然结果n n不对不对n n原因：原因：n n 对共享变对共享变n n量的访问缺量的访问缺n n乏约束乏约束prev和和curr: 初值分为初值分为(fn wi)0和和1的的共享变量共享变量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retva

28、l; t111111第21页/共42页第二十二页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n同步同步n n同同步步是是对对线线程程执执行行的的顺顺序序进进行行强强行行限限制制(xinzh)(xinzh)的的一一种种机机制制，用用来来控控制制线线程程执执行行的的相相对对顺顺序序，可可以以有有效效解解决决任任何何线线程程之之间间的的冲冲突突，而而这这些些冲冲突突有有可可能能会会导导致致线线程程的的执行出现异常行为执行出现异常行为n n简简言言之之，同同步步主主要要用用于于协协调调线线程程执行和管理共享数据执行和管理共享数据n n同步机制同步机制n n信

29、信号号量量、锁锁（又又可可细细分分成成多多种种）、条件变量、条件变量、第22页/共42页第二十三页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n锁锁n n用用来来体体现现一一种种互互斥斥的的并并行行控控制制策策略略n n一一个个线线程程在在同同一一个个时时刻刻只只能能使使用用一一个个锁锁，一一个个锁锁至至多多由由一一个个线线程程获得。锁有两个原子操作：获得。锁有两个原子操作：n n1.acquire:1.acquire:n n 等待等待(dngdi)(dngdi)锁状锁状n n态变为未加态变为未加n n锁状态，然锁状态，然n n后将其置为后将其置为n

30、 n已加锁状态已加锁状态prev和和curr: 初值分为初值分为(fn wi)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; 第23页/共42页第二十四页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n锁锁n n用用来来体体现现一一种种互互斥斥的的并并行行控控制制策策略略n n一一个

31、个(y(y)线线程程在在同同一一个个(y(y)时时刻刻只只能能使使用用一一个个(y(y)锁锁，一一个个(y(y)锁锁至至多多由由一一个个(y(y)线线程获得。锁有两个原子操作：程获得。锁有两个原子操作：n n2.release:2.release:n n 将锁状态将锁状态n n由已加锁变由已加锁变n n为未加锁为未加锁prev和和curr: 初值分为初值分为(fn wi)0和和1的共的共享变量享变量L是锁是锁int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev;

32、 curr = curr+prev;prev = retval; prev = retval;L-release(); L-release(); 第24页/共42页第二十五页，共43页。共享内存并行共享内存并行(bngxng)(bngxng)编程模型编程模型n n临界区（临界区（criticalsectioncriticalsection）n n指指包包含含(bohn)(bohn)有有共共享享变变量量的的一段代码，这些共享变量和一段代码，这些共享变量和n n多个线程之间存在相关关系多个线程之间存在相关关系n n多多线线程程编编程程的的主主要要挑挑战战在在于于需需要以多个线程执行要以多个线程执行

33、n n互斥操作的互斥操作的n n方式实现临方式实现临n n界区，以保界区，以保n n证多个线程证多个线程n n不会同时访不会同时访n n问临界区问临界区prev和和curr: 初值分为初值分为(fn wi)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(); 第25页/共42页第二

34、十六页，共43页。n n条件变量条件变量n n例：生产者例：生产者/ /消费者问题消费者问题n n一个一个(y)(y)典型的同步问题典型的同步问题n n也称有限缓冲区问题也称有限缓冲区问题n n生产者向缓冲区中写入生产者向缓冲区中写入n n数据数据n n消费者从缓冲区取得数消费者从缓冲区取得数n n据并对数据进行操作据并对数据进行操作n n生产者和消费者并行执生产者和消费者并行执n n行行共享内存并行共享内存并行(bngxng)编程模型编程模型void producer() / 临界区开始临界区开始 / 产生产生(chnshng)下一个数下一个数据据 / 临界区结束临界区结束void cons

35、umer() / 临界区开始临界区开始 / 消费下一个数据消费下一个数据 / 临界区结束临界区结束第26页/共42页第二十七页，共43页。n n条件变量条件变量n n右边是生产者线程，条右边是生产者线程，条n n件变量件变量C C使用锁使用锁L L来完成来完成n n对共享数据的访问，可对对共享数据的访问，可对n n条件变量条件变量C C执行执行3 3种原子操种原子操n n作（作（LCLC的初值为的初值为falsefalse）n n1.1.wait(L):wait(L):释释放放自自身身(zshn)(zshn)持有持有n n的锁并处于的锁并处于C C的等待队列。的等待队列。n n执行完毕时，锁已

36、被其他执行完毕时，锁已被其他n n线程获得线程获得共享内存并行共享内存并行(bngxng)编程模型编程模型void producer() while(1) L-acquire(); / 临界区开始临界区开始(kish) while(LC = true) C-wait(L); / 产生下一个数据产生下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 第27页/共42页第二十八页，共43页。n n条件变量条件变量n n右边是生产者线程，条右边是生产者线程，条n n件变量件变量C C使用使用(shyng)(shyng)锁锁L L来完成来完成

37、n n对共享数据的访问，可对对共享数据的访问，可对n n条件变量条件变量C C执行执行3 3种原子操种原子操n n作（作（LCLC的初值为的初值为falsefalse）n n2.signal(L):2.signal(L):发信号，允许发信号，允许n n等待等待C C的一个线程往下执的一个线程往下执n n行。该操作完毕后，锁仍行。该操作完毕后，锁仍n n然被发信号的线程持有然被发信号的线程持有共享内存并行共享内存并行(bngxng)编程模型编程模型void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-wait(

38、L); / 产生下一个产生下一个(y )数数据据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 第28页/共42页第二十九页，共43页。n n条件变量条件变量n n右边是生产者线程，条右边是生产者线程，条n n件变量件变量C C使用锁使用锁L L来完成来完成n n对共享数据的访问，可对对共享数据的访问，可对n n条件变量条件变量C C执行执行3 3种原子操种原子操n n作（作（LCLC的初值为的初值为falsefalse）n n3.broadcast(L):3.broadcast(L):发信号，发信号，n n允允许许所所有有等等待待(dng

39、di)C(dngdi)C的的线线程程往往n n下执行。该操作完毕后下执行。该操作完毕后,锁锁n n仍然被发信号的线程持有仍然被发信号的线程持有共享内存并行共享内存并行(bngxng)编程模型编程模型void producer() while(1) L-acquire(); / 临界区开始临界区开始(kish) while(LC = true) C-wait(L); / 产生下一个数据产生下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 第29页/共42页第三十页，共43页。n n生产者生产者/ /消费者问题消费者问题n nvoidp

40、roducer()voidproducer()voidconsumer()voidconsumer()n nwhile(1)while(1) while(1)while(1) L-acquire();L-acquire(); L-acquire();L-acquire();n n/ 临界区开始临界区开始 /临界区开始临界区开始n n while(LCwhile(LC = true)true) while(LC=while(LC=false)false) C-wait(L);C-wait(L);C-wait(L);C-wait(L);n n n n /产产生生下下一一个个(y(y)数数据据/消消

41、费费下下一一个个(y(y)数据数据n nLC=true;LC=true;LC=false;LC=false;n nC-signal(L);C-signal(L);C-signal(L);C-signal(L);n n/ 临界区结束临界区结束/临界区结束临界区结束n nL-release();L-release();L-release()L-release()n n 共享内存并行共享内存并行(bngxng)编程模型编程模型Conditon C; Lock L;BooL LC = false;第30页/共42页第三十一页，共43页。n n条件变量条件变量n n条件变量本身实质上条件变量本身实质上n

42、 n并没有需要检验的条件并没有需要检验的条件n n值，而是使用共享数据值，而是使用共享数据n n的状态来保存线程的条的状态来保存线程的条n n件值，用于多线程之间件值，用于多线程之间n n关于共享数据状态变化关于共享数据状态变化(binhu)(binhu)n n的通信的通信n n当特定条件满足时，当特定条件满足时，n n线程等待或者唤醒其他线程等待或者唤醒其他n n合作线程合作线程共享内存并行共享内存并行(bngxng)编程模型编程模型void producer() while(1) L-acquire(); / 临界区开始临界区开始 while(LC = true) C-wait(L); /

43、 产生产生(chnshng)下一个数据下一个数据 LC = true; C-signal(L); / 临界区结束临界区结束 L-release(); 第31页/共42页第三十二页，共43页。n n死锁死锁n n当当一一个个线线程程因因等等待待另另一一个个线程的资源线程的资源(zyun)(zyun)而阻塞，而而阻塞，而n n同同时时该该资资源源(zyun)(zyun)永永远远不不会会被被释放释放n n自自死死锁锁或或递递归归死死锁锁：线线程程T T试试图图获获得得一一个个锁锁，而而该该锁锁已已被被线线程程T T自自己己拥有拥有n n错错 序序 死死 锁锁 ： 线线 程程 T1T1占占 有有 资资

44、 源源(zyun)r1(zyun)r1并并等等待待由由线线程程T2T2占占有有资资源源(zyun)r2(zyun)r2；而而线线程程T2T2占占有有资资源源(zyun)r2(zyun)r2并并等等待待由由线线程程T1T1占有资源占有资源(zyun)r1(zyun)r1n n编编程程中中的的问问题题：怎怎样样避避免免出出现现死死锁锁共享内存并行共享内存并行(bngxng)编程模型编程模型第32页/共42页第三十三页，共43页。n n数据竞争数据竞争n n多多个个并并行行线线程程都都访访问问某某个个共共享享变量变量v v，其中至少有，其中至少有n n一一个个线线程程修修改改vv，并并且且这这些些线

45、线程程没有使用锁来控制没有使用锁来控制n n它们它们(tmen)(tmen)对对v v的访问的访问n n在在有有数数据据竞竞争争的的场场合合，各各线线程程对对数数据据的的访访问问次次序序是是不不确确定定的的，计计算结果依赖于这个次序算结果依赖于这个次序n n数数据据竞竞争争有有时时是是共共享享数数据据和和通通信信的的一一种种方方式式，但但多多数数情情况况下下属属于于程序错误程序错误 n n编编程程中中的的问问题题：怎怎样样发发现现程程序序中中的数据竞争的数据竞争共享内存并行共享内存并行(bngxng)编程模型编程模型第33页/共42页第三十四页，共43页。n n消息传递消息传递n n消消息息传

46、传递递是是进进程程之之间间交交换换信信息息的的一一种种方方式式，使使用用共共享享变变量量是是另另一一种方式种方式n n在在消消息息传传递递场场合合下下，由由于于一一个个消消息息在在被被接接收收者者接接收收之之前前(zhqin)(zhqin)，必必须须由由发发送送者者发发送送，因因此此隐隐含含了同步机制了同步机制n n消消息息传传递递可可以以在在分分布布式式系系统统、共共享享内内存存的的多多处处理理器器系系统统和和单单处处理理器器系系统统中中实实现现。在在分分布布式式系系统统上上实现共享变量有较大难度实现共享变量有较大难度n n实实现现消消息息传传递递依依靠靠两两个个通通信信原原语语：sends

47、end和和receivereceive消息传递并行消息传递并行(bngxng)编程模型编程模型第34页/共42页第三十五页，共43页。n n消消息息传传递递的的发发送送和和接接收收(jishu)(jishu)对象对象n n进进程程对对进进程程的的传传递递：两两个个进进程程不不依依赖赖于于线线程程自自行行进进行行通通信信，是是最最常见的消息传递方式常见的消息传递方式n n进进程程间间的的传传递递：属属于于不不同同进进程程的的线程之间进行通信线程之间进行通信n n进进程程内内的的传传递递：属属于于同同一一个个进进程程的线程之间进行通信的线程之间进行通信消息传递并行消息传递并行(bngxng)编程模

48、型编程模型第35页/共42页第三十六页，共43页。n n消息传递的同步与异步消息传递的同步与异步n n同同步步：消消息息发发送送后后，发发送送者者必必须须等等待待(dngdi)(dngdi)，直直到到接接收收者者的的响响应才能进行其他操作应才能进行其他操作n n异异步步：发发送送者者不不必必等等待待(dngdi)(dngdi)接收者的响应就可以继续执行接收者的响应就可以继续执行n n对对于于采采用用共共享享存存储储模模型型的的系系统统来来说，消息传递必须是同步的说，消息传递必须是同步的n n对对于于采采用用分分布布式式存存储储模模型型的的系系统统来说，消息传递则是异步的来说，消息传递则是异步的

49、消息传递并行消息传递并行(bngxng)编程模型编程模型第36页/共42页第三十七页，共43页。n n用用消消息息传传递递机机制制解解决决生生产产者者/ /消消费费者问题者问题n nvoidproducer()voidproducer()voidconsumer()voidconsumer()n nmessagepmsg;messagepmsg;messagecmsg;messagecmsg;n nwhile(1)while(1) while(1)while(1)n n receive(cbox,receive(cbox, pmsg);pmsg); receive(pbox,receive(p

50、box,cmsg);cmsg);n npmsg=produce();pmsg=produce();consume(cmsg);consume(cmsg);n nsend(pbox,pmsg);send(pbox,pmsg);send(cbox,NULL);send(cbox,NULL);n n n n n n/*/* 等待空消息、生产等待空消息、生产/*/*接收接收(jishu)(jishu)消息、消耗消消息、消耗消n n消息、发送消息消息、发送消息* 息息、发送空消息发送空消息*/*/消息传递并行消息传递并行(bngxng)编程模型编程模型第37页/共42页第三十八页，共43页。n n用用消

51、消息息传传递递机机制制(jzh)(jzh)解解决决生生产产者者/ /消费者问题消费者问题n nvoidproducer()voidproducer()voidconsumer()voidconsumer()n nmessagepmsg;messagepmsg;messagecmsg;messagecmsg;n nwhile(1)while(1) while(1)while(1)n n receive(cbox,receive(cbox, pmsg);pmsg); receive(pbox,receive(pbox,cmsg);cmsg);n npmsg=produce();pmsg=produ

52、ce();consume(cmsg);consume(cmsg);n nsend(pbox,pmsg);send(pbox,pmsg);send(cbox,NULL);send(cbox,NULL);n n n n n nvoidvoid main()main() 创创建建消消息息信信箱箱pbox,cbox;pbox,cbox;n n 给给cboxcbox发发NULLNULL消消息息;创创建建进进程程producerproducer和和consumer;consumer;n n 消息传递并行消息传递并行(bngxng)编程模型编程模型第38页/共42页第三十九页，共43页。小小 结结n n本讲

53、座小结本讲座小结n n计计算算机机体体系系结结构构的的多多样样性性，导导致致难难以以从从它它们们概概括括出出一一种种能能代代表表它它们们的的抽抽象象机机，并并进进一一步步抽抽象象出出统统一一的的并并行行(bngxng)(bngxng)编编 程程 模模 型型 （ 即即 并并 行行(bngxng)(bngxng)编程语言）编程语言）n n更更 难难 做做 到到 的的 是是 ： 基基 于于 这这 种种 并并 行行(bngxng)(bngxng)编编程程模模型型编编写写的的程程序序，通通过过编编译译器器和和操操作作系系统统的的支支持持，目目标标程程序序运运行行时时充充分分发发挥挥各各种种体体系系结结构

54、构的的长长处处n n通通过过对对共共享享内内存存和和消消息息传传递递两两种种并并行行(bngxng)(bngxng)编编程程模模型型的的简简单单介介绍绍，远远未未体体现现多多核核时时代代对对并并行行(bngxng)(bngxng)软软件件开开发发的的各各个个方方面面（并并行行(bngxng)(bngxng)算算法法的的设设计计和和分分析析、程程序序的的测测试试和和调调试、程序的分析和验证）的挑战试、程序的分析和验证）的挑战第39页/共42页第四十页，共43页。小小 结结n n本讲座小结本讲座小结n n并并行行编编程程模模型型（modelmodel）：是是编编写写可可被被编编译译和和运运行行的的

55、并并行行程程序序的的一一种种模模型型n n并并行行编编程程模模式式（patternpattern）：是是面面向向一类问题的并行程序的框架一类问题的并行程序的框架n n两两者者被被混混用用：常常用用编编程程模模式式中中的的主主要要(zhyo)(zhyo)机机制制经经常常出出现现在在编编程程模模型中型中n n相关课程相关课程n n计计算算机机体体系系结结构构、操操作作系系统统、编编译译原理、并行计算原理、并行计算第40页/共42页第四十一页，共43页。小小 结结n n研究方向研究方向n n怎怎样样从从现现代代体体系系结结构构抽抽象象出出计计算算模模型型n n面向体系结构的编译面向体系结构的编译(biny)(biny)优化优化n n并行程序的形式验证方法并行程序的形式验证方法第41页/共42页第四十二页，共43页。内容(nirng)总结会计学。围绕学科理论体系中的模型理论, 程序理论和计算理论。给定模型M和一类问题, 解决该类问题需多少资源。第1页/共42页。第3页/共42页。例如，矩阵分块乘就是把矩阵乘分成多个任务, 以便于在对称多处理器上并行执行这些任务。体系结构越来越复杂，若这些复杂的特征都要反。任务并行：每个处理器执行不同的任务。数据并行：把大任务分别成若干个相同的子任务。比顺序一致性还弱的统称(tngchng)为弱内存模型（不同情况有不同名称）第四十三页，共43页。