（计算机应用技术专业论文）bbl布局结构及算法研究.pdf

摘要 摘要 作为电子信息产业发展的核心和基础，集成电路技术正迅速向着更高集成度， 超小型化，高性能、高可靠性的方向发展。随着系统芯片( s o t 2 ) 设计方法和知 识产权( 口) 模块技术在集成电路设计中的不断发展和应用，布图规划和布局日渐 成为超大规模集成( v l s i ) 电路与系统物理设计的关键环节。布图规划和布局的 主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及 模块的引线端位置，使得芯片的面积以及模块之间的互连线总长最小。由于布图 规划和布局是芯片物理设计的第一个重要步骤，其结果将影响芯片的最终性能。 在v l s i 设计流程中，物理设计是既关键又复杂的一步，而布局又是物理设计 中最重要的一步，布局的诸多问题都是n p 完全问题，需要启发式算法来求解。随 着v l s i 集成度的迅猛提高，寻求有效的优化算法应用于布局问题，以提高布局质 量和速度已成为当务之急；同时如何高效地表示布局结构，从而提高布局质量成 为物理设计中的一个国际研究热点。本文正是在这样的背景下，对v l s i 物理设计 中的关键环节布局，展开了一些研究工作。 本文概括地介绍了布局结构表示研究的进展。针对不可二划分的b b l 布局问 题，近年来国内外涌现出如：c b l 、b s g 、s p 、o t r e e 等优秀的布局结构表示方法， 但它们在解空间的大小、编码的费用、编码与布局之间的转换时间等方面各有差 异。 本文提出了一种求解v l s i 布局问题的启发式算法。该算法通过设计模块的优 先顺序进行合理的布局，再辅助于边界矩形来减少边界浪费，对于模块布局放置 的多个可能位置进行比较，并将其放置在优先度最高的适当区域。同时本文阐述 了一种布局表示方法，在这种表示方法中尽量先用更受限制的资源，而尽量后用 。一般”的资源，一般有更多机会满足匹配来解决问题。 关键词：v i s i 布局，边界矩形，启发式算法，布局结构表示 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 ( r i ) ，i n t e g r a t ec i r c u i t o 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 e m 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 dr e l i a b i l i t y w i t ht h ec o n t i n u o u sd e v e l o p m e n t a n da p p l i c a t i o no fe d a d e s i g nm e t h o d o l o g yf o rv l s ic i r c u i ta n ds y s t e m sa sw e l la st h e a d v e n to ft h ei n t e l l e c t u a lp r o p e r t y ( i p ) m o d u l et e c h n o l o g y , f o o r p l a n n i n ga n dp l a c e m e n t h a v eb e c o m eak e ys e c t i o ni nt h ep r o c e s so ft h e i rp h y s i c a ld e s i g n m a i no b j e c t i v eo f f o o r p l a u n i n ga n dp l a c e m e n ti st ol o c a t ee a c hc i r c u i tm o d u l ei nas u i t a b l ep o s i t i o nw i t h a no p t i m a ls h a p ea n da s c e r t a i nt h ep o s i t i o no ft h ep a do ft h em o d u l ei no r d e rt o m i n i m i z ec h i pa r e aa n dl e n g t ho fi n t e r c o n n e c t i o na m o n gb l o c k su n d e rc o n d i t i o no f f u l f i l l i n gt h er e q u i r e m e n to fp l a c e m e n tc o n s t r a i n t s b e c a u s ei st h ef i r s ti m p o r t a n ts t e pi n p h y s i c a ld e s i g n ，i t sr e s u l tw i l la f f e c tt h ef i n a lp e r f o r m a n c eo fac h i p p h y s i c a ld e s i g ni sac o m p l e xk e yl i n ko ft h ev l s id e s i g nf l o w a n dt h ep l a c e m e n t i st 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 pc o m p l e t e ，w h i c h c 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 ft 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 tt 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 gp l a c e m e n t p 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 ec o m p u t a t i o n t i m e t of a c i l i t a t ep l a c e m e n t ，w ed e s i r ea ne f f i c i e n t ，f l e x i b l ea n de f f e c t i v er e p r e s e n t a t i o n w h i c hi n d u c e sas o l u t i o ns t r u c t u r ef u rp l a c e m e n to p t i m i z a t i o nt om o d e lt h eg e o m e t r i c r e l a t i o n s h i pa m o n gm o d u l e s u n d e rt h i sb a c k g r o u n d ，t h i sd i s s e r t a t i o ni si n t e n d e dt o r e p o r ts o m eo fo u rr e s e a r c hr e s u l t s ms o l v i n gb b l ( b u i l d i n gb l o c kl a y o u t ) p r o b l e m s i l l v i _ s ic i r c u i tp h y s i c a ld e s i g n i nt h i sd i s s e r t a t i o n , w eg i v eas u r v e yo fr e c e n td e v e l o p m e n to nn o n - s l i c i n g f l o o r p l a nr e p r e s e n t a t i o n s ，c 晷，c b l , b s qs e q u e n c ep a i ra n d0 t r e ee c t b u ti nt h e s o l u t i o ns p a c es i z e ，c o d eb e t w e e ne x p e n s e ，s w i t c h i n gt i m ei nc o d ea n dl a y o u ta s p e c t s a n d8 0o nh a v et h ed i f f e r e n c er e s p e c t i v e l y t h i sd i s s e a a t i o np r o p o s e sah e u r i s t i ca l g o r i t h mf o rs o l v i n gt h ev e r yl a r g es c a l e i n t e g r a t i o n ( v t s ob l o c kp l a c e m e n tp r o b l e m t h i sa l g o r i t h mm a t e r i a l i z e sr e a s o n a b l e a r r a n g e m e n tt h r o u g hd e s i g n i n gt h es e q u e n c ea c c o r d i n gt ot h eb l o c k s p f i o r i t 5u t i l i z e s a b s t r a c t t h es i d ec i r c u m s c r i p t i o na st h es u p p l e m e n t a t i o nf o rd e c r e a s i n gt h es i d ew a s t e ，c o m p a r e s s e v e r a lp o s s i b l el o c a t i o n so ft h eb l o c k s l a y o u t ，a n da c c e p t st h eo p t i m u ml o c a t i o nw h i c h h a dt h eh i g h e s tp r i o r i t yf o rc o n s e q u e n te s t a b l i s h m e n t s i m u l t a n e o u s l yt h i sd i s s e r t a t i o n e l a b o r a t eaf l o o r p l a nr e p r e s e n t a t i o n , w h i c hu s e st h er e s o u r c e st h a tr e c e i v e sm o r el i m i t s a sf a ra sp o s s i b l e a n dt h e nu s e st h eg e n e r a lr e s o u r c e g e n e r a l l yt h e r ea r en 粥犯 o p p o r t u n i t i e st os a t i s f yt h em a t c hg e n e r a l l yt os o l v et h ep r o b l e m k e y w o r d s ：v l s ip l a c e m e n t ，r e c t a n g l eo fs i d e ，h e u r i s t i ca l g o r i t h m ， p l a c e m e n tr e p r e s e n t a t i o n s m - 图目录 图目录 图1 1 信息产业中的e d a 2 图1 2v l s i 设计流程。3 图1 3 物理设计过程4 图1 - 4b b l 版图结构5 图1 5 标准单元和门阵列6 图3 1 可行域和面积，长边的关系2 1 图3 2 布局方向2 2 图4 - 1 变形网格b s g 2 7 图4 2 一个实例2 7 图4 3 网格表示序列对r g 卜，g - ) = ( e c a d i b ，f c b e a d ) 的约束。2 9 图4 4 序列对水平约束图2 9 图4 5 序列对垂直约束图3 0 图牛6 布局举例。3 1 图4 7t c g 表示3 l 图4 8 马赛克布局和非马赛克布局3 2 图4 9 角模块的删除操作3 3 图4 一l o 角模块的插入操作3 3 图4 1 1 布图结构和相应c b l 表示3 4 图4 - 1 2 布局p 示例3 5 图4 1 3 布局p 的轮廓3 5 图4 1 4 ( a ) 一为c s 表示布局的过程( 深色阴影模块表示轮廓，浅色阴影模块表示 己放置模块砸) 给出了c s 表示法3 6 图4 1 5 约束图3 7 图4 - 1 6 向左紧置布局3 8 图4 - 1 7 向左下紧置柿局3 8 图4 - 1 8o t r e e 表示的布局3 8 图4 1 97 个结点的o t r e e 3 9 图4 2 0 容许布局p 对应的水平b + t r e e 4 0 图4 - 2 1 容许布局p 对应的垂直b 骶c 4 0 图5 - 1 重心矩形约束条件下出现的问题4 6 图5 - 2 布局模块的边界矩形4 6 图5 3 使用边界矩形解决文献阳中使用重心矩形出现的问题4 7 图5 4 矩形块实施占角动作的两种可能布局位置4 8 图5 - 5 矩形块的外轮廓点。4 9 图5 6i 类动作( 占边) 的两种情况4 9 图5 - 7i i 类动作的第一种占角方式5 0 v 图目录 图5 - 8 类动作的第二种占角方式5 0 图5 - 9i i 类动作的第三种占角方式5 1 图5 1 0 文献【3 6 】和本文的布局结果 图5 1 1 仿真测试结果5 4 表目录 表目录 表5 1 文献【3 6 l 中的布局模块大小( h i 是长，w i 是宽) 5 2 表5 2 本文的布局结果与文献【蚓结果的比较5 2 表5 - 3a m i 3 3 的模块信息( h i 是长，w i 是宽) 5 3 表5 - 4a m i 4 9 的模块信息( h i 是长，w i 是宽) 5 3 表5 5 布局实例比较5 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期：妒7 年尹月讲b 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后应遵守此规定) e t i 朝i ；砷年垆月细 第一章绪论 第一章绪论 电子信息技术( i n f o r m a t i o nt e c h n o l o g y , r o 作为强大的社会生产力，在推动经济 发展、社会产业结构和生活方式的变革中的作用日益增长。t 1 r 产业是2 0 世纪以来 发展最为迅速的产业，而集成电路( i n t e g r a t e dc i r c u i t 1 0 产业是其发展的核心和基 础。据报道，世界国民生产总值的增值部分的6 5 与i c 有关，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 d 、 中规模集成( 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 es c a l ei n t e g r a t i o n ， t s d 的发展阶段，到目前已经进入了超大规模集成( v e r yl a r g es c a l ei n t e g r a t i o n 。 v l s d 和特大规模集成( u n u s u a ll a r g es c a l ei n t e g r a t i o n , u l s i ) 阶段，是个系统芯片 集成( s y s t e mo na c h i p ) 的时代。目前，商业化半导体芯片制造技术的主流已经达到 0 1 3 微米的线宽，今后的发展趋势是0 0 9 和0 0 6 5 微米( i b m 已经在实验室中实现1 甚至0 0 5 微米。集成电路技术迅速向着更高集成度、超小型化、高性能、高可靠 性的方向发展，一个芯片上可集成高达几亿，甚至十几亿的晶体管。随着集成度 的提高，芯片内部晶体管数目越来越多，使得集成电路设计的复杂性也越来越高。 如此高的集成度，靠人手工设计电路是不可想象的。可以这么说，v l s i 的进一步 发展离开了计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a o ) 和电子设计自动化 ( 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 ) 将寸步难行【4 l 【5 】。 e d a ( e l e c t r i cd e s i g n a u t o m a t i c ) t 具从6 0 年代末起，经过3 0 年发展，目前已 是电子设计的必备工具。图1 - 1 示出了i c 及e d a 在整个i t 市场中的关系与作用， 从图中可以看出，仅占r r 市场份额1 6 亿美元的e d a 产品支撑着8 0 0 0 亿美元的 r r 产业的电子设计与制造。而且随着电子产品开发技术含量的增加，这一趋势将 不断提高i ，l 。 - 1 电子科技大学硕士学位论文 惦包 微 图1 - 1 信息产业中的e d a 随着v l s i 电路中互连线特征尺寸的不断减小，许多电子，电路问题变得非常 突出，例如电路连线之间的噪声串扰、电迁移、电路发热、连线延迟等等。而电 路连线延迟和发热是其中的影响较大的问题，它们可能会制约整个v l s i 芯片的工 作速度。因此，连线延迟将成为电路延时的主要部份线问串扰也将成为影响电 路信号完整性的重要因素，连线本身也不再能当作集总参量处理。不占而喻。随 着深亚微米工艺的发展，集成电路设计将从以器件为中心的设计模式，逐步过渡 到器件和连线并重，和以互连为中心的设计模式。相应的，e d a 工具也要不断的 改进。而e d a 的关键改进之一又集中在它的物理设计部分，即布图规划、布局布 线等部分的算法改进。 1 1 v l s i ( 超大规模集成电路) 设计流程 超大规模集成电路v l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) 设计周期分为以下几个 步骤：系统规范说明( s y s t e ms p e c i f i c a t i o n ) ，功能设计( f u n c t i o nd e s i g n ) ，逻辑设 计( 1 0 9 i cd e s i g n ) ，电路致计( c i r c u i td e s i g n ) ，物理设计( p h y s i c a ld e s i g n ) ，设计 验证( d e s i g nv e r i f i c a t i o n ) ，制造( f a b r i c a t i o n ) ，封装和测试( p a c k a g ea n dt e s t ) v l s i 设计可能会在一个步骤中，或在几个步骤之间反复交替进行。v l s i 电路的 设计流程如图1 2 所示。 2 第一章绪论 最缱舰范瓣明 功能殴计 逻辑驶计 l i 路设计 物理设计 + 设词。验i i e 芯_ i 聿 圈迓 测试封装 图1 - 2v l s i 设计流程 1 系统规范说明包括系统功能、性能和物理尺寸。此外，还需要考虑选择设 计模式和制造工艺。最终结果是确定芯片尺寸、工作进度、功耗和系统功 能。 2 在功能设计中主要考虑系统的行为特性，常用的方法是时序图或者表示各 子模块间关系的关系图。利用这些信息可以改进整个设计过程或简化后续 的设计步骤。 3 逻辑设计中可以得到一个表示系统功能的逻辑结构并反复测试其正确性。 常用文本、原理图或者逻辑图表示设计，有时也用布尔方程表示设计。在 设计过程中，还要对该逻辑结构进行模拟以验证其正确性，并对其进行优 化设计或称之为逻辑最小化。 4 皇堕丝过吐要考虑逻辑部件的电路实现，包括速度和功耗。此外，还需注 意各种元件的电性能。通常用详细的电路图来表示电路设计。 5 物理设计即布图设计，是v l s l 设计中最费时的一步。物理设计要把每个 元件的电路表示转换成几何表示。同时，元件间连接的线网也被转换成几 何连线图形。电路的几何表示称为版图。版图设计要符合与制造工艺有关 的设计规则要求。 3 匝巫 坠圄 电子科技大学硕士学位论文 6 设计验证也称版图验证，它确保版图设计完成后所得到的集合图形满足制 造工艺要求和符合系统的设计规范。 7 芯片制造过程包括芯片准备、杂质注入、扩散和光刻等工艺。 8 在完成芯片制造后，要进行封装和测试。安置在印制电路板上的芯片可封 装成双列直插式、引脚阵列式或其它形式。 1 2 物理设计过程 v l s i 电路物理设计( p h y s i c a ld e s i g n ) 被称为布图设计( l a y o u td e s i g n ) 。它的输 入是电路的元件说明和网表( 可用原理图表示) ，输出是设计好的版图，即根据电路 以及工艺要求完成芯片上单元或功能模块的安鼠，实现它们之间所需要的互连。 它要把每个元件的电路表示转换成几何表示，同时，元件问的连线也要被转换成 几何连线图形。对电路的几何表示叫做版图，把版图的设计称为布图。版图设计 要符合与制造工艺有关的设计规则的所有要求。 电路设计 i 物 划分 理 设 - 计 布图规划和布局 总体布线 详细布线 上 设计验证 图1 3 物理设计过程 如图l - 3 指出了整个布图设计的过程包括划 分( p a r t i t i o n ) ，布图规划 c f i o o r p t a n n i n g ) ，布局但l a c a m 柚t ) ，布线m i l l g ) 1 1 】等而布图规划和布局是布图 一4 - 第一章绪论 设计的早期阶段，其完成质量对布线工作的顺利完成乃至最终芯片而积和性能的 影响极大。从各个阶段算法对布图结果的影响来看，布局是最重要的，其次是总 体布线，然后是详细布线。 1 3v l s i 的布图模式 按照对布局布线位置的限制和对布局模块的限制来分，可以把布图模式分为 全定制设计模式( 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 n s t y l e ) 两大类。 1 3 1全定制模式 整个电路被划分为一些子电路，每个子电路是一个模块。最通常情况下，模 块的外形和放置位置都没有限制。全定制设计模式对模块( 或单元) 和布局位置没有 限制。目前有基于几何图形的交互图形编辑、符号法版图设计和积木块自动布图 等三种模式。前两种方法属于手工的方法，设计者将手工设计好的版图草图用一 个交互图形编辑器输入，或是使用晶体管、通孔、连线的符号进行输入和编辑。 这类方法设计效率低、设计时间长，但是可以得到高集成度和高性能的芯片，广 泛的用于大批量产品的设计。 积木块自动布图( b u i l d i n g b l o c k sl a y o u t ，b b l ) 又称为任意形状单元布图，版图 如图1 - 4 所示。限于实现的困难，目前的b b l 模式中的模块都为矩形。b b l 模式 具有布图密度高和布线灵活的优点，又具有自动设计的高效率的优点，是一种很 理想的设计方法。同时，我们可以看到，由于模块的各边互相平行或垂直，很自 然的就配合了曼哈顿布线模型。 口口 口 璺口 口 亡= 二 u口 图1 - 4b b l 版图结构 1 3 2 半定制设计模式 半定制设计模式对单元的高度、电源线的位置和电源引线端的引出方向都有 - 5 电子科技大学硕士学位论文 一定的限制，而且，单元只能放置在规定的区域内或必须按行来进行放置。包括 了标准单元设计模式( s t a n d a r dc e i ld e s i g ns t y l o 、门阵列设计模式( g a t e a r r a y d e s i g ns t y l e ) 、现场可编程门阵列( f i c l dp r o g r a m m a b l eg a t ea r r a y , f p g a ) 等若 干小类。 1 标准单元设计模式( s t a n d a r dc e l ld e s i g ns t y l e ) ：系统事先已准备好几百种包 括有逻辑符号、拓扑和物理版图的“标准单元”存入单元库中，以供用户 设计不同的芯片。这些单元的逻辑功能、电路性能及几何设计规则都经过 验证和分析。 2 门阵列设计模式( g a t ea r r a yd e s i g ns t y l e ) ：又称为母片( m a s t e rs l i c e ) 法。它预 先设计和制作好各种规模的母片，其上除金属连线和通孔外的单元图形是 固定不变且以阵列排列。每个这样的单元可以经过不同的金属连线得到不 同功能的单元电路。母片上单元之间区域是水平和垂直的席线通道。标准 单元( 见图1 - 5 ( a ) ) 和门阵列( 见图l 一5 ( b ) ) 又常被称为基于行排列( r o wb a s e d ) 的模式。在这两种布图模式中，电路的基本单元有规则地成行排列，单元 行之间的区域作为布线通道( c h a n n e l ) 。由于单元行排列比较规则，问题相 对比较简单，所以布图设计技术首先在门阵列和标准单元模式上得到了比 较充分的发展。这两种方法较适于中批量和小批量，但性能要求高、设计 和制造的周期短、费用低的产品。 f a ) 桥 缱单元 口口口口口口 口口口口口口口 口口口口口口口 l il j 口 o 口口r 口日口口 f b ) 门阵多 圈1 - 5 标准单元和门阵列 3 门海设计模式( s e a - o f - g a t e sd e s i g ns t y l e ) , 进一步改进了宏单元阵列的版图 结构。它已取消了水平方向的通道，成为一种无通道( c h a n n e l 1 e s s ) 的门阵 列。一般的，功能块的形状如矩形，长宽比和位置由布图规划和布局算法 决定。 4 现场可编程门阵列( f i e l dp r o g r a m m a b l eg a t ea r r a y , f p g a ) ：是一种可编程 - 6 第一章绪论 器件( 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 提供了用户可编程和自己制造的能力，极大的 缩短了设计和制造的时间，节省了费用。但这种设计方式的版图，冗余面 积较多，适于单件或批量很小的产品 1 4 本论文完成的工作和内容组织 本文工作研究的是v l s i 物理设计中的布局问题。在d s m 和v d s m 半导体集 成工艺下的大规模集成电路设计中，布局结果的好坏直接影响整个布图设计，因 此如何高效地表示布局结构，从而提高布局质量成为布图设计中的一个国际研究 热点。本文较详细地回顾了当前国内外较流行的布局结构的表示方法及进展状况， 以及布局启发式算法，然后设计了求解v i _ s i 布局问题的启发式算法，通过设计模 块的优先顺序进行合理的布局，再辅助于边界矩形来减少边界浪费，对于模块布 局放置的多个可能位置进行比较，并将其放置在优先度最高的适当区域，取得了 较好得初始布局结果。最后展望研究布局结构的表示时，讨论了应用智能优化算 法，借以求解更大规模电路的布局问题。 论文的内容安排和组织如下：第二章v l s i 布局中的基本问题，第三章v l s i 柿局问题的启发式算法，第四章b b l 的布局表示方法的评述，第五章一种改进的 v l s i 布局算法，第六章总结与展望。 7 电子科技大学硕士学位论文 第二章v l s i 布局中的基本问题 布屑j ( p l a c c m e n t ) 是集成电路自动布图设计的重要环节之一：布局就是把元件或 模块安置在芯片或印刷电路板的适当位置，并使其满足一定的目标函数。布局阶 段的输入是一组模块、模块上的引线端信息和网表，如果模块内的电路版图已经 完成，则该模块的形状大小已知，此类模块称为“硬模块”( h a r db l o c k ) ，另一类 需要在布局阶段确定其形状和大小的模块则称为“软模块”( s o f tb l o c k ) 。通常所 说的“布局问题”是指待安置的模块均是形状和大小已知且固定的硬模块( h a r d b l o c k ) ，此时只需考虑给每个模块在芯片上分配一个位置。当模块中包含需要在布 局阶段确定其形状和大小的软模块( s o f tb l o c k ) 时，此时的布局问题成为“布图 规划”( f l o o q s l a n n i n g ) 问题。可见，布局问题仅是布图规划问题的一个特例。 由于布局的对象不同，布局问题的详细含义和目标会有所不同：通常的目标 是芯片的面积最小、总连线长度最短和能提供商的布通率等等。 2 1 布局问题定义 下面给出布局问题的正式定义： 设b 1 ，b 2 ，b n 是需要放置在芯片上的单元，每一个b i ( k k n ) ，它都有一个 高度h i 和宽度w i 相联系。n = n 1 ，n 2 n 。 表示连接不同单位的线网的集合， q = q l ，q 2 q k 表示单元间用于布线的空区域，“1 i m ) 表示估计的线网n i 的 长度。布局问题就是为每个单元寻求一个矩形区r = ( r 1 ；r 2 r 。) ，使得： 1 每个单元都能放置入它相对应的矩形区域，也就是说，r i 具有w i 的宽度和 h i 的高度 2 任意两个矩形不重叠。r i f lr j = 空，if - j ，1 i ，j n 3 布局是可布的。即q j ( i j k ) 足够用于布线。 4 所有r i ( k k n ) 和q j ( 1 j ：形。 召- 其中，k 是一种线网连线长度的估算公式，w 。是线网n 的权重，n 为所有线网的 集合。连线总长最小还可以用割线数总和最小来表示： m 组g 一 单元张力总和最小也常作为改善布局的目标函数。它是基于这样的数学模型： 所有单元被放在一个无摩擦力的液体上而，单元间彼此受拉力和斥力作用，单元 间的拉力大小和它们的连线数成正比。当单元重叠时，它们间的斥力将它们分开。 另外，门阵列布图模式改善布局的目标是可布性好，即希望线网均匀分布， 其目标函数为： m i n ( m a x e ) 1 函数中，c l 为水平切割或垂直切割的割线数。 2 4 2基于对交换的迭代改善 基于对交换的迭代改善是一种简单而实用的迭代改善算法。它通过芯片上一 对单元的位置互换而产生一个新的布局，与不同的目标函数结合就形成了不同的 迭代改善算法。 1 成对交换法( p a i r w i s ei n t e r c h a n g e , p i ) 是最简单的对交换策略。选定一个单 元后，可依次与其它单元逐个交换位置，每次交换后计算与这两个单元相 关的线网连线总长，如果结果有改善则替代原布局。此方法较适合单元的 大小和形状差别不大的门阵列和标准单元模式。 2 力矢量成对交换松弛法( f o r c ed i r e c t e d p a i t w i s er e l a x a t i o n ，f d p r ) 是有条 件的成对交换法，减少了交换的随机性，有力改善了成对交换法在交换对 象选择上的盲目性，避免了枚举所有可能的交换。它采用了力学模型，当 两个单元问存在公共线网时，就设想存在一条橡皮带把这两个单元联结起 来，其间的拉力由虎克定律决定此方法要求寻找双方互为零张力位置的 一对单元，此条件比较苛刻，往往限制了布局的进一步改进。 3 力矢量指向交换法( f o f d i r e c t e di n t e r c h a n g e , f d 0 先计算出每个模块的 总联结度，并按此结果进行排序，选择总联结度最大的模块为主模块( a ) ， 求出该模块的零张力位置0 3 ) ，以a 和b 为对角线作一矩形，然后依次在 矩形的长轴、短轴和对角线方向上分别和与之相邻的模块进行交换，每次 1 5 电子科技大学硕士学位论文 交换后都看是否得到改善，一旦改善，则以接受此交换并产生新布局。无 论三个方向的交换都不成功还是进行了某次交换使a 到达位置b ，都选取 下一主模块重复上述过程。 2 4 3基于数学规划方法的的迭代改善 从8 0 年代中开始，出现了些基于非线性连续规划和二次规划的算法，如： p r o u d 、g o r d i a n 、r i t u a l 等。它们有一个非常好的特性：可以基于严格的数 学分析证明它们的求解质量。 布局问题的难度随着单元数目的增加而增加，因此，处理v l s i 布局问题的经 典方法是基于分而治之的策略。同样，在用二次规划求解布局问题时，为了解决 模块间的重叠问题，也引入了划分技术和分区约束，把问题转化为有线性约束的 二次规划问题束求解。划分技术在该算法中起着重要作用。 划分技术主要应考虑划分线的方向和位置的选择、划分的层次及划分后单元 的交换技术等。在采用二划分时，通常是交替选择水平和垂直划分，以使：占片得 到均匀划分。一般说来，划分层次不能太多，最终予区域内的模块数不能太少。 划分层次太多不仅增加了求解子区域全局优化的次数，增加了计算时间，而且不 一定能得到好的解。尤其对b b l 模式，子区域中模块数目太少会严重影响求解质 量。对标准单元和门阵列，一般划分到每个子区域内仅包含十几个单元较为合适。 对b b l 模式，则主要看e s o ( e x h a u s t i v es l i c i n go p t i m i z a t i o n ) 等技术的处理能力。 2 4 4b b l 模式下的布局改善 以对交换为基础的迭代改善算法由于要求模块大小相差不能太大，一般只适 用于门阵列和标准单元布局模式，基于最小割的对交换算法仍然需要进行对交换， 它同样希望交换的双方在面积上相差不能太大，b b l 模式由于模块大小不均匀和 布局不规则，很难用这些方法进行迭代改善。在可二划分的结构下的布局结果可 能用通道区交叉图，水平通道区位置图和垂直通道区位置图三种图来描述。 2 4 5 小结 如前所述，布局迭代改善方法是多种多样的，例如：最能体现分而治之思想 的基于最小割的图划分算法。基于篇幅，这里不再进行更多的说明。 1 6 第二章v i s i 布局中的基本问题 2 5 总结 本章详细讲解了布局的整个情况，布局分为初始布局和迭代改善布局两个步 骤，一个好约初始布局也为以后迭代改善布局打下一个好的基础。本文的主要研 究放在初始布局这个步骤上。 1 7 电子科技大学硕士学位论文 第三章v l s i 布局问题的启发式算法 布局问题属于组合几何学范畴， 工智能、计算机图形学、计算几何、 物体的形状，布局问题分为【1 3 l ( 1 ) 二维规则布局问题 关于布局问题的研究论文散布于运筹学、人 组合最优化等领域。根据布局空问和待布局 待布局物体和布局空间都是矩形或圆形，如底盘装载问题( p a l l e t l o a d i n g p r o b l e m ) ，一刀切问题( g u i l l o t i n ec u t t i n gp r o b l e m ) 及非一刀切问题 ( n o n - g u i l l o t i n ec u t t i n gp r o b l e m ) 等。 ( 2 ) 二维不规则布局问题 待布局物体和布局空间至少有一个是二维不规则图形。 ( 3 ) 三维规则布局问题 包括长方体、圆柱体及球体布局问题，常见的是待布局物体和布局空间都是 长方体，如集装箱布局问题( s h i p p i n gc o n t a i n e rl o a d i n gp r o b l e m ) 。 ( 4 ) 三维不舰则布局问题 待布局物体和布局空闯是三维不规则实体，如坦克舱布置设计，火箭仪器舱 内的仪器布局问题。 而在v l s i 布局中一般都是二维规则布局问题，也有二维不舰则布局问题，由 于二维不规则布局问题的复杂程度，这里我们布局问题是二维规则布局问题。 3 1 布局对象 布局对象包括布局空间和布局物体，形状都为矩形，约定长边为长度方向、 短边为宽度方向。 3 1 1布局空间 布局空间的形式有两种：第一种形式是布局空闻的大小固定，矩形的长度和 宽度已知：第二种形式是布局空问一个方向的尺寸固定，称为布局空间的宽度， 另一个方向的尺寸大小相对宽度来说大得很多，可以看作不做任何限制，要求布 局时使高度尽可能地小 - 1 8 - 第三章v i s i 布局问题的启发式算法 布局空间的初始状态，即没有放置布局物体的空间，称为原始布局空间；放 入物体后剩余的空间称为剩余布局空间；将剩余布局空间分解成几个小的布局空 间，这些小的空间称为布局子空间；欲放入物体的布局子空间称为当前布局空间。 3 1 2布局物体 布局物体为若干种大小不同的物体，一种物体的数量为一个；若有尺寸相同 者，则视为不同物体，以序号来区分。为区别于已放入布局空间的物体，称没有 放入布局空间的物体为待布局物体。 3 2 布局约束 布局问题就是要把一些布局物体按一定的要求合理地放置在一个布局空间 内。从布局问题的定义可以看出，它是由布局空间、布局物体及其相互之间的关 系和要求组成的，这些关系、要求都可认为是布局的约束1 1 4 1 。当所有的约束都被 满足时，布局问题才算得到解决。 3 2 1目标约束 目标约束足对布局问题所追求的设计目标的限定。目标约束往往被综合( 或表 达) 为布局目标，如本文研究的基于目标的布局启发式算法，就是