（电路与系统专业论文）面向时间性能的高层次综合调度算法的优化技术研究[电路与系统专业优秀论文].pdf

面向时间性能的 高层次综合调度算法的优化技术研究 摘要 | l 随着电子设计自动化研究的飞速发展，逻辑综合和r t l 综合工具 不断臻于完善，使得高层次综合技术的研究成为集成电路设计自动化 工具研究领域中新的热点，在近2 0 年来在研究领域内获得了飞速的 发展。它的兴起有着其必然的原因：首先，高层次综合技术的应用可 以明显地提高设计速度，大大缩短设计周期，从而允许设计者对数字 系统进行不同方案的设计，寻求最优或满意的设计，加速了各种高性 能集成电路产品进入市场的过程。其次，随着集成电路规模的不断扩 大，其结构日趋复杂，迫使设计人员必须从更高的抽象层次来进行总 体设计，而高层次的行为描述比低层次的结构描述简洁且容易编写和 理解，这正好符合了这一发展方向的需要。 对于一个待设计的集成电路产品，用尽可能少的硬件代价来实现 一个时间性能可以接受的设计方案是其的一个目标，但在设计过程中 更常面对的另一个情况是用一个可以接受的硬件代价来实现一个时 间性能尽可能高的系统。特别是随着整个社会信息化进程的不断深 入，高速宽带网络的广泛应用使得对各类相关电子产品的时间性能要 求越来越高，迫切需要我们研究进一步提高时间性能的优化技术。本 文研究的内容即为在高层次综合的调度过程中针对时间性能优化的 各种技术。 本文首先详细研究了前人提出的各种典型的主调度算法，分析 了它们各自的特点和最适于解决的问题范围，随后研究了调度算法中 面向时间性能的各种优化技术，如功能流水线、循环折叠、循环分解、 多控制步操作技术、链技术和对控s t j 数据流图进行变换的强时间约 束条件下的调度优化技术等，详细分析了它们各自的优缺点和在主调 度算法中的应用，并在此基础上提出了两种新的调度和优化技术： ( 1 ) 提出了一种基于逐步放松的弹力引导算法的资源限制型调度算 法，它能够在面向资源限制条件的调度问题中获得高时间性能的解。 ( 2 ) 提出了一种新的强时间约束条件下的调度优化算法，使得在强 时间约束条件下进行调度的成功率大大提高。最后应用这些调度优化 技术实现了一个简单的调度系统r f s 。 譬以 关键词：电子设计自动化，高层次综合，调威时间性能 s t u d ie s0 nt h eo p t l m i z a t l 0 nt e c h n i q u e sf o r h l g hl e v e ls y n t h e s l ss c h e d u l i n ga l g o r l t h m 0 rie n t e d 丁0tim ep e r f o r m a n c e a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fe 1 e c t r o n i cd e s i g na u t o m a t i o n 1 0 9 i cs y n t h e s i sa n dr t ls y n t h e s i st o o l sh a v eb e e ng o i n gp e r f e c t a n ds t u d yo nh i g h l e v e ls y n t h e s i sh a sb e c o m i n ga n o t h e rh o t s p o t i ne d ar e s e a r c hf i e l d d u r i n gt h ep a s t 2 0 y e a r s h i g h l e v e l s y n t h e s i st e c h n i q u ec a ng r e a t l yr e d u c et h ed e s i g np e r i o da n d s p e e du p t h et i m e t o m a r k e t a l s ot h e h i g h l e v e ls y n t h e s i s t e c h n i q u ec a nh e l pt h ed e s i g n e r st od e s i g ns y s t e m so nam o r e a b s t r a c t l e v e l ，w h i c hh a ss h o wi t su t m o s ti m p o r t a n c ei nt h e d e s i g no ft o d a y sl a r g ec o m p l e xs t r u c t u r es y s t e m s f o ra ni cp r o d u c tt ob ed e s i g n e d ，o n ed e s i g nt a r g e ti st o g e tm i n i m u mh a r d w a r ec o s tw i t ha na c c e p t a b l et i m ep e r f o r m a n c e b u ta n o t h e rd e m a n dw em o r eo f t e ne n c o u n t e ri st o d e s i g n a h i g h e s t t i m e p e r f o r m a n c es y s t e mw i t ha na c c e p t a b l eh a r d w a r e c o s t w i t ht h e s o c i e t y s i n f o r m a t i o n a l p r o c e s s a n dw i d e a p p l i a n c e o f h i g hs p e e dn e t w o r k ，t h er e q u e s t s f o rt i m e p e r f o r m a n c e o ft e l e v a n te l e c t r o n i c p r o d u c t s a r e b e c o m i n g h i g h e r a n d h i g h e r t h e yb r i n g o na n u r g e n t n e e dt o s t u d y o p t i m i z a t i o nt e c h n i q u ef o rt i m ep e r f o r m a n c et h a t i sa l s ot h e m a i nc o n t e n to ft h isp a p e r t h e p a p e r f o c u s e si t s s t u d y o nt h et i m e p e r f o r m a n c e o p t i m i z a t i o nt e c h n i q u e so fh i g h l e v e ls y n t h e s i ss c h e d u l i n g a l g o r i t h m f i r s t l y ，i d i s c u s st h ee x i s t i n gm a i n s c h e d u l i n g a l g o r i t h m sa n da n a l y z et h e i rc h a r a c t e r i s t i c sa n dp r o b l e m st h a t t h e ya r eo r i e n t e dt o t h e nis t u d yt h eo p t i m i z a t i o nt e c h n i q u e s f o rt i m e p e r f o r m a n c e i nt h e s e s c h e d u l i n ga l g o r i t h m s t h e o p t i m i z a t i o nt e c h n i q u e s i n c l u d ef u n e t i o n a l p i p e i i n e ，l o o p f o l d i n g ，l o o pu n r o l l i n g ，m u l t i p l e c o n t r o l s t e po p e r a t i o n t e c h n i q u e ，c h a i nt e c h n i q u ea n do p t i m i z a t i o nt e c h n i q u eu n d e r s t r o n gt i m ec o n s t r a i n te t c o nt h eb a s e so ft h e s es t u d i e s ，i p r o p o s em yo w nt w oo p t i m i z a t i o nt e c h n i q u e s ：t h ef i r s to n ei s ag r a d u a lr e l a xa l g o r i t h mb a s e do nf d sa l g o r i t h mw h i c hc a ng e t h i g hq u a l i t ys c h e d u l i n gr e s u l tu n d e rr e s o u r c e1 i m i t s t h e s e c o n do n ei san e wo p t i m i z a t i o n s c h e d u l i n ga l g o r i t h mu n d e r s t r o n gt i m ec o n s t r a i n tw h i c hh a sam u c hh i g h e r s c h e d u l i n g s u c c e s sr a t et h a no t h e r a l g o r i t h mo ft h i s t y p e a t l a s ti i n t r o d u c ea s i m p l es e h e d u li n g s y s t e m n a m e dr f sw h i c hi s i m p l e m e n t e db ym y s e l fw i t ht h e s en e wt e c h n i q u e s k e yw o r d s ：e l e c t r o n i cd e s i g n s c h e d u l i n g ，t i m e a u t o m a t i o n ，h i g h l e v e ls y n t h e s i s ， p e r f o r m a n c e 申请上海交通大学硕士学位论文 第一章绪论 第一章绪论 随着逻辑综合和r t l 综合工具的不断臻于完善，高层次综合技术的研究成为 集成电路设计自动化工具研究领域中新的热点，在近2 0 年来在研究领域内获得 了飞速的发展。它的兴起有着其必然的原因：首先，高层次综合技术的应用可以 明显地提高设计速度，大大缩短设计周期，从而允许设计者对数字系统进行不同 方案的设计，寻求最优或满意的设计，加速了各种高性能集成电路产品进入市场 的过程。其次，随着集成电路规模的不断扩大，其结构日趋复杂，迫使设计人员 必须从更高的层次来把握总体设计，而高层次的行为描述通常比低层次的结构描 述简洁且容易编写和理解，这正好符合了这一潮流的需要。 本文研究的主要对象即为高层次综合调度过程中面向时间性能的优化技术。 首先我们将对高层次综合及一些相关概念做总体上的介绍。 1 1 高层次综合的起源与概念 集成电路技术的发展，一直沿着工艺技术( 集成能力) 和设计能力两条独立 的路线发展。长期以来，集成电路的集成能力一直按照著名的“摩尔”定律，以 每十八个月翻一翻的速度飞速发展，到2 0 0 1 年，成熟的制造工艺已经达到0 1 3 i - t m 的最小特征尺寸；逻辑电路的集成度可达一千万个晶体管每平方厘米。因此随着 工艺技术的迅速发展，对芯片的设计能力也不断地提出着新的要求，以便能够充 分利用工艺水平提高带来的益处。显然，要设计集成度如此高的芯片并保证设计 的正确性，仅仅依靠人工是不可想象也是无法实现的。随着计算机技术的发展， 人们可以利用计算机来辅助完成这项复杂的工作，这就导致了集成电路c a d ( c o m p u t e r a i d e dd e s i g n ) 系统的出现。 最早的集成电路c a d 系统，从7 0 年代就开始出现了。当时该类系统使用 1 6 位小型机，能够完成的主要工作是交互式图形的编辑和设计规则的检查，这 使得设计师从繁杂的手工绘图的工作中解放出来，并且由于该系统进行设计规则 检查，能够保证所绘制图形的正确性。但是，这类系统主要是帮助设计人员完成 申请上海交通大学硕士学位论文 第一章绪论 一些底层的、机械的重复性工作，抽象层次比较低，本身毫无思考能力，因而无 法保证设计的正确性，当设计出错时就暴露出返工费用高、设计周期长的弱点， 所以这类系统不能适应更大规模的设计任务。 8 0 年代出现了新一代的集成电路计算机辅助设计系统，如我所参与研制的 “熊猫”系统 1 。这一代c a d 系统以3 2 位工作站为硬件平台，同时软件的功 能大大增强，能够完成逻辑图输入、逻辑模拟、测试码生成、电路模拟、版图设 计、版图验证等功能。设计工程师能够使用前端的工具检验所设计电路的正确性， 在一定程度上减少了由于电气设计错误带来的重复设计耗时问题。在版图阶段， 这类系统除了有全定制电路的版图编辑工具( 如“熊猫”系统中的l e ) ，有的还 提供对门阵列、标准单元电路的自动布局布线功能。最重要的是，这类系统引入 了较完整的版图验证工具，包括设计规则检查d r c ( d e s i g n r u l ec h e c k ) ，电学 规则检查e r c ( e l e c t r i c i t y r u l ec h e c k ) 以及版图和电路的一致性检查l v s ( l a y o u t v e r s u ss c h e m a t i c ) 等工具，而l v s 中又使用了l p e ( l a y o u tp a r a m e t e re x t r a c t ) 工具( 版图参数提取工具) 的结果( 如“熊猫”系统) 。系统先将由l p e 得到的 电路图与原设计进行对比，检查二者是否一致；同时还可将l p e 得到的版图寄 生参数引入电路图进行电气性能的模拟，进一步检查电路的性能是否满足设计要 求。如此种种工具，保证了流片的一次成功率。然而，当设计规模进一步增大时， 这种形式的c a d 工具仍存在种种不足。例如，由于芯片的集成度越来越高，一 块芯片上常常集成数万、数十万的门，此时如果再利用原理图输入电路将是一件 非常繁杂的工作；另一方面，目前各类电子产品需要大量的a s i c ，同时由于全 定制芯片具有种种优点，因此要求生产大规模全定制a s i c 的呼声很高，如果 c a d 工具不能完成全定制芯片的自动布局、布线，则在如此大规模集成度的情 况下，按传统观念进行布线是行不通的。因此，正是基于以上种种考虑，在这个 阶段开始形成了“综合”的概念。综合即根据描述数字系统的行为以及要满足的 约束条件和目标集合，找出一个满足约束条件和目标集合的结构来实现它。这里 所说的行为是指数字系统或其他部件与外部环境的相互联系和相互作用，例如， 从输入到输出的映射关系，而结构指的是组成系统的各个部件及其相互之间的连 接关系。不过，在这个阶段，受限于计算机技术的发展水平和集成电路设计应用 情况的实际需要，对设计工具的研究主要集中在逻辑综合。 申请上海交通大学硕士学位论文第一章绪论 进入9 0 年代，由于计算机技术的发展，正式出现了e d a ( e l e c t r o n i cd e s i g n a u t o m a t i o n ) 的概念，即电子系统设计自动化；虽然过去的两代产品也被称为第 、第二代的e d a 产品，但实际上它们仍旧是传统意义下的计算机辅助工具： 正是第三代的e d a 产品，改变了集成电路设计的观念，在一定程度上，实现了 设计的自动化。设计自动化技术的发展，正是今后半导体学科和电路系统学科发 展的一个方向，设计自动化研究的主要内容，可参见文献 2 】 3 】。在第三代e d a 系统中，引入了硬件描述语言，使得设计芯片类似于设计软件的过程，更加灵活， 易于修改。同时，随着数字系统复杂性的不断提高，将系统分层描述成为了描述 系统的必要和主流的手段【4 【5 】 6 。最高层为系统层，该层涉及了整个系统的信 息流：第二层为算法层，该层主要描述单个处理器( 芯片) 内部的运算活动，以 算法的形式表示了一系列输入信号到输出信号的映射关系；再往下的第三层为寄 存器传输层，该层描述了在存储单元和各个功能单元之间的一系列数据流动和变 换的过程：最下两层为逻辑层和电路层，分别以布尔代数方程和电路网络方程的 形式描述各自的行为。在此系统分层描述的基础上采用了层次式的数据管理模 式，并在不同层次使用与集成电路设计不同阶段相应的e d a 工具，特别是由于 在寄存器传输级有比较完善的逻辑综合工具的产生和引入，免去了设计者大量重 复繁杂工作之苦，大大缩短了设计周期，从而大幅度地提高了设计复杂数字系统 的能力。 但是考察当前进行的许多复杂设计，一般都是先用软件算法表达设计意图并 进行仿真，然后将软件描述翻译为可综合的寄存器传输级硬件描述，最后用硬件 电路实现。其中的软件算法描述就是芯片功能的表示，如果翻译为对应的硬件描 述语言表示，即为高层次的行为描述。但是把这行为级的算法描述翻译为寄存器 传输级的描述的工作最初却是由硬件设计师用手工完成的，然后才能进行寄存器 传输级综合等后续步骤。很显然，这种方法存在着一些问题：一，i c 设计自动 化的要求整个过程是个紧密耦合的过程，各个设计层次上的e d a 工具应该具 备各种内在的，自动的通信机制，而这种设计方法中行为级和寄存器传输级之间 是脱节的，寄存器传输级以后的设计信息很难反馈到前级，从而可能导致各个层 次描述不一致。二，从高层次的行为描述向寄存器传输级的手工翻译过程费时费 力，而且极容易发生错误。三，对于典型的集成电路设计规模，寄存器传输级的 申请上海交通大学硕士学位论文 第一章绪论 仿真速度非常慢。四，这种方法限制了探索设计空间的能力，这是由于寄存器传 输级描述只能反映一种特定的电路硬件结构，而算法级的高层次行为描述和性能 要求的改变常常导致寄存器传输级的完全重新设计。 特别是2 0 世纪9 0 年代以来，i c 芯片集成度的增加极为迅速，且市场的变化 也日益迅速，要求大幅度地缩短集成电路的设计周期。传统的寄存器传输级的设 计方法在能力上已达到了极限，要求集成电路设计师必须在比寄存器传输级更高 的抽象层次上进行设计。因此，行为极的高层次综合设计方法和设计工具就应运 而生了。 高层次综合，也称行为综合，就是由e d a 工具经过一系列自动转换，根据 对数字系统行为的算法层的描述，在满足指定的目标和限制的条件下，生成寄存 器传输层的结构描述的综合，如图1 - 1 所示( 引自文献【7 】) 。该生成结构也即高 层次综合的目标包括个数据通路和一个控制器。数据通路是由寄存器，功能单 元，多路器和总线等模块构成的互连网络，用于实现数据的传输。控制器通常由 硬连逻辑( h a r d w i r e dl o g i c ) 或固件( f i r m w a r e ) 构成，用于控制数据通路中数据 的传输。 bx c = a + b ： z = x + y ； y 图1 1 高层描述与寄存器传输层实现 f i g1 - 1h i g hl e v e ld e s c r i p t i o r la n dr t li m p l e m e n t a t i o n 正如数字系统可以在多个不同的层面上进行详细描述一样，综合也可以在多 个层次上进行。高层综合的出现，使这种层次上的对应关系在更高的抽象层次上 得到了对应，进一步完善了新一代集成电路设计方法学的设计流程安排。使得真 一 晰 一 申请上海交通大学硕士学位论文 第一章绪论 正的对集成电路的自顶向下( t o pd o w n f l o w ) 的设计成为可能。下图给出了综合 的三个层次：高层次综合( h i g h l e v e ls y n t h e s i s ) ；逻辑综合( 1 0 9 i cs y n t h e s i s ) ：版 图综合( 1 a y o u ts y n t h e s i s ) 与数字系统描述之间的层次关系。 a l g o r i t h ml e v e l 上 r t l j l o g i c 】e v e 】 i + c i r c u i tl e v e l i ， l a y o u t1 e v e l h i g h l e v e ls y n t h e s i s l o g i cs y n t h e s i s l o g i cs y n t h e s i s l a y o u ts y n t h e s i s 图1 - 2 数字系统描述与综合的层次关系 f i g1 - 2h i e r a r c h yr e l a t i o n s h i pb e t w e e nd i g i t a ls y s t e md e s c r i p t i o na n ds y n t h e s i s 1 2 高层次综合的任务及流程 前文已经述及，高层次综合的任务是从一个高层次的对算法层的数字系统行 为的描述出发，在满足一定的目标和限制的条件下，生成寄存器传输层的结构描 述，即一个数据通路和一个控制器。它通常包括编译与转换，调度，分配，控制 器综合等部分 4 1 1 7 1 ，如图l - 3 所示： 1 2 1 编译与转换 高层次综合的第一步，首先是将行为特性描述编译转换到一种有利于高层次 综合的中间表示格式。数字系统的行为特性描述是由硬件描述语言描写的，它的 编译与计算机高级程序设计语言的编译相似。而中间表示格式通常是包含数据流 和控制流的语法分析图。 申请上海交通大学硕士学位论文第一章绪论 a l g o r i t h md e s c r i p t i o n 图卜3 高层次综合流程 f i g1 - 3 f l o wo f h i g hl e v e ls y n t h e s i s 122 调度 高层次综合的下面一步，也就是从行为到结构转换的核心部分，称为调度。 调度就是将操作赋给执行过程中的某个时间段。在同步系统中，执行时间是用控 制步来表示的，一个控制步是一个基本时序单位，对应一个或多个时钟周期。调 度工作的依据为控制数据流图中各操作的偏序关系以及给定的时间限制( 或资源 限制) ，以达到最小的资源消耗( 或时间消耗) 为目标。对于一个给定的数据流 图，调度除了要面对图本身的拓扑结构所决定的各个操作的偏序关系外，通常还 需要面对一些人为设定的限制条件：最常见的即为时间限制和资源限制。时间限 制规定了完成所有操作的最大时限，或者是输入数据的速率。资源限制则规定了 最多可以使用的资源数目和种类：包括各种基本运算单元，如加法器和乘法器等： 存储单元如寄存器等：互连网络如总线和多路器等；甚至可能只是一个总的指标， 如所有资源的总的造价或它们总共所占用的芯片面积等等。一个调度算法在满足 特定限制条件的情况下，将数据流图中的所有的操作节点安排到特定的控制步 上，即得到一个调度问题的可行解，可行解通常有多个。除了限制条件，调度问 题中的另一个重要概念为所谓的最优准则或者称目标函数。最优准则( 目标函数) 6 皇! 童圭塑奎望查堂堡主兰些堕茎 箜二童量鱼 的作用是在多个可行解中定义和区分好的解和坏的解。例如，在时间限制调度问 题中，最优准则通常为占用最少的芯片面积，又比如，在资源限制调度问题中， 最优准则通常为最快的系统功能完成时间。 调度的主要任务既然是把高层次行为描述的每一个操作都安排到一个特定 的时间间隔即控制步中去完成，它实际上是对欲设计系统进行时序上的划分，它 决定了整个数字系统中各操作的串行和并行的折衷，近似地决定了数字系统的性 能价格比，是从行为向结构转换的核心部分，是数据通道设计中至关重要的一步， 是高层次综合中最复杂的部分，因此也是高层次综合中最重要的环节。 1 2 3 分配 分配是将操作和变量( 或值) 绑定到相应的功能单元和寄存器进行运算和存 放。分配的目的在于使所占用的硬件资源花费最少。硬件资源包括功能单元，存 储单元以及数据传输的通路。分配过程与调度紧密相关，因为正是调度的结果反 映了各个操作和变量的生存期在不同的控制步上的重叠性，从而影响到功能单元 和寄存器的共享。 1 2 4 控制器综合 一旦调度和分配完成，数据通路设计完以后，还需要综合一个按调度要求控 制数据通路的控制器。控制器可以用多种方法来实现。通常使用的方法主要有两 种。一种是使用硬连逻辑( h a r d w i r e dl o g i c ) 来实现。此时，每一个控制步对应 于有限状态机( f s m ) 的一个状态，控制器的综合问题转化为有限状态机的综合 问题。还有一种方法是用固件( f i r m w a r e ) 实现。这种方法来源于微码技术。此 时，每一个控制步对应于微程序的一条指令。控制器的综合问题转化为了微指令 的优化问题。有限状态机的综合和微程序的优化技术在理论和实现上都已十分成 熟，而且控制机的设计与高层次综合的主要任务数据通路的设计相比较，比 较简单，与整个高层次综合的流程中的其他步骤的联系也相对独立，因此不是高 层次综合中的重点。 1 3 数据表示的中间格式 申请上海交通大学硕士学位论文第一章绪论 上文已经提到，行为级描述的代码被高层次行为综合系统读入后，要编译转 化为一定的内部模型，即某种严格定义的中间格式。整个高层次综合的过程就是 对中间数据格式表示的各种内部设计信息进行连续地转换的过程，所以在某种意 义上，可以认为这种中间数据表示格式才是高层综合系统真正的“输入形式”【6 】。 因此有必要再专门介绍一下高层次综合系统的中间数据格式。就综合系统而言， 最佳的输入形式是一种以节点表示操作，有向线段表示操作间的数据和控制关系 的有向图，通常有三种：数据流图，控制流图和控制数据流图。 1 3 1 数据流图 v 1 ：= a + b ： v 2 ：= c + d ： v 3 ：= v i + v 2 v 4 ：= e - f ： g ：= v 3 v 4 ： 图1 - 4 数据流图 f 。 f i g1 - 4 d a t a f l o “g r a p h 数据流图( d a t af l o wg r a p hd f g ) 是高层次综合系统中常用的中间格式。在 这种图中，用节点代表程序中的操作，用有向线段代表数据，线上的箭头代表了 数据流动的方向。节点的作用是根据输入的数据产生新的数据。数据流图可以有 同步和异步两种方式。在同步方式中，一条线在某个特定时刻( 控制步) 只能保 存一个数值，节点在新数值到来之前必须处理完旧的数据；而在异步方式中，每 条线都有一个对应的数据队列，数据进出队列和节点处理数据都是异步的。在现 在的高层次行为综合系统中都只能使用同步数据流图。数据流图是在程序中表示 表达式的最理想的形式，极其适合于使用在面向密集数据依赖关系系统的高层综 合系统中。其唯一的弱点在于表示数据间的控制结构的信息的能力较弱。尽管如 此，数据流图仍然是最基本和重要的中间格式，应用最广泛的调度算法最初都是 基于数据流图产生的。图1 - 4 即为一段v h d l 程序和其相应的数据流图。图中 节点n i n 5 对各种数据进行运算处理，各条线护g 则是相应的数据，线上的箭 申请上海交通大学硕士学位论文 第一章绪论 头表示数据流动方向。 1 ，3 2 控制流图 与数据流图相对应，还存在着一种控制流图( c o n t r o l f l o wg r a p hc f g ) ，它适 用于表示各种控制结构，例如条件循环，条件转移，子程序调用以及各种意外处 理等。控制流图也由节点和有向线组成。与数据流图不同的是这里的节点分为操 作节点和分支节点两类，操作节点与数据流图中的操作节点类似，只不过含义更 加广泛，不但包括算术和逻辑运算，还可以是赋值和子程序调用等操作；而分支 节点表示各种条件结构，比如说v h d l 中的i f , c a s e ，w h i l e 等语句。控制流图 中的有向线段不表示数据，而是表示节点之间的依赖关系。控制流图非常适合于 表示各种控制结构，但在数据流的分析和变换上的能力十分有限，因此除了极少 部分特殊的情况外应用不多。 1 3 3 控制数据流图 控制数据流图( c o n t r o ld a t af l o wg r a p hc d f g ) 则是在数据流图的基础上增加 控制节点形成的。在这种图中，节点表示数据操作和控制结构，有向线表示节点 之间的相关性。不过c d f g 的具体格式的定义因不同的高层综合工具而异 6 】 8 】， 但通常都包括操作节点，用于表示抽象的操作运算；结构节点，用于表示控制结 构：其中结构节点又常分为分支节点和汇聚节点，表示条件分支。此外还包括数 据相关边( 用实线表示) ，用于表示数据相关性；控制相关边( 用虚线表示) ，表 示控制相关边。 图1 5 所示即为一段v h d l 代码和其相应的控制数据流图的例子( 引自参考 文献 9 】) 。图中用三角形表示的即为结构节点。其中用上三角形表示的是分支节 点，用下三角形表示的是汇聚节点。有了分支节点和汇聚节点，在图中就能直接 标识出条件操作和循环结构，从而识别出控制结构。 需要特别说明的是，不论是数据流图，控制流图还是控制数据流图，都只是 一种表示信息的中间格式，它们之间并没有本质上的区别，只是在表达不同类型 的信息时其能力有所强弱。 9 申请上海交通大学硕士学位论文第一章绪论 u s e s t d a u e n t i t yd i f f e qi s p o r t ( x i n ，y i n ，u i n ：i ni n t e g e r ； x o u t ，y o u r ：o u ti n t e g e r ) g e n e r i c ( a d ：i n t e g e r ) , e n d d i f f e q ； 图1 - 5 控制数据流图 f i g1 - 5 c o n t r o ld a t af l o wg r a p h 1 4 高层次综合中的设计空间搜索 对于一个给定的系统描述，其实现的方式是多种多样的，这些所有可能的实 现方式的集合，即为该系统的设计空间，或称解空间。系统越复杂，其设计空间 也就越庞大。在上述高层次综合流程的各步骤中，一个主要问题是：为了找到满 足约束条件的最优解，必须搜索庞大的设计空间。而需要搜索的设计空间又是一 个多维的非连续的空间，难以找到一个规范的搜索集来系统的搜索整个空间。并 且由于设计空间的形状实际上是由具体问题说明限制的，无法保证搜索整个空 间。因此高层次综合中的任何一个子任务都是一个n p 问题。 由于设计空间是由问题说明的，使得设计空间成为一个不规范的复杂空间， 一 m 一 咖 一吼 弭 叫 州m 叭脚 t 妒 一 一咖一呻一一一一一一一一一一 申请上海交通大学硕士学位论文第一章绪论 因而无法保证完全搜索整个设计空间。为了对设计空间进行搜索，就需要引入专 家知识和专门知识来引导设计空间的搜索。目前使用的搜索策略有以下三种： ( 1 ) 运用基于规则、基于知识的专家系统引导对整个设计空间的搜索。但 是这种方法的问题在于搜索时间太长。 ( 2 ) 运用启发式算法进行设计空间的搜索，如构造算法、迭代改进算法、 贪婪算法规则等。启发式算法基于一些启发式规则，缩小问题的搜索空间，期望 在合理的时间内得到问题的近似最优解或满意解。启发式算法规则一般源于专家 设计经验，并在算法实现中不断加以完善。 ( 3 ) 缩小问题的领域，运用专门领域的知识引导设计空间搜索。由于问题 的领域缩小，使得设计空间迅速减小，相应领域的专门知识和特点可以较好地引 导设计空间搜索，寻求最优解或满意解。例如，面向数字信号处理系统( d i g i t a l s i g n a lp r o c e s s i n g ，d s p ) 设计的高层次综合系统 1o 】【1 1 【12 】，或面向控制系统设 计的高层次综合 1 3 卜【1 8 ，都可以根据其各自需要解决的特定问题实现综合的优 化。 1 5 本章小结 本章介绍了高层次综合系统的起源、概念和任务，分析了其各个组成部分的 在系统中的作用与意义，指出了调度在高层次综合系统中的核心地位，并特别重 点介绍了与调度紧密相关的高层次综合系统的中间数据表示格式以及对设计空 间的搜索方式的考虑方法，为下文进一步的研究建立了必要的概念。 本章参考文献 【2 】 3 【4 】 洪先龙，刘伟平，边计年，超大规模集成电路计算机辅助设计技术，北京，国防工 业出版社，1 9 9 8 。 林争辉等，微电子电路与系统，卷一，第一分册，上海，上海交通大学出版社，1 9 9 3 。 林争辉等，微电子电路与系统，卷一，第二分册，上海，上海交通大学出版社，1 9 9 5 。 薛宏熙，边计年，苏明，数字系统设计自动化，北京，清华大学出版社，1 9 9 6 。 i i 申请上海交通大学硕士学位论文第一章绪论 【5 】5 f 6 】 7 】 【8 】8 9 】 【1 0 【1 2 】 【1 3 】 【1 4 1 5 】 【1 6 】 1 7 杨之廉，申明，超大规模集成电路设计方法学导论，第二版，北京，清华大学出版 社，1 9 9 9 。 王志华，邓仰东，数字集成系统的结构化设计与高层次综合，北京，清华大学出版 社，2 0 0 0 。 李志坚，周润德，u l s i 器件电路与系统，北京，科学出版社，2 0 0 0 。 曹炜，林争辉，高层综合中一种新的控制，数据流图表示形式，上海交通大学学报， 2 0 0 0 ，3 4 ( 7 ) ：p p 8 9 6 - 8 9 9 p a u l i ng p i e r r e ，k n i g h tpj o l l i l ，f o m e - d i r e c t e ds c h e d u l i n g f o rt h eb e h a v i o r a ls y n t h e s i s o f a s i c s ，1 e e et r a m o nc a d 1 9 8 9 ，8 ( 6 ) ：p p6 6 1 6 7 9 s h a r m aa l o k ，j a i nr a j i v , l n s y n ：i n t e g r a t e ds c h e d u l i n gf o rd s p a p p l i c a t i o n s ，i n ：3 0 “ a c m i e e e d e s i g na u t o m a t i o nc o n f e r e n c e 1 9 9 3 p p 3 4 9 - 3 5 4 w a n gc h i n g y i ，p a r h i kk e s h a b ，h i g h - l e v e ld s ps y n t h e s i s u s i n g c o n c u r r e n t t r a n s f o r m a t i o n s ，s c h e d u l i n g ，a n da l l o c a t i o n i e e et r a n s o nc a d 1 9 9 5 ，1 4 ( 3 ) ： p p 2 7 4 - 2 9 5 b s h a r o u n ，m i e l m a s r y , a r c h i t e c t u r a ls y n t h e s i sf o rd s ps i l i c o nc o m p i l e r s 。i e e e t r a n s o nc a d ，v o l 8 ，n o 4 ，1 9 8 9 ，p p 4 3 1 4 4 7 b h a t t a c h a r y as u b h r a j i ld e ys u j i t b r g l e zf r a n c ，p e r f o r m a n c e a n a l y s i s a n d o p t i m i z a t i o no fs c h e d u l e sf o rc o n d i t i o n a la n dl o o p i n t e n s i v es p e c i f i c a t i o n s ，i n ：31 “ a c m i e e e d e s i g n a u t o m a t i o nc o n f e r e n c e 1 9 9 4 p p 4 9 1 , - 4 9 6 r a d i v o j e v i ci v a n ，b r e w e rf o r r e s t ，an e ws y m b o l i ct e c h n i q u ef o rc o n t r o l - d e p e n d e n t s c h e d u l i n g ，i e e et r a n s o nc a d 1 9 9 6 ，】5 ( 1 ) ：p p 4 5 巧7 y a n gc h i n y u a nj e r r y , m i c h e l id eg i o v a n n i ，a n dd a m i a n im a u r i z i o ，s c h e d u l i n ga n d c o n t r o lg e n e r a t i o nw i t he n v i r o n m e n t a lc o n s t r a i n t sb a s e do na u t o m a t a r e p r e s e n t a t i o n s ， i e e et r a n s 0 nc a d 1 9 9 6 ，1 5 ( 2 ) ：p p l 6 6 1 8 2 l a k s h m i n a r a y a n ag a n e s h ，k h o u r isk a m a l ，a n dj h akn i r a j ，w a v e s h e d ：an o v e l s c h e d u l i n gt e c h n i q u ef o rc o n t r o l f l o wi n t e n s i v eb e h a v i o r a ld e s c r i p t i o n s ，i n ：p m c i c c a d 1 9 9 7 p p 2 4 4 - 2 5 0 l a k s h m i n a r a y a n ag a n e s h ，r a g h u n a t h a na n a n d ，a n d j h akn i r a j ，l n c o r p o r m i n g s p e c u l m i v e e x e c u t i o ni n t o s c h e d u l i n g o fc o n t r o l f l o wi n t e n s i v eb e h a v i o r a l d e s c r i p t i o n s ，i n ：3 5 “a c m i e e e d e s i g n a u t o m a t i o nc o n f e r e n c e 。1 9 9 8 p p 1 0 8 1 1 3 1 2 生堕圭塑奎望查兰堡圭兰堡丝壅 笙= 童堡堡 ( 1 8 】b l u a n gs h ，j e a n gy l ，h w a n gc t ，e t a l ，at r e e - b a s e ds c h e d u l i n ga l g o r i t h mf o r c o n t r o l - d o m i n a t e dc i r c u i t s ，i n ：3 0 “a c m i e e ed e s i g na u t o m a t i o nc o n f e r e n c e 1 9 9 3 ， p p 5 7 8 5 8 2 1 3 申请上海交通大学硕士学位论文第二章高层次综合的主调度算法 第二章高层次综合的主调度算法 我们在第一章中已经了解到，调度的任务就是把高层次行为描述的每一个操 作都安排到一个特定的时间间隔即控制步中去完成，实际上是对欲设计系统进行 时序上的划分。调度决定了整个数字系统中各操作的串行和并行的折衷，近似地 决定了数字系统的性能价格比，是从行为向结构转换的核心部分，是数据通道设 计中至关重要的一步，也是高层次综合中最复杂的部分。 而一个调度算法总是在满足一定限制条件下工作的，这限制条件不但来自 中间数据格式的拓扑结构所决定的各个操作的偏序关系，通常还来自一些人为设 定的限制条件，例如资源限制和时间限制，这些限制实际上就是构造不同调度算 法的启发原则的基础。因此各种算法都有其特别适合解决的一类问题域。而优化 技术本身就是特别针对某一类问题域的进一步的处理原则，它必须结合某一类调 度算法一起使用。特别是由于各种优化技术处理的对象不同，处理的方式也不同， 可能不同的优化算法对原调度系统某种性能指标的作用正好相反，即不同的优化 技术的使用时可能会对调度带来副作用【1 ，所以在研究调度过程中面