跳到主要內容

臺灣博碩士論文加值系統

(3.236.23.193) 您好!臺灣時間:2021/07/24 14:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:趙英志
研究生(外文):Ying-Chih Chao
論文名稱:VLSI電路之主輸入端扇形錐交集
論文名稱(外文):Intersection of Input Fanout Cones of VLSI Circuits
指導教授:林榮彬林榮彬引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:97
語文別:中文
論文頁數:19
中文關鍵詞:關係交集
外文關鍵詞:relationintersection
相關次數:
  • 被引用被引用:0
  • 點閱點閱:120
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
分割(partition)和群聚(cluster)是處理龐大和複雜問題的一種非常有用的方法,尤其是在VLSI的領域範圍,將一個電路分割成較小的群組,依所需要之條件,使同一群組內的元素(element)之間關聯性強弱分析問題,在時間和空間上的複雜度都會有一定程度的降低。
在此篇論文中,我們提出了快速且有效率的方法,相對於傳統的方法將所有的主輸入端(primary input)之扇形錐(fanout cone)兩兩比對找交集,我們的方法首先是找出交集為100%關係,再以比對的方式找出非0%的部份,最後剩餘的部份就是關係為0%的主輸入端。實驗結果顯示我們的方法比傳統的方法的速度最快達39%,而我們的結果可以提供作為分析電路之應用,如找分析關係較密切的輸入端做群聚,進而找出使電路於待機模式(stand by node)下主輸入端的狀態來所產生最大或最小的漏電流(leakage)。
Partitioning and clustering are very effective methods to deal with huge and complicated problems, especially in the field of VLSI. Dealing with subproblems derived from the parts generated by partitioning (clustering) a circuit according to some requirements can reduce the time and space complexity of solving a problem.
In this thesis, we proposed an effective method to find the relationship of primary inputs of a circuit. The relationship between two primary inputs is defined as the number of gates in the intersection between two fanout cones rooted at the primary inputs divided by the number of gates in the two underlying fanout cones, whichever is larger. Our method first finds the primary input pairs which has a 100% relationship without making a full comparison between two underling primary input fanout cones. It then finds the non-zero relation pairs that each need a full comparison between two primary input fanout cones. It finally finds the zero-relation pairs without making any comparison of primary input fanout cones. The experimental result shows that our approach achieves about 39% speedup than the traditional one which compares all fanout cones of primary inputs to obtain intersections. Application of our results to form clusters of primary inputs with strong relation has been explored for finding an input vector that incurs a maximum/ minimum leakage current.
List of Figures x
List of Tables xi
Chapter 1. Introduction 1
1.1 Background 1
1.2 Scope of the work and contribution 3
1.3 Thesis organization 4
Chapter 2. Related work 5
Chapter 3. Method 9
3.1 Constructing the data structure from net list file 11
3.2 Finding the relations of primary inputs 13
Chapter 4. Experimental results 16
Chapter 5. Conclusions 18
References 19
[1] Guang-Wan Liao; Ja-Shong Feng and Rung-Bin Lin, “A Divide-and-Conquer Approach to Estimating Minimum/Maximum Leakage Current,” Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium, pp. 4717 - 4720 Vol. 5, 23-26 May 2005.
[2] E. Hartuv and R. Shamir, “A Clustering Algorithm based on Graph Connectivity,” Information Processing Letters, pp. 175-181, 2000.
[3] Earl R. Barnes, “An Algorithm for Partitioning the Nodes of a Graph,” Journal of Society for Industrial and Applied Mathematics, Vol. 3, No. 4, pp. 541-550, 1982.
[4] S. B. Akers, “Clustering Techniques for VLSI,” IEEE Int. Symp. on Circuits and Systems, pp. 472-476. 1982.
[5] C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for im-proving network partitions,” Proc. 19th Design Automation Conf., pp. 175-181, 1982.
[6] B. W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” Bell System Tech. Journal, vol. 49, pp. 291-307, Feb. 1970.
[7] D. G Schweikert and B.W. Kemighan, “A Proper Model for the Petitioning of Electrical Circuit,” in Proc. 9th Design Automation Workshop, Dallas, TX, pp. 57-62, 1979.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top