VLSI物理设计中布局及有约束的布局优化

摘要

随着微电子技术的高速发展，VLSI的集成度急剧增加，特征尺寸迅速下降至深亚微米甚至纳米级，导致VLSI物理设计阶段的任务更重，难度更大。布图规划和布局是VLSI物理设计中的早期阶段，其结果不但直接影响VLSI的整体设计质量，而且会对后续的布线设计产生决定性的影响。因而，布图规划和布局已成为VLSI设计的关键问题之一。本文在分析影响VLSI布图规划和布局相关因素的基础上，从布图规划及布局的表示法、布局算法中所采用的数据结构、布图规划的结构分析以及模块放置的优化方法等方面，对布局算法的优化、有约束的布图规划和布局、布线优化和标准单元模式布局等问题作了一些探索性研究，主要工作和取得的成果概括如下：
　　 ⑴在布局算法上，详细研究了布局算法中所采用的辅助数据结构和模块放置方法对算法运行效率的影响，提出了角轮廓结构（Corner-Contour）数据结构，证明其从左至右阶梯下降的重要特性，并结合O-tree和Single-Sequence（简称SS）表示法编码各自的特性，简化并优化了基于这两种表示法的布局算法；提出凹轮廓（Concave-Contour）数据结构，并用其实现有固定外框约束的布局；在布局算法中考虑矩形外框对布局的影响，以矩形外框对角线为准线引导模块放置，加快了布局算法的收敛；利用边界约束条件，在不执行模块放置程序的条件下快速评价布局编码，以缩小搜索范围，加快布局算法的收敛。
　　 ⑵在有约束的布局方面，详细研究了SS表示法的编码特性，提出并证明了基于该表示法的边界约束的充要条件，给出了边界约束条件的数字串表达式并用算法实现。对SS表示法边界约束条件的研究进一步完善了这种新式表示法。
　　 ⑶在布线优化方面，详细研究了SS表示法与对应布图规划之间的关系，提出基于该表示法的边界约束对布图规划进行分层结构分析、通过引导模块放置以优化布线结构的方法，不但使SS编码对应的布图规划图形结构更加清晰，而且实现了布局对布线的指导作用和基于布线优化的布局；基于B*-tree编码，用插入虚拟模块的方法实现了紧致型布局中任意模块对的连通，解决了布线中局部模块布通性的问题。
　　 ⑷在标准单元布局方面，从全新的角度考虑标准单元布局的优化问题，提出了标准单元方式下的布局表示法-Ordered Single Chain Tree（简称OSCT）。OSCT表示法编码以数字串编码形式表示标准单元布局的拓扑结构，易于实现标准单元布局的边界约束和布线优化，并能够借助现代随机优化算法对标准单元布局进行更大范围的、更加精确的优化计算。