在整个现代芯片设计的过程中，由于其复杂性，从而使得专业软件的广泛应用成为了必然。为了获得优异结果，使用软件的用户需要对底层数学模型和算法有较高的理解。此外，此类软件的开发人员必须对相关计算机科学方面有深入的了解，包括算法性能瓶颈以及各种算法如何操作和交互。《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》介绍并比较了集成电路物理设计阶段使用的基本算法，其中从抽象电路设计为开始并拓展到几何芯片布局。更新后的第2版包含了物理设计的新进展，并涵盖了基础技术。许多带有解决方案的示例和任务使得阐述更加形象生动，并有助于加深理解。
《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》是电子设计自动化领域中为数不多的精品，适合集成电路设计、自动化、计算机专业的高年级本科生、研究生和工程界的相关人士阅读。

随着芯片工艺进入5nm甚至2nm时代，芯片上布置的晶体管数量越来越多，给芯片设计带来全新的挑战。在此背景下，作者重新审视了现代芯片设计的基本算法体系，包括网表和系统划分、芯片规划、布局和布线、时序收敛等内容，描述了现代芯片实现流程的各个阶段。本书注重基础，全面覆盖物理设计各个步骤里的基本算法，且兼顾芯片设计中的特定情况，提供了大量的工业界实用的新颖布局、特殊类型布线和性能驱动设计。本书每章后都精心设计了习题并提供完整的答案，还提供了原版PPT课件。本书得到了众多业内大咖的强烈推荐。

第2版前言

自10多年前《超大规模集成电路物理设计：从图分割到时序收敛》出版以来，其在教学和实践中都从广大的读者中获得了积极的回应，这使得《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》顺理成章地获得出版。我们利用这个机会，在不对上一版书中架构和已撰写并论证的内容做大的改动的前提下，对上一版进行了修正和改进，并添加了一个关于机器学习的新章节。许多读者已经开始欣赏这种清晰的、图形描述的结构，这使他们能够理解复杂的算法关系。这一成功的秘诀也使得本书被翻译成繁体中文，而且这个版本在其特定的市场上也很受欢迎。
即使大多数提出的算法都是“经典”的，而且已经有几十年的历史了，但对于当今高度复杂的设计系统，理解它们的基本特性仍然是必不可少的。这种算法知识不仅对电子设计自动化（EDA）有用，而且对其他应用领域也有用。例如，任何曾经为Dijkstra算法编程过智能、有效的寻径功能的人都会理解并认可这些算法可用于优化更多的信息，包括交通和基础设施项目。此外，当使用商用EDA工具时，拥有EDA算法相关的知识会帮助读者大大提高能力。正如很难想象一个车手在不知道引擎盖下发生了什么的情况下驾驶赛车一样，了解基本的算法原理可以更容易地了解、掌握和充分利用现代EDA系统。
我们要感谢所有参与编写《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》的人。首先要感谢Andreas Krinke，他在设计自动化中使用了无数的练习来检测解释中是否存在哪怕很小的错误。我们也感谢Robert Fischbach和Mike Alexander所做的编辑工作。最后，我们要感谢Springer，特别是Charles Glaser，感谢他们在本书出版过程中给予的友好合作和支持。
最重要的是，我们要感谢许多学生，他们在每年举行的讲座后拿着本书向我们提出了探索性的问题。愿他们继续保持对知识的好奇心和渴望，愿本书成为他们今后职业生涯中的忠实伴侣。

Andrew B. Kahng　　
Jens Lienig　　
Igor L. Markov　　
Jin Hu　　


第1版前言

集成电路的超大规模集成物理设计在20世纪80-90年代之间经历了爆炸式的发展。研究者提出的很多基本技术虽然已经用于商业工具，但这些技术信息只发表在简短的会议论文集里，且仅面向该领域的专家。到了21世纪，学术界和工业界的研究者们将注意力集中到了基础算法的发展比较中，并将其延伸到了大规模的最优化问题，即汇集单点最优化为多目标设计流。《超大规模集成电路物理设计：从图分割到时序收敛》用一根主线囊括了物理设计的各个方面，第1章从基本概念开始，然后逐步地延伸到高深的概念，比如物理综合。读者寻求额外的详细资料时，可以查找在每章中提到的大量文献，包括专业的论文著作和近期的会议刊物。
第2章介绍了网表和系统划分。首先讨论了典型的问题构想，然后是平衡图和超图划分的经典算法。最后一节是一个重要的应用，即在多个在线可编程门阵列里进行系统划分，运用在高速仿真功能验证的背景下。
第3章介绍了芯片规划，包括布图规划、电源-地线规划和输入输出的分配。本章涉及的主题和技术很广，从图论方面的块压缩、模拟退火优化到具有封装意识的输入输出规划。
第4章介绍了超大规模集成布局，涵盖了一些实际问题的陈述。布局分为全局布局和详细布局，并首先介绍了传统上用于全局布局的几个算法框架。详细布局的算法则单独在一节里讲述。在布局方面，回顾了当今最好的方法，并对那些想实现大规模布局软件工具的读者给出了建议。
第5章和第6章介绍了全局布线和详细布线， 这在研究文献上受到了极大关注，因为布线影响可制造性与芯片产量优化。这两章的主题涵盖用图模型表示的版图及其在这些模型中的单网和多网布线。首先讨论了新颖的全局布线器，接着在详细设计中进行优化，进一步解决特殊类型的制造缺陷。
第7章介绍了特殊布线，即几类不适合在第5章和第6章介绍的全局布线和详细布线范例。其中包括通常应用在印制电路板的非Manhattan区域布线、每个同步数字电路需要的时钟树布线。不仅在算法方面，还探讨了工艺可变性对时钟树布线的影响，以及降低这种影响的手段。
第8章介绍了时序收敛，其视角特别独特。它完全覆盖了布局、布线和网表重组中的时序分析和相关最优化。8.6节汇集前几章所涉及的所有技术，成为一个扩展的设计流程，即用一张流程图来详细阐述，并通过几张图和大量的参考文献来逐步讨论。
《超大规模集成电路物理设计：从图分割到时序收敛》没有将物理设计之前的内容或者电子设计自动化的其他领域列出。本书向读者介绍了电子设计自动化产业和基本的电子设计自动化概念，涉及重要的图概念和算法分析，并仔细地定义了术语，用伪代码表示出了基本算法。书中有很多插图，每章最后也有一系列习题且答案都在附录里。与其他物理设计的书不一样，我们尽力避免不切实际和不必要的复杂算法。在许多示例里，我们对几种主流算法技术进行了比较，并向读者推荐了包含其他实验结果的出版物。
《超大规模集成电路物理设计：从图分割到时序收敛》中的一些章节内容参照了在2006年由Springer出版社出版的《电子版图综合电路——设计自动化的基本算法》。
感谢我们的同事和学生对《超大规模集成电路物理设计：从图分割到时序收敛》的早期版本进行了校对，并提出了一些改进意见，他们是（按英文字母顺序排列）：Matthew Guthaus、 Kwangok Jeong、 Seokhyeong Kang、 Johann Knechtel、 Andreas Krinke、 Jingwei Lu、 Nancy MacDonald、 Jarrod Roy、 Kambiz Samadi、 Yen-Kuan Wu和Hailong Yao。
第8章中的全局布局和时钟布线图是由Myung-Chul Kim和Dong-Jin Lee提供的。附录中的单元库是由PMC-Sierra公司的Bob Bullock、 Dan Clein和Bill Lye提供的；附录中的版图和原理图是Matthias Thiele生成的。本书的工作得到了美国国家自然科学基金会杰出青年教授奖（CAREER award 0448189）、德州仪器和SUN公司的部分支持。
希望读者能够从《超大规模集成电路物理设计：从图分割到时序收敛》的阅读中找到兴趣，为专业提升提供帮助。

Andrew B. Kahng　　
Jens Lienig　　
Igor L. Markov　　
Jin Hu　　

Andrew B.Kahng是美国加州大学圣地亚哥分校计算机科学与工程（CSE）系和电子与计算机工程（ECE）系教授，并担任高性能计算领域的名誉主席。他曾在Cadence公司（1995～1997年）担任访问科学家，并且是Blaze DFM公司的创始人、董事长和首席技术官（2004～2006年）。

Jens Lienig是德国德累斯顿工业大学（TUD）电气工程教授。他也是TUD机电与电子设计研究所的所长。他曾在Tanner Research公司（1996～1999年）和Robert Bosch公司（1999～2002年）担任项目经理。

Igor L.Markov是IEEE会士和ACM杰出科学家。除了在美国密歇根大学担任电气工程与计算机科学教授外，他还曾在谷歌公司（2014～2017年）工作，并且自2018年以来一直在Facebook/Meta公司工作。

Jin Hu是美国密歇根大学计算机科学与工程（CSE）系的博士生。之后，她先后在IBM公司（2013～2017年）、Bloomberg公司（2017～2019年）和Two Sigma Insurance Quantified（TSIQ）公司（自2019年以来）工作。

目 录
序
第2版前言
第1版前言
第1章　绪论1
1.1　电子设计自动化（EDA）1
1.2　VLSI设计流程4
1.3　VLSI设计模式8
1.4　版图层和设计规则12
1.5　物理设计优化14
1.6　算法复杂度15
1.7　图论术语17
1.8　常用EDA术语20
参考文献22
第2章　网表和系统划分23
2.1　引言23
2.2　术语24
2.3　优化目标25
2.4　划分算法25
2.4.1　Kernighan–Lin（KL）算法25
2.4.2　扩展的KL 算法29
2.4.3　Fiduccia- Mattheyses（FM）算法30
2.5　多级划分框架36
2.5.1　结群37
2.5.2　多级划分37
第2章练习38
参考文献39
第3章　芯片规划40
3.1　布图规划介绍41
3.2　布图规划的优化目标42
3.3　术语43
3.4　布图的表示45
3.4.1　从布图到一个约束图对45
3.4.2　从布图到一个序列对47
3.4.3　从序列对到一个布图47
3.5　布图规划算法52
3.5.1　布图尺寸变化52
3.5.2　群生长56
3.5.3　模拟退火60
3.5.4　集成布图规划算法63
3.6　引脚分配63
3.7　电源和地线布线67
3.7.1　电源和地线网分布设计67
3.7.2　平面布线68
3.7.3　网格布线69
第3章练习71
参考文献72
第4章　全局和详细布局74
4.1　引言74
4.2　优化目标75
4.3　全局布局81
4.3.1　最小割布局82
4.3.2　解析布局88
4.3.3　模拟退火95
4.3.4　现代布局算法97
4.4　合法化和详细布局99
第4章练习100
参考文献101
第5章　全局布线104
5.1　引言104
5.2　术语和定义106
5.3　优化目标108
5.4　布线区域的表示110
5.5　全局布线流程112
5.6　单网布线112
5.6.1　矩形布线112
5.6.2　连通图中的全局布线117
5.6.3　用Dijkstra算法找最短路径121
5.6.4　用A*搜索算法找最短路径126
5.7　全网表布线127
5.7.1　整数线性规划布线127
5.7.2　拆线重布（RRR）130
5.8　现代全局布线132
5.8.1　模式布线133
5.8.2　协商拥塞布线133
第5章练习134
参考文献135
第6章　详细布线137
6.1　术语137
6.2　水平和垂直约束图140
6.2.1　水平约束图140
6.2.2　垂直约束图141
6.3　通道布线算法142
6.3.1　左边算法142
6.3.2　Dogleg布线145
6.4　开关盒布线147
6.4.1　术语148
6.4.2　开关盒布线算法148
6.5　OTC与全局单元布线算法150
6.5.1　OTC布线方法151
6.5.2　OTC布线算法151
6.6　详细布线的现代挑战152
第6章练习154
参考文献155
第7章　特殊布线157
7.1　区域布线157
7.1.1　简介157
7.1.2　线网顺序159
7.2　非Manhattan布线161
7.2.1　八向Steiner树161
7.2.2　八向迷宫搜索163
7.3　时钟布线163
7.3.1　术语164
7.3.2　时钟树布线问题的提出166
7.4　现代时钟树综合168
7.4.1　构建全局零偏移时钟树168
7.4.2　含扰动时钟树缓冲插入175
第7章练习178
参考文献179
第8章　时序收敛181
8.1　引言181
8.2　时序分析和性能约束183
8.2.1　静态时序分析184
8.2.2　使用零松弛算法进行时延预算188
8.3　时序驱动布局192
8.3.1　基于线网的技术193
8.3.2　在线性规划的布局中使用STA 195
8.4　时序驱动布线196
8.4.1　有界半径有界代价算法197
8.4.2　Prim-Dijkstra算法的折衷198
8.4.3　源-汇时延的最小化199
8.5　物理综合201
8.5.1　改变门大小201
8.5.2　缓冲插入202
8.5.3　网表重构203
8.6　性能驱动设计流程206
8.7　结论213
第8章练习215
参考文献216
第9章　附录218
9.1　在物理设计中的机器学习218
9.1.1　介绍218
9.1.2　机器学习：在物理设计中的前景与挑战218
9.1.3　标准机器学习应用219
9.1.4　物理设计的机器学习现状220
9.1.5　未来发展223
9.2　章节练习的答案223
9.2.1　第2章：网表和系统划分223
9.2.2　第3章：芯片规划226
9.2.3　第4章：全局和详细布局229
9.2.4　第5章：全局布线232
9.2.5　第6章：详细布线235
9.2.6　第7章：特殊布线239
9.2.7　第8章：时序收敛247
9.3　CMOS单元布局示例251
参考文献253