可重組化現場可規劃邏輯陣列進化的速度很快，而且目前愈來愈受到歡迎，因為它提供了一種高效能且具有彈性的超大型積體電路設計技術。
本論文主要是探討當分割動態可重組化現場可規劃邏輯陣列時，如何降低區塊之間的通訊成本，由於時間上的切割關係，使得區塊之間必須要有優先順序的限制，然而在考量優先順序的限制下，會導致我們分割後的導線過度集中，因此我們再想辦法進一步讓導線均勻分散到每個區塊之中。
我們的演算法可分成兩個階段，在第一個階段中，利用儘早排程以及儘晚排程的資訊，將電路作初始的分割，並且得到一組固定節點與彈性節點的集合。在第二個階段中，我們將反覆地調整彈性節點的位置，來降低區塊之間導線的最大數目。實驗的結果證實了我們所使用的演算法是相當有效的。

Dynamically Reconfigurable FPGAs (DR-FPGAs) are evolving rapidly, and they are more and more popular, because they can offer the ability of flexibility and high performance for the VLSI design technology.
In this thesis, we focuses on the communication cost for DR-FPGAs. Due to the temporal partitioning, there may exist acyclic precedence constraints between all k blocks. To preserve the precedence relation in the partitioning step, the interconnections between blocks can be crowded. Hence, we try to distribute the interconnections into each block further.
Our algorithms are divided into two phases：1) In the scheduling phase, we use the information of ASAP and ALAP scheduling to partition the DAG initially, and get the sets of fixed nodes and flexible nodes. 2) In the min-cost phase, we adjust the position of flexible nodes iteratively to lower the upper bound of interconnections between blocks. Experimental results for the benchmark circuits demonstrate the effectiveness of our algorithms.

[1] S. Trimberger, “A time-multiplexed FPGA”, Proc FCCM, 1997, pp22-28.
[2] S. Trimberger, “Scheduling Designs into a Time-multiplexed FPGA”, International Symposium on Field Programmable Gate Arrays, Feb, 1998, pp.153-160.
[3] D. Chang and M. Marek-Sadowska, “Partitioning Sequential Circuits on Dynamically Reconfigurable FPGAs”, Computers, IEEE Transactions on , Volume: 48 Issue: 6 , June 1999, pp. 565 –578.
[4] A. DeHon, “DPGA-coupled microprocessors：Commodity ICs for the early 21st century” In IEEE Workshop on FPGAs for Custom Computing Machines,1994, pp. 31-39.
[5] D. Jones and D. M. Lewis, “A time-multiplexed FPGA architecture for logic emulation”, In IEEE Custom Integrated Circuits Conference,1995, pp.120-124.
[6] H. Liu and D. F. Wong, “Network flow based circuit partitioning for time-multiplexed FPGAs” in Proc.ICCAD, San Jose, CA, Nov.1998, pp.497-504.
[7] H. Liu and D. F. Wong “Circuit partitioning for dynamically reconfigurable FPGAs,” in Proc. Int. Symp. Field programmable Gate Arrays, Monterrey, CA, Feb.1999,pp.187-194.
[8] K.Purna and D.Bhatia, ”Temporal partitioning and scheduling data flow graph for reconfigurable computers,” IEEE Trans. Computers,vol.48,June 1999, pp579-590.
[9] E.Canto, J.M. Moreno, J. Cabestany, j. Faura, and J. M. Insenser “A bipartitioning algorithm for dynamically reconfigurable programmable logic”, in Field Programmable Logic and Applications (FPL’99) Sept.1999, pp. 134-143.
[10] Chao, G.M. Wu, Jiang, and Y. W. Chang, “A clustering- and probability-based approach for time-multiplexed FPGA partitioning” Computer-Aided Design, 1999. Digest of Technical Papers. 1999 IEEE/ACM International Conference on , 7-11 Nov. 1999, pp. 364-368.
[11] P.Andersson and K. Kuchcinski, “Performance oriented partitioning for time-multiplexed FPGA's” Euromicro Conference, 2000. Proceedings of the 26th , Volume: 1 , 5-7 Sept. 2000, pp. 60-66
[12] G.M. Wu, J.M. Lin, and Y. W. Chang; ” Generic ILP-based approaches for time-multiplexed FPGA partitioning”, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , Volume: 20 Issue: 10 , Oct. 2001, pp. 1266-1274
[13] B.W. Kernighan and S. Lin, “An efficient huristic procedure for partitioning graph”, Bell System Tech. Journal, vol.49, 1970, pp291-307.
[14] C.M. Fidducia and R.M. Matheyses, “A linear-time heuristic for improving network partitions”, Proc. DAC, 1982, pp.175-181.
[15] Xilinx, Inc., The Programmable Logic Data Book. San Jose, CA:Xilinx, 1996.