（电路与系统专业论文）eda领域中的逻辑优化算法研究.pdf

上海交通大学溥士学位论文 摘要 f 、逻辑综合和优化在电子设计自动化中占有非常重要的地位。多级逻辑优化自8 0 年代中 期开始兴起，到目前为止有相当一部分算法已经成功地用于集成电路计算机辅助设计软件 中。总的来说，这些年来对多级逻辑综合和优化的理解已经取得了很大的进步，但是与成 熟的两级综合和优化相比，这一领域仍有待于进一步的探索。现在，许多计算机科学家和 电子工程师仍然致力于这一领域的研究。每年1 e e e 的国际会议和杂志期刊上所发表的文 章中有相当部分与多级逻辑优化有关。因此，在今后相当长一段时间内这一领域仍然是 研究的热点。u 、 本论文对多级逻辑优化中的一些关键问题进行了深入的研究，研究内容主要涉及以下 四个部分： ( 1 ) o b d d 的应用研究。 ( 2 ) 未知时间环境下的时序分析和验证问题。 ( 3 ) 工艺映射问题。 ( 4 ) 时序重排算法。 其中，每个部分中所研究的具体问题以及通过对这些问题的研究所得到的一些基本结 论如下所述： 由于o b d d 的变量序问题是o b d d 应用中的一个“瓶颈”问题，我们在论文中对这 个问题进行了研究，并且提出了种基于动态计算可观测无关项的变量序算法。与以前算 法不同的是。我们是以可观测无关项中所含最小项的数目来作为原始输入变量的权值。对 标准电路的实验结果表明，我们的算法是有效的。 我们首次将o b d d 应用于组合逻辑电路的测试问题中，从另外个角度对组合逻辑电 路的测试问题进行了研究。陕际上，我们并没有对传统测试算法本身做任何改动，只是巧 妙地利用了o b d d 这种数据结构基于电路中节点逻辑函数的o b d d 表示，传统算法中 的反向回溯过程以及测试矢量集的生成和必要值的确定都可以转换为o b d d 图的运算，从 而可以在一定程度上改进算法的效率。通过对这个问题的研究，我们可以得到这样一个结 论：对e d a 领域中的某些涉及布尔代数运算的问题，当用传统算法难于处理时，我们可以 考虑使用o b d d 的概念，从而有可能克服传统算法中的缺陷，提高算法的效率。 如何在未知时间环境下进行时序分析和验证是近年来提出的一个新问题。在此处，我 们主要提出了这样一种新的思想，即：由于时间环境是未知的。我们先建立一个标准时间 环境，当电路处于其它时间环境时。可以把它看作是对标准时间环境的偏移。因此，基于 这个基本思想，我们提出了组合逻辑电路的延迟特征函数的概念，并且把整个组合电路看 作是一个黑盒子，抽象出电路的延迟行为参数集，这样我们就可以方便地进行未知时间环 摘要 境下的时序分析和验证问题。同时，我们根据提出的延迟特征函数的概念，给出了一种新 的判断时序安全可替换性的方法。通过对组合逻辑电路的延迟特征函数进行编码，并且判 断延迟特征函数之问是否存在相应的蕴涵关系，我们可以比较容易地识别组合电路之间的 。 时序安全可替换性。_ 在对工艺映射问题进行研究时，我们主要是提出了一种新的基于二分图完美匹配的布 r 尔匹配算法。 与原算法不同的是，我们并没有直接去寻找布尔变量之间的匹配。我们的思 i 路是：当两个布尔代数进行匹配时，首先确定哪些布尔变量之间不可以进行相互匹配，然 后将这种关系转变为二分图的匹配关系，最后利用二分图的完美匹配算法进行求解，即可 计算得到所有布尔变量之间的匹配。这样做的一个好处就是，我们可以避免原算法中因乘 积项过多而导致计算时间太长的缺陷。同时，基于d a g m a p 算法，我们给出了一种改进 的基于动态标记的f p g a 延迟优化算法。与原算法相比，动态标记算法使节点的标记号不 再是固定不变的，而是随着后续节点的标记自适应地变化，因而可以使延迟优化更为有效。 与延迟最优化算法f l o w m a p 相比我们的算法计算所用时间减少很多，优化结果也相差 、 不大，因此该算法是可行的。j 1 由于时序重排算法在时序电路优化中具有重要的地位，因此我们对基本的时序重排算 r 法进行了深入的研究。似前的算法必须处理大量的线性约束，因此在一定程度上降低了算 f 法的效率。我们在研究串注意到时序重排算法具有这样一些特点：它本身可以归结为线性 编程问题，并且时序重排变量的数值是一个整数值。于是，我们设想：如果可以事先确定 时序重排变量取值的上下界限。则我们可以明显减少线性约束的个数。基于此，我们提出 了基于变量定界的时序重排算法。通过对一些标准电路的实验表明，我们提出的算法可以 、 大量减少线性约束的个数，从而提高了算法的效率。f 基于以上提出的一些算法，我们都在s u n 3 2 6 0 上用c 语言编写了相应的源代码，并且 将计算结果与以前的方法进行了对比和分析。 关键词：电鼯乌系统，电子设辜百毛化，数字桑赢电路，逻l 曼合和优化，组蕃乏辑 电路，时序逻辑电路 、 i i 上海交通大学博士学位论文 a b s t r a c t l o g i cs y n t h e s i sa n do p t i m i z a t i o np l a y s av e r yi m p o r t a n tr o l ei ne l e c t r o n i cd e s i g na u t o m a t i o n s i n c et h em i d t e r mo f1 9 8 0 s ，m u l t i l e v e ll o g i cs y n t h e s i sa n do p t i m i z a t i o nh a v eb e g a nt oi n t e r e s t m a n y s c i e n t i s t sa n de n g i n e e r s t od a t e ，m a n ya l g o r i t h m sh a v e b e e ns u c c e s s f u l l ya p p l i e dt ot h es o f t o f i c c a d a l t h o u g hg r e a t p r o g r e s s h a s b e e n m a d e i n t h ed o m a i no f m u l t i l e v e l l o g i cs y n t h e s i s a n d o p t i m i z a t i o n ，c o m p a r e dt ot h et w ol e v e ls y n t h e s i sa n do p t i m i z a t i o n ，f u l l e rr e s e a r c ha r en e e d e d n o w ，m a n y s c i e n t i s t sa n d e n 画n e e r ss t i l ld e v o t et h e m s e l v e st ot h er e s e a r c ho f t h i sd o m a i n q u i t ea f e wp a p e r sp u b l i s h e di nt h ec o n f e r e n c e sa n d j o u r n a l so f i e e ec o n c e r um u l t i l e v e ll o g i cs y n t h e s i s a n do p t i m i z a t i o n t h e r e f o r e ，i nn e a rf u t u r e ，t h i sd o m a i ni ss t i l lt h ef o c u so fi c c a d ， i nt h i s p a p e r , w e d i s c u s ss o m ec r i t i c a l p r o b l e m s o nm u l t i l e v e l l o g i cs y n t h e s i s a n d o p t i m i z a t i o n t h e m a i nc o n t e n to f t h i sp a p e ri n c l u d e st h ef o l l o w i n gf o u r a s p e c t s ： ( 1 ) r e s e a r c h o nt h ea p p l i c a t i o no f o b d dt oo t h e r p r o b l e m s ( 2 ) t i m i n ga n a l y s i sa n d v e r i f i c a t i o nt r a d e rn n k n o w u t i m i n ge n v i r o n m e n t ( 3 ) t e c h n o l o g ym a p p i n g ( 4 ) r e t i m i n ga l g o r i t h m t h ed e t a i l so f o u rr e s e a r c ha n dt h er e s u l t st h a tw eh a v ed r e w u p a r es t a t e da sf o l l o w s ： b e c a u s et h ev a r i a b l eo r d e r i n go f o b d di st h e b o t t l e n e c k ”o ut h ea p p l i c a t i o no f t h e o b d d ， w ed i s c u s st h i sp r o b l e mi nt h i sp a p e r w ep r e s e n tan e w a l g o r i t h mf o rt h ev a r i a b l eo r d e r i n go f o b d db a s e d t h ed y n a m i cc o m p u t a t i o no ft h eo b s e r v a b i l i t yd o n tc a r es e t s c o m p a r e dt o f o r m e ra l g o r i t h m o u ra l g o r i t h mc o m p u t e st h en u m b e ro ft h em i d t e r m si nt h eo b s e r v a b i l i t yd o n t c a r es e t sa n dl o o ki ta st h ew e i g h to ft h ep r i m a r yi n p u t i ti ss h o w n m r o u g h t h ee x p e r i m e n t st h a t o u r a l g o r i t h mi se f f e c t i v e w ed i s c u s sh o wt oa p p l yt h eo b d dt ot h et e s to f c o m b i n a t i o n a lc i r c u i t si nt h i sp a p e r w ed o n o tc h a n g et h ec o n v e n t i o n a lt e s ta l g o r i t h mi t s e l fa n do n l ym a k eu s eo fo b d d i nt h i sa l g o r i t h m o u rr e s e a r c hr e s u l t ss h o w ：b ye x p r e s s i n gt h el o g i cf u n c t i o no f e v e r yn o d ei nt h ec i r c u i t sa st h e o b d d i tt r a n s f o r m st h eb a c k t r a c k 、t e s tv e c t o rg e n e r a t i o na n dt h ec o m p u t a t i o no fn e c e s s a r y a s s i g n m e n t si n t ot h ep r o b l e mo ft h eg r a p ho p e r a t i o n ，w h i c hc a ni m p r o v et h ee f f i c i e n c yo ft h e c o n v e n t i o n a la l g o r i t h m b a s e do nt h i sr e s e a r c h ，w ef i n dt h a tw h e nw e c o p ew i t hs o m ed i f f i c u l t p r o b l e m so nt h eo p e r a t i o n so f b o o l e a nf u n c t i o n s ，w ec a na p p l yt h eo b d d t ot h e s ep r o b l e m sa n d o v e r c o m et h ed i m c u l t i e s t h e p r o b l e mo f t i m i n ga n a l y s i sa n d v e r i f i c a t i o nu n d e ru n k n o w n t i m i n ge n v i r o n m e n ti san e w c h a l l e n g ei nr e c e n ty e a r s t os o l v et h i sp r o b l e m ，w ep r e s e n tan e wi d e a i nt h i sn e wi d e a ，b e c a u s e t h et i m i n ge n v i r o n m e n ti su n k n o w n ，w es e tas t a n d a r dt i m i n ge n v i r o n m e n t t h e n ，o t h e rt i m i n g e n v i r o n m e n tc a nb ev i e w e d t h er e l a t i v em o v e m e n to ft h es t a n d a r dt i m i n ge n v i r o n m e n t h e n c e b a s e do nt h i si d e a ，w ep r o p o s et h ec o n c e p to f d e l a yf u n c t i o no fc o m b i n a t i o n a lc i r c u i t s w el o o k u p o nt h ee n t i r ec o m b i n a t i o n a lc i r c u i ta sa b l a c kb o x ”a n da b s t r a c ti t sd e l a yc h a r a c t e r i s t i cs e t l a t e r , b ye m p l o y i n gt h ed e l a yc h a r a c t e r i s t i cs e t ，t i m i n gv e r i f i c a t i o nu n d e ru n k n o w nt i m i n g i n e n v i r o n m e n tc a l lb ee a s i l ym a d e ；a l s o ，b a s e do nt h ec o n c e p to f d e l a yf u n c t i o n so fc o m b i n a t i o n a l c i r c u i t s ，w ep r e s e n tan e wa p p r o a c ht ot h et i m i n gs a f er e p l a c a b i l i t y i nt h i sn e wa p p r o a c h ，w e e n c o d et h ed e l a yf u n c t i o n sa n dj u d g ew h e t h e rt h e r ei sa l l i m p l i c a t i o nr e l a t i o n s h i pa m o n gd e l a y f u n c t i o n s w e p r e s e n ta l li m p r o v e db o o l e a nm a t c h i n ga l g o r i t h mb a s e do nt h ep e r f e c tm a t c h i n go f t h e b i p a r t i t eg r a p hi nt h i sp a p e r c o m p a r e dt ot h ef o r m e ra l g o r i t h m s w ed on o ts e a r c ht h em a t c h i n g b e t w e e nb o o l e a nf u n c t i o n s d i r e c t l y w h e nc o n s i d e r i n g t h em a t c h i n go f t w ob o o l e a nf u n c t i o n s ，w e f i r s ts e a r c ht h ev a r i a b l e sa m o n gw h i c ht h em a t c h i n gc a nn o tb em a d e t h e nw et r a n s f o r mt h i s r e l a t i o n s h i pi n t ot h em a t c h i n go f b i p a r t i t eg r a p h l a s tw ea p p l yt h ep e r f e c tm a t c h i n ga l g o r i t h mt o t h i sb i p a r t i t eg r a p ha n df i n da l lt h em a t c h i n gb e t w e e nt w ob o o l e a nf u n c t i o n s b yd o i n g s o ，w ec a n a v o i dt h em u l t i p l i c a t i o no p e r a t i o n ，w h i c ho f t e nc o s tt o om u c hc o m p u t a t i o nt i m e a l s o ，b a s e do n t h ed a g m a p a l g o r i t h m ，w ep r e s e n td y n a m i cl a b e l i n g b a s e df p g a d e l a yo p t i m i z a t i o na l g o r i t h m c o m p a r e d t ot h ed a g m a p a l g o r i t h m ，w h e r et h el a b e l i n go f n o d e s i sf e d t h el a b e l i n go f n o d e s i sd y n a m i c a l l yc h a n g e da n dt h eo p t i m i z a t i o nr e s u l ti sm o r er e a s o n a b l e c o m p a r e dt ot h ef l o w m 印a l g o r i t h m ，o u ra l g o r i t h m i sm o r ee f f e c t i v ea n dt h ec o m p u t a t i o nt i m ei sa l m o s tt h es a m e t h e n ， o u ra l g o r i t h mi sp r a c t i c a b l e s i n c er e t i m i n gp l a y sav e r yi m p o r t a n tr o l ei nt h eo p t i m i z a t i o no fs e q u e n t i a lc i r c u i t s ，w e d i s c u s st h ep r o b l e m o f r e t i m i n gi nt h i sp a p e r b e c a u s et h e r ei sal a r g en u m b e r o f l i n e a rc o n s t r a i n t s i nf o r m e rr e t i m i n ga l g o r i t h m 。t h ee f f i c i e n c yi s g r e a t l yr e d u c e d t oo v e r c o m et i f f sd i f f i c u l t y , w e f i n ds o m ec h a r a c t e r i s t i c si nt h ep r o b l e mo f m f i m i n g t h ep r o b l e m o f m t i m i n g c a nb ea t t r i b u t e dt o t h ep r o b l e mo fl i n e a rp r o g r a ma n dt h es o l u t i o n sa r ea l w a y si n t e g e r s t h e n ，i f w ec a r lc o m p u t et h e u p p e ra n d l o w e rb o u n d so ft h es o l u t i o n s ，w ec r nr e d u c et h en u m b e ro fl i n e a rc o n s t r a i n t sg r e a t l y b a s e do nt h i si d e a , w e p r e s e n t t h ev a r i a b l eb o u n d i n g r e t i m i n ga l g o r i t h m i nt h i sp a p e r i ti ss h o w n t h r o u g ht h ee x p e r i m e n t st h a to u ra l g o r i t h mc a nr e d u c et h em u n b e ro fl i n e a rc o n s t r a i n t sa n dt h e e f f i c i e n c yc a n b eg r e a t l yi m p r o v e d a l lt h o s ea l g o r i t h m sp r e s e n t e da b o v eh a v eb e e np m g r a m m e do ns u n 3 1 2 6 0w o r k s t a t i o ni nc l a n g u a g e t h ee x p e r i m e n t a lr e s u l t sh a v eb e e nc o m p a r e d w i t ht h er e s u l t so ft h ef o r m e ra l g o r i t h m s a n dt h ea n a l y s i so f t h ee x p e r i m e n t a lr e s u l t sh a sa l s ob e e nm a d e k e yw o r d s ：c i r c u i ta n ds y s t e m ，e l e c t r o n i cd e s i g na u t o m a t i o n ，d i g i t a li n t e g r a t e dc i r c u i t s ， l o g i cs y n t h e s i sa n do p t i m i z a t i o n ，c o m b i n a t i o n a lc i r c u i t s ，s e q u e n t i a lc i r c u i t s 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个入或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 耋辨 1 日期：及比年6 月牛曰 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在_ 年解密后适用本授权书。 本学位论文属于， 不保密日。 ( 请在以上方框内打“4 ”) 学位论文作者签名：墨秉佛指导教师签名： 日期：勘j 净g 月牛日 日期炒年乡 啪躬 1 月汐日 i 本文为美国国家科学基金会( n s f ，u s a ) 资助项目 的一部分，编号为9 6 0 2 4 8 5 ，其n s fp r o g r a mn a m e ：5 9 7 8e a s t a s i aa n dp a c i f i cp r o g r a m 。 本文的研究同时得到我国国家教育部博士点基金的资 助。 对以上的支持和资助谨表感谢。 上海交通大学博七学位论文 1 1 概述 第一章绪论 1 9 5 8 年英国科学家j a c k k i l b y 和r o b e r t n o y c e 制造出世界上第一块集成电路( i n t e g r a t e d c i r c u i t s ，i c ) ，自从那以后，人们的生活发生了巨大的变化。 在集成电路发展的小规模( s m a l ls c a l ei n t e g r a t e dc i r c u i t s ，s s i ) 、中规模( m e d i u ms c a l e i n t e g r a t e dc i r c u i t s ，m s i ) 、大规模( l a r g es c a l ei n t e g r a t e dc i r c u i t s ，l s i ) 以及超大规模( v e r y l a r g es c a l ec i r c u i t s ，v l s i ) 这四个阶段中，应该说，具有重大意义的是大规模和超大规模集 成阶段【林9 3 】。 大规模和超大规模集成电路的问题直接关系到国际上正在开展的新技术革命。在国外， 电子工业特别是微电子工业的水平，是衡量一个国家现代化水平的重要标志。美国的杂志 这样反映他们自己的情况：“半个世纪以来在美国处于统治地位的汽车工业和冶金工业，已 经在8 0 年代让位于电子工业，电子工业这种技术和知识密集型的产业已经成为美国工业发 达的主要标志了” p a u 8 4 。 l s i v l s i 是一种电路，它是电路工程与集成技术相结合的产物。要发展集成电路，主 要涉及到工艺和设计两方面的问题。 微电子技术的发展，一方面使芯片内连接的晶体管数目越来越多，另一方面随着集成 度的提高，系统的体积可以做的越来越小。晶体管的线条和尺寸越细，不但使集成密度大 大提高，而且电路性能也大大改进，主要体现为速度的提高和功耗的降低。从1 9 8 5 年的1 0 微米工艺、1 9 9 2 年的0 5 微米工艺到1 9 9 5 年的0 3 5 微米工艺，现今的集成电路已经发展 到了深亚微米( d e e ps u b m i c m n ) 阶段，国外0 2 5 微米工艺的产品已相当成熟，并出现了o 1 8 微米工艺的产品。表1 1 列举了国际上集成电路工艺及集成电路的发展状况，表1 2 列举了 国际上c p u 的发展趋势，从中我们可以直观地体会一下微电子行业迅猛的发展势头 【f l e 9 4 】。 表1 1 国外集成电路工艺的发展状况 t a b l e1 1s t a t e o f - a r to f t h ei n t e g r a t e dc i r c u i t sa b r o a d 时间 1 9 7 01 9 7 51 9 8 01 9 8 51 9 9 01 9 9 9 集成度 l k4 k1 6 k6 4 k2 5 6 kl m4 m1 6 m2 5 6 m 特征线宽( 1 1 1 1 1 ) 1 285321 20 8o 5o 2 5 硅片直径( i n ) 22 534566 888 1 2 工艺 p m o sn m o sc m o sc m o s 第一章绪论 表1 2 近年来c p u 的发展趋势 t a b l e1 2t h ed e v e l o p m e n tt r e n do fc p ui nr e c e n ty e a r s 1 9 9 41 9 9 51 9 9 6 1 9 9 7 c p up e n t i u mm m x 1 9 9 9 p e n t i u mp e n t i u mp e n t i u mm m xp e n t i u mi i i p e n t i u mi i 特征线宽( b m ) 0 5 o3 5o 3 503 5 0 2 8o 2 5 芯片面积( m m2 ) 1 2 5 9 01 2 82 0 3 9 51 3 1 晶体管数量( m ) 3 33 34 57 5 4 57 5 从以上我们可以看到，如果需要在较短的时间内( t i m e t o m a r k e t ) 完成性能良好( q u a l i t y c i r c u i t ) 的芯片设计，必须应用计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，c a d ) 来管理设计 的复杂性，单纯的手工方式已经远远不能满足设计的要求了。 为了解决v l s i 设计上的复杂性，人们现在已经开始广泛使用抽象( a b s t r a c t ) 和层次化 ( h i e r a r c h y ) 的概念。这样做的一个结果就是，i c 设计工程师从原来的晶体管级( t r a n s i s t o r l e v e l ) 设计转移到了门级( g a t el e v e l ) 及寄存器传输级( r e g i s t e r - t r a n s f e rl e v e l ) 设计。进入 9 0 年代以后，随着硬件描述语言v e f i l o g 以及v h d l 的发展，i c 设计工程师只需要在高层 ( h i g hl e v e l ) 用硬件描述语言来描述所要设计的电路的行为功能就可以了，然后综合工具会 自动产生和优化硬件描述语言所描述的电路。显然，与以前相比，设计人员的任务减轻了 许多 b h s 9 0 】。 从另外个角度来看，为了满足设计人员的需要，v l s i c a d ( 也称为电子设计自动化， e l e c t r o n i cd e s i g na u t o m a t i o n ，e d a ) 软件必须具有多样性以及高效性的功能。多样性意味 着e d a 软件必须可以进行面积优化、延迟优化、功耗优化以及可测性设计等。而高效性意 味着e d a 软件必须在有限的计算时间内产生一个最优化、接近最优化或者至少是一个可以 接受的设计结果。这也是今天e d a 软件设计人员面临的巨大挑战。 在e d a 软件流程中有两个非常重要的阶段，即逻辑综合( 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 基于逻辑综合的设计流程 图1 1 给出了一个典型的基于逻辑综合的设计流程的框图 t r i 8 7 。 2 第一章绪论 图1 1一个典型的基于逻辑综合的设计流程 f i g u r e1 1 a t y p i c a ll o g i cs y a t h e s i sb a s e dd e s i g nf l o w 第一章绪论 从上图我们可以看到，v l s i 的基于逻辑综合的设计流程主要涉及设计规范的翻译 ( t r a n s l a t i o n ) 、电路的优化( o p t i m i z a t i o n ) 以及基于库的映射( m a p p i n g ) 等过程。 1 2 1 行为级模型( b e h a v i o r a lm o d e l i n g ) i c 的行为建模意味着抽象出该i c 要实现的逻辑功能而不涉及它的具体实现结构。行 为模型可以用许多语言来描述，如i s p s b b c + 7 9 、e l l a m p t 8 4 、v h d l i e e e 8 7 以及 v e r i l o g t m 9 1 等。但是，大多数行为模型还是用c 语言来描述，其原因在于c 语言本 身提供了一个较好的编程环境，而且c 源程序的运行速度很快，这对于超大规模i c 的建 模尤其有重要意义。 1 2 2 寄存器传输级模型( r e g i s t e r - t r a n s f e rl e v e lm o d e l i n g ) 从行为级模型到寄存器传输级模型的转换通常可以由人工完成。也可以由行为级综合 工具来完成 p t s + 7 9 】，这一步通常也称为高层综合( h i g h - l e v e ls y n t h e s i s ) 。它所实现的结 构包括一个数据通道和一个控制器。数据通路是由寄存器、功能单元、多路器和总线等模 块构成的互连网络，用于实现数据的传输 h t 8 3 t s 8 6 。控制器通常由硬连逻辑( h a r d w a r e d l o g i c ) 或固件( f i r m w a r e ) 构成，用于控制数据通路中数据的传输。高层综合所产生的硬件 结构一般为同步电路。通常，实现给定行为功能的硬件结构有许多种，高层综合的一个重 要任务就是找出一个满足约束条件和目标集合的、花费最少的硬件结构。高层综合通常包 括编译( c o m p i l a t i o n ) 、转换( t r a n s f o r m a t i o n ) 、调度( s c h e d u l e ) 、分配( a l l o c a t i o n ) 、控制器 综合、结果的生成与反编译等几个部分 d n s 9 ( 1 ) h p 7 8 i w t 8 9 w n 9 0 】。高层综合的结果 是一个未经优化的门级网表形式，它是逻辑优化的起始点。 1 2 3 两级逻辑优化( 1 h o - l e v e ll o g i co p t i m i z a t i o n ) 两级逻辑可以用多种方式来表示，如积之和形式( s u mo fp r o d u c t s ) 、a n d - o r 形式以 ) 及n o r - n o r 形式等。它们一般都用可编程逻辑阵列( p r o g r a m m a b l el o g i ca r r a y ，p l a ) 【f m 7 5 】 来实现，主要用于控制逻辑的综合。p l a 的优点是结构整齐，易于布局和布线，而它的缺 点是有的布尔代数用p l a 实现时，需要的面积与布尔代数中的逻辑变量数目成指数关系， 这也在一定程度上限制了p l a 的应用。但是两级逻辑优化的技术已经相当成熟，因此在多 级逻辑的综合和优化中仍然用到两级逻辑优化技术 b h m + 8 4 。 1 2 4 多级逻辑优化( m u l t i l e v e ll o g i co p t i m i z a t i o n ) 4 第一章绪论 与两级逻辑实现相比，多级逻辑实现通常可以得到速度更快、面积更小的电路，因此 近年来多级逻辑实现已经引起人们广泛的注意 b h j + 8 7 】【b r s + 8 7 】。目前已提出了许多有效 的算法，而且基于这些算法开发出一些成功的多级逻辑综合和优化系统，其中比较有代表 意义的有：m i s 系统 b r s + 8 7 ，它主要是基于代数优化的方法：b o l d 系统 b h j + 8 7 1 l ，它 主要是利用网络中的无关项进行优化，也就是布尔优化：以及s o c r a t e s 系统： b c g + 8 6 】， 它主要是采用基于规则( r u l e - b a s e d ) 的优化。有关多级逻辑综合和优化的详细叙述可以参 考 b h s 9 0 。 1 2 5 酬( t e c h n o l o g ym a p p i n g ) 逻辑综合和优化的结果是一个门级网表( g a t e l e v e ln e t l i s t ) ，它主要由一些组合逻辑门 ( 如n o r 或n a n d ) 和时序元件组成。为了实现该网表，必须用现有工艺库中的门去替代 这些通用的门，这一步通常就称为工艺映射。工艺映射的目标不单单只是门的替换，它必 须保证替换后的电路实现面积、速度以及功耗等方面的最优化。因此，工艺映射问题一直 是人们研究的重点 d g r + 8 7 k e u 8 7 。 1 2 6 物理设计( p h y s i c a ld e s i g n ) 版图是集成电路设计的最后阶段的产物。未来芯片中所有器件及互连线都以二维或准 三维几何图形形式确切定位在版图中。生产过程中所需的掩膜版上的图形来自版图。由于 版图与芯片内部的实际结构及其生产过程的这种直接关系，所以版图设计又称为物理设计。 版图设计通常主要包括布局( p l a c e m e n t ) 和布线( r d u 曲g ) 两个步骤。对版图设计的研究基本 上伴随着集成电路的出现就开始了，所以它的理论和算法相对来说是比较成熟的。有关这 方面的文献可以参考 b c i + 8 7 r s s 8 5 s s 8 4 s j g + 9 u 。 1 2 7 验证( v e r i l i c a t i o n ) 一般来说，验证是在设计的中间过程以及最后阶段进行的，它的主要任务是保证得到 的设计与规范所描述的行为是一致的。 第一个验证问题是设计验证i ：d e s i g nv e r i f i c a t i o n ) 。它的含义是要保证r t l 级实现能够 实现设计规范所描述的逻辑功能。为了实现这一目标通常有两种验证方法：一是基于模拟 环境( s i m u l a t i o n ) 的验证，即在r t l 级的原始输入端施加规范所规定的激励，然后在原始 输出端观察所得到的响应是否与规范一致。这种方法简单而可靠，但是对于原始输入较多 的情况，这种方法所耗费的时间是巨大的 h c 8 9 ：二是采用形式验证的方法( i f o r m a lm e t h o d ) ， 这种方法的特点是把规范所规定的逻辑功能和r t l 级实现的逻辑功能分别用形式语言来描 5 第一章绪论 述，然后验证两种形式语言的等价性 b h s 9 0 。这种方法的优点是可以明显减少验证所需 的时间。 第二个验证问题是实现验证( i m p l e m e n tv e r i f i c a t i o n ) ，它的含义是保证在设计过程中最 后得到的版图与规范所描述的逻辑功能是一致的。关于这方面的算法也是比较成熟的，可 以参考 d m n 8 9 m b 8 8 b r y 8 5 等。 1 2 8 测试( t e s t ) 即使是一个设计上完全正确的电路，经过实际的生产线流片以后而得到的芯片仍然有 可能出现与所设计的逻辑功能不一致的情况。这主要是由于目前的集成电路制造过程本身 存在的一些问题所造成的，例如，芯片内部某部分电路的开路、短路以及制造工艺本身引 起的杂散参数分布使得电位漂移等，从而使逻辑功能与设计要求不一致 b f 7 6 。因此，在 生产出芯片以后，必须对其进行测试，以保证它实现了正确的逻辑功能。 集成电路的测试是一个非常大的研究课题，它主要包括两方面的内容：故障建模和测 试方法学。 故障建模是指把物理故障( p h y s i c a lf