（计算机应用技术专业论文）eda全局布局中线长估计算法研究.pdf

东南大学硕士学位论文 摘要 箍着定制化芯片的需求越来越大，对与之配套的电子设计自动化( 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 ) 软件的要求也就越来越高，尤其是在某些特定芯片需要特定功能的e d a 软件支持的情况下然而，主流e d a 软件基本上被国外少数公司所垄断，价格昂贵且不 易获得特殊支持，所以研究并开发具有特定需求的e d a 软件成为当务之急 e d a 软件主要包括逻辑综合，布局和布线等功能，其中布局和布线是e d a 软件的重 要组成部分。布局布线的效果直接反映e d a 软件的质量，为了衡量布局布线的效果，用 于对布局布线进行评估的线长估计函数就显得十分重要。 论文分析了不同目标芯片类型的布局线长估计函数的特点，在全部线长、执行效率、 关键路径延迟、拥塞控制等方面，对线长估计函数及布局算法进行了改进，提高了布局算 法的执行效率和布局结果的精度。通过分析标准单元和f p g a 在布局结构、布局特点和布 局目标上的异同，总结出两种类型的线长代价函数的优化目标在标准单元布局线长估计 函数方面，首先实现了最小线长、最小关键延迟、最小拥塞三种运行模式，并且通过使用 带查找表和高度电路启发式分割的斯坦纳改进线长估计函数，代替了原有半周长线长估计， 大大提高了布局精度；针对f p g a 布局线长估计函数的特点，通过引入拥塞和s w i t c h 延迟 改善了布局的拥塞和延迟控制。 论文设计和实现了基于标准单元的最小分割布局原型系统，并实现了不同线长估计函 数，获得较好的布局结果。对当前主流f p g a 布局布线v p r 算法作了针对性的改进，实现 了6 输入l u t 结构，在线长估计函数中加入拥塞、s w i t c h 延迟等优化目标，且在布局阶段 尝试使用布线算法( p a t h 丘n d c r 诹代线长估计函数。 关键词：电子设计自动化，线长估计函数，布局，布线，标准单元，现场可编程门阵列，可 编程开关 东南大学硕士学位论文 a b s t r a c t a sd e m a n df o rc u s t o m i z i n gc h i p sb e i n gg r e a t e ra n d 毋_ c a t e t h eq u a l i t yo fe d a ( f _ l e c t r o n i c d e s i g na u t o m a t i o n ) l d i i s tb eb e t t e ra n db e t t e r , c s p e c i a n yw h c ns o 聪出p sn e e d 叩i a le d a s s u p p o r t 1 - l o w c v e r , i , l a j o re d as o f t w a r e sa 砖b a s i c a l l y 棚m o n o p o l i z e db yaf e wi o r e i g n c o m l m i e s ，w o r t h yo th i g hp r i c ea n du s hm tr e c e i v e 叩e c i a ls u p p o r t s o ，s t u d ya n d d e v e l o p m e n t o f e d a s o f t w a r e w i t h l , a r t i e u l a r f u n c t i o n h a s b e c o m ea t a s k o f t o p p r i o r i t y e d as y s t e m sm m a i n l yc o m p o s c c to fl o g i cs y n t h e s i s , p l a c e m e n ta n dr o u t i n g p l a c e m e n t a n dr o u t i n gi s0 0 eo ft h em o s ti m p o r t a n tc o m l n c n t si ne d as y s t e m s i no r d e rt ow e i g ht h e p l a c e m e n t sq u a l i t y , t h ew i r c l e n g t l ae s t i m a t i o nk m e t i o n t h a tu s e d o 嚣t i m a t et h er e s u l tj u s tm m v e r yi m p o r t a n l t h i st h e s i sa n a l y z e dt h ed i t t e r e n e eb e t w e e ns t a n d a r dc e l lb a s e dp l a c e m c n la n df i g a b a s e dp l a e e m e l i t , i m p r o v e dt h ew i r c l c n g t l ae s t i m a t i o na c c o r d i n gt ot o t a lw i r e l e n t h , mt i m c p a t h d e l a y e o n g e t i o nc o n t r o li tw a sa * a l y z c dt h a tt h es t a l l d a r dc e l la n df p g as i m i l a r i t i e sa n d d i f f e r e c so rs t r u c t t t r eo fp l a c e m e n tr e q u i r e m e n t s , p l a , ：e m n tc h a r a c t e r i s t i ca n dp l a c e m e n t s t a r g e t s ，h a ss u m m a r i z e d t h e o p t i m i z a t i o n o b j e c t i v e s o f t h e w i r e l e l a g t l a e s t i m a t i o n f u n c t i o n s o f t w o t y p e s hs t a n d a r dc e l l sw i r d e n g t l le s t i m a t i o nf u n c t i o n s f i r s ti m p l e m e n t e d t l a r e ew o r kp a t t r e m s , t h e nr e p l a c e dt h eo r i g i n a lh a l f - p e r i m e t e rw i r e l e n g t l ae s t i m a t i o nf u n c t i o n sb yt h ei m p r o v e ds t e i n e r w i r e l c n g t l lf u n c l i o l m sw i t hl o o k - u pt a b l ea n dh i g hd e g r e ec i r c u i tc u t t i n gh e u r i s t i ca l g o r i t h m i n f i g a p l a c e m e n tw i r d c n g t l ae s t i m a t i o nf u n c t i o n s , h a si m p r o v e dt h ep l a c e m e n tb yi n t r o d u c t i o no f c o n g e s t i o na n ds w i t c h e s d e l a y d e s i g n e da n di m p i c m c n t e at h es t a n d a r dc e l lb a s e do np l a c e m e n ts y s t e m , w i t h 1 w ot y p e so l w i r c l e n g t l ae s t i m a t i o 也a tl a s t , a n a l y z e dt h ev p ra r i t h m e t i ew h i e l ab a s eo rf ig a , a n dm d e s o mu s e f u lm o d i f i c a t i o n ss u c ha s ：6i n l m tl u t ：ia d d e dc o n g e s t i o n a l i g nf a c t o i s1 0t h e w i r e i c u g t l a e s t i m a t i o nf i m e t i o n , i n t e g r a t e dt h er e a lm u t i n ga r i t h m e t i c ( 1 , a t h r m c l 神t ot h e p l a c e m e n t , e t c k e yw o r d ：e l e c m m i ed e s i g na u t o m a t i o n , w i r e l e n g t l ae s t i m a t i o n , p l a e e m e n l , r o u t i n g ， s t a n d a r dc e l l ，f i o a , s w i t c h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与找一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：查竺墨日期：业j d 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：导师签名： 期：0 7 ，；3 口 第一章绪论 1 1 研究背景 第一章绪论 加世纪末，电子设计技术获得了飞速的发展，在其推动下，现代电子产品几乎渗透到 社会的各个领域，有力地推动了社会生产力的发展和社会信息化程度的提高，同时也使现 有的电子产品性能得到进一步提高，产品更新换代的节奏也变得越来越快。 微电子技术的进步表现在大规模集成电路加工技术和半导体工艺技术的发展上，使得 表征半导体工艺水平的线宽已经达到6 5 n m ，并不断地缩小。在单位硅片晶体管数量上基 本上遵循了著名的摩尔定律( 每两年单位芯片中的晶体管的数目就将增加一倍) 集成电路 设计正在不断向超大规模、极低功耗和超高速的方向发展；同时专用集成电路( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) 的设计成本也在不断降低，功能不断增强，现代的集成 电路已能实现片上系统( s y s t e mo nc h i p 。s o c ) 现代电子设计技术的核心已日趋转向基于计算机辅助设计的电子设计自动化 ( e l e c t r o n i c d e s i g n a u t o m a t i o n ，e d a ) 。e d a 技术就是依靠计算机强大的计算能力，在e d a 软件上，使用硬件描述语言( h a r d w a r ed e s c r i p t i o nl a n g u a g e ，h d l ) 进行系统逻辑描述， 全自动或有用户参与的半自动地完成逻辑编译、逻辑优化、逻辑综合、物理综合( 布局布 线) 及仿真测试，直至最终真实布局布线结果。e d a 技术的出现，使得设计者只需要在 e d a 软件上使用硬件描述语言就能完成芯片级硬件设计工作，是电子设计技术的巨大飞 跃。 另一方面，现代电子产品性能不断提高，复杂度不断增大，价格却一直在下降，产品 更新换代的步伐也越来越快，出现这些特点的主要原因就是微电子制造工艺和现代电子设 计技术的发展。前者以微细加工技术为代表，目前已进展到深亚微米阶段。可以在几平方 厘米的芯片上集成数千万个晶体管。代表了物理层在广度和深度上硬件电路实现的发展： 后者的核心就是电子设计自动化也就是e d a 技术，反应了现代先进的电子理论、仿真技 术、设计工艺和最新计算机软件技术的有机融合和升华。两者相互促进、相互推动而又相 互制约。没有现代电子设计技术的支持，想要完成上述超大规模集成电路的设计制造是不 可想象的。反过来，生产制造技术的不断进步又必将对现代电子设计技术提出新的要求。 e d a 以计算机为工作平台，融合了应用电子技术、计算机技术、智能化技术最新成果， 最终实现的目标是全定制或半定制a s i c 、f p g a c p l d ( 或称可编程a s i c ) 和p c b ( 印 刷电路版) ，前两个又可归结为基于a s i c 的i c 设计根据实现的工艺，基于e d a 技术的 半定制或全定制a s l c 可统称为掩模a l s c ，或直接称为a s i c 。 a s i c 大致分为门阵列a s i c 、标准单元a s i c ( 标准单元a s i c ) 和全定制a s i c 三种 门阵列芯片包括预定制相连的p m o s 和n m o s 晶体管行。基于标准单元a s i c 是当前使用 最广泛的a l s c 方式，它是使用库中不同大小的标准单元设计的，所有的标准单元的扩散、 接触点、过孔，多晶通道及金属通道等细节都已确定，只需用e d a 软件产生的网表文件 将单元“粘贴”到芯片的单元行上即可，并且与f p g a 设计相近。而全定制a s i c 设计中， 设计者对于电路的设计有完全的控制权。如图1 - 1 所示。在此，主要讨论e d a 软件在i c 设计方面的作用 东南大学硕士学位论文 图1 - 1 e d a 技术应用领域 e d a 技术伴随计算机、集成电路、电子设计的发展，经历了计算机辅助设计( c o m p u t e r a i d e d d e s i g n ，c a d ) ，计算机辅助工程设计( c o m p u l e r a i d e de n g i n e e r l n gd e s i g n ，c a e ) 电子设计自动化三个发展阶段。e d a 技术集中体现在e d a 工具软件上。e d a 软件涉及操 作系统、编译原理，数据库、人工智能、软件工程等多种计算机内容，也涉及微电子技术、 深亚微米技术、信号处理、电路系统等电子知识。 一个高水平e d a 软件的设计反映一个国家电子技术的整体发展水平，在a s i c 领域最 有名的e d a 供应商有c a d e n c e 、s y n o p s y s 和m e n t o r ，及后起之秀m a g m a 等，它们几乎垄 断了a s i c 和s o c 设计的从r t l 到g d s i i 的全程设计流程e d a 软件对比国外，我国相 对落后，只有特定领域有个别e d a 软件。 如今，国内高新电子行业发展迅速，对e d a 软件需求巨大，但国外e d a 软件价格昂 贵且无法获得特殊支持当今，对于芯片设计的任务已不完全由半导体厂商来独立承担， 越来越多的系统开发人员更愿意能够依据自己的需求来进行f p g a 或c p l d 设计，而且能 够快速简便的完成并投入使用，如果需求量大再以a s i c 的形式交由半导体公司批量生产。 目前e d a 工具优化质量还不高，很多芯片制造商在一些关键技术上还是采用半自动半人 工优化的方法，提高自动优化的水平是迫在眉睫的和必要的因此国内e d a 技术研究面 临巨大的机遇和挑战，特别是在基于标准单元及f i g a 等可编程器件的e d a 软件上寻找 突破以期获得长足发展。 e d a 软件一般用诸如v e r i l o g ，v h d l 、s y s t e mc 等硬件描述语言作为输入，经过高级 综合，逻辑综合，物理综合等步骤，最后一般生成g d s l l 格式。主要组成部分关系如图1 - 2 所示。 高级综合：将硬件描述语言编译成电路逻辑网表，并作为逻辑综合的输入，实现 硬件描述语言到r t l ( 寄存器转移级) 的转化。 逻辑综合：电路逻辑网表经逻辑综合和工艺映射，转化成由l u t 及触发器等元件 组成的网表，完成门级网络的优化，在保持原有逻辑功能的基础上生成面积较优 的门级网表，同时考虑可测试性等问题。 物理综合：对网表( n e t l i s t ) 进行布局、布线并优化 2 第一章绪论 高级语言 图1 - 2 e d a 软件流程 其中，物理综合是e d a 软件的极其重要的部分，它的好坏直接影响整个e d a 系统的 质量和执行效率。物理综合包括布局和布线两个部分： 布局( p l a c e m e n t ) ：主要是决定电路网表中的元件在芯片中的位置为了简化问 题，一般又将布局分为全局布局和细节布局两部分全局布局算法是将一堆元件 按一定的约束条件( 线长短，串扰小等) 分布到= x n 个子区域中，获得一个大概 的布局结果，然后在细节布局中按一定要求( 移动的元件最少等) 将各个子区域 中的元件无重叠的放置，得到最终布局结果以供布线使用。 布线( r o u t i n g ) ：布线就是在布局的基础上，按照网表的要求决定如何走线一 般采用广度优先搜索最短路径 在布局和布线过程中，需要使用线长估计函数对每次产生的布局布线结果进行评估。 线长估计函数能否正确且迅速地反映布局结果的好坏，直接决定了能否迅速高效地得到高 质量的布局布线结果。因此线长估计函数就成为e d a 领域亟待研究的重要课题之一 本论文将设计和实现基于标准单元的全局布局原型系统，并努力在线长、执行效率、 关键路径延迟、拥塞等优化目标上分别对基于标准单元和f p g a 布局线长估计函数进行改 进。 1 2 基本概念 e d a 软件：e d a 即电子设计自动化的简称。e d a ( e l e c t r o n i c d e s i g n a u t o m a t i o n ) 软 件是当今电子行业主要的工具软件，从各式各样的c p u 设计到f p g a 、c p l d 和p c b 设计 都需要e d a 软件支持。 目标代价函数、线长估计函数的关系：在布局的过程中需要对当前布局进行评估，以决 定是否保留此次迭代的结果，这就是目标代价函数的作用。在基于标准单元的布局算法中， 最常用的是采用曼哈顿距离来估算全部线长，故又称线长估计函数。在本论文中，不再区分 目标代价函数和线长估计函数。 f p g a ：即g a 是英文f i e l dp r o g r a m m a b l eg a t ea w a y 的缩写，即现场可编程门阵列，它是 在p a l 、g a l 、c p l d 等可编程器件的基础上进一步发展的产物。它是作为专用集成电路 ( a s i c ) 领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可 编程器件门电路数有限的缺点。f p g a 采用了逻辑单元阵列这样一个新概念，内部包括可配 东南大学硕士学位论文 置逻辑模块c l b ( c o n f i g u r a b l el o g i cb l o c k ) ，输出输入模块i o b ( i n p u to u t p u tb l o c k ) 和内 部连线( i n t e r c o n n e c t ) 三个部分。 最小生成树问题：寻找到用于连接各个引脚且实现最小线长的边的集合k r u s k a l 算法 和普里姆算法能够很好地解决这类问题。 斯坦纳树问题：给定含有n 个点的集合p ，找到点集s 使得在p u s 上的最小生成树有最小 代价，其中点集s 就叫斯坦纳点集( s t e i n e rp o i n t s ) 。 1 3 布局算法及其线长估计函数研究现状 布局算法完成的任务是在满足各项电学和工艺要求的条件下，在给定区域内( 或尽可能 小的区域内冱不重叠地安置电路中的所有单元，并且尽可能好地满足全部线长最短、拥塞 度最小等要求。而这些要求就是通过布局算法的线长估计函数加以体现和约束的。正是因为 线长估计函数直接影响着布局目标( 如全部线长、芯片面积、布通率( r o u t a b i l i t y ) 、时序延 迟c r m l i n gd e l a y ) ，拥塞等) ，并且电路的布局是版图设计中一个基本而且非常重要的环节， 所以布局算法及其线长估计函数成为e d a 领域的主要研究内容之一。 在过去几十年的时间里，布局算法及线长估计函数得到了广泛的关注和研究，并且产生 了大量的科技文献和有效的布局工具i l , 2 1 i e e e 有专门的刊物讨论包括布局在内的集成电路 设计自动化问题，如i e e e t r a n s a c t i o n s o n c o m p u t e r a i d e d d e s i g n o f i n t e g r a t e d c i r c u i t sa n d s y s t e m s 等。国际上每年就此专题要举行多个研讨会，如i e e ep i e e d i n gd e s i g na u t o m a l i o n c o n f e r e n c e , i n t e r n a t i o n a lo f e f c o m p u t e r - a i d e dd e s i g n a s i aa n ds o u t hp a c i f i cd e s i g n a u t o m a t i o nc o n f e r e n c e 。i n t e r n a t i o n a ls y m p o s i u mo i lp h y s i c a ld e s i g n 等。国外许多大学的电子 工程系和计算机科学系都有这一研究领域的研究小组，如u n i v e r s i t yo f c a l f f o m l a a tl o s a n g e l e sa n ds a nd i e g o 3 1 ，u n i v e t b i l yo fb i n g h a m t o n l 4 ，n o r t h w e s t e r nu n i v e r s i t y l s j 等。国内也有 清华大学等高校一直从事该领域的研究和教学工作 虽然许多文献提出的布局算法都相当成功地应用于当时的实际电路设计，但是随着集成 电路规模的扩大，深亚微米( d e e ps u b - m i c r o n , d s m ) 工艺成为主流，这些布局算法和布局工 具已经不再那么高效，有的甚至完全不能适用，因此需要研究和开发新的布局方法和工具， 从而解决布局布线中出现的新问题1 6 , 7 ，如广泛使用的半周长线长估计函数已无法满足布局 的精度要求，标准单元a s l c 和新型f p g a 都需要在布局阶段进行时序分析以获得最小关键路 径延迟，并且芯片拥塞问题也日趋严重。 当前布局算法面临两大严峻的挑战：大规模的设计尺寸( 上百万门的单元需要布局) 和复 杂的设计约束( 时延、噪声，功耗、拥塞度等k 研究布局方法的目的主要集中在两个方面： 针对线长、执行效率、最小关键延迟、最小拥塞等优化耳标。提高布局的质量和减少布局的 花费时问。本文正是围绕这些问题展开布局算法研究工作的。 根据e d a 目标器件的不同，布局布线算法可以分为基于标准单元布局布线和基于f p g a 等可编程器件的布局布线。 1 3 1 基于标准单元的布局算法研究现状 基于标准单元的布局启发式算法一般主要有三类：迭代法( i t e r a f i v em e t h o d ) 、数学归 纳法( m a t h e m a t i cp r o g r a m m i n gm e t h o d ) 和最小分割法( m i n - c u tm e t h o d ) 。这三种方法作 为布局启发式框架算法，在执行效率和布局结果质量上各有长短。 迭代法i s 是从一个已有布局状态出发，通过反复调整一个或者多个单元的位置，从而不 断地修改布局状态，最终获得一个比原布局状态质量好得多的布局结果与其它两类布局方 法相比，迭代法有很大的搜索域，可以得到高质量的布局结果，但执行效率很低典型的迭 代法如模拟退火算法，以美国加州大学伯克利分校的t i m b e r w o l f 为例例。 数学规划法【l o j 是将布局问题抽象成为一个数学规划问题，如二次规划( q u a d r a t i c 4 第一章绪论 p r o g r a m m i n g ) f 习题，然后对该模型进行数学求解。此类方法的一个非常好的特性是可以基于 严格的数学分析证明它的求解质量，但是由于该类方法是将布局问题抽象为数学模型，因此 不得不采用一些非精确模型进行近似，从而造成过分的约束，影响了最终的布局效果。数学 规划法对布局质量和花费时间进行了折中。文献【1 2 】所提出了一种标准单元模式下的快速增 量布局算法，算法采用单元行划分的方法处理布局约束，然后将布局调整归结为单元依次插 入单元行的问题，并构造了一个数学规划求解最佳的插入方案，比简单启发式算法的执行效 率要高很多但有一定偏差。 最小分割法 1 1 1 是一种构造性的布局方法，它首先将电路分割成两个或更多个子电路， 同时将芯片的布局面积相应地分割成若干个子区域，每个分割所得的子电路对应一个子区 域，如此反复分割下去，直到电路中的每个单元都有一个惟一的位置。分割法的优化目标是： 在分割过程中，使分割所得的子电路之间的连线个数最少，或称割线数最少( m i n - c u t ) 该类方法具有优化速度快的特点，能够很好地适应集成电路规模不断增大的需要，但是由于 分割法的最终优化目标是割线数最少，这与布局所追求的线网总长最短的目标有偏差，影响 了布局质量。另外，由于分割法是通过强行分割电路并在局部区域内进行布局，造成在早期 不完整和不准确的信息条件下就做出了不可逆转的决定，因而缺乏全局观念，很难获得布局 的最优解典型的最小分割算法如d r a g o n 2 0 0 0 ，其主要思想就是先将电路表示成超图 ( h y p e r g r a p h ) ，然后按照一定要求进行超图分割 6 1 标准单元布局由于不用考虑布线资源的数量和走线方式，因此基于标准单元布局的线长 估计函数一般都是以全部线长最小和执行效率最高为优化目标( o p t i m i z a t i o no b j e c t i v e ) 被标准单元布局采用的线长估计函数主要有以下几种： 1 半周长( h a l f - p e r i m e t e r , i - i p ) 线长估计：也是目前采用的最多的线长估计方法。这 种算法直接通过计算曼哈顿距离来对实际走线进行估计，执行效率非常高，对于两 引脚( p i n ) 或三引脚也有较高的精度但是对于更多引脚时线长就会被显著地低 估，且对于相同度数引脚的不同电路的误差也不同旧。 2线性最小生成树( r e c t i l i n e a rm i n i m u m s p a n n i n gt r e e ，r m s t ) 线长估计算法：这种算 法可以在合理的时间内得到较好的结果，但其本质都是采用普里姆( p r i m ) 算法， 对于全局布局算法来说时间依旧较长1 1 4 1 3 线性斯坦纳树( r e c t i l i n e a rs t e i n e rm i n i m a lt r e e ，r s m t ) 线长估计：这种算法使用斯 坦纳树来准确估计实际走线，可以获得精确的线长估计。但计算量极大，对于全局 布局算法其效率是极低的【塌1 7 1 s l 。 已有的基于标准单元布局的线长估计函数，有的具有很高的执行效率( 如半周长线长估 计) 但精度不高，有的具有较高的精度( 如线性斯坦纳树线长估计) 但执行效率偏低。研究 出既具有很高精度，又具有较高执行效率的线长估计函数，并能够成功应用在标准单元布局 系统中成为e d a 重要研究领域之一 1 3 2 基于f p g a 的布局算法研究现状 f p g a 的布局算法和标准单元的布局算法有相似性，也有很大不同。因为f p g a 的逻辑 模块和连线资源都是限定的，布局和布线只能在有限的空间进行。所以，布通率和连线资源 利用率成为重要的目标，这也是大多采用费时但搜索空间大的模拟退火启发式算法的原因。 同时，f g p a 的s w i t c h ( 可编程开关) 具有较高的电阻值，使信号经过开关时产生相当大的 延迟。提高f g p a 的时延性能需要多方面的研究和改进，包括线长估计函数和布局算法上的 改进。另外，现代f p g a l 矍辑结构e l 趋复杂，布线资源更加丰富，随之产生的拥塞问题就不 得不加以考虑。因此考虑f p g a 布局资源有限性和时延特性，与标准单元布局算法相比，全 部线长最小和执行效率已经不是惟一优化目标，像关键路径延迟和拥塞度等因素都是必须考 虑的问题。 5 东南大学硕士学位论文 基于f p g a 的布局算法一般采用迭代启发式算法，如模拟退火、遗传算法等，尤其是以 模拟退火算法为主。这也是因为f p g a 连线资源的有限性。时延约束严格，1 0 0 布通困难等 原因 当前附布局结果最好是加拿大多伦多大学研究的v p r ( v e r s a t i l ep l a c ea n dr o u t e ，通 用布局布线算法) 1 9 j 0 1 。v p r 布局算法主要针对岛式f p g a 结构，线长估计函数可以使用半 周长线长估计函数来对全部线长进行约束，同时v p r 布局目标函数也使用有效的时序分析来 控制关键路径上的延迟。但随着h 瞰器件的制造工艺的发展，v p r 需要作一些相应改进以 适应最新h g a 布局布线的需要，比如最新h i g a 都是基于6 输入的l u - r 结构，互联结构更加 复杂，增强了相邻c l b 的连线结构。而且越来越多的研究表明互联结构中的s w i t c h 的延迟已 经不能忽略，甚至成为主要问题。有的研究认为对于分段式的互联结构，一条走线所经过的 不同段数和s w i t c h 的数量远比单纯长度更为重要另外，v p r 算法没有考虑拥塞度的影响。 这就需要对v p r 等经典f p g a 布局算法进行改进。 1 3 3 布局线长估计函数研究热点 布局线长估计函数研究主要集中在三个优化目标( o p t i m i z a t i o n o b j e c t i v e ) 上：全部线 长和执行效率、关键路径延迟和最终布局结果的拥塞度。它们都是布局结果最重要的衡量 指标，也是布局线长估计函数当前研究和亟待解决的热点问题。另外，考虑能否在布局阶 段引入真实布线算法，以获得最准确的线长值和拥塞分布。下面将对这些问题分别进行介 绍。 1 以全部线长最短和执行效率最高为优化目标 全部线长( t o t a l w i r e l e n t h ) 是一个传统的布局优化目标，也是最早展开研究的优化目 标田j 。通过经验总结和分析，多数人认为带权线网总长( w e i g h t e dt o t a lw i r e l e n g t h ) 最短化 能较好她综合反映“使芯片面积最小化”、“1 0 0 布通率”、“减少寄生干扰和连线产生的延 时”等目标嘲 这类线长估计函数主要有半周长线长估计函数，线性最小生成树线长估计函数，线性 斯坦纳树线长估计函数等。全部线长最短和执行效率最高是相对的，半周长是以低精度的 代价换得高执行效率，线性线性斯坦纳树则是以低效率来获得高精度。但还是可以通过一 些方法来使两个目标尽可能的得到满足，例如用空问获得执行效率的提高，这也是研究的 重点之一 2 。以关键路径延迟最小为优化目标 随着集成电路特征尺寸的日趋减小和电路工作频率的不断提高，电路设计中的时序约 束o t m i n gc o n s t r a i n t ) 成为保证电路正常工作性能的重要因素，并且越来越受到人们的重视。 由于特征尺寸的减小和芯片面积的增大，一方面使得连线电阻和电容增大而造成线网充放 电时间增加；另一方面又使得输入输出之问的路径增长，这样。当连线电阻和电容与驱动 电阻和负载电容相当时，互连线的延迟0 n 研c o n n e c t d e l a y ) 就成为电路路径时延的一个重要 因素。据统计，在高密度、高速度的超大规模集成电路中，内部互连线延迟的平均值己达 到时钟周期的5 0 到7 0 以上吲。因此，芯片内部互连线延迟己经成为决定电路性能的一 个主要因素。 在超大规模集成电路的版图设计中，布局是决定连线分布和线长的重要环节，其结果 直接影响到电路的内部互连线延迟。因此在布局过程中，不仅要追求传统的线长最小，同 时还应当考虑关键路径延迟最小化。现在以路径延迟为优化目标的时延驱动o t m i n g d r i v e n ) 布局己经成为超大规模集成电路版图设计中的一个重要环节和布局理论研究的热点 问题。 在深亚微米及更先进的工艺条件下，电路中的互连线延迟已经超过单元的内部延迟时 间。并且在电路的总路径延迟中占主导地位因此，在布局过程中控制路径上的关键路径 6 第一章绪论 的延迟是必须的。 由于在布局阶段还没有产生实际的连线，因此需要在布局算法的线长估计函数中加入 时序估算模型( 如e l t x a m 模型洲) ，用来分析和计算互连线上的延迟。 当前用来分析和计算关键路径上的延迟的时序估算模型大致可分为基于路径 ( p a t h - b a s e d ) 和基于线网( n e t - b a s e d ) 两大类，分别介绍如下： 基于路径的时序估算模型是以整条路径为研究对象对其时延进行约束。因为电路中的 时延问题本质上是面向路径的，所以它能够给出问题的准确描述。解决的方法一般有两种： 第一种将问题抽象成为线性或非线性规划问题，并通过使用不同的数学规划技术进行分析 解决第二种直接最小化关键路径的长度，在迭代过程中，通过估算路径的时延，不断找 到电路中违犯时序约束的关键路径并对其进行动态调整。此类估算在整个优化过程中能够 准确地关注电路的时序情况，但是由于通常需要考虑电路中的所有路径，使得其只能处理 小规模电路 基于线网的布局算法并不直接着力于对整条路径的时序约束，而是将路径的时延约束 转变成为线网长度的约束或线网权重的分配，从而指导布局在不断地迭代优化过程中向好 的时序关系方向发展。此类估算模型适用于处理大规模电路，但是由于它是基于启发式的 迭代优化算法，存在波动震荡。以线网长度约束为基础的时序估算模型是对路径的时延 进行预算，其主要思想是将路径的时延约束分配到路径上的各个线网中去然而，这类算 法在对线网分配约束时，往往由于不恰当的分配，对一些线网要求得太严格，从而造成对 布局的过分约束。以线网权重分配为基础的时序估算模型是根据线网在路径时延约束中 的重要程度来分配权重的大小，例如经过路径数目多的线网以及关键路径上的线网的权重 要大些。由于线网权重的产生十分灵活方便，因此可以尽量避免对布局中线网的过分约束。 然而，这类算法对线网权重的分配是基于对路径的分析，而分析电路中的所有路径是不可 能做到的，因此如何建立合理而有效的线网权重分配机制是一个值得认真探讨的课题。在 v p r 算法中，一条路径上的s l a c k 越大，关键度就越低。实验表明这种线网权重分配机制 比较合理【1 9 2 0 如何有效地进行时序分析，估算互连线的延迟，和如何衡量路径的关键度，都是研究 的重要课题。v p r 算法也使用了时序分析，在布局线长估计函数中加入对关键路径延迟的 考虑。并且采用了基于路径和基于线网相结合的时序估算模型，首先对整个布局进行基于 路径的时序分析，然后每次布局变动时只采用基于线网的时序分析，从而既可以保证时序 分析的有效性也可以获得较高的执行效率 1 9 , 2 0 3 以拥塞度最小为优化目标 半导体工艺水平的不断提高和芯片规模的不断扩大，使得设计密度问题变得严峻起来， 它会导致对布线资源需求的大幅度增加，当芯片某些区域内的布线资源无法满足实际的走 线需要时，就会迫使线网绕道而行从而恶化设计性能，甚至无法实现1 0 0 布通率，造成 布线拥塞。这时，设计者需要从布线阶段返回到布局阶段重新调整单元在芯片中的位置。 这种由最初存在布线拥挤的布局到最终可布通所有走线的布局可能需要多次循环反复，对 于规模较小的电路，循环操作所需的时间是可以接受的，但是随着芯片规模的扩大，复杂 度的提高，这种依靠反复循环改进版图设计的做法在能够忍受的时间内无法解决布线拥塞 问题。另外，以全部线长最小为目标的优化布局往往造成芯片内布线密度的不均匀分布， 从而导致许多高布线密度区域的出现，因此需要将布线密度作为一个布局优化目标，加入 到布局线长估计函数中，以期在布局阶段发现并且尝试降低布线拥塞问题。 为了在布局阶段控制线网的拥塞度，就需要在布局线长估计函数中加入拥塞估算模型。 当前主要有如下三种拥塞估算模型： 1 ) g l o b a lb i n 估算模型：把给定的芯片划分成若干个矩形区域，一个区域称为一个 7 东南大学硕士学位论文 g l o b a lb i n 。给定一个初始的布局方案之后，单元和引脚都固定在芯片的某个位置 上，采用一个布线模型或者一个简单的布线器把连接单元以及引脚的线网布到芯 片上。这样，对于每个g l o b a lb i n 可以知道穿越其边缘的线网数。假定穿越某一 个g l o b a lb i n 某个边缘c 的走线数是& ，穿越该边缘的走线道数目是一定的，设 为耽，如果阢 s ，那么这条边上就出现拥塞了。拥塞度c o n g 如式( 1 - 1 ) 定 义“c o n g j o d。娟t(1-1) 。i d 。一s 。d 。 s t 2 ) 星型走线估算模型：该星型模型首先计算某个线网的几何中心，然后根据某单元 与中心之间的相对位置关系来估算在平面上的走线概率“1 3 )基于多部划分的估算模型：通过预先计算得到的斯坦纳树模型来估算实际的走线 拥塞度，达到了较高的精确度。但估算走线需要庞大的计算量，无法应用于大规 模电路布局。 文献1 2 2 认为由于现阶段拥塞度问题本身研究的缺乏和精确拥塞度模型的难以建立，如 何比较合理且有效地在布局阶段解决拥塞问题成为布局重大挑战之一。 4 以真实布线算法取代线长估计函数 线长估计函数只是尽最大可能来估计全部线长，如果能够使用真实布线算法来获得真实 布线结果。就可以十分准确的对布局结果进行准确评估。 但布线算法本身十分费时，如果直接在布局阶段采用，对于一般电路规模都是难以接受 的。现阶段还很少有相关研究文献报导。如何对布线算法进行改进，以期能够在布局中采用， 这也是值得研究的问题。 1 4 主要研究内容 如何选择和实现合适的布局启发式算法，如何分别针对标准单元和f p g a 的特点改进线 长估计函数以满足全部线长最短、执行效率最高、最小关键路径延迟、最小拥塞等优化目标， 提高e d a 软件布局质量，这些都是当前全局布局算法和线长估计函数研究热点，也是本论文 的研究目标 本论文主要研究基于标准单元全局布局系统原型实现，基于标准单元和f p c 漶布局算法 的线长估计函数( 即目标代价函数) 改进。 主要内容和创新如下： 分析和改进了斯坦纳树线长估计函数，以取代当前主流的半周长线长估计函数，获 得精度和执行效率上的相对有效提高 设计和实现了最小分割( m i n - c u t ) 启发算法的基于标准单元全局布局系统原型， 并在其中分别针对最小线长、最小关键路径延迟、最小拥塞实现了三种线长估计函 数运行模式，实现了半周长线长估计和改进后的斯坦纳树线长估计算法且进行了实 验对比。 针对当前f p g a 布局要求，改进了当前主流基于岛式f p g a 布局布线的r 算法。更 改了f p g a 结构描述，对线长目标代价函数进行改进( 加入拥塞、s w i t c h 延迟等) 及尝试在布局阶段使用p a t h f i n d e r 布线算法进行线长估计，有效提高了对延迟、拥 塞等的控制。 1 5 论文组织结构 论文共分六章： 第一章绪论，介绍课题的背景及意义，研究内容涉及到的一些基本概念。 8 第一章绪论 第二章标准单元布局算法及其线长估计函数。介绍了主流标准单元布局算法及其线长估 计函数，并进行了比较。 第三章基于标准单元布局的线长估计算法改进和采用最小分割( m i n - c e t ) 启发算法的 基于标准单元全局布局系统原型实现并分别实现了最小线长、最小关键路径延迟、最小拥 塞三种运行模式。 第四章f p g a ：布局算法及其线长估计函数介绍。主要介绍了最新f i ) g a 的结构特点，v p r 布局算法的时序分析，及v p r 的不足( 未考虑s w i t c h 延迟等) 第五章f p g _ a 布局算法及其线长估计函数改进。主要更改了f p g a 结构描述，改进了线 长目