保正版！超大规模集成电路布线设计理论与算法9787302599432清华大学出版社刘耿耿、郭文忠

超大规模集成电路(Very Large Scale Integration, VLSI)是信息产业的硬件核心，其发展水平的高低已成为衡量一个国家科学技术和工业发展水平的重要标志。在VLSI布线问题中，总体布线和Steiner最小树算法是一个相互关联、充满活力的研究领域，因此本书系统地剖析、分类和整合超大规模集成电路领域的总体布线和Steiner最小树算法，通过不同的方法实现了对VLSI布线算法的优化。
近年来，编者及其科研团队一直致力于超大规模集成电路领域的布线和Steiner最小树算法的理论及应用研究，特别是算法的构建及其应用，在此基础上撰写了此书。本书内容是编者基于自身所主持和参与的国家自然科学基金项目等的研究成果，吸纳了国内外许多具有代表性的研究成果，融合了课题组近年来在国内外重要学术刊物和国际会议上发表的研究成果，力图体现国内外在这一领域的最新研究进展。本书可作为计算机科学、自动化科学、人工智能等相关学科专业高年级本科生、研究生以及广大研究计算智能的科技工作者的参考书。由于编者水平有限，书中难免有疏漏之处，对于本书的不足之处，恳请读者批评指正。
全书由8章构成，内容自成体系，各章内容具体安排如下： 第1章是绪论，主要介绍了集成电路设计的基本流程，着重介绍了VLSI物理设计中的总体布线，阐述了Steiner最小树的问题模型； 第2章介绍了两种直角结构Steiner最小树算法； 第3章介绍了两种绕障直角结构Steiner最小树算法； 第4章介绍了考虑障碍物中布线资源重利用的直角结构Steiner最小树算法； 第5章介绍了总体布线中拥塞估计问题、总体布线中总线和非总线线网的布线算法等方面的研究工作； 第6章介绍了多种时延驱动层分配算法； 第7章介绍了基于轨道分配的详细布线问题，详细阐述了几种轨道分配算法和详细布线算法； 第8章主要介绍了现场可编程门阵列(Field Programmable Gate Array, FPGA)布线算法。其中，第1~2章和第4~8章由刘耿耿完成，第3章由郭文忠完成。
感谢清华大学出版社的大力支持和编辑的辛苦工作。同时，对课题组内参与有关研究工作的陈国龙教授、王廷基教授、张浩副教授、刘文皓博士、黄兴博士以及庄震、朱伟大、张星海、鲍晨鹏、张丽媛、裴镇宇、许文霖等硕士生表示衷心感谢。最后，感谢国家自然科学基金项目(61877010、11501114、U21A20472、11271002、11141005)、国家科技部重点研发计划课题(2021YFB3600503)、福建省自然科学基金项目(2019J01243、2018J07005) 、福建省科技创新平台项目(2009J1007)和计算机体系结构国家重点实验室开放课题(CARCHB202014)等对相关研究工作的资助。
编者
2022年3月

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

本书主要介绍超大规模集成电路中物理设计流程中的总体布线问题以及Steiner小树算法相结合，提出了超大规模集成电路中物理设计流程中多种算法来构建直角结构Steiner小树，例如离散PSO以及DABC算法、绒泡菌算法等等。本书还考虑障碍中布线资源重利用的Steiner小树构建，并提出了多种策略来进行总体布线，以及层分配的算法优化，还基于轨道分配进行详细布线的实现，后还实现了基于时分复用技术的多阶段FPGA布线器，并在每一个小节都有其实验结果与分析。

刘耿耿，副教授，博士生导师，中国计算机学会信息系统专委会委员，福建省人工智能学会理事。主要从事计算智能及其应用、集成电路设计算法、机器学习等方面的研究。主持1项国家自然科学基金面上项目、1项国家自然科学基金青年项目等6个项目，并参与了5项国家自然科学基金科研项目，在《IEEE Transaction on Cybernetics》、《IEEE Transactions on Industrial Informatics》、《计算机学报》、《自动化学报》等国内外权威刊物和国际会议上发表70多篇学术论文，其中JCR一区18篇，JCR二区3篇，并申请发明专利41件，其中授权8件， 获软件著作权12项。

第1章绪论

1.1引言

1.2集成电路设计

1.2.1物理设计

1.2.2布线

1.3总体布线

1.3.1总体布线图

1.3.2总体布线相关定义

1.3.3总体布线策略

1.3.4总体布线方法

1.4Steiner树

1.4.1Steiner最小树问题模型

1.4.2Steiner树结构

1.5相关研究

1.5.1MDSV

1.5.2ViaPillar

1.6本章总结

参考文献

第2章直角结构Steiner最小树算法

2.1引言

2.2基于离散PSO的直角结构Steiner最小树算法

2.2.1准备工作

2.2.2BRRA_DPSO

2.2.3实验结果

2.2.4结论和未来工作

2.3基于离散ABC的直角结构Steiner最小树算法

2.3.1人工蜂群算法

2.3.2DABC_OARST算法

2.3.3性能评估和算法对比

2.3.4小结

2.4本章总结

参考文献

第3章绕障直角结构Steiner最小树算法

3.1引言

3.2基于候选Steiner点的GSTP启发式算法框架

3.2.1引言

3.2.2SPCF算法框架

3.2.3测试与对比

3.2.4小结

3.3基于绒泡菌算法的绕障直角结构Steiner最小树算法

3.3.1引言

3.3.2问题模型

3.3.3算法设计

3.3.4实验结果

3.3.5结论

3.4本章总结

参考文献

第4章考虑障碍中布线资源重利用的直角结构Steiner最小树算法

4.1引言

4.2相关工作

4.3问题的表示和基础知识

4.3.1RSMTRERR问题定义

4.3.2约束相关知识

4.4算法设计

4.4.1布线图的生成

4.4.2Steiner树的构造

4.4.3改善过程

4.5测试结果

4.5.1求解LRSMT问题

4.5.2求解OARSMT_SC问题

4.5.3测试小结

4.6本章总结

参考文献

第5章直角结构总体布线算法

5.1引言

5.1.1绪论

5.1.2国内外研究现状

5.1.3本章主要工作

5.2问题描述

5.2.1物理设计概述

5.2.2术语和定义

5.2.3总体布线模型图

5.2.4总体布线方法

5.2.5总体布线的优化目标

5.3CGR： 高效的拥塞驱动总体布线算法

5.3.1引言

5.3.2问题描述

5.3.3CGR算法设计与实现

5.3.4实验结果与分析

5.3.5小结

5.4本章总结

参考文献

第6章直角结构VLSI层分配算法

6.1引言

6.2问题描述

6.2.1先进制程下的时延驱动层分配问题

6.2.2考虑总线的偏差驱动层分配问题

6.3国内外研究现状及发展动态分析

6.4基于非默认规则线的时延驱动层分配算法

6.4.1引言

6.4.2相关知识

6.4.3算法设计

6.4.4实验结果

6.4.5小结

6.5通孔尺寸感知的时延驱动层分配算法

6.5.1引言

6.5.2相关知识

6.5.3模型构建与算法设计

6.5.4实验结果

6.5.5小结

6.6基于通孔柱的时延驱动层分配算法

6.6.1引言

6.6.2相关知识

6.6.3算法设计

6.6.4实验结果

6.6.5小结

6.7考虑总线的偏差驱动层分配算法

6.7.1DLA算法设计与实现

6.7.2实验结果与分析 

6.7.3小结

6.8本章总结

6.8.1研究现状及成果

6.8.2未来工作展望

参考文献

第7章基于轨道分配的详细布线算法

7.1引言

7.2问题描述

7.2.1轨道分配问题

7.2.2基于轨道分配的详细布线问题

7.3冲突最小化的轨道分配算法

7.3.1引言

7.3.2基于SLDPSO的冲突最小化轨道分配算法

7.3.3仿真实验与结果分析

7.3.4小结

7.4可布线性驱动的轨道分配算法

7.4.1引言

7.4.2算法设计

7.4.3实验仿真与结果分析

7.4.4小结

7.5设计规则约束驱动的轨道分配算法

7.5.1引言

7.5.2算法设计

7.5.3实验仿真与结果分析

7.5.4小结

7.6设计规则约束驱动的详细布线算法

7.6.1引言

7.6.2算法设计

7.6.3实验仿真与结果分析

7.6.4小结

7.7本章总结

参考文献

第8章FPGA布线算法

8.1引言

8.2基于时分复用技术的多阶段FPGA布线器

8.2.1问题描述

8.2.2布线框架流程

8.2.3实验结果

8.2.4小结

8.3一种实用的逻辑验证架构级FPGA布线器

8.3.1时分复用技术

8.3.2布线框架流程

8.3.3实验结果

8.3.4小结

8.4本章总结

参考文献

本书主要介绍超大规模集成电路中物理设计流程中的总体布线问题以及Steiner最小树算法相结合。