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