由於現場可程式化陣列邏輯閘（FPGA）可以大幅降低整個設計和製造過程所需要的時間，因此被廣為應用在特殊積體電路（ASIC）的設計上，但是因為許多的應用，越來越要求系統的速度和效能（Performance），所以我們在分割一個大型的電路到許多的現場可程式化陣列邏輯閘晶片（FPGA chips）上時，必須儘量的減少因分害所帶來的延遲時間，同時也要滿足FPGA本身硬體上的限制，如面積（area）和接腳（pin）的數目等等。
本論文的第一部分是一個三階段（1）標記（labeling）（2）叢集（clustering）（3）壓縮（packing）的演算法，目的是在符合FPGA的面積和接腳數的限制下，減少電路的最大延遲時間。在標記階段中尋找滿足上述兩個限制的叢集，然後在叢集分割階段則從路徑的PO開始往PI的方向，亦即由下往上（bottom-up）的方式叢集分割整個電路，接著再使用類似於Bin-Packing的方法來減少叢集（clusters）到合理的數目。第二部分是對第一部分的方法加以修改，使減小最大延遲時間和複製CLB的數量取得平衡；一開始先把電路分成一個個的groups，然後我們限制CLB複製的數目，在這個數目的限制下，合併最大延遲路徑所經過的groups，並且叢集分割所有groups之內的CLBs，以試著減小電路的最大延遲時間，但則同時也必須付出因複製而增加CLB數目的代價，重複上述這些步驟直到所能複製的上限為止。
最後我們用ISCAS的測試電路（benchmark）得到一些結果，由實驗的數據經過比較，可以看出第一部分的方法對減小電路的最大延遲時間有很好的效果，但是會複製許多的CLB，而且叢集的數目也不少；第二部分的方法，限制CLB的複製數量，就能在合理的叢集數目下，獲得不錯的電路最大延遲時間。
|