動態可重組化現場可規劃邏輯陣列藉著在不同時間裡共用同一個邏輯裝置之後有大幅改善邏輯裝置密度的潛力，而且可重組化運算系統變成一個很活躍的研究方向。而在動態可重組化現場可規劃邏輯陣列上執行電路切割的問題和一般傳統的電路切割問題有所不同，是因為在動態可重組現場可規劃邏輯陣列上執行電路切割，會有優先權先後順序的限制，而在傳統的電路切割則不需要考慮這樣的問題。
　　在本論文中，我們著重在探討切割動態可重組化現場可規劃邏輯陣列時，如何降低每階段之間的通訊成本。我們使用一個兩階段的演算法。在第一階段中，利用儘早排程以及儘晚排程來將電路做初始化的切割。再來，我們用一個我們所提出的改良後的列舉式排序法來符合優先權先後順序的限制。在第二階段中，我們使用優先權函數以及複製節點的演算法，來更有效的降低每階段間的通訊成本。實驗的結果證實了我們所使用的演算法對大部分的測試電路相當有效的。

　　Dynamically Reconfigurable FPGAs (DR-FPGAs) have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for DR-FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them.
　　In this thesis, we focus on the communication cost reducing. We use a two phases algorithm, one is the labeling phase, another is the minimizing communication cost phase. In the labeling phase, we use the ASAP and ALAP scheduling to partition the circuit initially. And in this phase, we propose an improved list-scheduling algorithm to satisfy the precedence constraints. In the minimizing communication cost phase, we use the priority function to reduce the communication cost. And we use the temporal logic replication method to reduce the communication cost more efficiently by taking advantage of the slack logic capacity available. The experiment results show that our algorithm is efficient on communication cost reducing for most of the MCNC benchmark circuits.

[1] A. DeHon, “DPGA-coupled microprocessors: Commodity ICs for the 21st
Century,” IEEE Workshop on FPGAs for Custom Computing Machines, pp. 31-39,
1994.
[2] A. DeHon, “DPGA utilization and application,” Proc. ACM Int. Symp. FPGAs,
pp. 115-121, 1996.
[3] D. Chang and M. Marek-Sadowska, “Buffer minimization and
time-multiplexed I/O on dynamically reconfigurable FPGAs,” in Proc. ACM
int. Symp. FPGA, pp.142-148 1997.
[4] D. Chang and M. Marek-Sadowska. “Partitioning sequential circuit on
dynamically reconfigurable FPGAs,” IEEE Transactions on Computer, vol. 48,
pp. 565-578, June 1999.
[5] D. Jones and D. M. Lewis, “A time-multiplexed FPGA architecture for logic
emulation,” In Proc. IEEE Custom Integrated Circuit Conference, pp.
120-124, 1995.
[6] E. Canto, J. M. Moreno, J. Cabestany, I. Lacadena, and J. M. Insenser, “A
temporal bipartitioning algorithm for dynamically reconfigurable FPGAs,”
IEEE Transactions on Very Large Scale Integration Systems, vol. 9, no. 1,
pp. 210-218, February, 2001.
[7] G.. M. Wu, J. M. Lin, and Y. W. Chang, “Generic ILP-based approaches for
time-multiplexed FPGA partitioning,” IEEE Transactions on Computer-Aided
Design, vol. 20, pp. 1266-1274, October, 2001.
[8] H. Liu and D. F. Wong, “Network flow based circuit partitioning for
time-multiplexed FPGAs,” in Proc. IEEE/ACM int. Conf. Computer-Aided
Design, pp. 497-504, 1998.
[9] H. Liu and D. F. Wong, “Circuit partitioning for dynamically reconfigurable
FPGAs,” in Proc. Int. Symp. Field Programmable Gate Arrays. Monterrey, CA,
pp. 187-194 February, 1999.
[10] H. Yang and D. F. Wong, “Efficient network flow based min-cut balanced
partitioning,” in Proc. IEEE/ACM Int. Conference Computer-Aided Design,
pp.50-55, 2000.
[11] H. Yang and D. F. Wong, “New algorithm for min-cut replication in
partitioned circuits,” in Proc. IEEE/ACM Int. Conference computer-Aided
Design, pp.216-222, 1995.
[12] J. Hwang and A. El Gamal, “Min-cut replication in partitioned networks,”
IEEE Transactions on Computer-Aided Design, vol. 14, pp. 96-106, January,
1995.
[13] M. C. T. Chao, G. M. Wu, I. H. R. Jiang, and Y. W. Chang, ”A clustering-
and probability based approach for time-multiplexed FPGA partitioning,” in
Proc IEEE/ACM International Conference on Computer-Aided Design, pp.364-368,
Nov. 1999.
[14] N.B. Bhat, K. Chaudhary, and E.S. Kuh, “Performance-oriented fully routable
dynamic architecture for a field programmable logic device,” Memorandum No.
UCB/ERL M93/42, university of California, Berkeley, 1993.
[15] P. Andersson and K. Kuchcinski, “Performance oriented partitioning for
time-multiplexed FPGA’s,” Euromicro Conference, 2000. Proceedings of the
26th , Volume: 1 , pp. 60-66, Sept. 2000.
[16] S. Trimberger, “Scheduling Designs into a Time-multiplexed FPGA,” in Proc.
ACM Int. Symp. FPGA, pp. 153-160, 1998.
[17] S. Trimberger, “A time-multiplexed FPGA,” in Proc. IEEE Symp.
Filed-programmable Custom Computers. pp. 22-28, March, 1997.
[18] W. K. Mak and E. F. Y. Young, “Temporal logic replication for dynamically
reconfigurable FPGA partitioning,” IEEE Transactions on Computer-Aided
Design of Integrated Circuit and System, vol. 22, No.7, JULY 2003.
[19] Xilinx, Inc., The Programmable Logic Data Book. San Jose, CA:Xilinx, 1996