第2版前言

自10多年前《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》出版以來，其在教學(xué)和實(shí)踐中都從廣大的讀者中獲得了積極的回應(yīng)，這使得《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂（原書第2版）》順理成章地獲得出版。我們利用這個(gè)機(jī)會(huì)，在不對上一版書中架構(gòu)和已撰寫并論證的內(nèi)容做大的改動(dòng)的前提下，對上一版進(jìn)行了修正和改進(jìn)，并添加了一個(gè)關(guān)于機(jī)器學(xué)習(xí)的新章節(jié)。許多讀者已經(jīng)開始欣賞這種清晰的、圖形描述的結(jié)構(gòu)，這使他們能夠理解復(fù)雜的算法關(guān)系。這一成功的秘訣也使得本書被翻譯成繁體中文，而且這個(gè)版本在其特定的市場上也很受歡迎。
即使大多數(shù)提出的算法都是“經(jīng)典”的，而且已經(jīng)有幾十年的歷史了，但對于當(dāng)今高度復(fù)雜的設(shè)計(jì)系統(tǒng)，理解它們的基本特性仍然是必不可少的。這種算法知識不僅對電子設(shè)計(jì)自動(dòng)化（EDA）有用，而且對其他應(yīng)用領(lǐng)域也有用。例如，任何曾經(jīng)為Dijkstra算法編程過智能、有效的尋徑功能的人都會(huì)理解并認(rèn)可這些算法可用于優(yōu)化更多的信息，包括交通和基礎(chǔ)設(shè)施項(xiàng)目。此外，當(dāng)使用商用EDA工具時(shí)，擁有EDA算法相關(guān)的知識會(huì)幫助讀者大大提高能力。正如很難想象一個(gè)車手在不知道引擎蓋下發(fā)生了什么的情況下駕駛賽車一樣，了解基本的算法原理可以更容易地了解、掌握和充分利用現(xiàn)代EDA系統(tǒng)。
我們要感謝所有參與編寫《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂（原書第2版）》的人。首先要感謝Andreas Krinke，他在設(shè)計(jì)自動(dòng)化中使用了無數(shù)的練習(xí)來檢測解釋中是否存在哪怕很小的錯(cuò)誤。我們也感謝Robert Fischbach和Mike Alexander所做的編輯工作。最后，我們要感謝Springer，特別是Charles Glaser，感謝他們在本書出版過程中給予的友好合作和支持。
最重要的是，我們要感謝許多學(xué)生，他們在每年舉行的講座后拿著本書向我們提出了探索性的問題。愿他們繼續(xù)保持對知識的好奇心和渴望，愿本書成為他們今后職業(yè)生涯中的忠實(shí)伴侶。

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


第1版前言

集成電路的超大規(guī)模集成物理設(shè)計(jì)在20世紀(jì)80-90年代之間經(jīng)歷了爆炸式的發(fā)展。研究者提出的很多基本技術(shù)雖然已經(jīng)用于商業(yè)工具，但這些技術(shù)信息只發(fā)表在簡短的會(huì)議論文集里，且僅面向該領(lǐng)域的專家。到了21世紀(jì)，學(xué)術(shù)界和工業(yè)界的研究者們將注意力集中到了基礎(chǔ)算法的發(fā)展比較中，并將其延伸到了大規(guī)模的最優(yōu)化問題，即匯集單點(diǎn)最優(yōu)化為多目標(biāo)設(shè)計(jì)流�！冻�大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》用一根主線囊括了物理設(shè)計(jì)的各個(gè)方面，第1章從基本概念開始，然后逐步地延伸到高深的概念，比如物理綜合。讀者尋求額外的詳細(xì)資料時(shí)，可以查找在每章中提到的大量文獻(xiàn)，包括專業(yè)的論文著作和近期的會(huì)議刊物。
第2章介紹了網(wǎng)表和系統(tǒng)劃分。首先討論了典型的問題構(gòu)想，然后是平衡圖和超圖劃分的經(jīng)典算法。最后一節(jié)是一個(gè)重要的應(yīng)用，即在多個(gè)在線可編程門陣列里進(jìn)行系統(tǒng)劃分，運(yùn)用在高速仿真功能驗(yàn)證的背景下。
第3章介紹了芯片規(guī)劃，包括布圖規(guī)劃、電源-地線規(guī)劃和輸入輸出的分配。本章涉及的主題和技術(shù)很廣，從圖論方面的塊壓縮、模擬退火優(yōu)化到具有封裝意識的輸入輸出規(guī)劃。
第4章介紹了超大規(guī)模集成布局，涵蓋了一些實(shí)際問題的陳述。布局分為全局布局和詳細(xì)布局，并首先介紹了傳統(tǒng)上用于全局布局的幾個(gè)算法框架。詳細(xì)布局的算法則單獨(dú)在一節(jié)里講述。在布局方面，回顧了當(dāng)今最好的方法，并對那些想實(shí)現(xiàn)大規(guī)模布局軟件工具的讀者給出了建議。
第5章和第6章介紹了全局布線和詳細(xì)布線， 這在研究文獻(xiàn)上受到了極大關(guān)注，因?yàn)椴季�影響可制造性與芯片產(chǎn)量優(yōu)化。這兩章的主題涵蓋用圖模型表示的版圖及其在這些模型中的單網(wǎng)和多網(wǎng)布線。首先討論了新穎的全局布線器，接著在詳細(xì)設(shè)計(jì)中進(jìn)行優(yōu)化，進(jìn)一步解決特殊類型的制造缺陷。
第7章介紹了特殊布線，即幾類不適合在第5章和第6章介紹的全局布線和詳細(xì)布線范例。其中包括通常應(yīng)用在印制電路板的非Manhattan區(qū)域布線、每個(gè)同步數(shù)字電路需要的時(shí)鐘樹布線。不僅在算法方面，還探討了工藝可變性對時(shí)鐘樹布線的影響，以及降低這種影響的手段。
第8章介紹了時(shí)序收斂，其視角特別獨(dú)特。它完全覆蓋了布局、布線和網(wǎng)表重組中的時(shí)序分析和相關(guān)最優(yōu)化。8.6節(jié)匯集前幾章所涉及的所有技術(shù)，成為一個(gè)擴(kuò)展的設(shè)計(jì)流程，即用一張流程圖來詳細(xì)闡述，并通過幾張圖和大量的參考文獻(xiàn)來逐步討論。
《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》沒有將物理設(shè)計(jì)之前的內(nèi)容或者電子設(shè)計(jì)自動(dòng)化的其他領(lǐng)域列出。本書向讀者介紹了電子設(shè)計(jì)自動(dòng)化產(chǎn)業(yè)和基本的電子設(shè)計(jì)自動(dòng)化概念，涉及重要的圖概念和算法分析，并仔細(xì)地定義了術(shù)語，用偽代碼表示出了基本算法。書中有很多插圖，每章最后也有一系列習(xí)題且答案都在附錄里。與其他物理設(shè)計(jì)的書不一樣，我們盡力避免不切實(shí)際和不必要的復(fù)雜算法。在許多示例里，我們對幾種主流算法技術(shù)進(jìn)行了比較，并向讀者推薦了包含其他實(shí)驗(yàn)結(jié)果的出版物。
《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》中的一些章節(jié)內(nèi)容參照了在2006年由Springer出版社出版的《電子版圖綜合電路——設(shè)計(jì)自動(dòng)化的基本算法》。
感謝我們的同事和學(xué)生對《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》的早期版本進(jìn)行了校對，并提出了一些改進(jìn)意見，他們是（按英文字母順序排列）：Matthew Guthaus、 Kwangok Jeong、 Seokhyeong Kang、 Johann Knechtel、 Andreas Krinke、 Jingwei Lu、 Nancy MacDonald、 Jarrod Roy、 Kambiz Samadi、 Yen-Kuan Wu和Hailong Yao。
第8章中的全局布局和時(shí)鐘布線圖是由Myung-Chul Kim和Dong-Jin Lee提供的。附錄中的單元庫是由PMC-Sierra公司的Bob Bullock、 Dan Clein和Bill Lye提供的；附錄中的版圖和原理圖是Matthias Thiele生成的。本書的工作得到了美國國家自然科學(xué)基金會(huì)杰出青年教授獎(jiǎng)（CAREER award 0448189）、德州儀器和SUN公司的部分支持。
希望讀者能夠從《超大規(guī)模集成電路物理設(shè)計(jì)：從圖分割到時(shí)序收斂》的閱讀中找到興趣，為專業(yè)提升提供幫助。

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