本書主要介紹超大規(guī)模集成電路中物理設計流程中的總體布線問題以及Steiner小樹算法相結合，提出了超大規(guī)模集成電路中物理設計流程中多種算法來構建直角結構Steiner小樹，例如離散PSO以及DABC算法、絨泡菌算法等等。本書還考慮障礙中布線資源重利用的Steiner小樹構建，并提出了多種策略來進行總體布線，以及層分配的算法優(yōu)化，還基于軌道分配進行詳細布線的實現(xiàn)，后還實現(xiàn)了基于時分復用技術的多階段FPGA布線器，并在每一個小節(jié)都有其實驗結果與分析。
本書主要介紹超大規(guī)模集成電路中物理設計流程中的總體布線問題以及Steiner最小樹算法相結合。
超大規(guī)模集成電路(Very Large Scale Integration, VLSI)是信息產(chǎn)業(yè)的硬件核心，其發(fā)展水平的高低已成為衡量一個國家科學技術和工業(yè)發(fā)展水平的重要標志。在VLSI布線問題中，總體布線和Steiner最小樹算法是一個相互關聯(lián)、充滿活力的研究領域，因此本書系統(tǒng)地剖析、分類和整合超大規(guī)模集成電路領域的總體布線和Steiner最小樹算法，通過不同的方法實現(xiàn)了對VLSI布線算法的優(yōu)化。
近年來，編者及其科研團隊一直致力于超大規(guī)模集成電路領域的布線和Steiner最小樹算法的理論及應用研究，特別是算法的構建及其應用，在此基礎上撰寫了此書。本書內(nèi)容是編者基于自身所主持和參與的國家自然科學基金項目等的研究成果，吸納了國內(nèi)外許多具有代表性的研究成果，融合了課題組近年來在國內(nèi)外重要學術刊物和國際會議上發(fā)表的研究成果，力圖體現(xiàn)國內(nèi)外在這一領域的最新研究進展。本書可作為計算機科學、自動化科學、人工智能等相關學科專業(yè)高年級本科生、研究生以及廣大研究計算智能的科技工作者的參考書。由于編者水平有限，書中難免有疏漏之處，對于本書的不足之處，懇請讀者批評指正。
全書由8章構成，內(nèi)容自成體系，各章內(nèi)容具體安排如下： 第1章是緒論，主要介紹了集成電路設計的基本流程，著重介紹了VLSI物理設計中的總體布線，闡述了Steiner最小樹的問題模型； 第2章介紹了兩種直角結構Steiner最小樹算法； 第3章介紹了兩種繞障直角結構Steiner最小樹算法； 第4章介紹了考慮障礙物中布線資源重利用的直角結構Steiner最小樹算法； 第5章介紹了總體布線中擁塞估計問題、總體布線中總線和非總線線網(wǎng)的布線算法等方面的研究工作； 第6章介紹了多種時延驅動層分配算法； 第7章介紹了基于軌道分配的詳細布線問題，詳細闡述了幾種軌道分配算法和詳細布線算法； 第8章主要介紹了現(xiàn)場可編程門陣列(Field Programmable Gate Array, FPGA)布線算法。其中，第1~2章和第4~8章由劉耿耿完成，第3章由郭文忠完成。
感謝清華大學出版社的大力支持和編輯的辛苦工作。同時，對課題組內(nèi)參與有關研究工作的陳國龍教授、王廷基教授、張浩副教授、劉文皓博士、黃興博士以及莊震、朱偉大、張星海、鮑晨鵬、張麗媛、裴鎮(zhèn)宇、許文霖等碩士生表示衷心感謝。最后，感謝國家自然科學基金項目(61877010、11501114、U21A20472、11271002、11141005)、國家科技部重點研發(fā)計劃課題(2021YFB3600503)、福建省自然科學基金項目(2019J01243、2018J07005) 、福建省科技創(chuàng)新平臺項目(2009J1007)和計算機體系結構國家重點實驗室開放課題(CARCHB202014)等對相關研究工作的資助。
編者
2022年3月
于福州大學福建省網(wǎng)絡計算與智能信息處理重點實驗室
劉耿耿，副教授，博士生導師，中國計算機學會信息系統(tǒng)專委會委員，福建省人工智能學會理事。主要從事計算智能及其應用、集成電路設計算法、機器學習等方面的研究。主持1項國家自然科學基金面上項目、1項國家自然科學基金青年項目等6個項目，并參與了5項國家自然科學基金科研項目，在《IEEE Transaction on Cybernetics》、《IEEE Transactions on Industrial Informatics》、《計算機學報》、《自動化學報》等國內(nèi)外權威刊物和國際會議上發(fā)表70多篇學術論文，其中JCR一區(qū)18篇，JCR二區(qū)3篇，并申請發(fā)明專利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.2ViaPillar
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啟發(fā)式算法框架
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.1RSMTRERR問題定義
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國內(nèi)外研究現(xiàn)狀
5.1.3本章主要工作
5.2問題描述
5.2.1物理設計概述
5.2.2術語和定義
5.2.3總體布線模型圖
5.2.4總體布線方法
5.2.5總體布線的優(yōu)化目標
5.3CGR： 高效的擁塞驅動總體布線算法
5.3.1引言
5.3.2問題描述
5.3.3CGR算法設計與實現(xiàn)
5.3.4實驗結果與分析
5.3.5小結
5.4本章總結
參考文獻
第6章直角結構VLSI層分配算法
6.1引言
6.2問題描述
6.2.1先進制程下的時延驅動層分配問題
6.2.2考慮總線的偏差驅動層分配問題
6.3國內(nèi)外研究現(xiàn)狀及發(fā)展動態(tài)分析
6.4基于非默認規(guī)則線的時延驅動層分配算法
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.1DLA算法設計與實現(xiàn)
6.7.2實驗結果與分析
6.7.3小結
6.8本章總結
6.8.1研究現(xiàn)狀及成果
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設計規(guī)則約束驅動的軌道分配算法
7.5.1引言
7.5.2算法設計
7.5.3實驗仿真與結果分析
7.5.4小結
7.6設計規(guī)則約束驅動的詳細布線算法
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本章總結
參考文獻
書單推薦
