Abstract
由於現場可程式化陣列邏輯閘（EPGA）的設計流程簡單，製造過程快速，迅速成為受歡迎的設計型態（design style），常被用來設計電路的原型。然而要將一個大的電路系統用一些現場可程式化陣列邏輯閘晶片（EPGA chip）實作出來時，就要採用分割的技巧來把電路分散對應到各個現場可程式化陣列邏輯閘晶片中去，這時就要考慮到現場可程式化陣列邏輯閘晶片本身具有的一些限制如：面積限制（area constraints）與接腳數目限制（pin constraints）。 現場可程式化陣列邏輯閘晶片的分割問題中的兩個限制－面積限制與接腳數目限制，分別具有單調性與非單調性，這會使得分割電路時難以決定是否要在叢集中加入一個可規劃邏輯區塊。複製有分支的可規劃邏輯區塊可以簡化這個問題。複製一些有分支的可規劃邏輯區塊之後不僅使得接腳數目限制由非單調性轉換為單調性，也就是說當叢集中的可規劃邏輯區塊增加時，叢集的接腳數目也會增加，同時也可以使得分割的結果之後切割數目更少，因為我們在分割一個最長路徑時是儘量滿足面積限制但使用複製的方法來滿足接腳數目的限制，此外現場可程式化陳列邏輯閘晶片的使用率也可以略為提高。 我們提出了一個修改過的單一路徑叢集分割法（Modified PC-Strategy）來對那些無法完全放入同一叢集中的最長延遲路徑做分割，搭配上林志賢先生[１]所提出的一些定理雪展了一個三階段的Modified-ROBN演算法來做叢集分割。在對數個ISCAS的組合式電路做了測試之後，我們發現Modified-ROBN法不僅可以找到所有合理的叢集，其得到的結果中最長延遲路徑的延遲時間也較[1]中的結果更小，而且現場可程式化陣列邏輯輯閘晶片的使用率也提高了一些。