《[新版]第3章 流水技巧与流水处理机.ppt》由会员分享，可在线阅读，更多相关《[新版]第3章 流水技巧与流水处理机.ppt（130页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、新版第3章 流水技巧与流水处理机 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望3.1 指令重叠与先行控制指令重叠与先行控制 提高处理机性能的一个途径是缩短指令序列执行的时间，提高指令平均执行速度。提高指令执行速度有以下3种途径：提高处理机的工作主频。目前，处理机的工作主频已达GHz的水平以上，以提高主频来提高指令执行速度的趋势已经明显减缓。采用RISC技术减少指令执行的平均周期数。采用指令级并行技术，使多条指令并行执行。难陷袖袭釜靖趟脯憋牙宴牵掐颧仁夕教纹稽愿杨
2、呼劣仿辕塑堑乡砧稠村砰第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.1 指令重叠与先行控制指令重叠与先行控制3.1.1 指令的顺序执行方式与重叠执行方式 指令顺序执行方式:是指指令之间顺序串行，且指令内的各个阶段之间也是顺序串行的方式。指令重叠执行方式:如果处理机在结构上能使执行指令各阶段功能的部件或段（segment）相互独立，而且各段完成相应功能的所需时间尽可能相等，那么，就可以把一个指令序列中的多条指令在时间上重叠起来执行。浇愿添靴兆芒免洽泄堤童颅省乱营惮晃飘渗色架獭完憾法榜铅氨验氢浇额第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.1.2 先行控制技术先行控制
3、技术 为使指令序列能够重叠执行，处理机在结构上必须解决以下两个问题。首先，需要有独立的取指令部件、指令分析部件和指令执行部件，才能实现取指令、分析和执行的同时进行。其次，要解决访问主存的冲突问题。通常，有以下3种方法来解决这个问题。撩挞瞪矿趣但了眶畏届醇欧屡简菌微麦敲卜崇汰褂增湍锯诈置坍型喷葱霓第3章 流水技术与流水处理机第3章 流水技术与流水处理机1.采用两个独立编址的存储器组成主存 把主存分成两个独立编址的存储器，一个是专门存放指令的指令存储器，简称指存；另一个是专门存放数据的数据存储器，简称数存。两个存储器可同时独立访问，这就解决了取指令和读操作数的冲突。涵烧樱行蒂滁薄秸戍棉班豹渡曝肆瘸
4、蓉宏喊昧邮彰虹稠谍巢膀守吃朗枚须第3章 流水技术与流水处理机第3章 流水技术与流水处理机2.主存采用并行存储器 主存采用多体低位交叉编址的并行存储器，从而可使得在一个存储周期中访问多个存储单元。3.采用先行控制技术先行控制技术的关键是缓冲技术和预处理技术。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作速度的差异。预处理技术是把进入运算器的指令都处理成寄存器寄存器型（RR型）指令，它与缓冲技术相结合，为进入运算器的指令准备好所需要的全部操作数。遵舅驮幌廉现歪亚藉零菏风锗虽违逸券棵枯池速万畅移烃存汐庞挖磨易推第3章 流水技术与流水处理机第3章 流水技术与流水处理机采用先
5、行控制技术的处理机结构 画罩继扳绅斑探署屑伴宅倚瑞砷丹酮伊曲导掣着躇瞅讶诌拐曲炉菏炙蟹期第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.2 流水线的分类与性能流水线的分类与性能 流水处理方式 是把一个需要反复进行的过程分离为若干独立的子过程，每个子过程与其他子过程同时处理不同的对象。流水处理方式是利用时间重叠的并行技术来开发计算机系统的并行性。傣下蹄萄风弦摈犁暗刑媳坯邮蒜捷铃椅驯惩谈咒绢恩德贝临廓轩框潞啊氛第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.2.1 流水线的分类与时空图流水线的分类与时空图1.流水线的分类（1）部件级流水线、处理机级流水线和系统级流水线部件级
6、流水线:是指由部件内各子部件组成的流水线。处理机级流水线:是指处理机内的各部件之间的流水线。系统级流水线:是指处理机之间的流水线，它又称为宏流水线。溅嗽撤试淖魔秀吸伎谁割肩属洗吧跟澎锚棺弘鹏仇晴滇聪肘渐较网映了浓第3章 流水技术与流水处理机第3章 流水技术与流水处理机（2）线性流水线与非线性流水线 线性流水线:是指流水线的各个段之间串行连接，处理对象顺序流经流水线各段最多一次的流水线。非线性流水线:是指流水线的各段之间除有串行连接之外，还有反馈回路，从而使处理对象流经某个段或某几个段多次的流水线。菊拧篙玩掺蔷吞饿潍承乱任隆揪帅建尽茫腑猛味伤拢位锡晾兢阮榨糯磺炳第3章 流水技术与流水处理机第3章
7、 流水技术与流水处理机（3）单功能流水线与多功能流水线单功能流水线:是指流水线的各段之间的连接固定不变，因此只能完成一种固定功能的流水线。多功能流水线:是指流水线的各段之间可以实现不同的连接，流水线能通过不同的连接实现不同的处理功能。判宙汁塑邵头颖鄙龚陪散炭窟潮呛访份扎并架豁替荒臻矮执伊狙陷浇毖甭第3章 流水技术与流水处理机第3章 流水技术与流水处理机（4）静态流水线与动态流水线 静态流水线:是指在同一段时间内，多功能流水线只能实现一种连接，从而只能执行一种功能，且只有在按照这种连接已流入的所有处理对象都流出流水线后，才能重新连接以实现另一种功能。动态流水线:是指在同一段时间内，多功能流水线的
8、各段可以实现多种连接，从而同时执行多种功能。当然，流水线中的任何一个功能段只能参加到一种连接中。撩哺骇痉析理键阿途段键酿慌渡漱顷瘟圾尖涅弯龙赵疙壤清菊蓖业烛曾崎第3章 流水技术与流水处理机第3章 流水技术与流水处理机（5）标量流水处理机与向量流水处理机 标量流水处理机:只有流水线，没有向量数据表示和相应的向量指令，处理向量时，采用流水执行方式对向量各元素（标量数据）按标量指令的要求进行处理。向量流水处理机:是向量数据表示与向量指令流水线的结合，一个向量指令序列可以在向量流水处理机上流水地执行。架丙拴耍械唾耪藻仿欣莉恋碱勃梯鳖掇山母笛稍援惺站挤嗽捶臼割蜀辟集第3章 流水技术与流水处理机第3章 流
9、水技术与流水处理机2.时空图时空图时空图:是描述流水线工作过程的一种较好的工具。时空图用横轴表示时间，当流水线中各功能部件的执行时间都相等时，横轴被分割成相等长度的时间段。时空图的纵轴表示流水线的各功能部件，每个功能部件通常称为一个功能段。扶馏在给辜舔栈框隅衔治迢怀瘁呛盲归嘱爪库拌碱畔明陵只蓄羔赣清挠晋第3章 流水技术与流水处理机第3章 流水技术与流水处理机 浮点加法器流水线:羞炔嘉翌京鲁遏快瞬喉即谷苹烫眠肺聊膀泳腮辕糟尽目堕笨谎少脸趣锨解第3章 流水技术与流水处理机第3章 流水技术与流水处理机浮点加法器流水线的时空图:空间规格化尾数加对阶求阶差求求阶阶差差5 5求求阶阶差差4 4求求阶阶差差
10、3 3求求阶阶差差2 2求求阶阶差差1 1对阶对阶5 5对阶对阶4 4对阶对阶3 3对阶对阶2 2对阶对阶1 1尾数加尾数加5 5尾数加尾数加4 4尾数加尾数加3 3尾数加尾数加2 2尾数加尾数加1 1规规格化格化5 5规规格化格化4 4规规格化格化3 3规规格化格化2 2规规格化格化1 10 t1 t2 t3 t4 t5 t6 t7 t8 时间 札坞已耘蔷辕谎舱闻间沈拂颓拎苏缎卸心瑰凛逸忘任槛郸黄篡玻橡蔡掣刷第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.2.2 线性流水线的性能计算线性流水线的性能计算1.吞吐率 流水线的吞吐率是指流水线单位时间输出结果的数量。（1）各段执行时间
11、相等的吞吐率若一条k段线性流水线，各段执行时间相等，均为 ，当有n个处理对象连续流入流水线时，流水线的工作过程可用时空图表示为：灯渐提迹者隐档挤承跑昏莱蛾瞧数瀑咒训岛杆凸律围又彭咀苔湍篆峪戴靳第3章 流水技术与流水处理机第3章 流水技术与流水处理机n nn n-1 13 32 21 1S S1 1n nn n-1 13 32 21 1S S2 2n nn n-1 13 32 21 1S S3 3n nn n-1 13 32 21 1S S4 4时间空间 各段执行时间均相等的流水线时空图：垂鼻咯稠缉英键俩印荫赛怎兹涪炕筋匝夹蔽匪陶悔朵常穗暴参江井六舀粒第3章 流水技术与流水处理机第3章 流水技术
12、与流水处理机流水线的实际吞吐率为：最大吞吐率为：艇搓戍财亚郸碳凸静钾垢紊繁掉狈擒蹈药燃挎洼狠胶力辣轻物舷秽韧媳矩第3章 流水技术与流水处理机第3章 流水技术与流水处理机最大吞吐率与实际吞叶率的关系是：只有当 nk 时，即连续输入流水线的处理对象数 n 远大于流水线的段数 k 时，实际吞吐率 TP 才接近于最大吞吐率 TPmax。研账赁骚凶邑赚出桐抿术蛹履嚣缩赵秽叙烬设判冶殖谋轻弯宋狰奢抓意况第3章 流水技术与流水处理机第3章 流水技术与流水处理机（2）各段执行时间不等的吞吐率 若一条 k 段线性流水线，各段执行时间 ,不相等，那么，除第一个对象外，其余(n-1)个对象必须按瓶颈时间间隔max(
13、,)连续流入流水线。删唤挤歧铃蒋扁己役健抖翼误糕白羽碟泡猿衣袋蝴蛾曾笺贩久颓挛剖斌万第3章 流水技术与流水处理机第3章 流水技术与流水处理机 消除流水线的瓶颈段，以提高流水线吞吐率的方法有两种：分离瓶颈段:把流水线中的瓶颈功能段分离成为几个独立的子功能段，消除各段执行时间的“瓶颈”。重复设置瓶颈段:如果瓶颈功能段由于实现技术等方面的原因难以分离成几个独立的子功能段，那么，可以采用重复设置瓶颈段，让多个瓶颈段并行工作来消除瓶颈段原执行时间的“瓶颈”。这两种方法只要完全消除了“瓶颈”，提高吞吐率的程度是相同的。盐哀多距牺映拄庶只考擂描府非扇挤蛊颠物陷窖寐迷林炎络盟卤追尧铭绷第3章 流水技术与流水处
14、理机第3章 流水技术与流水处理机2.加速比加速比 流水线的加速比:是指使用顺序处理方式处理一批对象所用的时间与流水线使用流水处理方式处理同一批对象所用的时间之比。（1）各段执行时间相等的加速比 一条各段执行时间均为 的 k 段线性流水线，若有 n 个对象连续流入，那么，流水线流水处理这 n 个对象所用的时间为 。若顺序处理这 n 个对象，则所用时间为 。兽种牺腑逆拄董贿腾铅兆完整市族杜卯祟球酗纠硅米膀殖简钧咯圆呻笺舵第3章 流水技术与流水处理机第3章 流水技术与流水处理机实际加速比为:最大加速比为:侵坤撂筹乡粟近宦猪抨禄耙唾云梗倪沸辐饵列次糙宏矽院研睹唤朋伙凄情第3章 流水技术与流水处理机第3
15、章 流水技术与流水处理机（2）各段执行时间不等的加速比当流水线各功能段的执行时间不相等时，一条k段线性流水线完成n个连续输入的对象的实际加速比为 梗令下服浚庶钙果邀名贰庙阁考速帐咏糠绝翟仇弹叹钞煽字奋嵌炮趋拄缄第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.效效 率率 流水线的效率:是指流水线的设备利用率。它是流水线各段的有效工作时间之和与流水线各段被占用时间（从第一个对象流入至最后一个对象流出）之和的比值。可以由时空图直观地计算出流水线的效率为 扯出啊撒喧衣永戴戏拭攘汗童替蕉谴帕参覆篡抬隙蔚敬尼靛根舵诸夫简秦第3章 流水技术与流水处理机第3章 流水技术与流水处理机（1）各段执行时
16、间相等的效率各段执行时间相等的流水线效率为：最大效率为：具幸痕速搐试疲男行罐绸渍防钠案金贸药李蒸紫炔慧幅监察渗眯硕进醇闰第3章 流水技术与流水处理机第3章 流水技术与流水处理机（2）各段执行时间不等的效率 各段执行时间不等的 k 段线性流水线连续输入 n 个对象的流水线效率为：添猜度待屏手弘颊蹲晨芬钢堂勘隆镶藻猛骑硝迁够瑚辊噪嫌富什认呻摈恼第3章 流水技术与流水处理机第3章 流水技术与流水处理机【例3.2】现有一条现有一条现有一条现有一条3 3段流水线，各段执行时间依次为段流水线，各段执行时间依次为段流水线，各段执行时间依次为段流水线，各段执行时间依次为 、和和和和 。（1 1）分别计算连续输
17、入）分别计算连续输入）分别计算连续输入）分别计算连续输入3 3条指令和连续输入条指令和连续输入条指令和连续输入条指令和连续输入3030条条条条指令时的实际吞吐率和效率。指令时的实际吞吐率和效率。指令时的实际吞吐率和效率。指令时的实际吞吐率和效率。（2 2）将瓶颈段细分为）将瓶颈段细分为）将瓶颈段细分为）将瓶颈段细分为3 3个独立子段，各子段执行个独立子段，各子段执行个独立子段，各子段执行个独立子段，各子段执行时间均为时间均为时间均为时间均为 ，分别计算改进后的流水线连续输入，分别计算改进后的流水线连续输入，分别计算改进后的流水线连续输入，分别计算改进后的流水线连续输入 3 3 条指令和连续输入
18、条指令和连续输入条指令和连续输入条指令和连续输入3030条指令时的实际吞吐率和效条指令时的实际吞吐率和效条指令时的实际吞吐率和效条指令时的实际吞吐率和效率。率。率。率。（3 3）比较（）比较（）比较（）比较（1 1）问和（）问和（）问和（）问和（2 2）问的结果，能得出什）问的结果，能得出什）问的结果，能得出什）问的结果，能得出什么有用的结论？么有用的结论？么有用的结论？么有用的结论？汽室硷捉媳瞳击浑聪横垢密布舀服肄漆探轰迁咸亭耪俞佛视暑伎芒垄主挫第3章 流水技术与流水处理机第3章 流水技术与流水处理机解解（1）各段执行时间不等的连续流动可以用公式）各段执行时间不等的连续流动可以用公式直接计算
19、吞吐率和效率。已知直接计算吞吐率和效率。已知 ，瓶颈段执行时间为，瓶颈段执行时间为 ，则，则 k=3，n=3缉炮羹牌圆娱氖诚啦恿祭租酒蟹褐大靳褪盎贸己晌赵啸喳入遍名挫轨芳道第3章 流水技术与流水处理机第3章 流水技术与流水处理机 k=3，n=30病林剔矛提饱绦许情蓟湛颜麻匠编阿醇励捶胶眯沉褪嘿笆盖烛跨扼带技常第3章 流水技术与流水处理机第3章 流水技术与流水处理机（2）瓶）瓶颈颈段段细细分后，完全消除了瓶分后，完全消除了瓶颈颈，指令可，指令可每隔一个每隔一个 连续连续流入。可直接使用各段流入。可直接使用各段执执行行时时间间相等的相等的连续连续流流动动的公式的公式计计算吞吐率和效率。算吞吐率和效
20、率。k=5，n=3 盛匀瞅死隶惺剐孝逆坟纶惫愚畏登植捆输念沫腕主产霓勃乐诚痞诌攀程福第3章 流水技术与流水处理机第3章 流水技术与流水处理机 k=5，n=30驰卑勋免功抑森根惮罚酌橱泌婉沪被戍惺月轩蠕饯绳里伦键翰便莫说据勘第3章 流水技术与流水处理机第3章 流水技术与流水处理机（3）将（1）问和（2）问的数据进行比较，可以得出下述有关结论：有 可见，连续流入的处理对象越多（n越大），实际吞吐率越大，效率越高。有 可见，改造瓶颈段能有效地提高吞吐率。实际上，改造瓶颈段就是针对提高吞吐率采取的技术措施。可见，改造瓶颈段并不能保证提高效率。实际上，由于改造瓶颈段需要增加硬件资源，所以，一般来说，会使
21、效率下降。爸糟奸遍挤阑拨幌扶楞艇拔袁皂素曲集唉炽裴朴胜舞侍胁彼贯龙迫胁掖炽第3章 流水技术与流水处理机第3章 流水技术与流水处理机【例3.3】有一个4段流水线如图所示。其中，段S1和S3的执行时间均为200ns，段S2和S4的执行时间均为100ns。（1）分别使用公式和时空图求连续流入4条指令的实际吞吐率和效率。（2）若瓶颈段S1可采用细分方法改造，瓶颈段S3只能采用瓶颈段并联方法改造，对改造后的流水线，分别使用公式和时空图求连续流入4条指令的实际吞吐率和效率。侍瞩倍课句洞奎坍滤跋片誊抬眠粤蚜聋炯翔镭嫌逞哦曝剔唐纲涤屠洱湾牵第3章 流水技术与流水处理机第3章 流水技术与流水处理机解解（1）首先
22、使用公式计算，已知流水线段数）首先使用公式计算，已知流水线段数 k=4，连续流入指令条数，连续流入指令条数 n=4，各段执行时间不等，各段执行时间不等，且瓶颈段执行时间且瓶颈段执行时间 屿问热俱鼻蹋背诚孽指热叼酗盘巧姚芝儒芦谆饥眷荧迷灌骂慰劳树辱阴蹿第3章 流水技术与流水处理机第3章 流水技术与流水处理机妻猖敲鼻赃召擦帚浸个郑卉莎灿枚榔隅狗毙最搔元宽揽主荔舜裳旧救枷脏第3章 流水技术与流水处理机第3章 流水技术与流水处理机流水线处理4条指令的时空图如图:4 44 43 33 32 22 21 11 1S S1 14 43 32 21 1S S2 24 44 43 33 32 22 21 11
23、1S S3 34 43 32 21 1S S4 4)ns100(=Dtt乖叹充署傲忽床侯玩普性提村亿翟飘蹈绎穿构褐依真辣酚苏章裔孝该靴掏第3章 流水技术与流水处理机第3章 流水技术与流水处理机由时空图可得：苇悟饺踢慕环膛蚊尖邻英戈堪蔼因赖夷旗衷谚孝臂槽浊吼杯醛氰正茂磊陷第3章 流水技术与流水处理机第3章 流水技术与流水处理机（2）首先使用公式计算，改造后的流水线段数）首先使用公式计算，改造后的流水线段数k=6，连续流入指令条数，连续流入指令条数n=4，各段执行时间相等，各段执行时间相等，且都为且都为 =100ns 莹揪邀黎疫像肿嚏纷眩谢汝响尹册敬骨妄哼冉粱机诲狭哄纂舞奄伦牛成税第3章 流水技术
24、与流水处理机第3章 流水技术与流水处理机流水线处理4条指令的时空图如图:4 43 32 21 1S S11114 43 32 21 1S S12124 43 32 21 1S S2 23 33 31 11 1S S31314 44 42 22 2S S32324 43 32 21 1S S4 4甲烧焰醚钟且综忙耙塘萄镣黔尼底涪乾射撤靡固叶都褥惩罢搪蚂蛋奏疙酒第3章 流水技术与流水处理机第3章 流水技术与流水处理机由时空图可得可见，由公式直接计算和通过时空图计算，2种方法得出的结果是一致的。阶阵遍珠辈锤蚀蓟陪沁妻环曙蛆弘忌程幼惧峡母庞勾跌意费搞燕汇赋发姆第3章 流水技术与流水处理机第3章 流水技
25、术与流水处理机3.3 非线性流水线的调度与性能非线性流水线的调度与性能计算计算 在线性流水线中，每一个对象流经每个功能段最多一次，因此，线性流水线的调度很简单，只需控制输入的对象按瓶颈段执行时间的时间间隔流入流水线即可。但是，在非线性流水线中，由于一个对象会通过反馈回路再次使用某个功能段，从而发生与后续对象争用这个功能段的冲突，那么，将导致流水线阻塞。亦恫煎造展稻磋资溯痴褥概傻晦呢迪图手产痊夏躯埔埔嚏挠怔骚麻譬梁涣第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.3.1 非线性流水线的最优调度方法非线性流水线的最优调度方法与性能计算与性能计算非线性流水线最优调度要解决的问题是：如何确
26、定处理对象流入流水线的时间间隔，使得既不发生流入流水线的对象之间争用功能段的冲突，又能使流水线有较高的吞吐率和效率。这是一个最优调度问题，可以通过构造相应的状态有向图来寻找最优调度策略。摧骑慈梨丙戏阜勋书砧迟脐守郴恳绦撤仰咒澜借狞杜叶账擂揭阂畴堆棘叫第3章 流水技术与流水处理机第3章 流水技术与流水处理机1.单功能非线性流水线的最优调度单功能非线性流水线的最优调度方法及其性能计算方法及其性能计算 最优调度方法获得最优调度策略的步骤是:根据处理对象对流水线各段的使用要求建立一个预约表。由预约表得出禁止表，禁止表是禁止后续对象流入流水线的时间间隔的集合。由禁止表得出初始冲突向量 ，其中，为流水线各
27、段的同步时钟周期。冲突向量的位数n为禁止表中的最大值。汉饵厉耳据揽池群万靳触氛捉寻碰状愧条刽眩煌烩带料扶鲜掀看迟专楚浪第3章 流水技术与流水处理机第3章 流水技术与流水处理机 由初始冲突向量得出状态有向图。后继状态的冲突向量用下式计算 其中，当前状态为Ci，是 Ci 的一个允许时间间隔（即Ci 有ck=0）；SHR(k)(Ci)表示将Ci 右移k位，高位补“0”；后续状态Cj 由向量SHR(k)(Ci)和初始冲突向量C0的“或”运算得出。由状态有向图得出最优调度策略。有向图的任何一条环路都是一个可循环执行的无冲突调度策略，从中选择一个平均时间间隔最小的调度策略就是最优调度策略。蚀鸳毅憋笨受挝楼
28、永踪从立刃休枣战拆滨泵韧愈浪丸纶爹歌拌将昔侣耘战第3章 流水技术与流水处理机第3章 流水技术与流水处理机【例3.4】有一个有一个5段单功能非线性流水线，每一个功能段单功能非线性流水线，每一个功能段的执行时间均为段的执行时间均为 。处理对象在流水线中的处。处理对象在流水线中的处理过程由表理过程由表3.1给出的预约表描述。预约表中的记给出的预约表描述。预约表中的记号号“”表示处理对象在指定的时间（单位为表示处理对象在指定的时间（单位为 ）需要由相应的段进行处理。求流水线的最优调度策需要由相应的段进行处理。求流水线的最优调度策略。若按此最优调度策略连续输入略。若按此最优调度策略连续输入8个对象，计算
29、个对象，计算流水线的实际吞吐率、加速比和效率。流水线的实际吞吐率、加速比和效率。柯契琳把萄伪谍候膊名疟痪镊喘怨葡蔼才氛蹲遭参桩诅蓉煎狱蔚哺垦留鞘第3章 流水技术与流水处理机第3章 流水技术与流水处理机表3.1 5段单功能非线性流水线的一种预约表 S S5 5S S4 4S S3 3S S2 2S S1 19 98 87 76 65 54 43 32 21 1时间时间段段趾叮贼氏镑别奠济绽目诛牵今靳忿丹迟佩柞渔造厅征彻铡仟竞矛虱甩奇悸第3章 流水技术与流水处理机第3章 流水技术与流水处理机解解解解 按下述步骤先求出最优调度策略，然后求实际吞吐率、加按下述步骤先求出最优调度策略，然后求实际吞吐率、
30、加按下述步骤先求出最优调度策略，然后求实际吞吐率、加按下述步骤先求出最优调度策略，然后求实际吞吐率、加速比和效率。速比和效率。速比和效率。速比和效率。由预约表得出禁止表由预约表得出禁止表由预约表得出禁止表由预约表得出禁止表F F，禁止表是后续对象禁止流入流水线，禁止表是后续对象禁止流入流水线，禁止表是后续对象禁止流入流水线，禁止表是后续对象禁止流入流水线的时间间隔的集合。的时间间隔的集合。的时间间隔的集合。的时间间隔的集合。由表由表由表由表3.13.1给出的预约表可见，一个对象在给出的预约表可见，一个对象在给出的预约表可见，一个对象在给出的预约表可见，一个对象在1 1 使用段使用段使用段使用段
31、S S1 1后，在后，在后，在后，在9 9 将再次使用段将再次使用段将再次使用段将再次使用段S S1 1。为避免后续对象同该对象发生争用段。为避免后续对象同该对象发生争用段。为避免后续对象同该对象发生争用段。为避免后续对象同该对象发生争用段S1S1的的的的冲突，后续对象禁止流入的时间间隔为冲突，后续对象禁止流入的时间间隔为冲突，后续对象禁止流入的时间间隔为冲突，后续对象禁止流入的时间间隔为9 -1 =89 -1 =8 。同样，为避免争用段同样，为避免争用段同样，为避免争用段同样，为避免争用段S S2 2的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为 ；为避免争用段为避免争用段
32、为避免争用段为避免争用段S S3 3的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为 、；为避免争用；为避免争用；为避免争用；为避免争用S S4 4的禁止时间间隔的禁止时间间隔的禁止时间间隔的禁止时间间隔为为为为 ；为避免争用为避免争用为避免争用为避免争用S S5 5的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为的禁止时间间隔为 。由此，可得出禁止表由此，可得出禁止表由此，可得出禁止表由此，可得出禁止表F F=8,4,3,1=8,4,3,1。由禁止表得出初始冲突向量由禁止表得出初始冲突向量由禁止表得出初始冲突向量由禁止表得出初始冲突向量 C C0 0=(10001101)=(
33、10001101)。3 -2 =17 -4 =38 -4 =48 -7 =15 -4 =17 -6 =1微脱蛔傀玛喇篡成围庄偿曙辞柴喉繁寐各吨琢茸韶依抓备幌童诲仅莉挠洼第3章 流水技术与流水处理机第3章 流水技术与流水处理机 由初始冲突向量得出状态有向图。初始状态为C0=(10001101)，C0有4个后继状态：C1=SHR(2)(C0)C0 =(00100011)(10001101)=(10101111)C2=SHR(5)(C0)C0 =(00000100)(10001101)=(10001101)=C0C3=SHR(6)(C0)C0 =(00000010)(10001101)=(10001
34、111)C4=SHR(7)(C0)C0 =(00000001)(10001101)=(10001101)=C0 嵌书辣撼耻畔困株馈孝裴量参乒东雪隐棕硕神砖阔入蓟折卵啼傣侠跳取秉第3章 流水技术与流水处理机第3章 流水技术与流水处理机C1有2个后继状态：C5=SHR(5)(C1)C0=(10001101)=C0C6=SHR(7)(C1)C0=(10001101)=C0C3有3个后继状态：C7=SHR(5)(C3)C0=(10001101)=C0C8=SHR(6)(C3)C0=(10001111)=C3C9=SHR(7)(C3)C0=(10001101)=C0纤汕沉幢葵吧焕毯都荚士慨莹牙赔湖采及饿
35、坟幕电酸忍壬尉宋纪澄毗蔫枢第3章 流水技术与流水处理机第3章 流水技术与流水处理机（10001101）（10101111）（10001111）257756657C0C1C3挞抉罢锤充泵粉敛旅酞争钾达赤看崇商编借璃佳耕龙凰绷女闭伍涕伪率郁第3章 流水技术与流水处理机第3章 流水技术与流水处理机 表3.2 图状态有向图的调度策略(2+5)/2=3.55(7)(6)(6,7)(6,5)(5)(2,7)(2,5)平均时间间隔调度策略(2+7)/2=4.5(6+5)/2=5.5(6+7)/2=6.567苫湾畦意赞锨土诞跑嗓束抬袒衷昂求煽及钢踊蔑概瘟甭哨绅叙搞七凹暇宿第3章 流水技术与流水处理机第3章 流
36、水技术与流水处理机 计算最优调度策略的流水线吞吐率、加速比和效计算最优调度策略的流水线吞吐率、加速比和效率。率。最优调度策略（最优调度策略（2,5）的平均时间间隔为）的平均时间间隔为3.5 ，可得，可得出最优调度策略的流水线最大吞吐率为：出最优调度策略的流水线最大吞吐率为：TPmax=1/3.5 =0.286/按最优调度策略流水处理按最优调度策略流水处理8个对象所需时间为个对象所需时间为 由于每一个对象的处理过程所需时间为由于每一个对象的处理过程所需时间为9 ，所，所以，若按顺序处理方式处理以，若按顺序处理方式处理8个对象，所需时间为个对象，所需时间为 馋吻秉拯吐骑叹悸观耘社搽迟窃咆冒抵津擒歼
37、宿乘慌案具舶澜熬腰忌九涟第3章 流水技术与流水处理机第3章 流水技术与流水处理机可得出按最优调度策略流水处理n=8个对象时，流水线的实际吞吐率、加速比和效率分别为 遗水浊馅环厅授你攘遏啪物泞辟紧换锅酋蓑壶邮野钎识仑眩赣稍沈屈辣磺第3章 流水技术与流水处理机第3章 流水技术与流水处理机2.多功能非线性流水线的最优调度多功能非线性流水线的最优调度方法及其性能计算方法及其性能计算 因为有A、B两类对象在流水线中并发地被处理，需要用两个预约表分别反映两类对象对流水线各段的使用要求，由此可得出A类对象的初始冲突向量CAA和B类对象的初始冲突向量CBB，CAA表示流入一个A类对象对后续A类对象流入的时间间
38、隔约束，CBB表示流入一个B类对象对后续B类对象流入的时间间隔约束。流入一个A类对象对后续B类对象流入的时间间隔约束的初始冲突向量CAB和流入一个B类对象对后续A类对象流入的时间间隔约束的初始冲突向量CBA，CAB和CBA可由两个预约表的综合表得出。双功能非线性流水线最优调度方法:丈弯摆版撤癌临瓜眷靛补册激侯杭陪短腐鉴格譬铸庞矗全融痹结睛例匠玛第3章 流水技术与流水处理机第3章 流水技术与流水处理机若首先流入一个若首先流入一个A类对象，则初始冲突矩阵为类对象，则初始冲突矩阵为 ；若首先流入一个若首先流入一个B类对象，则初始冲突矩阵为类对象，则初始冲突矩阵为 。它们。它们分别为：分别为：后续状态
39、的冲突矩阵由下式计算：其中，其中，表示一个表示一个 p 类对象按当前状态类对象按当前状态 Mi 的一个允的一个允许时间间隔许时间间隔k 流入，则将当前状态矩阵流入，则将当前状态矩阵Mi的各行向量都右的各行向量都右移移 k 位，高位补位，高位补“0”，然后，同这个，然后，同这个 p 类对象的初始冲突矩类对象的初始冲突矩阵阵 进行进行“或或”运算。运算。探正卡飞羌洱绩堕辗腐索授狄细亩哪劝憾痊捎毡扮柯净赞暴捉畴煽因圾悦第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.3.2 非线性流水线最优调度的非线性流水线最优调度的时空图时空图 时空图可以直观地表示各类流水线的处理过程，也同样可以直观地
40、表示出非线性流水线的处理对象序列在最优调度策略的控制下，按预约表的要求占用流水线各段的处理过程。伍井绪俄冗剐憎搁缎抉啡考餐腔洪哈狠众椎慢玫每池鱼川屉铅妨咖擦俭棚第3章 流水技术与流水处理机第3章 流水技术与流水处理机【例【例3.6】有一个有一个5段单功能非线性流水线，每一个功段单功能非线性流水线，每一个功能段的执行时间均为能段的执行时间均为 ，处理对象在流水线中的，处理对象在流水线中的处理过程由例处理过程由例3.4中的表中的表3.1给出的预约表描述。给出的预约表描述。（1）求流水线的最优调度策略和最大吞吐率。）求流水线的最优调度策略和最大吞吐率。（2）若按最优调度策略连续流入）若按最优调度策略
41、连续流入6个对象，计算个对象，计算流水线的实际吞吐率、加速比和效率。流水线的实际吞吐率、加速比和效率。（3）画出按最优调度策略连续流入）画出按最优调度策略连续流入6个对象的时个对象的时空图，并由时空图计算流水线的实际吞吐率、加空图，并由时空图计算流水线的实际吞吐率、加速比和效率。速比和效率。蓝构召哮泵钧乍肝囚凡菜来论棍冬授兽择桔蜗缄未说谰邑问搪晰肖锌抉析第3章 流水技术与流水处理机第3章 流水技术与流水处理机 解 （1）因为处理对象的预约表相同，所以，流水线的最优调度策略即例3.4中求得的最优调度策略(2,5)。流水线的最大吞吐率就是最优调度策略的最大吞吐率，有TPmax=1/3.5 。（2）
42、按最优调度策略连续流入6个对象，流水线的实际吞吐率和加速比分别为:惕缓堵蝶瘁踊舜欧各舱镜跃愈本惺此榜镊原堆蚂饥梦黑恼此洗盼妖砍碱滇第3章 流水技术与流水处理机第3章 流水技术与流水处理机由表3.1给出的预约表可见，一个处理对象在流水线中被流水线5个段实际处理的时间之和为(2+2+3+2+2)=11 ，所以，流水线5个段处理6个对象的实际处理时间之和为611 =66 。流水线5个段共被占用的时间之和为525 =125 。因此，流水线的效率为 粕吼藤姬卧凑贼亚松泄竭熟迹厨嘻奋受娄溉增工烁待弃饵皿绑爵翁培排茧第3章 流水技术与流水处理机第3章 流水技术与流水处理机6 65 54 46 63 35 5
43、2 24 41 13 32 21 1S S1 16 66 65 55 54 44 43 33 32 22 21 11 1S S2 26 66 65 55 56 65 54 44 43 33 34 43 32 22 21 11 12 21 1S S3 36 66 65 55 54 44 43 33 32 22 21 11 1S S4 46 66 65 55 54 44 43 33 32 22 21 11 1S S5 52t 5t2t 5t2t 9tt(t)例3.6的时空图 就雍灵坊捧凹秩炭连详戮入恢荤佣狂条盂辰呐系精姚粤未蛊扔饯耀醉蒙澜第3章 流水技术与流水处理机第3章 流水技术与流水处理机由时
44、空图得出流水线的实际吞吐率、加速比和效率分别为：谋僻抹巩绕锥窒盏戍纵作贡岂吸嫁月笑轻灭厌吱写譬趁逢赣铃荚掌倪己样第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.3.3 非线性流水线的动态调度非线性流水线的动态调度的实现的实现 n单功能非线性流水线控制器主要由一个初始冲突向量寄存器和一个移位寄存器组成，寄存器的位数为对象经流水线处理所需的 的个数。每一个 将使移位寄存器中的当前冲突向量Ci右移一位，高位补“0”。密刘愿晚淳迢钉任纹弦撩冤桅惟桨锯柜跳什瞒财镰捌爵希遇戮铆汤叼密满第3章 流水技术与流水处理机第3章 流水技术与流水处理机n控制器的工作原理和操作过程如下：n 把初始冲突向量C
45、0由初始冲突向量寄存器装入移位寄存器。n 如果在某个 从移位寄存器移出的是“0”，且同时有一个对象请求进入流水线，则允许该对象进入流水线；如果从移位寄存器移出的是“1”，则禁止对象进入流水线，待下一个 到来时，重新提出请求。n 如果允许进入，就在现行 结束时修改移位寄存器中的内容Ci，它的新内容Cj是Ci移位后的值与初始冲突向量寄存器中的C0进行“或”运算的结果。如果禁止进入，移位寄存器的内容仅右移一位，高位补“0”。眨示坚胸阵楼针陈蓑季核各矩缚壁寥瘴俘挺签方字阉拂弘盾集宋墟珍滦瓶第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.4 流水线的相关问题与相关处流水线的相关问题与相关处理
46、理 n流水线的相关问题分为局部相关和全局相关两类。n局部相关对程序执行过程的影响较小，它仅涉及到相关指令前后的一条或几条指令的执行。n全局相关是指影响整个程序执行方向的相关，主要是转移类指令和中断引起的相关。力此签溶欢袋蜜橱拷卜码酬秀俘瘩肉娃店芥集队姜扁氨胜急辆肄掷属攒娜第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.4.1 局部相关及处理局部相关及处理 n1.顺序流动的“先写后读”相关及处理n顺序流动是指对象从流水线流出的次序同它们流入流水线的次序一样。n如果指令h写入结果的目的地址同指令j读取操作数的源地址是同一个存储单元或寄存器，那么，称这两条指令有“先写后读”的要求。如果当
47、指令j到达读段时，指令h还没有到达写段完成写入操作，那么，指令j读出的数据就是错误的，这就是“先写后读”相关。n解决顺序流动的“先写后读”相关的方法是：延迟、异步流动和建立相关通路。热癸眉寝昨谗漫为獭涧攀喝舷小成河镑泌卤堂逻费果更窃孵妓影俄昌伦圃第3章 流水技术与流水处理机第3章 流水技术与流水处理机2.异步流动的局部异步流动的局部相关相关 n异步流动是指对象从流水线流出的次序同它们流入流水线的次序不一样。n若指令序列中的指令j和指令k都有写操作，且写入的目的地址是同一存储单元或同一寄存器，则顺序执行的结果是指令j先写入而指令k后写入。但是，若采用异步流动方式，则可能出现指令k先于指令j到达写
48、段，那么该存储单元或寄存器的内容最后是由指令j写入的，而不是按指令序列的顺序要求由指令k写入的，这就是“写写”相关。视砸卯捎贱闰圭讽火烙孤怪崩罗翠芋侈毅侧檬赞锹癣郧煞塑钉唤祭冒她雷第3章 流水技术与流水处理机第3章 流水技术与流水处理机n若指令序列中的指令j的读操作和指令k的写操作是同一存储单元或同一寄存器，则这两条指令有“先读后写”的要求。若采用异步流动方式，则可能出现指令k的写操作先于指令j的读操作被执行，那么，指令j读取的数据就是指令k写入的数据，这是违反这两条指令“先读后写”要求的一个错误的数据，这就是“先读后写”相关。n异步流动解决相关的方法同样可以采用延迟方法。茬腺犹污君少悟廷昆绑
49、焙苔菊冷肪西埂花咕陌娄罕棱攀峭蛙钟烹变箍播隶第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.相关专用通相关专用通路路 n在流水线的读段与写段之间增加一条专用的数据通路。n指令j 的读操作不是从存储单元去读，而是通过专用通路读取指令h 刚送入写段的数据，广剧寝溪硼例霸兽胞淬片帚滦惭渤慈鹊这诫淫溯船凑衔藏吉真毛无花裙崩第3章 流水技术与流水处理机第3章 流水技术与流水处理机3.4.2 全局相关及全局相关及处理处理 n由条件转移或程序中断引起的相关称为全局相关。n1.条件转移的处理n在遇到条件转移指令时，为了使流水线不“断流”，通常采用“猜测法”，即在条件转移指令之后，选择一个分支方向，
50、让后续指令进入流水线执行。妄倦塞级幢镑帮酋讨挛英皿皖蔗年缴辱凯羹药憨卒椭出撑兢显洛梦碴败炭第3章 流水技术与流水处理机第3章 流水技术与流水处理机n假设在一般程序中条件转移指令所占比例为p，转移成功的概率为q，那么，对于一个由n条指令组成的程序在执行过程中，由于条件转移需要额外增加的执行时间就是pqn(k-1)。包括条件转移指令在内的n条指令的总的执行时间是 n可得出有条件转移影响的流水线的吞吐率为 炎桓率啼嗣鸽板弹停全良骚驾射诈草具辕吼萝塑缴洁涕仅昌壁釉斩猪旋馅第3章 流水技术与流水处理机第3章 流水技术与流水处理机n当 时，有条件转移影响的流水线的最大吞吐率为n由于条件转移指令的影响，流水