VLSI電路之主輸入端扇形錐交集

Intersection of Input Fanout Cones of VLSI Circuits

趙英志(Ying-Chih Chao)

指導教授 ： 林榮彬

元智大學/資訊學院/資訊工程學系/碩士(2009年)

https://doi.org/10.6838/YZU.2009.00177

摘要

分割(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.

並列關鍵字

relation ； intersection

參考文獻

[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.

[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.