（计算机科学与技术专业论文）循环阵列处理器体系结构的关键技术研究与实现.pdf

国防科学技术人学研究生院学位论文 摘要 半导体工艺技术的进步推动着体系结构设计技术的革新。综合考虑连线延迟、时钟频 率和设计验证代价，基于线程级并行的技术成为研究热点，其中的单芯片多处理器( c m p ) 体系结构以其简单、高效的优点具有广阔的发展前景。 循环阵列处理器( l e a p ) 体系结构，提出了一种基于固定指令多数据流模型，用于 加速最内层循环程序执行的c m p 体系结构，其设计实现还处于起步阶段，本文主要对三 个方面的关键技术进行了研究。 在c m p 体系结构中，存储器访问速度是影响整体执行性能的瓶颈，本文详细分析了 现有的存储模型、c a c h e 层次设计技术、编址方式、通信机制，并分析了三种新的c a c h e 设计技术，提出了l e a p 存储系统的整体结构模型，进行了算法设计。结合l e a p 访存的 具体特点，我们提出了数据打包传递技术和按访存规律预取的技术。在f p g a 设计环境中 模拟运行了f f t 核心循环，实验表明该技术可以有效降低带宽需求，减少网络冲突。 针对原有l e a p 程序只能执行最内层循环，所能执行程序范围非常有限的缺点，增加 其对多层循环自动加载和执行机制的支持。本文在分析现有的l e a p 单层循环自动执行机 制的基础上，分析了循环间数据相关和控制相关的解决方案，提出了多重循环调度策略， 实现了多层循环自动加载机制。 基于f p g a 芯片，开展了硬件实现与优化技术研究。从节省器件数量的角度，对原有 的计算单元进行了代码优化，优化后的硬件不产生器件冗余，且速度提高。 最后，根据上述设计思想和关键技术，实现了f i r 滤波器硬件加速部件，并在x i l i n x 公司的v i r t e x 2 芯片上综合实现。 关键词：单芯片多处理器，芯片内存储系统，循环硬件自动执行，硬件综合优化 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t t h ed e v e l o p m e n to fc i r c u i t i n t e g r a t i o ng r e a t l yp r o m o t e s r e n o v a t i o no f c o m p u t e r a r c h i t e c t u r e c o n s i d e r i n g w i r e d e l a y , c l o c kf r e q u e n c y , c o s t o fd e s i g na n d v a l i d a t i o n ， m u l t i t h r e a d i n gp a r a l l e l i s mi sp o l u p a ru s e d ，e s p e c i a l l yt h eo n ec h i pm u l t i p r o c e s s o r sa r c h i t e c t u r e ， a c c o r d i n gt oi t ss i m p l ea n dh i g he f f i c i e n c y t h el o o pe n g i n eo na r r a yp r o c e s s o r s ( l e a p ) ，w h i c hr a i s e df i x e di n s t r u c t i o nm u l t i p l ed a t a m o d e lt oa c c e l e r a t e l o o pp r o g r a m ，i s ao n ec h i p m u l t i p r o c e s s o r s ( c m p ) a r c h i t e c t u r e n o w l e a p ss t u d yi sj u s tb e g i n n i n g ，t h ep a p e rw i l l o u t s p r e a dr e s e a r c h e sa i m e da tt h r e ek e y t e c h n i q u e s 。 f o rc m pa r c h i t e c t u r e ，t h em e m o r ya c c e s s i n gs p e e da f f e c t st h ew h o l ep e r f o r m i n g e f f i c i e n c y i nt h i sp a p e rw eh a v ead e t a i l e ds t u d yo ft h em e m o r ym o d e l s ，h i e r a r c h i c a lc a c h e d e s i g n s ，o r g a n i z a t i o n sf o rt h ea d d r e s ss p a c e ，c o m m u n i c a t i o nm o d e l sa n ds o m en e w c a c h ed e s i g n t e c h n o l o g i e s ，a n d t h e n b r i n g f o r w a r dt h e d e s i g np r o j e c t o ft h el e a p s m e m o r y s y s t e m c o n s i d e r i n ga b o u tl e a p ss p e c i a l t i e s ，w ea d o p tt h ed a t ap a c k e dt e c h n o l o g ya n dp r e f e t c h a c c o r d i n gt om e m o r ya c c e s s i n g sr u l e t h r o u g hr u n n i n gf f to nf p g a ，i ti sp r o v e dt h a tt h e t e c h n o l o g yc a ne f f e c t i v e l yr e d u c et h em e m o r ya c c e s s i n g sd e l a y , e c o n o m i z em e m o r yw i d t h a i m i n ga tt h es h o r t a g et h a tt h e o l dl e a pc a no n l yr n ns i n g l e l a y e rl o o p ，w h i c hg r e a t l yl i m i t t h ek i n d so fp r o g r a m si tc a nr e f o r m w ew i l le n h a n c et h el e a pt od i nm u l t i - l a y e r sl o o p i nt h i s p a p e rw es t u d yt h ed a t ah a z a r d sa n dc o n t r o lh a z a r d si nl o o p ，a m e l i o r a t i n gt h eo l dc o d et or e a l i z e t h ea u t o m a t i cp e r f o r m i n go f m u l t i l a y e r sl o o p c a r r y i n go u tt h er e a l i z i n ga n do p t i m i z i n go fh a r d w a r eo nf p g a o p t i m i z i n gt h eo l dp e c o d et oe n o n o m i z ec i r c u i tc o m p o n e n t s ，t h ec o d eb e i n go p t i m i z e dc a nb es y n t h e s i z e dw i t h o u ta n y c o m p o m e n t sr e d u n d a n c y f i n a l l y , c o m b i n i n gt h et h r e ep a r t s ，w er u nf i rp r o g r a m s ，a n ds y n t h e s i z eo nv i r t e x 2c h i po f x i l i n xc o m p a n y k e yw o r d s ：o n ec h i p m u l t i p r o c e s s o r s ，m e m o r ys y s t e mo nc h i p ，a u t o m a t i cr e f o r mo f l o o p ，s y n t h e s i z ea n do p t i m i z eo fh a r d w a r e 第1 1 页 国防科学技术大学研究生院学位论文 图目录 图2 1c m p 和s m t 的指令提取6 图2 2 示例程序在单芯片阵列处理器上的映射和数据流图9 图2 3l e a p 整体结构示意图10 图2 4m u l t i s c a l a r 的执行机制一1 1 图2 5g p a 整体结构示意图1l 图3 1u m a 多处理器模型1 4 图3 2n u m a 多处理器模型1 5 图3 _ 3c o m a 多处理器模型1 5 图3 4c c n u m a 多处理器模型1 6 图3 5 消息传递多计算机一般模型1 7 图3 6 共享一级c a c h e 1 7 图3 7m a p 体系结构18 图3 8 共享二级c a c h e 一1 9 图3 9h y d r a 处理器的结构图2 0 图3 1 0 共享主存储器2 1 图3 1 1d s m 系统的组织结构示意图2 l 图3 1 2 四个存控互连的拓扑结构图2 6 图4 1存控整体结构示意图2 7 图4 2 本地请求执行流程图2 9 图4 3 其他存控请求的执行流程图2 9 图4 4c a c h e 查询执行示意图一3 0 图4 5c a c h e 替换操作的执行流程3 l 图4 6 本地仲裁的执行流程3 2 图4 7c a c h e 中数据流向仲裁器的执行一3 3 图4 8 将请求发送给外地存控的仲裁过程_ 3 3 图4 9 请求发送给本地存储体的仲裁过程3 5 图4 1 0f f t 核心循环的数据流图4 0 图4 1 1 两种c a c h e 设计技术的带宽需求比较图4 2 图5 1 单层循环自动执行4 4 图5 2 循环控制部件执行流程4 4 图5 3 三重循环自动执行状态机4 7 图6 1x s t 的综合结果5 0 图6 2 源程序的综合结果5 l 第i v 页 国防科学技术大学研究生院学位论文 图6 3一次优化后综合效果图 图6 4 二次优化后综合效果图 图7 1f i r 程序在l e a p 上的数据流图 图7 2f i r 算法存储系统连接示意图 图7 3 综合效果图 第v 页 铊够卯弼 国防科学技术大学研究生院学位论文 表目录 表1 1 计算机系统的分类及其系统特征2 表2 1c m p 和s m t 的比较一7 表2 2m u l t i s c a l a r 、g p a 和l e a p 的比较12 表4 1p e 的功能实现及其访存规律4 l 表6 1 程序优化前后所用器件数比较5 0 表6 2 计算部件优化前后所用器件数比较5 4 表7 1 计算部件访存情况5 6 表7 2f i r 算法所用器件数5 7 第i v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：煎堡睦到矬垄i 星体歪缱煎笪差缝垫盔班塞当塞墨 学位论文作者签名 重吐 日期：2 卯啦年t 1 月传日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：煎竖睦到缝堡墨篮丕箜擅鲍羞筵垫盔盟毽生塞理 日期：p 面牛年f j 月圬日 日期：枷仟，月旷日 国防科学技术大学研究生院学位论文 第一章绪论 近年来，微处理器芯片设计已成为一个热点话题，微处理器设计技术在工艺进步的推 动和应用需求的刺激下，经过3 0 余年的发展，已形成了种类繁多、性能与功能各异的百 花齐放的局面。本课题就是在对微处理器的现状与发展趋势研究的基础上展开的。 1 1 工艺进步对微处理器结构的影响 最早的微处理器i n t e l4 0 0 4 出现在7 0 年代初期，只有4 位字长，其结构也相当简单， 只有2 3 0 0 个晶体管。而那个时代大型计算机的c p u 体系结构已经有了长足的发展，采用 了流水线【1 、动态调度、并行等提高性能的方式，实现上也很复杂。可以说，微处理器最 初的出现，完全是因为半导体集成电路工艺的进步。 时至今r ，电路集成工艺的大幅度提高，迫切要求人们设计出新型的体系结构以充分 利用片上资源，其中主要要考虑的问题为信号传输延迟、时钟频率和设计复杂性【2 】： 1 集成度提高意味着线宽变窄，从而信号在片内传输单位距离所需的延迟也相应增 大( 当然另一方面也缩短了各功能单元之间的距离) 。 2 处理器的时钟频率呈指数级提高，带来了功耗的不断增大。 3 随着微处理器设计抽象级别的不断提升，一些较好的可以自动实现综合和布版的 工具已经诞生。然而，要实现较高的执行效率，仍然需要设计者自行考虑晶体管 的布局。日益复杂的设计和验证问题，使人们越来越感到难以承受。 为了解决上述问题，微处理器设计越来越强调结构的层次化、功能部件的模块化和分 布化，即每个功能部件都相对简单，部件内部尽可能保持通信的局部性。微处理器体系结 构的变革势在必行! 1 2 应用对微处理器结构的影响 进入2 1 世纪，计算机市场己从以s p e cc p u 2 0 0 0 为代表的传统应用，转向了三类不 同的应用：服务器应用，桌面应用，和市场增长最快的部分嵌入式应用。 1 当前的服务器应用以商用事务处理和w e b 服务为主，可用性、可扩展性、高吞吐 率是系统设计的关键。 2 桌面应用包括低端的p c 和高端的工作站，其中多媒体应用占9 0 以上，强调计 算、图形和交互性能，价格性能的优化是设计的关键。 3 嵌入式应用的性能和成本范围十分广泛，从简单的、只支持固化应用程序的8 位 1 6 位微控制器，到具有强大的图形图像和流媒体处理能力的3 2 位6 4 位微处理器 或数字信号处理器。价格和低功耗是嵌入式系统设计的关键，其性能要求多体现 为对实时处理的要求。 表1 1 给出了当前计算机系统的分类及其系统特征。 第1 页 国防科学技术大学研究生院学位论文 表1 1 计算机系统的分类及其系统特征 系统特征服务器 桌面嵌入式 $ 1 0 - $ 1 0 0 ，0 0 0 ( 仅包括高端网络 系统的价格 $ 1 0 ，0 0 0 - $ 1 0 ，0 0 0 ，0 0 0 $ 1 0 0 0 $ 1 0 0 0 0 路由器) $ 2 0 0 一$ 2 0 0 0$ 1 0 0 $ 1 0 0 0$ o 2 0 - $ 2 0 0 微处理器的单价 概念上的平均价格为$ 1 0 0 - 一5 0 0概念上的平均价格为$ 5 每年的销量( 据2 0 0 0 3 0 0 ，0 0 0 ，0 0 0 ( 仅包括3 2 位和6 4 4 ，0 0 0 ，0 0 0 1 5 0 ，0 0 0 ，0 0 0 年估计)位处理器、 可用性，扩展性，吞吐价格- 性能，多媒体，图 关键的系统设计问题 价格，功耗，面向应用的性能 量 形性能 1 3 微处理器的研究现状 目前，在桌面计算领域，i n t e l 公司的p e n t i u m 系列微处理器芯片【3 】领导了市场的主流， 占据着微机芯片市场的绝大部分份额，当前主流的芯片配置是3 2 位的p e n t i u mi v 。2 0 0 1 年8 月i n t e l 采用0 1 8 9 m 工艺实现了主频为2 g h z 的p e n t i u mi v 芯片，目前生产的p e n t i u m i v 芯片则大都采用0 1 3 9 m 工艺，主频已超过3 g h z 。a m d 公司的a t h l o nk 系列微处理器 与i n t e l 的p e n t i u m 系列二进制兼容，是i n t e l 公司的强劲对手，现在的a m d a t h l o n 处理器 的主频也超过了1 g h z ，并且即使频率略低，在实际性能上却并不逊色。a m d 的a m d 6 4 处理器，在实现与i a 3 2 兼容的同时，支持全6 4 位计算，更展示了强劲的潜力。另外， v i a 公司通过购并c y r i x 公司，也开始生产与p e n t i u m 系列二进制兼容的微处理器芯片。 目前，v i a 的c 3 芯片已开始进入桌面系统的低端市场。 i b m 4 、h p ( c o m p a q ) 、s g i 、s u n 等公司都生产各具特点的服务器用高性能通用 微处理器，这些微处理器都采用r i s c 指令系统，通过超标量、乱序执行、动态分支预测、 推测执行等机制，提高指令级并行性，改善性能。这类芯片被广泛应用于各种工作站、服 务器和高性能计算机中。 另外，i n t e l 和h p 公司早在1 9 9 4 年就启动了设计和生产基于e p i c 显式并行体系结构 的i a 一6 4 5 ，6 1 芯片合作项目，并陆续推出了i t a n i u m 和i t a n i u mi i 处理器。有人预计到2 0 0 4 年，i a 一6 4 对服务器市场的占有量将全面超过r i s c ，以后i a 6 4 标准也会形成，i n t e l 将会 主导这个标准。但是这些并不意味着i a 6 4 将最终代替r i s c 体系结构而一统天下。i n t e l 自己估计，要到2 0 0 5 甚至2 0 1 0 年，基于i t a n i u m 的6 4 位的计算平台才会成为主流。同时， i b m 、s u n 等一些实力雄厚的公司，仍在继续发展新的基于r i s c 体系结构的芯片。 传统上，通用微处理器的工作负载以非数值、不规则标量应用为主，实现高性能的方 第2 页 国防科学技术人学研究生院学位论文 法主要是开发指令级并行性( i l p , 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 n t e lx 8 6 为代表的c i s c 体系结构以超流水结构为提高性能的主要手段给人们留下了深刻的印象，这种结构将指令 流水线划分成更简单的流水级以提高时钟速率。目前，p e n t i u mi v 的流水线级数对定点运 算已达2 0 级，浮点运算达到2 9 级，处于执行状态的指令数达到1 2 6 条。而r i s c 芯片则 采用超标量结构作为提高处理器性能的主要手段，这种结构在指令界面上保持与r i s c 结 构兼容，但在内部由硬件做动态调度，实现多个操作的并行执行。为了进一步提高性能， c i s c 与p i s c e 微处理器在发展的过程中都从对方借鉴了很多东西，两者在体系结构上的 界限己越来越模糊【8 】。r i s c 微处理器在进入后r i s c 时代以后，其性能的进一步提高，已 不再是通过体系结构的创新得到的，而是用提高复杂度换来的。这种以复杂度换取性能的 做法现在已达到收益递减点，即每个时钟周期提取的指令多于4 条后，系统获得的并行性 收益已越来越少 9 】。 1 4 微处理器的发展趋势 当前，通用微处理器体系结构正面l | 缶着新的挑战和创新机遇。一方面，集成电路仍将 按摩尔定律持续高速发展，预测到2 0 1 1 年，单片上可集成的晶体管数将达到1 4 亿个，芯 片的特征尺寸为5 0 纳米，芯片的引脚数可达到6 5 3 2 个 1 0 ，1 1 1 。为了进一步开发应用问题 中的并行性，有效地利用集成度的提高带来的海量晶体管资源，提高微处理器的性能，降 低功耗，学术界和工业界开展了多个方面的研究与探索工作，这些工作基本上可以分为如 下几类【1 2 】： ( 1 ) 通过进一步提高复杂度来提高性能。这种方法沿袭传统的指令级并行方法来加 速单线程应用，目标在于进一步挖掘单个应用内在的i l p ，这方面的代表性研究工作有美 国m i c h i g a n 大学提出的a d v a n c e ds u p e r s c a l a r 1 3 1 处理器，c 锄e g i em e l l o n 大学提出的 s u p e r s p e c u l a t i v e 【1 4 】处理器，w i s c o n s i n m a d i s o n 大学提出的t r a c e 处理器【1 5 ，1 6 】和 m u l t i s c a l a r 1 7 ，1 8 ，1 9 处理器。这些研究共同的思想是组织更宽的超标量，采用更多的功能 部件，多级c a c h e 和贪婪的数据、控制和指令轨迹预测，达到使用尽可能多的i l p 。在这 类研究中提出的t r a c ec a c h e 2 0 ，2 1 技术现已用在了i n t e lp e n t i u mi v 处理器中。 ( 2 ) 用软件的复杂性换取硬件的简单性的显式并行的方法。这种方法运用所谓“大编 译”的设计思想，依靠编译器的努力，从应用中提取尽可能多的“显式并行性”，用超长指令 字( v l i w ) 2 2 ，2 3 来表示可以并行执行的指令，从而大大简化了在传统的超标量处理器 中为实现高度的指令级并行而需要增加的复杂的控制逻辑。i n t e l h p 公司的i a 6 4 、俄罗斯 e l b r u si n t e r n a t i o n a l 公司的e 2 k ，以及t r a n s m e t a 公司的c r u s o e 微处理器都采用了这一设 计思想来降低芯片的复杂度和功耗。这一办法的主要问题是：一、会增加软件( 即编译器) 的复杂性；二、有些相关( 如访存地址相关) 在编译时是无法确定的。此外，当指令宽度 进一步加宽后如何维护兼容性也是一个问题。 ( 3 ) 通过开发线程级并行( t l p , t h r e a d 1 e v e lp a r a l l e l i s m ) 或进程级并行( p l r 第3 页 国防科学技术大学研究生院学位论文 p r o c e s s l e v e lp a r a l l e l i s m ) 来提高性能，以简化硬件设计。代表性的工作有w a s h i n g t o n 大学 的同时多线程( s i m u l t a n e o u sm u l t i m r e a d i n g ，简称s m t ) 处理器和s t a n f o r d 大学的单芯片 多处理器( c h i pm u l t i p r o c e s s o r s ，简称c m p ) h y d r ac m p 2 4 ，2 5 1 。目前，i n t e l 已宣布将在 其x 8 6 芯片中采用s m t 技术，而i b m 的p o w e r 4 芯片和s u n 的m a j c 芯片则采用了c m p 结构。 今后，线程级并行技术将得到广泛发展，主要有如下两点原因 2 6 ，2 7 1 ： 1 传统的指令级并行技术存在自身无法克服的缺陷：一方面单个应用内在的i l p 是 有限的，提高性能的潜力很快就会达到极限；另一方面指令预取、指令乱序执行 等技术的使用导致硬件复杂度过高，使得一个完整的通用芯片的设计、验证和测 试成本变得令人难以接受 2 8 1 。 2 未来的多媒体技术和科学研究，如：计算化学，流体力学等，对计算量的需求将 大幅度增加，采用传统的单处理器系统已经不能满足需求，同时，硬件的支持解 决了在编译阶段检查存储相关这一难题，更加有利于实现线程级并行。 1 5 本课题的背景及主要研究任务 随着微处理器的蓬勃发展，各种新型的体系结构应运而生。本课题的研究基础循环阵 列处理器l e a p ( l o o pe n g i n eo na r r a yp r o c e s s o r ) 体系结构就是在这样的大背景下提出的 一种单芯片阵列处理器体系结构。本课题来源于“十五”国防预研：科学计算大规模并行 处理技术。其主要任务是在现有的l e a p 体系结构基础上，对以下三个关键技术进行研究 与实现： 1 循环阵列处理器片内存储系统的设计与实现； 2 多层循环自动执行机制的研究与实现； 3 基于f p g a 芯片的硬件逻辑实现与优化。 1 5 1 循环阵列处理器片内存储系统的设计与实现 前面已经提到，线程级，进程级并行技术可以大大提高处理器内部指令执行的并行度， 但是整个程序执行的速度还要受限于存储系统的数据供应速度。研究表明：处理器与存储 器性能的差距仍在以每年5 0 的速度增大，访存速度成为影响处理器性能提高的主要瓶颈。 根据目前的技术发展趋势，不久就会出现当处理器发射数百甚至上千条指令时只能取进一 个数据到片上存储器的情况。基于对上述事实的观察以及未来半导体技术所提供的能力， p i m ( p r o c e s s o r i nm e m o r y ) 处理器与存储器做在同一块芯片上，这样可使访存延时减少5 1 0 倍以上，存储器带宽增加5 0 一1 0 0 倍以上 3 0 】。在大多数情况下，整个应用在运行期问都可 放到片上存储器里。对于l e a p 体系结构，同样需要设计一个片上存储系统，以缓解存储 系统和计算部件之间的速度差距，这是本课题研究的重点。 第4 页 国防科学技术大学研究生院学位论文 1 5 2 多层循环自动执行机制的研究与实现 原有的l e a p 体系结构只能支持最内层的核心循环，而不能自动加载多层循环。这使 得在处理多层循环时，要首先对原程序进行改造，改造成单层循环，或者多次调用l e a p 。 在程序实际运行中，这一过程显然是不能接受的。要使l e a p 真正成为一个好用的处理器， 必须要实现其对多层循环自动加载机制的支持。 1 5 3 基于f p g a 芯片的硬件逻辑实现与优化 l e a p 采用的是c m p 体系结构，即在一块芯片上集成多个计算单元。我们希望每块芯 片上集成的计算单元的数量尽可能的多，那么就要求每个计算单元在保证正确执行预期功 能的前提下，其硬件结构尽可能的简单。这就对程序的代码风格提出了一定的要求，要对 原有的从纯逻辑角度编写的代码进行优化，使其生成的网表不出现器件冗余。 第5 页 国防科学技术人学研究生院学位论文 第二章循环阵列处理器体系结构 我们的研究工作都是在循环阵列处理器l e a p 的基础上展开的，所以在理解整个课题 前，对l e a p 的理解必不可少。同时，l e a p 采用的是现在被普遍看好的线程级并行技术， 并采用了硬件结构相对简单的c m p 体系结构。所以，要充分理解l e a p 的执行机制，首 先要从线程级并行体系结构说起。 2 1 线程级并行体系结构 现有的线程级并行体系结构中，单芯片多处理器( c h i pm u l t i p r o c e s s o r s ，简称c m p ) 和同时多线程( s i m t i o u sm u l t i t h r e a d i n g s ，简称s m t ) 技术是研究的主流，现将这两种体系 结构进行比较说明。 2 1 1c m p 和s m t c m p 3 1 ，3 2 ，3 3 1 的基本思想是在单个芯片上集成两个或两个以上结构相同的处理器，并 行执行多个线程。 s m t 3 4 ，3 5 ，3 6 1 是将超标量与多线程相结合的技术，在硬件上保留着很多线程的执行现 场，以指令发射槽的并行粒度加速多个线程的执行，最大可能地实现宽发射、乱序的超标 量处理，提高运算部件的利用率，缓和由于数据之间的依赖关系或c a c h e 命中失效带来的 访存延时，所付出的代价是增加了发射和控制逻辑的复杂性。当没有多个线程可用时，s m t 处理器看上去如同传统的宽发射超标量处理器一样。 图2 1 所示为并行执行四个线程时， i | | i l i l i f j | 4 c m p 和s m t 的指令调度过程。 i 匿】【煎团匝 卓蘼率翮 u 一雌u 划 巨划l u 恒u 燮l u 一 倒龋幽 煎【l q ul 旦倒迪l j 图2 1c m p 和s m t 的指令提取 从图中可以看出，s m t 是同时对四个线程进行指令调度，而c m p 是将每个线程分别 分配给一个处理器，当某个线程可以执行时，就进行指令提取。s m t 可以实现真正意义上 的处理器无空转执行，而c m p 不能完全实现延迟隐藏。但是，s m t 为了实现无空转指令 调度，不得不采用相对复杂的硬件设计，表2 1 对这两种体系结构进行了比较。 第6 页 国防科学技术大学研究生院学位论文 表2 1 c m p 和s m t 的比较 s r rc l p 硬件复杂度采用了分支预测，寄存器重命不需要复杂的实现机制，硬 名，乱序取指等机制，硬件复件实现简单。 杂。 芯片面积所需芯片面积较大芯片面积与处理器个数呈 线性关系 所需寄存器数量大，端口多较少 连线延迟对程连线延迟较长，降低了时钟频延迟短，只需要较短的时钟 序执行周划的率，程序执行要较长的时钟周周期 影响期 体系结构验证验证代价大只需验证每个处理器，代价 较小。 资源利用真正实现并行，没有资源浪费。存在资源浪费的现象 从纯粹的体系结构观点来看，s m t 处理器的灵活性是非常出色的。但是，当半导体工 艺进入0 1 8 微米以后，线延时已经超过了门延迟，要求微处理器的设计通过划分为许多规 模更小，局部性更好的基本单元结构来进行。相比之下，c m p 采用相对简单的硬件设计， 获得了相对较好的执行效率。一般情况下，如果代码可以被分成各个线程，由c m p 中各 个小的、执行效率较高的内核协同完成，比一个时钟周期提取多条指令的复杂的s m t 和 s u p e r s c a l a r 执行效率高。同时，c m p 中高效的执行内核与数据c a c h e 紧密相连，获得了更 高的时钟频率和更短的时钟周期。当然，c m p 也存在不足之处，如果一个应用不能有效地 被分解成多个线程，则它在c m p 处理器上运行的效率就很低。 总之，由于c m p 简单、高效，更有发展前途。所以，循环阵列处理器l e a p 采用了 c m p 体系结构。 2 1 2c m p 的研究现状 随着c m p 设计技术的蓬勃发展，涌现出了许多c m p 处理器。 1 9 9 4 年，t i 公司推出了t it m s 3 2 0 c 8 x 3 7 ，3 8 数字信号处理器，其基本结构包括：( 1 ) 哈佛结构；( 2 ) 流水线操作；( 3 ) 专用的硬件乘法器：( 4 ) 特殊的d s p 指令。这是一种特 别适合于进行数字信号处理运算的微处理器，其主要应用是实时快速地实现各种数字信号 处理算法。 1 9 9 5 年c a m b r i d g e 大学提出的mm a c h i n e 处理器，使用两种机制保证内部结点的流量： v e r t i c a lt h r e a d s ( v - t h r e a d s ) 和h o r i z o n t a lt h r e a d s ( h t h r e a d s ) ，可以同时开发指令级并 第7 页 国防科学技术大学研究生院学位论文 行和线程级并行。 1 9 9 8 年s t a n f o r d 大学设计了h y d r a 处理器用于验证c m p 体系结构的设计代价和执行 状况。h y d r a 处理器在一块芯片上集成了四个一个时钟周期提取两条指令的s u p e m c a l a r 处 理器。当时设计出的h y d r a 是非常昂贵的，将很多高速的s r a m 和d r a m 存储系统集成 于h y d r o 芯片上，其特殊之处为采用了共享二级c a c h e 的设计方式。 2 0 0 1 年，美国t e x a s 大学计算机体系结构实验室提出了g r i d 3 9 体系结构。g p a 与 传统的体系结构相比，允许更高的时钟频率，在一般的工作负担下，可以实现更高的指令 级并行以达到更好的执行效率。 d e c ( 数位计算设备公司) 推出的a l p h a 2 1 3 6 4 能够利用编译时和运行时的信息开发线 程级并行。a l p h a 4 0 ，4 1 ，4 2 是为广泛范围的商业应用设计的。同时，多线程是a l p h a 无序 指令执行的自然扩展，它也是在大多数应用负载下利用显性并行的最有效机制。 i b m 的p o w e r 4 处理器也采用了c m p 体系结构。p o w e r 4 被公认为是第一种“单片服务 器”，它由两个1 g h z 以上的处理器、一个大带宽系统交换开关、一个大容量内存高速缓 存和f o 接口组成。 为充分发挥c m p 和s m t 体系结构的优点，克服其不足。美国i l l i n o i s 计算机科学实 验室提出了集群式体系结构 4 3 ，这是一种将c m p 和s m t 相融合的体系结构设计技术。 每个芯片上有独立的处理器部件，每个处理器部件按照s m t 的执行机制工作，即可以同 时调度多个线程。集群式体系结构只是在芯片上复制一些取指带宽较低的s m t ，所以很容 易设计。同时，对处理器部件的划分在一定程度上限制了资源共享。研究证明，集群式体 系结构具备集中控制的s m t 体系结构的全部优点。 2 2 循环阵列处理器体系结构 下面，从提出背景、设计思想和硬件结构三个方面，对循环阵列处理器l e a p 体系结 构进行说明。 2 2 i 提出背景 循环阵列处理器体系结构l e a p ( 4 4 ，4 5 】) 是一种用于加速循环程序执行的c m p 体系结 构，其提出的背景是基于体系结构研究的如下现状： l - 在多媒体处理等许多应用领域，循环是程序的核心，几乎占整个程序运行中9 0 以上的时间( 【4 6 ，4 7 】) ，所以，循环程序执行速度的提高是提高整个程序执行效率的 关键。 2 超大规模集成电路技术的进步使线程级并行技术，成为研究的热点。 3 单芯片多处理器( c m p ) ，以其简单、高效的优点，日益成为线程级并行处理器领 域一种非常有前途的体系结构组织方式。 第8 页 国防科学技术大学研究生院学位论文 2 2 2 固定指令多数据流模型 为加速循环程序执行，我们提出了固定指令多数据流f i m d ( f i x e di n s t r u c t i o nm u l t i p l e d a t a ) 计算模型，其设计思想为：将循环体中的每个表达式固定分配给一个计算单元，由 循环控制部件约束数据之间的相关流动，计算单元在数据驱动下，自主推动循环程序的执 行。下面用一个简单的例子，迸一步说明其执行过程( 其中a ，b 和c 为数组变量，1 1 1 和 n 为常量) 。 f o r ( i 2 0 ；i 6 4 ；i + + 、b e g i n a 【i 】= b i 一1 + _ m ； c i 】2 a i 】+ n + c 【i 】； e n d 计算这个简单循环需要四个计算单元( 分别标识为p e 0 、p e l 、p e 2 和p e 3 ) ，其执行 的功能分别为( 其中，j 和数组p 为引入的中间变量) ： p e 0 ：j = i 一1 ： p e l ：a i 】= b d 】+ m ； p e 2 ：p 【i 】= a 【i 】+ n ： p e 3 ：c 【i 2 p 【i 】+ c 【i 】； 其数据流如图2 2 所示： 2 2 3 硬件结构 图2 2 示例程序在单芯片阵列处理器上的映射和数据流图 l e a p 的整体结构如图2 3 所示。在一块芯片上集成了多个计算单元组成的计算阵列， 计算单元只是一个具有指令和操作数存储功能的a l u ，这样设计有利于提高处理器的时钟 频率。计算单元采用数据驱动思想，当操作数就绪，指令就控制a l u 执行相应的运算。 每个计算单元内部设置多个操作数缓存，同时允许多条取操作数请求发出，实现了计算与 第9 页 国防科学技术大学研究生院学位论文 存储操作的重叠，有利于克服存储访问长延迟的固有特性。计算单元之间通过高速通道连 接。设置有循环控制部件，支持最内层循环直接映射到循环阵列上执行。能够有效开发循 环内部的语句级并行和循环间的循环片级并行。 图2 3l e a p 整体结构示意图 计算 单元 h o s t 是通用微处理器，与阵列处理器共享主存储器，存储器与阵列处理器之间有多条 存储通道相连，以保证提供足够的数据带宽。h o s t 负责执行操作系统调用，输入输出部分 在阵列处理器上不能获得好处的计算任务，以及负责循环阵列的启动，加载程序，退出以 及异常处理等工作。 阵列处理器在接收到指令和启动消息后，自主推动循环程序执行。计算单元具有独立 的循环步进能力，结束判断能力，数据交换和存储访问等能力。 阵列处理器通过网络连接各计算单元，网络系统包括两部分独立网络。存储网络是连 接各计算单元的局部存储器与外部存储器通道，提供各计算单元访问主存的通路，拓扑结 构为多条总线或二维网络。数据相关网络是连接各计算单元的输入出通道，用于计算单元 之间传递数据相关关系的消息，包括数据直传，数据等待，控制变量值传递等。拓扑结构 为二维网格或多维网络，也可以为可重构网络，因为每次运行时网络结构是固定的，当循 环运行时，通过加载信息重构计算单元之间的网络连接，保证足够的点点带宽。 系统中还有一个循环控制部件与数据相关网络连接，当所有循环片完成或执行了循环 退出语句，该部件等待其之前的循环片结束后，通知h o s t 循环执行完成。 2 3 与现有微处理器体系结构的横向比较 纵观现有的微处理器体系结构，m u l t i s c a l a rp o r c e s s o r 和g r i d 体系结构在执行机制上 与l e a p 存在相似之处，同时，由于其适用范围不同，其体系结构又各有不同，通过比较， 进一步明确l e a p 体系结构的优点和不足。 第l o 页 国防科学技术大学研究生院学位论文 2 3 1m u l t i s c a l a rp r o c e s s o r 在m u l t i s c a l a r 体系结构中，多个处理器顺序排列，由相应的软件和硬件负责将应用程 序顺序划分成多个任务块，分散在这些p e 上执行，每个p e 取并执行属于自己任务范围内 的指令。m u l t i s c a l a r