◆编辑推荐◆
随着芯片工艺进入5nm甚至2nm时代，芯片上布置的晶体管数量越来越多，给芯片设计带来全新的挑战。在此背景下，作者重新审视了现代芯片设计的基本算法体系，包括网表和系统划分、芯片规划、布局和布线、时序收敛等内容，描述了现代芯片实现流程的各个阶段。本书注重基础，全面覆盖物理设计各个步骤里的基本算法，且兼顾芯片设计中的特定情况，提供了大量的工业界实用的新颖布局、特殊类型布线和性能驱动设计。本书每章后都精心设计了习题并提供完整的答案，还提供了原版PPT课件。本书得到了众多业内大咖的强烈推荐。
扫描上方二维码7折购书
◆名人推荐◆
“这本书为第2版，将继续服务于EDA和设计社区。它是下一代专业人士的基础文本和参考资料，请阅读和使用这本书以继续发展芯片设计工具并设计先进的微电子产品。”
——IBM系统集团EDA副总裁Leon Stok博士
“这本书是我过去教授EDA课程时所希望拥有的，也是我现在一直在使用的一本书。”
——霍华德•休斯医学研究所Louis K.Scheffer博士
“我很乐意在教授物理设计时使用这本书。据我所知，当今没有其他作品能像它这样全面，该书以算法为重点，并为关键算法提供了清晰的伪代码。这本书设计得很漂亮！”
——密歇根大学John P.Hayes教授
“EDA的整个领域都将大大受惠于作者，因为他们提供了一个关于物理设计的单一连贯来源，具有清晰性和指导性，同时提供了关键的先进主题的细节，如时序收敛。”
——加州大学伯克利分校Kurt Keutzer教授
“由本领域的知名专家提出的基本概念和更先进概念的完美平衡。”
——明尼苏达大学Sachin Sapatnekar教授 ◆营销分类◆
AA0402工业技术——电工电子通信——电子技术
◆图书简介◆
在整个现代芯片设计的过程中，由于其复杂性，从而使得专业软件的广泛应用成为了必然。为了获得优异结果，使用软件的用户需要对底层数学模型和算法有较高的理解。此外，此类软件的开发人员必须对相关计算机科学方面有深入的了解，包括算法性能瓶颈以及各种算法如何操作和交互。《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》介绍并比较了集成电路物理设计阶段使用的基本算法，其中从抽象电路设计为开始并拓展到几何芯片布局。更新后的第2版包含了物理设计的新进展，并涵盖了基础技术。许多带有解决方案的示例和任务使得阐述更加形象生动，并有助于加深理解。
《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》是电子设计自动化领域中为数不多的精品，适合集成电路设计、自动化、计算机专业的高年级本科生、研究生和工程界的相关人士阅读。
◆ 目录：◆
目 录
序
第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
◆ 前言：◆
第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
◆ 序言：◆
序
集成电路的物理设计仍然是电子设计自动化领域中非常有趣和具有挑战性的领域之一。在硅芯片上集成越来越多的器件的能力需要通过算法来不断提高。如今，我们可以在一个5nm技术的芯片上集成120亿个晶体管。这个数字将在未来的几代技术中继续扩大，也就意味着需要更多的晶体管自动放置在芯片上并进行连接。此外，越来越多的延迟是由连接芯片上的设备的线路造成的。也就是说，在物理设计过程中考虑如何组合放置对芯片的设计有着深远的影响。在20世纪90年代，我们可以肯定地认为，一旦这些器件被很好地置入芯片，该设计的时间目标就可以达到。今天，在最终的布线完成之前，人们还不知道是否可以满足时间约束。
早在15年或20年前，人们就认为大多数物理设计问题已经解决。但是芯片上晶体管数量的持续增加以及物理、时序和逻辑域之间耦合的增加，使人们对芯片实现的基本算法基础有了新的审视，这正是《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》所提供的内容。它涵盖了所有物理设计步骤背后的基本算法，并展示了如何将它们应用于设计问题的当前实例。例如，第7章提供了关于特定设计情况的特殊类型布线的大量信息。
相比于其他书籍，《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》将更进一步提供对核心物理设计算法和基础数学的深入描述。作者强烈意识到了单目标的单点算法的时代已经结束。在本书中，作者强调了现代设计问题的多目标本质，并将一个物理设计流程的所有部分总结在了第8章。一个完整的流程图，从设计划分和布图规划一直到电气规则检查，描述了现代芯片实现流程的所有阶段。每个步骤都在整个流程的上下文中进行了描述，详情请参考前面的章节。半导体技术的新进展，如纳米片晶体管和背面配电，将要求我们重新审视核心优化策略和算法。最新进展表明，基于机器学习的算法通常在实践的设计流程中有更大的优化空间。
《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》将会受到学生和专业人士的赞赏。它从基础知识开始，并提供了足够的背景材料，让读者及时了解真正的问题。每一章都提供了丰富且有深度的介绍，因此非常有价值。这在当今时代尤为重要，因为其中一个领域的专家必须了解他们的算法对设计流程的其余部分的影响。布线专家将从阅读关于规划和布局的章节中获得巨大的好处。可制造性设计（DFM）专家寻求更好地理解布线算法，以及这些算法如何受到设置DFM需求的选择的影响，将从全局布线和详细布线的章节中获益。任何参与设计技术协同优化（DTCO）的技术专家都应该很好地理解本书中的关键算法，以突破物理上可能的和有益于设计工具与设计师的上限。
《超大规模集成电路物理设计：从图分割到时序收敛（原书第2版）》的每一章都配有一套附有详细答案的练习。这些练习可以促使学生真正理解基本的物理设计算法，并将它们应用于简单但见解深刻的问题实例。
这本书为第2版，将继续服务于EDA和设计社区。这是下一代专业人员的基础文本和参考资料，请阅读和使用这本书以继续发展芯片设计工具并提出先进的微电子技术。
Leon Stok博士
IBM系统集团电子设计自动化副总裁
美国纽约州波基普西市
◆ 作者简介：◆
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年以来）工作。
