（电路与系统专业论文）基于SingleSequence的布图规划设计及其实现[电路与系统专业优秀论文].pdf

南京邮电人学硕- l j 研究生学位论义中文摘要 摘要 集成电路( i c ) 是在半导体基片上形成的完整的电子线路，它是上世纪五十年代术期， 随着半导体晶体管硅平面技术的发展而出现的一种新型电子器件。当日，j 芯片罩的电路与系 统同趋复杂，超大规模集成电路( v l s i ) 设计技术水平也在逐渐提高。v l s i 设计中一般采用 分级设计的方法，这种设计方法是将v l s i 这一复杂的电路系统分解成许多可处理的子系 统。布图设计过程是整个v l s l 分级设计中非常关键的步骤之一，它的目的是将电路元件说 明和网络表产生出版图。在布图设计中，一般是以具有一定逻辑功能的单元作为基本电路， 其中积木块布图设计( b u i l d i n gb l o c kl a y o u t ，b b l ) 是以任意形状模块作为基本单元的一种 设计模式，它对于通用芯片的设计具有很实际的意义。 本文首先介绍了v l s i 设计的分类、几种全定制模式下常用的设计方法以及布图设计自 动化的重要性。然后介绍了s i n g l e s e q u e n c e 的编码和解码方法，它使布图规划与 s i n g l e s e q u e n c e 对应起来，这样的编码易于计算机识别，同时介绍了s i n g l e s e q u e n c e 的一些 性质和应用。接下束介绍如何运用模拟退火( s i m u l a t e da n n e a l i n g ) 算法对布图规划进行优 化。这样，整个布图规划的优化问题就转化为编码变换的问题，其中又介绍了一些算法如 约束图的生成算法及关键路径算法等。在编码变换达到最优情况下，将经变换的编码解码 成布图规划，这样实现了从初始图至【 最优图的一个过程，并给出实验结果。最后，是本文 的主要研究成果，在f i i 面介绍的基础上，首次将s i n g l e s e q u e n c e 用于解决约束条件如边界 约束和相邻约束下的布图规划优化问题，阐述了约束条件并提出了判断s i n g l e s e q u e n c e 是 否满足约束条件的算法，最后给出了完整解决方案。同样给出实验结果，并与传统方法进 行了比较。实验结果表u y j s i n g l e s e q u e n c e 在解决模块之间的相邻、模块与芯片边界相邻以 及芯片布局面积最小化等多目标优化时非常实用有效。 关键词：布图规划；s i n g l e s e q u e n c e , 单元；模块；模拟退火 南京邮l i 三人学硕i j 研究生学位论文英文摘要 a b s t r a c t t h ei n t e g r a t e dc i r c u i t ( i c ) i si n t e g r a t e de l e c t r o n i cc i r c u i tp r o d u c e do nas i l i c o nw a f e r f r o m t h ee n do f19 5 0 s ，i ta p p e a r e da san e wk i n do fe l e c t r o n i cc o m p o n e n tw i t ht h ed e v e l o p m e n to f s e m i c o n d u c t o rt e c h n o l o g yo ns i l i c o np l a n e t h ec i r c u i t sa n ds y s t e m so nc h i pb e c o m em o r ea n d m o r ec o m p l e xa n dt h ev l s id e s i g nt e c h n o l o g yi sa l s oi m p r o v e dq u i c k l y t h eh i e r a r c h i c a ld e s i g n i s w i d e l yu s e di nv l s id e s i g n t h i sm e t h o dd e c o m p o s e st h ec o m p l e xv l s ii n t om a n y s u b s y s t e m sw h i c hc a nb ep r o c e s s e de a s i l y t h ef l o o r p l a nd e s i g ni st om a k eaf l o o r p l a nf r o mt h e c i r c u i tc o m p o n e n t sd e s c r i p t i o na n dt h en e t - l i s t s i ti sac r i t i c a l s t e pi nt h ew h o l ev l s id e s i g n p r o c e s s 。t h eb a s i cc i r c u i tm o d u l ei st h eu n i tw i t hl o g i cf u n c t i o ni nt h ef l o o r p l a nd e s i g n t h e b u i l d i n gb l o c kl a y o u t ( b b l ) d e s i g ni so n eo ft h e mw h i c hu s ea n ys h a p ea sb a s i cm o d u l e s i n c e b b li so f t e nu s e da st h eg e n e r a li cd e s i g ns t y l e ，i th a sr e a l i s t i cs e n s e t h i sp a p e ri n t r o d u c e ss o m ek i n d so fv l s id e s i g nm e t h o d sa n dt h em e t h o d si nf u l l c u s t o m d e s i g ns t y l e a n dt h ei m p o r t a n c eo fa u t o m a t i c f i o o r p l a nd e s i g n t h e n i ti n t r o d u c e st h e s i n g l e s e q u e n c er e p r e s e n t a t i o nm e t h o da n di t sp r o p e r t i e s ，i n c l u d i n gs o m ea p p l i c a t i o n so ft h i s r e p r e s e n t a t i o nm e t h o d i tm a k e sf l o o r p l a nc o r r e s p o n dt ot h es i n g l e s e q u e n c ee x c l u s i v e l y t h i s k i n do fc o d ec a nb ee a s i l yr e c o g n i z e db yac o m p u t e r a f t e rt h a t ，t h ep a p e ri n t r o d u c e sh o wt o o p t i m i z eaf l o o r p l a nw i t hs i m u l a t e da n n e a l i n ga l g o r i t h m a st oo p t i m i z eaf l o o r p l a n ，t h ep r o b l e m c o n v e r t st oc o d em o v i n g a f t e rh a v i n gg o t t e nt h eb e s tc o d e ，i ti sd e c o d e dt oaf l o o r p l a na g a i n 。s o t h ew h o l ef l o o r p l a no p t i m i z a t i o np r o c e s sr e a l i z e sf r o ma l li n i t i a lf l o o r p l a nt oaf i n a lf l o o r p l a n t h e ne x p e r i m e n tr e s u l ti sg i v e n a tl a s t ，t h em a i ns t u d yr e s u l to ft h i sp a p e ri sp r o p o s e d b a s i n g o nt h em e n t i o n e da b o v e ，t h i sp a p e rr e s o l v e sf l o o r p l a no p t i m i z a t i o nw i t hc o n s t r a i n tc o n d i t i o n s ， s u c ha sb o u n d a r yc o n s t r a i n t sa n da b u t m e n tc o n s t r a i n t sf o rt h ef i r s tt i m e a f t e rd e s c r i b i n gt h e c o n s t r a i n tc o n d i t i o n si tp r o p o s e st h ea l g o r i t h m sf o rj u d g i n gw h e t h e ras i n g l e - s e q u e n c es a t i s f i e s t h ec o n s t r a i n tc o n d i t i o n sa n dt h ew h o l es o l u t i o n t h ee x p e r i m e n tr e s u l tc o m p a r e dw i t ht h e t r a d i t i o n a lm e t h o di n d i c a t e st h a ts i n g l e - s e q u e n c ei sap r a c t i c a b l ea n de f f e c t i v em e t h o di n r e s o l v i n gf l o o r p l a no p t i m i z a t i o np r o b l e mw i t hm u l t i o b j e c t i v e ，s u c ha sm o d u l ea b u t m e n tw i t h e a c ho t h e r ，m o d u l ea b u t m e n tw i t hc h i pw a l l sa n dt h ec h i pa r e am i n i m i z a t i o n k e y w o r d s ：f l o o r p l a n ，s i n g l e s e q u e n c e ，r o o m ，m o d u l e ，s i m u l a t e da n n e a l i n g 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：之丝判日期：左她鲴 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：记叁互4 一导师签名：监日期：之兰兰：兰：! 厂 南京邮电大学硕士研究生学位论文第章绪论 第一章绪论 1 1v l s i 布图设计的目的与意义 从上世纪5 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 m e g l 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 ，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 ，v l s i ) 的发展，人们已经可 以在单个芯片上制作包含上千万个晶体管的完整数字系统或数、模混合的电子系统，其设 计自动化的问题也就愈来愈受到人们广泛的关注。实践证明，v l s i 的设计离开设计自动化 ( 计算机辅助设计) 已经寸步难行i l l 。 布图设计作为整个集成电路设计过程中与产品研制和生产直接相关的一个设计过程， 是设计中费时最长和差错率最高的设计步骤之一。它直接关系到v l s i 的设计周期、成本 和产品质量。布图设计过程是一个由电路元件说明和网络表产生出设计好的版图的过程。 通常情况下，整个布图设计过程包括划分( p a r t i t i o n ) 、布图规划( f 1 0 0 叫撇i n g ) 、布局 ( p l a c e m e n t ) 、布线( r o u t i n g ) 和压缩( c o n l p a c t i o n ) 五个过程【2 1 。布图设计自动化就是利用计算 机作为辅助工具来实现布图设计的过程。 布图设计自动化在v l s i 制造过程中的重要性，一方面主要表现在缩短整个设计周期， 减少人工的投入，使成本降低，最大程度地提高v l s i 的生产效率，在人工设计时，设计 周期是与设计规模的2 3 次方成正比的，而目前已经开发的布图设计系统，虽然与人工设 计相比已经提高一个数量级以上，但其核心算法仍需很大改善；另外一方面主要表现在其 可以方便地进行设计正确性的验证，对于人工设计或人机交互式设计方式，设计的正确性 很大程度上依赖于设计者的经验和专业素养，这种情况下的差错率非常高，并且出现同类 错误时也很难检查。而采用设计自动化技术进行布图设计，由于遵循一定的方法，数据由 计算机统一管理，与此同时，又发展一系列相应的正确性验证的手段，从而就可基本上解 决设计正确性的验证问题，很大程度上提高设计成功率。 1 2v l s i 设计及布图设计模式的分类 从芯片的设计要求开始到芯片封装结束，v l s i 设计过程要经过若干步骤： ( 1 ) 系统规范说明( s y s t e ms p e c i f i c a t i o n ) 南京邮电大学硕士研究生学位论文第一章绪论 同其它设计一样，v l s i 设计首先要给出待设计系统的规范说明，包括系统功能、性 能和物理尺寸。此外，还需要考虑选择设计模式和制造工艺。最终结果是确定芯片尺寸、 工作速度、功耗和系统功能。 ( 2 ) 功能设计( f u n c t i o nd e s i g n ) 这一步骤主要是考虑系统的行为特性，常用的方法是用时序图或表示各子模块间相 互关系的关系图。利用这些信息可以改进整个设计过程或简化后续的设计步骤。 ( 3 ) 逻辑设计( l o g i cd e s i g n ) 这一步骤可以得到一个表示系统功能的逻辑结构，并反复测试其正确性。设计者通 常用文本、原理图或逻辑图表示设计，有时也用布尔方程表示设计。在设计过程中，还要 对该逻辑结构进行模拟以验证其正确性，并对其进行优化设计或称之为逻辑最小化。 ( 4 ) 电路设计( c i r c u i td e s i g n ) 电路设计时要考虑逻辑部件的电路实现，包括速度和功耗。此外，还要注意各种元件 的电性能，通常用详细的电路图来表示电路设计。 ( 5 ) 物理设计( p h y s i c a ld e s i g n ) 物理设计即布图设计，是v l s i 设计中最费时的一步。物理设计要把每个元件的电路 表示转换成几何表示，同时，元件间连接的线网也被转换成几何连线图形，这样的电路几 何图形表示称为版图。布图设计要符合与制造工艺有关的设计规则要求。由于布图设计的 复杂性，往往把布图设计分成布图划分、布图规划和布局、总体布线、详细布线等几个子 步骤进行。 ( 6 ) 设计验证( d e s i g nv e r i f i c a t i o n ) 在布图设计完成并得到以几何图形形式表示的版图以后，要进行设计验证，以确保 版图满足制造工艺要求和符合系统的设计规范。版图验证包括设计规则检查( d e s i g nr u l e c h e c k i n g ，d r c ) 、版图的电路网络表提取( n e tl i s te x t r a c t i o n ，n e ) 、电学规则检查( e l e c t r i c a l r u l ec h e c k i n g ，e r c ) 矛i 寄生参数提取( p a r a m e t e re x t r a c t i o n ，p e ) ，经过验证后的版图可以 送去制作掩模版并用于制造芯片。 ( 7 ) 芯片制造( f a b r i c a t i o n ) 芯片制造过程包括硅片准备、杂质注入、扩散、光刻等工艺。一个直径为1 0 厘米的 圆硅片大约可制作1 2 到3 0 个芯片。 ( 8 ) 封装和测试( p a c k a g e a n dt e s t ) 在完成芯片制造后，要进行封装和测试。安置在印制电路板( p r i n t e dc i r c u i tb o a r d ，p c b ) 上的芯片可封装成双列直插式( d u a li n 1 i n ep i n ，d i p ) 或引脚阵列式( p i ng r i da r r a y ，p g a ) ， 2 南京邮电大学硕士研究生学位论文第一章绪论 用于多芯片模块( m u l t i p l ec h i pm o d u l e ，m c m ) 上的芯片可不封装。 v l s i 设计可能会在其中一个步骤中或在几个步骤之间反复交替进行，其设计流程如 图1 1 所示。 晶体管电路 上 布图规划 l 布局 上 总体布线 j 详细布线 j l a y o u t 图1 1v l s i 设计流程 在整个设计过程中，布图设计是v l s i 设计中的一个关键环节。按照设计自动化程度 来分，可将布图设计方法分成手工设计和自动设计两大类。手工设计方法中又可分成基于 图形的交互图形编辑方法和基于符号的交互图形编辑方法。按照对布局布线位置的限制和 对布局模块的限制来分，则可以把设计方法分成全定制( f u l l c u s t o m ) 和半定制 ( s e m i c u s t o m ) 两大类，也称为全定制模式和半定制模式。 全定制模式对模块的布局位置没有限制。整个芯片的电路被划分成一些子电路，每个 子电路是一个模块。在通常情况下，模块的外形和放置位置都没有限制。除了模块所占据 区域以外的芯片区都是布线区。对于三层和三层以上布线工艺的布图设计，模块上面也可 以走线，只是其走线层数有所限制。因此，全定制设计模式除了要遵循最基本的几何设计 规则之外，几乎没有任何其它附加的物理限制。 全定制模式有交互图形编辑，符号法和积木块自动布图三种c a d 的方法服务于它。 南京邮电大学硕士研究生学位论文 第一章绪论 交互图形编辑是一种手工设计方法，也是一种传统的设计方法。设计者将手工设计好的版 图草图用一个交互图形编辑器( i n t e r a c t i v eg r a p h i ce d i t o r ) 输入到计算机并进行编辑；另外， 设计者也可以直接在屏幕上绘制版图。编辑器提供有插入、移动、删除、复制、拉伸等命 令，并辅以开窗、缩放、窗口移动等显示命令和文件处理命令，使设计者能方便自由地在 屏幕上绘制和编辑版图。这种方法可以得到高集成度和高性能的芯片，适合广泛用于大批 量产品的设计，缺点是设计效率低，设计时间长。 符号法版图设计方法( s y m b o l i cl a y o u ta p p r o a c h ) 也是一种人工设计方法，它使用晶体 管、通孔和连线的符号进行输入和编辑并产生一个拓扑版图，然后再根据给定的设计规则 将它转换成物理版图。不同工艺的晶体管、通孔和连线的符号以及它们相应的物理版图由 符号法版图编辑器事先制作好并存放在单元库中。器件尺寸和线宽可根据给定的设计规则 而进行相应的调整。直接由拓扑版图转换而成的物理版图往往有较多的冗余空间。因此， 符号法版图编辑器中还需提供版图压缩功能，以减小版图面积。符号法版图设计方法保持 了交互图形编辑方法所具有的较高布图密度和灵活性的优点，且由于设计规则是由符号法 版图编辑器维持的，用户在操作时无需考虑，因而大幅度地降低了设计工作量。 髓 桃 逻 鬈 图1 2 b b l 版图结构 积木块自动布1 蛩( b u i l d i n gb l o c kl a y o u t ，b b l ) 是任意形状单元布副3 1 ，图1 2 表示b b l 版图结构。限于当前实现的条件，目前的b b l 模式中的模块都简化为矩形，但它们可被 安置在芯片的任何位置上。模块版图可以是手工设计，也可以是用其它设计方法，如门阵 列，标准单元或者是用b b l 方法本身进行设计。如果在设计中还用其它自动设计方法设 计模块版图，那么整个芯片的设计就成为分级设计( h i e r a r c h i c a ld e s i g n ) 。分级设计可以降 4 南京邮电大学硕士研究生学位论文第一章绪论 低每个级别设计的复杂性，有利于自动设计技术的实现，但它可能要牺牲芯片面积的优化。 未被模块占有的芯片空间为布线区，b b l 模式下的布线区比较复杂，通常要先把它们划 分成矩形的通道区，然后再按一定次序逐个进行布线。传统的布线工艺用两层金属，此时 模块上面不能走线。随着三层和四层金属布线工艺的出现，模块上允许走三、四层线，出 现了跨单元布线( o v e rt h ec e l lr o u t i n g ，o c t ) 技术，它使得布线区域大大减少。b b l 模式 既具有布图密度高和布图灵活的优点，又具有自动设计高效率的优点，是一种很理想的设 计方法。但由于b b l 的布图算法和布图系统较其它设计方法复杂，目前还没有一个很成 功的实用系统。本篇论文的着手点，就是b b l 模式下如何对布图规划进行优化。 1 3 研究背景与现状 布图规划就是求解可变形状模块或称软模块的布局问题。布图规划和布局是布图设计 流程中的较早阶段，其完成的质量对布线工作的顺利完成乃至最终芯片的面积和性能的影 响非常大。另外，标准单元与宏模块一起的混合模式布局、模拟电路器件布局、数模混合 集成电路设计模式、多芯片集成设计模式以及采用知识产权模块( 即i p 模块的设计模式) 等都是积木块布图模式的布图规划和布局问题。许多学者提出了不同的b b l 布局算法。 早期关于b b l 布局的算法，如最小割法和力向量法等，都是从已有的门阵列和标准单元 的布局算法中受到启示加以模仿和引伸而得到的。其它方法还有：力构造法、2 d 边界搜 索方法、分级设计方法、分支限界法、解析型算法( 数学规划算法) 、模拟退火或遗传算法 ( 随机优化算法) 、机器学习和神经网络算法、模糊数学方法等等。其中许多算法与处理小 单元的布局算法非常类似，并没有考虑到宏单元或大模块布局的特点。 随着多层布线工艺的成熟和普及，跨单元( o v e rc e l l ) 布线得到了广泛应用，使得 n o n s l i c i n g 结构布局的优越性就更加明显。基于随机优化算法的布图规划与布局的关键 是要找到布局构形的有效表示形式，这一表示应当满足以下条件： ( 1 ) 表示的完备性，即对每一个布局存在一个相应的表示，以保证解空间中包含最优 解。 ( 2 ) 表示的是模块之间的拓扑关系，可以在表示与模块尺寸无关的条件下，对模块的 形状进行优化。 ( 3 ) 无冗余性，不存在多个表示对应同一个布局的情况发生，以保证计算效率。 ( 4 ) 表示与布局之间的转换计算复杂度低，这样在随机优化算法中对一个布局进行评 价时就可以节省时间，从而使算法的整体计算时间缩短。考虑到布局问题巨大的解空间， 5 南京邮电大学硕士研究生学位论文第一章绪论 这一点是算法实用化的关键。 ( 5 ) 表示的空间复杂性很低，当使用遗传进化算法时，这一点是很有用的。 一直以来对布图设计的研究很多。早在1 9 8 6 年，w o n g 和l i u 首次提出了s l i c i n g 结 构的p o l a n d 表达式表示【6 】，并使用该表示法得到了一个有效的模拟退火布局算法。为了 能表示一般性的b b l 结构，即n o n s l i c i n g 的布局结构，有人曾试图将s l i c i n g 的结构表 示进行推广，但效果并不理想。1 9 9 5 年，m u r a t a 等人提出了序列对结构( s e q u e n c ep a i r ， s p ) i 拘表示。1 9 9 6 年，n a k a t a k e 等人提出了b s g ( b o u n d e ds l i c i n go r i d ) 结构对一般的 n o n s l i c i n g 布局问题进行了成功的尝试。对含有甩个模块的布局问题，所有序列对的集合 是一个布局问题的解空间，共含有( ，21 ) 2 个序列对，每个都可以在o ( 甩2 ) 时间内对应到一 个布局，其中至少有一个序列对对应最优的布局。之后，w o n g 等人已经将序列对的计算 复杂性降低到o ( 1 9 ( 1 9 n ) ) 。b s g 是一种变形的网格，为了保证最优布局，n x 门网格的b s g 计算复杂性同样为o ( n 2 ) ，其解空间为c ( 玎2 ，玎) ，这个数目远远大于( ，z ! ) 2 。s e q u e n c e p a i r s ( s p s ) 8 1 是用于解决p a c k i n g 问题的一种比较好的办法【9 】【1 0 1 。稍后还有t r a n s i t i v ec l o s u r e g r a p h ( t c g ) 】，它的冗余度可以导致更大的解空间。1 9 9 9 年，g u o 和c h e n g 提出了有序 树，即o t r e e 表示【1 2 】。这一表示的解空间比序列对和b s g 都要小，而且其计算复杂性仅 为o ( n 1 。但这一表示与模块尺寸有关，由于这一布局表示在计算评估时有额外的压紧操 作，事实上其计算复杂性比论文中提出来的要大许多。2 0 0 0 年，y c c h a n g 等人对o t r e e 表示进行了改进，得到了文献 5 】中b * - t r e e 表示法，但这一改进的意义并不大，一些其它 的表示在学术上的影响也非常有限。基于随机优化布局算法，董社勤和洪先龙等人提出了 角模块( c b l ) 的表示形式【1 3 】【14 1 ，即平面矩形区域( 芯片) 用垂直于区域边界的直线进行任意 划分后得到的布局。2 0 0 2 年，y 。k a j i t a n i 和s a k a n u s h i 等人提出了q 序列的表示法【1 5 】【1 6 】， 通过一种简单的编码形式，成功的解决了从布图规划到计算机编码的对应，是一种比较实 用有效的方法。2 0 0 4 年，赵华安和刘陈等人在q ，序列的基础上提出了e q 一序列【i7 1 ，解决 了不能直接通过q 序列判断邻接单元的位置情况，可以有效地解决模块与边界邻接的问 题。2 0 0 3 年，y k a j i t a n i 等人提出了s i n g l e s e q u e n c e 18 1 ，它是一串整数序列，所以其形 式非常简单，便于计算机处理。 1 4 本文研究内容及论文结构 本文概括性地介绍了整个v l s i 设计过程以及布图设计在其中的重要性和意义，介绍了 6 南京邮电大学硕士研究生学位论文 第一章绪论 在全定制模式下几种常用c a d i 具实现的方法，其中着重说明t b b l 布图设计方法。通过 引入阿部顺序的概念，介绍了s i n g l e s e q u e n c e 这一表示法，以及此编码与布图规划之间的 对应关系，通过编码变换等方法实现布图规划的优化过程。最后提出了在一定约束条件下 进行布图规划的方法，它在解决模块之间的相邻、模块与芯片边界相邻以及芯片布局面积 最小化等多目标优化时非常实用有效。 本论文在第一章的绪论部分描述t v l s i 布局的目的与意义、v l s i 设计过程和布图设计 的分类以及当前的研究背景与现状；第二章引入阿部顺序、t 型交叉布图以及a b l r 系统等 概念，介绍了 s i n g l e s e q u e n c e l 拘定义、s i n g l e - s e q u e n c e l 拘编码特性以及如何从布图解码成 s i n g l e s e q u e n c e ，并介绍了布图规划的全列举及应用；第三章讲述了布图规划如何优化的 问题，介绍了如何生成初始解、基于s i n g l e s e q u e n c e 的局部变换，接着详细介绍了模拟退 火算法的模型，以及通过建立模型对布图规划进行优化，最后给出实验数据；第四章详细 阐述了s i n g l e s e q u e n c e 在边界约束条件下的布图规划优化问题以及基于s i n g l e - s e q u e n c e 表 示的模块邻接问题及其解决方法。最后仿真结果表i j f s i n g l e s e q u e n c e 在解决多目标条件下 的布图规划优化问题非常有效。最后一章是对前面各章的总结，对本文的工作给予结论， 并对今后的研究提出了课题。 南京邮电大学硕士研究生学位论文第二章s i n g l e - s e q u e n c e 及其应用 第二章s i n g l e s e q u e n c e 及其应用 在v l s i 布图设计的所有子步骤中，首先做的步骤是布图划分。由于一个芯片可能要包 含上千万个晶体管，加之受计算机存储空间和计算能力的限制，通常要把整个电路划分成 若干个模块，将待处理问题的规模缩小。如果模块内的器件数还太多，还可以进一步把模 块划分成一组子模块。划分时要考虑的因素包括模块的大小、模块数目和模块之间的连线 数等。在划分后，一般根据其包含的器件数估计模块的面积，再根据该模块和其它模块连 接关系以及上一层模块或芯片的形状估计该模块的形状和相对位置。其次是布图规划和布 局，布图规划的任务是要为整个芯片和每个模块选择一个好的布图方案。布图规划在整个 布图设计中占有重要地位。布局的任务是要确定模块在芯片上的位置，其目标是在保证布 通的前提下使芯片面积尽可能最小。由于布局问题比较复杂，通常把布局分成两步完成： 初始布局和改进布局。一般情况下，在初始布局时用构造的方法给出布局问题的初始解； 然后，通过迭代改进方法以优化布局结果。 早期的时候，对芯片里各个模块进行放置的方法，大多是直接确定模块位置，比如有 力向量平衡法结构法、力矢量松弛法等。近年来，通过预先对平面图划分区域，然后在相 应的区域里投入电路模块的方法用的比较多。这样，如何有效地划分好平面布图区域成了 问题的关键。通常，一个已经划分好区域的平面图可以用某种编码来表示，对于计算机来 说，编码更容易被识别和处理。布图规划的优化效率，一方面依赖于编码的长度，另一方 面也依赖于解码速度。s i n g l e s e q u e n c e 就是一种有效的表示法，它有着编码形式简单、变 换直接方便以及解码速度快的特点。 2 1 s i n g l e s e q u e n c e 的定义 2 1 1 定义的引入 积木块模式的版图结构可以划分为两种类型，即可二划分的( s l i c i n g ) 结构【4 】和不可二划 分的( n o n s l i c i n g ) 结构i 5 1 。所谓s l i c i n g 结构是指可以通过水平或垂直分割线将芯片所在的矩 形划分成两个区域，而且这一过程可以递归地进行直到每个子区域只能容纳一个模块为 止。s 1 i c i n g 结构表示的布图规划非常有限，因为绝大部分划分是n o n s l i c i n g l 拘。n o n s l i c i n g 结构的布局是指不一定具有s l i c i n g 结构的一般的布局结构。这种结构由于具有一般性以及 8 南京邮电大学硕士研究生学位论文第二章s i n g l e s e q u e n c e 及其应用 其布图的高密度性而受到人们更多的重视。布图规划技术的产生是由于积木块模式分级设 计的需要。在这里所谓的布图规划，它不同于组装( p a c k i n g ) 。刀个模块的p a c k i n g ，是指在 方形区域内放a n 个模块，只要模块不产生重叠，不论模块如何摆放，目标是使这个方形 区域面积最小就行了。而对于布图规划，是指先对一个方形芯片正好切分成n 个小方形单 元，每个单元必须对应放入一个模块。例如，对于4 个高与宽的数据分别是这样的模块： a ：3 2 ，b = 2 x3 ，c = 2 x 4 以及d - - - 3 3 。如果按照p a c k i n g 的方法，可以组成图2 1 ( a ) 所示 的图形，可以得到最小方形区域面积为3 0 ；按照布图规划的方法，先要对方形区域划分成 4 q 单元，然后在每个单元里投入一个模块，这样只能得到如2 1 ( b ) 图，其最小方形区域面 积为3 2 。 a ， c d ， b 图2 1p a c k i n g ( a ) 与布图规j e l j ( b ) 的比较 布图规划问题的输入是电路的网络表、模块的面积估计以及模块的初始形状；其输出 是所有模块的最佳形状和它们的位置。本论文里采用的是准任意单元模式，即所有单元为 大小不同的矩形，其i o 口排列在矩形的四个周边。这样前提下的布线通道必然会形成通道 区的交叉图，对平面图来说，这些布线通道区成为布图规划里的分割线。布图中的垂直分 割线和水平分割线互相t 形交叉，这样的布图被称为t 形交叉布图。本文的研究重点就是该 种形式的布图规划。 s i n g l e s e q u e n c e 就是表示布图规划的一种较好的编码方法，对于n 单元的布图规划， 它是一串包含l ，2 ，3 ，门得整数序列，并且有门! 种变换，其中的整数表示单元，当s s 用于解决p a c k i n g l p j 题时，则表示模块。在得知布图规划的阿部顺序的前提下，通过一定的 方法就可得到与布图规划对应的s i n g l e s e q u e n c e 。后面几节将作详细介绍。 2 1 2t 形交叉布图规划 所谓胆单元的t 形交叉布图，就是用刀一1 条分割线对矩形平面( 芯片) 进行划分后得到一 个包含胛个矩形单元的图形。图2 2 为单元数”= 8 时的t 形交叉布图。芯片里的垂直分割线 9 南京邮电火学硕士研究生学位论文 第二章s i n g l e - s e q u e n c e 及其应用 和水平分割线不允许交叉穿过，只形成t 形交叉：矩形平面四周的边也作为单元外部的分 割线，根据四周边位置分别称为顶墙( 孵) 、底墙( ) 、左墙( 睨) 、右墙( ) 。对于平面上 除右下单元外的任意一个单元f ，两分割线相交构成单元f 的右下角，其中一条分割线形成 t 形交叉的截止边，此截止边记为该单元的p r i m e 边防。对于一个单元f ，与它的p r i m e 边邻 接，并且位置处在单元f 另一侧的所有单元的集合称为相关单元集( a s s o c i a t e dr o o ms e t ) 。 当单元f 的p r i m e 边为水平分割线时，集合里单元的顺序是从左至右排列；当单元f 的p r i m e 边为垂直线时，集合里单元的顺序是从上至下排列。排在序列里第一个( 或唯一的) 单元称 为单元f 的次单元( n e x tr o o m ) 。图2 2 中，图上所标记的分割线分别为单元a ，b ，c 的p r i m e 边，单元b 的相关单元集包括单元d 和单元e ，其中单元d 是单元b 的次单元。 2 1 3 阿部顺序 图2 28 单元t 形交叉布图 阿部顺序( a b eo r d e r ) 1 9 是布图中依次访问所有单元的一种方法。对于t 型交叉的布图， 首先将布图中左上角的单元标为l ，然后看它的右下角，如果p r i m e 边垂直( 水平) ，则将p r i m e 边的另一侧最上面( 最左边) 的单元标为2 ，继续这个过程直到右下角i 拘r o o m 被标识。如图2 3 所示。 1 0 南京邮电大学硕士研究生学位论文 第二章s i n g l e s e q u e n c e 及其应用 幽2 3 布图的阿部顺序标记过程 定理2 1 - 对于布图规划里的各个单元，根据单元的阿部顺序能给出各p r i m e 边的顺序。 证明：所有各单元正好可以一次性地根据阿部顺序给出。对于芯片的最左上单元，很明显 可以由第一个阿部顺序分配。对于最左上单元以外的任意一单元f ，单元f 上面分割线作为 s t ，左分割线作为观。假定左分割线与上面分割线相交成为截止边，这个时候因为乩不 是芯片的左墙，看旺左侧有几个单元，把那些单元里最下面的单元作为i 。因为既是单 元i 的p r i m e 边，单元i 是单元j 的唯一的次单元，所以单元f 和单元f 的下面的顺序能被 分配。同时，如果f 有唯一能被分配的顺序，f 。也可以对应该顺序被分配，s 丁与乳交换位 置的时候也同样成立。反过来，如果f 的阿部顺序没有被分配，作为f 。次单元的f 的下面单 元，同样没有被分配的阿部顺序的单元也应该存在，可是，这样违反了顺序被给予芯片的 左上单元这样的条件，所以，所有的单元都有p r i m e 边的阿部顺序。因此，阿部顺序下的f 的 单元名，与其p r i m e 边的名字的阿部顺序相对应。 阿部顺序的一个重要性质就是它唯一标记了布图规划中的单元，从布图规划的左上角 开始到右下角结束，因此每个单元都有一个独一无二的阿部顺序。假设，和k 是布图规划 中的两个单元，如果 ，则单元在单元k 的左边或上面( 右边或下面) 。阿部顺 序是布图规划的基础。 2 1 4a b l r 关系 a b l r 关系口0 1 描述了布图规划中单元之间的位置关系。矩阵a b l r 将布图规划中单元 的位置关系用公式的形式表示出来，其定义如下：行和列表示矩形单元的标记，并以相同 的次序排列。( x ，y ) = a ( b ，l ，r ) ( 其中五夕是矩形单元的标记) 表示单元x 在单元y 之上( 或 者表示单元x 在单元j ，之下，或者表示单元石在单元少之左，或者表示单元工在单元少之 南京邮电大学硕士研究生学位论文 第二章s i n g l e - s e q u e n c e 及其应用 右) 。下面是包含4 个单元( 口，b ，c ，d ) 的布图的例子。 么舭r = 彳三= 幸，三，彳，三 r ，木，a ，a b ，b ，木，三 r ，b ，r ， 宰，三，彳，三 一，木，a ，a 一，一，乖，三 一一一幸 ， ( 2 1 ) ( 2 2 ) 因为( t 夕) = 曰和( y ，z ) = a 表示的意思相同，( x ，y ) = r 和( y ，x ) = l 也表示相同的意 思，因此可以用“一”来表示矩形中的占和r ，但没有损失任何信息，得到一个由式( 2 2 ) 表示的矩阵爿三。同样的方法可以得到矩阵b l ，a r 和b r 。观察发现么上是一个上三角阵， 这不是偶然的。有如下的定理： 定理2 2 ：一个a b l r 关系是固定不变的如果有两种矩形次序，分别被称为主次序和次序 列，前者与上三角阵彳相对应，后者与上三角阵b l 对应。 在上面介绍的例子中，( 口，b ，c ，d ) 就是主次序。在得到矩阵毗之前，先把矩阵标识 口，b ，c ，d 分别换成整数1 、2 、3 、4 ，然后用( y ，x ) - - b 来替换( x ，y ) = a ，就得到如下式表 示的矩阵b l 。通过重新排列矩形单元的次序，可以得到一个上三角矩阵b l ，如式所示。 序列( 3 ，l ，4 ，2 ) 就被称为次序列。事实上，布局就是把模块嵌入到t 型交叉的布图的单元 中，或者留空，但它们的a b l r 关系不变，如图2 4 所示。 ( b ) 图2 4 具有相同a b l r 关系的三个布图规划，次序列为( 3 ，1 ，4 ，2 ) 如果表示单元的标识是整数，可以很容易得到下面的定理。 定理2 3 ：对于( x ，少) 如果x 少，则在上三角阵舭中对应位置上的字母为三( 表示单元x 在 单元y 之左) ，否则对应位置上的字母为b ( 表示单元x 在单元y 之下) 。 1 2 南京邮电大学硕士研究生学位论文 第二章s i n g