Abstract
電路群聚問題中，空間和接腳的限制分別具有單調性及非單調性的特質。 藉由可規劃邏輯區塊的複製，我們將此問題轉換成較單純的單調性問題； 亦即當一群聚中可規劃邏輯區塊的數目增加時，接腳數目也必增加。這篇 論文中我們提出一些定理來幫助電路最小延遲目標的達成。這些定理說明 了在電路群聚過程中: (1.)電路中的某些路徑可以被忽略。 (2.)若違反 空間或接腳的限制時，電路分割是必須的。 (3.)保持最新的電路延遲最 少值。這些定理除了可以用在電路群聚問題中也可以用在電路的設計階段 。我們提出一個三階段的演算法，我們稱它為 "ROBN" 演算法；就是分支 節點的複製(Replication Of Branching Node)的縮寫。它以電路的最小 延遲為主要目標來完成電路群聚。如果路徑中的可規劃邏輯區塊被數個群 聚所共有，則路徑的延遲將會增加因為此路徑會經過數個群聚。我們可以 藉由複製這些可規劃邏輯區塊到各個群聚中，因而降低了路徑的延遲。" ROBN" 演算法藉由去除一些不可能是最大延遲的路徑來降低對整個電路 的搜尋。若路徑的延遲不影響整個電路，則區塊的複製可以不被執行。 "ROBN" 演算法就是基於上述的理念所發展出來的。實驗結果顯示場可規 劃邏輯陣列的使用率界於44%到60%之間。"ROBN"演算法在空間和接腳的限 制下可使電路的延遲減小。 The area and pin constraints of the circuit clustering problem are monotonic and non-monotonic, respectively. By the replication of branching nodes, we transfer the problem to a monotonic problem. The transformation makes the problem much easier to handle. When the number of CLBs increases in a cluster, the numbers of both CLBs and pins will increase. Several lemmas and theorems are proposed in this paper. They reveal the following: (1.) Certain paths of a circuit can be ignored while clustering; (2.) A partition can be fulfilled whenever the area or pin constraint of the problem is violated; (3.) The lower bound of the minimum delay is always up to date. The lemmas and theorems can be used not only in the circuit clustering problem but also in the circuit design stage. A three-phased algorithm, called the replication of branching nodes (ROBN) algorithm, is proposed to find all feasible clusters while minimizing the maximum circuit delay. Experimental results show that the ROBN algorithm can find all the feasible clusters of the given circuit. The total number of needed clusters is low and the utilization ratio of FPGAs ranges from 44% to 60%. The ROBN algorithm also minimize the maximum circuit delay under area and pin constraints.