（计算机科学与技术专业论文）kylin超线程技术研究与实现.pdf

里堕型兰垫查盔兰翌窒圭堕兰垡丝苎摘要英特尔公司的超线程技术( b ，p e r - 1 1 l r e a d i l l gt e c h n o l o g y ) 是一项新的微处理器体系结构技术，它将s m 盯( s i i i l i l l t a n e o l l sm u l t i t h r e a d i n g ) 技术引入到i n t e l 体系结构中，通过复制体系结构状态( a f c l l i t e c t u r es 协t e ) 资源将一个物理处理器看成两个逻辑处理器，但共享一套物理执行资源( e x e c u t i o nr e s o u r c e ) ，这样允许两个任务( 一个应用的两个线程或两个独立的应用) 同时运行，增加了微处理器的利用率，通过访存和计算的重叠降低了访存延迟对性能的影响。虽然i i l t e l 提供了超线程微处理器，但如果操作系统不能有效识别和支持超线程，则超线程微处理器如同普通微处理器一样，不能发挥性能。本文的主要工作就是研究k y l i n 操作系统如何有效支持的i n t e l 超线程处理器。本文完成的工作主要包括：首先分析了当前商用的s m t 技术，特别是h t e l 超线程技术，提出了操作系统需要进行的几点支持。其次，提出了一种基于处理器的性能比计算模型的超线程感知调度算法，调度两个加速比较大的线程在超线程处理器中并行执行。然后，设计实现了超线程感知的k y l i n 内核调度器，针对超线程技术进行了相应的调度优化。最后评测了超线程感知内核调度器的有效性。关键词：同时多线程技术，超线程技术，硬件性能计数器，内核调度器第1 页里堕型兰垫查奎茎竺茎生堕兰垡笙苎a b s t r a c th y p e r t l l r e a d i n gt e c h n o l o g yi sag r o u l l d b r e 出n gi 衄o v 撕o n 舶mi n t e lm a tb 幽g sm es m t ( s i r i l u l t a l l e o l l sm 幽慨a d i n 曲i n t om ec o r i l r i l e r c i a lh t e ia r c h i t c c 帆h y p e r -t h r c a d i n gp r o c e s s o r sd u p l i c a t ea r c l l i t e c m r cs 诅t et om a k eap h y s i c a lp a c k e ta p p e a r 嬲t w op r o c e s s o r sa 1 1 ds h a r et 1 1 e m c t i o nu m t w h i c hi i l c r c a s e sm ei l i l i t i 斌i o no fm ep r o c e s s o lh y p e r - t l 鹏a d i l l gp 0 c e s s o rc a i lb e 妇p l e m e m e db yl o w e re n e r g yc o s ta i l ds m a l l e rd i e - s i z e ，w h i c ha l l e v i a t e st l l ec o n n i c to f l o we n e r g yc o s t 缸d1 1 i g hp e r f b 衄a n c e i n t e lp m v i d e st 1 1 eh y p e r - t 1 1 r e a d i i l gt e c l l l l o l o g yt oi n c r e a s es y s t e mo u t p u t h o w e v e ri ft l l eo p e r a t i i l gs y s t e i nc a n n o t 鲫p p o r t 也et e c h n o l o g ye 虢c t i v e l y ，t l l eh y p e r - t h r e a d i i l gp m c e s s o rw i l ln o tb r i n ga n yb e n e f i t t h i sp a p 材p r c s e n t sm em e t l l o d s 吐l a tk y l i no p e r a t i n gs y s t e ms u p p o r th y p e 卜t h r e a d i i l gt c c l l i l o l o 科i i lt h i sp a p e rw ef i r s t l ya r l a l y z et 1 1 ec o m m e r c i a ls m r rp r o c e s s o r s ，e s p e c i a l l yi n t e lh y p e 卜t h r e a d i n gt e c l l i l o l o g ya 1 1 dp r e s e n th o wo p e r a t i n gs y s t e ms h o i l l ds u p p o r tt 1 1 eh y p e r - n 北a d i n g1 k h n o l o g y s c c o n d l y ，p r e map e 面r i n 锄c ee s t i m a t em o d e lb 越e do nt h ep d o c e 辎o re v e n t 删r d l y ，d e s i 弘a n di m p l 锄e n tk y l i nh ) ，p c r a d 啦a 、v a r ck c m e ls c h e d u l e r 也a to p t i i i l i z c sn l et l l z 它a ds c h e d u l i n gf o rh y p e r - n l r c a d i i l gp m c e s s o r l 鹤t l y ，e s t i m a t et l l ev a l i d i t yo f k y l i i lh ) p e r - 1 1 l r e a d i i l ga 、v a r es c h e d l l l e r k e ) 唧o r d s ：s i m u l t a i l e o u sm u i t i t h r e a d i n g ，h ) p e r - t h r e a d i n gt e c h n o l o g ) ，h a 坩w a r ep e d o r r 】n c ec o u n t e r k e m e ls c h e d u i e r第1 i 页国防科学技术大学研究生院学位论文图目录图2 1发射槽利用情况7图2 2h l t e ln e t b u r s t 体系结构8图2 - 3 传统处理器和超线程处理器9图2 4 超线程处理器其工作原理9图2 5i b mp o w e r5 体系结构1l图3 1 负载均衡流程图1 6图3 2l i n l l ) ( 调度器共享队列18图3 3u l e 调度器共享队列1 9图3 4g z i p 与不同程序并行运行时的性能比变化情况2 3图4 1用户级多线程示意图2 6图4 2内核支持实现多线程示意图2 7图4 3k y l i n 线程调度模型2 8图4 4内核进程，内核线程，k s e 和k s e g 结构相互间关系3 2图4 5内核进程状态变化图3 3图4 6 内核线程状态变化图3 3图4 7k s e 状态变化图3 5图5 1线程切换开销比较4 3图5 2v o l a l l o m a r k 测试比较4 4图5 3s p e cc p u 测试比较4 5第i v 页国防科学技术大学研究生院学位论文表目录表2 1i n t e lp e m i 眦4 处理器的资源分配8表3 1 硬件性能计数器2 0表3 2 测试平台2 0表3 3s p e cc p u 测试集2 1表3 4 最低与最高系统加速比2 1表4 1 内核进程关键域说明2 9表4 2k s e 重要域说明3 0表4 3k s e g 关键域的说明3l表4 4k s e q 关键数据结构说明3 7表5 1l m b e n c h 线程切换开销测试结果4 3第v 页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：k z ! i ! 塑垡蕉盐盛婴窒皇塞墨学位论文作者签名孝毛日期：0 洲厂年7 太月6 日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文( 保密学位论文在解密后适用本授权书。)学位论文题目：! y ! i n 蕉垡蕉挂丕盈窥盏塞理学位论文作者签名：煮差j日期：硝年文月歹日作者指导教师签名：兰薹坌整日期：力刀，年，l 月舌日国防科学技术大学研究生院学位论文第一章绪论1 1 课题来源本课题来源于国家8 6 3 重大软件专项课题“服务器操作系统内核”。随着计算机以及计算机网络应用的不断深入与普及，以操作系统为核心的系统软件由于其技术上的基础性和经济上的增值性，是提高软件产业核心竞争力的战略制高点，是国家信息系统安全的重要保证，是建立自主软件体系的基础。以微软为首的国外操作系统厂商通过掌握操作系统等平台软件成为软件产业的上游公司，控制了下游软件产业。作为一个主权大国，我国必须研制具有自主版权的操作系统，否则就不能掌握软件产业的主动权。目前，我国的操作系统完全依赖国外进口，已成为制约我国软件产业发展的严重瓶颈，及我国重要信息系统安全的重大潜在威胁。因此，加快发展以操作系统为核心的自主系统软件是关系到国家长治久安和国民经济可持续发展的重大战略抉择。为了掌握软件产业发展的主动权，为了确保国家信息基础设施的安全，科技部设立了8 6 3 软件重大专项，在系统软件领域实施战略必争，攻克和掌握以操作系统为核心的系统软件技术，形成持续创新的发展能力。自主的服务器操作系统的研发是8 6 3 软件重大专项战略部署中的重中之重。十五期间由国家科技部领导，国防科大联合中软、联想、浪潮、中科院软件所研制了国产银河麒麟( 简称k y l i n ) 操作系统，银河麒麟操作系统参照国际主流标准，借鉴u n 操作系统和微内核操作系统的设计思想，针对高性能服务器需求，设计并实现具有自主版权的、可支持多种c p u 芯片和多种计算机体系结构的、具有高性能、高可用性与高安全性的、并与l i l l u ) ( 应用和设备驱动二进制兼容的面向高性能网络服务的服务器操作系统。目前已推出试用版，并通过了基本功能、性能和安全等方面的测试，正在进行小范围的示范应用。1 2 课题研究背景处理器是计算机系统中最核心的部件，根据i n t e l 提供的资料，从4 8 6 到p e m i u r n4频率提高了5 0 多倍( 其中1 3 倍来自工艺的改进、4 倍来自结构的改进) ，性能提第1 页国防科学技术大学研究生院学位论文高了7 5 倍多( 其中1 3 倍来自工艺的改进、6 倍多来自结构的改进) 。估计1 0 年以后，芯片频率只能提高5 1 0 倍，而其余的性能提高都依赖于结构的改进。另外，片上集成的晶体管数量从目前的几千万个提高到未来的数十亿个，也需要有崭新的结构才能有效地组织和利用【l 】。随着工艺技术和应用需求的不断发展，处理器的体系结构经历了一个否定之否定的辩证发展过程。早期的机器是用分立元件做的，结构只能比较简单：到上世纪六、七十年代，中大规模集成电路的发展使m m3 6 0 3 7 0 和v a x l1 7 8 0 等机器先后采用了较复杂的指令系统( c i s c ) 和动态流水线结构；上世纪八十年代，开始通过超大规模集成电路将完整的处理器实现在单个芯片上。为了便于实现并提高效率，结构简单的r j s c ( r c d u c e dh l s 呲t i o ns e tc o m p u t c r - 精简指令集计算机) 处理器出现了；从上世纪九十年代中后期到现在，集成度的进一步提高为多发射的动态超标量超流水线结构提供了巨大的资源空间，融s c 结构又变得复杂化了。日趋复杂的单处理器结构导致芯片资源利用率降低及功耗的增加。同时，复杂的集中控制的结构给芯片的布线和时钟频率的提高带来了困难。于是，未来的芯片会需要一种简单的、分布式控制的结构，即芯片的体系结构越来越强调结构上的层次化、功能部件的模块化和分布化，让每个功能部件都相对地简单，部件内部尽可能保持连线的局部性。为了进一步开发并行性，有效地利用集成度的提高带来的海量晶体管资源，提高微处理器的性能，学术界和工业界已开展了多个方面的研究与探索工作。这些工作基本上可以分为如下三类“1 ： 通过进一步提高复杂度来提高性能。这种方法沿袭传统的指令级并行( i l pi n s t n l c t i o n l e v e lp a m i l e l i s m ) 方法来加速单线程应用，目标在于进一步挖掘单个应用内在的i l p 。这些研究共同的思想是组织发射度更宽的超标量结构，并采用更多的功能部件、多级c h e ( 高速缓存) 和激进的数据、控制和指令预测。这类方法的问题在于：一方面单个应用内在的i l p 是有限的，提高性能的潜力很快就会达到极限：另一方面将导致芯片的复杂度过高，使得一个完整的通用芯片的设计、验证和测试的成本变得令人难以接受。以下两类方法则分别从不同的途径在提高微处理器性能的同时降低芯片的复杂度。 用软件的复杂性换取硬件的简单性，即显式并行( e p i c e x p l i c i t l yp a m l l e li n s t m c t i o nc o m p u t i n g ) 。这种方法运用所谓“大编译”的设计思想，通过体系结构的支持，主要依靠编译器的努力，从应用中提取尽可能多的“显第2 页国防科学技术大学研究生院学位论文式并行性”，用超长指令字( v l l w ，v e r y l o n gi i l s 劬c t i o nw o r d ) 来表示可并行执行的指令，从而大大简化了控制逻辑。这个办法的主要问题是：一方面会增加软件( 即编译器) 的复杂性，另一方面有些相关( 如访存地址相关) 在编译时是无法确定的。此外，当指令宽度进一步加宽后如何维护兼容性也是一个问题。 通过线程进程级并行性的开发提高性能。代表性的工作有同时多线程( s m ts i m u l t a n e o i l sm i l l t i t h r e a d i n g ) 处理器。s m t 的基本思想是以指令发射槽的并行粒度加速多个线程的执行，最大可能地实现宽发射和乱序执行，提高处理器运算部件的利用率，缓和由于数据依赖或c a c h e 失效带来的访存延时。所付出的代价是略微增加了发射和控制逻辑的复杂性。从体系结构观点来看，s m 盯处理器的灵活性是非常出色的。i n t e l 超线程处理器是第一个商用的s m t 技术处理器，现在已经成为i i l t e l 公司的主流技术，大规模的应用在了服务器等高性能计算机平台上。现在主流的操作系统包括w i n d o w sx p ，m mp d x ，以及l i n u x2 4 1 7 以后的版本均针对超线程技术进行了相应的优化。k y l i l l 操作系统作为国产通用服务器操作系统也必须跟随当前国际上的主流技术，要求对超线程技术处理器提供较好的支持。1 3 课题研究的内容和完成的工作本课题的研究目标是在k y l i n 操作系统上实现对1 1 1 t e l 超线程技术的支持并且根据超线程技术的特点进行内核调度器的优化。课题的主要工作包括以下内容：系统的分析了当前主流的s m t 处理器的基本结构，关键技术以及操作系统需要进行的支持。设计了一种基于性能比计算模型的超线程感知的调度算法 设计实现了适合超线程技术的k y l i l l 超线程感知内核调度器对k y i i n 超线程感知内核调度器进行了性能评测，验证了其有效性在攻读硕士期间，以第一作者在微型机与应用和国防科技大学第五届研究生学术活动节论文集发表文章各一篇( 见本文附录)1 。4 论文的组织本文的内容共分六章，各章的内容安排如下：第3 页国防科学技术大学研究生院学位论文第一章绪论。介绍课题来源和研究背景，处理器的发展以及同时多线程( s m t s i m u l t a i l e o u s m u l t i t h r e a d i n 蓟技术的提出，确定了课题的研究目标。第二章操作系统同时多线程技术。介绍了i i l t e lh ”e r - 1 1 l r e a d i n g ，i b mp 0 、扼r等主流商用s m t 处理器技术，并提出了操作系统需要进行的几点优化。第三章k y l i n 超线程感知算法设计。提出了一种基于处理器事件性能比计算模型，并且在此基础上设计了一种超线程感知调度算法。第四章k y l i n 超线程内核调度器设计与实现。通过结合第三章的超线程调度算法设计实现了针对超线程技术进行调度优化的内核调度器。第五章性能评测和分析。采用l m b e n c h ，v o l a i l o m a r k ，s p e cc p u 等测试工具进行了内核调度器的性能评测，验证其有效性。第六章结束语。在总结全文的基础上，提出下一步的研究方向。第4 页国防科学技术大学研究生院学位论文第二章操作系统同时多线程( s m t ) 技术2 1 处理器指令并行方式2 1 1 多发射处理器多发射处理器。1 ( m u l t i p l ei s s u ep r o c e s s o r ) 包括超标量和超长指令字( v e r y l 。n g i n s t r u c t i o n r d ，v l l w ) 处理器，其思想是允许在一个时钟周期内发射多个操作执行以减少处理器的平均c p i ( c y c l ep e ri n s t r u c t i o n ) ，更好地利用处理器的功能部件。提高多发射处理器资源利用率的关键问题是如何在程序中找到足够的指令级并行性。超标量处理器是依赖硬件来发现i l p ，而v l l w 处理器则依赖编译器来发现i l p 。不管是超标量还是v l l w 处理器都只能挖掘同一个线程的i l p 来提高处理器资源利用率。当多发射处理器不能发现足够的指令来填满发射槽时就产生了水平浪费( h o r i z o n t a lw a s t e ) 。此外当资源冲突造成多发射处理器在接下来的时钟周期中不能发射指令，则造成了垂直浪费( v e r t i c a lw a s t e ) 。如图2 1 所示为多发射处理器中可能造成的垂直浪费和水平浪费情况。图2 一l 中空白块表示该指令发射槽浪费了；不同的填充纹理表示不同线程。现代超标量处理器包括：d e c c o m p a q 2 11 6 4 ，p o w e r p c ，m i p sr 1 0 0 0 0 ，s u nu l t r a s p a r c ，h pp a 一8 0 0 0 ，i n t e li a 一6 4 ( i t a n i u m ) ，t r a n s m e t ac r u s o e 。2 1 2 多线程处理器为了同时利用指令级并行和线程级并行，研究者提出了两种思路。第一种是将多个超标量处理器放在同一个芯片上，也称为单片多处理器( c m p ) 。第二种是在处理器中设计多个硬件现场，多个现场共享所有的功能部件，也就是采用多线程处理器。多线程处理器的目的是减少长延迟操作对处理器效率的影响，例如减少c a c h e失效和执行时间长的指令对处理器效率的影响。多线程处理器通常为每个线程维护独立的p c ( p r o g r a mc o u n t e r ) 和寄存器。由于能够快速地切换线程上下文，因此多线程处理器能在每个时钟周期发射一个独立线程的指令。多线程处理器又分为细粒度多线程( f i n e g r a i n e dm u l t i t h r e a d i n g ) 和粗粒度多线程( c o a r s e g r a i n e dm u l t i t h r e a d i n g ) 处理器。细粒度多线程处理器( 也称一焉了f 一国防科学技术大学研究生院学位论文为i n t e r l e a v e dm u l t i t h r e a d i n g ) 在每个时钟周期都进行线程上下文切换：粗粒度多线程处理器( 也称为b l o c k e dm u l t i t h r e a d i n g ) 是在遇到长延迟操作时才进行线程上下文切换，否则一直执行同一个线程的指令。由于存在多个独立的线程上下文可供取指，多线程处理器能够利用线程级并行来提高处理器资源的利用率。如图2 1 b 和2 1 c 所示。多线程处理器可以有效地减少垂直浪费情况。典型的多线程处理器包括：d e n e l c o rh e p ，t e r a ， i a s a 和m i ta l e w i f e 。2 1 3 单片多处理器( c m p )单片多处理器片采用的方式是简化核心。将更多的晶体管压缩到一个芯片中，同时简化每一个c p u 的设计，把更多的c p u 压在一个芯片当中以提高整个芯片处理事务的能力。c m p 允许多个线程在多个处理器核上并行执行，从而利用线程级并行性来提高系统性能。然而由于单片多处理器系统的资源是采用划分方式的，当没有足够线程时，资源就浪费了。图2 1 d 即为c 卿的指令发射槽利用图。c 肿的主要好处是处理器核可以很简单，易于获得较高主频，同时也缩短了设计和验证时间。典型的c m p 系统包括：s t a n f o r dh y d r a ，i b mp o w e r 4 ，s u nh i a j c ，b r o a d c o ms b l 2 5 0 ，c r a d l e su n i v e r s a lm i c r o s y s t e m 。2 1 4 同时多线程技术( s m t )同时多线程“3 是新的处理器体系结构，它允许在一个时钟周期内发射多个线程的多条指令执行。为了能够在一拍内同时执行多个线程中的指令，s m t 需要复制一些超标量资源。主要有： 硬件现场资源，包括寄存器和程序计数器每线程的流水线冲刷机制 指令执行结束后的撤出机制 每线程的精确中断和子程序返回机制在转移目标缓冲器和转换后援缓冲器t l b 中增加线程标志s m t 结合了超标量和多线程处理器的特点，可以同时减少水平和垂直浪费。s m t在两个方面提高了处理器的总体性能： s m t 允许在一个时钟周期内执行来自不同线程的多条指令。因此在一个时钟周期内，s m t 能够同时利用程序的t l p 和i l p 来消除水平浪费，提高处理器发射槽以及功能部件的利用率( 如图2 1 e 所示) 。理论上来说，s m t 允许任何线程的组合来发射指令。当由于长延迟操作或者资第6 页国防科学技术大学研究生院学位论文源冲突导致只有一个活动线程时，该线程能够使用所有可获得的发射槽。这使得可以通过使用其他线程的未阻塞指令来消除垂直浪费。由于s m t 处理器在每个时钟周期中可以选择多个线程的指令执行，因此能够更好的利用处理器资源。尽管多发射处理器在一个时钟周期内能执行多条指令，但是当在个时钟周期内不能找到足够的并行指令时，多发射处理器效率会下降。多线程处理器可以克服长延迟操作和资源冲突所带来的限制，但是不能有效地利用处理器中的所有资源。s m t 结合了超标量和多线程的好处，而不需要很大的代价( 例如芯片面积) 。阳霸豳圜| 亘霍上革爱射挂度参t c ) 镊枉度多俩簟_ 埒参麓理1 ) 弼时多拽住培掏( 4 发射膏)拽匠墙拘拽捏精拇曩结构0 戡l 匀伫墁五bg 拽e b0 魁理)h 茇射勘( 4 发射i 幻( 4 发舯，旬图2 1 发射槽利用情况2 2 商用的s m t 处理器从前一节看到，同时多线程技术可以较大幅度的提高处理器资源的利用率，处理器厂商也推出了一系列的商用s m r 处理器，如早期的p h a2 1 4 6 4 处理器，现在普遍使用的i n t e l 超线程( h y p e r - n 聆a d i n g ) 处理器，以及i b mp o w e r5 系列。2 2 1 i n t e l 超线程( h y p e r - t h r e a d i n g ) 处理器i n t e l 公司于2 0 0 2 将s m t 引入i n t e lp e n t i u m4 处理器，推出了h y p e r t h r e a d i n g 【6 】技术。h y p e r t h r e a d i n g 技术通过共享，划分，复制i n t e l 的n e t b u r s t 微体系结构( 图2 2 ) ，让一个物理c p u 中具有两个逻辑c p u 。支持超线程技术的操作系统可将一个物理处理器视作两个处理器，并为每个处理器分配一个线程进行处理。第7 页国防科学技术大学研究生院学位论文图2 2i m e ln e t b u 喊体系结构 复制的资源：为每个逻辑处理器维持的体系结构状态。划分的资源：当逻辑处理器处于多任务模式下，这些资源平均分给两个逻辑处理器，当处于单任务模式下，这些资源归一个逻辑处理器独享。共享的资源：逻辑处理器平等竞争的资源。表2 1k t e lp e n t i u m4 处理器的资源分配位置复制的资源共享的资源划分的资源取指n l bm i c m c o d cr o mc h es t r e m i l l gb u 彘r s分支预测r e t ms t a c kb u 廊rg l o b a li l i s t o 巧b r a n c hh i s t o r yb u 位ra m y译码s t a t el o g i cu o p q u e u e执行r e g i s t e r 糟n 枷ei n s t n l c t i o ns c h e d u l e r sl k t i r e m e n tr e o r d e rb u f f e r存储c a c h e sd t l b超线程技术复制了每个处理器的体系结构状态。体系结构状态对程序或线程流进行跟踪，各项工作( 包括加、乘、加载等) 由执行资源负责完成。在调度线程时，操作系统会将这两种体系结构状态视作两个逻辑处理器，支持多处理器或多线程的软件无需修改即可在两个逻辑处理器上运行，每个逻辑处理器可以单独对中断作出响应。第一个逻辑处理器可以跟踪一个软件线程，同时第二个逻辑处理器跟踪另一个软件线程。例如，当一个逻辑处理器在执行浮点运算时，另一个逻辑处理器可以执行加法运算和加载操作。第8 页国防科学技术大学研究生院学位论文i ：2 竺li 竺竺il ms l mh ms l a m - s t m r c - h lp r o c e s s o re x 划i o f r 睫s re x e t l o nr 吣s o r x e 叫u o np r d o e s s o fe x 曰刘1 1 0 nr e s o ur sr o u r e s d u t e s只e s r c e si-图2 3 传统处理器和超线程处理器图2 3 左图为传统的双c p u 系统，每个处理器有一套独立的体系结构状态和处理器执行资源。每个c p u 上只能同时执行一个线程。右图为支持超线程的双处理器系统，每个处理器有两套独立体系结构状态。超线程技术处理器的工作原理如图2 4 所示：图2 4 超线程处理器其工作原理 提取和发送引擎。提取和发送引擎可交替从各逻辑处理器提取指令并将这些指令发送至快速执行引擎处理。在执行跟踪高速缓存中，一行指令是为一个逻辑处理器而提取的，而另一行指令是为另一个逻辑处理器而提取的。只要两个逻辑处理器都要使用该执行跟踪高速缓存，这一过程就会不停地交替进行。如果一个逻辑处理器不需要使用此高速缓存，则另一个逻辑处理器会使用此执行跟踪高速缓存的全部带宽。 快速执行引擎。在快速执行引擎中，两个逻辑处理器可同时执行。快速执行引擎从指令队列中提取指令，并将其以最快的速度发送至执行单元。指令选取只和执行单元的相关性及可用性有关，可乱序进行，因此后边的指令可在先前指令之前安排执行。对大部分指令而言，执行内核不会记住哪第9 页国防科学技术大学研究生院学位论文些指令属于哪个逻辑处理器。调度程序也不会辨别不同逻辑处理器的指令，而只是简单地将指令队列中的独立指令分配到可用的执行资源。例如，调度程序可能会将线程l 的两条指令和线程2 的一条指令安排到同一周期。 重新排序与引退部件。重新排序与引退部件将所有乱序执行后的指令恢复程序顺序，并将这些指令的状态按程序顺序排好。两个逻辑处理器交替执行指令引退操作。 高速缓存：处理器的高速缓存高速向处理器核心传输数据和指令。高速缓存由这两个逻辑处理器共用，旨在通过高水平的结合确保将数据可靠保存在高速缓存中，从而最大限度地减少潜在的高速缓存冲突。 系统总线：奔腾4 处理器的8 0 0 或5 3 3 m h z 系统总线可提高多任务处理操作系统和多线程应用的吞吐量，并在访问系统内存时为超线程技术提供必要的带宽。当逻辑处理器无法在高速缓存中找到所需数据时，就会从通过系统总线从随机存取存储器中获取。2 2 2i b mp 们v e rsm m p o w e r 5 7 1 在基于p o w e r4 及p o w c r4 + 的设计基础上增加了同时多线程( s m 盯) 能力，可以将一个处理器转变为两个处理器，从而允许一个芯片同时运行两个线程，由此大大降低了完成一项任务所需要的时间。一个p o w e r5 系统最多可以支持多达6 4 个处理器，这样从软件运行角度来看，就好像是1 2 8 个处理器在工作。同h y p e r - n l r 朗d 吣技术类似，p o w e r5 的处理器也支持单线程模式和多线程模式。单线程模式允许一个线程使用所有的系统资源，多线程模式允许两个线程同时使用系统的资源。p o w e r 5 又将单线程模式分成了两种工作模式：l 、空闲状态：一个处理器的上下文是一个空的线程，不会产生任何的指令解码，系统资源由一个线程独占2 、挂起状态：一个线程的指令解码被挂起，另一个活跃线程占用系统资源，直到产生一个中断，被挂起的线程才会继续解码并且在多任务模式下执行。第1 0 页里堕型堂垫查奎兰坚茎圭堕堂焦笙苎图2 5i b m p o w e r 5 体系结构在m mp o w e r5 中，复制的资源包括程序计数器，指令队列，返回栈，存储队列。其它的资源包括分支历史表( b r a l l c h1 1 i s t o r yt a b l e s ) ，指令组构成( i n s 眦t i o ng r o u pf o 玎n a t i o n ) ，流出队列( i s s u cq u e u e ) 以及功能部件都由两个线程共享，并且对这些资源的访问都可以由线程特定的优先级控制。线程的优先级决定了从该线程解码的指令数目，通过这种机制可以使高优先级的线程使用更多的系统资源，这也是p o w e r5 系统比i n t c lh y p e r - 1 1 l r e a d i i l g 技术更具有优势的地方。p o w e r5 通过资源平衡逻辑部件( r e s 0 u r c e - b a l a n c i n gl o g i c ) 来监控g l o b a lc o m p l e t i o nt a b l e ( g t c ) ，二级c a c h e 的失效率以及指令流出队列。g l o b a lc o m p l e t i o nt a b l e ( g c t ) ，可以记录不同线程指令的执行情况，一个线程如果使用了g t ce n 砸e s 超过了预定义的阀值，说明该线程占用了过多的系统资源，那么它就会被赋予一个较低的优先级，使得该线程解码的指令减少，从而避免的其它线程的饿死。如果硬件监控到一个线程引起的二级c a c h e 失效超过了预定义的阀值，那么资源平衡逻辑部件就会暂停该指令的解码，直到c a c h e 拥塞消失。如果资源平衡逻辑部件监控到一个流出队列发生阻塞，那么说明一个线程执行了一个延迟较长的指令。这时处理器将该线程等待分派的指令清空，直到延迟较长的指令执行完毕。p o w e r5 系统通过资源平衡逻辑部件及时调整线程的优先级从而保证了处理器共享资源的最佳分配。第l l 页国防科学技术大学研究生院学位论文2 3 同时多线程的操作系统支持随着s m t 技术的普及，现在主流的操作系统针对s m t 做了相应的优化。2 3 1 对s m t 体系层次结构的支持i n t c l 在推出超线程技术的时候宣称传统的s m p 应用程序可以不加修改的应用在超线程的处理器上，但是由于超线程处理器中的逻辑处理器共享执行资源，如果把两个逻辑处理器当成s m p 系统中独立的处理器对待，在进行任务调度时则可能会导致两个超线程处理器的执行资源冲突，降低整个系统的性能。在s m t 系统中，如i n t e l 超线程系统，b i o s 负责启动逻辑处理器，它将所有已经启动的逻辑处理器创建为一张表，并将这张表提供给操作系统的多重a c p i描述表( m a d t ) 。b i o s 把m a d t 作为a c p i 的一部分传送到操作系统。在早期的操作系统中如w m d o w s2 0 0 0 是不能识别逻辑处理器和物理处理器的。w i n d o w s 2 0 0 0 顺序启动b i o s 列出的每个逻辑处理器直到已经启动的处理器数目与该版本操作系统的许可限度相等。直到w m d o w ss e r v e r2 0 0 3 和w m d o w s ) 可以通过i n t e l 的c p u i d 指令机制来识别超线程处理器，而且许可限度是以系统中物理处理器的个数为标准的。l i n l l 】( 内核从2 4 1 7 开始支持超线程技术，l i n l l ) ( 将超线程处理器视为m m a ( n o n u i l i f o 咖m e m o r ) r a c c e s s 觚l l i t e c h u r e ) 结构中的一个特例，每个物理处理器被视为n u m a 结构中的一个节点，该节点包含两个逻辑处理器。2 3 2s m t 环境中无效操作问题一些操作如s p i n 1 0 c k ，i d l e 1 0 0 p 的执行虽然没有进行真正的运算但却消耗了系统的执行资源，在s m r 系统中，这会导致整个物理c p u 的性能下降。多线程应用为了保证执行的正确性通常采用s p i n 1 0 c k 循环同步机制。s p i i i 1 0 c k循环发送多条读请求来查询共享变量，由于这些小循环的速度非常快，会产生大量的乱序读请求，因此没有优化的s p i l l 1 0 c k 循环会使操作系统的性能受到极大影响，特别是在s m t 系统中，会影响另一个逻辑处理器上线程的执行效率。操作系统针必须对这个问题进行了相应的优化使用相关的硬件指令。1 1 1 t e l 处理器提供了p a u s e 指令，将该指令插入s p i n 1 0 c k 的循环体中，当尝试获得s p i i l 锁失败时，则调用p a u s e 指令暂停一个逻辑c p u 的执行。i n t e l 第二代超线程处理器p r e s c o t t 提供了新的m o n i t o r 和m w a i t 指令对。m o n i t o l v m 、) v = a i t 是对h l t 和p a u s e的一个补充，目的是使共享同一物理资源的逻辑处理器对共享资源进行有第1 2 页国防科学技术大学研究生院学位论文效的划分或合并。m o n i t o r 建立起一个用来对写操作进行监视的内存地址范围；m w a r r 将逻辑处理器置于临时挂起状态并释放所占有的执行资源，直到有写操作作用于被监视的内存范围。这种机制可以替带s p i n 1 0 c k的使用。 不修改s p i l l 1 0 c k 的结构，通过硬件实现降低使用s p i nl o c k 线程的优先级，减少其对资源的占用。这是mp o w e r5 采用的方式。如果一个逻辑处理器上没有可以执行的进程，操作系统的调度器通常会调用i d l e 进程占有c p u ，i d l e 进程查看有没有新的或是迁移过来的进程可以执行，这个过程也会占用系统的执行资源。i n t e l 处理器提供了h l t 指令，当一个处理器处在i d l el o o p 状态时，执行该指令进入休眠状态，同时释放占用的系统执行资源，直到该处理器接受到一个中断。l i n l l ) 【2 6 使用p r e s c o n 的m 咖指令优化i d l e1 0 0 p 。空闲的处理器上的i d l e进程使用m 、7 l ，a 1 1 r 指令临时挂起，同时等待另一个逻辑处理器写入一个数据结构。当操作系统的调度器要在空闲的处理上执行一个新的进程时，则由另一个逻辑处理器写入该数据结构，唤醒空闲处理器的i d l e 进程。这种机制开销小于传统的机问中断方式。2 3 3 c a c h e 问题超线程微处理器l 1 数据c a c h e 的数据项是线性索引的，因此两个逻辑处理器可以用相同的线性地址访问数据，但这些两个线性地址有可能被映射到不同的物理地址，当这种竞争访问发生时就会重复地发生分配和淘汰c a c h el i n e ，系统性能则会受到影响，因此l i n u x 等操作系统通过调整用户栈大小以避免整6 4 k 边界引起的访问冲突。同时在s m t 系统中，逻辑处理器共享了c a c h e 等资源，进行线程迁移时，应该优先将线程迁移到同属的逻辑处理器上，从而减少线程迁移的开销以及减少c a c h e 的失效率。2 3 4 线程并行执行的问题在s m t 处理器是存在两个( 或多个) 执行现场的单处理器，c a c h e 、执行部件等是由两个逻辑处理器共享的，只有两个使用处理器不同部件( 比如整数部件和浮点部件) 的线程在其上运行的时候才有较好的加速，否则，由于执行部件冲突以及c a c h e 失效，使s m t 技术不会带来有效的性能提升。现有操作系统调度器通常不能区分哪些线程是有冲突的，哪些线程会使用不第1 3 页国防科学技术大学研究生院学位论文同的执行部件，因此如何将两个线程调度到同一个物理处理器上才能获得最大的系统加速比是一个非常值得研究的问题。2 4 本章小结本章介绍了现在的主流商用s m t 处理器血t e l 超线程处理器和i b mp o w e r5处理器的体系结构，这是我们研究工作的硬件基础。同时针对s m t 处理器的体系结构特点分析了操作系统需要进行的相关支持。第1 4 页国防科学技术大学研究生院学位论文第三章k y l i n 超线程感知调度算法设计在超线程系统中物理处理器同时执行两个线程，如果两个线程竞争物理处理器的相同功能部件，则会降低整个系统的性能。基于超线程感知的调度算法考虑到这种资源竞争关系，尽量把能获得最大系统加速比的两个线程调度到同一个物理处理上执行。3 1 当前主流操作系统的调度器在多线程的操作系统中，任务调度是一个全局性的、关键性的问题，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有决定性的影响。操作系统对任务的调度主要由内核调度器实现，如今主流的操作系统调度器包括l i l l u ) 【o ( 1 ) 调度器，f r c e b s d 的4 b s d 和u l e 调度器。3 1 1l i n u x 调度器l i i l l l ) c0 ( 1 ) 调度器在一定程度上支持了超线程技术。主要体现在两个方面：一是在处理器之间进行负载平衡时首先进行超线程物理处理器之间的负载均衡，避免一个物理处理器繁忙，而另一个物理处理器空闲的情况；二是实现了物理处理器中两个逻辑处理器运行队列的共享。1 ) 超线程处理器负载平衡o ( 1 ) 调度器在负载平衡方式上进行了较大地改进和优化：当某个处理器负载过轻而另一个处理器负载较重时，系统会从重载处理器上迁移进程过来，超线程系统的负载平衡并不是一次性平衡全系统的处理器负载，而是先平衡物理处理器间负载，再平衡物理处理器内逻辑处理器负载。负载平衡根据调度时机可分为两种调用方式，分别用于当前处理器空闲和处理器忙两种状态，我们称之为”空闲平衡”和”忙平衡”，两者的主要区别在于触发的频率不同，空闲平衡的触发频率大约为忙平衡触发频率的2 0 0 倍。但无论是空闲平衡还是忙平衡，它们的处理流程类似，如图3 1 。第1 5 页里堕型兰垫查奎堂翌茎竺堕堂垡笙茎图3 1 负载均衡流程图如果当前进程所在处理器空闲或者当前绝对时间为空闲平衡或忙平衡触发时钟的倍数，则首先触发物理处理器间负载平衡，计算每个物理处理器的负载情况，从而选择最忙的物理处理器，然后在该物理处理器所有逻辑处理器和当前进程所在处理器组成的处理器集合中判断能否通过进程迁移实现负载均衡，一个相对空闲的处理器上总是试图寻找一个高负载处理器，并将该处理器上的任务迁移到这个处理器上。由于为了避免进程迁移的开销，o ( 1 ) 调度器倾向于尽可能的不迁移进程，因此在判断是否能够迁移的时候做了很多限制： 只有系统最忙的处理器负载超过当前任务所在处理器负载2 5 时才进行负载平衡； 当前处理器的负载取当前真实负载和上一次执行负载平衡时的负载的较大值，平滑负载凹值； 各处理器的负载情况取当前真实负载和上一次执行负载平衡时的负载的较小值，平滑负载峰值； 对源、目的两个就绪队列加锁之后，再确认一次源就绪队列负载没有减小，否则取消负载平衡动作； 源就绪队列中以下三类进程参与负载情况计算，但不做实际迁