【doc】高层次综合的实有化逻辑图自动生成关键技术的研究

【doc】高层次综合的实有化逻辑图自动生成关键技术的研究 高层次综合的实有化逻辑图自动生成关键 技术的研究 第24卷第4期 2001年4月 计算 CHINESEJ 机 COMPUTERS VoI.24No4 Apr.2001 高层次综合的实用化逻辑图自动生成 关键技术的研究 刘沁楠刘明业 (北京理工大学ASIC研究所北京100081) 摘要研究的逻辑图自动生成系统是"九五"微电子重点科技面研项目的成果"实用化专用集成电路高层次自动 化设计系统——TaIent系统"的子系统,该系统通过对电路网 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 有效的识别与划分,逻辑单元的布局及互连信号线 的布线等,自动生成具有一定逻辑功能且布局美观规范的逻辑原理图.该文重点研究逻辑圉自动生成实用化过程 中的关键技术,将人工智能基于规则的知识表示与形式化算法相结合,提出有效的自动布局方法;应用模式识别理 论和方法解决逻辑图的自动布线问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,提出基于决策树的通道分配方法,并设计一套完整的规则体系;进而文中 给出详细的划分模型,并在此基础上,结合逻辑原理圉的特点实现了两种有效的划分算法:(1)种子生成的构造式 划分算法}(2)造代改进划分算法.其中算法(1)的设计思想主要源于贪婪构造,而算 法(2)则对经典的最小分割划 分算法Kern[ghan—Lin算法进行改进.基于上述研究实现的逻辑图自动生成系统, 能够在很短的时间内生成美观规 范,可读性好的逻辑图为整个系统实用化做出了贡献. 关键词高层次综合,逻辑图,布局,布线,决策树 中图法分类号:TP302 TheKeyTechniquesofAutomaticLogicDiagramsGenerationfor HighLevelSynthesis IIUQin—NanLIUMing—Ye (AStCResearc6C~zter,Beijingtn~ituteTechnology,Beijing100081) AbstractTheautomaticlogicdiagramgenerationsystemdiscussedinthispaperisasubsystem ofPracticalHighLevelDesign(HLD)SystemofASIC——Talent.whichisaproductionof " ninthfive—yearplan"pre—investigatingscientificresearchonmicro— electronicsofnationalde— lense.Byidentifyingandpartitioningthenet— list.placinglogicunitsandroutingsignallines,the SUbsystemcanautomaticallygenerategood— lookinglogicdiagramswithcertainlogiccircuitfunc— tionalinformation.ThekeystoneofourresearchistOsotvethetechnicalproblemsaboutproduc tionuseofautomaticlogicdiagramsgenerationsystem.Combiningtherule— basedknowledgede— notationwithformalalgorithm,weproposeanefficientmethodofautomaticplacement.Thethe— oryandmethodofpatternrecognitionisappliedtosolvetheautomaticroutingoflogicdiagrams andweproposeamethodofehannelroutingbasedondecisiontree.Thewholerulesystemisatso presentedinthispaper.Morem,er,andetailedpartitionmodelisdiscussed. Twoefficienta1g0一 rithmsformultiplewaypartitionoflogicdiagramsarealsoimplemented:(1)Seed—Ex口 ansional— gorithmand(2)herativeImprovementalgorithm.ThemainideaofSeedExpansionalg0rithmis aderivativeofgreedyalgorithmandherativeImprovementatgorithmisamodificati0n0ftradi— tionalmin— cutalgorithm(KLalgorithm)Experimentalresultsshowthatthesealgorithmshave 收稿日期:19990903I修改稿收到日期:200008—24.本课题得到N家"九五科拄攻 关项目(96738010205), 檄电子重点预研项目 (81113)tIN~自然科学基金(69476018)资助.刘沁楠,女.1974年生,博士研究生,研究 方向为逻辑图自动生成拄术, VHDL语言 ASIC自动综音与模拟验证拄术.刘明业一男t1934年生,教授.博士生导师,长期来 从事EDA的教学和科研工作. 4期刘沁楠等:高层次综合的实用化逻辑图自动生成关键技术的研究 I.wtimecomplexityandhighprecision,andtheyhavegoodeffectsinapplicationtBasedonthe ab.veresearchwork,aperfectautomaticschematicsgeneratorhasbeenconstructed.Thetoolis Droventobecorrectandstable,andhaveundergonetensoftestexamples.Itcangeneratenice andnormativelogicdiagramsquickly.Especiallyitcansolvethelogicdiagramgenerationprob— lem0flarge— scalecircuitseffectively.Thiscontributesgreatlytothepracticabilityofthewhole designsystem. Keywordshighlevelsynthesis,logicdiagram.placement?routing,decisiontree 1引言 随着ASIC设计复杂度的增加,高层次的自动 设计方法愈加受到人们的关注.为了增强设计过程 的交互性,有必要为用户提供逻辑图自动生成工具, 以便将高级综合产生的结构网表或者原始的 VHDL结构描述自动转换为相应的逻辑图.该工具 不但可以将设计结果更直观地呈献给设计人员,帮 助他们更好地理解设计,而且它所产生的逻辑图还 可以作为设计文档. 自80年代以来,很多学者对逻辑图的自动生成 进行了有益的探索与尝试.并作了大量的工作:Ku— mar2和Brady--*?解决了逻辑图自动生成系统中的 一 般性问题;Tou0建议对扇入树进行分组并将其 作为结构群;1986年,Chun"提出对元件进行功能 分组聚类以提高逻辑图的可读性….这些工作奠定 了逻辑图自动生成理论与方法的基础,并勾画出系 统的基本轮廓.80年代中后期,人们将逻辑图自动 生成的算法应用到各自的系统实现中,相继出现了 一 些实用系统:比较典型的有Autodraitn一,ASG_6], SPARH-以及HEREsY等等. 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 前人的工作,可 以看出:由于研究逻辑图自动生成的困难在于它的 最优 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 是主观的,未明确定义的,优化目标难于 归纳,更难于数学化,因而目前尚无一个尽善尽美 的方法.本文对解决上述问题的方法进行研究,总 结出一套启发式与算法式相结合的有效布图方法, 并在此基础上,研制开发了面向高层次综合的逻辑 图自动生成系统,该系统能够将高级综合以及工艺 映射的结果迅速转换为逻辑图,生成的图形布局合 理,走线归整有序,符合电路设计人员的阅图习惯. 2系统结构 整个系统的设计包括数据预处理,自动布局,自 动布线,自动划分,图形的输出与管理等相对独立的 过程,其中自动布局,布线以及划分是系统的核心 逻辑图自动生成系统结构如图1所示. 图1逻辑图自动生成系统结构图 3自动布图 从实现方法来看,逻辑图自动生成的技术途径 主要有两条:一条是基于形式化算法的方法.它选择 某个参数(譬如线的交叉点数,线长度,线拐角数等) 作为评估图形生成质量的重要指标,并以此作为算 法的优化目标,采用动态规划,模拟退火等算法求 解;另一条技术途径是利用人工智能的方法解决问 题,采用基于规则的专家系统,典型的如文献[9,lO] . 由于将逻辑图自动生成近似为最优化问题采用形 式化算法解决包括的判据以及优化目标很多,而某 些对于图形美观性的评估很难用数学方式形式化表 示,算法难以顾及多数优化目标,因此采用这种方法 生成的逻辑图在布图质量上不能达到用户要求;而 专家系统尽管可以很大程度地提高图形的美观性, 但它漫长的处理时间令人难以忍受.在系统实用化 计算机2001盎 阶段这两种方法都不适用.另一方面,在逻辑图自动 生成过程中,既包含确定性问题(如元件列定位),也 存在不确定的问题(如布局调整).对于前者,采用形 式化的算法进行处理比较适宜,而对于不确定问题, 基于知识的方法较优.基于上述原因,本文采用算法 与基于规则的启发式方法相结合的布图策略,它弥 补上述两种技术途径的缺陷,能够在较短的时间内 生成美观规范的逻辑图. 3.1自动布局技术 尽管人们对物理布局问题中所涉及的布局布线 技术的研究已经日渐成熟,但是这些技术还很难真 正应用于逻辑图自动生成领域.这主要是由于逻辑 图并不关心线的长度以及布局的密度,它所追求的 是图形的美观,规整以及良好的可读性本系统在布 局过程中,遵循以下几个原则; ? 保证整个图形均匀,对称. ? 保证信号流的流向一致,通常为由左至右. ? 保证功能相近的元件位置相邻. ? 尽量为布线提供方便. 为实现上述目标,布局过程主要由三个步骤完成. Step1确定各元件在整个图形中所占的列位置. Step2依次处理每一列的元件,根据元件之间的连接 关系以及元件本身的特征确定它在该列中的具体行位置. Step3.对上述布局结果进行优化.即对那些没能满足 设计目标的元件位置进行调整. 第1步确定元件列位置由列定位算法完成.该 算法的设计着眼于目标2,即保证信号流的流向自 左至右流入,这符合电路设计的习惯.具体而言,对 于每条信号线,其起始端元件的列号小于终止端元 件的列号对于每个元件而言,它的所有输入端元件 的列号都应当小于该元件的列号,而其所有输出端 元件的列号都应大于该元件的列号.但由于在时序 电路中通常都存在反馈线,不能完全按照上述算法 进行布局,需要进行反馈线的识别与处理,对于内反 馈将它们安置在同一列的相邻位置,而外反馈则将 它们放置在同一行,为此本文提出基于反馈线识别 的列定位算法.该算法的主要思想是在确定每个元 件列位置之前,首先要判断其是否位于反馈环上.如 果是,则进行相应的反馈处理,否则按照元件之间的 输入输出关系确定列号.上述处理方式使列定位算 法具有较强的通用性,无论是对组合电路还是对时 序电路该算法都能够有效地进行布局.对反馈环路 的识别由递归算法完成,详细过程参见算法1. 算法1.反馈环路的识别算法 /*元件J是元件i的一个输入端元件,0(r)为元件i 的扇出元件集合,test为递归标志,视值为0,如果元件i和元 件之间是内反馈,返回一1;如果是外反馈,返回1;如果元 件i和元件J之间不存在反馈环路,返回0?*/ jreedbaekidentify(i,J) { //如果元件i的直接输出与其直接输入相同,则为 内反馈 if((test~一0)&&(,?0"))) return(一1); //元件i没有扇出,不存在反馈环路 if(0(i)=一圣) return(0); test一+} //依次处理各扇出元件 forallb?0(i)do { lf0=一J) f 建立反馈循环链表CYCLIST,并将J添加 至该链表中; retorn(1)' if(bECYCLIST)//如果6属于循环链,则处理 i的下一个扇出元件 continue; e[se //递归调用 RET=feedbackidemify(b,J); if(RET一一1) break; }//else } endlor; if(0(z)==雪上述情况均不瞒足) return(0){ returI1(RET)' 该算法实现的过程类似于多叉树的搜索,搜索 采取深度优先的顺序.搜索之后产生一条循环链表, 位于该循环链表上的元件应处于同一行位置.递归 的回溯条件为搜索过程所产生的链表成为一个封闭 的循环链表或者元件无扇出. 布局过程的第2步,确定元件的行位置,即将同 一 列的元件在纵向位置上进行排序.在设计行定位 算法时注重元件之间的连接关系,使有直接连线关 系的元件放在临近位置,并将图形的均匀对称作为主 要的目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ,从而使得布局更为美观,整齐.详细算 法参见文献厂l8].采用上述行定位算法,则连接关系 如图2(a)所示的电路图布局之后为图2(b)所示. 4期刘沁楠等高层次综合的实用化逻辑图自动生成关键技术的研究 (a) 图2行定位算法布局结果 以上布局策略将二维布局问题合理地转化成一 维布局问题,不但简化了问题的复杂度,而且在一定 程度上提高了系统的效率.但由于逻辑原理图的复 杂多样性,单纯由行,列定位算法布局完成的图形很 难尽如人意,因此需要通过第三个步骤,调整布局以 达到最佳的布局效果.由于该阶段涉及许多不确定 性因素,因此基于知识的方法更适合于解决问题.采 用知识控制调整过程,不仅可以提高布局优化的效 率,而且能够获得理想的结果.知识的引入取决于我 们对图形美观性的理解.为此,我们观察大量手工绘 制的逻辑原理图,从中提取启发知识.知识大体分为 两类:事实与规则.事实主要包括调用上述布局算法 (行,列定位算法)产生的初始事实以及布局调整阶 段调用某些形式化算法后动态生成的事实.而规则 是指依据现有的事实调用某一优化算法的知识.在 布局调整过程中,规则的选择多种多样.譬如 规则1. 圈 规则2. ….口] 规则3 Dl厂=]lL1 规则的实用性以及有效性无法用具体的参数评 价,同时规则之间还有可能相互制约,这就要求我们 在实现的过程中综合考虑,统筹安排.知识的引入使 得布局调整过程灵活而且高效:首先,规则库易于扩 充.规则的产生源于对当前事实的判断,当有新事实 产生时,很容易向规则库中增添新规则.其次,依据 规则设计的布局调整算法"有的放矢",针对性强且 效果显着. 3.2自动布线技术 本系统采用通道布线的方法,但与传统意义上 的通道布线方法有所不同.它充分结合逻辑图自身 的特点,在通道分配过程中,采用类似于模式识别中 的"模板匹配"的方法进行处理,而对于轨道分配坝4 采用知识制导的方法. 3.2.1基于决策树的通道分配方法 借用模式识别理论中的有关概念,通道分配过 程中需要解决的问题可以表述为:从特征空间(输入 网表中的信号线的各方面特征)到决策空闻(基本线 型库)的映射.根据这一问题的特点,可以采用决策 论方法进行处理,假定每条信号线都含有?个特 征.,个特征的集合可以表示为一个向量,或者 ?维特征空间n中的一个点.通道分配的任务就 是把特征空间中的每个可能的向量(或者点)指定到 一 个适当的模式类(基本线型库中的某种线型),并 用该线型代替信号线.可以用"判别函数"对问题加 以公式化.设,一,‰表示基本线型库中的m 种线型(模式),并且令X一?,",]表示信 号线的特征向量,其中.表示第i个特征的度量, 用D(x)表示与(J一1,2,….m)相联系的判别函 数.那么,如果特征向量所表示的信号线属于to, 表示的基本线型,记成?,那么对于所有的 ?,则必须满足 D()>D,(),i,j--1,…,m,ivaj. 具体而言,实现通道分配的处理步骤包括: (1)基本线型库的建立.模式类(基本线型)的 特点在某种程度上决定着模式匹配所采用的方法. (2)信号线特征的提取和选择.主要包括信号 线类型,信号线始端元件与终端元件的类型以及相 对位置关系,输入/输出端口等方面的特征. (3)模式判别(分类决策).将特征空间中的点 (信号线)判别为某一模式类(基本线型). 借鉴模式识别的方法进行通道分配,选择合适 的模式判别(分类决策)策略非常重要.在模式识别 理论中,根据问题的具体特点,可以选择不同的判别 函数和实现方法.本文采用决策树(或称多级分类 器)的处理方法,这主要是由于决策树非常适合解决 多类问题的识别,它可以把一个复杂的多类别分类 计算机 问题转化为若干个简单的分类问题来解决,并不企 图用一个决策规则将多个类别一次分开,而是采用 多级的形式,使分类问题逐步得到解决.如果用T 表示决策树,那么,一个决策树丁对应于特征空间 的一种划分,它把特征空间分成若干个区域,每个区 域对应一个模式类. 根据问题的特点,信号线的特征信息以及基本 线型库的组织结构,可以构造如图3所示的分层决 策树.假定,样本集盖是输入网表中所有信号线的 集合,指标集j由基本线型库的顺序标识号构成,那 么可以按照以下方法构造决策树: (1)选择信号线的某一特征作为决策树根结点 使用的特征.这里选择了"是否为触发器类型"作为特征,相应的决策规则为 rule1:一l,一{IlI?I,…,I,. 其中,将基本线型库中的线型分为触发器(内反馈) 和非触发器两类,J,(1--<im)是同类线型的集合; (2)建立决策树的下一级图中,分类选择信号 线两端元件的列位置关系以及是否为内部信号线作 为特征,相应的决策规则为 rule2:x一,. =Ijj…,. J. 根据第一级分类后所处分支的不同,第二级决 策规则有若干个,但数目不太于m. (3)重复步骤(2),继续选择特征作为下级决策 的分类特性,直至信号线仅与基本线型库中的某一 确定线型相匹配.图中,对于特殊信号线(如触发器 类信号线)经过第二级分类便可达到这一目的.而多 数信号线则需要经过多次分级才可确定匹配目标. 本算法中,最多经过六级可到达目标.第三级分类特 征是输入端口的端口类型,第四级分类特征是信号 线两端元件的列位置关系,第五级,六级的分类特征 是信号线两端元件的行位置关系. 图3是用于通道分配的分类决策树,图中S表 示信号线的起始端元件,E表示信号线的终止端元 件,inpin表示信号线输入的端口,Column()表示元 件i的列号,Row(i)表示元件i的行号. 内部信号线 ? 一 \内都信号线/\……… 尸E7l inpin为 控制端口叭由由 一Column(3)~.1…,s'一?图3用于通道分配的分类决策树 系统中每种线型对应一个特定的通道分配算法, 因此一旦为信号线匹配确定的线型,那么该信号线所 占据的通道也将随之确定,基本线型库中的线型覆盖 了逻辑图中可能出现的所有走线类型,由此不难看 出,上述过程实际上是一个约束的过程.通过这种约 束,不但有效避免了迂回走线的存在,同时也为通道 分配提供了便利,很大程度上提高了系统的布线 速度. 3.2.2轨道分配 对于轨道分配,本文采用基于知识的方法予以 \辨 \ll >?( ES )//f% 4mm 4期刘沁楠等:高层次综台的实用化逻辑图自动生成关键技术的研究 解决.这允许我们直接从图形的美观性出发,有效减 少连线之间的交叉和拐角.在轨道分配阶段,遵循的 规则(启发知识)共l2条,分为两类,分别适用于垂 直通遭和水平通道,受篇幅所限.本节给出部分 规则. 规则4.在屏幕坐标系下,假设信号线A的起 始点坐标为(x,Y),终点坐标为(x…),信号线 B的起始点坐标为(xY,),终点坐标为(x…Y), 如果y<yy血<yY一YX<X&.则 MAXTRACKNUM/2(Track(A)%Track(B). 规则5.在屏幕坐标系下,假设信号线A的起 始点坐标为(x,Y一,),终点坐标为(x),信号线 B的起始点坐标为(xY,),终点坐标为(xm,Y), 对于垂直通道,如果y>y,y&>y岛,Y<y则 Track(B)<Track(A)<MAXTRCK?U/2. 规则6.在屏幕坐标系下,假设信号线A的 起始点坐标为(x…Y),终点坐标为(x,y), 信号线B的起始点坐标为(x,Y),终点坐标为 (x,YB.),如果y山<yy<y,x<x曲,则 MAXTRACK?UM/2<丁口cle(A)<Track(B). 设MAxAcK?uM表示通道内的轨道总 数,TRACK(i)表示为信号线i分配的轨道.虚线框 代表一个水平通道或者垂直通道.则上述三条规则 可由图4示意. (a)规则4 Y^) r) (b)规则5(c)规邱l6 图4轨道分配规则示意图 采用上述布局,布线算法生成的逻辑图连接关 系明确,布局美观合理,走线清晰.符合用户的阅图 4自动划分技术 习惯.图5所示为由表达式求解的综合结果自动生 成的逻辑图,并对图中5l号元件局部放大显示. 图5系统用户界面以及运行示倒 划分是层次式设计的一个重要过程.它在逻辑 图自动生成中的作用主要是降低大规模电路的布图 复杂性,同时增强图形的可读性.如果采用图的顶点 表示电路中的元件,图的边表示电路中的连线,那么 电路的划分问题就相应转化为图论中图的最优K 计算机 划分问题.在实际问题中,划分都有各自的目标函数 或约束条件.在逻辑图自动生成领域中,通常考虑以 下约束条件: ? 划分元数目的约束.即划分后所产生的划分 子集的数目不超过某个上限值. - 划分元容量的限制.划分产生的各个划分子 集中的元件数目不超过某个上限值. ? 划分元外部连线的限制.尽可能使划分元的 外部连线数最少,以保证各划分元的相对独立性 ? 布图的限制.划分时还应考虑到有利于布 局,布线等因素. 人们已经证明,面积约束下的图划分问题是 NP困难问题,它的计算复杂度极高,在实用规模上 不可能求出精确最优解.因而迄今为止,人们提出 的划分算法都是启发式的或者基于某种理论的.由 于划分问题无法在有限时间内保证找到最优解.因 而通常利用一些相对简单的方法快速构造一个初 始划分,然后再利用启发式算法对其进行迭代改 进.针对划分算法的上述特点,本文提出了如下划 分策略; 1.对于较大规模,复杂的设计电路或者当用户 对系统的快速响应有较高要求而对划分结果要求不 高时,利用构造式划分算法快速求解. 2.对于中小规模的设计电路或者用户对划分 结果有较高要求的情况.利用迭代改进式划分算法 求得最优解或准最优解. 本文遵从实用,通用和优化的原则,结合逻辑 图的特点,实现了多种划分算法,并在实际应用中 取得了良好的效果.本文重点讨论其中的两种划分 算法. 4.1种子生成构造式划分算法 该算法由电路网表中的一个或者若干个种子结 点(电路元件)开始,从种子结点的邻近结点中找出 与之强连接的结点,逐步结群成相互独立的种群.其 具体划分过程为:如果对于包含个元件的电路 H={.E),要构成划分H一(,.V-.,V), 同时满足: ll—,I一I(i) lI=一(一1)m(2) 其中m与满足关系式一rn/m. 可以分成K—I步完成,每一步确定一个结点 子集(即一个划分).在每一个结群的形成过程中 (1,一1),又可以细化为以下两个步骤: Step1.选择结点作为种子结点选择种子时应遵循 以F原则: (i)当J一1时,种子结点满足 lN(v)一max(N(v.)),1?z(3) (ii)当j>1时,目标函数为 L max(IN(v,)1Cv)(4) V o 一 6~" 其中N(v)表示与元件相连的线网集合,IN(v,)I 表示集合N(.)中的元素个数,Cvm表示结点与 之间的连接,如果此时有多个结点满足式(4), 则需要考虑另一个目标函数: rl rain??Cv(5)一J,--]. Step2.向V中添加新结点直至满足V.1一.结点. 添加时遵照以下优先级设置: 优先级1:结点的?Cv值越大,优先级别越高.E 优先级2:在优先级i相同的情况下,结点的 ?Cvovo值越小.优先级别越高.= d ? 该算法的形式化描述详见文献[19].种子生成 构造式划分算法的划分速度较快而且易于实现,但 由于结群的搜索空间通常是某个结群的相邻单元, 因而缺乏全局观点,本文通过施加适当的约束并设 置选择的优先级别,有效改善了划分的质量,而且 由于目标的选择比较简单,不会影响算法的速度. 实践证明,该算法在质量和效率上能够达到良好的 平衡. 4.2迭代改进式划分算法 迭代改进式划分算法注重对一个已知的划分 结果进行迭带改进,它首先从初始划分开始.通过 在划分子集间移动目标来改进结果.由Kernighan 和Lin提出的划分算法(KL算法)是划分领域中 第一个有效的启发式算法,此后的算法大多是在该 算法的基础上改进,譬如文献[14,I5].它通过在两 个规模相同的划分子集间交换结点组从而达到最 大程度的改善.它将交换的增益定义为两个子集台 之间的公共线网(割线网)的减小.KL算法每次在 两个子集合中选取一对结点(,)进行交换,其中 满足?V,口?,且gain()值最大.交换 之后的元件,将其锁定,调整造价,然后从剩余元 件集台中再挑选一对增益最大的元件进行交换, 再锁定,调整造价…,直到所有元件都锁定为止. 累计每次交换的增益.并将累计增益值最大的一 组结电对进行实际的交换.然后以当前的划分结 果作为下次选代改进的初始划分.整个算法的结 束条件是累计增益值为0.由于此过程可以从任意 4朝刘沁楠等:高层次综合的实用化逻辑图自动生成关键技术的研究 的初始划分开始重复进行.这样就能从生成的众 多划分中挑选晟优解,找到接近全局最优划分的 机会就增多. 该算法可以将二划分扩展成多块划分,即为后 来人们经常采用的递归二划分的方法.尽管这种多 块划分方法取得了一定的成功,但与直接求解图的 K划分的方法相比,存在着很大的限制.首先,采用 递归二划分的方法在本质上很难直接优化全局目标 函数,这是由于全局目标函数依赖于对所有K个划 分子集的直接的观察分析.而不是通过递归这种间 接的方式.其次,直接的K划分方法能够在加强平 衡约束的同时依旧保持充足的探测可行解空间的能 力.因此,直接对电路进行多块划分可以潜在产生更 好的划分结果.基于上述原因,本文采用改进的KL 算法直接对逻辑原理图进行多块划分,其算法描述 参见算法2. 算法2.改进的KL算法 GAINSUM--一;//为累计增益赋初值 构造初始划分,P,P",P}; 计算割线网CUTSIZE; whi(GA孙>O) for元件集合中的每十元件cdo for每十划分子集do 计算元件c向划分子集P移动后生的移动 增益; endfor; endfar; D=0: while(1ock—n"<元件总数) 选择将移动的元件MCi? if(MCj—NULL) f 保存移动元件MC,同时锁定MC; 更新与MC相关元件的移动增益毋;? ?一"+一} 累计GAINSUM~ lf(GAINSUM>0) 移动元件t更新CUTSIZE}@ 对所有元件解除锁定; ) 由于是直接的多块划分,如果仍然采用KL算 法中一次交换一对结点的移动策略,那么当前解的 邻域解空间就会达到0(IV1),这将使算法的计算 量过大从而降低算法的实用性.本文采用Fiduccia 和Mattheyses"提出的每次移动一个元件来代替 一 对结点交换的思想,即通过将一个元件从当前划 分子集移动到目标划分中进行迭代改进,这时解的 邻域解空间就会减少为0((一1)×ii).这样移 动增益也需要做相应的调整.设结点?由划分子集 移动到划分子集则移动增益定义为 gain:?q一?c?V(6) . EVf'. EV' 其中表示结点"与结点乞.之间的连线造价.式 (6)中的第一项表示结点"与划分子集之间的 连线造价和,第二项则是与划分子集之间的 内部造价IC. 对于算法2的?:选择移动元件MC而言,MC 应当是当前移动增益最大的元件.此外,选择时还需 要满足一个约束条件,即元件由划分子集移 动到划分子集之后,对于源划分和目标划分应当 满足: L(V)W()U(V),L()W(V)U(V). 给定电路,其总容量定义为=>:,其中 f W表示元件上的权值.另外为每个划分子集 定义一个容量函数W(.)=:,那么显然有 ?. ?一?W(V).1=I L(V)和U(V)分别为划分W(.)的下界与上 界.其定义如下: L(.)!I(1)/kI,U()=i(1+)/k『. 此处为浮动系数,O<<1_引入非常重要,正是 由于划分子集中允许存在这种容量误差,才使得算 法2中的单元移动成为可能.同时,浮动必须受范围 的限制,否则可能会令所有的元件都移动到一个划 分集合中去.如果划分之后各子集容量基本相同,那 么就称该划分是平衡的.通过实验发现,d的值越 大,则算法的搜索空间越大,划分结果越好,但收敛 较慢,而且对于划分的平衡损失较大.我们在实现过 程中,将值作为输八参数由用户控制选择(缺省 d:O.1),增强算法的灵活性. 对于算法2的?:更新移动增益,本文给出以下 两个性质. 性质1.元件q移动之后,只需要更新邻 居结点的增益. 性质2.元件q由划分子集移动到之 后,如果的邻居结点存在于划分子集或者 计算机2001拄 v当中,则需要更新元件与所有划分子集之间的 移动增益,否则,只需更新与划分子集,以及 与之间的移动增益. 我们在文献[19]中给出这两个性质的详细证明 过程.基于上述两个性质,算法在更新元件增益时可 以避免大量不必要的计算,从而有效提高算法的实 现效率.算法2经过最内层循环实际上确定了一组 移动元件序列?…,c),,但这些元件不 会都发生移动,而是从中确定一个累计增益值最大 的元件序列进行实际的移动.需要注意的是,上述集 合中元件的次序是确定的(这是由于元件的选 择依赖于移动序列(c_.fh,…,q),算法在选择移动 元件序列时也必须严格遵照此顺序.显然,如果元件 的移动增益为g,,那么选择移动元件序列的目标 函数为 maxgl,1?(7) lt 满足上式的值即为算法第?步中实际移动的 元件个数.移动之后,利用下式更新CUTSIZE: CUTSIZE—CUTSIZE—max>:g.(8) 整个算法的结束条件为:移动任何一组元件都 不能产生正增益.在上述算法的实现中我们采用时 间复杂度为线性的桶排序方法维护元件的移动增 益,由于采用链表的实现方式,移动增益值发生变化 所引起的再排序操作的时间复杂度为常数,其详细 结构可参见文献[13].该算法在一次移动中的时间 复杂度为0(nk×l1).其中表示与元件相连的 旦 线网集合的最大值,即-.max>fN(v)l,表示 l一1 划分的块数. KL算法的有效性取决于它能否尽快地发现最 佳的可移动单元,并加速单元移动的过程这种方法 虽然求解质量相对较高,但对初始划分的依赖性很 强.通常KL算法采用随机构造的方法创建初始划 分.一般情况下初始划分的质量很差.而本算法则同 时允许采用种子生成构造划分算法构造一个相对较 优的初始划分,这样不仅可以使算法快速收敛,而且 在很大程度上提高了求解的质量表l给出该造代 改进划分算法的运行结果,其中以划分子集的个数 作为划分参数,并将其设定为30.由该表可以看出, 系统的运行时间基本呈线性增长. 表1系统自动划分'剧试结果 此外,本系统还实现了模拟遇火,种群合并等多 种逻辑图划分算法,用户可灵活选用.受篇幅所限. 本文不作详细讨论 5结论 本文重点讨论逻辑图自动生成实用化过程中的 关键技术,包括自动布局,自动布线以及自动划分. 系统采用算法与基于规则的启发式方法相结合的布 图策略,考虑到系统的普及推广,我们采用开发环境 为PCPentium166,Windows98或WindowsNT,开 发工具选用Visuallc++5.O.实例测试表明,本系 统与国外的同类产品相比具有一定的竞争力,突出 表现在以下两方面: (1)布局合理,走线清晰 在设计布局算法时,本系统以元件之间的逻辑 连接关系作为布局的主要依据,将布局的对称性和 美观性作为算法的启发知识;布线阶段则以避免连 线重叠,减少连线之间的交叉和拐角作为布线算法 的主要目标函数.采用上述算法生成的逻辑图连接 关系明确,布局美观台理,走线清晰,符合用户的阅 图习惯. 4期刘沁楠等:高层次综台的实用化逻辑图自动生成关键技术的研究429 (2)成图迅速 对于一个实用化的系统而言,快速响应至关重 要.本系统不仅在算法设计上充分考虑到这点.井在 实现过程中采用优化的数据结构.因此,无论是布 图,划分,还是图形的滚动刷新,其运行速度都非常 快;对于规模较大的设计电路,也能够在合理的时间 范围内产生结果.因而从运行速度方面考虑,本系统 完全能够与国外的同类产品相媲美,达到了系统实 用化的要求.部分实例运行情况参见表2实例运行 结果一览表. 表2实例运行结果一览表 参考文献 lKumarAalAutomaticgenerationofdigitalsystem schematicdiagrams.1EEEDesignandTestMagazine,1986 88—65 2BradyHN,Jr.Automaticgenerationofschematicdiagrams [PhDdissertation].UniversityofTexas,Austin.1982 3Tou10.Automaticformattingoflogicsehamatits[MSdisseT— tation]MassachusettsInstituteofTechnology,1984 4ChunRK,ChangK,McNam~LP,VISl0N,VHDLin— ducedschematicimagingonnetlists.In:Proc24thDesign AutomatJonConfefence,1987.436—442 5Ma~wskiMAega1.Autodraft:Automaticsynthes~ofcJmuh schematic~In:Pro=lnternationalConfeTenc~ComputerAided Design.LosAlamkos:IEEEComputerSocietyPress.Califor tfa,l986435—438 6JehngYS,ChenLG,ParngTM.ASG;Automaticschemat一 】generatorIntegration,TVLS1Journa1.1991,l1:Il一27 7Frez~StephenT,LevJtanStevenPSPAR}Aschematic placeandroutesystem.IEEETransComputer-AidedDesign ofIntegratedCircuitsandSy3t~ms,19g3,12(7)=956—972 8ChiuehTzlCker,HERESY:Ahybridapproachtoautomatic schematicgeneration.DepartmentofElectricalEngineering andComputerScience,University0fCalifornia,Berkeley. CA94720.1991 9AhlstromM"a1.HAL:Aheuristicapproachtoschematic generation.ProceedingsofICCAD,1983.88—86 10SuinkelsGM?HalerLSchematicgenerationwithanexpert systemIEEETransComputerAidedDesign,1990,9(12): I289一I306 nFuKS.TApplicationofPatternRecognition.Beijing. PekingUniversityPress,1990(in?