（电工理论与新技术专业论文）基于蚁群算法的类tsp积木块布局优化算法.pdf

a b s t r a c t p h y s i c a ld e s i g nc a d o fi n t e g r a t e dc i r c u i ti sa l s oc a l l e dl a y o u td e s i g n i tb e l o n g s t oac r o s ss u b j e c tb e i n gi n v o l v e dw i t hc o m p u t e rs c i e n c ea n ds e m i c o n d u c t o rt e c h n i q u e l a y o u td e s i g na u t o m a t i o n i sa n i m p o r t a n tp r o c e s sw h i c hi s c o r r e l a t i v ew i t ht h e m a n u f a c t u r ea n dp r o d u c t i o ni nw h o l ei cd e s i g np r o j e c ta n db e i n gr e l a t et ot h ed e s i g n p e r i o d ，c o s t ，v a l i d i t ya n dq u a l i t yo ft h ei ci t sc o n t e n t si n c l u d ed e s i g ne v a l u a t i o na n d p h y s i c a lc h e c k ，p l a c e m e n t ，r o u t i n ga n ds o0 1 i b u i l d i n gb l o c kl a y o u tp l a c e m e n th a s b e e np r o v e dt h a ti san p c o m p l e t ep r o b l e mi ni cl a y o u td e s i g n a n tc o l o n ya l g o r i t h mi sak i n go fw h o l es t o c h a s t i cs e a r c ha l g o r i t h m i ti st h e m o s tf a m o u se x a m p l eo ft h es w a r mi n t e l l i g e n c es y s t e m sa n dh a sb e e na p p l i e dt o s e v e r a lt s pp r o b l e m sa n dr o u t i n gp r o b l e m si nc o m m u n i c a t i o n s e n l i g h t e n e db yt h e g o o dp e r f o r m a n c eo ft h ea l g o r i t h mi nr e s o l v i n gt h et s pp r o b l e m s ，t h i sp a p e ra d o p t a n tc o l o n ya l g o r i t h m i m p r o v e d i n r e s o l v i n gt h eo p t i m i z a t i o no fb b lp l a c e m e n t d e s i g n ，n a m e l yt h ei t e r a t i v ep r o c e s so f t h ep l a c e m e n to p t i m i z a t i o n b a s e do nt h er e s e a r c ho ft h ef o r m e rb b lp l a c e m e n tp r o b l e m sa i dt h e i n e x t r i c a b i l i t yo ft h ep o s i t i o nm o v e m e n ti nb b lp l a c e m e n td e s i g nb yt r a d i t i o n a la n t a l g o r i t h mm o d e l ，t h ep a p e rp r o p o s e sak i n do fd e f i n i t i o nc a l l e dq u a s it s pm o d e l ，i t c a nt r a n s f o r mt h ei n i t i a lp l a c e m e n tr e s u l ti n t oak i n do f q u a s it s ps h a p ea n dp e r f o r m aq u a s it s pb b l m o d e l ，t h e np r o p o s et h eq u a s it s pa l g o r i t h mo fb b lo p t i m i z a t i o n a n tc o l o n ya l g o r i t h m s s oe v e r yb b lc e l lc a nb em o v e da n ds e a r c h e da r o u n dt h e i r p o s i t i o na n da c h i e v e dt ot h eb e s to fr e s u l t a c c o r d i n g l yt h em o v e m e n to ft h eb u i l d i n g b l o c ka n dt h ep l a c e m e n tr e s u l t sc a nb es a t i s f i e dt h ec o n n e c t i o na m o n gt h eb u i l d i n g b l o c kc e l l s b a s e do nt h eb a s i cp r i n c i p l eo fa n ta l g o r i t h m ，t h ep a p e rp r o p o s ef e a s i b l e s o l u t i o nf o ri n c r e a s i n gr u n t i m ea n da v o i d i n gp r e m a t u r el o c a lo p t i m i z a t i o nb yt h e o r e t i c a n a l y s i sa n de x p e r i m e n t s t h es i m u l a t i o nw em a d ee x p r e s st h a tt h ea l g o r i t h mi s a p p l i c a b l et ot h eb b lp l a c e m e n t k e y w o r d s ：a n ta l g o r i t h m ，b u i l d i n gb l o c kl a y o u t ，q u a s it r a v e l i n gs a l e s m a np r o b l e m m o d e l ，l a y o u to p t i m i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁洼盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：签字日期：) 轧矿年f月弓日 学位论文版权使用授权书 本学位论文作者完全了解苤壅盘茔有关保留、使用学位论文的规定。 特授权基生盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 导师签名： 物孚 签字日期：k 赵年f月弓日签字日期：m 年月 日 第一章绪论 第一章绪论 近年来，随着计算机技术的不断进步，对于设计、制造计算机硬件设备 芯片的集成电路技术也取得了飞速的发展，二十一世纪的互联网平台和日益增长 的新服务对微处理器的性能提出了更高的要求，而微处理器芯片作为现代计算机 系统的核心和引擎，它不仅提供计算机系统所需的处理能力，而且能够管理内存 和互联子系统，支持整个系统实现多处理器并行计算，因而计算机的发展有赖于 微电子芯片技术的进步，尤其是作为信息技术基础的集成电路技术对计算机的发 展有着至关重要的影响，近年来，集成电路设计中所采用的计算机辅助设计( c a d ) 技术口1 发展十分迅速，它的发展对整个集成电路技术的进步起到了重要的推动 作用。 1 1 研究背景 集成电路技术自二十世纪五十年代末诞生以来，发展十分迅速，由最初的小 规模集成电路( s s i ) 逐步发展到超大规模集成电路( v l s i ) ，再到现如今的甚 大规模集成电路( u l s i ) 。技术的不断进步首先要归功于m o s 电路的发现，同时 细微加工技术、工艺技术、电路技术、测试技术等的进步以及设计技术的更新也 起到了关键性作用，这主要表现在设计过程全面地采用了c a d 技术。目前集成电 路技术中发展最为迅速的就是计算机辅助布图设计这一部分，为了能有效地解决 此类设计问题，一般将其分为划分、布局、布线三个部分分别进行研究，但由于 这三个设计部分均被证明为n p 问题，因此目前对实现这些设计目标所采用的不 同算法还需要进行不断地研究、探索。 基于单元模式的布图设计模式，包括标准单元和门阵列“m 1 目前仍是 布图设计的主流，它可以用于全芯片或模块内的布图，但由于积木块布图模式所 具有的设计灵活性和布图密度高等特点，可以作为设计大规模、高性能集成电路 第一章绪论 的有效方法，因此具有更广泛的研究发展前景。 近年来，随着优化技术的发展，对于布图设计中的布局设计问题，一些新的 智能算法( 如遗传算法、模拟退火算法、禁忌搜索算法) 得到了迅猛发展和广泛 应用，同时，研究人员还提出了一些新的模拟进化算法，其中的蚁群算法就是一 种源于大自然中生物世界的新的仿生类算法，诞生至今也只有短短几年的时间， 它由意大利学者m d o r i g o 等人首先提出，称之为蚁群系统( a n tc o l o n ys y s t e m ) ， 采用该算法求解t s p 问题、j o b s h o p 问题、g r a p hc o l o r i n g 问题均取得了较好的试 验结果。 1 2 布图设计及布局设计 通常，集成电路的设计和制造过程可以简单地分为：系统描述、功能设计、 逻辑设计、电路设计、布图设计、设计规划检查、样品测试和生产，这些过程不 同程度地都需要有c a d 技术的参与和辅助。其中，发展最为迅速的是计算机辅助 布图设计这一部分。 由于布图设计是一个非常困难的多目标、多变量的组合优化问题，因此涉及 到如算法的设计和分析、组合数学、图论、计算几何学等多方面的知识。布局设 计是集成电路自动布图设计的重要环节之一，简单地说就是元器件或功能单元在 芯片上的安置过程。 随着集成电路的规模、品种、数量的不断发展，其设计的自动化问题也越来 越受到人们的重视，人们已经从实践中得出一个无庸质疑的结论：集成电路的进 一步发展离开设计自动化( d a ) 或计算机辅助设计( c a d ) 是难以实现的，同时 集成电路的进步又推动了计算机的发展，计算机的发展反过来促进了集成电路和 c a d 技术的提高，集成电路、计算机、c a d 三者相互联系、相互影响、相互促进， 共同发展。 1 3 蚁群算法的基本原理 蚁群算法属于一种全局优化算法，它是研究人员受到对真实蚂蚁群体行为的 第一章绪论 研究启发而提出的，作为昆虫的蚂蚁虽然不具备视觉上的识别能力，但在寻找食 物源的过程中，能够在其走过的路径上释放一种蚂蚁所特有的分泌物信息 素，通过蚂蚁群体之间的相互交流作用，使一定范围内的蚂蚁能够辨别、觉察出 来，并以此指导自己的运动方向。当一些路径上通过的蚂蚁越来越多时，其留下 的信息素强度也会越来越大，以至后来蚂蚁选择该路径的概率也越高，从而进一 步增加了该路径的信息素强度，也就更增加了该路径对蚂蚁的吸引程度，这种选 择过程被称为蚂蚁的自催化行为。因此可以这样说，由大量蚂蚁组成的蚁群集体 行为所表现出的是一种信息的正反馈现象某一路径上走过的蚂蚁越多，则后 来者选择该路径的概率也就越大，蚂蚁群体之间就是靠这种信息交流的方式达到 搜索食物的目的。 蚂蚁群体在适应自然环境过程中所产生出来的这种集体行为被称为“群体智 能”( s w a r mi n t e l l i g e n c e ) 。算法虽然研究时间不长，但初步研究已表明，通过 在计算机上用虚拟的人工蚂蚁来仿真自然界中蚂蚁群体间的相互作用，可以用来 解决许多理论科学与实践工程中的复杂优化问题( 尤其是离散优化问题) ，因此 蚁群算法的这种正反馈的迭代思想可以为许多n p 完全问题提供一个新的行之有 效的解决思路。在网络路径的寻优过程中，蚂蚁可以适时地适应网络环境并动态 的变化，采用分布式的方法寻找到目的地，由于蚂蚁所具备的这种特点再加上蚁 群算法本质上的并行运算特性，使得蚊群算法成为v l s i 布局设计算法的一种可 行的发展方向。 1 4 论文的主要工作、创新点和论文的组织 1 。4 。1 论文的主要工作 本文分析了v l s i 布局设计问题的特点以及其中所包括的不同设计方式，并 且对其中的积木块布局模式进行了详细的介绍，提出了一种基于蚁群算法的类 t s p 积木块布局优化算法q a b o a c ( q u a s it r a v e l i n gs a l e s m a np r o b l e ma l g o r i t h m o f b u i l d i n g b l o c k l a y o u t o p t i m i z a t i o n b a s e d a n tc o l o n y a l g o r i t h m ) ，经过改进后的 蚁群算法通过对布局系统进行分布式地路径搜索，达到寻求最佳布局的结果。该 蒋一章绪论 算法的建立首先是一种改进的蚁群算法模型，将其运用到积木块布局设计问 题上，解决了传统蚁群算法在动态布局情况下的局限性问题，为布局设计的进一 步研究进行了有益的尝试，并且还扩充了蚁群算法的应用范围，。 该算法的主要特点是通过引用一种类t s p 模型的概念，将经过初始布局后 的积木块布局结果转化为种类似t s p 的布局形式，经过这种布局转换过程之后 可以动态她调整每一个积木块单元的位置，使积木块单元能够在所处位置的周围 进行移动，形成新的布局，最终寻求布局的最优化，并且布局结果满足积木块单 元之间所必需的连线关系。 1 4 2 论文的创新点 本文在充分研究v l s i 布局设计问题特点的基础上，提出了基于蚁群算法解 决v l s i 积木块布局优化问题的方法，并设计了仿真实验，验证了算法的有效性 及其优化能力。 本文在如下四个主要方面进行了独创性的尝试： ( 1 ) 分析了目前在v l s i 布图设计中的积木块布局优化问题求解方法，指出 作为一种n p 完全问题，积木块布局设计过程中需要进一步研究的方面，并通过 引入一个新的概念后提出了一种新的适用于v l s i 积木块布局优化的类t s p 积木 块布局算法模型。 ( 2 ) 为适用于积木块布局优化问题的求解，对于蚁群算法中的信息素和选择 概率两个关键变量，本文对此进行了一定的改进。 ( 3 ) 将改进后的蚁群算法引入到( 1 ) 中提到的布局模型中求解运算，并在算法 的运行过程中采用改进的局部信息素更新方法，加快了算法的收敛速度，避免过 早地出现局部优化解。 ( 4 ) 在所提出的q a b o a c 算法中，积木块单元不仅可以移动，而且本文增 加了对积木块单元同时进行旋转的变化，这样在搜索过程中可以缩短连线长度、 寻找到更为优化的布局结果。 1 4 3 论文的组织 第一章绪论 本章为论文的绪论部分，介绍了论文的相关研究背景、选题意义、主要工作 以及论文的主要创新点。 第二章概括性地论述了v l s i 布图设计问题研究，并说明了布图设计的原理 和意义，分析了近年来布图设计发展的概况以及发展存在的问题。 第三章着重介绍有关布局设计的定义，特别是积木块( b b l ) 模式布局问题 介绍了近年来有关b b l 布局的算法。 第四章中详细讨论了蚁群算法的基本原理，然后以解决经典t s p 问题为例介 绍蚁群系统模型的建立以及算法的发展现状。 第五章详细论述了基于蚁群算法的类t s p 模型积木块布局优化算法，并结台 实例进行仿真实验研究，得出实验结论。 第二章v l s i 布图设计问题研究 第二章v l si 布图设计问题研究 现如今，电子设计自动化( e l e c t r o n i ed e s i g na u t o m a t i o n ，e d a ) 和计算 机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 已成为集成电路发展必不可少的工 具。由于v l s i 所具有的高可靠性和高性能，使它成为发展电子工业的基础和核 心，而布图设计( 也称为版图设计) 问题又是发展v l s i 的关键。例如，在几十 平方毫米硅片上完成特征线条只有零点几个微米且具有上百万个器件的完整电 子系统设计，只靠人工设计是根本不可能的，因此在整个设计流程中，布图设计 是其中重要的一个设计环节。本章首先介绍了v l s i 布图设计的基本概念和发展 前景，之后分析了几种不同的布图设计模式以及布图设计领域近年来流行的布图 设计算法一启发式算法。 2 1 布图设计的基本概念 2 1 1v 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 逻辑设计( 1 0 9 i cd e s i g n ) 第二章v l s i 布图设计问题研究 这一步骤可以得到一个表示系统功能的逻辑结构并反复测试其正确性，设计 者通常用文本、原理图或逻辑图表示设计，有时也用布尔方程表示，在设计过程 中，还要对该逻辑结构进行模拟以验证其正确性，并对其进行优化设计或称之为 逻辑最小化。 4 电路设计( c i r c u itd 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 ) 在布图设计完成并得到以几何图形形式表示的版图以后， 要进行设计验证，以保证版图满足制造工艺要求和符合系统 的设计规范。它包括设计规则检查、版图的电路表提取、电 学规则检查和寄生参数提取。通过验证后的版图可以送去制 作掩模版并用于制造芯片。 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 l i n ep i n ，d i p ) 或引脚阵列式( p i n g r i d a r r a y ，p g a ) 。 v l s i 设计可能会在一个步骤中或在几个步骤之间反复交替进行，其设计流 程如图2 1 所示，v l s i 设计的目标就是要尽量减少这种反复次数以缩短产品进 入市场的时间。 第二章v l s i 布图设计问题研究 2 1 2v l s l 发展简史 1 9 5 8 年，美国德州仪器公司的基尔h 6 ( j a c k s k i l b y ) 在研究微型组件时，提出 用同一种材料做出晶体管、电阻、电容等元器件的设想，同年9 月在一个玻璃板 上焊上锗晶体管芯片等元件并连线电极而制成了由五个元器件组成的移相振荡 器，当输入i o v 电压时，该电路输出了一条正弦波曲线，于是在t i 公司实验室 里便诞生了世界第一块集成电路。 6 0 年代初，集成电路的规模也只是在每个芯片上有2 4 个基本逻辑电路， 而到了6 0 年代末，集成度已发展到每个芯片包含1 0 0 个门电路，其中大约集成 了1 0 0 0 个元件，即由小规模集成电路( s s i ：s m a l ls c a l ei n t e g r a t e dc i r c u i t ) 逐步发展进入到中规模集成电路( m s i ：m e d i u ms c a ei n t e g r a t e dc i r c u i t ) 阶段； 随着m o s 电路的出现和发展，微处理器的集成度成倍地增长，到了2 0 世纪7 0 年代，众多的单元部件己经可以集成到一块很小的硅晶片上，称为大规模集成电 路( l s l ：l a r g es c a l ei n t e g r a t e dc i r c u i t ) ，1 9 7 8 年一个1 6 位微处理器i 8 0 8 6 上已经集成了2 0 0 0 0 个元件；其中m o o r e 在1 9 7 5 年提出了芯片的集成度每一到 两年翻一翻的定律，至今仍然正确“；进入8 0 年代后逐渐发展到超大规模集成 电路( v l s i ：v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t ) ；而进入9 0 年代后，更 是迈入到了甚大规模集成电路( u l s i ：l a r g es c a l ei n t e g r a t e dc i r c u i t ) 阶段。 如今，国外的先进i c 工艺已经向着深亚微米技术发展，这期间，集成电路 的发展对其他产业所带来的推动和影响是巨大的，因而势必会促使以电子计算机 为代表的电子设备向着超小型化、高集成度、高可靠性的方向发展。如今集成电 路已经广泛应用到计算机、自动控制、通讯、测量、家用、医疗等社会各个领域， 它已经成为社会发展极其重要的硬件基础。 2 1 3 集成电路设计技术的前景 近年来，集成电路技术一直在按照m o o r e 定律发展，即集成电路性能每1 8 个月翻一翻，i c 的这种高速发展主要体现在集成电路设计的不断创新，i c 加工 工艺的特征线条不断缩小等方面。当前以硅为原材料的动态随机存储器( d r a m ) 的集成度已达到2 5 6 m i g b i t ，近年来，国外先进i c 工艺不断地发展，芯片上 第二章v l s i 布图设计问题研究 的特征尺寸也在不断地减少，1 9 9 0 年0 8 u m ，1 9 9 3 年0 6 u m ，1 9 9 5 年0 3 5 u m ， 1 9 9 7 年0 2 5 u m ，1 9 9 9 年0 1 8 u m ，据预测，用不了十年的时间，i c 的制造工艺 可以达到用0 1 u m 的制作工艺完成1 6 g b i t 的d r a m ，而这些技术的发展依赖于计 算机技术的不断提高，这其中也包括了i c 芯片集成度的提高，电路的功能复杂 度的增加以及芯片设计的仓4 新。今后i e 的发展趋势将是朝着高速、低压、低功 耗、高集成度方向发展，因此对于集成电路设计来说，前景广阔。 2 1 4v l s i 布图设计定义 目前在集成电路设计的各个过程中，c a d 技术已经覆盖了芯片设计的全过 程，从系统设计、综合模拟、测试到验证都有c a d 技术的支持，其中也包括布图 设计问题。简单地说，在逻辑电路设计完成后，根据给定设计的逻辑电路和工艺 要求自动完成芯片上元器件或单元功能块的安置，并实现它们之间所需要的 互联，这个过程称之为布图设计。 v l s i 电路工艺的发展不断对c a d 技术提出新的要求，但目前c a d 技术仍然 落后于工艺技术的发展，现有的设计工具还不能完全满足高性能、高集成度的要 求。新的设计方法也给这一领域带来了新的挑战和机遇。因此，用c a d 技术解决 v l s 布图设计技术还需要进一步研究和开发。 2 1 5 布图设计的构成 由于v l s i 布图设计的复杂性，它又可以分为划分、 图规划、布局、布线和压缩这几部分，如图2 2 所示。下 分别作简略介绍： 1 划分( p a r t i t i o n ) ： 由于集成电路的规模很大，对其整体进行布图设计是 困难的，因此，一般将它分成若干个规模较小的电路进行 计。划分就是将大而复杂的逻辑电路，按其功能分成若干个 图2 - 2 子电路，或将规模较大的电路分成若干个规模较小的电路，将较小的电路分配到 第二章v l s i 布图设计问题研究 不同的芯片上，或分配到同一芯片的不同位置“钉。“。划分的目的一般是在子电 路不超过给定大小的前提下，子电路之间的互连尽可能少。划分的效果主要取决 于三个因素：首先，电路系统被划分之后，其总体功能应该不变：其次，划分会 产生一些子电路之间的相互接口，一个好的划分应使这些接口尽可能少：第三， 划分过程所用时间应尽可能短。当电路划分结束之后，每个子电路所占芯片空间 可以预估出来，每个子电路的输入、输出引线位置也可以确定出来。 2 布图规划( f l o o rp l a n n i n g ) ： 布图规划技术“8 ”1 只是在一个较高层次上完成对可变形状模块( 或称软模 块) 的形状和大小的估计。在经过划分过程之后一般根据其所包含的器件数估计 模块的面积，再根据该模块和其他模块的连接关系以及上一层模块或芯片的形状 估计出该模块的形状、相对位置以及引线端的分配，真正实现这些软模块的物理 设计还需要将它们变成较低层次上的布局或布图规划问题。简单地讲，布图规划 就是求解软模块的布局问题。布图规划通常采用随机优化算法解决。 3 布局( p l a c e m e n t ) ： 布局。叩的任务是要确定模块在芯片上的精确位置，其目标是在保证完全布 通的前提下使芯片面积最小化和模块间连线的加权总长度最短。布局问题的输入 是器件模块集合、每个模块的输入、输出端口以及模块之间连线的网表信息。由 于布局问题比较复杂，通常把布局分成两步完成：初始布局和迭代优化布局。一 般情况下，在初始布局时用构造方法给出布局问题的初始解；然后通过迭代改进 优化布局结果。通常评价个布局的好坏有三个标准：1 ) 布局面积：2 ) 线网的 可布性：3 ) 电路的性能。 3 布线( r o u t i n g ) ： 布局设计完成后，接下来的任务是将各元件或单元模块之间按照要求进行连 线。布线乜”的目标是在满足工艺条件、电性能、设计要求下，使芯片总面积最 小，或在限定的区域里完全布通。通常又把布线分为两个阶段：总体布线( g l o b a l r o u t i n g ) 和详细布线( d e t a i l e dr o u t i n g ) 。总体布线要完成线网的合理分配， 但它只是把线网分配在合适的布线区域内，以确保得到尽可能高的布通率，而并 不关心走线的具体位置，详细布线则最终确定连线的具体位置。这样可以在总体 分析线网连接要求和布线区资源后，合理地分配线网，避免局部拥挤。它不但简 o 第二章v l s i 布图设计问题研究 化了布线问题本身，而且提高了布线的成功率。 4 压缩( c o m p a c t i o n ) ： 压缩是布线完成后的优化处理过程，它可以进一步减小芯片面积。目前常用 的有一维压缩和二维压缩乜“，较为成熟的是一维压缩技术。在压缩过程中必须 保证版图图形问不违反设计规则。 以上几部分设计过程虽然独立进行，但它们之间的联系又非常紧密，设计目 标也相互影响，并且是一个反复迭代求解的过程，因此必须注意布图中各个步骤 算法间目标函数的一致性，前面阶段的算法要尽量考虑到对后续阶段的影响。从 各个阶段算法对布图结果的影响来讲，布局是最重要的设计阶段。 2 2 布图设计模式 在布图设计中，单元的形状、大小及在芯片上的安置位置等直接关系到以后 的布线方式，不同的单元形式和安置方式对应不同的设计模式。v l s i 布图设计 的主要模式有：标准单元、门阵列、门海、可编程门阵列、积木块模式等。 1 标准单元模式： 标准单元设计模式( s t a n d a r dc e l ld e s i g ns t y l e ) 又称多元胞( p o l y c e l l ) 模式，是根据电路的互连要求及布图面积最小化的设计目标，将预先设计好的标 准单元成行地排列在版图上，这些单元可以是不同类型的门电路，也可以是复杂 的触发器、全加器等功能电路，般有2 0 0 4 0 0 种，以逻辑符号、逻辑功能及 相应物理版图的形式存放在单元库中。这些单元库中的标准单元版图应具有相同 的高度，宽度可以不同；电源线和地线的位置是规范化的，其他引脚位置一般在 单元的上下边界上。在标准单元模式下进行布图设计时，根据电路的互连要求及 版图面积最小化、时延优化等设计目标，将单元成行地排列，以此完成单元的布 局设计。行与行之间是称为通道的布线区，同行或相邻两行的单元互连可以通过 单元行间的上、下通道布线，隔行单元之间的垂直方向互连则必须使用事先预留 在标准单元间的“走线通道”( f r e e t h r o u g h ) 或在专门的“走线道单元” ( f e e d t h r o u g hc e l l ) 或“空单元”( e m p t yc e l l ) 来完成布线”3 。目前由于多层 金属工艺和“单元上( o v e r t h e - c e l l ) 布线”及区域布线( a r e ar o u t i n g ) 技 第二章v l s i 布图设计问题研究 术的提高，布线资源增加，可允许出现不等高单元和位置任意的引脚。 标准单元模式的布图可以利用自动布局和自动布线技术来完成，效率高、设 计周期短，十分适用于“专用集成电路”的设计，但它的布图密度低，往往会留 有冗余空问，当工艺更新时，单元库要随时更新，这是一项繁重的工作。 2 门阵列模式； 门阵列设计模式( g a t ea r r a yd e s i g ns t y e ) 是利用预先制造好的所谓“母 片”进行布图设计。母片上通常是以一定的间距成行成列地排列着形状和大4 , n 同的基本单元电路，将这些单元内部的晶体管互连后就构成一定形式的门。在布 图设计时，根据电路的要求，首先使电路的每个单元与母片的某个单元建立对应 关系( 通常母片上的单元数将大于电路实际需要的单元数，因此母片上有些单元 会是“冗余”的) ，然后将单元间的布线区域划分为通道区，并以适当的原则将 互连线分配到各个通道区，最后用通道区布线算法实现单元的互连构成具体电路 ”。这种设计模式设计周期短，成本低，但布图密度低，并且不能保证自动完 成布线。 一种改进的结构是去掉垂直方向的通道，把单元按行排列，类似于标准单元 模式，跨行单元间的垂直走线必须利用走线道或走线道单元。这种改进的结构称 之为宏单元阵列( m a c r o c e l la r r a y ) 。它避免了垂直方向通道冗余造成的浪费， 比传统的门阵列有更高的芯片利用率。由于它也是利用走线道完成垂直方向的连 线，因此其布线方法十分类似于标准单元模式，在总体布线后必须有一个走线道 分配，才能进行详细布线m 1e 2 s 。 由于门阵列模式设计和制造周期短、费用低，因而广泛用于小批量产品的 a s i c 设计，但缺点是单元和通道固定，芯片利用率低，电性能差。 3 门海设计模式： 门海设计模式( s e a o f g a t e sd e s i g ns t y l e ) 进一步改进了宏单元阵列的 布图结构，它取消了水平方向的通道，成为一种无通道的门阵列，它仍然保留了 门阵列的优点，母片预制，不同功能的电路只需要改变金属连线，但母片上没有 通道，只有一个二维的单元阵列，阵列上一些区域为功能块区，其他区域为布线 区，每个功能块的大小以及功能块数量取决于所设计的电路规模和划分算法。一 般功能块的形状为矩形，而长宽比和在芯片上的位置则由布图规划和布局算法确 第二章v l s i 布图设计问题研究 定。 门海模式的布线区类似于b b l 模式的结构，因此布图算法与b b l 布图算法十 分相似。不同之处在于门海模式下功能块的位置一旦确定，则不能再移动，只能 通过改变布线走向，而b b l 模式下功能块单元位置是可以随时移动的。 由于门海模式的的功能块大小形状和位置都比较灵活，允许设计像r 栅、r o m 这样较大的模块，因此与门阵列相比，它有更高的芯片利用率和更广泛的活用性。 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 ) 是一种可 编程器件，是近几年迅速发展起来的用于a s i c 设计的一种新方法。f p g a 提供 了用户可编程和自己制造的能力，极大地缩短了设计和制造时间，节省了费用， 具有很强的设计灵活性。 一个f p g a 芯片由若干个可编程的逻辑模块组成，它们即可以排列成如门阵 列那样的模块阵列，也可以排列成如宏单元阵列那样的行模式，也可以排列成如 门海那样无通道的模块阵列，这些逻辑模块可用一个可编程的布线网络进行连 接。通过逻辑综合的转换，将电路等价地转换成一个规则的阵列式电路，使其输 出成为输入信息的“与或”函数。如图2 3 所示为f p g a 设计方式与传统门 匝圈 ：i 圃i 一一一一：二= 一j 掩模编程方式( m p g a ) 图2 3 圈 臣圈 母片! 阵列设计方式的比较图。这种设计模式自动化程度高，设计周期短，成本低， 易测试，但布图密度较低。 5 积木块模式： 积木块模式( b u i i d i n gb l o c kl a y o u t ，简称b b l ) 也称为任意元胞模式， 第二章v l s l 布图设计问题研究 它是利用预先设计好的功能单元版图来进行电路的一种布图设计模式，如图2 4 所示。功能单元可能是门、寄存器、r a m 、r o m 、随机逻辑电路或者是之前规模较 小的设计功能块，也可以是标准单元。基本单元的形状、大小是任意的( 一般限 定为矩形) ，单元引出接点可以排列在单元的四边上，这种设计模式是目前最接 近于人工设计的布图模式。b b l 模式设计的任务是把所有给定的模块合理地安排 在整块芯片上，然后采用可行的布线估算算法实现电路互连，在满足设计规则的 前提下优化芯片面积或时延。 b b l 模式的主要特点是： 1 模块生成几乎不受限制。 2 设计自由度大。 3 布图密度高，布图灵活，有利于层次式设计，不受电路规模影响。 4 易于同工艺紧密结合，伸缩性大。 以上这些特点说明了b b l 布图模式可以作为设计大规模、高性能集成电路的 一种有效布图方式，这种设计模式已经引起了专家和学者越来越大的兴趣，但正 因为其单元设计所具有的灵活性，使得布局和布线过程更加困难，很难达到芯片 面积最小化的要求，所以说，这种模式的布图尤其是v l s i 布图设计中的一个难 题。 以上几种设计模式各有特点，但尤其以积木块设计模式最接近手工布图，因 此也最适合v l s i 布图设计。 积木块单元 图2 4 2 。3 布图设计算法启发式算法 在集成电路的布图设计领域，绝大多数问题都已证明为n p 完全问题，并且 其中的每个设计过程都面临着计算复杂性是指数复杂性的问题，因此很难找到一 1 4 第二章v l s l 布图设计问题研究 个多项式时间算法得到最优解。随着7 0 年代算法复杂性理论的完善，我们一般 不再强调一定要求得到最优解，在实际应用上，通常一个足够好的可行解也是可 以接受的，因此促使8 0 年代以来兴起了对现代优化理论的深入研究，并取得了 巨大的发展。 启发式算法是目前比较流行的解决布图设计问题的算法，其中包括贪婪算 法、遗传算法、模拟退火算法等等。它可以这样来定义口”：在可接受的计算费 用内( 指计算时间、占用空间等) 给出待解决组合优化问题每一个实例的一个可 行解，该可行解与最优解的偏离程度不一定事先可以预计出，即它能得到问题的 一个解，但不能保证是最优解。 启发式算法的长处在于它的数学模型本身是实际问题的简化，多数情况下具 有程序简单、直观、灵活和计算速度快等优点，是目前最重要的一种实用问题求 解方法，但启发式算法也有一定的弊端，比如不能保证求得最优解，通用性差， 同一算法并不一定适用两种不同的实际问题等，而且算法的好坏要依赖于实际问 题、经验和设计者的技术，算法的有效性都要通过大量的实际应用才能验证。一 个好的启发式算法应该是时问、空间复杂度较小，对大多数问题均可以得到近似 最优解。本文将要着重研究的蚁群算法”8 1 就属于一种随机搜索启发式算法，本 文在第四章中将做详细介绍。 第三章v l s i 布局设计算法研究 第三章 v l sl 布局设计算法研究 上一章中简要介绍了有关v l s 布图设计问题的概念、流程以及些布图的 设计模式和算法，其中，布局设计是布图设计流程中的关键问题之一，也是需要 进一步加以研究的难点之一。本文将在这一章里介绍有关v l s i 布局设计问题的 定义，着重探讨积木块( b b l ) 模式布局问题，之后介绍近年来b b l 模式布局设 计问题所采用的些算法。 3 1 布局设计综述 3 1 1 布局设计定义 之所以说布局是v l s i 布图设计中的关键问题之一，是因为布局质量的高低 直接影响着后面布线设计的难易程度，一个布局很差的布图，不可能通过高性能 的布线算法达到好的性能，因此说它是布图设计流程中一个不可忽视的过程。 布局定义为：设b l ，吃，吃是需要放置在芯片上的单元，对每一个 e ( 1 i h ) ，它都有一个高度鼻和宽度w f 相联系。n = n i ，2 ，n m 表示连接不 同单元的线网的集合，g = f 9 j ，q ，珐 表示单元之间用于布线的空区域， 厶( 1 f m ) 表示估计的线网j 的长度。布局设计就是为每一个单元寻找一个矩 形区域r = r l ，r 2 ，心) ，使 1 ) 每个单元都能放置于所对应的矩形区域，即足具有琏的宽度和彬的高 度。 2 ) 任意两个矩形不重叠，即是n 吩= 庐，i ，1 f ，_ ，” 3 ) 布局是可布的，即q j ( 1 j 七) 足够用于布线。 4 ) 所有e ( 1 f _ 2 ) 和g ( 1 - ，女) 面积之和最小。 5 ) 所有线网总线长最小，即厶最小。在性能驱动布线问题中，通常还要 求最长线网的线长最小，即m a ) 【饵f _ 1 ，2 ，嘲最小。 6 第三章v l s i 布局设计算法研究 由于设计的复杂性，v l s i 布局设计过程一般被分为初始布局和迭代改善布 局( 即布局优化) 两个阶段，相应的求解方法分为构造算法和迭代优化算法。其 中，初始布局是从一个单元出发，依次根据一定的单元选择策略选择下一个待放 鼍单元，然后将它安鼍在一个较合理的位置上，整个算法通过不断地选择和放置 单元得到一个布局结果，不仅可以减少布局优化设计的次数，面且可以提高整个 布局设计的效率；而布局优化的设计对象是经过初始布局后的布局结果，对此按 特定的选择规则进行单元位置和方位的调整，从而形成新的布局结果，并且它是 一个逐步优化的过程。本文所讨论的算法就属于一种迭代优化算法。 布局和布图设计中的许多问题一样是一个很复杂的难题，如果在布局过程中 仅仅考虑单元的形状、大小而不考虑单元间的互连关系，设计目标仅考虑安置面 积的最小化，则实际布局问题就蜕变为一个类似“下料”的问题；另一方面，如 果仅考虑单元间的互连关系，而不考虑单元形状和大小，此时就可以将模块拓扑 为一个点，若设每条连线仅连接两个模块，则布局问题蜕变为一个典型的二次分 配问题。无论是“下料”问题还是“二次分配问题”都已经被证明是n p 完全问 题。而事实上布局问题的设计目标远比上述问题还要复杂很多，由此可见布局问 题的复杂程度。 3 。1 2b b l 布局设计方式 对于标准单元的设计，由于受到高度的限制，因此单元的规模有限，在构造 大的功能模块时必须采取单元拼接的方式，这有可能对电路的性能产生很大影 响，甚至不可能实现一些逻辑。因此，在设计上常常需要更大的单元模块，这就 需要突破标准单元的外部限制，具体地讲就是突破标准单元在