多核处理器共享资源管理技术研究.pdf

《多核处理器共享资源管理技术研究.pdf》由会员分享，可在线阅读，更多相关《多核处理器共享资源管理技术研究.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、龙源期刊网 http:/ 多核处理器共享资源管理技术研究 作者：严杰俊,黄皓 来源：电脑知识与技术2011 年第 13 期 摘要：现代多核处理器结构的设计使得集成在同一块芯片上的多个执行核共享各种硬件资源，如片上最后一级 Cache、内存控制器、前端总线以及硬件预取单元等，而多线程的并行执行导致核与核之间共享资源的争用，造成系统整体性能的下降，如何有效地解决多核共享资源冲突来提升系统的整体性能以及应用程序的服务质量成为当今研究的热点。文章首先概要介绍当前主流的多核处理器，然后提出了多核体系结构下共享资源管理面临的挑战，接着分析了降低共享资源争用的策略方法：操作系统调度技术、资源划分技术，最后给

2、出了多核处理器共享资源管理技术可能的发展方向。关键词：多核；共享资源争用；线程调度；资源划分 中图法分类号 TP316 文献标识码：A文章编号：1009-3044(2011)13-3159-03 A Survey of Managing Contention for Shared Resources on Multicore Processors YAN Jie-jun,HUANG Hao (National Key Laboratory for Novel Software,Department of Computer Science and Technology,Nanjing Unive

3、rsity,Nanjing 210093,China)Abstract:Modern multi-core processors are designed with multiple cores integrated on a chip,one common feature of these multi-core chips is resources sharing among sibling cores that sit on the same chip,such as the last level Cache,memory controller,front-side bus and pre

4、fetching hardware.The parallel execution of multiple threads leading to the contention of shared resources,causing a degradation of the system performance.Therefore,How to solve the contention for shared resources effectively and improve overall system performance and quality of service becomes an a

5、ctive research area.In this paper,we introduce the mainstream multi-core processors and the challenge of managing contention for shared resources firstly,and then we analyzed the key technologies of shared resources management:operating system scheduling and shared resource partitioning;at last,we m

6、ake the conclusion of our paper and discuss the future of shared resources management technologies.Key words:multicore;shared resources contention;thread schedule;resource partition 1 概述 多核处理器指的是在一个芯片上集成了多个计算核心的处理器，相比于单核，多核处理器优势明显：多核处理器每个核心工作在较低的频率上，在通过并行运行来提高整体性能的同时有效的解决了散热问题；同一芯片上的多个核心互联线路极短，有利于降低

7、通信延迟，提高数龙源期刊网 http:/ 据传送带宽；多核处理器有利于指令级并行(ILP,Instruction Level Parallel)和线程级并行(TLP,Thread Level Parallel),充分挖掘程序潜在的并行性。当今主流的多核处理器采用片上多处理器结构(CMP,Chip Multi-Processor)，而更高端的则为片上多核多线程结构(CMT，CMP of Multi-threading)，它是同时多线程结构(SMT,Simultaneous Multi-Thread)以及 CMP 结构的结合体，性能非常卓越。现在高端的多核处理器一般都采用 CMT结构，如 IBM的

8、 Power5、Intel的Montecito 等，图 1给出了 CMP 以及 CMT 多核处理器体系结构图。2 多核共享资源管理面临的挑战 为了最大化利用硬件资源，现代多核体系结构共享很多硬件资源，如最后一级 Cache，内存控制器，硬件预取单元等，但是并行运行的线程对共享资源的争用会造成系统整体性能的下降，这就给操作系统设计者和微处理器设计者带来了挑战。首先，当今主流的操作系统（比如 Linux）缺乏对应用程序关于片上共享资源的使用情况的感知，对多核处理器当做黑盒对待，对片上资源如何在相互竞争的线程之间分配缺乏有效的控制；而且，目前操作系统缺乏实际有效的机制管理线程运行时使用的片上资源，大

9、多数的管理技术存在额外的开销或者需要特殊硬件的支持，并不实用。其次，多核处理器的 Cache 层次比较复杂，其中有每个核私有的 L1 Cache，有多个核共享或私有的 L2 Cache，甚至更多的核共享的 L3 Cache,共享 Cache 可以提高系统资源利用率，但是标准的 Cache 替换算法 LRU 并不能区分各个进程的访问，可能导致某个进程的 Cache 失效会替换掉其他进程的 Cache 块，影响系统的性能，微处理器的设计者需要从硬件的角度来解决Cache 的智能划分问题。3 多核处理器共享资源管理技术 多核处理器共享资源管理技术主要分为操作系统调度技术和硬件采用的资源划分技术。操作

10、系统调度技术通过修改操作系统的调度算法，将线程合理地分派到处理器核上去，优化共享资源的使用；资源划分技术通过修改硬件机制，使得硬件智能地在核之间自动分配共享资源（比如 Cache），从而达到优化目的。3.1 操作系统调度技术 当前主流操作系统(Linux)针对多核架构的调度策略主要考虑两点：负载平衡和 Cache的亲和力。负载平衡尝试在多个处理器之间平均地分配任务，如果出现失衡的情况，调度器就会尝试从负载较重的处理器将进程迁移到负载较轻的处理器上，然而任务迁移会带来相关的开销：当进程被迁移到另一个处理器上，原有的 Cache则会失效，影响性能，Linux最新的调度器考虑了 Cache 的亲和性

11、，在需要进行任务迁移时，优先考虑和当前处理器共享同一层 Cache的处理器，减少 Cache失效带来的性能开销。然而，现有操作系统的调度器都没有考虑到线程并行运行带来的共享资源争用问题。龙源期刊网 http:/ 学术界针对多核架构下操作系统调度的研究主要致力于对线程(进程)进行协同调度以减少对共享资源的争用。这样的调度器通常由两部分组成：线程分类机制和线程调度策略。做出调度决策所使用的信息，这里称为分类机制。分类机制决定了选择进程的哪些参数，以及由这些参数评估多个程序共享使用资源效果的方法；调度策略则根据线程分类机制所提供了信息将线程分配到各个核上去运行。3.1.1 线程分类机制 影响调度性能

12、的因素很多，不同的研究者在分析调度性能时考虑哪些是影响调度性能的主要因素的观点和侧重点不同，形成不同的评估模型。线程分类机制则负责建立这些评估模型,通过模型提供的信息和方法指导调度。对于任何的分类机制而言，需要提供一些应用程序的行为特征数据供其分析。描述程序 Cache行为的内存复用模式，也称作栈距离模式2(SDP，Stack Distance Profile),是以下将要阐述各种分类机制的主要参数。对一个内存块的连续两次访问之间访问其他内存块的次数 K称为 stack distance（或 reuse distance复用距离），假设 Cache为 N 路组相联，并使用 LRU（least

13、recently used）替换算法，那么如果 KN-1 则意味着 Cache失效，因此 SDP 可以很好的估计 Cache的利用情况。以下给出当今主流的线程分类机制，这些机制根据每个程序的自身行为去估算共享 Cache系统的整体行为。1）SDC 模型 Chandra1于 2005 年提出了 SDC(Stack Distance Competition)模型，SDC通过建模分析得到多个应用程序争用共享 Cache 的情况下各自的 Cache 行为(各自的 SDP)。算法的主体思想是通过各个程序独享 Cache时的 SDP 构造出一个合并后的系统整体 SDP,然后使用各个程序在总的 SDP 项中

14、所占的比例计算其占用有效 Cache 路数，得到程序在争用共享 Cache情况下的实际的 SDP。2）Animal模型 Animal模型3根据程序的内存访问行为将其分为四大类(turtle,sheep,rabbit,devil)，然后考虑这些类之间的组合对性能的影响。文章使用 Cache访问次数、程序单独运行时的 Cache失效次数以及保持失效率在定值以下所需的 Cache大小作为分类的依据。该分类算法只考虑不同类程序的相互影响问题，同类程序之间的影响并未特别考虑。3）Pain 模型 Zhuravlev 4提出了 pain 模型。Pain 主要考虑了两个因素：Cache sensitivity

15、和 Cache intensity。Cache sensitivity 用于衡量应用程序由于 Cache空间被他程序争用造成的影响；Cache intensity用于衡量一个程序会通过争用 Cache空间对其他程序造成的影响。通过这两个因素，龙源期刊网 http:/ 作者估计程序共享 Cache时带来的 pain，然后计算系统整体的 pain，作为衡量系统整体性能的指标。4）Miss Rate 很多的研究工作使用简单的 Cache统计信息作为系统的性能指标，典型的指标如系统的总体 Cache 失效次数，系统的总体 Cache失效率（失效次数除以内存访问次数），等。虽然这些指标简单直接，但是同样

16、可以用来指导调度。3.1.2 线程调度策略 线程调度策略根据分类机制提供的线程协同运行时的信息选择一个合理的调度方案将线程分配到核上运行。Fedorova5提出了平衡集(balance set scheduling)调度算法。算法从系统中可运行的线程集合中构造出多个线程组，每个线程组中线程的数目和可用的硬件线程数目相等，系统以线程组为单位调度运行。平衡集调度策略保证了系统拥有最少的 Cache失效率，然而算法倾向于选择Cache 需求度较低的线程，Cache需求度较高的线程被调度的概率则相应的下降，也就是说，算法提升性能的同时牺牲了系统的公平性。Knauerhase6通过保持系统整体 Cach

17、e失效次数最低进行调度。文章通过实验发现将每个时钟周期的 Cache 失效次数作为权重，并且使用每个线程上个时间片的权重作为调度的参考依据最合适。CPU可执行队列线程的权重之和为该 CPU权重，调度策略尽量会平衡每个 CPU的权重。3.2 共享资源划分技术 共享资源划分技术通过将不同核心使用的共享资源完全分开来，并合理的控制各个核心使用的共享资源的大小，来提供服务质量 QoS，或者最大化系统效率。当前的共享资源划分一般是对 Cache 进行划分的。多核系统中由于多个核心共享 Cache，这些核心各自占用多大一部分 Cache 对于系统性能影响会很大。Cache 划分就是通过软件或者硬件机制，找

18、到一种在处理器核之间合理分配 Cache 的方法，从而提高系统的性能。3.2.1 考虑性能的划分 Qureshi 7提出，在 CPU上增加一个硬件，监控每个核上程序的 SDP，然后另一个硬件单元根据 SDP 自动的在核之间分配给相应数量的 Cache 路，目标是使得分配后由总的 miss数量最低。结果显示，对于带全加速比低的程序，该方法能带来很好的性能提升，明显提高了系统吞吐量。不同于一般基于硬件的 Cache划分，Tam8提出了一种基于软件的 Cache划分算法，利用 OS 的页面分配机制来控制应用程序使用 Cache 的大小，在系统 Cache采用组相连策略的龙源期刊网 http:/ 情况

19、下，通过给页面着色，使得页面分组，每次应用进程需要申请页面的时候，只分配同一种颜色的页面给他，那么即使在 Cache 中丢失，硬件也只会替换掉本进程以前的 Cache，而不会影响其他进程的 Cache。实验结果表明，通过对 L2 进行细分割，可以提高整个系统 17%的效率（通过测量 IPC）。3.2.2 考虑公平的划分 一般以优化系统吞吐量来提升系统性能的多核体系结构下的线程调度算法有利于高 IPC 的线程，导致这些线程被调度大概率大大增加，从而造成系统的不公平性。文章9提出了基于公平性考虑的多核体系结构下的共享 Cache划分技术。作者提出了五个衡量共享 Cache 划分是否公平的度量指标，

20、使用这些度量方法，文章提出了静态和动态的两种 L2 Cache划分算法，静态的 Cache划分必须离线收集数据，优点在于可以避免 Cache抖动，然而缺点在于 Cache 替换算法必须为 LRU；动态的 Cache划分算法对 Cache 替换算法没有限制，但是需要在 Cache中加入额外的计数器统计 Cache失效情况。实验表明，采用公平性优化策略后，系统的公平性平均提高四倍，而吞吐率提升 15%。文章10指出，由于需要测量线程间的干扰程度以及对硬件共享资源采取强制性公平策略，目前存储系统公平性的解决机制过于复杂。文章提出了一个新颖的公平性机制，称作动态失效处理架构（DMHA），DMHA的关键

21、特征在于它可以在运行时改变 L1 Cache里的失效状态保持寄存器(MSHRs),这些寄存器决定了 Cache不被阻塞的情况下可以承受的最大失效数，通过在运行时根据优先级给不同的线程分配相应比例的 MSHR来控制线程的失效带宽，从而实现对共享内存系统的公平划分。3.2.3 考虑服务质量的划分 不可控的共享资源的争用引发了人们对应用程序服务质量的关注。文章11提出了如何管理未来多核系统资源的一个想法。通过丰富系统软件和硬件之间的接口来管理多核系统的资源。这些接口允许应用进程和系统软件显式地管理多核系统中所有的共享资源。作者将策略和机制分离，通过将进程的资源申请要求转变为虚拟私有机器(Virtua

22、l Private Machine，VPM)的申请，给不同应用要求的进程分配不同的资源，使得不同的进程能够满足不同的要求,保证了应用程序服务的质量。Moreto 12提出了一个 FlexDCP 框架，通过不同的缓存配置直接估计应用的性能。这使得操作系统能够将服务质量(QoS)的需求转换成对资源分配的需求，使得操作系统可以满足不同的 QoS要求，而不需要知道体系结构的内部信息。实验表明 FlexDCP 能够使得 94%的应用可以得到最好的性能，平均只有 1.48%的应用不能满足性能要求。4 结束语 龙源期刊网 http:/ 多核体系结构下的共享资源管理技术是当今研究的一大热点。本文首先概要介绍当

23、前主流的多核处理器，然后提出了多核体系结构下共享资源管理面临的挑战，最后分析了当今主流的降低共享资源争用的策略方法：操作系统调度技术、共享资源划分技术。当前对多核处理器共享资源的研究主要集中于最后一级 Cache 争用的解决方案，然而多核处理器除了共享 Cache之外，还共享诸如前端总线，内存控制器的硬件资源，因此，本文认为，应当在继续深入研究更为有效的 Cache管理技术的同时兼顾研究其他共享资源争用的解决策略。参考文献：1Chandra D,Guo F,Kim S,Solihin Y.Predicting Inter-Thread Cache Contention on a Chip Mu

24、lti-Processor ArchitectureC/HPCA05:Proceedings of the 11th International Symposium on High-Performance Computer Architecture,2005:340-351.2 Gecsei J,Slutz D R,Traiger I L.Evaluation techniques for storage hierarchiesJ.IBM System Journal,1970.3 Y Xie,Loh G.Dynamic Classification of Program Memory Beh

25、aviors in CMPsC.Proceedings of CMP-MSI,held in conjunction withISCA-35,2008.4 Zhuravlev S.Addressing Shared Resource Contention in Multicore Processors via SchedulingC.Proceedings of the 15th edition of ASPLOS on Architectural support for programming languages and operating systems,2010.5 Fedorova A

26、,Seltzer M,Small C,et al.Performance of multithreaded chip multiprocessors and implications for operating system designC.Proceedings of the annual conference on USENIX Annual Technical Conference,2005.6 Knauerhase R,Brett P,Hohlt B,et al.Using OS Observations to Improve Performance in Multicore Syst

27、emsJ.IEEE Micro,2008,28(3):54-66.7 Qureshi M K,PattY N.Utility-Based Cache Partitioning:A Low-Overhead,High-Performance,Runtime Mechanism to Partition Shared CachesC.Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture,2006:423-432.8 Tam D.Managing shared L2 Caches on

28、 multicore systems in softwareZ.Workshop on the Interaction between Operating Systems and Computer Architecture,2007.9 Kim S,Chandra D,Solihin Y.Fair Cache Sharing and Partitioning in a Chip Multiprocessor ArchitectureC.Proceedings of the 13th International Conference on Parallel Architecture and Co

29、mpilation Techniques,2004:111-122.龙源期刊网 http:/ 10 Jahre M,Natvig L.A Light-Weight Fairness Mechanism for Chip Multiprocessor Memory SystemsC.Proceedings of the 6th ACM Conference on Computing Frontiers,2009:1-10.11 Nesbit J K.A Framework for Managing Multicore ResourcesJ.IEEE May-June,2008:6-16.12 Moreto M.FlexDCP:a QoS framework for CMP architectures.ACM SIGOPS Operating SystemsJ.2009,43(2):86-95.注：本文中所涉及到的图表、注解、公式等内容请以 PDF格式阅读原文