（计算机科学与技术专业论文）基于并行处理单元的代码优化方法研究.pdf

基于并行处理单元的代码优化方法研究 摘要 与传统d s p 相比，现代d s p 采用更多的i l p 技术以提高机器性 能。本文讨论的d s p 采用分簇的v l 州体系结构，能够在单个时钟 周期同时执行多个操作。本文先讨论这款d s p 代码优化器的构造方 法，之后对t it m s 3 2 0 d m 6 4 2 给出了代码优化器的具体实现。 v l i wd s p 代码优化器在l c c 编译器框架基础上实现。首先用 l c c 作为编译前端得到中间代码，然后对中间代码进行模版注释得 到目标机器指令相对应的程序，最后对其进行簇分配和调度，同时分 配寄存器和功能单元，得到优化的并行汇编代码。 我们为v l i wd s p 定制它的机器规格说明和机器描述，书写代码 生成规则的i b u r g 规范文本，并由i b u r g 规范自动生成代码优化器中 的指令选择部分。这样提高了v l i wd s p 的代码优化器的可重定目标 性。 v l i wd s p 体系结构的一个显著特点是分簇，与这一特点相对 应，代码生成的一个重要步骤是簇分配，即为每个操作及其操作数映 射合适的簇。簇分配应使得各簇的功能单元得到充分利用，并设法减 少簇之间的数据传递。本文讨论了簇分配的常用算法和l i s t 调度算 法，最后给出统一的簇分配与调度算法( u a s ) 针对v l i w d s p 的实 现。该算法的特点是簇分配与调度一同进行，当调度一个操作时，同 时为这个操作和它的操作数分配合适的簇。实验证明本文给出的代码 优化方法对于常用的d s p 算法具有较好的优化效果。 关键词：v l i wd s p 代码优化并行单元簇分配调度 s t u d yo fco d eo p t i m i z i n gm e t h o db a s e d o np a r a l l e lf u n c t i o n a lu n i t s a b s t r a c t c o m p a r e dw i t ht r a d i t i o n a ld s p , m o d e md s pu s em o r ei l p t e c h n o l o g i e st oi m p r o v ei t sp e r f o r m a n c e t h ed s p w ed i s c u s si nt h i s t h e s i su s e sac l u s t e r e dv l i wa r c h i t e c t u r ea n dc a np e r f o r mm u l t i p l e o p e r a t i o n ss i m u l t a n e o u s l yd u r i n gas i n g l ec l o c kc y c l e w ed i s c u s st h e c o n s t r u c t i o no ft h ec o d eo p t i m i z e ro fv l i wd s pa n dp r e s e n tt h e i m p l e m e n t a t i o no f t it m s 3 2 0 d m 6 4 2e s p e c i a l l y v l i wd s pc o d eo p t i m i z e ri si m p l e m e n t e db a s e do nl c c c o m p i l e rf r a m e w o r k f i r s t ，w eg e tt h ei n t e r m e d i a t ec o d ef r o ml c c f r o n t e n d a n dt h e nw es e l e c ti n s t r u c t i o no ft a r g e tm a c h i n eb yt e m p l a t e m a t c h i n gf o ri n t e r m e d i a t ec o d e f i n a l l y , w eg e ta s s e m b l ec o d et h a t c a nb e p a r a l l e lp r o c e s s i n g b y c l u s t e ra s s i g n i n g 、i n s t r u c t i o n s c h e d u l i n ga n dr e g i s t e r & f u n c t i o n a lu n i t sa s s i g n i n gs i m u l t a n e o u s l y w ，ec u s t o m i z e dam a c h i n es p e c i f i c a t i o na n dam a c h i n ed e s c r i p t i o n f o rv l i wd s p w - ew r i t ei b u r gs p e c i f i c a t i o nw h i c hc o n t a i n sc o d e g e n e r a t i n gr u l e s ，a n di b u r gr e a d st h es p e c i f i c a t i o na n dg e n e r a t e st h e i n s t r u c t i o ns e l e c t i o nc o d e i t i m p r o v e s t h ev l i wd s pc o d e o p t i m i z e r sr e t a r g e t a b i l i t y o n ep r o m i n e n tf e a t u r e so fo u rd s p a r c h i t e c t u r ei sc l u s t e r i n g 、m t ht h i sf e a t u r e ，a ni m p o r t a n tp h a s eo fo u rc o d eo p t i m i z a t i o ni s c l u s t e r a s s i g n i n g ，w h i c hm a p so p e r a t i o n s a n dt h e i r o p e r a n d st o a p p r o p r i a t ec l u s t e r s c l u s t e ra s s i g n m e n ts h o u l dm a k em a x i m a lu s eo f f u n c t i o n a lu n i t sa c r o s s c l u s t e r s ，a n d r e d u c ei n t e r - c l u s t e rd a t a m o v e m e n tb e s i d e s w ed i s c u s st r a d i t i o n a lc l u s t e r a s s i g n m e n t a l g o r i t h ma n dl i s ti n s t r u c t i o n - s c h e d u l i n ga l g o r i t h m ，a n di m p l e m e n t t h eu n i f i e da s s i g ns c h e d u l e ( u a s ) a l g o r i t h mt o s u p p o r tc l u s t e r a s s i g n m e n t ，w h i c hh a st h ef o l l o w i n gf e a t u r e s ：c l u s t e ra s s i g n i n ga n d s c h e d u l i n g a r eu n i f i e d ，a n dw h e ns c h e d u l i n ga no p e r a t i o n ，t h e o p e r a t i o na n di t so p e r a n d sa r ea s s i g n e dt ot h e i ra p p r o p r i a t ec l u s t e r sa t t h es a m et i m e e x p e r i m e n t ss h o wt h a tt h ec o d eo p t i m i z e ri nt h i st h e s i s i sv e r ye f f e c t i v ei no p t i m i z a t i o no fc l a s s i c a ld s pa l g o r i t h m k e yw o r d s ：v l i wd s p ，c o d eo p t i m i z e r , p a r a l l e lu n i t s ，c l u s t e r a s s i g n i n g ，s c h e d u l i n g 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京 邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：匠仁菇每多毛一日期：2 堡生l 2 j 巧二_ 一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非 保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：竖墨亟 刷醛轹每吨_ 日期：竺竺：! 二堕 日期：翌呈：三：鉴 北京邮电大学硕士学位论文基于并行处理单元的代码优化方法研究 第一章绪论 数字信号处理器作为实时信号处理的核心器件，正在广泛应用于通信、计 算机、网络等各个领域。在d s p ( d i 百t a ls i g n a lp r o c e s s o r ) 系统的整体设计开发 过程中，软件开发的地位尤其重要。 实际开发中先采用c 语言实现算法然后对其进行三个阶段的优化。其中 第三个阶段的优化是写线性汇编，然后用c c s ( c o d ec o m p o s e rs t u d i o ) 提供 的汇编优化器对其进行优化。然而手工书写汇编代码需要程序员了解更多的硬 件信息。本文就是讨论v l 州d s p 体系结构机器的特点并给出其机器相关的优 化的一般方法，使得程序员不需要了解硬件信息就可以把c 源程序的代码片断 变成优化的可以并行执行的目标机器汇编代码。 1 1 1 课题背景 数字信号处理是2 0 世纪6 0 年代发展起来的新兴学科，已广泛应用于数字 通信、雷达、遥感、语音图像处理、测控、自动控制等诸多领域。d s p 是专门 用于实时数字信号处理的微处理器，现代d s p 大都使用v l 州( v e r yl o n g i n s t r u c t i o nw o r d ) 体系结构。由于一州d s p 采用了哈佛结构、多总线结构、 流水线技术和专用指令等特殊设计而具备了强大的运算能力。 对于d s p 的一个应用领域数字图像处理来说，在实时性上要实现实时采 集、实时传输、实时显示、实时处理，在分辨率上实现高分辨率，在色彩上要 实现无限色，在图像压缩上要实现超低码率的压缩，所有这些都需要庞大的计 算量，这样就要求有处理器要有很高的处理速度。 虽然d s p 功能强大，适合做密集计算，但d s p 的时钟频率是有限的，例 如t m s 3 2 0 c 6 0 0 0 系列c p u 时钟频率仅有2 0 0 m 6 0 0 m h z 2 1 ，这样在d s p 上运 行的程序特别是图像视频处理这样的复杂的计算量大的程序必须要经过优化， 才能完成实时性的要求。 目前在d s p 平台上编程多使用汇编语言与c 语言。汇编语言简洁高效， 能够直接操作d s p 的内部寄存器、存储空间、外设，但可读性、可修改性、 可移植性较差，一般程序员掌握起来需要一段时间。而c 语言是一种较为高 北京邮电大学硕士学位论文 基于并行处理单元的代码优化方法研究 效的高级语言，在可读性、可移植性等方面优于汇编指令。由于d s p 结构的特 殊性，使得该平台上的c 语言编译器无法充分发挥d s p 器件的性能优势，同 样功能的c 语言程序，效率往往只有直接书写的汇编程序的几分之一甚至几十 分之一【3 1 ，因此在采用d s p 进行程序开发时有必要根据d s p 的特性对c 语言 编写的程序进行进一步的优化。 在实际开发中先采用c 语言实现并验证算法的正确性，然后对没有经过任 何优化的c 代码进行测试然后对代码进行第二个阶段的优化，如果程序还不能 达到要求就要进行第三个阶段的优化，即用线性汇编语言进行个别影响效率的 代码段进行编程，利用芯片自身硬件结构的特点，对汇编程序进行优化与精简。 这往往能够使一些复杂的算法和功能模块在实时性方面取得非常好的效果。 然而第三个阶段的还是手工完成的，需要程序员深入了解d s p 的特性和 汇编语言，从而增加了软件开发的难度和开发周期。因而有必要研究v l i w d s p 的体系结构机器的特性，并实现其c 源程序代码到目标汇编代码的自动优 化方法。 1 1 2 研究现状 在d s p 软件开发中推荐的开发流程如图1 1 所利4 1 。程序员可以按照这三 个阶段来进行软件开发，相应的代码优化也分三个阶段进行。 第一个阶段：对第一个阶段，没有d s p 知识的用户就可以开发自己的c 代码，然后使用d s p 代码剖析工具，确定c 代码中可能存在的低效率段，为 进一步改进代码性能，进入第二阶段。 第二个阶段：使用一定的方法，改进c 代码，使用d s p 剖析工具检查其 性能，如果代码仍不能达到所期望的效率，则进入第三个阶段。 第三个阶段：从c 代码中抽出对运行时间影响最大的代码段，用线性汇编 改写这段代码。用户能使用汇编优化器优化该代码。 第一阶段的优化是基于通用微处理器的p c 机环境中的优化，主要是针对 c 程序的通用特性来考虑的。这方面的优化工作主要包括数据类型选择、数值 操作优化、快速算法、变量定义和使用优化、函数调用优化以及计算表格化【5 l 等。值得一提的是在第一个阶段的优化过程中，可以通过选定c c s ( c o d e c o m p o s e rs t u d i o ) 提供的c 编译器的选项来实现优化。 第二个阶段可以利用如下技术来提高性能【6 j ：( 1 ) 用d s p 编译器内部函数 来代替复杂的c 代码；( 2 ) 涉及到1 6 位数的存取操作，尽量用3 2 位操作数 代替；( 3 ) 注意利用软件流水线技术提高循环结构的代码性能；( 4 ) 展开循环 结构，可以牺牲代码的大小来换取速度。 2 北京邮电大学硕士学位论文 基于并行处理单元的代码优化方法研究 经过前两个阶段的代码优化之后，若对部分代码的性能不满意，可以利用 代码剖析工具提取出效率低的部分，然后有两种方法对其进行汇编优化。一种 方法是使用线性汇编重新改写，然后用c c s 提供的汇编优化器对改写的线性 汇编进行优化得到最终优化的汇编代码；另一种方法是直接对这部分代码进行 图1 - 1d s p 开发流程图 手工改写，得到优化的汇编代码。很显然第二种方法更为高效，但是需要程序 员对d s p 系列芯片的内部结构非常了解，而且需要大量的时间，在实际应用 3 北京邮电人学硕上学位论文基于并行处理单元的代码优化方法研究 中，除非代码的实时性要求非常高，一般都采用线性汇编改写c 代码。 线性汇编与普通的d s p 汇编很相似，都使用汇编指令书写代码。不同的 是，线性汇编不需要书写普通汇编时必须提供的所有信息( 如指令是否并行执 行、指令的标号、流水线的延迟、寄存器的使用和功能单元的使用等) 。汇编 优化器从输入的线性汇编代码中，完成以下功能【7 1 ：( 1 ) 寻找哪些c p u 指令可 以并行执行；( 2 ) 在软件流水线期间，处理流水线标号：( 3 ) 分配寄存器的用法； ( 4 ) 定义使用哪个功能单元。 1 1 3 研究内容 高速通信应用正在飞速增长，数字信号处理器( d s p ) 在其中扮演了重要 角色。d s p 应用的主流算法其内部循环大都可表达为向量运算，这些运算具有 天然的指令级并行性( 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 ) 。例如，典型的核心程 序f i r 滤波器可以表示为y i = 巳 一。此外，多数d s p 应用于对实时处理有 特殊需求的嵌入式环境，这种环境要求d s p 具有很好的性能。采用i l p 技术是 改进机器性能的一种重要途径。 为了取得更高性能，现代d s p 大都使用v l i w 体系结构。v l m 是一种 水平指令结构，每条指令包含多个并行执行的、相互间独立的简单操作。v l i w 体系结构为编译器呈现出一种简洁的界面，有利于构造高效的优化编译器。事 实上，v l 州体系结构依赖编译器静态地确定程序各操作的调度顺序，编译器 对于v l 州机器性能的发挥至关重要。采用v l i w 体系结构的d s p 有s t a r c o r e s c l 4 0 、a d it i g e r s h a r c 、t 1 t m s 3 2 0 c 6 0 0 0 2 】系列等，而c 6 0 0 0 系列d s p 凭 借与之搭配的优秀的集成开发环境在市场占据了很大份额。 本文围绕v l 州d s p 体系结构的机器，讨论了其代码优化器的构造方法。 并针对t it m s 3 2 0 d m 6 4 2 给出了具体的代码优化器方法。除了阐明这一过程 的具体实现，本文主要解决了如何使得v l 州d s p 的代码优化器尽可能地独 立于具体的处理器。 由于v l i wd s p 具有独特的特性，使得开发它的代码优化器面临巨大挑 战。一个最显著特性就是分簇( c l u s t e r i n g ) ，即处理器内核被分成了2 簇，每 簇由1 个寄存器文件和4 个与之关联的功能单元组成。功能单元能够便捷地访 问本地簇的寄存器，远地簇的寄存器访问则要通过共享的簇间数据通路。分簇 有效地降低了硬件设计的复杂度，从而c p u 的时钟周期可以更快。但是，分 簇给代码优化器的设计带来了挑战。代码优化器调度操作时( 在代码生成时发 生) ，不仅要充分利用处理器的功能单元，而且还要使得簇间的数据传递不会 过于频繁。也就是说，编译器需要为操作和它的操作数分配合适的簇，以减少 4 北京邮电人学硕士学位论文基于并行处理单元的代码优化方法研究 对共享的簇间通路使用的冲突。簇分配和调度是本文的重要研究内容。 1 2 本文贡献 本文主要有以下三个方面的贡献： 第一、研究了删体系结构机器相关优化的一般方法，并对t i 的 t m s 3 2 0 d m 6 4 2 处理器给出了代码优化器的设计和实现的实例。 第二、给出了机器描述的方法。对于不同体系机构的机器，只要给出机器 描述就能用现有的代码优化器对其进行优化。 第三，讨论了代码优化器后端的簇分配与调度算法。簇分配是分簇机器特 有的，簇分配使得各簇的功能单元得到充分利用，并减少了簇之间的数据传递。 本文的代码生成器使用u a s 算法做簇分配和调度，实验证明本文的优化方法 对于嵌入式图像处理具有很大的实用价值。 1 3 论文结构 第一章为绪论，概述课题的研究背景、研究现状和研究内容。第二章叙述 了- 一刑d s p 的体系结构，重点讨论与代码优化器相关的机器特性。第三章给 出了- 一刑d s p 代码优化器的设计与实现，讨论了代码优化器的总体框架、优 化的前端、与目标机器无关的代码生成接口、优化器的后端以及重要模块的算 法实现和一些关键数据结构。第四章给出的机器规格说明和机器描述。第五章 讨论了簇分配与调度策略并给出了具体算法实现及实验结果。第六章总结全 文，并对今后的工作做一个展望。 北京邮电人学硕士学位论文 基于并行处理单元的代码优化方法研究 第二章v l i wd s p 体系结构 本章主要叙述的对于d s p 代码优化器可见的体系结构特性。这些特性主 要涉及机器的资源约束、指令的执行延迟、指令打包的方法和条件执行。2 1 节描述了v l 删体系结构的特点发展趋势和编译方法。2 2 节描述的数据通路， 给出指令编译调度时应满足的资源约束条件。2 3 节简述了流水线，给出指令 的执行延迟。2 4 节介绍取指包和执行包的概念。2 5 节介绍条件执行特性。关 于t m s 3 2 0 c 6 0 0 0 系列d s p 的指令集放在第四章描述。 2 1v l i w 体系结构 2 1 1v l i w 的特点 1 9 8 3 年美国教授j f i s h e r 受水平微代码思想的启示，提出了v l i w ( 超长指 令字) 体系结构。v l i w 由编译器将多个可以同时并行执行的操作排在一条超 长指令字中，在一个指令周期内由c p u 并行发射，以减少对存储器的访问。 与传统结构相比，这种体系结构既可以提供较高的指令级并行度，同时又具有 简单的硬件译码和控制逻辑【引。 v l 州的特点是它能从应用程序中提取高度并行的指令数据，并把这些机 器指令均匀地分配给芯片中的众多执行单元。实际上采用v l 研技术的芯片设 计要比相应的超标量设计简单得多，采用v l i w 后，花少量的力气能做更多的 事 9 1 。 典型的v l 州芯片中具有上文提及的数量众多的执行单元，这些执行单元 被布放在整齐的网格上，在每个时钟周期内能执行多条指令。v l l w 需要智能 化的编译软件配合以安排这些指令的执行。 2 1 2v l i w 技术的发展 关于v l i w 技术可以追朔到8 0 年代早期，当时许多微型计算机公司，其 中最有名的要数c y d r o m e 和m u l t i f l o w 公司，联合起来企图设计出基于v l 州 的大型系统。但该技术当时没有得到过充分认证，也没有广泛的市场基础，因 此这次尝试以失败告终。但是现在v l i w 芯片技术的研究成果已经展现在我们 面前，无论是服务器领域，还是桌面领域或嵌入式领域都呈现了v l i w 技术的 勃勃生机。 实际上，英特尔公司的e p i ci a 6 4 结构最能体现大型v l m 的特剧m 】，它 6 北京邮电大学硕士学位论文基于并行处理单元的代码优化方法研究 要比该公司生产的同类3 2 位系列微处理器复杂得多。虽然这里不对它作详细 讨论，但这是千真万确的。由于二州在嵌入式应用中有上佳的表现，市场上 已经出现了好几种采用v l i w 技术的最新处理器。首先进入市场的是具有 v l 研概念的媒体处理器，比如飞利浦公司的t r i m e d i a 和c h r o m a t i c 公司的 m p a c t 媒体引擎。紧随其后，德州仪器公司( t i ) 也发布了基于v l 研技术的称 为v e l o c i t i 的c 6 x 系列数字信号处理器，该处理器主要用于蜂窝电话及相关 设备。为了使潜在用户确信芯片的c 编译器能将并行指令数据发送给d s p ， t i 公司花费了大量的时间与精力。在c 6 x 系列处理器发布一年后，t i 的努力 终于取得了巨大成效。在d s p 领域，还有其它竞争厂家如m a n l o gd e v i c e s 和 s t a r c o r e ( 后者是摩托罗拉公司与朗讯公司的一家合资公司) 也先后加入了 v l i w 阵营。而在做传统嵌入式系统设计的厂家中，也许要数t r a n s m e t a 公司 推出的c r u s o e 系列处理器最值得关注了。 2 1 3v l i w 结构的编译方法 v l 州体系结构性能的发挥在很大程度上依赖于其相应的编译器【1 1 1 ，这对 编译器及其优化技术提出了新的需求。因此，如何针对具体v l 州机器平台的 特点，研究相应的机器相关优化技术，在整个v l 研编译技术研究中占有重要 地位，并对快速提高国产_ 一研编译器性能有着重要的意义。 d a l a b u s 图2 - 1 v l i wd s p 数据通路 2 2v l i wd s p 的数据通路 v l 州d s p 的数据通路【1 2 1 如图2 1 所示。从图上可看出，c p u 包含两个并 列的数据通路a 和b ( 即簇a 和b ) ，它们分别连着通用寄存器文件a 和b 。 7 北京邮电大学硕十学位论文 基于并行处理单元的代码优化方法研究 每个数据通路包括四个功能单元( a l 、b c 、m u 、l d ) ，这些功能单元之间 相互独立，可同时执行指令。每个数据通路还各有一个交叉通路( x ) ，用以访 问另一通路的寄存器。以下小节进一步讨论数据通路的各种资源。 2 2 1 通用寄存器文件 数据通路a 和b 各有一个寄存器文件，它们均包含个1 6 个3 2 位寄存器。 v l i wd s p 支持的定点数据类型有3 2 位数、压缩1 6 位数和4 0 位长型数。3 2 位数自然存放在一个寄存器中。压缩1 6 位数存放在寄存器的高1 6 位或低1 6 位。v l 两d s p 支持一些s i m d 指令，它们能同时操作一个寄存器中的两个1 6 位数。4 0 位长型数存放在相邻的寄存器对中。 寄存器访问具有以下限制： 1 、每个时钟周期读同一寄存器的次数不能超过4 ( 条件寄存器的读取除 外) ； 2 、每个时钟周期写同一寄存器的次数不能超过1 。 2 2 2 功能单元 数据通路a 和b 各包括四个功能单元，每个功能单元能执行一定范围的 操作，叙述如下： a l 单元主要执行算术、比较和逻辑运算操作； b c 单元主要执行算术、逻辑运算、移位、位操作、分支和常数传递等操 作； m u 单元主要执行1 6 位的乘法操作； l d 单元主要执行加减法、地址计算和l o a d 、s t o r e 操作。 从上面的叙述可看出，有些操作仅能被特定的功能单元执行，而另外的操 作可被多个功能单元执行。v l 唧d s p 操作的指令集是类r i s c 的。 2 2 3 交叉通路 数据通路a 和b 各有一个交叉通路x ，它允许功能单元从另一通路的 寄存器文件读取操作数。交叉通路的使用具有以下限制： l 、只有的a l 的s r c l 和s r c 2 、b c 和m u 的s r c 2 能够使用交叉通路； 2 、每个时钟周期交叉通路只能被一个功能单元的某个输入使用。 2 2 4 存储访问通路 存储访问通路包括传递数据的通路l d s t 和传递地址的通路d a 。每个数 据通路均有自己的存储访问通路，记为t 。t 通路被l o a d 、s t o r e 操作使用，能 够执行l o a d 、s t o r e 的功能单元为l d 。实际上l d 只计算访存地址，访存使用 哪个t 通路由目的寄存器( 对于l o a d ) 或源数据寄存器( 对于s t o r e ) 所在的数 北京邮电大学硕士学位论文基于并行处理单元的代码优化方法研究 据通路决定。例如，在l d l 单元执行的l o a d ，它的目的寄存器为b 2 ，则l o a d 使用的访存通路为t 2 。 2 2 5 资源约束小结 v l 唧d s p 的资源约束大致有以下几种情况： l 、每个时钟周期不能有两个操作同时使用一个功能单元； 2 、每个时钟周期传递数据的通路不能被多次使用，并且若两个数据通路 部分重叠，则它们不能同时被使用； 3 、x 通路仅能供某些功能单元的某些输入使用； 4 、每个时钟周期读同一寄存器的次数不能超过4 ( 条件寄存器的读取除 外) ，写同一寄存器的次数不能超过1 。 2 3 流水线和指令延迟 l d w l d ws h r s h r l d wl d wis m p y hs m p y l d wl d wm v k l hm vls m p y hs m p yb l d wl d wm v k i a d ds h l l l d wl d w l m v k p g p s l a w p r 图2 - 2 流水线取指各阶段的一个具体例子 v l 州d s p 的流水线分为取指( f e t c h ) 、译码( d e c o d e ) 和执行( e x e c u t e ) 三级( s t a g e ) ，每一级又由若干个阶段( p h a s e ) 组成【1 3 】。所有的指令取指级包 含程序地址生成( p g ) 、程序地址发送( p s ) 、程序访问等待( p s ) 和程序接 收( p r ) 4 个阶段。每个时钟周期c p u 从存储器读取一个取指包，它由连续 的8 条指令组成。每个取指包又可细分为多个执行包，执行包之间串行分派， 9 北京邮电大学硕十学位论文基于并行处理单元的代码优化方法研究 其内部的指令并行分派。图2 2 是流水线取指各阶段的一个例子。 译码级包括指令分派( d p ) 和指令译码( d c ) 两个阶段。在d p 阶段， 指令分派部件将一个执行包的指令并行分派到各自对应的译码器。在d c 阶段， 指令被译码器译码。图2 3 中箭头指出的是每条指令将被分配到的功能单元。 指令n o p 由于与功能单元无关，因此不分配功能单元。 俐回固 埘 d e c o d e3 23 23 23 23 23 23 23 2 ia d da d ds t ws t wa d d kn o p tid p - z - y i 一广l 审台甲台告甲苦审d c 由由由由印n 吣c l i o na i 由由由由 图2 - 3 流水线译码阶段的2 个节拍 执行级根据定点和浮点流水线分成不同的阶段，定点流水线的执行级最多 分为5 个阶段( e 1 e 5 ) 。指令类型不同，执行它们需要的执行阶段数也不同。 所有指令它们的源操作数( 若存在的话) 都在e l 阶段开始前读取。单周期指 令的目的操作数在e l 阶段结束前写入，乘法指令和l o a d 指令的目的操作数分 别在e 2 和e 5 阶段写入。这几类指令的延迟槽个数等于指令执行阶段数减l 。 s t o r e 写存储器在e 3 阶段，l o a d 读存储器也在e 3 阶段，又由于v l i wd s p 只有l o a d 和s t o r e 指令能够访存，所以只要s t o r e 在l o a d 的前一拍流出，l o a d 指令就能读s t o r e 向内存写的值，即的延迟槽个数为0 。 分支指令没有目的操作数，它的延迟槽个数等于从分支目标地址产生到目 标地址处的指令进入执行阶段所需的时钟周期数减1 。分支地址在e 1 阶段产 生，它直接送往程序读取部件以产生p g 阶段的程序地址。分支目标指令进入 执行阶段还需经历取指级的剩余3 个阶段、译码级的2 个阶段和e l 阶段，共 6 个阶段。所以，分支的延迟槽个数为5 。图2 4 给出了t m s 3 2 0 c 6 2 x 流水执 行过程的功能框图。 2 4 取指包和执行包 如前所述，c p u 从存储器读取指令的基本单位是取指包，一个取指包包含 l o 北京邮电大学硕士学位论文基于并行处理单元的代码优化方法研究 多个执行包，每个执行包由多条并行分派的指令组成。执行包的各指令是相互 独立的，它们的组合不受限制，只需要满足机器的资源约束即可。这种特有的 两级打包指令的方法能够显著地缩短代码的长度，减少运行时的访存次数和功 耗【1 4 】【15 1 。 执行包由编译器调度或手工调度形成，取指包则由汇编器合成。从存储器 读取取指包并分派其中的各执行包的过程正好与汇编器使用执行包合成取指 包并将取指包存放至目标文件的过程相反。 例回五殂 俐c 睹 e x e c u t e s 晋l | 昌lis 芥i l 哥 l 口口口口口口口口口口口口口口口口i 。 【! 曼! ! ! i 幽! ! 璺窒垒z 旦! 毛兰! 。! 卜 r e g i s t e rf d e k- 3 2 i l d lt 3 ，is 1 n e 1 涮ils 惴h l l 溜ii 馏d 3 2 - 1 - 1 1000 000000000 00 00 t am e m o r yi n t e r f a c ec o n t r o l d a l d a t aa d d r e s s1 1 61 61 81 0 0 8 345l6 d 2 d a t aa d d r e s s2 i n t e r n a ld a t am e m o r y ( b y t ea d d r e s s a b l e ) 2 5 条件执行 图2 - 4t m s 3 2 0 c 6 2 x 流水执行过程的功能框图 v l 州d s p 包括几个条件寄存器b o 、b i 、b 2 、a i 和b 2 。几乎所有的指令 都可条件执行，即指令是否执行依赖于条件寄存器的值。使用条件执行，可以 消除程序的一些控制相关，提高程序的i l p 。 北京邮电大学硕上学位论文基于并行处理单元的代码优化方法研究 第三章v l i wd s p 代码优化器的设计 为了把c 源代码优化成汇编代码首先要完成翻译工作，这正是编译器需要 做的工作。本章讨论的v l 研d s p 代码优化器就是基于编译原理的。要把c 源代码的编译优化成为汇编代码需要作以下几方面的工作：编译器基础设施的 选择、中间代码到机器相关代码的转换( 即指令的选择) 、分簇寄存器的分配、 指令的调度( 包括资源冲突的解决和指令的并行调度) 、机器描述文件的书写 【l6 1 。本章主要讨论v l l wd s p 代码优化器的整体组织和数据结构以及编译前 端的概况。指令选择部分我们选择用i b u r g 紧缩规范自动生成的树分析程序。 第四章重点讨论机器规格说明和机器描述，第五章重点讨论分簇寄存器分配和 指令调度。 3 1 代码优化器总体设计框架 3 1 1 概述 本文采用编译思想实现v l l wd s p 代码优化器。首先用l c c 作为编译前 前 图3 - 1 传统编译器总体框架 端得到中间代码，然后选用i b u r g 紧缩规范对中间代码进行模版注释( 选择指 令) 得到目标机器指令相对应的程序，最后对其进行簇分配和调度，同时进行 1 2 北京邮电人学硕士学位论文 基于并行处理单元的代码优化方法研究 分配寄存器和功能单元，得到优化的并行汇编代码。 传统的编译程序生成技术如图3 1 所示，一般分为前端和后端，其中前端 进行机器无关的词法分析、语法分析、翻译成中间代码。后端则是机器相关的 中间代码转换、优化、寄存器分配、指令调度、目标代码生成等【l 刀。针对不同 的目标机器，编译后端都必须进行相应的改写以生成不同目标机上的相同语言 的编译程序。而改写编译程序后端的工作十分困难。本文通过在编译程序后端 加入机器描述模块，使得后端其他各机器相关的模块通过与机器描述进行交互 获取目标机信息而变成与机器无关，极大地增加了后端的灵活性，提高了整个 编译程序的可重定目标性。 本文通过使用机器描述技术对二州d s p 目标机器进行指令格式、指令延 时、操作书类型、寄存器文件等机器信息描述，把后端中机器相关的模块如调 度等从机器描述获取目标机信息变成机器无关，为v l i wd s p 型机器生成一具 有高灵活性，可重定目标型的代码优化程序。图3 2 是整个代码优化器的结构 图。当v l i w 型目标机器发生改变时，如改变某些指令的执行延时、增加新的 功能单元等。只需为新的目标机修改机器描述文件，就可以构造出面向新目标 机器的编译程序【1 8 】【1 9 1 。 图3 - 2 代码优化器的结构图 3 1 2 代码优化器的工作环境 代码优化器的工作环境如图3 - 3 所示。对于某一种体系结构的目标处理器， 只要给出其机器描述并通过机器描述语言解析器把这种描述变成代码优化器 可以处理的机器描述文件，代码优化器就可以把需要优化的c 源代码程序片断 北京邮电大学硕上学位论文基于并行处理单元的代码优化方法研究 优化成可以并行执行的目标机器的汇编代码。 3 2 优化器前端 3 2 1l c c 概述 l c c 是一款免费、开放源代码并被广泛使用的a n s ic 编译器。它的作者 是美国a t & t 实验室的c h r i s t o p h e l w f r a s e r 和美国普林斯顿大学教授d a v i d r h a n s o n ，当前版本为4 2 。l c c 的分析代码由手工编写而成，编译速度非 常快；l c c 没有单独的优化遍，但对于大多数应用来说，l c c 产生的代码已 经足够快了。与广为使用的g c c 形成鲜明对比的是，l c c 的源代码简单、紧 凑，十分有利于进行修改。以可变目标为目的的设计，移植或对各种不同用途 后端的实现比较简单【2 0 】。 图3 - 3 代码优化器的工作环境 l c c 目前已经应用在x 8 6 、m i p s 、s p a r c 等目标机器上。l c c 在结构 上分为前端和后端，具有可重定向特性，也就是说可以使用不同的后端以面向 不同目标机生成相应的汇编代码。l c c 的编译前端主要完成标准c 语言的词 l c c 前膏鲁种后 词诱语生 瑚6 后甥 浃注义成 卜、 m i p s 后璇 分廿分d d a g 斩惭忻 a v s p a r c 培螨 g 后麓 图3 - 4l c c 的总体结构 法分析、语法分析和语义分析，然后将语义转化成d a g ( d i r e c t e da c y c l i cg r a p h ) 中间表达形式，供后端处理。l c c 的编译后端完成的主要工作是将d a g 转 化成目标机需要的汇编代码。图3 4 是l c c 的总体结构。 1 4 北京邮电大学硕士学位论文基于并行处理单元的代码优化方法研究 基于l c c 移植特定嵌入式系统的编译器，可以通过剔除掉l c c 提供的其 它后端，用相应的嵌入式系统的后端替代来实现。这样一方面可以简化生成编 译器的结构，另一方面也可以减少系统构建中的错误。移植的编译器结构如图 3 5 所示【2 1 1 。 i ：c 葡馈 特定后辅 词语语生 法法义j 覆 瑚懒媸l 舒分分d 轿昕确 a g 图3 - 5 基于l c c 移植的编译器结构 本文就是利用l c c 的编译前端得到中间代码，再在后端进行自定义配置 的方法，最终得到代码优化器的。 3 2 2 数据结构 类型和符号的数据结构是编译器的核心数据表示。对于编译后端而言，中 间代码有关的数据结构也是非常重要的。l c c 使用d a g ( 有向无环图) 对中 间代码进行描述，它使用二叉树的链表形式进行组织。所有的中间代码通过代 码表进行管理，这种代码表与优化器中用于控制流分析的基本块有所区别，但 可以看作是一种扩展基本块，通过它可以方便进行基本块的划分，从而插入单 独的优化遍，使l c c 成为优化编译器。 编译器后端的实现者需要熟悉至少四种i , c c 的核心数据结构，分别是类 型、符号、d a g 节点和后端接口描述，本文不对其细节进行赘述，可参考l c c 编译器源代码。 对于这四种数据结构中，l c c 从概念上将其划分为三部分，一部分为编译 前端私有数据，根据l c c 后端的访问约定，l c c 后端并不访问这个部分的数 据；第二部分为前后端共享的数据；第三部分为后端私有数据；前端对此一无 所知【2 1 1 。其中，前两个部分的数据从形式上看没有区别，而第三部分，作为后 端的私有数据结构由后端自己实现，由各结构中的x 域成员进行维护，它们的 组织形式如下述： t y p e d e ft y p e x t y p e x * t y p e 北京邮电大学硕十学位论文基于并行处理单元的代码优化方法研究 t y p e d e fs y m b o l x s y m b o lx ) 宰s y m b o l t y p e d e fn o d e x n o d e x ) * n o d e t y p e d e fi n t e r f a c e x i n t e r f a c ex ) 宰i n t e r f a c e l c c 为生成可执行目标代码的代码生成器提供了一种自动代码生成的方 法，使用这种方法，后端的实现者只需要提供一份规范描述的目标机器描述文 本，由一个叫做i b u r g 的程序据其自动生成相关代码，而上图所示的x 域成员 类型由相应的后端文件提供，其数据由自动生成的代码进行访问，相关类型和 数据的声明在c o n f i g h 文件中声明。对于手工生成的代码，这些x 域，由实现 者自行实现和访问，可以将c o n f i g h 文件替换为自己的实现【2 l 】。 3 2 3 中间代码表示d a g 图 l c c 的中间代码表示使用的是d a g ( 有向无环图) ，其中多入口的节点 就是公共子表达式节点。使用这样的表示方法起到了删除公共子表达式的目的， 为后端生成高质量的目标代码提供了有力的保障。l c c 中间代码所提供的指 令是通过仔细筛选的，能够匹配大多数机器的硬件