非曼哈顿结构下VLSI多层总体布线算法研究

总体布线是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结构层分配多目标粒子群优化算法，以还原之前映射到平面上的多层总体布线资源。

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

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

ECC(椭圆曲线密码系统)是已写入我国无线局域网标准WAPI和我国正在制定其算法标准的一种公钥密码，在信息安全领域具有重要应用。本项目研究ECC算法的有效实现，重点是ECC算法VLSI实现时的算法结构和电路结构，具体包括两方面内容。一是为了更好地满足ECC软件实现或VLSI实现对各种具体实现算法的需求，要寻找ECC实现中的新算法、新方法，或者要优化各种已存在的ECC实现算法。二是如何依据这些新算法、新方法或优化算法，再结合VLSI实现的不同设计目标，要提出各种VLSI实现的算法结构、电路结构，并要获取各种VLSI实现的实验数据与结果。研究内容与拟解决的关键问题凝练于申请者近年来从事高速ECC密码芯片研制时所遇到的科学问题。研究成果对于丰富ECC算法VLSI实现的理论、方法和实验数据，支撑基于我国ECC标准的芯片研发具有重要意义。 2100433B