非曼哈頓結構下超大規模集成電路布線理論與算法

本書系統討論了非曼哈頓結構下超大規模集成電路布線設計的理論與算法，介紹了超大規模集成電路相關定義、研究現狀，並提出了對未來研究方向的展望，側重於介紹非曼哈頓結構Steiner樹布線算法的構建，其中布線樹考慮包括線長驅動、時延驅動、單層繞障、多層繞障、Slew約束等因素，設計了包括混合轉換、多階段轉換、預處理、局部處理、基於整數線性規劃和劃分等諸多有效策略，從而構造多種高效的非曼哈頓結構下的布線器。本書還介紹了應用於超大規模集成電路布線問題的群智能技術。期望的讀者是電腦行業電子設計自動化方面的本科生、研究生與工程師等相關研究人員。

 

目錄

 

 

 

第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本章總結

 

參考文獻