跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.86) 您好!臺灣時間:2025/02/09 00:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:段榮保
研究生(外文):Jung-Pao Twan
論文名稱:最小化串音效應之多階層式繞線方法
論文名稱(外文):A Multilevel Routing Algorithm for Crosstalk minimization
指導教授:陳美麗陳美麗引用關係
指導教授(外文):Mely Chen
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:86
中文關鍵詞:多階層式繞線轉換時間maze繞線方法擁擠度串音效應細部繞線廣域繞線
外文關鍵詞:Slew timeMultilevel routingCrosstalkMaze search routeDetail routeGlobal route
相關次數:
  • 被引用被引用:2
  • 點閱點閱:335
  • 評分評分:
  • 下載下載:35
  • 收藏至我的研究室書目清單書目收藏:0
由於製成的技術不斷的進步,半導體元件在越來越小的佈局面積下,卻要求越驅複雜的功能、越加快速的切換頻率,進而使串音效應(crosstalk)對於電路在功能與時序上的影響與日俱增,成為在設計電路時相當重要的一項考量因素。
本篇論文使用了近年來廣泛被討論的多階層式繞線架構,並且對於導線間的串音效應降低為主要的繞線考量。在廣域繞線階段,採用L shaped及Z shaped之pattern routing繞線方法,除了擁擠度的考量外,利用轉換時間(slew time)資訊,避免將容易形成串音效應的導線配置於相同的廣域繞線路徑上,以此降低未來形成相鄰導線的可能性。而在細部繞線階段,我們則是利用傳統的maze繞線方法,並且同時考量兩導線間slew time與的平行線段長度和距離間的關係,此外對於繞線過程中所形成的via也一併加入我們細部繞線的成本函數。
實驗結果可以發現,本論文所提出的方法與一般只考量降低平行線段長的crosstalk-driven的繞線方法比較下,在降低整個設計電路的因串音效應所產生的耦合電容上可降低約11%,而在via數也可降低約18%,在降低fail net數目產生也約有50%改善,繞線完成度平均都達到99%以上。
As the process technology progressing, the VLSI circuits are requested to work with more complex functionality and faster switching frequency within a smaller die size. Therefore the crosstalk between interconnect wires has become an important issue, it has serious influences on functionality and timing.
In this paper, we utilize a multilevel routing structure to reduce the crosstalk effect between neighboring parallel wires. In the global routing stage, we adopt the L-shape and Z-shape pattern routing methodology. We not only consider the routing congestion in this stage, but also make the long slew time nets and short slew time nets separate. In the detail routing stage, we use the modified maze search route algorithm which simultaneously consider the coupling capacitance (considering slew time、coupling length and coupling distance) and via number during the maze routing processing.
In the experiments, we use the real circuit cases as our test cases. Compared with the routing algorithm which only try to reduce the neighboring parallel wires, our algorithm can produce the routing with 11% lower coupling capacitance value and 18% lower via number. Besides, our algorithm decreases 50% fail net number. The most important is that the completion rate is over 99% in these test cases in which the row utilizations are about 80%.
目 錄

第一章 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
第二章 相關背景介紹. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 3
2.1 多階層式繞線架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Coupling Capacitance計算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Maze Route演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Physical Coupling Crosstalk Model. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 16
第三章 問題描述方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
3.1 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .17
3.2 問題描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 多階層降低串擾效應繞線方法簡介. . . . . . . . .. . . . . . . . . . . . . . . . . . . . .20
第四章 成本函數. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
4.1 Global Route採用的成本函數介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
4.2 Detail Route採用的成本函數介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
第五章 演算法、資料結構與程式流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1 演算法的執行步驟. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45
5.2 資料結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49
5.3 程式流程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51
第六章 實驗結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1 實驗數據 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .53
6.2 導線Slew Time分佈. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 54
6.3 三種不同成本考量之繞線結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56
6.4 繞線方法三釋疑. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64
6.5 三種不同成本考量之繞線結果比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .68
第七章 結論與未來方向. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.1 結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
7.2 未來方向. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
附錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
作者簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

圖 目 次

圖 2-1 : 廣域繞線圖形模型 (The Routing Graph) [9] . . . . . . . . . . . . . . . . . . . . . . 4
圖 2-2: 多層次繞線架構流程 (The Multilevel Framework Flow) [9]. . . . . .. . . . . 4
圖 2-3: 時序圖(case1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7圖
2-4: full overlap of node voltages示意圖(case 2) . . . . . . . . . . . . . . . . . . . . . . . .10
圖 2-5 : full overlap of voltages 示意圖( case 3) . . . . . . . . . . . . . . . . . . . . . . . . . . .10
圖 2-6: partial overlap of node voltages示意圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
圖 2-7 : partial overlap of voltages 示意圖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
圖2-8 : Switching Factor與Slew Time比值關係圖. . . . . . . . . . . . . . . . . . . . . . . . .14
圖 2-9 : Lee Algorithm [12] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
圖 2-10 : Physical coupling crosstalk[3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
圖 3-1 : 本論文所使用的Physical coupling model . . . .. . . . . . . . . . . . . . . . . . . . . 18
圖 3-2 : Tiles與Grids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
圖 3-3 : 一個簡略電路圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
圖 3-4 : Multilevel 架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
圖 4-1 : Global route的L/Z shape paths. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .26
圖 4-2 : 一個tile上下左右四邊之繞線容量. . . . . . . . . . . . . .. . . . . . . . . . . . . . . .28
圖 4-3 : 一個global routing 例子與其對應的初始global routing graph. . . . . . . . 28
圖 4-4 : net1選擇出一條廣域繞線路徑. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
圖 4-5 : net2選擇出一條廣域繞線路徑. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
圖 4-6 : net3選擇出一條global routing path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
圖4-7 : 本例中細部繞線最近與最遠產生串音效應的情況. . . . . . . . . . . . . . . . . .35
圖 4-8-1 : wave propagation範例. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 35
圖 4-8-2 : wave propagation範例. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 39
圖 4-8-3 : trace back範例. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 43
圖5-1 : Pseudo code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .48
圖 5-2 : 紀錄net所使用的資料結構. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 49
圖 5-3 : 本程式主要資料結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
圖 5-4 : 多階層繞線資料結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
圖 5-5 : 程式流程圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
圖6-1 耦合電容與導線間距關係. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 54
圖6-2-1 s13207 slew time分佈圖. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .54
圖6-2-2 s15850 slew time分佈圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
圖6-2-3 s35932 slew time分佈圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
圖6-2-4 s38417 slew time分佈圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
圖6-2-5 s38584 slew time分佈圖. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
圖6-3-1 s13207在Dva=1s與不同參數下,平均耦合電容. . . . . . . . . . . . . . . . . . . 60
圖6-3-2 s15850在Dva=1s與不同參數下,平均耦合電容. . . . . . .. . . . . . . . . . . . . 60
圖6-3-3 s35932在Dva=1s與不同參數下,平均耦合電容. . . . . . . . . . .. . . . . . . . . 60
圖6-3-4 s38417在Dva=1s與不同參數下,平均耦合電容. . . . . . . . . . . .. . . . . . . . 61
圖6-3-5 s138584在Dva=1s與不同參數下,平均耦合電容. . . . . . .. . . . . . . . . . . . 61
圖6-3-6 s13207在Dva=5s與不同參數下,平均耦合電容. . . . . . . . . . . . . . . . . . . 62
圖6-3-7 s15850在Dva=5s與不同參數下,平均耦合電容. . . .. . . . . . . . . . . . . . . . 62
圖6-3-8 s35932在Dva=5s與不同參數下,平均耦合電容. . . . . . . . . . . . . . . . . . . 62
圖6-3-9 s38417在Dva=5s與不同參數下,平均耦合電容. . . . . . . . . . . . . . . . . . . 63
圖6-3-10 s38584在Dva=5s與不同參數下,平均耦合電容. . . . . . . .. . . . . . . . . . . 63
圖6-4-1 s13207在方法Ⅱ與方法Ⅲ下的累積耦合電容變化. . . . . . . . . . . . . . . . . . 65
圖6-4-2 s15850在方法Ⅱ與方法Ⅲ下的累積耦合電容變化. . . . . . . . . . . . . . . . . . 65
圖6-4-3 s35932在方法Ⅱ與方法Ⅲ下的累積耦合電容變化. . . . . . . . . . . . . . . . . . 65
圖6-4-4 s38417在方法Ⅱ與方法Ⅲ下的累積耦合電容變化. . . . . . . . . . . . . . . . . . 66
圖6-4-5 s38584在方法Ⅱ與方法Ⅲ下的累積耦合電容變化. . . . . .. . . . . . . . . . . . 66
圖6-5-1 s13207在方法Ⅱ與方法Ⅲ下的累積Via變化 . . . . . . . . . . . . . . . . . . . . . 67
圖6-5-2 s15850在方法Ⅱ與方法Ⅲ下的累積Via變化. . . . . . . . . . . . . . . . . . . . . . 67
圖6-5-3 s35932在方法Ⅱ與方法Ⅲ下的累積Via變化. . . . . . . . . . . . . . . . . . . . . . 67
圖6-5-4 s38417在方法Ⅱ與方法Ⅲ下的累積Via變化. . . . . . . . . . . . . . . . . . . . . . 68
圖6-5-5 s38584在方法Ⅱ與方法Ⅲ下的累積Via變化. . . . . . . . . . . . . . . . . . . . . . 68


表 目 次
表 3-1 : Net weighting from wiring distribution map[15] . . . . . . . . . . . . . . . . . . . . . 22
表6-1 測試電路. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
表6-2 本實驗的Objective. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 56
表6-3-1在考量Dva=1s情況下IA與ⅡA比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
表6-3-2在考量Dva=5s情況下IA與ⅡA比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
表6-3-3 Dva=1s以內相鄰導線,ⅢA在不同γ與κ參數設定所得數據. . . . . . . . 58
表6-3-4 Dva=5s以內相鄰導線,ⅢB在不同γ與κ參數設定所得數據. . . . . . . . . . 59
表6-4-1 ⅡA and ⅢA(1:10) compare withⅠA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
表6-4-2 ⅡB and ⅢB(1:10) compare withⅠB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
[1] Kahng, A.B.; Muddu, S.; Sarto, E., “On switch factor based analysis of coupled RC interconnects,” in Proc. Design Automation Conference, June 5-9, 2000 , Pages:79 - 84 .
[2] T. Sakurai and K. Tamaru, “Simple formulas for two and three dimensional capacitance,” IEEE Transactions on Electron Devices, Pages:183-185, 1983.
[3] Ki-Wook Kim; Sung-Mo Kang, “Crosstalk noise minimization in domino logic design,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Volume: 20 , Issue: 9, Pages:1091 – 1100 , Sept. 2001.
[4] Chou, H, and S Chiu, "Crosstalk Reduction and Tolerance in Deep Sub-Micron Interconnects," Department of Electrical and Computer Engineering, University of Wisconsin, Madison, WI.
[5] Song-Ra Pan; Yao-Wen Chang, “Crosstalk-constrained performance optimization by using wire sizing and perturbation,” in Proc. International Conference on Computer Aided Design , Pages:581 – 584 , 17-20 Sept. 2000.
[6] Saxena, P.; Liu, C.L., “Crosstalk minimization using wire perturbations,” in Proc. Design Automation Conference, Pages:100 – 103, 21-25 June 1999.
[7] K.Chaudhary, A. Onozawa, and E. S. Kuh , “A Spacing Algorithm for performance Enhancement and Crosstalk Reduction,” in Proc. International Conference on Computer-Aided Design, Pages: 697-702, Nov. 1993.
[8] T. Gao and C. L. Liu , “Minimum crosstalk channel routing,” in Proc. International Conference on Computer Aided Design, Pages: 692-696, Nov. 1993.
[9] S.-P. Lin and Y.-W. Chang,“A novel framework for multilevel routing considering routability and performance,”in Proc. International Conference on Computer Aided Design, pp.44-50, Nov. 2002.
[10] J.Cong, M.Xie, and Y.Zhang, “An Enhance Multilevel routing system,” in Proc. International Conference on Computer Aided Design, pages:51-58, Nov 2002
[11] J.Cong, J.Fang, and Y.Zhang, “Multilevel Approach to Fill-chip gridless Routing,”in Proc. International Conference on Computer Aided Design, pages:396-403, Nov 2001.
[12] Lee, “An algorithm for path connection and its application,” IRE Transactions on Electronic Computer, EC-10, 1961
[13] 黃于容, ”最小化串音效應之多階層式繞線方法,” 私立中原大學資工研究所碩士論文, 2003.
[14] Alpert, C.J.; Devgan, A.; Quay, S.T., “Buffer insertion for noise and delay optimization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 18 , Issue: 11 , Pages:1633 - 1645, Nov. 1999.
[15] Chih-liang Eric Cheng, “Risa: Accurate And Efficient Placement Routability Modeling,” in Proc. International Conference on Computer Aided Design, pages:690 – 695,Nov 1994.
[16] T. Sakurai, “Closed-form Expressions for Interconnection Delay,Coupling, and Crosstalk in VLSI’s”, IEEE Trans. on Electron Devices, pp. 118-124, 1993.
[17] Rahmat, K.; Neves, J.; Lee, J.-F., “Methods for calculating coupling noise in early design: a comparative analysis” in Proc. International Conference on ICCD, Pages:76 – 81, Oct. 1998.
電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 顏綠清(1980)。大學生國文態度之研究。教育學院學報,5(3),3-125。
2. 鄭耀嬋、何華國(2004)。國小融合班學生學習態度及其相關因素之探討。國民教育研究學報,13,215-260。
3. 劉貞宜(2001)。數學資優生的解題歷程分析—以建中三位不同能力的數學資優生為例。資優教育研究,1(2),97-120。
4. 劉明洲(2000)。物件式編輯系統程式設計之解題歷程研究。花蓮師院學報,11,205-230。
5. 廖國鋒、葉中桂(1987)。國防管理學院學生學業成就與家庭社經背景態度關係之研究。國防管理學院學報,9(2),43-62。
6. 趙貞怡、劉傳璽(2004)。結構性LOGO環境對國小學童在角/旋轉認知及解決問題策略之影響。教育研究資訊,12(2),61-94。
7. 黃茂在、陳文典(2004)。「問題解決」的能力。科學教育月刊,273,21-42。
8. 陳玉花(1995)。學生學習責任與成就之探討。學生輔導,38,100-107。
9. 張國恩(1999)。資訊融入各科教學之內涵與實施。資訊與教育雜誌,72,2-9。
10. 徐龍政(1995)。LOGO作為國小資訊課程初學者語言之適用性研究。臺東師院學報,6,187-208。
11. 何榮桂(1998)。從教育部之資訊教育推展策略看未來中小學資訊教育的遠景。資訊與教育,68,2-13。
12. 吳明隆(1997)。減低電腦焦慮之輔導策略。國教之友,545,27-31。
13. 李文政(1990)。Children's Learning Geometric Concepts: Logo As A Learning Environment。國立政治大學學報,63,373-400。
14. 朱湘吉(1994)。原案分析法簡介。教學科技與媒體,14,49-53。
15. 王鼎銘(2000)。資訊時代數位影像對美感價值的沖擊與影響。教學科技與媒體,51,2-8。