（电路与系统专业论文）用于VLSI布局的计算智能方法研究[电路与系统专业优秀论文].pdf

电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 摘要 ( 作为电子信息产业发展的核心和基础，集成电路技术正迅速地向着更高 集成度、超小型化、高性能、高可靠性的方向发展。在v l s i 设计流程中，物 理设计是既关键又复杂的一步，而布局又是物理设计中最重要的一步，布局的 诸多问题都是n p 完全问题，需要启发式算法来求解。随着v l s i 集成度的迅 猛提高，寻求有效的优化算法应用于布局问题，以提高布局质量和速度已成为 当务之急。产 本文主要研究用于解决v l s i 布局问题的计算智能方法，在总结概括了当 前主要的布局优化算法的基础上，引入了禁忌搜索算法和模糊禁忌搜索算法， 并用于求解v l s i 布局问题。 禁忌搜索算法是一种可广泛用于各种优化问题的思想框架。许多文献也 都证明它在时间和性能上优于其他一些算法，在诸多组合优化领域中显示出了 强大的寻优能力，并以其较高的求解质量和效率得到人们越来越多的青睐。本 文将其引入，用以解决v l s i 门阵列布局问题，与遗传算法比较，在求解质量 和速度上都取得了优于遗传算法的结果。 然而，禁忌搜索算法的求解性能严重地依赖于算法的一些参数，它们又 大都在算法运行中起着指导算法前进的作用。这些参数都是凭经验选取的，而 且这些参数在算法运行过程中始终保持不变，这样的策略在很多情况下都不是 很有效。因此，我们发展了一种新的算法模糊禁忌搜索，它引入一个模糊 系统来控制禁忌搜索算法的参数取值。性针对v l s i 门阵列布局问题的应用 中，用当前解的优劣程度和非优化迭代的次数来控制邻域的产生，计算机仿真 结果表明该算法具有很好的寻优性能。l 产 关键词：v i s i 布局、随机优化算法、禁忌搜索算法、模糊系统 lj) 摘要 a b s t r a c t a st h ek e r n e la n df o u n d a t i o no ft h ei n f o r m a t i o nt e c h n o l o g y ( i t ) ，i n t e g r a t e c i r c u i t ( i c ) h a sb e e nd e v e l o p i n gr a p i d l yf e a t u r i n gl a r g e ra n dl a r g e ri n t e g r a t i o ns c a l e ， m o r em i n i a t u r i z a t i o n ，h i g h e rp e r f o r m a n c ea n d r e l i a b i l i t y t h eh i g h e r t h ec o m p l e x i t y o ft h ei cd e s i g ni s ，t h eh i g h e rt h ep e r f o r m a n c er e q u i r e m e n to ft h ee d at o o l si s p h y s i c a ld e s i g n i sa c o m p l e xk e y l i n ko ft h ev l s i d e s i g nf l o w a n d t h ep l a c e m e n ti s t h em o s ti m p o r t a n ts t e pi nt h el i n k m o s tp l a c e m e n tp r o b l e m sa r en p c o m p l e t e ， w h i c hc a no n l yb es o l v e db ys o m eh e u r i s t i ca l g o r i t h m s a st h er a p i di n c r e a s i n go f t h ev l s i i n t e g r a t i o ns c a l e ，i tb e c o m e su r g e n t t of i n de f f e c t i v ea l g o r i t h m sf o rs o l v i n g p l a c e m e n tp r o b l e m s ，a i m i n ga ti m p r o v i n gt h ep l a c e m e n tq u a l i t ya n ds h o r t e n i n gt h e c o m p u t a t i o n t i m e t h em a i nw o r ko ft h i sd i s s e r t a t i o ni sl i e so na p p l y i n gi n t e l l i g e n ta l g o r i t h m st o s o l v et h ev l s ip l a c e m e n tp r o b l e m s a f t e rab r i e fr e v i e wo fc u r r e n tp l a c e m e n t a l g o r i t h m s ，w ei n t r o d u c et w oa l g o r i t h m s ，w h i c ha r e t a b us e a r c h ( t s ) a l g o r i t h ma n d f u z z y t a b u s e a r c h ( f t s ) a l g o r i t h m ，t os o l v et h ev l s ip l a c e m e n tp r o b l e m s t si saf l e x i b l ef r a m e w o r ko fav a r i e t yo fs t r a t e g i e so r i g i n a t i n gf r o ma r t i f i c i a l i n t e l l i g e n c ea n d i st h e r e f o r eo p e nt of u r t h e ri m p r o v e m e n t i th a sb e e ns h o w nt h a tt s i s s u p e r i o rt om a n y o t h e ra l g o r i t h m sb o t hi nt h et i m er e q u i r e dt oo b t a i nas o l u t i o n a n di nt h eq u a l i t yo ft h es o l u t i o no fm a n yo p t i m i z a t i o np r o b l e m s i tb e c o m e sm o r e a n dm o r e p o p u l a r i no p t i m i z a t i o na l g o r i t h m s w ed e v e l o pat sa p p r o a c hf o rs o l v i n g t h ev l s i p l a c e m e n tp r o b l e m si nt h i sd i s s e r t a t i o n t h ec o m p u t e rs i m u l a t i o ns h o w s t h a tt si sb e t t e rt h a ng e n e t i ca l g o r i t h mi nt h eb o t hs p e e da n dq u a l i t yo fp l a c e m e n t h o w e v e r ，t h ep e r f o r m a n c eo ft ss t r o n g l yd e p e n d so nt h ek e yp a r a m e t e r s ， w h i c hg u i d et h es e a r c hi nt h et sp r o c e d u r e t h e ya r eu s u a l l yd e t e r m i n e db y e x p e r i e n c e a n da l w a y s k e e pc o n s t a n t d u r i n g t h ee n t i r es e a r c hp r o c e d u r e t h i s a p p r o a c hw o u l dn o tb ee f f i c i e n ti nm a n y c a s e s w ed e v e l o pa nf r sw h i c hu s ea f u z z ys y s t e mt o d e t e r m i n es o m ep a r a m e t e r sn e e d e di nt h et s b e n e f i t so ft h e m e t h o d o l o g y a r ei l k s 廿a t e db yt h en u m e r i c a lr e s u l t s k e y w o r d s ：v l s ip l a c e m e n t ，h e u r i s t i ca l g o r i t h m ，t a b us e a r c h ，f u z z ys y s t e m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：盥 日期：乒n 1 年月占e l 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丛导师签名： 日期：砌 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 第一章绪论 当今是一个信息的时代，电子信息技术( i n f o r m a t i o nt e c h n o l o g y ，i t ) 作 为强大的社会生产力，在推动经济发展、社会产业结构和生括方式的变革中的 作用日益增长。r r 产业是2 0 世纪以来发展最为迅速的产业，而集成电路 ( i n t e g r a t e dc i r c u i t ，i c ) 产业是其发展的核心和基础。据报道，世界国民生产 总值的增值部分的6 5 与i c 有关，r r 和i c 的发展水平已经成为衡量一个国 家综合国力的重要标志。我国在2 1 世纪初的“十五计划”里，明确地把软件 产业和集成电路产业作为中国高科技的两大重点发展方向。 集成电路从6 0 年代开始，已经历了小规模集成( s m a l ls c a l ei n t e g r a t i o n ， s s i ) 、中规模集成( m e d i u ms c a l ei n t e g r a t i o n ，m s i ) 、大规模集成( l a r g e s c a l ei n t e g r a t i o n ，l s i ) 的发展阶段，到目前已经进入了超大规模集成( v e r y l a r g e s c a l e i n t e g r a t i o n ，v l s i ) 和特大规模集成( u n u s u a ll a r g e s c a l e i n t e g r a t i o n ，u l s i ) 阶段，是一个“s y s t e mo nc h i p ”的时代。目前，商业化半 导体芯片制造技术的主流已经达到o 3 5 微米的线宽，预计今后的发展趋势是 0 1 5 微米甚至o 1 微米以下，即集成电路已经进入深亚微米工艺时代。集成电 路技术迅速向着更高集成度、超小型化、高性能、高可靠性的方向发展，一个 芯片上可集成高达几亿，甚至十几亿的晶体管。随着集成度的提高，芯片内部 晶体管数目越来越多，使得集成电路设计的复杂性也越来越高。可以这么说： v l s i 的进一步发展离开了计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，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 ) 将寸步难行【1 】【2 l 。 正是在这样的背景下，在范明钰博士后的中国博士后基金课题基础上， 电子科技大学5 7 0 教研室e d a 课题组申请到了四川省科技厅的计算智能在 超大规模集成电路物理设计中的应用科研项目。本文的工作是这个项目课题 的一部分，主要对v l s i 物理设计中的解决布局问题的算法进行了探讨。 1 1i c c a d 的发展概况 随着集成电路与计算机的迅速发展，以计算机辅助设计为基础的电子设 计自动化技术已经成为电子学领域的重要学科，并已形成一个独立的产业部 第一章绪论 门。它的兴起和发展，又促进了集成电路和电子系统的迅速发展。集成电路的 计算机辅助设计( i c c a d ) 的发展大致可以分为以下三个阶段 3 】。 7 0 年代到8 0 年代初，电子计算机的运行速度、存储量和图形功能等方面 都还正在发展之中，电子c a d 和e d a 技术没有形成系统，仅是有一些孤立 的软件程序，可以在逻辑仿真、电路仿真和印制电路板( p c b ) 、i c 版图绘 制等方面取代了设计人员的手工操作。这些软件一般只有简单的人机交互能 力，能处理的电路规模不大，计算和绘图的速度也很受限制。没有采用统一的 数据库管理技术，程序间的数据传输和交换很不方便。 8 0 年代后期，是计算机和集成电路高速发展的时期，也是i c c a d 技术 真正迈向自动化并形成e d a 产业的时期。这一时期的e d a 工具已经形成一 个有机的系统，可以完成各个设计阶段的自动设计，有友好的人机交互界面? 这种e d a 系统能有效地完成自顶向下( t o p d o w n ) 的设计任务，即从电原理 图构思到逻辑仿真、电路仿真、版图布局布线，一直到最后形成可以交付生产 的i c 版图的一系列的自动化设计过程。 9 0 年代后期，e d a 步入了一个崭新的时期，微电子技术以惊人的速度发 展，电子系统朝着多功能、高速度、智能化的趋势发展。对集成电路和专用集 成电路( a p p l i c a t i o ns p e c i f i ci c ，a s i c ) 的容量、速度、频带都提出了更高的 要求，也就对e d a 技术提出了更高的要求。 1 2 v l s i 设计流程 超大规模集成电路的设计包括了系统规范说明、功能设计、逻辑设计、 电路设计、物理设计、设计验证、制造、封装和测试等过程。v l s i 设计可能 会在一个步骤中，或在几个步骤之间反复交替进行。其流程如图1 1 所示。 v l s ic a d 或e d a 的目标就是要尽量减少这种反复次数以缩短产品进入市场 的时间1 “6 1 。 在整个设计过程中，物理设计( 或称为版图设计) 是其中重要的一环。 它是整个集成电路设计过程中与产品研制和生产直接相关的一个设计过程，直 接关系芯片设计周期，生产成本和产品质量；现今物理设计要在几十平方毫米 的硅片上设计出线条只有零点几微米且数以百万计的器件的整个电子系统。这 2 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 一步骤是以往人工设计中耗时最多，差错率最高的设计过程之一。因此，它也 是近年来e d a 工具中发展最快，自动化程度最高的领域之一。而且，随着 v l s i 向深亚微米推进，它也是受工艺影响最大、面临的机遇和挑战最大的领 域之一。 1 3物理设计过程 系统描述 山 i功能设计 山 逻辑设计 山 l电路设计 i物理设计 山 设计验证 山 芯片制造 i 山 l测试封装 图1 1v l s i 设计流程 v l s i 物理设计( p h y s i c a ld e s i g n ) 的输入是电路的元件说明和网表信息 ( 可用原理图表示) ，输出是设计好的版图，即根据电路和工艺要求完成芯片 上单元或功能块的安置，实现它们之间所需要的互连。它要把每个元件的电路 表示转换成几何表示，同时，元件间的连线也要被转换成几何连线图形。我们 把电路的几何表示叫做版图，而把版图的设计称为布图。版图设计要符合与制 造工艺有关的设计规则的所有要求。 3 3 第一章绪论 由于布图的复杂性，整个布图过程往往被分成若干个子步骤，包括：划 分( p a r t i t i o n ) 、布图规划和布局( f l o o r p l a n n i n g ，p l a c e m e n t ) 、布线 ( r o u t i n g ) 、压缩( c o m p a c t i o n ) 等，每一个子步骤完成布图的一部分。 划分过程将各部件分组形成多个模块( b l o c k ) ，以使处理问题的规模缩 小。各模块的大小和在芯片上的精确位置由布图规划和布局算法确定。布图规 划和布局算法的目标是最小化芯片的面积同时满足其它约束如模块间的完全互 连等。布局完成之后将进入线网布线阶段，这一阶段的首要任务是百分之百地 完成模块问的互连，其次是在完成布线的前提下进一步优化布线结果。线网布 线一般划分为总体布线和详细布线这两个布线过程，总体布线确定一个线网的 大致走线，它将各线网合理地分配到各布线区域中，以确保尽可能高的布通 率；详细布线则最终产生线网在芯片上的实际走线，及生成各线网的几何版 图。压缩的任务是从各个方向上压缩芯片的版图以期将芯片的总面积减小，整 个布图过程可以用图1 2 来表示。 l 物 l 理 l 设 w 划分 山 布圈规划和布局 山 总体布线 山 详细布线 图1 2 物理设计过程 布图过程往往是一个反复迭代求解的过程。例如，为了得到一个好的布 图结果，需要反复进行总体布线和详细布线，而后一个步骤的结果又依赖于前 一个步骤的结果。从一个不好的布局结果出发，一定不会获得好的布线结果。 4 一 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 因此，必须注意布图中各个步骤算法间目标函数的一致性，前面阶段的算法要 尽可能考虑到对后续阶段的影响。从各个阶段算法对布图结果的影响来讲，布 局是最重要的，其次是总体布线，然后是详细布线。 1 4 布图模式 按照对布局布线位置的限制和对布局模块的限制来分，可以把布图模式 分为全定制设计模式( f u l l - c u s t o md e s i g ns t y l e ) 和半定制设计模式( s e m i c u s t o m d e s i g ns t y l e ) 两大类。 1 4 1 全定制设计模式 全定制设计模式对模块( 或单元) 和布局位置没有限制。目前有基于几 何图形的交互图形编辑、符号法版图设计和积木块自动布图等三种模式。前两 种方法属于手工的方法，设计者将手工设计好的版图草图用一个交互图形编辑 器输入，或是使用晶体管、通孔、连线的符号进行输入和编辑。这类方法设计 效率低、设计时间长，但是可以得到高集成度和高性能的芯片，广泛的用于大 批量产品的设计。 积木块自动布图( b u i l d i n gb l o c k sl a y o u t ，b b l ) 又称为任意形状单元布 图，版图如图1 3 所示。限于实现的困难，目前的b b l 模式中的模块都为矩 形。b b l 模式具有布图密度高和布线灵活的优点，又具有自动设计的高效率 的优点，是一种很理想的设计方法。但由于其布图算法和布图系统较其他设计 方法复杂，目前还处于发展阶段，没有很成功且得到广泛应用的系统。 【一【j口 璺口 口 二 = u口 图t 38 b l 版图结构 3 第一章绪论 1 4 2 半定制设计横式 半定制设计模式对单元的高度、电源线的位置和电源引线端的引出方向 都有一定的限制，而且，单元只能放置在规定的区域内或必须按行来进行放 置。包括了标准单元设计模式( s t a n d a r dc e l ld e s i g ns t y l e ) 、门阵列设计模式 ( g a t ea r r a yd e s i g ns t y l e ) 、现场可编程门阵列( f i e l dp r o g r a m m a b l eg a t e a r r a y ，f p g a ) 等若干小类。 标准单元( 见图1 4 ( a ) ) 和门阵列( 见图1 4 ( b ) ) 又常被称为基于行排 列( r o wb a s e d ) 的模式。在这两种布图模式中，电路的基本单元有规则地成 行排列，单元行之间的区域作为布线通道( c h a n n e l ) 。由于单元行排列比较 规则，问题相对比较简单，所以布图设计技术首先在门阵列和标准单元模式上 得到了比较充分的发展。这两种方法较适于中批量和小批量，但性能要求高、 设计和制造的周期短、费用低的产品。 ( a ) 标准单元( b ) 门阵列 图1 4 现场可编程门阵列是一种可编程器件( p r o g r a m m a b l el o g i cd e v i c e ， p l d ) ，它是近几年迅速发展用于a s i c 设计的一种新方法。f p g a 提供了用户 可编程和自己制造的能力，极大的缩短了设计和制造的时间，节省了费用。但 这种设计方式的版图，冗余面积较多，适于单件或批量很小的产品。 所有模式中实现互连都是其最终目的，因而求最小连接树问题及多货物 网络流问题等都是其中最基本的问题，归根到底是组合优化问题，其中许多问 题已被证明是n p 复杂度的。寻求有效的优化算法以解决工艺向深亚微米推 进，规模达到京规模( 1 0 9 门) 时的诸多n p 困难问题已成为当务之急。 6 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 1 5 本论文的主要内容及安排 如前所述，物理设计是v l s i 设计流程中既关键又复杂的一步，而布局又 是物理设计中最重要的一步，布局的诸多问题都是n p 完全问题。本文的工作 是电子科技大学5 7 0 教研室e d a 课题组申请到的四川省科技厅的计算智能 在超大规模集成电路物理设计中的应用科研项目的一部分，主要对v l s i 物 理设计中的布局问题进行了探讨，在学习和总结目前一些优化算法的基础上， 引入禁忌算法和模糊禁忌算法来解决门阵列布局问题，在布局质量和速度上都 取得了很好的结果。 论文安排如下：第二章介绍v l s i 布局和布图规划，对布局中使用的线长 估计、目标函数及布局策略进行介绍；第三章归纳和总结了目前在优化布局中 使用的各种优化算法，对它们进行了分析；第四章介绍禁忌算法及其在门阵列 布局中的应用；第五章对模糊禁忌算法进行了讨论，并用以解决布局问题；第 六章为总结和展望。 第二章超大规模集成电路布局与布图规划 第二章超大规模集成电路布局与布图规划 布局是集成电路自动布图设计中的重要环节之一。布局就是把元件或者 模块安置在芯片或印制电路板的适当位置上，并使其满足一定的目标函数。布 局阶段的输入是一组模块、各个模块上的引线端信息和网表信息。如果模块内 的电路版图已经完成，则该模块的形状和大小已知，此类模块称为“硬模块” ( h a r db l o c k ) ，另一类需要在布局阶段确定其形状和大小的模块则称为“软 模块”( s o f tb l o c k ) 。通常所说的“布局问题”是指待安置的模块均为硬模块 的情况，此时，只需要考虑给每个模块在芯片上分配一个位置。但是，当模块 中包含有软模块的时候，布局问题就成为“布图规划”问题，这时要解决的不 仅是确定每一个模块在芯片上的位置，还要确定每个软模块的形状和大小，因 此，布局问题仅是布图规划问题的一个特例。 在布图规划中，我们只是在较高层次上完成了对软模块的形状和大小的 估计，以及它们的引线端的分配，还需要实现这些软模块内部具体的物理设 计。此时，它们又变成了较低层次上的布局或布图规划问题，布图规划中得到 的模块形状、面积和引线端的位置则作为低层布局或布图规划的约束条件。直 到在一个足够低的层次上，可以用手工或自动的方法完成这些软模块的物理设 计，使它成为硬模块为止。然后，我们再返回到较高层次上去做布局。 由于布局的对象不同，布局问题的详细含义和目标会有所不同。通常的 目标是芯片的面积最小、总连线长度最短和能提供高的布通率等等：在深亚微 米下，互连线所造成的延时已经成为影响芯片性能的主要因素，因此，在布局 时必须考虑性能优化( p e r f o r m a n c e d r i v e n ) 或时延优化( t i m i n g d r i v e n ) ，即 还需要将连线时延考虑在布局或布图规划的目标函数中。这样的布局或布图规 划问题称作性能驱动的布局( p e r f o r m a n c e d r i v e np l a c e m e n t ，f l o o r p l a n n i n g ) 或 时延驱动的布局( t i m i n g d r i v e np l a c e m e n t ，f l o o r p l a n n i n g ) 问题。 2 1 布局中的线长估计 大部分布局问题的目标都与连线长度有关，而且要考虑的时延优化也与 线长有关。由于在布局阶段不完成最终布线，而要在无几何走线的情况下判断 8 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 一个布局结果的好坏，就需要一个简单、快速、较为准确的线长估计方法来估 算线长。文献 1 】总结了九种计算一条线网的连线长度的方法。主要包括：最 小斯坦纳树( m i n i m u ms t e i n e rt r e e ，s m t ) 、最小生成树( m i n i m u ms p a n n i n g t r e e ，m s t ) 、最小链( m i n i m u mc h m n ) 、源到漏端的最小连接( m i n i m u m s o u r c e t o s i n kc o n n e c t i o n ) 、完全图( c o m p l e t eg r a p h ) 、边界图( b o u n d i n g b o x ) 、半周长( h a l fp e r i m e t e r ) 、二次线长( q u a d r a t i cw i r e l e n g t h ) 、单树 干斯坦纳树( s i n g l e t r u n k s t e i n e rt r e e ) 等。 最小斯坦纳树是一种最小树，其顶点除了线网顶点外，还有斯坦纳交叉 点。最小生成树是另一种最小树，其顶点包括线网顶点集。而最小链是一种最 小的连接所有顶点的链。这三种线网连接长度的估计都必须在构造它们相应的 布线树后才能计算它们的线长，在布局阶段要完成所有线网的布线所花的代价 太大，且比较困难，不适于在布线没有完成前估计线网的连线长度。而且最小 斯坦纳树是一个n p 困难问题，用它来计算线网长度，精度虽高，但是计算量 太大。 在优化连线总长的目标函数中用从源端到漏端的最小连接来表示线网长 度有利于减小芯片的最大延迟。而边界框和半周长是两种十分简单的线网长度 计算方法，广泛的用于线网总长作为优化目标函数的布局中。采用二次线长的 线长估计，可以使布局问题变成二次规划和二次优化问题，有不少基于数学规 划方法的算法采用二次线长的线长估计。单树干斯坦纳树是折衷考虑精度和计 算量的一种线长估计方法。 各种线长估计方法都有自己的特点，选用哪种线长估计方法取决于使用 哪种布局方法。 2 2 布局的目标函数 布局阶段的要求是把模块分配到芯片的合适位置，一般的目标包括芯片 面积最小、布通率高、电性能最优等。除此之外，还需要考虑一些工艺和电学 上的约束条件。目前，比较实际的布局方法是寻找一个比较简单、计算时问较 短又能反映布局优化目标的目标函数，采用一定的布局算法求解布局结果，以 使目标函数达到最小。不同的芯片布局模式对目标函数的选取应有所不同。较 为常用的有以下三类： 9 第二章超大规模集成电路布局与布图规划 2 2 i 基于连线总长的目标函数 设某一个芯片的布局p ，其连线总长为： 丁( p ) = l 。 城n ( 式2 1 ) 其中，l 可以是2 1 节中介绍的任意一种线网长度估计值，n 为所有线 网集合。基于连线总长( t o t a lw i r e l e n g 也b a s e d ) 布局的目标是使r ( p ) 最小 化。一般说来，在标准单元和b b l 模式布局中采用连线总长最短是可行的， 因为连线总长最短基本反映了芯片面积最小。 2 2 2 基于翻线的目标函数 设c 。( t ) 是x = 工，时切割线和线网的交点数，c p ( y 。) 是y = y 时切割线和 线网的交点数，则基于割线( c u t b a s e d ) 的目标可以采用两种目标函数： 1 使最大切割线数目最小化： ix ( | p ) - m a ，x c p ( z 。) ( 式2 2 ) 1r ( e ) = m a x c p ( ) ，f ) 布局目标是使水平和垂直方向的最大切割线数目最小化，其物理意 义是使线网尽可能的均匀分配。 2 使总的切割线数目最小化： 丁( p ) = g ( ) + c ，( y ) ( 式2 3 ) 2 2 3 基于最大密度的目标函数 对于一个布局p ，其局部密度定义为： d p ( p f ) = f p ( e ，) c 。( e ，) ( 式2 4 ) 其中，p ( q ) 为分配在巳中的线网的数目，c p ( 巳) 为p 。中通道的容最。 最大密度定义为： d ( p ) = m a x d 。( t ) ，i = 1 , 2 ， ( 式2 5 ) 1 0 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 布局目标是使d ( p ) 最小化，即使线网均匀分配，以提高布通率。这类目 标函数适用于像门阵列这样具有固定通道的芯片，比使用最大切割线数目最小 化的目标函数更能确切的反映出它的布通率。 2 2 4 复合的目标函数 以上为三种较为基本的目标函数，对于具体问题和要求，目标往往没有 这么单纯。可以将上述三类目标函数组合成几种复合的目标函数，以兼顾面积 最小、总连线最短和布通率高等要求，还可以设置其他的目标函数，例如加入 性能的限制，使它符合时延等性能的要求。总之，目标函数的选取对布局结果 的影响很大，具体使用什么样的目标函数要视问题及要求而定。 2 3 布局策略 由于布局设计的复杂性，通常将布局分为初始布局和迭代改善布局两个 子过程。首先通过一些构造性算法获得一个初始的布局构型，再通过一些优化 算法进行迭代改善，从而获得最佳或满意的布局效果。 2 3 1 初始布局 初始布局又称为构造型布局( c o n s t r u c t i v ep l a c e m e n t ) ，初始布局的目的 是求得一个比较好的初始布局构型，以减少迭代改善的次数，从而提高整个布 局设计的布局质量和处理效率。初始布局又包含选择和安置两部分，目前已有 基于联接度和基于结群等的初始布局方法。在基于联接度的布局方法中，单元 的选择和安置是同时进行的，通过计算未安置单元和已安置单元的单个联接 度、总联接度或者内外联接度等来选择本次要安景的单元，再通过“重心” 法、核心生长法或边生长法等安置策略来安置，完成后，这个单元的位置将不 再改变。而基于结群的布局方法是一种组合构造方法，它尽量推迟确定每一个 单元在芯片中的具体位置，将所有单元按照其联接度关系分为若干个群，使群 内有紧密内部联接关系而群间只有相对弱的联接关系，最后在结群的基础上进 行单元位置的确定。与随机选取布局构型后再进行改善布局相比，初始布局后 再进行迭代改善布局，无论在布局质量上还是在运行时间上效果都要好，但随 着电路规模的增加，初始布局的作用将会逐渐降低。 第二章超大规模集成电路布局与布图规划 2 3 2迭代改善布局 迭代改善( i t e r a t i v ei m p r o v e m e n t ) 布局是决定布局质量的关键过程，也 是一个复杂的过程，一个逐步优化的过程。它是在初始布局的基础上，通过各 种优化算法，求得一个满足面积最小、总的连线长度最短或者线网布通率最高 等要求的布局结果。这类问题多是n p 完全问题，即不能在多项式时间内求解 的问题。目前主要有三类迭代改善布局的方法，一类是基于对交换和最小割的 算法，一类是基于线性和非线性数学规划的算法，还有一类是基于随机优化的 算法。迭代改善布局是我们研究的重点，下一章里将详细介绍这些算法。 电子科技大学硕士学位论文：用于v l s i 布局的计算智能方法研究 第三章v l s i 物理布局中使用的各类算法 如前所述，v l s i 物理设计中的迭代改善布局问题，其实就是在初始布局 的基础上进行寻优的问题，它们大都具有n p 复杂度。在最优化问题中，因为 最大化问题也可以转化为最小化问题，为简便，我们通常只讨论最小化问题。 典型的最小化问题可以形式化为在n 维变量 x ，x ：，x 。1 构成的空间r ”中， 搜索变量x 0 = o ，x ：o ，x 。o ) ，使得对空间尺4 中任何一点x ，都有 f ( x o ) f ( x ) ，其中，( - ) 为定义在空间月“上的目标函数。 对于凸空间的搜索，传统的梯度下降法及其各种改进方法都是十分有效 的，但是，如果优化问题有多个极值，是在非凸空间中进行搜索，或者目标函 数不可微，以及解决的是离散问题等，则该类方法就无能为力了。在小规模的 情况下，可以使用穷尽法来解决这类问题，但随着问题规模的增大，又会面临 计算量爆炸的困难。 布局问题的难度随着单元数目的增加而增加。因此，处理v l s i 布局问题 的经典方法是基于分而治之的策略，其典型代表是最小割算法。从8 0 年代开 始，出现了一些基于非线性连续规划和二次规划的算法，这类算法有基于严格 的数学分析来证明它们的求解质量。面对布局的规模越来越大，为了解决计算 _ 量爆炸的问题，不少模拟物理或是生物现象的优化思想被提了出来，如模拟退 火、遗传算法、进化算法、人工神经网络以及蚁群算法等，这类基于随机优化 的启发式算法在布局中得到了较广泛的研究，可以得到很好的布局质量。各类 算法分述如下： 3 1 成对交换和最小割算法 基于对交换的迭代改善是一种既简单又实用的迭代改善算法。初始布局 阶段产生了一个初始布局构型，从这个布局结果出发，对特定的单元进行位置 互换或单元方位的变换来产生一个新的布局，与不同的目标函数结合就成了不 同的迭代改善方法。对于一个确定的目标函数，将变换后的新布局和前一个布 局进行比较，若布局结果得到了改善，则选用新的布局替代原来的布局，否则 第三章v l s i 物理布局中使用的各类算法 保留原来的布局。如此反复迭代，直到找到最优的布局结果或者迭代终止条件 被满足为止。 成对交换法( p a i r - w i s ei n t e r c h a n g e ，p i ) 选用连线总长最小或者单元张力 和最小为目标，随机或是根据各单元张力来选择要交换的单元。 最小割算法( m i n c u ta l g o r i t h m ) 7 - 9 选用线网的割值函数来作为目标函 数，可以是线网总割值最小也可以是最大割值最小化，最小割的目标函数如第 二章2 2 2 节所述，这样可以与线网的可布性对应起来。目前有面向割线的最 小割算法和面向模块的最小割算法，前者适用于标准单元、门阵列等基于行列 的布局方式，后者适用于积木块这样不太规则的布局方式。目前有些实用系统 仍使用最小割算法进行布局，但是，最小割算法是依赖于初始划分的迭代改进 启发式算法，局限于局部最优解是这类布局算法的主要缺点。虽然已经有一些 方法力图解决这个问题，但仍不如人意。 3 2 基于数学规划的方法 布局优化的一个目标就是使线网的总线长最短。对于一个布局输入，设 用m = m l ，m 2 ，m m ，n = f n l ，n 2 ，n ) ，p = f p l ，p 2 ，p p 分别表示单 元、线网和i 0 引线端的集合。单元r r i 。的位置坐标用它的中心坐标( x 。，y 。) 表 示，对于标准单元和门阵列布局，可以忽略模块的形状，则两单元m 和m ，间 的线长为t = ( x i x j ) + ( y i y f ) ，二次线长为瓯= ( 五一x ，) 2 + ( y 。一y j ) 2 ，总 的线长为h ，l = ，匕，总的二次线长为w r = q 。二次线长过多地惩罚了 长线网，且与最终的布局面积并没有良好的对应关系，但是，采用二次线长的 估计方式可以使得布局问题变成个二次规划或二次优化的问题”。从8 0 年 代中开始，就出现一些基于非线性连续规划和二次规划的算法，如： p r o u d 【1 “、g o r d i a n t l 2 1 、r i t u a l 1 孔和v e a p t l 4 1 等。这些算法把布局问题归 结为有线性约束的二次规划问题( l i n e a rc o n s t r a i n e dq u a d r a t i cp r o g r a m m i n g ， l q p ) ，线性约束条件来自于单元之间不重复且均匀的放置、满足性能驱动等 等布局所需的要求。这类算法有一个非常好的特性：可以基于严格的数学分析 来证明它们的求解质量。 电子科技大学硕士学位论文：用于v l $ 1 布局的计算智能方法研究 将问题用图g = ( y ，e ) 来表示，其中v = ( v ，v ：，v 。l 表示端点， e = p 。，p ：，e 。) 表示边。定义w ( g ) 是边e 的一个非负权值，所有的线网可以 表示成一个连接矩阵a = ( ) ，其中， 铲m 啪帅o e 拭3 1 采用以二次线长作为线长估计，加权总线长为目标函数m = q ，。，该 目标函数可以改写如为： 、 中( x ，y ) = x 7 q x + d r x + 圭y 7 q y + d 7 y( 式3 2 ) 其中，d r x 表示单元和i o 端的连接，q = ( 鼋。) 是a 的n ，l 阶拉普拉斯 矩阵： q u ： ? “ ( 式3 3 ) 。1 h f _ j 帆土驯 由( 式3 2 ) 可以看出，可以对x 和y 分别求解，则x 方向的总线长为： 中( x ) = x7 q x + d r x = 羔a i j ( 一一石j ) 2 + d r x ( 式3 4 ) i j = 1 为最小化目标函数( 式3 4 ) ，直接求解方程q x + d = 0 即可，然而这个结 果不是布图需要的结果，还需要考虑与布图模式有关的约束条件，以及一些性 能驱动的条件，可以根据不同的要求，建立不同的约束条件。将x 方向的约 束条件写成矩阵形式： c x = b ( 式3 5 ) 结合( 式3 4 ) 和( 式3 5 ) ，就得到一个线型约束的二次规划问题( l q p ) ： m i n 4 , ( x ) = ；x7 q x + d7 x i c x = b )( 式3 6 ) 由于矩阵q 是正定的，西( x ) 是一个凸函数，且有一个线性的等式约束条 件，( 式3 6 ) 具有唯一的全局极小值。文献【1 l 1 4 】都给出了各自求解这个l q p 的方法。二次规划求解的结果未必比其他布局算法来的好，但是其快速的特点 使它在工业界得以广泛的应用1 0 】。 第三章v l s i 物理布局中使用的各类算法 3 3 模拟退火算法 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法是由s r k p a 丽c k 等人于1 9 8 3 年针对v l s i 设计中的组合优化问题而提出的【坫】。今天，它已经发展成为一种 解决一般组合优化问题的有力而通用的算法。模拟退火算法通过将组合优化问 题和统计力学的热平衡问题相类比，开辟了求解组合优化问题的一条新途径。 该算法实质是对多极值非凸函数，通过设置温度参量，并按, - v e t 于温度的概率 接收比现行解较差的解，以跳出局部极值。 t i m b e rw o l f 系统”1 是模拟退火算法在v l s i 布局问题中应用的一个代 表，它是一个很有名的标准单元布图系统。结合对交换技术和模拟退火算法框 架就可以构造一个模拟退火方法求解布局问题的算法，算法描述如下： a i g o n t h ms i m u l i e d _ a n n e a l i n g b e g i n t = i n i t i a lt e m p e r a t u r e ： s = i n i t i a l _ s o l u t i o n ： w h i l e ( t f i n a lt e m p e r a t u r e 、d o w h i l e ( i n n e r _ l o o p _ c r i t e r i o ni sf a l s e ) d o s l = p e r t u r b ( s ) ； a c = c ( s 1 ) 一c ( s