FPGA中以效能為導向之多資源限制電路分割法

performance driven FPGA partitioning with complex resources

洪羽珊(Yu-Shan Hung)

指導教授 ： 謝財明 ； 謝財明

中原大學/工學院/資訊工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100037

摘要

為爭取產品上市時間，現場可程式化邏輯閘陣列（FPGA）這硬體架構以廣泛的被運用，而電路的日益龐大與複雜，或是為了面積大小的問題，或為了希望將電路簡單化，因此將整個電路分割成子電路來實踐也是必要的。而以FPGA來實踐電路時，雖然其具有可現場程式化的優點，但其效能是其對大的缺點，因此較少用來實踐許多即時系統。而若處理FPGA分割問題時，因為必須將電路分割至不同的FPGA中，效能面對更大的挑戰，因為要跨過兩個FPGA的連線（wire）之延遲時間勢必增加許多，因此我們希望在做FPGA分割時能夠以效能為導向，降低其關鍵性路徑（critical path）上的延遲時間。

又因為現在FPGA製作技術進步，以往的單資源FPGA以不敷使用，漸漸的發展出多資源FPGA，因此我們的研究就是希望在以效能為導向的情況下，成功的將電路分割至成本（cost）最小的多資源FPGA中。

在將電路分割時，以其關鍵性路徑為考量，盡量不要再增加關鍵性路徑上的延遲時間的前提下，將電路完成分割。在實驗結果中，我們可以發現此研究除了可以將電路以成本最小化的目標成功分割之外，在效能上的確有很大的改進。

關鍵字

現場可程式化邏輯閘陣列 ； 單資源限制 ； 分割 ； 多資源限制 ； 整數線性規劃 ； 關鍵性路徑

並列摘要

To shorten time to market , the architecture , FPGA, is used widely. Because the circuit is larger and more complex, it is necessary to partition a large circuit to several sub-circuits. Although a FPGA is programmable, the chief shortcoming of FPGA is poor performance, so that many real time systems can not implemented by FPGAs, especially when we deal with the problem of FPGA partitioning, the performance problem is more serious. We will partition the circuit to several different FPGAs and the delay of the wires cross two FPGAs is larger. We hope to decrease the delay of the critical path to achieve the performance driven goal.
As the fabrication technology rapidly evolves, the FPGA with single resource is not enough, so the architecture of FPGA with complex resources is brought up. The Objective of our research is performance driven partitioning that partition the circuit to FPGAs with complex resources successfully with cost minimization.
When we partition the circuit, we do not increase the delay of the critical path as far as possible. In the results of the experiments, we can see the algorithm not only partition the circuit with cost minimization but also improve the performance of the partitioning.

並列關鍵字

Partition ； FPGA(Filed Programmable Gate Array) ； Single resource constraint ； Complex resources constraints ； ILP(Integer Linear Programming) ； Critical path

參考文獻

[1] C.J. Aplert and A.B. Kahug, “A General Framework for Vertex Orderings, With Applications to netlist Clustering.”, Proc. IEEE Intl. Conf. on Comjputer-Aided Design, pp.63-67, 1994.

[2] C.J. Aplert and A.B. Kahug , “Recent Directions in Netlist Partition: a Survey”, the VLSI Journal, pp.181, 1995.

[3] B.W. Kermighan and S.Lin, “An Efficient Heuristic Procedure for Partition Graphs”, Bell system Tech. Journal, vol. 49, pp. 291-307, Feb. 1970.

[5] Raghu Burra and Dinesh Bhatia “Timming Driven Multi-FPGA Board Partitioning”, IEEE VLSI design 1998.

[6] R. Burra and D. Bhatia, “ Timing Driven Multi-FPGA Board Partitioning,”, Proc. IEEE Conf. on VLSI Design , pp: 234 -237 .1998