非曼哈顿结构下带粒子群优化的VLSI总体布线算法研究

项目名称： 非曼哈顿结构下带粒子群优化的VLSI总体布线算法研究

项目编号： No.11141005

项目类型： 专项基金项目

立项/批准年度： 2012

项目学科： 无线电电子学、电信技术

项目作者： 陈国龙

作者单位： 福州大学

项目金额： 10万元

中文摘要： VLSI总体布线的结果对详细布线的成功与否和芯片的性能影响极大，其本质是典型的NP困难多目标组合优化问题。非曼哈顿结构的引入使物理设计的诸多性能得到提高，但目前研究主要集中在通道布线，缺乏一个该结构下有效完整的总体布线方案。本课题研究在非曼哈顿结构下带粒子群优化的高效总体布线器的构建，其分为三个阶段：（1）构建各线网的非曼哈顿结构Steiner最小树集，定义拥挤度估算函数确定处于拥挤区域的线网，并对其构造拥挤度驱动的非曼哈顿结构Steiner树集；（2）引入能克服线网顺序依赖性的整数线性规划模型，并同时采用优化时延和功耗目标的缓冲器插入技术，构建非曼哈顿结构下基于整数线性规划的总体布线多目标优化模型，给出其相应的多目标粒子群优化算法；（3）通过定义线网关键性评价函数以获得基于启发式策略的初始层分配方案，继而以最小化拥挤度、通孔数和串扰为目标给出对初始方案进一步优化的非曼哈顿结构层分配算法。

中文关键词： 超大规模集成电路；布线；组合优化；粒子群优化算法；非曼哈顿结构

英文摘要：

英文关键词： Very Large Scale Integrated Ci；Routing；Combinatorial Optimization；Particle Swarm Optimization；Non-Manhattan Architecture