（计算机软件与理论专业论文）高级综合优化算法研究.pdf

l 喻尔滨i 群人学硕十学位论文 摘要 电子系统的设计复杂性和系统功能一直在呈几何级数增长，全球 的竞争又加剧了产品丌发周期的缩短。因此，对电子设计自动化工具 的需求越来越迫切，要求也f 1 益提高，这一切促进了e d a 的发展，加 速了设计方法和设计工具的更新换代。 本文在大量分析了以往高级综合系统所采用的技术基础上提出了 我们的高级综合优化策略。本文提出了两种类型的高级综合方法，其 一是提出了针对控制占主要部分的电路的高级综合方法，该方法采用 了基于控制流图的中间表示结构，在调度过程中采用了针对咳电路特 点的推测技术。这是一种专用综合系统，适用面比较小，但在所针对 具体的领域能够取得较理想的综合结果。 其二是提出了一种多目标的高级综合优化策略，该方法用在高级 综合的调度之前，其核心是对系统进行划分，在将行为描述转化为内 部表示模型的时，通过探索中间表示结果的关系来发现原设计描述中 的控制关系和并行计算，以便在高级综合中取得理想的结果，同时将 行为描述转化为图的过程中体现多种优化目的，所采用的中间表示模 型为基于p e t r i 网的内部表示模型，划分采用了模拟退火算法。该方法 是可扩展的，允许设计者自己引入所要的优化目的。 本文实现了模拟退火算法，用于对系统所转化的图的划分，在本 文的最后给出了具体的软件实现的详细说明，包括图的输入，解的格 式，候选解的生成，解的造价等等，给出了部分的实验数掘。 关键词：高级综合：模拟退火：p e t r i 网；数据流图；控制流图 ! 窒玺鎏：；堡銮主鎏土兰篮誊銮 a b s t r a c t t h ed e s i g n c o m p l e x i t ya n ds y s t e m f u n c t i o no fe l e c t r o n i c s y s t e m h a v eb e e ni n c r e a s i n g l a r g e l y ，t h ec o m p e t i t i o n f r o mt h e g l o b a l a l s o s h o r t e nt h e d e s i g np e r i o d ，t h e r e f o r e ，t h e d e m a n df o rt h e t o o l so f e l e c t r o n i c d e s i g n a u t o m a t i ci st r e m e n d o u sa n dt h e r e q u i r e m e n t f o r e f f i c i e n c yo fe d a t o o l si sm o r ea n dm o r ep r e c i s e a l lo ft h i sp r o m o t e s t h eu p d a t i n go ft h ee l e c t r o n i cd e s i g nm e t h o d sa n dt o o l si ns o m ec a s e s i nt h i s p a p e rw ep u t f o r w a r dt w ok i n d so fh i g hl e v e l s y n t h e s i s m e t h o db a s e do n r e s e a r c h i n gt h et e i z h n o l o g ya d o p t e di n o t h e rh l so r h l s o p t i m i z a t i o n o n ei s a s p e c i f i ch l s f o rc o n t r o li n t e n s i v ed e s i g n s ，w e a d o p t c o n t r o l f l o w g r a p h a st h ei n t e r n a l r e p r e s e n t a t i o n a n du s et h e s p e c u l a t i o nt e c h n o l o g yd u r i n gt h es c h e d u l i n g i ti se f f i c i e n tw h e na p p l i e d i nt h ec o n t r o li n t e n s i v ed e s i g nb u tt h eq u a l i t yo f s y n t h e s i sr e s u l t si sn o t w e l la c c e p t e dw h e nu s e df o ro t h e rt y p eo f d e s i g n t h eo t h e ri sam u l t i - t a r g e th l s o p t i m i z a t i o nm e t h o d ，u s e db e f o r e t h es u b t a s ko fh l ss c h e d u l i n g t h ee s s e n c eo ft h em e t h o di sas y s t e m p a r t i t i o na l g o r i t h m ，t h em u l t i - t a r g e to p t i m i z a t i o n i sr e f l e c t e dw h e n c o n v e r tt h eb e h a v i o r a l d e s c r i p t i o n i n t oa g r a p h ，t h ep u r p o s e o ft h e p a r t i t i o ni st of i n dt h ee x p l i c i tc o n t r o lr e l a t i o na n dp a r a l l e lc o m p u t a t i o n t h ei n t e r n a l r e p r e s e n t a t i o n w ea d o p t e di sap e t r in e tb a s e do n e ，t h e p a r t i t i o na l g o r i t h m i sa s i m u l a t e d a n n e a l i n ga l g o r i t h m t h e m e t h o di s e x t e n s i b l e ，t h a ti s t o s a yt h ed e s i g n e r sc a np r o d u c ea n da d dt h e i ro w n o p t i m i z a t i o np u r p o s et ot h em e t h o d w ei m p l e m e n tt h e s i m u l a t e d a n n e a l i n ga l g o r i t h ma n d u s ei tt o p a r t i t i o nt h eg r a p hg a i n e df r o mt h eu s e rd e s i g n ，a tl a s t ，w ei n t r o d u c ea n d i l l u s t r a t et h es o f t w a r e p a r t ，i n c l u d i n g t h e g r a p hi n p u ts t y l e ，t h e d a t a s t r u c t u r eo ft h er e s u l t ，t h em e t h o dt oc r e a t ec a n d i d a t er e s u l ta n dt h ec o s t o fr e s u l t ，w ea l s og i v es o m ee x p e r i m e n td a t a 堕玺鎏王堡盔主璧圭兰鲁鲨苎 k e yw o r d s ：h i g h l e v e l s y n t h e s i s d a t a f l o wg r a p h ； s i m u l a t e d a n n e a l i n g ；p e t r i n e t c o n t r o l f l o wg r a p h 哈尔滨1 程大学硕士学位论文 1 1项目背景 第1 章绪论 1 1 1集成电路的设计方法和工具的变革 1 9 5 9 年世界第一个集成电路只有4 个晶体管，而1 9 9 7 年时，一个芯 片上可以集成的晶体管数量已经高达4 0 0 0 多兆了。4 0 多年来集成电路技 术发生了惊人的变化，经历了小规模( s s i ) ，中规模( m s i ) ，大规模( l s ) ， 超大规模( v l s i ) ，目前已进入特大规模阶段( u l s i ) ，集成电路产业发展 也是r 薪月异，以集成电路为基础的电子信息产业已成为世界第一大产业 1 3 。电路性能迅速提高，生产工艺不断进步，目前生产工艺以达到0 1 3 u m 。 随着微电子技术的进步，人们对集成系统的需求也在不断提高，计算机、 通信、消费类电子产品、工业及军事等各种领域都大量的需要集成电路。 随着集成技术的不断发展和集成度的迅速提高，集成电路芯片的设训 工作越来越复杂，因此急需在设计方法和设计工具这两方面有一个大的变 革，这就是人们所说的“设计革命”。各种计算机辅助工具的涌现以及设 计方法学的诞生适应了这样的要求。 e d a 技术在此需求上应运而生，e d a ( e l e c t r o n i cd e s i g na u t o m a t ic ) 即电子设计自动化技术，是一种以计算机为基本工作平台，利用计算机图 形学、拓扑逻辑学、计算数学以至人工智能学等多种计算机应用学科的最 新成果而丌发出来的一整套软件工具，是一种帮助电子设计工程师从事电 子元件产品和系统设计的综合技术，e d a 技术可以看作是电子c a d 的高级 阶段“。 电子系统( 集成电路) 的设计自动化的发展，大致可分为i 个阶段【： 7 0 年代的第一代e d a 称为计算机辅助设计c a d ( c o m p u t e ra i d e d d e s i g n ) 系统，它以交互式的图形编辑和设计规则检查为特点，硬件采用 哈尔滨工程人学硕士学位论文 1 6 位小型机，逻辑图输入、逻辑模拟、电路模拟与版图设计及版图验证 是分别进行的，人们需要对两者的结果进行多次的比较和修改才能得到币 确的设计。第一代c a d 系统的引入使设计人员摆脱了繁复、易出错误的手 工画图、机械的刻红膜的传统方法，大大提高了效率，因而得到迅速的推 广。但是它仍不能适应规模较大的设计项目，而且设计周期长，费用高。 投片制作后发现原设计存在错误，不得不返工修改，其代价是昂贵的。 8 0 年代出现的第二代e d a 系统，称为计算机辅助工程 c a e ( c o m p u t e r a i d e de n g i n e e r jn g ) 系统。它以3 2 位工作站为硬件平台， 集逻辑图输入、逻辑模拟、测试码生成、电路模拟、版图设计、版图验证 等工具于一体，构成了比较完整的设计系统。工程师以输入线路图的方式 丌始设计集成电路，并在工作站上完成全部设计工作。 9 0 年代高屡次 设计自动化 8 0 年代计算机 辅助工穰 7 0 年代计算机 辅助髓计 图1 1 集成电路设计自动化的各个阶段 这时的系统不仅有设计全定制电路的版图编辑工具，还包括有门阵 列、标准单元等电路的自动设计工具和具有经过制造验证的，针对1 i 同工 艺的单元库。对于门阵列、标准单元等电路，系统可完成自动布局、自动 布线功能，因此大大减少了版图设计的工作量。在c a e 系统中，更重要的 是引入了版图与电路之间的一致性检查工具，此工具对版图进行版图参数 2 哈尔滨工程大学硕士学位论文 提取( l p e ) 得到相应的电路图，并将此电路图与设计所依赖的原电路图进 行比较，从而发现设计是否有错。同时还将提取得到的版图寄生参数进入 电路图，做一次电路模拟，以进一步检查电路的时序关系和速度是否符合 原设计要求。这些功能的引入保证了投片的一次成功率，但是一致性检查 和模拟仍然是设计最后阶段才加以实施的，发现错误时，还需要修改版图 或修改电路，付出相当的代价。 9 0 年代，芯片的设计复杂度越来越高，数万门以至数十万门的电路 设计的需求越来越大。单是依靠原理图输入方式已不堪承受，采用硬件描 述语言h d l 的设计方式就应运而生，设计工作从行为、功能级丌始，e d a 向设计的高层次发展。第三代e d a 系统的特点就是高层次设计的自动化 h l d a ( h i g hl e v e ld e s i g na u t o m a t i o n ) 。 第三代e d a 系统中引入了硬件描述语言，一般采用两种语言。：v h d l 语言和v e r i l o gh d l 语言；此外引入了行为综合和逻辑综合工具。采用较 高的抽象层次进行设计，并按层次式方法进行管理，大大提高了处理复杂 设计的能力，设计所需的周期也大幅度缩短；优化综合工具的采用使芯片 的品质如面积、速度功耗等得到了优化，因而第三代e d a 系统迅速得到了 推广和应用。 硬件描述语言的优点极其突出。描述方便，代码量小，易于发现设计 中的错误。如对3 2 的加法器，利用图形输入软件需要输入5 0 0 至1 0 0 0 个 门，工作量很大，而利用h d l 语言只需要写一行“a = b + c ”即可。而且， h d l 语言可读性强，易于修改和发现错误。同时高层次设计是与具体的生 成技术无关的，即与生产工艺无关。一个h d l 原码可以通过逻辑综合工具 综合为一个现场可编程门阵列，既f p g a 电路，也可以综合成某一工艺所 支持的专用集成电路，即a s i c 电路。对于不同的生产工艺，h d l 原码是 完全一样的，仅需要对不同的工艺库重新进行综合”3 。 借助于e d a 工具，设计者可以从设计的起始阶段控制整个设计，随时 监测、模拟系统的逻辑f 确性，判断延时情况等在以前只能在系统设计完 成之后才能做的事情，这样大大降低了由于错误设计造成的成本增加，设 计周期延长等弊端，特别是对于当前和今后准备采用i p ( i n t e l l e c t u a p r o p e r t y ) 核结构的集成电路和s o c ( s y s t e mo f f ac h j p ) ，由于存在嵌 3 哈尔滨工程大学硕士学位论文 入式软件的原因，要做到软件和硬件的合理分配及并行开发验证必须借助 于e d a m 具。 1 1 2 数字系统的设计层次 数字系统的设计包括行为、结构和物理三个领域。行为指系统的功能， 结构指系统的逻辑组成，物理指系统具体实现的几何特征与物理特性。根 据抽象级别的不同，数字系统又划分为若干层次，一般从顶向下包括系统 级、行为功能级( 或称算法级) 、寄存器传输级( r t l ) 、逻辑级、电路级等 叼 。 表1 1数字系统设计的各个层次 抽象层次时序单元基本单元电路的功能( 行为) 描述 级数据处理进程及通信自然语言描述或者相互通信的进程 算法级运算步运算的控制行为有限状态机，数据流图，控制流图 寄存器传 时钟周期寄存器，运算，传输布尔方程，二元决策圈，有限状态机 输级 逻辑门级延时逻辑门，器件原理图 电路级物理时间晶体管r ，l ，c 等电压，电流的微分方程 物理( 版 几何图形 图) 级 设计描述的最低层为版图级。版图级用几何图形描述硬件，即用硅表 面上的扩散区、多晶硅和金属等来表示硬件。在这一层次，硬件的描述只 是结构，而硬件的功能则隐含在器件的物理方程中。 版图级层次之上是电路级。电路级用有源器件和无源器件的互连关系 描述硬件，基本单元可以为双极型晶体管、m o s 晶体管、电阻、电容等。 器件的互连关系描述了电路的结构，电压电流之间所满足的微分方程描述 了电路的功能。 电路级之上是逻辑门级，这是数字系统设计的主要层次。该级的基本 4 哈尔滨。i ：程人学硕十学位论文 单元是与门，或门，异或门，反向器等逻辑门，有时还有触发器，锁存器 等逻辑单元。基本的时序单元是延时，该层最典型的描述是原理图。为了 计算整个设计的性能，需要仿真工具，也需要时序分析工具。时钟周期通 常由两个存储器之间的最长路经确定，一条路径上可能包含多个非存储部 件。 逻辑门级之上的层次是寄存器传输级，该级的基本设计单元是寄存 器、汁数器、多路选择器、算术逻辑单元( a l u ) 等，这里的基本单元也 称功能块，该层的结构描述是基本单元的互连。在这一层上用于综合工具 的典型描述为布尔方程、有限状态机( f s m ) 和二元决策图( b d d ) 。这一 层的主要设计工作是优化、综合、状态编码以及工艺映射。这旱的主要优 化工作是减少完成运算所需要的时钟周期和逻辑门数。 r t l 级之上的层次是行为级，也称为算法级。在该层，设计由运算步 来描述。运算语句和控制语句被用来组织输入、输出以及不同运算。这一一 层次的电路描述通常是事件驱动的描述，一般由外部世界和内步运算之f h j 的交换数据的协议构成。运算步指的是两次相邻的输入、输出或同步点之 问的数据处理。一个运算步可能会占用多个时钟周期。这一层次的典型描 述是行为有限状态机( b f s m ) ，控制流图( c f g ) ，数据流图( d f ( ；) 和控制数 据流图( c d f g ) 。 层次化设计的最高层次是系统级。系统级的基本单元可以是计算机、 磁盘驱动器、总线接口等大的数字单元。 大部分的硬件描述语言，都允许在中间三个层次( 逻辑门级，r t l 级、 算法级) 描述电路。在每个层次相应于使用硬件描述语言的一个子集写出 系统的描述。当描述一个大型系统时通常将不同层次的描述方法混合使 用，很少单独采用某一层次的描述。一般情况下，完整的系统由多个模块 构成，每个模块分别在不同层次描述。 1 2 数字系统高层次设计自动化技术 数字系统的高层次设计自动化技术主要由硬件描述语言、高层次综合 技术、高层次模拟技术、高层次测试综合技术构成，每部分相互之阳j 既有 5 哈尔滨r 张人学硕+ 学位论文 分工，又密切相关互为配合，共同完成整个大规模复杂数字系统的设训 工作。 1 2 1 高级综合研究与动态 高级综合( 也称为高层次综和，行为综合) ，是实现从较高级别描述自 动综合到较低级别描述的数字系统自动设计技术，般是指从算法级的行 为描述到寄存器传输级r t l ( r e g i s t e rt r a n s f e rl e v e l ) 的结构描述， 是没计自动化中的关键技术“1 。高层次综合技术是高层次设计技术中的关 键，是近十多年来最为热门的自动设计技术之一。综合器可以把硬件的高 层次描述转化为低层次描述，也可以把同层次的行为描述转化为结构描 述。由综合器自动完成这种转换，类似于软件开发时利用编译器把高绂语 言写出的程序转换为可执行的机器码。 高级综合产生于6 0 年代，但真正得到发展是在近十几年，特别是8 0 年代以后，学术界和工业界开发了一些列的高级综合工具，比较有影响的 是法国的t i m a i n p g 实验室的a m i c a l ，荷兰艾因霍温工业大学的e s c a p e 等，最为成熟并且首先商业化的是美国的s y n o p s y s 公司的b c ( b e h a v i o r c o m p l i e r ) 1 。 9 9 年底，q u i c k t u r n 公司推出第五代的设计验证系统m e r c u r y ，为复 杂i c 设计提供了从概念到系统级集成的连续验证环境。该公司并与 s y n o p s y s 公司联合推出e i ) a 系统中领先的逻辑综合工具与硬件仿真工具 楣结合的片上系统( s y s t e mo nc h i p ) 的解决方案“1 。 在国内，也有不少大专院校和研究单位在数字系统的高层次设计技术 理论研究和应用开发方面做了大量工作，取得了较为丰硕的成果。其中以 北京理工大学刘明业教授为主的a s i c 研究所为代表，在高层次综合的理 沦研究和应用系统h l s b i t 的开发应用方面解决了一系列关键性技术问 题，取得了可喜的成果，达到了比较高的水平“1 。 哈尔滨t 程火学硕十学位论文 1 2 2 高层次模拟 在高层次设计中，高层次模拟是十分重要的一环，其目的是验证设计 的功能正确性，即能在设计中尽早尽快地发现错误。一般整个设计周期中 的每个阶段一系统规范说明、设计、细化、门级验证都是同等重要的”】。 但是一种模拟技术是适应不了几个阶段的模拟验证工作的。为此，一个性 能优良的高层次模拟系统应当是在一个独立的模拟环境中，能建立三种模 拟技术，即先进的解释型模拟，高速的编译型模拟，以及快速精确的门级 模拟。同时，三种模拟技术与相应层次的综合工具紧密地集成在一起，支 持整个设计流程，并能达到模拟的高精度和高速度，支持从行为级到门级 的各个层次和描述语言的系统模拟“1 。 在高层次模拟中，一般的过程为验证设计的高层次抽象描述、分析评 估系统的设计思想、选择最佳的体系结构、划分系统和细化、验证i j 综合 性和功能的正确性、精确的门级模拟。具体是以3 个阶段进行划分和实现： 第l 阶段设计的初始阶段。即行为描述的设计细化实现阶段，使j = f j 解释型模拟方式。该模拟器的主要功能是检查并迅速修正设计的设计思 想；评估和探寻各种不同的设计方案，进行比较并选择最佳的系统结构方 案，调整行为描述源码和规则的检查；灵活直观的设计信息和结果显示及 统计的功能，设计改变后快速返回功能等。 第2 阶段在概念设计验证之后，进入以寄存器传输级r t l 描述的设 计细化实现阶段，该阶段则使用编译型模拟方式，这种方式以验证一个完 整电路系统的全部功能为目的，采用详细的功能齐全的输入激励波形，用 尽可能多的模拟周期进行模拟，在进入综合前要进行设计描述的可综合性 检查和可测试性检查。提高模拟仿真的速度，以便进行大量的模拟，是这 一阶段模拟的关键之一。 第3 阶段在设计的最后实现门级电路阶段，则使用门级模拟进行验 证以确保最终设计的逻辑正确性和精确的时间正确性。这一阶段，模拟的 速度和精度是关键性的因素。 在3 个阶段的模拟中，前两者因设计是以v h d l 语言进行描述的，因 哈尔滨： ：程大学硕十学位论文 此有时也称为v h d l 模拟系统，即高层次模拟系统，其模拟的基本思想与 第3 阶段的逻辑模拟的思想类似，区别仅是模拟驱动是以进程为单位，而 其关键是如何解决好复杂功能器件的建模和如何提高模拟的速度。 1 2 3 测试综合 随着设计层次的提高，使得设计人员面对的电路规模越来越大，功能 越来越复杂，相应电路的测试也变得越来越困难。因而，在高层次设计中， 测试综合也同益受到重视，成为高层次设计中的一个重要组成部分。随着 逻辑综合技术的成熟，测试综合也相应得到发展。 所谓测试综合，就是在设计过程中，根据电路的有关持点，自动地插 入测试结构，然后对电路进行综合优化，产生电路实现，从而极大地提高 电路的可测试性。在设计过程中，同时考虑测试的设计问题，使综合、模 拟、测试能综合性地考虑，统一的去实旌，这就有效地缩短整个产品的开 发时间、减少返工，加速产品推向市场的时间，形成产品的完整测试线。 通常测试设计应包括可测性的分析检查、故障覆盖率情况的分析、全扫描 或部分扫描电路的插入，以及能在相应的测试部分进行时间驱动优化，从 而在设计过程中能尽快地提高可测试性，且对所设计的电路性能和区域 ( 面积) 影响员小。同时，把可测性的设计与a t p g 相结合，就能对全扫描或 部分扫描设计预测其故障覆盖的结果。 1 3 课题的提出 目前，数字系统设计面临着设计能力几乎没有改进而设计复杂度不断 提高的矛盾。显然，人们必须改进设计方法，才能在保证设计质量的前提 下提高设计能力，即提高集成电路设计的“生产率”。实现这一目标通常 有两条途径： 1 ) 采用高层次设计工具，使设计者可以在高层次丌始设汁。目酊，寄 存器传输层次的综合工具己经被设计者广泛接受，今后要采用更高层次的 行为综合工具( 高层次综合) 。 8 哈尔滨一程人学硕士学位论文 2 ) 更为结构化的设计方法学，使设计者可以大量重复使用前人过去设 计的部件。统计表明，新设计中通常会有7 0 是过去用过的部件，现在由 于实际方法不合适或者缺乏设计工具而不得不重新设计这些部件”。 1 3 1 高级综合特点 当生产工艺从微米、亚微米、深亚微米发展到超深亚微米时，这变 化对集成电路设计及其设计方法学提出了新的问题和挑战，它要求建立起 一个更为精确的深亚微米器件模型、时序模型和互联模型。在深皿微米级 电路设计中的一个突出矛盾是时序问题。此时互连线的延迟将超过门延 迟；而且出于集成电路工作频率的提高，允许的时序容差变小，传输延迟 的影相加大，这对电路设计带来了难度。最近，在布图的研究中，已经有 许多关于时延驱动布图算法的研究，一般都是在结构基本不动的前提下用 增加缓冲门或改变元件尺寸的方法，但是仅仅靠物理设计过程解决时延和 功耗的问题都有着很大的局限性。因此必须对原有的设计流程加以适当的 修改，其中一个关键的问题是如何在逻辑设计过程中引入物理设计阶段的 数据，如何把布局布线工具、寄生参数提取工具的时序分析统计工具集成 到高层次综合中去，来有效地解决互连线引起的问题，以达到事半功倍的 效果。特别是集成度越来越高后，个新的设计不可能完全从头丌始，它 往往要利用已有的、经过验证可以重用( r e u s e ) 的模块，包括从他人处获 得的知识产权( i r i t e l l i g e n tp r o p r i e t a r y ，i p ) 模块，再加上部分新设计 的模块，形成一个具有特色的新设计。 高级综合算法级描述的内容为高层次电路行为，不涉及底层元件，1 i 区分数据处理( 组合逻辑) 与数据寄存( 时序逻辑) ，因此适合解决以上提出 的设计能力和设计复杂度的问题，其特征如下： 1 ) 设计划分为一些较大的块，每一个块代表一个功能，完成这一功能 需要多个时钟周期； 2 ) 在较高的抽象层次进行设计，使用的是抽象数据类型、循环控制结 构以及算法等； 3 ) 设计中需要在合适的地方插入r e s e t 、自定义的约束以及一些时 9 ：立a j 鎏土量盔耋堡土芝童：鲨塞 钟跳变沿。 1 3 2 高层次设计自动化特点 v h d l 硬件描述语言、高层次综合技术、高层次模拟技术、高层次测 试综合技术，构成了整个高层次设计的自动化技术的内容。每部分相互之 间既有分工，又密切相关。互为配合，同完成整个大规模复杂数字系统的 设计工作。在设计中采用了高层次设计自动化技术以后，结整个产品的设 计带束了如下的结果。 1 ) 提高了设计速度、缩短了产品开发周期。 出于高层次设计的描述采用行为级描述语言，这种语言易于描述，且 简练，一般行为级h d l 大约仅为相同功能寄存器传输缴h d l 代码的十分之 一。这可明显地提高设计速度，缩短设计周期，并实现了非集成电路专家 可直接参与从行为描述到芯片的设计工作，从而可以使更多的人同时进行 设计，加速了整体的设计进程。 2 ) 有效保证了设计质量、降低了成本。 高层次设计中行为描述通常要比低层次的结构描述简洁而又易于编 写和理解，这就相应的降低了设计的复杂性，减少了描述错误，且容易发 现和修改。另外，由于描述层次的提高而大大缩短了仿真时间，并使设计 中出现的问题能在早期得到发现，降低整体设计的成本。 3 ) 优化产品设计方案。 基于行为级的设计可以优化设计的体系结构。可寻求最优或满意的设 计方案，可快速评估多种结构削的性能价格比。 4 ) 与工艺无关，提高了设计的再利用性。 在高层次设计中，由于v h d l 语言具有与工艺无关的特性，因而在行 为和结构级就不用去关心与工艺相关的细节。这就为设计的再利用性提供 了条件，也为今后更快设计出新产品创造了条件，即一旦半导体厂商工艺 改变，只需用厂商的新库重新综合即可。 5 ) 大大提高了设计的可交流性。 在高层次设计中，用户一般以v h d l 语言描述作为设计的规范说明和 1 0 哈尔滨一程大学硕十学位论文 需求说明，在经高层次综合、用户修改、验证以后，仍可将结果转换为 v h d l 语言的描述，从而可以实现设计过程的自动文档化。 6 ) 提高了产品的可测试性。 通过高层次设计的产品，可降低设计的复杂性的可测试性和故障覆盖 率。 进入二十一世纪，i c 设计业已经进入片上系统( s o c ) 时代。为了适 应科技发展和市场竞争的需要，系统设计者不断寻求更短的上市时i 到，更 高的性能和更低的成本，所有这些都是推动i c 设汁业飞速发展的直接动 力。高级综合的如上优点使得其成为解决电路设计所面临问题的有力工具 之一，有着广阔的发展空间和应用前景。然而高级综合没有象逻辑综合那 样成熟，使用的效率和设计者的接受程度远远低于逻辑综合，因此有必要 对其进行改进、优化，使其综合效率更高，产生更好的寄存器传输级代码。 1 4 本文的主要工作 本文首先研究了高级综合的一些算法，对其解决高级综合问题的方式 进行研究，这些解决方式主要分为两类，一种是提出新的高级综合方法， 为一整套的解决方法，包括调度、分配等子任务的解决，有的还提出了新 的内部表示模型，从内部表示到最终目标代码生成都采用自己的方式。另 一种是解决了高级综合的某个子任务的优化，如解决调度、分配过程中寄 存器分配等。很多算法都是针对高级综合两个子任务调度和分配展丌的， 这些算法在某些优化目标中起到了很理想的效果。 在此基础上，我们以控制为主要部分的电路为例，说明了高级综合结 果优化的必要性，并针对这种电路的特点，提出了一种针对控制为主要部 分的电路高级综合优化策略，该策略采用控制流图为中阳j 表示结构，在高 级综合中采用推测技术，使用动态环调度技术完成整个综合的过程。这是 一种单目标的高级综合优化策略，也就是现在该领域研究的热门，即专剧 高级综合系统。一般来说专用高级综合系统在某些应用领域的效率要比 般通用的高级综合效率要高，但是适用面窄，通用性不强。 专用综合系统可配置性有限，因为其内部表示模型、调度方法、分配 1 1 哈尔滨i ：程火学硕： 学位论文 方法，以及控制器的生成都是针对具体类型电路特点而定做的。为此，本 文提出了多目标高级综合优化策略，该方法类似于一个软件组件，可以配 合其他高级综合工具使用，其主要思想就是对系统进行划分，使划分后得 到的子系统间连结费用最小，然后对各个子系统进行调度，分配，该优化 策略用在调度、分配之前。多目标优化策略体现在将系统转化为图的过程 中，本文的策略允许设计者自己引入设计意图和设计约束，并能灵活的体 现这些条件的彼此轻重关系。对系统的划分最终转化为图的划分，本文应 用模拟退火算法对图进行化分，取得了比较满意的效果。 在将高级综合的描述转换为图的过程中，本文使用了基于p e t r i 网的 内部表示模型，这种表示模型既有表示控制流图的部分，也有表示数据流 图的部分。这种内部表示模型有描述能力强、通用性好等突出优点，也容 易基于此模型对系统性能进行仿真和模拟。 最后本文详细说明了实现的过程，包括一些实验数据和一些采用的数 据结构，指出了一些还需要解决的问题。 本文第一章主要介绍了数字系统设计的发展历史和数字系统设计的 层次性，介绍了数字系统高层次设计的高层次综合、高层次模拟和高层次 测试综合技术以及高层次设计自动化技术的优越性。第二章详细介绍了数 字系统的高级综合的输入、内部表示模型、目标结构以及高级综合的流程 和采用的技术，重点介绍了高级综合的两个重要步骤，调度和分配，分析 了各种算法和策略。第三章说明了对高级综合结果进行优化和应用专门知 识的必要性，以控制为主要部分的电路为例，提出了针对这种电路特点的 高级综合方法。第四章详细说明了我们的多目标高级综合优化策略，以及 其中的一些算法、理论，重点阐明了我们的实现方法。第五章给出了详细 的软件实现方法、数据结构和程序主要模块的说明和今后要做的工作。 第2 章高层次综合概述 所谓高层次综合是指从算法级的行为描述到实现它的寄存器传输级 结构描述的转换。其重要任务是能从多种给定行为功能的硬件结构中找出 一种既满足约束条件和目标集合，又花费最少的硬件结构。高层次综合在 行为功能描述与其硬件结构实现之问架起一座桥梁，自动生成可以逻辑综 合的电路描述。高层次综合优化中要同时考虑电路结构、存储结构、互连 结构以及时序的设计等诸多因素。 2 1高层次综合基本任务和功能 数字系统的高层综合是在数字系统的算法行为确定之后，山一种抽象 的行为描述出发，寻求实现算法功能的最优寄存器传输级结构，目的是在 满足处理性能的前提条件下，使硬件开销极小。数字系统所要求的行为规 范、约束集和目标构成了高层综合系统的输入”1 。 数字系统的硬件结构包括数据通道和控制器两大部分，因此，数字系 统的高层综合分为数据通道综合和控制器综合。数据路径指的是从基于行 为描述的算法层综合，得到一个优化的寄存器传输级结构，主要包含四个 任务： 1 ) 使用一种硬件描述语言( h d l ) 来描述数字系统的行为，并将这种行 为描述变换到一种基于图的表示方式，通常为数据流图( d f g ) 或控制数据 流图( c d f g ) ，以此作为高层综合的基本数据结构。流图中的节点代表数据 操作，节点之间的有向弧表示数据相关关系或控制相关关系，它定义了数 据操作执行的先后顺序。 2 ) 时序调度( s c h e d u l i n g ) ，亦称为调度操作，即把流图中的数据操作 节点在遵守顺序约束的条件下，安排到恰当的控制步中，时序调度完成后 得到定时效据流图( s d f g ) 。时序调度一方面利用算法中的并行性，使一一个 控制步可以同时执行多个数据操作，满足处理速度的要求，另一方面又要 哈尔滨一：程大学硕十学位论文 合理控制各个控制步中的并行度，以减少硬件- 丌销。时序调度决定了数字 系统的处理速度和硬件代价之间的折衷，成为高层综合过程中最重要的环 节。 3 ) 资源分配( a l l o c a t i o n ) ，即为数字系统分配资源，具体而言，为数 据操作分配物理运算单元，为数据变量分配物理寄存器，为数据传输分配 总线和多路选择器。资源分配的目标是使所得的硬件数量最少，因此，不 并行的同类数据操作是相容的，可以复用同一运算单元，生命周期不重量 的变量可以占据同一物理寄存器，发生在不同时刻的数据传输可以共享同 一数据总线。根据这些相容关系合理分配硬件资源，将会导致数据通道的 简化。 4 ) 经过时序调度和资源分配综合得到个数据通道之后，可以根据数 据通道在各个控制步所需要的控制信号来产生一个状态图，然后由此状态 图产生控制器。这个控制器通常是微指令的或是一个基于p l a 的有限状态 机( f s m ) 。微指令方法灵活，译码电路简单，宜于实现复杂的控制。但在 算法十分规则、控制机理简单的时候，f s m 方法则显得更为可取。 高层综合的四个任务相互依赖、相互影响。行为描述恰当地表达算法 中的并行性以及层次化结构，将有利于后继综合过程。对于时序调度和资 源分配，方面为了确定两个操作是否能被调度到同一个控制步中执行， 也要知道它们是否使用了同一个硬件资源。进一步，为实际硬件寻找最有 效的时序调度，要求知道不同操作之间的延迟，而这些延迟只能在功能单 元和它们的互连细节被知道之后才能被掌握。另一方面，为了确定应该使 用多少个功能单元以及在这些功能单元中应该怎样安排各个操作，就必须 知道哪些操作将被并行执行，而这又来自于时序调度。至于控制器，尽管 结构比较规范，设计相对简单，但它的最佳结构和复杂程度仍取决于综合 得到的数据通道。由此可见，整个高层综合过程存在着一个因果循环。特 别考虑到时序调度和资源分配为最重要的两个优化过程，依赖关系更加密 切，因此高层综合系统应该同时执行它们。然而由于实际运作的复杂性， 许多高层综合系统独立地执行它们或通过对这两个任务的反复交替循环 来执行。 一般，新一代的高层次综合系统应具有以下基本功能： 1 4 哈尔滨l 程人学硕十学位论文 i _ i _ _ _ - i j j | i i _ _ i i ；j i i i i _ 目| i i - _ _ ii 可以完成硬件描述语言( 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 ，h d l ) ， 比如超高速集成电路硬件描述语言( v h s i ch a r d w a r ed e s c r i p t i o n l a n g u a g e ，v h d l ) 或v e r i l o gh d l 设计的转化和结构优化，通过局部和少 量的修改，就能构造出多种方案，能快速进行比较和选择，使在总体结构 和框架上能获得最优方案。 主要的优化功能应包括资源共享、优质元件的选择、元件参数化、 时间驱动的计算优化等。 能支持层次化的设计和行为、r t l 和结构编码等的混合类型设计。 能由行为综合转化成r t l 级综合，直至门级实现，以验证功能、评 估性能、完成不同结构的取舍等，使系统的评估和系统的设计合成在+ 起。 能使行为级的描述，通过综合优化，按所使用的a s i c 厂家库的关 键部位，快速生成参考电路，计算出性能、面积、功耗等，以便进行比较、 取舍，来决定最终的设计。 2 。2 高级综合的输入 高层次综合的输入包括行为级描述、设计约束、高层次元件库和工艺 库四种。行为级描述通常是行为级的h d l 描述。综合工具从h d l 源码提取 出i 0 端口的标准规范( 输入输出时序) 、操作和数据流、控制流和存储 器件需求等相关信息，并生成设计描述的中间表示格式( 通常为控制数掘 流图) 作为后续综合步骤的输入。设计约束主要包括时钟周期、操作步数 ( 周期数) 、设计吞吐量、硬件资源的最大数目、面积、最大功耗等。高 层次元件库主要包括加法器、乘法器、存储器、流水线部件，也可能包括 有关硬件实现的信息和设计中如何使用元件的规范。工艺库提供设了计面 积和时间是否满足约束的基本信息。行为级描述一般采用标准的硬件描述 语言v h d l ，v e r i l o g 等，这种行为级描述简单，代码少，容易发现设计中 的错误。 哈尔滨一程大学硕士学位论文 2 3 高级综合的中间结构 行为级描述的代码被高级综合器读入后，要转换为一定的内部表示模 型，即某种严格定义的中间格式，通常称为高级综合的设计表示。整个高 级综合的过程就是对内部设计表示的连续转换过程。对于硬件设计师来 说，综合器内部的设计表示是不可见的。 面向语言的表示形式分为三类：数据流图、控制流图和控制数据流图。 2 3 1 数据流图 这是程序设计中常用的中间格式。在此图中，节点代表程序中的操作， 有向线代表数据。节点的作用是根据输入数据产生新的数据，有向线的箭 头表示数据流动方向。 a 图2 1 数据流图 数掘流图是程序中表示表达式的理想形式，但是在表示控制结构上能 力有限。 哈尔滨哪鼙人学硕士学位论文 2 3 2 控制流图 控制流图适合表示各种控制结构，如条件循环、条件转移、子程序调 用以及意外情况处理等。控制流图也由节点和有向线组成。但是，节点分 为操作节点和分支节点两类，操作节点类似于数据流图，但意义更加广。泛， 可以是赋值、算术逻辑运算和子程序调用等，分支节点表示各种控制结构， 对应到v h d l 中，就是i f ，c a s e ，w h i l e 等语句；控制流图的有向线不表 示数据，而是表示节点之间的依赖关系。控制流图非常适合于表示各种控 制结构，但在数据流的分析和变换上能力有限。 图2 2 控制流图 2 3 3 控制数据流图 控制数据流图在数据流图基础上增加了控制节点形成，综合了控制流 哈尔滨r 释人学硕十学位论文 i i i i i ；i ；_ _ _ j e i i i i i _ _ 日_ i _ _ _ _ 一i q i 自i i 自；目i j i j j 图和数据流图的特点，是当| i 高级综合工具中最常用的设计表示形式。在 此图中，节点表示数据操作和控制结构，有向线表示节点之间的相关性。 不同的高级综合工具中，c d f g 在具体格式上变化很大。c d f g 中的有向线 分为两类：数据线和相关性线。前者表示各种数据，后者表示节点问的顺 序和控制关系。 2 4 高级综合的目标结构 高级综合器接受输入行为级描述后，将其转化为内部设计表示，然后 经过调度i 分配等步骤，形成最后的寄存器传输级代码作为输出。不管输 入的行为描述如何改变，而输出的寄存器传输级代码必须依据定的通用 模型来建立。这个通用模型被称为行为综合的目标结构，由控制单元、运 算单元组成。其中的控制单元一般是一个有限状态机，运算单元可以是数 据路径或协处理器。 通用模型常用的是带有数据路径的有限状态机( f s m d ，f s mw 1 1 h d a t a p a t h ) 与带有数据路径和协处理器的有限状念机( f s m c ，f s m dw i t h c o p r o c e s s o r ) 。 2 4 1f s m d 模型 f s m d 模型由g a j s k i 等在1 9 9 2 年提出，是一种可以代表全部硬件设 计的通用模型，f s m d 是在f s m 基础上增加了数据操作能力，其定义为i 元组 。其中： s ：指的是f s m d 中f s m 的状念集合； i * s s ：f s m 的输入集合i ，被数据路径输出的条件信号扩展； o * a ：f s m 对外界的输出集合0 ，并被内部变量赋值集合aj ) 。展： f ：f 一状态的生成函数，