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

超大规模集成电路物理设计中布图规划和线长估计问题是集成电路设计的重要环节，布图规划和线长估计问题是高度复杂的。我们已对其做了比较深入的研究，分析布图规划和线长估计问题的图论性质，给出问题解的构造方法，构造了一个多目标粒子群优化算法框架，继而研究求解布图规划和线长估计问题的有效多目标粒子群优化算法。本课题研究在非曼哈顿结构下带粒子群优化的高效总体布线器的构建，我们深入研究非曼哈顿结构下总体布线问题的相关性质，选取X结构作为非曼哈顿结构开展研究，取得的主要研究成果如下：（1）针对X结构Steiner最小树问题，分析非曼哈顿结构Steiner树性质，重新构造非曼哈顿结构 Steiner 树的编解码方式，提出来一种改进的离散粒子群优化算法用以求解X结构Steiner最小树；（2）定义拥挤度估算函数确定处于拥挤区域的线网和引入最小化线长最小半径的性能驱动布线树模型，构造不同目标和不同约束下的非曼哈顿结构布线树模型，从而构建其相应的粒子群优化算法，继而从适应度函数的构造、算法参数模型调整策略和性能提高策略三个方面来研究算法；（3）针对非曼哈顿结构下层分配问题，通过定义线网关键性评价函数以获得基于启发式策略的初始层分配方案，继而以最小化拥挤度、通孔数和串扰为目标给出对初始方案进一步优化的非曼哈顿结构层分配算法，分析算法的收敛性并检验这些算法的有效性和可行性。本项目的研究成果将为粒子群优化算法的进一步应用打下基础，并进一步提高我国关于超大规模集成电路设计基础理论研究水平。 2100433B

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

总体布线是VLSI物理设计中极为重要的一个环节。非曼哈顿结构的提出为物理设计带来诸多性能的提高，但该结构的引入和多层工艺的普及，使得总体布线问题更为复杂，且目前研究工作只就某些局部目标展开，缺乏一种该结构下有效完整的总体布线方案。正是在这样的背景下，本项目对非曼哈顿结构VLSI总体布线相关问题展开一些研究工作，选取X结构作为非曼哈顿结构的代表，完成的主要工作如下：（1）基于多目标PSO和Elmore时延模型提出了一种构建时延驱动X结构Steiner树的有效算法，从而有助于性能驱动X结构总体布线问题的研究。（2）绕障Steiner最小树的构建是VLSI物理设计中一个极为重要问题，为此，提出一种基于粒子群优化的有效算法用于求解X结构下的绕障Steiner最小树问题。考虑到粒子群优化算法存在收敛速度慢的不足，进一步设计一种四步骤的高效启发式算法用于求解该问题。（3）针对ML-OAXSMT问题，以最小化布线总代价为目标，并同时考虑到通孔数的优化，提出了一种基于PSO算法和惩罚机制的ML-OAXSMT构建算法。为了进一步提高求解多ML-OAXSMT问题的算法质量，基于查找表的思想，提出了一种高效的绕障策略，可以准确获得多层环境下的Steiner点位置，从而构建一棵高质量的ML-OAXSMT。(4) 针对X结构下的总体布线问题，提出一种基于ILP模型、划分策略及PSO等技术的高质量X结构总体布线算法。 本项目进一步扩宽研究思路，针对曼哈顿结构下绕障Steiner树构建问题并且将PSO扩展应用于VLSI电路划分阶段，主要完成以下工作：（1）研究了电压转换速率的计算模型和RSMT-RERR问题中的电压转换速率约束，基于SPCF算法框架提出考虑电压转换速率约束的直角Steiner树构造算法。（2）研究了ML-OARSMT问题的特征，提出了该问题布线图的构造方法。考虑避开障碍和连通相邻层，选择了三种类型候选通孔位置。 （3）电路划分作为VLSI物理设计中的首个关键环节，通过附加考虑时延因素，构造了电路划分的多目标问题模型，引入局部搜索策略以及基于小生境技术的表现型共享粒子评价机制，设计了一个求解多目标电路划分问题的混合DPSO。 2100433B

总体布线是物理设计中极为重要的一个环节。非曼哈顿结构带来物理设计诸多性能的提高，该结构的引入和多层工艺的普及，使得总体布线算法更为复杂，且目前研究工作只就某些局部目标展开，缺乏一个该结构下有效完整的多层总体布线方案。为此，本课题研究在非曼哈顿结构下高效的VLSI多层总体布线器的构建：（1）利用X结构Steiner树的几何性质，定义其编解码方式和操作算子，继而构造X结构Steiner最小树；（2）定义不同程度的拥挤区域为权重各异的障碍物，融入惩罚机制，构建X结构绕障Steiner树，并利用分治思想和整数规划模型，构建拥挤线网的重布方法；（3）将缓冲器插入问题转换成求解最小半径最小代价生成树，构造求解该问题的多目标粒子群优化算法，以期优化时延；（4）定义线网顺序的评价函数，分析串扰的计算方法，构造同时优化串扰和通孔数的X结构层分配多目标粒子群优化算法，以还原之前映射到平面上的多层总体布线资源。

第1章 绪论

1.1 引言

1.2 基本粒子群优化算法

1.2.1 粒子群优化算法的基本原理

1.2.2 基本粒子群优化算法模型

1.2.3 基本粒子群优化算法流程

1.2.4 参数分析与设置

1.3 粒子群优化算法的改进综述

1.3.1 基于惯性权值的改进

1.3.2 基于加速因子的改进

1.3.3 基于邻近群拓扑的改进

1.3.4 基于种群规模的改进

1.3.5 混合粒子群优化算法

1.4 粒子群优化算法的机理研究

1.5 粒子群优化算法的应用研究

1.6 离散粒子群优化算法

1.6.1 将速度作为位置变化的概率

1.6.2 直接将连续PSO用于离散问题的求解

1.6.3 重新定义PSO算法操作算子

1.7 DPSO算法应用

1.8 DPSO算法研究展望

参考文献

第2章 在P问题中的应用

2.1 引言

2.2 求解TSF问题的自适应粒子群优化算法

2.2.1 离散.PSO算法

2.2.2 求解TSP问题的PSO算法设计

2.2.3 惯性权值在离散PSO算法中的作用

2.2.4 实验结果与分析

2.3 求解TSP问题的动态领域PSO算法

2.3.1 相关概念

2.3.2 TSP问题的PSO操作

2.3.3 动态领域PSO算法的设计

2.3.4 实验结果及分析

2.4 求解TSP问题的PSO一ACO算法

2.4.1 模拟进化的蚁群算法

2.4.2 PSO-ACO算法的设计思想及总体框架

2.4.3 实验结果与分析

参考文献

第3章 在多工作流调度中的应用

3.1 引言

3.2 问题描述

3.2.1 多目标优化问题

3.2.2 求解多目标优化问题的基本方法

3.3 多目标工作流调度问题

3.4 基于表现型共享的多目标粒子群优化算法

3.4.1 基于表现型共享的适应度函数

3.4.2 算法的基本模型

3.4.3 算法步骤

3.4.4 算例测试与结果分析

3.5 求解多目标工作流调度问题的离散粒子群优化算法

3.5.1 算法基本模型

3.5.2 算法主要步骤

3.5.3 实验结果

参考文献

第4章 在多目标最小生成树问题中的应用

4.1 引言

4.2 问题模型

4.2.1 MST问题

4.2.2 mc-MST问题

4.3 改进的计数算法

4.4 求解mc-MST问题的NDPSO算法

4.4.1 粒子的编码机制

4.4.2 粒子的适应度函数

4.4.3 粒子的更新公式

4.4.4 算法描述

4.4.5 收敛性分析

4.5 实验结果与分析

4.5.1 测试问题

4.5.2 结果与分析

参考文献

第5章 在入侵检测数据特征选择中的应用

5.1 引言

5.2 特征选择

5.3 基于PSO和相关性分析的特征选择算法

5.3.1 粒子编码模式

5.3.2 适应度函数

5.3.3 参数设置

5.3.4 算法描述

5.3.5 实验结果与分析

5.4 基于PSo和邻域约简模型的特征选择算法

5.4.1 邻域粗糙集

5.4.2 算法的具体设计

5.4.3 仿真实验

5.5 基于PSO和云模型的特征选择算法

5.5.1 云的概念

5.5.2 云的对象隶属度计算

5.5.3 算法的具体设计

5.5.4 实验结果与分析

参考文献

第6章 在入侵检测系统中的应用

6.1 引言

6.2 基于连续粒子群分类算法的误用检测

6.2.1 目前入侵检测产品存在的缺陷

6.2.2 分类算法

6.2.3 基于连续粒子群的分类算法

6.3 基于否定选择算法的异常检测

6.3.1 基于异常的入侵检测系统的缺陷

6.3.2 人工免疫与否定选择算法

6.3.3 修改的否定选择算法

6.4 混合的网络入侵检测引擎

6.4.1 引入混合方式的目的

6.4.2 混合方式

6.4.3 混合的入侵检测引擎的整体结构

6.4.4 仿真实验

参考文献

第7章 在网络安全态势感知中的应用

7.1 引言

7.2 基于PSO-FNN的安全态势感知要素提取算法

7.2.1 相关算法

7.2.2 基于PSO-FNN的安全态势要素提取模型

7.2.3 基于PSO-FNN的安全态势要素提取方法

7.2.4 仿真实验与结果分析

7.3 基于PSO-BPNN的安全态势预测算法

7.3.1 基于PSO-BPNN的网络安全态势预测模型

7.3.2 基于PSO-BPNN网络安全态势预测方法

7.3.3 仿真实验

7.4 网络安全系统中的组态势感知研究

7.4.1 个体态势感知与组态势感知

7.4.2 基于PSO的聚类分析实验设计

7.4.3 算法流程

7.4.4 仿真实验

参考文献

第8章 在异构集群数据流分配中的应用

8.1 引言

8.2 数据流分配算法

8.3 基于PSO的异构集群数据流自适应分配策略

8.3.1 问题建模

8.3.2 带动态反馈机制的数据流自适应分配模型

8.3.3 改进的粒子群优化算法

8.3.4 仿真实验结果与分析

8.4 动态联盟思想的引入

8.4.1 动态联盟思想

8.4.2 问题建模

8.4.3 算法描述

8.4.4 算法仿真与结果分析

参考文献

第9.章 在WSN拓扑控制中的应用

9.1 引言

9.2 基于度约束最小生成树的wSN分布式拓扑控制

9.2.1 网络模型与问题描述

9.2.2 求解dc—MsT问题的DPSO

9.2.3 分布式拓扑控制方案

9.2.4 仿真实验

9.3 基于二连通的WSN拓扑控制方案

9.3.1 网络模型及问题描述

9.3.2 求解wSN二连通拓扑结构的DPSO算法

9.3.3 仿真实验

9.4 基于K一连通问题的wSN拓扑控制方案

9.4.1 相关工作

9.4.2 相关定义

9.4.3 集中式的KTCPSO算法描述

9.4.4 分布式KLPSO算法描述

9.4.5 算法的时间复杂度分析

9.4.6 仿真实验

参考文献

第10章 在WSN任务调度中的应用

10.1 引言

10.2 任务调度相关概念

10.3 WSN任务分配动态联盟模型及其算法

10.3.1 问题描述

10.3.2 任务分配动态联盟模型的构建

10.3.3 求解动态联盟模型的PSO算法

10.3.4 实验结果与分析

10.4 带多Agent的wSN自适应任务调度策略

10.4.1 多Agent系统

10.4.2 基于多Agent的无线传感器网络体系结构及系统模型

10.4.3 基于多Agent的无线传感器网络自适应任务调度策略

10.4.4 仿真实验与结果分析

10.5 基于串行联盟的动态任务分配算法

10.5.1 串行联盟思想的引入

10.5.2 基于DPSO的联盟形成算法

10.5.3 基于串行联盟的任务分配体系结构

10.5.4 仿真实验

10.6 基于并行联盟的动态任务分配算法

10.6.1 引言

10.6.2 并行联盟概述

10.6.3 基于并行联盟的任务分配算法

10.6.4 基于并行联盟的任务分配体系结构

10.6.5 仿真实验

参考文献

第1l章 在VLSI物理设计中的应用

11.1 引言

11.2 VLSI设计概述

11.2.1 VLSI设计流程

11.2.2 物理设计过程

11.3 单目标电路划分的离散PSO算法

11.3.1 相关工作

11.3.2 问题模型

11.3.3 算法描述

11.3.4 实验结果分析

11.4 单目标电路划分的混合PSO算法

11.4.1 算法的具体设计过程

11.4.2 实验结果与分析

11.5 多目标电路划分的离散：PSO算法

11.5.1 相关工作

11.5.2 多目标划分问题模型

11.5.3 基于DPSO框架下的多目标划分算法

11.5.4 实验结果与分析

11.6 解决布图规划的DPSO算法

11.6.1 VLSI布图模式与相关工作

11.6.2 问题描述

11.6.3 算法描述

11.6.4 实验结果与分析

11.7 解决布图规划的多目标PSO算法

11.7.1 采用整数序列编码的布图规划算法

11.7.2 采用序列对编码的布图规划算法

11.8 解决布图规划的协同多目标PSO算法

11.8.1 协同多目标算法概述

11.8.2 解决布图规划问题的协同多目标PSO算法

11.8.3 实验结果分析

参考文献