（计算机应用技术专业论文）一种降低片上多核系统缓存访问延迟的方法.pdf

摘要 摘要 片上多核处理器( c h i pm u l t i p r o c e s s o r ，c m p ) 将多个简单的处理核心集成 到一个物理芯片上，相对复杂的单核处理器设计而言可以更加有效的利用片上 资源，有利于发掘应用中线程级并行性。c m p 的体系结构特征决定了其具有功 耗低、设计和验证简单等优点。因此c m p 成为处理器在今后一段时间内发展 的趋势。为c m p 系统中的多个处理核心提供与其计算能力匹配的数据传输是 c m p 系统面临的主要问题，缓存系统设计作为该问题的主要解决方案成为c m p 系统研究的热点之一。 共享型的二级缓存设计可以更加有效的利用片上缓存，具有较低的缺失率， 是c m p 系统缓存设计的主要选择。n u c a 实现的共享型二级缓存设计在逻辑 上共享地址空间，但是物理上由多个二级缓存模块组成，该方式的缓存设计可 以提供较高的片上缓存访问带宽，避免了单一的二级缓存成为c m p 系统的瓶 颈。但是n u c a 实现的共享型二级缓存的平均访问延迟很大程度依赖于数据在 缓存模块之间的分布。 本文提出了一种基于进程调度对n u c a 实现的缓存设计访问延迟进行优化 的方案( c a c h ea c c e s sl a t e n c yo p t i m i z a t i o ns c h e m eb a s e do np r o c e s ss c h e d u l i n g ， c a l o s p s ) 。c a l o s p s 方案通过添加硬件计数器实现对应用访问缓存规律的收 集。c a l o s p s 方案在操作系统已有基础上对调度模块进行改动，增加了针对缓 存访问规律的中粒度调度模块。中粒度调度模块以应用对缓存模块的访问规律 作为输入，根据缓存访问规律对进程进行调度，并将进程迁移到距离其经常访 问的缓存模块较近的处理核心上执行从而降低进程访问缓存的平均延迟。 c a l o s p s 方案根据进程对缓存的访问规律对进程调度和迁移，可以降低 c m p 系统中处理核心访问缓存的平均延迟。同时，c a l o s p s 方案减少了数据在 片上网络中的传递。仿真结果表明，c a l o s p s 方案可以将缓存访问延迟平均降 低1 0 6 5 ，对某些特定基准测试程序最高可以降低2 5 8 9 ；对片上互连网络 的延迟平均可以降低1 9 5 9 ，对某些特定基准测试程序最高可以降低3 5 4 1 。 关键词：片上多核处理器缓存动态优化进程调度 a b s t r a c t a b s t r a c t c m p ( c h i pm u l t i p r o c e s s o r ) i n t e g r a t e sm u l t i p l es i m p l ep r o c e s s i n gc o r e si n t oa s i n g l ed i e ，a n di ss u i t a b l et oe x p l o r et h r e a d - l e v e lp a r a l l e l i s m ( t l p ) c o m p a r e dw i t h s i n g l e c o r ep r o c e s s o r c m pc a nu t i l i z et h eo n - c h i pr e s o u r c e sm o r ee f f e c t i v e l y ，a n d h a sa d v a n t a g e ss u c ha sl o w p o w e r ，e a s yt od e s i g n ，i m p l e m e n t a t i o na n dv e r i f i c a t i o n , w h i c hm a k e sc m pp r o c e s s o rd e s i g nt r e n di nt h ef u t u r e o n eo ft h ec r i t i c a lp r o b l e m s f o rc m pi sf e e d i n gt h ep r o c e s s i n gc o r e sw i t hs u f f i c i e n td a t a ，w h i c hs h o u l db e c o m p a t i b l e 、j r i t hi t sc o m p u t a t i o np o w e r c a c h es y s t e mb e c o m e s o n eo ft h eh o tc m p r e s e a r c ht o p i c s s h a r e dl 2 - c a c h ec a l lm a k eb e t t e ru s eo fo n - c h i pc a c h ec a p a c i t y ，h a sl o wm i s s r a t ec o m p a r e d 谢t hp r i v a t el 2 一c a c h e ，a n di st h em a i nd e s i g nc h o i c eo fc m p s h a r e d c a c h ew i t hn o n - u n i f o r mc a c h ea c c e s s ( n u c a ) i m p l e m e n t a t i o ns h a r e st h es a m e a d d r e s ss p a c eb u ti sp h y s i c a l l yc o m p o s e do fm u l t i p l ec a c h eb a n k s n u c ac a c h e o f f e r sh i g ho n c h i pc a c h eb a n d w i d t h , a n de l i m i n a t e st h eb o t t l e n e c ke f f e c to ft h eb i g s i n g l ec a c h e b u ti t sa v e r a g ea c c e s sl a t e n c yh i g h l yd e p e n d so ni t sd a t ad i s t r i b u t i o n a m o n gc a c h eb a n k s t h i sp a p e rp r o p o s e sac a c h ea c c e s sl a t e n c yo p t i m i z a t i o ns c h e m eb a s e do n p r o c e s ss c h e d u l i n g ( c a l o s p s ) c a l o s p sa d d sh a r d w a r ep e r f o r m a n c ec o u n t e r st o e x i s t i n gc m pd e s i g n st oc o l l e c tr u n t i m ec a c h ea c c e s sf r e q u e n c yo fe a c hp r o c e s sf o r a l lc a c h eb a n k s c a l o s p sm o d i f i e ds c h e d u l e rt a k e sp r o c e s sc a c h eb a n ka c c e s s f r e q u e n c i e sa si n p u t ，a n dr e s c h e d u l e sp r o c e s s e st ot h ep r o c e s s i n gc o r ew h i c hi s c l o s e s tt op r o c e s s sm o s tf r e q u e n t l ya c c e s s e dc a c h eb a n k c a l o s p sr e s c h e d u l e sa n dm i g r a t e sp r o c e s s e sa c c o r d i n gt ot h e i rc a c h eb a n k a c c e s sc h a r a c t e r i s t i c s ，a n dr e d u c e st h eh o p st h a tm e s s a g e sh a v et ob et r a n s m i t t e d ， t h e r e f o r eo p t i m i z e sa v e r a g ec a c h ea c c e s sl a t e n c yo fp r o c e s s i n gc o r e s c a l o s p s a l s od e c r e a s e st h eo n - c h i pt r a f f i c ，w h i c hi nt u r nr e d u c e sn e t w o r kq u e u i n gl a t e n c y a n dc o m m u n i c a t i o np o w e rc o n s u m p t i o n s i m u l a t i o nr e s u l t ss h o wt h a tc a l o s p sc a n r e d u c ea v e r a g ec a c h ea c c e s sl a t e n c yb y10 6 5 a n du pt o2 5 8 9 f o rs o m e p a r t i c u l a rb e n c h m a r k s ，a n dr e d u c e sa v e r a g eo n c h i pl a t e n c yb y19 5 9 a n du pt o a b s t r a c t 3 5 4 1 f o rs o m eb e n c h m a r k s k e yw o r d ：c h i p - m u l t i p r o c e s s o r , c a c h e ，r u n t i m eo p t i m i z a t i o n , p r o c e s ss c h e d u l i n g i i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位讫文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题且 姓名学号 答辩日期年月日 论文类别博士口 学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系，所 专业 联系电话 e m 8 i 王 通信地址( 邮编) ： 备注： 是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 伊j ，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 臣本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言弟一早jii 第一节片上多核处理器的出现背景及其特点 处理器负责程序指令的译码、执行，是影响系统整体性能的核心部件。传 统的提高处理器性能的主要方法有提高时钟频率和发掘指令级并行性 ( i n s t r u c t i o n l e v e lp a r a l l e l i s m ，i l p ) 等1 1 1 。时钟频率由于受到设计复杂度以及 功耗等因素的限制已经很难进步提升；随着流水线、多发射( s u p e r s c a l a r ) 以及 乱序执行( o u to fo r d e r ) 等技术的采用，进一步开发应用程序的指令级并行性对 处理器性能增长的影响也越来越小【2 】。但是，随着制造工艺的进步，片上可用 的晶体管数目仍然在按照摩尔定律增长。传统的单核处理器的性能提高已经难 于继续与晶体管数目的增长相匹配。 片上多核处理器( c h i pm u l t i p r o c e s s o r ，c m p ) 将多个处理核心集成到一个 芯片上，这些处理核心可以同时执行各自的进程1 。c m p 的体系结构有利于开 发线程级并行性( m e a d l e v e lp a r a l l e l i s m ，t l p ) ，且进程内部还可以继续开 发其中的指令级并行性。因此，c m p 成为今后一段时期内处理器发展的趋势。 由于c m p 的设计采用了较简单的处理器核心，通过多核心之间的并行执 行来提高系统的吞吐率和整体性能，因此c m p 的体系结构具有以下的特点： 高主频：c m p 中的处理核心一般都比较简单，且用于全局控制的信号较 少，因此可以实现较高的时钟频率； 低功耗：c m p 的每个处理核心相对简单，而且可以通过采用关闭闲置的 处理核心以及动态调节电压频率( d y n a m i cv o l t a g e f r e q u e n c ys c a l i n g ， d v f s ) 、负载优化分布等技术降低c m p 的整体功耗； 设计和验证简单：c m p 可以采用已有的处理核心作为单元块，从而缩短 处理器的设计和验证周期。 1 不同操作系统进行调度对象不同，l i n u x 中为轻量级进程而s o l a r i s 中则为线程。下文用进程代指操作系 统进行调度的基本单位，但在提及并行性粒度时依然用线程这一惯用名词。 l 第一章引言 第二节c m p 的分类 以集成的多个处理核心是否相同为标准，c m p 可以划分为同构c m p 和异 构c m p 。同构c m p 大都由物理结构相同的处理核心组成，多个处理核心执行 相同或者类似的任务。因此，任务的划分以及调度主要以均一对等的方式进行， 对编译器和操作系统的依赖较小。典型的同构c m p 产品主要有i b m 公司的 p o w e r 5 处理器 3 1 和s u n 公司的n i a g a r a 处理器 4 1 等。异构c m p 通常由一个通用 处理器和多个协处理器构成，其中的通用处理器主要实现控制、调度以及通用 计算，而集成的协处理器则可以实现对特定应用的加速。在异构c m p 系统上 运行的任务可以划分为多个子任务，任务调度系统根据不同子任务的特点决定 其应该在通用处理器上还是协处理器上运行。因此，异构c m p 从硬件体系结 构的设计层面来说可以更加有效的利用片上资源。然而，任务划分和调度的工 作效率也在很大程度上决定了异构c m p 系统的整体性能。因此，异构c m p 的 编译器和操作系统必须更加充分的考虑c m p 底层硬件结构才能充分发挥其体 系结构设计上的优势，设计和实现都比较复杂。异构c m p 的典型代表是i b m 公司的c e l l 处理器【5 】，它由一个p o w e r 结构的p p e ( p o w e rp r o c e s s o re l e m e n t ， p p e ) 和八个s p e ( s y n e r g i s t i ep r o c e s s o re l e m e n t ，s p e ) 构成，主要面向下一 代的宽带多媒体和图形应用。 根据c m p 的处理核心在层次化存储系统上的互连结构，c m p 可以分为三 类：共享一级缓存( c a c h e ) 的c m p 、共享二级缓存的c m p 以及共享主存的 c m p 。一般来说，处理核心之间的互连网络在层次化存储中越靠近处理器核心， 从体系结构层面来看可以有效发掘的并行性就越细致；而互连网络越靠近主存， 通信代价就越高，因此更适合并行性粒度更大的应用。目前大部分研究者都采 用共享二级缓存或者共享主存的c m p 设计方案。 第三节c m p 面临的主要问题 c m p 通过多线程的并行执行来提高系统的吞吐率。c m p 系统中运行的多 个线程可以通过同时运行多个应用或者由程序员对应用进行显式的并行化产生。 同时运行多个应用的方式可以提高系统的吞吐率，但是无法实现对其中某一特 定应用的加速；程序员显式构造的多个进程虽然可以通过并行执行实现对特定 应用实现加速，但是要求程序员深入理解c m p 的系统结构和应用本身的特点， 2 第一罩引言 并负责多个线程之间的通信和同步，对程序员要求较高。c m p 系统性能的完全 发挥主要依赖于可以简化并行编程模式的配套软件环境诸如编程模型、编程语 言、编译器以及适合于底层硬件的操作系统等的进一步完善 6 1 。 c m p 面临的另外一个问题则是为片上的多个处理核心提供与其计算能力 相匹配的数据传输能力，保证处理核心的有效运转。层次化的存储系统设计是 解决该问题的主要途径。其中，良好的缓存系统设计可以提供较高的片上带宽 和较低的平均访问延迟，同时具有较低的缺失率，减少对主存带宽的压力。因 此，片上缓存系统成为c m p 系统研究的热剧7 】【8 】【9 】【1 0 】【l l 】【1 2 】。 第四节论文导读 在c m p 系统中，主存储器的物理带宽和访问延迟是c m p 系统数据通信的 根本限制因素。共享型的缓存设计与独占型相比具有更大的片上缓存有效总容 量和较低的缺失率，对主存储器带宽的压力更小。但共享型的缓存设计的平均 访问命中延迟很大程度上依赖于被访问数据在缓存中的分布。 针对该问题，本文提出一种基于进程调度降低共享型缓存的平均访问命中 延迟的方案( c a c h ea c c e s sl a t e n c yo p t i m i z a t i o ns c h e m eb a s e do np r o c e s s s c h e d u l i n g ，c a l o s p s ) 。c a l o s p s 方案首先在现有共享型缓存设计的基础上 增加相应的硬件计数器，以发掘不同的进程对缓存系统的访问特点；c a l o s p s 方案对调度器也进行了相应的修改，修改后的调度器以进程对不同缓存模块的 访问频率为依据，将进程调度在距离其经常访问的缓存模块较近的处理核心上 运行，从而降低共享型缓存的平均访问命中时间。 本文第一章介绍了c m p 的出现背景及其特点，讨论了c m p 分类及其面临 的主要问题，引出了本文的研究背景，介绍了本文的整体结构组织。 第二章主要对c m p 中缓存系统的设计空间进行了讨论，其中着重介绍了 缓存系统的设计目标，分析比较了共享型缓存与独占型缓存设计的优缺点，并 最终采用共享型缓存系统作为基本设计，最后对优化共享型缓存设计访问延迟 的研究现状进行了概述。 第三章首先介绍了c a l o s p s 中缓存访问规律收集模块的设计，然后介绍了 c a l o s p s 方案的整体框架及其工作流程。调度算法是调度模块的重要组成部分， 第三章介绍了最优化调度算法的设计、正确性证明及时间复杂度分析，并提出 第一章引言 了一种相对简单的基于数值判断的调度算法。本章最后对c a l o s p s 方案中的相 关开销进行了定性分析。 第四章介绍了仿真作为体系结构量化研究重要手段面临的主要问题及解决 的主要办法；其次对流行的模拟器特别是本文采用的g e m s 模拟器进行了详细 介绍。本章接下来介绍了c a l o s p s 实验方案的设计，论述了实验方案的正确性， 并在最后对模拟器的修改和实现进行了说明。 第五章首先介绍了实验方案所采用的基准测试程序集合，对仿真实验环境 设置的相关参数进行了说明。本章接下来对仿真结果从缓存平均访问延迟、互 连网络平均延迟以及系统整体性能等方面进行了分析。 第六章总结了本文主要工作，提出了对c a l o s p s 进行深入研究的几个可能 方向，并对c a l o s p s 方案所展示的新的系统优化模式进行了讨论。 4 第二章缓存设计空间分析及研究现状 第二章缓存设计空间分析及研究现状 缓存是位于片上的存储部件，是层次化存储系统的重要组成部分。将处理 器经常访问的数据放置在缓存中可以减少处理器和存储系统的速度差异，较好 的为处理器提供其所需的指令和数据，维持处理部件的执行。 与单核处理器相比，c m p 具有多个处理核心，对主存储器的带宽需求更高， 为片上的多个处理核心提供与其处理能力相匹配的数据传输能力是c m p 面临 的主要问题之一。好的c 缓存系统设计应该具有较低的缺失率，从而减少 多个执行核心对主存带宽的需求，降低主存访问较大延迟导致的处理核心等待， 提高c m p 系统的整体系能。 第一节缓存系统的重要性及研究目标 随着制造工艺的发展，主存储器的访问延迟按照较小的指数规律降低。但 是，时钟频率、制造工艺以及体系结构设计上的多种创新使得处理器的性能却 在以更高的指数规律提升。二者综合造成的直接后果就是处理器与存储器的性 能差异呈指数关系增大，内存墙( m e m o r yw a l l ) 也成为了阻碍单核处理器性 能继续提高的主要因素之一【l3 1 。图2 1 给出了以1 9 8 0 年的性能为基准，存储器 和处理器的性能差距随时间变化的曲线图i l 引。 图2 1 存储器与处理器性能差距示意图 5 第二章缓存设计空间分析及研究现状 c m p 系统中将同时执行多个进程以开发应用中线程级并行性。但是，多个 线程的执行对数据的要求也将随着线程数目的增加几乎呈线性增长。因此，片 内与片外的数据交换带宽成为限制c m p 系统性能的主要瓶颈【”j 。 c m p 层次化的存储系统需要为处理核心提供与其计算能力相匹配的数据 传输能力，以维持多个处理核心的有效运转。缓存系统是层次化存储系统中的 重要组成部分之一，物理上大都位于处理器芯片内部。缓存系统通过将主存存 储器中被经常访问的数据读取到片上，使得处理器访问存储系统的平均延迟接 近于访问片上缓存的延迟。因此，缓存系统成为决定系统整体性能的核心部件 之一，其设计必须与c m p 系统中处理核心的数目、应用对数据的需求以及片 上互连网络的设计等多个因素匹配。 缓存系统的设计的最终目标是为处理核心提供尽可能小的平均访问延迟， 其实现的主要途径包括降低缓存系统的缺失率、命中延迟以及提供较高的缓存 访问带宽等【l 刖。主存储器的物理带宽受到处理器引脚数目的直接制约，是片内 与片外数据交换的根本限制因素。同时，随着处理器和主存储器性能差距的变 大，内存访问的延迟已经达到上百个时钟周期【l 引。具有较低缓存访问缺失率的 c m p 系统对主存储器的带宽需求低，同时可以避免较长的主存储器访问引起的 处理核心执行的停顿。因此，降低缺失率是缓存系统设计的首要目标。 第二节缓存系统设计空间 c m p 的缓存系统借鉴了多处理器系统中层次化结构的存储系统设计思想， 通常采用多级缓存结构。处理核心对一级缓存的访问处于其执行的关键路径上， 直接决定着处理核心的执行效率，必须要求一级缓存具有尽可能低的访问延迟。 因此，绝大多数的一级缓存采用独占型设计 3 1 1 4 5 1 。 c m p 系统中的二级缓存设计有独占型和共享型两种选择。独占型的缓存设 计使用分离的地址空间，处理核心拥有各自的缓存模块( c a c h eb a n k ) 。因此， 处理核心访问其二级缓存且命中时的访问延迟低，而且缓存系统的硬件实现较 为简单。但是，分离的地址空间设计使得具有相同地址的数据可能在二级缓存 的不同缓存模块中存在多个副本，二级缓存物理空间的整体利用率较低。因此， 独占型二级缓存设计通常具有较高的缺失率。共享型的缓存设计使用统一的地 址空间，每个处理核心可以访问片上所有的二级缓存模块。在共享型缓存设计 6 第二章缓存设计空间分析及研究现状 中，某一地址的数据在二级缓存中最多只有一个副本。因此，共享型设计可以 充分利用二级缓存的物理空间，与独占型缓存设计相比具有较低的缺失率。但 是，共享型缓存设计的访问命中延迟依赖于主存到缓存系统的地址映射方案、 数据在片上网络中的传输以及数据在缓存模块间分布等多个因素，一般来说比 独占型缓存设计的平均命中延迟大。同时，共享型缓存设计还面临不同核心在 共享缓存空间方案时的公平性等问题。 处理器引脚的数目限制了片内与片外数据通信的物理带宽，是c m p 系统 片内与片外数据传输的根本限制因素。由于共享型缓存设计具有更低的缺失率， 其对片内片外数据通信带宽的需求较低。同时，共享型缓存设计也避免了访问 主存储器导致的巨大延迟导致的处理核心等待，对提高系统的执行效率具有重 要的意义。因此，当前主流的商业通用多核处理器如i b m 的p o w e r5 处理器【3 】 和s u n 公司的n i a g a r a 处理器【4 】等都采用了共享二级缓存的设计。 在采用单一物理块实现方式的共享二级缓存设计的c m p 系统中，多个处 理核心对二级缓存的访问请求需要在集中的二级缓存服务序列中排队。同时集 中的二级缓存也无法为多个请求者提供足够的片上缓存访问带宽，成为系统整 体性能的瓶颈部件。针对这一问题，研究者提出了物理上采用分布式实现的共 享二级缓存设计。分布式实现的共享二级缓存物理上被划分为多个缓存模块 ( c a c h eb a n k ) ，分布在芯片的不同物理位置上，每个二级缓存模块拥有各自 的缓存控制器。处理核心对二级缓存的访问被分散到不同的缓存模块中，从而 可以为处理核心提高较高的片上缓存访问带宽。 在分布式实现的共享二级缓存设计中，处理核心访问缓存的平均命中延迟 与被访问的数据在不同缓存块中的分布直接相关，因此该设计模式也被称为非 均匀的缓存访问设计( n o n - u n i f o mc a c h ea c c e s s ，n u c a ) 。n u c a 实现的 共享型缓存设计具有较大的片上有效总容量，同时可以为片上的多个处理核心 提高较高的片上带宽，成为c m p 系统中最后一级缓存设计的首选p 1 【8 】【9 】【1 0 1 。 第三节n u c a 模型的研究现状 随着制造工艺的发展和时钟频率的提高，片上信号传输单位距离所需要的 时钟周期数目显著增加【1 6 】【1 7 1 。n u c a 缓存系统设计的核心思想是把缓存划分 为多个模块，将被访问的大部分数据都分布在距离访问者较近的缓存模块中， 7 第二章缓存设计空间分析及研究现状 从而避免信号在芯片全局范围内传输引入的延迟。事实上，数据在缓存模块中 的分布很大程度上由应用程序本身执行时对内存的访问决定的。另一方面， n u c a 缓存系统的命中访问时间还与片上互连网络的拥塞情况相关。降低 n u c a 缓存系统的平均访问命中延迟成为了c m p 缓存系统的研究热点之一 l 【7 】【8 】【9 】【1 0 1 。 混合型的缓存设计方案的根本思想是当某一缓存块( c a c h eb l o c k ) 被替换时 如其他缓存模块( c a c h eb a n k ) 中存在尚未使用的块( b l o c k ) ，则将其放置到 其他缓存块中，从而实现命中延迟与缺失率的折衷r 7 1 。但该方案需要复杂的缓 存一致性协议以及集中的目录结构来记录缓存块在缓存中的分布，增加了硬件 实现的复杂度，同时集中式控制结构的存在也导致该方案的可扩展性较差。 牺牲复制( v i c t i mr e p l i c a t i o n ) 是一种缓存管理策略，该策略试图将一级 缓存中由于容量缺失( c a p a c i t ym i s s ) 或者冲突缺失( c o n f l i c tm i s s ) 而被替换 出的缓存块放置在局部的二级缓存模块中【8 】。逻辑上来看，局部的二级缓存模 块成为对应一级缓存的牺牲缓冲区( v i c t i m sb u f f e r ) ，当一级缓存再次访问该 缓存块时可以快速访问。该方案的弊端在于上下两级缓存之间没有包含关系 ( i n c l u s i o np r o p e r t y ) ，因此将导致缓存一致性协议的复杂。另外，该方案的设 计还要求一级缓存在替换某个块的时候需要遍历其局部的二级缓存标记以查找 是否存在空闲的位置存放该块；而在每次一级缓存访问发生缺失的时候也需要 遍历局部的二级缓存标记，影响缓存访问时间的同时具有较高的能耗。 c m p - n u r a p i d ( n o n - u n i f o r ma c c e s sw i t hr e p l a c e m e n ta n dp l a c e m e n tu s i n g d i s t a n c ea s s o c i a t i v i t y ) 也是一种混合型缓存设计方案，该方案采取了缓存标记 部件( t a g ) 独占，数据存放部件共享的缓存硬件结构，并提出在局部二级缓 存块被完全占用而邻居缓存依然有空余的情况下将数据存放在邻居缓存模块中 【9 1 。该方案对硬件的改动较大，控制缓存块复制的算法复杂度高。同时，该方 案的一致性协议很大程度上依赖于广播，因此其采用了总线结构作为片上互连 网络，系统可扩展性较差。 数据迁移的方案是解决n u c a 缓存平均访问命中延迟的另一思路，该方案 将某个处理核心经常访问的数据复制到距离其较近的缓存模块中，从而减少 n u c a 缓存的平均访问延趔1 0 】。但当多个处理核心存在共享数据时，它们对共 享数据的访问将产生“乒乓 效应，使得数据在不同的缓存模块中来回移动， 数据最终将分布在请求者中间的位置，无法实现数据迁移方案的设计初衷。 8 第二章缓存设计空间分析及研究现状 第四节本章小结 内存墙是处理器性能提高的首要限制因素，层次化的存储结构是降低内存 墙效应的主要方法之一。本章介绍了缓存系统在层次化存储结构中的重要地位， 讨论了缓存设计目标之间的优先关系。通过对共享型和独占型两种c m p 二级 缓存系统的基本设计方法优缺点的比较分析发现，共享型缓存设计具有较低的 缺失率，解决了主存储器访问的带宽需求，避免了较大的主存储器访问延迟导 致的处理器等待，是主流商业处理器普遍采用的缓存设计。而n u c a 缓存系统 的提出进一步解决了共享型缓存设计的片上缓存带宽问题。但n u c a 缓存的访 问延迟却受到被访问数据的分布、片上网络拥塞情况等多个因素限制，本章最 后介绍了针对n u c a 缓存系统降低平均访问命中延迟的研究现状，并分析了这 些方案的优缺点。 9 第三章c a l o s p s 方案系统框架设计 第三章c a l o s p s 方案系统框架设计 操作系统中的进程调度器根据调度算法将c p u 资源分派给系统环境中的 就绪进程【1 8 】，实现c p u 资源在多道程序或多个用户之间的共享。调度器的设 计目标主要包括提高系统的吞吐率，实现实时应用与用户的及时交互。 在采用n u c a 缓存设计的c m p 系统环境中，处理核心与各个缓存模块之 间的拓扑距离是不同的。因此，进程在不同处理核心上执行时访问缓存的平均 命中时间是不同的。针对c m p 系统的这一特点，本章提出一种基于进程调度 降低n u c a 缓存平均访问命中时间( c a c h ea c c e s sl a t e n c yo p t i m i z a t i o ns c h e m e b a s e do np r o c e s ss c h e d u l i n g ，c a l o s p s ) 的方案。c a l o s p s 方案对现有软硬件 环境的改动主要包含两个方面。首先，在c m p 系统的每个二级缓存模块中增 加硬件计数器向量，记录每个进程对不同缓存模块的访问规律：其次，在进程 调度时，根据进程对不同缓存模块的访问规律，将进程调度到距离其经常访问 的缓存模块较近的处理核心上执行。 c a l o s p s 方案降低了处理核心访问缓存的平均命中访问延迟，提高了处理 核心的执行效率。同时，由于被访问的数据在片上网络中传递的拓扑距离减少， 降低了对片上网络带宽的需求。 第一节n u c a 缓存设计面i 临的主要问题 c i v i p 系统中集成了多个处理核心，不同处理核心并行的执行各自的线程， 有利于开发线程级并行性，成为今后处理器发展的趋势。采用n u c a 实现的共 享型缓存可以提供较大的片上有效容量和带宽，因此可以有效的减少片内片外 的数据通信，降低对内存带宽的压力，提高整体系统性能。图3 1 给出了采用 n u c a 缓存设计的c m p 系统结构简图。 l o 第三章c a l o s p s 方案系统框架设计 图3l 采用n u c a 缓存设计的c m p 系统结构简图 图3 1 给出了采用m e s h 作为互连网络拓扑结构，包含有十六个处理核心的 c m p 系统结构示意图。在上图中，每个处理核心包括一个计算核心及其独有的 一级缓存。二级缓存共享地址空间，但是物理上由十六个缓存模块( c a c h eb a n k ) 组成，每个缓存模块具有独立的缓存控制器。处理核心要访问的数据如果在二 级缓存中，那么该数据根据其地址将被唯一的映射在某一个缓存模块中。 当某个处理核心频繁访问距其较近的缓存模块时( 如图31 中蓝色连接标 示) ，平均访问命中延迟较低；当某个处理核心频繁访问距其较远的缓存模块 时( 如图31 中红色连接标示) ，平均访问命中延迟较高，处理核心需要经常 等待，此时c m p 系统的整体执行效率较低。优化n u c a 实现的共享型缓存的 平均访问延迟是其面临的主要问题。 数据在缓存模块中的具体分布由数据地址决定。而不同的应用具有不同的 访存模式和规律。因此降低n u c a 实现共享型缓存的平均访问命中延迟的方 案必须考虑到具体应用的影响。 习 第三章c a l o s p s 方案系统框架设计 第二节c a l o s p s 系统框架介绍 采用n u c a 实现的缓存系统具有较高的片上有效容量和带宽，但其平均访 问命中延迟与被访问数据在不同缓存模块中的分布直接相关。本文提出的 c a l o s p s 方案通过动态发掘进程执行过程中对缓存模块的访问规律，从而优化 共享型缓存的访问延迟。图3 2 给出了c a l o s p s 方案的对系统原有的进程调度 及迁移方案所做改进的示意图。 厂 、 应用层( 应用程序 ) 伞 操作系统层 ( 进程描述符1 卜叫 调度模块 ) 伞 硬件层 ( 缓存访问规律收集模块) 。 图3 2c a l o s p s 框架改动示意图 如图3 2 所示，c a l o s p s 方案对已有进程调度框架的改动主要在硬件层和 操作系统层。c a l o s p s 方案在硬件层增加了缓存访问规律收集模块，该模块负 责收集进程对不同缓存模块的访问规律；在操作系统层，c a l o s p s 方案首先对 描述进程的数据结构( 进程描述符) 进行相应的改动，添加适当的数据结构以 记录该进程对不同缓存模块的访问频率，从而挖掘进程对不同缓存模块的访问 规律。同时，操作系统中的调度模块也需要针对缓存优化进行适当的修改，使 其可以针对进程对不同缓存模块的访问规律进行调度。 在应用层的程序运行过程中，当其访问一级缓存没有命中时需要访问二级 缓存以获取相应的数据。此时，缓存访问规律收集模块中的硬件计数器记录该 进程对不同缓存模块的访问次数，并在进程切换的时候将硬件计数器中记录的 访问次数保存在当前进程的描述符中。当新增的针对缓存优化的调度模块被定 时器中断调用时，调度器对系统范围内的缓存访问规律符合预定特征的进程根 据调度算法进行调度，完成这些进程与处理核心之间的重新映射。调度算法的 设计目标是将进程调度到距离其经常访问缓存较近的处理核心上执行，以降低 进程执行过程中对缓存模块访问的平均访问命中延迟。 1 2 第三章c a l o s p s 方案系统框架设计 c a l o s p s 方案在应用程序执行过程中动态收集其对不同缓存模块的访问 规律，根据其对不同缓存模块的访问频率进行进程调度，并以此来降低缓存访 问的平均访问命中延迟。c a l o s p s 方案与现有方案嘲p 】【1 0 l 相比，对底层硬件的 改动小，可以动态的适应应用对缓存系统的需求。同时。该方案不依赖于具体 的硬件或者特定的缓存一致性模型，可扩展性较好。 3 2 1 缓存访问规律收集模块 缓存访问规律收集模块参考了现代处理器如i n t e il t a n i u m 处理器的设计【”1 通过添加硬件计数器向量的方式实现。图3 3 给出了增加缓存访问规律收集模 块后的c m p 结构示意图。 图3 3c a l o s p s 方案中c m p 物理结构示意图 维数与处理核心数目 相同的计数器向量 如图所示，缓存规律收集模块在每个二级缓存模块控制器中添加了一个硬 件计数器向量，每个硬件计数器向量的维数与c m p 中的处理核心数目相同， 第三章c a l o s p s 方案系统框架设计 假设其标号为0 n 1 。某个缓存模块计数向量中标号为i 的计数器用于记录c m p 系统中标号为i 的处理核心当前正在执行的进程对该缓存模块的访问次数。 为了记录进程对不同二级缓存模块的访问次数，操作系统中描述进程的数 据结构进程描述符也需要进行相应的修改。具体的做法是在进程描述符中增加 一个长度与系统中二级缓存模块数目相等的向量。某个进程描述符新增向量中 标号为k 的元素用于记录该进程对c m p 系统中标号为k 的缓存模块的访问次 数。 在调度过程中发生进程上下文切换( c o n t e x ts w i t c h ) 时，将要被挂起的进 程从各个缓存模块的硬件计数器中收集它对不同缓存模块的访问次数，并将其 对不同缓存模块的访问计数向量保存到其进程描述符中，然后该进程被加入到 等待队列中；被选定为下一时刻执行的进程则将其进程描述符中的缓存访问记 录向量中的值恢复到对应的硬件计数器中。前述的缓存访问模块的工作机制可 以使c m p 系统用较少的硬件代价实现对所有进程访问缓存模块规律的记录及 发掘。新添加的计数器用于记录进程对不同缓存模块的访问次数，而进程访问 缓存的规律可能跟其执行过程中所处的具体阶段直接相关，具有较强的动态性。 因此，当缓存调度模块利用进程描述符中的缓存访问信息对进程调度后，进程 描述符中记录的缓存访问信息被重置。 3 2 2 调度模块 1 现有进程调度方案 进程调度是多任务操作系统的关键部分，决定着进程与处理器资源之间的 动态映射关系。在单核处理器中，进程到处理器映射关系反映的是哪个进程得 到处理器资源，从而可以执行其指令；在c m p 环境中，这种映射关系在反映 哪个进程得到处理器资源的同时还需要决定进程得到的是哪一个处理核心。 l i n u x 操作系统中使用就绪进程队列数据结构来描述系统中可以调度的进 程。对s m p 或者c m p 这样含有多个处理部件的系统而言，不同内核版本中进 程调度的实现具有较大的区别。在l i n u x2 4 内核中，就绪进程队列是一个所有 处理部件共享的全局数据结构。调度器对就绪进程队列的任何操作都将因全局 自旋锁而导致处理核心之间的等待，使得就绪进程队列成为明显的瓶颈。l i n u x 2 6 内核中重新设计了该数据结构，每个处理核心维护各自的就绪进程队列，解 决了全局集中式数据结构的瓶颈效应。 1 4 第三苹c a l o s p s 方案系统框架设计 在l i n u x2 6 内核的调度过程中，调度器首先找到当前处理核心的就绪进程 队列里第一个非空的就绪进程链表，并从该链表中选择第一个进程作为下一个 时刻将要运行的进程。如果被选择的进程跟当前处理核心中正在执行的进程不 同，调度函数进行进程的上下文切换，处理核心开始执行被选定的进程。在多 处理核心的硬件环境下，多个就绪进程队列可能存在负载不均衡的情况，从而 影响系统的整体吞吐率。l i n u x2 6 内核中通过l o a db a l a n c e o 函数调用实现处理 核心之间的负载均衡。该函数在两种情况下被调用：一是某个就绪进程队列为 空时；二是在系统忙( 或闲) 时由定时器每2 0 0 m s ( 或l m s ) 调用一次。 从逻辑上看，l i n u x2 6 内核