（计算机科学与技术专业论文）同时多线程处理器资源共享控制策略研究.pdf

浙江大学博士学位论文 摘要 摘要 随着超大规模集成电路技术持续以指数级地发展 处理器芯片上集成的资源 将大量地增加 如何有效利用这些资源成为发挥处理器性能的关键 同时多线程 s m t 处理器通过同时执行来自多个线程的指令利用了线程级并行和指令级并 行 其细粒度的资源共享和操作延迟隐藏为处理器带来较好的性能提升 然而同 时多线程环境中 线程竞争共享资源胜过分享资源 不合理的资源竞争将会导致 共享资源的阻塞 滥用和浪费 资源共享控制的合理性决定了处理器的吞吐量和 线程间的公平性 随着处理器和存储器之间性能差距的增大 片外访存操作的长 延迟将造成s m t 处理器上越来越明显的资源阻塞和资源滥用 另外 各线程在 竞争共享资源的过程中随着程序行为的变化表现出变化的资源需求 适应性不强 的资源共享控制策略将很难持续地提供优化的资源分配方案 这些问题使如何合 理地控制s m t 处理器资源在线程之间的共享显得尤其重要 围绕上述问题 本文在深入研究分析相关工作的基础上 从避免长延迟l o a d 依赖指令阻塞共享资源 利用计算访存并发性有效隐藏片外访存长延迟 增强资 源共享策略对程序行为变化的适应性 以及避免控制决策运算影响关键流水线路 径这四种途径展开研究 并提出了相应的同时多线程处理器资源共享控制策略 通过模拟实验验证了各策略的有效性 主要取得以下研究成果 1 为避免长延迟l o a d 依赖指令阻塞共享资源 提出了长延迟l o a d 感知的 s m t 处理器指令派遣策略d s t a l l 和d s t a l l p 该策略在流水线的派遣阶段实 施停止派遣控制决策 根据检测到的或预测到的二级c a c h e 失效信息决定是否停 止派遣线程的指令到指令队列 通过避免已取指的长延迟l o a d 依赖指令在检测到 长延迟l o a d 后继续阻塞资源 以及缩短控制决策反馈信息利用延迟的方式 减少 了长延迟l o a d 给s m t 处理器资源共享带来的负面影响 2 针对隐藏片外访存长延迟的问题 提出了利用计算和访存操作并发性 的s m t 处理器资源划分策略e c m c 它从s m t 处理器利用线程级并行隐藏长操 i i i 浙江大学博士学位论文摘要 作延迟的本质特性出发 周期性地根据线程计算型访存型操作并发能力来调整共 享资源在各线程之间的划分 为在计算操作与片外访存操作并发性方面表现较好 的线程分配更多的资源 提高了执行时钟上的计算操作与访存操作并发率 较有 效地隐藏了c a c h e 失效l o a d 操作的长延迟 3 为了避免资源分配优化过程陷入局部次优空间 增强在变化的程序行 为中持续优化的能力 提出了一种空间触发的耗散式s m t 处理器资源分配策略 s d r d 该策略的分配优化自组织机制和分配空间上触发的混沌协同工作 通过 控制资源分配方案的相似度使资源分配方案能逃离局部极优方案 为程序行为变 化的不同阶段提供持续的资源分配优化 在仅以吞吐量为目标的情况下 同时照 顾了吞吐量和公平性性能 4 提出了s m t 处理器上非关键路径资源分配器设计模型n c p r d 该模 型使资源分配模块独立于处理器关键流水线路径 以避免资源分配在关键流水线 路径上的开销给处理器性能带来不可忽略的影响 n c p r d 的异步工作模式对于 时钟开销较明显的s m t 处理器隐式资源共享控制策略也具有参考意义 关键词 同时多线程 体系结构 资源共享控制 取指策略 派遣控制 资源划 分 性能 i v a b s t r a c t w i t ht h ec o n t i n u i n ga d v a n c e m e n t sa ta ne x p o n e n t i a lr a t ei nv l s it e c h n o l o g y t h e v o l u m eo fr e s o u r c e si n t e g r a t e di n t oap r o c e s s o rc h i pw i l l i n c r e a s er a p i d l y h o wt o m a l ee 伍c i e n tu t i l i z a t i o no ft h e s er e s o u r c e si st h ek e y t oe x e r tp r o c e s s o r sp e r f o r m a n c e s i m u l t a n e o u sm u l t i t h r e a d i n g s m t p r o c e s s o rt a k e sa d v a n t a g eo fb o t ht h r e a dl e v e l p a r a l l e l i s ma n di n s t r u c t i o nl e v e lp a r a l l e l i s mv i ac o n c u r r e n t l ye x e c u t i n gi n s t r u c t i o n s f 而md i f r e r e n tt l l r e a d s i t sf i n e g r a i n e dr e s o u r c es h a r i n ga n dl o n gl a t e n c yh i d i n gb r i n g s g o o dp e r f o r m a n c ei m p r o v e m e n t h o w e v e r t h r e a d sc o m p e t ef o rc o m m o nr e s o u r c e s r a t h e rt h a nt h e ys h a r et h e mi ns m te n v i r o n m e n t u n r e a s o n a b l er e s o u r c ec o m p e t i n g w i l lr e s u l ti nr e s o u r c ec l o g g i n g a b u s e m e n ta n dw a s t a g e t h er a t i o n a l i t yo f r e s o u r c e s h a r i n gc o n t r o ld e t e r m i n e st h et h r o u g h p u tp e r f o r m a n c ef o rp r o c e s s o ra n dt h ef a i r n e s s b e t w e e nt h r e a d s w i t ht h ee v e ri n c r e a s i n gp e r f o r m a n c eg a pb e t w e e np r o c e s s o ra n d m e m o r y t h el o n gl a t e n c y f r o mo f f c h i pm e m o r ya c c e s sw i l lm a k et h er e s o u r c e c l o g g i n ga n da b u s e m e n ti ns m tp r o c e s s o rm o r ee m i n e n t m o r e o v e r t h r e a d sc h a n g e t h e i rr e q u i r m e n to fr e s o u r c e sw i t ht h et h ec h a n g eo ft h e i rp r o g r a m b e h a v i o rw h e nt h e y c o m d e t ef o rr e s o u r c e s i ti sd i f f i c u l tf o ra nu n a d a p t a b l e r e s o u r c es h a r i n gc o n t r o lp o l i c y t 0 s u p p l yc o n t i n u i n go p t i m i z a t i o n o fr e s o u r c ed i s t r i b u t i o n a l l t h e s ep r o b l e m s e s p e c i a l l va u g m e n t t h es i g n i f i c a t i o no fh o wt or e a s o n a b l yc o n t r o lt h es h a r i n go fs m t p r o c e s s o rr e s o u r c e sa m o n g t h et h r e a d s a c c o r d i n gt ot h ep r o b l e m sm e n t i o n e da b o v e t h i sd i s s e r t a t i o n a f t e ra d e e ps t u d y o nr e l a t e dw o r k s l a u n c h e d t h er e s e a r c hi nf o u ra p p r o a c h e s p r e v e n t m g l o n g l a t e n c y 1 0 a dd e p e n d e n t s f r o mc l o g g i n gc o m m o nr e s o u r c e s e x p l o i t i n g t h e c o n c u r i e n c vo fc o r e p u t ea n dm e m o r ya c c e s so p e r a t i o n sf o rh i d i n go fo f f c h i pm e m o r y a c c e s sl a t e n c y m a k i n gt h er e s o u r c es h a r i n gc o n t r o lp o l i c ya d a p t a b l e t oc h a n g i n g p r o g r a mb e h a v i o r a n de l i m i n a t i n gt h ei n f l u e n c eb r o u g h tt o t h ec r i t i c a lp i p e l i n eb y t h o s ec y c l e ss p e n to nm a k i n gr e s o u r c ec o n t r o ld e c i s i o n c o r r e s p o n d i n g r e s o u r c e s h a r i n gc o n t r o lp o l i c yf o rs m tp r o c e s s o r sw a sp r e s e n tp e ra p p r o a c h a n d t h e i rv a l i d i t y w e r ep r o v e dt h r o u g hs i m u l a t i o n s t h em a i nc o n t r i b u t i o n sa r e a sf o l l o w s v 塑堑查兰堡圭兰堡堡壅垒婴 1 t op r e v e n ti n s t r u c t i o n sd e p e n d e n to nl o n g l a t e n c yl o a d sf r o mc l o g g i n gt h e c o m m o nr e s o u r c e s al o n g l a t e n c y l o a da w a r e dd i s p a t c hp o l i c yf o rs m t p r o c e s s o r si s p r o p o s e d t h i sp o l i c yd e c i d e so nw h e t h e rat h r e a ds h o u l db ed i s p a t c h s t a l l e da tt h e d i s p a t c hs t a g ei nt h ep i p e l i n ea c c o r d i n gt ot h ed e t e c t e do rp r e d i c t e dl 2c a c h em i s s i n f o r m a t i o n b yp r e v e n t i n gt h o s el o n g l a t e n c y l o a dd e p e n d e n t st h a th a v eb e e nf e t c h e d f r o mc l o g g i n gt h ec o m m o nr e s o u r c e sa f t e rd e t e c t i o no f l o n g l a t e n c yl o a d a n dr e d u c i n g t h ef e e d b a c kl a t e n c yo ft h el 2c a c h em i s si n f o r m a t i o n i ta l l e v i a t e st h en e g a t i v e i n f l u e n c eb r o u g h tt ot h er e s o u r c es h a r i n gi ns m t p r o c e s s o rb yl o n g l a t e n c yl o a d s 2 t oa d d r e s st h ep r o b l e mo fh i d i n gl o n gl a t e n c yo fo f f c h i pa c c e s s ar e s o u r c e p a r t i t i o n i n gp o l i c yf o rs m tp r o c e s s o r se x p l o i t i n gt h ec o m p u t e m e m o r yc o n c u r r e n c yi s p r o p o s e d i tf o l l o w st h ee s s e n t i a lf e a t u r eo fs m tp r o c e s s o r st h a th i d el o n gl a t e n c yb y e x p l o i t i n gt h r e a dl e v e lp a r a l l e l i s m t u n e st h er e s o u r c ep a r t i t i o n sa m o n gt h et h r e a d s p e r i o d i c a l l ya c c o r d i n gt ot h ec o n c u r r e n c yl e v e lo fc o m p u t e m e m o r yo p e r a t i o n so fe a c h t h r e a d a n dp r o v i d e sm o f er e s o u r c e st ot h et h r e a dt h a th a sb e t t e rp e r f o r m a n c ei n c o m p u t e m e m o r yc o n c u 熙n c y t h i sp o l i c yi m p r o v e st h ep r o p o r t i o no ft i m ef o r c o n c u r r e n tc o m p u t e m e m o r ye x e c u t i n gt ot h ew h o l e e x e c u t i n gt i m e p r o v i d i n g e f f e c t i v eh i d i n go fl o n gl a t e n c yb r o u g h tb yc a c h e m i s sl o a d s 3 t oa v o i dt h es t a g n a t i o ni nt h es u b o p t i m a lr e s o u r c ed i s t r i b u t i o ns p a c e si nt h e r e s o u r c ed i s t r i b u t i o no p t i m i z a t i o np r o c e d u r e a n de n h a n c et h ec a p a b i l i t yo f p e r f o r m i n g ac o n t i n u eo p t i m i z a t i o nf o rr e s o u r c ed i s t r i b u t i o nf o rc h a n g i n gp r o g r a mb e h a v i o r a s p a t i a l l yt r i g g e r e dd i s s i p a t i v er e s o u r c ed i s t r i b u t i o np o l i c yf o rs m tp r o c e s s o r si s p r o p o s e d i nt h i sp o l i c y t h es e l f o r g a n i z a t i o nm e c h a n i s mc o o p e r a t e sw i t ht h es p a t i a l l y t r i g g e r e dc h a o sf o rt h ed i s t r i b u t i o ns o l u t i o n s b yt a k i n gc o n t r o lo ft h es i m i l a r i t yo ft h e d i s t r i b u t i o ns o l u t i o n s t h ep o l i c yc a ne s c a p ef r o mt h es u b o p t i m a ls o l u t i o n a n ds u p p l y p e r s i s t e n to p t i m i z a t i o nf o rr e s o u r c ed i s t r i b u t i o ni nd i f f e r e n tp r o g r a mp h a s e s t h e t h r o u g h p u ta n df a i r n e s sp e r f o r m a n c ea r eb o t hi m p r o v e db yt a k i n go n l yt h et h r o u g h p u t a st h eo p t i m i z a t i o nt a r g e t 4 ad e s i g nm o d e lo fn o n c r i t i c a lp a t hr e s o u r c ed i s t r i b u t o rf o rs m t p r o c e s s o r si s p r o p o s e d w h i c hs e p a r a t e st h er e s o u r c ed i s t r i b u t i o nm o d u l ef r o mt h ec r i t i c a lp i p e l i n e p a t ht oa v o i dt h ec l o c kw a s t a g ec a u s e db yt h ec o m p u t a t i o no nt h ea l l o c a t i o ns o l u t i o n s v i 塑垩奎兰望 兰垡笙兰 垒 璺竺 t h ea s y n c h r o n o u sw o r km o d eo ft h i sn o n c r i t i c a lp a t hr e s o u r c ed i s t r i b u t o ri sa l s o m e a n i n g f u lf o rt h o s ei m p l i c i tr e s o u r c es h a r i n gc o n t r o lp o l i c i e st h a tc o n s u m eo b v i o u s c y c l e si nm a k i n gd e c i s i o n k e y w o r d s s i m u l t a n e o u sm u l t i t h r e a d i n g c o m p u t e ra r c h i t e c t u r e r e s o u r c es h a r i n g c o n t r o l f e t c hp o l i c y d i s p a t c hc o n t r o l r e s o u r c ep a r t i t i o n i n g p e r f o r m a n c e i 浙江大学博士学位论文 插图清单 插图清单 图1 1 处理器与存储器性能增长差异 2 图1 2 处理器与存储器时钟频率增长趋势 2 图1 3 本文组织结构关系 6 图2 1 同时多线程处理器体系结构模型 9 图2 2 同时多线程处理器流水线关键资源 1 0 图3 1 基于s i m p l e s c a l a r 扩展的模拟系统结构 3 0 图3 2m s i m 模块结构 3 2 图4 1 前端取指策略在l o a d 失效时流水线情况 4 1 图4 2 继续最早l 2 失效线程时序示意图 4 3 图4 3d s t a l l 在基本s m t 体系结构模型上的实现 4 5 图4 4d s t a l l p 在基本s m t 体系结构模型上的实现 4 6 图4 5d s t a l l d s t a l l p 及其它策略相对于i c o u n t 的i p c 提升 5 0 图4 6d s t a l l d s t a l l p 及其它策略相对于i c o u n t 的h m e a n 提升 5 1 图4 7d s t a l l d s t a l l p 及其它策略的d p m 值对比 5 2 图4 8 长延迟l o a d 触发延迟对d s t a l l 的性能影响 5 3 图4 9 长延迟l o a d 触发延迟对d s t a l l p 的性能影响 5 4 图5 1 同时多线程对存储级并行 a 及计算访存并发率 b 的影响 5 9 图5 2 计算操作和访存操作时钟示意图 6 0 图5 3i p m 对吞吐量性能i p c 和公平性性能h m e a n 的影响 6 2 图5 4e c m c 在基本s m t 体系结构模型上的实现 6 5 图5 5e c m c 与其它四种策略的i p c 和h m e a n 比较 6 7 图5 6e c m c 对其它四种策略的i p c 提升和h m e a n 提升 6 8 图5 7 计算型访存型操作并发率比较 6 9 图5 8 不同调整步距下e c m c 对i c o u n t 的i p c 和h m e a n 提升 7 0 i i 浙江大学博士学位论文 插图清单 图5 9 不同i q 大小下三种策略相对于i c o u n t 的i p c 和h m e a n 提升 7 l 图6 1 不同优化策略在m i x 2 类负载l u c a s p e r l b m k 下的优化过程 7 5 图6 2 不同优化策略在m e m 4 类负载l u c a s v p r e q u a k e t w o l f 下的优化过程7 5 图6 3s d r d 在基本s m t 模型上的实现 8 1 图6 4l s d r d 和g s d r d 与其它四种策略的i p c 和h m e a n 比较 8 5 图6 5l s d r d 和g s d r d 相对于i c o u n t 的i p c 和h m e a n 性能提升 8 6 图6 6s d r d 对其它四种策略的i p c 和h m e a n 性能提升 8 7 图6 7 利用范围对s d r d 的i p c 和h m e a n 性能影响 8 8 图6 8 混沌概率对s d r d 的i p c 和h m e a n 性能影响 8 9 图6 9 多样性阈值对s d r d 的i p c 和h m e a n 性能影响 9 0 图7 1s m t 模型上资源共享控制方法示意图 9 4 图7 2 非关键路径资源分配器模型 9 6 图7 3 与分配寄存器和流水线信息记录相关的操作时钟 9 8 图7 4n c p r d 实现对c p r d 实现的i p c 和h m e a n 性能提升 1 0 0 v 浙江大学博士学位论文 附表清单 附表清单 表2 1 不良资源竞争减少方法 1 9 表3 1 单线程负载模拟器基本配置 3 5 表3 2 测试程序分类及参考输入集 3 5 表4 1d s t a l l 与d s t a l l p 性能评估模拟器基本配置 4 8 表4 2d s t a l l 与d s t a l l p 性能评估所使用的多线程负载 4 9 表6 1s d r d 与h i l l 实现复杂性比较 8 2 表6 2 模拟器基本配置 8 3 表6 3 各类多线程负载配置 8 3 表6 4s d r d 参数设置 8 4 表6 5s d r d 相比其它策略具有不同性能提升等级的负载统计 8 7 表7 1 多线程负载组成 9 9 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研究成 果 也不包含为获得迸姿态堂或其他教育机构的学位或证书而使用过的材料 与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者虢7 东红 1 签字日期 钞矽年阳 多日 学位论文版权使用授权书 本学位论文作者完全了解逝婆盘鲎有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘 允许论文被查阅和借阅 本人授权逝婆盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播 可以采用影印 缩印或扫描等复制手段 保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 巧 红巧 签字日期 矽笋c 瑚 阳 导师签名 签字日期 2 沪9 年f2 月f r 乙日 浙江大学博士学位论文致谢 致谢 在本文完成之际 回首博士生活点点滴滴 犹似昨天 沉甸的感觉中更怀着 感恩的心 借此谨向所有给予我珍贵启发 鼓励和帮助的师长 同学 朋友和亲 人表示深深的感谢 首先要衷心感谢我的导师平玲娣教授以及潘雪增教授 他们在学术和科研上 的精心指导和教诲让我受益匪浅 在学识上的渊博视野和融会贯通鼓舞着我一直 奋斗上进 在态度上的严谨认真和精益求精让我深刻领会到做事的真谛 在生活 上的艰苦朴素和刻苦耐劳让我感受到上一辈人金子般的品质 也要感谢实验室的师兄弟姐妹们 感谢同门黄勇博士和姜励博士在科研工作 上给予的帮助 遇到挫折时总有他们的支持 感谢刘祖根博士 曾宪庭博士 张 宝军博士 李卓博士 傅建庆博士 李文博士 范容博士 张启飞博士 孙康博 士 王继民博士 万征博士等给予的启发和交流 他们不吝赐教和信息共享让我 更快进步 感谢陆敏峰硕士 曾璎珞硕士 施德来硕士 陈涛硕士 王贵丽硕士 等 从他们身上学到了敢于进取和勇于奋斗的精神 同时还要感谢同班同学潘巨 龙博士 胡保坤博士 张顺博士 蔡国永博士 周迪斌博士 孙锐博士 魏平博 士 李红博士等同学 与他们一起学习和生活的日子是美好的回忆 我要特别感谢我的妻子康望星女士 在我攻读博士的日子里 她在默默地支 持和鼓励我 让我全心投入学习工作 她在工作上的勤恳与认真和在生活上的纯 朴与平淡让我感到幸福备至 最后 我要把本文献给我的父亲和母亲 感谢他们在艰苦的环境下一如既往 地支持我 他们朴实中的智慧总让我感到无穷的动力 陈红洲 2 0 0 9 年9 月1 0 日于求是园 浙江大学博十学位论文第1 章绪论 1 绪论 1 1 研究背景与意义 半导体工业领域中 超大规模集成电路技术在近四十多年的持续发展中一直 遵循着摩尔定律 m o o r e sl a w 1 一 g o r d o nm o o r e 最开始指出以最小代价向集 成电路中所能填充的晶体管数量每年将会增长一倍 1 1 后来m o o r e 经过进一步观 察和分析又将增长速度精确为每两年增长一倍 2 随着芯片上能集成的晶体管数 量呈指数级地增长 单个处理器芯片上品体管的数量将数以十亿计 例如下一代 i n t e li t a n i u m 处理器 核心代号t u k w i l a 将集成有2 0 亿个晶体管 3 并且根据国 际半导体技术路线机构 i n t e r n a t i o n a lt e c h n o l o g yr o a d m a pf o rs e m i c o n d u c t o r s i t r s 2 0 0 8 年的预测 4 到2 0 1 6 年 工程师将采用2 2 5 n m 的工艺设计出包含多 达8 8 亿个晶体管的微处理器芯片 其时钟频率也将达到9 1 8 g h z 这为处理器提 供了很丰富的资源 然而程序所属的应用领域 程序设计思想 编译技术等决定了程序的固有指 令级并行度 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 许多研究显示 5 处理器从传 统的单指令流中实际能利用的指令级并行度是有限的 使用s p e cc p u 9 2 t l o 基准 测试程序 八发射a l p h a 超标量处理器的i p c i n s t r u c t i o n p e r c y c l e 不到1 5 1 1 1 处理器上许多资源不能得到充分的利用 此外 主要来源于访存指令的长延迟操 作使得数据消费指令需要等待较长时间才能继续进入流水线的下一阶段 这也降 低了处理器资源的使用效率 例如数据库类程序决策支持系统 d e c i s i o ns u p p o r t s y s t e m s 等经常大量访问不规则数据 频繁出现c a c h e 失效和访存长延迟 在四 发射的a l p h a 2 1 1 6 4 处理器上运行该工作负载的i p c 仅为0 5 2 6 0 7 6 9 多达7 5 的时间花费在等待访问大量数据所引起的停滞上 1 1 尽管通过高速c a c h e 存储层 次能缓解内存访问长延迟给处理器带来的负面影响 但许多新应用已呈现数据更 加密集型的处理需求 数据访问在时间和空间上表现出较差的局部性很大程度上 限制了高速c a c h e 的作用效果 浙江大学博十学位论文 第1 章绪论 n z 至 一 瓣 鬃 括 害 图1 1 处理器与存储器性能增长差异 9 年 图1 2 处理器与存储器时钟频率增长趋势 此外 虽然内存的访问速度也在不断增长 但相比处理器的速度增长则要缓 慢得多 从图1 1 显示的从1 9 8 0 年到2 0 1 0 年处理器与存储器性能的变化趋势中 可以看出 两者之间的性能差距在逐渐增大 而且根据i t r s 的预测 4 两者之间 的时钟频率增长差距在未来的十年将继续保持扩大的趋势 如图1 2 所示 引起 这一增长不平衡的主要原因是微处理器和存储器在设计目标上存在差异 前者强 调提供更快的晶体管和更精细的工艺水平来制造更快和功能更强的逻辑 而后者 2 浙江大学博士学位论文 第l 章绪论 则注重更小的单元面积上提供更大存储容量和更小的漏电以减少动态随机访存 的刷新时间 处理器和存储器之间逐渐增大的鸿沟使得内存访问延迟所占据的处 理器周期不断增多 因此形成的存储墙问题 m e m o 黟w a l l 1 1 2 1 4 较大程度地降 低了处理器资源的使用效率和限制了处理器性能的发挥 利用线程级并行性 t h r e a d l e v e lp a r a l l e l i s m t l p 的超标量处理器技术对 于克服程序有限的i l p 和隐藏操作长延迟有较为明显的作用 根据利用t l p 方式 和资源组织机制的不同 这样的处理器具有不同的资源利用水平和延迟隐藏水 平 片上多线程 c h i pm u l t i t h r e a d i n g c m t 处理器中一套流水线负责并行处 理不同线程的指令 其共享功能单元以及其它的一些关键流水线资源的机制使处 理器资源在线程之间得到较充分的利用 并且也隐藏了操作长延迟 其中指令交 错多线程 i n t e r l e a v e dm u l t i t h r e a d i n g i m t 处理器在每个时钟周期都进行线程 切换 为细粒度多线程 块交错多线程 b l o c k e dm u l t i t h r e a d i n g b m t 只是在 必要的情况下 如遇到长延迟操作 才进行线程切换 为粗粒度多线程 虽然i m t 和b m t 处理器能够利用t l p 来减少时序上因i l p 不足造成的空隙 但是在某个 时钟周期 可供并行发射执行的指令仍然只来自一个线程 关键资源依然会因为 线程i l p 不足而存在浪费 同时多线程 s i m u l t a n e o u sm u i t i t h r e a d i n g s m t 处 理器则允许在每个时钟周期同时发射执行多个线程的指令 比较充分地利用了 t l p 来同时减少时序上和部件空间上的资源浪费 来自各线程的更多可供并行发 射执行的指令使操作长延迟得到更有效的隐藏 区别于c m t 的单流水线体系 片上多处理器 c h i pm u l t i p r o c e s s o r c m p 8 1 5 1 6 上有多条流水线分别控制着多 个处理器核上线程的运行 每个单线程的核只执行一个线程的指令 c m p 的目标 是降低单核的复杂度 以缩短设计和验证时间 通过核间的可扩展性来降低功耗 但单核上的资源受线程i l p 和长延迟操作的影响存在浪费 而且c m p 上主要通 过多线程程序设计提高应用程序的性能 而不能通过分享其它流水线上的关键资 源来提高单线程的性能 较难满足那些单线程应用的需求 为了弥补c m p 的不 足 许多设计已经将s m t 技术结合到c m p 中以满足性能上的需求 1 7 1 9 1 多线程和超标量处理器技术的结合使s m t 处理器同时利用了i l p 和t l p 浙江大学博十学位论文第1 章绪论 它同时运行来自多个线程指令的机制较好地实现了细粒度的资源共享和操作延 迟隐藏 让处理器资源得到充分发挥以提高处理器性能 同时多线程技术带来的 较大性能提升和较小处理器芯片面积增加使其受到工业界亲昧 并在高性能服务 计算 桌面计算和嵌入式计算等领域得到广泛应用 然而同时多线程环境中 各 线程在大多数情况下是在竟相争用共享资源胜过分享资源 不合理的资源共享会 形成共享资源阻塞 滥用和浪费的现象 最终导致处理器吞吐量以及线程间公平 性的降低 随着处理器和存储器之间性能差距的增大 片外访存操作的长延迟将 造成s m t 处理器上越来越明显的资源阻塞和资源滥用 另外 s m t 处理器上各 线程在竞争共享资源的过程中随着程序行为的变化表现出变化的资源需求 静态 的或者适应性不强的资源共享控制策略将很难在变化的程序行为持续地提供相 应的优化控制 如何合理地控制共享资源在多线程之间的共享已经成为s m t 处 理器上有意义的热点研究问题 1 2 论文主要工作 本文研究工作主要围绕国家 8 6 3 高技术研究发展计划资助项目 图灵五 级操作系统设计及测评关键技术研究与实现 2 0 0 6 a a 0 1 2 4 3 1 浙江省重大科 技专项重点资助项目 新一代网络信息安全芯片u t m 及设备 2 0 0 6 c 1 1 1 0 5 而 进行的 本文在深入研究与分析相关工作的基础上 从如何避免长延迟l o a d 依赖 指令阻塞共享资源和缩短控制决策反馈利用延迟 如何利用计算访存并发性有效 隐藏片外访存长延迟 如何提供适应程序行为变化的资源分配策略 以及如何避 免控制决策运算影响关键流水线路径这四个思路展开研究 并提出了相应的s m t 处理器资源共享控制策略 通过模拟实验验证了各策略的有效性 主要工作包含 以下几个方面 1 深入研究和分析了s m t 处理器资源共享控制相关技术 建立了s m t 处理器性能模型 并通过该模型讨论分析了影响资源竞争的因素以及减少不良资 源竞争的方法 对现有的s m t 处理器资源共享控制策略进行了归纳分析 并概 述了通过取指策略 资源划分 利用存储级并行和复杂资源结构及指令调度机制 4 浙江大学博士学位论文第l 章绪论 的途径实现资源共享控制的相关工作及其优缺点 2 研究分析了s m t 环境下长延迟l o a d 操作给资源共享控制带来的挑战 从面临的问题中归纳总结出长延迟l o a d 依赖指令在长延迟l o a d 出现后继续阻塞资 源的原因 并指出了流水线反馈信息利用延迟对资源共享控制决策的影响 提出 了长延迟l o a d 感知的s m t 处理器指令派遣策略d s t a l l 和d s t a l l p 它在流 水线的派遣阶段实施停止派遣控制决策 减少了l o a d 依赖指令阻塞资源的机会 并通过提前预测流水线反馈信息的方法缩短了控制决策反馈信息的利用延迟 3 研究讨论了s m t 处理器上的指令操作并发性 分析了存储级并行在 s m t 环境下所受到的限制 并指出处理器性能随计算型和访存型操作并发性变化 的规律 为较好地隐藏片外访存操作的长延迟 提出了利用计算和访存操作并发 性的s m t 处理器资源划分策略e c m c 它为在计算操作与片外访存操作并发性 方面表现较好的线程分配更多的资源 e c m c 从s m t 处理器利用线程级并行隐 藏长操作延迟的本质特性出发 提高了执行时钟上的计算操作与访存操作并发 率 较有效地隐藏了c a c h e 失效l o a d 操作的长延迟 4 针对线程因程序行为变化而改变的资源分配优化空间进行了分析与观 察 为了适应变化的优化分配空间 提出了一种空间触发的耗散式s m t 处理器 资源分配策略s d r d 该策略的自组织机制和分配空间上触发的混沌协同工作 通过控制资源分配方案的相似度使资源分配方案能逃离局部极优方案 为程序行 为变化的不同阶段提供了持续的资源分配优化 5 从资源共享控制器与s m t 处理器关键流水线路径之间的交互出发 提 出了s m t 处理器上非关键路径资源共享控制器设计模型n c p r d 该模型使资源 分配模块独立于处理器关键流水线路径 避免了资源分配运算在关键流水线路径 上的开销给处理器性能带来不可忽略的影响 1 3 论文组织结构 全文共分八章 各章组织结构关系如图1 3 所示 浙江大学博士学位论文 第1 章绪论 第一章绪论 0 第二章相关研究概述 上 第三章模拟方法与环境建立 1 第四章第五章第六章 长延迟l o a d 感知的利用计算访存并发空间触发的耗散式 s m t 处理器指令派性的s m t 处理器资 s m t 处理器资源分 遣策略源划分策略 配策略 上 第七章s m t 处理器的非关键路径资源共享控制器设计 j 第八章总结 图1 3 本文组织结构关系 第一章 绪论 介绍课题研究背景 研究问题与研究意义 概述论文的主要 工作 简述论文的组织结构 第二章 相关研究概述 从同时多线程处理器体系结构模型触发 介绍s m t 处理器流水线关键资源的使用 以及典型的商业s m t 处理器 通过建立性能模 型分析影响s m t 处理器资源共享竞争的因素和解决的方法 从不同角度对s m t 处理器资源共享控制策略进行分类 并具体从取指策略 资源划分 利用存储级 并行以及复杂资源结构与指令调度机制四个方面概述现有资源共享控制策略 第三章 模拟方法与环境建立 分析和介绍相关s m t 处理器模拟器 程序 负载模拟方法以及评价指标 并为本课题选择适当的实验方法与配置 第四章 长延迟l o a d 感知的同时多线程处理器指令派遣策略 通过分析长延 迟l o a d 依赖指令阻塞资源的原因和流水线反馈信息利用延迟对资源共享控制决 6 浙江大学博士学位论文第l 章绪论 策的影响 确定本章所提策略d s t a l l 和d s t a l l p 的设计动机 9 细想 描述策 略设计与实现 对策略的性能和每长延迟l o a d 指令的依赖指令数指标进行评估 并对相关参数进行讨论 第五章 利用计算访存并发性的同时多线程处理器资源划分策略 分析存储 级并行在s m t 环境下所受到的限制 描述s m t 处理器上的计算型和访存型操作 并发性 研究处理器性能随计算型和访存型操作并发性变化的规律 确定本章所 提策略e c m c 的设计动机与细想 描述策略设计与实现 对策略的性能和计算访 存并发率指标进行评估 并对相关参数进行讨论 第六章 空间触发的耗散式同时多线程处理器资源分配策略 阐述程序行为 变化的过程中存在的资源分配优化空间变化 介绍本章所提策略s d r d 的主要思 想 叙述其自组织机制和空间上触发的混沌 描述算法过程及策略实现 对策略 的性能进行评估 并对相关参数进行讨论 第七章 同时多线程处理器的非关键路径资源共享控制器设计 分析资源共 享控制器与s m t 处理器流水线关键路径间的