（计算机系统结构专业论文）基于模拟退火和团划分的综合技术研究.pdf

、上 c l a s s i f i e di n d e x ： u d c ： ad is s e r t a ti o nf o rt h ed e g r e eo fm e n g r e s e a r c ho ns y n t h e s i st e c h n i q u e s ba s e do nsi m u l a t e da n n e a l i n ga n dc l i q u e p a r t i t i o n i n ga l g o r i t h m c a n d i d a t e ：y a hy i n g s u p e r v i s o r ：l e c t u r e rc h e n gl i x i n a c a d e m i cd e g r e e a p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra r c h i t e c t u r e d a t eo fs u b m i s s i o n ：j a n u a r y ，2 010 d a t eo f o r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y k ， 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：彦j 狈 日期：2 0 l o年弓月7 曰 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可日在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：7 司疑导师( 签字) ：霸漫畚t 、l 新 日期： 如f o 年弓月7 日勘0 年弓月7 日 乏 一 一 哈尔滨工程大学硕十学位论文 摘要 高级综合是数字系统设计自动化的关键技术之一，是近年来国内外研究、 开发和应用的热门课题。高级综合工具的出现简化了复杂集成电路的设计过 程，缩短了设计周期。高级综合理论的研究和算法的改进，对于提高综合质 量非常重要。本文主要关注高级综合中调度和分配两个关键步骤的优化问题。 首先，本文在分析以往高级综合系统所采用的技术基础上，提出了一种 新的高级综合调度优化策略。采用一种基于模拟退火算法的方案，优化高级 综合的调度过程，目的是以在较短的时间内逼近全局最优解。为了在调度过 程中进一步考虑调度和分配的相互作用，提出了同时考虑时间、造价和功能 单元利用率的能量函数，将分配结果作为计算调度方案能量函数的要素之一。 资源分配采用了一种快速的团划分算法实现，尽可能的满足能量函数易于计 算的需求。 、 其次，为了在实际应用中进一步减少算法执行时间和改善结果质量，本 文引入了对基本模拟退火算法的几种改进方案。采用改进算法流程和增加新 功能等手段，来减轻模拟退火算法中一些固有缺陷的影响。通过加温退火、 升温过程、记忆功能和返回搜索等改进策略，使算法具备了自适应初始温度 选择、避免过早陷入局部最优和防止错过全局最优等功能，从而进一步提升 了时序调度的优化效果。 本文实现了所提出的方案，通过实验验证了使用该方案优化调度和分配 问题的效果。在本文的最后，给出了算法的部分关键参数和主要的实验数据。 关键词：高级综合；模拟退火；团划分；调度；分配 、： 卜 哈尔滨工程大学硕十学位论文 a b s t r a c t h i 曲- l e v e ls y n t h e s i si so n eo ft h ek e yt e c h n o l o g i e so fd i g i t a ls y s t e md e s i g n a u t o m a t i o n ，a n dh a sb e c o m eah o tt o p i co fi n v e s t i g a t i o n ，d e v e l o p m e n t ，a n d a p p l i c a t i o na th o m ea n da b r o a di nr e c e n ty e a r s t h ea d v e n to ft h eh i g h l e v e l s y n t h e s i st o o l ss i m p l i f i e st h ed e s i g np r o c e s so fc o m p l e xi n t e g r a t e dc i r c u i t s ，a n d s h o r t e n sd e s i g nc y c l e s ，a n dt h es t u d yo fh i 曲l e v e ls y n t h e s i st h e o r ya n dt h e i m p r o v e m e n to f r e l a t e da l g o r i t h mi so fg r e a ti m p o r t a n c e i nt h i sp a p e r ，a t t e n t i o ni s c o n c e n t r a t e do nt h es c h e d u l i n ga n da l l o c a t i o no fh i g hl e v e ls y n t h e s i s f i r s t ，an e wo p t i m i z a t i o ns t r a t e g yo fh i g hl e v e ls y n t h e s i si sp u tf o r w a r d ， b a s e do nr e s e a r c h i n gt h et e c h n o l o g ya d o p t e di no t h e rh i g hl e v e ls y n t h e s i ss y s t e m t h es c h e d u l i n go fh i 曲l e v e ls y n t h e s i si so p t i m i z e dw i t has o l u t i o nb a s e do n s i m u l a t i o na n n e a l i n ga l g o r i t h m t h i sm e t h o d f u r t h e rc o n s i d e r st h ei n t e r a c t i o no f s c h e d u l i n gw i t ha l l o c a t i o ni nt h ep r o c e s so fs c h e d u l i n g ，a n dp r e s e n t sa n e wf o r m o fe n e r g yf u n c t i o ni n v o l v i n gt h r e ef a c t o r s ：t i m e ，c o s ta n du t i l i t yr a t i o t h er e s u l t o fa l l o c a t i o ni st r e a t e da saf a c t o ro fe n e r g yf u n c t i o n t h ea l l o c a t i o ni sc o m p l e t e d b yaq u i c k l yc l i q u ep a r t i t i o n i n ga l g o r i t h m ，t om e e tt h en e e d so fe n e r g yf u n c t i o n w h i c hm u s tb ec o m p u t e de a s i l y s e c o n d ，s e v e r a li m p r o v e m e n t so fs i m u l a t i o na n n e a l i n ga l g o r i t h mi si m p o r t e d ， f o rt h ed e c r e a s eo fo p e r a t i o nt i m ea n dp r o m o t i o no fe f ! f - e c ti nt h ep r a c t i c e t h e p r o c e s sa n di n c r e a s i n gn e wc a p a b i l i t i e s i s p e r f e c t e d ，t oa v o i dt h e d e f e c t so f s i m u l a t i o na n n e a l i n ga l g o r i t h m h e a t i n ga n n e a l i n g ，t e m p e r i n ga n n e a l i n g ， m e m o r i a la n n e a l i n ga n da n n e a l i n gw i t hb a c ks e a r c h i n ga r ei n t r o d u c e dt os o l v et h e p r o b l e m ss u c ha l st h es e l e c t i o no fi n i t i a lt e m p e r a t u r e t oa v o i df a l l i n gi n t ol o c a l o p t i m u mt o oe a r l ya n dp r e v e n t i o no fm i s sg l o b a lo p t i m u m i nd o i n gs o ，t h ee f f e c t o fs c h e d u l i n go p t i m i z a t i o ni sf u r t h e ri m p r o v e d 卜 一 t h es c h e m ew h i c hi s p u tf o r w a r di n t h i sp a p e ri si m p l e m e n t e d ，a n dt h e e f f e c t so ft h ea p p l i c a t i o no fo p t i m i z i n gt h es c h e d u l i n ga n da l l o c a t i o np r o c e s sa r e t e s t e d f i n a l l y ，t h ek e yp a r a m e t e r sa n de x p e r i m e n td a t a a r eg i v e nt ov e r i f yt h e e f f e c t s k e yw o r d s ：h i l g hl e v e ls y n t h e s i s ：s i m u l a t i o na n n e a l i n g ：s c h e d u l i n g ：a l l o c a t i o n 哈尔滨1 二稃大学硕+ 学位论文 目录 第1 章绪论l 1 1 课题背景l 1 1 1 数字系统的设计层次一1 1 1 2 高级综合的作用和特点2 1 1 3 国内外相关研究动态和进展一4 1 2 本文的主要工作6 1 3 论文的结构7 第2 章高级综合及其调度和分配算法8 2 1 高级综合基本任务和功能8 2 2 高级综合的数据表示1 0 2 2 1 高级综合的输入1 0 2 2 2 高级综合的中间结构1 1 2 2 3 高级综合的目标结构1 2 2 3 时序调度及主要算法1 4 2 3 1 调度算法分类1 4 2 3 2a s a p 和a l a p 算法1 5 2 3 3f d s ( f o r c ed i r e c t e ds c h e d u l i n g ) 算法1 6 2 3 4l s ( l i s ts c h e d u l i n g ) 算法1 7 2 3 5 整数线性规划算法1 7 2 4 资源分配及主要算法1 9 2 4 1 构造法19 2 4 2 分解法1 9 2 5 本章小结2 0 第3 章模拟退火算法及其改进”2 1 产 哈尔滨t 程大学硕士学位论文 3 1 模拟退火算法2 1 3 1 。1 基本思想2 1 3 1 2 组合优化与物理退火的相似性2 2 3 1 3 模拟退火算法的步骤2 3 3 2 模拟退火算法的改进策略”2 4 3 2 1 加温退火法2 4 3 2 2 带记忆功能的模拟退火2 5 3 2 3 带升温过程的模拟退火2 5 3 2 4 带返回搜索的模拟退火2 6 3 2 5 多次寻优法2 7 3 3 本章小结”2 7 第4 章基于模拟退火算法的调度优化及其改进2 8 4 1 基于模拟退火框架的调度优化2 8 4 1 1 调度优化与模拟退火的数学模型o2 8 4 1 2 将分配结果引入调度过程2 9 4 1 3 能量函数的形式和邻域的产生3 0 4 1 4 终止准则和冷却进度表3 1 4 1 5 基于模拟退火的调度优化流程3 2 4 2 使用改进的模拟退火流程- 3 4 4 3 本章小结3 8 第5 章基于团划分的资源分配实现”3 9 5 1 资源分配的问题模型3 9 5 1 1 功能单元分配问题3 9 5 1 2 寄存器分配问题4 0 5 2 基于团划分算法的资源分配4 1 5 2 1 基于团划分算法的功能单元分配4 l 5 2 2 基于团划分算法的寄存器分配4 2 产 0 哈尔滨t 程大学硕士学何论文 5 3 种快速团划分算法的实现“4 3 5 4 本章小结。4 6 第6 章实验结果及分析4 7 6 1 输入数据一4 7 6 1 1 输入的表示方法4 7 6 1 2 测试用例4 7 6 2 基于模拟退火算法的调度优化4 9 6 2 1 指定时间约束下的造价优化5 0 6 2 2 考虑时间和造价的多目标优化5 2 6 3 改进模拟退火算法的效果5 4 6 3 1 加温退火5 6 6 3 2 记忆功能和返回搜索5 6 6 3 3 升温过程5 7 6 4 本章小结5 7 结论“5 9 参考文献6 0 攻读硕士学位期间发表的论文和取得的科研成果6 5 致 射6 6 哈尔滨丁程大学硕士学位论文 第1 章绪论 1 1 课题背景 1 1 1 数字系统的设计层次 数字系统的电子自动化设计具有明显的层次性，根据抽象级别的不同， 自底向上划分为版图级、电路级、逻辑级、寄存器传输级( r t l ) 、算法级( 或 称行为功能级) 和系统级等若干不同的层次【1 】。通过这些设计层次，解决数字 系统以下三个方面的问题：系统要实现的功能( 行为领域) 、系统的逻辑组 成( 结构领域) 和系统具体实现的物理与几何特征( 物理领域) 。 版图级也称为物理级，是数字电路设计描述的最低层次。在版图级，以 几何图形描述硬件，如晶体管、二极管、电阻和连线等元件。需要注意的是， 版图级只是描述结构，硬件的功能隐含于器件的物理特性关系中。在这一层 次，系统的特性与器件的互连方式和器件的加工工艺都有关。 电路级用器件之间的互连关系描述硬件。在电路级，使用电路的微分方 程来描述系统的功能，电路的结构则由器件间的互连关系描述，其在整个设 计层次中位于版图级之上。电阻、电容和各种晶体管等器件是电路级的基本 单元。 逻辑门级( 简称为门级) 是数字系统设计的主要层次，各种逻辑门是这 一层次的基本单元，包括与f - j 、非门、或门、与非门和异或门等。此外，逻 辑门级的基本单元还包括锁存器和触发器等逻辑单元。逻辑门级在整个设计 层次中位于电路级之上，该层最典型的描述是原理图和布尔方程，基本的时 序单元是延时。因此，逻辑门级的设计需要仿真和时序分析工具，来计算系 统设计的性能。 寄存器传输级，也称r t l ( r e g i s t e rt r a n s f e rl e v e l ) ，描述较之门级描述更 为抽象。寄存器、计数器、算术逻辑单元( a l u ) 等元件是寄存器传输级的基 本单元。在这一层次也称基本单元为功能块，这些功能块的规模比基本门电 哈尔滨工程大学硕七学位论文 路单元要大得多。寄存器传输级位于逻辑门级之上，该层的结构描述是基本 单元的互连，反映其功能的是真值表和状态图。r t l 级的主要设计工作是优 化、综合、状态编码以及工艺映射，减少系统使用的逻辑门数，缩短完成运 算所需的时钟周期。有限状态机( f s m ) 、布尔方程和二元决策图( b d d ) 是寄 存器传输级的典型描述。 行为级也称算法级。控制流图( c f g ) 、数据流图( d f g ) 、控制数据流图 ( c d f g ) 和行为有限状态机( b f s m ) 是这一层次的典型描述。算法级位于r t l 级之上，使用运算步来描述设计。一个运算步可占一个或多个时钟周期，表 示相邻的输入、输出或同步点之间的数据处理。在算法级，输入、输出和不 同的运算通过运算语句和控制语句进行组织。 行为级之上的层次是系统级，也是数字系统层次化设计的最高层次。， 计算机、总线接口和磁盘驱动器等各种大的数字单元是系统级的基本单元。 表1 1 简要描述了数字系统设计的各个抽象层次。 表1 1 数字系统设计的层次 抽象层次电路功能描述基本单元时序单元 版图级几何图形 双极型晶体管、m o s 晶 电路级 电压、电流的微分方程物理时间 体管、电阻、电容等 逻辑门、触发器、锁存器 逻辑门级原理图延时 等 寄存器传布尔方程，有限状态机，二 寄存器、计数器、多路选 时钟周期 输级元决策图择器、a l u 等 数据流图，控制流图，控制 行为级输入、输出和运算控制运算步 数据流图，行为有限状态机 自然语言描述或者相互通 系统级 进程及相互之间的通信 数据处理 信的进程 1 1 2 高级综合的作用和特点 综合指从系统的行为领域到结构领域，从高层次设计到低层次设计的自 动转换和优化过程。根据起始层次的不同，综合可划分为逻辑综合、寄存器 哈尔滨工程大学硕士学位论文 传输级综合等。软件开发时，高级语言编写的程序可以由编译器自动转换为 可执行的机器码。与之类似，综合器可以自动把硬件的高层次描述转换为低 层次描述。 高级综合( 也称为高层次综合，行为综合) 是从算法级到寄存器传输级 ( r e g i s t e rt r a n s f e rl e v e l ，r t l ) 之间的转换【3 ，其目标是遵照一定的约束条件， 将数字系统的行为描述自动转换成结构描述。图1 1 描述了高级综合与数字 系统设计中抽象层次的关系。高级综合的引入，大大减轻了设计者的工作量， 显著缩短了设计周期，提高了设计质量，是设计自动化中的关键技术。 物 为特征 综合 图1 1 数字系统自动设计的层次关系 高级综合技术是一种数字系统自动设计技术，实现从较高设计层次的描 述自动转换到较低设计层次的描述，近2 0 年来始终是数字系统设计研究的热 点【2 】。在应用需求的驱动下，随着芯片复杂程度的提高，集成电路工艺水平 也不断提高。到2 0 1 0 年，4 5 n m c m o s 工艺的高速、低功耗超大规模i c 将量 产，其时钟频率将达到1 0 2 0 g h z ，能在单个芯片上集成数十亿个晶体管。 随着数字系统和v l s i ( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t s ) 复杂性的提高，设 计规模的不断增大，加之激烈的市场竞争，设计层次也越来越向高层次发展。 高层次设计中做出的合理决策，可以产生低层次综合无法替代的优化效果， 哈尔滨工程大学硕士学何论文 因此高级综合越来越受到重视。当前e d a 界广泛使用高级综合，全球有多家 e d a 工具厂商都有成熟的高级综合工具。 除了提高了设计速度、缩短了产品开发周期之外，高级综合技术的发展 给整个产品的设计带来了如下结果： 首先，有利于设计的重用。v h d l 语言的特性之一就是与工艺无关，因 此与工艺相关的细节在高层次设计中无需关心。只要用厂商的新工艺库重新 进行综合，就可以适应半导体厂商的工艺改变，有利于快速设计出新产品。 其次，由于描述层次较高，设计中出现的问题和错误可以在早期得到发 现，且更容易进行修改。与低层次的结构描述相比，高层次设计中的行为描 述更为简洁，且更易于理解和编写。这就使设计的复杂性相应降低，不仅使 描述错误的发生大大减少，而且使仿真时间大大缩短。 最后，为设计过程的自动文档化提供了条件。设计的规范说明和需求说 明在高层次设计中一般用v h d l 语言描述，在经高级综合以后，再经过用户 修改和验证，仍可转换为v h d l 语言描述的结果，方便设计文档的管理。 高级综合的行为描述不区分数据处理与数据寄存，不涉及底层元件，其 内容为高层次电路行为。主要特点为： 1 ) 使用抽象数据类型、各种控制结构和算法等，设计的抽象层次较高； 2 ) 将设计按照功能划分为一些需要若干时钟周期来完成的块，每个块代 表一个功能； 3 ) 需要将自定义的约束以及一些时钟跳变沿插入到设计中合适的地方。 1 1 3 国内外相关研究动态和进展 高级综合产生于6 0 年代，在近十几年得到飞速发展。十年来，各种新的 高级综合算法和工具不断出现，在各个主要研究方向，如低功耗高级综合、 基于可测性的高级综合和基于新模型的高级综合等研究方向均取得了新的发 展。 功耗一直是电路设计中的一个重要设计问题，特别是最近在移动通信、 4 哈尔滨工程大学硕士学位论文 医疗器械等应用对功耗提出了相当苛刻的要求。文 4 提出了一种低功耗综合 的活动模型，在调度过程中使用划分技术达到低功耗。文 5 考虑资源共享， 提出了功耗的下界估计方法，其使用的综合策略基于多电压和算术级变换， 通过重定时、减少循环和展开等方法降低功耗。 由于现在电路越来越复杂，电路的测试越来越困难，高级测试综合在近 年来得到越来越多的重视。将可测性提前到综合过程中考虑，不但可以使底 层测试的复杂度和所需硬件资源大为减少，还可以提高故障的覆盖率，从而 减少设计迭代。文 6 在寄存器分配阶段考虑可测性，使用一种基于有权图着 色的算法，不但显著减少了a t p g 时间，还使可控性和可观察性得到了一定 程度的增强。文献 7 】则讨论了基于b i s t 和层次化的可测试性。 近年来，基于多项式符号代数和p e t r i 网等新模型的综合方法也相继出 现，使高级综合技术的发展进入了新阶段。文献 8 提出的算法将位级描述的 组合或时序电路转化为字级多项式描述，并在高级综合工具p o l y s y s 中实 际应用了该算法。文 9 通过把行为级描述多项式分解为在元件库中存在的多 项式组合，实现了一种基于符号代数的数据路径综合算法。文【1 0 实现了一 种能有效减少多项式中运算操作的算法，方法是对多项式提取公因子和消去 公共子表达式。文 1 1 提出基于多项式符号代数的详细布局布线方案。文 1 2 通过基于p e t r i 网模型的一种并行方案进行高级综合，取得了较好的优化效 果。 上世纪8 0 年代以后，学术界和工业界开发了一系列的高级综合工具。其 中，美国s y n o p s y s 公司的b c ( b e h a v i o rc o m p l i e r ) 1 3 最为成熟，并首先进行了 商业化。比较有影响的高级综合工具还有荷兰艾因霍温工业大学的e s c a p e 和法国的t i m a i n p g 实验室的a m i c a l e l 3 等。 9 9 年底，q u i c k t u m 公司推出其第五代设计验证系统m e r c u r y 1 3 】，该 系统从概念到系统级集成的范围，为复杂集成电路设计提供了连续的验证环 境。，f o r t e 公司于0 3 年的设计自动化大会上推出了c y n t h e s i z e r 工具【1 引，在 j o h nc o o l e y 的d a c ( 设计自动化会议) 总结报告中，这中基于s y s t e mc 的工 哈尔滨丁程大学硕士学位论文 具得到了较好的评价。 在数字系统的高级综合技术理论研究和应用开发方面，国内许多科研单 位和大专院校也做了大量工作，并取得了大量成果。其中以北京理工大学刘 明业教授为首的a s i c 研究所，不但在高级综合的理论研究上解决了一系列 关键性技术问题，在应用系统h l s b i t 的开发应用方面也达到了比较高的水 亚【14 】 o 高级综合技术的研究将会不断取得新进展。在目标架构考虑、领域内综 合、通用库组织、设计重用和可测性高级综合等热门研究方向，新算法和新 的解决方案会不断出现。此外，如何与底层的布局结合，如何实现软调度方 法等都是有意义的探索方向。未来高级综合技术的研究依然大有可为。 1 2 本文的主要工作 本文首先分析高级综合的流程和步骤，着重研究高级综合的两个最重要 的子任务：时序调度和资源分配。 在分析各种调度和分配算法的基础上，采用基于模拟退火框架的调度算 法。在调度过程中，对于每次产生的调度方案，使用基于团划分算法的分配 算法，将分配的结果作为调度方案能量函数的一部分评价准则，从而同时进 行调度和分配的优化。为了减少算法执行时间，这里提出了一种简化的团划 分实现。 模拟退火算法具有多种优点，但是也存在一些固有的问题。为了提升算 法性能，在标准模拟退火算法的基础上，结合高级综合问题的特点，对模拟 退火算法的流程进行了改进。采用加温退火、记忆功能、返回搜索和升温过 程等策略，以改进标准模拟退火算法，从而在确定初始条件、避免局部最优 和消除随机性带来的算法固有缺点等方面获得提升。 本文实现了所提出的调度和分配优化方案，通过实验验证了使用改进模 拟退火算法进行高级综合的效果，详细说明了实验过程，包括主要的参数和 实验数据等。 6 哈尔滨工程大学硕士学位论文 i i 1 3 论文的结构 本文第1 章首先介绍了数字系统的设计层次，在此基础上说明了数字系 统高级综合的作用和特点，并介绍了国内外的研究动态和进展。 第2 章详细介绍高级综合的调度和分配问题，回顾和总结经典的调度和 分配算法，并说明了每种算法的特点和适用范围。对经典算法的分析，是本 文提出新方案的基础。 第3 章介绍模拟退火算法的理论，说明了模拟退火算法的几种常用的改 进方案，并说明了每种改进方案的理论依据和性能特点，为说明本文提出的 调度优化方案做准备。 第4 章详细介绍如何将模拟退火算法实际应用于高级综合的调度优化， 详细说明了本文提出的基于改进模拟退火算法的调度优化方案。其中，进行 能量函数的计算时，需要进行资源分配。 第5 章介绍了所采用的基于团划分的资源分配算法，并说明本文提出的 一种团划分的快速近似实现。 第6 章给出了详细的实验数据，对本文提出的调度和分配优化方案在单 目标和多目标两种情况下的效果进行了验证。对本文引入的几种模拟退火算 法改进策略，也通过实验数据验证了其效果。 哈尔滨t 一i - d 大学硕士学位论文 第2 章高级综合及其调度和分配算法 高级综合在行为描述与实现它的硬件实现之间架起一座桥梁，将数字系 统的行为描述自动转换为寄存器传输级的结构描述。高级综合的优化目标是 在满足目标集合和约束条件的基础上，寻求实现算法功能的最优寄存器传输 级方案，为给定的行为功能找出一种花费最少的硬件结构。因此，在优化过 程中需要同时考虑诸多因素，包括电路结构、存储结构、互连结构和时序设 计等。 高级综合的算法主要是调度和分配算法。调度的任务是在一定的约束条 件下，将每一个操作安排到合适的控制步中，主要解决行为描述操作的时间 安排问题。分配则主要解决操作步骤和硬件资源的匹配问题。时序调度是高 级综合中的关键问题，其结果的优劣直接影响电路的速度、面积和功耗等指 标。时序调度又和资源分配问题紧密相关，调度和分配的优化，直接决定了 数字系统的性能和代价。 2 1 高级综合基本任务和功能 高级综合的基本功能，是在数字系统的算法行为确定之后，在满足处理 性能的前提条件下，根据给定的约束条件，由算法级的行为描述得到一个优 化的寄存器传输级结构。从数据流的输入到输出，可以分解为以下四个主要 任务【1 5 】： 1 ) 将设计输入转化为内部表示。高级综合系统的输入应包括数字系统的 行为描述、设计约束以及高层次元件库和工艺库等【3 】。高级综合将设计输入， 如v h d l ，变换到一种基于图的表示方式，通常为控制数据流图【1 6 ( c o n t r o l d a t af l o wg r a p h ，c d f g ) 。在c d f g 中，数据操作用结点表示，数据依赖关 系或控制关系由结点之间的有向边来表示。 2 ) 时序调度t l s ( s c h e d u l i n g ) ，简称调度。其主要任务是，在满足约束条 件和数据依赖的前提下，将数据流图中的各个操作结点安排到合适的控制步 以在一个控制步中同时执行；另一方面，为了减少硬件开销，要合理控制各 个控制步中的并行度。因此，调度已经成为高级综合过程中最重要的环节。 3 ) 资源分配【1 5 】( a l l o c a t i o n ) ，也称为分配，目的是为数字系统分配资源， 目标是使数据通道中硬件数量最少。资源分配需要将功能单元分配给每一个 操作，将寄存器分配给所有变量，还要为数据传输分配相应的总线和多路选 择器。数字系统的数据通道可以简化，是因为相容关系的存在，即不同控制 步中相同类型的操作可以共享同一个功能单元，不同变量只要生命周期不重 叠就可以共享同一个寄存器。同样，同一条数据总线可由发生在不同时刻的 数据传输共享。进行资源分配时，需要根据这些相容关系合理分配硬件资源。 4 ) 生成目标结构。在进行了调度和分配两个步骤之后，就可以在得到的 数据通道中，由各个控制步所需的控制信号产生相应的状态图，再根据得到 的状态图生成控制器。 图2 1 描述了高级综合的基本流程。 高级综合的四个步骤之间是相互影响、相互依赖的，特别是调度和分配 为两个最重要的过程。一方面，在调度过程中，需要知道不同操作间的时间 延迟，才能得到最有效的调度方案，而只有在功能单元及其互连细节都得到 确定之后，这一信息才能被获取，此外，在一些调度算法中，必须知道两个 操作是否使用了同一个功能单元，才能确定它们是否应该调度到同一个控制 步；另一方面，在资源分配过程中，必须知道各个控制步中哪些操作将被并 行执行，才能确定需要使用的功能单元的数量，每个操作在这些功能单元中 又应如何安排，这些信息都来自于时序调度。 在新一代高级综合系统中，除了上述基本功能之外，还应该具有如下功 能【1 3 】： 首先，要能够进行硬件描述语言的结构优化，包括时间驱动的计算优化、 9 哈尔滨t 程大学硕士学位论文 资源共享和元件参数化等。此外还需要具有快速构造多种方案的能力，并可 以自动选择和比较，以便在总体结构和框架上进行优化。 硬连 辑综合的输入 用于文档管理库或其它 逻辑综合工具的输入 图2 1 高级综合流程 此外，还要能支持层次化的设计和混合类型设计，能够进行功能验证、 性能评估，并完成不同结构的取舍，将系统的评估与设计结合在一起。能够 依据a s i c 产品库的关键部位，通过综合优化快速根据行为描述生成所需参 考电路，从而确定最终设计。 2 2 高级综合的数据表示 2 2 1 高级综合的输入 如上文所述，高级综合作用的层次范围是从算法级的行为描述到寄存器 传输级的结构描述。因此，高级综合的输入必须包括行为级描述，通常是行 为级的h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ，硬件描述语言) 描述。一般采用 标准的硬件描述语言v h d l 或v e r i l o g 等，其优点是简单、代码少，且容 l o 哈尔滨工程大学硕士学位论文 易发现设计中的错误。高级综合工具从h d l 源码提取出相关的i o 端口的标 准规范、存储器件需求、控制流和数据流等信息，并为后续综合步骤提供以 中间数据结构表示的设计描述作为输入。除了行为描述之外，输入数据还需 要包括设计约束、高层次元件库和工艺库。其中，设计约束主要包括操作步 数( 周期数) 、所用硬件资源数和电路最大面积等信息。乘法器、a l u 运算器 以及存储器等元件的信息由元件库提供，有时还包括硬件实现的相关信息和 使用规范。器件的一些基本信息，如器件的面积和延迟时间是否满足约束等， 由工艺库来提供。 2 2 2 高级综合的中间结构 在高级综合过程中，行为级描述的代码首先要转换为一定的内部表示， 即某种严格定义的中间格式。整个高级综合的过程都要在内部设计表示上进 行。高级综合的内部表示形式分为三类：数据流i 羽( d a t af l o wg r a p h ，d f g ) 、 控制流图( c o n t r o lf l o wg r a p h ，c f g ) $ d 控制数据流匿 ( c o n t r o ld a t af l o wg r a p h ， c d f g ) 。 在d f g 中，程序中的操作由图的结点表示，结点间有向边的方向代表数 据流动的方向。在表示控制结构上能力有限，是数据流图的主要缺点。 c f g 也是由结点和有向边组成的。结点包括操作结点和分支结点两类， 其中操作结点的意义比数据流图中的结点更为广泛，不但可以是算术、逻辑 和赋值等运算，还可以是子程序调用；各种控制结构由分支结点表示，对应 于v h d l 中的各种控制语句，如i f 、c a s e 和w h i l e 等。c f g 中的有向边 表示结点间的数据依赖关系。与数据流图相比，控制流图更适用于表示各种 控制结构，其缺点是在数据流的分析和变换上能力有限。 在数据流图基础上增加控制结点，就形成控制数据流图 16 】。当前多使用 c d f g 作为中间数据结构，它综合了控制流图和数据流图的特点。控制数据 流图是一种有向无环图，其结点可以是操作结点或控制结点。c d f g 中的有 向边代表从一个结点到另一个结点值或控制的传递。 哈尔滨工程大学硕士学何论文 一般来说，c d f g 中的结点可以被分为以下几类： 1 ) 操作结点：表示数学、逻辑或关系操作。 2 ) 调用结点：表示子程序模块的调用。 3 ) 控制结点：表示条件判断或循环结构一类的操作。 4 ) 存储结点：表示与变量和信号相关的分配操作。 图2 2 给出了v h d l 代码和对应的c d f g 的一个例子。其中，结点l 、2 和6 是操作结点，结点3 是存储结点，结点4 、5 和7 是控制结点。 a ：= b + c + d ： w h i l e ( a 0 ) l o o p a ：= a 一1 ： e n dl 0 0 1 3 a ( a ) 一段简单的v h d l 代码 伯1 对应的c d f g 图2 2v h d l 代码片段和对应的c d f g 2 2 3 高级综合的目标结构 高级综合将行为级描述转化为内部设计表示后，经过调度和分配等步骤， 形成最后的寄存器传输级结构。需要特别注意的是，无论输入的行为描述有 多少种不同的形式，都必须依据一定的通用模型来建立输出的寄存器传输级 结构。带有数据通道的有限状态机( f s m d ，f i n i t es t a t em a c h i n ew i t h 哈尔滨工程大学硕士学位论文 d a t a p a t h ) 1 7 】和带有数据通道和协处理器的有限状态机( f s m c ，f s m dw i t h c o p r o c e s s o r ) 【1 8 】是最常用的通用模型。 2 2 3 1f s m d 模型 f s m d 模型是一种可以代表全部硬件设计的通用模型，由g a j s k i 等在 1 9 9 2 年提出【1 7 1 。在f s m ( f i n i t es t a t em a c h i n e ，有限状态机) 基础上增加数据操 作能力，就成为f s m d 。其定义为五元组 【1 7 】。其 中， s ：状态集合； ，：输入集合，被数据通道输出的条件信号扩展： d ：输出集合，被内部变量赋值集合扩展； 斥从i x s 到s 的映射，生成下一状态的函数； h ：从s 到o 的映射，输出函数。 2 2 3 2f s m c 模型 在f s m d 模型基础上，发展出了f s m c 模型。其特点是一部分操作可以 在协处理器上运行。协处理器可以是功能部件或运算电路，也允许协处理器 本身就是f s m d 或f s m c 模型。 f s m c 使用五元组 定义【1 8 】，其 中： & ：f s m c 中协处理器的集合； s x h & ：f s m c 状态集合； 厶：全部协处理器的输入集合； 4 ：内部赋值集合； q ：全部协处理器的输出集合； f 生成下一状态的函数； 办：输出函数； i x s s x r i 厶：f s m c 输入集合； o x a x hd c ：f s m c 的输出集合，被a 和协处理器局部输出集合所扩展； 哈尔滨丁程大学硕士学位论文 一个f s m c 可以被定义为一个f s m d 加上具有n 个协处理的集合c 。其 中，每一个协处理g 也定义为一个f s m c 。f s m c 层次结构由一个项层控制 器和一个可能包括若干协处理器的数据通路集合组成。图2 3 描述了f s m c 的结构模型。 图2 3f s m c 结构模型 2 3 时序调度及主要算法 调度是高级综合中的关键问题，其结果直接影响系统实现的性能。时序 调度主要任务是，按照数据相关性和约束条件的要求，将每一个操作安排到 合适的控制步( c o n t r o ls t e p ) ，主要解决行为描述操作的时间安排问题。一 个控制步在同步系统中对应一个或几个时钟周期，是调度中最基本的时序单 位。时序调度优化的目标是，在一定的约束条件下