（计算机科学与技术专业论文）芯片多线程处理器线程调度的性能测试与优化研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着近年来多核技术的迅速发展和推广，从服务器到个人计算机都可以获得 日益丰富的并行计算资源。但是，多核处理器的并行性并不肯定会带来性能的提 高，反而可能会加剧多线程资源争用问题。因此，如何合理有效地对线程进行调 度，提高系统的整体性能，成为多核应用的一个重要研究问题。在各种多核处理 器中，较晚出现的芯片多线程处理器正在成为主流，这得益于它的高性能和低功 耗特点。本论文研究的主题就是基于芯片多线程处理器的线程调度优化，实验平 台是配备两路u i t r a s p a r ct 2 处理器的s u nt 51 4 0 服务器，运行操作系统为s o l a r i s 1 0 。 本文首先通过测试的方式研究实验平台的多线程调度性能特点。在利用改进 的p i n g p o n g 多线程基准测试程序对实验平台进行了多种负载和调度方式的测试 之后，分析总结出芯片多线程处理器的线程调度性能规律。本文发现c a c h e 资源 是限制处理器多线程性能的主要因素。 基于测试得到的结论，本文设计了一种启发式调度优化算法。这个算法是基 于线程协同亲和度，这是本文定义的一种用于衡量线程协同执行性能的值。算法 的思想是，利用性能采样计算获得的亲和度调度矩阵，把多线程调度问题转化为 资源划分问题，以整数规划问题的解决思路设计优化算法，最后获得预测最优的 资源划分方案。为了实现这一算法，本文设计了一种用户级的应用线程调度框架。 它可以对配置运行的若干应用负载线程在一定的资源范围内进行动态调度优化。 它首先通过对协同运行的线程进行性能采样，获得一个亲和度调度矩阵，然后将 这个矩阵作为所设计的优化算法的输入，从而获得预测最优的线程调度方案，最 后按照这个方案进行线程绑定以实现调度。框架在适当的时候重启采样，使得动 态调度优化工作在性能采样、调度优化和调度实施三个阶段间循环持续。 本文在实验平台上实现了框架和算法，对配置好的多个应用负载进行调度优 化实验，并取得了一定的优化效果。最后，本文分析了所设计的调度框架和算法 的优缺点，并对下一步的研究工作提出了一些设想。 主题词：芯片多线程c a c h e 失效多核调度资源分配 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n da p p l y i n go fm u l t i c o r et e c h n o l o g y ，b o t hs e r v e r s a n dp e r s o n a lc o m p u t e r sc o u l da c h i e v em o r ea n dm o r ea b u n d a n tp a r a l l e lc o m p u t i n g r e s o u r c e s h o w e v e r ，t h ep a r a l l e l i s mo fm u l t i c o r ep r o c e s s o r sd i d n tc e r t a i n l yb r i n gt h e i m p r o v e m e n to fp e r f o r m a n c e ，b u tw o u l dm a k et h er e s o u r c ec o n t e n t i o np r o b l e mm o r e i n t e n s e t h e r e f o r e ，h o wt os c h e d u l et h r e a d sr a t i o n a l l ya n de f f e c t i v e l y ，i tb e c o m e sa n i m p o r t a n tr e s e a r c hi s s u ei nm u l t i c o r ea p p l i c a t i o n s a m o n ga l lt h ek i n d so fm u l t i c o r e p r o c e s s o r s ，t h ey o u n gc h i pm u l t i - t h r e a d e dp r o c e s s o ri sb e c o m i n gm a i n s t r e a mb e c a u s eo f i t sh i 曲p e r f o r m a n c ea n dl o wp o w e rc o s t i nt h i sp a p e r , t h es u b j e c tr e s e a r c h e di st h e o p t i m i z a t i o no ft h r e a ds c h e d u l i n gb a s e do nt h ec h i pm u l t i - t h r e a d e dp r o c e s s o r t h i s e x p e r i m e n t a lp l a t f o r mi st h es u nt 5 14 0s e r v e rw i t ht w ou l t r a s p a r ct 2p r o c e s s o r s ， w i t l ls o l a r i s10a si t so p e r a t i n gs y s t e m i nt h eu s eo fi m p r o v e dp i n g - - p o n gm u l t i t h r e a d e db e n c h m a r kp r o g r a mt o t e s t p l a t f o r m ，av a r i e t yo fl o a dt y p e sa n ds c h e d u l e sw e r et e s t e d ，a n dt h i sp a p e ra n a l y z e da n d s u m m a r i z e dt h em u l t i - t h r e a d e ds c h e d u l i n gp e r f o r m a n c ec h a r a c t e r i s t i c so nt h e c h i p m u l t i t h r e a d i n gp r o c e s s o r n l i sp a p e rf o u n dt h a tt h ec a c h er e s o u r c ei st h em a i nf a c t o rt o l i m i tt h em u l t i t h r e a d e dp e r f o r m a n c eo ft h ep r o c e s s o r s b a s e do nt h ec o n c l u s i o no ft h ep i n g p o n gt e s t s ，t h i sp a p e rd e s i g n e dah e u r i s t i c s c h e d u l i n go p t i m i z a t i o na l g o r i t h m n l ei d e ao ft h i sa l g o r i t h mi sb a s e do nt h ea f f i n i t y s c h e d u l i n g m a t r i xo b t a i n e db ys a m p l i n g p h a s e ，t r a n s f e r r i n gt h e m u l t i t h r e a d e d s c h e d u l i n gp r o b l e mi n t oar e s o u r c ep a r t i t i o n i n gp r o b l e m ，u s i n gi n t e g e rp r o g r a m m i n g i d e a st od e s i g nt h eo p t i m i z a t i o na l g o r i t h m ，t od e r i v et h ep r e d i c t e do p t i m a ld i v i s i o no f r e s o u r c e s i no r d e rt oi m p l e m e n tt h i sa l g o r i t h m ，t h i sp a p e rd e s i g n e dau s e r - l e v e lt h r e a d s c h e d u l i n ga p p l i c a t i o nf r a m e w o r k w i t hac e r t a i nr e s o u r c e sq u o t a , t h i sf r a m e w o r k c a r r i e so u td y n a m i cs c h e d u l i n go p t i m i z a t i o nf o rt h ec o n f i g u r e dw o r k l o a da p p l i c a t i o n s r u n n i n go n w 池t h ew o r k l o a dt h r e a d sr u n n i n gi np a i r so nac o r e ，t h ef r a m e w o r k s a m p l e st h ep e r f o r m a n c ed a t ao ft h et h r e a dp a i r s ，a n dt h e np r o d u c e sa na f f i n i t y s c h e d u l i n gm a t r i x t h e n ，i tu s e st h ea f f i n i t ys c h e d u l i n gm a t r i xa si n p u tt ot h ea l g o r i t h m t og e n e r a t et h ep r e d i c t e do p t i m a lt h r e a ds c h e d u l i n gp o l i c y ，a n da tl a s tc o n t r o l st h e t h r e a d st os c h e d u l eo nt h ed e s i g n a t e dp r o c e s s o r sw i t ht h r e a d b o u n ds y s t e mc a l l s w i t l l r e s t a r t i n gs a m p l i n ga tt h ea p p r o p r i a t et i m e ，t h ef r a m e w o r kr u n si nac y c l eo ft h r e e p h a s e s ，p e r f o r m a n c es a m p l i n g ，s c h e d u l i n go p t i m i z a t i o n ，a n ds c h e d u l i n gb o u n d ，s ot h a t t h ef r a m e w o r ki m p l e m e n t sc o n t i n u o u sd y n a m i cs c h e d u l i n go p t i m i z a t i o n i nt h i sp a p e r ，t h ef r a m e w o r ka n da l g o r i t h mw a si m p l e m e n t e do nt h ee x p e r i m e n t a l p l a t f o r m ，a n dm a d es c h e d u l i n go p t i m i z a t i o ne x p e r i m e n t so nm u l t i p l ea p p l i c a t i o n sw i t h v a r i o u sc o n f i g u r e dw o r k l o a d ，a n dh a v ea c h i e v e dac e r t a i nd e g r e eo fo p t i m i z a t i o nr e s u l t s f i n a l l y ，t h ep a p e ra n a l y z e dt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ef r a m e w o r ka n d 第i i 页 国防科学技术大学研究生院硕士学位论文 a l g o r i t h m ，a n da d v a n c e dan u m b e ro fi d e a so nf u t u r er e s e a r c hw o r k k e yw o r d s ：c h i pm u l t i t h r e a d e d ( c m t ) ，c a c h em i s s ，m u l t i c o r es c h e d u l e ， r e s o u r c ea s s i g n m e n t 第i i i 页 国防科学技术大学研究生院硕士学位论文 表 表 表 表 1 1 2 3 表5 1 表5 2 表5 3 表5 4 表5 5 表5 6 表目录 他处理器c a c h e 失效与访存延迟参数10 基线测试数据18 私有访存负载测试数据1 9 共享访存负载测试数据2 2 实验负载c a c h e 失效率采样4 8 实验负载平均i p c 采样5 0 a 取不同值的亲和度计算值5 l 实验负载亲和度调度矩阵5 2 实验负载亲和度归一化调度矩阵5 3 线程调度性能实验结果比较5 3 第1 l i 页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1s m t 、c m p 、c m t 体系结构图4 图2 2s m p 系统的调度域6 图2 3c m t 系统的调度域6 图2 4u l t r a s p a r ct 2 处理器体系结构9 图2 4 u 1 t r a s p a r ct 2 处理器内核结构1 0 图3 1p i n g p o n g 线程运行关系图1 2 图3 2 三线程扩展p i n g p o n g 模型l 3 图3 3 基线测试结果18 图3 4 计算密集型负载测试结果1 9 图3 5 私有只读负载测试结果2 0 图3 6 私有只写负载测试结果2 1 图3 7 私有读写负载测试结果2 1 图3 8 共享只读负载测试结果2 2 图3 9 共享只写负载测试结果2 3 图3 1 0 共享读写负载测试结果2 3 图3 1 1双线程访存负载测试结果2 4 图3 1 2 四线程访存负载测试结果2 5 图4 1基于m r 。p 的线程组划分流程示意图3 5 图5 1 框架工作流程设计3 7 图5 2 框架结构设计3 9 图5 3 处理器结构信息模块4 0 图5 4 应用线程树信息模块4 1 图5 5 实验负载绝对c a c h e 失效率采样4 9 图5 6 实验负载相对c a c h e 失效率采样4 9 图5 7 实验负载平均i p c 采样5 1 图5 8 取2 - - 0 1 时的亲和度散点分布图5 2 图5 9 调度实验平均i p c 比较5 4 图5 1 0 调度实验平均l 1 数据c a c h e 失效率比较5 4 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 茎压垒缮猩处垄墨缮猩溷廑鳗性能泅这生盆丝珏究 学位论文作者签名： 蕉歪缓1 日期：加。年l2 月弓1 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：芷兰垒绫猩处垄墨线猩通廑鲍性能到达生佐毡盈究 学位论文作者签名： 作者指导教师签名： 日期：? 乡7 年2 月岁日 日期u 1 年1 乙月1 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 自计算机诞生以来，c p u 性能的提升一直是硬件厂商追求的目标，而如何尽 可能提高对c p u 性能的利用效率也是软件设计者和使用者致力于研究的问题。近 十年来，传统的处理器研发方式已经无法显著提高处理器的性能，主要原因有三 点：风冷芯片的最大功耗和散热能力；指令级并行( i l p ) 的发掘空间；访存时延 【1 1 。处理器指令执行时延与访存时延之间的差距导致处理器利用率严重不足，这种 差距还在以每年5 0 的速度递增【2 】。当前流行的大多数商业工作负载，如数据库、 w e b 服务以及在线事务处理，会带来很高的c a c h e 失效率( c a c h em i s sr a t e ) ，浪 费了绝大部分的处理器时钟周期，使执行部件基本处于空闲状态。乱序执行和分 支预测等指令级并行技术虽然可以在一定程度上隐藏l 1c a c h e ( c a c h e ) 失效造成 的短延迟，但是不能缓解l 2c a c h e 失效造成的长延迟。在这种趋势下，随着主要 处理器厂商逐渐调整改变了其发展战略，微体系结构的发展已经迈入线程级并行 ( t l p ，t h r e a dl e v e lp a r a l l e l ) 的时代【3 1 。 但是，处理器的线程并行化并不像以前的速率提升那样能够直接带来应用性 能的提高【4 】，它让软件设计者们不得不面对复杂的、易错的并行计算环境，同时也 带来难以预测的资源争用问题。可能多个线程在多核处理器上的执行效率不会自 动提升，甚至比传统处理器更低【5 】。软件在线程级和进程级上的粗粒度并行性能主 要取决于高效的操作系统调度策略和同步通信机制。因此，基于多核处理器的操 作系统调度已成为现代操作系统的5 大热点问题之一【6 】。 本章首先说明课题的项目背景及意义，然后概括本文的主要工作和创新，并 给出全文的组织结构。 1 1 项目背景及课题意义 随着多核c p u 的出现、高速互连网络的成熟、开源软件的普及以及虚拟化技 术的飞速发展，为自主研制国产高端容错计算机提供了新的机遇。8 6 3 基金资助项 目高端容错计算机就是在这样的背景下提出的。本课题作为项目工作的一个 重要组成部分，具有重要的意义。 高端容错计算机项目的预期目标是自主研制3 2 路高端容错计算机系列产 品和掌握6 4 路高端容错计算机核心技术，2 0 1 0 年在国际同步推出具有先进水平的 3 2 路高端容错计算机系统，系统可用度达到9 9 9 9 9 。项目计划构建采用多路c m t 处理器构成一个提供大规模并行运算和服务环境的容错服务器系统，采用1 6 路6 4 线程的c m t 处理器，达到总体1 0 2 4 个硬件线程的规模。如此大规模的多线程并 第1 页 国防科学技术大学研究生院硕士学位论文 行环境，对于运行其上的操作系统以及应用软件来说，既是丰富的资源，又是对 其性能扩展性和稳定性的挑战。其要求实现大规模多线程的调度支持和优化，支 持3 2 路( 2 0 4 8 个逻辑线程) 的调度与管理。现有操作系统对逻辑c p u 规模的支 持能力均未达到这一级别，且采用传统的线程调度策略无法充分发挥众核处理器 的性能。因此对c m t 处理器多线程调度策略和调度算法提出了严格的要求。 本课题在对当前c m t 处理器线程调度优化技术进行研究的基础上，设计和开 发适用于该项目的性能测试和调度优化模型，以满足大规模多线程运行环境的要 求。 1 2 本文的工作及论文结构 1 2 1 本文的主要工作 本文主要研究和开发c m t 处理器平台的线程调度优化技术，目的是动态预测 最优的线程部署和协同调度方式，以提升系统和负载运行的性能。主要工作包括 以下几点： 1 1 对当前的多线程调度技术进行研究，总结已有的各种多线程处理器平台的 优化技术； 2 ) 设计了改进的p i n g p o n g 基准测试程序，并利用其进行实验测试，分析实 验平台所用的c m t 处理器的多线程调度性能； 3 ) 针对处理器资源争用对线程性能的影响，提出一种线程协同性能指标 亲和度，并基于这个指标设计了一种启发式线程调度优化算法。 4 1 基于所设计的算法，设计实现了一种用户级应用线程调度优化框架，并通 过实验取得了一定的性能优化效果。 在攻读硕士学位期间，以第一作者在计算机工程( 正刊) 发表文章一篇 ( 见本文附录) 。 1 2 2 论文结构 本文作为课题工作的总结，全文共分为六章。 第一章，首先说明项目背景及课题意义，然后概括本文的主要工作，最后给 出文章的组织结构。 第二章，对当前的多核调度优化技术进行研究，包括线程级并行的概念及原 理，多核调度的负载均衡问题，协同调度技术，调度技术的性能评价标准等，为 进一步开发多线程调度优化技术打下基础。 第三章，设计和改进了一种p i n g p o n g 基准测试程序，并在实际的平台上进行 第2 页 国防科学技术大学研究生院硕士学位论文 实验测试，从而对c m t 处理器的多线程调度性能进行分析评价。 第四章，针对单c m t 处理器上的线程调度优化问题，设计了亲和度调度矩阵 以及线程调度优化算法。 第五章，基于上一章设计的算法，设计实现了相关的线程调度框架，并在实 际硬件平台上进行实验，分析结果。 第六章，概括全文，总结课题所做的主要工作及研究成果，并对进一步的研 究进行展望。 第3 页 国防科学技术大学研究生院硕士学位论文 第二章多核调度技术研究 本章对当前的多核调度优化关键技术进行研究，描述了线程级并行技术的原 理及发展，研究了多核调度的负载均衡问题及协同调度技术，并介绍多核调度技 术中相关的性能评价标准，最后描述了课题进行研究和开发的实验平台的体系结 构及其特点。 2 1 多核处理器技术 c p u 多线程并行技术分三类：同时多线程技术( s m t ) 、芯片多处理器技术， 即多核技术( c m p ) ，以及两者的结合芯片多线程技术( c m t ) 。s m t 处理 器、c m p 处理器和c m t 处理器的大致结构如图2 1 所示。 线程执i线程执 行环境 i 行环境 功能部件 l 1 指令 ii l 1 数据 高速缓存l i 高速缓存 l 2 高速缓存 f s b 总线控制器 二亟塑型 c m p 处理嚣 霞1 宴圈i 圈圆 厂磊葡门 i _ j 亟墅巫 c m t 处理器 图2 1s m t 、c m p 、c m t 体系结构图 2 1 1s m t 处理器 s m t 技术【7 】相比传统的单线程处理器，在芯片上集成了多个线程执行环境， 每个线程执行环境包括一套完整的寄存器组，保存一组在线程运行时所需的全部 状态信息。在宏观上单个c p u 芯片内存在多个并行逻辑处理器，它们共享其它所 有的系统资源如执行部件、流水线、高速c a c h e 以及f s b 总线控制器等【8 】。处理 器将这多条线程的指令流交织在一起，把线程级并行转化为了指令级并行。当芯 片内某些线程进行访存操作时，另一些线程仍在运行，这样就避免了流水线停顿， 隐藏了访存延迟，提高了c p u 资源的利用率，从而增加处理器的整体i p c 和效能 出1 1 。 2 1 2c m p 处理器 c m p 技术9 】在一个c p u 芯片中集成多个完整的处理内核，每个处理内核不仅 有各自的线程执行环境，还有各自独立的功能部件、流水线和l 1c a c h e ，因此各 第4 页 国防科学技术大学研究生院硕士学位论文 个内核中的线程不仅是并发的，而且是并行执行的。此外，不同的c m p 实现有不 同的l 2c a c h e 共享方式，可能是所有内核共享一块大尺寸的l 2c a c h e ，也可能是 各个内核集成各自的l 2c a c h e t 2 1 。c m p 相比s m t 能够提供更高的单个线程i p c ， 但是很多系统资源的利用率相比传统的单线程处理器并没有很大提高。在宏观上 单个c p u 芯片的峰值速率是芯片内部所有处理内核的峰值速率之和。 2 1 3c m t 处理器 c m t 技术【1 0 】是指在芯片级采用c m p 技术，并且在内核级采用s m t 技术，实 际上就是在c p u 芯片内集成多套处理内核，而每个内核又具有多套线程执行环境。 在一个c m t 处理器中，多个内核共享l 2c a c h e 以及前端总线控制器等资源；在 每个处理内核中，多个硬件线程则共享核内的功能部件、流水线和l 1c a c h e 等资 源】。c m t 技术兼具s m t 和c m p 技术的优点，使单个处理器的性能得到了显著 的提高。但核内多线程间资源共享和核间资源共享并存，使得基于c m t 处理器的 线程调度问题在面对应用程序的多样性时更趋复杂化，需要进一步研究如何提高 系统实际性能的策略和机制【1 们。i b m 的p o w e r 5 t 12 1 、i n t e l 的m o n t e c i t o t l 3 】、s u n 的 n i a g a r a t l 4 j 以及u l t r a s p a r c t l 5 】都属于c m t 处理器。 2 2 多核调度技术 随着多核处理器硬件技术的发展，多线程在多核处理器上的调度技术逐步成 为研究的热点。下面从负载均衡、协同调度以及多核调度性能评价标准等方向对 多核调度技术的研究进行介绍。 2 2 1 负载均衡 负载均衡目标是在调度域内各调度组承担的负载大致相近，确保不出现某些 调度组的负载特别繁忙，而另一些调度组却处于空闲状态。其中，调度域s 。，是在 系统中所有逻辑处理器集合的1 个子集，即呙c 。在调度域墨，上，所有 调度组是，足：，是集合墨的一个完整正交划分，即是。u 墨：u = s ， 对任意2 个调度组有s 。r 、& = o 。 传统s m p 系统负载均衡的设计目标是每个c p u 芯片运行负载大致相当。在 传统s m p 系统中，调度域s 指所有c p u 芯片集合，每个c p u 芯片本身是一个独 立的调度组。例如，在8 个处理器芯片组成的传统s m p 系统中，调度域s 。- - o ，l ， 7 ，在该调度域上的调度组为& = i ) ，i _ 0 ，l ，7 。 第5 页 国防科学技术大学研究生院硕士学位论文 r - - - !r i f - - - - ! r - - - - - !t ir ir l r l ：0 ：；1 ；：2 ；3 ；：4 ；5 ；：6i ；7 ； l j ii ii ji ii i ii i s m p 图2 2s m p 系统的调度域 c m t 系统考虑每个c p u 芯片间的负载均衡问题，还进一步考虑在处理内核间 和线程执行环境问的负载均衡问题。在c m t 系统中，调度域有3 个层次：s m p 调度域，p h y 调度域和c o r e 调度域1 6 1 。 图2 3c m t 系统的调度域 s m p 调度域与传统s 系统相同，p h y 调度域是由c p u 芯片内部所有的处 理内核调度组构成，c o r e 调度域是由处理内核所属的所有逻辑处理器调度组构 成。在2 个双核处理器芯片组成的c m t 系统中( 每个核包括2 个线程执行环境) ， 逻辑处理器1 的调度域有3 个层次：s m p 调度域为 o ，1 ，7 ，包括2 个c p u 芯片调度组 0 ，l ，2 ，3 ) 和 4 ，5 ，6 ，7 ) ；p h y 调度域为 o ，1 ，2 ，3 ) ，分别包 括2 个处理内核调度组 o ，1 ) 和 2 ，3 ) ；c o r e 调度域为 0 ，1 ) ，包括2 个逻辑处 理器调度组 0 ) 和 1 。 2 2 2 协同调度 2 2 2 1 基本问题描述 在c m t 系统内，不同处理内核同时运行的2 个线程互称为硬件并行线程。在 同一个c p u 芯片内，不同处理内核同时运行的2 个线程互称为协同线程。协同调 度是指在负载特性、共享资源和评价指标等约束条件下，一些线程调度成协同线 程，另一些线程避免调度成协同线程。 传统s m p 系统只有硬件并行线程，每条并行线程独占一个完整的c p u 资源， 因此，传统s m p 系统调度有一个假设条件：在没有任何同步通信的约束条件下， 线程获得的性能与硬件并行线程无关。但该假设条件对于c m t 系统并不成立，其 原因是严重影响线程性能的硬件资源在协同线程之间的分配具有不确定性。研究 第6 页 国防科学技术大学研究生院硕士学位论文 表明，l 2c a c h e 短缺会严重影响线程性能，共享l 2c a c h e 对线程性能具有关键性 的影响1 1 。n 。增长l 1c a c h e 和l 2c a c h e 容量能降低l ic a c h e 和l 2c a c h e 的失效率， 但每个c p u 周期平均指令数i p c 依赖于l 2c a c h e 失效率，c m t 硬件并行技术能 降低和隐藏l ic a c h e 失效导致的短延迟，却不能改善l 2c a c h e 失效导致的长延迟 【2 】 o 在协同线程间共享l 2c a c h e 和f s b 总线控制器等c p u 硬件资源。如果硬件 不能监视和控制l 2c a c h e 等硬件资源的分配，那么硬件资源分配依赖于协同线程 对该资源的需求量，很容易导致不确定和不公平的资源分配1 1 8 】。线程的协同线程 相关性会导致：不公平的c p u 资源共享，性能的不可预见性和优先级的颠倒等问 题【1 9 1 。不公平的c p u 资源共享【2 0 】导致错误计费，如果某个线程与一个恶意线程互 为芯片级并行线程，那么该线程可能得不到与其所付费用等值的服务。性能的不 可预见性使得性能调整、服务质量提供和软实时系统的设计变得更复杂。当与一 个恶意线程协同运行时，一个高优先级的线程得不到性能提升，产生优先级颠倒 现象。另一个更严重的问题是“c a c h e 抖动【2 1 】：2 个线程频繁访存导致频繁c a c h e 失效，频繁c a c h e 失效导致双方的c a c h e 内容相互覆盖，加剧c a c h e 失效，从而 严重降低系统性能【2 2 j 。 2 2 2 2 协同调度分类 l 、特殊硬件支持 根据是否需要特定硬件支持，c m t 调度算法分为2 类：特定体系结构调度算 法和通用体系结构调度算法。特定体系结构调度算法是在特定硬件基础上动态测 量或分配共享资源，通过协同凋度选择协同线程。优化共享资源的分配，提高系 统的整体性能。文献【2 3 】提出访存监测框架，它在硬件体系结构的支持下，操作系 统运行时获得l 2c a c h e 的使用状态信息，并根据详细的访存信息进行线程调度以 提高性能。该调度算法能获得较好的性能，但需要特定硬件支持，具有很强的平 台相关性，较差的可扩展性。通用体系结构调度算法则是在现有硬件平台上，通 过模型分析和在线式软件测量的方法获取c m t 调度算法所需的输入信息。文献【2 】 提出一个用于估计给定并行线程数量条件下系统i p c 的分析模型，根据该模型计 算得到高i p c 的并行线程数量，实施相应的调度策略。此调度算法在传统s m p 调 度算法基础上实现，具有良好的可扩展性，但模型不够准确，不能直接监控硬件 状况，缺乏控制精度。 2 、硬件并行线程数量 根据硬件并行线程数量，c m t 调度算法分为2 类：硬件并行线程数量守恒算 法和硬件并行线程不守恒算法。 当线程数量超过处理内核数量时，如果硬件并行线程数量总是等于处理内核 第7 页 国防科学技术大学研究生院硕士学位论文 的数量，即系统不存在空闲处理内核，那么该系统的调度算法属于守恒算法，传 统s m p 系统的调度属于硬件并行线程数量守恒算法。如果硬件并行线程数量小于 处理内核的数量，即系统存在空闲处理内核，那么系统的调度算法就属于不守恒 算法。文献【2 】提出的硬件并行线程不守恒算法通过将一个或多个处理内核保持为空 闲状态以缓解c a c h e 争用，能避免共享l 2c a c h e 导致的c a c h e 抖动问题，提高系 统性能。 2 2 3 性能评价标准 2 2 3 1 效率 效率是衡量调度算法优劣的最主要性能评价标准，包括系统平均吞吐率和系 统平均i p c 等效率指标。在传统s m p 系统中，硬件并行线程独享c p u 芯片的所 有硬件资源，在任意处理器上运行功耗相同，因此，单纯追求效率成为传统s m p 系统调度算法的一个设计目标。 协同线程调度和负载均衡以追求性能优化为设计目标，用于优化c m t 处理器 的共享资源争用。文献【2 4 】提出协同线程调度，它采用联机性能监测和启发式算法， 实现最小资源争用程度的线程调度。用户级原型系统评估表明，上述算法通过对 线程的联合调度，降低了c m t 处理器的共享资源争用，优化了系统性能。 2 2 3 2 效率功耗比 c m t 系统调度算法要考虑能耗和散热问题。a c p i 定义处理内核能耗状态的 若干等级，处于运行状态的内核所需能耗和散热比较大，处于休眠或空闲状态的 内核所需能耗和散热比较少。工作电压和频率决定了整个处理器的能耗。在同一 个c m t 处理器中，所有处理内核共享同一个电源层和时钟。所需能耗最高的内核 决定电源层的电压值和时钟频率，它决定了整个c m t 处理器能耗。因此，c m t 处理器的总能耗近似等于最高内核能耗与内核数量的积。为了考察c m t 处理器的 单位功耗所获得的效率，引入效率瓦特比指标。c m t 系统为了节省能耗降低散热， 在不影响系统效率的前提下，操作系统应将线程集中调度在c p u 芯片上运行，获 得了较好的效率瓦特比。 2 2 3 3 公平性 公平性是衡量调度算法的另一个重要的性能评价标准。在传统s m p 系统中， 硬件并行线程独占各处理器内部资源，按硬件仲裁器定制的公平准则共享存储器 资源。但在c m t 系统中，协同线程相关的性能变化会产生不公平的c p u 资源分 配。虽然每个c p u 芯片访问共享存储器资源是按硬件仲裁器定制的公平准则，但 如果在某个芯片内部同时运行，1 个访存密集型线程，其他芯片只有l 条访存密集 第8 页 国防科学技术大学研究生院硕士学位论文 趔线程，那么后者获得的访存带宽是前者的n 倍。c m t 公平调度存在软硬件2 种 解决方案，其中哪种较好有待进一步研究。文献【1 6 】提出强制公平资源共享和操作 系统控制资源分配的基本思想，硬件实现动态资源划分，操作系统通过优先级分 配控制动态划分。硬件方案的优点在于不需要复杂和不精确的软件性能模型，但 开发费用高、市场周期长。 2 2 3 4 温度控制 动态温度管理d t m 在近几年己成为c m t 处理器调度领域内的一个研究热点。 d t m 的主要目标是在获得高性能计算时将芯片保持在一个安全的温度下。在芯片 内部，某个区域上的任务数量越多，该区域的热量、温度越高。若某个区域的温 度过高，则该区域的处理内核被配置为慢速甚至休眠状态，会严重影响性能。文 献【2 5 j 分析线程迁移范围对动态电压和频率的影响，通过线程迁移进行温度控制。 2 3 实验硬件平台 本文所用的实验平台是s u n 公司的t 5 1 4 0 服务器。这一款服务器采用了2 路 u l t r a s p a r ct 2p l u s 处理器，每个处理器集成了4 或8 个s p a r c 核，每个内核支 持8 条硬件线程( s t r a n d ) ，因此单个处理器有3 2 或6 4 条s t r a n d ，整个服务器可 提供6 4 或1 2 8 条s t r a n d 。图2 4 所示为u l t r a s p a r ct 2 处理器体系结构。 图2 4u l t r a s p a r ct 2 处理器体系结构 第9 页 国防科学技术大学研究生院硕士学位论文 图2 4 所示为u l t r a s p a r ct 2 处理器核的基本结构。每个s p a r c 核对8 条 s t r a n d 有完整地硬件支持，还集成有2 条整数运算流水线、1 条浮点流水线、一条 访存流水线。8 条s t r a n d 还被硬分区成了2 组，每组4 条，各共享1 条整数流水线。 此外，再加上被8 条s t r a n d 共享的1 条浮点流水线和访存流水线，在某一时刻， 核中最多只有两条s t r a n d 处于活动状态，可能的组合情况有：2 个指令流水线操作、 1 个整数操作和1 个浮点操作、1 个整数操作和1 个访存操作，以及1 个浮点操作 和1 个访存操作。各条s t r a n d s 按时钟周期而切换运行，运行s t r a n d 从被硬分组的 4 条中按照最近最少流出的优先级策略选取。当1 条s t r a n d 遇到了长延迟事件，例 如c a c h e 失效，它就会被标记为不可用，其中的指令不再流出，直到这个长延迟 事件解决。期间，其他可运行的s t r a n d 则继续运行。 核中的8 条s t r a n d 共享1 6 k b 的8 路关联指令缓存( 3 2 字节缓存线) 和8 k b 的4 路关联数据缓存( 1 6 字节缓存线) 。处理器中的8 个核通过交叉开关( c r o s s b a r ) 与芯片内的4 m b 大小1 6 路关联二级缓存( 6 4 字节缓存线) 相连。此外，处理器 中还集成有d r a m 控制器，一致性维护单元以及p c i e x 总线控制器等部件。 图2 4u l t r a s p a r ct 2 处理器内核结构 表2 1 列出了对处理器性能有关键影响的部分访存操作延迟参数。表中的访存 读取写入延迟的估算是假定处理器的m c u 单元在收到读写请求时，处于空闲状 态，并且该请求指向8 个f s b 通道中的最后一个【1 5 1 。 表2 1t 2 处理器c a c h e 失效与访存延迟参数 ，“延迟事件延迟时钟周期延迟时间 指令c a c h e 失效 2 41 7 1 4 n s l l 失效 数据c a c h e 失效 2 61 8 5 7 n s 访存读取延迟 1 2 9 8 59 2 7 5 n s l 2 失效 访存写入延迟 9 8 3 57 0 2 5r l $ 第1 0 页 国防科学技术大学研究生院硕士学位论文 该处理器的读数据指令首先是从l l 数据c a c h e 装载数据，而写数据指令则直 接把数据写入l 2c a c h e 。因此，读写操作对访存密集型负载性能上的影响会有所 不同。写回式的l 2c a c h e 也使得线程不必等待数据写回到内存而停顿。 2 4 本章小结 本章对当前的多核调度优化关键技术进行研究，接下来论文将在之前研究的 基础上进一步研究和开发适用于课题所属项目要求的多核调度优化相关技术及算 法，以满足项目的性能目标要求。 第1 1 页 国防科学技术大学研究生院硕士学位论文 第三章多线程性能测试 针对c m t 硬件平台的复杂性和体系结构上较新的特点，有必要对其多线程性 能进行测试，分析其特点以便于之后设计算