（电子科学与技术专业论文）同时多线程处理器中的资源分配策略研究.pdf

国防科学技术大学研究生院博士学位论文 结合使用 充分利用两种策略在优化公平性和提高性能方面的优势 在优化 公平性的同时尽可能提高处理器的总体性能 5 为了在保证实时任务服务质量的同时提高性能 提出在c p i t 策略中结合使用 m f p 策略 充分利用c p i t 和m f p 在保证实时任务服务质量和提高性能方面 的优势 在保证实时任务服务质量的同时尽可能提高处理器的总体性能 实验表明 本文提出的资源分配策略都能够有效地实现特定的目标 本文的 研究为同时多线程处理器在不同领域的广泛应用奠定了基础 主题词 同时多线程资源分配策略取指策略资源划分性能 公平性 服务质量 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t p a c t 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 r si m p r o v ep e r f o r m a n c eb ym u l t i p l e t h r e a d ss h a r i n gp r o c e s s o rr e s o u r c e s 1 1 1 ep e r f o r m a n c eo fe a c ht h r e a da n do v e r a l lp e r f o r m a n c eo f t h ep r o c e s s o ra r ea l ld e t e r m i n e db yh o wt oa l l o c a t es h a r e dr e s o u r c e sa m o n g t h ee o s c h e d u l e dt h r e a d s t h a ti s b yt h er e s o u r c ea l l o c a t i o np o l i c y i ti sa ni m p o r t a n t p r o j e c tt oa l l o c a t es h a r e dr e s o u r c e se f f i c i e n t l yi nt h er e s e a r c ho fs m tp r o c e s s o r s w 曲s m tp r o c e s s o r su s e dw i d e l y b e s i d e sp e r f o r m a n c e p r o c e s s o rh a r d w a r ei s r e q u i r e dt oc o n s i d e rf a i r n e s sa n dq u a l i t yo fs e r v i c e q o s o fr e a l t i m et a s k s c u r r e n t r e s e a r c h e so nr e s o u r c ea l l o c a t i o np o l i c i e si ns m t p r o c e s s o r sa r em a i n l yc o n c e m e dw i t h h o wt oi m p r o v ep e r f o r m a n c e h o wt oo p t i m i z ef a i r n e s sa a dh o wt og u a r a n t e eq o so f r e a l t i m et a s k s h o w e v e r f o ri m p r o v i n gp e r f o r m a n c e t h e r ee x i s tl o wr e s o u r c eu t i l i z a t i o n s e v e r er e s o u r c eu n d e r u s ea n dr e s o u r c ea b u s ei nc u r r e n tr e s o u r c ea l l o c a t i o np o l i c i e s h o wt oi m p r o v ep e r f o r m a n c ef u r t h e ri ss t i l lc h a l l e n g i n g f o ro p t i m i z i n gf a i m e s s c u r r e n tr e s e a r c h e sa l m o s tf o c u so ne v a l u a t i n gf a i r n e s so fp r e v i o u s l yp r o p o s e dp o l i c i e s n op o l i c yi sp r e s e n t e ds p e c i a l l yf o ro p t i m i z i n gf a i r n e s s h o wt oi m p l e m e n tf a i m e s sb y e f f i c i e n tr e 虻o b r s ea l l o c a t i o ni sd e m a n d i n g f o rg u a r a n t e e i n gq o so fr e a l t i m et a s k s r e l a t e dw o r k sa r er a r ea n do n l yo n ep o l i c ya l l o c a t i n gr e s o u r c e se x p l i c i t l yi sp r e s e n t e d h o wt og u a r a n t e eq o so fr e a l t i m et a s k sn e e d sf u r t h e rs t u d y d e t a i l e dr e s e a r c h e sh a v e b e e nd o n eo nt h e s et h r e ei s s u e s 1 1 碥m a i nc o n t r i b u t i o n sa r ca sf o l l o w s 1 t oi m p r o v ep e r f o r m a n c ef u r t h e r m f p ar e s o u r c ea l l o c a t i o np o l i c yf o rs m t p r o c e s s o r s i sp r o p o s e d m f pp o l i c yc o m b i n e st h ea d v a n t a g e so ff e t c hc o m r o l l i n gw i t h t h o s eo fr e s o u r c ep a r t i t i o n i n g a n da l l o c a t e ss h a r e dr e s o u r c e sm a i n l yb yf e t c hc o n t r o l l i n gt oa l l o wr e s o u r c e st ob ec o m p e t e df r e e l ya n dt oi n c r e a s er e s o u r c eu t i l i z a t i o na sar e s u l t r e s o u r c ep a r t i t i o n i n gi su s e dt or e d u c er e s o u r c eu n d e r u s ea n dr e s o u r c ea b u s ec a u s e db yi m p r o p e rr e s o u r c ec o m p e t i t i o n 2 t os u p p o r tf a i r n e s sb e t t e r f a i r ar e s o u r c ea l l o c a t i o np o l i c yf o rs m t p r o c e s s o r s i sp r o p o s e d f a i rp o l i c ya l l o c a t e ss h a r e dr e s o u r c e si n d i r e c t l yb yf e t c hc o n t r o l l i n g a n dp r i o r i t i z e st h et h r e a dw i t hl o w e rn o r m a l i z e ds p e e d u pt oa c c e l e r a t ei ta n dt o m a k ea l lt h ec o s c h e d u l e dt h r e a d ss h a r er e s o u r c e s f a i r l yi t sa r e s u l t 3 t og u a r a n t e eq o so fr e a l t i m et a s k s c p i t ar e s o l l t c ea l l o c a t i o np o l i c yf o rs m t p r o c e s s o r s i sp r o p o s e d c p r rp o l i c ya l l o c a t e ss h a r e dr e s o u r c e si n d i r e c t l yb yf e t c h c o n l x o l l i n g a n dd u l ya d j u s t st h ef e t c hp r i o r i t yo far e a l r i m et a s kt oc o n t r o li t sp e r f o r m a n c ea n dt og u a r a n t e eq o so f ar e a l t i m et a s ka sar e s u l t 4 t bo p t i m i z ef a i r n e s sa tt h es a m et i m et oi m p r o v ep e r f o r m a n c e f a i r ar e s o u r c e a l l o c a t i o np o l i c yf o rs m tp r o c e s s o r s i sp r o p o s e d f a i r p o l i c yc o m b i n e sf a i r 第i i i 页 国防科学技术大学研究生院博士学位论文 w i t ha n yp o l i c yp u r c h a s i n gp e r f o r m a n c ea st h em a i no p t i m i z a t i o ng o a l m a k i n gf u l l u s eo ft h et w op o l i c i e s a d v a n t a g e st oa c h i e v ea sh i g hp e r f o r m a n c e 鹬p o s s i b l e w h i l eo p t i m i z i n gf a i r n e s s 5 t og u a r a n t e eq o so fr e a l t i m et a s k sa tt h es a m et i m et oi m p r o v ep e r f o r m a n c e i ti s p r o p o s e dt oc o l t l b i ec p i tp o l i c yw i t hm f pp o l i c y m a l d n gf u l lu s eo ft h ea d v a n r a g e so fc p i ta n dm f pt oa c h i e v ea sh i g hp e r f o r m a n c ea sp o s s i b l ew h i l eg u a r a n t e e i n gq o so f r e a l t i m et a s k s p l e n t yo fe x p e r i m e n t sa r em a d e r e s u l t ss h o wt h a ta l lt h ep r o p o s e dr e s o u r c ea l l o c a t i o np o l i c i e sc 锄a c h i e v et h e i ro w l lg o a l se f f e c t i v e l y o u rr e s e a r c h e sm a k ei tp o s s i b l e t 0a p p l ys m t p r o c e s s o r st ov a r i o u sd o m a i n s k e yw 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 r e s o u r c ea l l o c a t i o np o l i c y i n s t r u c t i o nf e t c hp o l i c y 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 f a i r n e s s q o s 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表3 1 表3 2 表3 3 表3 4 表3 5 表4 1 表4 2 表4 3 表4 4 表4 5 表5 1 表5 2 表6 1 表6 2 实验主机环境 3 4 模拟器的基准配置 测试程序 3 6 s p e cc p u2 0 0 0 测试程序的分组 3 7 m e d i a b e n c h 测试程序的l 2c a c h e 失效 3 7 某6 4 项资源的分配 表示线程可以使用的资源数目不受限制 4 3 不同资源分配策略中存在的资源浪费和资源滥用对比 4 6 不同资源分配策略的硬件复杂度对比 4 7 m f p 模拟评估中使用的多线程负载 4 8 两线程负载中线程取指优先级的分布 5 0 f a i r 模拟评估中使用的多线程负载 6 7 模拟的2 线程负载优先级组合 6 9 c p i t 策略中切换阈值的取值 8 5 c p i t 模拟评估中使用的多线程负载 8 7 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图i 1 图1 2 图1 3 图1 4 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图3 1 图3 2 图3 3 图3 4 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 i n t e l 处理器主频每年提升的百分比 1 发射带宽增加后s p e cc p u2 0 0 0 程序的i p c 和硬件复杂度增长趋势 3 发射槽使用情况示意图 7 章节的基本关系 1 2 同时多线程处理器体系结构模型 1 5 单线程处理器流水线与s m t 处理器流水线的比较 1 6 两级自适应分支预测器 1 7 存储层次 1 8 同时多线程处理器中共享资源的分类 1 9 s m t 处理器上运行不同数目线程时的i p c 一2 0 队列类共享资源利用率举例 2 1 g s h a r e 分支预测器的预测准确率 2 2 l 2c a c h e 失效率 2 3 修改后的模拟器的流水线 3 2 隐式资源分配策略的模拟模型 3 3 显式资源分配策略的模拟模型 3 3 i c o u n t 资源分配策略的模拟模型 3 4 资源分配对性能的影响 3 9 取指优先级的转换 4 2 m f p 策略的实现 4 4 静态划分方法 4 5 m f p d 相对于m f p s 的i p c h m e a n 提升 4 9 m f p d 相对于其他策略的i p c 提升 5l m f p d 相对于其他策略的n m e a n 提升 5 2 共享资源数目发生变化时m f p d 相对于其他策略的i p c 提升 5 3 存储延时发生变化时m f p d 相对于其他策略的i p c 提升 5 4 两线程占用处理器份额的比值 5 7 g z i p 测试程序的i p c 随执行阶段的不同而发生的变化 6 l 多次采样的结果 6 1 f a i r 中采样阶段和调整阶段的交替执行过程 6 l f a i r 策略的实现 6 4 f a i r 策略中执行状态转换图 6 5 第 i 页 国防科学技术大学研究生院博士学位论文 图5 7 对公平性和总体性能的影响 6 8 图5 8 刀h 柚对公平性和总体性能的影响 6 8 图5 9f a i r 策略下的公平性结果 7 0 图5 1 0r r i c o u n t 和f a i r 的公平性结果比较 7 1 图5 i lr r i c o m 盯和f a i r 的总体性能结果比较 7 2 图6 1不同资源分配策略和不同负载组合下c r a f t y 的性能 7 3 图6 2 资源数目与性能的关系 7 5 图6 3c p i t 中策略与d m c 的关系 7 7 图6 4 e p i c e n c o d e 测试程序的i p c 随执行阶段的不同而发生的变化 7 8 图6 5c p i t 中采样阶段和调整阶段的交替执行过程 7 8 图6 6c p i t 策略的实现 8 1 图6 7c p i t 策略中执行状态转换图 8 l 图6 8蚴存在的偏差 8 2 图6 9e p i c e n c o d e 的采样结果 8 4 图6 1 0c p i t 的成功率和最大性能偏差 8 7 图6 1 lc t 的实际性能 8 8 图6 1 2 与i c o u n t 相比 c p i t 策略获得的总体性能 8 9 图6 1 3 与i c o u n t 相比 c p i t 策略下n c t 的性能 8 9 图6 1 4c p i t 和c a z o d a 的成功率和最大性能偏差结果比较 9 0 图6 1 5c p i t 相对于c a z o r l a 的n c t 性能提升和处理器总体性能提升 9 l 图7 1f m r 十i c o u n t 策略的实现 9 5 图7 2f a i r 十i c o u n t 相对于f a 瓜的总体性能提升 9 6 图7 3f a i r m f p 相对于f a i r 的总体性能提升 9 6 图7 4f a i r i c o i j l q t f a m m f p 和i c o u n t 的总体性能结果比较 9 7 图7 5f a i r f a i r i c o u n t 和f a i r m f p 的公平性结果比较 9 7 图7 6c p i t m f p 策略的实现 9 9 图7 7c p i t m f p 相对于c p i t l c o u n t 的总体性能提升 9 9 图7 8c p i t i c o u n t 和c p i t m f p 的成功率和最大性能偏差结果比较 1 0 0 第v i i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果 尽我所知 除了文中特另l j 加以标注和致谢的地方外 论文中不包含其他人己 经发表和撰写过的研究成果 也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意 学位论文题日 囿盐垒堡猩矬垄鋈生煎登塑佥螫筮 龟盈盔 学位论文作者签名 2 虿拿l 日期 少形年 口月 o 日 学位论文版权使用授权书 本人完金了解国防科学技术大学有关保留 使用学位论文的规定 本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档 允 许论文被查阅和借阅 可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密学位论文在解密后适用本授权书 学位论文题目 回盟垄缦焦缝垄墨生煎选亟金堑筮喳盈容 学位论文作者签名 作者指导教师签名 日期 另叩g 年 d 月 d 日 日期 z 年 o 月 o 日 国防科学技术大学研究生院博士学位论文 第一章绪论 传统的处理器体系结构主要通过开发指令级并行 i n s t r u c t i o nl e v e lp a r a l l e l i s m 简称i l p 来提高性能 但受硬件复杂度 应用程序固有的i l p 和存储延时 等因素的限制 通过开发指令级并行来提高处理器性能变得越来越困难 开发更 高层次的并行 线程级并行 t h r e a dl e v e lp a r a l l e l i s m 简称1 1 l p 成为新一代 处理器体系结构的主要选择 而作为一种重要的线程级并行开发途径 同时多线 程技术自被提出之日起就一直是处理器体系结构领域研究的热点 同时多线程处理器 1 卅通过每个周期执行来自不同线程的指令来提高处理器资 源的利用率 从而提高其性能 同时执行的线程共享处理器资源 每个线程执行 的性能和处理器的总体性能都取决于如何在线程之间分配共享资源 即取决于资 源分配策略 因此 如何有效地分配共享资源成为同时多线程处理器研究的重要 课题之一 1 1 课题背景 传统上 提高处理器性能可以采用两种方法 一是提高处理器的主频 增加 单位时问内执行的指令数目 二是提高执行的并行度 增加每个周期内执行的指 令数目 处理器主频的提高一方面得益于集成电路制造工艺的发展 另一方面则源于 流水线级数的增加 随着流水线设计接近每一站8 1 6 个f 0 4 f a n o u t o f f o u r 反相器延迟的最低下限净j 流水线级数的增加即将终止 此后 处理器主频的提升 只能依赖于工艺的发展 然而 随着集成电路制造工艺进入深亚微米阶段 主频 的提升虽然依旧有利于提高性能 可是功耗问题越来越严重 其增长率甚至超过 性能的增长 导致能源消耗和制造成本增加 还给处理器工作的稳定性和可靠性 带来了严峻的挑战 图1 1 是i n t e l 微处理器每年相对前一年主频提升的百分比 8 l 丑 采 也 索 取 彗 詹 塔 抖 图1 1i n t e l 处理器主频每年提升的百分比 第l 页 国防科学技术大学研究生院博士学位论文 从图1 1 中可以看出 自2 0 0 0 年开始 主频提升的迅猛势头开始大幅回落 2 0 0 4 年之后增长速度低于1 0 2 0 0 5 年3 月 i n t e l 在推出3 7 3 g h z 的p e n t i u m 4e e 之后宣布取消4 g h z 的p e n t i u m 5 7 7 处理器的开发 i n t e l 公司副总裁早在2 0 0 1 年 的国际固态电路大会 i s s c c 上就曾透露 9 1 英特尔将不再通过刻意追求频率的 方式来提高性能 由此可见 通过提升主频来提高处理器的性能变得越来越困难 而提高执行 并行度将成为提高处理器性能的主要手段 1 1 1 指令级并行的局限性 传统的处理器设计中通过超标量 s u p e r s e a l a r 或超长指令字 v e r yl o n g i n s t r u c t i o nw o r d 简称v l i w 结构来开发应用程序中的指令级并行 从而提高执 行的并行度 然而 通过进一步开发i l p 来提高处理器性能受到以下几个因素的 限制 1 硬件复杂度 超标量和超长指令字结构通过增加处理器的指令发射带宽来提高i l p 但是发 射带宽的增加会导致硬件非常复杂 对超标量处理器来说 增加发射带宽会大大增加控制逻辑的硬件复杂度 一 方面 宽发射需要配套宽取指 即需要更准确和更宽1 的分支预测 这势必增加取 指部件和分支预测器的复杂度 另一方面 由于指令流中存在数据相关 控制相 关和资源相关 这要求硬件分析更大的指令窗口才能充分利用发射带宽 而指令 窗口加大以后 更新处在指令槽中的指令状态 寻找可并行执行的指令将导致流 水线在发射阶段的硬件逻辑变得十分复杂 甚至难以实现 图1 2 给出了超标量结 构中发射带宽对s p e cc p u2 0 0 0 程序的i p c i n s t r u c t i o n sp e rc y c l e 和硬件复杂 度的影响们 可以看出 发射带宽超过4 之后获得的i p c 提升非常有限 而控制逻 辑的硬件复杂度却成倍提高 目前大多数超标量处理器的发射带宽都是4 t 例如 m i p s l 2 0 0 0 1 1 0 l a l p h a 2 1 2 6 4 1 1 1 1 p a r s c8 7 0 0 1 1 2 1 p o w e r 3 0 3 等 对v l i w 处理器来说 表面上看 发射带宽的增加不需要硬件实现复杂的控 制逻辑 而是由编译器找出应用程序中的i l p 但是 在v l i w 处理器中 增加发 射带宽需要更大的寄存器文件来支持 该寄存器文件还必须提供更多的端口 以 便向更多的功能部件提供操作数 大的 多端口的寄存器文件不仅实现复杂 而 且访问延时也会增加 我们看到 从v l l w 结构发展为显式并行指令计算 1 e x p l i c i t l yp a r a l l e li n s t r u c t i o nc o m p u t i n g 简称e p i c 结构的i t a n i u m 1 6 17 处理器 更宽 的意思是分支预测器能够同时为更多的分支指令提供预测信息 第2 页 国防科学技术大学研究生院博士学位论文 只实现了6 发射 这个发射宽度己难以再提高 图1 2 发射带宽增加后s p e cc p u2 0 0 0 程序的 c 和硬件复杂度增长趋势 2 应用程序固有的i l p 处理器体系结构的优化主要受到以s p e cc p u2 0 0 0 评测为代表的传统科学技 术应用的驱动 这类应用大多具有较规则的控制流和较高的i l p 可以便现有的动 态分支预测器的预测精度达到9 0 以上 但是 并非所有的应用都有很高的i l p 一般而言 整型程序固有的i l p 较低 浮点程序固有的i l p 较高 许多研究表明 1 4 5 t 洲 处理器从传统的单指令流中实际能开发出的i l p 是非常有限的 使用 s p e c 9 2 基准程序 p o w e r p c6 2 0 的i p c 为0 9 6 1 7 7 8 发射的a l p h a 处理器能 维持的i p c 不到i 5 n p e n t i u mp r o 对s p e c 9 5 基准程序有类似的i p c 值 在0 6 弘2 之间 6 l 我们在8 发射a l p h a 处理器2 上对s p e cc p u2 0 0 0 进行了测试 得到的平 均i p c 为2 1 5 对于一些服务器应用 像商业的在线事务处理 o n l i n et r a n s a c t i o np r o c e s s i n g 简称o l t p 和决策支持系统 d e c i s i o ns u p p o r ts y s t e m s 简称d s s 其控制 流非常不规则 i l p 较低 在一台由4 个p e n t i n mp r o 组成的对称多处理器系统上 运行o l t p 工作负载测得的i p c 为0 2 9 在4 发射的a l p h a 2 11 6 4 处理器上运行 d s s 工作负载测得的i p c 不到0 8 0 n 3 存储延时 存储器的速度和处理器的速度之间存在巨大的差距 处理器的速度每2 年提 高一倍 而存储器的速度每6 年才提高一倍 在主频为3 0 0m h z 的a l p h a 2 11 6 4 处 理器上 主存储器的访问延时为8 0 个时钟周期 l s l 随着集成电路制造工艺的发展 2 处理器的其他配置见第三章的表3 2 由于该配置是针对同时多线程结构的 与真实的单线程超标量处理器 塑些 墨壁堑翌盟鏊虽型塑型墼兰 塑些 塑堡盟堡妄堕薹堡堑 第3 页 国防科学技术大学研究生院博士学位论文 存储器的访问延时会越来越长 甚至会达到上百个时钟周期 在当代处理器中 通过使用c a c h e 已经避免了大量的存储延迟 许多先进的技 术 如乱序执行 预取 非阻塞c a c h e 写缓存等 也可以消除或隐藏一部分存储 延时 然而 由于c a c h e 的强制性失效必定存在 访问存储器是无法避免的 对于 时间局部性和空阎局部性不好的程序 c a c h e 失效会更加严重 而从单个应用程序 寻找不相关指令来充满流水线中长达上百个时钟周期的存储延时槽是不可能的 因此处理器会经常出现停顿 不能充分利用宽发射槽提供的i l p 开发能力 根据 测算 传统处理器运行时间中常常有8 5 是在等待存储器提供数据i l 综上 由于受到硬件复杂度的影响 传统处理器的发射带宽不能太高 这就 限制了指令级并行的开发 其实 即便不考虑硬件复杂度 令发射带宽足够大 由于应用程序固有i l p 的限制和长存储延时的影响 从单个应用程序能够开发出 来的i l p 也是非常有限的 因此 靠进一步提高执行的并行度来提高处理器的性 能必须寻找其他的解决方案 1 1 2 线程级并行的发展机遇 1 集成电路制造工艺的发展 摩尔定律指出 单芯片上晶体管的数目每1 8 个月翻一番 在过去的三十几年 里 大规模集成电路制造技术的发展一直遵循这个原则 根据i t r s i n t e r n a t i o n a l t e c h n o l o g yr o a d m a p f o rs e m i c o n d u c t o r s 2 0 0 5 年的预测 2 0 到2 0 1 0 年 单芯片上 晶体管的数目将达到2 2 亿个 那么 如何有效地利用如此众多的硬件资源呢 比较直观的做法就是把原来在处理器芯片外部实现的功能模块集成到芯片 上 如片内集成大容量c a c h e f o 控制器 网络控制器 图形加速器等 这种做 法虽能让丰富的硬件资源得到利用 但并不非常有效 原因是采用这种做法所获 得的处理器性能提升并不明显唧 如果利用丰富的硬件资源来加强处理器的计算能力 那么处理器性能有望得 到大幅度提升 使硬件资源得到更加有效的利用 但是这种做法最终能否有效利 用硬件资源 提高处理器性能要看计算能力能否得到充分的发挥 要想充分发挥 处理器的计算能力 就要尽可能为处理器提供更多可并行执行的指令 然而 单 纯依靠开发指令级并行很难提供充足的指令 从而造成计算资源的极大浪费 因 此 必须考虑开发更高层次的并行 线程级并行正是很好的选择 2 应用需求的变化 进入2 l 世纪 处理器的市场己从以s p e cc p u2 0 0 0 评测为代表的传统的科 学技术应用 扩展到三类不同的应用 服务器应用 桌面应用和嵌入式应用 应 第4 页 国防科学技术大学研究生院博士学位论文 用的发展给处理器的设计带来的挑战主要体现在 新应用己从计算密集型转向数 据密集型 展现出与传统的科学技术应用完全不同的执行和数据访问行为 很多 新应用的数据访问的时间局部性和空间局部性很差 或者说很少有数据重用 单 纯开发指令级并行的传统单线程处理器处理这类应用的能力很差 需要新的结构 来适应新的应用变化 此外 以w e b 应用和在线数据库事务处理为代表的网络计算向传统的处理器 结构提出了挑战 s u n 公司在业界首先提出 多线程是网络计算最明显的特征 1 9 1 例如 w e b 应用负载是典型的多线程负载 当用户浏览或者点击网页时 就会引 发服务器运行一个线程 成千上万的用户 每次浏览或者点击都会引发无数的线 程 数据库应用负载则是单个应用产生多个线程的典型 把分类或者检索的工作 分散到多个线程上 可以显著提升获得结果的速度 对于这些线程级并行较高而 指令级并行较低的商业应用 传统的处理器不具性能优势 能够开发线程级并行 的处理器将是更好的选择 综上 集成电路制造工艺的快速发展和应用需求的不断交化为线程级并行提 供了发展机遇 1 1 3 线程级并行解决方案 由于通过开发指令级并行来提高执行并行度 进而提高处理器性能受到诸多 因素的限制 研究者和业界把目标指向了更高层次的并行 线程级并行 并提 出了许多有效的线程级并行解决方案 当前 线程级并行开发的技术途径主要有两大类 多线程 m u l t i t h r e a d i n g 简称m t 体系结构和单芯片多处理器 c h i pm u l t i p r o c e s s o r 简称c m p 结构 1 多线程体系结构 根据指令的调度执行方式可以把多线程体系结构分成三类 细粒度多线程 f i n e g r a i n e dm u l t i t h r e a d i n g 简称f m t 体系结构 2 l 2 s l 粗粒度多线程 c o a r s e g r a i n e dm u l t i t h r e a d i n g 简称c m t 体系结构 2 9 3 6 和同时多线程体系结 构 f m t 体系结构 又叫指令交错3 多线程体系结构 6 1 i m e d e a v e dm u l t i t h r e a d i n g 简称i m t 每个时钟周期都进行线程的切换 多个线程交替执行 同一个周期 只从一个线程发射指令到功能部件 理论上 f m t 通过有效的调度可以完全隐藏 存储延时 即在存储操作完成之前不从同一个线程取指 但是这就要求有足够多 对i n t c r l 嘲v e dm u l t i t h r e a d i n g 和b l o c k e dm u w t h r e a d m g 的翻译方法有很多种 如交叉多线程和阻塞多线程 堕里亟塑笪鳖 旦型垫盔堂塞堑耋堕盟塑堡直鎏 堂堕叁墨查耋塞墼囡 第5 页 国防科学技术大学研究生院博士学位论文 的线程可以调度 因此 f m t 处理器通常都支持非常多的线程 如d e n e l c o r h e p 2 1 2 2 1 h o r i z o n 2 3 和c r a ym t a l 2 5 i 都支持1 2 8 个线程 c m t 体系结构 又叫块交错多线程体系结构f 6 b l o c k e dm u l t i t h r e a d i n g 简 称b m t 连续执行一个线程的指令 直到遇到长延时操作才切换到另一个线程 因此 c m t 也是同一个周期只能从一个线程发射指令 与f m t 相比 c m t 并不 需要太多的线程 而且在线程切换发生之前 一个线程可以全速运行 但是e m t 中的线程切换时机非常重要 对这个问题的研究也非常多f 2 9 3 0 3 1 1 例如 m i t s p a r e l e l 3 2 1 和m s p a r e 3 3 1 使用了s w i t c h o n c a c h e m i s s 和刚t c h o n s i g n a l 动态切换模 型 c h o p p l l 3 4 1 使用的是s 谢t c h o n 稍c h e m i s s 动态切换模型 r h a m m a 3 5 j 6 l 则使用 了多种线程切换技术 同时多线程体系结构 每个周期把来自多个线程的指令发射到多个功能部件 去执行 已经没有线程切换的概念 如果单个线程没有足够多的指令可以并行发 射 那么就从其他线程中取出不相关的指令和这个线程中的指令同时发射执行 因此 同时多线程体系结构能够同时开发单个应用中的指令级并行和多个应用间 的线程级并行 i n t e l 公司提出的超线程 3 7 j 蜘 h y p e r t h r e a d i n g 简称h t 技术就 是同时多线程体系结构的一种变体 并被应用在x e o n 处理器 3 9 1 和p e n t i u m 4 处理 i 器r 4 0 e f t 2 c m p 结构 随着单芯片上晶体管数目的增加 在同一个芯片上集成多个处理器已经成为 可能 这就产生了单芯片多处理器f 4 1 的概念 单芯片多处理器把多个处理器核 放在同一个芯片上 通过在多个处理器核上并行执行多个线程开发线程级并行 每个处理器核都有完整的执行和系统结构资源 各处理器核通常共享片上c a c h e 例如 i b mp o w e r 4 处理器 4 5 删片内集成了两个p o w e r 3 处理器核 每个处理器核 拥有自己的一级指令c a c h e 和一级数据c a c h e 共享二级c a c h e 斯坦福大学研究的 h y d r a 4 7 4 s 在单个芯片上集成了4 个m i p s 处理器核 同样也是所有处理器核共享 二级c a c h e 典型的c m p 处理器还包括a m do p t e r o n 4 9 1 i n t e lm o n t e c i t 0 1 5 0 5 h p p a 9 9 0 0 1 2 1 s t l s o n yt o s h i b a i b m 发布的c e l l t 5 2 1 等 1 1 4 同时多线程体系结构的优势 在单线程处理器中 所有周期发射出去的指令都来自同一个线程 而由于单 个应用固有指令级并行性的限制 导致发射槽的空闲和执行资源的浪费 图1 3 a 给出了单线程超标量处理器中发射槽可能的浪费 每一行方格数表示一个周期内 最多可发射的指令数 即发射带宽 空白方格表示当前周期该发射槽没有指令可 第6 页 国防科学技术大学研究生院博士学位论文 以发射执行 填充的方格表示有指令可以发射执行 发射槽的浪费可以分成垂直 浪费和水平浪费1 3 如果某个周期所有的发射槽都空闲 这时称发生了垂直浪费 如果只有部分发射槽空闲 则称发生了水平浪费 不难看出 单线程处理器中既 存在垂直浪费 又存在水平浪费 垂直浪费是由长延时操作造成的 而水平浪费 是由指令级并行不够造成的 1 同时多线程v s f m t 和c m t 图1 3 b 和 c 分别给出了f m t 和c m t 中发射槽的使用情况 f m t 和c m t 通过线程切换可以隐藏存储延时 因此减少了发射槽的垂直浪费 可是由于f m t 和c m t 在同一个时钟周期里只能从一个线程发射指令 因此指令级并行不足造成 的水平浪费仍然存在 图1 3 发射槽使用情况示意图 在s m t 体系结构中 每个周期可以发射来自不同线程的指令去执行 通过线 程级并行来弥补单线程指令级并行的不足 从而减少水平浪费 此外 当某个线 程因为长延时操作导致无法发射指令时 可以选择发射其他线程的指令 通过隐 藏延时来减少垂直浪费 图1 3 d 给出了s m t 处理器中发射槽的使用情况 可以 看到 s m t 极大地降低了发射槽的浪费 从而能够更好地提高执行资源的利用率 和处理器的性能 由于s m t 相对于f m t 和c m t 具有明显的性能优势 所以f m t 和c m t 已 经逐渐淡出 s m t 则成为多线程体系结构领域的研究热点 2 同时多线程v s c m p 图1 3 e 给出了c m p 处理器中发射槽的使用情况 在c m p 处理器中 发射带 宽静态地划分给每个处理器核 通过多个线程在多个处理器核上的并行执行来开 发线程级并行 从而减少发射带宽的水平浪费 如果没有足够的线程级并行 即 线程数目小于处理器核的数目 那么有些处理器核会完全处于空闲状态 造成极 第7 页 国防科学技术大学研究生院博士学位论文 大的资源浪费 此外 如果每个处理器核都是单线程的 那么单线程处理器中的 资源浪费问题在c m p 处理器中仍然存在 因此 从资源利用率的角度考虑 s m t 要优于c m p 然而 c m p 却有其自身的实现优势 比如 每个处理器核相对仍简 单 易于获得较高主频 利于设计重用 缩短设计和验证时间等 鉴于s m t 和c m p 各有所长 3 s 3 s 4 s s l 使用多个s m t 处理器核来构建c m p 将 是一种很好的选择 业界的发展也证明了这一点 l b m 在2 0 0 1 年发布的p o w e r 4 处理器是一款双核处理器 每个处理器核都是一个单线程的p o w e r 3 处理器 而在 2 0 0 4 年发布的p o w e r 5 处理器p 6 j 则结合了s m t 和c m p 的优点 片上集成了两个 处理器核 每个处理器核都是一个同时多线程处理器 无独有偶 a l p h a2 1 3 6 4 l s t s g l 中只采用了c m p 技术 而在a l p h a 2 1 4 6 4 5 9 1 中则同时采用了c m p 和s m t 技术 多核多线程将是未来处理器的主流结构 而s m t 作为多核多线程结构中的关 键技术已经引起了国内外科研院所和公司的广泛关注 围绕s m t 体系结构也展开 了大量的研究和探索 美国的华盛顿大学 6 0 6 1 6 2 1 加州大学 6 3 硼 马里兰大学 6 8 6 9 3 0 7 1 威斯康星大 学 7 2 7 3 斯坦福大学 密歇根大学 7 4 7 5 1 麻省理工 7 6 7 7 北卡罗莱州大学 7 8 1 西 班牙的u p c 大学 7 9 8 0 g l 英国的曼彻斯特大学 日本的东京大学等对s m t 体系结 构展开了深入的研究 8 2 8 3 h 8 5 1 国内的中科院计算技术研究所 8 6 8 7 8 蚋 中国科技大 掣8 9 1 哈尔滨工业大学 9 0 9 1 1 西北工业大学 9 2 1 国防科技大学 9 3 9 6 等也都对s m t 体系结构展开了研究 并给出了大量有参考价值的技术和结论 s m t 体系结构也受到了业界的青睐 许多主流商用处理器厂商都相继推出了 s m t 处理器产品 主要包括 i n t e 的p e n t i m u 4 和x e o n 处理器 c o m p a q