第1章緒論

1．1引言

1．2布線過程

1．2．1總體布線

1．2．2詳細布線

1．2．3軌道分配

1．3布線樹及布線算法研究現狀

1．3．1布線樹的構造算法

1．3．2總體布線算法

1．4研究展望

1．4．1通孔柱工藝下的VLSI性能驅動層布線問題

1．4．2多動態電壓芯片設計環境下的VLSI總體布線問題

1．5本章總結

參考文獻

第2章電路布線問題中的群智能技術

2．1引言

2．2簡介

2．3群智能技術

2．3．1ACO算法

2．3．2PSO算法

2．3．3DE算法

2．3．4ABC算法

2．3．5FA算法

2．4超大規模集成電路中的布線問題

2．4．1Steiner樹

2．4．2總體布線

2．4．3詳細布線

2．5使用群智能技術解決布線問題

2．5．1ACO算法的應用

2．5．2PSO算法的應用

2．5．3DE算法的應用

2．5．4ABC算法的應用

2．5．5FA算法的應用

2．6相關討論

2．6．1基於X結構的多層布線

2．6．2總體布線的多動態電壓設計

2．6．3基於先進通孔柱技術的多層布線

2．7未來研究

2．7．1使用SI的先進技術模型的布線

2．7．2探索新型可用的SI技術

2．8本章總結

參考文獻

第3章X結構Steiner小樹算法

3．1引言

3．2基於離散PSO的X結構Steiner小樹算法

3．2．1XSMT_PSO算法

3．2．2實驗仿真與結果分析

3．2．3小結

3．3基於離散差分進化的X結構Steiner小樹算法

3．3．1傳統差分進化算法

3．3．2算法設計

3．3．3算法仿真與實驗結果

3．3．4小結

3．4基於多策略優化離散差分進化的X結構Steiner小樹算法

3．4．1算法設計

3．4．2算法仿真與實驗結果

3．4．3小結

3．5基於文化基因的X結構Steiner小樹算法

3．5．1MA_XMST算法

3．5．2實驗仿真與結果分析

3．5．3小結

3．6線長驅動的X結構Steiner小樹算法

3．6．1引言

3．6．2算法設計

3．6．3實驗仿真與結果分析

3．6．4小結

3．7本章總結

參考文獻

第4章時延驅動X結構Steiner小樹算法

4．1引言

4．2時延驅動X結構Steiner小樹算法概述

4．2．1問題描述

4．2．2算法設計

4．2．3仿真實驗與結果分析

4．2．4小結

4．3彙延遲驅動的XSMT算法

4．3．1問題描述

4．3．2算法設計

4．3．3仿真實驗與結果分析

4．3．4小結

4．4本章總結

參考文獻

第5章單層繞障X結構Steiner小樹算法

5．1引言

5．2基於離散粒子群優化的X結構繞障Steiner小樹算法

5．2．1算法細節

5．2．2考慮可制造性的後續操作

5．2．3參數策略

5．2．4實驗結果

5．2．5小結

5．3快速繞障X結構Steiner小樹算法

5．3．1引言

5．3．2算法框架

5．3．3算法細節

5．3．4實驗結果

5．3．5小結

5．4X結構繞障Steiner小樹四步啟發式算法

5．4．1算法細節

5．4．2復雜性分析

5．4．3實驗結果

5．4．4小結

5．5本章總結

參考文獻

第6章多層繞障X結構Steiner小樹算法

6．1引言

6．2多層繞障X結構Steiner小樹快速啟發式算法

6．2．1相關工作

6．2．2問題模型

6．2．3算法的設計

6．2．4實驗結果

6．3本章總結

參考文獻

第7章考慮布線資源松弛的X結構Steiner小樹算法

7．1引言

7．2相關工作

7．2．1總體布線

7．2．2Steiner樹

7．2．3主要研究內容

7．3相關理論知識

7．3．1總體布線概述

7．3．2多動態電壓設計模型

7．3．3Steiner樹概述

7．4問題模型

7．5基於多階段優化的XSMTCRRR算法

7．5．1初始拓撲的生成

7．5．2預處理及布線樹的轉換

7．5．3調整

7．5．4冗餘點移除

7．5．5局部拓撲結構優化

7．5．6實驗結果及分析

7．6本章總結

參考文獻

第8章考慮Slew約束的X結構Steiner小樹算法

8．1引言

8．2相關工作

8．3問題相關定義及模型

8．3．1相關定義 

8．3．2Slew約束相關知識

8．3．3問題模型

8．4基於混合離散粒子群優化的Slew約束下X結構Steiner小樹

算法

8．4．1引腳對編碼方式與初始化

8．4．2預處理策略

8．4．3PSO搜尋

8．4．4局部策略

8．4．5混合修正策略

8．4．6算法時間復雜度分析

8．4．7實驗結果

8．5本章總結

參考文獻

第9章X結構總體布線算法

9．1引言

9．2基於ILP和劃分策略的X結構總體布線算法

9．2．1相關研究工作

9．2．2基礎知識

9．2．3ILP模型

9．2．4XGRouter的詳細設計過程

9．2．5實驗結果

9．2．6小結

9．3VLSI中高性能X結構多層總體布線器

9．3．1加強策略

9．3．2基於3種加強策略後布線器的新流程

9．3．3算法的收斂分析

9．3．4算法仿真與結果分析

9．3．5小結

9．4本章總結

參考文獻

過去幾十年來，超大規模集成電路(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月

於福州大學福建省網絡計算與智能信息處理重點實驗室