（计算机科学与技术专业论文）profile指导的页迁移技术的研究与实现.pdf

国防科学技术人1 研究生院学位论文 摘要 c c n u m a ( c a c h e c o h e r e n tn o n u n i f o t i nm e m o r ya r c h i t e c t u r e ) 系统结合了s m p 系统的 易编程性和分布式存储系统的易扩展性等优点，在科学计算和商业服务等领域有着良好 的发展前景。同传统s m p 系统相比，c c - n u m a 机器的远程存储器访问延迟远高于本地 存储器访问延迟，因此访存的局部性对整个系统的性能具有重要的影响。在访存的局部 性优化技术中，如果仅仅依靠用户在应用中进行优化或编译时优化，则优化的效果有限。 一种可行的方法是采用由操作系统提供的动态页迁移复制技术。 传统页迁移策略的决策信息是历史访问信息，使得迁移的及时性和准确性不自 得到 保证。基于这一考虑，我们提出了一种新的面向c c n u m a 的页迁移技术p r o f i l e 指 导的页迁移技术。与已有页迁移技术不同，我们的页迁移技术结合了p r o f i l e 信息反馈的 方法，能够动态地对未来一段时间的访存情况进行准确预测，具有迁移及时和决策准确 的优点。本文重点研究了该技术的决策信息和迁移策略。并提出了实现方案。完成的主 要工作如下： l 基于实际工程环境，研究了课题相关内容，主要包括c c - n u m a 体系结构和 c c n u m a 系统的数据局部性优化技术。分析了传统页迁移技术，并比较了主要的传统 页迁移策略。 2 页迁移的决策信息是迁移策略的基础，直接影响迁移策略的及时性和准确性。因 此，本文设计了p r o f i l e 指导的页迁移决策信息的形成框架，主要包括p r o f i l e 信息的数据 结构和它的生成与使用方法。 3 根据p r o f i l e 形成的决策信息，基于不同的迁移时机和决策条件，设计了四种p r o f i l e 指导的页迁移策略，并定制了相关的页迁移算法。这些策略能够确保页迁移的及时性和 准确性防止出现乒乓现象。同时模拟了四种页迁移策略，重在比较策略性能的优劣。 4 ，页迁移的开销是影响页迁移效率的重要因素，而迁移过程的页表刷新开销又是主 要的迁移开销。我们致力于减小p r o f i l e 指导的页迁移开销，提出了一种在操作系统内核 中高效实现物理地址到虚拟地址的转换技术反向页表技术，并着重研究了反向页表 在页迁移策略中的应用。 5 分析了l i n u x 内核对n u m a 的技术支持和i a 6 4 的存储管理机制，在此基础上 提出了基于反向页表的p r o f i l e 指导的页迁移技术实现方案。 论文完成的工作和取得的成果，对c c n u m a 存储优化技术的研究和实现，具有一定 的理论和实际意义，以及较高的研究参考价值。 关键词：c c - n u m a ，页迁移，页复制，p r o f i l e 信息，反向页表 国防科学 盘术人学 f 究生院学位论文 a b s t r a c t t h ec c - n u m a ( c a c h e c o h e r e n tn o n u n i f o r mm e m o f fa r c h i t e c t u r e ) s y s t e mh a st h e a d v a n t a g e so f p r o g r a m m a b i l i t yo f s m ps y s t e m sa n ds c a l a b i l i t yo f d i s t r i b u t e dm e m o r ys y s t e m s i th a sap r o m i s i n gp r o s p e c ti ns c i e n t i f i cc o m p u t i n ga n dc o m m e r c i a lm a r k e t c o m p a r e dw i m t r a d i t i o n a ls n i ps y s t e m s ，c c - n u m a m a c h i n e s a c c e s s i n gl a t e n c yt or e m o t em e m o r y i sh i g h e r t h a nt h a tt ol o c a lm e m o r y s ot h el o c a l i t yo f m e m o w a c c e s sh a sa ni m p o r t a n ti m p a c to nt h e p e r f o r m a n c eo f t h ew h o l es y s t e m i na l lt h et e c h n o l o g i e st oo p t i m i z et h el o c a l i t yo f m e m o r y a c c e s s ，i fa l lt h eo p t i m i z a t i o ni sd o n eb yu s e r si ns p e c i f i ca p p l i c a t i o n so ri nc o m p i l a t i o n ，t h e o p t i m i z i n ge f f e c t s a r el i m i t e d o n ef e a s i b l ew a yt o e x p l o i tm e m o r yl o c a l i t yi su s i n gp a g e m i g r a t i o n r e p l i c a t i o nt e c h n o l o g yp r o v i d e db yo p e r a t i n gs y s t e m t h ed e c i s i o ni n f o r m a t i o no ft r a d i t i o n a l p a g em i g r a t i o nt e c h n o l o g i e s i sh i s t o r i c a l a c c e s s i n gi n f o r m a t i o n t h e r e f o r e ，t h ei n s t a n t a n e o u s n e s sa n da c c u r a c yo fp a g em i g r a t i o nc a n 。t b eg u a r a n t e e d a c c o r d i n gt ot h ec o n s i d e r a t i o n ，w eb r i n gf o r w a r dan e wc c n u m ao r i e n t e d p a g em i g r a t i o nt e c h n o l o g y _ p r o f i l eg u i d e dp a g em i g r a t i o nt e c h n o l o g y d i f f e r e n tf r o m t h et r a d i t i o n a l p a g em i g r a t i o nt e c h n o l o g i e s ，o i l rp a g em i g r a t i o nt e c h n o l o g yc o m b i n e st h e p r o f i l eg u i d e dp o l i c y , w h i c hc a ng i v eap r e c i s ep r e d i c t i o no f m e m e r ya c c e s sd u r i n ga p e r i o do f t i m ei nt h ef u t u r e i th a sa d v a n t a g e so ft i m e l ym i g r a t i o na n da c c u r a t ed e c i s i o n ：t h i s p a p e r e m p h a s i z e so nt h ed e c i s i o ni n f o r m a t i o na n dt h em i g r a t i o np o l i c yo ft h ep r o f i l eg u i d e dp a g e m i g r a t i o nt e c h n o l o g y a n dw ep u tf o r w a r da ni m p l e m e n t i n gs o l u t i o nt ot h i st e c h n o l o g y i ta i m s a tm a k i n gf i v em a j o rc o n t r i b u t i o n s ： f i r s t l y , b a s e do n t h ep r o j e c tb a c k g r o u n d ，t h i sp a p e ri n t r o d u c e sr e l a t e dr e s e a r c h i n gf i e l d ， i n c l u d i n gt h e a r c h i t e c t u r eo fc c - n u m a s y s t e m sa n dt e c h n o l o g i e s t o o p t i m i z e t h ed a t a l o c a l i t yo fc c - n u m as y s t e m s t h e ni ta n a l y s e st h et r a d i t i o n a lp a g em i g r a t i o nt e c h n o l o g i e s a n d c o m p a r e st h em a i n s t r e a mp a g em i g r a t i o np o l i c i e s s e c o n d l y ，d e c i s i o ni n f o r m a t i o no fp a g em i g r a t i o n i sb a s i co f m i g r a t i o n p o l i c y i ti n f l u e n c e t h ei n s t a n t a n e o u s n e s sa n da c c u x a c yo f p a g em i g r a t i o np o l i c y s o ，t h i sp a g e rd e s i g n e daf r a m e o fd e c i s i o ni n f o r m a t i o nf o r m i n go fp r o f i l e g u i d e dp a g em i g r a t i o n ，w h i c hi n c l u d e st h e d a t a s t r u c t u r e t h ec r e a t i n ga n du s i n gm e t h o d s o f p r o f i l ei n f o r m a t i o n t h i r d l y , a c c o r d i n gt ot h ed e c i s i o ni n f o r m a t i o nf o r m e do fp r o f i l ei n f o r m a t i o n ，b a s e do n d i f f e r e n tm i g r a t i o no c c a s i o na n dd e c i s i o nc o n d i t i o n ，t h i sp a p e rd e s i g n e df o u rp o l i c i e so ft h e p r o f i l eg u i d e dp a g em i g r a t i o nt e c h n o l o g y a n dt h i sp a p e rc u s t o m i z e dc o r r e l a t i v em i g r a t i o n a l g o r i t h mo ft h ep r o f i l eg u i d e dp a g em i g r a t i o nt e c h n o l o g y t h e s ep o l i c i e sc a n _ g u a r a n t e et h e i n s t a n t a n e o u s n e s sa n da c c u r a c yo f p a g em i g r a t i o n ，a n dp r e v e n tp i n g - p a n gp h e n o m e n o n w e s i m u l a t e df o u r p a g em i g r a t i o np o l i c y , a i m i n g a tc o m p a r e i n g p o l i c yp e r f o r m a n c e f o u r t h l y , t h e c o s to f p a g e m i g r a t i o ni sa ni m p o r t a n tf a c t o ra f f e c t i n gt h ee f f i c i e n c yo f p a g e m i g r a t i o n ，a m o n gw h i c ht h ec o s td u r i n gm i g r a t i o np r o c e s si st h em a j o rc o s t b e c a u s et h e i m p l e m e n t a t i o no fp a g em i g r a t i o ni n v o l v e st r a n s l a t i o nf r o mp h y s i c a la d d r e s s e st ov i r t u a l a d d r e s s e s ，i tn e e dt r a v e l t h r o u g h a l lt h e p r o c e s s e s s v i r t u a la d d r e s s s p a c e i nt r a d i t i o n a l a p p r o a c h e s ，w h i c hi s i n e f f i c i e n ta n dc o s t l y a i m i n ga t d e c r e a s i n gt h ec o s to fp r o f i l eg u i d e d 国防科学技术夫学研究生院学位沦文 p a g em l g r a t l o n ，w eb r i n gt b r w a r dai l e wt e c h n o l o g yt h a tc a ne m c i e n t l yp e r f o r mt r a n s l a t i o n f r o mp h y s i c a la d d r e s s e st o v i r t u a la d d r e s s e si no sk e r n e l ，n a m e dt h e r e v e r s ep a g et a b l e t e c h n o l o g y ，a n de m p h a s i z eo u rs t u d yo nt h e a p p l i c a t i o n o fr e v e r s e p a g et a b l e i n p a g e m i g r a t i o np o l i c y f i n a l l y , t h i sp a p e ra n a l y s e st h es u p p o r t i n gt e c h n o l o g i e sf o rn u m a i nl i n u xk e m e j s a s w e l la s m e m o r ym a n a g e m e n tm e c h a n i s m si ni a 一6 4 a c c o r d i n gt oa l lt h e s ek n o w l e d g e s ，w e p mf o r w a r da ni m p l e m e n t i n gs o l u t i o nt ot h i sp r o f i l eg u i d e dp a g em i g r a t i o n t e c h n o l o g yb a s e d o nr e v e r s e p a g e t a b l e r h ew o r ka n dc o n t r i b u t i o n o ft h i s p a p e r h a v ead e f i n i t e r a t i o n a l ea n dr e a l c s i g n i f i c a n c e t ot h er e s e a r c ha n d i m p l e m e n t a t i o n o fc c - n u m am e m o r y o p t i m i z a t i o n t e c h n o l o g y , a n dh a v ec o n s i d e r a b l er e f e r e n t i a lv a l u e st or e l a t e dr e s e a r c h k e y w o r d s ：c c n u m a ，p a g em i g r a t i o n ，p a g er e p l i c a t i o n ，p r o f i l ei n f o r m a t i o n ，r e v e r s ep a g et a b l e 一 i h 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其芭 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论又题目： ! ! ! ! i ! i 撞昱丝亟适壁茧盛煎塑蕉生塞理 学位论文作者签名 丕堑 日期：劲d 审年j 月g 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 ? + i 坎求大学可以保留并向国家有关部门或机构送交论文的复印件和电产 j 一女，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密学位论文在解密后适用本授权书。) 学位论文题目：一上! ! ! i ! i 撞昱鲍厦垂整挂查的盟窒皇塞墨 学位论文作者签名 作者指导教师签名扔如邑 一 日期：珈0 4 年r 月8 日 日期：炒年厂月p 日 国伤科学技术入学研究生院学位论文 图目录 图l ld s m 的基本结构 图1 2s m p 体系结构 图1 3m p p 体系结构 图1 4c c n u m a 体系结构 图1 5i n t e l 公司的e p i c 设计理念 图1 6c c - n u m a 系统的远程存储访问 图2 - 1基于c a c h e 失效信息的复制，迁移决策树 图2 2 算法流程图 图2 3 用户级动态页迁移模型 图3 1 三级页表地址转换 图3 2i a 6 4 编译器结构。 图3 3 p r o f i l e 信息反馈指导的方法一 图3 - 4p r o f i l e 指导的页迁移过程 图3 - 5 p r o f x l e 信息的收集方法 图3 - 6 预测访问分布率优先的页迁移决策树 图3 7 剩余访问分布率优先的页迁移决筻树 图3 - 8 历史访问分布率优先的页迁移决策树 图3 - 9 首次远程c a c h e 失效触发的页迁移决策树 图3 1 0 迁移前后对迁移页面的访问 图3 1 1 算法实现的流程框架 图3 1 2 模拟程序主流程图 图3 1 3 页迁移策略的主流程图 图3 1 4 剩余访问分布率优先策略流程图 图3 1 5 历史访问分布率优先策略流程图 图3 1 6 首次c a c h e 失效触发的页迁移策略流程国 图3 17 传统页迁移策略流程图 图3 1 8 平均随机数的产生流程圉 图3 1 9 随机模式 图3 2 0 岛定义模式 图3 2 1 迁移策略性能增长率 图4 1 进程的虚存一 图4 2i a 一6 4 页表项 图4 3 页迁移技术中反向页表的应用一 图4 - 4 反向页表及其映射关系 j一一_一一棚一一棚一一一一一一一一一一一一一一一一一一一一一一一 国防科学技术火学研究生皖学位绝文 国防科学技术人学研究生院学位沦文 表2 1 表2 2 表3 1 表3 2 表3 - 3 表3 4 表目录 c a c h e 失效触发的页迁移策略参数 丽种迁移策略的比较 页迁移决策所需的p r o f i l e 信息格式 p r o f i l e 指导的页迁移算法的主要计数器及含义 p r o f i l e 指导的页迁移算法的阈值及作用 p r o f i l e 指导的页迁移技术与传统页迁移技术的比较 1 3 1 7 2 7 4 1 4 2 4 4 国防科学技术人学研究生院学位论文 第一章绪论 1 1 课题研究背景 过去的几十年里，计算机的发展经历了几代变更。从第一代的真空电子管和继电器 存储器计算机到近年以v l s l ( 超大规模集成电路) 为代表的第五代计算机。计算机系统 的速度在不断提高，而造价和体积却在不断地减小【9 。系统软件的发展也从机器、汇编 语言的荒莽时代逐渐步入以跨平台、可扩展、适合分布式计算的第五代编程语言体系。 其中最有前景的是开放源码的l i n u x 操作系统。未来的计算机系统将是具有更强的能力、 更友好的操作界面并借助互联网的分布式高性能计算平台。 随着处理器及存储器的速度逐渐接近物理极限，现代的高性能计算机为了克服大规 模集成电路和计算机系统制造工艺水平的限制，满足用户不断增长的计算需求，趋于采 用并行体系结构来提高运算能力。存储资源管理也随之成为个活跃的研究领域。分布 共享存储系统( d i s t r i b u t e ds h a r e dm e m o r y d s m ) 由于编程的简易性、良好的可扩展性、 设备的廉价性等诸多优点，成为当前高性能计算机研究的热点之一。 d s m 的基本结构如图l - 1 所示。d s m 由一组结构相同的处理机结点构成，每个结 点主要包括c p u 、c a c h e 、存储模块、通信和存储控制部件( c m m u ) ，结点间通过高速 网络连接。d s m 提供给用户一个统一的逻辑地址空间，每个结点存储模块的地址空间是 全局地址空间的一部分。c m m u 用于控制某结点访存是落在本地结点还是远地结点， 并通过消息方式完成远程数据访问。当访问页面不在本地时，将发生页失效，d s m 系统 从远程结点复制该页拷贝到本地结点。通常，d s m 系统中远程存储访问延迟和本地存储 访问延迟之间的差距能够达到1 到2 个数量级，所以，存储访问的局部性是影响d s m 性能的关键因素之- - 2 3 1 1 9 。 采取有效的局部性优化策略能够减少远程存储访问开销，达到改善系统性能的目的。 我们研究的p r o f i l e 指导的页迁移技术正是着眼予这一需求，是一种存储优化技术。 图1 1d s m 的基本结构 1 2 1n u m a 和c c n u m a 技术 1 2 相关研究 第1 页 国防科学技术大学研究生院1 学1 _ i ) ：论文 现今的6 4 位u n i x 并行计算服务器可分为两类：分布式若享存储结构( d s m ) 和 集群系统。n u m a ( 非均匀存储器存取结构一n o n u n i f o r mm e m o r ya c c e s s a r c h i t e c t u r e ) 是一一 种并行模型，属于d s m 一类。随着高性能计算机的迅速发展，n u m a 技术结合了 s m p ( s y m m e t r i cm u l t i p r o e e s s o r ) 系统和m p p ( m a s s i v e p a r a l l e lp r o c e s s i n g ) 系统的优势， 已经成为当今主流体系结构之一。 对称多处理机s m p s m p 也是一种共享存储器的多处理机结构。它具有寻址空间单一、编程简易和操作 方便等优点。s m p 系统包含多个完全相同的处理器，所有处理器都通过总线访问同一个 物理存储器，且访存延迟一致。处理器之间采用监听协议来实现高速缓存的一致性 2 】。 这就意味着s m p 系统只运行操作系统的一个拷贝，为单处理器系统编写的应用程序可以 毫无改变地在s m p 系统中运行。s m p 体系结构如图l - 2 所示。 目前，众多的商用并行服务器采用了s m p 结构。s m p 体系结构的缺点是可伸缩性 有限，因为存储器接口达到饱和时增加处理器并不能获得更高的性能。 图1 - 2s m p 体系结构 大规模并行处理机m p p m p p 是一种分布式存储模式。m p p 结点传统上由单一c p u 、少量的内存、部分i o 、 结点间的互连以及每个结点的一个操作系统实例组成，它可以被配置为s m p 模式，也可 以被配置为非s m p 模式。由于每个结点拥有自己的操作系统以及各自唯一的物理内存地 址空间，结点间的互连不需要硬件一致性。一致性是在软件中通过“消息传送”f m e s s a g e p a s s i n g ) 方式实现 2 】【9 】。m p p 体系结构如图1 3 所示。 m p p 属于集群系统，可扩展性好。但它的缺点是需要并行编程和并行编译的支持， 使用不便。 图1 - 3m p p 体系结构 第2 页 国防科学技术大学研究生院学位论文 n u m a 系统将s m p 与m p p 的优势结合在一起，它既保持了s m p 模式单一操作系 统拷贝、简便的程序编程模式以及易于管理的特点，又继承了m p p 模式的可扩充性，可 以有效地扩充系统的规模 4 】。 在n u m a 体系结构中，每个处理器与自已的本地存储器和高速缓存相连，并通过 处理器、i o 网络访问共享的y o 和外围设备。处理器之间的通信则通过可选的处理器间 的通信网络来实现。由于n u m a 机器( 如c r a yt 3 d 、t 3 e ) 的远程访问必须经过高性 能互联网络，本地访问只需要直接访问局部内存模块，使得远程主存访问延迟远高于本 地主存访问延迟；并且各个n u m a 结点的c a c h e 只能缓存本地数据与私有数据，使得数 据局部性成为影响系统性能的主要因素。 由于各个n u m a 结点上的存储器可以被所有结点访问，所以产生了多个处理器共 享同一存储单元而引起的存储一致性问题【5 】。为了解决该问题，s g i 采用高速缓存一致 性( c a c h ec o h e r e n t ) 技术，使远程数据能够进入本地c a c h e ，减少远程访问的频率。这 种结构称为c c - n u m a ( c a c h e c o h e r e n t n o n u n i f o r mm e m o r ya c c e s s ) 体系结构。典型 的c c n u m a 系统包括c o n v e x 的e x e m p l a r ，l i p v 2 6 0 0n u m a 系列，i b m 的n u m a q 和s g i 的o r i g i n 系列。 c c - n u m a 体系结构是s m p 结构的自然扩展，结合了s m p 系统的易编程性和分布 式存储系统的易扩展性等优点。典型的设计思想是，系统中每个结点都包含一定数目的 c p u 、主存、c a c h e 和u 0 设备。结点之间通过可扩展的通讯网络互连，并采用基于目录 的c a c h e 一致性协议。c c 小i u m a 结构具有如下特征： 1 单一内存地址空闯，尽管内存模块分布在各个结点上，但是所有的内存模块都 由硬件进行统一编址，并通过互联网络形成共享存储器，易于编程： 2 各c p u 的局部c a c h e 数据来源于全局内存，通常采用基于目录的c a c h e 一致性 协议来保证各结点的局部c a c h e 数据和存储器中数据的一致性，大多数访存可 以在本地高速c a c h e 中进行； 3 存储器在物理上是分布的，即内存模块分布在各个结点上，并通过高速互联网 络互连。这样避免了s m p 访问总线的带宽瓶颈，增强了并行机的可扩展能力。 c c n u m a 体系结构如图1 4 所示。c c - n u m a 系统在性能、灵活性、可用性方面 都能适合用户多种应用的要求，它己成为当今互联网经济时代非常卓越的体系结构，在 科学计算和商业服务等领域有着良好的发展前景，是今后几年大型服务器发展的重要方 向f 1 1 。 图1 4c c n u m a 体系结构 第3 页 国防科学技术人学研究生院。学位论文 1 2 2 i a 6 4 处理器与编译器 ( 一) i a 一6 4 处理器 迅速发展的高性能计算机对处理器的性能提出了严峻挑战，新一代的高性能6 4 位处 理器应运而生。 现在，3 2 位仍然是p c 机市场的主流体系结构。但是，随着处理数据量的不断扩大， 3 2 位处理器在处理能力和地址空间等方面明显不足。因此，增加指令宽度是微处理器的 发展趋势，i a 6 4 就是以6 4 位为基本处理单位。自英特尔于1 9 8 5 年通过8 0 3 8 6 从1 6 位 跨越到3 2 位计算以来，由i n t e l 和h p 公司共同开发的i a 一6 4 芯片代表了新型微处理器的 发展方向，是迄今为止最重要的体系结构。 随着时间推移，技术的进步，应用的发展，实现商性能处理器已不是传统复杂指令 集c i s c 、精简指令集p a s c ，以及现代o o o i s u p e r s c a l e ( 乱序执行，超标量) 架构所能胜 任的。6 4 位处理器的主要设计目标是克服当今处理器系统架构的瓶颈，开发一种全新的 系统架构，最大程度地开发指令级并行( l p ) 。因此i n t e l 提出了与旧有的c i s c 和r i s c 完全不同的设计理念，这就是e p i c ( 显式并行指令体系一- - e x p l i c i t y p a r a l l e l i n s t r u c t i o n c o m p u t i n g ) 2 5 】。e p i c 是i a 一6 4 最具特色的技术。所谓e p i c 技术，是指编译器首先分 析指令间的依赖关系，再将投有依赖关系的指令组合成一组，然后由内置的执行单元读 入被分成组的指令群并执行。e p i c 技术可以降低处理器成本，软件在编译时已经决定了 各条指令的分配情况，这样利用简单的硬件就能够提高指令的并行度。i n t e l 公司的e p i c 设计理念如图1 5 所示。 - 软硬件协同 获取最高性能 - 增强指令级 并行i l p 的先进 特征 - 大量的硬件 资源用于并行执 图1 - 5i n t e l 公司的e p i c 设计理念 i a 6 4 基于显性并行指令计算e p i c 技术，最终实现以下目标： 1 ，克服传统体系结构的限制，更改现有工业标准体系，采用新的并行运算体系： 2 6 4 位内存寻址能力，支持更大空间范围内寻址。在编辑器处理指令时，可以显 著提高效率： 3 单指令简化，即每条指令执行的功能减少，僵执行效率更高； 4 由于运行指令并行化，并且采用了程序控制指令，使得分支预测更加准确，运 算的利用效率更高； 第4 页 国防科学技术人学研究生院学位论文 5 现有流水线采用的是顺序结构，一条运行结束后进行下一条，i a 一6 4 采用并行流 水线结构，提高了工作效率； 6 与3 2 位系统兼容，保持原有投资； 7 通过s p e c u l a t i o n 技术，大大降低控制指令以及存储延迟所带来的浪费。 6 4 位处理器由于技术上的突破和性能上的提高，将成为c p u 历史发展的转折点。 目前正式宣布支持i a 一6 4 平台的有m o n t e r e y 、l i n u x 、h p u x 、s o l a r i s 、w i n 2 0 0 0 等操作 系统。 ( 二) i a 6 4 编译器 与传统的体系结构相比，基于i a 一6 4 的处理器可以提供更高的指令级并行性( i l p ) 。 主要是通过使用推测和预测等先进技术，并辅以大量的内部硬件资源等实现的。这些技 术能够发挥编译器的最大效能，形成新的应用程序编译优化方法，同时处理器也能够发 挥出最佳指令执行效能。 i a 6 4 编译器编译应用程序时着眼于三个主要目标： 1 最小化访存开销 2 最小化分支开销 3 最大化指令级并行 为此，i a 一6 4 编译器结合了些主要的编译优化技术，能够提高i a 6 4 平台上大多 数应用程序的性能( 2 4 1 。这些编译器中的技术利用了i a 6 4 体系结构的特点，减少了额 外的开销。例如，通过有效地应用大的寄存器文件，减小内存操作开销；通过使用旋转 寄存器，减少循环中软件寄存器重命名的开销；利用控制和数据推断来消除多余的l o a d 、 s t o r e 和计算指令。 i a 6 4 编译器的主要优势体现在如下几个方面： 1 使用程序间的优化技术提高编译的性能； 2 通过运用p r o f i l e 指导的编译优化，更好地利用i a 6 4 处理器的预测和推断技术： 3 利用i a 一6 4 体系结构的特性实现新的编译技术，通过软流水加速程序运行。 1 2 3 面向c c - n u m a 的页迁移技术 c c n u m a 系统解决了s m p 系统存在的总线带宽瓶颈问题，具有良好的可扩展性。 c c o n u m a 结构能够c a c h e 远程数据，从而开发了数据局部性，减少了网络竞争、节省 了主存带宽。并且硬件所提供鑫勺一致性主存抽象，能够在应用层将本地访问和远程访问 透明化，从而提供了良好的可编程性。 c c - n u m a 系统中，不同物理结点上的进程可以共享内存。因此所有进程的访问数 据都来自于全局虚地址空间的同一个c a c h e 拷贝。当页面不在本地内存时，发生页失效， 控制软件将从远程结点复制该页拷贝到本地结点，如图1 - 6 所示。物理结点的分布性导 致了内存访问开销取决于：访问数据的结点与包含数据的结点之间的距离。受结点互联 网络拓扑结构的影响，同传统s m p 系统相比，c c - n u m a 机器的远程存储器访问延迟远 高于本地存储器访问延迟。当大量的c a c h e 失效带来频繁的远程访问时，将严重影响系 统性能。所以提高数据局部性成为c c - n u m a 系统存储优化韵重要内容。 第5 页 国防科学技术人学研究生院学位论文 图1 - 6c c n u m a 系统的远程存储访问 数据的局部性主要体现在两个方面：时间局部性和空间局部性。时间局部性是指程 序最近访问的主存单元很可能在短期内被再次访问，产生时间局部性的主要原因是程序 中存在着大量的循环操作。可以通过内存管理中的页面替换算法的候选页选择来确保时 间局部性。比如最近最少使用( l r u ) 算法，其主要思想是将r a m 的每个页面设置一 个年龄计数器，这样每次交换时能够选择进程中的最老页进行交换。空间局部性是指程 序即将访问的主存单元很可能是当前访问数据附近的主存单元，即程序在一段时间内所 访问的地址可能集中在一定范围内，其典型情况是程序顺序执行。因此最好将频繁访问 的数据聚集在一片连续的主存区中【7 】。 在访存的局部性优化技术中，如果仅仅依靠用户在应用中进行优化，那么程序员必 须清楚操作系统中的页分配策略，不但需要修改程序以适应内存的分配需求，而且需要 在不考虑操作系统的情况下，重新定制页分配策略。这种方法一方面实现起来比较困难， 另一方面优化的效果有限。 通常，数据局部性的改善可以通过硬件c a c h e 远程数据、最佳页放置策略和页迁移 复制等机制来实现。由于c c - n u m a 机器能够c a c h e 远程数据，这在一定程度上开发了 数据的时间局部性。但由于c a c h e 容量和结构方面的约束，c a c h e 容量失效( c a p a c i t y m i s s ) 和冲突失效( c o n f l i c tm i s s ) 限制了数据局部性的进一步提高。最佳页放置策略通过编译 时对并行应用程序中的数组和循环等结构的静态分析结合运行时系统，能够对数据进 行最优化分配。当内存访问遵循静态模式时，可以选择这种方法，但是这种技术需要对 每个并行程序单独分析，在整个程序执行过程中，处理器的分配是固定的。相比前两种 机制，页迁移复制策略能够在程序执行过程中收集数据的局部性信息，并根据系统的实 际情况对数据分布进行动态调整，变远程存储访问为本地存储访问，减小c a c h e 容量和 冲突失效，从而达到优化系统性能的目的。 因此，对于运行在c c 寸小m d a 系统中的应用程序，页迁移技术能够很好地提供内存 数据局部性。页迁移复制技术实质上是一种预测技术，即根据收集到的页面访问信息预 测将来的访问情况。实际实现中，通常由硬件提供访问计数器，记录页面的访问失效信 息，由操作系统指定策略相关的些阈值，通过将页面的访问失效信息与操作系统指定 的参数进行比较，作出迁移或复制的决策【6 】【7 】【8 】。 第6 页 国防科学技术人学研究生院学位论文 1 3 1 工程环境 1 3 课题简介 本课题来源于0 1 3 1 型号任务和国家8 6 3 重大软件专项课题服务器操作系统内核”。 结合工程需求，我们的具体实现基于i n t e l 的i a 一6 4 处理器和l i n u x2 4 。1 8 内核。 i a 一6 4 是i n t e l 的6 4 位多处理器体系结构。它克服了传统体系结构的许多限制，并提 供了极大的可扩展空间。通过推断、预、钡4 、显式指令并行等技术，i a 一6 4 较高地实现了 指令级并行性。并且6 4 位存储器地址为高性能服务器提供了巨大的存储空间。而l i n u x 2 4 1 8 内核加上n u m a p a t c h 已经较好地实现了不连续内存设计、n u m a 系统的结点间 处理器的设计，有利于相关工作的展开。 1 3 2 课题研究内容 面向c c - n u m a 的存储优化技术是一个非常广泛的研究课题，其中，由于页迁移技 术能够减少远程访问频率，提高数据的局部性，成为热点研究问题。但是现有的页迁移 策略大多利用访存局部性原理，其决策信息是历史访问信息，通过历史累计信息来预测 未来的访问情况，只有当历史信息累积到一定条件后，才能触发页迁移复制过程，使得 迁移的及时性和准确性不能得到保证。为了解决这些问题，我们提出了p r o f i l e 指导的页 迁移技术。并且在迁移过程中加入了反向页表的支持，以提高迁移的效率。