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

南京邮电人学硕i ：研究生学位论文中义摘要 摘要 集成电路( i c ) 是在半导体基片上形成的完整的电子线路，它是上世纪五十年代末期， 随着半导体晶体管硅平面技术的发展而出现的一种新型电子器件。当前芯片罩的电路与系 统同趋复杂，超大规模集成电路( 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 ) 算法对布图规划进行优 化。这样，整个布图规划的优化问题就转化为编码变换的问题，其中又介绍了一些算法如 约束图的生成算法及关键路径算法等。在编码变换达到最优情况下，将经变换的编码解码 成布图规划，这样实现了从初始图到最优图的一个过程，并给出实验结果。最后，是本文 的创新之处。在前面介绍的基础上，首次将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 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 单元；模块；模拟退火；布线区域 南京邮电大学硕 ：研究生学位论文 英文摘要 a b s t r a c t t h ei n t e g r a t e de 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 d 勰an 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 l lb 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 ls 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 t 、析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 e 嬲b a s i cm o d u l e s i n c e b b li so f t e nu s e d 嬲t 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 ea n dt h ei m p o r t a n c eo fa u t o m a t i cf l o o r p l a nd e s i g n t h e ni 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 l lb 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 l l 乩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 n 谢t l ls 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 e p r o b l e mc o n v e r t st oc o d em o v i n g 。a f t e r h 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 n a g a i n s ot 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 l f l o o r p l a n 诵mt h ee x p e r i m e n tr e s u l t a tl a s t ，t h ei n n o v a t i o no ft h i sp a p e ri sp r o p o s e d b a s i n go n t 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 i d e r i n gr o u t i n ga r e a f o rt h ef r s tt i m e i tp r o p o s e sa na l g o r i t h mf o rs a t i s f y i n gt h ec o n d i t i o nc o n s i d e r i n gr o u t i n ga r e a b yu s i n gs i n g l e s e q u e n c ea 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 mt 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 m 丽t l lm u l t i - o b j e c t i v e ，s u c ha sc o n s i d e r i n gr o u t i n ga r e a a 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 ，r o u t i n ga r e a 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：2 蚰 同期：型翠丝幺一一 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 1 研究生签名：2 型至幽 导师签名： 邂一 只期：知口 ，- p 南京邮电人学颂i ? 研究生学位论义 第一章绪论 第一章绪论 1 1v l s i 布图设计的目的与意义 从上世纪5 0 年代丌始，集成电路经历了小规模集成( s n n a us 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 es c a l ei n t e 笋a t i o n ，l s i ) 的阶段。 近年来，随着超大规模集成电路( v e r yl a r g es c a l ei n t e 酎a t i o n ，v l s i ) 的发展，人们已经可 以在单个芯片上制作包含上千万个晶体管的完整数字系统或数、模混合的电子系统，其设 计自动化的问题也就愈来愈受到人们的关注。且随着集成电路的规模不断增大，复杂度不 断提高，基于i p ( i n t e l l e c t n a lp r o p e r t y ) 复用的层次化设计已成为必然趋势。在这样的背景下， 布图规划问题逐渐成为集成电路向更大规模、更高速度发展的瓶颈，极大地影响着集成电 路的开发时间。实践证明，v l s i 的设计离开设计自动化( 计算机辅助设计) 已经寸步难行i l j 。 随着系统芯片设计方法和知识产权( i p ) 模块技术在集成电路设计中的不断发展和应 用，布图规划( f 1 0 0 印l 锄i n g ) 日渐成为v l s i 物理设计的关键环节。其主要目的是在满足用 户约束条件的前提下确定芯片上模块的最佳位置以及模块的引线端位置，使得芯片面积利 用率达到最高。布图设计作为整个集成电路设计过程中与产品研制和生产直接相关的一个 设计过程，是设计过程中费时最长和差错率最高的设计步骤之一。它直接关系到v l s i 的设 计周期、成本和产品质量。布图设计过程是一个从电路元件说明和网络表中产生设计好的 版图的过程。通常情况下，整个布图设计过程包括划分( p a r t i t i o n ) 、布图规划( f 1 0 0 印l 锄i n g ) 、 布局( p l a c e m e n t ) 、布线( i b u t i n g ) 和压缩( c o m p a c t i o n ) 五个过程【2 l 。稚图设计自动化就是利用 计算机作为辅助工具来实现布图设计的过程。 布图规划问题是超大规模集成电路物理设计的重要阶段，其完成的质量直接影响后续 布线工作的顺利完成，乃至最终影响到芯片面积的大小和电路的性能。布图设计自动化在 v l s i 铝i 造过程中的重要性，一方面主要表现在缩短整个设计周期，减少人工的投入，使成 本降低，最大程度地提高v l s i 的生产效率。在人工设计时，设计周期是与设计规模的2 3 次方成正比的，而目前已经丌发的布图设计系统，虽然与人工设计相比已经提高一个数量 级以上，但其核心算法仍需很大改善：另外一方面主要表现在其可以方便地进行设计正确 性的验证，对于人工设计或人机交互式设计方式，设计的币确性很大程度上依赖于设计者 的经验和专业素养，这神情况下的差错率非常高，并且出现同类错误时也很难检查。而采 用设计自动化技术进行布图设计，由于遵循一定的方法，数据由计算机统一管理，与此同 时，又发展一系列相应的j 下确性验证手段，从而就可基本上解决设计f 确性的验证问题， 南京邮电人学硕j j 研究生学位论义 第一章绪论 很大程度上提高设计成功率。 1 2 v l s i 设计及布图设计模式的分类 从芯片的设计要求开始到芯片封装结束，v l s i 设计过程要经过若干步骤 2 1 ： ( 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 ) 这一步骤可以得到一个表示系统功能的逻辑结构，并反复测试其正确性。设计者通 常用文本、原理图或逻辑图表示设计，有时也用布尔方程表示设计。在设计过程中，还要 对该逻辑结构进行模拟以验证其j 下确性，并对其进行优化设计或称之为逻辑最小化。 ( 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 ) 设计验h q ! ( 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 t l 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 ) 和寄生参数提取( p a r a m e t e re x t r a c t i o n ，p e ) ，经过验证后的版图可以 送去制作掩模版并用于制造芯片。 2 南京邮电大学硕 ：研究生学位论义 第一章绪论 ( 7 ) 芯片制造( f a b r i c a t i o n ) 芯片制造过程包括硅片准备、杂质注入、扩散、光刻等工艺。 ( 8 ) 封装和测试( p a c k a g ea 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 n g r i da r r a y ，p g a ) ， 用于多芯片模块( 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 l 布图规划 j i布局 i 上 l 总体布线 上 i 详细布线 j i l a y 。u t 图1 1v l s ! 设计流程 在整个设计过程中，布图设计是v l s i 设计中的一个关键环节。按照设计自动化程度 来分，可将布图设计方法分成手工设计和自动设计两大类。手工设计方法中又可分成基于 图形的交互图形编辑方法和基于符号的交互图形编辑方法。按照对布局布线位置的限制和 对布局模块的限制来分，则可以把设计方法分成全定制( f u l l c u s t o m ) 和半定制 南京邮电大学硕i ：研究生学位论文 第一章绪论 ( s e m i c u s t o m ) 两大类【3 j ，也称为全定制模式和半定制模式。 全定制模式对模块的布局位置没有限制。整个芯片的电路被划分成一些子电路，每个 子电路是一个模块。在通常情况下，模块的外形和放置位置都没有限制。除了模块所占据 区域以外的芯片区都是布线区。对于三层和三层以上布线工艺的布图设计，模块上面也可 以布线，只是其布线层数有所限制。因此，全定制设计模式除了要遵循最基本的几何设计 规则之外，几乎没有任何其它附加的物理限制。 全定制模式有交互图形编辑，符号法和积木块自动布图三种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 cf l o o r p l a na p p r o a c h ) 也是一种人工设计方法，它使用晶 体管、通孔和连线的符号进行输入和编辑并产生一个拓扑版图，然后再根据给定的设计规 则将它转换成物理版图。不同工艺的晶体管、通孔和连线的符号以及它们相应的物理版图 由符号法布图编辑器事先制作好并存放在单元库中。器件尺寸和线宽可根据给定的设计规 则而进行相应的调整。直接由拓扑版图转换而成的物理版图往往有较多的冗余空间。因此， 符号法布图编辑器中还需提供版图压缩功能，以减小版图面积。符号法布图规划方法保持 了交互图形编辑方法所具有的较高稚图密度和灵活性的优点，且由于设计规则是由符号法 布图编辑器维持的，用户在操作时无需考患，因而大幅度地降低了设计工作量。 积木块自动布图( b u i l d i n gb l o c kl a y o u t ，b b l ) 是任意形状单元布刚4 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 ) 引。分级设计可以降低每个级别设计的复杂性，有利于自动设计技术 的实现，但它可能要以牺牲芯片面积的优化为代价。未被模块占有的芯片空间为布线区， b b l 模式下的布线区比较复杂，通常要先把它们划分成矩形的通道区，然后再按一定次 序逐个进行布线。传统的布线工艺用两层余属，此时模块上面不能布线。随着三层和四层 金属布线工艺的出现，模块上允许稚三、四层线，出现了跨单元布线( o v e rt h ec e l lr o u t i n g ， 4 南京邮电人学硕j 二研究生学位论文 第一章绪论 o c t ) 技术，这使得布线区域大大减少。b b l 模式既具有布图密度高和布图灵活的优点， 又具有自动设计高效率的优点，是一种很理想的设计方法。但由于b b l 的布图算法和布 图系统较其它设计方法复杂，目前还没有一个很成功的实用系统。本篇论文的着手点，就 是b b l 模式下如何对布图规划进行优化。 1 3 研究背景与现状 图1 2b b l 版图结构 齄 帆 逻 辚 在布图规划中，不仅要确定硬模块( 模块形状不可变) 的位置和方向，还要确定软模块 ( 模块形状可变) 的形状和大小。此外，布图规划还是一个多目标优化问题，它的目标函数 包括芯片面积的大小、模块之间互连线的长度、布线区域和拥挤度等。多年来，布图规划 一直是集成电路设计自动化研究的重要课题。 布图规划就是求解可变形状模块或称软模块的布局问题。布图规划和布局是布图设计 流程中的较早阶段，其完成的质量对布线工作的顺利完成乃至最终芯片的面积和性能的影 响非常大。另外，标准单元与宏模块一起的混合模式布局、模拟电路器件布局、数模混合 集成电路设计模式、多芯片集成设计模式以及采用知识产权模块( 即i p 模块的设计模式) 等都是积木块布图模式的布图规划和布局问题。许多学者提出了不同的b b l 布局算法。 早期关于b b l 布局的算法，如最小割法和力向量法等，都是从已有的门阵列和标准单元 南京邮电人学硕t ：t p f 究生学位论文 第一章绪论 的布局算法中受到启示加以模仿和引伸而得到的。其它方法还有：力构造法、2 d 边界搜 索方法、分级设计方法、分支限界法、解析型算法( 数学规划算法) 、模拟退火或遗传算法 ( 随机优化算法) 、机器学习和神经网络算法、模糊数学方法等等。其中许多算法与处理小 单元的布局算法非常类似，并没有考虑到宏单元或大模块布局的特点。 随着多层布线工艺的成熟和普及，跨单元( o v e rc e l l ) 布线得到了广泛应用，使得不可 二划分的( n o n - s l i c i n g ) 结构布局的优越性就更加明显。基于随机优化算法的布图规划与布 局的关键是要找到布局构形的有效表示形式，这一表示应当满足以下条件： ( 1 ) 表示的完备性，即对每一个布局存在一个相应的表示，以保证解空间中包含最优 解。 ( 2 ) 表示的是模块之间的拓扑关系，可以在表示与模块尺寸无关的条件下，对模块的 形状进行优化。 ( 3 ) 无冗余性，不存在多个表示对应同一个布局的情况发生，以保证计算效率。 ( 4 ) 表示与布局之间的转换计算复杂度低，这样在随机优化算法中对一个布局进行评 价时就可以节省时间，从而使算法的整体计算时间缩短。考虑到布局问题巨大的解空间， 这一点是算法实用化的关键。 ( 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 表达式表示【7 】，并使用该表示法得到了一个有效的模拟退火布局算法。为了 能表示一般性的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 gg r i d ) 结构 引，对一般的 n o n - s l i c i n g 布局问题进行了成功的尝试。对含有刀个模块的布局问题，所有序列对的集合 是一个布局问题的解空问，共含有( 刀! ) 2 个序列对，每个都可以在o t n 2 1 时间内对应到一个 布局，其中至少有一个序列对对应最优的布局。之后，w o n g 等人已经将序列对的计算复 杂性降低到o ( 1 9 ( 1 9 n ) ) 。b s g 是一种变形的网格，为了保证最优布局，f i x f 网格的b s g 计算复杂性同样为o ( n 2 ) ，其解空间为c ( ，1 2 ，一) ，这个数目远远大于( 刀! ) 2 。s e q u e n c e p a i r s ( s p s ) 1 9 1 是用于解决p a c k i n g 问题的一种比较好的办法【i o 】【1 。稍后还有t r a n s i t i v e c l o s u r eg r a p h ( t c g ) t 坨】，它的冗余度可以产生更大的解空间。1 9 9 9 年，g u o 和c h e n g 提出 了有序树，即o t r e e 表示f 1 3 】。这一表示的解空间比序列对和b s g 都要小，而且其计算复 杂性仅为o ( n ) 。但这一表示与模块尺寸有关，由于这一布局表示在计算评估时有额外的 6 南京邮电人学颂l ：研究生学位论义 第一常绪论 压紧操作，事实上其计算复杂性比论文中提出来的要大许多。2 0 0 0 年，y c c h a n g 等人 对o t r e e 表示进行了改进，得到了文献【6 】中b * - t r e e 表示法，但这一改进的意义并不大， 而其它的表示在学术上的影响也非常有限。基于随机优化向局算法，董社勤和洪先龙等人 提出了角模块( c b l ) 的表示形式【1 4 1 【1 5 】，即平面矩形区域( 芯片) 用垂直于区域边界的直线进 行任意划分后得到的布局。2 0 0 2 年。y k a j i t a n i 和s a k a n u s h i 等人提出了q 一序列的表示法 【1 6 】【1 7 】，通过一种简单的编码形式，成功地解决了从布图规划到计算机编码的对应，是一 种比较实用有效的方法。2 0 0 4 年，赵华安和刘陈等人在q 序列的基础上提出了e q 序列 【1 8 j ，解决了不能直接通过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 m 】，它是一串整数序列， 其形式非常简单，便于计算机处理。 1 4 本文研究内容及论文结构 本文概括性地介绍了整个v l s i 设计过程以及布图设计在其中的重要性和意义，介绍了 在全定制模式下几种常用c a d i 具实现的方法，其中着重说明了b b l 布图设计方法。通过 引入阿部顺序的概念，介绍t 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 的定义、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 在考虑布线区域下的布图规划优化问题，最后仿真结果表明 s i n g l e s e q u e n c e 在解决多目标条件下的布图规划优化问题非常有效。最后一章是对前面各 章的总结，对本文的工作给予结论，并对今后的研究提出了方向。 7 南京邮f 乜人学颂i ：研究生学位论义 第二章s i n g l e s e q u e n c e 及j 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 ) 结构和不可二划分 ( n o n s l i c i n g ) 结构i z u 。所i 胃s l i c i n g 结构是指可以通过水平或垂直分割线将芯片所在的矩形 划分成两个区域，而且这一过程可以递归地进行直到每个子区域只能容纳一个模块为止。 s l i c i n g 结构表示的布图规划非常有限，因为绝大部分划分是n o n s l i c i n g 的。n o n s l i c i n g 结 构的布局是指不一定具有s l i c i n g 结构的一般的布局结构。这种结构由于具有一般性以及其 布图的高密度性而受到人们更多的重视。布图规划技术产生于积木块模式分级设计的需 8 南京邮电大学硕i ：研究生学位论文 第二章s i n g l e - s e q u e n c e 及j e 心用 要。在这旱的布图规划，它不同于组装( p a c k i n g ) 。疗个模块的p a c k i n g ，是指在一个矩形区 域内放入门个模块，这个矩形区域可以划分为m ( m ，| ) 个小矩形区域，将刀个模块放入这m 个小矩形区域中，只要模块不产生重叠，不论模块如何摆放，目标是使这个矩形区域面积 最小就行了。而对于布图规划，是指先对一个矩形芯片正好切分成, 个小矩形单元，每个 单元必须对应放入一个模块。例如，对于4 个高与宽的数据分别是这样的模块：a = 3 2 ， b = 2 x 3 ，c = 2 x 4 以及d = 3 x 3 。如果按照p a c k i n g 的方法，可以组成图2 1 ( a ) 所示的图形，可 以得到最小矩形区域面积为3 0 ；按照仃图规划的方法，先要对矩形区域划分成4 个单元， 然后在每个单元旱投入一个模块，这样只能得到如2 1 ( b ) 图，其最小矩形区域面积为3 2 p ：j 。 一“u“7 蠹 一 。， 二7 。 。 i 。 ，成一， j j 二；q 、1 w i 。 i ， ：。 e；”。 0 ：， 势 4 i 。r ，罄；j l?z 。i 。一一l 。o | 。：一 1 二! 。 图2 1 p a c k i n g ( a ) 与布图规划( b ) 的比较 布图规划问题的输入是电路的网络表、模块的面积估计以及模块的初始形状；其输出 是所有模块的最佳形状和它们的位置。本文里采用的是准任意单元模式，即所有单元为大 小不同的矩形，其i o 口排列在矩形的四个周边。该前提下的布线通道必然会形成通道区的 交叉，对平面图来说，这些布线通道区成为布图规划罩的分割线。布图中的垂直分割线和 水平分割线相互t 形交叉，这样的布图被称为t 形交叉布图。本文的研究重点就是该种形式 的布图规划。 2 1 2t 形交叉图 刀单元的t 形交叉图，就是用刀一l 条分割线对矩形平面( 芯片) 进行划分后得到一个包含 一个矩形单元的图形。图2 2 为单元数刀= 8 时的t 形交叉图。芯片旱的垂直分割线和水平分 割线不允许交叉穿过，只形成t 形交叉；矩形平面四周的边也作为单元外部的分割线，根 据四周边位置分别称为项墙( ) 、底墙( ) 、左墙( 睨) 、右墙( ) 。对于平面上除右下单 9 南京邮f 乜人学颂i j 研究生学位论艾第二章s i n g l e s e q u e n c e 及j e 应用 元外的任意一个单元f ，两分割线相交构成单元f 的右下角，其中一条分割线形成t 形交叉 的截止边，此截止边记为该单元的p r i m e 边只。对于一个单元f ，与它的p 订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 的研m e 边为垂直线 时，集合里单元的顺序是从上至下排列。排在序列旱第一个( 或唯一的) 单元称为单元f 的次 单元( n e x tr o o m ) 。图2 。2 中，图上所标记的分割线只，只，只为单元口，b ，c 的p r i m e 边， 单元b 的相关单元集包括单元d 和单元p ，其中单元d 是单元6 的次单元1 2 。 2 1 3 阿部顺序 图2 28 单元t 形交叉布圈 阿部顺序：( a b eo r d e r ) t ：挖】是布图中依次访问所有单元的一种方法。对于t 型交叉的布图， 首先将布图中左上角的单元标为l ，然后看它的右下角，如果p r i m e 边垂直( 水平) ，则将p r i m e 边的另一侧最上面( 最左边) 的单元标为2 ，继续这个过程直到右下角的r o o m 被标识。如图2 3 所示。 定理2 1 ：对于布图规划罩的各个单元，根据单元的阿部顺序能给出各p r i m e 边的顺序【2 1 1 。 证明：所有单元f 好可以一次性地根据阿部顺序给出。对于芯片的最左上单元，很明 显可以由第一个阿部顺序分配。对于最左上单元以外的任意一单元f ，单元f 上面分割线作 为盯，左分割线作为毗。假定左分割线与上面分割线相交成为截止边，这个时候因为s l 1 0 南京邮电人学坝 ：研究生学位论义第_ 二章s i n g l e s e q u e n c e 及】e 应用 a b e 排序 图2 3 布图的阿部顺序标记过样 不是芯片的左墙，看观左侧有几个单元，把那些单元旱最下面的单元作为f 。因为观是 单元f 的p r i m e 边，单元f 是单元f 的唯一的次单元，所以单元f 和单元f 的下面的顺序能被 分配。同时，如果f 有唯一能被分配的顺序，f 也可以对应该顺序被分配，s t 与乩交换位 置的时候也同样成立。反过来，如果f 的阿部顺序没有被分配，作为f 次单元的f 的下面单 元，同样没有被分配的阿部顺序的单元也应该存在，可是，这样违反了顺序被给予芯片的 左上单元的条件，所以，所有的单元都有p r i m e 边的阿部顺序。因此，阿部顺序下的i 的单 元名，与其p r i m e 边的名字的阿部顺序相对应。 阿部顺序的一个重要性质就是它唯一标记了布图规划中的单元，从布图规划的左上角 开始到右下角结束，因此每个单元都有一个独一无二的阿部顺序。假设j 和k 是布图规划 中的两个单元，如果， 七) ，则单元在单元k 的左边或上面( 右边或下面) 。阿部顺 序是布图规划的基础。 2 1 4s 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 ，2 ，3 ，以中任意 个独立的整数组成的一个简单序列， 比如s s - - ( 4 ，9 ，5 ，l ，3 ，8 ，6 ，2 ，7 ) 。船序列中的任一个整数都可以用来表示平面中的任一个单 元，它是表示平面布局中的最简单的一种数据结构。豁具有一种特殊的性质，能够用来描 述布图规划中单元之间的位置关系，称之为a b l r 关系( a b o v e ，b e l o w ，l e f t ，r i g h t ) 。2 2 节中 将详细介绍豁的a b l r 关系。 南京邮电人学颁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 就是表示和图规划的一种较好的编码方法，对于 单元的布图规划， 它是一串包含l ，2 ，3 ，刀的序列，并且有刀! 种变换，其中的整数表示单元。当豁用于解决 p a c k i n g i h - j 题时，则表示模块。在得知布图规划的阿部顺序的前提下，通过一定的方法就可 得到与前i 图规划对应的s i n g l e - s e q u e n c e 。后面几节将作详细介绍。 2 2a b l r 关系 a b l r 关系【2 3 1 描述了布图规划中单元之间的位置关系。矩阵a b l r 将布图规划中单元 的位置关系用公式的形式表示出来，其定义如下：行和列表示矩形单元的标记，并以相同 的次序排列。( 毛y ) = a ( b ，l ，r ) ( 其中x ，y 是矩形单元的标记) 表示单元x 在单元少之上( 或 者表示单元x 在单元y 之下，或者表示单元x 在单元y 之左，或者表示单元x 在单元y 之 右) 。下面是包含4 个单元( 口，抚c ，d ) 的布图的例子。假设口，b ，c ，d 的位置关系如图2 a 所 示。 ， 口b 口 d 图2 4 ( 口，6 c ，d ) 位置关系 a b l r = 彳l =