使用模糊分群法處理積體電路設計上之圖形分割問題

Abstract

在電路系統階層化設計中，分割扮演一種非常重要的角色。因為好的分割 可以降低問題的複雜度和改進系統的績效與可靠度。本論文提出一種圖形 分割上的模糊分群法(FCMGP)來處理積體電路設計上之分割問題。使用模 糊分群法來處理圖形分割時，有兩個困難點必須要克服。第ㄧ，分群的群 中心須為圖形中的節點才合理。我們提出一種圖形分割上的模糊分群法， 因為它不用計算群中心，所以解決了上述的問題。第二 ，在圖形中，任 兩個節點間沒有幾何距離的存在，所以我們採用Y-H所定義的分群距離來 處理。最後，除顯示一些積體電路多維分割的結果外，並探討未來的研究 工作。 Partitioning plays an important role in finding the hierarchy of a circuit or a system. Good partitioning can significantly reduce the complexity of a design problem and improve both the performance and the reliability of the system. This thesis proposes a fuzzy c-means for graph partitioning (FCMGP) in integrated circuit design. The FCM algorithm is applied to graph partitioning, two problems must be processed. First, it is feasible that the centroids must be vertices in the graph. We proposed a fuzzy c-means for graph partitioning algorithm which can not compute the centroids for solving the above problem. Second, it exists no geometrical distance between any pair of vertices in the graph. Therefore, we used the clustering distance was defined by Y-H. Finally, some results of the multiple-way partitioning for integrated circuit design are presented and the future work is discussed.