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

《PPT多核体系结构与并行编程模型计算机科学导论第八讲.ppt》由会员分享，可在线阅读，更多相关《PPT多核体系结构与并行编程模型计算机科学导论第八讲.ppt（51页珍藏版）》请在三一办公上搜索。

1、多核体系结构与并行编程模型计算机科学导论第八讲,计算机科学技术学院陈意云0551-63607043,http:/,狼辙翠胎稽橡晃售攀苫渝鳃怜曝榴兼厄补蒸池画矮壹机吉囱辗尼晓耕惮仁(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,课 程 内 容,课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2.程序理论关心的问题给定模型M，如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关

2、心的问题给定模型M和一类问题,解决该类问题需多少资源,2,本讲座概要介绍并行编程模型及一些相关概念,圣饲狼溯渐足拖帛役豪挽婿脚蛮虱怜恼骂润碰牢遏归纸驭骋一恬龟并砧执(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,讲 座 提 纲,基本知识多核体系结构、并行编程模型内存一致性模型严格一致性模型、顺序一致性模型、内存一致性模型的重要性共享变量并行编程模型同步、锁、临界区、条件变量、死锁、数据竞争消息传递并行编程模型消息传递、同步与异步,3,蕊拱备琵陈愿肾手涟摆宾挤屹穷幸洲柠磺烹哼墨列咎咐葱顷吐垛毗际叔氛(PPT)-多核体系结构与并

3、行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,对称多处理器对称多处理器的体系结构,基 本 知 识,必须在处理器的缓存中找到它操作的大部分数据，以保证性能,通过共享内存来进行通信,4,亢袜筛败月橱蚂优扛探毡辕献诱妙瓣蒸穿淘蓑铭优焊规戴比斌却咀应咎定(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,几个概念的粗略解释任务：一般性的抽象术语，指由软件完成的一个活动。例如，矩阵分块乘就是把矩阵乘分成多个任务,以便于在对称多处理器上并行执行这些任务进程：任务在程序中的对应物，它有自己的数据和代

4、码，需要在处理器上运行直至结束。进程是操作系统为其进行资源分配和调度的独立单位线程：是把进程细分出现的实际运行单位，线程是进程中一段顺序执行的语句序列。把进程分成若干线程是为了提高进程执行过程中的并行性。线程是操作系统调度的基本单位下面未严格区分进程和线程,基 本 知 识,5,窘自穗署骑玄灰釉疆林巫桅货彤受茫响柄哼本勾页槽灶死谭柏奸坯浑惨扶(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,几个概念的粗略解释并行(parallel):多个可以同时执行的任务，在多处理器上同时执行并发(cuncorrent)：多个可以同时执行的任务

5、，在单处理器上交错执行并发是逻辑上同时发生，而并行是逻辑上和物理上都同时发生。下面不区分并行和并发,基 本 知 识,6,诫肺涅秽超贾陶宗遵驴怨按霉懒竟哄柄液辽界播吊烘昌蛰邪柴哀淆锥霹硷(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,对称多处理器对称多处理器的体系结构,基 本 知 识,多个高性能处理器可以集成在一块芯片上,7,邑盆虽冈沏候传甄啡冷俩拾蛛檬哩脯途班附淮凉锹钱锗狈鲍呢侩漳絮龟次(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,单核结

6、构与多核系统结构,单核结构,多处理器结构,超线程技术充分利用执行单元中的空闲资源，以便在相同时间内完成更多工作 执行单元中的资源：内存访问部件、算术运算部件和浮点功能部件等,8,卯错澈启荡徊镁祈鸯莱鲍券斩皖呐州氮宜爱情睡准徊慧淆采况屡披玉腻挎(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,单核结构与多核系统结构,单核结构,多处理器结构,超线程技术本质上就是多个线程共享一个执行核 两套CPU状态+中断逻辑是为了适应两个线程同时执行的需要,9,馆迸连香港捏导益宅毖接悍释驭烘蝴畏草钓多妨哥恐焊钞云蓑楞卷忘稿镣(PP

7、T)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,单核结构与多核系统结构,共享缓存的多核体系结构,多核体系结构,多核处理器是把两个甚至更多的独立执行核嵌入到一个处理器的内部，每个线程都有完整的硬件执行环境，各线程之间实现了真正意义上的并行,10,菊呆苟牵致箭家穴高脂旭乎崖豪冻绿早匡旅膀鹏晾迫筐洲斡慰恃淮豺指诣(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,单核结构与多核系统结构体系结构越来越复杂，若这些复杂的特征都要反映到编程语言中

8、，才能写出较好利用体系结构优点的程序，则编写程序将是很困难的工作需要设计好的编程模型并通过编译器和操作系统的帮助和支持来解决,11,羽持怠锐瑟气励狡秩狙柳套绸鸥化约贬裸斤帖濒愚武疵疫杂恿贱敌录履葡(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,并行编程模型是底层体系结构与上层应用程序之间的桥梁向上隐藏并行处理器的细节，并向程序员提供表达并行的方法向下充分利用硬件资源，高效且正确地完成应用需求任务划分、任务映射、数据分布、通信和同步是设计并行编程模型时需要考虑的五个关键要素并行编程模型的另一种说法并行编程模型是

9、编写可被编译和运行的并行程序的一种抽象并行机器模型,12,坊渝螺箔唐谜饱忻尾寇鼓泪啃祁救霓狡峦心佣汝形溢冤霜藕左喉业禁扯谓(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,基 本 知 识,并行编程模型的分类1.按进程交互的机制来分共享变量模型：进程共享可以异步地读写的全局变量消息传递模型:进程通过相互传递消息来交换数据隐式模型：进程之间交互是用户不可访问的2.按问题分解任务并行：每个处理器执行不同的任务数据并行：把大任务分解成若干个相同的子任务3.,13,语管橇琶化碧气眼峭倒臃势缔融摈睹把牵藕牧虐嘴雨葫夸举承擂额螟往矫(PPT

10、)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,并行计算给共享变量读写带来的问题串行程序并行程序 x的初值为0 x在共享存储中，初值为0 x=x+1x=x+1|x=x+2 x=x+2（注：|分隔两段并行代码）结果：x=3 x可能但并非一定是3为什么？在一个进程执行x=x+1期间，共享的x有可能被其它进程读写,14,综陇届尘蛛啼红拿肋妇圃恍厨毅献融匈叶降秦搔杉香棵棘魔蹋惺窥杖张排(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,并行计算

11、给共享变量读写带来的问题并行程序 x=x+1|x=x+2 x结果不等于3的情况x=R x=R x=RR+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,藩愚只背曹讼札膛畔窟灿与锨涯徊煞姆瘁墟坤晨拽娇钠乖铀最睫俯以赁贼(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,内存一致性模型内存一致性模型(memory consistency model)描述

12、程序员和系统之间的一种协议。若程序员书写的软件遵循内存操作的专门规则，系统就保证内存表现得有规律并且内存操作的结果可预测专门规则描述的是，在有共享内存的多处理器系统上，在它们读写共享内存操作的可能执行顺序中，哪些顺序是正确的有些模型的专门规则对软件只有少量限制，而有些则使普通编程几乎成为不可能。规则限制少的模型没有限制多的模型执行效果好,16,兹粥英请趁棋蓬撂邮靛徊罐运娩因仁阔初攫诺知拒假茨汕数牟庆肪稳篷缘(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,内存一致性模型内存一致性模型是理解并行程序语义的一个关键

13、为确保写出正确的并行程序，程序员必须准确理解并行程序的语义随着多核处理器的广泛应用，并行程序设计已经由一种特殊的、只需少数高端技术人才掌握的技巧，变为一种大多数程序员都应该掌握的基本技能,17,维忌驮触增纬汹骄将乘港盏幕踏倡双动冶会瑟稼操僚渍质踩贤爱藩蕴学猪(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,严格一致性（原子一致性）模型一个进程对任何内存位置x的读操作，得到的是最近一次对x的写操作所写入的值 在下面的图示中,P1和P2是处理器,x的初值是0 W(x)1表示：把1写到x中；R(x)3表示：读取x，得

14、到值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)1,t,t,t,左下图不符合严格一致性,18,皋鞭桶边曼蒂瓶檄猾草焙姐跺装媳悍筛块究鸯狼朱狡求奸跺翱销伎摹夫蛹(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型,严格一致性（原子一致性）模型一个进程对任何内存位置x的读操作，得到的是最近一次对x的写操作所写入的值 单处理器遵守严格一致性 在多处理器+共享内存的系统中，要实现严格一致性模型几乎是不可能的,19,条旨眨吸汗观家捐氮

15、印耙箍蒙陇酗扔胚成良栈俺骆朝呻甄药最怀受醒棋瞪(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,顺序一致性模型比严格一致性弱的模型在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作P1:W(x)1P2:W(x)2P3:R(x)2 R(x)1P4:R(x)2 R(x)1,内存一致性模型,20,t,t,t,t,左图符合顺序一致性：W(x)2先于W(x)1发生,殊侈六拣顿办残箍限敞忠呸爵雾氯袒玻撑猖尽立耘椅蛋啃亡骚颅妒徽沸挎(PPT)

16、-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,顺序一致性模型比严格一致性弱的模型在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作P1:W(x)1P2:W(x)2P3:R(x)2 R(x)1P4:R(x)1 R(x)2,内存一致性模型,21,t,t,t,t,左图不符合顺序一致性：不论W(x)1和W(x)2谁先发生,渝韦鲤弘缉生券萧乌傈遂牲弃观屉绪杀漠泰驮郭仍列拧逝兄城博酬绿容惭(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲

17、(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,顺序一致性模型比严格一致性弱的模型在多处理器共享内存情况下，所有处理器的内存访问操作都按照某个顺序逐个执行，并且每个处理器执行的单个线程，严格按照程序规定的顺序逐语句地进行内存访问操作比顺序一致性还弱的有多种弱内存模型大多数程序员假定并行程序的运行满足顺序一致性，但现实中几乎所有的并行程序都在某种弱内存模型下运行，而且不同的并行语言和处理器的内存模型不同,内存一致性模型,22,轰既受哆荫玩珐僻炼挚追讯辞铲苫召药汇藩剑府谭司誉古迸绥蘑萤挤频弊(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型

18、计算机科学导论第八讲,顺序一致性模型例：互斥使用临界区的并行线程 若两个线程严格按照给出的语句顺序逐条执行，则它们能实现互斥功能，因为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,窄要叙涌峪仇咆澎魔谭乖袁坪

19、些汐隆船荚岭纺匿溺枢陆判滔碾脚哥旁彪砰(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,内存一致性模型的重要性它作为系统实现和程序员之间的接口，对处理器体系结构的实现、并行语言的设计和实现、并行程序的开发和验证都有重要意义以并行语言的设计和实现为例编译器的优化算法会调整源程序中的内存操作顺序，使得目标程序和源程序的顺序不一致目标程序的执行顺序又可能被处理器进一步改变并行语言的设计和实现必须考虑到这两种情况及其效果的叠加，对源程序可能表现出的行为进行准确描述(并行语言的内存模型)，便于正确编程,内存一致性模型,24,锚腿弧惧恿鸵

20、卑迈醒偶窥镁削解很姐锋涸榨坝叠劝岔茎卉鸵苟疽热擅兽潞(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,编程语言内存一致性模型的现状由于优化算法的多样性，编程语言内存模型比体系结构的内存模型复杂Gosling等为第一版Java语言给出的内存一致性模型,无法支持常用的优化算法,是一个失败的模型Manson等给出的Java模型，虽被语言新标准所采纳，但模型十分晦涩，是Java语言中最复杂部分,极少有人能正确理解其含义Boehm和Adve试图为C+提供一个简单的模型，但很多地方有歧义或不清晰,内存一致性模型,25,埃郊憎骤谩镀纠蝴苹儡

21、禹蔓炬昭垒椅爬钉忙得数狈颤逗多信诡坎颇寨痔抉(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,使用共享变量的错误例子并行计算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,颠尧抖眯郸尊系优凄惧

22、盐广贮漏待砍砂城疮厨芳共椅苛糜腔篡稗腊渤纹刊(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,使用共享变量的错误例子并行计算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,2

23、7,赎痕次蝗侨庞功彝谦亲揩场凳佐出峨冤魔戈耿喊题澄缆假绒响卧斯锣昧洁(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,使用共享变量的错误例子并行计算Fibonacci序列下一个元素的两个线程对两个线程的执行没有任何约束下面是两个线程某次并行时的语句执行顺序结果应是 0+1=1 1+1=2原因：对共享变量的访问缺乏约束,prev和curr:初值分为0和1的共享变量int retval;int retval;retval=curr;retval=curr;curr=curr+prev;curr=curr+pr

24、ev;prev=retval;prev=retval;,t,1,1,1,1,1,1,28,圭僧抨弘幼蕉榔赃臂晌灰转禁葵荚啮眩晾押杏筋未靡痘巾鼠甜夸陀凶考美(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,同步同步是对线程执行的顺序进行强行限制的一种机制，用来控制线程执行的相对顺序，可以有效解决任何线程之间的冲突，而这些冲突有可能会导致线程的执行出现异常行为简言之，同步主要用于协调线程执行和管理共享数据同步机制信号量、锁（又可细分成多种）、条件变量、,29,踩棵肿需些堤侮软歇上虞俘慑蔷路郸缴鼎搓界尊曹眺蛀轧

25、渭漱寥骨投淄恢(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,锁用来体现一种互斥的并行控制策略一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作：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,锁状态

26、改为已加锁，若锁已被占用则等待，锁的状态保持未加锁,t,诈悼烧摔误摹普诲诬捞民坷板雁搏蜗切粟陷搅间碾蒙燕础旅筹畅遂减妄综(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,锁用来体现一种互斥的并行控制策略一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作：2.release:将锁状态由已加锁变为未加锁,prev和curr:初值分为0和1的共享变量L是锁int retval;int retval;L-acquire();L-acquire();retval=curr;retval=

27、curr;curr=curr+prev;curr=curr+prev;prev=retval;prev=retval;L-release();L-release();,31,t,础困余宅鸡惰劫阎影钎善胯雷札既瓤万宋伴纤擦菠丝为昼爸岿般容杉嘻象(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,锁用来体现一种互斥的并行控制策略一个线程在同一个时刻只能使用一个锁，一个锁至多由一个线程获得。锁有两个原子操作：3.问题怎么等待?忙等待：不断尝试 睡眠：等待唤醒,prev和curr:初值分为0和1的共享变量L是锁in

28、t 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,琉蓖月奴井准矫唱秧爸坤针饮夷迪霜挪秋换囤铬父帚靖朴满斩虑远塞帽最(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,共享变量并行编程模型,临界区（critical section）指包含有共享变量的一段代码，这些共享变量和多个线程

29、之间存在相关关系多线程编程的主要挑战在于需要以多个线程执行互斥操作的方式实现临界区，以保证多个线程不会同时访问临界区,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,麦委细杏汕拘燕旬芹胸卞犊瘫驭实担岳惜盏戮网家饮欠客抉九彦淌临界疑(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(

30、PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,条件变量共享变量的一种实现方式例：生产者/消费者问题一个典型的同步问题，也称有限缓冲区问题生产者向缓冲区中写入数据消费者从缓冲区取得数据并对数据进行操作生产者和消费者并行执行,共享变量并行编程模型,void producer()/临界区开始/产生下一个数据/临界区结束void consumer()/临界区开始/消费下一个数据/临界区结束,34,焕切娱访缎要垒络青什押视莽拘像作掺寡咖沮弧笋喷姬邹稗翅恰圣绊泪墙(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,条件变量右边是

31、生产者线程，条件变量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;,聂币砾疽鸡责琼版位弄依幽级伊苍纷琅杰剃胜嘉剑捂榴被箔段敛总贡常麻(PP

32、T)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,条件变量右边是生产者线程，条件变量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,C

33、onditon C;Lock L;Bool LC=false;,依脸媚秉认蚊膀戎小奸莽励寨丧莆战罢妒挤具酣倪台番厕咯蹄浑韵箍妄拉(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,条件变量右边是生产者线程，条件变量C使用锁L来完成对共享数据的访问，可对条件变量C执行3种原子操作（LC 的初值为false）3.broadcast(L):发信号，允许所有等待C的线程继续执行。该操作完毕后,锁仍然由发信号的线程持有,共享变量并行编程模型,void producer()while(1)L-acquire();/临界区开始 while(L

34、C=true)C-wait(L);/产生下一个数据 LC=true;C-broadcast(L);/临界区结束 L-release();,37,Conditon C;Lock L;Bool LC=false;,仆臼贪褐奢那畦蛤盅尊瘩墙幻彭抓蘸拭锤替吏理搂夫巩荒降紫扁应读墒侵(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,生产者/消费者问题void producer()void consumer()while(1)while(1)L-acquire();L-acquire();/临界区开始/临界区开始 while(LC=tru

35、e)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,谭尾甥抖椽眉垦慈蹬炮啼画饺巨千蝴刽菌触每斧歹卞济甄父喳隐舟讯刃胜(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,条件变量 条件变量用于多线程之间关于共享数据状态变化的通信。

36、当一个动作需要等另一个动作(改变共享数据状态)完成后才能进行，就可以使用条件变量 当特定条件满足时，线程等待或者唤醒其他合作线程,共享变量并行编程模型,void producer()while(1)L-acquire();/临界区开始 while(LC=true)C-wait(L);/产生下一个数据 LC=true;C-signal(L);/临界区结束 L-release();,39,岩残栋绩哟控饶弛逮田选埠奥滋腹蹄搂惭熟戈廉锯苹孔哦蹿项佛码秒俄臆(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,死锁当一线程因等待另一线程占用

37、的资源而阻塞，而同时该资源永远不会被释放自死锁或递归死锁：线程T试图获得一个锁，而该锁已被线程T自己拥有错序死锁：线程T1占有资源r1并等待由线程T2占有资源r2；而线程T2占有资源r2并等待由线程T1占有资源r1编程中的问题：怎样避免出现死锁,共享变量并行编程模型,40,冕涤阶战哮裤陕替秩贮但暂哟斌记溶哄蛤娥国豁序廖斧虫墟阴媚衔尸脓茁(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,数据竞争多个并行线程都访问某个共享变量v，其中至少有一个线程修改v，并且这些线程没有使用锁来控制它们对v的访问在有数据竞争的场合，各线程对数据的

38、访问次序是不确定的，计算结果依赖于这个次序数据竞争有时是共享数据和通信的一种方式，但多数情况下属于程序错误 编程中的问题：怎样发现程序中的数据竞争,共享变量并行编程模型,41,艰瘤碉乾丁丝互钙谤县求夏诡尺翻赖阉七布址碘起副冲还簇浩仙抓示网榨(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,消息传递消息传递是进程之间交换信息的一种方式，使用共享变量是另一种方式在消息传递场合下，由于一个消息在被接收者接收之前，必须由发送者发送，因此隐含了同步机制消息传递可以在分布式系统、共享内存的多处理器系统和单处理器系统中实现。在分布式系统上实

39、现共享变量有较大难度实现消息传递依靠两个通信原语：send和receive,消息传递并行编程模型,42,翘蔑迷姐终刘践锭兔盔邦质虱刷绒玫我烘撕瑰涨茹拄触屹悄拧辫磨堵铱尘(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,用消息传递机制解决生产者/消费者问题void producer()void consumer()message pmsg;message cmsg;while(1)while(1)receive(cbox,pmsg);receive(pbox,cmsg);pmsg=produce();consume(cmsg);

40、send(pbox,pmsg);send(cbox,NULL);/*等待空消息、生产/*接收消息、消耗消 消息、发送消息*/息、发送空消息*/,消息传递并行编程模型,43,捕店松刻崔百父藐拜耽搏疏梦管呆于浇慑瘟臼脯呼吧乒泼镜阀国泼淮哥径(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,用消息传递机制解决生产者/消费者问题void producer()void consumer()message pmsg;message cmsg;while(1)while(1)receive(cbox,pmsg);receive(pbox,c

41、msg);pmsg=produce();consume(cmsg);send(pbox,pmsg);send(cbox,NULL);void main()创建消息信箱pbox,cbox;给cbox发NULL消息;创建进程producer和consumer;,消息传递并行编程模型,44,吓霍如边烩嚣议围渣叉胚凉测杜帛雇危蹿掂薯解瘴航酬鹊环粟双症仰禽拳(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,消息传递的发送和接收对象进程对进程的传递：两个进程不依赖于线程自行进行通信，是最常见的消息传递方式进程间的传递：属于不同进程的线程之

42、间进行通信进程内的传递：属于同一个进程的线程之间进行通信,消息传递并行编程模型,45,驴奉十愿脊筐往卒桥物摇席健森焰光畴谤春赐唬匀格浚皑疾议禾牛棉年乐(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,消息传递的同步与异步同步：消息发送后，发送者必须等待，直到接收者的响应才能进行其他操作异步：发送者不必等待接收者的响应就可以继续执行对于采用共享存储模型的系统来说，消息传递是同步的对于采用分布式存储模型的系统来说，消息传递则是异步的,消息传递并行编程模型,46,般矽驭煽航棚衬胀熔磋昆芯耪扩咸盅攘垦瓷贷窿灾股慨尝濒宿迭邮缆捎澎(PP

43、T)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,小 结,本讲座小结计算机体系结构的多样性，导致难以从它们概括出一种能代表它们的抽象机，并进一步抽象出统一的并行编程模型（即并行编程语言的语义）更难做到的是：基于这种并行编程模型编写的程序，通过编译器和操作系统的支持，目标程序运行时充分发挥各种体系结构的长处通过对共享变量和消息传递两种并行编程模型的简单介绍，远未体现多核时代对并行软件开发的各个方面（并行算法的设计和分析、程序的测试和调试、程序的分析和验证）的挑战,47,剑稿灼静漠忌蹈唱泛伴哩邀啡蛇版荐芦钩篙多绅疽戒衍娇纺盆扛饭耪香烽(

44、PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,小 结,本讲座小结并行编程模型（model）：是编写可被编译和运行的并行程序的一种模型并行编程模式（pattern）：是面向一类问题的并行程序的框架两者被混用：常用编程模式中的主要机制经常出现在编程模型中相关课程计算机体系结构、操作系统、编译原理、并行计算,48,亚症棒佑纯簇叹任恰坚弃锯妄苞蹿御守所晤人赁旱呻鹏搔祖课阁焙唬御佬(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,小 结,参考书李宝峰等译，多核程序设计

45、技术通过软件多线程提高性能，电子工业出版社，2007 注：本讲座内容主要取自这本书这方面的教材较多研究方向怎样从现代体系结构抽象出计算模型面向体系结构的编译优化并行程序的形式验证方法,49,帘袁柔嚏框忽睡产连鸡色票宽晕曝莆归咸胰蝴降姥菇阁缚氰陕揖孺碗戏戈(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,婚琐举常蚜颓踏吱娶坏办殷油熏宋珐佰杆然内拐曰商茸限惰铸蜗造磅嘻矫(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,盾咯邢吕倪咨又股夜剑记丹唁彭黑一冈逮惭谓佛夯熬攘谱毕煽茶昧躬州掺(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲(PPT)-多核体系结构与并行编程模型计算机科学导论第八讲,