（计算机应用技术专业论文）基于时序驱动的综合技术研究.pdf

摘要 随着超大规模集成电路工艺的发展，电路规模越来越大，电路设计 的复杂度越来越大，这对于电子设计自动化提出了严峻的挑战。高级 综合工具可以在很大的设计空间中选择最优的设计方案。利用综合手 段，至少可以得到如下收益： ( 1 ) 缩短设计周期，降低设计成本。 ( 2 ) 减少设计错误。采用经过验证的自动综合工具，可以消除大部 分可能由人工带来的设计错误。 ( 3 ) 可以在多个设计方案中进行比较。 ( 4 ) 容易适应性能指标的部分改变。 特征尺寸进入0 3 5um 后，互连线延迟占到系统延迟的7 0 以上， 而延迟参数的分布又取决于版图的具体实现，导致时序收敛成为设计 的首要问题，因此综合技术必须要基于时序，保证时序收敛。 论文的重点是： ( 1 ) 不同加工工艺下综合手段的实现； ( 2 ) 基于时序驱动的综合手段的探索； ( 3 ) 静态时序分析的实现。 本文的研究成果己成功应用在8 位r i s cm c u 的设计上。 关键词：超大规模集成电路，电子设计自动化，综合，时序驱动，静 态时序分析 a b s t r a c t w i t ht h ed e v e l o p m e n to fv 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 ，c i r c u i t s c a l ei sm o r ea n dm o r el a r g e ，c o m p l e x i t yi sm o r ea n dm o r es e r i o u s ，w h i c h h a sb e c o m eah u g ec h a l l e n g et oe l e c t r o n i cd e s i g na u t o m a t i o n h i g hl e v e l s y n t h e s i st o o lc a nc h o o s eb e s ts c h e m ei nal a r g ed e s i g ns p a c e b e n e f i t so f s y n t h e s i st e c h n o l o g yi n c l u d e ： ( 1 ) i tc a ns h o r t e nd e s i g nc y c l ea n dr e d u c ed e s i g nc o s t ( 2 ) i tc a nr e d u c ee r r o r a u t o m a t i cs y n t h e s i st o o la f t e rv a l i d a t i o nc a n e l i m i n a t ee r r o rb e c a u s eo fm a n u a lw o r k ( 3 ) i tc a nc h o o s ea m o n gs e v e r a ls c h e m e s ( 4 ) i ti sa d a p t i v et oc h a n g eo fp e r f o r m a n c es p e c i f i c a t i o n w h e nf e a t u r es i z ec o m e st o0 3 5l a m ，i n t e r c o n n e c td e l a y h a s c o n t r i b u t e d7 0 t ot o t a ld e l a y d i s t r i b u t i o no fd e l a yp a r a m e t e r sl i eso n a c t u a l i m p l e m e n t a t i o no fl a y o u t ，w h i c h r e s u l t si nt h ef a c t t h a t t i m i n g c l o s u r eh a sb e c o m et h ec h i e fp r o b l e m s os y n t h e s i s t e c h n o l o g ym u s tb e b a s e do nt i m i n gt oi n s u r et i m i n gc l o s u r e t h i sp a p e rp u te m p h a s iso n ： ( 1 ) i m p l e m e n t a t i o no fs y n t h e s i su n d e rd i f f e r e n tp r o c e s s ( 2 ) e x p l o r et i m i n g - d r i v e n - b a s e ds y n t h e s i sm e t h o d ( 3 ) i m p l e m e n t a t i o no fs t a t i ct i m i n ga n a l y s i s t h er e 3 u l t so fr e s e a r c hh a v eb e e ns u c c e s s f u l l ya p p l i e dt ot h ed e s i g n o f8 一b i tr i s cm c ij k e yw o r d s ：v e r yl a r g e s c a l e i n t e g r a t e d a u t o m a t i o n ，s y n t h e s i s ，t i m i n g a n a l y s i s ， i i c i r c u i t ，e l e c t r o n i c d r i v e n ，s t a t i c d e s i g n t i m i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒胆王些盍堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字名袭缸哙签字日期6 2 印中年弓月髫日 | 学位论文版权使用授权书 本学位论文作者完全了解垒g b 王些盔堂有关保留、使用学位论文的规定有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 胆王些塞堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 。 学位论文者签名：数 、 导师签名 为明侄 签字日期垆；月，髫日 签字日期；- 钟多月t7 学位论文作者毕业后去向 工作单位： 通讯地址： 电话 邮编 零 致谢 本论文是在导师蒋建国、高明伦教授的悉心指导下完成的。蒋老 师和高老师不仅学识渊博、治学严谨，而且诚恳待人、诲人不倦。蒋 老师和高老师对科学的认真态度和崇高的品德是我永远学习的楷模， 并将使我终身受益。衷心感谢导师的培养、支持和教诲! 感谢王锐老师在工作、学习和生活上给予的指导，使得论文能够 顺利完成。 感谢合肥工大微电子设计研究所胡永华老师、许晓琳老师、邓红 辉老师、徐诺老师、林微和杜艳英的热情支持。 感谢h g d 0 8 r 0 1 项目组杜高明、蔡金青、何伟、齐海鹏、何叶东、 马友花、刘晓稳，感谢他们对我工作的关心和支持。 感谢微电子设计研究所所有同仁陪我度过三年美好时光。 感谢我的父母多年来的培养、帮助、关心和支持。 感谢安徽大学张有洁同学给予我学业上支持、生活上关心以及方 方面面的理解。 感谢文中引用过文献的所有作者们，感谢所有关心、支持和帮助 过我的老师、同学和朋友们1 1 1 1 黄正峰 2 0 0 4 年3 月于工大微电子所 第一章绪论 在全球经济低迷的今天，中国经济的飞速发展可谓是“一枝独秀”， 而在中国经济中，集成电路产业恰恰是“领头羊”。据信息产业部统计， 中国电子信息产业2 0 0 2 年达到1 4 万亿人民币的销售规模，成为继美 国、日本之后的世界第3 大i t 产品生产国。目前国内集成电路( 以下 简称i c ) 产业正以年均3 0 的速度增长，2 0 0 2 年中国集成电路市场规 模较上年增长2 9 ，其中国内i c 设计业产值1 5 亿元人民币，比上年增 长3 6 。超大规模集成电路及其相关技术是现代微电子信息技术飞速 发展的关键性技术，具有广泛影响和深远作用。微电子技术是电子信 息产业的基础和心脏，而集成电路是微电子技术的核心。努力发展我 国的集成电路产业将对经济建设、科技工程进步以及国肪现代化建设 起着巨大的推动作用。可以说，集成电路产业是我国经济飞速发展的 一个强有力的支点。 当今微电子工业的产值占世界经济总产值的4 ，成为世界第一大 产业。预测显示，今后2 5 年内，微电子产业更将占到世界总产值的 8 t 引。可以说，微电子科学技术是2 1 世纪上半叶科学技术竞争的焦点， 谁掌握了微电子技术，谁就掌握了主动权，微电子产业的规模和技术 水平成为衡量一个国家综合国力的主要标志。 1 1 微电子技术的发展趋势和现状 1 1 1 徽电子技术的发展趋势 1 9 4 7 年，巴丁发明了世界上第一只晶体管：1 9 5 8 年，采用硅平面 工艺的集成电路诞生；1 9 7 1 年，微处理器出现；这些事件都标志着微 电子学的飞速发展。 著名的摩尔( m o o r e ) 定律指出：集成电路每隔3 年集成度增加4 倍，特征尺寸缩小2 倍1 3 】。直到现在，摩尔定律仍然指导着微电子产业 的发展。表1 1 给出了19 9 7 2 0 0 9 年国际集成电路制造工艺的发展现状 和发展趋势 4 1 ”1 。 表卜1 1 9 9 7 2 0 0 9 年国际集成电路制造工艺的发展现状和发展趋势 年度1 9 9 71 9 9 92 0 0 12 0 0 32 0 0 62 0 0 9 线宽( um )0 2 50 180 15o 1 3o 1 00 0 7 晶体管数目( m )1 1 2 14 07 62 0 06 2 0 面积( m m 2 )3 0 03 4 03 8 54 3 05 2 06 2 0 主时钟频率( m h z )7 5 01 2 0 01 4 0 01 6 0 02 0 0 02 5 0 0 金属层数 66 7777 - 8 l 8 9 而目前绝大多数的整机系统都是通过印刷电路板( p c b ) 将各个芯 片连接起来组成的，虽然芯片本身功耗小，速度快，但印刷电路板带 来的连线延迟和噪声却大大降低了系统性能，成为系统发展的瓶颈。 在这样的技术推动与需求牵引下就出现了系统芯片( s o c ，s y s t e mo n c h i p ) 。系统芯片通常是指将多个独立的v l s 设计拼合在一起，完成 某一应用所需全部功能的集成电路。系统芯片应包含两个基本的部分： 硬件部分，包括p 、b u s 、r o m r a m 、i op o r t 等计算机的基本 部件： 软件部分，主要指操作系统，也可以包括重要的应用软件。 和在印刷电路板上实现的板级系统相比，系统芯片在性能方面有 着无法比拟的优势： 模拟电路i p 的使用可以减小噪声对于系统中模拟模块的影响； 输出缓冲器使用数量的减少可以降低功耗： d r a m 和c p u 之间的速度大大提高。 s o c 与由i c 组成的板级系统相比，由于s o c 能够全盘考虑整个 系统的各种情况，可以在同样的工艺技术条件下实现更高性能的系统 指标。另外，从产品的开发角度来讲，可以极大地降低整个系统的开 发费用，尤其对于消费类电子产品而言，系统芯片的开发可以大大地 缩短产品的面市时间( t i m e t o m a r k e t ) 。可以说，系统芯片无论在设 计思想还是设计方法上，都将是微电子设计领域乃至整个信息产业的 一场革命。 1 1 2 微电子技术的现状 近年来，我国逐步加大对微电子产业的投入，颁布了一系列优惠 政策，自主培养并从国外吸纳了一大批微电子技术的人才，取得了一 系列的科研成果并且成功地产业化： 中科院计算所设计的“龙芯”系列通用微处理器，标志着我国在现 代通用微处理器设计方面实现了“零”的突破，打破了我国长期依 赖国外c p u 的无“芯”历史，也标志着国产安全服务器c p u 和通用 的嵌入式微处理器产业化的开始； 上海交通大学微电子学院研制的“汉芯”d s p ，是中国自主知识产 权的第一款高性能d s p 处理器，可以在2 0 0 m h z 的工作频率下每秒 钟运行2 亿条指令； 苏州国芯科技有限公司的低功耗3 2 位嵌入式精简指令c , c o r e 技 术； 火马微电子推出的e v d 标准； 大唐移动和国外厂商联合开发的t d c d m a 芯片； 中星微电子的音视频处理芯片组等 以上数据都是中国i c 设计水平突飞猛进的体现”“。 1 2 课题来源以及研究目的和意义 本文的研究内容来源于： 。 国家信息产业部“嵌入式微处理器开发及产业化”项目( 信运 部 2 0 0 1 9 0 0 号) ； 中小企业创新基金项目( 立项代码0 2 c 2 6 2 1 3 4 0 0 2 0 8受理码 2 0 0 2 3 4 0 1 0 6 0 0 5 1 ) ： 本文研究的目的在于： 研究基于时序驱动的综合技术： 现有的综合技术，在不同工艺水平下的应用和实现 提升我国i c 设计中综合技术的能力； 一 本文研究的意义在于： 随着超大规模集成电路( v l s i ) 工艺的发展，电路规模越来越大， 电路设计的复杂度越来越大，这对于电子设计自动化( e d a ) 是严峻的 挑战。传统的逻辑设计方法已越来越不能适应设计的要求，而逐步代 之以高层次的自动设计方法，综合技术就是其中突出的代表。综合工 具可以在很大的设计空间中选择最优的设计方案。利用综合手段，至 少可以得到如下收益： ( 1 ) 缩短设计周期，降低设计成本。设计者只在高层次设计电路， 可以不对工艺本身作详细了解，从高层次向低层次的转换，由自动综 合工具完成，加快了设计速度，缩短了设计周期，提高了产品的竞争 力。 ( 2 ) 减少设计错误。对于大系统设计，随着设计复杂性的提高，人 工设计出现错误的可能性急剧增加。采用经过验证的自动综合工具， 可以消除大部分可能由人工带来的设计错误。 ( 3 ) 可以在多个设计方案中进行比较。传统的人工设计，每完成一 个设计方案都要花费很大的代价，而采用自动综合技术可以迅速得到 多个满足性能指标要求的设计方案，因此可以对比不同的设计方案的 优劣。 ( 4 ) 容易适应性能指标的部分改变。采用自动综合工具，硬件的行 为模型较容易修正，面从行为模型到寄存器以下的层次，都是自动产 生，因此较容易针对修改后的性能指标重新开始设计“。 当特征尺寸大于o 6 弘m 时，设计中的延迟主要由门级单元的延迟 引起。当特征尺寸越来越小时，在器件结构、关键工艺、集成技术等诸 多方面，将会遇到很多未知的问题“”3 。例如，当特征尺寸在0 3 5 um 时，互连线延迟在系统延迟中占据了主导地位，大概占到系统延迟 的7 0 以上“，而延迟参数的分布又取决于版图的具体实现，导致时 序是否收敛成为设计的首要问题。此外，特征尺寸变小后，互连线的 宽度交细，会引起一些新的物理效应，间接地影响时序： 电流密度迅速增大，导致电子迁徙和热载流子效应； 设计频率提高，连线间距变小，串扰和噪声效应对时序的影响加剧； 小的连线尺寸导致单位长度上的电阻提高，给时钟同步带来很大的 困难。 因此综合技术必须要基于时序，保证时序收敛。 本项目以现有的综合设计方法为切入点，以时序收敛为驱动，探 讨切实可行的、时序收敛的综合设计手段，力图提升我国i c 设计中综 合技术的能力。 1 3 主要研究内容和章节安排 本课题是针对不同工艺下基于时序驱动的综合技术的研究，并在此 基础上完成在v l s i 设计中的实际应用。本论文的研究内容，包括如下 几个方面： ( 1 ) 不同加工工艺下综合手段的实现，将在0 1 8um ，0 ，2 5u1 1 1 ，0 3 5 pn l 三种不同的加工工艺下运用综合技术； ( 2 ) 基于时序驱动的综合手段的探索，探索对于不同的模块采用不 同的综合手段，例如时钟发生模块的综合就较为别具一格； ( 3 ) 静态时序分析的实现。使用静态时序分析理论和相关e d a 工具， 对设计进行时序分析。 4 本文第一章介绍了综合技术的现状和发展趋势。第二章介绍了综 合的相关概念和知识背景，阐述了综合的定义、基本概念和实现原理 第三章介绍了静态时序分析的相关概念和知识背景，重点在于特殊时 序路径的分析和全芯片的静态时序分析。第四章叙述了时序驱动的综 合策略和手段的选择，针对不同的模块，诸如时钟发生模块、状态机 模块、数据路径模块以及全芯片，采用了迥然不同的综合策略和手段。 第五章描述了不同加工工艺时综合手段的实现，分别在0 3 5 um 、o 2 5 um 、0 18um 三种不同加工工艺下实现综合。第六章总结了论文的主 要工作和成果，对综合技术的发展趋势做了进一步的展望，并对基于 论文的工作的进一步开展做了展望。 第二章综合的相关概念和知识背景 超大规模集成电路( v l s i ) 可以划分为通用集成电路和专用集成 电路。存储器等大量生产且设计规则的集成电路称为通用集成电路， 面向某一应用背景而专门设计的集成电路称为专用集成电路( a s i c ) 。 目前，专用集成电路面临着设计能力几乎没有改进而设计复杂度却不 断提高的矛盾。统计表明，对于一个规模较大的专用集成电路设计， 通常由1 0 15 人在18 个月的时间内完成，每个设计者平均设计能力为 每天十几个器件1 。与此同时，专用集成电路的设计复杂度却在成指 数增加，1 9 8 4 年专用集成电路的设计规模在几十万个晶体管，2 0 0 0 年 专用集成电路的设计规模在1 0 0 0 万个晶体管，预计2 0 1 0 年要求的设 计规模将达到5 0 0 0 万个晶体管。这就意味着，到2 0 1 0 年，设计能力 和设计需求之间的巨大矛盾将会无法解决。因此，必须改进设计方法， 在保证设计质量的前提下提高设计能力，提高专用集成电路的“生产 率”。实现这一目标的有效途径就是：综合。 2 1 综台的定义和基本概念 综合来源于英文单词s y n t h e s is ，其基本含义是把一些抽象的对象 组合为一个统一的整体。在集成电路设计中，综合有着特殊的含义。 其定义是：“集成电路设计过程中设计描述从一种形式向另外一种形式 的( 自动) 变换过程。” 综合工具用于硬件设计过程中的自动设计或帮助设计者进行设 计。根据上述关于综合的定义，可以将集成电路设计中的综合器定义 为“把硬件设计的一种描述形式向另一种描述形式进行自动转换或者 帮助硬件设计者进行这种自动转换的软件工具”。综合器可以把硬件的 高层次描述转换为低层次描述，也可以把同层次的行为描述转换为结 构描述。综合器自动完成这种转换，和软件开发时利用编译器把高级 语言写出的程序转换为可执行机器码相类似。例如，c 语言编译器可 以把特定算法的c 语言描述转换为机器代码( 二进制代码) 描述，在 特定的计算机上，这种二进制代码可以执行。和它类似，综合器可以 把硬件的高层次描述( 算法级描述) 转化为中间层次的描述( 逻辑门 级描述) ，也可以利用称为硅编译器的版图级编译器，把中间层次的描 述转化为最低层次的描述( 几何版图描述) ，这种最低层次的描述可以 用某种集成电路制造工艺来实现硬件。图2 1 给出了软件编译和硬件综 合的类比。图2 1 中，在高层次采用硬件描述语言来描述电路对应于软 件设计中使用高级程序设计语言编写软件；高层次综合器对应于软件 设计中的高级语言编译器；高层次综合器产生的逻辑门或者电路层次 的设计描述对应于软件设计中的微码程序；逻辑门或者电路层次描述 经版图综合得到可制造的集成电路掩膜数据对应于软件设计中的微码 程序编译得到的二进制代码。 c 语言编译器 i 算法的微 t 微码编译器 l 高层次综合器 l 硬件雕 i 版图综合器 高层次描述 逻辑级晶体管级描述 几何版图描述 ( 在特定计算机上可以执行) ( 在特定工艺下可以制造) 程序设计硬件设计 图2 1软件的编译和硬件的综合 和软件程序设计相似，集成电路硬件设计时，利用综合工具从高 层次向低层次自动转换和直接在低层次设计硬件相比各有优缺点。对 于大型软件设计，直接采用微码设计软件几乎是不可能的，必须采用 高级语言设计系统。用高级语言设计程序，设计者的精力可以集中在 算法的实现上，而不必考虑计算机系统中寄存器的使用、物理内存的 分配等细节问题，可以节省时间，减少设计错误。然而，由于高级语 言编译器必须考虑从高级语言向低级语言转换时的各种情况，对于某 些具体问题，编译得出的机器码可能不是最优的。即使是带有优化功 能的编译器，也只能进行某些特定类型的优化，永远也不可能考虑到 所有可优化的情况。一般地讲，有经验的程序员直接在中间层次( 逻 辑门或者晶体管级) 设计的硬件质量要比综合器产生的好。 从硬件描述的一种形式向另一种形式自动转换的过程由两部分组 成：第一步是翻译，第二步是优化。综合器永远也不可能找出硬件设 计的全部可能实现方式，从而不可能得出最优方案。在大多数情况下， 设计方案是否最优并不重要，而面市时间、设计成本和设计可靠性是 优先权最高的考虑因素。当然，如果有可能，对自动综合产生的电路 进行人工修改，可能得到更优的设计方案。 对于软件设计，如果用微码写应用程序，要求程序员有很好的编 程功底，程序设计所花费的代价较大，程序调试的时间很漫长，程序 员也会很痛苦。同样，在较低层次设计硬件，也要求硬件设计者有丰 富的设计经验，硬件设计成本较高。硬件的预期生产量在一定程度上 影响了硬件的设计方法。对于生产量较小的集成电路，应该在较高的 层次进行设计，从高层次向低层次的转化，由综合器完成，目的是降 低设计成本。对于生产量较大的集成电路，应该在较低的层次进行设 计，目的是降低生产成本和提高电路性能，而在设计上所花费的代价 可以通过批量生产时降低的生产成本来抵消。 在不同层次设计集成电路可以使用不同的综合器。对于综合器来 讲，输入描述为系统级、算法级、寄存器传输级等逻辑门级以上描述 的综合器称为高层次综合器。输入描述为逻辑门级、晶体管级硬件描 述的综合器称为低层次综合器。对于高层次综合器，通常在综合器的 名字上带有其输入端的硬件描述层次。比如：把硬件的系统级描述转 换为较低一层次的描述的综合器被称为算法综合器；把寄存器级描述 转换为下一层次的描述的综合器称为数据流综合器；算法综合器和数 据流综合器都称为行为综合器。对于低层次综合器，综合器的命名方 式有些混乱。有的文献把综合器输入端硬件描述的层次作为综合器的 名字。比如，把逻辑门级描述转换为晶体管级或者版图级描述的综合 器可被称为逻辑综合器。但也有文献把综合器输出端硬件描述层次作 为综合器的名字。比如，把硬件的逻辑门级描述或者晶体管级描述转 化为版图级描述的综合器称为版图综合器或者硅编译器“”。本文中主 要借助逻辑综合器进行设计研究和探索。 目前业界主流的综合器，主要是美国s y n o p s y s 公司和c a d e n c e 公 司推出的综合器。就市场占有率而言，s y n o p s y s 公司在综合器市场上 占据了主导地位。值得一提的是，中国科学院计算技术研究所推出的 “龙芯一号”就是使用了c a d e n c e 公司的物理综合器p k s 。 s y n o p s y s 公司的综合器种类齐全，形成了系列化，它包括： 设计编译器( d e s i g nc o m p i l e r ) 行为编译器( b e h a v i o rc o m p i l e r ) 库编译器 ( l i b r a r yc o m p i l e r ) 物理编译器( p h y s i c a lc o m p i l e r ) 笔者在合肥工业大学微电子设计研究所学习期间，对d e s i g n c o m p i l e r 作了较为深入的研究。 本文的后续章节中将结合d e s i g nc o m p i l e r ，以一个8 位r i s c ( 精 简指令集计算机) 的m c u ( 微处理器) 为载体，主要对逻辑综合进行 研究，阐述如下内容： ( 1 ) 不同加工工艺下综合手段的实现，将在o 1 8 1 1m ，0 2 5 1 1m ，0 3 5 1 1 m 三种不同的加工工艺下运用综合技术： ( 2 ) 基于时序驱动的综合手段的探索，探索对于不同的模块采用不 同的综合手段； ( 3 ) 静态时序分析的实现，使用静态时序分析理论和相关e d a 工具， 对设计进行时序分析。 2 2 综合的模型 组合逻辑综合基于布尔代数理论，寄存器传输级综合( 又称时序 综合) 基于有限状态自动机( f s m ，f i n i t es t a t em a c h i n e ) 模型，而对 于高级综合而言，需要在f s m 基础上增加数据通道模型。 有限状态机可以形式化的描述为五元组形式： 其中s 是状态集合，i 是输入集合，0 是输出集合，f 是状态转化函数， h 是输出函数3 。 当状态较少( 几百个) 时，f s m 模型可以很好的工作，但是，当 状态很多时，即使是复杂度较低的元件，如i o 接口或者总线控制器 都至少有上千个状态，这时，f s m 模型很难适应设计需要。为了使f s m 模型适应更复杂的设计需要，引入了带数据通道的有限状态机( f s m d ， f i n i t es t a t em a c h i n ew i t hd a t a p a t h ) 的概念。这里数据通道可以是定点 或者浮点寄存器，用来存储状态变量。例如，一个1 6 位寄存器可以存 储2 m ( 6 5 5 3 6 ) 状态，从而大大简化了状态控制和操作控制。f s m d 的定义如下： 设v a r 是存储变量的集合 e x p 是表达式的集合 e x p = f ( x ，y ，z ，) lx ，y ，z ，v a r a 是赋值语句的集合： a 2 x 控制逻辑，也称为控制流综合，完成状态和时序控制； 数据通道，也称为数据流综合，完成信息的处理、存储和传输； 对于控制流综合而言，涉及的主要方法是传统的寄存器传输级综合： 而数据流综合则涉及高级综合的理论和方法，数据流综合的过程分为 三个部分： 中间数据结构的生成： 调度； 分配。 综合时首先要对输入的行为描述进行编译，然后将编译结果转换 为适合于综合的、信息完备的中间数据结构。综合常用的描述语言包 括v e r i l o g 、v h d l 等，常用的中间数据结构有c d f g 、v t ( v a l h et r e e ) 、 a d d 等。 控制流图( c f g ) 用于生成电路的控制信息，d f g ( 数据流图) 用 于生成电路的数据通道。 调度的任务是把数据流图中的操作按时间顺序分配到各个控制 步，从而确定操作执行的时序，并使d f g 中的各个操作既符合数据相 关，又能在满足设计约束的前提下最大限度地实现并行操作。 分配的任务是根据每个控制步的寄存器传输推导出数据通道，它 又分解为两个子任务： 一。 单元选择，确定设计中所使用的r t l 基元的种类和数目； 单元装配，将d f g 中的操作、变量和数据映射到选定的硬件基元。 分配结束后，产生了设计的数据通道部分，另外根据控制流图和 调度过程中产生的状态信息，可以通过控制流综合来生成控制器部分。 这样，数据通道和控制器就组成了一个完整的结构化设计。 调度和分配是综合中的两个最主要的任务，这两个任务互相联系， 互相制约，分配要根据调度的结果判断单元的共享和互斥，同时只有 确定了硬件实现后才能得到更加精确的调度。对调度和分配的处理是 综合的关键。 2 3 综合中的调度技术 调度是自动综合中非常复杂的一项工作。其内容是把硬件行为分 解为不同状态，把每个算子分配到指定状态内完成。在时序系统中， 状态是最基本的时间单位。通常一个状态就是一个系统时钟周期。 调度算法可以划分为两类，即基于数据流图的调度算法和基于控 制流图的调度算法。 对于基于数据流图的调度算法，最基本的目标就是用尽可能少的 状态完成数据操作，即尽可能快的完成数据操作。除了要减少状态个 数之外，还要考虑可利用的运算单元的种类和个数等约束条件。基于 数据流图的调度算法是最大并行的算法由于调度算法的基础是数据 流图，而数据流图依赖于运算之间的数据相关性，这就决定了其并行 性。基于数据流图的调度算法通常等效于二维优化问题，即：( 1 ) 利 用给定的运算资源，尽量减少完成电路功能所需要的状态个数；( 2 ) 在给定的状态中实现电路功能，尽量减少使用的运算资源。这种算法 假定减少实现电路功能所需要的状态个数就可以减少算法的总执行时 间。当硬件的行为中带有分支结构时j 如果每个分支以相同的概率执 行，减少状态个数确实可以减少算法的执行时间。但是实际情况并不 一定满足这种假设，所以减少状态个数并不完全等效于减少算法的运 行时间。 控制流图本身是电路行为描述的顺序表示。基于控制流图的调度 算法将运算序列分配到一个状态中，同一操作可以分配到不同状态中。 每一个运算序列只有一个入口和一个出口。对于业界最流行的硬件描 述语言如v h d l 和v e r i l o g ，支持i f e ls e ，c a s e 等语法结构，控制 流图的分支节点就表示了这些条件结构，基于控制流图的调度算法适 合处理这种结构。 2 3 1综合中的基于数据流图的调度技术 应用最广泛的调度技术大多是基于数据流图。基于数据流图的调 度通常通过两种迭代方法解决二维优化问题，这两种的迭代方法为： ( 1 ) 使用的运算资源数目固定，优化目标是使用最少的状态个数完成 指定算法，通过迭代修改约束条件，以取得最优结果，这种调度称为 约束资源的调度；( 2 ) 状态个数固定，优化目标是运算资源数目最小， 通过迭代修改约束条件，取得最优结果，这种调度称为约束时间的调 度。 通常假定对运算单元的种类和个数没有任何约束，对完成硬件行 为所需的状态个数也不做限制，这种条件下的调度称为无约束调度技 术。如果对二者均有约束，称为同时存在时间和资源约束的调度技术。 2 3 1 1 无约束调度技术 无约束调度技术不限制运算单元的种类和个数，依次选择数据运 算安排到某个状态中完成。每次把数据运算安排到某个状态时做出如 下两项决策：( 1 ) 下一步应该安排哪一项数据运算? ( 2 ) 应该把选定 的数据运算安排到哪一个状态中完成? 上述两项决策可以根据全局准则作出，也可以根据局部准则作出。 如果采用局部准则，作出决策时供选择的项数少，计算量少，但得到 的结果可能差一些；如果采用全局准则，可能会得到较好的调度结果， 但是每次选择一个算子或者选定一个状态所需要的计算量可能比较 大。设计者通常要在设计质量和运算量之间进行折衷。无约束调度技 术有很多种，不同之处在于选择安排算子的方法以及把算子安排在哪 一个状态的方法不同。图2 2 给出了x = e ( a + b + c ) ，y = ( a + c ) $ ( c + d ) 的数据流图。 ab acd xy 图2 2数据流图 2 3 1 1 1无约束a s a p ( a ss 0 0 na s p o s s ib le ) 算法 最简单的调度方法就是无约束a s a p 方法。假定算子的总数已知， 而且已经构造好硬件的数据流图，那么无约束a s a p 方法进行调度的原 则是在每一个状态安排尽可能多的算子。安排算子时只考虑是否可以 获得参加运算的数据，并假设总是可以获得所需要的运算单元。这就 是说，尽可能早地安排每一个算子。按这种原则对图2 2 中运算进行 调度，可以得到图2 3 中所示结果。通常a s a p 方法可以得到最快的运 j、jj夕 、丫 算速度，但采用a s a p 方法调度需要的运算单元个数会很多。例如，图 2 3 中状态s 1 需要三个加法器。 s 1 s 2 abac d xy 图2 3a s a p 方法调度的数据流图 2 3 1 1 2 无约束a l a p ( a s ia t e ra s p o s s i b ie ) 算法 a l a p 方法调度方法从数据操作的最后输出开始调度。从完成全部 数据操作的最后一个状态开始调度，把每个算子尽可能安排在最后一 个状态中。也就是说，首先把产生输出信号所需的算子安排在最后一 个状态；然后把完成最后状态中的运算所需的输入数据安排在次最后 状态中，即次最后状态的运算结果是最后状态所需的输入数据。如此 进行回溯，一直到所有算子全安排完为止。由于在开始调度时并不知 道总麸需要多少个状态，因此，a l a p 调度方法是在调度结果结束后再 对状态进行编号。图2 4 给出了使用a l a p 方法调度的结果。 、荨一一 矿、一彳 s 1 s 2 s 3 ab - _ _ - - - - - 8c _ - - _ _ - _ l _ - _ 。_ - _ - _ _ _ e 、拶 - - l _ _ - - _ - 上_ - - _ - _ - _ _ i - _ _ - _ _ 留 一一一一 一一一一一一一一一 xy 图2 4a l a p 方法调度的数据流图 2 3 1 2 带有约束的调度技术 无约束调度技术解释了调度的基本问题，但在实际应用中，调度 需要满足各种不同的约束。带有约束的调度技术可以分为：约束资源 的调度技术、约束时间的调度技术、同时约束时间和资源的调度技术。 ( 1 ) 约束资源的调度技术就是要限制芯片面积，限制所使用的功 能模块的个数。前面a s a p 方法需要3 个加法器和1 个乘法器，a l a p 方法需要3 个加法器和2 个乘法器。如果限制芯片面积，只能使用1 个加法器和1 个乘法器，那么这两种调度方案都不能满足要求。因此， 引入了称为约束资源的调度技术。包括：状态撕裂法、约束资源的a s a p 调度方法、约束资源的a l a p 调度方法、排队调度技术、自由度法。 ( 2 ) 约束时间的调度技术就是对芯片的运算速度有特定的要求。 在调度过程中，通过对状态数目的限制，可以实现对运算时间的约束。 对时间的约束分为两类：1 、限制全部数据必须在指定的状态数目中完 成；2 、限制某个算子必须在指定的状态中完成。有时候会同时存在这 两种约束。例如，对于图2 5 所示的数据流图，可以限制必须在三个 状态中完成全部运算，且限制算子1 和4 必须在第一个状态中完成， 算子2 必须在第二个状态中完成，算子3 必须在第三个状态完成。作 出这些限制的原因通常是由于这些算子位于一定的关键路径上，无法 把它们安排到其它状态。 约束时间的调度技术中最常用的是f d s ( f o r e ed i r e c t e d 1 4 s o s 1 s 2 s 3 abcd xyxy 图2 5无约束a s a p 调度以及a l a p 调度 s c h e d u l i n g ) 法。这种方法的优化目标是将同一类算子尽可能地均匀 地分布到各个状态中。均匀分布的结果是器件利用率得以提高。f d s 算法的主要目标就是在各个状态之间有效地共享数据处理单元。比如 对于算子5 的安排，有两种可能性，即算子5 可以安排在状态1 ，也可 以安排在状态2 。如果安排在状态1 ，则完成系统功能需要3 个加法器； 如果安排在状态2 ，则只需要2 个加法器。 ( 3 ) 对于同时存在时间和资源约束的调度问题，最常用的解决方 法是线性整数规划法，这种方法能够保证得到最优调度。但是，最优 调度常常是以牺牲运算时间为代价。线性整数规划法将调度问题表达 为一组满足不等式约束的线性目标函数。理论上讲，整数线性规划一 定有最优解，但是当不等式的个数比较大时，求解不等式所需的时间 成指数增长，因而不能采用该方法。调度较大规模的实际设计问题， 通常要采用简化算法。 2 3 2综合中的基于控制流图的调度技术 基于数据流图的调度技术以数据流图作为设计的内部表述，适用 于对无限数据流重复进行一系列运算的系统进行综合的调度，这种情 况下某些运算可以并行完成。在完成以控制为基本功能的系统中，控 制序列和外部条件有关，系统的算法描述主要包含控制结构，只有少 数运算的需求。对于这种系统的综合，不应采用基于数据流图的调度 方法，而应采用基于控制流图的调度技术，以控制流图作为设计的内 部表述。 在硬件高层源代码中，条件分支语句对应着不同的执行路径。完 成不同代码分支中的状态所需要的状态个数可能不同，但是对同一个 分支来讲，完成其运算所需的状态则是固定的。采用基于数据流图的 调度方法，本质上是假定完成所有代码分支所需要的状态个数相同， 即为各个分支中最大的状态个数。 基于控制流图的调度方法基本上是贯序法。需要根据控制流图定 义调度路径，就是将控制流图划分为调度路径序列，根据调度结果构 造有限状态机。 基于控制流图的调度方法主要有：a f a p 调度、动态环调度。 a f a p 调度方法首先对全部可能路径独立调度，然后设法减小路径 长度。出发点是在满足约束条件的前提下尽量减少状态个数。在控制 流图中，首先要拆除反馈边来去除图中的环路。 和a f a p 调度方法不同，动态环调度技术并不切断控制流图中的反 馈边，在调度过程中也不中断路径的生成。只有在违反约束条件时才 中断路径的生成，从而减少了路径个数，减少了路径生成的复杂性。 2 4综合中的分配技术 分配是指确定系统中使用哪几个器件以及器件之间如何连接。分 配包括三项内容：( 1 ) 分配寄存器或者r a m ，以存储数据；( 2 ) 分配运 算单元，以完成指定的数据运算：( 3 ) 分配器件之间的连接路径，以 完成数据在器件之间的传递。当然，一般情况下，这三项工作相互联 系。其中，为每个数据操作项分配硬件运算单元和为寄存器( 或者其 它存储单元) 分配数值又称为数据通道分配。分配得到的结果是硬件 的寄存器级表示。分配也可能受到一些约束条件的限制，比如最大延 迟、最大面积、最大功耗或者最大成本等。 分配算法一般可以分为如下两类：一类是迭代构造法，另一类是 全局构造法。迭代法每次只根据局部原则选择下一个要分配的内容， 每次只对一项内容进行分配，直到所有内容全部分配好为止。全局法 总是对未分配的内容进行检查，试图发现总体目标的最优调度方法。 穷举搜索法是全局分配法的最简单的例子。它能保证结果的最优性， 但是采用穷举搜索法所需要的计算量是巨大的。迭代法每次分配时只 对很小的空间进行搜索，因此计算效率较高，但是一般不能保证找到 最优解。 2 4 1分配的基本问题 分配要解决的第一个问题是分配寄存器，用来保存数据。图2 6 给出了对于图2 3 的调度结果分配寄存器和运算单元的情况。开始分 配时，必须对输入数据锁存之后才能开始运算，因此增加了状态s 0 来 6 完成输入数据锁存。 图2 6 中的深色小圆点表示数据存储要求例如在状态s 0 和s 1 之 间，要求存储5 个数据值，它们是输入的5 个数据可以任意分别把5 个 输入的数值a ，b ，c ，d 和e 分配给5 个寄存器r 1 r 2 ，r 3 ，r 4 和r 5 。在状 态s l 和s 2 之间同样需要存储5 个数据值，因为此时寄存器r l ，r 2 ， r 3 和r 4 中的数据己不再有用，所以可以重复使用这些寄存器。确定哪 个数据使用哪个存储单元对器件间互连的复杂程度影响很大，也会影 响信号延迟、芯片面积、器件种类和数量、器件的扇入扇出要求等内 容，因此会影响系统成本。 分配的第二项工作是分配运算单元。分配可能会受到器件库中运 算单元种类的限制，这种情况称为从底向上的分配，如果可以使用任 何需要的器件，而不受单元中是否存在这些器件的限制，称为无约束 分配或从顶向下的分配。对于同一设计问题，为满足不同的实际要求 可以采用不同的分配方法。对于这里讨论的例子，我们假定器件库中 有加法器、乘法器、寄存器、多路选择器等基本单元，采用从底向上 的分配方法。 s 0 r 5 s 1 s 3 d 守巴2巴， - 3 1 r 4 i 一 1 一| 7 a d l w a d 2 b 丫 r 并a d 3 ir j：r 3y r 5 、r 1 、r 2 y 夕r 4 胱旷晚u ， 工-一 r 5 厂r 1r 2 博m u l - r ltr 2 1 x y 图2 6按照a s a p 调度的结果分配寄存器和运算单元 在状态s l 中，3 个加运算同时运行，需要3 个加法器，分配3 个 加运算分别由加法器a d l ，a d 2 和a d 3 完成。在状态s 2 中，要执行1 个加运算和1 个乘运算，加运算可以重复使用加法器a d l ，乘运算可以 分配由乘法器m u l 完成。在状态s 3 ，由于只执行1 个乘运算，所以可 以重复使用乘法器m u i 。数据单元分配的结果也画在图2 6 中。 ab ecd 图2 7按照a s a p 调度的结果的一种数据通路 分配的第三项工作是分配数据通路，目的是完成器件之间的互连。 图2 7 给出了按图2 6 分配寄存器和