前言
过去几十年来，超大规模集成电路(Very Large Scale Integration Circuit, VLSI)已经成为信息技术与信息产业的硬件核心，其发展水平的高低已成为衡量一个国家科学技术和工业发展水平的重要标志。SRC发布的“Physical Design CAD Top10 Needs”中指出了当前物理设计亟待解决的十大问题，其中布线问题首当其冲，在芯片尺寸和容量上，需要布线的电路芯片规模达到成千上万的大模块和几百万个小模块，同时要求在合理可行的时间完成布线工作。此外，布线的质量严重影响了设计过程中的其他需求，包括定时和互连线分析。本书以布线问题为背景，分析了传统布线互连结构——曼哈顿结构在物理设计阶段的限制与缺陷，选择以非曼哈顿结构为基础模型进行布线，实现芯片整体性能的优化，并为在非曼哈顿结构和多层设计概念下变得更为复杂的布线问题寻求更为有效的布线算法。
近年来，编者及其科研团队一直致力于非曼哈顿结构下构建Steiner最小树的理论及应用研究，特别是使用算法的构建及其应用，并在此基础上撰写了此书。本书内容是作者基于自身所主持和参与的国家自然科学基金面上项目、国家自然科学基金青年项目等的研究成果，吸纳了国内外许多具有代表性的研究成果，并融合了课题组近年来在国内外重要学术刊物和国际会议上发表的研究成果，力图体现国内外在这一领域的最新研究进展。本书可作为计算机科学、自动化科学、人工智能等相关学科专业高年级本科生、研究生以及广大研究计算智能的科技工作者的参考书。由于作者水平有限，书中难免有疏漏之处，对于本书的不足之处，恳请读者批评指正。
全书由9章构成，内容自成体系，各章内容具体安排如下： 第1章主要介绍了超大规模集成电路设计方法的重要性及其发展现状，着重介绍了VLSI物理设计中总体布线与详细布线的相关概念，提出了非曼哈顿结构下VLSI布线设计的未来研究方向； 第2章主要介绍了基于群智能技术在X结构、多动态电压设计和通孔柱3种新模型下VLSI布线算法研究的探索； 第3章介绍了在总体布线中5种有效的X结构Steiner最小树算法； 第4章介绍了以时延为优化目标的时延驱动X结构Steiner最小树构建算法； 第5章介绍了3种有效的单层绕障X结构Steiner最小树算法； 第6章介绍了多层绕障的X结构Steiner最小树算法； 第7章介绍了一种高效的考虑布线资源松弛的X结构Steiner最小树算法； 第8章介绍了基于混合离散粒子群优化的Slew约束的X结构Steiner最小树算法； 第9章介绍了基于整数线性规划模型和划分策略的X结构总体布线算法。其中，第1章和第2章、第4章、第6~9章由刘耿耿完成，第3章由郭文忠完成，第5章由黄兴完成。




感谢清华大学出版社的大力支持和编辑的辛苦工作。同时，对课题组内参与有关研究工作的陈国龙教授、牛玉贞教授、陈志盛博士研究生以及庄震、陈晓华、汤浩、朱伟大、张星海、李荣荣、周茹平、魏凌、黄逸飞、杨礼亮、朱予涵等硕士研究生表示衷心感谢。最后，感谢国家自然科学基金项目（61877010、11501114、U21A20472、11271002、11141005）、国家科技部重点研发计划课题（2021YFB3600503）、福建省自然科学基金项目（2019J01243、2018J07005）、福建省科技创新平台项目（2009J1007）和计算机体系结构国家重点实验室开放课题（CARCHB202014）等对相关研究工作的资助。
编者
2021年12月

于福州大学福建省网络计算与智能信息处理重点实验室